是否有一个类似于qsort()的函数在内核空间中使用？

Question

我正在编写一个可加载的内核模块,我需要使用qsort()显然不能在内核空间中使用的函数.

我可以使用具有类似功能的功能吗？

(内核版本3.5.0)

Answer 1

linux内核包含一个heapsort的实现,其执行类似于quicksort.内核开发人员建议使用快速排序(在内核中)并提供以下基本原理:

[heapsort]的排序时间是平均和最差情况下的O(n log n).虽然qsort的平均速度提高了大约20%,但它遭受了可利用的O(n*n)最坏情况行为和额外的内存需求,这使得它不太适合内核使用.

头

#include <linux/sort.h>

原型

void sort(
    void *base, size_t num, size_t size,
    int (*cmp_func)(const void *, const void *),
    void (*swap_func)(void *, void *, int size));

用法

static int compare(const void *lhs, const void *rhs) {
    int lhs_integer = *(const int *)(lhs);
    int rhs_integer = *(const int *)(rhs);

    if (lhs_integer < rhs_integer) return -1;
    if (lhs_integer > rhs_integer) return 1;
    return 0;
}

void example() {
    int values[1024] = {...};
    sort(values, 1024, sizeof(int), &compare, NULL);
}

Answer 2

这是个好问题.该功能sort()在LIB/sort.c做工作,但它是一个堆排序,你可以了解更多关于这种选择在lib/sort.c