Mercurial > hg > toolkit / file comparison

comparison: ucx/list.c

ucx/list.c

changeset 1016
ccde46662db7
parent 943
9b5948aa5b90
equal deleted inserted replaced
1015:b459361d98ad 1016:ccde46662db7
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
510 343
511 void cx_list_init( 344 void cx_list_init(
512 struct cx_list_s *list, 345 struct cx_list_s *list,
513 struct cx_list_class_s *cl, 346 struct cx_list_class_s *cl,
514 const struct cx_allocator_s *allocator, 347 const struct cx_allocator_s *allocator,
515 cx_compare_func comparator,
516 size_t elem_size 348 size_t elem_size
517 ) { 349 ) {
518 list->cl = cl; 350 list->cl = cl;
519 list->collection.allocator = allocator; 351 list->collection.allocator = allocator;
520 list->collection.cmpfunc = comparator; 352 list->collection.size = 0;
353 list->collection.sorted = false; // should be set by the implementation
521 if (elem_size > 0) { 354 if (elem_size > 0) {
522 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;
523 } else { 360 } else {
524 list->collection.elem_size = sizeof(void *); 361 list->collection.elem_size = sizeof(void *);
525 if (list->collection.cmpfunc == NULL) { 362 list->collection.simple_cmp = cx_cmp_ptr;
526 list->collection.cmpfunc = cx_cmp_ptr; 363 list->collection.advanced_cmp = NULL;
527 } 364 list->collection.cmp_data = NULL;
528 list->collection.store_pointer = true; 365 list->collection.store_pointer = true;
529 list->climpl = list->cl;
530 list->cl = &cx_pointer_list_class;
531 } 366 }
532 } 367 }
533 368
534 int cxListCompare( 369 int cxListCompare(
535 const CxList *list, 370 const CxList *list,
536 const CxList *other 371 const CxList *other
537 ) { 372 ) {
373 // check if we cannot use the list internal function
538 bool cannot_optimize = false; 374 bool cannot_optimize = false;
539 375
540 // if one is storing pointers but the other is not 376 // if one is storing pointers but the other is not
541 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; 377 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
542 378
543 // if one class is wrapped but the other is not 379 // check if the lists are incompatible or this list does not implement compare
544 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); 380 cx_compare_func list_cmp = (cx_compare_func) list->cl->compare;
545 381 cx_compare_func other_cmp = (cx_compare_func) other->cl->compare;
546 // if the compare functions do not match or both are NULL 382 cannot_optimize |= list_cmp != other_cmp;
547 if (!cannot_optimize) { 383 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 384
556 if (cannot_optimize) { 385 if (cannot_optimize) {
557 // lists are definitely different - cannot use internal compare function 386 // lists are definitely different - cannot use internal compare function
558 if (list->collection.size == other->collection.size) { 387 if (list->collection.size == other->collection.size) {
559 CxIterator left = list->cl->iterator(list, 0, false); 388 CxIterator left = cxListIterator(list);
560 CxIterator right = other->cl->iterator(other, 0, false); 389 CxIterator right = cxListIterator(other);
561 for (size_t i = 0; i < list->collection.size; i++) { 390 for (size_t i = 0; i < list->collection.size; i++) {
562 void *leftValue = cxIteratorCurrent(left); 391 void *leftValue = cxIteratorCurrent(left);
563 void *rightValue = cxIteratorCurrent(right); 392 void *rightValue = cxIteratorCurrent(right);
564 int d = list->collection.cmpfunc(leftValue, rightValue); 393 // values are already unwrapped, invoke immediately
394 int d = cx_invoke_compare_func(list, leftValue, rightValue);
565 if (d != 0) { 395 if (d != 0) {
566 return d; 396 return d;
567 } 397 }
568 cxIteratorNext(left); 398 cxIteratorNext(left);
569 cxIteratorNext(right); 399 cxIteratorNext(right);
582 return list->collection.size; 412 return list->collection.size;
583 } 413 }
584 414
585 int cxListAdd(CxList *list, const void *elem) { 415 int cxListAdd(CxList *list, const void *elem) {
586 list->collection.sorted = false; 416 list->collection.sorted = false;
587 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;
588 } 418 }
589 419
590 size_t cxListAddArray(CxList *list, const void *array, size_t n) { 420 size_t cxListAddArray(CxList *list, const void *array, size_t n) {
591 list->collection.sorted = false; 421 list->collection.sorted = false;
592 return list->cl->insert_array(list, list->collection.size, array, n); 422 return list->cl->insert_array(list, list->collection.size, array, n);
593 } 423 }
594 424
595 int cxListInsert(CxList *list, size_t index, const void *elem) { 425 int cxListInsert(CxList *list, size_t index, const void *elem) {
596 list->collection.sorted = false; 426 list->collection.sorted = false;
597 return list->cl->insert_element(list, index, elem) == NULL; 427 return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL;
598 } 428 }
599 429
600 void *cxListEmplaceAt(CxList *list, size_t index) { 430 void *cxListEmplaceAt(CxList *list, size_t index) {
601 list->collection.sorted = false; 431 list->collection.sorted = false;
602 return list->cl->insert_element(list, index, NULL); 432 return list->cl->insert_element(list, index, NULL);
619 // tweak the fields of this iterator 449 // tweak the fields of this iterator
620 iter.elem_count = c; 450 iter.elem_count = c;
621 iter.index = 0; 451 iter.index = 0;
622 // replace the valid function to abort iteration when c is reached 452 // replace the valid function to abort iteration when c is reached
623 iter.base.valid = cx_list_emplace_iterator_valid; 453 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; 454 return iter;
630 } 455 }
631 456
632 CxIterator cxListEmplaceArray(CxList *list, size_t n) { 457 CxIterator cxListEmplaceArray(CxList *list, size_t n) {
633 return cxListEmplaceArrayAt(list, list->collection.size, n); 458 return cxListEmplaceArrayAt(list, list->collection.size, n);
634 } 459 }
635 460
636 int cxListInsertSorted(CxList *list, const void *elem) { 461 int cxListInsertSorted(CxList *list, const void *elem) {
637 assert(cxCollectionSorted(list)); 462 assert(cxCollectionSorted(list));
638 list->collection.sorted = true; 463 list->collection.sorted = true;
639 const void *data = list->collection.store_pointer ? &elem : elem; 464 return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0;
640 return list->cl->insert_sorted(list, data, 1) == 0;
641 } 465 }
642 466
643 int cxListInsertUnique(CxList *list, const void *elem) { 467 int cxListInsertUnique(CxList *list, const void *elem) {
644 if (cxCollectionSorted(list)) { 468 if (cxCollectionSorted(list)) {
645 list->collection.sorted = true; 469 list->collection.sorted = true;
646 const void *data = list->collection.store_pointer ? &elem : elem; 470 return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0;
647 return list->cl->insert_unique(list, data, 1) == 0;
648 } else { 471 } else {
649 if (cxListContains(list, elem)) { 472 if (cxListContains(list, elem)) {
650 return 0; 473 return 0;
651 } else { 474 } else {
652 return cxListAdd(list, elem); 475 return cxListAdd(list, elem);
671 return list->cl->insert_unique(list, array, n); 494 return list->cl->insert_unique(list, array, n);
672 } else { 495 } else {
673 const char *source = array; 496 const char *source = array;
674 for (size_t i = 0 ; i < n; i++) { 497 for (size_t i = 0 ; i < n; i++) {
675 // note: this also checks elements added in a previous iteration 498 // note: this also checks elements added in a previous iteration
676 const void *data = list->collection.store_pointer ? 499 const void *data = cx_deref(list, source);
677 *((const void**)source) : source;
678 if (!cxListContains(list, data)) { 500 if (!cxListContains(list, data)) {
679 if (cxListAdd(list, data)) { 501 if (cxListAdd(list, data)) {
680 return i; // LCOV_EXCL_LINE 502 return i; // LCOV_EXCL_LINE
681 } 503 }
682 } 504 }
685 return n; 507 return n;
686 } 508 }
687 } 509 }
688 510
689 int cxListInsertAfter(CxIterator *iter, const void *elem) { 511 int cxListInsertAfter(CxIterator *iter, const void *elem) {
690 CxList* list = (CxList*)iter->src_handle; 512 CxList* list = iter->src_handle;
691 list->collection.sorted = false; 513 list->collection.sorted = false;
692 return list->cl->insert_iter(iter, elem, 0); 514 return list->cl->insert_iter(iter, cx_ref(list, elem), 0);
693 } 515 }
694 516
695 int cxListInsertBefore(CxIterator *iter, const void *elem) { 517 int cxListInsertBefore(CxIterator *iter, const void *elem) {
696 CxList* list = (CxList*)iter->src_handle; 518 CxList* list = iter->src_handle;
697 list->collection.sorted = false; 519 list->collection.sorted = false;
698 return list->cl->insert_iter(iter, elem, 1); 520 return list->cl->insert_iter(iter, cx_ref(list, elem), 1);
699 } 521 }
700 522
701 int cxListRemove(CxList *list, size_t index) { 523 int cxListRemove(CxList *list, size_t index) {
702 return list->cl->remove(list, index, 1, NULL) == 0; 524 return list->cl->remove(list, index, 1, NULL) == 0;
703 } 525 }
732 list->collection.sorted = false; 554 list->collection.sorted = false;
733 return list->cl->swap(list, i, j); 555 return list->cl->swap(list, i, j);
734 } 556 }
735 557
736 void *cxListAt(const CxList *list, size_t index) { 558 void *cxListAt(const CxList *list, size_t index) {
737 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);
738 } 562 }
739 563
740 void *cxListFirst(const CxList *list) { 564 void *cxListFirst(const CxList *list) {
741 return list->cl->at(list, 0); 565 return cxListAt(list, 0);
742 } 566 }
743 567
744 void *cxListLast(const CxList *list) { 568 void *cxListLast(const CxList *list) {
745 return list->cl->at(list, list->collection.size - 1); 569 return cxListAt(list, list->collection.size - 1);
746 } 570 }
747 571
748 int cxListSet(CxList *list, size_t index, const void *elem) { 572 int cxListSet(CxList *list, size_t index, const void *elem) {
749 if (index >= list->collection.size) { 573 if (index >= list->collection.size) {
750 return 1; 574 return 1;
751 } 575 }
752 576
753 if (list->collection.store_pointer) { 577 if (list->collection.store_pointer) {
754 // For pointer collections, always use climpl 578 void **target = list->cl->at(list, index);
755 void **target = list->climpl->at(list, index);
756 *target = (void *)elem; 579 *target = (void *)elem;
757 } else { 580 } else {
758 void *target = list->cl->at(list, index); 581 void *target = list->cl->at(list, index);
759 memcpy(target, elem, list->collection.elem_size); 582 memcpy(target, elem, list->collection.elem_size);
760 } 583 }
761 584
762 return 0; 585 return 0;
763 } 586 }
764 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
765 CxIterator cxListIteratorAt(const CxList *list, size_t index) { 604 CxIterator cxListIteratorAt(const CxList *list, size_t index) {
766 if (list == NULL) list = cxEmptyList; 605 if (list == NULL) list = cxEmptyList;
767 return list->cl->iterator(list, index, false); 606 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false));
768 } 607 }
769 608
770 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) { 609 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
771 if (list == NULL) list = cxEmptyList; 610 if (list == NULL) list = cxEmptyList;
772 return list->cl->iterator(list, index, true); 611 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true));
773 } 612 }
774 613
775 CxIterator cxListIterator(const CxList *list) { 614 CxIterator cxListIterator(const CxList *list) {
776 if (list == NULL) list = cxEmptyList; 615 if (list == NULL) list = cxEmptyList;
777 return list->cl->iterator(list, 0, false); 616 return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false));
778 } 617 }
779 618
780 CxIterator cxListBackwardsIterator(const CxList *list) { 619 CxIterator cxListBackwardsIterator(const CxList *list) {
781 if (list == NULL) list = cxEmptyList; 620 if (list == NULL) list = cxEmptyList;
782 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));
783 } 622 }
784 623
785 size_t cxListFind(const CxList *list, const void *elem) { 624 size_t cxListFind(const CxList *list, const void *elem) {
786 return list->cl->find_remove((CxList*)list, elem, false); 625 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false);
787 } 626 }
788 627
789 bool cxListContains(const CxList* list, const void* elem) { 628 bool cxListContains(const CxList* list, const void* elem) {
790 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;
791 } 630 }
792 631
793 bool cxListIndexValid(const CxList *list, size_t index) { 632 bool cxListIndexValid(const CxList *list, size_t index) {
794 return index < list->collection.size; 633 return index < list->collection.size;
795 } 634 }
796 635
797 size_t cxListFindRemove(CxList *list, const void *elem) { 636 size_t cxListFindRemove(CxList *list, const void *elem) {
798 return list->cl->find_remove(list, elem, true); 637 return list->cl->find_remove(list, cx_ref(list, elem), true);
799 } 638 }
800 639
801 void cxListSort(CxList *list) { 640 void cxListSort(CxList *list) {
802 if (list->collection.sorted) return; 641 if (list->collection.sorted) return;
803 list->cl->sort(list); 642 list->cl->sort(list);
827 } 666 }
828 list->collection.simple_destructor = destr_bak; 667 list->collection.simple_destructor = destr_bak;
829 list->collection.advanced_destructor = destr2_bak; 668 list->collection.advanced_destructor = destr2_bak;
830 } 669 }
831 670
832 static void* cx_list_simple_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) { 671 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; 672 size_t elem_size = *(size_t*)data;
834 if (dst == NULL) dst = cxMalloc(al, elem_size); 673 if (dst == NULL) dst = cxMalloc(al, elem_size);
835 if (dst != NULL) memcpy(dst, src, elem_size); 674 if (dst != NULL) memcpy(dst, src, elem_size);
836 return dst; 675 return dst;
837 } 676 }
838 677
839 #define use_simple_clone_func(list) cx_list_simple_clone_func, NULL, (void*)&((list)->collection.elem_size) 678 #define use_shallow_clone_func(list) cx_list_shallow_clone_func, NULL, (void*)&((list)->collection.elem_size)
840 679
841 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, 680 int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func,
842 const CxAllocator *clone_allocator, void *data) { 681 const CxAllocator *clone_allocator, void *data) {
843 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; 682 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
844 683
900 void *min_elem = cxIteratorCurrent(min_iter); 739 void *min_elem = cxIteratorCurrent(min_iter);
901 void *sub_elem; 740 void *sub_elem;
902 int d; 741 int d;
903 if (cxIteratorValid(sub_iter)) { 742 if (cxIteratorValid(sub_iter)) {
904 sub_elem = cxIteratorCurrent(sub_iter); 743 sub_elem = cxIteratorCurrent(sub_iter);
905 cx_compare_func cmp = subtrahend->collection.cmpfunc; 744 d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend);
906 d = cmp(sub_elem, min_elem);
907 } else { 745 } else {
908 // no more elements in the subtrahend, 746 // no more elements in the subtrahend,
909 // 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
910 d = 1; 748 d = 1;
911 } 749 }
969 CxIterator src_iter = cxListIterator(src); 807 CxIterator src_iter = cxListIterator(src);
970 CxIterator other_iter = cxListIterator(other); 808 CxIterator other_iter = cxListIterator(other);
971 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { 809 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
972 void *src_elem = cxIteratorCurrent(src_iter); 810 void *src_elem = cxIteratorCurrent(src_iter);
973 void *other_elem = cxIteratorCurrent(other_iter); 811 void *other_elem = cxIteratorCurrent(other_iter);
974 int d = src->collection.cmpfunc(src_elem, other_elem); 812 int d = cx_list_compare_wrapper(src_elem, other_elem, src);
975 if (d == 0) { 813 if (d == 0) {
976 // is contained, clone it 814 // is contained, clone it
977 void **dst_mem = cxListEmplace(dst); 815 void **dst_mem = cxListEmplace(dst);
978 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; 816 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
979 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data); 817 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
1039 src_elem = cxIteratorCurrent(src_iter); 877 src_elem = cxIteratorCurrent(src_iter);
1040 d = -1; 878 d = -1;
1041 } else { 879 } else {
1042 src_elem = cxIteratorCurrent(src_iter); 880 src_elem = cxIteratorCurrent(src_iter);
1043 other_elem = cxIteratorCurrent(other_iter); 881 other_elem = cxIteratorCurrent(other_iter);
1044 d = src->collection.cmpfunc(src_elem, other_elem); 882 d = cx_list_compare_wrapper(src_elem, other_elem, src);
1045 } 883 }
1046 void *clone_from; 884 void *clone_from;
1047 if (d < 0) { 885 if (d < 0) {
1048 // source element is smaller clone it 886 // source element is smaller clone it
1049 clone_from = src_elem; 887 clone_from = src_elem;
1095 } 933 }
1096 934
1097 return 0; 935 return 0;
1098 } 936 }
1099 937
1100 int cxListCloneSimple(CxList *dst, const CxList *src) { 938 int cxListCloneShallow(CxList *dst, const CxList *src) {
1101 return cxListClone(dst, src, use_simple_clone_func(src)); 939 return cxListClone(dst, src, use_shallow_clone_func(src));
1102 } 940 }
1103 941
1104 int cxListDifferenceSimple(CxList *dst, const CxList *minuend, const CxList *subtrahend) { 942 int cxListDifferenceShallow(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
1105 return cxListDifference(dst, minuend, subtrahend, use_simple_clone_func(minuend)); 943 return cxListDifference(dst, minuend, subtrahend, use_shallow_clone_func(minuend));
1106 } 944 }
1107 945
1108 int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other) { 946 int cxListIntersectionShallow(CxList *dst, const CxList *src, const CxList *other) {
1109 return cxListIntersection(dst, src, other, use_simple_clone_func(src)); 947 return cxListIntersection(dst, src, other, use_shallow_clone_func(src));
1110 } 948 }
1111 949
1112 int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other) { 950 int cxListUnionShallow(CxList *dst, const CxList *src, const CxList *other) {
1113 return cxListUnion(dst, src, other, use_simple_clone_func(src)); 951 return cxListUnion(dst, src, other, use_shallow_clone_func(src));
1114 } 952 }
1115 953
1116 int cxListReserve(CxList *list, size_t capacity) { 954 int cxListReserve(CxList *list, size_t capacity) {
1117 if (list->cl->change_capacity == NULL) { 955 if (list->cl->change_capacity == NULL) {
1118 return 0; 956 return 0;

Mercurial Repository: toolkit

mercurial