0

I read lot of questions and answers about the "load"segmentation errors in pset5 but I still experience some difficulties fixing it. I tried to make sure there are no garbage values by initializing everything to NULL but you'll tell me if i did it correctly. I've decided on using a trie for this pset.

In the beginning I declare the following:

   typedef struct node
{ 
   bool is_word;
   struct node* children[27];

}
node;


node* root =NULL;
node* tempPtr = NULL;

int dictionary_size=0;
FILE* dict;

and then here is what I do in "load":

bool load(const char* dictionary)
   {   
     root=(struct node*)malloc(sizeof(node));

    for (int i = 0; i < 27; i++)
       {

          root->children[i]=NULL;


       }
  tempPtr=(struct node*)malloc(sizeof(node));
  tempPtr = root;
  for (int j = 0; j<27; j++)
      {
        tempPtr->children[j]=NULL;
      }

  dict = fopen(dictionary, "r");

  if (dict==NULL)
     {
        printf("Sorry, unable to open file\n");

    }


  for (int c = fgetc(dict); c != EOF; c = fgetc(dict))
    {

       if (c == '\'' && c !='\n')

        {

            tempPtr->children[c-'a'] = NULL;

          if(tempPtr->children[c-'a']== NULL) 
             {

            tempPtr->children[c-'a']=(struct node*)malloc(sizeof(node));

             }

          tempPtr=tempPtr->children[c-'a'];
          dictionary_size++;

    }

   else if(c=='\n')
   {
     tempPtr->is_word=true; 

   }

}
return false;

}

So basically Valgrind is telling me "Could not load /home/cs50/pset5/dictionaries/large"

The program is compiling fine and then gives me segmentation fault when I try to run it with austinpowers.txt.

I guess I'm not doing the initialization of the pointers correctly but I still cannot see the exact problem.

Any ideas where the problem(s) may be?

Thanks in advance!

UPDATE

Ok, two things: firstly, I fixed the problem with the "could not load large dictionary"message. basically, I set the "return false"statement at the end of the load function to "return true".

Secondly, I followed @Cliff B suggestions but I'm still getting the same errors. I guess I'm still not handling properly the capital letters? Now i get the segmentation fault again at the tempPtr->children[letter-'a']=NULL line or from time to time I get an error when I try to set tempPtr->is_word=true. Valgrind is saying that the address hasn't been stack'd, malloc'd or free'd and that the access is not within the mapped region. I honestly don't know what I'm doing wrong anymore. Here is the result in load after some corrections:

    bool load(const char* dictionary)
    {   

// TODO
 root=(struct node*)malloc(sizeof(node));

for (int i = 0; i < 27; i++)
{

   root->children[i]=NULL;

}

tempPtr=(struct node*)malloc(sizeof(node));
tempPtr = root;
for (int j = 0; j<27; j++)
{
    tempPtr->children[j]=NULL;

}

dict = fopen(dictionary, "r"); 


if (dict==NULL)
{
   printf("Sorry, unable to open file\n");
   return false;

}

int letter=0;

//for every word from the dictionary iterate over the trie
for (int c = fgetc(dict); c != EOF; c = fgetc(dict))
{
       letter = tolower(c);


   if (letter != '\'' || letter !='\n')

    {  

        if(tempPtr->children[letter-'a']== NULL) 
        {

            tempPtr->children[letter-'a']=(struct node*)malloc(sizeof(node));
            tempPtr->children[letter-'a']=NULL;

        //then continue
        }


        tempPtr=tempPtr->children[letter-'a'];


    }

   //if at the end of the word set is_word to true;
   else if(letter=='\n')
   {
        tempPtr->is_word=true; 
        dictionary_size++;
        tempPtr=root;

   }

}
return true;

}

Again, any suggestions on how to improve the code are most welcome! :)

UPDATE 2

I realised I overlooked something very small but very important (it seems to me this is often the case in programming). I was assigning NULL the wrong way, syntax-wise: tempPtr->children[letter-'a']=NULL and not ==NULL. Also the way I was checking for the end of the word wasn't complete and wasn't really doing much. Neither was dictionary_size as it wasn't inside the right if-condition. There were other issues as well but fixed them. Program working fine now!

1 Answer 1

1

I see several problems. First, look at this:

if (c == '\'' && c !='\n')

The only time this will ever be true is when you see an apostrophe. No letter will ever get past this. Perhaps you meant to type c != '\''?

Now,

tempPtr->children[c-'a'] = NULL;

What happens if c is a capital letter? You end up with a negative number for the index of children. That means you're accessing an invalid memory address, causing a seg fault. Coincidentally, the very first letter in Austinpowers.txt is a capital letter. Didn't the pset instructions say to be sure to handle capital and lowercase letters when checking spelling?

You are also not initializing anything in your nodes after using malloc to allocate the memory for them. Testing for NULLs on them will fail because they contain garbage data instead of nulls. When you declare a new node, you need to either initialize the children pointers to NULL or use calloc instead.

Ther may be other issues, but this should get you going.

As for not opening the dictionary, you should check to see if the dictionary file actually exists at the location that is hardcoded into your program.

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

4
  • I thought that I'm initializing the children to NULL with the following code with for (int j = 0; j<27; j++) { tempPtr->children[j]=NULL; }
    – GiP
    Commented Nov 19, 2015 at 18:58
  • OK, that was an error on my part, you are initializing it. I must have been looking at too many things. However the other issues remain. Most importantly, if you have a capital letter, like 'A', then for tempPtr->children[c-'a'] 'A' - 'a' = 65 - 97 = -32, so you're trying to access tempPtr->children[-32], an invalid location.
    – Cliff B
    Commented Nov 19, 2015 at 19:06
  • Ok, I updated my initial post :) Not sure this is the right way to convert the letters since I'm getting the same errors.
    – GiP
    Commented Nov 19, 2015 at 20:04
  • Btw I'm checking the capital and lowercase in "check" (that I haven't uploaded in this post), not in "load". For now, valgrind gives me errors in "load", I haven't reached the point of actually spell-checking. In any case, what you're saying makes sense but I'm still trying to make it work as you would see by the update above :)
    – GiP
    Commented Nov 19, 2015 at 21:05

You must log in to answer this question.

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