0

My program compiles, but in debug50 it seems to get caught in a loop during the first strcpy in load.

Any suggestions would be great thanks.

// Implements a dictionary's functionality

#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;

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

// Hash table
node *table[N];

// Number of words in dictionary
int word_count = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Hash word
    int index = hash(word);

    // Access linked list at index
    // Traverse along list searching for word
    for (node *tmp = table[index]; tmp != NULL; tmp = tmp->next)
    {
        if (strcasecmp(tmp->word, word) == 0)
        {
            return true;
        }
    }
    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 % N;
}


// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open dictionary file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Please enter a valid dictionary\n");
        return false;
    }

    char new_word[LENGTH + 1];

    // Read strings from file one at a time
    while (fscanf(dict, "%s", new_word) != 0)
    {
        // Allocates memory for new node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            unload();
            return false;
        }

        // Copies string to node
        strcpy(n->word, new_word);

        // Hashes word
        int index = hash(new_word);

        // Insert node into hash table at that location
        // If there is no word at the index
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;

            word_count++;

        }
        // If a list already exists
        else
        {
            n->next = table[index];
            table[index] = n;

            word_count++;
        }
    }
    fclose(dict);
    return true;
}

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

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

The program is "crashing" here while (fscanf(dict, "%s", new_word) != 0). From man fscanf [emphasis added]:

RETURN VALUE
On success, these functions return the number of input items successfully matched and assigned; this can be fewer than provided for, or even zero, in the event of an early matching failure.

The value EOF is returned if the end of input is reached before either the first successful conversion or a matching failure occurs. EOF is also returned if a read error occurs, in which case the error indicator for the stream (see ferror(3)) is set, and errno is set to indicate the error.

Program will not detect a "matching" failure, because each line in the dictionary is guaranteed by the spec to match the directive %s. The program is crashing because it continues reading the dictionary file long past EOF.

| improve this answer | |
  • Thank you. I think I must have been mixed up with a different function. I switched the while loop condition to != EOF. It now passes check50 on all but two of the tests. The program doesn't seem to handle cases when comparing the strings in check. Could you possibly point me in the right direction please? – Ewan Willsmer Jul 17 at 16:02
  • The hash function will generate different hash values for "cat" and "Cat". – DinoCoderSaurus Jul 17 at 16:22
  • I am using the same hash function and I have the same problem, if you manage to solve it could you please explain how you did it? Thanks! :) – Neus F. Jul 17 at 16:38
1

I have used the same hash function and I kept getting segmentation fault if the N had a very high value. I have spent so much time looking for the cause of the seg fault and this was it, so I explain it to you in case it happens the same in your code. :)

| improve this answer | |
  • Thank you! I've tried N values from 10000 down to 26 and still am having the same problem. – Ewan Willsmer Jul 17 at 20:13
  • 1
    In the hash function, I converted the word to lowercase and everything passes. – Ewan Willsmer Jul 18 at 9:15
  • Ok great! Thank you :) – Neus F. Jul 18 at 9:41
  • @EwanWillsmer - I'm running into the same capitalization issue since I also used djb2 for my hash table. Do you have any tips for coverting the word to lowercase in the hash function? Tolower() doesn't compile since it requires an int and atoi() - while solving the capitalization issue - eliminates the program's ability to properly handle substrings, which fails a different check haha. Thanks! – Devon yesterday
  • @Devon Try making a copy of tolower(word) in the hash function, using a for-loop and then running the hash on the copy. Hope that helps. – Ewan Willsmer yesterday

You must log in to answer this question.

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