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

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

[Lai Jiangshan]

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@cn.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@selenic.com>
+ *
+ * Sep 12 2008  Lai Jiangshan <laijs@cn.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 */
 

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

[Matt Mackall]

On Fri, 2008-09-12 at 19:55 +0800, Lai Jiangshan wrote:
> 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.

Ok, if I understand this correctly, your new function basically changes:

cmp(void *a, void *b)            to cmp(void *obj, int a, int b)
swap(void *a, void *b, int size) to swap(void *obj, int a, int b)

Since neither function actually looks at the data directly, it seems we
could make a unified sort function with:

cmp(void *base, int a, int b)
swap(void *base, int a, int b, int size)

What is the underlying data structure you're sorting by the way? Years
ago, I wrote a very nice merge sort for linked lists that I never got
around to submitting. 

-- 
Mathematics is the supreme nostalgia of our time.