Lines Matching refs:tree
219 void rbtree_init(rb_tree * tree) in rbtree_init() argument
222 tree->isize = 0; in rbtree_init()
223 tree->root = NULL; in rbtree_init()
230 rb_tree *tree = (rb_tree *) malloc(sizeof(rb_tree)); in rbtree_construct() local
231 if (!tree) { in rbtree_construct()
235 rbtree_init(tree); in rbtree_construct()
236 return tree; in rbtree_construct()
241 void rbtree_clean(rb_tree * tree, destructor d) in rbtree_clean() argument
243 if (tree->root) in rbtree_clean()
244 rbnode_destruct(tree->root, d); in rbtree_clean()
245 tree->root = NULL; in rbtree_clean()
246 tree->isize = 0; in rbtree_clean()
251 void rbtree_destruct(rb_tree * tree, destructor d) in rbtree_destruct() argument
253 rbtree_clean(tree, d); in rbtree_destruct()
254 free(tree); in rbtree_destruct()
259 int rbtree_size(rb_tree * tree) in rbtree_size() argument
261 return tree->isize; in rbtree_size()
266 int rbtree_depth(rb_tree * tree) in rbtree_depth() argument
268 if (!(tree->root)) in rbtree_depth()
270 return rbnode_depth(tree->root); in rbtree_depth()
275 int rbtree_contains(rb_tree * tree, datatype object) in rbtree_contains() argument
277 return (rbtree_find(tree, object) != NULL); in rbtree_contains()
282 rb_node *rbtree_insert(rb_tree * tree, datatype object) in rbtree_insert() argument
288 if (!(tree->root)) { in rbtree_insert()
295 tree->root = new_node; in rbtree_insert()
296 tree->isize = 1; in rbtree_insert()
304 cur_node = tree->root; in rbtree_insert()
348 tree->isize++; in rbtree_insert()
351 rbtree_insert_fixup(tree, new_node); in rbtree_insert()
360 rb_node *insert_successor_at(rb_tree * tree, rb_node * at_node, datatype object) in insert_successor_at() argument
365 if (!(tree->root)) { in insert_successor_at()
372 tree->root = new_node; in insert_successor_at()
373 tree->isize = 1; in insert_successor_at()
388 parent = rbnode_minimum(tree->root); in insert_successor_at()
409 tree->isize++; in insert_successor_at()
412 rbtree_insert_fixup(tree, new_node); in insert_successor_at()
419 rb_node *insert_predecessor_at(rb_tree * tree, rb_node * at_node, in insert_predecessor_at() argument
425 if (!(tree->root)) { in insert_predecessor_at()
432 tree->root = new_node; in insert_predecessor_at()
433 tree->isize = 1; in insert_predecessor_at()
448 parent = rbnode_maximum(tree->root); in insert_predecessor_at()
469 tree->isize++; in insert_predecessor_at()
472 rbtree_insert_fixup(tree, new_node); in insert_predecessor_at()
479 void rbtree_remove(rb_tree * tree, datatype object, destructor d) in rbtree_remove() argument
481 rb_node *node = rbtree_find(tree, object); /* Find the node */ in rbtree_remove()
482 rbtree_remove_at(tree, node, d); /* Remove the node */ in rbtree_remove()
487 void rbtree_remove_at(rb_tree * tree, rb_node * node, destructor d) in rbtree_remove_at() argument
494 if (tree->isize == 1) { in rbtree_remove_at()
495 rbnode_destruct(tree->root, d); in rbtree_remove_at()
496 tree->root = NULL; in rbtree_remove_at()
497 tree->isize = 0; in rbtree_remove_at()
550 tree->root = succ_node; in rbtree_remove_at()
574 tree->root = child; in rbtree_remove_at()
588 rbtree_remove_fixup(tree, child); in rbtree_remove_at()
598 tree->isize--; in rbtree_remove_at()
603 rb_node *rbtree_minimum(rb_tree * tree) in rbtree_minimum() argument
605 if (!(tree->root)) in rbtree_minimum()
609 return rbnode_minimum(tree->root); in rbtree_minimum()
614 rb_node *rbtree_maximum(rb_tree * tree) in rbtree_maximum() argument
616 if (!(tree->root)) in rbtree_maximum()
620 return rbnode_maximum(tree->root); in rbtree_maximum()
625 rb_node *rbtree_find(rb_tree * tree, datatype object) in rbtree_find() argument
627 rb_node *cur_node = tree->root; in rbtree_find()
645 void rbtree_rotate_left(rb_tree * tree, rb_node * x_node) in rbtree_rotate_left() argument
662 tree->root = y_node; in rbtree_rotate_left()
678 void rbtree_rotate_right(rb_tree * tree, rb_node * y_node) in rbtree_rotate_right() argument
695 tree->root = x_node; in rbtree_rotate_right()
711 void rbtree_insert_fixup(rb_tree * tree, rb_node * node) in rbtree_insert_fixup() argument
723 while (curr_node != tree->root && curr_node->parent->color == red) { in rbtree_insert_fixup()
759 rbtree_rotate_left(tree, curr_node); in rbtree_insert_fixup()
771 rbtree_rotate_right(tree, grandparent); in rbtree_insert_fixup()
800 rbtree_rotate_right(tree, curr_node); in rbtree_insert_fixup()
812 rbtree_rotate_left(tree, grandparent); in rbtree_insert_fixup()
818 tree->root->color = black; in rbtree_insert_fixup()
821 void rbtree_remove_fixup(rb_tree * tree, rb_node * node) in rbtree_remove_fixup() argument
826 while (curr_node != tree->root && curr_node->color == black) { in rbtree_remove_fixup()
849 rbtree_rotate_left(tree, curr_node->parent); in rbtree_remove_fixup()
869 curr_node = tree->root; in rbtree_remove_fixup()
888 curr_node = tree->root; in rbtree_remove_fixup()
908 rbtree_rotate_left(tree, in rbtree_remove_fixup()
920 rbtree_rotate_right(tree, in rbtree_remove_fixup()
924 rbtree_rotate_left(tree, in rbtree_remove_fixup()
938 curr_node = tree->root; in rbtree_remove_fixup()
959 rbtree_rotate_right(tree, curr_node->parent); in rbtree_remove_fixup()
980 curr_node = tree->root; in rbtree_remove_fixup()
998 curr_node = tree->root; in rbtree_remove_fixup()
1018 rbtree_rotate_right(tree, in rbtree_remove_fixup()
1030 rbtree_rotate_left(tree, in rbtree_remove_fixup()
1034 rbtree_rotate_right(tree, in rbtree_remove_fixup()
1048 curr_node = tree->root; in rbtree_remove_fixup()
1060 void rbtree_traverse(rb_tree * tree, opr * op) in rbtree_traverse() argument
1062 rbnode_traverse(tree->root, op); in rbtree_traverse()