fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include <pthread.h>
  6.  
  7.  
  8. struct Params
  9. {
  10.     int *start;
  11.     size_t len;
  12.     int depth;
  13. };
  14.  
  15. // only used for synchronizing stdout from overlap.
  16. pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
  17.  
  18. // forward declare our thread proc
  19. void *merge_sort_thread(void *pv);
  20.  
  21.  
  22. // a simple merge algorithm. there are *several* more efficient ways
  23. //  of doing this, but the purpose of this exercise is to establish
  24. //  merge-threading, so we stick with simple for now.
  25. void merge(int *start, int *mid, int *end)
  26. {
  27.     int *res = malloc((end - start)*sizeof(*res));
  28.     int *lhs = start, *rhs = mid, *dst = res;
  29.  
  30.     while (lhs != mid && rhs != end)
  31.         *dst++ = (*lhs < *rhs) ? *lhs++ : *rhs++;
  32.  
  33.     while (lhs != mid)
  34.         *dst++ = *lhs++;
  35.  
  36.     // copy results
  37.     memcpy(start, res, (rhs - start) * sizeof *res);
  38.     free(res);
  39. }
  40.  
  41. // our multi-threaded entry point.
  42. void merge_sort_mt(int *start, size_t len, int depth)
  43. {
  44.     if (len < 2)
  45.         return;
  46.  
  47.     if (depth <= 0 || len < 4)
  48.     {
  49.         merge_sort_mt(start, len/2, 0);
  50.         merge_sort_mt(start+len/2, len-len/2, 0);
  51.     }
  52.     else
  53.     {
  54.         struct Params params = { start, len/2, depth/2 };
  55.         pthread_t thrd;
  56.  
  57.         pthread_mutex_lock(&mtx);
  58.         printf("Starting subthread...\n");
  59.         pthread_mutex_unlock(&mtx);
  60.  
  61.         // create our thread
  62.         pthread_create(&thrd, NULL, merge_sort_thread, &params);
  63.  
  64.         // recurse into our top-end parition
  65.         merge_sort_mt(start+len/2, len-len/2, depth/2);
  66.  
  67.         // join on the launched thread
  68.         pthread_join(thrd, NULL);
  69.  
  70.         pthread_mutex_lock(&mtx);
  71.         printf("Finished subthread.\n");
  72.         pthread_mutex_unlock(&mtx);
  73.     }
  74.  
  75.     // merge the partitions.
  76.     merge(start, start+len/2, start+len);
  77. }
  78.  
  79. // our thread-proc that invokes merge_sort. this just passes the
  80. //  given parameters off to our merge_sort algorithm
  81. void *merge_sort_thread(void *pv)
  82. {
  83.     struct Params *params = pv;
  84.     merge_sort_mt(params->start, params->len, params->depth);
  85.     return pv;
  86. }
  87.  
  88. // public-facing api
  89. void merge_sort(int *start, size_t len)
  90. {
  91.     merge_sort_mt(start, len, 4); // 4 is a nice number, will use 7 threads.
  92. }
  93.  
  94. int main()
  95. {
  96.     static const unsigned int N = 15;
  97.     int *numbs = malloc(N * sizeof(*numbs));
  98.     unsigned int i;
  99.  
  100.     srand((unsigned)time(0));
  101.     for (i=0; i<N; ++i)
  102.     {
  103.         numbs[i] = rand() % 1024;
  104.         printf("%4d ", numbs[i]);
  105.         if ((i+1)%8 == 0)
  106.             printf("\n");
  107.     }
  108.     printf("\n");
  109.  
  110.     // invoke our multi-threaded merge-sort
  111.     merge_sort(numbs, N);
  112.     for (i=0; i<N; ++i)
  113.     {
  114.         printf("%4d ", numbs[i]);
  115.         if ((i+1)%8 == 0)
  116.             printf("\n");
  117.     }
  118.     printf("\n");
  119.  
  120.     free(numbs);
  121.  
  122.     return 0;
  123.  
  124. }
Success #stdin #stdout 0s 4448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 368  612  901  795   88  698  821  964 
 264  341  177  632  218  656  344 
Starting subthread...
Starting subthread...
Starting subthread...
Finished subthread.
Starting subthread...
Starting subthread...
Starting subthread...
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
Finished subthread.
  88  177  218  264  341  344  368  612 
 632  656  698  795  821  901  964
https://ideone.com/O3rzzW
language:
C (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!