Mercurial > hg > ucx / changeset

--- a/src/linked_list.c	Tue Sep 28 18:33:42 2021 +0200
+++ b/src/linked_list.c	Tue Sep 28 18:49:12 2021 +0200
@@ -109,30 +109,7 @@
     cx_linked_list_node *end;
 } cx_linked_list;
 
-static int cx_ll_add(cx_list_s *list, void *elem) {
-    cx_linked_list *ll = (cx_linked_list *) list;
-
-    cx_linked_list_node *node = cxMalloc(list->allocator,
-                                         sizeof(cx_linked_list_node) + list->itemsize);
-    if (node == NULL)
-        return 1;
-
-    memcpy(node->payload, elem, list->itemsize);
-    node->next = NULL;
-
-    if (ll->begin == NULL) {
-        ll->begin = ll->end = node;
-    } else {
-        // per contract of this linked list we know that end must be non-null
-        ll->end->next = node;
-        ll->end = node;
-    }
-    list->size++;
-
-    return 0;
-}
-
-static cx_linked_list_node *cx_ll_node_at(cx_linked_list* list, size_t index) {
+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) {
@@ -143,9 +120,60 @@
 }
 
 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
+    // out-of bounds check
+    if (index > list->size) return 1;
+
+    // cast a linked list pointer
     cx_linked_list *ll = (cx_linked_list *) list;
-    // TODO: implement using low level API
-    return 1;
+
+    // create the new node
+    cx_linked_list_node *node = cxMalloc(list->allocator,
+                                         sizeof(cx_linked_list_node) + list->itemsize);
+
+    // sortir if failed
+    if (node == NULL) return 1;
+
+    // copy payload to the new node
+    memcpy(node->payload, elem, list->itemsize);
+
+    // check if this is the first node
+    if (ll->begin == NULL) {
+        node->prev = node->next = NULL;
+        ll->begin = ll->end = node;
+    } else {
+        // check if this shall be the new end node
+        if (index == list->size) {
+            ll->end->next = node;
+            node->prev = ll->end;
+            node->next = NULL;
+            ll->end = node;
+        }
+        // check if this shall be the new start node
+        else if (index == 0) {
+            ll->begin->prev = node;
+            node->next = ll->begin;
+            node->prev = NULL;
+            ll->begin = node;
+        } else {
+            // find the node at the current index
+            cx_linked_list_node *cur = cx_ll_node_at(ll, index);
+
+            // insert before that node
+            // (we know all ptr are non-null because we handled all other cases before)
+            node->next = cur;
+            node->prev = cur->prev;
+            cur->prev = node;
+            node->prev->next = node;
+        }
+    }
+
+    // increase the size and return
+    list->size++;
+    return 0;
+}
+
+static int cx_ll_add(cx_list_s *list, void *elem) {
+    return cx_ll_insert(list, list->size, elem);
 }
 
 static int cx_ll_remove(cx_list_s *list, size_t index) {