1 package Analysis.OwnershipAnalysis;
9 public class TokenTupleSet extends Canonical {
11 private HashSet<TokenTuple> tokenTuples;
14 public TokenTupleSet() {
15 tokenTuples = new HashSet<TokenTuple>();
18 public TokenTupleSet(TokenTuple tt) {
24 public TokenTupleSet(TokenTupleSet tts) {
26 // okay to clone, TokenTuple and TokenTupleSet should be canonical
27 tokenTuples = (HashSet<TokenTuple>)tts.tokenTuples.clone();
31 public TokenTupleSet makeCanonical() {
32 return (TokenTupleSet) Canonical.makeCanonical(this);
35 public Iterator iterator() {
36 return tokenTuples.iterator();
39 public boolean isEmpty() {
40 return tokenTuples.isEmpty();
43 public boolean isSubset(TokenTupleSet ttsIn) {
45 return ttsIn.tokenTuples.containsAll(this.tokenTuples);
48 public boolean containsTuple(TokenTuple tt) {
50 return tokenTuples.contains(tt);
54 public TokenTupleSet union(TokenTupleSet ttsIn) {
56 TokenTupleSet ttsOut = new TokenTupleSet(this);
57 ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
58 return ttsOut.makeCanonical();
61 public TokenTupleSet add(TokenTuple tt) {
63 TokenTupleSet ttsOut = new TokenTupleSet(tt);
64 return ttsOut.union(this);
68 // this should only be done with a multiple-object heap region's token!
69 public TokenTupleSet increaseArity(Integer token) {
71 TokenTupleSet ttsOut = new TokenTupleSet(this);
73 = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
74 if( ttsOut.tokenTuples.contains(tt) ) {
75 ttsOut.tokenTuples.remove(tt);
76 ttsOut.tokenTuples.add(
77 new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
81 return ttsOut.makeCanonical();
85 public boolean equals(Object o) {
90 if( !(o instanceof TokenTupleSet) ) {
94 TokenTupleSet tts = (TokenTupleSet) o;
95 return tokenTuples.equals(tts.tokenTuples);
98 public int hashCode() {
99 return tokenTuples.hashCode();
103 // this should be a hash table so we can do this by key
104 public boolean containsToken(Integer token) {
105 assert token != null;
107 Iterator itr = tokenTuples.iterator();
108 while( itr.hasNext() ) {
109 TokenTuple tt = (TokenTuple) itr.next();
110 if( token.equals(tt.getToken() ) ) {
118 public TokenTupleSet ageTokens(AllocationSite as) {
121 TokenTupleSet ttsOut = new TokenTupleSet();
123 TokenTuple ttSummary = null;
124 boolean foundOldest = false;
126 Iterator itrT = this.iterator();
127 while( itrT.hasNext() ) {
128 TokenTuple tt = (TokenTuple) itrT.next();
130 Integer token = tt.getToken();
131 int age = as.getAge(token);
133 // summary tokens and tokens not associated with
134 // the site should be left alone
135 if( age == AllocationSite.AGE_notInThisSite ) {
136 ttsOut.tokenTuples.add(tt);
139 if( age == AllocationSite.AGE_summary ) {
140 // remember the summary tuple, but don't add it
141 // we may combine it with the oldest tuple
144 } else if( age == AllocationSite.AGE_oldest ) {
145 // found an oldest token, again just remember
150 // otherwise, we change this token to the
152 Integer tokenToChangeTo = as.getIthOldest(age + 1);
153 TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo);
154 ttsOut.tokenTuples.add(ttAged);
160 // there are four cases to consider here
161 // 1. we found a summary tuple and no oldest tuple
162 // Here we just pass the summary unchanged
163 // 2. we found an oldest tuple, no summary
164 // Make a new, arity-one summary tuple
165 // 3. we found both a summary and an oldest
166 // Merge them by increasing arity of summary
167 // 4. (not handled) we found neither, do nothing
168 if ( ttSummary != null && !foundOldest ) {
169 ttsOut.tokenTuples.add(ttSummary);
171 } else if( ttSummary == null && foundOldest ) {
172 ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
174 TokenTuple.ARITY_ONE).makeCanonical() );
176 } else if( ttSummary != null && foundOldest ) {
177 ttsOut.tokenTuples.add(ttSummary.increaseArity() );
180 return ttsOut.makeCanonical();
184 public ReachabilitySet rewrite( TokenTuple tokenToRewrite,
185 ReachabilitySet replacements ) {
187 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
189 if( !tokenTuples.contains( tokenToRewrite ) ) {
193 TokenTupleSet ttsMinusToken = new TokenTupleSet( this );
194 ttsMinusToken.tokenTuples.remove( tokenToRewrite );
196 Iterator<TokenTupleSet> replaceItr = replacements.iterator();
197 while( replaceItr.hasNext() ) {
198 TokenTupleSet replacement = replaceItr.next();
199 TokenTupleSet replaced = new TokenTupleSet();
200 replaced.tokenTuples.addAll( ttsMinusToken.tokenTuples );
201 replaced.tokenTuples.addAll( replacement.tokenTuples );
202 replaced = replaced.makeCanonical();
203 rsOut.add( replaced );
211 public String toString() {
212 return tokenTuples.toString();