Thread: problem with pointers to a struct, not compiling

This is a work in progress so there might be mistakes (which I can't get to right now cause it's not compiling), my main question is why is it giving me this when compiling:

Code:

gcc -ggdb -std=c99 -Wall -Werror   -c -o dictionary.o dictionary.c
dictionary.c: In function 'load':
dictionary.c:70:29: error: incompatible types when assigning to type 'char[46]' from type 'char *'
dictionary.c:98:38: error: incompatible types when assigning to type 'char[46]' from type 'char *'
make: *** [dictionary.o] Error 1

Code:

/****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * Implements a dictionary's functionality.
 ***************************************************************************/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "dictionary.h"

#define HASHTABLE_SIZE 25

// link list node structure
struct node {
  char data[LENGTH + 1]; // dictionary word
  struct node *next;
};

/*
 * Returns true if word is in dictionary else false.
 */

bool
check(const char *word)
{
    // TODO
    return false;
}


/*
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool
load(const char *dictionary)
{
    // open dictionary file
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
    { 
        printf("Error opening dictionary");
        return false;
    }
    
    /*******************
     * START LINK LIST *
     *******************/

    /* This won't change, or we would lose the list in memory */
    struct node *root[HASHTABLE_SIZE];       
    /* This will point to each node as it traverses the list */
    struct node *conductor[HASHTABLE_SIZE];  
    
    for (int i = '0'; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        root[i] = malloc( sizeof(struct node) ); 
    } 
    
    char word[LENGTH + 1]; // var for reading word from file
    fscanf(fp, "%s", word); // read 1 word from file 
    
    int hash_bucket = hashFunction(word);
    
    root[hash_bucket]->data = word;   
    root[hash_bucket]->next = 0;      
    
    conductor[hash_bucket] = root[hash_bucket]; 
    if ( conductor[hash_bucket] != 0 ) {
        while ( conductor[hash_bucket]->next != 0)
        {
            conductor[hash_bucket] = conductor[hash_bucket]->next;
        }
    }
    
    while (!feof(fp)) // go through whole dictionary file
    {
        fscanf(fp, "%s", word); // read 1 word from file
        hash_bucket = hashFunction(word);
        
        /* Creates a node at the end of the list */
        conductor[hash_bucket]->next = malloc( sizeof(struct node) );  

        conductor[hash_bucket] = conductor[hash_bucket]->next; 

        if ( conductor[hash_bucket] == 0 )
        {
            printf( "Out of memory" );
            return false;
        }
        /* initialize the new memory */
        conductor[hash_bucket]->next = 0;         
        conductor[hash_bucket]->data = word; 
    }
    
    // TESTING
    for (int i = '0'; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        conductor[i] = root[i];
        while (conductor[i]->next != NULL)
        {
            printf("%s\n" , conductor[i]->data);
            conductor[i] = conductor[i]->next;      
        }
        printf("\n\nBUCKET NUMBER %d\n\n" , i);
    }
    
    // dictionary has been loaded
    fclose(fp);
    return true; 
}


/*
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */

unsigned int
size(void)
{
    // TODO
    return 0;
}


/*
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

bool
unload(void)
{
    // TODO
    return false;
}

int
hashFunction(char word[LENGTH + 1])
{
    int n = word[0]; // first letter of each word is a bucket
    return (n % HASHTABLE_SIZE); // make sure it doesn't go over the max size of the hashtable
}

You cannot assign to an array. Rather, you should copy over the elements of the array.

Thanks for both replies, I implemented a loop to copy the array and fixed both things mentioned by Andi.

2 more problems appeared that I don't know how to fix :

1. The "word" array doesn't print properly when I call printf in gdb (I want it to print the whole string, which is supposed to be a word from the dictionary file).

2. It segfaults at line 73, where I implemented the loop for copying the array.

gdb:

Code:

(gdb) 
68        int hash_bucket = hashFunction(word);
(gdb) 
71        for (int a = 0; word[a] != '\0'; a++)
(gdb) 
73            root[hash_bucket]->data[a] = word[a];

(gdb) call printf("%s" , word)
$4 = 1
(gdb) printf "%s" , word 
a
(gdb) next

Program received signal SIGSEGV, Segmentation fault.
0x08048d02 in load (dictionary=0x8049044 "/home/cs50/pset6/dictionaries/large") at dictionary.c:73
73            root[hash_bucket]->data[a] = word[a];

updated code:

Code:

/****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * Implements a dictionary's functionality.
 ***************************************************************************/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "dictionary.h"

#define HASHTABLE_SIZE 25

