src/linked_list.c

Sun, 03 Oct 2021 16:02:53 +0200

author
Mike Becker <universe@uap-core.de>
date
Sun, 03 Oct 2021 16:02:53 +0200
changeset 455
8168e16cd1e9
parent 453
bb144d08cd44
child 456
227c2eabbef8
permissions
-rw-r--r--

change test names

398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 #include "cx/linked_list.h"
401
e6a8f7fb0c45 copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents: 400
diff changeset
30 #include <stdint.h>
e6a8f7fb0c45 copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents: 400
diff changeset
31 #include <string.h>
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 451
diff changeset
32 #include <assert.h>
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
33
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34 /* LOW LEVEL LINKED LIST FUNCTIONS */
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
39 size_t i = start_index;
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
40 void *cur = start;
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
41 while (i != index && cur != NULL) {
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
42 cur = *CX_LL_PTR(cur, loc_advance);
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
43 i < index ? i++ : i--;
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
44 }
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
45 return cur;
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
46 }
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
47
400
8cd274352419 changes off_t to ptrdiff_t
Mike Becker <universe@uap-core.de>
parents: 399
diff changeset
48 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) {
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
49 if (end != NULL) {
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
50 return *end;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
51 } else {
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
52 if (begin == NULL || *begin == NULL)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
53 return NULL;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
54
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
55 void *cur = *begin;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
56 void *last;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
57 do {
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
58 last = cur;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
59 } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
60
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
61 return last;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
62 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
63 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
64
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 451
diff changeset
65 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
66 void *last = cx_linked_list_last(begin, end, loc_next);
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
67 if (last == NULL) {
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 451
diff changeset
68 assert(begin != NULL);
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 451
diff changeset
69 *begin = new_node;
428
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
70 } else {
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
71 // if there is a last node, update its next pointer
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
72 void **next = CX_LL_PTR(last, loc_next);
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
73 *next = new_node;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
74 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
75
428
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
76 // if there is an end pointer, update it
408
dfdd571550f8 fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents: 407
diff changeset
77 if (end != NULL) {
dfdd571550f8 fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents: 407
diff changeset
78 *end = cx_linked_list_last(&new_node, NULL, loc_next);
dfdd571550f8 fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents: 407
diff changeset
79 }
428
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
80
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
81 // if the nodes use a prev pointer, update it
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
82 if (loc_prev >= 0) {
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
83 void **prev = CX_LL_PTR(new_node, loc_prev);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
84 *prev = last;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
85 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
86 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
87
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
88 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
89
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
90 typedef struct cx_linked_list_node cx_linked_list_node;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
91 struct cx_linked_list_node {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
92 cx_linked_list_node *prev;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
93 cx_linked_list_node *next;
403
8fa43b732980 use C99 flexible array to mark the node's payload
Mike Becker <universe@uap-core.de>
parents: 402
diff changeset
94 char payload[];
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
95 };
402
a34b93911956 use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents: 401
diff changeset
96
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
97 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
98 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
99
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
100 typedef struct {
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
101 cx_list_s base;
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
102 cx_linked_list_node *begin;
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
103 cx_linked_list_node *end;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
104 } cx_linked_list;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
105
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
106 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
107 if (index >= list->base.size) {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
108 return NULL;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
109 } else if (index > list->base.size / 2) {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
110 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index);
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
111 } else {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
112 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
113 }
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
114 }
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
115
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
116 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
117 // out-of bounds check
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
118 if (index > list->size) return 1;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
119
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
120 // cast a linked list pointer
437
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
121 cx_linked_list *ll = (cx_linked_list *) list;
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
122
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
123 // create the new node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
124 cx_linked_list_node *node = cxMalloc(list->allocator,
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
125 sizeof(cx_linked_list_node) + list->itemsize);
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
126
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
127 // sortir if failed
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
128 if (node == NULL) return 1;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
129
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
130 // copy payload to the new node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
131 memcpy(node->payload, elem, list->itemsize);
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
132
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
133 // check if this is the first node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
134 if (ll->begin == NULL) {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
135 node->prev = node->next = NULL;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
136 ll->begin = ll->end = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
137 } else {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
138 // check if this shall be the new end node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
139 if (index == list->size) {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
140 ll->end->next = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
141 node->prev = ll->end;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
142 node->next = NULL;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
143 ll->end = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
144 }
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
145 // check if this shall be the new start node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
146 else if (index == 0) {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
147 ll->begin->prev = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
148 node->next = ll->begin;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
149 node->prev = NULL;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
150 ll->begin = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
151 } else {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
152 // find the node at the current index
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
153 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
154
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
155 // insert before that node
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
156 // (we know all ptr are non-null because we handled all other cases before)
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
157 node->next = cur;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
158 node->prev = cur->prev;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
159 cur->prev = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
160 node->prev->next = node;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
161 }
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
162 }
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
163
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
164 // increase the size and return
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
165 list->size++;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
166 return 0;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
167 }
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
168
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
169 static int cx_ll_add(cx_list_s *list, void *elem) {
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
170 return cx_ll_insert(list, list->size, elem);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
171 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
172
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
173 static int cx_ll_remove(cx_list_s *list, size_t index) {
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
174 cx_linked_list *ll = (cx_linked_list *) list;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
175 cx_linked_list_node *node = cx_ll_node_at(ll, index);
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
176
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
177 // out-of-bounds check
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
178 if (node == NULL) return 1;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
179
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
180 // change left side connection
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
181 if (node->prev == NULL) {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
182 ll->begin = node->next;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
183 } else {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
184 node->prev->next = node->next;
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
185 }
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
186
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
187 // change right side connection
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
188 if (node->next == NULL) {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
189 ll->end = node->prev;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
190 } else {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
191 node->next->prev = node->prev;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
192 }
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
193
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
194 // adjust size
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
195 list->size--;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
196
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
197 // free and return
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
198 cxFree(list->allocator, node);
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
199
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
200 return 0;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
201 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
202
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
203 static void *cx_ll_at(cx_list_s *list, size_t index) {
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
204 cx_linked_list *ll = (cx_linked_list *) list;
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
205 cx_linked_list_node *node = cx_ll_node_at(ll, index);
440
003aa0a78e1e fix mixed up cases in cx_ll_at()
Mike Becker <universe@uap-core.de>
parents: 439
diff changeset
206 return node == NULL ? NULL : &node->payload;
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
207 }
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
208
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
209 static size_t cx_ll_find(cx_list_s *list, void *elem) {
437
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
210 CxListComparator cmp = list->cmpfunc;
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
211 cx_linked_list *ll = (cx_linked_list *) list;
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
212
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
213 size_t index;
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
214 cx_linked_list_node *node = ll->begin;
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
215 for (index = 0; index < list->size; index++) {
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
216 void *current = node->payload;
437
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
217 if (cmp(current, elem) == 0) {
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
218 return index;
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
219 }
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
220 node = node->next;
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
221 }
9d4971ea0625 implement linked list find
Mike Becker <universe@uap-core.de>
parents: 436
diff changeset
222 return index;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
223 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
224
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
225 static void *cx_ll_last(cx_list_s *list) {
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
226 cx_linked_list *ll = (cx_linked_list *) list;
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
227 cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);
404
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 403
diff changeset
228 return &last->payload;
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 403
diff changeset
229 }
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
230
451
db06dda7ac4d make cx_linked_list_class static
Mike Becker <universe@uap-core.de>
parents: 448
diff changeset
231 static cx_list_class cx_linked_list_class = {
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
232 cx_ll_add,
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
233 cx_ll_insert,
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
234 cx_ll_remove,
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
235 cx_ll_at,
404
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 403
diff changeset
236 cx_ll_find,
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 403
diff changeset
237 cx_ll_last
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
238 };
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
239
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
240 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
241 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
242 if (list == NULL)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
243 return NULL;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
244
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
245 list->base.cl = &cx_linked_list_class;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
246 list->base.allocator = allocator;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
247 list->base.cmpfunc = comparator;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
248 list->base.itemsize = item_size;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
249 list->base.capacity = SIZE_MAX;
441
7d5a06e32aa8 change cxLinkedListCreate() setting all fields instead of calling cxListRecalculateSize()
Mike Becker <universe@uap-core.de>
parents: 440
diff changeset
250 list->base.size = 0;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
251
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
252 list->begin = NULL;
441
7d5a06e32aa8 change cxLinkedListCreate() setting all fields instead of calling cxListRecalculateSize()
Mike Becker <universe@uap-core.de>
parents: 440
diff changeset
253 list->end = NULL;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
254
441
7d5a06e32aa8 change cxLinkedListCreate() setting all fields instead of calling cxListRecalculateSize()
Mike Becker <universe@uap-core.de>
parents: 440
diff changeset
255 return (CxList) list;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
256 }
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
257
409
5d167af0eadb adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents: 408
diff changeset
258 void cxLinkedListDestroy(CxList list) {
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
259 cx_linked_list *ll = (cx_linked_list *) list;
436
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
260
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
261 cx_linked_list_node *node = ll->begin;
436
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
262 while (node) {
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
263 void *next = node->next;
436
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
264 cxFree(list->allocator, node);
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
265 node = next;
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
266 }
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
267
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
268 cxFree(list->allocator, list);
409
5d167af0eadb adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents: 408
diff changeset
269 }
5d167af0eadb adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents: 408
diff changeset
270
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
271 size_t cxLinkedListRecalculateSize(CxList list) {
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
272 cx_linked_list *ll = (cx_linked_list *) list;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
273
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
274 if (ll->begin == NULL) {
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
275 ll->base.size = 0;
407
b447539ec255 simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents: 406
diff changeset
276 ll->end = NULL;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
277 return 0;
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
278 } else {
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
279 cx_linked_list_node *cur = ll->begin;
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
280 cx_linked_list_node *last;
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
281 size_t size = 0;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
282 do {
407
b447539ec255 simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents: 406
diff changeset
283 last = cur;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
284 size++;
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
285 } while ((cur = cur->next) != NULL);
407
b447539ec255 simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents: 406
diff changeset
286 ll->end = last;
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
287 ll->base.size = size;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
288 return size;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
289 }
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
290 }

mercurial