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