2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.1 1994-09-26 10:16:58 adam
8 * First version of dfa module in alex. This version uses yacc to parse
9 * regular expressions. This should be hand-made instead.
23 #define TRAN_CHUNK 800
25 int init_DFA_states (DFA_states **dfasp, SetType st, int hash)
31 dfas = (DFA_states *) imalloc( sizeof(DFA_states) );
33 dfas->hasharray = (DFA_state **) imalloc( sizeof(DFA_state*) * hash );
34 assert( dfas->hasharray );
36 dfas->freelist = dfas->unmarked = dfas->marked = NULL;
37 dfas->statemem = NULL;
42 dfas->transmem = tm = (DFA_trans *) imalloc( sizeof(DFA_trans) );
45 tm->size = TRAN_CHUNK;
47 tm->tran_block = (DFA_tran *) imalloc( sizeof(DFA_tran) * tm->size );
48 assert( tm->tran_block );
50 dfas->sortarray = NULL;
51 for( i=0; i<dfas->hash; i++ )
52 dfas->hasharray[i] = NULL;
56 int rm_DFA_states (DFA_states **dfasp)
58 DFA_states *dfas = *dfasp;
63 ifree( dfas->hasharray );
64 ifree( dfas->sortarray );
66 for( tm=dfas->transmem; tm; tm=tm1 )
68 ifree( tm->tran_block );
72 for( sm=dfas->statemem; sm; sm=sm1 )
74 ifree( sm->state_block );
83 int add_DFA_state (DFA_states *dfas, Set *s, DFA_state **sp)
91 sip = dfas->hasharray + (hash_Set( dfas->st, *s ) % dfas->hash);
92 for( si = *sip; si; si=si->link )
93 if( eq_Set( dfas->st, si->set, *s ) )
96 *s = rm_Set( dfas->st, *s );
101 sb = (DFA_stateb *) imalloc( sizeof(*sb) );
102 sb->next = dfas->statemem;
104 sb->state_block = si = dfas->freelist =
105 (DFA_state *) imalloc( sizeof(DFA_state)*DFA_CHUNK);
106 for( i = 0; i<DFA_CHUNK-1; i++, si++ )
112 dfas->freelist = si->next;
114 si->next = dfas->unmarked;
120 si->no = (dfas->no)++;
128 void add_DFA_tran (DFA_states *dfas, DFA_state *s, int ch0, int ch1, int to)
134 if( tm->ptr == tm->size )
136 tm = (DFA_trans *) imalloc( sizeof(DFA_trans) );
138 tm->next = dfas->transmem;
140 tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
141 tm->tran_block = (DFA_tran *) imalloc( sizeof(DFA_tran) * tm->size );
142 assert( tm->tran_block );
144 memcpy( tm->tran_block, s->trans, s->tran_no*sizeof( DFA_tran ) );
145 tm->ptr = s->tran_no;
146 s->trans = tm->tran_block;
149 t = tm->tran_block + tm->ptr++;
155 DFA_state *get_DFA_state (DFA_states *dfas)
159 if( !(si = dfas->unmarked) )
161 dfas->unmarked = si->next;
162 si->next = dfas->marked;
164 si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
169 void sort_DFA_states (DFA_states *dfas)
173 dfas->sortarray = (DFA_state **) imalloc( sizeof(DFA_state *)*dfas->no );
174 for( s = dfas->marked; s; s=s->next )
175 dfas->sortarray[s->no] = s;