Add list library.

4 files changed, 166 insertions, 49 deletions

diff --git a/list/CMakeLists.txt b/list/CMakeLists.txt
index 8caeabc..6e76ec6 100644
--- a/list/CMakeLists.txt
+++ b/list/CMakeLists.txt
@@ -4,14 +4,11 @@ project(list)
 
 # Library
 
-add_library(list
-  src/list.c)
+add_library(list INTERFACE)
 
-target_include_directories(list PUBLIC
+target_include_directories(list INTERFACE
   include)
 
-target_compile_options(list PRIVATE -Wall -Wextra)
-
 # Test
 
 add_executable(list_test
diff --git a/list/include/list.h b/list/include/list.h
index 945de28..facf820 100644
--- a/list/include/list.h
+++ b/list/include/list.h
@@ -1,21 +1,111 @@
-/// A doubly linked list.
-///
-/// This list does not hold user data. Instead, the list can be used as an
-/// intrusive list or as part as a more complex data structure.
+/// Doubly-linked list.
 #pragma once
 
+#include <assert.h>
 #include <stddef.h>
+#include <stdlib.h>
+
+#define DEF_LIST(type)         \
+  typedef struct type##_node { \
+    type                val;   \
+    struct type##_node* prev;  \
+    struct type##_node* next;  \
+  } type##_node;               \
+  typedef struct type##_list { \
+    type##_node* head;         \
+  } type##_list;
+
+static inline void* alloc(size_t size) {
+  void* ptr = calloc(1, size);
+  assert(ptr);
+  return ptr;
+}
+
+/// Create a new empty list.
+#define make_list(type) \
+  (type##_list) { 0 }
+
+/// Delete the list.
+#define del_list(list)                                  \
+  for (__typeof__(list.head) node = list.head; node;) { \
+    __typeof__(node) cur = node;                        \
+    node                 = node->next;                  \
+    free(cur);                                          \
+  }                                                     \
+  list.head = 0;
 
-typedef struct list list;
+/// Prepend a value to the list.
+#define list_push(list, value)                              \
+  {                                                         \
+    __typeof__(list.head) node = alloc(sizeof(*list.head)); \
+    node->val                  = value;                     \
+    node->next                 = list.head;                 \
+    if (list.head) {                                        \
+      list.head->prev = node;                               \
+    }                                                       \
+    list.head = node;                                       \
+  }
 
-typedef struct list {
-  list* prev;
-  list* next;
-} list;
+/// Delete the first occurrence of the value from the list.
+#define list_remove(list, search_value)                                   \
+  for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
+    if (iter->val == (search_value)) {                                    \
+      del_node(list, iter);                                               \
+      break;                                                              \
+    }                                                                     \
+  }
 
-/// Create a new list from an array of `size` items.
-void list_make(list* list, size_t size);
+/// Delete the node that contains the value at the given address from the
+/// list.
+#define list_remove_ptr(list, value_ptr)                                  \
+  for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
+    if (&iter->val == value_ptr) {                                        \
+      del_node(list, iter);                                               \
+      break;                                                              \
+    }                                                                     \
+  }
 
