fork download
copy 
  1. #ifndef RADIXSORT_H
  2. #define RADIXSORT_H
  3.  
  4. /*******************************************************************
  5. * Recommended compiler options:                                    *
  6. * -v -O3 -march=native -funroll-loops                              *
  7. * 250 million integers in the range [-2147483647,2147483647] 2.42s *
  8. * 100 million integers in the range [-2147483647,2147483647] 0.98s *
  9. *******************************************************************/
  10.  
  11. #include <stdlib.h>
  12. #include <string.h>
  13.  
  14. #include <unistd.h>
  15. #include <sys/wait.h>
  16. #include <sys/shm.h>
  17.  
  18. typedef unsigned int uint32_t;
  19.  
  20. /*******************************************************************
  21. * Flips all the bits if negative.                                  *
  22. * Flips only the sign bit if positive.                             *
  23. * Allows for both negative and positive values.                    *
  24. * Returns one of the two bytes of the integer.                     *
  25. *******************************************************************/
  26. static uint32_t position(int number, int pass) {
  27.     int mask;
  28. 	if (number <= 0) mask = 0x80000000;
  29. 	else mask = (number >> 31) | 0x80000000;
  30. 	uint32_t out = number ^ mask;
  31. 	return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff;
  32. }
  33. /*******************************************************************
  34. * Creates a histogram using shared memory and fork processes for   *
  35. * parallelism.  This creates a parallel conquer and divide         *
  36. * algorithm, which merges into one histogram to use later on in    *
  37. * the code.  Note: This will not work in windows, with unistd.h.   *
  38. *******************************************************************/
  39. static void histogram(int *array,int size,int pass,uint32_t *hist) {
  40.     int i, j;
  41.     for (i=0;i<8;i++) {
  42.         pid_t pid = fork();
  43.         if (pid < 0) _exit(0);
  44.         if (pid == 0) {
  45.             const int start = (i * size) >> 3;
  46.             const int stop  = i == 7 ? size : ((i + 1) * size) >> 3;
  47.             const int curr  = i << 16;
  48.             for (j=start;j<stop;++j)
  49.                 hist[curr + position(array[j], pass)]++;
  50.             _exit(0);
  51.         }
  52.     }
  53.     for (i=0;i<8;i++) wait(NULL);
  54.  
  55.     for (i=1;i<8;i++) {
  56.         const int pos = i << 16;
  57.         for (j=0;j<65536;j++)
  58.             hist[j] += hist[pos + j];
  59.     }
  60. 	for (i=1;i<65536;i++)
  61. 		hist[i] += hist[i-1];
  62. }
  63. /*******************************************************************
  64. * Counting sorts each of the 2 16-bit bytes of each integers.      *
  65. * This eliminates the need for buckets, for each pass.             *
  66. * Bytes used to eliminate the number of passes down from k (length *
  67. *   of the largest integer) down to 2 passes.                      *
  68. *******************************************************************/
  69. static void radixSort(int *array, int size) {
  70. 	int i;
  71.     const uint32_t arrSize = sizeof(uint32_t) << 19;
  72.     int shmMal = shmget(12345, arrSize, IPC_CREAT | 0666);
  73.         if (shmMal < 0) return;
  74.     uint32_t *hist = (uint32_t *) shmat(shmMal, NULL, 0);
  75.         if ((int *) hist == (int *) -1) return;
  76.     int *temp = (int *) malloc(size * sizeof(int));
  77. 		if (!temp) return;
  78.  
  79.     histogram(array, size, 0, hist);
  80.     for (i=size-1;i>=0;i--)
  81.         temp[--hist[position(array[i], 0)]] = array[i];
  82.  
  83.     memset(hist, 0, arrSize);
  84.     histogram(temp, size, 1, hist);
  85.     for (i=size-1;i>=0;i--)
  86.         array[--hist[position(temp[i], 1)]] = temp[i];
  87.  
  88.     free(temp);
  89.     shmdt((void *) hist);
  90.     shmctl(shmMal, IPC_RMID, 0);
  91. }
  92.  
  93. #endif
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LRvli5
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

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!