2 * Copyright © 2017 Jason Ekstrand
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
27 * An implementation of a red-black tree
29 * This file implements the guts of a red-black tree. The implementation
30 * is mostly based on the one in "Introduction to Algorithms", third
31 * edition, by Cormen, Leiserson, Rivest, and Stein. The primary
32 * divergence in our algorithms from those presented in CLRS is that we use
33 * NULL for the leaves instead of a sentinel. This means we have to do a
34 * tiny bit more tracking in our implementation of delete but it makes the
35 * algorithms far more explicit than stashing stuff in the sentinel.
43 rb_node_is_black(struct rb_node
*n
)
45 /* NULL nodes are leaves and therefore black */
46 return (n
== NULL
) || (n
->parent
& 1);
50 rb_node_is_red(struct rb_node
*n
)
52 return !rb_node_is_black(n
);
56 rb_node_set_black(struct rb_node
*n
)
62 rb_node_set_red(struct rb_node
*n
)
68 rb_node_copy_color(struct rb_node
*dst
, struct rb_node
*src
)
70 dst
->parent
= (dst
->parent
& ~1ull) | (src
->parent
& 1);
74 rb_node_set_parent(struct rb_node
*n
, struct rb_node
*p
)
76 n
->parent
= (n
->parent
& 1) | (uintptr_t)p
;
79 static struct rb_node
*
80 rb_node_minimum(struct rb_node
*node
)
87 static struct rb_node
*
88 rb_node_maximum(struct rb_node
*node
)
96 rb_tree_init(struct rb_tree
*T
)
102 * Replace the subtree of T rooted at u with the subtree rooted at v
104 * This is called RB-transplant in CLRS.
106 * The node to be replaced is assumed to be a non-leaf.
109 rb_tree_splice(struct rb_tree
*T
, struct rb_node
*u
, struct rb_node
*v
)
112 struct rb_node
*p
= rb_node_parent(u
);
114 assert(T
->root
== u
);
116 } else if (u
== p
->left
) {
119 assert(u
== p
->right
);
123 rb_node_set_parent(v
, p
);
127 rb_tree_rotate_left(struct rb_tree
*T
, struct rb_node
*x
)
129 assert(x
&& x
->right
);
131 struct rb_node
*y
= x
->right
;
134 rb_node_set_parent(y
->left
, x
);
135 rb_tree_splice(T
, x
, y
);
137 rb_node_set_parent(x
, y
);
141 rb_tree_rotate_right(struct rb_tree
*T
, struct rb_node
*y
)
143 assert(y
&& y
->left
);
145 struct rb_node
*x
= y
->left
;
148 rb_node_set_parent(x
->right
, y
);
149 rb_tree_splice(T
, y
, x
);
151 rb_node_set_parent(y
, x
);
155 rb_tree_insert_at(struct rb_tree
*T
, struct rb_node
*parent
,
156 struct rb_node
*node
, bool insert_left
)
158 /* This sets null children, parent, and a color of red */
159 memset(node
, 0, sizeof(*node
));
161 if (parent
== NULL
) {
162 assert(T
->root
== NULL
);
164 rb_node_set_black(node
);
169 assert(parent
->left
== NULL
);
172 assert(parent
->right
== NULL
);
173 parent
->right
= node
;
175 rb_node_set_parent(node
, parent
);
177 /* Now we do the insertion fixup */
178 struct rb_node
*z
= node
;
179 while (rb_node_is_red(rb_node_parent(z
))) {
180 struct rb_node
*z_p
= rb_node_parent(z
);
181 assert(z
== z_p
->left
|| z
== z_p
->right
);
182 struct rb_node
*z_p_p
= rb_node_parent(z_p
);
183 assert(z_p_p
!= NULL
);
184 if (z_p
== z_p_p
->left
) {
185 struct rb_node
*y
= z_p_p
->right
;
186 if (rb_node_is_red(y
)) {
187 rb_node_set_black(z_p
);
188 rb_node_set_black(y
);
189 rb_node_set_red(z_p_p
);
192 if (z
== z_p
->right
) {
194 rb_tree_rotate_left(T
, z
);
196 z_p
= rb_node_parent(z
);
197 assert(z
== z_p
->left
|| z
== z_p
->right
);
198 z_p_p
= rb_node_parent(z_p
);
200 rb_node_set_black(z_p
);
201 rb_node_set_red(z_p_p
);
202 rb_tree_rotate_right(T
, z_p_p
);
205 struct rb_node
*y
= z_p_p
->left
;
206 if (rb_node_is_red(y
)) {
207 rb_node_set_black(z_p
);
208 rb_node_set_black(y
);
209 rb_node_set_red(z_p_p
);
212 if (z
== z_p
->left
) {
214 rb_tree_rotate_right(T
, z
);
216 z_p
= rb_node_parent(z
);
217 assert(z
== z_p
->left
|| z
== z_p
->right
);
218 z_p_p
= rb_node_parent(z_p
);
220 rb_node_set_black(z_p
);
221 rb_node_set_red(z_p_p
);
222 rb_tree_rotate_left(T
, z_p_p
);
226 rb_node_set_black(T
->root
);
230 rb_tree_remove(struct rb_tree
*T
, struct rb_node
*z
)
232 /* x_p is always the parent node of X. We have to track this
233 * separately because x may be NULL.
235 struct rb_node
*x
, *x_p
;
236 struct rb_node
*y
= z
;
237 bool y_was_black
= rb_node_is_black(y
);
238 if (z
->left
== NULL
) {
240 x_p
= rb_node_parent(z
);
241 rb_tree_splice(T
, z
, x
);
242 } else if (z
->right
== NULL
) {
244 x_p
= rb_node_parent(z
);
245 rb_tree_splice(T
, z
, x
);
247 /* Find the minimum sub-node of z->right */
248 y
= rb_node_minimum(z
->right
);
249 y_was_black
= rb_node_is_black(y
);
252 if (rb_node_parent(y
) == z
) {
255 x_p
= rb_node_parent(y
);
256 rb_tree_splice(T
, y
, x
);
258 rb_node_set_parent(y
->right
, y
);
260 assert(y
->left
== NULL
);
261 rb_tree_splice(T
, z
, y
);
263 rb_node_set_parent(y
->left
, y
);
264 rb_node_copy_color(y
, z
);
267 assert(x_p
== NULL
|| x
== x_p
->left
|| x
== x_p
->right
);
272 /* Fixup RB tree after the delete */
273 while (x
!= T
->root
&& rb_node_is_black(x
)) {
274 if (x
== x_p
->left
) {
275 struct rb_node
*w
= x_p
->right
;
276 if (rb_node_is_red(w
)) {
277 rb_node_set_black(w
);
278 rb_node_set_red(x_p
);
279 rb_tree_rotate_left(T
, x_p
);
280 assert(x
== x_p
->left
);
283 if (rb_node_is_black(w
->left
) && rb_node_is_black(w
->right
)) {
287 if (rb_node_is_black(w
->right
)) {
288 rb_node_set_black(w
->left
);
290 rb_tree_rotate_right(T
, w
);
293 rb_node_copy_color(w
, x_p
);
294 rb_node_set_black(x_p
);
295 rb_node_set_black(w
->right
);
296 rb_tree_rotate_left(T
, x_p
);
300 struct rb_node
*w
= x_p
->left
;
301 if (rb_node_is_red(w
)) {
302 rb_node_set_black(w
);
303 rb_node_set_red(x_p
);
304 rb_tree_rotate_right(T
, x_p
);
305 assert(x
== x_p
->right
);
308 if (rb_node_is_black(w
->right
) && rb_node_is_black(w
->left
)) {
312 if (rb_node_is_black(w
->left
)) {
313 rb_node_set_black(w
->right
);
315 rb_tree_rotate_left(T
, w
);
318 rb_node_copy_color(w
, x_p
);
319 rb_node_set_black(x_p
);
320 rb_node_set_black(w
->left
);
321 rb_tree_rotate_right(T
, x_p
);
325 x_p
= rb_node_parent(x
);
328 rb_node_set_black(x
);
332 rb_tree_first(struct rb_tree
*T
)
334 return T
->root
? rb_node_minimum(T
->root
) : NULL
;
338 rb_tree_last(struct rb_tree
*T
)
340 return T
->root
? rb_node_maximum(T
->root
) : NULL
;
344 rb_node_next(struct rb_node
*node
)
347 /* If we have a right child, then the next thing (compared to this
348 * node) is the left-most child of our right child.
350 return rb_node_minimum(node
->right
);
352 /* If node doesn't have a right child, crawl back up the to the
353 * left until we hit a parent to the right.
355 struct rb_node
*p
= rb_node_parent(node
);
356 while (p
&& node
== p
->right
) {
358 p
= rb_node_parent(node
);
360 assert(p
== NULL
|| node
== p
->left
);
366 rb_node_prev(struct rb_node
*node
)
369 /* If we have a left child, then the previous thing (compared to
370 * this node) is the right-most child of our left child.
372 return rb_node_maximum(node
->left
);
374 /* If node doesn't have a left child, crawl back up the to the
375 * right until we hit a parent to the left.
377 struct rb_node
*p
= rb_node_parent(node
);
378 while (p
&& node
== p
->left
) {
380 p
= rb_node_parent(node
);
382 assert(p
== NULL
|| node
== p
->right
);
388 validate_rb_node(struct rb_node
*n
, int black_depth
)
391 assert(black_depth
== 0);
395 if (rb_node_is_black(n
)) {
398 assert(rb_node_is_black(n
->left
));
399 assert(rb_node_is_black(n
->right
));
402 validate_rb_node(n
->left
, black_depth
);
403 validate_rb_node(n
->right
, black_depth
);
407 rb_tree_validate(struct rb_tree
*T
)
412 assert(rb_node_is_black(T
->root
));
414 unsigned black_depth
= 0;
415 for (struct rb_node
*n
= T
->root
; n
; n
= n
->left
) {
416 if (rb_node_is_black(n
))
420 validate_rb_node(T
->root
, black_depth
);