src/toolbox/avl.c

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