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 120