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