1/* Copyright (c) 2000, 2016, Oracle and/or its affiliates.
2 Copyright (c) 2010, 2016, MariaDB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17/*
18 Code for handling red-black (balanced) binary trees.
19 key in tree is allocated accrding to following:
20
21 1) If size < 0 then tree will not allocate keys and only a pointer to
22 each key is saved in tree.
23 compare and search functions uses and returns key-pointer
24
25 2) If size == 0 then there are two options:
26 - key_size != 0 to tree_insert: The key will be stored in the tree.
27 - key_size == 0 to tree_insert: A pointer to the key is stored.
28 compare and search functions uses and returns key-pointer.
29
30 3) if key_size is given to init_tree then each node will continue the
31 key and calls to insert_key may increase length of key.
32 if key_size > sizeof(pointer) and key_size is a multiple of 8 (double
33 align) then key will be put on a 8 aligned address. Else
34 the key will be on address (element+1). This is transparent for user
35 compare and search functions uses a pointer to given key-argument.
36
37 - If you use a free function for tree-elements and you are freeing
38 the element itself, you should use key_size = 0 to init_tree and
39 tree_search
40
41 The actual key in TREE_ELEMENT is saved as a pointer or after the
42 TREE_ELEMENT struct.
43 If one uses only pointers in tree one can use tree_set_pointer() to
44 change address of data.
45
46 Implemented by monty.
47*/
48
49/*
50 NOTE:
51 tree->compare function should be ALWAYS called as
52 (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
53 and not other way around, as
54 (*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
55
56 ft_boolean_search.c (at least) relies on that.
57*/
58
59#include "mysys_priv.h"
60#include <m_string.h>
61#include <my_tree.h>
62#include "my_base.h"
63
64#define BLACK 1
65#define RED 0
66#define DEFAULT_ALLOC_SIZE 8192
67#define DEFAULT_ALIGN_SIZE 8192
68
69static int delete_tree_element(TREE *,TREE_ELEMENT *, my_bool abort);
70static int tree_walk_left_root_right(TREE *,TREE_ELEMENT *,
71 tree_walk_action,void *);
72static int tree_walk_right_root_left(TREE *,TREE_ELEMENT *,
73 tree_walk_action,void *);
74static void left_rotate(TREE_ELEMENT **parent,TREE_ELEMENT *leaf);
75static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf);
76static void rb_insert(TREE *tree,TREE_ELEMENT ***parent,
77 TREE_ELEMENT *leaf);
78static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
79
80
81/* The actual code for handling binary trees */
82
83#ifndef DBUG_OFF
84static int test_rb_tree(TREE_ELEMENT *element);
85#endif
86
87void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
88 int size, qsort_cmp2 compare,
89 tree_element_free free_element, void *custom_arg,
90 myf my_flags)
91{
92 DBUG_ENTER("init_tree");
93 DBUG_PRINT("enter",("tree: %p size: %d", tree, size));
94
95 if (default_alloc_size < DEFAULT_ALLOC_SIZE)
96 default_alloc_size= DEFAULT_ALLOC_SIZE;
97 default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
98 bzero((uchar*) &tree->null_element,sizeof(tree->null_element));
99 tree->root= &tree->null_element;
100 tree->compare=compare;
101 tree->size_of_element= size > 0 ? (uint) size : 0;
102 tree->memory_limit=memory_limit;
103 tree->free=free_element;
104 tree->allocated=0;
105 tree->elements_in_tree=0;
106 tree->custom_arg = custom_arg;
107 tree->null_element.colour=BLACK;
108 tree->null_element.left=tree->null_element.right=0;
109 tree->my_flags= my_flags;
110 tree->flag= 0;
111 if (!free_element && size >= 0 &&
112 ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
113 {
114 /*
115 We know that the data doesn't have to be aligned (like if the key
116 contains a double), so we can store the data combined with the
117 TREE_ELEMENT.
118 */
119 tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
120 /* Fix allocation size so that we don't lose any memory */
121 default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
122 if (!default_alloc_size)
123 default_alloc_size=1;
124 default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
125 }
126 else
127 {
128 tree->offset_to_key=0; /* use key through pointer */
129 tree->size_of_element+=sizeof(void*);
130 }
131 if (!(tree->with_delete= MY_TEST(my_flags & MY_TREE_WITH_DELETE)))
132 {
133 init_alloc_root(&tree->mem_root, "tree", default_alloc_size, 0,
134 MYF(my_flags));
135 tree->mem_root.min_malloc= sizeof(TREE_ELEMENT)+tree->size_of_element;
136 }
137 DBUG_VOID_RETURN;
138}
139
140static int free_tree(TREE *tree, my_bool abort, myf free_flags)
141{
142 int error, first_error= 0;
143 DBUG_ENTER("free_tree");
144 DBUG_PRINT("enter",("tree: %p", tree));
145
146 if (tree->root) /* If initialized */
147 {
148 if (tree->with_delete)
149 {
150 if ((error= delete_tree_element(tree, tree->root, abort)))
151 {
152 first_error= first_error ? first_error : error;
153 abort= 1;
154 }
155 }
156 else
157 {
158 if (tree->free)
159 {
160 if (tree->memory_limit)
161 (*tree->free)(NULL, free_init, tree->custom_arg);
162 if ((error= delete_tree_element(tree, tree->root, abort)))
163 first_error= first_error ? first_error : error;
164 if (tree->memory_limit)
165 (*tree->free)(NULL, free_end, tree->custom_arg);
166 }
167 free_root(&tree->mem_root, free_flags);
168 }
169 }
170 tree->root= &tree->null_element;
171 tree->elements_in_tree=0;
172 tree->allocated=0;
173
174 DBUG_RETURN(first_error);
175}
176
177
178/**
179 Delete tree.
180
181 @param tree Tree
182 @param abort 0 if normal, 1 if tree->free should not be called.
183
184 @return 0 ok
185 <> 0 Returns first <> 0 from (tree->free)(*,free_free,*)
186
187 @Notes
188 If one (tree->free)(,free_free,) returns <> 0, no future
189 tree->free(*,free_free,*) will be called.
190 Other tree->free operations (free_init, free_end) will be called
191*/
192
193
194int delete_tree(TREE* tree, my_bool abort)
195{
196 return free_tree(tree, abort, MYF(0)); /* my_free() mem_root if applicable */
197}
198
199int reset_tree(TREE* tree)
200{
201 /* do not free mem_root, just mark blocks as free */
202 return free_tree(tree, 0, MYF(MY_MARK_BLOCKS_FREE));
203}
204
205
206static int delete_tree_element(TREE *tree, TREE_ELEMENT *element,
207 my_bool abort)
208{
209 int error, first_error= 0;
210 if (element != &tree->null_element)
211 {
212 if ((first_error= delete_tree_element(tree, element->left, abort)))
213 abort= 1;
214 if (!abort && tree->free)
215 {
216 if ((error= (*tree->free)(ELEMENT_KEY(tree,element), free_free,
217 tree->custom_arg)))
218 {
219 first_error= first_error ? first_error : error;
220 abort= 1;
221 }
222 }
223 if ((error= delete_tree_element(tree, element->right, abort)))
224 first_error= first_error ? first_error : error;
225 if (tree->with_delete)
226 my_free(element);
227 }
228 return first_error;
229}
230
231
232/*
233 insert, search and delete of elements
234
235 The following should be true:
236 parent[0] = & parent[-1][0]->left ||
237 parent[0] = & parent[-1][0]->right
238*/
239
240TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
241 void* custom_arg)
242{
243 int cmp;
244 TREE_ELEMENT *element,***parent;
245
246 parent= tree->parents;
247 *parent = &tree->root; element= tree->root;
248 for (;;)
249 {
250 if (element == &tree->null_element ||
251 (cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
252 key)) == 0)
253 break;
254 if (cmp < 0)
255 {
256 *++parent= &element->right; element= element->right;
257 }
258 else
259 {
260 *++parent = &element->left; element= element->left;
261 }
262 }
263 if (element == &tree->null_element)
264 {
265 uint alloc_size;
266 if (tree->flag & TREE_ONLY_DUPS)
267 return((TREE_ELEMENT *) 1);
268 alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
269 tree->allocated+=alloc_size;
270
271 if (tree->memory_limit && tree->elements_in_tree
272 && tree->allocated > tree->memory_limit)
273 {
274 reset_tree(tree);
275 return tree_insert(tree, key, key_size, custom_arg);
276 }
277
278 key_size+=tree->size_of_element;
279 if (tree->with_delete)
280 element=(TREE_ELEMENT *) my_malloc(alloc_size,
281 MYF(tree->my_flags | MY_WME));
282 else
283 element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
284 if (!element)
285 return(NULL);
286 **parent=element;
287 element->left=element->right= &tree->null_element;
288 if (!tree->offset_to_key)
289 {
290 if (key_size == sizeof(void*)) /* no length, save pointer */
291 *((void**) (element+1))=key;
292 else
293 {
294 *((void**) (element+1))= (void*) ((void **) (element+1)+1);
295 memcpy((uchar*) *((void **) (element+1)),key,
296 (size_t) (key_size-sizeof(void*)));
297 }
298 }
299 else
300 memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
301 element->count=1; /* May give warning in purify */
302 tree->elements_in_tree++;
303 rb_insert(tree,parent,element); /* rebalance tree */
304 }
305 else
306 {
307 if (tree->flag & TREE_NO_DUPS)
308 return(NULL);
309 element->count++;
310 /* Avoid a wrap over of the count. */
311 if (! element->count)
312 element->count--;
313 }
314 DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
315 return element;
316}
317
318int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
319{
320 int cmp,remove_colour;
321 TREE_ELEMENT *element,***parent, ***org_parent, *nod;
322 if (!tree->with_delete)
323 return 1; /* not allowed */
324
325 parent= tree->parents;
326 *parent= &tree->root; element= tree->root;
327 for (;;)
328 {
329 if (element == &tree->null_element)
330 return 1; /* Was not in tree */
331 if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
332 key)) == 0)
333 break;
334 if (cmp < 0)
335 {
336 *++parent= &element->right; element= element->right;
337 }
338 else
339 {
340 *++parent = &element->left; element= element->left;
341 }
342 }
343 if (element->left == &tree->null_element)
344 {
345 (**parent)=element->right;
346 remove_colour= element->colour;
347 }
348 else if (element->right == &tree->null_element)
349 {
350 (**parent)=element->left;
351 remove_colour= element->colour;
352 }
353 else
354 {
355 org_parent= parent;
356 *++parent= &element->right; nod= element->right;
357 while (nod->left != &tree->null_element)
358 {
359 *++parent= &nod->left; nod= nod->left;
360 }
361 (**parent)=nod->right; /* unlink nod from tree */
362 remove_colour= nod->colour;
363 org_parent[0][0]=nod; /* put y in place of element */
364 org_parent[1]= &nod->right;
365 nod->left=element->left;
366 nod->right=element->right;
367 nod->colour=element->colour;
368 }
369 if (remove_colour == BLACK)
370 rb_delete_fixup(tree,parent);
371 if (tree->free)
372 (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
373 tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
374 my_free(element);
375 tree->elements_in_tree--;
376 return 0;
377}
378
379
380void *tree_search(TREE *tree, void *key, void *custom_arg)
381{
382 int cmp;
383 TREE_ELEMENT *element=tree->root;
384
385 for (;;)
386 {
387 if (element == &tree->null_element)
388 return (void*) 0;
389 if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
390 key)) == 0)
391 return ELEMENT_KEY(tree,element);
392 if (cmp < 0)
393 element=element->right;
394 else
395 element=element->left;
396 }
397}
398
399void *tree_search_key(TREE *tree, const void *key,
400 TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
401 enum ha_rkey_function flag, void *custom_arg)
402{
403 int cmp;
404 TREE_ELEMENT *element= tree->root;
405 TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
406 TREE_ELEMENT **last_equal_element= NULL;
407
408/*
409 TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
410*/
411
412 *parents = &tree->null_element;
413 while (element != &tree->null_element)
414 {
415 *++parents= element;
416 if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
417 key)) == 0)
418 {
419 switch (flag) {
420 case HA_READ_KEY_EXACT:
421 case HA_READ_KEY_OR_NEXT:
422 case HA_READ_BEFORE_KEY:
423 case HA_READ_KEY_OR_PREV:
424 last_equal_element= parents;
425 cmp= 1;
426 break;
427 case HA_READ_AFTER_KEY:
428 cmp= -1;
429 break;
430 case HA_READ_PREFIX_LAST:
431 case HA_READ_PREFIX_LAST_OR_PREV:
432 last_equal_element= parents;
433 cmp= -1;
434 break;
435 default:
436 return NULL;
437 }
438 }
439 if (cmp < 0) /* element < key */
440 {
441 last_right_step_parent= parents;
442 element= element->right;
443 }
444 else
445 {
446 last_left_step_parent= parents;
447 element= element->left;
448 }
449 }
450 switch (flag) {
451 case HA_READ_KEY_EXACT:
452 case HA_READ_PREFIX_LAST:
453 *last_pos= last_equal_element;
454 break;
455 case HA_READ_KEY_OR_NEXT:
456 *last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
457 break;
458 case HA_READ_AFTER_KEY:
459 *last_pos= last_left_step_parent;
460 break;
461 case HA_READ_PREFIX_LAST_OR_PREV:
462 *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
463 break;
464 case HA_READ_BEFORE_KEY:
465 *last_pos= last_right_step_parent;
466 break;
467 case HA_READ_KEY_OR_PREV:
468 *last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
469 break;
470 default:
471 return NULL;
472 }
473 return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
474}
475
476/*
477 Search first (the most left) or last (the most right) tree element
478*/
479void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
480 TREE_ELEMENT ***last_pos, int child_offs)
481{
482 TREE_ELEMENT *element= tree->root;
483
484 *parents= &tree->null_element;
485 while (element != &tree->null_element)
486 {
487 *++parents= element;
488 element= ELEMENT_CHILD(element, child_offs);
489 }
490 *last_pos= parents;
491 return **last_pos != &tree->null_element ?
492 ELEMENT_KEY(tree, **last_pos) : NULL;
493}
494
495void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
496 int r_offs)
497{
498 TREE_ELEMENT *x= **last_pos;
499
500 if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
501 {
502 x= ELEMENT_CHILD(x, r_offs);
503 *++*last_pos= x;
504 while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
505 {
506 x= ELEMENT_CHILD(x, l_offs);
507 *++*last_pos= x;
508 }
509 return ELEMENT_KEY(tree, x);
510 }
511 else
512 {
513 TREE_ELEMENT *y= *--*last_pos;
514 while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
515 {
516 x= y;
517 y= *--*last_pos;
518 }
519 return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
520 }
521}
522
523/*
524 Expected that tree is fully balanced
525 (each path from root to leaf has the same length)
526*/
527ha_rows tree_record_pos(TREE *tree, const void *key,
528 enum ha_rkey_function flag, void *custom_arg)
529{
530 int cmp;
531 TREE_ELEMENT *element= tree->root;
532 double left= 1;
533 double right= tree->elements_in_tree;
534
535 while (element != &tree->null_element)
536 {
537 if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
538 key)) == 0)
539 {
540 switch (flag) {
541 case HA_READ_KEY_EXACT:
542 case HA_READ_BEFORE_KEY:
543 cmp= 1;
544 break;
545 case HA_READ_AFTER_KEY:
546 cmp= -1;
547 break;
548 default:
549 return HA_POS_ERROR;
550 }
551 }
552 if (cmp < 0) /* element < key */
553 {
554 element= element->right;
555 left= (left + right) / 2;
556 }
557 else
558 {
559 element= element->left;
560 right= (left + right) / 2;
561 }
562 }
563 switch (flag) {
564 case HA_READ_KEY_EXACT:
565 case HA_READ_BEFORE_KEY:
566 return (ha_rows) right;
567 case HA_READ_AFTER_KEY:
568 return (ha_rows) left;
569 default:
570 return HA_POS_ERROR;
571 }
572}
573
574int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
575{
576 switch (visit) {
577 case left_root_right:
578 return tree_walk_left_root_right(tree,tree->root,action,argument);
579 case right_root_left:
580 return tree_walk_right_root_left(tree,tree->root,action,argument);
581 }
582 return 0; /* Keep gcc happy */
583}
584
585static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
586{
587 int error;
588 if (element->left) /* Not null_element */
589 {
590 if ((error=tree_walk_left_root_right(tree,element->left,action,
591 argument)) == 0 &&
592 (error=(*action)(ELEMENT_KEY(tree,element),
593 (element_count) element->count,
594 argument)) == 0)
595 error=tree_walk_left_root_right(tree,element->right,action,argument);
596 return error;
597 }
598 return 0;
599}
600
601static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
602{
603 int error;
604 if (element->right) /* Not null_element */
605 {
606 if ((error=tree_walk_right_root_left(tree,element->right,action,
607 argument)) == 0 &&
608 (error=(*action)(ELEMENT_KEY(tree,element),
609 (element_count) element->count,
610 argument)) == 0)
611 error=tree_walk_right_root_left(tree,element->left,action,argument);
612 return error;
613 }
614 return 0;
615}
616
617
618 /* Functions to fix up the tree after insert and delete */
619
620static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
621{
622 TREE_ELEMENT *y;
623
624 y=leaf->right;
625 leaf->right=y->left;
626 parent[0]=y;
627 y->left=leaf;
628}
629
630static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
631{
632 TREE_ELEMENT *x;
633
634 x=leaf->left;
635 leaf->left=x->right;
636 parent[0]=x;
637 x->right=leaf;
638}
639
640static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
641{
642 TREE_ELEMENT *y,*par,*par2;
643
644 leaf->colour=RED;
645 while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
646 {
647 if (par == (par2=parent[-2][0])->left)
648 {
649 y= par2->right;
650 if (y->colour == RED)
651 {
652 par->colour=BLACK;
653 y->colour=BLACK;
654 leaf=par2;
655 parent-=2;
656 leaf->colour=RED; /* And the loop continues */
657 }
658 else
659 {
660 if (leaf == par->right)
661 {
662 left_rotate(parent[-1],par);
663 par=leaf; /* leaf is now parent to old leaf */
664 }
665 par->colour=BLACK;
666 par2->colour=RED;
667 right_rotate(parent[-2],par2);
668 break;
669 }
670 }
671 else
672 {
673 y= par2->left;
674 if (y->colour == RED)
675 {
676 par->colour=BLACK;
677 y->colour=BLACK;
678 leaf=par2;
679 parent-=2;
680 leaf->colour=RED; /* And the loop continues */
681 }
682 else
683 {
684 if (leaf == par->left)
685 {
686 right_rotate(parent[-1],par);
687 par=leaf;
688 }
689 par->colour=BLACK;
690 par2->colour=RED;
691 left_rotate(parent[-2],par2);
692 break;
693 }
694 }
695 }
696 tree->root->colour=BLACK;
697}
698
699static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
700{
701 TREE_ELEMENT *x,*w,*par;
702
703 x= **parent;
704 while (x != tree->root && x->colour == BLACK)
705 {
706 if (x == (par=parent[-1][0])->left)
707 {
708 w=par->right;
709 if (w->colour == RED)
710 {
711 w->colour=BLACK;
712 par->colour=RED;
713 left_rotate(parent[-1],par);
714 parent[0]= &w->left;
715 *++parent= &par->left;
716 w=par->right;
717 }
718 if (w->left->colour == BLACK && w->right->colour == BLACK)
719 {
720 w->colour=RED;
721 x=par;
722 parent--;
723 }
724 else
725 {
726 if (w->right->colour == BLACK)
727 {
728 w->left->colour=BLACK;
729 w->colour=RED;
730 right_rotate(&par->right,w);
731 w=par->right;
732 }
733 w->colour=par->colour;
734 par->colour=BLACK;
735 w->right->colour=BLACK;
736 left_rotate(parent[-1],par);
737 x=tree->root;
738 break;
739 }
740 }
741 else
742 {
743 w=par->left;
744 if (w->colour == RED)
745 {
746 w->colour=BLACK;
747 par->colour=RED;
748 right_rotate(parent[-1],par);
749 parent[0]= &w->right;
750 *++parent= &par->right;
751 w=par->left;
752 }
753 if (w->right->colour == BLACK && w->left->colour == BLACK)
754 {
755 w->colour=RED;
756 x=par;
757 parent--;
758 }
759 else
760 {
761 if (w->left->colour == BLACK)
762 {
763 w->right->colour=BLACK;
764 w->colour=RED;
765 left_rotate(&par->left,w);
766 w=par->left;
767 }
768 w->colour=par->colour;
769 par->colour=BLACK;
770 w->left->colour=BLACK;
771 right_rotate(parent[-1],par);
772 x=tree->root;
773 break;
774 }
775 }
776 }
777 x->colour=BLACK;
778}
779
780#ifndef DBUG_OFF
781
782 /* Test that the proporties for a red-black tree holds */
783
784static int test_rb_tree(TREE_ELEMENT *element)
785{
786 int count_l,count_r;
787
788 if (!element->left)
789 return 0; /* Found end of tree */
790 if (element->colour == RED &&
791 (element->left->colour == RED || element->right->colour == RED))
792 {
793 printf("Wrong tree: Found two red in a row\n");
794 return -1;
795 }
796 count_l=test_rb_tree(element->left);
797 count_r=test_rb_tree(element->right);
798 if (count_l >= 0 && count_r >= 0)
799 {
800 if (count_l == count_r)
801 return count_l+(element->colour == BLACK);
802 printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
803 }
804 return -1;
805}
806#endif
807