Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » spring2015 » data » projects » dll0
haas:spring2015:data:projects:dll0

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
haas:spring2015:data:projects:dll0 [2014/11/06 11:46] – external edit 127.0.0.1haas:spring2015:data:projects:dll0 [2015/04/04 22:59] (current) – [Errata] wedge
Line 11: Line 11:
 This section will document any updates applied to the project since original release: 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.  +  * __revision 1__: looks like I forgot to include the node unit tests, here they are (20150331) 
-    * 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) +    * there was a mild typo in the **inc/node.h** header file (FIXED) 
-  * __revision 2__: various unit-test fixes (20141028) +      * the parameter to mknode() was incorrectly an int, it should be a char 
-    * unit-append and unit-insert had some syntax errors (FIXED) +    * updated unit-mklist to check for proper list return status codes 
-  * __revision 3__: various unit-test fixes (20141028) +    * updated unit-display to check for proper list return status codes 
-    * logic error in unit-display constructs the list incorrectly (FIXED) +  * __revision 2__: updated unit tests to support error condition status (20150402) 
-    * I may have done something to unit-sortlist; updating that just because. +    * unit-display had a typo (FIXED) 
-  * __revision 4__: unit-obtain and verify-obtain.sh now ready (20141029) +    * unit-insert is now ready to go 
-    * verify-list.sh updated to support obtain +    * unit-append should also be good to go 
-  * __revision 5__: unit-findnode and verify-findnode.sh now ready (20141029) +    * quieted compiler warnings for unit-cplist and unit-find (still need to finish) 
-    * verify-list.sh updated to support findnode +  * __revision 3__: updated more unit tests to support error condition status (20150403) 
-    * at this point, all list library unit test/verify scripts are released +    * unit-find is now operational and conformant to error condition status checking 
-    * node library unit tests still to go, be on the lookout for future updates +    * there was a bug with checking for a DLL_SUCCESS result, this resulted in fixes to: 
-  * __revision 6__: node library unit tests and verify scripts now ready (20141029) +      * unit-display 
-    * unit-mknode, unit-cpnode, and unit-rmnode +      * unit-insert 
-    * verify-mknode.sh, verify-cpnode.sh, verify-rmnode.sh, verify-node.sh +      * unit-append 
-    * 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). +    * I've disabled the cplist unit test and verify-list does not try to run it (so you won't be impeded by its current unfinished state) 
-  * __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) +    * new options in base Makefile: 
-    * unit-obtain had a typo preventing compilation, now FIXED +      * "reupdate", which re-applies last revision 
-    * unit-cpnode had a few typos, also now FIXED +      * "reupdate-all", which re-applies all revisions, from 1 to current 
-      * there were also 3 logic errors, doing invalid comparisons, which would have likely resulted in persistent failures (a false negative situation). These are FIXED. +      * various backend infrastructure tweaks (because I deserve nice things) 
-    * 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) +  * __revision 4__: unit-cplist is now fully operational (20150404) 
-      * Which means now it'll likely just be updates based on discovered logic errors +    * also did some house cleaning in list unit Makefile
-  * __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===== =====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. 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.
  
 +=====Procedure to Obtain dll0=====
 +As this is a rewrite, dll0 is not based on any of the code you have written up to this point. As such, the transition process is slightly different:
 +
 +<cli>
 +lab46:~/src/data/sll3$ make get-dll0
 +...
 +</cli>
 +
 +The "get-" functionality is distinct from the "upgrade-" you have been using to transition between the sll* projects. When you upgrade, your existing code is copied over, because the next project builds upon what you did previously.
 +
 +But when you "get" dll0, you are getting an entirely new project skeleton- NONE of your existing code is copied over (the structure has changed enough where copying your own code would have been rather problematic).
 +
 +Once you run "**make get-dll0**" you should have a **dll0** directory that you can access and commence working on just as you have with the other project directories.
 =====Project Overview===== =====Project Overview=====
  
Line 64: Line 62:
  
 struct node { struct node {
-        char         data; +        char         value; 
-        struct node *prev; +        struct node *after; 
-        struct node *next;+        struct node *prior;
 }; };
 typedef struct node Node; typedef struct node Node;
  
 Node *mknode(char  );     // allocate new node containing value Node *mknode(char  );     // allocate new node containing value
-Node *rmnode(Node *);     // deallocate node 
 Node *cpnode(Node *);     // duplicate node Node *cpnode(Node *);     // duplicate node
 +Node *rmnode(Node *);     // deallocate node
  
 #endif #endif
 </code> </code>
  
-There is an addition of a "prev" node pointer, to allow connections to our previous neighbors.+There is an addition of a "prior" 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.+The node info element has been renamed to "value", just to make sure you understand what is going on code-wise.
  
 ====In inc/list.h==== ====In inc/list.h====
