distrib/utils/more/ch.c

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