Pset5 (Speller) 奇怪的 Valgrind 内存错误，没有泄漏

Question

我已经阅读了有关 pset5 Valgrind 内存错误的其他线程，但这对我没有帮助。我得到 0 次泄漏，但这是：

==1917== 条件跳转或移动取决于未初始化的值看起来您正在尝试使用可能没有值的变量？仔细看一下dictionary.c.

的第34行

错误指的是第 34 行：lower[i] = tolower(word[i]);

为了提供上下文，下面的代码会尝试检查词典中是否存在已上传到散列 table 的单词。我试图将想要的单词转换为小写，因为所有字典单词也是小写的，因此它们的哈希值是相同的。该程序成功完成了所有任务，但随后偶然发现了这些内存错误。

关于 Valgrind 为什么对我生气有什么暗示吗？谢谢！

 // Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lower[LENGTH + 1]; 

   //Converts word to lower so the hashes of the dictionary entry and searched word would match
    for (int i = 0; i < LENGTH + 1; i++)
    {
        lower[i] = tolower(word[i]);
    }

    // Creates node from the given bucket
    node *tmp = table[hash(lower)];

    // Traverses the linked list
    while (tmp != NULL)
    {
        if (strcasecmp(word, tmp->word) == 0)
        {
            return true;
        }

        tmp = tmp->next;
    }

    return false;
}

下面是整个 dictionary.c 文件：

// Implements a dictionary's functionality
#include <string.h>
#include <strings.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.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 26^3
const unsigned int N = 17576;

// Hash table
node *table[N];
int count = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lower[LENGTH + 1]; 

   //Converts word to lower so the hashes of the dictionary entry and searched word would match
    for (int i = 0; i < LENGTH + 1; i++)
    {
        lower[i] = tolower(word[i]);
    }

    // Creates node from the given bucket
    node *tmp = table[hash(lower)];

    // Traverses the linked list
    while (tmp != NULL)
    {
        if (strcasecmp(word, tmp->word) == 0)
        {
            return true;
        }

        tmp = tmp->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Modified hash function by Dan Berstein taken from http://www.cse.yorku.ca/~oz/hash.html
    unsigned int hash = 5381;
    int c;

    while ((c = *word++))
    {
        hash = (((hash << 5) + hash) + c) % N; /* hash * 33 + c */
    }

    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *inptr = fopen(dictionary, "r");

    if (dictionary == NULL)
    {
        printf("Could not load %s\n.", dictionary);
        return false;
    }

    // Create a char array to temporarily hold the new word (r stands for read)
    char r_word[N+1];

    // Until the end of file
    while (fscanf(inptr, "%s", r_word) != EOF)
    {
        // Increments count
        count++;

        // Create a node
        node *new_node = malloc(sizeof(node));

        if (new_node == NULL)
        {
            unload();
            return false;
        }

        strcpy(new_node->word, r_word);

         // Hash the node
        int index = hash(new_node->word);
        // Places the node at the right index
        new_node->next = table[index];
        table[index] = new_node;
    }

    fclose(inptr);

    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (&load == false)
    {
        return '0';
    }
    else
    {
        return count;
    }

}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Interates over the array
    for (int i = 0; i < N; i++)
    {
        node *head = table[i];

        while (head != NULL)
        {
            node *tmp = head;
            head = head->next;
            free(tmp);
        }
    }

    return true;
}

Answer 1

此循环遍历 word-

的 最大长度

for (int i = 0; i < LENGTH + 1; i++)
{
    lower[i] = tolower(word[i]);
}

除非你看看 word 是如何创建的-

while (fscanf(inptr, "%s", r_word) != EOF)
{
    // Increments count
    count++;
    // Create a node
    node *new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        unload();
        return false;
    }
    strcpy(new_node->word, r_word);

注意，变量 r_word 的长度可能不完全 LENGTH + 1。所以你在word中真正拥有的是N个字符，其中N是不一定LENGTH + 1，它可能更少。

因此，对于比 LENGTH + 1 短的单词，遍历整个 0 -> LENGTH + 1 会出现问题。你正在遍历没有值的数组槽，它们有垃圾值。

有什么解决办法？这正是 c 字符串具有 [=21=]-

的原因

for (int i = 0; word[i] != '[=12=]'; i++)
{
    lower[i] = tolower(word[i]);
}

这将在到达 NULL 字符时立即停止循环，您一定已经知道，它标记字符串的结尾 - 也就是 char 数组。

您的代码中可能还有更多错误。但是对于您的特定问题 - 越界阅读就是答案。

Pset5 (Speller) 奇怪的 Valgrind 内存错误，没有泄漏

Pset5 (Speller) Weird Valgrind memory errors, no leaks

valgrind

cs50