cstructhashmapdynamic-memory-allocationfree

Freeing memory for dynamically allocated hashmap with structs as values - C


I have followed a few tutorials for hashmaps in c. From the code you can probably tell I relied heavily on this implementation which has a nice follow up video where he revisits it to show how he would free the hashmap link.

My problem is I can't seem to remove my memory leaks when creating and destroying my hashmap. I have inserted the memory leak function that visual studio provides but I can't seem to get it to tell me which line the leak occured in I just get:

Detected memory leaks!
Dumping objects ->
{89} normal block at 0x0000026818DA0E80, 8 bytes long.
 Data: <    h   > E0 0D DA 18 68 02 00 00 
Object dump complete.

I understand I probably malloced the wrong sized thing for a certain variable but I have spent a few days looking through the code and can't seem to find it.

I get another memory leak when using my insert function - HashMapInsert() within hashmap.c:

Detected memory leaks!
Dumping objects ->
{95} normal block at 0x000001CBB57C0DE0, 8 bytes long.
 Data: <        > CD CD CD CD CD CD CD CD 
{89} normal block at 0x000001CBB57C10B0, 8 bytes long.
 Data: <  |     > 90 12 7C B5 CB 01 00 00 
Object dump complete.

I have a feeling it is my struct entry->next pointer but I have tried to free that in the freeEntry() function within hashmap.c and the leaks persist. Any help would be much appreciated.

Below is an minimal reproducible example (i think). I have tried free(hmp->entries) near the end of the HashMapDelete function but that errors out (heap corruption error). I have also tried free(e->next) in the freeEntry function with no luck. I think the issue is to do with the calloc within the HashMapCreate but I do not know what to change to test a different way than whats implemented.

hashmap.h

#pragma once
#ifndef HASHMAP_H
#define HASHMAP_H

#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <inttypes.h>

typedef struct entry {
    char* key;
    double* value;
    struct entry* next;
} entry;

typedef struct hashmap {
    size_t* size;
    entry** entries;
} hashmap;

uint64_t HashMapHash(char* key, size_t size);
hashmap* HashMapCreate(size_t size);
bool HashMapInsert(hashmap* hmp, char* key, double value);
void HashMapPrint(hashmap* hmp);
void HashMapDelete(hashmap* hmp);

#endif`

hashmap.c

#include "hashmap.h"

hashmap* HashMapCreate(size_t size) {
    printf("\nHello Hash World!!!");

    hashmap* hmp = malloc(sizeof(hashmap*));

    if (hmp == NULL) {
        return NULL;
    }

    hmp->size = malloc(sizeof(size_t));

    if (hmp->size == NULL) {
        return NULL;
    }

    *hmp->size = size;

    hmp->entries = calloc(*hmp->size, sizeof(entry*));

    return hmp;
}

uint64_t HashMapHash(char* key, size_t size) {
    
    uint64_t hashVal = 1;

    for (int i = 0; i < strlen(key); i++) {
        hashVal += key[i];
        hashVal = (hashVal * key[i]) % size;
    }

    return hashVal;
}

bool HashMapInsert(hashmap* hmp, char* key, double value) {
    if (hmp == NULL || key == NULL) {
        return false;
    }

    entry* tmp = HashMapGet(hmp, key);

    if (tmp != NULL) {
        return false;
    }

    uint64_t idx = HashMapHash(key, *hmp->size);

    entry* e = malloc(sizeof(entry));

    if (e == NULL) {
        return false;
    }

    e->key = malloc(strlen(key)+1);

    if (e->key == NULL) {
        free(e);
        return false;
    }
    printf("\nSize of %s: %zu", key, strlen(key));
    strcpy_s(e->key, strlen(key) + 1, key);

    e->value = malloc(sizeof(double));

    if (e->value == NULL) {
        free(e->key);
        free(e);
        return false;
    }

    *e->value = value;

    e->next = malloc(sizeof(entry*));

    if (e->next == NULL) {
        free(e->key);
        free(e->value);
        free(e);
        return false;
    }

    e->next = hmp->entries[idx];
    hmp->entries[idx] = e;

    return true;
}

void freeEntry(entry* e) {
    free(e->value);
    free(e->key);
    //free(e->next);
    free(e);
}

void HashMapPrint(hashmap* hmp) {

    entry* node = NULL;

    printf("\nStart");
    for (int i = 0; i < *hmp->size; i++) {
        printf("\n[%-3d]: ", i);
        node = hmp->entries[i];
        while (node != NULL) {
            printf("%-10s | ", node->key);
            node = node->next;
        }
    }
    printf("\nEnd");
}

void HashMapDelete(hashmap* hmp) {
    if (hmp == NULL) {
        return;
    }

    entry* tmp = NULL;

    for (int i = 0; i < *hmp->size; i++) {

        while (hmp->entries[i] != NULL) {
            tmp = hmp->entries[i];
            hmp->entries[i] = hmp->entries[i]->next;
            freeEntry(tmp);
        }

        free(hmp->entries[i]);
    }

    HashMapPrint(hmp);

    free(hmp->entries);
    free(hmp->size);
}

main.c

#define _CRTDBG_MAP_ALLOC

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <inttypes.h>
#include <string.h>
#include <crtdbg.h>

#include "HashMapLib/hashmap.h"

int main() {

    size_t size = 10;
    
    hashmap* hmp = HashMapCreate(size);

    HashMapDelete(hmp);

    _CrtDumpMemoryLeaks();
}

Solution

  • One leak is because of these two lines:

    e->next = malloc(sizeof(entry*));
    
    // ...
    
    e->next = hmp->entries[idx];
    

    The first line allocates memory, and assigns the result to e->next. Then the next line overwrites e->next with another pointer. That makes you loose the original pointer.

    The simple solution is to remove the first line, with the allocation.


    The allocation is also flawed because it allocate memory for the size of a pointer, not the size of the structure itself. Something you seem to have done in other places as well.

    All in all, you use too many pointers and too much dynamic allocation, in places where it's not needed.