Блог

Я прошу прощения за длинный фрагмент кода впереди, но я потратил много времени на просмотр здесь, и я чувствую, что ничто из того, что я видел до сих пор, не может помочь мне решить эту проблему. Я задавал вопросы на форумах курса, помогал TAs и получал предложения от друзей, и ничто не смогло устранить корень моей проблемы здесь.

В этой программе я использую дерево для создания средства проверки орфографии. В моем коде есть много вещей, которые необходимо исправить, но утечка памяти — единственная, с которой мне действительно нужна помощь, чтобы разобраться.

Проблема в том, что я совершенно уверен, что выделяю правильное количество места для своих узлов, и я думаю, что Valgrind подтверждает это, потому что у меня есть только 2 не освобожденных блока (из 365 371 выделенных).

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

 /**
c* Implements a dictionary's functionality.
*/
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// number of characters we are using (a-z and ')
#define LETTERS 27

// max guaranteed number of nonnegative char values that exist
#define CHARVALUES 128

// create node structure for trie
typedef struct node
{
    struct node *children[LETTERS];
    bool is_word;
}
node;

// create root node for trie
node *root;

// stores the size of our dictionary
unsigned int dict_size = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // keeps track of where we are; starts with root for each new word
    node *current_node = root;

    while (*word != '')
    {

        // indices: 'a' -> 0, ..., 'z' -> 25, '' -> 26
        int index = (tolower(*word) - 'a') % CHARVALUES;
        if (index >= LETTERS - 1)
        {
            // by assumption, the char must be ''' if not 'n' or a letter
            index = LETTERS - 1;
        }

        // if the node we need to go to is NULL, the word is not here
        if (current_node->children[index] == NULL)
        {
            return false;
        }

        // go to the next logical node, and look at the next letter of the word
        current_node = current_node->children[index];
        word  ;
    }
    return current_node->is_word;
}

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

    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        return false;
    }

    // allocate memory for the root node
    root = malloc(sizeof(node));

    // store first letter (by assumption, it must be a lowercase letter)
    char letter = fgetc(inptr);

    // stores indices corresponding to letters
    int index = 0;

    /**
     * we can assume that there is at least one word; we will execute the loop
     * and assign letter a new value at the end. at the end of each loop, due
     * to the inside loop, letter will be a newline; we know the EOF in the
     * dictionary follows a newline, so the loop will terminate appropriately
     */
    do
    {
        // keeps track of where we are; starts with root for each new word
        node *current_node = root; 

        // this loop will only execute if our character is a letter or '''
        while (letter != 'n')
        {
            // indices: 'a' -> 0, ..., 'z' -> 25, '' -> 26
            index = (letter - 'a') % CHARVALUES;
            if (index >= LETTERS - 1)
            {
                // by assumption, the char must be ''' if not 'n' or a letter
                index = LETTERS - 1;
            }

            // allocate memory for a node if we have not done so already
            if (current_node->children[index] == NULL)
            {
                current_node->children[index] = malloc(sizeof(node));

                // if we cannot allocate the memory, unload and return false
                if (current_node->children[index] == NULL)
                {
                    unload();
                    return false;
                }

            }

            // go to the appropriate node for the next letter in our word
            current_node = current_node->children[index];

            // get the next letter
            letter = fgetc(inptr);
        }

        // after each linefeed, our current node represents a dictionary word
        current_node->is_word = true;
        dict_size  ;

        // get the next letter
        letter = fgetc(inptr);
    }
    while (letter != EOF);

    fclose(inptr);

    // if we haven't returned false yet, then loading the trie must have worked
    return true;
}

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

void clear(node *head)
{
    for (int i = 0; i < LETTERS; i  )
    {
        if (head->children[i] != NULL)
        {
            clear(head->children[i]);
        }
    }
    free(head);
}

    /**
     * Unloads dictionary from memory. Returns true if successful else false.
     */
    bool unload(void)
    {
        clear(root);
        return true;
    }
  

Соответствующий вывод valgrind выглядит следующим образом:

 ==18981== HEAP SUMMARY:
