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: NODE1======

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

  * no updates yet

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

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

=====Procedure for bootstrapping=====

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

<cli>
lab46:~$ cd src
lab46:~/src$ cd data
lab46:~/src/data$ cd node0
lab46:~/src/data/node0$ 
</cli>

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:

<cli>
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$ 
</cli>

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

So let's do it:

<cli>
lab46:~/src/data/node0$ cd ../node1
lab46:~/src/data/node1$ 
</cli>

====Overview====
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
    * ...

====Operating====

The project is driven by a fleet of optimized **Makefile**s, 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:

<cli>
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$ 
</cli>

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

  - **make**: just go and try to build everything
  - **make debug**: build with debugging support
  - **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.

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

<cli>
lab46:~/src/data/node1$ make submit
...
</cli>
 
====Bugfixes and Updates====
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:

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

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:

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

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

<cli>
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$ 
</cli>

At this point your code is up to date (obviously the above output will reflect whatever the current revision is).
====upgrades====
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:

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

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

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

====node library====
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 **#include**ing.

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

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

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.
====Node library unit tests====
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!

====Node application programs====
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.
====Building the code====
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:

<cli>
lab46:~$ cd src/data/node1
lab46:~/src/data/node1$  
</cli>

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

===cleaning things out===
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):

<cli>
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$ 
</cli>

===compile project===
Next, compile the whole project

<cli>
lab46:~/src/data/node1$ make
...
</cli>
====Our binaries====
Compiled executables go in the **bin** directory, so if we change into there and take a look around we see:

<cli>
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$ 
</cli>

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

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

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

====Sample Output====
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:

<cli>
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$ 
</cli>

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

======Your task======
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).

=====node-app-test3=====
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.

=====node-app-arrtolist=====
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:

<cli>
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$ 
</cli>

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.

=====node-app-display2=====
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.

=====Submission Criteria=====
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.
Lab46 Wiki

User Tools

Site Tools

Page Tools
