CODEWITHSUNDEEP
cmemory-leakshashtable
MiguelD
MiguelD

Reputation: 449

Hashtable leaking memory

I made a hashtable, and it runs fine, but when i run it with valgrind,it tells me there is memory leaks when creating the hashtable and a memory leak for every user insertion, 12 bytes per insertion and 40 for creating the hashtable

here is some testable code:

#include <malloc.h>
#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#define initial_size 5

typedef struct user_pos {
    char nick[6];
    int position_in_file;
}user_pos;

typedef struct bucket{
    user_pos *info;
}bucket;

typedef struct hashtable{
    int size;
    int elements;
    bucket **buckets;
}hashtable;


unsigned hash(char *s) {
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval;
}

hashtable * create() {
    hashtable *htable;
    if((htable = malloc(sizeof(hashtable))) == NULL)
        return NULL;
    if((htable->buckets = malloc(sizeof(bucket) * initial_size)) == NULL)
        return NULL;
    htable->size = initial_size;
    htable->elements = 0;
    for(int i=0; i < initial_size; i++){
        htable->buckets[i] = NULL;
    }
    return htable;
}


void insert(hashtable *hashtable, char *nick, int position_in_file){
    int hash_value = hash(nick);
    int new_position = hash_value % hashtable->size;
    if (new_position < 0) new_position += hashtable->size;
    int position = new_position;
    while (hashtable->buckets[position] != NULL && position != new_position - 1) {
        if(hashtable->buckets[position]->info != NULL){
            position++;
            position %= hashtable->size;
        }else{
            break;
        }
    }
    hashtable->buckets[position] = malloc(sizeof(bucket));
    hashtable->buckets[position]->info = malloc(sizeof(user_pos));
    strcpy(hashtable->buckets[position]->info->nick, nick);
    hashtable->buckets[position]->info->position_in_file = position_in_file;
    hashtable->elements++;

}

void delete_hashtable(hashtable *ht) {
    for(int i = 0; i<ht->size; i++){
        if(ht->buckets[i] != NULL && ht->buckets[i]->info != NULL)
            free(ht->buckets[i]);
    }
    free(ht);
}

int main(){

    hashtable *ht = create();
    insert(ht, "nick1", 1);
    insert(ht, "nick2", 2);
    delete_hashtable(ht);

    return 0;
}

I am initializing a bucket everytime i insert a new item, but i think i cant free it after, because that would erase what was just added, the same for the create() function.

How do i avoid leaking memory in this case?

Thanks in advance.

Upvotes: 2

Views: 456

Answers (1)

dbush
dbush

Reputation: 223992

The memory leak is not in your allocation function but in the cleanup. You fail to free everything you allocated in delete_hashtable.

You clean up ht->buckets[i] and ht, but fail to clean up ht->buckets[i]->info and ht->buckets. You need to free those as well:

void delete_hashtable(hashtable *ht) {
    for(int i = 0; i<ht->size; i++){
        if(ht->buckets[i] != NULL && ht->buckets[i]->info != NULL)
            free(ht->buckets[i]->info);
            free(ht->buckets[i]);
    }
    free(ht->buckets);
    free(ht);
}

Also, you're allocating the wrong number of bytes for htable->buckets:

if((htable->buckets = malloc(sizeof(bucket) * initial_size)) == NULL)

Each element is a bucket *, not a bucket, so that's the size you should use:

if((htable->buckets = malloc(sizeof(bucket *) * initial_size)) == NULL)

Or better yet:

if((htable->buckets = malloc(sizeof(*htable->buckets) * initial_size)) == NULL)

That way it doesn't matter what the type of htable->buckets is or if you change it later.

Upvotes: 2

Related Questions