src/regex/regc_cvec.c

/*
 * Utility functions for handling cvecs
 * This file is #included by regcomp.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.	All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $Header$
 *
 */

/*
 * newcvec - allocate a new cvec
 */
static struct cvec *
newcvec(int nchrs,				/* to hold this many chrs... */
		int nranges,			/* ... and this many ranges... */
		int nmcces)				/* ... and this many MCCEs */
{
	size_t		n;
	size_t		nc;
	struct cvec *cv;

	nc = (size_t) nchrs + (size_t) nmcces *(MAXMCCE + 1) + (size_t) nranges *2;

	n = sizeof(struct cvec) + (size_t) (nmcces - 1) * sizeof(chr *)
		+ nc * sizeof(chr);
	cv = (struct cvec *) MALLOC(n);
	if (cv == NULL)
		return NULL;
	cv->chrspace = nchrs;
	cv->chrs = (chr *) &cv->mcces[nmcces];		/* chrs just after MCCE
												 * ptrs */
	cv->mccespace = nmcces;
	cv->ranges = cv->chrs + nchrs + nmcces * (MAXMCCE + 1);
	cv->rangespace = nranges;
	return clearcvec(cv);
}

/*
 * clearcvec - clear a possibly-new cvec
 * Returns pointer as convenience.
 */
static struct cvec *
clearcvec(struct cvec * cv)
{
	int			i;

	assert(cv != NULL);
	cv->nchrs = 0;
	assert(cv->chrs == (chr *) &cv->mcces[cv->mccespace]);
	cv->nmcces = 0;
	cv->nmccechrs = 0;
	cv->nranges = 0;
	for (i = 0; i < cv->mccespace; i++)
		cv->mcces[i] = NULL;

	return cv;
}

/*
 * addchr - add a chr to a cvec
 */
static void
addchr(struct cvec * cv,		/* character vector */
	   chr c)					/* character to add */
{
	assert(cv->nchrs < cv->chrspace - cv->nmccechrs);
	cv->chrs[cv->nchrs++] = (chr) c;
}

/*
 * addrange - add a range to a cvec
 */
static void
addrange(struct cvec * cv,		/* character vector */
		 chr from,				/* first character of range */
		 chr to)				/* last character of range */
{
	assert(cv->nranges < cv->rangespace);
	cv->ranges[cv->nranges * 2] = (chr) from;
	cv->ranges[cv->nranges * 2 + 1] = (chr) to;
	cv->nranges++;
}

/*
 * addmcce - add an MCCE to a cvec
 */
static void
addmcce(struct cvec * cv,		/* character vector */
		chr *startp,			/* beginning of text */
		chr *endp)				/* just past end of text */
{
	int			len;
	int			i;
	chr		   *s;
	chr		   *d;

	if (startp == NULL && endp == NULL)
		return;
	len = endp - startp;
	assert(len > 0);
	assert(cv->nchrs + len < cv->chrspace - cv->nmccechrs);
	assert(cv->nmcces < cv->mccespace);
	d = &cv->chrs[cv->chrspace - cv->nmccechrs - len - 1];
	cv->mcces[cv->nmcces++] = d;
	for (s = startp, i = len; i > 0; s++, i--)
		*d++ = *s;
	*d++ = 0;					/* endmarker */
	assert(d == &cv->chrs[cv->chrspace - cv->nmccechrs]);
	cv->nmccechrs += len + 1;
}

/*
 * haschr - does a cvec contain this chr?
 */
static int						/* predicate */
haschr(struct cvec * cv,		/* character vector */
	   chr c)					/* character to test for */
{
	int			i;
	chr		   *p;

	for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
	{
		if (*p == c)
			return 1;
	}
	for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
	{
		if ((*p <= c) && (c <= *(p + 1)))
			return 1;
	}
	return 0;
}

/*
 * getcvec - get a cvec, remembering it as v->cv
 */
static struct cvec *
getcvec(struct vars * v,		/* context */
		int nchrs,				/* to hold this many chrs... */
		int nranges,			/* ... and this many ranges... */
		int nmcces)				/* ... and this many MCCEs */
{
	if (v->cv != NULL && nchrs <= v->cv->chrspace &&
		nranges <= v->cv->rangespace && nmcces <= v->cv->mccespace)
		return clearcvec(v->cv);

	if (v->cv != NULL)
		freecvec(v->cv);
	v->cv = newcvec(nchrs, nranges, nmcces);
	if (v->cv == NULL)
		ERR(REG_ESPACE);

	return v->cv;
}

/*
 * freecvec - free a cvec
 */
