Add array_list.h

2 files changed, 170 insertions, 0 deletions

diff --git a/include/shared/array_list.h b/include/shared/array_list.h
new file mode 100644
index 0000000..8b942ad
--- /dev/null
+++ b/include/shared/array_list.h
@@ -0,0 +1,105 @@
+#ifndef SHARED_ARRAY_LIST_H_
+#define SHARED_ARRAY_LIST_H_
+
+#include "kern/common.h"
+#include "kern/mem.h"
+
+#define ALLOC kalloc
+#define FREE kfree
+
+#define array_list_t(type) array_list_##type##_t
+#define array_list_new(type) array_list_##type##_new
+#define array_list_length(type) array_list_##type##_length
+#define array_list_reserve(type) array_list_##type##_reserve
+#define array_list_add(type) array_list_##type##_add
+#define array_list_remove(type) array_list_##type##remove
+#define array_list_ref(type) array_list_##type##_get
+#define array_list_free(type) array_list_##type##_free
+
+#define array_list_foreach(ar, val)            \
+  typeof((ar)->elements[0]) val;               \
+  if ((ar)->size > 0) val = (ar)->elements[0]; \
+  for (size_t _idx_ = 0; _idx_ < (ar)->size;   \
+       val = (++_idx_) >= (ar)->size ? val : (ar)->elements[_idx_])
+
+#define ARRAY_LIST_DECL(type)                                                \
+  typedef struct {                                                           \
+    size_t reserved;                                                         \
+    size_t size;                                                             \
+    type* elements;                                                          \
+  } array_list_t(type);                                                      \
+  size_t array_list_length(type)(const array_list_t(type)*);                 \
+  array_list_t(type) * array_list_new(type)();                               \
+  bool array_list_reserve(type)(array_list_t(type)*, size_t len);            \
+  bool array_list_add(type)(array_list_t(type)*, type val);                  \
+  bool array_list_remove(type)(array_list_t(type)*, size_t idx, type * out); \
+  type* array_list_ref(type)(array_list_t(type)*, size_t idx);               \
+  void array_list_free(type)(array_list_t(type)*);
+
+#define ARRAY_LIST_IMPL(type)                                            \
+  array_list_t(type) * array_list_new(type)()                            \
+  {                                                                      \
+    array_list_t(type)* ret = ALLOC(sizeof(array_list_t(type)));         \
+    ret->size = 0;                                                       \
+    ret->reserved = 0;                                                   \
+    ret->elements = NULL;                                                \
+    return ret;                                                          \
+  }                                                                      \
+  size_t array_list_length(type)(const array_list_t(type) * lst)         \
+  {                                                                      \
+    return lst->size;                                                    \
+  }                                                                      \
+  bool array_list_reserve(type)(array_list_t(type) * lst, size_t newlen) \
+  {                                                                      \
+    if (lst->reserved < newlen) {                                        \
+      type* new_arr = ALLOC(sizeof(type) * newlen);                      \
+      if (!new_arr) {                                                    \
+        return 0;                                                        \
+      }                                                                  \
+      for (size_t i = 0; i < lst->size; ++i) {                           \
+        new_arr[i] = lst->elements[i];                                   \
+      }                                                                  \
+      FREE(lst->elements);                                               \
+      lst->elements = new_arr;                                           \
+      lst->reserved = newlen;                                            \
+    }                                                                    \
+    return 1;                                                            \
+  }                                                                      \
+  bool array_list_add(type)(array_list_t(type) * lst, type v)            \
+  {                                                                      \
+    if (lst->size == lst->reserved) {                                    \
+      if (!array_list_reserve(type)(                                     \
+              lst, lst->reserved == 0 ? 4 : lst->reserved * 2)) {        \
+        return 0;                                                        \
+      }                                                                  \
+    }                                                                    \
+    lst->elements[lst->size++] = v;                                      \
+    return 1;                                                            \
+  }                                                                      \
+  bool array_list_remove(type)(                                          \
+      array_list_t(type) * lst, size_t idx, type * out)                  \
+  {                                                                      \
+    if (idx >= lst->size) {                                              \
+      return 0;                                                          \
+    }                                                                    \
+    if (out) *out = lst->elements[idx];                                  \
+    for (size_t i = idx; i < lst->size - 1; ++i) {                       \
+      lst->elements[i] = lst->elements[i + 1];                           \
+    }                                                                    \
+    lst->size--;                                                         \
+    return 1;                                                            \
+  }                                                                      \
+  type* array_list_ref(type)(array_list_t(type) * lst, size_t idx)       \
+  {                                                                      \
+    if (idx >= lst->size) {                                              \
+      return NULL;                                                       \
+    }                                                                    \
+    return &lst->elements[idx];                                          \
+  }                                                                      \
+  void array_list_free(type)(array_list_t(type) * lst)                   \
+  {                                                                      \
+    FREE(lst->elements);                                                 \
+    FREE(lst);                                                           \
+  }
+
+#endif /* SHARED_ARRAY_LIST_H_ */
diff --git a/tests/test_array_list.c b/tests/test_array_list.c
new file mode 100644
index 0000000..71ffa55
--- /dev/null
+++ b/tests/test_array_list.c
@@ -0,0 +1,65 @@
+#include "kern/mem.h"
+#include "shared/array_list.h"
+#include "test_harness.h"
+
+ARRAY_LIST_DECL(int);
+ARRAY_LIST_IMPL(int);
+
+TEST(array_list, smell)
+{
+  array_list_t(int)* list = array_list_new(int)();
+
+  array_list_add(int)(list, 1);
+  array_list_add(int)(list, 2);
+  array_list_add(int)(list, 3);
+  array_list_add(int)(list, 4);
+  array_list_add(int)(list, 5);
+
+  int expected[5] = {1, 2, 3, 4, 5};
+
+  for (size_t i = 0; i < 5; ++i) {
+    ASSERT_EQ(*array_list_ref(int)(list, i), expected[i]);
+  }
+
+  ASSERT_EQ(array_list_length(int)(list), 5);
+  *array_list_ref(int)(list, 3) = 8;
+  expected[3] = 8;
+
+  for (size_t i = 0; i < 5; ++i) {
+    ASSERT_EQ(*array_list_ref(int)(list, i), expected[i]);
+  }
+
+  int out;
+  array_list_remove(int)(list, 2, &out);
+  ASSERT_EQ(out, 3);
+  ASSERT_EQ(array_list_length(int)(list), 4);
+
+  int expected2[4] = {1, 2, 8, 5};
+  for (size_t i = 0; i < 4; ++i) {
+    ASSERT_EQ(*array_list_ref(int)(list, i), expected2[i]);
+  }
+
+  return 0;
+}
+
+TEST(array_list, foreach)
+{
+  array_list_t(int)* arl = array_list_new(int)();
+  array_list_add(int)(arl, 3);
+  array_list_add(int)(arl, 2);
+  array_list_add(int)(arl, 1);
+
+  int i = 0;
+  int values[3];
+  array_list_foreach(arl, val) {
+    values[i] = val;
+    ++ i;
+  }
+
+  ASSERT_EQ(values[0], 3);
+  ASSERT_EQ(values[1], 2);
+  ASSERT_EQ(values[2], 1);
+
+  return 0;
+
+}