Mercurial > hg > ucx / file revision

 /*

  * 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>

 #include <assert.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, ptrdiff_t loc_next) {

     if (begin == NULL)

         return NULL;

     void *cur = begin;

     void *last;

     do {

         last = cur;

     } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);

     return last;

 }

 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {

     void *last;

     if (end == NULL) {

         assert(begin != NULL);

         last = cx_linked_list_last(*begin, loc_next);

     } else {

         last = *end;

     }

     if (last == NULL) {

         assert(begin != NULL);

         *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, 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;

     }

 }

 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

 typedef struct cx_linked_list_node cx_linked_list_node;

 struct cx_linked_list_node {

     cx_linked_list_node *prev;

     cx_linked_list_node *next;

     char payload[];

 };

 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)

 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)

 typedef struct {

     cx_list_s base;

     cx_linked_list_node *begin;

     cx_linked_list_node *end;

 } cx_linked_list;

 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {

     if (index >= list->base.size) {

         return NULL;

     } else if (index > list->base.size / 2) {

         return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index);

     } else {

         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);

     }

 }

 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {

     // out-of bounds check

     if (index > list->size) return 1;

     // cast a linked list pointer

     cx_linked_list *ll = (cx_linked_list *) list;

     // create the new node

     cx_linked_list_node *node = cxMalloc(list->allocator,

                                          sizeof(cx_linked_list_node) + list->itemsize);

     // sortir if failed

     if (node == NULL) return 1;

     // copy payload to the new node

     memcpy(node->payload, elem, list->itemsize);

     // check if this is the first node

     if (ll->begin == NULL) {

         node->prev = node->next = NULL;

         ll->begin = ll->end = node;

     } else {

         // check if this shall be the new end node

         if (index == list->size) {

             ll->end->next = node;

             node->prev = ll->end;

             node->next = NULL;

             ll->end = node;

         }

         // check if this shall be the new start node

         else if (index == 0) {

             ll->begin->prev = node;

             node->next = ll->begin;

             node->prev = NULL;

             ll->begin = node;

         } else {

             // find the node at the current index

             cx_linked_list_node *cur = cx_ll_node_at(ll, index);

             // insert before that node

             // (we know all ptr are non-null because we handled all other cases before)

             node->next = cur;

             node->prev = cur->prev;

             cur->prev = node;

             node->prev->next = node;

         }

     }

     // increase the size and return

     list->size++;

     return 0;

 }

 static int cx_ll_add(cx_list_s *list, void *elem) {

     return cx_ll_insert(list, list->size, elem);

 }

 static int cx_ll_remove(cx_list_s *list, size_t index) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_node *node = cx_ll_node_at(ll, index);

     // out-of-bounds check

     if (node == NULL) return 1;

     // change left side connection

     if (node->prev == NULL) {

         ll->begin = node->next;

     } else {

         node->prev->next = node->next;

     }

     // change right side connection

     if (node->next == NULL) {

         ll->end = node->prev;

     } else {

         node->next->prev = node->prev;

     }

     // adjust size

     list->size--;

     // free and return

     cxFree(list->allocator, node);

     return 0;

 }

 static void *cx_ll_at(cx_list_s *list, size_t index) {

     cx_linked_list *ll = (cx_linked_list *) list;

     cx_linked_list_node *node = cx_ll_node_at(ll, 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;

     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;

     cx_linked_list_node *last = ll->end;

     return last == NULL ? NULL : &last->payload;

 }

 static 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->base.size = 0;

     list->begin = NULL;

     list->end = NULL;

     return (CxList) list;

 }

 void cxLinkedListDestroy(CxList list) {

     cx_linked_list *ll = (cx_linked_list *) list;

     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 {

         cx_linked_list_node *cur = ll->begin;

         cx_linked_list_node *last;

         size_t size = 0;

         do {

             last = cur;

             size++;

         } while ((cur = cur->next) != NULL);

         ll->end = last;

         ll->base.size = size;

         return size;

     }

 }