MCPcopy Create free account
hub / github.com/DeusData/codebase-memory-mcp / cypher_stable_sort

Function cypher_stable_sort

src/cypher/cypher.c:3757–3792  ·  view source on GitHub ↗

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. */

Source from the content-addressed store, hash-verified

3755 * the bubble sorts' swap test. Without scratch memory it degrades to an
3756 * insertion sort with the same test and result. */
3757static 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. */

Callers 2

rb_apply_order_byFunction · 0.85
sort_bindingsFunction · 0.85

Calls 2

cbm_allocFunction · 0.85
cbm_freeFunction · 0.85

Tested by

no test coverage detected