0

Every time I run ./speller, it gives me this error:

* Error in `./speller': free(): invalid pointer: 0x00007f2e3ac72ac8 * Aborted

When I check my large dictionary after this, it is totally erased. I know there is something wrong with my check function (after some experiments), but I just want to know why and how my large dictionary gets erased.

I am using a trie for this pset.

Thank you for your attention.

EDIT: Added part of my code

    typedef struct trienode
{
    struct trienode *parent;
    struct trienode *children[27];
    bool isleaf;
}
trienode;

//creates a pointer to the first structure
trienode *ROOT;

//create int pointer to take note of workcount (wcount)
int *WCOUNT;

Load Function

bool load(const char *dictionary)
{
//open the dictionary file
FILE *dicttext = fopen(dictionary, "w");
if (dicttext == NULL)
{
    fprintf(stderr, "Could not create %s.\n", dictionary);
    return false;
}

//allocate memory for ROOT
ROOT = malloc(sizeof(trienode));
//initialises the data inside the root structure
ROOT->isleaf = false;
ROOT->parent = NULL;
for (int j = 0; j < 27; j++)
{
    ROOT->children[j] = NULL;
}
//initialise wordcount
WCOUNT = malloc(sizeof(int));
*WCOUNT = 0;

//pointer for traversing
trienode *traverse = ROOT;

//start reading the word from the text. NOTE: make sure that all upper case letters char are tolower-ed first
for (int c = fgetc(dicttext); c != EOF; c = fgetc(dicttext))
{
    while (c != '\0')
    {
        if (isalpha(c) != 0)
        {
            c = tolower(c);
            c = INDEX(c);
        }

        else if (c == '\'')
        {
            c = 26;
        }

        //if the path is not yet opened
        if (traverse->children[c] == NULL)
        {
            //create new pointer
            traverse->children[c] = malloc(sizeof(trienode));
            //check if pointer was created properly
            if (traverse->children[c] == NULL)
            {
                fprintf(stderr, "Error creating Pointer\n");
                return false;
            }
            //point parent node of children to the parent 
            traverse->children[c]->parent = traverse;
            traverse->isleaf = false;
            //points traverse to the child
            traverse = traverse->children[c];
            //makes the children pointers NULL through iteration
            for (int j = 0; j < 27; j++)
            {
                traverse->children[j] = NULL;
            }
        }
        //if the path is open
        else
        {
            traverse = traverse->children[INDEX(c)];
        }

    }
    //wordcount + 1
    *WCOUNT += 1;
    //inform computer that it is not a leaf
    traverse->isleaf = true;
}
//free memory
free(traverse);
return true;
}

Check Function

    /**
* Returns true if word is in dictionary else false.
*/
bool check(const char *word)
{
//creates a pointer called traverse which points to the first structure of the trie
trienode *traverse = ROOT;
//iterate through the word and move down the trie until the second last letter of the word 
for (int i = 0, l = strlen(word); i < l; i++)
{
    int c = word[i];
    if (isalpha(c) != 0)
    {
        c = tolower(c);
        c = INDEX(c);
    }

    else
    {
        c = 26;
    }

    if (traverse->children[c] == NULL)
    {
        return false;
    }

    else 
    {
        traverse = traverse->children[c];
    }
}

//check if the end of the word really tallys with the end of a word found in the dictionary
if (traverse->isleaf == true)
{
    return true;
}
free(traverse);
return false;
}
1

You don't need a parent pointer, you always walk the trie from the root, never back.

Your while loop does not make too much sense to me. In the first iteration, c is a regular character, but after that, it has been transformed to an index, and you don't read another character in the loop. Also please note that the words in the dictionary are separated by newline characters, not '\0'.

I did it a bit differently in the outer loop:

  • on '\n', I ended the word (traverse->isleaf = true;), and reset the cursor (traverse = ROOT;)
  • else I'd traverse the trie one step at a time, if needed creating the node to traverse to, so no inner loop

You should swap the

traverse->isleaf = false;

and

traverse = traverse->children[c];

else you'd set isleaf for the current cursor, not for the newly malloced node.

Don't free traverse in check or load, in both cases it points to a node in your trie. In check, skip that if (traverse->isleaf == true), and just return traverse->isleaf;.

It's easier to store the word count in an int rather than a pointer to int. Dynamic memory allocation is useful only if the amount of memory allocated is previously unknown, or if variables should survive the end of the function (so cannot be placed on function's stack), but cannot be made global (for example because you have multiple of them). Here, you have one global variable of known size, so keeping track in a simple int is sufficient.

3
  • Thanks for your answer. As an extension of your point on the newline character, is it correct me to say that \0 is only added at the end of character strings? – joshwong Feb 24 '17 at 14:02
  • Also, how does the compiler actually read \n and other newline characters? Does it have a size (in bits)? – joshwong Feb 24 '17 at 14:03
  • '\0' is a character that is used to determine the end of a string, so you don't have to keep the length somewhere. Pascal uses the first byte of the string for storing the length (means you instantly have the length, but strings are limited to 255 characters). Just like the '\0', '\n' is a regular character, of value 0x0A or decimal 10. Handling of newlines gets interesting only if you have DOS/Windows based files around. Those use "\r\n" (0x0D0A) for line end. A common way is ignoring the '\r' and taking the '\n' for newlines, works in most cases. Old macs used '\r' only. – Blauelf Feb 24 '17 at 14:16

You must log in to answer this question.

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