1 /* -*- Mode: c; c-basic-offset: 2 -*-
2 *
3 * raptor_avltree.c - Balanced Binary Tree / AVL Tree
4 *
5 * This file is in the public domain.
6 *
7 * Based on public domain sources posted to comp.sources.misc in 1993
8 *
9 * From: p...@vix.com (Paul Vixie)
10 * Newsgroups: comp.sources.unix
11 * Subject: v27i034: REPOST AVL Tree subroutines (replaces v11i020 from 1987), Part01/01
12 * Date: 6 Sep 1993 13:51:22 -0700
13 * Message-ID: <1.747348668.4037@gw.home.vix.com>
14 *
15 * ----------------------------------------------------------------------
16 * Original headers below
17 */
18
19 /* as_tree - tree library for as
20 * vix 14dec85 [written]
21 * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
22 * vix 06feb86 [added tree_mung()]
23 * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
24 * vix 23jun86 [added delete uar to add for replaced nodes]
25 * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
26 */
27
28
29 /* This program text was created by Paul Vixie using examples from the book:
30 * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
31 * 0-13-022005-1. This code and associated documentation is hereby placed
32 * in the public domain.
33 */
34
35
36 #ifdef HAVE_CONFIG_H
37 #include <raptor_config.h>
38 #endif
39
40 #ifdef WIN32
41 #include <win32_raptor_config.h>
42 #endif
43
44 #ifdef HAVE_STDLIB_H
45 #include <stdlib.h>
46 #endif
47
48
49 /* Raptor includes */
50 #include "raptor.h"
51 #include "raptor_internal.h"
52
53
54 #if RAPTOR_DEBUG > 1
55 #define RAPTOR_AVLTREE_DEBUG1(msg) RAPTOR_DEBUG1(msg)
56 #else
57 #define RAPTOR_AVLTREE_DEBUG1(msg)
58 #endif
59
60
61 #define RAPTOR_AVLTREE_ENOMEM -1
62 #define RAPTOR_AVLTREE_EXISTS 1
63
64
65 #ifndef STANDALONE
66
67 /* AVL-tree node */
68 struct raptor_avltree_node_s {
69 /* parent tree */
70 struct raptor_avltree_node_s *parent;
71
72 /* left child tree */
73 struct raptor_avltree_node_s *left;
74
75 /* right child tree */
76 struct raptor_avltree_node_s *right;
77
78 /* balance factor =
79 * height of the right tree minus the height of the left tree
80 * i.e. equal: 0 left larger: -1 right larger: 1
81 */
82 signed char balance;
83
84 /* actual data */
85 void* data;
86 };
87
88
89 #ifndef TRUE
90 #define TRUE 1
91 #define FALSE 0
92 #endif
93
94
95 /* local prototypes */
96 static int raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p);
97 static void* raptor_avltree_delete_internal(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p);
98 static void* raptor_avltree_delete_internal2(raptor_avltree* tree, raptor_avltree_node** ppr_r, int *rebalancing_p, raptor_avltree_node** ppr_q);
99 static void raptor_avltree_balance_left(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p);
100 static void raptor_avltree_balance_right(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p);
101 static raptor_avltree_node* raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node, const void* p_data);
102 static int raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node, int depth, raptor_avltree_visit_function visit_fn, void* user_data);
103 static void raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node);
104
105
106
107 /*
108 * raptor_new_avltree:
109 * @world: raptor_world object
110 * @compare_fn: item comparison function for ordering
111 * @free_fn: item free function (or NULL)
112 * @flags: AVLTree flags - bitmask of
113 * RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES - raptor_avltree_add()
114 * will replace any duplicate items (default is to ignore them and
115 * return >0 on duplicates)
116 *
117 * INTERNAL - AVL Tree Constructor
118 *
119 * Return value: new AVL Tree or NULL on failure
120 */
121 raptor_avltree*
raptor_new_avltree(raptor_world * world,raptor_data_compare_function compare_fn,raptor_data_free_function free_fn,unsigned int flags)122 raptor_new_avltree(raptor_world* world,
123 raptor_data_compare_function compare_fn,
124 raptor_data_free_function free_fn,
125 unsigned int flags)
126 {
127 raptor_avltree* tree;
128
129 tree=(raptor_avltree*)RAPTOR_MALLOC(raptor_avltree, sizeof(*tree));
130 if(!tree)
131 return NULL;
132
133 tree->world=world;
134 tree->root=NULL;
135 tree->compare_fn=compare_fn;
136 tree->free_fn=free_fn;
137 tree->print_fn=NULL;
138 tree->flags=flags;
139 tree->size=0;
140 tree->cursor_iterator=NULL;
141
142 return tree;
143 }
144
145
146 /*
147 * raptor_free_avltree:
148 * @tree: AVLTree object
149 *
150 * INTERNAL - AVL Tree destructor
151 */
152 void
raptor_free_avltree(raptor_avltree * tree)153 raptor_free_avltree(raptor_avltree* tree)
154 {
155 RAPTOR_ASSERT_OBJECT_POINTER_RETURN(tree, raptor_avltree);
156
157 raptor_free_avltree_internal(tree, tree->root);
158
159 if(tree->cursor_iterator)
160 raptor_free_avltree_iterator(tree->cursor_iterator);
161
162 RAPTOR_FREE(raptor_avltree, tree);
163 }
164
165
166 static void
raptor_free_avltree_internal(raptor_avltree * tree,raptor_avltree_node * node)167 raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node)
168 {
169 if(node) {
170 raptor_free_avltree_internal(tree, node->left);
171
172 raptor_free_avltree_internal(tree, node->right);
173
174 if(tree->free_fn)
175 tree->free_fn(node->data);
176 tree->size--;
177 RAPTOR_FREE(raptor_avltree_node, node);
178 }
179 }
180
181
182 /* methods */
183
184 static raptor_avltree_node*
raptor_avltree_search_internal(raptor_avltree * tree,raptor_avltree_node * node,const void * p_data)185 raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node,
186 const void* p_data)
187 {
188 if(node) {
189 int cmp= tree->compare_fn(p_data, node->data);
190
191 if(cmp > 0)
192 return raptor_avltree_search_internal(tree, node->right, p_data);
193 else if(cmp < 0)
194 return raptor_avltree_search_internal(tree, node->left, p_data);
195
196 /* found */
197 return node;
198 }
199
200 /* otherwise not found */
201 return NULL;
202 }
203
204
205 /*
206 * raptor_avltree_search:
207 * @tree: AVL Tree object
208 * @p_data: pointer to data item
209 *
210 * INTERNAL - find an item in an AVL Tree
211 *
212 * Return value: shared pointer to item (still owned by AVL Tree) or NULL on failure or if not found
213 */
214 void*
raptor_avltree_search(raptor_avltree * tree,const void * p_data)215 raptor_avltree_search(raptor_avltree* tree, const void* p_data)
216 {
217 raptor_avltree_node* node;
218 node=raptor_avltree_search_internal(tree, tree->root, p_data);
219 return node ? node->data : NULL;
220 }
221
222
223 /*
224 * raptor_avltree_add:
225 * @tree: AVL Tree object
226 * @p_data: pointer to data item
227 *
228 * INTERNAL - add an item to an AVL Tree
229 *
230 * The item added becomes owned by the AVL Tree, and will be freed by
231 * the free_fn argument given to raptor_new_avltree().
232 *
233 * Return value: 0 on success, >0 if equivalent item exists (and the old element remains in the tree), <0 on failure
234 */
235 int
raptor_avltree_add(raptor_avltree * tree,void * p_data)236 raptor_avltree_add(raptor_avltree* tree, void* p_data)
237 {
238 int rebalancing= FALSE;
239 int rv;
240
241 rv=raptor_avltree_sprout(tree, NULL, &tree->root, p_data,
242 &rebalancing);
243 #if RAPTOR_DEBUG > 1
244 raptor_avltree_check(tree);
245 #endif
246
247 return rv;
248 }
249
250
251 /*
252 * raptor_avltree_remove:
253 * @tree: AVL Tree object
254 * @p_data: pointer to data item
255 *
256 * INTERNAL - remove an item from an AVL Tree and return it
257 *
258 * The item removed is no longer owned by the AVL Tree and is
259 * owned by the caller.
260 *
261 * Return value: object or NULL on failure or if not found
262 */
263 void*
raptor_avltree_remove(raptor_avltree * tree,void * p_data)264 raptor_avltree_remove(raptor_avltree* tree, void* p_data)
265 {
266 int rebalancing= FALSE;
267 void* rdata;
268
269 rdata=raptor_avltree_delete_internal(tree, &tree->root, p_data,
270 &rebalancing);
271 if(rdata)
272 tree->size--;
273
274 #if RAPTOR_DEBUG > 1
275 raptor_avltree_check(tree);
276 #endif
277
278 return rdata;
279 }
280
281
282 /*
283 * raptor_avltree_delete:
284 * @tree: AVL Tree object
285 * @p_data: pointer to data item
286 *
287 * INTERNAL - remove an item from an AVL Tree and free it
288 */
289 int
raptor_avltree_delete(raptor_avltree * tree,void * p_data)290 raptor_avltree_delete(raptor_avltree* tree, void* p_data)
291 {
292 void* rdata;
293
294 rdata=raptor_avltree_remove(tree, p_data);
295 if(rdata) {
296 if(tree->free_fn)
297 tree->free_fn(rdata);
298 }
299
300 return (rdata != NULL);
301 }
302
303
304 static int
raptor_avltree_visit_internal(raptor_avltree * tree,raptor_avltree_node * node,int depth,raptor_avltree_visit_function visit_fn,void * user_data)305 raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node,
306 int depth,
307 raptor_avltree_visit_function visit_fn,
308 void* user_data)
309 {
310 if(!node)
311 return TRUE;
312
313 if(!raptor_avltree_visit_internal(tree, node->left, depth+1,
314 visit_fn, user_data))
315 return FALSE;
316
317 if(!visit_fn(depth, node->data, user_data))
318 return FALSE;
319
320 if(!raptor_avltree_visit_internal(tree, node->right, depth+1,
321 visit_fn, user_data))
322 return FALSE;
323
324 return TRUE;
325 }
326
327
328 /*
329 * raptor_avltree_visit:
330 * @tree: AVL Tree object
331 * @visit_fn: visit function to call at each item
332 * @user_data: user data pointer fo visit function
333 *
334 * INTERNAL - perform an in-order visit of the items in the AVL Tree
335 *
336 * Return value: non-0 if traversal was terminated early by @visit_fn
337 */
338 int
raptor_avltree_visit(raptor_avltree * tree,raptor_avltree_visit_function visit_fn,void * user_data)339 raptor_avltree_visit(raptor_avltree* tree,
340 raptor_avltree_visit_function visit_fn,
341 void* user_data)
342 {
343 return raptor_avltree_visit_internal(tree, tree->root, 0,
344 visit_fn, user_data);
345 }
346
347
348 #ifdef RAPTOR_DEBUG
349 static void
raptor_avltree_print_node(raptor_avltree_node * node)350 raptor_avltree_print_node(raptor_avltree_node* node)
351 {
352 fprintf(stderr, "%p: parent %p left %p right %p data %p",
353 node, node->parent, node->left, node->right, node->data);
354 }
355
356
357 static void
raptor_avltree_check_node(raptor_avltree * tree,raptor_avltree_node * node,const char * fn,const char * where)358 raptor_avltree_check_node(raptor_avltree* tree, raptor_avltree_node* node,
359 const char* fn, const char* where)
360 {
361 if(node->parent) {
362 if((node->parent == node->left) || (node->parent == node->right)) {
363 if(fn && where)
364 fprintf(stderr, "%s (%s): ", fn, where);
365 fputs("ERROR bad node ", stderr);
366 raptor_avltree_print_node(node);
367 fputc('\n', stderr);
368 fflush(stderr);
369 abort();
370 }
371 if(node->parent->left != node && node->parent->right != node) {
372 if(fn && where)
373 fprintf(stderr, "%s (%s): ", fn, where);
374 fputs("ERROR parent node ", stderr);
375 raptor_avltree_print_node(node->parent);
376 fputs(" has no reference to child node ", stderr);
377 raptor_avltree_print_node(node);
378 fputc('\n', stderr);
379 fflush(stderr);
380 abort();
381 }
382 }
383 }
384 #endif
385
386
387 static int
raptor_avltree_sprout_left(raptor_avltree * tree,raptor_avltree_node ** node_pp,void * p_data,int * rebalancing_p)388 raptor_avltree_sprout_left(raptor_avltree* tree, raptor_avltree_node** node_pp,
389 void* p_data, int *rebalancing_p)
390 {
391 raptor_avltree_node *p1, *p2, *p_parent;
392 int rc;
393
394 RAPTOR_AVLTREE_DEBUG1("LESS. raptor_avltree_sprouting left.\n");
395
396 p_parent=(*node_pp)->parent;
397
398 rc=raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->left, p_data,
399 rebalancing_p);
400 if(rc)
401 return rc;
402
403 if(!*rebalancing_p)
404 return FALSE;
405
406 /* left branch has grown longer */
407 RAPTOR_AVLTREE_DEBUG1("LESS: left branch has grown\n");
408 switch((*node_pp)->balance) {
409 case 1:
410 /* right branch WAS longer; balance is ok now */
411 RAPTOR_AVLTREE_DEBUG1("LESS: case 1.. balance restored implicitly\n");
412 (*node_pp)->balance= 0;
413 *rebalancing_p= FALSE;
414 break;
415
416 case 0:
417 /* balance WAS okay; now left branch longer */
418 RAPTOR_AVLTREE_DEBUG1("LESS: case 0.. balance bad but still ok\n");
419 (*node_pp)->balance= -1;
420 break;
421
422 case -1:
423 /* left branch was already too long. rebalance */
424 RAPTOR_AVLTREE_DEBUG1("LESS: case -1: rebalancing\n");
425 p1= (*node_pp)->left;
426
427 if(p1->balance == -1) {
428 /* LL */
429 RAPTOR_AVLTREE_DEBUG1("LESS: single LL\n");
430 (*node_pp)->left= p1->right;
431 if((*node_pp)->left)
432 (*node_pp)->left->parent=(*node_pp);
433 p1->right = *node_pp;
434 if(p1->right)
435 p1->right->parent=p1;
436 (*node_pp)->balance= 0;
437 *node_pp= p1;
438 (*node_pp)->parent=p_parent;
439 } else {
440 /* double LR */
441 RAPTOR_AVLTREE_DEBUG1("LESS: double LR\n");
442 p2= p1->right;
443 p1->right= p2->left;
444 if(p1->right)
445 p1->right->parent=p1;
446 p2->left= p1;
447 if(p2->left)
448 p2->left->parent=p2;
449
450 (*node_pp)->left= p2->right;
451 if((*node_pp)->left)
452 (*node_pp)->left->parent= (*node_pp);
453 p2->right= *node_pp;
454 if(p2->right)
455 p2->right->parent=p2;
456
457 if(p2->balance == -1)
458 (*node_pp)->balance= 1;
459 else
460 (*node_pp)->balance= 0;
461
462 if(p2->balance == 1)
463 p1->balance= -1;
464 else
465 p1->balance= 0;
466 *node_pp = p2;
467 (*node_pp)->parent=p_parent;
468 } /* end else */
469
470 (*node_pp)->balance= 0;
471 *rebalancing_p= FALSE;
472 } /* end switch */
473
474 return FALSE;
475 }
476
477
478 static int
raptor_avltree_sprout_right(raptor_avltree * tree,raptor_avltree_node ** node_pp,void * p_data,int * rebalancing_p)479 raptor_avltree_sprout_right(raptor_avltree* tree,
480 raptor_avltree_node** node_pp,
481 void* p_data, int *rebalancing_p)
482 {
483 raptor_avltree_node *p1, *p2, *p_parent;
484 int rc;
485
486 RAPTOR_AVLTREE_DEBUG1("MORE: raptor_avltree_sprouting to the right\n");
487
488 p_parent=(*node_pp)->parent;
489
490 rc=raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->right, p_data,
491 rebalancing_p);
492 if(rc)
493 return rc;
494
495 if(!*rebalancing_p)
496 return FALSE;
497
498 /* right branch has grown longer */
499 RAPTOR_AVLTREE_DEBUG1("MORE: right branch has grown\n");
500
501 switch((*node_pp)->balance) {
502 case -1:
503 RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, fixed implicitly\n");
504 (*node_pp)->balance= 0;
505 *rebalancing_p= FALSE;
506 break;
507
508 case 0:
509 RAPTOR_AVLTREE_DEBUG1("MORE: balance was okay, now off but ok\n");
510 (*node_pp)->balance= 1;
511 break;
512
513 case 1:
514 RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, need to rebalance\n");
515 p1= (*node_pp)->right;
516
517 if(p1->balance == 1) {
518 /* RR */
519 RAPTOR_AVLTREE_DEBUG1("MORE: single RR\n");
520 (*node_pp)->right= p1->left;
521 if((*node_pp)->right)
522 (*node_pp)->right->parent= (*node_pp);
523 p1->left= *node_pp;
524 if(p1->left)
525 p1->left->parent= p1;
526 (*node_pp)->balance= 0;
527 *node_pp= p1;
528 (*node_pp)->parent=p_parent;
529 } else {
530 /* double RL */
531 RAPTOR_AVLTREE_DEBUG1("MORE: double RL\n");
532
533 p2= p1->left;
534 p1->left= p2->right;
535 if(p1->left)
536 p1->left->parent=p1;
537 p2->right= p1;
538 if(p2->right)
539 p2->right->parent=p2;
540
541 (*node_pp)->right= p2->left;
542 if((*node_pp)->right)
543 (*node_pp)->right->parent= (*node_pp);
544 p2->left= *node_pp;
545 if(p2->left)
546 p2->left->parent=p2;
547
548 if(p2->balance == 1)
549 (*node_pp)->balance= -1;
550 else
551 (*node_pp)->balance= 0;
552
553 if(p2->balance == -1)
554 p1->balance= 1;
555 else
556 p1->balance= 0;
557
558 *node_pp= p2;
559 (*node_pp)->parent=p_parent;
560 } /* end else */
561
562 (*node_pp)->balance= 0;
563 *rebalancing_p= FALSE;
564 } /* end switch */
565
566 return FALSE;
567 }
568
569
570 /* grow a tree by sprouting with a new node
571 *
572 * Return values:
573 * 0 on success
574 * >0 if equivalent item exists (and the old element remains in the tree)
575 * <0 if memory is exhausted.
576 */
577 static int
raptor_avltree_sprout(raptor_avltree * tree,raptor_avltree_node * parent,raptor_avltree_node ** node_pp,void * p_data,int * rebalancing_p)578 raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent,
579 raptor_avltree_node** node_pp, void* p_data,
580 int *rebalancing_p)
581 {
582 int cmp;
583
584 RAPTOR_AVLTREE_DEBUG1("Enter\n");
585
586 /* If grounded, add the node here, set the rebalance flag and return */
587 if(!*node_pp) {
588 RAPTOR_AVLTREE_DEBUG1("grounded. adding new node, setting rebalancing flag true\n");
589 *node_pp= (raptor_avltree_node*)RAPTOR_MALLOC(raptor_avltree_node, sizeof(**node_pp));
590 if(!*node_pp) {
591 if(tree->free_fn)
592 tree->free_fn(p_data);
593 return RAPTOR_AVLTREE_ENOMEM;
594 }
595
596 (*node_pp)->parent= parent;
597 (*node_pp)->left= NULL;
598 (*node_pp)->right= NULL;
599 (*node_pp)->balance= 0;
600 (*node_pp)->data= p_data;
601 *rebalancing_p= TRUE;
602
603 tree->size++;
604
605 return FALSE;
606 }
607
608 /* compare the data */
609 cmp= tree->compare_fn(p_data, (*node_pp)->data);
610 if(cmp < 0)
611 /* if LESS, prepare to move to the left. */
612 return raptor_avltree_sprout_left(tree, node_pp, p_data, rebalancing_p);
613 else if(cmp > 0)
614 /* if MORE, prepare to move to the right. */
615 return raptor_avltree_sprout_right(tree, node_pp, p_data, rebalancing_p);
616
617 /* otherwise equivalent key */
618 *rebalancing_p= FALSE;
619
620 if(tree->flags & RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES) {
621 /* replace item with equivalent key */
622 if(tree->free_fn)
623 tree->free_fn((*node_pp)->data);
624 (*node_pp)->data= p_data;
625
626 return FALSE;
627 } else {
628 /* ignore item with equivalent key */
629 if(tree->free_fn)
630 tree->free_fn(p_data);
631 return RAPTOR_AVLTREE_EXISTS;
632 }
633 }
634
635
636 static void*
raptor_avltree_delete_internal(raptor_avltree * tree,raptor_avltree_node ** node_pp,void * p_data,int * rebalancing_p)637 raptor_avltree_delete_internal(raptor_avltree* tree,
638 raptor_avltree_node** node_pp,
639 void* p_data,
640 int *rebalancing_p)
641 {
642 int cmp;
643 void* rdata=NULL;
644
645 RAPTOR_AVLTREE_DEBUG1("Enter\n");
646
647 if(*node_pp == NULL) {
648 RAPTOR_AVLTREE_DEBUG1("key not in tree\n");
649 return rdata;
650 }
651
652 cmp= tree->compare_fn((*node_pp)->data, p_data);
653
654 if(cmp > 0) {
655 RAPTOR_AVLTREE_DEBUG1("too high - scan left\n");
656 rdata= raptor_avltree_delete_internal(tree, &(*node_pp)->left, p_data,
657 rebalancing_p);
658 if(*rebalancing_p)
659 raptor_avltree_balance_left(tree, node_pp, rebalancing_p);
660
661 } else if(cmp < 0) {
662 RAPTOR_AVLTREE_DEBUG1("too low - scan right\n");
663 rdata= raptor_avltree_delete_internal(tree, &(*node_pp)->right, p_data,
664 rebalancing_p);
665 if(*rebalancing_p)
666 raptor_avltree_balance_right(tree, node_pp, rebalancing_p);
667
668 } else {
669 raptor_avltree_node *pr_q;
670
671 RAPTOR_AVLTREE_DEBUG1("equal\n");
672 pr_q= *node_pp;
673
674 rdata=pr_q->data;
675
676 if(pr_q->right == NULL) {
677 RAPTOR_AVLTREE_DEBUG1("right subtree null\n");
678 *node_pp= pr_q->left;
679 *rebalancing_p= TRUE;
680 } else if(pr_q->left == NULL) {
681 RAPTOR_AVLTREE_DEBUG1("right subtree non-null, left subtree null\n");
682 *node_pp= pr_q->right;
683 *rebalancing_p= TRUE;
684 } else {
685 RAPTOR_AVLTREE_DEBUG1("neither subtree null\n");
686 rdata=raptor_avltree_delete_internal2(tree, &pr_q->left, rebalancing_p,
687 &pr_q);
688 if(*rebalancing_p)
689 raptor_avltree_balance_left(tree, node_pp, rebalancing_p);
690 }
691
692 RAPTOR_FREE(raptor_avltree_node, pr_q);
693 }
694
695 return rdata;
696 }
697
698
699 static void*
raptor_avltree_delete_internal2(raptor_avltree * tree,raptor_avltree_node ** ppr_r,int * rebalancing_p,raptor_avltree_node ** ppr_q)700 raptor_avltree_delete_internal2(raptor_avltree* tree,
701 raptor_avltree_node** ppr_r,
702 int *rebalancing_p,
703 raptor_avltree_node** ppr_q)
704 {
705 void* rdata=NULL;
706
707 RAPTOR_AVLTREE_DEBUG1("Enter\n");
708
709 if((*ppr_r)->right != NULL) {
710 rdata=raptor_avltree_delete_internal2(tree,
711 &(*ppr_r)->right,
712 rebalancing_p,
713 ppr_q);
714 if(*rebalancing_p)
715 raptor_avltree_balance_right(tree, ppr_r, rebalancing_p);
716
717 } else {
718 rdata=(*ppr_q)->data;
719
720 (*ppr_q)->data= (*ppr_r)->data;
721 *ppr_q= *ppr_r;
722 *ppr_r= (*ppr_r)->left;
723 *rebalancing_p= TRUE;
724 }
725
726 return rdata;
727 }
728
729
730 static void
raptor_avltree_balance_left(raptor_avltree * tree,raptor_avltree_node ** node_pp,int * rebalancing_p)731 raptor_avltree_balance_left(raptor_avltree* tree,
732 raptor_avltree_node** node_pp, int *rebalancing_p)
733 {
734 raptor_avltree_node *p1, *p2, *p_parent;
735 int b1, b2;
736
737 RAPTOR_AVLTREE_DEBUG1("left branch has shrunk\n");
738
739 p_parent=(*node_pp)->parent;
740
741 switch((*node_pp)->balance) {
742 case -1:
743 RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n");
744 (*node_pp)->balance= 0;
745 break;
746
747 case 0:
748 RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n");
749 (*node_pp)->balance= 1;
750 *rebalancing_p= FALSE;
751 break;
752
753 case 1:
754 RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n");
755 p1= (*node_pp)->right;
756 b1= p1->balance;
757
758 if(b1 >= 0) {
759 RAPTOR_AVLTREE_DEBUG1("single RR\n");
760 (*node_pp)->right= p1->left;
761 if((*node_pp)->right)
762 (*node_pp)->right->parent= (*node_pp);
763 p1->left= *node_pp;
764 if(p1->left)
765 p1->left->parent= p1;
766 if(b1 == 0) {
767 RAPTOR_AVLTREE_DEBUG1("b1 == 0\n");
768 (*node_pp)->balance= 1;
769 p1->balance= -1;
770 *rebalancing_p= FALSE;
771 } else {
772 RAPTOR_AVLTREE_DEBUG1("b1 != 0\n");
773 (*node_pp)->balance= 0;
774 p1->balance= 0;
775 }
776 *node_pp= p1;
777 (*node_pp)->parent=p_parent;
778 } else {
779 RAPTOR_AVLTREE_DEBUG1("double RL\n");
780 p2= p1->left;
781 b2= p2->balance;
782 p1->left= p2->right;
783 if(p1->left)
784 p1->left->parent=p1;
785 p2->right= p1;
786 if(p2->right)
787 p2->right->parent=p2;
788 (*node_pp)->right= p2->left;
789 if((*node_pp)->right)
790 (*node_pp)->right->parent= (*node_pp);
791 p2->left= *node_pp;
792 if(p2->left)
793 p2->left->parent= p2;
794 if(b2 == 1)
795 (*node_pp)->balance= -1;
796 else
797 (*node_pp)->balance= 0;
798 if(b2 == -1)
799 p1->balance= 1;
800 else
801 p1->balance= 0;
802 *node_pp= p2;
803 (*node_pp)->parent=p_parent;
804 p2->balance= 0;
805 }
806 break;
807 } /* end switch */
808
809 }
810
811
812 static void
raptor_avltree_balance_right(raptor_avltree * tree,raptor_avltree_node ** node_pp,int * rebalancing_p)813 raptor_avltree_balance_right(raptor_avltree* tree,
814 raptor_avltree_node** node_pp, int *rebalancing_p)
815 {
816 raptor_avltree_node *p1, *p2, *p_parent;
817 int b1, b2;
818
819 RAPTOR_AVLTREE_DEBUG1("right branch has shrunk\n");
820
821 p_parent=(*node_pp)->parent;
822
823 switch((*node_pp)->balance) {
824 case 1:
825 RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n");
826 (*node_pp)->balance= 0;
827 break;
828
829 case 0:
830 RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n");
831 (*node_pp)->balance= -1;
832 *rebalancing_p= FALSE;
833 break;
834
835 case -1:
836 RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n");
837 p1= (*node_pp)->left;
838 b1= p1->balance;
839
840 if(b1 <= 0) {
841 RAPTOR_AVLTREE_DEBUG1("single LL\n");
842 (*node_pp)->left= p1->right;
843 if((*node_pp)->left)
844 (*node_pp)->left->parent= (*node_pp);
845 p1->right= *node_pp;
846 if(p1->right)
847 p1->right->parent= p1;
848 if(b1 == 0) {
849 RAPTOR_AVLTREE_DEBUG1("b1 == 0\n");
850 (*node_pp)->balance= -1;
851 p1->balance= 1;
852 *rebalancing_p= FALSE;
853 } else {
854 RAPTOR_AVLTREE_DEBUG1("b1 != 0\n");
855 (*node_pp)->balance= 0;
856 p1->balance= 0;
857 }
858 *node_pp= p1;
859 (*node_pp)->parent=p_parent;
860 } else {
861 RAPTOR_AVLTREE_DEBUG1("double LR\n");
862 p2= p1->right;
863 b2= p2->balance;
864 p1->right= p2->left;
865 if(p1->right)
866 p1->right->parent= p1;
867 p2->left= p1;
868 if(p2->left)
869 p2->left->parent= p2;
870 (*node_pp)->left= p2->right;
871 if((*node_pp)->left)
872 (*node_pp)->left->parent= (*node_pp);
873 p2->right= *node_pp;
874 if(p2->right)
875 p2->right->parent= p2;
876 if(b2 == -1)
877 (*node_pp)->balance= 1;
878 else
879 (*node_pp)->balance= 0;
880 if(b2 == 1)
881 p1->balance= -1;
882 else
883 p1->balance= 0;
884 *node_pp= p2;
885 (*node_pp)->parent=p_parent;
886 p2->balance= 0;
887 }
888 } /* end switch */
889
890 }
891
892
893 /*
894 * raptor_avltree_size:
895 * @tree: AVL Tree object
896 *
897 * INTERNAL - Get the number of items in the AVL Tree
898 *
899 * Return value: number of items in tree
900 */
901 int
raptor_avltree_size(raptor_avltree * tree)902 raptor_avltree_size(raptor_avltree* tree)
903 {
904 return tree->size;
905 }
906
907
908 /*
909 * raptor_avltree_set_print_handler:
910 * @tree: AVL Tree object
911 * @print_fn: print function
912 *
913 * INTERNAL - set the handler for printing an item in a tree
914 *
915 */
916 void
raptor_avltree_set_print_handler(raptor_avltree * tree,raptor_data_print_function print_fn)917 raptor_avltree_set_print_handler(raptor_avltree* tree,
918 raptor_data_print_function print_fn)
919 {
920 tree->print_fn=print_fn;
921 }
922
923
924 /* Follow left children until a match for range is found (if range not NULL) */
925 static raptor_avltree_node*
raptor_avltree_node_leftmost(raptor_avltree * tree,raptor_avltree_node * node,void * range)926 raptor_avltree_node_leftmost(raptor_avltree* tree, raptor_avltree_node* node,
927 void* range)
928 {
929 /*assert(node);
930 assert(!range || tree->compare_fn(range, node->data) == 0);*/
931 if(range)
932 while(node && node->left &&
933 tree->compare_fn(range, node->left->data) == 0)
934 node=node->left;
935 else
936 while(node && node->left)
937 node=node->left;
938
939 return node;
940 }
941
942
943 static raptor_avltree_node*
raptor_avltree_node_rightmost(raptor_avltree * tree,raptor_avltree_node * node,void * range)944 raptor_avltree_node_rightmost(raptor_avltree* tree, raptor_avltree_node* node,
945 void* range)
946 {
947 /*assert(node);
948 assert(!range || tree->compare_fn(range, node->data) == 0);*/
949 if(range)
950 while(node && node->right &&
951 tree->compare_fn(range, node->right->data) == 0)
952 node=node->right;
953 else
954 while(node && node->right)
955 node=node->right;
956 return node;
957 }
958
959
960 /* Follow right children until a match for range is found (range required) */
961 static raptor_avltree_node*
raptor_avltree_node_search_right(raptor_avltree * tree,raptor_avltree_node * node,void * range)962 raptor_avltree_node_search_right(raptor_avltree* tree,
963 raptor_avltree_node* node, void* range)
964 {
965 raptor_avltree_node* result;
966
967 if(node == NULL)
968 return NULL;
969
970 result=node->right;
971 while(result) {
972 if(tree->compare_fn(range, result->data) == 0) {
973 return result;
974 } else {
975 result = result->right;
976 }
977 }
978
979 return node;
980 }
981
982
983 /* Follow left children until a match for range is found (range required) */
984 static raptor_avltree_node*
raptor_avltree_node_search_left(raptor_avltree * tree,raptor_avltree_node * node,void * range)985 raptor_avltree_node_search_left(raptor_avltree* tree,
986 raptor_avltree_node* node, void* range)
987 {
988 raptor_avltree_node* result;
989
990 if(node == NULL)
991 return NULL;
992
993 result=node->left;
994 while(result) {
995 if(tree->compare_fn(range, result->data) == 0) {
996 return result;
997 } else {
998 result = result->left;
999 }
1000 }
1001
1002 return node;
1003 }
1004
1005
1006 static raptor_avltree_node*
raptor_avltree_node_prev(raptor_avltree * tree,raptor_avltree_node * node,void * range)1007 raptor_avltree_node_prev(raptor_avltree* tree, raptor_avltree_node* node,
1008 void* range)
1009 {
1010 int up=0;
1011
1012 /*assert(!range || tree->compare_fn(range, node->data) == 0);*/
1013
1014 if(node->left) {
1015 /* Should never go left if the current node is already < range */
1016 raptor_avltree_node* prev;
1017 prev=raptor_avltree_node_rightmost(tree, node->left, NULL);
1018 /*assert(!range ||tree->compare_fn(range, node->data) <= 0);*/
1019 if(range) {
1020 if(tree->compare_fn(range, prev->data) == 0) {
1021 up = 0;
1022 node = prev;
1023 } else {
1024 up = 1;
1025 }
1026 } else {
1027 node = prev;
1028 up = 0;
1029 }
1030 } else {
1031 up = 1;
1032 }
1033
1034 if(up) {
1035 raptor_avltree_node* last=node;
1036 /* Need to go up */
1037 node=node->parent;
1038 while(node) {
1039
1040 /* moving from right subtree to this node */
1041 if(node->right && last == node->right) {
1042 break;
1043 }
1044
1045 /* moved up to find an unvisited left subtree */
1046 if(node->left && last != node->left) {
1047 /* Should never go left if the current node is already > range */
1048 /*assert(!range ||tree->compare_fn(range, node->data) <= 0);*/
1049 node=raptor_avltree_node_rightmost(tree, node->left, range);
1050 break;
1051 }
1052 last=node;
1053 node=node->parent;
1054 }
1055 }
1056
1057 if (node && range) {
1058 if (tree->compare_fn(range, node->data) == 0)
1059 return node;
1060 else
1061 return NULL;
1062 } else {
1063 return node;
1064 }
1065 }
1066
1067
1068 /* Follow right children until a match for range is found (if range not NULL) */
1069 static raptor_avltree_node*
raptor_avltree_node_next(raptor_avltree * tree,raptor_avltree_node * node,void * range)1070 raptor_avltree_node_next(raptor_avltree* tree, raptor_avltree_node* node,
1071 void* range)
1072 {
1073 int up=0;
1074
1075 /*assert(!range || tree->compare_fn(range, node->data) == 0);*/
1076
1077 if(node->right) {
1078 /* Should never go right if the current node is already > range */
1079 raptor_avltree_node* next;
1080 next=raptor_avltree_node_leftmost(tree, node->right, NULL);
1081 /*assert(!range ||tree->compare_fn(range, node->data) <= 0);*/
1082 if(range) {
1083 if(tree->compare_fn(range, next->data) == 0) {
1084 up = 0;
1085 node = next;
1086 } else {
1087 up = 1;
1088 }
1089 } else {
1090 node = next;
1091 up = 0;
1092 }
1093 } else {
1094 up = 1;
1095 }
1096
1097 if(up) {
1098 raptor_avltree_node* last=node;
1099 /* Need to go up */
1100 node=node->parent;
1101 while(node) {
1102
1103 /* moving from left subtree to this node */
1104 if(node->left && last == node->left) {
1105 break;
1106 }
1107
1108 /* moved up to find an unvisited right subtree */
1109 if(node->right && last != node->right) {
1110 /* Should never go right if the current node is already > range */
1111 /*assert(!range ||tree->compare_fn(range, node->data) <= 0);*/
1112 node=raptor_avltree_node_leftmost(tree, node->right, range);
1113 break;
1114 }
1115 last=node;
1116 node=node->parent;
1117 }
1118 }
1119
1120 if (node && range) {
1121 if (tree->compare_fn(range, node->data) == 0)
1122 return node;
1123 else
1124 return NULL;
1125 } else {
1126 return node;
1127 }
1128 }
1129
1130
1131 struct raptor_avltree_iterator_s {
1132 raptor_avltree* tree;
1133 raptor_avltree_node* root;
1134 raptor_avltree_node* current;
1135 void* range;
1136 raptor_data_free_function range_free_fn;
1137 int direction;
1138 int is_finished;
1139 };
1140
1141
1142 /*
1143 * raptor_new_avltree_iterator:
1144 * @tree: #raptor_avltree object
1145 * @range: range
1146 * @range_free_fn: function to free @range object
1147 * @direction: <0 to go 'backwards' otherwise 'forwards'
1148 *
1149 * INTERNAL - Get an in-order iterator for the start of a range, or the entire contents
1150 *
1151 * If range is NULL, the entire tree is walked in order. If range
1152 * specifies a range (i.e. the tree comparison function will 'match'
1153 * (return 0 for) range and /several/ nodes), the iterator will be
1154 * placed at the leftmost child matching range, and
1155 * raptor_avltree_iterator_next will iterate over all nodes (and only
1156 * nodes) that match range.
1157 *
1158 * Return value: a new #raptor_avltree_iterator object or NULL on failure
1159 **/
1160 raptor_avltree_iterator*
raptor_new_avltree_iterator(raptor_avltree * tree,void * range,raptor_data_free_function range_free_fn,int direction)1161 raptor_new_avltree_iterator(raptor_avltree* tree, void* range,
1162 raptor_data_free_function range_free_fn,
1163 int direction)
1164 {
1165 raptor_avltree_iterator* iterator;
1166
1167 iterator=(raptor_avltree_iterator*)RAPTOR_CALLOC(raptor_avltree_iterator,
1168 1, sizeof(raptor_avltree_iterator));
1169 if(!iterator)
1170 return NULL;
1171
1172 iterator->is_finished=0;
1173 iterator->current=NULL;
1174
1175 iterator->tree = tree;
1176 iterator->range = range;
1177 iterator->range_free_fn = range_free_fn;
1178 iterator->direction = direction;
1179
1180 if(range) {
1181 /* find the topmost match (range is contained entirely in tree
1182 * rooted here)
1183 */
1184 iterator->current=raptor_avltree_search_internal(tree, tree->root, range);
1185 } else {
1186 iterator->current=tree->root;
1187 }
1188
1189 iterator->root = iterator->current;
1190
1191 if(iterator->current) {
1192 if(iterator->direction < 0) {
1193 /* go down to find END of range (or tree) */
1194 while (1) {
1195 raptor_avltree_node* pred;
1196 iterator->current=raptor_avltree_node_rightmost(tree, iterator->current,
1197 range);
1198 /* move left until a match is found */
1199 pred=raptor_avltree_node_search_left(tree, iterator->current->right,
1200 range);
1201
1202 if(pred && tree->compare_fn(range, pred->data) == 0)
1203 iterator->current = pred;
1204 else
1205 break;
1206 }
1207 } else {
1208 /* go down to find START of range (or tree) */
1209 while (1) {
1210 raptor_avltree_node* pred;
1211 iterator->current=raptor_avltree_node_leftmost(tree, iterator->current,
1212 range);
1213 /* move right until a match is found */
1214 pred=raptor_avltree_node_search_right(tree, iterator->current->left,
1215 range);
1216
1217 if(pred && tree->compare_fn(range, pred->data) == 0)
1218 iterator->current = pred;
1219 else
1220 break;
1221 }
1222 }
1223 }
1224
1225 return iterator;
1226 }
1227
1228
1229 /*
1230 * raptor_free_avltree_iterator:
1231 * @iterator: AVL Tree iterator object
1232 *
1233 * INTERNAL - AVL Tree Iterator destructor
1234 */
1235 void
raptor_free_avltree_iterator(raptor_avltree_iterator * iterator)1236 raptor_free_avltree_iterator(raptor_avltree_iterator* iterator)
1237 {
1238 if(!iterator)
1239 return;
1240
1241 if(iterator->range && iterator->range_free_fn)
1242 iterator->range_free_fn(iterator->range);
1243
1244 RAPTOR_FREE(raptor_avltree_iterator, iterator);
1245 }
1246
1247
1248 /*
1249 * raptor_avltree_iterator_end:
1250 * @iterator: AVL Tree iterator object
1251 *
1252 * INTERNAL - test if an iteration is finished
1253 *
1254 * Return value: non-0 if iteration is finished
1255 */
1256 int
raptor_avltree_iterator_end(raptor_avltree_iterator * iterator)1257 raptor_avltree_iterator_end(raptor_avltree_iterator* iterator)
1258 {
1259 raptor_avltree_node *node=iterator->current;
1260
1261 if(iterator->is_finished)
1262 return 1;
1263 iterator->is_finished=(node == NULL);
1264
1265 return iterator->is_finished;
1266 }
1267
1268
1269 /*
1270 * raptor_avltree_iterator_next:
1271 * @iterator: AVL Tree iterator object
1272 *
1273 * INTERNAL - move iteration to next/prev object
1274 *
1275 * Return value: non-0 if iteration is finished
1276 */
1277 int
raptor_avltree_iterator_next(raptor_avltree_iterator * iterator)1278 raptor_avltree_iterator_next(raptor_avltree_iterator* iterator)
1279 {
1280 raptor_avltree_node *node=iterator->current;
1281
1282 if(!node || iterator->is_finished)
1283 return 1;
1284
1285 if(iterator->direction < 0)
1286 iterator->current=raptor_avltree_node_prev(iterator->tree, node,
1287 iterator->range);
1288 else
1289 iterator->current=raptor_avltree_node_next(iterator->tree, node,
1290 iterator->range);
1291 /* Stay within rooted subtree */
1292 if (iterator->root->parent == iterator->current)
1293 iterator->current = NULL;
1294
1295 iterator->is_finished=(iterator->current == NULL);
1296
1297 return iterator->is_finished;
1298 }
1299
1300
1301 /*
1302 * raptor_avltree_iterator_get:
1303 * @iterator: AVL Tree iterator object
1304 *
1305 * INTERNAL - get current iteration object
1306 *
1307 * Return value: object or NULL if iteration is finished
1308 */
1309 void*
raptor_avltree_iterator_get(raptor_avltree_iterator * iterator)1310 raptor_avltree_iterator_get(raptor_avltree_iterator* iterator)
1311 {
1312 raptor_avltree_node *node=iterator->current;
1313
1314 if(iterator->is_finished)
1315 return NULL;
1316
1317 iterator->is_finished=(node == NULL);
1318 if(iterator->is_finished)
1319 return NULL;
1320
1321 return node->data;
1322 }
1323
1324
1325 /* move the tree cursor to the first item by order */
1326 int
raptor_avltree_cursor_first(raptor_avltree * tree)1327 raptor_avltree_cursor_first(raptor_avltree* tree)
1328 {
1329 if(tree->cursor_iterator) {
1330 raptor_free_avltree_iterator(tree->cursor_iterator);
1331 tree->cursor_iterator=NULL;
1332 }
1333
1334 if(!tree->size)
1335 return 1;
1336
1337 tree->cursor_iterator=raptor_new_avltree_iterator(tree, NULL, NULL, 1);
1338 return (tree->cursor_iterator == NULL);
1339 }
1340
1341
1342 /* move the tree cursor to the last item by order */
1343 int
raptor_avltree_cursor_last(raptor_avltree * tree)1344 raptor_avltree_cursor_last(raptor_avltree* tree)
1345 {
1346 if(tree->cursor_iterator) {
1347 raptor_free_avltree_iterator(tree->cursor_iterator);
1348 tree->cursor_iterator=NULL;
1349 }
1350
1351 if(!tree->size)
1352 return 1;
1353
1354 tree->cursor_iterator=raptor_new_avltree_iterator(tree, NULL, NULL, -1);
1355 return (tree->cursor_iterator == NULL);
1356 }
1357
1358
1359 /* move the tree cursor to the previous item by order */
1360 int
raptor_avltree_cursor_prev(raptor_avltree * tree)1361 raptor_avltree_cursor_prev(raptor_avltree* tree)
1362 {
1363 int rc;
1364 if(!tree->cursor_iterator)
1365 rc=raptor_avltree_cursor_last(tree);
1366 else
1367 rc=raptor_avltree_iterator_next(tree->cursor_iterator);
1368 return rc;
1369 }
1370
1371
1372 /* move the tree cursor to the next item by order */
1373 int
raptor_avltree_cursor_next(raptor_avltree * tree)1374 raptor_avltree_cursor_next(raptor_avltree* tree)
1375 {
1376 int rc;
1377 if(!tree->cursor_iterator)
1378 rc=raptor_avltree_cursor_first(tree);
1379 else
1380 rc=raptor_avltree_iterator_next(tree->cursor_iterator);
1381 return rc;
1382 }
1383
1384
1385 /* get the item at the tree cursor (or NULL if no cursor was set) */
1386 void*
raptor_avltree_cursor_get(raptor_avltree * tree)1387 raptor_avltree_cursor_get(raptor_avltree* tree)
1388 {
1389 if(tree->cursor_iterator)
1390 return raptor_avltree_iterator_get(tree->cursor_iterator);
1391 return NULL;
1392 }
1393
1394
1395 /* print the items in the tree in order (for debugging) */
1396 void
raptor_avltree_print(raptor_avltree * tree,FILE * stream)1397 raptor_avltree_print(raptor_avltree* tree, FILE* stream)
1398 {
1399 int i;
1400 int rv=0;
1401 raptor_avltree_iterator* iter;
1402
1403 fprintf(stream, "AVL Tree size %u\n", tree->size);
1404 for(i=0, (iter=raptor_new_avltree_iterator(tree, NULL, NULL, 1));
1405 iter && !rv;
1406 i++, (rv=raptor_avltree_iterator_next(iter))) {
1407 const void* data=raptor_avltree_iterator_get(iter);
1408 if(!data)
1409 continue;
1410 fprintf(stream, "%d) ", i);
1411 if(tree->print_fn)
1412 tree->print_fn(stream, data);
1413 else
1414 fprintf(stream, "Data Node %p\n", data);
1415 }
1416 /*assert(i == tree->size);*/
1417 }
1418
1419
1420 #ifdef RAPTOR_DEBUG
1421
1422 static int
raptor_avltree_dump_internal(raptor_avltree * tree,raptor_avltree_node * node,int depth,FILE * stream)1423 raptor_avltree_dump_internal(raptor_avltree* tree, raptor_avltree_node* node,
1424 int depth, FILE* stream)
1425 {
1426 int i;
1427 if(!node)
1428 return TRUE;
1429
1430 for(i=0; i < depth; i++)
1431 fputs(" ", stream);
1432 fprintf(stream, "Node %p: parent %p left %p right %p data %p\n",
1433 node, node->parent, node->left, node->right, node->data);
1434 if(tree->print_fn) {
1435 for(i= 0; i < depth; i++)
1436 fputs(" ", stream);
1437 tree->print_fn(stream, node->data);
1438 }
1439
1440 if(!raptor_avltree_dump_internal(tree, node->left, depth+1, stream))
1441 return FALSE;
1442
1443 if(!raptor_avltree_dump_internal(tree, node->right, depth+1, stream))
1444 return FALSE;
1445
1446 return TRUE;
1447 }
1448
1449
1450 /* debugging tree dump with pointers and depth indenting */
1451 int
raptor_avltree_dump(raptor_avltree * tree,FILE * stream)1452 raptor_avltree_dump(raptor_avltree* tree, FILE* stream)
1453 {
1454 fprintf(stream, "Dumping avltree %p size %u\n", tree, tree->size);
1455 return raptor_avltree_dump_internal(tree, tree->root, 0, stream);
1456 }
1457
1458
1459 static void
raptor_avltree_check_internal(raptor_avltree * tree,raptor_avltree_node * node,unsigned int * count_p)1460 raptor_avltree_check_internal(raptor_avltree* tree, raptor_avltree_node* node,
1461 unsigned int* count_p)
1462 {
1463 if(!node)
1464 return;
1465 (*count_p)++;
1466
1467 raptor_avltree_check_node(tree, node, NULL, NULL);
1468
1469 raptor_avltree_check_internal(tree, node->left, count_p);
1470
1471 raptor_avltree_check_internal(tree, node->right, count_p);
1472 }
1473
1474
1475 /* debugging tree check - parent/child pointers and counts */
1476 void
raptor_avltree_check(raptor_avltree * tree)1477 raptor_avltree_check(raptor_avltree* tree)
1478 {
1479 unsigned int count=0;
1480
1481 raptor_avltree_check_internal(tree, tree->root, &count);
1482 if(count != tree->size) {
1483 fprintf(stderr, "Tree %p nodes count is %u. actual count %d\n",
1484 tree, tree->size, count);
1485 abort();
1486 }
1487 }
1488
1489 #endif
1490
1491 #endif
1492
1493
1494 #ifdef STANDALONE
1495
1496 #include <string.h>
1497
1498 typedef struct
1499 {
1500 FILE *fh;
1501 int count;
1502 const char** results;
1503 int failed;
1504 } visit_state;
1505
1506 #if RAPTOR_DEBUG > 1
1507 static int
print_string(int depth,void * data,void * user_data)1508 print_string(int depth, void* data, void *user_data)
1509 {
1510 visit_state* vs=(visit_state*)user_data;
1511
1512 fprintf(vs->fh, "%3d: %s\n", vs->count, (char*) data);
1513 vs->count++;
1514 return 1;
1515 }
1516 #endif
1517
1518 static int
check_string(int depth,void * data,void * user_data)1519 check_string(int depth, void* data, void *user_data)
1520 {
1521 visit_state* vs=(visit_state*)user_data;
1522 const char* result=vs->results[vs->count];
1523
1524 if(strcmp((const char*)data, result)) {
1525 fprintf(vs->fh, "%3d: Expected '%s' but found '%s'\n", vs->count,
1526 result, (char*)data);
1527 vs->failed=1;
1528 }
1529 vs->count++;
1530
1531 return 1;
1532 }
1533
1534 static int
compare_strings(const void * l,const void * r)1535 compare_strings(const void *l, const void *r)
1536 {
1537 return strcmp((const char*)l, (const char*)r);
1538 }
1539
1540
1541 /* one more prototype */
1542 int main(int argc, char *argv[]);
1543
1544 int
main(int argc,char * argv[])1545 main(int argc, char *argv[])
1546 {
1547 raptor_world *world;
1548 const char *program=raptor_basename(argv[0]);
1549 #define ITEM_COUNT 8
1550 const char *items[ITEM_COUNT+1] = { "ron", "amy", "jen", "bij", "jib", "daj", "jim", "def", NULL };
1551 #define DELETE_COUNT 2
1552 const char *delete_items[DELETE_COUNT+1] = { "jen", "jim", NULL };
1553 #define RESULT_COUNT (ITEM_COUNT-DELETE_COUNT)
1554 const char *results[RESULT_COUNT+1] = { "amy", "bij", "daj", "def", "jib", "ron", NULL};
1555
1556 raptor_avltree* tree;
1557 raptor_avltree_iterator* iter;
1558 visit_state vs;
1559 int i;
1560
1561 world = raptor_new_world();
1562 if(!world || raptor_world_open(world))
1563 exit(1);
1564
1565 tree=raptor_new_avltree(world,
1566 compare_strings,
1567 NULL, /* no free as they are static pointers above */
1568 0);
1569 if(!tree) {
1570 fprintf(stderr, "%s: Failed to create tree\n", program);
1571 exit(1);
1572 }
1573 for(i=0; items[i]; i++) {
1574 int rc;
1575 void* node;
1576
1577 #if RAPTOR_DEBUG > 1
1578 fprintf(stderr, "%s: Adding tree item '%s'\n", program, items[i]);
1579 #endif
1580
1581 rc=raptor_avltree_add(tree, (void*)items[i]);
1582 if(rc) {
1583 fprintf(stderr,
1584 "%s: Adding tree item %d '%s' failed, returning error %d\n",
1585 program, i, items[i], rc);
1586 exit(1);
1587 }
1588
1589 #ifdef RAPTOR_DEBUG
1590 raptor_avltree_check(tree);
1591 #endif
1592
1593 node=raptor_avltree_search(tree, (void*)items[i]);
1594 if(!node) {
1595 fprintf(stderr,
1596 "%s: Tree did NOT contain item %d '%s' as expected\n",
1597 program, i, items[i]);
1598 exit(1);
1599 }
1600 }
1601
1602 #if RAPTOR_DEBUG > 1
1603 fprintf(stderr, "%s: Printing tree\n", program);
1604 vs.fh=stderr;
1605 vs.count=0;
1606 raptor_avltree_visit(tree, print_string, &vs);
1607
1608 fprintf(stderr, "%s: Dumping tree\n", program);
1609 raptor_avltree_dump(tree, stderr);
1610 #endif
1611
1612
1613
1614 for(i=0; delete_items[i]; i++) {
1615 int rc;
1616
1617 #if RAPTOR_DEBUG > 1
1618 fprintf(stderr, "%s: Deleting tree item '%s'\n", program, delete_items[i]);
1619 #endif
1620
1621 rc=raptor_avltree_delete(tree, (void*)delete_items[i]);
1622 if(!rc) {
1623 fprintf(stderr,
1624 "%s: Deleting tree item %d '%s' failed, returning error %d\n",
1625 program, i, delete_items[i], rc);
1626 exit(1);
1627 }
1628
1629 #ifdef RAPTOR_DEBUG
1630 raptor_avltree_check(tree);
1631 #endif
1632 }
1633
1634
1635 #if RAPTOR_DEBUG > 1
1636 fprintf(stderr, "%s: Walking tree forwards via iterator\n", program);
1637 #endif
1638 iter=raptor_new_avltree_iterator(tree, NULL, NULL, 1);
1639 for(i=0; 1; i++) {
1640 const char* data=(const char*)raptor_avltree_iterator_get(iter);
1641 const char* result=results[i];
1642 if((!data && data != result) || (data && strcmp(data, result))) {
1643 fprintf(stderr, "%3d: Forwards iterator expected '%s' but found '%s'\n",
1644 i, result, data);
1645 exit(1);
1646 }
1647 #if RAPTOR_DEBUG > 1
1648 fprintf(stderr, "%3d: Got '%s'\n", i, data);
1649 #endif
1650 if(raptor_avltree_iterator_next(iter))
1651 break;
1652 if(i > RESULT_COUNT) {
1653 fprintf(stderr, "Forward iterator did not end on result %i as expected\n", i);
1654 exit(1);
1655 }
1656 }
1657 raptor_free_avltree_iterator(iter);
1658
1659
1660 #if RAPTOR_DEBUG > 1
1661 fprintf(stderr, "%s: Walking tree backwards via cursor\n", program);
1662 #endif
1663 raptor_avltree_cursor_last(tree);
1664 for(i=RESULT_COUNT-1; 1; i--) {
1665 const char* data=(const char*)raptor_avltree_cursor_get(tree);
1666 const char* result=results[i];
1667 if((!data && data != result) || (data && strcmp(data, result))) {
1668 fprintf(stderr, "%3d: Backwards cursoring expected '%s' but found '%s'\n",
1669 i, result, data);
1670 exit(1);
1671 }
1672 #if RAPTOR_DEBUG > 1
1673 fprintf(stderr, "%3d: Got '%s'\n", i, data);
1674 #endif
1675 if(raptor_avltree_cursor_prev(tree))
1676 break;
1677 if(i < 0) {
1678 fprintf(stderr, "Backwards cursor did not end on result %i as expected\n", i);
1679 exit(1);
1680 }
1681 }
1682
1683
1684 #if RAPTOR_DEBUG > 1
1685 fprintf(stderr, "%s: Checking tree\n", program);
1686 #endif
1687 vs.count=0;
1688 vs.results=results;
1689 vs.failed=0;
1690 raptor_avltree_visit(tree, check_string, &vs);
1691 if(vs.failed) {
1692 fprintf(stderr, "%s: Checking tree failed\n", program);
1693 exit(1);
1694 }
1695
1696
1697 for(i=0; results[i]; i++) {
1698 const char* result=results[i];
1699 char* data=(char*)raptor_avltree_remove(tree, (void*)result);
1700 if(!data) {
1701 fprintf(stderr, "%s: remove %i failed at item '%s'\n", program, i,
1702 result);
1703 exit(1);
1704 }
1705 if(strcmp(data, result)) {
1706 fprintf(stderr, "%s: remove %i returned %s not %s as expected\n", program,
1707 i, data, result);
1708 exit(1);
1709 }
1710 }
1711
1712
1713 #if RAPTOR_DEBUG > 1
1714 fprintf(stderr, "%s: Freeing tree\n", program);
1715 #endif
1716 raptor_free_avltree(tree);
1717
1718 raptor_free_world(world);
1719
1720 /* keep gcc -Wall happy */
1721 return(0);
1722 }
1723
1724 #endif
1725