Главная » Ядро Linux » Перемещение по связанным спискам

0

Теперь  мы уже знаем, как  объявлять, инициализировать и работать  со связанными  списками в ядре.  Это  все хорошо, но  не  имеет  никакого смысла, если  нет возможности работать  С данными, которые хранятся в списках!  Связанный список — это просто  контейнер, в котором хранятся важные  данные. Необходимо иметь способ  перемещения по списку  и доступа  к данным. К счастью, ядро  предоставляет набор  полезных интерфейсов для перемещения по связанным спискам и обращения к структурам данных, которые хранятся в этих  списках.

Обратите внимание, что, в отличие  от подпрограмм управления списками, операции перебора элементов списка из н узлов масштабируются как О (n).

Наиболее простой способ  выполнять итерации по  элементам связанного списка — это использовать макрос   list_for_eac h  () . Этот макрос  принимает два параметра—  указатели на  структуры  list_head .  Первый параметр указывает на текущий элемент списка, а второй — на любой  элемент списка, для которого необходимо обойти  все узлы.  На  каждой  итерации цикла  первый параметр макроса указывает на текущий элемент списка, пока  не будут пройдены все элементы, как в следующем примере.

struct list_head *р;

list_for_each(p, list) {

/* р указывает на каждый элемент списка list */

}

Это пока все еще бесполезно! Указатель  на структуру узла списка — это не то, что нам  нужно.  Нам  нужен  указатель  на структуру данных, в которой содержится структура узла.  В показанном ранее  примере структуры  данных  my_struc t  необходимо получить  указатель  на  каждый   экземпляр структуры  my_struct , а не  на  их поля list . Макрос  listentry( )  возвращает структуру  данных, которая содержит соответствующий элемент list_head . Этот  макрос  принимает три  параметра: указатель на текущий узел, тип структуры  данных, в которую  включен узел списка, и имя  поля структуры  данных, в которой хранится этот узел.

struct list_head *р;

struct my_struct *my;

list_for_each(p, mine->list) {

my = list_entry(p, struct my_struct, list);

/*

* указатель my указывает на все структуры данных,

* в которые включено поле list

*/

}

Макрос list_for_eac h ()  раскрывается в обычный цикл  for.  Предыдущий пример  раскрывается следующим образом,

for (р = mine->list->next; р != mine->list; р = p->next)

Кроме этого, макрос   list_for_each( )  также  выполняет предварительную загрузку  (prefetch) данных  в память, если  процессор поддерживает такую возможность,

чтобы  все данные  следующих  элементов списка гарантированно находились в памяти. Когда  нет необходимости выполнять предварительную загрузку, можно  использовать макрос       list_for_each() , который работает  в точности, как цикл  for. Если нет гарантии, что список содержит очень  мало  элементов или  пустой, то всегда необходимо использовать версию  с предварительной загрузкой. Никогда нельзя  программировать цикл  вручную, необходимо всегда использовать макрос.

Если  необходимо выполнить прохождение по спискам в обратном порядке, то следует  использовать макрос   list_for_each_pre v () , который использует для  прохождения указатель  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 в списке

*/

}

Обратите  внимание, что  этот  макрос  защищен  только от  операций удаления  узлов списка.   Для  защиты   отдельных   элементов   списка   от  конкурентного  доступа  необходимо   использовать  блокировки.

Б

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии