1 /* src/toolbox/avl.h - AVL tree implementation
3 Copyright (C) 1996-2005, 2006 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 Contact: cacao@cacaojvm.org
27 Authors: Christian Thalinger
31 $Id: avl.h 4357 2006-01-22 23:33:38Z twisti $
43 #include "vm/global.h"
46 /* define direction in an AVL node ********************************************/
52 /* tree comparator prototype **************************************************/
54 typedef s4 avl_comparator(const void *a, const void *b);
57 /* forward typedefs ***********************************************************/
59 typedef struct avl_tree avl_tree;
60 typedef struct avl_node avl_node;
63 /* avl_tree *******************************************************************/
66 avl_node *root; /* pointer to root node */
67 avl_comparator *comparator; /* pointer to comparison function */
68 s4 entries; /* contains number of entries */
69 #if defined(USE_THREADS)
70 java_objectheader *lock; /* threads lock object */
75 /* avl_node *******************************************************************/
78 void *data; /* pointer to data structure */
79 s4 balance; /* the range of the field is -2...2 */
80 avl_node *childs[2]; /* pointers to the child nodes */
84 /* function prototypes ********************************************************/
86 avl_tree *avl_create(avl_comparator *compar);
87 bool avl_insert(avl_tree *tree, void *data);
88 void *avl_find(avl_tree *tree, void *data);
91 void avl_dump(avl_node* node, s4 indent);
98 * These are local overrides for various environment variables in Emacs.
99 * Please do not remove this and leave it at the end of the file, where
100 * Emacs will automagically detect them.
101 * ---------------------------------------------------------------------
104 * indent-tabs-mode: t