Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.