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

Question

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

有没有类似功能的函数可以使用？

（内核版本3.5.0）

- Varda Elentári

---

快速排序不是适合内核代码的算法——它的性能太不可预测了。使用一个可靠的堆排序算法会更好。 - Lee Daniel Crocker

@LeeDanielCrocker: qsort() 不一定需要使用快速排序。 - Michael Burr

是的，虽然这经常发生。但我仍会自己编写内核模块。 - Lee Daniel Crocker

Answer 1

Linux内核包含一个堆排序的实现，其表现类似于快速排序。内核开发人员建议在内核中使用堆排序而不是快速排序，并给出以下理由：

堆排序的排序时间在平均情况和最坏情况下都是O（n log n）。虽然快排平均比堆排快约20％，但它具有可利用的O（n * n）最坏情况行为和额外的内存要求，使其不太适合内核使用。

Header

#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);
}

- Bill Lynch

---

qsort 函数并不一定是使用快速排序算法实现的。语言标准只规定它进行排序。符合标准但有点变态的实现甚至可以使用冒泡排序。（是的，qsort 的名称是“快速排序”的缩写，但并没有要求必须这样实现。） - Keith Thompson

Answer 2

这是一个好问题。在lib/sort.c中的sort()函数可以完成此任务，但它使用堆排序，您可以在lib/sort.c中了解更多有关此选择的信息。

- Mathuin

---

这个回答缺乏足够的信息来构成一个好的答案。你是如何确定没有相应的东西的？ - djechlin

我在某个人的Linux内核存储库中的lib/qsort.c文件夹中找到了一个qsort实现，但是我在Torvald的存储库中找不到它。不过我会在他的存储库中使用grep命令查找qsort。 - Mathuin