MPPA - tests - added insertion sort and selection sort

5 files changed, 159 insertions, 0 deletions

diff --git a/test/mppa/sort/Makefile b/test/mppa/sort/Makefile
new file mode 100644
index 00000000..1f4a0d51
--- /dev/null
+++ b/test/mppa/sort/Makefile
@@ -0,0 +1,40 @@
+PRNG=../lib/prng.c
+
+insertion-test-x86: insertion.c $(PRNG)
+	gcc -g -D__UNIT_TEST_INSERTION__ -O2 -std=c99 $^ -o $@
+
+insertion-test-k1c: insertion.c $(PRNG)
+	k1-gcc -D__UNIT_TEST_INSERTION__ -O2 -std=c99 $^ -o $@
+
+selection-test-x86: selection.c $(PRNG)
+	gcc -g -D__UNIT_TEST_SELECTION__ -O2 -std=c99 $^ -o $@
+
+selection-test-k1c: selection.c $(PRNG)
+	k1-gcc -D__UNIT_TEST_SELECTION__ -O2 -std=c99 $^ -o $@
+
+.PHONY:
+unittest: unittest-x86 unittest-k1c
+
+.PHONY:
+unittest-x86: insertion-test-x86 selection-test-x86
+	@for test in $^; do\
+		if ! ./$$test; then\
+			>&2 echo "ERROR: $$test failed";\
+		else\
+			echo "x86: Test $$test Succeeded";\
+		fi;\
+	done
+
+.PHONY:
+unittest-k1c: insertion-test-k1c selection-test-k1c
+	@for test in $^; do\
+		if ! k1-cluster -- ./$$test; then\
+			>&2 echo "ERROR: $$test failed";\
+		else\
+			echo "k1c: Test $$test Succeeded";\
+		fi;\
+	done
+
+.PHONY:
+clean:
+	rm -f insertion-test-x86 insertion-test-k1c selection-test-k1c selection-test-x86
diff --git a/test/mppa/sort/insertion.c b/test/mppa/sort/insertion.c
new file mode 100644
index 00000000..2c6065e7
--- /dev/null
+++ b/test/mppa/sort/insertion.c
@@ -0,0 +1,52 @@
+#include "../lib/prng.h"
+#include "../lib/types.h"
+
+void swap(uint64_t *a, uint64_t *b){
+    uint64_t tmp = *a;
+    *a = *b;
+    *b = tmp;
+}
+
+int insert_sort(uint64_t *res, const uint64_t *T, int size){
+    if (size <= 0)
+        return -1;
+
+    for (int i = 0 ; i < size ; i++)
+        res[i] = T[i];
+
+    for (int i = 0 ; i < size-1 ; i++){
+        if (res[i] > res[i+1]){
+            swap(&res[i], &res[i+1]);
+            for (int j = i ; j > 1 ; j--)
+                if (res[j-1] > res[j])
+                    swap(&res[j-1], &res[j]);
+        }
+    }
+
+    return 0;
+}
+
+#ifdef __UNIT_TEST_INSERTION__
+#define SIZE 100
+
+int main(void){
+    uint64_t T[SIZE];
+    uint64_t res[SIZE];
+    srand(42);
+
+    for (int i = 0 ; i < SIZE ; i++)
+        T[i] = randlong();
+
+    /* Sorting the table */
+    if (insert_sort(res, T, SIZE) < 0) return -1;
+
+    /* Computing max(T) */
+    uint64_t max = T[0];
+    for (int i = 1 ; i < SIZE ; i++)
+        if (T[i] > max)
+            max = T[i];
+
+    /* We should have: max(T) == res[SIZE] */
+    return !(max == res[SIZE-1]);
+}
+#endif // __UNIT_TEST_INSERTION__
diff --git a/test/mppa/sort/insertion.h b/test/mppa/sort/insertion.h
new file mode 100644
index 00000000..135b3bc1
--- /dev/null
+++ b/test/mppa/sort/insertion.h
@@ -0,0 +1,6 @@
+#ifndef __INSERTION_H__
+#define __INSERTION_H__
+
+int insert_sort(uint64_t *res, const uint64_t *T, int size);
+
+#endif // __INSERTION_H__
diff --git a/test/mppa/sort/selection.c b/test/mppa/sort/selection.c
new file mode 100644
index 00000000..432bbf49
--- /dev/null
+++ b/test/mppa/sort/selection.c
@@ -0,0 +1,55 @@
+#include "../lib/prng.h"
+#include "../lib/types.h"
+
+void swap(uint64_t *a, uint64_t *b){
+    uint64_t tmp = *a;
+    *a = *b;
+    *b = tmp;
+}
+
+int selection_sort(uint64_t *res, const uint64_t *T, int size){
+    if (size <= 0)
+        return -1;
+
+    for (int i = 0 ; i < size ; i++)
+        res[i] = T[i];
+
+    for (int j = 0 ; j < size ; j++){
+        int i;
+        int iMin = j;
+        for (i = j+1 ; i < size ; i++)
+            if (res[i] < res[iMin])
+                iMin = i;
+
+        if (iMin != j)
+            swap (&res[j], &res[iMin]);
+    }
+
+    return 0;
+}
+
+#ifdef __UNIT_TEST_SELECTION__
+#define SIZE 100
+
+int main(void){
+    uint64_t T[SIZE];
+    uint64_t res[SIZE];
+    srand(42);
+
+    for (int i = 0 ; i < SIZE ; i++)
+        T[i] = randlong();
+
+    /* Sorting the table */
+    if (selection_sort(res, T, SIZE) < 0) return -1;
+
+    /* Computing max(T) */
+    uint64_t max = T[0];
+    for (int i = 1 ; i < SIZE ; i++)
+        if (T[i] > max)
+            max = T[i];
+
+    /* We should have: max(T) == res[SIZE] */
+    return !(max == res[SIZE-1]);
+}
+#endif // __UNIT_TEST_SELECTION__
+
diff --git a/test/mppa/sort/selection.h b/test/mppa/sort/selection.h
new file mode 100644
index 00000000..b2b4aebe
--- /dev/null
+++ b/test/mppa/sort/selection.h
@@ -0,0 +1,6 @@
+#ifndef __SELECTION_H__
+#define __SELECTION_H__
+
+int selection_sort(uint64_t *res, const uint64_t *T, int size);
+
+#endif // __SELECTION_H__