Реалізація пов’язаних списків в ядрі Linux

У ядрі Linux для проходження по звязаних списками використовується уніфікований підхід При проходженні звязаного списку, якщо не важливий порядок проходу, цю операцію не обовязково починати з головного елемента, насправді взагалі не важливо, з якого елементу списку починати проходження Важливо тільки, щоб при такому проходженні були пройдені всі вузли У більшості випадків немає необхідності вводити концепції першого і останнього елементів Якщо в кільцевому повязаному списку міститься колекція несортованих даних, то будь елемент можна назвати головним Для проходження всього повязаного списку необхідно взяти будь-який елемент і слідувати за покажчиками, поки знову не повернемося до того елемента, з якого почали обхід списку Це позбавляє від необхідності вводити спеціальний головний елемент Крім того, спрощуються процедури роботи зі звязаними списками Кожна підпрограма повинна просто приймати покажчик на один елемент – будь елемент списку Розробники ядра навіть трошки пишаються такою дотепною реалізацією

Повязані списки в ядрі, так само як і в будь-якій складній програмі, зустрічаються часто Наприклад, в ядрі звязаний список використовується для зберігання списку завдань (структура task_struc t кожного процесу є елементом повязаного списку)

Структура елемента списку

Раніше в ядрі було кілька реалізацій повязаних списків Проте в таких випадках необхідна єдина реалізація з метою прибрати різний код, який виконує однакові дії Під час розробки серії ядер 21 була запропонована єдина реалізація повязаних списків в ядрі Сьогодні в усіх підсистемах ядра використовується офіційна реалізація Для нових розробок необхідно використовувати тільки існуючий інтерфейс і не потрібно винаходити велосипед

Код роботи зі звязаними списками визначений у файлі , A основна структура даних має дуже простий вигляд

struct list_head {

struct list_head *next, *prev

}

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

обхід списку можна починати з будь-якого елемента, і кожен елемент може бути головним У звязку з цим всі елементи списку називаються головними (list head) Покажчик next вказує на наступний елемент списку, а покажчик prev-на попередній елемент списку Якщо поточний елемент списку є останнім, то його покажчик next вказує на перший вузол Якщо ж поточним елементом є першим, то його покажчик pre v вказує па останній вузол списку Завдяки елегантній реалізації повязаних списків без концепції головного елемента, можна взагалі не вводити поняття перший і останнього елементів

Структура listhea d сама по собі марна Її необхідно включати в інші структури даних

struct my_struct {

struct list_head list

unsigned long dog

void *cat

}

Перед використанням елементи повязаних списків повинні бути ініціалізовані Так як елементи повязаних списків зазвичай створюються динамічно (інакше, ймовірно, не потрібно використовувати звязаний список), то ці елементи, як правило, не започатковано під час виконання

struct my_struct * р

/ * Виділити память для структури my_struct . * /

p-&gtdog = 0

p-&gtcat = NULL INIT_LIST_HEAD(&ampp-&gtlist)

Якщо структура даних створюється статично під час компіляції і на неї є безпосередня посилання, то ініціалізацію можна виконати таким чином

struct my_struct mine = {

.list = LIST_HEAD_INIT(minelist),

.dog = 0,

.cat = NULL

}

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

static LIST_HEAD(fox)

Ця команда дозволяє статично створити звязаний список з імям fox

Немає необхідності явно виконувати будь-які операції зі службовими полями елементів повязаного списку Замість цього необхідно просто включити структуру вузла повязаного списку в вашу структуру даних, щоб можна було легко маніпулювати даними і виконувати проходження по звязаному списку

Джерело: Лав, Роберт Розробка ядра 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>

*

*