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