Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/lex/ecs.c	Lines:	53	55	96.4 %
Date:	2017-11-13	Branches:	44	50	88.0 %


/*	$OpenBSD: ecs.c,v 1.9 2015/11/20 18:54:49 tedu Exp $	*/

/* ecs - equivalence class routines */

/*  Copyright (c) 1990 The Regents of the University of California. */
/*  All rights reserved. */

/*  This code is derived from software contributed to Berkeley by */
/*  Vern Paxson. */

/*  The United States Government has rights in this work pursuant */
/*  to contract no. DE-AC03-76SF00098 between the United States */
/*  Department of Energy and the University of California. */

/* This file is part of flex */

/*  Redistribution and use in source and binary forms, with or without */
/*  modification, are permitted provided that the following conditions */
/*  are met: */

/*  1. Redistributions of source code must retain the above copyright */
/*     notice, this list of conditions and the following disclaimer. */
/*  2. Redistributions in binary form must reproduce the above copyright */
/*     notice, this list of conditions and the following disclaimer in the */
/*     documentation and/or other materials provided with the distribution. */

/*  Neither the name of the University nor the names of its contributors */
/*  may be used to endorse or promote products derived from this software */
/*  without specific prior written permission. */

/*  THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */
/*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */
/*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
/*  PURPOSE. */


#include "flexdef.h"

/* ccl2ecl - convert character classes to set of equivalence classes */

void
ccl2ecl(void)
{
	int i, ich, newlen, cclp, ccls, cclmec;

	for (i = 1; i <= lastccl; ++i) {
		/*
		 * We loop through each character class, and for each
		 * character in the class, add the character's equivalence
		 * class to the new "character" class we are creating.  Thus
		 * when we are all done, character classes will really
		 * consist of collections of equivalence classes
		 */

		newlen = 0;
		cclp = cclmap[i];

		for (ccls = 0; ccls < ccllen[i]; ++ccls) {
			ich = ccltbl[cclp + ccls];
			cclmec = ecgroup[ich];

			if (cclmec > 0) {
				ccltbl[cclp + newlen] = cclmec;
				++newlen;
			}
		}

		ccllen[i] = newlen;
	}
}


/* cre8ecs - associate equivalence class numbers with class members
 *
 * fwd is the forward linked-list of equivalence class members.  bck
 * is the backward linked-list, and num is the number of class members.
 *
 * Returned is the number of classes.
 */

int
cre8ecs(int *fwd, int *bck, int num)
{
	int i, j, numcl;

	numcl = 0;

	/*
	 * Create equivalence class numbers.  From now on, ABS( bck(x) ) is
	 * the equivalence class number for object x.  If bck(x) is positive,
	 * then x is the representative of its equivalence class.
	 */
	for (i = 1; i <= num; ++i)
		if (bck[i] == NIL) {
			bck[i] = ++numcl;
			for (j = fwd[i]; j != NIL; j = fwd[j])
				bck[j] = -numcl;
		}
	return numcl;
}


/* mkeccl - update equivalence classes based on character class xtions
 *
 * synopsis
 *    u_char ccls[];
 *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 *    void mkeccl( u_char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
 *			int llsiz, int NUL_mapping );
 *
 * ccls contains the elements of the character class, lenccl is the
 * number of elements in the ccl, fwd is the forward link-list of equivalent
 * characters, bck is the backward link-list, and llsiz size of the link-list.
 *
 * NUL_mapping is the value which NUL (0) should be mapped to.
 */

