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