Робота зі зв’язаними списками

Для роботи зі звязаними списками ядро ​​надає сімейство функцій Всі вони беруть покажчики на одну або більше структур lis t head Всі функції виконані як функції з підстановкою тіла (inline) на мові С, і їх все можна знайти у файлі

Цікаво, що час виконання всіх цих функцій масштабується як О (1) 1

Це означає, що вони виконуються протягом постійного інтервалу часу незалежно від кількості елементів списку, для якого вони викликаються Наприклад, час додавання елемента в звязаний список з 3 і 3000 елементів буде однаковим Це, можливо, і не викликає подиву, але проте, приємно

Для додавання елемента в звязаний список можна використати таку функцію

list_add(struct list_head *new, struct list head *head)

Ця функція додає вузол new в заданий звязаний список відразу після елемента head Оскільки звязаний список є кільцевим і для нього не існує понять перший і останнього вузлів, як параметр head можна використовувати покажчик на будь-який елемент списку Якщо як розглянутого параметра завжди надсилати покажчик на останній елемент, то цю функцію можна використовувати для організації стека

Для додавання елемента в кінець звязаного списку служить наступна функція

list_add_tail (struct list_head *new, struct list_head *head)

Ця функція додає новий елемент new в звязаний список відразу перед елементом, на який вказує параметр head Оскільки звязаний список є кільцевим, то, як і у випадку функції list_ad d (), як параметр head можна передавати покажчик на будь-який елемент списку Цю функцію можна використовувати для реалізації черги, якщо передавати покажчик на перший елемент

Для видалення вузла списку служить наступна функція

list_del (struct list_head *entry)

Ця функція дозволяє видалити зі списку елемент, на який вказує параметр entry Зверніть увагу, що ця функція не звільняє память, виділену під структуру даних, яка містить вузол списку, на який вказує параметр entry Ця функція просто видаляє вузол зі списку Після виклику цієї функції зазвичай необхідно видалити структуру даних, в якій знаходиться вузол list_head

Для видалення вузла зі списку і повторної ініціалізації цього вузла служить наступна функція

list_del_init(struct  list head *entry)

1 Питання складності алгоритмів розглядаються в приложени і В

Ця функція аналогічна функції list_del (), за винятком того, що вона додатково инициализирует зазначену структуру listhea d з тих міркувань, що ця структура даних більше не потрібна як елемент поточного списку і її повторно можна використовувати

Для переміщення вузла з одного списку в інший призначена наступна функція

list_move(struct list_head *list, struct list_head *head)

Ця функція видаляє елемент lis t з одного повязаного списку і додає його в інший звязаний список після елемента head

Для переміщення елемента з одного повязаного списку в кінець іншого служить наступна функція

list_move_tail (struct list_head *list, struct list_head *head)

Ця функція виконує те ж саме, що і функція list_rnov e (), але вставляє елемент перед елементом head

Для перевірки того, порожній чи список, служить функція

list_empty(struct list_head *head)

Ця функція повертає нульове значення, якщо звязаний список порожній, і нульове значення в іншому випадку

Для обєднання двох що не перекриваються повязаних списків служить наступна функція

list_splice(struct list_head *list, struct list_head *head)

Ця функція вставляє список, на який вказує параметр list, в інший список після параметра head

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

list splice init(struct list head *list, struct list head *head)

Ця функція аналогічна функції listsplice (), за винятком того, що параметр list, що представляє список, з якого віддаляються елементи, повторно ініціалізується

Як уникнути двох зайвих разименованія

Якщо вам вже доступні покажчики nex t і prev, то можна заощадити пару процесорних тактів (зокрема, час виконання операцій разименованія покажчиків) шляхом виклику внутрішніх функцій роботи з повязаними списками Всі раніше розглянуті функції в суті не роблять нічого, окрім отримання покажчиків nex t і pre v і викликів внутрішніх функцій Внутрішні функції мають ті ж імена, що і їх оболонки, але перед імям використовується два символи підкреслення Замість того щоб викликати функцію list _ del (list), можна викликати функцію __ list_del (prev, next) Це має сенс, тільки коли зазначені покажчики вже відомі В іншому випадку просто вийде некрасивий код Для докладної інформації про ці інтерфейсах можна звернутися до файлу

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

*

*