universe@398: /* universe@398: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@398: * universe@398: * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. universe@398: * universe@398: * Redistribution and use in source and binary forms, with or without universe@398: * modification, are permitted provided that the following conditions are met: universe@398: * universe@398: * 1. Redistributions of source code must retain the above copyright universe@398: * notice, this list of conditions and the following disclaimer. universe@398: * universe@398: * 2. Redistributions in binary form must reproduce the above copyright universe@398: * notice, this list of conditions and the following disclaimer in the universe@398: * documentation and/or other materials provided with the distribution. universe@398: * universe@398: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@398: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@398: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@398: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@398: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@398: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@398: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@398: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@398: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@398: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@398: * POSSIBILITY OF SUCH DAMAGE. universe@398: */ universe@398: universe@398: #include "cx/linked_list.h" universe@401: #include universe@401: #include universe@453: #include universe@398: universe@398: /* LOW LEVEL LINKED LIST FUNCTIONS */ universe@398: universe@468: #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off)) universe@398: universe@438: void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { universe@473: assert(start != NULL); universe@473: assert(loc_advance >= 0); universe@438: size_t i = start_index; universe@446: void *cur = start; universe@438: while (i != index && cur != NULL) { universe@468: cur = CX_LL_PTR(cur, loc_advance); universe@438: i < index ? i++ : i--; universe@438: } universe@438: return cur; universe@438: } universe@438: universe@456: void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) { universe@473: assert(loc_next >= 0); universe@456: if (begin == NULL) universe@456: return NULL; universe@398: universe@456: void *cur = begin; universe@456: void *last; universe@456: do { universe@456: last = cur; universe@468: } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); universe@398: universe@456: return last; universe@398: } universe@398: universe@473: void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) { universe@473: assert(begin != NULL); universe@473: assert(loc_next >= 0); universe@473: if (begin == node) return NULL; universe@473: void *cur = begin; universe@473: void *next; universe@473: while (1) { universe@473: next = CX_LL_PTR(cur, loc_next); universe@473: if (next == node) return cur; universe@473: cur = next; universe@473: } universe@473: } universe@473: universe@453: void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { universe@473: assert(loc_next >= 0); universe@456: void *last; universe@456: if (end == NULL) { universe@456: assert(begin != NULL); universe@456: last = cx_linked_list_last(*begin, loc_next); universe@456: } else { universe@456: last = *end; universe@456: } universe@398: if (last == NULL) { universe@453: assert(begin != NULL); universe@453: *begin = new_node; universe@428: } else { universe@428: // if there is a last node, update its next pointer universe@468: CX_LL_PTR(last, loc_next) = new_node; universe@398: } universe@398: universe@428: // if there is an end pointer, update it universe@408: if (end != NULL) { universe@456: *end = cx_linked_list_last(new_node, loc_next); universe@408: } universe@428: universe@428: // if the nodes use a prev pointer, update it universe@398: if (loc_prev >= 0) { universe@468: CX_LL_PTR(new_node, loc_prev) = last; universe@398: } universe@398: } universe@398: universe@473: void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { universe@473: assert(loc_next >= 0); universe@473: assert(loc_prev >= 0 || begin != NULL); universe@473: universe@473: // find adjacent nodes universe@473: void *next = CX_LL_PTR(node, loc_next); universe@473: void *prev; universe@473: if (loc_prev >= 0) { universe@473: prev = CX_LL_PTR(node, loc_prev); universe@473: } else { universe@473: prev = cx_linked_list_prev(*begin, loc_next, node); universe@473: } universe@473: universe@473: // update links of adjacent nodes universe@473: if (prev != NULL) { universe@473: CX_LL_PTR(prev, loc_next) = next; universe@473: } universe@473: if (next != NULL && loc_prev >= 0) { universe@473: CX_LL_PTR(next, loc_prev) = prev; universe@473: } universe@473: universe@473: // erase links of the target node universe@473: CX_LL_PTR(node, loc_next) = NULL; universe@473: if (loc_prev >= 0) { universe@473: CX_LL_PTR(node, loc_prev) = NULL; universe@473: } universe@473: universe@473: // update begin, if required universe@473: if (*begin == node) { universe@473: *begin = next; universe@473: } universe@473: universe@473: // update end, if required universe@473: if (end != NULL && *end == node) { universe@473: *end = prev; universe@473: } universe@473: universe@473: return prev == NULL ? next : prev; universe@473: } universe@473: universe@468: size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { universe@473: assert(loc_next >= 0); universe@468: size_t size = 0; universe@468: while (node != NULL) { universe@468: node = CX_LL_PTR(node, loc_next); universe@468: size++; universe@468: } universe@468: return size; universe@468: } universe@468: universe@468: #define ll_prev(node) CX_LL_PTR(node, loc_prev) universe@468: #define ll_next(node) CX_LL_PTR(node, loc_next) universe@468: #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) universe@468: universe@468: static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, universe@468: ptrdiff_t loc_data, int follow_ptr, universe@468: size_t length, void *ls, void *le, void *re, universe@468: CxListComparator cmp_func) { universe@468: const size_t sbo_len = 1024; universe@468: void *sbo[sbo_len]; universe@468: void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; universe@468: void *rc, *lc; universe@468: universe@468: lc = ls; universe@468: rc = le; universe@468: size_t n = 0; universe@468: while (lc && lc != le && rc != re) { universe@468: if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { universe@468: sorted[n] = lc; universe@468: lc = ll_next(lc); universe@468: } else { universe@468: sorted[n] = rc; universe@468: rc = ll_next(rc); universe@468: } universe@468: n++; universe@468: } universe@468: while (lc && lc != le) { universe@468: sorted[n] = lc; universe@468: lc = ll_next(lc); universe@468: n++; universe@468: } universe@468: while (rc && rc != re) { universe@468: sorted[n] = rc; universe@468: rc = ll_next(rc); universe@468: n++; universe@468: } universe@468: universe@468: // Update pointer universe@468: if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; universe@468: for (size_t i = 0; i < length - 1; i++) { universe@468: ll_next(sorted[i]) = sorted[i + 1]; universe@468: if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i]; universe@468: } universe@468: ll_next(sorted[length - 1]) = NULL; universe@468: universe@468: void *ret = sorted[0]; universe@468: if (sorted != sbo) { universe@468: free(sorted); universe@468: } universe@468: return ret; universe@468: } universe@468: universe@468: void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, universe@468: ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { universe@468: assert(begin != NULL); universe@473: assert(loc_next >= 0); universe@473: assert(loc_data >= 0); universe@473: assert(cmp_func); universe@468: universe@468: void *lc, *ls, *le, *re; universe@468: universe@468: // set start node universe@468: ls = *begin; universe@468: universe@468: // check how many elements are already sorted universe@468: lc = ls; universe@468: size_t ln = 1; universe@468: while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { universe@468: lc = ll_next(lc); universe@468: ln++; universe@468: } universe@468: le = ll_next(lc); universe@468: universe@468: // if first unsorted node is NULL, the list is already completely sorted universe@468: if (le != NULL) { universe@468: void *rc; universe@468: size_t rn = 1; universe@468: rc = le; universe@468: // skip already sorted elements universe@468: while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { universe@468: rc = ll_next(rc); universe@468: rn++; universe@468: } universe@468: re = ll_next(rc); universe@468: universe@468: // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them universe@468: void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, universe@468: ln + rn, ls, le, re, cmp_func); universe@468: universe@468: // Something left? Sort it! universe@468: size_t remainder_length = cx_linked_list_size(re, loc_next); universe@468: if (remainder_length > 0) { universe@468: void *remainder = re; universe@468: cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); universe@468: universe@468: // merge sorted list with (also sorted) remainder universe@468: *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, universe@468: ln + rn + remainder_length, universe@468: sorted, remainder, NULL, cmp_func); universe@468: } else { universe@468: // no remainder - we've got our sorted list universe@468: *begin = sorted; universe@468: } universe@468: if (end) *end = cx_linked_list_last(sorted, loc_next); universe@468: } universe@468: } universe@468: universe@468: #undef ll_next universe@468: #undef ll_data universe@468: universe@473: void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { universe@473: assert(begin != NULL); universe@473: assert(loc_next >= 0); universe@473: universe@473: // swap all links universe@473: void *prev = NULL; universe@473: void *cur = *begin; universe@473: while (cur != NULL) { universe@473: void *next = CX_LL_PTR(cur, loc_next); universe@473: universe@473: CX_LL_PTR(cur, loc_next) = prev; universe@473: if (loc_prev >= 0) { universe@473: CX_LL_PTR(cur, loc_prev) = next; universe@473: } universe@473: universe@473: prev = cur; universe@473: cur = next; universe@473: } universe@473: universe@473: // update begin and end universe@473: if (end != NULL) { universe@473: *end = *begin; universe@473: } universe@473: *begin = prev; universe@473: } universe@473: universe@398: /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ universe@398: universe@447: typedef struct cx_linked_list_node cx_linked_list_node; universe@447: struct cx_linked_list_node { universe@447: cx_linked_list_node *prev; universe@447: cx_linked_list_node *next; universe@403: char payload[]; universe@447: }; universe@402: universe@446: #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) universe@446: #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) universe@469: #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) universe@439: universe@398: typedef struct { universe@435: cx_list_s base; universe@446: cx_linked_list_node *begin; universe@446: cx_linked_list_node *end; universe@398: } cx_linked_list; universe@398: universe@448: static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { universe@447: if (index >= list->base.size) { universe@447: return NULL; universe@447: } else if (index > list->base.size / 2) { universe@468: return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); universe@447: } else { universe@447: return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); universe@447: } universe@447: } universe@447: universe@438: static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { universe@448: // out-of bounds check universe@448: if (index > list->size) return 1; universe@448: universe@448: // cast a linked list pointer universe@437: cx_linked_list *ll = (cx_linked_list *) list; universe@448: universe@448: // create the new node universe@448: cx_linked_list_node *node = cxMalloc(list->allocator, universe@448: sizeof(cx_linked_list_node) + list->itemsize); universe@448: universe@448: // sortir if failed universe@448: if (node == NULL) return 1; universe@448: universe@448: // copy payload to the new node universe@448: memcpy(node->payload, elem, list->itemsize); universe@448: universe@448: // check if this is the first node universe@448: if (ll->begin == NULL) { universe@448: node->prev = node->next = NULL; universe@448: ll->begin = ll->end = node; universe@448: } else { universe@448: // check if this shall be the new end node universe@448: if (index == list->size) { universe@448: ll->end->next = node; universe@448: node->prev = ll->end; universe@448: node->next = NULL; universe@448: ll->end = node; universe@448: } universe@468: // check if this shall be the new start node universe@448: else if (index == 0) { universe@448: ll->begin->prev = node; universe@448: node->next = ll->begin; universe@448: node->prev = NULL; universe@448: ll->begin = node; universe@448: } else { universe@448: // find the node at the current index universe@448: cx_linked_list_node *cur = cx_ll_node_at(ll, index); universe@448: universe@448: // insert before that node universe@448: // (we know all ptr are non-null because we handled all other cases before) universe@448: node->next = cur; universe@448: node->prev = cur->prev; universe@448: cur->prev = node; universe@448: node->prev->next = node; universe@448: } universe@448: } universe@448: universe@448: // increase the size and return universe@448: list->size++; universe@448: return 0; universe@448: } universe@448: universe@448: static int cx_ll_add(cx_list_s *list, void *elem) { universe@448: return cx_ll_insert(list, list->size, elem); universe@398: } universe@398: universe@466: static int cx_pll_insert(cx_list_s *list, size_t index, void *elem) { universe@466: return cx_ll_insert(list, index, &elem); universe@466: } universe@466: universe@466: static int cx_pll_add(cx_list_s *list, void *elem) { universe@466: return cx_ll_insert(list, list->size, &elem); universe@466: } universe@466: universe@438: static int cx_ll_remove(cx_list_s *list, size_t index) { universe@447: cx_linked_list *ll = (cx_linked_list *) list; universe@447: cx_linked_list_node *node = cx_ll_node_at(ll, index); universe@447: universe@447: // out-of-bounds check universe@447: if (node == NULL) return 1; universe@447: universe@447: // change left side connection universe@447: if (node->prev == NULL) { universe@447: ll->begin = node->next; universe@447: } else { universe@447: node->prev->next = node->next; universe@438: } universe@447: universe@447: // change right side connection universe@447: if (node->next == NULL) { universe@447: ll->end = node->prev; universe@447: } else { universe@447: node->next->prev = node->prev; universe@447: } universe@447: universe@447: // adjust size universe@447: list->size--; universe@447: universe@447: // free and return universe@447: cxFree(list->allocator, node); universe@447: universe@438: return 0; universe@398: } universe@398: universe@439: static void *cx_ll_at(cx_list_s *list, size_t index) { universe@439: cx_linked_list *ll = (cx_linked_list *) list; universe@447: cx_linked_list_node *node = cx_ll_node_at(ll, index); universe@466: return node == NULL ? NULL : node->payload; universe@466: } universe@466: universe@466: static void *cx_pll_at(cx_list_s *list, size_t index) { universe@466: cx_linked_list *ll = (cx_linked_list *) list; universe@466: cx_linked_list_node *node = cx_ll_node_at(ll, index); universe@468: return node == NULL ? NULL : *(void **) node->payload; universe@439: } universe@439: universe@438: static size_t cx_ll_find(cx_list_s *list, void *elem) { universe@437: CxListComparator cmp = list->cmpfunc; universe@437: cx_linked_list *ll = (cx_linked_list *) list; universe@437: universe@437: size_t index; universe@446: cx_linked_list_node *node = ll->begin; universe@446: for (index = 0; index < list->size; index++) { universe@446: void *current = node->payload; universe@437: if (cmp(current, elem) == 0) { universe@437: return index; universe@437: } universe@437: node = node->next; universe@437: } universe@437: return index; universe@398: } universe@398: universe@466: static size_t cx_pll_find(cx_list_s *list, void *elem) { universe@466: CxListComparator cmp = list->cmpfunc; universe@466: cx_linked_list *ll = (cx_linked_list *) list; universe@466: universe@466: size_t index; universe@466: cx_linked_list_node *node = ll->begin; universe@466: for (index = 0; index < list->size; index++) { universe@468: void *current = *(void **) node->payload; universe@466: if (cmp(current, elem) == 0) { universe@466: return index; universe@466: } universe@466: node = node->next; universe@466: } universe@466: return index; universe@466: } universe@466: universe@438: static void *cx_ll_last(cx_list_s *list) { universe@439: cx_linked_list *ll = (cx_linked_list *) list; universe@456: cx_linked_list_node *last = ll->end; universe@466: return last == NULL ? NULL : last->payload; universe@466: } universe@466: universe@466: static void *cx_pll_last(cx_list_s *list) { universe@466: cx_linked_list *ll = (cx_linked_list *) list; universe@466: cx_linked_list_node *last = ll->end; universe@468: return last == NULL ? NULL : *(void **) last->payload; universe@404: } universe@398: universe@469: static void cx_ll_sort(cx_list_s *list) { universe@469: cx_linked_list *ll = (cx_linked_list *) list; universe@469: cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, universe@469: CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, universe@469: 0, list->cmpfunc); universe@469: } universe@469: universe@469: static void cx_pll_sort(cx_list_s *list) { universe@469: cx_linked_list *ll = (cx_linked_list *) list; universe@469: cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, universe@469: CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, universe@469: 1, list->cmpfunc); universe@469: } universe@469: universe@451: static cx_list_class cx_linked_list_class = { universe@398: cx_ll_add, universe@398: cx_ll_insert, universe@398: cx_ll_remove, universe@439: cx_ll_at, universe@404: cx_ll_find, universe@469: cx_ll_last, universe@469: cx_ll_sort universe@398: }; universe@398: universe@466: static cx_list_class cx_pointer_linked_list_class = { universe@466: cx_pll_add, universe@466: cx_pll_insert, universe@466: cx_ll_remove, universe@466: cx_pll_at, universe@466: cx_pll_find, universe@469: cx_pll_last, universe@469: cx_pll_sort universe@466: }; universe@466: universe@406: CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { universe@446: cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); universe@398: if (list == NULL) universe@398: return NULL; universe@398: universe@435: list->base.cl = &cx_linked_list_class; universe@435: list->base.allocator = allocator; universe@435: list->base.cmpfunc = comparator; universe@435: list->base.itemsize = item_size; universe@435: list->base.capacity = SIZE_MAX; universe@441: list->base.size = 0; universe@406: universe@435: list->begin = NULL; universe@441: list->end = NULL; universe@406: universe@441: return (CxList) list; universe@406: } universe@406: universe@466: CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator) { universe@466: cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); universe@466: if (list == NULL) universe@466: return NULL; universe@466: universe@466: list->base.cl = &cx_pointer_linked_list_class; universe@466: list->base.allocator = allocator; universe@466: list->base.cmpfunc = comparator; universe@468: list->base.itemsize = sizeof(void *); universe@466: list->base.capacity = SIZE_MAX; universe@466: list->base.size = 0; universe@466: universe@466: list->begin = NULL; universe@466: list->end = NULL; universe@466: universe@466: return (CxList) list; universe@466: } universe@466: universe@409: void cxLinkedListDestroy(CxList list) { universe@446: cx_linked_list *ll = (cx_linked_list *) list; universe@436: universe@446: cx_linked_list_node *node = ll->begin; universe@436: while (node) { universe@446: void *next = node->next; universe@436: cxFree(list->allocator, node); universe@436: node = next; universe@436: } universe@436: universe@435: cxFree(list->allocator, list); universe@409: }