Age Owner TLA Line data Source code
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-2023, 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 */
49 : rbt_comparator comparator;
50 : rbt_combiner combiner;
51 : rbt_allocfunc allocfunc;
52 : rbt_freefunc freefunc;
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 *
1615 tgl 102 CBC 173 : 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 : {
4634 109 173 : RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
110 :
1615 111 173 : Assert(node_size > sizeof(RBTNode));
112 :
113 173 : tree->root = RBTNIL;
4634 114 173 : tree->node_size = node_size;
4805 teodor 115 173 : tree->comparator = comparator;
4634 tgl 116 173 : tree->combiner = combiner;
117 173 : tree->allocfunc = allocfunc;
4805 teodor 118 173 : tree->freefunc = freefunc;
119 :
120 173 : tree->arg = arg;
121 :
122 173 : return tree;
123 : }
124 :
125 : /* Copy the additional data fields from one RBTNode to another */
126 : static inline void
1615 tgl 127 320118 : rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
128 : {
129 320118 : memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
4634 130 320118 : }
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 *
1615 145 40001 : rbt_find(RBTree *rbt, const RBTNode *data)
146 : {
147 40001 : RBTNode *node = rbt->root;
148 :
149 489818 : while (node != RBTNIL)
150 : {
151 478817 : int cmp = rbt->comparator(data, node, rbt->arg);
152 :
4805 teodor 153 478817 : if (cmp == 0)
4634 tgl 154 29000 : return node;
4805 teodor 155 449817 : else if (cmp < 0)
156 254351 : node = node->left;
157 : else
158 195466 : node = node->right;
159 : }
160 :
161 11001 : 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 *
275 akorotkov 172 GNC 3538 : rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
173 : {
174 3538 : RBTNode *node = rbt->root;
175 3538 : RBTNode *greater = NULL;
176 :
177 48495 : while (node != RBTNIL)
178 : {
179 44958 : int cmp = rbt->comparator(data, node, rbt->arg);
180 :
181 44958 : if (equal_match && cmp == 0)
182 1 : return node;
183 44957 : else if (cmp < 0)
184 : {
185 19524 : greater = node;
186 19524 : node = node->left;
187 : }
188 : else
189 25433 : node = node->right;
190 : }
191 :
192 3537 : 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 6467 : rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
204 : {
205 6467 : RBTNode *node = rbt->root;
206 6467 : RBTNode *lesser = NULL;
207 :
208 90941 : while (node != RBTNIL)
209 : {
210 84475 : int cmp = rbt->comparator(data, node, rbt->arg);
211 :
212 84475 : if (equal_match && cmp == 0)
213 1 : return node;
214 84474 : else if (cmp > 0)
215 : {
216 40566 : lesser = node;
217 40566 : node = node->right;
218 : }
219 : else
220 43908 : node = node->left;
221 : }
222 :
223 6466 : 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 : */
1615 tgl 234 ECB : RBTNode *
1615 tgl 235 GIC 3 : rbt_leftmost(RBTree *rbt)
4634 tgl 236 ECB : {
1615 tgl 237 CBC 3 : RBTNode *node = rbt->root;
1615 tgl 238 GIC 3 : RBTNode *leftmost = rbt->root;
4634 tgl 239 ECB :
1615 tgl 240 GIC 17 : while (node != RBTNIL)
4634 tgl 241 ECB : {
4634 tgl 242 GIC 14 : leftmost = node;
4634 tgl 243 CBC 14 : node = node->left;
4634 tgl 244 ECB : }
245 :
1615 tgl 246 GIC 3 : if (leftmost != RBTNIL)
4634 tgl 247 CBC 1 : return leftmost;
4634 tgl 248 ECB :
4634 tgl 249 GIC 2 : return NULL;
250 : }
4634 tgl 251 ECB :
252 : /**********************************************************************
253 : * Insertion *
4805 teodor 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
1615 tgl 263 GIC 268631 : rbt_rotate_left(RBTree *rbt, RBTNode *x)
264 : {
1615 tgl 265 CBC 268631 : RBTNode *y = x->right;
266 :
4805 teodor 267 ECB : /* establish x->right link */
4805 teodor 268 CBC 268631 : x->right = y->left;
1615 tgl 269 GIC 268631 : if (y->left != RBTNIL)
4805 teodor 270 CBC 129812 : y->left->parent = x;
271 :
4805 teodor 272 ECB : /* establish y->parent link */
1615 tgl 273 GIC 268631 : if (y != RBTNIL)
4805 teodor 274 CBC 268631 : y->parent = x->parent;
275 268631 : if (x->parent)
4805 teodor 276 ECB : {
4805 teodor 277 GIC 268181 : if (x == x->parent->left)
4805 teodor 278 CBC 82317 : x->parent->left = y;
4805 teodor 279 ECB : else
4805 teodor 280 GIC 185864 : x->parent->right = y;
281 : }
4805 teodor 282 ECB : else
283 : {
1615 tgl 284 GIC 450 : rbt->root = y;
4805 teodor 285 ECB : }
286 :
287 : /* link x and y */
4805 teodor 288 GIC 268631 : y->left = x;
1615 tgl 289 268631 : if (x != RBTNIL)
4805 teodor 290 268631 : x->parent = y;
291 268631 : }
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
4805 teodor 297 ECB : * child of that node.
298 : */
299 : static void
1615 tgl 300 CBC 70783 : rbt_rotate_right(RBTree *rbt, RBTNode *x)
301 : {
302 70783 : RBTNode *y = x->left;
303 :
4805 teodor 304 ECB : /* establish x->left link */
4805 teodor 305 CBC 70783 : x->left = y->right;
1615 tgl 306 GIC 70783 : if (y->right != RBTNIL)
4805 teodor 307 22661 : y->right->parent = x;
4805 teodor 308 ECB :
309 : /* establish y->parent link */
1615 tgl 310 GIC 70783 : if (y != RBTNIL)
4805 teodor 311 CBC 70783 : y->parent = x->parent;
4805 teodor 312 GIC 70783 : if (x->parent)
313 : {
314 70729 : if (x == x->parent->right)
315 62402 : x->parent->right = y;
316 : else
317 8327 : x->parent->left = y;
318 : }
319 : else
320 : {
1615 tgl 321 54 : rbt->root = y;
322 : }
323 :
324 : /* link x and y */
4805 teodor 325 CBC 70783 : y->right = x;
1615 tgl 326 GIC 70783 : if (x != RBTNIL)
4805 teodor 327 CBC 70783 : x->parent = y;
4805 teodor 328 GIC 70783 : }
329 :
4805 teodor 330 ECB : /*
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",
3260 bruce 336 : * which move the problem progressively higher up in the tree. If one of the
4805 teodor 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
1615 tgl 344 GIC 317606 : rbt_insert_fixup(RBTree *rbt, RBTNode *x)
345 : {
4805 teodor 346 ECB : /*
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 : */
1615 tgl 350 CBC 866466 : while (x != rbt->root && x->parent->color == RBTRED)
4805 teodor 351 ECB : {
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
4790 bruce 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.
4805 teodor 367 : */
4805 teodor 368 CBC 548860 : if (x->parent == x->parent->parent->left)
4805 teodor 369 ECB : {
1615 tgl 370 GIC 80539 : RBTNode *y = x->parent->parent->right;
371 :
1615 tgl 372 CBC 80539 : if (y->color == RBTRED)
4805 teodor 373 ECB : {
1615 tgl 374 : /* uncle is RBTRED */
1615 tgl 375 GIC 19350 : x->parent->color = RBTBLACK;
1615 tgl 376 CBC 19350 : y->color = RBTBLACK;
377 19350 : x->parent->parent->color = RBTRED;
378 :
4805 teodor 379 19350 : x = x->parent->parent;
380 : }
381 : else
382 : {
1615 tgl 383 ECB : /* uncle is RBTBLACK */
4805 teodor 384 GIC 61189 : if (x == x->parent->right)
385 : {
386 : /* make x a left child */
4805 teodor 387 CBC 53860 : x = x->parent;
1615 tgl 388 53860 : rbt_rotate_left(rbt, x);
4805 teodor 389 ECB : }
390 :
391 : /* recolor and rotate */
1615 tgl 392 GIC 61189 : x->parent->color = RBTBLACK;
393 61189 : x->parent->parent->color = RBTRED;
394 :
395 61189 : rbt_rotate_right(rbt, x->parent->parent);
396 : }
397 : }
398 : else
399 : {
400 : /* mirror image of above code */
401 468321 : RBTNode *y = x->parent->parent->left;
402 :
403 468321 : if (y->color == RBTRED)
404 : {
405 : /* uncle is RBTRED */
1615 tgl 406 CBC 259682 : x->parent->color = RBTBLACK;
1615 tgl 407 GIC 259682 : y->color = RBTBLACK;
408 259682 : x->parent->parent->color = RBTRED;
409 :
4805 teodor 410 259682 : x = x->parent->parent;
411 : }
4805 teodor 412 ECB : else
413 : {
414 : /* uncle is RBTBLACK */
4805 teodor 415 GIC 208639 : if (x == x->parent->left)
416 : {
417 7436 : x = x->parent;
1615 tgl 418 7436 : rbt_rotate_right(rbt, x);
419 : }
420 208639 : x->parent->color = RBTBLACK;
421 208639 : x->parent->parent->color = RBTRED;
422 :
423 208639 : 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
4805 teodor 430 ECB : * node in the tree increases by one.
431 : */
1615 tgl 432 CBC 317606 : rbt->root->color = RBTBLACK;
4805 teodor 433 GIC 317606 : }
4805 teodor 434 ECB :
435 : /*
436 : * rbt_insert: insert a new value into the tree.
437 : *
1615 tgl 438 : * data represents the value to insert. Its RBTNode fields need not
4634 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 *
1615 tgl 453 GIC 1317870 : rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
4805 teodor 454 ECB : {
1615 tgl 455 : RBTNode *current,
456 : *parent,
4805 teodor 457 : *x;
458 : int cmp;
459 :
460 : /* find where node belongs */
1615 tgl 461 GIC 1317870 : current = rbt->root;
4805 teodor 462 1317870 : parent = NULL;
4634 tgl 463 CBC 1317870 : cmp = 0; /* just to prevent compiler warning */
464 :
1615 465 13759374 : while (current != RBTNIL)
466 : {
1615 tgl 467 GIC 13441768 : cmp = rbt->comparator(data, current, rbt->arg);
4805 teodor 468 CBC 13441768 : if (cmp == 0)
4805 teodor 469 ECB : {
470 : /*
471 : * Found node with given key. Apply combiner.
472 : */
1615 tgl 473 GIC 1000264 : rbt->combiner(current, data, rbt->arg);
4634 474 1000264 : *isNew = false;
475 1000264 : return current;
476 : }
4805 teodor 477 CBC 12441504 : parent = current;
4805 teodor 478 GIC 12441504 : current = (cmp < 0) ? current->left : current->right;
4805 teodor 479 ECB : }
480 :
481 : /*
4634 tgl 482 : * Value is not present, so create a new node containing data.
483 : */
4634 tgl 484 GIC 317606 : *isNew = true;
4634 tgl 485 ECB :
1615 tgl 486 GIC 317606 : x = rbt->allocfunc(rbt->arg);
487 :
488 317606 : x->color = RBTRED;
489 :
490 317606 : x->left = RBTNIL;
491 317606 : x->right = RBTNIL;
4634 492 317606 : x->parent = parent;
1615 493 317606 : rbt_copy_data(rbt, x, data);
4805 teodor 494 ECB :
495 : /* insert node in tree */
4805 teodor 496 GIC 317606 : if (parent)
497 : {
498 317451 : if (cmp < 0)
499 68528 : parent->left = x;
500 : else
501 248923 : parent->right = x;
502 : }
503 : else
504 : {
1615 tgl 505 155 : rbt->root = x;
506 : }
507 :
508 317606 : rbt_insert_fixup(rbt, x);
509 :
4634 510 317606 : return x;
511 : }
512 :
513 : /**********************************************************************
514 : * Deletion *
4805 teodor 515 ECB : **********************************************************************/
516 :
517 : /*
518 : * Maintain Red-Black tree balance after deleting a black node.
519 : */
520 : static void
1615 tgl 521 GIC 12875 : rbt_delete_fixup(RBTree *rbt, RBTNode *x)
522 : {
4805 teodor 523 ECB : /*
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 : */
1615 tgl 528 GIC 23962 : while (x != rbt->root && x->color == RBTBLACK)
4805 teodor 529 ECB : {
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
4790 bruce 535 : * (where the black-height is allowed to decrease).
4805 teodor 536 : */
4805 teodor 537 CBC 11087 : if (x == x->parent->left)
538 : {
1615 tgl 539 9501 : RBTNode *w = x->parent->right;
4805 teodor 540 ECB :
1615 tgl 541 GIC 9501 : if (w->color == RBTRED)
542 : {
543 2274 : w->color = RBTBLACK;
544 2274 : x->parent->color = RBTRED;
545 :
1615 tgl 546 CBC 2274 : rbt_rotate_left(rbt, x->parent);
4805 teodor 547 GIC 2274 : w = x->parent->right;
4805 teodor 548 ECB : }
549 :
1615 tgl 550 CBC 9501 : if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
551 : {
552 5898 : w->color = RBTRED;
4790 bruce 553 ECB :
4805 teodor 554 CBC 5898 : x = x->parent;
4805 teodor 555 ECB : }
556 : else
557 : {
1615 tgl 558 CBC 3603 : if (w->right->color == RBTBLACK)
559 : {
560 1257 : w->left->color = RBTBLACK;
561 1257 : w->color = RBTRED;
562 :
563 1257 : rbt_rotate_right(rbt, w);
4805 teodor 564 GIC 1257 : w = x->parent->right;
565 : }
566 3603 : w->color = x->parent->color;
1615 tgl 567 CBC 3603 : x->parent->color = RBTBLACK;
1615 tgl 568 GIC 3603 : w->right->color = RBTBLACK;
569 :
1615 tgl 570 CBC 3603 : rbt_rotate_left(rbt, x->parent);
1615 tgl 571 GIC 3603 : x = rbt->root; /* Arrange for loop to terminate. */
4805 teodor 572 ECB : }
573 : }
574 : else
575 : {
1615 tgl 576 GIC 1586 : RBTNode *w = x->parent->left;
577 :
578 1586 : if (w->color == RBTRED)
579 : {
580 157 : w->color = RBTBLACK;
581 157 : x->parent->color = RBTRED;
582 :
1615 tgl 583 CBC 157 : rbt_rotate_right(rbt, x->parent);
4805 teodor 584 GIC 157 : w = x->parent->left;
585 : }
586 :
1615 tgl 587 1586 : if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
588 : {
589 842 : w->color = RBTRED;
4790 bruce 590 ECB :
4805 teodor 591 GIC 842 : x = x->parent;
592 : }
593 : else
594 : {
1615 tgl 595 744 : if (w->left->color == RBTBLACK)
596 : {
597 255 : w->right->color = RBTBLACK;
598 255 : w->color = RBTRED;
4790 bruce 599 ECB :
1615 tgl 600 GIC 255 : rbt_rotate_left(rbt, w);
4805 teodor 601 CBC 255 : w = x->parent->left;
602 : }
603 744 : w->color = x->parent->color;
1615 tgl 604 GIC 744 : x->parent->color = RBTBLACK;
1615 tgl 605 CBC 744 : w->left->color = RBTBLACK;
4790 bruce 606 ECB :
1615 tgl 607 GIC 744 : rbt_rotate_right(rbt, x->parent);
1615 tgl 608 CBC 744 : x = rbt->root; /* Arrange for loop to terminate. */
4805 teodor 609 ECB : }
610 : }
611 : }
1615 tgl 612 CBC 12875 : x->color = RBTBLACK;
4805 teodor 613 GIC 12875 : }
4805 teodor 614 ECB :
615 : /*
616 : * Delete node z from tree.
617 : */
618 : static void
1615 tgl 619 GIC 14989 : rbt_delete_node(RBTree *rbt, RBTNode *z)
4805 teodor 620 ECB : {
621 : RBTNode *x,
622 : *y;
623 :
624 : /* This is just paranoia: we should only get called on a valid node */
1615 tgl 625 CBC 14989 : if (!z || z == RBTNIL)
4805 teodor 626 LBC 0 : return;
627 :
4805 teodor 628 ECB : /*
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 : */
1615 tgl 633 CBC 14989 : if (z->left == RBTNIL || z->right == RBTNIL)
634 : {
635 : /* y has a RBTNIL node as a child */
4805 teodor 636 GIC 12477 : y = z;
637 : }
4805 teodor 638 ECB : else
639 : {
640 : /* find tree successor */
4805 teodor 641 GIC 2512 : y = z->right;
1615 tgl 642 CBC 5302 : while (y->left != RBTNIL)
4805 teodor 643 2790 : y = y->left;
644 : }
4805 teodor 645 ECB :
646 : /* x is y's only child */
1615 tgl 647 GIC 14989 : if (y->left != RBTNIL)
4805 teodor 648 539 : x = y->left;
4805 teodor 649 ECB : else
4805 teodor 650 GIC 14450 : x = y->right;
4805 teodor 651 ECB :
652 : /* Remove y from the tree. */
4805 teodor 653 CBC 14989 : x->parent = y->parent;
4805 teodor 654 GIC 14989 : if (y->parent)
655 : {
656 14987 : if (y == y->parent->left)
4805 teodor 657 CBC 12137 : y->parent->left = x;
658 : else
659 2850 : y->parent->right = x;
4805 teodor 660 ECB : }
661 : else
662 : {
1615 tgl 663 CBC 2 : rbt->root = x;
664 : }
4805 teodor 665 ECB :
666 : /*
4634 tgl 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.
4805 teodor 669 : */
4805 teodor 670 CBC 14989 : if (y != z)
1615 tgl 671 GIC 2512 : rbt_copy_data(rbt, z, y);
672 :
673 : /*
4805 teodor 674 ECB : * 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 : */
1615 tgl 677 GIC 14989 : if (y->color == RBTBLACK)
678 12875 : rbt_delete_fixup(rbt, x);
679 :
680 : /* Now we can recycle the y node */
1615 tgl 681 CBC 14989 : if (rbt->freefunc)
1615 tgl 682 GIC 14989 : rbt->freefunc(y, rbt->arg);
683 : }
684 :
685 : /*
686 : * rbt_delete: remove the given tree entry
4634 tgl 687 ECB : *
1615 tgl 688 EUB : * "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
1615 tgl 695 CBC 14989 : rbt_delete(RBTree *rbt, RBTNode *node)
696 : {
1615 tgl 697 GIC 14989 : rbt_delete_node(rbt, node);
4805 teodor 698 CBC 14989 : }
699 :
700 : /**********************************************************************
701 : * Traverse *
702 : **********************************************************************/
4805 teodor 703 ECB :
1615 tgl 704 : static RBTNode *
1615 tgl 705 CBC 267756 : rbt_left_right_iterator(RBTreeIterator *iter)
706 : {
2410 heikki.linnakangas 707 GIC 267756 : if (iter->last_visited == NULL)
708 : {
1615 tgl 709 CBC 150 : iter->last_visited = iter->rbt->root;
710 878 : while (iter->last_visited->left != RBTNIL)
2410 heikki.linnakangas 711 GIC 728 : iter->last_visited = iter->last_visited->left;
4634 tgl 712 ECB :
2410 heikki.linnakangas 713 GIC 150 : return iter->last_visited;
714 : }
4634 tgl 715 ECB :
1615 tgl 716 CBC 267606 : if (iter->last_visited->right != RBTNIL)
717 : {
2410 heikki.linnakangas 718 133805 : iter->last_visited = iter->last_visited->right;
1615 tgl 719 266728 : while (iter->last_visited->left != RBTNIL)
2410 heikki.linnakangas 720 GIC 132923 : iter->last_visited = iter->last_visited->left;
4634 tgl 721 ECB :
2410 heikki.linnakangas 722 GIC 133805 : return iter->last_visited;
723 : }
724 :
2410 heikki.linnakangas 725 ECB : for (;;)
4805 teodor 726 GIC 133805 : {
1615 tgl 727 267606 : RBTNode *came_from = iter->last_visited;
728 :
2410 heikki.linnakangas 729 267606 : iter->last_visited = iter->last_visited->parent;
730 267606 : if (iter->last_visited == NULL)
731 : {
2410 heikki.linnakangas 732 CBC 150 : iter->is_over = true;
4805 teodor 733 150 : break;
734 : }
735 :
2410 heikki.linnakangas 736 GIC 267456 : if (iter->last_visited->left == came_from)
737 133651 : break; /* came from left sub-tree, return current
738 : * node */
2410 heikki.linnakangas 739 ECB :
740 : /* else - came from right sub-tree, continue to move up */
741 : }
742 :
2410 heikki.linnakangas 743 CBC 133801 : return iter->last_visited;
4805 teodor 744 ECB : }
745 :
746 : static RBTNode *
1615 tgl 747 GIC 10001 : rbt_right_left_iterator(RBTreeIterator *iter)
748 : {
2410 heikki.linnakangas 749 10001 : if (iter->last_visited == NULL)
750 : {
1615 tgl 751 1 : iter->last_visited = iter->rbt->root;
752 14 : while (iter->last_visited->right != RBTNIL)
2410 heikki.linnakangas 753 13 : iter->last_visited = iter->last_visited->right;
754 :
755 1 : return iter->last_visited;
756 : }
4805 teodor 757 ECB :
1615 tgl 758 GIC 10000 : if (iter->last_visited->left != RBTNIL)
4805 teodor 759 ECB : {
2410 heikki.linnakangas 760 CBC 5000 : iter->last_visited = iter->last_visited->left;
1615 tgl 761 GIC 9986 : while (iter->last_visited->right != RBTNIL)
2410 heikki.linnakangas 762 4986 : iter->last_visited = iter->last_visited->right;
763 :
764 5000 : return iter->last_visited;
765 : }
766 :
2410 heikki.linnakangas 767 ECB : for (;;)
2410 heikki.linnakangas 768 GIC 5000 : {
1615 tgl 769 CBC 10000 : RBTNode *came_from = iter->last_visited;
770 :
2410 heikki.linnakangas 771 10000 : iter->last_visited = iter->last_visited->parent;
772 10000 : if (iter->last_visited == NULL)
2410 heikki.linnakangas 773 ECB : {
2410 heikki.linnakangas 774 GIC 1 : iter->is_over = true;
4805 teodor 775 CBC 1 : break;
776 : }
777 :
2410 heikki.linnakangas 778 9999 : if (iter->last_visited->right == came_from)
2410 heikki.linnakangas 779 GIC 4999 : break; /* came from right sub-tree, return current
2410 heikki.linnakangas 780 ECB : * node */
781 :
782 : /* else - came from left sub-tree, continue to move up */
783 : }
4805 teodor 784 :
2410 heikki.linnakangas 785 GIC 5000 : return iter->last_visited;
786 : }
787 :
4634 tgl 788 ECB : /*
1615 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
4634 792 : * returns NULL or the traversal stops being of interest.
793 : *
794 : * If the tree is changed during traversal, results of further calls to
1615 795 : * rbt_iterate are unspecified. Multiple concurrent iterators on the same
796 : * tree are allowed.
797 : *
2410 heikki.linnakangas 798 : * The iterator state is stored in the 'iter' struct. The caller should
2037 tgl 799 : * treat it as an opaque struct.
800 : */
801 : void
1615 tgl 802 GIC 171 : rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
803 : {
804 : /* Common initialization for all traversal orders */
1615 tgl 805 CBC 171 : iter->rbt = rbt;
2410 heikki.linnakangas 806 GIC 171 : iter->last_visited = NULL;
1615 tgl 807 171 : iter->is_over = (rbt->root == RBTNIL);
808 :
4805 teodor 809 CBC 171 : switch (ctrl)
810 : {
4790 bruce 811 169 : case LeftRightWalk: /* visit left, then self, then right */
1615 tgl 812 GIC 169 : iter->iterate = rbt_left_right_iterator;
4805 teodor 813 CBC 169 : break;
4790 bruce 814 2 : case RightLeftWalk: /* visit right, then self, then left */
1615 tgl 815 2 : iter->iterate = rbt_right_left_iterator;
4805 teodor 816 GIC 2 : break;
4805 teodor 817 LBC 0 : default:
4634 tgl 818 UIC 0 : elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
819 : }
4805 teodor 820 CBC 171 : }
821 :
4634 tgl 822 ECB : /*
1615 823 : * rbt_iterate: return the next node in traversal order, or NULL if no more
4634 824 : */
825 : RBTNode *
1615 tgl 826 CBC 277777 : rbt_iterate(RBTreeIterator *iter)
827 : {
2410 heikki.linnakangas 828 GIC 277777 : if (iter->is_over)
4805 teodor 829 20 : return NULL;
4805 teodor 830 ECB :
2410 heikki.linnakangas 831 CBC 277757 : return iter->iterate(iter);
832 : }
|
