Appendix: growable arrays

"Growing" arrays with realloc()

The realloc() function gives a handy way to grow or shrink an array:

Trying it in practice

Let's use realloc() to create a growable array of floats.

The most obvious things we need are a pointer to point to the start of the dynamically-allocated memory and and integer variable to keep track of how many values we have. Our first attempt to create a growable array of floats may look a bit like this:

NB: note the initialisation of values and nvals.

This works well enough: every time the user enters a new number the program calls realloc() to allocate the new array, copy the old one to it, frees the old one and set values to the address of the new aray. At all times nvals is both the number of values stored in the array and the number of values the allocated memory is capable of storing as they are always one and the same.

However, this is very inefficient:

• realloc() is slow anyway.
• Every time we add an element to the array we have to copy the old array to the new one.

Speeding it up

The first fix is increase the size of the underlying array by a few at a time. We can then keep track of the number of allocated but unused elements only call realloc() when the array is full. Of course we now have two numbers as the number of elements in the "real" array is now less than or equal to the size of the allocated chunk of memory storing it. This means we have another number to keep track of.

The following code allocates floats 64 at a time, and only calls realloc() when the array is full.

A more subtle problem

When you change you phone how much easier is it for you to be able to keep the same number? What would you have to do if every time you changed your phone you had a new number?

Thus our growable array of floats requires three variables to describe it: a pointer to the memory, the number of elements the memory can store and the number we have actually used. We could probably get away with this if we only wanted to use the array inside a single function but of course we won't. How will we pass this information between functions?

The following structure combines the three values into a structure:

This enables us to allocate as many extendable arrays as we like and to pass pointers to them between dfferent functions.

The following code illustrates this and in the process defines two functions, one for creating a new array and one for extending an existing array (but see note below):

The above code illustrates a slightly surprising fact about realloc(): although it may reyurn a different address than it was given it doesn't have to. Situations where realloc() may decide to retyurn the same address include:

• The array is shrinking not growing.
• There is unallocated space immediately folloing on from the array so the allocation can just be grown.

In our case, there are no allocations between succesive calls to realloc() and realloc() is able to just grow the array without moving it.

More realistic behaviour

We can simulate the more realistic case by havign an extra call to malloc() every time we add an element to the array. This has the additional advantage of illustrating a common bug (the "memory leak") by calling malloc() several times but neglecting to either remember or free the previous allocations.