Второе издание
 Скачать 3.09 Mb.
|
|
А Связанные списки С вязанный список — это структура хранения информации (контейнер), которая может содержать переменное количество элементов данных, часто называе- мых узлами, и позволяет манипулировать этими данными. В отличие от статического массива, элементы связанного списка можно создавать динамически. Это дает воз- можность создавать переменное количество элементов списка, причем указанное ко- личество может быть неизвестно на этапе компиляции. Так как элементы связанных списков создаются в разные моменты времени, они не обязательно будут находиться в смежных областях оперативной памяти. Поэтому элементы списка должны быть связаны друг с другом таким образом, чтобы каждый элемент содержал указатель на следующий за ним элемент (next). Вставка или удаление элементов списка выполня- ется простым измепением указателей на следующий элемент. Структура связанного списка показана на рис. А.1. Рис. A.I. Однос&язный список В. некоторых связанных списках содержится указатель не только на следующий, но и на предыдущий элемент (prev). Эти списки называются двухсвязными (doubly link- ed), потому что они связаны как вперед, так и назад. Связанные списки, аналогичные тем, что показаны на рис.А.1, называются односвязиыми (singly linked). Двухсвязный список показан на рис. А.2. Рис. А.2. Двухсвязный список next next next NULL NULL prev next prev next prev next NULL Кольцевые связанные списки Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя next последнего элемента обычно устанавливается равным спе- циальному значению, обычно NULL, чтобы показать, что этот элемент списка явля- ется последним. в определенных случаях последний элемент списка не указывает на специальное значение, а указывает на первый элемент этого же списка. Такой список называется кольцевым связанным списком (circular linked list), поскольку связи образуют топологию кольца. Кольцевые связанные списки могут быть как односвязными, так и двухсвязными. В двухсвязных кольцевых списках указатель prev первого элемента указывает на последний элемент списка. На рис. А.З и А.4 показаны соответственно односвязные и двухсвязные кольцевые списки. Рис. A3. Односвязный кольцевой список Рис. А.4. Двухсвязный кольцевой список Стандартной реализацией связанных списков в ядре Linux является двухсвязный кольцевой список. Такие связанные списки обеспечивают наибольшую гибкость работы. Перемещение по связанному списку Перемещение по связанному списку выполняется последовательно (линейно). После того как просмотрен текущий элемент, выполнятся разыменование его указа- теля next, что позволяет обратиться к следующему за ним элементу и т.д. Это самый простой и наиболее подходящий метод перемещения но связанному списку. Если важна возможность произвольного доступа к любому элементу контейнера, то свя- занные списки не используются. Связанные списки используются, когда важна воз- можность динамического добавления и удаления элементов, а также возможность последовательного прохождения по всем элементам списка. 416 Приложение А next next next prev next prev next prev next Часто первый элемент списка представлен с помощью специального указателя, который называется головным элементом или головой (head), что дает возможность бы- стро и легко обращаться к первому элементу. В некольцевом связанном списке по- следний элемент отличается тем, что его указатель равен значению NULL. В кольце- вом связанном списке последний элемент отличается тем, что указывает на головной элемент. Таким образом прохождение списка можно выполнить линейно, начиная с первого элемента и заканчивая последним. В двухсвязном списке прохождение мож- но также выполнить и в противоположном направлении, начиная с последнего и за- канчивая первым элементом. Конечно, если задан определенный элемент списка, то можно перейти по списку вперед и назад на заданное количество элементов. При этом нет необходимости проходить весь список. Реализация связанных списков в ядре Linux В ядре Linux для прохождения по связанным спискам используется унифициро- ванный подход. При прохождении связанного списка, если не важен порядок про- хода, эту операцию не обязательно начинать с головного элемента, на самом деле вообще не важно, с какого элемента списка начинать прохождение! Важно только, чтобы при таком прохождении были пройдены все узлы. В большинстве случаев нет необходимости вводить концепции первого и последнего элементов. Если в кольце- вом связанном списке содержится коллекция несортированных данных, то любой эле- мент можно назвать головным. Для прохождения всего связанного списка необходи- мо взять любой элемент и следовать за указателями, пока снова не вернемся к тому элементу, с которого начали обход списка. Это избавляет от необходимости вводить специальный головной элемент. Кроме того, упрощаются процедуры работы со свя- занными списками. Каждая подпрограмма должна просто принимать указатель на один элемент — любой элемент списка. Разработчики ядра даже немножко гордятся такой остроумной реализацией. Связанные списки в ядре, так же как и в любой сложной программе, встречаются часто. Например, в ядре связанный список используется для хранения списка задач (структура task_struct каждого процесса является элементом связанного списка). Структура элемента списка Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 2.1 была пред- ложена единая реализация связанных списков в ядре. Сегодня во всех подсистемах ядра используется официальная реализация. Для новых разработок необходимо ис- пользовать только существующий интерфейс и не нужно изобретать велосипед. Код работы со связанными списками определен в файле < l i n u x / l i s t . h > , a основная структура данных имеет очень простой вид. struct list_head { struct list_head *next, *prev; }; Обратите внимание на характерное имя структуры l i s t h e a d . Такое название выбрано, чтобы подчеркнуть, что списку не нужно головного элемента. Наоборот, Связанные списки 417 обход списка можно начинать с любого элемента, и каждый элемент может быть головным. В связи с этим все элементы списка называются головными (list head). Указатель next указывает на следующий элемент списка, а указатель prev— на пред- ыдущий элемент списка. Если текущий элемент списка является последним, то его указатель next указывает на первый узел. Если же текущим элементом является пер- вый, то его указатель prev указывает па последний узел списка. Благодаря элегант- ной реализации связанных списков без концепции головного элемента, можно во- обще не вводить понятия первого и последнего элементов. Структура l i s t h e a d сама по себе бесполезна. Ее необходимо включать в другие структуры данных. struct my_struct { struct list_head list; unsigned long dog; void *cat; }; Перед использованием элементы связанных списков должны быть инициализиро- ваны. Так как элементы связанных списков обычно создаются динамически (иначе, вероятно, не нужно использовать связанный список), то эти элементы, как правило, инициализируются во время выполнения. struct my_struct *р; /* выделить память для структуры my_struct .. */ p->dog = 0; p->cat = NULL; INIT_LIST_HEAD(&p->list); Если структура данных создается статически во время компиляции и на нее есть непосредственная ссылка, то инициализацию можно выполнить следующим обра- зом. struct my_struct mine = { .list = LIST_HEAD_INIT(mine.list), .dog = 0, .cat = NULL }; Для того чтобы создать и инициализировать связанный список, можно использо- вать следующее объявление. static LIST_HEAD(fox); Эта команда позволяет статически создать связанный список с именем fox. Нет необходимости явно выполнять какие-либо операции со служебными полями элементов связанного списка. Вместо этого необходимо просто включить структуру узла связанного списка в вашу структуру данных, чтобы можно было легко манипули- ровать данными и выполнять прохождение по связанному списку. 418 Приложение А Работа со связанными списками Для работы со связанными списками ядро предоставляет семейство функций. Все они принимают указатели на одну или более структур l i s t head. Все функции вы- полнены как функции с подстановкой тела (inline) на языке С, и их все можно найти в файле < l i n u x / l i s t . h > . Интересно, что время выполнения всех этих функций масштабируется как О (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. Поскольку связанный список являет- ся кольцевым, то, как и в случае функции l i s t _ a d d (), в качестве параметра head можно передавать указатель на любой элемент списка. Эту функцию можно исполь- зовать для реализации очереди, если передавать указатель на первый элемент. Для удаления узла списка служит следующая функция. list_del (struct list_head *entry) Эта функция позволяет удалить из списка элемент, на который указывает пара- метр e n t r y . Обратите внимание, что эта функция не освобождает память, выде- ленную под структуру данных, содержащую узел списка, на который указывает па- раметр e n t r y . Данная функция просто удаляет узел из списка. После вызова этой функции обычно необходимо удалить структуру данных, в которой находится узел l i s t _ h e a d . Для удаления узла из списка и повторной инициализации этого узла служит сле- дующая функция. list_del_init(struct list head *entry) 1 Вопросы сложности алгоритмов рассматриваются в приложении В. Связанные списки 419 Эта. функция аналогична функции l i s t _ d e l ( ) , за исключением того, что она до- полнительно инициализирует указанную структуру l i s t h e a d из тех соображений, что эта структура данных больше не нужна в качестве элемента текущего списка и ее повторно можно использовать. Для перемещения узла из одного списка в другой предназначена следующая функ- ция. list_move(struct list_head *list, struct list_head *head) Эта функция удаляет элемент l i s t из одного связанного списка и добавляет его в другой связанный список после элемента head. Для перемещения элемента из одного связанного списка в конец другого служит следующая функция. list_move_tail (struct list_head *list, struct list_head *head) Эта функция выполняет то же самое, что и функция list_rnove (), но вставляет элемент перед элементом head. Для проверки того, пуст ли список, служит функция. list_empty (struct list_head *head) Эта функция возвращает ненулевое значение, если связанный список пуст, и ну- левое значение в противном случае. Для объединения двух не перекрывающихся связанных списков служит следую- щая функция. list_splice(struct list_head *list, struct list_head *head) Эта функция вставляет список, на который указывает параметр l i s t , в другой список после параметра head. Для объединения двух не перекрывающихся списков и повторной инициализа- ции старого головного элемента служит следующая функция. list splice init(struct list head *list, struct list head *head) Эта функция аналогична функции l i s t s p l i c e ( ) , за исключением того, что па- раметр l i s t , представляющий список, из которого удаляются элементы, повторно инициализируется. Как избежать двух лишних разыменований Если вам уже доступны указатели n e x t и prev, то можно сэкономить пару процессорных тактов (в частности, время выполнения операций разыменования указателей) путем вызова внутрен- них функций работы со связанными списками. Все ранее рассмотренные функции в сущности не делают ничего, кроме получения указателей n e x t и p r e v и вызовов внутренних функций. Внутренние функции имеют те же имена, что и их оболочки, но перед именем используется два символа подчеркивания. Вместо того чтобы вызвать функцию l i s t _ d e l ( l i s t ) , можно вызвать функцию _ _ l i s t _ d e l ( p r e v , n e x t ) . Это имеет смысл, только когда указанные ука- затели уже известны. В противном случае просто получится некрасивый код. Для подробной информации об этих интерфейсах можно обратиться к файлу < l i n u x / l i s t . h > . 420 Приложение А Перемещение по связанным спискам Теперь мы уже знаем, как объявлять, инициализировать и работать со связан- ными списками в ядре. Это все хорошо, но не имеет никакого смысла, если нет возможности работать С данными, которые хранятся в списках! Связанный спи- сок — это просто контейнер, в котором хранятся важные данные. Необходимо иметь способ перемещения по списку и доступа к данным. К счастью, ядро предоставляет набор полезных интерфейсов для перемещения по связанным спискам и обращения к структурам данных, которые хранятся в этих списках. Обратите внимание, что, в отличие от подпрограмм управления списками, опера- ции перебора элементов списка из н узлов масштабируются как О (n). Наиболее простой способ выполнять итерации по элементам связанного спи- ска — это использовать макрос l i s t _ f o r _ e a c h () . Этот макрос принимает два па- раметра— указатели на структуры list_head. Первый параметр указывает на теку- щий элемент списка, а второй — на любой элемент списка, для которого необходимо обойти все узлы. На каждой итерации цикла первый параметр макроса указывает на текущий элемент списка, пока не будут пройдены все элементы, как в следующем примере. struct list_head *р; list_for_each(p, list) { /* р указывает на каждый элемент списка list */ } Это пока все еще бесполезно! Указатель на структуру узла списка — это не то, что нам нужно. Нам нужен указатель на структуру данных, в которой содержится струк- тура узла. В показанном ранее примере структуры данных my_struct необходимо получить указатель на каждый экземпляр структуры my_struct, а не на их поля l i s t . Макрос l i s t e n t r y ( ) возвращает структуру данных, которая содержит соот- ветствующий элемент list_head. Этот макрос принимает три параметра: указатель на текущий узел, тип структуры данных, в которую включен узел списка, и имя поля структуры данных, в которой хранится этот узел. struct list_head *р; 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 (р = mine->list->next; р != mine->list; р = p->next) Кроме этого, макрос l i s t _ f o r _ e a c h ( ) также выполняет предварительную за- грузку (prefetch) данных в память, если процессор поддерживает такую возможность, Связанные списки 421 чтобы все данные следующих элементов списка гарантированно находились в памя- ти. Когда нет необходимости выполнять предварительную загрузку, можно использо- вать макрос 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 в списке */ } Обратите внимание, что этот макрос защищен только от операций удаления узлов списка. Для защиты отдельных элементов списка от конкурентного доступа необхо- димо использовать блокировки. 422 Приложение А Б Генератор случайных чисел ядра В ядре Linux реализован генератор случайных чисел, который теоретически мо- жет генерировать истинно случайные числа. Генератор случайных чисел собира- ет в пул энтропии шумы внешней среды, которые поступают из драйверов устройств. Этот пул доступен как в ядре, так и для пользовательских процессов в качестве ис- точника данных, которые не только случайны внутри системы, но и недетерминиро- ваны для внешних источников атак. Такие случайные числа используются различны- ми внешними приложениями, особенно для целей криптографии. Истинно случайные числа отличаются от псевдослучайных чисел, которые гене- рируются библиотечными функциями языка С. Псевдослучайные числа создаются с помощью детерминированных функций. Хотя такие функции и могут генериро- вать последовательности чисел, которые обладают некоторыми свойствами истин- но случайных чисел, тем не менее такие числа только статистически случайны. Псевдослучайные числа являются детерминированными, потому что если известно хотя бы одно число последовательности, то можно определить и все остальные. Если известно так называемое порождающее число последовательности (seed), то обыч- но по нему определяется и вся последовательность. Для приложений, которые тре- буют истинно случайных чисел, как, например, криптография, псевдослучайные чис- ла обычно не подходят. В отличие от псевдослучайных чисел, истинно случайные числа не зависят от той функции, которая используется для их генерации. Более того, если известен некото- рый член последовательности истинно случайных чисел, то внешний наблюдатель не сможет определить, какие числа будет выдавать генератор в будущем, т.е. такой генератор - недетерминированный. Физический термин энтропия— это мера беспорядка и случайности в любой си- стеме. Энтропия измеряется в единицах энергии на единицу температуры (Джоуль на градус Кельвина). Когда Клод Шеннон (Claude Shennon) 1 , создатель информаци- онной теории, искал термин для представления случайности информации, великий 1 Клод Шеннон (30 апреля 1916-24 февраля 2001) работал инженером в компании Bell Labs. В его наиболее известной работе Математическая теории связи, опубликованной в 1948 году, впервые были разработаны основы информационной теории и было введено понятие энтропии Шеннона. Шеннон также любил кататься на одноколесном велосипеде. математик Джон фон Нейман (John von Neumann) 2 предложил ему использовать термин энтропия, потому что никто толком не понимает, что за этим понятием кро- ется. Шеннон согласился, и сегодня это звучит как энтропия Шеннона. Некоторые ученые считают, что такое двойное название только вносит путаницу, и когда речь идет об информации, то используют термин неопределенность. Разработчики ядра, на- оборот, считают, что "энтропия"- это "круто", и поддерживают использование дан- ного термина. При рассмотрении генераторов случайных чисел понятие энтропии Шеннона яв- ляется очень важным. Эта характеристика измеряется в битах на символ. Высокое значение энтропии означает, что в последовательности символов мало полезной (точнее, предсказуемой) информации и много случайного "мусора". Ядро поддер- живает пул энтропии, который пополняется данными, возникающими в результате недетерминированных событий, связанных с аппаратными устройствами. В идеале, этот пул содержит полностью случайные данные. Для того чтобы иметь представ- ление о значении энтропии пула, ядро постоянно вычисляет меру неопределенно- сти данных в пуле. По мере того как ядро добавляет данные в пул, оно оценивает меру случайности добавляемых данных. И наоборот, по мере того как данные из- влекаются из пула, ядро уменьшает значение оценки энтропии. Соответствующая количественная характеристика называется оценкой энтропии. Если значение оценки энтропии становится равным нулю, то ядро может отказаться выполнять запрос по считыванию данных из пула. Генератор случайных чисел ядра был предложен в версии 1.3.30 и находится в файле drivers/char/random.с. |