62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
68 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
80 	rbtree_type *rbtree;  in rbtree_create()  local
83 	rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));  in rbtree_create()
84 	if (!rbtree) {  in rbtree_create()
89 	rbtree_init(rbtree, cmpf);  in rbtree_create()
91 	return rbtree;  in rbtree_create()
95 rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))  in rbtree_init()  argument
98 	rbtree->root = RBTREE_NULL;  in rbtree_init()
99 	rbtree->count = 0;  in rbtree_init()
100 	rbtree->cmp = cmpf;  in rbtree_init()
108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_left()  argument
124 		rbtree->root = right;  in rbtree_rotate_left()
135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_right()  argument
151 		rbtree->root = 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()
183 					rbtree_rotate_left(rbtree, node);  in rbtree_insert_fixup()
188 				rbtree_rotate_right(rbtree, node->parent->parent);  in rbtree_insert_fixup()
208 					rbtree_rotate_right(rbtree, node);  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()
228 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)  in rbtree_insert()  argument
234 	rbnode_type	*node = rbtree->root;  in rbtree_insert()
237 	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));  in rbtree_insert()
241 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {  in rbtree_insert()
257 	rbtree->count++;  in rbtree_insert()
267 		rbtree->root = data;  in rbtree_insert()
271 	rbtree_insert_fixup(rbtree, data);  in rbtree_insert()
281 rbtree_search (rbtree_type *rbtree, const void *key)  in rbtree_search()  argument
285 	if (rbtree_find_less_equal(rbtree, key, &node)) {  in rbtree_search()
305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,  in change_parent_ptr()  argument
310 		log_assert(rbtree->root == old);  in change_parent_ptr()
311 		if(rbtree->root == old) rbtree->root = new;  in change_parent_ptr()
329 rbtree_delete(rbtree_type *rbtree, const void *key)  in rbtree_delete()  argument
333 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;  in rbtree_delete()
334 	rbtree->count--;  in rbtree_delete()
352 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);  in rbtree_delete()
354 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);  in rbtree_delete()
384 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);  in rbtree_delete()
396 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);  in rbtree_delete()
406 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,  in rbtree_delete_fixup()  argument
429 				rbtree_rotate_right(rbtree, child_parent);  in rbtree_delete_fixup()
430 			else	rbtree_rotate_left(rbtree, child_parent);  in rbtree_delete_fixup()
475 		rbtree_rotate_left(rbtree, sibling);  in rbtree_delete_fixup()
487 		rbtree_rotate_right(rbtree, sibling);  in rbtree_delete_fixup()
500 		rbtree_rotate_right(rbtree, child_parent);  in rbtree_delete_fixup()
506 		rbtree_rotate_left(rbtree, child_parent);  in rbtree_delete_fixup()
511 rbtree_find_less_equal(rbtree_type *rbtree, const void *key,  in rbtree_find_less_equal()  argument
520 	node = rbtree->root;  in rbtree_find_less_equal()
523 	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));  in rbtree_find_less_equal()
527 		r = rbtree->cmp(key, node->key);  in rbtree_find_less_equal()
549 rbtree_first (rbtree_type *rbtree)  in rbtree_first()  argument
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);  in rbtree_first()
558 rbtree_last (rbtree_type *rbtree)  in rbtree_last()  argument
562 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);  in rbtree_last()