Mercurial > hg > dbutils / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c

changeset 31
287484519844
parent 23
b26390e77237
equal deleted inserted replaced
30:d33eaaec15da 31:287484519844
63 i < index ? i++ : i--; 63 i < index ? i++ : i--;
64 } 64 }
65 return (void *) cur; 65 return (void *) cur;
66 } 66 }
67 67
68 void *cx_linked_list_find_c(
69 const void *start,
70 ptrdiff_t loc_advance,
71 ptrdiff_t loc_data,
72 const void *elem,
73 size_t *found_index,
74 cx_compare_func2 cmp_func,
75 void *context
76 ) {
77 assert(start != NULL);
78 assert(loc_advance >= 0);
79 assert(loc_data >= 0);
80 assert(cmp_func);
81
82 void *node = (void*) start;
83 size_t index = 0;
84 do {
85 void *current = ll_data(node);
86 if (cmp_func(current, elem, context) == 0) {
87 if (found_index != NULL) {
88 *found_index = index;
89 }
90 return node;
91 }
92 node = ll_advance(node);
93 index++;
94 } while (node != NULL);
95 return NULL;
96 }
97
68 void *cx_linked_list_find( 98 void *cx_linked_list_find(
69 const void *start, 99 const void *start,
70 ptrdiff_t loc_advance, 100 ptrdiff_t loc_advance,
71 ptrdiff_t loc_data, 101 ptrdiff_t loc_data,
72 cx_compare_func cmp_func,
73 const void *elem, 102 const void *elem,
74 size_t *found_index 103 size_t *found_index,
75 ) { 104 cx_compare_func cmp_func
76 assert(start != NULL); 105 ) {
77 assert(loc_advance >= 0); 106 cx_compare_func_wrapper wrapper = {cmp_func};
78 assert(loc_data >= 0); 107 return cx_linked_list_find_c(start, loc_advance, loc_data,
79 assert(cmp_func); 108 elem, found_index, cx_ccmp_wrap, &wrapper);
80
81 void *node = (void*) start;
82 size_t index = 0;
83 do {
84 void *current = ll_data(node);
85 if (cmp_func(current, elem) == 0) {
86 if (found_index != NULL) {
87 *found_index = index;
88 }
89 return node;
90 }
91 node = ll_advance(node);
92 index++;
93 } while (node != NULL);
94 return NULL;
95 } 109 }
96 110
97 void *cx_linked_list_first( 111 void *cx_linked_list_first(
98 const void *node, 112 const void *node,
99 ptrdiff_t loc_prev 113 ptrdiff_t loc_prev
238 } else { 252 } else {
239 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); 253 cx_linked_list_link(insert_end, successor, loc_prev, loc_next);
240 } 254 }
241 } 255 }
242 256
243 void cx_linked_list_insert_sorted(
244 void **begin,
245 void **end,
246 ptrdiff_t loc_prev,
247 ptrdiff_t loc_next,
248 void *new_node,
249 cx_compare_func cmp_func
250 ) {
251 assert(ll_next(new_node) == NULL);
252 cx_linked_list_insert_sorted_chain(
253 begin, end, loc_prev, loc_next, new_node, cmp_func);
254 }
255
256 static void *cx_linked_list_insert_sorted_chain_impl( 257 static void *cx_linked_list_insert_sorted_chain_impl(
257 void **begin, 258 void **begin,
258 void **end, 259 void **end,
259 ptrdiff_t loc_prev, 260 ptrdiff_t loc_prev,
260 ptrdiff_t loc_next, 261 ptrdiff_t loc_next,
261 void *insert_begin, 262 void *insert_begin,
262 cx_compare_func cmp_func, 263 cx_compare_func2 cmp_func,
264 void *context,
263 bool allow_duplicates 265 bool allow_duplicates
264 ) { 266 ) {
265 assert(begin != NULL); 267 assert(begin != NULL);
266 assert(loc_next >= 0); 268 assert(loc_next >= 0);
267 assert(insert_begin != NULL); 269 assert(insert_begin != NULL);
274 void *dup_begin = NULL; 276 void *dup_begin = NULL;
275 void *dup_end = NULL; 277 void *dup_end = NULL;
276 278
277 // determine the new start 279 // determine the new start
278 { 280 {
279 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); 281 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument, context);
280 if (d <= 0) { 282 if (d <= 0) {
281 // the new chain starts with the original chain 283 // the new chain starts with the original chain
282 new_begin = new_end = source_original; 284 new_begin = new_end = source_original;
283 source_original = ll_next(source_original); 285 source_original = ll_next(source_original);
284 if (d == 0) { 286 if (d == 0) {
300 } 302 }
301 } 303 }
302 304
303 // now successively compare the elements and add them to the correct chains 305 // now successively compare the elements and add them to the correct chains
304 while (source_original != NULL && source_argument != NULL) { 306 while (source_original != NULL && source_argument != NULL) {
305 int d = cmp_func(source_original, source_argument); 307 int d = cmp_func(source_original, source_argument, context);
306 if (d <= 0) { 308 if (d <= 0) {
307 // the original is not larger, add it to the chain 309 // the original is not larger, add it to the chain
308 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); 310 cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
309 new_end = source_original; 311 new_end = source_original;
310 source_original = ll_next(source_original); 312 source_original = ll_next(source_original);
325 source_argument = ll_next(source_argument); 327 source_argument = ll_next(source_argument);
326 } 328 }
327 } else { 329 } else {
328 // the original is larger, append the source argument to the chain 330 // the original is larger, append the source argument to the chain
329 // check if we must discard the source argument as duplicate 331 // check if we must discard the source argument as duplicate
330 if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { 332 if (!allow_duplicates && cmp_func(new_end, source_argument, context) == 0) {
331 if (dup_end == NULL) { 333 if (dup_end == NULL) {
332 dup_begin = dup_end = source_argument; 334 dup_begin = dup_end = source_argument;
333 } else { 335 } else {
334 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 336 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
335 dup_end = source_argument; 337 dup_end = source_argument;
354 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 356 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
355 new_end = cx_linked_list_last(source_argument, loc_next); 357 new_end = cx_linked_list_last(source_argument, loc_next);
356 } else { 358 } else {
357 // otherwise we must check one-by-one 359 // otherwise we must check one-by-one
358 while (source_argument != NULL) { 360 while (source_argument != NULL) {
359 if (cmp_func(new_end, source_argument) == 0) { 361 if (cmp_func(new_end, source_argument, context) == 0) {
360 if (dup_end == NULL) { 362 if (dup_end == NULL) {
361 dup_begin = dup_end = source_argument; 363 dup_begin = dup_end = source_argument;
362 } else { 364 } else {
363 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 365 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
364 dup_end = source_argument; 366 dup_end = source_argument;
392 *end = new_end; 394 *end = new_end;
393 } 395 }
394 return dup_begin; 396 return dup_begin;
395 } 397 }
396 398
399 void cx_linked_list_insert_sorted(
400 void **begin,
401 void **end,
402 ptrdiff_t loc_prev,
403 ptrdiff_t loc_next,
404 void *new_node,
405 cx_compare_func cmp_func
406 ) {
407 assert(ll_next(new_node) == NULL);
408 cx_linked_list_insert_sorted_chain(
409 begin, end, loc_prev, loc_next, new_node, cmp_func);
410 }
411
397 void cx_linked_list_insert_sorted_chain( 412 void cx_linked_list_insert_sorted_chain(
398 void **begin, 413 void **begin,
399 void **end, 414 void **end,
400 ptrdiff_t loc_prev, 415 ptrdiff_t loc_prev,
401 ptrdiff_t loc_next, 416 ptrdiff_t loc_next,
402 void *insert_begin, 417 void *insert_begin,
403 cx_compare_func cmp_func 418 cx_compare_func cmp_func
404 ) { 419 ) {
420 cx_compare_func_wrapper wrapper = {cmp_func};
405 cx_linked_list_insert_sorted_chain_impl( 421 cx_linked_list_insert_sorted_chain_impl(
406 begin, end, loc_prev, loc_next, 422 begin, end, loc_prev, loc_next,
407 insert_begin, cmp_func, true); 423 insert_begin, cx_ccmp_wrap, &wrapper, true);
408 } 424 }
409 425
410 int cx_linked_list_insert_unique( 426 int cx_linked_list_insert_unique(
411 void **begin, 427 void **begin,
412 void **end, 428 void **end,
426 ptrdiff_t loc_prev, 442 ptrdiff_t loc_prev,
427 ptrdiff_t loc_next, 443 ptrdiff_t loc_next,
428 void *insert_begin, 444 void *insert_begin,
429 cx_compare_func cmp_func 445 cx_compare_func cmp_func
430 ) { 446 ) {
447 cx_compare_func_wrapper wrapper = {cmp_func};
431 return cx_linked_list_insert_sorted_chain_impl( 448 return cx_linked_list_insert_sorted_chain_impl(
432 begin, end, loc_prev, loc_next, 449 begin, end, loc_prev, loc_next,
433 insert_begin, cmp_func, false); 450 insert_begin, cx_ccmp_wrap, &wrapper, false);
451 }
452
453 void cx_linked_list_insert_sorted_c(
454 void **begin,
455 void **end,
456 ptrdiff_t loc_prev,
457 ptrdiff_t loc_next,
458 void *new_node,
459 cx_compare_func2 cmp_func,
460 void *context
461 ) {
462 assert(ll_next(new_node) == NULL);
463 cx_linked_list_insert_sorted_chain_c(
464 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
465 }
466
467 void cx_linked_list_insert_sorted_chain_c(
468 void **begin,
469 void **end,
470 ptrdiff_t loc_prev,
471 ptrdiff_t loc_next,
472 void *insert_begin,
473 cx_compare_func2 cmp_func,
474 void *context
475 ) {
476 cx_linked_list_insert_sorted_chain_impl(
477 begin, end, loc_prev, loc_next,
478 insert_begin, cmp_func, context, true);
479 }
480
481 int cx_linked_list_insert_unique_c(
482 void **begin,
483 void **end,
484 ptrdiff_t loc_prev,
485 ptrdiff_t loc_next,
486 void *new_node,
487 cx_compare_func2 cmp_func,
488 void *context
489 ) {
490 assert(ll_next(new_node) == NULL);
491 return NULL != cx_linked_list_insert_unique_chain_c(
492 begin, end, loc_prev, loc_next, new_node, cmp_func, context);
493 }
494
495 void *cx_linked_list_insert_unique_chain_c(
496 void **begin,
497 void **end,
498 ptrdiff_t loc_prev,
499 ptrdiff_t loc_next,
500 void *insert_begin,
501 cx_compare_func2 cmp_func,
502 void *context
503 ) {
504 return cx_linked_list_insert_sorted_chain_impl(
505 begin, end, loc_prev, loc_next,
506 insert_begin, cmp_func, context, false);
434 } 507 }
435 508
436 size_t cx_linked_list_remove_chain( 509 size_t cx_linked_list_remove_chain(
437 void **begin, 510 void **begin,
438 void **end, 511 void **end,
509 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE 582 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
510 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 583 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
511 #endif 584 #endif
512 585
513 static void cx_linked_list_sort_merge( 586 static void cx_linked_list_sort_merge(
587 void **begin,
588 void **end,
514 ptrdiff_t loc_prev, 589 ptrdiff_t loc_prev,
515 ptrdiff_t loc_next, 590 ptrdiff_t loc_next,
516 ptrdiff_t loc_data, 591 ptrdiff_t loc_data,
517 size_t length, 592 size_t length,
518 void *ls, 593 void *ls,
519 void *le, 594 void *le,
520 void *re, 595 void *re,
521 cx_compare_func cmp_func, 596 cx_compare_func2 cmp_func,
522 void **begin, 597 void *context
523 void **end
524 ) { 598 ) {
525 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 599 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
526 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 600 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
527 cxMallocDefault(sizeof(void *) * length) : sbo; 601 cxMallocDefault(sizeof(void *) * length) : sbo;
528 if (sorted == NULL) abort(); // LCOV_EXCL_LINE 602 if (sorted == NULL) abort(); // LCOV_EXCL_LINE
530 604
531 lc = ls; 605 lc = ls;
532 rc = le; 606 rc = le;
533 size_t n = 0; 607 size_t n = 0;
534 while (lc && lc != le && rc != re) { 608 while (lc && lc != le && rc != re) {
535 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 609 if (cmp_func(ll_data(lc), ll_data(rc), context) <= 0) {
536 sorted[n] = lc; 610 sorted[n] = lc;
537 lc = ll_next(lc); 611 lc = ll_next(lc);
538 } else { 612 } else {
539 sorted[n] = rc; 613 sorted[n] = rc;
540 rc = ll_next(rc); 614 rc = ll_next(rc);
564 if (sorted != sbo) { 638 if (sorted != sbo) {
565 cxFreeDefault(sorted); 639 cxFreeDefault(sorted);
566 } 640 }
567 } 641 }
568 642
569 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function 643 void cx_linked_list_sort_c( // NOLINT(misc-no-recursion) - purposely recursive function
570 void **begin, 644 void **begin,
571 void **end, 645 void **end,
572 ptrdiff_t loc_prev, 646 ptrdiff_t loc_prev,
573 ptrdiff_t loc_next, 647 ptrdiff_t loc_next,
574 ptrdiff_t loc_data, 648 ptrdiff_t loc_data,
575 cx_compare_func cmp_func 649 cx_compare_func2 cmp_func,
650 void *context
576 ) { 651 ) {
577 assert(begin != NULL); 652 assert(begin != NULL);
578 assert(loc_next >= 0); 653 assert(loc_next >= 0);
579 assert(loc_data >= 0); 654 assert(loc_data >= 0);
580 assert(cmp_func); 655 assert(cmp_func);
588 if (ls == NULL) return; 663 if (ls == NULL) return;
589 664
590 // check how many elements are already sorted 665 // check how many elements are already sorted
591 lc = ls; 666 lc = ls;
592 size_t ln = 1; 667 size_t ln = 1;
593 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 668 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc), context) > 0) {
594 lc = ll_next(lc); 669 lc = ll_next(lc);
595 ln++; 670 ln++;
596 } 671 }
597 le = ll_next(lc); 672 le = ll_next(lc);
598 673
600 if (le != NULL) { 675 if (le != NULL) {
601 void *rc; 676 void *rc;
602 size_t rn = 1; 677 size_t rn = 1;
603 rc = le; 678 rc = le;
604 // skip already sorted elements 679 // skip already sorted elements
605 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 680 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc), context) > 0) {
606 rc = ll_next(rc); 681 rc = ll_next(rc);
607 rn++; 682 rn++;
608 } 683 }
609 re = ll_next(rc); 684 re = ll_next(rc);
610 685
611 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 686 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
612 void *sorted_begin, *sorted_end; 687 void *sorted_begin, *sorted_end;
613 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 688 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
689 loc_prev, loc_next, loc_data,
614 ln + rn, ls, le, re, cmp_func, 690 ln + rn, ls, le, re, cmp_func,
615 &sorted_begin, &sorted_end); 691 context);
616 692
617 // Something left? Sort it! 693 // Something left? Sort it!
618 size_t remainder_length = cx_linked_list_size(re, loc_next); 694 size_t remainder_length = cx_linked_list_size(re, loc_next);
619 if (remainder_length > 0) { 695 if (remainder_length > 0) {
620 void *remainder = re; 696 void *remainder = re;
621 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); 697 cx_linked_list_sort_c(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func, context);
622 698
623 // merge sorted list with (also sorted) remainder 699 // merge sorted list with (also sorted) remainder
624 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 700 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
701 loc_prev, loc_next, loc_data,
625 ln + rn + remainder_length, 702 ln + rn + remainder_length,
626 sorted_begin, remainder, NULL, cmp_func, 703 sorted_begin, remainder, NULL, cmp_func,
627 &sorted_begin, &sorted_end); 704 context);
628 } 705 }
629 *begin = sorted_begin; 706 *begin = sorted_begin;
630 if (end) *end = sorted_end; 707 if (end) *end = sorted_end;
631 } 708 }
709 }
710
711 void cx_linked_list_sort(
712 void **begin,
713 void **end,
714 ptrdiff_t loc_prev,
715 ptrdiff_t loc_next,
716 ptrdiff_t loc_data,
717 cx_compare_func cmp_func
718 ) {
719 cx_compare_func_wrapper wrapper = {cmp_func};
720 cx_linked_list_sort_c(begin, end, loc_prev, loc_next, loc_data, cx_ccmp_wrap, &wrapper);
721 }
722
723 int cx_linked_list_compare_c(
724 const void *begin_left,
725 const void *begin_right,
726 ptrdiff_t loc_advance,
727 ptrdiff_t loc_data,
728 cx_compare_func2 cmp_func,
729 void *context
730 ) {
731 const void *left = begin_left, *right = begin_right;
732
733 while (left != NULL && right != NULL) {
734 const void *left_data = ll_data(left);
735 const void *right_data = ll_data(right);
736 int result = cmp_func(left_data, right_data, context);
737 if (result != 0) return result;
738 left = ll_advance(left);
739 right = ll_advance(right);
740 }
741
742 if (left != NULL) { return 1; }
743 else if (right != NULL) { return -1; }
744 else { return 0; }
632 } 745 }
633 746
634 int cx_linked_list_compare( 747 int cx_linked_list_compare(
635 const void *begin_left, 748 const void *begin_left,
636 const void *begin_right, 749 const void *begin_right,
637 ptrdiff_t loc_advance, 750 ptrdiff_t loc_advance,
638 ptrdiff_t loc_data, 751 ptrdiff_t loc_data,
639 cx_compare_func cmp_func 752 cx_compare_func cmp_func
640 ) { 753 ) {
641 const void *left = begin_left, *right = begin_right; 754 cx_compare_func_wrapper wrapper = {cmp_func};
642 755 return cx_linked_list_compare_c(begin_left, begin_right,
643 while (left != NULL && right != NULL) { 756 loc_advance, loc_data, cx_ccmp_wrap, &wrapper);
644 const void *left_data = ll_data(left);
645 const void *right_data = ll_data(right);
646 int result = cmp_func(left_data, right_data);
647 if (result != 0) return result;
648 left = ll_advance(left);
649 right = ll_advance(right);
650 }
651
652 if (left != NULL) { return 1; }
653 else if (right != NULL) { return -1; }
654 else { return 0; }
655 } 757 }
656 758
657 void cx_linked_list_reverse( 759 void cx_linked_list_reverse(
658 void **begin, 760 void **begin,
659 void **end, 761 void **end,
796 char *next = CX_LL_PTR(node, ll->loc_next); 898 char *next = CX_LL_PTR(node, ll->loc_next);
797 return next + ll->loc_data; 899 return next + ll->loc_data;
798 } 900 }
799 } 901 }
800 902
801 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 903 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r, void *c) {
802 static _Thread_local off_t cx_ll_insert_sorted_loc_data; 904 cx_linked_list *list = c;
803 905 const char *left = (const char*)l + list->loc_data;
804 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { 906 const char *right = (const char*)r + list->loc_data;
805 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; 907 return cx_list_compare_wrapper(left, right, list);
806 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
807 return cx_ll_insert_sorted_cmp_func(left, right);
808 } 908 }
809 909
810 static size_t cx_ll_insert_sorted_impl( 910 static size_t cx_ll_insert_sorted_impl(
811 struct cx_list_s *list, 911 struct cx_list_s *list,
812 const void *array, 912 const void *array,
837 CX_LL_PTR(next, ll->loc_prev) = prev; 937 CX_LL_PTR(next, ll->loc_prev) = prev;
838 prev = next; 938 prev = next;
839 } 939 }
840 CX_LL_PTR(prev, ll->loc_next) = NULL; 940 CX_LL_PTR(prev, ll->loc_next) = NULL;
841 941
842 // invoke the low level function 942 // invoke the low-level function
843 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; 943 void *duplicates = cx_linked_list_insert_sorted_chain_impl(
844 cx_ll_insert_sorted_loc_data = ll->loc_data; 944 &ll->begin,
845 if (allow_duplicates) { 945 &ll->end,
846 cx_linked_list_insert_sorted_chain( 946 ll->loc_prev,
847 &ll->begin, 947 ll->loc_next,
848 &ll->end, 948 chain,
849 ll->loc_prev, 949 cx_ll_insert_sorted_cmp_helper,
850 ll->loc_next, 950 list,
851 chain, 951 allow_duplicates
852 cx_ll_insert_sorted_cmp_helper 952 );
853 ); 953 list->collection.size += inserted;
854 list->collection.size += inserted; 954 if (!allow_duplicates) {
855 } else {
856 void *duplicates = cx_linked_list_insert_unique_chain(
857 &ll->begin,
858 &ll->end,
859 ll->loc_prev,
860 ll->loc_next,
861 chain,
862 cx_ll_insert_sorted_cmp_helper
863 );
864 list->collection.size += inserted;
865 // free the nodes that did not make it into the list 955 // free the nodes that did not make it into the list
866 while (duplicates != NULL) { 956 while (duplicates != NULL) {
867 void *next = CX_LL_PTR(duplicates, ll->loc_next); 957 void *next = CX_LL_PTR(duplicates, ll->loc_next);
868 cxFree(list->collection.allocator, duplicates); 958 cxFree(list->collection.allocator, duplicates);
869 duplicates = next; 959 duplicates = next;
1088 ) { 1178 ) {
1089 if (list->collection.size == 0) return 0; 1179 if (list->collection.size == 0) return 0;
1090 1180
1091 size_t index; 1181 size_t index;
1092 cx_linked_list *ll = (cx_linked_list *) list; 1182 cx_linked_list *ll = (cx_linked_list *) list;
1093 char *node = cx_linked_list_find( 1183 char *node = cx_linked_list_find_c(
1094 ll->begin, 1184 ll->begin,
1095 ll->loc_next, ll->loc_data, 1185 ll->loc_next, ll->loc_data,
1096 list->collection.cmpfunc, elem, 1186 elem, &index,
1097 &index 1187 cx_list_compare_wrapper,
1098 ); 1188 list);
1099 if (node == NULL) { 1189 if (node == NULL) {
1100 return list->collection.size; 1190 return list->collection.size;
1101 } 1191 }
1102 if (remove) { 1192 if (remove) {
1103 cx_invoke_destructor(list, node + ll->loc_data); 1193 cx_invoke_destructor(list, node + ll->loc_data);
1109 return index; 1199 return index;
1110 } 1200 }
1111 1201
1112 static void cx_ll_sort(struct cx_list_s *list) { 1202 static void cx_ll_sort(struct cx_list_s *list) {
1113 cx_linked_list *ll = (cx_linked_list *) list; 1203 cx_linked_list *ll = (cx_linked_list *) list;
1114 cx_linked_list_sort(&ll->begin, &ll->end, 1204 cx_linked_list_sort_c(&ll->begin, &ll->end,
1115 ll->loc_prev, ll->loc_next, ll->loc_data, 1205 ll->loc_prev, ll->loc_next, ll->loc_data,
1116 list->collection.cmpfunc); 1206 cx_list_compare_wrapper, list);
1117 } 1207 }
1118 1208
1119 static void cx_ll_reverse(struct cx_list_s *list) { 1209 static void cx_ll_reverse(struct cx_list_s *list) {
1120 cx_linked_list *ll = (cx_linked_list *) list; 1210 cx_linked_list *ll = (cx_linked_list *) list;
1121 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next); 1211 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
1127 ) { 1217 ) {
1128 cx_linked_list *left = (cx_linked_list *) list; 1218 cx_linked_list *left = (cx_linked_list *) list;
1129 cx_linked_list *right = (cx_linked_list *) other; 1219 cx_linked_list *right = (cx_linked_list *) other;
1130 assert(left->loc_next == right->loc_next); 1220 assert(left->loc_next == right->loc_next);
1131 assert(left->loc_data == right->loc_data); 1221 assert(left->loc_data == right->loc_data);
1132 return cx_linked_list_compare(left->begin, right->begin, 1222 return cx_linked_list_compare_c(left->begin, right->begin,
1133 left->loc_next, left->loc_data, 1223 left->loc_next, left->loc_data,
1134 list->collection.cmpfunc); 1224 cx_list_compare_wrapper, (void*)list);
1135 } 1225 }
1136 1226
1137 static bool cx_ll_iter_valid(const void *it) { 1227 static bool cx_ll_iter_valid(const void *it) {
1138 const struct cx_iterator_s *iter = it; 1228 const struct cx_iterator_s *iter = it;
1139 return iter->elem_handle != NULL; 1229 return iter->elem_handle != NULL;
1270 cx_ll_iterator, 1360 cx_ll_iterator,
1271 }; 1361 };
1272 1362
1273 CxList *cxLinkedListCreate( 1363 CxList *cxLinkedListCreate(
1274 const CxAllocator *allocator, 1364 const CxAllocator *allocator,
1275 cx_compare_func comparator,
1276 size_t elem_size 1365 size_t elem_size
1277 ) { 1366 ) {
1278 if (allocator == NULL) { 1367 if (allocator == NULL) {
1279 allocator = cxDefaultAllocator; 1368 allocator = cxDefaultAllocator;
1280 } 1369 }
1285 list->loc_next = sizeof(void*); 1374 list->loc_next = sizeof(void*);
1286 list->loc_data = sizeof(void*)*2; 1375 list->loc_data = sizeof(void*)*2;
1287 list->loc_extra = -1; 1376 list->loc_extra = -1;
1288 list->extra_data_len = 0; 1377 list->extra_data_len = 0;
1289 cx_list_init((CxList*)list, &cx_linked_list_class, 1378 cx_list_init((CxList*)list, &cx_linked_list_class,
1290 allocator, comparator, elem_size); 1379 allocator, elem_size);
1291 1380
1292 return (CxList *) list; 1381 return (CxList *) list;
1293 } 1382 }
1294 1383
1295 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) { 1384 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) {

Mercurial Repository: dbutils

mercurial