pattern.c

Gcomm is a serial communications program similar to seyon, but more modern, and easier to use. Works

#ifndef lint
static const char sccsid[] = "@(#)pattern.c 1.1 96/11/02 Edward Falk" ;
#endif

/*
 * Copyright (c) 1995 by Edward A. Falk
 */


/**********
 *
 *
 *	@@@@    @@@   @@@@@  @@@@@  @@@@@  @@@@   @   @  
 *	@   @  @   @    @      @    @      @   @  @@  @  
 *	@@@@   @@@@@    @      @    @@@    @@@@   @ @ @  
 *	@      @   @    @      @    @      @  @   @  @@  
 *	@      @   @    @      @    @@@@@  @   @  @   @  
 *
 *	PATTERN - simplistic pattern matching
 *
 *	These routines perform very basic pattern matches.  There are
 *	no wild cards.  The Knuth-Morris-Pratt pattern matching algorithm
 *	is used because it tests one character at a time, and doesn't
 *	require you to keep characters once they're tested, and because I
 *	think it's cool.
 *
 *
 *	void
 *	PatInit(Pattern *pat)
 *		Init pattern.  Call at start or any time the pattern
 *		should be reset (such as after a timeout).
 *
 *	int
 *	PatChar(Pattern *pat, int c)
 *		Pass character to pattern.  Return true if this character
 *		completes a match.
 *
 *
 *
 *	Edward A. Falk
 *
 *	July, 1995
 *
 *
 *
 **********/

#include <stdio.h>
#include <malloc.h>

#include "pattern.h"

/****
 *
 * Constants,  typedefs, externals, globals, statics, macros, block data
 *
 ****/

static	void	patDefine() ;



void
PatInit(pat)
	Pattern	*pat ;
{
	pat->count = 0 ;
	if( pat->flink == NULL )
	  patDefine(pat) ;
}


static	void
patDefine(pat)
	Pattern	*pat ;
{
	int	i,j ;
	int	len ;
	char	c ;

	if( pat == NULL || pat->str == NULL )
	  return ;

	len = strlen(pat->str) ;

	pat->flink = malloc(len) ;

	/* here's how the Knuth-Morris-Pratt string matching algorithm
	 * works:
	 *
	 * The simple case is when there is no initial substring of the
	 * search string which is repeated (i.e. the first character
	 * never occurs again.)  In such a case, you would match pattern
	 * characters against input characters one by one until the
	 * pattern was exhausted.  If any character failed to match, you
	 * would go back to the first pattern character and try again.
	 *
	 *  Example:  matching "weaver".  Compare input characters against
	 *  'w'.  If a match is found, advance the pattern to 'e'.  If the
	 *  next character matches 'e', then advance to 'a' and so on.  If
	 *  any character fails to match, reset the pattern and try that
	 *  character against the 'w' again.
	 *
	 * If there *are* repeated initial strings, you can't always go
	 * back to the start.  For instance, suppose we were trying to
	 * match "hathaway" and the input string was hathathaway.  The first
	 * "hatha" characters would match, but the second 't' would fail to
	 * match the 'w'.  In this case, you don't want to go retry the
	 * first pattern character, but the fourth.
	 *
	 * The "flink" field in the pattern is an array of "failure
	 * links" which indicate how far back in the pattern to go on a
	 * failure.  For patterns which don't repeat their first
	 * character, all failure links are 0.
	 *
	 * To build failure links:  For each pattern character Pi, start
	 * following Fi-1 until a match is found for Pi-1.  Set Fi = index
	 * of matched character + 1.
	 */

	/* First flink is irrelevant (we set it to 0).  Second flink is
	 * a pointer to character 0 (where else could it go?)
	 */

	i = 0 ;
	pat->flink[i++] = 0 ;
	pat->flink[i++] = 0 ;
	for(; i<len; ++i)
	{
	  j = pat->flink[i-1] ;
	  c = pat->str[i-1] ;
	  for(;;) {
	    if( c == pat->str[j] ) {
	      pat->flink[i] = j+1 ;
	      break ;
	    }
	    else if( j == 0 ) {
	      pat->flink[i] = 0 ;
	      break ;
	    }
	    j = pat->flink[j] ;
	  }
	}
}



int
PatChar(pat, c)
	Pattern	*pat ;
	int	c ;
{
	if( pat->str[pat->count] == c ) {
	  ++pat->count ;
	  return (pat->str[pat->count] == '\0') ;
	}

	else if( pat->count > 0 ) {
	  pat->count = pat->flink[pat->count] ;
	  return PatChar(pat, c) ;
	}

	else return 0 ;
}