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 |
|
5 |
{ |
44 |
|
|
int i, ich, newlen, cclp, ccls, cclmec; |
45 |
|
|
|
46 |
✓✓ |
49 |
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 |
|
44 |
newlen = 0; |
56 |
|
44 |
cclp = cclmap[i]; |
57 |
|
|
|
58 |
✓✓ |
469 |
for (ccls = 0; ccls < ccllen[i]; ++ccls) { |
59 |
|
425 |
ich = ccltbl[cclp + ccls]; |
60 |
|
425 |
cclmec = ecgroup[ich]; |
61 |
|
|
|
62 |
✓✓ |
425 |
if (cclmec > 0) { |
63 |
|
220 |
ccltbl[cclp + newlen] = cclmec; |
64 |
|
220 |
++newlen; |
65 |
|
|
} |
66 |
|
|
} |
67 |
|
|
|
68 |
|
44 |
ccllen[i] = newlen; |
69 |
|
|
} |
70 |
|
5 |
} |
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 |
|
10 |
{ |
84 |
|
|
int i, j, numcl; |
85 |
|
|
|
86 |
|
10 |
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 |
✓✓ |
1436 |
for (i = 1; i <= num; ++i) |
94 |
✓✓ |
1426 |
if (bck[i] == NIL) { |
95 |
|
164 |
bck[i] = ++numcl; |
96 |
✓✓ |
1426 |
for (j = fwd[i]; j != NIL; j = fwd[j]) |
97 |
|
1262 |
bck[j] = -numcl; |
98 |
|
|
} |
99 |
|
10 |
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 |
|
1402 |
{ |
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 |
|
1402 |
cclp = 0; |
131 |
|
|
|
132 |
✓✓ |
4953 |
while (cclp < lenccl) { |
133 |
|
2149 |
cclm = ccls[cclp]; |
134 |
|
|
|
135 |
✗✓ |
2149 |
if (NUL_mapping && cclm == 0) |
136 |
|
|
cclm = NUL_mapping; |
137 |
|
|
|
138 |
|
2149 |
oldec = bck[cclm]; |
139 |
|
2149 |
newec = cclm; |
140 |
|
|
|
141 |
|
2149 |
j = cclp + 1; |
142 |
|
|
|
143 |
✓✓ |
58044 |
for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) { |
144 |
|
|
/* look for the symbol in the character class */ |
145 |
✓✓ |
15273 |
for (; j < lenccl; ++j) { |
146 |
|
|
int ccl_char; |
147 |
|
|
|
148 |
✓✓✗✓
|
49442 |
if (NUL_mapping && ccls[j] == 0) |
149 |
|
|
ccl_char = NUL_mapping; |
150 |
|
|
else |
151 |
|
49442 |
ccl_char = ccls[j]; |
152 |
|
|
|
153 |
✓✓ |
49442 |
if (ccl_char > i) |
154 |
|
20127 |
break; |
155 |
|
|
|
156 |
✓✓✓✗
|
29315 |
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 |
|
14042 |
bck[i] = newec; |
165 |
|
14042 |
fwd[newec] = i; |
166 |
|
14042 |
newec = i; |
167 |
|
|
/* Set flag so we don't reprocess. */ |
168 |
|
14042 |
cclflags[j] = 1; |
169 |
|
|
|
170 |
|
|
/* Get next equivalence class member. */ |
171 |
|
|
/* continue 2 */ |
172 |
|
14042 |
goto next_pt; |
173 |
|
|
} |
174 |
|
|
} |
175 |
|
|
|
176 |
|
|
/* |
177 |
|
|
* Symbol isn't in character class. Put it in the |
178 |
|
|
* old equivalence class. |
179 |
|
|
*/ |
180 |
|
|
|
181 |
|
41853 |
bck[i] = oldec; |
182 |
|
|
|
183 |
✓✓ |
41853 |
if (oldec != NIL) |
184 |
|
41830 |
fwd[oldec] = i; |
185 |
|
|
|
186 |
|
41853 |
oldec = i; |
187 |
|
|
|
188 |
|
55895 |
next_pt: ; |
189 |
|
|
} |
190 |
|
|
|
191 |
✓✓✓✓
|
2149 |
if (bck[cclm] != NIL || oldec != bck[cclm]) { |
192 |
|
1325 |
bck[cclm] = NIL; |
193 |
|
1325 |
fwd[oldec] = NIL; |
194 |
|
|
} |
195 |
|
2149 |
fwd[newec] = NIL; |
196 |
|
|
|
197 |
|
|
/* Find next ccl member to process. */ |
198 |
|
|
|
199 |
✓✓ |
16191 |
for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) { |
200 |
|
|
/* Reset "doesn't need processing" flag. */ |
201 |
|
14042 |
cclflags[cclp] = 0; |
202 |
|
|
} |
203 |
|
|
} |
204 |
|
1402 |
} |
205 |
|
|
|
206 |
|
|
|
207 |
|
|
/* mkechar - create equivalence class for single character */ |
208 |
|
|
|
209 |
|
|
void |
210 |
|
|
mkechar(int tch, int *fwd, int *bck) |
211 |
|
4766 |
{ |
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 |
✓✓ |
4766 |
if (fwd[tch] != NIL) |
218 |
|
1624 |
bck[fwd[tch]] = bck[tch]; |
219 |
|
|
|
220 |
✓✓ |
4766 |
if (bck[tch] != NIL) |
221 |
|
2292 |
fwd[bck[tch]] = fwd[tch]; |
222 |
|
|
|
223 |
|
4766 |
fwd[tch] = NIL; |
224 |
|
4766 |
bck[tch] = NIL; |
225 |
|
4766 |
} |