Line 88: Line 86:
  
 #include "node.h"                       // list relies on node to work #include "node.h"                       // list relies on node to work
 +
 +#define  DLL_SUCCESS            0
 +#define  DLL_MALLOC_FAIL        1
 +#define  DLL_ALREADY_ALLOC      2
 +#define  DLL_NULL               4
 +#define  DLL_EMPTY              8
 +#define  DLL_DEFAULT_FAIL       64
 +#define  DLL_FAIL               128
  
 struct list { struct list {
-    Node *start;                        // pointer to start of list +    Node              *first;           // pointer to start of list 
-    Node *end;                          // pointer to end of list+    Node              *last;            // pointer to end of list
 }; };
-typedef struct list List;               // because we deserve nice things+typedef struct list    List;            // because we deserve nice things
  
-List *mklist(void  );                   // create/allocate new list struct +int mklist (List **);                   // create/allocate new list struct 
-List *cplist(List *);                   // copy (duplicate) list +int cplist (List *,  List **);          // duplicate list contents 
-List *rmlist(List *);                   // remove all nodes from list+
  
-List *insert (List *, Node *, Node *);  // add node before given node +int insert (List **, Node *, Node *);   // add node before given node 
-List *append (List *, Node *, Node *);  // add node after given node +int 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 +int display(List *,  int);              // display list from start to end 
- +int find   (List *,  int,    Node **);  // locate node containing value
-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 #endif
Line 115: Line 115:
 The following changes have taken place: 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).+  * **qty** has been removed from the list
   * **getpos()**/**setpos()** are no longer present. In many ways their functionality is no longer needed with the doubly-linked nature of the list.   * **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).+  * **searchlist()** has been renamed to **find()** (aesthetic change, to keep function names at 8 characters or less, and now supports resuming (finding additional matches).
   * **displayf()/displayb()** are gone, and previous functionality will be merged into one universal **display()** function.    * **displayf()/displayb()** are gone, and previous functionality will be merged into one universal **display()** function. 
  
 +There is now a set of status/error codes that will be utilized as list function return values, so we can better report particular failures.
 +
 +====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==== ====list library====
 In **src/node/**, you will find skeletons of what was previously there, ready for you to re-implement. In **src/node/**, you will find skeletons of what was previously there, ready for you to re-implement.
Line 127: Line 148:
 Figure out what is going on, the connections, and make sure you understand it. 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).+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==== ====List library unit tests====
 In **testing/list/unit/**, you will find these new files: In **testing/list/unit/**, you will find these new files:
  
 +  * **unit-mklist.c** - unit test for **mklist()** library function
 +  * **unit-cplist.c** - unit test for **cplist()** library function
   * **unit-append.c** - unit test for **append()** library function   * **unit-append.c** - unit test for **append()** library function
   * **unit-insert.c** - unit test for **insert()** library function   * **unit-insert.c** - unit test for **insert()** library function
-  * **unit-swapnode.c** - unit test for **swapnode()** library function +  * **unit-find.c** - unit test for **find()** library function
-  * **unit-sortlist.c** - unit test for **sortlist()** library function+
   * **unit-display.c** - unit test for **display()** library function   * **unit-display.c** - unit test for **display()** library function
  
-Additional unit tests will be provided via dll0 project updates.+Enhancements to these unit tests may 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. There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent list functionality.
Line 184: Line 206:
 =    Verifying Doubly-Linked List Functionality    = =    Verifying Doubly-Linked List Functionality    =
 ==================================================== ====================================================
-  [mklist] Total:   5, Matches:   5, Mismatches:   0 +  [mklist] Total:  11, Matches:  11, Mismatches:   0 
-  [cplist] Total:  30, Matches:  30, Mismatches:   0 +  [cplist] Total:  17, Matches:  17, Mismatches:   0 
-  [rmlist] Total:   3, Matches:   3, Mismatches:   0 +  [append] Total:  22, Matches:  22, Mismatches:   0 
-  [append] Total:  11, Matches:  11, Mismatches:   0 +  [insert] Total:  22, Matches:  22, Mismatches:   0 
-  [insert] Total:  11, Matches:  11, Mismatches:   0 + [display] Total:  12, Matches:  12, Mismatches:   0 
-  [obtain] Total:  12, Matches:  12, Mismatches:   0 +    [find] Total:  28, Matches:  28, 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+ [RESULTS] Total: 112, Matches: 112, Mismatches:   0
 ==================================================== ====================================================
 lab46:~/src/data/dll0$  lab46:~/src/data/dll0$ 
haas/spring2015/data/projects/dll0.1415274401.txt.gz · Last modified: 2015/03/23 15:28 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki