contrib/flex/tblcmp.c

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