CS50 PSET5-Speller：运行Valgrind时出现Invalid read错误求助

First off, that Valgrind error is telling you exactly what you suspect: your code is trying to read 1 byte of memory it shouldn't have access to. The issue almost certainly ties back to how cursor->word is stored or referenced in your hash table nodes. Let's break down the most likely causes and how to fix them:

Common Causes & Fixes #

1. cursor->word isn't properly NUL-terminated #

The strcasecmp function reads characters until it hits a \0 (NUL) byte. If your node's word array doesn't end with this terminator, strcasecmp will keep reading past the end of the array into memory that doesn't belong to you—triggering Valgrind's error.

How to fix:

• First, double-check your node struct definition. Make sure the word array has enough space for the longest possible word plus the NUL terminator:

  // Example: if LENGTH is the max word length in your dictionary
  typedef struct node {
      char word[LENGTH + 1]; // +1 for the '\0'
      struct node *next;
  } node;
  

• When copying words into nodes (in your load function), explicitly add the NUL terminator, even if you use strncpy (which doesn't always add it automatically):

  // Instead of just strncpy(new_node->word, dict_word, LENGTH);
  int word_len = strlen(dict_word);
  // Cap the length to avoid overflow
  if (word_len > LENGTH) word_len = LENGTH;
  strncpy(new_node->word, dict_word, word_len);
  new_node->word[word_len] = '\0'; // Force the terminator
  

2. Your hash function returns an invalid index #

If hash(word) spits out an index that's outside the bounds of your hash_table array, hash_table[hash(word)] will point to memory that's not part of your hash table. This gives you a "wild pointer," and accessing cursor->word from that pointer is an illegal memory read.

How to fix:

• Add debug checks to verify the hash index is valid. For example, in your check function:

  bool check(const char *word) {
      int index = hash(word);
      // Add an assertion to catch invalid indices during testing
      assert(index >= 0 && index < HASH_TABLE_SIZE); // Define HASH_TABLE_SIZE as your table's size
      node *cursor = hash_table[index];
      // ... rest of your code
  }
  

• Audit your hash function to ensure it always returns a value between 0 and HASH_TABLE_SIZE - 1. Common mistakes here include forgetting to mod the final hash value by the table size.

3. Node memory is corrupted elsewhere #

It's possible that the memory for your node (or its word array) was corrupted in another part of your code—like in the load function when allocating or writing to nodes. For example:

• Allocating too little memory for a node (e.g., malloc(sizeof(node*)) instead of malloc(sizeof(node)))
• Writing past the end of the word array in load (e.g., copying a word longer than LENGTH without truncating)

How to debug:

• Run Valgrind with the --track-origins=yes flag to get more details about where the invalid memory originated:

  valgrind --leak-check=full --track-origins=yes ./your_speller_program
  

  This will show you if the bad memory was allocated in load, or if it's the result of an out-of-bounds write elsewhere.

Quick Test to Isolate the Issue #

To confirm it's the NUL terminator issue, you can temporarily modify your check function to print the length of cursor->word (using strlen—if strlen returns a value longer than your LENGTH constant, that's proof the terminator is missing):

while (cursor != NULL) {
    printf("cursor->word: '%s', strlen: %zu\n", cursor->word, strlen(cursor->word));
    if (strcasecmp(cursor->word, word) == 0) {
        return true;
    }
    cursor = cursor->next;
}

If strlen returns something way too big, that's a dead giveaway the terminator is missing.

内容的提问来源于stack exchange，提问作者Drazer