lib/flex/ecs.c

   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 with or without
  15  * modification are permitted provided that: (1) source distributions retain
  16  * this entire copyright notice and comment, and (2) distributions including
  17  * binaries display the following acknowledgement:  ``This product includes
  18  * software developed by the University of California, Berkeley and its
  19  * contributors'' in the documentation or other materials provided with the
  20  * distribution and in all advertising materials mentioning features or use
  21  * of this software.  Neither the name of the University nor the names of
  22  * its contributors may be used to endorse or promote products derived from
  23  * this software without 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: /home/daffy/u0/vern/flex/RCS/ecs.c,v 2.9 93/12/07 10:18:20 vern 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         }