2
\$\begingroup\$

The previous generic dynamic array I asked a review for here was written using only the preprocessor and so while the array itself was type-safe, all the manipulating macros where not.

In this try I wrote a dynamic array that stores the element size, and then a macro interface that hides it as an implementation detail. I also took advice from the previous review and removed the arrayMap(array,callback) macro and replaced it with VEC_FOREACH(index_variable_name, vec) which is simply a wrapper around a for loop.

A note on memory allocation: as I'm still testing this array, I didn't add any code to gracefully handle memory allocation errors yet.

The code is currently in a single file, and isn't ready yet to be included by other files yet.

#include <stdint.h>
#include <stdlib.h>
#include <stddef.h> // offsetof
#include <assert.h>

typedef struct vec_header {
    uint32_t used;
    uint32_t capacity;
    uint32_t element_size;
    char data[];
} VecHeader;

union align {
    int i;
    long l;
    long *lp;
    void *p;
    void (*fp)(void);
    float f;
    double d;
    long double ld;
};

union header {
    VecHeader h;
    union align a;
};

VecHeader *_vec_make_header(uint32_t element_size, uint32_t capacity) {
    VecHeader *h = calloc(1, element_size * capacity + sizeof(union header));
    assert(h);
    h->capacity = capacity;
    h->element_size = element_size;
    return h;
}


static inline VecHeader *_vec_to_header(void *vec) {
    assert(vec);
    return vec - offsetof(VecHeader, data);
}

void _vec_free_header(VecHeader *h) {
    free(h);
}

void _vec_ensure_capacity(void **vec, uint32_t capacity) {
    assert(vec && *vec);
    VecHeader *h = _vec_to_header(*vec);
    if(h->used >= capacity) {
        return;
    }
    h->capacity = capacity;
    h = realloc(h, h->element_size * h->capacity +sizeof(union header));
    assert(h);
    *vec = (void *)h->data;
}

void *_vec_prepare_push(void **vec) {
    assert(vec && *vec);
    VecHeader *h = _vec_to_header(*vec);
    if(h->used + 1 > h->capacity) {
        h->capacity *= 2;
        h = realloc(h, h->element_size * h->capacity + sizeof(union header));
        assert(h);
    }
    h->used++;
    *vec = (void *)h->data;
    return h->data + (h->used - 1) * h->element_size;
}


void *_vec_pop(VecHeader *h) {
    assert(h && h->used > 0);
    h->used--;
    return h->data + h->used * h->element_size;
}

void *_vec_get(VecHeader *h, uint32_t index) {
    assert(h && index < h->used);
    return h->data + index * h->element_size;
}

void _vec_copy(void **dest_vec, VecHeader *src) {
    assert(dest_vec && *dest_vec && src);
    VecHeader *dest = _vec_to_header(*dest_vec);
    assert(dest->element_size == src->element_size);
    dest->used = 0; // clear the destination vec.
    _vec_ensure_capacity(dest_vec, src->capacity);
    dest = _vec_to_header(*dest_vec); // needed in case of reallocation in above call.
    // both loops can be replaced with 'memcpy(dest->data, src->data, i * src->element_size);
    for(uint32_t i = 0; i < src->used; ++i) {
        for(uint32_t j = 0; j < src->element_size; ++j) {
            dest->data[i * dest->element_size + j] = src->data[i * src->element_size + j];
        }
    }
    _vec_to_header(*dest_vec)->used = src->used;
}

void _vec_reverse(void *vec) {
    assert(vec);
    VecHeader *h = _vec_to_header(vec);
    // The division below might result in a float in which
    // case it will be rounded down which is what we want.
    for(uint32_t i = 0; i < h->used / 2; ++i) {
        for(uint32_t j = 0; j < h->element_size; ++j) {
            char tmp = h->data[i * h->element_size + j];
            h->data[i * h->element_size + j] = h->data[(h->used - i - 1) * h->element_size + j];
            h->data[(h->used - i - 1) * h->element_size + j] = tmp;
        }
    }
}

#define VEC_INITIAL_SIZE 8

#define VEC_NEW(type) ((type *)(_vec_make_header(sizeof(type), VEC_INITIAL_SIZE)->data))
#define VEC_FREE(vec) (_vec_free_header(_vec_to_header((void *)vec)))

#define VEC_CAPACITY(vec) (_vec_to_header((void *)vec)->capacity)
#define VEC_LENGTH(vec) (_vec_to_header((void *)vec)->used)

#define VEC_PUSH(vec, value) (*(typeof(vec))(_vec_prepare_push((void **)&(vec))) = (value))
#define VEC_POP(vec) (*(typeof(vec))_vec_pop(_vec_to_header((void *)vec)))
#define VEC_GET(vec, index) (*(typeof(vec))_vec_get(_vec_to_header((void *)vec), index))

#define VEC_COPY(dest, src) (_vec_copy((void **)&(dest), _vec_to_header((void *)src)))
#define VEC_CLEAR(vec) ((void)(_vec_to_header((void *)vec)->used = 0))

#define VEC_REVERSE(vec) (_vec_reverse((void *)(vec)))

#define VEC_FOREACH(index_var_name, vec) for(uint32_t index_var_name = 0; index_var_name < VEC_LENGTH(vec); ++index_var_name)
// Note: [vec] is referenced multiple times.
#define VEC_ITERATE(iter_var_name, vec) for(typeof(*vec) *iter_var_name = (vec); iter_var_name - (vec) < VEC_LENGTH(vec); ++iter_var_name)

An example usage:

#include <stdio.h>

int main(void) {
    int *nums = VEC_NEW(int);
    VEC_PUSH(nums, 42);
    VEC_PUSH(nums, 123);

    VEC_FOREACH(i, nums) {
        printf("nums[%u] = %d\n", i, nums[i]); // VEC_GET(nums, i) checks bounds.
    }

    int *nums2 = VEC_NEW(int);
    VEC_COPY(nums2, nums);
    printf("len: %u, cap: %u, nums2[len] = %d\n", VEC_LENGTH(nums2), VEC_CAPACITY(nums2), VEC_POP(nums2));
    VEC_CLEAR(nums2);
    VEC_FREE(nums2);
    VEC_FREE(nums);
    return 0;
}

\$\endgroup\$
1
  • 3
    \$\begingroup\$ I really like the DbC precondition checks, such as assert(h && h->used > 0);. Consider writing multiple asserts, one per conjunct. It is "equivalent", yes. But in the unlikely event that, say, 2nd conjunct fails, then the line number of the assert diagnostic will give us valuable debugging information that the combined expression will not. No biggie, just something to consider. \$\endgroup\$
    – J_H
    Commented Jan 16, 2023 at 20:03

1 Answer 1

1
\$\begingroup\$

Should vec_header.data be a uint8_t instead of a char?

VEC_NEW asserts and fails on an allocation error. It could return NULL and let the caller decide how to handle out-of-memory errors.

Why does _vec_ensure_capacity test that h->used is greater than the desired capacity, rather than h->capacity? This means you may reallocate when the destination is large enough, but not full. And when used is bigger than the new capacity, you don't reallocate - leaving around the old values with no way to access them.

_vec_prepare_push could call _vec_ensure_capacity to avoid having two very similar blocks of code that call realloc.

The last line of _vec_copy shouldn't need another call to _vec_to_header: dest already has that value.

Technically, the division in _vec_reverse won't result in a float, but it will be rounded toward zero as you state.

In _vec_reverse, I might use two local variables for the repeated index calculations: uint32_t front = i * h->element_size + j; rear = (h->used - i - 1) * h->element_size + j;

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.