-/// Iterates over all the items in the list.
-#define list_foreach(LIST, iter) \
-  for (struct list* iter = LIST; iter; iter = iter->next)
+/// Delete the list node.
+#define del_node(list, node)         \
+  {                                  \
+    assert(node);                    \
+    if (node->prev) {                \
+      node->prev->next = node->next; \
+    }                                \
+    if (node->next) {                \
+      node->next->prev = node->prev; \
+    }                                \
+    if (list.head == node) {         \
+      list.head = 0;                 \
+    }                                \
+    free(node);                      \
+    node = 0;                        \
+  }
+
+/// Iterate over all the items in the list.
+///
+/// Use 'value' to refer to the address of the current node's value during
+/// iteration.
+#define list_foreach(list, body)                       \
+  {                                                    \
+    __typeof__(list.head) node = list.head;            \
+    while (node) {                                     \
+      const __typeof__(node->val)* value = &node->val; \
+      body;                                            \
+      node = node->next;                               \
+    }                                                  \
+  }
+
+/// Iterate over all the items in the list.
+///
+/// Use 'value' to refer to the address of the current node's value during
+/// iteration.
+#define list_foreach_mut(list, body)             \
+  {                                              \
+    __typeof__(list.head) node = list.head;      \
+    while (node) {                               \
+      __typeof__(node->val)* value = &node->val; \
+      body;                                      \
+      node = node->next;                         \
+    }                                            \
+  }
diff --git a/list/src/list.c b/list/src/list.c
deleted file mode 100644
index f5b6507..0000000
--- a/list/src/list.c
+++ /dev/null
@@ -1,14 +0,0 @@
-#include "list.h"
-
-#include <assert.h>
-
-void list_make(list* list, size_t size) {
-  if (size == 0) {
-    return;
-  }
-  assert(list);
-  for (size_t i = 0; i < size; ++i) {
-    list[i].prev = (i == 0 ? 0 : &list[i - 1]);
-    list[i].next = (i == size - 1 ? 0 : &list[i + 1]);
-  }
-}
diff --git a/list/test/list_test.c b/list/test/list_test.c
index a11c713..9ff10c1 100644
--- a/list/test/list_test.c
+++ b/list/test/list_test.c
@@ -4,31 +4,75 @@
 
 #define TEST_LIST_SIZE 10
 
-// Create an empty list.
-TEST_CASE(list_create_empty) { list_make(0, 0); }
-
-// Create a list of a given size.
-TEST_CASE(list_create) {
-  struct list list[TEST_LIST_SIZE];
-  list_make(list, TEST_LIST_SIZE);
-}
+DEF_LIST(int);
 
 // Iterate over a list.
 TEST_CASE(list_traverse) {
-  int numbers[TEST_LIST_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
-
-  struct list list[TEST_LIST_SIZE];
-  list_make(list, TEST_LIST_SIZE);
+  int_list list = make_list(int);
+  for (int i = 0; i < TEST_LIST_SIZE; ++i) {
+    list_push(list, i + 1);
+  }
 
   int count = 0;
-  int sum = 0;
-  list_foreach(list, item) {
+  int sum   = 0;
+  list_foreach(list, {
     count++;
-    sum += numbers[item - list];
-  }
+    sum += *value;
+  });
 
   TEST_EQUAL(count, TEST_LIST_SIZE);
   TEST_EQUAL(sum, TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2);
+
+  del_list(list);
+}
+
+// Delete by value.
+TEST_CASE(list_remove_by_value) {
+  int_list list = make_list(int);
+  for (int i = 0; i < TEST_LIST_SIZE; ++i) {
+    list_push(list, i + 1);
+  }
+
+  list_remove(list, 5);
+
+  int count = 0;
+  int sum   = 0;
+  list_foreach(list, {
+    count++;
+    sum += *value;
+  });
+
+  TEST_EQUAL(count, TEST_LIST_SIZE - 1);
+  TEST_EQUAL(sum, (TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2) - 5);
+
+  del_list(list);
+}
+
+// Delete by address.
+TEST_CASE(list_remove_by_address) {
+  const int N = 3;
+
+  int* ptrs[3] = {0};
+
+  int_list list = make_list(int);
+  for (int i = 0; i < N; ++i) {
+    list_push(list, i + 1);
+    ptrs[i] = &list.head->val;
+  }
+
+  list_remove_ptr(list, ptrs[1]); // Value 2.
+
+  int count = 0;
+  int sum   = 0;
+  list_foreach(list, {
+    count++;
+    sum += *value;
+  });
+
+  TEST_EQUAL(count, 2);
+  TEST_EQUAL(sum, 1 + 3);
+
+  del_list(list);
 }
 
 int main() { return 0; }