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