HW3: merge 大致完成，尚未完整測試

4 files changed, 77 insertions, 18 deletions

diff --git a/hw3/configure.ac b/hw3/configure.ac
index ad614bd..97e80a8 100644
--- a/hw3/configure.ac
+++ b/hw3/configure.ac
@@ -14,6 +14,7 @@ AC_PROG_CC_C99
 AC_PROG_RANLIB
 
 # Checks for typedefs, structures, and compiler characteristics.
+AC_CHECK_HEADER_STDBOOL
 AC_TYPE_SIZE_T
 
 # Checks for library functions.
diff --git a/hw3/merger.c b/hw3/merger.c
index 32ddc9e..18f383e 100644
--- a/hw3/merger.c
+++ b/hw3/merger.c
@@ -7,9 +7,11 @@
 
 #include <inttypes.h>
 #include <pthread.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdint.h>
 #include <stdlib.h>
+#include <string.h>
 #include <unistd.h>
 
 #define  SORT_DATA(x)     ((SortData*)(x))
@@ -22,10 +24,9 @@ typedef struct {
 #define  MERGE_DATA(x)    ((MergeData*)(x))
 typedef struct {
 	int_least32_t* s;
-	int start1;
-	int len1;
-	int start2;
-	int len2;
+	int start;
+	int mid;
+	int end;
 } MergeData;
 
 static int_least32_t read_32b_integer (FILE* fp) {
@@ -62,7 +63,54 @@ static void* task_sort (void* sd_generic) {
 	return NULL;
 }
 
-static void* task_merge (void* sd_generic) {
+static void* task_merge (void* md_generic) {
+	MergeData* md = MERGE_DATA (md_generic);
+	int_least32_t* t = xmalloc (sizeof (int_least32_t) * (md->end - md->start));
+	int_least32_t* s = md->s;
+
+	int i = md->start, iend = md->mid;
+	int j = md->mid,   jend = md->end;
+	int k = 0;
+
+	int dup_count = 0;
+	bool is_dup;
+
+	while (i < iend && j < jend) {
+		if (s[i] > s[j]) {
+			t[k] = s[j];
+			j++, k++;
+			is_dup = false;
+		} else if (s[i] < s[j]) {
+			t[k] = s[i];
+			i++, k++;
+			is_dup = false;
+		} else {
+			if (!is_dup) {
+				dup_count++;
+			}
+			t[k] = s[i];
+			i++, k++;
+			t[k] = s[j];
+			j++, k++;
+			is_dup = true;
+		}
+	}
+
+	while (i < iend) {
+		t[k] = s[i];
+		i++, k++;
+	}
+	while (j < jend) {
+		t[k] = s[j];
+		j++, k++;
+	}
+
+	memcpy (s + md->start, t, sizeof (int_least32_t) * (md->end - md->start));
+	fprintf (msg_dev, "Merged %d and %d elements with %d duplicates.\n",
+		md->mid - md->start, md->end - md->mid, dup_count);
+
+	free (t);
+	return NULL;
 }
 
 int main (int argc, char* argv[]) {
@@ -123,7 +171,29 @@ int main (int argc, char* argv[]) {
 
 	/* Merge */
 	MergeData* md_list = xmalloc (sizeof (MergeData) * t);
-
+	for (long mss = ss; mss < n; mss *= 2) {
+		t = n / mss;
+		if (t * mss != n) {
+			t++;
+		}
+		t /= 2;
+		for (int i = 0, st = 0; i < t; i++, st += mss * 2) {
+			md_list[i] = (MergeData) {
+				.s = s,
+				.start = st,
+				.mid = st + mss,
+				.end = (st + mss * 2 > n) ? n : (st + mss * 2)
+			};
+			r = pthread_create (&tid[i], NULL, task_merge, &md_list[i]);
+			if (r != 0) {
+				perror ("merge: pthread_create");
+				exit (5);
+			}
+		}
+		for (int i = 0; i < t; i++) {
+			pthread_join (tid[i], NULL);
+		}
+	}
 
 	/* Output */
 	for (int i = 0; i < n; i++) {
diff --git a/hw3/xwrap.c b/hw3/xwrap.c
index bff218e..7a8a5b6 100644
--- a/hw3/xwrap.c
+++ b/hw3/xwrap.c
@@ -46,14 +46,3 @@ void* xmalloc (size_t size) {
 
 	return memptr;
 }
-
-void* xrealloc (void* ptr, size_t size) {
-	void* newptr;
-
-	while ((newptr = realloc (ptr, size)) == NULL) {
-		nanosleep (&(struct timespec) { RETRY_SEC, RETRY_NSEC }, NULL);
-		write (STDERR_FILENO, fail_msg, fail_len);
-	}
-
-	return newptr;
-}
diff --git a/hw3/xwrap.h b/hw3/xwrap.h
index 7c64cf7..f02867f 100644
--- a/hw3/xwrap.h
+++ b/hw3/xwrap.h
@@ -8,6 +8,5 @@
 
 int     xatol (const char* str, long* result);
 void*   xmalloc (size_t size);
-void*   xrealloc (void* ptr, size_t size);
 
 #endif /* X_GENERAL_WRAPPER */