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