Add remove ability to linked list.

3 files changed, 221 insertions, 107 deletions

diff --git a/include/shared/linked_list.h b/include/shared/linked_list.h
index 3f8e075..ec72377 100644
--- a/include/shared/linked_list.h
+++ b/include/shared/linked_list.h
@@ -1,15 +1,21 @@
 #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
+#include "kern/common.h"
+
+#define linked_list_t(T) linked_list___##T##___t
+#define linked_list_node_t(T) linked_list_node___##T##___t
+#define linked_list_itr_t(T) linked_list_node_itr___##T##___t
+#define linked_list_push_back(T) linked_list_push_back___##T
+#define linked_list_push_front(T) linked_list_push_front___##T
+#define linked_list_pop_front(T) linked_list_pop_front___##T
+#define linked_list_pop_back(T) linked_list_pop_back___##T
+#define linked_list_front(T) linked_list_front___##T
+#define linked_list_back(T) linked_list_back___##T
+#define linked_list_length(T) linked_list_length___##T
+#define linked_list_find_match(T) linked_list_find_match___##T
+#define linked_list_remove_first_match(T) linked_list_remove_first_match___##T
+#define linked_list_remove(T) linked_list_remove___##T
 
 #define LINKED_LIST_INIT \
   {                      \
@@ -24,108 +30,171 @@
 
 #define NO_ATTRIBUTE
 
-#define LINKED_LIST_DECL(type) LINKED_LIST_INTERNAL_DECL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_DECL(T) LINKED_LIST_INTERNAL_DECL(T, NO_ATTRIBUTE)
 
-#define LINKED_LIST_STATIC_DECL(type) LINKED_LIST_INTERNAL_DECL(type, static)
+#define LINKED_LIST_STATIC_DECL(T) LINKED_LIST_INTERNAL_DECL(T, static inline)
 
-#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);                                                  \
+#define LINKED_LIST_INTERNAL_DECL(T, attr)                                     \
+  typedef struct LINKED_LIST_NODE_##T {                                        \
+    T value;                                                                   \
+    struct LINKED_LIST_NODE_##T* next;                                         \
+  } linked_list_node_t(T);                                                     \
+                                                                               \
+  typedef struct {                                                             \
+    linked_list_node_t(T) * prev;                                              \
+    linked_list_node_t(T) * cur;                                               \
+  } linked_list_itr_t(T);                                                      \
                                                                                \
   typedef struct {                                                             \
-    linked_list_node_t(type) * head;                                           \
-  } linked_list_t(type);                                                       \
+    linked_list_node_t(T) * head;                                              \
+  } linked_list_t(T);                                                          \
                                                                                \
-  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);
+  attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value);          \
+  attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value);         \
+  attr void linked_list_pop_back(T)(linked_list_t(T) * ll);                    \
+  attr void linked_list_pop_front(T)(linked_list_t(T) * ll);                   \
+  attr size_t linked_list_length(T)(const linked_list_t(T) * ll);              \
+  attr T* linked_list_front(T)(const linked_list_t(T) * ll);                   \
+  attr bool linked_list_find_match(T)(                                         \
+      const linked_list_t(T) * ll,                                             \
+      linked_list_itr_t(T) * itr_out,                                          \
+      bool (*match)(T, void*),                                                 \
+      void* closure);                                                          \
+  attr bool linked_list_remove_first_match(T)(                                 \
+      linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure); \
+  attr T* linked_list_back(T)(const linked_list_t(T) * ll);
 
-#define LINKED_LIST_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, NO_ATTRIBUTE)
 
-#define LINKED_LIST_STATIC_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, static)
+#define LINKED_LIST_STATIC_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, static inline)
 
