Mercurial > hg > ucx / changeset

--- a/src/Makefile	Sun Sep 29 23:08:40 2024 +0200
+++ b/src/Makefile	Mon Sep 30 19:17:19 2024 +0200
@@ -130,8 +130,8 @@
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -c $<
 
-$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h cx/iterator.h \
- cx/array_list.h cx/list.h cx/collection.h cx/allocator.h cx/compare.h
+$(build_dir)/tree$(OBJ_EXT): tree.c cx/tree.h cx/common.h cx/collection.h \
+ cx/allocator.h cx/iterator.h cx/compare.h cx/array_list.h cx/list.h
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -c $<
 

--- a/src/cx/tree.h	Sun Sep 29 23:08:40 2024 +0200
+++ b/src/cx/tree.h	Mon Sep 30 19:17:19 2024 +0200
@@ -741,11 +741,6 @@
     cx_tree_search_func search;
 
     /**
-     * The total size of a node, including the element size.
-     */
-    size_t node_size;
-
-    /**
      * The number of currently stored elements.
      */
     size_t size;
@@ -867,6 +862,9 @@
  * The specified \p allocator will be used for creating the tree struct
  * and SHALL be used by \p create_func to allocate memory for the nodes.
  *
+ * \attention This function will also register a simple destructor which
+ * will free the nodes with the allocator's free() method.
+ *
  * @param allocator the allocator that shall be used
  * @param create_func a function that creates new nodes
  * @param search_func a function that compares two nodes
@@ -878,6 +876,7 @@
  * @param loc_next offset in the node struct for the next pointer
  * @return the new tree
  * @see cxTreeCreateSimple()
+ * @see cxTreeCreateWrapped()
  */
 __attribute__((__nonnull__, __warn_unused_result__))
 CxTree *cxTreeCreate(
@@ -916,6 +915,37 @@
 }
 
 /**
+ * Creates a new tree structure based on an existing tree.
+ *
+ * The specified \p allocator will be used for creating the tree struct
+ * and SHALL be used by \p create_func to allocate memory for the nodes.
+ *
+ * \attention This function will create an incompletely defined tree structure
+ * where neither the create function, the search function, nor a destructor
+ * will be set. If you wish to use any of this functionality for the wrapped
+ * tree, you need to specify those functions afterwards.
+ *
+ * @param root the root node of the tree that shall be wrapped
+ * @param loc_parent offset in the node struct for the parent pointer
+ * @param loc_children offset in the node struct for the children linked list
+ * @param loc_last_child optional offset in the node struct for the pointer to
+ * the last child in the linked list (negative if there is no such pointer)
+ * @param loc_prev offset in the node struct for the prev pointer
+ * @param loc_next offset in the node struct for the next pointer
+ * @return the new tree
+ * @see cxTreeCreate()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+CxTree *cxTreeCreateWrapped(
+        void *root,
+        ptrdiff_t loc_parent,
+        ptrdiff_t loc_children,
+        ptrdiff_t loc_last_child,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next
+);
+
+/**
  * Destroys the tree structure.
  *
  * \attention This function will only invoke the destructor functions
@@ -927,7 +957,147 @@
  * @param tree the tree to destroy
  */
 __attribute__((__nonnull__))
-void cxTreeDestroy(CxTree *tree);
+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()).
+ *
+ * @param tree the tree
+ * @param data the data to insert
+ * @return zero on success, non-zero on failure
+ */
+__attribute__((__nonnull__))
+static inline int cxTreeInsert(
+        CxTree *tree,
+        const void *data
+) {
+    return tree->cl->insert_element(tree, data);
+}
+
+/**
+ * Inserts elements provided by an iterator efficiently 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()).
+ *
+ * @param tree the tree
+ * @param iter the iterator providing the elements
+ * @param n the maximum number of elements to insert
+ * @return the number of elements that could be successfully inserted
+ */
+__attribute__((__nonnull__))
+static inline size_t cxTreeInsertIter(
+        CxTree *tree,
+        struct cx_iterator_base_s *iter,
+        size_t n
+) {
+    return tree->cl->insert_many(tree, iter, n);
+}
+
+/**
+ * Inserts an array of data efficiently 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()).
+ *
+ * @param tree the tree
+ * @param data the array of data to insert
+ * @param elem_size the size of each element in the array
+ * @param n the number of elements in the array
+ * @return the number of elements that could be successfully inserted
+ */
+__attribute__((__nonnull__))
+static inline size_t cxTreeInsertArray(
+        CxTree *tree,
+        const void *data,
+        size_t elem_size,
+        size_t n
+) {
+    if (n == 0) return 0;
+    if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
+    CxIterator iter = cxIterator(data, elem_size, n);
+    return tree->cl->insert_many(tree, cxIteratorRef(iter), n);
+}
+
+/**
+ * Searches the data in the specified tree.
+ *
+ * \remark For this function to work, the tree needs a specified search
+ * function, which might not be available wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+__attribute__((__nonnull__))
+static inline void *cxTreeFind(
+        CxTree *tree,
+        const void *data
+) {
+    return tree->cl->find(tree, tree->root, data);
+}
+
+/**
+ * Searches the data in the specified subtree.
+ *
+ * \note When \p subtree_root is not part of the \p tree, the behavior is
+ * undefined.
+ *
+ * \remark For this function to work, the tree needs a specified search
+ * function, which might not be the case for wrapped trees
+ * (see #cxTreeCreateWrapped()).
+ *
+ * @param tree the tree
+ * @param data the data to search for
+ * @param subtree_root the node where to start
+ * @return the first matching node, or \c NULL when the data cannot be found
+ */
+__attribute__((__nonnull__))
+static inline void *cxTreeFindInSubtree(
+        CxTree *tree,
+        const void *data,
+        void *subtree_root
+) {
+    return tree->cl->find(tree, subtree_root, data);
+}
+
+/**
+ * Creates a depth-first iterator for the specified tree.
+ *
+ * @param tree the tree to iterate
+ * @param visit_on_exit true, if the iterator shall visit a node again when
+ * leaving the sub-tree
+ * @return a tree iterator (depth-first)
+ * @see cxTreeVisitor()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxTreeIterator cxTreeIterator(
+        CxTree *tree,
+        bool visit_on_exit
+) {
+    return tree->cl->iterator(tree, visit_on_exit);
+}
+
+/**
+ * Creates a breadth-first iterator for the specified tree.
+ *
+ * @param tree the tree to iterate
+ * @return a tree visitor (a.k.a. breadth-first iterator)
+ * @see cxTreeIterator()
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) {
+    return tree->cl->visitor(tree);
+}
 
 #ifdef __cplusplus
 } // extern "C"

--- a/tests/Makefile	Sun Sep 29 23:08:40 2024 +0200
+++ b/tests/Makefile	Mon Sep 30 19:17:19 2024 +0200
@@ -111,7 +111,8 @@
 	$(CC) -o $@ $(CFLAGS) -c $<
 
 $(TEST_DIR)/test_tree$(OBJ_EXT): test_tree.c ../src/cx/tree.h \
- ../src/cx/common.h ../src/cx/iterator.h ../src/cx/test.h \
+ ../src/cx/common.h ../src/cx/collection.h ../src/cx/allocator.h \
+ ../src/cx/iterator.h ../src/cx/compare.h ../src/cx/test.h \
  util_allocator.h ../src/cx/allocator.h
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -c $<