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@398: #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@438: size_t i = start_index; universe@446: void *cur = start; universe@438: while (i != index && cur != NULL) { universe@438: 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@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@456: } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); universe@398: universe@456: return last; universe@398: } universe@398: universe@453: void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 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@428: void **next = CX_LL_PTR(last, loc_next); universe@428: *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@406: void **prev = CX_LL_PTR(new_node, loc_prev); universe@398: *prev = last; universe@398: } universe@398: } universe@398: 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@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@457: 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@448: // 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@466: 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@466: 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@466: return last == NULL ? NULL : *(void**)last->payload; universe@404: } universe@398: 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@404: cx_ll_last 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@466: cx_pll_last 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@466: 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: } universe@409: universe@406: size_t cxLinkedListRecalculateSize(CxList list) { universe@435: cx_linked_list *ll = (cx_linked_list *) list; universe@406: universe@406: if (ll->begin == NULL) { universe@435: ll->base.size = 0; universe@407: ll->end = NULL; universe@406: return 0; universe@406: } else { universe@446: cx_linked_list_node *cur = ll->begin; universe@446: cx_linked_list_node *last; universe@435: size_t size = 0; universe@406: do { universe@407: last = cur; universe@406: size++; universe@446: } while ((cur = cur->next) != NULL); universe@407: ll->end = last; universe@435: ll->base.size = size; universe@406: return size; universe@398: } universe@406: }