Mercurial > hg > toolkit / file comparison

comparison: ucx/list.c

ucx/list.c

changeset 431
bb7da585debc
parent 324
ce13a778654a
child 440
7c4b9cba09ca
equal deleted inserted replaced
169:fe49cff3c571 431:bb7da585debc
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 * 3 *
4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 * 5 *
6 * Redistribution and use in source and binary forms, with or without 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must retain the above copyright 9 * 1. Redistributions of source code must retain the above copyright
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 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 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "ucx/list.h" 29 #include "cx/list.h"
30 30
31 UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) { 31 #include <string.h>
32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); 32
33 } 33 // <editor-fold desc="Store Pointers Functionality">
34 34
35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l, 35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
36 copy_func fnc, void *data) { 36
37 UcxList *ret = NULL; 37 static int cx_pl_cmpfunc(
38 while (l) { 38 const void *l,
39 if (fnc) { 39 const void *r
40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); 40 ) {
41 void *const *lptr = l;
42 void *const *rptr = r;
43 const void *left = lptr == NULL ? NULL : *lptr;
44 const void *right = rptr == NULL ? NULL : *rptr;
45 return cx_pl_cmpfunc_impl(left, right);
46 }
47
48 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
49 // cast away const - this is the hacky thing
50 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
51 cx_pl_cmpfunc_impl = l->cmpfunc;
52 l->cmpfunc = cx_pl_cmpfunc;
53 }
54
55 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
56 // cast away const - this is the hacky thing
57 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
58 l->cmpfunc = cx_pl_cmpfunc_impl;
59 }
60
61 static void cx_pl_destructor(struct cx_list_s *list) {
62 list->climpl->destructor(list);
63 }
64
65 static int cx_pl_insert_element(
66 struct cx_list_s *list,
67 size_t index,
68 const void *element
69 ) {
70 return list->climpl->insert_element(list, index, &element);
71 }
72
73 static size_t cx_pl_insert_array(
74 struct cx_list_s *list,
75 size_t index,
76 const void *array,
77 size_t n
78 ) {
79 return list->climpl->insert_array(list, index, array, n);
80 }
81
82 static size_t cx_pl_insert_sorted(
83 struct cx_list_s *list,
84 const void *array,
85 size_t n
86 ) {
87 cx_pl_hack_cmpfunc(list);
88 size_t result = list->climpl->insert_sorted(list, array, n);
89 cx_pl_unhack_cmpfunc(list);
90 return result;
91 }
92
93 static int cx_pl_insert_iter(
94 struct cx_iterator_s *iter,
95 const void *elem,
96 int prepend
97 ) {
98 struct cx_list_s *list = iter->src_handle.m;
99 return list->climpl->insert_iter(iter, &elem, prepend);
100 }
101
102 static int cx_pl_remove(
103 struct cx_list_s *list,
104 size_t index
105 ) {
106 return list->climpl->remove(list, index);
107 }
108
109 static void cx_pl_clear(struct cx_list_s *list) {
110 list->climpl->clear(list);
111 }
112
113 static int cx_pl_swap(
114 struct cx_list_s *list,
115 size_t i,
116 size_t j
117 ) {
118 return list->climpl->swap(list, i, j);
119 }
120
121 static void *cx_pl_at(
122 const struct cx_list_s *list,
123 size_t index
124 ) {
125 void **ptr = list->climpl->at(list, index);
126 return ptr == NULL ? NULL : *ptr;
127 }
128
129 static ssize_t cx_pl_find_remove(
130 struct cx_list_s *list,
131 const void *elem,
132 bool remove
133 ) {
134 cx_pl_hack_cmpfunc(list);
135 ssize_t ret = list->climpl->find_remove(list, &elem, remove);
136 cx_pl_unhack_cmpfunc(list);
137 return ret;
138 }
139
140 static void cx_pl_sort(struct cx_list_s *list) {
141 cx_pl_hack_cmpfunc(list);
142 list->climpl->sort(list);
143 cx_pl_unhack_cmpfunc(list);
144 }
145
146 static int cx_pl_compare(
147 const struct cx_list_s *list,
148 const struct cx_list_s *other
149 ) {
150 cx_pl_hack_cmpfunc(list);
151 int ret = list->climpl->compare(list, other);
152 cx_pl_unhack_cmpfunc(list);
153 return ret;
154 }
155
156 static void cx_pl_reverse(struct cx_list_s *list) {
157 list->climpl->reverse(list);
158 }
159
160 static void *cx_pl_iter_current(const void *it) {
161 const struct cx_iterator_s *iter = it;
162 void **ptr = iter->base.current_impl(it);
163 return ptr == NULL ? NULL : *ptr;
164 }
165
166 static struct cx_iterator_s cx_pl_iterator(
167 const struct cx_list_s *list,
168 size_t index,
169 bool backwards
170 ) {
171 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
172 iter.base.current_impl = iter.base.current;
173 iter.base.current = cx_pl_iter_current;
174 return iter;
175 }
176
177 static cx_list_class cx_pointer_list_class = {
178 cx_pl_destructor,
179 cx_pl_insert_element,
180 cx_pl_insert_array,
181 cx_pl_insert_sorted,
182 cx_pl_insert_iter,
183 cx_pl_remove,
184 cx_pl_clear,
185 cx_pl_swap,
186 cx_pl_at,
187 cx_pl_find_remove,
188 cx_pl_sort,
189 cx_pl_compare,
190 cx_pl_reverse,
191 cx_pl_iterator,
192 };
193
194 void cxListStoreObjects(CxList *list) {
195 list->collection.store_pointer = false;
196 if (list->climpl != NULL) {
197 list->cl = list->climpl;
198 list->climpl = NULL;
199 }
200 }
201
202 void cxListStorePointers(CxList *list) {
203 list->collection.elem_size = sizeof(void *);
204 list->collection.store_pointer = true;
205 list->climpl = list->cl;
206 list->cl = &cx_pointer_list_class;
207 }
208
209 // </editor-fold>
210
211 // <editor-fold desc="empty list implementation">
212
213 static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {
214 // this is a noop, but MUST be implemented
215 }
216
217 static void *cx_emptyl_at(
218 __attribute__((__unused__)) const struct cx_list_s *list,
219 __attribute__((__unused__)) size_t index
220 ) {
221 return NULL;
222 }
223
224 static ssize_t cx_emptyl_find_remove(
225 __attribute__((__unused__)) struct cx_list_s *list,
226 __attribute__((__unused__)) const void *elem,
227 __attribute__((__unused__)) bool remove
228 ) {
229 return -1;
230 }
231
232 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) const void *iter) {
233 return false;
234 }
235
236 static CxIterator cx_emptyl_iterator(
237 const struct cx_list_s *list,
238 size_t index,
239 __attribute__((__unused__)) bool backwards
240 ) {
241 CxIterator iter = {0};
242 iter.src_handle.c = list;
243 iter.index = index;
244 iter.base.valid = cx_emptyl_iter_valid;
245 return iter;
246 }
247
248 static cx_list_class cx_empty_list_class = {
249 cx_emptyl_noop,
250 NULL,
251 NULL,
252 NULL,
253 NULL,
254 NULL,
255 cx_emptyl_noop,
256 NULL,
257 cx_emptyl_at,
258 cx_emptyl_find_remove,
259 cx_emptyl_noop,
260 NULL,
261 cx_emptyl_noop,
262 cx_emptyl_iterator,
263 };
264
265 CxList cx_empty_list = {
266 {
267 NULL,
268 NULL,
269 0,
270 0,
271 NULL,
272 NULL,
273 NULL,
274 false
275 },
276 &cx_empty_list_class,
277 NULL
278 };
279
280 CxList *const cxEmptyList = &cx_empty_list;
281
282 // </editor-fold>
283
284 #define invoke_list_func(name, list, ...) \
285 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
286 (list, __VA_ARGS__)
287
288 size_t cx_list_default_insert_array(
289 struct cx_list_s *list,
290 size_t index,
291 const void *data,
292 size_t n
293 ) {
294 size_t elem_size = list->collection.elem_size;
295 const char *src = data;
296 size_t i = 0;
297 for (; i < n; i++) {
298 if (0 != invoke_list_func(insert_element,
299 list, index + i, src + (i * elem_size))) {
300 return i;
301 }
302 }
303 return i;
304 }
305
306 size_t cx_list_default_insert_sorted(
307 struct cx_list_s *list,
308 const void *sorted_data,
309 size_t n
310 ) {
311 // corner case
312 if (n == 0) return 0;
313
314 size_t elem_size = list->collection.elem_size;
315 cx_compare_func cmp = list->collection.cmpfunc;
316 const char *src = sorted_data;
317
318 // track indices and number of inserted items
319 size_t di = 0, si = 0, inserted = 0;
320
321 // search the list for insertion points
322 for (; di < list->collection.size; di++) {
323 const void *list_elm = invoke_list_func(at, list, di);
324
325 // compare current list element with first source element
326 // if less or equal, skip
327 if (cmp(list_elm, src) <= 0) {
328 continue;
329 }
330
331 // determine number of consecutive elements that can be inserted
332 size_t ins = 1;
333 const char *next = src;
334 while (++si < n) {
335 next += elem_size;
336 // once we become larger than the list elem, break
337 if (cmp(list_elm, next) <= 0) {
338 break;
339 }
340 // otherwise, we can insert one more
341 ins++;
342 }
343
344 // insert the elements at location si
345 if (ins == 1) {
346 if (0 != invoke_list_func(insert_element,
347 list, di, src))
348 return inserted;
41 } else { 349 } else {
42 ret = ucx_list_append_a(alloc, ret, l->data); 350 size_t r = invoke_list_func(insert_array, list, di, src, ins);
351 if (r < ins) return inserted + r;
43 } 352 }
44 l = l->next; 353 inserted += ins;
45 } 354 di += ins;
46 return ret; 355
47 } 356 // everything inserted?
48 357 if (inserted == n) return inserted;
49 int ucx_list_equals(const UcxList *l1, const UcxList *l2, 358 src = next;
50 cmp_func fnc, void* data) { 359 }
51 if (l1 == l2) return 1; 360
52 361 // insert remaining items
53 while (l1 != NULL && l2 != NULL) { 362 if (si < n) {
54 if (fnc == NULL) { 363 inserted += invoke_list_func(insert_array, list, di, src, n - si);
55 if (l1->data != l2->data) return 0; 364 }
365
366 return inserted;
367 }
368
369 void cx_list_default_sort(struct cx_list_s *list) {
370 size_t elem_size = list->collection.elem_size;
371 size_t list_size = list->collection.size;
372 void *tmp = malloc(elem_size * list_size);
373 if (tmp == NULL) abort();
374
375 // copy elements from source array
376 char *loc = tmp;
377 for (size_t i = 0; i < list_size; i++) {
378 void *src = invoke_list_func(at, list, i);
379 memcpy(loc, src, elem_size);
380 loc += elem_size;
381 }
382
383 // qsort
384 qsort(tmp, list_size, elem_size,
385 list->collection.cmpfunc);
386
387 // copy elements back
388 loc = tmp;
389 for (size_t i = 0; i < list_size; i++) {
390 void *dest = invoke_list_func(at, list, i);
391 memcpy(dest, loc, elem_size);
392 loc += elem_size;
393 }
394
395 free(tmp);
396 }
397
398 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
399 if (i == j) return 0;
400 if (i >= list->collection.size) return 1;
401 if (j >= list->collection.size) return 1;
402
403 size_t elem_size = list->collection.elem_size;
404
405 void *tmp = malloc(elem_size);
406 if (tmp == NULL) return 1;
407
408 void *ip = invoke_list_func(at, list, i);
409 void *jp = invoke_list_func(at, list, j);
410
411 memcpy(tmp, ip, elem_size);
412 memcpy(ip, jp, elem_size);
413 memcpy(jp, tmp, elem_size);
414
415 free(tmp);
416
417 return 0;
418 }
419
420 void cxListDestroy(CxList *list) {
421 list->cl->destructor(list);
422 }
423
424 int cxListCompare(
425 const CxList *list,
426 const CxList *other
427 ) {
428 bool cannot_optimize = false;
429
430 // if one is storing pointers but the other is not
431 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
432
433 // if one class is wrapped but the other is not
434 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
435
436 // if the compare functions do not match or both are NULL
437 if (!cannot_optimize) {
438 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
439 list->climpl->compare : list->cl->compare);
440 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
441 other->climpl->compare : other->cl->compare);
442 cannot_optimize |= list_cmp != other_cmp;
443 cannot_optimize |= list_cmp == NULL;
444 }
445
446 if (cannot_optimize) {
447 // lists are definitely different - cannot use internal compare function
448 if (list->collection.size == other->collection.size) {
449 CxIterator left = list->cl->iterator(list, 0, false);
450 CxIterator right = other->cl->iterator(other, 0, false);
451 for (size_t i = 0; i < list->collection.size; i++) {
452 void *leftValue = cxIteratorCurrent(left);
453 void *rightValue = cxIteratorCurrent(right);
454 int d = list->collection.cmpfunc(leftValue, rightValue);
455 if (d != 0) {
456 return d;
457 }
458 cxIteratorNext(left);
459 cxIteratorNext(right);
460 }
461 return 0;
56 } else { 462 } else {
57 if (fnc(l1->data, l2->data, data) != 0) return 0; 463 return list->collection.size < other->collection.size ? -1 : 1;
58 } 464 }
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;
75 alfree(alloc, f);
76 }
77 }
78
79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
80 if (!destr) destr = free;
81 while (list != NULL) {
82 destr(list->data);
83 list = list->next;
84 }
85 }
86
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) {
92 UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
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 { 465 } else {
105 nl->prev = NULL; 466 // lists are compatible
106 return nl; 467 return list->cl->compare(list, other);
107 } 468 }
108 } 469 }
109 470
110 UcxList *ucx_list_prepend(UcxList *l, void *data) { 471 CxIterator cxListMutIteratorAt(
111 return ucx_list_prepend_a(ucx_default_allocator(), l, data); 472 CxList *list,
112 } 473 size_t index
113 474 ) {
114 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { 475 CxIterator it = list->cl->iterator(list, index, false);
115 UcxList *nl = ucx_list_append_a(alloc, NULL, data); 476 it.base.mutating = true;
116 if (!nl) { 477 return it;
117 return NULL; 478 }
118 } 479
119 l = ucx_list_first(l); 480 CxIterator cxListMutBackwardsIteratorAt(
120 481 CxList *list,
121 if (l) { 482 size_t index
122 nl->next = l; 483 ) {
123 l->prev = nl; 484 CxIterator it = list->cl->iterator(list, index, true);
124 } 485 it.base.mutating = true;
125 return nl; 486 return it;
126 } 487 }
127
128 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
129 if (l1) {
130 UcxList *last = ucx_list_last(l1);
131 last->next = l2;
132 if (l2) {
133 l2->prev = last;
134 }
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
163 UcxList *ucx_list_get(const UcxList *l, size_t index) {
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(const UcxList *l, void *elem,
176 cmp_func fnc, void *cmpdata) {
177 ssize_t index = 0;
178 UCX_FOREACH(e, l) {
179 if (fnc) {
180 if (fnc(elem, e->data, cmpdata) == 0) {
181 return index;
182 }
183 } else {
184 if (elem == e->data) {
185 return index;
186 }
187 }
188 index++;
189 }
190 return -1;
191 }
192
193 int ucx_list_contains(const UcxList *l, void *elem,
194 cmp_func fnc, void *cmpdata) {
195 return ucx_list_find(l, elem, fnc, cmpdata) > -1;
196 }
197
198 size_t ucx_list_size(const UcxList *l) {
199 if (l == NULL) return 0;
200
201 const UcxList *e = l;
202 size_t s = 1;
203 while (e->next != NULL) {
204 e = e->next;
205 s++;
206 }
207
208 return s;
209 }
210
211 static UcxList *ucx_list_sort_merge(size_t length,
212 UcxList* ls, UcxList* le, UcxList* re,
213 cmp_func fnc, void* data) {
214
215 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
216 UcxList *rc, *lc;
217
218 lc = ls; rc = le;
219 size_t n = 0;
220 while (lc && lc != le && rc != re) {
221 if (fnc(lc->data, rc->data, data) <= 0) {
222 sorted[n] = lc;
223 lc = lc->next;
224 } else {
225 sorted[n] = rc;
226 rc = rc->next;
227 }
228 n++;
229 }
230 while (lc && lc != le) {
231 sorted[n] = lc;
232 lc = lc->next;
233 n++;
234 }
235 while (rc && rc != re) {
236 sorted[n] = rc;
237 rc = rc->next;
238 n++;
239 }
240
241 // Update pointer
242 sorted[0]->prev = NULL;
243 for (int i = 0 ; i < length-1 ; i++) {
244 sorted[i]->next = sorted[i+1];
245 sorted[i+1]->prev = sorted[i];
246 }
247 sorted[length-1]->next = NULL;
248
249 UcxList *ret = sorted[0];
250 free(sorted);
251 return ret;
252 }
253
254 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
255 if (l == NULL) {
256 return NULL;
257 }
258
259 UcxList *lc;
260 size_t ln = 1;
261
262 UcxList *ls = l, *le, *re;
263
264 // check how many elements are already sorted
265 lc = ls;
266 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
267 lc = lc->next;
268 ln++;
269 }
270 le = lc->next;
271
272 if (le == NULL) {
273 return l; // this list is already sorted :)
274 } else {
275 UcxList *rc;
276 size_t rn = 1;
277 rc = le;
278 // skip already sorted elements
279 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
280 rc = rc->next;
281 rn++;
282 }
283 re = rc->next;
284
285 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
286 UcxList *sorted = ucx_list_sort_merge(ln+rn,
287 ls, le, re,
288 fnc, data);
289
290 // Something left? Sort it!
291 size_t remainder_length = ucx_list_size(re);
292 if (remainder_length > 0) {
293 UcxList *remainder = ucx_list_sort(re, fnc, data);
294
295 // merge sorted list with (also sorted) remainder
296 l = ucx_list_sort_merge(ln+rn+remainder_length,
297 sorted, remainder, NULL, fnc, data);
298 } else {
299 // no remainder - we've got our sorted list
300 l = sorted;
301 }
302
303 return l;
304 }
305 }
306
307 UcxList *ucx_list_first(const UcxList *l) {
308 if (!l) {
309 return NULL;
310 }
311
312 const UcxList *e = l;
313 while (e->prev) {
314 e = e->prev;
315 }
316 return (UcxList *)e;
317 }
318
319 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
320 return ucx_list_remove_a(ucx_default_allocator(), l, e);
321 }
322
323 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
324 if (l == e) {
325 l = e->next;
326 }
327
328 if (e->next) {
329 e->next->prev = e->prev;
330 }
331
332 if (e->prev) {
333 e->prev->next = e->next;
334 }
335
336 alfree(alloc, e);
337 return l;
338 }
339
340
341 static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
342 UcxList const *left, UcxList const *right,
343 cmp_func cmpfnc, void* cmpdata,
344 copy_func cpfnc, void* cpdata,
345 int op) {
346
347 UcxList *res = NULL;
348 UcxList *cur = NULL;
349 const UcxList *src = left;
350
351 do {
352 UCX_FOREACH(node, src) {
353 void* elem = node->data;
354 if (
355 (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
356 (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
357 (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
358 UcxList *nl = almalloc(allocator, sizeof(UcxList));
359 nl->prev = cur;
360 nl->next = NULL;
361 if (cpfnc) {
362 nl->data = cpfnc(elem, cpdata);
363 } else {
364 nl->data = elem;
365 }
366 if (cur != NULL)
367 cur->next = nl;
368 cur = nl;
369 if (res == NULL)
370 res = cur;
371 }
372 }
373 if (op == 0 && src == left)
374 src = right;
375 else
376 src = NULL;
377 } while (src != NULL);
378
379 return res;
380 }
381
382 UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
383 cmp_func cmpfnc, void* cmpdata,
384 copy_func cpfnc, void* cpdata) {
385 return ucx_list_union_a(ucx_default_allocator(),
386 left, right, cmpfnc, cmpdata, cpfnc, cpdata);
387 }
388
389 UcxList* ucx_list_union_a(UcxAllocator *allocator,
390 UcxList const *left, UcxList const *right,
391 cmp_func cmpfnc, void* cmpdata,
392 copy_func cpfnc, void* cpdata) {
393
394 return ucx_list_setoperation_a(allocator, left, right,
395 cmpfnc, cmpdata, cpfnc, cpdata, 0);
396 }
397
398 UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
399 cmp_func cmpfnc, void* cmpdata,
400 copy_func cpfnc, void* cpdata) {
401 return ucx_list_intersection_a(ucx_default_allocator(), left, right,
402 cmpfnc, cmpdata, cpfnc, cpdata);
403 }
404
405 UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
406 UcxList const *left, UcxList const *right,
407 cmp_func cmpfnc, void* cmpdata,
408 copy_func cpfnc, void* cpdata) {
409
410 return ucx_list_setoperation_a(allocator, left, right,
411 cmpfnc, cmpdata, cpfnc, cpdata, 1);
412 }
413
414 UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
415 cmp_func cmpfnc, void* cmpdata,
416 copy_func cpfnc, void* cpdata) {
417 return ucx_list_difference_a(ucx_default_allocator(), left, right,
418 cmpfnc, cmpdata, cpfnc, cpdata);
419 }
420
421 UcxList* ucx_list_difference_a(UcxAllocator *allocator,
422 UcxList const *left, UcxList const *right,
423 cmp_func cmpfnc, void* cmpdata,
424 copy_func cpfnc, void* cpdata) {
425
426 return ucx_list_setoperation_a(allocator, left, right,
427 cmpfnc, cmpdata, cpfnc, cpdata, 2);
428 }

Mercurial Repository: toolkit

mercurial