nserver: Add darray.h

2 files changed, 312 insertions, 0 deletions

diff --git a/nserver/src/darray.c b/nserver/src/darray.c
new file mode 100644
index 0000000..6dc3839
--- /dev/null
+++ b/nserver/src/darray.c
@@ -0,0 +1,192 @@
+#include <darray.h>
+#include <darray_algos.h>
+#include <assert.h>
+
+DArray *DArray_create(size_t element_size, size_t initial_max)
+{
+    DArray *array = malloc(sizeof(DArray));
+    check_mem(array);
+    array->max = initial_max;
+    check(array->max > 0, "You must set initial_max > 0.");
+
+    array->contents = calloc(initial_max, sizeof(void *));
+    check_mem(array->contents);
+
+    array->end = 0;
+    array->element_size = element_size;
+    array->expand_rate = DEFAULT_EXPAND_RATE;
+
+    return array;
+
+ error:
+    if (array)
+        free(array);
+    return NULL;
+}
+
+void DArray_clear(DArray *array)
+{
+    check(array != NULL, "array cannot be NULL");
+
+    int i = 0;
+    if (array->element_size > 0) {
+        for (i = 0; i < array->max; i++) {
+            if (array->contents[i] != NULL) {
+                free(array->contents[i]);
+            }
+        }
+    }
+
+ error:
+    return;
+}
+
+static inline int DArray_resize(DArray *array, size_t newsize)
+{
+    check(array != NULL, "array cannot be NULL");
+    check((int) newsize >= array->end, "newsize must be >= end.");
+
+    array->max = newsize;
+    check(array->max > 0, "The newsize must be > 0.");
+
+    void *contents = realloc(array->contents,
+                             array->max * sizeof(void *));
+    // Check contents and assume realloc doesn't harm the original on error.
+
+    check_mem(contents);
+
+    array->contents = contents;
+
+    return 0;
+ error:
+    return -1;
+}
+
+int DArray_expand(DArray *array)
+{
+    size_t old_max = array->max;
+    check(DArray_resize(array, array->max + array->expand_rate) == 0,
+          "Failed to expand array to new size: %d",
+          array->max + (int) array->expand_rate);
+
+    memset(array->contents + old_max, 0, (array->expand_rate) * sizeof(void *));
+
+    return 0;
+
+ error:
+    return -1;
+}
+
+int DArray_contract(DArray *array)
+{
+    check(array != NULL, "array cannot be NULL");
+
+    int new_size = array->end < (int) array->expand_rate ?
+        (int) array->expand_rate : array->end;
+
+    return DArray_resize(array, new_size + 1);
+ error:
+    return -1;
+}
+
+void DArray_destroy(DArray *array)
+{
+    if (array) {
+        if (array->contents)
+            free(array->contents);
+        free(array);
+    }
+}
+
+void DArray_clear_destroy(DArray *array)
+{
+    DArray_clear(array);
+    DArray_destroy(array);
+}
+
+int DArray_push(DArray *array, void *el)
+{
+    check(array != NULL, "array cannot be NULL");
+
+    array->contents[array->end] = el;
+    array->end++;
+
+    if (DArray_end(array) >= DArray_max(array)) {
+        return DArray_expand(array);
+    } else {
+        return 0;
+    }
+
+ error:
+    return -1;
+}
+
+void *DArray_pop(DArray *array)
+{
+    check(array != NULL, "array cannot be NULL");
+    check(array->end - 1 >= 0, "Attempt to pop from empty array.");
+
+    void *el = DArray_remove(array, array->end - 1);
+    array->end--;
+
+    if (DArray_end(array) > (int)array->expand_rate
+        && DArray_end(array) % array->expand_rate) {
+        DArray_contract(array);
+    }
+
+    return el;
+ error:
+    return NULL;
+}
+
+int DArray_sort_add(DArray *array, void *el, DArray_compare cmp)
+{
+    int rc;
+    rc = DArray_push(array, el);
+    check(rc == 0, "Error pushing element.");
+
+    // sort the array.
+    rc = DArray_heapsort(array, cmp);
+    check(rc == 0, "Error sorting array.");
+
+    return 0;
+ error:
+    return -1;
+}
+
+DArray *DArray_shallow_copy(DArray *array)
+{
+    DArray *copy  = DArray_create(array->element_size, array->max);
+    check(copy != NULL, "Error creating DArray copy.");
+
+    int i = 0;
+    for (i = 0; i < array->max; i++) {
+            copy->contents[i] = array->contents[i];
+    }
+
+    return copy;
+ error:
+    return NULL;
+}
+
+int DArray_find(DArray *array, void *el, DArray_compare cmp)
+{
+    int low = 0;
+    int high = DArray_end(array) - 1;
+    void *c = NULL;
+
+    while (low <= high) {
+        int middle =  low + (high - low) / 2;
+        c = DArray_get(array, middle);
+
+        if (cmp(&el, &c) < 0) {
+            high = middle - 1;
+        } else if (cmp(&el, &c) > 0) {
+            low = middle + 1;
+        } else {
+            return middle;
+        }
+    }
+
+    return -1;
+}
diff --git a/nserver/src/darray.h b/nserver/src/darray.h
new file mode 100644
index 0000000..d262d39
--- /dev/null
+++ b/nserver/src/darray.h
@@ -0,0 +1,120 @@
+#ifndef _DArray_h
+#define _DArray_h
+#include <stdlib.h>
+#include <assert.h>
+#include <dbg.h>
+
+typedef struct DArray {
+    int end;
+    int max;
+    size_t element_size;
+    size_t expand_rate;
+    void **contents;
+} DArray;
+
+typedef int (*DArray_compare) (const void *a, const void *b);
+
+DArray *DArray_create(size_t element_size, size_t initial_max);
+
+void DArray_destroy(DArray *array);
+
+void DArray_clear(DArray *array);
+
+int DArray_expand(DArray *array);
+
+int DArray_contract(DArray *array);
+
+int DArray_push(DArray *array, void *el);
+
+void *DArray_pop(DArray *array);
+
+int DArray_sort_add(DArray *array, void *el, DArray_compare cmp);
+
+int DArray_find(DArray *array, void *el, DArray_compare cmp);
+
+void DArray_clear_destroy(DArray *array);
+
+/**
+ * Creates a new DArray using `DArray_create` and copies the
+ * `contents` from array to the newly created DArray.
+ *
+ * Returns newly created DArray.
+ */
+DArray *DArray_shallow_copy(DArray *array);
+
+#define DArray_last(A) ((A)->contents[(A)->end - 1])
+#define DArray_first(A) ((A)->contents[0])
+#define DArray_end(A) ((A)->end)
+#define DArray_count(A) DArray_end(A)
+#define DArray_max(A) ((A)->max)
+
+#define DEFAULT_EXPAND_RATE 300
+
+static inline int DArray_set(DArray *array, int i, void *el)
+{
+    check(array != NULL, "array cannot be NULL");
+    check(i >= 0, "i cannot be lesser than 0");
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstrict-overflow"
+    check(i < array->max, "darray attempt to set past max");
+#pragma GCC diagnostic pop
+
+    if (i > array->end)
+        array->end = i;
+
+    array->contents[i] = el;
+    return i;
+ error:
+    return -1;
+}
+
+static inline void *DArray_get(DArray *array, int i)
+{
+    check(array != NULL, "array cannot be NULL");
+    check(i >= 0, "i cannot be lesser than 0");
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstrict-overflow"
+    check(i < array->max, "darray attempt to get past max");
+#pragma GCC diagnostic pop
+
+    return array->contents[i];
+ error:
+    return NULL;
+}
+
+static inline void *DArray_remove(DArray *array, int i)
+{
+    check(array != NULL, "array cannot be NULL");
+    check(i >= 0, "i cannot be lesser than 0");
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstrict-overflow"
+    check(i < array->max, "darray attempt to get past max");
+#pragma GCC diagnostic pop
+
+    void *el = array->contents[i];
+
+    array->contents[i] = NULL;
+
+    return el;
+ error:
+    return NULL;
+}
+
+static inline void *DArray_new(DArray *array)
+{
+    check(array != NULL, "array cannot be NULL");
+    check(array->element_size > 0,
+          "Can't use DArray_new on 0 size darrays.");
+
+    return calloc(1, array->element_size);
+
+ error:
+    return NULL;
+}
+
+#define DArray_free(E) free((E))
+
+#endif