From 282dc00e20ab5a8a0ec0a520933b18f5884a19e6 Mon Sep 17 00:00:00 2001
From: Matthew Fernandez <matthew.fernandez@gmail.com>
Date: Sun, 25 Dec 2022 14:22:38 -0800
Subject: [PATCH] cgraph: add remove-by-value functionality to the generic list

Note that this assumes elements can be compared using `memcmp` which is not true
for most aggregates. It is the responsibility of the caller to avoid using this
with types that cannot be compared in this way.
---
 lib/cgraph/list.h      | 28 +++++++++++++++
 lib/cgraph/test_list.c | 81 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 109 insertions(+)

diff --git a/lib/cgraph/list.h b/lib/cgraph/list.h
index f0415c162..55ed7072c 100644
--- a/lib/cgraph/list.h
+++ b/lib/cgraph/list.h
@@ -4,6 +4,7 @@
 #include <cgraph/alloc.h>
 #include <stdbool.h>
 #include <stdlib.h>
+#include <string.h>
 
 #ifdef __GNUC__
 #define LIST_UNUSED __attribute__((unused))
@@ -105,6 +106,33 @@
     list->data[index] = item;                                                  \
   }                                                                            \
                                                                                \
+  /** remove an element from a list                                            \
+   *                                                                           \
+   * \param list List to operate on                                            \
+   * \param item Value of element to remove                                    \
+   */                                                                          \
+  static inline LIST_UNUSED void name##_remove(name##_t *list, type item) {    \
+    assert(list != NULL);                                                      \
+                                                                               \
+    for (size_t i = 0; i < list->size; ++i) {                                  \
+      /* is this the element we are looking for? */                            \
+      if (memcmp(&list->data[i], &item, sizeof(type)) == 0) {                  \
+                                                                               \
+        /* destroy the element we are about to remove */                       \
+        void (*dtor_)(type) = (void (*)(type))(dtor);                          \
+        if (dtor_ != NULL) {                                                   \
+          dtor_(list->data[i]);                                                \
+        }                                                                      \
+                                                                               \
+        /* shrink the list */                                                  \
+        size_t remainder = (list->size - i - 1) * sizeof(type);                \
+        memmove(&list->data[i], &list->data[i + 1], remainder);                \
+        --list->size;                                                          \
+        return;                                                                \
+      }                                                                        \
+    }                                                                          \
+  }                                                                            \
+                                                                               \
   /** access an element in a list for the purpose of modification              \
    *                                                                           \
    * Because this acquires an internal pointer into the list structure, `get`  \
diff --git a/lib/cgraph/test_list.c b/lib/cgraph/test_list.c
index 1ffe47455..ad3274e6b 100644
--- a/lib/cgraph/test_list.c
+++ b/lib/cgraph/test_list.c
@@ -71,6 +71,70 @@ static void test_set(void) {
   ints_free(&xs);
 }
 
+/// removing from an empty list should be a no-op
+static void test_remove_empty(void) {
+  ints_t xs = {0};
+  ints_remove(&xs, 10);
+  assert(ints_size(&xs) == 0);
+  ints_free(&xs);
+}
+
+/// some basic removal tests
+static void test_remove(void) {
+  ints_t xs = {0};
+
+  for (size_t i = 0; i < 10; ++i) {
+    ints_append(&xs, (int)i);
+  }
+
+  // remove something that does not exist
+  ints_remove(&xs, 42);
+  for (size_t i = 0; i < 10; ++i) {
+    assert(ints_get(&xs, i) == (int)i);
+  }
+
+  // remove in the middle
+  ints_remove(&xs, 4);
+  assert(ints_size(&xs) == 9);
+  for (size_t i = 0; i < 9; ++i) {
+    if (i < 4) {
+      assert(ints_get(&xs, i) == (int)i);
+    } else {
+      assert(ints_get(&xs, i) == (int)i + 1);
+    }
+  }
+
+  // remove the first
+  ints_remove(&xs, 0);
+  assert(ints_size(&xs) == 8);
+  for (size_t i = 0; i < 8; ++i) {
+    if (i < 3) {
+      assert(ints_get(&xs, i) == (int)i + 1);
+    } else {
+      assert(ints_get(&xs, i) == (int)i + 2);
+    }
+  }
+
+  // remove the last
+  ints_remove(&xs, 9);
+  assert(ints_size(&xs) == 7);
+  for (size_t i = 0; i < 7; ++i) {
+    if (i < 3) {
+      assert(ints_get(&xs, i) == (int)i + 1);
+    } else {
+      assert(ints_get(&xs, i) == (int)i + 2);
+    }
+  }
+
+  // remove all the rest
+  for (size_t i = 0; i < 7; ++i) {
+    ints_remove(&xs, ints_get(&xs, 0));
+  }
+  assert(ints_size(&xs) == 0);
+
+  ints_free(&xs);
+}
+
 static void test_at(void) {
   ints_t xs = {0};
   for (size_t i = 0; i < 10; ++i) {
@@ -380,6 +444,20 @@ static void test_dtor(void) {
   strs_free(&xs);
 }
 
+/// test removal does not leak memory
+static void test_remove_with_dtor(void) {
+  strs_t xs = {0};
+
+  char *hello = strdup("hello");
+  assert(hello != NULL);
+
+  strs_append(&xs, hello);
+  strs_remove(&xs, hello);
+  assert(strs_size(&xs) == 0);
+
+  strs_free(&xs);
+}
+
 int main(void) {
 
 #define RUN(t)                                                                 \
@@ -394,6 +472,8 @@ int main(void) {
   RUN(append);
   RUN(get);
   RUN(set);
+  RUN(remove_empty);
+  RUN(remove);
   RUN(at);
   RUN(clear_empty);
   RUN(clear);
@@ -413,6 +493,7 @@ int main(void) {
   RUN(large);
   RUN(attach_detach);
   RUN(dtor);
+  RUN(remove_with_dtor);
 
 #undef RUN
 
-- 
2.40.0