# 2.11BSD#431 - /usr/src/usr.bin/struct/3.reach.c

##### Functions

    NUM               X
    SETNUM            X
    exits             X
    getreach          X
    inspr             X
    number            X

##### struct's

    pair              X

       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 = (struct pair *)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 = (struct pair *)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 = (struct pair *)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((int)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:     }

#### Defined functions

NUM defined in line 115; used 8 times

- in line 81-84(4), 137(2), 144(2)

SETNUM defined in line 122; used 1 times

- in line 108

exits defined in line 50; used 2 times

- in line 44, 65

getreach defined in line 35; used 1 times

- in /usr/src/usr.bin/struct/3.main.c line 14

inspr defined in line 131; used 3 times

- in line 69-70(2), 78

number defined in line 96; used 3 times

- in line 41, 106-111(2)

#### Defined variables

sccsid defined in line 2; never used

#### Defined struct's

pair defined in line 29; used 12 times

- in line 38(2), 44(2), 54-57(4), 65(2), 134(2)

Last modified: 1993-01-18 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 818 |