common/bucketsort.c

   1 #include "bucketsort.h"
   2
   3 extern void bucket_sort_intersect(uint32_t *const estart, uint32_t *const estop,
   4                                   uint32_t *const ostart, uint32_t *const ostop,
   5                                   bucket_info_t *bucket_info, bucket_array_t bucket) {
   6     uint32_t *p1, *p2;
   7     uint32_t *start[2];
   8     uint32_t *stop[2];
   9
  10     start[0] = estart;
  11     stop[0] = estop;
  12     start[1] = ostart;
  13     stop[1] = ostop;
  14
  15     // init buckets to be empty
  16     for (uint32_t i = 0; i < 2; i++) {
  17         for (uint32_t j = 0x00; j <= 0xff; j++) {
  18             bucket[i][j].bp = bucket[i][j].head;
  19         }
  20     }
  21
  22     // sort the lists into the buckets based on the MSB (contribution bits)
  23     for (uint32_t i = 0; i < 2; i++) {
  24         for (p1 = start[i]; p1 <= stop[i]; p1++) {
  25             uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
  26             *(bucket[i][bucket_index].bp++) = *p1;
  27         }
  28     }
  29
  30     // write back intersecting buckets as sorted list.
  31     // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
  32     for (uint32_t i = 0; i < 2; i++) {
  33         p1 = start[i];
  34         uint32_t nonempty_bucket = 0;
  35         for (uint32_t j = 0x00; j <= 0xff; j++) {
  36             if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
  37                 bucket_info->bucket_info[i][nonempty_bucket].head = p1;
  38                 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
  39                 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
  40                 nonempty_bucket++;
  41             }
  42         }
  43         bucket_info->numbuckets = nonempty_bucket;
  44     }
  45 }