A Simple Dynamic Array for C

Introduction

When many programmers get inspired to implement a dynamic array (meaning an array that grows automatically as new elements are appended) in C, they often try to incorporate the element’s type into the array. Since C lacks a template facility like C++, that often means (ab)using and that, not only has to reallocate the array, but also to O(1).

Why 1.5 instead of 2? The problem with 2 is that doubling the size of each new allocation is always greater than the sum of all previous allocations combined, which means realloc can’t reuse even a block coalesced from previous allocations. For example, assuming previous allocations of 4, 8, and 16 (summing to 28), the next allocation will be 32, but 32 > 28, so realloc can’t reuse that block.

In contrast, growing by 1.5x yields allocations 4, 6, and 9 (summing to 19), and the next allocation will be 13, and 13 ≤ 19, so realloc can reuse that block; hence 1.5x is easier on the memory allocator by reducing fragmentation. Additionally, growing by 1.5x wastes at most 33% of allocated memory whereas 2x wastes at most 50%.

The use of ARRAY_CAP_MIN having a value of 4 eliminates the expensive initial size increases (that would start out as 2, 3, and 4).

Other Functions

The functions array_init, array_reserve, array_push_back, and array_cleanup are all you really need for a dynamic array. For convenience, you could also add functions like array_back, array_front, array_pop_back, array_qsort, and array_bsearch. Those, if wanted, are left as exercises for the reader.

Adding Type Information

Now that we’ve got a nice, small, and efficient implementation of a dynamic array, it turns out that it is possible to add type information thus making the dynamic array type-safe by using just a few small macros.

As far as I know, the following technique was invented by with a pointer to the desired element type:

#define typed_array(TYPE) \

  union { array_t array; TYPE *ptr_type; }



t_array(int) int_array;

By using a union, ptr_type takes up no additional space. It’s also never written to nor read from: it exists only to provide type information at compile-time.

Why TYPE* and not just TYPE? Because (a) TYPE* is sufficient and (b) sizeof(TYPE*) is just the size of a pointer that’s always less than sizeof(array_t).

Given such a union, we can now implement additional wrapper macros for array:

#define typed_array_init(ARRAY) \

  array_init( &(ARRAY)->array, sizeof( *(ARRAY)->ptr_type ) )



#define typed_array_push_back(ARRAY) \

  (typeof((ARRAY)->ptr_type))array_push_back( &(ARRAY)->array )



#define typed_array_at_nc(ARRAY,INDEX) \

  (typeof((ARRAY)->ptr_type))array_at_nc( &(ARRAY)->array, (INDEX) )

Obviously, these macros require , but typeof has also been supported by gcc and clang as an extension to older C versions for some time.

Given those macros, we can now do:

typed_array(int) int_array;

typed_array_init( &int_array );

*typed_array_push_back( &int_array ) = 42;

that eliminates the explicit use of sizeof as well as all the casts. Optionally, you can add even more macros for pointer iteration:

#define typed_array_type(ARRAY)  typeof( *(ARRAY)->ptr_type )



#define typed_array_begin(ARRAY) (ARRAY)->array.elements



#define typed_array_end(ARRAY) \

  typed_array_at_nc( (ARRAY), (ARRAY)->array.len )

Then:

for ( typed_array_type(&ia) *e = typed_array_begin(&ia);

      e < typed_array_end(&ia); ++e ) {

  printf( "%d\n", *e );

}

Caveat

One caveat with typed_array, specifically with its use of an anonymous union, is that C doesn’t consider anonymous unions (or structures) the same type even when their members are identical:

typed_array(int) i;

typed_array(int) j;

// ...

i = j;  // error: assigning incompatible type

However, you can use typedef to make them the same type:

typedef typed_array(int) int_array;



int_array i;

int_array j;

// ...

i = j;  // OK now

Verbosity

If you think having to spell out typed_array all the time is too verbose, you could rename array to be something like vp_array (void pointer array) and then just name typed_array as array, especially if you always plan to use the typed version.

Conclusion

Personally, I find that the dynamic array implementation shown here exemplifies the project and it works just fine.

If you really want a type-safe version, it’s easily added on as an extra. Keeping it as an extra rather than trying to incorporate type information directly into array keeps the two layers nicely separated and makes each simpler.