Dynamic Array

.gitignore

*.o
main
*.dSYM

array.c

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>

#include "array.h"

void    array_move_elements(Array *old, Array *new, int first, int last);
void    array_free(Array *array);
void    array_expand(Array *array);
void    _array_push(Array *array, void *element);
int     array_split(Array *array, Array **left, Array **right);
Array * array_merge(Array *left, Array *right, e_cmp_cb compare);

Array *
array_create(int element_type, int alloc_increment)
{
    Array *array = malloc(sizeof(Array)); // TODO: malloc() errors

    array->element_type    = element_type;
    array->elements        = NULL;
    array->size            = 0;
    array->alloc_size      = alloc_increment;
    array->alloc_increment = alloc_increment;

    array->elements = calloc(array->alloc_size, sizeof(void *));

    return array;
}

void
array_push(Array *array, ...)
{
    va_list  arg_p;
    void    *element = NULL;

    va_start(arg_p, array);

    if (array->element_type == ELEMENT_TYPE_INT) {
        int *value = malloc(sizeof(int));
        *value = va_arg(arg_p, int);

        element = value;
    } else {
        element = va_arg(arg_p, void *);
    }

    va_end(arg_p);
    _array_push(array, element);
}

void *
array_pop(Array *array)
{
    int  index = array->size - 1;
    void *element = NULL;

    if (index >= 0) {
        element = array->elements[index];
        array->size--;
    }

    return element;
}

void *
array_get(Array *array, int index)
{
    void *element = NULL;

    if (index >= 0 && index <= (array->size - 1)) {
        element = array->elements[index];
    }

    return element;
}

void *
array_first(Array *array)
{
    return array_get(array, 0);
}

void *
array_last(Array *array)
{
    return array_get(array, (array->size - 1));
}

// 2 removal strategies:
//   *         array_remove: remove specified element and shift others down
//   * array_remove_replace: alloc a new array that's the same size and copy all

void *
array_remove(Array *array, int index)
{
    void *element   = NULL;
    int  next_index = 0;

    if (index >= 0 && index <= (array->size - 1)) {
        element = array->elements[index];

        for (next_index = index + 1; next_index < array->size; next_index++) {
            array->elements[next_index - 1] = array->elements[next_index];
        }

        array->size--;
    }

    return element;
}

Array *
array_remove_replace(Array *array, int index, void **element)
{
    Array *new_array = array;

    if (index >= 0 && index <= (array->size - 1)) {
        new_array = array_create(array->element_type, array->alloc_increment);

        *element = array->elements[index];

        array_move_elements(array, new_array, 0, (index - 1));
        array_move_elements(array, new_array, (index + 1), (array->size - 1));

        array_free(array);
    }

    return new_array;
}

void
array_destroy(Array *array, e_free_cb free)
{
    int i = 0;

    for (i = 0; i < array->size; i++) {
        free(array->elements[i]);
    }

    array_free(array);
}

void
array_sort_bubble(Array *array, e_cmp_cb compare)
{
    int swapped = 0,
        cur     = 0,
        next    = 0;

    void *tmp;

    do {
        swapped = 0;

        for (cur = 0; cur < (array->size - 1); cur++) {
            next = cur + 1;
            if (compare(array->elements[cur], array->elements[next]) == 1) {
                tmp = array->elements[next];

                array->elements[next] = array->elements[cur];
                array->elements[cur]  = tmp;

                swapped = 1;
            }
        }
    } while (swapped);
}

Array *
array_sort_merge(Array *array, e_cmp_cb compare)
{
    int   split;
    Array *left, *right, *new;

    split = array_split(array, &left, &right);

    if (split) {
        left  = array_sort_merge(left, compare);
        right = array_sort_merge(right, compare);

        new = array_merge(left, right, compare);
        array_free(array);

        array = new;
    }

    return array;
}

