| 235 | |
| 236 | template <typename T, typename FUNC> |
| 237 | INLINE void MergeArrays (FlatArray<T*> ptrs, |
| 238 | FlatArray<int> sizes, |
| 239 | FUNC f) |
| 240 | { |
| 241 | if (ptrs.Size() <= 16) |
| 242 | { |
| 243 | MergeArrays1 (ptrs, sizes, f); |
| 244 | return; |
| 245 | } |
| 246 | // static Timer tall("merge arrays"); RegionTimer reg(tall); |
| 247 | |
| 248 | struct valsrc { int val, src; }; |
| 249 | struct trange { int idx, val; }; |
| 250 | |
| 251 | int nactive = 0; |
| 252 | int nrange = 0; |
| 253 | /* |
| 254 | STACK_ARRAY(valsrc, minvals, sizes.Size()); |
| 255 | STACK_ARRAY(trange, ranges, sizes.Size()+1); |
| 256 | */ |
| 257 | ArrayMem<valsrc,1024> minvals(sizes.Size()); |
| 258 | ArrayMem<trange,1024> ranges(sizes.Size()+1); |
| 259 | |
| 260 | constexpr int nhash = 1024; // power of 2 |
| 261 | int hashes[nhash]; |
| 262 | |
| 263 | for (int i = 0; i < nhash; i++) |
| 264 | hashes[i] = -1; |
| 265 | |
| 266 | // take first value from every array ... |
| 267 | for (auto i : sizes.Range()) |
| 268 | while (sizes[i]) |
| 269 | { |
| 270 | auto val = *ptrs[i]; |
| 271 | sizes[i]--; |
| 272 | ptrs[i]++; |
| 273 | if (hashes[val&(nhash-1)] == val) continue; |
| 274 | minvals[nactive].val = val; |
| 275 | hashes[val&(nhash-1)] = val; |
| 276 | minvals[nactive].src = i; |
| 277 | nactive++; |
| 278 | break; |
| 279 | } |
| 280 | // cout << "starting values " << endl << minvals << endl; |
| 281 | |
| 282 | // presort minvals: |
| 283 | // values from ranges[i] up are all smaller or equal rangevals[i] |
| 284 | // minvals[j] <= rangevals[i] <==> j >= ranges[i] \forall i >= 0 |
| 285 | |
| 286 | while (nactive > 0) |
| 287 | { |
| 288 | // partial quicksort |
| 289 | int lower = 0; |
| 290 | if (nrange > 0) lower = ranges[nrange-1].idx; |
| 291 | |
| 292 | // cout << "start quicksort in range [" << lower << ", " << nactive-1 << "]" << endl; |
| 293 | while (true) |
| 294 | { |
no test coverage detected