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