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