1 cananian 1.1.2.1 // PreOrderClazNumbering.java, created Sun Mar 10 05:24:15 2002 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Backend.RuntimeTiny;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
8 cananian 1.1.2.1 import harpoon.Util.HClassUtil;
9 cananian 1.1.2.1
10 cananian 1.1.2.1 import java.util.Collections;
11 cananian 1.1.2.1 import java.util.Comparator;
12 cananian 1.1.2.1 import java.util.HashMap;
13 cananian 1.1.2.1 import java.util.Iterator;
14 cananian 1.1.2.1 import java.util.Map;
15 cananian 1.1.2.1 import java.util.Set;
16 cananian 1.1.2.1 /**
17 cananian 1.1.2.1 * <code>PreOrderClazNumbering</code> will number single-inheritance
18 cananian 1.1.2.1 * instantiated classes (i.e. not interfaces or arrays of interfaces)
19 cananian 1.1.2.1 * such that all classes numbered in an interval [a,b] will be
20 cananian 1.1.2.1 * instances of the first common superclass of A and B, where
21 cananian 1.1.2.1 * <code>clazNumber(A)==a</code> and <code>clazNumber(B)==b</code>.
22 cananian 1.1.2.1 * This is useful for implementing quick 'instanceOf' tests;
23 cananian 1.1.2.1 * to determine if an object is an instanceof class A, you can
24 cananian 1.1.2.1 * simply see if the object falls within the interval
25 cananian 1.1.2.1 * <code>[classNumber(A),maxChildNumber(A)]</code>.
26 cananian 1.1.2.1 *
27 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
28 cananian 1.2 * @version $Id: PreOrderClazNumbering.java,v 1.2 2002/04/10 03:03:43 cananian Exp $
29 cananian 1.1.2.1 */
30 cananian 1.1.2.1 public class PreOrderClazNumbering extends ClazNumbering {
31 cananian 1.1.2.1 private final Map<HClass,Integer> minmap = new HashMap<HClass,Integer>();
32 cananian 1.1.2.1 private final Map<HClass,Integer> maxmap = new HashMap<HClass,Integer>();
33 cananian 1.1.2.1 private final int max;
34 cananian 1.1.2.1
35 cananian 1.1.2.1 /** Creates a <code>PreOrderClazNumbering</code>. */
36 cananian 1.1.2.1 public PreOrderClazNumbering(ClassHierarchy ch) {
37 cananian 1.1.2.1 Set<HClass> all = ch.instantiatedClasses();
38 cananian 1.1.2.1 HClass root = Collections.min(all, new Comparator<HClass>() {
39 cananian 1.1.2.1 public int compare(HClass a, HClass b) {
40 cananian 1.1.2.1 // major sort key is inheritance.
41 cananian 1.1.2.1 if (a.isInstanceOf(b) && !b.isInstanceOf(a)) return 1;
42 cananian 1.1.2.1 if (b.isInstanceOf(a) && !a.isInstanceOf(b)) return -1;
43 cananian 1.1.2.1 // break ties by sorting lexicographically.
44 cananian 1.1.2.1 return a.getDescriptor().compareTo(b.getDescriptor());
45 cananian 1.1.2.1 }
46 cananian 1.1.2.1 });
47 cananian 1.1.2.1 assert root.getName().equals("java.lang.Object");
48 cananian 1.1.2.1 this.max = number(-1, root, ch);
49 cananian 1.1.2.1
50 cananian 1.1.2.1 }
51 cananian 1.1.2.1 private int number(int n, HClass hc, ClassHierarchy ch) {
52 cananian 1.1.2.1 assert !(minmap.containsKey(hc) || maxmap.containsKey(hc)) :
53 cananian 1.1.2.1 "at entrance to number(), we shouldn't have a mapping for "+hc;
54 cananian 1.1.2.1 if (HClassUtil.baseClass(hc).isInterface())
55 cananian 1.1.2.1 return n; // only single-inheritance tree.
56 cananian 1.1.2.1 if (ch.instantiatedClasses().contains(hc)) n++;
57 cananian 1.1.2.1 minmap.put(hc, new Integer(n));
58 cananian 1.1.2.1 for (Iterator<HClass> it=ch.children(hc).iterator(); it.hasNext(); )
59 cananian 1.1.2.1 n=number(n, it.next(), ch);
60 cananian 1.1.2.1 maxmap.put(hc, new Integer(n));
61 cananian 1.1.2.1 assert minmap.containsKey(hc) && maxmap.containsKey(hc) :
62 cananian 1.1.2.1 "at exit to number(), we *should* have a mapping for "+hc;
63 cananian 1.1.2.1 return n;
64 cananian 1.1.2.1 }
65 cananian 1.1.2.1
66 cananian 1.1.2.1 /** Returns the number associated with the given <code>HClass</code>. */
67 cananian 1.1.2.1 public int clazNumber(HClass hc) {
68 cananian 1.1.2.1 assert minmap.containsKey(hc) :
69 cananian 1.1.2.1 "clazNumber() not valid for the non-single-inheritance class "
70 cananian 1.1.2.1 +hc;
71 cananian 1.1.2.1 return minmap.get(hc).intValue();
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1 /** Returns the maximum number associated with an instantiatable
74 cananian 1.1.2.1 * child of the given <code>HClass</code>. */
75 cananian 1.1.2.1 public int maxChildNumber(HClass hc) {
76 cananian 1.1.2.1 assert maxmap.containsKey(hc) :
77 cananian 1.1.2.1 "maxChildNumber() not valid for the non-single-inheritance class "
78 cananian 1.1.2.1 +hc;
79 cananian 1.1.2.1 return maxmap.get(hc).intValue();
80 cananian 1.1.2.1 }
81 cananian 1.1.2.1 /** Returns the smallest number which this <code>ClazNumbering</code>
82 cananian 1.1.2.1 * will associate with any <code>HClass</code>. */
83 cananian 1.1.2.1 public int minNumber() { return 0; }
84 cananian 1.1.2.1 /** Returns the largest number which this <code>ClazNumbering</code>
85 cananian 1.1.2.1 * will associate with any <code>HClass</code>. */
86 cananian 1.1.2.1 public int maxNumber() { return max; }
87 cananian 1.1.2.1
88 cananian 1.2 }