1 Step 1: initialise the list (20 marks) In this section, you will define the structures that represent the nodes of the list and the list as a unit. You will also write four auxiliary functions: allocator, which allocates a single node with malloc and updates an integer counter, deAllocator, which frees a single node with free and updates the same counter, initialiseList, which calls allocator to allocate the list head and tail and initialise them, and freeList, which calls deAllocator to free the head and the tail of the list and set all pointers to NULL. Start by defining a node as struct node \{ int i; struct node next; struct node *prev; \} ; where i is the integer stored in the node, next is a pointer to the next node, i.e. the right neighbour of the node, and prev is a pointer to the previous node, i.e. the left neighbour of the node. The second structure you need is a list handle, containing all information you need to access the list, e.g. struct list \{ struct node head; 3 struct node *tail; struct node *right; struct node left; int length; \}; where head is a pointer to the list head, i.e. the leftmost node of the list, tail is a pointer to the list tail, i.e. the rightmost node in the list, left is a pointer to the node storing the last-added odd integer, right is a pointer to the node storing the last-added even integer, and length is the number of nodes in the free space. The program in Listing 1 declares a list called myList, allocates the head and tail of the list and connects them, makes myList. left and myList. right point to the head and tail of the list, initialises myList. length to 0 , prints the list and the value of the allocation counter, frees the nodes, set all list pointers to NULL and length to 1, and prints the counter again. int main() \{ int counter = 0; struct list myList; myList, head = malloc (sizeof (struct node)); counter++; myList.tail = malloc (sizeof(struct node)); counter++; myList, head next = myList.tail; myList, tail prev = myList. head; myList head prev = NULL; myList , tail next = NULL; 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 The auxiliary function printlist is defined in Appendix A. After adding all required definitions, compile the code and run it. The output should be The program in Listing 1 is not very readable. Rewrite it as int main() \{ int counter =0; 4 Listing 2: Compact initialisation by defining the following auxiliary functions: void *allocator(int size, int *counter); void deallocator (void *p, int *counter); void initialiselist (struct list *pList, int counter); void freelist(struct list *pList, int *counter); Define the functions so that the programs in Listing 1 and Listing 2 have the same output. In particular, - allocator should - allocate size bytes of memory by calling malloc, - check if malloc returned a valid pointer, i.e. a non-null pointer, and, if so, increase the value of the counter by one, and - return the pointer returned by malloc. - deAllocator should - check that the first argument is a valid, i.e. non-null, pointer and, if so, free the memory pointed by the first argument and decrease the counter by one and - return nothing. - initialiselist should - call allocator to allocate the head and the tail of the list, - initialise the members of the list as in Listing 1, and - return nothing. - freeList should - check that plist->left points to the same node as plist->head, pList->right points to the same node as pList->tail, and pList->length is zero, i.e. that the list does not contain any occupied or free nodes, - if the list is empty, call deAllocator twice to deallocate the head and the tail of the list, and - if the deallocation is successful, set all pointers to NULL and length to 1. Create a C file, step1. c, containing all required headers and definitions and the code in Listing 2. Compile the code and check that it behaves exactly as the program in Listing 1. 2 Step 2: allocate free nodes (20 marks) In this section, you will make the program allocate extra free space in blocks of size BLOCKSIZE. To make the block size visible to all functions, define a macro called BLOCKSIZE just after the headers. The main task of this step is to define a free-block allocator, declared as void allocateBlock(struct list *pList, int *counter, int nNodes); where pList is a pointer to the list handle, counter is a pointer to the memory allocation counter defined in main, and nNodes is the number of nodes to be added to the free space. To allocate new nodes, you will call allocateBlock with BLOCKSIZE as the third argument. - allocate a new object of type struct node by calling allocator, - link the new node to the existing ones so that the doubly-linked structure of the list is preserved, - set i of the new node to 1, and - increase pList->length by one. To get an intuition of what the function is supposed to do, draw a simple cartoon of the node-insertion process. Copy the content of step1.c into a new file, step2.c, add the definition of BLOCKSIZE on the top, replace main with Listing 3 : Free node allocation and include your implementation of allocateBlock and the definition of deAllocateBlock given in Appendix A. Compile the code and check that the output is the same as in the following example. Example. If you set BLDCKSIZE to 2, the output should be 3 Step 3: push and pull integers to the list (40 marks) In this section, you will write three functions, pushInt, to store a digit in the list, pullint, to remove a digit from the list, and clearList, which calls pullint until the list is completely free, deallocate the free nodes, and call freelist to free the head and the tail of the list. pushint will check that the list has a nonempty free space, i.e. if length is not zero, and, if so, store a new digit in it. If the free space is empty, pushInt will call allocateBlock to increase its size and then perform the required push operation. pullint will emove a digit from one side of the list and then check if the size of the free space is larger than BLockSIZE. that case, pullint should call deAllocateBlock to deallocate BLOCKSIZE free nodes. - Declare pushInt as void pushint (struct list *pList, int *counter, int i); where plist and counter are interpreted as in the previous section and is an integer from 0 to 9. pushint should - call allocateBlock, with BLOCKSIZE as a third argument, if there are no free nodes in the gap, - check if i is odd or even, - if i is odd, store it on the first available node on the right of the head-side stack, i.e. on the node on the right of the node pointed by pList->left, and, - if i is even, store it on the first available node on the left of the tail-side stack, i.e. on the node on the left of the node pointed by plist->right. - Declare pullint as void pullint (struct list *pList, int *counter, int i); 1 where pList, counter, and i are interpreted as in pushInt. In this case, i is used to decide on what side of the list you perform the pull operation, i.e. to decide whether you remove the (odd) digit in the node pointed by plist->left or the (even) digit in the node pointed by plist->right. pullint should - check if i is odd or even, - if i is odd, check that plist->left = pList->head, i.e. there is at least one odd integer in the list, and, if so, * replace the digit in the node pointed by plist->left with 1, 8 move pList->left to pList->left->prev, and * increase plist->length by one, - if i is even, check that pList->right = pList->tail, i.e. there is at least one even integer in the list, and, if so, \& replace the digit in the node pointed by pList->right with 1, \& move plist->right to plist->right->next, and * increase plist->length by one, - check if pList->length > BLDCKSIZE and, if so, call deAllocateBlock to remove BLOCKSIZE free nodes from the free space. - Declare clearlist as void clearList (struct list *pList, int *counter) 1 where pList and counter are interpreted as in pushint and pullint. clearlist should - remove all digits in the head-side stack by calling pullint with i=1 until pList->left points to the head of the list, - remove all digits in the tail-side stack by calling pullint with i=0 until pList->right points to the tail of the list, - remove all free nodes by calling deAllocateBlock with pList->length as the third argument, and - free the list by calling freeList. step2. c into a new file, step3.c, and replace main with Listing 4: Pushing and pulling Compile the code and check that the output is the same as in the following example. Examaple. If you set BLockSIZE to 2, the output should be 8 4 Step 4: interact with the user (20 marks) To make your program interactive, you need a function, getInput, for parsing the user input. The program should ask the user to enter two (possibly noisy) lines of integers and parse them by calling getInput twice. The first line will contain the integers that the program will push to the list. The second line will contain the integers that decide from which side of the list the program will pull the integers. To avoid overflow, getInput will only accept maxInput digits, where max Input =5 BLOCKSIZE. For example, if BLOCKSIZE =1, and the first line of the user input is On3 plu8 tw0 3qu4l th833 the program will push a 0 to the tail-side stack, a 3 to the head-side stack, an 8 and another 0 to the tail-side stack, and another 3 to the heas-side stack. All characters after the second 3 will be discarded. Define max Input outside main, e.g. just after the headers, so that it can be accessed by all functions. - Declare getInput as int getinput (char 3 ); 1 where s is a string and the return value is the minimum between the number of digits in the input and maxinput. The function should use s to buffer the digits as suggested in Algorithm 1 . - Complete main given in Listing 5 so that your program behaves as in the examples given below. \begin{tabular}{l} \hline Algorithm 1 Pseudocode of int getInput (char s ) \\ Input: char s \\ declare a variable, c, of type char \\ declare a variable, i, of type int \\ set c to the null-character \\ set i to 0 \\ while c is not a new line character and i is smaller than maxinput do \\ read a new character from the terminal and store it in c \\ if c is a digit, i.e. c{0,,9} then \\ copy c to the ith entry of s \\ increase i by one \\ end if \\ end while \\ if i is equal to maxinput then \\ while c is not a new line character do \\ read a new character from the terminal and do nothing \\ end while \\ end if \\ return i \end{tabular} Listing 5: main Save the program in a new file, step4.c, and compile and run it for different choices of BLOCKSIZE. For any choice of BLOCKSIZE and different input strings, use Valgrind to see if the program runs without problems. Note. The return value of getInput is the number of accepted digits contained in the user input. The function should copy the selected digits into s without converting them to integers. The conversion to integers should be performed in main when the digits are used as an input for pushInt and pullint. Example. If you set BLOCKSIZE to 1 and the user enters The same stdin input when you set both BLOCKSIZE to 2 produces 11