Dynamic array in C

Question

It's a dynamic array, the elements can be accessed normally and it supports any type. I believe I'm relying on undefined behavior when I treat every pointer to pointer as void ** and I would like to know if it will work on the main platforms.

Every call to da_reserve() and da_push_back() might cause the array address to change. The meta data is hidden behind the pointer that is returned by da_new().

I know it's kind of a hack and I appreciate any suggestions on how to make it a proper dynamic array.

dynamic_array.h

#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H

#include <stdlib.h>
#include <stdbool.h>

#define DA_SUCCESS 1
#define DA_ERROR 0
extern void *DA_EMPTY;

#define Dynamic_Array(type)type *
#define Dynamic_Array_Ptr(da)(void **)da

#define da_new(type, slots) da_new_(sizeof(type), (slots))
void *da_new_(size_t size, size_t slots);
void da_delete(void *da);

int da_push_back(void **da, void *element);
void *da_pop_back(void *da);

size_t da_get_count(void *da);
size_t da_available_slots(void *da);

bool da_is_empty(void *da);
bool da_is_full(void *da);

void da_clear(void *da);
void da_reserve(void **da, size_t total_slots);

#endif

dynamic_array.c

#include "dynamic_array.h"
#include <string.h>

typedef struct {
    size_t size;
    size_t position;
    size_t slots;
} Index;

static char dummy;
void *DA_EMPTY = &dummy;

static inline Index *get_index(void *da)
{
    return (Index *)da - 1;
}

static inline void *get_da(Index *index)
{
    return index + 1;
}

void *da_new_(size_t size, size_t slots)
{
    Index *index = malloc(sizeof(Index) + size * slots);
    if(index == NULL)
        return NULL;

    index->size = size;
    index->position = 0;
    index->slots = slots;

    return get_da(index);
}

void da_delete(void *da)
{
    free(get_index(da));
}

static int expand(void **da)
{
    Index *index = get_index(*da);
    size_t new_size = index->slots * 2;
    if((index = realloc(index, new_size * index->size + sizeof(Index))) == NULL)
        return DA_ERROR;

    index->slots = new_size;
    *da = get_da(index);
    return DA_SUCCESS;
}

int da_push_back(void **da, void *element)
{
    Index *index = get_index(*da);
    if(index->position == index->slots)
        if(expand(da) == DA_ERROR)
            return DA_ERROR;

        else
            index = get_index(*da);

    memcpy((char *)*da + index->position++ * index->size, element, index->size);
    return DA_SUCCESS;
}

void *da_pop_back(void *da)
{
    Index *index = get_index(da);
    if(index->position == 0)
        return DA_EMPTY;

    return (char *)da + --index->position * index->size;
}

size_t da_get_count(void *da)
{
    Index *index = get_index(da);
    return index->position;
}

size_t da_available_slots(void *da)
{
    Index *index = get_index(da);
    return index->slots - index->position;
}

bool da_is_empty(void *da)
{
    Index *index = get_index(da);
    return index->position == 0;
}

bool da_is_full(void *da)
{
    Index *index = get_index(da);
    return index->position == index->slots;
}

void da_clear(void *da)
{
    Index *index = get_index(da);
    index->position = 0;
}

void da_reserve(void **da, size_t total_slots)
{
    Index *index = get_index(*da);

    if(index->slots >= total_slots)
        return;

    if((index = realloc(index, total_slots * index->size + sizeof(Index))) == NULL)
        return;

    index->slots = total_slots;
    *da = get_da(index);
}

usage

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "dynamic_array.h"

int main(void)
{
    srand(time(NULL));

    Dynamic_Array(int) numbers = da_new(int, 500);

    for(size_t i = 0; i < 50000; ++i){
        int random = rand();
        da_push_back(Dynamic_Array_Ptr(&numbers), &random);
    }

    size_t count = da_get_count(numbers);
    for(size_t i = 0; i < count; ++i)
        printf("Random number: %d\n", numbers[i]);

    da_delete(numbers);

    return 0;
}

Answer 1

Nasty Hack

I grant that it's a hack but I'd like to know of a platform where the following doesn't fix the alignment issue:

