Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Mon Dec 20 13:01:38 2021 +0100
     1.2 +++ b/src/cx/linked_list.h	Thu Dec 23 15:20:50 2021 +0100
     1.3 @@ -55,7 +55,11 @@
     1.4   * @param item_size the size of each element in bytes
     1.5   * @return the created list
     1.6   */
     1.7 -CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
     1.8 +CxList cxLinkedListCreate(
     1.9 +        CxAllocator allocator,
    1.10 +        CxListComparator comparator,
    1.11 +        size_t item_size
    1.12 +);
    1.13  
    1.14  /**
    1.15   * Allocates a linked list for storing pointers.
    1.16 @@ -66,7 +70,10 @@
    1.17   * @param comparator the comparator for the elements
    1.18   * @return the created list
    1.19   */
    1.20 -CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator);
    1.21 +CxList cxPointerLinkedListCreate(
    1.22 +        CxAllocator allocator,
    1.23 +        CxListComparator comparator
    1.24 +);
    1.25  
    1.26  /**
    1.27   * Deallocates the memory of the entire list.
    1.28 @@ -94,8 +101,12 @@
    1.29   * @param index the search index
    1.30   * @return the node found at the specified index
    1.31   */
    1.32 -void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index)
    1.33 -__attribute__((__nonnull__));
    1.34 +void *cx_linked_list_at(
    1.35 +        void *start,
    1.36 +        size_t start_index,
    1.37 +        ptrdiff_t loc_advance,
    1.38 +        size_t index
    1.39 +) __attribute__((__nonnull__));
    1.40  
    1.41  /**
    1.42   * Finds the index of an element within a linked list.
    1.43 @@ -109,9 +120,14 @@
    1.44   * @param elem a pointer to the element to find
    1.45   * @return the index of the element or a past-one index if the element could not be found
    1.46   */
    1.47 -size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
    1.48 -                           CxListComparator cmp_func, void *elem)
    1.49 -__attribute__((__nonnull__));
    1.50 +size_t cx_linked_list_find(
    1.51 +        void *start,
    1.52 +        ptrdiff_t loc_advance,
    1.53 +        ptrdiff_t loc_data,
    1.54 +        int follow_ptr,
    1.55 +        CxListComparator cmp_func,
    1.56 +        void *elem
    1.57 +) __attribute__((__nonnull__));
    1.58  
    1.59  /**
    1.60   * Finds the first node in a linked list.
    1.61 @@ -123,8 +139,10 @@
    1.62   * @param node a pointer to a node in the list
    1.63   * @param loc_prev the location of the \c prev pointer
    1.64   */
    1.65 -void *cx_linked_list_first(void *node, ptrdiff_t loc_prev)
    1.66 -__attribute__((__nonnull__));
    1.67 +void *cx_linked_list_first(
    1.68 +        void *node,
    1.69 +        ptrdiff_t loc_prev
    1.70 +) __attribute__((__nonnull__));
    1.71  
    1.72  /**
    1.73   * Finds the last node in a linked list.
    1.74 @@ -137,8 +155,10 @@
    1.75   * @param loc_next the location of the \c next pointer
    1.76   * @return a pointer to the last node
    1.77   */
    1.78 -void *cx_linked_list_last(void *node, ptrdiff_t loc_next)
    1.79 -__attribute__((__nonnull__));
    1.80 +void *cx_linked_list_last(
    1.81 +        void *node,
    1.82 +        ptrdiff_t loc_next
    1.83 +) __attribute__((__nonnull__));
    1.84  
    1.85  /**
    1.86   * Finds the predecessor of a node in case it is not linked.
    1.87 @@ -150,8 +170,11 @@
    1.88   * @param node the successor of the node to find
    1.89   * @return the node or \c NULL if \p node has no predecessor
    1.90   */
    1.91 -void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node)
    1.92 -__attribute__((__nonnull__));
    1.93 +void *cx_linked_list_prev(
    1.94 +        void *begin,
    1.95 +        ptrdiff_t loc_next,
    1.96 +        void *node
    1.97 +) __attribute__((__nonnull__));
    1.98  
    1.99  /**
   1.100   * Adds a new node to a linked list.
   1.101 @@ -165,8 +188,13 @@
   1.102   * @param loc_next the location of a \c next pointer within your node struct (required)
   1.103   * @param new_node a pointer to the node that shall be appended
   1.104   */
   1.105 -void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node)
   1.106 -__attribute__((__nonnull__(5)));
   1.107 +void cx_linked_list_add(
   1.108 +        void **begin,
   1.109 +        void **end,
   1.110 +        ptrdiff_t loc_prev,
   1.111 +        ptrdiff_t loc_next,
   1.112 +        void *new_node
   1.113 +) __attribute__((__nonnull__(5)));
   1.114  
   1.115  /**
   1.116   * Prepends a new node to a linked list.
   1.117 @@ -180,8 +208,98 @@
   1.118   * @param loc_next the location of a \c next pointer within your node struct (required)
   1.119   * @param new_node a pointer to the node that shall be prepended
   1.120   */
   1.121 -void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node)
   1.122 -__attribute__((__nonnull__(5)));
   1.123 +void cx_linked_list_prepend(
   1.124 +        void **begin,
   1.125 +        void **end,
   1.126 +        ptrdiff_t loc_prev,
   1.127 +        ptrdiff_t loc_next,
   1.128 +        void *new_node
   1.129 +) __attribute__((__nonnull__(5)));
   1.130 +
   1.131 +/**
   1.132 + * Links two nodes.
   1.133 + *
   1.134 + * @param left the new predecessor of \p right
   1.135 + * @param right the new successor of \p left
   1.136 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
   1.137 + * @param loc_next the location of a \c next pointer within your node struct (required)
   1.138 + */
   1.139 +void cx_linked_list_link(
   1.140 +        void *left,
   1.141 +        void *right,
   1.142 +        ptrdiff_t loc_prev,
   1.143 +        ptrdiff_t loc_next
   1.144 +) __attribute__((__nonnull__));
   1.145 +
   1.146 +/**
   1.147 + * Unlinks two nodes.
   1.148 + *
   1.149 + * If right is not the successor of left, the behavior is undefined.
   1.150 + *
   1.151 + * @param left the predecessor of \p right
   1.152 + * @param right the successor of \p left
   1.153 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
   1.154 + * @param loc_next the location of a \c next pointer within your node struct (required)
   1.155 + */
   1.156 +void cx_linked_list_unlink(
   1.157 +        void *left,
   1.158 +        void *right,
   1.159 +        ptrdiff_t loc_prev,
   1.160 +        ptrdiff_t loc_next
   1.161 +) __attribute__((__nonnull__));
   1.162 +
   1.163 +/**
   1.164 + * Inserts a new node after a given node of a linked list.
   1.165 + * The new node must not be part of any list already.
   1.166 + *
   1.167 + * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
   1.168 + * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
   1.169 + *
   1.170 + * @param begin a pointer to the begin node pointer (if your list has one)
   1.171 + * @param end a pointer to the end node pointer (if your list has one)
   1.172 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
   1.173 + * @param loc_next the location of a \c next pointer within your node struct (required)
   1.174 + * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
   1.175 + * @param new_node a pointer to the node that shall be prepended
   1.176 + */
   1.177 +void cx_linked_list_insert(
   1.178 +        void **begin,
   1.179 +        void **end,
   1.180 +        ptrdiff_t loc_prev,
   1.181 +        ptrdiff_t loc_next,
   1.182 +        void *node,
   1.183 +        void *new_node
   1.184 +) __attribute__((__nonnull__(6)));
   1.185 +
   1.186 +/**
   1.187 + * Inserts a chain of nodes after a given node of a linked list.
   1.188 + * The chain must not be part of any list already.
   1.189 + *
   1.190 + * If you do not explicitly specify the end of the chain, it will be determined by traversing
   1.191 + * the \c next pointer.
   1.192 + *
   1.193 + * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
   1.194 + * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
   1.195 + * to provide a valid \p loc_prev location.
   1.196 + * Then the chain will be prepended to the list.
   1.197 + *
   1.198 + * @param begin a pointer to the begin node pointer (if your list has one)
   1.199 + * @param end a pointer to the end node pointer (if your list has one)
   1.200 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
   1.201 + * @param loc_next the location of a \c next pointer within your node struct (required)
   1.202 + * @param node the node after which to insert (\c NULL to prepend the chain to the list)
   1.203 + * @param insert_begin a pointer to the first node of the chain that shall be inserted
   1.204 + * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
   1.205 + */
   1.206 +void cx_linked_list_insert_chain(
   1.207 +        void **begin,
   1.208 +        void **end,
   1.209 +        ptrdiff_t loc_prev,
   1.210 +        ptrdiff_t loc_next,
   1.211 +        void *node,
   1.212 +        void *insert_begin,
   1.213 +        void *insert_end
   1.214 +) __attribute__((__nonnull__(6)));
   1.215  
   1.216  /**
   1.217   * Removes a node from the linked list.
   1.218 @@ -202,8 +320,13 @@
   1.219   * @param loc_next the location of a \c next pointer within your node struct (required)
   1.220   * @param node the node to remove
   1.221   */
   1.222 -void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node)
   1.223 -__attribute__((__nonnull__(5)));
   1.224 +void cx_linked_list_remove(
   1.225 +        void **begin,
   1.226 +        void **end,
   1.227 +        ptrdiff_t loc_prev,
   1.228 +        ptrdiff_t loc_next,
   1.229 +        void *node
   1.230 +) __attribute__((__nonnull__(5)));
   1.231  
   1.232  
   1.233  /**
   1.234 @@ -212,7 +335,10 @@
   1.235   * @param loc_next the location of the \c next pointer within the node struct
   1.236   * @return the size of the list or zero if \p node is \c NULL
   1.237   */
   1.238 -size_t cx_linked_list_size(void *node, ptrdiff_t loc_next);
   1.239 +size_t cx_linked_list_size(
   1.240 +        void *node,
   1.241 +        ptrdiff_t loc_next
   1.242 +);
   1.243  
   1.244  /**
   1.245   * Sorts a linked list based on a comparison function.
   1.246 @@ -245,10 +371,15 @@
   1.247   * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
   1.248   * @param cmp_func the compare function defining the sort order
   1.249   */
   1.250 -void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
   1.251 -                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func)
   1.252 -__attribute__((__nonnull__(1, 7)));
   1.253 -
   1.254 +void cx_linked_list_sort(
   1.255 +        void **begin,
   1.256 +        void **end,
   1.257 +        ptrdiff_t loc_prev,
   1.258 +        ptrdiff_t loc_next,
   1.259 +        ptrdiff_t loc_data,
   1.260 +        int follow_ptr,
   1.261 +        CxListComparator cmp_func
   1.262 +) __attribute__((__nonnull__(1, 7)));
   1.263  
   1.264  /**
   1.265   * Reverses the order of the nodes in a linked list.
   1.266 @@ -258,8 +389,12 @@
   1.267   * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
   1.268   * @param loc_next the location of a \c next pointer within your node struct (required)
   1.269   */
   1.270 -void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next)
   1.271 -__attribute__((__nonnull__(1)));
   1.272 +void cx_linked_list_reverse(
   1.273 +        void **begin,
   1.274 +        void **end,
   1.275 +        ptrdiff_t loc_prev,
   1.276 +        ptrdiff_t loc_next
   1.277 +) __attribute__((__nonnull__(1)));
   1.278  
   1.279  #ifdef __cplusplus
   1.280  } /* extern "C" */

     2.1 --- a/src/linked_list.c	Mon Dec 20 13:01:38 2021 +0100
     2.2 +++ b/src/linked_list.c	Thu Dec 23 15:20:50 2021 +0100
     2.3 @@ -39,7 +39,12 @@
     2.4  #define ll_advance(node) CX_LL_PTR(node, loc_advance)
     2.5  #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
     2.6  
     2.7 -void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     2.8 +void *cx_linked_list_at(
     2.9 +        void *start,
    2.10 +        size_t start_index,
    2.11 +        ptrdiff_t loc_advance,
    2.12 +        size_t index
    2.13 +) {
    2.14      assert(start != NULL);
    2.15      assert(loc_advance >= 0);
    2.16      size_t i = start_index;
    2.17 @@ -51,8 +56,14 @@
    2.18      return cur;
    2.19  }
    2.20  
    2.21 -size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
    2.22 -                           CxListComparator cmp_func, void *elem) {
    2.23 +size_t cx_linked_list_find(
    2.24 +        void *start,
    2.25 +        ptrdiff_t loc_advance,
    2.26 +        ptrdiff_t loc_data,
    2.27 +        int follow_ptr,
    2.28 +        CxListComparator cmp_func,
    2.29 +        void *elem
    2.30 +) {
    2.31      assert(start != NULL);
    2.32      assert(loc_advance >= 0);
    2.33      assert(loc_data >= 0);
    2.34 @@ -71,11 +82,17 @@
    2.35      return index;
    2.36  }
    2.37  
    2.38 -void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
    2.39 +void *cx_linked_list_first(
    2.40 +        void *node,
    2.41 +        ptrdiff_t loc_prev
    2.42 +) {
    2.43      return cx_linked_list_last(node, loc_prev);
    2.44  }
    2.45  
    2.46 -void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
    2.47 +void *cx_linked_list_last(
    2.48 +        void *node,
    2.49 +        ptrdiff_t loc_next
    2.50 +) {
    2.51      assert(node != NULL);
    2.52      assert(loc_next >= 0);
    2.53  
    2.54 @@ -88,7 +105,11 @@
    2.55      return last;
    2.56  }
    2.57  
    2.58 -void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
    2.59 +void *cx_linked_list_prev(
    2.60 +        void *begin,
    2.61 +        ptrdiff_t loc_next,
    2.62 +        void *node
    2.63 +) {
    2.64      assert(begin != NULL);
    2.65      assert(node != NULL);
    2.66      assert(loc_next >= 0);
    2.67 @@ -102,10 +123,41 @@
    2.68      }
    2.69  }
    2.70  
    2.71 -void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.72 -    assert(new_node != NULL);
    2.73 +void cx_linked_list_link(
    2.74 +        void *left,
    2.75 +        void *right,
    2.76 +        ptrdiff_t loc_prev,
    2.77 +        ptrdiff_t loc_next
    2.78 +) {
    2.79      assert(loc_next >= 0);
    2.80 -    assert(ll_next(new_node) == NULL);
    2.81 +    ll_next(left) = right;
    2.82 +    if (loc_prev >= 0) {
    2.83 +        ll_prev(right) = left;
    2.84 +    }
    2.85 +}
    2.86 +
    2.87 +void cx_linked_list_unlink(
    2.88 +        void *left,
    2.89 +        void *right,
    2.90 +        ptrdiff_t loc_prev,
    2.91 +        ptrdiff_t loc_next
    2.92 +) {
    2.93 +    assert (loc_next >= 0);
    2.94 +    assert(ll_next(left) == right);
    2.95 +    ll_next(left) = NULL;
    2.96 +    if (loc_prev >= 0) {
    2.97 +        assert(ll_prev(right) == left);
    2.98 +        ll_prev(right) = NULL;
    2.99 +    }
   2.100 +}
   2.101 +
   2.102 +void cx_linked_list_add(
   2.103 +        void **begin,
   2.104 +        void **end,
   2.105 +        ptrdiff_t loc_prev,
   2.106 +        ptrdiff_t loc_next,
   2.107 +        void *new_node
   2.108 +) {
   2.109      void *last;
   2.110      if (end == NULL) {
   2.111          assert(begin != NULL);
   2.112 @@ -113,57 +165,76 @@
   2.113      } else {
   2.114          last = *end;
   2.115      }
   2.116 -    if (last == NULL) {
   2.117 +    cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
   2.118 +}
   2.119 +
   2.120 +void cx_linked_list_prepend(
   2.121 +        void **begin,
   2.122 +        void **end,
   2.123 +        ptrdiff_t loc_prev,
   2.124 +        ptrdiff_t loc_next,
   2.125 +        void *new_node
   2.126 +) {
   2.127 +    cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
   2.128 +}
   2.129 +
   2.130 +void cx_linked_list_insert(
   2.131 +        void **begin,
   2.132 +        void **end,
   2.133 +        ptrdiff_t loc_prev,
   2.134 +        ptrdiff_t loc_next,
   2.135 +        void *node,
   2.136 +        void *new_node
   2.137 +) {
   2.138 +    cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
   2.139 +}
   2.140 +
   2.141 +void cx_linked_list_insert_chain(
   2.142 +        void **begin,
   2.143 +        void **end,
   2.144 +        ptrdiff_t loc_prev,
   2.145 +        ptrdiff_t loc_next,
   2.146 +        void *node,
   2.147 +        void *insert_begin,
   2.148 +        void *insert_end
   2.149 +) {
   2.150 +    // find the end of the chain, if not specified
   2.151 +    if (insert_end == NULL) {
   2.152 +        insert_end = cx_linked_list_last(insert_begin, loc_next);
   2.153 +    }
   2.154 +
   2.155 +    // determine the successor
   2.156 +    void *successor;
   2.157 +    if (node == NULL) {
   2.158 +        assert(begin != NULL || (end != NULL && loc_prev >= 0));
   2.159          if (begin != NULL) {
   2.160 -            *begin = new_node;
   2.161 +            successor = *begin;
   2.162 +            *begin = insert_begin;
   2.163 +        } else {
   2.164 +            successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
   2.165          }
   2.166      } else {
   2.167 -        // if there is a last node, update its next pointer
   2.168 -        ll_next(last) = new_node;
   2.169 +        successor = ll_next(node);
   2.170 +        cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
   2.171      }
   2.172  
   2.173 -    // if there is an end pointer, update it
   2.174 -    if (end != NULL) {
   2.175 -        *end = new_node;
   2.176 -    }
   2.177 -
   2.178 -    // if the nodes use a prev pointer, update it
   2.179 -    if (loc_prev >= 0) {
   2.180 -        assert(ll_prev(new_node) == NULL);
   2.181 -        ll_prev(new_node) = last;
   2.182 +    if (successor == NULL) {
   2.183 +        // the list ends with the new chain
   2.184 +        if (end != NULL) {
   2.185 +            *end = insert_end;
   2.186 +        }
   2.187 +    } else {
   2.188 +        cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
   2.189      }
   2.190  }
   2.191  
   2.192 -void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
   2.193 -    assert(new_node != NULL);
   2.194 -    assert(loc_next >= 0);
   2.195 -    assert(ll_next(new_node) == NULL);
   2.196 -    void *first;
   2.197 -    if (begin == NULL) {
   2.198 -        assert(end != NULL);
   2.199 -        assert(loc_prev >= 0);
   2.200 -        first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
   2.201 -    } else {
   2.202 -        first = *begin;
   2.203 -    }
   2.204 -    if (first == NULL) {
   2.205 -        if (end != NULL) {
   2.206 -            *end = new_node;
   2.207 -        }
   2.208 -    } else {
   2.209 -        ll_next(new_node) = first;
   2.210 -        if (loc_prev >= 0) {
   2.211 -            ll_prev(first) = new_node;
   2.212 -        }
   2.213 -    }
   2.214 -
   2.215 -    if (begin != NULL) {
   2.216 -        assert(loc_prev < 0 || ll_prev(new_node) == NULL);
   2.217 -        *begin = new_node;
   2.218 -    }
   2.219 -}
   2.220 -
   2.221 -void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
   2.222 +void cx_linked_list_remove(
   2.223 +        void **begin,
   2.224 +        void **end,
   2.225 +        ptrdiff_t loc_prev,
   2.226 +        ptrdiff_t loc_next,
   2.227 +        void *node
   2.228 +) {
   2.229      assert(node != NULL);
   2.230      assert(loc_next >= 0);
   2.231      assert(loc_prev >= 0 || begin != NULL);
   2.232 @@ -196,7 +267,10 @@
   2.233      }
   2.234  }
   2.235  
   2.236 -size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
   2.237 +size_t cx_linked_list_size(
   2.238 +        void *node,
   2.239 +        ptrdiff_t loc_next
   2.240 +) {
   2.241      assert(loc_next >= 0);
   2.242      size_t size = 0;
   2.243      while (node != NULL) {
   2.244 @@ -206,10 +280,17 @@
   2.245      return size;
   2.246  }
   2.247  
   2.248 -static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
   2.249 -                                       ptrdiff_t loc_data, int follow_ptr,
   2.250 -                                       size_t length, void *ls, void *le, void *re,
   2.251 -                                       CxListComparator cmp_func) {
   2.252 +static void *cx_linked_list_sort_merge(
   2.253 +        ptrdiff_t loc_prev,
   2.254 +        ptrdiff_t loc_next,
   2.255 +        ptrdiff_t loc_data,
   2.256 +        int follow_ptr,
   2.257 +        size_t length,
   2.258 +        void *ls,
   2.259 +        void *le,
   2.260 +        void *re,
   2.261 +        CxListComparator cmp_func
   2.262 +) {
   2.263      const size_t sbo_len = 1024;
   2.264      void *sbo[sbo_len];
   2.265      void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
   2.266 @@ -242,8 +323,7 @@
   2.267      // Update pointer
   2.268      if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
   2.269      for (size_t i = 0; i < length - 1; i++) {
   2.270 -        ll_next(sorted[i]) = sorted[i + 1];
   2.271 -        if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
   2.272 +        cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
   2.273      }
   2.274      ll_next(sorted[length - 1]) = NULL;
   2.275  
   2.276 @@ -255,8 +335,14 @@
   2.277  }
   2.278  
   2.279  void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
   2.280 -        void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
   2.281 -        ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
   2.282 +        void **begin,
   2.283 +        void **end,
   2.284 +        ptrdiff_t loc_prev,
   2.285 +        ptrdiff_t loc_next,
   2.286 +        ptrdiff_t loc_data,
   2.287 +        int follow_ptr,
   2.288 +        CxListComparator cmp_func
   2.289 +) {
   2.290      assert(begin != NULL);
   2.291      assert(loc_next >= 0);
   2.292      assert(loc_data >= 0);
   2.293 @@ -310,7 +396,12 @@
   2.294      }
   2.295  }
   2.296  
   2.297 -void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
   2.298 +void cx_linked_list_reverse(
   2.299 +        void **begin,
   2.300 +        void **end,
   2.301 +        ptrdiff_t loc_prev,
   2.302 +        ptrdiff_t loc_next
   2.303 +) {
   2.304      assert(begin != NULL);
   2.305      assert(loc_next >= 0);
   2.306  
   2.307 @@ -355,7 +446,10 @@
   2.308      cx_linked_list_node *end;
   2.309  } cx_linked_list;
   2.310  
   2.311 -static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
   2.312 +static cx_linked_list_node *cx_ll_node_at(
   2.313 +        cx_linked_list *list,
   2.314 +        size_t index
   2.315 +) {
   2.316      if (index >= list->base.size) {
   2.317          return NULL;
   2.318      } else if (index > list->base.size / 2) {
   2.319 @@ -365,72 +459,69 @@
   2.320      }
   2.321  }
   2.322  
   2.323 -static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
   2.324 +static int cx_ll_insert(
   2.325 +        cx_list_s *list,
   2.326 +        size_t index,
   2.327 +        void *elem
   2.328 +) {
   2.329      // out-of bounds check
   2.330      if (index > list->size) return 1;
   2.331  
   2.332      // cast a linked list pointer
   2.333      cx_linked_list *ll = (cx_linked_list *) list;
   2.334  
   2.335 -    // create the new node
   2.336 -    cx_linked_list_node *node = cxMalloc(list->allocator,
   2.337 -                                         sizeof(cx_linked_list_node) + list->itemsize);
   2.338 +    // create the new new_node
   2.339 +    cx_linked_list_node *new_node = cxMalloc(list->allocator,
   2.340 +                                             sizeof(cx_linked_list_node) + list->itemsize);
   2.341  
   2.342      // sortir if failed
   2.343 -    if (node == NULL) return 1;
   2.344 +    if (new_node == NULL) return 1;
   2.345  
   2.346 -    // copy payload to the new node
   2.347 -    memcpy(node->payload, elem, list->itemsize);
   2.348 +    // initialize new new_node
   2.349 +    new_node->prev = new_node->next = NULL;
   2.350 +    memcpy(new_node->payload, elem, list->itemsize);
   2.351  
   2.352 -    // check if this is the first node
   2.353 -    if (ll->begin == NULL) {
   2.354 -        node->prev = node->next = NULL;
   2.355 -        ll->begin = ll->end = node;
   2.356 -    } else {
   2.357 -        // check if this shall be the new end node
   2.358 -        if (index == list->size) {
   2.359 -            ll->end->next = node;
   2.360 -            node->prev = ll->end;
   2.361 -            node->next = NULL;
   2.362 -            ll->end = node;
   2.363 -        }
   2.364 -            // check if this shall be the new start node
   2.365 -        else if (index == 0) {
   2.366 -            ll->begin->prev = node;
   2.367 -            node->next = ll->begin;
   2.368 -            node->prev = NULL;
   2.369 -            ll->begin = node;
   2.370 -        } else {
   2.371 -            // find the node at the current index
   2.372 -            cx_linked_list_node *cur = cx_ll_node_at(ll, index);
   2.373 +    // find position efficiently
   2.374 +    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1);
   2.375  
   2.376 -            // insert before that node
   2.377 -            // (we know all ptr are non-null because we handled all other cases before)
   2.378 -            node->next = cur;
   2.379 -            node->prev = cur->prev;
   2.380 -            cur->prev = node;
   2.381 -            node->prev->next = node;
   2.382 -        }
   2.383 -    }
   2.384 +    // insert
   2.385 +    cx_linked_list_insert_chain(
   2.386 +            (void **) &ll->begin, (void **) &ll->end,
   2.387 +            CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
   2.388 +            node, new_node, new_node
   2.389 +    );
   2.390  
   2.391      // increase the size and return
   2.392      list->size++;
   2.393      return 0;
   2.394  }
   2.395  
   2.396 -static int cx_ll_add(cx_list_s *list, void *elem) {
   2.397 +static int cx_ll_add(
   2.398 +        cx_list_s *list,
   2.399 +        void *elem
   2.400 +) {
   2.401      return cx_ll_insert(list, list->size, elem);
   2.402  }
   2.403  
   2.404 -static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) {
   2.405 +static int cx_pll_insert(
   2.406 +        cx_list_s *list,
   2.407 +        size_t index,
   2.408 +        void *elem
   2.409 +) {
   2.410      return cx_ll_insert(list, index, &elem);
   2.411  }
   2.412  
   2.413 -static int cx_pll_add(cx_list_s *list, void *elem) {
   2.414 +static int cx_pll_add(
   2.415 +        cx_list_s *list,
   2.416 +        void *elem
   2.417 +) {
   2.418      return cx_ll_insert(list, list->size, &elem);
   2.419  }
   2.420  
   2.421 -static int cx_ll_remove(cx_list_s *list, size_t index) {
   2.422 +static int cx_ll_remove(
   2.423 +        cx_list_s *list,
   2.424 +        size_t index
   2.425 +) {
   2.426      cx_linked_list *ll = (cx_linked_list *) list;
   2.427      cx_linked_list_node *node = cx_ll_node_at(ll, index);
   2.428  
   2.429 @@ -450,25 +541,37 @@
   2.430      return 0;
   2.431  }
   2.432  
   2.433 -static void *cx_ll_at(cx_list_s *list, size_t index) {
   2.434 +static void *cx_ll_at(
   2.435 +        cx_list_s *list,
   2.436 +        size_t index
   2.437 +) {
   2.438      cx_linked_list *ll = (cx_linked_list *) list;
   2.439      cx_linked_list_node *node = cx_ll_node_at(ll, index);
   2.440      return node == NULL ? NULL : node->payload;
   2.441  }
   2.442  
   2.443 -static void *cx_pll_at(cx_list_s *list, size_t index) {
   2.444 +static void *cx_pll_at(
   2.445 +        cx_list_s *list,
   2.446 +        size_t index
   2.447 +) {
   2.448      cx_linked_list *ll = (cx_linked_list *) list;
   2.449      cx_linked_list_node *node = cx_ll_node_at(ll, index);
   2.450      return node == NULL ? NULL : *(void **) node->payload;
   2.451  }
   2.452  
   2.453 -static size_t cx_ll_find(cx_list_s *list, void *elem) {
   2.454 +static size_t cx_ll_find(
   2.455 +        cx_list_s *list,
   2.456 +        void *elem
   2.457 +) {
   2.458      return cx_linked_list_find(((cx_linked_list *) list)->begin,
   2.459                                 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   2.460                                 0, list->cmpfunc, elem);
   2.461  }
   2.462  
   2.463 -static size_t cx_pll_find(cx_list_s *list, void *elem) {
   2.464 +static size_t cx_pll_find(
   2.465 +        cx_list_s *list,
   2.466 +        void *elem
   2.467 +) {
   2.468      return cx_linked_list_find(((cx_linked_list *) list)->begin,
   2.469                                 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   2.470                                 1, list->cmpfunc, elem);
   2.471 @@ -506,7 +609,11 @@
   2.472          cx_pll_sort
   2.473  };
   2.474  
   2.475 -CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
   2.476 +CxList cxLinkedListCreate(
   2.477 +        CxAllocator allocator,
   2.478 +        CxListComparator comparator,
   2.479 +        size_t item_size
   2.480 +) {
   2.481      cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
   2.482      if (list == NULL)
   2.483          return NULL;
   2.484 @@ -524,7 +631,10 @@
   2.485      return (CxList) list;
   2.486  }
   2.487  
   2.488 -CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
   2.489 +CxList cxPointerLinkedListCreate(
   2.490 +        CxAllocator allocator,
   2.491 +        CxListComparator comparator
   2.492 +) {
   2.493      cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
   2.494      if (list == NULL)
   2.495          return NULL;