Lines Matching refs:rbt
127 rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
129 memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
145 rbt_find(RBTree *rbt, const RBTNode *data)
147 RBTNode *node = rbt->root;
151 int cmp = rbt->comparator(data, node, rbt->arg);
173 rbt_leftmost(RBTree *rbt)
175 RBTNode *node = rbt->root;
176 RBTNode *leftmost = rbt->root;
201 rbt_rotate_left(RBTree *rbt, RBTNode *x)
222 rbt->root = y;
238 rbt_rotate_right(RBTree *rbt, RBTNode *x)
259 rbt->root = y;
282 rbt_insert_fixup(RBTree *rbt, RBTNode *x)
288 while (x != rbt->root && x->parent->color == RBTRED)
326 rbt_rotate_left(rbt, x);
333 rbt_rotate_right(rbt, x->parent->parent);
356 rbt_rotate_right(rbt, x);
361 rbt_rotate_left(rbt, x->parent->parent);
370 rbt->root->color = RBTBLACK;
391 rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
399 current = rbt->root;
405 cmp = rbt->comparator(data, current, rbt->arg);
411 rbt->combiner(current, data, rbt->arg);
424 x = rbt->allocfunc(rbt->arg);
431 rbt_copy_data(rbt, x, data);
443 rbt->root = x;
446 rbt_insert_fixup(rbt, x);
459 rbt_delete_fixup(RBTree *rbt, RBTNode *x)
466 while (x != rbt->root && x->color == RBTBLACK)
484 rbt_rotate_left(rbt, x->parent);
501 rbt_rotate_right(rbt, w);
508 rbt_rotate_left(rbt, x->parent);
509 x = rbt->root; /* Arrange for loop to terminate. */
521 rbt_rotate_right(rbt, x->parent);
538 rbt_rotate_left(rbt, w);
545 rbt_rotate_right(rbt, x->parent);
546 x = rbt->root; /* Arrange for loop to terminate. */
557 rbt_delete_node(RBTree *rbt, RBTNode *z)
601 rbt->root = x;
609 rbt_copy_data(rbt, z, y);
616 rbt_delete_fixup(rbt, x);
619 if (rbt->freefunc)
620 rbt->freefunc(y, rbt->arg);
633 rbt_delete(RBTree *rbt, RBTNode *node)
635 rbt_delete_node(rbt, node);
647 iter->last_visited = iter->rbt->root;
689 iter->last_visited = iter->rbt->root;
740 rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
743 iter->rbt = rbt;
745 iter->is_over = (rbt->root == RBTNIL);