1 Step 1: initialise the list (20 marks) In this section, you will define the structures that you need to handle the nodes of the list and the list as a unit and write three functions to allocate, initialise, and deallocate the list starting nodes, i.e. the list head and tail. In particular, allocator will allocate a single node with malloc and update an integer counter 3 deAllocator will free a single node with free and update the same counter initialiseList will allocate two nodes, the list head and tail, by calling allocator and initialise them. 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 a pointer to the next node, i.e. the right neighbour of the node, and prev a pointer to the previous node, i.e. the left neighbour of the node. To make your program more readable, and let functions modify the list directly, define the following list handle struct list { struct node *head; struct node *tail; struct node *right; struct node *left; int length; }; where head is a pointer to the head of the list, i.e. the left most node of the list, tail is a pointer to the tail of the list, i.e. the rightmost node in the list, right is a pointer to the node storing the last-added even integer, and left is a pointer to the node storing the last-added odd integer. The following program allocates the list head and tail, connects them to each other, sets the structure members left and right to point to the head and tail of the list, initialises the size of the free-gap to 0, prints the list and the value of the allocation counter, frees the two nodes, and prints the counter again. 1 3 4 5 6 7 H 9 10 11 12 13 14 int main() { int counter = 0; struct list myList; printf ("allocating two nodes myList.head - malloc(sizeof(struct node)); counter++; myList.tail - malloc(sizeof (struct node)); counter++; printf("initialising the list ... "); myList.left - myliot.head, myList.right = myList.tail; mylist.tail->i = 0; myList.head->i = 0; myList.head->next = myList.tail; myList.head->prev - NULL; myList.tail->prev - myList.head; myList.tail->next = NULL; printf(" | $d || $d I ", myList.head->i, myList.tail->i); printf("counter = %d ", counter); printf ("freeing the list free (myList.head); counter free (myList.tail); counter-- printf("counter- %d ", counter); } Code 1: Explicit initialisation 15 16 17 18 19 20 21 22 24 25 4 To compile the program, you will need to add all required headers, macros, structure definitions, and function declarations before main and all required function definitions after it. Your task consists of writing three functions declared as void allocator (int size, int counter); void deAllocator (void *p, int counter); void initialiselist (struct list *plist, int counter); where the return value of allocator is the pointer returned by malloc, size is the number of bytes that you want to allocate using malloc, counter is a pointer to the counter that keeps track of the number of dynamic memory allocations, p is a pointer to the memory block that you want to free using free, and pList is the pointer to the list-handle defined above. The functions should be implemented so that the following program becomes equivalent to Code 1, e.g. the output of the two programs should match for any initialisation of the counter. 1 2 3 1 5 5 9 10 11 12 13 int main() { int counter = 0; struct list myList; printf("allocating two nodes printf("initialising the list "); initialiseList (amyList, &counter); printf(" | 30 || 1d I ", myList.head->1, mylist.tail->); printf("counter - 8d ", counter); printf("freeing the list "); deAllocator (myList.head, &counter); deallocator (my 1st tail, counter); printf("counter - %d ", counter); } Code 2: Compact initialisation In particular. allocator should -- allocate a block of memory of size bytes by calling malloc - check if malloc returned a valid, i.e. non-null, pointer and, if so, increase the value of the counter by one - return the pointer returned by malloc (see Lines 5-6 of Code 1) . de Allocator should check that the first argument is a valid, i.e. non-null, pointer and, if so, free the memory block pointed by the first argument and decrease the counter by one return nothing (see Lines 21-22 of Code 1) initialiselist should -- call allocator twice, once to allocate the head and once to allocate the tail of the list - initialise the member of the structure as in Lines 10-17 of Code 1 - return nothing. Create a C file, stepi.c, containing all required headers, macros, and function declarations, main given in Code 2, and your implementation of all functions. Check that the file can be compiled and run without errors and compare its output with the output of Code 1. 5 Example A run of step1.c should produce the following output allocating two nodes initialising the list 1 0 1 0 1 counter - 2 freeing the list ... counter = 0