tblcmp.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932
  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. * Redistribution and use in source and binary forms are permitted provided
  14. * that: (1) source distributions retain this entire copyright notice and
  15. * comment, and (2) distributions including binaries display the following
  16. * acknowledgement: ``This product includes software developed by the
  17. * University of California, Berkeley and its contributors'' in the
  18. * documentation or other materials provided with the distribution and in
  19. * all advertising materials mentioning features or use of this software.
  20. * Neither the name of the University nor the names of its contributors may
  21. * be used to endorse or promote products derived from this software without
  22. * specific prior written permission.
  23. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  24. * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  25. * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  26. */
  27. #ifndef lint
  28. static char rcsid[] =
  29. "@(#) $Id$ (LBL)";
  30. #endif
  31. #include "flexdef.h"
  32. /* declarations for functions that have forward references */
  33. void mkentry PROTO((register int*, int, int, int, int));
  34. void mkprot PROTO((int[], int, int));
  35. void mktemplate PROTO((int[], int, int));
  36. void mv2front PROTO((int));
  37. int tbldiff PROTO((int[], int, int[]));
  38. /* bldtbl - build table entries for dfa state
  39. *
  40. * synopsis
  41. * int state[numecs], statenum, totaltrans, comstate, comfreq;
  42. * bldtbl( state, statenum, totaltrans, comstate, comfreq );
  43. *
  44. * State is the statenum'th dfa state. It is indexed by equivalence class and
  45. * gives the number of the state to enter for a given equivalence class.
  46. * totaltrans is the total number of transitions out of the state. Comstate
  47. * is that state which is the destination of the most transitions out of State.
  48. * Comfreq is how many transitions there are out of State to Comstate.
  49. *
  50. * A note on terminology:
  51. * "protos" are transition tables which have a high probability of
  52. * either being redundant (a state processed later will have an identical
  53. * transition table) or nearly redundant (a state processed later will have
  54. * many of the same out-transitions). A "most recently used" queue of
  55. * protos is kept around with the hope that most states will find a proto
  56. * which is similar enough to be usable, and therefore compacting the
  57. * output tables.
  58. * "templates" are a special type of proto. If a transition table is
  59. * homogeneous or nearly homogeneous (all transitions go to the same
  60. * destination) then the odds are good that future states will also go
  61. * to the same destination state on basically the same character set.
  62. * These homogeneous states are so common when dealing with large rule
  63. * sets that they merit special attention. If the transition table were
  64. * simply made into a proto, then (typically) each subsequent, similar
  65. * state will differ from the proto for two out-transitions. One of these
  66. * out-transitions will be that character on which the proto does not go
  67. * to the common destination, and one will be that character on which the
  68. * state does not go to the common destination. Templates, on the other
  69. * hand, go to the common state on EVERY transition character, and therefore
  70. * cost only one difference.
  71. */
  72. void bldtbl( state, statenum, totaltrans, comstate, comfreq )
  73. int state[], statenum, totaltrans, comstate, comfreq;
  74. {
  75. int extptr, extrct[2][CSIZE + 1];
  76. int mindiff, minprot, i, d;
  77. int checkcom;
  78. /* If extptr is 0 then the first array of extrct holds the result of the
  79. * "best difference" to date, which is those transitions which occur in
  80. * "state" but not in the proto which, to date, has the fewest differences
  81. * between itself and "state". If extptr is 1 then the second array of
  82. * extrct hold the best difference. The two arrays are toggled
  83. * between so that the best difference to date can be kept around and
  84. * also a difference just created by checking against a candidate "best"
  85. * proto.
  86. */
  87. extptr = 0;
  88. /* if the state has too few out-transitions, don't bother trying to
  89. * compact its tables
  90. */
  91. if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  92. mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  93. else
  94. {
  95. /* checkcom is true if we should only check "state" against
  96. * protos which have the same "comstate" value
  97. */
  98. checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  99. minprot = firstprot;
  100. mindiff = totaltrans;
  101. if ( checkcom )
  102. {
  103. /* find first proto which has the same "comstate" */
  104. for ( i = firstprot; i != NIL; i = protnext[i] )
  105. if ( protcomst[i] == comstate )
  106. {
  107. minprot = i;
  108. mindiff = tbldiff( state, minprot, extrct[extptr] );
  109. break;
  110. }
  111. }
  112. else
  113. {
  114. /* since we've decided that the most common destination out
  115. * of "state" does not occur with a high enough frequency,
  116. * we set the "comstate" to zero, assuring that if this state
  117. * is entered into the proto list, it will not be considered
  118. * a template.
  119. */
  120. comstate = 0;
  121. if ( firstprot != NIL )
  122. {
  123. minprot = firstprot;
  124. mindiff = tbldiff( state, minprot, extrct[extptr] );
  125. }
  126. }
  127. /* we now have the first interesting proto in "minprot". If
  128. * it matches within the tolerances set for the first proto,
  129. * we don't want to bother scanning the rest of the proto list
  130. * to see if we have any other reasonable matches.
  131. */
  132. if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  133. { /* not a good enough match. Scan the rest of the protos */
  134. for ( i = minprot; i != NIL; i = protnext[i] )
  135. {
  136. d = tbldiff( state, i, extrct[1 - extptr] );
  137. if ( d < mindiff )
  138. {
  139. extptr = 1 - extptr;
  140. mindiff = d;
  141. minprot = i;
  142. }
  143. }
  144. }
  145. /* check if the proto we've decided on as our best bet is close
  146. * enough to the state we want to match to be usable
  147. */
  148. if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  149. {
  150. /* no good. If the state is homogeneous enough, we make a
  151. * template out of it. Otherwise, we make a proto.
  152. */
  153. if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  154. mktemplate( state, statenum, comstate );
  155. else
  156. {
  157. mkprot( state, statenum, comstate );
  158. mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  159. }
  160. }
  161. else
  162. { /* use the proto */
  163. mkentry( extrct[extptr], numecs, statenum,
  164. prottbl[minprot], mindiff );
  165. /* if this state was sufficiently different from the proto
  166. * we built it from, make it, too, a proto
  167. */
  168. if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  169. mkprot( state, statenum, comstate );
  170. /* since mkprot added a new proto to the proto queue, it's possible
  171. * that "minprot" is no longer on the proto queue (if it happened
  172. * to have been the last entry, it would have been bumped off).
  173. * If it's not there, then the new proto took its physical place
  174. * (though logically the new proto is at the beginning of the
  175. * queue), so in that case the following call will do nothing.
  176. */
  177. mv2front( minprot );
  178. }
  179. }
  180. }
  181. /* cmptmps - compress template table entries
  182. *
  183. * synopsis
  184. * cmptmps();
  185. *
  186. * template tables are compressed by using the 'template equivalence
  187. * classes', which are collections of transition character equivalence
  188. * classes which always appear together in templates - really meta-equivalence
  189. * classes. until this point, the tables for templates have been stored
  190. * up at the top end of the nxt array; they will now be compressed and have
  191. * table entries made for them.
  192. */
  193. void cmptmps()
  194. {
  195. int tmpstorage[CSIZE + 1];
  196. register int *tmp = tmpstorage, i, j;
  197. int totaltrans, trans;
  198. peakpairs = numtemps * numecs + tblend;
  199. if ( usemecs )
  200. {
  201. /* create equivalence classes base on data gathered on template
  202. * transitions
  203. */
  204. nummecs = cre8ecs( tecfwd, tecbck, numecs );
  205. }
  206. else
  207. nummecs = numecs;
  208. if ( lastdfa + numtemps + 1 >= current_max_dfas )
  209. increase_max_dfas();
  210. /* loop through each template */
  211. for ( i = 1; i <= numtemps; ++i )
  212. {
  213. totaltrans = 0; /* number of non-jam transitions out of this template */
  214. for ( j = 1; j <= numecs; ++j )
  215. {
  216. trans = tnxt[numecs * i + j];
  217. if ( usemecs )
  218. {
  219. /* the absolute value of tecbck is the meta-equivalence class
  220. * of a given equivalence class, as set up by cre8ecs
  221. */
  222. if ( tecbck[j] > 0 )
  223. {
  224. tmp[tecbck[j]] = trans;
  225. if ( trans > 0 )
  226. ++totaltrans;
  227. }
  228. }
  229. else
  230. {
  231. tmp[j] = trans;
  232. if ( trans > 0 )
  233. ++totaltrans;
  234. }
  235. }
  236. /* it is assumed (in a rather subtle way) in the skeleton that
  237. * if we're using meta-equivalence classes, the def[] entry for
  238. * all templates is the jam template, i.e., templates never default
  239. * to other non-jam table entries (e.g., another template)
  240. */
  241. /* leave room for the jam-state after the last real state */
  242. mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  243. }
  244. }
  245. #ifdef ACK_MOD
  246. static void bzero(p, cnt)
  247. register char *p;
  248. register int cnt;
  249. {
  250. while (cnt-- > 0) *p++ = '\0';
  251. }
  252. #endif /* ACK_MOD */
  253. /* expand_nxt_chk - expand the next check arrays */
  254. void expand_nxt_chk()
  255. {
  256. register int old_max = current_max_xpairs;
  257. current_max_xpairs += MAX_XPAIRS_INCREMENT;
  258. ++num_reallocs;
  259. nxt = reallocate_integer_array( nxt, current_max_xpairs );
  260. chk = reallocate_integer_array( chk, current_max_xpairs );
  261. bzero( (char *) (chk + old_max),
  262. MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  263. }
  264. /* find_table_space - finds a space in the table for a state to be placed
  265. *
  266. * synopsis
  267. * int *state, numtrans, block_start;
  268. * int find_table_space();
  269. *
  270. * block_start = find_table_space( state, numtrans );
  271. *
  272. * State is the state to be added to the full speed transition table.
  273. * Numtrans is the number of out-transitions for the state.
  274. *
  275. * find_table_space() returns the position of the start of the first block (in
  276. * chk) able to accommodate the state
  277. *
  278. * In determining if a state will or will not fit, find_table_space() must take
  279. * into account the fact that an end-of-buffer state will be added at [0],
  280. * and an action number will be added in [-1].
  281. */
  282. int find_table_space( state, numtrans )
  283. int *state, numtrans;
  284. {
  285. /* firstfree is the position of the first possible occurrence of two
  286. * consecutive unused records in the chk and nxt arrays
  287. */
  288. register int i;
  289. register int *state_ptr, *chk_ptr;
  290. register int *ptr_to_last_entry_in_state;
  291. /* if there are too many out-transitions, put the state at the end of
  292. * nxt and chk
  293. */
  294. if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
  295. {
  296. /* if table is empty, return the first available spot in chk/nxt,
  297. * which should be 1
  298. */
  299. if ( tblend < 2 )
  300. return ( 1 );
  301. i = tblend - numecs; /* start searching for table space near the
  302. * end of chk/nxt arrays
  303. */
  304. }
  305. else
  306. i = firstfree; /* start searching for table space from the
  307. * beginning (skipping only the elements
  308. * which will definitely not hold the new
  309. * state)
  310. */
  311. while ( 1 ) /* loops until a space is found */
  312. {
  313. if ( i + numecs > current_max_xpairs )
  314. expand_nxt_chk();
  315. /* loops until space for end-of-buffer and action number are found */
  316. while ( 1 )
  317. {
  318. if ( chk[i - 1] == 0 ) /* check for action number space */
  319. {
  320. if ( chk[i] == 0 ) /* check for end-of-buffer space */
  321. break;
  322. else
  323. i += 2; /* since i != 0, there is no use checking to
  324. * see if (++i) - 1 == 0, because that's the
  325. * same as i == 0, so we skip a space
  326. */
  327. }
  328. else
  329. ++i;
  330. if ( i + numecs > current_max_xpairs )
  331. expand_nxt_chk();
  332. }
  333. /* if we started search from the beginning, store the new firstfree for
  334. * the next call of find_table_space()
  335. */
  336. if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
  337. firstfree = i + 1;
  338. /* check to see if all elements in chk (and therefore nxt) that are
  339. * needed for the new state have not yet been taken
  340. */
  341. state_ptr = &state[1];
  342. ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  343. for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  344. ++chk_ptr )
  345. if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  346. break;
  347. if ( chk_ptr == ptr_to_last_entry_in_state )
  348. return ( i );
  349. else
  350. ++i;
  351. }
  352. }
  353. /* inittbl - initialize transition tables
  354. *
  355. * synopsis
  356. * inittbl();
  357. *
  358. * Initializes "firstfree" to be one beyond the end of the table. Initializes
  359. * all "chk" entries to be zero. Note that templates are built in their
  360. * own tbase/tdef tables. They are shifted down to be contiguous
  361. * with the non-template entries during table generation.
  362. */
  363. void inittbl()
  364. {
  365. register int i;
  366. bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  367. tblend = 0;
  368. firstfree = tblend + 1;
  369. numtemps = 0;
  370. if ( usemecs )
  371. {
  372. /* set up doubly-linked meta-equivalence classes
  373. * these are sets of equivalence classes which all have identical
  374. * transitions out of TEMPLATES
  375. */
  376. tecbck[1] = NIL;
  377. for ( i = 2; i <= numecs; ++i )
  378. {
  379. tecbck[i] = i - 1;
  380. tecfwd[i - 1] = i;
  381. }
  382. tecfwd[numecs] = NIL;
  383. }
  384. }
  385. /* mkdeftbl - make the default, "jam" table entries
  386. *
  387. * synopsis
  388. * mkdeftbl();
  389. */
  390. void mkdeftbl()
  391. {
  392. int i;
  393. jamstate = lastdfa + 1;
  394. ++tblend; /* room for transition on end-of-buffer character */
  395. if ( tblend + numecs > current_max_xpairs )
  396. expand_nxt_chk();
  397. /* add in default end-of-buffer transition */
  398. nxt[tblend] = end_of_buffer_state;
  399. chk[tblend] = jamstate;
  400. for ( i = 1; i <= numecs; ++i )
  401. {
  402. nxt[tblend + i] = 0;
  403. chk[tblend + i] = jamstate;
  404. }
  405. jambase = tblend;
  406. base[jamstate] = jambase;
  407. def[jamstate] = 0;
  408. tblend += numecs;
  409. ++numtemps;
  410. }
  411. /* mkentry - create base/def and nxt/chk entries for transition array
  412. *
  413. * synopsis
  414. * int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  415. * mkentry( state, numchars, statenum, deflink, totaltrans );
  416. *
  417. * "state" is a transition array "numchars" characters in size, "statenum"
  418. * is the offset to be used into the base/def tables, and "deflink" is the
  419. * entry to put in the "def" table entry. If "deflink" is equal to
  420. * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  421. * (i.e., jam entries) into the table. It is assumed that by linking to
  422. * "JAMSTATE" they will be taken care of. In any case, entries in "state"
  423. * marking transitions to "SAME_TRANS" are treated as though they will be
  424. * taken care of by whereever "deflink" points. "totaltrans" is the total
  425. * number of transitions out of the state. If it is below a certain threshold,
  426. * the tables are searched for an interior spot that will accommodate the
  427. * state array.
  428. */
  429. void mkentry( state, numchars, statenum, deflink, totaltrans )
  430. register int *state;
  431. int numchars, statenum, deflink, totaltrans;
  432. {
  433. register int minec, maxec, i, baseaddr;
  434. int tblbase, tbllast;
  435. if ( totaltrans == 0 )
  436. { /* there are no out-transitions */
  437. if ( deflink == JAMSTATE )
  438. base[statenum] = JAMSTATE;
  439. else
  440. base[statenum] = 0;
  441. def[statenum] = deflink;
  442. return;
  443. }
  444. for ( minec = 1; minec <= numchars; ++minec )
  445. {
  446. if ( state[minec] != SAME_TRANS )
  447. if ( state[minec] != 0 || deflink != JAMSTATE )
  448. break;
  449. }
  450. if ( totaltrans == 1 )
  451. {
  452. /* there's only one out-transition. Save it for later to fill
  453. * in holes in the tables.
  454. */
  455. stack1( statenum, minec, state[minec], deflink );
  456. return;
  457. }
  458. for ( maxec = numchars; maxec > 0; --maxec )
  459. {
  460. if ( state[maxec] != SAME_TRANS )
  461. if ( state[maxec] != 0 || deflink != JAMSTATE )
  462. break;
  463. }
  464. /* Whether we try to fit the state table in the middle of the table
  465. * entries we have already generated, or if we just take the state
  466. * table at the end of the nxt/chk tables, we must make sure that we
  467. * have a valid base address (i.e., non-negative). Note that not only are
  468. * negative base addresses dangerous at run-time (because indexing the
  469. * next array with one and a low-valued character might generate an
  470. * array-out-of-bounds error message), but at compile-time negative
  471. * base addresses denote TEMPLATES.
  472. */
  473. /* find the first transition of state that we need to worry about. */
  474. if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  475. { /* attempt to squeeze it into the middle of the tabls */
  476. baseaddr = firstfree;
  477. while ( baseaddr < minec )
  478. {
  479. /* using baseaddr would result in a negative base address below
  480. * find the next free slot
  481. */
  482. for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  483. ;
  484. }
  485. if ( baseaddr + maxec - minec >= current_max_xpairs )
  486. expand_nxt_chk();
  487. for ( i = minec; i <= maxec; ++i )
  488. if ( state[i] != SAME_TRANS )
  489. if ( state[i] != 0 || deflink != JAMSTATE )
  490. if ( chk[baseaddr + i - minec] != 0 )
  491. { /* baseaddr unsuitable - find another */
  492. for ( ++baseaddr;
  493. baseaddr < current_max_xpairs &&
  494. chk[baseaddr] != 0;
  495. ++baseaddr )
  496. ;
  497. if ( baseaddr + maxec - minec >= current_max_xpairs )
  498. expand_nxt_chk();
  499. /* reset the loop counter so we'll start all
  500. * over again next time it's incremented
  501. */
  502. i = minec - 1;
  503. }
  504. }
  505. else
  506. {
  507. /* ensure that the base address we eventually generate is
  508. * non-negative
  509. */
  510. baseaddr = max( tblend + 1, minec );
  511. }
  512. tblbase = baseaddr - minec;
  513. tbllast = tblbase + maxec;
  514. if ( tbllast >= current_max_xpairs )
  515. expand_nxt_chk();
  516. base[statenum] = tblbase;
  517. def[statenum] = deflink;
  518. for ( i = minec; i <= maxec; ++i )
  519. if ( state[i] != SAME_TRANS )
  520. if ( state[i] != 0 || deflink != JAMSTATE )
  521. {
  522. nxt[tblbase + i] = state[i];
  523. chk[tblbase + i] = statenum;
  524. }
  525. if ( baseaddr == firstfree )
  526. /* find next free slot in tables */
  527. for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  528. ;
  529. tblend = max( tblend, tbllast );
  530. }
  531. /* mk1tbl - create table entries for a state (or state fragment) which
  532. * has only one out-transition
  533. *
  534. * synopsis
  535. * int state, sym, onenxt, onedef;
  536. * mk1tbl( state, sym, onenxt, onedef );
  537. */
  538. void mk1tbl( state, sym, onenxt, onedef )
  539. int state, sym, onenxt, onedef;
  540. {
  541. if ( firstfree < sym )
  542. firstfree = sym;
  543. while ( chk[firstfree] != 0 )
  544. if ( ++firstfree >= current_max_xpairs )
  545. expand_nxt_chk();
  546. base[state] = firstfree - sym;
  547. def[state] = onedef;
  548. chk[firstfree] = state;
  549. nxt[firstfree] = onenxt;
  550. if ( firstfree > tblend )
  551. {
  552. tblend = firstfree++;
  553. if ( firstfree >= current_max_xpairs )
  554. expand_nxt_chk();
  555. }
  556. }
  557. /* mkprot - create new proto entry
  558. *
  559. * synopsis
  560. * int state[], statenum, comstate;
  561. * mkprot( state, statenum, comstate );
  562. */
  563. void mkprot( state, statenum, comstate )
  564. int state[], statenum, comstate;
  565. {
  566. int i, slot, tblbase;
  567. if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  568. {
  569. /* gotta make room for the new proto by dropping last entry in
  570. * the queue
  571. */
  572. slot = lastprot;
  573. lastprot = protprev[lastprot];
  574. protnext[lastprot] = NIL;
  575. }
  576. else
  577. slot = numprots;
  578. protnext[slot] = firstprot;
  579. if ( firstprot != NIL )
  580. protprev[firstprot] = slot;
  581. firstprot = slot;
  582. prottbl[slot] = statenum;
  583. protcomst[slot] = comstate;
  584. /* copy state into save area so it can be compared with rapidly */
  585. tblbase = numecs * (slot - 1);
  586. for ( i = 1; i <= numecs; ++i )
  587. protsave[tblbase + i] = state[i];
  588. }
  589. /* mktemplate - create a template entry based on a state, and connect the state
  590. * to it
  591. *
  592. * synopsis
  593. * int state[], statenum, comstate, totaltrans;
  594. * mktemplate( state, statenum, comstate, totaltrans );
  595. */
  596. void mktemplate( state, statenum, comstate )
  597. int state[], statenum, comstate;
  598. {
  599. int i, numdiff, tmpbase, tmp[CSIZE + 1];
  600. Char transset[CSIZE + 1];
  601. int tsptr;
  602. ++numtemps;
  603. tsptr = 0;
  604. /* calculate where we will temporarily store the transition table
  605. * of the template in the tnxt[] array. The final transition table
  606. * gets created by cmptmps()
  607. */
  608. tmpbase = numtemps * numecs;
  609. if ( tmpbase + numecs >= current_max_template_xpairs )
  610. {
  611. current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  612. ++num_reallocs;
  613. tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  614. }
  615. for ( i = 1; i <= numecs; ++i )
  616. if ( state[i] == 0 )
  617. tnxt[tmpbase + i] = 0;
  618. else
  619. {
  620. transset[tsptr++] = i;
  621. tnxt[tmpbase + i] = comstate;
  622. }
  623. if ( usemecs )
  624. mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
  625. mkprot( tnxt + tmpbase, -numtemps, comstate );
  626. /* we rely on the fact that mkprot adds things to the beginning
  627. * of the proto queue
  628. */
  629. numdiff = tbldiff( state, firstprot, tmp );
  630. mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  631. }
  632. /* mv2front - move proto queue element to front of queue
  633. *
  634. * synopsis
  635. * int qelm;
  636. * mv2front( qelm );
  637. */
  638. void mv2front( qelm )
  639. int qelm;
  640. {
  641. if ( firstprot != qelm )
  642. {
  643. if ( qelm == lastprot )
  644. lastprot = protprev[lastprot];
  645. protnext[protprev[qelm]] = protnext[qelm];
  646. if ( protnext[qelm] != NIL )
  647. protprev[protnext[qelm]] = protprev[qelm];
  648. protprev[qelm] = NIL;
  649. protnext[qelm] = firstprot;
  650. protprev[firstprot] = qelm;
  651. firstprot = qelm;
  652. }
  653. }
  654. /* place_state - place a state into full speed transition table
  655. *
  656. * synopsis
  657. * int *state, statenum, transnum;
  658. * place_state( state, statenum, transnum );
  659. *
  660. * State is the statenum'th state. It is indexed by equivalence class and
  661. * gives the number of the state to enter for a given equivalence class.
  662. * Transnum is the number of out-transitions for the state.
  663. */
  664. void place_state( state, statenum, transnum )
  665. int *state, statenum, transnum;
  666. {
  667. register int i;
  668. register int *state_ptr;
  669. int position = find_table_space( state, transnum );
  670. /* base is the table of start positions */
  671. base[statenum] = position;
  672. /* put in action number marker; this non-zero number makes sure that
  673. * find_table_space() knows that this position in chk/nxt is taken
  674. * and should not be used for another accepting number in another state
  675. */
  676. chk[position - 1] = 1;
  677. /* put in end-of-buffer marker; this is for the same purposes as above */
  678. chk[position] = 1;
  679. /* place the state into chk and nxt */
  680. state_ptr = &state[1];
  681. for ( i = 1; i <= numecs; ++i, ++state_ptr )
  682. if ( *state_ptr != 0 )
  683. {
  684. chk[position + i] = i;
  685. nxt[position + i] = *state_ptr;
  686. }
  687. if ( position + numecs > tblend )
  688. tblend = position + numecs;
  689. }
  690. /* stack1 - save states with only one out-transition to be processed later
  691. *
  692. * synopsis
  693. * int statenum, sym, nextstate, deflink;
  694. * stack1( statenum, sym, nextstate, deflink );
  695. *
  696. * if there's room for another state one the "one-transition" stack, the
  697. * state is pushed onto it, to be processed later by mk1tbl. If there's
  698. * no room, we process the sucker right now.
  699. */
  700. void stack1( statenum, sym, nextstate, deflink )
  701. int statenum, sym, nextstate, deflink;
  702. {
  703. if ( onesp >= ONE_STACK_SIZE - 1 )
  704. mk1tbl( statenum, sym, nextstate, deflink );
  705. else
  706. {
  707. ++onesp;
  708. onestate[onesp] = statenum;
  709. onesym[onesp] = sym;
  710. onenext[onesp] = nextstate;
  711. onedef[onesp] = deflink;
  712. }
  713. }
  714. /* tbldiff - compute differences between two state tables
  715. *
  716. * synopsis
  717. * int state[], pr, ext[];
  718. * int tbldiff, numdifferences;
  719. * numdifferences = tbldiff( state, pr, ext )
  720. *
  721. * "state" is the state array which is to be extracted from the pr'th
  722. * proto. "pr" is both the number of the proto we are extracting from
  723. * and an index into the save area where we can find the proto's complete
  724. * state table. Each entry in "state" which differs from the corresponding
  725. * entry of "pr" will appear in "ext".
  726. * Entries which are the same in both "state" and "pr" will be marked
  727. * as transitions to "SAME_TRANS" in "ext". The total number of differences
  728. * between "state" and "pr" is returned as function value. Note that this
  729. * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  730. */
  731. int tbldiff( state, pr, ext )
  732. int state[], pr, ext[];
  733. {
  734. register int i, *sp = state, *ep = ext, *protp;
  735. register int numdiff = 0;
  736. protp = &protsave[numecs * (pr - 1)];
  737. for ( i = numecs; i > 0; --i )
  738. {
  739. if ( *++protp == *++sp )
  740. *++ep = SAME_TRANS;
  741. else
  742. {
  743. *++ep = *sp;
  744. ++numdiff;
  745. }
  746. }
  747. return ( numdiff );
  748. }