comparison: src/array_list.c
src/array_list.c
- changeset 1507
- f4010cda9a2a
- parent 1496
- 1a982f6f2407
- child 1508
- dfc0ddd9571e
equal
deleted
inserted
replaced
| 1506:2a4339475bcf | 1507:f4010cda9a2a |
|---|---|
| 593 ) { | 593 ) { |
| 594 return cx_array_insert_sorted_impl(target, size, capacity, | 594 return cx_array_insert_sorted_impl(target, size, capacity, |
| 595 cmp_func, sorted_data, elem_size, elem_count, reallocator, false); | 595 cmp_func, sorted_data, elem_size, elem_count, reallocator, false); |
| 596 } | 596 } |
| 597 | 597 |
| 598 size_t cx_array_binary_search_inf( | 598 // implementation that finds ANY index |
| 599 static size_t cx_array_binary_search_inf_impl( | |
| 599 const void *arr, | 600 const void *arr, |
| 600 size_t size, | 601 size_t size, |
| 601 size_t elem_size, | 602 size_t elem_size, |
| 602 const void *elem, | 603 const void *elem, |
| 603 cx_compare_func cmp_func | 604 cx_compare_func cmp_func |
| 638 pivot_index = left_index + (right_index - left_index) / 2; | 639 pivot_index = left_index + (right_index - left_index) / 2; |
| 639 const char *arr_elem = array + pivot_index * elem_size; | 640 const char *arr_elem = array + pivot_index * elem_size; |
| 640 result = cmp_func(elem, arr_elem); | 641 result = cmp_func(elem, arr_elem); |
| 641 if (result == 0) { | 642 if (result == 0) { |
| 642 // found it! | 643 // found it! |
| 643 // check previous elements; | |
| 644 // when they are equal, report the smallest index | |
| 645 arr_elem -= elem_size; | |
| 646 while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) { | |
| 647 pivot_index--; | |
| 648 arr_elem -= elem_size; | |
| 649 } | |
| 650 return pivot_index; | 644 return pivot_index; |
| 651 } else if (result < 0) { | 645 } else if (result < 0) { |
| 652 // element is smaller than pivot, continue search left | 646 // element is smaller than pivot, continue search left |
| 653 right_index = pivot_index - 1; | 647 right_index = pivot_index - 1; |
| 654 } else { | 648 } else { |
| 657 } | 651 } |
| 658 } | 652 } |
| 659 | 653 |
| 660 // report the largest upper bound | 654 // report the largest upper bound |
| 661 return result < 0 ? (pivot_index - 1) : pivot_index; | 655 return result < 0 ? (pivot_index - 1) : pivot_index; |
| 656 } | |
| 657 | |
| 658 size_t cx_array_binary_search_inf( | |
| 659 const void *arr, | |
| 660 size_t size, | |
| 661 size_t elem_size, | |
| 662 const void *elem, | |
| 663 cx_compare_func cmp_func | |
| 664 ) { | |
| 665 size_t index = cx_array_binary_search_inf_impl( | |
| 666 arr, size, elem_size, elem, cmp_func); | |
| 667 // in case of equality, report the largest index | |
| 668 const char *e = ((const char *) arr) + (index + 1) * elem_size; | |
| 669 while (index + 1 < size && cmp_func(e, elem) == 0) { | |
| 670 e += elem_size; | |
| 671 index++; | |
| 672 } | |
| 673 return index; | |
| 662 } | 674 } |
| 663 | 675 |
| 664 size_t cx_array_binary_search( | 676 size_t cx_array_binary_search( |
| 665 const void *arr, | 677 const void *arr, |
| 666 size_t size, | 678 size_t size, |
| 684 size_t size, | 696 size_t size, |
| 685 size_t elem_size, | 697 size_t elem_size, |
| 686 const void *elem, | 698 const void *elem, |
| 687 cx_compare_func cmp_func | 699 cx_compare_func cmp_func |
| 688 ) { | 700 ) { |
| 689 size_t inf = cx_array_binary_search_inf( | 701 size_t index = cx_array_binary_search_inf_impl( |
| 690 arr, size, elem_size, elem, cmp_func | 702 arr, size, elem_size, elem, cmp_func |
| 691 ); | 703 ); |
| 692 if (inf == size) { | 704 const char *e = ((const char *) arr) + index * elem_size; |
| 693 // no infimum means, first element is supremum | 705 if (index == size) { |
| 706 // no infimum means the first element is supremum | |
| 694 return 0; | 707 return 0; |
| 695 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { | 708 } else if (cmp_func(e, elem) == 0) { |
| 696 return inf; | 709 // found an equal element, search the smallest index |
| 710 e -= elem_size; // e now contains the element at index-1 | |
| 711 while (index > 0 && cmp_func(e, elem) == 0) { | |
| 712 e -= elem_size; | |
| 713 index--; | |
| 714 } | |
| 715 return index; | |
| 697 } else { | 716 } else { |
| 698 return inf + 1; | 717 // we already have the largest index of the infimum (by design) |
| 718 // the next element is the supremum (or there is no supremum) | |
| 719 return index + 1; | |
| 699 } | 720 } |
| 700 } | 721 } |
| 701 | 722 |
| 702 #ifndef CX_ARRAY_SWAP_SBO_SIZE | 723 #ifndef CX_ARRAY_SWAP_SBO_SIZE |
| 703 #define CX_ARRAY_SWAP_SBO_SIZE 128 | 724 #define CX_ARRAY_SWAP_SBO_SIZE 128 |
