Home | History | Annotate | Download | only in util

Lines Matching defs:rbtree

2  * rbtree.c -- generic red black tree
45 #include "util/rbtree.h"
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;
83 	rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
84 	if (!rbtree) {
89 	rbtree_init(rbtree, cmpf);
91 	return rbtree;
95 rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
98 	rbtree->root = RBTREE_NULL;
99 	rbtree->count = 0;
100 	rbtree->cmp = cmpf;
108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
124 		rbtree->root = right;
135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
151 		rbtree->root = left;
158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
163 	while (node != rbtree->root && node->parent->color == RED) {
183 					rbtree_rotate_left(rbtree, node);
188 				rbtree_rotate_right(rbtree, node->parent->parent);
208 					rbtree_rotate_right(rbtree, node);
213 				rbtree_rotate_left(rbtree, node->parent->parent);
217 	rbtree->root->color = BLACK;
228 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
234 	rbnode_type	*node = rbtree->root;
237 	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
241 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {
257 	rbtree->count++;
267 		rbtree->root = data;
271 	rbtree_insert_fixup(rbtree, data);
281 rbtree_search (rbtree_type *rbtree, const void *key)
285 	if (rbtree_find_less_equal(rbtree, key, &node)) {
305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
310 		log_assert(rbtree->root == old);
311 		if(rbtree->root == old) rbtree->root = new;
329 rbtree_delete(rbtree_type *rbtree, const void *key)
333 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
334 	rbtree->count--;
352 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
354 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);
384 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
396 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);
406 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
429 				rbtree_rotate_right(rbtree, child_parent);
430 			else	rbtree_rotate_left(rbtree, child_parent);
475 		rbtree_rotate_left(rbtree, sibling);
487 		rbtree_rotate_right(rbtree, sibling);
500 		rbtree_rotate_right(rbtree, child_parent);
506 		rbtree_rotate_left(rbtree, child_parent);
511 rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
520 	node = rbtree->root;
523 	fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
527 		r = rbtree->cmp(key, node->key);
549 rbtree_first (rbtree_type *rbtree)
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
558 rbtree_last (rbtree_type *rbtree)
562 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);