typedef struct {
    size_t size;
    size_t position;
    size_t slots;
    size_t padding;//NOT USED.
} Index;

The alignment issue is that although malloc(.) returns a universally aligned address, the sizeof(Index) may not be a multiple of the alignment of the element type.

So for example if sizeof(size_t)==4 (i.e. typical 32-bit platform) it is likely that the Index in the OP will be such that sizeof(Index)=12 but if the elements are say double requiring alignment of 8 the array will start at an address that is 4 mod 8 not 0 mod 8 as required. Operations on the elements as double 'in situ' will have undefined behaviour.

The reason my hack will work is that given there is no reason to pad Index then as I propose it sizeof(Index)=4*sizeof(size_t) giving 4 byte alignment off the bat.

If sizeof(size_t)==2 (e.g. 16-bit platform) it will be 8 byte aligned.

If sizeof(size_t)==4 (e.g. 32-bit platform) it will be 16 byte aligned.

If sizeof(size_t)==8 (e.g. 64-bit platform) it will be 32 byte aligned.

So the 'breaking' case is a platform with a data type having an alignment greater than 4 times the word size. I know of none and think such a thing unlikely.

Doing It Properly

If you want to do it all properly you need to work out the alignment of the stored type. There is no guaranteed standard way to achieve that. In C++11 you can use alignof(.) but this is a C challenge. The most portable way (I know of) is:

#include <stddef.h> //Defines offsetof(.,.) macro.
#define alignment_of(type) offsetof(struct { char w;type v;},v)

Here's a skeleton of a fixed dynamic array. I leave completion as an exercise. Noteworthy features are:

1. Addresses alignment using best available practice (above).

2. Uses 1 for error and 0 for success. That is so ingrained it is beyond a matter of taste. See comments.

3. Engages in a bit of type punning to provide a bit of type-safety. void* parameters are asking for trouble.

4. Adds a bit of type-safety by size checking values pushed onto the array.

I would suggest 1 & 2 are mandatory but 3 & 4 are ideas to consider.

#include <stdint.h>//Defines MAX_SIZE
#include <stddef.h>//Defines the little known offsetof macro.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>//Defines memcpy(.,.,.). I know! I know!

//Defined as a macro so we can implement a bit of dynamic type safety.
#define da_push_back(DA,ELEM) da_push_back_(&(DA),&(ELEM),sizeof(ELEM))

//Best known practice for determining type alignment in C.
#define alignment_of(type) offsetof(struct { char w;type v;},v)

#define da_new(type,slots) da_new_(sizeof(type),slots,alignment_of(type),#type)

//Overwhelming convention is to use zero as 'success' and non-zero as 'error'.
//This allows the definition of diagnostic error codes and meaningful constructs 
// like int error=da_thing(); if(error){ handle error... }
const int DA_SUCCESS=0;
const int DA_ERROR=1;

struct dynamic_struct;

typedef struct dynamic_struct* dynamic_array;

typedef struct {
    size_t size;
    size_t position;
    size_t slots;
    size_t offset;//This will be store the amount of dynamically calculated alignment padding.
    const char* name;//Optional run-time type info. See stringizing # in macro.
} Index;


dynamic_array da_new_(size_t size,size_t slots,size_t align,const char* name){

    //Get alignment for both elements & Index.
    size_t falign=alignment_of(Index);
    if(falign<align){
        falign=align;
    }
    
    //offset will be the padding to go before Index.
    const size_t over=sizeof(Index)%falign;
    const size_t offset=over==0?0:falign-over;

    //Allocate the padding the Index and the slots.
    const size_t headersize=offset+sizeof(Index);
    char*const block=malloc(headersize+size*slots);
    if(block==NULL){
        return NULL;//allocation failed - behave like malloc(.).
    }
    
    //Notice we are padding at the start.
    //If we pad between Index and the elements we get in to a muddle.
    //To find the index from the array we need the offset but it's in the Index!
    //It's important to remember this offset so we can free the right point at the end.
    Index* index=(Index*)(block+offset);
    
    index->size=size;
    index->position=0;
    index->slots=slots;
    index->offset=offset;
    index->name=name;
    return (dynamic_array)(block+headersize);
}


Index* da_get_index(dynamic_array da){
    return ((Index*)da)-1;
}