void
array_print(Array *array, e_print_cb print)
{
    int i = 0;

    if (array->size == 0) {
        printf("Array is empty.\n");
    } else {
        printf("Array contains %d elements:\n", array->size);

        printf("  [");

        for (i = 0; i < array->size; i++) {
            if (i != 0) { printf(", "); }
            print(array->elements[i]);
        }

        printf("]\n");
    }
}

void
array_move_elements(Array *old, Array *new, int start, int end)
{
    int i = start;

    for (; i <= end; i++) {
        _array_push(new, old->elements[i]);
    }
}

void
array_free(Array *array)
{
    free(array->elements);
    free(array);
}

void
array_expand(Array *array)
{
    int new_size = array->alloc_size + array->alloc_increment;

    array->elements = realloc(array->elements, new_size * sizeof(void *));
    array->alloc_size = new_size;
}

void
_array_push(Array *array, void *element)
{
    if (array->size == array->alloc_size) {
        array_expand(array);
    }

    array->elements[array->size] = element;
    array->size++;
}

int
array_split(Array *array, Array **left, Array **right)
{
    if (array->size == 1) { return 0; }

    int i, left_size = array->size / 2;

    *left  = array_create(array->element_type, left_size);
    *right = array_create(array->element_type, array->size - left_size);

    for (i = 0; i < left_size; i++) {
        _array_push(*left, array->elements[i]);
    }

    for (i = left_size; i < array->size; i++) {
        _array_push(*right, array->elements[i]);
    }

    return 1;
}

Array *
array_merge(Array *left, Array *right, e_cmp_cb compare)
{
    int i, cmp,
        r_index = 0,
        l_index = 0;

    Array *array = array_create(left->element_type, left->size + right->size);

    while (r_index < right->size && l_index < left->size) {
        cmp = compare(left->elements[l_index], right->elements[r_index]);

        if (cmp == 1) {
            _array_push(array, right->elements[r_index]);
            r_index++;
        } else if (cmp == -1) {
            _array_push(array, left->elements[l_index]);
            l_index++;
        } else {
            _array_push(array, right->elements[r_index]);
            _array_push(array, left->elements[l_index]);

            l_index++;
            r_index++;
        }
    }

    for (i = l_index; i < left->size; i++)  {
        _array_push(array, left->elements[i]);
    }

    for (i = r_index; i < right->size; i++) {
        _array_push(array, right->elements[i]);
    }

    array_free(left);
    array_free(right);

    return array;
}

array.h

#ifndef _ARRAY_H
#define _ARRAY_H

// Can I do this with enum instead?
#define ELEMENT_TYPE_INT   1
#define ELEMENT_TYPE_OTHER 2

typedef struct Array {
    int  element_type;
    void **elements;
    int  size;
    int  alloc_size;
    int  alloc_increment;
} Array;

typedef void (*e_print_cb)(void *e);
typedef void (*e_free_cb)(void *e);
typedef int  (*e_cmp_cb)(void *a, void *b);

Array * array_create(int element_type, int alloc_size);
void    array_push(Array *array, ...);
void  * array_pop(Array *array);
void  * array_get(Array *array, int index);
void  * array_first(Array *array);
void  * array_last(Array *array);
void  * array_remove(Array *array, int index);
Array * array_remove_replace(Array *array, int index, void **element);
void    array_sort_bubble(Array *array, e_cmp_cb compare);
Array * array_sort_merge(Array *array, e_cmp_cb compare);
void    array_print(Array *array, e_print_cb print);
void    array_destroy(Array *array, e_free_cb free);
void    array_free(Array *array);

#endif

main.c

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

#include "array.h"

#define ARRAY_ALLOC_SIZE 7

// Example struct

typedef struct Map {
    char *name;
    int value;
} Map;

Map *map_create(const char *name, int value)
{
    Map *map = malloc(sizeof(Map));

    map->name  = strdup(name);
    map->value = value;

    return map;
}

void map_free(Map *map)
{
    if (map->name) { free(map->name); }
    free(map);
}

