src/linked_list.c

Tue, 15 Feb 2022 19:07:14 +0100

author
Mike Becker <universe@uap-core.de>
date
Tue, 15 Feb 2022 19:07:14 +0100
changeset 502
33e7b6ebf403
parent 500
eb9e7bd40a8e
child 503
a89857072ace
permissions
-rw-r--r--

change Doxyfile to ignore __attribute__ and include static inline functions

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
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
38 #define ll_next(node) CX_LL_PTR(node, loc_next)
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
41
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
42 void *cx_linked_list_at(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
43 void *start,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
44 size_t start_index,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
45 ptrdiff_t loc_advance,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
46 size_t index
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
47 ) {
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
48 assert(start != NULL);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
49 assert(loc_advance >= 0);
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
50 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
51 void *cur = start;
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
52 while (i != index && cur != NULL) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
53 cur = ll_advance(cur);
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
54 i < index ? i++ : i--;
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
55 }
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
56 return cur;
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
57 }
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
58
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
59 size_t cx_linked_list_find(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
60 void const *start,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
61 ptrdiff_t loc_advance,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
62 ptrdiff_t loc_data,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
63 bool follow_ptr,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
64 CxListComparator cmp_func,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
65 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
66 ) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
67 assert(start != NULL);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
68 assert(loc_advance >= 0);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
69 assert(loc_data >= 0);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
70 assert(cmp_func);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
71
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
72 void const *node = start;
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
73 size_t index = 0;
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
74 do {
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
75 void *current = ll_data(node);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
76 if (cmp_func(current, elem) == 0) {
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
77 return index;
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
78 }
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
79 node = ll_advance(node);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
80 index++;
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
81 } while (node != NULL);
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
82 return index;
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
83 }
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
84
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
85 void *cx_linked_list_first(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
86 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
87 ptrdiff_t loc_prev
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
88 ) {
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 474
diff changeset
89 return cx_linked_list_last(node, loc_prev);
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 474
diff changeset
90 }
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 474
diff changeset
91
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
92 void *cx_linked_list_last(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
93 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
94 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
95 ) {
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
96 assert(node != NULL);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
97 assert(loc_next >= 0);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
98
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 474
diff changeset
99 void *cur = node;
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
100 void *last;
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
101 do {
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
102 last = cur;
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
103 } while ((cur = ll_next(cur)) != NULL);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
104
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
105 return last;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
106 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
107
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
108 void *cx_linked_list_prev(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
109 void *begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
110 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
111 void *node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
112 ) {
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
113 assert(begin != NULL);
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
114 assert(node != NULL);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
115 assert(loc_next >= 0);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
116 if (begin == node) return NULL;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
117 void *cur = begin;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
118 void *next;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
119 while (1) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
120 next = ll_next(cur);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
121 if (next == node) return cur;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
122 cur = next;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
123 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
124 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
125
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
126 void cx_linked_list_link(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
127 void *left,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
128 void *right,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
129 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
130 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
131 ) {
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
132 assert(loc_next >= 0);
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
133 ll_next(left) = right;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
134 if (loc_prev >= 0) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
135 ll_prev(right) = left;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
136 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
137 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
138
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
139 void cx_linked_list_unlink(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
140 void *left,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
141 void *right,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
142 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
143 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
144 ) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
145 assert (loc_next >= 0);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
146 assert(ll_next(left) == right);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
147 ll_next(left) = NULL;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
148 if (loc_prev >= 0) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
149 assert(ll_prev(right) == left);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
150 ll_prev(right) = NULL;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
151 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
152 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
153
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
154 void cx_linked_list_add(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
155 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
156 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
157 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
158 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
159 void *new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
160 ) {
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
161 void *last;
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
162 if (end == NULL) {
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
163 assert(begin != NULL);
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
164 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
165 } else {
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
166 last = *end;
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
167 }
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
168 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
169 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
170
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
171 void cx_linked_list_prepend(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
172 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
173 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
174 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
175 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
176 void *new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
177 ) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
178 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
179 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
180
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
181 void cx_linked_list_insert(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
182 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
183 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
184 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
185 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
186 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
187 void *new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
188 ) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
189 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
190 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
191
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
192 void cx_linked_list_insert_chain(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
193 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
194 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
195 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
196 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
197 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
198 void *insert_begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
199 void *insert_end
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
200 ) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
201 // find the end of the chain, if not specified
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
202 if (insert_end == NULL) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
203 insert_end = cx_linked_list_last(insert_begin, loc_next);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
204 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
205
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
206 // determine the successor
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
207 void *successor;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
208 if (node == NULL) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
209 assert(begin != NULL || (end != NULL && loc_prev >= 0));
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
210 if (begin != NULL) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
211 successor = *begin;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
212 *begin = insert_begin;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
213 } else {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
214 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
215 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
216 } else {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
217 successor = ll_next(node);
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
218 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
408
dfdd571550f8 fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents: 407
diff changeset
219 }
428
da66264af8ad fix special cases for linked_list_add
Mike Becker <universe@uap-core.de>
parents: 423
diff changeset
220
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
221 if (successor == NULL) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
222 // the list ends with the new chain
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
223 if (end != NULL) {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
224 *end = insert_end;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
225 }
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
226 } else {
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
227 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
228 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
229 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
230
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
231 void cx_linked_list_remove(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
232 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
233 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
234 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
235 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
236 void *node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
237 ) {
477
73a93c7a56ae add more explicit documentation to cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 476
diff changeset
238 assert(node != NULL);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
239 assert(loc_next >= 0);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
240 assert(loc_prev >= 0 || begin != NULL);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
241
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
242 // find adjacent nodes
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
243 void *next = ll_next(node);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
244 void *prev;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
245 if (loc_prev >= 0) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
246 prev = ll_prev(node);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
247 } else {
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
248 prev = cx_linked_list_prev(*begin, loc_next, node);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
249 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
250
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
251 // update next pointer of prev node, or set begin
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
252 if (prev == NULL) {
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
253 if (begin != NULL) {
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
254 *begin = next;
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
255 }
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
256 } else {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
257 ll_next(prev) = next;
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
258 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
259
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
260 // update prev pointer of next node, or set end
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
261 if (next == NULL) {
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
262 if (end != NULL) {
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
263 *end = prev;
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
264 }
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
265 } else if (loc_prev >= 0) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
266 ll_prev(next) = prev;
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
267 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
268 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
269
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
270 size_t cx_linked_list_size(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
271 void const *node,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
272 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
273 ) {
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
274 assert(loc_next >= 0);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
275 size_t size = 0;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
276 while (node != NULL) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
277 node = ll_next(node);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
278 size++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
279 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
280 return size;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
281 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
282
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
283 static void *cx_linked_list_sort_merge(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
284 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
285 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
286 ptrdiff_t loc_data,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
287 bool follow_ptr,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
288 size_t length,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
289 void *ls,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
290 void *le,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
291 void *re,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
292 CxListComparator cmp_func
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
293 ) {
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
294 const size_t sbo_len = 1024;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
295 void *sbo[sbo_len];
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
296 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
297 void *rc, *lc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
298
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
299 lc = ls;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
300 rc = le;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
301 size_t n = 0;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
302 while (lc && lc != le && rc != re) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
303 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
304 sorted[n] = lc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
305 lc = ll_next(lc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
306 } else {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
307 sorted[n] = rc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
308 rc = ll_next(rc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
309 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
310 n++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
311 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
312 while (lc && lc != le) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
313 sorted[n] = lc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
314 lc = ll_next(lc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
315 n++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
316 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
317 while (rc && rc != re) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
318 sorted[n] = rc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
319 rc = ll_next(rc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
320 n++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
321 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
322
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
323 // Update pointer
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
324 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
325 for (size_t i = 0; i < length - 1; i++) {
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
326 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
327 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
328 ll_next(sorted[length - 1]) = NULL;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
329
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
330 void *ret = sorted[0];
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
331 if (sorted != sbo) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
332 free(sorted);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
333 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
334 return ret;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
335 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
336
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
337 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
338 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
339 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
340 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
341 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
342 ptrdiff_t loc_data,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
343 bool follow_ptr,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
344 CxListComparator cmp_func
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
345 ) {
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
346 assert(begin != NULL);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
347 assert(loc_next >= 0);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
348 assert(loc_data >= 0);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
349 assert(cmp_func);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
350
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
351 void *lc, *ls, *le, *re;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
352
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
353 // set start node
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
354 ls = *begin;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
355
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
356 // check how many elements are already sorted
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
357 lc = ls;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
358 size_t ln = 1;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
359 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
360 lc = ll_next(lc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
361 ln++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
362 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
363 le = ll_next(lc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
364
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
365 // if first unsorted node is NULL, the list is already completely sorted
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
366 if (le != NULL) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
367 void *rc;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
368 size_t rn = 1;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
369 rc = le;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
370 // skip already sorted elements
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
371 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
372 rc = ll_next(rc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
373 rn++;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
374 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
375 re = ll_next(rc);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
376
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
377 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
378 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
379 ln + rn, ls, le, re, cmp_func);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
380
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
381 // Something left? Sort it!
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
382 size_t remainder_length = cx_linked_list_size(re, loc_next);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
383 if (remainder_length > 0) {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
384 void *remainder = re;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
385 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
386
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
387 // merge sorted list with (also sorted) remainder
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
388 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
389 ln + rn + remainder_length,
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
390 sorted, remainder, NULL, cmp_func);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
391 } else {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
392 // no remainder - we've got our sorted list
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
393 *begin = sorted;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
394 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
395 if (end) *end = cx_linked_list_last(sorted, loc_next);
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
396 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
397 }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
398
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
399 int cx_linked_list_compare(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
400 void const *begin_left,
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
401 void const *begin_right,
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
402 ptrdiff_t loc_advance,
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
403 ptrdiff_t loc_data,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
404 bool follow_ptr,
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
405 CxListComparator cmp_func
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
406 ) {
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
407 void const *left = begin_left, *right = begin_right;
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
408
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
409 while (left != NULL && right != NULL) {
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
410 int result = cmp_func(ll_data(left), ll_data(right));
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
411 if (result != 0) return result;
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
412 left = ll_advance(left);
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
413 right = ll_advance(right);
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
414 }
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
415
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
416 if (left != NULL) { return 1; }
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
417 else if (right != NULL) { return -1; }
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
418 else { return 0; }
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
419 }
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
420
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
421 void cx_linked_list_reverse(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
422 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
423 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
424 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
425 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
426 ) {
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
427 assert(begin != NULL);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
428 assert(loc_next >= 0);
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
429
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
430 // swap all links
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
431 void *prev = NULL;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
432 void *cur = *begin;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
433 while (cur != NULL) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
434 void *next = ll_next(cur);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
435
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
436 ll_next(cur) = prev;
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
437 if (loc_prev >= 0) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
438 ll_prev(cur) = next;
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
439 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
440
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
441 prev = cur;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
442 cur = next;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
443 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
444
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
445 // update begin and end
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
446 if (end != NULL) {
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
447 *end = *begin;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
448 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
449 *begin = prev;
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
450 }
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 469
diff changeset
451
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
452 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
453
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
454 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
455 struct cx_linked_list_node {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
456 cx_linked_list_node *prev;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
457 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
458 char payload[];
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
459 };
402
a34b93911956 use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents: 401
diff changeset
460
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
461 #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
462 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
463 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
464
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
465 typedef struct {
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
466 struct 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
467 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
468 cx_linked_list_node *end;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
469 } cx_linked_list;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
470
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
471 static cx_linked_list_node *cx_ll_node_at(
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
472 cx_linked_list const *list,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
473 size_t index
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
474 ) {
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
475 if (index >= list->base.size) {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
476 return NULL;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
477 } else if (index > list->base.size / 2) {
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
478 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
479 } else {
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
480 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
481 }
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
482 }
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
483
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
484 static int cx_ll_insert_at(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
485 struct cx_list_s *list,
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
486 cx_linked_list_node *node,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
487 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
488 ) {
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
489
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
490 // create the new new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
491 cx_linked_list_node *new_node = cxMalloc(list->allocator,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
492 sizeof(cx_linked_list_node) + list->itemsize);
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
493
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
494 // sortir if failed
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
495 if (new_node == NULL) return 1;
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
496
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
497 // initialize new new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
498 new_node->prev = new_node->next = NULL;
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
499 memcpy(new_node->payload, elem, list->itemsize);
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
500
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
501 // insert
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
502 cx_linked_list *ll = (cx_linked_list *) list;
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
503 cx_linked_list_insert_chain(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
504 (void **) &ll->begin, (void **) &ll->end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
505 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
506 node, new_node, new_node
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
507 );
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
508
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
509 // increase the size and return
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
510 list->size++;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
511 return 0;
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
512 }
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
513
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
514 static int cx_ll_insert(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
515 struct cx_list_s *list,
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
516 size_t index,
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
517 void const *elem
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
518 ) {
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
519 // out-of bounds check
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
520 if (index > list->size) return 1;
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
521
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
522 // find position efficiently
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
523 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
524
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
525 // perform insert
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
526 return cx_ll_insert_at(list, node, elem);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
527 }
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
528
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
529 static int cx_ll_add(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
530 struct cx_list_s *list,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
531 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
532 ) {
448
37c5d2fdb36b implement cx_ll_insert()
Mike Becker <universe@uap-core.de>
parents: 447
diff changeset
533 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
534 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
535
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
536 static int cx_pll_insert(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
537 struct cx_list_s *list,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
538 size_t index,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
539 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
540 ) {
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
541 return cx_ll_insert(list, index, &elem);
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
542 }
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
543
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
544 static int cx_pll_add(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
545 struct cx_list_s *list,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
546 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
547 ) {
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
548 return cx_ll_insert(list, list->size, &elem);
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
549 }
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
550
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
551 static int cx_ll_remove(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
552 struct cx_list_s *list,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
553 size_t index
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
554 ) {
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
555 cx_linked_list *ll = (cx_linked_list *) list;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
556 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
557
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
558 // out-of-bounds check
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
559 if (node == NULL) return 1;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
560
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
561 // remove
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
562 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
563 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
564
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
565 // adjust size
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
566 list->size--;
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
567
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
568 // free and return
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
569 cxFree(list->allocator, node);
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
570
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 437
diff changeset
571 return 0;
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
572 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
573
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
574 static void *cx_ll_at(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
575 struct cx_list_s const *list,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
576 size_t index
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
577 ) {
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
578 cx_linked_list *ll = (cx_linked_list *) list;
447
87b2cdd668ed implement cx_ll_remove()
Mike Becker <universe@uap-core.de>
parents: 446
diff changeset
579 cx_linked_list_node *node = cx_ll_node_at(ll, index);
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
580 return node == NULL ? NULL : node->payload;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
581 }
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
582
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
583 static void *cx_pll_at(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
584 struct cx_list_s const *list,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
585 size_t index
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
586 ) {
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
587 cx_linked_list *ll = (cx_linked_list *) list;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
588 cx_linked_list_node *node = cx_ll_node_at(ll, index);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
589 return node == NULL ? NULL : *(void **) node->payload;
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
590 }
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
591
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
592 static size_t cx_ll_find(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
593 struct cx_list_s const *list,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
594 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
595 ) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
596 return cx_linked_list_find(((cx_linked_list *) list)->begin,
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
597 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
598 false, list->cmpfunc, elem);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
599 }
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
600
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
601 static size_t cx_pll_find(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
602 struct cx_list_s const *list,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
603 void const *elem
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
604 ) {
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
605 return cx_linked_list_find(((cx_linked_list *) list)->begin,
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
606 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
607 true, list->cmpfunc, elem);
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
608 }
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
609
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
610 static void cx_ll_sort(struct cx_list_s *list) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
611 cx_linked_list *ll = (cx_linked_list *) list;
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
612 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
613 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
614 false, list->cmpfunc);
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
615 }
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
616
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
617 static void cx_pll_sort(struct cx_list_s *list) {
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
618 cx_linked_list *ll = (cx_linked_list *) list;
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
619 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
620 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
487
4bd19279778c use c99 bool + add test for low level find
Mike Becker <universe@uap-core.de>
parents: 486
diff changeset
621 true, list->cmpfunc);
469
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
622 }
0458bff0b1cd add high level list sort and inlines method invocation functions
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
623
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
624 static void cx_ll_reverse(struct cx_list_s *list) {
490
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
625 cx_linked_list *ll = (cx_linked_list *) list;
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
626 cx_linked_list_reverse((void **) &ll->begin, (void **) ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
627 }
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
628
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
629 static int cx_ll_compare(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
630 struct cx_list_s const *list,
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
631 struct cx_list_s const *other
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
632 ) {
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
633 cx_linked_list *left = (cx_linked_list *) list;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
634 cx_linked_list *right = (cx_linked_list *) other;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
635 return cx_linked_list_compare(left->begin, right->begin,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
636 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
637 false, list->cmpfunc);
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
638 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
639
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
640 static int cx_pll_compare(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
641 struct cx_list_s const *list,
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
642 struct cx_list_s const *other
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
643 ) {
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
644 cx_linked_list *left = (cx_linked_list *) list;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
645 cx_linked_list *right = (cx_linked_list *) other;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
646 return cx_linked_list_compare(left->begin, right->begin,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
647 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
648 true, list->cmpfunc);
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
649 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
650
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
651 static bool cx_ll_iter_valid(CxIterator const *iter) {
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
652 return iter->elem_handle != NULL;
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
653 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
654
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
655 static void cx_ll_iter_next(CxIterator *iter) {
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
656 if (iter->remove) {
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
657 iter->remove = false;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
658 cx_linked_list *ll = iter->src_handle;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
659 cx_linked_list_node *node = iter->elem_handle;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
660 iter->elem_handle = node->next;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
661 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
662 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
663 ll->base.size--;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
664 cxFree(ll->base.allocator, node);
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
665 } else {
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
666 iter->index++;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
667 cx_linked_list_node *node = iter->elem_handle;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
668 iter->elem_handle = node->next;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
669 }
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
670 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
671
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
672 static void *cx_ll_iter_current(CxIterator const *iter) {
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
673 cx_linked_list_node *node = iter->elem_handle;
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
674 return node->payload;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
675 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
676
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
677 static void *cx_pll_iter_current(CxIterator const *iter) {
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
678 cx_linked_list_node *node = iter->elem_handle;
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
679 return *(void **) node->payload;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
680 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
681
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
682 static CxIterator cx_ll_iterator(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
683 struct cx_list_s *list,
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
684 size_t index
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
685 ) {
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
686 CxIterator iter;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
687 iter.index = index;
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
688 iter.src_handle = list;
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
689 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
690 iter.valid = cx_ll_iter_valid;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
691 iter.current = cx_ll_iter_current;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
692 iter.next = cx_ll_iter_next;
495
2856c74e18ba add the feature to remove items during iteration
Mike Becker <universe@uap-core.de>
parents: 494
diff changeset
693 iter.remove = false;
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
694 return iter;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
695 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
696
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
697 static CxIterator cx_pll_iterator(
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
698 struct cx_list_s *list,
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
699 size_t index
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
700 ) {
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
701 CxIterator iter = cx_ll_iterator(list, index);
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
702 iter.current = cx_pll_iter_current;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
703 return iter;
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
704 }
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
705
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
706 static int cx_ll_insert_iter(
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
707 CxIterator *iter,
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
708 void const *elem,
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
709 int prepend
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
710 ) {
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
711 struct cx_list_s *list = iter->src_handle;
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
712 cx_linked_list_node *node = iter->elem_handle;
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
713 if (node != NULL) {
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
714 assert(prepend >= 0 && prepend <= 1);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
715 cx_linked_list_node *choice[2] = {node, node->prev};
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
716 int result = cx_ll_insert_at(list, choice[prepend], elem);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
717 iter->index += prepend * (0 == result);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
718 return result;
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
719 } else {
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
720 int result = cx_ll_insert(list, list->size, elem);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
721 iter->index = list->size;
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
722 return result;
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
723 }
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
724 }
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
725
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
726 static int cx_pll_insert_iter(
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
727 CxIterator *iter,
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
728 void const *elem,
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
729 int prepend
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
730 ) {
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
731 return cx_ll_insert_iter(iter, &elem, prepend);
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
732 }
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
733
451
db06dda7ac4d make cx_linked_list_class static
Mike Becker <universe@uap-core.de>
parents: 448
diff changeset
734 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
735 cx_ll_add,
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
736 cx_ll_insert,
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
737 cx_ll_insert_iter,
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
738 cx_ll_remove,
439
9a5adedd6de6 add high-level function cxListAt()
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
739 cx_ll_at,
404
86ebc3745e62 adds cxListLast
Mike Becker <universe@uap-core.de>
parents: 403
diff changeset
740 cx_ll_find,
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
741 cx_ll_sort,
490
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
742 cx_ll_compare,
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
743 cx_ll_reverse,
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
744 cx_ll_iterator
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
745 };
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
746
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
747 static cx_list_class cx_pointer_linked_list_class = {
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
748 cx_pll_add,
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
749 cx_pll_insert,
499
3dc9075df822 add cxListInsertAfter() and cxListInsertBefore()
Mike Becker <universe@uap-core.de>
parents: 495
diff changeset
750 cx_pll_insert_iter,
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
751 cx_ll_remove,
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
752 cx_pll_at,
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
753 cx_pll_find,
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
754 cx_pll_sort,
490
e66551b47466 add cxListReverse()
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
755 cx_pll_compare,
494
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
756 cx_ll_reverse,
6ce8cfa10a96 add iterator interface + linked list iterator
Mike Becker <universe@uap-core.de>
parents: 490
diff changeset
757 cx_pll_iterator,
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
758 };
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
759
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
760 CxList *cxLinkedListCreate(
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
761 CxAllocator *allocator,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
762 CxListComparator comparator,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
763 size_t item_size
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
764 ) {
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
765 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
766 if (list == NULL)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
767 return NULL;
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
768
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
769 list->base.cl = &cx_linked_list_class;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
770 list->base.allocator = allocator;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
771 list->base.cmpfunc = comparator;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
772 list->base.itemsize = item_size;
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
773 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
774 list->base.size = 0;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
775
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
776 list->begin = NULL;
441
7d5a06e32aa8 change cxLinkedListCreate() setting all fields instead of calling cxListRecalculateSize()
Mike Becker <universe@uap-core.de>
parents: 440
diff changeset
777 list->end = NULL;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
778
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
779 return (CxList *) list;
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
780 }
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 404
diff changeset
781
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
782 CxList *cxPointerLinkedListCreate(
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
783 CxAllocator *allocator,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
784 CxListComparator comparator
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
785 ) {
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
786 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
787 if (list == NULL)
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
788 return NULL;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
789
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
790 list->base.cl = &cx_pointer_linked_list_class;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
791 list->base.allocator = allocator;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
792 list->base.cmpfunc = comparator;
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
793 list->base.itemsize = sizeof(void *);
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
794 list->base.capacity = SIZE_MAX;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
795 list->base.size = 0;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
796
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
797 list->begin = NULL;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
798 list->end = NULL;
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
799
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
800 return (CxList *) list;
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
801 }
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 457
diff changeset
802
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
803 CxList *cxLinkedListFromArray(
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
804 CxAllocator *allocator,
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
805 CxListComparator comparator,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
806 size_t item_size,
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
807 size_t num_items,
489
af6be1e123aa add some const qualifiers
Mike Becker <universe@uap-core.de>
parents: 488
diff changeset
808 void const *array
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
809 ) {
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
810 CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
811 if (list == NULL) return NULL;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
812 for (size_t i = 0; i < num_items; i++) {
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
813 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
814 cxLinkedListDestroy(list);
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
815 return NULL;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
816 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
817 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
818 return list;
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
819 }
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
820
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 499
diff changeset
821 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
822 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
823
446
668757098b73 remove unnecessary fields from linked list node and simplifies cx_ll_add()
Mike Becker <universe@uap-core.de>
parents: 441
diff changeset
824 cx_linked_list_node *node = ll->begin;
436
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
825 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
826 void *next = node->next;
436
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
827 cxFree(list->allocator, node);
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
828 node = next;
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
829 }
ca9ce2297c29 add node destruction in cxLinkedListDestroy()
Mike Becker <universe@uap-core.de>
parents: 435
diff changeset
830
435
0fe204d50f54 change inheritance model for lists
Mike Becker <universe@uap-core.de>
parents: 428
diff changeset
831 cxFree(list->allocator, list);
409
5d167af0eadb adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents: 408
diff changeset
832 }

mercurial