V10/cmd/flex/ecs.c

/* ecs - equivalence class routines */

/*
 * Copyright (c) 1989 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.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Berkeley.  The name of the
 * University may not 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.
 */

#ifndef lint

static char copyright[] =
    "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
static char CR_continuation[] = "@(#) All rights reserved.\n";

static char rcsid[] =
    "@(#) $Header: ecs.c,v 2.0 89/06/20 15:49:39 vern Locked $ (LBL)";

#endif

#include "flexdef.h"

/* ccl2ecl - convert character classes to set of equivalence classes
 *
 * synopsis
 *    ccl2ecl();
 */

ccl2ecl()

    {
    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 )
		{
		ccltbl[cclp + newlen] = cclmec;
		++newlen;
		}
	    }

	ccllen[i] = newlen;
	}
    }


/* cre8ecs - associate equivalence class numbers with class members
 *
 * synopsis
 *    int cre8ecs();
 *    number of classes = cre8ecs( fwd, bck, num );
 *
 *  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( fwd, bck, num )
int fwd[], bck[], 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
 *    char ccls[];
 *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
 *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
 *
 * where 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
 */

mkeccl( ccls, lenccl, fwd, bck, llsiz )
char ccls[];
int lenccl, fwd[], bck[], llsiz;

    {
    int cclp, oldec, newec;
    int cclm, i, j;

#define PROCFLG 0x80

    /* 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];
	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 && (ccls[j] <= i || (ccls[j] & PROCFLG)); ++j )
		if ( ccls[j] == i )
		    {
		    /* 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;
		    ccls[j] |= PROCFLG;	/* set flag so we don't reprocess */

		    /* 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; (ccls[cclp] & PROCFLG) && cclp < lenccl; ++cclp )
	    {
	    /* reset "doesn't need processing" flag */
	    ccls[cclp] &= ~PROCFLG;
	    }
	}
    }


/* mkechar - create equivalence class for single character
 *
 * synopsis
 *    int tch, fwd[], bck[];
 *    mkechar( tch, fwd, bck );
 */

mkechar( tch, fwd, bck )
int tch, fwd[], 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;
    }