0

I have implemented load, check, and unload for dictionary.c using trie, and I am suffering a segmentation fault. The error happens inside load function, or, to be more precise, inside the function called un_node, a recursive function I call in unload. The line if(cursor -> children[a] != NULL) pops up when I run debug50. Although I did not malloc my root/head node as a global (I just wrote node *root;), isn't the memory allocated in load function extant?

I did check whether I null pointed every children of next_node and root after mallocking them.

Regarding the un_node function, I am not sure whether I should free(cursor); return; inside the for loop or outside the for loop.

    /**
 * Implements a dictionary's functionality.
 */

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


#include "dictionary.h"

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

 //create a trie data type
   typedef struct node
   {
        bool is_word;
        struct node *children[27]; //this is a pointer too!  
   }node; 

 //function prototype

 void un_node (node *node_name);
 void nullpoint (node *node_name);

 //initialize root
    node *root;       


bool check(const char *word)
{
    //create a trav pointer
    node *cursor = root;        
    int i = 0;

    while(word[i] != '\0')
    {
            char ch = word[i]; 
            int index = (tolower(ch) - 97);

            if(index == -58)
            {
                index = 26;
            }

           //validate index
           if(index < 0 || index > 26)
           {
               printf("Error: index\n");
               return false;
           }

        if(cursor -> children[index] != NULL)
            {
                cursor = cursor -> children[index];
                i++;
            }
        else
            {
                //if it is NULL then word is not in dictionary
                return false;
            }

    }
    //end of word, so check if there is a flag from load
    if(cursor -> is_word == true)
    {
        return true;
    }
    else
        return false;

}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    //malloc space for root node
    root = malloc(sizeof(node));

    //all of root's children point to NULL now
    nullpoint (root);

   //open dictionary
   FILE *dptr = fopen(dictionary, "r");
   if(dptr == NULL)
   {
       return false;
   }


   char *c = malloc(sizeof(char));
   node *next_node;

   //scan the file char by char until end and store it in c
   while(fscanf(dptr,"%s",c) != EOF)
   {

       //in the beginning of every word, make a traversal pointer copy of root so we can always refer back to root
       node *trav = root;

       //when temp increments, it moves on to next character of word
       char *temp;
       temp = c;

       //repeat for every word
       while ((*temp) != '\0')
       {
            //convert char into array index
           int alpha = (tolower(*temp) - 97);

           //handle apostrophe
           if(alpha == -58)
           {
               alpha = 26;
           }

           //validate alpha
           if(alpha < 0 || alpha > 26)
           {
               printf("Error: alpha\n");
               return false;
           }


           //if array element is pointing to NULL, i.e. it hasn't been open yet,
            if(trav -> children[alpha] == NULL)
                {

                //then malloc next node and point it with the cursor. 
                next_node = malloc(sizeof(node));

                //initialize children of newly allocated node    
                nullpoint(next_node);

                //cursor points at the newly allocated memory
                trav -> children[alpha] = next_node; 
                //cusor moves on
                trav = trav -> children[alpha];//null?

                //quit if malloc returns null
                if(next_node == NULL)
                    {
                        printf("Could not open dictionary");
                        return false;
                    }

                }

            else
                {
                //if an already existing path, just go to it
                trav = trav -> children[alpha];
                } 

                //increment the address of temp variable
                temp++;
        }
        //a word is loaded. 
        trav -> is_word = true;

   }
   //success
   fclose(dptr);
   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)
{
    node *cursor = root;
    un_node(cursor);
    return true;
}

void un_node (node *cursor)
{
    for(int a = 0; a<27; a++)
    {
        //if the children's pointee is not NULL, i.e. this is not a dead end
        if(cursor -> children[a] != NULL)
        {
            //go back to the beginning (with cursor -> children[a] as new argument) restart this function
            un_node(cursor -> children[a]);
        }

    }
    //and when it is dead end, start to   
    free(cursor);
    return;
}

//function that points all children of node to NULL
void nullpoint (node *node_name)
{
    for(int t=0;t<27;t++)
    {
        node_name -> children[t] = NULL;
    }
}
0

In

char *c = malloc(sizeof(char));

you allocate space for one char, and in

fscanf(dptr,"%s",c)

you ask fscanf to put a string of arbitrary length in that one-char memory block. Sounds unpleasent. Per problem specification, the string can be at most LENGTH+1 bytes (maximum word length of LENGTH plus the null terminator).

That memory also is never freed. You can avoid some of this by declaring c on stack, as char c[LENGTH+1];. Using malloc just has no advantage in this case.

While you initialise the pointers on a new node, you don't ensure that is_word initially is set to false. This might allow some faulty words to slip through detection, but in a random way (not necessarily consistent between runs, and not between your and another compiler or computer).

2
  • That did solve my seg-fault! But do you know why when I ran debug50 it stopped at this lien: "if(cursor -> children[a] != NULL)" as if this was the cause? – Jason Lim Sep 7 '17 at 16:26
  • fscanf when called with a pointer to the heap (where you also allocate your nodes) might have overwritten the first few pointers in your root node, the string interpreted as pointers then probably points somewhere you may not access. – Blauelf Sep 7 '17 at 17:50

You must log in to answer this question.

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