PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
rbtree.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * rbtree.c
4  * implementation for PostgreSQL generic Red-Black binary tree package
5  * Adopted from http://algolist.manual.ru/ds/rbtree.php
6  *
7  * This code comes from Thomas Niemann's "Sorting and Searching Algorithms:
8  * a Cookbook".
9  *
10  * See http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_man.htm for
11  * license terms: "Source code, when part of a software project, may be used
12  * freely without reference to the author."
13  *
14  * Red-black trees are a type of balanced binary tree wherein (1) any child of
15  * a red node is always black, and (2) every path from root to leaf traverses
16  * an equal number of black nodes. From these properties, it follows that the
17  * longest path from root to leaf is only about twice as long as the shortest,
18  * so lookups are guaranteed to run in O(lg n) time.
19  *
20  * Copyright (c) 2009-2017, PostgreSQL Global Development Group
21  *
22  * IDENTIFICATION
23  * src/backend/lib/rbtree.c
24  *
25  *-------------------------------------------------------------------------
26  */
27 #include "postgres.h"
28 
29 #include "lib/rbtree.h"
30 
31 
32 /*
33  * Colors of nodes (values of RBNode.color)
34  */
35 #define RBBLACK (0)
36 #define RBRED (1)
37 
38 /*
39  * RBTree control structure
40  */
41 struct RBTree
42 {
43  RBNode *root; /* root node, or RBNIL if tree is empty */
44 
45  /* Remaining fields are constant after rb_create */
46 
47  Size node_size; /* actual size of tree nodes */
48  /* The caller-supplied manipulation functions */
53  /* Passthrough arg passed to all manipulation functions */
54  void *arg;
55 };
56 
57 /*
58  * all leafs are sentinels, use customized NIL name to prevent
59  * collision with system-wide constant NIL which is actually NULL
60  */
61 #define RBNIL (&sentinel)
62 
64 
65 /*
66  * Values used in the RBTreeIterator.next_state field, with an
67  * InvertedWalk iterator.
68  */
70 {
76 
77 /*
78  * rb_create: create an empty RBTree
79  *
80  * Arguments are:
81  * node_size: actual size of tree nodes (> sizeof(RBNode))
82  * The manipulation functions:
83  * comparator: compare two RBNodes for less/equal/greater
84  * combiner: merge an existing tree entry with a new one
85  * allocfunc: allocate a new RBNode
86  * freefunc: free an old RBNode
87  * arg: passthrough pointer that will be passed to the manipulation functions
88  *
89  * Note that the combiner's righthand argument will be a "proposed" tree node,
90  * ie the input to rb_insert, in which the RBNode fields themselves aren't
91  * valid. Similarly, either input to the comparator may be a "proposed" node.
92  * This shouldn't matter since the functions aren't supposed to look at the
93  * RBNode fields, only the extra fields of the struct the RBNode is embedded
94  * in.
95  *
96  * The freefunc should just be pfree or equivalent; it should NOT attempt
97  * to free any subsidiary data, because the node passed to it may not contain
98  * valid data! freefunc can be NULL if caller doesn't require retail
99  * space reclamation.
100  *
101  * The RBTree node is palloc'd in the caller's memory context. Note that
102  * all contents of the tree are actually allocated by the caller, not here.
103  *
104  * Since tree contents are managed by the caller, there is currently not
105  * an explicit "destroy" operation; typically a tree would be freed by
106  * resetting or deleting the memory context it's stored in. You can pfree
107  * the RBTree node if you feel the urge.
108  */
109 RBTree *
110 rb_create(Size node_size,
111  rb_comparator comparator,
112  rb_combiner combiner,
113  rb_allocfunc allocfunc,
114  rb_freefunc freefunc,
115  void *arg)
116 {
117  RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
118 
119  Assert(node_size > sizeof(RBNode));
120 
121  tree->root = RBNIL;
122  tree->node_size = node_size;
123  tree->comparator = comparator;
124  tree->combiner = combiner;
125  tree->allocfunc = allocfunc;
126  tree->freefunc = freefunc;
127 
128  tree->arg = arg;
129 
130  return tree;
131 }
132 
133 /* Copy the additional data fields from one RBNode to another */
134 static inline void
135 rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
136 {
137  memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
138 }
139 
140 /**********************************************************************
141  * Search *
142  **********************************************************************/
143 
144 /*
145  * rb_find: search for a value in an RBTree
146  *
147  * data represents the value to try to find. Its RBNode fields need not
148  * be valid, it's the extra data in the larger struct that is of interest.
149  *
150  * Returns the matching tree entry, or NULL if no match is found.
151  */
152 RBNode *
153 rb_find(RBTree *rb, const RBNode *data)
154 {
155  RBNode *node = rb->root;
156 
157  while (node != RBNIL)
158  {
159  int cmp = rb->comparator(data, node, rb->arg);
160 
161  if (cmp == 0)
162  return node;
163  else if (cmp < 0)
164  node = node->left;
165  else
166  node = node->right;
167  }
168 
169  return NULL;
170 }
171 
172 /*
173  * rb_leftmost: fetch the leftmost (smallest-valued) tree node.
174  * Returns NULL if tree is empty.
175  *
176  * Note: in the original implementation this included an unlink step, but
177  * that's a bit awkward. Just call rb_delete on the result if that's what
178  * you want.
179  */
180 RBNode *
182 {
183  RBNode *node = rb->root;
184  RBNode *leftmost = rb->root;
185 
186  while (node != RBNIL)
187  {
188  leftmost = node;
189  node = node->left;
190  }
191 
192  if (leftmost != RBNIL)
193  return leftmost;
194 
195  return NULL;
196 }
197 
198 /**********************************************************************
199  * Insertion *
200  **********************************************************************/
201 
202 /*
203  * Rotate node x to left.
204  *
205  * x's right child takes its place in the tree, and x becomes the left
206  * child of that node.
207  */
208 static void
210 {
211  RBNode *y = x->right;
212 
213  /* establish x->right link */
214  x->right = y->left;
215  if (y->left != RBNIL)
216  y->left->parent = x;
217 
218  /* establish y->parent link */
219  if (y != RBNIL)
220  y->parent = x->parent;
221  if (x->parent)
222  {
223  if (x == x->parent->left)
224  x->parent->left = y;
225  else
226  x->parent->right = y;
227  }
228  else
229  {
230  rb->root = y;
231  }
232 
233  /* link x and y */
234  y->left = x;
235  if (x != RBNIL)
236  x->parent = y;
237 }
238 
239 /*
240  * Rotate node x to right.
241  *
242  * x's left right child takes its place in the tree, and x becomes the right
243  * child of that node.
244  */
245 static void
247 {
248  RBNode *y = x->left;
249 
250  /* establish x->left link */
251  x->left = y->right;
252  if (y->right != RBNIL)
253  y->right->parent = x;
254 
255  /* establish y->parent link */
256  if (y != RBNIL)
257  y->parent = x->parent;
258  if (x->parent)
259  {
260  if (x == x->parent->right)
261  x->parent->right = y;
262  else
263  x->parent->left = y;
264  }
265  else
266  {
267  rb->root = y;
268  }
269 
270  /* link x and y */
271  y->right = x;
272  if (x != RBNIL)
273  x->parent = y;
274 }
275 
276 /*
277  * Maintain Red-Black tree balance after inserting node x.
278  *
279  * The newly inserted node is always initially marked red. That may lead to
280  * a situation where a red node has a red child, which is prohibited. We can
281  * always fix the problem by a series of color changes and/or "rotations",
282  * which move the problem progressively higher up in the tree. If one of the
283  * two red nodes is the root, we can always fix the problem by changing the
284  * root from red to black.
285  *
286  * (This does not work lower down in the tree because we must also maintain
287  * the invariant that every leaf has equal black-height.)
288  */
289 static void
291 {
292  /*
293  * x is always a red node. Initially, it is the newly inserted node. Each
294  * iteration of this loop moves it higher up in the tree.
295  */
296  while (x != rb->root && x->parent->color == RBRED)
297  {
298  /*
299  * x and x->parent are both red. Fix depends on whether x->parent is
300  * a left or right child. In either case, we define y to be the
301  * "uncle" of x, that is, the other child of x's grandparent.
302  *
303  * If the uncle is red, we flip the grandparent to red and its two
304  * children to black. Then we loop around again to check whether the
305  * grandparent still has a problem.
306  *
307  * If the uncle is black, we will perform one or two "rotations" to
308  * balance the tree. Either x or x->parent will take the
309  * grandparent's position in the tree and recolored black, and the
310  * original grandparent will be recolored red and become a child of
311  * that node. This always leaves us with a valid red-black tree, so
312  * the loop will terminate.
313  */
314  if (x->parent == x->parent->parent->left)
315  {
316  RBNode *y = x->parent->parent->right;
317 
318  if (y->color == RBRED)
319  {
320  /* uncle is RBRED */
321  x->parent->color = RBBLACK;
322  y->color = RBBLACK;
323  x->parent->parent->color = RBRED;
324 
325  x = x->parent->parent;
326  }
327  else
328  {
329  /* uncle is RBBLACK */
330  if (x == x->parent->right)
331  {
332  /* make x a left child */
333  x = x->parent;
334  rb_rotate_left(rb, x);
335  }
336 
337  /* recolor and rotate */
338  x->parent->color = RBBLACK;
339  x->parent->parent->color = RBRED;
340 
341  rb_rotate_right(rb, x->parent->parent);
342  }
343  }
344  else
345  {
346  /* mirror image of above code */
347  RBNode *y = x->parent->parent->left;
348 
349  if (y->color == RBRED)
350  {
351  /* uncle is RBRED */
352  x->parent->color = RBBLACK;
353  y->color = RBBLACK;
354  x->parent->parent->color = RBRED;
355 
356  x = x->parent->parent;
357  }
358  else
359  {
360  /* uncle is RBBLACK */
361  if (x == x->parent->left)
362  {
363  x = x->parent;
364  rb_rotate_right(rb, x);
365  }
366  x->parent->color = RBBLACK;
367  x->parent->parent->color = RBRED;
368 
369  rb_rotate_left(rb, x->parent->parent);
370  }
371  }
372  }
373 
374  /*
375  * The root may already have been black; if not, the black-height of every
376  * node in the tree increases by one.
377  */
378  rb->root->color = RBBLACK;
379 }
380 
381 /*
382  * rb_insert: insert a new value into the tree.
383  *
384  * data represents the value to insert. Its RBNode fields need not
385  * be valid, it's the extra data in the larger struct that is of interest.
386  *
387  * If the value represented by "data" is not present in the tree, then
388  * we copy "data" into a new tree entry and return that node, setting *isNew
389  * to true.
390  *
391  * If the value represented by "data" is already present, then we call the
392  * combiner function to merge data into the existing node, and return the
393  * existing node, setting *isNew to false.
394  *
395  * "data" is unmodified in either case; it's typically just a local
396  * variable in the caller.
397  */
398 RBNode *
399 rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
400 {
401  RBNode *current,
402  *parent,
403  *x;
404  int cmp;
405 
406  /* find where node belongs */
407  current = rb->root;
408  parent = NULL;
409  cmp = 0; /* just to prevent compiler warning */
410 
411  while (current != RBNIL)
412  {
413  cmp = rb->comparator(data, current, rb->arg);
414  if (cmp == 0)
415  {
416  /*
417  * Found node with given key. Apply combiner.
418  */
419  rb->combiner(current, data, rb->arg);
420  *isNew = false;
421  return current;
422  }
423  parent = current;
424  current = (cmp < 0) ? current->left : current->right;
425  }
426 
427  /*
428  * Value is not present, so create a new node containing data.
429  */
430  *isNew = true;
431 
432  x = rb->allocfunc(rb->arg);
433 
434  x->color = RBRED;
435 
436  x->left = RBNIL;
437  x->right = RBNIL;
438  x->parent = parent;
439  rb_copy_data(rb, x, data);
440 
441  /* insert node in tree */
442  if (parent)
443  {
444  if (cmp < 0)
445  parent->left = x;
446  else
447  parent->right = x;
448  }
449  else
450  {
451  rb->root = x;
452  }
453 
454  rb_insert_fixup(rb, x);
455 
456  return x;
457 }
458 
459 /**********************************************************************
460  * Deletion *
461  **********************************************************************/
462 
463 /*
464  * Maintain Red-Black tree balance after deleting a black node.
465  */
466 static void
468 {
469  /*
470  * x is always a black node. Initially, it is the former child of the
471  * deleted node. Each iteration of this loop moves it higher up in the
472  * tree.
473  */
474  while (x != rb->root && x->color == RBBLACK)
475  {
476  /*
477  * Left and right cases are symmetric. Any nodes that are children of
478  * x have a black-height one less than the remainder of the nodes in
479  * the tree. We rotate and recolor nodes to move the problem up the
480  * tree: at some stage we'll either fix the problem, or reach the root
481  * (where the black-height is allowed to decrease).
482  */
483  if (x == x->parent->left)
484  {
485  RBNode *w = x->parent->right;
486 
487  if (w->color == RBRED)
488  {
489  w->color = RBBLACK;
490  x->parent->color = RBRED;
491 
492  rb_rotate_left(rb, x->parent);
493  w = x->parent->right;
494  }
495 
496  if (w->left->color == RBBLACK && w->right->color == RBBLACK)
497  {
498  w->color = RBRED;
499 
500  x = x->parent;
501  }
502  else
503  {
504  if (w->right->color == RBBLACK)
505  {
506  w->left->color = RBBLACK;
507  w->color = RBRED;
508 
509  rb_rotate_right(rb, w);
510  w = x->parent->right;
511  }
512  w->color = x->parent->color;
513  x->parent->color = RBBLACK;
514  w->right->color = RBBLACK;
515 
516  rb_rotate_left(rb, x->parent);
517  x = rb->root; /* Arrange for loop to terminate. */
518  }
519  }
520  else
521  {
522  RBNode *w = x->parent->left;
523 
524  if (w->color == RBRED)
525  {
526  w->color = RBBLACK;
527  x->parent->color = RBRED;
528 
529  rb_rotate_right(rb, x->parent);
530  w = x->parent->left;
531  }
532 
533  if (w->right->color == RBBLACK && w->left->color == RBBLACK)
534  {
535  w->color = RBRED;
536 
537  x = x->parent;
538  }
539  else
540  {
541  if (w->left->color == RBBLACK)
542  {
543  w->right->color = RBBLACK;
544  w->color = RBRED;
545 
546  rb_rotate_left(rb, w);
547  w = x->parent->left;
548  }
549  w->color = x->parent->color;
550  x->parent->color = RBBLACK;
551  w->left->color = RBBLACK;
552 
553  rb_rotate_right(rb, x->parent);
554  x = rb->root; /* Arrange for loop to terminate. */
555  }
556  }
557  }
558  x->color = RBBLACK;
559 }
560 
561 /*
562  * Delete node z from tree.
563  */
564 static void
566 {
567  RBNode *x,
568  *y;
569 
570  if (!z || z == RBNIL)
571  return;
572 
573  /*
574  * y is the node that will actually be removed from the tree. This will
575  * be z if z has fewer than two children, or the tree successor of z
576  * otherwise.
577  */
578  if (z->left == RBNIL || z->right == RBNIL)
579  {
580  /* y has a RBNIL node as a child */
581  y = z;
582  }
583  else
584  {
585  /* find tree successor */
586  y = z->right;
587  while (y->left != RBNIL)
588  y = y->left;
589  }
590 
591  /* x is y's only child */
592  if (y->left != RBNIL)
593  x = y->left;
594  else
595  x = y->right;
596 
597  /* Remove y from the tree. */
598  x->parent = y->parent;
599  if (y->parent)
600  {
601  if (y == y->parent->left)
602  y->parent->left = x;
603  else
604  y->parent->right = x;
605  }
606  else
607  {
608  rb->root = x;
609  }
610 
611  /*
612  * If we removed the tree successor of z rather than z itself, then move
613  * the data for the removed node to the one we were supposed to remove.
614  */
615  if (y != z)
616  rb_copy_data(rb, z, y);
617 
618  /*
619  * Removing a black node might make some paths from root to leaf contain
620  * fewer black nodes than others, or it might make two red nodes adjacent.
621  */
622  if (y->color == RBBLACK)
623  rb_delete_fixup(rb, x);
624 
625  /* Now we can recycle the y node */
626  if (rb->freefunc)
627  rb->freefunc(y, rb->arg);
628 }
629 
630 /*
631  * rb_delete: remove the given tree entry
632  *
633  * "node" must have previously been found via rb_find or rb_leftmost.
634  * It is caller's responsibility to free any subsidiary data attached
635  * to the node before calling rb_delete. (Do *not* try to push that
636  * responsibility off to the freefunc, as some other physical node
637  * may be the one actually freed!)
638  */
639 void
641 {
642  rb_delete_node(rb, node);
643 }
644 
645 /**********************************************************************
646  * Traverse *
647  **********************************************************************/
648 
649 static RBNode *
651 {
652  if (iter->last_visited == NULL)
653  {
654  iter->last_visited = iter->rb->root;
655  while (iter->last_visited->left != RBNIL)
656  iter->last_visited = iter->last_visited->left;
657 
658  return iter->last_visited;
659  }
660 
661  if (iter->last_visited->right != RBNIL)
662  {
663  iter->last_visited = iter->last_visited->right;
664  while (iter->last_visited->left != RBNIL)
665  iter->last_visited = iter->last_visited->left;
666 
667  return iter->last_visited;
668  }
669 
670  for (;;)
671  {
672  RBNode *came_from = iter->last_visited;
673 
674  iter->last_visited = iter->last_visited->parent;
675  if (iter->last_visited == NULL)
676  {
677  iter->is_over = true;
678  break;
679  }
680 
681  if (iter->last_visited->left == came_from)
682  break; /* came from left sub-tree, return current
683  * node */
684 
685  /* else - came from right sub-tree, continue to move up */
686  }
687 
688  return iter->last_visited;
689 }
690 
691 static RBNode *
693 {
694  if (iter->last_visited == NULL)
695  {
696  iter->last_visited = iter->rb->root;
697  while (iter->last_visited->right != RBNIL)
698  iter->last_visited = iter->last_visited->right;
699 
700  return iter->last_visited;
701  }
702 
703  if (iter->last_visited->left != RBNIL)
704  {
705  iter->last_visited = iter->last_visited->left;
706  while (iter->last_visited->right != RBNIL)
707  iter->last_visited = iter->last_visited->right;
708 
709  return iter->last_visited;
710  }
711 
712  for (;;)
713  {
714  RBNode *came_from = iter->last_visited;
715 
716  iter->last_visited = iter->last_visited->parent;
717  if (iter->last_visited == NULL)
718  {
719  iter->is_over = true;
720  break;
721  }
722 
723  if (iter->last_visited->right == came_from)
724  break; /* came from right sub-tree, return current
725  * node */
726 
727  /* else - came from left sub-tree, continue to move up */
728  }
729 
730  return iter->last_visited;
731 }
732 
733 static RBNode *
735 {
736  if (iter->last_visited == NULL)
737  {
738  iter->last_visited = iter->rb->root;
739  return iter->last_visited;
740  }
741 
742  if (iter->last_visited->left != RBNIL)
743  {
744  iter->last_visited = iter->last_visited->left;
745  return iter->last_visited;
746  }
747 
748  do
749  {
750  if (iter->last_visited->right != RBNIL)
751  {
752  iter->last_visited = iter->last_visited->right;
753  break;
754  }
755 
756  /* go up and one step right */
757  for (;;)
758  {
759  RBNode *came_from = iter->last_visited;
760 
761  iter->last_visited = iter->last_visited->parent;
762  if (iter->last_visited == NULL)
763  {
764  iter->is_over = true;
765  break;
766  }
767 
768  if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBNIL))
769  {
770  iter->last_visited = iter->last_visited->right;
771  return iter->last_visited;
772  }
773  }
774  }
775  while (iter->last_visited != NULL);
776 
777  return iter->last_visited;
778 }
779 
780 static RBNode *
782 {
783  RBNode *came_from;
784  RBNode *current;
785 
786  current = iter->last_visited;
787 
788 loop:
789  switch ((InvertedWalkNextStep) iter->next_step)
790  {
791  /* First call, begin from root */
792  case NextStepBegin:
793  current = iter->rb->root;
794  iter->next_step = NextStepLeft;
795  goto loop;
796 
797  case NextStepLeft:
798  while (current->left != RBNIL)
799  current = current->left;
800 
801  iter->next_step = NextStepRight;
802  goto loop;
803 
804  case NextStepRight:
805  if (current->right != RBNIL)
806  {
807  current = current->right;
808  iter->next_step = NextStepLeft;
809  goto loop;
810  }
811  else /* not moved - return current, then go up */
812  iter->next_step = NextStepUp;
813  break;
814 
815  case NextStepUp:
816  came_from = current;
817  current = current->parent;
818  if (current == NULL)
819  {
820  iter->is_over = true;
821  break; /* end of iteration */
822  }
823  else if (came_from == current->right)
824  {
825  /* return current, then continue to go up */
826  break;
827  }
828  else
829  {
830  /* otherwise we came from the left */
831  Assert(came_from == current->left);
832  iter->next_step = NextStepRight;
833  goto loop;
834  }
835  }
836 
837  iter->last_visited = current;
838  return current;
839 }
840 
841 /*
842  * rb_begin_iterate: prepare to traverse the tree in any of several orders
843  *
844  * After calling rb_begin_iterate, call rb_iterate repeatedly until it
845  * returns NULL or the traversal stops being of interest.
846  *
847  * If the tree is changed during traversal, results of further calls to
848  * rb_iterate are unspecified. Multiple concurrent iterators on the same
849  * tree are allowed.
850  *
851  * The iterator state is stored in the 'iter' struct. The caller should
852  * treat it as opaque struct.
853  */
854 void
856 {
857  /* Common initialization for all traversal orders */
858  iter->rb = rb;
859  iter->last_visited = NULL;
860  iter->is_over = (rb->root == RBNIL);
861 
862  switch (ctrl)
863  {
864  case LeftRightWalk: /* visit left, then self, then right */
866  break;
867  case RightLeftWalk: /* visit right, then self, then left */
869  break;
870  case DirectWalk: /* visit self, then left, then right */
871  iter->iterate = rb_direct_iterator;
872  break;
873  case InvertedWalk: /* visit left, then right, then self */
875  iter->next_step = NextStepBegin;
876  break;
877  default:
878  elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
879  }
880 }
881 
882 /*
883  * rb_iterate: return the next node in traversal order, or NULL if no more
884  */
885 RBNode *
887 {
888  if (iter->is_over)
889  return NULL;
890 
891  return iter->iterate(iter);
892 }
struct RBNode * left
Definition: rbtree.h:26
RBNode * rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
Definition: rbtree.c:399
void(* rb_freefunc)(RBNode *x, void *arg)
Definition: rbtree.h:63
static void rb_rotate_left(RBTree *rb, RBNode *x)
Definition: rbtree.c:209
static void rb_insert_fixup(RBTree *rb, RBNode *x)
Definition: rbtree.c:290
RBNode * last_visited
Definition: rbtree.h:54
RBTree * rb_create(Size node_size, rb_comparator comparator, rb_combiner combiner, rb_allocfunc allocfunc, rb_freefunc freefunc, void *arg)
Definition: rbtree.c:110
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:53
int(* rb_comparator)(const RBNode *a, const RBNode *b, void *arg)
Definition: rbtree.h:60
rb_comparator comparator
Definition: rbtree.c:49
rb_allocfunc allocfunc
Definition: rbtree.c:51
RBNode * rb_iterate(RBTreeIterator *iter)
Definition: rbtree.c:886
Size node_size
Definition: rbtree.c:47
#define RBRED
Definition: rbtree.c:36
RBNode * rb_leftmost(RBTree *rb)
Definition: rbtree.c:181
struct RBNode * right
Definition: rbtree.h:27
char next_step
Definition: rbtree.h:55
#define ERROR
Definition: elog.h:43
struct RBNode * parent
Definition: rbtree.h:28
Definition: rbtree.h:23
rb_combiner combiner
Definition: rbtree.c:50
#define RBNIL
Definition: rbtree.c:61
bool is_over
Definition: rbtree.h:56
static RBNode sentinel
Definition: rbtree.c:63
static RBNode * rb_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:650
char color
Definition: rbtree.h:25
rb_freefunc freefunc
Definition: rbtree.c:52
void(* rb_combiner)(RBNode *existing, const RBNode *newdata, void *arg)
Definition: rbtree.h:61
static RBNode * rb_direct_iterator(RBTreeIterator *iter)
Definition: rbtree.c:734
void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:855
void * arg
Definition: rbtree.c:54
#define NULL
Definition: c.h:229
static void rb_rotate_right(RBTree *rb, RBNode *x)
Definition: rbtree.c:246
#define Assert(condition)
Definition: c.h:675
static void rb_delete_node(RBTree *rb, RBNode *z)
Definition: rbtree.c:565
RBTree * rb
Definition: rbtree.h:52
RBOrderControl
Definition: rbtree.h:35
static RBNode * rb_inverted_iterator(RBTreeIterator *iter)
Definition: rbtree.c:781
size_t Size
Definition: c.h:356
static void rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
Definition: rbtree.c:135
RBNode * root
Definition: rbtree.c:43
RBNode *(* rb_allocfunc)(void *arg)
Definition: rbtree.h:62
void * palloc(Size size)
Definition: mcxt.c:849
static RBNode * rb_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:692
Definition: rbtree.c:41
void * arg
#define RBBLACK
Definition: rbtree.c:35
#define elog
Definition: elog.h:219
InvertedWalkNextStep
Definition: rbtree.c:69
static void rb_delete_fixup(RBTree *rb, RBNode *x)
Definition: rbtree.c:467
RBNode * rb_find(RBTree *rb, const RBNode *data)
Definition: rbtree.c:153
void rb_delete(RBTree *rb, RBNode *node)
Definition: rbtree.c:640
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742