I made the speller program from problem set 5 and it does everything right except for some memory error, which I am not able to solve. My code is as follows:
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
int words = 0;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// TODO
node *ptr = table[hash(word)];
while (ptr != NULL)
{
if (strcasecmp(word, ptr->word) == 0)
{
return true;
}
ptr = ptr->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
return toupper(word[0]) - 'A';
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open the dictionary file
FILE *source = fopen(dictionary, "r");
if(source == NULL)
{
return false;
}
char *buffer = malloc(LENGTH + 1);
if (buffer == NULL)
{
return false;
}
// Read each word in the file
while(fscanf(source, "%s", buffer) != EOF)
{
// Add each word to the hash table
node *ptr = table[hash(buffer)];
node *new_entry = malloc(sizeof(node));
table[hash(buffer)] = new_entry;
new_entry->next = ptr;
strcpy(new_entry->word, buffer);
words++;
}
// Close the dictionary file
fclose(source);
free(buffer);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return words;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// TODO
node *tmp = NULL, *ptr = NULL;
for (int i = 0; i < N; i++)
{
if (table[i] != NULL)
{
ptr = table[i];
while (ptr != NULL)
{
tmp = ptr;
free(ptr);
ptr = tmp->next;
}
}
}
return true;
}
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
int words = 0;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// TODO
node *ptr = table[hash(word)];
while (ptr != NULL)
{
if (strcasecmp(word, ptr->word) == 0)
{
return true;
}
ptr = ptr->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
return toupper(word[0]) - 'A';
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open the dictionary file
FILE *source = fopen(dictionary, "r");
if(source == NULL)
{
return false;
}
char *buffer = malloc(LENGTH + 1);
if (buffer == NULL)
{
return false;
}
// Read each word in the file
while(fscanf(source, "%s", buffer) != EOF)
{
// Add each word to the hash table
node *ptr = table[hash(buffer)];
node *new_entry = malloc(sizeof(node));
table[hash(buffer)] = new_entry;
new_entry->next = ptr;
strcpy(new_entry->word, buffer);
words++;
}
// Close the dictionary file
fclose(source);
free(buffer);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return words;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// TODO
node *tmp = NULL, *ptr = NULL;
for (int i = 0; i < N; i++)
{
if (table[i] != NULL)
{
ptr = table[i];
while (ptr != NULL)
{
tmp = ptr;
free(ptr);
ptr = tmp->next;
}
}
}
return true;
}
The error Valgrind gave to me was as follows:
==49523==
==49523== HEAP SUMMARY:
==49523== in use at exit: 0 bytes in 0 blocks
==49523== total heap usage: 143,097 allocs, 143,097 frees, 8,023,302 bytes allocated
==49523==
==49523== All heap blocks were freed -- no leaks are possible
==49523==
==49523== For lists of detected and suppressed errors, rerun with: -s
==49523== ERROR SUMMARY: 143091 errors from 1 contexts (suppressed: 0 from 0)
Asking for help...
/home/ubuntu/.local/share/help50/cs50/helpers/helpers/_common.py:1: SyntaxWarning: invalid escape sequence '\/'
FILE_PATH = "(?:(?:.*)\/(?:[^/]+)\/)?"
/home/ubuntu/.local/share/help50/cs50/helpers/helpers/valgrind.py:81: SyntaxWarning: invalid escape sequence '\d'
"are definitely lost in loss record [\d,]+ of [\d,]+$", line)
==49523== Invalid read of size 8
==49523== at 0x109B52: unload (dictionary.c:104)
==49523== by 0x10970F: main (speller.c:153)
Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look
at line 104 of dictionary.c.
Line 104 is the line 'ptr = tmp->next' in the unload function near the last. At line 104, I am running a loop to free all memory from a linked list. In the past programs, I used a very similar loop for freeing the memory. Free the current node, while storing its next node's address in a temporary node and then repeating the same process with the next node.
The problem is here:
tmp = ptr;
free(ptr);
ptr = tmp->next;
The problem is that the assignment tmp = ptr does not create a copy of the node that ptr is pointing to, it only creates a copy of the pointer. The value stored in ptr.
That means you will have two pointers, ptr and tmp, pointing to the exact same object in memory.
When you then call free(ptr), both of those pointers become invalid, and dereferencing either of them (like you do with tmp->next) will lead to undefined behavior.
The solution is rather simple: Change the order in which you do things:
tmp = ptr;
ptr = tmp->next;
free(tmp);