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 func);
  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 func);
  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 func);
  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 func, void *arg, TreeTraversionOrder order);
  83 /*
  84         Traverse the tree.
  85         Calls func on every element, with the extra argument arg.
  86 */
  87
  88 void tree_clr(Tree *tree, Iterator func, void *arg, TreeTraversionOrder order);
  89 /*
  90         Traverses the tree and deletes all elements.
  91         Calls func 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_