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

   1 /*
   2  * Copyright (C) 2010 Timo Kokkonen <kaapeli@itanic.dy.fi>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  */
  17
  18 #include <stdlib.h>
  19
  20 #include "bintree.h"
  21
  22 /*
  23  * bintree_add - Add to tree
  24  *
  25  * Adds a node to a sorted tree. If the new node is already found from
  26  * the tree, the existing node is returned and the new node is not
  27  * added. If new node is not found, the new one is added and the tree
  28  * is kept sorted.
  29  */
  30 struct bintree *bintree_add(struct bintree *tree, struct bintree *new,
  31                         struct bintree_ops *ops)
  32 {
  33         int ret;
  34
  35         if (tree == NULL)
  36                 return new;
  37
  38         ret = ops->compare(tree, new);
  39         if (ret < 0) {
  40                 if (tree->left)
  41                         return bintree_add(tree->left, new, ops);
  42                 tree->left = new;
  43                 return new;
  44         }
  45
  46         if (ret > 0) {
  47                 if (tree->right)
  48                         return bintree_add(tree->right, new, ops);
  49                 tree->right = new;
  50                 return new;
  51         }
  52
  53         return tree;
  54 }
  55
  56 /*
  57  * bintree_find - Find a node from a tree.
  58  *
  59  * If node is found, pointer to the node is returned. If no node is
  60  * found, null is returned.
  61  */
  62 struct bintree *bintree_find(struct bintree *tree, struct bintree *new,
  63                         struct bintree_ops *ops)
  64 {
  65         int ret;
  66
  67         if (tree == NULL)
  68                 return NULL;
  69
  70         ret = ops->compare(tree, new);
  71         if (ret < 0) {
  72                 if (tree->left)
  73                         return bintree_find(tree->left, new, ops);
  74
  75                 return NULL;
  76         }
  77
  78         if (ret > 0) {
  79                 if (tree->right)
  80                         return bintree_find(tree->right, new, ops);
  81
  82                 return NULL;
  83         }
  84
  85         return tree;
  86 }
  87
  88 /*
  89  * bintree_walk - walk through a binary tree from left to right
  90  *
  91  * Returns the number of nodes in the tree
  92  */
  93 int bintree_walk(struct bintree *tree, struct bintree_ops *ops)
  94 {
  95         int count = 0;
  96
  97         if (tree->left)
  98                 count += bintree_walk(tree->left, ops);
  99
 100         if (ops->callback)
 101                 ops->callback(tree, ops);
 102
 103         count++;
 104
 105         if (tree->right)
 106                 count += bintree_walk(tree->right, ops);
 107
 108         return count;
 109 }