Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2320 Data Structures</fs></WRAP>
</WRAP>

~~TOC~~

======Project: DLL0======

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

  * __revision 1__: someone jumped the gun and upgraded to dll0 before being fully up-to-date on sll2; this revision effectively does the same initializing actions as that latest sll2 update does (and if you've already applied it, no problem). I also instituted a prerequisite rule which will cause future upgrades to fail if all current updates are not applied, to mitigate this problem in the future. 
    * Additionally, I implemented some more of the unit tests and verify scripts. At this point, all but obtain and findnode have functioning unit tests/verify scripts in the list library (20141027)
  * __revision 2__: various unit-test fixes (20141028)
    * unit-append and unit-insert had some syntax errors (FIXED)
  * __revision 3__: various unit-test fixes (20141028)
    * logic error in unit-display constructs the list incorrectly (FIXED)
    * I may have done something to unit-sortlist; updating that just because.
  * __revision 4__: unit-obtain and verify-obtain.sh now ready (20141029)
    * verify-list.sh updated to support obtain
  * __revision 5__: unit-findnode and verify-findnode.sh now ready (20141029)
    * verify-list.sh updated to support findnode
    * at this point, all list library unit test/verify scripts are released
    * node library unit tests still to go, be on the lookout for future updates
  * __revision 6__: node library unit tests and verify scripts now ready (20141029)
    * unit-mknode, unit-cpnode, and unit-rmnode
    * verify-mknode.sh, verify-cpnode.sh, verify-rmnode.sh, verify-node.sh
    * at this point, all dll0 project content is released. Future updates should reflect just typos and bug fixes (of which I'm sure there are some).
  * __revision 7__: in a "should have actually tried compiling everything before making it available as a revision" moment, I needed to push through some further bugfixes (20141029)
    * unit-obtain had a typo preventing compilation, now FIXED
    * unit-cpnode had a few typos, also now FIXED
      * there were also 3 logic errors, doing invalid comparisons, which would have likely resulted in persistent failures (a false negative situation). These are FIXED.
    * I hope that NOW the dll0 code base (as provided) will cleanly compile, and is now feature complete (all intended unit tests and verification scripts deployed)
      * Which means now it'll likely just be updates based on discovered logic errors
  * __revision 8__: chasing down some logic errors discovered... (20141030)
    * unit-append and unit-insert had a problem potentially throwing off the first or second test (what I'll call the "space after the NULL" issue). Somewhat implementation dependent, but FIXED.
    * unit-sortlist was calling sortlist() with the incorrect mode under the "Sorting from greatest to least" test, which would have always produced incorrect values. FIXED.
    * unit-cplist, a frequent mention on the revision list for some reason (also a lot more complex than the others due to the nature of its testing), suffered from ntmp2 being set incorrectly right before my big loop checking the copied list against the original list (ntmp2 was erroneously set to **ltmp -> end** instead of **ltmp2 -> end**). So now correct implementations will pass the test. So: FIXED.
  * __revision 9__: in what has been a record number of revisions for a project, I now present revision 9, with further logic error fixes in the unit tests and verify scripts. This is good- the pioneers have helped hammer out the bugs so everyone else benefits from tried-and-true tests (20141031)
    * unit-cplist, perhaps the most troublesome of the unit tests, has hopefully stabilized. Some rather insidious logic errors hiding out in this last round, but that's largely because of its aggressive testing (for your benefit) to ensure proper compliance with your implementation. FIXED.
    * unit-obtain had an errant append() call which would throw off all the results after a certain point. This is now FIXED.
    * all the verify scripts have received some tweaks to improve output flexibility and reduce false negatives, especially on those initial "NULL"-only outputs.
      * verify-list.sh had a bug where it didn't detect successful results correctly. FIXED.
  * __revision 10__: as I make further optimizations to the next project (**dls0**), I took the opportunity to backport some of the aesthetic enhancements I made. (20141103)
    * base Makefile: infrastructure improvements (because I deserve nice things)
    * verify-node.sh: improved display, more accurate totals
    * unit-cpnode.c: improved display (added blank line between some of the tests)
    * verify-list.sh: improved display, more accurate totals

=====Objective=====
In this project, we take our first opportunity to undergo a complete code re-write of linked list functionality, while we implement our first doubly linked list.

=====Project Overview=====

For this project, we're going to be re-implementing MOST of the previous node and list functions. There have been a few changes, namely:

====In inc/node.h====
<code c 1>
#ifndef _NODE_H
#define _NODE_H

#include <stdlib.h>

struct node {
        char         data;
        struct node *prev;
        struct node *next;
};
typedef struct node Node;

Node *mknode(char  );     // allocate new node containing value
Node *rmnode(Node *);     // deallocate node
Node *cpnode(Node *);     // duplicate node

#endif
</code>

There is an addition of a "prev" node pointer, to allow connections to our previous neighbors.

The node value element has been renamed to "data", just to make sure you understand what is going on code-wise.

====In inc/list.h====

<code c 1>
#ifndef _LIST_H
#define _LIST_H

#include "node.h"                       // list relies on node to work

struct list {
    Node *start;                        // pointer to start of list
    Node *end;                          // pointer to end of list
};
typedef struct list List;               // because we deserve nice things

List *mklist(void  );                   // create/allocate new list struct
List *cplist(List *);                   // copy (duplicate) list
List *rmlist(List *);                   // remove all nodes from list

List *insert (List *, Node *, Node *);  // add node before given node
List *append (List *, Node *, Node *);  // add node after given node
List *obtain (List *, Node **       );  // obtain/disconnect node from list

void  display(List *, int);             // display list according to mode

Node *findnode(List *, int);            // locate node containing value
List *sortlist(List *, int);            // sort list (according to mode)

List *swapnode(List *, Node *, Node *); // swap positions of given nodes in list

#endif
</code>

The following changes have taken place:

  * **qty** has been removed from the list; any code you wrote that is based on it will need to be implemented a different way (do NOT recreate the conditions to continue relying on a count, you will lose credit if you do so).
  * **getpos()**/**setpos()** are no longer present. In many ways their functionality is no longer needed with the doubly-linked nature of the list.
  * **searchlist()** has been renamed to **findnode()** (aesthetic change, to keep function names at 8 characters or less).
  * **displayf()/displayb()** are gone, and previous functionality will be merged into one universal **display()** function. 

====list library====
In **src/node/**, you will find skeletons of what was previously there, ready for you to re-implement.

In **src/list/**, you will find the same- 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.

As ALL source files are now skeletons, no sample code has been given. This is intended to be a fresh implementation. While you may reference old code, do not rely on it- try your hand at implementing the functionality from scratch (the more you do this from scratch, the more it will help you).

====List library unit tests====
In **testing/list/unit/**, you will find these new files:

  * **unit-append.c** - unit test for **append()** library function
  * **unit-insert.c** - unit test for **insert()** library function
  * **unit-swapnode.c** - unit test for **swapnode()** library function
  * **unit-sortlist.c** - unit test for **sortlist()** library function
  * **unit-display.c** - unit test for **display()** library function

Additional unit tests will be provided via dll0 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:

<cli>
lab46:~/src/data/dll0$ 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/dll0$ 
</cli>

====list library====
Here is what you should get for list:

<cli>
lab46:~/src/data/dll0$ bin/verify-list.sh 
====================================================
=    Verifying Doubly-Linked List Functionality    =
====================================================
  [mklist] Total:   5, Matches:   5, Mismatches:   0
  [cplist] Total:  30, Matches:  30, Mismatches:   0
  [rmlist] Total:   3, Matches:   3, Mismatches:   0
  [append] Total:  11, Matches:  11, Mismatches:   0
  [insert] Total:  11, Matches:  11, Mismatches:   0
  [obtain] Total:  12, Matches:  12, Mismatches:   0
 [display] Total:   6, Matches:   6, Mismatches:   0
[findnode] Total:  11, Matches:  11, Mismatches:   0
[sortlist] Total:   6, Matches:   6, Mismatches:   0
[swapnode] Total:   7, Matches:   7, Mismatches:   0
====================================================
 [RESULTS] Total: 102, Matches: 102, Mismatches:   0
====================================================
lab46:~/src/data/dll0$ 
</cli>
=====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.
Lab46 Wiki

User Tools

Site Tools

Page Tools
