1 /*- 2 * Copyright (C) 2012 Oleg Moskalenko <oleg.moskalenko@citrix.com> 3 * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <sys/cdefs.h> 29 __FBSDID("$FreeBSD$"); 30 31 #include <errno.h> 32 #include <err.h> 33 #include <langinfo.h> 34 #include <math.h> 35 #if defined(SORT_THREADS) 36 #include <pthread.h> 37 #include <semaphore.h> 38 #endif 39 #include <stdlib.h> 40 #include <string.h> 41 #include <wchar.h> 42 #include <wctype.h> 43 #include <unistd.h> 44 45 #include "coll.h" 46 #include "radixsort.h" 47 48 #define TINY_NODE(sl) ((sl)->tosort_num < 65) 49 #define SMALL_NODE(sl) ((sl)->tosort_num < 5) 50 51 /* are we sorting in reverse order ? */ 52 static bool reverse_sort; 53 54 /* sort sub-levels array size */ 55 static const size_t slsz = 256 * sizeof(struct sort_level*); 56 57 /* one sort level structure */ 58 struct sort_level 59 { 60 struct sort_level **sublevels; 61 struct sort_list_item **leaves; 62 struct sort_list_item **sorted; 63 struct sort_list_item **tosort; 64 size_t leaves_num; 65 size_t leaves_sz; 66 size_t level; 67 size_t real_sln; 68 size_t start_position; 69 size_t sln; 70 size_t tosort_num; 71 size_t tosort_sz; 72 }; 73 74 /* stack of sort levels ready to be sorted */ 75 struct level_stack { 76 struct level_stack *next; 77 struct sort_level *sl; 78 }; 79 80 static struct level_stack *g_ls; 81 82 #if defined(SORT_THREADS) 83 /* stack guarding mutex */ 84 static pthread_mutex_t g_ls_mutex; 85 86 /* counter: how many items are left */ 87 static size_t sort_left; 88 /* guarding mutex */ 89 static pthread_mutex_t sort_left_mutex; 90 91 /* semaphore to count threads */ 92 static sem_t mtsem; 93 94 /* 95 * Decrement items counter 96 */ 97 static inline void 98 sort_left_dec(size_t n) 99 { 100 101 pthread_mutex_lock(&sort_left_mutex); 102 sort_left -= n; 103 pthread_mutex_unlock(&sort_left_mutex); 104 } 105 106 /* 107 * Do we have something to sort ? 108 */ 109 static inline bool 110 have_sort_left(void) 111 { 112 bool ret; 113 114 pthread_mutex_lock(&sort_left_mutex); 115 ret = (sort_left > 0); 116 pthread_mutex_unlock(&sort_left_mutex); 117 return (ret); 118 } 119 120 #else 121 122 #define sort_left_dec(n) 123 124 #endif /* SORT_THREADS */ 125 126 /* 127 * Push sort level to the stack 128 */ 129 static inline void 130 push_ls(struct sort_level* sl) 131 { 132 struct level_stack *new_ls; 133 134 new_ls = sort_malloc(sizeof(struct level_stack)); 135 new_ls->sl = sl; 136 137 #if defined(SORT_THREADS) 138 if (nthreads > 1) 139 pthread_mutex_lock(&g_ls_mutex); 140 #endif 141 142 new_ls->next = g_ls; 143 g_ls = new_ls; 144 145 #if defined(SORT_THREADS) 146 if (nthreads > 1) 147 pthread_mutex_unlock(&g_ls_mutex); 148 #endif 149 } 150 151 /* 152 * Pop sort level from the stack (single-threaded style) 153 */ 154 static inline struct sort_level* 155 pop_ls_st(void) 156 { 157 struct sort_level *sl; 158 159 if (g_ls) { 160 struct level_stack *saved_ls; 161 162 sl = g_ls->sl; 163 saved_ls = g_ls; 164 g_ls = g_ls->next; 165 sort_free(saved_ls); 166 } else 167 sl = NULL; 168 169 return (sl); 170 } 171 172 /* 173 * Pop sort level from the stack (multi-threaded style) 174 */ 175 static inline struct sort_level* 176 pop_ls_mt(void) 177 { 178 struct level_stack *saved_ls; 179 struct sort_level *sl; 180 181 #if defined(SORT_THREADS) 182 pthread_mutex_lock(&g_ls_mutex); 183 #endif 184 185 if (g_ls) { 186 sl = g_ls->sl; 187 saved_ls = g_ls; 188 g_ls = g_ls->next; 189 } else { 190 sl = NULL; 191 saved_ls = NULL; 192 } 193 194 #if defined(SORT_THREADS) 195 pthread_mutex_unlock(&g_ls_mutex); 196 #endif 197 198 sort_free(saved_ls); 199 200 return (sl); 201 } 202 203 static void 204 add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, int indx) 205 { 206 struct sort_level *ssl; 207 208 ssl = sl->sublevels[indx]; 209 210 if (ssl == NULL) { 211 ssl = sort_malloc(sizeof(struct sort_level)); 212 memset(ssl, 0, sizeof(struct sort_level)); 213 214 ssl->level = sl->level + 1; 215 sl->sublevels[indx] = ssl; 216 217 ++(sl->real_sln); 218 } 219 220 if (++(ssl->tosort_num) > ssl->tosort_sz) { 221 ssl->tosort_sz = ssl->tosort_num + 128; 222 ssl->tosort = sort_realloc(ssl->tosort, 223 sizeof(struct sort_list_item*) * (ssl->tosort_sz)); 224 } 225 226 ssl->tosort[ssl->tosort_num - 1] = item; 227 } 228 229 static inline void 230 add_leaf(struct sort_level *sl, struct sort_list_item *item) 231 { 232 233 if (++(sl->leaves_num) > sl->leaves_sz) { 234 sl->leaves_sz = sl->leaves_num + 128; 235 sl->leaves = sort_realloc(sl->leaves, 236 (sizeof(struct sort_list_item*) * (sl->leaves_sz))); 237 } 238 sl->leaves[sl->leaves_num - 1] = item; 239 } 240 241 static inline int 242 get_wc_index(struct sort_list_item *sli, size_t level) 243 { 244 const struct bwstring *bws; 245 246 bws = sli->ka.key[0].k; 247 248 if ((BWSLEN(bws) > level)) 249 return (unsigned char) BWS_GET(bws,level); 250 return (-1); 251 } 252 253 static void 254 place_item(struct sort_level *sl, size_t item) 255 { 256 struct sort_list_item *sli; 257 int c; 258 259 sli = sl->tosort[item]; 260 c = get_wc_index(sli, sl->level); 261 262 if (c == -1) 263 add_leaf(sl, sli); 264 else 265 add_to_sublevel(sl, sli, c); 266 } 267 268 static void 269 free_sort_level(struct sort_level *sl) 270 { 271 272 if (sl) { 273 if (sl->leaves) 274 sort_free(sl->leaves); 275 276 if (sl->level > 0) 277 sort_free(sl->tosort); 278 279 if (sl->sublevels) { 280 struct sort_level *slc; 281 size_t sln; 282 283 sln = sl->sln; 284 285 for (size_t i = 0; i < sln; ++i) { 286 slc = sl->sublevels[i]; 287 if (slc) 288 free_sort_level(slc); 289 } 290 291 sort_free(sl->sublevels); 292 } 293 294 sort_free(sl); 295 } 296 } 297 298 static void 299 run_sort_level_next(struct sort_level *sl) 300 { 301 struct sort_level *slc; 302 size_t i, sln, tosort_num; 303 304 if (sl->sublevels) { 305 sort_free(sl->sublevels); 306 sl->sublevels = NULL; 307 } 308 309 switch (sl->tosort_num){ 310 case 0: 311 goto end; 312 case (1): 313 sl->sorted[sl->start_position] = sl->tosort[0]; 314 sort_left_dec(1); 315 goto end; 316 case (2): 317 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]), 318 sl->level) > 0) { 319 sl->sorted[sl->start_position++] = sl->tosort[1]; 320 sl->sorted[sl->start_position] = sl->tosort[0]; 321 } else { 322 sl->sorted[sl->start_position++] = sl->tosort[0]; 323 sl->sorted[sl->start_position] = sl->tosort[1]; 324 } 325 sort_left_dec(2); 326 327 goto end; 328 default: 329 if (TINY_NODE(sl) || (sl->level > 15)) { 330 listcoll_t func; 331 332 func = get_list_call_func(sl->level); 333 334 sl->leaves = sl->tosort; 335 sl->leaves_num = sl->tosort_num; 336 sl->leaves_sz = sl->leaves_num; 337 sl->leaves = sort_realloc(sl->leaves, 338 (sizeof(struct sort_list_item *) * 339 (sl->leaves_sz))); 340 sl->tosort = NULL; 341 sl->tosort_num = 0; 342 sl->tosort_sz = 0; 343 sl->sln = 0; 344 sl->real_sln = 0; 345 if (sort_opts_vals.sflag) { 346 if (mergesort(sl->leaves, sl->leaves_num, 347 sizeof(struct sort_list_item *), 348 (int(*)(const void *, const void *)) func) == -1) 349 /* NOTREACHED */ 350 err(2, "Radix sort error 3"); 351 } else 352 qsort(sl->leaves, sl->leaves_num, 353 sizeof(struct sort_list_item *), 354 (int(*)(const void *, const void *)) func); 355 356 memcpy(sl->sorted + sl->start_position, 357 sl->leaves, sl->leaves_num * 358 sizeof(struct sort_list_item*)); 359 360 sort_left_dec(sl->leaves_num); 361 362 goto end; 363 } else { 364 sl->tosort_sz = sl->tosort_num; 365 sl->tosort = sort_realloc(sl->tosort, 366 sizeof(struct sort_list_item*) * (sl->tosort_sz)); 367 } 368 } 369 370 sl->sln = 256; 371 sl->sublevels = sort_malloc(slsz); 372 memset(sl->sublevels, 0, slsz); 373 374 sl->real_sln = 0; 375 376 tosort_num = sl->tosort_num; 377 for (i = 0; i < tosort_num; ++i) 378 place_item(sl, i); 379 380 sort_free(sl->tosort); 381 sl->tosort = NULL; 382 sl->tosort_num = 0; 383 sl->tosort_sz = 0; 384 385 if (sl->leaves_num > 1) { 386 if (keys_num > 1) { 387 if (sort_opts_vals.sflag) { 388 mergesort(sl->leaves, sl->leaves_num, 389 sizeof(struct sort_list_item *), 390 (int(*)(const void *, const void *)) list_coll); 391 } else { 392 qsort(sl->leaves, sl->leaves_num, 393 sizeof(struct sort_list_item *), 394 (int(*)(const void *, const void *)) list_coll); 395 } 396 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 397 qsort(sl->leaves, sl->leaves_num, 398 sizeof(struct sort_list_item *), 399 (int(*)(const void *, const void *)) list_coll_by_str_only); 400 } 401 } 402 403 sl->leaves_sz = sl->leaves_num; 404 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) * 405 (sl->leaves_sz))); 406 407 if (!reverse_sort) { 408 memcpy(sl->sorted + sl->start_position, sl->leaves, 409 sl->leaves_num * sizeof(struct sort_list_item*)); 410 sl->start_position += sl->leaves_num; 411 sort_left_dec(sl->leaves_num); 412 413 sort_free(sl->leaves); 414 sl->leaves = NULL; 415 sl->leaves_num = 0; 416 sl->leaves_sz = 0; 417 418 sln = sl->sln; 419 420 for (i = 0; i < sln; ++i) { 421 slc = sl->sublevels[i]; 422 423 if (slc) { 424 slc->sorted = sl->sorted; 425 slc->start_position = sl->start_position; 426 sl->start_position += slc->tosort_num; 427 if (SMALL_NODE(slc)) 428 run_sort_level_next(slc); 429 else 430 push_ls(slc); 431 sl->sublevels[i] = NULL; 432 } 433 } 434 435 } else { 436 size_t n; 437 438 sln = sl->sln; 439 440 for (i = 0; i < sln; ++i) { 441 n = sln - i - 1; 442 slc = sl->sublevels[n]; 443 444 if (slc) { 445 slc->sorted = sl->sorted; 446 slc->start_position = sl->start_position; 447 sl->start_position += slc->tosort_num; 448 if (SMALL_NODE(slc)) 449 run_sort_level_next(slc); 450 else 451 push_ls(slc); 452 sl->sublevels[n] = NULL; 453 } 454 } 455 456 memcpy(sl->sorted + sl->start_position, sl->leaves, 457 sl->leaves_num * sizeof(struct sort_list_item*)); 458 sort_left_dec(sl->leaves_num); 459 } 460 461 end: 462 free_sort_level(sl); 463 } 464 465 /* 466 * Single-threaded sort cycle 467 */ 468 static void 469 run_sort_cycle_st(void) 470 { 471 struct sort_level *slc; 472 473 for (;;) { 474 slc = pop_ls_st(); 475 if (slc == NULL) { 476 break; 477 } 478 run_sort_level_next(slc); 479 } 480 } 481 482 #if defined(SORT_THREADS) 483 484 /* 485 * Multi-threaded sort cycle 486 */ 487 static void 488 run_sort_cycle_mt(void) 489 { 490 struct sort_level *slc; 491 492 for (;;) { 493 slc = pop_ls_mt(); 494 if (slc == NULL) { 495 if (have_sort_left()) { 496 pthread_yield(); 497 continue; 498 } 499 break; 500 } 501 run_sort_level_next(slc); 502 } 503 } 504 505 /* 506 * Sort cycle thread (in multi-threaded mode) 507 */ 508 static void* 509 sort_thread(void* arg) 510 { 511 512 run_sort_cycle_mt(); 513 514 sem_post(&mtsem); 515 516 return (arg); 517 } 518 519 #endif /* defined(SORT_THREADS) */ 520 521 static void 522 run_top_sort_level(struct sort_level *sl) 523 { 524 struct sort_level *slc; 525 526 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag : 527 default_sort_mods->rflag; 528 529 sl->start_position = 0; 530 sl->sln = 256; 531 sl->sublevels = sort_malloc(slsz); 532 memset(sl->sublevels, 0, slsz); 533 534 for (size_t i = 0; i < sl->tosort_num; ++i) 535 place_item(sl, i); 536 537 if (sl->leaves_num > 1) { 538 if (keys_num > 1) { 539 if (sort_opts_vals.sflag) { 540 mergesort(sl->leaves, sl->leaves_num, 541 sizeof(struct sort_list_item *), 542 (int(*)(const void *, const void *)) list_coll); 543 } else { 544 qsort(sl->leaves, sl->leaves_num, 545 sizeof(struct sort_list_item *), 546 (int(*)(const void *, const void *)) list_coll); 547 } 548 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 549 qsort(sl->leaves, sl->leaves_num, 550 sizeof(struct sort_list_item *), 551 (int(*)(const void *, const void *)) list_coll_by_str_only); 552 } 553 } 554 555 if (!reverse_sort) { 556 memcpy(sl->tosort + sl->start_position, sl->leaves, 557 sl->leaves_num * sizeof(struct sort_list_item*)); 558 sl->start_position += sl->leaves_num; 559 sort_left_dec(sl->leaves_num); 560 561 for (size_t i = 0; i < sl->sln; ++i) { 562 slc = sl->sublevels[i]; 563 564 if (slc) { 565 slc->sorted = sl->tosort; 566 slc->start_position = sl->start_position; 567 sl->start_position += slc->tosort_num; 568 push_ls(slc); 569 sl->sublevels[i] = NULL; 570 } 571 } 572 573 } else { 574 size_t n; 575 576 for (size_t i = 0; i < sl->sln; ++i) { 577 578 n = sl->sln - i - 1; 579 slc = sl->sublevels[n]; 580 581 if (slc) { 582 slc->sorted = sl->tosort; 583 slc->start_position = sl->start_position; 584 sl->start_position += slc->tosort_num; 585 push_ls(slc); 586 sl->sublevels[n] = NULL; 587 } 588 } 589 590 memcpy(sl->tosort + sl->start_position, sl->leaves, 591 sl->leaves_num * sizeof(struct sort_list_item*)); 592 593 sort_left_dec(sl->leaves_num); 594 } 595 596 #if defined(SORT_THREADS) 597 if (nthreads < 2) { 598 #endif 599 run_sort_cycle_st(); 600 #if defined(SORT_THREADS) 601 } else { 602 size_t i; 603 604 for(i = 0; i < nthreads; ++i) { 605 pthread_attr_t attr; 606 pthread_t pth; 607 608 pthread_attr_init(&attr); 609 pthread_attr_setdetachstate(&attr, 610 PTHREAD_DETACHED); 611 612 for (;;) { 613 int res = pthread_create(&pth, &attr, 614 sort_thread, NULL); 615 if (res >= 0) 616 break; 617 if (errno == EAGAIN) { 618 pthread_yield(); 619 continue; 620 } 621 err(2, NULL); 622 } 623 624 pthread_attr_destroy(&attr); 625 } 626 627 for(i = 0; i < nthreads; ++i) 628 sem_wait(&mtsem); 629 } 630 #endif /* defined(SORT_THREADS) */ 631 } 632 633 static void 634 run_sort(struct sort_list_item **base, size_t nmemb) 635 { 636 struct sort_level *sl; 637 638 #if defined(SORT_THREADS) 639 size_t nthreads_save = nthreads; 640 if (nmemb < MT_SORT_THRESHOLD) 641 nthreads = 1; 642 643 if (nthreads > 1) { 644 pthread_mutexattr_t mattr; 645 646 pthread_mutexattr_init(&mattr); 647 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP); 648 649 pthread_mutex_init(&g_ls_mutex, &mattr); 650 pthread_mutex_init(&sort_left_mutex, &mattr); 651 652 pthread_mutexattr_destroy(&mattr); 653 654 sem_init(&mtsem, 0, 0); 655 656 } 657 #endif 658 659 sl = sort_malloc(sizeof(struct sort_level)); 660 memset(sl, 0, sizeof(struct sort_level)); 661 662 sl->tosort = base; 663 sl->tosort_num = nmemb; 664 sl->tosort_sz = nmemb; 665 666 #if defined(SORT_THREADS) 667 sort_left = nmemb; 668 #endif 669 670 run_top_sort_level(sl); 671 672 free_sort_level(sl); 673 674 #if defined(SORT_THREADS) 675 if (nthreads > 1) { 676 sem_destroy(&mtsem); 677 pthread_mutex_destroy(&g_ls_mutex); 678 pthread_mutex_destroy(&sort_left_mutex); 679 } 680 nthreads = nthreads_save; 681 #endif 682 } 683 684 void 685 rxsort(struct sort_list_item **base, size_t nmemb) 686 { 687 688 run_sort(base, nmemb); 689 } 690