src/linked_list.c

Mon, 08 Aug 2022 17:12:00 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 08 Aug 2022 17:12:00 +0200
changeset 572
f0f99dd06d9f
parent 552
4373c2a90066
child 592
bb69ef3ad1f3
permissions
-rw-r--r--

#201 - remove dangerous allocator config

There is no plausible use case, except using the testing
allocator in the test case, and having the possibility to
specify any allocator (including another mempool) causes
more harm than good.

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

mercurial