dictionary.c - pset5 segmentation fault

Question

// Implements a dictionary`'s functionality

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

// Number of buckets in hash table = 26 raised to 4.
const unsigned int N = 456976;

//keep track of number of nodes in hash table.
int nodes = 0;

// Hash table
node *table[N];

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

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash_code = 0;
    unsigned int count;

    //case insensitive.
    char buffer[LENGTH + 1];
    strcpy(buffer,word);

    for (int i = 0, s = strlen(word); i < s; i++)
    {
        buffer[i] = tolower(buffer[i]);
    }

    //hash function.
    for(count = 0; word[count] != '\0'; count++)
    {
        hash_code = word[count] + (hash_code << 6) + (hash_code << 16) - hash_code;
    }
    return (hash_code % N);
}

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

    char word[LENGTH + 1];
    while(fscanf(file,"%s", word) != EOF)
    {
        //creating a new node.
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
           free(n);
           return false;
        }
        strcpy(n->word, word);

        //obtain hash code.
        int index = hash(word);

        //insert into hash table.
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
        }

        nodes++;
        free(n);
    }
    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node *tmp = NULL;
    node *cursor = NULL;

    //iterating over each linked list in the hash table.
    for(int i = 0; i < N; i++)
    {
        //freeing all node in that linked list.
        while(cursor-> != NULL)
        {
            cursor = table[i];
            tmp = cursor;
            cursor = cursor->next;
            free (tmp);
        }
        if (table[i] != NULL)
        {
            return false;
        }
    }
    return true;
 }

Answer 1

The first big problems I see are in check(). Look at this line:

while(cursor->next != NULL)

This is going to result in every other node being skipped, among other anomalies. It should be checking cursor, not cursor->next. I'll let you figure out why. Next, there's the two free(cursor) statements in the check function. Even though you created a pointer, it doesn't mean it should be freed. The cursor pointer is a temporary holder of the addresses in the tree. If you free it after loading an address from the tree, you're going to break the linked list in the tree.

Next, unload simply does nothing. Look at this code.

node *tmp = NULL;
node *cursor = NULL;

//iterating over each linked list in the hash table.
for(int i = 0; i < N; i++)
{
    //freeing all node in that linked list.
    while(cursor->next != NULL)

Isn't the value of cursor == null? IF cursor == null then cursor->next doesn't even exist! Also, this is the same problem of checking next instead of cursor.

Maybe cursor should be assigned an address, say from an array somewhere? ;-)

There may be other issues, but this will get you started.

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