src/toolbox/avl.c

   1 /* src/toolbox/avl.c - AVL tree implementation
   2
   3    Copyright (C) 1996-2005, 2006, 2007 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 */
  26
  27
  28 #include "config.h"
  29
  30 #include <assert.h>
  31
  32 #include "vm/types.h"
  33
  34 #include "mm/memory.h"
  35
  36 #include "threads/lock-common.h"
  37
  38 #include "toolbox/avl.h"
  39 #include "toolbox/logging.h"
  40
  41 #include "vm/global.h"
  42 #include "vm/vm.h"
  43
  44
  45 /* avl_create ******************************************************************
  46
  47    Creates a AVL tree structure.
  48
  49 *******************************************************************************/
  50
  51 avl_tree_t *avl_create(avl_comparator *comparator)
  52 {
  53         avl_tree_t *t;
  54
  55         t = NEW(avl_tree_t);
  56
  57         t->root       = NULL;
  58         t->comparator = comparator;
  59         t->entries    = 0;
  60
  61 #if defined(ENABLE_THREADS)
  62         /* create lock object for this tree */
  63
  64         t->lock       = NEW(java_object_t);
  65
  66         LOCK_INIT_OBJECT_LOCK(t->lock);
  67 #endif
  68
  69         return t;
  70 }
  71
  72
  73 /* avl_newnode *****************************************************************
  74
  75    Creates a new AVL node and sets the pointers correctly.
  76
  77 *******************************************************************************/
  78
  79 static avl_node_t *avl_newnode(void *data)
  80 {
  81         avl_node_t *n;
  82
  83         n = NEW(avl_node_t);
  84
  85         n->data      = data;
  86
  87         /* ATTENTION: NEW allocates memory zeroed out */
  88
  89 /*      n->balance   = 0; */
  90 /*      n->childs[0] = NULL; */
  91 /*      n->childs[1] = NULL; */
  92
  93         return n;
  94 }
  95
  96
  97 /* avl_rotate_left *************************************************************
  98
  99    Does a left rotation on an AVL node.
 100
 101    A (node)         B
 102     \              / \
 103      B       -->  A   C
 104       \
 105        C
 106
 107 *******************************************************************************/
 108
 109 static void avl_rotate_left(avl_node_t **node)
 110 {
 111         avl_node_t *tmp;
 112         avl_node_t *tmpnode;
 113
 114         /* rotate the node */
 115
 116         tmp                       = *node;
 117         tmpnode                   = tmp->childs[AVL_RIGHT];
 118         tmp->childs[AVL_RIGHT]    = tmpnode->childs[AVL_LEFT];
 119         tmpnode->childs[AVL_LEFT] = tmp;
 120
 121         /* set new parent node */
 122
 123         *node                     = tmpnode;
 124 }
 125
 126
 127 /* avl_rotate_right ************************************************************
 128
 129    Does a right rotation on an AVL node.
 130
 131        C (node)         B
 132       /                / \
 133      B           -->  A   C
 134     /
 135    A
 136
 137 *******************************************************************************/
 138
 139 static void avl_rotate_right(avl_node_t **node)
 140 {
 141         avl_node_t *tmp;
 142         avl_node_t *tmpnode;
 143
 144         /* rotate the node */
 145
 146         tmp                        = *node;
 147         tmpnode                    = tmp->childs[AVL_LEFT];
 148         tmp->childs[AVL_LEFT]      = tmpnode->childs[AVL_RIGHT];
 149         tmpnode->childs[AVL_RIGHT] = tmp;
 150
 151         /* set new parent node */
 152
 153         *node                      = tmpnode;
 154 }
 155
 156
 157 /* avl_adjust_balance **********************************************************
 158
 159    Does a balance adjustment after a double rotation.
 160
 161 *******************************************************************************/
 162
 163 static void avl_adjust_balance(avl_node_t *node)
 164 {
 165         avl_node_t *left;
 166         avl_node_t *right;
 167
 168         left  = node->childs[AVL_LEFT];
 169         right = node->childs[AVL_RIGHT];
 170
 171         switch (node->balance) {
 172         case -1:
 173                 left->balance  = 0;
 174                 right->balance = 1;
 175                 break;
 176
 177         case 0:
 178                 left->balance  = 0;
 179                 right->balance = 0;
 180                 break;
 181
 182         case 1:
 183                 left->balance  = -1;
 184                 right->balance = 0;
 185                 break;
 186         }
 187
 188         node->balance = 0;
 189 }
 190
 191
 192 /* avl_insert_intern ***********************************************************
 193
 194    Inserts a AVL node into a AVL tree.
 195
 196 *******************************************************************************/
 197
 198 static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
 199 {
 200         avl_node_t *tmpnode;
 201         s4          res;
 202         s4          direction;
 203         s4          insert;
 204         s4          balance;
 205
 206         /* set temporary variable */
 207
 208         tmpnode = *node;
 209
 210         /* per default no node was inserted */
 211
 212         insert = 0;
 213
 214         /* compare the current node */
 215
 216         res = tree->comparator(tmpnode->data, data);
 217
 218         /* is this node already in the tree? */
 219
 220         if (res == 0)
 221                 vm_abort("avl_insert_intern: node already in the tree");
 222
 223         /* goto left or right child */
 224
 225         direction = (res < 0) ? AVL_LEFT : AVL_RIGHT;
 226
 227         /* there is a child, go recursive */
 228
 229         if (tmpnode->childs[direction]) {
 230                 balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
 231         }
 232         else {
 233                 avl_node_t *newnode;
 234
 235                 /* no child, create this node */
 236
 237                 newnode = avl_newnode(data);
 238
 239                 /* insert into parent node */
 240
 241                 tmpnode->childs[direction] = newnode;
 242
 243                 /* node was inserted, but don't set insert to 1, since this
 244                    insertion is handled in this recursion depth */
 245
 246                 balance = 1;
 247         }
 248
 249         /* add insertion value to node balance, value depends on the
 250            direction */
 251
 252         tmpnode->balance += (direction == AVL_LEFT) ? -balance : balance;
 253
 254         if ((balance != 0) && (tmpnode->balance != 0)) {
 255                 if (tmpnode->balance < -1) {
 256                         /* left subtree too tall: right rotation needed */
 257
 258                         if (tmpnode->childs[AVL_LEFT]->balance < 0) {
 259                                 avl_rotate_right(&tmpnode);
 260
 261                                 /* simple balance adjustments */
 262
 263                                 tmpnode->balance = 0;
 264                                 tmpnode->childs[AVL_RIGHT]->balance = 0;
 265                         }
 266                         else {
 267                                 avl_rotate_left(&tmpnode->childs[AVL_LEFT]);
 268                                 avl_rotate_right(&tmpnode);
 269                                 avl_adjust_balance(tmpnode);
 270                         }
 271                 }
 272                 else if (tmpnode->balance > 1) {
 273                         /* right subtree too tall: left rotation needed */
 274
 275                         if (tmpnode->childs[AVL_RIGHT]->balance > 0) {
 276                                 avl_rotate_left(&tmpnode);
 277
 278                                 /* simple balance adjustments */
 279
 280                                 tmpnode->balance = 0;
 281                                 tmpnode->childs[AVL_LEFT]->balance = 0;
 282                         }
 283                         else {
 284                                 avl_rotate_right(&tmpnode->childs[AVL_RIGHT]);
 285                                 avl_rotate_left(&tmpnode);
 286                                 avl_adjust_balance(tmpnode);
 287                         }
 288                 }
 289                 else {
 290                         insert = 1;
 291                 }
 292         }
 293
 294         /* set back node */
 295
 296         *node = tmpnode;
 297
 298         /* insertion was ok */
 299
 300         return insert;
 301 }
 302
 303
 304 /* avl_insert ******************************************************************
 305
 306    Inserts a AVL node into a AVL tree.
 307
 308 *******************************************************************************/
 309
 310 bool avl_insert(avl_tree_t *tree, void *data)
 311 {
 312         assert(tree);
 313         assert(data);
 314
 315         LOCK_MONITOR_ENTER(tree->lock);
 316
 317         /* if we don't have a root node, create one */
 318
 319         if (tree->root == NULL)
 320                 tree->root = avl_newnode(data);
 321         else
 322                 avl_insert_intern(tree, &tree->root, data);
 323
 324         /* increase entries count */
 325
 326         tree->entries++;
 327
 328         LOCK_MONITOR_EXIT(tree->lock);
 329
 330         /* insertion was ok */
 331
 332         return true;
 333 }
 334
 335
 336 /* avl_find ********************************************************************
 337
 338    Find a given data structure in the AVL tree, with the comparision
 339    function of the tree.
 340
 341 *******************************************************************************/
 342
 343 void *avl_find(avl_tree_t *tree, void *data)
 344 {
 345         avl_node_t *node;
 346         s4          res;
 347
 348         assert(tree);
 349         assert(data);
 350
 351         LOCK_MONITOR_ENTER(tree->lock);
 352
 353         /* search the tree for the given node */
 354
 355         for (node = tree->root; node != NULL; ) {
 356                 /* compare the current node */
 357
 358                 res = tree->comparator(node->data, data);
 359
 360                 /* was the entry found? return it */
 361
 362                 if (res == 0) {
 363                         LOCK_MONITOR_EXIT(tree->lock);
 364
 365                         return node->data;
 366                 }
 367
 368                 /* goto left or right child */
 369
 370                 node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT];
 371         }
 372
 373         LOCK_MONITOR_EXIT(tree->lock);
 374
 375         /* entry was not found, returning NULL */
 376
 377         return NULL;
 378 }
 379
 380
 381 /* avl_dump ********************************************************************
 382
 383    Dumps the AVL tree starting with node.
 384
 385 *******************************************************************************/
 386
 387 #if !defined(NDEBUG)
 388 void avl_dump(avl_node_t* node, s4 indent)
 389 {
 390         s4 tmp;
 391
 392         tmp = indent;
 393
 394         if (node == NULL)
 395                         return;
 396
 397         if (node->childs[AVL_RIGHT])
 398                 avl_dump(node->childs[AVL_RIGHT], tmp + 1);
 399
 400         log_start();
 401
 402         while(indent--)
 403                 log_print("   ");
 404
 405         log_print("%p (%d)", node->data, node->balance);
 406         log_finish();
 407
 408         if (node->childs[AVL_LEFT])
 409                 avl_dump(node->childs[AVL_LEFT], tmp + 1);
 410 }
 411 #endif
 412
 413
 414 /*
 415  * These are local overrides for various environment variables in Emacs.
 416  * Please do not remove this and leave it at the end of the file, where
 417  * Emacs will automagically detect them.
 418  * ---------------------------------------------------------------------
 419  * Local variables:
 420  * mode: c
 421  * indent-tabs-mode: t
 422  * c-basic-offset: 4
 423  * tab-width: 4
 424  * End:
 425  */