0

I was working on pset5 (speller), and I think my program seems to work. However, it does not pass check50, and I think that this might be due to the valgrind errors I am receiving (which I pasted below, along with what help50 said about them). I've attached my code. Thanks!

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

node *hashtable[26];

int hash(char *to_hash)
{
    int h = 0;
    if (islower (to_hash[0]))
    {
        h = (int)(to_hash[0]) - 'a';
    }
    else if (isupper (to_hash))
    {
        h = (int)(to_hash[0]) - 'A';
    }
    return h;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int x = strlen(word);
    char word2 [x + 1];
    strcpy(word2, word);
    int y;
    int k = (hash)(word2);
    node *cursor = hashtable[k];
    while (cursor != NULL)
    {
        if (strcasecmp((cursor -> word), word2) == 0)
        {
            y = 1;
        }
        cursor = cursor -> next;
    }
    if (y == 1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    char word [LENGTH + 1];

    FILE *file = fopen (dictionary, "r");
    node *new_node;

    if (file == NULL)
    {
        return false;
    }

    while (fscanf(file, "%s", word) != EOF)
    {
        new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        else
        {
            strcpy(new_node -> word, word);
            int i = (hash)(word);
            if (hashtable[i] == NULL)
            {
                hashtable[i] = new_node;
                new_node -> next = NULL;
            }
            else
            {
                new_node -> next = hashtable[i];
                hashtable[i] = new_node;
            }
        }
    }

    free (new_node);
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    int x = 0;
    for (int i = 0; i < 26; i++)
    {
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            cursor = cursor -> next;
            x++;
        }

    }
    return x;
}

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

==6303== Memcheck, a memory error detector

==6303== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.

==6303== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info

==6303== Command: ./speller texts/ralph.txt

==6303==

Could not open texts/ralph.txt.

==6303== Invalid read of size 8

==6303== at 0x423146: unload (dictionary.c:133)

==6303== by 0x420B50: main (speller.c:61)

==6303== Address 0x6ebddf0 is 48 bytes inside a block of size 56 free'd

==6303== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)

==6303== by 0x422FA2: load (dictionary.c:102)

==6303== by 0x420962: main (speller.c:42)

==6303==

==6303== Invalid free() / delete / delete[] / realloc()

==6303== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)

==6303== by 0x423158: unload (dictionary.c:134)

==6303== by 0x420B50: main (speller.c:61)

==6303== Address 0x6ebddc0 is 0 bytes inside a block of size 56 free'd

==6303== at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64- linux.so)

==6303== by 0x422FA2: load (dictionary.c:102)

==6303== by 0x420962: main (speller.c:42)

==6303== ==6303==

==6303== HEAP SUMMARY:

==6303== in use at exit: 0 bytes in 0 blocks

==6303== total heap usage: 143,093 allocs, 143,094 frees, 8,014,232 bytes allocated

==6303==

==6303== All heap blocks were freed -- no leaks are possible

==6303==

==6303== For counts of detected and suppressed errors, rerun with: -v

==6303== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

HELP50

Helping with...

==6303== Invalid read of size 8

==6303== at 0x423146: unload (dictionary.c:133)

==6303== by 0x420B50: main (speller.c:61)

Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 133 of dictionary.c.

1 Answer 1

1

With the free (new_node); in load, you free the last node you added to the hash table. It's still in use, so don't do that. Remove the line.

BTW, (hash)(word) looks a bit weird. Putting the first word in parentheses is usually done in type casts, like one might use char *word = (char*)malloc((LENGTH+1)*sizeof(char));, explicitly casting the void* returned by malloc to char*. Please run style50 on that code, it might find more odd-looking things.

edit: And I have no idea how it would do that, but when you write isupper (to_hash) instead of isupper (to_hash[0]), that seems to cause segmentation faults. Again, no idea how this could happen.

5
  • Thank you for this. This fixed the valgrind error. However, whenever I run it, I am getting a segmentation fault, and I can't figure out why it is. Is there something I am missing?
    – user3256
    Jun 28, 2018 at 18:24
  • No, it is happening for all combinations. I ran valgrind again, and there is a new error.
    – user3256
    Jun 28, 2018 at 19:05
  • This is what help50 says: Helping with... ==3814== Invalid read of size 2 ==3814== at 0x40114B: hash (dictionary.c:30) ==3814== by 0x4011D4: check (dictionary.c:44) ==3814== by 0x400D21: main (speller.c:112) Looks like you're trying to access 2 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 30 of dictionary.c.
    – user3256
    Jun 28, 2018 at 19:06
  • The problem appears to be with the hash function
    – user3256
    Jun 28, 2018 at 19:07
  • Correct, more precisely with your uppercase path. That's why I did not see it, I used a text in all lowercase. You forgot a [0].
    – Blauelf
    Jun 28, 2018 at 19:12

You must log in to answer this question.

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