![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to path.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig|
Return to path.c CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: #include <stdio.h>
2: #include "common.h"
3: #include "code.h"
4: #include "sym.h"
5: #include "machine.h"
6:
7: /*
8: * Routines to enumerate paths of a tree. Firt call path_setup to
9: * initialize the internal data structure. Each component of the
10: * path may be consecutively retrieved by calling path_getsym.
11: */
12:
13: /*
14: * For trees, a path is defined to be the sequence of nodes and edges
15: * from the root to a leaf. A path is represented here as a list of
16: * path components. Each component is represented by the following
17: * strucutre and may either be a pointer to a node or an integer.
18: * If the integer is i then the next component is the ith child of the
19: * previous component in the list. For example, "a 3 b 1 c" is a path
20: * for the tree "a(x,y,b(c,k))". The tag field indicates whether the
21: * component is a node or a branch.
22: * When the component represents a node then the node field points
23: * the corresponding Node structure. When the component is a branch then
24: * branch is the index of the current branch followed (1 is leftmost...)
25: * and node is a list of all unexamined children.
26: */
27: struct path {
28: int tag;
29: #define P_NODE 0
30: #define P_BRANCH 1
31: int branch;
32: Node *node;
33: };
34:
35: /*
36: * The path component list is stored in the path array. Path_length
37: * is the length of the path. Path_ptr points to the first unread
38: * component of the path component list. (see path_getsym
39: * and path_build for details)
40: */
41: struct path path[2*MAXPATH];
42: static int path_length;
43: static struct path *path_ptr = NULL;
44:
45: /*
46: * Given a tree, path_setup updates the path array with the leftmost
47: * of a subtree starting at root. The leftmost path is produced by
48: * following the leftmost branch of every encountered interior node
49: * starting at the root. Note that this routine can be used to layout
50: * the leftmost branch of a subtree into part of the path array and for
51: * initializing the path array with the leftmost path of the whole tree.
52: */
53: void
54: path_setup(root)
55: Node *root;
56: {
57: for(;;) {
58: register struct path *pp = &path[path_length++];
59: Node *ep;
60: assert (root!=NULL);
61:
62: /* Place node in the component list */
63: pp->tag = P_NODE;
64: pp->node = root;
65:
66: /* If leaf encountered exit */
67: if ((ep=root->children)==NULL)
68: break;
69:
70: /*
71: * Mark that the left branch (i.e. 1st in our numbering
72: * scheme) was followed.
73: */
74: pp = &path[path_length++];
75: pp->tag = P_BRANCH;
76: pp->branch = 1;
77: pp->node = ep->siblings;
78: root = ep;
79: }
80: path_ptr = path;
81: }
82:
83: /*
84: * Path_build generates the next path of the tree and returns 0 if
85: * there are no more paths. Each path can be associated
86: * with exactly one leaf. Hence the ordering of paths generated by
87: * this routine is the same as a left to right ordering of the leaves.
88: */
89: path_build()
90: {
91: Node *np, *ep;
92: struct path *pp = &path[path_length-1];
93:
94: /*
95: * Assert that the end of the last path was indeed
96: * a leaf.
97: */
98: assert (pp->tag == P_NODE);
99: assert ((pp->node)->children == NULL);
100:
101: /*
102: * back up until we find a node that still has children
103: */
104: pp--;
105: while (pp >= &path[1] && pp->node==NULL) pp -= 2;
106:
107: /*
108: * If we hit the beginning of the path array, there are
109: * no more leaves and hence no more paths.
110: */
111: if (pp < &path[1]) {
112: /* reset path_length */
113: path_length = 0;
114: return(0);
115: }
116:
117: /*
118: * append the new leftmost branch onto the rest of
119: * the path component list.
120: */
121: pp->branch++;
122: np = pp->node;
123: pp->node = np->siblings;
124: path_length = pp-path+1;
125: path_setup(np);
126: return(1);
127: }
128:
129: /*
130: * Get the next component in the path component list.
131: * When the end of a path is reached, NULL is returned and
132: * the next call will retrieve the first component of the next path.
133: * EOF is returned if there are no more paths.
134: * A return value of 1 indicates that the value returned in mi is
135: * valid.
136: */
137: int
138: path_getsym(mi)
139: register struct machine_input *mi;
140: {
141: if(path_ptr > &path[path_length]) {
142: /*
143: * When the end of that path is passed, generate the
144: * next path.
145: */
146: if(!path_build())
147: return(EOF);
148: path_ptr = path;
149: }
150: if (path_ptr == &path[path_length]) {
151: /*
152: * Path_ptr just encountered the end of
153: * the path, return a marker value
154: * to notify caller.
155: */
156: mi->value = 0;
157: path_ptr++;
158: return(NULL);
159: } else if (path_ptr->tag != P_BRANCH) {
160: /*
161: * Translate the right machine input value
162: */
163: mi->sym = (path_ptr->node)->sym;
164: switch((mi->sym)->attr) {
165:
166: case A_NODE:
167: mi->value = MV_NODE((mi->sym)->unique);
168: break;
169:
170: case A_LABEL:
171: mi->value = MV_LABEL((mi->sym)->unique);
172: break;
173:
174: default:
175: assert(0);
176: }
177: } else {
178: mi->value = MV_BRANCH(path_ptr->branch);
179: }
180: path_ptr++;
181: return(1);
182: }
183:
184: /*
185: * Prints out path for debugging
186: */
187: void
188: prpath()
189: {
190: register int i;
191: for(i=0; i < path_length; i++) {
192: struct path *pp = &path[i];
193: if (pp->tag==P_NODE) {
194: struct node *np = pp->node;
195: printf("[%s]", (np->sym)->name);
196: } else {
197: assert (pp->tag == P_BRANCH);
198: printf("%d", pp->branch);
199: }
200: }
201: putchar('\n');
202:
203: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.