User:Antigng-bot/regex/DFAOptimize

#include <stdlib.h>
#include "mem.h"
#include "regexFrontEnd.h"
#include "NFARuntime.h"
#include "DFAProcess.h"
#include "DFAMinimize.h"
#include "struct.h"

struct _DFAOStackElem
{
	int state;
	int count;
	int flag;
	struct _DFAOStackElem *next;
};
struct _DFAOStackElem *DFAOStackSP=NULL;

static int DFAOStackPop()
{
	struct _DFAOStackElem *temp=DFAOStackSP;
	int state=DFAOStackSP->state;
	DFAOStackSP=DFAOStackSP->next;
	s_free(temp);
	return state;
}
static int DFAOStackIsNull()
{
	return !DFAOStackSP;
}
static void DFAOStackLock()
{
	if(DFAOStackSP) DFAOStackSP->flag=1;
	return;
}
static void DFAOStackPush(int state,int count)
{
	struct _DFAOStackElem *pre_state=NULL;
	struct _DFAOStackElem *cur_state=DFAOStackSP;
	while(cur_state)
	{
		if(cur_state->flag) break;
		if(cur_state->count<=count) break;
		pre_state=cur_state;
		cur_state=cur_state->next;
	}
	if(pre_state)
	{
		cur_state=(struct _DFAOStackElem *)s_calloc(1,sizeof(struct _DFAOStackElem));
		cur_state->next=pre_state->next;
		pre_state->next=cur_state;
		cur_state->flag=0;
		cur_state->state=state;
		cur_state->count=count;
	}
	else
	{
		cur_state=(struct _DFAOStackElem *)s_calloc(1,sizeof(struct _DFAOStackElem));
		cur_state->next=DFAOStackSP;
		DFAOStackSP=cur_state;
		cur_state->flag=0;
		cur_state->state=state;
		cur_state->count=count;
	}
	return;
}
int ODFATop=0;
int *ODFAForwardConv=NULL;
int *ODFABackwardConv=NULL;
static void DFAOIni()
{
	int count=0;
	ODFAForwardConv=(int *)s_calloc(MDFATop,sizeof(int));
	ODFABackwardConv=(int *)s_calloc(MDFATop,sizeof(int));
	for(;count<MDFATop;count++)
	{
		ODFAForwardConv[count]=-1;
	}
	ODFATop=0;
	return;
}
static void DFAOSaveSubStates(struct _DFANode state)
{
	struct _DFACharChain *action=state.actionlist;
	int *local=(int *)s_calloc(MDFATop,sizeof(int));
	while(action)
	{
		if(ODFAForwardConv[action->state]==-1)
		{
			local[action->state]++;
		}
		action=action->next;
	}
	action=state.actionlist;
	DFAOStackLock();
	while(action)
	{
		if(local[action->state])
		{
			DFAOStackPush(action->state,local[action->state]);
			local[action->state]=0;
		}
		action=action->next;
	}
	s_free(local);
	return;
}
static void DFAOArrangeStates(int ini_state)
{
	DFAOStackPush(ini_state,0);
	do
	{
		int state=DFAOStackPop();
		if(ODFAForwardConv[state]==-1)
		{
			ODFABackwardConv[ODFATop]=state;
			ODFAForwardConv[state]=ODFATop;
			ODFATop++;
			DFAOSaveSubStates(MDFAStates[state]);
		}
	}while(!DFAOStackIsNull());
	return;
}
struct _DFANode *ODFAStates=NULL;

static struct _DFACharChain *DFAOForkActionlist(const struct _DFACharChain *actionlist)
{
	struct _DFACharChain *fork_actionlist=NULL,*cur=NULL;
	if(actionlist)
	{
		fork_actionlist=(struct _DFACharChain *)s_calloc(1,sizeof(struct _DFACharChain));
		fork_actionlist->ch=actionlist->ch;
		fork_actionlist->state=ODFAForwardConv[actionlist->state];
		actionlist=actionlist->next;
		cur=fork_actionlist;
	}
	else return NULL;
	while(actionlist)
	{
		cur->next=(struct _DFACharChain *)s_calloc(1,sizeof(struct _DFACharChain));
		cur=cur->next;
		cur->ch=actionlist->ch;
		cur->state=ODFAForwardConv[actionlist->state];
		actionlist=actionlist->next;
	}
	return fork_actionlist;
}

static void DFAOPostProcess()
{
	int state=0;
	ODFAStates=(struct _DFANode *)s_calloc(ODFATop,sizeof(struct _DFANode));
	for(;state<ODFATop;state++)
	{
		ODFAStates[state].type=MDFAStates[ODFABackwardConv[state]].type;
		ODFAStates[state].actionlist=DFAOForkActionlist(MDFAStates[ODFABackwardConv[state]].actionlist);
	}
	s_free(ODFAForwardConv);
	s_free(ODFABackwardConv);
	return;
}

void DFAOptimize(int ini_state)
{
	DFAOIni();
	DFAOArrangeStates(ini_state);
	DFAOPostProcess();
	return;
}