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 #include "flexdef.h"
34 __RCSID("$NetBSD: ecs.c,v 1.3 2014/10/30 18:44:05 christos Exp $");
35
36 /* ccl2ecl - convert character classes to set of equivalence classes */
37
ccl2ecl()38 void ccl2ecl ()
39 {
40 int i, ich, newlen, cclp, ccls, cclmec;
41
42 for (i = 1; i <= lastccl; ++i) {
43 /* We loop through each character class, and for each character
44 * in the class, add the character's equivalence class to the
45 * new "character" class we are creating. Thus when we are all
46 * done, character classes will really consist of collections
47 * of equivalence classes
48 */
49
50 newlen = 0;
51 cclp = cclmap[i];
52
53 for (ccls = 0; ccls < ccllen[i]; ++ccls) {
54 ich = ccltbl[cclp + ccls];
55 cclmec = ecgroup[ich];
56
57 if (cclmec > 0) {
58 ccltbl[cclp + newlen] = cclmec;
59 ++newlen;
60 }
61 }
62
63 ccllen[i] = newlen;
64 }
65 }
66
67
68 /* cre8ecs - associate equivalence class numbers with class members
69 *
70 * fwd is the forward linked-list of equivalence class members. bck
71 * is the backward linked-list, and num is the number of class members.
72 *
73 * Returned is the number of classes.
74 */
75
cre8ecs(fwd,bck,num)76 int cre8ecs (fwd, bck, num)
77 int fwd[], bck[], num;
78 {
79 int i, j, numcl;
80
81 numcl = 0;
82
83 /* Create equivalence class numbers. From now on, ABS( bck(x) )
84 * is the equivalence class number for object x. If bck(x)
85 * is positive, then x is the representative of its equivalence
86 * class.
87 */
88 for (i = 1; i <= num; ++i)
89 if (bck[i] == NIL) {
90 bck[i] = ++numcl;
91 for (j = fwd[i]; j != NIL; j = fwd[j])
92 bck[j] = -numcl;
93 }
94
95 return numcl;
96 }
97
98
99 /* mkeccl - update equivalence classes based on character class xtions
100 *
101 * synopsis
102 * Char ccls[];
103 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
104 * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
105 * int llsiz, int NUL_mapping );
106 *
107 * ccls contains the elements of the character class, lenccl is the
108 * number of elements in the ccl, fwd is the forward link-list of equivalent
109 * characters, bck is the backward link-list, and llsiz size of the link-list.
110 *
111 * NUL_mapping is the value which NUL (0) should be mapped to.
112 */
113
mkeccl(ccls,lenccl,fwd,bck,llsiz,NUL_mapping)114 void mkeccl (ccls, lenccl, fwd, bck, llsiz, NUL_mapping)
115 Char ccls[];
116 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
117 {
118 int cclp, oldec, newec;
119 int cclm, i, j;
120 static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
121
122 /* Note that it doesn't matter whether or not the character class is
123 * negated. The same results will be obtained in either case.
124 */
125
126 cclp = 0;
127
128 while (cclp < lenccl) {
129 cclm = ccls[cclp];
130
131 if (NUL_mapping && cclm == 0)
132 cclm = NUL_mapping;
133
134 oldec = bck[cclm];
135 newec = cclm;
136
137 j = cclp + 1;
138
139 for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) { /* look for the symbol in the character class */
140 for (; j < lenccl; ++j) {
141 register int ccl_char;
142
143 if (NUL_mapping && ccls[j] == 0)
144 ccl_char = NUL_mapping;
145 else
146 ccl_char = ccls[j];
147
148 if (ccl_char > i)
149 break;
150
151 if (ccl_char == i && !cclflags[j]) {
152 /* We found an old companion of cclm
153 * in the ccl. Link it into the new
154 * equivalence class and flag it as
155 * having been processed.
156 */
157
158 bck[i] = newec;
159 fwd[newec] = i;
160 newec = i;
161 /* Set flag so we don't reprocess. */
162 cclflags[j] = 1;
163
164 /* Get next equivalence class member. */
165 /* continue 2 */
166 goto next_pt;
167 }
168 }
169
170 /* Symbol isn't in character class. Put it in the old
171 * equivalence class.
172 */
173
174 bck[i] = oldec;
175
176 if (oldec != NIL)
177 fwd[oldec] = i;
178
179 oldec = i;
180
181 next_pt:;
182 }
183
184 if (bck[cclm] != NIL || oldec != bck[cclm]) {
185 bck[cclm] = NIL;
186 fwd[oldec] = NIL;
187 }
188
189 fwd[newec] = NIL;
190
191 /* Find next ccl member to process. */
192
193 for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) {
194 /* Reset "doesn't need processing" flag. */
195 cclflags[cclp] = 0;
196 }
197 }
198 }
199
200
201 /* mkechar - create equivalence class for single character */
202
mkechar(tch,fwd,bck)203 void mkechar (tch, fwd, bck)
204 int tch, fwd[], bck[];
205 {
206 /* If until now the character has been a proper subset of
207 * an equivalence class, break it away to create a new ec
208 */
209
210 if (fwd[tch] != NIL)
211 bck[fwd[tch]] = bck[tch];
212
213 if (bck[tch] != NIL)
214 fwd[bck[tch]] = fwd[tch];
215
216 fwd[tch] = NIL;
217 bck[tch] = NIL;
218 }
219