0

So when I originally wrote my code for the dictionary.c, I forgot to create the header nodes for each 'bucket' in the hash table. It ran well when every first node of each linked list had a letter, but it keeps failing the check50's since (it seems) check50 doesn't load a full dictionary with a word for each letter of the alphabet. I learned the segfault was because the line in unload() which checks if the next node in a linked list is NULL would run start with nodes that never even existed, thus the first table[i]->next has no value since it itself doesn't exist. Line 102-107 is where I tried to add a head to each table[i], but it keeps on segfaulting(the terminal's output below).

What am I doing wrong, and how can I fix this segfault?

$ ./speller dictionaries/small texts/cat.txt
Segmentation fault

Here is my 'small.txt'

cat
caterpillar

Here is my 'cat.txt'

A cat is not a caterpillar.

// Implements a dictionary's functionality

#include <stdbool.h>
#include <strings.h>
#include <string.h>
#include "dictionary.h"



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

//head of each 'bucket' in the hash table
node *head = NULL;

// Number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

//Global Number of Words Loaded
int dcount = 0;
int firstWord[26]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    
    // TODO
    //1.Hash to obtain a hash value
    //printf("Hashing %s....\n", word);
    int index = hash(word);
    if(firstWord[index]==0)
    {
        return false;
    }
    //2.Access the linked list at that index in the hash table
    node *cursor = table[index];
    //3.Traverse the linked list, looking for the word(strcasecmp)
    while(true)
    {
        if(strcasecmp(word, cursor->word)==0)
        {
            return true;
        }
        else
        {
            if(cursor->next !=NULL)
            {
                cursor = cursor->next;
                
            }
            else
            {
                return false;
            }
        }
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //It has been proven that this function can return an appropriate hash value: a=0, b=1, ect ect
    //DONE
    //The Concept: each index of this array corresponds to a letter of the alphabet, starting from 0.
    //The way this hash function works is that it checks to see which index the word it is given belongs to.
    //Implementation:

    //1)Cast the 1st character as an ascii value(cast to int), first with the lowercase being checked.
    //2)Check if the value is even a letter
    if((int)word[0]>64 && (int)word[0]<91)
    {
        int index = (int)word[0] - 65;
        //3)Subtract a certain amount which matches the ascii value to the index
        //5)that value is the hash value for the word
        return index;
    }
    //4)Subtract a different amount if it is capital
    if((int)word[0]>96 && (int)word[0]<123)
    {
        int index = (int)word[0] - 97;
        //3)Subtract a certain amount which matches the ascii value to the index
        //5)that value is the hash value for the word
        return index;
    }

    return 0;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    int k = 0;
    while(k <25)
    {
        table[k] = head;
        k++;
    }
    //printf("Load Function Running\n");
    //DONE: This function can successfully load a dictionary into a hash table

    //Open file into pointer ptr
    FILE *ptr = fopen(dictionary, "r");
    if(ptr == NULL)
    {
        return false;
    }

    while(true)
    {
        size();
        //It has been proven that this section WILL load the next word through each iteration.
        //LOAD NEW WORD
        char tWord[LENGTH];
        int r = fscanf(ptr, "%s", tWord);
        if( r == EOF)
        {
            //printf("Displaying contents in 'z'\n");
            node *cursor = table[25];
            while (false)
            {
                printf("-%s\n", cursor->word);
                if(cursor->next!=NULL)
                {
                    cursor = cursor->next;
                }else
                {
                    break;
                    
                }
                
            }
            
            return true;
        }

        //APPEND TO LINKED LIST
        node *nptr = malloc(sizeof(tWord));
        if(nptr == NULL)
        {
            printf("QUIT: nptr is NULL, returning 1\n");
            return false;
        }
        nptr->next=NULL;
        strcpy(nptr->word, tWord);
        int index = hash(tWord);
        
        node *tptr = table[index]->next;
        nptr->next = tptr;
        table[index]->next=nptr;
        firstWord[index]=1;
        
    }
    //Test if read properly
    printf("load function terminated.\n");
    return false;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    //printf("dcount = %i\n", dcount);
    dcount++;
    return dcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //return false;
    // TODO
    for(int i = 0; i <= 25; i++)
    {
        node *cursor = table[i];
        int j=0;
        //if(i==25){printf("Z!\n");}
        while (true)
        {
            //if(i==25){printf("NEW WORD!\n");}
            j++;
            free(table[i]);
            if(i==0){printf("NEW WORD! : table.[i]->word == '%s'\n", table[i]->word);}
            
            if(table[i]->next != NULL)
            {
                //cursor = cursor->next;
                table[i]=table[i]->next;
                cursor = table[i]->next;
            }
            else
            {
                break;
            }
                    
        }
        if(i==25)
        {
            return true;
        }
    }
    return false;
}
1

For starters, you can't free table[i] and two lines later try to access table[i]->next. It no longer exists. That's where the seg fault comes from.

This unload code is needlessly complicated. I would suggest throwing it out and starting fresh. The pseudocode is simple.

Is the pointer null?  If yes, terminate the loop.
Save the ->next pointer.
delete the current pointer.
move the next pointer into the current pointer. 
lather, rinse and repeat. ;-)

Create two temp vars. Start by setting them to table[i]. Let's call them A and B. Create a loop that terminates when one becomes null. The mechanism of the pseudocode looks something like this, although I'm not giving you the specifics. You need to work that out.

B=A
A=A->next
free B

I believe there's an entire video somewhere that goes through all this.

Some programming notes.

Get rid of head. It was a tool used to explain something in the lecture, but it's redundant as used here. It's only purpose here is to hold the value NULL. Instead, just loop across the table[] array and set them all to NULL directly.

Best and worst practice: While loop. If you have a while(true) loop, there's almost a 100% chance that you did something wrong. A while(true) loop is something that is intended to run forever, like an OS daemon. A perfect example is the code that runs in the background watching for mouse input or keyboard input. As long as the computer is running, this should keep running too.

In regular, non-OS, non-mission critical programming, this is almost always a bad practice, especially if there's a break statement. The while statement should test for whatever condition is leading to the break statement and terminate the loop accordingly.

This is also a good indicator that the code is more complex than necessary and should be simplified. Needlessly complex or convoluted code often leads to software bugs. There's an old saying in coding, "K.I.S.S -- Keep It Simple, Stupid!" Something I've learned the hard way over many years!

Oh, and is it possible that some of your limits of <25 should be <26?

This'll get you going. It's not everything, but it's a start. Happy programming! ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Love the help man, appreciate it lots! Oct 22 '20 at 2:07

You must log in to answer this question.

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