// link list node structure
struct node {
  char data[LENGTH + 1]; // dictionary word
  struct node *next;
};

/*
 * Returns true if word is in dictionary else false.
 */

bool
check(const char *word)
{
    // TODO
    return false;
}


/*
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool
load(const char *dictionary)
{
    // open dictionary file
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
    { 
        printf("Error opening dictionary");
        return false;
    }
    
    /*******************
     * START LINK LIST *
     *******************/

    /* This won't change, or we would lose the list in memory */
    struct node *root[HASHTABLE_SIZE];       
    /* This will point to each node as it traverses the list */
    struct node *conductor[HASHTABLE_SIZE];  
    
    for (int i = 0; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        root[i] = malloc( sizeof(struct node) ); 
    } 
    
    char word[LENGTH + 1]; // var for reading word from file
    fscanf(fp, "%s", word); // read 1 word from file 
    
    int hash_bucket = hashFunction(word);
    
    // begin insert word into the node->data
    for (int a = 0; word[a] != '\0'; a++)
    { 
        root[hash_bucket]->data[a] = word[a];
    }
    // end insert word into node->data
    
    root[hash_bucket]->next = 0;      
    
    conductor[hash_bucket] = root[hash_bucket]; 
    if ( conductor[hash_bucket] != 0 ) {
        while ( conductor[hash_bucket]->next != 0)
        {
            conductor[hash_bucket] = conductor[hash_bucket]->next;
        }
    }
    
    while ((fscanf(fp, "%s", word)) == 1) // go through whole dictionary file and read 1 word at a time
    {
        hash_bucket = hashFunction(word); // hash function, find out which bucket to put word in
        
        /* Creates a node at the end of the list */
        conductor[hash_bucket]->next = malloc( sizeof(struct node) );  

        conductor[hash_bucket] = conductor[hash_bucket]->next; 

        if ( conductor[hash_bucket] == 0 )
        {
            printf( "Out of memory" );
            return false;
        }
        
        /* initialize the new memory */
        conductor[hash_bucket]->next = 0;         
        
        // begin insert word into the node->data
        for (int a = 0; word[a] != '\0'; a++)
        { 
            root[hash_bucket]->data[a] = word[a];
        }
        // end insert word into node->data
    }
    
    // TESTING
    for (int i = 0; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        conductor[i] = root[i];
        while (conductor[i]->next != NULL)
        {
            printf("%s\n" , conductor[i]->data);
            conductor[i] = conductor[i]->next;      
        }
        printf("\n\nBUCKET NUMBER %d\n\n" , i);
    }
    
    // dictionary has been loaded
    fclose(fp);
    return true; 
}


/*
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */

unsigned int
size(void)
{
    // TODO
    return 0;
}


