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