home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / struct / 2.dfs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  4.4 KB  |  174 lines
  1. #include <stdio.h>
  2. #
  3. /* depth-first search used to identify back edges, unreachable nodes;
  4.     each node v entered by back edge replaced by
  5.     LOOPVX ->ITERVX -> v,
  6.     so that back edges entering v now enter the ITERVX,
  7.     and other edges entering v now enter the LOOPVX.
  8.     Nodes are numbered according to depth-first search:
  9.         before numbering- ntobef[v] = i => node numbered v is i'th
  10.             node in order of first visit during the search;
  11.         after numbering- ntoaft[v] = i => node numbered v is i'th
  12.             node visited in order of last visit during the search.
  13.             Also, in this case after[i] = v.
  14. */
  15.  
  16. #include "def.h"
  17. #include "2.def.h"
  18.  
  19. #define MAXINS 3    /* spacing needed between numbers generated during depth first search */
  20.  
  21. int *status;
  22. int befcount, aftcount;
  23. /* following defines used to mark back edges and nodes entered by back edges */
  24. #define UNPROCESSED    0
  25. #define STACKED    1
  26. #define FINISHED    2
  27. #define MARK(v)    {REACH(v) = 1; }    /* mark node v */
  28. #define UNMARK(v)    {REACH(v) = 0; }
  29. #define MARKED(v)    (REACH(v))
  30. #define MKEDGE(e)    {if (e >= -1) e = -(e+3); }    /* mark edge e */
  31. #define UNMKEDGE(e)    {if (e < -1) e = -(e+3); }
  32. #define BACKEDGE(e)    (e < -1)
  33.  
  34.  
  35. dfs(v)        /* depth first search */
  36. VERT v;
  37.     {
  38.     int i; VERT w;
  39.     accessnum = 0;
  40.     status = challoc(sizeof(*status) * nodenum);
  41.     for (w = 0; w < nodenum; ++w)
  42.         {
  43.         status[w] = UNPROCESSED;
  44.         UNMARK(w);
  45.         }
  46.     search(v);
  47.     chreach();
  48.     chfree(status, sizeof(*status) * nodenum);
  49.     addloop();
  50.     after = challoc(sizeof(*after) * accessnum);
  51.     for (i = 0; i < accessnum; ++i)
  52.         after[i] = UNDEFINED;
  53.     ntoaft = challoc(sizeof(*ntoaft) * nodenum);
  54.     ntobef = challoc(sizeof(*ntobef) * nodenum);
  55.     for (w = 0; w < nodenum; ++w)
  56.         ntobef[w] = ntoaft[w] = UNDEFINED;
  57.     befcount = 0;
  58.     aftcount = 0;
  59.     repsearch(v);
  60.     }
  61.  
  62.  
  63. search(v)
  64.     /* using depth first search, mark back edges using MKEDGE, and nodes entered by back
  65.     edges using MARK */
  66. VERT v;
  67.     {
  68.     VERT adj; int i;
  69.     status[v] = STACKED;
  70.     for(i = 0; i < ARCNUM(v); ++i)
  71.         {
  72.         adj = ARC(v,i);
  73.         if (!DEFINED(adj)) continue;
  74.         else if (status[adj] == UNPROCESSED)
  75.             search(adj);
  76.         else if (status[adj] == STACKED)
  77.             {
  78.             MARK(adj);        /* mark adj as entered by back edge */
  79.             MKEDGE(ARC(v,i));    /* mark edge ARC(v,i) as being back edge */
  80.             }
  81.         }
  82.     status[v] = FINISHED;
  83.     ++accessnum;
  84.     }
  85.  
  86. chreach()        /* look for unreachable nodes */
  87.     {
  88.     VERT v;
  89.     LOGICAL unreach;
  90.     unreach = FALSE;
  91.     for (v = 0; v < nodenum; ++v)
  92.         if (status[v] == UNPROCESSED && NTYPE(v) != FMTVX
  93.             && NTYPE(v) != STOPVX && NTYPE(v) != RETVX)
  94.             {
  95.             unreach = TRUE;
  96.             if (debug)
  97.                 fprintf(stderr,"node %d unreachable\n",v);
  98.             }
  99.     if (unreach)
  100.         error(": unreachable statements - ","will be ignored","");
  101.     }
  102.  
  103.  
  104. addloop()    /* add LOOPVX, ITERVX at nodes entered by back edges, and adjust edges */
  105.     {
  106.     VERT v, adj;
  107.     int j, oldnum;
  108.     for (v = 0, oldnum = nodenum; v < oldnum; ++v)    /* insloop increases nodenum */
  109.         if (MARKED(v))
  110.             {
  111.             UNMARK(v);    /* remove mark indicating v entered by back edge */
  112.             if (NTYPE(v) != ITERVX)            /* DO loops already have ITERVX */
  113.                  insloop(v);  /* add LOOPVX, ITERVX since v entered by back edge*/
  114.             }
  115.     /* arcs which used to enter v now enter LOOPVX; must make back edges enter ITERVX */
  116.     for (v = 0; v < nodenum; ++v)
  117.         for (j = 0; j < ARCNUM(v); ++j)
  118.             {
  119.             if (BACKEDGE(ARC(v,j)))
  120.                 {
  121.                 UNMKEDGE(ARC(v,j));        /* return edge to normal value */
  122.                 adj = ARC(v,j);
  123.                 if (NTYPE(adj) == ITERVX) continue;
  124.                 ASSERT(NTYPE(adj) == LOOPVX,addloop);
  125.                 ARC(v,j) = ARC(adj,0);    /* change arc to point to ITERVX */
  126.                 ASSERT(NTYPE(ARC(v,j)) == ITERVX,addloop);
  127.                 }
  128.             }
  129.     }
  130.  
  131. insloop(v)        /* insert LOOPVX, ITERVX at node number v */
  132. VERT v;
  133.     {
  134.     VERT loo, iter;
  135.     loo = create(LOOPVX, 1);
  136.     iter = create(ITERVX,1);
  137.     accessnum += 2;
  138.     /* want LOOPVX to take on node number v, so that arcs other than back arcs
  139.         entering v will enter the LOOPVX automatically */
  140.     exchange(&graph[v], &graph[loo]);
  141.     exchange(&v, &loo);
  142.     ARC(loo,0) = iter;
  143.     ARC(iter,0) = v;
  144.     FATH(iter) = UNDEFINED;    /* will be defined later along with FATH for DOVX */
  145.     }
  146.  
  147. exchange(p1,p2)        /* exchange values of p1,p2 */
  148. int *p1,*p2;
  149.     {
  150.     int temp;
  151.     temp = *p1;
  152.     *p1 = *p2;
  153.     *p2 = temp;
  154.     }
  155.  
  156.  
  157. repsearch(v)        /* repeat df search in order to fill in after, ntoaft, ntobef tables */
  158. VERT v;
  159.     {
  160.     VERT adj; int i,temp;
  161.     ntobef[v] = befcount;
  162.     ++befcount;
  163.     for(i = 0; i < ARCNUM(v); ++i)
  164.         {
  165.         adj = ARC(v,i);
  166.         if (DEFINED(adj) && ntobef[adj] == UNDEFINED)
  167.             repsearch(adj);
  168.         }
  169.     ++aftcount;
  170.     temp = accessnum - aftcount;
  171.     after[temp] = v;
  172.     ntoaft[v] = temp;
  173.     }
  174.