Shizuka Kamishima avatar Shizuka Kamishima committed 164e91a Draft

lcthw - darray

Comments (0)

Files changed (3)

liblcthw/src/lcthw/darray.c

+#include <lcthw/darray.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 an 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) {
+    int i = 0;
+    if (array->element_size > 0) {
+        for (i = 0; i < array->max; i++) {
+            if (array->contents[i] != NULL) {
+                free(array->contents[i]);
+            }
+        }
+    }
+}
+
+static inline int DArray_resize(DArray *array, size_t newsize) {
+    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 darray to new size: %d", array->max + (int)array->expand_rate);
+
+    memset(array->contents + old_max, 0, array->expand_rate + 1);
+    return 0;
+
+error:
+    return -1;
+}
+
+int DArray_contract(DArray *array) {
+    int new_size = array->end < (int)array->expand_rate ? (int)array->expand_rate : array->end;
+    return DArray_resize(array, new_size + 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) {
+    array->contents[array->end] = el;
+    array->end++;
+
+    if (DArray_end(array) >= DArray_max(array)) {
+        return DArray_expand(array);
+    } else {
+        return 0;
+    }
+}
+
+void *DArray_pop(DArray *array) {
+    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;
+}

liblcthw/src/lcthw/darray.h

+#ifndef lcthw_DArray_h
+#define lcthw_DArray_h
+
+#include <stdlib.h>
+#include <assert.h>
+#include <lcthw/dbg.h>
+
+typedef struct DArray {
+    int end;
+    int max;
+    size_t element_size;
+    size_t expand_rate;
+    void **contents;
+} DArray;
+
+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);
+
+void DArray_clear_destroy(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 void DArray_set(DArray *array, int i, void *el) {
+    check(i < array->max, "darray attempt to set past max");
+    array->contents[i] = el;
+error:
+    return;
+}
+
+static inline void *DArray_get(DArray *array, int i) {
+    check(i < array->max, "darray attempt to get past max");
+    return array->contents[i];
+error:
+    return NULL;
+}
+
+static inline void *DArray_remove(DArray *array, int i) {
+    void *el = array->contents[i];
+    array->contents[i] = NULL;
+    return el;
+}
+
+static inline void *DArray_new(DArray *array) {
+    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

liblcthw/tests/darray_tests.c

+#include "minunit.h"
+#include <lcthw/darray.h>
+
+static DArray *array = NULL;
+static int *val1 = NULL;
+static int *val2 = NULL;
+
+char *test_create() {
+    array = DArray_create(sizeof(int), 100);
+    mu_assert(array != NULL, "DArray_create failed");
+    mu_assert(array->contents != NULL, "contents are wrong in darray");
+    mu_assert(array->end == 0, "end isn't at the right spot");
+    mu_assert(array->element_size == sizeof(int), "element size is wrong");
+    mu_assert(array->max == 100, "wrong max length on initial size");
+    
+    return NULL;
+}
+
+char *test_destroy() {
+    DArray_destroy(array);
+    return NULL;
+}
+
+char *test_new() {
+    val1 = DArray_new(array);
+    mu_assert(val1 != NULL, "failed to make a new element");
+
+    val2 = DArray_new(array);
+    mu_assert(val2 != NULL, "failed to make a new element");
+
+    return NULL;
+}
+
+char *test_set() {
+    DArray_set(array, 0, val1);
+    DArray_set(array, 1, val2);
+    return NULL;
+}
+
+char *test_get() {
+    mu_assert(DArray_get(array, 0) == val1, "wrong first value");
+    mu_assert(DArray_get(array, 1) == val2, "wrong second value");
+    return NULL;
+}
+
+char *test_remove() {
+    int *val_check = DArray_remove(array, 0);
+    mu_assert(val_check != NULL, "should not get NULL");
+    mu_assert(*val_check == *val1, "should get the first value");
+    mu_assert(DArray_get(array, 0) == NULL, "should be gone");
+    DArray_free(val_check);
+
+    val_check = DArray_remove(array, 1);
+    mu_assert(val_check != NULL, "should not get NULL");
+    mu_assert(*val_check == *val1, "should get the first value");
+    mu_assert(DArray_get(array, 0) == NULL, "should be gone");
+    DArray_free(val_check);
+
+    return NULL;
+}
+
+char *test_expand_contract() {
+    int old_max = array->max;
+    DArray_expand(array);
+    mu_assert((unsigned int)array->max == old_max + array->expand_rate, "Wrong size after expand");
+
+    DArray_contract(array);
+    mu_assert((unsigned int)array->max == array->expand_rate + 1, "should stay at expand_rate at least");
+
+    DArray_contract(array);
+    mu_assert((unsigned int)array->max == array->expand_rate + 1, "should stay at expand_rate at least");
+    
+    return NULL;
+}
+
+char *test_push_pop() {
+    int i = 0;
+    for (i = 0; i < 1000; i++) {
+        int *val = DArray_new(array);
+        *val = i * 333;
+        DArray_push(array, val);
+    }
+    mu_assert(array->max == 1201, "wrong max size");
+
+    for (i = 999; i >= 0; i--) {
+        int *val = DArray_pop(array);
+        mu_assert(val != NULL, "shouldn't get a NULL");
+        mu_assert(*val == i * 333, "wrong value");
+        DArray_free(val);
+    }
+
+    return NULL;
+}
+
+char *all_tests() {
+    mu_suite_start();
+
+    mu_run_test(test_create);
+    mu_run_test(test_new);
+    mu_run_test(test_set);
+    mu_run_test(test_get);
+    mu_run_test(test_remove);
+    mu_run_test(test_expand_contract);
+    mu_run_test(test_push_pop);
+    mu_run_test(test_destroy);
+
+    return NULL;
+}
+
+RUN_TESTS(all_tests);
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.