BSD 4_4 release

[unix-history] / usr / src / usr.bin / struct / struct / 2.dfs.c

/*-
* This module is believed to contain source code proprietary to AT&T.
* Use and redistribution is subject to the Berkeley Software License
* Agreement and your Software Agreement with AT&T (Western Electric).
*/

#ifndef lint
static char sccsid[] = "@(#)2.dfs.c     8.1 (Berkeley) 6/6/93";
#endif /* not lint */

#include <stdio.h>
#
/* depth-first search used to identify back edges, unreachable nodes;
       each node v entered by back edge replaced by
       LOOPVX ->ITERVX -> v,
       so that back edges entering v now enter the ITERVX,
       and other edges entering v now enter the LOOPVX.
       Nodes are numbered according to depth-first search:
               before numbering- ntobef[v] = i => node numbered v is i'th
                       node in order of first visit during the search;
               after numbering- ntoaft[v] = i => node numbered v is i'th
                       node visited in order of last visit during the search.
                       Also, in this case after[i] = v.
*/

#include "def.h"
#include "2.def.h"

#define MAXINS 3        /* spacing needed between numbers generated during depth first search */

int *status;
int befcount, aftcount;
/* following defines used to mark back edges and nodes entered by back edges */
#define UNPROCESSED     0
#define STACKED 1
#define FINISHED        2
#define MARK(v) {REACH(v) = 1; }        /* mark node v */
#define UNMARK(v)       {REACH(v) = 0; }
#define MARKED(v)       (REACH(v))
#define MKEDGE(e)       {if (e >= -1) e = -(e+3); }     /* mark edge e */
#define UNMKEDGE(e)     {if (e < -1) e = -(e+3); }
#define BACKEDGE(e)     (e < -1)


dfs(v)          /* depth first search */
VERT v;
       {
       int i; VERT w;
       accessnum = 0;
       status = challoc(sizeof(*status) * nodenum);
       for (w = 0; w < nodenum; ++w)
               {
               status[w] = UNPROCESSED;
               UNMARK(w);
               }
       search(v);
       chreach();
       chfree(status, sizeof(*status) * nodenum);
       addloop();
       after = challoc(sizeof(*after) * accessnum);
       for (i = 0; i < accessnum; ++i)
               after[i] = UNDEFINED;
       ntoaft = challoc(sizeof(*ntoaft) * nodenum);
       ntobef = challoc(sizeof(*ntobef) * nodenum);
       for (w = 0; w < nodenum; ++w)
               ntobef[w] = ntoaft[w] = UNDEFINED;
       befcount = 0;
       aftcount = 0;
       repsearch(v);
       }


search(v)
       /* using depth first search, mark back edges using MKEDGE, and nodes entered by back
       edges using MARK */
VERT v;
       {
       VERT adj; int i;
       status[v] = STACKED;
       for(i = 0; i < ARCNUM(v); ++i)
               {
               adj = ARC(v,i);
               if (!DEFINED(adj)) continue;
               else if (status[adj] == UNPROCESSED)
                       search(adj);
               else if (status[adj] == STACKED)
                       {
                       MARK(adj);              /* mark adj as entered by back edge */
                       MKEDGE(ARC(v,i));       /* mark edge ARC(v,i) as being back edge */
                       }
               }
       status[v] = FINISHED;
       ++accessnum;
       }

chreach()               /* look for unreachable nodes */
       {
       VERT v;
       LOGICAL unreach;
       unreach = FALSE;
       for (v = 0; v < nodenum; ++v)
               if (status[v] == UNPROCESSED && NTYPE(v) != FMTVX
                       && NTYPE(v) != STOPVX && NTYPE(v) != RETVX)
                       {
                       unreach = TRUE;
                       if (debug)
                               fprintf(stderr,"node %d unreachable\n",v);
                       }
       if (unreach)
               error(": unreachable statements - ","will be ignored","");
       }


addloop()       /* add LOOPVX, ITERVX at nodes entered by back edges, and adjust edges */
       {
       VERT v, adj;
       int j, oldnum;
       for (v = 0, oldnum = nodenum; v < oldnum; ++v)  /* insloop increases nodenum */
               if (MARKED(v))
                       {
                       UNMARK(v);      /* remove mark indicating v entered by back edge */
                       if (NTYPE(v) != ITERVX)                 /* DO loops already have ITERVX */
                                insloop(v);  /* add LOOPVX, ITERVX since v entered by back edge*/
                       }
       /* arcs which used to enter v now enter LOOPVX; must make back edges enter ITERVX */
       for (v = 0; v < nodenum; ++v)
               for (j = 0; j < ARCNUM(v); ++j)
                       {
                       if (BACKEDGE(ARC(v,j)))
                               {
                               UNMKEDGE(ARC(v,j));             /* return edge to normal value */
                               adj = ARC(v,j);
                               if (NTYPE(adj) == ITERVX) continue;
                               ASSERT(NTYPE(adj) == LOOPVX,addloop);
                               ARC(v,j) = ARC(adj,0);  /* change arc to point to ITERVX */
                               ASSERT(NTYPE(ARC(v,j)) == ITERVX,addloop);
                               }
                       }
       }

insloop(v)              /* insert LOOPVX, ITERVX at node number v */
VERT v;
       {
       VERT loo, iter;
       loo = create(LOOPVX, 1);
       iter = create(ITERVX,1);
       accessnum += 2;
       /* want LOOPVX to take on node number v, so that arcs other than back arcs
               entering v will enter the LOOPVX automatically */
       exchange(&graph[v], &graph[loo]);
       exchange(&v, &loo);
       ARC(loo,0) = iter;
       ARC(iter,0) = v;
       FATH(iter) = UNDEFINED; /* will be defined later along with FATH for DOVX */
       }

exchange(p1,p2)         /* exchange values of p1,p2 */
int *p1,*p2;
       {
       int temp;
       temp = *p1;
       *p1 = *p2;
       *p2 = temp;
       }


repsearch(v)            /* repeat df search in order to fill in after, ntoaft, ntobef tables */
VERT v;
       {
       VERT adj; int i,temp;
       ntobef[v] = befcount;
       ++befcount;
       for(i = 0; i < ARCNUM(v); ++i)
               {
               adj = ARC(v,i);
               if (DEFINED(adj) && ntobef[adj] == UNDEFINED)
                       repsearch(adj);
               }
       ++aftcount;
       temp = accessnum - aftcount;
       after[temp] = v;
       ntoaft[v] = temp;
       }