Drizzled Public API Documentation

ut0rbt.cc
1 /***************************************************************************/
24 /********************************************************************/
32 #include "ut0rbt.h"
33 
34 /**********************************************************************/
53 #if defined(IB_RBT_TESTING)
54 #warning "Testing enabled!"
55 #endif
56 
57 #define ROOT(t) (t->root->left)
58 #define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1)
59 
60 /**********************************************************************/
62 static
63 void
64 rbt_print_subtree(
65 /*==============*/
66  const ib_rbt_t* tree,
67  const ib_rbt_node_t* node,
68  ib_rbt_print_node print)
69 {
70  /* FIXME: Doesn't do anything yet */
71  if (node != tree->nil) {
72  print(node);
73  rbt_print_subtree(tree, node->left, print);
74  rbt_print_subtree(tree, node->right, print);
75  }
76 }
77 
78 /**********************************************************************/
81 static
82 ibool
83 rbt_check_ordering(
84 /*===============*/
85  const ib_rbt_t* tree)
86 {
87  const ib_rbt_node_t* node;
88  const ib_rbt_node_t* prev = NULL;
89 
90  /* Iterate over all the nodes, comparing each node with the prev */
91  for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) {
92 
93  if (prev && tree->compare(prev->value, node->value) >= 0) {
94  return(FALSE);
95  }
96 
97  prev = node;
98  }
99 
100  return(TRUE);
101 }
102 
103 /**********************************************************************/
107 static
108 ibool
109 rbt_count_black_nodes(
110 /*==================*/
111  const ib_rbt_t* tree,
112  const ib_rbt_node_t* node)
113 {
114  ulint result;
115 
116  if (node != tree->nil) {
117  ulint left_height = rbt_count_black_nodes(tree, node->left);
118 
119  ulint right_height = rbt_count_black_nodes(tree, node->right);
120 
121  if (left_height == 0
122  || right_height == 0
123  || left_height != right_height) {
124 
125  result = 0;
126  } else if (node->color == IB_RBT_RED) {
127 
128  /* Case 3 */
129  if (node->left->color != IB_RBT_BLACK
130  || node->right->color != IB_RBT_BLACK) {
131 
132  result = 0;
133  } else {
134  result = left_height;
135  }
136  /* Check if it's anything other than RED or BLACK. */
137  } else if (node->color != IB_RBT_BLACK) {
138 
139  result = 0;
140  } else {
141 
142  result = right_height + 1;
143  }
144  } else {
145  result = 1;
146  }
147 
148  return(result);
149 }
150 
151 /**********************************************************************/
154 static
155 void
156 rbt_rotate_left(
157 /*============*/
158  const ib_rbt_node_t* nil,
159  ib_rbt_node_t* node)
160 {
161  ib_rbt_node_t* right = node->right;
162 
163  node->right = right->left;
164 
165  if (right->left != nil) {
166  right->left->parent = node;
167  }
168 
169  /* Right's new parent was node's parent. */
170  right->parent = node->parent;
171 
172  /* Since root's parent is tree->nil and root->parent->left points
173  back to root, we can avoid the check. */
174  if (node == node->parent->left) {
175  /* Node was on the left of its parent. */
176  node->parent->left = right;
177  } else {
178  /* Node must have been on the right. */
179  node->parent->right = right;
180  }
181 
182  /* Finally, put node on right's left. */
183  right->left = node;
184  node->parent = right;
185 }
186 
187 /**********************************************************************/
190 static
191 void
192 rbt_rotate_right(
193 /*=============*/
194  const ib_rbt_node_t* nil,
195  ib_rbt_node_t* node)
196 {
197  ib_rbt_node_t* left = node->left;
198 
199  node->left = left->right;
200 
201  if (left->right != nil) {
202  left->right->parent = node;
203  }
204 
205  /* Left's new parent was node's parent. */
206  left->parent = node->parent;
207 
208  /* Since root's parent is tree->nil and root->parent->left points
209  back to root, we can avoid the check. */
210  if (node == node->parent->right) {
211  /* Node was on the left of its parent. */
212  node->parent->right = left;
213  } else {
214  /* Node must have been on the left. */
215  node->parent->left = left;
216  }
217 
218  /* Finally, put node on left's right. */
219  left->right = node;
220  node->parent = left;
221 }
222 
223 /**********************************************************************/
225 static
227 rbt_tree_add_child(
228 /*===============*/
229  const ib_rbt_t* tree,
230  ib_rbt_bound_t* parent,
231  ib_rbt_node_t* node)
232 {
233  /* Cast away the const. */
234  ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last;
235 
236  if (last == tree->root || parent->result < 0) {
237  last->left = node;
238  } else {
239  /* FIXME: We don't handle duplicates (yet)! */
240  ut_a(parent->result != 0);
241 
242  last->right = node;
243  }
244 
245  node->parent = last;
246 
247  return(node);
248 }
249 
250 /**********************************************************************/
252 static
254 rbt_tree_insert(
255 /*============*/
256  ib_rbt_t* tree,
257  const void* key,
258  ib_rbt_node_t* node)
259 {
260  ib_rbt_bound_t parent;
261  ib_rbt_node_t* current = ROOT(tree);
262 
263  parent.result = 0;
264  parent.last = tree->root;
265 
266  /* Regular binary search. */
267  while (current != tree->nil) {
268 
269  parent.last = current;
270  parent.result = tree->compare(key, current->value);
271 
272  if (parent.result < 0) {
273  current = current->left;
274  } else {
275  current = current->right;
276  }
277  }
278 
279  ut_a(current == tree->nil);
280 
281  rbt_tree_add_child(tree, &parent, node);
282 
283  return(node);
284 }
285 
286 /**********************************************************************/
288 static
289 void
290 rbt_balance_tree(
291 /*=============*/
292  const ib_rbt_t* tree,
293  ib_rbt_node_t* node)
294 {
295  const ib_rbt_node_t* nil = tree->nil;
296  ib_rbt_node_t* parent = node->parent;
297 
298  /* Restore the red-black property. */
299  node->color = IB_RBT_RED;
300 
301  while (node != ROOT(tree) && parent->color == IB_RBT_RED) {
302  ib_rbt_node_t* grand_parent = parent->parent;
303 
304  if (parent == grand_parent->left) {
305  ib_rbt_node_t* uncle = grand_parent->right;
306 
307  if (uncle->color == IB_RBT_RED) {
308 
309  /* Case 1 - change the colors. */
310  uncle->color = IB_RBT_BLACK;
311  parent->color = IB_RBT_BLACK;
312  grand_parent->color = IB_RBT_RED;
313 
314  /* Move node up the tree. */
315  node = grand_parent;
316 
317  } else {
318 
319  if (node == parent->right) {
320  /* Right is a black node and node is
321  to the right, case 2 - move node
322  up and rotate. */
323  node = parent;
324  rbt_rotate_left(nil, node);
325  }
326 
327  grand_parent = node->parent->parent;
328 
329  /* Case 3. */
330  node->parent->color = IB_RBT_BLACK;
331  grand_parent->color = IB_RBT_RED;
332 
333  rbt_rotate_right(nil, grand_parent);
334  }
335 
336  } else {
337  ib_rbt_node_t* uncle = grand_parent->left;
338 
339  if (uncle->color == IB_RBT_RED) {
340 
341  /* Case 1 - change the colors. */
342  uncle->color = IB_RBT_BLACK;
343  parent->color = IB_RBT_BLACK;
344  grand_parent->color = IB_RBT_RED;
345 
346  /* Move node up the tree. */
347  node = grand_parent;
348 
349  } else {
350 
351  if (node == parent->left) {
352  /* Left is a black node and node is to
353  the right, case 2 - move node up and
354  rotate. */
355  node = parent;
356  rbt_rotate_right(nil, node);
357  }
358 
359  grand_parent = node->parent->parent;
360 
361  /* Case 3. */
362  node->parent->color = IB_RBT_BLACK;
363  grand_parent->color = IB_RBT_RED;
364 
365  rbt_rotate_left(nil, grand_parent);
366  }
367  }
368 
369  parent = node->parent;
370  }
371 
372  /* Color the root black. */
373  ROOT(tree)->color = IB_RBT_BLACK;
374 }
375 
376 /**********************************************************************/
379 static
381 rbt_find_successor(
382 /*===============*/
383  const ib_rbt_t* tree,
384  const ib_rbt_node_t* current)
387 {
388  const ib_rbt_node_t* nil = tree->nil;
389  ib_rbt_node_t* next = current->right;
390 
391  /* Is there a sub-tree to the right that we can follow. */
392  if (next != nil) {
393 
394  /* Follow the left most links of the current right child. */
395  while (next->left != nil) {
396  next = next->left;
397  }
398 
399  } else { /* We will have to go up the tree to find the successor. */
400  ib_rbt_node_t* parent = current->parent;
401 
402  /* Cast away the const. */
403  next = (ib_rbt_node_t*) current;
404 
405  while (parent != tree->root && next == parent->right) {
406  next = parent;
407  parent = next->parent;
408  }
409 
410  next = (parent == tree->root) ? NULL : parent;
411  }
412 
413  return(next);
414 }
415 
416 /**********************************************************************/
419 static
421 rbt_find_predecessor(
422 /*=================*/
423  const ib_rbt_t* tree,
424  const ib_rbt_node_t* current)
427 {
428  const ib_rbt_node_t* nil = tree->nil;
429  ib_rbt_node_t* prev = current->left;
430 
431  /* Is there a sub-tree to the left that we can follow. */
432  if (prev != nil) {
433 
434  /* Follow the right most links of the current left child. */
435  while (prev->right != nil) {
436  prev = prev->right;
437  }
438 
439  } else { /* We will have to go up the tree to find the precedecessor. */
440  ib_rbt_node_t* parent = current->parent;
441 
442  /* Cast away the const. */
443  prev = (ib_rbt_node_t*)current;
444 
445  while (parent != tree->root && prev == parent->left) {
446  prev = parent;
447  parent = prev->parent;
448  }
449 
450  prev = (parent == tree->root) ? NULL : parent;
451  }
452 
453  return(prev);
454 }
455 
456 /**********************************************************************/
459 static
460 void
461 rbt_eject_node(
462 /*===========*/
463  ib_rbt_node_t* eject,
464  ib_rbt_node_t* node)
465 {
466  /* Update the to be ejected node's parent's child pointers. */
467  if (eject->parent->left == eject) {
468  eject->parent->left = node;
469  } else if (eject->parent->right == eject) {
470  eject->parent->right = node;
471  } else {
472  ut_a(0);
473  }
474  /* eject is now an orphan but otherwise its pointers
475  and color are left intact. */
476 
477  node->parent = eject->parent;
478 }
479 
480 /**********************************************************************/
482 static
483 void
484 rbt_replace_node(
485 /*=============*/
486  ib_rbt_node_t* replace,
487  ib_rbt_node_t* node)
488 {
489  ib_rbt_color_t color = node->color;
490 
491  /* Update the node pointers. */
492  node->left = replace->left;
493  node->right = replace->right;
494 
495  /* Update the child node pointers. */
496  node->left->parent = node;
497  node->right->parent = node;
498 
499  /* Make the parent of replace point to node. */
500  rbt_eject_node(replace, node);
501 
502  /* Swap the colors. */
503  node->color = replace->color;
504  replace->color = color;
505 }
506 
507 /**********************************************************************/
510 static
512 rbt_detach_node(
513 /*============*/
514  const ib_rbt_t* tree,
515  ib_rbt_node_t* node)
516 {
517  ib_rbt_node_t* child;
518  const ib_rbt_node_t* nil = tree->nil;
519 
520  if (node->left != nil && node->right != nil) {
521  /* Case where the node to be deleted has two children. */
522  ib_rbt_node_t* successor = rbt_find_successor(tree, node);
523 
524  ut_a(successor != nil);
525  ut_a(successor->parent != nil);
526  ut_a(successor->left == nil);
527 
528  child = successor->right;
529 
530  /* Remove the successor node and replace with its child. */
531  rbt_eject_node(successor, child);
532 
533  /* Replace the node to delete with its successor node. */
534  rbt_replace_node(node, successor);
535  } else {
536  ut_a(node->left == nil || node->right == nil);
537 
538  child = (node->left != nil) ? node->left : node->right;
539 
540  /* Replace the node to delete with one of it's children. */
541  rbt_eject_node(node, child);
542  }
543 
544  /* Reset the node links. */
545  node->parent = node->right = node->left = tree->nil;
546 
547  return(child);
548 }
549 
550 /**********************************************************************/
553 static
555 rbt_balance_right(
556 /*==============*/
557  const ib_rbt_node_t* nil,
558  ib_rbt_node_t* parent,
559  ib_rbt_node_t* sibling)
560 {
561  ib_rbt_node_t* node = NULL;
562 
563  ut_a(sibling != nil);
564 
565  /* Case 3. */
566  if (sibling->color == IB_RBT_RED) {
567 
568  parent->color = IB_RBT_RED;
569  sibling->color = IB_RBT_BLACK;
570 
571  rbt_rotate_left(nil, parent);
572 
573  sibling = parent->right;
574 
575  ut_a(sibling != nil);
576  }
577 
578  /* Since this will violate case 3 because of the change above. */
579  if (sibling->left->color == IB_RBT_BLACK
580  && sibling->right->color == IB_RBT_BLACK) {
581 
582  node = parent; /* Parent needs to be rebalanced too. */
583  sibling->color = IB_RBT_RED;
584 
585  } else {
586  if (sibling->right->color == IB_RBT_BLACK) {
587 
588  ut_a(sibling->left->color == IB_RBT_RED);
589 
590  sibling->color = IB_RBT_RED;
591  sibling->left->color = IB_RBT_BLACK;
592 
593  rbt_rotate_right(nil, sibling);
594 
595  sibling = parent->right;
596  ut_a(sibling != nil);
597  }
598 
599  sibling->color = parent->color;
600  sibling->right->color = IB_RBT_BLACK;
601 
602  parent->color = IB_RBT_BLACK;
603 
604  rbt_rotate_left(nil, parent);
605  }
606 
607  return(node);
608 }
609 
610 /**********************************************************************/
613 static
615 rbt_balance_left(
616 /*=============*/
617  const ib_rbt_node_t* nil,
618  ib_rbt_node_t* parent,
619  ib_rbt_node_t* sibling)
620 {
621  ib_rbt_node_t* node = NULL;
622 
623  ut_a(sibling != nil);
624 
625  /* Case 3. */
626  if (sibling->color == IB_RBT_RED) {
627 
628  parent->color = IB_RBT_RED;
629  sibling->color = IB_RBT_BLACK;
630 
631  rbt_rotate_right(nil, parent);
632  sibling = parent->left;
633 
634  ut_a(sibling != nil);
635  }
636 
637  /* Since this will violate case 3 because of the change above. */
638  if (sibling->right->color == IB_RBT_BLACK
639  && sibling->left->color == IB_RBT_BLACK) {
640 
641  node = parent; /* Parent needs to be rebalanced too. */
642  sibling->color = IB_RBT_RED;
643 
644  } else {
645  if (sibling->left->color == IB_RBT_BLACK) {
646 
647  ut_a(sibling->right->color == IB_RBT_RED);
648 
649  sibling->color = IB_RBT_RED;
650  sibling->right->color = IB_RBT_BLACK;
651 
652  rbt_rotate_left(nil, sibling);
653 
654  sibling = parent->left;
655 
656  ut_a(sibling != nil);
657  }
658 
659  sibling->color = parent->color;
660  sibling->left->color = IB_RBT_BLACK;
661 
662  parent->color = IB_RBT_BLACK;
663 
664  rbt_rotate_right(nil, parent);
665  }
666 
667  return(node);
668 }
669 
670 /**********************************************************************/
672 static
673 void
674 rbt_remove_node_and_rebalance(
675 /*==========================*/
676  ib_rbt_t* tree,
677  ib_rbt_node_t* node)
678 {
679  /* Detach node and get the node that will be used
680  as rebalance start. */
681  ib_rbt_node_t* child = rbt_detach_node(tree, node);
682 
683  if (node->color == IB_RBT_BLACK) {
684  ib_rbt_node_t* last = child;
685 
686  ROOT(tree)->color = IB_RBT_RED;
687 
688  while (child && child->color == IB_RBT_BLACK) {
689  ib_rbt_node_t* parent = child->parent;
690 
691  /* Did the deletion cause an imbalance in the
692  parents left sub-tree. */
693  if (parent->left == child) {
694 
695  child = rbt_balance_right(
696  tree->nil, parent, parent->right);
697 
698  } else if (parent->right == child) {
699 
700  child = rbt_balance_left(
701  tree->nil, parent, parent->left);
702 
703  } else {
704  ut_error;
705  }
706 
707  if (child) {
708  last = child;
709  }
710  }
711 
712  ut_a(last);
713 
714  last->color = IB_RBT_BLACK;
715  ROOT(tree)->color = IB_RBT_BLACK;
716  }
717 
718  /* Note that we have removed a node from the tree. */
719  --tree->n_nodes;
720 }
721 
722 /**********************************************************************/
724 static
725 void
726 rbt_free_node(
727 /*==========*/
728  ib_rbt_node_t* node,
729  ib_rbt_node_t* nil)
730 {
731  if (node != nil) {
732  rbt_free_node(node->left, nil);
733  rbt_free_node(node->right, nil);
734 
735  ut_free(node);
736  }
737 }
738 
739 /**********************************************************************/
741 UNIV_INTERN
742 void
744 /*=====*/
745  ib_rbt_t* tree)
746 {
747  rbt_free_node(tree->root, tree->nil);
748  ut_free(tree->nil);
749  ut_free(tree);
750 }
751 
752 /**********************************************************************/
755 UNIV_INTERN
756 ib_rbt_t*
758 /*=======*/
759  size_t sizeof_value,
760  ib_rbt_compare compare)
761 {
762  ib_rbt_t* tree;
763  ib_rbt_node_t* node;
764 
765  tree = (ib_rbt_t*) ut_malloc(sizeof(*tree));
766  memset(tree, 0, sizeof(*tree));
767 
768  tree->sizeof_value = sizeof_value;
769 
770  /* Create the sentinel (NIL) node. */
771  node = tree->nil = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
772  memset(node, 0, sizeof(*node));
773 
774  node->color = IB_RBT_BLACK;
775  node->parent = node->left = node->right = node;
776 
777  /* Create the "fake" root, the real root node will be the
778  left child of this node. */
779  node = tree->root = (ib_rbt_node_t*) ut_malloc(sizeof(*node));
780  memset(node, 0, sizeof(*node));
781 
782  node->color = IB_RBT_BLACK;
783  node->parent = node->left = node->right = tree->nil;
784 
785  tree->compare = compare;
786 
787  return(tree);
788 }
789 
790 /**********************************************************************/
793 UNIV_INTERN
794 const ib_rbt_node_t*
796 /*=======*/
797  ib_rbt_t* tree,
798  const void* key,
799  const void* value)
801 {
802  ib_rbt_node_t* node;
803 
804  /* Create the node that will hold the value data. */
805  node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
806 
807  memcpy(node->value, value, tree->sizeof_value);
808  node->parent = node->left = node->right = tree->nil;
809 
810  /* Insert in the tree in the usual way. */
811  rbt_tree_insert(tree, key, node);
812  rbt_balance_tree(tree, node);
813 
814  ++tree->n_nodes;
815 
816  return(node);
817 }
818 
819 /**********************************************************************/
822 UNIV_INTERN
823 const ib_rbt_node_t*
825 /*=========*/
826  ib_rbt_t* tree,
827  ib_rbt_bound_t* parent,
828  const void* value)
830 {
831  ib_rbt_node_t* node;
832 
833  /* Create the node that will hold the value data */
834  node = (ib_rbt_node_t*) ut_malloc(SIZEOF_NODE(tree));
835 
836  memcpy(node->value, value, tree->sizeof_value);
837  node->parent = node->left = node->right = tree->nil;
838 
839  /* If tree is empty */
840  if (parent->last == NULL) {
841  parent->last = tree->root;
842  }
843 
844  /* Append the node, the hope here is that the caller knows
845  what s/he is doing. */
846  rbt_tree_add_child(tree, parent, node);
847  rbt_balance_tree(tree, node);
848 
849  ++tree->n_nodes;
850 
851 #if defined(IB_RBT_TESTING)
852  ut_a(rbt_validate(tree));
853 #endif
854  return(node);
855 }
856 
857 /**********************************************************************/
860 UNIV_INTERN
861 const ib_rbt_node_t*
863 /*=======*/
864  const ib_rbt_t* tree,
865  const void* key)
866 {
867  const ib_rbt_node_t* current = ROOT(tree);
868 
869  /* Regular binary search. */
870  while (current != tree->nil) {
871  int result = tree->compare(key, current->value);
872 
873  if (result < 0) {
874  current = current->left;
875  } else if (result > 0) {
876  current = current->right;
877  } else {
878  break;
879  }
880  }
881 
882  return(current != tree->nil ? current : NULL);
883 }
884 
885 /**********************************************************************/
888 UNIV_INTERN
889 ibool
891 /*=======*/
892  ib_rbt_t* tree,
893  const void* key)
894 {
895  ibool deleted = FALSE;
896  ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key);
897 
898  if (node) {
899  rbt_remove_node_and_rebalance(tree, node);
900 
901  ut_free(node);
902  deleted = TRUE;
903  }
904 
905  return(deleted);
906 }
907 
908 /**********************************************************************/
912 UNIV_INTERN
915 /*============*/
916  ib_rbt_t* tree,
917  const ib_rbt_node_t* const_node)
921 {
922  /* Cast away the const. */
923  rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node);
924 
925  /* This is to make it easier to do something like this:
926  ut_free(rbt_remove_node(node));
927  */
928 
929  return((ib_rbt_node_t*) const_node);
930 }
931 
932 /**********************************************************************/
935 UNIV_INTERN
936 const ib_rbt_node_t*
938 /*============*/
939  const ib_rbt_t* tree,
940  const void* key)
941 {
942  ib_rbt_node_t* lb_node = NULL;
943  ib_rbt_node_t* current = ROOT(tree);
944 
945  while (current != tree->nil) {
946  int result = tree->compare(key, current->value);
947 
948  if (result > 0) {
949 
950  current = current->right;
951 
952  } else if (result < 0) {
953 
954  lb_node = current;
955  current = current->left;
956 
957  } else {
958  lb_node = current;
959  break;
960  }
961  }
962 
963  return(lb_node);
964 }
965 
966 /**********************************************************************/
969 UNIV_INTERN
970 const ib_rbt_node_t*
972 /*============*/
973  const ib_rbt_t* tree,
974  const void* key)
975 {
976  ib_rbt_node_t* ub_node = NULL;
977  ib_rbt_node_t* current = ROOT(tree);
978 
979  while (current != tree->nil) {
980  int result = tree->compare(key, current->value);
981 
982  if (result > 0) {
983 
984  ub_node = current;
985  current = current->right;
986 
987  } else if (result < 0) {
988 
989  current = current->left;
990 
991  } else {
992  ub_node = current;
993  break;
994  }
995  }
996 
997  return(ub_node);
998 }
999 
1000 /**********************************************************************/
1003 UNIV_INTERN
1004 int
1006 /*=======*/
1007  const ib_rbt_t* tree,
1008  ib_rbt_bound_t* parent,
1009  const void* key)
1010 {
1011  ib_rbt_node_t* current = ROOT(tree);
1012 
1013  /* Every thing is greater than the NULL root. */
1014  parent->result = 1;
1015  parent->last = NULL;
1016 
1017  while (current != tree->nil) {
1018 
1019  parent->last = current;
1020  parent->result = tree->compare(key, current->value);
1021 
1022  if (parent->result > 0) {
1023  current = current->right;
1024  } else if (parent->result < 0) {
1025  current = current->left;
1026  } else {
1027  break;
1028  }
1029  }
1030 
1031  return(parent->result);
1032 }
1033 
1034 /**********************************************************************/
1038 UNIV_INTERN
1039 int
1041 /*===========*/
1042  const ib_rbt_t* tree,
1043  ib_rbt_bound_t* parent,
1044  const void* key,
1045  ib_rbt_compare compare)
1046 {
1047  ib_rbt_node_t* current = ROOT(tree);
1048 
1049  /* Every thing is greater than the NULL root. */
1050  parent->result = 1;
1051  parent->last = NULL;
1052 
1053  while (current != tree->nil) {
1054 
1055  parent->last = current;
1056  parent->result = compare(key, current->value);
1057 
1058  if (parent->result > 0) {
1059  current = current->right;
1060  } else if (parent->result < 0) {
1061  current = current->left;
1062  } else {
1063  break;
1064  }
1065  }
1066 
1067  return(parent->result);
1068 }
1069 
1070 /**********************************************************************/
1072 UNIV_INTERN
1073 const ib_rbt_node_t*
1075 /*======*/
1076  /* out leftmost node or NULL */
1077  const ib_rbt_t* tree) /* in: rb tree */
1078 {
1079  ib_rbt_node_t* first = NULL;
1080  ib_rbt_node_t* current = ROOT(tree);
1081 
1082  while (current != tree->nil) {
1083  first = current;
1084  current = current->left;
1085  }
1086 
1087  return(first);
1088 }
1089 
1090 /**********************************************************************/
1093 UNIV_INTERN
1094 const ib_rbt_node_t*
1096 /*=====*/
1097  const ib_rbt_t* tree)
1098 {
1099  ib_rbt_node_t* last = NULL;
1100  ib_rbt_node_t* current = ROOT(tree);
1101 
1102  while (current != tree->nil) {
1103  last = current;
1104  current = current->right;
1105  }
1106 
1107  return(last);
1108 }
1109 
1110 /**********************************************************************/
1113 UNIV_INTERN
1114 const ib_rbt_node_t*
1116 /*=====*/
1117  const ib_rbt_t* tree,
1118  const ib_rbt_node_t* current)
1119 {
1120  return(current ? rbt_find_successor(tree, current) : NULL);
1121 }
1122 
1123 /**********************************************************************/
1126 UNIV_INTERN
1127 const ib_rbt_node_t*
1129 /*=====*/
1130  const ib_rbt_t* tree,
1131  const ib_rbt_node_t* current)
1132 {
1133  return(current ? rbt_find_predecessor(tree, current) : NULL);
1134 }
1135 
1136 /**********************************************************************/
1138 UNIV_INTERN
1139 void
1141 /*======*/
1142  ib_rbt_t* tree)
1143 {
1144  rbt_free_node(ROOT(tree), tree->nil);
1145 
1146  tree->n_nodes = 0;
1147  tree->root->left = tree->root->right = tree->nil;
1148 }
1149 
1150 /**********************************************************************/
1153 UNIV_INTERN
1154 ulint
1156 /*===========*/
1157  ib_rbt_t* dst,
1158  const ib_rbt_t* src)
1159 {
1160  ib_rbt_bound_t parent;
1161  ulint n_merged = 0;
1162  const ib_rbt_node_t* src_node = rbt_first(src);
1163 
1164  if (rbt_empty(src) || dst == src) {
1165  return(0);
1166  }
1167 
1168  for (/* No op */; src_node; src_node = rbt_next(src, src_node)) {
1169 
1170  if (rbt_search(dst, &parent, src_node->value) != 0) {
1171  rbt_add_node(dst, &parent, src_node->value);
1172  ++n_merged;
1173  }
1174  }
1175 
1176  return(n_merged);
1177 }
1178 
1179 /**********************************************************************/
1184 UNIV_INTERN
1185 ulint
1187 /*=======================*/
1188  ib_rbt_t* dst,
1189  ib_rbt_t* src)
1190 {
1191  ib_rbt_bound_t parent;
1192  ib_rbt_node_t* src_node;
1193  ulint old_size = rbt_size(dst);
1194 
1195  if (rbt_empty(src) || dst == src) {
1196  return(0);
1197  }
1198 
1199  for (src_node = (ib_rbt_node_t*) rbt_first(src); src_node; /* */) {
1200  ib_rbt_node_t* prev = src_node;
1201 
1202  src_node = (ib_rbt_node_t*)rbt_next(src, prev);
1203 
1204  /* Skip duplicates. */
1205  if (rbt_search(dst, &parent, prev->value) != 0) {
1206 
1207  /* Remove and reset the node but preserve
1208  the node (data) value. */
1209  rbt_remove_node_and_rebalance(src, prev);
1210 
1211  /* The nil should be taken from the dst tree. */
1212  prev->parent = prev->left = prev->right = dst->nil;
1213  rbt_tree_add_child(dst, &parent, prev);
1214  rbt_balance_tree(dst, prev);
1215 
1216  ++dst->n_nodes;
1217  }
1218  }
1219 
1220 #if defined(IB_RBT_TESTING)
1221  ut_a(rbt_validate(dst));
1222  ut_a(rbt_validate(src));
1223 #endif
1224  return(rbt_size(dst) - old_size);
1225 }
1226 
1227 /**********************************************************************/
1231 UNIV_INTERN
1232 ibool
1234 /*=========*/
1235  const ib_rbt_t* tree)
1236 {
1237  if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) {
1238  return(rbt_check_ordering(tree));
1239  }
1240 
1241  return(FALSE);
1242 }
1243 
1244 /**********************************************************************/
1246 UNIV_INTERN
1247 void
1249 /*======*/
1250  const ib_rbt_t* tree,
1251  ib_rbt_print_node print)
1252 {
1253  rbt_print_subtree(tree, ROOT(tree), print);
1254 }
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
Definition: ut0rbt.cc:1140
UNIV_INTERN const ib_rbt_node_t * rbt_prev(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition: ut0rbt.cc:1128
UNIV_INTERN const ib_rbt_node_t * rbt_lower_bound(const ib_rbt_t *tree, const void *key)
Definition: ut0rbt.cc:937
UNIV_INTERN const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
Definition: ut0rbt.cc:1095
UNIV_INTERN void * ut_malloc(ulint n)
Definition: ut0mem.cc:235
UNIV_INTERN int rbt_search_cmp(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare)
Definition: ut0rbt.cc:1040
UNIV_INTERN const ib_rbt_node_t * rbt_lookup(const ib_rbt_t *tree, const void *key)
Definition: ut0rbt.cc:862
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, ib_rbt_print_node print)
Definition: ut0rbt.cc:1248
#define ut_a(EXPR)
Definition: ut0dbg.h:105
UNIV_INTERN ib_rbt_node_t * rbt_remove_node(ib_rbt_t *tree, const ib_rbt_node_t *node)
Definition: ut0rbt.cc:914
UNIV_INTERN ibool rbt_delete(ib_rbt_t *tree, const void *key)
Definition: ut0rbt.cc:890
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
Definition: ut0rbt.cc:757
UNIV_INTERN ibool rbt_validate(const ib_rbt_t *tree)
Definition: ut0rbt.cc:1233
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
Definition: ut0rbt.cc:1186
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
Definition: ut0rbt.cc:1155
UNIV_INTERN const ib_rbt_node_t * rbt_insert(ib_rbt_t *tree, const void *key, const void *value)
Definition: ut0rbt.cc:795
UNIV_INTERN const ib_rbt_node_t * rbt_add_node(ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
Definition: ut0rbt.cc:824
UNIV_INTERN const ib_rbt_node_t * rbt_upper_bound(const ib_rbt_t *tree, const void *key)
Definition: ut0rbt.cc:971
UNIV_INTERN int rbt_search(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
Definition: ut0rbt.cc:1005
UNIV_INTERN void ut_free(void *ptr)
Definition: ut0mem.cc:294
#define ut_error
Definition: ut0dbg.h:115
UNIV_INTERN const ib_rbt_node_t * rbt_first(const ib_rbt_t *tree)
Definition: ut0rbt.cc:1074
UNIV_INTERN const ib_rbt_node_t * rbt_next(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition: ut0rbt.cc:1115
UNIV_INTERN void rbt_free(ib_rbt_t *tree)
Definition: ut0rbt.cc:743