CS50 拼写器内存泄漏

Question

经过大量工作后，我已经让拼写器开始工作，它编译并运行正确，但是当我通过 valgrind 运行它时，我遇到了很多内存泄漏。我检查了我的代码，但没有发现任何问题。什么可能导致内存泄漏？免费没有按预期工作吗？

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <strings.h>
#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];
//Count words when written in hashtable
int wordcount = 0;
// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Hashes word for comparing
    int cmp = hash(word);
    //Access linked list based on hashtable index
    node* point = table[cmp];
    //Check if word is on linked list
    while (point != NULL)
    {
        if (strcasecmp(point->word, word) == 0)
        {
            return true;
        }
        point = point->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //Hashfunction source: https://study.cs50.net/hashtables
    //Hash on first letter of string
    int hash = toupper(word[0]) - 'A';
    return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Opens file in read mode
    FILE *file =fopen(dictionary,"r");
    //Checks if there actually is a file
    if (file == NULL)
    {
        return false;
    }
    char word[LENGTH + 1];
    //Iterate through file while checking if end of file has not been reached
    while(fscanf(file, "%s",word) != EOF)
    {
        //Creates new node
        node* n = malloc(sizeof(node));
        //Checks if node is NULL
        if (n == NULL)
        {
            return false;
        }
        //Copy word from dictionary to hashtable
        strcpy(n->word, word);
        //Hashes word to determine index
        int h = hash(n->word);
        //Inserts word on linked list
        n->next = table[h];
        table[h] = n;
        wordcount++;
    }
    return  true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //Indicates which linked list is currently being freed
    int list = 0;
    for (int i = 0; i < N;i++)
    {
        //Access linked list based on cmp
        node* cursor = table[list];
        node* tmp = cursor;
        while (cursor != NULL)
        {
        cursor = cursor->next;
        free(tmp);
        node* tpm = cursor;
        }
        list++;
    }
    return true;
}

Valgrind 错误消息

~/pset5/speller/ $ valgrind ./speller texts/cat.txt
==1749== Memcheck, a memory error detector
==1749== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1749== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==1749== Command: ./speller texts/cat.txt
==1749== 

MISSPELLED WORDS

==1749== Invalid free() / delete / delete[] / realloc()
==1749==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x40126A: unload (dictionary.c:106)
==1749==    by 0x400E09: main (speller.c:152)
==1749==  Address 0x56e9670 is 0 bytes inside a block of size 56 free'd
==1749==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x40126A: unload (dictionary.c:106)
==1749==    by 0x400E09: main (speller.c:152)
==1749==  Block was alloc'd at
==1749==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x401172: load (dictionary.c:69)
==1749==    by 0x400964: main (speller.c:40)
==1749== 

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.23
TIME IN check:        0.04
TIME IN size:         0.00
TIME IN unload:       0.11
TIME IN TOTAL:        1.38

==1749== 
==1749== HEAP SUMMARY:
==1749==     in use at exit: 8,012,192 bytes in 143,066 blocks
==1749==   total heap usage: 143,096 allocs, 143,095 frees, 8,023,416 bytes allocated
==1749== 
==1749== 552 bytes in 1 blocks are still reachable in loss record 1 of 3
==1749==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x5258E49: __fopen_internal (iofopen.c:65)
==1749==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==1749==    by 0x40112E: load (dictionary.c:58)
==1749==    by 0x400964: main (speller.c:40)
==1749== 
==1749== 8,010,184 bytes in 143,039 blocks are indirectly lost in loss record 2 of 3
==1749==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x401172: load (dictionary.c:69)
==1749==    by 0x400964: main (speller.c:40)
==1749== 
==1749== 8,011,640 (1,456 direct, 8,010,184 indirect) bytes in 26 blocks are definitely lost in loss record 3 of 3
==1749==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1749==    by 0x401172: load (dictionary.c:69)
==1749==    by 0x400964: main (speller.c:40)
==1749== 
==1749== LEAK SUMMARY:
==1749==    definitely lost: 1,456 bytes in 26 blocks
==1749==    indirectly lost: 8,010,184 bytes in 143,039 blocks
==1749==      possibly lost: 0 bytes in 0 blocks
==1749==    still reachable: 552 bytes in 1 blocks
==1749==         suppressed: 0 bytes in 0 blocks
==1749== 
==1749== For counts of detected and suppressed errors, rerun with: -v
==1749== ERROR SUMMARY: 143066 errors from 2 contexts (suppressed: 0 fr

om 0)

Answer 1

首先，你的加载函数是错误的。让我们一步步从 while 循环开始：

我们扫描第一个字
创建 node* n 并对其进行 malloc
检查 n 是否不为空
将单词从文件复制到n
创建h来存储单词的哈希值
设置 n->next = table[h] 其中 table[h] 当前等于 NULL

如何解决这个问题（为了方便我更改了一些变量名称）：

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary){

    //Data holds a single dictionary word
    char data[LENGTH + 1];

    //Open dictionary file
    FILE* list = fopen(dictionary, "r");
    if(list == NULL){
        printf("File is missing.\n");
        return 1;
    }

    while(fscanf(list, "%s", data) != EOF){
        //Store word in a node
        node *new_word = malloc(sizeof(node));
        if(new_word == NULL){
            return 1;
        }

        strcpy(new_word->word, data);
        new_word -> next = NULL; //We want to initially set it to null incase this is the first word in table[hash_index]

        //hash word to obtain hash value
        int hash_index = hash(data);

        //insert node into hashtable at that location
        if(table[hash_index] == NULL){ 
            table[hash_index] = new_word;
        }
        else{
            new_word -> next = table[hash_index];
            table[hash_index] = new_word;
        }
        num_words++;
    }
    fclose(list); //Make sure to add this as this will erase the `reachable` error in valgrind
    return true;
}

此外，这只是提高生活质量，但您将 unload() 更改为：

for(int i = 0; i < N; i++){
        while(table[i] != NULL){
            node *tmp = table[i] -> next;
            free(table[i]);
            table[i] = tmp;
        }
    }

CS50 拼写器内存泄漏

CS50 Speller memory leak

c

memory-leaks

cs50