Corning Community College CSCS2320 Data Structures ~~TOC~~ ======Project: DLL1====== =====Errata===== This section will document any updates applied to the project since original release: * __revision 1__: Implemented a few refinements to unit-obtain (20150415) =====Objective===== In this project, we continue our doubly linked list re-write, completing the remaining library functions. =====Procedure to Obtain dll1===== As this project utilizes the code you wrote in dll0, you must upgrade to dll1 from dll0 (same thing that we did to transition between the sll* projects): lab46:~/src/data/dll0$ make upgrade-dll1 ... =====Project Overview===== As we started with the last project, we're implementing the remaining functions of our new doubly linked list implementation. As such, new function prototypes have been added to the list.h header file: unsigned char rmlist (List **); // deallocate empty list unsigned char obtain (List **, Node **); // obtain/disconnect node from list unsigned char compare(List *, List *, long int *); // compare two lists for equality unsigned char empty (List **); // empty an existing list unsigned char sort (List **, char); // sort list (according to mode) unsigned char swap (List **, Node *, Node *); // swap positions of given nodes in list These functions will also make use of the status/error codes introduced in dll0. Additional effort has gone into identifying likely codes applied in various conditions. Be sure to reference the provided comments as well as the unit tests for more information. ====list operation status codes==== You'll notice the presence of a set of #define's in the list header file. These are intended to be used to report on various states of list status after performing various operations. They are not exclusive- in some cases, multiple states can be applied. The intent is that you will OR together all pertinent states and return that from the function. * **DLL_SUCCESS** - everything went according to plan, no errors encountered, average case * **DLL_MALLOC_FAIL** - memory allocation failed (considered in error) * **DLL_ALREADY_ALLOC** - memory has already been allocated (considered in error) * **DLL_NULL** - result is NULL (probably in error) * **DLL_EMPTY** - result is an empty list (may or may not be in error) * **DLL_DEFAULT_FAIL** - default state of unimplemented functions (default error) * **DLL_FAIL** - some error occurred For example, in the case of "DLL_MALLOC_FAIL", there are actually a total of three states raised: * DLL_FAIL (a problem has occurred) * DLL_MALLOC_FAIL (a problem has occurred when using malloc()) * DLL_NULL (no memory allocated, so list cannot be anything but NULL) ALL THREE states must be returned from the function in question should such an occurrence take place. ====list library==== In **src/list/**, you will find the addition of a new set of skeletons of the above prototyped functions, hollowed out in anticipation of being made operational. Figure out what is going on, the connections, and make sure you understand it. Be sure to focus on implementing the functionality from scratch (the more you do this from scratch, vs. referencing old code, the more it will help you). ====List library unit tests==== In **testing/list/unit/**, you will find these new files: * **unit-rmlist.c** - unit test for **rmlist()** library function * **unit-obtain.c** - unit test for **obtain()** library function * **unit-compare.c** - unit test for **compare()** library function * **unit-empty.c** - unit test for **empty()** library function * **unit-sort.c** - unit test for **sort()** library function * **unit-swap.c** - unit test for **swap()** library function Enhancements to these unit tests may be provided via dll1 project updates. There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent list functionality. These are complete runnable programs (when compiled, and linked against the list library, which is all handled for you by the **Makefile** system in place). Of particular importance, I want you to take a close look at: * the source code to each of these unit tests * the purpose of these programs is to validate the correct functionality of the respective library functions * follow the logic * make sure you understand what is going on * ask questions to get clarification! * the output from these programs once compiled and ran * analyze the output * make sure you understand what is going on * ask questions to get clarification! =====Expected Results===== To assist you in verifying a correct implementation, a fully working implementation of the node and list libraries should resemble the following (when running the respective verify script): ====node library==== Here is what you should get for node: lab46:~/src/data/dll1$ bin/verify-node.sh ==================================================== = Verifying Doubly-Linked Node Functionality = ==================================================== [mknode] Total: 5, Matches: 5, Mismatches: 0 [cpnode] Total: 6, Matches: 6, Mismatches: 0 [rmnode] Total: 2, Matches: 2, Mismatches: 0 ==================================================== [RESULTS] Total: 13, Matches: 13, Mismatches: 0 ==================================================== lab46:~/src/data/dll1$ There were no changes required to the node library between dll0 and dll1, so once you achieved a working implementation, the results should remain the same here. ====list library==== Here is what you should get for list: lab46:~/src/data/dll1$ bin/verify-list.sh ==================================================== = Verifying Doubly-Linked List Functionality = ==================================================== [mklist] Total: 11, Matches: 11, Mismatches: 0 [cplist] Total: 17, Matches: 17, Mismatches: 0 [append] Total: 22, Matches: 22, Mismatches: 0 [insert] Total: 22, Matches: 22, Mismatches: 0 [display] Total: 12, Matches: 12, Mismatches: 0 [find] Total: 28, Matches: 28, Mismatches: 0 [compare] Total: 18, Matches: 18, Mismatches: 0 [empty] Total: 6, Matches: 6, Mismatches: 0 [rmlist] Total: 6, Matches: 6, Mismatches: 0 [obtain] Total: 57, Matches: 57, Mismatches: 0 [swap] Total: 9, Matches: 9, Mismatches: 0 [sort] Total: 42, Matches: 42, Mismatches: 0 ==================================================== [RESULTS] Total: 250, Matches: 250, Mismatches: 0 ==================================================== lab46:~/src/data/dll1$ =====Submission Criteria===== To be successful in this project, the following criteria must be met: * Project must be submit on time, by the posted deadline. * Late submissions will lose 25% credit per day, with the submission window closing on the 4th day following the deadline. * All code must compile cleanly (no warnings or errors) * all requested functions must be implemented in the related library * all requested functionality must conform to stated requirements (either on this project page or in comment banner in source code files themselves). * Executed programs must display in a manner similar to provided output * output formatted, where applicable, must match that of project requirements * Processing must be correct based on input given and output requested * Output must be correct (i.e. the list visualization, where applicable) based on values input * Code must be nicely and consistently indented (you may use the **indent** tool) * Code must be commented * Any "to be implemented" comments **MUST** be removed * these "to be implemented" comments, if still present at evaluation time, will result in points being deducted. * Sufficient comments explaining the point of provided logic **MUST** be present * Track/version the source code in a repository * Submit a copy of your source code to me using the **submit** tool (**make submit** will do this) by the deadline.