X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Frasterize;a=blobdiff_plain;f=array.h;fp=array.h;h=d8c192ba9b2301e4666ce73a40449ebc29fe2f7a;hp=0000000000000000000000000000000000000000;hb=a3ba0121189f38132480b0c0c4be96df3c93900b;hpb=143da66e7f625b7f195a115b9740a748ee003534

diff --git a/array.h b/array.h
new file mode 100644
index 0000000..d8c192b
--- /dev/null
+++ b/array.h
@@ -0,0 +1,352 @@
+
+/*
+ * 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_
+