realloc fails in simple dict library-CodePudding

I wrote a lightweight dictionary for a quick project with C, and I am getting the error: realloc(): invalid next size. I know this means my heap is corrupted somehow, but I'm not sure what I did wrong, it seems like my code is super simple.

The realloc always fails the fourth access, ie when dict->num_kvs = 4

Below is my code. It includes the dict library as well as the function that is using it. Any help would be much appreciated

Offending function:

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 (plus the struct definitions)


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;
}

CodePudding user response：

When you try to add the first element, you are incrementing dict->num_kvs to 1, then you allocate a single element. Then this line:

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

It will try to write to the [1] element, instead of [0] element. This is out of bounds. You should use:

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

PS: If you're using GCC or Clang, AddressSanitizer is a great tool to help you detect these type of bugs.