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