/*
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

bool
unload(void)
{
    // TODO
    return false;
}

int
hashFunction(char word[LENGTH + 1])
{
    int n = word[0]; // first letter of each word is a bucket
    return (n % HASHTABLE_SIZE); // make sure it doesn't go over the max size of the hashtable
}

Thanks for your reply Andreas,

I am still working on this and not sure why it segfaults but I have found more information while debugging:

It seems to me that the loop is fine, since the printf works in it, but please correct me if I'm wrong as I don't think I understand you. It seems the memory doesn't get allocated though because when it reaches the hash_bucket number 1, it segfaults. You can see what the program prints in the terminal below:

Code:

memory bucket[0] has been allocated
memory bucket[1] has been allocated
memory bucket[2] has been allocated
memory bucket[3] has been allocated
memory bucket[4] has been allocated
memory bucket[5] has been allocated
memory bucket[6] has been allocated
memory bucket[7] has been allocated
memory bucket[8] has been allocated
memory bucket[9] has been allocated
memory bucket[10] has been allocated
memory bucket[11] has been allocated
memory bucket[12] has been allocated
memory bucket[13] has been allocated
memory bucket[14] has been allocated
memory bucket[15] has been allocated
memory bucket[16] has been allocated
memory bucket[17] has been allocated
memory bucket[18] has been allocated
memory bucket[19] has been allocated
memory bucket[20] has been allocated
memory bucket[21] has been allocated
memory bucket[22] has been allocated
memory bucket[23] has been allocated
memory bucket[24] has been allocated
memory bucket[25] has been allocated
first word inserted properly, root[0]->data is 'a' 
hash number: 0, word: aaa , x: 0
hash number: 0, word: aaas , x: 1
hash number: 0, word: aachen , x: 2
...
...
hash number: 0, word: azurite , x: 9125
hash number: 0, word: azusa , x: 9126
hash number: 1, word: baa , x: 9127
Segmentation fault (core dumped)

this is what i get with valgrind:

Code:

==31295== Conditional jump or move depends on uninitialised value(s)
==31295==    at 0x407D606: vfprintf (vfprintf.c:1568)
==31295==    by 0x40867EE: printf (printf.c:35)
==31295==    by 0x80486B5: main (speller.c:46)
==31295== 
first word inserted properly, root[0]->data is 'a' 
==31295== Use of uninitialised value of size 4
==31295==    at 0x8048EC6: load (dictionary.c:114)
==31295==    by 0x80486B5: main (speller.c:46)
==31295== 
==31295== Invalid write of size 4
==31295==    at 0x8048EC6: load (dictionary.c:114)
==31295==    by 0x80486B5: main (speller.c:46)
==31295==  Address 0xb80 is not stack'd, malloc'd or (recently) free'd
==31295== 
==31295== 
==31295== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==31295==  Access not within mapped region at address 0xB80
==31295==    at 0x8048EC6: load (dictionary.c:114)
==31295==    by 0x80486B5: main (speller.c:46)
==31295==  If you believe this happened as a result of a stack
==31295==  overflow in your program's main thread (unlikely but
==31295==  possible), you can try to increase the size of the
==31295==  main thread stack using the --main-stacksize= flag.
==31295==  The main thread stack size used in this run was 8388608.
==31295== 
==31295== HEAP SUMMARY:
==31295==     in use at exit: 476,712 bytes in 9,156 blocks
==31295==   total heap usage: 9,156 allocs, 0 frees, 476,712 bytes allocated
==31295== 
==31295== 52 bytes in 1 blocks are definitely lost in loss record 1 of 5
==31295==    at 0x4025D69: malloc (vg_replace_malloc.c:236)
==31295==    by 0x8048CE8: load (dictionary.c:62)
==31295==    by 0x80486B5: main (speller.c:46)
==31295== 
==31295== 52 bytes in 1 blocks are definitely lost in loss record 2 of 5
==31295==    at 0x4025D69: malloc (vg_replace_malloc.c:236)
==31295==    by 0x8048EC5: load (dictionary.c:114)
==31295==    by 0x80486B5: main (speller.c:46)
==31295== 
==31295== LEAK SUMMARY:
==31295==    definitely lost: 104 bytes in 2 blocks
==31295==    indirectly lost: 0 bytes in 0 blocks
==31295==      possibly lost: 0 bytes in 0 blocks
==31295==    still reachable: 476,608 bytes in 9,154 blocks
==31295==         suppressed: 0 bytes in 0 blocks
==31295== Reachable blocks (those to which a pointer was found) are not shown.
==31295== To see them, rerun with: --leak-check=full --show-reachable=yes
==31295== 
==31295== For counts of detected and suppressed errors, rerun with: -v
==31295== Use --track-origins=yes to see where uninitialised values come from
==31295== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 14 from 9)
Segmentation fault

updated code:

Code:

/****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 6
 *
 * Implements a dictionary's functionality.
 ***************************************************************************/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "dictionary.h"

#define HASHTABLE_SIZE 25

// link list node structure
struct node {
  char data[LENGTH + 1]; // dictionary word
  struct node *next;
};

/*
 * Returns true if word is in dictionary else false.
 */

bool
check(const char *word)
{
    // TODO
    return false;
}


