CS50 问题集 5 Speller：Valgrind 问题 - 条件跳转或移动取决于未初始化的值

Question

我已经运行我的程序通过 check50 并得到以下输出：

:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:) handles most basic words properly
:) handles min length (1-char) words
:) handles max length (45-char) words
:) handles words with apostrophes properly
:) spell-checking is case-insensitive
:) handles substrings properly
:( program is free of memory errors
    valgrind tests failed; rerun with --log for more information.

valgrind 测试日志显示：

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpud3boltd -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 125)

最后一行引用的代码是这个函数中的if语句，用于递归删除我的哈希表中的链表：

// Destroy function deletes an entire linked list recursively

void destroy(struct node* list)
{
    // Initialise current node pointer to point to head of list
    node* current = list;
    // Recursion base case
    if (current == NULL)
    {
        return;
    }
    destroy(current->next);
    free(current);
}

由以下函数调用：

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        if (hashtable[i] == NULL)
        {
            continue;
        }
        destroy(hashtable[i]);
    }
    return true;
}

当我运行 valgrind 自己时，我得到以下输出：

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

MISSPELLED WORDS

==10541== Conditional jump or move depends on uninitialised value(s)
==10541==    at 0x401429: destroy (dictionary.c:127)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x4014A4: unload (dictionary.c:144)
==10541==    by 0x400ED9: main (speller.c:152)
==10541==  Uninitialised value was created by a heap allocation
==10541==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541==    by 0x401325: load (dictionary.c:85)
==10541==    by 0x400A34: main (speller.c:40)
==10541== 
==10541== Conditional jump or move depends on uninitialised value(s)
==10541==    at 0x401429: destroy (dictionary.c:127)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x4014A4: unload (dictionary.c:144)
==10541==    by 0x400ED9: main (speller.c:152)
==10541==  Uninitialised value was created by a heap allocation
==10541==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541==    by 0x401325: load (dictionary.c:85)
==10541==    by 0x400A34: main (speller.c:40)
==10541== 
==10541== Conditional jump or move depends on uninitialised value(s)
==10541==    at 0x401429: destroy (dictionary.c:127)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x401440: destroy (dictionary.c:131)
==10541==    by 0x4014A4: unload (dictionary.c:144)
==10541==    by 0x400ED9: main (speller.c:152)
==10541==  Uninitialised value was created by a heap allocation
==10541==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541==    by 0x401325: load (dictionary.c:85)
==10541==    by 0x400A34: main (speller.c:40)
==10541== 

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.46
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       0.25
TIME IN TOTAL:        1.72

==10541== 
==10541== HEAP SUMMARY:
==10541==     in use at exit: 0 bytes in 0 blocks
==10541==   total heap usage: 143,096 allocs, 143,096 frees, 8,023,416 bytes allocated
==10541== 
==10541== All heap blocks were freed -- no leaks are possible
==10541== 
==10541== For counts of detected and suppressed errors, rerun with: -v
==10541== ERROR SUMMARY: 40053 errors from 3 contexts (suppressed: 0 from 0)

Asking for help...

==10541== Conditional jump or move depends on uninitialised value(s)

Looks like you're trying to use a variable that might not have a value? Take a closer look at line 127 of dictionary.c.

关于我哪里出错的任何想法？我认为自从我初始化 current 以列出这应该不是问题。我尝试在 list 之前将 current 初始化为 NULL，但这没有任何区别。

*编辑

添加了完整代码，因为 valgrind 测试引用了其他行：

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Keep track of number of words in dictionary
int dict_size = 0;

// Number of buckets in hash table
const unsigned int HASHTABLE_SIZE = 65536;

