Implementation of a Doubly Linked List with Dynamic Memory Allocation in C

The list will grow or shrink by adding, when needed, given amounts of free nodes to the free gap between the stacks. The number of free nodes added to the list will be the same at each time and fixed by a macro, BLOCKSIZE, defined at the beginning of the program. As all integers stored in the list will be nonnegative, free nodes will be marked with the fixed negative value 1. To keep track of all dynamic memory allocations, you will use a leak-aware allocator and deallocator that update a shared counter defined in main. You will write your program in four main steps, described in the following sections. For each section, save a standalone code that can be compiled without errors and produces the expected output. We suggest you call your solutions step1.c, step2.c, step3.c, step4.c and test the functions that you implement in each section through this Moodle Checker. As we also evaluate the structure and style of your programs, passing all tests will not guarantee you to get full marks.

 

Work and save your solutions on the teaching server linux.cim.rhul.ac.uk to avoid unpleasant surprises, instabilities, and to be sure you can reproduce the examples given in this document without possible machine dependent issues. Always compile your code with gcc Wall Werror Wall and check that the program executes without issues by running the executable, a.out, with the following command valgrind ./a.out and reading carefully what is printed on the screen. Sketch of the implementation.

 

Step 1 (20 marks). In the beginning, the list will consist of only two nodes, the head and the tail, connected to each other. Your first task is to allocate these two nodes and initialise the doubly linked list.

 

Step 2 (20 marks). Before you start storing integers into the list, you will need to allocate a certain amount of free nodes and place them between the head and the tail. All allocated nodes, i.e. the head, the free nodes, and the tail, should always form a doubly-linked list.

Step 3 (40 marks). To store a given integer into the list, you will write a push function that adds the integer to the head-side stack, i.e. on the left of the free space, or the tail-side stack, i.e. on the right of the free space, depending on whether the integer is odd or even. New integers will be stored into the first available free node, i.e. odd integers into the leftmost node of the free gap and even integers into the rightmost node of the free gap. To remove an integer from the list, you will write a pull function that replaces a stored integer with 1, i.e. that makes the corresponding node free to store a new value.

 

The choice between removing an integer from the left or the right will be fixed by a parameter passed to the pull function. To simplify the setup, you will always remove the last added integer of a stack, i.e. the last integer on the right of the head-side stack or the last integer on the left of the tail-side stack. The number of free nodes in the gap between the two stacks will then increase or decrease, according to the number of times you call the push and pull functions. You will need to keep track of the amount of available space, i.e. the number of free nodes in the gap, and remove, i.e. deallocate, BLOCKSIZE free nodes if the size of the gap is larger than BLOCKSIZE add, i.e. allocate, BLOCKSIZE free nodes if the size of the free gap is 0.

 

The allocation or deallocation process will simulate the request for more memory that a program can send to the operating system during the execution. Possible calls to the block allocation and deallocation should
be included in the push and pull functions.

 

Step 4 (20 marks). In the end, you will make the program interactive so that the user can decide the number of integers to push to the list and the number of integers to pull from it. In practice, the user will enter a line of (noisy) signed integers into the terminal, e.g.

one plus2 +two3 4 +five5 1 zero and the program will perform the corresponding series of pulling and pushing operations, e.g.
1. add three integers
2. attempt to remove four integers
3. add five integers
4. attempt to remove 1.
After processing the user input, the program should clear the list, i.e. remove all integers, and deallocate all
the allocated dynamic memory. The execution of the user instruction above will produce an output similar
topushing 3 integers

| 0 | | 1 | | 2 | | 0 | | 0 |
pulling 4 integers
| 0 | | 0 |
pushing 5 integers
| 0 | | 1 | | 3 | | 1 | | 4 | | 2 | | 0 | | 0 |
pulling 1 integers
| 0 | | 1 | | 3 | | 1 | | 1 | | 2 | | 0 | | 0 |