Linux カーネルの rbtree：比較関数を保持せず、ノードを構造体に埋め込む赤黒木

Linux カーネルの赤黒木には rb_insert(tree, key, value) のような関数がありません。木が比較関数を登録して保持しておく場所もありません。基本の API では、木を下りながら左右を決めるループを使う側が自分で書き、ライブラリが受け持つのはその後の色の付け替えと回転だけです。v6.17 のヘッダーにはこのループを代わりに回すインラインのヘルパーもありますが、これらも比較関数を保持せず、呼び出すたびに引数として受け取ります。

教科書と同じ赤黒木なのに API の形がここまで違う理由と、その形から生まれる選択肢を整理します。対象は Linux v6.17 の Documentation/core-api/rbtree.rst、include/linux/rbtree.h、include/linux/rbtree_augmented.h、lib/rbtree.c です。

コールバックをやめてループを渡した理由

カーネルのドキュメントは、この実装が速度向けに最適化されていると説明しています。ノードとデータを別々に持ってポインタでつなぐ代わりに、struct rb_node をデータ構造体の中に埋め込むので、間接参照が一段少なく、キャッシュの局所性もよくなるということです。木が比較コールバックの関数ポインタを持っていて呼び出すのではなく、探索・挿入関数を利用者に書かせるのも同じ理由です。Andrea Arcangeli の 1999 年の著作権表示がある rbtree.h の冒頭コメントには、コールバックを使うと性能が大きく落ちるので、C で性能と汎用性を両立するにはこの形にするしかないと書かれています。ロックも利用者に任されています。

ドキュメントは他のカーネルのデータ構造とも比べています。ハッシュテーブルはソート状態が保たれないので順番にたどりにくく、特定のサイズとハッシュ関数に合わせて調整が必要です。rbtree は任意のキーを格納しつつ、規模が大きくなっても無理なく動くとしています。ハッシュテーブルの最悪ケースについてはハッシュテーブルが O(1) でなくなるときで扱いました。

ノードはデータの中にある

木に入れる構造体は struct rb_node メンバーを持ちます。

struct mytype {
	struct rb_node node;
	char *keystring;
};

struct rb_root mytree = RB_ROOT;

木の関数がやり取りするのは struct rb_node * だけです。そこから外側の構造体を得るには、container_of() か、同じ働きをする rb_entry(node, type, member) マクロを使います。キーがどこにあってどんな型なのか、木はまったく知りません。

探索は、根から始めて比較結果に応じて rb_left か rb_right をたどる普通の二分探索木の探索です。ドキュメントの例も、strcmp の結果で向きを決める while ループひとつです。

挿入は二段階に分かれる

挿入は、新しいノードをつなぐ場所を探す作業と、つないだ後でバランスを取る作業に分かれます。ドキュメントの例がしていることを疑似コードにするとこうなります。

link   = 根へのリンクのアドレス        （struct rb_node ** 型）
parent = なし
link が指すノード cur がある間:
    parent = cur
    新しいキー < cur のキー  →  link = cur の左リンクのアドレス
    新しいキー > cur のキー  →  link = cur の右リンクのアドレス
    等しい                   →  失敗を返す（同じキーがすでにある）

ステップ 1: rb_link_node(新しいノード, parent, link)   空き場所につなぐ
ステップ 2: rb_insert_color(新しいノード, root)        色の修正と回転

ドキュメントの C の例では、container_of() で cur の外側の構造体を得て、strcmp でキーを比べます。探索との違いは、ノードではなくノードを指すポインタのアドレス（struct rb_node **）をたどることです。ループを抜けると、link は新しいノードを書き込む空き場所を指しています。rb_link_node() は新しいノードに親を記録し、子を両方 NULL にしてから、その場所にノードを書き込みます。続く rb_insert_color() が色を直し、必要なら回転します。

同じキーに出会ったときの扱いも、このループが決めます。上の例は失敗を返しますが、重複を許したいなら片側に下り続けるように書けば済みます。

v6.17 のヘッダーにあるヘルパー

毎回ループを書かなくて済むように、v6.17 の rbtree.h には比較関数を呼び出しごとに引数で受け取るヘルパーがあります。木が比較関数を保持するわけではないので、同じ木には毎回一貫した比較関数を渡す必要があります。下の表のうち rb_for_each() だけは for ループに展開されるプリプロセッサマクロで、残りは static __always_inline 関数です。

名前	種類	比較の引数	動作
rb_add()	インライン関数	less(a, b)	ノードを挿入。戻り値なし
rb_find_add()	インライン関数	cmp(a, b)	cmp が 0 になるノードがあればそれを返し、なければ挿入して NULL を返す
rb_find()	インライン関数	cmp(key, node)	キーに一致するノード、または NULL
rb_find_first()	インライン関数	cmp(key, node)	一致するノードのうち最も左のもの
rb_for_each()	マクロ	cmp(key, node)	一致するノードを順にたどる（rb_find_first() と rb_next_match() を使う）

