Simple vector implementation in C

README.md

See Acutal Git Repo here:

#C Vector

My personal implementation of the c++ vector in C. I do not guarentee speed, stability or even usability. Sorry.

Please adhere to all license restrictions listed in the main directory.

#Build instructions

See the RunTests.sh to test to see if the vector implementation is functional.

sh RunTests.sh

To link with your own files include the header

#include "vector.h"
~C code beneath~

in your function, then build/link it as such.

gcc -c -(CFLAGS) vector.c -o vector.o
gcc -(CFLAGS) yourfunc.c vector.o -o yourfunc
rm *.o

#TODO

• Figure out how to implement vector_die with concurrency

vector.c

#include <stdlib.h>
#include <stdio.h>
#include "vector.h"

/*
 * Initializes vector field.  
 * Starts with INIT_CAPACITY (8). I do this because I wanted the initial
 * capacity to be a power of 2 as the growth polcy grows/shrinks by 2. 16 was
 * too many, whereas 8 was better.  
 * Can crash program if Out of Memory.
 */
void vector_init(vector *vec)
{
    vec->size = 0;
    vec->capacity = INIT_CAPACITY;
    vec->elems = malloc((vec->capacity)*sizeof(void *));
    if (!vec->elems)
    {
        vector_die(0);
    }
}

/*
 * Frees underlying array structure
 * Note if the vector struct was intialized onto the heap, that must be freed
 * too.
 */
void vector_free(vector *vec)
{
    free(vec->elems);
    vec->capacity = 0;
    vec->size = 0;
}

/*
 * Growth Policy handling
 * If the current size is equal to the capacity, grow capacity by a factor of
 * 2.
 * If the current size is 4 times less than or equal to the capacity, shrink
 * capacity by  a factor of 2.
 * Can crash program with Out of Memory error.
 */
static void growth_policy(vector *vec)
{
    if (vec->capacity == vec->size)
    {
        vector_grow(vec, 2*(vec->capacity));
    }
    if (vec->size > 0 && vec->size*4 <= vec->capacity)
    {
        vector_grow(vec, (vec->capacity)/2);
    }
}

/*
 * Called by growth_policy()
 * Can crash program with Out of Memory error
 */
static void vector_grow(vector *vec, int new_size)
{
    void **elems = realloc(vec->elems, new_size * sizeof(void *));
    if (elems)
    {
        vec->capacity = new_size;
        vec->elems = elems;
    }
    else
    {
        vector_die(0);
    }
}

/*
 * Appends an element to the end of the array.
 * Complexity: Amortized O(1) | O(n)
 * May grow array size.
 */
void vector_add(vector *vec, void *new_elem)
{
    growth_policy(vec); 
    vec->elems[vec->size++] = new_elem;
}

/*
 * Sets element within the vector at given index to the value of new_elem.
 * Complexity: O(1)
 * Program may crash if index is out of bounds.
 */
void vector_set(vector *vec, int ind, void *new_elem)
{
    if (ind >= vec->size || ind < 0)
    {
        vector_die(1);
    }
    vec->elems[ind] = new_elem;
}

/*
 * Returns element within vector at given index.
 * Complexity: O(1)
 * Program may crash if index is out of bounds.
 */
void *vector_get(vector *vec, int ind)
{
    if (ind >= vec->size || ind < 0)
    {
        vector_die(1);
    }
    return vec->elems[ind];
}

/*
 * Removes and returns last element within vector.
 * Complexity: Amortized O(1) | O(n)
 * Can throw both Out of memory and index out of bounds errors.
 */
void *vector_pop(vector *vec)
{
    return vector_delete(vec, vec->size-1);
}

/*
 * Removes and returns element at given index within vector.
 * Complexity: Amortized O(1) | O(n)
 * Can throw both Out of memory and index out of bounds errors.
 */
void *vector_delete(vector *vec, int ind)
{
    if (ind < 0 || ind >= vec->size)
    {
        vector_die(1);
    }
    void *ret = vec->elems[ind];
    vec->elems[ind] = NULL;

    int i;
    for (i = ind; i< vec->size; i++)
    {
        vec->elems[i] = vec->elems[i+1];
        vec->elems[i+1] = NULL;
    }
    vec->size--;
    growth_policy(vec);
    return ret;
}

/*
 * HERE BE DRAGONS!!
 * Sorts the vector using stdlib qsort. Works only for numeric types.
 * Complexity: O(nlog(n))
 * See C reference for qsort implementation.
 */
void vector_sort(vector *vec)
{
    qsort(vec->elems, vector_size(vec), sizeof(vec->elems[0]), cmpfunc);
}

static int cmpfunc (const void *a, const void *b)
{
    if (*(const double*)a < *(const double*)b)
        return -1;
    if (*(const double*)a > *(const double*)b)
        return 1;
    return 0;
}

/*
 * Returns first element within vector.
 * Complexity: O(1)
 * Can throw out of index error if size is 0.
 */
void *vector_front(vector *vec)
{
    if (vec->size == 0)
    {
        vector_die(1);
    }
    return vec->elems[0];
}

/*
 * Returns last element within vector
 * Complexity: O(1)
 * Can throw out of index error if size is 0.
 */
void *vector_back(vector *vec)
{
    if (vec->size == 0)
    {
        vector_die(1);
    }
    return vec->elems[vec->size-1];
}

/*
 * Returns underlying void array containing elements.
 * Complexity: O(n)
 * The array is allocated on the heap, so it must be freed after usage is done.
 */
void **vector_data(vector *vec)
{
    void **arr = malloc(vec->size * sizeof(void *));
    int i;
    for (i = 0; i < vec->size; i++)
    {
        arr[i] = vec->elems[i];
    }
    return arr;
}

/*
 * Returns capacity of array
 * Complexity: O(1)
 */
int vector_capacity(vector *vec)
{
    return vec->capacity;
}

/*
 * Returns size of array
 * Complexity: O(1)
 */
int vector_size(vector *vec)
{
    return vec->size;
}

/*
 * Returns 1 if size is zero, otherwise zero.
 * Complexity: O(1)
 */
int vector_empty(vector *vec)
{
    return (vec->size == 0);
}

/*
 * Oh shit.
 * Exits the process after printing information regarding the crash.
 * Case 0: Out of memory
 * Case 1: Indexing error
 * ...
 * TODO:
 * Does this not end properly with concurrency?
 */
void vector_die(int error)
{
    switch(error)
    {
        case 0:
            printf("vector_die:\nOut of memory. Aborting.\n");
            break;
        case 1:
            printf("vector_die:\nIndexing error. Aborting.\n");
            break;
    }
    exit(1);
}

vector.h

#ifndef vector_h
#define vector_h

//Becausce C# and Java had a reason to
#define INIT_CAPACITY 10

typedef struct vector
{
    void **elems;
    int capacity;
    int size;
} vector;

//Constructor / Destructor
void vector_init(vector *);
void vector_free(vector *);

//Modifiers
void vector_add(vector *, void *);
void vector_set(vector *, int, void *);
void *vector_get(vector *, int);
void *vector_pop(vector *);
void *vector_delete(vector *, int);
void vector_sort(vector *);
static int cmpfunc (const void *, const void *);

//Element Access
void *vector_front(vector *);
void *vector_back(vector *);
void **vector_data(vector *);

//Capacity
int vector_capacity(vector *);
int vector_size(vector *);
int vector_empty(vector *);

//Growth policy
static void vector_grow(vector *, int);
static void growth_policy(vector *);

//Error Handling
void vector_die(int);

#endif