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