aboutsummaryrefslogtreecommitdiffstats
path: root/com32/elflink/modules/sort.c
diff options
context:
space:
mode:
authorStefan Bucur <stefanb@zytor.com>2008-08-11 19:22:29 +0300
committerStefan Bucur <stefan@stefan-ubumac.(none)>2009-03-15 10:10:50 +0200
commit9195aa5d71b5593742fcae9957e2e9328717fb12 (patch)
tree92743c40530ba52d78b81040eee1bb1110a38180 /com32/elflink/modules/sort.c
parentfac2992f2848ce2a630ba03f3a9f43d5928297ae (diff)
downloadsyslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.tar.gz
syslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.tar.xz
syslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.zip
Created a simple quick sort module.
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..a6f854d9
--- /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 = 1;
+ 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);