Linuxカーネルの赤黒木

赤黒の木はバランスのとれた二分木の一種で、良い性質を持っていますツリー内のノードは順序付けられていて、バランスが取れているので検索はそれほど悪く見えません。二分木に基づく演算の時間的複雑さは、Ｏ（ｌｏｇ（Ｎ））である。 Linuxカーネルは、vm_area_structを管理するときに赤黒木を使用してメモリブロックを維持します。

最初にinclude /linux /rbtree.hを見て、以下のように赤黒木の定義を確認します。

struct rb_node

{

unsigned long rb_parent_color;

#define RB_RED 0

#define RB_BLACK 1

struct rb_node * rb_right;

struct rb_node * rb_left;

} __attribute __（（aligned（sizeof（long））））;

struct rb_rootはstruct rb_node *のラッパーです。利点は、二次ポインタを通過しないように見えることです。はい、とても簡単です。以下の重要なマクロを見てください。rb_parent_colorがそれほど単純ではないことに注意してくださいAndrea Arcangeliはここで小さなトリックを使いますが、それは素晴らしいことです。名前が示すように、このメンバーは実際には親へのポインタとこのノードの色を含んでいます。それはどのようにしましたか？非常に単純で、整列は機能します。これは、sizeof（long）サイズアライメントなので、IA-32では、rb_node構造体のアドレスの下位2ビットはゼロでなければなりません。空ではなく、それらを使用して色を表現することをお勧めします。実際、1つでも十分です。

このようにして親ポインタを抽出するには、rb_parent_colorメンバの下位2ビットをクリアするだけです。

#define rb_parent（r）（（構造体rb_node *）（（r） - > rb_parent_color&〜3））

色を取るには、最後のビットを見てください。

#define rb_color（r）（（r） - > rb_parent_color& 1）

色のテストと色の設定も当然のことです。次のインライン関数について特に言及します。

静的インラインvoid rb_link_node（構造体rb_node * node、構造体rb_node * parent、構造体rb_node ** rb_link）;

parentをnodeの親ノードに設定し、rb_linkにnodeをポイントさせます。

ここではlib /rbtree.cに焦点を当て、赤黒木に関連する重要なアルゴリズムのいくつかを調べます。始める前に、赤黒ツリーのルールを思い出してみましょう。

1.各ノードは赤か黒かのどちらかです。

2.ルートノードは黒;

3.赤ノード子供がいる場合、その子供も黒でなければなりません。

4.ルートノードからリーフまでの各パスは、同じ数の黒ノードを含む必要があります。 。

これら4つの規則は、ソートツリーのバランスを制限することができます。

__rb_rotate_leftはルートルートツリー内のノードnodeの左回転、__rb_rotate_rightは右回りです。これら2つの機能は、外部へのインターフェースを提供するのではなく、後続の挿入および削除サービス用です。

新しく挿入されたノードは、挿入後に上記の規則が破られ、色と回転が復元され、バイナリツリーが再調整されると、葉に、赤く染色されます。挿入操作のインターフェース関数は、次のとおりです。void rb_insert_color（struct rb_node * node、struct rb_root * root）;
決定された親ノードを置きます。点の節点ノードは根を根とする赤黒木に統合されています特定のアルゴリズムの分析は[1]の14.3節を参照することができますここでの実装は本とほぼ同じです。ノードの親ノードを決定する方法は、rb_insert_colorを呼び出して手動で行う必要があります。挿入操作にはループの反復が必要ですが、総回転数が2倍を超えないようにする必要があります。だから効率はまだ非常に楽観的です。

削除操作は多少面倒ですが、最初に通常の二分探索木のように削除を実行してから、削除したノードの色によってさらに実行するかどうかを判断する必要があります。操作削除するインタフェースは次のとおりです。

void rb_erase（struct rb_node * node、struct rb_root * root）;

実際には、実際にはnodeを削除しません。代わりに、単にルートをルートとするツリーから分離して、最後に調整するために__rb_erase_colorを呼び出すかどうかを判断する必要があります。具体的なアルゴリズムの説明については、対応する__rb_erase_colorの本の[1]の13.3節および14.4節、RB-DELETE-FIXUPを参照してください。ここでの実装は基本的に本の実装と同じです。

残りのインタフェースはもっと単純です。

構造体rb_node * rb_first（構造体rb_root * root）;

根を根とする木の中で最小のものを見つけて返します。ルートノードから左に移動する限り、ノード。

struct rb_node * rb_last（struct rb_root * root）;

は、最大のものを見つけて返すことです。

struct rb_node * rb_next（struct rb_node * node）;

ツリー内の連続したnodeを返すのは少し複雑です。 nodeの右の子が空でない場合は、nodeの右のサブツリーの最小のノードを返すだけでよく、空の場合は、重なっているノードの父の左の子のノードを調べて見つける必要があります。親ノード上記がルートノードに到達した場合、NULLを返します。

struct rb_node * rb_prev（struct rb_node * node）;

nodeの前身を返し、rb_nextの演算と対称的です。

void rb_replace_node（構造体rb_node * victim、構造体rb_node * new、構造体rb_root * root）;

rootをrootに置き換えますツリー内の犠牲ノード。

赤黒ツリーインターフェイスの典型的な例は次のとおりです。

静的インラインstruct page * rb_search_page_cache（struct inode * inode、

unsigned long offset）

{

struct rb_node * n = inode-> i_rb_page_cache.rb_node;

struct page * page;

while（n）

{

page = rb_entry（n、struct page、rb_page_cache）;

if（offset） < page-> offset）

n = n-> rb_left;

else if（offset> page-> offset）

n = n- > rb_right;

else

戻るページ。