Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Mon Dec 20 12:10:48 2021 +0100
+++ b/src/cx/linked_list.h	Mon Dec 20 13:01:38 2021 +0100
@@ -98,6 +98,22 @@
 __attribute__((__nonnull__));
 
 /**
+ * Finds the index of an element within a linked list.
+ *
+ * @param start a pointer to the start node
+ * @param loc_advance the location of the pointer to advance
+ * @param loc_data the location of the \c data pointer within your node struct
+ * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
+ * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
+ * @param cmp_func a compare function to compare \p elem against the node data
+ * @param elem a pointer to the element to find
+ * @return the index of the element or a past-one index if the element could not be found
+ */
+size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
+                           CxListComparator cmp_func, void *elem)
+__attribute__((__nonnull__));
+
+/**
  * Finds the first node in a linked list.
  *
  * The function starts with the pointer denoted by \p node and traverses the list
@@ -226,7 +242,7 @@
  * @param loc_next the location of a \c next pointer within your node struct (required)
  * @param loc_data the location of the \c data pointer within your node struct
  * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
- * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func.
+ * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
  * @param cmp_func the compare function defining the sort order
  */
 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,

--- a/src/linked_list.c	Mon Dec 20 12:10:48 2021 +0100
+++ b/src/linked_list.c	Mon Dec 20 13:01:38 2021 +0100
@@ -34,6 +34,10 @@
 /* LOW LEVEL LINKED LIST FUNCTIONS */
 
 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
+#define ll_prev(node) CX_LL_PTR(node, loc_prev)
+#define ll_next(node) CX_LL_PTR(node, loc_next)
+#define ll_advance(node) CX_LL_PTR(node, loc_advance)
+#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
 
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     assert(start != NULL);
@@ -41,12 +45,32 @@
     size_t i = start_index;
     void *cur = start;
     while (i != index && cur != NULL) {
-        cur = CX_LL_PTR(cur, loc_advance);
+        cur = ll_advance(cur);
         i < index ? i++ : i--;
     }
     return cur;
 }
 
+size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
+                           CxListComparator cmp_func, void *elem) {
+    assert(start != NULL);
+    assert(loc_advance >= 0);
+    assert(loc_data >= 0);
+    assert(cmp_func);
+
+    void *node = start;
+    size_t index = 0;
+    do {
+        void *current = ll_data(node);
+        if (cmp_func(current, elem) == 0) {
+            return index;
+        }
+        node = ll_advance(node);
+        index++;
+    } while (node != NULL);
+    return index;
+}
+
 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
     return cx_linked_list_last(node, loc_prev);
 }
@@ -59,7 +83,7 @@
     void *last;
     do {
         last = cur;
-    } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
+    } while ((cur = ll_next(cur)) != NULL);
 
     return last;
 }
@@ -72,7 +96,7 @@
     void *cur = begin;
     void *next;
     while (1) {
-        next = CX_LL_PTR(cur, loc_next);
+        next = ll_next(cur);
         if (next == node) return cur;
         cur = next;
     }
@@ -81,7 +105,7 @@
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
     assert(new_node != NULL);
     assert(loc_next >= 0);
-    assert(CX_LL_PTR(new_node, loc_next) == NULL);
+    assert(ll_next(new_node) == NULL);
     void *last;
     if (end == NULL) {
         assert(begin != NULL);
@@ -95,7 +119,7 @@
         }
     } else {
         // if there is a last node, update its next pointer
-        CX_LL_PTR(last, loc_next) = new_node;
+        ll_next(last) = new_node;
     }
 
     // if there is an end pointer, update it
@@ -105,15 +129,15 @@
 
     // if the nodes use a prev pointer, update it
     if (loc_prev >= 0) {
-        assert(CX_LL_PTR(new_node, loc_prev) == NULL);
-        CX_LL_PTR(new_node, loc_prev) = last;
+        assert(ll_prev(new_node) == NULL);
+        ll_prev(new_node) = last;
     }
 }
 
 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
     assert(new_node != NULL);
     assert(loc_next >= 0);
