Annotation of src/usr.bin/more/ch.c, Revision 1.1
1.1 ! deraadt 1: /*
! 2: * Copyright (c) 1988 Mark Nudleman
! 3: * Copyright (c) 1988 Regents of the University of California.
! 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: * 3. All advertising materials mentioning features or use of this software
! 15: * must display the following acknowledgement:
! 16: * This product includes software developed by the University of
! 17: * California, Berkeley and its contributors.
! 18: * 4. Neither the name of the University nor the names of its contributors
! 19: * may be used to endorse or promote products derived from this software
! 20: * without specific prior written permission.
! 21: *
! 22: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
! 23: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 24: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 25: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 26: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 27: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 28: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 29: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 30: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 31: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 32: * SUCH DAMAGE.
! 33: */
! 34:
! 35: #ifndef lint
! 36: /* from: static char sccsid[] = "@(#)ch.c 5.11 (Berkeley) 6/21/92"; */
! 37: static char *rcsid = "$Id: ch.c,v 1.3 1994/04/06 17:50:39 cgd Exp $";
! 38: #endif /* not lint */
! 39:
! 40: /*
! 41: * Low level character input from the input file.
! 42: * We use these special purpose routines which optimize moving
! 43: * both forward and backward from the current read pointer.
! 44: */
! 45:
! 46: #include <sys/types.h>
! 47: #include <sys/file.h>
! 48: #include <unistd.h>
! 49: #include <stdio.h>
! 50: #include <less.h>
! 51:
! 52: int file = -1; /* File descriptor of the input file */
! 53:
! 54: /*
! 55: * Pool of buffers holding the most recently used blocks of the input file.
! 56: */
! 57: struct buf {
! 58: struct buf *next, *prev;
! 59: long block;
! 60: int datasize;
! 61: char data[BUFSIZ];
! 62: };
! 63: int nbufs;
! 64:
! 65: /*
! 66: * The buffer pool is kept as a doubly-linked circular list, in order from
! 67: * most- to least-recently used. The circular list is anchored by buf_anchor.
! 68: */
! 69: #define END_OF_CHAIN ((struct buf *)&buf_anchor)
! 70: #define buf_head buf_anchor.next
! 71: #define buf_tail buf_anchor.prev
! 72:
! 73: static struct {
! 74: struct buf *next, *prev;
! 75: } buf_anchor = { END_OF_CHAIN, END_OF_CHAIN };
! 76:
! 77: extern int ispipe, cbufs, sigs;
! 78:
! 79: /*
! 80: * Current position in file.
! 81: * Stored as a block number and an offset into the block.
! 82: */
! 83: static long ch_block;
! 84: static int ch_offset;
! 85:
! 86: /* Length of file, needed if input is a pipe. */
! 87: static off_t ch_fsize;
! 88:
! 89: /* Number of bytes read, if input is standard input (a pipe). */
! 90: static off_t last_piped_pos;
! 91:
! 92: /*
! 93: * Get the character pointed to by the read pointer. ch_get() is a macro
! 94: * which is more efficient to call than fch_get (the function), in the usual
! 95: * case that the block desired is at the head of the chain.
! 96: */
! 97: #define ch_get() \
! 98: ((buf_head->block == ch_block && \
! 99: ch_offset < buf_head->datasize) ? \
! 100: buf_head->data[ch_offset] : fch_get())
! 101:
! 102: static
! 103: fch_get()
! 104: {
! 105: extern int bs_mode;
! 106: register struct buf *bp;
! 107: register int n, ch;
! 108: register char *p, *t;
! 109: off_t pos;
! 110:
! 111: /* look for a buffer holding the desired block. */
! 112: for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
! 113: if (bp->block == ch_block) {
! 114: if (ch_offset >= bp->datasize)
! 115: /*
! 116: * Need more data in this buffer.
! 117: */
! 118: goto read_more;
! 119: /*
! 120: * On a pipe, we don't sort the buffers LRU
! 121: * because this can cause gaps in the buffers.
! 122: * For example, suppose we've got 12 1K buffers,
! 123: * and a 15K input stream. If we read the first 12K
! 124: * sequentially, then jump to line 1, then jump to
! 125: * the end, the buffers have blocks 0,4,5,6,..,14.
! 126: * If we then jump to line 1 again and try to
! 127: * read sequentially, we're out of luck when we
! 128: * get to block 1 (we'd get the "pipe error" below).
! 129: * To avoid this, we only sort buffers on a pipe
! 130: * when we actually READ the data, not when we
! 131: * find it already buffered.
! 132: */
! 133: if (ispipe)
! 134: return(bp->data[ch_offset]);
! 135: goto found;
! 136: }
! 137: /*
! 138: * Block is not in a buffer. Take the least recently used buffer
! 139: * and read the desired block into it. If the LRU buffer has data
! 140: * in it, and input is a pipe, then try to allocate a new buffer first.
! 141: */
! 142: if (ispipe && buf_tail->block != (long)(-1))
! 143: (void)ch_addbuf(1);
! 144: bp = buf_tail;
! 145: bp->block = ch_block;
! 146: bp->datasize = 0;
! 147:
! 148: read_more:
! 149: pos = (ch_block * BUFSIZ) + bp->datasize;
! 150: if (ispipe) {
! 151: /*
! 152: * The data requested should be immediately after
! 153: * the last data read from the pipe.
! 154: */
! 155: if (pos != last_piped_pos) {
! 156: error("pipe error");
! 157: quit();
! 158: }
! 159: } else
! 160: (void)lseek(file, pos, L_SET);
! 161:
! 162: /*
! 163: * Read the block.
! 164: * If we read less than a full block, we just return the
! 165: * partial block and pick up the rest next time.
! 166: */
! 167: n = iread(file, &bp->data[bp->datasize], BUFSIZ - bp->datasize);
! 168: if (n == READ_INTR)
! 169: return (EOI);
! 170: if (n < 0) {
! 171: error("read error");
! 172: quit();
! 173: }
! 174: if (ispipe)
! 175: last_piped_pos += n;
! 176:
! 177: p = &bp->data[bp->datasize];
! 178: bp->datasize += n;
! 179:
! 180: /*
! 181: * Set an EOI marker in the buffered data itself. Then ensure the
! 182: * data is "clean": there are no extra EOI chars in the data and
! 183: * that the "meta" bit (the 0200 bit) is reset in each char;
! 184: * also translate \r\n sequences to \n if -u flag not set.
! 185: */
! 186: if (n == 0) {
! 187: ch_fsize = pos;
! 188: bp->data[bp->datasize++] = EOI;
! 189: }
! 190:
! 191: if (bs_mode) {
! 192: for (p = &bp->data[bp->datasize]; --n >= 0;) {
! 193: *--p &= 0177;
! 194: if (*p == EOI)
! 195: *p = 0200;
! 196: }
! 197: }
! 198: else {
! 199: for (t = p; --n >= 0; ++p) {
! 200: ch = *p & 0177;
! 201: if (ch == '\r' && n && (p[1] & 0177) == '\n') {
! 202: ++p;
! 203: *t++ = '\n';
! 204: }
! 205: else
! 206: *t++ = (ch == EOI) ? 0200 : ch;
! 207: }
! 208: if (p != t) {
! 209: bp->datasize -= p - t;
! 210: if (ispipe)
! 211: last_piped_pos -= p - t;
! 212: }
! 213: }
! 214:
! 215: found:
! 216: if (buf_head != bp) {
! 217: /*
! 218: * Move the buffer to the head of the buffer chain.
! 219: * This orders the buffer chain, most- to least-recently used.
! 220: */
! 221: bp->next->prev = bp->prev;
! 222: bp->prev->next = bp->next;
! 223:
! 224: bp->next = buf_head;
! 225: bp->prev = END_OF_CHAIN;
! 226: buf_head->prev = bp;
! 227: buf_head = bp;
! 228: }
! 229:
! 230: if (ch_offset >= bp->datasize)
! 231: /*
! 232: * After all that, we still don't have enough data.
! 233: * Go back and try again.
! 234: */
! 235: goto read_more;
! 236:
! 237: return(bp->data[ch_offset]);
! 238: }
! 239:
! 240: /*
! 241: * Determine if a specific block is currently in one of the buffers.
! 242: */
! 243: static
! 244: buffered(block)
! 245: long block;
! 246: {
! 247: register struct buf *bp;
! 248:
! 249: for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
! 250: if (bp->block == block)
! 251: return(1);
! 252: return(0);
! 253: }
! 254:
! 255: /*
! 256: * Seek to a specified position in the file.
! 257: * Return 0 if successful, non-zero if can't seek there.
! 258: */
! 259: ch_seek(pos)
! 260: register off_t pos;
! 261: {
! 262: long new_block;
! 263:
! 264: new_block = pos / BUFSIZ;
! 265: if (!ispipe || pos == last_piped_pos || buffered(new_block)) {
! 266: /*
! 267: * Set read pointer.
! 268: */
! 269: ch_block = new_block;
! 270: ch_offset = pos % BUFSIZ;
! 271: return(0);
! 272: }
! 273: return(1);
! 274: }
! 275:
! 276: /*
! 277: * Seek to the end of the file.
! 278: */
! 279: ch_end_seek()
! 280: {
! 281: off_t ch_length();
! 282:
! 283: if (!ispipe)
! 284: return(ch_seek(ch_length()));
! 285:
! 286: /*
! 287: * Do it the slow way: read till end of data.
! 288: */
! 289: while (ch_forw_get() != EOI)
! 290: if (sigs)
! 291: return(1);
! 292: return(0);
! 293: }
! 294:
! 295: /*
! 296: * Seek to the beginning of the file, or as close to it as we can get.
! 297: * We may not be able to seek there if input is a pipe and the
! 298: * beginning of the pipe is no longer buffered.
! 299: */
! 300: ch_beg_seek()
! 301: {
! 302: register struct buf *bp, *firstbp;
! 303:
! 304: /*
! 305: * Try a plain ch_seek first.
! 306: */
! 307: if (ch_seek((off_t)0) == 0)
! 308: return(0);
! 309:
! 310: /*
! 311: * Can't get to position 0.
! 312: * Look thru the buffers for the one closest to position 0.
! 313: */
! 314: firstbp = bp = buf_head;
! 315: if (bp == END_OF_CHAIN)
! 316: return(1);
! 317: while ((bp = bp->next) != END_OF_CHAIN)
! 318: if (bp->block < firstbp->block)
! 319: firstbp = bp;
! 320: ch_block = firstbp->block;
! 321: ch_offset = 0;
! 322: return(0);
! 323: }
! 324:
! 325: /*
! 326: * Return the length of the file, if known.
! 327: */
! 328: off_t
! 329: ch_length()
! 330: {
! 331: if (ispipe)
! 332: return(ch_fsize);
! 333: return((off_t)(lseek(file, (off_t)0, L_XTND)));
! 334: }
! 335:
! 336: /*
! 337: * Return the current position in the file.
! 338: */
! 339: off_t
! 340: ch_tell()
! 341: {
! 342: return(ch_block * BUFSIZ + ch_offset);
! 343: }
! 344:
! 345: /*
! 346: * Get the current char and post-increment the read pointer.
! 347: */
! 348: ch_forw_get()
! 349: {
! 350: register int c;
! 351:
! 352: c = ch_get();
! 353: if (c != EOI && ++ch_offset >= BUFSIZ) {
! 354: ch_offset = 0;
! 355: ++ch_block;
! 356: }
! 357: return(c);
! 358: }
! 359:
! 360: /*
! 361: * Pre-decrement the read pointer and get the new current char.
! 362: */
! 363: ch_back_get()
! 364: {
! 365: if (--ch_offset < 0) {
! 366: if (ch_block <= 0 || (ispipe && !buffered(ch_block-1))) {
! 367: ch_offset = 0;
! 368: return(EOI);
! 369: }
! 370: ch_offset = BUFSIZ - 1;
! 371: ch_block--;
! 372: }
! 373: return(ch_get());
! 374: }
! 375:
! 376: /*
! 377: * Allocate buffers.
! 378: * Caller wants us to have a total of at least want_nbufs buffers.
! 379: * keep==1 means keep the data in the current buffers;
! 380: * otherwise discard the old data.
! 381: */
! 382: ch_init(want_nbufs, keep)
! 383: int want_nbufs;
! 384: int keep;
! 385: {
! 386: register struct buf *bp;
! 387: char message[80];
! 388:
! 389: cbufs = nbufs;
! 390: if (nbufs < want_nbufs && ch_addbuf(want_nbufs - nbufs)) {
! 391: /*
! 392: * Cannot allocate enough buffers.
! 393: * If we don't have ANY, then quit.
! 394: * Otherwise, just report the error and return.
! 395: */
! 396: (void)sprintf(message, "cannot allocate %d buffers",
! 397: want_nbufs - nbufs);
! 398: error(message);
! 399: if (nbufs == 0)
! 400: quit();
! 401: return;
! 402: }
! 403:
! 404: if (keep)
! 405: return;
! 406:
! 407: /*
! 408: * We don't want to keep the old data,
! 409: * so initialize all the buffers now.
! 410: */
! 411: for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
! 412: bp->block = (long)(-1);
! 413: last_piped_pos = (off_t)0;
! 414: ch_fsize = NULL_POSITION;
! 415: (void)ch_seek((off_t)0);
! 416: }
! 417:
! 418: /*
! 419: * Allocate some new buffers.
! 420: * The buffers are added to the tail of the buffer chain.
! 421: */
! 422: ch_addbuf(nnew)
! 423: int nnew;
! 424: {
! 425: register struct buf *bp;
! 426: register struct buf *newbufs;
! 427: char *calloc();
! 428:
! 429: /*
! 430: * We don't have enough buffers.
! 431: * Allocate some new ones.
! 432: */
! 433: newbufs = (struct buf *)calloc((u_int)nnew, sizeof(struct buf));
! 434: if (newbufs == NULL)
! 435: return(1);
! 436:
! 437: /*
! 438: * Initialize the new buffers and link them together.
! 439: * Link them all onto the tail of the buffer list.
! 440: */
! 441: nbufs += nnew;
! 442: cbufs = nbufs;
! 443: for (bp = &newbufs[0]; bp < &newbufs[nnew]; bp++) {
! 444: bp->next = bp + 1;
! 445: bp->prev = bp - 1;
! 446: bp->block = (long)(-1);
! 447: }
! 448: newbufs[nnew-1].next = END_OF_CHAIN;
! 449: newbufs[0].prev = buf_tail;
! 450: buf_tail->next = &newbufs[0];
! 451: buf_tail = &newbufs[nnew-1];
! 452: return(0);
! 453: }