realloc 在简单的字典库中失败

Question

我用 C 为一个快速项目编写了一个轻量级字典，但出现错误：realloc(): invalid next size。我知道这意味着我的堆以某种方式损坏了，但我不确定我做错了什么，看起来我的代码非常简单。

realloc 总是在第四次访问时失败，即 dict->num_kvs = 4

下面是我的代码。它包括 dict 库以及使用它的函数。任何帮助将不胜感激

违规功能：

int* get_letter_frequencies(char* stream) { 

    Dict* dict = Dict_initialize();    

    for(int i = 0; i < strlen(stream); i++) {
        Dict_increment_or_add_key(dict, stream[i]);
    }

    int* to_return = Dict_get_values_array(dict);

    Dict_free();

    return to_return;
}

simple_dict.c（加上结构定义）


typedef struct kv_pair {
    char key;
    int value;
} KV_Pair;

typedef struct dict_ {
    struct kv_pair* kv_pairs;
    int num_kvs;
} Dict;

Dict* Dict_initialize() {
    Dict* to_return = malloc(sizeof(Dict));
    to_return->num_kvs = 0;
    to_return->kv_pairs = NULL;
    return to_return;
}

void Dict_free(Dict* dict) {
    free(dict->kv_pairs);
    free(dict);
}

int Dict_add_key(Dict* dict, char key) {
    dict->num_kvs++;
    printf("next size: %d\n", dict->num_kvs);
    dict->kv_pairs = realloc(dict->kv_pairs, dict->num_kvs * sizeof(KV_Pair));
    printf("realloc passed \n");

    dict->kv_pairs[dict->num_kvs].value = 1;

    return 0;
}

int Dict_find_key(Dict* dict, char key){

    for(int i = 0; i < dict->num_kvs; i++) {
        char cur_key = dict->kv_pairs[i].key;
        if(cur_key == key) {
            return i;
        }
    }

    return -1;
}

int Dict_increment_or_add_key(Dict* dict, char key) {

    int key_index = Dict_find_key(dict, key);

    if(key_index == -1) {
        Dict_add_key(dict, key);
    } else {
        dict->kv_pairs[key_index].value++;
    }


}

int* Dict_get_values_array (Dict* dict) {
    int* to_return = malloc(dict->num_kvs * sizeof(int));

    for(int i = 0; i < dict->num_kvs; i++) {
        to_return[i] = dict->kv_pairs[i].value;
    }

    if(dict->num_kvs > 26) {
        printf("more than 26 kvs: %d", dict->num_kvs);
    }

    return to_return;
}

Answer 1

当您尝试添加第一个元素时，您将 dict->num_kvs 递增到 1，然后分配一个元素。然后这一行：

dict->kv_pairs[dict->num_kvs].value = 1;

它将尝试写入 [1] 元素，而不是 [0] 元素。这是越界的。你应该使用：

dict->kv_pairs[dict->num_kvs-1].value = 1;

PS: 如果您使用的是 GCC 或 Clang，AddressSanitizer 是帮助您检测此类错误的好工具。

realloc 在简单的字典库中失败

realloc fails in simple dict library

c

memory-leaks

memory-management

heap-memory

realloc