Implementation of a type-safe generic dynamic array in C

Question

I'm new to C and was trying to write a generic dynamic array which is type safe. I'm not sure if I pulled it off in the best way possible though.

dynarray.h:

#ifndef h_DynArray
#define h_DynArray

#define DYNAMIC_ARR_SIZE 10 // Default size for dynamic arrays
#define DYNAMIC_ARR_GROWTHRATE 2 //Growthrate for dynamic arrays

#define DYNAMIC_ARR_FREE_ON_ERROR 1
#define DYNAMIC_ARR_KEEP_ON_ERROR 0

struct DynArray_Options
{
    char freeOnError; // If set, will free the contents of the array when an error is caught, otherwise the contents remain
} DynArray_Options;

struct $DynArray
{
    size_t size; // Number of elements in array
    size_t capacity; // Capacity of array
    unsigned char* data; // Pointer to data
    struct DynArray_Options options; // Array options

    size_t typeSize; // sizeof(type)
};

void $DynArray_Create(struct $DynArray* arr, size_t typeSize);
void $DynArray_Free(struct $DynArray* arr);
void $DynArray_EmptyPush(struct $DynArray* arr);
void $DynArray_Push(struct $DynArray* arr, void* value);
void $DynArray_Pop(struct $DynArray* arr);
void $DynArray_RemoveAt(struct $DynArray* arr, size_t index);
void $DynArray_Shrink(struct $DynArray* arr);
void $DynArray_Reserve(struct $DynArray* arr, size_t size);

/*
* Defines a DynArray of type(tag).
*/
#define DynArray(tag) DynArray$##tag

/*
* Utility macros for getting functions for type(tag).
*/

#define DynArray_ReinterpretCast(tag) DynArray$##tag##_ReinterpretCast
#define DynArray_Create(tag) DynArray$##tag##_Create
#define DynArray_Free(tag) DynArray$##tag##_Free
#define DynArray_EmptyPush(tag) DynArray$##tag##_EmptyPush
#define DynArray_Push(tag) DynArray$##tag##_Push
#define DynArray_Pop(tag) DynArray$##tag##_Pop
#define DynArray_RemoveAt(tag) DynArray$##tag##_RemoveAt
#define DynArray_Shrink(tag) DynArray$##tag##_Shrink 
#define DynArray_Reserve(tag) DynArray$##tag##_Reserve

#define DynArray_Decl(type, tag) \
$DynArray_Decl_Type(type, tag) \
static inline void DynArray$##tag##_Create(struct DynArray(tag)* arr) \
{ \
    $DynArray_Create(&arr->$arr, sizeof(type)); \
} \
$DynArray_Decl_Func(type, tag) \
$DynArray_Decl_Func_Push(type, tag)

#define $DynArray_Decl_Type(type, tag) \
struct DynArray(tag) \
{ \
    union \
    { \
        struct $DynArray $arr; \
        struct \
        {  \
            size_t size; \
            size_t capacity; \
            type* values; \
            struct DynArray_Options options; \
        }; \
    }; \
};

#define $DynArray_Decl_Func(type, tag) \
static inline struct DynArray(tag) DynArray$##tag##_ReinterpretCast(void* arr) \
{ \
    struct DynArray(tag) dst; \
    memcpy(&dst, arr, sizeof dst); \
    return dst; \
} \
static inline void DynArray$##tag##_Free(struct DynArray(tag)* arr) \
{ \
    $DynArray_Free(&arr->$arr); \
} \
static inline void DynArray$##tag##_EmptyPush(struct DynArray(tag)* arr) \
{ \
    $DynArray_EmptyPush(&arr->$arr); \
} \
static inline void DynArray$##tag##_Pop(struct DynArray(tag)* arr) \
{ \
    $DynArray_Pop(&arr->$arr); \
} \
static inline void DynArray$##tag##_RemoveAt(struct DynArray(tag)* arr, size_t index) \
{ \
    $DynArray_RemoveAt(&arr->$arr, index); \
} \
static inline void DynArray$##tag##_Shrink(struct DynArray(tag)* arr) \
{ \
    $DynArray_Shrink(&arr->$arr); \
} \
static inline void DynArray$##tag##_Reserve(struct DynArray(tag)* arr, size_t size) \
{ \
    $DynArray_Reserve(&arr->$arr, size); \
}

#define $DynArray_Decl_Func_Push(type, tag) \
static inline void DynArray$##tag##_Push(struct DynArray(tag)* arr, type value) \
{ \
    $DynArray_Push(&arr->$arr, &value); \
} \

