Added heapsort utility function to the lib/ framework.
authorDavide Libenzi <dlibenzi@google.com>
Thu, 15 Oct 2015 22:23:09 +0000 (15:23 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Fri, 30 Oct 2015 20:02:29 +0000 (16:02 -0400)
Signed-off-by: Davide Libenzi <dlibenzi@google.com>
Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/sort.h [new file with mode: 0644]
kern/lib/Kbuild
kern/lib/sort.c [new file with mode: 0644]

diff --git a/kern/include/sort.h b/kern/include/sort.h
new file mode 100644 (file)
index 0000000..294807e
--- /dev/null
@@ -0,0 +1,11 @@
+/* Copyright (c) 2015 Google Inc
+ * Davide Libenzi <dlibenzi@google.com>
+ * See LICENSE for details.
+ */
+
+#pragma once
+
+#include <stdio.h>
+
+void sort(void *base, size_t count, size_t size,
+          int (*cmp)(const void *, const void *));
index 1cb408f..aa4a004 100644 (file)
@@ -1,2 +1,3 @@
+obj-y                                          += sort.o
 obj-y                                          += zlib_deflate/
 obj-y                                          += zlib_inflate/
diff --git a/kern/lib/sort.c b/kern/lib/sort.c
new file mode 100644 (file)
index 0000000..425ca68
--- /dev/null
@@ -0,0 +1,49 @@
+/* Copyright (c) 2015 Google Inc
+ * Davide Libenzi <dlibenzi@google.com>
+ * See LICENSE for details.
+ */
+
+#include <stdio.h>
+
+static void mem_swap(void *a, void *b, size_t size)
+{
+       for (; size > 0; size--, a++, b++) {
+               char tmp = *(char*) a;
+
+               *(char *) a = *(char *) b;
+               *(char *) b = tmp;
+       }
+}
+
+void sort(void *base, size_t count, size_t size,
+          int (*cmp)(const void *, const void *))
+{
+       ssize_t n = count * size, c;
+
+       /* Standard heapsort algorithm. First loop creates a heap, and the
+        * second one progressively pop the top of the heap, and does re-heap
+        * operations so that we maintain the heap properties.
+        */
+       for (ssize_t i = (count / 2 - 1) * size; i >= 0; i -= size) {
+               for (ssize_t 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;
+                       mem_swap(base + r, base + c, size);
+               }
+       }
+
+       for (ssize_t i = n - size; i > 0; i -= size) {
+               mem_swap(base, base + i, size);
+               for (ssize_t 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;
+                       mem_swap(base + r, base + c, size);
+               }
+       }
+}