159 lines
5.4 KiB
C
159 lines
5.4 KiB
C
#include <c_InplaceMSD.h>
|
||
|
||
#define COMPONENT_IP_MSD_CUTOFF 15
|
||
|
||
/**
|
||
* @brief 内部原子物理接口：泛型就地连续内存块对调
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_IP_MSD_InternalSwap(void* a, void* b, c_size_t size) {
|
||
if (a == b) return;
|
||
char* p1 = (char*)a;
|
||
char* p2 = (char*)b;
|
||
char temp_buf[256];
|
||
c_size_t bytes_left = size;
|
||
while (bytes_left > 0) {
|
||
c_size_t chunk = (bytes_left < sizeof(temp_buf)) ? bytes_left : sizeof(temp_buf);
|
||
memcpy(temp_buf, p1, chunk);
|
||
memcpy(p1, p2, chunk);
|
||
memcpy(p2, temp_buf, chunk);
|
||
p1 += chunk;
|
||
p2 += chunk;
|
||
bytes_left -= chunk;
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 带起始偏移量 d 的全景多级深度级联字典序比对器
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
int c_IP_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) {
|
||
if (char_a == -1) return 0; // 双方完全全等至截止符
|
||
cur_d++;
|
||
continue;
|
||
}
|
||
return char_a - char_b; // 终止符 -1 天然小于普通字节
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 局部自适应优化：泛型后缀级联插入排序
|
||
*/
|
||
static void c_IP_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);
|
||
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);
|
||
if (c_IP_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 基数排序递归控制状态机（完全隔离式 American Flag）
|
||
*/
|
||
static void c_InPlace_MSD_Recursive(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) {
|
||
if (high <= low || high == (c_size_t)-1) {
|
||
return;
|
||
}
|
||
|
||
if (high - low < COMPONENT_IP_MSD_CUTOFF) {
|
||
c_IP_MSD_InsertionSort(base, low, high, elem_size, extractor, d, args);
|
||
return;
|
||
}
|
||
|
||
#define C_IP_R 257
|
||
c_size_t count[C_IP_R];
|
||
c_size_t head[C_IP_R];
|
||
c_size_t end[C_IP_R];
|
||
|
||
memset(count, 0, sizeof(count));
|
||
|
||
// 步骤 1：频率计算（终止符 -1 映射至桶 0，普通字节 0~255 映射至桶 1~256）
|
||
for (c_size_t i = low; i <= high; i++) {
|
||
int c = extractor(base + (i * elem_size), d, args);
|
||
count[c + 1]++;
|
||
}
|
||
|
||
// 步骤 2：🌟【编译加固核心】：摒弃错误的数组名直接代数赋值，采用符合 C 语法的增量对齐
|
||
c_size_t current_offset = low;
|
||
for (int r = 0; r < C_IP_R; r++) {
|
||
head[r] = current_offset;
|
||
current_offset += count[r];
|
||
end[r] = current_offset; // 精确卡死当前桶的物理右开边界
|
||
}
|
||
|
||
// 独立克隆一份绝对不变的初始边界快照，专门供后面分治变轨定位
|
||
c_size_t sub_bounds[C_IP_R];
|
||
memcpy(sub_bounds, head, sizeof(head));
|
||
|
||
// 步骤 3：环置换无损对调状态机
|
||
for (int r = 0; r < C_IP_R; r++) {
|
||
while (head[r] < end[r]) {
|
||
char* curr_elem = base + (head[r] * elem_size);
|
||
|
||
// 动态重新提取当前插槽换进来的新内容特征，消除残留
|
||
int c = extractor(curr_elem, d, args);
|
||
int c_slot = c + 1;
|
||
|
||
if (c_slot == r) {
|
||
head[r]++; // 合规归位，当前桶游标单调步进
|
||
}
|
||
else if (head[c_slot] < end[c_slot]) {
|
||
c_size_t dest_pos = head[c_slot];
|
||
char* target_elem = base + (dest_pos * elem_size);
|
||
|
||
// 置换指针，且当前 head[r] 指针原地坚守，下一轮循环自动对其重审讯
|
||
c_IP_MSD_InternalSwap(curr_elem, target_elem, elem_size);
|
||
head[c_slot]++;
|
||
}
|
||
else {
|
||
head[r]++; // 外部桶已满，强行作为游离多余项滑过
|
||
}
|
||
}
|
||
}
|
||
|
||
// 步骤 4：级联多路分治递归（桶 0 对应的终止符 -1 区间已经完全完结，彻底跳过不递归）
|
||
for (int r = 1; r < C_IP_R; r++) {
|
||
c_size_t next_low = sub_bounds[r];
|
||
c_size_t next_high = end[r] - 1;
|
||
|
||
if (next_high > next_low && next_high != (c_size_t)-1) {
|
||
c_InPlace_MSD_Recursive(base, next_low, next_high, elem_size, extractor, d + 1, args);
|
||
}
|
||
}
|
||
#undef C_IP_R
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级纯就地、零堆额外损耗泛型 MSD 基数排序统一外部入口
|
||
*/
|
||
c_err_t c_InPlaceMSD_RadixSort(void* base, c_size_t num, c_size_t elem_size, c_MSD_ExtractorFn extractor, void* args) {
|
||
if (!base || elem_size == 0 || !extractor) {
|
||
return C_ERR_PARAM;
|
||
}
|
||
if (num < 2) {
|
||
return C_ERR_OK; // 零体安全放行
|
||
}
|
||
|
||
char* array_base = (char*)base;
|
||
c_InPlace_MSD_Recursive(array_base, 0, num - 1, elem_size, extractor, 0, args);
|
||
return C_ERR_OK;
|
||
}
|