2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.2 1995-01-24 16:00:23 adam
8 * Added -ansi to CFLAGS.
9 * Some changes to the dfa module.
11 * Revision 1.1 1994/09/26 10:16:58 adam
12 * First version of dfa module in alex. This version uses yacc to parse
13 * regular expressions. This should be hand-made instead.
27 #define TRAN_CHUNK 800
29 int init_DFA_states (struct DFA_states **dfasp, SetType st, int hash)
31 struct DFA_states *dfas;
35 dfas = (struct DFA_states *) imalloc (sizeof(struct DFA_states));
37 dfas->hasharray = (struct DFA_state **)
38 imalloc (sizeof(struct DFA_state*) * hash);
39 assert (dfas->hasharray);
41 dfas->freelist = dfas->unmarked = dfas->marked = NULL;
42 dfas->statemem = NULL;
47 dfas->transmem = tm = (struct DFA_trans *)
48 imalloc (sizeof(struct DFA_trans));
51 tm->size = TRAN_CHUNK;
53 tm->tran_block = (struct DFA_tran *)
54 imalloc (sizeof(struct DFA_tran) * tm->size);
55 assert (tm->tran_block);
57 dfas->sortarray = NULL;
58 for (i=0; i<dfas->hash; i++)
59 dfas->hasharray[i] = NULL;
63 int rm_DFA_states (struct DFA_states **dfasp)
65 struct DFA_states *dfas = *dfasp;
67 struct DFA_trans *tm, *tm1;
70 ifree (dfas->hasharray);
71 ifree (dfas->sortarray);
73 for (tm=dfas->transmem; tm; tm=tm1)
75 ifree (tm->tran_block);
79 for (sm=dfas->statemem; sm; sm=sm1)
81 ifree (sm->state_block);
90 int add_DFA_state (struct DFA_states *dfas, Set *s, struct DFA_state **sp)
93 struct DFA_state *si, **sip;
98 sip = dfas->hasharray + (hash_Set (dfas->st, *s) % dfas->hash);
99 for (si = *sip; si; si=si->link)
100 if (eq_Set (dfas->st, si->set, *s))
103 *s = rm_Set (dfas->st, *s);
108 sb = (DFA_stateb *) imalloc (sizeof(*sb));
109 sb->next = dfas->statemem;
111 sb->state_block = si = dfas->freelist =
112 (struct DFA_state *) imalloc (sizeof(struct DFA_state)*DFA_CHUNK);
113 for (i = 0; i<DFA_CHUNK-1; i++, si++)
119 dfas->freelist = si->next;
121 si->next = dfas->unmarked;
127 si->no = (dfas->no)++;
135 void add_DFA_tran (struct DFA_states *dfas, struct DFA_state *s,
136 int ch0, int ch1, int to)
138 struct DFA_trans *tm;
142 if (tm->ptr == tm->size)
144 tm = (struct DFA_trans *) imalloc (sizeof(struct DFA_trans));
146 tm->next = dfas->transmem;
148 tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
149 tm->tran_block = (struct DFA_tran *)
150 imalloc (sizeof(struct DFA_tran) * tm->size);
151 assert (tm->tran_block);
153 memcpy (tm->tran_block, s->trans,
154 s->tran_no*sizeof (struct DFA_tran));
155 tm->ptr = s->tran_no;
156 s->trans = tm->tran_block;
159 t = tm->tran_block + tm->ptr++;
165 struct DFA_state *get_DFA_state (struct DFA_states *dfas)
167 struct DFA_state *si;
169 if (!(si = dfas->unmarked))
171 dfas->unmarked = si->next;
172 si->next = dfas->marked;
174 si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
179 void sort_DFA_states (struct DFA_states *dfas)
183 dfas->sortarray = (struct DFA_state **)
184 imalloc (sizeof(struct DFA_state *)*dfas->no);
185 for (s = dfas->marked; s; s=s->next)
186 dfas->sortarray[s->no] = s;