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

• no updates yet

To continue getting acclimated to this whole 'node' thing, and to further familiarize ourselves with the project directory tree.

If you haven't done so yet, you absolutely, positively, MUST watch this video: http://www.youtube.com/watch?v=5VnDaHBi8dM

On Lab46, change into your node0 directory (I'll use ~/src/data/node0/ in my examples):

lab46:~$ cd src
lab46:~/src$ cd data
lab46:~/src/data$ cd node0
lab46:~/src/data/node0$ 

At this point you should be completed with the node0 project.

If you are done, and a make help shows an upgrade-node1 option being available, we can proceed with bootstrapping the node1 project:

lab46:~/src/data/node0$ make upgrade-node1
make[1]: Entering directory '/home/username/src/data/node0/src'
make[2]: Entering directory '/home/username/src/data/node0/src/node'
rm -f *.swp *.o  core
make[2]: Leaving directory '/home/username/src/data/node0/src/node'
make[1]: Leaving directory '/home/username/src/data/node0/src'
make[1]: Entering directory '/home/username/src/data/node0/testing'
make[2]: Entering directory '/home/username/src/data/node0/testing/node'
make[3]: Entering directory '/home/username/src/data/node0/testing/node/app'
rm -f *.swp *.o ../../../bin/node-app-display node-app-test2 node-app-test core
make[3]: Leaving directory '/home/username/src/data/node0/testing/node/app'
make[2]: Leaving directory '/home/username/src/data/node0/testing/node'
make[1]: Leaving directory '/home/username/src/data/node0/testing'
Archiving the project ...
Compressing the archive ...
Setting Permissions ...
You may now switch to the ../node1 directory
lab46:~/src/data/node0$ 

As you can see from the last line: You may now switch to the ../node1 directory

So let's do it:

lab46:~/src/data/node0$ cd ../node1
lab46:~/src/data/node1$ 

Just as before, you'll see various files and directories located here (one regular file, Makefile, and 5 directories). The directory structure (note, not all these directories may yet be present, although a few more are here than were in the node0 project) for the project is as follows:

• bin: compiled, executable programs will reside here
• inc: project-related header files are here
• lib: compiled, archived object files (aka libraries) will reside here
• src: subdirectory tree containing our Data Structure implementations
  • node: location of our node implementation (NEW in this project)
  • list: location of our linked list implementation (manipulation of nodes)
  • stack: location of our stack implementation (manipulation of lists)
  • queue: location of our queue implementation (a different manipulation of lists)
  • …
• testing: subdirectory tree containing our test apps and unit tests
  • node: node-related testing files will be here
    • app: end-user applications, demonstrating use (NEW files in this project)
    • unit: unit tests, helping to verify correct implementation (NEW in this project)
  • list: list-related testing files
    • app: end-user applications, demonstrating use
    • unit: unit tests, helping to verify correct implementation
  • …

The project is driven by a fleet of optimized Makefiles, which will facilitate the compiling process for us.

Each Makefile plays a unique role (the closer the Makefile is to the source code, the more specialized it becomes).

The base-level Makefile is used to enact whole-project actions, such as initiating a compile, cleaning the project directory tree of compiled and object code, submitting projects, or applying bug-fixes or upgrading to other projects.

Running make help will give you a list of available options:

lab46:~/src/data/node1$ make help

****************[ Data Structures List Implementation ]*****************
** make                     - build everything (libs and testing)     **
** make debug               - build everything with debug symbols     **
**                                                                    **
** make libs                - build all supporting libraries          **
** make libs-debug          - build all libraries with debug symbols  **
** make testing             - build unit tests                        **
** make testing-debug       - build unit tests with debugging symbols **
**                                                                    **
** make save                - create a backup archive                 **
** make submit              - submit assignment (based on dirname)    **
** make update              - check for and apply updates             **
**                                                                    **
** make clean               - clean; remove all objects/compiled code **
** make help                - this information                        **
************************************************************************
lab46:~/src/data/node1$ 

In general, you will likely make the most frequent use of these options:

1. make: just go and try to build everything
2. make debug: build with debugging support
3. make clean: clean out everything so we can do a full compile

Most of what you do will be some combination of those 3 options.

When you are done with the project and are ready to submit it, you simply run make submit:

lab46:~/src/data/node1$ make submit
...

Sometimes, a typo or other issue will be uncovered in the provided code you have. I will endeavor to release updates which will enable you to bring your code up-to-date with my copy.

When a new update is available, you will start seeing the following appear as you go about using make:

lab46:~/src/data/node1$ make
*********************************************************
*** NEW UPDATE AVAILABLE: Type 'make update' to apply ***
*********************************************************
...
lab46:~/src/data/node1$ 

When this occurs, you may want to perform a backup (and/or commit/push any changes to your repository)– certain files may be replaced, and you do not want to lose any modifications you have made:

lab46:~/src/data/node1$ make save
Archiving the project ...
Compressing the archive ...
Setting Permissions ...
lab46:~/src/data/node1$ 

Once you have done that, go ahead and apply the update (note this output is from the node0 project update, so you will not see the exact same output):

lab46:~/src/data/node1$ make update
Update 1 COMMENCING
Update 1 CHANGE SUMMARY: Fixed base and other Makefile typos
    Please reference errata section on project page for more information
Update 1 COMPLETE
Updated from revision 0 to revision 1
lab46:~/src/data/node1$ 

At this point your code is up to date (obviously the above output will reflect whatever the current revision is).

As the semester progresses, additional projects will be made available. When this occurs, you may notice new entries appear on the make help display. For example, as the deadline for the node1 project approaches, you will see the following appear:

...
** make update              - check for and apply updates             **
** make upgrade-sll0        - upgrade to next project (sll0)          **
**                                                                    **
** make clean               - clean; remove all objects/compiled code **
...

By typing make upgrade-sll0, your current work on node1 will be copied into a new sll0 directory (peer to node1), and any new files will be copied in from its project directory in /var/public/data/fall2014/sll0/

As such, it is most advisable to have completed work on node1 before upgrading to the sll0 project, so any work you've done will be immediately available to build upon in the next project (the projects will be comprehensive to one another– sll0 will rely on work completed in node1, sll1 (the project after sll0) will rely on the work done in sll0, etc.).

In src/node/, you will find 3 new files: mk.c, cp.c, and rm.c (along with a Makefile)

Take a look at the code there. These are the files that contain functions which will be compiled and archived into the node library (libnode.a) we will be using in this and future projects.

Figure out what is going on, make sure you understand it.

There are 3 functions in the node library:

• mknode() - creates and initializes a new node, eliminating your need to manually run malloc() for new nodes
• cpnode() - duplicates an existing node
• rmnode() - removes/deallocates (frees the memory allocated to) a node

None of these files denote an entire runnable program. These are merely standalone functions. The various programs under the testing/ directory will use these functions in addition to their application logic to create complete executable programs.

You will also notice there are function prototypes for these node library functions in the node.h header file, located in the inc/ subdirectory, which you'll notice all the related programs you'll be playing with in this project are #includeing.

The prototypes (taken right from inc/node.h are as follows:

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

This is your API for the node library. In order to use the node library three things need to happen:

• you must #include “node.h” (generally already done you in this project)
• you must link against lib/libnode.a (the Makefiles take care of this for you)
• you must call the functions providing the appropriate arguments and handling the return values

In general, this is no different than what you've already done, each and every time you've used printf(), scanf(), atoi(), sqrt(), etc. Only until now, you haven't actually had the code right in front of you. But these functions all work the same way, these conditions have to be met for them to operate and be used.

The compiler does a lot of behind-the-scenes work (linking against the C standard library by default, so all you have to do is include stdio.h and/or stdlib.h).

If you've ever played with the math library, you've had a slightly closer look, as such code wouldn't compile with only an include of math.h, you also needed to add a -lm on the compiler command-line.

Again, same details apply here, only the Makefile system automates the library linking. All we have to do is #include the appropriate files.

In testing/node/unit/, you will find 3 files (along with a Makefile):

• unit-cpnode.c - unit test for cpnode() library function
• unit-mknode.c - unit test for mknode() library function
• unit-rmnode.c - unit test for rmnode() library function

These are complete runnable programs (when compiled, and linked against the node 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!

Once again we find ourselves in testing/node/app/, which still has the programs from the previous project (node0). But you should notice some new files as well:

• node-app-arrtolist.c
• node-app-display2.c
• node-app-test3.c

Take a look at these new additions. Your task for this project will involve implementing requested functionality/completing these programs.

You've made changes to node-app-display2.c, and are ready to see your results. What do we do?

First, let's have a second terminal open and logged into lab46. Put it in the base directory of the node1 project:

lab46:~$ cd src/data/node1
lab46:~/src/data/node1$  

Keep your other terminal in the ~/src/data/node1/testing/node/app/ directory, so you can more effectively make changes.

If you've already ran make to build everything a few times, you may want to clean things out and do a fresh compile (never hurts, and might actually fix some problems):

lab46:~/src/data/node1$ make clean
make[1]: Entering directory '/home/user/src/data/node1/src'
make[2]: Entering directory '/home/user/src/data/node1/src/node'
rm -f *.swp *.o cp.o mk.o rm.o core
make[2]: Leaving directory '/home/user/src/data/node1/src/node'
make[1]: Leaving directory '/home/user/src/data/node1/src'
make[1]: Entering directory '/home/user/src/data/node1/testing'
make[2]: Entering directory '/home/user/src/data/node1/testing/node'
make[3]: Entering directory '/home/user/src/data/node1/testing/node/app'
rm -f *.swp *.o ../../../bin/node-app-arrtolist node-app-display2 node-app-display node-app-test2 node-app-test3 node-app-test core
make[3]: Leaving directory '/home/user/src/data/node1/testing/node/app'
make[3]: Entering directory '/home/user/src/data/node1/testing/node/unit'
rm -f *.swp *.o ../../../bin/unit-cpnode unit-mknode unit-rmnode core
make[3]: Leaving directory '/home/user/src/data/node1/testing/node/unit'
make[2]: Leaving directory '/home/user/src/data/node1/testing/node'
make[1]: Leaving directory '/home/user/src/data/node1/testing'
lab46:~/src/data/node1$ 

Next, compile the whole project

lab46:~/src/data/node1$ make
...

Compiled executables go in the bin directory, so if we change into there and take a look around we see:

lab46:~/src/data/node1$ cd bin
lab46:~/src/data/node1/bin$ ls
node-app-display  node-app-test  node-app-test2
lab46:~/src/data/node1/bin$ 

To run node-app-display2, we'd do the following (specify a relative path to the executable):

lab46:~/src/data/node1/bin$ ./node-app-display2

The program will now run, and do whatever it was programmed to do.

For example, let's say we ran the program and put the values 6, 17, 23, 4, 56, and 2 in the list. Your completed program would look like this when run:

lab46:~/src/data/node1/bin$ ./node-app-display2
Enter a value (-1 to quit): 6
Enter a value (-1 to quit): 17
Enter a value (-1 to quit): 23
Enter a value (-1 to quit): 4
Enter a value (-1 to quit): 56
Enter a value (-1 to quit): 2
Enter a value (-1 to quit): -1
6 -> 17 -> 23 -> 4 -> 56 -> 2 -> NULL
lab46:~/src/data/node1/bin$ 

NOTE: This is just example input. Not only should your program work with this, but lists of any length, containing any arrangement of valid values.

NOTE2: The output of node-app-display2 should be pretty much identical to that of node-app-display, as only the method of arriving at the (same) solution has changed.

This project has you making changes to 3 files, all in the testing/node/app/ directory:

• node-app-arrtolist.c - convert an existing array to a linked list
• node-app-display2.c - rewrite the list-building logic using a do-while loop
• node-app-test3.c - rewrite -test2 using node library functions

In addition to the stated tasks, you are to convert the code in these 3 programs to use node library functions (i.e. once complete, you should no longer be calling malloc() to create new nodes, and you shouldn't be initializing node values to 0 or setting initial next pointers to NULL– let the node library functions do that for you).

A big aspect of the node0 and node1 projects is to get you acclimated to the overall structure of the project organization, and to make use of library functions created to facilitate our on-going explorations.

So, along that path, your task with node-app-test3 is to re-implement the functionality of node-app-test2 (previously provided as a complete running program in the node0 project), and to convert it over to using node library functions.

That means:

• no more explicit malloc() calls, value initializations to 0, initial next pointers to NULL; use mknode() instead
• use of cpnode() where you have instances of duplicated nodes (this DOES happen in node-app-test2.

You are to get a program that produces the same functional output (obviously with different displayed addresses), by using the node library and its functions.

The skeleton is there, you just need to adapt the code.

As a means of testing your understanding, this program sets up a pre-existing array, filled with values, and displays it to STDOUT.

Your task is to add in logic that builds a list, one node at a time, containing the same values (and in the same order) as is found in that array, and to then display the linked list to STDOUT, where we should see identical information.

Sample output of completed code should look like:

lab46:~/src/data/node1/bin$ ./node-app-arrtolist
Array: 3 1 4 1 5 9 2 6 5 3 5 8 9 7
List:  3 1 4 1 5 9 2 6 5 3 5 8 9 7
lab46:~/src/data/node1/bin$ 

As the array is defined with set values, your output, when complete and correct, should always be the same. This tends to be a good exercise in demonstrating you understand conceptually what is going on and can perform the necessary node manipulations to pull it off.

Again, be sure to use node library functions (like mknode()) in this program.

In the node0 project we had to implement the display functionality for the list being built.

Here, we work with that same idea, only we change a few things around structurally in the program- the final output should still be the same, but the code to produce it will be different.

Basically, there are three items for you to address:

• convert your raw malloc() calls and node initializations to mknode() calls. There should be 0 instances of malloc() in your final code.
• switch the main driving loop that builds the list to a do-while (the previous version used a while). But you're aiming for the same end result.
  • your display functionality can remain a while
• move your display code into a dedicated display() function, which takes as a parameter a Node pointer pointing to the preferred beginning of the list you'd like to display.
  • This starts warming us up to future projects, where we'll be using and calling lots of functions

The output should be the same as experienced in node-app-display, the first version of the program, as you had to complete in the node0 project.

To be successful in this project, the following criteria must be met:

• Code must compile cleanly (no warnings or errors)
  • node-app-test3, node-app-arrtolist, and node-app-display2
• Executed programs must display in a manner similar to provided output
• Processing must be correct based on input given and output requested
• Output must be correct (i.e. the list visualization) based on values input
• Code must be nicely and consistently indented (you may use the indent tool)
• Code must be commented
• 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.