implement cx_ll_remove()

Tue, 28 Sep 2021 18:33:42 +0200

author
Mike Becker <universe@uap-core.de>
date
Tue, 28 Sep 2021 18:33:42 +0200
changeset 447
87b2cdd668ed
parent 446
668757098b73
child 448
37c5d2fdb36b

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  

mercurial