Книга: Разработка ядра Linux
Перемещение по связанным спискам
Перемещение по связанным спискам
Теперь мы уже знаем, как объявлять, инициализировать и работать со связанными списками в ядре. Это все хорошо, но не имеет никакого смысла, если нет возможности работать С данными, которые хранятся в списках! Связанный список — это просто контейнер, в котором хранятся важные данные. Необходимо иметь способ перемещения по списку и доступа к данным. К счастью, ядро предоставляет набор полезных интерфейсов для перемещения по связанным спискам и обращения к структурам данных, которые хранятся в этих списках.
Обратите внимание, что, в отличие от подпрограмм управления списками, операции перебора элементов списка из n узлов масштабируются как O(n).
Наиболее простой способ выполнять итерации по элементам связанного списка — это использовать макрос list_for_each()
. Этот макрос принимает два параметра — указатели на структуры list_head
. Первый параметр указывает на текущий элемент списка, а второй — на любой элемент списка, для которого необходимо обойти все узлы. На каждой итерации цикла первый параметр макроса указывает на текущий элемент списка, пока не будут пройдены все элементы, как в следующем примере.
struct list_head *p;
list_for_each(p, list) {
/* p указывает на каждый элемент списка list */
}
Это пока все еще бесполезно! Указатель на структуру узла списка — это не то, что нам нужно. Нам нужен указатель на структуру данных, в которой содержится структура узла. В показанном ранее примере структуры данных my_struct
необходимо получить указатель на каждый экземпляр структуры my_struct
, а не на их поля list
. Макрос list_entry()
возвращает структуру данных, которая содержит соответствующий элемент list_head
. Этот макрос принимает три параметра: указатель на текущий узел, тип структуры данных, в которую включен узел списка, и имя поля структуры данных, в которой хранится этот узел.
struct list_head *p;
struct my_struct *my;
list_for_each(p, mine->list) {
my = list_entry(p, struct my_struct, list);
/*
* указатель my указывает на все структуры данных,
* в которые включено поле list
*/
}
Макрос list_for_each()
раскрывается в обычный цикл for
. Предыдущий пример раскрывается следующим образом.
for (p = mine->list->next; p != mine->list; p = p->next)
Кроме этого, макрос list_for_each()
также выполняет предварительную загрузку (prefetch) данных в память, если процессор поддерживает такую возможность, чтобы все данные следующих элементов списка гарантированно находились в памяти. Когда нет необходимости выполнять предварительную загрузку, можно использовать макрос __list_for_each()
, который работает в точности, как цикл for
. Если нет гарантии, что список содержит очень мало элементов или пустой, то всегда необходимо использовать версию с предварительной загрузкой. Никогда нельзя программировать цикл вручную, необходимо всегда использовать макрос.
Если необходимо выполнить прохождение по спискам в обратном порядке, то следует использовать макрос list_for_each_prev()
, который использует для прохождения указатель prev
, а не указатель next
.
Обратите внимание, что при прохождении связанного списка ничто не мешает удалять элементы из этого списка. Обычно, чтобы предотвратить конкурентный доступ, следует использовать блокировки. Макрос list_for_each_safe()
использует временные переменные, чтобы сделать прохождение списка безопасным при одновременном удалении элементов.
struct list_head *p, *n;
struct my_struct *my;
list_for_each_safe(p, n, &mine->list) {
my = list_entry(p, struct my_struct, list);
/*
* указатель my указывает на каждый экземпляр
* структуры my_struct в списке
*/
}
Обратите внимание, что этот макрос защищен только от операций удаления узлов списка. Для защиты отдельных элементов списка от конкурентного доступа необходимо использовать блокировки.
- 17.14. Анимирование и перемещение видов
- Перемещение по диалоговым окнам
- Копирование и перемещение фрагментов текста
- Перемещение и копирование файлов и папок
- Перемещение по листу
- Перемещение и копирование ячеек с помощью кнопки мыши
- Перемещение по бинарному дереву
- 8.4. Перемещение по иерархии файлов
- 8.4.3. Перемещение по иерархии: nftw()
- Перемещение по файловой системе
- Работа с данными, связанными с процессорами, на этапе компиляции
- Перемещение по связанному списку