Age Owner Branch data 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-2025, 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 *
2496 tgl@sss.pgh.pa.us 102 :CBC 227 : 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 : : {
5515 109 : 227 : RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
110 : :
2496 111 [ - + ]: 227 : Assert(node_size > sizeof(RBTNode));
112 : :
113 : 227 : tree->root = RBTNIL;
5515 114 : 227 : tree->node_size = node_size;
5686 teodor@sigaev.ru 115 : 227 : tree->comparator = comparator;
5515 tgl@sss.pgh.pa.us 116 : 227 : tree->combiner = combiner;
117 : 227 : tree->allocfunc = allocfunc;
5686 teodor@sigaev.ru 118 : 227 : tree->freefunc = freefunc;
119 : :
120 : 227 : tree->arg = arg;
121 : :
122 : 227 : return tree;
123 : : }
124 : :
125 : : /* Copy the additional data fields from one RBTNode to another */
126 : : static inline void
2496 tgl@sss.pgh.pa.us 127 : 322019 : rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
128 : : {
129 : 322019 : memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
5515 130 : 322019 : }
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 *
2496 145 : 40001 : rbt_find(RBTree *rbt, const RBTNode *data)
146 : : {
147 : 40001 : RBTNode *node = rbt->root;
148 : :
149 [ + + ]: 489260 : while (node != RBTNIL)
150 : : {
151 : 478259 : int cmp = rbt->comparator(data, node, rbt->arg);
152 : :
5686 teodor@sigaev.ru 153 [ + + ]: 478259 : if (cmp == 0)
5515 tgl@sss.pgh.pa.us 154 : 29000 : return node;
5686 teodor@sigaev.ru 155 [ + + ]: 449259 : else if (cmp < 0)
156 : 258890 : node = node->left;
157 : : else
158 : 190369 : 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 *
1156 akorotkov@postgresql 172 : 5655 : rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
173 : : {
174 : 5655 : RBTNode *node = rbt->root;
175 : 5655 : RBTNode *greater = NULL;
176 : :
177 [ + + ]: 78776 : while (node != RBTNIL)
178 : : {
179 : 73122 : int cmp = rbt->comparator(data, node, rbt->arg);
180 : :
181 [ + + + + ]: 73122 : if (equal_match && cmp == 0)
182 : 1 : return node;
183 [ + + ]: 73121 : else if (cmp < 0)
184 : : {
185 : 34659 : greater = node;
186 : 34659 : node = node->left;
187 : : }
188 : : else
189 : 38462 : node = node->right;
190 : : }
191 : :
192 : 5654 : 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 : 4350 : rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
204 : : {
205 : 4350 : RBTNode *node = rbt->root;
206 : 4350 : RBTNode *lesser = NULL;
207 : :
208 [ + + ]: 59958 : while (node != RBTNIL)
209 : : {
210 : 55609 : int cmp = rbt->comparator(data, node, rbt->arg);
211 : :
212 [ + + + + ]: 55609 : if (equal_match && cmp == 0)
213 : 1 : return node;
214 [ + + ]: 55608 : else if (cmp > 0)
215 : : {
216 : 27589 : lesser = node;
217 : 27589 : node = node->right;
218 : : }
219 : : else
220 : 28019 : node = node->left;
221 : : }
222 : :
223 : 4349 : 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 *
2496 tgl@sss.pgh.pa.us 235 : 3 : rbt_leftmost(RBTree *rbt)
236 : : {
237 : 3 : RBTNode *node = rbt->root;
238 : 3 : RBTNode *leftmost = rbt->root;
239 : :
240 [ + + ]: 15 : while (node != RBTNIL)
241 : : {
5515 242 : 12 : leftmost = node;
243 : 12 : node = node->left;
244 : : }
245 : :
2496 246 [ + + ]: 3 : if (leftmost != RBTNIL)
5515 247 : 1 : return leftmost;
248 : :
249 : 2 : 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
2496 263 : 269278 : rbt_rotate_left(RBTree *rbt, RBTNode *x)
264 : : {
265 : 269278 : RBTNode *y = x->right;
266 : :
267 : : /* establish x->right link */
5686 teodor@sigaev.ru 268 : 269278 : x->right = y->left;
2496 tgl@sss.pgh.pa.us 269 [ + + ]: 269278 : if (y->left != RBTNIL)
5686 teodor@sigaev.ru 270 : 130104 : y->left->parent = x;
271 : :
272 : : /* establish y->parent link */
2496 tgl@sss.pgh.pa.us 273 [ + - ]: 269278 : if (y != RBTNIL)
5686 teodor@sigaev.ru 274 : 269278 : y->parent = x->parent;
275 [ + + ]: 269278 : if (x->parent)
276 : : {
277 [ + + ]: 268812 : if (x == x->parent->left)
278 : 82351 : x->parent->left = y;
279 : : else
280 : 186461 : x->parent->right = y;
281 : : }
282 : : else
283 : : {
2496 tgl@sss.pgh.pa.us 284 : 466 : rbt->root = y;
285 : : }
286 : :
287 : : /* link x and y */
5686 teodor@sigaev.ru 288 : 269278 : y->left = x;
2496 tgl@sss.pgh.pa.us 289 [ + - ]: 269278 : if (x != RBTNIL)
5686 teodor@sigaev.ru 290 : 269278 : x->parent = y;
291 : 269278 : }
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
2496 tgl@sss.pgh.pa.us 300 : 70764 : rbt_rotate_right(RBTree *rbt, RBTNode *x)
301 : : {
302 : 70764 : RBTNode *y = x->left;
303 : :
304 : : /* establish x->left link */
5686 teodor@sigaev.ru 305 : 70764 : x->left = y->right;
2496 tgl@sss.pgh.pa.us 306 [ + + ]: 70764 : if (y->right != RBTNIL)
5686 teodor@sigaev.ru 307 : 22585 : y->right->parent = x;
308 : :
309 : : /* establish y->parent link */
2496 tgl@sss.pgh.pa.us 310 [ + - ]: 70764 : if (y != RBTNIL)
5686 teodor@sigaev.ru 311 : 70764 : y->parent = x->parent;
312 [ + + ]: 70764 : if (x->parent)
313 : : {
314 [ + + ]: 70696 : if (x == x->parent->right)
315 : 62382 : x->parent->right = y;
316 : : else
317 : 8314 : x->parent->left = y;
318 : : }
319 : : else
320 : : {
2496 tgl@sss.pgh.pa.us 321 : 68 : rbt->root = y;
322 : : }
323 : :
324 : : /* link x and y */
5686 teodor@sigaev.ru 325 : 70764 : y->right = x;
2496 tgl@sss.pgh.pa.us 326 [ + - ]: 70764 : if (x != RBTNIL)
5686 teodor@sigaev.ru 327 : 70764 : x->parent = y;
328 : 70764 : }
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
2496 tgl@sss.pgh.pa.us 344 : 319386 : rbt_insert_fixup(RBTree *rbt, RBTNode *x)
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 [ + + + + ]: 869883 : 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 : : */
5686 teodor@sigaev.ru 368 [ + + ]: 550497 : if (x->parent == x->parent->parent->left)
369 : : {
2496 tgl@sss.pgh.pa.us 370 : 80887 : RBTNode *y = x->parent->parent->right;
371 : :
372 [ + + ]: 80887 : if (y->color == RBTRED)
373 : : {
374 : : /* uncle is RBTRED */
375 : 19702 : x->parent->color = RBTBLACK;
376 : 19702 : y->color = RBTBLACK;
377 : 19702 : x->parent->parent->color = RBTRED;
378 : :
5686 teodor@sigaev.ru 379 : 19702 : x = x->parent->parent;
380 : : }
381 : : else
382 : : {
383 : : /* uncle is RBTBLACK */
384 [ + + ]: 61185 : if (x == x->parent->right)
385 : : {
386 : : /* make x a left child */
387 : 53829 : x = x->parent;
2496 tgl@sss.pgh.pa.us 388 : 53829 : rbt_rotate_left(rbt, x);
389 : : }
390 : :
391 : : /* recolor and rotate */
392 : 61185 : x->parent->color = RBTBLACK;
393 : 61185 : x->parent->parent->color = RBTRED;
394 : :
395 : 61185 : rbt_rotate_right(rbt, x->parent->parent);
396 : : }
397 : : }
398 : : else
399 : : {
400 : : /* mirror image of above code */
401 : 469610 : RBTNode *y = x->parent->parent->left;
402 : :
403 [ + + ]: 469610 : if (y->color == RBTRED)
404 : : {
405 : : /* uncle is RBTRED */
406 : 260410 : x->parent->color = RBTBLACK;
407 : 260410 : y->color = RBTBLACK;
408 : 260410 : x->parent->parent->color = RBTRED;
409 : :
5686 teodor@sigaev.ru 410 : 260410 : x = x->parent->parent;
411 : : }
412 : : else
413 : : {
414 : : /* uncle is RBTBLACK */
415 [ + + ]: 209200 : if (x == x->parent->left)
416 : : {
417 : 7436 : x = x->parent;
2496 tgl@sss.pgh.pa.us 418 : 7436 : rbt_rotate_right(rbt, x);
419 : : }
420 : 209200 : x->parent->color = RBTBLACK;
421 : 209200 : x->parent->parent->color = RBTRED;
422 : :
423 : 209200 : 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 : 319386 : rbt->root->color = RBTBLACK;
5686 teodor@sigaev.ru 433 : 319386 : }
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 *
2496 tgl@sss.pgh.pa.us 453 : 1556485 : 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 : 1556485 : current = rbt->root;
5686 teodor@sigaev.ru 462 : 1556485 : parent = NULL;
5515 tgl@sss.pgh.pa.us 463 : 1556485 : cmp = 0; /* just to prevent compiler warning */
464 : :
2496 465 [ + + ]: 15490892 : while (current != RBTNIL)
466 : : {
467 : 15171506 : cmp = rbt->comparator(data, current, rbt->arg);
5686 teodor@sigaev.ru 468 [ + + ]: 15171506 : if (cmp == 0)
469 : : {
470 : : /*
471 : : * Found node with given key. Apply combiner.
472 : : */
2496 tgl@sss.pgh.pa.us 473 : 1237099 : rbt->combiner(current, data, rbt->arg);
5515 474 : 1237099 : *isNew = false;
475 : 1237099 : return current;
476 : : }
5686 teodor@sigaev.ru 477 : 13934407 : parent = current;
478 [ + + ]: 13934407 : current = (cmp < 0) ? current->left : current->right;
479 : : }
480 : :
481 : : /*
482 : : * Value is not present, so create a new node containing data.
483 : : */
5515 tgl@sss.pgh.pa.us 484 : 319386 : *isNew = true;
485 : :
2496 486 : 319386 : x = rbt->allocfunc(rbt->arg);
487 : :
488 : 319386 : x->color = RBTRED;
489 : :
490 : 319386 : x->left = RBTNIL;
491 : 319386 : x->right = RBTNIL;
5515 492 : 319386 : x->parent = parent;
2496 493 : 319386 : rbt_copy_data(rbt, x, data);
494 : :
495 : : /* insert node in tree */
5686 teodor@sigaev.ru 496 [ + + ]: 319386 : if (parent)
497 : : {
498 [ + + ]: 319183 : if (cmp < 0)
499 : 69142 : parent->left = x;
500 : : else
501 : 250041 : parent->right = x;
502 : : }
503 : : else
504 : : {
2496 tgl@sss.pgh.pa.us 505 : 203 : rbt->root = x;
506 : : }
507 : :
508 : 319386 : rbt_insert_fixup(rbt, x);
509 : :
5515 510 : 319386 : 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
2496 521 : 13086 : rbt_delete_fixup(RBTree *rbt, RBTNode *x)
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 [ + + + + ]: 24280 : 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 : : */
5686 teodor@sigaev.ru 537 [ + + ]: 11194 : if (x == x->parent->left)
538 : : {
2496 tgl@sss.pgh.pa.us 539 : 9656 : RBTNode *w = x->parent->right;
540 : :
541 [ + + ]: 9656 : if (w->color == RBTRED)
542 : : {
543 : 2267 : w->color = RBTBLACK;
544 : 2267 : x->parent->color = RBTRED;
545 : :
546 : 2267 : rbt_rotate_left(rbt, x->parent);
5686 teodor@sigaev.ru 547 : 2267 : w = x->parent->right;
548 : : }
549 : :
2496 tgl@sss.pgh.pa.us 550 [ + + + + ]: 9656 : if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
551 : : {
552 : 5930 : w->color = RBTRED;
553 : :
5686 teodor@sigaev.ru 554 : 5930 : x = x->parent;
555 : : }
556 : : else
557 : : {
2496 tgl@sss.pgh.pa.us 558 [ + + ]: 3726 : if (w->right->color == RBTBLACK)
559 : : {
560 : 1292 : w->left->color = RBTBLACK;
561 : 1292 : w->color = RBTRED;
562 : :
563 : 1292 : rbt_rotate_right(rbt, w);
5686 teodor@sigaev.ru 564 : 1292 : w = x->parent->right;
565 : : }
566 : 3726 : w->color = x->parent->color;
2496 tgl@sss.pgh.pa.us 567 : 3726 : x->parent->color = RBTBLACK;
568 : 3726 : w->right->color = RBTBLACK;
569 : :
570 : 3726 : rbt_rotate_left(rbt, x->parent);
571 : 3726 : x = rbt->root; /* Arrange for loop to terminate. */
572 : : }
573 : : }
574 : : else
575 : : {
576 : 1538 : RBTNode *w = x->parent->left;
577 : :
578 [ + + ]: 1538 : if (w->color == RBTRED)
579 : : {
580 : 159 : w->color = RBTBLACK;
581 : 159 : x->parent->color = RBTRED;
582 : :
583 : 159 : rbt_rotate_right(rbt, x->parent);
5686 teodor@sigaev.ru 584 : 159 : w = x->parent->left;
585 : : }
586 : :
2496 tgl@sss.pgh.pa.us 587 [ + + + + ]: 1538 : if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
588 : : {
589 : 846 : w->color = RBTRED;
590 : :
5686 teodor@sigaev.ru 591 : 846 : x = x->parent;
592 : : }
593 : : else
594 : : {
2496 tgl@sss.pgh.pa.us 595 [ + + ]: 692 : if (w->left->color == RBTBLACK)
596 : : {
597 : 256 : w->right->color = RBTBLACK;
598 : 256 : w->color = RBTRED;
599 : :
600 : 256 : rbt_rotate_left(rbt, w);
5686 teodor@sigaev.ru 601 : 256 : w = x->parent->left;
602 : : }
603 : 692 : w->color = x->parent->color;
2496 tgl@sss.pgh.pa.us 604 : 692 : x->parent->color = RBTBLACK;
605 : 692 : w->left->color = RBTBLACK;
606 : :
607 : 692 : rbt_rotate_right(rbt, x->parent);
608 : 692 : x = rbt->root; /* Arrange for loop to terminate. */
609 : : }
610 : : }
611 : : }
612 : 13086 : x->color = RBTBLACK;
5686 teodor@sigaev.ru 613 : 13086 : }
614 : :
615 : : /*
616 : : * Delete node z from tree.
617 : : */
618 : : static void
2496 tgl@sss.pgh.pa.us 619 : 15031 : rbt_delete_node(RBTree *rbt, RBTNode *z)
620 : : {
621 : : RBTNode *x,
622 : : *y;
623 : :
624 : : /* This is just paranoia: we should only get called on a valid node */
625 [ + - - + ]: 15031 : if (!z || z == RBTNIL)
5686 teodor@sigaev.ru 626 :UBC 0 : 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 : : */
2496 tgl@sss.pgh.pa.us 633 [ + + + + ]:CBC 15031 : if (z->left == RBTNIL || z->right == RBTNIL)
634 : : {
635 : : /* y has a RBTNIL node as a child */
5686 teodor@sigaev.ru 636 : 12398 : y = z;
637 : : }
638 : : else
639 : : {
640 : : /* find tree successor */
641 : 2633 : y = z->right;
2496 tgl@sss.pgh.pa.us 642 [ + + ]: 5907 : while (y->left != RBTNIL)
5686 teodor@sigaev.ru 643 : 3274 : y = y->left;
644 : : }
645 : :
646 : : /* x is y's only child */
2496 tgl@sss.pgh.pa.us 647 [ + + ]: 15031 : if (y->left != RBTNIL)
5686 teodor@sigaev.ru 648 : 505 : x = y->left;
649 : : else
650 : 14526 : x = y->right;
651 : :
652 : : /* Remove y from the tree. */
653 : 15031 : x->parent = y->parent;
654 [ + + ]: 15031 : if (y->parent)
655 : : {
656 [ + + ]: 15029 : if (y == y->parent->left)
657 : 12333 : y->parent->left = x;
658 : : else
659 : 2696 : y->parent->right = x;
660 : : }
661 : : else
662 : : {
2496 tgl@sss.pgh.pa.us 663 : 2 : 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 : : */
5686 teodor@sigaev.ru 670 [ + + ]: 15031 : if (y != z)
2496 tgl@sss.pgh.pa.us 671 : 2633 : 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 [ + + ]: 15031 : if (y->color == RBTBLACK)
678 : 13086 : rbt_delete_fixup(rbt, x);
679 : :
680 : : /* Now we can recycle the y node */
681 [ + - ]: 15031 : if (rbt->freefunc)
682 : 15031 : 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
695 : 15031 : rbt_delete(RBTree *rbt, RBTNode *node)
696 : : {
697 : 15031 : rbt_delete_node(rbt, node);
5686 teodor@sigaev.ru 698 : 15031 : }
699 : :
700 : : /**********************************************************************
701 : : * Traverse *
702 : : **********************************************************************/
703 : :
704 : : static RBTNode *
2496 tgl@sss.pgh.pa.us 705 : 269584 : rbt_left_right_iterator(RBTreeIterator *iter)
706 : : {
3291 heikki.linnakangas@i 707 [ + + ]: 269584 : if (iter->last_visited == NULL)
708 : : {
2496 tgl@sss.pgh.pa.us 709 : 198 : iter->last_visited = iter->rbt->root;
710 [ + + ]: 1031 : while (iter->last_visited->left != RBTNIL)
3291 heikki.linnakangas@i 711 : 833 : iter->last_visited = iter->last_visited->left;
712 : :
713 : 198 : return iter->last_visited;
714 : : }
715 : :
2496 tgl@sss.pgh.pa.us 716 [ + + ]: 269386 : if (iter->last_visited->right != RBTNIL)
717 : : {
3291 heikki.linnakangas@i 718 : 134702 : iter->last_visited = iter->last_visited->right;
2496 tgl@sss.pgh.pa.us 719 [ + + ]: 268355 : while (iter->last_visited->left != RBTNIL)
3291 heikki.linnakangas@i 720 : 133653 : iter->last_visited = iter->last_visited->left;
721 : :
722 : 134702 : return iter->last_visited;
723 : : }
724 : :
725 : : for (;;)
5686 teodor@sigaev.ru 726 : 134702 : {
2496 tgl@sss.pgh.pa.us 727 : 269386 : RBTNode *came_from = iter->last_visited;
728 : :
3291 heikki.linnakangas@i 729 : 269386 : iter->last_visited = iter->last_visited->parent;
730 [ + + ]: 269386 : if (iter->last_visited == NULL)
731 : : {
732 : 198 : iter->is_over = true;
5686 teodor@sigaev.ru 733 : 198 : break;
734 : : }
735 : :
3291 heikki.linnakangas@i 736 [ + + ]: 269188 : if (iter->last_visited->left == came_from)
737 : 134486 : 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 : 134684 : return iter->last_visited;
744 : : }
745 : :
746 : : static RBTNode *
2496 tgl@sss.pgh.pa.us 747 : 10001 : rbt_right_left_iterator(RBTreeIterator *iter)
748 : : {
3291 heikki.linnakangas@i 749 [ + + ]: 10001 : if (iter->last_visited == NULL)
750 : : {
2496 tgl@sss.pgh.pa.us 751 : 1 : iter->last_visited = iter->rbt->root;
752 [ + + ]: 13 : while (iter->last_visited->right != RBTNIL)
3291 heikki.linnakangas@i 753 : 12 : iter->last_visited = iter->last_visited->right;
754 : :
755 : 1 : return iter->last_visited;
756 : : }
757 : :
2496 tgl@sss.pgh.pa.us 758 [ + + ]: 10000 : if (iter->last_visited->left != RBTNIL)
759 : : {
3291 heikki.linnakangas@i 760 : 5036 : iter->last_visited = iter->last_visited->left;
2496 tgl@sss.pgh.pa.us 761 [ + + ]: 9987 : while (iter->last_visited->right != RBTNIL)
3291 heikki.linnakangas@i 762 : 4951 : iter->last_visited = iter->last_visited->right;
763 : :
764 : 5036 : return iter->last_visited;
765 : : }
766 : :
767 : : for (;;)
768 : 5036 : {
2496 tgl@sss.pgh.pa.us 769 : 10000 : RBTNode *came_from = iter->last_visited;
770 : :
3291 heikki.linnakangas@i 771 : 10000 : iter->last_visited = iter->last_visited->parent;
772 [ + + ]: 10000 : if (iter->last_visited == NULL)
773 : : {
774 : 1 : iter->is_over = true;
5686 teodor@sigaev.ru 775 : 1 : break;
776 : : }
777 : :
3291 heikki.linnakangas@i 778 [ + + ]: 9999 : if (iter->last_visited->right == came_from)
779 : 4963 : 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 : 4964 : 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
2496 tgl@sss.pgh.pa.us 802 : 225 : rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
803 : : {
804 : : /* Common initialization for all traversal orders */
805 : 225 : iter->rbt = rbt;
3291 heikki.linnakangas@i 806 : 225 : iter->last_visited = NULL;
2496 tgl@sss.pgh.pa.us 807 : 225 : iter->is_over = (rbt->root == RBTNIL);
808 : :
5686 teodor@sigaev.ru 809 [ + + - ]: 225 : switch (ctrl)
810 : : {
5671 bruce@momjian.us 811 : 223 : case LeftRightWalk: /* visit left, then self, then right */
2496 tgl@sss.pgh.pa.us 812 : 223 : iter->iterate = rbt_left_right_iterator;
5686 teodor@sigaev.ru 813 : 223 : break;
5671 bruce@momjian.us 814 : 2 : case RightLeftWalk: /* visit right, then self, then left */
2496 tgl@sss.pgh.pa.us 815 : 2 : iter->iterate = rbt_right_left_iterator;
5686 teodor@sigaev.ru 816 : 2 : break;
5686 teodor@sigaev.ru 817 :UBC 0 : default:
5515 tgl@sss.pgh.pa.us 818 [ # # ]: 0 : elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
819 : : }
5686 teodor@sigaev.ru 820 :CBC 225 : }
821 : :
822 : : /*
823 : : * rbt_iterate: return the next node in traversal order, or NULL if no more
824 : : */
825 : : RBTNode *
2496 tgl@sss.pgh.pa.us 826 : 279611 : rbt_iterate(RBTreeIterator *iter)
827 : : {
3291 heikki.linnakangas@i 828 [ + + ]: 279611 : if (iter->is_over)
5686 teodor@sigaev.ru 829 : 26 : return NULL;
830 : :
3291 heikki.linnakangas@i 831 : 279585 : return iter->iterate(iter);
832 : : }
|
