2 * Copyright (C) 1994-1999, Index Data
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.6 1999-02-02 14:50:14 adam
8 * Updated WIN32 code specific sections. Changed header.
10 * Revision 1.5 1996/10/29 13:57:31 adam
11 * Include of zebrautl.h instead of alexutil.h.
13 * Revision 1.4 1995/09/04 12:33:28 adam
14 * Various cleanup. YAZ util used instead.
16 * Revision 1.3 1995/01/25 11:30:51 adam
17 * Simple error reporting when parsing regular expressions.
18 * Memory usage reduced.
20 * Revision 1.2 1995/01/24 16:00:23 adam
21 * Added -ansi to CFLAGS.
22 * Some changes to the dfa module.
24 * Revision 1.1 1994/09/26 10:16:58 adam
25 * First version of dfa module in alex. This version uses yacc to parse
26 * regular expressions. This should be hand-made instead.
39 #define TRAN_CHUNK 100
41 int init_DFA_states (struct DFA_states **dfasp, SetType st, int hash)
43 struct DFA_states *dfas;
47 dfas = (struct DFA_states *) imalloc (sizeof(struct DFA_states));
49 dfas->hasharray = (struct DFA_state **)
50 imalloc (sizeof(struct DFA_state*) * hash);
51 assert (dfas->hasharray);
53 dfas->freelist = dfas->unmarked = dfas->marked = NULL;
54 dfas->statemem = NULL;
59 dfas->transmem = tm = (struct DFA_trans *)
60 imalloc (sizeof(struct DFA_trans));
63 tm->size = TRAN_CHUNK;
65 tm->tran_block = (struct DFA_tran *)
66 imalloc (sizeof(struct DFA_tran) * tm->size);
67 assert (tm->tran_block);
69 dfas->sortarray = NULL;
70 for (i=0; i<dfas->hash; i++)
71 dfas->hasharray[i] = NULL;
75 int rm_DFA_states (struct DFA_states **dfasp)
77 struct DFA_states *dfas = *dfasp;
79 struct DFA_trans *tm, *tm1;
83 ifree (dfas->hasharray);
84 ifree (dfas->sortarray);
86 for (tm=dfas->transmem; tm; tm=tm1)
88 ifree (tm->tran_block);
92 for (sm=dfas->statemem; sm; sm=sm1)
94 ifree (sm->state_block);
103 int add_DFA_state (struct DFA_states *dfas, Set *s, struct DFA_state **sp)
106 struct DFA_state *si, **sip;
111 assert (dfas->hasharray);
112 sip = dfas->hasharray + (hash_Set (dfas->st, *s) % dfas->hash);
113 for (si = *sip; si; si=si->link)
114 if (eq_Set (dfas->st, si->set, *s))
117 *s = rm_Set (dfas->st, *s);
122 sb = (DFA_stateb *) imalloc (sizeof(*sb));
123 sb->next = dfas->statemem;
125 sb->state_block = si = dfas->freelist =
126 (struct DFA_state *) imalloc (sizeof(struct DFA_state)*DFA_CHUNK);
127 for (i = 0; i<DFA_CHUNK-1; i++, si++)
133 dfas->freelist = si->next;
135 si->next = dfas->unmarked;
141 si->no = (dfas->no)++;
149 void add_DFA_tran (struct DFA_states *dfas, struct DFA_state *s,
150 int ch0, int ch1, int to)
152 struct DFA_trans *tm;
156 if (tm->ptr == tm->size)
158 tm = (struct DFA_trans *) imalloc (sizeof(struct DFA_trans));
160 tm->next = dfas->transmem;
162 tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
163 tm->tran_block = (struct DFA_tran *)
164 imalloc (sizeof(struct DFA_tran) * tm->size);
165 assert (tm->tran_block);
167 memcpy (tm->tran_block, s->trans,
168 s->tran_no*sizeof (struct DFA_tran));
169 tm->ptr = s->tran_no;
170 s->trans = tm->tran_block;
173 t = tm->tran_block + tm->ptr++;
179 struct DFA_state *get_DFA_state (struct DFA_states *dfas)
181 struct DFA_state *si;
183 if (!(si = dfas->unmarked))
185 dfas->unmarked = si->next;
186 si->next = dfas->marked;
188 si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
193 void sort_DFA_states (struct DFA_states *dfas)
197 dfas->sortarray = (struct DFA_state **)
198 imalloc (sizeof(struct DFA_state *)*dfas->no);
199 for (s = dfas->marked; s; s=s->next)
200 dfas->sortarray[s->no] = s;
201 ifree (dfas->hasharray);
202 dfas->hasharray = NULL;