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$"); 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 */ 86235267Sgaborstatic pthread_mutex_t g_ls_mutex; 87235267Sgabor 88235267Sgabor/* counter: how many items are left */ 89235435Sgaborstatic size_t sort_left; 90235267Sgabor/* guarding mutex */ 91235267Sgaborstatic pthread_mutex_t sort_left_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{ 102235267Sgabor 103235267Sgabor pthread_mutex_lock(&sort_left_mutex); 104235267Sgabor sort_left -= n; 105235267Sgabor pthread_mutex_unlock(&sort_left_mutex); 106235267Sgabor} 107235267Sgabor 108235267Sgabor/* 109235267Sgabor * Do we have something to sort ? 110235267Sgabor */ 111235267Sgaborstatic inline bool 112235267Sgaborhave_sort_left(void) 113235267Sgabor{ 114235267Sgabor bool ret; 115235267Sgabor 116235267Sgabor pthread_mutex_lock(&sort_left_mutex); 117235267Sgabor ret = (sort_left > 0); 118235267Sgabor pthread_mutex_unlock(&sort_left_mutex); 119235267Sgabor return (ret); 120235267Sgabor} 121235267Sgabor 122235267Sgabor#else 123235267Sgabor 124235267Sgabor#define sort_left_dec(n) 125235267Sgabor 126235267Sgabor#endif /* SORT_THREADS */ 127235267Sgabor 128235267Sgabor/* 129235267Sgabor * Push sort level to the stack 130235267Sgabor */ 131235267Sgaborstatic inline void 132235267Sgaborpush_ls(struct sort_level* sl) 133235267Sgabor{ 134235267Sgabor struct level_stack *new_ls; 135235267Sgabor 136235267Sgabor new_ls = sort_malloc(sizeof(struct level_stack)); 137235267Sgabor new_ls->sl = sl; 138235267Sgabor 139235267Sgabor#if defined(SORT_THREADS) 140235267Sgabor if (nthreads > 1) 141235267Sgabor pthread_mutex_lock(&g_ls_mutex); 142235267Sgabor#endif 143235267Sgabor 144235267Sgabor new_ls->next = g_ls; 145235267Sgabor g_ls = new_ls; 146235267Sgabor 147235267Sgabor#if defined(SORT_THREADS) 148235267Sgabor if (nthreads > 1) 149235267Sgabor pthread_mutex_unlock(&g_ls_mutex); 150235267Sgabor#endif 151235267Sgabor} 152235267Sgabor 153235267Sgabor/* 154235267Sgabor * Pop sort level from the stack (single-threaded style) 155235267Sgabor */ 156235267Sgaborstatic inline struct sort_level* 157235267Sgaborpop_ls_st(void) 158235267Sgabor{ 159235267Sgabor struct sort_level *sl; 160235267Sgabor 161235267Sgabor if (g_ls) { 162235267Sgabor struct level_stack *saved_ls; 163235267Sgabor 164235267Sgabor sl = g_ls->sl; 165235267Sgabor saved_ls = g_ls; 166235267Sgabor g_ls = g_ls->next; 167235267Sgabor sort_free(saved_ls); 168235267Sgabor } else 169235267Sgabor sl = NULL; 170235267Sgabor 171235267Sgabor return (sl); 172235267Sgabor} 173235267Sgabor 174259853Sdim#if defined(SORT_THREADS) 175259853Sdim 176235267Sgabor/* 177235267Sgabor * Pop sort level from the stack (multi-threaded style) 178235267Sgabor */ 179235267Sgaborstatic inline struct sort_level* 180235267Sgaborpop_ls_mt(void) 181235267Sgabor{ 182235267Sgabor struct level_stack *saved_ls; 183235267Sgabor struct sort_level *sl; 184235267Sgabor 185235267Sgabor pthread_mutex_lock(&g_ls_mutex); 186235267Sgabor 187235267Sgabor if (g_ls) { 188235267Sgabor sl = g_ls->sl; 189235267Sgabor saved_ls = g_ls; 190235267Sgabor g_ls = g_ls->next; 191235267Sgabor } else { 192235267Sgabor sl = NULL; 193235267Sgabor saved_ls = NULL; 194235267Sgabor } 195235267Sgabor 196235267Sgabor pthread_mutex_unlock(&g_ls_mutex); 197235267Sgabor 198235267Sgabor sort_free(saved_ls); 199235267Sgabor 200235267Sgabor return (sl); 201235267Sgabor} 202235267Sgabor 203259853Sdim#endif /* defined(SORT_THREADS) */ 204259853Sdim 205235267Sgaborstatic void 206242430Sgaboradd_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx) 207235267Sgabor{ 208235267Sgabor struct sort_level *ssl; 209235267Sgabor 210235267Sgabor ssl = sl->sublevels[indx]; 211235267Sgabor 212235267Sgabor if (ssl == NULL) { 213235267Sgabor ssl = sort_malloc(sizeof(struct sort_level)); 214235267Sgabor memset(ssl, 0, sizeof(struct sort_level)); 215235267Sgabor 216235267Sgabor ssl->level = sl->level + 1; 217235267Sgabor sl->sublevels[indx] = ssl; 218235267Sgabor 219235267Sgabor ++(sl->real_sln); 220235267Sgabor } 221235267Sgabor 222235267Sgabor if (++(ssl->tosort_num) > ssl->tosort_sz) { 223235267Sgabor ssl->tosort_sz = ssl->tosort_num + 128; 224235267Sgabor ssl->tosort = sort_realloc(ssl->tosort, 225235267Sgabor sizeof(struct sort_list_item*) * (ssl->tosort_sz)); 226235267Sgabor } 227235267Sgabor 228235267Sgabor ssl->tosort[ssl->tosort_num - 1] = item; 229235267Sgabor} 230235267Sgabor 231235267Sgaborstatic inline void 232235267Sgaboradd_leaf(struct sort_level *sl, struct sort_list_item *item) 233235267Sgabor{ 234235267Sgabor 235235267Sgabor if (++(sl->leaves_num) > sl->leaves_sz) { 236235267Sgabor sl->leaves_sz = sl->leaves_num + 128; 237235267Sgabor sl->leaves = sort_realloc(sl->leaves, 238235267Sgabor (sizeof(struct sort_list_item*) * (sl->leaves_sz))); 239235267Sgabor } 240235267Sgabor sl->leaves[sl->leaves_num - 1] = item; 241235267Sgabor} 242235267Sgabor 243235267Sgaborstatic inline int 244235267Sgaborget_wc_index(struct sort_list_item *sli, size_t level) 245235267Sgabor{ 246235267Sgabor const struct bwstring *bws; 247235267Sgabor 248235267Sgabor bws = sli->ka.key[0].k; 249235267Sgabor 250235267Sgabor if ((BWSLEN(bws) > level)) 251235267Sgabor return (unsigned char) BWS_GET(bws,level); 252235267Sgabor return (-1); 253235267Sgabor} 254235267Sgabor 255235267Sgaborstatic void 256235267Sgaborplace_item(struct sort_level *sl, size_t item) 257235267Sgabor{ 258235267Sgabor struct sort_list_item *sli; 259235267Sgabor int c; 260235267Sgabor 261235267Sgabor sli = sl->tosort[item]; 262235267Sgabor c = get_wc_index(sli, sl->level); 263235267Sgabor 264235267Sgabor if (c == -1) 265235267Sgabor add_leaf(sl, sli); 266235267Sgabor else 267235267Sgabor add_to_sublevel(sl, sli, c); 268235267Sgabor} 269235267Sgabor 270235267Sgaborstatic void 271235267Sgaborfree_sort_level(struct sort_level *sl) 272235267Sgabor{ 273235267Sgabor 274235267Sgabor if (sl) { 275235267Sgabor if (sl->leaves) 276235267Sgabor sort_free(sl->leaves); 277235267Sgabor 278235267Sgabor if (sl->level > 0) 279235267Sgabor sort_free(sl->tosort); 280235267Sgabor 281235267Sgabor if (sl->sublevels) { 282235267Sgabor struct sort_level *slc; 283235267Sgabor size_t sln; 284235267Sgabor 285235267Sgabor sln = sl->sln; 286235267Sgabor 287235267Sgabor for (size_t i = 0; i < sln; ++i) { 288235267Sgabor slc = sl->sublevels[i]; 289235267Sgabor if (slc) 290235267Sgabor free_sort_level(slc); 291235267Sgabor } 292235267Sgabor 293235267Sgabor sort_free(sl->sublevels); 294235267Sgabor } 295235267Sgabor 296235267Sgabor sort_free(sl); 297235267Sgabor } 298235267Sgabor} 299235267Sgabor 300235267Sgaborstatic void 301235267Sgaborrun_sort_level_next(struct sort_level *sl) 302235267Sgabor{ 303235267Sgabor struct sort_level *slc; 304235267Sgabor size_t i, sln, tosort_num; 305235267Sgabor 306235267Sgabor if (sl->sublevels) { 307235267Sgabor sort_free(sl->sublevels); 308235267Sgabor sl->sublevels = NULL; 309235267Sgabor } 310235267Sgabor 311235267Sgabor switch (sl->tosort_num){ 312235267Sgabor case 0: 313235267Sgabor goto end; 314235267Sgabor case (1): 315235267Sgabor sl->sorted[sl->start_position] = sl->tosort[0]; 316235267Sgabor sort_left_dec(1); 317235267Sgabor goto end; 318235267Sgabor case (2): 319235267Sgabor if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]), 320235267Sgabor sl->level) > 0) { 321235267Sgabor sl->sorted[sl->start_position++] = sl->tosort[1]; 322235267Sgabor sl->sorted[sl->start_position] = sl->tosort[0]; 323235267Sgabor } else { 324235267Sgabor sl->sorted[sl->start_position++] = sl->tosort[0]; 325235267Sgabor sl->sorted[sl->start_position] = sl->tosort[1]; 326235267Sgabor } 327235267Sgabor sort_left_dec(2); 328235267Sgabor 329235267Sgabor goto end; 330235267Sgabor default: 331235267Sgabor if (TINY_NODE(sl) || (sl->level > 15)) { 332235267Sgabor listcoll_t func; 333235267Sgabor 334235267Sgabor func = get_list_call_func(sl->level); 335235267Sgabor 336235267Sgabor sl->leaves = sl->tosort; 337235267Sgabor sl->leaves_num = sl->tosort_num; 338235267Sgabor sl->leaves_sz = sl->leaves_num; 339235267Sgabor sl->leaves = sort_realloc(sl->leaves, 340235267Sgabor (sizeof(struct sort_list_item *) * 341235267Sgabor (sl->leaves_sz))); 342235267Sgabor sl->tosort = NULL; 343235267Sgabor sl->tosort_num = 0; 344235267Sgabor sl->tosort_sz = 0; 345235267Sgabor sl->sln = 0; 346235267Sgabor sl->real_sln = 0; 347235267Sgabor if (sort_opts_vals.sflag) { 348235267Sgabor if (mergesort(sl->leaves, sl->leaves_num, 349235267Sgabor sizeof(struct sort_list_item *), 350235267Sgabor (int(*)(const void *, const void *)) func) == -1) 351235267Sgabor /* NOTREACHED */ 352235267Sgabor err(2, "Radix sort error 3"); 353235267Sgabor } else 354238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 355235267Sgabor sizeof(struct sort_list_item *), 356235267Sgabor (int(*)(const void *, const void *)) func); 357235267Sgabor 358235267Sgabor memcpy(sl->sorted + sl->start_position, 359235267Sgabor sl->leaves, sl->leaves_num * 360235267Sgabor sizeof(struct sort_list_item*)); 361235267Sgabor 362235267Sgabor sort_left_dec(sl->leaves_num); 363235267Sgabor 364235267Sgabor goto end; 365235267Sgabor } else { 366235267Sgabor sl->tosort_sz = sl->tosort_num; 367235267Sgabor sl->tosort = sort_realloc(sl->tosort, 368235267Sgabor sizeof(struct sort_list_item*) * (sl->tosort_sz)); 369235267Sgabor } 370235267Sgabor } 371235267Sgabor 372235267Sgabor sl->sln = 256; 373235267Sgabor sl->sublevels = sort_malloc(slsz); 374235267Sgabor memset(sl->sublevels, 0, slsz); 375235267Sgabor 376235267Sgabor sl->real_sln = 0; 377235267Sgabor 378235267Sgabor tosort_num = sl->tosort_num; 379235267Sgabor for (i = 0; i < tosort_num; ++i) 380235267Sgabor place_item(sl, i); 381235267Sgabor 382235267Sgabor sort_free(sl->tosort); 383235267Sgabor sl->tosort = NULL; 384235267Sgabor sl->tosort_num = 0; 385235267Sgabor sl->tosort_sz = 0; 386235267Sgabor 387235267Sgabor if (sl->leaves_num > 1) { 388235267Sgabor if (keys_num > 1) { 389235267Sgabor if (sort_opts_vals.sflag) { 390235267Sgabor mergesort(sl->leaves, sl->leaves_num, 391235267Sgabor sizeof(struct sort_list_item *), 392235267Sgabor (int(*)(const void *, const void *)) list_coll); 393235267Sgabor } else { 394238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 395235267Sgabor sizeof(struct sort_list_item *), 396235267Sgabor (int(*)(const void *, const void *)) list_coll); 397235267Sgabor } 398235267Sgabor } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 399238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 400235267Sgabor sizeof(struct sort_list_item *), 401235267Sgabor (int(*)(const void *, const void *)) list_coll_by_str_only); 402235267Sgabor } 403235267Sgabor } 404235267Sgabor 405235267Sgabor sl->leaves_sz = sl->leaves_num; 406235267Sgabor sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) * 407235267Sgabor (sl->leaves_sz))); 408235267Sgabor 409235267Sgabor if (!reverse_sort) { 410235267Sgabor memcpy(sl->sorted + sl->start_position, sl->leaves, 411235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 412235267Sgabor sl->start_position += sl->leaves_num; 413235267Sgabor sort_left_dec(sl->leaves_num); 414235267Sgabor 415235267Sgabor sort_free(sl->leaves); 416235267Sgabor sl->leaves = NULL; 417235267Sgabor sl->leaves_num = 0; 418235267Sgabor sl->leaves_sz = 0; 419235267Sgabor 420235267Sgabor sln = sl->sln; 421235267Sgabor 422235267Sgabor for (i = 0; i < sln; ++i) { 423235267Sgabor slc = sl->sublevels[i]; 424235267Sgabor 425235267Sgabor if (slc) { 426235267Sgabor slc->sorted = sl->sorted; 427235267Sgabor slc->start_position = sl->start_position; 428235267Sgabor sl->start_position += slc->tosort_num; 429235267Sgabor if (SMALL_NODE(slc)) 430235267Sgabor run_sort_level_next(slc); 431235267Sgabor else 432235267Sgabor push_ls(slc); 433235267Sgabor sl->sublevels[i] = NULL; 434235267Sgabor } 435235267Sgabor } 436235267Sgabor 437235267Sgabor } else { 438235267Sgabor size_t n; 439235267Sgabor 440235267Sgabor sln = sl->sln; 441235267Sgabor 442235267Sgabor for (i = 0; i < sln; ++i) { 443235267Sgabor n = sln - i - 1; 444235267Sgabor slc = sl->sublevels[n]; 445235267Sgabor 446235267Sgabor if (slc) { 447235267Sgabor slc->sorted = sl->sorted; 448235267Sgabor slc->start_position = sl->start_position; 449235267Sgabor sl->start_position += slc->tosort_num; 450235267Sgabor if (SMALL_NODE(slc)) 451235267Sgabor run_sort_level_next(slc); 452235267Sgabor else 453235267Sgabor push_ls(slc); 454235267Sgabor sl->sublevels[n] = NULL; 455235267Sgabor } 456235267Sgabor } 457235267Sgabor 458235267Sgabor memcpy(sl->sorted + sl->start_position, sl->leaves, 459235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 460235267Sgabor sort_left_dec(sl->leaves_num); 461235267Sgabor } 462235267Sgabor 463235267Sgaborend: 464235267Sgabor free_sort_level(sl); 465235267Sgabor} 466235267Sgabor 467235267Sgabor/* 468235267Sgabor * Single-threaded sort cycle 469235267Sgabor */ 470235267Sgaborstatic void 471235267Sgaborrun_sort_cycle_st(void) 472235267Sgabor{ 473235267Sgabor struct sort_level *slc; 474235267Sgabor 475235267Sgabor for (;;) { 476235267Sgabor slc = pop_ls_st(); 477235267Sgabor if (slc == NULL) { 478235267Sgabor break; 479235267Sgabor } 480235267Sgabor run_sort_level_next(slc); 481235267Sgabor } 482235267Sgabor} 483235267Sgabor 484235267Sgabor#if defined(SORT_THREADS) 485235267Sgabor 486235267Sgabor/* 487235267Sgabor * Multi-threaded sort cycle 488235267Sgabor */ 489235267Sgaborstatic void 490235267Sgaborrun_sort_cycle_mt(void) 491235267Sgabor{ 492235267Sgabor struct sort_level *slc; 493235267Sgabor 494235267Sgabor for (;;) { 495235267Sgabor slc = pop_ls_mt(); 496235267Sgabor if (slc == NULL) { 497235267Sgabor if (have_sort_left()) { 498235267Sgabor pthread_yield(); 499235267Sgabor continue; 500235267Sgabor } 501235267Sgabor break; 502235267Sgabor } 503235267Sgabor run_sort_level_next(slc); 504235267Sgabor } 505235267Sgabor} 506235267Sgabor 507235267Sgabor/* 508235267Sgabor * Sort cycle thread (in multi-threaded mode) 509235267Sgabor */ 510235267Sgaborstatic void* 511235267Sgaborsort_thread(void* arg) 512235267Sgabor{ 513235267Sgabor 514235267Sgabor run_sort_cycle_mt(); 515235267Sgabor 516235267Sgabor sem_post(&mtsem); 517235267Sgabor 518235267Sgabor return (arg); 519235267Sgabor} 520235267Sgabor 521235267Sgabor#endif /* defined(SORT_THREADS) */ 522235267Sgabor 523235267Sgaborstatic void 524235267Sgaborrun_top_sort_level(struct sort_level *sl) 525235267Sgabor{ 526235267Sgabor struct sort_level *slc; 527235267Sgabor 528235267Sgabor reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag : 529235267Sgabor default_sort_mods->rflag; 530235267Sgabor 531235267Sgabor sl->start_position = 0; 532235267Sgabor sl->sln = 256; 533235267Sgabor sl->sublevels = sort_malloc(slsz); 534235267Sgabor memset(sl->sublevels, 0, slsz); 535235267Sgabor 536235267Sgabor for (size_t i = 0; i < sl->tosort_num; ++i) 537235267Sgabor place_item(sl, i); 538235267Sgabor 539235267Sgabor if (sl->leaves_num > 1) { 540235267Sgabor if (keys_num > 1) { 541235267Sgabor if (sort_opts_vals.sflag) { 542235267Sgabor mergesort(sl->leaves, sl->leaves_num, 543235267Sgabor sizeof(struct sort_list_item *), 544235267Sgabor (int(*)(const void *, const void *)) list_coll); 545235267Sgabor } else { 546238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 547235267Sgabor sizeof(struct sort_list_item *), 548235267Sgabor (int(*)(const void *, const void *)) list_coll); 549235267Sgabor } 550235267Sgabor } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) { 551238108Sgabor DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num, 552235267Sgabor sizeof(struct sort_list_item *), 553235267Sgabor (int(*)(const void *, const void *)) list_coll_by_str_only); 554235267Sgabor } 555235267Sgabor } 556235267Sgabor 557235267Sgabor if (!reverse_sort) { 558235267Sgabor memcpy(sl->tosort + sl->start_position, sl->leaves, 559235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 560235267Sgabor sl->start_position += sl->leaves_num; 561235267Sgabor sort_left_dec(sl->leaves_num); 562235267Sgabor 563235267Sgabor for (size_t i = 0; i < sl->sln; ++i) { 564235267Sgabor slc = sl->sublevels[i]; 565235267Sgabor 566235267Sgabor if (slc) { 567235267Sgabor slc->sorted = sl->tosort; 568235267Sgabor slc->start_position = sl->start_position; 569235267Sgabor sl->start_position += slc->tosort_num; 570235267Sgabor push_ls(slc); 571235267Sgabor sl->sublevels[i] = NULL; 572235267Sgabor } 573235267Sgabor } 574235267Sgabor 575235267Sgabor } else { 576235267Sgabor size_t n; 577235267Sgabor 578235267Sgabor for (size_t i = 0; i < sl->sln; ++i) { 579235267Sgabor 580235267Sgabor n = sl->sln - i - 1; 581235267Sgabor slc = sl->sublevels[n]; 582235267Sgabor 583235267Sgabor if (slc) { 584235267Sgabor slc->sorted = sl->tosort; 585235267Sgabor slc->start_position = sl->start_position; 586235267Sgabor sl->start_position += slc->tosort_num; 587235267Sgabor push_ls(slc); 588235267Sgabor sl->sublevels[n] = NULL; 589235267Sgabor } 590235267Sgabor } 591235267Sgabor 592235267Sgabor memcpy(sl->tosort + sl->start_position, sl->leaves, 593235267Sgabor sl->leaves_num * sizeof(struct sort_list_item*)); 594235267Sgabor 595235267Sgabor sort_left_dec(sl->leaves_num); 596235267Sgabor } 597235267Sgabor 598235267Sgabor#if defined(SORT_THREADS) 599235267Sgabor if (nthreads < 2) { 600235267Sgabor#endif 601235267Sgabor run_sort_cycle_st(); 602235267Sgabor#if defined(SORT_THREADS) 603235267Sgabor } else { 604235267Sgabor size_t i; 605235267Sgabor 606235267Sgabor for(i = 0; i < nthreads; ++i) { 607235267Sgabor pthread_attr_t attr; 608235267Sgabor pthread_t pth; 609235267Sgabor 610235267Sgabor pthread_attr_init(&attr); 611235267Sgabor pthread_attr_setdetachstate(&attr, 612235267Sgabor PTHREAD_DETACHED); 613235267Sgabor 614235987Sgabor for (;;) { 615235987Sgabor int res = pthread_create(&pth, &attr, 616235987Sgabor sort_thread, NULL); 617235987Sgabor if (res >= 0) 618235987Sgabor break; 619235987Sgabor if (errno == EAGAIN) { 620235987Sgabor pthread_yield(); 621235987Sgabor continue; 622235987Sgabor } 623235987Sgabor err(2, NULL); 624235987Sgabor } 625235267Sgabor 626235267Sgabor pthread_attr_destroy(&attr); 627235267Sgabor } 628235267Sgabor 629235267Sgabor for(i = 0; i < nthreads; ++i) 630235267Sgabor sem_wait(&mtsem); 631235267Sgabor } 632235267Sgabor#endif /* defined(SORT_THREADS) */ 633235267Sgabor} 634235267Sgabor 635235267Sgaborstatic void 636235267Sgaborrun_sort(struct sort_list_item **base, size_t nmemb) 637235267Sgabor{ 638235267Sgabor struct sort_level *sl; 639235267Sgabor 640235267Sgabor#if defined(SORT_THREADS) 641235987Sgabor size_t nthreads_save = nthreads; 642235987Sgabor if (nmemb < MT_SORT_THRESHOLD) 643235987Sgabor nthreads = 1; 644235987Sgabor 645235267Sgabor if (nthreads > 1) { 646235267Sgabor pthread_mutexattr_t mattr; 647235267Sgabor 648235267Sgabor pthread_mutexattr_init(&mattr); 649235267Sgabor pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP); 650235267Sgabor 651235267Sgabor pthread_mutex_init(&g_ls_mutex, &mattr); 652235267Sgabor pthread_mutex_init(&sort_left_mutex, &mattr); 653235267Sgabor 654235267Sgabor pthread_mutexattr_destroy(&mattr); 655235267Sgabor 656235267Sgabor sem_init(&mtsem, 0, 0); 657235267Sgabor 658235267Sgabor } 659235267Sgabor#endif 660235267Sgabor 661235267Sgabor sl = sort_malloc(sizeof(struct sort_level)); 662235267Sgabor memset(sl, 0, sizeof(struct sort_level)); 663235267Sgabor 664235267Sgabor sl->tosort = base; 665235267Sgabor sl->tosort_num = nmemb; 666235267Sgabor sl->tosort_sz = nmemb; 667235267Sgabor 668235267Sgabor#if defined(SORT_THREADS) 669235267Sgabor sort_left = nmemb; 670235267Sgabor#endif 671235267Sgabor 672235267Sgabor run_top_sort_level(sl); 673235267Sgabor 674235267Sgabor free_sort_level(sl); 675235267Sgabor 676235267Sgabor#if defined(SORT_THREADS) 677235267Sgabor if (nthreads > 1) { 678235267Sgabor sem_destroy(&mtsem); 679235267Sgabor pthread_mutex_destroy(&g_ls_mutex); 680235267Sgabor pthread_mutex_destroy(&sort_left_mutex); 681235267Sgabor } 682235987Sgabor nthreads = nthreads_save; 683235267Sgabor#endif 684235267Sgabor} 685235267Sgabor 686235267Sgaborvoid 687235267Sgaborrxsort(struct sort_list_item **base, size_t nmemb) 688235267Sgabor{ 689235267Sgabor 690235267Sgabor run_sort(base, nmemb); 691235267Sgabor} 692