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 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 }