Mercurial > hg > dbutils / file comparison

comparison: ucx/list.c

ucx/list.c

changeset 31
287484519844
parent 23
b26390e77237
equal deleted inserted replaced
30:d33eaaec15da 31:287484519844
29 #include "cx/list.h" 29 #include "cx/list.h"
30 30
31 #include <string.h> 31 #include <string.h>
32 #include <assert.h> 32 #include <assert.h>
33 33
34 // <editor-fold desc="Store Pointers Functionality"> 34 // we don't want to include the full array_list.h.
35 35 // therefore, we only forward declare the one function we want to use
36 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; 36 CX_EXPORT void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
37 37 cx_compare_func2 fn, void *context);
38 static int cx_pl_cmpfunc( 38
39 const void *l, 39
40 const void *r 40 int cx_list_compare_wrapper(const void *l, const void *r, void *c) {
41 ) { 41 CxList *list = c;
42 // l and r are guaranteed to be non-NULL pointing to the list's memory 42 const void *left;
43 void *const *lptr = l; 43 const void *right;
44 void *const *rptr = r; 44 if (cxCollectionStoresPointers(list)) {
45 const void *left = *lptr; 45 left = *(void**)l;
46 const void *right = *rptr; 46 right = *(void**)r;
47 if (left == NULL) { 47 // for historic reasons, we are handling the NULL case here
48 // NULL is smaller than any value except NULL 48 // because every UCX compare function does not support NULL arguments
49 return right == NULL ? 0 : -1; 49 if (left == NULL) {
50 } else if (right == NULL) { 50 if (right == NULL) return 0;
51 // any value is larger than NULL 51 return -1;
52 return 1; 52 } else if (right == NULL) {
53 } 53 return 1;
54 return cx_pl_cmpfunc_impl(left, right); 54 }
55 } 55 } else {
56 56 left = l;
57 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) { 57 right = r;
58 // cast away const - this is the hacky thing 58 }
59 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; 59 return cx_invoke_compare_func(list, left, right);
60 cx_pl_cmpfunc_impl = l->cmpfunc; 60 }
61 l->cmpfunc = cx_pl_cmpfunc; 61
62 } 62 #define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c)
63
64 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
65 // cast away const - this is the hacky thing
66 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
67 l->cmpfunc = cx_pl_cmpfunc_impl;
68 }
69
70 static void cx_pl_destructor(struct cx_list_s *list) {
71 list->climpl->deallocate(list);
72 }
73
74 static void *cx_pl_insert_element(
75 struct cx_list_s *list,
76 size_t index,
77 const void *element
78 ) {
79 return list->climpl->insert_element(list, index, &element);
80 }
81
82 static size_t cx_pl_insert_array(
83 struct cx_list_s *list,
84 size_t index,
85 const void *array,
86 size_t n
87 ) {
88 return list->climpl->insert_array(list, index, array, n);
89 }
90
91 static size_t cx_pl_insert_sorted(
92 struct cx_list_s *list,
93 const void *array,
94 size_t n
95 ) {
96 cx_pl_hack_cmpfunc(list);
97 size_t result = list->climpl->insert_sorted(list, array, n);
98 cx_pl_unhack_cmpfunc(list);
99 return result;
100 }
101
102 static size_t cx_pl_insert_unique(
103 struct cx_list_s *list,
104 const void *array,
105 size_t n
106 ) {
107 cx_pl_hack_cmpfunc(list);
108 size_t result = list->climpl->insert_unique(list, array, n);
109 cx_pl_unhack_cmpfunc(list);
110 return result;
111 }
112
113 static int cx_pl_insert_iter(
114 struct cx_iterator_s *iter,
115 const void *elem,
116 int prepend
117 ) {
118 struct cx_list_s *list = iter->src_handle;
119 return list->climpl->insert_iter(iter, &elem, prepend);
120 }
121
122 static size_t cx_pl_remove(
123 struct cx_list_s *list,
124 size_t index,
125 size_t num,
126 void *targetbuf
127 ) {
128 return list->climpl->remove(list, index, num, targetbuf);
129 }
130
131 static void cx_pl_clear(struct cx_list_s *list) {
132 list->climpl->clear(list);
133 }
134
135 static int cx_pl_swap(
136 struct cx_list_s *list,
137 size_t i,
138 size_t j
139 ) {
140 return list->climpl->swap(list, i, j);
141 }
142
143 static void *cx_pl_at(
144 const struct cx_list_s *list,
145 size_t index
146 ) {
147 void **ptr = list->climpl->at(list, index);
148 return ptr == NULL ? NULL : *ptr;
149 }
150
151 static size_t cx_pl_find_remove(
152 struct cx_list_s *list,
153 const void *elem,
154 bool remove
155 ) {
156 cx_pl_hack_cmpfunc(list);
157 size_t ret = list->climpl->find_remove(list, &elem, remove);
158 cx_pl_unhack_cmpfunc(list);
159 return ret;
160 }
161
162 static void cx_pl_sort(struct cx_list_s *list) {
163 cx_pl_hack_cmpfunc(list);
164 list->climpl->sort(list);
165 cx_pl_unhack_cmpfunc(list);
166 }
167
168 static int cx_pl_compare(
169 const struct cx_list_s *list,
170 const struct cx_list_s *other
171 ) {
172 cx_pl_hack_cmpfunc(list);
173 int ret = list->climpl->compare(list, other);
174 cx_pl_unhack_cmpfunc(list);
175 return ret;
176 }
177
178 static void cx_pl_reverse(struct cx_list_s *list) {
179 list->climpl->reverse(list);
180 }
181
182 static void *cx_pl_iter_current(const void *it) {
183 const struct cx_iterator_s *iter = it;
184 void **ptr = iter->base.current_impl(it);
185 return ptr == NULL ? NULL : *ptr;
186 }
187
188 static int cx_pl_change_capacity(struct cx_list_s *list, size_t cap) {
189 if (list->climpl->change_capacity == NULL) {
190 return 0;
191 } else {
192 return list->climpl->change_capacity(list, cap);
193 }
194 }
195
196 static struct cx_iterator_s cx_pl_iterator(
197 const struct cx_list_s *list,
198 size_t index,
199 bool backwards
200 ) {
201 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
202 iter.base.current_impl = iter.base.current;
203 iter.base.current = cx_pl_iter_current;
204 return iter;
205 }
206
207 static cx_list_class cx_pointer_list_class = {
208 cx_pl_destructor,
209 cx_pl_insert_element,
210 cx_pl_insert_array,
211 cx_pl_insert_sorted,
212 cx_pl_insert_unique,
213 cx_pl_insert_iter,
214 cx_pl_remove,
215 cx_pl_clear,
216 cx_pl_swap,
217 cx_pl_at,
218 cx_pl_find_remove,
219 cx_pl_sort,
220 cx_pl_compare,
221 cx_pl_reverse,
222 cx_pl_change_capacity,
223 cx_pl_iterator,
224 };
225 // </editor-fold>
226 63
227 // <editor-fold desc="empty list implementation"> 64 // <editor-fold desc="empty list implementation">
228 65
229 static void cx_emptyl_noop(cx_attr_unused CxList *list) { 66 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
230 // this is a noop, but MUST be implemented 67 // this is a noop, but MUST be implemented
281 }; 118 };
282 119
283 CxList cx_empty_list = { 120 CxList cx_empty_list = {
284 { 121 {
285 NULL, 122 NULL,
286 NULL,
287 0, 123 0,
288 0, 124 0,
125 NULL,
126 NULL,
127 NULL,
289 NULL, 128 NULL,
290 NULL, 129 NULL,
291 NULL, 130 NULL,
292 false, 131 false,
293 true, 132 true,
294 }, 133 },
295 &cx_empty_list_class, 134 &cx_empty_list_class,
296 NULL
297 }; 135 };
298 136
299 CxList *const cxEmptyList = &cx_empty_list; 137 CxList *const cxEmptyList = &cx_empty_list;
300 138
301 // </editor-fold> 139 // </editor-fold>
302
303 #define invoke_list_func(name, list, ...) \
304 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
305 (list, __VA_ARGS__)
306 140
307 size_t cx_list_default_insert_array( 141 size_t cx_list_default_insert_array(
308 struct cx_list_s *list, 142 struct cx_list_s *list,
309 size_t index, 143 size_t index,
310 const void *data, 144 const void *data,
311 size_t n 145 size_t n
312 ) { 146 ) {
313 const char *src = data; 147 const char *src = data;
314 size_t i = 0; 148 size_t i = 0;
315 for (; i < n; i++) { 149 for (; i < n; i++) {
316 if (NULL == invoke_list_func( 150 if (NULL == list->cl->insert_element(list, index + i, src)
317 insert_element, list, index + i, src)
318 ) { 151 ) {
319 return i; // LCOV_EXCL_LINE 152 return i; // LCOV_EXCL_LINE
320 } 153 }
321 if (src != NULL) { 154 if (src != NULL) {
322 src += list->collection.elem_size; 155 src += list->collection.elem_size;
333 ) { 166 ) {
334 // corner case 167 // corner case
335 if (n == 0) return 0; 168 if (n == 0) return 0;
336 169
337 size_t elem_size = list->collection.elem_size; 170 size_t elem_size = list->collection.elem_size;
338 cx_compare_func cmp = list->collection.cmpfunc;
339 const char *src = sorted_data; 171 const char *src = sorted_data;
340 172
341 // track indices and number of inserted items 173 // track indices and number of inserted items
342 size_t di = 0, si = 0, processed = 0; 174 size_t di = 0, si = 0, processed = 0;
343 175
344 // search the list for insertion points 176 // search the list for insertion points
345 while (di < list->collection.size) { 177 while (di < list->collection.size) {
346 const void *list_elm = invoke_list_func(at, list, di); 178 const void *list_elm = list->cl->at(list, di);
347 179
348 // compare the current list element with the first source element 180 // compare the current list element with the first source element
349 // if less, skip the list elements 181 // if less, skip the list elements
350 // if equal, skip the list elements and optionally the source elements 182 // if equal, skip the list elements and optionally the source elements
351 { 183 {
352 int d = cmp(list_elm, src); 184 int d = cx_list_compare_wrapper(list_elm, src, list);
353 if (d <= 0) { 185 if (d <= 0) {
354 if (!allow_duplicates && d == 0) { 186 if (!allow_duplicates && d == 0) {
355 src += elem_size; 187 src += elem_size;
356 si++; 188 si++;
357 processed++; // we also count duplicates for the return value 189 processed++; // we also count duplicates for the return value
358 while (si < n && cmp(list_elm, src) == 0) { 190 while (si < n && cx_list_compare_wrapper(list_elm, src, list) == 0) {
359 src += elem_size; 191 src += elem_size;
360 si++; 192 si++;
361 processed++; 193 processed++;
362 } 194 }
363 if (processed == n) { 195 if (processed == n) {
373 size_t ins = 1, skip = 0; 205 size_t ins = 1, skip = 0;
374 const char *next = src; 206 const char *next = src;
375 while (++si < n) { 207 while (++si < n) {
376 if (!allow_duplicates) { 208 if (!allow_duplicates) {
377 // skip duplicates within the source 209 // skip duplicates within the source
378 if (cmp(next, next + elem_size) == 0) { 210 if (cx_list_compare_wrapper(next, next + elem_size, list) == 0) {
379 next += elem_size; 211 next += elem_size;
380 skip++; 212 skip++;
381 continue; 213 continue;
382 } else { 214 } else {
383 if (skip > 0) { 215 if (skip > 0) {
387 } 219 }
388 } 220 }
389 } 221 }
390 next += elem_size; 222 next += elem_size;
391 // once we become larger than the list elem, break 223 // once we become larger than the list elem, break
392 if (cmp(list_elm, next) <= 0) { 224 if (cx_list_compare_wrapper(list_elm, next, list) <= 0) {
393 break; 225 break;
394 } 226 }
395 // otherwise, we can insert one more 227 // otherwise, we can insert one more
396 ins++; 228 ins++;
397 } 229 }
398 230
399 // insert the elements at location si 231 // insert the elements at location si
400 if (ins == 1) { 232 if (ins == 1) {
401 if (NULL == invoke_list_func(insert_element, list, di, src)) { 233 if (NULL == list->cl->insert_element(list, di, src)) {
402 return processed; // LCOV_EXCL_LINE 234 return processed; // LCOV_EXCL_LINE
403 } 235 }
404 } else { 236 } else {
405 size_t r = invoke_list_func(insert_array, list, di, src, ins); 237 size_t r = list->cl->insert_array(list, di, src, ins);
406 if (r < ins) { 238 if (r < ins) {
407 return processed + r; // LCOV_EXCL_LINE 239 return processed + r; // LCOV_EXCL_LINE
408 } 240 }
409 } 241 }
410 processed += ins + skip; 242 processed += ins + skip;
418 } 250 }
419 251
420 // insert remaining items 252 // insert remaining items
421 if (si < n) { 253 if (si < n) {
422 if (allow_duplicates) { 254 if (allow_duplicates) {
423 processed += invoke_list_func(insert_array, list, di, src, n - si); 255 processed += list->cl->insert_array(list, di, src, n - si);
424 } else { 256 } else {
425 const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1); 257 const void *last = di == 0 ? NULL : list->cl->at(list, di - 1);
426 for (; si < n; si++) { 258 for (; si < n; si++) {
427 // skip duplicates within the source 259 // skip duplicates within the source
428 if (last == NULL || cmp(last, src) != 0) { 260 if (last == NULL || cx_list_compare_wrapper(last, src, list) != 0) {
429 if (NULL == invoke_list_func(insert_element, list, di, src)) { 261 if (NULL == list->cl->insert_element(list, di, src)) {
430 return processed; // LCOV_EXCL_LINE 262 return processed; // LCOV_EXCL_LINE
431 } 263 }
432 last = src; 264 last = src;
433 di++; 265 di++;
434 } 266 }
464 if (tmp == NULL) abort(); // LCOV_EXCL_LINE 296 if (tmp == NULL) abort(); // LCOV_EXCL_LINE
465 297
466 // copy elements from source array 298 // copy elements from source array
467 char *loc = tmp; 299 char *loc = tmp;
468 for (size_t i = 0; i < list_size; i++) { 300 for (size_t i = 0; i < list_size; i++) {
469 void *src = invoke_list_func(at, list, i); 301 void *src = list->cl->at(list, i);
470 memcpy(loc, src, elem_size); 302 memcpy(loc, src, elem_size);
471 loc += elem_size; 303 loc += elem_size;
472 } 304 }
473 305
474 // qsort 306 // qsort
475 qsort(tmp, list_size, elem_size, 307 cx_array_qsort_c(tmp, list_size, elem_size, cx_list_compare_wrapper, list);
476 list->collection.cmpfunc);
477 308
478 // copy elements back 309 // copy elements back
479 loc = tmp; 310 loc = tmp;
480 for (size_t i = 0; i < list_size; i++) { 311 for (size_t i = 0; i < list_size; i++) {
481 void *dest = invoke_list_func(at, list, i); 312 void *dest = list->cl->at(list, i);
482 memcpy(dest, loc, elem_size); 313 memcpy(dest, loc, elem_size);
483 loc += elem_size; 314 loc += elem_size;
484 } 315 }
485 316
486 cxFreeDefault(tmp); 317 cxFreeDefault(tmp);
494 size_t elem_size = list->collection.elem_size; 325 size_t elem_size = list->collection.elem_size;
495 326
496 void *tmp = cxMallocDefault(elem_size); 327 void *tmp = cxMallocDefault(elem_size);
497 if (tmp == NULL) return 1; // LCOV_EXCL_LINE 328 if (tmp == NULL) return 1; // LCOV_EXCL_LINE
498 329
499 void *ip = invoke_list_func(at, list, i); 330 void *ip = list->cl->at(list, i);
500 void *jp = invoke_list_func(at, list, j); 331 void *jp = list->cl->at(list, j);
501 332
502 memcpy(tmp, ip, elem_size); 333 memcpy(tmp, ip, elem_size);
503 memcpy(ip, jp, elem_size); 334 memcpy(ip, jp, elem_size);
504 memcpy(jp, tmp, elem_size); 335 memcpy(jp, tmp, elem_size);
505 336
510 341
511 void cx_list_init( 342 void cx_list_init(
512 struct cx_list_s *list, 343 struct cx_list_s *list,
513 struct cx_list_class_s *cl, 344 struct cx_list_class_s *cl,
514 const struct cx_allocator_s *allocator, 345 const struct cx_allocator_s *allocator,
515 cx_compare_func comparator,
516 size_t elem_size 346 size_t elem_size
517 ) { 347 ) {
518 list->cl = cl; 348 list->cl = cl;
519 list->collection.allocator = allocator; 349 list->collection.allocator = allocator;
520 list->collection.cmpfunc = comparator; 350 list->collection.size = 0;
351 list->collection.sorted = false; // should be set by the implementation
521 if (elem_size > 0) { 352 if (elem_size > 0) {
522 list->collection.elem_size = elem_size; 353 list->collection.elem_size = elem_size;
354 list->collection.simple_cmp = NULL;
355 list->collection.advanced_cmp = cx_ccmp_memcmp;
356 list->collection.cmp_data = &list->collection.elem_size;
357 list->collection.store_pointer = false;
523 } else { 358 } else {
524 list->collection.elem_size = sizeof(void *); 359 list->collection.elem_size = sizeof(void *);
525 if (list->collection.cmpfunc == NULL) { 360 list->collection.simple_cmp = cx_cmp_ptr;
526 list->collection.cmpfunc = cx_cmp_ptr; 361 list->collection.advanced_cmp = NULL;
527 } 362 list->collection.cmp_data = NULL;
528 list->collection.store_pointer = true; 363 list->collection.store_pointer = true;
529 list->climpl = list->cl;
530 list->cl = &cx_pointer_list_class;
531 } 364 }
532 } 365 }
533 366
534 int cxListCompare( 367 int cxListCompare(
535 const CxList *list, 368 const CxList *list,
536 const CxList *other 369 const CxList *other
537 ) { 370 ) {
371 // check if we cannot use the list internal function
538 bool cannot_optimize = false; 372 bool cannot_optimize = false;
539 373
540 // if one is storing pointers but the other is not 374 // if one is storing pointers but the other is not
541 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; 375 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
542 376
543 // if one class is wrapped but the other is not 377 // check if the lists are incompatible or this list does not implement compare
544 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); 378 cx_compare_func list_cmp = (cx_compare_func) list->cl->compare;
545 379 cx_compare_func other_cmp = (cx_compare_func) other->cl->compare;
546 // if the compare functions do not match or both are NULL 380 cannot_optimize |= list_cmp != other_cmp;
547 if (!cannot_optimize) { 381 cannot_optimize |= list_cmp == NULL;
548 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
549 list->climpl->compare : list->cl->compare);
550 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
551 other->climpl->compare : other->cl->compare);
552 cannot_optimize |= list_cmp != other_cmp;
553 cannot_optimize |= list_cmp == NULL;
554 }
555 382
556 if (cannot_optimize) { 383 if (cannot_optimize) {
557 // lists are definitely different - cannot use internal compare function 384 // lists are definitely different - cannot use internal compare function
558 if (list->collection.size == other->collection.size) { 385 if (list->collection.size == other->collection.size) {
559 CxIterator left = list->cl->iterator(list, 0, false); 386 CxIterator left = cxListIterator(list);
560 CxIterator right = other->cl->iterator(other, 0, false); 387 CxIterator right = cxListIterator(other);
561 for (size_t i = 0; i < list->collection.size; i++) { 388 for (size_t i = 0; i < list->collection.size; i++) {
562 void *leftValue = cxIteratorCurrent(left); 389 void *leftValue = cxIteratorCurrent(left);
563 void *rightValue = cxIteratorCurrent(right); 390 void *rightValue = cxIteratorCurrent(right);
564 int d = list->collection.cmpfunc(leftValue, rightValue); 391 // values are already unwrapped, invoke immediately
392 int d = cx_invoke_compare_func(list, leftValue, rightValue);
565 if (d != 0) { 393 if (d != 0) {
566 return d; 394 return d;
567 } 395 }
568 cxIteratorNext(left); 396 cxIteratorNext(left);
569 cxIteratorNext(right); 397 cxIteratorNext(right);
582 return list->collection.size; 410 return list->collection.size;
583 } 411 }
584 412
585 int cxListAdd(CxList *list, const void *elem) { 413 int cxListAdd(CxList *list, const void *elem) {
586 list->collection.sorted = false; 414 list->collection.sorted = false;
587 return list->cl->insert_element(list, list->collection.size, elem) == NULL; 415 return list->cl->insert_element(list, list->collection.size, cx_ref(list, elem)) == NULL;
588 } 416 }
589 417
590 size_t cxListAddArray(CxList *list, const void *array, size_t n) { 418 size_t cxListAddArray(CxList *list, const void *array, size_t n) {
591 list->collection.sorted = false; 419 list->collection.sorted = false;
592 return list->cl->insert_array(list, list->collection.size, array, n); 420 return list->cl->insert_array(list, list->collection.size, array, n);
593 } 421 }
594 422
595 int cxListInsert(CxList *list, size_t index, const void *elem) { 423 int cxListInsert(CxList *list, size_t index, const void *elem) {
596 list->collection.sorted = false; 424 list->collection.sorted = false;
597 return list->cl->insert_element(list, index, elem) == NULL; 425 return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL;
598 } 426 }
599 427
600 void *cxListEmplaceAt(CxList *list, size_t index) { 428 void *cxListEmplaceAt(CxList *list, size_t index) {
601 list->collection.sorted = false; 429 list->collection.sorted = false;
602 return list->cl->insert_element(list, index, NULL); 430 return list->cl->insert_element(list, index, NULL);
619 // tweak the fields of this iterator 447 // tweak the fields of this iterator
620 iter.elem_count = c; 448 iter.elem_count = c;
621 iter.index = 0; 449 iter.index = 0;
622 // replace the valid function to abort iteration when c is reached 450 // replace the valid function to abort iteration when c is reached
623 iter.base.valid = cx_list_emplace_iterator_valid; 451 iter.base.valid = cx_list_emplace_iterator_valid;
624 // if we are storing pointers, we want to return the pure pointers.
625 // therefore, we must unwrap the "current" method
626 if (list->collection.store_pointer) {
627 iter.base.current = iter.base.current_impl;
628 }
629 return iter; 452 return iter;
630 } 453 }
631 454
632 CxIterator cxListEmplaceArray(CxList *list, size_t n) { 455 CxIterator cxListEmplaceArray(CxList *list, size_t n) {
633 return cxListEmplaceArrayAt(list, list->collection.size, n); 456 return cxListEmplaceArrayAt(list, list->collection.size, n);
634 } 457 }
635 458
636 int cxListInsertSorted(CxList *list, const void *elem) { 459 int cxListInsertSorted(CxList *list, const void *elem) {
637 assert(cxCollectionSorted(list)); 460 assert(cxCollectionSorted(list));
638 list->collection.sorted = true; 461 list->collection.sorted = true;
639 const void *data = list->collection.store_pointer ? &elem : elem; 462 return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0;
640 return list->cl->insert_sorted(list, data, 1) == 0;
641 } 463 }
642 464
643 int cxListInsertUnique(CxList *list, const void *elem) { 465 int cxListInsertUnique(CxList *list, const void *elem) {
644 if (cxCollectionSorted(list)) { 466 if (cxCollectionSorted(list)) {
645 list->collection.sorted = true; 467 list->collection.sorted = true;
646 const void *data = list->collection.store_pointer ? &elem : elem; 468 return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0;
647 return list->cl->insert_unique(list, data, 1) == 0;
648 } else { 469 } else {
649 if (cxListContains(list, elem)) { 470 if (cxListContains(list, elem)) {
650 return 0; 471 return 0;
651 } else { 472 } else {
652 return cxListAdd(list, elem); 473 return cxListAdd(list, elem);
671 return list->cl->insert_unique(list, array, n); 492 return list->cl->insert_unique(list, array, n);
672 } else { 493 } else {
673 const char *source = array; 494 const char *source = array;
674 for (size_t i = 0 ; i < n; i++) { 495 for (size_t i = 0 ; i < n; i++) {
675 // note: this also checks elements added in a previous iteration 496 // note: this also checks elements added in a previous iteration
676 const void *data = list->collection.store_pointer ? 497 const void *data = cx_deref(list, source);
677 *((const void**)source) : source;
678 if (!cxListContains(list, data)) { 498 if (!cxListContains(list, data)) {
679 if (cxListAdd(list, data)) { 499 if (cxListAdd(list, data)) {
680 return i; // LCOV_EXCL_LINE 500 return i; // LCOV_EXCL_LINE
681 } 501 }
682 } 502 }
685 return n; 505 return n;
686 } 506 }
687 } 507 }
688 508
689 int cxListInsertAfter(CxIterator *iter, const void *elem) { 509 int cxListInsertAfter(CxIterator *iter, const void *elem) {
690 CxList* list = (CxList*)iter->src_handle; 510 CxList* list = iter->src_handle;
691 list->collection.sorted = false; 511 list->collection.sorted = false;
692 return list->cl->insert_iter(iter, elem, 0); 512 return list->cl->insert_iter(iter, cx_ref(list, elem), 0);
693 } 513 }
694 514
695 int cxListInsertBefore(CxIterator *iter, const void *elem) { 515 int cxListInsertBefore(CxIterator *iter, const void *elem) {
696 CxList* list = (CxList*)iter->src_handle; 516 CxList* list = iter->src_handle;
697 list->collection.sorted = false; 517 list->collection.sorted = false;
698 return list->cl->insert_iter(iter, elem, 1); 518 return list->cl->insert_iter(iter, cx_ref(list, elem), 1);
699 } 519 }
700 520
701 int cxListRemove(CxList *list, size_t index) { 521 int cxListRemove(CxList *list, size_t index) {
702 return list->cl->remove(list, index, 1, NULL) == 0; 522 return list->cl->remove(list, index, 1, NULL) == 0;
703 } 523 }
732 list->collection.sorted = false; 552 list->collection.sorted = false;
733 return list->cl->swap(list, i, j); 553 return list->cl->swap(list, i, j);
734 } 554 }
735 555
736 void *cxListAt(const CxList *list, size_t index) { 556 void *cxListAt(const CxList *list, size_t index) {
737 return list->cl->at(list, index); 557 void *result = list->cl->at(list, index);
558 if (result == NULL) return NULL;
559 return cx_deref(list, result);
738 } 560 }
739 561
740 void *cxListFirst(const CxList *list) { 562 void *cxListFirst(const CxList *list) {
741 return list->cl->at(list, 0); 563 return cxListAt(list, 0);
742 } 564 }
743 565
744 void *cxListLast(const CxList *list) { 566 void *cxListLast(const CxList *list) {
745 return list->cl->at(list, list->collection.size - 1); 567 return cxListAt(list, list->collection.size - 1);
746 } 568 }
747 569
748 int cxListSet(CxList *list, size_t index, const void *elem) { 570 int cxListSet(CxList *list, size_t index, const void *elem) {
749 if (index >= list->collection.size) { 571 if (index >= list->collection.size) {
750 return 1; 572 return 1;
751 } 573 }
752 574
753 if (list->collection.store_pointer) { 575 if (list->collection.store_pointer) {
754 // For pointer collections, always use climpl 576 void **target = list->cl->at(list, index);
755 void **target = list->climpl->at(list, index);
756 *target = (void *)elem; 577 *target = (void *)elem;
757 } else { 578 } else {
758 void *target = list->cl->at(list, index); 579 void *target = list->cl->at(list, index);
759 memcpy(target, elem, list->collection.elem_size); 580 memcpy(target, elem, list->collection.elem_size);
760 } 581 }
761 582
762 return 0; 583 return 0;
763 } 584 }
764 585
586 static void *cx_pl_iter_current(const void *it) {
587 const struct cx_iterator_s *iter = it;
588 void **ptr = iter->base.current_impl(it);
589 return ptr == NULL ? NULL : *ptr;
590 }
591
592 CX_INLINE CxIterator cx_pl_iter_wrap(const CxList *list, CxIterator iter) {
593 if (cxCollectionStoresPointers(list)) {
594 iter.base.current_impl = iter.base.current;
595 iter.base.current = cx_pl_iter_current;
596 return iter;
597 } else {
598 return iter;
599 }
600 }
601
765 CxIterator cxListIteratorAt(const CxList *list, size_t index) { 602 CxIterator cxListIteratorAt(const CxList *list, size_t index) {
766 if (list == NULL) list = cxEmptyList; 603 if (list == NULL) list = cxEmptyList;
767 return list->cl->iterator(list, index, false); 604 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false));
768 } 605 }
769 606
770 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) { 607 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
771 if (list == NULL) list = cxEmptyList; 608 if (list == NULL) list = cxEmptyList;
772 return list->cl->iterator(list, index, true); 609 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true));
773 } 610 }
774 611
775 CxIterator cxListIterator(const CxList *list) { 612 CxIterator cxListIterator(const CxList *list) {
776 if (list == NULL) list = cxEmptyList; 613 if (list == NULL) list = cxEmptyList;
777 return list->cl->iterator(list, 0, false); 614 return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false));
778 } 615 }
779 616
780 CxIterator cxListBackwardsIterator(const CxList *list) { 617 CxIterator cxListBackwardsIterator(const CxList *list) {
781 if (list == NULL) list = cxEmptyList; 618 if (list == NULL) list = cxEmptyList;
782 return list->cl->iterator(list, list->collection.size - 1, true); 619 return cx_pl_iter_wrap(list, list->cl->iterator(list, list->collection.size - 1, true));
783 } 620 }
784 621
785 size_t cxListFind(const CxList *list, const void *elem) { 622 size_t cxListFind(const CxList *list, const void *elem) {
786 return list->cl->find_remove((CxList*)list, elem, false); 623 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false);
787 } 624 }
788 625
789 bool cxListContains(const CxList* list, const void* elem) { 626 bool cxListContains(const CxList* list, const void* elem) {
790 return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size; 627 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false) < list->collection.size;
791 } 628 }
792 629
793 bool cxListIndexValid(const CxList *list, size_t index) { 630 bool cxListIndexValid(const CxList *list, size_t index) {
794 return index < list->collection.size; 631 return index < list->collection.size;
795 } 632 }
796 633
797 size_t cxListFindRemove(CxList *list, const void *elem) { 634 size_t cxListFindRemove(CxList *list, const void *elem) {
798 return list->cl->find_remove(list, elem, true); 635 return list->cl->find_remove(list, cx_ref(list, elem), true);
799 } 636 }
800 637
801 void cxListSort(CxList *list) { 638 void cxListSort(CxList *list) {
802 if (list->collection.sorted) return; 639 if (list->collection.sorted) return;
803 list->cl->sort(list); 640 list->cl->sort(list);
827 } 664 }
828 list->collection.simple_destructor = destr_bak; 665 list->collection.simple_destructor = destr_bak;
829 list->collection.advanced_destructor = destr2_bak; 666 list->collection.advanced_destructor = destr2_bak;
830 } 667 }
831 668
832 static void* cx_list_simple_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) { 669 static void* cx_list_shallow_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) {
833 size_t elem_size = *(size_t*)data; 670 size_t elem_size = *(size_t*)data;
834 if (dst == NULL) dst = cxMalloc(al, elem_size); 671 if (dst == NULL) dst = cxMalloc(al, elem_size);
835 if (dst != NULL) memcpy(dst, src, elem_size); 672 if (dst != NULL) memcpy(dst, src, elem_size);
836 return dst; 673 return dst;
837 } 674 }
838 675
839 #define use_simple_clone_func(list) cx_list_simple_clone_func, NULL, (void*)&((list)->collection.elem_size) 676 #define use_shallow_clone_func(list) cx_list_shallow_clone_func, NULL, (void*)&((list)->collection.elem_size)
840 677
841 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, 678 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func,
842 const CxAllocator *clone_allocator, void *data) { 679 const CxAllocator *clone_allocator, void *data) {
843 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; 680 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
844 681
900 void *min_elem = cxIteratorCurrent(min_iter); 737 void *min_elem = cxIteratorCurrent(min_iter);
901 void *sub_elem; 738 void *sub_elem;
902 int d; 739 int d;
903 if (cxIteratorValid(sub_iter)) { 740 if (cxIteratorValid(sub_iter)) {
904 sub_elem = cxIteratorCurrent(sub_iter); 741 sub_elem = cxIteratorCurrent(sub_iter);
905 cx_compare_func cmp = subtrahend->collection.cmpfunc; 742 d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend);
906 d = cmp(sub_elem, min_elem);
907 } else { 743 } else {
908 // no more elements in the subtrahend, 744 // no more elements in the subtrahend,
909 // i.e., the min_elem is larger than any elem of the subtrahend 745 // i.e., the min_elem is larger than any elem of the subtrahend
910 d = 1; 746 d = 1;
911 } 747 }
969 CxIterator src_iter = cxListIterator(src); 805 CxIterator src_iter = cxListIterator(src);
970 CxIterator other_iter = cxListIterator(other); 806 CxIterator other_iter = cxListIterator(other);
971 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { 807 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
972 void *src_elem = cxIteratorCurrent(src_iter); 808 void *src_elem = cxIteratorCurrent(src_iter);
973 void *other_elem = cxIteratorCurrent(other_iter); 809 void *other_elem = cxIteratorCurrent(other_iter);
974 int d = src->collection.cmpfunc(src_elem, other_elem); 810 int d = cx_list_compare_wrapper(src_elem, other_elem, src);
975 if (d == 0) { 811 if (d == 0) {
976 // is contained, clone it 812 // is contained, clone it
977 void **dst_mem = cxListEmplace(dst); 813 void **dst_mem = cxListEmplace(dst);
978 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; 814 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
979 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data); 815 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
1039 src_elem = cxIteratorCurrent(src_iter); 875 src_elem = cxIteratorCurrent(src_iter);
1040 d = -1; 876 d = -1;
1041 } else { 877 } else {
1042 src_elem = cxIteratorCurrent(src_iter); 878 src_elem = cxIteratorCurrent(src_iter);
1043 other_elem = cxIteratorCurrent(other_iter); 879 other_elem = cxIteratorCurrent(other_iter);
1044 d = src->collection.cmpfunc(src_elem, other_elem); 880 d = cx_list_compare_wrapper(src_elem, other_elem, src);
1045 } 881 }
1046 void *clone_from; 882 void *clone_from;
1047 if (d < 0) { 883 if (d < 0) {
1048 // source element is smaller clone it 884 // source element is smaller clone it
1049 clone_from = src_elem; 885 clone_from = src_elem;
1095 } 931 }
1096 932
1097 return 0; 933 return 0;
1098 } 934 }
1099 935
1100 int cxListCloneSimple(CxList *dst, const CxList *src) { 936 int cxListCloneShallow(CxList *dst, const CxList *src) {
1101 return cxListClone(dst, src, use_simple_clone_func(src)); 937 return cxListClone(dst, src, use_shallow_clone_func(src));
1102 } 938 }
1103 939
1104 int cxListDifferenceSimple(CxList *dst, const CxList *minuend, const CxList *subtrahend) { 940 int cxListDifferenceShallow(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
1105 return cxListDifference(dst, minuend, subtrahend, use_simple_clone_func(minuend)); 941 return cxListDifference(dst, minuend, subtrahend, use_shallow_clone_func(minuend));
1106 } 942 }
1107 943
1108 int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other) { 944 int cxListIntersectionShallow(CxList *dst, const CxList *src, const CxList *other) {
1109 return cxListIntersection(dst, src, other, use_simple_clone_func(src)); 945 return cxListIntersection(dst, src, other, use_shallow_clone_func(src));
1110 } 946 }
1111 947
1112 int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other) { 948 int cxListUnionShallow(CxList *dst, const CxList *src, const CxList *other) {
1113 return cxListUnion(dst, src, other, use_simple_clone_func(src)); 949 return cxListUnion(dst, src, other, use_shallow_clone_func(src));
1114 } 950 }
1115 951
1116 int cxListReserve(CxList *list, size_t capacity) { 952 int cxListReserve(CxList *list, size_t capacity) {
1117 if (list->cl->change_capacity == NULL) { 953 if (list->cl->change_capacity == NULL) {
1118 return 0; 954 return 0;

Mercurial Repository: dbutils

mercurial