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