source: trunk/minix/commands/yap/getline.c@ 11

Last change on this file since 11 was 9, checked in by Mattia Monga, 14 years ago

Minix 3.1.2a
File size: 15.5 KB
Line 
1/* Copyright (c) 1985 Ceriel J.H. Jacobs */
2
3# ifndef lint
4static char rcsid[] = "$Header: /cvsup/minix/src/commands/yap/getline.c,v 1.1.1.1 2005/04/21 14:55:39 beng Exp $";
5# endif
6
7# define _GETLINE_
8
9# include <errno.h>
10# include "in_all.h"
11# include "getline.h"
12# include "options.h"
13# include "process.h"
14# include "term.h"
15# include "main.h"
16# include "display.h"
17# include "output.h"
18# include "assert.h"
19
20extern int errno;
21
22# define BLOCKSIZE 2048 /* size of blocks */
23# define CHUNK 50 /* # of blockheaders allocated at a time */
24
25/*
26 * The blockheaders of the blocks that are in core are kept in a linked list.
27 * The last added block is indicated by b_head,
28 * the tail of the list is indicated by b_tail.
29 * The links go from b_tail to b_head.
30 * The blockheaders are all in an array, in the order of the line numbers.
31 * Also, the blockheaders must always be in core, so they have to be rather
32 * small. On systems with a small address space, yap can run out of core,
33 * and panic. However, this should only happen with very large files (>> 1M).
34 */
35
36struct block {
37 int b_flags; /* Contains the following flags: */
38# define DUMPED 01 /* block dumped on temporary file */
39# define PARTLY 02 /* block not filled completely (eof) */
40 int b_next; /* ptr in linked list */
41 long b_end; /* line number of last line in block */
42 char * b_info; /* the block */
43 int * b_offs; /* line offsets within the block */
44 long b_foff; /* offset of block in file */
45};
46
47static struct block * blocklist, /* beginning of the list of blocks */
48 * maxblocklist, /* first free entry in the list */
49 * topblocklist; /* end of allocated core for the list */
50static int b_head,
51 b_tail;
52static int tfdes, ifdes; /* File descriptors for temporary's */
53static long lastreadline; /* lineno of last line read */
54static int ENDseen;
55
56STATIC VOID readblock();
57STATIC VOID nextblock();
58STATIC char *re_alloc();
59
60STATIC struct block *
61new_block()
62{
63 register struct block *pblock = maxblocklist - 1;
64
65 if (!maxblocklist || !(pblock->b_flags & PARTLY)) {
66 /*
67 * There is no last block, or it was filled completely,
68 * so allocate a new blockheader.
69 */
70 register int siz;
71
72 pblock = blocklist;
73 if (maxblocklist == topblocklist) {
74 /*
75 * No blockheaders left. Allocate new ones
76 */
77 siz = topblocklist - pblock;
78 blocklist = pblock = (struct block *)
79 re_alloc((char *) pblock,
80 (unsigned) (siz * sizeof(*pblock)),
81 (unsigned) ((siz + CHUNK) * sizeof(*pblock)));
82 pblock += siz;
83 topblocklist = pblock + CHUNK;
84 maxblocklist = pblock;
85 for (; pblock < topblocklist; pblock++) {
86 pblock->b_end = 0;
87 pblock->b_info = 0;
88 pblock->b_flags = 0;
89 }
90 if (!siz) {
91 /*
92 * Create dummy header cell.
93 */
94 maxblocklist++;
95 }
96 }
97 pblock = maxblocklist++;
98 }
99 nextblock(pblock);
100 return pblock;
101}
102
103/*
104 * Return the block in which line 'n' of the current file can be found.
105 * If "disable_interrupt" = 0, the call may be interrupted, in which
106 * case it returns 0.
107 */
108
109STATIC struct block *
110getblock(n, disable_interrupt) register long n; {
111 register struct block * pblock;
112
113 if (stdf < 0) {
114 /*
115 * Not file descriptor, so return end of file
116 */
117 return 0;
118 }
119 pblock = maxblocklist - 1;
120 if (n < lastreadline ||
121 (n == lastreadline && !(pblock->b_flags & PARTLY))) {
122 /*
123 * The line asked for has been read already.
124 * Perform binary search in the blocklist to find the block
125 * where it's in.
126 */
127 register struct block *min, *mid;
128
129 min = blocklist + 1;
130 do {
131 mid = min + (pblock - min) / 2;
132 if (n > mid->b_end) {
133 min = mid + 1;
134 }
135 else pblock = mid;
136 } while (min < pblock);
137 /* Found, pblock is now a reference to the block wanted */
138 if (!pblock->b_info) readblock(pblock);
139 return pblock;
140 }
141
142 /*
143 * The line was'nt read yet, so read blocks until found
144 */
145 for (;;) {
146 if (interrupt && !disable_interrupt) return 0;
147 pblock = new_block();
148 if (pblock->b_end >= n) {
149 return pblock;
150 }
151 if (pblock->b_flags & PARTLY) {
152 /*
153 * We did not find it, and the last block could not be
154 * read completely, so return 0;
155 */
156 return 0;
157 }
158 }
159 /* NOTREACHED */
160}
161
162char *
163getline(n, disable_interrupt) long n; {
164 register struct block *pblock;
165
166 if (!(pblock = getblock(n, disable_interrupt))) {
167 return (char *) 0;
168 }
169 return pblock->b_info + pblock->b_offs[n - ((pblock-1)->b_end + 1)];
170}
171
172/*
173 * Find the last line of the input, and return its number
174 */
175
176long
177to_lastline() {
178
179 for (;;) {
180 if (!getline(lastreadline + 1, 0)) {
181 /*
182 * "lastreadline" always contains the linenumber of
183 * the last line read. So, if the call to getline
184 * succeeds, "lastreadline" is affected
185 */
186 if (interrupt) return -1L;
187 return lastreadline;
188 }
189 }
190 /* NOTREACHED */
191}
192
193#if MAXNBLOCKS
194int nblocks; /* Count number of large blocks */
195#endif
196
197/*
198 * Allocate some memory. If unavailable, free some and try again.
199 * If all fails, panic.
200 */
201
202char *
203alloc(size, isblock) unsigned size; {
204
205 register char *pmem;
206 register struct block *pblock, *bllist;
207 char *malloc();
208 long lseek();
209 register long i;
210
211 bllist = blocklist;
212 while (
213#if MAXNBLOCKS
214 (isblock && nblocks >= MAXNBLOCKS) ||
215#endif
216 !(pmem = malloc(size)) /* No space */
217 ) {
218 if (b_tail == 0) {
219 /*
220 * Also, no blocks in core. Pity
221 */
222 panic("No core");
223 }
224#if MAXNBLOCKS
225 nblocks--;
226#endif
227 pblock = bllist + b_tail;
228 b_tail = pblock->b_next;
229 if (!nopipe && !(pblock->b_flags & DUMPED)) {
230 /*
231 * Dump the block on a temporary file
232 */
233 if (!tfdes) {
234 /*
235 * create and open temporary files
236 */
237 tfdes = opentemp(0);
238 ifdes = opentemp(1);
239 }
240 pblock->b_flags |= DUMPED;
241 /*
242 * Find out where to dump the block, and dump it
243 */
244 i = (pblock-1)->b_end * sizeof(int);
245 (VOID) lseek(tfdes,
246 ((long) BLOCKSIZE * (pblock - bllist)), 0);
247 if (write(tfdes, pblock->b_info, BLOCKSIZE)
248 != BLOCKSIZE) {
249 panic("write failed");
250 }
251 /*
252 * Also dump the offsets of the lines in the block
253 */
254 (VOID) lseek(ifdes, i, 0);
255 i = pblock->b_end * sizeof(int) - i;
256 if (write(ifdes, (char *) pblock->b_offs, (int) i)
257 != (int) i) {
258 panic("Write failed");
259 }
260 }
261 /*
262 * Now that the block is dumped, the space taken by it can
263 * be freed
264 */
265 free((char *) pblock->b_offs);
266 free(pblock->b_info);
267 pblock->b_info = (char *) 0;
268 }
269#if MAXNBLOCKS
270 if (isblock) nblocks++;
271#endif
272 return pmem;
273}
274
275/*
276 * Re-allocate the memorychunk pointed to by ptr, to let it
277 * grow or shrink.
278 * realloc of the standard C library is useless, as it is destructive
279 * if the malloc fails.
280 */
281
282STATIC char *
283re_alloc(ptr,oldsize, newsize)
284char *ptr; unsigned oldsize; unsigned newsize; {
285 register char *pmem;
286 register char *c1, *c2;
287
288 /*
289 * We could be smarter here, by checking if newsize < oldsize, and in
290 * that case using realloc, but this depends on realloc using the
291 * same block if the block shrinks. The question is, wether all
292 * reallocs in the world do this.
293 */
294 pmem = alloc(newsize, 0);
295 if (oldsize) {
296 /*
297 * This test makes re_alloc also work if there was no old block
298 */
299 c1 = pmem;
300 c2 = ptr;
301 if (newsize > oldsize) {
302 newsize = oldsize;
303 }
304 while (newsize--) {
305 *c1++ = *c2++;
306 }
307 free(ptr);
308 }
309 return pmem;
310}
311
312/*
313 * Append a block to the linked list of blockheaders of blocks that are
314 * in core.
315 */
316
317STATIC VOID
318addtolist(pblock) register struct block *pblock; {
319 register struct block *bllist = blocklist;
320
321 pblock->b_next = 0;
322 (bllist + b_head)->b_next = pblock - bllist;
323 b_head = pblock - bllist;
324 if (!b_tail) {
325 /*
326 * The list was empty, initialize
327 */
328 b_tail = b_head;
329 }
330}
331
332static char *saved;
333static long filldegree;
334
335/*
336 * Try to read the block indicated by pblock
337 */
338
339STATIC VOID
340nextblock(pblock) register struct block *pblock; {
341 register char *c, /* Run through pblock->b_info */
342 *c1; /* indicate end of pblock->b_info */
343 register int *poff; /* pointer in line-offset list */
344 register int cnt; /* # of characters read */
345 register unsigned siz; /* Size of allocated line-offset list */
346 static unsigned savedsiz; /* saved "siz" */
347 static int *savedpoff; /* saved "poff" */
348 static char *savedc1; /* saved "c1" */
349
350 if (pblock->b_flags & PARTLY) {
351 /*
352 * The block was already partly filled. Initialize locals
353 * accordingly
354 */
355 poff = savedpoff;
356 siz = savedsiz;
357 pblock->b_flags = 0;
358 c1 = savedc1;
359 if (c1 == pblock->b_info || *(c1 - 1)) {
360 /*
361 * We had incremented "lastreadline" temporarily,
362 * because the last line could not be completely read
363 * last time we tried. Undo this increment
364 */
365 poff--;
366 --lastreadline;
367 }
368 }
369 else {
370 if (nopipe) pblock->b_foff = lseek(stdf, 0L, 1);
371 if (saved) {
372 /*
373 * There were leftovers from the previous block
374 */
375 pblock->b_info = saved;
376 if (nopipe) pblock->b_foff -= savedc1 - saved;
377 c1 = savedc1;
378 saved = 0;
379 }
380 else { /* Allocate new block */
381 pblock->b_info = c1 = alloc(BLOCKSIZE + 1, 1);
382 }
383 /*
384 * Allocate some space for line-offsets
385 */
386 pblock->b_offs = poff = (int *)
387 alloc((unsigned) (100 * sizeof(int)), 0);
388 siz = 99;
389 *poff++ = 0;
390 }
391 c = c1;
392 for (;;) {
393 /*
394 * Read loop
395 */
396 cnt = read(stdf, c1, BLOCKSIZE - (c1 - pblock->b_info));
397 if (cnt < 0) {
398 /*
399 * Interrupted read
400 */
401 if (errno == EINTR) continue;
402 error("Could not read input file");
403 cnt = 0;
404 }
405 c1 += cnt;
406 if (c1 != pblock->b_info + BLOCKSIZE) {
407 ENDseen = 1;
408 pblock->b_flags |= PARTLY;
409 }
410 break;
411 }
412 assert(c <= c1);
413 while (c < c1) {
414 /*
415 * Now process the block
416 */
417 *c &= 0177; /* Most significant bit ignored */
418 if (*c == '\n') {
419 /*
420 * Newlines are replaced by '\0', so that "getline"
421 * can deliver one line at a time
422 */
423 *c = 0;
424 lastreadline++;
425 /*
426 * Remember the line-offset
427 */
428 if (poff == pblock->b_offs + siz) {
429 /*
430 * No space for it, allocate some more
431 */
432 pblock->b_offs = (int *)
433 re_alloc((char *) pblock->b_offs,
434 (siz+1) * sizeof(int),
435 (siz + 51) * sizeof(int));
436 poff = pblock->b_offs + siz;
437 siz += 50;
438 }
439 *poff++ = c - pblock->b_info + 1;
440 }
441 else if (*c == '\0') {
442 /*
443 * 0-bytes are replaced by 0200, because newlines are
444 * replaced by 0, and 0200 & 0177 gives again 0 ...
445 */
446 *c = 0200;
447 }
448 c++;
449 }
450 assert(c==c1);
451 *c = 0;
452 if (c != pblock->b_info && *(c-1) != 0) {
453 /*
454 * The last line read does not end with a newline, so add one
455 */
456 lastreadline++;
457 *poff++ = c - pblock->b_info + 1;
458 if (!(pblock->b_flags & PARTLY) && *(poff - 2) != 0) {
459 /*
460 * Save the started line; it will be in the next block.
461 * Remove the newline we added just now.
462 */
463 saved = c1 = alloc(BLOCKSIZE + 1, 1);
464 c = pblock->b_info + *(--poff - 1);
465 while (*c) *c1++ = *c++;
466 c = pblock->b_info + *(poff - 1);
467 savedc1 = c1;
468 --lastreadline;
469 }
470 }
471 pblock->b_end = lastreadline;
472 if (pblock->b_flags & PARTLY) {
473 /*
474 * Take care, that we can call "nextblock" again, to fill in
475 * the rest of this block
476 */
477 savedsiz = siz;
478 savedpoff = poff;
479 savedc1 = c;
480 if (c == pblock->b_info) {
481 lastreadline++;
482 pblock->b_end = 0;
483 }
484 }
485 else {
486 /*
487 * Not completely read blocks are not in the linked list,
488 * so can never be "swapped out".
489 */
490 addtolist(pblock);
491 cnt = pblock - blocklist;
492 filldegree = ((c-pblock->b_info) + (cnt-1) * filldegree) / cnt;
493 }
494 assert(pblock->b_end - (pblock-1)->b_end <= poff - pblock->b_offs);
495}
496
497/*
498 * Allocate core for the block, and read it back from
499 * the temporary file.
500 */
501
502STATIC VOID
503readblock(pblock) register struct block *pblock; {
504
505 register int size;
506 register long i;
507
508 /*
509 * Find out where the block is, and read it
510 */
511 pblock->b_info = alloc(BLOCKSIZE + 1, 1);
512 i = (pblock - 1)->b_end * sizeof(int);
513 size = (int) (pblock->b_end * sizeof(int) - i);
514 pblock->b_offs = (int *) alloc((unsigned) size, 0);
515 if (nopipe) {
516 register char *c;
517 register int line_index;
518 int cnt;
519 long l = lseek(stdf, 0L, 1);
520
521 (VOID) lseek(stdf, pblock->b_foff, 0);
522 cnt = read(stdf, pblock->b_info, BLOCKSIZE);
523 (VOID) lseek(stdf, l, 0);
524 c = pblock->b_info;
525 pblock->b_offs[0] = 0;
526 line_index = 1;
527 size /= sizeof(int);
528 while (c < pblock->b_info + cnt) {
529 *c &= 0177;
530 if (*c == '\n') {
531 *c = '\0';
532 if (line_index < size)
533 pblock->b_offs[line_index++] =
534 (c - pblock->b_info) + 1;
535 }
536 else if (*c == '\0') *c = 0200;
537 c++;
538 }
539 *c = '\0';
540 }
541 else {
542 (VOID) lseek(tfdes, (long) ((long) BLOCKSIZE * (pblock - blocklist)),0);
543 if (read(tfdes, pblock->b_info,BLOCKSIZE) != BLOCKSIZE) {
544 panic("read error");
545 }
546 /*
547 * Find out where the line-offset list is, and read it
548 */
549 (VOID) lseek(ifdes, i, 0);
550 if (read(ifdes, (char *) pblock->b_offs, size) != size) {
551 panic("read error");
552 }
553 pblock->b_info[BLOCKSIZE] = '\0';
554 }
555 /*
556 * Add this block to the list of incore blocks
557 */
558 addtolist(pblock);
559}
560
561/*
562 * Called after processing a file.
563 * Free all core.
564 */
565
566VOID
567do_clean() {
568
569 register struct block *pblock;
570 register char *p;
571
572 for (pblock = blocklist; pblock < maxblocklist; pblock++) {
573 if (p = pblock->b_info) {
574 free(p);
575 free((char *) pblock->b_offs);
576 }
577 }
578 if (p = (char *) blocklist) {
579 free(p);
580 }
581 blocklist = 0;
582 maxblocklist = 0;
583 topblocklist = 0;
584 lastreadline = 0;
585 filldegree = 0;
586 ENDseen = 0;
587 if (p = saved) free(p);
588 saved = 0;
589 b_head = 0;
590 b_tail = 0;
591# if MAXNBLOCKS
592 nblocks = 0;
593# endif
594}
595
596/*
597 * Close a file with file-descriptor "file", if it indeed is one
598 */
599
600STATIC VOID
601cls(file) {
602 if (file) (VOID) close(file);
603}
604
605/*
606 * Close all files
607 */
608
609VOID
610cls_files() {
611
612 cls(tfdes);
613 cls(ifdes);
614 cls(stdf);
615}
616
617/*
618 * Get a character. If possible, do some workahead.
619 */
620
621int
622getch() {
623# if USG_OPEN
624# include <fcntl.h>
625# include <sys/stat.h>
626
627 register int i,j;
628 struct stat buf;
629# else
630# ifdef FIONREAD
631# include <sys/stat.h>
632
633 struct stat buf;
634 long i;
635# endif
636# endif
637
638 char c;
639 int retval;
640
641 flush();
642 if (startcomm) {
643 /*
644 * Command line option command
645 */
646 if (*startcomm) return *startcomm++;
647 return '\n';
648 }
649# if USG_OPEN
650 if (stdf >= 0) {
651 /*
652 * Make reads from the terminal non-blocking, so that
653 * we can see if the user typed something
654 */
655 i = fcntl(0,F_GETFL,0);
656 if (i != -1 && fcntl(0, F_SETFL, i|O_NDELAY) != -1) {
657 j = 0;
658 while (! ENDseen &&
659 ((j = read(0,&c,1)) == 0
660#ifdef EWOULDBLOCK
661 || (j < 0 && errno == EWOULDBLOCK)
662#endif
663 )
664 &&
665 (nopipe ||
666 (fstat(stdf,&buf) >= 0 && buf.st_size > 0))) {
667 /*
668 * Do some read ahead, after making sure there
669 * is input and the user did not type a command
670 */
671 new_block();
672 }
673 (VOID) fcntl(0,F_SETFL,i);
674 if (j < 0) {
675 /*
676 * Could this have happened?
677 * I'm not sure, because the read is
678 * nonblocking. Can it be interrupted then?
679 */
680 return -1;
681 }
682 if (j > 0) return c;
683 }
684 }
685# else
686# ifdef FIONREAD
687 if (stdf >= 0) {
688 /*
689 * See if there are any characters waiting in the terminal input
690 * queue. If there are not, read ahead.
691 */
692 while (! ENDseen &&
693 ( ioctl(0, FIONREAD, (char *) &i) >= 0 && i == 0) &&
694 ( nopipe || fstat(stdf,&buf) >= 0 && buf.st_size > 0)) {
695 /*
696 * While the user does'nt type anything, and there is
697 * input to be processed, work ahead
698 */
699 if (interrupt) return -1;
700 new_block();
701 }
702 }
703# endif
704# endif
705 if (read(0,&c,1) <= 0) retval = -1; else retval = c & 0177;
706 return retval;
707}
708
709/*
710 * Get the position of line "ln" in the file.
711 */
712
713long
714getpos(ln) long ln; {
715 register struct block *pblock;
716 register long i;
717
718 pblock = getblock(ln,1);
719 assert(pblock != 0);
720 i = filldegree * (pblock - blocklist);
721 return i - (filldegree - pblock->b_offs[ln - (pblock-1)->b_end]);
722}
Note: See TracBrowser for help on using the repository browser.