freebsd rb.h insert を読んでみよう

前に赤黒木に挿入するときは赤が２つ来るのを防ぐように調節すると書きました。

それがfreebsdのmallocではどのように実装されているのかを見てみましょう。

freebsdは9.3です。rb.hは/usr/src/lib/libc/stdlib内にありますね。

    a_attr void								\
a_prefix##insert(a_rbt_type *rbtree, a_type *node) {			\
    struct {								\
	a_type *node;							\
	int cmp;							\
    } path[sizeof(void *) << 4], *pathp;				\
    rbt_node_new(a_type, a_field, rbtree, node);			\
    /* Wind. */								\
    path->node = rbtree->rbt_root;					\
    for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {	\
	int cmp = pathp->cmp = a_cmp(node, pathp->node);		\
	assert(cmp != 0);						\
	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);						\
	}								\
    }									\
    pathp->node = node;							\
    /* Unwind. */							\
    for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {	\
	a_type *cnode = pathp->node;					\
	if (pathp->cmp < 0) {						\
	    a_type *left = pathp[1].node;				\
	    rbtn_left_set(a_type, a_field, cnode, left);		\
	    if (rbtn_red_get(a_type, a_field, left)) {			\
		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
		    /* Fix up 4-node. */				\
		    a_type *tnode;					\
		    rbtn_black_set(a_type, a_field, leftleft);		\
		    rbtn_rotate_right(a_type, a_field, cnode, tnode);	\
		    cnode = tnode;					\
		}							\
	    } else {							\
		return;							\
	    }								\
	} else {							\
	    a_type *right = pathp[1].node;				\
	    rbtn_right_set(a_type, a_field, cnode, right);		\
	    if (rbtn_red_get(a_type, a_field, right)) {			\
		a_type *left = rbtn_left_get(a_type, a_field, cnode);	\
		if (rbtn_red_get(a_type, a_field, left)) {		\
		    /* Split 4-node. */					\
		    rbtn_black_set(a_type, a_field, left);		\
		    rbtn_black_set(a_type, a_field, right);		\
		    rbtn_red_set(a_type, a_field, cnode);		\
		} else {						\
		    /* Lean left. */					\
		    a_type *tnode;					\
		    bool tred = rbtn_red_get(a_type, a_field, cnode);	\
		    rbtn_rotate_left(a_type, a_field, cnode, tnode);	\
		    rbtn_color_set(a_type, a_field, tnode, tred);	\
		    rbtn_red_set(a_type, a_field, cnode);		\
		    cnode = tnode;					\
		}							\
	    } else {							\
		return;							\
	    }								\
	}								\
	pathp->node = cnode;						\
    }									\
    /* Set root, and make it black. */					\
    rbtree->rbt_root = path->node;					\
    rbtn_black_set(a_type, a_field, rbtree->rbt_root);			\
}

という感じです。読みやすくはないですね。

/* Unwind. */　までは赤黒木を準備しているところです。cmpでの比較を使って

右左と入れていきます。

肝心なのは/* Unwind. */以降ですね。

まず挿入されるnodeをpathp->node にいれています。これは一番後ろ（下）の

ノードでここからrootへ遡っていきます。

 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {    \

このループの中でのnodeがcnodeです。current nodeでしょうか。

ループ内ではまず (pathp->cmp < 0) によって場合分けされます。

では読んで行きましょう。

pathp->cmp <0 //今のノードのcmpがマイナスの時

a_type *left = pathp[1].node; //今のノードの次の（下の）ノードを

rbtn_left_set(a_type, a_field, cnode, left);       //今のノードの左にセットします。

if (rbtn_red_get(a_type, a_field, left)) {            //そしてその左のノードが赤で
       a_type *leftleft = rbtn_left_get(a_type, a_field, left);
       if (rbtn_red_get(a_type, a_field, leftleft)) {  //その左のノードの左の子ノードが赤なら

rbtn_black_set(a_type, a_field, leftleft);        //左の左子ノードを黒にします
            rbtn_rotate_right(a_type, a_field, cnode, tnode);    //右に回します
            cnode = tnode;  //回した後の親ノードをcnodeにします。

これは前にやった２番のタイプ（赤の左の子が赤）です。赤黒木をやってみよう 2 - yamshing's diary

　　　黒

          /

　　赤

       /

　赤

これの最後を黒にして右に回すと

　　　  赤

            /      \

　　黒　　黒

これで赤が２個になることが解消されます。

ここで一休み次回は右に赤が来る場合を見て行きましょう。