1 cananian 1.1 // Reachable.java, created Tue Nov 11 14:18:19 2003 by cananian 2 cananian 1.1 // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu> 3 cananian 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details. 4 cananian 1.1 package harpoon.Analysis; 5 cananian 1.1 6 cananian 1.1 import harpoon.ClassFile.HCode; 7 cananian 1.1 import harpoon.ClassFile.HCodeElement; 8 cananian 1.1 import harpoon.IR.Properties.CFGrapher; 9 cananian 1.3 import net.cscott.jutil.WorkSet; 10 cananian 1.1 11 cananian 1.1 import java.util.Arrays; 12 cananian 1.1 import java.util.Collections; 13 cananian 1.1 import java.util.HashSet; 14 cananian 1.1 import java.util.Iterator; 15 cananian 1.1 import java.util.Set; 16 cananian 1.1 /** 17 cananian 1.1 * <code>Reachable</code> 18 cananian 1.1 * 19 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu> 20 cananian 1.4 * @version $Id: Reachable.java,v 1.4 2004/02/08 03:19:12 cananian Exp $ 21 cananian 1.1 */ 22 cananian 1.1 public final class Reachable<HCE extends HCodeElement> { 23 cananian 1.1 public final Set<HCE> reachable; 24 cananian 1.1 25 cananian 1.1 public Reachable(HCode<HCE> hcode) { 26 cananian 1.3 this(hcode, (CFGrapher<HCE>) CFGrapher.DEFAULT); 27 cananian 1.1 } 28 cananian 1.1 public Reachable(HCode<HCE> hcode, CFGrapher<HCE> grapher) { 29 cananian 1.1 Set<HCE> reachable = new HashSet<HCE>(); 30 cananian 1.1 // initialize worklist. 31 cananian 1.1 WorkSet<HCE> work = new WorkSet<HCE>(); 32 cananian 1.1 work.addAll(Arrays.asList(grapher.getFirstElements(hcode))); 33 cananian 1.1 // iterate until worklist is empty. 34 cananian 1.1 while (!work.isEmpty()) { 35 cananian 1.1 HCE hce = work.removeFirst(); 36 cananian 1.1 reachable.add(hce); 37 cananian 1.1 38 cananian 1.4 for(HCE succ : grapher.succElemC(hce)) { 39 cananian 1.1 if (!reachable.contains(succ)) 40 cananian 1.1 work.add(succ); 41 cananian 1.1 } 42 cananian 1.1 } 43 cananian 1.1 // done! 44 cananian 1.1 this.reachable = Collections.unmodifiableSet(reachable); 45 cananian 1.1 } 46 cananian 1.1 public boolean isReachable(HCE hce) { 47 cananian 1.1 return reachable.contains(hce); 48 cananian 1.1 } 49 cananian 1.1 }