tblcmp.c (99112) | tblcmp.c (179549) |
---|---|
1/* tblcmp - table compression routines */ 2 3/*- 4 * Copyright (c) 1990 The Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Vern Paxson. --- 14 unchanged lines hidden (view full) --- 23 * specific prior written permission. 24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 27 */ 28 29/* $Header: /home/daffy/u0/vern/flex/RCS/tblcmp.c,v 2.11 94/11/05 17:08:28 vern Exp $ */ 30#include <sys/cdefs.h> | 1/* tblcmp - table compression routines */ 2 3/*- 4 * Copyright (c) 1990 The Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Vern Paxson. --- 14 unchanged lines hidden (view full) --- 23 * specific prior written permission. 24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 27 */ 28 29/* $Header: /home/daffy/u0/vern/flex/RCS/tblcmp.c,v 2.11 94/11/05 17:08:28 vern Exp $ */ 30#include <sys/cdefs.h> |
31__FBSDID("$FreeBSD: head/usr.bin/lex/tblcmp.c 99112 2002-06-30 05:25:07Z obrien $"); | 31__FBSDID("$FreeBSD: head/usr.bin/lex/tblcmp.c 179549 2008-06-04 19:50:34Z dwmalone $"); |
32 33#include "flexdef.h" 34 35 36/* declarations for functions that have forward references */ 37 | 32 33#include "flexdef.h" 34 35 36/* declarations for functions that have forward references */ 37 |
38void mkentry PROTO((register int*, int, int, int, int)); | 38void mkentry PROTO((int*, int, int, int, int)); |
39void mkprot PROTO((int[], int, int)); 40void mktemplate PROTO((int[], int, int)); 41void mv2front PROTO((int)); 42int tbldiff PROTO((int[], int, int[])); 43 44 45/* bldtbl - build table entries for dfa state 46 * --- 178 unchanged lines hidden (view full) --- 225 * classes', which are collections of transition character equivalence 226 * classes which always appear together in templates - really meta-equivalence 227 * classes. 228 */ 229 230void cmptmps() 231 { 232 int tmpstorage[CSIZE + 1]; | 39void mkprot PROTO((int[], int, int)); 40void mktemplate PROTO((int[], int, int)); 41void mv2front PROTO((int)); 42int tbldiff PROTO((int[], int, int[])); 43 44 45/* bldtbl - build table entries for dfa state 46 * --- 178 unchanged lines hidden (view full) --- 225 * classes', which are collections of transition character equivalence 226 * classes which always appear together in templates - really meta-equivalence 227 * classes. 228 */ 229 230void cmptmps() 231 { 232 int tmpstorage[CSIZE + 1]; |
233 register int *tmp = tmpstorage, i, j; | 233 int *tmp = tmpstorage, i, j; |
234 int totaltrans, trans; 235 236 peakpairs = numtemps * numecs + tblend; 237 238 if ( usemecs ) 239 { 240 /* Create equivalence classes based on data gathered on 241 * template transitions. --- 55 unchanged lines hidden (view full) --- 297 } 298 299 300 301/* expand_nxt_chk - expand the next check arrays */ 302 303void expand_nxt_chk() 304 { | 234 int totaltrans, trans; 235 236 peakpairs = numtemps * numecs + tblend; 237 238 if ( usemecs ) 239 { 240 /* Create equivalence classes based on data gathered on 241 * template transitions. --- 55 unchanged lines hidden (view full) --- 297 } 298 299 300 301/* expand_nxt_chk - expand the next check arrays */ 302 303void expand_nxt_chk() 304 { |
305 register int old_max = current_max_xpairs; | 305 int old_max = current_max_xpairs; |
306 307 current_max_xpairs += MAX_XPAIRS_INCREMENT; 308 309 ++num_reallocs; 310 311 nxt = reallocate_integer_array( nxt, current_max_xpairs ); 312 chk = reallocate_integer_array( chk, current_max_xpairs ); 313 --- 22 unchanged lines hidden (view full) --- 336 */ 337 338int find_table_space( state, numtrans ) 339int *state, numtrans; 340 { 341 /* Firstfree is the position of the first possible occurrence of two 342 * consecutive unused records in the chk and nxt arrays. 343 */ | 306 307 current_max_xpairs += MAX_XPAIRS_INCREMENT; 308 309 ++num_reallocs; 310 311 nxt = reallocate_integer_array( nxt, current_max_xpairs ); 312 chk = reallocate_integer_array( chk, current_max_xpairs ); 313 --- 22 unchanged lines hidden (view full) --- 336 */ 337 338int find_table_space( state, numtrans ) 339int *state, numtrans; 340 { 341 /* Firstfree is the position of the first possible occurrence of two 342 * consecutive unused records in the chk and nxt arrays. 343 */ |
344 register int i; 345 register int *state_ptr, *chk_ptr; 346 register int *ptr_to_last_entry_in_state; | 344 int i; 345 int *state_ptr, *chk_ptr; 346 int *ptr_to_last_entry_in_state; |
347 348 /* If there are too many out-transitions, put the state at the end of 349 * nxt and chk. 350 */ 351 if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT ) 352 { 353 /* If table is empty, return the first available spot in 354 * chk/nxt, which should be 1. --- 76 unchanged lines hidden (view full) --- 431 432/* inittbl - initialize transition tables 433 * 434 * Initializes "firstfree" to be one beyond the end of the table. Initializes 435 * all "chk" entries to be zero. 436 */ 437void inittbl() 438 { | 347 348 /* If there are too many out-transitions, put the state at the end of 349 * nxt and chk. 350 */ 351 if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT ) 352 { 353 /* If table is empty, return the first available spot in 354 * chk/nxt, which should be 1. --- 76 unchanged lines hidden (view full) --- 431 432/* inittbl - initialize transition tables 433 * 434 * Initializes "firstfree" to be one beyond the end of the table. Initializes 435 * all "chk" entries to be zero. 436 */ 437void inittbl() 438 { |
439 register int i; | 439 int i; |
440 441 zero_out( (char *) chk, (size_t) (current_max_xpairs * sizeof( int )) ); 442 443 tblend = 0; 444 firstfree = tblend + 1; 445 numtemps = 0; 446 447 if ( usemecs ) --- 64 unchanged lines hidden (view full) --- 512 * marking transitions to "SAME_TRANS" are treated as though they will be 513 * taken care of by whereever "deflink" points. "totaltrans" is the total 514 * number of transitions out of the state. If it is below a certain threshold, 515 * the tables are searched for an interior spot that will accommodate the 516 * state array. 517 */ 518 519void mkentry( state, numchars, statenum, deflink, totaltrans ) | 440 441 zero_out( (char *) chk, (size_t) (current_max_xpairs * sizeof( int )) ); 442 443 tblend = 0; 444 firstfree = tblend + 1; 445 numtemps = 0; 446 447 if ( usemecs ) --- 64 unchanged lines hidden (view full) --- 512 * marking transitions to "SAME_TRANS" are treated as though they will be 513 * taken care of by whereever "deflink" points. "totaltrans" is the total 514 * number of transitions out of the state. If it is below a certain threshold, 515 * the tables are searched for an interior spot that will accommodate the 516 * state array. 517 */ 518 519void mkentry( state, numchars, statenum, deflink, totaltrans ) |
520register int *state; | 520int *state; |
521int numchars, statenum, deflink, totaltrans; 522 { | 521int numchars, statenum, deflink, totaltrans; 522 { |
523 register int minec, maxec, i, baseaddr; | 523 int minec, maxec, i, baseaddr; |
524 int tblbase, tbllast; 525 526 if ( totaltrans == 0 ) 527 { /* there are no out-transitions */ 528 if ( deflink == JAMSTATE ) 529 base[statenum] = JAMSTATE; 530 else 531 base[statenum] = 0; --- 257 unchanged lines hidden (view full) --- 789 * State is the statenum'th state. It is indexed by equivalence class and 790 * gives the number of the state to enter for a given equivalence class. 791 * Transnum is the number of out-transitions for the state. 792 */ 793 794void place_state( state, statenum, transnum ) 795int *state, statenum, transnum; 796 { | 524 int tblbase, tbllast; 525 526 if ( totaltrans == 0 ) 527 { /* there are no out-transitions */ 528 if ( deflink == JAMSTATE ) 529 base[statenum] = JAMSTATE; 530 else 531 base[statenum] = 0; --- 257 unchanged lines hidden (view full) --- 789 * State is the statenum'th state. It is indexed by equivalence class and 790 * gives the number of the state to enter for a given equivalence class. 791 * Transnum is the number of out-transitions for the state. 792 */ 793 794void place_state( state, statenum, transnum ) 795int *state, statenum, transnum; 796 { |
797 register int i; 798 register int *state_ptr; | 797 int i; 798 int *state_ptr; |
799 int position = find_table_space( state, transnum ); 800 801 /* "base" is the table of start positions. */ 802 base[statenum] = position; 803 804 /* Put in action number marker; this non-zero number makes sure that 805 * find_table_space() knows that this position in chk/nxt is taken 806 * and should not be used for another accepting number in another --- 57 unchanged lines hidden (view full) --- 864 * as transitions to "SAME_TRANS" in "ext". The total number of differences 865 * between "state" and "pr" is returned as function value. Note that this 866 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 867 */ 868 869int tbldiff( state, pr, ext ) 870int state[], pr, ext[]; 871 { | 799 int position = find_table_space( state, transnum ); 800 801 /* "base" is the table of start positions. */ 802 base[statenum] = position; 803 804 /* Put in action number marker; this non-zero number makes sure that 805 * find_table_space() knows that this position in chk/nxt is taken 806 * and should not be used for another accepting number in another --- 57 unchanged lines hidden (view full) --- 864 * as transitions to "SAME_TRANS" in "ext". The total number of differences 865 * between "state" and "pr" is returned as function value. Note that this 866 * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". 867 */ 868 869int tbldiff( state, pr, ext ) 870int state[], pr, ext[]; 871 { |
872 register int i, *sp = state, *ep = ext, *protp; 873 register int numdiff = 0; | 872 int i, *sp = state, *ep = ext, *protp; 873 int numdiff = 0; |
874 875 protp = &protsave[numecs * (pr - 1)]; 876 877 for ( i = numecs; i > 0; --i ) 878 { 879 if ( *++protp == *++sp ) 880 *++ep = SAME_TRANS; 881 else 882 { 883 *++ep = *sp; 884 ++numdiff; 885 } 886 } 887 888 return numdiff; 889 } | 874 875 protp = &protsave[numecs * (pr - 1)]; 876 877 for ( i = numecs; i > 0; --i ) 878 { 879 if ( *++protp == *++sp ) 880 *++ep = SAME_TRANS; 881 else 882 { 883 *++ep = *sp; 884 ++numdiff; 885 } 886 } 887 888 return numdiff; 889 } |