==18981==     in use at exit: 448 bytes in 2 blocks
==18981==   total heap usage: 365,371 allocs, 365,369 frees, 81,843,792 bytes allocated
==18981== 
==18981== 448 (224 direct, 224 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011B0: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:40)
==18981== 
==18981== LEAK SUMMARY:
==18981==    definitely lost: 224 bytes in 1 blocks
==18981==    indirectly lost: 224 bytes in 1 blocks
==18981==      possibly lost: 0 bytes in 0 blocks
==18981==    still reachable: 0 bytes in 0 blocks
==18981==         suppressed: 0 bytes in 0 blocks
==18981== 1 errors in context 3 of 11:
==18981== 
==18981== 
==18981== Invalid read of size 8
==18981==    at 0x40120C: load (dictionary.c:123)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 4 of 11:
==18981== Invalid read of size 8
==18981==    at 0x4011E0: load (dictionary.c:114)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 5 of 11:
==18981== Invalid write of size 8
==18981==    at 0x4011D4: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
==18981== 
==18981== 
==18981== 1 errors in context 6 of 11:
==18981== Invalid read of size 8
==18981==    at 0x4011B2: load (dictionary.c:109)
==18981==    by 0x4008CD: main (speller.c:41)
==18981==  Address 0xb3fde70 is 16 bytes before a block of size 224 alloc'd
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011CB: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:41)
  

Итак, моя интерпретация этого вывода заключается в том, что в следующем блоке кода:

         if (current_node->children[index] == NULL)
        {
            current_node->children[index] = malloc(sizeof(node));

            // if we cannot allocate the memory, unload and return false
            if (current_node->children[index] == NULL)
            {
                unload();
                return false;
            }

        }
  

malloc оператор (который действительно является словарем строк.c: 111) выполняется дважды, так что выделенная память никогда не освобождается. (Это правильно?) Теперь это наводит меня на мысль, что настоящая проблема заключается в моей функции clear, то есть в том, что она написана плохо и не очищает каждый узел моего дерева.

Тем не менее, я часами смотрел на код и буквально не вижу в нем ничего плохого. (Я уверен, что много; Я просто не слишком хорош в этом.)

Любая помощь в этом была бы весьма признательна.

В качестве примечания: у меня было несколько человек (не сотрудников курса), которые говорили мне, что я должен инициализировать все мои указатели в дочернем массиве на NULL, но сотрудники курса прямо сказали мне, что это необязательно, и я уже протестировал оба способа с одинаковыми результатами. Я знаю, что это, вероятно, проблема переносимости, даже если она технически «работает» таким образом, но просто знайте, что это не то решение, которое я ищу, поскольку я знаю, что есть какая-то другая основная причина (т. Е. Та, Из-за которой она вообще не работает ни на одном устройстве …)

Опять же, если вы можете каким-либо образом помочь с тем, что не так с моей логикой здесь, я был бы очень признателен. Я пытался разобраться в этом часами, но безрезультатно.

 root = malloc(sizeof(node));
  

Это дает фрагмент неинициализированной памяти.

 if (current_node->children[index] == NULL)
  

Здесь вы предполагаете, что память была инициализирована, в то время как на самом деле это мусор.

Вам необходимо инициализировать содержимое root перед их использованием или, в качестве альтернативы, использовать calloc, чтобы установить их все равными нулю.

После переключения обоих операторов malloc() с помощью calloc() (как предлагали другие; это устраняет ваши многочисленные ошибки valgrind), добавления небольшого примерного словаря и следующего минималистичного main():

 int main() {

    load("dict.txt");

    printf("Checked: %in", check("hello"));
    printf("Checked: %in", check("sdfsdf"));

    unload();

    return 0;
}
  

… ваш код выполняется намного чище и без каких-либо утечек памяти:

 ==636== HEAP SUMMARY:
==636==     in use at exit: 0 bytes in 0 blocks
==636==   total heap usage: 15 allocs, 15 frees, 42,688 bytes allocated
==636==
==636== All heap blocks were freed -- no leaks are possible
==636==
==636== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 8)
  

Однако у вас будет одна очевидная утечка, если вы вернете false из load() — вы не освободите указатель на файл.

Редактировать: Valgrind начинает выдавать всевозможные ошибки (снова), когда вы вводите слова в верхнем регистре в словарь. Поэтому сосредоточьте свои усилия на отладке там.