/*
* The following is used to define the "raw" version of DynArray
* which uses a custom Create function to assign sizeof(type).
*/
$DynArray_Decl_Type(unsigned char, raw)
static inline void DynArray$raw_Create(struct DynArray(raw)* arr, size_t typeSize)
{
    $DynArray_Create(&arr->$arr, typeSize);
}
$DynArray_Decl_Func(unsigned char, raw)
static inline void DynArray$raw_Push(struct DynArray(raw)* arr, void* value)
{
    $DynArray_Push(&arr->$arr, value);
}

#endif

dynarray.c:

#include <stdlib.h>
#include <string.h>
#include "dynarray.h"

void $DynArray_Create(struct $DynArray* arr, size_t typeSize)
{
    arr->data = malloc(typeSize * DYNAMIC_ARR_SIZE);
    arr->size = 0;
    arr->capacity = DYNAMIC_ARR_SIZE;
    arr->typeSize = typeSize;
    arr->options.freeOnError = DYNAMIC_ARR_FREE_ON_ERROR;
}

void $DynArray_Free(struct $DynArray* arr)
{
    free(arr->data);
    arr->data = NULL;
}

inline void $DynArray_ErrorFree(struct $DynArray* arr)
{
    if (arr->options.freeOnError)
    {
        free(arr->data);
        arr->data = NULL;
    }
}

void $DynArray_EmptyPush(struct $DynArray* arr)
{
    if (arr->data)
    {
        if (arr->size == arr->capacity)
        {
            size_t newCapacity = (size_t)(arr->capacity * DYNAMIC_ARR_GROWTHRATE);
            if (newCapacity == arr->capacity) ++newCapacity;
            void* tmp = realloc(arr->data, arr->typeSize * newCapacity);
            if (tmp)
            {
                arr->data = tmp;
                arr->capacity = newCapacity;
                ++arr->size;
            }
            else
            {
                $DynArray_ErrorFree(arr);
            }
        }
        else
        {
            ++arr->size;
        }
    }
}

void $DynArray_Push(struct $DynArray* arr, void* value)
{
    $DynArray_EmptyPush(arr);
    if (arr->data) memcpy(arr->data + (arr->size - 1) * arr->typeSize, value, arr->typeSize);
}

void $DynArray_Pop(struct $DynArray* arr)
{
    if (arr->data)
    {
        if (arr->size > 0)
        {
            --arr->size;
        }
    }
}

void $DynArray_RemoveAt(struct $DynArray* arr, size_t index)
{
    if (arr->data)
    {
        if (arr->size > 1 && index > 0 && index < arr->size)
        {
            size_t size = arr->size - 1 - index;
            if (size != 0) memmove(arr->data + index * arr->typeSize, arr->data + (index + 1) * arr->typeSize, size * arr->typeSize);
            --arr->size;
        }
    }
}

void $DynArray_Shrink(struct $DynArray* arr)
{
    if (arr->data)
    {
        size_t newCapacity = arr->size;
        if (newCapacity != arr->capacity)
        {
            void* tmp = realloc(arr->data, arr->typeSize * newCapacity);
            if (tmp)
            {
                arr->data = tmp;
                arr->capacity = newCapacity;
                ++arr->size;
            }
            else
            {
                $DynArray_ErrorFree(arr);
            }
        }
    }
}

void $DynArray_Reserve(struct $DynArray* arr, size_t size)
{
    if (arr->data)
    {
        size_t newCapacity = arr->size + size;
        if (newCapacity > arr->capacity)
        {
            void* tmp = realloc(arr->data, arr->typeSize * newCapacity);
            if (tmp)
            {
                arr->data = tmp;
                arr->capacity = newCapacity;
                arr->size = size;
            }
            else
            {
                $DynArray_ErrorFree(arr);
            }
        }
        else
        {
            arr->size = size;
        }
    }
    else
    {
        void* tmp = malloc(arr->typeSize * size);
        if (tmp)
        {
            arr->data = tmp;
            arr->capacity = size;
            arr->size = size;
        }
    }
}

usage:

DynArray_Decl(int, int) // Declaration outside

int main()
{
    struct DynArray(int) intArr;
    DynArray_Create(int)(&intArr);

    for (size_t i = 0; i < 10; i++)
    {
        DynArray_Push(int)(&intArr, i);
    }

    printf("size: %i\n", intArr.size);
    printf("%i\n", intArr.values[2]);
}

