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