0

I have been all day trying to find the bug in my problem but I find it impossible. The program runs correctly at first but the misspelled words are not the ones expected, and then suddenly there is a segmentation fault that I don't know where it comes from. Maybe the problem is the hash function, I have copied it from the internet and I don't really understand how it works. I am so frustrated and I would really appreciate it if someone could help me.

// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.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;

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

// Hash table
node *table[N];

int *counter;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int index = hash(word);
    node *trav = table[index];
    while (trav != NULL)
    {
        if (strcasecmp(trav->word, word) == 0)
        {
            return true;
        }
        else
        {
            trav = trav->next;
        }
    }
    return false;
}

// Hashes word to a number, code from http://www.cse.yorku.ca/~oz/hash.html 
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c;

    while (c = *word++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Initialize the counter to 0 (to count the words in the dictionary)
    int c = 0;
    
    //Opens the file
    FILE* ptr = fopen(dictionary, "r");
    if (ptr == NULL)
    {
        printf("Not enough memory\n");
        return false;
    }
    
    char buff[LENGTH + 1];
    while (fscanf(ptr, "%s", buff) != EOF)
    {
        //create node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("Not enough memory\n");
            return false;
        }
        
        //copy node to the buffer
        strcpy(n->word, buff);
        
        //hash the word
        int index = hash(buff);
        
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
        }
        c++;

    }
    
    //if we have arrived to the end of the file, return true
    if (feof(ptr) == true)
    {
        return true;
        *counter = c;
    }
    return false;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *temp = table[i]->next;
        node *cursor = table[i]->next;
        while (cursor != NULL)
        {
            cursor = cursor->next;
            free(temp);
            temp = cursor;
        }
    }
    return true;
}

Thank you :)

2

Here's what I see.

First, the seg fault is happening here:

    if (table[index] == NULL)

The problem is the value of index. It's way too large. The cause is back in the hash function. Although it's a great hash function, it has to be edited slightly. The return value MUST be limited to the maximum size of the table[] array. This is done by using a modulo operation:

return hash % N;

Next, the code is using the int POINTER counter to count words. Unfortunately, no memory was ever allocated to it. That's going to cause seg faults. Why not just declare an int instead of an int pointer?

Programming tip: When deciding whether to use a standard var or a pointer var, consider what it's being used for. If it's something that's well defined, a regular variable is probably in order. For example, if you're creating a single integer that will be used over and over, make it an int. Need a buffer of a fixed length? That's well defined too, so create an array of appropriate size and type. BUT, if you're doing something that's dynamic, like creating nodes or other structs to be added to a linked list, then use a pointer and allocate memory to it as needed.

Then, the unload function is generating seg faults too. This one is a little more complicated because it needs some recoding. The first problem I spotted there is in this line:

    node *temp = table[i]->next;

Something like this has a very high likelihood of creating a seg fault because it assumes that table[i]->next actually exists. The problem is this: if table[i] is NULL, then the struct doesn't exist, so table[i] doesn't exist. Trying to access something that doesn't exist always generates a seg fault.

Perhaps you should be assigning table[i] instead?

Finally, let's look at the end of load():

//if we have arrived to the end of the file, return true
if (feof(ptr) == true)
{
    return true;
    *counter = c;
}
return false;

The if statement is unnecessary. For the code to get here, the code would have had to get to the EOF on the input file.

Next, the line*counter = c; will never execute. It's impossible to get to it because of the return statement on the previous line. When a return statement executes, program execution immediately terminates processing of the function. No further code in the function will be executed and control transfers back to the code that called the function.

Also, the return false; statement is another line of code that simply will never execute, except under the most adverse error condition (which I can't think of, off the top of my head.) If the input file doesn't open, the code executes the first return statement. If it does, then the dictionary is processed and code continues down to the return true; statement at which point the function ends. There's no path where the code gets here.

In short, everything in that code snipet can be deleted, except for return true;

There may be more issues, but these are the major ones.

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

  • Wow this was super helpfull!! Thank you soo much! Now when I tried to compile again the code, I have seen there is an error in the hash function: – Neus F. Jul 17 '20 at 8:17
  • while (c = *word++) – Neus F. Jul 17 '20 at 8:17
  • I guess it is because we have to write == instead of =, does this make sense? – Neus F. Jul 17 '20 at 8:18
  • Or maybe I have to initialize the variable c to a vaue? – Neus F. Jul 17 '20 at 8:20
  • The code in the hash function is correct. It uses some advanced techniques to do certain things very efficiently and quickly with minimal code. This function could be rewritten to make more sense to new programmers, but doing that would seriously impact the code's efficiency. Just stick with the way it's written. However, you would do well to eaxmine the code carefully. Break it down and figure out exactly what each step does and how it does it. I believe that if you search google for the source of the code, you'll also find some more in depth explanation of how it works. – Cliff B Jul 17 '20 at 9:08
1

Your code seems to be good.

Don't put a check condition at the end of load function, I think segfault being is caused due to this just close the file after exiting while-loop

fclose(fp);

Also I noticed you didn't declare a global counter at the top of the program so that you just have to counter++ inside your load function and return its value inside size function.

If I helped you be sure to tick the answer to keep other smiling too 😃.

You must log in to answer this question.

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