#include "common.h"#include "code.h"#include "sym.h"#include "machine.h" /* * Routines to enumerate paths of a tree.  Firt call path_setup to * initialize the internal data structure.  Each component of the * path may be consecutively retrieved by calling path_getsym. */ /* * For trees, a path is defined to be the sequence of nodes and edges * from the root to a leaf.  A path is represented here as a list of * path components.  Each component is represented by the following * strucutre and may either be a pointer to a node or an integer. * If the integer is i then the next component is the ith child of the * previous component in the list.  For example, "a 3 b 1 c" is a path * for the tree "a(x,y,b(c,k))".  The tag field indicates whether the * component is a node or a branch. *	When the component represents a node then the node field points * the corresponding Node structure.  When the component is a branch then * branch is the index of the current branch followed (1 is leftmost...) * and node is a list of all unexamined children. */struct path {	int tag;#define		P_NODE	0#define		P_BRANCH	1	int branch;	Node *node;}; /* * The path component list is stored in the path array.  Path_length * is the length of the path.  Path_ptr points to the first unread * component of the path component list. (see path_getsym * and path_build for details) */#define MAXPATH 64struct path path[MAXPATH];static int path_length;static struct path *path_ptr = NULL; /* * Given a tree, path_setup updates the path array with the leftmost * of a subtree starting at root.  The leftmost path is produced by * following the leftmost branch of every encountered interior node  * starting at the root.  Note that this routine can be used to layout * the leftmost branch of a subtree into part of the path array and for * initializing the path array with the leftmost path of the whole tree. */voidpath_setup(Node *root){	for(;;) {		register struct path *pp = &path[path_length++];		Node *ep;		assert (root!=NULL); 		if(path_length > MAXPATH)			error(1, "maxpathlength exceeded"); 		/* Place node in the component list */		pp->tag = P_NODE;		pp->node = root; 		/* If leaf encountered exit */		if ((ep=root->children)==NULL)			break; 		/*		 * Mark that the left branch (i.e. 1st in our numbering		 * scheme) was followed.		 */		pp = &path[path_length++];		if(path_length > MAXPATH)			error(1, "maxpathlength exceeded");		pp->tag = P_BRANCH;		pp->branch = 1;		pp->node = ep->siblings;		root = ep;	}	path_ptr = path;} /* * Path_build generates the next path of the tree and returns 0 if * there are no more paths.  Each path can be associated * with exactly one leaf.  Hence the ordering of paths generated by * this routine is the same as a left to right ordering of the leaves. */intpath_build(void){	Node *np;	struct path *pp = &path[path_length-1]; 	/*	 * Assert that the end of the last path was indeed	 * a leaf.	 */	assert (pp->tag == P_NODE);	assert ((pp->node)->children == NULL); 	/*	 * back up until we find a node that still has children	 */	pp--;	while (pp >= &path[1] && pp->node==NULL) pp -= 2; 	/*	 * If we hit the beginning of the path array, there are	 * no more leaves and hence no more paths.	 */	if(pp < &path[1]) {		/* reset path_length */		path_length = 0;		return 0;	} 	/*	 * append the new leftmost branch onto the rest of	 * the path component list.	 */	pp->branch++;	np = pp->node;	pp->node = np->siblings;	path_length = pp-path+1;	path_setup(np);	return 1;} /* * Get the next component in the path component list. * When the end of a path is reached, NULL is returned and * the next call will retrieve the first component of the next path. * EOF is returned if there are no more paths. * A return value of 1 indicates that the value returned in mi is * valid. */intpath_getsym(struct machine_input *mi){	if(path_ptr > &path[path_length]) {		/*		 * When the end of that path is passed, generate the		 * next path.		 */		if(!path_build())			return -1;		path_ptr = path;	}	if(path_ptr == &path[path_length]){		/*		 * Path_ptr just encountered the end of		 * the path, return a marker value		 * to notify caller.		 */		mi->value = 0;		path_ptr++;		return 0;	}else if(path_ptr->tag != P_BRANCH){		/*		 * Translate the right machine input value		 */		mi->sym = (path_ptr->node)->sym;		switch(mi->sym->attr){		case A_NODE:			mi->value = MV_NODE((mi->sym)->unique);			break;		case A_LABEL:			mi->value = MV_LABEL((mi->sym)->unique);			break;		default:			assert(0);		}	}else		mi->value = MV_BRANCH(path_ptr->branch);	path_ptr++;	return 1;} /* * Prints out path for debugging */voidprpath(void){	int i;	struct path *pp; 	for(i = 0; i < path_length; i++) {		pp = &path[i];		if(pp->tag==P_NODE)			print("[%s]", pp->node->sym->name);		else{			assert (pp->tag == P_BRANCH);			print("%d", pp->branch);		}	}	print("\n");}