usr.bin/sort/radixsort.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
   5  * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #include <sys/cdefs.h>
  31 __FBSDID("$FreeBSD$");
  32
  33 #include <errno.h>
  34 #include <err.h>
  35 #include <langinfo.h>
  36 #include <math.h>
  37 #if defined(SORT_THREADS)
  38 #include <pthread.h>
  39 #include <semaphore.h>
  40 #endif
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <wchar.h>
  44 #include <wctype.h>
  45 #include <unistd.h>
  46
  47 #include "coll.h"
  48 #include "radixsort.h"
  49
  50 #define DEFAULT_SORT_FUNC_RADIXSORT mergesort
  51
  52 #define TINY_NODE(sl) ((sl)->tosort_num < 65)
  53 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
  54
  55 /* are we sorting in reverse order ? */
  56 static bool reverse_sort;
  57
  58 /* sort sub-levels array size */
  59 static const size_t slsz = 256 * sizeof(struct sort_level*);
  60
  61 /* one sort level structure */
  62 struct sort_level
  63 {
  64         struct sort_level       **sublevels;
  65         struct sort_list_item   **leaves;
  66         struct sort_list_item   **sorted;
  67         struct sort_list_item   **tosort;
  68         size_t                    leaves_num;
  69         size_t                    leaves_sz;
  70         size_t                    level;
  71         size_t                    real_sln;
  72         size_t                    start_position;
  73         size_t                    sln;
  74         size_t                    tosort_num;
  75         size_t                    tosort_sz;
  76 };
  77
  78 /* stack of sort levels ready to be sorted */
  79 struct level_stack {
  80         struct level_stack       *next;
  81         struct sort_level        *sl;
  82 };
  83
  84 static struct level_stack *g_ls;
  85
  86 #if defined(SORT_THREADS)
  87 /* stack guarding mutex */
  88 static pthread_cond_t g_ls_cond;
  89 static pthread_mutex_t g_ls_mutex;
  90
  91 /* counter: how many items are left */
  92 static size_t sort_left;
  93 /* guarding mutex */
  94
  95 /* semaphore to count threads */
  96 static sem_t mtsem;
  97
  98 /*
  99  * Decrement items counter
 100  */
 101 static inline void
 102 sort_left_dec(size_t n)
 103 {
 104         pthread_mutex_lock(&g_ls_mutex);
 105         sort_left -= n;
 106         if (sort_left == 0 && nthreads > 1)
 107                 pthread_cond_broadcast(&g_ls_cond);
 108         pthread_mutex_unlock(&g_ls_mutex);
 109 }
 110
 111 /*
 112  * Do we have something to sort ?
 113  *
 114  * This routine does not need to be locked.
 115  */
 116 static inline bool
 117 have_sort_left(void)
 118 {
 119         bool ret;
 120
 121         ret = (sort_left > 0);
 122
 123         return (ret);
 124 }
 125
 126 #else
 127
 128 #define sort_left_dec(n)
 129
 130 #endif /* SORT_THREADS */
 131
 132 static void
 133 _push_ls(struct level_stack *ls)
 134 {
 135
 136         ls->next = g_ls;
 137         g_ls = ls;
 138 }
 139
 140 /*
 141  * Push sort level to the stack
 142  */
 143 static inline void
 144 push_ls(struct sort_level *sl)
 145 {
 146         struct level_stack *new_ls;
 147
 148         new_ls = sort_malloc(sizeof(struct level_stack));
 149         new_ls->sl = sl;
 150
 151 #if defined(SORT_THREADS)
 152         if (nthreads > 1) {
 153                 pthread_mutex_lock(&g_ls_mutex);
 154                 _push_ls(new_ls);
 155                 pthread_cond_signal(&g_ls_cond);
 156                 pthread_mutex_unlock(&g_ls_mutex);
 157         } else
 158 #endif
 159                 _push_ls(new_ls);
 160 }
 161
 162 /*
 163  * Pop sort level from the stack (single-threaded style)
 164  */
 165 static inline struct sort_level*
 166 pop_ls_st(void)
 167 {
 168         struct sort_level *sl;
 169
 170         if (g_ls) {
 171                 struct level_stack *saved_ls;
 172
 173                 sl = g_ls->sl;
 174                 saved_ls = g_ls;
 175                 g_ls = g_ls->next;
 176                 sort_free(saved_ls);
 177         } else
 178                 sl = NULL;
 179
 180         return (sl);
 181 }
 182
 183 #if defined(SORT_THREADS)
 184
 185 /*
 186  * Pop sort level from the stack (multi-threaded style)
 187  */
 188 static inline struct sort_level*
 189 pop_ls_mt(void)
 190 {
 191         struct level_stack *saved_ls;
 192         struct sort_level *sl;
 193
 194         pthread_mutex_lock(&g_ls_mutex);
 195
 196         for (;;) {
 197                 if (g_ls) {
 198                         sl = g_ls->sl;
 199                         saved_ls = g_ls;
 200                         g_ls = g_ls->next;
 201                         break;
 202                 }
 203                 sl = NULL;
 204                 saved_ls = NULL;
 205
 206                 if (have_sort_left() == 0)
 207                         break;
 208                 pthread_cond_wait(&g_ls_cond, &g_ls_mutex);
 209         }
 210
 211         pthread_mutex_unlock(&g_ls_mutex);
 212
 213         sort_free(saved_ls);
 214
 215         return (sl);
 216 }
 217
 218 #endif /* defined(SORT_THREADS) */
 219
 220 static void
 221 add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
 222 {
 223         struct sort_level *ssl;
 224
 225         ssl = sl->sublevels[indx];
 226
 227         if (ssl == NULL) {
 228                 ssl = sort_malloc(sizeof(struct sort_level));
 229                 memset(ssl, 0, sizeof(struct sort_level));
 230
 231                 ssl->level = sl->level + 1;
 232                 sl->sublevels[indx] = ssl;
 233
 234                 ++(sl->real_sln);
 235         }
 236
 237         if (++(ssl->tosort_num) > ssl->tosort_sz) {
 238                 ssl->tosort_sz = ssl->tosort_num + 128;
 239                 ssl->tosort = sort_realloc(ssl->tosort,
 240                     sizeof(struct sort_list_item*) * (ssl->tosort_sz));
 241         }
 242
 243         ssl->tosort[ssl->tosort_num - 1] = item;
 244 }
 245
 246 static inline void
 247 add_leaf(struct sort_level *sl, struct sort_list_item *item)
 248 {
 249
 250         if (++(sl->leaves_num) > sl->leaves_sz) {
 251                 sl->leaves_sz = sl->leaves_num + 128;
 252                 sl->leaves = sort_realloc(sl->leaves,
 253                     (sizeof(struct sort_list_item*) * (sl->leaves_sz)));
 254         }
 255         sl->leaves[sl->leaves_num - 1] = item;
 256 }
 257
 258 static inline int
 259 get_wc_index(struct sort_list_item *sli, size_t level)
 260 {
 261         const struct key_value *kv;
 262         const struct bwstring *bws;
 263
 264         kv = get_key_from_keys_array(&sli->ka, 0);
 265         bws = kv->k;
 266
 267         if ((BWSLEN(bws) > level))
 268                 return (unsigned char) BWS_GET(bws,level);
 269         return (-1);
 270 }
 271
 272 static void
 273 place_item(struct sort_level *sl, size_t item)
 274 {
 275         struct sort_list_item *sli;
 276         int c;
 277
 278         sli = sl->tosort[item];
 279         c = get_wc_index(sli, sl->level);
 280
 281         if (c == -1)
 282                 add_leaf(sl, sli);
 283         else
 284                 add_to_sublevel(sl, sli, c);
 285 }
 286
 287 static void
 288 free_sort_level(struct sort_level *sl)
 289 {
 290
 291         if (sl) {
 292                 if (sl->leaves)
 293                         sort_free(sl->leaves);
 294
 295                 if (sl->level > 0)
 296                         sort_free(sl->tosort);
 297
 298                 if (sl->sublevels) {
 299                         struct sort_level *slc;
 300                         size_t sln;
 301
 302                         sln = sl->sln;
 303
 304                         for (size_t i = 0; i < sln; ++i) {
 305                                 slc = sl->sublevels[i];
 306                                 if (slc)
 307                                         free_sort_level(slc);
 308                         }
 309
 310                         sort_free(sl->sublevels);
 311                 }
 312
 313                 sort_free(sl);
 314         }
 315 }
 316
 317 static void
 318 run_sort_level_next(struct sort_level *sl)
 319 {
 320         struct sort_level *slc;
 321         size_t i, sln, tosort_num;
 322
 323         if (sl->sublevels) {
 324                 sort_free(sl->sublevels);
 325                 sl->sublevels = NULL;
 326         }
 327
 328         switch (sl->tosort_num) {
 329         case 0:
 330                 goto end;
 331         case (1):
 332                 sl->sorted[sl->start_position] = sl->tosort[0];
 333                 sort_left_dec(1);
 334                 goto end;
 335         case (2):
 336                 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
 337                     sl->level) > 0) {
 338                         sl->sorted[sl->start_position++] = sl->tosort[1];
 339                         sl->sorted[sl->start_position] = sl->tosort[0];
 340                 } else {
 341                         sl->sorted[sl->start_position++] = sl->tosort[0];
 342                         sl->sorted[sl->start_position] = sl->tosort[1];
 343                 }
 344                 sort_left_dec(2);
 345
 346                 goto end;
 347         default:
 348                 if (TINY_NODE(sl) || (sl->level > 15)) {
 349                         listcoll_t func;
 350
 351                         func = get_list_call_func(sl->level);
 352
 353                         sl->leaves = sl->tosort;
 354                         sl->leaves_num = sl->tosort_num;
 355                         sl->leaves_sz = sl->leaves_num;
 356                         sl->leaves = sort_realloc(sl->leaves,
 357                             (sizeof(struct sort_list_item *) *
 358                             (sl->leaves_sz)));
 359                         sl->tosort = NULL;
 360                         sl->tosort_num = 0;
 361                         sl->tosort_sz = 0;
 362                         sl->sln = 0;
 363                         sl->real_sln = 0;
 364                         if (sort_opts_vals.sflag) {
 365                                 if (mergesort(sl->leaves, sl->leaves_num,
 366                                     sizeof(struct sort_list_item *),
 367                                     (int(*)(const void *, const void *)) func) == -1)
 368                                         /* NOTREACHED */
 369                                         err(2, "Radix sort error 3");
 370                         } else
 371                                 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
 372                                     sizeof(struct sort_list_item *),
 373                                     (int(*)(const void *, const void *)) func);
 374
 375                         memcpy(sl->sorted + sl->start_position,
 376                             sl->leaves, sl->leaves_num *
 377                             sizeof(struct sort_list_item*));
 378
 379                         sort_left_dec(sl->leaves_num);
 380
 381                         goto end;
 382                 } else {
 383                         sl->tosort_sz = sl->tosort_num;
 384                         sl->tosort = sort_realloc(sl->tosort,
 385                             sizeof(struct sort_list_item*) * (sl->tosort_sz));
 386                 }
 387         }
 388
 389         sl->sln = 256;
 390         sl->sublevels = sort_malloc(slsz);
 391         memset(sl->sublevels, 0, slsz);
 392
 393         sl->real_sln = 0;
 394
 395         tosort_num = sl->tosort_num;
 396         for (i = 0; i < tosort_num; ++i)
 397                 place_item(sl, i);
 398
 399         sort_free(sl->tosort);
 400         sl->tosort = NULL;
 401         sl->tosort_num = 0;
 402         sl->tosort_sz = 0;
 403
 404         if (sl->leaves_num > 1) {
 405                 if (keys_num > 1) {
 406                         if (sort_opts_vals.sflag) {
 407                                 mergesort(sl->leaves, sl->leaves_num,
 408                                     sizeof(struct sort_list_item *),
 409                                     (int(*)(const void *, const void *)) list_coll);
 410                         } else {
 411                                 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
 412                                     sizeof(struct sort_list_item *),
 413                                     (int(*)(const void *, const void *)) list_coll);
 414                         }
 415                 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
 416                         DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
 417                             sizeof(struct sort_list_item *),
 418                             (int(*)(const void *, const void *)) list_coll_by_str_only);
 419                 }
 420         }
 421
 422         sl->leaves_sz = sl->leaves_num;
 423         sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
 424             (sl->leaves_sz)));
 425
 426         if (!reverse_sort) {
 427                 memcpy(sl->sorted + sl->start_position, sl->leaves,
 428                     sl->leaves_num * sizeof(struct sort_list_item*));
 429                 sl->start_position += sl->leaves_num;
 430                 sort_left_dec(sl->leaves_num);
 431
 432                 sort_free(sl->leaves);
 433                 sl->leaves = NULL;
 434                 sl->leaves_num = 0;
 435                 sl->leaves_sz = 0;
 436
 437                 sln = sl->sln;
 438
 439                 for (i = 0; i < sln; ++i) {
 440                         slc = sl->sublevels[i];
 441
 442                         if (slc) {
 443                                 slc->sorted = sl->sorted;
 444                                 slc->start_position = sl->start_position;
 445                                 sl->start_position += slc->tosort_num;
 446                                 if (SMALL_NODE(slc))
 447                                         run_sort_level_next(slc);
 448                                 else
 449                                         push_ls(slc);
 450                                 sl->sublevels[i] = NULL;
 451                         }
 452                 }
 453
 454         } else {
 455                 size_t n;
 456
 457                 sln = sl->sln;
 458
 459                 for (i = 0; i < sln; ++i) {
 460                         n = sln - i - 1;
 461                         slc = sl->sublevels[n];
 462
 463                         if (slc) {
 464                                 slc->sorted = sl->sorted;
 465                                 slc->start_position = sl->start_position;
 466                                 sl->start_position += slc->tosort_num;
 467                                 if (SMALL_NODE(slc))
 468                                         run_sort_level_next(slc);
 469                                 else
 470                                         push_ls(slc);
 471                                 sl->sublevels[n] = NULL;
 472                         }
 473                 }
 474
 475                 memcpy(sl->sorted + sl->start_position, sl->leaves,
 476                     sl->leaves_num * sizeof(struct sort_list_item*));
 477                 sort_left_dec(sl->leaves_num);
 478         }
 479
 480 end:
 481         free_sort_level(sl);
 482 }
 483
 484 /*
 485  * Single-threaded sort cycle
 486  */
 487 static void
 488 run_sort_cycle_st(void)
 489 {
 490         struct sort_level *slc;
 491
 492         for (;;) {
 493                 slc = pop_ls_st();
 494                 if (slc == NULL) {
 495                         break;
 496                 }
 497                 run_sort_level_next(slc);
 498         }
 499 }
 500
 501 #if defined(SORT_THREADS)
 502
 503 /*
 504  * Multi-threaded sort cycle
 505  */
 506 static void
 507 run_sort_cycle_mt(void)
 508 {
 509         struct sort_level *slc;
 510
 511         for (;;) {
 512                 slc = pop_ls_mt();
 513                 if (slc == NULL)
 514                         break;
 515                 run_sort_level_next(slc);
 516         }
 517 }
 518
 519 /*
 520  * Sort cycle thread (in multi-threaded mode)
 521  */
 522 static void*
 523 sort_thread(void* arg)
 524 {
 525         run_sort_cycle_mt();
 526         sem_post(&mtsem);
 527
 528         return (arg);
 529 }
 530
 531 #endif /* defined(SORT_THREADS) */
 532
 533 static void
 534 run_top_sort_level(struct sort_level *sl)
 535 {
 536         struct sort_level *slc;
 537
 538         reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
 539             default_sort_mods->rflag;
 540
 541         sl->start_position = 0;
 542         sl->sln = 256;
 543         sl->sublevels = sort_malloc(slsz);
 544         memset(sl->sublevels, 0, slsz);
 545
 546         for (size_t i = 0; i < sl->tosort_num; ++i)
 547                 place_item(sl, i);
 548
 549         if (sl->leaves_num > 1) {
 550                 if (keys_num > 1) {
 551                         if (sort_opts_vals.sflag) {
 552                                 mergesort(sl->leaves, sl->leaves_num,
 553                                     sizeof(struct sort_list_item *),
 554                                     (int(*)(const void *, const void *)) list_coll);
 555                         } else {
 556                                 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
 557                                     sizeof(struct sort_list_item *),
 558                                     (int(*)(const void *, const void *)) list_coll);
 559                         }
 560                 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
 561                         DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
 562                             sizeof(struct sort_list_item *),
 563                             (int(*)(const void *, const void *)) list_coll_by_str_only);
 564                 }
 565         }
 566
 567         if (!reverse_sort) {
 568                 memcpy(sl->tosort + sl->start_position, sl->leaves,
 569                     sl->leaves_num * sizeof(struct sort_list_item*));
 570                 sl->start_position += sl->leaves_num;
 571                 sort_left_dec(sl->leaves_num);
 572
 573                 for (size_t i = 0; i < sl->sln; ++i) {
 574                         slc = sl->sublevels[i];
 575
 576                         if (slc) {
 577                                 slc->sorted = sl->tosort;
 578                                 slc->start_position = sl->start_position;
 579                                 sl->start_position += slc->tosort_num;
 580                                 push_ls(slc);
 581                                 sl->sublevels[i] = NULL;
 582                         }
 583                 }
 584
 585         } else {
 586                 size_t n;
 587
 588                 for (size_t i = 0; i < sl->sln; ++i) {
 589
 590                         n = sl->sln - i - 1;
 591                         slc = sl->sublevels[n];
 592
 593                         if (slc) {
 594                                 slc->sorted = sl->tosort;
 595                                 slc->start_position = sl->start_position;
 596                                 sl->start_position += slc->tosort_num;
 597                                 push_ls(slc);
 598                                 sl->sublevels[n] = NULL;
 599                         }
 600                 }
 601
 602                 memcpy(sl->tosort + sl->start_position, sl->leaves,
 603                     sl->leaves_num * sizeof(struct sort_list_item*));
 604
 605                 sort_left_dec(sl->leaves_num);
 606         }
 607
 608 #if defined(SORT_THREADS)
 609         if (nthreads < 2) {
 610 #endif
 611                 run_sort_cycle_st();
 612 #if defined(SORT_THREADS)
 613         } else {
 614                 size_t i;
 615
 616                 for(i = 0; i < nthreads; ++i) {
 617                         pthread_attr_t attr;
 618                         pthread_t pth;
 619
 620                         pthread_attr_init(&attr);
 621                         pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
 622
 623                         for (;;) {
 624                                 int res = pthread_create(&pth, &attr,
 625                                     sort_thread, NULL);
 626                                 if (res >= 0)
 627                                         break;
 628                                 if (errno == EAGAIN) {
 629                                         pthread_yield();
 630                                         continue;
 631                                 }
 632                                 err(2, NULL);
 633                         }
 634
 635                         pthread_attr_destroy(&attr);
 636                 }
 637
 638                 for (i = 0; i < nthreads; ++i)
 639                         sem_wait(&mtsem);
 640         }
 641 #endif /* defined(SORT_THREADS) */
 642 }
 643
 644 static void
 645 run_sort(struct sort_list_item **base, size_t nmemb)
 646 {
 647         struct sort_level *sl;
 648
 649 #if defined(SORT_THREADS)
 650         size_t nthreads_save = nthreads;
 651         if (nmemb < MT_SORT_THRESHOLD)
 652                 nthreads = 1;
 653
 654         if (nthreads > 1) {
 655                 pthread_mutexattr_t mattr;
 656
 657                 pthread_mutexattr_init(&mattr);
 658                 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
 659
 660                 pthread_mutex_init(&g_ls_mutex, &mattr);
 661                 pthread_cond_init(&g_ls_cond, NULL);
 662
 663                 pthread_mutexattr_destroy(&mattr);
 664
 665                 sem_init(&mtsem, 0, 0);
 666
 667         }
 668 #endif
 669
 670         sl = sort_malloc(sizeof(struct sort_level));
 671         memset(sl, 0, sizeof(struct sort_level));
 672
 673         sl->tosort = base;
 674         sl->tosort_num = nmemb;
 675         sl->tosort_sz = nmemb;
 676
 677 #if defined(SORT_THREADS)
 678         sort_left = nmemb;
 679 #endif
 680
 681         run_top_sort_level(sl);
 682
 683         free_sort_level(sl);
 684
 685 #if defined(SORT_THREADS)
 686         if (nthreads > 1) {
 687                 sem_destroy(&mtsem);
 688                 pthread_mutex_destroy(&g_ls_mutex);
 689         }
 690         nthreads = nthreads_save;
 691 #endif
 692 }
 693
 694 void
 695 rxsort(struct sort_list_item **base, size_t nmemb)
 696 {
 697
 698         run_sort(base, nmemb);
 699 }