diff options
| -rw-r--r-- | include/shared/linked_list.h | 131 | ||||
| -rw-r--r-- | tests/test_linked_list.c | 41 |
2 files changed, 172 insertions, 0 deletions
diff --git a/include/shared/linked_list.h b/include/shared/linked_list.h new file mode 100644 index 0000000..17c2cdd --- /dev/null +++ b/include/shared/linked_list.h @@ -0,0 +1,131 @@ +#ifndef SHARED_LINKED_LIST_H_ +#define SHARED_LINKED_LIST_H_ + +#define linked_list_t(type) linked_list_##type##_t +#define linked_list_node_t(type) linked_list_node_##type##_t +#define linked_list_push_back(type) linked_list_push_back_##type +#define linked_list_push_front(type) linked_list_push_front_##type +#define linked_list_pop_front(type) linked_list_pop_front_##type +#define linked_list_pop_back(type) linked_list_pop_back_##type +#define linked_list_front(type) linked_list_front_##type +#define linked_list_back(type) linked_list_back_##type +#define linked_list_length(type) linked_list_length_##type +#define linked_list_length(type) linked_list_length_##type + +#define LINKED_LIST_INIT \ + { \ + .head = NULL \ + } + +#define linked_list_foreach(ll, val) \ + for (typeof(ll.head) _cur_ = ll.head, typeof(_cur_->value) val; \ + _cur_ != NULL && ((val = _cur_->value) || 1); \ + _cur_ = _cur_->next) + +#define NO_ATTRIBUTE + +#define LINKED_LIST_DECL(type) LINKED_LIST_INTERNAL_DECL(type, NO_ATTRIBUTE) + +#define LINKED_LIST_STATIC_DECL(type) LINKED_LIST_INTERNAL_DECL(type, static) + +#define LINKED_LIST_INTERNAL_DECL(type, attr) \ + typedef struct LINKED_LIST_NODE_##type { \ + type value; \ + struct LINKED_LIST_NODE_##type* next; \ + } linked_list_node_t(type); \ + \ + typedef struct { \ + linked_list_node_t(type) * head; \ + } linked_list_t(type); \ + \ + attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value); \ + attr void linked_list_push_front(type)( \ + linked_list_t(type) * ll, type value); \ + attr void linked_list_pop_back(type)(linked_list_t(type) * ll); \ + attr void linked_list_pop_front(type)(linked_list_t(type) * ll); \ + attr type* linked_list_front(type)(linked_list_t(type) * ll); \ + attr type* linked_list_back(type)(linked_list_t(type) * ll); + +#define LINKED_LIST_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, NO_ATTRIBUTE) + +#define LINKED_LIST_STATIC_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, static) + +#define LINKED_LIST_INTERNAL_IMPL(type, attr) \ + attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value) \ + { \ + if (!ll->head) { \ + ll->head = kalloc(sizeof(linked_list_node_t(type))); \ + ll->head->value = value; \ + ll->head->next = NULL; \ + } else { \ + linked_list_node_t(type)* c = ll->head; \ + while (c->next) c = c->next; \ + c->next = kalloc(sizeof(linked_list_node_t(type))); \ + c->next->next = NULL; \ + c->next->value = value; \ + } \ + } \ + attr void linked_list_push_front(type)(linked_list_t(type) * ll, type value) \ + { \ + if (!ll->head) { \ + ll->head = kalloc(sizeof(linked_list_node_t(type))); \ + ll->head->value = value; \ + ll->head->next = NULL; \ + } else { \ + linked_list_node_t(type)* node = \ + kalloc(sizeof(linked_list_node_t(type))); \ + node->next = ll->head; \ + node->value = value; \ + ll->head = node; \ + } \ + } \ + attr void linked_list_pop_back(type)(linked_list_t(type) * ll) \ + { \ + if (!ll->head) { \ + return; \ + } \ + if (!ll->head->next) { \ + kfree(ll->head); \ + ll->head = NULL; \ + return; \ + } \ + linked_list_node_t(type)* c = ll->head; \ + while (c->next->next) c = c->next; \ + kfree(c->next); \ + c->next = NULL; \ + return; \ + } \ + attr void linked_list_pop_front(type)(linked_list_t(type) * ll) \ + { \ + if (!ll->head) { \ + return; \ + } \ + linked_list_node_t(type)* node = ll->head; \ + ll->head = node->next; \ + kfree(node); \ + } \ + attr type* linked_list_front(type)(linked_list_t(type) * ll) \ + { \ + if (!ll->head) { \ + return NULL; \ + } \ + return &ll->head->value; \ + } \ + attr type* linked_list_back(type)(linked_list_t(type) * ll) \ + { \ + if (!ll->head) { \ + return NULL; \ + } \ + linked_list_node_t(type)* cur = ll->head; \ + while (cur->next) cur = cur->next; \ + return &cur->value; \ + } \ + attr size_t linked_list_length(type)(linked_list_t(type) * ll) \ + { \ + linked_list_node_t(type) * cur; \ + size_t ret = 0; \ + for (cur = ll->head; cur; cur = cur->next) ++ret; \ + return ret; \ + } + +#endif /* SHARED_LINKED_LIST_H_ */ diff --git a/tests/test_linked_list.c b/tests/test_linked_list.c new file mode 100644 index 0000000..401091a --- /dev/null +++ b/tests/test_linked_list.c @@ -0,0 +1,41 @@ +#include "kern/mem.h" +#include "shared/linked_list.h" +#include "test_harness.h" + +LINKED_LIST_STATIC_DECL(int); +LINKED_LIST_STATIC_IMPL(int); + +TEST(linked_list, smell) +{ + linked_list_t(int) ll = LINKED_LIST_INIT; + + ASSERT_EQ(linked_list_length(int)(&ll), 0); + + linked_list_push_front(int)(&ll, 5); + ASSERT_EQ(linked_list_length(int)(&ll), 1); + + linked_list_push_front(int)(&ll, 3); + linked_list_push_back(int)(&ll, 2); + + ASSERT_EQ(linked_list_length(int)(&ll), 3); + ASSERT_EQ(*linked_list_front(int)(&ll), 3); + ASSERT_EQ(*linked_list_back(int)(&ll), 2); + + linked_list_push_back(int)(&ll, 7); + ASSERT_EQ(*linked_list_back(int)(&ll), 7); + linked_list_pop_back(int)(&ll); + ASSERT_EQ(*linked_list_back(int)(&ll), 2); + + linked_list_pop_front(int)(&ll); + + ASSERT_EQ(*linked_list_front(int)(&ll), 5); + + linked_list_pop_front(int)(&ll); + + ASSERT_EQ(*linked_list_front(int)(&ll), 2); + + linked_list_pop_front(int)(&ll); + + ASSERT_EQ(linked_list_front(int)(&ll), NULL); + return 0; +} |