src/toolbox/tree.c

   1 /* toolbox/tree.h - binary tree management
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Reinhard Grafl
  28
  29
  30 */
  31
  32
  33 #include <stdio.h>
  34 #include <assert.h>
  35
  36 #include "mm/memory.h"
  37 #include "toolbox/tree.h"
  38
  39
  40 tree *tree_new(treeelementcomperator comperator)
  41 {
  42         tree *t = NEW(tree);
  43
  44         t->usedump = 0;
  45         t->comperator = comperator;
  46         t->top = NULL;
  47         t->active = NULL;
  48
  49         return t;
  50 }
  51
  52
  53 tree *tree_dnew(treeelementcomperator comperator)
  54 {
  55         tree *t = DNEW(tree);
  56
  57         t->usedump = 1;
  58         t->comperator = comperator;
  59         t->top = NULL;
  60         t->active = NULL;
  61
  62         return t;
  63 }
  64
  65
  66 static void tree_nodefree(treenode *tn)
  67 {
  68         if (!tn)
  69                 return;
  70
  71         tree_nodefree(tn->left);
  72         tree_nodefree(tn->right);
  73         FREE(tn, treenode);
  74 }
  75
  76
  77 void tree_free(tree *t)
  78 {
  79         assert(!t->usedump);
  80
  81         tree_nodefree(t->top);
  82         FREE(t, tree);
  83 }
  84
  85
  86 static treenode *tree_nodeadd(tree *t, treenode *par, treenode *n,
  87                                                           void *element, void *key)
  88 {
  89         if (!n) {
  90                 if (t->usedump) {
  91                         n = DNEW(treenode);
  92
  93                 } else {
  94                         n = NEW(treenode);
  95                 }
  96
  97                 n->left = NULL;
  98                 n->right = NULL;
  99                 n->parent = par;
 100                 n->element = element;
 101
 102         } else {
 103                 if (t->comperator(key, n->element) < 0) {
 104                         n->left = tree_nodeadd(t, n, n->left, element, key);
 105
 106                 } else {
 107                         n->right = tree_nodeadd(t, n, n->right, element, key);
 108                 }
 109         }
 110
 111         return n;
 112 }
 113
 114
 115 void tree_add(tree *t, void *element, void *key)
 116 {
 117         t->top = tree_nodeadd(t, NULL, t->top, element, key);
 118         t->active = t->top;
 119 }
 120
 121
 122 static treenode *tree_nodefind(tree *t, treenode *n, void *key)
 123 {
 124         int way;
 125
 126         if (!n)
 127                 return NULL;
 128
 129         way = t->comperator(key, n->element);
 130         if (way == 0)
 131                 return n;
 132
 133         if (way < 0) {
 134                 return tree_nodefind(t, n->left, key);
 135
 136         } else {
 137                 return tree_nodefind (t, n -> right, key);
 138         }
 139 }
 140
 141
 142 void *tree_find(tree *t, void *key)
 143 {
 144         treenode *tn = tree_nodefind(t, t->top, key);
 145
 146         if (!tn)
 147                 return NULL;
 148
 149         t->active = tn;
 150
 151         return tn->element;
 152 }
 153
 154
 155
 156 void *tree_this(tree *t)
 157 {
 158         if (!t->active)
 159                 return NULL;
 160
 161         return t->active->element;
 162 }
 163
 164
 165 static treenode *leftmostnode(treenode *t)
 166 {
 167         while (t->left) {
 168                 t = t->left;
 169         }
 170
 171         return t;
 172 }
 173
 174
 175 void *tree_first(tree *t)
 176 {
 177         treenode *a = t->top;
 178
 179         if (!a)
 180                 return NULL;
 181
 182         a = leftmostnode(a);
 183         t->active = a;
 184
 185         return a->element;
 186 }
 187
 188
 189 void *tree_next (tree *t)
 190 {
 191         treenode *a = t->active;
 192         treenode *comefrom = NULL;
 193
 194         while (a) {
 195                 if (!a)
 196                         return NULL;
 197
 198                 if (a->left && (a->left == comefrom)) {
 199                         t -> active = a;
 200                         return a->element;
 201                 }
 202
 203                 if (a->right && (a->right != comefrom)) {
 204                         a = leftmostnode(a->right);
 205                         t -> active = a;
 206                         return a->element;
 207                 }
 208
 209                 comefrom = a;
 210                 a = a->parent;
 211         }
 212
 213         t->active = NULL;
 214
 215         return NULL;
 216 }
 217
 218
 219 /*
 220  * These are local overrides for various environment variables in Emacs.
 221  * Please do not remove this and leave it at the end of the file, where
 222  * Emacs will automagically detect them.
 223  * ---------------------------------------------------------------------
 224  * Local variables:
 225  * mode: c
 226  * indent-tabs-mode: t
 227  * c-basic-offset: 4
 228  * tab-width: 4
 229  * End:
 230  */