1.1 --- a/src/linked_list.c Tue Sep 28 18:33:42 2021 +0200 1.2 +++ b/src/linked_list.c Tue Sep 28 18:49:12 2021 +0200 1.3 @@ -109,30 +109,7 @@ 1.4 cx_linked_list_node *end; 1.5 } cx_linked_list; 1.6 1.7 -static int cx_ll_add(cx_list_s *list, void *elem) { 1.8 - cx_linked_list *ll = (cx_linked_list *) list; 1.9 - 1.10 - cx_linked_list_node *node = cxMalloc(list->allocator, 1.11 - sizeof(cx_linked_list_node) + list->itemsize); 1.12 - if (node == NULL) 1.13 - return 1; 1.14 - 1.15 - memcpy(node->payload, elem, list->itemsize); 1.16 - node->next = NULL; 1.17 - 1.18 - if (ll->begin == NULL) { 1.19 - ll->begin = ll->end = node; 1.20 - } else { 1.21 - // per contract of this linked list we know that end must be non-null 1.22 - ll->end->next = node; 1.23 - ll->end = node; 1.24 - } 1.25 - list->size++; 1.26 - 1.27 - return 0; 1.28 -} 1.29 - 1.30 -static cx_linked_list_node *cx_ll_node_at(cx_linked_list* list, size_t index) { 1.31 +static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { 1.32 if (index >= list->base.size) { 1.33 return NULL; 1.34 } else if (index > list->base.size / 2) { 1.35 @@ -143,9 +120,60 @@ 1.36 } 1.37 1.38 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 1.39 + // out-of bounds check 1.40 + if (index > list->size) return 1; 1.41 + 1.42 + // cast a linked list pointer 1.43 cx_linked_list *ll = (cx_linked_list *) list; 1.44 - // TODO: implement using low level API 1.45 - return 1; 1.46 + 1.47 + // create the new node 1.48 + cx_linked_list_node *node = cxMalloc(list->allocator, 1.49 + sizeof(cx_linked_list_node) + list->itemsize); 1.50 + 1.51 + // sortir if failed 1.52 + if (node == NULL) return 1; 1.53 + 1.54 + // copy payload to the new node 1.55 + memcpy(node->payload, elem, list->itemsize); 1.56 + 1.57 + // check if this is the first node 1.58 + if (ll->begin == NULL) { 1.59 + node->prev = node->next = NULL; 1.60 + ll->begin = ll->end = node; 1.61 + } else { 1.62 + // check if this shall be the new end node 1.63 + if (index == list->size) { 1.64 + ll->end->next = node; 1.65 + node->prev = ll->end; 1.66 + node->next = NULL; 1.67 + ll->end = node; 1.68 + } 1.69 + // check if this shall be the new start node 1.70 + else if (index == 0) { 1.71 + ll->begin->prev = node; 1.72 + node->next = ll->begin; 1.73 + node->prev = NULL; 1.74 + ll->begin = node; 1.75 + } else { 1.76 + // find the node at the current index 1.77 + cx_linked_list_node *cur = cx_ll_node_at(ll, index); 1.78 + 1.79 + // insert before that node 1.80 + // (we know all ptr are non-null because we handled all other cases before) 1.81 + node->next = cur; 1.82 + node->prev = cur->prev; 1.83 + cur->prev = node; 1.84 + node->prev->next = node; 1.85 + } 1.86 + } 1.87 + 1.88 + // increase the size and return 1.89 + list->size++; 1.90 + return 0; 1.91 +} 1.92 + 1.93 +static int cx_ll_add(cx_list_s *list, void *elem) { 1.94 + return cx_ll_insert(list, list->size, elem); 1.95 } 1.96 1.97 static int cx_ll_remove(cx_list_s *list, size_t index) {