时间戳

首页 > 解决方案 > 哈希表泄漏内存

c - 哈希表泄漏内存

问题描述

我制作了一个哈希表，它运行良好，但是当我使用它运行它时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()函数也是如此。

在这种情况下如何避免内存泄漏？

提前致谢。

标签： cmemory-leakshashtable

解决方案

内存泄漏不在您的分配函数中，而是在清理中。您无法释放您分配的所有内容delete_hashtable。

您清理ht->buckets[i]and ht，但未能清理ht->buckets[i]->infoand 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)

每个元素都是 a bucket *，而不是 a bucket，所以这是您应该使用的大小：

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

或者更好：

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

htable->buckets这样，无论是什么类型或稍后更改它都无关紧要。

推荐阅读