git.itanic.dy.fi Git - scan-pagemap/blob - bintree.c

   1 #include <stdlib.h>
   2
   3 #include "bintree.h"
   4
   5 /*
   6  * bintree_add - Add to tree
   7  *
   8  * Adds a node to a sorted tree. If the new node is already found from
   9  * the tree, the existing node is returned and the new node is not
  10  * added. If new node is not found, the new one is added and the tree
  11  * is kept sorted.
  12  */
  13 struct bintree *bintree_add(struct bintree *tree, struct bintree *new,
  14                         struct bintree_ops *ops)
  15 {
  16         int ret;
  17
  18         if (tree == NULL)
  19                 return new;
  20
  21         ret = ops->compare(tree, new);
  22         if (ret < 0) {
  23                 if (tree->left)
  24                         return bintree_add(tree->left, new, ops);
  25                 tree->left = new;
  26                 return new;
  27         }
  28
  29         if (ret > 0) {
  30                 if (tree->right)
  31                         return bintree_add(tree->right, new, ops);
  32                 tree->right = new;
  33                 return new;
  34         }
  35
  36         return tree;
  37 }
  38
  39 /*
  40  * bintree_find - Find a node from a tree.
  41  *
  42  * If node is found, pointer to the node is returned. If no node is
  43  * found, null is returned.
  44  */
  45 struct bintree *bintree_find(struct bintree *tree, struct bintree *new,
  46                         struct bintree_ops *ops)
  47 {
  48         int ret;
  49
  50         if (tree == NULL)
  51                 return NULL;
  52
  53         ret = ops->compare(tree, new);
  54         if (ret < 0) {
  55                 if (tree->left)
  56                         return bintree_find(tree->left, new, ops);
  57
  58                 return NULL;
  59         }
  60
  61         if (ret > 0) {
  62                 if (tree->right)
  63                         return bintree_find(tree->right, new, ops);
  64
  65                 return NULL;
  66         }
  67
  68         return tree;
  69 }
  70
  71 /*
  72  * bintree_walk - walk through a binary tree from left to right
  73  *
  74  * Returns the number of nodes in the tree
  75  */
  76 int bintree_walk(struct bintree *tree, struct bintree_ops *ops)
  77 {
  78         int count = 0;
  79
  80         if (tree->left)
  81                 count += bintree_walk(tree->left, ops);
  82
  83         if (ops->callback)
  84                 ops->callback(tree, ops);
  85
  86         count++;
  87
  88         if (tree->right)
  89                 count += bintree_walk(tree->right, ops);
  90
  91         return count;
  92 }