openmp/merge/sort.c

   1 /* implementation of parallel merge sort */
   2 #include <stdio.h>
   3 #include <omp.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include "numlist1.h"
   7 #include "numlist2.h"
   8
   9 #define LISTSIZE 10000000
  10
  11 void printlist(char * message, int * ptr) {
  12         printf (message);
  13         while (*ptr != -1) {
  14                 printf (" %i", *ptr);
  15                 ptr++;
  16         }
  17         printf ("\n");
  18 }
  19
  20 int rank(int elem, int * list) {
  21         int pos;
  22
  23         //usleep(2000);//2ms
  24         pos = 0;
  25         if (elem == -1) { return -1; }
  26         while (*list >= 0) {
  27                 /*printf ("elem_list: %i %i\n", elem, *list);*/
  28                 if (elem <= *list) {
  29                         return pos;
  30                 }
  31                 list++;
  32                 pos++;
  33         }
  34         return -1;
  35 }
  36
  37 /* merge(a,n,b,m,c): merges a of size n and b of size m into c */
  38 void merge(int ti, int * a, int n, int * b, int m, int * c) {
  39         int sum;
  40         int i;
  41 //      usleep (1000);//1ms
  42         /*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/
  43         if (m<0) { m=0;}
  44         if (n<0) { n=0;}
  45         sum = n + m;
  46         //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);
  47         for (i = 0; i < sum; i++) {
  48                 //usleep (1000);//1ms
  49                 // n+m == 0
  50                 if (*a < 0 && *b < 0) {
  51                         printf ("%i Calculation failed somehow...\n", ti);
  52                         return;
  53                 }
  54                 if (*a < 0) {
  55                         c[i] = *b; m--;
  56                         b++;
  57                 } else {
  58                         if (*b < 0) {
  59                                 c[i] = *a; n--;
  60                                 a++;
  61                         } else {
  62                                 if (*a < *b) {
  63                                         c[i] = *a; n--;
  64                                         a++;
  65                                 } else {
  66                                         c[i] = *b; m--;
  67                                         b++;
  68                                 }
  69                         }
  70                 }
  71         }
  72         return;
  73 }
  74
  75 int main ( int argc, char ** argv) {
  76         int n = LISTSIZE;
  77         int p = 1;
  78         int opt, i;
  79         int a_len, b_len, b_len_end, b_len_begin;
  80         int * c;
  81
  82         while ((opt = getopt(argc, argv, "t:")) != -1) {
  83                 switch (opt) {
  84                         case 't':
  85                                 p = atoi(optarg);
  86                                 break;
  87                         default: /* '?' */
  88                                 fprintf(stderr, "Usage: %s [-t threads]\n", argv[0]);
  89                                 exit(EXIT_FAILURE);
  90                 }
  91         }
  92
  93         //printf ("Maximal number of threads: %i\n", omp_get_max_threads());
  94         //printf ("----------------------------------\n");
  95
  96         c = (int *) malloc((LISTSIZE * 2 + 1) * (sizeof (int)));
  97         c[LISTSIZE*2] = -1;
  98
  99         //printlist("0 Sorted List A:", a);
 100         //printlist("0 Sorted List B:", b);
 101
 102         a_len = n/p;
 103         #pragma omp parallel for shared(a,b,c,n,p,a_len) private(i,b_len_begin,b_len_end,b_len)
 104         for (i = 0; i < p; i++) {
 105                 b_len_begin = rank(a[i*a_len], b);
 106                 b_len_end = rank(a[(i+1)*a_len], b);
 107                 if (b_len_begin < 0) {
 108                         printf ("Insert to end of list!\n");
 109                         b_len_begin = n;
 110                 }
 111                 if (b_len_end < 0) {
 112                         //printf ("Reached end of list!\n");
 113                         b_len_end = n;
 114                 }
 115                 b_len = b_len_end - b_len_begin;
 116                 //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]);
 117                 merge(  i+1,
 118                                 &a[i*a_len],
 119                                 a_len,
 120                                 &b[b_len_begin],
 121                                 b_len,
 122                                 &c[i*a_len+b_len_begin]);
 123         }
 124
 125         //printlist("Sorted List:", c);
 126         free(c);
 127         return 0;
 128 }
 129