我正在编写一个可加载的内核模块,我需要使用显然不能在内核空间中使用的函数qsort().
有可以使用的函数有类似的功能吗？
(内核版本3.5.0)
解决方法
linux内核包括一个执行类似于quicksort的heapsort的实现.内核开发人员推荐使用快速排序(在内核中),并提供以下理由：
Sorting time [of heapsort] is O(n log n) both on average and worst-case. While
qsort is about 20% faster on average,it suffers from exploitable
O(n*n) worst-case behavior and extra memory requirements that make
it less suitable for kernel use.
头
#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);
}