diff options
author | 2015-08-04 12:17:53 -0700 | |
---|---|---|
committer | 2015-08-04 15:44:42 -0700 | |
commit | 9ca8dbcc65cfc63d6f5ef3312a33184e1d726e00 (patch) | |
tree | 1c9cafbcd35f783a87880a10f85d1a060db1a563 /kernel/lib/sort.c | |
parent | 98260f3884f4a202f9ca5eabed40b1354c489b29 (diff) |
Add the rt linux 4.1.3-rt3 as base
Import the rt linux 4.1.3-rt3 as OPNFV kvm base.
It's from git://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git linux-4.1.y-rt and
the base is:
commit 0917f823c59692d751951bf5ea699a2d1e2f26a2
Author: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Date: Sat Jul 25 12:13:34 2015 +0200
Prepare v4.1.3-rt3
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
We lose all the git history this way and it's not good. We
should apply another opnfv project repo in future.
Change-Id: I87543d81c9df70d99c5001fbdf646b202c19f423
Signed-off-by: Yunhong Jiang <yunhong.jiang@intel.com>
Diffstat (limited to 'kernel/lib/sort.c')
-rw-r--r-- | kernel/lib/sort.c | 123 |
1 files changed, 123 insertions, 0 deletions
diff --git a/kernel/lib/sort.c b/kernel/lib/sort.c new file mode 100644 index 000000000..43c9fe73a --- /dev/null +++ b/kernel/lib/sort.c @@ -0,0 +1,123 @@ +/* + * A fast, small, non-recursive O(nlog n) sort for the Linux kernel + * + * Jan 23 2005 Matt Mackall <mpm@selenic.com> + */ + +#include <linux/types.h> +#include <linux/export.h> +#include <linux/sort.h> + +static void u32_swap(void *a, void *b, int size) +{ + u32 t = *(u32 *)a; + *(u32 *)a = *(u32 *)b; + *(u32 *)b = t; +} + +static void generic_swap(void *a, void *b, int size) +{ + char t; + + do { + t = *(char *)a; + *(char *)a++ = *(char *)b; + *(char *)b++ = t; + } while (--size > 0); +} + +/** + * sort - sort an array of elements + * @base: pointer to data to sort + * @num: number of elements + * @size: size of each element + * @cmp_func: pointer to comparison function + * @swap_func: pointer to swap function or NULL + * + * This function does a heapsort on the given array. You may provide a + * swap_func function optimized to your element type. + * + * Sorting time is O(n log n) both on average and worst-case. While + * qsort is about 20% faster on average, it suffers from exploitable + * O(n*n) worst-case behavior and extra memory requirements that make + * it less suitable for kernel use. + */ + +void sort(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *), + void (*swap_func)(void *, void *, int size)) +{ + /* pre-scale counters for performance */ + int i = (num/2 - 1) * size, n = num * size, c, r; + + if (!swap_func) + swap_func = (size == 4 ? u32_swap : generic_swap); + + /* heapify */ + for ( ; i >= 0; i -= size) { + for (r = i; r * 2 + size < n; r = c) { + c = r * 2 + size; + if (c < n - size && + cmp_func(base + c, base + c + size) < 0) + c += size; + if (cmp_func(base + r, base + c) >= 0) + break; + swap_func(base + r, base + c, size); + } + } + + /* sort */ + for (i = n - size; i > 0; i -= size) { + swap_func(base, base + i, size); + for (r = 0; r * 2 + size < i; r = c) { + c = r * 2 + size; + if (c < i - size && + cmp_func(base + c, base + c + size) < 0) + c += size; + if (cmp_func(base + r, base + c) >= 0) + break; + swap_func(base + r, base + c, size); + } + } +} + +EXPORT_SYMBOL(sort); + +#if 0 +#include <linux/slab.h> +/* a simple boot-time regression test */ + +int cmpint(const void *a, const void *b) +{ + return *(int *)a - *(int *)b; +} + +static int sort_test(void) +{ + int *a, i, r = 1; + + a = kmalloc(1000 * sizeof(int), GFP_KERNEL); + BUG_ON(!a); + + printk("testing sort()\n"); + + for (i = 0; i < 1000; i++) { + r = (r * 725861) % 6599; + a[i] = r; + } + + sort(a, 1000, sizeof(int), cmpint, NULL); + + for (i = 0; i < 999; i++) + if (a[i] > a[i+1]) { + printk("sort() failed!\n"); + break; + } + + kfree(a); + + return 0; +} + +module_init(sort_test); +#endif |