]>
Commit | Line | Data |
---|---|---|
1 | /* classes: src_files */ | |
2 | ||
3 | /* Copyright (C) 1995, 1996 Tom Lord | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify | |
6 | * it under the terms of the GNU Library General Public License as published by | |
7 | * the Free Software Foundation; either version 2, or (at your option) | |
8 | * any later version. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, | |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | * GNU Library General Public License for more details. | |
14 | * | |
15 | * You should have received a copy of the GNU Library General Public License | |
16 | * along with this software; see the file COPYING. If not, write to | |
17 | * the Free Software Foundation, 59 Temple Place - Suite 330, | |
18 | * Boston, MA 02111-1307, USA. | |
19 | */ | |
20 | ||
21 | ||
22 | \f | |
23 | #include "rxall.h" | |
24 | #include "rx.h" | |
25 | #include "rxunfa.h" | |
26 | #include "rxnfa.h" | |
27 | \f | |
28 | ||
29 | #ifdef __STDC__ | |
30 | static int | |
31 | unfa_equal (void * va, void * vb) | |
32 | #else | |
33 | static int | |
34 | unfa_equal (va, vb) | |
35 | void * va; | |
36 | void * vb; | |
37 | #endif | |
38 | { | |
39 | return rx_rexp_equal ((struct rexp_node *)va, (struct rexp_node *)vb); | |
40 | } | |
41 | ||
42 | ||
43 | struct rx_hash_rules unfa_rules = { unfa_equal, 0, 0, 0, 0 }; | |
44 | ||
45 | ||
46 | #ifdef __STDC__ | |
47 | static struct rx_cached_rexp * | |
48 | canonical_unfa (struct rx_hash * table, struct rexp_node * rexp, int cset_size) | |
49 | #else | |
50 | static struct rx_cached_rexp * | |
51 | canonical_unfa (table, rexp, cset_size) | |
52 | struct rx_hash * table; | |
53 | struct rexp_node * rexp; | |
54 | int cset_size; | |
55 | #endif | |
56 | { | |
57 | struct rx_hash_item * it; | |
58 | it = rx_hash_store (table, rx_rexp_hash (rexp, 0), rexp, &unfa_rules); | |
59 | ||
60 | if (it->binding == 0) | |
61 | { | |
62 | struct rx_cached_rexp * cr; | |
63 | ||
64 | if (it->data == (void *)rexp) | |
65 | rx_save_rexp (rexp); | |
66 | ||
67 | cr = (struct rx_cached_rexp *)malloc (sizeof (*cr)); | |
68 | rx_bzero ((char *)cr, sizeof (*cr)); | |
69 | if (!cr) | |
70 | return 0; | |
71 | it->binding = (void *)cr; | |
72 | cr->unfa.nfa = 0; | |
73 | cr->unfa.exp = rexp; | |
74 | cr->hash_item = it; | |
75 | rx_save_rexp (rexp); | |
76 | } | |
77 | return (struct rx_cached_rexp *)it->binding; | |
78 | } | |
79 | ||
80 | ||
81 | #ifdef __STDC__ | |
82 | static struct rx * | |
83 | rx_unfa_rx (struct rx_cached_rexp * cr, struct rexp_node * exp, int cset_size) | |
84 | #else | |
85 | static struct rx * | |
86 | rx_unfa_rx (cr, exp, cset_size) | |
87 | struct rx_cached_rexp * cr; | |
88 | struct rexp_node * exp; | |
89 | int cset_size; | |
90 | #endif | |
91 | { | |
92 | struct rx * new_rx; | |
93 | ||
94 | if (cr->unfa.nfa) | |
95 | return cr->unfa.nfa; | |
96 | ||
97 | new_rx = rx_make_rx (cset_size); | |
98 | if (!new_rx) | |
99 | return 0; | |
100 | { | |
101 | struct rx_nfa_state * start; | |
102 | struct rx_nfa_state * end; | |
103 | start = end = 0; | |
104 | if (!rx_build_nfa (new_rx, exp, &start, &end)) | |
105 | { | |
106 | free (new_rx); | |
107 | return 0; | |
108 | } | |
109 | new_rx->start_nfa_states = start; | |
110 | end->is_final = 1; | |
111 | start->is_start = 1; | |
112 | { | |
113 | struct rx_nfa_state * s; | |
114 | int x; | |
115 | x = 0; | |
116 | for (s = new_rx->nfa_states; s; s = s->next) | |
117 | s->id = x++; | |
118 | } | |
119 | } | |
120 | cr->unfa.nfa = new_rx; | |
121 | return new_rx; | |
122 | } | |
123 | ||
124 | ||
125 | \f | |
126 | ||
127 | #ifdef __STDC__ | |
128 | struct rx_unfaniverse * | |
129 | rx_make_unfaniverse (int delay) | |
130 | #else | |
131 | struct rx_unfaniverse * | |
132 | rx_make_unfaniverse (delay) | |
133 | int delay; | |
134 | #endif | |
135 | { | |
136 | struct rx_unfaniverse * it; | |
137 | it = (struct rx_unfaniverse *)malloc (sizeof (*it)); | |
138 | if (!it) return 0; | |
139 | rx_bzero ((char *)it, sizeof (*it)); | |
140 | it->delay = delay; | |
141 | return it; | |
142 | } | |
143 | ||
144 | ||
145 | #ifdef __STDC__ | |
146 | void | |
147 | rx_free_unfaniverse (struct rx_unfaniverse * it) | |
148 | #else | |
149 | void | |
150 | rx_free_unfaniverse (it) | |
151 | struct rx_unfaniverse * it; | |
152 | #endif | |
153 | { | |
154 | } | |
155 | ||
156 | ||
157 | ||
158 | \f | |
159 | ||
160 | #ifdef __STDC__ | |
161 | struct rx_unfa * | |
162 | rx_unfa (struct rx_unfaniverse * unfaniverse, struct rexp_node * exp, int cset_size) | |
163 | #else | |
164 | struct rx_unfa * | |
165 | rx_unfa (unfaniverse, exp, cset_size) | |
166 | struct rx_unfaniverse * unfaniverse; | |
167 | struct rexp_node * exp; | |
168 | int cset_size; | |
169 | #endif | |
170 | { | |
171 | struct rx_cached_rexp * cr; | |
172 | if (exp && exp->cr) | |
173 | cr = exp->cr; | |
174 | else | |
175 | { | |
176 | cr = canonical_unfa (&unfaniverse->table, exp, cset_size); | |
177 | if (exp) | |
178 | exp->cr = cr; | |
179 | } | |
180 | if (!cr) | |
181 | return 0; | |
182 | if (cr->next) | |
183 | { | |
184 | if (unfaniverse->free_queue == cr) | |
185 | { | |
186 | unfaniverse->free_queue = cr->next; | |
187 | if (unfaniverse->free_queue == cr) | |
188 | unfaniverse->free_queue = 0; | |
189 | } | |
190 | cr->next->prev = cr->prev; | |
191 | cr->prev->next = cr->next; | |
192 | cr->next = 0; | |
193 | cr->prev = 0; | |
194 | --unfaniverse->delayed; | |
195 | } | |
196 | ++cr->unfa.refs; | |
197 | cr->unfa.cset_size = cset_size; | |
198 | cr->unfa.verse = unfaniverse; | |
199 | rx_unfa_rx (cr, exp, cset_size); | |
200 | return &cr->unfa; | |
201 | } | |
202 | ||
203 | ||
204 | #ifdef __STDC__ | |
205 | void | |
206 | rx_free_unfa (struct rx_unfa * unfa) | |
207 | #else | |
208 | void | |
209 | rx_free_unfa (unfa) | |
210 | struct rx_unfa * unfa; | |
211 | #endif | |
212 | { | |
213 | struct rx_cached_rexp * cr; | |
214 | cr = (struct rx_cached_rexp *)unfa; | |
215 | if (!cr) | |
216 | return; | |
217 | if (!--cr->unfa.refs) | |
218 | { | |
219 | if (!unfa->verse->free_queue) | |
220 | { | |
221 | unfa->verse->free_queue = cr; | |
222 | cr->next = cr->prev = cr; | |
223 | } | |
224 | else | |
225 | { | |
226 | cr->next = unfa->verse->free_queue; | |
227 | cr->prev = unfa->verse->free_queue->prev; | |
228 | cr->next->prev = cr; | |
229 | cr->prev->next = cr; | |
230 | } | |
231 | ||
232 | ++unfa->verse->delayed; | |
233 | while (unfa->verse->delayed > unfa->verse->delay) | |
234 | { | |
235 | struct rx_cached_rexp * it; | |
236 | it = unfa->verse->free_queue; | |
237 | unfa->verse->free_queue = it->next; | |
238 | if (!--unfa->verse->delayed) | |
239 | unfa->verse->free_queue = 0; | |
240 | it->prev->next = it->next; | |
241 | it->next->prev = it->prev; | |
242 | if (it->unfa.exp) | |
243 | it->unfa.exp->cr = 0; | |
244 | rx_free_rexp ((struct rexp_node *)it->hash_item->data); | |
245 | rx_hash_free (it->hash_item, &unfa_rules); | |
246 | rx_free_rx (it->unfa.nfa); | |
247 | rx_free_rexp (it->unfa.exp); | |
248 | free (it); | |
249 | if (it == cr) | |
250 | break; | |
251 | } | |
252 | } | |
253 | else | |
254 | return; | |
255 | } | |
256 | ||
257 | ||
258 | #ifdef __STDC__ | |
259 | void | |
260 | rx_save_unfa (struct rx_unfa * unfa) | |
261 | #else | |
262 | void | |
263 | rx_save_unfa (unfa) | |
264 | struct rx_unfa * unfa; | |
265 | #endif | |
266 | { | |
267 | ++(unfa->refs); | |
268 | } | |
269 |