page.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 }