I'm writing a loadable kernel module and I need to use the function qsort()
which apparently cannot be used in kernel space.
Is there a function that I can use that has a similar functionality ?
(Kernel version 3.5.0)
The linux kernel includes an implementation of heapsort which performs similar to quicksort. The kernel developers recommend heapsort over quicksort (within the kernel) and give the following rationale:
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);
}
That's a good question. The functionsort()
in lib/sort.c does the job, but it's a heap sort, you can learn more about this choice in lib/sort.c
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With