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