Contents of /alx-src/tags/kernel26-2.6.12-alx-r9/lib/sort.c
Parent Directory | Revision Log
Revision 630 -
(show annotations)
(download)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 2431 byte(s)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 2431 byte(s)
Tag kernel26-2.6.12-alx-r9
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 | { |
93 | int *a, i, r = 1; |
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 |