ucx: src/linked_list.c@9d4971ea0625 (annotated)

src/linked_list.c@9d4971ea0625 (annotated)

src/linked_list.c

Mon, 27 Sep 2021 17:49:23 +0200

author: Mike Becker <universe@uap-core.de>
date: Mon, 27 Sep 2021 17:49:23 +0200
changeset 437: 9d4971ea0625
parent 436: ca9ce2297c29
child 438: cd3069757010
permissions: -rw-r--r--

implement linked list find

 /*
  * 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_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[];
 };
 typedef struct {
     cx_list_s base;
     void *begin;
     void *end;
     ptrdiff_t loc_prev;
     ptrdiff_t loc_next;
 } cx_linked_list;
 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,
             offsetof(struct cx_linked_list_node, prev),
             offsetof(struct cx_linked_list_node, next),
             node
     );
     if (ret == 0) {
         list->size++;
         return 0;
     } else {
         return ret;
     }
 }
 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;
 }
 void *cx_ll_remove(cx_list_s *list, size_t index) {
     cx_linked_list *ll = (cx_linked_list *) list;
     // TODO: implement using low level API
     return NULL;
 }
 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;
 }
 void *cx_ll_last(cx_list_s *list) {
     cx_linked_list *linkedList = (cx_linked_list *) list;
     struct cx_linked_list_node *last = cx_linked_list_last(
             NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));
     return &last->payload;
 }
 cx_list_class cx_linked_list_class = {
         cx_ll_add,
         cx_ll_insert,
         cx_ll_remove,
         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 = offsetof(struct cx_linked_list_node, prev);
     list->loc_next = offsetof(struct cx_linked_list_node, 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;
     }
 }

Mercurial > hg > ucx / annotate

src/linked_list.c@9d4971ea0625 (annotated)

src/linked_list.c