Tue, 28 Sep 2021 18:33:42 +0200
implement cx_ll_remove()
src/linked_list.c | file | annotate | diff | comparison | revisions |
1.1 --- a/src/linked_list.c Tue Sep 28 18:22:00 2021 +0200 1.2 +++ b/src/linked_list.c Tue Sep 28 18:33:42 2021 +0200 1.3 @@ -93,11 +93,12 @@ 1.4 1.5 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 1.6 1.7 -typedef struct { 1.8 - void *prev; 1.9 - void *next; 1.10 +typedef struct cx_linked_list_node cx_linked_list_node; 1.11 +struct cx_linked_list_node { 1.12 + cx_linked_list_node *prev; 1.13 + cx_linked_list_node *next; 1.14 char payload[]; 1.15 -} cx_linked_list_node; 1.16 +}; 1.17 1.18 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) 1.19 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) 1.20 @@ -131,6 +132,16 @@ 1.21 return 0; 1.22 } 1.23 1.24 +static cx_linked_list_node *cx_ll_node_at(cx_linked_list* list, size_t index) { 1.25 + if (index >= list->base.size) { 1.26 + return NULL; 1.27 + } else if (index > list->base.size / 2) { 1.28 + return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index); 1.29 + } else { 1.30 + return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 1.31 + } 1.32 +} 1.33 + 1.34 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 1.35 cx_linked_list *ll = (cx_linked_list *) list; 1.36 // TODO: implement using low level API 1.37 @@ -138,24 +149,38 @@ 1.38 } 1.39 1.40 static int cx_ll_remove(cx_list_s *list, size_t index) { 1.41 - if (index >= list->size) { 1.42 - return 1; 1.43 + cx_linked_list *ll = (cx_linked_list *) list; 1.44 + cx_linked_list_node *node = cx_ll_node_at(ll, index); 1.45 + 1.46 + // out-of-bounds check 1.47 + if (node == NULL) return 1; 1.48 + 1.49 + // change left side connection 1.50 + if (node->prev == NULL) { 1.51 + ll->begin = node->next; 1.52 + } else { 1.53 + node->prev->next = node->next; 1.54 } 1.55 - cx_linked_list *ll = (cx_linked_list *) list; 1.56 - // TODO: implement using low level API 1.57 + 1.58 + // change right side connection 1.59 + if (node->next == NULL) { 1.60 + ll->end = node->prev; 1.61 + } else { 1.62 + node->next->prev = node->prev; 1.63 + } 1.64 + 1.65 + // adjust size 1.66 + list->size--; 1.67 + 1.68 + // free and return 1.69 + cxFree(list->allocator, node); 1.70 + 1.71 return 0; 1.72 } 1.73 1.74 static void *cx_ll_at(cx_list_s *list, size_t index) { 1.75 cx_linked_list *ll = (cx_linked_list *) list; 1.76 - cx_linked_list_node *node; 1.77 - if (index >= list->size) { 1.78 - node = NULL; 1.79 - } else if (index > list->size / 2) { 1.80 - node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index); 1.81 - } else { 1.82 - node = cx_linked_list_at(ll->begin, 0, CX_LL_LOC_NEXT, index); 1.83 - } 1.84 + cx_linked_list_node *node = cx_ll_node_at(ll, index); 1.85 return node == NULL ? NULL : &node->payload; 1.86 } 1.87