--- /dev/null
+
+/*
+ * CS5600 University of Utah
+ * Charles McGarvey
+ * mcgarvey@eng.utah.edu
+ */
+
+#ifndef _ARRAY_H_
+#define _ARRAY_H_
+
+#include "assert.h"
+#include "common.h"
+
+
+#define ARRAY_CAPACITY_DEFAULT (128)
+#define ARRAY_CAPACITY_MIN (4)
+
+
+/*
+ * A random-access dynamically-expandable array class.
+ */
+struct array
+{
+ void* arr;
+ size_t cap;
+ size_t len;
+ size_t siz;
+};
+typedef struct array array_t;
+
+/*
+ * Allocate a new array with the element size and initial capacity.
+ */
+array_t* array_alloc2(size_t size, size_t capacity);
+
+/*
+ * Allocate a new array with the element size.
+ */
+INLINE_MAYBE
+array_t* array_alloc(size_t size)
+{
+ return array_alloc2(size, ARRAY_CAPACITY_DEFAULT);
+}
+
+#define array_alloc_type(T) array_alloc(sizeof(T))
+#define array_alloc_type2(T, C) array_alloc2(sizeof(T), C)
+
+/*
+ * Destroy an array, freeing up its memory.
+ */
+INLINE_MAYBE
+void array_destroy(array_t* v)
+{
+ assert(v && v->arr);
+ mem_free(v->arr);
+ mem_free(v);
+}
+
+
+/*
+ * An iterator class for the array.
+ */
+struct array_it
+{
+ const array_t* arr;
+ size_t pos;
+ int dir;
+};
+typedef struct array_it array_it_t;
+
+/*
+ * Initialize an array iterator.
+ */
+INLINE_MAYBE
+void array_it_init(array_it_t* it, const array_t* v, size_t position, int direction)
+{
+ assert(it);
+ it->arr = v;
+ it->pos = position;
+ it->dir = direction;
+}
+
+
+/*
+ * Index into a random position into the array.
+ */
+INLINE_MAYBE
+void* array_index(const array_t* v, size_t i)
+{
+ assert(v && v->arr);
+ return (char*)v->arr + i * v->siz;
+}
+
+/*
+ * Get the first item in the array.
+ */
+INLINE_MAYBE
+void* array_front(const array_t* v)
+{
+ return array_index(v, 0);
+}
+
+/*
+ * Get the last item in the array.
+ */
+INLINE_MAYBE
+void* array_back(const array_t* v)
+{
+ return array_index(v, v->len - 1);
+}
+
+
+/*
+ * Get a forward iterator at the first item in the array.
+ */
+INLINE_MAYBE
+array_it_t array_begin(const array_t* v)
+{
+ assert(v && v->arr);
+ array_it_t it;
+ array_it_init(&it, v, 0, 1);
+ return it;
+}
+
+/*
+ * Get a forward iterator after the last item in the array.
+ */
+INLINE_MAYBE
+array_it_t array_end(const array_t* v)
+{
+ assert(v && v->arr);
+ array_it_t it;
+ array_it_init(&it, v, v->len, 1);
+ return it;
+}
+
+/*
+ * Get a backward iterator at the last item in the array.
+ */
+INLINE_MAYBE
+array_it_t array_rbegin(const array_t* v)
+{
+ assert(v && v->arr);
+ array_it_t it;
+ array_it_init(&it, v, v->len - 1, -1);
+ return it;
+}
+
+/*
+ * Get a backward iterator before the first item in the array.
+ */
+INLINE_MAYBE
+array_it_t array_rend(const array_t* v)
+{
+ assert(v && v->arr);
+ array_it_t it;
+ array_it_init(&it, v, -1, -1);
+ return it;
+}
+
+
+/*
+ * Get the current capacity of the array. The capacity is how many elements
+ * could be inserted into the array without reallocating more memory.
+ */
+INLINE_MAYBE
+size_t array_capacity(const array_t* v)
+{
+ assert(v && v->arr);
+ return v->cap;
+}
+
+/*
+ * Make sure there is at least enough memory for a certain number of elements.
+ */
+void array_reserve(array_t* v, size_t s);
+
+/*
+ * Shrink the amount of memory used to fit what is currently inserted into the
+ * array and no more. Of course more memory can be reallocated later.
+ */
+void array_done(array_t* v);
+
+
+/*
+ * Get the current number of items in the array. This is less than or equal
+ * to the capacity of the array.
+ */
+INLINE_MAYBE
+size_t array_size(const array_t* v)
+{
+ assert(v && v->arr);
+ return v->len;
+}
+
+/*
+ * Get whether or not the array is empty.
+ */
+INLINE_MAYBE
+bool array_empty(const array_t* v)
+{
+ return array_size(v) == 0;
+}
+
+/*
+ * Resize the array, either truncating or expanding the size.
+ */
+INLINE_MAYBE
+void array_resize(array_t* v, size_t s)
+{
+ array_reserve(v, s);
+ v->len = s;
+}
+
+/*
+ * Remove all items from the array.
+ */
+INLINE_MAYBE
+void array_clear(array_t* v)
+{
+ assert(v && v->arr);
+ v->len = 0;
+}
+
+
+/*
+ * Push an item onto the end of the array.
+ */
+INLINE_MAYBE
+void array_push(array_t* v, void* e)
+{
+ assert(v && v->arr);
+ size_t len = v->len + 1;
+ if (v->cap < len) {
+ array_reserve(v, len);
+ }
+ memcpy(array_index(v, v->len), e, v->siz);
+ v->len = len;
+}
+
+
+/*
+ * Pop the item off of the end of the array. The item is returned, but its
+ * memory could be overwritten with addition array calls, so it must be copied
+ * if it needs to be kept.
+ */
+INLINE_MAYBE
+void* array_pop(array_t* v)
+{
+ assert(v && v->arr);
+ return array_index(v, --v->len);
+}
+
+
+/*
+ * The type of function used when calling elements of the array.
+ */
+typedef void (*array_call_fn_t)(size_t i, void* e);
+
+/*
+ * Call a function once for each element of the array.
+ */
+void array_call(const array_t* v, array_call_fn_t fn);
+
+
+/*
+ * Get the element pointed to by an iterator and increment the iterator.
+ */
+INLINE_MAYBE
+void* array_it_next(array_it_t* it)
+{
+ assert(it->arr);
+ if (it->pos < it->arr->len) {
+ void* e = array_index(it->arr, it->pos);
+ it->pos += it->dir;
+ return e;
+ }
+ return NULL;
+}
+
+/*
+ * Decrement the iterator and get the element pointed to by the iterator.
+ */
+INLINE_MAYBE
+void* array_it_prev(array_it_t* it)
+{
+ assert(it->arr);
+ if (it->pos - it->dir < it->arr->len) {
+ it->pos -= it->dir;
+ void* e = array_index(it->arr, it->pos);
+ return e;
+ }
+ return NULL;
+}
+
+
+#define DEFINE_ARRAY_TYPE(T) DEFINE_ARRAY_TYPE2(T##_t, T)
+#define DEFINE_ARRAY_TYPE2(T, N) \
+INLINE_MAYBE array_t* array_##N##_alloc() \
+{ \
+ return array_alloc(sizeof(T)); \
+} \
+INLINE_MAYBE array_t* array_##N##_alloc2(size_t capacity) \
+{ \
+ return array_alloc2(sizeof(T), capacity); \
+} \
+INLINE_MAYBE T* array_##N##_index(const array_t* v, size_t i) \
+{ \
+ return (T*)array_index(v, i); \
+} \
+INLINE_MAYBE T* array_##N##_front(array_t* v) \
+{ \
+ return (T*)array_front(v); \
+} \
+INLINE_MAYBE T* array_##N##_back(array_t* v) \
+{ \
+ return (T*)array_back(v); \
+} \
+INLINE_MAYBE void array_##N##_push(array_t* v, T e) \
+{ \
+ assert(v && v->arr); \
+ size_t len = v->len + 1; \
+ if (v->cap < len) { \
+ array_reserve(v, len); \
+ } \
+ T* t = array_##N##_back(v); \
+ *(t + 1) = e; \
+ /* specialize with assignment copying rather than memcpy */ \
+ v->len = len; \
+} \
+INLINE_MAYBE T* array_##N##_pop(array_t* v) \
+{ \
+ return (T*)array_pop(v); \
+} \
+typedef void (*array_##N##_call_fn_t)(size_t i, T* e); \
+INLINE_MAYBE void \
+array_##N##_call(array_t* v, array_##N##_call_fn_t fn) \
+{ \
+ array_call(v, (array_call_fn_t)fn); \
+} \
+INLINE_MAYBE T* array_it_##N##_next(array_it_t* it) \
+{ \
+ return (T*)array_it_next(it); \
+} \
+INLINE_MAYBE T* array_it_##N##_prev(array_it_t* it) \
+{ \
+ return (T*)array_it_prev(it); \
+}
+
+
+#endif // _ARRAY_H_
+