0

I've spent a whole day trying to solve pset5. When i try to run the code it kept showing "Segmentation fault".

Here's what i get from Valgrind

==21210== HEAP SUMMARY:
==21210==     in use at exit: 664 bytes in 3 blocks
==21210==   total heap usage: 4 allocs, 1 frees, 4,760 bytes allocated
==21210== 
==21210== 112 bytes in 2 blocks are still reachable in loss record 1 of 2
==21210==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21210==    by 0x401275: load (dictionary.c:79)
==21210==    by 0x4009B4: main (speller.c:40)
==21210== 
==21210== 552 bytes in 1 blocks are still reachable in loss record 2 of 2
==21210==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21210==    by 0x5258E49: __fopen_internal (iofopen.c:65)
==21210==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==21210==    by 0x401231: load (dictionary.c:70)
==21210==    by 0x4009B4: main (speller.c:40)
==21210== 
==21210== LEAK SUMMARY:
==21210==    definitely lost: 0 bytes in 0 blocks
==21210==    indirectly lost: 0 bytes in 0 blocks
==21210==      possibly lost: 0 bytes in 0 blocks
==21210==    still reachable: 664 bytes in 3 blocks
==21210==         suppressed: 0 bytes in 0 blocks
==21210== 
==21210== For counts of detected and suppressed errors, rerun with: -v
==21210== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
/etc/profile.d/cli.sh: line 94: 21210 Segmentation fault      valgrind ./speller texts/cat.txt

And here is my full code. Though Valgrind says that the seg fault is on line 94(just a bracket), i can't find the problem on my own. According to Valgrind, the problem is in the load fuction but i do see a lot of people having load functions that look quite similar to mine. Any help would be appriciated!

// Implements a dictionary's functionality

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


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

//track size of dictionary for size function
int track_word = 0;

// Number of buckets in hash table
const unsigned int N = 1;

// Hash table#define HASHTABLE_SIZE 65536
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
   
    char tmp_word[strlen(word)];
    strcpy(tmp_word, word);
    for (int i = 0; tmp_word[i] != '\0'; i++ )
    {
        tmp_word[i] = tolower(word[i]);
    }
    int w = hash(tmp_word);
    node *cursor = NULL;
    cursor = table[w];
    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, tmp_word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
//hash function djb2
//retrieved from http://www.cse.yorku.ca/~oz/hash.html 09.07.2020
unsigned int hash(const char *word)
{
    unsigned int hash_value = N;
    int c;
    while ((c = *word++))
    {
        hash_value = ((hash_value << 5) + hash_value) + c; /* hash * 33 + c */
    }
    return hash_value;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary,"r");  //line 70
    if (file == NULL)
    {
        return false;
    }
    
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node)); //line 79
        new_node->next = NULL;
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        strcpy (new_node->word, word);
        int h = hash(word);
       
        if (table[h] == NULL)
        {
            table[h] = new_node;
        }
        else
        {   //this is line 94
            new_node->next = table[h];
            table[h] = new_node;
        }
        track_word++;
    }
    fclose(file);
    return true;
    
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i< N; i++)
    {
        node *cursor = table[i];
        if(cursor != NULL)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
        free(cursor);
        
    }
    return true;
}
1
  • 1
    This jumps off the page const unsigned int N = 1;. table is declared with one element. How big of a number does hash return? My guess is it's likely to be a heckuva lot bigger than 0. valgrind is usually not the right tool for finding a seg fault. debugging is where one should begin. Find out which line is crashing. This post gives helpful hints. – DinoCoderSaurus Jul 9 '20 at 17:14
0

As @DinoCoderSaurus stated (Dino, you really need to leave answers instead of comments), the hash function isn't limited. It can return a hash value far larger than the size of table[]. It should be limited to the size of the table, N, using the modulo operator.

The next issue is that table[] is never initialized, so it can contain invalid addresses that are used by the code. Each array element should be set to NULL before using the array.

Finally, isn't N a bit small? It's set to 1.

You must log in to answer this question.

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