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;  in rbtree_create()  local
45 	rbtree = (rbtree_type *) region_alloc(region, sizeof(rbtree_type));  in rbtree_create()
46 	if (!rbtree) {  in rbtree_create()
51 	rbtree->root = RBTREE_NULL;  in rbtree_create()
52 	rbtree->count = 0;  in rbtree_create()
53 	rbtree->region = region;  in rbtree_create()
54 	rbtree->cmp = cmpf;  in rbtree_create()
56 	return rbtree;  in rbtree_create()
64 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_left()  argument
80 		rbtree->root = right;  in rbtree_rotate_left()
91 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_right()  argument
107 		rbtree->root = left;  in rbtree_rotate_right()
114 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)  in rbtree_insert_fixup()  argument
119 	while (node != rbtree->root && node->parent->color == RED) {  in rbtree_insert_fixup()
139 					rbtree_rotate_left(rbtree, node);  in rbtree_insert_fixup()
144 				rbtree_rotate_right(rbtree, node->parent->parent);  in rbtree_insert_fixup()
164 					rbtree_rotate_right(rbtree, node);  in rbtree_insert_fixup()
169 				rbtree_rotate_left(rbtree, node->parent->parent);  in rbtree_insert_fixup()
173 	rbtree->root->color = BLACK;  in rbtree_insert_fixup()
184 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)  in rbtree_insert()  argument
190 	rbnode_type	*node = rbtree->root;  in rbtree_insert()
196 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {  in rbtree_insert()
212 	rbtree->count++;  in rbtree_insert()
222 		rbtree->root = data;  in rbtree_insert()
226 	rbtree_insert_fixup(rbtree, data);  in rbtree_insert()
236 rbtree_search (rbtree_type *rbtree, const void *key)  in rbtree_search()  argument
240 	if (rbtree_find_less_equal(rbtree, key, &node)) {  in rbtree_search()
258 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent, rbnode_type* old, rbnode_ty…  in change_parent_ptr()  argument
262 		assert(rbtree->root == old);  in change_parent_ptr()
263 		if(rbtree->root == old) rbtree->root = new;  in change_parent_ptr()
279 rbtree_delete(rbtree_type *rbtree, const void *key)  in rbtree_delete()  argument
283 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;  in rbtree_delete()
284 	rbtree->count--;  in rbtree_delete()
302 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);  in rbtree_delete()
304 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);  in rbtree_delete()
334 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);  in rbtree_delete()
346 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);  in rbtree_delete()
356 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child, rbnode_type* child_parent)  in rbtree_delete_fixup()  argument
378 				rbtree_rotate_right(rbtree, child_parent);  in rbtree_delete_fixup()
379 			else	rbtree_rotate_left(rbtree, child_parent);  in rbtree_delete_fixup()
424 		rbtree_rotate_left(rbtree, sibling);  in rbtree_delete_fixup()
436 		rbtree_rotate_right(rbtree, sibling);  in rbtree_delete_fixup()
449 		rbtree_rotate_right(rbtree, child_parent);  in rbtree_delete_fixup()
455 		rbtree_rotate_left(rbtree, child_parent);  in rbtree_delete_fixup()
460 rbtree_find_less_equal(rbtree_type *rbtree, const void *key, rbnode_type **result)  in rbtree_find_less_equal()  argument
468 	node = rbtree->root;  in rbtree_find_less_equal()
474 		r = rbtree->cmp(key, node->key);  in rbtree_find_less_equal()
496 rbtree_first (rbtree_type *rbtree)  in rbtree_first()  argument
500 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);  in rbtree_first()
505 rbtree_last (rbtree_type *rbtree)  in rbtree_last()  argument
509 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);  in rbtree_last()