Работя в C проект и създадох следната реализация на хеш таблица:
typedef struct hash_record
{
char* key;
char* value;
struct hash_record* next;
}hash_record;
typedef struct hash_bucket
{
char* key;
hash_record* head_record;
}hash_bucket;
typedef struct hash_table
{
int bucket_num;
hash_bucket** hash_entry;
}hash_table;
int hash_init(hash_table** h_table, int bucket_num)
{
int i;
(*h_table) = malloc(sizeof(char)*sizeof(hash_table));
assert((*h_table) != NULL);
(*h_table)->hash_entry = malloc(sizeof(hash_bucket*) * bucket_num);
assert((*h_table)->hash_entry != NULL);
(*h_table)->bucket_num = bucket_num;
for(i = 0; i < bucket_num; i++)
{
(*h_table)->hash_entry[i] = malloc(sizeof(hash_bucket));
(*h_table)->hash_entry[i]->head_record = NULL;
(*h_table)->hash_entry[i]->key = NULL;
}
return 0;
}
int hash_destroy(hash_table** h_table)
{
int i;
hash_record* tmp_rec, *tmp_rec_2;
if((*h_table) == NULL)
{
return 0;
}
for(i = 0; i < (*h_table)->bucket_num; i++)
{
assert((*h_table)->hash_entry[i] != NULL);
tmp_rec = (*h_table)->hash_entry[i]->head_record;
while(tmp_rec != NULL)
{
assert((tmp_rec != NULL) && (tmp_rec->value != NULL));
tmp_rec_2 = tmp_rec;
tmp_rec = tmp_rec->next;
if(tmp_rec_2->value != NULL && strlen(tmp_rec_2->value) > 0 &&
tmp_rec_2->key != NULL && strlen(tmp_rec_2->key) > 0)
{
free(tmp_rec_2->value);
free(tmp_rec_2->key);
}
free(tmp_rec_2);
}
assert((*h_table)->hash_entry[i] != NULL);
free((*h_table)->hash_entry[i]);
}
free((*h_table)->hash_entry);
free((*h_table));
return 0;
}
void hash_put_value(hash_table** h_table, char* key, char* value)
{
hash_record* tmp_rec, *tmp_rec2;
assert((*h_table) != NULL);
assert((*h_table)->bucket_num > 0);
assert((*h_table)->hash_entry != 0);
assert(key != NULL && strlen((char*) key) > 0);
assert(value != NULL);
assert(strlen(value) > 0);
unsigned int bucket_no = FNVHash (key, strlen(key));
bucket_no = bucket_no % (*h_table)->bucket_num;
assert((*h_table)->hash_entry[bucket_no] != NULL);
tmp_rec = malloc(sizeof(hash_record));
tmp_rec->key = malloc(sizeof(char)*(1 + strlen(key)));
strcpy(tmp_rec->key, key);
tmp_rec->value = malloc(sizeof(char)*(1 + strlen(value)));
strcpy(tmp_rec->value, value);
tmp_rec->next = NULL;
if( (*h_table)->hash_entry[bucket_no]->head_record == NULL )
{
(*h_table)->hash_entry[bucket_no]->head_record = tmp_rec;
}
else
{
tmp_rec->next = (*h_table)->hash_entry[bucket_no]->head_record->next;
(*h_table)->hash_entry[bucket_no]->head_record = tmp_rec;
}
}
Клиентският код, който използва горната реализация, е следният:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "hash_table.h"
int main(int argc, char** argv)
{
int call_type;
int done;
hash_table* h_table;
hash_init(&h_table, 67);
char* sample_key;
int i;
hash_record* h_table_iterator;
unsigned int bucket_iterator;
for(i = 0; i < 1000; i++)
{
sample_key = malloc(sizeof(char)*(1 + strlen("key_XXXXXXX")));
sprintf(sample_key, "key_%d", i);
hash_put_value(&h_table, sample_key, sample_key);
free(sample_key);
}
hash_destroy(&h_table);
return 0;
}
Когато изпълня кода си с Valgrind, получавам следното:
db2inst1@bear:~/Documents/bigintegration/Recode-UDF$ valgrind --tool=memcheck --leak- check=yes --show-reachable=yes --num-callers=20 ./hash_test
==3031== Memcheck, a memory error detector
==3031== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==3031== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==3031== Command: ./hash_test
==3031==
==3031==
==3031== HEAP SUMMARY:
==3031== in use at exit: 37,100 bytes in 2,799 blocks
==3031== total heap usage: 4,069 allocs, 1,270 frees, 53,404 bytes allocated
==3031==
==3031== 7,354 bytes in 933 blocks are indirectly lost in loss record 1 of 3
==3031== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3031== by 0x40173C: hash_put_value (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031== by 0x40091D: main (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031==
==3031== 7,354 bytes in 933 blocks are indirectly lost in loss record 2 of 3
==3031== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3031== by 0x40178F: hash_put_value (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031== by 0x40091D: main (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031==
==3031== 37,100 (22,392 direct, 14,708 indirect) bytes in 933 blocks are definitely lost in loss record 3 of 3
==3031== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)
==3031== by 0x401705: hash_put_value (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031== by 0x40091D: main (in /home/db2inst1/Documents/bigintegration/Recode-UDF/hash_test)
==3031==
==3031== LEAK SUMMARY:
==3031== definitely lost: 22,392 bytes in 933 blocks
==3031== indirectly lost: 14,708 bytes in 1,866 blocks
==3031== possibly lost: 0 bytes in 0 blocks
==3031== still reachable: 0 bytes in 0 blocks
==3031== suppressed: 0 bytes in 0 blocks
==3031==
==3031== For counts of detected and suppressed errors, rerun with: -v
==3031== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)
Не разбирам каква е причината за изтичането на памет, уловено от Valgrind. Наистина съм загрижен за този въпрос, защото обикновено разпределям памет по този начин и вярвам, че след като Valgrind се оплаква, трябва да правя нещо нередно.
Прегледах други публикации по този въпрос, но не намерих нещо подобно на моя код. Някакви мисли, съвети, индикации какво правя погрешно?
Благодаря ти, Ник
