ucx: comparison src/cx/tree.h

-:9533fc293aea
+:72db8e42b95e
 /**
 * The class definition for arbitrary trees.
 */
 struct cx_tree_class_s {
 /**
-* Destructor function.
-*
-* Implementations SHALL invoke the node destructor functions if provided
-* and SHALL deallocate the tree memory.
-*/
-void (*destructor)(struct cx_tree_s *);
-/**
 * Member function for inserting a single element.
 *
 * Implementations SHALL NOT simply invoke \p insert_many as this comes
 * with too much overhead.
 */
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 );
 /**
-* Destroys the tree structure.
-*
-* \attention This function will only invoke the destructor functions
-* on the nodes, if specified.
-* It will NOT additionally free the nodes with the tree's allocator, because
-* that would cause a double-free in most scenarios.
-*
-* @param tree the tree to destroy
-*/
-__attribute__((__nonnull__))
-static inline void cxTreeDestroy(CxTree *tree) {
-tree->cl->destructor(tree);
-}
-/**
 * Inserts data into the tree.
 *
 * \remark For this function to work, the tree needs specified search and
 * create functions, which might not be available for wrapped trees
 * (see #cxTreeCreateWrapped()).
 /**
 * A function that is invoked when a node needs to be re-linked to a new parent.
 *
 * When a node is re-linked, sometimes the contents need to be updated.
-* This callback is invoked by #cxTreeRemove() so that those updates can be
+* This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
-* applied when re-linking the children of the removed node.
+* so that those updates can be applied when re-linking the children of the
+* removed node.
 *
 * @param node the affected node
 * @param old_parent the old parent of the node
 * @param new_parent the new parent of the node
 */
 * @param relink_func optional callback to update the content of each re-linked
 * node
 * @return zero on success, non-zero if \p node is the root node of the tree
 */
 __attribute__((__nonnull__(1,2)))
-int cxTreeRemove(
+int cxTreeRemoveNode(
 CxTree *tree,
 void *node,
 cx_tree_relink_func relink_func
 );
 * @param node the node to remove
 */
 __attribute__((__nonnull__))
 void cxTreeRemoveSubtree(CxTree *tree, void *node);
+/**
+* Destroys a node and re-links its children to its former parent.
+*
+* If the node is not part of the tree, the behavior is undefined.
+*
+* It is guaranteed that the simple destructor is invoked before
+* the advanced destructor.
+*
+* \attention This function will not free the memory of the node with the
+* tree's allocator, because that is usually done by the advanced destructor
+* and would therefore result in a double-free.
+*
+* @param tree the tree
+* @param node the node to destroy (must not be the root node)
+* @param relink_func optional callback to update the content of each re-linked
+* node
+* @return zero on success, non-zero if \p node is the root node of the tree
+*/
+__attribute__((__nonnull__(1,2)))
+int cxTreeDestroyNode(
+CxTree *tree,
+void *node,
+cx_tree_relink_func relink_func
+);
+/**
+* Destroys a node and it's subtree.
+*
+* It is guaranteed that the simple destructor is invoked before
+* the advanced destructor, starting with the leaf nodes of the subtree.
+*
+* When this function is invoked on the root node of the tree, it destroys the
+* tree contents, but - in contrast to #cxTreeDestroy() - not the tree
+* structure, leaving an empty tree behind.
+*
+* \note The destructor function, if any, will \em not be invoked. That means
+* you will need to free the removed subtree by yourself, eventually.
+*
+* \attention This function will not free the memory of the nodes with the
+* tree's allocator, because that is usually done by the advanced destructor
+* and would therefore result in a double-free.
+*
+* @param tree the tree
+* @param node the node to remove
+* @see cxTreeDestroy()
+*/
+__attribute__((__nonnull__))
+void cxTreeDestroySubtree(CxTree *tree, void *node);
+/**
+* Destroys the tree contents.
+*
+* It is guaranteed that the simple destructor is invoked before
+* the advanced destructor, starting with the leaf nodes of the subtree.
+*
+* This is a convenience macro for invoking #cxTreeDestroySubtree() on the
+* root node of the tree.
+*
+* \attention Be careful when calling this function when no destructor function
+* is registered that actually frees the memory of nodes. In that case you will
+* need a reference to the (former) root node of the tree somewhere or
+* otherwise you will be leaking memory.
+*
+* @param tree the tree
+* @see cxTreeDestroySubtree()
+*/
+#define cxTreeClear(tree) cxTreeDestroySubtree(tree, tree->root)
+/**
+* Destroys the tree structure.
+*
+* The destructor functions are invoked for each node, starting with the leaf
+* nodes.
+* It is guaranteed that for each node the simple destructor is invoked before
+* the advanced destructor.
+*
+* \attention This function will only invoke the destructor functions
+* on the nodes.
+* It will NOT additionally free the nodes with the tree's allocator, because
+* that would cause a double-free in most scenarios where the advanced
+* destructor is already freeing the memory.
+*
+* @param tree the tree to destroy
+*/
+__attribute__((__nonnull__))
+static inline void cxTreeDestroy(CxTree *tree) {
+if (tree->root != NULL) {
+cxTreeDestroySubtree(tree, tree->root);
+}
+cxFree(tree->allocator, tree);
+}
 #ifdef __cplusplus
 } // extern "C"
 #endif
 #endif //UCX_TREE_H

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h