Annotation of src/usr.bin/lex/ecs.c, Revision 1.1
1.1 ! deraadt 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 are permitted provided
! 15: * that: (1) source distributions retain this entire copyright notice and
! 16: * comment, and (2) distributions including binaries display the following
! 17: * acknowledgement: ``This product includes software developed by the
! 18: * University of California, Berkeley and its contributors'' in the
! 19: * documentation or other materials provided with the distribution and in
! 20: * all advertising materials mentioning features or use of this software.
! 21: * Neither the name of the University nor the names of its contributors may
! 22: * be used to endorse or promote products derived from this software without
! 23: * 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: /a/cvsroot/src/usr.bin/lex/ecs.c,v 1.7 1995/05/05 05:35:15 jtc Exp $ */
! 30:
! 31: #include "flexdef.h"
! 32:
! 33: /* ccl2ecl - convert character classes to set of equivalence classes */
! 34:
! 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:
! 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:
! 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:
! 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: }