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
23 #include "rxall.h"
24 #include "rxnode.h"
25
26
27
28 #define INITSIZE 8
29 #define EXPANDSIZE 8
30
31 #ifdef __STDC__
32 static int
rx_init_string(struct rx_string * thisone,char first)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
rx_free_string(struct rx_string * junk)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
rx_adjoin_string(struct rx_string * str,char c)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
rx_copy_string(struct rx_string * to,struct rx_string * from)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
rx_compare_rx_strings(struct rx_string * a,struct rx_string * b)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
rx_string_hash(unsigned long seed,struct rx_string * str)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
182
183 #ifdef __STDC__
184 struct rexp_node *
rexp_node(int type)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 *
rx_mk_r_cset(int type,int size,rx_Bitset b)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 *
rx_mk_r_int(int type,int intval)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 *
rx_mk_r_str(int type,char c)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 *
rx_mk_r_binop(int type,struct rexp_node * a,struct rexp_node * b)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 *
rx_mk_r_monop(int type,struct rexp_node * a)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
rx_free_rexp(struct rexp_node * node)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
rx_save_rexp(struct rexp_node * node)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 *
rx_copy_rexp(int cset_size,struct rexp_node * 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
394
395 #ifdef __STDC__
396 struct rexp_node *
rx_shallow_copy_rexp(int cset_size,struct rexp_node * 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
446
447
448 #ifdef __STDC__
449 int
rx_rexp_equal(struct rexp_node * a,struct rexp_node * b)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
517
518
519 #ifdef __STDC__
520 unsigned long
rx_rexp_hash(struct rexp_node * node,unsigned long seed)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 }
546