freebsd rb.h remove を読んでみよう5
今回はrb.hのremoveを読んでいきましょう
a_attr void \
a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
struct { \
a_type *node; \
int cmp; \
} *pathp, *nodep, path[sizeof(void *) << 4]; \
/* Wind. */ \
nodep = NULL; /* Silence compiler warning. */ \
path->node = rbtree->rbt_root; \
for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
int cmp = pathp->cmp = a_cmp(node, pathp->node); \
if (cmp < 0) { \
pathp[1].node = rbtn_left_get(a_type, a_field, \
pathp->node); \
} else { \
pathp[1].node = rbtn_right_get(a_type, a_field, \
pathp->node); \
if (cmp == 0) { \
/* Find node's successor, in preparation for swap. */ \
pathp->cmp = 1; \
nodep = pathp; \
for (pathp++; pathp->node != &rbtree->rbt_nil; \
pathp++) { \
pathp->cmp = -1; \
pathp[1].node = rbtn_left_get(a_type, a_field, \
pathp->node); \
} \
break; \
} \
} \
} \
assert(nodep->node == node); \
pathp--; \
if (pathp->node != node) { \
/* Swap node with its successor. */ \
bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
rbtn_color_set(a_type, a_field, pathp->node, \
rbtn_red_get(a_type, a_field, node)); \
rbtn_left_set(a_type, a_field, pathp->node, \
rbtn_left_get(a_type, a_field, node)); \
/* If node's successor is its right child, the following code */\
/* will do the wrong thing for the right child pointer. */\
/* However, it doesn't matter, because the pointer will be */\
/* properly set when the successor is pruned. */\
rbtn_right_set(a_type, a_field, pathp->node, \
rbtn_right_get(a_type, a_field, node)); \
rbtn_color_set(a_type, a_field, node, tred); \
/* The pruned leaf node's child pointers are never accessed */\
/* again, so don't bother setting them to nil. */\
nodep->node = pathp->node; \
pathp->node = node; \
if (nodep == path) { \
rbtree->rbt_root = nodep->node; \
} else { \
if (nodep[-1].cmp < 0) { \
rbtn_left_set(a_type, a_field, nodep[-1].node, \
nodep->node); \
} else { \
rbtn_right_set(a_type, a_field, nodep[-1].node, \
nodep->node); \
} \
} \
} else { \
a_type *left = rbtn_left_get(a_type, a_field, node); \
if (left != &rbtree->rbt_nil) { \
/* node has no successor, but it has a left child. */\
/* Splice node out, without losing the left child. */\
assert(rbtn_red_get(a_type, a_field, node) == false); \
assert(rbtn_red_get(a_type, a_field, left)); \
rbtn_black_set(a_type, a_field, left); \
if (pathp == path) { \
rbtree->rbt_root = left; \
} else { \
if (pathp[-1].cmp < 0) { \
rbtn_left_set(a_type, a_field, pathp[-1].node, \
left); \
} else { \
rbtn_right_set(a_type, a_field, pathp[-1].node, \
left); \
} \
} \
return; \
} else if (pathp == path) { \
/* The tree only contained one node. */ \
rbtree->rbt_root = &rbtree->rbt_nil; \
return; \
} \
}
insertの時と同じようにまずはターゲットとなるノードまでの
ノードを配列に入れていきます。
pathpにその配列の先頭のアドレスがありそれをpathp++でループしていきます。
path->node = rbtree->rbt_root;
for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {
ループ内ではa_cmpを呼び出しその戻り値がマイナスの時(小さい時)は
pathpのノードの左の子を逆の場合はpathpのノードの右の子をpathpの配列の
次のindexに入れます。
int cmp = pathp->cmp = a_cmp(node, pathp->node);
if (cmp < 0) {
pathp[1].node = rbtn_left_get(a_type, a_field, pathp->node);
} else {
pathp[1].node = rbtn_right_get(a_type, a_field, pathp->node);
cmpがゼロの時すなわちpathp->nodeがターゲットのノード(ここでは削除されるべきノード)の時cmpを1にし(右側にあるノードが次に来る)そのポインターをnodepに格納します。
pathp->cmp = 1; nodep = pathp;
そのあとpathpを一つ進めます。つまり削除されるべきノードの右の子供をpathpが指しています。
そこから左の子のノードをpathpの配列にnilになるまで入れていきます。
左の子がnilのノードに来たらbreakします。
for (pathp++; pathp->node != &rbtree->rbt_nil; pathp++) {
pathp->cmp = -1;
pathp[1].node = rbtn_left_get(a_type, a_field, pathp->node);
}
break;
ここでpathpはforを出る時にnilのノードのを指しているので
まずは一つ巻き戻します。
pathp--;
pathpは何を指しているのでしょうか？
もし削除されるべきノードの右の子がnilだった場合
このループには入りません。
for (pathp++; pathp->node != &rbtree->rbt_nil; pathp++) {
ただ最初のpathp++は実行されるので次のpathp--と合わせてpathpは
削除されるノードのpathpを指しています。
そこで次の条件で分岐されます。
if (pathp->node != node) {
削除されるノード(node)とpathpの指しているノードが違うなら
つまり削除されるノードの右の子がnilでないならと読みかえられます。
削除されるノードの右の子がある場合どうなるのでしょう。
コメントに
/* Swap node with its successor. */
とあります。何をするのでしょうか？
一行づつ読んでみましょう。
bool tred = rbtn_red_get(a_type, a_field, pathp->node); //pathp->nodeの色が赤かどうかを保存します。 rbtn_color_set(a_type, a_field, pathp->node, rbtn_red_get(a_type, a_field, node)); //pathpのノードに削除されるノードの色をセットします。 rbtn_left_set(a_type, a_field, pathp->node, rbtn_left_get(a_type, a_field, node)); //削除されるノードの左の子をpathpのノードの左にセットします。 rbtn_right_set(a_type, a_field, pathp->node, rbtn_right_get(a_type, a_field, node)); //削除されるノードの右の子をpathpのノードの右にセットします。 rbtn_color_set(a_type, a_field, node, tred); //保存していたpathpのノードの色を削除されるノードの色にセットします。 nodep->node = pathp->node; //削除されるノードのあったアドレスのノードにpathpのノードを入れます。 pathp->node = node; //pathpのノードに削除されるノードを入れます。
これが
こうなるということです。
色は省略していますが同じ色になるように色も交換しています。
そしてこのあとこのnodepがpathすなわちpath配列の先頭かどうかをチェックして
そうならnodepのノード(4番)をルートにします。
そうでないならnodepの一つ前のindex(親ノード)のcmpによってcmpがマイナスなら
左に逆なら右につけます。
これでスワップが完了です。
ところで
/* If node's successor is its right child, the following code */
/* will do the wrong thing for the right child pointer. */
/* However, it doesn't matter, because the pointer will be */
/* properly set when the successor is pruned. */
このコメントはどういう意味でしょうか？
もし削除されるノードの次のノードが右の子のノードならおかしなことになると言っています。
つまりこれは削除されるノードが右に子のノードがあってその子のノードに左の子が一つもない場合のことを言っています。
これはこういう場合のことでしょう
確かに
rbtn_right_set(a_type, a_field, pathp->node, rbtn_right_get(a_type, a_field, node));
で自分自身を自分の右の子にしてしまうことになってしまいます。
しかしその後pathpのノードに削除されるノードが入るので問題ないと言っています。
それでは次回は削除されるノードの右がnilの場合を見ていきましょう。
お疲れ様でした。