I'm also not too sure if I utilized union properly in the declaration ($DynArray_Decl_Type) or if that produces undefined behaviour.

Welcome to Code Review! I have rolled back Rev 4 → 2. Please see What to do when someone answers. — Sᴀᴍ Onᴇᴌᴀ
– Sᴀᴍ Onᴇᴌᴀ ♦, Commented Nov 8, 2021 at 19:52

chux · Accepted Answer · 2021-11-08 12:47:21Z

Big task

OP's goal of "trying to write a generic dynamic array which is type safe." is admirable, but not a good task for someone new to C.

I recommend to start with a write a generic dynamic array for void *.

Later, research _Generic.

Not so generic

Approach relies on types not having spaces.

Try struct DynArray(long long) llArr;

Stand-alone failure

#include "dynarray.h" fails as dynarray.h requires prior #include <>. Put those in dynarray.h.

Use #include "dynarray.h" first, before other includes, in dynarray.c to test.

Why 10

Rather than some magic number 10, Rework to start with size 0.

// #define DYNAMIC_ARR_SIZE 10

Allow $DynArray_Free(NULL)

This, like free(NULL), simplifies clean-up

void $DynArray_Free(struct $DynArray* arr) {
  if (arr) {
    free(arr->data);
    arr->data = NULL;
  }
}

More reasonable max line length

        // if (size != 0) memmove(arr->data + index * arr->typeSize, arr->data + (index + 1) * arr->typeSize, size * arr->typeSize);

vs.

        if (size != 0) {
          memmove(arr->data + index * arr->typeSize, 
              arr->data + (index + 1) * arr->typeSize,
              size * arr->typeSize);
        }

$ is not part of the standard C coding languages

$ not needed anyways. Consider dropping it.

Unneeded if()

In $DynArray_Reserve(), code starts with unneeded if (arr->data) test. realloc(NULL, ...) is OK.

If ptr is a null pointer, the realloc function behaves like the malloc function for the specified size.

Uniform naming

Rather than DYNAMIC_ARR_..., match DYNARRAY_....

Other than that, very good naming scheme.

Allow pushing const data

// void $DynArray_Push(struct $DynArray* arr, void* value)
void $DynArray_Push(struct $DynArray* arr, const void* value)

Not always an error

$DynArray_Shrink() calls $DynArray_ErrorFree(arr) even if arr->size == 0.

Bug??

In $DynArray_Shrink(), code has ++arr->size;. Maybe --arr->size;?

Pedantic: check overflow

// Add
if (arr->capacity > SIZE_MAX/DYNAMIC_ARR_GROWTHRATE) Handle_Error();
size_t newCapacity = (size_t)(arr->capacity * DYNAMIC_ARR_GROWTHRATE);

Use correct specifier

I also suspect code was not compiled with all warnings enabled. Save time, enabled them all.

// printf("size: %i\n", intArr.size);
printf("size: %zu\n", intArr.size);

Info hiding

Consider only declaring struct $DynArray in dynarry.h and putting the definition in dynarray.c. User need not see the members. Create access functions if member access needed.

Thanks, this was really helpful, however in the case of types having spaces such as in long long, is this not covered by the code using a tag for its types? For example: DynArray_Decl(long long, longlong) then when using it, use struct DynArray(longlong) — name
– name, Commented Nov 8, 2021 at 13:30
Also yes there is a bug in the shrink function, thanks for pointing that out haha, there should be no modification to arr->size. Good catch! — name
– name, Commented Nov 8, 2021 at 13:33
Also, just had a very quick look at _Generic, but I'm not sure how it would work to allow for user-defined types. — name
– name, Commented Nov 8, 2021 at 13:45
@name Re: DynArray_Decl. The .h file provides scant info on its usage. Sample code also lacks detail with DynArray_Decl(int, int). AFAIK, one should code DynArray_Decl(long long, long long). Do not relay on user access to the *.c file to understand how to this function set. More documentation in the .h file is deserved. — chux
– chux, Commented Nov 8, 2021 at 16:01
@name Does not main() demo a failed type safe? struct DynArray(int) intArr; ... DynArray_Push(int)(&intArr, i /* which is a size_t and not int */);? — chux
– chux, Commented Nov 8, 2021 at 16:06

Stack Exchange Network

Implementation of a type-safe generic dynamic array in C

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Implementation of a type-safe generic dynamic array in C

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions