diff options
Diffstat (limited to 'hifi/xaf/hifi-dpf/core/util/rbtree.c')
| -rw-r--r-- | hifi/xaf/hifi-dpf/core/util/rbtree.c | 842 |
1 files changed, 0 insertions, 842 deletions
diff --git a/hifi/xaf/hifi-dpf/core/util/rbtree.c b/hifi/xaf/hifi-dpf/core/util/rbtree.c deleted file mode 100644 index 740e0255..00000000 --- a/hifi/xaf/hifi-dpf/core/util/rbtree.c +++ /dev/null @@ -1,842 +0,0 @@ -/******************************************************************************* -* Copyright (C) 2018 Cadence Design Systems, Inc. -* -* Permission is hereby granted, free of charge, to any person obtaining -* a copy of this software and associated documentation files (the -* "Software"), to use this Software with Cadence processor cores only and -* not with any other processors and platforms, subject to -* the following conditions: -* -* The above copyright notice and this permission notice shall be included -* in all copies or substantial portions of the Software. -* -* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. -* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY -* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, -* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE -* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - -******************************************************************************/ - -/******************************************************************************* - * rbtree.c - * - * Red-black tree library - ******************************************************************************/ - -#include "xf.h" - -/******************************************************************************* - * Macros definitions - ******************************************************************************/ - -/* ...node color */ -#define RB_RED (1) -#define RB_BLK (0) - -/* ...pointer to parent node */ -#define RB_PARENT(tree, node) ((node)->parent) - -/* ...pointer to left child node */ -#define RB_LEFT(tree, node) ((node)->left) - -/* ...pointer to right child node */ -#define RB_RIGHT(tree, node) ((node)->right) - -/* ...pointer to right child node */ -#define RB_COLOR(tree, node) ((node)->color & 1) - -/* ...check if node is black */ -#define RB_IS_BLACK(tree, node) (!((node)->color & RB_RED)) - -/* ...root node index of the tree - can be simplified? */ -#define RB_ROOT(tree) RB_LEFT((tree), &(tree)->root) - -/* ...empty node */ -#define RB_NULL(tree) (&(tree)->root) - -/******************************************************************************* - * Helpers - ******************************************************************************/ - -#define RB_SET_P(t, n, p) \ - ({ (n)->parent = (p); }) - -#define RB_SET_L(t, n, l) \ - ({ (n)->left = (l); }) - -#define RB_SET_R(t, n, r) \ - ({ (n)->right = (r); }) - -#define RB_SET_C(t, n, c) \ - RB_SET_C_##c((t), (n)) - -#define RB_SET_C_RB_BLK(t, n) \ - ({ (n)->color &= ~1; }) - -#define RB_SET_C_RB_RED(t, n) \ - ({ (n)->color |= 1; }) - -#define RB_SET_P_C(t, n, p, c) \ - ({ (n)->parent = (p); RB_SET_C_##c(t, n); }) - -#define RB_SET_P_L(t, n, p, l) \ - ({ (n)->parent = (p); (n)->left = (l); }) - -#define RB_SET_P_L_C(t, n, p, l, c) \ - ({ (n)->parent = (p); (n)->left = (l); RB_SET_C_##c(t, n); }) - -#define RB_SET_P_R(t, n, p, r) \ - ({ (n)->parent = (p); (n)->right = (r); }) - -#define RB_SET_P_R_C(t, n, p, r, c) \ - ({ (n)->parent = (p); (n)->right = (r); RB_SET_C_##c(t, n); }) - -#define RB_SET_P_L_R(t, n, p, l, r) \ - ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); }) - -#define RB_SET_P_L_R_C(t, n, p, l, r, c)\ - ({ (n)->parent = (p); (n)->left = (l); (n)->right = (r); RB_SET_C_##c(t, n); }) - -#define RB_SET_ROOT(t, n) \ - RB_SET_L((t), &(t)->root, (n)) - -/******************************************************************************* - * RB-tree functions - ******************************************************************************/ - -/******************************************************************************* - * rb_first, rb_last - * - * Return pointer to first/last item in the tree - ******************************************************************************/ - -rb_idx_t rb_first(rb_tree_t *tree) -{ - rb_idx_t p_idx, t_idx; - - if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree)) - { - /* ...find left-most item in non-empty tree */ - while ((t_idx = RB_LEFT(tree, p_idx)) != RB_NULL(tree)) - p_idx = t_idx; - } - - return p_idx; -} - -rb_idx_t rb_last(rb_tree_t *tree) -{ - rb_idx_t p_idx, t_idx; - - if ((p_idx = RB_ROOT(tree)) != RB_NULL(tree)) - { - /* ...find right-most item in non-empty tree */ - while ((t_idx = RB_RIGHT(tree, p_idx)) != RB_NULL(tree)) - p_idx = t_idx; - } - - return p_idx; -} - -/******************************************************************************* - * rb_next, rb_prev - * - * Return next / previous in-order item in the tree - ******************************************************************************/ - -rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx) -{ - rb_idx_t p_idx, c_idx, t_idx; - - /* ...if we have any right children, process them */ - if ((c_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree)) - { - /* ...descent to the left-most node starting from right child */ - while ((t_idx = RB_LEFT(tree, c_idx)) != RB_NULL(tree)) - c_idx = t_idx; - return c_idx; - } - - /* ...no right children; ascend to our parent while we are right child */ - while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree)) - { - /* ...as soon as "n" is a left child, return "p" */ - if (n_idx == RB_RIGHT(tree, p_idx)) - n_idx = p_idx; - else - return p_idx; - } - - /* ...we were right-most child */ - return p_idx; -} - -rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx) -{ - rb_idx_t p_idx, c_idx, t_idx; - - /* ...if we have any left children, process them */ - if ((c_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree)) - { - /* ...descent to the right-most node starting from left child */ - while ((t_idx = RB_RIGHT(tree, c_idx)) != RB_NULL(tree)) - c_idx = t_idx; - return c_idx; - } - - /* ...no left children; ascend to our parent while we are left child */ - while ((p_idx = RB_PARENT(tree, n_idx)) != RB_NULL(tree)) - { - /* ...as soon as "n" is a right child, return "p" */ - if (n_idx == RB_LEFT(tree, p_idx)) - n_idx = p_idx; - else - return p_idx; - } - - /* ...we were left-most child */ - return p_idx; -} - -/******************************************************************************* - * rb_init - * - * Initialize rb-tree structure - ******************************************************************************/ - -void rb_init(rb_tree_t *tree) -{ - /* ...initialize sentinel node of the empty tree */ - RB_SET_P_L_R_C(tree, &tree->root, RB_NULL(tree), RB_NULL(tree), RB_NULL(tree), RB_BLK); -} - -/******************************************************************************* - * rb_insert - * - * Insert new item into RB-tree. Returns non-zero node index on success - ******************************************************************************/ - -/* ...internal tree balancing function */ -static void __rb_insert_balance(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx) -{ - rb_idx_t u_idx, g_idx, t_idx, cl_idx, cr_idx; - -rebalance: - - /*************************************************************************** - * Trivial case #1 - N (red) is a root - **************************************************************************/ - - if (p_idx == RB_NULL(tree)) - { - RB_SET_C(tree, n_idx, RB_BLK); - goto root; - } - - /*************************************************************************** - * Trivial case #2 - P is black - **************************************************************************/ - - if (RB_IS_BLACK(tree, p_idx)) - goto done; - - /*************************************************************************** - * Complex cases - P is red, N is red - **************************************************************************/ - - /* ...grandparent must exist and be black */ - g_idx = RB_PARENT(tree, p_idx); - if (p_idx == RB_LEFT(tree, g_idx)) - { - /* ...we are left grandchild; get uncle (if it exists) */ - u_idx = RB_RIGHT(tree, g_idx); - - /* ...if U is read, we have conditions of case #3 */ - if (!RB_IS_BLACK(tree, u_idx)) - goto case3; - - /* ...we will need grand-grand-parent later */ - t_idx = RB_PARENT(tree, g_idx); - - /* ...U is black/null; if we are LL grandchild, we have case #5 */ - if (n_idx == RB_LEFT(tree, p_idx)) - goto case5_ll; - - /* ...N is RL grandchild of G; case #4 */ - goto case4_rl; - } - else - { - /* ...we are right grandchild; get uncle (if it exists) */ - u_idx = RB_LEFT(tree, g_idx); - - /* ...if U is read, we have conditions of case #3 */ - if (!RB_IS_BLACK(tree, u_idx)) - goto case3; - - /* ...we will need grand-grand-parent later */ - t_idx = RB_PARENT(tree, g_idx); - - /* ...U is black/null; if we are RR grandchild, we have case #5 */ - if (n_idx == RB_RIGHT(tree, p_idx)) - goto case5_rr; - - /* ...N is LR grandchild of G; case #4 */ - goto case4_lr; - } - -case4_rl: - - /*************************************************************************** - * Case #4 - P is red, U is black, N is red RL grandchild of G. We will do - * two tree rotations - first the one described in case #4, second is the - * one described in case #5 (as have conditions for case #5(LL) with P and - * N changing roles - **************************************************************************/ - - cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx); - RB_SET_P_L_R_C(tree, n_idx, t_idx, p_idx, g_idx, RB_BLK); - RB_SET_P_R(tree, p_idx, n_idx, cl_idx); - RB_SET_P(tree, cl_idx, p_idx); - RB_SET_P_L_C(tree, g_idx, n_idx, cr_idx, RB_RED); - RB_SET_P(tree, cr_idx, g_idx); - - /* ...new root of subtree is N; adjust T pointer */ - goto case5_xx; - -case4_lr: - - /*************************************************************************** - * Case #4 - P is red, U is black, N is red LR grandchild of G. We will do - * two tree rotations - first the one described in case #4, second is the - * one described in case #5 (as have conditions for case #5(RR) with P and - * N changing roles - **************************************************************************/ - - cl_idx = RB_LEFT(tree, n_idx), cr_idx = RB_RIGHT(tree, n_idx); - RB_SET_P_L_R_C(tree, n_idx, t_idx, g_idx, p_idx, RB_BLK); - RB_SET_P_L(tree, p_idx, n_idx, cr_idx); - RB_SET_P(tree, cr_idx, p_idx); - RB_SET_P_R_C(tree, g_idx, n_idx, cl_idx, RB_RED); - RB_SET_P(tree, cl_idx, g_idx); - - /* ...new root of the subtree is N; adjust T pointer */ - goto case5_xx; - -case5_ll: - - /*************************************************************************** - * Case #5: N is LL grandchild of P; N and P red, G and U black - **************************************************************************/ - - cr_idx = RB_RIGHT(tree, p_idx); - RB_SET_P_L_C(tree, g_idx, p_idx, cr_idx, RB_RED); - RB_SET_P(tree, cr_idx, g_idx); - RB_SET_P_R_C(tree, p_idx, t_idx, g_idx, RB_BLK); - - /* ...new root of the subtree is P; relabel and adjust T pointer */ - n_idx = p_idx; - goto case5_xx; - -case5_rr: - - /*************************************************************************** - * Case #5: N is RR grandchild of P; N and P red, G and U black - **************************************************************************/ - - cl_idx = RB_LEFT(tree, p_idx); - RB_SET_P_R_C(tree, g_idx, p_idx, cl_idx, RB_RED); - RB_SET_P(tree, cl_idx, g_idx); - RB_SET_P_L_C(tree, p_idx, t_idx, g_idx, RB_BLK); - - /* ...new root of the subtree is P; relabel and adjust T pointer */ - n_idx = p_idx; - goto case5_xx; - -case5_xx: - - /* ...N is a (black) root of subtree; check if it is a root of tree as well */ - if (t_idx == RB_NULL(tree)) - goto root; - else if (g_idx == RB_LEFT(tree, t_idx)) - RB_SET_L(tree, t_idx, n_idx); - else - RB_SET_R(tree, t_idx, n_idx); - - goto done; - -case3: - - /*************************************************************************** - * Case #3 - P and U are red, G is black - **************************************************************************/ - - RB_SET_C(tree, p_idx, RB_BLK); - RB_SET_C(tree, u_idx, RB_BLK); - RB_SET_C(tree, g_idx, RB_RED); - - /* ...rebalance the tree for a G */ - n_idx = g_idx, p_idx = RB_PARENT(tree, g_idx); - goto rebalance; - -root: - /* ...adjust root pointer of the tree */ - RB_SET_ROOT(tree, n_idx); - -done: - /* ...tree is balanced */ - return; -} - -/* ...high-level API function */ -void rb_insert(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx) -{ - if (p_idx == RB_NULL(tree)) - { - /* ...set black root node */ - RB_SET_P_L_R_C(tree, n_idx, p_idx, p_idx, p_idx, RB_BLK); - - /* ...tree consists of the only root node; is balanced */ - RB_SET_ROOT(tree, n_idx); - } - else - { - /* ...create new node - set parent pointer and paint red */ - RB_SET_P_L_R_C(tree, n_idx, p_idx, RB_NULL(tree), RB_NULL(tree), RB_RED); - - /* ...and rebalance the tree */ - __rb_insert_balance(tree, n_idx, p_idx); - } -} - -/******************************************************************************* - * rb_delete - * - * Remove item from RB-key (by key). Returns zero on success - ******************************************************************************/ - -/* ...internal tree balancing function */ -static void __rb_delete_rebalance(rb_tree_t *tree, rb_idx_t p_idx) -{ - rb_idx_t n_idx, s_idx, sl_idx, sr_idx, g_idx, c_idx, cl_idx, cr_idx; - - /* ...initialize rebalancing procedure with null-child of P */ - n_idx = RB_NULL(tree); - -rebalance: - - /* ...save grand-parent pointer (may be null) */ - g_idx = RB_PARENT(tree, p_idx); - - /*************************************************************************** - * Check for complex cases - **************************************************************************/ - - if (n_idx == RB_LEFT(tree, p_idx)) - { - /* ...N is left child; get sibling (must exist) and its children */ - s_idx = RB_RIGHT(tree, p_idx); - sl_idx = RB_LEFT(tree, s_idx); - sr_idx = RB_RIGHT(tree, s_idx); - - /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */ - if (RB_IS_BLACK(tree, s_idx)) - goto test3_l; - else - goto case2_l; - } - else - { - /* ...N is right child; get sibling (must exist) and its children */ - s_idx = RB_LEFT(tree, p_idx); - sl_idx = RB_LEFT(tree, s_idx); - sr_idx = RB_RIGHT(tree, s_idx); - - /* ...if S is black, test for conditions 3,4,5,6; otherwise - case 2 */ - if (RB_IS_BLACK(tree, s_idx)) - goto test3_r; - else - goto case2_r; - } - -case2_l: - - /*************************************************************************** - * Case #2: N is a left child of P; S is red - **************************************************************************/ - - c_idx = sl_idx; - RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_BLK); - RB_SET_P_R_C(tree, p_idx, s_idx, c_idx, RB_RED); - RB_SET_P(tree, c_idx, p_idx); - - /* ...S is new root of subtree, Sl(C) is new sibling of N; update G */ - goto case2_x; - -case2_r: - - /*************************************************************************** - * Case #2: N is a right child of P; S is red - **************************************************************************/ - - c_idx = sr_idx; - RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_BLK); - RB_SET_P_L_C(tree, p_idx, s_idx, c_idx, RB_RED); - RB_SET_P(tree, c_idx, p_idx); - - /* ...S is new root of subtree, Sr(C) is new sibling of N; update G */ - goto case2_x; - -case2_x: - - /* ...check if S is becoming new (black) root of the tree */ - if (g_idx == RB_NULL(tree)) - RB_SET_ROOT(tree, s_idx); - else if (p_idx == RB_LEFT(tree, g_idx)) - RB_SET_L(tree, g_idx, s_idx); - else - RB_SET_R(tree, g_idx, s_idx); - - /* ...relabel new N's grandparent (now S) as G and new sibling (now C) as S */ - g_idx = s_idx, s_idx = c_idx; - sl_idx = RB_LEFT(tree, s_idx); - sr_idx = RB_RIGHT(tree, s_idx); - - /* ...N is still one of P's children; select proper side */ - if (n_idx == RB_LEFT(tree, p_idx)) - goto test3_l; - else - goto test3_r; - -test3_l: - - /*************************************************************************** - * Test for cases 3,4,5,6; P is any, S is black. N is left child of P - **************************************************************************/ - - if (!RB_IS_BLACK(tree, sr_idx)) - /* ...Sr is red, Sl of any color; conditions for case #6 are met */ - goto case6_l; - else if (!RB_IS_BLACK(tree, sl_idx)) - /* ...Sr is black and Sl is red; conditions for case #5 are met */ - goto case5_l; - else if (RB_IS_BLACK(tree, p_idx)) - /* ...Sl and Sr are of the same (black) color and P is black */ - goto case3; - else - /* ...Sl and Sr are of the same (black) color and P is red */ - goto case4; - -test3_r: - - /*************************************************************************** - * Test for cases 3,4,5,6; P is any, S is black. N is right child of P - **************************************************************************/ - - if (!RB_IS_BLACK(tree, sl_idx)) - /* ...Sl is red, Sr of any color; conditions for case #6 are met */ - goto case6_r; - else if (!RB_IS_BLACK(tree, sr_idx)) - /* ...Sl is black and Sr is red; conditions for case #5 are met */ - goto case5_r; - else if (RB_IS_BLACK(tree, p_idx)) - /* ...Sl and Sr are of the same (black) color and P is black */ - goto case3; - else - /* ...Sl and Sr are of the same (black) color and P is red */ - goto case4; - -case3: - - /*************************************************************************** - * Case #3: N, P, S, Sl and Sr are black - **************************************************************************/ - - RB_SET_C(tree, s_idx, RB_RED); - - /* ...and rebalance the tree for parent */ - n_idx = p_idx, p_idx = RB_PARENT(tree, p_idx); - - if (p_idx == RB_NULL(tree)) - goto done; - else - goto rebalance; - -case4: - - /*************************************************************************** - * Case #4: N and S are black, P is red, Sl and Sr are all black - **************************************************************************/ - - RB_SET_C(tree, s_idx, RB_RED); - RB_SET_C(tree, p_idx, RB_BLK); - - goto done; - -case5_l: - /*************************************************************************** - * Case #5: S is black, Sl is red, Sr is black; N is left child of P. We - * have two subsequent transformations (case #5 and case #6) combined - **************************************************************************/ - - cl_idx = RB_LEFT(tree, sl_idx); - cr_idx = RB_RIGHT(tree, sl_idx); - - if (RB_IS_BLACK(tree, p_idx)) - RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_BLK); - else - RB_SET_P_L_R_C(tree, sl_idx, g_idx, p_idx, s_idx, RB_RED); - - RB_SET_P_R_C(tree, p_idx, sl_idx, cl_idx, RB_BLK); - RB_SET_P(tree, cl_idx, p_idx); - RB_SET_P_L(tree, s_idx, sl_idx, cr_idx); - RB_SET_P(tree, cr_idx, s_idx); - - /* ...relabel new root as S (for common processing in case #6) */ - s_idx = sl_idx; - goto case6_x; - -case5_r: - /*************************************************************************** - * Case #5: S is black, Sr is red, Sl is black; N is right child of P. We - * have two subsequent transformations (case #5 and case #6) combined - **************************************************************************/ - - cl_idx = RB_LEFT(tree, sr_idx); - cr_idx = RB_RIGHT(tree, sr_idx); - - if (RB_IS_BLACK(tree, p_idx)) - RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_BLK); - else - RB_SET_P_L_R_C(tree, sr_idx, g_idx, s_idx, p_idx, RB_RED); - - RB_SET_P_L_C(tree, p_idx, sr_idx, cr_idx, RB_BLK); - RB_SET_P(tree, cr_idx, p_idx); - RB_SET_P_R(tree, s_idx, sr_idx, cl_idx); - RB_SET_P(tree, cl_idx, s_idx); - - /* ...relabel new root as S (for common processing in case #6) */ - s_idx = sr_idx; - goto case6_x; - -case6_l: - - /*************************************************************************** - * Case #6: S is black, N is the left child of P, Sr is red - **************************************************************************/ - - if (RB_IS_BLACK(tree, p_idx)) - RB_SET_P_L(tree, s_idx, g_idx, p_idx); - else - RB_SET_P_L_C(tree, s_idx, g_idx, p_idx, RB_RED); - - RB_SET_P_R_C(tree, p_idx, s_idx, sl_idx, RB_BLK); - RB_SET_P(tree, sl_idx, p_idx); - RB_SET_C(tree, sr_idx, RB_BLK); - - /* ...S is a new root of subtree; update G */ - goto case6_x; - -case6_r: - - /*************************************************************************** - * Case #6: S is black, N is the right child of P, Sl is red - **************************************************************************/ - - if (RB_IS_BLACK(tree, p_idx)) - RB_SET_P_R(tree, s_idx, g_idx, p_idx); - else - RB_SET_P_R_C(tree, s_idx, g_idx, p_idx, RB_RED); - - RB_SET_P_L_C(tree, p_idx, s_idx, sr_idx, RB_BLK); - RB_SET_P(tree, sr_idx, p_idx); - RB_SET_C(tree, sl_idx, RB_BLK); - - /* ...S is a new root of subtree; update G */ - goto case6_x; - -case6_x: - - /* ...S is a new root of subtree; update G's pointer */ - if (g_idx == RB_NULL(tree)) - RB_SET_ROOT(tree, s_idx); - else if (p_idx == RB_LEFT(tree, g_idx)) - RB_SET_L(tree, g_idx, s_idx); - else - RB_SET_R(tree, g_idx, s_idx); - - /* ...tree is balanced; pass through */ - -done: - - return; -} - -/* ...high-level API function */ -rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx) -{ - rb_idx_t p_idx, t_idx, m_idx, c_idx, l_idx, r_idx, k_idx; - u32 color; - - /* ...save parent of element N that we are going to remove */ - p_idx = RB_PARENT(tree, n_idx); - - /* ...get in-order predecessor/successor of n_idx, if possible */ - if ((m_idx = RB_LEFT(tree, n_idx)) != RB_NULL(tree)) - { - while ((t_idx = RB_RIGHT(tree, m_idx)) != RB_NULL(tree)) - m_idx = t_idx; - - /* ...set the child of in-order predecessor (may be null) */ - c_idx = RB_LEFT(tree, m_idx); - } - else if ((m_idx = RB_RIGHT(tree, n_idx)) != RB_NULL(tree)) - { - while ((t_idx = RB_LEFT(tree, m_idx)) != RB_NULL(tree)) - m_idx = t_idx; - - /* ...set the child of in-order successor (may be null) */ - c_idx = RB_RIGHT(tree, m_idx); - } - else if (p_idx == RB_NULL(tree)) - { - /* ...tree consists of the only root node N that we are removing */ - RB_SET_ROOT(tree, m_idx); - - /* ..return tree null pointer */ - return m_idx; - } - else - { - /* ...N is a (non-root) leaf node; M and C are null */ - c_idx = m_idx; - - /* ...save the color of the node we are going to delete */ - color = RB_COLOR(tree, n_idx); - - /* ...set new parent of C */ - t_idx = p_idx; - - /* ...pointer that we return as in-order predecessor/successor */ - k_idx = p_idx; - - /* ...adjust only parent of the N */ - goto adjust_parent; - } - - /* ...node that replaces our component is M */ - k_idx = m_idx; - - /*************************************************************************** - * Replace node N with M - **************************************************************************/ - - /* ...save original color of M (the node that we are deleting) */ - color = RB_COLOR(tree, m_idx); - - /* ...put M in place of N; get N's children */ - l_idx = RB_LEFT(tree, n_idx); - r_idx = RB_RIGHT(tree, n_idx); - - /* ...see if M is a child of N */ - if ((t_idx = RB_PARENT(tree, m_idx)) != n_idx) - { - /* ...C becomes left or right child of M's original parent T */ - if (c_idx == RB_LEFT(tree, m_idx)) - RB_SET_R(tree, t_idx, c_idx); - else - RB_SET_L(tree, t_idx, c_idx); - - /* ...adjust C parent pointer (okay if it's null) */ - RB_SET_P(tree, c_idx, t_idx); - - /* ...set all pointers of node M (it replaces N) */ - RB_SET_P_L_R(tree, m_idx, p_idx, l_idx, r_idx); - RB_SET_P(tree, l_idx, m_idx); - RB_SET_P(tree, r_idx, m_idx); - } - else - { - /* ...M is a left or right child of N; it gets to N's place, and C remains intact */ - if (m_idx == l_idx) - { - RB_SET_P_R(tree, m_idx, p_idx, r_idx); - RB_SET_P(tree, r_idx, m_idx); - } - else - { - RB_SET_P_L(tree, m_idx, p_idx, l_idx); - RB_SET_P(tree, l_idx, m_idx); - } - - /* ...parent of C is still M (we label it as T) */ - t_idx = m_idx; - } - - /* ...paint M in the same color as N which it replaced */ - if (RB_IS_BLACK(tree, n_idx)) - RB_SET_C(tree, m_idx, RB_BLK); - else - RB_SET_C(tree, m_idx, RB_RED); - -adjust_parent: - - /* ...adjust N's parent node to point to M */ - if (p_idx == RB_NULL(tree)) - RB_SET_ROOT(tree, m_idx); - else if (n_idx == RB_LEFT(tree, p_idx)) - RB_SET_L(tree, p_idx, m_idx); - else - RB_SET_R(tree, p_idx, m_idx); - - /* ...check for a color of deleted item (M or N in case it is a leaf) */ - if (color == RB_BLK) - { - if (c_idx == RB_NULL(tree)) - /* ...rebalance the tree for a T node (it is never a null)*/ - __rb_delete_rebalance(tree, t_idx); - else - /* ...C node exists and is necessarily red; repaint it black */ - RB_SET_C(tree, c_idx, RB_BLK); - } - - /* ....return the node K which replaced deleted node N */ - return k_idx; -} - -/******************************************************************************* - * rb_replace - * - * Replace the node with the same-key node - adjust tree pointers - ******************************************************************************/ - -void rb_replace(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t t_idx) -{ - rb_idx_t p_idx, l_idx, r_idx; - - /* ...get node pointers */ - p_idx = RB_PARENT(tree, n_idx), l_idx = RB_LEFT(tree, n_idx), r_idx = RB_RIGHT(tree, n_idx); - - /* ...set new node pointers */ - RB_SET_P_L_R(tree, t_idx, p_idx, l_idx, r_idx); - - /* ...set node color */ - if (RB_IS_BLACK(tree, n_idx)) - RB_SET_C(tree, t_idx, RB_BLK); - else - RB_SET_C(tree, t_idx, RB_RED); - - /* ...update parent node */ - if (p_idx == RB_NULL(tree)) - RB_SET_ROOT(tree, t_idx); - else if (n_idx == RB_LEFT(tree, p_idx)) - RB_SET_L(tree, p_idx, t_idx); - else - RB_SET_R(tree, p_idx, t_idx); - - /* ...update children's parent node (okay if null) */ - RB_SET_P(tree, l_idx, t_idx), RB_SET_P(tree, r_idx, t_idx); -} |