external/bsd/flex/dist/ecs.c

   1 /*      $NetBSD$        */
   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    ccl2ecl ()
  42 {
  43         int     i, ich, newlen, cclp, ccls, cclmec;
  44
  45         for (i = 1; i <= lastccl; ++i) {
  46                 /* We loop through each character class, and for each character
  47                  * in the class, add the character's equivalence class to the
  48                  * new "character" class we are creating.  Thus when we are all
  49                  * done, character classes will really consist of collections
  50                  * of equivalence classes
  51                  */
  52
  53                 newlen = 0;
  54                 cclp = cclmap[i];
  55
  56                 for (ccls = 0; ccls < ccllen[i]; ++ccls) {
  57                         ich = ccltbl[cclp + ccls];
  58                         cclmec = ecgroup[ich];
  59
  60                         if (cclmec > 0) {
  61                                 ccltbl[cclp + newlen] = cclmec;
  62                                 ++newlen;
  63                         }
  64                 }
  65
  66                 ccllen[i] = newlen;
  67         }
  68 }
  69
  70
  71 /* cre8ecs - associate equivalence class numbers with class members
  72  *
  73  * fwd is the forward linked-list of equivalence class members.  bck
  74  * is the backward linked-list, and num is the number of class members.
  75  *
  76  * Returned is the number of classes.
  77  */
  78
  79 int     cre8ecs (fwd, bck, num)
  80      int     fwd[], bck[], num;
  81 {
  82         int     i, j, numcl;
  83
  84         numcl = 0;
  85
  86         /* Create equivalence class numbers.  From now on, ABS( bck(x) )
  87          * is the equivalence class number for object x.  If bck(x)
  88          * is positive, then x is the representative of its equivalence
  89          * class.
  90          */
  91         for (i = 1; i <= num; ++i)
  92                 if (bck[i] == NIL) {
  93                         bck[i] = ++numcl;
  94                         for (j = fwd[i]; j != NIL; j = fwd[j])
  95                                 bck[j] = -numcl;
  96                 }
  97
  98         return numcl;
  99 }
 100
 101
 102 /* mkeccl - update equivalence classes based on character class xtions
 103  *
 104  * synopsis
 105  *    Char ccls[];
 106  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 107  *    void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
 108  *                      int llsiz, int NUL_mapping );
 109  *
 110  * ccls contains the elements of the character class, lenccl is the
 111  * number of elements in the ccl, fwd is the forward link-list of equivalent
 112  * characters, bck is the backward link-list, and llsiz size of the link-list.
 113  *
 114  * NUL_mapping is the value which NUL (0) should be mapped to.
 115  */
 116
 117 void    mkeccl (ccls, lenccl, fwd, bck, llsiz, NUL_mapping)
 118      Char    ccls[];
 119      int     lenccl, fwd[], bck[], llsiz, 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         /* Note that it doesn't matter whether or not the character class is
 126          * negated.  The same results will be obtained in either case.
 127          */
 128
 129         cclp = 0;
 130
 131         while (cclp < lenccl) {
 132                 cclm = ccls[cclp];
 133
 134                 if (NUL_mapping && cclm == 0)
 135                         cclm = NUL_mapping;
 136
 137                 oldec = bck[cclm];
 138                 newec = cclm;
 139
 140                 j = cclp + 1;
 141
 142                 for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) {       /* look for the symbol in the character class */
 143                         for (; j < lenccl; ++j) {
 144                                 register int ccl_char;
 145
 146                                 if (NUL_mapping && ccls[j] == 0)
 147                                         ccl_char = NUL_mapping;
 148                                 else
 149                                         ccl_char = ccls[j];
 150
 151                                 if (ccl_char > i)
 152                                         break;
 153
 154                                 if (ccl_char == i && !cclflags[j]) {
 155                                         /* We found an old companion of cclm
 156                                          * in the ccl.  Link it into the new
 157                                          * equivalence class and flag it as
 158                                          * having been processed.
 159                                          */
 160
 161                                         bck[i] = newec;
 162                                         fwd[newec] = i;
 163                                         newec = i;
 164                                         /* Set flag so we don't reprocess. */
 165                                         cclflags[j] = 1;
 166
 167                                         /* Get next equivalence class member. */
 168                                         /* continue 2 */
 169                                         goto next_pt;
 170                                 }
 171                         }
 172
 173                         /* Symbol isn't in character class.  Put it in the old
 174                          * equivalence class.
 175                          */
 176
 177                         bck[i] = oldec;
 178
 179                         if (oldec != NIL)
 180                                 fwd[oldec] = i;
 181
 182                         oldec = i;
 183
 184                       next_pt:;
 185                 }
 186
 187                 if (bck[cclm] != NIL || oldec != bck[cclm]) {
 188                         bck[cclm] = NIL;
 189                         fwd[oldec] = NIL;
 190                 }
 191
 192                 fwd[newec] = NIL;
 193
 194                 /* Find next ccl member to process. */
 195
 196                 for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) {
 197                         /* Reset "doesn't need processing" flag. */
 198                         cclflags[cclp] = 0;
 199                 }
 200         }
 201 }
 202
 203
 204 /* mkechar - create equivalence class for single character */
 205
 206 void    mkechar (tch, fwd, bck)
 207      int     tch, fwd[], bck[];
 208 {
 209         /* If until now the character has been a proper subset of
 210          * an equivalence class, break it away to create a new ec
 211          */
 212
 213         if (fwd[tch] != NIL)
 214                 bck[fwd[tch]] = bck[tch];
 215
 216         if (bck[tch] != NIL)
 217                 fwd[bck[tch]] = fwd[tch];
 218
 219         fwd[tch] = NIL;
 220         bck[tch] = NIL;
 221 }