static void
freecvec(struct cvec * cv)
{
	FREE(cv);
}
Commit	Line	Data
	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	* $Header$
	32	*
	33	*/
	34
	35	/*
	36	* newcvec - allocate a new cvec
	37	*/
	38	static struct cvec *
	39	newcvec(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
	49	n = sizeof(struct cvec) + (size_t) (nmcces - 1) * sizeof(chr *)
	50	+ nc * sizeof(chr);
	51	cv = (struct cvec *) MALLOC(n);
	52	if (cv == NULL)
	53	return NULL;
	54	cv->chrspace = nchrs;
	55	cv->chrs = (chr ) &cv->mcces[nmcces]; / chrs just after MCCE
	56	* ptrs */
	57	cv->mccespace = nmcces;
	58	cv->ranges = cv->chrs + nchrs + nmcces * (MAXMCCE + 1);
	59	cv->rangespace = nranges;
	60	return clearcvec(cv);
	61	}
	62
	63	/*
	64	* clearcvec - clear a possibly-new cvec
	65	* Returns pointer as convenience.
	66	*/
	67	static struct cvec *
	68	clearcvec(struct cvec * cv)
	69	{
	70	int i;
	71
	72	assert(cv != NULL);
	73	cv->nchrs = 0;
	74	assert(cv->chrs == (chr *) &cv->mcces[cv->mccespace]);
	75	cv->nmcces = 0;
	76	cv->nmccechrs = 0;
	77	cv->nranges = 0;
	78	for (i = 0; i < cv->mccespace; i++)
	79	cv->mcces[i] = NULL;
	80
	81	return cv;
	82	}
	83
	84	/*
	85	* addchr - add a chr to a cvec
	86	*/
	87	static void
	88	addchr(struct cvec * cv, /* character vector */
	89	chr c) /* character to add */
	90	{
	91	assert(cv->nchrs < cv->chrspace - cv->nmccechrs);
	92	cv->chrs[cv->nchrs++] = (chr) c;
	93	}
	94
	95	/*
	96	* addrange - add a range to a cvec
	97	*/
	98	static void
	99	addrange(struct cvec * cv, /* character vector */
	100	chr from, /* first character of range */
	101	chr to) /* last character of range */
	102	{
	103	assert(cv->nranges < cv->rangespace);
	104	cv->ranges[cv->nranges * 2] = (chr) from;
	105	cv->ranges[cv->nranges * 2 + 1] = (chr) to;
	106	cv->nranges++;
	107	}
	108
	109	/*
	110	* addmcce - add an MCCE to a cvec
	111	*/
	112	static void
	113	addmcce(struct cvec * cv, /* character vector */
	114	chr startp, / beginning of text */
	115	chr endp) / just past end of text */
	116	{
	117	int len;
	118	int i;
	119	chr *s;
	120	chr *d;
	121
	122	if (startp == NULL && endp == NULL)
	123	return;
	124	len = endp - startp;
	125	assert(len > 0);
	126	assert(cv->nchrs + len < cv->chrspace - cv->nmccechrs);
	127	assert(cv->nmcces < cv->mccespace);
	128	d = &cv->chrs[cv->chrspace - cv->nmccechrs - len - 1];
	129	cv->mcces[cv->nmcces++] = d;
	130	for (s = startp, i = len; i > 0; s++, i--)
	131	d++ = s;
	132	d++ = 0; / endmarker */
	133	assert(d == &cv->chrs[cv->chrspace - cv->nmccechrs]);
	134	cv->nmccechrs += len + 1;
	135	}
	136
	137	/*
	138	* haschr - does a cvec contain this chr?
	139	*/
	140	static int /* predicate */
	141	haschr(struct cvec * cv, /* character vector */
	142	chr c) /* character to test for */
	143	{
	144	int i;
	145	chr *p;
	146
	147	for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
	148	{
	149	if (*p == c)
	150	return 1;
	151	}
	152	for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
	153	{
	154	if ((p <= c) && (c <= (p + 1)))
	155	return 1;
	156	}
	157	return 0;
	158	}
	159
	160	/*
	161	* getcvec - get a cvec, remembering it as v->cv
	162	*/
	163	static struct cvec *
	164	getcvec(struct vars * v, /* context */
	165	int nchrs, /* to hold this many chrs... */
	166	int nranges, /* ... and this many ranges... */
	167	int nmcces) /* ... and this many MCCEs */
	168	{
	169	if (v->cv != NULL && nchrs <= v->cv->chrspace &&
	170	nranges <= v->cv->rangespace && nmcces <= v->cv->mccespace)
	171	return clearcvec(v->cv);
	172
	173	if (v->cv != NULL)
	174	freecvec(v->cv);
	175	v->cv = newcvec(nchrs, nranges, nmcces);
	176	if (v->cv == NULL)
	177	ERR(REG_ESPACE);
	178
	179	return v->cv;
	180	}
	181
	182	/*
	183	* freecvec - free a cvec
	184	*/
	185	static void
	186	freecvec(struct cvec * cv)
	187	{
	188	FREE(cv);
	189	}