Mercurial > hg > ucx / file comparison

comparison: src/list.c

src/list.c

changeset 1618
ef7cab6eb131
parent 1616
bdc04a8e0dd3
equal deleted inserted replaced
1617:d4385f35f8b0 1618:ef7cab6eb131
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 int cx_list_compare_wrapper(const void *l, const void *r, void *c) {
35 35 CxList *list = c;
36 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; 36 const void *left;
37 37 const void *right;
38 static int cx_pl_cmpfunc( 38 if (cxCollectionStoresPointers(list)) {
39 const void *l, 39 left = *(void**)l;
40 const void *r 40 right = *(void**)r;
41 ) { 41 // for historic reasons, we are handling the NULL case here
42 // l and r are guaranteed to be non-NULL pointing to the list's memory 42 // because every UCX compare function does not support NULL arguments
43 void *const *lptr = l; 43 if (left == NULL) {
44 void *const *rptr = r; 44 if (right == NULL) return 0;
45 const void *left = *lptr; 45 return -1;
46 const void *right = *rptr; 46 } else if (right == NULL) {
47 if (left == NULL) { 47 return 1;
48 // NULL is smaller than any value except NULL 48 }
49 return right == NULL ? 0 : -1; 49 } else {
50 } else if (right == NULL) { 50 left = l;
51 // any value is larger than NULL 51 right = r;
52 return 1; 52 }
53 } 53 return cx_invoke_compare_func(list, left, right);
54 return cx_pl_cmpfunc_impl(left, right); 54 }
55 } 55
56 56 #define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c)
57 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
58 // cast away const - this is the hacky thing
59 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
60 cx_pl_cmpfunc_impl = l->cmpfunc;
61 l->cmpfunc = cx_pl_cmpfunc;
62 }
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 57
227 // <editor-fold desc="empty list implementation"> 58 // <editor-fold desc="empty list implementation">
228 59
229 static void cx_emptyl_noop(cx_attr_unused CxList *list) { 60 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
230 // this is a noop, but MUST be implemented 61 // this is a noop, but MUST be implemented
281 }; 112 };
282 113
283 CxList cx_empty_list = { 114 CxList cx_empty_list = {
284 { 115 {
285 NULL, 116 NULL,
286 NULL,
287 0, 117 0,
288 0, 118 0,
119 NULL,
120 NULL,
121 NULL,
289 NULL, 122 NULL,
290 NULL, 123 NULL,
291 NULL, 124 NULL,
292 false, 125 false,
293 true, 126 true,
294 }, 127 },
295 &cx_empty_list_class, 128 &cx_empty_list_class,
296 NULL
297 }; 129 };
298 130
299 CxList *const cxEmptyList = &cx_empty_list; 131 CxList *const cxEmptyList = &cx_empty_list;
300 132
301 // </editor-fold> 133 // </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 134
307 size_t cx_list_default_insert_array( 135 size_t cx_list_default_insert_array(
308 struct cx_list_s *list, 136 struct cx_list_s *list,
309 size_t index, 137 size_t index,
310 const void *data, 138 const void *data,
311 size_t n 139 size_t n
312 ) { 140 ) {
313 const char *src = data; 141 const char *src = data;
314 size_t i = 0; 142 size_t i = 0;
315 for (; i < n; i++) { 143 for (; i < n; i++) {
316 if (NULL == invoke_list_func( 144 if (NULL == list->cl->insert_element(list, index + i, src)
317 insert_element, list, index + i, src)
318 ) { 145 ) {
319 return i; // LCOV_EXCL_LINE 146 return i; // LCOV_EXCL_LINE
320 } 147 }
321 if (src != NULL) { 148 if (src != NULL) {
322 src += list->collection.elem_size; 149 src += list->collection.elem_size;
333 ) { 160 ) {
334 // corner case 161 // corner case
335 if (n == 0) return 0; 162 if (n == 0) return 0;
336 163
337 size_t elem_size = list->collection.elem_size; 164 size_t elem_size = list->collection.elem_size;
338 cx_compare_func cmp = list->collection.cmpfunc;
339 const char *src = sorted_data; 165 const char *src = sorted_data;
340 166
341 // track indices and number of inserted items 167 // track indices and number of inserted items
342 size_t di = 0, si = 0, processed = 0; 168 size_t di = 0, si = 0, processed = 0;
343 169
344 // search the list for insertion points 170 // search the list for insertion points
345 while (di < list->collection.size) { 171 while (di < list->collection.size) {
346 const void *list_elm = invoke_list_func(at, list, di); 172 const void *list_elm = list->cl->at(list, di);
347 173
348 // compare the current list element with the first source element 174 // compare the current list element with the first source element
349 // if less, skip the list elements 175 // if less, skip the list elements
350 // if equal, skip the list elements and optionally the source elements 176 // if equal, skip the list elements and optionally the source elements
351 { 177 {
352 int d = cmp(list_elm, src); 178 int d = cx_list_compare_wrapper(list_elm, src, list);
353 if (d <= 0) { 179 if (d <= 0) {
354 if (!allow_duplicates && d == 0) { 180 if (!allow_duplicates && d == 0) {
355 src += elem_size; 181 src += elem_size;
356 si++; 182 si++;
357 processed++; // we also count duplicates for the return value 183 processed++; // we also count duplicates for the return value
358 while (si < n && cmp(list_elm, src) == 0) { 184 while (si < n && cx_list_compare_wrapper(list_elm, src, list) == 0) {
359 src += elem_size; 185 src += elem_size;
360 si++; 186 si++;
361 processed++; 187 processed++;
362 } 188 }
363 if (processed == n) { 189 if (processed == n) {
373 size_t ins = 1, skip = 0; 199 size_t ins = 1, skip = 0;
374 const char *next = src; 200 const char *next = src;
375 while (++si < n) { 201 while (++si < n) {
376 if (!allow_duplicates) { 202 if (!allow_duplicates) {
377 // skip duplicates within the source 203 // skip duplicates within the source
378 if (cmp(next, next + elem_size) == 0) { 204 if (cx_list_compare_wrapper(next, next + elem_size, list) == 0) {
379 next += elem_size; 205 next += elem_size;
380 skip++; 206 skip++;
381 continue; 207 continue;
382 } else { 208 } else {
383 if (skip > 0) { 209 if (skip > 0) {
387 } 213 }
388 } 214 }
389 } 215 }
390 next += elem_size; 216 next += elem_size;
391 // once we become larger than the list elem, break 217 // once we become larger than the list elem, break
392 if (cmp(list_elm, next) <= 0) { 218 if (cx_list_compare_wrapper(list_elm, next, list) <= 0) {
393 break; 219 break;
394 } 220 }
395 // otherwise, we can insert one more 221 // otherwise, we can insert one more
396 ins++; 222 ins++;
397 } 223 }
398 224
399 // insert the elements at location si 225 // insert the elements at location si
400 if (ins == 1) { 226 if (ins == 1) {
401 if (NULL == invoke_list_func(insert_element, list, di, src)) { 227 if (NULL == list->cl->insert_element(list, di, src)) {
402 return processed; // LCOV_EXCL_LINE 228 return processed; // LCOV_EXCL_LINE
403 } 229 }
404 } else { 230 } else {
405 size_t r = invoke_list_func(insert_array, list, di, src, ins); 231 size_t r = list->cl->insert_array(list, di, src, ins);
406 if (r < ins) { 232 if (r < ins) {
407 return processed + r; // LCOV_EXCL_LINE 233 return processed + r; // LCOV_EXCL_LINE
408 } 234 }
409 } 235 }
410 processed += ins + skip; 236 processed += ins + skip;
418 } 244 }
419 245
420 // insert remaining items 246 // insert remaining items
421 if (si < n) { 247 if (si < n) {
422 if (allow_duplicates) { 248 if (allow_duplicates) {
423 processed += invoke_list_func(insert_array, list, di, src, n - si); 249 processed += list->cl->insert_array(list, di, src, n - si);
424 } else { 250 } else {
425 const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1); 251 const void *last = di == 0 ? NULL : list->cl->at(list, di - 1);
426 for (; si < n; si++) { 252 for (; si < n; si++) {
427 // skip duplicates within the source 253 // skip duplicates within the source
428 if (last == NULL || cmp(last, src) != 0) { 254 if (last == NULL || cx_list_compare_wrapper(last, src, list) != 0) {
429 if (NULL == invoke_list_func(insert_element, list, di, src)) { 255 if (NULL == list->cl->insert_element(list, di, src)) {
430 return processed; // LCOV_EXCL_LINE 256 return processed; // LCOV_EXCL_LINE
431 } 257 }
432 last = src; 258 last = src;
433 di++; 259 di++;
434 } 260 }
455 size_t n 281 size_t n
456 ) { 282 ) {
457 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); 283 return cx_list_default_insert_sorted_impl(list, sorted_data, n, false);
458 } 284 }
459 285
286 // TODO: remove this hack once we have a solution for qsort() / qsort_s()
287 static _Thread_local CxList *cx_hack_for_qsort_list;
288 static int cx_hack_cmp_for_qsort(const void *l, const void *r) {
289 return cx_list_compare_wrapper(l, r, cx_hack_for_qsort_list);
290 }
291
460 void cx_list_default_sort(struct cx_list_s *list) { 292 void cx_list_default_sort(struct cx_list_s *list) {
461 size_t elem_size = list->collection.elem_size; 293 size_t elem_size = list->collection.elem_size;
462 size_t list_size = list->collection.size; 294 size_t list_size = list->collection.size;
463 void *tmp = cxMallocDefault(elem_size * list_size); 295 void *tmp = cxMallocDefault(elem_size * list_size);
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 // TODO: qsort_s() is not as nice as we thought
476 list->collection.cmpfunc); 308 cx_hack_for_qsort_list = list;
309 qsort(tmp, list_size, elem_size, cx_hack_cmp_for_qsort);
477 310
478 // copy elements back 311 // copy elements back
479 loc = tmp; 312 loc = tmp;
480 for (size_t i = 0; i < list_size; i++) { 313 for (size_t i = 0; i < list_size; i++) {
481 void *dest = invoke_list_func(at, list, i); 314 void *dest = list->cl->at(list, i);
482 memcpy(dest, loc, elem_size); 315 memcpy(dest, loc, elem_size);
483 loc += elem_size; 316 loc += elem_size;
484 } 317 }
485 318
486 cxFreeDefault(tmp); 319 cxFreeDefault(tmp);
494 size_t elem_size = list->collection.elem_size; 327 size_t elem_size = list->collection.elem_size;
495 328
496 void *tmp = cxMallocDefault(elem_size); 329 void *tmp = cxMallocDefault(elem_size);
497 if (tmp == NULL) return 1; // LCOV_EXCL_LINE 330 if (tmp == NULL) return 1; // LCOV_EXCL_LINE
498 331
499 void *ip = invoke_list_func(at, list, i); 332 void *ip = list->cl->at(list, i);
500 void *jp = invoke_list_func(at, list, j); 333 void *jp = list->cl->at(list, j);
501 334
502 memcpy(tmp, ip, elem_size); 335 memcpy(tmp, ip, elem_size);
503 memcpy(ip, jp, elem_size); 336 memcpy(ip, jp, elem_size);
504 memcpy(jp, tmp, elem_size); 337 memcpy(jp, tmp, elem_size);
505 338
514 const struct cx_allocator_s *allocator, 347 const struct cx_allocator_s *allocator,
515 size_t elem_size 348 size_t elem_size
516 ) { 349 ) {
517 list->cl = cl; 350 list->cl = cl;
518 list->collection.allocator = allocator; 351 list->collection.allocator = allocator;
519 list->collection.cmpfunc = NULL; 352 list->collection.size = 0;
353 list->collection.sorted = false; // should be set by the implementation
520 if (elem_size > 0) { 354 if (elem_size > 0) {
521 list->collection.elem_size = elem_size; 355 list->collection.elem_size = elem_size;
356 list->collection.simple_cmp = NULL;
357 list->collection.advanced_cmp = cx_acmp_memcmp;
358 list->collection.cmp_data = &list->collection.elem_size;
359 list->collection.store_pointer = false;
522 } else { 360 } else {
523 list->collection.elem_size = sizeof(void *); 361 list->collection.elem_size = sizeof(void *);
524 if (list->collection.cmpfunc == NULL) { 362 list->collection.simple_cmp = cx_cmp_ptr;
525 list->collection.cmpfunc = cx_cmp_ptr; 363 list->collection.advanced_cmp = NULL;
526 } 364 list->collection.cmp_data = NULL;
527 list->collection.store_pointer = true; 365 list->collection.store_pointer = true;
528 list->climpl = list->cl;
529 list->cl = &cx_pointer_list_class;
530 } 366 }
531 } 367 }
532 368
533 int cxListCompare( 369 int cxListCompare(
534 const CxList *list, 370 const CxList *list,
535 const CxList *other 371 const CxList *other
536 ) { 372 ) {
373 // check if we cannot use the list internal function
537 bool cannot_optimize = false; 374 bool cannot_optimize = false;
538 375
539 // if one is storing pointers but the other is not 376 // if one is storing pointers but the other is not
540 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; 377 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
541 378
542 // if one class is wrapped but the other is not 379 // check if the lists are incompatible or this list does not implement compare
543 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); 380 cx_compare_func list_cmp = (cx_compare_func) list->cl->compare;
544 381 cx_compare_func other_cmp = (cx_compare_func) other->cl->compare;
545 // if the compare functions do not match or both are NULL 382 cannot_optimize |= list_cmp != other_cmp;
546 if (!cannot_optimize) { 383 cannot_optimize |= list_cmp == NULL;
547 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
548 list->climpl->compare : list->cl->compare);
549 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
550 other->climpl->compare : other->cl->compare);
551 cannot_optimize |= list_cmp != other_cmp;
552 cannot_optimize |= list_cmp == NULL;
553 }
554 384
555 if (cannot_optimize) { 385 if (cannot_optimize) {
556 // lists are definitely different - cannot use internal compare function 386 // lists are definitely different - cannot use internal compare function
557 if (list->collection.size == other->collection.size) { 387 if (list->collection.size == other->collection.size) {
558 CxIterator left = list->cl->iterator(list, 0, false); 388 CxIterator left = cxListIterator(list);
559 CxIterator right = other->cl->iterator(other, 0, false); 389 CxIterator right = cxListIterator(other);
560 for (size_t i = 0; i < list->collection.size; i++) { 390 for (size_t i = 0; i < list->collection.size; i++) {
561 void *leftValue = cxIteratorCurrent(left); 391 void *leftValue = cxIteratorCurrent(left);
562 void *rightValue = cxIteratorCurrent(right); 392 void *rightValue = cxIteratorCurrent(right);
563 int d = list->collection.cmpfunc(leftValue, rightValue); 393 // values are already unwrapped, invoke immediately
394 int d = cx_invoke_compare_func(list, leftValue, rightValue);
564 if (d != 0) { 395 if (d != 0) {
565 return d; 396 return d;
566 } 397 }
567 cxIteratorNext(left); 398 cxIteratorNext(left);
568 cxIteratorNext(right); 399 cxIteratorNext(right);
581 return list->collection.size; 412 return list->collection.size;
582 } 413 }
583 414
584 int cxListAdd(CxList *list, const void *elem) { 415 int cxListAdd(CxList *list, const void *elem) {
585 list->collection.sorted = false; 416 list->collection.sorted = false;
586 return list->cl->insert_element(list, list->collection.size, elem) == NULL; 417 return list->cl->insert_element(list, list->collection.size, cx_ref(list, elem)) == NULL;
587 } 418 }
588 419
589 size_t cxListAddArray(CxList *list, const void *array, size_t n) { 420 size_t cxListAddArray(CxList *list, const void *array, size_t n) {
590 list->collection.sorted = false; 421 list->collection.sorted = false;
591 return list->cl->insert_array(list, list->collection.size, array, n); 422 return list->cl->insert_array(list, list->collection.size, array, n);
592 } 423 }
593 424
594 int cxListInsert(CxList *list, size_t index, const void *elem) { 425 int cxListInsert(CxList *list, size_t index, const void *elem) {
595 list->collection.sorted = false; 426 list->collection.sorted = false;
596 return list->cl->insert_element(list, index, elem) == NULL; 427 return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL;
597 } 428 }
598 429
599 void *cxListEmplaceAt(CxList *list, size_t index) { 430 void *cxListEmplaceAt(CxList *list, size_t index) {
600 list->collection.sorted = false; 431 list->collection.sorted = false;
601 return list->cl->insert_element(list, index, NULL); 432 return list->cl->insert_element(list, index, NULL);
618 // tweak the fields of this iterator 449 // tweak the fields of this iterator
619 iter.elem_count = c; 450 iter.elem_count = c;
620 iter.index = 0; 451 iter.index = 0;
621 // replace the valid function to abort iteration when c is reached 452 // replace the valid function to abort iteration when c is reached
622 iter.base.valid = cx_list_emplace_iterator_valid; 453 iter.base.valid = cx_list_emplace_iterator_valid;
623 // if we are storing pointers, we want to return the pure pointers.
624 // therefore, we must unwrap the "current" method
625 if (list->collection.store_pointer) {
626 iter.base.current = iter.base.current_impl;
627 }
628 return iter; 454 return iter;
629 } 455 }
630 456
631 CxIterator cxListEmplaceArray(CxList *list, size_t n) { 457 CxIterator cxListEmplaceArray(CxList *list, size_t n) {
632 return cxListEmplaceArrayAt(list, list->collection.size, n); 458 return cxListEmplaceArrayAt(list, list->collection.size, n);
633 } 459 }
634 460
635 int cxListInsertSorted(CxList *list, const void *elem) { 461 int cxListInsertSorted(CxList *list, const void *elem) {
636 assert(cxCollectionSorted(list)); 462 assert(cxCollectionSorted(list));
637 list->collection.sorted = true; 463 list->collection.sorted = true;
638 const void *data = list->collection.store_pointer ? &elem : elem; 464 return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0;
639 return list->cl->insert_sorted(list, data, 1) == 0;
640 } 465 }
641 466
642 int cxListInsertUnique(CxList *list, const void *elem) { 467 int cxListInsertUnique(CxList *list, const void *elem) {
643 if (cxCollectionSorted(list)) { 468 if (cxCollectionSorted(list)) {
644 list->collection.sorted = true; 469 list->collection.sorted = true;
645 const void *data = list->collection.store_pointer ? &elem : elem; 470 return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0;
646 return list->cl->insert_unique(list, data, 1) == 0;
647 } else { 471 } else {
648 if (cxListContains(list, elem)) { 472 if (cxListContains(list, elem)) {
649 return 0; 473 return 0;
650 } else { 474 } else {
651 return cxListAdd(list, elem); 475 return cxListAdd(list, elem);
670 return list->cl->insert_unique(list, array, n); 494 return list->cl->insert_unique(list, array, n);
671 } else { 495 } else {
672 const char *source = array; 496 const char *source = array;
673 for (size_t i = 0 ; i < n; i++) { 497 for (size_t i = 0 ; i < n; i++) {
674 // note: this also checks elements added in a previous iteration 498 // note: this also checks elements added in a previous iteration
675 const void *data = list->collection.store_pointer ? 499 const void *data = cx_deref(list, source);
676 *((const void**)source) : source;
677 if (!cxListContains(list, data)) { 500 if (!cxListContains(list, data)) {
678 if (cxListAdd(list, data)) { 501 if (cxListAdd(list, data)) {
679 return i; // LCOV_EXCL_LINE 502 return i; // LCOV_EXCL_LINE
680 } 503 }
681 } 504 }
684 return n; 507 return n;
685 } 508 }
686 } 509 }
687 510
688 int cxListInsertAfter(CxIterator *iter, const void *elem) { 511 int cxListInsertAfter(CxIterator *iter, const void *elem) {
689 CxList* list = (CxList*)iter->src_handle; 512 CxList* list = iter->src_handle;
690 list->collection.sorted = false; 513 list->collection.sorted = false;
691 return list->cl->insert_iter(iter, elem, 0); 514 return list->cl->insert_iter(iter, cx_ref(list, elem), 0);
692 } 515 }
693 516
694 int cxListInsertBefore(CxIterator *iter, const void *elem) { 517 int cxListInsertBefore(CxIterator *iter, const void *elem) {
695 CxList* list = (CxList*)iter->src_handle; 518 CxList* list = iter->src_handle;
696 list->collection.sorted = false; 519 list->collection.sorted = false;
697 return list->cl->insert_iter(iter, elem, 1); 520 return list->cl->insert_iter(iter, cx_ref(list, elem), 1);
698 } 521 }
699 522
700 int cxListRemove(CxList *list, size_t index) { 523 int cxListRemove(CxList *list, size_t index) {
701 return list->cl->remove(list, index, 1, NULL) == 0; 524 return list->cl->remove(list, index, 1, NULL) == 0;
702 } 525 }
731 list->collection.sorted = false; 554 list->collection.sorted = false;
732 return list->cl->swap(list, i, j); 555 return list->cl->swap(list, i, j);
733 } 556 }
734 557
735 void *cxListAt(const CxList *list, size_t index) { 558 void *cxListAt(const CxList *list, size_t index) {
736 return list->cl->at(list, index); 559 void *result = list->cl->at(list, index);
560 if (result == NULL) return NULL;
561 return cx_deref(list, result);
737 } 562 }
738 563
739 void *cxListFirst(const CxList *list) { 564 void *cxListFirst(const CxList *list) {
740 return list->cl->at(list, 0); 565 return cxListAt(list, 0);
741 } 566 }
742 567
743 void *cxListLast(const CxList *list) { 568 void *cxListLast(const CxList *list) {
744 return list->cl->at(list, list->collection.size - 1); 569 return cxListAt(list, list->collection.size - 1);
745 } 570 }
746 571
747 int cxListSet(CxList *list, size_t index, const void *elem) { 572 int cxListSet(CxList *list, size_t index, const void *elem) {
748 if (index >= list->collection.size) { 573 if (index >= list->collection.size) {
749 return 1; 574 return 1;
750 } 575 }
751 576
752 if (list->collection.store_pointer) { 577 if (list->collection.store_pointer) {
753 // For pointer collections, always use climpl 578 void **target = list->cl->at(list, index);
754 void **target = list->climpl->at(list, index);
755 *target = (void *)elem; 579 *target = (void *)elem;
756 } else { 580 } else {
757 void *target = list->cl->at(list, index); 581 void *target = list->cl->at(list, index);
758 memcpy(target, elem, list->collection.elem_size); 582 memcpy(target, elem, list->collection.elem_size);
759 } 583 }
760 584
761 return 0; 585 return 0;
762 } 586 }
763 587
588 static void *cx_pl_iter_current(const void *it) {
589 const struct cx_iterator_s *iter = it;
590 void **ptr = iter->base.current_impl(it);
591 return ptr == NULL ? NULL : *ptr;
592 }
593
594 CX_INLINE CxIterator cx_pl_iter_wrap(const CxList *list, CxIterator iter) {
595 if (cxCollectionStoresPointers(list)) {
596 iter.base.current_impl = iter.base.current;
597 iter.base.current = cx_pl_iter_current;
598 return iter;
599 } else {
600 return iter;
601 }
602 }
603
764 CxIterator cxListIteratorAt(const CxList *list, size_t index) { 604 CxIterator cxListIteratorAt(const CxList *list, size_t index) {
765 if (list == NULL) list = cxEmptyList; 605 if (list == NULL) list = cxEmptyList;
766 return list->cl->iterator(list, index, false); 606 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false));
767 } 607 }
768 608
769 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) { 609 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
770 if (list == NULL) list = cxEmptyList; 610 if (list == NULL) list = cxEmptyList;
771 return list->cl->iterator(list, index, true); 611 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true));
772 } 612 }
773 613
774 CxIterator cxListIterator(const CxList *list) { 614 CxIterator cxListIterator(const CxList *list) {
775 if (list == NULL) list = cxEmptyList; 615 if (list == NULL) list = cxEmptyList;
776 return list->cl->iterator(list, 0, false); 616 return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false));
777 } 617 }
778 618
779 CxIterator cxListBackwardsIterator(const CxList *list) { 619 CxIterator cxListBackwardsIterator(const CxList *list) {
780 if (list == NULL) list = cxEmptyList; 620 if (list == NULL) list = cxEmptyList;
781 return list->cl->iterator(list, list->collection.size - 1, true); 621 return cx_pl_iter_wrap(list, list->cl->iterator(list, list->collection.size - 1, true));
782 } 622 }
783 623
784 size_t cxListFind(const CxList *list, const void *elem) { 624 size_t cxListFind(const CxList *list, const void *elem) {
785 return list->cl->find_remove((CxList*)list, elem, false); 625 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false);
786 } 626 }
787 627
788 bool cxListContains(const CxList* list, const void* elem) { 628 bool cxListContains(const CxList* list, const void* elem) {
789 return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size; 629 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false) < list->collection.size;
790 } 630 }
791 631
792 bool cxListIndexValid(const CxList *list, size_t index) { 632 bool cxListIndexValid(const CxList *list, size_t index) {
793 return index < list->collection.size; 633 return index < list->collection.size;
794 } 634 }
795 635
796 size_t cxListFindRemove(CxList *list, const void *elem) { 636 size_t cxListFindRemove(CxList *list, const void *elem) {
797 return list->cl->find_remove(list, elem, true); 637 return list->cl->find_remove(list, cx_ref(list, elem), true);
798 } 638 }
799 639
800 void cxListSort(CxList *list) { 640 void cxListSort(CxList *list) {
801 if (list->collection.sorted) return; 641 if (list->collection.sorted) return;
802 list->cl->sort(list); 642 list->cl->sort(list);
899 void *min_elem = cxIteratorCurrent(min_iter); 739 void *min_elem = cxIteratorCurrent(min_iter);
900 void *sub_elem; 740 void *sub_elem;
901 int d; 741 int d;
902 if (cxIteratorValid(sub_iter)) { 742 if (cxIteratorValid(sub_iter)) {
903 sub_elem = cxIteratorCurrent(sub_iter); 743 sub_elem = cxIteratorCurrent(sub_iter);
904 cx_compare_func cmp = subtrahend->collection.cmpfunc; 744 d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend);
905 d = cmp(sub_elem, min_elem);
906 } else { 745 } else {
907 // no more elements in the subtrahend, 746 // no more elements in the subtrahend,
908 // i.e., the min_elem is larger than any elem of the subtrahend 747 // i.e., the min_elem is larger than any elem of the subtrahend
909 d = 1; 748 d = 1;
910 } 749 }
968 CxIterator src_iter = cxListIterator(src); 807 CxIterator src_iter = cxListIterator(src);
969 CxIterator other_iter = cxListIterator(other); 808 CxIterator other_iter = cxListIterator(other);
970 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { 809 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
971 void *src_elem = cxIteratorCurrent(src_iter); 810 void *src_elem = cxIteratorCurrent(src_iter);
972 void *other_elem = cxIteratorCurrent(other_iter); 811 void *other_elem = cxIteratorCurrent(other_iter);
973 int d = src->collection.cmpfunc(src_elem, other_elem); 812 int d = cx_list_compare_wrapper(src_elem, other_elem, src);
974 if (d == 0) { 813 if (d == 0) {
975 // is contained, clone it 814 // is contained, clone it
976 void **dst_mem = cxListEmplace(dst); 815 void **dst_mem = cxListEmplace(dst);
977 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; 816 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
978 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data); 817 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
1038 src_elem = cxIteratorCurrent(src_iter); 877 src_elem = cxIteratorCurrent(src_iter);
1039 d = -1; 878 d = -1;
1040 } else { 879 } else {
1041 src_elem = cxIteratorCurrent(src_iter); 880 src_elem = cxIteratorCurrent(src_iter);
1042 other_elem = cxIteratorCurrent(other_iter); 881 other_elem = cxIteratorCurrent(other_iter);
1043 d = src->collection.cmpfunc(src_elem, other_elem); 882 d = cx_list_compare_wrapper(src_elem, other_elem, src);
1044 } 883 }
1045 void *clone_from; 884 void *clone_from;
1046 if (d < 0) { 885 if (d < 0) {
1047 // source element is smaller clone it 886 // source element is smaller clone it
1048 clone_from = src_elem; 887 clone_from = src_elem;

Mercurial Repository: ucx

mercurial