Return to 3.reach.c CVS log

Up to [CSRG BSD Unix] / 41BSD / cmd / struct

Annotation of 41BSD/cmd/struct/3.reach.c, revision 1.1

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

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