2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.3 1995-01-25 11:30:51 adam
8 * Simple error reporting when parsing regular expressions.
9 * Memory usage reduced.
11 * Revision 1.2 1995/01/24 16:00:23 adam
12 * Added -ansi to CFLAGS.
13 * Some changes to the dfa module.
15 * Revision 1.1 1994/09/26 10:16:58 adam
16 * First version of dfa module in alex. This version uses yacc to parse
17 * regular expressions. This should be hand-made instead.
31 #define TRAN_CHUNK 100
33 int init_DFA_states (struct DFA_states **dfasp, SetType st, int hash)
35 struct DFA_states *dfas;
39 dfas = (struct DFA_states *) imalloc (sizeof(struct DFA_states));
41 dfas->hasharray = (struct DFA_state **)
42 imalloc (sizeof(struct DFA_state*) * hash);
43 assert (dfas->hasharray);
45 dfas->freelist = dfas->unmarked = dfas->marked = NULL;
46 dfas->statemem = NULL;
51 dfas->transmem = tm = (struct DFA_trans *)
52 imalloc (sizeof(struct DFA_trans));
55 tm->size = TRAN_CHUNK;
57 tm->tran_block = (struct DFA_tran *)
58 imalloc (sizeof(struct DFA_tran) * tm->size);
59 assert (tm->tran_block);
61 dfas->sortarray = NULL;
62 for (i=0; i<dfas->hash; i++)
63 dfas->hasharray[i] = NULL;
67 int rm_DFA_states (struct DFA_states **dfasp)
69 struct DFA_states *dfas = *dfasp;
71 struct DFA_trans *tm, *tm1;
75 ifree (dfas->hasharray);
76 ifree (dfas->sortarray);
78 for (tm=dfas->transmem; tm; tm=tm1)
80 ifree (tm->tran_block);
84 for (sm=dfas->statemem; sm; sm=sm1)
86 ifree (sm->state_block);
95 int add_DFA_state (struct DFA_states *dfas, Set *s, struct DFA_state **sp)
98 struct DFA_state *si, **sip;
103 assert (dfas->hasharray);
104 sip = dfas->hasharray + (hash_Set (dfas->st, *s) % dfas->hash);
105 for (si = *sip; si; si=si->link)
106 if (eq_Set (dfas->st, si->set, *s))
109 *s = rm_Set (dfas->st, *s);
114 sb = (DFA_stateb *) imalloc (sizeof(*sb));
115 sb->next = dfas->statemem;
117 sb->state_block = si = dfas->freelist =
118 (struct DFA_state *) imalloc (sizeof(struct DFA_state)*DFA_CHUNK);
119 for (i = 0; i<DFA_CHUNK-1; i++, si++)
125 dfas->freelist = si->next;
127 si->next = dfas->unmarked;
133 si->no = (dfas->no)++;
141 void add_DFA_tran (struct DFA_states *dfas, struct DFA_state *s,
142 int ch0, int ch1, int to)
144 struct DFA_trans *tm;
148 if (tm->ptr == tm->size)
150 tm = (struct DFA_trans *) imalloc (sizeof(struct DFA_trans));
152 tm->next = dfas->transmem;
154 tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
155 tm->tran_block = (struct DFA_tran *)
156 imalloc (sizeof(struct DFA_tran) * tm->size);
157 assert (tm->tran_block);
159 memcpy (tm->tran_block, s->trans,
160 s->tran_no*sizeof (struct DFA_tran));
161 tm->ptr = s->tran_no;
162 s->trans = tm->tran_block;
165 t = tm->tran_block + tm->ptr++;
171 struct DFA_state *get_DFA_state (struct DFA_states *dfas)
173 struct DFA_state *si;
175 if (!(si = dfas->unmarked))
177 dfas->unmarked = si->next;
178 si->next = dfas->marked;
180 si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
185 void sort_DFA_states (struct DFA_states *dfas)
189 dfas->sortarray = (struct DFA_state **)
190 imalloc (sizeof(struct DFA_state *)*dfas->no);
191 for (s = dfas->marked; s; s=s->next)
192 dfas->sortarray[s->no] = s;
193 ifree (dfas->hasharray);
194 dfas->hasharray = NULL;