usr.bin/more/ch.c

/*
 * Copyright (c) 1988 Mark Nudleman
 * Copyright (c) 1988 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char sccsid[] = "@(#)ch.c        5.11 (Berkeley) 6/21/92";
#endif /* not lint */

/*
 * Low level character input from the input file.
 * We use these special purpose routines which optimize moving
 * both forward and backward from the current read pointer.
 */

#include <sys/types.h>
#include <sys/file.h>
#include <unistd.h>
#include <stdio.h>
#include <less.h>

int file = -1;          /* File descriptor of the input file */

/*
 * Pool of buffers holding the most recently used blocks of the input file.
 */
struct buf {
        struct buf *next, *prev;
        long block;
        int datasize;
        char data[BUFSIZ];
};
int nbufs;

/*
 * The buffer pool is kept as a doubly-linked circular list, in order from
 * most- to least-recently used.  The circular list is anchored by buf_anchor.
 */
#define END_OF_CHAIN    ((struct buf *)&buf_anchor)
#define buf_head        buf_anchor.next
#define buf_tail        buf_anchor.prev

static struct {
        struct buf *next, *prev;
} buf_anchor = { END_OF_CHAIN, END_OF_CHAIN };

extern int ispipe, cbufs, sigs;

/*
 * Current position in file.
 * Stored as a block number and an offset into the block.
 */
static long ch_block;
static int ch_offset;

/* Length of file, needed if input is a pipe. */
static off_t ch_fsize;

/* Number of bytes read, if input is standard input (a pipe). */
static off_t last_piped_pos;

/*
 * Get the character pointed to by the read pointer.  ch_get() is a macro
 * which is more efficient to call than fch_get (the function), in the usual
 * case that the block desired is at the head of the chain.
 */
#define ch_get() \
        ((buf_head->block == ch_block && \
            ch_offset < buf_head->datasize) ? \
            buf_head->data[ch_offset] : fch_get())

static
fch_get()
{
        extern int bs_mode;
        register struct buf *bp;
        register int n, ch;
        register char *p, *t;
        off_t pos, lseek();

        /* look for a buffer holding the desired block. */
        for (bp = buf_head;  bp != END_OF_CHAIN;  bp = bp->next)
                if (bp->block == ch_block) {
                        if (ch_offset >= bp->datasize)
                                /*
                                 * Need more data in this buffer.
                                 */
                                goto read_more;
                        /*
                         * On a pipe, we don't sort the buffers LRU
                         * because this can cause gaps in the buffers.
                         * For example, suppose we've got 12 1K buffers,
                         * and a 15K input stream.  If we read the first 12K
                         * sequentially, then jump to line 1, then jump to
                         * the end, the buffers have blocks 0,4,5,6,..,14.
                         * If we then jump to line 1 again and try to
                         * read sequentially, we're out of luck when we
                         * get to block 1 (we'd get the "pipe error" below).
                         * To avoid this, we only sort buffers on a pipe
                         * when we actually READ the data, not when we
                         * find it already buffered.
                         */
                        if (ispipe)
                                return(bp->data[ch_offset]);
                        goto found;
                }
        /*
         * Block is not in a buffer.  Take the least recently used buffer
         * and read the desired block into it.  If the LRU buffer has data
         * in it, and input is a pipe, then try to allocate a new buffer first.
         */
        if (ispipe && buf_tail->block != (long)(-1))
                (void)ch_addbuf(1);
        bp = buf_tail;
        bp->block = ch_block;
        bp->datasize = 0;

read_more:
        pos = (ch_block * BUFSIZ) + bp->datasize;
        if (ispipe) {
                /*
                 * The data requested should be immediately after
                 * the last data read from the pipe.
                 */
                if (pos != last_piped_pos) {
                        error("pipe error");
                        quit();
                }
        } else
                (void)lseek(file, pos, L_SET);

        /*
         * Read the block.
         * If we read less than a full block, we just return the
         * partial block and pick up the rest next time.
         */
        n = iread(file, &bp->data[bp->datasize], BUFSIZ - bp->datasize);
        if (n == READ_INTR)
                return (EOI);
        if (n < 0) {
                error("read error");
                quit();
        }
        if (ispipe)
                last_piped_pos += n;

        p = &bp->data[bp->datasize];
        bp->datasize += n;

        /*
         * Set an EOI marker in the buffered data itself.  Then ensure the
         * data is "clean": there are no extra EOI chars in the data and
         * that the "meta" bit (the 0200 bit) is reset in each char;
         * also translate \r\n sequences to \n if -u flag not set.
         */
        if (n == 0) {
                ch_fsize = pos;
                bp->data[bp->datasize++] = EOI;
        }

        if (bs_mode) {
                for (p = &bp->data[bp->datasize]; --n >= 0;) {
                        *--p &= 0177;
                        if (*p == EOI)
                                *p = 0200;
                }
        }
        else {
                for (t = p; --n >= 0; ++p) {
                        ch = *p & 0177;
                        if (ch == '\r' && n && (p[1] & 0177) == '\n') {
                                ++p;
                                *t++ = '\n';
                        }
                        else
                                *t++ = (ch == EOI) ? 0200 : ch;
                }
                if (p != t) {
                        bp->datasize -= p - t;
                        if (ispipe)
                                last_piped_pos -= p - t;
                }
        }

found:
        if (buf_head != bp) {
                /*
                 * Move the buffer to the head of the buffer chain.
                 * This orders the buffer chain, most- to least-recently used.
                 */
                bp->next->prev = bp->prev;
                bp->prev->next = bp->next;

                bp->next = buf_head;
                bp->prev = END_OF_CHAIN;
                buf_head->prev = bp;
                buf_head = bp;
        }

        if (ch_offset >= bp->datasize)
                /*
                 * After all that, we still don't have enough data.
                 * Go back and try again.
                 */
                goto read_more;

        return(bp->data[ch_offset]);
}

