Create a compressed directory, e.g. 202223cs2850cw2. zip, that contains the four C files described in the following sections, step1.c, step2.c, step3.c, and step4.c. Optionally, you can save all auxiliary functions in a (single) separate file, functions.c, that you include in a task-specific program, e.g. step1. c, by writing \#include "functions.c" 1 on top of the file. In this case, step1.c would have the following structure I/... macro definitions \#include "functions.c" int main() \} In this assignment, you will write a program that simulates the organization of the virtual memory in a running process. The virtual address space will be represented by a dynamic doubly linked list. The list will store integers in two stacks, which will grow and shrink during the program execution. In particular, - the first stack, which starts at the head of the list and grow towards the tail, will contain odd digits, i.e. 1,3,5,7, or 9 , - the second stack, which starts at the tail of the list and grows towards the head, will contain even digits, e.g. 0, 2,4,6, or 8 , - between the two stacks, the program will maintain a free space, i.e. a set of free nodes, simulating the free memory between the heap and the stack in a process virtual address space. Here is an illustrative diagram of the list that your program is supposed to build: The list will grow or shrink by adding or removing fixed-size blocks of free nodes. The number of free nodes added to or removed from the list will be fixed by a macro, BLOCKSIZE, defined at the beginning of the program. Newly allocated free nodes will temporarily store a fixed negative value, e.g. 1. When some free space is available, the program will be able to push digits to the list. The program will also include a pull function, to free one node from a selected stack. The user will control the pushing and pulling operations by writing two strings in the terminal. The number of digits accepted from the input will be capped at a fixed value to avoid overflow. The program will keep track of all dynamic memory allocations through leak-aware allocation and deallocation functions, which update a counter defined in main. To write the program, follow the steps described in the next sections. Save a separate C file, e.g. step1 . c, step2.c, step3.c, or step4.c, for each section and make sure that it can be compiled without errors and produces the expected output. After completing a section, test your implementation with Valgrind and the Example. The output of the final program with BLOCKSIZE set to 1 and input On3 plu8 tw0 3 qu 41 th833 and 000 is The same input, with BLOCKSIZE set to 2 , produces 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 1 ; 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; 1 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. Listing 1: Explicit initialisation 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; struct list myList; pritialiselist (\&myList, \&counter); freelist (\&myList, \&counter); printlist (\&myList, \&counter); \} 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 BLDCKSIZE 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. - Let allocateBlock consist of a loop of nNodes iterations where, at each iteration, you - 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 BLDCKSIZE 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 move a digit from one side of the list and then check if the size of the free space is larger than BLDCKSIZE. that case, pullint should call deAllocateBlock to deallocate BLDCKSIZE free nodes. - Declare pushint as void pushint(struct list plist, int *counter, int 1 ); a where pList and counter are interpreted as in the previous section and i 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 *pL1st, int *counter, int 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, * 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 clearilst (struct list *pList, int *counter) a 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 pull Int 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. 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 and setting BLOCKSIZE to 1 gives 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 get Input 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, get Input will only accept maxInput digits, where maxInput =5 BLOCKSIZE. For example, if BLOCKSIZE =1, and the first line of the user input is On3 plu8 tw0 3 qu4l 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 maxinput outside main, e.g- just after the headers, so that it can be accessed by all functions. - Declare getInput as int getinput (char $ ) ; a where s is a string and the return value is the minimum between the number of digits in the input and max Input. 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. int main(){ int counter =0; struct list myList; initialiselist(smyList, \&counter); printist (smylist, \&counter); char sPush []; char sPull []; int lenpush - getinput (); int lenpull - getinput (); int 10; int j=0; while ((1+j)