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

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:spring2015:data:projects:dll0 [2015/03/23 15:29] – [In inc/node.h] wedgehaas: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 #__: <description> (DATESTRING)+  * __revision 1__: looks like I forgot to include the node unit tests, here they are (20150331) 
 +    * there was a mild typo in the **inc/node.h** header file (FIXED) 
 +      * the parameter to mknode() was incorrectly an int, it should be a char 
 +    * updated unit-mklist to check for proper list return status codes 
 +    * updated unit-display to check for proper list return status codes 
 +  * __revision 2__: updated unit tests to support error condition status (20150402) 
 +    * unit-display had a typo (FIXED) 
 +    * unit-insert is now ready to go 
 +    * unit-append should also be good to go 
 +    * quieted compiler warnings for unit-cplist and unit-find (still need to finish) 
 +  * __revision 3__: updated more unit tests to support error condition status (20150403) 
 +    * unit-find is now operational and conformant to error condition status checking 
 +    * there was a bug with checking for a DLL_SUCCESS result, this resulted in fixes to: 
 +      * unit-display 
 +      * unit-insert 
 +      * unit-append 
 +    * 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) 
 +    * new options in base Makefile: 
 +      * "reupdate", which re-applies last revision 
 +      * "reupdate-all", which re-applies all revisions, from 1 to current 
 +      * various backend infrastructure tweaks (because I deserve nice things) 
 +  * __revision 4__: unit-cplist is now fully operational (20150404) 
 +    * also did some house cleaning in list unit Makefile
 =====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 33: Line 68:
 typedef struct node Node; typedef struct node Node;
  
-Node *mknode(int   );     // allocate new node containing value+Node *mknode(char  );     // allocate new node containing value
 Node *cpnode(Node *);     // duplicate node Node *cpnode(Node *);     // duplicate node
 Node *rmnode(Node *);     // deallocate node Node *rmnode(Node *);     // deallocate node
Line 51: 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 78: 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 90: 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 147: 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.1427124580.txt.gz · Last modified: 2015/03/23 15:29 by wedge

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