How to handle alignment of a header for a dynamic array in C

Question

I am implementing a dynamic array of arbitrary type in C. The implementation works by allocating a header prior to the data of the array:

typedef struct
{
    unsigned char* begin; // Pointer to data
    unsigned char* end; // Pointer to last element
    size_t typeSize; // Size of type
    size_t capacity; // Capacity of array (not number of elements in array)
} dynamicArr;

#define dynamicArr_ConstructBase(dest, src, newCapacity) \
dest = src;                                              \
dest->capacity = newCapacity;                            \
dest->begin = (unsigned char*)dest + sizeof *dest

#define dynamicArr_Construct(dest, src, newCapacity, currSize, typeSize) \
dynamicArr_ConstructBase(dest, src, newCapacity);                        \
dest->end = dest->begin + typeSize * (currSize)

#define dynamicArr_Header(arr) ((dynamicArr*)((unsigned char*)(arr) - sizeof(dynamicArr)))
static inline size_t dynamicArr_Size(dynamicArr* arr)
{
    return (arr->end - arr->begin) / arr->typeSize;
}

#define dynamicArr_Create(typename, arr) typename* arr = (typename*)dynamicArr_Create_(sizeof(typename))
static inline unsigned char* dynamicArr_Create_(size_t typeSize)
{
    dynamicArr* dynArr;
    void* tmp = malloc(sizeof * dynArr + typeSize * 10);
    if (!tmp) return NULL;

    dynArr = tmp;
    dynArr->begin = (unsigned char*)dynArr + sizeof * dynArr;
    dynArr->end = dynArr->begin;
    dynArr->capacity = 10;
    dynArr->typeSize = typeSize;

    return dynArr->begin;
}

#define dynamicArr_Free(arr) free(dynamicArr_Header(arr))

#define dynamicArr_Push(arr, item) \
do                                                                                                \
{                                                                                                 \
    if (arr)                                                                                      \
    {                                                                                             \
        dynamicArr* header = dynamicArr_Header(arr);                                              \
        if (header->typeSize && header->typeSize == sizeof item)                                  \
        {                                                                                         \
            size_t arrSize = dynamicArr_Size(header);                                             \
            if (arrSize == header->capacity)                                                      \
            {                                                                                     \
                size_t newCapacity = (size_t)(header->capacity * 1.5f);                           \
                if (newCapacity == header->capacity) ++newCapacity;                               \
                void* tmp = realloc(header, sizeof(dynamicArr) + header->typeSize * newCapacity); \
                if (tmp)                                                                          \
                {                                                                                 \
                    dynamicArr_Construct(header, tmp, newCapacity, arrSize, header->typeSize);    \
                    *((void**)&(arr)) = header->begin;                                            \
                    arr[arrSize] = item;                                                          \
                    header->end += header->typeSize;                                              \
                }                                                                                 \
                else                                                                              \
                {                                                                                 \
                    free(header);                                                                 \
                    arr = NULL;                                                                   \
                }                                                                                 \
            }                                                                                     \
            else                                                                                  \
            {                                                                                     \
                arr[arrSize] = item;                                                              \
                header->end += header->typeSize;                                                  \
            }                                                                                     \
        }                                                                                         \
    }                                                                                             \
} while(0)

Example use:

void Func()
{
    dynamicArr_Create(int, intArr);
    dynamicArr_Push(intArr, 10);
    printf("%i\n", intArr[0]);
    dynamicArr_Free(intArr);
}

The problem with this is that I believe this is undefined behaviour for if the compiler chooses to use aligned instructions as the items of the array the come after the header may not be aligned.

Is there a way to guarantee the alignment of the items ?

I've looked into using flexible array members, however I'm not sure how to implement this such that it would work with arbitrary types.

For example, I could declare the header like so:

#define dynamicArr_Header(type) \
struct                          \
{                               \
    size_t typeSize;            \
    size_t capacity;            \
    type data[];                \
}

However if I am to use this in code my compiler warns me '=': incompatible types - from '*' to '*'.

Example that causes warning:

dynamicArr_Header(int)* A = malloc(sizeof(dynamicArr_Header(int)));
dynamicArr_Header(int)* B = A; //Causes warning

Is this dangerous to do? Is this because the anonymous structs are really not the same type, or does this cause more problems (such as whether I can guarantee the compiler pads and packs these structs the same way)?

Another "problem" with the flexible array member approach is that I would have to pass the header pointer around unlike in the previous approach where I could provide just the pointer to the data. I know with the flexible array version I could:

int* pntrToIntArr = &header->data[0];

But I would like the header to be abstracted away, but if I provided the pointer to the data array how would I retrieve the header back? Can I just do (dynamicArr_Header(int)*)((unsigned char*)pntrToIntArr - sizeof(dynamicArr_Header(int)))?

Is what I'm doing simply not possible in C without breaking strict-aliasing / alignment rules? I know I'm probably breaking a lot of strict-aliasing rules with the pointer semantics.

Does the header have to be part of the same allocation as the data? Seems like the simplest approach would be to allocate memory for the header, then make a separate allocation for the data. Then you could guarantee alignment thru [an aligned allocation](https://stackoverflow.com/questions/3839922/aligned-malloc-in-gcc). — Nick ODell, Jul 18 '21 at 18:45
@NickODell It technically does not have to part of the same allocation but I would prefer if it was. As I've said in the question I would like the header to be abstracted away and if the data and header were part of 2 different allocations the implementation would not be able to retrieve the header from the data pointer. Obviously I could just ignore this, pass the header pointer around, take the loss and do 2 allocations but I would like to avoid that possibility. — name, Jul 18 '21 at 18:52
To begin with you should get rid of the dirty, unreadable macro. Then maybe people can be bothered with reading this code. The best advise for writing function-like macros are: 1) Don't write function-like macros, and 2) If you really have good reasons why you actually need a function-like macro, then indent the backspace to a fixed column in your text editor, 60, 70 or something like that, long as it is consistent. — Lundin, Jul 18 '21 at 19:34
@Lundin You're too kind. ;-) Seriously, though, IMO there's no reason for a function-like macro like some of the ones here. They literally should just be actual functions. For one, actual functions are a lot easier to maintain since they're not just plopped whole-hog into some unknown context with possible name collisions, nevermind not having to bother with any line continuation. And you can't single-step line-by-line through a macro like that with a debugger unless you like debugging preprocessed code (hint: you ***won't***). — Andrew Henle, Jul 18 '21 at 22:58
@AndrewHenle I chose to use a function-like macro since I was not sure how to implement arbitrary types without it. I'm happy to learn and accept alternative solutions! — name, Jul 18 '21 at 23:46
For the flexible array struct approach, you don't have to pass around a pointer to the header, you can retrieve the header from the data array pointer (see how container_of macro from linux code works), but you have to make sure that the array you pass around is actually a part of a "header struct". As far as the compiler is concerned, A and B don't have the same type (see what you get when you expand the macros). — lulle2007200, Jul 23 '21 at 13:25
But with flexible array structs, you will have a hard time to realloc (if you only want to pass around the pointer to the actual array). You could do something like https://godbolt.org/z/TEP3cYxsK , but that's also awkward to use. — lulle2007200, Jul 23 '21 at 14:44

How to handle alignment of a header for a dynamic array in C

0 Answers0