В отличие от предыдущей статьи данная статья описывает деревья в ядре Linux. Точнее говоря, описывается API, а не сами деревья, алгоритмы на них и правила формирования красно-чёрных деревьев. Если вас интересуют основы, то стоит обратить внимание на статью "Абстрактные типы данных - Красно-чёрные деревья (Red black trees)" от 14 октября 2011. Здесь свойства красно-чёрных деревьев упомянуты лишь вкратце. Статья основана на материалах lwn.net
Наряду с базисными деревьями (radix trees) ядро содержит реализацию структуры данных, известной под названием "красно-чёрное дерево" (red-black tree). Красно-чёрные деревья (в ядре более известные, как "rbtrees") являются разновидностью полусбалансированных деревьев. Каждый узел дерева содержит некое значение и не более двух дочерних узлов; значение узла больше, чем значения любого из содержащихся в его левом поддереве или меньше любого из значений его правого поддерева. Поиск значения возможен с самого первого глубокого узла обходом слева направо.
Каждый узел красно-чёрного дерева может быть красного или чёрного цвета, корень дерева всегда чёрный. Набор правил, исходя из которых окрашиваются узлы и когда должна происходить перебалансировка несколько сложен. Данная статья не будет касаться этой темы (см. выше). Вместо описания механизмов работы красно-чёрных деревьев мы сконцентрируем внимание на том, как используются красно-чёрные деревья в ядре Linux.
Сложность правил формирования красно-чёрных деревьев окупается некоторыми преимуществами, в частности при том, что красно-чёрное дерево - это бинарное дерево, поиск значения осуществляется за логарифмическое время. Если дерево поддерживается в надлежащем состоянии, то самый длинный путь к листу никогда не будет превышать двукратной длины наикратчайшего пути - иными словами, дерево всегда почти сбалансировано. Но самое важное свойство красно-чёрных деревьев с точки зрения ядра это то, что операции вставки и удаления (1) быстрые и (2) имеют гарантированное время обработки. Вся работа разработчиков ядра по сокращению временных издержек при выполнении кода пошла бы насмарку, если бы какая-либо из используемых ядром структур данных отнимала много времени, скажем, на перебалансировку. При использовании красно-чёрных деревьев есть небольшие издержки, связанные с операцией поиска, т.к. дерево сбалансировано не идеально, однако операции вставки и удаления быстры и выполняются за гарантированно короткое время. Таким образом, красно-чёрные деревья находят своё применение там, где часто необходимо добавлять и удалять узлы.
В ядре множество мест, где используются красно-чёрные деревья. Планировщики ввода-вывода anticipatory (упреждающий), deadline (алгоритм крайнего срока) и CFQ (completely fair queuing - абсолютно честная очередь) используют красно-чёрные деревья для отслеживания запросов; драйвер пакетной записи CD/DVD использует красно-чёрные деревья для этих же целей. Код таймеров высокого разрешения использует красно-чёрное дерево для упорядочивания невыполненных запросов на таймеры. Файловая система ext3 отслеживает в красно-чёрных деревьях содержимое (записи) директорий. Также с помощью красно-чёрных деревьев отслеживаются диапазоны виртуальных адресов (VMAs), дескрипторы файлов, на которых применяется опрос вызовом epoll(), криптографические ключи и сетевые пакеты в планировщике "hierarchical token bucket" (классовая дисциплина очереди НТВ).
Использование красно-чёрных деревьев начинается с включения заголовка <linux/rbtree.h>. Это одна из самых хитрых в использовании структур данных ядра. При разработке структуры данных на языке С разработчику всегда приходится решать, каким образом включить в эту структуру некие данные произвольного типа и как сравнивать их между собой. Человек, который написал реализацию красно-чёрных деревьев в Linux (копирайт в коде принадлежит Андреа Арканджели (Andrea Arcangeli)) принял следующие решения:
- Структуры, которые являются частью красно-чёрного дерева (учёт которых ведётся с помощью дерева) должны иметь поле типа rb_node; для ссылок на объекты используются не указатели void*. Это общий принцип реализации структур данных ядра, так что едва ли это много кого удивит.
- В коде красно-чёрных деревьев нет функции обратного вызова (колбэка) "сравнить два объекта". Вместо этого для использования дерева пользователь должен сам написать функции поиска и вставки, используя примитивные функции, предоставляемые интерфейсом реализации красно-чёрных деревьев. В итоге использование красно-чёрных деревьев требует немного больше работы, а сама структура не так непрозрачна, как больше пришлось бы по вкусу преподавателю компьютерных наук. Тем не менее результатом такого подхода является скорость и отсутствие кучи функций, поддерживающих инфтраструктуру там, где интенсивны операции поиска.
Необходимо также помнить, что подобно многим структурам данных ядра красно-чёрные деревья (далее просто rbtree) не предоставляют механизмов блокировки сами по себе. Любой код, использующий rbtree должен обеспечивать собственный механизм взаимного исключения для поддержания дерева в целостном состоянии. Обычно, блокирока будет соответствовать схемам, используемым в других, уже существующих частях кода и поэтому нет необходимости изобретать некий свой механизм блокировок.
Корень красно-чёрного дерева имеет тип struct rb_root; пустое дерево может быть проинициализировано строкой:
struct rb_root the_root = RB_ROOT;
Предположим, у нас уже есть красно-чёрное дерево, ломящееся от всяких интересных данных. Обход дерева (без поиска) прямолинеен:
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 означает, что узел не существует.
Т.к. структура rb_node внедряется в пользовательскую структуру, поиск нужного узла rb_node осуществляется просто при использовании нужного поля нашей пользовательской структуры. Вызов любой из упомянутых выше функций возратит указатель на внедрённое поле типа rb_node. Однако, это поле не будет содержать интересующих нас данных. Это та ситуация, когда нужен макрос container_of(), но у нас нет необходимости напрямую использовать container_of(). Вместо этого используйте rb_entry():
rb_entry(pointer, type, member);
Здесь pointer - указатель на член rb_node в нашей структуре, type - тип нашей пользовательской структуры, а member - имя поля типа rb_node внутри контейнера (структуры, хранимой в дереве).
Поиск значения в дереве начинается с корня, затем циклически значение каждого узла сравнивается с искомым ключом и последующим переходом к более левой ветви, если необходимо. Т.о., код функции поиска в rbtree может выглядеть приблизительно так:
struct my_stuff *my_rb_search (struct rb_root *root, int value)
{
struct rb_node *node = root->rb_node; /* top of the tree */
while (node) {
struct my_stuff *stuff = rb_entry (node, struct my_stuff, node);
if (stuff->coolness > value)
node = node->rb_left;
else if (stuff->coolness < value)
node = node->rb_right;
else
return stuff; /* Found it */
}
return NULL;
}Здесь мы ищем структуры типа struct my_stuff, сравнивая поле coolness с заданным значением. Для простоты мы используем целочисленные значения, но не всякое использование деревьев обязано быть таким простым. Если значение coolness корня больше, чем искомое значение, поиск должен быть продолжен в левой ветви дерева (если это значение вообще присутствует в дереве), так что мы переходим по указателю rb_left и начинаем сначала. Если искомое значение больше, чем значение из текущего узла, нам надо перейти на правую ветку. Наконец, либо функция найдёт точное совпадение, или достигнет "конца" дерева.
Код вставки немного сложнее. Он должен обойти дерево в поисках листа, где можно вставить новый узел. Как только такое место найдено, новый узел вставляется с цветом "красный", а дерево перебалансируется при необходимости. Код функции вставки может выглядеть так:
void my_rb_insert (struct rb_root *root, struct my_stuff *new)
{
struct rb_node **link = &root->rb_node, *parent;
int value = new->coolness;
/* Go to the bottom of the tree */
while (*link) {
parent = *link;
struct my_stuff *stuff = rb_entry (parent, struct my_stuff, parent);
if (stuff->coolness > value)
link = &(*link)->rb_left;
else
link = &(*link)->rb_right;
}
/* Put the new node there */
rb_link_node (new, parent, link);
rb_insert_color (new, root);
}В этом случае обход дерева более похож на поиск. Указатель link имеет вторую степень косвенности; в конце этот указатель используется, чтобы уведомить код rbtree, какая из ветвей (rb_left или rb_right) будет содержать новое значение. Код проходит по всему дереву до конца, указатель parent содержит адрес родителя для вставленного узла, а link указывает на соответствующее поле родительского узла. Затем вызывается функция:
void rb_link_node (struct rb_node *new_node,
struct rb_node *parent,
struct rb_node **link);Вызов этой функции встроит новый узел в дерево, как узел красного цвета. После этого вызова дерево может перестать соответствовать требованиям построения красно-чёрных деревьев и в таком случае необходима перебалансировка. Эта работа выполняется функцией:
void rb_insert_color (struct rb_node *new_node, struct rb_root *tree);
На этом шаге дерево должно содержать новые данные и быть сбалансированным.
В примере выше делалось важное предположение: новое значение, добавляемое в дерево, не существовало в дереве ранее. Если это предположение оказывается неверным, дерево может быть испорчено. Если есть вероятность дубликатов в дереве, код должен тщательно проверить наличие таких дубликатов (как делается в случае поиска) и остановиться (без вставки узла) если найдено совпадение.
Удаление узла из дерево - очень простой шаг; просто вызовите функцию:
void rb_erase (struct rb_node *victim, struct rb_root *tree);
После вызова данной йункции узел victim больше не будет являться частью дерева, которое может потребовать перебалансировки после операции удаления. Если один узел дерева должен быть заменён другим с тем же самым значением, необязательно последовательно проводить удаление и вставку. Вместо этого просто используйте функцию:
void rb_replace_node (struct rb_node *old,
struct rb_node *new,
struct rb_root *tree);Этот вызов быстро удалит из дерева старый узел, заменив его на new. Однако, если new имеет не такое же значение, как old, дерево будет испорчено.
No comments:
Post a Comment