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