Lines Matching +full:parent +full:- +full:child
1 /* SPDX-License-Identifier: GPL-2.0+ */
18 * Please note - only struct rb_augment_callbacks and the prototypes for
37 __rb_insert_augmented(node, root, augment->rotate); in rb_insert_augmented()
48 if (node->rbaugmented == augmented) \
50 node->rbaugmented = augmented; \
51 rb = rb_parent(&node->rbfield); \
59 new->rbaugmented = old->rbaugmented; \
66 new->rbaugmented = old->rbaugmented; \
67 old->rbaugmented = rbcompute(old); \
82 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
83 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
84 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
88 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; in rb_set_parent()
94 rb->__rb_parent_color = (unsigned long)p | color; in rb_set_parent_color()
99 struct rb_node *parent, struct rb_root *root) in __rb_change_child() argument
101 if (parent) { in __rb_change_child()
102 if (parent->rb_left == old) in __rb_change_child()
103 parent->rb_left = new; in __rb_change_child()
105 parent->rb_right = new; in __rb_change_child()
107 root->rb_node = new; in __rb_change_child()
110 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
117 struct rb_node *child = node->rb_right, *tmp = node->rb_left; in __rb_erase_augmented() local
118 struct rb_node *parent, *rebalance; in __rb_erase_augmented() local
123 * Case 1: node to erase has no more than 1 child (easy!) in __rb_erase_augmented()
125 * Note that if there is one child it must be red due to 5) in __rb_erase_augmented()
129 pc = node->__rb_parent_color; in __rb_erase_augmented()
130 parent = __rb_parent(pc); in __rb_erase_augmented()
131 __rb_change_child(node, child, parent, root); in __rb_erase_augmented()
132 if (child) { in __rb_erase_augmented()
133 child->__rb_parent_color = pc; in __rb_erase_augmented()
136 rebalance = __rb_is_black(pc) ? parent : NULL; in __rb_erase_augmented()
137 tmp = parent; in __rb_erase_augmented()
138 } else if (!child) { in __rb_erase_augmented()
139 /* Still case 1, but this time the child is node->rb_left */ in __rb_erase_augmented()
140 tmp->__rb_parent_color = pc = node->__rb_parent_color; in __rb_erase_augmented()
141 parent = __rb_parent(pc); in __rb_erase_augmented()
142 __rb_change_child(node, tmp, parent, root); in __rb_erase_augmented()
144 tmp = parent; in __rb_erase_augmented()
146 struct rb_node *successor = child, *child2; in __rb_erase_augmented()
147 tmp = child->rb_left; in __rb_erase_augmented()
150 * Case 2: node's successor is its right child in __rb_erase_augmented()
154 * (x) (s) -> (x) (c) in __rb_erase_augmented()
158 parent = successor; in __rb_erase_augmented()
159 child2 = successor->rb_right; in __rb_erase_augmented()
160 augment->copy(node, successor); in __rb_erase_augmented()
164 * node's right child subtree in __rb_erase_augmented()
168 * (x) (y) -> (x) (y) in __rb_erase_augmented()
177 parent = successor; in __rb_erase_augmented()
179 tmp = tmp->rb_left; in __rb_erase_augmented()
181 parent->rb_left = child2 = successor->rb_right; in __rb_erase_augmented()
182 successor->rb_right = child; in __rb_erase_augmented()
183 rb_set_parent(child, successor); in __rb_erase_augmented()
184 augment->copy(node, successor); in __rb_erase_augmented()
185 augment->propagate(parent, successor); in __rb_erase_augmented()
188 successor->rb_left = tmp = node->rb_left; in __rb_erase_augmented()
191 pc = node->__rb_parent_color; in __rb_erase_augmented()
195 successor->__rb_parent_color = pc; in __rb_erase_augmented()
196 rb_set_parent_color(child2, parent, RB_BLACK); in __rb_erase_augmented()
199 unsigned long pc2 = successor->__rb_parent_color; in __rb_erase_augmented()
200 successor->__rb_parent_color = pc; in __rb_erase_augmented()
201 rebalance = __rb_is_black(pc2) ? parent : NULL; in __rb_erase_augmented()
206 augment->propagate(tmp, NULL); in __rb_erase_augmented()
216 __rb_erase_color(rebalance, root, augment->rotate); in rb_erase_augmented()