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>
23 static inline rb_node_t *
24 rb_node_right (rb_tree_t * rt, rb_node_t * n)
26 return pool_elt_at_index (rt->nodes, n->right);
29 static inline rb_node_t *
30 rb_node_left (rb_tree_t * rt, rb_node_t * n)
32 return pool_elt_at_index (rt->nodes, n->left);
35 static inline rb_node_t *
36 rb_node_parent (rb_tree_t * rt, rb_node_t * n)
38 return pool_elt_at_index (rt->nodes, n->parent);
42 rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x)
44 rb_node_t *y, *tmp, *xp;
45 rb_node_index_t xi, yi;
47 xi = rb_node_index (rt, x);
49 y = rb_node_right (rt, x);
51 if (y->left != RBTREE_TNIL_INDEX)
53 tmp = rb_node_left (rt, y);
56 xp = rb_node_parent (rt, x);
57 y->parent = x->parent;
58 if (x->parent == RBTREE_TNIL_INDEX)
59 rt->root = rb_node_index (rt, y);
60 else if (xp->left == xi)
69 rb_tree_rotate_right (rb_tree_t * rt, rb_node_t * y)
71 rb_node_index_t yi, xi;
74 yi = rb_node_index (rt, y);
76 x = rb_node_left (rt, y);
78 if (x->right != RBTREE_TNIL_INDEX)
80 rb_node_t *tmp = rb_node_right (rt, x);
83 yp = rb_node_parent (rt, y);
84 x->parent = y->parent;
85 if (y->parent == RBTREE_TNIL_INDEX)
86 rt->root = rb_node_index (rt, x);
87 else if (yp->right == yi)
96 rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
98 rb_node_index_t yi = 0, xi = rt->root, zi;
99 rb_node_t *y, *zpp, *x, *zp;
101 y = rb_node (rt, RBTREE_TNIL_INDEX);
102 while (xi != RBTREE_TNIL_INDEX)
104 x = rb_node (rt, xi);
111 yi = rb_node_index (rt, y);
113 if (yi == RBTREE_TNIL_INDEX)
114 rt->root = rb_node_index (rt, z);
115 else if (z->key < y->key)
116 y->left = rb_node_index (rt, z);
118 y->right = rb_node_index (rt, z);
120 /* Tree fixup stage */
121 while (y->color == RBTREE_RED)
123 zi = rb_node_index (rt, z);
124 zp = rb_node_parent (rt, z);
125 zpp = rb_node_parent (rt, zp);
126 if (z->parent == zpp->left)
128 y = rb_node_right (rt, zpp);
129 if (y->color == RBTREE_RED)
131 zp->color = RBTREE_BLACK;
132 y->color = RBTREE_BLACK;
133 zpp->color = RBTREE_RED;
141 rb_tree_rotate_left (rt, z);
142 zp = rb_node (rt, z->parent);
143 zpp = rb_node (rt, zp->parent);
145 zp->color = RBTREE_BLACK;
146 zpp->color = RBTREE_RED;
147 rb_tree_rotate_right (rt, zpp);
152 y = rb_node (rt, zpp->left);
153 if (y->color == RBTREE_RED)
155 zp->color = RBTREE_BLACK;
156 y->color = RBTREE_BLACK;
157 zpp->color = RBTREE_RED;
165 rb_tree_rotate_right (rt, z);
166 zp = rb_node (rt, z->parent);
167 zpp = rb_node (rt, zp->parent);
169 zp->color = RBTREE_BLACK;
170 zpp->color = RBTREE_RED;
171 rb_tree_rotate_left (rt, zpp);
175 rb_node (rt, rt->root)->color = RBTREE_BLACK;
179 rb_tree_add (rb_tree_t * rt, u32 key)
183 pool_get_zero (rt->nodes, n);
185 n->color = RBTREE_RED;
186 rb_tree_insert (rt, n);
187 return rb_node_index (rt, n);
191 rb_tree_add2 (rb_tree_t * rt, u32 key, u32 opaque)
195 pool_get_zero (rt->nodes, n);
197 n->color = RBTREE_RED;
199 rb_tree_insert (rt, n);
200 return rb_node_index (rt, n);
204 rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
206 while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
208 x = rb_node_left (rt, x);
210 x = rb_node_right (rt, x);
215 rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
217 while (x->left != RBTREE_TNIL_INDEX)
218 x = rb_node_left (rt, x);
223 rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x)
225 while (x->right != RBTREE_TNIL_INDEX)
226 x = rb_node_right (rt, x);
231 rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
235 up = rb_node_parent (rt, u);
236 if (u->parent == RBTREE_TNIL_INDEX)
237 rt->root = rb_node_index (rt, v);
238 else if (rb_node_index (rt, u) == up->left)
239 up->left = rb_node_index (rt, v);
241 up->right = rb_node_index (rt, v);
242 v->parent = u->parent;
246 rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
248 rb_node_color_t y_original_color;
249 rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
250 rb_node_index_t xi, yi;
253 y_original_color = y->color;
255 if (z->left == RBTREE_TNIL_INDEX)
257 x = rb_node_right (rt, z);
258 rb_tree_transplant (rt, z, x);
260 else if (z->right == RBTREE_TNIL_INDEX)
262 x = rb_node_left (rt, z);
263 rb_tree_transplant (rt, z, x);
267 y = rb_tree_min_subtree (rt, rb_node_right (rt, z));
268 y_original_color = y->color;
269 x = rb_node_right (rt, y);
270 yi = rb_node_index (rt, y);
271 if (y->parent == rb_node_index (rt, z))
275 rb_tree_transplant (rt, y, rb_node_right (rt, y));
277 yr = rb_node_right (rt, y);
280 rb_tree_transplant (rt, z, y);
282 yl = rb_node_left (rt, y);
287 if (y_original_color == RBTREE_RED)
290 /* Tree fixup needed */
292 xi = rb_node_index (rt, x);
293 while (xi != rt->root && x->color == RBTREE_BLACK)
295 xp = rb_node_parent (rt, x);
298 w = rb_node_right (rt, xp);
299 if (w->color == RBTREE_RED)
301 w->color = RBTREE_BLACK;
302 xp->color = RBTREE_RED;
303 rb_tree_rotate_left (rt, xp);
304 w = rb_node_right (rt, xp);
306 wl = rb_node_left (rt, w);
307 wr = rb_node_right (rt, w);
308 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
310 w->color = RBTREE_RED;
315 if (wr->color == RBTREE_BLACK)
317 wl->color = RBTREE_BLACK;
318 w->color = RBTREE_RED;
319 rb_tree_rotate_right (rt, w);
320 w = rb_node_right (rt, xp);
322 w->color = xp->color;
323 xp->color = RBTREE_BLACK;
324 wr->color = RBTREE_BLACK;
325 rb_tree_rotate_left (rt, xp);
326 x = rb_node (rt, rt->root);
331 w = rb_node_left (rt, xp);
332 if (w->color == RBTREE_RED)
334 w->color = RBTREE_BLACK;
335 xp->color = RBTREE_RED;
336 rb_tree_rotate_right (rt, xp);
337 w = rb_node_left (rt, xp);
339 wl = rb_node_left (rt, w);
340 wr = rb_node_right (rt, w);
341 if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
343 w->color = RBTREE_RED;
348 if (wl->color == RBTREE_BLACK)
350 wr->color = RBTREE_BLACK;
351 w->color = RBTREE_RED;
352 rb_tree_rotate_left (rt, w);
353 w = rb_node_left (rt, xp);
355 w->color = xp->color;
356 xp->color = RBTREE_BLACK;
357 wl->color = RBTREE_BLACK;
358 rb_tree_rotate_right (rt, xp);
359 x = rb_node (rt, rt->root);
362 xi = rb_node_index (rt, x);
364 x->color = RBTREE_BLACK;
368 rb_tree_del (rb_tree_t * rt, u32 key)
371 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
372 if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
374 rb_tree_del_node (rt, n);
375 pool_put (rt->nodes, n);
380 rb_tree_n_nodes (rb_tree_t * rt)
382 return pool_elts (rt->nodes);
386 rb_tree_free_nodes (rb_tree_t * rt)
389 pool_flush (n, rt->nodes,;);
393 rb_tree_init (rb_tree_t * rt)
398 rt->root = RBTREE_TNIL_INDEX;
400 /* By convention first node, index 0, is the T.nil sentinel */
401 pool_get_zero (rt->nodes, tnil);
402 tnil->color = RBTREE_BLACK;
406 * fd.io coding-style-patch-verification: ON
409 * eval: (c-set-style "gnu")