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 <stdbool.h>       // for bool
  18 #include "bits/compare.h"  // for cmp_ref (not used in file)
  19
  20 typedef struct TreeNode {
  21         /* public */
  22         void *dat;            // pointer to data
  23         /* private */
  24         struct TreeNode *lft; // left branch (data is "smaller")
  25         struct TreeNode *rgt; // right branch (data is "bigger")
  26 } TreeNode;
  27
  28 typedef struct {
  29         /* private */
  30         TreeNode *rot; // root node
  31 } Tree;
  32
  33 typedef enum {
  34         TRAVERSION_PREORDER,
  35         TRAVERSION_INORDER,
  36         TRAVERSION_POSTORDER,
  37 } TreeTraversionOrder;
  38
  39 void tree_ini(Tree *tree);
  40 /*
  41         Initializes the tree.
  42
  43         The tree should be uninitialized or empty before passed to this function.
  44         This function should be called before any other function is called on the tree.
  45 */
  46
  47 bool tree_add(Tree *tree, void *key, void *dat, void *cmp, void *trans);
  48 /*
  49         Add an element to the tree.
  50
  51         If an equal element is already in the tree, don't add anything.
  52         Return whether an element has been added.
  53 */
  54
  55 void *tree_get(Tree *tree, void *key, void *cmp, void *trans);
  56 /*
  57         Get an element from the tree, or return NULL if none found.
  58 */
  59
  60 bool tree_del(Tree *tree, void *key, void *cmp, void *call, void *arg, void *trans);
  61 /*
  62         Delete an element from the tree if it is found.
  63         Return whether an element has been deleted.
  64 */
  65
  66 TreeNode **tree_nfd(Tree *tree, void *key, void *cmp);
  67 /*
  68         Find the location of a node matching key.
  69
  70         This can be the location of an an existing node, or the location where a node matching
  71                 that key would need to be stored.
  72 */
  73
  74 void tree_nmk(Tree *tree, TreeNode **node, void *dat);
  75 /*
  76         Create a node with dat as data and store it's pointer at the given location.
  77 */
  78
  79 void tree_nrm(Tree *tree, TreeNode **node);
  80 /*
  81         Remove the node at the given location.
  82 */
  83
  84 void tree_trv(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
  85 /*
  86         Traverse the tree.
  87         Calls iter on every element, with the extra argument arg.
  88 */
  89
  90 void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order);
  91 /*
  92         Traverses the tree and deletes all elements.
  93         Calls iter on every element, with the extra argument arg.
  94
  95         The tree is empty afterwards.
  96         If no callback is given, the traversion order is irrelevant.
  97 */
  98
  99 #endif // _DRAGONSTD_TREE_H_