dragonstd/tree.c

   1 #include <stdlib.h>  // for malloc, free
   2 #include "bits/callback.h" // for Callback, Comparator, Transformer
   3 #include "bits/wrappers.h"
   4 #include "tree.h"
   5
   6 static inline TreeNode **search(TreeNode **node, void *key, Comparator cmp)
   7 {
   8         if (!*node)
   9                 return node;
  10
  11         int rel = cmp((*node)->dat, key);
  12
  13         if (rel == 0)
  14                 return node;
  15         else if (rel > 0)
  16                 return search(&(*node)->lft, key, cmp);
  17         else // (rel < 0)
  18                 return search(&(*node)->rgt, key, cmp);
  19 }
  20
  21 static inline void traverse(TreeNode *node, Callback iter, void *arg, Transformer trans, TreeTraversionOrder order, int delete)
  22 {
  23         if (!node)
  24                 return;
  25
  26         if (iter && order == TRAVERSION_PREORDER ) iter(trans ? trans(node->dat) : node->dat, arg);
  27         traverse(node->lft, iter, arg, trans, order, delete);
  28         if (iter && order == TRAVERSION_INORDER  ) iter(trans ? trans(node->dat) : node->dat, arg);
  29         traverse(node->rgt, iter, arg, trans, order, delete);
  30         if (iter && order == TRAVERSION_POSTORDER) iter(trans ? trans(node->dat) : node->dat, arg);
  31
  32         if (delete)
  33                 free(node);
  34 }
  35
  36 void tree_ini(Tree *tree)
  37 {
  38         tree->rot = NULL;
  39 }
  40
  41 WRAP_NODE_FUNCTIONS(Tree, tree_)
  42
  43 TreeNode **tree_nfd(Tree *tree, void *key, void *cmp)
  44 {
  45         return search(&tree->rot, key, cmp);
  46 }
  47
  48 void tree_nmk(__attribute__((unused)) Tree *tree, TreeNode **node, void *dat)
  49 {
  50         *node = malloc(sizeof **node);
  51         (*node)->dat = dat;
  52         (*node)->lft = (*node)->rgt = NULL;
  53 }
  54
  55 void tree_nrm(__attribute__((unused)) Tree *tree, TreeNode **node)
  56 {
  57         TreeNode *old = *node;
  58         *node = old->lft;
  59
  60         if (old->rgt) {
  61                 TreeNode **rgt = node;
  62
  63                 while (*rgt)
  64                         rgt = &(*rgt)->rgt;
  65
  66                 *rgt = old->rgt;
  67         }
  68
  69         free(old);
  70 }
  71
  72 void tree_trv(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order)
  73 {
  74         traverse(tree->rot, iter, arg, trans, order, 0);
  75 }
  76
  77 void tree_clr(Tree *tree, void *iter, void *arg, void *trans, TreeTraversionOrder order)
  78 {
  79         traverse(tree->rot, iter, arg, trans, order, 1);
  80         tree_ini(tree);
  81 }