pangen4.h

对软件进行可达性测试的软件

	"	return v->key;",
	"}",
	"",
	"static ulong",
	"mk_key(Vertex *v)	/* not sensitive to order */",
	"{	ulong m = 0, vk2 = 0;",
	"	Edge *e;",
	"",
	"	if (v->dst[0])",
	"	{	m += HASH(v->dst[0], v->to[0] - v->from[0] + 1);",
	"		vk2 = (ulong) v->dst[0]; ",
	"	}",
	"	if (v->dst[1])",
	"	{	m += HASH(v->dst[1], v->to[1] - v->from[1] + 1);",
	"		if ((ulong) v->dst[1] > vk2) vk2 = (ulong) v->dst[1]; ",
	"	}",
	"	for (e = v->Succ; e; e = e->Nxt)",
	"	{	m += HASH(e->Dst, e->To - e->From + 1 + e->s);",
	"		if ((ulong) e->Dst > vk2) vk2 = (ulong) e->Dst; ",
	"	}",
	"	Tally = (vk2>>2)&(TWIDTH-1);",
	"	return m;",
	"}",
	"",
	"static ulong",
	"mk_special(int sigma, Vertex *n, Vertex *v)",
	"{	ulong m = 0, vk2 = 0;",
	"	Edge *f;",
	"	int i;",
	"",
	"	for (i = 0; i < 2; i++)",
	"		if (v->dst[i])",
	"		{	if (sigma >= v->from[i] && sigma <= v->to[i])",
	"			{	m += HASH(v->dst[i], v->to[i]-v->from[i]);",
	"				if ((ulong) v->dst[i] > vk2",
	"				&&   v->to[i] > v->from[i])",
	"					vk2 = (ulong) v->dst[i]; ",
	"			} else",
	"			{	m += HASH(v->dst[i], v->to[i]-v->from[i]+1);",
	"				if ((ulong) v->dst[i] > vk2)",
	"					vk2 = (ulong) v->dst[i]; ",
	"		}	}",
	"	for (f = v->Succ; f; f = f->Nxt)",
	"	{	if (sigma >= f->From && sigma <= f->To)",
	"		{	m += HASH(f->Dst, f->To - f->From + f->s);",
	"			if ((ulong) f->Dst > vk2",
	"			&&   f->To - f->From + f->s > 0)",
	"				vk2 = (ulong) f->Dst; ",
	"		} else if (f->s == 1 && sigma == f->S)",
	"		{	m += HASH(f->Dst, f->To - f->From + 1);",
	"			if ((ulong) f->Dst > vk2) vk2 = (ulong) f->Dst; ",
	"		} else",
	"		{	m += HASH(f->Dst, f->To - f->From + 1 + f->s);",
	"			if ((ulong) f->Dst > vk2) vk2 = (ulong) f->Dst; ",
	"	}	}",
	"",
	"	if ((ulong) n > vk2) vk2 = (ulong) n; ",
	"	Tally = (vk2>>2)&(TWIDTH-1);",
	"	m += HASH(n, 1);",
	"	return m;",
	"}",
	"",
	"void ",
	"dfa_init(ushort nr_layers)",
	"{	int i; Vertex *r, *t;",
	"",
	"	dfa_depth = nr_layers;	/* one byte per layer */",
	"	path   = (Vertex **) emalloc((dfa_depth+1)*sizeof(Vertex *));",
	"	layers = (Vertex **) emalloc(TWIDTH*(dfa_depth+1)*sizeof(Vertex *));",
	"	lastword = (uchar *) emalloc((dfa_depth+1)*sizeof(uchar));",
	"	lastword[dfa_depth] = lastword[0] = 255;",
	"	path[0] = R = new_vertex(); F = new_vertex();",
	"",
	"	for (i = 1, r = R; i < dfa_depth; i++, r = t)",
	"		t = allDelta(r, i-1);",
	"	NF = allDelta(r, i-1);",
	"}",
	"",
	"#if 0",
	"static void complement_dfa(void) { Vertex *tmp = F; F = NF; NF = tmp; }",
	"#endif",
	"",
	"double",
	"tree_stats(Vertex *t)",
	"{	Edge *e; double cnt=0.0;",
	"	if (!t) return 0;",
	"	if (!t->key) return 0;",
	"	t->key = 0; /* precaution */",
	"	if (t->dst[0]) cnt++;",
	"	if (t->dst[1]) cnt++;",
	"	for (e = t->Succ; e; e = e->Nxt)",
	"		cnt++;",
	"	cnt += tree_stats(t->lnk);",
	"	cnt += tree_stats(t->left);",
	"	cnt += tree_stats(t->right);",
	"	return cnt;",
	"}",
	"",
	"void",
	"dfa_stats(void)",
	"{	int i, j; double cnt = 0.0;",
	"	for (j = 0; j < TWIDTH; j++)",
	"	for (i = 0; i < dfa_depth+1; i++)",
	"		cnt += tree_stats(layers[i*TWIDTH+j]);",
	"	printf(\"Minimized Automaton:\t%%6d nodes and %%6g edges\\n\",",
	"		nr_states, cnt);",
	"}",
	"",
	"int",
	"dfa_member(ulong n)",
	"{	Vertex **p, **q;",
	"	uchar *w = &word[n];",
	"	int i;",
	"",
	"	p = &path[n]; q = (p+1);",
	"	for (i = n; i < dfa_depth; i++)",
	"		*q++ = Delta(*p++, *w++);",
	"	return (*p == F);",
	"}",
	"",
	"int",
	"dfa_store(uchar *sv)",
	"{	Vertex **p, **q, *s, *y, *old, *new = F;",
	"	uchar *w, *u = lastword;",
	"	int i, j, k;",
	"",
	"	w = word = sv;",
	"	while (*w++ == *u++)	/* find first byte that differs */",
	"		;",
	"	pfrst = (int) (u - lastword) - 1;",
	"	memcpy(&lastword[pfrst], &sv[pfrst], dfa_depth-pfrst);",
	"	if (pfrst > iv) pfrst = iv;",
	"	if (pfrst > nv) pfrst = nv;",
	"/* phase1: */",
	"	p = &path[pfrst]; q = (p+1); w = &word[pfrst];",
	"	for (i = pfrst; i < dfa_depth; i++)",
	"		*q++ = Delta(*p++, *w++);	/* (*p)->delta[*w++]; */",
	"",
	"	if (*p == F) return 1;	/* it's already there */",
	"/* phase2: */",
	"	iv = dfa_depth;",
	"	do {	iv--;",
	"		old = new;",
	"		new = find_it(path[iv], old, word[iv], iv);",
	"	} while (new && iv > 0);",
	"",
	"/* phase3: */",
	"	nv = k = 0; s = path[0];",
	"	for (j = 1; j <= iv; ++j) ",
	"		if (path[j]->num > 1)",
	"		{	y = new_vertex();",
	"			copyEdges(y, path[j]);",
	"			insert_it(y, j);",
	"			numDelta(y, 1);",
	"			delete_it(s, j-1);",
	"			setDelta(s, word[j-1], y);",
	"			insert_it(s, j-1);",
	"			y->num = 1;	/* initial value 1 */",
	"			s = y;",
	"			path[j]->num--;	/* only 1 moved from j to y */",
	"			k = 1;",
	"		} else",
	"		{	s = path[j];",
	"			if (!k) nv = j;",
	"		}",
	"	y = Delta(s, word[iv]);",
	"	y->num--;",
	"	delete_it(s, iv); ",
	"	setDelta(s, word[iv], old);",
	"	insert_it(s, iv); ",
	"	old->num++;",
	"",
	"	for (j = iv+1; j < dfa_depth; j++)",
	"		if (path[j]->num == 0)",
	"		{	numDelta(path[j], -1);",
	"			delete_it(path[j], j);",
	"			recyc_vertex(path[j]);",
	"		} else",
	"			break;",
	"	return 0;",
	"}",
	"",
	"static Vertex *",
	"splay(ulong i, Vertex *t)",
	"{	Vertex N, *l, *r, *y;",
	"",
	"	if (!t) return t;",
	"	N.left = N.right = (Vertex *) 0;",
	"	l = r = &N;",
	"	for (;;)",
	"	{	if (i < t->key)",
	"		{	if (!t->left) break;",
	"			if (i < t->left->key)",
	"			{	y = t->left;",
	"				t->left = y->right;",
	"				y->right = t;",
	"				t = y;",
	"				if (!t->left) break;",
	"			}",
	"			r->left = t;",
	"			r = t;",
	"			t = t->left;",
	"		} else if (i > t->key)",
	"		{	if (!t->right) break;",
	"			if (i > t->right->key)",
	"			{	y = t->right;",
	"				t->right = y->left;",
	"				y->left = t;",
	"				t = y;",
	"				if (!t->right) break;",
	"			}",
	"			l->right = t;",
	"			l = t;",
	"			t = t->right;",
	"		} else",
	"			break;",
	"	}",
	"	l->right = t->left;",
	"	r->left = t->right;",
	"	t->left = N.right;",
	"	t->right = N.left;",
	"	return t;",
	"}",
	"",
	"static void",
	"insert_it(Vertex *v, int L)",
	"{	Vertex *new, *t;",
	"	ulong i; int nr;",
	"",
	"	i = mk_key(v);",
	"	nr = ((L*TWIDTH)+Tally);",
	"	t = layers[nr];",
	"",
	"	v->key = i; ",
	"	if (!t)",
	"	{	layers[nr] = v;",
	"		return;",
	"	}",
	"	t = splay(i, t);",
	"	if (i < t->key)",
	"	{	new = v;",
	"		new->left = t->left;",
	"		new->right = t;",
	"		t->left = (Vertex *) 0;",
	"	} else if (i > t->key)",
	"	{	new = v;",
	"		new->right = t->right;",
	"		new->left = t;",
	"		t->right = (Vertex *) 0;",
	"	} else	 /* it's already there */",
	"	{	v->lnk = t->lnk; /* put in linked list off v */",
	"		t->lnk = v;",
	"		new = t;",
	"	}",
	"	layers[nr] = new;",
	"}",
	"",
	"static int",
	"checkit(Vertex *h, Vertex *v, Vertex *n, uchar sigma)",
	"{	Edge *g, *f;",
	"	int i, k, j = 1;",
	"",
	"	for (k = 0; k < 2; k++)",
	"		if (h->dst[k])",
	"		{	if (sigma >= h->from[k] && sigma <= h->to[k])",
	"			{	if (h->dst[k] != n) goto no_match;",
	"			}",
	"			for (i = h->from[k]; i <= h->to[k]; i++)",
	"			{	if (i == sigma) continue;",
	"				g = cacheDelta(v, i, j); j = 0;",
	"				if (h->dst[k] != g->Dst)",
	"					goto no_match;",
	"				if (g->s == 0 || g->S != i)",
	"					i = g->To;",
	"		}	}",
	"	for (f = h->Succ; f; f = f->Nxt)",
	"	{	if (INRANGE(f,sigma))",
	"		{	if (f->Dst != n) goto no_match;",
	"		}",
	"		for (i = f->From; i <= f->To; i++)",
	"		{	if (i == sigma) continue;",
	"			g = cacheDelta(v, i, j); j = 0;",
	"			if (f->Dst != g->Dst)",
	"				goto no_match;",
	"			if (g->s == 1 && i == g->S)",
	"				continue;",
	"			i = g->To;",
	"		}",
	"		if (f->s && f->S != sigma)",
	"		{	g = cacheDelta(v, f->S, 1);",
	"			if (f->Dst != g->Dst)",
	"				goto no_match;",
	"		}",
	"	}",
	"	if (h->Succ || h->dst[0] || h->dst[1]) return 1;",
	"no_match:",
	"	return 0;",
	"}",
	"",
	"static Vertex *",
	"find_it(Vertex *v, Vertex *n, uchar sigma, int L)",
	"{	Vertex *z, *t;",
	"	ulong i; int nr;",
	"",
	"	i = mk_special(sigma,n,v);",
	"	nr = ((L*TWIDTH)+Tally);",
	"	t = layers[nr];",
	"",
	"	if (!t) return (Vertex *) 0;",
	"	layers[nr] = t = splay(i, t);",
	"	if (i == t->key)",
	"	for (z = t; z; z = z->lnk)",
	"		if (checkit(z, v, n, sigma))",
	"			return z;",
	"",
	"	return (Vertex *) 0;",
	"}",
	"",
	"static void",
	"delete_it(Vertex *v, int L)",
	"{	Vertex *x, *t;",
	"	ulong i; int nr;",
	"",
	"	i = cheap_key(v);",
	"	nr = ((L*TWIDTH)+Tally);",
	"	t = layers[nr];",
	"	if (!t) return;",
	"",
	"	t = splay(i, t);",
	"	if (i == t->key)",
	"	{	Vertex *z, *y = (Vertex *) 0;",
	"		for (z = t; z && z != v; y = z, z = z->lnk)",
	"			;",
	"		if (z != v) goto bad;",
	"		if (y)",
	"		{	y->lnk = z->lnk;",
	"			z->lnk = (Vertex *) 0;",
	"			layers[nr] = t;",
	"			return;",
	"		} else if (z->lnk)	/* z == t == v */",
	"		{	y = z->lnk;",
	"			y->left = t->left;",
	"			y->right = t->right;",
	"			t->left = t->right = t->lnk = (Vertex *) 0;",
	"			layers[nr] = y;",
	"			return;",
	"		}",
	"		/* delete the node itself */",
	"		if (!t->left)",
	"		{	x = t->right;",
	"		} else",
	"		{	x = splay(i, t->left);",
	"			x->right = t->right;",
	"		}",
	"		t->left = t->right = t->lnk = (Vertex *) 0;",
	"		layers[nr] = x;",
	"		return;",
	"	}",
	"bad:	Uerror(\"cannot happen delete\");",
	"}",
	"#endif", /* MA */
	0,
};