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