const char* da_get_typename(dynamic_array da){
    return da_get_index(da)->name;
}

size_t da_get_slots(dynamic_array da){
    return da_get_index(da)->slots;    
}

int da_delete(dynamic_array da){
    //remember kids only render unto free(.) what malloc(.) has rendered unto thee.
    //Or calloc(.) or realloc(.) obviously. But you get the point.
    //We need to find the bottom of the block including any offset padding.
    Index*const index=da_get_index(da);
    const size_t offset=index->offset;
    void*const block=((char*const)index)-offset;
    free(block);
    return DA_SUCCESS;
}

//We pass in sizecheck from the macro as a bit of type safety.
//Obviously this is no guarantee but will at least protect against some gross errors.
int da_push_back_(dynamic_array* da,const void*const element,const size_t sizecheck){
    Index* index=da_get_index(*da);
    const size_t size=index->size;
    const size_t position=index->position;
    const size_t slots=index->slots;
    
    if(sizecheck!=size){
        return DA_ERROR;//element not compatible with array...
    }
    
    if(position>=slots){
        size_t newslots;
        if(slots>SIZE_MAX/2){
            if(slots==SIZE_MAX){
                return DA_ERROR;//Exceeded size_t. 
            }
            newslots=SIZE_MAX;
        }else{
            newslots=slots==0?1:slots*2;
        }
        const size_t offset=index->offset;
        const size_t headersize=offset+sizeof(Index);
        void*block=((char*)index)-offset;
        char* newblock=realloc(block,headersize+newslots*size);
        if(newblock==NULL){
            return DA_ERROR;//Re-allocation failed.
        }
        *da=(dynamic_array)(newblock+headersize);
        index=da_get_index(*da);
        index->slots=newslots;
    }
    
    char* array=(char*)*da;
    memcpy(array+position*size,element,size);
    ++(index->position);
    return DA_SUCCESS;
}

void* da_get_array(dynamic_array da){
    return da;
}

int main(void) {
    int errors=0;
    dynamic_array array=da_new(double,3);

    double val=-2.718;
    errors+=da_push_back(array,val);    

    double*access=da_get_array(array);
    access[1]=1234.0;
    access[2]=3.1415926535;

    printf("type-name is \"%s\"\n",da_get_typename(array));
    printf("%p %f %f %f\n",(void *)access,access[0],access[1],access[2]);
    
    da_delete(array);
    
    dynamic_array grow=da_new(int,3);
    
    if(da_get_slots(grow)<3){
        ++errors;
    }
    
    int vint=99;
    errors+=da_push_back(grow,vint);
    vint=88;
    errors+=da_push_back(grow,vint);
    vint=77;
    errors+=da_push_back(grow,vint);
    
    //Now we make it grow...
    vint=66;
    errors+=da_push_back(grow,vint);
    
    if(da_get_slots(grow)<4){
        ++errors;
    }

    
    int* ints=da_get_array(grow);
    
    if(ints[0]!=99||ints[1]!=88||ints[2]!=77||ints[3]!=66){
        ++errors;
    }
    
    printf("%d %d %d %d\n",ints[0],ints[1],ints[2],ints[3]);
    
    da_delete(grow);
    
    dynamic_array longd=da_new(long   double,10);
    
    //Stringizing will 'normalise' the white-space in the typename.
    //The source has multiple white-space characters
    if(strcmp("long double",da_get_typename(longd))!=0){
        ++errors;
    }
    da_delete(longd);
    
    //But it will consider aliases to be different.
    //Notice how these two arrays have the same type but not type-name.
    dynamic_array uinta=da_new(unsigned,10);
    if(strcmp("unsigned",da_get_typename(uinta))!=0){
        ++errors;
    }
    
    dynamic_array uintb=da_new(unsigned int,10);
    if(strcmp("unsigned int",da_get_typename(uintb))!=0){
        ++errors;
    }
    
    da_delete(uinta);
    da_delete(uintb);    
    
    if(errors!=0){
        printf("ERRORS - %d\n",errors);
    }else{
        printf("** SUCCESS **\n");
    }
    return errors==0?EXIT_SUCCESS:EXIT_FAILURE;
}