0

I am not able to figure out what is causing the segmentation fault in my load function. Valgrind is pointing to fread and the lines where I have 'malloc'-ed memory, but more importantly to the line table[index] = n;. I have referred to most of the q&a on this topic. I have also inserted some print statements but have not been able to figure out the problem. Any advice/hints will be highly appreciated.

speller/ $ valgrind ./speller texts/lalaland.txt
==20587== Memcheck, a memory error detector
==20587== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==20587== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==20587== Command: ./speller texts/lalaland.txt
==20587== 
file opened
memory allocated to buffer
amemory allocated to node

memory allocated to node
==20587== 
==20587== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==20587==  Bad permissions for mapped region at address 0x10BEF8
==20587==    at 0x109C46: load (dictionary.c:162)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== HEAP SUMMARY:
==20587==     in use at exit: 5,694 bytes in 5 blocks
==20587==   total heap usage: 6 allocs, 1 frees, 5,750 bytes allocated
==20587== 
==20587== 46 bytes in 1 blocks are still reachable in loss record 1 of 5
==20587==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20587==    by 0x109AE6: load (dictionary.c:111)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== 56 bytes in 1 blocks are still reachable in loss record 2 of 5
==20587==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20587==    by 0x109B9D: load (dictionary.c:139)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== 472 bytes in 1 blocks are still reachable in loss record 3 of 5
==20587==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20587==    by 0x49C86CD: __fopen_internal (iofopen.c:65)
==20587==    by 0x49C86CD: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==20587==    by 0x109A7D: load (dictionary.c:92)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== 1,024 bytes in 1 blocks are still reachable in loss record 4 of 5
==20587==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20587==    by 0x49C7C23: _IO_file_doallocate (filedoalloc.c:101)
==20587==    by 0x49D6D5F: _IO_doallocbuf (genops.c:347)
==20587==    by 0x49D5FDF: _IO_file_overflow@@GLIBC_2.2.5 (fileops.c:744)
==20587==    by 0x49D4754: _IO_new_file_xsputn (fileops.c:1243)
==20587==    by 0x49D4754: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1196)
==20587==    by 0x49BE1CC: outstring_func (vfprintf-internal.c:239)
==20587==    by 0x49BE1CC: __vfprintf_internal (vfprintf-internal.c:1263)
==20587==    by 0x49A981E: printf (printf.c:33)
==20587==    by 0x109ADC: load (dictionary.c:106)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== 4,096 bytes in 1 blocks are still reachable in loss record 5 of 5
==20587==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20587==    by 0x49C7C23: _IO_file_doallocate (filedoalloc.c:101)
==20587==    by 0x49D6D5F: _IO_doallocbuf (genops.c:347)
==20587==    by 0x49D4543: _IO_file_xsgetn (fileops.c:1287)
==20587==    by 0x49C8C28: fread (iofread.c:38)
==20587==    by 0x109B36: load (dictionary.c:124)
==20587==    by 0x1092DB: main (speller.c:40)
==20587== 
==20587== LEAK SUMMARY:
==20587==    definitely lost: 0 bytes in 0 blocks
==20587==    indirectly lost: 0 bytes in 0 blocks
==20587==      possibly lost: 0 bytes in 0 blocks
==20587==    still reachable: 5,694 bytes in 5 blocks
==20587==         suppressed: 0 bytes in 0 blocks
==20587== 
==20587== For lists of detected and suppressed errors, rerun with: -s
==20587== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
/opt/cs50/bin/valgrind: line 11: 20587 Segmentation fault      (core dumped) /usr/bin/valgrind $*

here's my code for the load function

#include <cs50.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.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;

// TODO: Choose number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// prototypes
int strcasecmp(char *c1, const char *c2);


// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // convert word to lower case
    char *lower = malloc(sizeof(char) * (strlen(word) + 1));

    for (int i = 0, n = strlen(word) + 1; i < n; i++)
    {
        lower[i] = tolower(word[i]);
    }

    int index = hash(word);

    // traversal pointer
    node *tmp = table[index];

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

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}

// no. of words loaded into hash table from dictionary
int count = 0;


// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // initialize all node pointers in the table to NULL
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

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

    if (!file)
    {
        printf("File not found\n");
        return 1;
    }
    
    // check for a valid file pointer
    if (file == NULL)
    {
        fclose(file);
        printf("Could not open file\n");
        return 2;
    }
    printf("file opened\n");

    char *buffer = malloc(sizeof(char)*(LENGTH + 1));

    if (buffer == NULL)
    {
        printf("not enough memory for buffer/n");
        return 1;
    }
    printf("memory allocated to buffer\n");

    char c;
    int t = 0;
    
    // read chars from file one at a time
    while (fread(&c, sizeof(char), 1, file))
    {
        printf("%c", c);
        if (c != '\0')
        {
            buffer[t] = c;
            t++;
        }
        buffer[t] = '\0';
        t = 0;

        if (t == 0)
        {
            // allocate memory for one node
            node *n = malloc(sizeof(node));

            if (n == NULL)
            {
                printf("not enough memory/n");
                return 1;
                break;
            }
            printf("memory allocated to node\n");

            // copy word into the node
            strcpy(n->word, buffer);
            n->next = NULL;

            // hash the word through the hash function
            int index = hash(n->word);

            if (table[index] == NULL)
            {
                table[index] = n;
            }
            n->next = table[index];
            table[index] = n;

            free(n);
        }
    }

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

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // loop over the hash table
    for (int i = 0; i < N; i++)
    {
        while (table[i]->next != NULL)
        {
            node *trav = malloc(sizeof(node));

            if (trav == NULL)
            {
                printf("not enough memory/n");
                return false;
                break;
            }

            trav = table[i];
            table[i] = table[i]->next;
            free(trav);
        }
    }
    return true;
}


1 Answer 1

0

I see several real and potential issues in the code above.

My best guess, without seeing your hash function, is that the hash function is returning a value that's greater than N, the limit to the size of the table[N] array. Have you checked the hash values that are being returned?

Next, the code has the following statement in load: free(n);. This will release the memory that was just allocated to store a word in the tree. None of the nodes should be freed until the unload function executes. This may well be causing a seg fault, or an additional seg fault.

suggestion: Why does the code read one character at a time from the input file? This is terribly inefficient. Note that much of the time and resources expended in a file read or write are the overhead to access the file. Instead, it should be reading in an entire line at a time. As the spec states, each line contains one word. Also, there's the additional overhead of executing an entire pass through the while loop for each letter instead of each line.

This should get you going again. ;-)

[EDIT]

The problem is that this code is not processing words, it's processing letters. (I noticed this earlier and it didn't click.) When the code gets to the non-printable char at the end of each line, it goes bonkers and you get a seg fault.

Again, why does the code read one letter at a time and try to process each letter as if it were a word???? It should read in an entire line as a word, per the program spec. If you want to see it in more detail, add the following as line 139:

        printf("Word: %s, hash: %i\n",n->word, index);

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

5
  • I am still using the default hash function. I tested it too, its working fine. I removed free(n); from the code but I am still getting the seg fault. Could it be any other line that's causing it? Appreciate your help.
    – Soumik
    Commented May 3, 2023 at 15:26
  • please edit the question and add the rest of the code.
    – Cliff B
    Commented May 3, 2023 at 21:55
  • I have added the rest of the code.
    – Soumik
    Commented May 4, 2023 at 13:25
  • I changed my code based on your suggestion. However, now I am getting a double free or corruption (fasttop) error
    – Soumik
    Commented May 24, 2023 at 18:34
  • Answered in your new question.
    – Cliff B
    Commented May 25, 2023 at 4:37

You must log in to answer this question.

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