4.3BSD - /usr/src/usr.bin/struct/3.reach.c

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

Defined functions

Defined variables

Defined struct's