src/toolbox/tree.c

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