radixsort.h (23557B)
1 #pragma once 2 3 /** 4 * type safe radix sort 5 * 6 * radix sort sorts keys that are either uint type or string type (char*) keys 7 * radix sort is faster than qsort from glibc and flashsort and takes less memory 8 * 9 * the radixyUintDef, radixyStringDef, radixyUintThreadDef, radixyStringThreadDef define the radix sort functions for arrays with the given element type: 10 * 11 * - shellsort##name or shellsortS##name - internal shell sort function 12 * - radixsort##name or radixsortS##name - function with all the parameters 13 * - name - function only with array and size parameters 14 * - nameSafe - like name and checks if there are empty strings 15 * 16 * the *ThreadDef macros defines threaded radix sort functions 17 * 18 * 19 * Example: 20 * 21 * // sorting array with string keys 22 * 23 * typ struct {char *a; int b;} skElemt; 24 * 25 * // define macro or function for access the key given an address to an element in the array 26 * #define radixsortAt(ptr) (ptr)->a 27 * 28 * // define a radixsort function with name 'radiS' and 'radiSSafe' sorting arrays with skElemt element type 29 * radixyStringDef(,radiS,skElemt,6,4, 40); 30 * #undef radixsortAt 31 * 32 * // the radiSSafe check if there are empty strings (NULL or "") in the keys 33 * // Empty strings are not allowed. 34 * 35 * // declare array 36 * skElemt radS[200]; 37 * 38 * // sort the array 39 * radiS(radS, sz); 40 * 41 * // or call safe function: 42 * if (!radiSSafe(radS, sz)) { 43 * logE("Empty strings are not allowed"); 44 * } 45 * 46 * 47 * 48 * // sorting a u32 array 49 * 50 * // define macro or function for access the key given an address to an element in the array 51 * #define radixsortAt(ptr) *(ptr) 52 * 53 * // define a radixsort function with name 'radi' sorting u32 arrays 54 * radixyUintDef(, radi , u32, 6, 4, 40); 55 * #undef radixsortAt 56 * 57 * // declare array 58 * u32 urnd[200]; 59 * 60 * // sort the array 61 * radi(urnd, 200); 62 * 63 * 64 * 65 * // sorting an array with struct elements 66 * 67 * // declare element type 68 * typ struct {u64 a; int b;} rdxElemt; 69 * 70 * // define macro or function to access the key given an address to an element in the array 71 * #define radixsortAt(ptr) (ptr)->a 72 * 73 * // define a radixsort function with name 'radi64' sorting arrays with elements of type rdxElemt and u64 keys 74 * radixyUintDef(, radi64 , rdxElemt, 6, 4, 40); 75 * #undef radixsortAt 76 * 77 * // declare array 78 * rdxElemt radA[200]; 79 * 80 * // sort the array 81 * radi64(radA, 200); 82 * 83 */ 84 85 // define for internal use in radixyUint 86 #define radixyStop 256 87 88 /** 89 * radixyUintDef defines functions for sorting arrays of elemType 90 * the keys have to be unsigned int (any size) 91 * 92 * Functions: 93 * - shellsort##name - internal shell sort function 94 * - radixsort##name - function with all the parameters 95 * - name - function only with array and size parameters 96 * 97 * \param 98 * scope is static, internal or empty 99 * \param 100 * name function name for the sort function 101 * \param 102 * stackSizeP is the depth of the look-forward stack 103 * \param 104 * cutoffP is the digit cutoff for switching to shellsort 105 * \param 106 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort 107 */ 108 #define radixyUintDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\ 109 internal inline void shellsort##name(elemType *arr, size_t size) {\ 110 typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\ 111 typeof(arr[0]) elem; /* tmp record */\ 112 \ 113 {rangeFrom(i, 3, size) {\ 114 tmp = radixsortAt(&arr[i]);\ 115 elem = arr[i];\ 116 size_t j;\ 117 for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\ 118 arr[j] = arr[j-3];\ 119 }\ 120 arr[j] = elem;\ 121 }}\ 122 \ 123 {rangeFrom(i, 1, size) {\ 124 tmp = radixsortAt(&arr[i]);\ 125 elem = arr[i];\ 126 size_t j;\ 127 for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\ 128 arr[j] = arr[j-1];\ 129 }\ 130 arr[j] = elem;\ 131 }}\ 132 }\ 133 \ 134 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\ 135 u8 *a;\ 136 size_t counts[radixyStop];\ 137 size_t offsets[radixyStop];\ 138 size_t starts[radixyStop];\ 139 size_t ends[radixyStop];\ 140 size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\ 141 \ 142 pError0(zeroBuf(counts, sizeof(counts)));\ 143 \ 144 /* compute counts */\ 145 {range(x, size) {\ 146 a = (u8*)&radixsortAt(&arr[x]);\ 147 u8 c = a[digt];\ 148 counts[c]++;\ 149 }}\ 150 \ 151 /* compute offsets */\ 152 offsets[0] = 0;\ 153 starts[0] = 0;\ 154 {rangeFrom(x, 1, radixyStop) {\ 155 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\ 156 }}\ 157 ends[radixyStop-1] = size;\ 158 \ 159 \ 160 /* loop on digit values */\ 161 {range(x, radixyStop) {\ 162 /* move records according to digit value */\ 163 while(offsets[x] < ends[x]) {\ 164 a = (u8*)&radixsortAt(&arr[offsets[x]]);\ 165 u8 target = a[digt];\ 166 if (target == x) {\ 167 /* this record already placed in the correct bucket */\ 168 offsets[x]++;\ 169 }\ 170 else {\ 171 size_t stackIdx = 0;\ 172 size_t stack[stackSize];\ 173 stack[stackIdx++] = offsets[x];\ 174 while(target != x && stackIdx < stackSize) {\ 175 stack[stackIdx] = offsets[target]++;\ 176 a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\ 177 target = a[digt];\ 178 stackIdx++;\ 179 }\ 180 if (stackIdx != stackSize) {\ 181 /* found an element to store a offsets[x] */\ 182 offsets[x]++;\ 183 }\ 184 stackIdx--;\ 185 var tmp = arr[stack[stackIdx]];\ 186 while(stackIdx) {\ 187 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 188 stackIdx--;\ 189 }\ 190 arr[stack[0]] = tmp;\ 191 }\ 192 }\ 193 }}\ 194 \ 195 /* cutoff to shellsort */\ 196 if (digit < cutoff) {\ 197 /* loop on digit values to sort the buckets */\ 198 {range(x, radixyStop) {\ 199 if (counts[x] > radixLevel) {\ 200 radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\ 201 }\ 202 else {\ 203 if (counts[x] < 2) continue;\ 204 shellsort##name(&arr[starts[x]], counts[x]);\ 205 }\ 206 }}\ 207 }\ 208 else {\ 209 {range(x, radixyStop) {\ 210 if (counts[x] > 1) {\ 211 shellsort##name(&arr[starts[x]], counts[x]);\ 212 }\ 213 }}\ 214 }\ 215 }\ 216 scope void name(elemType *arr, size_t size) {\ 217 radixsort##name(arr, size, 0, stackSizeP, cutoffP);\ 218 } 219 220 221 /** 222 * radixyUintThreadDef (like radixyUintDef) defines functions for sorting arrays of elemType 223 * the keys have to be unsigned int (any size) 224 * 225 * the defined functions by this macro are multithreaded using the threadpool in libsheepy 226 * 227 * Functions: 228 * - shellsort##name - internal shell sort function 229 * - radixsort##name - function with all the parameters 230 * - name - function only with array and size parameters 231 * 232 * \param 233 * scope is static, internal or empty 234 * \param 235 * name function name for the sort function 236 * \param 237 * stackSizeP is the depth of the look-forward stack 238 * \param 239 * cutoffP is the digit cutoff for switching to shellsort 240 * \param 241 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort 242 */ 243 #define radixyUintThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\ 244 internal inline void shellsort##name(elemType *arr, size_t size) {\ 245 typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\ 246 typeof(arr[0]) elem; /* tmp record */\ 247 \ 248 {rangeFrom(i, 3, size) {\ 249 tmp = radixsortAt(&arr[i]);\ 250 elem = arr[i];\ 251 size_t j;\ 252 for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\ 253 arr[j] = arr[j-3];\ 254 }\ 255 arr[j] = elem;\ 256 }}\ 257 \ 258 {rangeFrom(i, 1, size) {\ 259 tmp = radixsortAt(&arr[i]);\ 260 elem = arr[i];\ 261 size_t j;\ 262 for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\ 263 arr[j] = arr[j-1];\ 264 }\ 265 arr[j] = elem;\ 266 }}\ 267 }\ 268 \ 269 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff);\ 270 \ 271 typ struct {elemType *arr; size_t size; size_t digit; size_t stackSize; size_t cutoff;} radixy##name##Argst;\ 272 \ 273 void radixsort##name##Thread(void *args) {\ 274 cast(radixy##name##Argst*, p, args);\ 275 radixsort##name(p->arr, p->size, p->digit, p->stackSize, p->cutoff);\ 276 }\ 277 \ 278 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\ 279 u8 *a;\ 280 size_t counts[radixyStop];\ 281 size_t offsets[radixyStop];\ 282 size_t starts[radixyStop];\ 283 size_t ends[radixyStop];\ 284 size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\ 285 radixy##name##Argst rdxArgs[radixyStop]; /* arguments for functions in the threadpool */\ 286 size_t rdxArgsIdx = 0;\ 287 \ 288 pError0(zeroBuf(counts, sizeof(counts)));\ 289 \ 290 /* compute counts */\ 291 {range(x, size) {\ 292 a = (u8*)&radixsortAt(&arr[x]);\ 293 u8 c = a[digt];\ 294 counts[c]++;\ 295 }}\ 296 \ 297 /* compute offsets */\ 298 offsets[0] = 0;\ 299 starts[0] = 0;\ 300 {rangeFrom(x, 1, radixyStop) {\ 301 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\ 302 }}\ 303 ends[radixyStop-1] = size;\ 304 \ 305 \ 306 /* loop on digit values */\ 307 {range(x, radixyStop) {\ 308 /* move records according to digit value */\ 309 while(offsets[x] < ends[x]) {\ 310 a = (u8*)&radixsortAt(&arr[offsets[x]]);\ 311 u8 target = a[digt];\ 312 if (target == x) {\ 313 /* this record already placed in the correct bucket */\ 314 offsets[x]++;\ 315 }\ 316 else {\ 317 size_t stackIdx = 0;\ 318 size_t stack[stackSize];\ 319 stack[stackIdx++] = offsets[x];\ 320 while(target != x && stackIdx < stackSize) {\ 321 stack[stackIdx] = offsets[target]++;\ 322 a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\ 323 target = a[digt];\ 324 stackIdx++;\ 325 }\ 326 if (stackIdx != stackSize) {\ 327 /* found an element to store a offsets[x] */\ 328 offsets[x]++;\ 329 }\ 330 stackIdx--;\ 331 var tmp = arr[stack[stackIdx]];\ 332 while(stackIdx) {\ 333 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 334 stackIdx--;\ 335 }\ 336 arr[stack[0]] = tmp;\ 337 }\ 338 }\ 339 }}\ 340 \ 341 /* cutoff to shellsort */\ 342 if (digit < cutoff) {\ 343 /* loop on digit values to sort the buckets */\ 344 {range(x, radixyStop) {\ 345 if (counts[x] > radixLevel) {\ 346 if (!digit) {\ 347 rdxArgs[rdxArgsIdx] = (radixy##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .stackSize=stackSize, .cutoff=cutoff};\ 348 tpoolAdd(radixsort##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\ 349 rdxArgsIdx++;\ 350 }\ 351 else\ 352 radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\ 353 }\ 354 else {\ 355 if (counts[x] < 2) continue;\ 356 shellsort##name(&arr[starts[x]], counts[x]);\ 357 }\ 358 }}\ 359 }\ 360 else {\ 361 {range(x, radixyStop) {\ 362 if (counts[x] > 1) {\ 363 shellsort##name(&arr[starts[x]], counts[x]);\ 364 }\ 365 }}\ 366 }\ 367 \ 368 if (!digit) {\ 369 tpoolWait;\ 370 }\ 371 }\ 372 scope void name(elemType *arr, size_t size) {\ 373 radixsort##name(arr, size, 0, stackSizeP, cutoffP);\ 374 } 375 376 377 /** 378 * radixyStringDef defines functions for sorting arrays of elemType 379 * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults) 380 * 381 * Functions: 382 * - shellsortS##name - internal shell sort function 383 * - radixsortS##name - function with all the parameters 384 * - name - function only with array and size parameters 385 * - nameSafe - like name and checks if there are empty strings 386 * 387 * \param 388 * scope is static, internal or empty 389 * \param 390 * name function name for the sort function 391 * \param 392 * stackSizeP is the depth of the look-forward stack 393 * \param 394 * cutoffP is the digit cutoff for switching to shellsort 395 * \param 396 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort 397 */ 398 #define radixyStringDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\ 399 internal inline void shellsortS##name(elemType *arr, size_t size) {\ 400 char *tmp; /* tmp key */\ 401 typeof(arr[0]) elem; /* tmp record */\ 402 \ 403 {rangeFrom(i, 3, size) {\ 404 tmp = radixsortAt(&arr[i]);\ 405 elem = arr[i];\ 406 size_t j;\ 407 for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\ 408 arr[j] = arr[j-3];\ 409 }\ 410 arr[j] = elem;\ 411 }}\ 412 \ 413 {rangeFrom(i, 1, size) {\ 414 tmp = radixsortAt(&arr[i]);\ 415 elem = arr[i];\ 416 size_t j;\ 417 for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\ 418 arr[j] = arr[j-1];\ 419 }\ 420 arr[j] = elem;\ 421 }}\ 422 }\ 423 \ 424 /** 425 * radixyS doesn't accept empty strings 426 * it segfaults when there is an empty string in the array 427 */\ 428 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\ 429 size_t counts[charStop+1];\ 430 size_t offsets[charStop+1];\ 431 size_t starts[charStop+1];\ 432 size_t ends[charStop+1];\ 433 size_t digt = digit;\ 434 \ 435 pError0(zeroBuf(counts, sizeof(counts)));\ 436 \ 437 /* compute counts */\ 438 {range(x, size) {\ 439 u8 c = *(radixsortAt(&arr[x])+digt);\ 440 counts[c]++;\ 441 }}\ 442 \ 443 /* compute offsets */\ 444 offsets[0] = 0;\ 445 starts[0] = 0;\ 446 offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\ 447 rangeFrom(x, charStart+1, charStop+1) {\ 448 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\ 449 }\ 450 ends[charStop] = size;\ 451 \ 452 /* sort 0 end of string */\ 453 /* move records according to digit value */\ 454 while(offsets[0] < ends[0]) {\ 455 u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\ 456 if (target == 0) {\ 457 /* this record already placed in the correct bucket */\ 458 offsets[0]++;\ 459 }\ 460 else {\ 461 size_t stackIdx = 0;\ 462 size_t stack[stackSize];\ 463 stack[stackIdx++] = offsets[0];\ 464 while(target != 0 && stackIdx < stackSize) {\ 465 stack[stackIdx] = offsets[target]++;\ 466 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\ 467 stackIdx++;\ 468 }\ 469 if (stackIdx != stackSize) {\ 470 /* found an element to store a offsets[0] */\ 471 offsets[0]++;\ 472 }\ 473 stackIdx--;\ 474 var tmp = arr[stack[stackIdx]];\ 475 while(stackIdx) {\ 476 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 477 stackIdx--;\ 478 }\ 479 arr[stack[0]] = tmp;\ 480 }\ 481 }\ 482 /* loop on digit values */\ 483 {rangeFrom(x, charStart, charStop+1) {\ 484 /* move records according to digit value */\ 485 while(offsets[x] < ends[x]) {\ 486 u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\ 487 if (target == x) {\ 488 /* this record already placed in the correct bucket */\ 489 offsets[x]++;\ 490 }\ 491 else {\ 492 size_t stackIdx = 0;\ 493 size_t stack[stackSize];\ 494 stack[stackIdx++] = offsets[x];\ 495 while(target != x && stackIdx < stackSize) {\ 496 stack[stackIdx] = offsets[target]++;\ 497 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\ 498 stackIdx++;\ 499 }\ 500 if (stackIdx != stackSize) {\ 501 /* found an element to store a offsets[x] */\ 502 offsets[x]++;\ 503 }\ 504 stackIdx--;\ 505 var tmp = arr[stack[stackIdx]];\ 506 while(stackIdx) {\ 507 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 508 stackIdx--;\ 509 }\ 510 arr[stack[0]] = tmp;\ 511 }\ 512 }\ 513 }}\ 514 \ 515 /* cutoff to shellsort */\ 516 if (digit < cutoff) {\ 517 /* sort 0 end of string */\ 518 if (counts[0] > radixLevel) {\ 519 radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\ 520 }\ 521 else {\ 522 if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\ 523 }\ 524 /* loop on digit values to sort the buckets */\ 525 {rangeFrom(x, charStart, charStop+1) {\ 526 if (counts[x] > radixLevel) {\ 527 radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\ 528 }\ 529 else {\ 530 if (counts[x] < 2) continue;\ 531 shellsortS##name(&arr[starts[x]], counts[x]);\ 532 }\ 533 }}\ 534 }\ 535 else {\ 536 if (counts[0] > 1) {\ 537 shellsortS##name(&arr[starts[0]], counts[0]);\ 538 }\ 539 rangeFrom(x, charStart, charStop+1) {\ 540 if (counts[x] > 1) {\ 541 shellsortS##name(&arr[starts[x]], counts[x]);\ 542 }\ 543 }\ 544 }\ 545 }\ 546 scope void name(elemType *arr, size_t size) {\ 547 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\ 548 }\ 549 scope bool name##Safe(elemType *arr, size_t size) {\ 550 {range(i, size) {\ 551 if (isEmptyS(radixsortAt(&arr[i]))) ret false;\ 552 }}\ 553 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\ 554 ret true;\ 555 } 556 557 558 559 /** 560 * radixyStringThreadDef (like radixyStringDef) defines functions for sorting arrays of elemType 561 * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults) 562 * 563 * the defined functions by this macro are multithreaded using the threadpool in libsheepy 564 * 565 * Functions: 566 * - shellsortS##name - internal shell sort function 567 * - radixsortS##name - function with all the parameters 568 * - name - function only with array and size parameters 569 * - nameSafe - like name and checks if there are empty strings 570 * 571 * \param 572 * scope is static, internal or empty 573 * \param 574 * name function name for the sort function 575 * \param 576 * stackSizeP is the depth of the look-forward stack 577 * \param 578 * cutoffP is the digit cutoff for switching to shellsort 579 * \param 580 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort 581 */ 582 #define radixyStringThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\ 583 internal inline void shellsortS##name(elemType *arr, size_t size) {\ 584 char *tmp; /* tmp key */\ 585 typeof(arr[0]) elem; /* tmp record */\ 586 \ 587 {rangeFrom(i, 3, size) {\ 588 tmp = radixsortAt(&arr[i]);\ 589 elem = arr[i];\ 590 size_t j;\ 591 for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\ 592 arr[j] = arr[j-3];\ 593 }\ 594 arr[j] = elem;\ 595 }}\ 596 \ 597 {rangeFrom(i, 1, size) {\ 598 tmp = radixsortAt(&arr[i]);\ 599 elem = arr[i];\ 600 size_t j;\ 601 for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\ 602 arr[j] = arr[j-1];\ 603 }\ 604 arr[j] = elem;\ 605 }}\ 606 }\ 607 \ 608 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff);\ 609 \ 610 typ struct {elemType *arr; size_t size; size_t digit; u8 charStart; u16 charStop; size_t stackSize; size_t cutoff;} radixyS##name##Argst;\ 611 \ 612 void radixsortS##name##Thread(void *args) {\ 613 cast(radixyS##name##Argst*, p, args);\ 614 radixsortS##name(p->arr, p->size, p->digit, p->charStart, p->charStop, p->stackSize, p->cutoff);\ 615 }\ 616 \ 617 /** 618 * radixyS doesn't accept empty strings 619 * it segfaults when there is an empty string in the array 620 */\ 621 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\ 622 size_t counts[charStop+1];\ 623 size_t offsets[charStop+1];\ 624 size_t starts[charStop+1];\ 625 size_t ends[charStop+1];\ 626 size_t digt = digit;\ 627 radixyS##name##Argst rdxArgs[charStop+1]; /* arguments for functions in the threadpool */\ 628 size_t rdxArgsIdx = 0;\ 629 \ 630 pError0(zeroBuf(counts, sizeof(counts)));\ 631 \ 632 /* compute counts */\ 633 {range(x, size) {\ 634 u8 c = *(radixsortAt(&arr[x])+digt);\ 635 counts[c]++;\ 636 }}\ 637 \ 638 /* compute offsets */\ 639 offsets[0] = 0;\ 640 starts[0] = 0;\ 641 offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\ 642 rangeFrom(x, charStart+1, charStop+1) {\ 643 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\ 644 }\ 645 ends[charStop] = size;\ 646 \ 647 /* sort 0 end of string */\ 648 /* move records according to digit value */\ 649 while(offsets[0] < ends[0]) {\ 650 u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\ 651 if (target == 0) {\ 652 /* this record already placed in the correct bucket */\ 653 offsets[0]++;\ 654 }\ 655 else {\ 656 size_t stackIdx = 0;\ 657 size_t stack[stackSize];\ 658 stack[stackIdx++] = offsets[0];\ 659 while(target != 0 && stackIdx < stackSize) {\ 660 stack[stackIdx] = offsets[target]++;\ 661 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\ 662 stackIdx++;\ 663 }\ 664 if (stackIdx != stackSize) {\ 665 /* found an element to store a offsets[0] */\ 666 offsets[0]++;\ 667 }\ 668 stackIdx--;\ 669 var tmp = arr[stack[stackIdx]];\ 670 while(stackIdx) {\ 671 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 672 stackIdx--;\ 673 }\ 674 arr[stack[0]] = tmp;\ 675 }\ 676 }\ 677 /* loop on digit values */\ 678 {rangeFrom(x, charStart, charStop+1) {\ 679 /* move records according to digit value */\ 680 while(offsets[x] < ends[x]) {\ 681 u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\ 682 if (target == x) {\ 683 /* this record already placed in the correct bucket */\ 684 offsets[x]++;\ 685 }\ 686 else {\ 687 size_t stackIdx = 0;\ 688 size_t stack[stackSize];\ 689 stack[stackIdx++] = offsets[x];\ 690 while(target != x && stackIdx < stackSize) {\ 691 stack[stackIdx] = offsets[target]++;\ 692 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\ 693 stackIdx++;\ 694 }\ 695 if (stackIdx != stackSize) {\ 696 /* found an element to store a offsets[x] */\ 697 offsets[x]++;\ 698 }\ 699 stackIdx--;\ 700 var tmp = arr[stack[stackIdx]];\ 701 while(stackIdx) {\ 702 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\ 703 stackIdx--;\ 704 }\ 705 arr[stack[0]] = tmp;\ 706 }\ 707 }\ 708 }}\ 709 \ 710 /* cutoff to shellsort */\ 711 if (digit < cutoff) {\ 712 /* sort 0 end of string */\ 713 if (counts[0] > radixLevel) {\ 714 if (!digit) {\ 715 rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[0]], .size=counts[0], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\ 716 tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\ 717 rdxArgsIdx++;\ 718 }\ 719 else\ 720 radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\ 721 }\ 722 else {\ 723 if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\ 724 }\ 725 /* loop on digit values to sort the buckets */\ 726 {rangeFrom(x, charStart, charStop+1) {\ 727 if (counts[x] > radixLevel) {\ 728 if (!digit) {\ 729 rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\ 730 tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\ 731 rdxArgsIdx++;\ 732 }\ 733 else\ 734 radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\ 735 }\ 736 else {\ 737 if (counts[x] < 2) continue;\ 738 shellsortS##name(&arr[starts[x]], counts[x]);\ 739 }\ 740 }}\ 741 }\ 742 else {\ 743 if (counts[0] > 1) {\ 744 shellsortS##name(&arr[starts[0]], counts[0]);\ 745 }\ 746 rangeFrom(x, charStart, charStop+1) {\ 747 if (counts[x] > 1) {\ 748 shellsortS##name(&arr[starts[x]], counts[x]);\ 749 }\ 750 }\ 751 }\ 752 \ 753 if (!digit) {\ 754 tpoolWait;\ 755 }\ 756 }\ 757 scope void name(elemType *arr, size_t size) {\ 758 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\ 759 }\ 760 scope bool name##Safe(elemType *arr, size_t size) {\ 761 {range(i, size) {\ 762 if (isEmptyS(radixsortAt(&arr[i]))) ret false;\ 763 }}\ 764 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\ 765 ret true;\ 766 } 767 768 // vim: set expandtab ts=2 sw=2: