Line data Source code
1 : /* src/toolbox/avl.c - AVL tree implementation
2 :
3 : Copyright (C) 1996-2013
4 : CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
5 :
6 : This file is part of CACAO.
7 :
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.
12 :
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.
17 :
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
21 : 02110-1301, USA.
22 :
23 : */
24 :
25 : #include "toolbox/avl.hpp"
26 : #include <assert.h> // for assert
27 : #include <stddef.h> // for NULL
28 : #include "mm/memory.hpp" // for NEW
29 : #include "threads/mutex.hpp" // for Mutex
30 : #include "toolbox/logging.hpp" // for log_print, log_finish, etc
31 : #include "vm/types.hpp" // for s4
32 : #include "vm/vm.hpp" // for vm_abort
33 :
34 : /* define direction in an AVL node ********************************************/
35 :
36 : #define AVL_LEFT 0
37 : #define AVL_RIGHT 1
38 :
39 :
40 : /* avl_tree_t *****************************************************************/
41 :
42 : struct avl_tree_t {
43 : Mutex* mutex; ///< Mutex to lock the tree.
44 : avl_node_t *root; /* pointer to root node */
45 : avl_comparator *comparator; /* pointer to comparison function */
46 : s4 entries; /* contains number of entries */
47 : };
48 :
49 :
50 : /* avl_node_t *****************************************************************/
51 :
52 : struct avl_node_t {
53 : void *data; /* pointer to data structure */
54 : s4 balance; /* the range of the field is -2...2 */
55 : avl_node_t *childs[2]; /* pointers to the child nodes */
56 : };
57 :
58 :
59 : /* avl_create ******************************************************************
60 :
61 : Creates a AVL tree structure.
62 :
63 : *******************************************************************************/
64 :
65 163 : avl_tree_t *avl_create(avl_comparator *comparator)
66 : {
67 : avl_tree_t *t;
68 :
69 163 : t = NEW(avl_tree_t);
70 :
71 163 : t->mutex = new Mutex();
72 163 : t->root = NULL;
73 163 : t->comparator = comparator;
74 163 : t->entries = 0;
75 :
76 163 : return t;
77 : }
78 :
79 :
80 : /* avl_newnode *****************************************************************
81 :
82 : Creates a new AVL node and sets the pointers correctly.
83 :
84 : *******************************************************************************/
85 :
86 99619 : static avl_node_t *avl_newnode(void *data)
87 : {
88 : avl_node_t *n;
89 :
90 99619 : n = NEW(avl_node_t);
91 :
92 99619 : n->data = data;
93 :
94 : /* ATTENTION: NEW allocates memory zeroed out */
95 :
96 : /* n->balance = 0; */
97 : /* n->childs[0] = NULL; */
98 : /* n->childs[1] = NULL; */
99 :
100 99619 : return n;
101 : }
102 :
103 :
104 : /* avl_rotate_left *************************************************************
105 :
106 : Does a left rotation on an AVL node.
107 :
108 : A (node) B
109 : \ / \
110 : B --> A C
111 : \
112 : C
113 :
114 : *******************************************************************************/
115 :
116 98067 : static void avl_rotate_left(avl_node_t **node)
117 : {
118 : avl_node_t *tmp;
119 : avl_node_t *tmpnode;
120 :
121 : /* rotate the node */
122 :
123 98067 : tmp = *node;
124 98067 : tmpnode = tmp->childs[AVL_RIGHT];
125 98067 : tmp->childs[AVL_RIGHT] = tmpnode->childs[AVL_LEFT];
126 98067 : tmpnode->childs[AVL_LEFT] = tmp;
127 :
128 : /* set new parent node */
129 :
130 98067 : *node = tmpnode;
131 98067 : }
132 :
133 :
134 : /* avl_rotate_right ************************************************************
135 :
136 : Does a right rotation on an AVL node.
137 :
138 : C (node) B
139 : / / \
140 : B --> A C
141 : /
142 : A
143 :
144 : *******************************************************************************/
145 :
146 99 : static void avl_rotate_right(avl_node_t **node)
147 : {
148 : avl_node_t *tmp;
149 : avl_node_t *tmpnode;
150 :
151 : /* rotate the node */
152 :
153 99 : tmp = *node;
154 99 : tmpnode = tmp->childs[AVL_LEFT];
155 99 : tmp->childs[AVL_LEFT] = tmpnode->childs[AVL_RIGHT];
156 99 : tmpnode->childs[AVL_RIGHT] = tmp;
157 :
158 : /* set new parent node */
159 :
160 99 : *node = tmpnode;
161 99 : }
162 :
163 :
164 : /* avl_adjust_balance **********************************************************
165 :
166 : Does a balance adjustment after a double rotation.
167 :
168 : *******************************************************************************/
169 :
170 97 : static void avl_adjust_balance(avl_node_t *node)
171 : {
172 : avl_node_t *left;
173 : avl_node_t *right;
174 :
175 97 : left = node->childs[AVL_LEFT];
176 97 : right = node->childs[AVL_RIGHT];
177 :
178 97 : switch (node->balance) {
179 : case -1:
180 4 : left->balance = 0;
181 4 : right->balance = 1;
182 4 : break;
183 :
184 : case 0:
185 61 : left->balance = 0;
186 61 : right->balance = 0;
187 61 : break;
188 :
189 : case 1:
190 32 : left->balance = -1;
191 32 : right->balance = 0;
192 : break;
193 : }
194 :
195 97 : node->balance = 0;
196 97 : }
197 :
198 :
199 : /* avl_insert_intern ***********************************************************
200 :
201 : Inserts a AVL node into a AVL tree.
202 :
203 : *******************************************************************************/
204 :
205 850429 : static s4 avl_insert_intern(avl_tree_t *tree, avl_node_t **node, void *data)
206 : {
207 : avl_node_t *tmpnode;
208 : s4 res;
209 : s4 direction;
210 : s4 insert;
211 : s4 balance;
212 :
213 : /* set temporary variable */
214 :
215 850429 : tmpnode = *node;
216 :
217 : /* per default no node was inserted */
218 :
219 850429 : insert = 0;
220 :
221 : /* compare the current node */
222 :
223 850429 : res = tree->comparator(tmpnode->data, data);
224 :
225 : /* is this node already in the tree? */
226 :
227 850429 : if (res == 0)
228 0 : vm_abort("avl_insert_intern: node already in the tree");
229 :
230 : /* goto left or right child */
231 :
232 850429 : direction = (res < 0) ? AVL_LEFT : AVL_RIGHT;
233 :
234 : /* there is a child, go recursive */
235 :
236 850429 : if (tmpnode->childs[direction]) {
237 750973 : balance = avl_insert_intern(tree, &tmpnode->childs[direction], data);
238 : }
239 : else {
240 : avl_node_t *newnode;
241 :
242 : /* no child, create this node */
243 :
244 99456 : newnode = avl_newnode(data);
245 :
246 : /* insert into parent node */
247 :
248 99456 : tmpnode->childs[direction] = newnode;
249 :
250 : /* node was inserted, but don't set insert to 1, since this
251 : insertion is handled in this recursion depth */
252 :
253 99456 : balance = 1;
254 : }
255 :
256 : /* add insertion value to node balance, value depends on the
257 : direction */
258 :
259 850429 : tmpnode->balance += (direction == AVL_LEFT) ? -balance : balance;
260 :
261 850429 : if ((balance != 0) && (tmpnode->balance != 0)) {
262 294990 : if (tmpnode->balance < -1) {
263 : /* left subtree too tall: right rotation needed */
264 :
265 96 : if (tmpnode->childs[AVL_LEFT]->balance < 0) {
266 2 : avl_rotate_right(&tmpnode);
267 :
268 : /* simple balance adjustments */
269 :
270 2 : tmpnode->balance = 0;
271 2 : tmpnode->childs[AVL_RIGHT]->balance = 0;
272 : }
273 : else {
274 94 : avl_rotate_left(&tmpnode->childs[AVL_LEFT]);
275 94 : avl_rotate_right(&tmpnode);
276 94 : avl_adjust_balance(tmpnode);
277 : }
278 : }
279 294894 : else if (tmpnode->balance > 1) {
280 : /* right subtree too tall: left rotation needed */
281 :
282 97973 : if (tmpnode->childs[AVL_RIGHT]->balance > 0) {
283 97970 : avl_rotate_left(&tmpnode);
284 :
285 : /* simple balance adjustments */
286 :
287 97970 : tmpnode->balance = 0;
288 97970 : tmpnode->childs[AVL_LEFT]->balance = 0;
289 : }
290 : else {
291 3 : avl_rotate_right(&tmpnode->childs[AVL_RIGHT]);
292 3 : avl_rotate_left(&tmpnode);
293 3 : avl_adjust_balance(tmpnode);
294 : }
295 : }
296 : else {
297 196921 : insert = 1;
298 : }
299 : }
300 :
301 : /* set back node */
302 :
303 850429 : *node = tmpnode;
304 :
305 : /* insertion was ok */
306 :
307 850429 : return insert;
308 : }
309 :
310 :
311 : /* avl_insert ******************************************************************
312 :
313 : Inserts a AVL node into a AVL tree.
314 :
315 : *******************************************************************************/
316 :
317 99619 : bool avl_insert(avl_tree_t *tree, void *data)
318 : {
319 99619 : assert(tree);
320 99619 : assert(data);
321 :
322 99619 : tree->mutex->lock();
323 :
324 : /* if we don't have a root node, create one */
325 :
326 99619 : if (tree->root == NULL)
327 163 : tree->root = avl_newnode(data);
328 : else
329 99456 : avl_insert_intern(tree, &tree->root, data);
330 :
331 : /* increase entries count */
332 :
333 99619 : tree->entries++;
334 :
335 99619 : tree->mutex->unlock();
336 :
337 : /* insertion was ok */
338 :
339 99619 : return true;
340 : }
341 :
342 :
343 : /* avl_find ********************************************************************
344 :
345 : Find a given data structure in the AVL tree, with the comparision
346 : function of the tree.
347 :
348 : *******************************************************************************/
349 :
350 2235495 : void *avl_find(avl_tree_t *tree, void *data)
351 : {
352 : avl_node_t *node;
353 : s4 res;
354 :
355 2235495 : assert(tree);
356 2235495 : assert(data);
357 :
358 2235495 : tree->mutex->lock();
359 :
360 : /* search the tree for the given node */
361 :
362 24927708 : for (node = tree->root; node != NULL; ) {
363 : /* compare the current node */
364 :
365 22692213 : res = tree->comparator(node->data, data);
366 :
367 : /* was the entry found? return it */
368 :
369 22692213 : if (res == 0) {
370 2235495 : tree->mutex->unlock();
371 :
372 2235495 : return node->data;
373 : }
374 :
375 : /* goto left or right child */
376 :
377 20456718 : node = node->childs[(res < 0) ? AVL_LEFT : AVL_RIGHT];
378 : }
379 :
380 0 : tree->mutex->unlock();
381 :
382 : /* entry was not found, returning NULL */
383 :
384 0 : return NULL;
385 : }
386 :
387 :
388 : /* avl_dump ********************************************************************
389 :
390 : Dumps the AVL tree starting with node.
391 :
392 : *******************************************************************************/
393 :
394 : #if !defined(NDEBUG)
395 0 : void avl_dump(avl_node_t* node, s4 indent)
396 : {
397 : s4 tmp;
398 :
399 0 : tmp = indent;
400 :
401 0 : if (node == NULL)
402 0 : return;
403 :
404 0 : if (node->childs[AVL_RIGHT])
405 0 : avl_dump(node->childs[AVL_RIGHT], tmp + 1);
406 :
407 0 : log_start();
408 :
409 0 : while(indent--)
410 0 : log_print(" ");
411 :
412 0 : log_print("%p (%d)", node->data, node->balance);
413 0 : log_finish();
414 :
415 0 : if (node->childs[AVL_LEFT])
416 0 : avl_dump(node->childs[AVL_LEFT], tmp + 1);
417 : }
418 : #endif
419 :
420 :
421 : /*
422 : * These are local overrides for various environment variables in Emacs.
423 : * Please do not remove this and leave it at the end of the file, where
424 : * Emacs will automagically detect them.
425 : * ---------------------------------------------------------------------
426 : * Local variables:
427 : * mode: c++
428 : * indent-tabs-mode: t
429 : * c-basic-offset: 4
430 : * tab-width: 4
431 : * End:
432 : */
|
