ecs.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349
  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. * Redistribution and use in source and binary forms are permitted provided
  14. * that: (1) source distributions retain this entire copyright notice and
  15. * comment, and (2) distributions including binaries display the following
  16. * acknowledgement: ``This product includes software developed by the
  17. * University of California, Berkeley and its contributors'' in the
  18. * documentation or other materials provided with the distribution and in
  19. * all advertising materials mentioning features or use of this software.
  20. * Neither the name of the University nor the names of its contributors may
  21. * be used to endorse or promote products derived from this software without
  22. * specific prior written permission.
  23. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  24. * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  25. * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  26. */
  27. #ifndef lint
  28. static char rcsid[] =
  29. "@(#) $Id$ (LBL)";
  30. #endif
  31. #include "flexdef.h"
  32. /* ccl2ecl - convert character classes to set of equivalence classes
  33. *
  34. * synopsis
  35. * ccl2ecl();
  36. */
  37. void ccl2ecl()
  38. {
  39. int i, ich, newlen, cclp, ccls, cclmec;
  40. for ( i = 1; i <= lastccl; ++i )
  41. {
  42. /* we loop through each character class, and for each character
  43. * in the class, add the character's equivalence class to the
  44. * new "character" class we are creating. Thus when we are all
  45. * done, character classes will really consist of collections
  46. * of equivalence classes
  47. */
  48. newlen = 0;
  49. cclp = cclmap[i];
  50. for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  51. {
  52. ich = ccltbl[cclp + ccls];
  53. cclmec = ecgroup[ich];
  54. if ( xlation && cclmec < 0 )
  55. {
  56. /* special hack--if we're doing %t tables then it's
  57. * possible that no representative of this character's
  58. * equivalence class is in the ccl. So waiting till
  59. * we see the representative would be disastrous. Instead,
  60. * we add this character's equivalence class anyway, if it's
  61. * not already present.
  62. */
  63. int j;
  64. /* this loop makes this whole process n^2; but we don't
  65. * really care about %t performance anyway
  66. */
  67. for ( j = 0; j < newlen; ++j )
  68. if ( ccltbl[cclp + j] == -cclmec )
  69. break;
  70. if ( j >= newlen )
  71. { /* no representative yet, add this one in */
  72. ccltbl[cclp + newlen] = -cclmec;
  73. ++newlen;
  74. }
  75. }
  76. else if ( cclmec > 0 )
  77. {
  78. ccltbl[cclp + newlen] = cclmec;
  79. ++newlen;
  80. }
  81. }
  82. ccllen[i] = newlen;
  83. }
  84. }
  85. /* cre8ecs - associate equivalence class numbers with class members
  86. *
  87. * synopsis
  88. * int cre8ecs();
  89. * number of classes = cre8ecs( fwd, bck, num );
  90. *
  91. * fwd is the forward linked-list of equivalence class members. bck
  92. * is the backward linked-list, and num is the number of class members.
  93. *
  94. * Returned is the number of classes.
  95. */
  96. int cre8ecs( fwd, bck, num )
  97. int fwd[], bck[], num;
  98. {
  99. int i, j, numcl;
  100. numcl = 0;
  101. /* create equivalence class numbers. From now on, abs( bck(x) )
  102. * is the equivalence class number for object x. If bck(x)
  103. * is positive, then x is the representative of its equivalence
  104. * class.
  105. */
  106. for ( i = 1; i <= num; ++i )
  107. if ( bck[i] == NIL )
  108. {
  109. bck[i] = ++numcl;
  110. for ( j = fwd[i]; j != NIL; j = fwd[j] )
  111. bck[j] = -numcl;
  112. }
  113. return ( numcl );
  114. }
  115. /* ecs_from_xlation - associate equivalence class numbers using %t table
  116. *
  117. * synopsis
  118. * numecs = ecs_from_xlation( ecmap );
  119. *
  120. * Upon return, ecmap will map each character code to its equivalence
  121. * class. The mapping will be positive if the character is the representative
  122. * of its class, negative otherwise.
  123. *
  124. * Returns the number of equivalence classes used.
  125. */
  126. int ecs_from_xlation( ecmap )
  127. int ecmap[];
  128. {
  129. int i;
  130. int nul_is_alone = false;
  131. int did_default_xlation_class = false;
  132. if ( xlation[0] != 0 )
  133. {
  134. /* if NUL shares its translation with other characters, choose one
  135. * of the other characters as the representative for the equivalence
  136. * class. This allows a cheap test later to see whether we can
  137. * do away with NUL's equivalence class.
  138. */
  139. for ( i = 1; i < csize; ++i )
  140. if ( xlation[i] == -xlation[0] )
  141. {
  142. xlation[i] = xlation[0];
  143. ecmap[0] = -xlation[0];
  144. break;
  145. }
  146. if ( i >= csize )
  147. /* didn't find a companion character--remember this fact */
  148. nul_is_alone = true;
  149. }
  150. for ( i = 1; i < csize; ++i )
  151. if ( xlation[i] == 0 )
  152. {
  153. if ( did_default_xlation_class )
  154. ecmap[i] = -num_xlations;
  155. else
  156. {
  157. /* make an equivalence class for those characters not
  158. * specified in the %t table
  159. */
  160. ++num_xlations;
  161. ecmap[i] = num_xlations;
  162. did_default_xlation_class = true;
  163. }
  164. }
  165. else
  166. ecmap[i] = xlation[i];
  167. if ( nul_is_alone )
  168. /* force NUL's equivalence class to be the last one */
  169. {
  170. ++num_xlations;
  171. ecmap[0] = num_xlations;
  172. /* there's actually a bug here: if someone is fanatic enough to
  173. * put every character in its own translation class, then right
  174. * now we just promoted NUL's equivalence class to be csize + 1;
  175. * we can handle NUL's class number being == csize (by instead
  176. * putting it in its own table), but we can't handle some *other*
  177. * character having to be put in its own table, too. So in
  178. * this case we bail out.
  179. */
  180. if ( num_xlations > csize )
  181. flexfatal( "too many %t classes!" );
  182. }
  183. return num_xlations;
  184. }
  185. /* mkeccl - update equivalence classes based on character class xtions
  186. *
  187. * synopsis
  188. * Char ccls[];
  189. * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
  190. * mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping );
  191. *
  192. * where ccls contains the elements of the character class, lenccl is the
  193. * number of elements in the ccl, fwd is the forward link-list of equivalent
  194. * characters, bck is the backward link-list, and llsiz size of the link-list
  195. *
  196. * NUL_mapping is the value which NUL (0) should be mapped to.
  197. */
  198. void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
  199. Char ccls[];
  200. int lenccl, fwd[], bck[], llsiz, NUL_mapping;
  201. {
  202. int cclp, oldec, newec;
  203. int cclm, i, j;
  204. static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
  205. /* note that it doesn't matter whether or not the character class is
  206. * negated. The same results will be obtained in either case.
  207. */
  208. cclp = 0;
  209. while ( cclp < lenccl )
  210. {
  211. cclm = ccls[cclp];
  212. if ( NUL_mapping && cclm == 0 )
  213. cclm = NUL_mapping;
  214. oldec = bck[cclm];
  215. newec = cclm;
  216. j = cclp + 1;
  217. for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  218. { /* look for the symbol in the character class */
  219. for ( ; j < lenccl; ++j )
  220. {
  221. register int ccl_char;
  222. if ( NUL_mapping && ccls[j] == 0 )
  223. ccl_char = NUL_mapping;
  224. else
  225. ccl_char = ccls[j];
  226. if ( ccl_char > i )
  227. break;
  228. if ( ccl_char == i && ! cclflags[j] )
  229. {
  230. /* we found an old companion of cclm in the ccl.
  231. * link it into the new equivalence class and flag it as
  232. * having been processed
  233. */
  234. bck[i] = newec;
  235. fwd[newec] = i;
  236. newec = i;
  237. cclflags[j] = 1; /* set flag so we don't reprocess */
  238. /* get next equivalence class member */
  239. /* continue 2 */
  240. goto next_pt;
  241. }
  242. }
  243. /* symbol isn't in character class. Put it in the old equivalence
  244. * class
  245. */
  246. bck[i] = oldec;
  247. if ( oldec != NIL )
  248. fwd[oldec] = i;
  249. oldec = i;
  250. next_pt:
  251. ;
  252. }
  253. if ( bck[cclm] != NIL || oldec != bck[cclm] )
  254. {
  255. bck[cclm] = NIL;
  256. fwd[oldec] = NIL;
  257. }
  258. fwd[newec] = NIL;
  259. /* find next ccl member to process */
  260. for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
  261. {
  262. /* reset "doesn't need processing" flag */
  263. cclflags[cclp] = 0;
  264. }
  265. }
  266. }
  267. /* mkechar - create equivalence class for single character
  268. *
  269. * synopsis
  270. * int tch, fwd[], bck[];
  271. * mkechar( tch, fwd, bck );
  272. */
  273. void mkechar( tch, fwd, bck )
  274. int tch, fwd[], bck[];
  275. {
  276. /* if until now the character has been a proper subset of
  277. * an equivalence class, break it away to create a new ec
  278. */
  279. if ( fwd[tch] != NIL )
  280. bck[fwd[tch]] = bck[tch];
  281. if ( bck[tch] != NIL )
  282. fwd[bck[tch]] = fwd[tch];
  283. fwd[tch] = NIL;
  284. bck[tch] = NIL;
  285. }