Dynamic Arrays

Standard C arrays have fixed size, but for many applications, we’d like to be able to grow or shrink an array as needed. This can be done efficiently with careful use of realloc. The resulting data structure is called a dynamic array and includes enough information beyond the contents of the array itself to allow resizing to be handled mostly automatically.

The pointer returned by malloc doesn’t give us access to the size of the block, so we are going to need to keep track of this for ourselves. We can do this with a struct that holds a pointer to the block and the size as fields. For some applications, it may be convenient to keep track of a separate count of the number of locations we actually use. This allows use to increase the size of the block to more than we are asked for, so we don’t have to resize every time the user wants to expand it. The usual strategy is that when we grow the block, we guarantee that its new size is at least twice its old size. This gives a trade-off between wasting space (by allocating a block that is up to twice as big as what the user asked for) and wasting time (doubling means that by the time we allocate another n elements, we’ve increased the size of the array by at least n, so the cost per element is O(1)).

A typical struct implementing a dynamic array might look like this:

struct array {
    size_t n;    // number of elements used
    size_t size; // size of data block
    int *data;   // data block
};

The functions implementing the array will be responsible for maintaining the invariants that n <= size and size is in fact the number of ints that can be stored in data.

Below is a simplified implementation of a dynamic array of ints. This implementation skips the n component by not allowing the user to specify the size of the array. Instead, the provided arrayGet and arraySet functions automatically resize the array so that any position the user asks for will be available. This makes the array effectively infinite from the user’s perspective, although available memory may eventually put a constraint on how infinite the array is in practice.

// Basic dynamic array type.
//
// This acts like an unboundedly large array
// of ints, all initialized to zero.
//
// The trick is to resize the underlying array
// whenever the caller asks for a location that
// isn't in the array already.

// Create a new array initialized to 0.
struct array *arrayCreate(void);

// Return the value in an array at given position.
int arrayGet(struct array *, size_t position);

// Set the value in an array at given position.
// Returns new value.
int arraySet(struct array *, size_t position, int value);

// Free all space used by an array.
void arrayDestroy(struct array *);

examples/dynamicArray/array.h

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>

#include "array.h"

// Invariant: size == number of elements in data
struct array {
    size_t size; // number of elements in data;
    int *data;   // malloc'd block
};

#define SIZE_INITIAL (16)
#define SIZE_MULTIPLIER (2)    // Minimum ratio to grow by.

// Create a new array initialized to 0.
struct array *
arrayCreate(void)
{
    struct array *a = malloc(sizeof(struct array));
    assert(a);

    a->size = SIZE_INITIAL;

    // calloc zeroes out the array
    a->data = calloc(a->size, sizeof(int));

    assert(a->data);

    return a;
}

// Expand array if needed to include position.
static void
arrayExpand(struct array *a, size_t position)
{
    if(position >= a->size) {
        // expansion needed
        size_t bigger = a->size * SIZE_MULTIPLIER;

        if(position >= bigger) {
            // even more expansion needed
            bigger = position + 1;
        }

        // Breaks invariant, we will fix later
        // after using a->size to zero out new space.
        a->data = realloc(a->data, sizeof(int) * bigger);

        memset(&a->data[a->size], 0, sizeof(int) * (bigger - a->size));

        a->size = bigger;
    }
}

// Return the value in an array at given position.
int
arrayGet(struct array *a, size_t position)
{
    if(position >= a->size) {
        // No need to expand, just return the default value.
        return 0;
    } else {
        return a->data[position];
    }
}

// Set the value in an array at given position.
int
arraySet(struct array *a, size_t position, int value)
{
    arrayExpand(a, position);

    return a->data[position] = value;
}

// Free all space used by an array.
void 
arrayDestroy(struct array *a)
{
    free(a->data);
    free(a);
}

examples/dynamicArray/array.c

Here is a simple test program testArray.c and Makefile.


Licenses and Attributions


Speak Your Mind