Many applications allocate very large numbers of blocks of memory of the same size.

For example, a program that uses a lot of linked lists may aflocate large numbers of list

nodes, such as:

struct listnode $\{$

double data;

struct list$\_$node $*$ next;

b

Where a program allocates and frees large numbers of list nodes using the C malloc$()$

and free$()$ functions, the execution time overheads can be large. One common solution

is to avoid calling the free$()$ function to refease the memory for a list node and to instead

add the list node to a linked list known as the free list. When new list nodes should be

allocated, the program will first check whether there are any nodes on the free list. If

there is a free node, the program will take that node from the free list. Otherwise, the

program will allocate a new list node using the malloc$()$ function as normal.

Write an abstract datatype that represents a memory allocator for list nodes that

implements this memory allocation and freeing strategy. Your allocator should have

the following structure:

struct listnode$\_$allocator $\{$

struct list$\_$node $*$ free$\_$list; $//$ pointer to head of free list

$//$ and any other fields you need

$3$

Your memory allocator should support the following functions:

$//$ create a new node allocator with an $$empty free list

listnode$\_$allocator $*$ allocator$\_$new$($int size$)$;

$//$ allocate a new list node from the free list, or with malloc

$//$ if free list empty

listnode $*$ allocator$\_$alloc$($listnode$\_$allocator $*$ this$)$;

$//$ return a list node to allocator and store in the free list

void allocator$\_$free$($listnode$\_$allocator $*$ this, listnode$*$ item$)$;

$//$ destructor; free all memory.used by the listnode allocator

$//$ and the free list

void allocator$\_$delete$($listnode$\_$allocator $*$ this$)$;

$//$ free groups of nodes that are adjacent in memory

void allocator$\_$free$\_$groups$($listnode$\_$allocator $*$ this$)$;

The allocator$\_$free$\_$groups$()$ function frees groups of listnodes that are adjacent in

memory. Given two pointers, p and g$,$ that point to listnodes, the two listnodes are

adjacent if $($p $+$ NODE$\_$SIZE $==$ q$)||($q $+$ NODESIZE $==$ p$),$ where NODESIZE is a

constant that you can use in your code. Wherever a sequence of two or more adjacent

nodes appears in memory, your routine should free each of these nodes. Note that

the elements of the free list may be in any order, and you need to be able to find

nodes that are adjacent in memory despite the arbitrary ordering.

Please comment on the time complexity of your solution.