Return to 3.reach.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin / struct

Annotation of 43BSDTahoe/usr.bin/struct/3.reach.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)3.reach.c  4.1     (Berkeley)      2/11/83";
        !             3: #endif not lint
        !             4: 
        !             5: #include <stdio.h>
        !             6: #
        !             7: /*
        !             8: set REACH[v] = w if w is only node outside subtree of v which is reached from within
        !             9:        subtree of v, REACH[v] = UNDEFINED otherwise
        !            10: */
        !            11: #include "def.h"
        !            12: 
        !            13: /* strategy in obtaining REACH(v) for each node v:
        !            14: Since only need to know whether there is exactly one exit from subtree of v,
        !            15: need keep track only of 2 farthest exits from each subtree rather than all exits.
        !            16: The first may be the unique exit, while the second is used when the children
        !            17: of a node has the same first exit.
        !            18: To obtain 2 farthest exits of v, look at 2 farthest exits of children of v and
        !            19: the nodes entered by arcs from v.  Farthest exits are identified by numbering
        !            20: the nodes from -2 to -(accessnum-2) starting at the bottom left corner of tree
        !            21: using procedure number().  The farthest exit from the subtree of v is the one
        !            22: with the least number according NUM to this numbering.  If a node w is an exit from the
        !            23: subtree of v, then NUM(w) < NUM(v).  The negative numbers allow NUM(v) to be stored
        !            24: in the same location as REACH(v).  REACH(w) may already be set when an arc (v,w) to a child
        !            25: is searched, but the negative numbering is consistent, i.e. NUM(v) < NUM(w) in this case
        !            26: as in other cases where w is not an exit from the subtree of v.
        !            27: */
        !            28: 
        !            29: struct pair {
        !            30:        int smallest;
        !            31:        int second;
        !            32:        };
        !            33: 
        !            34: 
        !            35: getreach()             /* obtain REACH(v) for each node v */
        !            36:        {
        !            37:        VERT v;
        !            38:        struct pair *pr;
        !            39:        for (v = 0; v < nodenum; ++v)
        !            40:                REACH(v) = UNDEFINED;
        !            41:        number(START);
        !            42:        for (v = START; DEFINED(v); v = RSIB(v))
        !            43:                {
        !            44:                pr = exits(v);  /* need to free the space for pr */
        !            45:                chfree(pr,sizeof(*pr));
        !            46:                }
        !            47:        }
        !            48: 
        !            49: 
        !            50: exits(v)       /* set REACH(v) = w if w is only node outside subtree of v which is reached from within
        !            51:                        subtree of v, leave REACH(v) UNDEFINED otherwise */
        !            52: VERT v;
        !            53:        {
        !            54:        struct pair *vpair, *chpair;
        !            55:        VERT w,t;
        !            56:        int i;
        !            57:        vpair = challoc(sizeof(*vpair));
        !            58:        vpair ->smallest = vpair ->second = UNDEFINED;
        !            59:        for (i = 0; i < CHILDNUM(v); ++i)
        !            60:                {
        !            61:                w = LCHILD(v,i);
        !            62:                if (!DEFINED(w)) continue;
        !            63:                for (t = w; DEFINED(t); t = RSIB(t))
        !            64:                        {
        !            65:                        chpair = exits(t);
        !            66: 
        !            67:                        /* set vpair->smallest,second to two smallest of vpair->smallest,second,
        !            68:                                chpair->smallest,second */
        !            69:                        if (inspr(chpair->smallest,vpair))
        !            70:                                inspr(chpair->second,vpair);
        !            71:                        chfree(chpair, sizeof(*chpair));
        !            72:                        }
        !            73:                }
        !            74:        for (i = 0; i < ARCNUM(v); ++i)
        !            75:                {
        !            76:                w = ARC(v,i);
        !            77:                if (!DEFINED(w)) continue;
        !            78:                        inspr(w,vpair);
        !            79:                }
        !            80:        /* throw out nodes in subtree of  v */
        !            81:        if (NUM(vpair->second) >= NUM(v))
        !            82:                {
        !            83:                vpair->second = UNDEFINED;
        !            84:                if (NUM(vpair->smallest) >= NUM(v))
        !            85:                        vpair->smallest = UNDEFINED;
        !            86:                }
        !            87:        if (vpair->second == UNDEFINED)
        !            88:                 REACH(v) = vpair->smallest;    /* vpair->smallest possibly UNDEFINED */
        !            89:        else
        !            90:                REACH(v) = UNDEFINED;
        !            91:        return(vpair);
        !            92:        }
        !            93: 
        !            94: 
        !            95:        /* number nodes from -2 to -(accessnum+2) starting at bottom left corner of tree */
        !            96: number(v)
        !            97: VERT v;
        !            98:        {
        !            99:        int i;
        !           100:        VERT w;
        !           101:        static int count;
        !           102:        for (i = 0; i < CHILDNUM(v); ++i)
        !           103:                {
        !           104:                w = LCHILD(v,i);
        !           105:                if (DEFINED(w))
        !           106:                        number(w);
        !           107:                }
        !           108:        SETNUM(v,count-2);
        !           109:        --count;
        !           110:        if (DEFINED(RSIB(v)))
        !           111:                number(RSIB(v));
        !           112:        }
        !           113: 
        !           114: 
        !           115: NUM(v)
        !           116: VERT v;
        !           117:        {
        !           118:        if (!DEFINED(v)) return(UNDEFINED);
        !           119:        return(REACH(v));
        !           120:        }
        !           121: 
        !           122: SETNUM(v,count)
        !           123: VERT v; int count;
        !           124:        {
        !           125:        /* this reuses REACH to save space;
        !           126:        /* appears to be no conflict with setting true value of REACH later */
        !           127:        REACH(v) = count;
        !           128:        }
        !           129: 
        !           130: 
        !           131: LOGICAL inspr(w,pr)            /* insert w in order in pr, return TRUE if <= smaller of pr */
        !           132:                                        /* don't insert duplicates */
        !           133: VERT w;
        !           134: struct pair *pr;
        !           135:        {
        !           136:        if (w == pr-> smallest) return(TRUE);
        !           137:        if (NUM(w) < NUM(pr->smallest))
        !           138:                {
        !           139:                pr->second = pr->smallest;
        !           140:                pr->smallest = w;
        !           141:                return(TRUE);
        !           142:                }
        !           143:        if (w == pr->second) return(FALSE);
        !           144:        if (NUM(w) < NUM(pr->second))
        !           145:                pr->second = w;
        !           146:        return(FALSE);
        !           147:        }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.