0

This has by far been the most rage-inducing pset in the course. Down to my last check50 error now, failing the "program is free of memory errors" test. I've run it in Valgrind and it says there are no leaks, but returns the following:

$ valgrind ./speller texts/cat.txt
==4786== Memcheck, a memory error detector
==4786== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4786== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==4786== Command: ./speller texts/cat.txt
==4786== 

MISSPELLED WORDS

==4786== Syscall param openat(filename) points to unaddressable byte(s)
==4786==    at 0x52E9C8E: open (open64.c:47)
==4786==    by 0x5266589: _IO_file_open (fileops.c:189)
==4786==    by 0x5266589: _IO_file_fopen@@GLIBC_2.2.5 (fileops.c:281)
==4786==    by 0x5258EA9: __fopen_internal (iofopen.c:78)
==4786==    by 0x5258EA9: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==4786==    by 0x4011A1: load (dictionary.c:83)
==4786==    by 0x4012D0: size (dictionary.c:136)
==4786==    by 0x400DBB: main (speller.c:144)
==4786==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==4786== 

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.73
TIME IN check:        0.02
TIME IN size:         0.01
TIME IN unload:       0.18
TIME IN TOTAL:        1.95

==4786== 
==4786== HEAP SUMMARY:
==4786==     in use at exit: 0 bytes in 0 blocks
==4786==   total heap usage: 143,097 allocs, 143,097 frees, 8,023,968 bytes allocated
==4786== 
==4786== All heap blocks were freed -- no leaks are possible
==4786== 
==4786== For counts of detected and suppressed errors, rerun with: -v
==4786== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Here's my code, would appreciate if someone can show me where the problem is.

// Implements a dictionary's functionality

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


// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

//initialize var for wordcount
int wordcount = 0;

// Number of buckets in hash table, or hashtable size
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

    //hash the word to obtain the hash value using hash function.
    int index = (hash(word));

    //access linked list at that index in the table
    node* cursor = table[index];

    //iterate through the list looking for the word (strcasecmp)
    //for (node* i = 0; i != NULL; i++)

    //execute this loop until cursor hits NULL
    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
            return true;

        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //TODO

    //source: Deliberate Think on Youtube

    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (isalpha(word[i]))
        {
            //convert word to lowercase so it handles "case-insensitively"
            n = tolower(word[i]) - 'a' + 1;
        }
        else
            n = 27;

        hash = ((hash << 3) + n) % N;
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO

    //open dictionary file
    FILE* dict = fopen(dictionary, "r");

    //if return value is NULL, return an error
    if (dict == NULL)
    {
        return false;
    }

    //iterate through each bucket in the hashtable and initialize to null?
    for (int i = 0; i < N; i++)
        table[i] = NULL;

    char word[LENGTH + 1];

    //read the string from the file (fscanf(file, "%s", word)) until it reached EOF.  try while loop for this
    while (fscanf(dict, "%s", word) != EOF)
    {
        //create new node using malloc
        node *newnode = malloc(sizeof(node));

        //check if return value is NULL
        if (newnode == NULL)
        {
            free(newnode);
            return false;
        }

        //copy word into node using strcpy
        strcpy(newnode->word, word);

        //hash the word using the hash function above to determine which linked list the word should be placed in
        int index = hash(word);

        //insert the word into the hash table

            //add a new node to the linked list
            //set its pointer to the first element in the list
            //then reset the head's pointer to the new node

        newnode->next = table[index];
        table[index] = newnode;

        //increment wordcount for each word added
        wordcount++;
    }
    fclose(dict);

    return true;
}

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

    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //iterate through hash table
    for (int i = 0; i < N; i++)
    {
        //init the cursor and tmp
        node* cursor = table[i];

        while (cursor != NULL)
        {
            node* tmp = cursor;
            //cursor moves to the next node
            cursor = cursor->next;
            //free the node tmp is currently pointing at
            free(tmp);
        }
        free(cursor);
    }
    return true;
}
0

Your valgrind report points to a wrong place for the cause. The true cause is free(cursor); at line 160 that frees a NULL pointer. The following is the error. You can reproduce/debug it with the link, just click start.

  Memory access error: freeing a non-pointer; abort execution.
  # free 0x0, which does not point to a legit memory space.
  # Stack trace (most recent call first) of the error.
  # [0]  file:/musl-1.1.10/src/malloc/safe_malloc.c::93, 5
  # [1]  file:/dictionary.c::160, 9
  # [2]  file:/speller.c::152, 21
  # [3]  [libc-start-main]
0

Fixed it myself! My memory problem was in the size function. The if (load = false) line was causing a problem. I had to create a new global variable for isLoaded, initialized to false, set it to true after the dictionary is loaded, and then have size check that for true or false rather than what I had before.

1
  • You're right. That line, if (load(false)) is actually calling load and passing false as the parameter. Not sure what this is going to do, but it can't be good. It would be easier to simply return wordcount. Keep in mind that if load returns false, the main speller program is going to terminate, so you don't need to worry about whether load completed here.
    – Cliff B
    Jun 12 '20 at 2:24

You must log in to answer this question.

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