311 lines
11 KiB
C
311 lines
11 KiB
C
#include <c_AmericanFlag.h>
|
||
#include <c_ArrayStack.h>
|
||
|
||
#define COMPONENT_AFS_CUTOFF 15
|
||
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
/**
|
||
* @brief 内部原子物理接口：泛型就地连续内存块高效对调
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_AFS_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_AFS_CascadedCompare(const void* a, const void* b, c_size_t start_d, c_AFS_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;
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 降级优化专线：泛型后缀级联插入排序
|
||
*/
|
||
static void c_AFS_InsertionSort(char* base, c_size_t low, c_size_t high, c_size_t elem_size, c_AFS_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_AFS_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 美国国旗排序核心递归分治控制状态机（完全体就地环置换版）
|
||
*/
|
||
static void c_AmericanFlagSort_Recursive(char* base, c_size_t low, c_size_t high, c_size_t elem_size, c_AFS_ExtractorFn extractor, c_size_t d, void* args) {
|
||
if (high <= low || high == (c_size_t)-1) {
|
||
return;
|
||
}
|
||
|
||
if (high - low < COMPONENT_AFS_CUTOFF) {
|
||
c_AFS_InsertionSort(base, low, high, elem_size, extractor, d, args);
|
||
return;
|
||
}
|
||
|
||
// 🌟【规范统一字符表】：终止符 -1 映射到桶 0，普通字节 0~255 映射到桶 1~256，总上限 257
|
||
#define C_AFS_R 257
|
||
c_size_t count[C_AFS_R];
|
||
c_size_t head[C_AFS_R];
|
||
c_size_t end[C_AFS_R]; // 🌟【右边界加固锁】：死死锁存每个桶的绝对开区间截止端点
|
||
|
||
memset(count, 0, sizeof(count));
|
||
|
||
// 步骤 1：频率扫描计数
|
||
for (c_size_t i = low; i <= high; i++) {
|
||
int c = extractor(base + (i * elem_size), d, args);
|
||
count[c + 1]++;
|
||
}
|
||
|
||
// 步骤 2：精准增量式计算每个桶在连续内存 [low, high] 中的物理起始与截止配额
|
||
c_size_t current_offset = low;
|
||
for (int r = 0; r < C_AFS_R; r++) {
|
||
head[r] = current_offset;
|
||
current_offset += count[r];
|
||
end[r] = current_offset;
|
||
}
|
||
|
||
// 克隆一份绝对不会被置换扭转污染的初始边界快照 sub_bounds，专门供后续级联多路分治递归定位安全区
|
||
c_size_t sub_bounds[C_AFS_R];
|
||
memcpy(sub_bounds, head, sizeof(head));
|
||
|
||
// 步骤 3：🌟🌟🌟【美国国旗就地多路环置换绝对内核】🌟🌟🌟
|
||
for (int r = 0; r < C_AFS_R; r++) {
|
||
while (head[r] < end[r]) {
|
||
// 每次进入循环体，必须动态基于当前的 head[r] 最新游标地址执行一维寻址定位
|
||
char* curr_elem = base + (head[r] * elem_size);
|
||
|
||
// 🌟【重新特征提取联锁】：动态计算出换进来的新元素的正确目标桶
|
||
int c = extractor(curr_elem, d, args);
|
||
int c_slot = c + 1;
|
||
|
||
// 情况 A：元素本就属于当前正在梳理的桶 r，无需置换，当前桶游标单调步进滑过
|
||
if (c_slot == r) {
|
||
head[r]++;
|
||
}
|
||
// 情况 B：属于外部其他桶，且那个目标桶目前尚未满员（head < end 锁有效拦截）
|
||
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] 游标指针在原地坚守守候！
|
||
// 在下一轮 while 循环中，由于前面的重提取联锁，会立刻对被对调过来的数据执行哈希哈希特征重提取
|
||
c_AFS_InternalSwap(curr_elem, target_elem, elem_size);
|
||
head[c_slot]++;
|
||
}
|
||
// 情况 C：属于外部其他桶，但目标桶在前面已被前置填满（head >= end）
|
||
else {
|
||
// 说明由于大规模随机碰撞分配它不得不中途暂存，直接向前强行合拢，滑过处理
|
||
head[r]++;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 步骤 4：级联多路分治深层递归（桶 0 对应的终止符 -1 属于完结节点，果断跳过不递归）
|
||
for (int r = 1; r < C_AFS_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_AmericanFlagSort_Recursive(base, next_low, next_high, elem_size, extractor, d + 1, args);
|
||
}
|
||
}
|
||
#undef C_AFS_R
|
||
}
|
||
|
||
/**
|
||
* @brief 工业级纯就地、零动态堆内存损耗泛型美国国旗排序标准对外总线入口
|
||
*/
|
||
c_err_t c_AmericanFlag_Sort(void* base, c_size_t num, c_size_t elem_size, c_AFS_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_AmericanFlagSort_Recursive(array_base, 0, num - 1, elem_size, extractor, 0, args);
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
// 显式转储栈的最大深度上限（足以承载 1024 层深度的字符串级联下探，物理隔离栈溢出）
|
||
#define COMPONENT_NAFS_STACK_MAX 1024
|
||
|
||
typedef struct {
|
||
c_size_t low; // 当前待处理区间的左闭端点物理下标
|
||
c_size_t high; // 当前待处理区间的右闭端点物理下标
|
||
c_size_t d; // 当前执行分桶扫描的第 d 个无符号字节游标位置
|
||
} c_NAFS_Frame_t;
|
||
|
||
c_err_t c_AmericanFlag_NonRecSort(void* base, c_size_t num, c_size_t elem_size, c_AFS_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; // 零体安全放行
|
||
}
|
||
|
||
char* array_base = (char*)base;
|
||
|
||
// 🌟【非递归核心防线】：在栈空间建立显式帧管理矩阵，将弹跳开销控制在确定常量内
|
||
c_ArrayStack_t stack;
|
||
c_ArrayStack_Init(&stack, sizeof(c_NAFS_Frame_t), 1024, allocator);
|
||
// c_NAFS_Frame_t stack[COMPONENT_NAFS_STACK_MAX];
|
||
// c_size_t stack_size = 0;
|
||
|
||
// 初始首帧压栈：区间为 [0, num-1]，高位起始字节 d = 0
|
||
// stack[stack_size].low = 0;
|
||
// stack[stack_size].high = num - 1;
|
||
// stack[stack_size].d = 0;
|
||
// stack_size++;
|
||
|
||
c_NAFS_Frame_t frame;
|
||
frame.low = 0;
|
||
frame.high = num - 1;
|
||
frame.d = 0;
|
||
c_ArrayStack_Push(&stack, &frame);
|
||
|
||
#define C_AFS_R 257
|
||
c_size_t count[C_AFS_R];
|
||
c_size_t head[C_AFS_R];
|
||
c_size_t end[C_AFS_R];
|
||
c_size_t sub_bounds[C_AFS_R];
|
||
|
||
|
||
// 启动非递归主迭代滑窗
|
||
while (!c_ArrayStack_IsEmpty(&stack)) {
|
||
// 出栈当前待处理的帧载体
|
||
// stack_size--;
|
||
// c_size_t low = stack[stack_size].low;
|
||
// c_size_t high = stack[stack_size].high;
|
||
// c_size_t d = stack[stack_size].d;
|
||
|
||
c_ArrayStack_Pop(&stack, &frame);
|
||
c_size_t low = frame.low;
|
||
c_size_t high = frame.high;
|
||
c_size_t d = frame.d;
|
||
|
||
// 极限拦截
|
||
if (high <= low || high == (c_size_t)-1) {
|
||
continue;
|
||
}
|
||
|
||
// 优化点 1：小区间降级截断，直接走快速就地级联插入专线
|
||
if (high - low < COMPONENT_AFS_CUTOFF) {
|
||
c_AFS_InsertionSort(array_base, low, high, elem_size, extractor, d, args);
|
||
continue;
|
||
}
|
||
|
||
memset(count, 0, sizeof(count));
|
||
|
||
// 1. 频率扫描计数
|
||
for (c_size_t i = low; i <= high; i++) {
|
||
int c = extractor(array_base + (i * elem_size), d, args);
|
||
count[c + 1]++;
|
||
}
|
||
|
||
// 2. 精确增量式计算每个桶在当前闭区间内绝对物理起始与截止配额
|
||
c_size_t current_offset = low;
|
||
for (int r = 0; r < C_AFS_R; r++) {
|
||
head[r] = current_offset;
|
||
current_offset += count[r];
|
||
end[r] = current_offset;
|
||
}
|
||
|
||
// 锁存绝对不变的初始边界快照
|
||
memcpy(sub_bounds, head, sizeof(head));
|
||
|
||
// 3. 🌟🌟🌟【环置换无损对调核心状态机（Dynamic Remap Lock）】🌟🌟🌟
|
||
for (int r = 0; r < C_AFS_R; r++) {
|
||
while (head[r] < end[r]) {
|
||
char* curr_elem = array_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 = array_base + (dest_pos * elem_size);
|
||
c_AFS_InternalSwap(curr_elem, target_elem, elem_size);
|
||
head[c_slot]++;
|
||
}
|
||
else {
|
||
head[r]++;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 4. 🌟【迭代变轨核心】：将后续的多路深度分治区间逆向压入显式栈中
|
||
// 注意：桶 0 对应的终止符 -1 属于完结节点，彻底剔除不入栈
|
||
for (int r = C_AFS_R - 1; r >= 1; 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) {
|
||
// 状态检查：防止极限特种输入冲破显式栈容量
|
||
// if (stack_size < COMPONENT_NAFS_STACK_MAX) {
|
||
// stack[stack_size].low = next_low;
|
||
// stack[stack_size].high = next_high;
|
||
// stack[stack_size].d = d + 1; // 字节游标单调向右推
|
||
// stack_size++;
|
||
// }
|
||
frame.low = next_low;
|
||
frame.high = next_high;
|
||
frame.d = d+1;
|
||
c_ArrayStack_Push(&stack, &frame);
|
||
}
|
||
}
|
||
|
||
}
|
||
|
||
#undef C_AFS_R
|
||
c_ArrayStack_Destroy(&stack);
|
||
return C_ERR_OK;
|
||
} |