tools/pldt/org.eclipse.ptp.pldt.openmp.analysis/src/org/eclipse/ptp/pldt/openmp/analysis/ompcfg/OMPDFS.java

/**********************************************************************
 * Copyright (c) 2006 IBM Corporation.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.ptp.pldt.openmp.analysis.ompcfg;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;

/**
 * Does a depth first search through an OMPCFG,
 * given the initial node
 * @author pazel
 *
 */
public abstract class OMPDFS
{
    protected OMPCFGNode    startNode_    = null;
    protected HashSet       visited_      = new HashSet();
    
    protected Stack         currentNodes_ = new Stack();
    
    public static final int CONTINUE   = 0;
    public static final int SKIP       = 1;  // SKIP following current node further
    public static final int ABORT      = 2;  // abord DFS
    
    /**
     * OMPDFS - constructor
     * @param startNode - OMPCFGNode
     */
    public OMPDFS(OMPCFGNode startNode)
    {
        startNode_ = startNode;
    }
    
    /**
     * startWalking - method to start the dfs walking
     *
     */
    public void startWalking()
    {
        walkDFS(startNode_);
    }
    
    /**
     * walkDFS - recursively walk the tree visiting each node 1 time
     *           NOTE: only connected component to start node
     * @param node - OMPCFGNode
     * @return int    (code to continue, skip, or abort)
     */
    protected int walkDFS(OMPCFGNode node)
    {
        if (visited_.contains(node))  return CONTINUE;
        
        currentNodes_.push(node);  // sets the new context on the stack
        int code = visit(node);
        visited_.add(node);
        
        if (code==SKIP)  { currentNodes_.pop();  return CONTINUE; }  // we only skip this level, continue others
        if (code==ABORT) { currentNodes_.pop();  return ABORT;    }
        
        OMPCFGNode [] outNodes = node.getOutNodes();
        for(int i=0; i<outNodes.length; i++) {
           int iCode = walkDFS(outNodes[i]);
           if (iCode==ABORT) { currentNodes_.pop();  return ABORT;  } // code cannot be skip
        }
        currentNodes_.pop();
        
        return CONTINUE;
    }
    
    /**
     * getNodeStack - get the current node stack context
     * @return OMPCFGNode []
     */
    public OMPCFGNode [] getNodeStack()
    {
        OMPCFGNode [] l = new OMPCFGNode[currentNodes_.size()];
        int count=0;
        for(Iterator i=currentNodes_.iterator(); i.hasNext();) 
            l[count++] = (OMPCFGNode)i.next();
        return l;
    }
    
    /**
     * getNodeStackSize - get the size of the stack
     * @return int
     */
    public int getNodeStackSize()
    {
        return currentNodes_.size();
    }
    
    /**
     * isVisited - determine if node has been visited on walk
     * @param node - OMPCFGNode
     * @return boolean
     */
    public boolean isVisited(OMPCFGNode node)
    {
        return visited_.contains(node);
    }
    
    /**
     * visit - visit method - what the user usually overrides
     * @param node - OMPCFGNode
     */
    public abstract int visit(OMPCFGNode node);


}