quicksort

4 files changed, 111 insertions, 0 deletions

diff --git a/test/monniaux/quicksort/Makefile b/test/monniaux/quicksort/Makefile
new file mode 100644
index 00000000..1d8913dd
--- /dev/null
+++ b/test/monniaux/quicksort/Makefile
@@ -0,0 +1,40 @@
+CFLAGS=-Wall -O3
+K1C_CC=k1-mbr-gcc
+K1C_CFLAGS=-Wall -O3 -std=c99
+K1C_CCOMP=../../../ccomp
+K1C_CCOMPFLAGS=-Wall -O3 -D__thread= -D__int128=int
+
+PRODUCTS=quicksort.host quicksort.gcc.k1c.out quicksort.ccomp.k1c.out quicksort.ccomp.k1c.s quicksort.gcc.k1c.s quicksort.gcc.k1c quicksort.ccomp.k1c
+
+all:	$(PRODUCTS)
+
+%.gcc.k1c.s: %.c
+	$(K1C_CC) $(K1C_CFLAGS) -S $< -o $@
+
+%.gcc.k1c.o: %.gcc.k1c.s
+	$(K1C_CC) $(K1C_CFLAGS) -c $< -o $@
+
+%.ccomp.k1c.s: %.c
+	$(K1C_CCOMP) $(K1C_CCOMPFLAGS) -S $< -o $@
+
+%.ccomp.k1c.o: %.ccomp.k1c.s
+	$(K1C_CCOMP) $(K1C_CCOMPFLAGS) -c $< -o $@
+
+quicksort.host: quicksort.c quicksort_run.c quicksort.h
+	$(CC) $(CFLAGS) quicksort.c quicksort_run.c -o $@
+
+quicksort.gcc.k1c.s quicksort.ccomp.k1c.s quicksort_run.gcc.k1c.s: quicksort.h
+
+quicksort.gcc.k1c: quicksort.gcc.k1c.o quicksort_run.gcc.k1c.o
+	$(K1C_CC) $(K1C_CFLAGS) $+ -o $@
+
+quicksort.ccomp.k1c: quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o
+	$(K1C_CCOMP) $(K1C_CCOMPFLAGS) $+ -o $@
+
+%.k1c.out: %.k1c
+	k1-cluster --cycle-based -- $< | tee $@
+
+clean:
+	$(RM) -f $(PRODUCTS) quicksort.gcc.k1c.o quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o
+
+.PHONY: clean
diff --git a/test/monniaux/quicksort/quicksort.c b/test/monniaux/quicksort/quicksort.c
new file mode 100644
index 00000000..de04bf2d
--- /dev/null
+++ b/test/monniaux/quicksort/quicksort.c
@@ -0,0 +1,42 @@
+#include "quicksort.h"
+
+/* Rosetta Code */
+void quicksort(data *A, int len) {
+  if (len < 2) return;
+ 
+  data pivot = A[len / 2];
+ 
+  int i, j;
+  for (i = 0, j = len - 1; ; i++, j--) {
+    while (A[i] < pivot) i++;
+    while (A[j] > pivot) j--;
+ 
+    if (i >= j) break;
+ 
+    data temp = A[i];
+    A[i]     = A[j];
+    A[j]     = temp;
+  }
+ 
+  quicksort(A, i);
+  quicksort(A + i, len - i);
+}
+
+data data_random(void) {
+  static uint64_t next = 1325997111;
+  next = next * 1103515245 + 12345;
+  return next;
+}
+
+void data_vec_random(data *a, unsigned len) {
+  for(unsigned i=0; i<len; i++) {
+    a[i] = data_random();
+  }
+}
+
+bool data_vec_is_sorted(const data *a, unsigned len) {
+  for(unsigned i=0; i<len-1; i++) {
+    if (a[i] > a[i+1]) return false;
+  }
+  return true;
+}
diff --git a/test/monniaux/quicksort/quicksort.h b/test/monniaux/quicksort/quicksort.h
new file mode 100644
index 00000000..cc73e7c3
--- /dev/null
+++ b/test/monniaux/quicksort/quicksort.h
@@ -0,0 +1,7 @@
+#include <stdint.h>
+#include <stdbool.h>
+
+typedef uint64_t data;
+void quicksort(data *A, int len);
+void data_vec_random(data *a, unsigned len);
+bool data_vec_is_sorted(const data *a, unsigned len);
diff --git a/test/monniaux/quicksort/quicksort_run.c b/test/monniaux/quicksort/quicksort_run.c
new file mode 100644
index 00000000..c269cc48
--- /dev/null
+++ b/test/monniaux/quicksort/quicksort_run.c
@@ -0,0 +1,22 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include "quicksort.h"
+#include "../cycles.h"
+
+int main (void) {
+  cycle_count_config();
+  unsigned len=10000;
+  data *vec = malloc(sizeof(data) * len);
+  data_vec_random(vec, len);
+  cycle_t quicksort_time = get_cycle();
+  quicksort(vec, len);
+  quicksort_time = get_cycle() - quicksort_time;
+  printf("sorted=%s\n"
+	 "quicksort_time=%" PRIu64 "\n",
+	 data_vec_is_sorted(vec, len)?"true":"false",
+	 quicksort_time);
+  free(vec);
+  return 0;
+}
+