Simple expandable vector in C

Question

I'm getting tired of reading templated c++ code so I am dipping my feet in c. Here is a small, not full, implementation of an expandable vector. Right now I need only push_back and the ability to grow on demand, no pop or removal that's why it's missing.

Just upfront, yes I did consider making the vector metadata and the dynamic memory one block of memory, I just didn't like having to pass a double pointer to enable the reallocation. If there is another option i'd like to hear it.

With regard to initialization I was wondering what the more preferred way of doing it the way i did it ...

vector* v = vector_allocate(); // allocate data in v and v itself
vector_free(v); // free data in v and v itself
v = NULL;

or

vector v;
vector_initialize(&v); // allocate data in v
vector_free(&v); // free data in v
// v is now unusable ...

Code is written for Visual Studio, i did not compile under gcc.

#ifdef _MSC_VER 
    #define _CRTDBG_MAP_ALLOC  
    #include <stdlib.h>  
    #include <crtdbg.h> 
#else
    #include <stdlib.h>
    #define _CrtDumpMemoryLeaks()   ((int)0)
#endif

#include <assert.h>
#include <stdio.h>
#include <string.h>

typedef struct {
    size_t capacity;
    size_t data_size;
    size_t size;
    char* data;
} vector;

// Allocate the data structure for the vector
vector* vector_allocate(size_t data_size) {
    vector* result = malloc(sizeof *result);
    if (result) {
        result->data = malloc(data_size);
        result->capacity = 1;
        result->data_size = data_size;
        result->size = 0; 
        if (!result->data)
        {
            free(result);
            result = NULL;
        }
    }
    return result;
}

// Free the memory of the vector, the pointer to the vector is invalid after this
void vector_free(vector* v)
{
    if (v)
    {
        free(v->data);
        v->data = NULL;
        free(v);
    }
}

// Return the element at index, does not do a range check
void* vector_get(vector* v, size_t index) {
    return &(v->data[index * v->data_size]);
}

// Return the element at index, return NULL if index is out of range for the vector
inline void* vector_get_checked(vector* v, size_t index) {
    return (index >= 0 && index < v->size) ? &(v->data[index * v->data_size]) : NULL;
}

// if capacity < new_capacity realloc up to new_capacity
void vector_reserve(vector* v, size_t new_capacity) {
    if (new_capacity <= v->size) return;
    void* new_data = realloc(v->data, new_capacity*v->data_size);
    if (new_data) {
        v->capacity = new_capacity;
        v->data = new_data;
    }
    else {
        abort();
    }
}

// Puts an element data[size * data_size], will reserve more space if size == capacity
void vector_push_back(vector* v, void* data) {
    if (v->size >= v->capacity) {
        size_t new_capacity = (v->capacity > 0) ? (size_t)(v->capacity * 2) : 1;
        vector_reserve(v, new_capacity);
    }
    memcpy(vector_get(v,v->size), data, v->data_size);
    ++v->size;
}

// Here there be tests ... 

void vector_test_alloc_free()
{
    printf("vector_test_alloc_free: ");
    vector* v = vector_allocate(sizeof(int));
    assert(v != NULL);
    assert(v->capacity == 1);
    assert(v->size == 0);
    assert(v->data_size == sizeof(int));
    assert(v->data != NULL);
    printf("OK\n");
    vector_free(v);
}

void vector_test_insert_read_int()
{
    printf("vector_test_insert_read_int: ");
    int val1 = 0xabcdabcd;
    int val2 = 0xeffeeffe;
    vector* v = vector_allocate(sizeof(int));
    vector_push_back(v,&val1);
    assert(v->size == 1);
    assert(v->capacity == 1);
    int* p = vector_get(v, 0);
    assert(*p == val1);
    vector_push_back(v, &val2);
    assert(*p == val1);
    assert(*(p + 1) == val2);

    printf("OK\n");
    vector_free(v);
}

void vector_test_insert_read_struct()
{
    struct data {
        double d;
        int i;
    };

    printf("vector_test_insert_read_struct: ");
    vector* v = vector_allocate(sizeof(struct data));
    struct data d1 = { 0.05, 123 };
    struct data d2 = { -1.9999e10, -9000 };
    vector_push_back(v, &d1);
    vector_push_back(v, &d2);
    struct data* p = vector_get(v, 0);
    assert((*p).d == d1.d); // Bitcopy should be exactly equal
    assert((*p).i == d1.i);
    p = vector_get(v, 1);
    assert((*p).i == d2.i);
    assert((*p).d == d2.d);

    printf("OK\n");
    vector_free(v);
}

