tree.c

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