// Print callbacks
void
element_integer_print(void *element)
{
    printf("%d", *(int *)element);
}

void
element_map_print(void *element)
{
    Map *map = (Map *)element;

    printf("'%s': %d", map->name, map->value);
}

// Free callbacks
void
element_map_free(void *element)
{
    map_free((Map *)element);
}

void
element_integer_free(void *element)
{
    free(element);
}

// Compare callbacks

int
element_integer_compare(void *a, void *b)
{
    int result = 0,
        first  = *(int *)a,
        second = *(int *)b;

    if (first < second) {
        result = -1;
    } else if (first > second) {
        result = 1;
    }

    return result;
}

int
element_map_compare(void *a, void *b)
{
    int result  = 0;
    Map *first  = (Map *)a,
        *second = (Map *)b;

    if (first->value < second->value){
        result = -1;
    } else if (first->value > second->value){
        result = 1;
    }

    return result;
}

void test_int_array();
void test_int_array_bubble_sort();
void test_int_array_merge_sort();
void test_map_array();
void test_map_array_bubble_sort();
void test_map_array_merge_sort();

int
main(void)
{
    printf("Integer Array:\n\n");
    test_int_array();
    printf("\n");

    printf("Bubble sorting: \n\n");
    test_int_array_bubble_sort();
    printf("\n");

    printf("Merge sorting: \n\n");
    test_int_array_merge_sort();
    printf("\n");

    printf("Map Array:\n\n");
    test_map_array();
    printf("\n");

    printf("Bubble sorting: \n\n");
    test_map_array_bubble_sort();
    printf("\n");

    printf("Merge sorting: \n\n");
    test_map_array_merge_sort();
    printf("\n");

    return 0;
}

void
test_int_array()
{
    int    i        = 0,
           position = 0;

    Array *array = array_create(ELEMENT_TYPE_INT, ARRAY_ALLOC_SIZE);
    void  *element;

    for (i = 20; i > 0; i--) {
        array_push(array, i);
    }

    printf("First element is: ");
    element_integer_print(array_first(array));
    printf("\n");

    printf("Last element is: ");
    element_integer_print(array_last(array));
    printf("\n");

    position = 5;
    printf("Element at index #%d is: ", position);
    element_integer_print(array_get(array, position));
    printf("\n");

    array_print(array, element_integer_print);

    printf("Removing (shift) element at index %d\n", position);
    element = array_remove(array, position);

    printf("Value was: ");
    element_integer_print(element);
    printf("\n");

    element_integer_free(element);

    array_print(array, element_integer_print);

    printf("Removing (replace) element at index %d\n", position);
    array = array_remove_replace(array, position, &element);

    printf("Value was: ");
    element_integer_print(element);
    printf("\n");

    element_integer_free(element);

    array_print(array, element_integer_print);

    while (array->size > 0) {
        printf("Removed element:");
        element = array_pop(array);

        element_integer_print(element);
        printf("\n");

        element_integer_free(element);
    }

    array_print(array, element_integer_print);

    array_destroy(array, element_integer_free);
}

void
test_int_array_bubble_sort()
{
    int i = 0;

    Array *array = array_create(ELEMENT_TYPE_INT, ARRAY_ALLOC_SIZE);

    for (i = 10; i > 0; i--) {
        array_push(array, i);
    }

    array_print(array, element_integer_print);
    array_sort_bubble(array, element_integer_compare);
    array_print(array, element_integer_print);

    for (i = 20; i > 10; i--) {
        array_push(array, i);
    }

    array_print(array, element_integer_print);
    array_sort_bubble(array, element_integer_compare);
    array_print(array, element_integer_print);

    array_destroy(array, element_integer_free);
}

