Lines Matching refs:self
188 struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
244 RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
246 RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
253 RB_SET_FATHER(self, parent);
254 RB_SET_POSITION(self, position);
256 RB_MARK_BLACK(self); /* root is always black */
258 rbt->rbt_minmax[RB_DIR_LEFT] = self;
259 rbt->rbt_minmax[RB_DIR_RIGHT] = self;
271 rbt->rbt_minmax[position] = self;
277 RB_MARK_RED(self);
281 self->rb_left = parent->rb_nodes[position];
282 self->rb_right = parent->rb_nodes[position];
283 parent->rb_nodes[position] = self;
284 KASSERT(RB_CHILDLESS_P(self));
291 if (RB_ROOT_P(rbt, self)) {
292 RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
295 RB_NODETOITEM(rbto, self),
296 RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
297 RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
300 RB_NODETOITEM(rbto, RB_FATHER(self)),
301 RB_NODETOITEM(rbto, self)) < 0);
302 RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
303 self, rb_link);
306 KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
312 rb_tree_insert_rebalance(rbt, self);
313 KASSERT(rb_tree_check_node(rbt, self, NULL, true));
321 * Swap the location and colors of 'self' and its child @ which. The child
392 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
394 struct rb_node * father = RB_FATHER(self);
400 KASSERT(!RB_ROOT_P(rbt, self));
401 KASSERT(RB_RED_P(self));
406 KASSERT(!RB_SENTINEL_P(self));
408 KASSERT(RB_RED_P(self));
442 self = grandpa;
443 father = RB_FATHER(self);
444 KASSERT(RB_RED_P(self));
454 KASSERT(!RB_ROOT_P(rbt, self));
455 KASSERT(RB_RED_P(self));
462 if (self == father->rb_nodes[other]) {
470 KASSERT(RB_FATHER(father) == self);
471 KASSERT(self->rb_nodes[which] == father);
472 KASSERT(RB_FATHER(self) == grandpa);
473 self = father;
474 father = RB_FATHER(self);
476 KASSERT(RB_RED_P(self) && RB_RED_P(father));
485 KASSERT(RB_FATHER(self) == father);
486 KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
487 KASSERT(RB_RED_P(self));
498 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
500 const unsigned int which = RB_POSITION(self);
501 struct rb_node *father = RB_FATHER(self);
503 const bool was_root = RB_ROOT_P(rbt, self);
506 KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
507 KASSERT(!rebalance || RB_BLACK_P(self));
508 KASSERT(RB_CHILDLESS_P(self));
509 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
512 * Since we are childless, we know that self->rb_left is pointing
515 father->rb_nodes[which] = self->rb_left;
521 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
524 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
525 rbt->rbt_minmax[RB_POSITION(self)] = father;
535 RB_SET_FATHER(self, NULL);
550 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
559 if (standin_father == self) {
561 * As a child of self, any childen would be opposite of
568 * Since we aren't a child of self, any childen would be
578 KASSERT(RB_TWOCHILDREN_P(self));
587 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
599 if (standin_father == self) {
611 if (standin_father == self) {
624 KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
625 KASSERT(self->rb_nodes[standin_which] == standin);
642 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
644 KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
656 KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
657 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
661 * Now copy the result of self to standin and then replace
662 * self with standin in the tree.
664 RB_COPY_PROPERTIES(standin, self);
665 RB_SET_FATHER(standin, RB_FATHER(self));
672 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
675 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
676 rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
677 RB_SET_FATHER(self, NULL);
697 * rb_tree_node_swap(rbt, self, which);
698 * rb_tree_prune_node(rbt, self, false);
703 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
706 struct rb_node *father = RB_FATHER(self);
707 struct rb_node *son = self->rb_nodes[which];
709 const bool was_root = RB_ROOT_P(rbt, self);
713 KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
716 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
723 RB_COPY_PROPERTIES(son, self);
731 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
737 } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
738 rbt->rbt_minmax[RB_POSITION(self)] = son;
740 RB_SET_FATHER(self, NULL);
751 struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
754 KASSERT(!RB_SENTINEL_P(self));
774 if (RB_CHILDLESS_P(self)) {
775 const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
776 rb_tree_prune_node(rbt, self, rebalance);
779 KASSERT(!RB_CHILDLESS_P(self));
780 if (!RB_TWOCHILDREN_P(self)) {
789 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
790 KASSERT(RB_BLACK_P(self));
791 KASSERT(RB_RED_P(self->rb_nodes[which]));
792 KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
793 rb_tree_prune_blackred_branch(rbt, self, which);
796 KASSERT(RB_TWOCHILDREN_P(self));
802 which = RB_POSITION(self) ^ RB_DIR_OTHER;
809 rb_tree_swap_prune_and_rebalance(rbt, self, standin);
968 struct rb_node *self;
978 self = rbt->rbt_root;
979 if (RB_SENTINEL_P(self))
981 while (!RB_SENTINEL_P(self->rb_nodes[direction]))
982 self = self->rb_nodes[direction];
983 return RB_NODETOITEM(rbto, self);
986 self = RB_ITEMTONODE(rbto, object);
987 KASSERT(!RB_SENTINEL_P(self));
992 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
993 while (!RB_ROOT_P(rbt, self)) {
994 if (other == RB_POSITION(self))
995 return RB_NODETOITEM(rbto, RB_FATHER(self));
996 self = RB_FATHER(self);
1005 self = self->rb_nodes[direction];
1006 KASSERT(!RB_SENTINEL_P(self));
1007 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1008 self = self->rb_nodes[other];
1009 return RB_NODETOITEM(rbto, self);
1014 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
1020 if (self == NULL) {
1026 self = rbt->rbt_root;
1027 if (RB_SENTINEL_P(self))
1029 while (!RB_SENTINEL_P(self->rb_nodes[direction]))
1030 self = self->rb_nodes[direction];
1031 return self;
1034 KASSERT(!RB_SENTINEL_P(self));
1039 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
1040 while (!RB_ROOT_P(rbt, self)) {
1041 if (other == RB_POSITION(self))
1042 return RB_FATHER(self);
1043 self = RB_FATHER(self);
1052 self = self->rb_nodes[direction];
1053 KASSERT(!RB_SENTINEL_P(self));
1054 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1055 self = self->rb_nodes[other];
1056 return self;
1060 rb_tree_count_black(const struct rb_node *self)
1064 if (RB_SENTINEL_P(self))
1067 left = rb_tree_count_black(self->rb_left);
1068 right = rb_tree_count_black(self->rb_right);
1072 return left + RB_BLACK_P(self);
1076 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
1082 KASSERT(!RB_SENTINEL_P(self));
1084 RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
1089 if (RB_ROOT_P(rbt, self)) {
1090 KASSERT(self == rbt->rbt_root);
1091 KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
1092 KASSERT(RB_FATHER(selfself);
1093 KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
1096 RB_NODETOITEM(rbto, self),
1097 RB_NODETOITEM(rbto, RB_FATHER(self)));
1099 KASSERT(self != rbt->rbt_root);
1100 KASSERT(!RB_FATHER_SENTINEL_P(self));
1101 if (RB_POSITION(self) == RB_DIR_LEFT) {
1103 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1106 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
1114 const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1115 const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1116 KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
1117 KASSERT(next0 == TAILQ_NEXT(self, rb_link));
1119 KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
1120 KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
1129 KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
1130 (void) rb_tree_count_black(self);
1131 if (RB_RED_P(self)) {
1133 KASSERT(!RB_ROOT_P(rbt, self));
1134 brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
1135 KASSERT(RB_BLACK_P(RB_FATHER(self)));
1141 KASSERT(!RB_CHILDLESS_P(self)
1149 KASSERT(RB_CHILDLESS_P(self)
1150 || (RB_TWOCHILDREN_P(self)
1151 && RB_BLACK_P(self->rb_left)
1152 && RB_BLACK_P(self->rb_right)));
1158 KASSERT(RB_CHILDLESS_P(self)
1168 KASSERT(RB_CHILDLESS_P(self)
1169 || RB_TWOCHILDREN_P(self)
1170 || (!RB_LEFT_SENTINEL_P(self)
1171 && RB_RIGHT_SENTINEL_P(self)
1172 && RB_RED_P(self->rb_left)
1173 && RB_CHILDLESS_P(self->rb_left))
1174 || (!RB_RIGHT_SENTINEL_P(self)
1175 && RB_LEFT_SENTINEL_P(self)
1176 && RB_RED_P(self->rb_right)
1177 && RB_CHILDLESS_P(self->rb_right)));
1184 if (!RB_ROOT_P(rbt, self)
1185 && RB_CHILDLESS_P(self)
1186 && RB_BLACK_P(RB_FATHER(self))) {
1187 const unsigned int which = RB_POSITION(self);
1192 self, other);
1210 KASSERT(RB_ROOT_P(rbt, self)
1211 || RB_ROOT_P(rbt, RB_FATHER(self))
1212 || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
1217 KASSERT(RB_LEFT_SENTINEL_P(self)
1218 || RB_CHILDLESS_P(self->rb_left)
1219 || !RB_RIGHT_SENTINEL_P(self));
1224 KASSERT(RB_RIGHT_SENTINEL_P(self)
1225 || RB_CHILDLESS_P(self->rb_right)
1226 || !RB_LEFT_SENTINEL_P(self));
1233 KASSERT(RB_TWOCHILDREN_P(self->rb_left)
1234 || RB_CHILDLESS_P(self->rb_right)
1235 || RB_CHILDLESS_P(self->rb_right->rb_left)
1236 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
1237 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
1238 || RB_CHILDLESS_P(self->rb_right->rb_right)
1239 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
1240 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
1247 KASSERT(RB_TWOCHILDREN_P(self->rb_right)
1248 || RB_CHILDLESS_P(self->rb_left)
1249 || RB_CHILDLESS_P(self->rb_left->rb_left)
1250 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
1251 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
1252 || RB_CHILDLESS_P(self->rb_left->rb_right)
1253 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
1254 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
1260 if (RB_TWOCHILDREN_P(self)) {
1264 prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1268 next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1280 const struct rb_node *self;
1295 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1296 rb_tree_check_node(rbt, self, prev, false);
1313 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1314 rb_tree_check_node(rbt, self, NULL, true);
1322 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
1325 if (RB_SENTINEL_P(self))
1328 if (RB_TWOCHILDREN_P(self)) {
1329 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1330 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
1334 if (!RB_LEFT_SENTINEL_P(self)) {
1335 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1337 if (!RB_RIGHT_SENTINEL_P(self)) {
1338 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
Indexes created Sun Oct 19 02:09:48 GMT 2025