Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * A fast, small, non-recursive O(nlog n) sort for the Linux kernel | |
3 | * | |
4 | * Jan 23 2005 Matt Mackall <mpm@selenic.com> | |
5 | */ | |
6 | ||
7 | #include <linux/kernel.h> | |
8 | #include <linux/module.h> | |
ecec4cb7 | 9 | #include <linux/sort.h> |
1da177e4 | 10 | |
ecec4cb7 | 11 | static void u32_swap(void *a, void *b, int size) |
1da177e4 LT |
12 | { |
13 | u32 t = *(u32 *)a; | |
14 | *(u32 *)a = *(u32 *)b; | |
15 | *(u32 *)b = t; | |
16 | } | |
17 | ||
ecec4cb7 | 18 | static void generic_swap(void *a, void *b, int size) |
1da177e4 LT |
19 | { |
20 | char t; | |
21 | ||
22 | do { | |
23 | t = *(char *)a; | |
24 | *(char *)a++ = *(char *)b; | |
25 | *(char *)b++ = t; | |
26 | } while (--size > 0); | |
27 | } | |
28 | ||
29 | /* | |
30 | * sort - sort an array of elements | |
31 | * @base: pointer to data to sort | |
32 | * @num: number of elements | |
33 | * @size: size of each element | |
34 | * @cmp: pointer to comparison function | |
35 | * @swap: pointer to swap function or NULL | |
36 | * | |
37 | * This function does a heapsort on the given array. You may provide a | |
38 | * swap function optimized to your element type. | |
39 | * | |
40 | * Sorting time is O(n log n) both on average and worst-case. While | |
41 | * qsort is about 20% faster on average, it suffers from exploitable | |
42 | * O(n*n) worst-case behavior and extra memory requirements that make | |
43 | * it less suitable for kernel use. | |
44 | */ | |
45 | ||
46 | void sort(void *base, size_t num, size_t size, | |
47 | int (*cmp)(const void *, const void *), | |
48 | void (*swap)(void *, void *, int size)) | |
49 | { | |
50 | /* pre-scale counters for performance */ | |
51 | int i = (num/2) * size, n = num * size, c, r; | |
52 | ||
53 | if (!swap) | |
54 | swap = (size == 4 ? u32_swap : generic_swap); | |
55 | ||
56 | /* heapify */ | |
57 | for ( ; i >= 0; i -= size) { | |
58 | for (r = i; r * 2 < n; r = c) { | |
59 | c = r * 2; | |
60 | if (c < n - size && cmp(base + c, base + c + size) < 0) | |
61 | c += size; | |
62 | if (cmp(base + r, base + c) >= 0) | |
63 | break; | |
64 | swap(base + r, base + c, size); | |
65 | } | |
66 | } | |
67 | ||
68 | /* sort */ | |
69 | for (i = n - size; i >= 0; i -= size) { | |
70 | swap(base, base + i, size); | |
71 | for (r = 0; r * 2 < i; r = c) { | |
72 | c = r * 2; | |
73 | if (c < i - size && cmp(base + c, base + c + size) < 0) | |
74 | c += size; | |
75 | if (cmp(base + r, base + c) >= 0) | |
76 | break; | |
77 | swap(base + r, base + c, size); | |
78 | } | |
79 | } | |
80 | } | |
81 | ||
82 | EXPORT_SYMBOL(sort); | |
83 | ||
84 | #if 0 | |
85 | /* a simple boot-time regression test */ | |
86 | ||
87 | int cmpint(const void *a, const void *b) | |
88 | { | |
89 | return *(int *)a - *(int *)b; | |
90 | } | |
91 | ||
92 | static int sort_test(void) | |
93 | { | |
d28c2bc8 | 94 | int *a, i, r = 1; |
1da177e4 LT |
95 | |
96 | a = kmalloc(1000 * sizeof(int), GFP_KERNEL); | |
97 | BUG_ON(!a); | |
98 | ||
99 | printk("testing sort()\n"); | |
100 | ||
101 | for (i = 0; i < 1000; i++) { | |
102 | r = (r * 725861) % 6599; | |
103 | a[i] = r; | |
104 | } | |
105 | ||
106 | sort(a, 1000, sizeof(int), cmpint, NULL); | |
107 | ||
108 | for (i = 0; i < 999; i++) | |
109 | if (a[i] > a[i+1]) { | |
110 | printk("sort() failed!\n"); | |
111 | break; | |
112 | } | |
113 | ||
114 | kfree(a); | |
115 | ||
116 | return 0; | |
117 | } | |
118 | ||
119 | module_init(sort_test); | |
120 | #endif |