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_insert (rb_tree_t * rt, rb_node_t * z)
80 rb_node_index_t yi = 0, xi = rt->root, zi;
81 rb_node_t *y, *zpp, *x, *zp;
83 y = rb_node (rt, RBTREE_TNIL_INDEX);
84 while (xi != RBTREE_TNIL_INDEX)
93 yi = rb_node_index (rt, y);
95 if (yi == RBTREE_TNIL_INDEX)
96 rt->root = rb_node_index (rt, z);
97 else if (z->key < y->key)
98 y->left = rb_node_index (rt, z);
100 y->right = rb_node_index (rt, z);
102 /* Tree fixup stage */
103 while (y->color == RBTREE_RED)
105 zi = rb_node_index (rt, z);
106 zp = rb_node_parent (rt, z);
107 zpp = rb_node_parent (rt, zp);
108 if (z->parent == zpp->left)
110 y = rb_node_right (rt, zpp);
111 if (y->color == RBTREE_RED)
113 zp->color = RBTREE_BLACK;
114 y->color = RBTREE_BLACK;
115 zpp->color = RBTREE_RED;
123 rb_tree_rotate_left (rt, z);
124 zp = rb_node (rt, z->parent);
125 zpp = rb_node (rt, zp->parent);
127 zp->color = RBTREE_BLACK;
128 zpp->color = RBTREE_RED;
129 rb_tree_rotate_right (rt, zpp);
134 y = rb_node (rt, zpp->left);
135 if (y->color == RBTREE_RED)
137 zp->color = RBTREE_BLACK;
138 y->color = RBTREE_BLACK;
139 zpp->color = RBTREE_RED;
147 rb_tree_rotate_right (rt, z);
148 zp = rb_node (rt, z->parent);
149 zpp = rb_node (rt, zp->parent);
151 zp->color = RBTREE_BLACK;
152 zpp->color = RBTREE_RED;
153 rb_tree_rotate_left (rt, zpp);
157 rb_node (rt, rt->root)->color = RBTREE_BLACK;
161 rb_tree_add (rb_tree_t * rt, u32 key)
165 pool_get_zero (rt->nodes, n);
167 n->color = RBTREE_RED;
168 rb_tree_insert (rt, n);
169 return rb_node_index (rt, n);
173 rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque)
177 pool_get_zero (rt->nodes, n);
179 n->color = RBTREE_RED;
181 rb_tree_insert (rt, n);
182 return rb_node_index (rt, n);
186 rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
188 while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
190 x = rb_node_left (rt, x);
192 x = rb_node_right (rt, x);
197 rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
199 while (x->left != RBTREE_TNIL_INDEX)
200 x = rb_node_left (rt, x);
205 rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x)
207 while (x->right != RBTREE_TNIL_INDEX)
208 x = rb_node_right (rt, x);
213 rb_tree_successor (rb_tree_t * rt, rb_node_t * x)
217 if (x->right != RBTREE_TNIL_INDEX)
218 return rb_tree_min_subtree (rt, rb_node_right (rt, x));
220 y = rb_node_parent (rt, x);
221 while (!rb_node_is_tnil (rt, y) && y->right == rb_node_index (rt, x))
224 y = rb_node_parent (rt, y);
230 rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x)
234 if (x->left != RBTREE_TNIL_INDEX)
235 return rb_tree_max_subtree (rt, rb_node_left (rt, x));
237 y = rb_node_parent (rt, x);
238 while (!rb_node_is_tnil (rt, y) && y->left == rb_node_index (rt, x))
241 y = rb_node_parent (rt, y);
247 rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
251 up = rb_node_parent (rt, u);
252 if (u->parent == RBTREE_TNIL_INDEX)
253 rt->root = rb_node_index (rt, v);
254 else if (rb_node_index (rt, u) == up->left)
255 up->left = rb_node_index (rt, v);
257 up->right = rb_node_index (rt, v);
258 v->parent = u->parent;
262 rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
264 rb_node_color_t y_original_color;
265 rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
266 rb_node_index_t xi, yi;
269 y_original_color = y->color;
271 if (z->left == RBTREE_TNIL_INDEX)
273 x = rb_node_right (rt, z);
274 rb_tree_transplant (rt, z, x);
276 else if (z->right == RBTREE_TNIL_INDEX)
278 x = rb_node_left (rt, z);
279 rb_tree_transplant (rt, z, x);
283 y = rb_tree_min_subtree (rt, rb_node_right (rt, z));
284 y_original_color = y->color;
285 x = rb_node_right (rt, y);
286 yi = rb_node_index (rt, y);
287 if (y->parent == rb_node_index (rt, z))
291 rb_tree_transplant (rt, y, rb_node_right (rt, y));
293 yr = rb_node_right (rt, y);
296 rb_tree_transplant (rt, z, y);
298 yl = rb_node_left (rt, y);
303 if (y_original_color == RBTREE_RED)
306 /* Tree fixup needed */
308 xi = rb_node_index (rt, x);
309 while (xi != rt->root && x->color == RBTREE_BLACK)
311 xp = rb_node_parent (rt, x);
314 w = rb_node_right (rt, xp);
315 if (w->color == RBTREE_RED)
317 w->color = RBTREE_BLACK;
318 xp->color = RBTREE_RED;
319 rb_tree_rotate_left (rt, xp);
320 w = rb_node_right (rt, xp);
322 wl = rb_node_left (rt, w);
323 wr = rb_node_right (rt, w);
324 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
326 w->color = RBTREE_RED;
331 if (wr->color == RBTREE_BLACK)
333 wl->color = RBTREE_BLACK;
334 w->color = RBTREE_RED;
335 rb_tree_rotate_right (rt, w);
336 w = rb_node_right (rt, xp);
338 w->color = xp->color;
339 xp->color = RBTREE_BLACK;
340 wr->color = RBTREE_BLACK;
341 rb_tree_rotate_left (rt, xp);
342 x = rb_node (rt, rt->root);
347 w = rb_node_left (rt, xp);
348 if (w->color == RBTREE_RED)
350 w->color = RBTREE_BLACK;
351 xp->color = RBTREE_RED;
352 rb_tree_rotate_right (rt, xp);
353 w = rb_node_left (rt, xp);
355 wl = rb_node_left (rt, w);
356 wr = rb_node_right (rt, w);
357 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
359 w->color = RBTREE_RED;
364 if (wl->color == RBTREE_BLACK)
366 wr->color = RBTREE_BLACK;
367 w->color = RBTREE_RED;
368 rb_tree_rotate_left (rt, w);
369 w = rb_node_left (rt, xp);
371 w->color = xp->color;
372 xp->color = RBTREE_BLACK;
373 wl->color = RBTREE_BLACK;
374 rb_tree_rotate_right (rt, xp);
375 x = rb_node (rt, rt->root);
378 xi = rb_node_index (rt, x);
380 x->color = RBTREE_BLACK;
384 rb_tree_del (rb_tree_t * rt, u32 key)
387 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
388 if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
390 rb_tree_del_node (rt, n);
391 pool_put (rt->nodes, n);
396 rb_tree_n_nodes (rb_tree_t * rt)
398 return pool_elts (rt->nodes);
402 rb_tree_free_nodes (rb_tree_t * rt)
404 pool_free (rt->nodes);
405 rt->root = RBTREE_TNIL_INDEX;
409 rb_tree_init (rb_tree_t * rt)
414 rt->root = RBTREE_TNIL_INDEX;
416 /* By convention first node, index 0, is the T.nil sentinel */
417 pool_get_zero (rt->nodes, tnil);
418 tnil->color = RBTREE_BLACK;
422 * fd.io coding-style-patch-verification: ON
425 * eval: (c-set-style "gnu")