ucx/linked_list.c

Sun, 06 Oct 2024 12:00:31 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Sun, 06 Oct 2024 12:00:31 +0200
branch
newapi
changeset 324
ce13a778654a
parent 253
087cc9216f28
permissions
-rw-r--r--

update ucx

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"
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
31 #include "cx/compare.h"
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 #include <string.h>
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 #include <assert.h>
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 // LOW LEVEL LINKED LIST FUNCTIONS
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 #define ll_next(node) CX_LL_PTR(node, loc_next)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41 #define ll_data(node) (((char*)(node))+loc_data)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 void *cx_linked_list_at(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
44 const void *start,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 size_t start_index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 assert(start != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 assert(loc_advance >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 size_t i = start_index;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
52 const void *cur = start;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 while (i != index && cur != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54 cur = ll_advance(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 i < index ? i++ : i--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 return (void *) cur;
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 ssize_t cx_linked_list_find(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
61 const void *start,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 cx_compare_func cmp_func,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
65 const void *elem
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 ) {
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
67 void *dummy;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
68 return cx_linked_list_find_node(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
69 &dummy, start,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
70 loc_advance, loc_data,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
71 cmp_func, elem
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
72 );
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
73 }
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
74
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
75 ssize_t cx_linked_list_find_node(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
76 void **result,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
77 const void *start,
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
78 ptrdiff_t loc_advance,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
79 ptrdiff_t loc_data,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
80 cx_compare_func cmp_func,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
81 const void *elem
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
82 ) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
83 assert(result != NULL);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 assert(start != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 assert(loc_advance >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86 assert(loc_data >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 assert(cmp_func);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
89 const void *node = start;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 ssize_t index = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 do {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 void *current = ll_data(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 if (cmp_func(current, elem) == 0) {
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
94 *result = (void*) node;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 return index;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 node = ll_advance(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 index++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 } while (node != NULL);
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
100 *result = NULL;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 return -1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 }
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 void *cx_linked_list_first(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
105 const void *node,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106 ptrdiff_t loc_prev
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 return cx_linked_list_last(node, loc_prev);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 void *cx_linked_list_last(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
112 const void *node,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
118 const void *cur = node;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
119 const void *last;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 do {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 last = cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122 } while ((cur = ll_next(cur)) != NULL);
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 return (void *) last;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 void *cx_linked_list_prev(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
128 const void *begin,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 ptrdiff_t loc_next,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
130 const void *node
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 if (begin == node) return NULL;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
136 const void *cur = begin;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
137 const void *next;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 while (1) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 next = ll_next(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140 if (next == node) return (void *) cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 cur = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 }
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 void cx_linked_list_link(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 void *left,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 void *right,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149 ptrdiff_t loc_next
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 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152 ll_next(left) = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 ll_prev(right) = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 void cx_linked_list_unlink(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 void *left,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 void *right,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
162 ptrdiff_t loc_next
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 assert (loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
165 assert(ll_next(left) == right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 ll_next(left) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168 assert(ll_prev(right) == left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
169 ll_prev(right) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
170 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
171 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 void cx_linked_list_add(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
177 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
178 void *new_node
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 *last;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
181 if (end == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 last = *end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187 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
188 }
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 void cx_linked_list_prepend(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
192 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 void *new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 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
198 }
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 void cx_linked_list_insert(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
201 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
204 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205 void *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
206 void *new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
207 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208 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
209 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
211 void cx_linked_list_insert_chain(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
215 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
216 void *node,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 void *insert_begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 void *insert_end
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 // find the end of the chain, if not specified
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 if (insert_end == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222 insert_end = cx_linked_list_last(insert_begin, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 }
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 // determine the successor
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 void *successor;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
227 if (node == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
228 assert(begin != NULL || (end != NULL && loc_prev >= 0));
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229 if (begin != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230 successor = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 *begin = insert_begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
233 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236 successor = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 cx_linked_list_link(node, insert_begin, loc_prev, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240 if (successor == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 // the list ends with the new chain
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
243 *end = insert_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
244 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247 }
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
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
250 void cx_linked_list_insert_sorted(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
251 void **begin,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
252 void **end,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
253 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
254 ptrdiff_t loc_next,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
255 void *new_node,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
256 cx_compare_func cmp_func
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
257 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
258 assert(ll_next(new_node) == NULL);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
259 cx_linked_list_insert_sorted_chain(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
260 begin, end, loc_prev, loc_next, new_node, cmp_func);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
261 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
262
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
263 void cx_linked_list_insert_sorted_chain(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
264 void **begin,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
265 void **end,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
266 ptrdiff_t loc_prev,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
267 ptrdiff_t loc_next,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
268 void *insert_begin,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
269 cx_compare_func cmp_func
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
270 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
271 assert(begin != NULL);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
272 assert(loc_next >= 0);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
273 assert(insert_begin != NULL);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
274
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
275 // track currently observed nodes
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
276 void *dest_prev = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
277 void *dest = *begin;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
278 void *src = insert_begin;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
279
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
280 // special case: list is empty
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
281 if (dest == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
282 *begin = src;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
283 if (end != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
284 *end = cx_linked_list_last(src, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
285 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
286 return;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
287 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
288
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
289 // search the list for insertion points
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
290 while (dest != NULL && src != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
291 // compare current list node with source node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
292 // if less or equal, skip
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
293 if (cmp_func(dest, src) <= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
294 dest_prev = dest;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
295 dest = ll_next(dest);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
296 continue;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
297 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
298
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
299 // determine chain of elements that can be inserted
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
300 void *end_of_chain = src;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
301 void *next_in_chain = ll_next(src);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
302 while (next_in_chain != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
303 // once we become larger than the list elem, break
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
304 if (cmp_func(dest, next_in_chain) <= 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
305 break;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
306 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
307 // otherwise, we can insert one more
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
308 end_of_chain = next_in_chain;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
309 next_in_chain = ll_next(next_in_chain);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
310 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
311
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
312 // insert the elements
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
313 if (dest_prev == NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
314 // new begin
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
315 *begin = src;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
316 } else {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
317 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
318 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
319 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
320
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
321 // continue with next
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
322 src = next_in_chain;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
323 dest_prev = dest;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
324 dest = ll_next(dest);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
325 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
326
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
327 // insert remaining items
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
328 if (src != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
329 cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
330 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
331
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
332 // determine new end of list, if requested
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
333 if (end != NULL) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
334 *end = cx_linked_list_last(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
335 dest != NULL ? dest : dest_prev, loc_next);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
336 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
337 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
338
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339 void cx_linked_list_remove(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
340 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
341 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
342 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
343 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
344 void *node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
345 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
346 assert(node != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
347 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
348 assert(loc_prev >= 0 || begin != NULL);
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 // find adjacent nodes
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
351 void *next = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
352 void *prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
353 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
354 prev = ll_prev(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
355 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
356 prev = cx_linked_list_prev(*begin, loc_next, node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
357 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
358
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
359 // update next pointer of prev node, or set begin
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
360 if (prev == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
361 if (begin != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
362 *begin = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
363 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
364 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
365 ll_next(prev) = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
366 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
367
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
368 // update prev pointer of next node, or set end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
369 if (next == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
370 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
371 *end = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
372 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
373 } else if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
374 ll_prev(next) = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
375 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
376 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
377
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
378 size_t cx_linked_list_size(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
379 const void *node,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
380 ptrdiff_t loc_next
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 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
383 size_t size = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
384 while (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
385 node = ll_next(node);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
386 size++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
387 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
388 return size;
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
391 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
392 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
393 #endif
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
394
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
395 static void cx_linked_list_sort_merge(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
396 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
397 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
398 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
399 size_t length,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
400 void *ls,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
401 void *le,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
402 void *re,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
403 cx_compare_func cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
404 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
405 void **end
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 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
408 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
409 malloc(sizeof(void *) * length) : sbo;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
410 if (sorted == NULL) abort();
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
411 void *rc, *lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
412
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
413 lc = ls;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
414 rc = le;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
415 size_t n = 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
416 while (lc && lc != le && rc != re) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
417 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
418 sorted[n] = lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
419 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
420 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
421 sorted[n] = rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
422 rc = ll_next(rc);
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 n++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
425 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
426 while (lc && lc != le) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
427 sorted[n] = lc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
428 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
429 n++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
430 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
431 while (rc && rc != re) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
432 sorted[n] = rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
433 rc = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
434 n++;
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
437 // Update pointer
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
438 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
439 cx_for_n (i, length - 1) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
440 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
441 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
442 ll_next(sorted[length - 1]) = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
443
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
444 *begin = sorted[0];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
445 *end = sorted[length-1];
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
446 if (sorted != sbo) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
447 free(sorted);
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
451 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
452 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
453 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
454 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
455 ptrdiff_t loc_next,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
456 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
457 cx_compare_func cmp_func
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
458 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
459 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
460 assert(loc_next >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
461 assert(loc_data >= 0);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
462 assert(cmp_func);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
463
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
464 void *lc, *ls, *le, *re;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
465
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
466 // set start node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
467 ls = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
468
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
469 // early exit when this list is empty
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
470 if (ls == NULL) return;
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 // check how many elements are already sorted
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
473 lc = ls;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
474 size_t ln = 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
475 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
476 lc = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
477 ln++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
478 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
479 le = ll_next(lc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
480
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
481 // if first unsorted node is NULL, the list is already completely sorted
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
482 if (le != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
483 void *rc;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
484 size_t rn = 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
485 rc = le;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
486 // skip already sorted elements
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
487 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
488 rc = ll_next(rc);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
489 rn++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
490 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
491 re = ll_next(rc);
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 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
494 void *sorted_begin, *sorted_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
495 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
496 ln + rn, ls, le, re, cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
497 &sorted_begin, &sorted_end);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
498
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
499 // Something left? Sort it!
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
500 size_t remainder_length = cx_linked_list_size(re, loc_next);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
501 if (remainder_length > 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
502 void *remainder = re;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
503 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
504
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
505 // merge sorted list with (also sorted) remainder
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
506 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
507 ln + rn + remainder_length,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
508 sorted_begin, remainder, NULL, cmp_func,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
509 &sorted_begin, &sorted_end);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
510 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
511 *begin = sorted_begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
512 if (end) *end = sorted_end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
513 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
514 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
515
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
516 int cx_linked_list_compare(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
517 const void *begin_left,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
518 const void *begin_right,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
519 ptrdiff_t loc_advance,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
520 ptrdiff_t loc_data,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
521 cx_compare_func cmp_func
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
522 ) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
523 const void *left = begin_left, *right = begin_right;
174
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 while (left != NULL && right != NULL) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
526 const void *left_data = ll_data(left);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
527 const void *right_data = ll_data(right);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
528 int result = cmp_func(left_data, right_data);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
529 if (result != 0) return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
530 left = ll_advance(left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
531 right = ll_advance(right);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
532 }
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 if (left != NULL) { return 1; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
535 else if (right != NULL) { return -1; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
536 else { return 0; }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
537 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
538
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
539 void cx_linked_list_reverse(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
540 void **begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
541 void **end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
542 ptrdiff_t loc_prev,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
543 ptrdiff_t loc_next
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 assert(begin != NULL);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
546 assert(loc_next >= 0);
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 // swap all links
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
549 void *prev = NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
550 void *cur = *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
551 while (cur != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
552 void *next = ll_next(cur);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
553
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
554 ll_next(cur) = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
555 if (loc_prev >= 0) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
556 ll_prev(cur) = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
557 }
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 prev = cur;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
560 cur = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
561 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
562
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
563 // update begin and end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
564 if (end != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
565 *end = *begin;
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 *begin = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
568 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
569
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
570 // HIGH LEVEL LINKED LIST IMPLEMENTATION
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 typedef struct cx_linked_list_node cx_linked_list_node;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
573 struct cx_linked_list_node {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
574 cx_linked_list_node *prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
575 cx_linked_list_node *next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
576 char payload[];
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
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
579 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
580 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
581 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
582
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
583 typedef struct {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
584 struct cx_list_s base;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
585 cx_linked_list_node *begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
586 cx_linked_list_node *end;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
587 } cx_linked_list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
588
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
589 static cx_linked_list_node *cx_ll_node_at(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
590 const cx_linked_list *list,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
591 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
592 ) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
593 if (index >= list->base.collection.size) {
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
594 return NULL;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
595 } else if (index > list->base.collection.size / 2) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
596 return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
597 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
598 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
599 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
600 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
601
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
602 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
603 return cxMalloc(list->collection.allocator,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
604 sizeof(cx_linked_list_node) + list->collection.elem_size);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
605 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
606
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
607 static int cx_ll_insert_at(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
608 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
609 cx_linked_list_node *node,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
610 const void *elem
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
611 ) {
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 // create the new new_node
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
614 cx_linked_list_node *new_node = cx_ll_malloc_node(list);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
615
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
616 // sortir if failed
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
617 if (new_node == NULL) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
618
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
619 // initialize new new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
620 new_node->prev = new_node->next = NULL;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
621 memcpy(new_node->payload, elem, list->collection.elem_size);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
622
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
623 // insert
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
624 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
625 cx_linked_list_insert_chain(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
626 (void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
627 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
628 node, new_node, new_node
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
629 );
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
630
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
631 // increase the size and return
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
632 list->collection.size++;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
633 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
634 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
635
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
636 static size_t cx_ll_insert_array(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
637 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
638 size_t index,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
639 const void *array,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
640 size_t n
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
641 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
642 // out-of bounds and corner case check
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
643 if (index > list->collection.size || n == 0) return 0;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
644
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
645 // find position efficiently
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
646 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
647
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
648 // perform first insert
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
649 if (0 != cx_ll_insert_at(list, node, array)) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
650 return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
651 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
652
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
653 // is there more?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
654 if (n == 1) return 1;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
655
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
656 // we now know exactly where we are
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
657 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
658
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
659 // we can add the remaining nodes and immediately advance to the inserted node
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
660 const char *source = array;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
661 for (size_t i = 1; i < n; i++) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
662 source += list->collection.elem_size;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
663 if (0 != cx_ll_insert_at(list, node, source)) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
664 return i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
665 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
666 node = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
667 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
668 return n;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
669 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
670
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
671 static int cx_ll_insert_element(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
672 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
673 size_t index,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
674 const void *element
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
675 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
676 return 1 != cx_ll_insert_array(list, index, element, 1);
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
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
679 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
680
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
681 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
682 const cx_linked_list_node *left = l;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
683 const cx_linked_list_node *right = r;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
684 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
685 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
686
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
687 static size_t cx_ll_insert_sorted(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
688 struct cx_list_s *list,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
689 const void *array,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
690 size_t n
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
691 ) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
692 // special case
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
693 if (n == 0) return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
694
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
695 // create a new chain of nodes
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
696 cx_linked_list_node *chain = cx_ll_malloc_node(list);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
697 if (chain == NULL) return 0;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
698
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
699 memcpy(chain->payload, array, list->collection.elem_size);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
700 chain->prev = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
701 chain->next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
702
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
703 // add all elements from the array to that chain
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
704 cx_linked_list_node *prev = chain;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
705 const char *src = array;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
706 size_t inserted = 1;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
707 for (; inserted < n; inserted++) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
708 cx_linked_list_node *next = cx_ll_malloc_node(list);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
709 if (next == NULL) break;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
710 src += list->collection.elem_size;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
711 memcpy(next->payload, src, list->collection.elem_size);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
712 prev->next = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
713 next->prev = prev;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
714 prev = next;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
715 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
716 prev->next = NULL;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
717
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
718 // invoke the low level function
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
719 cx_linked_list *ll = (cx_linked_list *) list;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
720 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
721 cx_linked_list_insert_sorted_chain(
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
722 (void **) &ll->begin,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
723 (void **) &ll->end,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
724 CX_LL_LOC_PREV,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
725 CX_LL_LOC_NEXT,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
726 chain,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
727 cx_ll_insert_sorted_cmp_helper
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
728 );
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
729
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
730 // adjust the list metadata
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
731 list->collection.size += inserted;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
732
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
733 return inserted;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
734 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
735
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
736 static int cx_ll_remove(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
737 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
738 size_t index
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
739 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
740 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
741 cx_linked_list_node *node = cx_ll_node_at(ll, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
742
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
743 // out-of-bounds check
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
744 if (node == NULL) return 1;
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 // element destruction
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
747 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
748
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
749 // remove
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
750 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
751 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
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 // adjust size
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
754 list->collection.size--;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
755
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
756 // free and return
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
757 cxFree(list->collection.allocator, node);
174
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 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
760 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
761
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
762 static void cx_ll_clear(struct cx_list_s *list) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
763 if (list->collection.size == 0) return;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
764
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
765 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
766 cx_linked_list_node *node = ll->begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
767 while (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
768 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
769 cx_linked_list_node *next = node->next;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
770 cxFree(list->collection.allocator, node);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
771 node = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
772 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
773 ll->begin = ll->end = NULL;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
774 list->collection.size = 0;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
775 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
776
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
777 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
187
24ce2c326d85 implement toggle button (WinUI3)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 174
diff changeset
778 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
779 #endif
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
780 unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
781
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
782 static int cx_ll_swap(
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
783 struct cx_list_s *list,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
784 size_t i,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
785 size_t j
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
786 ) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
787 if (i >= list->collection.size || j >= list->collection.size) return 1;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
788 if (i == j) return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
789
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
790 // perform an optimized search that finds both elements in one run
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
791 cx_linked_list *ll = (cx_linked_list *) list;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
792 size_t mid = list->collection.size / 2;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
793 size_t left, right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
794 if (i < j) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
795 left = i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
796 right = j;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
797 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
798 left = j;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
799 right = i;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
800 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
801 cx_linked_list_node *nleft, *nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
802 if (left < mid && right < mid) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
803 // case 1: both items left from mid
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
804 nleft = cx_ll_node_at(ll, left);
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
805 assert(nleft != NULL);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
806 nright = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
807 for (size_t c = left; c < right; c++) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
808 nright = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
809 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
810 } else if (left >= mid && right >= mid) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
811 // case 2: both items right from mid
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
812 nright = cx_ll_node_at(ll, right);
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
813 assert(nright != NULL);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
814 nleft = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
815 for (size_t c = right; c > left; c--) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
816 nleft = nleft->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 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
819 // case 3: one item left, one item right
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
820
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
821 // chose the closest to begin / end
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
822 size_t closest;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
823 size_t other;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
824 size_t diff2boundary = list->collection.size - right - 1;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
825 if (left <= diff2boundary) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
826 closest = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
827 other = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
828 nleft = cx_ll_node_at(ll, left);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
829 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
830 closest = right;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
831 other = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
832 diff2boundary = left;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
833 nright = cx_ll_node_at(ll, right);
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 // is other element closer to us or closer to boundary?
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
837 if (right - left <= diff2boundary) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
838 // search other element starting from already found element
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
839 if (closest == left) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
840 nright = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
841 for (size_t c = left; c < right; c++) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
842 nright = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
843 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
844 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
845 nleft = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
846 for (size_t c = right; c > left; c--) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
847 nleft = nleft->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
848 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
849 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
850 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
851 // search other element starting at the boundary
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
852 if (closest == left) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
853 nright = cx_ll_node_at(ll, other);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
854 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
855 nleft = cx_ll_node_at(ll, other);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
856 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
857 }
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
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
860 if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
861 cx_linked_list_node *prev = nleft->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
862 cx_linked_list_node *next = nright->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
863 cx_linked_list_node *midstart = nleft->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
864 cx_linked_list_node *midend = nright->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
865
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
866 if (prev == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
867 ll->begin = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
868 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
869 prev->next = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
870 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
871 nright->prev = prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
872 if (midstart == nright) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
873 // special case: both nodes are adjacent
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
874 nright->next = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
875 nleft->prev = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
876 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
877 // likely case: a chain is between the two nodes
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
878 nright->next = midstart;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
879 midstart->prev = nright;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
880 midend->next = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
881 nleft->prev = midend;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
882 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
883 nleft->next = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
884 if (next == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
885 ll->end = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
886 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
887 next->prev = nleft;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
888 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
889 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
890 // swap payloads to avoid relinking
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
891 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
892 memcpy(buf, nleft->payload, list->collection.elem_size);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
893 memcpy(nleft->payload, nright->payload, list->collection.elem_size);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
894 memcpy(nright->payload, buf, list->collection.elem_size);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
895 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
896
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
897 return 0;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
898 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
899
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
900 static void *cx_ll_at(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
901 const struct cx_list_s *list,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
902 size_t index
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 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
905 cx_linked_list_node *node = cx_ll_node_at(ll, index);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
906 return node == NULL ? NULL : node->payload;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
907 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
908
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
909 static ssize_t cx_ll_find_remove(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
910 struct cx_list_s *list,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
911 const void *elem,
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
912 bool remove
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
913 ) {
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
914 if (remove) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
915 cx_linked_list *ll = ((cx_linked_list *) list);
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
916 cx_linked_list_node *node;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
917 ssize_t index = cx_linked_list_find_node(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
918 (void **) &node,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
919 ll->begin,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
920 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
921 list->collection.cmpfunc, elem
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
922 );
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
923 if (node != NULL) {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
924 cx_invoke_destructor(list, node->payload);
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
925 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
926 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
927 list->collection.size--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
928 cxFree(list->collection.allocator, node);
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
929 }
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
930 return index;
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
931 } else {
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
932 return cx_linked_list_find(
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
933 ((cx_linked_list *) list)->begin,
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
934 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
935 list->collection.cmpfunc, elem
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
936 );
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
937 }
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
938 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
939
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
940 static void cx_ll_sort(struct cx_list_s *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
941 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
942 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
943 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
944 list->collection.cmpfunc);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
945 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
946
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
947 static void cx_ll_reverse(struct cx_list_s *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
948 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
949 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
950 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
951
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
952 static int cx_ll_compare(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
953 const struct cx_list_s *list,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
954 const struct cx_list_s *other
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
955 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
956 cx_linked_list *left = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
957 cx_linked_list *right = (cx_linked_list *) other;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
958 return cx_linked_list_compare(left->begin, right->begin,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
959 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
960 list->collection.cmpfunc);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
961 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
962
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
963 static bool cx_ll_iter_valid(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
964 const struct cx_iterator_s *iter = it;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
965 return iter->elem_handle != NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
966 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
967
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
968 static void cx_ll_iter_next(void *it) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
969 struct cx_iterator_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
970 if (iter->base.remove) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
971 iter->base.remove = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
972 struct cx_list_s *list = iter->src_handle.m;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
973 cx_linked_list *ll = iter->src_handle.m;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
974 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
975 iter->elem_handle = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
976 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
977 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
978 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
979 list->collection.size--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
980 cxFree(list->collection.allocator, node);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
981 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
982 iter->index++;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
983 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
984 iter->elem_handle = node->next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
985 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
986 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
987
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
988 static void cx_ll_iter_prev(void *it) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
989 struct cx_iterator_s *iter = it;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
990 if (iter->base.remove) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
991 iter->base.remove = false;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
992 struct cx_list_s *list = iter->src_handle.m;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
993 cx_linked_list *ll = iter->src_handle.m;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
994 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
995 iter->elem_handle = node->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
996 iter->index--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
997 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
998 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
999 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1000 list->collection.size--;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1001 cxFree(list->collection.allocator, node);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1002 } else {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1003 iter->index--;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1004 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1005 iter->elem_handle = node->prev;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1006 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1007 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1008
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1009 static void *cx_ll_iter_current(const void *it) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1010 const struct cx_iterator_s *iter = it;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1011 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1012 return node->payload;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1013 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1014
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1015 static CxIterator cx_ll_iterator(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1016 const struct cx_list_s *list,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1017 size_t index,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1018 bool backwards
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1019 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1020 CxIterator iter;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1021 iter.index = index;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1022 iter.src_handle.c = list;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1023 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1024 iter.elem_size = list->collection.elem_size;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1025 iter.elem_count = list->collection.size;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1026 iter.base.valid = cx_ll_iter_valid;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1027 iter.base.current = cx_ll_iter_current;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1028 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1029 iter.base.mutating = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1030 iter.base.remove = false;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1031 return iter;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1032 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1033
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1034 static int cx_ll_insert_iter(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1035 CxIterator *iter,
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1036 const void *elem,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1037 int prepend
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1038 ) {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1039 struct cx_list_s *list = iter->src_handle.m;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1040 cx_linked_list_node *node = iter->elem_handle;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1041 if (node != NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1042 assert(prepend >= 0 && prepend <= 1);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1043 cx_linked_list_node *choice[2] = {node, node->prev};
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1044 int result = cx_ll_insert_at(list, choice[prepend], elem);
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1045 if (result == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1046 iter->elem_count++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1047 if (prepend) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1048 iter->index++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1049 }
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1050 }
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1051 return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1052 } else {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1053 int result = cx_ll_insert_element(list, list->collection.size, elem);
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1054 if (result == 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1055 iter->elem_count++;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1056 iter->index = list->collection.size;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1057 }
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1058 return result;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1059 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1060 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1061
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1062 static void cx_ll_destructor(CxList *list) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1063 cx_linked_list *ll = (cx_linked_list *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1064
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1065 cx_linked_list_node *node = ll->begin;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1066 while (node) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1067 cx_invoke_destructor(list, node->payload);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1068 void *next = node->next;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1069 cxFree(list->collection.allocator, node);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1070 node = next;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1071 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1072
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1073 cxFree(list->collection.allocator, list);
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1074 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1075
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1076 static cx_list_class cx_linked_list_class = {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1077 cx_ll_destructor,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1078 cx_ll_insert_element,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1079 cx_ll_insert_array,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1080 cx_ll_insert_sorted,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1081 cx_ll_insert_iter,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1082 cx_ll_remove,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1083 cx_ll_clear,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1084 cx_ll_swap,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1085 cx_ll_at,
253
087cc9216f28 initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 187
diff changeset
1086 cx_ll_find_remove,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1087 cx_ll_sort,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1088 cx_ll_compare,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1089 cx_ll_reverse,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1090 cx_ll_iterator,
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1091 };
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1092
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1093 CxList *cxLinkedListCreate(
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1094 const CxAllocator *allocator,
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1095 cx_compare_func comparator,
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1096 size_t elem_size
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1097 ) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1098 if (allocator == NULL) {
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1099 allocator = cxDefaultAllocator;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1100 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1101
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1102 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1103 if (list == NULL) return NULL;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1104
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1105 list->base.cl = &cx_linked_list_class;
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1106 list->base.collection.allocator = allocator;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1107
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1108 if (elem_size > 0) {
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1109 list->base.collection.elem_size = elem_size;
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1110 list->base.collection.cmpfunc = comparator;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1111 } else {
324
ce13a778654a update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 253
diff changeset
1112 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
174
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1113 cxListStorePointers((CxList *) list);
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1114 }
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1115
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1116 return (CxList *) list;
0358f1d9c506 upgrade ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1117 }

mercurial