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