Mailing List Archive

# HG changeset patch
# User Keir Fraser <keir@xen.org>
# Date 1293180406 0
# Node ID ef30046259f017f0723a40ea693d3cb8ff5ad743
# Parent ceb508436e6e45cd67dd97299e82439734147a01
make sort() generally available

Rather than having this general library function only on ia64, move it
into common code, to be used by x86 exception table sorting too.

Signed-off-by: Jan Beulich <jbeulich@novell.com>
---
xen/arch/ia64/linux-xen/sort.c | 122 -------------------------------
xen/include/asm-ia64/linux/sort.h | 10 --
xen/arch/ia64/linux-xen/Makefile | 1
xen/arch/ia64/linux-xen/README.origin | 1
xen/common/Makefile | 1
xen/common/sort.c | 82 ++++++++++++++++++++
xen/include/asm-ia64/linux/README.origin | 1
xen/include/xen/sort.h | 10 ++
8 files changed, 93 insertions(+), 135 deletions(-)

diff -r ceb508436e6e -r ef30046259f0 xen/arch/ia64/linux-xen/Makefile
--- a/xen/arch/ia64/linux-xen/Makefile Fri Dec 24 08:42:52 2010 +0000
+++ b/xen/arch/ia64/linux-xen/Makefile Fri Dec 24 08:46:46 2010 +0000
@@ -12,7 +12,6 @@ obj-y += setup.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
diff -r ceb508436e6e -r ef30046259f0 xen/arch/ia64/linux-xen/README.origin
--- a/xen/arch/ia64/linux-xen/README.origin Fri Dec 24 08:42:52 2010 +0000
+++ b/xen/arch/ia64/linux-xen/README.origin Fri Dec 24 08:46:46 2010 +0000
@@ -21,7 +21,6 @@ setup.c -> linux/arch/ia64/kernel/setu
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
diff -r ceb508436e6e -r ef30046259f0 xen/arch/ia64/linux-xen/sort.c
--- a/xen/arch/ia64/linux-xen/sort.c Fri Dec 24 08:42:52 2010 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,122 +0,0 @@
-/*
- * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
- *
- * Jan 23 2005 Matt Mackall <mpm@selenic.com>
- */
-
-#include <linux/kernel.h>
-#include <linux/module.h>
-#ifdef XEN
-#include <linux/types.h>
-#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
diff -r ceb508436e6e -r ef30046259f0 xen/common/Makefile
--- a/xen/common/Makefile Fri Dec 24 08:42:52 2010 +0000
+++ b/xen/common/Makefile Fri Dec 24 08:46:46 2010 +0000
@@ -22,6 +22,7 @@ obj-y += schedule.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
diff -r ceb508436e6e -r ef30046259f0 xen/common/sort.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/xen/common/sort.c Fri Dec 24 08:46:46 2010 +0000
@@ -0,0 +1,82 @@
+/*
+ * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
+ *
+ * Jan 23 2005 Matt Mackall <mpm@selenic.com>
+ */
+
+#include <xen/types.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: 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);
+ }
+ }
+}
diff -r ceb508436e6e -r ef30046259f0 xen/include/asm-ia64/linux/README.origin
--- a/xen/include/asm-ia64/linux/README.origin Fri Dec 24 08:42:52 2010 +0000
+++ b/xen/include/asm-ia64/linux/README.origin Fri Dec 24 08:46:46 2010 +0000
@@ -16,7 +16,6 @@ percpu.h -> linux/include/linux/percpu.
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
diff -r ceb508436e6e -r ef30046259f0 xen/include/asm-ia64/linux/sort.h
--- a/xen/include/asm-ia64/linux/sort.h Fri Dec 24 08:42:52 2010 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,10 +0,0 @@
-#ifndef _LINUX_SORT_H
-#define _LINUX_SORT_H
-
-#include <linux/types.h>
-
-void sort(void *base, size_t num, size_t size,
- int (*cmp)(const void *, const void *),
- void (*swap)(void *, void *, int));
-
-#endif
diff -r ceb508436e6e -r ef30046259f0 xen/include/xen/sort.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/xen/include/xen/sort.h Fri Dec 24 08:46:46 2010 +0000
@@ -0,0 +1,10 @@
+#ifndef __XEN_SORT_H__
+#define __XEN_SORT_H__
+
+#include <xen/types.h>
+
+void sort(void *base, size_t num, size_t size,
+ int (*cmp)(const void *, const void *),
+ void (*swap)(void *, void *, int));
+
+#endif /* __XEN_SORT_H__ */

_______________________________________________
Xen-changelog mailing list
Xen-changelog@lists.xensource.com
http://lists.xensource.com/xen-changelog