acsm.c

AC算法 用指针实现 用指针指向状态机的状态变量

//this is a file used in Multi-Pattern Search Engine


#include "acsm.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>


#define MEMASSERT(p,s) if(!p){fprintf(stderr,"ACSM-No Memory: %s!\n",s);exit(0);}


static void *AC_MALLOC (int n)         
{
	void *p;
	p = malloc (n);

	return p;
}


static void AC_FREE(void *p)           
{
	if (p)
		free(p);
	p=NULL;
}


typedef struct _qnode                                //define a queue node
{
	STATE * cs;
	struct _qnode *next;
}QNODE;


typedef struct                                       //define a queue
{
	QNODE * head, *tail;
	int count;
}QUEUE;



STATEMACHINE *acsmNew ()                 //innitial the statemachine
{	
	STATEMACHINE * p;
	p = (STATEMACHINE *) AC_MALLOC (sizeof (STATEMACHINE));
	MEMASSERT (p, "acsmnew");
	if (p)
		memset (p, 0, sizeof (STATEMACHINE));
	return p;
}


STATE * smalloc()                           //creat a space to state and innitial it 
{
    int i;
	STATE * s;
	s= (STATE *) AC_MALLOC (sizeof (STATE));
	MEMASSERT (s, "BuildACSM");
	memset (s, 0,sizeof (STATE));
    s->aNextState[MAXLEN] = (void *)AC_MALLOC(sizeof(MAXLEN));
	MEMASSERT (s->aNextState , "acsmCompile");
	memset (s->aNextState , 0,sizeof (s->aNextState));
    for (i = 0; i < ALPHABET_SIZE; i++)
		{
			s->aNextState[i] = ACSM_FAIL_STATE;
		}
	s->FailState=NULL;

	return s;
}




static void queue_init (QUEUE * s)              //innitial the queue
{
	s->head = s->tail = 0;
	s->count = 0;
}


static void queueadd (QUEUE * s,STATE * q)            //add a element to a queue
{
	QNODE * p;
	if (!s->head)
	{
		p=s->tail = s->head = (QNODE *) AC_MALLOC (sizeof (QNODE));
		MEMASSERT (p, "queueadd");
//		q->next = 0;   //Set the New Node's Next Null
		p->cs=q;
		p->next=0;
//		s->head->cs=s->tail->cs=q;
	}
	else
	{
		p= (QNODE *) AC_MALLOC (sizeof (QNODE));
		MEMASSERT (p, "queueadd");
		p->next = 0;
		p->cs=q;
		s->tail->next = p;
		s->tail = p;
	}
	s->count++;
}

STATE * queueremove (QUEUE * s)             //remove a element from a queue
{
//	STATE * ad;
//	*ad=NULL;
	STATE *cs;
	QNODE *q;
	if (s->head)
	{
		q = s->head;
		cs=q->cs;
		s->head=s->head->next;
		s->count--;
		if (!s->head)
		{
			s->tail = 0;
			s->count = 0;
		}

		AC_FREE (q);
	}
	return cs;
}

static int queue_count (QUEUE * s)             //return the count of the queue
{
	return s->count;
}

static void queue_free (QUEUE * s)               //free a queue
{
	while (queue_count (s))
	{
		queueremove (s);
	}
}



void AddMatchList (STATE * s,unsigned char * p)    //add the pattern to the state
{
	ACSM_PATTERN * q;
	q=(ACSM_PATTERN *)AC_MALLOC(sizeof(ACSM_PATTERN));
	MEMASSERT(q,"AddMatchList");
	if(q)
	{
		memset(q,0,sizeof(ACSM_PATTERN));
	}
    q->pattern=p;
	q->num=0;
//	s->MatchList=(ACSM_PATTERN *)AC_MALLOC(sizeof(ACSM_PATTERN));
    q->nextpattern =NULL;
	s->MatchList = q;

}


void AddPatternState(STATEMACHINE * acsm,unsigned char * pat,int m)   //add state to the statemachine
{
	int n;
	STATE * next,*s,*snew;
	unsigned char * pattern;
	pattern=pat;
	s=acsm->aStateMachine;
	n=m;
    for (; n > 0; pattern ++, n--)
	{
		next = s->aNextState[*pattern];
		if (next == ACSM_FAIL_STATE)
			break;
		s = next;
	}
    
	for (; n > 0; pattern++, n--)
	{
        snew= smalloc();
        s->aNextState[*pattern]=snew;
		s=snew;
	}
	
    AddMatchList (s, pat);                            //add the pattern to the state
}


