Linux Red-black Tree

Red-black tree의 개념과 용도

Linux의 Red-black Tree(rbtree)

날짜: 2007년 1월 18일

저자: Rob Landley <rob@landley.net>

Red-black tree란 무엇이며 어디에 사용하는가?

Red-black tree는 정렬 가능한 key/value data pair를 저장하는 self-balancing binary search tree입니다. Sparse array를 효율적으로 저장하기 위해 long integer index로 node를 삽입·접근·삭제하는 radix tree와 다르고, 정렬 상태를 유지하지 않아 순서대로 순회하기 어렵고 특정 크기와 hash function에 맞춰 조정해야 하는 hash table과도 다릅니다. Rbtree는 임의의 key를 저장하면서 자연스럽게 확장됩니다.

Red-black tree는 AVL tree와 비슷하지만 삽입과 삭제의 실시간 최악 성능 한계를 더 빠르게 제공합니다. Tree를 균형 잡기 위해 삽입은 최대 두 번, 삭제는 최대 세 번 회전하며 lookup은 약간 느리지만 여전히 `O(log n)`입니다.

Linux Weekly News에 따르면 kernel의 여러 곳에서 red-black tree를 사용합니다. Deadline과 CFQ I/O scheduler 및 packet CD/DVD driver는 request를 추적하고, high-resolution timer 코드는 미처리 timer request를 정리합니다. ext3 filesystem은 directory entry를 추적하며, VMA, epoll file descriptor, cryptographic key, hierarchical token bucket scheduler의 network packet도 red-black tree로 관리합니다.

이 문서는 Linux rbtree 구현의 사용법을 다룹니다. Red-black tree의 성질과 구현에 관한 추가 자료는 다음과 같습니다.

• Linux Weekly News: red-black treeshttps://lwn.net/Articles/184495/
• Wikipedia: Red-black treehttps://en.wikipedia.org/wiki/Red-black_tree

Linux rbtree 구현

Linux의 red-black tree 구현

Linux rbtree 구현은 `lib/rbtree.c`에 있으며 사용할 때는 `#include <linux/rbtree.h>`를 포함합니다.

Linux 구현은 속도에 맞춰 최적화되어 전통적인 tree 구현보다 indirection 계층이 하나 적고 cache locality가 좋습니다. 별도의 `rb_node`와 data 구조체를 포인터로 연결하지 않고 각 `struct rb_node`를 자신이 정리하는 data 구조체 안에 포함합니다.

Comparison callback function pointer도 사용하지 않습니다. 사용자가 제공된 rbtree 함수를 호출하는 자체 search와 insert 함수를 작성해야 하며 locking 역시 rbtree 사용자 책임입니다.

새 rbtree 생성

새 rbtree 생성

Rbtree의 data node는 `struct rb_node` 멤버를 포함하는 구조체입니다.

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

포함된 `struct rb_node` 포인터에서 바깥 data 구조체에 접근할 때 표준 `container_of()` 매크로를 사용합니다. 개별 멤버에는 `rb_entry(node, type, member)`로 직접 접근할 수도 있습니다.

각 rbtree의 root에는 `rb_root` 구조체가 있으며 다음과 같이 빈 상태로 초기화합니다.

struct rb_root mytree = RB_ROOT;

값 검색

Rbtree에서 값 검색

Tree 검색 함수는 root에서 시작해 각 값을 비교하고 필요에 따라 왼쪽 또는 오른쪽 branch를 따라가면 됩니다.

예:

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;
}

데이터 삽입

Rbtree에 data 삽입

새 node를 삽입할 위치를 먼저 검색하고, node를 삽입한 뒤 tree를 다시 균형 잡는 recoloring 과정을 수행합니다.

삽입 검색은 새 node를 접붙일 포인터의 위치를 찾는다는 점에서 일반 검색과 다릅니다. Rebalancing을 위해 새 node에는 parent node 링크도 필요합니다.

예:

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;
}

기존 데이터 삭제와 교체

Rbtree의 기존 data 삭제 또는 교체

Tree에서 기존 node를 삭제하려면 다음 함수를 호출합니다.

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);
}

기존 node를 같은 key를 가진 새 node로 교체하려면 다음 함수를 호출합니다.

void rb_replace_node(struct rb_node *old, struct rb_node *new,
                        struct rb_root *tree);

이 방식의 교체는 tree를 다시 정렬하지 않습니다. 새 node의 key가 이전 node와 같지 않으면 rbtree가 손상될 가능성이 큽니다.

정렬 순서로 순회

Rbtree에 저장된 element를 정렬 순서로 순회

Rbtree 내용을 정렬 순서로 순회하는 네 함수가 제공됩니다. 임의의 tree에서 동작하며 locking 목적 외에는 수정하거나 감쌀 필요가 없습니다.

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);

순회를 시작하려면 tree root 포인터로 `rb_first()` 또는 `rb_last()`를 호출합니다. 각각 첫 element 또는 마지막 element에 포함된 node 구조체 포인터를 반환합니다. 계속하려면 현재 node에 `rb_next()` 또는 `rb_prev()`를 호출하고, 더 이상 node가 없으면 NULL을 반환합니다.

