From d1408c9541da0cb1f5428576cb63dd84e8afb22e Mon Sep 17 00:00:00 2001
From: David Kaufmann <astra@ionic.at>
Date: Wed, 25 Jan 2012 03:27:08 +0100
Subject: [PATCH] hillis: implemented partial prefix sums algorithm

---
 openmp/prefix/hillis.c | 43 +++++++++++++++++++++++++++++++++++-------
 openmp/prefix/hillis.h |  2 ++
 2 files changed, 38 insertions(+), 7 deletions(-)

diff --git a/openmp/prefix/hillis.c b/openmp/prefix/hillis.c
index 153ba43..525eecb 100644
--- a/openmp/prefix/hillis.c
+++ b/openmp/prefix/hillis.c
@@ -3,6 +3,10 @@
  */
 #include "hillis.h"
 
+/*
+ * Hillis/Steele, prefix sum version
+ */
+/*
 void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
 	numtype tmp[size];
 	unsigned long k;
@@ -11,15 +15,40 @@ void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
 	for(k=2; k <= size; k <<=1){
 		#pragma omp parallel for shared(x, size, ops, k) private(i)
 		for(i = (k-1); i < size; i+=k){
-			//printf ("x[%2li] = x[%2li] + x[%2li]; // {i:%li, k:%li}\n", i, i-k, i, i, k);
+#ifdef DEBUG
+			printf ("x[%2li] = x[%2li] + x[%2li]; // {i:%li, k:%li}\n", i, i-k, i, i, k);
+#endif
 			x[i] = x[i-(k/2)] + x[i];
 		}
-		//arrayState(x, size);
-		//barrier;
 	}
+}
+*/
 
-	/* Copy out array to in */
-//	for (i = 0; i < size; i++){
-//		x[i] = tmp[i+1];
-//	}
+/*
+ * Hillis/Steele, partial prefix sum version
+ */
+void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
+	numtype *y;
+	unsigned long k;
+	unsigned long i;
+
+	y = malloc(size * sizeof(numtype));
+	y[0] = x[0];
+
+	for (k=1; k<size; k<<=1) {
+		for (i=k; i<size; i++) {
+#ifdef DEBUG
+			printf ("y[%li] = x[%li] + x[%li]; // %li + %li", i, i-k, i, x[i-k], x[i]);
+#endif
+			y[i] = x[i-k]+x[i];
+		}
+		memcpy (x, y, size * sizeof(numtype));
+	}
+
+	if (y != NULL) {
+		free(y);
+		y = NULL;
+	}else{
+		printf ("Has not been freed!!!\n");
+	}
 }
diff --git a/openmp/prefix/hillis.h b/openmp/prefix/hillis.h
index aa2257c..fd78349 100644
--- a/openmp/prefix/hillis.h
+++ b/openmp/prefix/hillis.h
@@ -2,5 +2,7 @@
  * O(nlog n) work algorithm (Hillis-Steele)
  */
 #include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
 #include "prefix.h"
 
-- 
2.43.0