1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 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_calloc(1, sizeof(struct sort_level)); 229 230 ssl->level = sl->level + 1; 231 sl->sublevels[indx] = ssl; 232 233 ++(sl->real_sln); 234 } 235 236 if (++(ssl->tosort_num) > ssl->tosort_sz) { 237 ssl->tosort_sz = ssl->tosort_num + 128; 238 ssl->tosort = sort_realloc(ssl->tosort, 239 sizeof(struct sort_list_item*) * (ssl->tosort_sz)); 240 } 241 242 ssl->tosort[ssl->tosort_num - 1] = item; 243 } 244 245 static inline void 246 add_leaf(struct sort_level *sl, struct sort_list_item *item) 247 { 248 249 if (++(sl->leaves_num) > sl->leaves_sz) { 250 sl->leaves_sz = sl->leaves_num + 128; 251 sl->leaves = sort_realloc(sl->leaves, 252 (sizeof(struct sort_list_item*) * (sl->leaves_sz))); 253 } 254 sl->leaves[sl->leaves_num - 1] = item; 255 } 256 257 static inline int 258 get_wc_index(struct sort_list_item *sli, size_t level) 259 { 260 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t); 261 const struct key_value *kv; 262 const struct bwstring *bws; 263 264 kv = get_key_from_keys_array(&sli->ka, 0); 265 bws = kv->k; 266 267 if ((BWSLEN(bws) * wcfact > level)) { 268 wchar_t res; 269 270 /* 271 * Sort wchar strings a byte at a time, rather than a single 272 * byte from each wchar. 273 */ 274 res = (wchar_t)BWS_GET(bws, level / wcfact); 275 /* Sort most-significant byte first. */ 276 if (level % wcfact < wcfact - 1) 277 res = (res >> (8 * (wcfact - 1 - (level % wcfact)))); 278 279 return (res & 0xff); 280 } 281 282 return (-1); 283 } 284 285 static void 286 place_item(struct sort_level *sl, size_t item) 287 { 288 struct sort_list_item *sli; 289 int c; 290 291 sli = sl->tosort[item]; 292 c = get_wc_index(sli, sl->level); 293 294 if (c == -1) 295 add_leaf(sl, sli); 296 else 297 add_to_sublevel(sl, sli, c); 298 } 299 300 static void 301 free_sort_level(struct sort_level *sl) 302 { 303 304 if (sl) { 305 if (sl->leaves) 306 sort_free(sl->leaves); 307 308 if (sl->level > 0) 309 sort_free(sl->tosort); 310 311 if (sl->sublevels) { 312 struct sort_level *slc; 313 size_t sln; 314 315 sln = sl->sln; 316 317 for (size_t i = 0; i < sln; ++i) { 318 slc = sl->sublevels[i]; 319 if (slc) 320 free_sort_level(slc); 321 } 322 323 sort_free(sl->sublevels); 324 } 325 326 sort_free(sl); 327 } 328 } 329 330 static void 331 run_sort_level_next(struct sort_level *sl) 332 { 333 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t); 334 struct sort_level *slc; 335 size_t i, sln, tosort_num; 336 337 if (sl->sublevels) { 338 sort_free(sl->sublevels); 339 sl->sublevels = NULL; 340 } 341 342 switch (sl->tosort_num) { 343 case 0: 344 goto end; 345 case (1): 346 sl->sorted[sl->start_position] = sl->tosort[0]; 347 sort_left_dec(1); 348 goto end; 349 case (2): 350 /* 351 * Radixsort only processes a single byte at a time. In wchar 352 * mode, this can be a subset of the length of a character. 353 * list_coll_offset() offset is in units of wchar, not bytes. 354 * So to calculate the offset, we must divide by 355 * sizeof(wchar_t) and round down to the index of the first 356 * character this level references. 357 */ 358 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]), 359 sl->level / wcfact) > 0) { 360 sl->sorted[sl->start_position++] = sl->tosort[1]; 361 sl->sorted[sl->start_position] = sl->tosort[0]; 362 } else { 363 sl->sorted[sl->start_position++] = sl->tosort[0]; 364 sl->sorted[sl->start_position] = sl->tosort[1]; 365 } 366 sort_left_dec(2); 367 368 goto end; 369 default: 370 if (TINY_NODE(sl) || (sl->level > 15)) { 371 listcoll_t func; 372 373 /* 374 * Collate comparison offset is in units of 375 * character-width, so we must divide the level (bytes) 376 * by operating character width (wchar_t or char). See 377 * longer comment above. 378 */ 379 func = get_list_call_func(sl->level / wcfact); 380 381 sl->leaves = sl->tosort; 382 sl->leaves_num = sl->tosort_num; 383 sl->leaves_sz = sl->leaves_num; 384 sl->leaves = sort_realloc(sl->leaves, 385 (sizeof(struct sort_list_item *) * 386 (sl->leaves_sz))); 387 sl->tosort = NULL; 388 sl->tosort_num = 0; 389 sl->tosort_sz = 0; 390 sl->sln = 0; 391 sl->real_sln = 0; 392 if (sort_opts_vals.sflag) { 393 if (mergesort(sl->leaves, sl->leaves_num, 394 sizeof(struct sort_list_item *), 395 (int(*)(const void *, const void *)) func) == -1) 396 /* NOTREACHED */ 397 err(2, "Radix sort error 3"); 398 } else 399 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 400 sizeof(struct sort_list_item *), 401 (int(*)(const void *, const void *)) func); 402 403 memcpy(sl->sorted + sl->start_position, 404 sl->leaves, sl->leaves_num * 405 sizeof(struct sort_list_item*)); 406 407 sort_left_dec(sl->leaves_num); 408 409 goto end; 410 } else { 411 sl->tosort_sz = sl->tosort_num; 412 sl->tosort = sort_realloc(sl->tosort, 413 sizeof(struct sort_list_item*) * (sl->tosort_sz)); 414 } 415 } 416 417 sl->sln = 256; 418 sl->sublevels = sort_calloc(1, slsz); 419 420 sl->real_sln = 0; 421 422 tosort_num = sl->tosort_num; 423 for (i = 0; i < tosort_num; ++i) 424 place_item(sl, i); 425 426 sort_free(sl->tosort); 427 sl->tosort = NULL; 428 sl->tosort_num = 0; 429 sl->tosort_sz = 0; 430 431 if (sl->leaves_num > 1) { 432 if (keys_num > 1) { 433 if (sort_opts_vals.sflag) { 434 mergesort(sl->leaves, sl->leaves_num, 435 sizeof(struct sort_list_item *), 436 (int(*)(const void *, const void *)) list_coll); 437 } else { 438 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 439 sizeof(struct sort_list_item *), 440 (int(*)(const void *, const void *)) list_coll); 441 } 442 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 443 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 444 sizeof(struct sort_list_item *), 445 (int(*)(const void *, const void *)) list_coll_by_str_only); 446 } 447 } 448 449 sl->leaves_sz = sl->leaves_num; 450 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) * 451 (sl->leaves_sz))); 452 453 if (!reverse_sort) { 454 memcpy(sl->sorted + sl->start_position, sl->leaves, 455 sl->leaves_num * sizeof(struct sort_list_item*)); 456 sl->start_position += sl->leaves_num; 457 sort_left_dec(sl->leaves_num); 458 459 sort_free(sl->leaves); 460 sl->leaves = NULL; 461 sl->leaves_num = 0; 462 sl->leaves_sz = 0; 463 464 sln = sl->sln; 465 466 for (i = 0; i < sln; ++i) { 467 slc = sl->sublevels[i]; 468 469 if (slc) { 470 slc->sorted = sl->sorted; 471 slc->start_position = sl->start_position; 472 sl->start_position += slc->tosort_num; 473 if (SMALL_NODE(slc)) 474 run_sort_level_next(slc); 475 else 476 push_ls(slc); 477 sl->sublevels[i] = NULL; 478 } 479 } 480 481 } else { 482 size_t n; 483 484 sln = sl->sln; 485 486 for (i = 0; i < sln; ++i) { 487 n = sln - i - 1; 488 slc = sl->sublevels[n]; 489 490 if (slc) { 491 slc->sorted = sl->sorted; 492 slc->start_position = sl->start_position; 493 sl->start_position += slc->tosort_num; 494 if (SMALL_NODE(slc)) 495 run_sort_level_next(slc); 496 else 497 push_ls(slc); 498 sl->sublevels[n] = NULL; 499 } 500 } 501 502 memcpy(sl->sorted + sl->start_position, sl->leaves, 503 sl->leaves_num * sizeof(struct sort_list_item*)); 504 sort_left_dec(sl->leaves_num); 505 } 506 507 end: 508 free_sort_level(sl); 509 } 510 511 /* 512 * Single-threaded sort cycle 513 */ 514 static void 515 run_sort_cycle_st(void) 516 { 517 struct sort_level *slc; 518 519 for (;;) { 520 slc = pop_ls_st(); 521 if (slc == NULL) { 522 break; 523 } 524 run_sort_level_next(slc); 525 } 526 } 527 528 #if defined(SORT_THREADS) 529 530 /* 531 * Multi-threaded sort cycle 532 */ 533 static void 534 run_sort_cycle_mt(void) 535 { 536 struct sort_level *slc; 537 538 for (;;) { 539 slc = pop_ls_mt(); 540 if (slc == NULL) 541 break; 542 run_sort_level_next(slc); 543 } 544 } 545 546 /* 547 * Sort cycle thread (in multi-threaded mode) 548 */ 549 static void* 550 sort_thread(void* arg) 551 { 552 run_sort_cycle_mt(); 553 sem_post(&mtsem); 554 555 return (arg); 556 } 557 558 #endif /* defined(SORT_THREADS) */ 559 560 static void 561 run_top_sort_level(struct sort_level *sl) 562 { 563 struct sort_level *slc; 564 565 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag : 566 default_sort_mods->rflag; 567 568 sl->start_position = 0; 569 sl->sln = 256; 570 sl->sublevels = sort_calloc(1, slsz); 571 572 for (size_t i = 0; i < sl->tosort_num; ++i) 573 place_item(sl, i); 574 575 if (sl->leaves_num > 1) { 576 if (keys_num > 1) { 577 if (sort_opts_vals.sflag) { 578 mergesort(sl->leaves, sl->leaves_num, 579 sizeof(struct sort_list_item *), 580 (int(*)(const void *, const void *)) list_coll); 581 } else { 582 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 583 sizeof(struct sort_list_item *), 584 (int(*)(const void *, const void *)) list_coll); 585 } 586 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 587 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 588 sizeof(struct sort_list_item *), 589 (int(*)(const void *, const void *)) list_coll_by_str_only); 590 } 591 } 592 593 if (!reverse_sort) { 594 memcpy(sl->tosort + sl->start_position, sl->leaves, 595 sl->leaves_num * sizeof(struct sort_list_item*)); 596 sl->start_position += sl->leaves_num; 597 sort_left_dec(sl->leaves_num); 598 599 for (size_t i = 0; i < sl->sln; ++i) { 600 slc = sl->sublevels[i]; 601 602 if (slc) { 603 slc->sorted = sl->tosort; 604 slc->start_position = sl->start_position; 605 sl->start_position += slc->tosort_num; 606 push_ls(slc); 607 sl->sublevels[i] = NULL; 608 } 609 } 610 611 } else { 612 size_t n; 613 614 for (size_t i = 0; i < sl->sln; ++i) { 615 616 n = sl->sln - i - 1; 617 slc = sl->sublevels[n]; 618 619 if (slc) { 620 slc->sorted = sl->tosort; 621 slc->start_position = sl->start_position; 622 sl->start_position += slc->tosort_num; 623 push_ls(slc); 624 sl->sublevels[n] = NULL; 625 } 626 } 627 628 memcpy(sl->tosort + sl->start_position, sl->leaves, 629 sl->leaves_num * sizeof(struct sort_list_item*)); 630 631 sort_left_dec(sl->leaves_num); 632 } 633 634 #if defined(SORT_THREADS) 635 if (nthreads < 2) { 636 #endif 637 run_sort_cycle_st(); 638 #if defined(SORT_THREADS) 639 } else { 640 size_t i; 641 642 for(i = 0; i < nthreads; ++i) { 643 pthread_attr_t attr; 644 pthread_t pth; 645 646 pthread_attr_init(&attr); 647 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED); 648 649 for (;;) { 650 int res = pthread_create(&pth, &attr, 651 sort_thread, NULL); 652 if (res >= 0) 653 break; 654 if (errno == EAGAIN) { 655 pthread_yield(); 656 continue; 657 } 658 err(2, NULL); 659 } 660 661 pthread_attr_destroy(&attr); 662 } 663 664 for (i = 0; i < nthreads; ++i) 665 sem_wait(&mtsem); 666 } 667 #endif /* defined(SORT_THREADS) */ 668 } 669 670 static void 671 run_sort(struct sort_list_item **base, size_t nmemb) 672 { 673 struct sort_level *sl; 674 675 #if defined(SORT_THREADS) 676 size_t nthreads_save = nthreads; 677 if (nmemb < MT_SORT_THRESHOLD) 678 nthreads = 1; 679 680 if (nthreads > 1) { 681 pthread_mutexattr_t mattr; 682 683 pthread_mutexattr_init(&mattr); 684 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP); 685 686 pthread_mutex_init(&g_ls_mutex, &mattr); 687 pthread_cond_init(&g_ls_cond, NULL); 688 689 pthread_mutexattr_destroy(&mattr); 690 691 sem_init(&mtsem, 0, 0); 692 693 } 694 #endif 695 696 sl = sort_calloc(1, sizeof(struct sort_level)); 697 698 sl->tosort = base; 699 sl->tosort_num = nmemb; 700 sl->tosort_sz = nmemb; 701 702 #if defined(SORT_THREADS) 703 sort_left = nmemb; 704 #endif 705 706 run_top_sort_level(sl); 707 708 free_sort_level(sl); 709 710 #if defined(SORT_THREADS) 711 if (nthreads > 1) { 712 sem_destroy(&mtsem); 713 pthread_mutex_destroy(&g_ls_mutex); 714 } 715 nthreads = nthreads_save; 716 #endif 717 } 718 719 void 720 rxsort(struct sort_list_item **base, size_t nmemb) 721 { 722 723 run_sort(base, nmemb); 724 } 725