|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [xen master] lib: move sort code
commit f772b592b75d3144174d4c645b916f2718d9cce5
Author: Jan Beulich <jbeulich@xxxxxxxx>
AuthorDate: Fri Dec 18 13:25:40 2020 +0100
Commit: Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Fri Dec 18 13:25:40 2020 +0100
lib: move sort code
Build this code into an archive, partly paralleling bsearch().
Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
Acked-by: Julien Grall <jgrall@xxxxxxxxxx>
Acked-by: Wei Liu <wl@xxxxxxx>
Reviewed-by: Bertrand Marquis <bertrand.marquis@xxxxxxx>
---
xen/common/Makefile | 1 -
xen/common/sort.c | 82 -----------------------------------------------------
xen/lib/Makefile | 1 +
xen/lib/sort.c | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 83 insertions(+), 83 deletions(-)
diff --git a/xen/common/Makefile b/xen/common/Makefile
index e8ce23acea..7a4e652b57 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -36,7 +36,6 @@ obj-y += rcupdate.o
obj-y += rwlock.o
obj-y += shutdown.o
obj-y += softirq.o
-obj-y += sort.o
obj-y += smp.o
obj-y += spinlock.o
obj-y += stop_machine.o
diff --git a/xen/common/sort.c b/xen/common/sort.c
deleted file mode 100644
index 7b7544bbc2..0000000000
--- a/xen/common/sort.c
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- * 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 - 1) * 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 + size < n; r = c )
- {
- c = r * 2 + size;
- 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 + size < i; r = c )
- {
- c = r * 2 + size;
- 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 --git a/xen/lib/Makefile b/xen/lib/Makefile
index f12dab7a73..42cf7a1164 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -6,3 +6,4 @@ lib-y += ctype.o
lib-y += list-sort.o
lib-y += parse-size.o
lib-y += rbtree.o
+lib-y += sort.o
diff --git a/xen/lib/sort.c b/xen/lib/sort.c
new file mode 100644
index 0000000000..ee983d0bc3
--- /dev/null
+++ b/xen/lib/sort.c
@@ -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 - 1) * 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 + size < n; r = c )
+ {
+ c = r * 2 + size;
+ 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 + size < i; r = c )
+ {
+ c = r * 2 + size;
+ 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);
+ }
+ }
+}
--
generated by git-patchbot for /home/xen/git/xen.git#master
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |