Back to Lesson 11

For these exercises, you should grab the starter code. This code is based on our linked list example from Monday’s class. You’ll be adding functionality (and fixing some bugs) in simplelinkedlist.c.

Exercise 1: Compiling the program

You can try to compile the program using this command:

clang -o sll -gdwarf-4 -fPIC simplelinkedlist.c

Unfortunately, you’ve been given buggy code. Drat! Make use of the error message from clang to find and fix the bug.

Exercise 2: Finding a segfault

Now that you’ve compiled the program, you can try to run it! Use this command:

./sll

Bummer. Broken code again. And a segfault no less. >:(

Have no fear, gdb is here! Our compilation command did a bunch of extra stuff (which also occurs for your next assignment), including loading debug symbols. This will be handy to be able to step through our code.

In the terminal, start up gdb prepped to run your code:

gdb sll

Hit return until you get to a prompt that looks like this:

(gdb)

There’s a lot we can do with gdb, but for now let’s just figure out where this segfault is happening. Use r to run your program:

(gdb) r

Once you hit return, it runs the program and stops when it hits the segfault. A whole bunch of stuff prints, but it ends like this:

Program received signal SIGSEGV, Segmentation fault.
0x00005c033f5f21f8 in main () at simplelinkedlist.c:XXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

I’ve replaced some really helpful output from that message with XXXXXX so you have to run it to see. This should tell you where the bug is. Go ahead and remove this line – it shouldn’t have been there anyway.

Also, you can get out of gdb by typing q (or quit).

Exercise 3: Inspecting variables with gdb

We can do a lot more in gdb. Recompile your code, then run gdb and set a breakpoint at the start of main, which tells gdb to pause when it gets to that line of code:

(gdb) b main

You could have typed break if you prefer. gdb has lots of shortcuts that are single-character commands instead of their full-world counterparts.

Now, run your code again with r (or run). You should see that it hit your breakpoint:

Breakpoint 1, main () at simplelinkedlist.c:37
37          head.value = 5;

The line shown is the next one that will execute. You can use n to go to the next line (or s if you want to “step into” a function call).

(gdb) n
38          head.next = NULL;

Notice that gdb is telling you which line of code it’s about to execute, by number. That’s handy, because we can set breakpoints that way, too. Set a breakpoint at the line of the first print statement. For me, that’s line 48. Then, type c (or continue) to continue execution until that breakpoint:

(gdb) (gdb) b simplelinkedlist.c:48
Breakpoint 3 at 0x5a7c61d991cb: file simplelinkedlist.c, line 48.
(gdb) c
Continuing.

Breakpoint 3, main () at simplelinkedlist.c:48
48          printf("first value: %d\n", head.value);

Let’s inspect some values. We can use p (or print) to see the value of expressions in our code. Try these:

• p head
• p head.value
• p head.next
• p head.next->value
• p head.next->next

If you have questions about anything, make sure to ask!

Exercise 4: Fixing memory leaks

The code you have uses malloc but is missing the all-important corresponding calls to free. Let’s use valgrind to see how many things aren’t being freed.

A call to valgrind is in the file run_valgrind. Take a look, then execute it from the terminal:

./run_valgrind

This gives a lot of output, but parsing through it can be useful. Here’s a trimmed copy of mine:

...
==916899== 16 bytes in 1 blocks are definitely lost in loss record 1 of 2
==916899==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==916899==    by 0x1091B0: main (simplelinkedlist.c:41)
==916899== 
...
==916899== 
==916899== LEAK SUMMARY:
==916899==    definitely lost: 32 bytes in 2 blocks
==916899==    indirectly lost: 0 bytes in 0 blocks
==916899==      possibly lost: 0 bytes in 0 blocks
==916899==    still reachable: 0 bytes in 0 blocks
==916899==         suppressed: 0 bytes in 0 blocks
==916899== 
==916899== For lists of detected and suppressed errors, rerun with: -s
==916899== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

This tells me useful things, like how I have 2 valgrind errors, including something based on a value that was allocated on line 41. For me, that’s the first call to malloc in main.

Use the output from valgrind to make sure you free everything that is malloced.

Exercise 5: Additional functionality

Take some time to implement some more functionality, specifically the three functions given as prototypes:

// TODO: Write functions:
void display(linked_list_node_t *lst);
bool contains(linked_list_node_t *lst, int item);
void cleanup(linked_list_node_t *lst); // TODO: change head in main to be on heap before testing this

Writing these here with our simple integer-only linked list will be good practice before writing them in your next assignment with more complicated Scheme-based lists.

Back to Lesson 11

Exercise 6: Getting started with P1

Now switch over to the assignment page for P1. Download the starter code and open up main.c.

Your goal right now is to read through the file and get a sense for what you need to implement. Sketch the Scheme lists, as cons cells, corresponding to the CR (shouldTestAdvanced = false) list and the AD list. Make a note to yourself which functions and/or node types are only used in the AD part.

Back to Lesson 11