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