/* b01902062 藍ĉŒşç‘‹ */ #ifdef HAVE_CONFIG_H # include "config.h" #endif #include "xwrap.h" #include #include #include #include #include #include #include #include #define SORT_DATA(x) ((SortData*)(x)) typedef struct { int_least32_t* s; int start; int len; } SortData; #define MERGE_DATA(x) ((MergeData*)(x)) typedef struct { int_least32_t* s; int start; int mid; int end; } MergeData; static int_least32_t read_32b_integer (FILE* fp) { int_least32_t n; switch (fscanf (fp, "%" SCNdLEAST32, &n)) { case 0: fputs ("Invalid input!\n", stderr); exit (3); case EOF: fputs ("Why EOF?\n", stderr); exit (4); } return n; } static int qsort_cmp_cb (const void* a, const void* b) { int_least32_t aa = *(int_least32_t*)a; int_least32_t bb = *(int_least32_t*)b; if (aa > bb) { return 1; } else if (aa == bb) { return 0; } else { return -1; } } static FILE* msg_dev; static void* task_sort (void* sd_generic) { SortData* sd = SORT_DATA (sd_generic); qsort (sd->s + sd->start, sd->len, sizeof (int_least32_t), qsort_cmp_cb); fprintf (msg_dev, "Sorted %d elements.\n", sd->len); return NULL; } 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_least32_t dup_num = s[i]; int dup_count = 0; bool is_dup = false; 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_num != s[i]) { dup_count++; } dup_num = s[i]; 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[]) { if (argc < 2) { fprintf (stderr, "Usage: %s segment_size\n", argv[0]); return 1; } char* merger_stderr = getenv ("MERGE_STDERR"); if (merger_stderr == NULL || *merger_stderr == '\0') { msg_dev = stdout; } else { msg_dev = stderr; } long ss; if (xatol (argv[1], &ss) < 0) { fprintf (stderr, "%s: %s is not an integer\n", argv[0], argv[1]); return 2; } if (ss <= 0) { fprintf (stderr, "%s: %ld is not a valid segment size\n", argv[0], ss); return 2; } int_least32_t n = read_32b_integer (stdin); int_least32_t* s = xmalloc (sizeof (int_least32_t) * n); for (int i = 0; i < n; i++) { s[i] = read_32b_integer (stdin); } int t = n / ss; int r; if (t * ss != n) { t++; } pthread_t* tid = xmalloc (sizeof (pthread_t) * t); /* Sort */ SortData* sd_list = xmalloc (sizeof (SortData) * t); for (int i = 0, st = 0; i < t; i++, st += ss) { sd_list[i] = (SortData) { .s = s, .start = st, .len = (st + ss >= n) ? (n - st) : ss }; r = pthread_create (&tid[i], NULL, task_sort, &sd_list[i]); if (r != 0) { perror ("sort: pthread_create"); exit (5); } } for (int i = 0; i < t; i++) { pthread_join (tid[i], NULL); } free (sd_list); /* 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++) { if (i) { putchar (' '); } printf ("%" PRIdLEAST32, s[i]); } putchar ('\n'); free (s); free (tid); free (md_list); return 0; }