void
test_int_array_merge_sort()
{
    Array *array = array_create(ELEMENT_TYPE_INT, ARRAY_ALLOC_SIZE);

    array_push(array, 3);
    array_push(array, 1);
    array_push(array, 5);
    array_push(array, 4);
    array_push(array, 10);
    array_push(array, 1);
    array_push(array, 16);

    array_print(array, element_integer_print);

    array = array_sort_merge(array, element_integer_compare);
    array_print(array, element_integer_print);

    array_destroy(array, element_integer_free);
}

void
test_map_array()
{
    int position = 0;

    Array *array = array_create(ELEMENT_TYPE_OTHER, ARRAY_ALLOC_SIZE);
    void  *element;

    array_push(array, map_create("Ten",  10));
    array_push(array, map_create("Nine",  9));
    array_push(array, map_create("Eight", 8));
    array_push(array, map_create("Seven", 7));
    array_push(array, map_create("Six",   6));
    array_push(array, map_create("Five",  5));
    array_push(array, map_create("Four",  4));
    array_push(array, map_create("Three", 3));
    array_push(array, map_create("Two",   2));
    array_push(array, map_create("One",   1));

    printf("First element is: ");
    element_map_print(array_first(array));
    printf("\n");

    printf("Last element is: ");
    element_map_print(array_last(array));
    printf("\n");

    position = 5;
    printf("Element at index #%d is: ", position);
    element_map_print(array_get(array, position));
    printf("\n");

    array_print(array, element_map_print);

    printf("Removing (shift) element at index %d\n", position);
    element = array_remove(array, position);

    printf("Value was: ");
    element_map_print(element);
    printf("\n");

    element_map_free(element);

    array_print(array, element_map_print);

    printf("Removing (replace) element at index %d\n", position);
    array = array_remove_replace(array, position, &element);

    printf("Value was: ");
    element_map_print(element);
    printf("\n");

    element_map_free(element);

    while (array->size > 0) {
        printf("Removed element:");
        element = array_pop(array);

        element_map_print(element);
        printf("\n");

        element_map_free(element);
    }

    array_print(array, element_map_print);

    array_destroy(array, element_map_free);
}

void
test_map_array_bubble_sort()
{
    Array *array = array_create(ELEMENT_TYPE_OTHER, ARRAY_ALLOC_SIZE);

    array_push(array, map_create("Ten",  10));
    array_push(array, map_create("Nine",  9));
    array_push(array, map_create("Eight", 8));
    array_push(array, map_create("Seven", 7));
    array_push(array, map_create("Six",   6));

    array_print(array, element_map_print);
    array_sort_bubble(array, element_map_compare);
    array_print(array, element_map_print);

    array_push(array, map_create("Five",  5));
    array_push(array, map_create("Four",  4));
    array_push(array, map_create("Three", 3));
    array_push(array, map_create("Two",   2));
    array_push(array, map_create("One",   1));

    array_print(array, element_map_print);
    array_sort_bubble(array, element_map_compare);
    array_print(array, element_map_print);

    array_destroy(array, element_map_free);
}

void
test_map_array_merge_sort()
{
    Array *array = array_create(ELEMENT_TYPE_OTHER, ARRAY_ALLOC_SIZE);

    array_push(array, map_create("Ten",  10));
    array_push(array, map_create("Nine",  9));
    array_push(array, map_create("Eight", 8));
    array_push(array, map_create("Seven", 7));
    array_push(array, map_create("Six",   6));

    array_print(array, element_map_print);
    array = array_sort_merge(array, element_map_compare);
    array_print(array, element_map_print);

    array_push(array, map_create("Five",  5));
    array_push(array, map_create("Four",  4));
    array_push(array, map_create("Three", 3));
    array_push(array, map_create("Two",   2));
    array_push(array, map_create("One",   1));

    array_print(array, element_map_print);
    array = array_sort_merge(array, element_map_compare);
    array_print(array, element_map_print);

    array_destroy(array, element_map_free);
}

Makefile

CFLAGS=-g -Wall -Wextra

all: main

main: array.o

clean:
	rm -rf *.o main *.dSYM