tblcmp.c revision 250873
11590Srgrimes/* tblcmp - table compression routines */ 21590Srgrimes 31590Srgrimes/* Copyright (c) 1990 The Regents of the University of California. */ 41590Srgrimes/* All rights reserved. */ 51590Srgrimes 61590Srgrimes/* This code is derived from software contributed to Berkeley by */ 71590Srgrimes/* Vern Paxson. */ 81590Srgrimes 91590Srgrimes/* The United States Government has rights in this work pursuant */ 101590Srgrimes/* to contract no. DE-AC03-76SF00098 between the United States */ 111590Srgrimes/* Department of Energy and the University of California. */ 121590Srgrimes 131590Srgrimes/* This file is part of flex. */ 141590Srgrimes 151590Srgrimes/* Redistribution and use in source and binary forms, with or without */ 161590Srgrimes/* modification, are permitted provided that the following conditions */ 171590Srgrimes/* are met: */ 181590Srgrimes 191590Srgrimes/* 1. Redistributions of source code must retain the above copyright */ 201590Srgrimes/* notice, this list of conditions and the following disclaimer. */ 211590Srgrimes/* 2. Redistributions in binary form must reproduce the above copyright */ 221590Srgrimes/* notice, this list of conditions and the following disclaimer in the */ 231590Srgrimes/* documentation and/or other materials provided with the distribution. */ 241590Srgrimes 251590Srgrimes/* Neither the name of the University nor the names of its contributors */ 261590Srgrimes/* may be used to endorse or promote products derived from this software */ 271590Srgrimes/* without specific prior written permission. */ 281590Srgrimes 291590Srgrimes/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 301590Srgrimes/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 311590Srgrimes/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 321590Srgrimes/* PURPOSE. */ 331590Srgrimes 3427575Scharnier#include "flexdef.h" 351590Srgrimes 361590Srgrimes 371590Srgrimes/* declarations for functions that have forward references */ 381590Srgrimes 391590Srgrimesvoid mkentry PROTO ((register int *, int, int, int, int)); 4027575Scharniervoid mkprot PROTO ((int[], int, int)); 411590Srgrimesvoid mktemplate PROTO ((int[], int, int)); 4227575Scharniervoid mv2front PROTO ((int)); 431590Srgrimesint tbldiff PROTO ((int[], int, int[])); 4499112Sobrien 4599112Sobrien 461590Srgrimes/* bldtbl - build table entries for dfa state 471590Srgrimes * 4899709Sdd * synopsis 4999709Sdd * int state[numecs], statenum, totaltrans, comstate, comfreq; 501590Srgrimes * bldtbl( state, statenum, totaltrans, comstate, comfreq ); 511590Srgrimes * 521590Srgrimes * State is the statenum'th dfa state. It is indexed by equivalence class and 531590Srgrimes * gives the number of the state to enter for a given equivalence class. 541590Srgrimes * totaltrans is the total number of transitions out of the state. Comstate 551590Srgrimes * is that state which is the destination of the most transitions out of State. 561590Srgrimes * Comfreq is how many transitions there are out of State to Comstate. 571590Srgrimes * 581590Srgrimes * A note on terminology: 59100806Sdd * "protos" are transition tables which have a high probability of 6027575Scharnier * either being redundant (a state processed later will have an identical 61200462Sdelphij * transition table) or nearly redundant (a state processed later will have 62124824Scperciva * many of the same out-transitions). A "most recently used" queue of 63216696Sed * protos is kept around with the hope that most states will find a proto 6427575Scharnier * which is similar enough to be usable, and therefore compacting the 65209567Sgavin * output tables. 661590Srgrimes * "templates" are a special type of proto. If a transition table is 6727575Scharnier * homogeneous or nearly homogeneous (all transitions go to the same 681590Srgrimes * destination) then the odds are good that future states will also go 6952158Snectar * to the same destination state on basically the same character set. 70110609Stjr * These homogeneous states are so common when dealing with large rule 7127575Scharnier * sets that they merit special attention. If the transition table were 721590Srgrimes * simply made into a proto, then (typically) each subsequent, similar 731590Srgrimes * state will differ from the proto for two out-transitions. One of these 741590Srgrimes * out-transitions will be that character on which the proto does not go 7592920Simp * to the common destination, and one will be that character on which the 7692920Simp * state does not go to the common destination. Templates, on the other 7792920Simp * hand, go to the common state on EVERY transition character, and therefore 7892920Simp * cost only one difference. 791590Srgrimes */ 801590Srgrimes 811590Srgrimesvoid bldtbl (state, statenum, totaltrans, comstate, comfreq) 82110609Stjr int state[], statenum, totaltrans, comstate, comfreq; 831590Srgrimes{ 8418295Sroberto int extptr, extrct[2][CSIZE + 1]; 85100806Sdd int mindiff, minprot, i, d; 861590Srgrimes 871590Srgrimes /* If extptr is 0 then the first array of extrct holds the result 8827575Scharnier * of the "best difference" to date, which is those transitions 89102944Sdwmalone * which occur in "state" but not in the proto which, to date, 901590Srgrimes * has the fewest differences between itself and "state". If 911590Srgrimes * extptr is 1 then the second array of extrct hold the best 921590Srgrimes * difference. The two arrays are toggled between so that the 9337262Sbde * best difference to date can be kept around and also a difference 941590Srgrimes * just created by checking against a candidate "best" proto. 951590Srgrimes */ 96100806Sdd 971590Srgrimes extptr = 0; 981590Srgrimes 991590Srgrimes /* If the state has too few out-transitions, don't bother trying to 10052158Snectar * compact its tables. 10152158Snectar */ 1021590Srgrimes 103216696Sed if ((totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE)) 1041590Srgrimes mkentry (state, numecs, statenum, JAMSTATE, totaltrans); 1051590Srgrimes 10699708Sdd else { 107100806Sdd /* "checkcom" is true if we should only check "state" against 108100806Sdd * protos which have the same "comstate" value. 1091590Srgrimes */ 1101590Srgrimes int checkcom = 11127575Scharnier 11227575Scharnier comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE; 1131590Srgrimes 1141590Srgrimes minprot = firstprot; 1151590Srgrimes mindiff = totaltrans; 11627575Scharnier 11727575Scharnier if (checkcom) { 1181590Srgrimes /* Find first proto which has the same "comstate". */ 1191590Srgrimes for (i = firstprot; i != NIL; i = protnext[i]) 12099708Sdd if (protcomst[i] == comstate) { 12199708Sdd minprot = i; 12299708Sdd mindiff = tbldiff (state, minprot, 123100806Sdd extrct[extptr]); 124100806Sdd break; 125100806Sdd } 1261590Srgrimes } 1271590Srgrimes 12827575Scharnier else { 12999708Sdd /* Since we've decided that the most common destination 1301590Srgrimes * out of "state" does not occur with a high enough 1311590Srgrimes * frequency, we set the "comstate" to zero, assuring 1321590Srgrimes * that if this state is entered into the proto list, 1331590Srgrimes * it will not be considered a template. 134110609Stjr */ 1351590Srgrimes comstate = 0; 1361590Srgrimes 13727575Scharnier if (firstprot != NIL) { 13827575Scharnier minprot = firstprot; 139216696Sed mindiff = tbldiff (state, minprot, 140216696Sed extrct[extptr]); 14127575Scharnier } 14227575Scharnier } 1431590Srgrimes 14437262Sbde /* We now have the first interesting proto in "minprot". If 14537262Sbde * it matches within the tolerances set for the first proto, 1461590Srgrimes * we don't want to bother scanning the rest of the proto list 1471590Srgrimes * to see if we have any other reasonable matches. 1481590Srgrimes */ 1491590Srgrimes 1501590Srgrimes if (mindiff * 100 > 151110609Stjr totaltrans * FIRST_MATCH_DIFF_PERCENTAGE) { 152110609Stjr /* Not a good enough match. Scan the rest of the 1531590Srgrimes * protos. 1541590Srgrimes */ 1551590Srgrimes for (i = minprot; i != NIL; i = protnext[i]) { 1561590Srgrimes d = tbldiff (state, i, extrct[1 - extptr]); 1571590Srgrimes if (d < mindiff) { 15887286Sdwmalone extptr = 1 - extptr; 1591590Srgrimes mindiff = d; 1601590Srgrimes minprot = i; 1611590Srgrimes } 1621590Srgrimes } 1631590Srgrimes } 1641590Srgrimes 1651590Srgrimes /* Check if the proto we've decided on as our best bet is close 1661590Srgrimes * enough to the state we want to match to be usable. 1671590Srgrimes */ 168110609Stjr 1691590Srgrimes if (mindiff * 100 > 1701590Srgrimes totaltrans * ACCEPTABLE_DIFF_PERCENTAGE) { 17127575Scharnier /* No good. If the state is homogeneous enough, 1721590Srgrimes * we make a template out of it. Otherwise, we 1731590Srgrimes * make a proto. 1741590Srgrimes */ 1751590Srgrimes 1761590Srgrimes if (comfreq * 100 >= 1771590Srgrimes totaltrans * TEMPLATE_SAME_PERCENTAGE) 1781590Srgrimes mktemplate (state, statenum, 1791590Srgrimes comstate); 1801590Srgrimes 1811590Srgrimes else { 1821590Srgrimes mkprot (state, statenum, comstate); 18399708Sdd mkentry (state, numecs, statenum, 18499708Sdd JAMSTATE, totaltrans); 185100806Sdd } 186100806Sdd } 187100806Sdd 188100806Sdd else { /* use the proto */ 189100806Sdd mkentry (extrct[extptr], numecs, statenum, 190100806Sdd prottbl[minprot], mindiff); 191100806Sdd 192100806Sdd /* If this state was sufficiently different from the 193110609Stjr * proto we built it from, make it, too, a proto. 194100806Sdd */ 195100806Sdd 196100806Sdd if (mindiff * 100 >= 197100806Sdd totaltrans * NEW_PROTO_DIFF_PERCENTAGE) 1981590Srgrimes mkprot (state, statenum, comstate); 1991590Srgrimes 200216696Sed /* Since mkprot added a new proto to the proto queue, 201216737Sed * it's possible that "minprot" is no longer on the 202216737Sed * proto queue (if it happened to have been the last 203216696Sed * entry, it would have been bumped off). If it's 204216696Sed * not there, then the new proto took its physical 205100806Sdd * place (though logically the new proto is at the 206100806Sdd * beginning of the queue), so in that case the 207100806Sdd * following call will do nothing. 208100806Sdd */ 209100806Sdd 210100806Sdd mv2front (minprot); 211100806Sdd } 212100806Sdd } 213100806Sdd} 21499708Sdd 2151590Srgrimes 2161590Srgrimes/* cmptmps - compress template table entries 2171590Srgrimes * 2181590Srgrimes * Template tables are compressed by using the 'template equivalence 2191590Srgrimes * classes', which are collections of transition character equivalence 22087286Sdwmalone * classes which always appear together in templates - really meta-equivalence 221124824Scperciva * classes. 2221590Srgrimes */ 2231590Srgrimes 2241590Srgrimesvoid cmptmps () 2251590Srgrimes{ 2261590Srgrimes int tmpstorage[CSIZE + 1]; 2271590Srgrimes register int *tmp = tmpstorage, i, j; 2281590Srgrimes int totaltrans, trans; 2291590Srgrimes 2301590Srgrimes peakpairs = numtemps * numecs + tblend; 23152158Snectar 23252158Snectar if (usemecs) { 23352158Snectar /* Create equivalence classes based on data gathered on 23452158Snectar * template transitions. 235124824Scperciva */ 236124824Scperciva nummecs = cre8ecs (tecfwd, tecbck, numecs); 2371590Srgrimes } 23852158Snectar 2391590Srgrimes else 24052158Snectar nummecs = numecs; 24199708Sdd 24299708Sdd while (lastdfa + numtemps + 1 >= current_max_dfas) 24387286Sdwmalone increase_max_dfas (); 24427575Scharnier 2451590Srgrimes /* Loop through each template. */ 2461590Srgrimes 24727575Scharnier for (i = 1; i <= numtemps; ++i) { 24827575Scharnier /* Number of non-jam transitions out of this template. */ 249102944Sdwmalone totaltrans = 0; 25027575Scharnier 251100806Sdd for (j = 1; j <= numecs; ++j) { 25227575Scharnier trans = tnxt[numecs * i + j]; 25327575Scharnier 25427575Scharnier if (usemecs) { 2551590Srgrimes /* The absolute value of tecbck is the 25687286Sdwmalone * meta-equivalence class of a given 2571590Srgrimes * equivalence class, as set up by cre8ecs(). 2581590Srgrimes */ 2591590Srgrimes if (tecbck[j] > 0) { 26099708Sdd tmp[tecbck[j]] = trans; 26199708Sdd 26299708Sdd if (trans > 0) 26399708Sdd ++totaltrans; 26499708Sdd } 265209567Sgavin } 266209567Sgavin 267209567Sgavin else { 26899708Sdd tmp[j] = trans; 26999708Sdd 2701590Srgrimes if (trans > 0) 2711590Srgrimes ++totaltrans; 2721590Srgrimes } 27387286Sdwmalone } 2741590Srgrimes 2751590Srgrimes /* It is assumed (in a rather subtle way) in the skeleton 276110609Stjr * that if we're using meta-equivalence classes, the def[] 277100806Sdd * entry for all templates is the jam template, i.e., 278100806Sdd * templates never default to other non-jam table entries 2791590Srgrimes * (e.g., another template) 2801590Srgrimes */ 2811590Srgrimes 2821590Srgrimes /* Leave room for the jam-state after the last real state. */ 28387286Sdwmalone mkentry (tmp, nummecs, lastdfa + i + 1, JAMSTATE, 2841590Srgrimes totaltrans); 28599708Sdd } 286110609Stjr} 287100806Sdd 288100806Sdd 28999708Sdd 29099708Sdd/* expand_nxt_chk - expand the next check arrays */ 29199708Sdd 2921590Srgrimesvoid 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 327int 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 */ 422void 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 454void 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 503void 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 619void 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 645void 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 683void 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 735void 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 762void 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 805void 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 835int 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} 854