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