CSAPP part 0: linked list operation
This article series is mainly about what I have learned in the CSAPP at Carnegie Mellon University, focusing on the lab. Please feel free to leave comments on the article, providing your own insight and solutions to the lab.
Before attending to CSAPP course, all students need to complete lab 0, which is related to the operation of the linked list, in order to make sure that the student has the expected background in C Language Programming.
It is expected to complete the lab within 2 hours, I completed this lab in about 1 hour.
Overview
This lab mainly focuses on how to implement a linked list as a queue, which might cover the following concepts when we are going to do the lab:
- Memory management in C.
- Allocating and manipulating pointer-based data structures.
- String operation in C.
- Recognize the performance of key operations in data structures.
- Produce robust code that operates correctly with invalid arguments.
The lab provides a rough sample code for the students, the students only focus on several key functions of the queue. The file queue.h contains the following declarations of structures and functions:
In this lab, we need to focus on pointer manipulation, preventing from accessing unavailable memory addresses, handling unexpected arguments, and releasing the memory space properly. And now let’s break the lab into several parts and start from the simple one to the hard one.
queue_size
The queue_size function with some advice comment is as follow:
We are required to implement the function with O(1) operation time. It is very intuitive that we just read another variable that keeps the current size of the queue, which results in O(1) operation time for this function.
Hence, we could just add another field in the linked list data structure to keep the size of the queue. So for this function, we will result in the following code modification:
There are two friendly reminders:
- We should also update the size in other operation functions such as inserting an element to the queue.
- Don’t forget to handle the situation if the queue was a NULL pointer.
Before starting to complete the next function, you might notice that the queue is able to insert from either the head or the tail. On top of that, the operation to insert an element from the tail needs to be O(1).
All the operations trying to be O(1) operate-time would need another field to act as a reference for fast performance in this lab. As previous queue_size function, we might need another field to store the current tail element in the queue so that we can directly access the tail element without iteration.
Hence, we would like to modify the declaration of the queue like this:
queue_new
This function is primarily for initializing a new queue. Just remember to return NULL when the program failed to allocate the queue.
queue_free
As for queue_free function, we will need to also release the memory space of the queue element. Hence, there should be an iteration to visit the queue elements and free them.
You might also notice that before the free to the whole queue element, I re-assign the value of the next pointer to NULL. It is because the pointer pointing to the memory space that has been freed is called a dangling pointer, which might cause the program to show undesirable results due to the unintended access.
For example, if we store the pointer somewhere and then the corresponding string is destroyed, the pointer becomes invalid. If we use const char *name just in the scope of new_foo (for example, for printing purposes) then the pointer will remain valid.
queue_insert_head
There is one worth-noting point for C novices when they are going to implement this function:
We would allocate the memory space twice, one is for a queue element, another is for the string stored in a queue element. Be aware of fail allocation. If we failed to allocate memory space for the string in the queue element, we will still need to free the queue element previously allocated before return. Otherwise, it would cause a memory leak.
queue_insert_tail
Again, we will need to allocate the memory space twice, free the remaining memory space before return if fail allocation happened.
queue_remove_head
In this function, we will need to not only free the memory space but also copy the value of the string inside the queue element. Utilize strncpy to copy the string value into the buf pointer if the buf pointer is non-NULL.
queue_reverse
For this function, there are several ways to implement:
- Use two loops to visit the queue, the first one is to keep all elements into a pointer array in order, the second one is to visit the pointer array reversely and re-assign the current pointer pointing to the memory space of the next pointer’s.
- Use three pointers to keep current, next, and previous elements and visit the queue from head to tail, freeing the memory space one by one.
- Recursively reverse the rest list and put the first element at the end.
Three methods work well, however, the first one can not deal with the situation that the size of the queue is huge.
Here is the reason. A typical memory representation of a C program consists of the following sections:
A program has a limited memory space, and it is divided into several sections. As shown in the picture, the stack area traditionally adjoined the heap area and grew in the opposite direction; once we declare a variable or dynamically allocate memory space, the variable or the allocated memory space actually exists in the stack, and the stack grows.
When the stack pointer met the heap pointer, free memory was exhausted and would cause a segmentation fault. That’s why the first one might not work with a large queue since we would go to allocate a large number of the pointers in an array, which causes the stack to grow and meet the heap pointer.
In this lab, for simplicity, we can go for the second solution:
If you are interested in the course material, you can find out more here:
Thank you for your time and patience to read the article.
