WARNING - OLD ARCHIVES

This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
   
 
 
Xen 
 
Home Products Support Community News
 
   
 

xen-changelog

[Xen-changelog] [xen-unstable] make sort() generally available

To: xen-changelog@xxxxxxxxxxxxxxxxxxx
Subject: [Xen-changelog] [xen-unstable] make sort() generally available
From: Xen patchbot-unstable <patchbot-unstable@xxxxxxxxxxxxxxxxxxx>
Date: Fri, 24 Dec 2010 15:47:37 -0800
Delivery-date: Fri, 24 Dec 2010 15:54:27 -0800
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
List-help: <mailto:xen-changelog-request@lists.xensource.com?subject=help>
List-id: BK change log <xen-changelog.lists.xensource.com>
List-post: <mailto:xen-changelog@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/mailman/listinfo/xen-changelog>, <mailto:xen-changelog-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/mailman/listinfo/xen-changelog>, <mailto:xen-changelog-request@lists.xensource.com?subject=unsubscribe>
Reply-to: xen-devel@xxxxxxxxxxxxxxxxxxx
Sender: xen-changelog-bounces@xxxxxxxxxxxxxxxxxxx
# HG changeset patch
# User Keir Fraser <keir@xxxxxxx>
# 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@xxxxxxxxxx>
---
 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@xxxxxxxxxxx>
- */
-
-#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@xxxxxxxxxxx>
+ */
+
+#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@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog

<Prev in Thread] Current Thread [Next in Thread>
  • [Xen-changelog] [xen-unstable] make sort() generally available, Xen patchbot-unstable <=