Mercurial > hg > dav / file comparison

comparison: ucx/list.c

ucx/list.c

branch
dav-2
changeset 891
4d58cbcc9efa
parent 889
42cdbf9bbd49
equal deleted inserted replaced
890:e77ccf1c4bb3 891:4d58cbcc9efa
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 struct cx_iterator_s cx_pl_iterator(
189 const struct cx_list_s *list,
190 size_t index,
191 bool backwards
192 ) {
193 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
194 iter.base.current_impl = iter.base.current;
195 iter.base.current = cx_pl_iter_current;
196 return iter;
197 }
198
199 static cx_list_class cx_pointer_list_class = {
200 cx_pl_destructor,
201 cx_pl_insert_element,
202 cx_pl_insert_array,
203 cx_pl_insert_sorted,
204 cx_pl_insert_unique,
205 cx_pl_insert_iter,
206 cx_pl_remove,
207 cx_pl_clear,
208 cx_pl_swap,
209 cx_pl_at,
210 cx_pl_find_remove,
211 cx_pl_sort,
212 cx_pl_compare,
213 cx_pl_reverse,
214 cx_pl_iterator,
215 };
216 // </editor-fold>
217 63
218 // <editor-fold desc="empty list implementation"> 64 // <editor-fold desc="empty list implementation">
219 65
220 static void cx_emptyl_noop(cx_attr_unused CxList *list) { 66 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
221 // this is a noop, but MUST be implemented 67 // this is a noop, but MUST be implemented
265 cx_emptyl_at, 111 cx_emptyl_at,
266 cx_emptyl_find_remove, 112 cx_emptyl_find_remove,
267 cx_emptyl_noop, 113 cx_emptyl_noop,
268 NULL, 114 NULL,
269 cx_emptyl_noop, 115 cx_emptyl_noop,
116 NULL,
270 cx_emptyl_iterator, 117 cx_emptyl_iterator,
271 }; 118 };
272 119
273 CxList cx_empty_list = { 120 CxList cx_empty_list = {
274 { 121 {
275 NULL, 122 NULL,
276 NULL,
277 0, 123 0,
278 0, 124 0,
125 NULL,
126 NULL,
127 NULL,
279 NULL, 128 NULL,
280 NULL, 129 NULL,
281 NULL, 130 NULL,
282 false, 131 false,
283 true, 132 true,
284 }, 133 },
285 &cx_empty_list_class, 134 &cx_empty_list_class,
286 NULL
287 }; 135 };
288 136
289 CxList *const cxEmptyList = &cx_empty_list; 137 CxList *const cxEmptyList = &cx_empty_list;
290 138
291 // </editor-fold> 139 // </editor-fold>
292
293 #define invoke_list_func(name, list, ...) \
294 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
295 (list, __VA_ARGS__)
296 140
297 size_t cx_list_default_insert_array( 141 size_t cx_list_default_insert_array(
298 struct cx_list_s *list, 142 struct cx_list_s *list,
299 size_t index, 143 size_t index,
300 const void *data, 144 const void *data,
301 size_t n 145 size_t n
302 ) { 146 ) {
303 const char *src = data; 147 const char *src = data;
304 size_t i = 0; 148 size_t i = 0;
305 for (; i < n; i++) { 149 for (; i < n; i++) {
306 if (NULL == invoke_list_func( 150 if (NULL == list->cl->insert_element(list, index + i, src)
307 insert_element, list, index + i, src)
308 ) { 151 ) {
309 return i; // LCOV_EXCL_LINE 152 return i; // LCOV_EXCL_LINE
310 } 153 }
311 if (src != NULL) { 154 if (src != NULL) {
312 src += list->collection.elem_size; 155 src += list->collection.elem_size;
323 ) { 166 ) {
324 // corner case 167 // corner case
325 if (n == 0) return 0; 168 if (n == 0) return 0;
326 169
327 size_t elem_size = list->collection.elem_size; 170 size_t elem_size = list->collection.elem_size;
328 cx_compare_func cmp = list->collection.cmpfunc;
329 const char *src = sorted_data; 171 const char *src = sorted_data;
330 172
331 // track indices and number of inserted items 173 // track indices and number of inserted items
332 size_t di = 0, si = 0, processed = 0; 174 size_t di = 0, si = 0, processed = 0;
333 175
334 // search the list for insertion points 176 // search the list for insertion points
335 while (di < list->collection.size) { 177 while (di < list->collection.size) {
336 const void *list_elm = invoke_list_func(at, list, di); 178 const void *list_elm = list->cl->at(list, di);
337 179
338 // compare the current list element with the first source element 180 // compare the current list element with the first source element
339 // if less, skip the list elements 181 // if less, skip the list elements
340 // if equal, skip the list elements and optionally the source elements 182 // if equal, skip the list elements and optionally the source elements
341 { 183 {
342 int d = cmp(list_elm, src); 184 int d = cx_list_compare_wrapper(list_elm, src, list);
343 if (d <= 0) { 185 if (d <= 0) {
344 if (!allow_duplicates && d == 0) { 186 if (!allow_duplicates && d == 0) {
345 src += elem_size; 187 src += elem_size;
346 si++; 188 si++;
347 processed++; // we also count duplicates for the return value 189 processed++; // we also count duplicates for the return value
348 while (si < n && cmp(list_elm, src) == 0) { 190 while (si < n && cx_list_compare_wrapper(list_elm, src, list) == 0) {
349 src += elem_size; 191 src += elem_size;
350 si++; 192 si++;
351 processed++; 193 processed++;
352 } 194 }
353 if (processed == n) { 195 if (processed == n) {
363 size_t ins = 1, skip = 0; 205 size_t ins = 1, skip = 0;
364 const char *next = src; 206 const char *next = src;
365 while (++si < n) { 207 while (++si < n) {
366 if (!allow_duplicates) { 208 if (!allow_duplicates) {
367 // skip duplicates within the source 209 // skip duplicates within the source
368 if (cmp(next, next + elem_size) == 0) { 210 if (cx_list_compare_wrapper(next, next + elem_size, list) == 0) {
369 next += elem_size; 211 next += elem_size;
370 skip++; 212 skip++;
371 continue; 213 continue;
372 } else { 214 } else {
373 if (skip > 0) { 215 if (skip > 0) {
377 } 219 }
378 } 220 }
379 } 221 }
380 next += elem_size; 222 next += elem_size;
381 // once we become larger than the list elem, break 223 // once we become larger than the list elem, break
382 if (cmp(list_elm, next) <= 0) { 224 if (cx_list_compare_wrapper(list_elm, next, list) <= 0) {
383 break; 225 break;
384 } 226 }
385 // otherwise, we can insert one more 227 // otherwise, we can insert one more
386 ins++; 228 ins++;
387 } 229 }
388 230
389 // insert the elements at location si 231 // insert the elements at location si
390 if (ins == 1) { 232 if (ins == 1) {
391 if (NULL == invoke_list_func(insert_element, list, di, src)) { 233 if (NULL == list->cl->insert_element(list, di, src)) {
392 return processed; // LCOV_EXCL_LINE 234 return processed; // LCOV_EXCL_LINE
393 } 235 }
394 } else { 236 } else {
395 size_t r = invoke_list_func(insert_array, list, di, src, ins); 237 size_t r = list->cl->insert_array(list, di, src, ins);
396 if (r < ins) { 238 if (r < ins) {
397 return processed + r; // LCOV_EXCL_LINE 239 return processed + r; // LCOV_EXCL_LINE
398 } 240 }
399 } 241 }
400 processed += ins + skip; 242 processed += ins + skip;
408 } 250 }
409 251
410 // insert remaining items 252 // insert remaining items
411 if (si < n) { 253 if (si < n) {
412 if (allow_duplicates) { 254 if (allow_duplicates) {
413 processed += invoke_list_func(insert_array, list, di, src, n - si); 255 processed += list->cl->insert_array(list, di, src, n - si);
414 } else { 256 } else {
415 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);
416 for (; si < n; si++) { 258 for (; si < n; si++) {
417 // skip duplicates within the source 259 // skip duplicates within the source
418 if (last == NULL || cmp(last, src) != 0) { 260 if (last == NULL || cx_list_compare_wrapper(last, src, list) != 0) {
419 if (NULL == invoke_list_func(insert_element, list, di, src)) { 261 if (NULL == list->cl->insert_element(list, di, src)) {
420 return processed; // LCOV_EXCL_LINE 262 return processed; // LCOV_EXCL_LINE
421 } 263 }
422 last = src; 264 last = src;
423 di++; 265 di++;
424 } 266 }
454 if (tmp == NULL) abort(); // LCOV_EXCL_LINE 296 if (tmp == NULL) abort(); // LCOV_EXCL_LINE
455 297
456 // copy elements from source array 298 // copy elements from source array
457 char *loc = tmp; 299 char *loc = tmp;
458 for (size_t i = 0; i < list_size; i++) { 300 for (size_t i = 0; i < list_size; i++) {
459 void *src = invoke_list_func(at, list, i); 301 void *src = list->cl->at(list, i);
460 memcpy(loc, src, elem_size); 302 memcpy(loc, src, elem_size);
461 loc += elem_size; 303 loc += elem_size;
462 } 304 }
463 305
464 // qsort 306 // qsort
465 qsort(tmp, list_size, elem_size, 307 cx_array_qsort_c(tmp, list_size, elem_size, cx_list_compare_wrapper, list);
466 list->collection.cmpfunc);
467 308
468 // copy elements back 309 // copy elements back
469 loc = tmp; 310 loc = tmp;
470 for (size_t i = 0; i < list_size; i++) { 311 for (size_t i = 0; i < list_size; i++) {
471 void *dest = invoke_list_func(at, list, i); 312 void *dest = list->cl->at(list, i);
472 memcpy(dest, loc, elem_size); 313 memcpy(dest, loc, elem_size);
473 loc += elem_size; 314 loc += elem_size;
474 } 315 }
475 316
476 cxFreeDefault(tmp); 317 cxFreeDefault(tmp);
484 size_t elem_size = list->collection.elem_size; 325 size_t elem_size = list->collection.elem_size;
485 326
486 void *tmp = cxMallocDefault(elem_size); 327 void *tmp = cxMallocDefault(elem_size);
487 if (tmp == NULL) return 1; // LCOV_EXCL_LINE 328 if (tmp == NULL) return 1; // LCOV_EXCL_LINE
488 329
489 void *ip = invoke_list_func(at, list, i); 330 void *ip = list->cl->at(list, i);
490 void *jp = invoke_list_func(at, list, j); 331 void *jp = list->cl->at(list, j);
491 332
492 memcpy(tmp, ip, elem_size); 333 memcpy(tmp, ip, elem_size);
493 memcpy(ip, jp, elem_size); 334 memcpy(ip, jp, elem_size);
494 memcpy(jp, tmp, elem_size); 335 memcpy(jp, tmp, elem_size);
495 336
500 341
501 void cx_list_init( 342 void cx_list_init(
502 struct cx_list_s *list, 343 struct cx_list_s *list,
503 struct cx_list_class_s *cl, 344 struct cx_list_class_s *cl,
504 const struct cx_allocator_s *allocator, 345 const struct cx_allocator_s *allocator,
505 cx_compare_func comparator,
506 size_t elem_size 346 size_t elem_size
507 ) { 347 ) {
508 list->cl = cl; 348 list->cl = cl;
509 list->collection.allocator = allocator; 349 list->collection.allocator = allocator;
510 list->collection.cmpfunc = comparator; 350 list->collection.size = 0;
351 list->collection.sorted = false; // should be set by the implementation
511 if (elem_size > 0) { 352 if (elem_size > 0) {
512 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;
513 } else { 358 } else {
514 list->collection.elem_size = sizeof(void *); 359 list->collection.elem_size = sizeof(void *);
515 if (list->collection.cmpfunc == NULL) { 360 list->collection.simple_cmp = cx_cmp_ptr;
516 list->collection.cmpfunc = cx_cmp_ptr; 361 list->collection.advanced_cmp = NULL;
517 } 362 list->collection.cmp_data = NULL;
518 list->collection.store_pointer = true; 363 list->collection.store_pointer = true;
519 list->climpl = list->cl;
520 list->cl = &cx_pointer_list_class;
521 } 364 }
522 } 365 }
523 366
524 int cxListCompare( 367 int cxListCompare(
525 const CxList *list, 368 const CxList *list,
526 const CxList *other 369 const CxList *other
527 ) { 370 ) {
371 // check if we cannot use the list internal function
528 bool cannot_optimize = false; 372 bool cannot_optimize = false;
529 373
530 // if one is storing pointers but the other is not 374 // if one is storing pointers but the other is not
531 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; 375 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
532 376
533 // if one class is wrapped but the other is not 377 // check if the lists are incompatible or this list does not implement compare
534 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); 378 cx_compare_func list_cmp = (cx_compare_func) list->cl->compare;
535 379 cx_compare_func other_cmp = (cx_compare_func) other->cl->compare;
536 // if the compare functions do not match or both are NULL 380 cannot_optimize |= list_cmp != other_cmp;
537 if (!cannot_optimize) { 381 cannot_optimize |= list_cmp == NULL;
538 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
539 list->climpl->compare : list->cl->compare);
540 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
541 other->climpl->compare : other->cl->compare);
542 cannot_optimize |= list_cmp != other_cmp;
543 cannot_optimize |= list_cmp == NULL;
544 }
545 382
546 if (cannot_optimize) { 383 if (cannot_optimize) {
547 // lists are definitely different - cannot use internal compare function 384 // lists are definitely different - cannot use internal compare function
548 if (list->collection.size == other->collection.size) { 385 if (list->collection.size == other->collection.size) {
549 CxIterator left = list->cl->iterator(list, 0, false); 386 CxIterator left = cxListIterator(list);
550 CxIterator right = other->cl->iterator(other, 0, false); 387 CxIterator right = cxListIterator(other);
551 for (size_t i = 0; i < list->collection.size; i++) { 388 for (size_t i = 0; i < list->collection.size; i++) {
552 void *leftValue = cxIteratorCurrent(left); 389 void *leftValue = cxIteratorCurrent(left);
553 void *rightValue = cxIteratorCurrent(right); 390 void *rightValue = cxIteratorCurrent(right);
554 int d = list->collection.cmpfunc(leftValue, rightValue); 391 // values are already unwrapped, invoke immediately
392 int d = cx_invoke_compare_func(list, leftValue, rightValue);
555 if (d != 0) { 393 if (d != 0) {
556 return d; 394 return d;
557 } 395 }
558 cxIteratorNext(left); 396 cxIteratorNext(left);
559 cxIteratorNext(right); 397 cxIteratorNext(right);
572 return list->collection.size; 410 return list->collection.size;
573 } 411 }
574 412
575 int cxListAdd(CxList *list, const void *elem) { 413 int cxListAdd(CxList *list, const void *elem) {
576 list->collection.sorted = false; 414 list->collection.sorted = false;
577 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;
578 } 416 }
579 417
580 size_t cxListAddArray(CxList *list, const void *array, size_t n) { 418 size_t cxListAddArray(CxList *list, const void *array, size_t n) {
581 list->collection.sorted = false; 419 list->collection.sorted = false;
582 return list->cl->insert_array(list, list->collection.size, array, n); 420 return list->cl->insert_array(list, list->collection.size, array, n);
583 } 421 }
584 422
585 int cxListInsert(CxList *list, size_t index, const void *elem) { 423 int cxListInsert(CxList *list, size_t index, const void *elem) {
586 list->collection.sorted = false; 424 list->collection.sorted = false;
587 return list->cl->insert_element(list, index, elem) == NULL; 425 return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL;
588 } 426 }
589 427
590 void *cxListEmplaceAt(CxList *list, size_t index) { 428 void *cxListEmplaceAt(CxList *list, size_t index) {
591 list->collection.sorted = false; 429 list->collection.sorted = false;
592 return list->cl->insert_element(list, index, NULL); 430 return list->cl->insert_element(list, index, NULL);
609 // tweak the fields of this iterator 447 // tweak the fields of this iterator
610 iter.elem_count = c; 448 iter.elem_count = c;
611 iter.index = 0; 449 iter.index = 0;
612 // replace the valid function to abort iteration when c is reached 450 // replace the valid function to abort iteration when c is reached
613 iter.base.valid = cx_list_emplace_iterator_valid; 451 iter.base.valid = cx_list_emplace_iterator_valid;
614 // if we are storing pointers, we want to return the pure pointers.
615 // therefore, we must unwrap the "current" method
616 if (list->collection.store_pointer) {
617 iter.base.current = iter.base.current_impl;
618 }
619 return iter; 452 return iter;
620 } 453 }
621 454
622 CxIterator cxListEmplaceArray(CxList *list, size_t n) { 455 CxIterator cxListEmplaceArray(CxList *list, size_t n) {
623 return cxListEmplaceArrayAt(list, list->collection.size, n); 456 return cxListEmplaceArrayAt(list, list->collection.size, n);
624 } 457 }
625 458
626 int cxListInsertSorted(CxList *list, const void *elem) { 459 int cxListInsertSorted(CxList *list, const void *elem) {
627 assert(cxCollectionSorted(list)); 460 assert(cxCollectionSorted(list));
628 list->collection.sorted = true; 461 list->collection.sorted = true;
629 const void *data = list->collection.store_pointer ? &elem : elem; 462 return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0;
630 return list->cl->insert_sorted(list, data, 1) == 0;
631 } 463 }
632 464
633 int cxListInsertUnique(CxList *list, const void *elem) { 465 int cxListInsertUnique(CxList *list, const void *elem) {
634 if (cxCollectionSorted(list)) { 466 if (cxCollectionSorted(list)) {
635 list->collection.sorted = true; 467 list->collection.sorted = true;
636 const void *data = list->collection.store_pointer ? &elem : elem; 468 return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0;
637 return list->cl->insert_unique(list, data, 1) == 0;
638 } else { 469 } else {
639 if (cxListContains(list, elem)) { 470 if (cxListContains(list, elem)) {
640 return 0; 471 return 0;
641 } else { 472 } else {
642 return cxListAdd(list, elem); 473 return cxListAdd(list, elem);
661 return list->cl->insert_unique(list, array, n); 492 return list->cl->insert_unique(list, array, n);
662 } else { 493 } else {
663 const char *source = array; 494 const char *source = array;
664 for (size_t i = 0 ; i < n; i++) { 495 for (size_t i = 0 ; i < n; i++) {
665 // note: this also checks elements added in a previous iteration 496 // note: this also checks elements added in a previous iteration
666 const void *data = list->collection.store_pointer ? 497 const void *data = cx_deref(list, source);
667 *((const void**)source) : source;
668 if (!cxListContains(list, data)) { 498 if (!cxListContains(list, data)) {
669 if (cxListAdd(list, data)) { 499 if (cxListAdd(list, data)) {
670 return i; // LCOV_EXCL_LINE 500 return i; // LCOV_EXCL_LINE
671 } 501 }
672 } 502 }
675 return n; 505 return n;
676 } 506 }
677 } 507 }
678 508
679 int cxListInsertAfter(CxIterator *iter, const void *elem) { 509 int cxListInsertAfter(CxIterator *iter, const void *elem) {
680 CxList* list = (CxList*)iter->src_handle; 510 CxList* list = iter->src_handle;
681 list->collection.sorted = false; 511 list->collection.sorted = false;
682 return list->cl->insert_iter(iter, elem, 0); 512 return list->cl->insert_iter(iter, cx_ref(list, elem), 0);
683 } 513 }
684 514
685 int cxListInsertBefore(CxIterator *iter, const void *elem) { 515 int cxListInsertBefore(CxIterator *iter, const void *elem) {
686 CxList* list = (CxList*)iter->src_handle; 516 CxList* list = iter->src_handle;
687 list->collection.sorted = false; 517 list->collection.sorted = false;
688 return list->cl->insert_iter(iter, elem, 1); 518 return list->cl->insert_iter(iter, cx_ref(list, elem), 1);
689 } 519 }
690 520
691 int cxListRemove(CxList *list, size_t index) { 521 int cxListRemove(CxList *list, size_t index) {
692 return list->cl->remove(list, index, 1, NULL) == 0; 522 return list->cl->remove(list, index, 1, NULL) == 0;
693 } 523 }
722 list->collection.sorted = false; 552 list->collection.sorted = false;
723 return list->cl->swap(list, i, j); 553 return list->cl->swap(list, i, j);
724 } 554 }
725 555
726 void *cxListAt(const CxList *list, size_t index) { 556 void *cxListAt(const CxList *list, size_t index) {
727 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);
728 } 560 }
729 561
730 void *cxListFirst(const CxList *list) { 562 void *cxListFirst(const CxList *list) {
731 return list->cl->at(list, 0); 563 return cxListAt(list, 0);
732 } 564 }
733 565
734 void *cxListLast(const CxList *list) { 566 void *cxListLast(const CxList *list) {
735 return list->cl->at(list, list->collection.size - 1); 567 return cxListAt(list, list->collection.size - 1);
736 } 568 }
737 569
738 int cxListSet(CxList *list, size_t index, const void *elem) { 570 int cxListSet(CxList *list, size_t index, const void *elem) {
739 if (index >= list->collection.size) { 571 if (index >= list->collection.size) {
740 return 1; 572 return 1;
741 } 573 }
742 574
743 if (list->collection.store_pointer) { 575 if (list->collection.store_pointer) {
744 // For pointer collections, always use climpl 576 void **target = list->cl->at(list, index);
745 void **target = list->climpl->at(list, index);
746 *target = (void *)elem; 577 *target = (void *)elem;
747 } else { 578 } else {
748 void *target = list->cl->at(list, index); 579 void *target = list->cl->at(list, index);
749 memcpy(target, elem, list->collection.elem_size); 580 memcpy(target, elem, list->collection.elem_size);
750 } 581 }
751 582
752 return 0; 583 return 0;
753 } 584 }
754 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
755 CxIterator cxListIteratorAt(const CxList *list, size_t index) { 602 CxIterator cxListIteratorAt(const CxList *list, size_t index) {
756 if (list == NULL) list = cxEmptyList; 603 if (list == NULL) list = cxEmptyList;
757 return list->cl->iterator(list, index, false); 604 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false));
758 } 605 }
759 606
760 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) { 607 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) {
761 if (list == NULL) list = cxEmptyList; 608 if (list == NULL) list = cxEmptyList;
762 return list->cl->iterator(list, index, true); 609 return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true));
763 } 610 }
764 611
765 CxIterator cxListIterator(const CxList *list) { 612 CxIterator cxListIterator(const CxList *list) {
766 if (list == NULL) list = cxEmptyList; 613 if (list == NULL) list = cxEmptyList;
767 return list->cl->iterator(list, 0, false); 614 return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false));
768 } 615 }
769 616
770 CxIterator cxListBackwardsIterator(const CxList *list) { 617 CxIterator cxListBackwardsIterator(const CxList *list) {
771 if (list == NULL) list = cxEmptyList; 618 if (list == NULL) list = cxEmptyList;
772 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));
773 } 620 }
774 621
775 size_t cxListFind(const CxList *list, const void *elem) { 622 size_t cxListFind(const CxList *list, const void *elem) {
776 return list->cl->find_remove((CxList*)list, elem, false); 623 return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false);
777 } 624 }
778 625
779 bool cxListContains(const CxList* list, const void* elem) { 626 bool cxListContains(const CxList* list, const void* elem) {
780 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;
781 } 628 }
782 629
783 bool cxListIndexValid(const CxList *list, size_t index) { 630 bool cxListIndexValid(const CxList *list, size_t index) {
784 return index < list->collection.size; 631 return index < list->collection.size;
785 } 632 }
786 633
787 size_t cxListFindRemove(CxList *list, const void *elem) { 634 size_t cxListFindRemove(CxList *list, const void *elem) {
788 return list->cl->find_remove(list, elem, true); 635 return list->cl->find_remove(list, cx_ref(list, elem), true);
789 } 636 }
790 637
791 void cxListSort(CxList *list) { 638 void cxListSort(CxList *list) {
792 if (list->collection.sorted) return; 639 if (list->collection.sorted) return;
793 list->cl->sort(list); 640 list->cl->sort(list);
816 cxListRemoveArray(list,list->collection.size - n, n); 663 cxListRemoveArray(list,list->collection.size - n, n);
817 } 664 }
818 list->collection.simple_destructor = destr_bak; 665 list->collection.simple_destructor = destr_bak;
819 list->collection.advanced_destructor = destr2_bak; 666 list->collection.advanced_destructor = destr2_bak;
820 } 667 }
668
669 static void* cx_list_shallow_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) {
670 size_t elem_size = *(size_t*)data;
671 if (dst == NULL) dst = cxMalloc(al, elem_size);
672 if (dst != NULL) memcpy(dst, src, elem_size);
673 return dst;
674 }
675
676 #define use_shallow_clone_func(list) cx_list_shallow_clone_func, NULL, (void*)&((list)->collection.elem_size)
821 677
822 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,
823 const CxAllocator *clone_allocator, void *data) { 679 const CxAllocator *clone_allocator, void *data) {
824 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; 680 if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
825 681
856 cx_list_pop_uninitialized_elements(dst, 712 cx_list_pop_uninitialized_elements(dst,
857 dst->collection.size - cloned - orig_size); 713 dst->collection.size - cloned - orig_size);
858 return 1; 714 return 1;
859 } 715 }
860 716
717 // set the sorted flag when we know it's sorted
718 if (orig_size == 0 && src->collection.sorted) {
719 dst->collection.sorted = true;
720 }
721
861 return 0; 722 return 0;
862 } 723 }
863 724
864 int cxListDifference(CxList *dst, 725 int cxListDifference(CxList *dst,
865 const CxList *minuend, const CxList *subtrahend, 726 const CxList *minuend, const CxList *subtrahend,
876 void *min_elem = cxIteratorCurrent(min_iter); 737 void *min_elem = cxIteratorCurrent(min_iter);
877 void *sub_elem; 738 void *sub_elem;
878 int d; 739 int d;
879 if (cxIteratorValid(sub_iter)) { 740 if (cxIteratorValid(sub_iter)) {
880 sub_elem = cxIteratorCurrent(sub_iter); 741 sub_elem = cxIteratorCurrent(sub_iter);
881 cx_compare_func cmp = subtrahend->collection.cmpfunc; 742 d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend);
882 d = cmp(sub_elem, min_elem);
883 } else { 743 } else {
884 // no more elements in the subtrahend, 744 // no more elements in the subtrahend,
885 // 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
886 d = 1; 746 d = 1;
887 } 747 }
945 CxIterator src_iter = cxListIterator(src); 805 CxIterator src_iter = cxListIterator(src);
946 CxIterator other_iter = cxListIterator(other); 806 CxIterator other_iter = cxListIterator(other);
947 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { 807 while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) {
948 void *src_elem = cxIteratorCurrent(src_iter); 808 void *src_elem = cxIteratorCurrent(src_iter);
949 void *other_elem = cxIteratorCurrent(other_iter); 809 void *other_elem = cxIteratorCurrent(other_iter);
950 int d = src->collection.cmpfunc(src_elem, other_elem); 810 int d = cx_list_compare_wrapper(src_elem, other_elem, src);
951 if (d == 0) { 811 if (d == 0) {
952 // is contained, clone it 812 // is contained, clone it
953 void **dst_mem = cxListEmplace(dst); 813 void **dst_mem = cxListEmplace(dst);
954 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; 814 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
955 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data); 815 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
1004 bool dst_was_empty = cxCollectionSize(dst) == 0; 864 bool dst_was_empty = cxCollectionSize(dst) == 0;
1005 865
1006 CxIterator src_iter = cxListIterator(src); 866 CxIterator src_iter = cxListIterator(src);
1007 CxIterator other_iter = cxListIterator(other); 867 CxIterator other_iter = cxListIterator(other);
1008 while (cxIteratorValid(src_iter) || cxIteratorValid(other_iter)) { 868 while (cxIteratorValid(src_iter) || cxIteratorValid(other_iter)) {
1009 void *src_elem, *other_elem; 869 void *src_elem = NULL, *other_elem = NULL;
1010 int d; 870 int d;
1011 if (!cxIteratorValid(src_iter)) { 871 if (!cxIteratorValid(src_iter)) {
1012 other_elem = cxIteratorCurrent(other_iter); 872 other_elem = cxIteratorCurrent(other_iter);
1013 d = 1; 873 d = 1;
1014 } else if (!cxIteratorValid(other_iter)) { 874 } else if (!cxIteratorValid(other_iter)) {
1015 src_elem = cxIteratorCurrent(src_iter); 875 src_elem = cxIteratorCurrent(src_iter);
1016 d = -1; 876 d = -1;
1017 } else { 877 } else {
1018 src_elem = cxIteratorCurrent(src_iter); 878 src_elem = cxIteratorCurrent(src_iter);
1019 other_elem = cxIteratorCurrent(other_iter); 879 other_elem = cxIteratorCurrent(other_iter);
1020 d = src->collection.cmpfunc(src_elem, other_elem); 880 d = cx_list_compare_wrapper(src_elem, other_elem, src);
1021 } 881 }
1022 if (d <= 0) { 882 void *clone_from;
1023 // source element is smaller or equal, clone it 883 if (d < 0) {
1024 void **dst_mem = cxListEmplace(dst); 884 // source element is smaller clone it
1025 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; 885 clone_from = src_elem;
1026 void* dst_ptr = clone_func(target, src_elem, clone_allocator, data);
1027 if (dst_ptr == NULL) {
1028 cx_list_pop_uninitialized_elements(dst, 1);
1029 return 1;
1030 }
1031 if (cxCollectionStoresPointers(dst)) {
1032 *dst_mem = dst_ptr;
1033 }
1034 cxIteratorNext(src_iter); 886 cxIteratorNext(src_iter);
1035 // if the other element was equal, skip it 887 } else if (d == 0) {
1036 if (d == 0) { 888 // both elements are equal, clone from the source, skip other
1037 cxIteratorNext(other_iter); 889 clone_from = src_elem;
1038 } 890 cxIteratorNext(src_iter);
891 cxIteratorNext(other_iter);
1039 } else { 892 } else {
1040 // the other element is smaller, clone it 893 // the other element is smaller, clone it
1041 void **dst_mem = cxListEmplace(dst); 894 clone_from = other_elem;
1042 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
1043 void* dst_ptr = clone_func(target, other_elem, clone_allocator, data);
1044 if (dst_ptr == NULL) {
1045 cx_list_pop_uninitialized_elements(dst, 1);
1046 return 1;
1047 }
1048 if (cxCollectionStoresPointers(dst)) {
1049 *dst_mem = dst_ptr;
1050 }
1051 cxIteratorNext(other_iter); 895 cxIteratorNext(other_iter);
896 }
897 void **dst_mem = cxListEmplace(dst);
898 void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem;
899 void* dst_ptr = clone_func(target, clone_from, clone_allocator, data);
900 if (dst_ptr == NULL) {
901 cx_list_pop_uninitialized_elements(dst, 1);
902 return 1;
903 }
904 if (cxCollectionStoresPointers(dst)) {
905 *dst_mem = dst_ptr;
1052 } 906 }
1053 } 907 }
1054 908
1055 // if dst was empty, it is now guaranteed to be sorted 909 // if dst was empty, it is now guaranteed to be sorted
1056 dst->collection.sorted = dst_was_empty; 910 dst->collection.sorted = dst_was_empty;
1076 } 930 }
1077 } 931 }
1078 932
1079 return 0; 933 return 0;
1080 } 934 }
935
936 int cxListCloneShallow(CxList *dst, const CxList *src) {
937 return cxListClone(dst, src, use_shallow_clone_func(src));
938 }
939
940 int cxListDifferenceShallow(CxList *dst, const CxList *minuend, const CxList *subtrahend) {
941 return cxListDifference(dst, minuend, subtrahend, use_shallow_clone_func(minuend));
942 }
943
944 int cxListIntersectionShallow(CxList *dst, const CxList *src, const CxList *other) {
945 return cxListIntersection(dst, src, other, use_shallow_clone_func(src));
946 }
947
948 int cxListUnionShallow(CxList *dst, const CxList *src, const CxList *other) {
949 return cxListUnion(dst, src, other, use_shallow_clone_func(src));
950 }
951
952 int cxListReserve(CxList *list, size_t capacity) {
953 if (list->cl->change_capacity == NULL) {
954 return 0;
955 }
956 if (capacity <= cxCollectionSize(list)) {
957 return 0;
958 }
959 return list->cl->change_capacity(list, capacity);
960 }
961
962 int cxListShrink(CxList *list) {
963 if (list->cl->change_capacity == NULL) {
964 return 0;
965 }
966 return list->cl->change_capacity(list, cxCollectionSize(list));
967 }

Mercurial Repository: dav

mercurial