initial import of NetBSD tree

1 files changed, 225 insertions, 0 deletions

diff --git a/usr.bin/lex/ecs.c b/usr.bin/lex/ecs.c
new file mode 100644
index 00000000000..5379c6272b7
--- /dev/null
+++ b/usr.bin/lex/ecs.c
@@ -0,0 +1,225 @@
+/* ecs - equivalence class routines */
+
+/*-
+ * Copyright (c) 1990 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Vern Paxson.
+ * 
+ * The United States Government has rights in this work pursuant
+ * to contract no. DE-AC03-76SF00098 between the United States
+ * Department of Energy and the University of California.
+ *
+ * Redistribution and use in source and binary forms are permitted provided
+ * that: (1) source distributions retain this entire copyright notice and
+ * comment, and (2) distributions including binaries display the following
+ * acknowledgement:  ``This product includes software developed by the
+ * University of California, Berkeley and its contributors'' in the
+ * documentation or other materials provided with the distribution and in
+ * all advertising materials mentioning features or use of this software.
+ * Neither the name of the University nor the names of its contributors may
+ * be used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ */
+
+/* $Header: /cvs/OpenBSD/src/usr.bin/lex/ecs.c,v 1.1 1995/10/18 08:45:29 deraadt Exp $ */
+
+#include "flexdef.h"
+
+/* ccl2ecl - convert character classes to set of equivalence classes */
+
+void ccl2ecl()
+	{
+	int i, ich, newlen, cclp, ccls, cclmec;
+
+	for ( i = 1; i <= lastccl; ++i )
+		{
+		/* We loop through each character class, and for each character
+		 * in the class, add the character's equivalence class to the
+		 * new "character" class we are creating.  Thus when we are all
+		 * done, character classes will really consist of collections
+		 * of equivalence classes
+		 */
+
+		newlen = 0;
+		cclp = cclmap[i];
+
+		for ( ccls = 0; ccls < ccllen[i]; ++ccls )
+			{
+			ich = ccltbl[cclp + ccls];
+			cclmec = ecgroup[ich];
+
+			if ( cclmec > 0 )
+				{
+				ccltbl[cclp + newlen] = cclmec;
+				++newlen;
+				}
+			}
+
+		ccllen[i] = newlen;
+		}
+	}
+
+
+/* cre8ecs - associate equivalence class numbers with class members
+ *
+ * fwd is the forward linked-list of equivalence class members.  bck
+ * is the backward linked-list, and num is the number of class members.
+ *
+ * Returned is the number of classes.
+ */
+
+int cre8ecs( fwd, bck, num )
+int fwd[], bck[], num;
+	{
+	int i, j, numcl;
+
+	numcl = 0;
+
+	/* Create equivalence class numbers.  From now on, ABS( bck(x) )
+	 * is the equivalence class number for object x.  If bck(x)
+	 * is positive, then x is the representative of its equivalence
+	 * class.
+	 */
+	for ( i = 1; i <= num; ++i )
+		if ( bck[i] == NIL )
+			{
+			bck[i] = ++numcl;
+			for ( j = fwd[i]; j != NIL; j = fwd[j] )
+				bck[j] = -numcl;
+			}
+
+	return numcl;
+	}
+
+
+/* mkeccl - update equivalence classes based on character class xtions
+ *
+ * synopsis
+ *    Char ccls[];
+ *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
+ *    void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
+ *			int llsiz, int NUL_mapping );
+ *
+ * ccls contains the elements of the character class, lenccl is the
+ * number of elements in the ccl, fwd is the forward link-list of equivalent
+ * characters, bck is the backward link-list, and llsiz size of the link-list.
+ *
+ * NUL_mapping is the value which NUL (0) should be mapped to.
+ */
+
+void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
+Char ccls[];
+int lenccl, fwd[], bck[], llsiz, NUL_mapping;
+	{
+	int cclp, oldec, newec;
+	int cclm, i, j;
+	static unsigned char cclflags[CSIZE];	/* initialized to all '\0' */
+
+	/* Note that it doesn't matter whether or not the character class is
+	 * negated.  The same results will be obtained in either case.
+	 */
+
+	cclp = 0;
+
+	while ( cclp < lenccl )
+		{
+		cclm = ccls[cclp];
+
+		if ( NUL_mapping && cclm == 0 )
+			cclm = NUL_mapping;
+
+		oldec = bck[cclm];
+		newec = cclm;
+
+		j = cclp + 1;
+
+		for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
+			{ /* look for the symbol in the character class */
+			for ( ; j < lenccl; ++j )
+				{
+				register int ccl_char;
+
+				if ( NUL_mapping && ccls[j] == 0 )
+					ccl_char = NUL_mapping;
+				else
+					ccl_char = ccls[j];
+
+				if ( ccl_char > i )
+					break;
+
+				if ( ccl_char == i && ! cclflags[j] )
+					{
+					/* We found an old companion of cclm
+					 * in the ccl.  Link it into the new
+					 * equivalence class and flag it as
+					 * having been processed.
+					 */
+
+					bck[i] = newec;
+					fwd[newec] = i;
+					newec = i;
+					/* Set flag so we don't reprocess. */
+					cclflags[j] = 1;
+
+					/* Get next equivalence class member. */
+					/* continue 2 */
+					goto next_pt;
+					}
+				}
+
+			/* Symbol isn't in character class.  Put it in the old
+			 * equivalence class.
+			 */
+
+			bck[i] = oldec;
+
+			if ( oldec != NIL )
+				fwd[oldec] = i;
+
+			oldec = i;
+
+			next_pt: ;
+			}
+
+		if ( bck[cclm] != NIL || oldec != bck[cclm] )
+			{
+			bck[cclm] = NIL;
+			fwd[oldec] = NIL;
+			}
+
+		fwd[newec] = NIL;
+
+		/* Find next ccl member to process. */
+
+		for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
+			{
+			/* Reset "doesn't need processing" flag. */
+			cclflags[cclp] = 0;
+			}
+		}
+	}
+
+
+/* mkechar - create equivalence class for single character */
+
+void mkechar( tch, fwd, bck )
+int tch, fwd[], bck[];
+	{
+	/* If until now the character has been a proper subset of
+	 * an equivalence class, break it away to create a new ec
+	 */
+
+	if ( fwd[tch] != NIL )
+		bck[fwd[tch]] = bck[tch];
+
+	if ( bck[tch] != NIL )
+		fwd[bck[tch]] = fwd[tch];
+
+	fwd[tch] = NIL;
+	bck[tch] = NIL;
+	}