# HG changeset patch # User Mike Becker # Date 1640001698 -3600 # Node ID e3be53a3354fe9c4402f4e3327c332fa7afbc1d9 # Parent a29bdd703e02fef42e51bf9561c11b4d51eceb48 add cx_linked_list_find() diff -r a29bdd703e02 -r e3be53a3354f src/cx/linked_list.h --- 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, diff -r a29bdd703e02 -r e3be53a3354f src/linked_list.c --- 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) {