ucx/linked_list.c

Tue, 03 Oct 2023 14:18:25 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Tue, 03 Oct 2023 14:18:25 +0200
branch
newapi
changeset 199
84e0a24bab4a
parent 187
24ce2c326d85
child 253
087cc9216f28
permissions
-rw-r--r--

add main tabview based on WinUI TabView

174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 #include "cx/linked_list.h"
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30 #include "cx/utils.h"
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31 #include <string.h>
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 #include <assert.h>
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34 // LOW LEVEL LINKED LIST FUNCTIONS
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 #define ll_next(node) CX_LL_PTR(node, loc_next)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 #define ll_data(node) (((char*)(node))+loc_data)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42 void *cx_linked_list_at(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 void const *start,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 size_t start_index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 assert(start != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 assert(loc_advance >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 size_t i = start_index;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 void const *cur = start;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52 while (i != index && cur != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 cur = ll_advance(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54 i < index ? i++ : i--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 return (void *) cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59 ssize_t cx_linked_list_find(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 void const *start,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 cx_compare_func cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 void const *elem
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 assert(start != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 assert(loc_advance >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 assert(loc_data >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 assert(cmp_func);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71 void const *node = start;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 ssize_t index = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 do {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 void *current = ll_data(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 if (cmp_func(current, elem) == 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 return index;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 node = ll_advance(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 index++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 } while (node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 return -1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
83
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 void *cx_linked_list_first(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 void const *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86 ptrdiff_t loc_prev
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88 return cx_linked_list_last(node, loc_prev);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
89 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 void *cx_linked_list_last(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 void const *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 void const *cur = node;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 void const *last;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 do {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 last = cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 } while ((cur = ll_next(cur)) != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 return (void *) last;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 void *cx_linked_list_prev(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 void const *begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 void const *node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 if (begin == node) return NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 void const *cur = begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 void const *next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 while (1) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119 next = ll_next(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 if (next == node) return (void *) cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 cur = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 void cx_linked_list_link(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 void *left,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 void *right,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 ll_next(left) = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 ll_prev(right) = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
137
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 void cx_linked_list_unlink(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 void *left,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140 void *right,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
143 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144 assert (loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 assert(ll_next(left) == right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 ll_next(left) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148 assert(ll_prev(right) == left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149 ll_prev(right) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
150 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
151 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 void cx_linked_list_add(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 void *new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 void *last;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 if (end == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
162 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
165 last = *end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
169
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
170 void cx_linked_list_prepend(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
171 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 void *new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
177 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
178 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
179
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
180 void cx_linked_list_insert(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
181 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 void *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 void *new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
188 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
190
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 void cx_linked_list_insert_chain(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
192 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 void *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 void *insert_begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 void *insert_end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
199 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
200 // find the end of the chain, if not specified
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
201 if (insert_end == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 insert_end = cx_linked_list_last(insert_begin, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
204
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205 // determine the successor
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
206 void *successor;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
207 if (node == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208 assert(begin != NULL || (end != NULL && loc_prev >= 0));
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
209 if (begin != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 successor = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
211 *begin = insert_begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
215 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
216 successor = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
219
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
220 if (successor == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 // the list ends with the new chain
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 *end = insert_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
227 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
228 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230 void cx_linked_list_remove(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
233 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 void *node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239 assert(loc_prev >= 0 || begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 // find adjacent nodes
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 void *next = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
243 void *prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
244 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 prev = ll_prev(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247 prev = cx_linked_list_prev(*begin, loc_next, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
250 // update next pointer of prev node, or set begin
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
251 if (prev == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
252 if (begin != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
253 *begin = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
254 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
255 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
256 ll_next(prev) = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
257 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
258
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
259 // update prev pointer of next node, or set end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
260 if (next == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
261 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
262 *end = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
263 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
264 } else if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
265 ll_prev(next) = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
266 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
267 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
268
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
269 size_t cx_linked_list_size(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
270 void const *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
271 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
272 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
273 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
274 size_t size = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
275 while (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
276 node = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
277 size++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
278 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
279 return size;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
280 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
281
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
284 #endif
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
285
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
286 static void cx_linked_list_sort_merge(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
287 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
288 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
289 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
290 size_t length,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
291 void *ls,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
292 void *le,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
293 void *re,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
294 cx_compare_func cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
295 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
296 void **end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
297 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
298 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
299 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
300 malloc(sizeof(void *) * length) : sbo;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
301 if (sorted == NULL) abort();
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
302 void *rc, *lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
303
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
304 lc = ls;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
305 rc = le;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
306 size_t n = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
307 while (lc && lc != le && rc != re) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
308 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
309 sorted[n] = lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
310 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
311 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
312 sorted[n] = rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
313 rc = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
314 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
315 n++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
316 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
317 while (lc && lc != le) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
318 sorted[n] = lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
319 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
320 n++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
321 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
322 while (rc && rc != re) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
323 sorted[n] = rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
324 rc = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
325 n++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
326 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
327
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
328 // Update pointer
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
329 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
330 cx_for_n (i, length - 1) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
331 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
332 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
333 ll_next(sorted[length - 1]) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
334
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
335 *begin = sorted[0];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
336 *end = sorted[length-1];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
337 if (sorted != sbo) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
338 free(sorted);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
340 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
341
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
342 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
343 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
344 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
345 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
346 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
347 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
348 cx_compare_func cmp_func
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
349 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
350 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
351 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
352 assert(loc_data >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
353 assert(cmp_func);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
354
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
355 void *lc, *ls, *le, *re;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
356
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
357 // set start node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
358 ls = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
359
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
360 // early exit when this list is empty
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
361 if (ls == NULL) return;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
362
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
363 // check how many elements are already sorted
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
364 lc = ls;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
365 size_t ln = 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
366 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
367 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
368 ln++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
369 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
370 le = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
371
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
372 // if first unsorted node is NULL, the list is already completely sorted
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
373 if (le != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
374 void *rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
375 size_t rn = 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
376 rc = le;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
377 // skip already sorted elements
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
378 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
379 rc = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
380 rn++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
381 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
382 re = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
383
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
384 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
385 void *sorted_begin, *sorted_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
386 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
387 ln + rn, ls, le, re, cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
388 &sorted_begin, &sorted_end);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
389
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
390 // Something left? Sort it!
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
391 size_t remainder_length = cx_linked_list_size(re, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
392 if (remainder_length > 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
393 void *remainder = re;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
394 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
395
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
396 // merge sorted list with (also sorted) remainder
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
397 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
398 ln + rn + remainder_length,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
399 sorted_begin, remainder, NULL, cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
400 &sorted_begin, &sorted_end);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
401 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
402 *begin = sorted_begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
403 if (end) *end = sorted_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
404 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
405 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
406
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
407 int cx_linked_list_compare(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
408 void const *begin_left,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
409 void const *begin_right,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
410 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
411 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
412 cx_compare_func cmp_func
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
413 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
414 void const *left = begin_left, *right = begin_right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
415
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
416 while (left != NULL && right != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
417 void const *left_data = ll_data(left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
418 void const *right_data = ll_data(right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
419 int result = cmp_func(left_data, right_data);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
420 if (result != 0) return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
421 left = ll_advance(left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
422 right = ll_advance(right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
423 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
424
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
425 if (left != NULL) { return 1; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
426 else if (right != NULL) { return -1; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
427 else { return 0; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
428 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
429
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
430 void cx_linked_list_reverse(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
431 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
432 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
433 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
434 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
435 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
436 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
437 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
438
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
439 // swap all links
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
440 void *prev = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
441 void *cur = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
442 while (cur != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
443 void *next = ll_next(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
444
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
445 ll_next(cur) = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
446 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
447 ll_prev(cur) = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
448 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
449
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
450 prev = cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
451 cur = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
452 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
453
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
454 // update begin and end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
455 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
456 *end = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
457 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
458 *begin = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
459 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
460
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
461 // HIGH LEVEL LINKED LIST IMPLEMENTATION
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
462
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
463 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
464
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
465 typedef struct cx_linked_list_node cx_linked_list_node;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
466 struct cx_linked_list_node {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
467 cx_linked_list_node *prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
468 cx_linked_list_node *next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
469 char payload[];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
470 };
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
471
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
472 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
473 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
474 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
475
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
476 typedef struct {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
477 struct cx_list_s base;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
478 cx_linked_list_node *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
479 cx_linked_list_node *end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
480 } cx_linked_list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
481
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
482 static cx_linked_list_node *cx_ll_node_at(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
483 cx_linked_list const *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
484 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
485 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
486 if (index >= list->base.size) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
487 return NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
488 } else if (index > list->base.size / 2) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
489 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
490 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
491 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
492 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
493 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
494
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
495 static int cx_ll_insert_at(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
496 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
497 cx_linked_list_node *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
498 void const *elem
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
499 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
500
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
501 // create the new new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
502 cx_linked_list_node *new_node = cxMalloc(list->allocator,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
503 sizeof(cx_linked_list_node) + list->item_size);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
504
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
505 // sortir if failed
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
506 if (new_node == NULL) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
507
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
508 // initialize new new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
509 new_node->prev = new_node->next = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
510 memcpy(new_node->payload, elem, list->item_size);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
511
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
512 // insert
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
513 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
514 cx_linked_list_insert_chain(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
515 (void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
516 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
517 node, new_node, new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
518 );
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
519
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
520 // increase the size and return
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
521 list->size++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
522 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
523 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
524
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
525 static size_t cx_ll_insert_array(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
526 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
527 size_t index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
528 void const *array,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
529 size_t n
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
530 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
531 // out-of bounds and corner case check
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
532 if (index > list->size || n == 0) return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
533
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
534 // find position efficiently
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
535 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
536
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
537 // perform first insert
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
538 if (0 != cx_ll_insert_at(list, node, array)) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
539 return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
540 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
541
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
542 // is there more?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
543 if (n == 1) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
544
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
545 // we now know exactly where we are
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
546 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
547
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
548 // we can add the remaining nodes and immedately advance to the inserted node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
549 char const *source = array;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
550 for (size_t i = 1; i < n; i++) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
551 source += list->item_size;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
552 if (0 != cx_ll_insert_at(list, node, source)) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
553 return i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
554 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
555 node = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
556 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
557 return n;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
558 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
559
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
560 static int cx_ll_insert_element(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
561 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
562 size_t index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
563 void const *element
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
564 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
565 return 1 != cx_ll_insert_array(list, index, element, 1);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
566 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
567
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
568 static int cx_ll_remove(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
569 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
570 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
571 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
572 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
573 cx_linked_list_node *node = cx_ll_node_at(ll, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
574
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
575 // out-of-bounds check
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
576 if (node == NULL) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
577
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
578 // element destruction
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
579 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
580
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
581 // remove
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
582 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
583 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
584
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
585 // adjust size
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
586 list->size--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
587
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
588 // free and return
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
589 cxFree(list->allocator, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
590
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
591 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
592 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
593
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
594 static void cx_ll_clear(struct cx_list_s *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
595 if (list->size == 0) return;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
596
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
597 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
598 cx_linked_list_node *node = ll->begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
599 while (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
600 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
601 cx_linked_list_node *next = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
602 cxFree(list->allocator, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
603 node = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
604 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
605 ll->begin = ll->end = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
606 list->size = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
607 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
608
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
187
24ce2c326d85 implement toggle button (WinUI3)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 174
diff changeset
610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
611 #endif
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
612
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
613 static int cx_ll_swap(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
614 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
615 size_t i,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
616 size_t j
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
617 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
618 if (i >= list->size || j >= list->size) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
619 if (i == j) return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
620
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
621 // perform an optimized search that finds both elements in one run
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
622 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
623 size_t mid = list->size / 2;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
624 size_t left, right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
625 if (i < j) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
626 left = i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
627 right = j;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
628 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
629 left = j;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
630 right = i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
631 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
632 cx_linked_list_node *nleft, *nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
633 if (left < mid && right < mid) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
634 // case 1: both items left from mid
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
635 nleft = cx_ll_node_at(ll, left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
636 nright = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
637 for (size_t c = left; c < right; c++) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
638 nright = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
639 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
640 } else if (left >= mid && right >= mid) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
641 // case 2: both items right from mid
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
642 nright = cx_ll_node_at(ll, right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
643 nleft = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
644 for (size_t c = right; c > left; c--) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
645 nleft = nleft->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
646 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
647 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
648 // case 3: one item left, one item right
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
649
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
650 // chose the closest to begin / end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
651 size_t closest;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
652 size_t other;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
653 size_t diff2boundary = list->size - right - 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
654 if (left <= diff2boundary) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
655 closest = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
656 other = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
657 nleft = cx_ll_node_at(ll, left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
658 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
659 closest = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
660 other = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
661 diff2boundary = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
662 nright = cx_ll_node_at(ll, right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
663 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
664
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
665 // is other element closer to us or closer to boundary?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
666 if (right - left <= diff2boundary) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
667 // search other element starting from already found element
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
668 if (closest == left) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
669 nright = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
670 for (size_t c = left; c < right; c++) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
671 nright = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
672 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
673 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
674 nleft = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
675 for (size_t c = right; c > left; c--) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
676 nleft = nleft->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
677 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
678 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
679 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
680 // search other element starting at the boundary
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
681 if (closest == left) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
682 nright = cx_ll_node_at(ll, other);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
683 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
684 nleft = cx_ll_node_at(ll, other);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
685 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
686 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
687 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
688
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
689 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
690 cx_linked_list_node *prev = nleft->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
691 cx_linked_list_node *next = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
692 cx_linked_list_node *midstart = nleft->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
693 cx_linked_list_node *midend = nright->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
694
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
695 if (prev == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
696 ll->begin = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
697 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
698 prev->next = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
699 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
700 nright->prev = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
701 if (midstart == nright) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
702 // special case: both nodes are adjacent
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
703 nright->next = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
704 nleft->prev = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
705 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
706 // likely case: a chain is between the two nodes
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
707 nright->next = midstart;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
708 midstart->prev = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
709 midend->next = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
710 nleft->prev = midend;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
711 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
712 nleft->next = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
713 if (next == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
714 ll->end = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
715 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
716 next->prev = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
717 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
718 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
719 // swap payloads to avoid relinking
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
720 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
721 memcpy(buf, nleft->payload, list->item_size);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
722 memcpy(nleft->payload, nright->payload, list->item_size);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
723 memcpy(nright->payload, buf, list->item_size);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
724 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
725
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
726 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
727 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
728
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
729 static void *cx_ll_at(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
730 struct cx_list_s const *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
731 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
732 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
733 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
734 cx_linked_list_node *node = cx_ll_node_at(ll, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
735 return node == NULL ? NULL : node->payload;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
736 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
737
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
738 static ssize_t cx_ll_find(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
739 struct cx_list_s const *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
740 void const *elem
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
741 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
742 return cx_linked_list_find(((cx_linked_list *) list)->begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
743 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
744 list->cmpfunc, elem);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
745 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
746
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
747 static void cx_ll_sort(struct cx_list_s *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
748 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
749 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
750 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
751 list->cmpfunc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
752 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
753
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
754 static void cx_ll_reverse(struct cx_list_s *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
755 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
756 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
757 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
758
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
759 static int cx_ll_compare(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
760 struct cx_list_s const *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
761 struct cx_list_s const *other
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
762 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
763 cx_linked_list *left = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
764 cx_linked_list *right = (cx_linked_list *) other;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
765 return cx_linked_list_compare(left->begin, right->begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
766 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
767 list->cmpfunc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
768 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
769
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
770 static bool cx_ll_iter_valid(void const *it) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
771 struct cx_iterator_s const *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
772 return iter->elem_handle != NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
773 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
774
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
775 static void cx_ll_iter_next(void *it) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
776 struct cx_iterator_base_s *itbase = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
777 if (itbase->remove) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
778 itbase->remove = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
779 struct cx_mut_iterator_s *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
780 struct cx_list_s *list = iter->src_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
781 cx_linked_list *ll = iter->src_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
782 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
783 iter->elem_handle = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
784 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
785 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
786 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
787 list->size--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
788 cxFree(list->allocator, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
789 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
790 struct cx_iterator_s *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
791 iter->index++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
792 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
793 iter->elem_handle = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
794 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
795 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
796
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
797 static void cx_ll_iter_prev(void *it) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
798 struct cx_iterator_base_s *itbase = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
799 if (itbase->remove) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
800 itbase->remove = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
801 struct cx_mut_iterator_s *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
802 struct cx_list_s *list = iter->src_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
803 cx_linked_list *ll = iter->src_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
804 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
805 iter->elem_handle = node->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
806 iter->index--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
807 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
808 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
809 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
810 list->size--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
811 cxFree(list->allocator, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
812 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
813 struct cx_iterator_s *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
814 iter->index--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
815 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
816 iter->elem_handle = node->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
817 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
818 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
819
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
820 static void *cx_ll_iter_current(void const *it) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
821 struct cx_iterator_s const *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
822 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
823 return node->payload;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
824 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
825
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
826 static bool cx_ll_iter_flag_rm(void *it) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
827 struct cx_iterator_base_s *iter = it;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
828 if (iter->mutating) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
829 iter->remove = true;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
830 return true;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
831 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
832 return false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
833 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
834 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
835
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
836 static CxIterator cx_ll_iterator(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
837 struct cx_list_s const *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
838 size_t index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
839 bool backwards
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
840 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
841 CxIterator iter;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
842 iter.index = index;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
843 iter.src_handle = list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
844 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
845 iter.base.valid = cx_ll_iter_valid;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
846 iter.base.current = cx_ll_iter_current;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
847 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
848 iter.base.flag_removal = cx_ll_iter_flag_rm;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
849 iter.base.mutating = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
850 iter.base.remove = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
851 return iter;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
852 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
853
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
854 static int cx_ll_insert_iter(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
855 CxMutIterator *iter,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
856 void const *elem,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
857 int prepend
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
858 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
859 struct cx_list_s *list = iter->src_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
860 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
861 if (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
862 assert(prepend >= 0 && prepend <= 1);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
863 cx_linked_list_node *choice[2] = {node, node->prev};
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
864 int result = cx_ll_insert_at(list, choice[prepend], elem);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
865 iter->index += prepend * (0 == result);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
866 return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
867 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
868 int result = cx_ll_insert_element(list, list->size, elem);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
869 iter->index = list->size;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
870 return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
871 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
872 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
873
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
874 static void cx_ll_destructor(CxList *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
875 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
876
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
877 cx_linked_list_node *node = ll->begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
878 while (node) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
879 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
880 void *next = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
881 cxFree(list->allocator, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
882 node = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
883 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
884
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
885 cxFree(list->allocator, list);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
886 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
887
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
888 static cx_list_class cx_linked_list_class = {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
889 cx_ll_destructor,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
890 cx_ll_insert_element,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
891 cx_ll_insert_array,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
892 cx_ll_insert_iter,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
893 cx_ll_remove,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
894 cx_ll_clear,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
895 cx_ll_swap,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
896 cx_ll_at,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
897 cx_ll_find,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
898 cx_ll_sort,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
899 cx_ll_compare,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
900 cx_ll_reverse,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
901 cx_ll_iterator,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
902 };
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
903
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
904 CxList *cxLinkedListCreate(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
905 CxAllocator const *allocator,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
906 cx_compare_func comparator,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
907 size_t item_size
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
908 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
909 if (allocator == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
910 allocator = cxDefaultAllocator;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
911 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
912
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
913 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
914 if (list == NULL) return NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
915
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
916 list->base.cl = &cx_linked_list_class;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
917 list->base.allocator = allocator;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
918 list->base.cmpfunc = comparator;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
919
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
920 if (item_size > 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
921 list->base.item_size = item_size;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
922 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
923 cxListStorePointers((CxList *) list);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
924 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
925
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
926 return (CxList *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
927 }

mercurial