Project: DLL1

This section will document any updates applied to the project since original release:

• revision 1: Implemented a few refinements to unit-obtain (20150415)

In this project, we continue our doubly linked list re-write, completing the remaining library functions.

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
...

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.

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.

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).

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!

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):

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.

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$ 

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.