Разработка ядра Linux - [192]
>next). Вставка или удаление элементов списка выполняется простым изменением указателей на следующий элемент. Структура связанного списка показана на рис. А.1.
Рис. A.1. Односвязный список
В. некоторых связанных списках содержится указатель не только на следующий, но и на предыдущий элемент (>prev). Эти списки называются двухсвязными (doubly linked), потому что они связаны как вперед, так и назад. Связанные списки, аналогичные тем, что показаны на рис. А.1, называются односвязными (singly linked). Двухсвязный список показан на рис. А.2.
Рис. А.2. Двухсвязный список
Кольцевые связанные списки
Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя >next последнего элемента обычно устанавливается равным специальному значению, обычно >NULL, чтобы показать, что этот элемент списка является последним. в определенных случаях последний элемент списка не указывает на специальное значение, а указывает на первый элемент этого же списка. Такой список называется кольцевым связанным списком (circular linked list), поскольку связи образуют топологию кольца. Кольцевые связанные списки могут быть как односвязными, так и двухсвязными. В двухсвязных кольцевых списках указатель prev первого элемента указывает на последний элемент списка. На рис. А.3 и А.4 показаны соответственно односвязные и двухсвязные кольцевые списки.
Рис. A.3. Односвязный кольцевой список
Рис. А.4. Двухсвязный кольцевой список
Стандартной реализацией связанных списков в ядре Linux является двухсвязный кольцевой список. Такие связанные списки обеспечивают наибольшую гибкость работы.
Перемещение по связанному списку
Перемещение по связанному списку выполняется последовательно (линейно). После того как просмотрен текущий элемент, выполнятся разыменование его указателя >next, что позволяет обратиться к следующему за ним элементу и т.д. Это самый простой и наиболее подходящий метод перемещения но связанному списку. Если важна возможность произвольного доступа к любому элементу контейнера, то связанные списки не используются. Связанные списки используются, когда важна возможность динамического добавления и удаления элементов, а также возможность последовательного прохождения по всем элементам списка.
Часто первый элемент списка представлен с помощью специального указателя, который называется головным элементом или головой (head), что дает возможность быстро и легко обращаться к первому элементу. В некольцевом связанном списке последний элемент отличается тем, что его указатель равен значению >NULL. В кольцевом связанном списке последний элемент отличается тем, что указывает на головной элемент. Таким образом прохождение списка можно выполнить линейно, начиная с первого элемента и заканчивая последним. В двухсвязном списке прохождение можно также выполнить и в противоположном направлении, начиная с последнего и заканчивая первым элементом. Конечно, если задан определенный элемент списка, то можно перейти по списку вперед и назад на заданное количество элементов. При этом нет необходимости проходить весь список.
Реализация связанных списков в ядре Linux
В ядре Linux для прохождения по связанным спискам используется унифицированный подход. При прохождении связанного списка, если не важен порядок прохода, эту операцию не обязательно начинать с головного элемента, на самом деле вообще не важно, с какого элемента списка начинать прохождение! Важно только, чтобы при таком прохождении были пройдены все узлы. В большинстве случаев нет необходимости вводить концепции первого и последнего элементов. Если в кольцевом связанном списке содержится коллекция несортированных данных, то любой элемент можно назвать головным. Для прохождения всего связанного списка необходимо взять любой элемент и следовать за указателями, пока снова не вернемся к тому элементу, с которого начали обход списка. Это избавляет от необходимости вводить специальный головной элемент. Кроме того, упрощаются процедуры работы со связанными списками. Каждая подпрограмма должна просто принимать указатель на один элемент — любой элемент списка. Разработчики ядра даже немножко гордятся такой остроумной реализацией.
Связанные списки в ядре, так же как и в любой сложной программе, встречаются часто. Например, в ядре связанный список используется для хранения списка задач (структура >task_struct каждого процесса является элементом связанного списка).
Структура элемента списка
Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 2.1 была предложена единая реализация связанных списков в ядре. Сегодня во всех подсистемах ядра используется официальная реализация. Для новых разработок необходимо использовать только существующий интерфейс и не нужно изобретать велосипед.
Код работы со связанными списками определен в файле >, a основная структура данных имеет очень простой вид.
>struct list_head {
> struct list_head *next, *prev;
