0

My check function returns all hashtable indexes as NULL (I printed a known index of 124 and still returns NULL), despite all indexes printed correctly in load. I am not sure where exactly the problem lies. Some help would be much appreciated : )

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include <ctype.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 = 100000;

// counting the number of nodes;
unsigned long int node_count = 0;
unsigned long int *count_ptr = &node_count;

// Hash table
node *table[N];

void init_hash_table();

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //printing out a value stored at a known index
    printf("VALUE AT INDEX 124: %s\n", table[124]->word);
    
    long int index = hash(word);
    
    printf("Index: %li\n", index);
    
    node *index_ptr;
    index_ptr = table[index];
    
    printf("PTR(new):%s \n", index_ptr->word);
    printf("PTR(table):%s \n", table[index]->word);
    
    while(index_ptr != NULL)
    {
        printf("-------- Begin comparison:");
        printf("%s --- %s\n", index_ptr->word, word);
        printf("-------- End");
        
        if (strcasecmp(index_ptr->word, word) == 0)
        {
            return true;
        }
        
        index_ptr = index_ptr->next;
    }
    return false;
}

// Hashes word to a number
// Inspired by Engineering Man on YouTube
// Video link: https://www.youtube.com/watch?v=wg8hZxMRwcw&t=369s
unsigned int hash(const char *word)
{
    unsigned long int value = 1;
    unsigned int i = 0;
    unsigned int key = strlen(word);
    
    // making a duplicate to change the string to upper case
    char *duplicate = malloc(key + 1);
    strcpy(duplicate, word);
    
    for(; i < key; i++)
    {
        duplicate[i] = toupper(duplicate[i]);
        value = value * 59 + duplicate[i];
    }
    
    value = value % N;
    free(duplicate);
    return value;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (!dict)
    {
        return 1;
    }
    
    char tmp_word[LENGTH];
    char *tmp_word_ptr = &tmp_word[0];
    while(true)
    {
        int end = fscanf(dict, "%s", tmp_word);
        if (end == EOF)
        {
            return true;
        }
        
        node *ptr = malloc(sizeof(node));
        if (ptr == NULL)
        {
            unload();
            return false;
        }
        
        strcpy(ptr->word, tmp_word_ptr);
        
        
        int hash_num = hash(tmp_word_ptr);
        
        printf("LOAD copy: %s // in ptr: %s // hash value: %i\n", tmp_word_ptr, ptr-> word, hash_num);
        
        //setting all pointers to NULL
        init_hash_table();
        
        if (table[hash_num] == NULL)
        {
            table[hash_num] = ptr;
            (*count_ptr)++;
            table[hash_num]->next = NULL;
            printf("LOAD Hash table value: %s at index %i\n", table[hash_num]->word, hash_num);
        }
        else 
        {
            ptr->next = table[hash_num];
            table[hash_num] = ptr;
            (*count_ptr)++;
        }
    }
    return 0;
}

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

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

    }
    
    free(count_ptr);
    
    return true;
}

// Set hash table pointers to NULL initially
void init_hash_table()
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
}

This is what it prints out:

LOAD copy: a // in ptr: a // hash value: 124
LOAD Hash table value: a at index 124
LOAD copy: A // in ptr: A // hash value: 124
LOAD Hash table value: A at index 124
LOAD copy: and // in ptr: and // hash value: 36314
LOAD Hash table value: and at index 36314
LOAD copy: cat // in ptr: cat // hash value: 42525
LOAD Hash table value: cat at index 42525
LOAD copy: caterpillar // in ptr: caterpillar // hash value: 95300
LOAD Hash table value: caterpillar at index 95300
LOAD copy: the // in ptr: the // hash value: 2100
LOAD Hash table value: the at index 2100
LOAD copy: tree // in ptr: tree // hash value: 58779
LOAD Hash table value: tree at index 58779

MISSPELLED WORDS

VALUE AT INDEX 124: (null)
Index: 124
PTR(new):(null) 
PTR(table):(null) 
A
VALUE AT INDEX 124: (null)
Index: 42525
PTR(new):(null) 
PTR(table):(null) 
cat
VALUE AT INDEX 124: (null)
Index: 7871
PTR(new):(null) 
PTR(table):(null) 
is
VALUE AT INDEX 124: (null)
Index: 81642
PTR(new):(null) 
PTR(table):(null) 
not
VALUE AT INDEX 124: (null)
Index: 124
PTR(new):(null) 
PTR(table):(null) 
a
VALUE AT INDEX 124: (null)
Index: 95300
PTR(new):(null) 
PTR(table):(null) 
caterpillar
Segmentation fault
1

Perhaps its because table[] is being reinitialized with every word processed in the while loop? This will result in only the last word's index pointer being left in the array.

The table[] array needs to be initialized once. It should be done before the while loop starts, not inside the while loop.

As for the seg fault, well, that may be related to something else, and warrants a new question. There may be other issues, I didn't look. ;-)

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

  • 1
    thank you!! It was a stupid mistake that I should've spotted earlier... but at least now I learned something : ) – Lisa Oct 31 '20 at 21:44

You must log in to answer this question.

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