1/*
2 * Utility functions for handling cvecs
3 * This file is #included by regcomp.c.
4 *
5 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
6 *
7 * Development of this software was funded, in part, by Cray Research Inc.,
8 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
9 * Corporation, none of whom are responsible for the results.  The author
10 * thanks all of them.
11 *
12 * Redistribution and use in source and binary forms -- with or without
13 * modification -- are permitted for any purpose, provided that
14 * redistributions in source form retain this entire copyright notice and
15 * indicate the origin and nature of any modifications.
16 *
17 * I'd appreciate being given credit for this package in the documentation
18 * of software which uses it, but that is not a requirement.
19 *
20 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
21 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
22 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
23 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 *
31 */
32
33/*
34 - newcvec - allocate a new cvec
35 ^ static struct cvec *newcvec(int, int, int);
36 */
37static struct cvec *
38newcvec(nchrs, nranges, nmcces)
39    int nchrs;				/* to hold this many chrs... */
40    int nranges;			/* ... and this many ranges... */
41    int nmcces;				/* ... and this many MCCEs */
42{
43    size_t n;
44    size_t nc;
45    struct cvec *cv;
46
47    nc = (size_t)nchrs + (size_t)nmcces*(MAXMCCE+1) + (size_t)nranges*2;
48    n = sizeof(struct cvec) + (size_t)(nmcces-1)*sizeof(chr *)
49	    + nc*sizeof(chr);
50    cv = (struct cvec *)MALLOC(n);
51    if (cv == NULL) {
52	return NULL;
53    }
54    cv->chrspace = nchrs;
55    cv->chrs = (chr *)&cv->mcces[nmcces];	/* chrs just after MCCE ptrs */
56    cv->mccespace = nmcces;
57    cv->ranges = cv->chrs + nchrs + nmcces*(MAXMCCE+1);
58    cv->rangespace = nranges;
59    return clearcvec(cv);
60}
61
62/*
63 - clearcvec - clear a possibly-new cvec
64 * Returns pointer as convenience.
65 ^ static struct cvec *clearcvec(struct cvec *);
66 */
67static struct cvec *
68clearcvec(cv)
69    struct cvec *cv;			/* character vector */
70{
71    int i;
72
73    assert(cv != NULL);
74    cv->nchrs = 0;
75    assert(cv->chrs == (chr *)&cv->mcces[cv->mccespace]);
76    cv->nmcces = 0;
77    cv->nmccechrs = 0;
78    cv->nranges = 0;
79    for (i = 0; i < cv->mccespace; i++) {
80	cv->mcces[i] = NULL;
81    }
82
83    return cv;
84}
85
86/*
87 - addchr - add a chr to a cvec
88 ^ static VOID addchr(struct cvec *, pchr);
89 */
90static VOID
91addchr(cv, c)
92    struct cvec *cv;			/* character vector */
93    pchr c;				/* character to add */
94{
95    assert(cv->nchrs < cv->chrspace - cv->nmccechrs);
96    cv->chrs[cv->nchrs++] = (chr)c;
97}
98
99/*
100 - addrange - add a range to a cvec
101 ^ static VOID addrange(struct cvec *, pchr, pchr);
102 */
103static VOID
104addrange(cv, from, to)
105    struct cvec *cv;			/* character vector */
106    pchr from;				/* first character of range */
107    pchr to;				/* last character of range */
108{
109    assert(cv->nranges < cv->rangespace);
110    cv->ranges[cv->nranges*2] = (chr)from;
111    cv->ranges[cv->nranges*2 + 1] = (chr)to;
112    cv->nranges++;
113}
114
115/*
116 - addmcce - add an MCCE to a cvec
117 ^ static VOID addmcce(struct cvec *, chr *, chr *);
118 */
119static VOID
120addmcce(cv, startp, endp)
121    struct cvec *cv;			/* character vector */
122    chr *startp;			/* beginning of text */
123    chr *endp;				/* just past end of text */
124{
125    int len;
126    int i;
127    chr *s;
128    chr *d;
129
130    if (startp == NULL && endp == NULL) {
131	return;
132    }
133    len = endp - startp;
134    assert(len > 0);
135    assert(cv->nchrs + len < cv->chrspace - cv->nmccechrs);
136    assert(cv->nmcces < cv->mccespace);
137    d = &cv->chrs[cv->chrspace - cv->nmccechrs - len - 1];
138    cv->mcces[cv->nmcces++] = d;
139    for (s = startp, i = len; i > 0; s++, i--) {
140	*d++ = *s;
141    }
142    *d++ = 0;				/* endmarker */
143    assert(d == &cv->chrs[cv->chrspace - cv->nmccechrs]);
144    cv->nmccechrs += len + 1;
145}
146
147/*
148 - haschr - does a cvec contain this chr?
149 ^ static int haschr(struct cvec *, pchr);
150 */
151static int				/* predicate */
152haschr(cv, c)
153    struct cvec *cv;			/* character vector */
154    pchr c;				/* character to test for */
155{
156    int i;
157    chr *p;
158
159    for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) {
160	if (*p == c) {
161	    return 1;
162	}
163    }
164    for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) {
165	if ((*p <= c) && (c <= *(p+1))) {
166	    return 1;
167	}
168    }
169    return 0;
170}
171
172/*
173 - getcvec - get a cvec, remembering it as v->cv
174 ^ static struct cvec *getcvec(struct vars *, int, int, int);
175 */
176static struct cvec *
177getcvec(v, nchrs, nranges, nmcces)
178    struct vars *v;			/* context */
179    int nchrs;				/* to hold this many chrs... */
180    int nranges;			/* ... and this many ranges... */
181    int nmcces;				/* ... and this many MCCEs */
182{
183    if (v->cv != NULL && nchrs <= v->cv->chrspace &&
184	    nranges <= v->cv->rangespace && nmcces <= v->cv->mccespace) {
185	return clearcvec(v->cv);
186    }
187
188    if (v->cv != NULL) {
189	freecvec(v->cv);
190    }
191    v->cv = newcvec(nchrs, nranges, nmcces);
192    if (v->cv == NULL) {
193	ERR(REG_ESPACE);
194    }
195
196    return v->cv;
197}
198
199/*
200 - freecvec - free a cvec
201 ^ static VOID freecvec(struct cvec *);
202 */
203static VOID
204freecvec(cv)
205    struct cvec *cv;			/* character vector */
206{
207    FREE(cv);
208}
209