1 /* ecs - equivalence class routines */ 2 3 /* Copyright (c) 1990 The Regents of the University of California. */ 4 /* All rights reserved. */ 5 6 /* This code is derived from software contributed to Berkeley by */ 7 /* Vern Paxson. */ 8 9 /* The United States Government has rights in this work pursuant */ 10 /* to contract no. DE-AC03-76SF00098 between the United States */ 11 /* Department of Energy and the University of California. */ 12 13 /* This file is part of flex */ 14 15 /* Redistribution and use in source and binary forms, with or without */ 16 /* modification, are permitted provided that the following conditions */ 17 /* are met: */ 18 19 /* 1. Redistributions of source code must retain the above copyright */ 20 /* notice, this list of conditions and the following disclaimer. */ 21 /* 2. Redistributions in binary form must reproduce the above copyright */ 22 /* notice, this list of conditions and the following disclaimer in the */ 23 /* documentation and/or other materials provided with the distribution. */ 24 25 /* Neither the name of the University nor the names of its contributors */ 26 /* may be used to endorse or promote products derived from this software */ 27 /* without specific prior written permission. */ 28 29 /* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 30 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 31 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 32 /* PURPOSE. */ 33 #include "flexdef.h" 34 __RCSID("$NetBSD: ecs.c,v 1.2 2016/01/09 17:38:57 christos Exp $"); 35 36 /* ccl2ecl - convert character classes to set of equivalence classes */ 37 38 void ccl2ecl () 39 { 40 int i, ich, newlen, cclp, ccls, cclmec; 41 42 for (i = 1; i <= lastccl; ++i) { 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 ich = ccltbl[cclp + ccls]; 55 cclmec = ecgroup[ich]; 56 57 if (cclmec > 0) { 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 bck[i] = ++numcl; 91 for (j = fwd[i]; j != NIL; j = fwd[j]) 92 bck[j] = -numcl; 93 } 94 95 return numcl; 96 } 97 98 99 /* mkeccl - update equivalence classes based on character class xtions 100 * 101 * synopsis 102 * Char ccls[]; 103 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping; 104 * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz], 105 * int llsiz, int NUL_mapping ); 106 * 107 * ccls contains the elements of the character class, lenccl is the 108 * number of elements in the ccl, fwd is the forward link-list of equivalent 109 * characters, bck is the backward link-list, and llsiz size of the link-list. 110 * 111 * NUL_mapping is the value which NUL (0) should be mapped to. 112 */ 113 114 void mkeccl (ccls, lenccl, fwd, bck, llsiz, NUL_mapping) 115 Char ccls[]; 116 int lenccl, fwd[], bck[], llsiz, NUL_mapping; 117 { 118 int cclp, oldec, newec; 119 int cclm, i, j; 120 static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */ 121 122 /* Note that it doesn't matter whether or not the character class is 123 * negated. The same results will be obtained in either case. 124 */ 125 126 cclp = 0; 127 128 while (cclp < lenccl) { 129 cclm = ccls[cclp]; 130 131 if (NUL_mapping && cclm == 0) 132 cclm = NUL_mapping; 133 134 oldec = bck[cclm]; 135 newec = cclm; 136 137 j = cclp + 1; 138 139 for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) { /* look for the symbol in the character class */ 140 for (; j < lenccl; ++j) { 141 int ccl_char; 142 143 if (NUL_mapping && ccls[j] == 0) 144 ccl_char = NUL_mapping; 145 else 146 ccl_char = ccls[j]; 147 148 if (ccl_char > i) 149 break; 150 151 if (ccl_char == i && !cclflags[j]) { 152 /* We found an old companion of cclm 153 * in the ccl. Link it into the new 154 * equivalence class and flag it as 155 * having been processed. 156 */ 157 158 bck[i] = newec; 159 fwd[newec] = i; 160 newec = i; 161 /* Set flag so we don't reprocess. */ 162 cclflags[j] = 1; 163 164 /* Get next equivalence class member. */ 165 /* continue 2 */ 166 goto next_pt; 167 } 168 } 169 170 /* Symbol isn't in character class. Put it in the old 171 * equivalence class. 172 */ 173 174 bck[i] = oldec; 175 176 if (oldec != NIL) 177 fwd[oldec] = i; 178 179 oldec = i; 180 181 next_pt:; 182 } 183 184 if (bck[cclm] != NIL || oldec != bck[cclm]) { 185 bck[cclm] = NIL; 186 fwd[oldec] = NIL; 187 } 188 189 fwd[newec] = NIL; 190 191 /* Find next ccl member to process. */ 192 193 for (++cclp; cclp < lenccl && cclflags[cclp]; ++cclp) { 194 /* Reset "doesn't need processing" flag. */ 195 cclflags[cclp] = 0; 196 } 197 } 198 } 199 200 201 /* mkechar - create equivalence class for single character */ 202 203 void mkechar (tch, fwd, bck) 204 int tch, fwd[], bck[]; 205 { 206 /* If until now the character has been a proper subset of 207 * an equivalence class, break it away to create a new ec 208 */ 209 210 if (fwd[tch] != NIL) 211 bck[fwd[tch]] = bck[tch]; 212 213 if (bck[tch] != NIL) 214 fwd[bck[tch]] = fwd[tch]; 215 216 fwd[tch] = NIL; 217 bck[tch] = NIL; 218 } 219