Lines Matching full:parent
56 LDNS_RBTREE_NULL, /* Parent. */
121 right->left->parent = node; in ldns_rbtree_rotate_left()
123 right->parent = node->parent; in ldns_rbtree_rotate_left()
125 if (node->parent != LDNS_RBTREE_NULL) { in ldns_rbtree_rotate_left()
126 if (node == node->parent->left) { in ldns_rbtree_rotate_left()
127 node->parent->left = right; in ldns_rbtree_rotate_left()
129 node->parent->right = right; in ldns_rbtree_rotate_left()
135 node->parent = right; in ldns_rbtree_rotate_left()
148 left->right->parent = node; in ldns_rbtree_rotate_right()
150 left->parent = node->parent; in ldns_rbtree_rotate_right()
152 if (node->parent != LDNS_RBTREE_NULL) { in ldns_rbtree_rotate_right()
153 if (node == node->parent->right) { in ldns_rbtree_rotate_right()
154 node->parent->right = left; in ldns_rbtree_rotate_right()
156 node->parent->left = left; in ldns_rbtree_rotate_right()
162 node->parent = left; in ldns_rbtree_rotate_right()
171 while (node != rbtree->root && node->parent->color == RED) { in ldns_rbtree_insert_fixup()
172 /* If our parent is left child of our grandparent... */ in ldns_rbtree_insert_fixup()
173 if (node->parent == node->parent->parent->left) { in ldns_rbtree_insert_fixup()
174 uncle = node->parent->parent->right; in ldns_rbtree_insert_fixup()
178 /* Paint the parent and the uncle black... */ in ldns_rbtree_insert_fixup()
179 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
183 node->parent->parent->color = RED; in ldns_rbtree_insert_fixup()
186 node = node->parent->parent; in ldns_rbtree_insert_fixup()
189 if (node == node->parent->right) { in ldns_rbtree_insert_fixup()
190 node = node->parent; in ldns_rbtree_insert_fixup()
194 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
195 node->parent->parent->color = RED; in ldns_rbtree_insert_fixup()
196 ldns_rbtree_rotate_right(rbtree, node->parent->parent); in ldns_rbtree_insert_fixup()
199 uncle = node->parent->parent->left; in ldns_rbtree_insert_fixup()
203 /* Paint the parent and the uncle black... */ in ldns_rbtree_insert_fixup()
204 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
208 node->parent->parent->color = RED; in ldns_rbtree_insert_fixup()
211 node = node->parent->parent; in ldns_rbtree_insert_fixup()
214 if (node == node->parent->left) { in ldns_rbtree_insert_fixup()
215 node = node->parent; in ldns_rbtree_insert_fixup()
219 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
220 node->parent->parent->color = RED; in ldns_rbtree_insert_fixup()
221 ldns_rbtree_rotate_left(rbtree, node->parent->parent); in ldns_rbtree_insert_fixup()
249 ldns_rbnode_t *parent = LDNS_RBTREE_NULL; in ldns_rbtree_insert() local
251 /* Lets find the new parent... */ in ldns_rbtree_insert()
257 parent = node; in ldns_rbtree_insert()
267 data->parent = parent; in ldns_rbtree_insert()
273 if (parent != LDNS_RBTREE_NULL) { in ldns_rbtree_insert()
275 parent->left = data; in ldns_rbtree_insert()
277 parent->right = data; in ldns_rbtree_insert()
317 /** Update parent pointers of child trees of 'parent' */
318 static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldn… in change_parent_ptr() argument
320 if(parent == LDNS_RBTREE_NULL) in change_parent_ptr()
325 if(parent->left == old) parent->left = new; in change_parent_ptr()
326 if(parent->right == old) parent->right = new; in change_parent_ptr()
328 /** Update parent pointer of a node 'child' */
332 if(child->parent == old) child->parent = new; in change_child_ptr()
354 * readjust the pointers left,right,parent */ in ldns_rbtree_delete()
360 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); in ldns_rbtree_delete()
362 change_parent_ptr(rbtree, smright->parent, smright, to_delete); in ldns_rbtree_delete()
364 /* swap parent pointers in children of smright/to_delete */ in ldns_rbtree_delete()
376 smright->parent = smright; in ldns_rbtree_delete()
380 swap_np(&to_delete->parent, &smright->parent); in ldns_rbtree_delete()
391 change_parent_ptr(rbtree, to_delete->parent, to_delete, child); in ldns_rbtree_delete()
392 change_child_ptr(child, to_delete, to_delete->parent); in ldns_rbtree_delete()
403 else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent); in ldns_rbtree_delete()
406 to_delete->parent = LDNS_RBTREE_NULL; in ldns_rbtree_delete()
426 /* removed parent==black from root, every path, so ok */ in ldns_rbtree_delete_fixup()
451 child_parent = child_parent->parent; in ldns_rbtree_delete_fixup()
576 ldns_rbnode_t *parent; in ldns_rbtree_next() local
584 parent = node->parent; in ldns_rbtree_next()
585 while (parent != LDNS_RBTREE_NULL && node == parent->right) { in ldns_rbtree_next()
586 node = parent; in ldns_rbtree_next()
587 parent = parent->parent; in ldns_rbtree_next()
589 node = parent; in ldns_rbtree_next()
597 ldns_rbnode_t *parent; in ldns_rbtree_previous() local
605 parent = node->parent; in ldns_rbtree_previous()
606 while (parent != LDNS_RBTREE_NULL && node == parent->left) { in ldns_rbtree_previous()
607 node = parent; in ldns_rbtree_previous()
608 parent = parent->parent; in ldns_rbtree_previous()
610 node = parent; in ldns_rbtree_previous()