Add CMake config

[dragonstd.git] / dragonstd / tree.h

diff --git a/dragonstd/tree.h b/dragonstd/tree.h
new file mode 100644 (file)
index 0000000..064906d
--- /dev/null
+++ b/dragonstd/tree.h
@@ -0,0 +1,99 @@
+/*
+       Tree
+       ----
+
+       A binary search tree.
+
+       Note: This structure is included in <search.h> the C library as of POSIX.1-2001 and
+               POSIX.1-2008. However, the standard does not contain functions to delete the tree
+               and to traverse it with an additional argument. Glibc provides these functions,
+               but dragonstd conforms to the POSIX standard and does not use GNU extensions.
+               Therefore, this implementation is used to provide the missing features.
+*/
+
+#ifndef _DRAGONSTD_TREE_H_ // include guard
+#define _DRAGONSTD_TREE_H_
+
+#include <stdbool.h>      // for bool
+#include "bits/compare.h" // for cmp_ref (not used in file)
+
+typedef struct TreeNode {
+       /* public */
+       void *dat;            // pointer to data
+       /* private */
+       struct TreeNode *lft; // left branch (data is "smaller")
+       struct TreeNode *rgt; // right branch (data is "bigger")
+} TreeNode;
+
+typedef struct {
+       /* private */
+       TreeNode *rot; // root node
+} Tree;
+
+typedef enum {
+       TRAVERSION_PREORDER,
+       TRAVERSION_INORDER,
+       TRAVERSION_POSTORDER,
+} TreeTraversionOrder;
+
+void tree_ini(Tree *tree);
+/*
+       Initializes the tree.
+
+       The tree should be uninitialized or empty before passed to this function.
+       This function should be called before any other function is called on the tree.
+*/
+
+bool tree_add(Tree *tree, void *key, void *dat, void *cmp, void *trans);
+/*
+       Add an element to the tree.
+
+       If an equal element is already in the tree, don't add anything.
+       Return whether an element has been added.
+*/
+
+void *tree_get(Tree *tree, void *key, void *cmp, void *trans);
+/*
+       Get an element from the tree, or return NULL if none found.
+*/
+
+bool tree_del(Tree *tree, void *key, void *cmp, void *call, void *arg, void *trans);
+/*
+       Delete an element from the tree if it is found.
+       Return whether an element has been deleted.
+*/
+
+TreeNode **tree_nfd(Tree *tree, void *key, void *cmp);
+/*
+       Find the location of a node matching key.
+
+       This can be the location of an an existing node, or the location where a node matching
+               that key would need to be stored.
+*/
+
+void tree_nmk(Tree *tree, TreeNode **node, void *dat);
+/*
+       Create a node with dat as data and store it's pointer at the given location.
+*/
+
+void tree_nrm(Tree *tree, TreeNode **node);
+/*
+       Remove the node at the given location.
+*/
+
+void tree_trv(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
+/*
+       Traverse the tree.
+       Calls iter on every element, with the extra argument arg.
+*/
+
+void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
+/*
+       Traverses the tree and deletes all elements.
+       Calls iter on every element, with the extra argument arg.
+
+       The tree is empty afterwards.
+       If no callback is given, the traversion order is irrelevant.
+*/
+
+#endif // _DRAGONSTD_TREE_H_