aboutsummaryrefslogtreecommitdiffstats
path: root/com32/elflink/modules/sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'com32/elflink/modules/sort.c')
-rw-r--r--com32/elflink/modules/sort.c75
1 files changed, 75 insertions, 0 deletions
diff --git a/com32/elflink/modules/sort.c b/com32/elflink/modules/sort.c
new file mode 100644
index 00000000..bec0ef2a
--- /dev/null
+++ b/com32/elflink/modules/sort.c
@@ -0,0 +1,75 @@
+/*
+ * sort.c - Sample ELF module providing a quick sort function
+ *
+ * Created on: Aug 11, 2008
+ * Author: Stefan Bucur <stefanb@zytor.com>
+ */
+
+#include <stdlib.h>
+#include <sys/module.h>
+
+/**
+ * sort_init - Module entry point.
+ */
+static int sort_init() {
+ return 0; // Nothing to do; return success
+}
+
+
+static inline void swap(int *x, int *y) {
+ int tmp;
+ tmp = *x;
+ *x = *y;
+ *y = tmp;
+}
+
+static inline int randint(int l, int u) {
+ return l + (rand() % (u-l+1));
+}
+
+/**
+ * quick_sort_range - A small and efficient version of quicksort.
+ * @nums: The numbers to sort
+ * @l: The lower index in the vector (inclusive)
+ * @u: The upper index in the vector (inclusive)
+ *
+ * The implementation is taken from "Beautiful Code", by O'Reilly, the
+ * book students received from Google as a gift for their acceptance
+ * in the GSoC 2008 program. The code belongs to Jon Bentley, who
+ * wrote the third chapter of the book. Since ELF modules were written
+ * as part of this program, the author of the module considered
+ * the book had to be put at some use. :)
+ */
+static void quick_sort_range(int *nums, int l, int u) {
+ int i, m;
+ if (l >= u) return;
+
+ swap(&nums[l], &nums[randint(l, u)]);
+
+ m = l;
+ for (i = l+1; i <= u; i++) {
+ if (nums[i] < nums[l])
+ swap(&nums[++m], &nums[i]);
+ }
+
+ swap(&nums[l], &nums[m]);
+
+ quick_sort_range(nums, l, m-1);
+ quick_sort_range(nums, m+1, u);
+}
+
+
+void quick_sort(int *nums, int count) {
+ quick_sort_range(nums, 0, count-1);
+}
+
+/**
+ * sort_exit - Module exit point.
+ */
+static void sort_exit() {
+ // Nothing to do
+}
+
+// Define entry and exit points.
+MODULE_INIT(sort_init);
+MODULE_EXIT(sort_exit);