2.9BSD - /usr/src/cmd/struct/3.reach.c

   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:     }

Defined functions

Defined struct's