void vector_test_safe_get()
{
    printf("vector_test_safe_get:  ");
    vector* v = vector_allocate(sizeof(int));
    int val = 0xff;
    vector_push_back(v, &val);
    vector_push_back(v, &val);

    assert(NULL == vector_get_checked(v, -1));
    assert(NULL == vector_get_checked(v, 2));
    assert(val == *(int*)(vector_get_checked(v, 1)));

    printf("OK\n");
    vector_free(v);
}

void vector_test_reserve()
{
    printf("vector_test_reserve:  ");
    vector* v = vector_allocate(sizeof(int));
    assert(v->capacity == 1);
    vector_reserve(v, 10);
    assert(v->capacity == 10);

    // if we didn't assign the correct space VS will shout about
    // overwriting memory in DEBUG
    int* p = (int*)v->data;
    for (int i = 0; i < 10; ++i)
    {
        *p = i;
        ++p;
    }

    printf("OK\n");
    vector_free(v);
}

int main(int arc, const char* argv[])
{
    vector_test_alloc_free();
    vector_test_insert_read_int();
    vector_test_insert_read_struct();
    vector_test_safe_get();
    vector_test_reserve();
    _CrtDumpMemoryLeaks();
    return 0;
}

Any input is appreciated, especially with regard to colloquial c ...

Answer 1

Allocating the structure along with the data is a design decision which usually makes sense for dynamically linked libraries in which the specific details of the struct might change from one version to the next, I personally dislike this approach when you are compiling the code with the executable because you could just as easily avoid the allocation, it might contribute to memory fragmentation and it's more complicated. So I would use vector_init() and vector_destroy().

int vector_init(vector* v, size_t data_size)
{
    v->data = malloc(data_size);
    v->capacity = 1;
    v->data_size = data_size;
    v->size = 0;

    return v->data != NULL;
}

Setting v->data to NULL is not necessary, but it can help to catch bugs and is very cheap, so that's a good idea.

void vector_destroy(vector* v)
{
    free(v->data);
    v->data = NULL;
}

You don't need the parentheses around v->data[index * v->data_size] because array indexing has higher precedence than &. It's more idiommatic to write &v->data[index * v->data_size];.

// Return the element at index, does not do a range check
void* vector_get(vector* v, size_t index)
{
    return &v->data[index * v->data_size];
}

Using the inline keyword is mostly useless because compilers can usually figure out pretty well when to inline or not. Link-time optimization, on the other hand can reduce code size considerably and produce performance improvements. Also inline works differently in C, I get undefined reference to vector_get_checked when trying to use the function as is. If you really want to keep the inline hint, you should do as follows to ensure a symbol is emitted. Take a look at https://stackoverflow.com/questions/16245521/c99-inline-function-in-c-file/16245669#16245669

inline void* vector_get_checked(vector* v, size_t index);

// Return the element at index, return NULL if index is out of range for the vector
void* vector_get_checked(vector* v, size_t index)
{
    return (index >= 0 && index < v->size) ? &v->data[index * v->data_size] : NULL;
}

There's a bug on the first if, it compares against size instead of capacity. An empty vector will always trigger a realloc even if it has enough capacity already.

// if capacity < new_capacity realloc up to new_capacity
void vector_reserve(vector* v, size_t new_capacity)
{
    if (new_capacity <= v->capacity) return;

    void* new_data = realloc(v->data, new_capacity*v->data_size);
    if (new_data) {
        v->capacity = new_capacity;
        v->data = new_data;
    }
    else {
        abort();
    }
}

v->size shouldn't ever be greater than v->capacity, I would put an assert to catch that and compare for equality only. If you don't need lazy allocation, you can also just set new_capacity = 2 * v->capacity.

// Puts an element data[size * data_size], will reserve more space if size == capacity
void vector_push_back(vector* v, void* data)
{
    assert(v->size <= v->capacity);

    if (v->size == v->capacity) {
        size_t new_capacity = v->capacity * 2;
        vector_reserve(v, new_capacity);
    }

    memcpy(vector_get(v,v->size), data, v->data_size);
    ++v->size;
}

