From a66d2cc6e0910f96e2b84f182e9e54168d0b2f14 Mon Sep 17 00:00:00 2001
From: David Kaufmann <astra@fsinf.at>
Date: Tue, 25 Oct 2011 18:31:15 +0200
Subject: [PATCH] add openmp from isi

---
 openmp/merge/Makefile |  20 +++++++
 openmp/merge/sort.c   | 119 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 139 insertions(+)
 create mode 100644 openmp/merge/Makefile
 create mode 100644 openmp/merge/sort.c

diff --git a/openmp/merge/Makefile b/openmp/merge/Makefile
new file mode 100644
index 0000000..f8efee4
--- /dev/null
+++ b/openmp/merge/Makefile
@@ -0,0 +1,20 @@
+# GCC Makefile
+
+CC      = gcc
+CFLAGS  = -pedantic -Wall -g -fopenmp
+LDFLAGS = -fopenmp
+
+BINARIES = sort
+OBJECTS  = $(BINARIES).o
+
+all: sort
+
+sort: sort.o
+	$(CC) -o $@ $< $(LDFLAGS)
+
+%.o: %.c
+	$(CC) $(CFLAGS) -c $<
+
+.PHONY: clean
+clean:
+	rm -rf $(OBJECTS) $(BINARIES)
diff --git a/openmp/merge/sort.c b/openmp/merge/sort.c
new file mode 100644
index 0000000..13957f3
--- /dev/null
+++ b/openmp/merge/sort.c
@@ -0,0 +1,119 @@
+/* implementation of parallel merge sort */
+#include <stdio.h>
+#include <omp.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#define LISTSIZE 10
+#define THREADS 2
+
+void printlist(char * message, int * ptr) {
+	printf (message);
+	while (*ptr != -1) {
+		printf (" %i", *ptr);
+		ptr++;
+	}
+	printf ("\n");
+}
+
+int rank(int elem, int * list) {
+	int pos;
+	
+	pos = 0;
+	if (elem == -1) { return -1; }
+	while (*list >= 0) {
+		/*printf ("elem_list: %i %i\n", elem, *list);*/
+		if (elem <= *list) {
+			return pos;
+		}
+		list++;
+		pos++;
+	}
+	return -1;
+}
+
+/* merge(a,n,b,m,c): merges a of size n and b of size m into c */
+void merge(int ti, int * a, int n, int * b, int m, int * c) {
+	int sum;
+	int i;
+	sleep (1);
+	/*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/
+	if (m<0) { m=0;}
+	if (n<0) { n=0;}
+	sum = n + m;
+	//printf ("%i modifying %i (%i+%i) (c[%i]/0x%08x -> c[%i]/0x%08x)\n", ti, sum, n, m, 0, (unsigned int) &c, sum-1, ((unsigned int) &c)+sum);
+	i = 0;
+	while (i < sum) {
+		if (*a < 0 && *b < 0) {
+			printf ("%i Calculation failed somehow...\n", ti);
+			return;
+		}
+		if (*a < 0) {
+			c[i] = *b; m--;
+			b++;
+		} else {
+			if (*b < 0) {
+				c[i] = *a; n--;
+				a++;
+			} else {
+				if (*a < *b) {
+					c[i] = *a; n--;
+					a++;
+				} else {
+					c[i] = *b; m--;
+					b++;
+				}
+			}
+		}
+		i++;
+	}
+	return;
+}
+
+int main ( int argc, char ** argv) {
+	int n = LISTSIZE;
+	int p = THREADS;
+	int i;
+	int a_len, b_len, b_len_end, b_len_begin;
+	int a[] = {0,3,4,14,61,62,70,72,74,99,-1};
+	int b[] = {1,2,7,34,35,68,77,78,79,84,-1};
+	int * c;
+
+	printf ("----------------------------------\n");
+
+	c = (int *) malloc((LISTSIZE * 2 + 1) * (sizeof (int)));
+	c[LISTSIZE*2] = -1;
+
+	printlist("0 Sorted List A:", a);
+	printlist("0 Sorted List B:", b);
+
+	a_len = n/p;
+#pragma omp parallel for shared(a,b,c,n,p,a_len) private(i,b_len_begin,b_len_end,b_len)
+	for (i = 0; i < p; i++) {
+		b_len_begin = rank(a[i*a_len], b);
+		b_len_end = rank(a[(i+1)*a_len], b);
+		if (b_len_begin < 0) {
+			printf ("Insert to end of list!\n");
+			b_len_begin = n;
+		}
+		if (b_len_end < 0) {
+			printf ("Reached end of list!\n");
+			b_len_end = n;
+		}
+		b_len = b_len_end - b_len_begin;
+		printf ("%i a_len: %i, b_len: %i (begin:%i ([%i]) -> end:%i [%i])\n", i+1, a_len, b_len, b_len_begin, b[b_len_begin], b_len_end, b[b_len_end]);
+		if (b_len == 0) {
+			continue;
+		}
+		merge(	i+1,
+				&a[i*a_len],
+				a_len,
+				&b[b_len_begin],
+				b_len,
+				&c[i*a_len+b_len_begin]);
+	}
+
+	printlist("Sorted List:", c);
+	free(c);
+	return 0;
+}
-- 
2.43.0