-    assert(CX_LL_PTR(new_node, loc_next) == NULL);
+    assert(ll_next(new_node) == NULL);
     void *first;
     if (begin == NULL) {
         assert(end != NULL);
@@ -127,14 +151,14 @@
             *end = new_node;
         }
     } else {
-        CX_LL_PTR(new_node, loc_next) = first;
+        ll_next(new_node) = first;
         if (loc_prev >= 0) {
-            CX_LL_PTR(first, loc_prev) = new_node;
+            ll_prev(first) = new_node;
         }
     }
 
     if (begin != NULL) {
-        assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
+        assert(loc_prev < 0 || ll_prev(new_node) == NULL);
         *begin = new_node;
     }
 }
@@ -145,10 +169,10 @@
     assert(loc_prev >= 0 || begin != NULL);
 
     // find adjacent nodes
-    void *next = CX_LL_PTR(node, loc_next);
+    void *next = ll_next(node);
     void *prev;
     if (loc_prev >= 0) {
-        prev = CX_LL_PTR(node, loc_prev);
+        prev = ll_prev(node);
     } else {
         prev = cx_linked_list_prev(*begin, loc_next, node);
     }
@@ -159,7 +183,7 @@
             *begin = next;
         }
     } else {
-        CX_LL_PTR(prev, loc_next) = next;
+        ll_next(prev) = next;
     }
 
     // update prev pointer of next node, or set end
@@ -168,7 +192,7 @@
             *end = prev;
         }
     } else if (loc_prev >= 0) {
-        CX_LL_PTR(next, loc_prev) = prev;
+        ll_prev(next) = prev;
     }
 }
 
@@ -176,16 +200,12 @@
     assert(loc_next >= 0);
     size_t size = 0;
     while (node != NULL) {
-        node = CX_LL_PTR(node, loc_next);
+        node = ll_next(node);
         size++;
     }
     return size;
 }
 
-#define ll_prev(node) CX_LL_PTR(node, loc_prev)
-#define ll_next(node) CX_LL_PTR(node, loc_next)
-#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
-
 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
                                        ptrdiff_t loc_data, int follow_ptr,
                                        size_t length, void *ls, void *le, void *re,
@@ -290,9 +310,6 @@
     }
 }
 
-#undef ll_next
-#undef ll_data
-
 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
     assert(begin != NULL);
     assert(loc_next >= 0);
@@ -301,11 +318,11 @@
     void *prev = NULL;
     void *cur = *begin;
     while (cur != NULL) {
-        void *next = CX_LL_PTR(cur, loc_next);
+        void *next = ll_next(cur);
 
-        CX_LL_PTR(cur, loc_next) = prev;
+        ll_next(cur) = prev;
         if (loc_prev >= 0) {
-            CX_LL_PTR(cur, loc_prev) = next;
+            ll_prev(cur) = next;
         }
 
         prev = cur;
@@ -446,35 +463,15 @@
 }
 
 static size_t cx_ll_find(cx_list_s *list, void *elem) {
-    CxListComparator cmp = list->cmpfunc;
-    cx_linked_list *ll = (cx_linked_list *) list;
-
-    size_t index;
-    cx_linked_list_node *node = ll->begin;
-    for (index = 0; index < list->size; index++) {
-        void *current = node->payload;
-        if (cmp(current, elem) == 0) {
-            return index;
-        }
-        node = node->next;
-    }
-    return index;
+    return cx_linked_list_find(((cx_linked_list *) list)->begin,
+                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                               0, list->cmpfunc, elem);
 }
 
 static size_t cx_pll_find(cx_list_s *list, void *elem) {
-    CxListComparator cmp = list->cmpfunc;
-    cx_linked_list *ll = (cx_linked_list *) list;
-
-    size_t index;
-    cx_linked_list_node *node = ll->begin;
-    for (index = 0; index < list->size; index++) {
-        void *current = *(void **) node->payload;
-        if (cmp(current, elem) == 0) {
-            return index;
-        }
-        node = node->next;
-    }
-    return index;
+    return cx_linked_list_find(((cx_linked_list *) list)->begin,
+                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                               1, list->cmpfunc, elem);
 }
 
 static void cx_ll_sort(cx_list_s *list) {