/* src/toolbox/avl.c - AVL tree implementation
- Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
- C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
- E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
- J. Wenninger, Institut f. Computersprachen - TU Wien
+ Copyright (C) 1996-2005, 2006, 2007, 2008
+ CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
This file is part of CACAO.
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- Contact: cacao@cacaojvm.org
-
- Authors: Christian Thalinger
-
- Changes:
-
- $Id: avl.c 4921 2006-05-15 14:24:36Z twisti $
-
*/
#include "vm/types.h"
-#include "mm/memory.h"
-#include "toolbox/avl.h"
+#include "mm/memory.hpp"
-#if defined(ENABLE_THREADS)
-# include "threads/native/threads.h"
-#endif
+#include "threads/mutex.hpp"
+
+#include "toolbox/avl.h"
+#include "toolbox/logging.hpp"
-#include "vm/builtin.h"
+#include "vm/global.h"
+#include "vm/vm.hpp"
/* avl_create ******************************************************************
*******************************************************************************/
-avl_tree *avl_create(avl_comparator *compar)
+avl_tree_t *avl_create(avl_comparator *comparator)
{
- avl_tree *t;
+ avl_tree_t *t;
- t = NEW(avl_tree);
+ t = NEW(avl_tree_t);
+ t->mutex = Mutex_new();
t->root = NULL;
- t->comparator = compar;
+ t->comparator = comparator;
t->entries = 0;
-#if defined(ENABLE_THREADS)
- /* create lock object for this tree */
-
- t->lock = NEW(java_objectheader);
-
- lock_init_object_lock(t->lock);
-#endif
-
return t;
}
*******************************************************************************/
-static avl_node *avl_newnode(void *data)
+static avl_node_t *avl_newnode(void *data)
{
- avl_node *n;
+ avl_node_t *n;
- n = NEW(avl_node);
+ n = NEW(avl_node_t);
n->data = data;
*******************************************************************************/
-static void avl_rotate_left(avl_node **node)
+static void avl_rotate_left(avl_node_t **node)
{
- avl_node *tmp;
- avl_node *tmpnode;
+ avl_node_t *tmp;
+ avl_node_t *tmpnode;
/* rotate the node */
*******************************************************************************/
-static void avl_rotate_right(avl_node **node)
+static void avl_rotate_right(avl_node_t **node)
{
- avl_node *tmp;
- avl_node *tmpnode;
+ avl_node_t *tmp;
+ avl_node_t *tmpnode;
/* rotate the node */
*******************************************************************************/
-static void avl_adjust_balance(avl_node *node)
+static void avl_adjust_balance(avl_node_t *node)
{
- avl_node *left;
- avl_node *right;
+ avl_node_t *left;
+ avl_node_t *right;
left = node->childs[AVL_LEFT];
right = node->childs[AVL_RIGHT];
*******************************************************************************/
-static s4 avl_insert_intern(avl_tree *tree, avl_node **node, void *data)
+static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
{
- avl_node *tmpnode;
- s4 res;
- s4 direction;
- s4 insert;
- s4 balance;
+ avl_node_t *tmpnode;
+ s4 res;
+ s4 direction;
+ s4 insert;
+ s4 balance;
/* set temporary variable */
/* compare the current node */
- res = tree->comparator(data, tmpnode->data);
+ res = tree->comparator(tmpnode->data, data);
/* is this node already in the tree? */
if (res == 0)
- assert(0);
+ vm_abort("avl_insert_intern: node already in the tree");
/* goto left or right child */
if (tmpnode->childs[direction]) {
balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
-
- } else {
- avl_node *newnode;
+ }
+ else {
+ avl_node_t *newnode;
/* no child, create this node */
tmpnode->balance = 0;
tmpnode->childs[AVL_RIGHT]->balance = 0;
-
- } else {
+ }
+ else {
avl_rotate_left(&tmpnode->childs[AVL_LEFT]);
avl_rotate_right(&tmpnode);
avl_adjust_balance(tmpnode);
}
-
- } else if (tmpnode->balance > 1) {
+ }
+ else if (tmpnode->balance > 1) {
/* right subtree too tall: left rotation needed */
if (tmpnode->childs[AVL_RIGHT]->balance > 0) {
tmpnode->balance = 0;
tmpnode->childs[AVL_LEFT]->balance = 0;
-
- } else {
+ }
+ else {
avl_rotate_right(&tmpnode->childs[AVL_RIGHT]);
avl_rotate_left(&tmpnode);
avl_adjust_balance(tmpnode);
}
-
- } else {
+ }
+ else {
insert = 1;
}
}
*******************************************************************************/
-bool avl_insert(avl_tree *tree, void *data)
+bool avl_insert(avl_tree_t *tree, void *data)
{
assert(tree);
assert(data);
-#if defined(ENABLE_THREADS)
- builtin_monitorenter(tree->lock);
-#endif
+ Mutex_lock(tree->mutex);
/* if we don't have a root node, create one */
- if (tree->root == NULL) {
+ if (tree->root == NULL)
tree->root = avl_newnode(data);
-
- } else {
+ else
avl_insert_intern(tree, &tree->root, data);
- }
/* increase entries count */
tree->entries++;
-#if 0
- printf("tree=%p entries=%d\n", tree, tree->entries);
-
- printf("-------------------\n");
- avl_dump(tree->root, 0);
- printf("-------------------\n");
-#endif
-
-#if defined(ENABLE_THREADS)
- builtin_monitorexit(tree->lock);
-#endif
+ Mutex_unlock(tree->mutex);
/* insertion was ok */
*******************************************************************************/
-void *avl_find(avl_tree *tree, void *data)
+void *avl_find(avl_tree_t *tree, void *data)
{
- avl_node *node;
- s4 res;
+ avl_node_t *node;
+ s4 res;
assert(tree);
assert(data);
-#if defined(ENABLE_THREADS)
- builtin_monitorenter(tree->lock);
-#endif
+ Mutex_lock(tree->mutex);
/* search the tree for the given node */
for (node = tree->root; node != NULL; ) {
/* compare the current node */
- res = tree->comparator(data, node->data);
+ res = tree->comparator(node->data, data);
/* was the entry found? return it */
if (res == 0) {
-#if defined(ENABLE_THREADS)
- builtin_monitorexit(tree->lock);
-#endif
+ Mutex_unlock(tree->mutex);
return node->data;
}
node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT];
}
-#if defined(ENABLE_THREADS)
- builtin_monitorexit(tree->lock);
-#endif
+ Mutex_unlock(tree->mutex);
/* entry was not found, returning NULL */
*******************************************************************************/
#if !defined(NDEBUG)
-void avl_dump(avl_node* node, s4 indent)
+void avl_dump(avl_node_t* node, s4 indent)
{
s4 tmp;
if (node->childs[AVL_RIGHT])
avl_dump(node->childs[AVL_RIGHT], tmp + 1);
+ log_start();
+
while(indent--)
- printf(" ");
+ log_print(" ");
- printf("%p (%d)\n", node->data, node->balance);
+ log_print("%p (%d)", node->data, node->balance);
+ log_finish();
if (node->childs[AVL_LEFT])
avl_dump(node->childs[AVL_LEFT], tmp + 1);
projects / cacao.git / blobdiff