tree.h

   1 /*
   2         Tree
   3         ----
   4
   5         A binary search tree.
   6
   7         Note: This structure is included in <search.h> the C library as of POSIX.1-2001 and
   8                 POSIX.1-2008. However, the standard does not contain functions to delete the tree
   9                 and to traverse it with an additional argument. Glibc provides these functions,
  10                 but dragonstd conforms to the POSIX standard and does not use GNU extensions.
  11                 Therefore, this implementation is used to provide the missing features.
  12 */
  13
  14 #ifndef _DRAGONSTD_TREE_H_ // include guard
  15 #define _DRAGONSTD_TREE_H_
  16
  17 #include "bits/callback.h" // for Iterator, Comparator
  18
  19 typedef struct TreeNode {
  20         /* public */
  21         void *dat;            // pointer to data
  22         /* private */
  23         struct TreeNode *lft; // left branch (data is "smaller")
  24         struct TreeNode *rgt; // right branch (data is "bigger")
  25 } TreeNode;
  26
  27 typedef struct {
  28         /* private */
  29         TreeNode *rot; // root node
  30 } Tree;
  31
  32 typedef enum {
  33         TRAVERSION_PREORDER,
  34         TRAVERSION_INORDER,
  35         TRAVERSION_POSTORDER,
  36 } TreeTraversionOrder;
  37
  38 void tree_ini(Tree *tree);
  39 /*
  40         Initializes the tree.
  41
  42         The tree should be uninitialized or empty before passed to this function.
  43         This function should be called before any other function is called on the tree.
  44 */
  45
  46 void *tree_add(Tree *tree, void *dat, Comparator cmp, Transformer trans);
  47 /*
  48         Add an element to the tree.
  49
  50         If an equal element is already in the tree, return it and don't add anything.
  51         Otherwise, return added element.
  52 */
  53
  54 void *tree_get(Tree *tree, void *key, Comparator cmp, Transformer trans);
  55 /*
  56         Get an element from the tree, or return NULL if none found.
  57 */
  58
  59 void *tree_del(Tree *tree, void *key, Comparator cmp, Transformer trans);
  60 /*
  61         Delete an element from the tree and return it, or NULL if none found.
  62 */
  63
  64 TreeNode **tree_nfd(Tree *tree, void *key, Comparator cmp);
  65 /*
  66         Find the location of a node matching key.
  67
  68         This can be the location of an an existing node, or the location where a node matching
  69                 that key would need to be stored.
  70 */
  71
  72 void tree_nmk(Tree *tree, TreeNode **node, void *dat);
  73 /*
  74         Create a node with dat as data and store it's pointer at the given location.
  75 */
  76
  77 void tree_nrm(Tree *tree, TreeNode **node);
  78 /*
  79         Remove the node at the given location.
  80 */
  81
  82 void tree_trv(Tree *tree, Iterator iter, void *arg, Transformer trans, TreeTraversionOrder order);
  83 /*
  84         Traverse the tree.
  85         Calls iter on every element, with the extra argument arg.
  86 */
  87
  88 void tree_clr(Tree *tree, Iterator iter, void *arg, Transformer trans, TreeTraversionOrder order);
  89 /*
  90         Traverses the tree and deletes all elements.
  91         Calls iter on every element, with the extra argument arg.
  92
  93         The tree is empty afterwards.
  94         If no callback is given, the traversion order is irrelevant.
  95 */
  96
  97 #endif // _DRAGONSTD_TREE_H_