contrib/flex/src/ecs.c

   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
  34
  35 #include "flexdef.h"
  36
  37 /* ccl2ecl - convert character classes to set of equivalence classes */
  38
  39 void    ccl2ecl (void)
  40 {
  41         int     i, ich, newlen, cclp, ccls, cclmec;
  42
  43         for (i = 1; i <= lastccl; ++i) {
  44                 /* We loop through each character class, and for each character
  45                  * in the class, add the character's equivalence class to the
  46                  * new "character" class we are creating.  Thus when we are all
  47                  * done, character classes will really consist of collections
  48                  * of equivalence classes
  49                  */
  50
  51                 newlen = 0;
  52                 cclp = cclmap[i];
  53
  54                 for (ccls = 0; ccls < ccllen[i]; ++ccls) {
  55                         ich = ccltbl[cclp + ccls];
  56                         cclmec = ecgroup[ich];
  57
  58                         if (cclmec > 0) {
  59                                 /* Note: range 1..256 is mapped to 1..255,0 */
  60                                 ccltbl[cclp + newlen] = (unsigned char) 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 (int fwd[], int bck[], int num)
  79 {
  80         int     i, j, numcl;
  81
  82         numcl = 0;
  83
  84         /* Create equivalence class numbers.  From now on, ABS( bck(x) )
  85          * is the equivalence class number for object x.  If bck(x)
  86          * is positive, then x is the representative of its equivalence
  87          * class.
  88          */
  89         for (i = 1; i <= num; ++i)
  90                 if (bck[i] == NIL) {
  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  *    unsigned char ccls[];
 104  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 105  *    void mkeccl( unsigned 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 (unsigned char ccls[], int lenccl, int fwd[], int bck[], int llsiz, int NUL_mapping)
 116 {
 117         int     cclp, oldec, newec;
 118         int     cclm, i, j;
 119         static unsigned char cclflags[CSIZE];   /* initialized to all '\0' */
 120
 121         /* Note that it doesn't matter whether or not the character class is
 122          * negated.  The same results will be obtained in either case.
 123          */
 124
 125         cclp = 0;
 126
 127         while (cclp < lenccl) {
 128                 cclm = ccls[cclp];
 129
 130                 if (NUL_mapping && cclm == 0)
 131                         cclm = NUL_mapping;
 132
 133                 oldec = bck[cclm];
 134                 newec = cclm;
 135
 136                 j = cclp + 1;
 137
 138                 for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) {       /* look for the symbol in the character class */
 139                         for (; j < lenccl; ++j) {
 140                                 int ccl_char;
 141
 142                                 if (NUL_mapping && ccls[j] == 0)
 143                                         ccl_char = NUL_mapping;
 144                                 else
 145                                         ccl_char = ccls[j];
 146
 147                                 if (ccl_char > i)
 148                                         break;
 149
 150                                 if (ccl_char == i && !cclflags[j]) {
 151                                         /* We found an old companion of cclm
 152                                          * in the ccl.  Link it into the new
 153                                          * equivalence class and flag it as
 154                                          * having been processed.
 155                                          */
 156
 157                                         bck[i] = newec;
 158                                         fwd[newec] = i;
 159                                         newec = i;
 160                                         /* Set flag so we don't reprocess. */
 161                                         cclflags[j] = 1;
 162
 163                                         /* Get next equivalence class member. */
 164                                         /* continue 2 */
 165                                         goto next_pt;
 166                                 }
 167                         }
 168
 169                         /* Symbol isn't in character class.  Put it in the old
 170                          * equivalence class.
 171                          */
 172
 173                         bck[i] = oldec;
 174
 175                         if (oldec != NIL)
 176                                 fwd[oldec] = i;
 177
 178                         oldec = i;
 179
 180                       next_pt:;
 181                 }
 182
 183                 if (bck[cclm] != NIL || oldec != bck[cclm]) {
 184                         bck[cclm] = NIL;
 185                         fwd[oldec] = NIL;
 186                 }
 187
 188                 fwd[newec] = NIL;
 189
 190                 /* Find next ccl member to process. */
 191
 192                 for (++cclp; cclp < lenccl && cclflags[cclp]; ++cclp) {
 193                         /* Reset "doesn't need processing" flag. */
 194                         cclflags[cclp] = 0;
 195                 }
 196         }
 197 }
 198
 199
 200 /* mkechar - create equivalence class for single character */
 201
 202 void    mkechar (int tch, int fwd[], int bck[])
 203 {
 204         /* If until now the character has been a proper subset of
 205          * an equivalence class, break it away to create a new ec
 206          */
 207
 208         if (fwd[tch] != NIL)
 209                 bck[fwd[tch]] = bck[tch];
 210
 211         if (bck[tch] != NIL)
 212                 fwd[bck[tch]] = fwd[tch];
 213
 214         fwd[tch] = NIL;
 215         bck[tch] = NIL;
 216 }