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