-#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;                                                                \
-  }
+#define PRAGMA(x) _Pragma(#x)
+#define LINKED_LIST_INTERNAL_IMPL(T, attr)                                    \
+  _Pragma("GCC diagnostic push")                                              \
+      _Pragma("GCC diagnostic ignored \"-Wunused-function\"")                 \
+          attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value)  \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      ll->head = kalloc(sizeof(linked_list_node_t(T)));                       \
+      ll->head->value = value;                                                \
+      ll->head->next = NULL;                                                  \
+    } else {                                                                  \
+      linked_list_node_t(T)* c = ll->head;                                    \
+      while (c->next) c = c->next;                                            \
+      c->next = kalloc(sizeof(linked_list_node_t(T)));                        \
+      c->next->next = NULL;                                                   \
+      c->next->value = value;                                                 \
+    }                                                                         \
+  }                                                                           \
+  attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value)         \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      ll->head = kalloc(sizeof(linked_list_node_t(T)));                       \
+      ll->head->value = value;                                                \
+      ll->head->next = NULL;                                                  \
+    } else {                                                                  \
+      linked_list_node_t(T)* node = kalloc(sizeof(linked_list_node_t(T)));    \
+      node->next = ll->head;                                                  \
+      node->value = value;                                                    \
+      ll->head = node;                                                        \
+    }                                                                         \
+  }                                                                           \
+  attr void linked_list_pop_back(T)(linked_list_t(T) * ll)                    \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return;                                                                 \
+    }                                                                         \
+    if (!ll->head->next) {                                                    \
+      kfree(ll->head);                                                        \
+      ll->head = NULL;                                                        \
+      return;                                                                 \
+    }                                                                         \
+    linked_list_node_t(T)* c = ll->head;                                      \
+    while (c->next->next) c = c->next;                                        \
+    kfree(c->next);                                                           \
+    c->next = NULL;                                                           \
+    return;                                                                   \
+  }                                                                           \
+  attr void linked_list_pop_front(T)(linked_list_t(T) * ll)                   \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return;                                                                 \
+    }                                                                         \
+    linked_list_node_t(T)* node = ll->head;                                   \
+    ll->head = node->next;                                                    \
+    kfree(node);                                                              \
+  }                                                                           \
+  attr T* linked_list_front(T)(const linked_list_t(T) * ll)                   \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return NULL;                                                            \
+    }                                                                         \
+    return &ll->head->value;                                                  \
+  }                                                                           \
+  attr T* linked_list_back(T)(const linked_list_t(T) * ll)                    \
+  {                                                                           \
+    if (!ll->head) {                                                          \
+      return NULL;                                                            \
+    }                                                                         \
+    linked_list_node_t(T)* cur = ll->head;                                    \
+    while (cur->next) cur = cur->next;                                        \
+    return &cur->value;                                                       \
+  }                                                                           \
+  attr size_t linked_list_length(T)(const linked_list_t(T) * ll)              \
+  {                                                                           \
+    linked_list_node_t(T) * cur;                                              \
+    size_t ret = 0;                                                           \
+    for (cur = ll->head; cur; cur = cur->next) ++ret;                         \
+    return ret;                                                               \
+  }                                                                           \
+  attr bool linked_list_find_match(T)(                                        \
+      const linked_list_t(T) * ll,                                            \
+      linked_list_itr_t(T) * itr_out,                                         \
+      bool (*match)(T, void*),                                                \
+      void* closure)                                                          \
+  {                                                                           \
+    linked_list_node_t(T)* prev = NULL;                                       \
+    linked_list_node_t(T)* cur = NULL;                                        \
+    if (!ll || !ll->head) {                                                   \
+      return 0;                                                               \
+    }                                                                         \
+    for (cur = ll->head; cur != NULL; cur = (prev = cur)->next) {             \
+      if (match(cur->value, closure)) {                                       \
+        itr_out->prev = prev;                                                 \
+        itr_out->cur = cur;                                                   \
+        return 1;                                                             \
+      }                                                                       \
+    }                                                                         \
+    return 0;                                                                 \
+  }                                                                           \
+  attr bool linked_list_remove_first_match(T)(                                \
+      linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure) \
+  {                                                                           \
+    linked_list_itr_t(T) ctx;                                                 \
+    if (!linked_list_find_match(T)(ll, &ctx, match, closure)) {               \
+      return 0;                                                               \
+    }                                                                         \
+    if (out) *out = ctx.cur->value;                                           \
+    if (!ctx.prev) {                                                          \
+      ll->head = ctx.cur->next;                                               \
+    } else {                                                                  \
+      ctx.prev->next = ctx.cur->next;                                         \
+    }                                                                         \
+    kfree(ctx.cur);                                                           \
+    return 1;                                                                 \
+  }                                                                           \
+  int memcmp(const void* s1, const void* s2, size_t n);                       \
+  static inline bool linked_list___##T##___eq(T elem, void* other)            \
+  {                                                                           \
+    return memcmp(&elem, other, sizeof(T)) == 0;                              \
+  }                                                                           \
+  attr bool linked_list_remove(T)(linked_list_t(T) * ll, T val)               \
+  {                                                                           \
+    bool (*fn)(T, void*) = &linked_list___##T##___eq;                         \
+    bool ret = 0;                                                             \
+    while (linked_list_remove_first_match(T)(ll, NULL, fn, &val)) ret = 1;    \
+    return ret;                                                                 \
+  }                                                                           \
+  _Pragma("GCC diagnostic pop")
 
 #endif /* SHARED_LINKED_LIST_H_ */