/*
 * Determine if a specific block is currently in one of the buffers.
 */
static
buffered(block)
        long block;
{
        register struct buf *bp;

        for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
                if (bp->block == block)
                        return(1);
        return(0);
}

/*
 * Seek to a specified position in the file.
 * Return 0 if successful, non-zero if can't seek there.
 */
ch_seek(pos)
        register off_t pos;
{
        long new_block;

        new_block = pos / BUFSIZ;
        if (!ispipe || pos == last_piped_pos || buffered(new_block)) {
                /*
                 * Set read pointer.
                 */
                ch_block = new_block;
                ch_offset = pos % BUFSIZ;
                return(0);
        }
        return(1);
}

/*
 * Seek to the end of the file.
 */
ch_end_seek()
{
        off_t ch_length();

        if (!ispipe)
                return(ch_seek(ch_length()));

        /*
         * Do it the slow way: read till end of data.
         */
        while (ch_forw_get() != EOI)
                if (sigs)
                        return(1);
        return(0);
}

/*
 * Seek to the beginning of the file, or as close to it as we can get.
 * We may not be able to seek there if input is a pipe and the
 * beginning of the pipe is no longer buffered.
 */
ch_beg_seek()
{
        register struct buf *bp, *firstbp;

        /*
         * Try a plain ch_seek first.
         */
        if (ch_seek((off_t)0) == 0)
                return(0);

        /*
         * Can't get to position 0.
         * Look thru the buffers for the one closest to position 0.
         */
        firstbp = bp = buf_head;
        if (bp == END_OF_CHAIN)
                return(1);
        while ((bp = bp->next) != END_OF_CHAIN)
                if (bp->block < firstbp->block)
                        firstbp = bp;
        ch_block = firstbp->block;
        ch_offset = 0;
        return(0);
}

/*
 * Return the length of the file, if known.
 */
off_t
ch_length()
{
        off_t lseek();

        if (ispipe)
                return(ch_fsize);
        return((off_t)(lseek(file, (off_t)0, L_XTND)));
}

/*
 * Return the current position in the file.
 */
off_t
ch_tell()
{
        return(ch_block * BUFSIZ + ch_offset);
}

/*
 * Get the current char and post-increment the read pointer.
 */
ch_forw_get()
{
        register int c;

        c = ch_get();
        if (c != EOI && ++ch_offset >= BUFSIZ) {
                ch_offset = 0;
                ++ch_block;
        }
        return(c);
}

/*
 * Pre-decrement the read pointer and get the new current char.
 */
ch_back_get()
{
        if (--ch_offset < 0) {
                if (ch_block <= 0 || (ispipe && !buffered(ch_block-1))) {
                        ch_offset = 0;
                        return(EOI);
                }
                ch_offset = BUFSIZ - 1;
                ch_block--;
        }
        return(ch_get());
}

/*
 * Allocate buffers.
 * Caller wants us to have a total of at least want_nbufs buffers.
 * keep==1 means keep the data in the current buffers;
 * otherwise discard the old data.
 */
ch_init(want_nbufs, keep)
        int want_nbufs;
        int keep;
{
        register struct buf *bp;
        char message[80];

        cbufs = nbufs;
        if (nbufs < want_nbufs && ch_addbuf(want_nbufs - nbufs)) {
                /*
                 * Cannot allocate enough buffers.
                 * If we don't have ANY, then quit.
                 * Otherwise, just report the error and return.
                 */
                (void)sprintf(message, "cannot allocate %d buffers",
                    want_nbufs - nbufs);
                error(message);
                if (nbufs == 0)
                        quit();
                return;
        }

        if (keep)
                return;

        /*
         * We don't want to keep the old data,
         * so initialize all the buffers now.
         */
        for (bp = buf_head;  bp != END_OF_CHAIN;  bp = bp->next)
                bp->block = (long)(-1);
        last_piped_pos = (off_t)0;
        ch_fsize = NULL_POSITION;
        (void)ch_seek((off_t)0);
}

/*
 * Allocate some new buffers.
 * The buffers are added to the tail of the buffer chain.
 */
ch_addbuf(nnew)
        int nnew;
{
        register struct buf *bp;
        register struct buf *newbufs;
        char *calloc();

        /*
         * We don't have enough buffers.
         * Allocate some new ones.
         */
        newbufs = (struct buf *)calloc((u_int)nnew, sizeof(struct buf));
        if (newbufs == NULL)
                return(1);

        /*
         * Initialize the new buffers and link them together.
         * Link them all onto the tail of the buffer list.
         */
        nbufs += nnew;
        cbufs = nbufs;
        for (bp = &newbufs[0];  bp < &newbufs[nnew];  bp++) {
                bp->next = bp + 1;
                bp->prev = bp - 1;
                bp->block = (long)(-1);
        }
        newbufs[nnew-1].next = END_OF_CHAIN;
        newbufs[0].prev = buf_tail;
        buf_tail->next = &newbufs[0];
        buf_tail = &newbufs[nnew-1];
        return(0);
}