Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Mon Dec 20 12:10:48 2021 +0100
     1.2 +++ b/src/cx/linked_list.h	Mon Dec 20 13:01:38 2021 +0100
     1.3 @@ -98,6 +98,22 @@
     1.4  __attribute__((__nonnull__));
     1.5  
     1.6  /**
     1.7 + * Finds the index of an element within a linked list.
     1.8 + *
     1.9 + * @param start a pointer to the start node
    1.10 + * @param loc_advance the location of the pointer to advance
    1.11 + * @param loc_data the location of the \c data pointer within your node struct
    1.12 + * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
    1.13 + * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
    1.14 + * @param cmp_func a compare function to compare \p elem against the node data
    1.15 + * @param elem a pointer to the element to find
    1.16 + * @return the index of the element or a past-one index if the element could not be found
    1.17 + */
    1.18 +size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
    1.19 +                           CxListComparator cmp_func, void *elem)
    1.20 +__attribute__((__nonnull__));
    1.21 +
    1.22 +/**
    1.23   * Finds the first node in a linked list.
    1.24   *
    1.25   * The function starts with the pointer denoted by \p node and traverses the list
    1.26 @@ -226,7 +242,7 @@
    1.27   * @param loc_next the location of a \c next pointer within your node struct (required)
    1.28   * @param loc_data the location of the \c data pointer within your node struct
    1.29   * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
    1.30 - * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func.
    1.31 + * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
    1.32   * @param cmp_func the compare function defining the sort order
    1.33   */
    1.34  void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,

     2.1 --- a/src/linked_list.c	Mon Dec 20 12:10:48 2021 +0100
     2.2 +++ b/src/linked_list.c	Mon Dec 20 13:01:38 2021 +0100
     2.3 @@ -34,6 +34,10 @@
     2.4  /* LOW LEVEL LINKED LIST FUNCTIONS */
     2.5  
     2.6  #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
     2.7 +#define ll_prev(node) CX_LL_PTR(node, loc_prev)
     2.8 +#define ll_next(node) CX_LL_PTR(node, loc_next)
     2.9 +#define ll_advance(node) CX_LL_PTR(node, loc_advance)
    2.10 +#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
    2.11  
    2.12  void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
    2.13      assert(start != NULL);
    2.14 @@ -41,12 +45,32 @@
    2.15      size_t i = start_index;
    2.16      void *cur = start;
    2.17      while (i != index && cur != NULL) {
    2.18 -        cur = CX_LL_PTR(cur, loc_advance);
    2.19 +        cur = ll_advance(cur);
    2.20          i < index ? i++ : i--;
    2.21      }
    2.22      return cur;
    2.23  }
    2.24  
    2.25 +size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
    2.26 +                           CxListComparator cmp_func, void *elem) {
    2.27 +    assert(start != NULL);
    2.28 +    assert(loc_advance >= 0);
    2.29 +    assert(loc_data >= 0);
    2.30 +    assert(cmp_func);
    2.31 +
    2.32 +    void *node = start;
    2.33 +    size_t index = 0;
    2.34 +    do {
    2.35 +        void *current = ll_data(node);
    2.36 +        if (cmp_func(current, elem) == 0) {
    2.37 +            return index;
    2.38 +        }
    2.39 +        node = ll_advance(node);
    2.40 +        index++;
    2.41 +    } while (node != NULL);
    2.42 +    return index;
    2.43 +}
    2.44 +
    2.45  void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
    2.46      return cx_linked_list_last(node, loc_prev);
    2.47  }
    2.48 @@ -59,7 +83,7 @@
    2.49      void *last;
    2.50      do {
    2.51          last = cur;
    2.52 -    } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
    2.53 +    } while ((cur = ll_next(cur)) != NULL);
    2.54  
    2.55      return last;
    2.56  }
    2.57 @@ -72,7 +96,7 @@
    2.58      void *cur = begin;
    2.59      void *next;
    2.60      while (1) {
    2.61 -        next = CX_LL_PTR(cur, loc_next);
    2.62 +        next = ll_next(cur);
    2.63          if (next == node) return cur;
    2.64          cur = next;
    2.65      }
    2.66 @@ -81,7 +105,7 @@
    2.67  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.68      assert(new_node != NULL);
    2.69      assert(loc_next >= 0);
    2.70 -    assert(CX_LL_PTR(new_node, loc_next) == NULL);
    2.71 +    assert(ll_next(new_node) == NULL);
    2.72      void *last;
    2.73      if (end == NULL) {
    2.74          assert(begin != NULL);
    2.75 @@ -95,7 +119,7 @@
    2.76          }
    2.77      } else {
    2.78          // if there is a last node, update its next pointer
    2.79 -        CX_LL_PTR(last, loc_next) = new_node;
    2.80 +        ll_next(last) = new_node;
    2.81      }
    2.82  
    2.83      // if there is an end pointer, update it
    2.84 @@ -105,15 +129,15 @@
    2.85  
    2.86      // if the nodes use a prev pointer, update it
    2.87      if (loc_prev >= 0) {
    2.88 -        assert(CX_LL_PTR(new_node, loc_prev) == NULL);
    2.89 -        CX_LL_PTR(new_node, loc_prev) = last;
    2.90 +        assert(ll_prev(new_node) == NULL);
    2.91 +        ll_prev(new_node) = last;
    2.92      }
    2.93  }
    2.94  
    2.95  void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.96      assert(new_node != NULL);
    2.97      assert(loc_next >= 0);
    2.98 -    assert(CX_LL_PTR(new_node, loc_next) == NULL);
    2.99 +    assert(ll_next(new_node) == NULL);
   2.100      void *first;
   2.101      if (begin == NULL) {
   2.102          assert(end != NULL);
   2.103 @@ -127,14 +151,14 @@
   2.104              *end = new_node;
   2.105          }
   2.106      } else {
   2.107 -        CX_LL_PTR(new_node, loc_next) = first;
   2.108 +        ll_next(new_node) = first;
   2.109          if (loc_prev >= 0) {
   2.110 -            CX_LL_PTR(first, loc_prev) = new_node;
   2.111 +            ll_prev(first) = new_node;
   2.112          }
   2.113      }
   2.114  
   2.115      if (begin != NULL) {
   2.116 -        assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
   2.117 +        assert(loc_prev < 0 || ll_prev(new_node) == NULL);
   2.118          *begin = new_node;
   2.119      }
   2.120  }
   2.121 @@ -145,10 +169,10 @@
   2.122      assert(loc_prev >= 0 || begin != NULL);
   2.123  
   2.124      // find adjacent nodes
   2.125 -    void *next = CX_LL_PTR(node, loc_next);
   2.126 +    void *next = ll_next(node);
   2.127      void *prev;
   2.128      if (loc_prev >= 0) {
   2.129 -        prev = CX_LL_PTR(node, loc_prev);
   2.130 +        prev = ll_prev(node);
   2.131      } else {
   2.132          prev = cx_linked_list_prev(*begin, loc_next, node);
   2.133      }
   2.134 @@ -159,7 +183,7 @@
   2.135              *begin = next;
   2.136          }
   2.137      } else {
   2.138 -        CX_LL_PTR(prev, loc_next) = next;
   2.139 +        ll_next(prev) = next;
   2.140      }
   2.141  
   2.142      // update prev pointer of next node, or set end
   2.143 @@ -168,7 +192,7 @@
   2.144              *end = prev;
   2.145          }
   2.146      } else if (loc_prev >= 0) {
   2.147 -        CX_LL_PTR(next, loc_prev) = prev;
   2.148 +        ll_prev(next) = prev;
   2.149      }
   2.150  }
   2.151  
   2.152 @@ -176,16 +200,12 @@
   2.153      assert(loc_next >= 0);
   2.154      size_t size = 0;
   2.155      while (node != NULL) {
   2.156 -        node = CX_LL_PTR(node, loc_next);
   2.157 +        node = ll_next(node);
   2.158          size++;
   2.159      }
   2.160      return size;
   2.161  }
   2.162  
   2.163 -#define ll_prev(node) CX_LL_PTR(node, loc_prev)
   2.164 -#define ll_next(node) CX_LL_PTR(node, loc_next)
   2.165 -#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
   2.166 -
   2.167  static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
   2.168                                         ptrdiff_t loc_data, int follow_ptr,
   2.169                                         size_t length, void *ls, void *le, void *re,
   2.170 @@ -290,9 +310,6 @@
   2.171      }
   2.172  }
   2.173  
   2.174 -#undef ll_next
   2.175 -#undef ll_data
   2.176 -
   2.177  void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
   2.178      assert(begin != NULL);
   2.179      assert(loc_next >= 0);
   2.180 @@ -301,11 +318,11 @@
   2.181      void *prev = NULL;
   2.182      void *cur = *begin;
   2.183      while (cur != NULL) {
   2.184 -        void *next = CX_LL_PTR(cur, loc_next);
   2.185 +        void *next = ll_next(cur);
   2.186  
   2.187 -        CX_LL_PTR(cur, loc_next) = prev;
   2.188 +        ll_next(cur) = prev;
   2.189          if (loc_prev >= 0) {
   2.190 -            CX_LL_PTR(cur, loc_prev) = next;
   2.191 +            ll_prev(cur) = next;
   2.192          }
   2.193  
   2.194          prev = cur;
   2.195 @@ -446,35 +463,15 @@
   2.196  }
   2.197  
   2.198  static size_t cx_ll_find(cx_list_s *list, void *elem) {
   2.199 -    CxListComparator cmp = list->cmpfunc;
   2.200 -    cx_linked_list *ll = (cx_linked_list *) list;
   2.201 -
   2.202 -    size_t index;
   2.203 -    cx_linked_list_node *node = ll->begin;
   2.204 -    for (index = 0; index < list->size; index++) {
   2.205 -        void *current = node->payload;
   2.206 -        if (cmp(current, elem) == 0) {
   2.207 -            return index;
   2.208 -        }
   2.209 -        node = node->next;
   2.210 -    }
   2.211 -    return index;
   2.212 +    return cx_linked_list_find(((cx_linked_list *) list)->begin,
   2.213 +                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   2.214 +                               0, list->cmpfunc, elem);
   2.215  }
   2.216  
   2.217  static size_t cx_pll_find(cx_list_s *list, void *elem) {
   2.218 -    CxListComparator cmp = list->cmpfunc;
   2.219 -    cx_linked_list *ll = (cx_linked_list *) list;
   2.220 -
   2.221 -    size_t index;
   2.222 -    cx_linked_list_node *node = ll->begin;
   2.223 -    for (index = 0; index < list->size; index++) {
   2.224 -        void *current = *(void **) node->payload;
   2.225 -        if (cmp(current, elem) == 0) {
   2.226 -            return index;
   2.227 -        }
   2.228 -        node = node->next;
   2.229 -    }
   2.230 -    return index;
   2.231 +    return cx_linked_list_find(((cx_linked_list *) list)->begin,
   2.232 +                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
   2.233 +                               1, list->cmpfunc, elem);
   2.234  }
   2.235  
   2.236  static void cx_ll_sort(cx_list_s *list) {