/////////////////////////////////////////////////////////////////////////// Merge step 1: find sample ranks in each segment ///////////////////////////////////////////////////////////////////////////
| 108 | // Merge step 1: find sample ranks in each segment |
| 109 | //////////////////////////////////////////////////////////////////////////////// |
| 110 | static void generateSampleRanks(uint *ranksA, uint *ranksB, uint *srcKey, uint stride, uint N, uint sortDir) |
| 111 | { |
| 112 | uint lastSegmentElements = N % (2 * stride); |
| 113 | uint sampleCount = (lastSegmentElements > stride) ? (N + 2 * stride - lastSegmentElements) / (2 * SAMPLE_STRIDE) |
| 114 | : (N - lastSegmentElements) / (2 * SAMPLE_STRIDE); |
| 115 | |
| 116 | for (uint pos = 0; pos < sampleCount; pos++) { |
| 117 | const uint i = pos & ((stride / SAMPLE_STRIDE) - 1); |
| 118 | const uint segmentBase = (pos - i) * (2 * SAMPLE_STRIDE); |
| 119 | |
| 120 | const uint lenA = stride; |
| 121 | const uint lenB = umin(stride, N - segmentBase - stride); |
| 122 | const uint nA = stride / SAMPLE_STRIDE; |
| 123 | const uint nB = getSampleCount(lenB); |
| 124 | |
| 125 | if (i < nA) { |
| 126 | ranksA[(segmentBase + 0) / SAMPLE_STRIDE + i] = i * SAMPLE_STRIDE; |
| 127 | ranksB[(segmentBase + 0) / SAMPLE_STRIDE + i] = binarySearchExclusive( |
| 128 | srcKey[segmentBase + i * SAMPLE_STRIDE], srcKey + segmentBase + stride, lenB, sortDir); |
| 129 | } |
| 130 | |
| 131 | if (i < nB) { |
| 132 | ranksB[(segmentBase + stride) / SAMPLE_STRIDE + i] = i * SAMPLE_STRIDE; |
| 133 | ranksA[(segmentBase + stride) / SAMPLE_STRIDE + i] = binarySearchInclusive( |
| 134 | srcKey[segmentBase + stride + i * SAMPLE_STRIDE], srcKey + segmentBase, lenA, sortDir); |
| 135 | } |
| 136 | } |
| 137 | } |
| 138 | |
| 139 | //////////////////////////////////////////////////////////////////////////////// |
| 140 | // Merge step 2: merge ranks and indices to derive elementary intervals |
no test coverage detected