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:

#include <stdio.h>
#include <stdlib.h>

int main() {
  float *values = NULL;
  int nvals = 0;
  float value;

  printf("Just keep typing in numbers!\n");

  while(scanf("%g", &value) == 1) {
    values = realloc(values, (nvals+1) * sizeof *values);
    values[nvals] = value;
    ++nvals;
  }

  printf("The array has %d elements\n", nvals);
  for(int i = 0; i < nvals; ++i)
    printf("%d: %g\n", i, values[i]);  

  return 0;
}

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.

// Demonstrate a growable array 
#include <stdio.h>
#include <stdlib.h>

# define GROWBY 64

int main() {
  float *values = NULL;
  int nvals = 0, buflen = 0;
  float value;

  printf("Just keep typing in numbers!\n");
  while(scanf("%g", &value) == 1) {
    if ( nvals ==  buflen) {
      buflen += GROWBY;
      values = realloc(values, buflen * sizeof *values);
    }
    values[nvals] = value;
    ++nvals;
  }

  printf("The array has %d elements and %d spare\n", 
         nvals, buflen - nvals);
  for(int i = 0; i < nvals; ++i)
    printf("%d: %g\n", i, values[i]);  
  
  return 0;
}

A more subtle problem

realloc() does not not normally return the same address it was called with.

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?

Any type of "thing" in the problem we are thinking about whose properties cannot be represented by an existing variable type or array should normally have its own structure type.

The following structure combines the three values into a structure:

// Growable array of floats
typedef struct floatarray {
  float *values;
  int nvals;
  int buflen;
} Floatarray;

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):

// Demonstrate a growable array 
#include <stdio.h>
#include <stdlib.h>

# define GROWBY 16
// Growable array of floats
typedef struct floatarray {
  float *values;
  int nvals;
  int buflen;
} Floatarray;

// Allocate a new growable array
Floatarray *newfloatarray(void) {
  Floatarray *f;

  f = xmalloc(sizeof *f); // NB xmalloc checks for NULL
  f->buflen = f->nvals = 0;
  f->values = NULL;

  return f;
}

// Add a value to an array, extending it if necessary
void addtoarray(Floatarray *f, float value) {
  // Check to see if we need to extend the array
  if (   f->nvals == f->buflen) {
    f->buflen += GROWBY;
    f->values = realloc(f->values, f->buflen * sizeof f->values);
  }
  f->values[f->nvals] = value;
  f->nvals++;
}

int main() {
  Floatarray *far;
  float value;

  far = newfloatarray();

  printf("Just keep typing in numbers!\n");

  while(scanf("%g", &value) == 1) {
    addtoarray(far, value);
  }

  printf("The array has %d elements\n", far->nvals);
  for(int i = 0; i < far->nvals; ++i)
    printf("%d: %g\n", i, far->values[i]);
  
  return 0;
}

Step through this code

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.

// Demonstrate a growable array 
// - NB This code contains an unnecessary call to malloc()
// - to simulate the behavior of realloc() in a larger, 
// - more realistic program whether there is other 
// - dynamic memory allocation
#include <stdio.h>
#include <stdlib.h>

# define GROWBY 16
// Growable array of floats
typedef struct floatarray {
  float *values;
  int nvals;
  int buflen;
} Floatarray;

// Allocate a new growable array
Floatarray *newfloatarray(void) {
  Floatarray *f;

  f = xmalloc(sizeof *f); // NB xmalloc checks for NULL
  f->buflen = f->nvals = 0;
  f->values = NULL;

  return f;
}

// Add a value to an array, extending it if necessary
void addtoarray(Floatarray *f, float value) {
  // Check to see if we need to extend the array
  if (   f->nvals == f->buflen) {
    f->buflen += GROWBY;
    f->values = realloc(f->values, f->buflen * sizeof f->values);
  }
  f->values[f->nvals] = value;
  f->nvals++;
}

int main() {
  Floatarray *far;
  float value;
  int *dummy; // - For dummy malloc() call

  far = newfloatarray();

  printf("Just keep typing in numbers!\n");

  while(scanf("%g", &value) == 1) {
    addtoarray(far, value);
    dummy = malloc(8); // - Simulate other calls to malloc
  }

  printf("The array has %d elements\n", far->nvals);
  for(int i = 0; i < far->nvals; ++i)
    printf("%d: %g\n", i, far->values[i]);
  
  return 0;
}

Step through this code