0

I have been following all the instructions very carefully and have been able to come up with a code that looks like it should be doing all the steps needed in every function, I would say.

When I execute speller using the small dictionary the program works. Yahoo.

However when I try executing using the large dictionary I get this error: munmap_chunk(): invalid pointer Aborted

I don't know why is this happening. I would say I am correctly feeing the memory dynamically allocated to build my hashtable.

I am pasting here my code. A million thanks in advance for your kind help.

// 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"

unsigned int hash_word(const char *word);

// Initialize word count
int word_count = 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 = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    // Take the word and hash it to obtain a hash value
    // Access the linked list at that hash value
    // Traverse linked list looking at one node at a time

    int h = hash_word(word);
    node *cursor = table[h];

    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash_word(const char *word)
{
    /**
     * A case-insensitive implementation of the djb2 hash function.
     * Change NUM_BUCKETS to whatever your number of buckets is.
     *
     * Adapted by Neel Mehta from
     * http://stackoverflow.com/questions/2571683/djb2-hash-function.
     */
    unsigned long hash = 5381;

    for (const char* ptr = word; *ptr != '\0'; ptr++)
    {
        hash = ((hash << 5) + hash) + tolower(*ptr);
    }

    return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO
    // Open dictionary file
    // Read srings from file one at a time
    // Create a new node for each word
    // Hash that word to obtain a hash value
    // Insert node into hash table

    // Open dictionary file
    FILE *file = fopen(dictionary, "rf");
    if (file == NULL)
    {
        return false;
    }

    // Read srings from file one at a time
    char *word = malloc(sizeof(LENGTH + 1));
    while (fscanf(file, "%s", word) != EOF)
    {
        // Create a new node for each word
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }

        // Count new word
        word_count++;

        // Copy the word into the node
        strcpy(n->word, word);

        // Insert node into hash table
        int h = hash_word(word);
        node *head = table[h];

        // If bucket is empty, insert the first node
        if (head == NULL)
        {
            table[h] = n;
        }
        // If not empty, insert node to front of list
        else
        {
            n->next = table[h];
            table[h] = n;
        }
    }

    // Close dictionary file and success
    fclose(file);
    return true;

}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    // Create a cursor variable and a tmp variable
    // Move cursor to the next node
    // Free up tmp node
    // Repeat process until cursor == NULL

    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];

        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

1

Problem is here char *word = malloc(sizeof(LENGTH + 1));. Specifically sizeof(LENGTH + 1). LENGTH + 1 returns an int. sizeof(an int) is 4 in the IDE. If you want to see what problems there are, and since the small dictionary doesn't seg fault, suggest valgrind -v ./speller dictionaries/small texfile to give you more feedback.

1
  • Genius! Thank you, the correct approach here was to malloc enough memory to store a node, so char *word = malloc(sizeof(node)); would be the right approach here. Thank you for shedding light on it! Mar 19 '20 at 17:46

You must log in to answer this question.

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