| 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
| ||
|
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/
Powered by blists - more mailing lists