- *
- * @return If no insertion happened, the found element.
- * If an insertion happened, then either key or NULL is returned (which
- * one it is depends on the tree state and the implementation, you
- * should make no assumptions that it's one or the other in the code).
+ * @param next Used to allocate and free AVTreeNodes. For insertion the user
+ * must set it to an allocated and zeroed object of at least
+ * av_tree_node_size bytes size. av_tree_insert() will set it to
+ * NULL if it has been consumed.
+ * For deleting elements *next is set to NULL by the user and
+ * av_tree_node_size() will set it to the AVTreeNode which was
+ * used for the removed element.
+ * This allows the use of flat arrays, which have
+ * lower overhead compared to many malloced elements.
+ * You might want to define a function like:
+ * @code
+ * void *tree_insert(struct AVTreeNode **rootp, void *key,
+ * int (*cmp)(void *key, const void *b),
+ * AVTreeNode **next)
+ * {
+ * if (!*next)
+ * *next = av_mallocz(av_tree_node_size);
+ * return av_tree_insert(rootp, key, cmp, next);
+ * }
+ * void *tree_remove(struct AVTreeNode **rootp, void *key,
+ * int (*cmp)(void *key, const void *b, AVTreeNode **next))
+ * {
+ * av_freep(next);
+ * return av_tree_insert(rootp, key, cmp, next);
+ * }
+ * @endcode
+ * @return If no insertion happened, the found element; if an insertion or
+ * removal happened, then either key or NULL will be returned.
+ * Which one it is depends on the tree state and the implementation. You
+ * should make no assumptions that it's one or the other in the code.