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