Add linked list header.

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;
+}