1 /* src/toolbox/avl.c - AVL tree implementation
3 Copyright (C) 1996-2005, 2006, 2007, 2008
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
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.
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.
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
32 #include "mm/memory.hpp"
34 #include "threads/mutex.hpp"
36 #include "toolbox/avl.h"
37 #include "toolbox/logging.hpp"
39 #include "vm/global.h"
43 /* avl_create ******************************************************************
45 Creates a AVL tree structure.
47 *******************************************************************************/
49 avl_tree_t *avl_create(avl_comparator *comparator)
55 t->mutex = Mutex_new();
57 t->comparator = comparator;
64 /* avl_newnode *****************************************************************
66 Creates a new AVL node and sets the pointers correctly.
68 *******************************************************************************/
70 static avl_node_t *avl_newnode(void *data)
78 /* ATTENTION: NEW allocates memory zeroed out */
81 /* n->childs[0] = NULL; */
82 /* n->childs[1] = NULL; */
88 /* avl_rotate_left *************************************************************
90 Does a left rotation on an AVL node.
98 *******************************************************************************/
100 static void avl_rotate_left(avl_node_t **node)
105 /* rotate the node */
108 tmpnode = tmp->childs[AVL_RIGHT];
109 tmp->childs[AVL_RIGHT] = tmpnode->childs[AVL_LEFT];
110 tmpnode->childs[AVL_LEFT] = tmp;
112 /* set new parent node */
118 /* avl_rotate_right ************************************************************
120 Does a right rotation on an AVL node.
128 *******************************************************************************/
130 static void avl_rotate_right(avl_node_t **node)
135 /* rotate the node */
138 tmpnode = tmp->childs[AVL_LEFT];
139 tmp->childs[AVL_LEFT] = tmpnode->childs[AVL_RIGHT];
140 tmpnode->childs[AVL_RIGHT] = tmp;
142 /* set new parent node */
148 /* avl_adjust_balance **********************************************************
150 Does a balance adjustment after a double rotation.
152 *******************************************************************************/
154 static void avl_adjust_balance(avl_node_t *node)
159 left = node->childs[AVL_LEFT];
160 right = node->childs[AVL_RIGHT];
162 switch (node->balance) {
183 /* avl_insert_intern ***********************************************************
185 Inserts a AVL node into a AVL tree.
187 *******************************************************************************/
189 static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
197 /* set temporary variable */
201 /* per default no node was inserted */
205 /* compare the current node */
207 res = tree->comparator(tmpnode->data, data);
209 /* is this node already in the tree? */
212 vm_abort("avl_insert_intern: node already in the tree");
214 /* goto left or right child */
216 direction = (res < 0) ? AVL_LEFT : AVL_RIGHT;
218 /* there is a child, go recursive */
220 if (tmpnode->childs[direction]) {
221 balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
226 /* no child, create this node */
228 newnode = avl_newnode(data);
230 /* insert into parent node */
232 tmpnode->childs[direction] = newnode;
234 /* node was inserted, but don't set insert to 1, since this
235 insertion is handled in this recursion depth */
240 /* add insertion value to node balance, value depends on the
243 tmpnode->balance += (direction == AVL_LEFT) ? -balance : balance;
245 if ((balance != 0) && (tmpnode->balance != 0)) {
246 if (tmpnode->balance < -1) {
247 /* left subtree too tall: right rotation needed */
249 if (tmpnode->childs[AVL_LEFT]->balance < 0) {
250 avl_rotate_right(&tmpnode);
252 /* simple balance adjustments */
254 tmpnode->balance = 0;
255 tmpnode->childs[AVL_RIGHT]->balance = 0;
258 avl_rotate_left(&tmpnode->childs[AVL_LEFT]);
259 avl_rotate_right(&tmpnode);
260 avl_adjust_balance(tmpnode);
263 else if (tmpnode->balance > 1) {
264 /* right subtree too tall: left rotation needed */
266 if (tmpnode->childs[AVL_RIGHT]->balance > 0) {
267 avl_rotate_left(&tmpnode);
269 /* simple balance adjustments */
271 tmpnode->balance = 0;
272 tmpnode->childs[AVL_LEFT]->balance = 0;
275 avl_rotate_right(&tmpnode->childs[AVL_RIGHT]);
276 avl_rotate_left(&tmpnode);
277 avl_adjust_balance(tmpnode);
289 /* insertion was ok */
295 /* avl_insert ******************************************************************
297 Inserts a AVL node into a AVL tree.
299 *******************************************************************************/
301 bool avl_insert(avl_tree_t *tree, void *data)
306 Mutex_lock(tree->mutex);
308 /* if we don't have a root node, create one */
310 if (tree->root == NULL)
311 tree->root = avl_newnode(data);
313 avl_insert_intern(tree, &tree->root, data);
315 /* increase entries count */
319 Mutex_unlock(tree->mutex);
321 /* insertion was ok */
327 /* avl_find ********************************************************************
329 Find a given data structure in the AVL tree, with the comparision
330 function of the tree.
332 *******************************************************************************/
334 void *avl_find(avl_tree_t *tree, void *data)
342 Mutex_lock(tree->mutex);
344 /* search the tree for the given node */
346 for (node = tree->root; node != NULL; ) {
347 /* compare the current node */
349 res = tree->comparator(node->data, data);
351 /* was the entry found? return it */
354 Mutex_unlock(tree->mutex);
359 /* goto left or right child */
361 node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT];
364 Mutex_unlock(tree->mutex);
366 /* entry was not found, returning NULL */
372 /* avl_dump ********************************************************************
374 Dumps the AVL tree starting with node.
376 *******************************************************************************/
379 void avl_dump(avl_node_t* node, s4 indent)
388 if (node->childs[AVL_RIGHT])
389 avl_dump(node->childs[AVL_RIGHT], tmp + 1);
396 log_print("%p (%d)", node->data, node->balance);
399 if (node->childs[AVL_LEFT])
400 avl_dump(node->childs[AVL_LEFT], tmp + 1);
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 * ---------------------------------------------------------------------
412 * indent-tabs-mode: t