Iterator 함수는 포함된 `struct rb_node` 포인터를 반환합니다. 바깥 data 구조체는 `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);

Cached rbtree

Cached rbtree

Binary search tree에서 가장 왼쪽의 가장 작은 node를 구하는 작업은 순회나 특정 순서를 이용하는 사용자에게 흔합니다. `struct rb_root_cached`를 사용하면 `O(logN)`인 `rb_first()` 호출을 잠재적으로 비싼 tree 순회 없이 단순한 pointer fetch로 최적화할 수 있습니다. Memory footprint는 커지지만 유지에 필요한 runtime overhead는 무시할 정도입니다.

`rb_root`처럼 cached rbtree도 다음과 같이 빈 상태로 초기화합니다.

struct rb_root_cached mytree = RB_ROOT_CACHED;

Cached rbtree는 가장 왼쪽 node를 cache하는 추가 포인터를 가진 일반 `rb_root`입니다. 따라서 `rb_root`를 사용할 수 있는 곳이면 `rb_root_cached`도 사용할 수 있고 augmented tree도 지원하며 몇 가지 interface만 추가됩니다.

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 *);

Insert와 erase에는 각각 augmented tree용 대응 함수도 있습니다.

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 *);

Augmented rbtree 지원

Augmented rbtree 지원

Augmented rbtree는 각 node에 추가 data를 저장하는 rbtree입니다. Node N의 추가 data는 N을 root로 하는 subtree의 모든 node 내용에 대한 함수여야 합니다. 이 data로 rbtree에 새 기능을 더할 수 있으며 기본 rbtree 위에 구축되는 선택적 기능입니다.

이 기능을 사용하는 사용자는 node 삽입과 삭제 시 자신이 제공한 augmentation callback과 함께 augmentation 함수를 호출해야 합니다.

Augmented rbtree 조작을 구현하는 C 파일은 `<linux/rbtree.h>` 대신 `<linux/rbtree_augmented.h>`를 포함해야 합니다. 이 header는 의존해서는 안 되는 일부 구현 세부 정보를 노출하므로 문서화된 API만 사용하십시오. 사용자가 실수로 구현 세부 정보에 의존할 가능성을 줄이기 위해 header file에서는 `<linux/rbtree_augmented.h>`를 포함하지 마십시오.

삽입할 때는 삽입 node까지 이어지는 path의 augmented 정보를 먼저 갱신하고 평소처럼 `rb_link_node()`를 호출한 뒤 `rb_insert_color()` 대신 `rb_augment_inserted()`를 호출합니다. `rb_augment_inserted()`가 tree를 rebalancing하면 영향받는 subtree의 augmented 정보를 갱신하도록 사용자 callback을 호출합니다.

Node를 지울 때는 `rb_erase()` 대신 `rb_erase_augmented()`를 호출합니다. 이 함수는 영향받는 subtree의 augmented 정보를 갱신하는 사용자 함수를 callback합니다.

두 경우 callback은 `struct rb_augment_callbacks`로 제공하며 세 callback을 정의해야 합니다.

• Propagation callback은 주어진 node와 조상들의 augmented value를 지정한 stop point까지 갱신합니다. Stop이 NULL이면 root까지 모두 갱신합니다.
• Copy callback은 주어진 subtree의 augmented value를 새로 지정된 subtree root로 복사합니다.
• Tree rotation callback은 주어진 subtree의 augmented value를 새 root로 복사하고 이전 subtree root의 augmented 정보를 다시 계산합니다.

`rb_erase_augmented()`의 컴파일된 코드는 propagation과 copy callback을 inline하여 함수가 커질 수 있습니다. 따라서 각 augmented rbtree 사용자는 compiled code 크기를 제한하도록 `rb_erase_augmented()` 호출 지점을 하나만 두어야 합니다.

Interval tree 예제

사용 예 (Sample usage)

Interval tree는 augmented rb tree의 예입니다. 참고 자료는 Cormen, Leiserson, Rivest, Stein의 'Introduction to Algorithms'입니다.

전통적인 rbtree는 단일 key만 가지므로 `[lo:hi]` 같은 interval range를 직접 저장한 뒤 새 `lo:hi`와 겹치는 범위를 빠르게 찾거나 정확히 일치하는 범위를 검색할 수 없습니다.

그러나 rbtree를 augment하여 interval range를 구조적으로 저장하면 효율적인 overlap lookup과 exact match가 가능합니다.

각 node에 저장하는 추가 정보는 모든 descendant node 가운데 가장 큰 `hi`, 즉 `max_hi` 값입니다. 각 node와 바로 아래 child만 살펴도 이 값을 유지할 수 있습니다. 이를 이용하면 가능한 모든 match 중 시작 주소가 가장 낮은 lowest match를 `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 */
      }
}

Interval tree callback과 삽입·삭제

삽입과 삭제는 다음 augmented callback을 사용하여 정의합니다.

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);
}

`compute_subtree_last()`는 현재 node와 양쪽 child의 `__subtree_last`에서 최댓값을 계산합니다. `augment_propagate`, `augment_copy`, `augment_rotate`는 각각 조상 갱신, 값 복사, 회전 뒤 재계산을 담당합니다.

`interval_tree_insert()`는 검색 경로의 `__subtree_last`를 갱신한 뒤 `rb_link_node()`와 `rb_insert_augmented()`를 호출합니다. `interval_tree_remove()`는 같은 callback 집합과 함께 `rb_erase_augmented()`를 호출합니다.