diff options
Diffstat (limited to 'hw3/merger.c')
| -rw-r--r-- | hw3/merger.c | 82 |
1 files changed, 76 insertions, 6 deletions
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++) { |