void
mkeccl(u_char *ccls, int lenccl, int *fwd, int *bck, int llsiz, int NUL_mapping)
{
	int cclp, oldec, newec;
	int cclm, i, j;
	static unsigned char cclflags[CSIZE];	/* initialized to all '\0' */

	/*
	 * Note that it doesn't matter whether or not the character class is
	 * negated.  The same results will be obtained in either case.
	 */

	cclp = 0;

	while (cclp < lenccl) {
		cclm = ccls[cclp];

		if (NUL_mapping && cclm == 0)
			cclm = NUL_mapping;

		oldec = bck[cclm];
		newec = cclm;

		j = cclp + 1;

		for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) {
			/* look for the symbol in the character class */
			for (; j < lenccl; ++j) {
				int ccl_char;

				if (NUL_mapping && ccls[j] == 0)
					ccl_char = NUL_mapping;
				else
					ccl_char = ccls[j];

				if (ccl_char > i)
					break;

				if (ccl_char == i && !cclflags[j]) {
					/*
					 * We found an old companion of cclm
					 * in the ccl.  Link it into the new
					 * equivalence class and flag it as
					 * having been processed.
					 */

					bck[i] = newec;
					fwd[newec] = i;
					newec = i;
					/* Set flag so we don't reprocess. */
					cclflags[j] = 1;

					/* Get next equivalence class member. */
					/* continue 2 */
					goto next_pt;
				}
			}

			/*
			 * Symbol isn't in character class.  Put it in the
			 * old equivalence class.
			 */

			bck[i] = oldec;

			if (oldec != NIL)
				fwd[oldec] = i;

			oldec = i;

	next_pt:	;
		}

		if (bck[cclm] != NIL || oldec != bck[cclm]) {
			bck[cclm] = NIL;
			fwd[oldec] = NIL;
		}
		fwd[newec] = NIL;

		/* Find next ccl member to process. */

		for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) {
			/* Reset "doesn't need processing" flag. */
			cclflags[cclp] = 0;
		}
	}
}


/* mkechar - create equivalence class for single character */

