src/toolbox/tree.c

   1 /* toolbox/tree.h - binary tree management
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    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., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Reinhard Grafl
  28
  29    $Id: tree.c 1735 2004-12-07 14:33:27Z twisti $
  30
  31 */
  32
  33
  34 #include <stdio.h>
  35 #include <assert.h>
  36
  37 #include "mm/memory.h"
  38 #include "toolbox/tree.h"
  39
  40
  41 tree *tree_new(treeelementcomperator comperator)
  42 {
  43         tree *t = NEW(tree);
  44
  45         t->usedump = 0;
  46         t->comperator = comperator;
  47         t->top = NULL;
  48         t->active = NULL;
  49
  50         return t;
  51 }
  52
  53
  54 tree *tree_dnew(treeelementcomperator comperator)
  55 {
  56         tree *t = DNEW(tree);
  57
  58         t->usedump = 1;
  59         t->comperator = comperator;
  60         t->top = NULL;
  61         t->active = NULL;
  62
  63         return t;
  64 }
  65
  66
  67 static void tree_nodefree(treenode *tn)
  68 {
  69         if (!tn)
  70                 return;
  71
  72         tree_nodefree(tn->left);
  73         tree_nodefree(tn->right);
  74         FREE(tn, treenode);
  75 }
  76
  77
  78 void tree_free(tree *t)
  79 {
  80         assert(!t->usedump);
  81
  82         tree_nodefree(t->top);
  83         FREE(t, tree);
  84 }
  85
  86
  87 static treenode *tree_nodeadd(tree *t, treenode *par, treenode *n,
  88                                                           void *element, void *key)
  89 {
  90         if (!n) {
  91                 if (t->usedump) {
  92                         n = DNEW(treenode);
  93
  94                 } else {
  95                         n = NEW(treenode);
  96                 }
  97
  98                 n->left = NULL;
  99                 n->right = NULL;
 100                 n->parent = par;
 101                 n->element = element;
 102
 103         } else {
 104                 if (t->comperator(key, n->element) < 0) {
 105                         n->left = tree_nodeadd(t, n, n->left, element, key);
 106
 107                 } else {
 108                         n->right = tree_nodeadd(t, n, n->right, element, key);
 109                 }
 110         }
 111
 112         return n;
 113 }
 114
 115
 116 void tree_add(tree *t, void *element, void *key)
 117 {
 118         t->top = tree_nodeadd(t, NULL, t->top, element, key);
 119         t->active = t->top;
 120 }
 121
 122
 123 static treenode *tree_nodefind(tree *t, treenode *n, void *key)
 124 {
 125         int way;
 126
 127         if (!n)
 128                 return NULL;
 129
 130         way = t->comperator(key, n->element);
 131         if (way == 0)
 132                 return n;
 133
 134         if (way < 0) {
 135                 return tree_nodefind(t, n->left, key);
 136
 137         } else {
 138                 return tree_nodefind (t, n -> right, key);
 139         }
 140 }
 141
 142
 143 void *tree_find(tree *t, void *key)
 144 {
 145         treenode *tn = tree_nodefind(t, t->top, key);
 146
 147         if (!tn)
 148                 return NULL;
 149
 150         t->active = tn;
 151
 152         return tn->element;
 153 }
 154
 155
 156
 157 void *tree_this(tree *t)
 158 {
 159         if (!t->active)
 160                 return NULL;
 161
 162         return t->active->element;
 163 }
 164
 165
 166 static treenode *leftmostnode(treenode *t)
 167 {
 168         while (t->left) {
 169                 t = t->left;
 170         }
 171
 172         return t;
 173 }
 174
 175
 176 void *tree_first(tree *t)
 177 {
 178         treenode *a = t->top;
 179
 180         if (!a)
 181                 return NULL;
 182
 183         a = leftmostnode(a);
 184         t->active = a;
 185
 186         return a->element;
 187 }
 188
 189
 190 void *tree_next (tree *t)
 191 {
 192         treenode *a = t->active;
 193         treenode *comefrom = NULL;
 194
 195         while (a) {
 196                 if (!a)
 197                         return NULL;
 198
 199                 if (a->left && (a->left == comefrom)) {
 200                         t -> active = a;
 201                         return a->element;
 202                 }
 203
 204                 if (a->right && (a->right != comefrom)) {
 205                         a = leftmostnode(a->right);
 206                         t -> active = a;
 207                         return a->element;
 208                 }
 209
 210                 comefrom = a;
 211                 a = a->parent;
 212         }
 213
 214         t->active = NULL;
 215
 216         return NULL;
 217 }
 218
 219
 220 /*
 221  * These are local overrides for various environment variables in Emacs.
 222  * Please do not remove this and leave it at the end of the file, where
 223  * Emacs will automagically detect them.
 224  * ---------------------------------------------------------------------
 225  * Local variables:
 226  * mode: c
 227  * indent-tabs-mode: t
 228  * c-basic-offset: 4
 229  * tab-width: 4
 230  * End:
 231  */