1.1 --- a/xen/arch/ia64/linux-xen/Makefile	Fri Dec 24 08:42:52 2010 +0000
     1.2 +++ b/xen/arch/ia64/linux-xen/Makefile	Fri Dec 24 08:46:46 2010 +0000
     1.3 @@ -12,7 +12,6 @@ obj-y += sal.o
     1.4  obj-y += setup.o
     1.5  obj-y += smpboot.o
     1.6  obj-y += smp.o
     1.7 -obj-y += sort.o
     1.8  obj-y += time.o
     1.9  obj-y += tlb.o
    1.10  obj-y += unaligned.o

     2.1 --- a/xen/arch/ia64/linux-xen/README.origin	Fri Dec 24 08:42:52 2010 +0000
     2.2 +++ b/xen/arch/ia64/linux-xen/README.origin	Fri Dec 24 08:46:46 2010 +0000
     2.3 @@ -21,7 +21,6 @@ sal.c			-> linux/arch/ia64/kernel/sal.c
     2.4  setup.c			-> linux/arch/ia64/kernel/setup.c
     2.5  smp.c			-> linux/arch/ia64/kernel/smp.c
     2.6  smpboot.c		-> linux/arch/ia64/kernel/smpboot.c
     2.7 -sort.c			-> linux/lib/sort.c
     2.8  time.c			-> linux/arch/ia64/kernel/time.c
     2.9  tlb.c			-> linux/arch/ia64/mm/tlb.c
    2.10  unaligned.c		-> linux/arch/ia64/kernel/unaligned.c

     3.1 --- a/xen/arch/ia64/linux-xen/sort.c	Fri Dec 24 08:42:52 2010 +0000
     3.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.3 @@ -1,122 +0,0 @@
     3.4 -/*
     3.5 - * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
     3.6 - *
     3.7 - * Jan 23 2005  Matt Mackall <mpm@selenic.com>
     3.8 - */
     3.9 -
    3.10 -#include <linux/kernel.h>
    3.11 -#include <linux/module.h>
    3.12 -#ifdef XEN
    3.13 -#include <linux/types.h>
    3.14 -#endif
    3.15 -
    3.16 -void u32_swap(void *a, void *b, int size)
    3.17 -{
    3.18 -	u32 t = *(u32 *)a;
    3.19 -	*(u32 *)a = *(u32 *)b;
    3.20 -	*(u32 *)b = t;
    3.21 -}
    3.22 -
    3.23 -void generic_swap(void *a, void *b, int size)
    3.24 -{
    3.25 -	char t;
    3.26 -
    3.27 -	do {
    3.28 -		t = *(char *)a;
    3.29 -		*(char *)a++ = *(char *)b;
    3.30 -		*(char *)b++ = t;
    3.31 -	} while (--size > 0);
    3.32 -}
    3.33 -
    3.34 -/*
    3.35 - * sort - sort an array of elements
    3.36 - * @base: pointer to data to sort
    3.37 - * @num: number of elements
    3.38 - * @size: size of each element
    3.39 - * @cmp: pointer to comparison function
    3.40 - * @swap: pointer to swap function or NULL
    3.41 - *
    3.42 - * This function does a heapsort on the given array. You may provide a
    3.43 - * swap function optimized to your element type.
    3.44 - *
    3.45 - * Sorting time is O(n log n) both on average and worst-case. While
    3.46 - * qsort is about 20% faster on average, it suffers from exploitable
    3.47 - * O(n*n) worst-case behavior and extra memory requirements that make
    3.48 - * it less suitable for kernel use.
    3.49 - */
    3.50 -
    3.51 -void sort(void *base, size_t num, size_t size,
    3.52 -	  int (*cmp)(const void *, const void *),
    3.53 -	  void (*swap)(void *, void *, int size))
    3.54 -{
    3.55 -	/* pre-scale counters for performance */
    3.56 -	int i = (num/2) * size, n = num * size, c, r;
    3.57 -
    3.58 -	if (!swap)
    3.59 -		swap = (size == 4 ? u32_swap : generic_swap);
    3.60 -
    3.61 -	/* heapify */
    3.62 -	for ( ; i >= 0; i -= size) {
    3.63 -		for (r = i; r * 2 < n; r  = c) {
    3.64 -			c = r * 2;
    3.65 -			if (c < n - size && cmp(base + c, base + c + size) < 0)
    3.66 -				c += size;
    3.67 -			if (cmp(base + r, base + c) >= 0)
    3.68 -				break;
    3.69 -			swap(base + r, base + c, size);
    3.70 -		}
    3.71 -	}
    3.72 -
    3.73 -	/* sort */
    3.74 -	for (i = n - size; i >= 0; i -= size) {
    3.75 -		swap(base, base + i, size);
    3.76 -		for (r = 0; r * 2 < i; r = c) {
    3.77 -			c = r * 2;
    3.78 -			if (c < i - size && cmp(base + c, base + c + size) < 0)
    3.79 -				c += size;
    3.80 -			if (cmp(base + r, base + c) >= 0)
    3.81 -				break;
    3.82 -			swap(base + r, base + c, size);
    3.83 -		}
    3.84 -	}
    3.85 -}
    3.86 -
    3.87 -EXPORT_SYMBOL(sort);
    3.88 -
    3.89 -#if 0
    3.90 -/* a simple boot-time regression test */
    3.91 -
    3.92 -int cmpint(const void *a, const void *b)
    3.93 -{
    3.94 -	return *(int *)a - *(int *)b;
    3.95 -}
    3.96 -
    3.97 -static int sort_test(void)
    3.98 -{
    3.99 -	int *a, i, r = 1;
   3.100 -
   3.101 -	a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
   3.102 -	BUG_ON(!a);
   3.103 -
   3.104 -	printk("testing sort()\n");
   3.105 -
   3.106 -	for (i = 0; i < 1000; i++) {
   3.107 -		r = (r * 725861) % 6599;
   3.108 -		a[i] = r;
   3.109 -	}
   3.110 -
   3.111 -	sort(a, 1000, sizeof(int), cmpint, NULL);
   3.112 -
   3.113 -	for (i = 0; i < 999; i++)
   3.114 -		if (a[i] > a[i+1]) {
   3.115 -			printk("sort() failed!\n");
   3.116 -			break;
   3.117 -		}
   3.118 -
   3.119 -	kfree(a);
   3.120 -
   3.121 -	return 0;
   3.122 -}
   3.123 -
   3.124 -module_init(sort_test);
   3.125 -#endif

     4.1 --- a/xen/common/Makefile	Fri Dec 24 08:42:52 2010 +0000
     4.2 +++ b/xen/common/Makefile	Fri Dec 24 08:46:46 2010 +0000
     4.3 @@ -22,6 +22,7 @@ obj-y += sched_arinc653.o
     4.4  obj-y += schedule.o
     4.5  obj-y += shutdown.o
     4.6  obj-y += softirq.o
     4.7 +obj-y += sort.o
     4.8  obj-y += spinlock.o
     4.9  obj-y += stop_machine.o
    4.10  obj-y += string.o

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/xen/common/sort.c	Fri Dec 24 08:46:46 2010 +0000
     5.3 @@ -0,0 +1,82 @@
     5.4 +/*
     5.5 + * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
     5.6 + *
     5.7 + * Jan 23 2005  Matt Mackall <mpm@selenic.com>
     5.8 + */
     5.9 +
    5.10 +#include <xen/types.h>
    5.11 +
    5.12 +static void u32_swap(void *a, void *b, int size)
    5.13 +{
    5.14 +    u32 t = *(u32 *)a;
    5.15 +    *(u32 *)a = *(u32 *)b;
    5.16 +    *(u32 *)b = t;
    5.17 +}
    5.18 +
    5.19 +static void generic_swap(void *a, void *b, int size)
    5.20 +{
    5.21 +    char t;
    5.22 +
    5.23 +    do {
    5.24 +        t = *(char *)a;
    5.25 +        *(char *)a++ = *(char *)b;
    5.26 +        *(char *)b++ = t;
    5.27 +    } while ( --size > 0 );
    5.28 +}
    5.29 +
    5.30 +/*
    5.31 + * sort - sort an array of elements
    5.32 + * @base: pointer to data to sort
    5.33 + * @num: number of elements
    5.34 + * @size: size of each element
    5.35 + * @cmp: pointer to comparison function
    5.36 + * @swap: pointer to swap function or NULL
    5.37 + *
    5.38 + * This function does a heapsort on the given array. You may provide a
    5.39 + * swap function optimized to your element type.
    5.40 + *
    5.41 + * Sorting time is O(n log n) both on average and worst-case. While
    5.42 + * qsort is about 20% faster on average, it suffers from exploitable
    5.43 + * O(n*n) worst-case behavior and extra memory requirements that make
    5.44 + * it less suitable for kernel use.
    5.45 + */
    5.46 +
    5.47 +void sort(void *base, size_t num, size_t size,
    5.48 +          int (*cmp)(const void *, const void *),
    5.49 +          void (*swap)(void *, void *, int size))
    5.50 +{
    5.51 +    /* pre-scale counters for performance */
    5.52 +    int i = (num/2) * size, n = num * size, c, r;
    5.53 +
    5.54 +    if (!swap)
    5.55 +        swap = (size == 4 ? u32_swap : generic_swap);
    5.56 +
    5.57 +    /* heapify */
    5.58 +    for ( ; i >= 0; i -= size )
    5.59 +    {
    5.60 +        for ( r = i; r * 2 < n; r  = c )
    5.61 +        {
    5.62 +            c = r * 2;
    5.63 +            if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) )
    5.64 +                c += size;
    5.65 +            if ( cmp(base + r, base + c) >= 0 )
    5.66 +                break;
    5.67 +            swap(base + r, base + c, size);
    5.68 +        }
    5.69 +    }
    5.70 +
    5.71 +    /* sort */
    5.72 +    for ( i = n - size; i >= 0; i -= size )
    5.73 +    {
    5.74 +        swap(base, base + i, size);
    5.75 +        for ( r = 0; r * 2 < i; r = c )
    5.76 +        {
    5.77 +            c = r * 2;
    5.78 +            if ( (c < i - size) && (cmp(base + c, base + c + size) < 0) )
    5.79 +                c += size;
    5.80 +            if ( cmp(base + r, base + c) >= 0 )
    5.81 +                break;
    5.82 +            swap(base + r, base + c, size);
    5.83 +        }
    5.84 +    }
    5.85 +}

     6.1 --- a/xen/include/asm-ia64/linux/README.origin	Fri Dec 24 08:42:52 2010 +0000
     6.2 +++ b/xen/include/asm-ia64/linux/README.origin	Fri Dec 24 08:46:46 2010 +0000
     6.3 @@ -16,7 +16,6 @@ notifier.h		-> linux/include/linux/notif
     6.4  percpu.h		-> linux/include/linux/percpu.h
     6.5  preempt.h		-> linux/include/linux/preempt.h
     6.6  seqlock.h		-> linux/include/linux/seqlock.h
     6.7 -sort.h			-> linux/include/linux/sort.h
     6.8  stddef.h		-> linux/include/linux/stddef.h
     6.9  thread_info.h		-> linux/include/linux/thread_info.h
    6.10  time.h			-> linux/include/linux/time.h

     7.1 --- a/xen/include/asm-ia64/linux/sort.h	Fri Dec 24 08:42:52 2010 +0000
     7.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.3 @@ -1,10 +0,0 @@
     7.4 -#ifndef _LINUX_SORT_H
     7.5 -#define _LINUX_SORT_H
     7.6 -
     7.7 -#include <linux/types.h>
     7.8 -
     7.9 -void sort(void *base, size_t num, size_t size,
    7.10 -	  int (*cmp)(const void *, const void *),
    7.11 -	  void (*swap)(void *, void *, int));
    7.12 -
    7.13 -#endif

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/xen/include/xen/sort.h	Fri Dec 24 08:46:46 2010 +0000
     8.3 @@ -0,0 +1,10 @@
     8.4 +#ifndef __XEN_SORT_H__
     8.5 +#define __XEN_SORT_H__
     8.6 +
     8.7 +#include <xen/types.h>
     8.8 +
     8.9 +void sort(void *base, size_t num, size_t size,
    8.10 +          int (*cmp)(const void *, const void *),
    8.11 +          void (*swap)(void *, void *, int));
    8.12 +
    8.13 +#endif /* __XEN_SORT_H__ */