void
mkechar(int tch, int *fwd, int *bck)
{
	/*
	 * If until now the character has been a proper subset of an
	 * equivalence class, break it away to create a new ec
	 */

	if (fwd[tch] != NIL)
		bck[fwd[tch]] = bck[tch];

	if (bck[tch] != NIL)
		fwd[bck[tch]] = fwd[tch];

	fwd[tch] = NIL;
	bck[tch] = NIL;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: ecs.c,v 1.9 2015/11/20 18:54:49 tedu Exp $ */
2
3			/* ecs - equivalence class routines */
4
5			/* Copyright (c) 1990 The Regents of the University of California. */
6			/* All rights reserved. */
7
8			/* This code is derived from software contributed to Berkeley by */
9			/* Vern Paxson. */
10
11			/* The United States Government has rights in this work pursuant */
12			/* to contract no. DE-AC03-76SF00098 between the United States */
13			/* Department of Energy and the University of California. */
14
15			/* This file is part of flex */
16
17			/* Redistribution and use in source and binary forms, with or without */
18			/* modification, are permitted provided that the following conditions */
19			/* are met: */
20
21			/* 1. Redistributions of source code must retain the above copyright */
22			/* notice, this list of conditions and the following disclaimer. */
23			/* 2. Redistributions in binary form must reproduce the above copyright */
24			/* notice, this list of conditions and the following disclaimer in the */
25			/* documentation and/or other materials provided with the distribution. */
26
27			/* Neither the name of the University nor the names of its contributors */
28			/* may be used to endorse or promote products derived from this software */
29			/* without specific prior written permission. */
30
31			/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */
32			/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */
33			/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
34			/* PURPOSE. */
35
36
37			#include "flexdef.h"
38
39			/* ccl2ecl - convert character classes to set of equivalence classes */
40
41			void
42			ccl2ecl(void)
43			{
44			int i, ich, newlen, cclp, ccls, cclmec;
45
46	✓✓	4930	for (i = 1; i <= lastccl; ++i) {
47			/*
48			* We loop through each character class, and for each
49			* character in the class, add the character's equivalence
50			* class to the new "character" class we are creating. Thus
51			* when we are all done, character classes will really
52			* consist of collections of equivalence classes
53			*/
54
55			newlen = 0;
56		2462	cclp = cclmap[i];
57
58	✓✓	108960	for (ccls = 0; ccls < ccllen[i]; ++ccls) {
59		52018	ich = ccltbl[cclp + ccls];
60		52018	cclmec = ecgroup[ich];
61
62	✓✓	52018	if (cclmec > 0) {
63		33184	ccltbl[cclp + newlen] = cclmec;
64		33184	++newlen;
65		33184	}
66			}
67
68		2462	ccllen[i] = newlen;
69			}
70		2	}
71
72
73			/* cre8ecs - associate equivalence class numbers with class members
74			*
75			* fwd is the forward linked-list of equivalence class members. bck
76			* is the backward linked-list, and num is the number of class members.
77			*
78			* Returned is the number of classes.
79			*/
80
81			int
82			cre8ecs(int fwd, int bck, int num)
83			{
84			int i, j, numcl;
85
86			numcl = 0;
87
88			/*
89			* Create equivalence class numbers. From now on, ABS( bck(x) ) is
90			* the equivalence class number for object x. If bck(x) is positive,
91			* then x is the representative of its equivalence class.
92			*/
93	✓✓	1240	for (i = 1; i <= num; ++i)
94	✓✓	614	if (bck[i] == NIL) {
95		118	bck[i] = ++numcl;
96	✓✓	1228	for (j = fwd[i]; j != NIL; j = fwd[j])
97		496	bck[j] = -numcl;
98			}
99		4	return numcl;
100			}
101
102
103			/* mkeccl - update equivalence classes based on character class xtions
104			*
105			* synopsis
106			* u_char ccls[];
107			* int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
108			* void mkeccl( u_char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
109			* int llsiz, int NUL_mapping );
110			*
111			* ccls contains the elements of the character class, lenccl is the
112			* number of elements in the ccl, fwd is the forward link-list of equivalent
113			* characters, bck is the backward link-list, and llsiz size of the link-list.
114			*
115			* NUL_mapping is the value which NUL (0) should be mapped to.
116			*/
117
118			void
119			mkeccl(u_char ccls, int lenccl, int fwd, int *bck, int llsiz, int NUL_mapping)
120			{
121			int cclp, oldec, newec;
122			int cclm, i, j;
123			static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
124
125			/*
126			* Note that it doesn't matter whether or not the character class is
127			* negated. The same results will be obtained in either case.
128			*/
129
130			cclp = 0;
131
132	✓✓	169232	while (cclp < lenccl) {
133		56674	cclm = ccls[cclp];
134
135	✗✓	56674	if (NUL_mapping && cclm == 0)
136			cclm = NUL_mapping;
137
138		56674	oldec = bck[cclm];
139			newec = cclm;
140
141		56674	j = cclp + 1;
142
143	✓✓✓✗	1099292	for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) {
144			/* look for the symbol in the character class */
145	✓✓	1136476	for (; j < lenccl; ++j) {
146			int ccl_char;
147
148	✓✓✗✓	994684	if (NUL_mapping && ccls[j] == 0)
149			ccl_char = NUL_mapping;
150			else
151		506998	ccl_char = ccls[j];
152
153	✓✓	506998	if (ccl_char > i)
154		17160	break;
155
156	✓✓✓✗	740086	if (ccl_char == i && !cclflags[j]) {
157			/*
158			* We found an old companion of cclm
159			* in the ccl. Link it into the new
160			* equivalence class and flag it as
161			* having been processed.
162			*/
163
164		250248	bck[i] = newec;
165		250248	fwd[newec] = i;
166			newec = i;
167			/* Set flag so we don't reprocess. */
168		250248	cclflags[j] = 1;
169
170			/* Get next equivalence class member. */
171			/* continue 2 */
172		250248	goto next_pt;
173			}
174	✓✓✓✗	239590	}
175
176			/*
177			* Symbol isn't in character class. Put it in the
178			* old equivalence class.
179			*/
180
181		78400	bck[i] = oldec;
182
183	✓✓	78400	if (oldec != NIL)
184		78034	fwd[oldec] = i;
185
186		78400	oldec = i;
187
188			next_pt: ;
189			}
190
191	✓✓✓✓	109956	if (bck[cclm] != NIL \|\| oldec != bck[cclm]) {
192		3758	bck[cclm] = NIL;
193		3758	fwd[oldec] = NIL;
194		3758	}
195		56674	fwd[newec] = NIL;
196
197			/* Find next ccl member to process. */
198
199	✓✓✓✗	864092	for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) {
200			/* Reset "doesn't need processing" flag. */
201		250248	cclflags[cclp] = 0;
202			}
203			}
204		18628	}
205
206
207			/* mkechar - create equivalence class for single character */
208
209			void
210			mkechar(int tch, int fwd, int bck)
211			{
212			/*
213			* If until now the character has been a proper subset of an
214			* equivalence class, break it away to create a new ec
215			*/
216
217	✓✓	23920	if (fwd[tch] != NIL)
218		3294	bck[fwd[tch]] = bck[tch];
219
220	✓✓	11960	if (bck[tch] != NIL)
221		3078	fwd[bck[tch]] = fwd[tch];
222
223		11960	fwd[tch] = NIL;
224		11960	bck[tch] = NIL;
225		11960	}