ucx: comparison src/cx/tree.h

-:9b2c12494ccf
+:303a981e6834
 * A function to compare two nodes.
 */
 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;
 /**
 /**
 * Creates a new tree structure based on the specified layout.
 *
 * 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
 * @param loc_parent offset in the node struct for the parent pointer
 * 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 cxTreeCreateSimple()
+* @see cxTreeCreateWrapped()
 */
 __attribute__((__nonnull__, __warn_unused_result__))
 CxTree *cxTreeCreate(
 const CxAllocator *allocator,
 cx_tree_node_create_func create_func,
 return cxTreeCreate(cxDefaultAllocator,
 create_func, search_func, cx_tree_node_base_layout);
 }
 /**
+* 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
 * on the nodes, if specified.
 * It will NOT automatically free the nodes with the allocator, because that
 * a tree which memory is managed by someone else.
 *
 * @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"
 #endif

Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h