Утечка памяти в реализации хеш-таблицы - PullRequest
Новая
       15

Утечка памяти в реализации хеш-таблицы

1 голос
/ 24 февраля 2012

Я реализовал структуру хеш-таблицы следующим образом (читает все слова из текстовых файлов, создает хеш-таблицу и затем печатает все значения таблицы в одной строке): 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int hashf(const char *buf, size_t len) {
    unsigned int h = 0;
    size_t i;
    for (i = 0; i < len; i++) {
        h += buf[i];
        h += h << 10;
        h ^= h >> 7;
    }
    h += h << 3;
    h ^= h >> 11;
    h += h << 15;
    return h;
}

void destroy_hash(char *hashtable[], int table_size) {
    int i;
    for (i=0; i<table_size; i++) {
        if (hashtable[i]) {
            free(hashtable[i]);
        }
    }
}

int main(int argc, char *argv[])
{
    if (argc != 3) {
        printf("Invalid parameters!\n");
        return EXIT_FAILURE;
    }
    const char *filename = argv[1];
    int table_size = atoi(argv[2]);

    char *hashtable[table_size];
    int i;
    for (i = 0; i < table_size; i++) {
        hashtable[i] = NULL;
    }
    unsigned int h, h_k;

    FILE *fileread = fopen(filename, "r");

    char *key;
    char buf[100];
    int probe_nro, word_nro = 0;

    if (fileread) {

        fscanf(fileread, "%99s", buf);
        key = malloc((strlen(buf)+1)*sizeof(char));
        memcpy(key, buf, strlen(buf) + 1);
        while(!feof(fileread)) {
            // Increase word_nro by 1
            word_nro += 1;
            if (word_nro <= table_size) {
                h = hashf(key, strlen(buf)) % table_size;
                if (!hashtable[h]) {
                    hashtable[h] = key;
                }
                else {
                    // Begin probing
                    probe_nro = 1;
                    // Save original hash to h_k:
                    h_k = h;

                    h = (h_k+(probe_nro*probe_nro)) % table_size;

                    while (hashtable[h] && (probe_nro <= 10000)) {
                        probe_nro += 1;
                        h = (h_k+(probe_nro*probe_nro)) % table_size;
                    }
                    // If no vacancy found after 10000 probes, return error
                    if (probe_nro == 10000) {
                        printf("Error: table full\n");
                        free(key);
                        destroy_hash(hashtable, table_size);
                        return(1);
                    }
                    hashtable[h] = key;
                }
                fscanf(fileread, "%99s", buf);
                if (!feof(fileread)) {
                    key = malloc((strlen(buf)+1)*sizeof(char));
                    memcpy(key, buf, strlen(buf) + 1);
                }
            }
        else {
            free(key);
            printf("Error: table full\n");
            destroy_hash(hashtable, table_size);
            return(1);
        }
    }
    for (i=0; i < table_size; i++) {
        if (hashtable[i]) {
            printf("%s", hashtable[i]);
        }
        else {
            printf(" ");
        }
        if (i < table_size - 1) {
            printf(",");
        }
    }
    printf("\n");
    destroy_hash(hashtable, table_size);
}
else    {
    printf("Can't open file!\n");
    return(1);
}
return(0);
}

Я не могу найти утечку памяти, которая обозначена в valgrind как: общее использование кучи: 7 выделений, 6 освобождений, выделение 604 байта все еще достижимо: 568 байтов в 1 блоках

Можете ли вы заметить, что я все еще должен освободить, или что я делаю неправильно? Большое спасибо.

Ответы [ 2 ]

1 голос
/ 24 февраля 2012

В этой строке 

if (!feof(fileread)) {
    key = malloc((strlen(buf)+1)*sizeof(char));
    memcpy(key, buf, strlen(buf) + 1); // <--
}

Вы заставляете key указывать на новое местоположение, не освобождая старую память, выделенную вам malloc. Должно быть 

if (!feof(fileread)) {
    free(key); // <--
    key = malloc((strlen(buf)+1)*sizeof(char));
    memcpy(key, buf, strlen(buf) + 1);
}
0 голосов
/ 24 февраля 2012 
void destroy_hash(char *hashtable[], int table_size) {
    int i;
    for (i=0; i<table_size; i++) {
        if (hashtable[i]) {
            free(hashtable[i]);
            hashtable[i] = NULL; /* this one ? */
        }
    }
}
...