使用者:Antigng-bot/regex/DFAProcess

#include <stdlib.h>
#include "mem.h"
#include "regexFrontEnd.h"
#include "NFARuntime.h"
#include "DFAProcess.h"
#include "struct.h"
static int DFASubsetInChain(struct _NFANode *subset,struct _DFASubsetChain *chain)
{
	while(chain)
	{
		if(chain->subset>subset) return 0;
		else if(chain->subset==subset) return 1;
		chain=chain->next;
	}
	return 0;
}
static struct _DFASubsetChain *DFAMergeChains(struct _DFASubsetChain *chain1,struct _DFASubsetChain *chain2)
{
	struct _DFASubsetChain p;
	struct _DFASubsetChain *head=&p,*cur=head;
	p.next=NULL;
	while((chain1)&&(chain2))
	{
		if(chain1->subset<chain2->subset)
		{
			cur->next=chain1;
			chain1=chain1->next;
			cur=cur->next;
			cur->next=0;
		}
		else
		{
			cur->next=chain2;
			chain2=chain2->next;
			cur=cur->next;
			cur->next=0;
		}
	}
	if(chain1)
	{
		cur->next=chain1;
	}
	else if(chain2)
	{
		cur->next=chain2;
	}
	return p.next;
}
static struct _DFASubsetChain *DFAAddSubsetToChain(struct _NFANode *subset,struct _DFASubsetChain *chain)
{
	struct _DFASubsetChain *node=(struct _DFASubsetChain *)s_calloc(sizeof(struct _DFASubsetChain),1);
	node->subset=subset;
	return DFAMergeChains(chain,node);
}
static struct _DFASubsetChain *DFACreateSubsetChain(struct _DFASubsetChain *head,struct _NFANode *NFAStart)
{
	struct queue *visitQueue=queueini();
	struct _NFANode *node=NFAStart;
	queuepush(visitQueue,NFAStart);
	do
	{
		queuepop(visitQueue,(void **)&node);
		if(!DFASubsetInChain(node,head))
		{
			head=DFAAddSubsetToChain(node,head);
			if(node->edgetable)
			{
				struct _NodeEdgeList *p=NULL;
				if(int_hashquery(node->edgetable,0,(void **)&p))
				{
					while(p)
					{
						queuepush(visitQueue,p->edge);
						p=p->next;
					}
				}
			}
		}
	}while(!queueisnull(visitQueue));
	s_free(visitQueue);
	return head;
}
struct _DFASubsetChain *getSubsetChain(struct _NFANode *NFAStart)
{
	return DFACreateSubsetChain(NULL,NFAStart);
}
struct _DFANode *DFAStates=NULL;
int DFALimit=0;
int DFATop=0;
static void DFAIni(void)
{
	DFAStates=(struct _DFANode *)s_calloc(sizeof(struct _DFANode)*(nodecount+32)*1024,1);
	DFALimit=(nodecount+32)*1024;
	DFATop=0;
	return;
}

static int DFASubsetChainCompare(const struct _DFASubsetChain *chain1,const struct _DFASubsetChain *chain2)
{
	while(chain1&&chain2)
	{
		if(chain1->subset!=chain2->subset) return 1;
		chain1=chain1->next;
		chain2=chain2->next;
	}
	return chain1||chain2;
}
static int DFAMatchStates(const struct _DFASubsetChain *chain)
{
	int count=0;
	for(;count<DFATop;count++)
	{
		if(!DFASubsetChainCompare(DFAStates[count].id,chain)) return count;
	}
	return -1;
}

static int DFAStateIsEnd(const struct _DFASubsetChain *chain)
{
	while(chain)
	{
		if(!chain->subset->edgetable) return 1;
		chain=chain->next;
	}
	return 0;
}

static struct _DFASubsetChain *DFAGetNextSubset(unsigned int ch,const struct _DFASubsetChain *cur)
{
	struct _DFASubsetChain *follow=NULL;
	while(cur)
	{
		struct _NodeEdgeList *p=NULL;
		if(cur->subset->edgetable)
		{
			if(int_hashquery(cur->subset->edgetable,ch,(void **)&p))
			{
				while(p)
				{
					follow=DFACreateSubsetChain(follow,p->edge);
					p=p->next;
				}
			}
		}
		cur=cur->next;
	}
	return follow;
}
static struct _DFACharChain *DFAMergeAction(struct _DFACharChain *chain1,struct _DFACharChain *chain2)
{
	struct _DFACharChain p;
	struct _DFACharChain *head=&p,*cur=head;
	p.next=NULL;
	while((chain1)&&(chain2))
	{
		if(chain1->ch<chain2->ch)
		{
			cur->next=chain1;
			chain1=chain1->next;
			cur=cur->next;
			cur->next=0;
		}
		else
		{
			cur->next=chain2;
			chain2=chain2->next;
			cur=cur->next;
			cur->next=0;
		}
	}
	if(chain1)
	{
		cur->next=chain1;
	}
	else if(chain2)
	{
		cur->next=chain2;
	}
	return p.next;
}
static struct _DFACharChain *DFAAddCharToActionlist(unsigned int ch,struct _DFACharChain *chain)
{
	struct _DFACharChain *node=(struct _DFACharChain *)s_calloc(sizeof(struct _DFACharChain),1);
	node->ch=ch;
	node->state=0;
	return DFAMergeAction(chain,node);
}
static int DFACharInAction(unsigned int ch,struct _DFACharChain *chain)
{
	while(chain)
	{
		if(chain->ch>ch) return 0;
		else if(chain->ch==ch) return 1;
		chain=chain->next;
	}
	return 0;
}
static struct _DFACharChain *DFACreateActionList(const struct _DFASubsetChain *chain)
{
	struct _DFACharChain *action=NULL;
	while(chain)
	{
		if(chain->subset->validchar)
		{
			struct _NodeCharList *chlist=chain->subset->validchar;
			while(chlist)
			{
				if(chlist->ch&&(!DFACharInAction(chlist->ch,action)))
				{
					action=DFAAddCharToActionlist(chlist->ch,action);
				}
				chlist=chlist->next;
			}
		}
		chain=chain->next;
	}
	return action;
}
static int DFAAddNewState(struct _DFASubsetChain *chain)
{
	if(DFATop==DFALimit) return 1;
	DFAStates[DFATop].id=chain;
	DFAStates[DFATop].type=DFAStateIsEnd(chain);
	DFAStates[DFATop].actionlist=DFACreateActionList(chain);
	DFATop++;
	return 0;

}
static void DFAFreeSubsetChain(struct _DFASubsetChain *chain)
{
	struct _DFASubsetChain *pre=chain;
	while(chain)
	{
		pre=chain->next;
		s_free(chain);
		chain=pre;
	}
	return;
}
int ConvertNFAToDFA(struct _NFAType *NFA)
{
	int count=0;
	struct _DFASubsetChain *chain=DFACreateSubsetChain(NULL,NFA->begin);
	DFAIni();
	if(DFAAddNewState(chain)) return 1;
	for(count=0;count<DFATop;count++)
	{
		struct _DFACharChain *action=DFAStates[count].actionlist;
		struct _DFASubsetChain *cur=DFAStates[count].id;
		struct _DFASubsetChain *follow=NULL;
		while(action)
		{
			int state=0;
			follow=DFAGetNextSubset(action->ch,cur);
			if(0>(state=DFAMatchStates(follow)))
			{
				if(DFAAddNewState(follow)) return 1;
				action->state=DFATop-1;
			}
			else
			{
				DFAFreeSubsetChain(follow);
				action->state=state;
			}
			action=action->next;
		}
	}
	return 0;
}