munmap_chunk(): invalid pointer错误排查：计数排序free操作异常

在实现针对foo结构体的计数排序（作为基数排序的子函数）时，执行free(T)操作触发munmap_chunk(): invalid pointer错误。以下是相关代码及问题分析：

核心问题代码（计数排序实现） #

void csortr(foo* A, const size_t n, const int d) { // 大小为n的foo数组，按第d个字符排序
    int count[95] = { 0 }; // 值的范围确定为95个

    for (register int i = 0; i < n; ++i) {
        ++(count[index(A[i].key[d])]); // index函数用于获取字符的索引（已独立测试，逻辑正确）
    }

    for (register int i = 1; i < 95; ++i) {
        count[i] += count[i - 1];
    }

    foo* T = (foo*) malloc(n * rectypesize);
    memcpy(T, A, n * rectypesize);

    // 问题出在此处
    for (register int i = 0; i < n; ++i) {
        memcpy(&A[count[index(T[i].key[d])]], &T[i], rectypesize);
    }

    free(T);
}

相关依赖代码 #

基数排序调用函数 #

void rsortr(foo* A, const size_t n) {
    // 从“最低位”到“最高位”遍历“数位”
    for (register int i = KEYLEN - 1; i > -1; --i) {
        csortr(A, n, i);
    }
}

main函数调用方式 #

rsortr(data, len); // data为foo*类型，len为size_t类型

index函数 #

short index(const char c) {
  return (short) (c - ' '); // 问题域信息：最小字符为' '，最大为'~'，对应索引0..94，因此使用95作为相关数组大小
}

foo结构体定义 #

typedef struct {
    char key[KEYLEN + 1]; // 这些大小并非问题原因
    char value[VALLEN + 1];
} foo;

rectypesize是常量sizeof(foo)。

错误原因分析 #

1. 数组越界写入：计数排序中，累加后的count数组里，count[k]表示的是小于等于索引k的元素总数，最大值为n。而数组A的有效下标范围是0到n-1，直接使用&A[count[index(T[i].key[d])]]会访问到A[n]这个越界位置，写入该位置会破坏堆内存的元数据（包括T的内存块信息），最终导致free(T)时触发指针无效错误。
2. 计数排序逻辑错误：标准计数排序需要从后往前遍历临时数组，并且每次放置元素后递减对应count值，否则会出现元素覆盖、位置冲突的问题，同时也会导致越界。

修复方案 #

修正计数排序的核心逻辑，调整count数组的使用方式，避免越界：

void csortr(foo* A, const size_t n, const int d) {
    int count[95] = { 0 };

    for (register int i = 0; i < n; ++i) {
        ++count[index(A[i].key[d])];
    }

    // 累加后，将count转换为元素的最后下标（从0开始）
    for (register int i = 1; i < 95; ++i) {
        count[i] += count[i - 1];
    }

    foo* T = (foo*) malloc(n * rectypesize);
    memcpy(T, A, n * rectypesize);

    // 从后往前遍历临时数组，避免相同元素的顺序被打乱（稳定排序）
    for (register int i = n - 1; i >= 0; --i) {
        int idx = index(T[i].key[d]);
        // 先递减count值，得到当前元素的正确下标
        count[idx]--;
        memcpy(&A[count[idx]], &T[i], rectypesize);
    }

    free(T);
}

修复要点 #

• 将count数组的值转换为元素的最后有效下标：通过先递减count[idx]，确保下标落在0到n-1范围内，避免越界。
• 从后往前遍历临时数组T：保证计数排序的稳定性，这对基数排序的正确性至关重要（基数排序依赖稳定的子排序算法）。

内容的提问来源于stack exchange，提问作者William Edwardson