Stable sort of idx[0..n). Both this and the bubble sorts it replaces are * stable, so for any consistent ordering they give the same permutation. An * item moves before an earlier one only when cmp(earlier, item) > 0, which is * the bubble sorts' swap test. Without scratch memory it degrades to an * insertion sort with the same test and result. */
| 3755 | * the bubble sorts' swap test. Without scratch memory it degrades to an |
| 3756 | * insertion sort with the same test and result. */ |
| 3757 | static void cypher_stable_sort(int *idx, int n, cypher_index_cmp_fn cmp, const void *ctx) { |
| 3758 | if (n < PAIR_LEN) { |
| 3759 | return; |
| 3760 | } |
| 3761 | int *tmp = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)n * sizeof(int)); |
| 3762 | if (!tmp) { |
| 3763 | for (int i = SKIP_ONE; i < n; i++) { |
| 3764 | for (int j = i; j > 0 && cmp(ctx, idx[j - SKIP_ONE], idx[j]) > 0; j--) { |
| 3765 | int swap = idx[j]; |
| 3766 | idx[j] = idx[j - SKIP_ONE]; |
| 3767 | idx[j - SKIP_ONE] = swap; |
| 3768 | } |
| 3769 | } |
| 3770 | return; |
| 3771 | } |
| 3772 | for (int64_t width = SKIP_ONE; width < n; width *= PAIR_LEN) { |
| 3773 | for (int64_t lo = 0; lo < n; lo += PAIR_LEN * width) { |
| 3774 | int64_t mid = lo + width < n ? lo + width : n; |
| 3775 | int64_t hi = mid + width < n ? mid + width : n; |
| 3776 | int64_t i = lo; |
| 3777 | int64_t j = mid; |
| 3778 | int64_t k = lo; |
| 3779 | while (i < mid && j < hi) { |
| 3780 | tmp[k++] = cmp(ctx, idx[i], idx[j]) > 0 ? idx[j++] : idx[i++]; |
| 3781 | } |
| 3782 | while (i < mid) { |
| 3783 | tmp[k++] = idx[i++]; |
| 3784 | } |
| 3785 | while (j < hi) { |
| 3786 | tmp[k++] = idx[j++]; |
| 3787 | } |
| 3788 | } |
| 3789 | memcpy(idx, tmp, (size_t)n * sizeof(int)); |
| 3790 | } |
| 3791 | cbm_free(CBM_MEM_CLASS_OTHER, tmp); |
| 3792 | } |
| 3793 | |
| 3794 | /* String key → the index it was first recorded with. Keys are copied: the |
| 3795 | * arrays they mirror are reallocated as they grow. */ |
no test coverage detected