Linux 中的紅黑樹 (rbtree)¶
- 日期:
2007 年 1 月 18 日
- 作者:
Rob Landley <rob@landley.net>
什麼是紅黑樹，它有什麼用？¶
紅黑樹是一種自平衡二叉搜尋樹，用於儲存可排序的鍵/值資料對。這與基數樹（用於高效儲存稀疏陣列，從而使用長整數索引來插入/訪問/刪除節點）和雜湊表（不保持有序以便按順序遍歷，並且必須針對特定大小和雜湊函式進行調優，而紅黑樹可以優雅地擴充套件以儲存任意鍵）不同。
紅黑樹與 AVL 樹相似，但在插入和刪除方面提供更快的即時有界最壞情況效能（分別最多兩次旋轉和三次旋轉以平衡樹），查詢時間稍慢（但仍為 O(log n)）。
引用 Linux Weekly News 的話
核心中使用了許多紅黑樹。deadline 和 CFQ I/O 排程器使用紅黑樹來跟蹤請求；資料包 CD/DVD 驅動程式也這樣做。高精度計時器程式碼使用紅黑樹來組織未完成的計時器請求。ext3 檔案系統在紅黑樹中跟蹤目錄條目。虛擬記憶體區域 (VMAs) 使用紅黑樹進行跟蹤，epoll 檔案描述符、加密金鑰以及“分層令牌桶”排程器中的網路資料包也是如此。
本文件涵蓋 Linux 紅黑樹實現的用法。有關紅黑樹的性質和實現的更多資訊，請參閱
- Linux Weekly News 關於紅黑樹的文章
- 維基百科紅黑樹條目
紅黑樹的 Linux 實現¶
Linux 的紅黑樹實現位於“lib/rbtree.c”檔案中。要使用它，請“#include <linux/rbtree.h>”。
Linux 紅黑樹實現經過速度最佳化，因此比更傳統的樹實現少了一層間接（並具有更好的快取區域性性）。它不使用指向單獨的 `rb_node` 和資料結構的指標，而是將 `struct rb_node` 的每個例項嵌入到它組織的資料結構中。並且不使用比較回撥函式指標，而是期望使用者編寫自己的樹搜尋和插入函式，這些函式呼叫提供的紅黑樹函式。鎖定也由紅黑樹程式碼的使用者負責。
建立新的紅黑樹¶
紅黑樹中的資料節點是包含 `struct rb_node` 成員的結構體
struct mytype {
struct rb_node node;
char *keystring;
};
當處理嵌入式 `struct rb_node` 的指標時，可以使用標準 `container_of()` 宏訪問包含的資料結構。此外，可以透過 `rb_entry(node, type, member)` 直接訪問單個成員。
每個紅黑樹的根是一個 `rb_root` 結構體，它透過以下方式初始化為空：
struct rb_root mytree = RB_ROOT;
在紅黑樹中搜索值¶
為你的樹編寫搜尋函式相當簡單：從根開始，比較每個值，並根據需要遵循左分支或右分支。
示例
struct mytype *my_search(struct rb_root *root, char *string)
{
struct rb_node *node = root->rb_node;
while (node) {
struct mytype *data = container_of(node, struct mytype, node);
int result;
result = strcmp(string, data->keystring);
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
將資料插入紅黑樹¶
在樹中插入資料首先涉及搜尋新節點的插入位置，然後插入節點並重新平衡（“重新著色”）樹。
插入搜尋與先前的搜尋不同，它需要找到要嫁接新節點的指標位置。新節點還需要一個指向其父節點的連結，以用於重新平衡。
示例
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);
int result = strcmp(data->keystring, this->keystring);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return FALSE;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return TRUE;
}
在紅黑樹中刪除或替換現有資料¶
要從樹中刪除現有節點，請呼叫
void rb_erase(struct rb_node *victim, struct rb_root *tree);
示例
struct mytype *data = mysearch(&mytree, "walrus");
if (data) {
rb_erase(&data->node, &mytree);
myfree(data);
}
要用一個具有相同鍵的新節點替換樹中的現有節點，請呼叫
void rb_replace_node(struct rb_node *old, struct rb_node *new,
struct rb_root *tree);
以這種方式替換節點不會重新排序樹：如果新節點與舊節點沒有相同的鍵，紅黑樹可能會損壞。
迭代紅黑樹中儲存的元素（按排序順序）¶
提供了四個函式，用於按排序順序迭代紅黑樹的內容。這些函式適用於任意樹，不應需要修改或封裝（除了鎖定目的）
struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);
要開始迭代，呼叫 `rb_first()` 或 `rb_last()` 並傳入樹根的指標，這將返回指向樹中第一個或最後一個元素中包含的節點結構的指標。要繼續，透過在當前節點上呼叫 `rb_next()` 或 `rb_prev()` 來獲取下一個或上一個節點。當沒有更多節點時，這將返回 NULL。
迭代器函式返回指向嵌入式 `struct rb_node` 的指標，可以利用 `container_of()` 宏訪問其包含的資料結構，並可以透過 `rb_entry(node, type, member)` 直接訪問單個成員。
示例
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);
快取紅黑樹¶
計算最左（最小）節點對於二叉搜尋樹來說是一項非常常見的任務，例如用於遍歷或依賴特定順序進行自身邏輯的使用者。為此，使用者可以使用 'struct rb_root_cached' 將 O(logN) 的 `rb_first()` 呼叫最佳化為簡單的指標獲取，避免潛在昂貴的樹迭代。這在維護上執行時開銷可忽略不計；儘管記憶體佔用較大。
與 `rb_root` 結構類似，快取的紅黑樹透過以下方式初始化為空：
struct rb_root_cached mytree = RB_ROOT_CACHED;
快取紅黑樹只是一個普通的 `rb_root`，額外有一個指標用於快取最左節點。這使得 `rb_root_cached` 可以在 `rb_root` 存在的任何地方存在，從而允許支援增強樹以及一些額外的介面
struct rb_node *rb_first_cached(struct rb_root_cached *tree);
void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool);
void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
插入和刪除呼叫都有其各自的增強樹對應物
void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *,
bool, struct rb_augment_callbacks *);
void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *,
struct rb_augment_callbacks *);
支援增強紅黑樹¶
增強紅黑樹是一種紅黑樹，每個節點中儲存了一些附加資料，其中節點 N 的附加資料必須是根植於 N 的子樹中所有節點內容的一個函式。這些資料可用於為紅黑樹增強一些新功能。增強紅黑樹是在基本紅黑樹基礎設施之上構建的可選功能。需要此功能的紅黑樹使用者在插入和刪除節點時，必須呼叫增強函式並提供使用者定義的增強回撥。
實現增強紅黑樹操作的 C 檔案必須包含 <linux/rbtree_augmented.h>，而不是 <linux/rbtree.h>。請注意，linux/rbtree_augmented.h 暴露出一些你本不應依賴的紅黑樹實現細節；請堅持那裡文件化的 API，並且也不要從標頭檔案中包含 <linux/rbtree_augmented.h>，以儘量減少你的使用者意外依賴這些實現細節的可能性。
在插入時，使用者必須更新導致插入節點的路徑上的增強資訊，然後像往常一樣呼叫 `rb_link_node()` 並呼叫 `rb_augment_inserted()` 而不是通常的 `rb_insert_color()` 呼叫。如果 `rb_augment_inserted()` 重新平衡紅黑樹，它將回調到使用者提供的函式中以更新受影響子樹上的增強資訊。
刪除節點時，使用者必須呼叫 `rb_erase_augmented()` 而不是 `rb_erase()`。 `rb_erase_augmented()` 會回撥使用者提供的函式以更新受影響子樹上的增強資訊。
在這兩種情況下，回撥都透過 `struct rb_augment_callbacks` 提供。必須定義 3 個回撥：
一個傳播回撥，它更新給定節點及其祖先的增強值，直到給定的停止點（或 NULL 表示一直更新到根）。
一個複製回撥，它將給定子樹的增強值複製到新分配的子樹根。
一個樹旋轉回調，它將給定子樹的增強值複製到新分配的子樹根，並重新計算原子樹根的增強資訊。
`rb_erase_augmented()` 的編譯程式碼可能會內聯傳播和複製回撥，這導致函式體很大，因此每個增強紅黑樹使用者應只有一個 `rb_erase_augmented()` 呼叫站點，以限制編譯程式碼大小。
使用示例¶
區間樹是增強紅黑樹的一個例子。參考——Cormen、Leiserson、Rivest 和 Stein 的《演算法導論》。有關區間樹的更多細節：
經典紅黑樹只有一個鍵，不能直接用於儲存像 [lo:hi] 這樣的區間範圍，也無法快速查詢與新 lo:hi 的任何重疊或查詢新 lo:hi 的精確匹配。
然而，紅黑樹可以增強以結構化方式儲存此類區間範圍，從而可以進行高效的查詢和精確匹配。
每個節點中儲存的“額外資訊”是其所有後代節點中的最大 hi (max_hi) 值。此資訊只需檢視節點及其直接子節點即可在每個節點處維護。這將用於 O(log n) 查詢最低匹配（所有可能匹配中最低的起始地址），例如：
struct interval_tree_node *
interval_tree_first_match(struct rb_root *root,
unsigned long start, unsigned long last)
{
struct interval_tree_node *node;
if (!root->rb_node)
return NULL;
node = rb_entry(root->rb_node, struct interval_tree_node, rb);
while (true) {
if (node->rb.rb_left) {
struct interval_tree_node *left =
rb_entry(node->rb.rb_left,
struct interval_tree_node, rb);
if (left->__subtree_last >= start) {
/*
* Some nodes in left subtree satisfy Cond2.
* Iterate to find the leftmost such node N.
* If it also satisfies Cond1, that's the match
* we are looking for. Otherwise, there is no
* matching interval as nodes to the right of N
* can't satisfy Cond1 either.
*/
node = left;
continue;
}
}
if (node->start <= last) { /* Cond1 */
if (node->last >= start) /* Cond2 */
return node; /* node is leftmost match */
if (node->rb.rb_right) {
node = rb_entry(node->rb.rb_right,
struct interval_tree_node, rb);
if (node->__subtree_last >= start)
continue;
}
}
return NULL; /* No match */
}
}
插入/刪除是使用以下增強回撥定義的：
static inline unsigned long
compute_subtree_last(struct interval_tree_node *node)
{
unsigned long max = node->last, subtree_last;
if (node->rb.rb_left) {
subtree_last = rb_entry(node->rb.rb_left,
struct interval_tree_node, rb)->__subtree_last;
if (max < subtree_last)
max = subtree_last;
}
if (node->rb.rb_right) {
subtree_last = rb_entry(node->rb.rb_right,
struct interval_tree_node, rb)->__subtree_last;
if (max < subtree_last)
max = subtree_last;
}
return max;
}
static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
{
while (rb != stop) {
struct interval_tree_node *node =
rb_entry(rb, struct interval_tree_node, rb);
unsigned long subtree_last = compute_subtree_last(node);
if (node->__subtree_last == subtree_last)
break;
node->__subtree_last = subtree_last;
rb = rb_parent(&node->rb);
}
}
static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
{
struct interval_tree_node *old =
rb_entry(rb_old, struct interval_tree_node, rb);
struct interval_tree_node *new =
rb_entry(rb_new, struct interval_tree_node, rb);
new->__subtree_last = old->__subtree_last;
}
static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
{
struct interval_tree_node *old =
rb_entry(rb_old, struct interval_tree_node, rb);
struct interval_tree_node *new =
rb_entry(rb_new, struct interval_tree_node, rb);
new->__subtree_last = old->__subtree_last;
old->__subtree_last = compute_subtree_last(old);
}
static const struct rb_augment_callbacks augment_callbacks = {
augment_propagate, augment_copy, augment_rotate
};
void interval_tree_insert(struct interval_tree_node *node,
struct rb_root *root)
{
struct rb_node **link = &root->rb_node, *rb_parent = NULL;
unsigned long start = node->start, last = node->last;
struct interval_tree_node *parent;
while (*link) {
rb_parent = *link;
parent = rb_entry(rb_parent, struct interval_tree_node, rb);
if (parent->__subtree_last < last)
parent->__subtree_last = last;
if (start < parent->start)
link = &parent->rb.rb_left;
else
link = &parent->rb.rb_right;
}
node->__subtree_last = last;
rb_link_node(&node->rb, rb_parent, link);
rb_insert_augmented(&node->rb, root, &augment_callbacks);
}
void interval_tree_remove(struct interval_tree_node *node,
struct rb_root *root)
{
rb_erase_augmented(&node->rb, root, &augment_callbacks);
}