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 2017/01/02 17:45:27 christos Exp $");
35
36/* ccl2ecl - convert character classes to set of equivalence classes */
37
38void    ccl2ecl (void)
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				/* Note: range 1..256 is mapped to 1..255,0 */
59				ccltbl[cclp + newlen] = (unsigned char) cclmec;
60				++newlen;
61			}
62		}
63
64		ccllen[i] = newlen;
65	}
66}
67
68
69/* cre8ecs - associate equivalence class numbers with class members
70 *
71 * fwd is the forward linked-list of equivalence class members.  bck
72 * is the backward linked-list, and num is the number of class members.
73 *
74 * Returned is the number of classes.
75 */
76
77int     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
99/* mkeccl - update equivalence classes based on character class xtions
100 *
101 * synopsis
102 *    unsigned char ccls[];
103 *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
104 *    void mkeccl( unsigned 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
114void    mkeccl (unsigned char 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];
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] == 0)
142					ccl_char = NUL_mapping;
143				else
144					ccl_char = ccls[j];
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
199/* mkechar - create equivalence class for single character */
200
201void    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