From 5ffbc4ada491f7cafc885db873fee873ca13bdb7 Mon Sep 17 00:00:00 2001
From: "Michael D. Lowis" <mike@mdlowis.com>
Date: Sun, 5 Jul 2015 23:57:14 -0400
Subject: [PATCH] Initial implementation of vector

---
 source/data/vec.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++
 source/data/vec.h |  46 ++++++++++++++++++
 2 files changed, 163 insertions(+)
 create mode 100644 source/data/vec.c
 create mode 100644 source/data/vec.h

diff --git a/source/data/vec.c b/source/data/vec.c
new file mode 100644
index 0000000..1f27352
--- /dev/null
+++ b/source/data/vec.c
@@ -0,0 +1,117 @@
+/**
+  @file vec.c
+*/
+#include <data/vec.h>
+
+#ifndef DEFAULT_VEC_CAPACITY
+#define DEFAULT_VEC_CAPACITY (size_t)8
+#endif
+
+void vec_init(vec_t* vec, size_t elem_size)
+{
+    vec->elem_size     = elem_size;
+    vec->elem_count    = 0;
+    vec->elem_capacity = DEFAULT_VEC_CAPACITY;
+    vec->elem_buffer   = malloc(elem_size * vec->elem_capacity);
+}
+
+size_t vec_size(vec_t* vec)
+{
+    return vec->elem_count;
+}
+
+bool vec_empty(vec_t* vec)
+{
+    return (vec->elem_count == 0);
+}
+
+size_t vec_capacity(vec_t* vec)
+{
+    return vec->elem_capacity;
+}
+
+void vec_resize(vec_t* vec, size_t count, void* fillval)
+{
+    if (count > vec->elem_count)
+    {
+        vec_reserve(vec, vec_next_capacity(count+1));
+        for (; vec->elem_count < count; vec->elem_count++)
+            memcpy(&(vec->elem_buffer[vec->elem_count * vec->elem_size]), fillval, vec->elem_size);
+    }
+    else if (count < vec->elem_count)
+    {
+        vec->elem_count = count;
+    }
+}
+
+size_t vec_next_capacity(size_t req_size)
+{
+    size_t next_power = req_size;
+    size_t num_bits = sizeof(size_t) * 8;
+    size_t bit_n;
+
+    /* Find the next highest power of 2 */
+    next_power--;
+    for (bit_n = 1; bit_n < num_bits; bit_n = bit_n << 1)
+    {
+        next_power = next_power | (next_power >> bit_n);
+    }
+    next_power++;
+
+    return next_power;
+}
+
+void vec_shrink_to_fit(vec_t* vec)
+{
+    vec->elem_buffer   = realloc(vec->elem_buffer, vec->elem_count * vec->elem_size);
+    vec->elem_capacity = vec->elem_count;
+}
+
+void vec_reserve(vec_t* vec, size_t size)
+{
+    vec->elem_buffer = realloc(vec->elem_buffer, size * vec->elem_size);
+    vec->elem_count  = size;
+}
+
+void* vec_at(vec_t* vec, size_t index)
+{
+    return &(vec->elem_buffer[index * vec->elem_size]);
+}
+
+void vec_set(vec_t* vec, size_t index, void* data)
+{
+    memcpy(&(vec->elem_buffer[index * vec->elem_size]), data, vec->elem_size);
+}
+
+bool vec_insert(vec_t* vec, size_t index, size_t num_elements, ...)
+{
+    (void)vec;
+    (void)index;
+    (void)num_elements;
+    return false;
+}
+
+bool vec_erase(vec_t* vec, size_t start_idx, size_t end_idx)
+{
+    (void)vec;
+    (void)start_idx;
+    (void)end_idx;
+    return false;
+}
+
+void vec_push_back(vec_t* vec, void* data)
+{
+    vec_resize(vec, vec->elem_count+1, data);
+}
+
+void vec_pop_back(vec_t* vec, void* outdata)
+{
+    vec->elem_count--;
+    memcpy(outdata, &(vec->elem_buffer[vec->elem_count * vec->elem_size]), vec->elem_size);
+}
+
+void vec_clear(vec_t* vec)
+{
+    vec->elem_count = 0;
+}
+
diff --git a/source/data/vec.h b/source/data/vec.h
new file mode 100644
index 0000000..ed92515
--- /dev/null
+++ b/source/data/vec.h
@@ -0,0 +1,46 @@
+/**
+  @file vec.h
+*/
+#ifndef VEC_H
+#define VEC_H
+
+#include <libc.h>
+
+typedef struct {
+    size_t   elem_count;
+    size_t   elem_size;
+    size_t   elem_capacity;
+    uint8_t* elem_buffer;
+} vec_t;
+
+void vec_init(vec_t* vec, size_t elem_size);
+
+size_t vec_size(vec_t* vec);
+
+bool vec_empty(vec_t* vec);
+
+size_t vec_capacity(vec_t* vec);
+
+void vec_resize(vec_t* vec, size_t size, void* data);
+
+size_t vec_next_capacity(size_t req_size);
+
+void vec_shrink_to_fit(vec_t* vec);
+
+void vec_reserve(vec_t* vec, size_t size);
+
+void* vec_at(vec_t* vec, size_t index);
+
+void vec_set(vec_t* vec, size_t index, void* data);
+
+bool vec_insert(vec_t* vec, size_t index, size_t num_elements, ...);
+
+bool vec_erase(vec_t* vec, size_t start_idx, size_t end_idx);
+
+void vec_push_back(vec_t* vec, void* data);
+
+void vec_pop_back(vec_t* vec, void* outdata);
+
+void vec_clear(vec_t* vec);
+
+#endif /* VEC_H */
-- 
2.55.0