SHARE
TWEET

thdsort

a guest Feb 28th, 2020 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*                                                                              
  2.   thdsort.c                                                                    
  3.   S. Edward Dolan                                                              
  4.   Wednesday, February 26 2020                                                  
  5. */                                                                              
  6.                                                                                
  7. #define _GNU_SOURCE             /* for qsort_r() */                            
  8.                                                                                
  9. #include <stdlib.h>                                                            
  10. #include <stdio.h>                                                              
  11. #include <string.h>                                                            
  12. #include <pthread.h>                                                            
  13. #include <stdarg.h>                                                            
  14.                                                                                
  15. #define MAX_THREADS 64                                                          
  16. #define MIN_ARRAY_SIZE 128                                                      
  17.                                                                                
  18. /* Larry Wall says... */                                                        
  19. void die(const char* format, ...) {                                            
  20.     va_list ap;                                                                
  21.     va_start(ap, format);                                                      
  22.     vprintf(format, ap);                                                        
  23.     va_end(ap);                                                                
  24.     exit(1);                                                                    
  25. }                                                                              
  26.                                                                                
  27. /*                                                                              
  28.   An array slice to be sorted. The members are the same parameters as qsort()  
  29.   except the merge index which is used by merge().                              
  30.                                                                                
  31.   NOTE: size and compar could be hard-coded in sort()                          
  32. */                                                                              
  33. typedef struct slice_t {                                                        
  34.     void* base;                 /* pointer to first element of the slice */    
  35.     size_t nmemb;               /* slice size */                                
  36.     size_t size;                /* element size in bytes */                    
  37.     int (*compar)(const void*, const void*, void*); /* comparison function */  
  38.     size_t i;                   /* merge index */                              
  39. } slice_t;                                                                      
  40.                                                                                
  41. /* sort comparison function */                                                  
  42. int intless(const void* x, const void* y, void* foo) {                          
  43.     (void)foo;                                                                  
  44.     return *(int const*)x - *(int const*)y;                                    
  45. }                                                                              
  46.                                                                                
  47. /* sort the array slice */                                                      
  48. void* sortThread(void* slice) {                                                
  49.     slice_t* s = (slice_t*)slice;                                              
  50.     /* man qsort_r to see what this arg is for -----v */                        
  51.     qsort_r(s->base, s->nmemb, s->size, s->compar, NULL);                      
  52.     return slice; // don't care about the result, could return NULL            
  53. }                                                                              
  54.                                                                                
  55. /*                                                                              
  56.   debug: For testing the correctness of a multi-threaded sort. See usage in    
  57.          sort() and merge();                                                    
  58. */                                                                              
  59. void writeArray(int* a, size_t arraySize, const char* fileName) {              
  60.     FILE* f = fopen(fileName, "wb");                                            
  61.     fwrite(a, sizeof(int), arraySize, f);                                      
  62.     fclose(f);                                                                  
  63. }
  64.  
  65. * debug: For viewing small arrays. */                                          
  66. void printArray(int* a, size_t n) {                                            
  67.     for (size_t i=0; i<n; ++i)                                                  
  68.         printf("%d\n", a[i]);                                                  
  69.     puts("");                                                                  
  70. }                                                                              
  71.                                                                                
  72. /*                                                                              
  73.   Merge the sorted slices in `a' into a new array.                              
  74.  */                                                                            
  75. void merge(int* a, slice_t* slices, int nslices, size_t arraySize) {            
  76.     int* out = malloc(sizeof(int) * arraySize);                                
  77.     if (!out) {                                                                
  78.         free(a);                                                                
  79.         die("failed to allocate merge array of size: %ld\n", arraySize);        
  80.     }                                                                          
  81.     size_t i = 0;                                                              
  82.     slice_t *winner = NULL;     /* slice with the smallest integer */          
  83.     while (1) {                                                                
  84.         winner = NULL;                                                          
  85.         for (int j=0; j<nslices; ++j) {                                        
  86.             if (!winner && slices[j].i < slices[j].nmemb)                      
  87.                 winner = &slices[j];                                            
  88.             else if (slices[j].i < slices[j].nmemb &&                          
  89.                      *((int*)slices[j].base + slices[j].i) <                    
  90.                      *((int*)winner->base + winner->i))                        
  91.                 winner = &slices[j]; /* swap */                                
  92.         }                                                                      
  93.         if (winner)                                                            
  94.             out[i++] = *((int*)winner->base + winner->i++);                    
  95.         else                                                                    
  96.             break;              /* all slices merged */                        
  97.     }                                                                          
  98.     /* writeArray(out, arraySize, "multi_threaded.bin"); */                    
  99.     /* printArray(out, arraySize); */                                          
  100.     free(out);                                                                  
  101. }                                                                              
  102.                                                                                
  103. /*                                                                              
  104.   Sort an array of random integers using nThreads.                              
  105.  */                                                                            
  106. void sort(int nThreads, size_t arraySize) {                                    
  107.     int* a = malloc(sizeof(int) * arraySize);                                  
  108.     if (!a)                                                                    
  109.         die("failed to allocate initial array of size: %ld\n", arraySize);      
  110.     for (size_t i=0; i<arraySize; ++i)                                          
  111.         a[i] = rand();          /* initialize with random integers */          
  112.     if (nThreads == 1) {                                                        
  113.         qsort_r(a, arraySize, sizeof(int), intless, NULL);                      
  114.         /* writeArray(a, arraySize, "single_threaded.bin"); */                  
  115.         /* printArray(a, arraySize); */                                        
  116.     }                                                                          
  117.     else {                                                                      
  118.         int i = 0;                                                              
  119.         slice_t slices[MAX_THREADS];                                            
  120.         memset(slices, 0, sizeof(slice_t) * MAX_THREADS);                      
  121.         size_t sliceSize = arraySize / nThreads; /* see @@@ below */            
  122.         for (; i<nThreads; ++i) {                                              
  123.             slices[i].base = a + sliceSize * i;                                
  124.             slices[i].nmemb = sliceSize;                                        
  125.             slices[i].size = sizeof(int);                                      
  126.             slices[i].compar = intless;                                        
  127.             /* memset above will zero i */                                      
  128.         }                                                                      
  129.         /* @@@ last slice gets the leftover from the integer division */
  130.         slices[i-1].nmemb += arraySize % nThreads;                              
  131.         pthread_t threads[MAX_THREADS];                                        
  132.         for (i=0; i<nThreads; ++i)                                              
  133.             if (pthread_create(&threads[i], NULL, sortThread, &slices[i])) {    
  134.                 free(a);                                                        
  135.                 die("failed to create thread: %d\n", i);                        
  136.             }                                                                  
  137.         for (i=0; i<nThreads; ++i)                                              
  138.             if (pthread_join(threads[i], NULL)) {                              
  139.                 free(a);                                                        
  140.                 die("failed to join thread: %d\n", i);                          
  141.             }                                                                  
  142.         merge(a, slices, nThreads, arraySize);                                  
  143.     }                                                                          
  144.     free(a);                                                                    
  145. }                                                                              
  146.                                                                                
  147. int main(int argc, char** argv) {                                              
  148.     if (argc != 3)                                                              
  149.         die("usage: thdsort THREAD_COUNT ARRAY_SIZE\n");                        
  150.     int nThreads = atoi(argv[1]);                                              
  151.     if (nThreads < 1 || nThreads > MAX_THREADS)                                
  152.         die("THREAD_COUNT must be 1 to %d\n", MAX_THREADS);                    
  153.     long arraySize = atol(argv[2]);                                            
  154.     if (arraySize < MIN_ARRAY_SIZE)                                            
  155.         die("ARRAY_SIZE must be >= %d\n", MIN_ARRAY_SIZE);                      
  156.     sort(nThreads, arraySize);                                                  
  157.     return 0;                                                                  
  158. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top