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