/* src/toolbox/avl.h - 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.h 4921 2006-05-15 14:24:36Z twisti $
-
*/
#include "vm/types.h"
+#include "threads/mutex.hpp"
+
#include "vm/global.h"
/* tree comparator prototype **************************************************/
-typedef s4 avl_comparator(const void *a, const void *b);
+typedef s4 avl_comparator(const void *treenode, const void *node);
/* forward typedefs ***********************************************************/
-typedef struct avl_tree avl_tree;
-typedef struct avl_node avl_node;
+typedef struct avl_tree_t avl_tree_t;
+typedef struct avl_node_t avl_node_t;
-/* avl_tree *******************************************************************/
+/* avl_tree_t *****************************************************************/
-struct avl_tree {
-#if defined(ENABLE_THREADS)
- java_objectheader *lock; /* threads lock object */
-#endif
- avl_node *root; /* pointer to root node */
- avl_comparator *comparator; /* pointer to comparison function */
- s4 entries; /* contains number of entries */
+struct avl_tree_t {
+ Mutex* mutex; ///< Mutex to lock the tree.
+ avl_node_t *root; /* pointer to root node */
+ avl_comparator *comparator; /* pointer to comparison function */
+ s4 entries; /* contains number of entries */
};
-/* avl_node *******************************************************************/
+/* avl_node_t *****************************************************************/
-struct avl_node {
- void *data; /* pointer to data structure */
- s4 balance; /* the range of the field is -2...2 */
- avl_node *childs[2]; /* pointers to the child nodes */
+struct avl_node_t {
+ void *data; /* pointer to data structure */
+ s4 balance; /* the range of the field is -2...2 */
+ avl_node_t *childs[2]; /* pointers to the child nodes */
};
/* function prototypes ********************************************************/
-avl_tree *avl_create(avl_comparator *compar);
-bool avl_insert(avl_tree *tree, void *data);
-void *avl_find(avl_tree *tree, void *data);
+avl_tree_t *avl_create(avl_comparator *comparator);
+bool avl_insert(avl_tree_t *tree, void *data);
+void *avl_find(avl_tree_t *tree, void *data);
#if !defined(NDEBUG)
-void avl_dump(avl_node* node, s4 indent);
+void avl_dump(avl_node_t* node, s4 indent);
#endif
#endif /* _AVL_H */