diff options
| -rw-r--r-- | include/shared/array_list.h | 105 | ||||
| -rw-r--r-- | tests/test_array_list.c | 65 |
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; + +} |