0

I get a seg fault when running the code below. I ran GDB and what I can tell is that it works well when the word I look for is in the dictionary (e.g. this), but that it does not work when the word is wrong (e.g. thiss). In the latter case when I watch the expression trav->word in GDB I get "No value". When it then starts the do while loop it crashes. I think it has something to do with the way I have initialised the hash table and loaded it into memory. Jus to be sure I will post that code below.

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // Point to hashed location
    char* search_word = malloc(sizeof(char[LENGTH + 1]));
    strcpy(search_word, word);
    int key = hash_it(search_word);
    free(search_word);
    node* trav = hashtable[key];

    // Check word and return true if match
    do
    {
        if(strcmp(word, trav->word) == 0)
        {
            return true;
        }
        else
        {
            trav = trav->next;
        }
    }
    while(trav->next != NULL);

    // word not found
    return false;
}

Here is my code outside of the functions in the dictionary file

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// define size of hashtable & max lenght of word
#define HASHTABLE_SIZE 65536
#define LENGHT 45

// global variables
typedef struct node
{
    char word[LENGHT + 1];
    struct node* next;
}
node;

node* hashtable[HASHTABLE_SIZE];
int count_words = 0;

// prototype
int hash_it(char* word);

And here is my load function. I thought I had to point all node pointers in my hashtable array to NULL or is that the problem? But then if I do not set the pointers to NULL, then I may have garbage values in the pointers that can lead me to read into memory where I should not be right? Many thanks in advance, CB

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // open dictionary
    FILE* inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    // buffer
    char buffer[LENGHT + 1];

    // initialize all pointers in hashtable to NULL
    for(int i = 0; i < HASHTABLE_SIZE; i++)
    {
        hashtable[i] = NULL;
    }

    // store each word in table
    while(fscanf(inptr, "%s", buffer) == 1)
    {
        // make new node & insert read word
        node* new_node = malloc(sizeof(node));
        new_node->next = NULL;
        strcpy(new_node->word, buffer);

        // hash the word
        int key = hash_it(buffer);

        // set pointer of new node to the head of the list
        new_node->next = hashtable[key];

        // set pointer of indexed location to new node
        hashtable[key] = new_node;

        // add 1 to dictionary counter
        count_words++;
    }
    return true;
}
0

It looks like the problem is the do/while loop in check(). Remember that a do/while loop is guaranteed to execute at least once. If the hashtable entry is null, then that first pass is going to result in a seg fault when trav = trav->next; is executed. Instead, maybe a while loop instead of a do/while loop would be more appropriate?

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

1
  • Thanks Cliff, that does the job! Where my chain of thought was wrong is in the fact that the hash table does not hold nodes, but only pointers to nodes. Now I get it. – CB Nuji Jun 1 '16 at 21:17

You must log in to answer this question.

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