cKit/String/c_MSD.c

#include <c_MSD.h>

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

// 小区间降级截断阈值，小于该元素个数的碎子树不再分配计数桶，直接转产插入排序提速
#define COMPONENT_MSD_CUTOFF 15

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */


/**
 * @brief 🌟【核心加固】：带起始偏移量 d 的全景多级深度级联字典序比对器
 *
 * 专门用于在小区间降级时，完美承接、维系 MSD 的终止符权重与后缀字典序判定
 */
static inline int c_MSD_CascadedCompare(const void* a, const void* b, c_size_t start_d, c_MSD_ExtractorFn extractor, void* args) {
    c_size_t cur_d = start_d;
    while (1) {
        int char_a = extractor(a, cur_d, args);
        int char_b = extractor(b, cur_d, args);

        // 如果完全相等
        if (char_a == char_b) {
            // 如果双双遇到了终止符 -1，说明字符串完全全等，返回 0
            if (char_a == -1) {
                return 0;
            }
            // 否则前缀一致，游标无伤向右推，继续深度对碰比对后缀
            cur_d++;
            continue;
        }

        // 胜负已分：严格遵循 MSD 契约，终止符 -1 是绝对的极小值
        return char_a - char_b;
    }
}

/**
 * @brief 纠正后的局部内联优化泛型插入排序
 */
static void c_MSD_InsertionSort(char* base, c_size_t low, c_size_t high, c_size_t elem_size, c_MSD_ExtractorFn extractor, c_size_t d, void* args) {
    for (c_size_t i = low + 1; i <= high; i++) {
        c_size_t j = i;
        char* item_i = base + (i * elem_size);

        // 分配 256 字节的局部栈栈缓冲区承接影子副本，隔绝别名践踏
        // assert(elem_size<256);
        char v_buf[elem_size];
        memcpy(v_buf, item_i, elem_size);

        while (j > low) {
            char* previous = base + ((j - 1) * elem_size);
            char* current  = base + (j * elem_size);

            // 🌟【核心修正】：调用带偏移量 d 的深度级联比对器，对后缀执行完全的字典序倒装走查
            if (c_MSD_CascadedCompare(v_buf, previous, d, extractor, args) < 0) {
                memcpy(current, previous, elem_size);
                j--;
            } else {
                break;
            }
        }
        memcpy(base + (j * elem_size), v_buf, elem_size);
    }
}

/**
 * @brief MSD 高位优先基数排序分治递归核心状态机
 */
static void c_MSD_RadixSortRecursive(char* base, char* aux, c_size_t low, c_size_t high, c_size_t elem_size, c_MSD_ExtractorFn extractor, c_size_t d, void* args) {
    if (high <= low || high == (c_size_t)-1) {
        return;
    }

    // 优化点 1：大荡荡后的碎子树完美降级截断
    if (high - low < COMPONENT_MSD_CUTOFF) {
        c_MSD_InsertionSort(base, low, high, elem_size, extractor, d, args);
        return;
    }

    #define C_MSD_R 256
    c_size_t count[C_MSD_R + 2];
    memset(count, 0, sizeof(count));

    for (c_size_t i = low; i <= high; i++) {
        int c = extractor(base + (i * elem_size), d, args);
        count[c + 2]++;
    }

    for (int r = 0; r < C_MSD_R + 1; r++) {
        count[r + 1] += count[r];
    }

    for (c_size_t i = low; i <= high; i++) {
        int c = extractor(base + (i * elem_size), d, args);
        c_size_t dest_idx = count[c + 1]++;
        memcpy(aux + (dest_idx * elem_size), base + (i * elem_size), elem_size);
    }

    c_size_t range_len = high - low + 1;
    memcpy(base + (low * elem_size), aux, range_len * elem_size);

    // 🌟【分治避让控制】：终止符 r = -1 映射在映射后的位置，其对应的区间元素已完全排好序，
    // 必须被剔除、略过，不再触发后续的 d+1 右移推进！
    for (int r = 0; r < C_MSD_R; r++) {
        c_size_t next_low  = low + count[r];
        if (count[r + 1] > count[r]) {
            c_size_t next_high = low + count[r + 1] - 1;
            if (next_high > next_low) {
                c_MSD_RadixSortRecursive(base, aux, next_low, next_high, elem_size, extractor, d + 1, args);
            }
        }
    }
    #undef C_MSD_R
}

/**
 * @brief 变长泛型高位优先（MSD）基数排序对外标准入口
 */
c_err_t c_MSD_RadixSort(void* base, c_size_t num, c_size_t elem_size, c_MSD_ExtractorFn extractor, void* args, c_Allocator_t* allocator) {
    if (!base || elem_size == 0 || !extractor) {
        return C_ERR_PARAM;
    }
    if (num < 2) {
        return C_ERR_OK;
    }

    c_Allocator_t local_alloc;
    if (allocator) {
        local_alloc = *allocator;
    } else {
        local_alloc = c_DefaultAllocator;
    }

    char* array_base = (char*)base;

    if (((c_size_t)-1) / elem_size < num) {
        return C_ERR_NOMEM;
    }

    char* aux = (char*)c_Allocator_Alloc(&local_alloc, num * elem_size);
    if (!aux) {
        return C_ERR_NOMEM;
    }

    c_MSD_RadixSortRecursive(array_base, aux, 0, num - 1, elem_size, extractor, 0, args);

    c_Allocator_Free(&local_alloc, aux);
    return C_ERR_OK;
}