Lines Matching full:parent
54 RBTREE_NULL, /* Parent. */
113 right->left->parent = node; in rbtree_rotate_left()
115 right->parent = node->parent; in rbtree_rotate_left()
117 if (node->parent != RBTREE_NULL) { in rbtree_rotate_left()
118 if (node == node->parent->left) { in rbtree_rotate_left()
119 node->parent->left = right; in rbtree_rotate_left()
121 node->parent->right = right; in rbtree_rotate_left()
127 node->parent = right; in rbtree_rotate_left()
140 left->right->parent = node; in rbtree_rotate_right()
142 left->parent = node->parent; in rbtree_rotate_right()
144 if (node->parent != RBTREE_NULL) { in rbtree_rotate_right()
145 if (node == node->parent->right) { in rbtree_rotate_right()
146 node->parent->right = left; in rbtree_rotate_right()
148 node->parent->left = left; in rbtree_rotate_right()
154 node->parent = left; in rbtree_rotate_right()
163 while (node != rbtree->root && node->parent->color == RED) { in rbtree_insert_fixup()
164 /* If our parent is left child of our grandparent... */ in rbtree_insert_fixup()
165 if (node->parent == node->parent->parent->left) { in rbtree_insert_fixup()
166 uncle = node->parent->parent->right; in rbtree_insert_fixup()
170 /* Paint the parent and the uncle black... */ in rbtree_insert_fixup()
171 node->parent->color = BLACK; in rbtree_insert_fixup()
175 node->parent->parent->color = RED; in rbtree_insert_fixup()
178 node = node->parent->parent; in rbtree_insert_fixup()
181 if (node == node->parent->right) { in rbtree_insert_fixup()
182 node = node->parent; in rbtree_insert_fixup()
186 node->parent->color = BLACK; in rbtree_insert_fixup()
187 node->parent->parent->color = RED; in rbtree_insert_fixup()
188 rbtree_rotate_right(rbtree, node->parent->parent); in rbtree_insert_fixup()
191 uncle = node->parent->parent->left; in rbtree_insert_fixup()
195 /* Paint the parent and the uncle black... */ in rbtree_insert_fixup()
196 node->parent->color = BLACK; in rbtree_insert_fixup()
200 node->parent->parent->color = RED; in rbtree_insert_fixup()
203 node = node->parent->parent; in rbtree_insert_fixup()
206 if (node == node->parent->left) { in rbtree_insert_fixup()
207 node = node->parent; in rbtree_insert_fixup()
211 node->parent->color = BLACK; in rbtree_insert_fixup()
212 node->parent->parent->color = RED; in rbtree_insert_fixup()
213 rbtree_rotate_left(rbtree, node->parent->parent); in rbtree_insert_fixup()
235 rbnode_type *parent = RBTREE_NULL; in rbtree_insert() local
238 /* Lets find the new parent... */ in rbtree_insert()
244 parent = node; in rbtree_insert()
254 data->parent = parent; in rbtree_insert()
260 if (parent != RBTREE_NULL) { in rbtree_insert()
262 parent->left = data; in rbtree_insert()
264 parent->right = data; in rbtree_insert()
304 /** Update parent pointers of child trees of 'parent' */
305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent, in change_parent_ptr() argument
308 if(parent == RBTREE_NULL) in change_parent_ptr()
314 log_assert(parent->left == old || parent->right == old in change_parent_ptr()
315 || parent->left == new || parent->right == new); in change_parent_ptr()
316 if(parent->left == old) parent->left = new; in change_parent_ptr()
317 if(parent->right == old) parent->right = new; in change_parent_ptr()
319 /** Update parent pointer of a node 'child' */
324 log_assert(child->parent == old || child->parent == new); in change_child_ptr()
325 if(child->parent == old) child->parent = new; in change_child_ptr()
346 * readjust the pointers left,right,parent */ in rbtree_delete()
352 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); in rbtree_delete()
354 change_parent_ptr(rbtree, smright->parent, smright, to_delete); in rbtree_delete()
356 /* swap parent pointers in children of smright/to_delete */ in rbtree_delete()
368 smright->parent = smright; in rbtree_delete()
372 swap_np(&to_delete->parent, &smright->parent); in rbtree_delete()
384 change_parent_ptr(rbtree, to_delete->parent, to_delete, child); in rbtree_delete()
385 change_child_ptr(child, to_delete, to_delete->parent); in rbtree_delete()
396 else rbtree_delete_fixup(rbtree, child, to_delete->parent); in rbtree_delete()
399 to_delete->parent = RBTREE_NULL; in rbtree_delete()
420 /* removed parent==black from root, every path, so ok */ in rbtree_delete_fixup()
445 child_parent = child_parent->parent; in rbtree_delete_fixup()
573 rbnode_type *parent; in rbtree_next() local
579 parent = node->parent; in rbtree_next()
580 while (parent != RBTREE_NULL && node == parent->right) { in rbtree_next()
581 node = parent; in rbtree_next()
582 parent = parent->parent; in rbtree_next()
584 node = parent; in rbtree_next()
592 rbnode_type *parent; in rbtree_previous() local
598 parent = node->parent; in rbtree_previous()
599 while (parent != RBTREE_NULL && node == parent->left) { in rbtree_previous()
600 node = parent; in rbtree_previous()
601 parent = parent->parent; in rbtree_previous()
603 node = parent; in rbtree_previous()