]>
Commit | Line | Data |
---|---|---|
d76ed9a9 AS |
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 "rxnode.h" | |
25 | \f | |
26 | ||
27 | ||
28 | #define INITSIZE 8 | |
29 | #define EXPANDSIZE 8 | |
30 | ||
31 | #ifdef __STDC__ | |
32 | static int | |
33 | rx_init_string(struct rx_string *thisone, char first) | |
34 | #else | |
35 | static int | |
36 | rx_init_string(thisone, first) | |
37 | struct rx_string *thisone; | |
38 | char first; | |
39 | #endif | |
40 | { | |
41 | char *tmp; | |
42 | ||
43 | tmp = (char *) malloc (INITSIZE); | |
44 | ||
45 | if(!tmp) | |
46 | return -1; | |
47 | ||
48 | thisone->contents = tmp; | |
49 | thisone->contents[0] = first; | |
50 | thisone->reallen = INITSIZE; | |
51 | thisone->len = 1; | |
52 | return 0; | |
53 | } | |
54 | ||
55 | #ifdef __STDC__ | |
56 | static void | |
57 | rx_free_string (struct rx_string *junk) | |
58 | #else | |
59 | static void | |
60 | rx_free_string (junk) | |
61 | struct rx_string *junk; | |
62 | #endif | |
63 | { | |
64 | free (junk->contents); | |
65 | junk->len = junk->reallen = 0; | |
66 | junk->contents = 0; | |
67 | } | |
68 | ||
69 | ||
70 | #ifdef __STDC__ | |
71 | int | |
72 | rx_adjoin_string (struct rx_string *str, char c) | |
73 | #else | |
74 | int | |
75 | rx_adjoin_string (str, c) | |
76 | struct rx_string *str; | |
77 | char c; | |
78 | #endif | |
79 | { | |
80 | if (!str->contents) | |
81 | return rx_init_string (str, c); | |
82 | ||
83 | if (str->len == str->reallen) | |
84 | { | |
85 | char *temp; | |
86 | temp = (char *) realloc (str->contents, str->reallen + EXPANDSIZE); | |
87 | ||
88 | if(!temp) | |
89 | return -1; | |
90 | ||
91 | str->contents = temp; | |
92 | str->reallen += EXPANDSIZE; | |
93 | } | |
94 | ||
95 | str->contents[str->len++] = c; | |
96 | return 0; | |
97 | } | |
98 | ||
99 | ||
100 | #ifdef __STDC__ | |
101 | static int | |
102 | rx_copy_string (struct rx_string *to, struct rx_string *from) | |
103 | #else | |
104 | static int | |
105 | rx_copy_string (to, from) | |
106 | struct rx_string *to; | |
107 | struct rx_string *from; | |
108 | #endif | |
109 | { | |
110 | char *tmp; | |
111 | ||
112 | if (from->len) | |
113 | { | |
114 | tmp = (char *) malloc (from->reallen); | |
115 | ||
116 | if (!tmp) | |
117 | return -1; | |
118 | } | |
119 | ||
120 | rx_free_string (to); | |
121 | to->len = from->len; | |
122 | to->reallen = from->reallen; | |
123 | to->contents = tmp; | |
124 | ||
125 | memcpy (to->contents, from->contents, from->reallen); | |
126 | ||
127 | return 0; | |
128 | } | |
129 | ||
130 | ||
131 | #ifdef __STDC__ | |
132 | static int | |
133 | rx_compare_rx_strings (struct rx_string *a, struct rx_string *b) | |
134 | #else | |
135 | static int | |
136 | rx_compare_rx_strings (a, b) | |
137 | struct rx_string *a; | |
138 | struct rx_string *b; | |
139 | #endif | |
140 | { | |
141 | if (a->len != b->len) | |
142 | return 0; | |
143 | ||
144 | if (a->len) | |
145 | return !memcmp (a->contents, b->contents, a->len); | |
146 | else | |
147 | return 1; /* trivial case: "" == "" */ | |
148 | } | |
149 | ||
150 | ||
151 | #ifdef __STDC__ | |
152 | static unsigned long | |
153 | rx_string_hash (unsigned long seed, struct rx_string *str) | |
154 | #else | |
155 | static unsigned long | |
156 | rx_string_hash (seed, str) | |
157 | unsigned long seed; | |
158 | struct rx_string *str; | |
159 | #endif | |
160 | { | |
161 | /* From Tcl: */ | |
162 | unsigned long result; | |
163 | int c; | |
164 | char * string; | |
165 | int len; | |
166 | ||
167 | string = str->contents; | |
168 | len = str->len; | |
169 | result = seed; | |
170 | ||
171 | while (len--) | |
172 | { | |
173 | c = *string; | |
174 | string++; | |
175 | result += (result<<3) + c; | |
176 | } | |
177 | return result; | |
178 | } | |
179 | ||
180 | ||
181 | \f | |
182 | ||
183 | #ifdef __STDC__ | |
184 | struct rexp_node * | |
185 | rexp_node (int type) | |
186 | #else | |
187 | struct rexp_node * | |
188 | rexp_node (type) | |
189 | int type; | |
190 | #endif | |
191 | { | |
192 | struct rexp_node *n; | |
193 | ||
194 | n = (struct rexp_node *) malloc (sizeof (*n)); | |
195 | rx_bzero ((char *)n, sizeof (*n)); | |
196 | if (n) | |
197 | { | |
198 | n->type = type; | |
199 | n->id = -1; | |
200 | n->refs = 1; | |
201 | } | |
202 | return n; | |
203 | } | |
204 | ||
205 | ||
206 | /* free_rexp_node assumes that the bitset passed to rx_mk_r_cset | |
207 | * can be freed using rx_free_cset. | |
208 | */ | |
209 | ||
210 | #ifdef __STDC__ | |
211 | struct rexp_node * | |
212 | rx_mk_r_cset (int type, int size, rx_Bitset b) | |
213 | #else | |
214 | struct rexp_node * | |
215 | rx_mk_r_cset (type, size, b) | |
216 | int type; | |
217 | int size; | |
218 | rx_Bitset b; | |
219 | #endif | |
220 | { | |
221 | struct rexp_node * n; | |
222 | n = rexp_node (type); | |
223 | if (n) | |
224 | { | |
225 | n->params.cset = b; | |
226 | n->params.cset_size = size; | |
227 | } | |
228 | return n; | |
229 | } | |
230 | ||
231 | ||
232 | #ifdef __STDC__ | |
233 | struct rexp_node * | |
234 | rx_mk_r_int (int type, int intval) | |
235 | #else | |
236 | struct rexp_node * | |
237 | rx_mk_r_int (type, intval) | |
238 | int type; | |
239 | int intval; | |
240 | #endif | |
241 | { | |
242 | struct rexp_node * n; | |
243 | n = rexp_node (type); | |
244 | if (n) | |
245 | n->params.intval = intval; | |
246 | return n; | |
247 | } | |
248 | ||
249 | ||
250 | #ifdef __STDC__ | |
251 | struct rexp_node * | |
252 | rx_mk_r_str (int type, char c) | |
253 | #else | |
254 | struct rexp_node * | |
255 | rx_mk_r_str (type, c) | |
256 | int type; | |
257 | char c; | |
258 | #endif | |
259 | { | |
260 | struct rexp_node *n; | |
261 | n = rexp_node (type); | |
262 | if (n) | |
263 | rx_init_string (&(n->params.cstr), c); | |
264 | return n; | |
265 | } | |
266 | ||
267 | ||
268 | #ifdef __STDC__ | |
269 | struct rexp_node * | |
270 | rx_mk_r_binop (int type, struct rexp_node * a, struct rexp_node * b) | |
271 | #else | |
272 | struct rexp_node * | |
273 | rx_mk_r_binop (type, a, b) | |
274 | int type; | |
275 | struct rexp_node * a; | |
276 | struct rexp_node * b; | |
277 | #endif | |
278 | { | |
279 | struct rexp_node * n = rexp_node (type); | |
280 | if (n) | |
281 | { | |
282 | n->params.pair.left = a; | |
283 | n->params.pair.right = b; | |
284 | } | |
285 | return n; | |
286 | } | |
287 | ||
288 | ||
289 | #ifdef __STDC__ | |
290 | struct rexp_node * | |
291 | rx_mk_r_monop (int type, struct rexp_node * a) | |
292 | #else | |
293 | struct rexp_node * | |
294 | rx_mk_r_monop (type, a) | |
295 | int type; | |
296 | struct rexp_node * a; | |
297 | #endif | |
298 | { | |
299 | return rx_mk_r_binop (type, a, 0); | |
300 | } | |
301 | ||
302 | ||
303 | #ifdef __STDC__ | |
304 | void | |
305 | rx_free_rexp (struct rexp_node * node) | |
306 | #else | |
307 | void | |
308 | rx_free_rexp (node) | |
309 | struct rexp_node * node; | |
310 | #endif | |
311 | { | |
312 | if (node && !--node->refs) | |
313 | { | |
314 | if (node->params.cset) | |
315 | rx_free_cset (node->params.cset); | |
316 | if (node->params.cstr.reallen) | |
317 | rx_free_string (&(node->params.cstr)); | |
318 | rx_free_rexp (node->params.pair.left); | |
319 | rx_free_rexp (node->params.pair.right); | |
320 | rx_free_rexp (node->simplified); | |
321 | free ((char *)node); | |
322 | } | |
323 | } | |
324 | ||
325 | #ifdef __STDC__ | |
326 | void | |
327 | rx_save_rexp (struct rexp_node * node) | |
328 | #else | |
329 | void | |
330 | rx_save_rexp (node) | |
331 | struct rexp_node * node; | |
332 | #endif | |
333 | { | |
334 | if (node) | |
335 | ++node->refs; | |
336 | } | |
337 | ||
338 | ||
339 | #ifdef __STDC__ | |
340 | struct rexp_node * | |
341 | rx_copy_rexp (int cset_size, struct rexp_node *node) | |
342 | #else | |
343 | struct rexp_node * | |
344 | rx_copy_rexp (cset_size, node) | |
345 | int cset_size; | |
346 | struct rexp_node *node; | |
347 | #endif | |
348 | { | |
349 | if (!node) | |
350 | return 0; | |
351 | else | |
352 | { | |
353 | struct rexp_node *n; | |
354 | n = rexp_node (node->type); | |
355 | if (!n) | |
356 | return 0; | |
357 | ||
358 | if (node->params.cset) | |
359 | { | |
360 | n->params.cset = rx_copy_cset (cset_size, | |
361 | node->params.cset); | |
362 | if (!n->params.cset) | |
363 | { | |
364 | rx_free_rexp (n); | |
365 | return 0; | |
366 | } | |
367 | } | |
368 | ||
369 | if (node->params.cstr.reallen) | |
370 | if (rx_copy_string (&(n->params.cstr), &(node->params.cstr))) | |
371 | { | |
372 | rx_free_rexp(n); | |
373 | return 0; | |
374 | } | |
375 | ||
376 | n->params.intval = node->params.intval; | |
377 | n->params.intval2 = node->params.intval2; | |
378 | n->params.pair.left = rx_copy_rexp (cset_size, node->params.pair.left); | |
379 | n->params.pair.right = rx_copy_rexp (cset_size, node->params.pair.right); | |
380 | if ( (node->params.pair.left && !n->params.pair.left) | |
381 | || (node->params.pair.right && !n->params.pair.right)) | |
382 | { | |
383 | rx_free_rexp (n); | |
384 | return 0; | |
385 | } | |
386 | n->id = node->id; | |
387 | n->len = node->len; | |
388 | n->observed = node->observed; | |
389 | return n; | |
390 | } | |
391 | } | |
392 | ||
393 | \f | |
394 | ||
395 | #ifdef __STDC__ | |
396 | struct rexp_node * | |
397 | rx_shallow_copy_rexp (int cset_size, struct rexp_node *node) | |
398 | #else | |
399 | struct rexp_node * | |
400 | rx_shallow_copy_rexp (cset_size, node) | |
401 | int cset_size; | |
402 | struct rexp_node *node; | |
403 | #endif | |
404 | { | |
405 | if (!node) | |
406 | return 0; | |
407 | else | |
408 | { | |
409 | struct rexp_node *n; | |
410 | n = rexp_node (node->type); | |
411 | if (!n) | |
412 | return 0; | |
413 | ||
414 | if (node->params.cset) | |
415 | { | |
416 | n->params.cset = rx_copy_cset (cset_size, | |
417 | node->params.cset); | |
418 | if (!n->params.cset) | |
419 | { | |
420 | rx_free_rexp (n); | |
421 | return 0; | |
422 | } | |
423 | } | |
424 | ||
425 | if (node->params.cstr.reallen) | |
426 | if (rx_copy_string (&(n->params.cstr), &(node->params.cstr))) | |
427 | { | |
428 | rx_free_rexp(n); | |
429 | return 0; | |
430 | } | |
431 | ||
432 | n->params.intval = node->params.intval; | |
433 | n->params.intval2 = node->params.intval2; | |
434 | n->params.pair.left = node->params.pair.left; | |
435 | rx_save_rexp (node->params.pair.left); | |
436 | n->params.pair.right = node->params.pair.right; | |
437 | rx_save_rexp (node->params.pair.right); | |
438 | n->id = node->id; | |
439 | n->len = node->len; | |
440 | n->observed = node->observed; | |
441 | return n; | |
442 | } | |
443 | } | |
444 | ||
445 | \f | |
446 | ||
447 | ||
448 | #ifdef __STDC__ | |
449 | int | |
450 | rx_rexp_equal (struct rexp_node * a, struct rexp_node * b) | |
451 | #else | |
452 | int | |
453 | rx_rexp_equal (a, b) | |
454 | struct rexp_node * a; | |
455 | struct rexp_node * b; | |
456 | #endif | |
457 | { | |
458 | int ret; | |
459 | ||
460 | if (a == b) | |
461 | return 1; | |
462 | ||
463 | if ((a == 0) || (b == 0)) | |
464 | return 0; | |
465 | ||
466 | if (a->type != b->type) | |
467 | return 0; | |
468 | ||
469 | switch (a->type) | |
470 | { | |
471 | case r_cset: | |
472 | ret = ( (a->params.cset_size == b->params.cset_size) | |
473 | && rx_bitset_is_equal (a->params.cset_size, | |
474 | a->params.cset, | |
475 | b->params.cset)); | |
476 | break; | |
477 | ||
478 | case r_string: | |
479 | ret = rx_compare_rx_strings (&(a->params.cstr), &(b->params.cstr)); | |
480 | break; | |
481 | ||
482 | case r_cut: | |
483 | ret = (a->params.intval == b->params.intval); | |
484 | break; | |
485 | ||
486 | case r_concat: | |
487 | case r_alternate: | |
488 | ret = ( rx_rexp_equal (a->params.pair.left, b->params.pair.left) | |
489 | && rx_rexp_equal (a->params.pair.right, b->params.pair.right)); | |
490 | break; | |
491 | case r_opt: | |
492 | case r_star: | |
493 | case r_plus: | |
494 | ret = rx_rexp_equal (a->params.pair.left, b->params.pair.left); | |
495 | break; | |
496 | case r_interval: | |
497 | ret = ( (a->params.intval == b->params.intval) | |
498 | && (a->params.intval2 == b->params.intval2) | |
499 | && rx_rexp_equal (a->params.pair.left, b->params.pair.left)); | |
500 | break; | |
501 | case r_parens: | |
502 | ret = ( (a->params.intval == b->params.intval) | |
503 | && rx_rexp_equal (a->params.pair.left, b->params.pair.left)); | |
504 | break; | |
505 | ||
506 | case r_context: | |
507 | ret = (a->params.intval == b->params.intval); | |
508 | break; | |
509 | default: | |
510 | return 0; | |
511 | } | |
512 | return ret; | |
513 | } | |
514 | ||
515 | ||
516 | \f | |
517 | ||
518 | ||
519 | #ifdef __STDC__ | |
520 | unsigned long | |
521 | rx_rexp_hash (struct rexp_node * node, unsigned long seed) | |
522 | #else | |
523 | unsigned long | |
524 | rx_rexp_hash (node, seed) | |
525 | struct rexp_node * node; | |
526 | unsigned long seed; | |
527 | #endif | |
528 | { | |
529 | if (!node) | |
530 | return seed; | |
531 | ||
532 | seed = rx_rexp_hash (node->params.pair.left, seed); | |
533 | seed = rx_rexp_hash (node->params.pair.right, seed); | |
534 | seed = rx_bitset_hash (node->params.cset_size, node->params.cset); | |
535 | seed = rx_string_hash (seed, &(node->params.cstr)); | |
536 | seed += (seed << 3) + node->params.intval; | |
537 | seed += (seed << 3) + node->params.intval2; | |
538 | seed += (seed << 3) + node->type; | |
539 | seed += (seed << 3) + node->id; | |
540 | #if 0 | |
541 | seed += (seed << 3) + node->len; | |
542 | seed += (seed << 3) + node->observed; | |
543 | #endif | |
544 | return seed; | |
545 | } |