[Из песочницы] Как использовать список ядра Linux для создания очереди
Приветствую! В данной статье рассматривается использование реализации двусвязного списка ядра Linux.
Двусвязный список в ядре Linux реализован в файле include/linux/list.h. Мы будем использовать адаптированный вариант list.h [1], который отличается от оригинального возможностью использовать его в userspace. Например, создадим очередь — структурe данных с доступом к элементам по принципу «первый пришёл — первый вышел» для произвольного типа данных на основе list.h.Для этого создаем структуру очереди и структуру элемента очереди:
Файл fifo.h:
#ifndef FIFO_H #define FIFO_H
#include «list.h»
struct fifo_item { void* data; // указатель на произвольные данные struct list_head list; // структура двусвязного списка };
struct fifo { struct list_head headlist; // двусвязный список int length; // длина void (*item_free)(struct fifo_item*); // метод освобождения памяти при удалении элемента };
// создание и удаление int fifo_init (struct fifo * fifo, void (*item_free)(struct fifo_item*)); int fifo_exit (struct fifo * fifo); // добавление и извлечение данных int fifo_push (struct fifo * fifo, void* data); void* fifo_pop (struct fifo * fifo); // операция над каждым элементом int fifo_for_each (struct fifo * fifo, void (*func)(struct fifo_item*));
#endif Начало и завершение работы со структурой очереди будет производится соответственно fifo_init и fifo_exit. Второй аргумент fifo_init — это функция, которая будет вызываться при завершении работы с очередью. Данная функция служит для освобождения памяти, занимаемой элементом буфера, при завершении работы с буфером.Добавление и извлечение данных производится при помощи fifo_push и fifo_pop соответственно. Данные в очереди хранятся по указателю, который передается вторым аргументом fifo_push, и возвращается fifo_pop.
Для выполнения однотипных операций над элементами очереди служит fifo_for_each. Вторым аргументом передается функция, реализующая требуемую операцию. Ниже приведена возможная реализация.
Файл fifo.с:
#include <stdlib.h>
#include «fifo.h»
int fifo_init (struct fifo *fifo, void (*item_free)(struct fifo_item*)) { INIT_LIST_HEAD (&(fifo→headlist));
fifo→length = 0; fifo→item_free=item_free;
return 0; }
int fifo_exit (struct fifo* fifo) { int res=0; struct list_head *pos, *q; struct fifo_item* item;
list_for_each_safe (pos, q, &(fifo→headlist)) { item=list_entry (pos, struct fifo_item, list); fifo→item_free (item); list_del (pos); free (item); }
return res; }
int fifo_push (struct fifo* fifo, void* data) { int res=-1; struct fifo_item* item;
item=(struct fifo_item*)malloc (sizeof (struct fifo_item));
if (NULL!= item) { item→data = data; list_add_tail (&(item→list), &(fifo→headlist));
fifo→length++; }
return res; }
void* fifo_pop (struct fifo* fifo) { void* res=NULL; struct fifo_item* item=list_entry (fifo→headlist.next, struct fifo_item, list);
if (! list_empty (&(fifo→headlist))) { res = item→data;
list_del (&(item→list));
free (item);
fifo→length--; }
return res; }
int fifo_for_each (struct fifo* fifo, void (*func)(struct fifo_item*)) { int res = 0; struct fifo_item* item;
list_for_each_entry (item, &(fifo→headlist), list) func (item);
return res; } В fifo_init инициализируется «голова» списка: INIT_LIST_HEAD (&(fifo→headlist)), устанавливается нулевая длина и метод для очистки памяти при завершении работы с очередью.В fifo_exit производится «защищенный» проход по всем элементам списка. Для каждого элемента очереди производится освобождение памяти, выделенной под данные, после чего элемент удаляется из списка, а память, которую он занимал, освобождается.
В fifo_push выделяется память под элемент списка. Если эта операция произведена успешно, в элементе очереди сохраняется указатель на данные и элемент добавляется в хвост списка. Длина очереди, соответственно, увеличивается.
В fifo_pop сначала находится первый элемент очереди. Если список не пуст и такой элемент найден, сохраняется указатель на данные. Затем элемент удаляется из списка, а память, которую он использовал, освобождается. Длина очереди, соответственно, уменьшается.
Чтобы использовать эту реализацию очереди для некоторой произвольной структуры данных, необходимо создать метод free для освобождения памяти данных элемента при завершении работы с буфером, а также метод для типовой операции над элементами буфера, если он требуется.
В данном примере используются mydata_free, который служит для освобождения памяти, выделенной под данные элемента очереди, а также mydata_print — функция, которая выводит элементы очереди на экран. В качестве данных выступает тип float в структуре mydata.
Файл main.с:
#include <stdlib.h>
#include «fifo.h»
struct mydata { float value; };
void* mydata_create (void) { return (struct mydata *)malloc (sizeof (struct mydata)); }
void mydata_free (struct fifo_item* item) { free (item→data); }
void mydata_print (struct fifo_item* item) { struct mydata* data = (struct mydata*)item→data;
printf («item: %f\n», data→value); }
int main () { int i; struct fifo myfifo; struct mydata* newdata;
// начало работы с FIFO fifo_init (&myfifo, mydata_free);
for (i=0; i<10; i++) { // новые данные newdata=mydata_create();
if (! newdata) { return -1; }
newdata→value = (float)i*0.1;
// добавляем в FIFO fifo_push (&myfifo, newdata); }
// печать данных printf («FIFO:\n»); fifo_for_each (&myfifo, mydata_print); printf (»\n»);
do { newdata = fifo_pop (&myfifo);
if (newdata) { printf («pop: %f\n», newdata→value); }
if (myfifo.length == 5) { printf (»\nFIFO:\n»); fifo_for_each (&myfifo, mydata_print); printf (»\n»); }
} while (newdata);
// конец работы с FIFO fifo_exit (&myfifo);
return 0; } Функция main содержит тестовые операции с буфером.
Результат работы:
$ ./testfifo FIFO: item: 0.000000 item: 0.100000 item: 0.200000 item: 0.300000 item: 0.400000 item: 0.500000 item: 0.600000 item: 0.700000 item: 0.800000 item: 0.900000
pop: 0.000000 pop: 0.100000 pop: 0.200000 pop: 0.300000 pop: 0.400000
FIFO: item: 0.500000 item: 0.600000 item: 0.700000 item: 0.800000 item: 0.900000
pop: 0.500000 pop: 0.600000 pop: 0.700000 pop: 0.800000 pop: 0.900000 Используемые источники 1.Linux Kernel Linked List Explained (русский перевод)
