c - 在内核空间中是否有类似于 qsort() 的函数？

Question

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

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

（内核版本 3.5.0）

Answer 1

linux 内核包含一个堆排序的实现，其执行类似于快速排序。内核开发人员推荐堆排序而不是快速排序（在内核中），并给出以下理由：

[of 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

这是个好问题。lib/sort.csort()中的函数可以完成这项工作，但它是一种堆排序，您可以在lib/sort.c