Mercurial > hg > ucx / changeset

     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) {