pangen4.h

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

/***** spin: pangen4.h *****/

/* Copyright (c) 1997-2003 by Lucent Technologies, Bell Laboratories.     */
/* All Rights Reserved.  This software is for educational purposes only.  */
/* No guarantee whatsoever is expressed or implied by the distribution of */
/* this code.  Permission is given to distribute this code provided that  */
/* this introductory message is not removed and no monies are exchanged.  */
/* Software written by Gerard J. Holzmann.  For tool documentation see:   */
/*             http://spinroot.com/                                       */
/* Send all bug-reports and/or questions to: [e-mail]            */

/* The DFA code below was written by Anuj Puri and Gerard J. Holzmann in  */
/* May 1997, and was inspired by earlier work on data compression using   */
/* sharing tree data structures and graph-encoded sets by J-Ch. Gregoire  */
/* (INRS Telecom, Quebec, Canada) and D.Zampunieris (Univ.Namur, Belgium) */

/* The splay routine code included here is based on the public domain     */
/* version written by D. Sleator <[e-mail]> in 1992.            */

static char *Dfa[] = {
	"#ifdef MA",
	"/*",
	"#include <stdio.h>",
	"#define uchar	unsigned char",
	"*/",
	"#define ulong	unsigned long",
	"#define ushort	unsigned short",
	"",
	"#define TWIDTH		256",
	"#define HASH(y,n)	(n)*(((int)y))",
	"#define INRANGE(e,h)	((h>=e->From && h<=e->To)||(e->s==1 && e->S==h))",
	"",
	"extern char	*emalloc(unsigned long);	/* imported routine  */",
	"extern void	dfa_init(ushort);	/* 4 exported routines */",
	"extern int	dfa_member(ulong);",
	"extern int	dfa_store(uchar *);",
	"extern void	dfa_stats(void);",
	"",
	"typedef struct Edge {",
	"	uchar From, To;		/* max range 0..255 */",
	"	uchar s, S;		/* if s=1, S is singleton */",
	"	struct Vertex	*Dst;",
	"	struct Edge	*Nxt;",
	"} Edge;",
	"",
	"typedef struct Vertex {",
	"	ulong	key, num;	/* key for splay tree, nr incoming edges */",
	"	uchar	from[2], to[2];	/* in-node predefined edge info    */",
	"	struct	Vertex	*dst[2];/* most nodes have 2 or more edges */",
	"	struct	Edge	*Succ;	/* in case there are more edges */",
	"	struct	Vertex	*lnk, *left, *right; /* splay tree plumbing */",
	"} Vertex;",
	"",
	"static Edge	*free_edges;",
	"static Vertex	*free_vertices;",
	"static Vertex	**layers;	/* one splay tree of nodes per layer */",
	"static Vertex	**path;		/* run of word in the DFA */",
	"static Vertex	*R, *F, *NF;	/* Root, Final, Not-Final */",
	"static uchar	*word, *lastword;/* string, and last string inserted */",
	"static int	dfa_depth, iv=0, nv=0, pfrst=0, Tally;",
	"",
	"static void	insert_it(Vertex *, int);	/* splay-tree code */",
	"static void	delete_it(Vertex *, int);",
	"static Vertex	*find_it(Vertex *, Vertex *, uchar, int);",
	"",
	"static void",
	"recyc_edges(Edge *e)",
	"{",
	"	if (!e) return;",
	"	recyc_edges(e->Nxt);",
	"	e->Nxt = free_edges;",
	"	free_edges = e;",
	"}",
	"",
	"static Edge *",
	"new_edge(Vertex *dst)",
	"{	Edge *e;",
	"",
	"	if (free_edges)",
	"	{	e = free_edges;",
	"		free_edges = e->Nxt;",
	"		e->From = e->To = e->s = e->S = 0;",
	"		e->Nxt = (Edge *) 0;",
	"	} else",
	"		e = (Edge *) emalloc(sizeof(Edge));",
	"	e->Dst = dst;",
	"",
	"	return e;",
	"}",
	"",
	"static void",
	"recyc_vertex(Vertex *v)",
	"{",
	"	recyc_edges(v->Succ);",
	"	v->Succ = (Edge *) free_vertices;",
	"	free_vertices = v;",
	"	nr_states--;",
	"}",
	"",
	"static Vertex *",
	"new_vertex(void)",
	"{	Vertex *v;",
	"",
	"	if (free_vertices)",
	"	{	v = free_vertices;",
	"		free_vertices = (Vertex *) v->Succ;",
	"		v->Succ = (Edge *) 0;",
	"		v->num  = 0;",
	"	} else",
	"		v = (Vertex *) emalloc(sizeof(Vertex));",
	"",
	"	nr_states++;",
	"	return v; ",
	"}",
	"",
	"static Vertex *",
	"allDelta(Vertex *v, int n)",
	"{	Vertex *dst = new_vertex();",
	"",
	"	v->from[0] = 0;",
	"	v->to[0] = 255;",
	"	v->dst[0] = dst;",
	"	dst->num = 256;",
	"	insert_it(v, n);",
	"	return dst;",
	"}",
	"",
	"static void",
	"insert_edge(Vertex *v, Edge *e)",
	"{	/* put new edge first */",
	"	if (!v->dst[0])",
	"	{	v->dst[0] = e->Dst;",
	"		v->from[0] = e->From;",
	"		v->to[0] = e->To;",
	"		recyc_edges(e);",
	"		return;",
	"	}",
	"	if (!v->dst[1])",
	"	{	v->from[1] = v->from[0]; v->from[0] = e->From;",
	"		v->to[1]   = v->to[0];   v->to[0]   = e->To;",
	"		v->dst[1]  = v->dst[0];  v->dst[0]  = e->Dst;",
	"		recyc_edges(e);",
	"		return;",
	"	} /* shift */",
	"	{	int f      = v->from[1];",
	"		int t      = v->to[1];",
	"		Vertex *d  = v->dst[1];",
	"		v->from[1] = v->from[0]; v->from[0] = e->From;",
	"		v->to[1]   = v->to[0];   v->to[0]   = e->To;",
	"		v->dst[1]  = v->dst[0];  v->dst[0]  = e->Dst;",
	"		e->From = f;",
	"		e->To   = t;",
	"		e->Dst  = d;",
	"	}",
	"	e->Nxt = v->Succ;",
	"	v->Succ = e;",
	"}",
	"",
	"static void",
	"copyRecursive(Vertex *v, Edge *e)",
	"{	Edge *f;",
	"	if (e->Nxt) copyRecursive(v, e->Nxt);",
	"	f = new_edge(e->Dst);",
	"	f->From = e->From;",
	"	f->To   = e->To;",
	"	f->s    = e->s;",
	"	f->S    = e->S;",
	"	f->Nxt  = v->Succ;",
	"	v->Succ = f;",
	"}",
	"",
	"static void",
	"copyEdges(Vertex *to, Vertex *from)",
	"{	int i;",
	"	for (i = 0; i < 2; i++)",
	"	{	to->from[i] = from->from[i];",
	"		to->to[i]   = from->to[i];",
	"		to->dst[i]  = from->dst[i];",
	"	}",
	"	if (from->Succ) copyRecursive(to, from->Succ);",
	"}",
	"",
	"static Edge *",
	"cacheDelta(Vertex *v, int h, int first)",
	"{	static Edge *ov, tmp;  int i;",
	"",
	"	if (!first && INRANGE(ov,h))",
	"		return ov; /* intercepts about 10%% */",
	"	for (i = 0; i < 2; i++)",
	"		if (v->dst[i] && h >= v->from[i] && h <= v->to[i])",
	"		{	tmp.From = v->from[i];",
	"			tmp.To   = v->to[i];",
	"			tmp.Dst  = v->dst[i];",
	"			tmp.s    =  tmp.S = 0;",
	"			ov = &tmp;",
	"			return ov;",
	"		}",
	"	for (ov = v->Succ; ov; ov = ov->Nxt)",
	"		if (INRANGE(ov,h)) return ov;",
	"",
	"	Uerror(\"cannot get here, cacheDelta\");",
	"	return (Edge *) 0;",
	"}",
	"",
	"static Vertex *",
	"Delta(Vertex *v, int h)	/* v->delta[h] */",
	"{	Edge *e;",
	"",
	"	if (v->dst[0] && h >= v->from[0] && h <= v->to[0])",
	"		return v->dst[0];	/* oldest edge */",
	"	if (v->dst[1] && h >= v->from[1] && h <= v->to[1])",
	"		return v->dst[1];",
	"	for (e = v->Succ; e; e = e->Nxt)",
	"		if (INRANGE(e,h))",
	"			return e->Dst;",
	"	Uerror(\"cannot happen Delta\");",
	"	return (Vertex *) 0;",
	"}",
	"",
	"static void",
	"numDelta(Vertex *v, int d)",
	"{	Edge *e;",
	"	ulong cnt;",
	"	int i;",
	"",
	"	for (i = 0; i < 2; i++)",
	"	if (v->dst[i])",
	"	{	cnt = v->dst[i]->num + d*(1 + v->to[i] - v->from[i]);",
	"		if (d == 1 && cnt < v->dst[i]->num) goto bad;",
	"		v->dst[i]->num = cnt;",
	"	}",
	"	for (e = v->Succ; e; e = e->Nxt)",
	"	{	cnt = e->Dst->num + d*(1 + e->To - e->From + e->s);",
	"		if (d == 1 && cnt < e->Dst->num)",
	"bad:			Uerror(\"too many incoming edges\");",
	"		e->Dst->num = cnt;",
	"	}",
	"}",
	"",
	"static void",
	"setDelta(Vertex *v, int h, Vertex *newdst)	/* v->delta[h] = newdst; */",
	"{	Edge *e, *f = (Edge *) 0, *g;",
	"	int i;",
	"",
	"	/* remove the old entry, if there */",
	"	for (i = 0; i < 2; i++)",
	"		if (v->dst[i] && h >= v->from[i] && h <= v->to[i])",
	"		{	if (h == v->from[i])",
	"			{	if (h == v->to[i])",
	"				{	v->dst[i] = (Vertex *) 0;",
	"					v->from[i] = v->to[i] = 0;",
	"				} else",
	"					v->from[i]++;",
	"			} else if (h == v->to[i])",
	"			{	v->to[i]--;",
	"			} else",
	"			{	g = new_edge(v->dst[i]);/* same dst */",
	"				g->From    = v->from[i];",
	"				g->To      = h-1;	/* left half */",
	"				v->from[i] = h+1;	/* right half */",
	"				insert_edge(v, g);",
	"			}",
	"			goto part2;",
	"		}",
	"	for (e = v->Succ; e; f = e, e = e->Nxt)",
	"	{	if (e->s == 1 && e->S == h)",
	"		{	e->s = e->S = 0;",
	"			goto rem_tst;",
	"		}",
	"		if (h >= e->From && h <= e->To)",
	"		{	if (h == e->From)",
	"			{	if (h == e->To)",
	"				{	if (e->s)",
	"					{	e->From = e->To = e->S;",
	"						e->s = 0;",
	"						break;",
	"					} else",
	"						goto rem_do;",
	"				} else",
	"					e->From++;",
	"			} else if (h == e->To)",
	"			{	e->To--;",
	"			} else				/* split */",
	"			{	g = new_edge(e->Dst);	/* same dst */",
	"				g->From = e->From;",
	"				g->To   = h-1;		/* g=left half */",
	"				e->From = h+1;		/* e=right half */",
	"				g->Nxt  = e->Nxt;	/* insert g */",
	"				e->Nxt  = g;		/* behind e */",
	"				break;			/* done */",
	"			}",
	"",
	"rem_tst:		if (e->From > e->To)",
	"			{	if (e->s == 0) {",
	"rem_do:				if (f)",
	"						f->Nxt = e->Nxt;",
	"					else",
	"						v->Succ = e->Nxt;",
	"					e->Nxt = (Edge *) 0;",
	"					recyc_edges(e);",
	"				} else",
	"				{	e->From = e->To = e->S;",
	"					e->s = 0;",
	"			}	}",
	"			break;",
	"	}	}",
	"part2:",
	"	/* check if newdst is already there */",
	"	for (i = 0; i < 2; i++)",
	"		if (v->dst[i] == newdst)",
	"		{	if (h+1 == (int) v->from[i])",
	"			{	v->from[i] = h;",
	"				return;",
	"			}",
	"			if (h == (int) v->to[i]+1)",
	"			{	v->to[i] = h;",
	"				return;",
	"		}	}",
	"	for (e = v->Succ; e; e = e->Nxt)",
	"	{	if (e->Dst == newdst)",
	"		{	if (h+1 == (int) e->From)",
	"			{	e->From = h;",
	"				if (e->s == 1 && e->S+1 == e->From)",
	"				{	e->From = e->S;",
	"					e->s = e->S = 0;",
	"				}",
	"				return;",
	"			}",
	"			if (h == (int) e->To+1)",
	"			{	e->To = h;",
	"				if (e->s == 1 && e->S == e->To+1)",
	"				{	e->To = e->S;",
	"					e->s = e->S = 0;",
	"				}",
	"				return;",
	"			}",
	"			if (e->s == 0)",
	"			{	e->s = 1;",
	"				e->S = h;",
	"				return;",
	"	}	}	}",
	"	/* add as a new edge */",
	"	e = new_edge(newdst);",
	"	e->From = e->To = h;",
	"	insert_edge(v, e);",
	"}",
	"",
	"static ulong",
	"cheap_key(Vertex *v)",
	"{	ulong vk2 = 0;",
	"",
	"	if (v->dst[0])",
	"	{	vk2 = (ulong) v->dst[0];",
	"		if ((ulong) v->dst[1] > vk2)",
	"			vk2 = (ulong) v->dst[1];",
	"	} else if (v->dst[1])",
	"		vk2 = (ulong) v->dst[1]; ",
	"	if (v->Succ)",
	"	{	Edge *e;",
	"		for (e = v->Succ; e; e = e->Nxt)",
	"			if ((ulong) e->Dst > vk2)",
	"				vk2 = (ulong) e->Dst;",
	"	}",
	"	Tally = (vk2>>2)&(TWIDTH-1);",