Rather having this general library function only on ia64, move it into common code. Signed-off-by: Jan Beulich --- a/xen/arch/ia64/linux-xen/Makefile +++ b/xen/arch/ia64/linux-xen/Makefile @@ -12,7 +12,6 @@ obj-y += sal.o obj-y += setup.o obj-y += smpboot.o obj-y += smp.o -obj-y += sort.o obj-y += time.o obj-y += tlb.o obj-y += unaligned.o --- a/xen/arch/ia64/linux-xen/README.origin +++ b/xen/arch/ia64/linux-xen/README.origin @@ -21,7 +21,6 @@ sal.c -> linux/arch/ia64/kernel/sal.c setup.c -> linux/arch/ia64/kernel/setup.c smp.c -> linux/arch/ia64/kernel/smp.c smpboot.c -> linux/arch/ia64/kernel/smpboot.c -sort.c -> linux/lib/sort.c time.c -> linux/arch/ia64/kernel/time.c tlb.c -> linux/arch/ia64/mm/tlb.c unaligned.c -> linux/arch/ia64/kernel/unaligned.c --- a/xen/arch/ia64/linux-xen/sort.c +++ /dev/null @@ -1,122 +0,0 @@ -/* - * A fast, small, non-recursive O(nlog n) sort for the Linux kernel - * - * Jan 23 2005 Matt Mackall - */ - -#include -#include -#ifdef XEN -#include -#endif - -void u32_swap(void *a, void *b, int size) -{ - u32 t = *(u32 *)a; - *(u32 *)a = *(u32 *)b; - *(u32 *)b = t; -} - -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: pointer to comparison function - * @swap: pointer to swap function or NULL - * - * This function does a heapsort on the given array. You may provide a - * swap 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)(const void *, const void *), - void (*swap)(void *, void *, int size)) -{ - /* pre-scale counters for performance */ - int i = (num/2) * size, n = num * size, c, r; - - if (!swap) - swap = (size == 4 ? u32_swap : generic_swap); - - /* heapify */ - for ( ; i >= 0; i -= size) { - for (r = i; r * 2 < n; r = c) { - c = r * 2; - if (c < n - size && cmp(base + c, base + c + size) < 0) - c += size; - if (cmp(base + r, base + c) >= 0) - break; - swap(base + r, base + c, size); - } - } - - /* sort */ - for (i = n - size; i >= 0; i -= size) { - swap(base, base + i, size); - for (r = 0; r * 2 < i; r = c) { - c = r * 2; - if (c < i - size && cmp(base + c, base + c + size) < 0) - c += size; - if (cmp(base + r, base + c) >= 0) - break; - swap(base + r, base + c, size); - } - } -} - -EXPORT_SYMBOL(sort); - -#if 0 -/* 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 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -20,6 +20,7 @@ obj-y += sched_sedf.o obj-y += schedule.o obj-y += shutdown.o obj-y += softirq.o +obj-y += sort.o obj-y += spinlock.o obj-y += stop_machine.o obj-y += string.o --- /dev/null +++ b/xen/common/sort.c @@ -0,0 +1,78 @@ +/* + * A fast, small, non-recursive O(nlog n) sort for the Linux kernel + * + * Jan 23 2005 Matt Mackall + */ + +#include + +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: pointer to comparison function + * @swap: pointer to swap function or NULL + * + * This function does a heapsort on the given array. You may provide a + * swap 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)(const void *, const void *), + void (*swap)(void *, void *, int size)) +{ + /* pre-scale counters for performance */ + int i = (num/2) * size, n = num * size, c, r; + + if (!swap) + swap = (size == 4 ? u32_swap : generic_swap); + + /* heapify */ + for ( ; i >= 0; i -= size) { + for (r = i; r * 2 < n; r = c) { + c = r * 2; + if (c < n - size && cmp(base + c, base + c + size) < 0) + c += size; + if (cmp(base + r, base + c) >= 0) + break; + swap(base + r, base + c, size); + } + } + + /* sort */ + for (i = n - size; i >= 0; i -= size) { + swap(base, base + i, size); + for (r = 0; r * 2 < i; r = c) { + c = r * 2; + if (c < i - size && cmp(base + c, base + c + size) < 0) + c += size; + if (cmp(base + r, base + c) >= 0) + break; + swap(base + r, base + c, size); + } + } +} --- a/xen/include/asm-ia64/linux/README.origin +++ b/xen/include/asm-ia64/linux/README.origin @@ -16,7 +16,6 @@ notifier.h -> linux/include/linux/notif percpu.h -> linux/include/linux/percpu.h preempt.h -> linux/include/linux/preempt.h seqlock.h -> linux/include/linux/seqlock.h -sort.h -> linux/include/linux/sort.h stddef.h -> linux/include/linux/stddef.h thread_info.h -> linux/include/linux/thread_info.h time.h -> linux/include/linux/time.h --- a/xen/include/asm-ia64/linux/sort.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef _LINUX_SORT_H -#define _LINUX_SORT_H - -#include - -void sort(void *base, size_t num, size_t size, - int (*cmp)(const void *, const void *), - void (*swap)(void *, void *, int)); - -#endif --- /dev/null +++ b/xen/include/xen/sort.h @@ -0,0 +1,10 @@ +#ifndef __SORT_H__ +#define __SORT_H__ + +#include + +void sort(void *base, size_t num, size_t size, + int (*cmp)(const void *, const void *), + void (*swap)(void *, void *, int)); + +#endif /* __SORT_H__ */