1/* tblcmp - table compression routines */ 2 3/* Copyright (c) 1990 The Regents of the University of California. */ 4/* All rights reserved. */ 5 6/* This code is derived from software contributed to Berkeley by */ 7/* Vern Paxson. */ 8 9/* The United States Government has rights in this work pursuant */ 10/* to contract no. DE-AC03-76SF00098 between the United States */ 11/* Department of Energy and the University of California. */ 12 13/* This file is part of flex. */ 14 15/* Redistribution and use in source and binary forms, with or without */ 16/* modification, are permitted provided that the following conditions */ 17/* are met: */ 18 19/* 1. Redistributions of source code must retain the above copyright */ 20/* notice, this list of conditions and the following disclaimer. */ 21/* 2. Redistributions in binary form must reproduce the above copyright */ 22/* notice, this list of conditions and the following disclaimer in the */ 23/* documentation and/or other materials provided with the distribution. */ 24 25/* Neither the name of the University nor the names of its contributors */ 26/* may be used to endorse or promote products derived from this software */ 27/* without specific prior written permission. */ 28 29/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 30/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 31/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 32/* PURPOSE. */ 33 34#include "flexdef.h" 35 36 37/* declarations for functions that have forward references */ 38 39void mkentry PROTO ((int *, int, int, int, int)); 40void mkprot PROTO ((int[], int, int)); 41void mktemplate PROTO ((int[], int, int)); 42void mv2front PROTO ((int)); 43int tbldiff PROTO ((int[], int, int[])); 44 45 46/* bldtbl - build table entries for dfa state 47 * 48 * synopsis 49 * int state[numecs], statenum, totaltrans, comstate, comfreq; 50 * bldtbl( state, statenum, totaltrans, comstate, comfreq ); 51 * 52 * State is the statenum'th dfa state. It is indexed by equivalence class and 53 * gives the number of the state to enter for a given equivalence class. 54 * totaltrans is the total number of transitions out of the state. Comstate 55 * is that state which is the destination of the most transitions out of State. 56 * Comfreq is how many transitions there are out of State to Comstate. 57 * 58 * A note on terminology: 59 * "protos" are transition tables which have a high probability of 60 * either being redundant (a state processed later will have an identical 61 * transition table) or nearly redundant (a state processed later will have 62 * many of the same out-transitions). A "most recently used" queue of 63 * protos is kept around with the hope that most states will find a proto 64 * which is similar enough to be usable, and therefore compacting the 65 * output tables. 66 * "templates" are a special type of proto. If a transition table is 67 * homogeneous or nearly homogeneous (all transitions go to the same 68 * destination) then the odds are good that future states will also go 69 * to the same destination state on basically the same character set. 70 * These homogeneous states are so common when dealing with large rule 71 * sets that they merit special attention. If the transition table were 72 * simply made into a proto, then (typically) each subsequent, similar 73 * state will differ from the proto for two out-transitions. One of these 74 * out-transitions will be that character on which the proto does not go 75 * to the common destination, and one will be that character on which the 76 * state does not go to the common destination. Templates, on the other 77 * hand, go to the common state on EVERY transition character, and therefore 78 * cost only one difference. 79 */ 80 81void bldtbl (state, statenum, totaltrans, comstate, comfreq) 82 int state[], statenum, totaltrans, comstate, comfreq; 83{ 84 int extptr, extrct[2][CSIZE + 1]; 85 int mindiff, minprot, i, d; 86 87 /* If extptr is 0 then the first array of extrct holds the result 88 * of the "best difference" to date, which is those transitions 89 * which occur in "state" but not in the proto which, to date, 90 * has the fewest differences between itself and "state". If 91 * extptr is 1 then the second array of extrct hold the best 92 * difference. The two arrays are toggled between so that the 93 * best difference to date can be kept around and also a difference 94 * just created by checking against a candidate "best" proto. 95 */ 96 97 extptr = 0; 98 99 /* If the state has too few out-transitions, don't bother trying to 100 * compact its tables. 101 */ 102 103 if ((totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE)) 104 mkentry (state, numecs, statenum, JAMSTATE, totaltrans); 105 106 else { 107 /* "checkcom" is true if we should only check "state" against 108 * protos which have the same "comstate" value. 109 */ 110 int checkcom = 111 112 comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; 113 114 minprot = firstprot; 115 mindiff = totaltrans; 116 117 if (checkcom) { 118 /* Find first proto which has the same "comstate". */ 119 for (i = firstprot; i != NIL; i = protnext[i]) 120 if (protcomst[i] == comstate) { 121 minprot = i; 122 mindiff = tbldiff (state, minprot, 123 extrct[extptr]); 124 break; 125 } 126 } 127 128 else { 129 /* Since we've decided that the most common destination 130 * out of "state" does not occur with a high enough 131 * frequency, we set the "comstate" to zero, assuring 132 * that if this state is entered into the proto list, 133 * it will not be considered a template. 134 */ 135 comstate = 0; 136 137 if (firstprot != NIL) { 138 minprot = firstprot; 139 mindiff = tbldiff (state, minprot, 140 extrct[extptr]); 141 } 142 } 143 144 /* We now have the first interesting proto in "minprot". If 145 * it matches within the tolerances set for the first proto, 146 * we don't want to bother scanning the rest of the proto list 147 * to see if we have any other reasonable matches. 148 */ 149 150 if (mindiff * 100 > 151 totaltrans * FIRST_MATCH_DIFF_PERCENTAGE) { 152 /* Not a good enough match. Scan the rest of the 153 * protos. 154 */ 155 for (i = minprot; i != NIL; i = protnext[i]) { 156 d = tbldiff (state, i, extrct[1 - extptr]); 157 if (d < mindiff) { 158 extptr = 1 - extptr; 159 mindiff = d; 160 minprot = i; 161 } 162 } 163 } 164 165 /* Check if the proto we've decided on as our best bet is close 166 * enough to the state we want to match to be usable. 167 */ 168 169 if (mindiff * 100 > 170 totaltrans * ACCEPTABLE_DIFF_PERCENTAGE) { 171 /* No good. If the state is homogeneous enough, 172 * we make a template out of it. Otherwise, we 173 * make a proto. 174 */ 175 176 if (comfreq * 100 >= 177 totaltrans * TEMPLATE_SAME_PERCENTAGE) 178 mktemplate (state, statenum, 179 comstate); 180 181 else { 182 mkprot (state, statenum, comstate); 183 mkentry (state, numecs, statenum, 184 JAMSTATE, totaltrans); 185 } 186 } 187 188 else { /* use the proto */ 189 mkentry (extrct[extptr], numecs, statenum, 190 prottbl[minprot], mindiff); 191 192 /* If this state was sufficiently different from the 193 * proto we built it from, make it, too, a proto. 194 */ 195 196 if (mindiff * 100 >= 197 totaltrans * NEW_PROTO_DIFF_PERCENTAGE) 198 mkprot (state, statenum, comstate); 199 200 /* Since mkprot added a new proto to the proto queue, 201 * it's possible that "minprot" is no longer on the 202 * proto queue (if it happened to have been the last 203 * entry, it would have been bumped off). If it's 204 * not there, then the new proto took its physical 205 * place (though logically the new proto is at the 206 * beginning of the queue), so in that case the 207 * following call will do nothing. 208 */ 209 210 mv2front (minprot); 211 } 212 } 213} 214 215 216/* cmptmps - compress template table entries 217 * 218 * Template tables are compressed by using the 'template equivalence 219 * classes', which are collections of transition character equivalence 220 * classes which always appear together in templates - really meta-equivalence 221 * classes. 222 */ 223 224void cmptmps () 225{ 226 int tmpstorage[CSIZE + 1]; 227 int *tmp = tmpstorage, i, j; 228 int totaltrans, trans; 229 230 peakpairs = numtemps * numecs + tblend; 231 232 if (usemecs) { 233 /* Create equivalence classes based on data gathered on 234 * template transitions. 235 */ 236 nummecs = cre8ecs (tecfwd, tecbck, numecs); 237 } 238 239 else 240 nummecs = numecs; 241 242 while (lastdfa + numtemps + 1 >= current_max_dfas) 243 increase_max_dfas (); 244 245 /* Loop through each template. */ 246 247 for (i = 1; i <= numtemps; ++i) { 248 /* Number of non-jam transitions out of this template. */ 249 totaltrans = 0; 250 251 for (j = 1; j <= numecs; ++j) { 252 trans = tnxt[numecs * i + j]; 253 254 if (usemecs) { 255 /* The absolute value of tecbck is the 256 * meta-equivalence class of a given 257 * equivalence class, as set up by cre8ecs(). 258 */ 259 if (tecbck[j] > 0) { 260 tmp[tecbck[j]] = trans; 261 262 if (trans > 0) 263 ++totaltrans; 264 } 265 } 266 267 else { 268 tmp[j] = trans; 269 270 if (trans > 0) 271 ++totaltrans; 272 } 273 } 274 275 /* It is assumed (in a rather subtle way) in the skeleton 276 * that if we're using meta-equivalence classes, the def[] 277 * entry for all templates is the jam template, i.e., 278 * templates never default to other non-jam table entries 279 * (e.g., another template) 280 */ 281 282 /* Leave room for the jam-state after the last real state. */ 283 mkentry (tmp, nummecs, lastdfa + i + 1, JAMSTATE, 284 totaltrans); 285 } 286} 287 288 289 290/* expand_nxt_chk - expand the next check arrays */ 291 292void expand_nxt_chk () 293{ 294 int old_max = current_max_xpairs; 295 296 current_max_xpairs += MAX_XPAIRS_INCREMENT; 297 298 ++num_reallocs; 299 300 nxt = reallocate_integer_array (nxt, current_max_xpairs); 301 chk = reallocate_integer_array (chk, current_max_xpairs); 302 303 zero_out ((char *) (chk + old_max), 304 (size_t) (MAX_XPAIRS_INCREMENT * sizeof (int))); 305} 306 307 308/* find_table_space - finds a space in the table for a state to be placed 309 * 310 * synopsis 311 * int *state, numtrans, block_start; 312 * int find_table_space(); 313 * 314 * block_start = find_table_space( state, numtrans ); 315 * 316 * State is the state to be added to the full speed transition table. 317 * Numtrans is the number of out-transitions for the state. 318 * 319 * find_table_space() returns the position of the start of the first block (in 320 * chk) able to accommodate the state 321 * 322 * In determining if a state will or will not fit, find_table_space() must take 323 * into account the fact that an end-of-buffer state will be added at [0], 324 * and an action number will be added in [-1]. 325 */ 326 327int find_table_space (state, numtrans) 328 int *state, numtrans; 329{ 330 /* Firstfree is the position of the first possible occurrence of two 331 * consecutive unused records in the chk and nxt arrays. 332 */ 333 int i; 334 int *state_ptr, *chk_ptr; 335 int *ptr_to_last_entry_in_state; 336 337 /* If there are too many out-transitions, put the state at the end of 338 * nxt and chk. 339 */ 340 if (numtrans > MAX_XTIONS_FULL_INTERIOR_FIT) { 341 /* If table is empty, return the first available spot in 342 * chk/nxt, which should be 1. 343 */ 344 if (tblend < 2) 345 return 1; 346 347 /* Start searching for table space near the end of 348 * chk/nxt arrays. 349 */ 350 i = tblend - numecs; 351 } 352 353 else 354 /* Start searching for table space from the beginning 355 * (skipping only the elements which will definitely not 356 * hold the new state). 357 */ 358 i = firstfree; 359 360 while (1) { /* loops until a space is found */ 361 while (i + numecs >= current_max_xpairs) 362 expand_nxt_chk (); 363 364 /* Loops until space for end-of-buffer and action number 365 * are found. 366 */ 367 while (1) { 368 /* Check for action number space. */ 369 if (chk[i - 1] == 0) { 370 /* Check for end-of-buffer space. */ 371 if (chk[i] == 0) 372 break; 373 374 else 375 /* Since i != 0, there is no use 376 * checking to see if (++i) - 1 == 0, 377 * because that's the same as i == 0, 378 * so we skip a space. 379 */ 380 i += 2; 381 } 382 383 else 384 ++i; 385 386 while (i + numecs >= current_max_xpairs) 387 expand_nxt_chk (); 388 } 389 390 /* If we started search from the beginning, store the new 391 * firstfree for the next call of find_table_space(). 392 */ 393 if (numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT) 394 firstfree = i + 1; 395 396 /* Check to see if all elements in chk (and therefore nxt) 397 * that are needed for the new state have not yet been taken. 398 */ 399 400 state_ptr = &state[1]; 401 ptr_to_last_entry_in_state = &chk[i + numecs + 1]; 402 403 for (chk_ptr = &chk[i + 1]; 404 chk_ptr != ptr_to_last_entry_in_state; ++chk_ptr) 405 if (*(state_ptr++) != 0 && *chk_ptr != 0) 406 break; 407 408 if (chk_ptr == ptr_to_last_entry_in_state) 409 return i; 410 411 else 412 ++i; 413 } 414} 415 416 417/* inittbl - initialize transition tables 418 * 419 * Initializes "firstfree" to be one beyond the end of the table. Initializes 420 * all "chk" entries to be zero. 421 */ 422void inittbl () 423{ 424 int i; 425 426 zero_out ((char *) chk, 427 428 (size_t) (current_max_xpairs * sizeof (int))); 429 430 tblend = 0; 431 firstfree = tblend + 1; 432 numtemps = 0; 433 434 if (usemecs) { 435 /* Set up doubly-linked meta-equivalence classes; these 436 * are sets of equivalence classes which all have identical 437 * transitions out of TEMPLATES. 438 */ 439 440 tecbck[1] = NIL; 441 442 for (i = 2; i <= numecs; ++i) { 443 tecbck[i] = i - 1; 444 tecfwd[i - 1] = i; 445 } 446 447 tecfwd[numecs] = NIL; 448 } 449} 450 451 452/* mkdeftbl - make the default, "jam" table entries */ 453 454void mkdeftbl () 455{ 456 int i; 457 458 jamstate = lastdfa + 1; 459 460 ++tblend; /* room for transition on end-of-buffer character */ 461 462 while (tblend + numecs >= current_max_xpairs) 463 expand_nxt_chk (); 464 465 /* Add in default end-of-buffer transition. */ 466 nxt[tblend] = end_of_buffer_state; 467 chk[tblend] = jamstate; 468 469 for (i = 1; i <= numecs; ++i) { 470 nxt[tblend + i] = 0; 471 chk[tblend + i] = jamstate; 472 } 473 474 jambase = tblend; 475 476 base[jamstate] = jambase; 477 def[jamstate] = 0; 478 479 tblend += numecs; 480 ++numtemps; 481} 482 483 484/* mkentry - create base/def and nxt/chk entries for transition array 485 * 486 * synopsis 487 * int state[numchars + 1], numchars, statenum, deflink, totaltrans; 488 * mkentry( state, numchars, statenum, deflink, totaltrans ); 489 * 490 * "state" is a transition array "numchars" characters in size, "statenum" 491 * is the offset to be used into the base/def tables, and "deflink" is the 492 * entry to put in the "def" table entry. If "deflink" is equal to 493 * "JAMSTATE", then no attempt will be made to fit zero entries of "state" 494 * (i.e., jam entries) into the table. It is assumed that by linking to 495 * "JAMSTATE" they will be taken care of. In any case, entries in "state" 496 * marking transitions to "SAME_TRANS" are treated as though they will be 497 * taken care of by wherever "deflink" points. "totaltrans" is the total 498 * number of transitions out of the state. If it is below a certain threshold, 499 * the tables are searched for an interior spot that will accommodate the 500 * state array. 501 */ 502 503void mkentry (state, numchars, statenum, deflink, totaltrans) 504 int *state; 505 int numchars, statenum, deflink, totaltrans; 506{ 507 int minec, maxec, i, baseaddr; 508 int tblbase, tbllast; 509 510 if (totaltrans == 0) { /* there are no out-transitions */ 511 if (deflink == JAMSTATE) 512 base[statenum] = JAMSTATE; 513 else 514 base[statenum] = 0; 515 516 def[statenum] = deflink; 517 return; 518 } 519 520 for (minec = 1; minec <= numchars; ++minec) { 521 if (state[minec] != SAME_TRANS) 522 if (state[minec] != 0 || deflink != JAMSTATE) 523 break; 524 } 525 526 if (totaltrans == 1) { 527 /* There's only one out-transition. Save it for later to fill 528 * in holes in the tables. 529 */ 530 stack1 (statenum, minec, state[minec], deflink); 531 return; 532 } 533 534 for (maxec = numchars; maxec > 0; --maxec) { 535 if (state[maxec] != SAME_TRANS) 536 if (state[maxec] != 0 || deflink != JAMSTATE) 537 break; 538 } 539 540 /* Whether we try to fit the state table in the middle of the table 541 * entries we have already generated, or if we just take the state 542 * table at the end of the nxt/chk tables, we must make sure that we 543 * have a valid base address (i.e., non-negative). Note that 544 * negative base addresses dangerous at run-time (because indexing 545 * the nxt array with one and a low-valued character will access 546 * memory before the start of the array. 547 */ 548 549 /* Find the first transition of state that we need to worry about. */ 550 if (totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE) { 551 /* Attempt to squeeze it into the middle of the tables. */ 552 baseaddr = firstfree; 553 554 while (baseaddr < minec) { 555 /* Using baseaddr would result in a negative base 556 * address below; find the next free slot. 557 */ 558 for (++baseaddr; chk[baseaddr] != 0; ++baseaddr) ; 559 } 560 561 while (baseaddr + maxec - minec + 1 >= current_max_xpairs) 562 expand_nxt_chk (); 563 564 for (i = minec; i <= maxec; ++i) 565 if (state[i] != SAME_TRANS && 566 (state[i] != 0 || deflink != JAMSTATE) && 567 chk[baseaddr + i - minec] != 0) { /* baseaddr unsuitable - find another */ 568 for (++baseaddr; 569 baseaddr < current_max_xpairs && 570 chk[baseaddr] != 0; ++baseaddr) ; 571 572 while (baseaddr + maxec - minec + 1 >= 573 current_max_xpairs) 574 expand_nxt_chk (); 575 576 /* Reset the loop counter so we'll start all 577 * over again next time it's incremented. 578 */ 579 580 i = minec - 1; 581 } 582 } 583 584 else { 585 /* Ensure that the base address we eventually generate is 586 * non-negative. 587 */ 588 baseaddr = MAX (tblend + 1, minec); 589 } 590 591 tblbase = baseaddr - minec; 592 tbllast = tblbase + maxec; 593 594 while (tbllast + 1 >= current_max_xpairs) 595 expand_nxt_chk (); 596 597 base[statenum] = tblbase; 598 def[statenum] = deflink; 599 600 for (i = minec; i <= maxec; ++i) 601 if (state[i] != SAME_TRANS) 602 if (state[i] != 0 || deflink != JAMSTATE) { 603 nxt[tblbase + i] = state[i]; 604 chk[tblbase + i] = statenum; 605 } 606 607 if (baseaddr == firstfree) 608 /* Find next free slot in tables. */ 609 for (++firstfree; chk[firstfree] != 0; ++firstfree) ; 610 611 tblend = MAX (tblend, tbllast); 612} 613 614 615/* mk1tbl - create table entries for a state (or state fragment) which 616 * has only one out-transition 617 */ 618 619void mk1tbl (state, sym, onenxt, onedef) 620 int state, sym, onenxt, onedef; 621{ 622 if (firstfree < sym) 623 firstfree = sym; 624 625 while (chk[firstfree] != 0) 626 if (++firstfree >= current_max_xpairs) 627 expand_nxt_chk (); 628 629 base[state] = firstfree - sym; 630 def[state] = onedef; 631 chk[firstfree] = state; 632 nxt[firstfree] = onenxt; 633 634 if (firstfree > tblend) { 635 tblend = firstfree++; 636 637 if (firstfree >= current_max_xpairs) 638 expand_nxt_chk (); 639 } 640} 641 642 643/* mkprot - create new proto entry */ 644 645void mkprot (state, statenum, comstate) 646 int state[], statenum, comstate; 647{ 648 int i, slot, tblbase; 649 650 if (++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE) { 651 /* Gotta make room for the new proto by dropping last entry in 652 * the queue. 653 */ 654 slot = lastprot; 655 lastprot = protprev[lastprot]; 656 protnext[lastprot] = NIL; 657 } 658 659 else 660 slot = numprots; 661 662 protnext[slot] = firstprot; 663 664 if (firstprot != NIL) 665 protprev[firstprot] = slot; 666 667 firstprot = slot; 668 prottbl[slot] = statenum; 669 protcomst[slot] = comstate; 670 671 /* Copy state into save area so it can be compared with rapidly. */ 672 tblbase = numecs * (slot - 1); 673 674 for (i = 1; i <= numecs; ++i) 675 protsave[tblbase + i] = state[i]; 676} 677 678 679/* mktemplate - create a template entry based on a state, and connect the state 680 * to it 681 */ 682 683void mktemplate (state, statenum, comstate) 684 int state[], statenum, comstate; 685{ 686 int i, numdiff, tmpbase, tmp[CSIZE + 1]; 687 Char transset[CSIZE + 1]; 688 int tsptr; 689 690 ++numtemps; 691 692 tsptr = 0; 693 694 /* Calculate where we will temporarily store the transition table 695 * of the template in the tnxt[] array. The final transition table 696 * gets created by cmptmps(). 697 */ 698 699 tmpbase = numtemps * numecs; 700 701 if (tmpbase + numecs >= current_max_template_xpairs) { 702 current_max_template_xpairs += 703 MAX_TEMPLATE_XPAIRS_INCREMENT; 704 705 ++num_reallocs; 706 707 tnxt = reallocate_integer_array (tnxt, 708 current_max_template_xpairs); 709 } 710 711 for (i = 1; i <= numecs; ++i) 712 if (state[i] == 0) 713 tnxt[tmpbase + i] = 0; 714 else { 715 transset[tsptr++] = i; 716 tnxt[tmpbase + i] = comstate; 717 } 718 719 if (usemecs) 720 mkeccl (transset, tsptr, tecfwd, tecbck, numecs, 0); 721 722 mkprot (tnxt + tmpbase, -numtemps, comstate); 723 724 /* We rely on the fact that mkprot adds things to the beginning 725 * of the proto queue. 726 */ 727 728 numdiff = tbldiff (state, firstprot, tmp); 729 mkentry (tmp, numecs, statenum, -numtemps, numdiff); 730} 731 732 733/* mv2front - move proto queue element to front of queue */ 734 735void mv2front (qelm) 736 int qelm; 737{ 738 if (firstprot != qelm) { 739 if (qelm == lastprot) 740 lastprot = protprev[lastprot]; 741 742 protnext[protprev[qelm]] = protnext[qelm]; 743 744 if (protnext[qelm] != NIL) 745 protprev[protnext[qelm]] = protprev[qelm]; 746 747 protprev[qelm] = NIL; 748 protnext[qelm] = firstprot; 749 protprev[firstprot] = qelm; 750 firstprot = qelm; 751 } 752} 753 754 755/* place_state - place a state into full speed transition table 756 * 757 * State is the statenum'th state. It is indexed by equivalence class and 758 * gives the number of the state to enter for a given equivalence class. 759 * Transnum is the number of out-transitions for the state. 760 */ 761 762void place_state (state, statenum, transnum) 763 int *state, statenum, transnum; 764{ 765 int i; 766 int *state_ptr; 767 int position = find_table_space (state, transnum); 768 769 /* "base" is the table of start positions. */ 770 base[statenum] = position; 771 772 /* Put in action number marker; this non-zero number makes sure that 773 * find_table_space() knows that this position in chk/nxt is taken 774 * and should not be used for another accepting number in another 775 * state. 776 */ 777 chk[position - 1] = 1; 778 779 /* Put in end-of-buffer marker; this is for the same purposes as 780 * above. 781 */ 782 chk[position] = 1; 783 784 /* Place the state into chk and nxt. */ 785 state_ptr = &state[1]; 786 787 for (i = 1; i <= numecs; ++i, ++state_ptr) 788 if (*state_ptr != 0) { 789 chk[position + i] = i; 790 nxt[position + i] = *state_ptr; 791 } 792 793 if (position + numecs > tblend) 794 tblend = position + numecs; 795} 796 797 798/* stack1 - save states with only one out-transition to be processed later 799 * 800 * If there's room for another state on the "one-transition" stack, the 801 * state is pushed onto it, to be processed later by mk1tbl. If there's 802 * no room, we process the sucker right now. 803 */ 804 805void stack1 (statenum, sym, nextstate, deflink) 806 int statenum, sym, nextstate, deflink; 807{ 808 if (onesp >= ONE_STACK_SIZE - 1) 809 mk1tbl (statenum, sym, nextstate, deflink); 810 811 else { 812 ++onesp; 813 onestate[onesp] = statenum; 814 onesym[onesp] = sym; 815 onenext[onesp] = nextstate; 816 onedef[onesp] = deflink; 817 } 818} 819 820 821/* tbldiff - compute differences between two state tables 822 * 823 * "state" is the state array which is to be extracted from the pr'th 824 * proto. "pr" is both the number of the proto we are extracting from 825 * and an index into the save area where we can find the proto's complete 826 * state table. Each entry in "state" which differs from the corresponding 827 * entry of "pr" will appear in "ext". 828 * 829 * Entries which are the same in both "state" and "pr" will be marked 830 * as transitions to "SAME_TRANS" in "ext". The total number of differences 831 * between "state" and "pr" is returned as function value. Note that this 832 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 833 */ 834 835int tbldiff (state, pr, ext) 836 int state[], pr, ext[]; 837{ 838 int i, *sp = state, *ep = ext, *protp; 839 int numdiff = 0; 840 841 protp = &protsave[numecs * (pr - 1)]; 842 843 for (i = numecs; i > 0; --i) { 844 if (*++protp == *++sp) 845 *++ep = SAME_TRANS; 846 else { 847 *++ep = *sp; 848 ++numdiff; 849 } 850 } 851 852 return numdiff; 853} 854