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