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