Mercurial > hg > ucx / file diff

--- a/src/cx/tree.h	Sun Oct 06 12:40:44 2024 +0200
+++ b/src/cx/tree.h	Sun Oct 06 13:37:05 2024 +0200
@@ -811,14 +811,6 @@
  */
 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
@@ -970,21 +962,6 @@
 );
 
 /**
- * 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
@@ -1199,8 +1176,9 @@
  * 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
- * applied when re-linking the children of the removed node.
+ * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode()
+ * 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
@@ -1227,7 +1205,7 @@
  * @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
@@ -1247,6 +1225,99 @@
 __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