Переміщення по зв’язаних списками

Тепер ми вже знаємо, як оголошувати, ініціалізувати і працювати зі звязаними списками в ядрі Це все добре, але не має жодного сенсу, якщо немає можливості працювати З даними, які зберігаються в списках Звязаний список – це просто контейнер, в якому зберігаються важливі дані Необхідно мати спосіб переміщення за списком і доступу до даних На щастя, ядро ​​надає набір корисних інтерфейсів для переміщення по звязаних списками і звернення до структур даних, які зберігаються в цих списках

Зверніть увагу, що, на відміну від підпрограм управління списками, операції перебору елементів списку з н вузлів масштабуються як О (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-&gtlist) {

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, &ampmine-&gtlist) {

my = list_entry (p, struct my_struct, list)

/*

* Покажчик my вказує на кожен екземпляр

* Структури my_struct в списку

*/

}

Зверніть увагу, що цей макрос захищенийтільки від операцій видалення вузлів списку Для захисту окремих елементів списку від конкурентного доступу необхідно використовувати блокування

Б

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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*