blob: dc68360d72926846e35b1afb7e520c3bc334e12f [file] [log] [blame]
/* ecs - equivalence class routines */
/* Copyright (c) 1990 The Regents of the University of California. */
/* All rights reserved. */
/* This code is derived from software contributed to Berkeley by */
/* Vern Paxson. */
/* The United States Government has rights in this work pursuant */
/* to contract no. DE-AC03-76SF00098 between the United States */
/* Department of Energy and the University of California. */
/* This file is part of flex */
/* Redistribution and use in source and binary forms, with or without */
/* modification, are permitted provided that the following conditions */
/* are met: */
/* 1. Redistributions of source code must retain the above copyright */
/* notice, this list of conditions and the following disclaimer. */
/* 2. Redistributions in binary form must reproduce the above copyright */
/* notice, this list of conditions and the following disclaimer in the */
/* documentation and/or other materials provided with the distribution. */
/* Neither the name of the University nor the names of its contributors */
/* may be used to endorse or promote products derived from this software */
/* without specific prior written permission. */
/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */
/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */
/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
/* PURPOSE. */
#include "flexdef.h"
/* ccl2ecl - convert character classes to set of equivalence classes */
void ccl2ecl (void)
{
int i, ich, newlen, cclp, ccls, cclmec;
for (i = 1; i <= lastccl; ++i) {
/* We loop through each character class, and for each character
* in the class, add the character's equivalence class to the
* new "character" class we are creating. Thus when we are all
* done, character classes will really consist of collections
* of equivalence classes
*/
newlen = 0;
cclp = cclmap[i];
for (ccls = 0; ccls < ccllen[i]; ++ccls) {
ich = ccltbl[cclp + ccls];
cclmec = ecgroup[ich];
if (cclmec > 0) {
/* Note: range 1..256 is mapped to 1..255,0 */
ccltbl[cclp + newlen] = (unsigned char) cclmec;
++newlen;
}
}
ccllen[i] = newlen;
}
}
/* cre8ecs - associate equivalence class numbers with class members
*
* fwd is the forward linked-list of equivalence class members. bck
* is the backward linked-list, and num is the number of class members.
*
* Returned is the number of classes.
*/
int cre8ecs (int fwd[], int bck[], int num)
{
int i, j, numcl;
numcl = 0;
/* Create equivalence class numbers. From now on, ABS( bck(x) )
* is the equivalence class number for object x. If bck(x)
* is positive, then x is the representative of its equivalence
* class.
*/
for (i = 1; i <= num; ++i)
if (bck[i] == NIL) {
bck[i] = ++numcl;
for (j = fwd[i]; j != NIL; j = fwd[j])
bck[j] = -numcl;
}
return numcl;
}
/* mkeccl - update equivalence classes based on character class xtions
*
* synopsis
* unsigned char ccls[];
* int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
* void mkeccl( unsigned char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
* int llsiz, int NUL_mapping );
*
* ccls contains the elements of the character class, lenccl is the
* number of elements in the ccl, fwd is the forward link-list of equivalent
* characters, bck is the backward link-list, and llsiz size of the link-list.
*
* NUL_mapping is the value which NUL (0) should be mapped to.
*/
void mkeccl (unsigned char ccls[], int lenccl, int fwd[], int bck[], int llsiz, int NUL_mapping)
{
int cclp, oldec, newec;
int cclm, i, j;
static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
/* Note that it doesn't matter whether or not the character class is
* negated. The same results will be obtained in either case.
*/
cclp = 0;
while (cclp < lenccl) {
cclm = ccls[cclp];
if (NUL_mapping && cclm == 0)
cclm = NUL_mapping;
oldec = bck[cclm];
newec = cclm;
j = cclp + 1;
for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) { /* look for the symbol in the character class */
for (; j < lenccl; ++j) {
int ccl_char;
if (NUL_mapping && ccls[j] == 0)
ccl_char = NUL_mapping;
else
ccl_char = ccls[j];
if (ccl_char > i)
break;
if (ccl_char == i && !cclflags[j]) {
/* We found an old companion of cclm
* in the ccl. Link it into the new
* equivalence class and flag it as
* having been processed.
*/
bck[i] = newec;
fwd[newec] = i;
newec = i;
/* Set flag so we don't reprocess. */
cclflags[j] = 1;
/* Get next equivalence class member. */
/* continue 2 */
goto next_pt;
}
}
/* Symbol isn't in character class. Put it in the old
* equivalence class.
*/
bck[i] = oldec;
if (oldec != NIL)
fwd[oldec] = i;
oldec = i;
next_pt:;
}
if (bck[cclm] != NIL || oldec != bck[cclm]) {
bck[cclm] = NIL;
fwd[oldec] = NIL;
}
fwd[newec] = NIL;
/* Find next ccl member to process. */
for (++cclp; cclp < lenccl && cclflags[cclp]; ++cclp) {
/* Reset "doesn't need processing" flag. */
cclflags[cclp] = 0;
}
}
}
/* mkechar - create equivalence class for single character */
void mkechar (int tch, int fwd[], int bck[])
{
/* If until now the character has been a proper subset of
* an equivalence class, break it away to create a new ec
*/
if (fwd[tch] != NIL)
bck[fwd[tch]] = bck[tch];
if (bck[tch] != NIL)
fwd[bck[tch]] = fwd[tch];
fwd[tch] = NIL;
bck[tch] = NIL;
}