Back to home page

LXR

 
 

    


0001 /*
0002  * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
0003  *
0004  * Jan 23 2005  Matt Mackall <mpm@selenic.com>
0005  */
0006 
0007 #include <linux/types.h>
0008 #include <linux/export.h>
0009 #include <linux/sort.h>
0010 
0011 static int alignment_ok(const void *base, int align)
0012 {
0013     return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
0014         ((unsigned long)base & (align - 1)) == 0;
0015 }
0016 
0017 static void u32_swap(void *a, void *b, int size)
0018 {
0019     u32 t = *(u32 *)a;
0020     *(u32 *)a = *(u32 *)b;
0021     *(u32 *)b = t;
0022 }
0023 
0024 static void u64_swap(void *a, void *b, int size)
0025 {
0026     u64 t = *(u64 *)a;
0027     *(u64 *)a = *(u64 *)b;
0028     *(u64 *)b = t;
0029 }
0030 
0031 static void generic_swap(void *a, void *b, int size)
0032 {
0033     char t;
0034 
0035     do {
0036         t = *(char *)a;
0037         *(char *)a++ = *(char *)b;
0038         *(char *)b++ = t;
0039     } while (--size > 0);
0040 }
0041 
0042 /**
0043  * sort - sort an array of elements
0044  * @base: pointer to data to sort
0045  * @num: number of elements
0046  * @size: size of each element
0047  * @cmp_func: pointer to comparison function
0048  * @swap_func: pointer to swap function or NULL
0049  *
0050  * This function does a heapsort on the given array. You may provide a
0051  * swap_func function optimized to your element type.
0052  *
0053  * Sorting time is O(n log n) both on average and worst-case. While
0054  * qsort is about 20% faster on average, it suffers from exploitable
0055  * O(n*n) worst-case behavior and extra memory requirements that make
0056  * it less suitable for kernel use.
0057  */
0058 
0059 void sort(void *base, size_t num, size_t size,
0060       int (*cmp_func)(const void *, const void *),
0061       void (*swap_func)(void *, void *, int size))
0062 {
0063     /* pre-scale counters for performance */
0064     int i = (num/2 - 1) * size, n = num * size, c, r;
0065 
0066     if (!swap_func) {
0067         if (size == 4 && alignment_ok(base, 4))
0068             swap_func = u32_swap;
0069         else if (size == 8 && alignment_ok(base, 8))
0070             swap_func = u64_swap;
0071         else
0072             swap_func = generic_swap;
0073     }
0074 
0075     /* heapify */
0076     for ( ; i >= 0; i -= size) {
0077         for (r = i; r * 2 + size < n; r  = c) {
0078             c = r * 2 + size;
0079             if (c < n - size &&
0080                     cmp_func(base + c, base + c + size) < 0)
0081                 c += size;
0082             if (cmp_func(base + r, base + c) >= 0)
0083                 break;
0084             swap_func(base + r, base + c, size);
0085         }
0086     }
0087 
0088     /* sort */
0089     for (i = n - size; i > 0; i -= size) {
0090         swap_func(base, base + i, size);
0091         for (r = 0; r * 2 + size < i; r = c) {
0092             c = r * 2 + size;
0093             if (c < i - size &&
0094                     cmp_func(base + c, base + c + size) < 0)
0095                 c += size;
0096             if (cmp_func(base + r, base + c) >= 0)
0097                 break;
0098             swap_func(base + r, base + c, size);
0099         }
0100     }
0101 }
0102 
0103 EXPORT_SYMBOL(sort);
0104 
0105 #if 0
0106 #include <linux/slab.h>
0107 /* a simple boot-time regression test */
0108 
0109 int cmpint(const void *a, const void *b)
0110 {
0111     return *(int *)a - *(int *)b;
0112 }
0113 
0114 static int sort_test(void)
0115 {
0116     int *a, i, r = 1;
0117 
0118     a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
0119     BUG_ON(!a);
0120 
0121     printk("testing sort()\n");
0122 
0123     for (i = 0; i < 1000; i++) {
0124         r = (r * 725861) % 6599;
0125         a[i] = r;
0126     }
0127 
0128     sort(a, 1000, sizeof(int), cmpint, NULL);
0129 
0130     for (i = 0; i < 999; i++)
0131         if (a[i] > a[i+1]) {
0132             printk("sort() failed!\n");
0133             break;
0134         }
0135 
0136     kfree(a);
0137 
0138     return 0;
0139 }
0140 
0141 module_init(sort_test);
0142 #endif