Tue, 28 Sep 2021 18:03:10 +0200
add test for cx_linked_list_add
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include "cx/linked_list.h" #include <stdint.h> #include <string.h> /* LOW LEVEL LINKED LIST FUNCTIONS */ #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { size_t i = start_index; void* cur = start; while (i != index && cur != NULL) { cur = *CX_LL_PTR(cur, loc_advance); i < index ? i++ : i--; } return cur; } void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) { if (end != NULL) { return *end; } else { if (begin == NULL || *begin == NULL) return NULL; void *cur = *begin; void *last; do { last = cur; } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); return last; } } int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { void *last = cx_linked_list_last(begin, end, loc_next); if (last == NULL) { if (begin == NULL) { // no current list and no begin ptr to write to - we don't find something to append to return 1; } else { // start fresh list *begin = new_node; } } else { // if there is a last node, update its next pointer void **next = CX_LL_PTR(last, loc_next); *next = new_node; } // if there is an end pointer, update it if (end != NULL) { *end = cx_linked_list_last(&new_node, NULL, loc_next); } // if the nodes use a prev pointer, update it if (loc_prev >= 0) { void **prev = CX_LL_PTR(new_node, loc_prev); *prev = last; } return 0; } /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ struct cx_linked_list_node { void *prev; void *next; char payload[]; }; #define CX_LL_LOC_PREV offsetof(struct cx_linked_list_node, prev) #define CX_LL_LOC_NEXT offsetof(struct cx_linked_list_node, next) typedef struct { cx_list_s base; void *begin; void *end; ptrdiff_t loc_prev; ptrdiff_t loc_next; } cx_linked_list; static int cx_ll_add(cx_list_s *list, void *elem) { cx_linked_list *ll = (cx_linked_list *) list; struct cx_linked_list_node *node = cxMalloc(list->allocator, sizeof(struct cx_linked_list_node) + list->itemsize); if (node == NULL) return 1; node->next = node->prev = NULL; memcpy(node->payload, elem, list->itemsize); int ret = cx_linked_list_add( &ll->begin, &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node ); if (ret == 0) { list->size++; return 0; } else { return ret; } } static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { cx_linked_list *ll = (cx_linked_list *) list; // TODO: implement using low level API return 1; } static int cx_ll_remove(cx_list_s *list, size_t index) { if (index >= list->size) { return 1; } cx_linked_list *ll = (cx_linked_list *) list; // TODO: implement using low level API return 0; } static void *cx_ll_at(cx_list_s *list, size_t index) { cx_linked_list *ll = (cx_linked_list *) list; struct cx_linked_list_node *node; if (index >= list->size) { node = NULL; } else if (index > list->size / 2) { node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index); } else { node = cx_linked_list_at(ll->begin, 0, CX_LL_LOC_NEXT, index); } return node == NULL ? NULL : &node->payload; } 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; struct 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; } static void *cx_ll_last(cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; struct cx_linked_list_node *last = cx_linked_list_last(NULL, &ll->end, CX_LL_LOC_NEXT); return &last->payload; } cx_list_class cx_linked_list_class = { cx_ll_add, cx_ll_insert, cx_ll_remove, cx_ll_at, cx_ll_find, cx_ll_last }; CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { cx_linked_list* list = cxMalloc(allocator, sizeof(cx_linked_list)); if (list == NULL) return NULL; list->base.cl = &cx_linked_list_class; list->base.allocator = allocator; list->base.cmpfunc = comparator; list->base.itemsize = item_size; list->base.capacity = SIZE_MAX; list->begin = NULL; list->loc_prev = CX_LL_LOC_PREV; list->loc_next = CX_LL_LOC_NEXT; CxList result = (CxList) list; cxLinkedListRecalculateSize(result); return result; } void cxLinkedListDestroy(CxList list) { cx_linked_list* ll = (cx_linked_list*) list; struct cx_linked_list_node* node = ll->begin; while (node) { void* next = node->next; cxFree(list->allocator, node); node = next; } cxFree(list->allocator, list); } size_t cxLinkedListRecalculateSize(CxList list) { cx_linked_list *ll = (cx_linked_list *) list; if (ll->begin == NULL) { ll->base.size = 0; ll->end = NULL; return 0; } else { void *cur = ll->begin; void *last; size_t size = 0; do { last = cur; size++; } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL); ll->end = last; ll->base.size = size; return size; } }