/*
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool
load(const char *dictionary)
{
    // open dictionary file
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
    { 
        printf("Error opening dictionary");
        return false;
    }
    
    /*******************
     * START LINK LIST *
     *******************/

    /* This won't change, or we would lose the list in memory */
    struct node *root[HASHTABLE_SIZE];       
    /* This will point to each node as it traverses the list */
    struct node *conductor[HASHTABLE_SIZE];  
    
    for (int i = 0; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        root[i] = malloc( sizeof(struct node) ); 
        // TESTING
        printf("memory bucket[%d] has been allocated\n" , i);
    } 
    
    char word[LENGTH + 1]; // var for reading word from file
    fscanf(fp, "%s", word); // read 1 word from file 
    
    int hash_bucket = hashFunction(word);
      
    // begin insert word into the node->data
    for (int a = 0; word[a] != '\0'; a++)
    { 
        root[hash_bucket]->data[a] = word[a];
        root[hash_bucket]->next = 0;
        conductor[hash_bucket] = root[hash_bucket]; 
    }
    // end insert word into node->data
    
    // TESTING
    printf("first word inserted properly, root[%d]->data is '%s' \n" , hash_bucket , root[hash_bucket]->data);
    int x = 0;
    FILE *tester = fopen("tester.txt", "w");
    if (fp == NULL)
    { 
        printf("Error opening dictionary");
        return false;
    }
    // END TESTING
    
    if ( conductor[hash_bucket] != 0 ) {
        while ( conductor[hash_bucket]->next != 0)
        {
            conductor[hash_bucket] = conductor[hash_bucket]->next;
            // TESTING
            printf("traverse bucket %d\n" , hash_bucket);
        }
    }
    
    while ((fscanf(fp, "%s", word)) == 1) // go through whole dictionary file and read 1 word at a time
    {        
        hash_bucket = hashFunction(word); // hash function, find out which bucket to put word in
        
        // TESTING
        char y[200];
        sprintf(y , "hash number: %d, word: %s , x: %d\n" , hash_bucket, word , x);
        // printf("%s" , y);
        fprintf(tester, "%s" , y);
        x++;
        // END TESTING
        
        /* Creates a node at the end of the list */
        conductor[hash_bucket]->next = malloc( sizeof(struct node) );  

        conductor[hash_bucket] = conductor[hash_bucket]->next; 

        if ( conductor[hash_bucket] == 0 )
        {
            printf( "Out of memory" );
            return false;
        }
        
        /* initialize the new memory */
        conductor[hash_bucket]->next = 0;         
        
        // begin insert word into the node->data
        for (int a = 0; word[a] != '\0'; a++)
        { 
            root[hash_bucket]->data[a] = word[a];
        }
        // end insert word into node->data
    }
    
    // TESTING
    for (int i = 0; i <= HASHTABLE_SIZE; i++ ) // create hashtable 
    { 
        conductor[i] = root[i];
        while (conductor[i]->next != NULL)
        {
            printf("%s\n" , conductor[i]->data);
            conductor[i] = conductor[i]->next;      
        }
        printf("\n\nBUCKET NUMBER %d\n\n" , i);
    }
    
    // dictionary has been loaded
    fclose(fp);
    return true; 
}


/*
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */

unsigned int
size(void)
{
    // TODO
    return 0;
}


/*
 * Unloads dictionary from memory.  Returns true if successful else false.
 */

bool
unload(void)
{
    // TODO
    return false;
}

int
hashFunction(char word[LENGTH + 1])
{
    int n = (word[0] - 'a'); // first letter of each word is a bucket
    return (n % HASHTABLE_SIZE); // make sure it doesn't go over the max size of the hashtable
}

Originally Posted by durrr

It seems to me that the loop is fine, since the printf works in it, but please correct me if I'm wrong as I don't think I understand you.

Using "<=" in a for-loop to go through an array is in most cases wrong.
As you can see in your output you allocate memory for root[0] up to root[25]. But if you count the lines (look at the line numbers), you will notice that you allocate memory for 26 elements but you have declared root to hold only 25 elements. You have to use "<" in your comparison.
Just because you are lucky and it seems to work doesn't mean it's correct.

Originally Posted by durrr

It seems the memory doesn't get allocated though because when it reaches the hash_bucket number 1, it segfaults.

Let's walk through your code:
Line 56 declares an array of pointers to struct node "root" and line 58 does the same for "conductor". Both arrays are uninitialized.
Lines 60-65 only set the pointers in "root" to a valid memory block.
Line 70 calculates "hash_bucket" for the first word which is 0.
Line 77 assigns root[0] to conductor[0] meaning that both pointers point to the same object (BTW: 76 and 77 shouldn't be inside the for-loop because "hash_bucket" won't change and thus both lines do the same on every iteration).
Line 92-99 are unnecessary because conductor[0]->next is NULL. You've only read one word yet. That's why you don't get the line "traverse bucket 0" in your output.

Now the really problematic part:
The while-loop starting at 101 reads another word and on 103 you calculate its hash. Since the words in your dictionary are ordered alphabetically, the first 9126 words start with "a" and the hash will always be 0 (like the first word). Thus on line 114 (the line which is shown in your valgrind output) conductor[0]->next is a valid pointer. But as soon as you get the first word starting with "b" the hash will be 1 and now you want to dereference the pointer in conductor[1] which you have never initialized. The result is the seg fault.

You have another problem on line 130 (which you weren't able to reach yet when running the program): "root[hash_bucket]" will always point to the head of your list, thus on every iteration you overwrite the word you have stored there before. You want to use "conductor[hash_bucket]" here.

Bye, Andreas