哈夫曼压缩程序中realloc异常，Valgrind报错求排查方案

问题描述 #

我正在开发一款基于哈夫曼算法生成字典以压缩文本文件的C语言程序。程序可正常运行，但Valgrind检测出大量realloc相关的内存错误。尝试自行封装realloc逻辑以及直接调用库函数，均无法解决问题，恳请提供排查思路。

运行程序需使用参数格式：-o 1 -f read.txt -v，其中read.txt可为任意ASCII编码的文本文件。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>

const int expand_size = 4;
int length = 4;

typedef struct {
    char w[2]; //word
    int v; //value
    int d; //direction
    char b; //binary
} node_t;

int maxi(node_t * huff, int n) {
    int maxi = huff[0].v;
    for (int i = 0; i < n; i++)
        if (huff[i].v > maxi) {
            maxi = huff[i].v;
        }
    return maxi;
}

int mini(node_t * huff, int n) {
    int mini = maxi(huff, n);
    int w = 0;
    for (int i = 0; i < n; i++)
        if (huff[i].v <= mini && huff[i].v >= 0) {
            w = i;
            mini = huff[i].v;
        }
    return w;
}

node_t * realoc(node_t * huff) {
    node_t * temp = realloc(huff, (length + expand_size) * sizeof(node_t));
    return temp;
}

int huffman(node_t * huff, int n) {
    int j = 1;
    int i = 1;

    int index1;
    int index2;
    int value1;
    int value2;

    while (i != n) {
        index1 = mini(huff, n);
        value1 = huff[index1].v;
        huff[index1].v = -1;
        index2 = mini(huff, n);
        value2 = huff[index2].v;
        huff[index2].v = -1;

        huff[index1].d = n;
        huff[index2].d = n;

        huff[index1].b = '1';
        huff[index2].b = '0';

        if (n == length) {
            node_t * temp;
            temp = realoc(huff);
            huff = temp;
            for (int h = length; h < length + expand_size; h++) {
                huff[h].v = 0;
            }
            length += expand_size;
        }

        huff[n].v = value1 + value2;
        huff[n].w[0] = j + '0';
        j++;
        i = i + 2;
        n++;

    }
    return n;
}

int main(int argc, char ** argv) {
    int n;
    ///reading from a file///
    FILE * read;
    char word[2];
    char c;

    ///getopt parimeters///
    int opt;
    char * file = NULL;
    char steps = 0;
    char compression_level = 0;

    ///getopt///
    while ((opt = getopt(argc, argv, "o:f:v")) != -1) {
        switch (opt) {

        case 'f':
            file = optarg;
            break;

        case 'v':
            steps = 1;
            break;

        case 'o':
            compression_level = atof(optarg);
            break;

        case '?':
            printf("Złe parametry wywołania");
            return 1;
            break;
        }
    }

    read = fopen(file, "r");

    node_t * huff = malloc(sizeof(node_t) * (length));

    int counter = 0; ///how many nodes are in the table (nodes from the file not the ones that we create with huffman algorithm)

    for (int i = 0; i < length; i++)
        huff[i].v = 0;

    if (read == NULL) {
        printf("file can't be opened \n");
        return 1;
    }

    if (compression_level == 1) {
        while ((c = fgetc(read)) != EOF) {
            for (int i = 0; i < length; i++) {
                if (huff[i].v == 0) {
                    huff[i].w[0] = c;
                    huff[i].v++;
                    counter++;
                    break;
                }
                if (huff[i].w[0] == c) {
                    huff[i].v++;
                    break;
                }
                if (i == length - 1) {
                    node_t * temp;
                    temp = realoc(huff);
                    huff = temp;
                    for (int j = length; j < length + expand_size; j++) {
                        huff[j].v = 0;
                        //huff[j].w[0] = ' ';
                    }
                    length += expand_size;
                }
            }
        }
    }

    n = huffman(huff, counter);

    ///printing the table///

    int l;
    for (int i = 0; i < counter; i++) {
        l = i;

        if (compression_level == 1)
            printf("%c: ", huff[i].w[0]);

        if (compression_level == 2)
            printf("%c%c: ", huff[i].w[0], huff[i].w[1]);

        while (l != n - 1) {
            printf("%c", huff[l].b);
            l = huff[l].d;
        }
        printf("\n");
    }

    if (steps == 1) {
        for (int i = 0; i < counter; i++) {
            if (huff[i].w[0] == 10)
                printf("'%d' 'LINE FEED' occured %d razy\n", huff[i].w[0], huff[i].v);
            //else printf("'%d' '%s' wystapilo %d razy\n", huff[i].w, huff[i].w, huff[i].v);
        }
        printf("array length %d\n", length);
        printf("how many nodes %d\n", n);
        printf("how many primary nodes %d\n", counter);
        //printf("v = %d, o = %d\n", steps, compression_level);
    }
    free(huff);
    fclose(read);
    return 0;
}