Functions that take no parameters in C should be declared as taking void, leaving it empty is allowed for compatibility with very old programs. https://stackoverflow.com/a/5929736/5285110.

void vector_test_alloc_free(void)
{
    printf("vector_test_alloc_free: ");
    vector v;
    vector_init(&v, sizeof(int));
    assert(v.data != NULL);
    assert(v.capacity == 1);
    assert(v.size == 0);
    assert(v.data_size == sizeof(int));
    assert(v.data != NULL);
    printf("OK\n");
    vector_destroy(&v);
}

void vector_test_insert_read_int(void)
{
    printf("vector_test_insert_read_int: ");
    int val1 = 0xabcdabcd;
    int val2 = 0xeffeeffe;

    vector v;
    vector_init(&v, sizeof(int));
    vector_push_back(&v,&val1);

    assert(v.size == 1);
    assert(v.capacity == 1);

    int* p = vector_get(&v, 0);
    assert(*p == val1);

    // push_back might invalidate previous pointer
    vector_push_back(&v, &val2);
    p = vector_get(&v, 0);
    assert(*p == val1);
    assert(*(p + 1) == val2);

    printf("OK\n");
    vector_destroy(&v);
}

void vector_test_insert_read_struct(void)
{
    struct data {
        double d;
        int i;
    };

    printf("vector_test_insert_read_struct: ");
    vector v;
    vector_init(&v, sizeof(struct data));
    struct data d1 = { 0.05, 123 };
    struct data d2 = { -1.9999e10, -9000 };
    vector_push_back(&v, &d1);
    vector_push_back(&v, &d2);
    struct data* p = vector_get(&v, 0);
    assert((*p).d == d1.d); // Bitcopy should be exactly equal
    assert((*p).i == d1.i);
    p = vector_get(&v, 1);
    assert((*p).i == d2.i);
    assert((*p).d == d2.d);

    printf("OK\n");
    vector_destroy(&v);
}

void vector_test_safe_get(void)
{
    printf("vector_test_safe_get:  ");
    vector v;
    vector_init(&v, sizeof(int));
    int val = 0xff;
    vector_push_back(&v, &val);
    vector_push_back(&v, &val);

    assert(NULL == vector_get_checked(&v, -1));
    assert(NULL == vector_get_checked(&v, 2));
    assert(val == *(int*)(vector_get_checked(&v, 1)));

    printf("OK\n");
    vector_destroy(&v);
}

void vector_test_reserve()
{
    printf("vector_test_reserve:  ");
    vector v;
    vector_init(&v, sizeof(int));
    assert(v.capacity == 1);
    vector_reserve(&v, 10);
    assert(v.capacity == 10);

    // if we didn't assign the correct space VS will shout about
    // overwriting memory in DEBUG
    int* p = (int*)v.data;
    for (int i = 0; i < 10; ++i)
    {
        *p = i;
        ++p;
    }

    printf("OK\n");
    vector_destroy(&v);
}

int main(int arc, const char* argv[])
{
    vector_test_alloc_free();
    vector_test_insert_read_int();
    vector_test_insert_read_struct();
    vector_test_safe_get();
    vector_test_reserve();

    return 0;
}

Answer 2

regarding:

typedef struct {
    size_t capacity;
    size_t data_size;
    size_t size;
    char* data;
} vector;

it is much more flexible to separate the definition of a struct from the typedef for the struct. I.E.

struct sVector {
    size_t capacity;
    size_t data_size;
    size_t size;
    char* data;
};
typedef struct sVector vector;

Strongly suggest checking for errors from system functions where the function is invoked, rather than at some other place in the code. I.E.

vector* result = malloc(sizeof *result);
if( !vector )
{
    perror( "malloc failed" );
    exit( EXIT_FAILURE );
}

// implied else, malloc successful

regarding:

if (v) { free(v->data); v->data = NULL; free(v); }

there is no usefulness to the statement:

v->data = NULL;

the vector struct only allows for one instance of the data. Suggest implementing a linked list instead

The function: abort() will not tell the user why the code failed nor exactly what failed. Suggest using:

perror( "realloc failed" );
// clean up the other allocations before calling `exit()`
exit( EXIT_FAILURE );