Sat, 14 Nov 2020 21:11:35 +0100
fix configure target options
0 | 1 | /* |
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
3 | * | |
157 | 4 | * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. |
0 | 5 | * |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions are met: | |
8 | * | |
9 | * 1. Redistributions of source code must retain the above copyright | |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * | |
12 | * 2. Redistributions in binary form must reproduce the above copyright | |
13 | * notice, this list of conditions and the following disclaimer in the | |
14 | * documentation and/or other materials provided with the distribution. | |
15 | * | |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
26 | * POSSIBILITY OF SUCH DAMAGE. | |
27 | */ | |
28 | ||
157 | 29 | #include "ucx/list.h" |
0 | 30 | |
31 | UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { | |
32 | return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); | |
33 | } | |
34 | ||
35 | UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, | |
36 | copy_func fnc, void *data) { | |
37 | UcxList *ret = NULL; | |
38 | while (l) { | |
39 | if (fnc) { | |
40 | ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); | |
41 | } else { | |
42 | ret = ucx_list_append_a(alloc, ret, l->data); | |
43 | } | |
44 | l = l->next; | |
45 | } | |
46 | return ret; | |
47 | } | |
48 | ||
49 | int ucx_list_equals(const UcxList *l1, const UcxList *l2, | |
50 | cmp_func fnc, void* data) { | |
51 | if (l1 == l2) return 1; | |
52 | ||
53 | while (l1 != NULL && l2 != NULL) { | |
54 | if (fnc == NULL) { | |
55 | if (l1->data != l2->data) return 0; | |
56 | } else { | |
57 | if (fnc(l1->data, l2->data, data) != 0) return 0; | |
58 | } | |
59 | l1 = l1->next; | |
60 | l2 = l2->next; | |
61 | } | |
62 | ||
63 | return (l1 == NULL && l2 == NULL); | |
64 | } | |
65 | ||
66 | void ucx_list_free(UcxList *l) { | |
67 | ucx_list_free_a(ucx_default_allocator(), l); | |
68 | } | |
69 | ||
70 | void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { | |
71 | UcxList *e = l, *f; | |
72 | while (e != NULL) { | |
73 | f = e; | |
74 | e = e->next; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
75 | alfree(alloc, f); |
0 | 76 | } |
77 | } | |
78 | ||
152
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
79 | void ucx_list_free_content(UcxList* list, ucx_destructor destr) { |
157 | 80 | if (!destr) destr = free; |
152
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
81 | while (list != NULL) { |
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
82 | destr(list->data); |
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
83 | list = list->next; |
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
84 | } |
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
85 | } |
62921b370c60
fixes use after free when a GtkTreeView was destroyed
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
124
diff
changeset
|
86 | |
0 | 87 | UcxList *ucx_list_append(UcxList *l, void *data) { |
88 | return ucx_list_append_a(ucx_default_allocator(), l, data); | |
89 | } | |
90 | ||
91 | UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
92 | UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList)); |
0 | 93 | if (!nl) { |
94 | return NULL; | |
95 | } | |
96 | ||
97 | nl->data = data; | |
98 | nl->next = NULL; | |
99 | if (l) { | |
100 | UcxList *t = ucx_list_last(l); | |
101 | t->next = nl; | |
102 | nl->prev = t; | |
103 | return l; | |
104 | } else { | |
105 | nl->prev = NULL; | |
106 | return nl; | |
107 | } | |
108 | } | |
109 | ||
110 | UcxList *ucx_list_prepend(UcxList *l, void *data) { | |
111 | return ucx_list_prepend_a(ucx_default_allocator(), l, data); | |
112 | } | |
113 | ||
114 | UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { | |
115 | UcxList *nl = ucx_list_append_a(alloc, NULL, data); | |
116 | if (!nl) { | |
117 | return NULL; | |
118 | } | |
119 | l = ucx_list_first(l); | |
120 | ||
121 | if (l) { | |
122 | nl->next = l; | |
123 | l->prev = nl; | |
124 | } | |
125 | return nl; | |
126 | } | |
127 | ||
128 | UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { | |
129 | if (l1) { | |
130 | UcxList *last = ucx_list_last(l1); | |
131 | last->next = l2; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
132 | if (l2) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
133 | l2->prev = last; |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
134 | } |
0 | 135 | return l1; |
136 | } else { | |
137 | return l2; | |
138 | } | |
139 | } | |
140 | ||
141 | UcxList *ucx_list_last(const UcxList *l) { | |
142 | if (l == NULL) return NULL; | |
143 | ||
144 | const UcxList *e = l; | |
145 | while (e->next != NULL) { | |
146 | e = e->next; | |
147 | } | |
148 | return (UcxList*)e; | |
149 | } | |
150 | ||
151 | ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) { | |
152 | ssize_t index = 0; | |
153 | while (list) { | |
154 | if (list == elem) { | |
155 | return index; | |
156 | } | |
157 | list = list->next; | |
158 | index++; | |
159 | } | |
160 | return -1; | |
161 | } | |
162 | ||
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
163 | UcxList *ucx_list_get(const UcxList *l, size_t index) { |
0 | 164 | if (l == NULL) return NULL; |
165 | ||
166 | const UcxList *e = l; | |
167 | while (e->next && index > 0) { | |
168 | e = e->next; | |
169 | index--; | |
170 | } | |
171 | ||
172 | return (UcxList*)(index == 0 ? e : NULL); | |
173 | } | |
174 | ||
175 | ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | |
176 | ssize_t index = 0; | |
177 | UCX_FOREACH(e, l) { | |
178 | if (fnc) { | |
179 | if (fnc(elem, e->data, cmpdata) == 0) { | |
180 | return index; | |
181 | } | |
182 | } else { | |
183 | if (elem == e->data) { | |
184 | return index; | |
185 | } | |
186 | } | |
187 | index++; | |
188 | } | |
189 | return -1; | |
190 | } | |
191 | ||
192 | int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | |
193 | return ucx_list_find(l, elem, fnc, cmpdata) > -1; | |
194 | } | |
195 | ||
196 | size_t ucx_list_size(const UcxList *l) { | |
197 | if (l == NULL) return 0; | |
198 | ||
199 | const UcxList *e = l; | |
200 | size_t s = 1; | |
201 | while (e->next != NULL) { | |
202 | e = e->next; | |
203 | s++; | |
204 | } | |
205 | ||
206 | return s; | |
207 | } | |
208 | ||
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
209 | static UcxList *ucx_list_sort_merge(int length, |
157 | 210 | UcxList* ls, UcxList* le, UcxList* re, |
0 | 211 | cmp_func fnc, void* data) { |
212 | ||
213 | UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | |
214 | UcxList *rc, *lc; | |
215 | ||
216 | lc = ls; rc = le; | |
217 | int n = 0; | |
218 | while (lc && lc != le && rc != re) { | |
219 | if (fnc(lc->data, rc->data, data) <= 0) { | |
220 | sorted[n] = lc; | |
221 | lc = lc->next; | |
222 | } else { | |
223 | sorted[n] = rc; | |
224 | rc = rc->next; | |
225 | } | |
226 | n++; | |
227 | } | |
228 | while (lc && lc != le) { | |
229 | sorted[n] = lc; | |
230 | lc = lc->next; | |
231 | n++; | |
232 | } | |
233 | while (rc && rc != re) { | |
234 | sorted[n] = rc; | |
235 | rc = rc->next; | |
236 | n++; | |
237 | } | |
238 | ||
239 | // Update pointer | |
240 | sorted[0]->prev = NULL; | |
241 | for (int i = 0 ; i < length-1 ; i++) { | |
242 | sorted[i]->next = sorted[i+1]; | |
243 | sorted[i+1]->prev = sorted[i]; | |
244 | } | |
245 | sorted[length-1]->next = NULL; | |
246 | ||
247 | UcxList *ret = sorted[0]; | |
248 | free(sorted); | |
249 | return ret; | |
250 | } | |
251 | ||
252 | UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | |
253 | if (l == NULL) { | |
254 | return NULL; | |
255 | } | |
256 | ||
257 | UcxList *lc; | |
258 | int ln = 1; | |
259 | ||
157 | 260 | UcxList *ls = l, *le, *re; |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
261 | |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
262 | // check how many elements are already sorted |
0 | 263 | lc = ls; |
264 | while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
265 | lc = lc->next; | |
266 | ln++; | |
267 | } | |
268 | le = lc->next; | |
269 | ||
270 | if (le == NULL) { | |
271 | return l; // this list is already sorted :) | |
272 | } else { | |
273 | UcxList *rc; | |
274 | int rn = 1; | |
275 | rc = le; | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
276 | // skip already sorted elements |
0 | 277 | while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
278 | rc = rc->next; | |
279 | rn++; | |
280 | } | |
281 | re = rc->next; | |
282 | ||
283 | // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
284 | UcxList *sorted = ucx_list_sort_merge(ln+rn, | |
285 | ls, le, re, | |
286 | fnc, data); | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
287 | |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
288 | // Something left? Sort it! |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
289 | size_t remainder_length = ucx_list_size(re); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
290 | if (remainder_length > 0) { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
291 | UcxList *remainder = ucx_list_sort(re, fnc, data); |
0 | 292 | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
293 | // merge sorted list with (also sorted) remainder |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
294 | l = ucx_list_sort_merge(ln+rn+remainder_length, |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
295 | sorted, remainder, NULL, fnc, data); |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
296 | } else { |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
297 | // no remainder - we've got our sorted list |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
298 | l = sorted; |
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
299 | } |
0 | 300 | |
301 | return l; | |
302 | } | |
303 | } | |
304 | ||
305 | UcxList *ucx_list_first(const UcxList *l) { | |
306 | if (!l) { | |
307 | return NULL; | |
308 | } | |
309 | ||
310 | const UcxList *e = l; | |
311 | while (e->prev) { | |
312 | e = e->prev; | |
313 | } | |
314 | return (UcxList *)e; | |
315 | } | |
316 | ||
317 | UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | |
318 | return ucx_list_remove_a(ucx_default_allocator(), l, e); | |
319 | } | |
320 | ||
321 | UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { | |
29
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
322 | if (l == e) { |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
323 | l = e->next; |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
324 | } |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
325 | |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
326 | if (e->next) { |
0 | 327 | e->next->prev = e->prev; |
328 | } | |
29
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
329 | |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
330 | if (e->prev) { |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
331 | e->prev->next = e->next; |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
332 | } |
c96169444d88
added locale support (Cocoa) and ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
0
diff
changeset
|
333 | |
124
80609f9675f1
added support for icons for the table widget (GTK)
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
29
diff
changeset
|
334 | alfree(alloc, e); |
0 | 335 | return l; |
336 | } |