ヘッダーのコメントは、cmp(a->key, b) < 0 が less(a, b) と同じ意味になる、という形で二つの演算子の関係を定義しています。演算子が半順序しか定めない場合、一致する要素のどれを rb_find() が見つけるかは保証しないとも書かれています。キーだけを渡すこの形にした理由は、比較のためだけにスタック上へダミーのオブジェクトを作らずに済むようにするためで、オブジェクトが大きいとそれが難しい場合があるからだと説明しています。

rb_add() のループは、less(node, parent) が真のときだけ左へ進み、等しければ右へ進みます。ここから言える性質があります（コードから導いたもので、コメントに書かれた保証ではありません）。木全体を rb_add() と一貫した less で作っていれば、新しいノードはソート順で、同じキーを持つ既存のノードすべての後ろに入ります。回転はソート順を変えないので、この並びは保たれます。同じキーの最初の要素が欲しいときに rb_find() ではなく rb_find_first() を使うのも同じ理由です。

色は親ポインタの下位ビットにある

rb_node には色用のフィールドが見当たりません。rbtree.h と rbtree_augmented.h のマクロを見ると、親ポインタと色は __rb_parent_color という unsigned long ひとつに同居しています。

__rb_parent_color（unsigned long ひとつ）
[ 親ノードのアドレス ...... | b1 | b0 ]   b1, b0 = 下位 2 ビット
rb_parent(r) = 値 & ~3   下位 2 ビットを消して親のアドレスを得る
rb_color(r)  = 値 & 1    ビット 0 が色（RB_RED = 0、RB_BLACK = 1）

この方法は、ノードのアドレスの下位 2 ビットが常に 0 であるという前提でしか成り立ちません。そのアラインメントを保証する struct rb_node の定義は rbtree_types.h にありますが、この記事で確認したファイルには含まれていません。

同じフィールドは「どの木にも入っていないノード」の目印にも使われます。RB_CLEAR_NODE(node) はこの値をノード自身のアドレスにし、RB_EMPTY_NODE(node) はその状態かどうかを調べます。rb_next() と rb_prev() はそういうノードを渡されると NULL を返します。

バランスと回転の回数

lib/rbtree.c の冒頭コメントは赤黒木の五つの性質を挙げ、そのうち「赤いノードの子はどちらも黒」と「根から葉までのすべての単純パスに含まれる黒ノードの数は等しい」の二つが O(log n) を保証すると説明しています。赤いノードは連続できないので、どのパスの黒ノード数も B なら、最も長いパスは 2B になるという理屈です。

カーネルのドキュメントは AVL 木と比べて、挿入と削除で最悪ケースの実時間性能がよいと述べ、バランス調整の回転は挿入で最大 2 回、削除で最大 3 回だとしています。その代わり探索はわずかに遅いものの、やはり O(log n) です。

__rb_insert() の構造を見ると、この数字の出どころがわかります。

挿入のケース	条件	処理	回転	その後
Case 1	おじが赤	親とおじを黒、祖父を赤に	0	祖父で繰り返す
Case 2	おじが黒、ノードが内側の子	親で回転して Case 3 の形に	1	Case 3 へ続く
Case 3	おじが黒、ノードが外側の子	祖父で回転	1	終了

回転する経路は必ず Case 3 で終わるので、回転は最大 2 回です。ただし Case 1 は色を変えるだけで二段上でループを繰り返すため、色の付け替えは根の方へ何度も上がることがあります。「回転は最大 2 回」は「挿入後の調整が定数時間」という意味ではありません。削除側の ____rb_erase_color() も同じ構造で、回転するケース（1、3、4）をすべて通っても Case 4 で終わり、色を変えるだけの Case 2 は親の方へ上がることがあります。

走査：スタックの代わりに親ポインタ

ソート順にたどる関数は rb_first()、rb_last()、rb_next()、rb_prev() の四つです。

struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

rb_next() は、右の子があればそこへ下りてから最も左のノードまで進みます。なければ親ポインタをたどって上がり、左の子の位置から上がってきた最初の親を返します。別のスタックが要らないのは、どのノードも親ポインタを持っているからです。

木をまるごと解放するには後行順の走査があります。rbtree_postorder_for_each_entry_safe(pos, n, root, field) は子を親より先に訪れ、次のノードを先に取っておくので、ループ本体で pos のメモリを解放しても構いません。コメントには但し書きがあります。木を並べ替えるような変更には対応できず、pos に rb_erase() を呼ぶこともそれに含まれます。削除で再バランスが起きると、一部のノードを見落とすことがあるからです。

cached 木：最も左のノードを手元に持つ

rb_first() は根から左端まで下りるので、木の高さぶんの時間がかかります。最小の要素を頻繁に求める用途のために struct rb_root_cached があります。ドキュメントによれば、通常の rb_root に最も左のノードを指すポインタをひとつ足したもので、維持のコストは無視できる程度ですが、メモリは多く使います。ヘッダーの rb_first_cached() はそのポインタを読むだけで、コメントにも “Same as rb_first(), but O(1)” とあります。

