tpage.cc - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tpage.cc (17831B)
---
1 #include "misc.h"
2 #include "slug.h"
3 #include "range.h"
4 #include "page.h"
5
6 const int MAXRANGES = 1000;
7 static range *ptemp[MAXRANGES]; // for movefloats()
8
9 static void swapright(int n) // used by movefloats()
10 {
11 range *t = ptemp[n];
12 ptemp[n] = ptemp[n+1];
13 ptemp[n+1] = t;
14 ptemp[n]->setaccum( ptemp[n+1]->accum() -
15 ptemp[n+1]->rawht() + ptemp[n]->rawht() );
16 ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() );
17 }
18
19 // Figure out the goal position for each floating range on scratch,
20 // and move it past stream ranges until it's as close to its goal as possible.
21 static void movefloats(stream *scratch, double scale)
22 {
23 int nranges, i;
24 const int Huge = 100000;
25
26 for (nranges = 0; scratch->more(); scratch->advance())
27 ptemp[nranges++] = scratch->current();
28 scratch->freeall();
29 ufrange rtemp;
30 ptemp[nranges] = &rtemp;
31 rtemp.setgoal(Huge);
32 int accumV = 0; // compute accum values and
33 for (i = 0; i < nranges; i++) { // pick closest goal for floats
34 ptemp[i]->pickgoal(accumV, scale);
35 ptemp[i]->setaccum(accumV += ptemp[i]->rawht());
36 }
37 int j; // index for inner loop below:
38 for (i = nranges; --i >= 0; ) // stably sort floats to bottom
39 for (j = i; j < nranges; j++)
40 if (ptemp[j]->goal() > ptemp[j+1]->goal())
41 swapright(j);
42 else
43 break;
44 if (dbg & 16)
45 printf("#movefloats: before floating, from bottom:\n");
46 for (i = nranges; --i >= 0; ) { // find topmost float
47 if (ptemp[i]->goal() == NOGOAL)
48 break;
49 if (dbg & 16)
50 printf("# serialno %d goal %d height %d\n",
51 ptemp[i]->serialno(), ptemp[i]->goal(),
52 ptemp[i]->rawht());
53 } // i+1 is topmost float
54 for (i++ ; i < nranges; i++) // move each float up the page
55 for (j = i; j > 0; j--) // as long as closer to its goal
56 if (ptemp[j]->goal()
57 <= ptemp[j-1]->accum() + ptemp[j]->rawht()/2
58 && ptemp[j-1]->goal() == NOGOAL)
59 swapright(j-1);
60 else
61 break;
62 if (ptemp[nranges] != &rtemp)
63 ERROR "goal sentinel has disappeared from movefloats" FATAL;
64 for (i = 0; i < nranges; i++) // copy sorted list back
65 scratch->append(ptemp[i]);
66 }
67
68 // Traverse the leaves of a tree of ranges, filtering out only SP and VBOX.
69 static range *filter(generator *g)
70 {
71 range *r;
72 while ((r = g->next()) != 0)
73 if (r->isvbox() || r->issp())
74 break;
75 return r;
76 }
77
78 // Zero out leading and trailing spaces; coalesce adjacent SP's.
79 static void trimspace(stream *scratch)
80 {
81 generator g;
82 range *r, *prevr = 0;
83
84 for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r)
85 r->setheight(0); // zap leading SP
86 for ( ; (r = filter(&g)) != 0; prevr = r)
87 if (r->issp())
88 if (prevr && prevr->issp()) {
89 // coalesce adjacent SPs
90 r->setheight(max(r->rawht(), prevr->height()));
91 prevr->setheight(0);
92 } else // a VBOX intervened
93 r->setheight(r->rawht());
94 if (prevr && prevr->issp()) // zap *all* trailing space
95 prevr->setheight(0); // (since it all coalesced
96 // into the last one)
97 }
98
99 // Pad the non-zero SP's in scratch so the total height is wantht.
100 // Note that the SP values in scratch are not the raw values, and
101 // indeed may already have been padded.
102 static void justify(stream *scratch, int wantht)
103 {
104 range *r;
105 int nsp = 0, hsp = 0;
106
107 int adjht = scratch->height();
108 // Find all the spaces.
109 generator g;
110 for (g = scratch; (r = g.next()) != 0; )
111 if (r->issp() && r->height() > 0) {
112 nsp++;
113 hsp += r->height();
114 }
115 int excess = wantht - adjht;
116 if (excess < 0)
117 ERROR "something on page %d is oversize by %d\n",
118 userpn, -excess WARNING;
119 if (dbg & 16)
120 printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n",
121 userpn, excess, nsp, hsp, adjht);
122 if (excess <= 0 || nsp == 0)
123 return;
124 // Redistribute the excess space.
125 for (g = scratch; (r = g.next()) != 0; )
126 if (r->issp() && r->height() > 0) {
127 int delta = (int) ((float)(r->height()*excess)/hsp + 0.5);
128 if (dbg & 16)
129 printf("# pad space %d by %d: hsp %d excess %d\n",
130 r->height(), delta, hsp, excess);
131 r->setheight(r->height() + delta);
132 }
133 }
134
135 // If r were added to s, would the height of the composed result be at most maxht?
136 int wouldfit(range *r, stream *s, int maxht)
137 {
138 if (r->rawht() + s->rawht() <= maxht)
139 return 1; // the conservative test succeeded
140 stream scratch; // local playground for costly test
141 for (stream cd = *s; cd.more(); cd.advance())
142 scratch.append(cd.current());
143 scratch.append(r);
144 movefloats(&scratch, ((double) scratch.rawht())/maxht);
145 trimspace(&scratch);
146 int retval = scratch.height() <= maxht;
147 scratch.freeall();
148 return retval;
149 }
150
151 // If s1 were added to s, would the height of the composed result be at most maxht?
152 // The computational structure is similar to that above.
153 int wouldfit(stream *s1, stream *s, int maxht)
154 {
155 if (s1->rawht() + s->rawht() <= maxht)
156 return 1;
157 stream scratch, cd;
158 for (cd = *s; cd.more(); cd.advance())
159 scratch.append(cd.current());
160 for (cd = *s1; cd.more(); cd.advance())
161 scratch.append(cd.current());
162 movefloats(&scratch, ((double) scratch.rawht())/maxht);
163 trimspace(&scratch);
164 int retval = scratch.height() <= maxht;
165 scratch.freeall();
166 return retval;
167 }
168
169 // All of stream *s is destined for one column or the other; which is it to be?
170 void multicol::choosecol(stream *s, int goalht)
171 {
172 stream *dest;
173 if (!leftblocked && wouldfit(s, &(column[0]), goalht))
174 dest = &(column[0]);
175 else {
176 dest = &(column[1]);
177 if (!s->current()->floatable())
178 // a stream item is going into the right
179 // column, so no more can go into the left.
180 leftblocked = 1;
181 }
182 for (stream cd = *s; cd.more(); cd.advance())
183 dest->append(cd.current());
184 }
185
186 double coltol = 0.5;
187
188 // Try, very hard, to put everything in the multicol into two columns
189 // so that the total height is at most htavail.
190 void multicol::compose(int defonly)
191 {
192 if (!nonempty()) {
193 setheight(0);
194 return;
195 }
196 scratch.freeall(); // fill scratch with everything destined
197 // for either column
198 stream cd;
199 for (cd = definite; cd.more(); cd.advance())
200 scratch.append(cd.current());
201 if (!defonly)
202 for (cd = *(currpage->stage); cd.more(); cd.advance())
203 if (cd.current()->numcol() == 2)
204 scratch.append(cd.current());
205 scratch.restoreall(); // in particular, floatables' goals
206 int i;
207 int rawht = scratch.rawht();
208 int halfheight = (int)(coltol*rawht);
209 // choose a goal height
210 int maxht = defonly ? halfheight : htavail;
211 secondtry:
212 for (i = 0; i < 2; i++)
213 column[i].freeall();
214 leftblocked = 0;
215 cd = scratch;
216 while (cd.more()) {
217 queue ministage; // for the minimally acceptable chunks
218 ministage.freeall(); // that are to be added to either column
219 while (cd.more() && !cd.current()->issentinel()) {
220 ministage.enqueue(cd.current());
221 cd.advance();
222 }
223 choosecol(&ministage, maxht);
224 if (cd.more() && cd.current()->issentinel())
225 cd.advance(); // past sentinel
226 }
227 if (height() > htavail && maxht != htavail) {
228 // We tried to balance the columns, but
229 // the result was too tall. Go back
230 // and try again with the less ambitious
231 // goal of fitting the space available.
232 maxht = htavail;
233 goto secondtry;
234 }
235 for (i = 0; i < 2; i++) {
236 movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize);
237 trimspace(&(column[i]));
238 }
239 if (dbg & 32) {
240 printf("#multicol::compose: htavail %d maxht %d dv %d\n",
241 htavail, maxht, height());
242 dump();
243 }
244 if (defonly)
245 stretch(height());
246 }
247
248 // A sequence of two-column ranges waits on the stage.
249 // So long as the page's skeleton hasn't changed--that is, the maximum height
250 // available to the two-column chunk is the same--we just use the columns that
251 // have been built up so far, and choose a column into which to put the stage.
252 // If the skeleton has changed, however, then we may need to make entirely
253 // new decisions about which column gets what, so we recompose the whole page.
254 void multicol::tryout()
255 {
256 if (htavail == prevhtavail)
257 choosecol(currpage->stage, htavail);
258 else
259 currpage->compose(DRAFT);
260 prevhtavail = htavail;
261 }
262
263 // Make both columns the same height.
264 // (Maybe this should also be governed by minfull,
265 // to prevent padding very underfull columns.)
266 void multicol::stretch(int wantht)
267 {
268 if (wantht < height())
269 ERROR "page %d: two-column chunk cannot shrink\n", userpn FATAL;
270 for (int i = 0; i < 2; i++)
271 justify(&(column[i]), wantht);
272 if (dbg & 16)
273 printf("#col hts: left %d right %d\n",
274 column[0].height(), column[1].height());
275 }
276
277 // Report an upper bound on how tall the current two-column object is.
278 // The (possibly composed) heights of the two columns give a crude upper
279 // bound on the total height. If the result is more than the height
280 // available for the two-column object, then the columns are each
281 // composed to give a better estimate of their heights.
282 int multicol::height()
283 {
284 int retval = max(column[0].height(), column[1].height());
285 if (retval < htavail)
286 return retval;
287 for (int i = 0; i < 2; i++) {
288 movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize);
289 trimspace(&(column[i]));
290 }
291 return max(column[0].height(), column[1].height());
292 }
293
294 void multicol::dump()
295 {
296 printf("####2COL dv %d\n", height());
297 printf("# left column:\n");
298 column[0].dump();
299 printf("# right column:\n");
300 column[1].dump();
301 }
302
303 // From the head of queue qp, peel off a piece whose raw height is at most space.
304 int peeloff(stream *qp, int space)
305 {
306 stream *s1 = qp->current()->children();
307 if (!(s1 && s1->more() && s1->current()->height() <= space))
308 // in other words, either qp's head is
309 // not nested, or its first subrange
310 return 0; // is also too big, so we give up
311 qp->split();
312 s1 = qp->current()->children();
313 stream *s2 = qp->next()->children();
314 while (s2->more() && s2->current()->rawht() <= space) {
315 s1->append(s2->current());
316 space -= s2->current()->rawht();
317 s2->advance();
318 }
319 return 1;
320 }
321
322 // There are four possibilities for consecutive calls to tryout().
323 // If we're processing a sequence of single-column ranges, tryout()
324 // uses the original algorithm: (1) conservative test; (2) costly test;
325 // (3) split a breakable item.
326 // If we're processing a sequence of double-column ranges, tryout()
327 // defers to twocol->tryout(), which gradually builds up the contents
328 // of the two columns until they're as tall as they can be without
329 // exceeding twocol->htavail.
330 // If we're processing a sequence of single-column ranges and we
331 // get a double-column range, then we use compose() to build a
332 // skeleton page and set twocol->htavail, the maximum height that
333 // should be occupied by twocol.
334 // If we're processing a sequence of double-column ranges and we
335 // get a single-column range, then we should go back and squish
336 // the double-column chunk as short as possible before we see if
337 // we can fit the single-column range.
338 void page::tryout()
339 {
340 if (!stage->more())
341 ERROR "empty stage in page::tryout()\n" FATAL;
342 int curnumcol = stage->current()->numcol();
343 if (dbg & 32) {
344 printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n",
345 curnumcol, prevncol);
346 stage->dump();
347 printf("#END of stage contents\n");
348 }
349 switch(curnumcol) {
350 default:
351 ERROR "unexpected number of columns in tryout(): %d\n",
352 stage->current()->numcol() FATAL;
353 break;
354 case 1:
355 if (prevncol == 2)
356 compose(FINAL);
357 if (wouldfit(stage, &definite, pagesize - twocol->height()))
358 commit();
359 else if (stage->current()->breakable() || blank()
360 && peeloff(stage,
361 pagesize - (definite.height() + twocol->height()))) {
362 // first add the peeled-off part that fits
363 adddef(stage->dequeue());
364 // then send the rest back for later
365 stage->current()->setbreaking();
366 welsh();
367 } else if (blank()) {
368 stage->current()->rdump();
369 ERROR "A %s is too big to continue.\n",
370 stage->current()->typename() FATAL;
371 } else
372 welsh();
373 break;
374 case 2:
375 if (prevncol == 1)
376 compose(DRAFT);
377 else
378 twocol->tryout();
379 if (scratch.height() <= pagesize)
380 commit();
381 else
382 welsh();
383 break;
384 }
385 prevncol = curnumcol;
386 }
387
388 // To compose the page, we (1) fill scratch with the stuff that's meant to
389 // go on the page; (2) compose scratch as best we can; (3) set the maximum
390 // height available to the two-column part of the page; (4) have the two-
391 // column part compose itself.
392 // In the computation of twocol->htavail, it does not matter that
393 // twocol->height() is merely an upper bound, because it is merely being
394 // subtracted out to give the exact total height of the single-column stuff.
395 void page::compose(int final)
396 {
397 makescratch(final);
398 int adjht = scratch.rawht();
399 if (dbg & 16)
400 printf("# page %d measure %d\n", userpn, adjht);
401 movefloats(&scratch, ((double) adjht)/pagesize);
402 trimspace(&scratch);
403 twocol->htavail = pagesize - (scratch.height() - twocol->height());
404 twocol->compose(final);
405 adjht = scratch.height();
406 if (dbg & 16)
407 printf("# page %d measure %d after trim\n", userpn, adjht);
408 }
409
410 // Fill the scratch area with ranges destined for the page.
411 // If defonly == 0, then add anything that's on stage--this is a trial run.
412 // If defonly != 0, use only what's definitely on the page.
413 void page::makescratch(int defonly)
414 {
415 scratch.freeall();
416 stream cd;
417 for (cd = definite; cd.more(); cd.advance())
418 scratch.append(cd.current());
419 if (!defonly)
420 for (cd = *stage; cd.more(); cd.advance())
421 if (cd.current()->numcol() == 1)
422 scratch.append(cd.current());
423 if (twocol->nonempty())
424 scratch.append(twocol);
425 }
426
427 // Accept the current contents of the stage.
428 // If the stage contains two-column ranges, add a sentinel to indicate the end
429 // of a chunk of stage contents.
430 void page::commit()
431 {
432 if (dbg & 4)
433 printf("#entering page::commit()\n");
434 int numcol = 0;
435 while (stage->more()) {
436 numcol = stage->current()->numcol();
437 adddef(stage->dequeue());
438 }
439 if (numcol == 2)
440 adddef(new sentrange);
441 }
442
443 // Send the current contents of the stage back to its source.
444 void page::welsh()
445 {
446 if (dbg & 4)
447 printf("#entering page::welsh()\n");
448 while (stage->more()) {
449 range *r = stage->dequeue();
450 r->enqueue(ANDBLOCK);
451 }
452 }
453
454 enum { USonly = 1 };
455
456 // So long as anything is eligible to go onto the page, keep trying.
457 // Once nothing is eligible, compose and justify the page.
458 void page::fill()
459 {
460 while (stage->prime())
461 stage->pend();
462 compose(FINAL);
463 if (dbg & 16)
464 scratch.dump();
465 if (anymore()) {
466 int adjht = scratch.height();
467 if (adjht > minfull*pagesize) {
468 justify(&scratch, pagesize);
469 adjht = scratch.height();
470 int stretchamt = max(pagesize - adjht, 0);
471 twocol->stretch(twocol->height() + stretchamt);
472 // in case the page's stretchability lies
473 // entirely in its two-column part
474 } else
475 ERROR "page %d only %.0f%% full; will not be adjusted\n",
476 userpn, 100*(double) adjht/pagesize WARNING;
477 }
478 }
479
480 void page::adddef(range *r)
481 {
482 if (dbg & 4)
483 printf("#entering page::adddef()\n");
484 switch (r->numcol()) {
485 case 1: definite.append(r);
486 break;
487 case 2: twocol->definite.append(r);
488 break;
489 default: ERROR "%d-column range unexpected\n", r->numcol() FATAL;
490 }
491 }
492
493 int multicol::print(int cv, int col)
494 {
495 if (col != 0)
496 ERROR "multicolumn output must start in left column\n" FATAL;
497 int curv = cv, maxv = cv; // print left column
498 for ( ; column[0].more(); column[0].advance()) {
499 curv = column[0].current()->print(curv, 0);
500 maxv = max(maxv, curv);
501 }
502 curv = cv; // print right column
503 for ( ; column[1].more(); column[1].advance()) {
504 curv = column[1].current()->print(curv, 1);
505 maxv = max(maxv, curv);
506 }
507 return maxv;
508 }
509
510 void page::print()
511 {
512 static int tops = 1, bots = 1;
513 if (!scratch.more()) {
514 ERROR "## Here's what's left on squeue:\n" WARNING;
515 squeue.dump();
516 ERROR "## Here's what's left on bfqueue:\n" WARNING;
517 bfqueue.dump();
518 ERROR "## Here's what's left on ufqueue:\n" WARNING;
519 ufqueue.dump();
520 ERROR "page %d appears to be empty\n", userpn WARNING;
521 fflush(stderr), fflush(stdout), exit(0);
522 // something is very wrong if this happens
523 }
524 printf("p%d\n", userpn); // print troff output page number
525 if (ptlist.more()) { // print page header
526 ptlist.current()->print(0, 0);
527 ptlist.advance();
528 } else if (tops) {
529 ERROR "ran out of page titles at %d\n", userpn WARNING;
530 tops = 0;
531 }
532 int curv = 0;
533 printf("V%d\n", curv = pagetop);// print page contents
534 for ( ; scratch.more(); scratch.advance()) {
535 curv = scratch.current()->print(curv, 0);
536 }
537 if (btlist.more()) { // print page footer
538 btlist.current()->print(0, 0);
539 btlist.advance();
540 } else if (bots) {
541 ERROR "ran out of page bottoms at %d\n", userpn WARNING;
542 bots = 0;
543 }
544 printf("V%d\n", physbot); // finish troff output page
545 }
546
547 int pagetop = 0; // top printing margin
548 int pagebot = 0; // bottom printing margin
549 int physbot = 0; // physical bottom of page
550
551 double minfull = 0.9; // minimum fullness before padding
552
553 int pn = 0; // cardinal page number
554 int userpn = 0; // page number derived from PT slugs
555
556 static void makepage()
557 {
558 page pg(pagebot - pagetop);
559 ++pn;
560 userpn = ptlist.more() ? ptlist.current()->pn() : pn;
561 pg.fill();
562 pg.print();
563 }
564
565 static void conv(FILE *fp)
566 {
567 startup(fp); // read slugs, etc.
568 while (anymore())
569 makepage();
570 lastrange->print(0, 0); // trailer
571 checkout(); // check that everything was printed
572 }
573
574 int
575 main(int argc, char **argv)
576 {
577 static FILE *fp = stdin;
578 progname = argv[0];
579 while (argc > 1 && argv[1][0] == '-') {
580 switch (argv[1][1]) {
581 case 'd':
582 dbg = atoi(&argv[1][2]);
583 if (dbg == 0)
584 dbg = ~0;
585 break;
586 case 'm':
587 minfull = 0.01*atof(&argv[1][2]);
588 break;
589 case 'c':
590 coltol = 0.01*atof(&argv[1][2]);
591 break;
592 case 'w':
593 wantwarn = 1;
594 break;
595 }
596 argc--;
597 argv++;
598 }
599 if (argc <= 1)
600 conv(stdin);
601 else
602 while (--argc > 0) {
603 if (strcmp(*++argv, "-") == 0)
604 fp = stdin;
605 else if ((fp = fopen(*argv, "r")) == NULL)
606 ERROR "can't open %s\n", *argv FATAL;
607 conv(fp);
608 fclose(fp);
609 }
610 exit(0);
611 return 0; /* gcc */
612 }