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