O Torvalds Linus

Сайт о *nix системах и всем что с ними связано

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

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

Поэтому в Linux определена структура list head, два поля которой, next и prev, содержат указатели вперед и назад для элемента двунаправленного списка общего назначения. При этом важно отметить, что указатели в поле list head содержат адреса других полей list head, а не адреса структур, включающих В себя структуру list head.

Новый список создается с помощью макроса LIST_HEAD(list_name). Он объявляет новую переменную С именем list_name, имеющую тип list head, которая представляет собой пустой первый элемент, резервирующий место для головы нового списка. Кроме того, макрос инициализирует поля prev и next структуры list head так, что переменная list name указывает сама на себя.

В ядре Linux 2.6 применяется еще один вид двунаправленных списков. Они отличаются от списков list head тем, что не являются циклическими. В основном, они используются в качестве хеш – таблиц, у которых размер имеет большое значение, а возможности найти последний элемент за постоянное время нет. Голова такого списка хранится в структуре hiist head, которая всего лишь указывает на первый элемент списка (или содержит null, если список пуст). Каждый элемент представлен структурой hiist node, которая содержит указатель next на следующий элемент и указатель pprev на предыдущий элемент. Поскольку список не циклический, поле pprev первого элемента и поле next последнего содержит null.

Add A Comment