fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

ecs.c (5710B)


      1 /*	$OpenBSD: ecs.c,v 1.6 2003/06/04 17:34:44 millert Exp $	*/
      2 
      3 /* ecs - equivalence class routines */
      4 
      5 /*-
      6  * Copyright (c) 1990 The Regents of the University of California.
      7  * All rights reserved.
      8  *
      9  * This code is derived from software contributed to Berkeley by
     10  * Vern Paxson.
     11  * 
     12  * The United States Government has rights in this work pursuant
     13  * to contract no. DE-AC03-76SF00098 between the United States
     14  * Department of Energy and the University of California.
     15  *
     16  * Redistribution and use in source and binary forms, with or without
     17  * modification, are permitted provided that the following conditions
     18  * are met:
     19  *
     20  * 1. Redistributions of source code must retain the above copyright
     21  *    notice, this list of conditions and the following disclaimer.
     22  * 2. Redistributions in binary form must reproduce the above copyright
     23  *    notice, this list of conditions and the following disclaimer in the
     24  *    documentation and/or other materials provided with the distribution.
     25  *
     26  * Neither the name of the University nor the names of its contributors
     27  * may be used to endorse or promote products derived from this software
     28  * without specific prior written permission.
     29  *
     30  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
     31  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
     32  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     33  * PURPOSE.
     34  */
     35 
     36 /* $Header: /cvs/src/usr.bin/lex/ecs.c,v 1.6 2003/06/04 17:34:44 millert Exp $ */
     37 
     38 #include "flexdef.h"
     39 
     40 /* ccl2ecl - convert character classes to set of equivalence classes */
     41 
     42 void ccl2ecl()
     43 	{
     44 	int i, ich, newlen, cclp, ccls, cclmec;
     45 
     46 	for ( i = 1; i <= lastccl; ++i )
     47 		{
     48 		/* We loop through each character class, and for each character
     49 		 * in the class, add the character's equivalence class to the
     50 		 * new "character" class we are creating.  Thus when we are all
     51 		 * done, character classes will really consist of collections
     52 		 * of equivalence classes
     53 		 */
     54 
     55 		newlen = 0;
     56 		cclp = cclmap[i];
     57 
     58 		for ( ccls = 0; ccls < ccllen[i]; ++ccls )
     59 			{
     60 			ich = ccltbl[cclp + ccls];
     61 			cclmec = ecgroup[ich];
     62 
     63 			if ( cclmec > 0 )
     64 				{
     65 				ccltbl[cclp + newlen] = cclmec;
     66 				++newlen;
     67 				}
     68 			}
     69 
     70 		ccllen[i] = newlen;
     71 		}
     72 	}
     73 
     74 
     75 /* cre8ecs - associate equivalence class numbers with class members
     76  *
     77  * fwd is the forward linked-list of equivalence class members.  bck
     78  * is the backward linked-list, and num is the number of class members.
     79  *
     80  * Returned is the number of classes.
     81  */
     82 
     83 int cre8ecs( fwd, bck, num )
     84 int fwd[], bck[], num;
     85 	{
     86 	int i, j, numcl;
     87 
     88 	numcl = 0;
     89 
     90 	/* Create equivalence class numbers.  From now on, ABS( bck(x) )
     91 	 * is the equivalence class number for object x.  If bck(x)
     92 	 * is positive, then x is the representative of its equivalence
     93 	 * class.
     94 	 */
     95 	for ( i = 1; i <= num; ++i )
     96 		if ( bck[i] == NIL )
     97 			{
     98 			bck[i] = ++numcl;
     99 			for ( j = fwd[i]; j != NIL; j = fwd[j] )
    100 				bck[j] = -numcl;
    101 			}
    102 
    103 	return numcl;
    104 	}
    105 
    106 
    107 /* mkeccl - update equivalence classes based on character class xtions
    108  *
    109  * synopsis
    110  *    Char ccls[];
    111  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
    112  *    void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
    113  *			int llsiz, int NUL_mapping );
    114  *
    115  * ccls contains the elements of the character class, lenccl is the
    116  * number of elements in the ccl, fwd is the forward link-list of equivalent
    117  * characters, bck is the backward link-list, and llsiz size of the link-list.
    118  *
    119  * NUL_mapping is the value which NUL (0) should be mapped to.
    120  */
    121 
    122 void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
    123 Char ccls[];
    124 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
    125 	{
    126 	int cclp, oldec, newec;
    127 	int cclm, i, j;
    128 	static unsigned char cclflags[CSIZE];	/* initialized to all '\0' */
    129 
    130 	/* Note that it doesn't matter whether or not the character class is
    131 	 * negated.  The same results will be obtained in either case.
    132 	 */
    133 
    134 	cclp = 0;
    135 
    136 	while ( cclp < lenccl )
    137 		{
    138 		cclm = ccls[cclp];
    139 
    140 		if ( NUL_mapping && cclm == 0 )
    141 			cclm = NUL_mapping;
    142 
    143 		oldec = bck[cclm];
    144 		newec = cclm;
    145 
    146 		j = cclp + 1;
    147 
    148 		for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
    149 			{ /* look for the symbol in the character class */
    150 			for ( ; j < lenccl; ++j )
    151 				{
    152 				int ccl_char;
    153 
    154 				if ( NUL_mapping && ccls[j] == 0 )
    155 					ccl_char = NUL_mapping;
    156 				else
    157 					ccl_char = ccls[j];
    158 
    159 				if ( ccl_char > i )
    160 					break;
    161 
    162 				if ( ccl_char == i && ! cclflags[j] )
    163 					{
    164 					/* We found an old companion of cclm
    165 					 * in the ccl.  Link it into the new
    166 					 * equivalence class and flag it as
    167 					 * having been processed.
    168 					 */
    169 
    170 					bck[i] = newec;
    171 					fwd[newec] = i;
    172 					newec = i;
    173 					/* Set flag so we don't reprocess. */
    174 					cclflags[j] = 1;
    175 
    176 					/* Get next equivalence class member. */
    177 					/* continue 2 */
    178 					goto next_pt;
    179 					}
    180 				}
    181 
    182 			/* Symbol isn't in character class.  Put it in the old
    183 			 * equivalence class.
    184 			 */
    185 
    186 			bck[i] = oldec;
    187 
    188 			if ( oldec != NIL )
    189 				fwd[oldec] = i;
    190 
    191 			oldec = i;
    192 
    193 			next_pt: ;
    194 			}
    195 
    196 		if ( bck[cclm] != NIL || oldec != bck[cclm] )
    197 			{
    198 			bck[cclm] = NIL;
    199 			fwd[oldec] = NIL;
    200 			}
    201 
    202 		fwd[newec] = NIL;
    203 
    204 		/* Find next ccl member to process. */
    205 
    206 		for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
    207 			{
    208 			/* Reset "doesn't need processing" flag. */
    209 			cclflags[cclp] = 0;
    210 			}
    211 		}
    212 	}
    213 
    214 
    215 /* mkechar - create equivalence class for single character */
    216 
    217 void mkechar( tch, fwd, bck )
    218 int tch, fwd[], bck[];
    219 	{
    220 	/* If until now the character has been a proper subset of
    221 	 * an equivalence class, break it away to create a new ec
    222 	 */
    223 
    224 	if ( fwd[tch] != NIL )
    225 		bck[fwd[tch]] = bck[tch];
    226 
    227 	if ( bck[tch] != NIL )
    228 		fwd[bck[tch]] = fwd[tch];
    229 
    230 	fwd[tch] = NIL;
    231 	bck[tch] = NIL;
    232 	}