// Declare Hash table
node *hashtable[HASHTABLE_SIZE];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Make lowercase copy of word (so resulting index from hash function will match)
    int n = strlen(word);
    char word_copy[n+1];
    for (int i = 0; i < n; i++)
    {
        word_copy[i] = tolower(word[i]);
    }
    // Add NULL terminating character to lowercase copy of word
    word_copy[n] = '[=15=]';
    // Hash lowercase word to obtain index
    int hash_index = hash(word_copy);
    // Create pointer to node that points to the linked list at that element
    node* trav = hashtable[hash_index];
    // Traverse/search linked list for desired word
    while (trav != NULL)
    {
        if (strcasecmp(trav->word, word_copy) == 0)
        {
            return true;
        }
        trav = trav->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash = 0;
    for(int i = 0, n = strlen(word); i < n; i++)
    {
        hash = (hash << 2) ^ word[i];
    }
    return hash % HASHTABLE_SIZE;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Open dictionary.h file
    FILE* dict_ptr = fopen(dictionary, "r");
    // Check to see if dictionary.h file pointer is NULL
    if (dict_ptr == NULL)
    {
        fprintf(stderr, "Error: Could not open %s", dictionary);
        return false;
    }
    // Create array of chars into which we can temporarily store each
    char buffer[LENGTH + 1];
    // Loop over whole to copy each string until we reach end of file (EOF)
    while (fscanf(dict_ptr, "%s", buffer) != EOF)
    {
        // Create temporary node for current word
        node* current = malloc(sizeof(node));
        // Check if pointer to temporary node equals NULL
        if (current == NULL)
        {
            return false;
        }
        // Copy current word into string field of node
        strcpy(current->word, buffer);
        // Implement hash function on current word to obtain hash table index value for current word
        int index = hash(buffer);
        // Add current word node to hashtable array
        // If there are no nodes at that element, simply add node to that element
        if (hashtable[index] == NULL)
        {
            hashtable[index] = current;
            dict_size++;
        }
        // Else add current node to beginning of linked list at that element
        else
        {
            current->next = hashtable[index];
            hashtable[index] = current;
            dict_size++;
        }
    }
    fclose(dict_ptr);
    return true;
}

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

// Destroy function deletes an entire linked list recursively

void destroy(struct node* list)
{
    // Initialise current node pointer to point to head of list
    node* current_node = list;
    // Recursion base case
    if (current_node == NULL)
    {
        return;
    }
    destroy(current_node->next);
    free(current_node);
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        if (hashtable[i] == NULL)
        {
            continue;
        }
        destroy(hashtable[i]);
    }
    return true;
}

Answer 1

如果你看一下 load:

    node* current = malloc(sizeof(node));
    // Check if pointer to temporary node equals NULL
    if (current == NULL)
    {
        return false;
    }
    // Copy current word into string field of node
    strcpy(current->word, buffer);
    // Implement hash function on current word to obtain hash table index value for current word
    int index = hash(buffer);
    // Add current word node to hashtable array
    // If there are no nodes at that element, simply add node to that element
    if (hashtable[index] == NULL)
    {
        hashtable[index] = current;
        dict_size++;
    }
    // Else add current node to beginning of linked list at that element
    else
    {
        current->next = hashtable[index];
        hashtable[index] = current;
        dict_size++;
    }

您为 current 分配 space，然后将字符串复制到 word。但是，如果列表不为空，则只能设置 next。当它为空时，您永远不会设置 next。因此，当您稍后遍历列表时，您正在读取一个未初始化的值。

在这种情况下您还需要设置 next:

    // Add current word node to hashtable array
    // If there are no nodes at that element, simply add node to that element
    if (hashtable[index] == NULL)
    {
        current->next = NULL;
        hashtable[index] = current;
        dict_size++;
    }
    // Else add current node to beginning of linked list at that element
    else
    {
        current->next = hashtable[index];
        hashtable[index] = current;
        dict_size++;
    }

这里注意，每个case的做法都是一样的，可以合并一下：

    // Add current word node to hashtable array
    current->next = hashtable[index];
    hashtable[index] = current;
    dict_size++;

CS50 问题集 5 Speller：Valgrind 问题 - 条件跳转或移动取决于未初始化的值

CS50 Problem Set 5 Speller: Valgrind issue - Conditional jump or move depends on uninitialised value(s)

c

valgrind

hashtable

cs50