Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 1618
ef7cab6eb131
parent 1605
55b13f583356
equal deleted inserted replaced
1617:d4385f35f8b0 1618:ef7cab6eb131
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_acmp_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
257 void **begin, 271 void **begin,
258 void **end, 272 void **end,
259 ptrdiff_t loc_prev, 273 ptrdiff_t loc_prev,
260 ptrdiff_t loc_next, 274 ptrdiff_t loc_next,
261 void *insert_begin, 275 void *insert_begin,
262 cx_compare_func cmp_func, 276 cx_compare_func2 cmp_func,
277 void *context,
263 bool allow_duplicates 278 bool allow_duplicates
264 ) { 279 ) {
265 assert(begin != NULL); 280 assert(begin != NULL);
266 assert(loc_next >= 0); 281 assert(loc_next >= 0);
267 assert(insert_begin != NULL); 282 assert(insert_begin != NULL);
274 void *dup_begin = NULL; 289 void *dup_begin = NULL;
275 void *dup_end = NULL; 290 void *dup_end = NULL;
276 291
277 // determine the new start 292 // determine the new start
278 { 293 {
279 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); 294 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument, context);
280 if (d <= 0) { 295 if (d <= 0) {
281 // the new chain starts with the original chain 296 // the new chain starts with the original chain
282 new_begin = new_end = source_original; 297 new_begin = new_end = source_original;
283 source_original = ll_next(source_original); 298 source_original = ll_next(source_original);
284 if (d == 0) { 299 if (d == 0) {
300 } 315 }
301 } 316 }
302 317
303 // now successively compare the elements and add them to the correct chains 318 // now successively compare the elements and add them to the correct chains
304 while (source_original != NULL && source_argument != NULL) { 319 while (source_original != NULL && source_argument != NULL) {
305 int d = cmp_func(source_original, source_argument); 320 int d = cmp_func(source_original, source_argument, context);
306 if (d <= 0) { 321 if (d <= 0) {
307 // the original is not larger, add it to the chain 322 // the original is not larger, add it to the chain
308 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); 323 cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
309 new_end = source_original; 324 new_end = source_original;
310 source_original = ll_next(source_original); 325 source_original = ll_next(source_original);
325 source_argument = ll_next(source_argument); 340 source_argument = ll_next(source_argument);
326 } 341 }
327 } else { 342 } else {
328 // the original is larger, append the source argument to the chain 343 // the original is larger, append the source argument to the chain
329 // check if we must discard the source argument as duplicate 344 // check if we must discard the source argument as duplicate
330 if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { 345 if (!allow_duplicates && cmp_func(new_end, source_argument, context) == 0) {
331 if (dup_end == NULL) { 346 if (dup_end == NULL) {
332 dup_begin = dup_end = source_argument; 347 dup_begin = dup_end = source_argument;
333 } else { 348 } else {
334 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 349 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
335 dup_end = source_argument; 350 dup_end = source_argument;
354 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 369 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
355 new_end = cx_linked_list_last(source_argument, loc_next); 370 new_end = cx_linked_list_last(source_argument, loc_next);
356 } else { 371 } else {
357 // otherwise we must check one-by-one 372 // otherwise we must check one-by-one
358 while (source_argument != NULL) { 373 while (source_argument != NULL) {
359 if (cmp_func(new_end, source_argument) == 0) { 374 if (cmp_func(new_end, source_argument, context) == 0) {
360 if (dup_end == NULL) { 375 if (dup_end == NULL) {
361 dup_begin = dup_end = source_argument; 376 dup_begin = dup_end = source_argument;
362 } else { 377 } else {
363 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 378 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next);
364 dup_end = source_argument; 379 dup_end = source_argument;
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_acmp_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_acmp_wrap, &wrapper, false);
434 } 451 }
435 452
436 size_t cx_linked_list_remove_chain( 453 size_t cx_linked_list_remove_chain(
437 void **begin, 454 void **begin,
438 void **end, 455 void **end,
509 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE 526 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
510 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 527 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
511 #endif 528 #endif
512 529
513 static void cx_linked_list_sort_merge( 530 static void cx_linked_list_sort_merge(
531 void **begin,
532 void **end,
514 ptrdiff_t loc_prev, 533 ptrdiff_t loc_prev,
515 ptrdiff_t loc_next, 534 ptrdiff_t loc_next,
516 ptrdiff_t loc_data, 535 ptrdiff_t loc_data,
517 size_t length, 536 size_t length,
518 void *ls, 537 void *ls,
519 void *le, 538 void *le,
520 void *re, 539 void *re,
521 cx_compare_func cmp_func, 540 cx_compare_func2 cmp_func,
522 void **begin, 541 void *context
523 void **end
524 ) { 542 ) {
525 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 543 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
526 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 544 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
527 cxMallocDefault(sizeof(void *) * length) : sbo; 545 cxMallocDefault(sizeof(void *) * length) : sbo;
528 if (sorted == NULL) abort(); // LCOV_EXCL_LINE 546 if (sorted == NULL) abort(); // LCOV_EXCL_LINE
530 548
531 lc = ls; 549 lc = ls;
532 rc = le; 550 rc = le;
533 size_t n = 0; 551 size_t n = 0;
534 while (lc && lc != le && rc != re) { 552 while (lc && lc != le && rc != re) {
535 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 553 if (cmp_func(ll_data(lc), ll_data(rc), context) <= 0) {
536 sorted[n] = lc; 554 sorted[n] = lc;
537 lc = ll_next(lc); 555 lc = ll_next(lc);
538 } else { 556 } else {
539 sorted[n] = rc; 557 sorted[n] = rc;
540 rc = ll_next(rc); 558 rc = ll_next(rc);
564 if (sorted != sbo) { 582 if (sorted != sbo) {
565 cxFreeDefault(sorted); 583 cxFreeDefault(sorted);
566 } 584 }
567 } 585 }
568 586
569 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function 587 void cx_linked_list_sort_c( // NOLINT(misc-no-recursion) - purposely recursive function
570 void **begin, 588 void **begin,
571 void **end, 589 void **end,
572 ptrdiff_t loc_prev, 590 ptrdiff_t loc_prev,
573 ptrdiff_t loc_next, 591 ptrdiff_t loc_next,
574 ptrdiff_t loc_data, 592 ptrdiff_t loc_data,
575 cx_compare_func cmp_func 593 cx_compare_func2 cmp_func,
594 void *context
576 ) { 595 ) {
577 assert(begin != NULL); 596 assert(begin != NULL);
578 assert(loc_next >= 0); 597 assert(loc_next >= 0);
579 assert(loc_data >= 0); 598 assert(loc_data >= 0);
580 assert(cmp_func); 599 assert(cmp_func);
588 if (ls == NULL) return; 607 if (ls == NULL) return;
589 608
590 // check how many elements are already sorted 609 // check how many elements are already sorted
591 lc = ls; 610 lc = ls;
592 size_t ln = 1; 611 size_t ln = 1;
593 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 612 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc), context) > 0) {
594 lc = ll_next(lc); 613 lc = ll_next(lc);
595 ln++; 614 ln++;
596 } 615 }
597 le = ll_next(lc); 616 le = ll_next(lc);
598 617
600 if (le != NULL) { 619 if (le != NULL) {
601 void *rc; 620 void *rc;
602 size_t rn = 1; 621 size_t rn = 1;
603 rc = le; 622 rc = le;
604 // skip already sorted elements 623 // skip already sorted elements
605 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 624 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc), context) > 0) {
606 rc = ll_next(rc); 625 rc = ll_next(rc);
607 rn++; 626 rn++;
608 } 627 }
609 re = ll_next(rc); 628 re = ll_next(rc);
610 629
611 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 630 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
612 void *sorted_begin, *sorted_end; 631 void *sorted_begin, *sorted_end;
613 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 632 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
633 loc_prev, loc_next, loc_data,
614 ln + rn, ls, le, re, cmp_func, 634 ln + rn, ls, le, re, cmp_func,
615 &sorted_begin, &sorted_end); 635 context);
616 636
617 // Something left? Sort it! 637 // Something left? Sort it!
618 size_t remainder_length = cx_linked_list_size(re, loc_next); 638 size_t remainder_length = cx_linked_list_size(re, loc_next);
619 if (remainder_length > 0) { 639 if (remainder_length > 0) {
620 void *remainder = re; 640 void *remainder = re;
621 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); 641 cx_linked_list_sort_c(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func, context);
622 642
623 // merge sorted list with (also sorted) remainder 643 // merge sorted list with (also sorted) remainder
624 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 644 cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
645 loc_prev, loc_next, loc_data,
625 ln + rn + remainder_length, 646 ln + rn + remainder_length,
626 sorted_begin, remainder, NULL, cmp_func, 647 sorted_begin, remainder, NULL, cmp_func,
627 &sorted_begin, &sorted_end); 648 context);
628 } 649 }
629 *begin = sorted_begin; 650 *begin = sorted_begin;
630 if (end) *end = sorted_end; 651 if (end) *end = sorted_end;
631 } 652 }
653 }
654
655 void cx_linked_list_sort(
656 void **begin,
657 void **end,
658 ptrdiff_t loc_prev,
659 ptrdiff_t loc_next,
660 ptrdiff_t loc_data,
661 cx_compare_func cmp_func
662 ) {
663 cx_compare_func_wrapper wrapper = {cmp_func};
664 cx_linked_list_sort_c(begin, end, loc_prev, loc_next, loc_data, cx_acmp_wrap, &wrapper);
665 }
666
667 int cx_linked_list_compare_c(
668 const void *begin_left,
669 const void *begin_right,
670 ptrdiff_t loc_advance,
671 ptrdiff_t loc_data,
672 cx_compare_func2 cmp_func,
673 void *context
674 ) {
675 const void *left = begin_left, *right = begin_right;
676
677 while (left != NULL && right != NULL) {
678 const void *left_data = ll_data(left);
679 const void *right_data = ll_data(right);
680 int result = cmp_func(left_data, right_data, context);
681 if (result != 0) return result;
682 left = ll_advance(left);
683 right = ll_advance(right);
684 }
685
686 if (left != NULL) { return 1; }
687 else if (right != NULL) { return -1; }
688 else { return 0; }
632 } 689 }
633 690
634 int cx_linked_list_compare( 691 int cx_linked_list_compare(
635 const void *begin_left, 692 const void *begin_left,
636 const void *begin_right, 693 const void *begin_right,
637 ptrdiff_t loc_advance, 694 ptrdiff_t loc_advance,
638 ptrdiff_t loc_data, 695 ptrdiff_t loc_data,
639 cx_compare_func cmp_func 696 cx_compare_func cmp_func
640 ) { 697 ) {
641 const void *left = begin_left, *right = begin_right; 698 cx_compare_func_wrapper wrapper = {cmp_func};
642 699 return cx_linked_list_compare_c(begin_left, begin_right,
643 while (left != NULL && right != NULL) { 700 loc_advance, loc_data, cx_acmp_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 } 701 }
656 702
657 void cx_linked_list_reverse( 703 void cx_linked_list_reverse(
658 void **begin, 704 void **begin,
659 void **end, 705 void **end,
796 char *next = CX_LL_PTR(node, ll->loc_next); 842 char *next = CX_LL_PTR(node, ll->loc_next);
797 return next + ll->loc_data; 843 return next + ll->loc_data;
798 } 844 }
799 } 845 }
800 846
801 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 847 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; 848 cx_linked_list *list = c;
803 849 const char *left = (const char*)l + list->loc_data;
804 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { 850 const char *right = (const char*)r + list->loc_data;
805 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; 851 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 } 852 }
809 853
810 static size_t cx_ll_insert_sorted_impl( 854 static size_t cx_ll_insert_sorted_impl(
811 struct cx_list_s *list, 855 struct cx_list_s *list,
812 const void *array, 856 const void *array,
837 CX_LL_PTR(next, ll->loc_prev) = prev; 881 CX_LL_PTR(next, ll->loc_prev) = prev;
838 prev = next; 882 prev = next;
839 } 883 }
840 CX_LL_PTR(prev, ll->loc_next) = NULL; 884 CX_LL_PTR(prev, ll->loc_next) = NULL;
841 885
842 // invoke the low level function 886 // invoke the low-level function
843 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; 887 void *duplicates = cx_linked_list_insert_sorted_chain_impl(
844 cx_ll_insert_sorted_loc_data = ll->loc_data; 888 &ll->begin,
845 if (allow_duplicates) { 889 &ll->end,
846 cx_linked_list_insert_sorted_chain( 890 ll->loc_prev,
847 &ll->begin, 891 ll->loc_next,
848 &ll->end, 892 chain,
849 ll->loc_prev, 893 cx_ll_insert_sorted_cmp_helper,
850 ll->loc_next, 894 list,
851 chain, 895 allow_duplicates
852 cx_ll_insert_sorted_cmp_helper 896 );
853 ); 897 list->collection.size += inserted;
854 list->collection.size += inserted; 898 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 899 // free the nodes that did not make it into the list
866 while (duplicates != NULL) { 900 while (duplicates != NULL) {
867 void *next = CX_LL_PTR(duplicates, ll->loc_next); 901 void *next = CX_LL_PTR(duplicates, ll->loc_next);
868 cxFree(list->collection.allocator, duplicates); 902 cxFree(list->collection.allocator, duplicates);
869 duplicates = next; 903 duplicates = next;
1088 ) { 1122 ) {
1089 if (list->collection.size == 0) return 0; 1123 if (list->collection.size == 0) return 0;
1090 1124
1091 size_t index; 1125 size_t index;
1092 cx_linked_list *ll = (cx_linked_list *) list; 1126 cx_linked_list *ll = (cx_linked_list *) list;
1093 char *node = cx_linked_list_find( 1127 char *node = cx_linked_list_find_c(
1094 ll->begin, 1128 ll->begin,
1095 ll->loc_next, ll->loc_data, 1129 ll->loc_next, ll->loc_data,
1096 list->collection.cmpfunc, elem, 1130 elem, &index,
1097 &index 1131 cx_list_compare_wrapper,
1098 ); 1132 list);
1099 if (node == NULL) { 1133 if (node == NULL) {
1100 return list->collection.size; 1134 return list->collection.size;
1101 } 1135 }
1102 if (remove) { 1136 if (remove) {
1103 cx_invoke_destructor(list, node + ll->loc_data); 1137 cx_invoke_destructor(list, node + ll->loc_data);
1109 return index; 1143 return index;
1110 } 1144 }
1111 1145
1112 static void cx_ll_sort(struct cx_list_s *list) { 1146 static void cx_ll_sort(struct cx_list_s *list) {
1113 cx_linked_list *ll = (cx_linked_list *) list; 1147 cx_linked_list *ll = (cx_linked_list *) list;
1114 cx_linked_list_sort(&ll->begin, &ll->end, 1148 cx_linked_list_sort_c(&ll->begin, &ll->end,
1115 ll->loc_prev, ll->loc_next, ll->loc_data, 1149 ll->loc_prev, ll->loc_next, ll->loc_data,
1116 list->collection.cmpfunc); 1150 cx_list_compare_wrapper, list);
1117 } 1151 }
1118 1152
1119 static void cx_ll_reverse(struct cx_list_s *list) { 1153 static void cx_ll_reverse(struct cx_list_s *list) {
1120 cx_linked_list *ll = (cx_linked_list *) list; 1154 cx_linked_list *ll = (cx_linked_list *) list;
1121 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next); 1155 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
1127 ) { 1161 ) {
1128 cx_linked_list *left = (cx_linked_list *) list; 1162 cx_linked_list *left = (cx_linked_list *) list;
1129 cx_linked_list *right = (cx_linked_list *) other; 1163 cx_linked_list *right = (cx_linked_list *) other;
1130 assert(left->loc_next == right->loc_next); 1164 assert(left->loc_next == right->loc_next);
1131 assert(left->loc_data == right->loc_data); 1165 assert(left->loc_data == right->loc_data);
1132 return cx_linked_list_compare(left->begin, right->begin, 1166 return cx_linked_list_compare_c(left->begin, right->begin,
1133 left->loc_next, left->loc_data, 1167 left->loc_next, left->loc_data,
1134 list->collection.cmpfunc); 1168 cx_list_compare_wrapper, (void*)list);
1135 } 1169 }
1136 1170
1137 static bool cx_ll_iter_valid(const void *it) { 1171 static bool cx_ll_iter_valid(const void *it) {
1138 const struct cx_iterator_s *iter = it; 1172 const struct cx_iterator_s *iter = it;
1139 return iter->elem_handle != NULL; 1173 return iter->elem_handle != NULL;

Mercurial Repository: ucx

mercurial