0
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include <strings.h>

#include "dictionary.h"

int s = 0;

// 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 = 45;

// Hash table
node *table[N];

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

// Hashes word to a number (using first two letters)
unsigned int hash(const char *word)
{
    int n = strlen(word) - 1;
    return n;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (!dict)
    {
        return false;
    }
    char *tempword = malloc((LENGTH + 1) * sizeof(char));
    while (fscanf(dict, "%s", tempword) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        strcpy(n->word, tempword);
        int hsh = hash(tempword);
        n->next = table[hsh];
        table[hsh] = n;
        s++;
        free(n);
    }
    free(tempword);
    fclose(dict);
    return true;
}

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

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

Amongst other valgrind errors, I always get invalid read of size 1 at line 33 (if(strcasecmp(cursor->word, word) == 0)). Using debug50 I have not been able to work out why this is but I have noticed that the else bracket a few lines later is not updating the cursor. I hope this is clear enough and thanks in advance for any help :)

2

Actually, the problem lies in load.

    free(n);

This is corrupting the dictionary tree. Remember, n is a pointer to memory. When you free it, you free that memory. Even if it has been added to the linked lists of the tree, that particular memory is being freed. The bottom line is that immediately after the words are stored in the tree, their nodes are being deleted.

The effect on check is unpredictable. It can result in seg faults or infinite waits/loops, but no found words.

The memory should only be freed in unload, not in load. (Well, tempword can be freed after the loop is done because it is no longer needed. )

This is a good example of how a problem in one place can cause extensive errors in a totally different part of a program. Whenever you have a bug that you can't find where you expect, you need to carefully look at everything related - the logic and the data content!

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

BTW, did you remember to initialize table[] ??? ;-)

  • Thank you so much! Can I ask how you worked out what was wrong? – katja Sep 21 '20 at 11:23
  • Experience. I've debugged several hundred versions of this pset. At a certain point, I just know when I see issues. I know that doesn't help. However, in this case, it's about understanding that freeing memory that was just allocated should be a red flag. Especially when you know that that memory is going to be used later. – Cliff B Sep 21 '20 at 20:50

You must log in to answer this question.

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