unloading a trie

atlantis43 · 02-18-2014, 10:39 PM

Trying to learn about tries in C-programming, and hope someone can help me understand how to parse the progression to subsequent levels of the ‘tree’ portion of the trie.
I’m trying to write an unload() function for a trie-based dictionary, and am providing what I think are the appropriate sections of code with which I'm working:
Structure declarations:

Code:

#define ALPHABET_SIZE (27)
#define LENGTH 7
#define CHAR_TO_INDEX(c) (tolower((int)c) - (int)'a')
char* word; 

// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
    int value;
    trie_node_t *children[ALPHABET_SIZE];
};
 
// trie ADT
typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;
    int count;
};

Function call:

Code:

unload(&trie);

Function I’ve written (so far), which reaches first ‘children’ level

Code:

void unload(trie_t *pTrie)
{
trie_node_t *pUnload;
    pUnload = pTrie->root;
            //make sure trie is present
if(pUnload !=NULL)
    {
    int alpharray;
    for(alpharray = 0; alpharray<ALPHABET_SIZE ; alpharray++)
    {
   //this refers to first level array of trie
 if( pUnload->children[k]!=NULL )

Question is "How do I parse pointers to the subsequent levels of "children": eg., where pTrie->count =2, 3, 4, etc.?
Thanks for any help.
Richard

NevemTeve · 02-19-2014, 03:21 AM

This thing is called recursion:

Code:

void free_all_core (struct trie_node *p)
{
    int i;

    for (i= 0; i<ALPHABET_SIZE; ++i) {
        if (p->children[i]) {
            free_all_core (p->children[i]);
            p->children[i]= NULL;  /* just to be fool-proof */
        }
    }
    free (p);
}

void free_all (struct trie *t)
{
    if (t) {
        if (t->root) free_all_core (t->root);
        free (t);
   }
}

atlantis43 · 02-19-2014, 07:52 AM

I knew that recursion would be necessary for efficiency, but didn't realize how to do the above parsing (and definitely didn't realize that two separate functions would be needed to free the nodes and the root). Now I just have to clarify (to myself) how this recursive code affects the "highest" level first, and then proceeds backward to the "root". Thanks again for this clarification.
Richard

atlantis43 · 02-19-2014, 09:03 AM

Quote:

Originally Posted by NevemTeve

This thing is called recursion:

Code:

void free_all_core (struct trie_node *p)
{
    int i;

    for (i= 0; i<ALPHABET_SIZE; ++i) {
        if (p->children[i]) {
            free_all_core (p->children[i]);
            p->children[i]= NULL;  /* just to be fool-proof */
        }
    }
    free (p);
}

void free_all (struct trie *t)
{
    if (t) {
        if (t->root) free_all_core (t->root);
        free (t);
   }
}

Getting a coredump when running your suggestion.
I've declared following pointers in main():

Code:

    trie_t trie;
    struct trie_node trienode;

and am calling functions as below:

Code:

free_all_core (&trienode);
free_all (&trie);

also getting info as follows on terminal:
*** Error in `./trietest': free(): invalid pointer: 0xbfd7a6d0 ***
Anything that I've forgotten?

NevemTeve · 02-19-2014, 10:03 AM

You should decide which elements are static, and which ones are malloc'ed. Only the malloc'ed ones can be freed, obviously.

Code:

void free_trie (struct trie *t);

int main (void)
{
    trie mytrie;

/* initialize */
    memset (&mytrie, 0, sizeof (mytrie));

/* add/delete/print elements etc */
   ...

/* free everything */
   free_trie (&mytrie);
}

void free_trie_recursive (struct trie_node *p)
{
    int i;

    for (i= 0; i<ALPHABET_SIZE; ++i) {
        if (p->children[i]) {
            free_trie_recursive (p->children[i]);
            p->children[i]= NULL;  /* just to be fool-proof */
        }
    }
    free (p);
}

void free_trie (struct trie *t)
{
    if (t) {
        if (t->root) free_trie_recursive (t->root);
/****   free (t); not in this context! ****/
   }
}

atlantis43 · 02-19-2014, 10:53 AM

Thanks so much for your persistence with my inattention to detail. I was using an incorrect call in main(): free_trie_recursive(), which screwed up everything.