usr.bin/lex/tblcmp.c

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