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 36static 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 58int 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 */ 63struct buf { 64 struct buf *next, *prev; 65 long block; 66 int datasize; 67 char data[BUFSIZ]; 68}; 69int 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 79static 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 */ 87static long ch_block; 88static int ch_offset; 89 90/* Length of file, needed if input is a pipe. */ 91static off_t ch_fsize; 92 93/* Number of bytes read, if input is standard input (a pipe). */ 94static 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 106static int fch_get __P((void)); 107static int buffered __P((long)); 108 109static int 110fch_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 154read_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 221found: 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 */ 249static int 250buffered(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 */ 265int 266ch_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 */ 286int 287ch_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 */ 306int 307ch_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 */ 335off_t 336ch_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 */ 346off_t 347ch_tell() 348{ 349 return(ch_block * BUFSIZ + ch_offset); 350} 351 352/* 353 * Get the current char and post-increment the read pointer. 354 */ 355int 356ch_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 */ 371int 372ch_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 */ 391void 392ch_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 */ 432int 433ch_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} 464