キャッシュを正しく保つ責任の一部は利用者にあります。rb_insert_color_cached(node, root, leftmost) は、新しいノードが最も左かどうかを第 3 引数で受け取ります。自分で書いた挿入ループで一度でも右へ進んだなら false を渡す必要があります。rb_add_cached() はこの判断を代わりにやり、新しいノードが最も左になればそのノードを、そうでなければ NULL を返します。削除では、rb_erase_cached() が消すノードが最も左なら rb_next() でキャッシュを移します。

最小の要素を繰り返し取り出すのは、優先度付きキューの仕事でもあります。ヒープが全体のソートの代わりに何を守っているかはヒープはソート済みリストではないで扱いました。rbtree は全体をソート状態に保つので、上の走査関数でどのノードからでも前後の要素へ移れます。

augmented 木：部分木の要約値を保つ

augmented rbtree は各ノードに追加のデータを持ちますが、その値はそのノードを根とする部分木全体の関数でなければなりません。ドキュメントの例は区間木です。ノードごとに区間 [start, last] を持ち、部分木の中で最大の last を __subtree_last として保持します。左の子のこの値が問い合わせ区間の開始より小さければ、左の部分木に重なる区間はないので下りる必要がありません。ドキュメントは、こうして開始アドレスが最も小さい一致区間を O(log n) で見つけると説明しています。

回転や削除で部分木の形が変わると、要約値も直す必要があります。そのため利用者は struct rb_augment_callbacks で三つのコールバックを渡します。

• propagate：指定したノードから停止点（または根）まで上がりながら値を計算し直す。
• copy：ある部分木の値を、新しくその部分木の根になったノードにコピーする。
• rotate：copy と同じコピーをしてから、元の部分木の根の値を計算し直す。

挿入では、下りる経路の値を利用者が先に更新し、rb_link_node() の後で rb_insert_color() の代わりに rb_insert_augmented() を呼びます。削除には rb_erase_augmented() を使います。ドキュメントのサンプルと RB_DECLARE_CALLBACKS_MAX マクロの propagate は、計算し直した値が元の値と同じならそこで止まります。それより上の祖先の値は変わる理由がないからです。

ドキュメントはさらに二つのことを求めています。rb_erase_augmented() はコンパイル後のコードに propagate と copy のコールバックがインライン化されて大きくなりうるので、augmented rbtree の利用者ごとに呼び出し箇所をひとつにすること。また <linux/rbtree_augmented.h> は実装の詳細を露出させるので、C ファイルからだけ include し、ヘッダーファイルからは include しないこと。ヘッダー自身のコメントも、公開を意図しているのは struct rb_augment_callbacks と rb_insert_augmented()、rb_erase_augmented() のプロトタイプだけで、残りは依存すべきでない実装の詳細だとしています。

ロックなし探索が約束すること、しないこと

ロックは利用者任せですが、lib/rbtree.c にはロックを取らずに探索する場合の説明があります。木の構造を変えるストア（rb_left、rb_right）はすべて WRITE_ONCE() で行い、プログラム順で一時的にもループを作らないこと。この二つの条件で保証されるのは次の点です。

• ロックなしの走査は有効な要素だけを見て、ループにはまらずに終わる。
• 探索が要素を返したなら、それは正しい要素である。

保証されないことも書かれています。回転はアトミックではないので、探索が部分木ごと見落とすことがあります。要素が返らなかったからといって、その要素がないとは限りません。rb_find_rcu() のコメントも、並行して回転が起きている間の下降は健全ではなく、偽陰性になりうると警告しています。したがって、ロックなしで得た「見つからない」をそのまま結論にはできず、確かめる必要があるなら別の仕組みが要ります。

挿入側には rb_link_node_rcu() と、それを使う rb_find_add_rcu() があります。新しいノードを場所に書き込むときに rcu_assign_pointer() を使うのが通常版との違いで、コメントはこれを Store-Release を加えると表現しています。

ノードの差し替えはソートし直さない

rb_replace_node(old, new, root) は、削除と再挿入をせずにノードをひとつ差し替えます。実装は old のポインタと色をそのまま new にコピーし、子と親が new を指すように直すだけで、比較は一度もしません。そのためドキュメントは、新しいノードのキーが古いノードと違えば木はおそらく壊れると警告しています。キーを変えたいなら、削除して入れ直す必要があります。

参照したドキュメントとソース

• Red-black Trees (rbtree) in Linux、Linux カーネルドキュメント v6.17（ページ本文の日付表記は 2007 年 1 月 18 日、Rob Landley）
• include/linux/rbtree.h、Linux v6.17
• include/linux/rbtree_augmented.h、Linux v6.17
• lib/rbtree.c、Linux v6.17

2026 年 10 月 15 日に確認しました。ほかのカーネルバージョンでは、ヘルパーの種類やシグネチャが異なる場合があります。