* src/vm/vm.c, src/vm/vm.h: Moved to .cpp.

[cacao.git] / src / toolbox / avl.c

diff --git a/src/toolbox/avl.c b/src/toolbox/avl.c
index 799fa7ea8fe0f4565bd9c486eb7ffea74dcfe19e..0b6b481442b3c57435f42ef3287b3e56f3f94e7f 100644 (file)
--- a/src/toolbox/avl.c
+++ b/src/toolbox/avl.c
@@ -1,9 +1,7 @@
 /* src/toolbox/avl.c - AVL tree implementation
 
-   Copyright (C) 1996-2005, 2006, 2007 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.
 
@@ -22,8 +20,6 @@
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
    02110-1301, USA.
 
-   $Id: avl.c 7859 2007-05-03 08:29:16Z twisti $
-
 */
 
 
@@ -38,6 +34,10 @@
 #include "threads/lock-common.h"
 
 #include "toolbox/avl.h"
+#include "toolbox/logging.h"
+
+#include "vm/global.h"
+#include "vm/vm.hpp"
 
 
 /* avl_create ******************************************************************
@@ -46,20 +46,20 @@
 
 *******************************************************************************/
 
-avl_tree_t *avl_create(avl_comparator *compar)
+avl_tree_t *avl_create(avl_comparator *comparator)
 {
        avl_tree_t *t;
 
        t = NEW(avl_tree_t);
 
        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);
+       t->lock       = NEW(java_object_t);
 
        LOCK_INIT_OBJECT_LOCK(t->lock);
 #endif
@@ -211,12 +211,12 @@ static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
 
        /* 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 */
 
@@ -226,8 +226,8 @@ static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
 
        if (tmpnode->childs[direction]) {
                balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
-
-       } else {
+       }
+       else {
                avl_node_t *newnode;
 
                /* no child, create this node */
@@ -260,14 +260,14 @@ static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
 
                                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) {
@@ -277,14 +277,14 @@ static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
 
                                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;
                }
        }
@@ -314,25 +314,15 @@ bool avl_insert(avl_tree_t *tree, void *data)
 
        /* 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
-
        LOCK_MONITOR_EXIT(tree->lock);
 
        /* insertion was ok */
@@ -363,7 +353,7 @@ void *avl_find(avl_tree_t *tree, void *data)
        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 */
 
@@ -405,10 +395,13 @@ void avl_dump(avl_node_t* node, s4 indent)
        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);