c - カーネル空間で使用される qsort() に似た関数はありますか?

Question

ロード可能なカーネル モジュールを作成していますが、qsort()明らかにカーネル空間では使用できない関数を使用する必要があります。

同様の機能を持つ私が使用できる機能はありますか？

(カーネルバージョン 3.5.0)

Answer 1

Linux カーネルには、クイックソートと同様に実行するヒープソートの実装が含まれています。カーネル開発者は、(カーネル内での) クイックソートよりもヒープソートを推奨しており、次の理由を挙げています。

[ヒープソートの] ソート時間は、平均でも最悪の場合でも 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);
}