linux-kernel - [PATCH -mm 1/2] sort: Add obj_sort() for sorting all kinds of random-accessible objects

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <48CA58A4.8020902@cn.fujitsu.com>
Date:	Fri, 12 Sep 2008 19:55:16 +0800
From:	Lai Jiangshan <laijs@...fujitsu.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
CC:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Matt Mackall <mpm@...enic.com>,
	Paul Menage <menage@...gle.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: [PATCH -mm 1/2] sort: Add obj_sort() for sorting all kinds of random-accessible
 objects


current sort can only sort objects on continuous memory,
but sometimes we need to sort objects on noncontinuous memory,
this patch provide obj_sort() for this.

Sometimes a C struct(the container of objects, or objects) may be designed
with some high-level language's semantic meaning. obj_sort() can sort
for them.

obj_sort() is need for sort pids for cgroup.tasks file.

Signed-off-by: Lai Jiangshan <laijs@...fujitsu.com>
---
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..d1e2f71 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -7,4 +7,8 @@ void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
 
+void obj_sort(void *container, size_t begin, size_t end,
+		int (*cmp)(const void *container, size_t left, size_t right),
+		void (*swap)(void *container, size_t left, size_t right));
+
 #endif
diff --git a/lib/sort.c b/lib/sort.c
index 6abbaf3..d0c80ce 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -2,6 +2,9 @@
  * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
  *
  * Jan 23 2005  Matt Mackall <mpm@...enic.com>
+ *
+ * Sep 12 2008  Lai Jiangshan <laijs@...fujitsu.com>
+ *       Add obj_sort for sorting all kinds of random-accessible objects.
  */
 
 #include <linux/kernel.h>
@@ -56,7 +59,7 @@ void sort(void *base, size_t num, size_t size,
 
 	/* heapify */
 	for ( ; i >= 0; i -= size) {
-		for (r = i; r * 2 + size < n; r  = c) {
+		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;
@@ -82,6 +85,63 @@ void sort(void *base, size_t num, size_t size,
 
 EXPORT_SYMBOL(sort);
 
+/**
+ * obj_sort - sort objects of an random-accessible objects container
+ * @container: pointer to container of objects.
+ * @begin: begin pos for sort
+ * @end: end pos for sort
+ * @cmp: pointer to comparison function
+ * @swap: pointer to swap function
+ *
+ * This function does a heapsort on the given random-accessible
+ * objects container.
+ * Sort the region [begin, end) of the container.
+ *
+ * sort() is recommended for sorting objects on continuous memory
+ * for performance(sort an array, etc).
+ *
+ * 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 obj_sort(void *container, size_t begin, size_t end,
+		int (*cmp)(const void *container, size_t left, size_t right),
+		void (*swap)(void *container, size_t left, size_t right))
+{
+	ssize_t i, c, r, n = end - begin;
+
+	/* heapify */
+	for (i = n/2 - 1; i >= 0; i--) {
+		for (r = i; r * 2 + 1 < n; r = c) {
+			c = r * 2 + 1;
+			if (c < n - 1 && cmp(container, begin + c,
+					begin + c + 1) < 0)
+				c++;
+			if (cmp(container, begin + r, begin + c) >= 0)
+				break;
+			swap(container, begin + r, begin + c);
+		}
+	}
+
+	/* sort */
+	for (i = n - 1; i > 0; i--) {
+		swap(container, begin, begin + i);
+		for (r = 0; r * 2 + 1 < i; r = c) {
+			c = r * 2 + 1;
+			if (c < i - 1 && cmp(container, begin + c,
+					begin + c + 1) < 0)
+				c++;
+			if (cmp(container, begin + r, begin + c) >= 0)
+				break;
+			swap(container, begin + r, begin + c);
+		}
+	}
+}
+
+EXPORT_SYMBOL(obj_sort);
+
 #if 0
 /* a simple boot-time regression test */
 


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/