0

This is how I've implemented my load function:

bool load(const char* dictionary)
{
    // Open file
    FILE* input = fopen(dictionary, "r");
    if (input == NULL)
    {
        return false;
    }

    for (int i = 0; i < SIZE; i++)
    {
        hashtable[i] = NULL; 
    }

    // Hashing each word and storing it until end of file is reached
    while (true)
    {
        // Allocate memory for each word
        node* new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            unload();
            fclose(input);
            return false;
        }

        // Word into hash function
        if (fscanf(input, "%45s", new_node -> word) != EOF)
        {
            free(new_node);
            break;
        }
        unsigned int n = hash(new_node -> word);

        new_node -> next = hashtable[n] -> next;
        hashtable[n] -> next = new_node;

        ctr++;
    }

    if (ferror(input))
    {
        unload();
        fclose(input);
        return false;
    }

    fclose(input);
    return true;
}
2

TL; DR:

Change

if (fscanf(input, "%45s", new_node -> word) != EOF)  

to

if (fscanf(input, "%45s", new_node -> word) == EOF)

and

new_node -> next = hashtable[n] -> next;
hashtable[n] -> next = new_node;  

to

new_node -> next = hashtable[n];
hashtable[n] = new_node;

Too Many Words:

Firstly, it seems the conditions are flipped on the if statement, causing it to produce an empty dictionary, not a segfault:

    if (fscanf(input, "%45s", new_node -> word) != EOF)

should be:

    if (fscanf(input, "%45s", new_node -> word) == EOF)

Once this is fixed, the segfault will occur. this is because of how nodes are added to the list:

Each element in the hashtable is initialized to NULL. It seems logical that hashtable[n]->next would be NULL as well, but unfortunately, this is not necessarily the case. You haven't shared your node struct, so let's assume it looks like this:

struct node
{
    char word[LENGTH + 1];
    struct node* next;
}

A struct is just a bunch of things sitting next to each other in memory. When we define a struct, the key information we are giving the computer is the name of each element and its size. I like to picture it like a freight train, with each car as one byte. When we define the struct, essentially we are saying, the first 46 cars are for this thing called word, and then the next 4 bytes are for a pointer called next which points to another node. Then whenever we malloc a struct, we're just asking for a place in memory where we can fit a 50 car train, and malloc gives us the address of the first car (first char in the word). Because the computer is stupid, this means if we set the hashtable[n] to NULL and ask for hashtable[n]->next, the computer imagines a train starting at 0x0 and tries to bust into the 46th - 50th cars, which don't actually contain that pointer, and actually are probably part of a totally different train.

In the above example, if hashtable[n] = NULL:

  • hashtable[n] = 0x0
  • hashtable[n]->word = (*hashtable[n]).word = 0x0 + 0 (it's the first thing in the struct)
  • hashtable[n]->next = (*hashtable[n]).next = 0x0 + sizeof(hashtable[n]->word) = 0x0 + 46 = 0x2E

As seen above, the way that pointer arithmetic plays out, we ended up trying to access 0x2E which is not accessible and certainly doesn't contain a pointer to a node. This is where you are getting a segfault. Here's what it looks like on gdb:

(gdb) run austinpowers.txt
Starting program: /home/jharvard/Dropbox/pset5/speller austinpowers.txt  

Program received signal SIGSEGV, Segmentation fault.
0x08049203 in load (dictionary=0x80493c2 "/home/cs50/pset5/dictionaries/large") at dictionary.c:117
117         new_node -> next = hashtable[n] -> next;
(gdb) p hashtable[n]
$1 = (node *) 0x0
(gdb) p hashtable[n]->word
Cannot access memory at address 0x0
(gdb) p hashtable[n]->next
Cannot access memory at address 0x30 (in the middle of where it thinks the 4 byte next pointer is)

So what you actually want is to make your new_node -> next to point to the hashtable[n] node itself:

    new_node -> next = hashtable[n];

Then, once you have new_node pointing to where the next item in the list is, you can just replace hashtable[n] with the new_node:

    hashtable[n] = new_node;

These few small changes seem to make the code work properly.

Hope that helps

| improve this answer | |
  • This worked like a charm! Thanks so much for your detailed and comprehensive answer, Sam, I really feel like I understand this much better conceptually now. – serenasos Oct 22 '15 at 14:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .