2 * Copyright (c) 2019 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
17 * Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
18 * Introduction to algorithms. MIT press, 3rd Edition, Ch. 13
21 #include <vppinfra/rbtree.h>
24 rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x)
26 rb_node_t *y, *tmp, *xp;
27 rb_node_index_t xi, yi;
29 xi = rb_node_index (rt, x);
31 y = rb_node_right (rt, x);
33 if (y->left != RBTREE_TNIL_INDEX)
35 tmp = rb_node_left (rt, y);
38 xp = rb_node_parent (rt, x);
39 y->parent = x->parent;
40 if (x->parent == RBTREE_TNIL_INDEX)
41 rt->root = rb_node_index (rt, y);
42 else if (xp->left == xi)
51 rb_tree_rotate_right (rb_tree_t * rt, rb_node_t * y)
53 rb_node_index_t yi, xi;
56 yi = rb_node_index (rt, y);
58 x = rb_node_left (rt, y);
60 if (x->right != RBTREE_TNIL_INDEX)
62 rb_node_t *tmp = rb_node_right (rt, x);
65 yp = rb_node_parent (rt, y);
66 x->parent = y->parent;
67 if (y->parent == RBTREE_TNIL_INDEX)
68 rt->root = rb_node_index (rt, x);
69 else if (yp->right == yi)
78 rb_tree_fixup_inline (rb_tree_t * rt, rb_node_t * y, rb_node_t * z)
83 while (y->color == RBTREE_RED)
85 zi = rb_node_index (rt, z);
86 zp = rb_node_parent (rt, z);
87 zpp = rb_node_parent (rt, zp);
88 if (z->parent == zpp->left)
90 y = rb_node_right (rt, zpp);
91 if (y->color == RBTREE_RED)
93 zp->color = RBTREE_BLACK;
94 y->color = RBTREE_BLACK;
95 zpp->color = RBTREE_RED;
103 rb_tree_rotate_left (rt, z);
104 zp = rb_node (rt, z->parent);
105 zpp = rb_node (rt, zp->parent);
107 zp->color = RBTREE_BLACK;
108 zpp->color = RBTREE_RED;
109 rb_tree_rotate_right (rt, zpp);
114 y = rb_node (rt, zpp->left);
115 if (y->color == RBTREE_RED)
117 zp->color = RBTREE_BLACK;
118 y->color = RBTREE_BLACK;
119 zpp->color = RBTREE_RED;
127 rb_tree_rotate_right (rt, z);
128 zp = rb_node (rt, z->parent);
129 zpp = rb_node (rt, zp->parent);
131 zp->color = RBTREE_BLACK;
132 zpp->color = RBTREE_RED;
133 rb_tree_rotate_left (rt, zpp);
137 rb_node (rt, rt->root)->color = RBTREE_BLACK;
141 rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
143 rb_node_index_t yi = 0, xi = rt->root;
146 y = rb_node (rt, RBTREE_TNIL_INDEX);
147 while (xi != RBTREE_TNIL_INDEX)
149 x = rb_node (rt, xi);
156 yi = rb_node_index (rt, y);
158 if (yi == RBTREE_TNIL_INDEX)
159 rt->root = rb_node_index (rt, z);
160 else if (z->key < y->key)
161 y->left = rb_node_index (rt, z);
163 y->right = rb_node_index (rt, z);
165 /* Tree fixup stage */
166 rb_tree_fixup_inline (rt, y, z);
170 rb_tree_add (rb_tree_t * rt, u32 key)
174 pool_get_zero (rt->nodes, n);
176 n->color = RBTREE_RED;
177 rb_tree_insert (rt, n);
178 return rb_node_index (rt, n);
182 rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque)
186 pool_get_zero (rt->nodes, n);
188 n->color = RBTREE_RED;
190 rb_tree_insert (rt, n);
191 return rb_node_index (rt, n);
195 rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
197 rb_node_index_t yi = 0, xi = rt->root;
198 rb_node_t *z, *y, *x;
200 pool_get_zero (rt->nodes, z);
202 z->color = RBTREE_RED;
205 y = rb_node (rt, RBTREE_TNIL_INDEX);
206 while (xi != RBTREE_TNIL_INDEX)
208 x = rb_node (rt, xi);
210 if (ltfn (z->key, x->key))
215 yi = rb_node_index (rt, y);
217 if (yi == RBTREE_TNIL_INDEX)
218 rt->root = rb_node_index (rt, z);
219 else if (ltfn (z->key, y->key))
220 y->left = rb_node_index (rt, z);
222 y->right = rb_node_index (rt, z);
224 rb_tree_fixup_inline (rt, y, z);
226 return rb_node_index (rt, z);
230 rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
232 while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
234 x = rb_node_left (rt, x);
236 x = rb_node_right (rt, x);
241 rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x, u32 key,
244 while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
245 if (ltfn (key, x->key))
246 x = rb_node_left (rt, x);
248 x = rb_node_right (rt, x);
253 rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
255 while (x->left != RBTREE_TNIL_INDEX)
256 x = rb_node_left (rt, x);
261 rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x)
263 while (x->right != RBTREE_TNIL_INDEX)
264 x = rb_node_right (rt, x);
269 rb_tree_successor (rb_tree_t * rt, rb_node_t * x)
273 if (x->right != RBTREE_TNIL_INDEX)
274 return rb_tree_min_subtree (rt, rb_node_right (rt, x));
276 y = rb_node_parent (rt, x);
277 while (!rb_node_is_tnil (rt, y) && y->right == rb_node_index (rt, x))
280 y = rb_node_parent (rt, y);
286 rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x)
290 if (x->left != RBTREE_TNIL_INDEX)
291 return rb_tree_max_subtree (rt, rb_node_left (rt, x));
293 y = rb_node_parent (rt, x);
294 while (!rb_node_is_tnil (rt, y) && y->left == rb_node_index (rt, x))
297 y = rb_node_parent (rt, y);
303 rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
307 up = rb_node_parent (rt, u);
308 if (u->parent == RBTREE_TNIL_INDEX)
309 rt->root = rb_node_index (rt, v);
310 else if (rb_node_index (rt, u) == up->left)
311 up->left = rb_node_index (rt, v);
313 up->right = rb_node_index (rt, v);
314 v->parent = u->parent;
318 rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
320 rb_node_color_t y_original_color;
321 rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
322 rb_node_index_t xi, yi;
325 y_original_color = y->color;
327 if (z->left == RBTREE_TNIL_INDEX)
329 x = rb_node_right (rt, z);
330 rb_tree_transplant (rt, z, x);
332 else if (z->right == RBTREE_TNIL_INDEX)
334 x = rb_node_left (rt, z);
335 rb_tree_transplant (rt, z, x);
339 y = rb_tree_min_subtree (rt, rb_node_right (rt, z));
340 y_original_color = y->color;
341 x = rb_node_right (rt, y);
342 yi = rb_node_index (rt, y);
343 if (y->parent == rb_node_index (rt, z))
347 rb_tree_transplant (rt, y, x);
349 yr = rb_node_right (rt, y);
352 rb_tree_transplant (rt, z, y);
354 yl = rb_node_left (rt, y);
359 if (y_original_color == RBTREE_RED)
362 /* Tree fixup needed */
364 xi = rb_node_index (rt, x);
365 while (xi != rt->root && x->color == RBTREE_BLACK)
367 xp = rb_node_parent (rt, x);
370 w = rb_node_right (rt, xp);
371 if (w->color == RBTREE_RED)
373 w->color = RBTREE_BLACK;
374 xp->color = RBTREE_RED;
375 rb_tree_rotate_left (rt, xp);
376 w = rb_node_right (rt, xp);
378 wl = rb_node_left (rt, w);
379 wr = rb_node_right (rt, w);
380 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
382 if (!rb_node_is_tnil (rt, w))
383 w->color = RBTREE_RED;
388 if (wr->color == RBTREE_BLACK)
390 wl->color = RBTREE_BLACK;
391 w->color = RBTREE_RED;
392 rb_tree_rotate_right (rt, w);
393 w = rb_node_right (rt, xp);
394 wr = rb_node_right (rt, w);
396 w->color = xp->color;
397 xp->color = RBTREE_BLACK;
398 wr->color = RBTREE_BLACK;
399 rb_tree_rotate_left (rt, xp);
400 x = rb_node (rt, rt->root);
405 w = rb_node_left (rt, xp);
406 if (w->color == RBTREE_RED)
408 w->color = RBTREE_BLACK;
409 xp->color = RBTREE_RED;
410 rb_tree_rotate_right (rt, xp);
411 w = rb_node_left (rt, xp);
413 wl = rb_node_left (rt, w);
414 wr = rb_node_right (rt, w);
415 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
417 if (!rb_node_is_tnil (rt, w))
418 w->color = RBTREE_RED;
423 if (wl->color == RBTREE_BLACK)
425 wr->color = RBTREE_BLACK;
426 w->color = RBTREE_RED;
427 rb_tree_rotate_left (rt, w);
428 w = rb_node_left (rt, xp);
429 wl = rb_node_left (rt, w);
431 w->color = xp->color;
432 xp->color = RBTREE_BLACK;
433 wl->color = RBTREE_BLACK;
434 rb_tree_rotate_right (rt, xp);
435 x = rb_node (rt, rt->root);
438 xi = rb_node_index (rt, x);
440 x->color = RBTREE_BLACK;
444 rb_tree_del (rb_tree_t * rt, u32 key)
447 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
448 if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
450 rb_tree_del_node (rt, n);
451 pool_put (rt->nodes, n);
456 rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn)
459 n = rb_tree_search_subtree_custom (rt, rb_node (rt, rt->root), key, ltfn);
460 if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
462 rb_tree_del_node (rt, n);
463 pool_put (rt->nodes, n);
468 rb_tree_n_nodes (rb_tree_t * rt)
470 return pool_elts (rt->nodes);
474 rb_tree_free_nodes (rb_tree_t * rt)
476 pool_free (rt->nodes);
477 rt->root = RBTREE_TNIL_INDEX;
481 rb_tree_init (rb_tree_t * rt)
486 rt->root = RBTREE_TNIL_INDEX;
488 /* By convention first node, index 0, is the T.nil sentinel */
489 pool_get_zero (rt->nodes, tnil);
490 tnil->color = RBTREE_BLACK;
494 * fd.io coding-style-patch-verification: ON
497 * eval: (c-set-style "gnu")