Перемещение по связанным спискам

Перемещение по связанным спискам

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

Обратите внимание, что, в отличие от подпрограмм управления списками, операции перебора элементов списка из 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 в списке

 */

}

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Перемещение по листу

Из книги Компьютер на 100. Начинаем с Windows Vista автора Зозуля Юрий

Перемещение по листу Данные всегда вводятся в активную ячейку, выделенную жирной рамкой (см. рис. 6.2). Для смены активной ячейки есть два способа.? Щелчок кнопкой мыши на нужной ячейке.? Клавиши со стрелками (?, ?, ?, ?) (они сделают активной соседнюю ячейку в выбранном


Перемещение объектов

Из книги AutoCAD 2009 автора Орлов Андрей Александрович

Перемещение объектов Теперь, когда вам привычны различные способы, которые существуют для выделения объектов, настало время некоторых действий. Команда MOVE перемещает объекты на расстояние и угол, предложенные пользователем.Чтобы вызвать команду MOVE, щелкните на кнопке


Перемещение и копирование

Из книги Pinnacle Studio 11 автора Чиртик Александр Анатольевич

Перемещение и копирование Чтобы изменить место положения перехода, достаточно переместить его значок с помощью мыши на новое место.Если для большого количества сцен проекта подойдет один и тот же переход (например, при создании слайд-шоу), то можно использовать


Перемещение объектов

Из книги AutoCAD 2009 для студента. Самоучитель автора Соколова Татьяна Юрьевна

Перемещение объектов Команда MOVE осуществляет перемещение объектов. Она вызывается из падающего меню Modify ? Move или щелчком на пиктограмме Move на панели инструментов Modify.Запросы команды MOVE: Select objects: – выбрать объекты Select objects: – нажать клавишу Enter для завершения выбора


Перемещение объектов

Из книги AutoCAD 2009. Начали! автора Соколова Татьяна Юрьевна

Перемещение объектов Команда MOVE осуществляет перемещение объектов. Она вызывается из падающего меню Modify ? Move или щелчком на пиктограмме Move на панели инструментов Modify.Запросы команды MOVE:Select objects: – выбрать объектыSelect objects: – нажать клавишу Enter для завершения выбора


Перемещение объектов

Из книги AutoCAD 2010 автора Орлов Андрей Александрович

Перемещение объектов Теперь, когда вам привычны различные способы выделения объектов, настало время некоторых действий.Команда MOVE перемещает объекты на расстояние и угол, предложенные пользователем.При запуске команды MOVE в области командной строки AutoCAD появляется


Перемещение объектов

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Перемещение объектов Необходимость возвращать память операционной системе порождает одну из самых утонченных частей механизма: сборщик мусора может при необходимости перемещать объекты.Это свойство вызывает головную боль при реализации сборщика, но оно делает этот


24.2.3. Перемещение курсора

Из книги Разработка приложений в среде Linux. Второе издание автора Джонсон Майкл К.

24.2.3. Перемещение курсора Как и в большинстве программ, курсор терминала используется библиотекой S-Lang для обозначения позиции, принятой по умолчанию, для ввода текста и для подсказки пользователю. Программы S-Lang могут перемещать курсор с помощью показанной ниже


2.2.3. Перемещение окон

Из книги С компьютером на ты. Самое необходимое автора Егоров А. А.

2.2.3. Перемещение окон Также окна можно перемещать из одной части экрана в другую. Для этого наведите мышью на строку заголовка, нажмите и удерживайте левую кнопку и перетащите окно.Альтернативный способ — щелкните правой кнопкой мыши на строке заголовка и в открывшемся


Перемещение объектов

Из книги AutoCAD 2009. Учебный курс автора Соколова Татьяна Юрьевна

Перемещение объектов Команда MOVE осуществляет перемещение объектов. Она вызывается из падающего меню Modify ? Move или щелчком на пиктограмме Move на панели инструментов Modify.Запросы команды


Перемещение объектов

Из книги AutoCAD 2008 для студента: популярный самоучитель автора Соколова Татьяна Юрьевна

Перемещение объектов Команда MOVE осуществляет перемещение объектов. Она вызывается из падающего меню Modify ? Move или щелчком на пиктограмме Move на панели инструментов Modify.Запросы команды MOVE:Select objects: – выбрать объектыSelect objects: – нажать клавишу Enter для завершения выбора


Перемещение букв

Из книги Adobe Flash. Создание аркад, головоломок и других игр с помощью ActionScript автора Розенцвейг Гэри

Перемещение букв Исходный файл: Textfly.fla Во многих Flash-роликах по экрану перемешается текст. Сушествует множество способов создания этого эффекта, некоторые из них проиллюстрированы примерами, которые имеются на Web-сайте поддержки книги.Задача проектаВ данном разделе


Присоединиться к спискам рассылки по вопросам безопасности

Из книги IT-безопасность: стоит ли рисковать корпорацией? автора Маккарти Линда

Присоединиться к спискам рассылки по вопросам безопасности Важно вовремя узнавать об очередной угрозе, возникающей в Интернете. Если ваш персонал технической поддержки не будет в курсе новых дыр и проблем в безопасности, то хакеры опередят его на несколько шагов.


Б.1.5. Перемещение по файлу

Из книги Программирование для Linux. Профессиональный подход автора Митчелл Марк

Б.1.5. Перемещение по файлу В файловом дескрипторе запоминается текущая позиция в файле. При чтении или записи данных указатель текущей позиции перемещается на то количество байтов, которое было прочитано или записано. Но иногда нужно осуществлять простое перемещение по


Перемещение окон

Из книги Как приручить компьютер за несколько часов автора Ремнева Ирина

Перемещение окон Окна на рабочем столе Windows ХР очень часто появляются не там, где вам хотелось бы. Это нормально. С помощью мыши вы легко можете перетянуть его в любое другое место экрана. Лучше и удобнее всего перетягивать окно, ухватив строку заголовка.Теперь вы знаете,