1 /* ecs - equivalence class routines */
2
3 /*-
4 * Copyright (c) 1990 The Regents of the University of California.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Vern Paxson.
9 *
10 * The United States Government has rights in this work pursuant
11 * to contract no. DE-AC03-76SF00098 between the United States
12 * Department of Energy and the University of California.
13 *
14 * Redistribution and use in source and binary forms with or without
15 * modification are permitted provided that: (1) source distributions retain
16 * this entire copyright notice and comment, and (2) distributions including
17 * binaries display the following acknowledgement: ``This product includes
18 * software developed by the University of California, Berkeley and its
19 * contributors'' in the documentation or other materials provided with the
20 * distribution and in all advertising materials mentioning features or use
21 * of this software. Neither the name of the University nor the names of
22 * its contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27 */
28
29 /* $Header: /home/daffy/u0/vern/flex/RCS/ecs.c,v 2.9 93/12/07 10:18:20 vern Exp $ */
30
31 #include "flexdef.h"
32
33 /* ccl2ecl - convert character classes to set of equivalence classes */
34
ccl2ecl()35 void ccl2ecl()
36 {
37 int i, ich, newlen, cclp, ccls, cclmec;
38
39 for ( i = 1; i <= lastccl; ++i )
40 {
41 /* We loop through each character class, and for each character
42 * in the class, add the character's equivalence class to the
43 * new "character" class we are creating. Thus when we are all
44 * done, character classes will really consist of collections
45 * of equivalence classes
46 */
47
48 newlen = 0;
49 cclp = cclmap[i];
50
51 for ( ccls = 0; ccls < ccllen[i]; ++ccls )
52 {
53 ich = ccltbl[cclp + ccls];
54 cclmec = ecgroup[ich];
55
56 if ( cclmec > 0 )
57 {
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 {
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 * Char ccls[];
104 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
105 * void mkeccl( 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
mkeccl(ccls,lenccl,fwd,bck,llsiz,NUL_mapping)115 void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
116 Char ccls[];
117 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
118 {
119 int cclp, oldec, newec;
120 int cclm, i, j;
121 static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
122
123 /* Note that it doesn't matter whether or not the character class is
124 * negated. The same results will be obtained in either case.
125 */
126
127 cclp = 0;
128
129 while ( cclp < lenccl )
130 {
131 cclm = ccls[cclp];
132
133 if ( NUL_mapping && cclm == 0 )
134 cclm = NUL_mapping;
135
136 oldec = bck[cclm];
137 newec = cclm;
138
139 j = cclp + 1;
140
141 for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
142 { /* look for the symbol in the character class */
143 for ( ; j < lenccl; ++j )
144 {
145 register int ccl_char;
146
147 if ( NUL_mapping && ccls[j] == 0 )
148 ccl_char = NUL_mapping;
149 else
150 ccl_char = ccls[j];
151
152 if ( ccl_char > i )
153 break;
154
155 if ( ccl_char == i && ! cclflags[j] )
156 {
157 /* We found an old companion of cclm
158 * in the ccl. Link it into the new
159 * equivalence class and flag it as
160 * having been processed.
161 */
162
163 bck[i] = newec;
164 fwd[newec] = i;
165 newec = i;
166 /* Set flag so we don't reprocess. */
167 cclflags[j] = 1;
168
169 /* Get next equivalence class member. */
170 /* continue 2 */
171 goto next_pt;
172 }
173 }
174
175 /* Symbol isn't in character class. Put it in the old
176 * equivalence class.
177 */
178
179 bck[i] = oldec;
180
181 if ( oldec != NIL )
182 fwd[oldec] = i;
183
184 oldec = i;
185
186 next_pt: ;
187 }
188
189 if ( bck[cclm] != NIL || oldec != bck[cclm] )
190 {
191 bck[cclm] = NIL;
192 fwd[oldec] = NIL;
193 }
194
195 fwd[newec] = NIL;
196
197 /* Find next ccl member to process. */
198
199 for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
200 {
201 /* Reset "doesn't need processing" flag. */
202 cclflags[cclp] = 0;
203 }
204 }
205 }
206
207
208 /* mkechar - create equivalence class for single character */
209
mkechar(tch,fwd,bck)210 void mkechar( tch, fwd, bck )
211 int tch, fwd[], bck[];
212 {
213 /* If until now the character has been a proper subset of
214 * an equivalence class, break it away to create a new ec
215 */
216
217 if ( fwd[tch] != NIL )
218 bck[fwd[tch]] = bck[tch];
219
220 if ( bck[tch] != NIL )
221 fwd[bck[tch]] = fwd[tch];
222
223 fwd[tch] = NIL;
224 bck[tch] = NIL;
225 }
226