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