static void qnode_init (QNODE * AD) 
{
	AD->cs=0;
	AD->next=0;
}

void Build_DFA (STATEMACHINE * acsm)
{
	int i;
	QNODE  AD,*qnode=&AD;
    QUEUE  q, *queue=&q;
	STATE *r,*t;   
//	AD->cs=acsm->aStateMachine;
//	AD->next=NULL;


    queue_init (queue);
	qnode_init (qnode);
	for (i = 0; i < MAXLEN; i++)
	{
		qnode->cs = acsm->aStateMachine->aNextState[i];
		if (qnode->cs)
		{
			queueadd(queue, qnode->cs);                    //add the state's adress to the queue
			qnode->cs->FailState = acsm->aStateMachine;    //set first statetable's fail state is 0
		}
	}
    while (queue_count (queue) > 0)
	{
		r = queueremove (queue);

		for (i = 0; i < MAXLEN; i++)
		{
			STATE * fs, *next, * CurrState;
			if ((r->aNextState[i]!=NULL))
			{
				qnode->cs=t=r->aNextState[i];
				queueadd (queue, qnode->cs);

				fs = r->FailState;
//                while ((next=fs->aNextState[i]) ==ACSM_FAIL_STATE)
//				{
//					fs = fs->FailState;
//				}
//                t->FailState = next;
				next=fs;
				t->FailState = next;

			}
			else
			{
			    CurrState=r->FailState;	
				r->aNextState[i] =CurrState->aNextState[i];
			}
		}
	}

	queue_free (queue);

//	return 0;
}


//int PrintMatch(AC_PATTERN * mlist, int nline, int index)
//{
//	fprintf (stdout, "Match KeyWord %s at %d line %d char\n", mlist->pattern,nline,index);
//}

//int acsmSearch (STATEMACHINE * acsm, char *Tx,int n,int nline)
//{
//	char *T,*Tc;
//	int index;
	//T=Tx;
  //  Tc=Tx+n;
//	STATE *w=0;
    //ACSM_PATTERN *mlist=0;
  //  for (; T < Tc; T++)   //s=acsm->aStateMachine
//	{
//		w = acsm->aStateMachine->aNextState[*T];
//
//		if( s.MatchList != NULL )
//		{
//			for( mlist=s.MatchList; mlist!=NULL;
//				mlist=mlist->next )
//			{
//				index = T - mlist->num + 1 - Tx;
			//	PrintMatch (mlist,nline,index);
//				fprintf (stdout, "Match KeyWord %s at %d line %d char\n", mlist->pattern,nline,index);
//			}
//		}
//	}

//	return 0;
//}


void PrintMatch(ACSM_PATTERN * mlist,int nline,int index)
{
		fprintf(stdout,"%s zimu %d xing %d geshu\n",mlist->pattern,nline,index);
}



void acsmSearch (STATEMACHINE * acsm,unsigned char *Tx,int n,int nline)
{
	unsigned char *Tend,*Tc;
	ACSM_PATTERN *mlist;
	STATE *d;
	int index=0;
	Tend=Tx+n;
	Tc=Tx;

	for(;Tx<Tend;Tx++)
	{
		d=acsm->aStateMachine->aNextState[*Tx];
		if(d!=NULL)
		{
			acsm->aStateMachine=d;
			if(d->MatchList!=NULL)
			{
				for(mlist=acsm->aStateMachine->MatchList;mlist!=NULL;mlist=mlist->nextpattern)
				{
					index=Tx-mlist->num+1-Tc;
					PrintMatch(mlist,nline,index);
				}
			}
		}
	}
}



void acsmFree(STATEMACHINE *acsm)           //free the momery
{ 
	int i;
	STATE * s,*r;
	s=acsm->aStateMachine;
	for(i=0;i<ALPHABET_SIZE;i++)
	{
		if(s->aNextState[i]!=ACSM_FAIL_STATE)
		{
			r=s->aNextState[i];
			AC_FREE(r);
		}
	//AC_FREE(s->FailState);
	}
}