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