diff --git a/src/kern/stdlibrepl.c b/src/kern/stdlibrepl.c
index 588191b..38b8477 100644
--- a/src/kern/stdlibrepl.c
+++ b/src/kern/stdlibrepl.c
@@ -15,14 +15,37 @@ size_t strlen(char* ch)
 
 #ifdef ARCH_STM32L4
 
-void memcpy(void* dest, void* src, size_t size)
+void* memcpy(void* dest, const void* src, size_t size)
 {
   uint8_t* dest_ = dest;
-  uint8_t* src_ = src;
+  const uint8_t* src_ = src;
 
-  while(size --) {
+  while (size--) {
     *(dest_++) = *(src_++);
   }
+
+  return dest;
+}
+
+int memcmp(const void* s1_, const void* s2_, size_t size)
+{
+  const uint8_t* s1 = s1_;
+  const uint8_t* s2 = s2_;
+
+  while (size--) {
+    if (*s1 != *s2) {
+      if (*s1 > *s2) {
+        return 1;
+      } else {
+        return -1;
+      }
+    }
+
+    ++s1;
+    ++s2;
+  }
+
+  return 0;
 }
 
 #endif
diff --git a/tests/test_linked_list.c b/tests/test_linked_list.c
index 7ec96b5..2c51625 100644
--- a/tests/test_linked_list.c
+++ b/tests/test_linked_list.c
@@ -60,3 +60,25 @@ TEST(linked_list, foreach)
 
   return 0;
 }
+
+TEST(linked_list, remove)
+{
+  linked_list_t(int) ll = LINKED_LIST_INIT;
+  linked_list_push_front(int)(&ll, 1);
+  linked_list_push_front(int)(&ll, 2);
+  linked_list_push_front(int)(&ll, 3);
+  linked_list_push_front(int)(&ll, 4);
+  linked_list_push_front(int)(&ll, 4);
+
+  int ec = linked_list_remove(int)(&ll, 4);
+  ASSERT_EQ(!!ec, 1);
+  ec = linked_list_remove(int)(&ll, 2);
+  ASSERT_EQ(!!ec, 1);
+  ec = linked_list_remove(int)(&ll, 1);
+  ASSERT_EQ(!!ec, 1);
+
+  ASSERT_EQ(linked_list_length(int)(&ll), 1);
+  ASSERT_EQ(*linked_list_front(int)(&ll), 3);
+
+  return 0;
+}