Lines Matching +full:child +full:- +full:node
2 * rbtree.c -- generic red black tree
4 * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
47 /** Node colour black */
49 /** Node colour red */
52 /** the NULL node, global alloc */
62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
65 /** Fixup node colours when insert happened */
66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
67 /** Fixup node colours when delete happened */
68 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
98 rbtree->root = RBTREE_NULL; in rbtree_init()
99 rbtree->count = 0; in rbtree_init()
100 rbtree->cmp = cmpf; in rbtree_init()
104 * Rotates the node to the left.
108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node) in rbtree_rotate_left() argument
110 rbnode_type *right = node->right; in rbtree_rotate_left()
111 node->right = right->left; in rbtree_rotate_left()
112 if (right->left != RBTREE_NULL) in rbtree_rotate_left()
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()
124 rbtree->root = right; in rbtree_rotate_left()
126 right->left = node; in rbtree_rotate_left()
127 node->parent = right; in rbtree_rotate_left()
131 * Rotates the node to the right.
135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node) in rbtree_rotate_right() argument
137 rbnode_type *left = node->left; in rbtree_rotate_right()
138 node->left = left->right; in rbtree_rotate_right()
139 if (left->right != RBTREE_NULL) in rbtree_rotate_right()
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()
151 rbtree->root = left; in rbtree_rotate_right()
153 left->right = node; in rbtree_rotate_right()
154 node->parent = left; in rbtree_rotate_right()
158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node) in rbtree_insert_fixup() argument
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()
169 if (uncle->color == RED) { in rbtree_insert_fixup()
171 node->parent->color = BLACK; in rbtree_insert_fixup()
172 uncle->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()
180 /* Are we the right child? */ in rbtree_insert_fixup()
181 if (node == node->parent->right) { in rbtree_insert_fixup()
182 node = node->parent; in rbtree_insert_fixup()
183 rbtree_rotate_left(rbtree, node); in rbtree_insert_fixup()
185 /* Now we're the left child, repaint and rotate... */ 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()
194 if (uncle->color == RED) { in rbtree_insert_fixup()
196 node->parent->color = BLACK; in rbtree_insert_fixup()
197 uncle->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()
205 /* Are we the right child? */ in rbtree_insert_fixup()
206 if (node == node->parent->left) { in rbtree_insert_fixup()
207 node = node->parent; in rbtree_insert_fixup()
208 rbtree_rotate_right(rbtree, node); in rbtree_insert_fixup()
210 /* Now we're the right child, repaint and rotate... */ 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()
217 rbtree->root->color = BLACK; in rbtree_insert_fixup()
222 * Inserts a node into a red black tree.
224 * Returns NULL on failure or the pointer to the newly added node
234 rbnode_type *node = rbtree->root; in rbtree_insert() local
237 fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp)); in rbtree_insert()
239 while (node != RBTREE_NULL) { in rbtree_insert()
241 if ((r = rbtree->cmp(data->key, node->key)) == 0) { in rbtree_insert()
244 parent = node; in rbtree_insert()
247 node = node->left; in rbtree_insert()
249 node = node->right; in rbtree_insert()
253 /* Initialize the new node */ in rbtree_insert()
254 data->parent = parent; in rbtree_insert()
255 data->left = data->right = RBTREE_NULL; in rbtree_insert()
256 data->color = RED; in rbtree_insert()
257 rbtree->count++; in rbtree_insert()
262 parent->left = data; in rbtree_insert()
264 parent->right = data; in rbtree_insert()
267 rbtree->root = data; in rbtree_insert()
270 /* Fix up the red-black properties... */ in rbtree_insert()
283 rbnode_type *node; in rbtree_search() local
285 if (rbtree_find_less_equal(rbtree, key, &node)) { in rbtree_search()
286 return node; in rbtree_search()
292 /** helpers for delete: swap node colours */
298 /** helpers for delete: swap node pointers */
304 /** Update parent pointers of child trees of 'parent' */
310 log_assert(rbtree->root == old); in change_parent_ptr()
311 if(rbtree->root == old) rbtree->root = new; 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' */
320 static void change_child_ptr(rbnode_type* child, rbnode_type* old, in change_child_ptr() argument
323 if(child == RBTREE_NULL) return; in change_child_ptr()
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()
332 rbnode_type *child; in rbtree_delete() local
334 rbtree->count--; in rbtree_delete()
336 /* make sure we have at most one non-leaf child */ in rbtree_delete()
337 if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL) in rbtree_delete()
340 rbnode_type *smright = to_delete->right; in rbtree_delete()
341 while(smright->left != RBTREE_NULL) in rbtree_delete()
342 smright = smright->left; in rbtree_delete()
348 /* swap colors - colors are tied to the position in the tree */ in rbtree_delete()
349 swap_int8(&to_delete->color, &smright->color); in rbtree_delete()
351 /* swap child pointers in parents of smright/to_delete */ in rbtree_delete()
352 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); in rbtree_delete()
353 if(to_delete->right != smright) in rbtree_delete()
354 change_parent_ptr(rbtree, smright->parent, smright, to_delete); in rbtree_delete()
357 change_child_ptr(smright->left, smright, to_delete); in rbtree_delete()
358 change_child_ptr(smright->left, smright, to_delete); in rbtree_delete()
359 change_child_ptr(smright->right, smright, to_delete); in rbtree_delete()
360 change_child_ptr(smright->right, smright, to_delete); in rbtree_delete()
361 change_child_ptr(to_delete->left, to_delete, smright); in rbtree_delete()
362 if(to_delete->right != smright) in rbtree_delete()
363 change_child_ptr(to_delete->right, to_delete, smright); in rbtree_delete()
364 if(to_delete->right == smright) in rbtree_delete()
367 to_delete->right = to_delete; in rbtree_delete()
368 smright->parent = smright; in rbtree_delete()
372 swap_np(&to_delete->parent, &smright->parent); in rbtree_delete()
373 swap_np(&to_delete->left, &smright->left); in rbtree_delete()
374 swap_np(&to_delete->right, &smright->right); in rbtree_delete()
378 log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL); in rbtree_delete()
380 if(to_delete->left != RBTREE_NULL) child = to_delete->left; in rbtree_delete()
381 else child = to_delete->right; in rbtree_delete()
383 /* unlink to_delete from the tree, replace to_delete with child */ 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()
387 if(to_delete->color == RED) in rbtree_delete()
389 /* if node is red then the child (black) can be swapped in */ in rbtree_delete()
391 else if(child->color == RED) in rbtree_delete()
393 /* change child to BLACK, removing a RED node is no problem */ in rbtree_delete()
394 if(child!=RBTREE_NULL) child->color = BLACK; 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()
400 to_delete->left = RBTREE_NULL; in rbtree_delete()
401 to_delete->right = RBTREE_NULL; in rbtree_delete()
402 to_delete->color = BLACK; in rbtree_delete()
406 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child, in rbtree_delete_fixup() argument
412 /* determine sibling to the node that is one-black short */ in rbtree_delete_fixup()
413 if(child_parent->right == child) sibling = child_parent->left; in rbtree_delete_fixup()
414 else sibling = child_parent->right; in rbtree_delete_fixup()
424 if(sibling->color == RED) in rbtree_delete_fixup()
426 child_parent->color = RED; in rbtree_delete_fixup()
427 sibling->color = BLACK; in rbtree_delete_fixup()
428 if(child_parent->right == child) in rbtree_delete_fixup()
432 if(child_parent->right == child) sibling = child_parent->left; in rbtree_delete_fixup()
433 else sibling = child_parent->right; in rbtree_delete_fixup()
436 if(child_parent->color == BLACK in rbtree_delete_fixup()
437 && sibling->color == BLACK in rbtree_delete_fixup()
438 && sibling->left->color == BLACK in rbtree_delete_fixup()
439 && sibling->right->color == BLACK) in rbtree_delete_fixup()
442 sibling->color = RED; in rbtree_delete_fixup()
444 child = child_parent; in rbtree_delete_fixup()
445 child_parent = child_parent->parent; in rbtree_delete_fixup()
447 if(child_parent->right == child) sibling = child_parent->left; in rbtree_delete_fixup()
448 else sibling = child_parent->right; in rbtree_delete_fixup()
453 if(child_parent->color == RED in rbtree_delete_fixup()
454 && sibling->color == BLACK in rbtree_delete_fixup()
455 && sibling->left->color == BLACK in rbtree_delete_fixup()
456 && sibling->right->color == BLACK) in rbtree_delete_fixup()
460 sibling->color = RED; in rbtree_delete_fixup()
461 child_parent->color = BLACK; in rbtree_delete_fixup()
466 /* get a new sibling, by rotating at sibling. See which child in rbtree_delete_fixup()
468 if(child_parent->right == child in rbtree_delete_fixup()
469 && sibling->color == BLACK in rbtree_delete_fixup()
470 && sibling->right->color == RED in rbtree_delete_fixup()
471 && sibling->left->color == BLACK) in rbtree_delete_fixup()
473 sibling->color = RED; in rbtree_delete_fixup()
474 sibling->right->color = BLACK; in rbtree_delete_fixup()
477 if(child_parent->right == child) sibling = child_parent->left; in rbtree_delete_fixup()
478 else sibling = child_parent->right; in rbtree_delete_fixup()
480 else if(child_parent->left == child in rbtree_delete_fixup()
481 && sibling->color == BLACK in rbtree_delete_fixup()
482 && sibling->left->color == RED in rbtree_delete_fixup()
483 && sibling->right->color == BLACK) in rbtree_delete_fixup()
485 sibling->color = RED; in rbtree_delete_fixup()
486 sibling->left->color = BLACK; in rbtree_delete_fixup()
489 if(child_parent->right == child) sibling = child_parent->left; in rbtree_delete_fixup()
490 else sibling = child_parent->right; in rbtree_delete_fixup()
493 /* now we have a black sibling with a red child. rotate and exchange colors. */ in rbtree_delete_fixup()
494 sibling->color = child_parent->color; in rbtree_delete_fixup()
495 child_parent->color = BLACK; in rbtree_delete_fixup()
496 if(child_parent->right == child) in rbtree_delete_fixup()
498 log_assert(sibling->left->color == RED); in rbtree_delete_fixup()
499 sibling->left->color = BLACK; in rbtree_delete_fixup()
504 log_assert(sibling->right->color == RED); in rbtree_delete_fixup()
505 sibling->right->color = BLACK; in rbtree_delete_fixup()
515 rbnode_type *node; in rbtree_find_less_equal() local
520 node = rbtree->root; in rbtree_find_less_equal()
523 fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp)); in rbtree_find_less_equal()
526 while (node != RBTREE_NULL) { in rbtree_find_less_equal()
527 r = rbtree->cmp(key, node->key); in rbtree_find_less_equal()
530 *result = node; in rbtree_find_less_equal()
534 node = node->left; in rbtree_find_less_equal()
537 *result = node; in rbtree_find_less_equal()
538 node = node->right; in rbtree_find_less_equal()
551 rbnode_type *node; in rbtree_first() local
553 for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left); in rbtree_first()
554 return node; in rbtree_first()
560 rbnode_type *node; in rbtree_last() local
562 for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right); in rbtree_last()
563 return node; in rbtree_last()
567 * Returns the next node...
571 rbtree_next (rbnode_type *node) in rbtree_next() argument
575 if (node->right != RBTREE_NULL) { in rbtree_next()
577 for (node = node->right; node->left != RBTREE_NULL; node = node->left); in rbtree_next()
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()
586 return node; in rbtree_next()
590 rbtree_previous(rbnode_type *node) in rbtree_previous() argument
594 if (node->left != RBTREE_NULL) { in rbtree_previous()
596 for (node = node->left; node->right != RBTREE_NULL; node = node->right); in rbtree_previous()
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()
605 return node; in rbtree_previous()
610 traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node) in traverse_post() argument
612 if(!node || node == RBTREE_NULL) in traverse_post()
615 traverse_post(func, arg, node->left); in traverse_post()
616 traverse_post(func, arg, node->right); in traverse_post()
618 (*func)(node, arg); in traverse_post()
625 traverse_post(func, arg, tree->root); in traverse_postorder()