如何使用仅限于POSIX函数清理整个POSIX树？

Question

如果使用 tsearch 填充了一个 POSIX 二叉树，如何清理整个树？GCC 提供了 tdestroy 扩展函数，但如果想只使用 POSIX 函数该怎么办？

我的当前实现使用 twalk 遍历整个树，在遍历到 endorder 和 leaf 节点时调用 tdelete，但这会显示有关常量正确性的警告：

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);
        }
}

POSIX兼容应用程序的预期方法是什么？

- Marcus Harrison

Answer 1

POSIX对tsearch()函数族的描述中，有一个信息丰富的示例部分展示了标准如何认为可以删除树中的所有元素（作为如何使用这些函数的完整示例的一部分）:

/* 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);
}

基本上，它使用 tdelete() 反复删除根节点，直到没有根节点可删除。 delete_root() 函数也被展示了 - 它是一个无操作函数，用于返回成功的0。

我们可以就调用 tdelete() 中的强制类型转换进行争论（或者缺乏这种转换）。

- Jonathan Leffler

---

很遗憾，Linux程序员手册没有像这样的内容；截至4.16版本，它只介绍了如何公开和使用tdestroy。 - S.S. Anne

是的，tdestroy 的 3posix 手册没有提到这一点，这将非常有用。 感谢您的回答！ - Marcus Harrison

Answer 2

提议使用在 twalk() 的 action 中调用 tdelete() 的解决方案与 POSIX 对应用程序的要求产生冲突，即 action 和 compar 不得更改树。实际上，使用后释放或不完全清理的情况很可能发生。

我能想到的最好的方法是不使用 tsearch/tfind/tdelete/twalk 或分配新内存来存储 twalk() 的结果，然后再使用 tdelete()。

不使用 tsearch/tfind/tdelete/twalk 也可以使用基数 tries 和哈希表等数据结构，这些数据结构在现代架构上比二叉树更有效率。

- jilles

---

除非您确实遇到性能问题并且已经测量出它会产生差异，否则我不会避免使用tsearch，因为“基数尝试和哈希表[...]在现代架构上往往更有效”。 tsearch API非常易于使用，最优的大O，不依赖于键类型（而基数是），并且倾向于使代码非常轻巧和简单。 - R.. GitHub STOP HELPING ICE