src/toolbox/avl.c

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