usr.bin/sort/radixsort.c

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