0

I've looked through everyone with the same problem, the common answer seems to be lower-case issues in the hash function or freeing pointers before you are actually done using them. I have tried playing around with everything I can think of in this code, but still get almost all my words as misspelled. I still believe the problem to be within my check/hash-function, as my load seemed to work fine when I checked that. Anyone have any pointers?

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.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 = 676;         // for now looking at two first letters 26*26

// Hash table
node *table[N];

// Dictionary word-counter
int dictionary_word_count = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int n = strlen(word);
    char copy_word[n + 1];
    strcpy(copy_word, word);
    char lwrcase_word[n + 1];
    for (int i = 0; i < n; i++)

    {
        lwrcase_word[i] = tolower(copy_word[i]);
    }

    int index = hash(lwrcase_word);             // hash word to find linked list's index
    node *trav = malloc(sizeof(node));  // create a node that can traverse from the start through linked list, looking for matching word.
    if (trav == NULL)
    {
        return 1;
        printf("Not enough memory");
    }

    trav->next = table[index];

        while(trav->next != NULL)
        {
            if (strcmp(trav->word, lwrcase_word) == 0)  // if match found, word is not misspelled, function returns true
            {
                return true;
            }

            trav = trav->next;          // else keep looking for a match
        }

    return false;
    }

// Hashes word to a number
// hash-function credit to http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
        unsigned long hash = 5381;
        int c;

        while ((c = *word++)) // could be - while ( assign(&c, *word++) != '\0' )
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash % N; // to keep values within hashtable
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    for(int i = 0; i < N; i++)
    {
        table[i] = NULL;              // initializing hashtable pointers, to avoid garbage values
    }

    char word[LENGTH + 1];                   // create string for word to be read into
    FILE *file = fopen(dictionary, "r");     // open dictionary

    if (file == NULL)
    {
        printf("File could not be opened\n");
        return false;
    }

    while (fscanf(file, "%s", word) != EOF)  // read one string at a time from dictionary into word array
    {

            node *n = malloc(sizeof(node)); // allocate memory for new node

            if (n == NULL)
            {
                printf("Not enough memory\n");
                return false;
            }

            int index = hash(n->word);   // find index node will be placed at with hashfunction
            strcpy(n->word, word);          // the dictionary word will be put into node
            dictionary_word_count++;        // counting words

            if (table[index] != NULL)       // if there is a collision
            {
                n->next = table[index];     // FIRST point node to the old head index was pointing at
                table[index] = n;           // then point index at node, now new head
            }

            else
            {
                table[index] = n;           // if index is empty, node is head
                n->next = NULL;
            }
    }

    return true;
    fclose(file);
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for(int i = 0; i < N; i++)
    {
        node *trav = malloc(sizeof(node));  // create two travellers that can go over hashtable
        node *tmp = malloc(sizeof(node));
        if (trav == NULL || tmp == NULL)
        {
            printf ("Memory is full!");
            return false;
        }

        trav = table[i];                    // They will both start at index of linked list
        tmp = table[i];

        while(trav != NULL)           // trav will go through list until NULL
        {                                   // tmp will free node after trav has moved on, then proceed to be in travs place
            trav = trav->next;
            free(tmp);
            tmp = trav;
        }

    }
    return true;
}

1

I can understand your frustration in resolving this. I'm guessing that you're looking for a single problem, or maybe two, and trying to get an entire complex program to work by finding and fixing that single issue. A lot of new programmers fall into that trap. You need to understand that code needs to be tested section by section. In this case, load needed to be tested and validated as working correctly before you'd be able to even start working on the larger issues in check. This is also a good indicator that some more quality time needs to be spent with the debugger.

There are a few issues to be dealt with. First, look at the following code in load():

        int index = hash(n->word);   // find index node will be placed at with hashfunction
        strcpy(n->word, word);          // the dictionary word will be put into node

How can the code determine the hash value of a word before it's been copied into n->word? Maybe you should switch the order of these two lines?

Moving on to check, there are more issues. First, in order to hash lwrcase_word, there needs to be an end of string marker, '\0', at the end of the word, but it was never set.

Finally, the remaining code in check uses and updates trav->word in several places where it should be using trav instead. I'll leave it to you to figure out the details on how.

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

5
  • Yeah I see what you mean, I guess I thought I had tested the load function, as it seemed to be working for me when I first wrote it, but I will definitely from now on be absolutely sure. Thanks for the advice, I'll get back to work!
    – HoopsLoops
    May 25 '20 at 8:58
  • I am a bit confused as to how I would add an end of string marker, I feel I have never run into a problem like this before. So I am to understand when I strcpy the word into my copystring 'copy_word' the \0 doesn't get copied as well?
    – HoopsLoops
    May 25 '20 at 9:07
  • But I did resolve this issue, as I wen't back to my hash-function after you helped me resolve my load issue, and I resolved my character case issue there, instead of the check function - but I am a bit confused as to what you meant with the \0 and would love to learn!
    – HoopsLoops
    May 25 '20 at 9:14
  • When you call strcpy, the \0 is automatically added. Later though, the code is copying letter by letter to lwrcase_word. That means that the \0 also has to be manually written to lwrcase_word too. It's not automatically done. lwrcase_word[n-1] = '\0';
    – Cliff B
    May 25 '20 at 17:17
  • Ah I see what you mean, of course. Thanks!
    – HoopsLoops
    May 26 '20 at 3:52
1

Your code has hidden memory errors. I ran speller small aca.txt and got the following error.

  Memory access error: writing to the outside of a memory space; abort execution.
  # Writing 1 bytes to 0xffa8882a will clobber other memory-spaces.
  #
  # The memory-space-to-be-written (start:0xffa887fc, size:46 bytes) is bound to 'word' at
  #    file:/dictionary.c::86, 10
  #
  #  0xffa887fc               0xffa88829
  #  +------------------------------+
  #  |the memory-space-to-be-written|......
  #  +------------------------------+
  #                                  ^~~~~~~~~~
  #        the write starts at 0xffa8882a that is right after the memory-space end.
  #
  # Stack trace (most recent call first) of the write.
  # [0]  file:/musl-1.1.10/src/stdio/vfscanf.c::258, 6
  # [1]  file:/musl-1.1.10/src/stdio/fscanf.c::28, 8
  # [2]  file:/dictionary.c::95, 12
  # [3]  file:/speller.c::40, 19
  # [4]  [libc-start-main]
1
  • Thanks man, will have a look at my memory errors again, was just trying to get to the point where the function was working, as I hadn't free'd anything other than in the unload function, so I assumed it wouldn't give med problems, but am I wrong to think that?
    – HoopsLoops
    May 25 '20 at 9:16

You must log in to answer this question.

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