n this assignment we$$re going to experiment with dynamic memory as well as explore some

of the properties of different memory approaches.

Phonebook Variants

We are going to create $3$ variants of our phonebook program from assignment $6.$ If you are

unsure of your solution you can use the provided solution as long as you include a comment

citing what functions were used and what changes you needed to make.

All of these variants focus on a specific deficiency that our phonebook has, that is$,$ that it$$s

size is limited and fixed. Dynamic allocation gives us some tools to solve that.

You should read all three variants and consider if there are any changes to the base imple$-$

mentation that will make these modifications easier. $($hint: creating a function to get a free

node is probably going to be very helpful$)$

Once you have a base implementation you should rename it phonebook$-$base.c$,$ and create

a makefile rule phonebook$-$base to build this base version. It is a good idea to also

develop a set of tests which you can use to validate that all further variants work as intended.

Allocation and Expansion $[30$ Points$]$

Copy your phonebook$-$base.c to phonebook$-$mallocblock.c and create a makefile rule

which can build this variant.

In this variant we will change our fixed node array to one that is malloc$()$ed or calloc$()$ed

when the list is initialized. The free list will be populated from this allocation.

When the free list runs out of nodes, it should be expanded by malloc$().$ This can happen

either when the last node is used, or when the next node is created. Document your choice

in the in$-$file comments.

Your malloc$()/$calloc$()$ blocks should be of a size PHONEBOOK SIZE which should be set

to $10.$

Ensure you test your solution$$s ability to expand the list.

On$-$demand Allocation $[30$ Points$]$

Copy your phonebook$-$base.c to phonebook$-$malloc.c and create a makefile rule which can

build this variant.

In this variant we will remove our fixed node array and the free list will be unused. Instead,

each time a node is requested it should be allocated with malloc$()/$calloc$().$

$2$

When a node is removed from the list, it should be free$()$ed$.$ Phonebook clear should free

all used nodes.

Ensure this solution is able to add and remove items from the list. $($hint$,$ use valgrind to

ensure that memory is not corrupted or leaked$)$

BONUS $[20$ Points$]$

Some of you may have noticed that the Allocation and Expansion approach currently leaks

memory. To receive full marks for the bonus develop a method to ensure that all the memory

chunks are freed when the list is cleared.

BONUS BONUS $[20$ Points$]$

Extend this freeing behaviour to freeing chunks when they are no longer used $($i$.$e$.$ all there

memory is on the free list$).$ Consider the performance implications of your approach.

Note, that attempting the bonus without having a solid implementation of the base prob$-$

lem may result in you base solution not working and the loss of marks in that section.

ATTEMPTING the bonus will not be considered a reason for non$-$bonus functionality not

working.

Evaluating the Variants $[40$ Points$]$

Using your profiler from LE$9,$ develop several additional test inputs which you believe will

be interesting for exploring these variants $($including the base$).$ For example, the list in the

Allocation and Expansion variant is growing every $10$ nodes, so measuring over multiple of

$10$ boundaries will likely be interesting.

The number of tests inputs needed is up to you, it should be enough you can develop an

understanding of the impact and tradeoffs of each approach. Your test inputs should work

on all variants $($you may need to make slight fixes to their code to achieve this$).$

Based on your testing write a short report on the approaches, your report should identify

the following for each: The general behaviour of memory, cpu, and duration; usages of this

approach $($i$.$e$.$ scenerios where is performs better, or performs better in some way$)$; usages

to avoid $($i$.$e$.$ scenerios where this approach performs poorly or poor in some way$).$ Your

descriptions should identify the specific data you collected that supports your statements.

Consider if there are modifications to the exact approaches described here that would be

interesting to explore and what you hypothesize they would change in your results.

In your conclusion, propose a method you would use to select between these approaches.

You may format this report in any of $$markdown$,$pdf$,$ or $$plain text$,$ but no other docu$-$

ment types.

$3$

Files to hand in

All source files must be on git. The following files are to be packaged into a tarball a$9.$tar

and submitted to canvas:

$-$ git.log

$-$ Makefile

$-$ phonebook$-$base.c

$-$ phonebook$-$mallocblock.c

$-$ phonebook$-$malloc.c

$-$ analaysis.$[$md $|$ pdf $|$ txt$]$

You can generate the git.log file with the following command:

git log main..a$9>$ git.log

Your tarball should be flat $($contain no subdirectories$),$ and should not contain any files not

listed above. Remember the com