Hashtable утечка памяти - PullRequest
Новая
       9

Hashtable утечка памяти

0 голосов
/ 12 июня 2018

Я создал хеш-таблицу, и она работает нормально, но когда я запускаю ее с valgrind, она говорит мне, что при создании хеш-таблицы возникают утечки памяти и утечки памяти для каждой вставки пользователя, 12 байт на вставку и 40 длясоздание хеш-таблицы

вот некоторый тестируемый код: 

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

Я инициализирую корзину каждый раз, когда вставляю новый элемент, но думаю, что не могу освободить его после, потому что это стерло бы то, чтотолько что добавлено, то же самое для функции create().

Как мне избежать утечки памяти в этом случае?

Заранее спасибо.

1 Ответ

0 голосов
/ 12 июня 2018

Утечка памяти не в вашей функции выделения, а в очистке.Вы не можете освободить все, что вы выделили в delete_hashtable.

Вы очищаете ht->buckets[i] и ht, но не можете очистить ht->buckets[i]->info и ht->buckets.Вам также необходимо освободить их: 

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

Кроме того, вы выделяете неправильное количество байтов для htable->buckets: 

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

Каждый элемент представляет собой bucket *,это не bucket, поэтому вы должны использовать этот размер: 

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

Или еще лучше: 

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

Таким образом, не имеет значения, какой тип htable->bucketsили если вы измените его позже.

...