1: /* Extended regular expression matching and search library.
2: Copyright (C) 2002, 2003 Free Software Foundation, Inc.
3: This file is part of the GNU C Library.
4: Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5:
6: The GNU C Library is free software; you can redistribute it and/or
7: modify it under the terms of the GNU Lesser General Public
8: License as published by the Free Software Foundation; either
9: version 2.1 of the License, or (at your option) any later version.
10:
11: The GNU C Library is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: Lesser General Public License for more details.
15:
16: You should have received a copy of the GNU Lesser General Public
17: License along with the GNU C Library; if not, write to the Free
18: Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19: 02111-1307 USA. */
20:
21: static void re_string_construct_common (const char *str, int len,
22: re_string_t *pstr,
23: RE_TRANSLATE_TYPE trans, int icase);
24: #ifdef RE_ENABLE_I18N
25: static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx,
26: wint_t *last_wc);
27: #endif /* RE_ENABLE_I18N */
28: static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
29: const re_node_set *nodes,
30: unsigned int hash);
31: static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
32: unsigned int hash);
33: static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
34: const re_node_set *nodes,
35: unsigned int hash);
36: static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
37: const re_node_set *nodes,
38: unsigned int context,
39: unsigned int hash);
40: static unsigned int inline calc_state_hash (const re_node_set *nodes,
41: unsigned int context);
42:
43: /* Functions for string operation. */
44:
45: /* This function allocate the buffers. It is necessary to call
46: re_string_reconstruct before using the object. */
47:
48: static reg_errcode_t
49: re_string_allocate (pstr, str, len, init_len, trans, icase)
50: re_string_t *pstr;
51: const char *str;
52: int len, init_len, icase;
53: RE_TRANSLATE_TYPE trans;
54: {
55: reg_errcode_t ret;
56: int init_buf_len = (len + 1 < init_len) ? len + 1: init_len;
57: re_string_construct_common (str, len, pstr, trans, icase);
58: pstr->stop = pstr->len;
59:
60: ret = re_string_realloc_buffers (pstr, init_buf_len);
61: if (BE (ret != REG_NOERROR, 0))
62: return ret;
63:
64: pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
65: : (unsigned char *) str);
66: pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
67: pstr->valid_len = (MBS_CASE_ALLOCATED (pstr) || MBS_ALLOCATED (pstr)
68: || MB_CUR_MAX > 1) ? pstr->valid_len : len;
69: return REG_NOERROR;
70: }
71:
72: /* This function allocate the buffers, and initialize them. */
73:
74: static reg_errcode_t
75: re_string_construct (pstr, str, len, trans, icase)
76: re_string_t *pstr;
77: const char *str;
78: int len, icase;
79: RE_TRANSLATE_TYPE trans;
80: {
81: reg_errcode_t ret;
82: re_string_construct_common (str, len, pstr, trans, icase);
83: pstr->stop = pstr->len;
84: /* Set 0 so that this function can initialize whole buffers. */
85: pstr->valid_len = 0;
86:
87: if (len > 0)
88: {
89: ret = re_string_realloc_buffers (pstr, len + 1);
90: if (BE (ret != REG_NOERROR, 0))
91: return ret;
92: }
93: pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
94: : (unsigned char *) str);
95: pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
96:
97: if (icase)
98: {
99: #ifdef RE_ENABLE_I18N
100: if (MB_CUR_MAX > 1)
101: build_wcs_upper_buffer (pstr);
102: else
103: #endif /* RE_ENABLE_I18N */
104: build_upper_buffer (pstr);
105: }
106: else
107: {
108: #ifdef RE_ENABLE_I18N
109: if (MB_CUR_MAX > 1)
110: build_wcs_buffer (pstr);
111: else
112: #endif /* RE_ENABLE_I18N */
113: {
114: if (trans != NULL)
115: re_string_translate_buffer (pstr);
116: else
117: pstr->valid_len = len;
118: }
119: }
120:
121: /* Initialized whole buffers, then valid_len == bufs_len. */
122: pstr->valid_len = pstr->bufs_len;
123: return REG_NOERROR;
124: }
125:
126: /* Helper functions for re_string_allocate, and re_string_construct. */
127:
128: static reg_errcode_t
129: re_string_realloc_buffers (pstr, new_buf_len)
130: re_string_t *pstr;
131: int new_buf_len;
132: {
133: #ifdef RE_ENABLE_I18N
134: if (MB_CUR_MAX > 1)
135: {
136: wint_t *new_array = re_realloc (pstr->wcs, wint_t, new_buf_len);
137: if (BE (new_array == NULL, 0))
138: return REG_ESPACE;
139: pstr->wcs = new_array;
140: }
141: #endif /* RE_ENABLE_I18N */
142: if (MBS_ALLOCATED (pstr))
143: {
144: unsigned char *new_array = re_realloc (pstr->mbs, unsigned char,
145: new_buf_len);
146: if (BE (new_array == NULL, 0))
147: return REG_ESPACE;
148: pstr->mbs = new_array;
149: }
150: if (MBS_CASE_ALLOCATED (pstr))
151: {
152: unsigned char *new_array = re_realloc (pstr->mbs_case, unsigned char,
153: new_buf_len);
154: if (BE (new_array == NULL, 0))
155: return REG_ESPACE;
156: pstr->mbs_case = new_array;
157: if (!MBS_ALLOCATED (pstr))
158: pstr->mbs = pstr->mbs_case;
159: }
160: pstr->bufs_len = new_buf_len;
161: return REG_NOERROR;
162: }
163:
164:
165: static void
166: re_string_construct_common (str, len, pstr, trans, icase)
167: const char *str;
168: int len;
169: re_string_t *pstr;
170: RE_TRANSLATE_TYPE trans;
171: int icase;
172: {
173: memset (pstr, '\0', sizeof (re_string_t));
174: pstr->raw_mbs = (const unsigned char *) str;
175: pstr->len = len;
176: pstr->trans = trans;
177: pstr->icase = icase ? 1 : 0;
178: }
179:
180: #ifdef RE_ENABLE_I18N
181:
182: /* Build wide character buffer PSTR->WCS.
183: If the byte sequence of the string are:
184: <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>
185: Then wide character buffer will be:
186: <wc1> , WEOF , <wc2> , WEOF , <wc3>
187: We use WEOF for padding, they indicate that the position isn't
188: a first byte of a multibyte character.
189:
190: Note that this function assumes PSTR->VALID_LEN elements are already
191: built and starts from PSTR->VALID_LEN. */
192:
193: static void
194: build_wcs_buffer (pstr)
195: re_string_t *pstr;
196: {
197: mbstate_t prev_st;
198: int byte_idx, end_idx, mbclen, remain_len;
199: /* Build the buffers from pstr->valid_len to either pstr->len or
200: pstr->bufs_len. */
201: end_idx = (pstr->bufs_len > pstr->len)? pstr->len : pstr->bufs_len;
202: for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
203: {
204: wchar_t wc;
205: remain_len = end_idx - byte_idx;
206: prev_st = pstr->cur_state;
207: mbclen = mbrtowc (&wc, ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
208: + byte_idx), remain_len, &pstr->cur_state);
209: if (BE (mbclen == (size_t) -2, 0))
210: {
211: /* The buffer doesn't have enough space, finish to build. */
212: pstr->cur_state = prev_st;
213: break;
214: }
215: else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0))
216: {
217: /* We treat these cases as a singlebyte character. */
218: mbclen = 1;
219: wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
220: pstr->cur_state = prev_st;
221: }
222:
223: /* Apply the translateion if we need. */
224: if (pstr->trans != NULL && mbclen == 1)
225: {
226: int ch = pstr->trans[pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]];
227: pstr->mbs_case[byte_idx] = ch;
228: }
229: /* Write wide character and padding. */
230: pstr->wcs[byte_idx++] = wc;
231: /* Write paddings. */
232: for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
233: pstr->wcs[byte_idx++] = WEOF;
234: }
235: pstr->valid_len = byte_idx;
236: }
237:
238: /* Build wide character buffer PSTR->WCS like build_wcs_buffer,
239: but for REG_ICASE. */
240:
241: static void
242: build_wcs_upper_buffer (pstr)
243: re_string_t *pstr;
244: {
245: mbstate_t prev_st;
246: int byte_idx, end_idx, mbclen, remain_len;
247: /* Build the buffers from pstr->valid_len to either pstr->len or
248: pstr->bufs_len. */
249: end_idx = (pstr->bufs_len > pstr->len)? pstr->len : pstr->bufs_len;
250: for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
251: {
252: wchar_t wc;
253: remain_len = end_idx - byte_idx;
254: prev_st = pstr->cur_state;
255: mbclen = mbrtowc (&wc, ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
256: + byte_idx), remain_len, &pstr->cur_state);
257: if (BE (mbclen == (size_t) -2, 0))
258: {
259: /* The buffer doesn't have enough space, finish to build. */
260: pstr->cur_state = prev_st;
261: break;
262: }
263: else if (mbclen == 1 || mbclen == (size_t) -1 || mbclen == 0)
264: {
265: /* In case of a singlebyte character. */
266: int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
267: /* Apply the translateion if we need. */
268: if (pstr->trans != NULL && mbclen == 1)
269: {
270: ch = pstr->trans[ch];
271: pstr->mbs_case[byte_idx] = ch;
272: }
273: pstr->wcs[byte_idx] = iswlower (wc) ? toupper (wc) : wc;
274: pstr->mbs[byte_idx++] = islower (ch) ? toupper (ch) : ch;
275: if (BE (mbclen == (size_t) -1, 0))
276: pstr->cur_state = prev_st;
277: }
278: else /* mbclen > 1 */
279: {
280: if (iswlower (wc))
281: wcrtomb ((char *) pstr->mbs + byte_idx, towupper (wc), &prev_st);
282: else
283: memcpy (pstr->mbs + byte_idx,
284: pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);
285: pstr->wcs[byte_idx++] = iswlower (wc) ? toupper (wc) : wc;
286: /* Write paddings. */
287: for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
288: pstr->wcs[byte_idx++] = WEOF;
289: }
290: }
291: pstr->valid_len = byte_idx;
292: }
293:
294: /* Skip characters until the index becomes greater than NEW_RAW_IDX.
295: Return the index. */
296:
297: static int
298: re_string_skip_chars (pstr, new_raw_idx, last_wc)
299: re_string_t *pstr;
300: int new_raw_idx;
301: wint_t *last_wc;
302: {
303: mbstate_t prev_st;
304: int rawbuf_idx, mbclen;
305: wchar_t wc = 0;
306:
307: /* Skip the characters which are not necessary to check. */
308: for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_len;
309: rawbuf_idx < new_raw_idx;)
310: {
311: int remain_len;
312: remain_len = pstr->len - rawbuf_idx;
313: prev_st = pstr->cur_state;
314: mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx,
315: remain_len, &pstr->cur_state);
316: if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))
317: {
318: /* We treat these cases as a singlebyte character. */
319: mbclen = 1;
320: pstr->cur_state = prev_st;
321: }
322: /* Then proceed the next character. */
323: rawbuf_idx += mbclen;
324: }
325: *last_wc = (wint_t) wc;
326: return rawbuf_idx;
327: }
328: #endif /* RE_ENABLE_I18N */
329:
330: /* Build the buffer PSTR->MBS, and apply the translation if we need.
331: This function is used in case of REG_ICASE. */
332:
333: static void
334: build_upper_buffer (pstr)
335: re_string_t *pstr;
336: {
337: int char_idx, end_idx;
338: end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
339:
340: for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)
341: {
342: int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];
343: if (pstr->trans != NULL)
344: {
345: ch = pstr->trans[ch];
346: pstr->mbs_case[char_idx] = ch;
347: }
348: if (islower (ch))
349: pstr->mbs[char_idx] = toupper (ch);
350: else
351: pstr->mbs[char_idx] = ch;
352: }
353: pstr->valid_len = char_idx;
354: }
355:
356: /* Apply TRANS to the buffer in PSTR. */
357:
358: static void
359: re_string_translate_buffer (pstr)
360: re_string_t *pstr;
361: {
362: int buf_idx, end_idx;
363: end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
364:
365: for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx)
366: {
367: int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];
368: pstr->mbs_case[buf_idx] = pstr->trans[ch];
369: }
370:
371: pstr->valid_len = buf_idx;
372: }
373:
374: /* This function re-construct the buffers.
375: Concretely, convert to wide character in case of MB_CUR_MAX > 1,
376: convert to upper case in case of REG_ICASE, apply translation. */
377:
378: static reg_errcode_t
379: re_string_reconstruct (pstr, idx, eflags, newline)
380: re_string_t *pstr;
381: int idx, eflags, newline;
382: {
383: int offset = idx - pstr->raw_mbs_idx;
384: if (offset < 0)
385: {
386: /* Reset buffer. */
387: #ifdef RE_ENABLE_I18N
388: if (MB_CUR_MAX > 1)
389: memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
390: #endif /* RE_ENABLE_I18N */
391: pstr->len += pstr->raw_mbs_idx;
392: pstr->stop += pstr->raw_mbs_idx;
393: pstr->valid_len = pstr->raw_mbs_idx = 0;
394: pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
395: : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
396: if (!MBS_CASE_ALLOCATED (pstr))
397: pstr->mbs_case = (unsigned char *) pstr->raw_mbs;
398: if (!MBS_ALLOCATED (pstr) && !MBS_CASE_ALLOCATED (pstr))
399: pstr->mbs = (unsigned char *) pstr->raw_mbs;
400: offset = idx;
401: }
402:
403: if (offset != 0)
404: {
405: /* Are the characters which are already checked remain? */
406: if (offset < pstr->valid_len)
407: {
408: /* Yes, move them to the front of the buffer. */
409: pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags,
410: newline);
411: #ifdef RE_ENABLE_I18N
412: if (MB_CUR_MAX > 1)
413: memmove (pstr->wcs, pstr->wcs + offset,
414: (pstr->valid_len - offset) * sizeof (wint_t));
415: #endif /* RE_ENABLE_I18N */
416: if (MBS_ALLOCATED (pstr))
417: memmove (pstr->mbs, pstr->mbs + offset,
418: pstr->valid_len - offset);
419: if (MBS_CASE_ALLOCATED (pstr))
420: memmove (pstr->mbs_case, pstr->mbs_case + offset,
421: pstr->valid_len - offset);
422: pstr->valid_len -= offset;
423: #if DEBUG
424: assert (pstr->valid_len > 0);
425: #endif
426: }
427: else
428: {
429: /* No, skip all characters until IDX. */
430: pstr->valid_len = 0;
431: #ifdef RE_ENABLE_I18N
432: if (MB_CUR_MAX > 1)
433: {
434: int wcs_idx;
435: wint_t wc;
436: pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;
437: for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
438: pstr->wcs[wcs_idx] = WEOF;
439: if (pstr->trans && wc <= 0xff)
440: wc = pstr->trans[wc];
441: pstr->tip_context = (IS_WIDE_WORD_CHAR (wc) ? CONTEXT_WORD
442: : ((newline && IS_WIDE_NEWLINE (wc))
443: ? CONTEXT_NEWLINE : 0));
444: }
445: else
446: #endif /* RE_ENABLE_I18N */
447: {
448: int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1];
449: if (pstr->trans)
450: c = pstr->trans[c];
451: pstr->tip_context = (IS_WORD_CHAR (c) ? CONTEXT_WORD
452: : ((newline && IS_NEWLINE (c))
453: ? CONTEXT_NEWLINE : 0));
454: }
455: }
456: if (!MBS_CASE_ALLOCATED (pstr))
457: {
458: pstr->mbs_case += offset;
459: /* In case of !MBS_ALLOCATED && !MBS_CASE_ALLOCATED. */
460: if (!MBS_ALLOCATED (pstr))
461: pstr->mbs += offset;
462: }
463: }
464: pstr->raw_mbs_idx = idx;
465: pstr->len -= offset;
466: pstr->stop -= offset;
467:
468: /* Then build the buffers. */
469: #ifdef RE_ENABLE_I18N
470: if (MB_CUR_MAX > 1)
471: {
472: if (pstr->icase)
473: build_wcs_upper_buffer (pstr);
474: else
475: build_wcs_buffer (pstr);
476: }
477: else
478: #endif /* RE_ENABLE_I18N */
479: {
480: if (pstr->icase)
481: build_upper_buffer (pstr);
482: else if (pstr->trans != NULL)
483: re_string_translate_buffer (pstr);
484: }
485: pstr->cur_idx = 0;
486:
487: return REG_NOERROR;
488: }
489:
490: static void
491: re_string_destruct (pstr)
492: re_string_t *pstr;
493: {
494: #ifdef RE_ENABLE_I18N
495: re_free (pstr->wcs);
496: #endif /* RE_ENABLE_I18N */
497: if (MBS_ALLOCATED (pstr))
498: re_free (pstr->mbs);
499: if (MBS_CASE_ALLOCATED (pstr))
500: re_free (pstr->mbs_case);
501: }
502:
503: /* Return the context at IDX in INPUT. */
504:
505: static unsigned int
506: re_string_context_at (input, idx, eflags, newline_anchor)
507: const re_string_t *input;
508: int idx, eflags, newline_anchor;
509: {
510: int c;
511: if (idx < 0 || idx == input->len)
512: {
513: if (idx < 0)
514: /* In this case, we use the value stored in input->tip_context,
515: since we can't know the character in input->mbs[-1] here. */
516: return input->tip_context;
517: else /* (idx == input->len) */
518: return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
519: : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
520: }
521: #ifdef RE_ENABLE_I18N
522: if (MB_CUR_MAX > 1)
523: {
524: wint_t wc;
525: int wc_idx = idx;
526: while(input->wcs[wc_idx] == WEOF)
527: {
528: #ifdef DEBUG
529: /* It must not happen. */
530: assert (wc_idx >= 0);
531: #endif
532: --wc_idx;
533: if (wc_idx < 0)
534: return input->tip_context;
535: }
536: wc = input->wcs[wc_idx];
537: if (IS_WIDE_WORD_CHAR (wc))
538: return CONTEXT_WORD;
539: return (newline_anchor && IS_WIDE_NEWLINE (wc)) ? CONTEXT_NEWLINE : 0;
540: }
541: else
542: #endif
543: {
544: c = re_string_byte_at (input, idx);
545: if (IS_WORD_CHAR (c))
546: return CONTEXT_WORD;
547: return (newline_anchor && IS_NEWLINE (c)) ? CONTEXT_NEWLINE : 0;
548: }
549: }
550:
551: /* Functions for set operation. */
552:
553: static reg_errcode_t
554: re_node_set_alloc (set, size)
555: re_node_set *set;
556: int size;
557: {
558: set->alloc = size;
559: set->nelem = 0;
560: set->elems = re_malloc (int, size);
561: if (BE (set->elems == NULL, 0))
562: return REG_ESPACE;
563: return REG_NOERROR;
564: }
565:
566: static reg_errcode_t
567: re_node_set_init_1 (set, elem)
568: re_node_set *set;
569: int elem;
570: {
571: set->alloc = 1;
572: set->nelem = 1;
573: set->elems = re_malloc (int, 1);
574: if (BE (set->elems == NULL, 0))
575: {
576: set->alloc = set->nelem = 0;
577: return REG_ESPACE;
578: }
579: set->elems[0] = elem;
580: return REG_NOERROR;
581: }
582:
583: static reg_errcode_t
584: re_node_set_init_2 (set, elem1, elem2)
585: re_node_set *set;
586: int elem1, elem2;
587: {
588: set->alloc = 2;
589: set->elems = re_malloc (int, 2);
590: if (BE (set->elems == NULL, 0))
591: return REG_ESPACE;
592: if (elem1 == elem2)
593: {
594: set->nelem = 1;
595: set->elems[0] = elem1;
596: }
597: else
598: {
599: set->nelem = 2;
600: if (elem1 < elem2)
601: {
602: set->elems[0] = elem1;
603: set->elems[1] = elem2;
604: }
605: else
606: {
607: set->elems[0] = elem2;
608: set->elems[1] = elem1;
609: }
610: }
611: return REG_NOERROR;
612: }
613:
614: static reg_errcode_t
615: re_node_set_init_copy (dest, src)
616: re_node_set *dest;
617: const re_node_set *src;
618: {
619: dest->nelem = src->nelem;
620: if (src->nelem > 0)
621: {
622: dest->alloc = dest->nelem;
623: dest->elems = re_malloc (int, dest->alloc);
624: if (BE (dest->elems == NULL, 0))
625: {
626: dest->alloc = dest->nelem = 0;
627: return REG_ESPACE;
628: }
629: memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
630: }
631: else
632: re_node_set_init_empty (dest);
633: return REG_NOERROR;
634: }
635:
636: /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
637: DEST. Return value indicate the error code or REG_NOERROR if succeeded.
638: Note: We assume dest->elems is NULL, when dest->alloc is 0. */
639:
640: static reg_errcode_t
641: re_node_set_add_intersect (dest, src1, src2)
642: re_node_set *dest;
643: const re_node_set *src1, *src2;
644: {
645: int i1, i2, id;
646: if (src1->nelem > 0 && src2->nelem > 0)
647: {
648: if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
649: {
650: dest->alloc = src1->nelem + src2->nelem + dest->nelem;
651: dest->elems = re_realloc (dest->elems, int, dest->alloc);
652: if (BE (dest->elems == NULL, 0))
653: return REG_ESPACE;
654: }
655: }
656: else
657: return REG_NOERROR;
658:
659: for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
660: {
661: if (src1->elems[i1] > src2->elems[i2])
662: {
663: ++i2;
664: continue;
665: }
666: if (src1->elems[i1] == src2->elems[i2])
667: {
668: while (id < dest->nelem && dest->elems[id] < src2->elems[i2])
669: ++id;
670: if (id < dest->nelem && dest->elems[id] == src2->elems[i2])
671: ++id;
672: else
673: {
674: memmove (dest->elems + id + 1, dest->elems + id,
675: sizeof (int) * (dest->nelem - id));
676: dest->elems[id++] = src2->elems[i2++];
677: ++dest->nelem;
678: }
679: }
680: ++i1;
681: }
682: return REG_NOERROR;
683: }
684:
685: /* Calculate the union set of the sets SRC1 and SRC2. And store it to
686: DEST. Return value indicate the error code or REG_NOERROR if succeeded. */
687:
688: static reg_errcode_t
689: re_node_set_init_union (dest, src1, src2)
690: re_node_set *dest;
691: const re_node_set *src1, *src2;
692: {
693: int i1, i2, id;
694: if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
695: {
696: dest->alloc = src1->nelem + src2->nelem;
697: dest->elems = re_malloc (int, dest->alloc);
698: if (BE (dest->elems == NULL, 0))
699: return REG_ESPACE;
700: }
701: else
702: {
703: if (src1 != NULL && src1->nelem > 0)
704: return re_node_set_init_copy (dest, src1);
705: else if (src2 != NULL && src2->nelem > 0)
706: return re_node_set_init_copy (dest, src2);
707: else
708: re_node_set_init_empty (dest);
709: return REG_NOERROR;
710: }
711: for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
712: {
713: if (src1->elems[i1] > src2->elems[i2])
714: {
715: dest->elems[id++] = src2->elems[i2++];
716: continue;
717: }
718: if (src1->elems[i1] == src2->elems[i2])
719: ++i2;
720: dest->elems[id++] = src1->elems[i1++];
721: }
722: if (i1 < src1->nelem)
723: {
724: memcpy (dest->elems + id, src1->elems + i1,
725: (src1->nelem - i1) * sizeof (int));
726: id += src1->nelem - i1;
727: }
728: else if (i2 < src2->nelem)
729: {
730: memcpy (dest->elems + id, src2->elems + i2,
731: (src2->nelem - i2) * sizeof (int));
732: id += src2->nelem - i2;
733: }
734: dest->nelem = id;
735: return REG_NOERROR;
736: }
737:
738: /* Calculate the union set of the sets DEST and SRC. And store it to
739: DEST. Return value indicate the error code or REG_NOERROR if succeeded. */
740:
741: static reg_errcode_t
742: re_node_set_merge (dest, src)
743: re_node_set *dest;
744: const re_node_set *src;
745: {
746: int si, di;
747: if (src == NULL || src->nelem == 0)
748: return REG_NOERROR;
749: if (dest->alloc < src->nelem + dest->nelem)
750: {
751: int *new_buffer;
752: dest->alloc = 2 * (src->nelem + dest->alloc);
753: new_buffer = re_realloc (dest->elems, int, dest->alloc);
754: if (BE (new_buffer == NULL, 0))
755: return REG_ESPACE;
756: dest->elems = new_buffer;
757: }
758:
759: for (si = 0, di = 0 ; si < src->nelem && di < dest->nelem ;)
760: {
761: int cp_from, ncp, mid, right, src_elem = src->elems[si];
762: /* Binary search the spot we will add the new element. */
763: right = dest->nelem;
764: while (di < right)
765: {
766: mid = (di + right) / 2;
767: if (dest->elems[mid] < src_elem)
768: di = mid + 1;
769: else
770: right = mid;
771: }
772: if (di >= dest->nelem)
773: break;
774:
775: if (dest->elems[di] == src_elem)
776: {
777: /* Skip since, DEST already has the element. */
778: ++di;
779: ++si;
780: continue;
781: }
782:
783: /* Skip the src elements which are less than dest->elems[di]. */
784: cp_from = si;
785: while (si < src->nelem && src->elems[si] < dest->elems[di])
786: ++si;
787: /* Copy these src elements. */
788: ncp = si - cp_from;
789: memmove (dest->elems + di + ncp, dest->elems + di,
790: sizeof (int) * (dest->nelem - di));
791: memcpy (dest->elems + di, src->elems + cp_from,
792: sizeof (int) * ncp);
793: /* Update counters. */
794: di += ncp;
795: dest->nelem += ncp;
796: }
797:
798: /* Copy remaining src elements. */
799: if (si < src->nelem)
800: {
801: memcpy (dest->elems + di, src->elems + si,
802: sizeof (int) * (src->nelem - si));
803: dest->nelem += src->nelem - si;
804: }
805: return REG_NOERROR;
806: }
807:
808: /* Insert the new element ELEM to the re_node_set* SET.
809: return 0 if SET already has ELEM,
810: return -1 if an error is occured, return 1 otherwise. */
811:
812: static int
813: re_node_set_insert (set, elem)
814: re_node_set *set;
815: int elem;
816: {
817: int idx, right, mid;
818: /* In case of the set is empty. */
819: if (set->elems == NULL || set->alloc == 0)
820: {
821: if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
822: return 1;
823: else
824: return -1;
825: }
826:
827: /* Binary search the spot we will add the new element. */
828: idx = 0;
829: right = set->nelem;
830: while (idx < right)
831: {
832: mid = (idx + right) / 2;
833: if (set->elems[mid] < elem)
834: idx = mid + 1;
835: else
836: right = mid;
837: }
838:
839: /* Realloc if we need. */
840: if (set->alloc < set->nelem + 1)
841: {
842: int *new_array;
843: set->alloc = set->alloc * 2;
844: new_array = re_malloc (int, set->alloc);
845: if (BE (new_array == NULL, 0))
846: return -1;
847: /* Copy the elements they are followed by the new element. */
848: if (idx > 0)
849: memcpy (new_array, set->elems, sizeof (int) * (idx));
850: /* Copy the elements which follows the new element. */
851: if (set->nelem - idx > 0)
852: memcpy (new_array + idx + 1, set->elems + idx,
853: sizeof (int) * (set->nelem - idx));
854: re_free (set->elems);
855: set->elems = new_array;
856: }
857: else
858: {
859: /* Move the elements which follows the new element. */
860: if (set->nelem - idx > 0)
861: memmove (set->elems + idx + 1, set->elems + idx,
862: sizeof (int) * (set->nelem - idx));
863: }
864: /* Insert the new element. */
865: set->elems[idx] = elem;
866: ++set->nelem;
867: return 1;
868: }
869:
870: /* Compare two node sets SET1 and SET2.
871: return 1 if SET1 and SET2 are equivalent, retrun 0 otherwise. */
872:
873: static int
874: re_node_set_compare (set1, set2)
875: const re_node_set *set1, *set2;
876: {
877: int i;
878: if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
879: return 0;
880: for (i = 0 ; i < set1->nelem ; i++)
881: if (set1->elems[i] != set2->elems[i])
882: return 0;
883: return 1;
884: }
885:
886: /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise. */
887:
888: static int
889: re_node_set_contains (set, elem)
890: const re_node_set *set;
891: int elem;
892: {
893: int idx, right, mid;
894: if (set->nelem <= 0)
895: return 0;
896:
897: /* Binary search the element. */
898: idx = 0;
899: right = set->nelem - 1;
900: while (idx < right)
901: {
902: mid = (idx + right) / 2;
903: if (set->elems[mid] < elem)
904: idx = mid + 1;
905: else
906: right = mid;
907: }
908: return set->elems[idx] == elem ? idx + 1 : 0;
909: }
910:
911: static void
912: re_node_set_remove_at (set, idx)
913: re_node_set *set;
914: int idx;
915: {
916: if (idx < 0 || idx >= set->nelem)
917: return;
918: if (idx < set->nelem - 1)
919: memmove (set->elems + idx, set->elems + idx + 1,
920: sizeof (int) * (set->nelem - idx - 1));
921: --set->nelem;
922: }
923:
924:
925: /* Add the token TOKEN to dfa->nodes, and return the index of the token.
926: Or return -1, if an error will be occured. */
927:
928: static int
929: re_dfa_add_node (dfa, token, mode)
930: re_dfa_t *dfa;
931: re_token_t token;
932: int mode;
933: {
934: if (dfa->nodes_len >= dfa->nodes_alloc)
935: {
936: re_token_t *new_array;
937: dfa->nodes_alloc *= 2;
938: new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
939: if (BE (new_array == NULL, 0))
940: return -1;
941: else
942: dfa->nodes = new_array;
943: if (mode)
944: {
945: int *new_nexts, *new_indices;
946: re_node_set *new_edests, *new_eclosures, *new_inveclosures;
947:
948: new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
949: new_indices = re_realloc (dfa->org_indices, int, dfa->nodes_alloc);
950: new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
951: new_eclosures = re_realloc (dfa->eclosures, re_node_set,
952: dfa->nodes_alloc);
953: new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
954: dfa->nodes_alloc);
955: if (BE (new_nexts == NULL || new_indices == NULL
956: || new_edests == NULL || new_eclosures == NULL
957: || new_inveclosures == NULL, 0))
958: return -1;
959: dfa->nexts = new_nexts;
960: dfa->org_indices = new_indices;
961: dfa->edests = new_edests;
962: dfa->eclosures = new_eclosures;
963: dfa->inveclosures = new_inveclosures;
964: }
965: }
966: dfa->nodes[dfa->nodes_len] = token;
967: dfa->nodes[dfa->nodes_len].duplicated = 0;
968: dfa->nodes[dfa->nodes_len].constraint = 0;
969: return dfa->nodes_len++;
970: }
971:
972: static unsigned int inline
973: calc_state_hash (nodes, context)
974: const re_node_set *nodes;
975: unsigned int context;
976: {
977: unsigned int hash = nodes->nelem + context;
978: int i;
979: for (i = 0 ; i < nodes->nelem ; i++)
980: hash += nodes->elems[i];
981: return hash;
982: }
983:
984: /* Search for the state whose node_set is equivalent to NODES.
985: Return the pointer to the state, if we found it in the DFA.
986: Otherwise create the new one and return it. In case of an error
987: return NULL and set the error code in ERR.
988: Note: - We assume NULL as the invalid state, then it is possible that
989: return value is NULL and ERR is REG_NOERROR.
990: - We never return non-NULL value in case of any errors, it is for
991: optimization. */
992:
993: static re_dfastate_t*
994: re_acquire_state (err, dfa, nodes)
995: reg_errcode_t *err;
996: re_dfa_t *dfa;
997: const re_node_set *nodes;
998: {
999: unsigned int hash;
1000: re_dfastate_t *new_state;
1001: struct re_state_table_entry *spot;
1002: int i;
1003: if (BE (nodes->nelem == 0, 0))
1004: {
1005: *err = REG_NOERROR;
1006: return NULL;
1007: }
1008: hash = calc_state_hash (nodes, 0);
1009: spot = dfa->state_table + (hash & dfa->state_hash_mask);
1010:
1011: for (i = 0 ; i < spot->num ; i++)
1012: {
1013: re_dfastate_t *state = spot->array[i];
1014: if (hash != state->hash)
1015: continue;
1016: if (re_node_set_compare (&state->nodes, nodes))
1017: return state;
1018: }
1019:
1020: /* There are no appropriate state in the dfa, create the new one. */
1021: new_state = create_ci_newstate (dfa, nodes, hash);
1022: if (BE (new_state != NULL, 1))
1023: return new_state;
1024: else
1025: {
1026: *err = REG_ESPACE;
1027: return NULL;
1028: }
1029: }
1030:
1031: /* Search for the state whose node_set is equivalent to NODES and
1032: whose context is equivalent to CONTEXT.
1033: Return the pointer to the state, if we found it in the DFA.
1034: Otherwise create the new one and return it. In case of an error
1035: return NULL and set the error code in ERR.
1036: Note: - We assume NULL as the invalid state, then it is possible that
1037: return value is NULL and ERR is REG_NOERROR.
1038: - We never return non-NULL value in case of any errors, it is for
1039: optimization. */
1040:
1041: static re_dfastate_t*
1042: re_acquire_state_context (err, dfa, nodes, context)
1043: reg_errcode_t *err;
1044: re_dfa_t *dfa;
1045: const re_node_set *nodes;
1046: unsigned int context;
1047: {
1048: unsigned int hash;
1049: re_dfastate_t *new_state;
1050: struct re_state_table_entry *spot;
1051: int i;
1052: if (nodes->nelem == 0)
1053: {
1054: *err = REG_NOERROR;
1055: return NULL;
1056: }
1057: hash = calc_state_hash (nodes, context);
1058: spot = dfa->state_table + (hash & dfa->state_hash_mask);
1059:
1060: for (i = 0 ; i < spot->num ; i++)
1061: {
1062: re_dfastate_t *state = spot->array[i];
1063: if (hash != state->hash)
1064: continue;
1065: if (re_node_set_compare (state->entrance_nodes, nodes)
1066: && state->context == context)
1067: return state;
1068: }
1069: /* There are no appropriate state in `dfa', create the new one. */
1070: new_state = create_cd_newstate (dfa, nodes, context, hash);
1071: if (BE (new_state != NULL, 1))
1072: return new_state;
1073: else
1074: {
1075: *err = REG_ESPACE;
1076: return NULL;
1077: }
1078: }
1079:
1080: /* Allocate memory for DFA state and initialize common properties.
1081: Return the new state if succeeded, otherwise return NULL. */
1082:
1083: static re_dfastate_t *
1084: create_newstate_common (dfa, nodes, hash)
1085: re_dfa_t *dfa;
1086: const re_node_set *nodes;
1087: unsigned int hash;
1088: {
1089: re_dfastate_t *newstate;
1090: reg_errcode_t err;
1091: newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1092: if (BE (newstate == NULL, 0))
1093: return NULL;
1094: err = re_node_set_init_copy (&newstate->nodes, nodes);
1095: if (BE (err != REG_NOERROR, 0))
1096: {
1097: re_free (newstate);
1098: return NULL;
1099: }
1100: newstate->trtable = NULL;
1101: newstate->trtable_search = NULL;
1102: newstate->hash = hash;
1103: return newstate;
1104: }
1105:
1106: /* Store the new state NEWSTATE whose hash value is HASH in appropriate
1107: position. Return value indicate the error code if failed. */
1108:
1109: static reg_errcode_t
1110: register_state (dfa, newstate, hash)
1111: re_dfa_t *dfa;
1112: re_dfastate_t *newstate;
1113: unsigned int hash;
1114: {
1115: struct re_state_table_entry *spot;
1116: spot = dfa->state_table + (hash & dfa->state_hash_mask);
1117:
1118: if (spot->alloc <= spot->num)
1119: {
1120: re_dfastate_t **new_array;
1121: spot->alloc = 2 * spot->num + 2;
1122: new_array = re_realloc (spot->array, re_dfastate_t *, spot->alloc);
1123: if (BE (new_array == NULL, 0))
1124: return REG_ESPACE;
1125: spot->array = new_array;
1126: }
1127: spot->array[spot->num++] = newstate;
1128: return REG_NOERROR;
1129: }
1130:
1131: /* Create the new state which is independ of contexts.
1132: Return the new state if succeeded, otherwise return NULL. */
1133:
1134: static re_dfastate_t *
1135: create_ci_newstate (dfa, nodes, hash)
1136: re_dfa_t *dfa;
1137: const re_node_set *nodes;
1138: unsigned int hash;
1139: {
1140: int i;
1141: reg_errcode_t err;
1142: re_dfastate_t *newstate;
1143: newstate = create_newstate_common (dfa, nodes, hash);
1144: if (BE (newstate == NULL, 0))
1145: return NULL;
1146: newstate->entrance_nodes = &newstate->nodes;
1147:
1148: for (i = 0 ; i < nodes->nelem ; i++)
1149: {
1150: re_token_t *node = dfa->nodes + nodes->elems[i];
1151: re_token_type_t type = node->type;
1152: if (type == CHARACTER && !node->constraint)
1153: continue;
1154:
1155: /* If the state has the halt node, the state is a halt state. */
1156: else if (type == END_OF_RE)
1157: newstate->halt = 1;
1158: #ifdef RE_ENABLE_I18N
1159: else if (type == COMPLEX_BRACKET
1160: || (type == OP_PERIOD && MB_CUR_MAX > 1))
1161: newstate->accept_mb = 1;
1162: #endif /* RE_ENABLE_I18N */
1163: else if (type == OP_BACK_REF)
1164: newstate->has_backref = 1;
1165: else if (type == ANCHOR || node->constraint)
1166: newstate->has_constraint = 1;
1167: }
1168: err = register_state (dfa, newstate, hash);
1169: if (BE (err != REG_NOERROR, 0))
1170: {
1171: free_state (newstate);
1172: newstate = NULL;
1173: }
1174: return newstate;
1175: }
1176:
1177: /* Create the new state which is depend on the context CONTEXT.
1178: Return the new state if succeeded, otherwise return NULL. */
1179:
1180: static re_dfastate_t *
1181: create_cd_newstate (dfa, nodes, context, hash)
1182: re_dfa_t *dfa;
1183: const re_node_set *nodes;
1184: unsigned int context, hash;
1185: {
1186: int i, nctx_nodes = 0;
1187: reg_errcode_t err;
1188: re_dfastate_t *newstate;
1189:
1190: newstate = create_newstate_common (dfa, nodes, hash);
1191: if (BE (newstate == NULL, 0))
1192: return NULL;
1193: newstate->context = context;
1194: newstate->entrance_nodes = &newstate->nodes;
1195:
1196: for (i = 0 ; i < nodes->nelem ; i++)
1197: {
1198: unsigned int constraint = 0;
1199: re_token_t *node = dfa->nodes + nodes->elems[i];
1200: re_token_type_t type = node->type;
1201: if (node->constraint)
1202: constraint = node->constraint;
1203:
1204: if (type == CHARACTER && !constraint)
1205: continue;
1206: /* If the state has the halt node, the state is a halt state. */
1207: else if (type == END_OF_RE)
1208: newstate->halt = 1;
1209: #ifdef RE_ENABLE_I18N
1210: else if (type == COMPLEX_BRACKET
1211: || (type == OP_PERIOD && MB_CUR_MAX > 1))
1212: newstate->accept_mb = 1;
1213: #endif /* RE_ENABLE_I18N */
1214: else if (type == OP_BACK_REF)
1215: newstate->has_backref = 1;
1216: else if (type == ANCHOR)
1217: constraint = node->opr.ctx_type;
1218:
1219: if (constraint)
1220: {
1221: if (newstate->entrance_nodes == &newstate->nodes)
1222: {
1223: newstate->entrance_nodes = re_malloc (re_node_set, 1);
1224: if (BE (newstate->entrance_nodes == NULL, 0))
1225: {
1226: free_state (newstate);
1227: return NULL;
1228: }
1229: re_node_set_init_copy (newstate->entrance_nodes, nodes);
1230: nctx_nodes = 0;
1231: newstate->has_constraint = 1;
1232: }
1233:
1234: if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1235: {
1236: re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1237: ++nctx_nodes;
1238: }
1239: }
1240: }
1241: err = register_state (dfa, newstate, hash);
1242: if (BE (err != REG_NOERROR, 0))
1243: {
1244: free_state (newstate);
1245: newstate = NULL;
1246: }
1247: return newstate;
1248: }
1249:
1250: static void
1251: free_state (state)
1252: re_dfastate_t *state;
1253: {
1254: if (state->entrance_nodes != &state->nodes)
1255: {
1256: re_node_set_free (state->entrance_nodes);
1257: re_free (state->entrance_nodes);
1258: }
1259: re_node_set_free (&state->nodes);
1260: re_free (state->trtable);
1261: re_free (state->trtable_search);
1262: re_free (state);
1263: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to regex_internal.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / smartmontools / regex