[BACK]Return to file.c CVS log [TXT][DIR] Up to [local] / src / usr.bin / sort

Annotation of src/usr.bin/sort/file.c, Revision 1.16

1.15      millert     1: /*     $OpenBSD: file.c,v 1.14 2015/04/01 22:43:16 deraadt Exp $       */
1.1       millert     2:
                      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/mman.h>
                     31: #include <sys/stat.h>
                     32: #include <sys/types.h>
                     33: #include <sys/queue.h>
                     34:
                     35: #include <err.h>
                     36: #include <fcntl.h>
                     37: #include <stdio.h>
                     38: #include <stdlib.h>
1.14      deraadt    39: #include <signal.h>
1.1       millert    40: #include <string.h>
                     41: #include <unistd.h>
                     42: #include <wchar.h>
                     43: #include <wctype.h>
                     44:
                     45: #include "coll.h"
                     46: #include "file.h"
                     47: #include "radixsort.h"
                     48:
                     49: unsigned long long free_memory = 1000000;
                     50: unsigned long long available_free_memory = 1000000;
                     51:
                     52: bool use_mmap;
                     53:
                     54: const char *tmpdir = "/var/tmp";
                     55: const char *compress_program;
                     56:
                     57: size_t max_open_files = 16;
                     58:
                     59: /*
                     60:  * How much space we read from file at once
                     61:  */
                     62: #define READ_CHUNK 4096
                     63:
                     64: /*
                     65:  * File reader structure
                     66:  */
                     67: struct file_reader {
                     68:        struct reader_buffer     rb;
                     69:        FILE                    *file;
                     70:        char                    *fname;
                     71:        unsigned char           *buffer;
                     72:        unsigned char           *mmapaddr;
                     73:        unsigned char           *mmapptr;
                     74:        size_t                   bsz;
                     75:        size_t                   cbsz;
                     76:        size_t                   mmapsize;
                     77:        size_t                   strbeg;
                     78:        char                     elsymb;
                     79: };
                     80:
                     81: /*
                     82:  * Structure to be used in file merge process.
                     83:  */
                     84: struct file_header {
                     85:        struct file_reader              *fr;
                     86:        struct sort_list_item           *si; /* current top line */
                     87:        size_t                           file_pos;
                     88: };
                     89:
                     90: /*
                     91:  * List elements of "cleanable" files list.
                     92:  */
                     93: struct CLEANABLE_FILE {
                     94:        char                            *fn;
                     95:        LIST_ENTRY(CLEANABLE_FILE)       files;
                     96: };
                     97:
                     98: /*
                     99:  * List header of "cleanable" files list.
                    100:  */
                    101: static LIST_HEAD(CLEANABLE_FILES, CLEANABLE_FILE) tmp_files;
                    102:
                    103: /*
                    104:  * Init tmp files list
                    105:  */
                    106: void
                    107: init_tmp_files(void)
                    108: {
                    109:        LIST_INIT(&tmp_files);
                    110: }
                    111:
                    112: /*
                    113:  * Save name of a tmp file for signal cleanup
                    114:  */
                    115: void
                    116: tmp_file_atexit(const char *tmp_file)
                    117: {
1.12      millert   118:        struct CLEANABLE_FILE *item;
1.14      deraadt   119:        sigset_t mask, oldmask;
1.12      millert   120:
                    121:        item = sort_malloc(sizeof(struct CLEANABLE_FILE));
                    122:        item->fn = sort_strdup(tmp_file);
1.14      deraadt   123:
                    124:        sigfillset(&mask);
                    125:        sigprocmask(SIG_BLOCK, &mask, &oldmask);
1.12      millert   126:        LIST_INSERT_HEAD(&tmp_files, item, files);
1.14      deraadt   127:        sigprocmask(SIG_SETMASK, &oldmask, NULL);
1.1       millert   128: }
                    129:
                    130: /*
                    131:  * Clear tmp files
                    132:  */
                    133: void
                    134: clear_tmp_files(void)
                    135: {
                    136:        struct CLEANABLE_FILE *item;
                    137:
                    138:        LIST_FOREACH(item, &tmp_files, files) {
                    139:                if (item != NULL && item->fn != NULL)
                    140:                        unlink(item->fn);
                    141:        }
                    142: }
                    143:
                    144: /*
                    145:  * Check whether a file is a temporary file
                    146:  */
                    147: static bool
                    148: file_is_tmp(const char *fn)
                    149: {
                    150:        struct CLEANABLE_FILE *item;
                    151:
1.12      millert   152:        LIST_FOREACH(item, &tmp_files, files) {
                    153:                if (item->fn != NULL && strcmp(item->fn, fn) == 0)
                    154:                        return true;
1.1       millert   155:        }
                    156:
1.12      millert   157:        return false;
1.1       millert   158: }
                    159:
                    160: /*
                    161:  * Generate new temporary file name
                    162:  */
                    163: char *
                    164: new_tmp_file_name(void)
                    165: {
                    166:        char *ret;
1.7       tobias    167:        int fd;
1.1       millert   168:
1.7       tobias    169:        sort_asprintf(&ret, "%s/.bsdsort.XXXXXXXXXX", tmpdir);
                    170:        if ((fd = mkstemp(ret)) == -1)
                    171:                err(2, "%s", ret);
                    172:        close(fd);
1.1       millert   173:        tmp_file_atexit(ret);
                    174:        return ret;
                    175: }
                    176:
                    177: /*
                    178:  * Initialize file list
                    179:  */
                    180: void
                    181: file_list_init(struct file_list *fl, bool tmp)
                    182: {
1.12      millert   183:        fl->count = 0;
                    184:        fl->sz = 0;
                    185:        fl->fns = NULL;
                    186:        fl->tmp = tmp;
1.1       millert   187: }
                    188:
                    189: /*
                    190:  * Add a file name to the list
                    191:  */
                    192: void
                    193: file_list_add(struct file_list *fl, char *fn, bool allocate)
                    194: {
1.12      millert   195:        if (fl->count >= fl->sz) {
                    196:                fl->fns = sort_reallocarray(fl->fns,
                    197:                    fl->sz ? fl->sz : (fl->sz = 1), 2 * sizeof(char *));
                    198:                fl->sz *= 2;
1.1       millert   199:        }
1.12      millert   200:        fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;
                    201:        fl->count += 1;
1.1       millert   202: }
                    203:
                    204: /*
                    205:  * Populate file list from array of file names
                    206:  */
                    207: void
                    208: file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate)
                    209: {
1.12      millert   210:        int i;
1.1       millert   211:
1.12      millert   212:        for (i = 0; i < argc; i++)
                    213:                file_list_add(fl, argv[i], allocate);
1.1       millert   214: }
                    215:
                    216: /*
                    217:  * Clean file list data and delete the files,
                    218:  * if this is a list of temporary files
                    219:  */
                    220: void
                    221: file_list_clean(struct file_list *fl)
                    222: {
1.12      millert   223:        if (fl->fns) {
                    224:                size_t i;
1.1       millert   225:
1.12      millert   226:                for (i = 0; i < fl->count; i++) {
                    227:                        if (fl->fns[i]) {
                    228:                                if (fl->tmp)
                    229:                                        unlink(fl->fns[i]);
                    230:                                sort_free(fl->fns[i]);
                    231:                                fl->fns[i] = NULL;
1.1       millert   232:                        }
                    233:                }
1.12      millert   234:                sort_free(fl->fns);
                    235:                fl->fns = NULL;
1.1       millert   236:        }
1.12      millert   237:        fl->sz = 0;
                    238:        fl->count = 0;
                    239:        fl->tmp = false;
1.1       millert   240: }
                    241:
                    242: /*
                    243:  * Init sort list
                    244:  */
                    245: void
                    246: sort_list_init(struct sort_list *l)
                    247: {
1.12      millert   248:        l->count = 0;
                    249:        l->size = 0;
                    250:        l->memsize = sizeof(struct sort_list);
                    251:        l->list = NULL;
1.1       millert   252: }
                    253:
                    254: /*
                    255:  * Add string to sort list
                    256:  */
                    257: void
                    258: sort_list_add(struct sort_list *l, struct bwstring *str)
                    259: {
1.12      millert   260:        size_t indx = l->count;
1.1       millert   261:
1.12      millert   262:        if ((l->list == NULL) || (indx >= l->size)) {
                    263:                size_t newsize = (l->size + 1) + 1024;
1.1       millert   264:
1.12      millert   265:                l->list = sort_reallocarray(l->list, newsize,
                    266:                    sizeof(struct sort_list_item *));
                    267:                l->memsize += (newsize - l->size) *
                    268:                    sizeof(struct sort_list_item *);
                    269:                l->size = newsize;
                    270:        }
                    271:        l->list[indx] = sort_list_item_alloc();
                    272:        sort_list_item_set(l->list[indx], str);
                    273:        l->memsize += sort_list_item_size(l->list[indx]);
                    274:        l->count += 1;
1.1       millert   275: }
                    276:
                    277: /*
                    278:  * Clean sort list data
                    279:  */
                    280: void
                    281: sort_list_clean(struct sort_list *l)
                    282: {
1.12      millert   283:        if (l->list) {
                    284:                size_t i;
1.1       millert   285:
1.12      millert   286:                for (i = 0; i < l->count; i++) {
                    287:                        struct sort_list_item *item;
1.1       millert   288:
1.12      millert   289:                        item = l->list[i];
1.1       millert   290:
1.12      millert   291:                        if (item) {
                    292:                                sort_list_item_clean(item);
                    293:                                sort_free(item);
                    294:                                l->list[i] = NULL;
1.1       millert   295:                        }
                    296:                }
1.12      millert   297:                sort_free(l->list);
                    298:                l->list = NULL;
1.1       millert   299:        }
1.12      millert   300:        l->count = 0;
                    301:        l->size = 0;
                    302:        l->memsize = sizeof(struct sort_list);
1.1       millert   303: }
                    304:
                    305: /*
                    306:  * Write sort list to file
                    307:  */
                    308: void
                    309: sort_list_dump(struct sort_list *l, const char *fn)
                    310: {
1.12      millert   311:        FILE *f;
                    312:
                    313:        f = openfile(fn, "w");
                    314:        if (f == NULL)
                    315:                err(2, "%s", fn);
1.1       millert   316:
1.12      millert   317:        if (l->list) {
                    318:                size_t i;
1.1       millert   319:
1.12      millert   320:                if (!sort_opts_vals.uflag) {
                    321:                        for (i = 0; i < l->count; ++i)
                    322:                                bwsfwrite(l->list[i]->str, f,
                    323:                                    sort_opts_vals.zflag);
                    324:                } else {
                    325:                        struct sort_list_item *last_printed_item = NULL;
                    326:                        struct sort_list_item *item;
                    327:                        for (i = 0; i < l->count; ++i) {
                    328:                                item = l->list[i];
                    329:                                if ((last_printed_item == NULL) ||
                    330:                                    list_coll(&last_printed_item, &item)) {
                    331:                                        bwsfwrite(item->str, f, sort_opts_vals.zflag);
                    332:                                        last_printed_item = item;
1.1       millert   333:                                }
                    334:                        }
                    335:                }
1.12      millert   336:        }
1.1       millert   337:
1.12      millert   338:        closefile(f, fn);
1.1       millert   339: }
                    340:
                    341: /*
                    342:  * Checks if the given file is sorted.  Stops at the first disorder,
                    343:  * prints the disordered line and returns 1.
                    344:  */
                    345: int
                    346: check(const char *fn)
                    347: {
                    348:        struct bwstring *s1, *s2, *s1disorder, *s2disorder;
                    349:        struct file_reader *fr;
                    350:        struct keys_array *ka1, *ka2;
                    351:        int res;
                    352:        size_t pos, posdisorder;
                    353:
                    354:        s1 = s2 = s1disorder = s2disorder = NULL;
                    355:        ka1 = ka2 = NULL;
                    356:
                    357:        fr = file_reader_init(fn);
                    358:
                    359:        res = 0;
                    360:        pos = 1;
                    361:        posdisorder = 1;
                    362:
                    363:        if (fr == NULL) {
                    364:                err(2, "%s", fn);
                    365:                goto end;
                    366:        }
                    367:
                    368:        s1 = file_reader_readline(fr);
                    369:        if (s1 == NULL)
                    370:                goto end;
                    371:
                    372:        ka1 = keys_array_alloc();
                    373:        preproc(s1, ka1);
                    374:
                    375:        s2 = file_reader_readline(fr);
                    376:        if (s2 == NULL)
                    377:                goto end;
                    378:
                    379:        ka2 = keys_array_alloc();
                    380:        preproc(s2, ka2);
                    381:
                    382:        for (;;) {
                    383:
                    384:                if (debug_sort) {
                    385:                        bwsprintf(stdout, s2, "s1=<", ">");
                    386:                        bwsprintf(stdout, s1, "s2=<", ">");
                    387:                }
                    388:                int cmp = key_coll(ka2, ka1, 0);
                    389:                if (debug_sort)
                    390:                        printf("; cmp1=%d", cmp);
                    391:
                    392:                if (!cmp && sort_opts_vals.complex_sort &&
                    393:                    !(sort_opts_vals.uflag) && !(sort_opts_vals.sflag)) {
                    394:                        cmp = top_level_str_coll(s2, s1);
                    395:                        if (debug_sort)
                    396:                                printf("; cmp2=%d", cmp);
                    397:                }
                    398:                if (debug_sort)
                    399:                        printf("\n");
                    400:
                    401:                if ((sort_opts_vals.uflag && (cmp <= 0)) || (cmp < 0)) {
                    402:                        if (!(sort_opts_vals.csilentflag)) {
                    403:                                s2disorder = bwsdup(s2);
                    404:                                posdisorder = pos;
                    405:                                if (debug_sort)
                    406:                                        s1disorder = bwsdup(s1);
                    407:                        }
                    408:                        res = 1;
                    409:                        goto end;
                    410:                }
                    411:
                    412:                pos++;
                    413:
                    414:                clean_keys_array(s1, ka1);
                    415:                sort_free(ka1);
                    416:                ka1 = ka2;
                    417:                ka2 = NULL;
                    418:
                    419:                bwsfree(s1);
                    420:                s1 = s2;
                    421:
                    422:                s2 = file_reader_readline(fr);
                    423:                if (s2 == NULL)
                    424:                        goto end;
                    425:
                    426:                ka2 = keys_array_alloc();
                    427:                preproc(s2, ka2);
                    428:        }
                    429:
                    430: end:
                    431:        if (ka1) {
                    432:                clean_keys_array(s1, ka1);
                    433:                sort_free(ka1);
                    434:        }
                    435:
                    436:        if (s1)
                    437:                bwsfree(s1);
                    438:
                    439:        if (ka2) {
                    440:                clean_keys_array(s2, ka2);
                    441:                sort_free(ka2);
                    442:        }
                    443:
                    444:        if (s2)
                    445:                bwsfree(s2);
                    446:
                    447:        if (fn == NULL || *fn == 0 || strcmp(fn, "-") == 0) {
                    448:                for (;;) {
                    449:                        s2 = file_reader_readline(fr);
                    450:                        if (s2 == NULL)
                    451:                                break;
                    452:                        bwsfree(s2);
                    453:                }
                    454:        }
                    455:
                    456:        file_reader_free(fr);
                    457:
                    458:        if (s2disorder) {
                    459:                bws_disorder_warnx(s2disorder, fn, posdisorder);
                    460:                if (s1disorder) {
                    461:                        bws_disorder_warnx(s1disorder, fn, posdisorder);
                    462:                        if (s1disorder != s2disorder)
                    463:                                bwsfree(s1disorder);
                    464:                }
                    465:                bwsfree(s2disorder);
                    466:                s1disorder = NULL;
                    467:                s2disorder = NULL;
                    468:        }
                    469:
                    470:        if (res)
                    471:                exit(res);
                    472:
                    473:        return 0;
                    474: }
                    475:
                    476: /*
                    477:  * Opens a file.  If the given filename is "-", stdout will be
                    478:  * opened.
                    479:  */
                    480: FILE *
                    481: openfile(const char *fn, const char *mode)
                    482: {
                    483:        FILE *file;
                    484:
                    485:        if (strcmp(fn, "-") == 0) {
                    486:                return (mode && mode[0] == 'r') ? stdin : stdout;
                    487:        } else {
                    488:                mode_t orig_file_mask = 0;
                    489:                int is_tmp = file_is_tmp(fn);
                    490:
                    491:                if (is_tmp && (mode[0] == 'w'))
                    492:                        orig_file_mask = umask(S_IWGRP | S_IWOTH |
                    493:                            S_IRGRP | S_IROTH);
                    494:
                    495:                if (is_tmp && (compress_program != NULL)) {
                    496:                        char *cmd;
                    497:
                    498:                        fflush(stdout);
                    499:
                    500:                        if (mode[0] == 'r')
1.6       millert   501:                                sort_asprintf(&cmd, "%s -d < %s",
1.5       tobias    502:                                    compress_program, fn);
1.1       millert   503:                        else if (mode[0] == 'w')
1.6       millert   504:                                sort_asprintf(&cmd, "%s > %s",
1.1       millert   505:                                    compress_program, fn);
                    506:                        else
                    507:                                err(2, "Wrong file mode");
                    508:
                    509:                        if ((file = popen(cmd, mode)) == NULL)
                    510:                                err(2, NULL);
                    511:
                    512:                        sort_free(cmd);
                    513:
                    514:                } else if ((file = fopen(fn, mode)) == NULL)
                    515:                        err(2, "%s", fn);
                    516:
                    517:                if (is_tmp && (mode[0] == 'w'))
                    518:                        umask(orig_file_mask);
                    519:        }
                    520:
                    521:        return file;
                    522: }
                    523:
                    524: /*
                    525:  * Close file
                    526:  */
                    527: void
                    528: closefile(FILE *f, const char *fn)
                    529: {
                    530:        if (f == NULL) {
                    531:                ;
                    532:        } else if (f == stdin) {
                    533:                ;
                    534:        } else if (f == stdout) {
                    535:                fflush(f);
                    536:        } else {
                    537:                if (file_is_tmp(fn) && compress_program != NULL) {
                    538:                        if (pclose(f) < 0)
                    539:                                err(2, NULL);
                    540:                } else
                    541:                        fclose(f);
                    542:        }
                    543: }
                    544:
                    545: /*
                    546:  * Reads a file into the internal buffer.
                    547:  */
                    548: struct file_reader *
                    549: file_reader_init(const char *fsrc)
                    550: {
                    551:        struct file_reader *ret;
                    552:
                    553:        if (fsrc == NULL)
                    554:                fsrc = "-";
                    555:
1.2       millert   556:        ret = sort_calloc(1, sizeof(struct file_reader));
1.1       millert   557:
                    558:        ret->elsymb = '\n';
                    559:        if (sort_opts_vals.zflag)
                    560:                ret->elsymb = 0;
                    561:
                    562:        ret->fname = sort_strdup(fsrc);
                    563:
                    564:        if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {
                    565:                struct stat stat_buf;
                    566:                void *addr;
                    567:                size_t sz = 0;
                    568:                int fd;
                    569:
                    570:                fd = open(fsrc, O_RDONLY);
                    571:                if (fd < 0)
                    572:                        err(2, "%s", fsrc);
                    573:
                    574:                if (fstat(fd, &stat_buf) < 0)
                    575:                        err(2, "%s", fsrc);
                    576:                sz = stat_buf.st_size;
                    577:
                    578:                addr = mmap(NULL, sz, PROT_READ, 0, fd, 0);
1.16    ! millert   579:                close(fd);
        !           580:                if (addr != MAP_FAILED) {
1.1       millert   581:                        ret->mmapaddr = addr;
                    582:                        ret->mmapsize = sz;
                    583:                        ret->mmapptr = ret->mmapaddr;
                    584:                        posix_madvise(addr, sz, POSIX_MADV_SEQUENTIAL);
                    585:                }
                    586:        }
                    587:
                    588:        if (ret->mmapaddr == NULL) {
                    589:                ret->file = openfile(fsrc, "r");
                    590:                if (ret->file == NULL)
                    591:                        err(2, "%s", fsrc);
                    592:
                    593:                if (strcmp(fsrc, "-")) {
                    594:                        ret->cbsz = READ_CHUNK;
                    595:                        ret->buffer = sort_malloc(ret->cbsz);
                    596:                        ret->bsz = 0;
                    597:                        ret->strbeg = 0;
                    598:
                    599:                        ret->bsz = fread(ret->buffer, 1, ret->cbsz, ret->file);
                    600:                        if (ret->bsz == 0) {
                    601:                                if (ferror(ret->file))
                    602:                                        err(2, NULL);
                    603:                        }
                    604:                }
                    605:        }
                    606:
                    607:        return ret;
                    608: }
                    609:
                    610: struct bwstring *
                    611: file_reader_readline(struct file_reader *fr)
                    612: {
                    613:        struct bwstring *ret = NULL;
                    614:
                    615:        if (fr->mmapaddr) {
                    616:                unsigned char *mmapend;
                    617:
                    618:                mmapend = fr->mmapaddr + fr->mmapsize;
                    619:                if (fr->mmapptr >= mmapend)
                    620:                        return NULL;
                    621:                else {
                    622:                        unsigned char *strend;
                    623:                        size_t sz;
                    624:
                    625:                        sz = mmapend - fr->mmapptr;
                    626:                        strend = memchr(fr->mmapptr, fr->elsymb, sz);
                    627:
                    628:                        if (strend == NULL) {
                    629:                                ret = bwscsbdup(fr->mmapptr, sz);
                    630:                                fr->mmapptr = mmapend;
                    631:                        } else {
                    632:                                ret = bwscsbdup(fr->mmapptr, strend -
                    633:                                    fr->mmapptr);
                    634:                                fr->mmapptr = strend + 1;
                    635:                        }
                    636:                }
                    637:
                    638:        } else if (fr->file != stdin) {
                    639:                unsigned char *strend;
                    640:                size_t bsz1, remsz, search_start;
                    641:
                    642:                search_start = 0;
                    643:                remsz = 0;
                    644:                strend = NULL;
                    645:
                    646:                if (fr->bsz > fr->strbeg)
                    647:                        remsz = fr->bsz - fr->strbeg;
                    648:
                    649:                /* line read cycle */
                    650:                for (;;) {
                    651:                        if (remsz > search_start)
                    652:                                strend = memchr(fr->buffer + fr->strbeg +
                    653:                                    search_start, fr->elsymb, remsz -
                    654:                                    search_start);
                    655:                        else
                    656:                                strend = NULL;
                    657:
                    658:                        if (strend)
                    659:                                break;
                    660:                        if (feof(fr->file))
                    661:                                break;
                    662:
                    663:                        if (fr->bsz != fr->cbsz)
                    664:                                /* NOTREACHED */
                    665:                                err(2, "File read software error 1");
                    666:
                    667:                        if (remsz > (READ_CHUNK >> 1)) {
                    668:                                search_start = fr->cbsz - fr->strbeg;
                    669:                                fr->cbsz += READ_CHUNK;
1.13      millert   670:                                fr->buffer = sort_reallocarray(fr->buffer,
                    671:                                    1, fr->cbsz);
1.1       millert   672:                                bsz1 = fread(fr->buffer + fr->bsz, 1,
                    673:                                    READ_CHUNK, fr->file);
                    674:                                if (bsz1 == 0) {
                    675:                                        if (ferror(fr->file))
                    676:                                                err(2, NULL);
                    677:                                        break;
                    678:                                }
                    679:                                fr->bsz += bsz1;
                    680:                                remsz += bsz1;
                    681:                        } else {
1.12      millert   682:                                if (remsz > 0 && fr->strbeg > 0) {
                    683:                                        memmove(fr->buffer,
                    684:                                            fr->buffer + fr->strbeg, remsz);
                    685:                                }
1.1       millert   686:                                fr->strbeg = 0;
                    687:                                search_start = remsz;
                    688:                                bsz1 = fread(fr->buffer + remsz, 1,
                    689:                                    fr->cbsz - remsz, fr->file);
                    690:                                if (bsz1 == 0) {
                    691:                                        if (ferror(fr->file))
                    692:                                                err(2, NULL);
                    693:                                        break;
                    694:                                }
                    695:                                fr->bsz = remsz + bsz1;
                    696:                                remsz = fr->bsz;
                    697:                        }
                    698:                }
                    699:
                    700:                if (strend == NULL)
                    701:                        strend = fr->buffer + fr->bsz;
                    702:
                    703:                if ((fr->buffer + fr->strbeg <= strend) &&
                    704:                    (fr->strbeg < fr->bsz) && (remsz>0))
                    705:                        ret = bwscsbdup(fr->buffer + fr->strbeg, strend -
                    706:                            fr->buffer - fr->strbeg);
                    707:
                    708:                fr->strbeg = (strend - fr->buffer) + 1;
                    709:        } else {
                    710:                size_t len = 0;
                    711:
                    712:                ret = bwsfgetln(fr->file, &len, sort_opts_vals.zflag,
                    713:                    &(fr->rb));
                    714:        }
                    715:
                    716:        return ret;
                    717: }
                    718:
                    719: static void
                    720: file_reader_clean(struct file_reader *fr)
                    721: {
1.12      millert   722:        if (fr->mmapaddr)
                    723:                munmap(fr->mmapaddr, fr->mmapsize);
1.1       millert   724:
1.12      millert   725:        sort_free(fr->buffer);
1.1       millert   726:
1.12      millert   727:        if (fr->file)
1.15      millert   728:                closefile(fr->file, fr->fname);
1.1       millert   729:
1.12      millert   730:        sort_free(fr->fname);
1.1       millert   731:
1.12      millert   732:        memset(fr, 0, sizeof(struct file_reader));
1.1       millert   733: }
                    734:
                    735: void
                    736: file_reader_free(struct file_reader *fr)
                    737: {
1.12      millert   738:        file_reader_clean(fr);
                    739:        sort_free(fr);
1.1       millert   740: }
                    741:
                    742: int
                    743: procfile(const char *fsrc, struct sort_list *list, struct file_list *fl)
                    744: {
                    745:        struct file_reader *fr;
                    746:
                    747:        fr = file_reader_init(fsrc);
                    748:        if (fr == NULL)
                    749:                err(2, "%s", fsrc);
                    750:
                    751:        /* file browse cycle */
                    752:        for (;;) {
                    753:                struct bwstring *bws;
                    754:
                    755:                bws = file_reader_readline(fr);
                    756:
                    757:                if (bws == NULL)
                    758:                        break;
                    759:
                    760:                sort_list_add(list, bws);
                    761:
                    762:                if (list->memsize >= available_free_memory) {
                    763:                        char *fn;
                    764:
                    765:                        fn = new_tmp_file_name();
                    766:                        sort_list_to_file(list, fn);
                    767:                        file_list_add(fl, fn, false);
                    768:                        sort_list_clean(list);
                    769:                }
                    770:        }
                    771:
                    772:        file_reader_free(fr);
                    773:
                    774:        return 0;
                    775: }
                    776:
                    777: /*
                    778:  * Compare file headers. Files with EOF always go to the end of the list.
                    779:  */
                    780: static int
                    781: file_header_cmp(struct file_header *f1, struct file_header *f2)
                    782: {
1.12      millert   783:        int ret;
                    784:
1.1       millert   785:        if (f1 == f2)
                    786:                return 0;
1.12      millert   787:        if (f1->fr == NULL)
                    788:                return (f2->fr == NULL) ? 0 : 1;
                    789:        if (f2->fr == NULL)
                    790:                return -1;
                    791:
                    792:        ret = list_coll(&(f1->si), &(f2->si));
                    793:        if (!ret)
                    794:                return (f1->file_pos < f2->file_pos) ? -1 : 1;
                    795:        return ret;
1.1       millert   796: }
                    797:
                    798: /*
                    799:  * Allocate and init file header structure
                    800:  */
                    801: static void
                    802: file_header_init(struct file_header **fh, const char *fn, size_t file_pos)
                    803: {
1.12      millert   804:        struct bwstring *line;
1.1       millert   805:
1.12      millert   806:        *fh = sort_malloc(sizeof(struct file_header));
                    807:        (*fh)->file_pos = file_pos;
                    808:        (*fh)->fr = file_reader_init(fn);
                    809:        if ((*fh)->fr == NULL) {
                    810:                err(2, "Cannot open %s for reading",
                    811:                    strcmp(fn, "-") == 0 ? "stdin" : fn);
                    812:        }
                    813:        line = file_reader_readline((*fh)->fr);
                    814:        if (line == NULL) {
                    815:                file_reader_free((*fh)->fr);
                    816:                (*fh)->fr = NULL;
                    817:                (*fh)->si = NULL;
                    818:        } else {
                    819:                (*fh)->si = sort_list_item_alloc();
                    820:                sort_list_item_set((*fh)->si, line);
1.1       millert   821:        }
                    822: }
                    823:
                    824: /*
                    825:  * Close file
                    826:  */
                    827: static void
                    828: file_header_close(struct file_header **fh)
                    829: {
1.12      millert   830:        if ((*fh)->fr) {
                    831:                file_reader_free((*fh)->fr);
                    832:                (*fh)->fr = NULL;
                    833:        }
                    834:        if ((*fh)->si) {
                    835:                sort_list_item_clean((*fh)->si);
                    836:                sort_free((*fh)->si);
                    837:                (*fh)->si = NULL;
1.1       millert   838:        }
1.12      millert   839:        sort_free(*fh);
                    840:        *fh = NULL;
1.1       millert   841: }
                    842:
                    843: /*
                    844:  * Swap two array elements
                    845:  */
                    846: static void
                    847: file_header_swap(struct file_header **fh, size_t i1, size_t i2)
                    848: {
                    849:        struct file_header *tmp;
                    850:
                    851:        tmp = fh[i1];
                    852:        fh[i1] = fh[i2];
                    853:        fh[i2] = tmp;
                    854: }
                    855:
                    856: /* heap algorithm ==>> */
                    857:
                    858: /*
                    859:  * See heap sort algorithm
                    860:  * "Raises" last element to its right place
                    861:  */
                    862: static void
                    863: file_header_heap_swim(struct file_header **fh, size_t indx)
                    864: {
                    865:        if (indx > 0) {
                    866:                size_t parent_index;
                    867:
                    868:                parent_index = (indx - 1) >> 1;
                    869:
                    870:                if (file_header_cmp(fh[indx], fh[parent_index]) < 0) {
                    871:                        /* swap child and parent and continue */
                    872:                        file_header_swap(fh, indx, parent_index);
                    873:                        file_header_heap_swim(fh, parent_index);
                    874:                }
                    875:        }
                    876: }
                    877:
                    878: /*
                    879:  * Sink the top element to its correct position
                    880:  */
                    881: static void
                    882: file_header_heap_sink(struct file_header **fh, size_t indx, size_t size)
                    883: {
                    884:        size_t left_child_index;
                    885:        size_t right_child_index;
                    886:
                    887:        left_child_index = indx + indx + 1;
                    888:        right_child_index = left_child_index + 1;
                    889:
                    890:        if (left_child_index < size) {
                    891:                size_t min_child_index;
                    892:
                    893:                min_child_index = left_child_index;
                    894:
                    895:                if ((right_child_index < size) &&
                    896:                    (file_header_cmp(fh[left_child_index],
                    897:                    fh[right_child_index]) > 0))
                    898:                        min_child_index = right_child_index;
                    899:                if (file_header_cmp(fh[indx], fh[min_child_index]) > 0) {
                    900:                        file_header_swap(fh, indx, min_child_index);
                    901:                        file_header_heap_sink(fh, min_child_index, size);
                    902:                }
                    903:        }
                    904: }
                    905:
                    906: /* <<== heap algorithm */
                    907:
                    908: /*
                    909:  * Adds element to the "left" end
                    910:  */
                    911: static void
                    912: file_header_list_rearrange_from_header(struct file_header **fh, size_t size)
                    913: {
                    914:        file_header_heap_sink(fh, 0, size);
                    915: }
                    916:
                    917: /*
                    918:  * Adds element to the "right" end
                    919:  */
                    920: static void
                    921: file_header_list_push(struct file_header *f, struct file_header **fh, size_t size)
                    922: {
                    923:        fh[size++] = f;
                    924:        file_header_heap_swim(fh, size - 1);
                    925: }
                    926:
                    927: struct last_printed
                    928: {
                    929:        struct bwstring *str;
                    930: };
                    931:
                    932: /*
                    933:  * Prints the current line of the file
                    934:  */
                    935: static void
                    936: file_header_print(struct file_header *fh, FILE *f_out, struct last_printed *lp)
                    937: {
1.12      millert   938:        if (sort_opts_vals.uflag) {
                    939:                if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {
1.1       millert   940:                        bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1.12      millert   941:                        if (lp->str)
                    942:                                bwsfree(lp->str);
                    943:                        lp->str = bwsdup(fh->si->str);
                    944:                }
                    945:        } else
                    946:                bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1.1       millert   947: }
                    948:
                    949: /*
                    950:  * Read next line
                    951:  */
                    952: static void
                    953: file_header_read_next(struct file_header *fh)
                    954: {
1.12      millert   955:        struct bwstring *tmp;
1.1       millert   956:
1.12      millert   957:        tmp = file_reader_readline(fh->fr);
                    958:        if (tmp == NULL) {
                    959:                file_reader_free(fh->fr);
                    960:                fh->fr = NULL;
                    961:                if (fh->si) {
                    962:                        sort_list_item_clean(fh->si);
                    963:                        sort_free(fh->si);
                    964:                        fh->si = NULL;
1.1       millert   965:                }
1.12      millert   966:        } else {
                    967:                if (fh->si == NULL)
                    968:                        fh->si = sort_list_item_alloc();
                    969:                sort_list_item_set(fh->si, tmp);
1.1       millert   970:        }
                    971: }
                    972:
                    973: /*
                    974:  * Merge array of "files headers"
                    975:  */
                    976: static void
                    977: file_headers_merge(size_t fnum, struct file_header **fh, FILE *f_out)
                    978: {
                    979:        struct last_printed lp;
                    980:        size_t i;
                    981:
                    982:        memset(&lp, 0, sizeof(lp));
                    983:
                    984:        /*
                    985:         * construct the initial sort structure
                    986:         */
                    987:        for (i = 0; i < fnum; i++)
                    988:                file_header_list_push(fh[i], fh, i);
                    989:
                    990:        while (fh[0]->fr) { /* unfinished files are always in front */
                    991:                /* output the smallest line: */
                    992:                file_header_print(fh[0], f_out, &lp);
                    993:                /* read a new line, if possible: */
                    994:                file_header_read_next(fh[0]);
                    995:                /* re-arrange the list: */
                    996:                file_header_list_rearrange_from_header(fh, fnum);
                    997:        }
                    998:
                    999:        if (lp.str)
                   1000:                bwsfree(lp.str);
                   1001: }
                   1002:
                   1003: /*
                   1004:  * Merges the given files into the output file, which can be
                   1005:  * stdout.
                   1006:  */
                   1007: static void
                   1008: merge_files_array(size_t argc, char **argv, const char *fn_out)
                   1009: {
1.12      millert  1010:        struct file_header **fh;
                   1011:        FILE *f_out;
                   1012:        size_t i;
1.1       millert  1013:
1.12      millert  1014:        f_out = openfile(fn_out, "w");
1.1       millert  1015:
1.12      millert  1016:        if (f_out == NULL)
                   1017:                err(2, "%s", fn_out);
1.1       millert  1018:
1.12      millert  1019:        fh = sort_reallocarray(NULL, argc + 1, sizeof(struct file_header *));
1.1       millert  1020:
1.12      millert  1021:        for (i = 0; i < argc; i++)
                   1022:                file_header_init(fh + i, argv[i], i);
1.1       millert  1023:
1.12      millert  1024:        file_headers_merge(argc, fh, f_out);
1.1       millert  1025:
1.12      millert  1026:        for (i = 0; i < argc; i++)
                   1027:                file_header_close(fh + i);
1.1       millert  1028:
1.12      millert  1029:        sort_free(fh);
1.1       millert  1030:
1.12      millert  1031:        closefile(f_out, fn_out);
1.1       millert  1032: }
                   1033:
                   1034: /*
                   1035:  * Shrinks the file list until its size smaller than max number of opened files
                   1036:  */
                   1037: static int
                   1038: shrink_file_list(struct file_list *fl)
                   1039: {
1.12      millert  1040:        struct file_list new_fl;
                   1041:        size_t indx = 0;
                   1042:
                   1043:        if (fl->count < max_open_files)
1.1       millert  1044:                return 0;
                   1045:
1.12      millert  1046:        file_list_init(&new_fl, true);
                   1047:        while (indx < fl->count) {
                   1048:                char *fnew;
                   1049:                size_t num;
                   1050:
                   1051:                num = fl->count - indx;
                   1052:                fnew = new_tmp_file_name();
                   1053:
                   1054:                if (num >= max_open_files)
                   1055:                        num = max_open_files - 1;
                   1056:                merge_files_array(num, fl->fns + indx, fnew);
                   1057:                if (fl->tmp) {
                   1058:                        size_t i;
                   1059:
                   1060:                        for (i = 0; i < num; i++)
                   1061:                                unlink(fl->fns[indx + i]);
1.1       millert  1062:                }
1.12      millert  1063:                file_list_add(&new_fl, fnew, false);
                   1064:                indx += num;
                   1065:        }
                   1066:        fl->tmp = false; /* already taken care of */
                   1067:        file_list_clean(fl);
1.1       millert  1068:
1.12      millert  1069:        fl->count = new_fl.count;
                   1070:        fl->fns = new_fl.fns;
                   1071:        fl->sz = new_fl.sz;
                   1072:        fl->tmp = new_fl.tmp;
1.1       millert  1073:
1.12      millert  1074:        return 1;
1.1       millert  1075: }
                   1076:
                   1077: /*
                   1078:  * Merge list of files
                   1079:  */
                   1080: void
                   1081: merge_files(struct file_list *fl, const char *fn_out)
                   1082: {
1.12      millert  1083:        while (shrink_file_list(fl))
                   1084:                ;
1.1       millert  1085:
1.12      millert  1086:        merge_files_array(fl->count, fl->fns, fn_out);
1.1       millert  1087: }
                   1088:
                   1089: static const char *
                   1090: get_sort_method_name(int sm)
                   1091: {
                   1092:        if (sm == SORT_MERGESORT)
                   1093:                return "mergesort";
                   1094:        else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
                   1095:                return "radixsort";
                   1096:        else if (sort_opts_vals.sort_method == SORT_HEAPSORT)
                   1097:                return "heapsort";
                   1098:        else
                   1099:                return "quicksort";
                   1100: }
                   1101:
                   1102: /*
                   1103:  * Sort list of lines and writes it to the file
                   1104:  */
                   1105: void
                   1106: sort_list_to_file(struct sort_list *list, const char *outfile)
                   1107: {
                   1108:        struct sort_mods *sm = &(keys[0].sm);
                   1109:
                   1110:        if (!sm->Mflag && !sm->Rflag && !sm->Vflag &&
                   1111:            !sm->gflag && !sm->hflag && !sm->nflag) {
                   1112:                if ((sort_opts_vals.sort_method == SORT_DEFAULT) && byte_sort)
                   1113:                        sort_opts_vals.sort_method = SORT_RADIXSORT;
                   1114:
                   1115:        } else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
                   1116:                err(2, "Radix sort cannot be used with these sort options");
                   1117:
                   1118:        /*
1.12      millert  1119:         * To handle stable sort and the unique cases in the
                   1120:         * right order, we need to use a stable algorithm.
1.1       millert  1121:         */
                   1122:        if (sort_opts_vals.sflag) {
                   1123:                switch (sort_opts_vals.sort_method){
                   1124:                case SORT_MERGESORT:
                   1125:                        break;
                   1126:                case SORT_RADIXSORT:
                   1127:                        break;
                   1128:                case SORT_DEFAULT:
                   1129:                        sort_opts_vals.sort_method = SORT_MERGESORT;
                   1130:                        break;
                   1131:                default:
                   1132:                        errx(2, "The chosen sort method cannot be used with "
                   1133:                            "stable and/or unique sort");
                   1134:                };
                   1135:        }
                   1136:
                   1137:        if (sort_opts_vals.sort_method == SORT_DEFAULT)
                   1138:                sort_opts_vals.sort_method = DEFAULT_SORT_ALGORITHM;
                   1139:
                   1140:        if (debug_sort)
                   1141:                printf("sort_method=%s\n",
                   1142:                    get_sort_method_name(sort_opts_vals.sort_method));
                   1143:
                   1144:        switch (sort_opts_vals.sort_method){
                   1145:        case SORT_RADIXSORT:
                   1146:                rxsort(list->list, list->count);
                   1147:                break;
                   1148:        case SORT_MERGESORT:
                   1149:                mergesort(list->list, list->count,
                   1150:                    sizeof(struct sort_list_item *), list_coll);
                   1151:                break;
                   1152:        case SORT_HEAPSORT:
                   1153:                heapsort(list->list, list->count,
                   1154:                    sizeof(struct sort_list_item *), list_coll);
                   1155:                break;
                   1156:        case SORT_QSORT:
                   1157:                qsort(list->list, list->count,
                   1158:                    sizeof(struct sort_list_item *), list_coll);
                   1159:                break;
                   1160:        default:
                   1161:                DEFAULT_SORT_FUNC(list->list, list->count,
                   1162:                    sizeof(struct sort_list_item *), list_coll);
                   1163:                break;
                   1164:        }
                   1165:        sort_list_dump(list, outfile);
                   1166: }