CODEWITHSUNDEEP
cposix
Marcus Harrison
Marcus Harrison

Reputation: 869

How can you clean an entire POSIX tree with only POSIX functions?

Having populated a POSIX binary tree with tsearch, how is it possible to clean-up the entire tree? GCC provides tdestroy as an extension, but if you want to use POSIX-only functions how can you do it?

My current implementation uses twalk to walk the tree and, for endorder and leaf nodes, calls tdelete, but this understandably shows warnings about const-correctness:

static void free_tree(const void *node, const VISIT which, const int depth)
{
        struct search_entry *entry;
        switch (which) {
                case endorder:
                case leaf:
                        entry = *(struct search_entry **)node;
                        tdelete(entry->key, &node, search_entry_compare);
                        free(entry);
        }
}

What was the expected approach for POSIX-compliant applications?

Upvotes: 3

Views: 388

Answers (2)

Jonathan Leffler
Jonathan Leffler

Reputation: 753675

The POSIX description of the tsearch() family of functions has an informative Examples section which shows how the standard thinks you can delete all the elements of a tree (as part of a bigger, complete example of how to use the functions):

/* Delete all nodes in the tree */
while (root != NULL) {
    elementptr = *(struct element **)root;
    printf("deleting node: string = %s,  count = %d\n",
           elementptr->string,
           elementptr->count);
    tdelete((void *)elementptr, &root, delete_root);
    free(elementptr);
}

Basically, it repeatedly deletes the root node with tdelete() until there is no longer a root node to delete. The delete_root() function is also shown — it is a no-op that returns 0 for success.

We can debate the merits (or lack of them) for the cast in the call to tdelete().

Upvotes: 6

jilles
jilles

Reputation: 11232

The proposed solution of calling tdelete() from twalk()'s action conflicts with the POSIX requirement on the application that action and compar not change the tree. In practice, a use after free or incomplete cleanup is likely.

The best I can think of is either not using tsearch/tfind/tdelete/twalk or allocating new memory to store twalk() results and using tdelete() afterwards.

Not using tsearch/tfind/tdelete/twalk may also allow data structures such as radix tries and hash tables that tend to be more efficient on modern architectures than binary trees.

Upvotes: 1

Related Questions