1235267Sgabor/*- 2251245Sgabor * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com> 3235267Sgabor * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org> 4235267Sgabor * All rights reserved. 5235267Sgabor * 6235267Sgabor * Redistribution and use in source and binary forms, with or without 7235267Sgabor * modification, are permitted provided that the following conditions 8235267Sgabor * are met: 9235267Sgabor * 1. Redistributions of source code must retain the above copyright 10235267Sgabor * notice, this list of conditions and the following disclaimer. 11235267Sgabor * 2. Redistributions in binary form must reproduce the above copyright 12235267Sgabor * notice, this list of conditions and the following disclaimer in the 13235267Sgabor * documentation and/or other materials provided with the distribution. 14235267Sgabor * 15235267Sgabor * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16235267Sgabor * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17235267Sgabor * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18235267Sgabor * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19235267Sgabor * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20235267Sgabor * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21235267Sgabor * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22235267Sgabor * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23235267Sgabor * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24235267Sgabor * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25235267Sgabor * SUCH DAMAGE. 26235267Sgabor */ 27235267Sgabor 28235267Sgabor#include <sys/cdefs.h> 29235267Sgabor__FBSDID("$FreeBSD: stable/10/usr.bin/sort/radixsort.c 318152 2017-05-10 20:29:01Z marius $"); 30235267Sgabor 31235267Sgabor#include <errno.h> 32235267Sgabor#include <err.h> 33235267Sgabor#include <langinfo.h> 34235267Sgabor#include <math.h> 35235267Sgabor#if defined(SORT_THREADS) 36235267Sgabor#include <pthread.h> 37235267Sgabor#include <semaphore.h> 38235267Sgabor#endif 39235267Sgabor#include <stdlib.h> 40235267Sgabor#include <string.h> 41235267Sgabor#include <wchar.h> 42235267Sgabor#include <wctype.h> 43235267Sgabor#include <unistd.h> 44235267Sgabor 45235267Sgabor#include "coll.h" 46235267Sgabor#include "radixsort.h" 47235267Sgabor 48238108Sgabor#define DEFAULT_SORT_FUNC_RADIXSORT mergesort 49238108Sgabor 50235267Sgabor#define TINY_NODE(sl) ((sl)->tosort_num < 65) 51235267Sgabor#define SMALL_NODE(sl) ((sl)->tosort_num < 5) 52235267Sgabor 53235267Sgabor/* are we sorting in reverse order ? */ 54235435Sgaborstatic bool reverse_sort; 55235267Sgabor 56235267Sgabor/* sort sub-levels array size */ 57235267Sgaborstatic const size_t slsz = 256 * sizeof(struct sort_level*); 58235267Sgabor 59235267Sgabor/* one sort level structure */ 60235267Sgaborstruct sort_level 61235267Sgabor{ 62235267Sgabor struct sort_level **sublevels; 63235267Sgabor struct sort_list_item **leaves; 64235267Sgabor struct sort_list_item **sorted; 65235267Sgabor struct sort_list_item **tosort; 66235267Sgabor size_t leaves_num; 67235267Sgabor size_t leaves_sz; 68235267Sgabor size_t level; 69235267Sgabor size_t real_sln; 70235267Sgabor size_t start_position; 71235267Sgabor size_t sln; 72235267Sgabor size_t tosort_num; 73235267Sgabor size_t tosort_sz; 74235267Sgabor}; 75235267Sgabor 76235267Sgabor/* stack of sort levels ready to be sorted */ 77235267Sgaborstruct level_stack { 78235267Sgabor struct level_stack *next; 79235267Sgabor struct sort_level *sl; 80235267Sgabor}; 81235267Sgabor 82235435Sgaborstatic struct level_stack *g_ls; 83235267Sgabor 84235267Sgabor#if defined(SORT_THREADS) 85235267Sgabor/* stack guarding mutex */ 86313321Spfgstatic pthread_cond_t g_ls_cond; 87235267Sgaborstatic pthread_mutex_t g_ls_mutex; 88235267Sgabor 89235267Sgabor/* counter: how many items are left */ 90235435Sgaborstatic size_t sort_left; 91235267Sgabor/* guarding mutex */ 92235267Sgabor 93235267Sgabor/* semaphore to count threads */ 94235267Sgaborstatic sem_t mtsem; 95235267Sgabor 96235267Sgabor/* 97235267Sgabor * Decrement items counter 98235267Sgabor */ 99235267Sgaborstatic inline void 100235267Sgaborsort_left_dec(size_t n) 101235267Sgabor{ 102313321Spfg pthread_mutex_lock(&g_ls_mutex); 103235267Sgabor sort_left -= n; 104313321Spfg if (sort_left == 0 && nthreads > 1) 105313321Spfg pthread_cond_broadcast(&g_ls_cond); 106313321Spfg pthread_mutex_unlock(&g_ls_mutex); 107235267Sgabor} 108235267Sgabor 109235267Sgabor/* 110235267Sgabor * Do we have something to sort ? 111313321Spfg * 112313321Spfg * This routine does not need to be locked. 113235267Sgabor */ 114235267Sgaborstatic inline bool 115235267Sgaborhave_sort_left(void) 116235267Sgabor{ 117235267Sgabor bool ret; 118235267Sgabor 119235267Sgabor ret = (sort_left > 0); 120313321Spfg 121235267Sgabor return (ret); 122235267Sgabor} 123235267Sgabor 124235267Sgabor#else 125235267Sgabor 126235267Sgabor#define sort_left_dec(n) 127235267Sgabor 128235267Sgabor#endif /* SORT_THREADS */ 129235267Sgabor 130235267Sgabor/* 131235267Sgabor * Push sort level to the stack 132235267Sgabor */ 133235267Sgaborstatic inline void 134235267Sgaborpush_ls(struct sort_level* sl) 135235267Sgabor{ 136235267Sgabor struct level_stack *new_ls; 137235267Sgabor 138235267Sgabor new_ls = sort_malloc(sizeof(struct level_stack)); 139235267Sgabor new_ls->sl = sl; 140235267Sgabor 141235267Sgabor#if defined(SORT_THREADS) 142235267Sgabor if (nthreads > 1) 143235267Sgabor pthread_mutex_lock(&g_ls_mutex); 144235267Sgabor#endif 145235267Sgabor 146235267Sgabor new_ls->next = g_ls; 147235267Sgabor g_ls = new_ls; 148235267Sgabor 149235267Sgabor#if defined(SORT_THREADS) 150235267Sgabor if (nthreads > 1) 151313321Spfg pthread_cond_signal(&g_ls_cond); 152313321Spfg#endif 153313321Spfg 154313321Spfg#if defined(SORT_THREADS) 155313321Spfg if (nthreads > 1) 156235267Sgabor pthread_mutex_unlock(&g_ls_mutex); 157235267Sgabor#endif 158235267Sgabor} 159235267Sgabor 160235267Sgabor/* 161235267Sgabor * Pop sort level from the stack (single-threaded style) 162235267Sgabor */ 163235267Sgaborstatic inline struct sort_level* 164235267Sgaborpop_ls_st(void) 165235267Sgabor{ 166235267Sgabor struct sort_level *sl; 167235267Sgabor 168235267Sgabor if (g_ls) { 169235267Sgabor struct level_stack *saved_ls; 170235267Sgabor 171235267Sgabor sl = g_ls->sl; 172235267Sgabor saved_ls = g_ls; 173235267Sgabor g_ls = g_ls->next; 174235267Sgabor sort_free(saved_ls); 175235267Sgabor } else 176235267Sgabor sl = NULL; 177235267Sgabor 178235267Sgabor return (sl); 179235267Sgabor} 180235267Sgabor 181259853Sdim#if defined(SORT_THREADS) 182259853Sdim 183235267Sgabor/* 184235267Sgabor * Pop sort level from the stack (multi-threaded style) 185235267Sgabor */ 186235267Sgaborstatic inline struct sort_level* 187235267Sgaborpop_ls_mt(void) 188235267Sgabor{ 189235267Sgabor struct level_stack *saved_ls; 190235267Sgabor struct sort_level *sl; 191235267Sgabor 192235267Sgabor pthread_mutex_lock(&g_ls_mutex); 193235267Sgabor 194313321Spfg for (;;) { 195313321Spfg if (g_ls) { 196313321Spfg sl = g_ls->sl; 197313321Spfg saved_ls = g_ls; 198313321Spfg g_ls = g_ls->next; 199313321Spfg break; 200313321Spfg } 201235267Sgabor sl = NULL; 202235267Sgabor saved_ls = NULL; 203313321Spfg 204313321Spfg if (have_sort_left() == 0) 205313321Spfg break; 206313321Spfg pthread_cond_wait(&g_ls_cond, &g_ls_mutex); 207235267Sgabor } 208235267Sgabor 209235267Sgabor pthread_mutex_unlock(&g_ls_mutex); 210235267Sgabor 211235267Sgabor sort_free(saved_ls); 212235267Sgabor 213235267Sgabor return (sl); 214235267Sgabor} 215235267Sgabor 216259853Sdim#endif /* defined(SORT_THREADS) */ 217259853Sdim 218235267Sgaborstatic void 219242430Sgaboradd_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx) 220235267Sgabor{ 221235267Sgabor struct sort_level *ssl; 222235267Sgabor 223235267Sgabor ssl = sl->sublevels[indx]; 224235267Sgabor 225235267Sgabor if (ssl == NULL) { 226235267Sgabor ssl = sort_malloc(sizeof(struct sort_level)); 227235267Sgabor memset(ssl, 0, sizeof(struct sort_level)); 228235267Sgabor 229235267Sgabor ssl->level = sl->level + 1; 230235267Sgabor sl->sublevels[indx] = ssl; 231235267Sgabor 232235267Sgabor ++(sl->real_sln); 233235267Sgabor } 234235267Sgabor 235235267Sgabor if (++(ssl->tosort_num) > ssl->tosort_sz) { 236235267Sgabor ssl->tosort_sz = ssl->tosort_num + 128; 237235267Sgabor ssl->tosort = sort_realloc(ssl->tosort, 238235267Sgabor sizeof(struct sort_list_item*) * (ssl->tosort_sz)); 239235267Sgabor } 240235267Sgabor 241235267Sgabor ssl->tosort[ssl->tosort_num - 1] = item; 242235267Sgabor} 243235267Sgabor 244235267Sgaborstatic inline void 245235267Sgaboradd_leaf(struct sort_level *sl, struct sort_list_item *item) 246235267Sgabor{ 247235267Sgabor 248235267Sgabor if (++(sl->leaves_num) > sl->leaves_sz) { 249235267Sgabor sl->leaves_sz = sl->leaves_num + 128; 250235267Sgabor sl->leaves = sort_realloc(sl->leaves, 251235267Sgabor (sizeof(struct sort_list_item*) * (sl->leaves_sz))); 252235267Sgabor } 253235267Sgabor sl->leaves[sl->leaves_num - 1] = item; 254235267Sgabor} 255235267Sgabor 256235267Sgaborstatic inline int 257235267Sgaborget_wc_index(struct sort_list_item *sli, size_t level) 258235267Sgabor{ 259318152Smarius const struct key_value *kv; 260235267Sgabor const struct bwstring *bws; 261235267Sgabor 262318152Smarius kv = get_key_from_keys_array(&sli->ka, 0); 263318152Smarius bws = kv->k; 264235267Sgabor 265235267Sgabor if ((BWSLEN(bws) > level)) 266235267Sgabor return (unsigned char) BWS_GET(bws,level); 267235267Sgabor return (-1); 268235267Sgabor} 269235267Sgabor 270235267Sgaborstatic void 271235267Sgaborplace_item(struct sort_level *sl, size_t item) 272235267Sgabor{ 273235267Sgabor struct sort_list_item *sli; 274235267Sgabor int c; 275235267Sgabor 276235267Sgabor sli = sl->tosort[item]; 277235267Sgabor c = get_wc_index(sli, sl->level); 278235267Sgabor 279235267Sgabor if (c == -1) 280235267Sgabor add_leaf(sl, sli); 281235267Sgabor else 282235267Sgabor add_to_sublevel(sl, sli, c); 283235267Sgabor} 284235267Sgabor 285235267Sgaborstatic void 286235267Sgaborfree_sort_level(struct sort_level *sl) 287235267Sgabor{ 288235267Sgabor 289235267Sgabor if (sl) { 290235267Sgabor if (sl->leaves) 291235267Sgabor sort_free(sl->leaves); 292235267Sgabor 293235267Sgabor if (sl->level > 0) 294235267Sgabor sort_free(sl->tosort); 295235267Sgabor 296235267Sgabor if (sl->sublevels) { 297235267Sgabor struct sort_level *slc; 298235267Sgabor size_t sln; 299235267Sgabor 300235267Sgabor sln = sl->sln; 301235267Sgabor 302235267Sgabor for (size_t i = 0; i < sln; ++i) { 303235267Sgabor slc = sl->sublevels[i]; 304235267Sgabor if (slc) 305235267Sgabor free_sort_level(slc); 306235267Sgabor } 307235267Sgabor 308235267Sgabor sort_free(sl->sublevels); 309235267Sgabor } 310235267Sgabor 311235267Sgabor sort_free(sl); 312235267Sgabor } 313235267Sgabor} 314235267Sgabor 315235267Sgaborstatic void 316235267Sgaborrun_sort_level_next(struct sort_level *sl) 317235267Sgabor{ 318235267Sgabor struct sort_level *slc; 319235267Sgabor size_t i, sln, tosort_num; 320235267Sgabor 321235267Sgabor if (sl->sublevels) { 322235267Sgabor sort_free(sl->sublevels); 323235267Sgabor sl->sublevels = NULL; 324235267Sgabor } 325235267Sgabor 326235267Sgabor switch (sl->tosort_num){ 327235267Sgabor case 0: 328235267Sgabor goto end; 329235267Sgabor case (1): 330235267Sgabor sl->sorted[sl->start_position] = sl->tosort[0]; 331235267Sgabor sort_left_dec(1); 332235267Sgabor goto end; 333235267Sgabor case (2): 334235267Sgabor if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]), 335235267Sgabor sl->level) > 0) { 336235267Sgabor sl->sorted[sl->start_position++] = sl->tosort[1]; 337235267Sgabor sl->sorted[sl->start_position] = sl->tosort[0]; 338235267Sgabor } else { 339235267Sgabor sl->sorted[sl->start_position++] = sl->tosort[0]; 340235267Sgabor sl->sorted[sl->start_position] = sl->tosort[1]; 341235267Sgabor } 342235267Sgabor sort_left_dec(2); 343235267Sgabor 344235267Sgabor goto end; 345235267Sgabor default: 346235267Sgabor if (TINY_NODE(sl) || (sl->level > 15)) { 347235267Sgabor listcoll_t func; 348235267Sgabor 349235267Sgabor func = get_list_call_func(sl->level); 350235267Sgabor 351235267Sgabor sl->leaves = sl->tosort; 352235267Sgabor sl->leaves_num = sl->tosort_num; 353235267Sgabor sl->leaves_sz = sl->leaves_num; 354235267Sgabor sl->leaves = sort_realloc(sl->leaves, 355235267Sgabor (sizeof(struct sort_list_item *) * 356235267Sgabor (sl->leaves_sz))); 357235267Sgabor sl->tosort = NULL; 358235267Sgabor sl->tosort_num = 0; 359235267Sgabor sl->tosort_sz = 0; 360235267Sgabor sl->sln = 0; 361235267Sgabor sl->real_sln = 0; 362235267Sgabor if (sort_opts_vals.sflag) { 363235267Sgabor if (mergesort(sl->leaves, sl->leaves_num, 364235267Sgabor sizeof(struct sort_list_item *), 365235267Sgabor (int(*)(const void *, const void *)) func) == -1) 366235267Sgabor /* NOTREACHED */ 367235267Sgabor err(2, "Radix sort error 3"); 368235267Sgabor } else 369238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 370235267Sgabor sizeof(struct sort_list_item *), 371235267Sgabor (int(*)(const void *, const void *)) func); 372235267Sgabor 373235267Sgabor memcpy(sl->sorted + sl->start_position, 374235267Sgabor sl->leaves, sl->leaves_num * 375235267Sgabor sizeof(struct sort_list_item*)); 376235267Sgabor 377235267Sgabor sort_left_dec(sl->leaves_num); 378235267Sgabor 379235267Sgabor goto end; 380235267Sgabor } else { 381235267Sgabor sl->tosort_sz = sl->tosort_num; 382235267Sgabor sl->tosort = sort_realloc(sl->tosort, 383235267Sgabor sizeof(struct sort_list_item*) * (sl->tosort_sz)); 384235267Sgabor } 385235267Sgabor } 386235267Sgabor 387235267Sgabor sl->sln = 256; 388235267Sgabor sl->sublevels = sort_malloc(slsz); 389235267Sgabor memset(sl->sublevels, 0, slsz); 390235267Sgabor 391235267Sgabor sl->real_sln = 0; 392235267Sgabor 393235267Sgabor tosort_num = sl->tosort_num; 394235267Sgabor for (i = 0; i < tosort_num; ++i) 395235267Sgabor place_item(sl, i); 396235267Sgabor 397235267Sgabor sort_free(sl->tosort); 398235267Sgabor sl->tosort = NULL; 399235267Sgabor sl->tosort_num = 0; 400235267Sgabor sl->tosort_sz = 0; 401235267Sgabor 402235267Sgabor if (sl->leaves_num > 1) { 403235267Sgabor if (keys_num > 1) { 404235267Sgabor if (sort_opts_vals.sflag) { 405235267Sgabor mergesort(sl->leaves, sl->leaves_num, 406235267Sgabor sizeof(struct sort_list_item *), 407235267Sgabor (int(*)(const void *, const void *)) list_coll); 408235267Sgabor } else { 409238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 410235267Sgabor sizeof(struct sort_list_item *), 411235267Sgabor (int(*)(const void *, const void *)) list_coll); 412235267Sgabor } 413235267Sgabor } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 414238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 415235267Sgabor sizeof(struct sort_list_item *), 416235267Sgabor (int(*)(const void *, const void *)) list_coll_by_str_only); 417235267Sgabor } 418235267Sgabor } 419235267Sgabor 420235267Sgabor sl->leaves_sz = sl->leaves_num; 421235267Sgabor sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) * 422235267Sgabor (sl->leaves_sz))); 423235267Sgabor 424235267Sgabor if (!reverse_sort) { 425235267Sgabor memcpy(sl->sorted + sl->start_position, sl->leaves, 426235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 427235267Sgabor sl->start_position += sl->leaves_num; 428235267Sgabor sort_left_dec(sl->leaves_num); 429235267Sgabor 430235267Sgabor sort_free(sl->leaves); 431235267Sgabor sl->leaves = NULL; 432235267Sgabor sl->leaves_num = 0; 433235267Sgabor sl->leaves_sz = 0; 434235267Sgabor 435235267Sgabor sln = sl->sln; 436235267Sgabor 437235267Sgabor for (i = 0; i < sln; ++i) { 438235267Sgabor slc = sl->sublevels[i]; 439235267Sgabor 440235267Sgabor if (slc) { 441235267Sgabor slc->sorted = sl->sorted; 442235267Sgabor slc->start_position = sl->start_position; 443235267Sgabor sl->start_position += slc->tosort_num; 444235267Sgabor if (SMALL_NODE(slc)) 445235267Sgabor run_sort_level_next(slc); 446235267Sgabor else 447235267Sgabor push_ls(slc); 448235267Sgabor sl->sublevels[i] = NULL; 449235267Sgabor } 450235267Sgabor } 451235267Sgabor 452235267Sgabor } else { 453235267Sgabor size_t n; 454235267Sgabor 455235267Sgabor sln = sl->sln; 456235267Sgabor 457235267Sgabor for (i = 0; i < sln; ++i) { 458235267Sgabor n = sln - i - 1; 459235267Sgabor slc = sl->sublevels[n]; 460235267Sgabor 461235267Sgabor if (slc) { 462235267Sgabor slc->sorted = sl->sorted; 463235267Sgabor slc->start_position = sl->start_position; 464235267Sgabor sl->start_position += slc->tosort_num; 465235267Sgabor if (SMALL_NODE(slc)) 466235267Sgabor run_sort_level_next(slc); 467235267Sgabor else 468235267Sgabor push_ls(slc); 469235267Sgabor sl->sublevels[n] = NULL; 470235267Sgabor } 471235267Sgabor } 472235267Sgabor 473235267Sgabor memcpy(sl->sorted + sl->start_position, sl->leaves, 474235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 475235267Sgabor sort_left_dec(sl->leaves_num); 476235267Sgabor } 477235267Sgabor 478235267Sgaborend: 479235267Sgabor free_sort_level(sl); 480235267Sgabor} 481235267Sgabor 482235267Sgabor/* 483235267Sgabor * Single-threaded sort cycle 484235267Sgabor */ 485235267Sgaborstatic void 486235267Sgaborrun_sort_cycle_st(void) 487235267Sgabor{ 488235267Sgabor struct sort_level *slc; 489235267Sgabor 490235267Sgabor for (;;) { 491235267Sgabor slc = pop_ls_st(); 492235267Sgabor if (slc == NULL) { 493235267Sgabor break; 494235267Sgabor } 495235267Sgabor run_sort_level_next(slc); 496235267Sgabor } 497235267Sgabor} 498235267Sgabor 499235267Sgabor#if defined(SORT_THREADS) 500235267Sgabor 501235267Sgabor/* 502235267Sgabor * Multi-threaded sort cycle 503235267Sgabor */ 504235267Sgaborstatic void 505235267Sgaborrun_sort_cycle_mt(void) 506235267Sgabor{ 507235267Sgabor struct sort_level *slc; 508235267Sgabor 509235267Sgabor for (;;) { 510235267Sgabor slc = pop_ls_mt(); 511313321Spfg if (slc == NULL) 512235267Sgabor break; 513235267Sgabor run_sort_level_next(slc); 514235267Sgabor } 515235267Sgabor} 516235267Sgabor 517235267Sgabor/* 518235267Sgabor * Sort cycle thread (in multi-threaded mode) 519235267Sgabor */ 520235267Sgaborstatic void* 521235267Sgaborsort_thread(void* arg) 522235267Sgabor{ 523235267Sgabor run_sort_cycle_mt(); 524235267Sgabor sem_post(&mtsem); 525235267Sgabor 526235267Sgabor return (arg); 527235267Sgabor} 528235267Sgabor 529235267Sgabor#endif /* defined(SORT_THREADS) */ 530235267Sgabor 531235267Sgaborstatic void 532235267Sgaborrun_top_sort_level(struct sort_level *sl) 533235267Sgabor{ 534235267Sgabor struct sort_level *slc; 535235267Sgabor 536235267Sgabor reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag : 537235267Sgabor default_sort_mods->rflag; 538235267Sgabor 539235267Sgabor sl->start_position = 0; 540235267Sgabor sl->sln = 256; 541235267Sgabor sl->sublevels = sort_malloc(slsz); 542235267Sgabor memset(sl->sublevels, 0, slsz); 543235267Sgabor 544235267Sgabor for (size_t i = 0; i < sl->tosort_num; ++i) 545235267Sgabor place_item(sl, i); 546235267Sgabor 547235267Sgabor if (sl->leaves_num > 1) { 548235267Sgabor if (keys_num > 1) { 549235267Sgabor if (sort_opts_vals.sflag) { 550235267Sgabor mergesort(sl->leaves, sl->leaves_num, 551235267Sgabor sizeof(struct sort_list_item *), 552235267Sgabor (int(*)(const void *, const void *)) list_coll); 553235267Sgabor } else { 554238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 555235267Sgabor sizeof(struct sort_list_item *), 556235267Sgabor (int(*)(const void *, const void *)) list_coll); 557235267Sgabor } 558235267Sgabor } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 559238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 560235267Sgabor sizeof(struct sort_list_item *), 561235267Sgabor (int(*)(const void *, const void *)) list_coll_by_str_only); 562235267Sgabor } 563235267Sgabor } 564235267Sgabor 565235267Sgabor if (!reverse_sort) { 566235267Sgabor memcpy(sl->tosort + sl->start_position, sl->leaves, 567235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 568235267Sgabor sl->start_position += sl->leaves_num; 569235267Sgabor sort_left_dec(sl->leaves_num); 570235267Sgabor 571235267Sgabor for (size_t i = 0; i < sl->sln; ++i) { 572235267Sgabor slc = sl->sublevels[i]; 573235267Sgabor 574235267Sgabor if (slc) { 575235267Sgabor slc->sorted = sl->tosort; 576235267Sgabor slc->start_position = sl->start_position; 577235267Sgabor sl->start_position += slc->tosort_num; 578235267Sgabor push_ls(slc); 579235267Sgabor sl->sublevels[i] = NULL; 580235267Sgabor } 581235267Sgabor } 582235267Sgabor 583235267Sgabor } else { 584235267Sgabor size_t n; 585235267Sgabor 586235267Sgabor for (size_t i = 0; i < sl->sln; ++i) { 587235267Sgabor 588235267Sgabor n = sl->sln - i - 1; 589235267Sgabor slc = sl->sublevels[n]; 590235267Sgabor 591235267Sgabor if (slc) { 592235267Sgabor slc->sorted = sl->tosort; 593235267Sgabor slc->start_position = sl->start_position; 594235267Sgabor sl->start_position += slc->tosort_num; 595235267Sgabor push_ls(slc); 596235267Sgabor sl->sublevels[n] = NULL; 597235267Sgabor } 598235267Sgabor } 599235267Sgabor 600235267Sgabor memcpy(sl->tosort + sl->start_position, sl->leaves, 601235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 602235267Sgabor 603235267Sgabor sort_left_dec(sl->leaves_num); 604235267Sgabor } 605235267Sgabor 606235267Sgabor#if defined(SORT_THREADS) 607235267Sgabor if (nthreads < 2) { 608235267Sgabor#endif 609235267Sgabor run_sort_cycle_st(); 610235267Sgabor#if defined(SORT_THREADS) 611235267Sgabor } else { 612235267Sgabor size_t i; 613235267Sgabor 614235267Sgabor for(i = 0; i < nthreads; ++i) { 615235267Sgabor pthread_attr_t attr; 616235267Sgabor pthread_t pth; 617235267Sgabor 618235267Sgabor pthread_attr_init(&attr); 619313321Spfg pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED); 620235267Sgabor 621235987Sgabor for (;;) { 622235987Sgabor int res = pthread_create(&pth, &attr, 623235987Sgabor sort_thread, NULL); 624235987Sgabor if (res >= 0) 625235987Sgabor break; 626235987Sgabor if (errno == EAGAIN) { 627235987Sgabor pthread_yield(); 628235987Sgabor continue; 629235987Sgabor } 630235987Sgabor err(2, NULL); 631235987Sgabor } 632235267Sgabor 633235267Sgabor pthread_attr_destroy(&attr); 634235267Sgabor } 635235267Sgabor 636313321Spfg for (i = 0; i < nthreads; ++i) 637235267Sgabor sem_wait(&mtsem); 638235267Sgabor } 639235267Sgabor#endif /* defined(SORT_THREADS) */ 640235267Sgabor} 641235267Sgabor 642235267Sgaborstatic void 643235267Sgaborrun_sort(struct sort_list_item **base, size_t nmemb) 644235267Sgabor{ 645235267Sgabor struct sort_level *sl; 646235267Sgabor 647235267Sgabor#if defined(SORT_THREADS) 648235987Sgabor size_t nthreads_save = nthreads; 649235987Sgabor if (nmemb < MT_SORT_THRESHOLD) 650235987Sgabor nthreads = 1; 651235987Sgabor 652235267Sgabor if (nthreads > 1) { 653235267Sgabor pthread_mutexattr_t mattr; 654235267Sgabor 655235267Sgabor pthread_mutexattr_init(&mattr); 656235267Sgabor pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP); 657235267Sgabor 658235267Sgabor pthread_mutex_init(&g_ls_mutex, &mattr); 659313321Spfg pthread_cond_init(&g_ls_cond, NULL); 660235267Sgabor 661235267Sgabor pthread_mutexattr_destroy(&mattr); 662235267Sgabor 663235267Sgabor sem_init(&mtsem, 0, 0); 664235267Sgabor 665235267Sgabor } 666235267Sgabor#endif 667235267Sgabor 668235267Sgabor sl = sort_malloc(sizeof(struct sort_level)); 669235267Sgabor memset(sl, 0, sizeof(struct sort_level)); 670235267Sgabor 671235267Sgabor sl->tosort = base; 672235267Sgabor sl->tosort_num = nmemb; 673235267Sgabor sl->tosort_sz = nmemb; 674235267Sgabor 675235267Sgabor#if defined(SORT_THREADS) 676235267Sgabor sort_left = nmemb; 677235267Sgabor#endif 678235267Sgabor 679235267Sgabor run_top_sort_level(sl); 680235267Sgabor 681235267Sgabor free_sort_level(sl); 682235267Sgabor 683235267Sgabor#if defined(SORT_THREADS) 684235267Sgabor if (nthreads > 1) { 685235267Sgabor sem_destroy(&mtsem); 686235267Sgabor pthread_mutex_destroy(&g_ls_mutex); 687235267Sgabor } 688235987Sgabor nthreads = nthreads_save; 689235267Sgabor#endif 690235267Sgabor} 691235267Sgabor 692235267Sgaborvoid 693235267Sgaborrxsort(struct sort_list_item **base, size_t nmemb) 694235267Sgabor{ 695235267Sgabor 696235267Sgabor run_sort(base, nmemb); 697235267Sgabor} 698