path: root/com32/libutil/quicksort.c
diff options
authorMatt Fleming <matt.fleming@linux.intel.com>2011-04-26 09:59:53 +0100
committerMatt Fleming <matt.fleming@linux.intel.com>2011-04-26 10:04:59 +0100
commit74518b8b691c8aba1425673864c45b7721d9a738 (patch)
tree2b0d26c3617cabfd1c5e60bc046fd872014def4a /com32/libutil/quicksort.c
parent8f10ba6d251ac05b54f183cb98bf5310a0675338 (diff)
elflink: Make ELF the default object format
com32/elflink/modules was originally created to house ELF modules and keep them separate from the COM32 modules as the elflink branch was being developed. However, this has inadvertently created a maintenance nightmare because code was copied from elsewhere in the tree into com32/elflink/modules, resulting in duplication. Bug fixes have been going into the original code but have not been merged onto the elflink branch, leaving the duplicate code in com32/elflink/modules buggy. So let's delete this directory. There really is no reason to keep ELF and COM32 modules separate because there's no reason to need both COM32 and ELF modules to coexist. ELF is a far superior object file format and all modules are not emitted as ELF objects. Now that we're outputting ELF modules we can use dynamic memory instead of the cs_bounce bounce buffer. This commit requires a certain amount of shuffling for some files. quicksort.c isn't a module and belongs as part of the util library. cli.h belongs in com32/include so that other modules can make use of the cli code in ldlinux.c32. All libraries are now ELF shared libraries which are only loaded to fixup unresolved symbols for executable modules and renamed from *.a to *.c32. This reduces the runtime memory footprint because libraries are only loaded when needed and because every executable no longer gets its own copy of code/data (as it would if linking with a static library). Also, remove MINLIBOBJS from libcom32.c32 because it is already part of libcom32min.a and we don't want to have any duplicate symbols between the core (which links with libcom32min.a) and libcom32.c32. Welcome to the New World Order of ELF modules! Signed-off-by: Matt Fleming <matt.fleming@linux.intel.com>
Diffstat (limited to 'com32/libutil/quicksort.c')
1 files changed, 59 insertions, 0 deletions
diff --git a/com32/libutil/quicksort.c b/com32/libutil/quicksort.c
new file mode 100644
index 00000000..32ac0f01
--- /dev/null
+++ b/com32/libutil/quicksort.c
@@ -0,0 +1,59 @@
+ * sort.c - Sample ELF module providing a quick sort function
+ *
+ * Created on: Aug 11, 2008
+ * Author: Stefan Bucur <stefanb@zytor.com>
+ */
+#include <stdlib.h>
+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 to 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);