Lines Matching +full:left +full:- +full:right
2 * rbtree.c -- generic red black tree
6 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
57 LDNS_RBTREE_NULL, /* Left. */
58 LDNS_RBTREE_NULL, /* Right. */
64 /** rotate subtree left (to preserve redblack property) */
66 /** rotate subtree right (to preserve redblack property) */
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.
118 ldns_rbnode_t *right = node->right; in ldns_rbtree_rotate_left() local
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.
145 ldns_rbnode_t *left = node->left; in ldns_rbtree_rotate_right() local
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()
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()
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()
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()
248 ldns_rbnode_t *node = rbtree->root; in ldns_rbtree_insert()
254 if ((r = rbtree->cmp(data->key, node->key)) == 0) { in ldns_rbtree_insert()
260 node = node->left; in ldns_rbtree_insert()
262 node = node->right; 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()
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()
332 if(child->parent == old) child->parent = new; in change_child_ptr()
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()
347 /* swap with smallest from right subtree (or largest from left) */ 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()
354 * readjust the pointers left,right,parent */ 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()
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()
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()
398 else if(child->color == RED) 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()
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()
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()
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()
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()
520 node = rbtree->root; in ldns_rbtree_find_less_equal()
526 r = rbtree->cmp(key, node->key); in ldns_rbtree_find_less_equal()
533 node = node->left; 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()
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()
561 ldns_rbnode_t *node = rbtree->root; in ldns_rbtree_last()
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()
578 if (node->right != LDNS_RBTREE_NULL) { in ldns_rbtree_next()
579 /* One right, then keep on going left... */ 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()
587 parent = parent->parent; in ldns_rbtree_next()
599 if (node->left != LDNS_RBTREE_NULL) { in ldns_rbtree_previous()
600 /* One left, then keep on going right... */ 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()
608 parent = parent->parent; 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()
659 traverse_post(func, arg, node->left); in traverse_post()
660 traverse_post(func, arg, node->right); in traverse_post()
669 traverse_post(func, arg, tree->root); in ldns_traverse_postorder()