Lines Matching defs:self
177 rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
201 const signed int diff = (*compare_nodes)(tmp, self);
233 KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
234 KASSERT(next == NULL || (*compare_nodes)(self, next) > 0);
241 RB_SET_FATHER(self, parent);
242 RB_SET_POSITION(self, position);
244 RB_MARK_BLACK(self); /* root is always black */
246 rbt->rbt_minmax[RB_DIR_LEFT] = self;
247 rbt->rbt_minmax[RB_DIR_RIGHT] = self;
259 rbt->rbt_minmax[position] = self;
265 RB_MARK_RED(self);
269 self->rb_left = parent->rb_nodes[position];
270 self->rb_right = parent->rb_nodes[position];
271 parent->rb_nodes[position] = self;
272 KASSERT(RB_CHILDLESS_P(self));
279 if (RB_ROOT_P(rbt, self)) {
280 RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
282 KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
283 RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
285 KASSERT((*compare_nodes)(RB_FATHER(self), self) > 0);
286 RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
287 self, rb_link);
290 KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
296 rb_tree_insert_rebalance(rbt, self);
297 KASSERT(rb_tree_check_node(rbt, self, NULL, true));
305 * Swap the location and colors of 'self' and its child @ which. The child
376 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
378 struct rb_node * father = RB_FATHER(self);
384 KASSERT(!RB_ROOT_P(rbt, self));
385 KASSERT(RB_RED_P(self));
390 KASSERT(!RB_SENTINEL_P(self));
392 KASSERT(RB_RED_P(self));
426 self = grandpa;
427 father = RB_FATHER(self);
428 KASSERT(RB_RED_P(self));
438 KASSERT(!RB_ROOT_P(rbt, self));
439 KASSERT(RB_RED_P(self));
446 if (self == father->rb_nodes[other]) {
454 KASSERT(RB_FATHER(father) == self);
455 KASSERT(self->rb_nodes[which] == father);
456 KASSERT(RB_FATHER(self) == grandpa);
457 self = father;
458 father = RB_FATHER(self);
460 KASSERT(RB_RED_P(self) && RB_RED_P(father));
469 KASSERT(RB_FATHER(self) == father);
470 KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
471 KASSERT(RB_RED_P(self));
483 rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
485 const unsigned int which = RB_POSITION(self);
486 struct rb_node *father = RB_FATHER(self);
487 const bool was_root = RB_ROOT_P(rbt, self);
489 KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
490 KASSERT(!rebalance || RB_BLACK_P(self));
491 KASSERT(RB_CHILDLESS_P(self));
492 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
495 * Since we are childless, we know that self->rb_left is pointing
498 father->rb_nodes[which] = self->rb_left;
504 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
507 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
508 rbt->rbt_minmax[RB_POSITION(self)] = father;
518 RB_SET_FATHER(self, NULL);
534 rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
543 if (standin_father == self) {
545 * As a child of self, any childen would be opposite of
552 * Since we aren't a child of self, any childen would be
562 KASSERT(RB_TWOCHILDREN_P(self));
571 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
583 if (standin_father == self) {
595 if (standin_father == self) {
608 KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
609 KASSERT(self->rb_nodes[standin_which] == standin);
626 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
628 KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
640 KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
641 standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
645 * Now copy the result of self to standin and then replace
646 * self with standin in the tree.
648 RB_COPY_PROPERTIES(standin, self);
649 RB_SET_FATHER(standin, RB_FATHER(self));
656 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
659 if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
660 rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
661 RB_SET_FATHER(self, NULL);
681 * rb_tree_node_swap(rbt, self, which);
682 * rb_tree_prune_node(rbt, self, false);
687 rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
690 struct rb_node *father = RB_FATHER(self);
691 struct rb_node *son = self->rb_nodes[which];
692 const bool was_root = RB_ROOT_P(rbt, self);
695 KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
698 KASSERT(rb_tree_check_node(rbt, self, NULL, false));
705 RB_COPY_PROPERTIES(son, self);
713 RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
719 } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
720 rbt->rbt_minmax[RB_POSITION(self)] = son;
722 RB_SET_FATHER(self, NULL);
732 rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
737 KASSERT(!RB_SENTINEL_P(self));
757 if (RB_CHILDLESS_P(self)) {
758 const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
759 rb_tree_prune_node(rbt, self, rebalance);
762 KASSERT(!RB_CHILDLESS_P(self));
763 if (!RB_TWOCHILDREN_P(self)) {
772 which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
773 KASSERT(RB_BLACK_P(self));
774 KASSERT(RB_RED_P(self->rb_nodes[which]));
775 KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
776 rb_tree_prune_blackred_branch(rbt, self, which);
779 KASSERT(RB_TWOCHILDREN_P(self));
785 which = RB_POSITION(self) ^ RB_DIR_OTHER;
791 standin = rb_tree_iterate(rbt, self, which);
792 rb_tree_swap_prune_and_rebalance(rbt, self, standin);
947 rb_tree_iterate(struct rb_tree *rbt, struct rb_node *self,
953 if (self == NULL) {
959 self = rbt->rbt_root;
960 if (RB_SENTINEL_P(self))
962 while (!RB_SENTINEL_P(self->rb_nodes[other]))
963 self = self->rb_nodes[other];
964 return self;
967 KASSERT(!RB_SENTINEL_P(self));
972 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
973 while (!RB_ROOT_P(rbt, self)) {
974 if (other == RB_POSITION(self))
975 return RB_FATHER(self);
976 self = RB_FATHER(self);
985 self = self->rb_nodes[direction];
986 KASSERT(!RB_SENTINEL_P(self));
987 while (!RB_SENTINEL_P(self->rb_nodes[other]))
988 self = self->rb_nodes[other];
989 return self;
994 rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
1000 if (self == NULL) {
1006 self = rbt->rbt_root;
1007 if (RB_SENTINEL_P(self))
1009 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1010 self = self->rb_nodes[other];
1011 return self;
1014 KASSERT(!RB_SENTINEL_P(self));
1019 if (RB_SENTINEL_P(self->rb_nodes[direction])) {
1020 while (!RB_ROOT_P(rbt, self)) {
1021 if (other == RB_POSITION(self))
1022 return RB_FATHER(self);
1023 self = RB_FATHER(self);
1032 self = self->rb_nodes[direction];
1033 KASSERT(!RB_SENTINEL_P(self));
1034 while (!RB_SENTINEL_P(self->rb_nodes[other]))
1035 self = self->rb_nodes[other];
1036 return self;
1040 rb_tree_count_black(const struct rb_node *self)
1044 if (RB_SENTINEL_P(self))
1047 left = rb_tree_count_black(self->rb_left);
1048 right = rb_tree_count_black(self->rb_right);
1052 return left + RB_BLACK_P(self);
1056 rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
1061 KASSERT(!RB_SENTINEL_P(self));
1062 KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
1067 if (RB_ROOT_P(rbt, self)) {
1068 KASSERT(self == rbt->rbt_root);
1069 KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
1070 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1071 KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
1073 KASSERT(self != rbt->rbt_root);
1074 KASSERT(!RB_FATHER_SENTINEL_P(self));
1075 if (RB_POSITION(self) == RB_DIR_LEFT) {
1076 KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
1077 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
1079 KASSERT((*compare_nodes)(self, RB_FATHER(self)) < 0);
1080 KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
1088 const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1089 const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1090 KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
1091 KASSERT(next0 == TAILQ_NEXT(self, rb_link));
1093 KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
1094 KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
1103 KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
1104 (void) rb_tree_count_black(self);
1105 if (RB_RED_P(self)) {
1107 KASSERT(!RB_ROOT_P(rbt, self));
1108 brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
1109 KASSERT(RB_BLACK_P(RB_FATHER(self)));
1115 KASSERT(!RB_CHILDLESS_P(self)
1123 KASSERT(RB_CHILDLESS_P(self)
1124 || (RB_TWOCHILDREN_P(self)
1125 && RB_BLACK_P(self->rb_left)
1126 && RB_BLACK_P(self->rb_right)));
1132 KASSERT(RB_CHILDLESS_P(self)
1142 KASSERT(RB_CHILDLESS_P(self)
1143 || RB_TWOCHILDREN_P(self)
1144 || (!RB_LEFT_SENTINEL_P(self)
1145 && RB_RIGHT_SENTINEL_P(self)
1146 && RB_RED_P(self->rb_left)
1147 && RB_CHILDLESS_P(self->rb_left))
1148 || (!RB_RIGHT_SENTINEL_P(self)
1149 && RB_LEFT_SENTINEL_P(self)
1150 && RB_RED_P(self->rb_right)
1151 && RB_CHILDLESS_P(self->rb_right)));
1158 if (!RB_ROOT_P(rbt, self)
1159 && RB_CHILDLESS_P(self)
1160 && RB_BLACK_P(RB_FATHER(self))) {
1161 const unsigned int which = RB_POSITION(self);
1166 self, other);
1184 KASSERT(RB_ROOT_P(rbt, self)
1185 || RB_ROOT_P(rbt, RB_FATHER(self))
1186 || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
1191 KASSERT(RB_LEFT_SENTINEL_P(self)
1192 || RB_CHILDLESS_P(self->rb_left)
1193 || !RB_RIGHT_SENTINEL_P(self));
1198 KASSERT(RB_RIGHT_SENTINEL_P(self)
1199 || RB_CHILDLESS_P(self->rb_right)
1200 || !RB_LEFT_SENTINEL_P(self));
1207 KASSERT(RB_TWOCHILDREN_P(self->rb_left)
1208 || RB_CHILDLESS_P(self->rb_right)
1209 || RB_CHILDLESS_P(self->rb_right->rb_left)
1210 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
1211 || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
1212 || RB_CHILDLESS_P(self->rb_right->rb_right)
1213 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
1214 || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
1221 KASSERT(RB_TWOCHILDREN_P(self->rb_right)
1222 || RB_CHILDLESS_P(self->rb_left)
1223 || RB_CHILDLESS_P(self->rb_left->rb_left)
1224 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
1225 || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
1226 || RB_CHILDLESS_P(self->rb_left->rb_right)
1227 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
1228 || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
1234 if (RB_TWOCHILDREN_P(self)) {
1238 prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
1242 next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
1254 const struct rb_node *self;
1269 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1270 rb_tree_check_node(rbt, self, prev, false);
1287 TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
1288 rb_tree_check_node(rbt, self, NULL, true);
1296 rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
1299 if (RB_SENTINEL_P(self))
1302 if (RB_TWOCHILDREN_P(self)) {
1303 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1304 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
1308 if (!RB_LEFT_SENTINEL_P(self)) {
1309 rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
1311 if (!RB_RIGHT_SENTINEL_P(self)) {
1312 rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);