C is an obsolete language and there’s really no good reason to use it. For all but the most esoteric projects, C++ should be used instead of C. I may elaborate on this theme in a future post.

That being said, sometimes you’re stuck with C code. Maybe you’re working on legacy code, or you don’t have control over the engineering requirements. Maybe management mistakenly thought C was “faster” or “more portable”. Maybe there’s no C++ compiler for your platform.

Recently, I was asked to reduce the memory footprint for a C application which had somehow ballooned to gargantuan proportions. The application was targeted at an embedded device with 64MB of RAM and no virtual memory. A bit of sleuthing revealed that a geocoding API was allocating a 20MB data structure. That’s a pretty hefty chunk of change for our little device. The API allocated space for up to 50 matches (each of which was 400kb), instead of using a dynamic array to return the results. The code was written by a junior engineer.

When using C, you tend to spend inordinate amounts of time managing arrays, strings, and hashtables. Think of the thousands of hours wasted on such minutae. Isn’t our collective time more valuable? I feel pity for the poor engineers (like me) forced to labor under such cruel conditions.

Here is a recipe for quick and dirty dynamic arrays in C. I have used this pattern many times with excellent results.

Introduction

This example is targeted at a specific use case. It will serve you well if you have to accumulate an unknown amount of data. You can roll this into an existing struct or grow it into a generic void* array class. I tend to use it inline in other data structures because it’s so simple. You can also use this pattern in Java if you want to avoid the overhead of the java.util.* classes.

Struct

First, create a struct or add the members to an existing struct. In this case I’m creating a new struct and my array will store char*’s. Note that pos is the number of elements in the array, and capacity is the number of elements that the array is capable of storing. Feel free to use other variable names if they make more sense to you.

Gub is simply a word I use a lot in test code, similar to foo or bar.

typedef struct {
    int pos;
    int capacity;
    char **array;
} Gub;

Init the struct

calloc is a handy allocation function that fills the memory with zeroes before returning it. This is an easy way to avoid uninitialized memory errors. In this case, I’m also counting on that behavior because I want pos to be 0 and I want array to be NULL before proceeding.

Gub *g = (Gub*)calloc(sizeof(Gub), 1);

Create an empty array

When creating the empty array, it’s necessary to select an initial capacity. In this case the array can hold four elements before it needs to be resized. Note that we init capacity inline here. Personally I think this makes the code more readable.

This could be written just as easily with malloc (or calloc), but I prefer to use realloc to matche the code used when appending elements (see below). Realloc is a magical allocation function that resizes an existing block of allocated memory to a new size. It’s tremendously useful for resizable data structures. If you pass NULL to realloc (as we’re doing here with the g->array), realloc will simply allocate new memory for you.

g->array = (char**)realloc(g->array, (g->capacity = 4) *
                                     sizeof(char*));

Append some data

This is a silly loop that appends argv to the array. Before adding an element to the array, we check to see if there’s room for more elements. If pos == capacity, the array is full and must be resized. Realloc resizes the block of memory and then we’re good to go. Again, note that capacity is modified inline during the realloc. I think this makes the code more readable. In this case I’m simply doubling the size of the array whenever we run out of space.

Also, note that g->pos is incremented inline when we actually add the element.

for (int i = 0; i < argc; ++i) {
    if (g->pos == g->capacity) {
        g->array = (char**)realloc(g->array, (g->capacity *= 2) *
                                             sizeof(char*));
    }
    g->array[g->pos++] = argv[i];
}

Free

When we’re done with the array, we free it and then the containing struct. Don’t forget to free the elements themselves if necessary.

free(g->array);
free(g);