Cross Reference: /src/external/bsd/nsd/dist/rbtree.c

Lines Matching defs:rbtree
2  * rbtree.c -- generic red black tree
15 #include "rbtree.h"
28 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
29 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
30 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
31 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child, rbnode_type* child_parent);
42 	rbtree_type *rbtree;
45 	rbtree = (rbtree_type *) region_alloc(region, sizeof(rbtree_type));
46 	if (!rbtree) {
51 	rbtree->root = RBTREE_NULL;
52 	rbtree->count = 0;
53 	rbtree->region = region;
54 	rbtree->cmp = cmpf;
56 	return rbtree;
64 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
68 	/* Check if rbtree is NULL */
69 	if (!rbtree) {
86 		rbtree->root = right;
97 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
101 	/* Check if rbtree is NULL */
102 	if (!rbtree) {
119 		rbtree->root = left;
126 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
130 	/* Check if rbtree is NULL */
131 	if (!rbtree) {
136 	while (node != rbtree->root && node->parent->color == RED) {
156 					rbtree_rotate_left(rbtree, node);
161 				rbtree_rotate_right(rbtree, node->parent->parent);
181 					rbtree_rotate_right(rbtree, node);
186 				rbtree_rotate_left(rbtree, node->parent->parent);
190 	rbtree->root->color = BLACK;
201 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
208 	/* Check if rbtree is NULL */
209 	if (!rbtree) {
214 	node = rbtree->root;
220 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {
236 	rbtree->count++;
246 		rbtree->root = data;
250 	rbtree_insert_fixup(rbtree, data);
260 rbtree_search (rbtree_type *rbtree, const void *key)
264 	/* Check if rbtree is NULL */
265 	if (!rbtree) {
269 	if (rbtree_find_less_equal(rbtree, key, &node)) {
287 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent, rbnode_type* old, rbnode_type* new)
289 	/* Check if rbtree is NULL */
290 	if (!rbtree) {
296 		assert(rbtree->root == old);
297 		if(rbtree->root == old) rbtree->root = new;
313 rbtree_delete(rbtree_type *rbtree, const void *key)
318 	/* Check if rbtree is NULL */
319 	if (!rbtree) {
323 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
324 	rbtree->count--;
342 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
344 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);
374 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
386 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);
396 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child, rbnode_type* child_parent)
401 	/* Check if rbtree is NULL */
402 	if (!rbtree) {
423 				rbtree_rotate_right(rbtree, child_parent);
424 			else	rbtree_rotate_left(rbtree, child_parent);
469 		rbtree_rotate_left(rbtree, sibling);
481 		rbtree_rotate_right(rbtree, sibling);
494 		rbtree_rotate_right(rbtree, child_parent);
500 		rbtree_rotate_left(rbtree, child_parent);
505 rbtree_find_less_equal(rbtree_type *rbtree, const void *key, rbnode_type **result)
512 	/* Check if rbtree is NULL */
513 	if (!rbtree) {
519 	node = rbtree->root;
525 		r = rbtree->cmp(key, node->key);
547 rbtree_first (rbtree_type *rbtree)
551 	/* Check if rbtree is NULL */
552 	if (!rbtree) {
556 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
561 rbtree_last (rbtree_type *rbtree)
565 	/* Check if rbtree is NULL */
566 	if (!rbtree) {
570 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
OpenGrok
