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