From 0fb339fd9dc30b997c76563271e9b3e3f24db84d Mon Sep 17 00:00:00 2001
From: David Monniaux <david.monniaux@univ-grenoble-alpes.fr>
Date: Sat, 19 Jan 2019 19:17:46 +0100
Subject: some more example

---
 test/monniaux/heapsort/Makefile       | 40 ++++++++++++++++++++++++
 test/monniaux/heapsort/heapsort.c     | 58 +++++++++++++++++++++++++++++++++++
 test/monniaux/heapsort/heapsort.h     |  7 +++++
 test/monniaux/heapsort/heapsort_run.c | 22 +++++++++++++
 4 files changed, 127 insertions(+)
 create mode 100644 test/monniaux/heapsort/Makefile
 create mode 100644 test/monniaux/heapsort/heapsort.c
 create mode 100644 test/monniaux/heapsort/heapsort.h
 create mode 100644 test/monniaux/heapsort/heapsort_run.c

(limited to 'test/monniaux/heapsort')

diff --git a/test/monniaux/heapsort/Makefile b/test/monniaux/heapsort/Makefile
new file mode 100644
index 00000000..47dac2bb
--- /dev/null
+++ b/test/monniaux/heapsort/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=heapsort.host heapsort.gcc.k1c.out heapsort.ccomp.k1c.out heapsort.ccomp.k1c.s heapsort.gcc.k1c.s heapsort.gcc.k1c heapsort.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 $@
+
+heapsort.host: heapsort.c heapsort_run.c heapsort.h
+	$(CC) $(CFLAGS) heapsort.c heapsort_run.c -o $@
+
+heapsort.gcc.k1c.s heapsort.ccomp.k1c.s heapsort_run.gcc.k1c.s: heapsort.h
+
+heapsort.gcc.k1c: heapsort.gcc.k1c.o heapsort_run.gcc.k1c.o
+	$(K1C_CC) $(K1C_CFLAGS) $+ -o $@
+
+heapsort.ccomp.k1c: heapsort.ccomp.k1c.o heapsort_run.gcc.k1c.o
+	$(K1C_CCOMP) $(K1C_CCOMPFLAGS) $+ -o $@
+
+%.k1c.out: %.k1c
+	k1-cluster --cycle-based -- $< | tee $@
+
+clean:
+	$(RM) -f $(PRODUCTS) heapsort.gcc.k1c.o heapsort.ccomp.k1c.o heapsort_run.gcc.k1c.o heapsort_run.gcc.k1c.s
+
+.PHONY: clean
diff --git a/test/monniaux/heapsort/heapsort.c b/test/monniaux/heapsort/heapsort.c
new file mode 100644
index 00000000..550eff4d
--- /dev/null
+++ b/test/monniaux/heapsort/heapsort.c
@@ -0,0 +1,58 @@
+#include "heapsort.h"
+
+/* Rosetta Code */
+static inline int max (data *a, int n, int i, int j, int k) {
+    int m = i;
+    if (j < n && a[j] > a[m]) {
+        m = j;
+    }
+    if (k < n && a[k] > a[m]) {
+        m = k;
+    }
+    return m;
+}
+ 
+static void downheap (data *a, int n, int i) {
+    while (1) {
+        int j = max(a, n, i, 2 * i + 1, 2 * i + 2);
+        if (j == i) {
+            break;
+        }
+        data t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+        i = j;
+    }
+}
+ 
+void heapsort (data *a, int n) {
+    int i;
+    for (i = (n - 2) / 2; i >= 0; i--) {
+        downheap(a, n, i);
+    }
+    for (i = 0; i < n; i++) {
+        data t = a[n - i - 1];
+        a[n - i - 1] = a[0];
+        a[0] = t;
+        downheap(a, n - i - 1, 0);
+    }
+}
+
+data data_random(void) {
+  static uint64_t next = 1325997111;
+  next = next * 1103515249 + 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/heapsort/heapsort.h b/test/monniaux/heapsort/heapsort.h
new file mode 100644
index 00000000..247d6773
--- /dev/null
+++ b/test/monniaux/heapsort/heapsort.h
@@ -0,0 +1,7 @@
+#include <stdint.h>
+#include <stdbool.h>
+
+typedef uint64_t data;
+void heapsort(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/heapsort/heapsort_run.c b/test/monniaux/heapsort/heapsort_run.c
new file mode 100644
index 00000000..76378067
--- /dev/null
+++ b/test/monniaux/heapsort/heapsort_run.c
@@ -0,0 +1,22 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include "heapsort.h"
+#include "../cycles.h"
+
+int main (void) {
+  cycle_count_config();
+  unsigned len=30000;
+  data *vec = malloc(sizeof(data) * len);
+  data_vec_random(vec, len);
+  cycle_t heapsort_time = get_cycle();
+  heapsort(vec, len);
+  heapsort_time = get_cycle() - heapsort_time;
+  printf("sorted=%s\n"
+	 "heapsort_time=%" PRIu64 "\n",
+	 data_vec_is_sorted(vec, len)?"true":"false",
+	 heapsort_time);
+  free(vec);
+  return 0;
+}
+ 
-- 
cgit