Сортировка связанного списка ядра linux
У меня есть программа на языке Си, которая моделирует различные алгоритмы планирования. Информация о процессе считывается из файла. Информация о каждом процессе в файле хранится в следующей структуре:
struct task_struct {
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
unsigned int flags; /* per process flags, defined below */
int on_rq;
int prio, static_prio, normal_prio;
const struct sched_class *sched_class;
struct list_head tasks;
pid_t pid;
int arr;
/* simplify accounting */
int ticks;
int start_tick;
int end_tick;
int burst;
};
У меня есть структура "очереди", которая будет содержать список задач / процессов
struct rq {
struct task_struct *curr, *idle, *stop;
struct list_head task_root;
};
Я немного понимаю, как работают связанные списки ядра, и у меня есть пользовательская версия списка.h. похоже, что большинство взаимодействий со списком определяются в списке.h. у кого-нибудь есть идея, как это сделать пытаетесь реализовать алгоритм сортировки (возможно, слияние), используя функции в этом файле?
1 ответ:
Почему бы просто не использовать
list_sort
, определенный вlinux/list_sort.h
? Синтаксис:/** * list_sort - sort a list * @priv: private data, opaque to list_sort(), passed to @cmp * @head: the list to sort * @cmp: the elements comparison function * * This function implements "merge sort", which has O(nlog(n)) * complexity. * * The comparison function @cmp must return a negative value if @a * should sort before @b, and a positive value if @a should sort after * @b. If @a and @b are equivalent, and their original relative * ordering is to be preserved, @cmp must return 0. */ void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, struct list_head *a, struct list_head *b))