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