Mercurial > hg > ucx / changeset

--- a/src/cx/tree.h	Sun Sep 29 13:32:33 2024 +0200
+++ b/src/cx/tree.h	Sun Sep 29 13:49:33 2024 +0200
@@ -38,7 +38,7 @@
 
 #include "common.h"
 
-#include "iterator.h"
+#include "collection.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -657,6 +657,124 @@
         ptrdiff_t loc_next
 );
 
+
+/**
+ * Tree class type.
+ */
+typedef struct cx_tree_class_s cx_tree_class;
+
+/**
+ * Structure for holding the base data of a tree.
+ */
+struct cx_tree_s {
+    /**
+     * The tree class definition.
+     */
+    const cx_tree_class *cl;
+
+    /**
+     * A function to create new nodes.
+     */
+    cx_tree_node_create_func node_create;
+
+    /**
+     * The pointer to additional data that is passed to the create function.
+     */
+    void *create_data;
+
+    /**
+     * An optional simple destructor for the tree nodes.
+     */
+    cx_destructor_func simple_destructor;
+
+    /**
+     * An optional advanced destructor for the tree nodes.
+     */
+    cx_destructor_func2 advanced_destructor;
+
+    /**
+     * The pointer to additional data that is passed to the advanced destructor.
+     */
+    void *destructor_data;
+
+    /**
+     * 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;
+};
+
+/**
+ * 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.
+     */
+    int (*insert_element)(
+            struct cx_tree_s *tree,
+            const void *data
+    );
+
+    /**
+     * Member function for inserting multiple elements.
+     *
+     * Implementations SHALL avoid to perform a full search in the tree for
+     * every element even though the source data MAY be unsorted.
+     */
+    size_t (*insert_many)(
+            struct cx_tree_s *tree,
+            struct cx_iterator_base_s *iter,
+            size_t n
+    );
+
+    /**
+     * Member function for finding a node.
+     */
+    void *(*find)(
+            struct cx_tree_s *tree,
+            const void *data
+    );
+
+    /**
+     * Member function for creating an iterator for the tree.
+     */
+    CxTreeIterator (*iterator)(
+            struct cx_tree_s *tree,
+            bool visit_on_exit
+    );
+
+    /**
+     * Member function for creating a visitor for the tree.
+     */
+    CxTreeVisitor (*visitor)(struct cx_tree_s *tree);
+};
+
+/**
+ * Common type for all tree implementations.
+ */
+typedef struct cx_tree_s CxTree;
+
 #ifdef __cplusplus
 } // extern "C"
 #endif