Mercurial > hg > ucx / changeset

--- a/src/linked_list.c	Tue Sep 28 18:22:00 2021 +0200
+++ b/src/linked_list.c	Tue Sep 28 18:33:42 2021 +0200
@@ -93,11 +93,12 @@
 
 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
 
-typedef struct {
-    void *prev;
-    void *next;
+typedef struct cx_linked_list_node cx_linked_list_node;
+struct cx_linked_list_node {
+    cx_linked_list_node *prev;
+    cx_linked_list_node *next;
     char payload[];
-} cx_linked_list_node;
+};
 
 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
@@ -131,6 +132,16 @@
     return 0;
 }
 
+static cx_linked_list_node *cx_ll_node_at(cx_linked_list* list, size_t index) {
+    if (index >= list->base.size) {
+        return NULL;
+    } else if (index > list->base.size / 2) {
+        return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index);
+    } else {
+        return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
+    }
+}
+
 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
     cx_linked_list *ll = (cx_linked_list *) list;
     // TODO: implement using low level API
@@ -138,24 +149,38 @@
 }
 
 static int cx_ll_remove(cx_list_s *list, size_t index) {
-    if (index >= list->size) {
-        return 1;
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_linked_list_node *node = cx_ll_node_at(ll, index);
+
+    // out-of-bounds check
+    if (node == NULL) return 1;
+
+    // change left side connection
+    if (node->prev == NULL) {
+        ll->begin = node->next;
+    } else {
+        node->prev->next = node->next;
     }
-    cx_linked_list *ll = (cx_linked_list *) list;
-    // TODO: implement using low level API
+
+    // change right side connection
+    if (node->next == NULL) {
+        ll->end = node->prev;
+    } else {
+        node->next->prev = node->prev;
+    }
+
+    // adjust size
+    list->size--;
+
+    // free and return
+    cxFree(list->allocator, node);
+
     return 0;
 }
 
 static void *cx_ll_at(cx_list_s *list, size_t index) {
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_node *node;
-    if (index >= list->size) {
-        node = NULL;
-    } else if (index > list->size / 2) {
-        node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index);
-    } else {
-        node = cx_linked_list_at(ll->begin, 0, CX_LL_LOC_NEXT, index);
-    }
+    cx_linked_list_node *node = cx_ll_node_at(ll, index);
     return node == NULL ? NULL : &node->payload;
 }