1 /* src/toolbox/avl.c - AVL tree implementation
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
8 This file is part of CACAO.
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.
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.
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
25 $Id: avl.c 7862 2007-05-03 14:53:39Z twisti $
36 #include "mm/memory.h"
38 #include "threads/lock-common.h"
40 #include "toolbox/avl.h"
41 #include "toolbox/logging.h"
43 #include "vm/global.h"
47 /* avl_create ******************************************************************
49 Creates a AVL tree structure.
51 *******************************************************************************/
53 avl_tree_t *avl_create(avl_comparator *comparator)
60 t->comparator = comparator;
63 #if defined(ENABLE_THREADS)
64 /* create lock object for this tree */
66 t->lock = NEW(java_objectheader);
68 LOCK_INIT_OBJECT_LOCK(t->lock);
75 /* avl_newnode *****************************************************************
77 Creates a new AVL node and sets the pointers correctly.
79 *******************************************************************************/
81 static avl_node_t *avl_newnode(void *data)
89 /* ATTENTION: NEW allocates memory zeroed out */
92 /* n->childs[0] = NULL; */
93 /* n->childs[1] = NULL; */
99 /* avl_rotate_left *************************************************************
101 Does a left rotation on an AVL node.
109 *******************************************************************************/
111 static void avl_rotate_left(avl_node_t **node)
116 /* rotate the node */
119 tmpnode = tmp->childs[AVL_RIGHT];
120 tmp->childs[AVL_RIGHT] = tmpnode->childs[AVL_LEFT];
121 tmpnode->childs[AVL_LEFT] = tmp;
123 /* set new parent node */
129 /* avl_rotate_right ************************************************************
131 Does a right rotation on an AVL node.
139 *******************************************************************************/
141 static void avl_rotate_right(avl_node_t **node)
146 /* rotate the node */
149 tmpnode = tmp->childs[AVL_LEFT];
150 tmp->childs[AVL_LEFT] = tmpnode->childs[AVL_RIGHT];
151 tmpnode->childs[AVL_RIGHT] = tmp;
153 /* set new parent node */
159 /* avl_adjust_balance **********************************************************
161 Does a balance adjustment after a double rotation.
163 *******************************************************************************/
165 static void avl_adjust_balance(avl_node_t *node)
170 left = node->childs[AVL_LEFT];
171 right = node->childs[AVL_RIGHT];
173 switch (node->balance) {
194 /* avl_insert_intern ***********************************************************
196 Inserts a AVL node into a AVL tree.
198 *******************************************************************************/
200 static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
208 /* set temporary variable */
212 /* per default no node was inserted */
216 /* compare the current node */
218 res = tree->comparator(tmpnode->data, data);
220 /* is this node already in the tree? */
223 vm_abort("avl_insert_intern: node already in the tree");
225 /* goto left or right child */
227 direction = (res < 0) ? AVL_LEFT : AVL_RIGHT;
229 /* there is a child, go recursive */
231 if (tmpnode->childs[direction]) {
232 balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
237 /* no child, create this node */
239 newnode = avl_newnode(data);
241 /* insert into parent node */
243 tmpnode->childs[direction] = newnode;
245 /* node was inserted, but don't set insert to 1, since this
246 insertion is handled in this recursion depth */
251 /* add insertion value to node balance, value depends on the
254 tmpnode->balance += (direction == AVL_LEFT) ? -balance : balance;
256 if ((balance != 0) && (tmpnode->balance != 0)) {
257 if (tmpnode->balance < -1) {
258 /* left subtree too tall: right rotation needed */
260 if (tmpnode->childs[AVL_LEFT]->balance < 0) {
261 avl_rotate_right(&tmpnode);
263 /* simple balance adjustments */
265 tmpnode->balance = 0;
266 tmpnode->childs[AVL_RIGHT]->balance = 0;
269 avl_rotate_left(&tmpnode->childs[AVL_LEFT]);
270 avl_rotate_right(&tmpnode);
271 avl_adjust_balance(tmpnode);
274 else if (tmpnode->balance > 1) {
275 /* right subtree too tall: left rotation needed */
277 if (tmpnode->childs[AVL_RIGHT]->balance > 0) {
278 avl_rotate_left(&tmpnode);
280 /* simple balance adjustments */
282 tmpnode->balance = 0;
283 tmpnode->childs[AVL_LEFT]->balance = 0;
286 avl_rotate_right(&tmpnode->childs[AVL_RIGHT]);
287 avl_rotate_left(&tmpnode);
288 avl_adjust_balance(tmpnode);
300 /* insertion was ok */
306 /* avl_insert ******************************************************************
308 Inserts a AVL node into a AVL tree.
310 *******************************************************************************/
312 bool avl_insert(avl_tree_t *tree, void *data)
317 LOCK_MONITOR_ENTER(tree->lock);
319 /* if we don't have a root node, create one */
321 if (tree->root == NULL)
322 tree->root = avl_newnode(data);
324 avl_insert_intern(tree, &tree->root, data);
326 /* increase entries count */
330 LOCK_MONITOR_EXIT(tree->lock);
332 /* insertion was ok */
338 /* avl_find ********************************************************************
340 Find a given data structure in the AVL tree, with the comparision
341 function of the tree.
343 *******************************************************************************/
345 void *avl_find(avl_tree_t *tree, void *data)
353 LOCK_MONITOR_ENTER(tree->lock);
355 /* search the tree for the given node */
357 for (node = tree->root; node != NULL; ) {
358 /* compare the current node */
360 res = tree->comparator(node->data, data);
362 /* was the entry found? return it */
365 LOCK_MONITOR_EXIT(tree->lock);
370 /* goto left or right child */
372 node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT];
375 LOCK_MONITOR_EXIT(tree->lock);
377 /* entry was not found, returning NULL */
383 /* avl_dump ********************************************************************
385 Dumps the AVL tree starting with node.
387 *******************************************************************************/
390 void avl_dump(avl_node_t* node, s4 indent)
399 if (node->childs[AVL_RIGHT])
400 avl_dump(node->childs[AVL_RIGHT], tmp + 1);
407 log_print("%p (%d)", node->data, node->balance);
410 if (node->childs[AVL_LEFT])
411 avl_dump(node->childs[AVL_LEFT], tmp + 1);
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 * ---------------------------------------------------------------------
423 * indent-tabs-mode: t