Lines Matching +full:child +full:- +full:node
2 * rbtree.c -- generic red black tree
6 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
49 /** Node colour black */
51 /** Node colour red */
54 /** the NULL node, global alloc */
65 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
67 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
68 /** Fixup node colours when insert happened */
69 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
70 /** Fixup node colours when delete happened */
71 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* ch…
100 rbtree->root = LDNS_RBTREE_NULL; in ldns_rbtree_init()
101 rbtree->count = 0; in ldns_rbtree_init()
102 rbtree->cmp = cmpf; in ldns_rbtree_init()
112 * Rotates the node to the left.
116 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) in ldns_rbtree_rotate_left() argument
118 ldns_rbnode_t *right = node->right; in ldns_rbtree_rotate_left()
119 node->right = right->left; in ldns_rbtree_rotate_left()
120 if (right->left != LDNS_RBTREE_NULL) in ldns_rbtree_rotate_left()
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()
132 rbtree->root = right; in ldns_rbtree_rotate_left()
134 right->left = node; in ldns_rbtree_rotate_left()
135 node->parent = right; in ldns_rbtree_rotate_left()
139 * Rotates the node to the right.
143 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) in ldns_rbtree_rotate_right() argument
145 ldns_rbnode_t *left = node->left; in ldns_rbtree_rotate_right()
146 node->left = left->right; in ldns_rbtree_rotate_right()
147 if (left->right != LDNS_RBTREE_NULL) in ldns_rbtree_rotate_right()
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()
159 rbtree->root = left; in ldns_rbtree_rotate_right()
161 left->right = node; in ldns_rbtree_rotate_right()
162 node->parent = left; in ldns_rbtree_rotate_right()
166 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node) in ldns_rbtree_insert_fixup() argument
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()
177 if (uncle->color == RED) { in ldns_rbtree_insert_fixup()
179 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
180 uncle->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()
188 /* Are we the right child? */ 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()
191 ldns_rbtree_rotate_left(rbtree, node); in ldns_rbtree_insert_fixup()
193 /* Now we're the left child, repaint and rotate... */ 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()
202 if (uncle->color == RED) { in ldns_rbtree_insert_fixup()
204 node->parent->color = BLACK; in ldns_rbtree_insert_fixup()
205 uncle->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()
213 /* Are we the right child? */ 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()
216 ldns_rbtree_rotate_right(rbtree, node); in ldns_rbtree_insert_fixup()
218 /* Now we're the right child, repaint and rotate... */ 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()
225 rbtree->root->color = BLACK; in ldns_rbtree_insert_fixup()
236 * Inserts a node into a red black tree.
238 * Returns NULL on failure or the pointer to the newly added node
248 ldns_rbnode_t *node = rbtree->root; in ldns_rbtree_insert() local
252 while (node != LDNS_RBTREE_NULL) { in ldns_rbtree_insert()
254 if ((r = rbtree->cmp(data->key, node->key)) == 0) { in ldns_rbtree_insert()
257 parent = node; in ldns_rbtree_insert()
260 node = node->left; in ldns_rbtree_insert()
262 node = node->right; in ldns_rbtree_insert()
266 /* Initialize the new node */ in ldns_rbtree_insert()
267 data->parent = parent; in ldns_rbtree_insert()
268 data->left = data->right = LDNS_RBTREE_NULL; in ldns_rbtree_insert()
269 data->color = RED; in ldns_rbtree_insert()
270 rbtree->count++; in ldns_rbtree_insert()
275 parent->left = data; in ldns_rbtree_insert()
277 parent->right = data; in ldns_rbtree_insert()
280 rbtree->root = data; in ldns_rbtree_insert()
283 /* Fix up the red-black properties... */ in ldns_rbtree_insert()
296 ldns_rbnode_t *node; in ldns_rbtree_search() local
298 if (ldns_rbtree_find_less_equal(rbtree, key, &node)) { in ldns_rbtree_search()
299 return node; in ldns_rbtree_search()
305 /** helpers for delete: swap node colours */
311 /** helpers for delete: swap node pointers */
317 /** Update parent pointers of child trees of 'parent' */
322 if(rbtree->root == old) rbtree->root = new; 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' */
329 static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new) in change_child_ptr() argument
331 if(child == LDNS_RBTREE_NULL) return; in change_child_ptr()
332 if(child->parent == old) child->parent = new; in change_child_ptr()
339 ldns_rbnode_t *child; in ldns_rbtree_delete() local
341 rbtree->count--; in ldns_rbtree_delete()
343 /* make sure we have at most one non-leaf child */ in ldns_rbtree_delete()
344 if(to_delete->left != LDNS_RBTREE_NULL && in ldns_rbtree_delete()
345 to_delete->right != LDNS_RBTREE_NULL) in ldns_rbtree_delete()
348 ldns_rbnode_t *smright = to_delete->right; in ldns_rbtree_delete()
349 while(smright->left != LDNS_RBTREE_NULL) in ldns_rbtree_delete()
350 smright = smright->left; in ldns_rbtree_delete()
356 /* swap colors - colors are tied to the position in the tree */ in ldns_rbtree_delete()
357 swap_int8(&to_delete->color, &smright->color); in ldns_rbtree_delete()
359 /* swap child pointers in parents of smright/to_delete */ in ldns_rbtree_delete()
360 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); in ldns_rbtree_delete()
361 if(to_delete->right != smright) in ldns_rbtree_delete()
362 change_parent_ptr(rbtree, smright->parent, smright, to_delete); in ldns_rbtree_delete()
365 change_child_ptr(smright->left, smright, to_delete); in ldns_rbtree_delete()
366 change_child_ptr(smright->left, smright, to_delete); in ldns_rbtree_delete()
367 change_child_ptr(smright->right, smright, to_delete); in ldns_rbtree_delete()
368 change_child_ptr(smright->right, smright, to_delete); in ldns_rbtree_delete()
369 change_child_ptr(to_delete->left, to_delete, smright); in ldns_rbtree_delete()
370 if(to_delete->right != smright) in ldns_rbtree_delete()
371 change_child_ptr(to_delete->right, to_delete, smright); in ldns_rbtree_delete()
372 if(to_delete->right == smright) in ldns_rbtree_delete()
375 to_delete->right = 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()
381 swap_np(&to_delete->left, &smright->left); in ldns_rbtree_delete()
382 swap_np(&to_delete->right, &smright->right); in ldns_rbtree_delete()
387 if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left; in ldns_rbtree_delete()
388 else child = to_delete->right; in ldns_rbtree_delete()
390 /* unlink to_delete from the tree, replace to_delete with child */ 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()
394 if(to_delete->color == RED) in ldns_rbtree_delete()
396 /* if node is red then the child (black) can be swapped in */ in ldns_rbtree_delete()
398 else if(child->color == RED) in ldns_rbtree_delete()
400 /* change child to BLACK, removing a RED node is no problem */ in ldns_rbtree_delete()
401 if(child!=LDNS_RBTREE_NULL) child->color = BLACK; 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()
407 to_delete->left = LDNS_RBTREE_NULL; in ldns_rbtree_delete()
408 to_delete->right = LDNS_RBTREE_NULL; in ldns_rbtree_delete()
409 to_delete->color = BLACK; in ldns_rbtree_delete()
413 static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* ch… in ldns_rbtree_delete_fixup() argument
418 /* determine sibling to the node that is one-black short */ in ldns_rbtree_delete_fixup()
419 if(child_parent->right == child) sibling = child_parent->left; in ldns_rbtree_delete_fixup()
420 else sibling = child_parent->right; in ldns_rbtree_delete_fixup()
430 if(sibling->color == RED) in ldns_rbtree_delete_fixup()
432 child_parent->color = RED; in ldns_rbtree_delete_fixup()
433 sibling->color = BLACK; in ldns_rbtree_delete_fixup()
434 if(child_parent->right == child) in ldns_rbtree_delete_fixup()
438 if(child_parent->right == child) sibling = child_parent->left; in ldns_rbtree_delete_fixup()
439 else sibling = child_parent->right; in ldns_rbtree_delete_fixup()
442 if(child_parent->color == BLACK in ldns_rbtree_delete_fixup()
443 && sibling->color == BLACK in ldns_rbtree_delete_fixup()
444 && sibling->left->color == BLACK in ldns_rbtree_delete_fixup()
445 && sibling->right->color == BLACK) in ldns_rbtree_delete_fixup()
448 sibling->color = RED; in ldns_rbtree_delete_fixup()
450 child = child_parent; in ldns_rbtree_delete_fixup()
451 child_parent = child_parent->parent; in ldns_rbtree_delete_fixup()
453 if(child_parent->right == child) sibling = child_parent->left; in ldns_rbtree_delete_fixup()
454 else sibling = child_parent->right; in ldns_rbtree_delete_fixup()
459 if(child_parent->color == RED in ldns_rbtree_delete_fixup()
460 && sibling->color == BLACK in ldns_rbtree_delete_fixup()
461 && sibling->left->color == BLACK in ldns_rbtree_delete_fixup()
462 && sibling->right->color == BLACK) in ldns_rbtree_delete_fixup()
466 sibling->color = RED; in ldns_rbtree_delete_fixup()
467 child_parent->color = BLACK; in ldns_rbtree_delete_fixup()
471 /* get a new sibling, by rotating at sibling. See which child in ldns_rbtree_delete_fixup()
473 if(child_parent->right == child in ldns_rbtree_delete_fixup()
474 && sibling->color == BLACK in ldns_rbtree_delete_fixup()
475 && sibling->right->color == RED in ldns_rbtree_delete_fixup()
476 && sibling->left->color == BLACK) in ldns_rbtree_delete_fixup()
478 sibling->color = RED; in ldns_rbtree_delete_fixup()
479 sibling->right->color = BLACK; in ldns_rbtree_delete_fixup()
482 if(child_parent->right == child) sibling = child_parent->left; in ldns_rbtree_delete_fixup()
483 else sibling = child_parent->right; in ldns_rbtree_delete_fixup()
485 else if(child_parent->left == child in ldns_rbtree_delete_fixup()
486 && sibling->color == BLACK in ldns_rbtree_delete_fixup()
487 && sibling->left->color == RED in ldns_rbtree_delete_fixup()
488 && sibling->right->color == BLACK) in ldns_rbtree_delete_fixup()
490 sibling->color = RED; in ldns_rbtree_delete_fixup()
491 sibling->left->color = BLACK; in ldns_rbtree_delete_fixup()
494 if(child_parent->right == child) sibling = child_parent->left; in ldns_rbtree_delete_fixup()
495 else sibling = child_parent->right; in ldns_rbtree_delete_fixup()
498 /* now we have a black sibling with a red child. rotate and exchange colors. */ in ldns_rbtree_delete_fixup()
499 sibling->color = child_parent->color; in ldns_rbtree_delete_fixup()
500 child_parent->color = BLACK; in ldns_rbtree_delete_fixup()
501 if(child_parent->right == child) in ldns_rbtree_delete_fixup()
503 sibling->left->color = BLACK; in ldns_rbtree_delete_fixup()
508 sibling->right->color = BLACK; in ldns_rbtree_delete_fixup()
517 ldns_rbnode_t *node; in ldns_rbtree_find_less_equal() local
520 node = rbtree->root; in ldns_rbtree_find_less_equal()
525 while (node != LDNS_RBTREE_NULL) { in ldns_rbtree_find_less_equal()
526 r = rbtree->cmp(key, node->key); in ldns_rbtree_find_less_equal()
529 *result = node; in ldns_rbtree_find_less_equal()
533 node = node->left; in ldns_rbtree_find_less_equal()
536 *result = node; in ldns_rbtree_find_less_equal()
537 node = node->right; in ldns_rbtree_find_less_equal()
550 ldns_rbnode_t *node = rbtree->root; in ldns_rbtree_first() local
552 if (rbtree->root != LDNS_RBTREE_NULL) { in ldns_rbtree_first()
553 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left); in ldns_rbtree_first()
555 return node; in ldns_rbtree_first()
561 ldns_rbnode_t *node = rbtree->root; in ldns_rbtree_last() local
563 if (rbtree->root != LDNS_RBTREE_NULL) { in ldns_rbtree_last()
564 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right); in ldns_rbtree_last()
566 return node; in ldns_rbtree_last()
570 * Returns the next node...
574 ldns_rbtree_next(ldns_rbnode_t *node) in ldns_rbtree_next() argument
578 if (node->right != LDNS_RBTREE_NULL) { in ldns_rbtree_next()
580 for (node = node->right; in ldns_rbtree_next()
581 node->left != LDNS_RBTREE_NULL; in ldns_rbtree_next()
582 node = node->left); in ldns_rbtree_next()
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()
591 return node; in ldns_rbtree_next()
595 ldns_rbtree_previous(ldns_rbnode_t *node) in ldns_rbtree_previous() argument
599 if (node->left != LDNS_RBTREE_NULL) { in ldns_rbtree_previous()
601 for (node = node->left; in ldns_rbtree_previous()
602 node->right != LDNS_RBTREE_NULL; in ldns_rbtree_previous()
603 node = node->right); in ldns_rbtree_previous()
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()
612 return node; in ldns_rbtree_previous()
628 new_tree = ldns_rbtree_create(tree->cmp); in ldns_rbtree_split()
632 move_node = ldns_rbtree_delete(tree, cur_node->key); in ldns_rbtree_split()
642 * add all node from the second tree to the first (removing them from the
654 ldns_rbnode_t* node) in traverse_post() argument
656 if(!node || node == LDNS_RBTREE_NULL) in traverse_post()
659 traverse_post(func, arg, node->left); in traverse_post()
660 traverse_post(func, arg, node->right); in traverse_post()
662 (*func)(node, arg); in traverse_post()
669 traverse_post(func, arg, tree->root); in ldns_traverse_postorder()