PROJECT: Singly-Linked List of Nodes (SLL0)

As we are slowly building onto our code library, this week we will be moving forward to list manipulating functions, lists containing nodes; at this point, we should now have fully functional node processing functions as the foundation.

If you remember from our pseudocode from sln0, one of the processes we implemented to include new nodes into a list was to insert them. That is what we will be focusing on…

First and foremost, after upgrading your project folder, as explained further down below, you will find a new header file inside the inc directory called 'list.h'. This header declares a new type of struct called List, with two pointer properties lead and last, and five new functions:

• mklist()
• setpos()
• getpos()
• insert()
• displays()

It is recommended to work on them in that order. If you choose to work on them in that order, know that the unit tests call on display so you will need to comment out the display call inside the unit tests of setpos, getpos, and insert. However, mklist works fine and should be the first one completed.

You will now have a new directory as well called 'list', /sll0/src/list/.
Here you will find four new .c files containing their corresponding functions:

• mk.c
• pos.c
• insert.c
• displayf.c

Our goal is to implement five functions in four files. The files are located in the /src/list directories along with a makefile. The functions are themed on the use of lists.

To get the project files:

cd /sln1
make upgrade-sll0
cd ../sll0/

* this will upgrade sln1 → sll0

NOTICE: To easily compile your files, from the base directory you can run make clean followed by make default afterwards you can run make check or inside the bin folder run the desired unit test if you want more specific information of what went wrong.

Another thing to note is that the sll0 project files can only compile with version 9 of gcc. If you are not on lab46 and the project fails to build the library or unit tests, this may be because you are using a newer or older version of gcc.

You can use an older version of gcc off of lab46 by using the following commands (assuming you are using a Raspberry Pi with it's default OS) in this link: https://gist.github.com/sol-prog/95e4e7e3674ac819179acf33172de8a9

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash

There are four programs that you will need to complete. The first consists of creating the initial list (mklist). The pos.c program has two functions you will need to complete. The first being getpos() and the second setpos() as seen below. Finally, we need to have a displayf(). Information on these functions can be found below.

mklist() should make a new list containing a lead and last node. These nodes point to the start and end of the list. Is very similar to mknode().For Errors: On error, return NULL. getpos() should get the position of the node passed into the function. It should look at the node passed in → info and find that node inside the list. If that node isn't found inside the list it should return the appropriate error specified inside pos.c. Start a temp node at the beginning of the list and go through each node until the given node is reached, using some form of a counter to obtain that positions value. For Errors: If Null/Undefined list or node is given, return a negative one(-1). If out-out-bounds condition, return a negative two.(-2) setpos() should set a new Node* to a position specified by a number passed into the function, think of setting a tmp variable and looping to get to that position as done in sln0. For Errors: If Null/Undefined list or node is given, return a negative one(-1). If out-out-bounds condition, return a negative two.(-2) insert() should put a new node containing a value passed into the function before the specified place. This place will be passed into the function as will the new node. For optimization of your program these should utilize the setpos() and getpos() functions to set new nodes to maintain the list. The list should be able to insert before the start and anywhere else. Remember that if the node is one after the start, you will have to set the lead's right to the new node.

displayf() should display the list in a forward orientation (start→end node). There are two modes for display. The first is to display the list without the position of each value i.e 4 → 13 → -1 → NULL.

The second mode is to display the index along with the values of the list. i.e 4[0] → 10[1] → …. → NULL

One tool that can be utilised for debugging is the gdb and make debug commands. Use the command make with the argument debug (typed as “make debug”), then run the gdb command with the executable you are debugging (“gdb ./executable”), then from the use “run {any arguments}” and it will show where your error has occured. Furthermore, with regards to debugging a specific unit test, you can make use of the tests in sll0/unit/list/(unit test to debug). Here you will be able to compare your results with the expected results. (Unit tests are very useful!)

An “errors” file is also made after running make default. Checking through this may be helpful in figuring out what's going wrong if things aren't working.
After running “make” your c code will be compiled, if errors are present the errors file as mentioned will prompt with a message after the compile looking like “* There were warnings or errors during compile! Type: 'cat errors' at the prompt to view.”. If you see this message, you can cat the file errors that is only available in the base sll0 directory, this file will display every error present while compiling all of the c files. You need to be careful because it shows every compile error so if many errors are present, it might be multiple files not just one, meaning there is most likely less errors than you think for the given file you are working on.
=====OUTPUT SPECIFICATIONS===== The only program that will be displaying output is the display function, with it possessing a standard mode and an indexed mode. The standard will simply show the values one after another, such as “0 → 3 → 7 → 9 → 19 → NULL”. The indexed mode will show the list address (starting at 0) along with the index location, such that “[0] 0 → [1] 3 → [2] 7 →[3] 9 → NULL”. Note that the NULL is not accompanied by a list address. =====UNIT TESTS===== When running make check there will be 43 total match checks, when the functions are setup correctly, all 43 should match the output of the unit tests. You may receive an error that looks something like this: <cli> YOURNAME@lab46:~/YOURDIR/sll0$ make check ====================================================== = Verifying Singly-Linked List Functionality = ====================================================== [mklist] Total: 5, Matches: 5, Mismatches: 0 [insert] Total: 11, Matches: 11, Mismatches: 0 [displayf] Total: 10, Matches: 10, Mismatches: 0 [getpos] Total: 8, Matches: 8, Mismatches: 0 [setpos] * NOT CURRENTLY OPERATIONAL * ====================================================== [RESULTS] Total: 34, Matches: 34, Mismatches: 9 ====================================================== </cli> This does not mean the verify script is broken, you likely have a segmentation fault.
To analyze further, navigate to sll0/unit/list and run the unit test for the function giving you problems. In this example: <cli> YOURNAME@lab46:~/YOURDIR$ cd unit/list/ YOURNAME@lab46:~/YOURDIR/unit/list$ ./unit-setpos UNIT TEST: list library setpos() function ========================================= Test 0: Running setpos() on NULL list … Segmentation fault (core dumped) </cli> Indeed, a segmentation fault. You'll also receive this error if you haven't yet implemented displayf**.