核心问题排查 #

1. 指针传递失效导致野指针 #

huffman函数的参数是node_t * huff，属于传值传递。当你在函数内调用realloc并将返回值赋值给局部变量huff时，main函数中的原始指针并不会更新。这会导致main里的指针仍然指向已经被realloc释放的旧内存，后续访问时触发内存错误。

2. 未处理realloc失败的情况 #

封装的realoc函数没有检查realloc的返回值。如果内存分配失败，realloc会返回NULL，此时直接返回NULL会导致后续代码访问空指针，同时原内存块会丢失，造成内存泄漏。

3. 全局变量length引发的逻辑混乱 #

length是全局变量，在main和huffman函数中都被修改，这种共享状态容易导致数组长度的不同步，比如huffman扩容后修改了length，但main中的循环可能基于旧的length值访问越界。

4. 文件读取循环的逻辑漏洞 #

在main的字符处理循环中，当遍历到数组最后一个元素（i == length -1）才触发扩容，但扩容后当前循环直接结束，导致当前字符未被处理。另外，扩容后的新元素初始化不完整，可能引发未定义行为。

5. 哈夫曼算法的循环条件错误 #

原循环条件while (i != n)不符合哈夫曼算法的逻辑：哈夫曼算法需要循环counter-1次（每次合并两个节点，直到只剩根节点），原条件会导致循环次数错误，可能访问超出数组范围的元素。

具体修复步骤 #

1. 修复指针传递问题 #

将huffman函数的参数改为指针的指针，确保main中的指针能同步更新到realloc后的地址：

int huffman(node_t ** huff, int n) {
    int j = 1;
    while (n > 1) {
        int index1 = mini(*huff, n);
        int value1 = (*huff)[index1].v;
        (*huff)[index1].v = -1;

        int index2 = mini(*huff, n);
        int value2 = (*huff)[index2].v;
        (*huff)[index2].v = -1;

        (*huff)[index1].d = n;
        (*huff)[index2].d = n;

        (*huff)[index1].b = '1';
        (*huff)[index2].b = '0';

        if (n == length) {
            node_t * temp = realloc(*huff, (length + expand_size) * sizeof(node_t));
            if (!temp) {
                perror("realloc failed");
                free(*huff);
                exit(EXIT_FAILURE);
            }
            *huff = temp;
            for (int h = length; h < length + expand_size; h++) {
                (*huff)[h].v = 0;
            }
            length += expand_size;
        }

        (*huff)[n].v = value1 + value2;
        (*huff)[n].w[0] = j + '0';
        j++;
        n--;
    }
    return n;
}

同时修改main中的调用：

n = huffman(&huff, counter);

2. 添加realloc错误检查 #

修改realoc函数，增加错误处理：

node_t * realoc(node_t * huff) {
    node_t * temp = realloc(huff, (length + expand_size) * sizeof(node_t));
    if (!temp) {
        perror("realloc failed");
        free(huff);
        exit(EXIT_FAILURE);
    }
    return temp;
}

3. 重构全局变量length（可选但推荐） #

将length改为main函数的局部变量，通过参数传递给需要的函数，避免全局变量带来的不可控性：

int main() {
    int length = 4;
    // ...
    // 调用函数时传递length的指针或值
}

4. 修复文件读取循环逻辑 #

调整字符处理逻辑，确保扩容后能正确处理当前字符：

if (compression_level == 1) {
    while ((c = fgetc(read)) != EOF) {
        int found = 0;
        for (int i = 0; i < length; i++) {
            if (huff[i].v == 0) {
                huff[i].w[0] = c;
                huff[i].v++;
                counter++;
                found = 1;
                break;
            }
            if (huff[i].w[0] == c) {
                huff[i].v++;
                found = 1;
                break;
            }
        }
        if (!found) {
            node_t * temp = realoc(huff);
            huff = temp;
            for (int j = length; j < length + expand_size; j++) {
                huff[j].v = 0;
            }
            huff[length].w[0] = c;
            huff[length].v++;
            counter++;
            length += expand_size;
        }
    }
}

5. 修正哈夫曼循环条件 #

将循环条件改为while (n > 1)，符合哈夫曼算法的合并逻辑，确保循环正确终止。

内容的提问来源于stack exchange，提问作者Michał Jagodzinski