usr.bin/sort/file.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
   5  * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
   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 <sys/mman.h>
  34 #include <sys/stat.h>
  35 #include <sys/types.h>
  36 #include <sys/queue.h>
  37
  38 #include <err.h>
  39 #include <fcntl.h>
  40 #if defined(SORT_THREADS)
  41 #include <pthread.h>
  42 #endif
  43 #include <semaphore.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <unistd.h>
  48 #include <wchar.h>
  49 #include <wctype.h>
  50
  51 #include "coll.h"
  52 #include "file.h"
  53 #include "radixsort.h"
  54
  55 unsigned long long free_memory = 1000000;
  56 unsigned long long available_free_memory = 1000000;
  57
  58 bool use_mmap;
  59
  60 const char *tmpdir = "/var/tmp";
  61 const char *compress_program;
  62
  63 size_t max_open_files = 16;
  64
  65 /*
  66  * How much space we read from file at once
  67  */
  68 #define READ_CHUNK (4096)
  69
  70 /*
  71  * File reader structure
  72  */
  73 struct file_reader
  74 {
  75         struct reader_buffer     rb;
  76         FILE                    *file;
  77         char                    *fname;
  78         char                    *buffer;
  79         unsigned char           *mmapaddr;
  80         unsigned char           *mmapptr;
  81         size_t                   bsz;
  82         size_t                   cbsz;
  83         size_t                   mmapsize;
  84         size_t                   strbeg;
  85         int                      fd;
  86         char                     elsymb;
  87 };
  88
  89 /*
  90  * Structure to be used in file merge process.
  91  */
  92 struct file_header
  93 {
  94         struct file_reader              *fr;
  95         struct sort_list_item           *si; /* current top line */
  96         size_t                           file_pos;
  97 };
  98
  99 /*
 100  * List elements of "cleanable" files list.
 101  */
 102 struct CLEANABLE_FILE
 103 {
 104         char                            *fn;
 105         LIST_ENTRY(CLEANABLE_FILE)       files;
 106 };
 107
 108 /*
 109  * List header of "cleanable" files list.
 110  */
 111 static LIST_HEAD(CLEANABLE_FILES,CLEANABLE_FILE) tmp_files;
 112
 113 /*
 114  * Semaphore to protect the tmp file list.
 115  * We use semaphore here because it is signal-safe, according to POSIX.
 116  * And semaphore does not require pthread library.
 117  */
 118 static sem_t tmp_files_sem;
 119
 120 static void mt_sort(struct sort_list *list,
 121     int (*sort_func)(void *, size_t, size_t,
 122     int (*)(const void *, const void *)), const char* fn);
 123
 124 /*
 125  * Init tmp files list
 126  */
 127 void
 128 init_tmp_files(void)
 129 {
 130
 131         LIST_INIT(&tmp_files);
 132         sem_init(&tmp_files_sem, 0, 1);
 133 }
 134
 135 /*
 136  * Save name of a tmp file for signal cleanup
 137  */
 138 void
 139 tmp_file_atexit(const char *tmp_file)
 140 {
 141
 142         if (tmp_file) {
 143                 sem_wait(&tmp_files_sem);
 144                 struct CLEANABLE_FILE *item =
 145                     sort_malloc(sizeof(struct CLEANABLE_FILE));
 146                 item->fn = sort_strdup(tmp_file);
 147                 LIST_INSERT_HEAD(&tmp_files, item, files);
 148                 sem_post(&tmp_files_sem);
 149         }
 150 }
 151
 152 /*
 153  * Clear tmp files
 154  */
 155 void
 156 clear_tmp_files(void)
 157 {
 158         struct CLEANABLE_FILE *item;
 159
 160         sem_wait(&tmp_files_sem);
 161         LIST_FOREACH(item,&tmp_files,files) {
 162                 if ((item) && (item->fn))
 163                         unlink(item->fn);
 164         }
 165         sem_post(&tmp_files_sem);
 166 }
 167
 168 /*
 169  * Check whether a file is a temporary file
 170  */
 171 static bool
 172 file_is_tmp(const char* fn)
 173 {
 174         struct CLEANABLE_FILE *item;
 175         bool ret = false;
 176
 177         if (fn) {
 178                 sem_wait(&tmp_files_sem);
 179                 LIST_FOREACH(item,&tmp_files,files) {
 180                         if ((item) && (item->fn))
 181                                 if (strcmp(item->fn, fn) == 0) {
 182                                         ret = true;
 183                                         break;
 184                                 }
 185                 }
 186                 sem_post(&tmp_files_sem);
 187         }
 188
 189         return (ret);
 190 }
 191
 192 /*
 193  * Generate new temporary file name
 194  */
 195 char *
 196 new_tmp_file_name(void)
 197 {
 198         char *ret;
 199         int fd;
 200
 201         if (asprintf(&ret, "%s/.bsdsort.XXXXXXXXXX", tmpdir) == -1)
 202                 err(2, "asprintf()");
 203         if ((fd = mkstemp(ret)) == -1)
 204                 err(2, "mkstemp()");
 205         close(fd);
 206
 207         tmp_file_atexit(ret);
 208         return (ret);
 209 }
 210
 211 /*
 212  * Initialize file list
 213  */
 214 void
 215 file_list_init(struct file_list *fl, bool tmp)
 216 {
 217
 218         if (fl) {
 219                 fl->count = 0;
 220                 fl->sz = 0;
 221                 fl->fns = NULL;
 222                 fl->tmp = tmp;
 223         }
 224 }
 225
 226 /*
 227  * Add a file name to the list
 228  */
 229 void
 230 file_list_add(struct file_list *fl, const char *fn, bool allocate)
 231 {
 232
 233         if (fl && fn) {
 234                 if (fl->count >= fl->sz || (fl->fns == NULL)) {
 235                         fl->sz = (fl->sz) * 2 + 1;
 236                         fl->fns = sort_realloc(fl->fns, fl->sz *
 237                             sizeof(char *));
 238                 }
 239                 fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;
 240                 fl->count += 1;
 241         }
 242 }
 243
 244 /*
 245  * Populate file list from array of file names
 246  */
 247 void
 248 file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate)
 249 {
 250
 251         if (fl && argv) {
 252                 int i;
 253
 254                 for (i = 0; i < argc; i++)
 255                         file_list_add(fl, argv[i], allocate);
 256         }
 257 }
 258
 259 /*
 260  * Clean file list data and delete the files,
 261  * if this is a list of temporary files
 262  */
 263 void
 264 file_list_clean(struct file_list *fl)
 265 {
 266
 267         if (fl) {
 268                 if (fl->fns) {
 269                         size_t i;
 270
 271                         for (i = 0; i < fl->count; i++) {
 272                                 if (fl->fns[i]) {
 273                                         if (fl->tmp)
 274                                                 unlink(fl->fns[i]);
 275                                         sort_free(fl->fns[i]);
 276                                         fl->fns[i] = 0;
 277                                 }
 278                         }
 279                         sort_free(fl->fns);
 280                         fl->fns = NULL;
 281                 }
 282                 fl->sz = 0;
 283                 fl->count = 0;
 284                 fl->tmp = false;
 285         }
 286 }
 287
 288 /*
 289  * Init sort list
 290  */
 291 void
 292 sort_list_init(struct sort_list *l)
 293 {
 294
 295         if (l) {
 296                 l->count = 0;
 297                 l->size = 0;
 298                 l->memsize = sizeof(struct sort_list);
 299                 l->list = NULL;
 300         }
 301 }
 302
 303 /*
 304  * Add string to sort list
 305  */
 306 void
 307 sort_list_add(struct sort_list *l, struct bwstring *str)
 308 {
 309
 310         if (l && str) {
 311                 size_t indx = l->count;
 312
 313                 if ((l->list == NULL) || (indx >= l->size)) {
 314                         size_t newsize = (l->size + 1) + 1024;
 315
 316                         l->list = sort_realloc(l->list,
 317                             sizeof(struct sort_list_item*) * newsize);
 318                         l->memsize += (newsize - l->size) *
 319                             sizeof(struct sort_list_item*);
 320                         l->size = newsize;
 321                 }
 322                 l->list[indx] = sort_list_item_alloc();
 323                 sort_list_item_set(l->list[indx], str);
 324                 l->memsize += sort_list_item_size(l->list[indx]);
 325                 l->count += 1;
 326         }
 327 }
 328
 329 /*
 330  * Clean sort list data
 331  */
 332 void
 333 sort_list_clean(struct sort_list *l)
 334 {
 335
 336         if (l) {
 337                 if (l->list) {
 338                         size_t i;
 339
 340                         for (i = 0; i < l->count; i++) {
 341                                 struct sort_list_item *item;
 342
 343                                 item = l->list[i];
 344
 345                                 if (item) {
 346                                         sort_list_item_clean(item);
 347                                         sort_free(item);
 348                                         l->list[i] = NULL;
 349                                 }
 350                         }
 351                         sort_free(l->list);
 352                         l->list = NULL;
 353                 }
 354                 l->count = 0;
 355                 l->size = 0;
 356                 l->memsize = sizeof(struct sort_list);
 357         }
 358 }
 359
 360 /*
 361  * Write sort list to file
 362  */
 363 void
 364 sort_list_dump(struct sort_list *l, const char *fn)
 365 {
 366
 367         if (l && fn) {
 368                 FILE *f;
 369
 370                 f = openfile(fn, "w");
 371                 if (f == NULL)
 372                         err(2, NULL);
 373
 374                 if (l->list) {
 375                         size_t i;
 376                         if (!(sort_opts_vals.uflag)) {
 377                                 for (i = 0; i < l->count; ++i)
 378                                         bwsfwrite(l->list[i]->str, f,
 379                                             sort_opts_vals.zflag);
 380                         } else {
 381                                 struct sort_list_item *last_printed_item = NULL;
 382                                 struct sort_list_item *item;
 383                                 for (i = 0; i < l->count; ++i) {
 384                                         item = l->list[i];
 385                                         if ((last_printed_item == NULL) ||
 386                                             list_coll(&last_printed_item, &item)) {
 387                                                 bwsfwrite(item->str, f, sort_opts_vals.zflag);
 388                                                 last_printed_item = item;
 389                                         }
 390                                 }
 391                         }
 392                 }
 393
 394                 closefile(f, fn);
 395         }
 396 }
 397
 398 /*
 399  * Checks if the given file is sorted.  Stops at the first disorder,
 400  * prints the disordered line and returns 1.
 401  */
 402 int
 403 check(const char *fn)
 404 {
 405         struct bwstring *s1, *s2, *s1disorder, *s2disorder;
 406         struct file_reader *fr;
 407         struct keys_array *ka1, *ka2;
 408         int res;
 409         size_t pos, posdisorder;
 410
 411         s1 = s2 = s1disorder = s2disorder = NULL;
 412         ka1 = ka2 = NULL;
 413
 414         fr = file_reader_init(fn);
 415
 416         res = 0;
 417         pos = 1;
 418         posdisorder = 1;
 419
 420         if (fr == NULL) {
 421                 err(2, NULL);
 422                 goto end;
 423         }
 424
 425         s1 = file_reader_readline(fr);
 426         if (s1 == NULL)
 427                 goto end;
 428
 429         ka1 = keys_array_alloc();
 430         preproc(s1, ka1);
 431
 432         s2 = file_reader_readline(fr);
 433         if (s2 == NULL)
 434                 goto end;
 435
 436         ka2 = keys_array_alloc();
 437         preproc(s2, ka2);
 438
 439         for (;;) {
 440
 441                 if (debug_sort) {
 442                         bwsprintf(stdout, s2, "s1=<", ">");
 443                         bwsprintf(stdout, s1, "s2=<", ">");
 444                 }
 445                 int cmp = key_coll(ka2, ka1, 0);
 446                 if (debug_sort)
 447                         printf("; cmp1=%d", cmp);
 448
 449                 if (!cmp && sort_opts_vals.complex_sort &&
 450                     !(sort_opts_vals.uflag) && !(sort_opts_vals.sflag)) {
 451                         cmp = top_level_str_coll(s2, s1);
 452                         if (debug_sort)
 453                                 printf("; cmp2=%d", cmp);
 454                 }
 455                 if (debug_sort)
 456                         printf("\n");
 457
 458                 if ((sort_opts_vals.uflag && (cmp <= 0)) || (cmp < 0)) {
 459                         if (!(sort_opts_vals.csilentflag)) {
 460                                 s2disorder = bwsdup(s2);
 461                                 posdisorder = pos;
 462                                 if (debug_sort)
 463                                         s1disorder = bwsdup(s1);
 464                         }
 465                         res = 1;
 466                         goto end;
 467                 }
 468
 469                 pos++;
 470
 471                 clean_keys_array(s1, ka1);
 472                 sort_free(ka1);
 473                 ka1 = ka2;
 474                 ka2 = NULL;
 475
 476                 bwsfree(s1);
 477                 s1 = s2;
 478
 479                 s2 = file_reader_readline(fr);
 480                 if (s2 == NULL)
 481                         goto end;
 482
 483                 ka2 = keys_array_alloc();
 484                 preproc(s2, ka2);
 485         }
 486
 487 end:
 488         if (ka1) {
 489                 clean_keys_array(s1, ka1);
 490                 sort_free(ka1);
 491         }
 492
 493         if (s1)
 494                 bwsfree(s1);
 495
 496         if (ka2) {
 497                 clean_keys_array(s2, ka2);
 498                 sort_free(ka2);
 499         }
 500
 501         if (s2)
 502                 bwsfree(s2);
 503
 504         if ((fn == NULL) || (*fn == 0) || (strcmp(fn, "-") == 0)) {
 505                 for (;;) {
 506                         s2 = file_reader_readline(fr);
 507                         if (s2 == NULL)
 508                                 break;
 509                         bwsfree(s2);
 510                 }
 511         }
 512
 513         file_reader_free(fr);
 514
 515         if (s2disorder) {
 516                 bws_disorder_warnx(s2disorder, fn, posdisorder);
 517                 if (s1disorder) {
 518                         bws_disorder_warnx(s1disorder, fn, posdisorder);
 519                         if (s1disorder != s2disorder)
 520                                 bwsfree(s1disorder);
 521                 }
 522                 bwsfree(s2disorder);
 523                 s1disorder = NULL;
 524                 s2disorder = NULL;
 525         }
 526
 527         if (res)
 528                 exit(res);
 529
 530         return (0);
 531 }
 532
 533 /*
 534  * Opens a file.  If the given filename is "-", stdout will be
 535  * opened.
 536  */
 537 FILE *
 538 openfile(const char *fn, const char *mode)
 539 {
 540         FILE *file;
 541
 542         if (strcmp(fn, "-") == 0) {
 543                 return ((mode && mode[0] == 'r') ? stdin : stdout);
 544         } else {
 545                 mode_t orig_file_mask = 0;
 546                 int is_tmp = file_is_tmp(fn);
 547
 548                 if (is_tmp && (mode[0] == 'w'))
 549                         orig_file_mask = umask(S_IWGRP | S_IWOTH |
 550                             S_IRGRP | S_IROTH);
 551
 552                 if (is_tmp && (compress_program != NULL)) {
 553                         char *cmd;
 554                         size_t cmdsz;
 555
 556                         cmdsz = strlen(fn) + 128;
 557                         cmd = sort_malloc(cmdsz);
 558
 559                         fflush(stdout);
 560
 561                         if (mode[0] == 'r')
 562                                 snprintf(cmd, cmdsz - 1, "cat %s | %s -d",
 563                                     fn, compress_program);
 564                         else if (mode[0] == 'w')
 565                                 snprintf(cmd, cmdsz - 1, "%s > %s",
 566                                     compress_program, fn);
 567                         else
 568                                 err(2, "%s", getstr(7));
 569
 570                         if ((file = popen(cmd, mode)) == NULL)
 571                                 err(2, NULL);
 572
 573                         sort_free(cmd);
 574
 575                 } else
 576                         if ((file = fopen(fn, mode)) == NULL)
 577                                 err(2, NULL);
 578
 579                 if (is_tmp && (mode[0] == 'w'))
 580                         umask(orig_file_mask);
 581         }
 582
 583         return (file);
 584 }
 585
 586 /*
 587  * Close file
 588  */
 589 void
 590 closefile(FILE *f, const char *fn)
 591 {
 592         if (f == NULL) {
 593                 ;
 594         } else if (f == stdin) {
 595                 ;
 596         } else if (f == stdout) {
 597                 fflush(f);
 598         } else {
 599                 if (file_is_tmp(fn) && compress_program != NULL) {
 600                         if(pclose(f)<0)
 601                                 err(2,NULL);
 602                 } else
 603                         fclose(f);
 604         }
 605 }
 606
 607 /*
 608  * Reads a file into the internal buffer.
 609  */
 610 struct file_reader *
 611 file_reader_init(const char *fsrc)
 612 {
 613         struct file_reader *ret;
 614
 615         if (fsrc == NULL)
 616                 fsrc = "-";
 617
 618         ret = sort_calloc(1, sizeof(struct file_reader));
 619
 620         ret->elsymb = '\n';
 621         if (sort_opts_vals.zflag)
 622                 ret->elsymb = 0;
 623
 624         ret->fname = sort_strdup(fsrc);
 625
 626         if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {
 627
 628                 do {
 629                         struct stat stat_buf;
 630                         void *addr;
 631                         size_t sz = 0;
 632                         int fd, flags;
 633
 634                         flags = MAP_NOCORE | MAP_NOSYNC;
 635
 636                         fd = open(fsrc, O_RDONLY);
 637                         if (fd < 0)
 638                                 err(2, NULL);
 639
 640                         if (fstat(fd, &stat_buf) < 0) {
 641                                 close(fd);
 642                                 break;
 643                         }
 644
 645                         sz = stat_buf.st_size;
 646
 647 #if defined(MAP_PREFAULT_READ)
 648                         flags |= MAP_PREFAULT_READ;
 649 #endif
 650
 651                         addr = mmap(NULL, sz, PROT_READ, flags, fd, 0);
 652                         if (addr == MAP_FAILED) {
 653                                 close(fd);
 654                                 break;
 655                         }
 656
 657                         ret->fd = fd;
 658                         ret->mmapaddr = addr;
 659                         ret->mmapsize = sz;
 660                         ret->mmapptr = ret->mmapaddr;
 661
 662                 } while (0);
 663         }
 664
 665         if (ret->mmapaddr == NULL) {
 666                 ret->file = openfile(fsrc, "r");
 667                 if (ret->file == NULL)
 668                         err(2, NULL);
 669
 670                 if (strcmp(fsrc, "-")) {
 671                         ret->cbsz = READ_CHUNK;
 672                         ret->buffer = sort_malloc(ret->cbsz);
 673                         ret->bsz = 0;
 674                         ret->strbeg = 0;
 675
 676                         ret->bsz = fread(ret->buffer, 1, ret->cbsz, ret->file);
 677                         if (ret->bsz == 0) {
 678                                 if (ferror(ret->file))
 679                                         err(2, NULL);
 680                         }
 681                 }
 682         }
 683
 684         return (ret);
 685 }
 686
 687 struct bwstring *
 688 file_reader_readline(struct file_reader *fr)
 689 {
 690         struct bwstring *ret = NULL;
 691
 692         if (fr->mmapaddr) {
 693                 unsigned char *mmapend;
 694
 695                 mmapend = fr->mmapaddr + fr->mmapsize;
 696                 if (fr->mmapptr >= mmapend)
 697                         return (NULL);
 698                 else {
 699                         unsigned char *strend;
 700                         size_t sz;
 701
 702                         sz = mmapend - fr->mmapptr;
 703                         strend = memchr(fr->mmapptr, fr->elsymb, sz);
 704
 705                         if (strend == NULL) {
 706                                 ret = bwscsbdup(fr->mmapptr, sz);
 707                                 fr->mmapptr = mmapend;
 708                         } else {
 709                                 ret = bwscsbdup(fr->mmapptr, strend -
 710                                     fr->mmapptr);
 711                                 fr->mmapptr = strend + 1;
 712                         }
 713                 }
 714
 715         } else if (fr->file != stdin) {
 716                 char *strend;
 717                 size_t bsz1, remsz, search_start;
 718
 719                 search_start = 0;
 720                 remsz = 0;
 721                 strend = NULL;
 722
 723                 if (fr->bsz > fr->strbeg)
 724                         remsz = fr->bsz - fr->strbeg;
 725
 726                 /* line read cycle */
 727                 for (;;) {
 728                         if (remsz > search_start)
 729                                 strend = memchr(fr->buffer + fr->strbeg +
 730                                     search_start, fr->elsymb, remsz -
 731                                     search_start);
 732                         else
 733                                 strend = NULL;
 734
 735                         if (strend)
 736                                 break;
 737                         if (feof(fr->file))
 738                                 break;
 739
 740                         if (fr->bsz != fr->cbsz)
 741                                 /* NOTREACHED */
 742                                 err(2, "File read software error 1");
 743
 744                         if (remsz > (READ_CHUNK >> 1)) {
 745                                 search_start = fr->cbsz - fr->strbeg;
 746                                 fr->cbsz += READ_CHUNK;
 747                                 fr->buffer = sort_realloc(fr->buffer,
 748                                     fr->cbsz);
 749                                 bsz1 = fread(fr->buffer + fr->bsz, 1,
 750                                     READ_CHUNK, fr->file);
 751                                 if (bsz1 == 0) {
 752                                         if (ferror(fr->file))
 753                                                 err(2, NULL);
 754                                         break;
 755                                 }
 756                                 fr->bsz += bsz1;
 757                                 remsz += bsz1;
 758                         } else {
 759                                 if (remsz > 0 && fr->strbeg>0)
 760                                         bcopy(fr->buffer + fr->strbeg,
 761                                             fr->buffer, remsz);
 762
 763                                 fr->strbeg = 0;
 764                                 search_start = remsz;
 765                                 bsz1 = fread(fr->buffer + remsz, 1,
 766                                     fr->cbsz - remsz, fr->file);
 767                                 if (bsz1 == 0) {
 768                                         if (ferror(fr->file))
 769                                                 err(2, NULL);
 770                                         break;
 771                                 }
 772                                 fr->bsz = remsz + bsz1;
 773                                 remsz = fr->bsz;
 774                         }
 775                 }
 776
 777                 if (strend == NULL)
 778                         strend = fr->buffer + fr->bsz;
 779
 780                 if ((fr->buffer + fr->strbeg <= strend) &&
 781                     (fr->strbeg < fr->bsz) && (remsz>0))
 782                         ret = bwscsbdup(fr->buffer + fr->strbeg, strend -
 783                             fr->buffer - fr->strbeg);
 784
 785                 fr->strbeg = (strend - fr->buffer) + 1;
 786
 787         } else {
 788                 int delim = sort_opts_vals.zflag ? '\0' : '\n';
 789                 ssize_t len = getdelim(&fr->buffer, &fr->bsz, delim, fr->file);
 790                 if (len < 0) {
 791                         if (!feof(fr->file))
 792                                 err(2, NULL);
 793                         return (NULL);
 794                 }
 795                 if (len > 0 && fr->buffer[len - 1] == delim)
 796                         len--;
 797                 ret = bwscsbdup(fr->buffer, len);
 798         }
 799
 800         return (ret);
 801 }
 802
 803 static void
 804 file_reader_clean(struct file_reader *fr)
 805 {
 806
 807         if (fr) {
 808                 if (fr->mmapaddr)
 809                         munmap(fr->mmapaddr, fr->mmapsize);
 810
 811                 if (fr->fd)
 812                         close(fr->fd);
 813
 814                 if (fr->buffer)
 815                         sort_free(fr->buffer);
 816
 817                 if (fr->file)
 818                         if (fr->file != stdin)
 819                                 closefile(fr->file, fr->fname);
 820
 821                 if(fr->fname)
 822                         sort_free(fr->fname);
 823
 824                 memset(fr, 0, sizeof(struct file_reader));
 825         }
 826 }
 827
 828 void
 829 file_reader_free(struct file_reader *fr)
 830 {
 831
 832         if (fr) {
 833                 file_reader_clean(fr);
 834                 sort_free(fr);
 835         }
 836 }
 837
 838 int
 839 procfile(const char *fsrc, struct sort_list *list, struct file_list *fl)
 840 {
 841         struct file_reader *fr;
 842
 843         fr = file_reader_init(fsrc);
 844         if (fr == NULL)
 845                 err(2, NULL);
 846
 847         /* file browse cycle */
 848         for (;;) {
 849                 struct bwstring *bws;
 850
 851                 bws = file_reader_readline(fr);
 852
 853                 if (bws == NULL)
 854                         break;
 855
 856                 sort_list_add(list, bws);
 857
 858                 if (list->memsize >= available_free_memory) {
 859                         char *fn;
 860
 861                         fn = new_tmp_file_name();
 862                         sort_list_to_file(list, fn);
 863                         file_list_add(fl, fn, false);
 864                         sort_list_clean(list);
 865                 }
 866         }
 867
 868         file_reader_free(fr);
 869
 870         return (0);
 871 }
 872
 873 /*
 874  * Compare file headers. Files with EOF always go to the end of the list.
 875  */
 876 static int
 877 file_header_cmp(struct file_header *f1, struct file_header *f2)
 878 {
 879
 880         if (f1 == f2)
 881                 return (0);
 882         else {
 883                 if (f1->fr == NULL) {
 884                         return ((f2->fr == NULL) ? 0 : +1);
 885                 } else if (f2->fr == NULL)
 886                         return (-1);
 887                 else {
 888                         int ret;
 889
 890                         ret = list_coll(&(f1->si), &(f2->si));
 891                         if (!ret)
 892                                 return ((f1->file_pos < f2->file_pos) ? -1 : +1);
 893                         return (ret);
 894                 }
 895         }
 896 }
 897
 898 /*
 899  * Allocate and init file header structure
 900  */
 901 static void
 902 file_header_init(struct file_header **fh, const char *fn, size_t file_pos)
 903 {
 904
 905         if (fh && fn) {
 906                 struct bwstring *line;
 907
 908                 *fh = sort_malloc(sizeof(struct file_header));
 909                 (*fh)->file_pos = file_pos;
 910                 (*fh)->fr = file_reader_init(fn);
 911                 if ((*fh)->fr == NULL) {
 912                         perror(fn);
 913                         err(2, "%s", getstr(8));
 914                 }
 915                 line = file_reader_readline((*fh)->fr);
 916                 if (line == NULL) {
 917                         file_reader_free((*fh)->fr);
 918                         (*fh)->fr = NULL;
 919                         (*fh)->si = NULL;
 920                 } else {
 921                         (*fh)->si = sort_list_item_alloc();
 922                         sort_list_item_set((*fh)->si, line);
 923                 }
 924         }
 925 }
 926
 927 /*
 928  * Close file
 929  */
 930 static void
 931 file_header_close(struct file_header **fh)
 932 {
 933
 934         if (fh && *fh) {
 935                 if ((*fh)->fr) {
 936                         file_reader_free((*fh)->fr);
 937                         (*fh)->fr = NULL;
 938                 }
 939                 if ((*fh)->si) {
 940                         sort_list_item_clean((*fh)->si);
 941                         sort_free((*fh)->si);
 942                         (*fh)->si = NULL;
 943                 }
 944                 sort_free(*fh);
 945                 *fh = NULL;
 946         }
 947 }
 948
 949 /*
 950  * Swap two array elements
 951  */
 952 static void
 953 file_header_swap(struct file_header **fh, size_t i1, size_t i2)
 954 {
 955         struct file_header *tmp;
 956
 957         tmp = fh[i1];
 958         fh[i1] = fh[i2];
 959         fh[i2] = tmp;
 960 }
 961
 962 /* heap algorithm ==>> */
 963
 964 /*
 965  * See heap sort algorithm
 966  * "Raises" last element to its right place
 967  */
 968 static void
 969 file_header_heap_swim(struct file_header **fh, size_t indx)
 970 {
 971
 972         if (indx > 0) {
 973                 size_t parent_index;
 974
 975                 parent_index = (indx - 1) >> 1;
 976
 977                 if (file_header_cmp(fh[indx], fh[parent_index]) < 0) {
 978                         /* swap child and parent and continue */
 979                         file_header_swap(fh, indx, parent_index);
 980                         file_header_heap_swim(fh, parent_index);
 981                 }
 982         }
 983 }
 984
 985 /*
 986  * Sink the top element to its correct position
 987  */
 988 static void
 989 file_header_heap_sink(struct file_header **fh, size_t indx, size_t size)
 990 {
 991         size_t left_child_index;
 992         size_t right_child_index;
 993
 994         left_child_index = indx + indx + 1;
 995         right_child_index = left_child_index + 1;
 996
 997         if (left_child_index < size) {
 998                 size_t min_child_index;
 999
1000                 min_child_index = left_child_index;
1001
1002                 if ((right_child_index < size) &&
1003                     (file_header_cmp(fh[left_child_index],
1004                     fh[right_child_index]) > 0))
1005                         min_child_index = right_child_index;
1006                 if (file_header_cmp(fh[indx], fh[min_child_index]) > 0) {
1007                         file_header_swap(fh, indx, min_child_index);
1008                         file_header_heap_sink(fh, min_child_index, size);
1009                 }
1010         }
1011 }
1012
1013 /* <<== heap algorithm */
1014
1015 /*
1016  * Adds element to the "left" end
1017  */
1018 static void
1019 file_header_list_rearrange_from_header(struct file_header **fh, size_t size)
1020 {
1021
1022         file_header_heap_sink(fh, 0, size);
1023 }
1024
1025 /*
1026  * Adds element to the "right" end
1027  */
1028 static void
1029 file_header_list_push(struct file_header *f, struct file_header **fh, size_t size)
1030 {
1031
1032         fh[size++] = f;
1033         file_header_heap_swim(fh, size - 1);
1034 }
1035
1036 struct last_printed
1037 {
1038         struct bwstring *str;
1039 };
1040
1041 /*
1042  * Prints the current line of the file
1043  */
1044 static void
1045 file_header_print(struct file_header *fh, FILE *f_out, struct last_printed *lp)
1046 {
1047
1048         if (fh && fh->fr && f_out && fh->si && fh->si->str) {
1049                 if (sort_opts_vals.uflag) {
1050                         if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {
1051                                 bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1052                                 if (lp->str)
1053                                         bwsfree(lp->str);
1054                                 lp->str = bwsdup(fh->si->str);
1055                         }
1056                 } else
1057                         bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1058         }
1059 }
1060
1061 /*
1062  * Read next line
1063  */
1064 static void
1065 file_header_read_next(struct file_header *fh)
1066 {
1067
1068         if (fh && fh->fr) {
1069                 struct bwstring *tmp;
1070
1071                 tmp = file_reader_readline(fh->fr);
1072                 if (tmp == NULL) {
1073                         file_reader_free(fh->fr);
1074                         fh->fr = NULL;
1075                         if (fh->si) {
1076                                 sort_list_item_clean(fh->si);
1077                                 sort_free(fh->si);
1078                                 fh->si = NULL;
1079                         }
1080                 } else {
1081                         if (fh->si == NULL)
1082                                 fh->si = sort_list_item_alloc();
1083                         sort_list_item_set(fh->si, tmp);
1084                 }
1085         }
1086 }
1087
1088 /*
1089  * Merge array of "files headers"
1090  */
1091 static void
1092 file_headers_merge(size_t fnum, struct file_header **fh, FILE *f_out)
1093 {
1094         struct last_printed lp;
1095         size_t i;
1096
1097         memset(&lp, 0, sizeof(lp));
1098
1099         /*
1100          * construct the initial sort structure
1101          */
1102         for (i = 0; i < fnum; i++)
1103                 file_header_list_push(fh[i], fh, i);
1104
1105         while (fh[0]->fr) { /* unfinished files are always in front */
1106                 /* output the smallest line: */
1107                 file_header_print(fh[0], f_out, &lp);
1108                 /* read a new line, if possible: */
1109                 file_header_read_next(fh[0]);
1110                 /* re-arrange the list: */
1111                 file_header_list_rearrange_from_header(fh, fnum);
1112         }
1113
1114         if (lp.str)
1115                 bwsfree(lp.str);
1116 }
1117
1118 /*
1119  * Merges the given files into the output file, which can be
1120  * stdout.
1121  */
1122 static void
1123 merge_files_array(size_t argc, const char **argv, const char *fn_out)
1124 {
1125
1126         if (argv && fn_out) {
1127                 struct file_header **fh;
1128                 FILE *f_out;
1129                 size_t i;
1130
1131                 f_out = openfile(fn_out, "w");
1132
1133                 if (f_out == NULL)
1134                         err(2, NULL);
1135
1136                 fh = sort_malloc((argc + 1) * sizeof(struct file_header *));
1137
1138                 for (i = 0; i < argc; i++)
1139                         file_header_init(fh + i, argv[i], (size_t) i);
1140
1141                 file_headers_merge(argc, fh, f_out);
1142
1143                 for (i = 0; i < argc; i++)
1144                         file_header_close(fh + i);
1145
1146                 sort_free(fh);
1147
1148                 closefile(f_out, fn_out);
1149         }
1150 }
1151
1152 /*
1153  * Shrinks the file list until its size smaller than max number of opened files
1154  */
1155 static int
1156 shrink_file_list(struct file_list *fl)
1157 {
1158
1159         if ((fl == NULL) || (size_t) (fl->count) < max_open_files)
1160                 return (0);
1161         else {
1162                 struct file_list new_fl;
1163                 size_t indx = 0;
1164
1165                 file_list_init(&new_fl, true);
1166                 while (indx < fl->count) {
1167                         char *fnew;
1168                         size_t num;
1169
1170                         num = fl->count - indx;
1171                         fnew = new_tmp_file_name();
1172
1173                         if ((size_t) num >= max_open_files)
1174                                 num = max_open_files - 1;
1175                         merge_files_array(num, fl->fns + indx, fnew);
1176                         if (fl->tmp) {
1177                                 size_t i;
1178
1179                                 for (i = 0; i < num; i++)
1180                                         unlink(fl->fns[indx + i]);
1181                         }
1182                         file_list_add(&new_fl, fnew, false);
1183                         indx += num;
1184                 }
1185                 fl->tmp = false; /* already taken care of */
1186                 file_list_clean(fl);
1187
1188                 fl->count = new_fl.count;
1189                 fl->fns = new_fl.fns;
1190                 fl->sz = new_fl.sz;
1191                 fl->tmp = new_fl.tmp;
1192
1193                 return (1);
1194         }
1195 }
1196
1197 /*
1198  * Merge list of files
1199  */
1200 void
1201 merge_files(struct file_list *fl, const char *fn_out)
1202 {
1203
1204         if (fl && fn_out) {
1205                 while (shrink_file_list(fl));
1206
1207                 merge_files_array(fl->count, fl->fns, fn_out);
1208         }
1209 }
1210
1211 static const char *
1212 get_sort_method_name(int sm)
1213 {
1214
1215         if (sm == SORT_MERGESORT)
1216                 return "mergesort";
1217         else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1218                 return "radixsort";
1219         else if (sort_opts_vals.sort_method == SORT_HEAPSORT)
1220                 return "heapsort";
1221         else
1222                 return "quicksort";
1223 }
1224
1225 /*
1226  * Wrapper for qsort
1227  */
1228 static int sort_qsort(void *list, size_t count, size_t elem_size,
1229     int (*cmp_func)(const void *, const void *))
1230 {
1231
1232         qsort(list, count, elem_size, cmp_func);
1233         return (0);
1234 }
1235
1236 /*
1237  * Sort list of lines and writes it to the file
1238  */
1239 void
1240 sort_list_to_file(struct sort_list *list, const char *outfile)
1241 {
1242         struct sort_mods *sm = &(keys[0].sm);
1243
1244         if (!(sm->Mflag) && !(sm->Rflag) && !(sm->Vflag) &&
1245             !(sm->gflag) && !(sm->hflag) && !(sm->nflag)) {
1246                 if ((sort_opts_vals.sort_method == SORT_DEFAULT) && byte_sort)
1247                         sort_opts_vals.sort_method = SORT_RADIXSORT;
1248
1249         } else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1250                 err(2, "%s", getstr(9));
1251
1252         /*
1253          * to handle stable sort and the unique cases in the
1254          * right order, we need stable basic algorithm
1255          */
1256         if (sort_opts_vals.sflag) {
1257                 switch (sort_opts_vals.sort_method){
1258                 case SORT_MERGESORT:
1259                         break;
1260                 case SORT_RADIXSORT:
1261                         break;
1262                 case SORT_DEFAULT:
1263                         sort_opts_vals.sort_method = SORT_MERGESORT;
1264                         break;
1265                 default:
1266                         errx(2, "%s", getstr(10));
1267                 }
1268         }
1269
1270         if (sort_opts_vals.sort_method == SORT_DEFAULT)
1271                 sort_opts_vals.sort_method = DEFAULT_SORT_ALGORITHM;
1272
1273         if (debug_sort)
1274                 printf("sort_method=%s\n",
1275                     get_sort_method_name(sort_opts_vals.sort_method));
1276
1277         switch (sort_opts_vals.sort_method){
1278         case SORT_RADIXSORT:
1279                 rxsort(list->list, list->count);
1280                 sort_list_dump(list, outfile);
1281                 break;
1282         case SORT_MERGESORT:
1283                 mt_sort(list, mergesort, outfile);
1284                 break;
1285         case SORT_HEAPSORT:
1286                 mt_sort(list, heapsort, outfile);
1287                 break;
1288         case SORT_QSORT:
1289                 mt_sort(list, sort_qsort, outfile);
1290                 break;
1291         default:
1292                 mt_sort(list, DEFAULT_SORT_FUNC, outfile);
1293                 break;
1294         }
1295 }
1296
1297 /******************* MT SORT ************************/
1298
1299 #if defined(SORT_THREADS)
1300 /* semaphore to count threads */
1301 static sem_t mtsem;
1302
1303 /* current system sort function */
1304 static int (*g_sort_func)(void *, size_t, size_t,
1305     int(*)(const void *, const void *));
1306
1307 /*
1308  * Sort cycle thread (in multi-threaded mode)
1309  */
1310 static void*
1311 mt_sort_thread(void* arg)
1312 {
1313         struct sort_list *list = arg;
1314
1315         g_sort_func(list->list, list->count, sizeof(struct sort_list_item *),
1316             (int(*)(const void *, const void *)) list_coll);
1317
1318         sem_post(&mtsem);
1319
1320         return (arg);
1321 }
1322
1323 /*
1324  * Compare sub-lists. Empty sub-lists always go to the end of the list.
1325  */
1326 static int
1327 sub_list_cmp(struct sort_list *l1, struct sort_list *l2)
1328 {
1329
1330         if (l1 == l2)
1331                 return (0);
1332         else {
1333                 if (l1->count == 0) {
1334                         return ((l2->count == 0) ? 0 : +1);
1335                 } else if (l2->count == 0) {
1336                         return (-1);
1337                 } else {
1338                         int ret;
1339
1340                         ret = list_coll(&(l1->list[0]), &(l2->list[0]));
1341                         if (!ret)
1342                                 return ((l1->sub_list_pos < l2->sub_list_pos) ?
1343                                     -1 : +1);
1344                         return (ret);
1345                 }
1346         }
1347 }
1348
1349 /*
1350  * Swap two array elements
1351  */
1352 static void
1353 sub_list_swap(struct sort_list **sl, size_t i1, size_t i2)
1354 {
1355         struct sort_list *tmp;
1356
1357         tmp = sl[i1];
1358         sl[i1] = sl[i2];
1359         sl[i2] = tmp;
1360 }
1361
1362 /* heap algorithm ==>> */
1363
1364 /*
1365  * See heap sort algorithm
1366  * "Raises" last element to its right place
1367  */
1368 static void
1369 sub_list_swim(struct sort_list **sl, size_t indx)
1370 {
1371
1372         if (indx > 0) {
1373                 size_t parent_index;
1374
1375                 parent_index = (indx - 1) >> 1;
1376
1377                 if (sub_list_cmp(sl[indx], sl[parent_index]) < 0) {
1378                         /* swap child and parent and continue */
1379                         sub_list_swap(sl, indx, parent_index);
1380                         sub_list_swim(sl, parent_index);
1381                 }
1382         }
1383 }
1384
1385 /*
1386  * Sink the top element to its correct position
1387  */
1388 static void
1389 sub_list_sink(struct sort_list **sl, size_t indx, size_t size)
1390 {
1391         size_t left_child_index;
1392         size_t right_child_index;
1393
1394         left_child_index = indx + indx + 1;
1395         right_child_index = left_child_index + 1;
1396
1397         if (left_child_index < size) {
1398                 size_t min_child_index;
1399
1400                 min_child_index = left_child_index;
1401
1402                 if ((right_child_index < size) &&
1403                     (sub_list_cmp(sl[left_child_index],
1404                     sl[right_child_index]) > 0))
1405                         min_child_index = right_child_index;
1406                 if (sub_list_cmp(sl[indx], sl[min_child_index]) > 0) {
1407                         sub_list_swap(sl, indx, min_child_index);
1408                         sub_list_sink(sl, min_child_index, size);
1409                 }
1410         }
1411 }
1412
1413 /* <<== heap algorithm */
1414
1415 /*
1416  * Adds element to the "right" end
1417  */
1418 static void
1419 sub_list_push(struct sort_list *s, struct sort_list **sl, size_t size)
1420 {
1421
1422         sl[size++] = s;
1423         sub_list_swim(sl, size - 1);
1424 }
1425
1426 struct last_printed_item
1427 {
1428         struct sort_list_item *item;
1429 };
1430
1431 /*
1432  * Prints the current line of the file
1433  */
1434 static void
1435 sub_list_header_print(struct sort_list *sl, FILE *f_out,
1436     struct last_printed_item *lp)
1437 {
1438
1439         if (sl && sl->count && f_out && sl->list[0]->str) {
1440                 if (sort_opts_vals.uflag) {
1441                         if ((lp->item == NULL) || (list_coll(&(lp->item),
1442                             &(sl->list[0])))) {
1443                                 bwsfwrite(sl->list[0]->str, f_out,
1444                                     sort_opts_vals.zflag);
1445                                 lp->item = sl->list[0];
1446                         }
1447                 } else
1448                         bwsfwrite(sl->list[0]->str, f_out,
1449                             sort_opts_vals.zflag);
1450         }
1451 }
1452
1453 /*
1454  * Read next line
1455  */
1456 static void
1457 sub_list_next(struct sort_list *sl)
1458 {
1459
1460         if (sl && sl->count) {
1461                 sl->list += 1;
1462                 sl->count -= 1;
1463         }
1464 }
1465
1466 /*
1467  * Merge sub-lists to a file
1468  */
1469 static void
1470 merge_sub_lists(struct sort_list **sl, size_t n, FILE* f_out)
1471 {
1472         struct last_printed_item lp;
1473         size_t i;
1474
1475         memset(&lp,0,sizeof(lp));
1476
1477         /* construct the initial list: */
1478         for (i = 0; i < n; i++)
1479                 sub_list_push(sl[i], sl, i);
1480
1481         while (sl[0]->count) { /* unfinished lists are always in front */
1482                 /* output the smallest line: */
1483                 sub_list_header_print(sl[0], f_out, &lp);
1484                 /* move to a new line, if possible: */
1485                 sub_list_next(sl[0]);
1486                 /* re-arrange the list: */
1487                 sub_list_sink(sl, 0, n);
1488         }
1489 }
1490
1491 /*
1492  * Merge sub-lists to a file
1493  */
1494 static void
1495 merge_list_parts(struct sort_list **parts, size_t n, const char *fn)
1496 {
1497         FILE* f_out;
1498
1499         f_out = openfile(fn,"w");
1500
1501         merge_sub_lists(parts, n, f_out);
1502
1503         closefile(f_out, fn);
1504 }
1505
1506 #endif /* defined(SORT_THREADS) */
1507 /*
1508  * Multi-threaded sort algorithm "driver"
1509  */
1510 static void
1511 mt_sort(struct sort_list *list,
1512     int(*sort_func)(void *, size_t, size_t, int(*)(const void *, const void *)),
1513     const char* fn)
1514 {
1515 #if defined(SORT_THREADS)
1516         if (nthreads < 2 || list->count < MT_SORT_THRESHOLD) {
1517                 size_t nthreads_save = nthreads;
1518                 nthreads = 1;
1519 #endif
1520                 /* if single thread or small data, do simple sort */
1521                 sort_func(list->list, list->count,
1522                     sizeof(struct sort_list_item *),
1523                     (int(*)(const void *, const void *)) list_coll);
1524                 sort_list_dump(list, fn);
1525 #if defined(SORT_THREADS)
1526                 nthreads = nthreads_save;
1527         } else {
1528                 /* multi-threaded sort */
1529                 struct sort_list **parts;
1530                 size_t avgsize, cstart, i;
1531
1532                 /* array of sub-lists */
1533                 parts = sort_malloc(sizeof(struct sort_list*) * nthreads);
1534                 cstart = 0;
1535                 avgsize = list->count / nthreads;
1536
1537                 /* set global system sort function */
1538                 g_sort_func = sort_func;
1539
1540                 /* set sublists */
1541                 for (i = 0; i < nthreads; ++i) {
1542                         size_t sz = 0;
1543
1544                         parts[i] = sort_malloc(sizeof(struct sort_list));
1545                         parts[i]->list = list->list + cstart;
1546                         parts[i]->memsize = 0;
1547                         parts[i]->sub_list_pos = i;
1548
1549                         sz = (i == nthreads - 1) ? list->count - cstart :
1550                             avgsize;
1551
1552                         parts[i]->count = sz;
1553
1554                         parts[i]->size = parts[i]->count;
1555
1556                         cstart += sz;
1557                 }
1558
1559                 /* init threads counting semaphore */
1560                 sem_init(&mtsem, 0, 0);
1561
1562                 /* start threads */
1563                 for (i = 0; i < nthreads; ++i) {
1564                         pthread_t pth;
1565                         pthread_attr_t attr;
1566
1567                         pthread_attr_init(&attr);
1568                         pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
1569
1570                         for (;;) {
1571                                 int res = pthread_create(&pth, &attr,
1572                                     mt_sort_thread, parts[i]);
1573
1574                                 if (res >= 0)
1575                                         break;
1576                                 if (errno == EAGAIN) {
1577                                         pthread_yield();
1578                                         continue;
1579                                 }
1580                                 err(2, NULL);
1581                         }
1582
1583                         pthread_attr_destroy(&attr);
1584                 }
1585
1586                 /* wait for threads completion */
1587                 for (i = 0; i < nthreads; ++i) {
1588                         sem_wait(&mtsem);
1589                 }
1590                 /* destroy the semaphore - we do not need it anymore */
1591                 sem_destroy(&mtsem);
1592
1593                 /* merge sorted sub-lists to the file */
1594                 merge_list_parts(parts, nthreads, fn);
1595
1596                 /* free sub-lists data */
1597                 for (i = 0; i < nthreads; ++i) {
1598                         sort_free(parts[i]);
1599                 }
1600                 sort_free(parts);
1601         }
1602 #endif /* defined(SORT_THREADS) */
1603 }