Return to path.c CVS log

Up to [Research Unix] / researchv10dc / cmd / twig

Annotation of researchv10dc/cmd/twig/path.c, revision 1.1

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.