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