0

My code looks like this: (ignore the comments; they're old)

// Implements a dictionary's functionality

#include <stdbool.h>
#include <string.h>
#include "dictionary.h"
#include <ctype.h>
#include <strings.h>
#include <stdlib.h>
#include <stdio.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 potential first letters * 26 potential second letters
// + 26 situations where the word is one letter long)
const unsigned int N = 702;

// Hash table
node *table[N];

// Global Variable that counts num of words
unsigned int num_of_words = 0;

// Initialize some temporary nodes
node temporary;
node n;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Allocate memory for a temporary node and make sure memory is allocated; otherwise return false
    node *temporarypoint;
    // Set a variable index to the hash on the hash table that the word belongs to
    int index = hash(word);
    // Set the address of the temporary node to what the correct index on the hash table points at
    temporarypoint = table[index];
    if (temporarypoint == NULL)
    {
        return false;
    }
    // While temporary is pointing at a valid place in memory, compare whether a word matches
    // and return true if there is a match
    while (temporarypoint != NULL)
        if (strcasecmp(temporarypoint->word, word) == 0)
        {
            return true;
        }
        // If the word doesn't match, set the temp node to the value that the next part of the temp node was pointing at
        else
        {
            temporarypoint = temporarypoint->next;
        }
    // Return false since no word has been found to match
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    if (strlen(word) == 1)
    {
        // Lowercase the first letter of the inputted word
        char first = tolower(word[0]);
        // Subtract 97 from that character, which will give a value from 0-26 on the ASCII Table
        first = (first - 97);
        return first;
    }
    else
    {
        // Lowercase the first and second letter of the inputted word
        char first = tolower(word[0]);
        char second = tolower(word[1]);
        if (first < 97 || first > 120 || second < 97 || second > 120)
        {
            return 1;
        }
        // Subtract 97 from that character, which will give a value from 0-26 on the ASCII Table, then shift it over
        // so that the letters act like a system of numbers based on 26 rather than 10
        first = (first - 97) * 26;
        second -= 97;
        // Add the two to get a total and return that total as a hash
        unsigned int total = first + second + 26;
        return total;
    }
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open the dictionary in a file pointer called file; make sure that the file is readable and return false if not
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    // Declare an array of length LENGTH to store each word
    char word[LENGTH];
    // Initialize an int that will hold the index of the hash table
    int index = 0;
    // While it is not the end of the dictionary, load more words into the array of linked lists
    while (fscanf(file, "%s", word) != EOF)
    {
        // Allocate memory for a node and check that there is enough memory to allocate; if not return false
        node *pointn = malloc(sizeof(node));
        if (pointn == NULL)
        {
            return false;
        }
        // Copy the characters in the array word into the word part of the node n
        strcpy(pointn->word, word);
        // Assign the hash index of the word to the variable index
        index = hash(pointn->word);
        // If this is the first node in the linked list, add the node to the linked list
        if (table[index] == NULL)
        {
            table[index] = pointn;
        }
        // Given that this is not the first node, make the node the first node in the linked list
        else
        {
            // Make the pointer of the node n point at what the head of the correct linked list points at
            pointn->next = table[index];
            // Point the head of the correct linked list at the node n
            table[index] = pointn;
        }
        // Call the size function, which should add one to the variable num_of_words
        size();
        free(pointn);
    }
    // Free the memory for node n
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // Adds one to the num of words and then returns that as the return value of the function
    num_of_words++;
    return num_of_words;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    n.next = malloc(sizeof(node));
    if (n.next == NULL)
    {
        return false;
    }
    temporary.next = malloc(sizeof(node));
    if (temporary.next == NULL)
    {
        return false;
    }
    node *npoint = n.next;
    node *temporarypoint = temporary.next;
    // For every linked list in the hash table, free the memory allocated for each node
    for (int i = 0; i < N; i++)
    {
        // Set the address of the cursor node to what the head of the linked list points at
        n.next = table[i];
        // Set the address of the tmp node to what the cursor points at
        temporary.next = n.next;
        // While the cursor points at a valid place in memory, free the data it points at, move it to what tmp points
        // at, and then move the address of tmp to what tmp was pointing at
        while (n.next != NULL)
        {
            // Free the data cursor is pointing at
            free(n.next);
            // Set the pointer of cursor to point at the address of tmp
            n.next = &temporary;
            // If the pointer of tmp still points at something, set the address of tmp to what tmp was pointing at
            if (temporary.next != NULL)
            {
                temporary = *temporary.next;
            }
        }
    }
    // Free all temporary nodes
    free(npoint);
    free(temporarypoint);
    return true;
}

I am getting a seg fault error in this section, which is in the load function:

// If this is the first node in the linked list, add the node to the linked list
            if (table[index] == NULL)
            {
                table[index] = pointn;
            }
            // Given that this is not the first node, make the node the first node in the linked list
            else
            {
                // Make the pointer of the node n point at what the head of the correct linked list points at
                pointn->next = table[index];
                // Point the head of the correct linked list at the node n
                table[index] = pointn;
            }

When I use debug50 on it, there are too many words in the dictionary, so I just press the play button, which goes until I get the error message. Valgrind has been unhelpful throughout my working on this code because it repeatedly points to the same line 93, even when there is only a comment there. Going back to debug 50, when I check the local variables, it showing index as a negative number even though it should be positive. When I look into the contents of the array "word", I find what I think is the issue. The characters are all over the place and do not form a word for some reason. From my perspective, it just looks like a bunch of random characters in random spots in the array, some divided by some \0 values. If possible, could someone please explain why these random characters are randomly appearing? Thank you for any response you give!

  • One thing I recommend is changing your node allocation in load to: node *pointn = calloc(1, sizeof(node)); This will ensure the allocated memory is zeroed out. If you don't, the tail end of each linked list will have a junk pointer to somewhere random, which is going to be an issue during unload(). – Sentox Nov 9 '20 at 2:59
  • Thank you so much for your answer, Sentox! I implemented calloc into my code, but for some reason, I still received the same errors with random characters appearing in the word array and the index becoming negative as a result. Do you know why this could be? If you don't know the answer, that is completely fine! Thank you for everything you have already done! – dillon__nguyen Nov 9 '20 at 20:24
1

The random values you see in word is the result of previous iterations of the loop assigning longer words than the current one. It's not an issue per se since the functions handling it (such as strlen or strcpy) will just read to the first null terminator anyway.

The problem lies in the hash function, and actually took me a little while to figure out. It's an error I commonly make of overlooking the limitations of data types.

first = (first - 96) * 26;

The problem here is that first is a char, so it can't hold a value higher than 127. This causes it to get wrapped into a negative number in certain cases. When a negative total is created, this in turn is wrapped into an unsigned int which results in an extremely high value... which is in turn assigned to a signed int back in the load function, giving you a negative and out-of-bounds index (it would, of course, be out of bounds either way).

PS. Something else to look out for - think about that call to free(pointn). Do you really want to free the memory pointn is pointing at?

You must log in to answer this question.

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