/root/src/xen/xen/common/sort.c
Line | Count | Source (jump to first uncovered line) |
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 <xen/types.h> |
8 | | |
9 | | static void u32_swap(void *a, void *b, int size) |
10 | 0 | { |
11 | 0 | u32 t = *(u32 *)a; |
12 | 0 | *(u32 *)a = *(u32 *)b; |
13 | 0 | *(u32 *)b = t; |
14 | 0 | } |
15 | | |
16 | | static void generic_swap(void *a, void *b, int size) |
17 | 0 | { |
18 | 0 | char t; |
19 | 0 |
|
20 | 0 | do { |
21 | 0 | t = *(char *)a; |
22 | 0 | *(char *)a++ = *(char *)b; |
23 | 0 | *(char *)b++ = t; |
24 | 0 | } while ( --size > 0 ); |
25 | 0 | } |
26 | | |
27 | | /* |
28 | | * sort - sort an array of elements |
29 | | * @base: pointer to data to sort |
30 | | * @num: number of elements |
31 | | * @size: size of each element |
32 | | * @cmp: pointer to comparison function |
33 | | * @swap: pointer to swap function or NULL |
34 | | * |
35 | | * This function does a heapsort on the given array. You may provide a |
36 | | * swap function optimized to your element type. |
37 | | * |
38 | | * Sorting time is O(n log n) both on average and worst-case. While |
39 | | * qsort is about 20% faster on average, it suffers from exploitable |
40 | | * O(n*n) worst-case behavior and extra memory requirements that make |
41 | | * it less suitable for kernel use. |
42 | | */ |
43 | | |
44 | | void sort(void *base, size_t num, size_t size, |
45 | | int (*cmp)(const void *, const void *), |
46 | | void (*swap)(void *, void *, int size)) |
47 | 2 | { |
48 | 2 | /* pre-scale counters for performance */ |
49 | 2 | int i = (num/2 - 1) * size, n = num * size, c, r; |
50 | 2 | |
51 | 2 | if (!swap) |
52 | 0 | swap = (size == 4 ? u32_swap : generic_swap); |
53 | 2 | |
54 | 2 | /* heapify */ |
55 | 79 | for ( ; i >= 0; i -= size ) |
56 | 77 | { |
57 | 215 | for ( r = i; r * 2 + size < n; r = c ) |
58 | 141 | { |
59 | 141 | c = r * 2 + size; |
60 | 141 | if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) ) |
61 | 99 | c += size; |
62 | 141 | if ( cmp(base + r, base + c) >= 0 ) |
63 | 3 | break; |
64 | 138 | swap(base + r, base + c, size); |
65 | 138 | } |
66 | 77 | } |
67 | 2 | |
68 | 2 | /* sort */ |
69 | 157 | for ( i = n - size; i >= 0; i -= size ) |
70 | 155 | { |
71 | 155 | swap(base, base + i, size); |
72 | 857 | for ( r = 0; r * 2 + size < i; r = c ) |
73 | 728 | { |
74 | 728 | c = r * 2 + size; |
75 | 728 | if ( (c < i - size) && (cmp(base + c, base + c + size) < 0) ) |
76 | 308 | c += size; |
77 | 728 | if ( cmp(base + r, base + c) >= 0 ) |
78 | 26 | break; |
79 | 702 | swap(base + r, base + c, size); |
80 | 702 | } |
81 | 155 | } |
82 | 2 | } |