Приветствую!
В данной статье рассматривается использование реализации двусвязного списка ядра 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: %fn", 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: %fn", 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 (русский перевод)
Автор: spot62
