Simple C dynamic array library w/ radix sort implementation.

dynamic_array.c

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>

typedef struct {
    void ** data;
    int last;
    int size;
} DArray;

DArray *
darray_init()
{
    DArray *array;

    array = malloc(sizeof(DArray));

    array->last = -1;
    array->size = 16;
    array->data = calloc(array->size, sizeof(void *));

    return array;
}

void
darray_resize(DArray *array, int size)
{
    array->data = realloc(array->data, size * sizeof(void *));
    array->size = size;
}

void *
darray_get(DArray *array, int index)
{
    return array->data[index];
}

void
darray_set(DArray *array, int index, void *value)
{
    int new_size = array->size;

    while (index > (new_size - 1)) {
        new_size *= 2;
    }

    if (new_size != array->size) {
        darray_resize(array, new_size);
    }

    array->data[index] = value;

    if (index > array->last) {
        array->last = index;
    }
}

void
darray_push(DArray *array, void *value)
{
    array->last++;

    if (array->last == array->size) {
        darray_resize(array, array->size * 2);
    }

    array->data[array->last] = value;
}

void *
darray_pop(DArray *array)
{
    void *value;
    value = darray_get(array, array->last);
    darray_set(array, array->last, NULL);
    array->last--;
    return value;
}

DArray *
darray_radix_sort(DArray *array)
{
    DArray *buckets, *bucket;
    int *val, i, j, cur, mask, sortval, sorted;

    buckets = darray_init();

    mask = 1;

    do {
        sorted = 1;

        // reset the buckets
        for (i = 0; i < 10; i++) {
            darray_set(buckets, i, darray_init());
        }

        // sort the values into buckets
        for (i = 0; i <= (array->last); i++) {
            val = darray_get(array, i);
            sortval = (*val / mask) % 10;
            if (sortval > 0) { sorted = 0; }
            darray_push(darray_get(buckets, sortval), val);
        }

        // rebuild array
        cur = 0;

        for (i = 0; i < 10; i++) {
            bucket = darray_get(buckets, i);

           for (j = 0; j <= (bucket->last); j++) {
                darray_set(array,
                           cur++,
                           darray_get(bucket, j));
           }
        }

        mask *= 10;

    } while (!sorted);

    return array;
}

void
test_darray_init()
{
    DArray *array = darray_init();

    assert(array->last == -1);
    assert(array->size == 16);
}

void
test_darray_get_set()
{
    DArray *array = darray_init();

    int *i;
    i = malloc(sizeof(int));
    *i = 1500;

    darray_set(array, 0, i);

    assert(array->last == 0);
    assert(array->size == 16);
    assert(*(int *)darray_get(array, 0) == 1500);
}

void 
test_darray_resize()
{
    DArray *array = darray_init();

    int *i;
    i = malloc(sizeof(int));
    *i = 1500;

    darray_set(array, 50, i);

    assert(array->last == 50);
    assert(array->size == 64);
    assert(*(int *)darray_get(array, 50) == 1500);

    darray_set(array, 100, i);

    assert(array->last == 100);
    assert(array->size == 128);
    assert(*(int *)darray_get(array, 50)  == 1500);
    assert(*(int *)darray_get(array, 100) == 1500);
}

void
test_darray_push_pop()
{
    DArray *array = darray_init();
    int *i, j;

    for (j = 0; j < 16; j++) {
        i = malloc(sizeof(int));
        *i = j;
        darray_push(array, i);
    }

    assert(array->last == 15);
    assert(array->size == 16);
    assert(*(int *)darray_get(array, 0)  == 0);
    assert(*(int *)darray_get(array, 15) == 15);

    i = malloc(sizeof(int));
    *i = 16;
    darray_push(array, i);

    assert(array->last == 16);
    assert(array->size == 32);
    assert(*(int *)darray_get(array, 0)  == 0);
    assert(*(int *)darray_get(array, 15) == 15);
    assert(*(int *)darray_get(array, 16) == 16);

    assert(*(int *)darray_pop(array) == 16);
    assert(darray_get(array, 16) == NULL);
    assert(array->last == 15);
    assert(array->size == 32);
}

void
test_darray_radix_sort()
{
    srand(time(NULL));

    DArray *array;
    int *i, j, v1, v2;

    array = darray_init();

    for (j = 0; j < 10; j++) {
        i = malloc(sizeof(int));
        *i = rand() % 1000;
        darray_push(array, i);
    }

    /*
    printf("UNSORTED: ");

    for (j = 0; j < 10; j++) {
        printf("%d ", *(int *)darray_get(array, j));    
    } 

    printf("\n");
    */

    darray_radix_sort(array);

    /*
    printf("SORTED:   ");

    for (j = 0; j < 10; j++) {
        printf("%d ", *(int *)darray_get(array, j));    
    } 

    printf("\n");
    */

    for (j = 0; j < 9; j++) {
        v1 = *(int *)darray_get(array, j);
        v2 = *(int *)darray_get(array, j + 1);

        assert(v1 <= v2);
    }
}

int
main()
{
    test_darray_init();

    test_darray_get_set();

    test_darray_resize();

    test_darray_push_pop();

    test_darray_radix_sort();

    return 1;
}

Makefile

CFLAGS=-g -Wall -Wextra

all: dynamic_array

clean:
    rm -rf dynamic_array *.dSYM