0

Good morning, I have segmentation fault on my dictionary.c code, I was trying to find a Typ0 mistake or variable declaration mistake but I can not find anyone. Also I can not find logic errors, so I do not understand where is my mistake, can someone help me to find my mistake please?.

// 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 = 75;
unsigned int CounterOfWords = 0;
unsigned int hashindex = 0;

// Hash table
node *table[N];

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

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    // This hash return the sum of the values from the first 3 characters of the word

    int aux1 = strlen(word);
    if(aux1 < 3)
    {
        for(int i = 0; i<aux1 ;i++)
        {
            hashindex  = hashindex + (toupper(word[i]) - 'A');
        }
    }else
    {
        for(int i = 0; i<3; i++)
        {
            hashindex  = hashindex + (toupper(word[i]) - 'A');
        }
    }
    return hashindex;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *file = fopen(dictionary,"r");
    if(file == NULL)
    {
        return false;
    }

    char word[LENGTH+1];

    while(fscanf(file,"%s",word)==1)
    {
        hashindex = hash(word);
        node* temp = malloc(sizeof(node));
        if(temp == NULL)
        {
            return 1;
        }
        strcpy(temp->word,word);
        temp->next = table[hashindex];
        table[hashindex]=temp;
        CounterOfWords++;
    }
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    if(CounterOfWords > 0)
    {
        return CounterOfWords;
    }
    return 0;
}

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

        if(i == N-1 && table[i] == NULL)
        {
            return true;
        }
    }
    return false;
}

1 Answer 1

0

It's definitely a logic error.

Questions:

  1. What are the hash values being generated by the hash function?
  2. What's the value of N? Remember, N is the number of elements in the dictionary array table[N].
  3. What prevents the hash value that's returned from being larger than N?

If you need more help, post a comment.

[EDIT]

This is a great example of why it is usually a very bad practice to use global variables! I missed it originally because I didn't dig really deep on why the hash value being returned was too big, just that it was. (I don't want to take all the fun from people that are still learning. ;-) )

Note that hashindex is a GLOBAL variable! That means that it is a permanent variable as long as this program is running. Why is that significant? Each time that the hash function is executed, hashindex will retain whatever value it is assigned even after the hash function ends. Global vars are persistent throughout the run of the program. They don't reset automatically at any point.

That means that hashindex starts off with the value that it had from the last time the hash function was called. Letter values are just being added and added to it. That means that it has potentially no limit to how large it will grow, other than an overflow condition for it's data type.

So, let's assume that the actual hash values for the first 3 words in the dictionary are supposed to be 45, 40 and 50. This code would return a hash of 45 for the first word, 45+40 = 85 for the second word and 85+50 = 135 for the third, and so on. This is well beyond the N limit of 75. Even if N were something limitless, the next problem is that the hash function is no longer deterministic, meaning that it will never produce the same result for the same word.

Side note/lesson. Because of the way C works, those values above 75 may or may not trigger a seg fault. C will allow indexing of an array beyond it's end, provided that it's still within the memory space. (It has it's history in the creation of the language and the processing of contatenated strings.) So, it's likely that something like 76 would keep running, but would grab whatever data happened to follow the array in physical memory, while a hash of 486 is more likely to produce a seg fault.

Now, if hashindex had been declared as a local var inside of the hash function, as it should, then its value would be returned to the calling function, and the variable would be destroyed at the end of each run and recreated at the start of the next run.

The very important lesson here is to avoid using globals if at all possible. It's a useful tool when appropriate, but should be avoided if at all possible! If there's a really good reason to do so, then do it, but the urge to create a global should be a really, really big red flag to make absolutely sure it is necessary! In general, and almost universally, it's a bad practice. It can lead to hidden bugs, data corruption and just headaches all around, as you just saw. Globals just make it too easy for mistakes to creep into code that otherwise looks just fine.

Interestingly, this program also demonstrates a case where it is appropriate - CounterOfWords. ;-)

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

8
  • Thank yo for your reply. regarding to your questions: 1.- the sum of the first 3 characters on the word. 2.- I modified N equal to 75, as if i sum z +z +z i will have 75. 3.- as i modified the value of N, it should not be greater than N. Commented May 3, 2023 at 14:13
  • please edit the question and add the entire code.
    – Cliff B
    Commented May 3, 2023 at 21:54
  • that is my entire code Commented May 3, 2023 at 23:06
  • Oops, my bad. Two in a row on the same topic. Only yours had full code. See edited answer. ;-)
    – Cliff B
    Commented May 3, 2023 at 23:34
  • thanks for your reply. I fixed it but on my hash code I had to write "return hashindex % 75" in order to work. Somehow even if I define N as a number bigger than 75, I got segment fault, so I had to put the "%75". can you explain me that please?. I thought that on the speller.c code there was some kind of restriction but I could not find it. Commented May 4, 2023 at 3:29

You must log in to answer this question.

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