Lines Matching refs:self
197 struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
253 RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
255 RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
262 RB_SET_FATHER(self, parent);
263 RB_SET_POSITION(self, position);
265 RB_MARK_BLACK(self); /* root is always black */
267 rbt->rbt_minmax[RB_DIR_LEFT] = self;
268 rbt->rbt_minmax[RB_DIR_RIGHT] = self;
280 rbt->rbt_minmax[position] = self;
286 RB_MARK_RED(self);
290 self->rb_left = parent->rb_nodes[position];
291 self->rb_right = parent->rb_nodes[position];
292 parent->rb_nodes[position] = self;
293 KASSERT(RB_CHILDLESS_P(self));
300 if (RB_ROOT_P(rbt, self)) {
301 RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
304 RB_NODETOITEM(rbto, self),
305 RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
306 RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
309 RB_NODETOITEM(rbto, RB_FATHER(self)),
310 RB_NODETOITEM(rbto, self)) < 0);
311 RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
312 self, rb_link);
315 KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
321 rb_tree_insert_rebalance(rbt, self);
322 KASSERT(rb_tree_check_node(rbt, self, NULL, true));
330 * Swap the location and colors of 'self' and its child @ which. The child
401 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
403 struct rb_node * father = RB_FATHER(self);
409 KASSERT(!RB_ROOT_P(rbt, self));
410 KASSERT(RB_RED_P(self));
415 KASSERT(!RB_SENTINEL_P(self));
417 KASSERT(RB_RED_P(self));
451 self = grandpa;
452 father = RB_FATHER(self);
453 KASSERT(RB_RED_P(self));
463 KASSERT(!RB_ROOT_P(rbt, self));
464 KASSERT(RB_RED_P(self));
471 if (self == father->rb_nodes[other]) {
479 KASSERT(RB_FATHER(father) == self);
480 KASSERT(self->rb_nodes[which] == father);
481 KASSERT(RB_FATHER(self) == grandpa);
482 self = father;
483 father = RB_FATHER(self);
485 KASSERT(RB_RED_P(self) && RB_RED_P(father));
494 KASSERT(RB_FATHER(self) == father);
495 KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
496 KASSERT(RB_RED_P(self));
507 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
509 const unsigned int which = RB_POSITION(self);
510 struct rb_node *father = RB_FATHER(self);
512 const bool was_root = RB_ROOT_P(rbt, self);
515 KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
516 KASSERT(!rebalance || RB_BLACK_P(self));
517 KASSERT(RB_CHILDLESS_P(self));
518 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
521 * Since we are childless, we know that self->rb_left is pointing
524 father->rb_nodes[which] = self->rb_left;
530 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
533 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
534 rbt->rbt_minmax[RB_POSITION(self)] = father;
544 RB_SET_FATHER(self, NULL);
559 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
568 if (standin_father == self) {
570 * As a child of self, any childen would be opposite of
577 * Since we aren't a child of self, any childen would be
587 KASSERT(RB_TWOCHILDREN_P(self));
596 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
608 if (standin_father == self) {
620 if (standin_father == self) {
633 KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
634 KASSERT(self->rb_nodes[standin_which] == standin);
651 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
653 KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
665 KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
666 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
670 * Now copy the result of self to standin and then replace
671 * self with standin in the tree.
673 RB_COPY_PROPERTIES(standin, self);
674 RB_SET_FATHER(standin, RB_FATHER(self));
681 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
684 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
685 rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
686 RB_SET_FATHER(self, NULL);
706 * rb_tree_node_swap(rbt, self, which);
707 * rb_tree_prune_node(rbt, self, false);
712 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
715 struct rb_node *father = RB_FATHER(self);
716 struct rb_node *son = self->rb_nodes[which];
718 const bool was_root = RB_ROOT_P(rbt, self);
722 KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
725 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
732 RB_COPY_PROPERTIES(son, self);
740 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
746 } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
747 rbt->rbt_minmax[RB_POSITION(self)] = son;
749 RB_SET_FATHER(self, NULL);
760 struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
763 KASSERT(!RB_SENTINEL_P(self));
783 if (RB_CHILDLESS_P(self)) {
784 const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
785 rb_tree_prune_node(rbt, self, rebalance);
788 KASSERT(!RB_CHILDLESS_P(self));
789 if (!RB_TWOCHILDREN_P(self)) {
798 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
799 KASSERT(RB_BLACK_P(self));
800 KASSERT(RB_RED_P(self->rb_nodes[which]));
801 KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
802 rb_tree_prune_blackred_branch(rbt, self, which);
805 KASSERT(RB_TWOCHILDREN_P(self));
811 which = RB_POSITION(self) ^ RB_DIR_OTHER;
818 rb_tree_swap_prune_and_rebalance(rbt, self, standin);
977 struct rb_node *self;
987 self = rbt->rbt_root;
988 if (RB_SENTINEL_P(self))
990 while (!RB_SENTINEL_P(self->rb_nodes[direction]))
991 self = self->rb_nodes[direction];
992 return RB_NODETOITEM(rbto, self);
995 self = RB_ITEMTONODE(rbto, object);
996 KASSERT(!RB_SENTINEL_P(self));
1001 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
1002 while (!RB_ROOT_P(rbt, self)) {
1003 if (other == RB_POSITION(self))
1004 return RB_NODETOITEM(rbto, RB_FATHER(self));
1005 self = RB_FATHER(self);
1014 self = self->rb_nodes[direction];
1015 KASSERT(!RB_SENTINEL_P(self));
1016 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1017 self = self->rb_nodes[other];
1018 return RB_NODETOITEM(rbto, self);
1023 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
1029 if (self == NULL) {
1035 self = rbt->rbt_root;
1036 if (RB_SENTINEL_P(self))
1038 while (!RB_SENTINEL_P(self->rb_nodes[direction]))
1039 self = self->rb_nodes[direction];
1040 return self;
1043 KASSERT(!RB_SENTINEL_P(self));
1048 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
1049 while (!RB_ROOT_P(rbt, self)) {
1050 if (other == RB_POSITION(self))
1051 return RB_FATHER(self);
1052 self = RB_FATHER(self);
1061 self = self->rb_nodes[direction];
1062 KASSERT(!RB_SENTINEL_P(self));
1063 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1064 self = self->rb_nodes[other];
1065 return self;
1069 rb_tree_count_black(const struct rb_node *self)
1073 if (RB_SENTINEL_P(self))
1076 left = rb_tree_count_black(self->rb_left);
1077 right = rb_tree_count_black(self->rb_right);
1081 return left + RB_BLACK_P(self);
1085 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
1091 KASSERT(!RB_SENTINEL_P(self));
1093 RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
1098 if (RB_ROOT_P(rbt, self)) {
1099 KASSERT(self == rbt->rbt_root);
1100 KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
1101 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1102 KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
1105 RB_NODETOITEM(rbto, self),
1106 RB_NODETOITEM(rbto, RB_FATHER(self)));
1108 KASSERT(self != rbt->rbt_root);
1109 KASSERT(!RB_FATHER_SENTINEL_P(self));
1110 if (RB_POSITION(self) == RB_DIR_LEFT) {
1112 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1115 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
1123 const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1124 const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1125 KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
1126 KASSERT(next0 == TAILQ_NEXT(self, rb_link));
1128 KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
1129 KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
1138 KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
1139 (void) rb_tree_count_black(self);
1140 if (RB_RED_P(self)) {
1142 KASSERT(!RB_ROOT_P(rbt, self));
1143 brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
1144 KASSERT(RB_BLACK_P(RB_FATHER(self)));
1150 KASSERT(!RB_CHILDLESS_P(self)
1158 KASSERT(RB_CHILDLESS_P(self)
1159 || (RB_TWOCHILDREN_P(self)
1160 && RB_BLACK_P(self->rb_left)
1161 && RB_BLACK_P(self->rb_right)));
1167 KASSERT(RB_CHILDLESS_P(self)
1177 KASSERT(RB_CHILDLESS_P(self)
1178 || RB_TWOCHILDREN_P(self)
1179 || (!RB_LEFT_SENTINEL_P(self)
1180 && RB_RIGHT_SENTINEL_P(self)
1181 && RB_RED_P(self->rb_left)
1182 && RB_CHILDLESS_P(self->rb_left))
1183 || (!RB_RIGHT_SENTINEL_P(self)
1184 && RB_LEFT_SENTINEL_P(self)
1185 && RB_RED_P(self->rb_right)
1186 && RB_CHILDLESS_P(self->rb_right)));
1193 if (!RB_ROOT_P(rbt, self)
1194 && RB_CHILDLESS_P(self)
1195 && RB_BLACK_P(RB_FATHER(self))) {
1196 const unsigned int which = RB_POSITION(self);
1201 self, other);
1219 KASSERT(RB_ROOT_P(rbt, self)
1220 || RB_ROOT_P(rbt, RB_FATHER(self))
1221 || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
1226 KASSERT(RB_LEFT_SENTINEL_P(self)
1227 || RB_CHILDLESS_P(self->rb_left)
1228 || !RB_RIGHT_SENTINEL_P(self));
1233 KASSERT(RB_RIGHT_SENTINEL_P(self)
1234 || RB_CHILDLESS_P(self->rb_right)
1235 || !RB_LEFT_SENTINEL_P(self));
1242 KASSERT(RB_TWOCHILDREN_P(self->rb_left)
1243 || RB_CHILDLESS_P(self->rb_right)
1244 || RB_CHILDLESS_P(self->rb_right->rb_left)
1245 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
1246 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
1247 || RB_CHILDLESS_P(self->rb_right->rb_right)
1248 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
1249 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
1256 KASSERT(RB_TWOCHILDREN_P(self->rb_right)
1257 || RB_CHILDLESS_P(self->rb_left)
1258 || RB_CHILDLESS_P(self->rb_left->rb_left)
1259 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
1260 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
1261 || RB_CHILDLESS_P(self->rb_left->rb_right)
1262 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
1263 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
1269 if (RB_TWOCHILDREN_P(self)) {
1273 prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1277 next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1289 const struct rb_node *self;
1304 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1305 rb_tree_check_node(rbt, self, prev, false);
1322 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1323 rb_tree_check_node(rbt, self, NULL, true);
1331 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
1334 if (RB_SENTINEL_P(self))
1337 if (RB_TWOCHILDREN_P(self)) {
1338 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1339 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
1343 if (!RB_LEFT_SENTINEL_P(self)) {
1344 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1346 if (!RB_RIGHT_SENTINEL_P(self)) {
1347 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);