jaroslav@1981
|
1 |
/*
|
jaroslav@1981
|
2 |
* Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
|
jaroslav@1981
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
jaroslav@1981
|
4 |
*
|
jaroslav@1981
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
jaroslav@1981
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
jaroslav@1981
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
jaroslav@1981
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
jaroslav@1981
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
jaroslav@1981
|
10 |
*
|
jaroslav@1981
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
jaroslav@1981
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
jaroslav@1981
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
jaroslav@1981
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
jaroslav@1981
|
15 |
* accompanied this code).
|
jaroslav@1981
|
16 |
*
|
jaroslav@1981
|
17 |
* You should have received a copy of the GNU General Public License version
|
jaroslav@1981
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
jaroslav@1981
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
jaroslav@1981
|
20 |
*
|
jaroslav@1981
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
jaroslav@1981
|
22 |
* or visit www.oracle.com if you need additional information or have any
|
jaroslav@1981
|
23 |
* questions.
|
jaroslav@1981
|
24 |
*/
|
jaroslav@1981
|
25 |
|
jaroslav@1981
|
26 |
package java.lang;
|
jaroslav@1981
|
27 |
|
jaroslav@1981
|
28 |
import java.util.WeakHashMap;
|
jaroslav@1981
|
29 |
import java.util.concurrent.atomic.AtomicInteger;
|
jaroslav@1981
|
30 |
|
jaroslav@1981
|
31 |
/**
|
jaroslav@1981
|
32 |
* Lazily associate a computed value with (potentially) every type.
|
jaroslav@1981
|
33 |
* For example, if a dynamic language needs to construct a message dispatch
|
jaroslav@1981
|
34 |
* table for each class encountered at a message send call site,
|
jaroslav@1981
|
35 |
* it can use a {@code ClassValue} to cache information needed to
|
jaroslav@1981
|
36 |
* perform the message send quickly, for each class encountered.
|
jaroslav@1981
|
37 |
* @author John Rose, JSR 292 EG
|
jaroslav@1981
|
38 |
* @since 1.7
|
jaroslav@1981
|
39 |
*/
|
jaroslav@1981
|
40 |
public abstract class ClassValue<T> {
|
jaroslav@1981
|
41 |
/**
|
jaroslav@1981
|
42 |
* Sole constructor. (For invocation by subclass constructors, typically
|
jaroslav@1981
|
43 |
* implicit.)
|
jaroslav@1981
|
44 |
*/
|
jaroslav@1981
|
45 |
protected ClassValue() {
|
jaroslav@1981
|
46 |
}
|
jaroslav@1981
|
47 |
|
jaroslav@1981
|
48 |
/**
|
jaroslav@1981
|
49 |
* Computes the given class's derived value for this {@code ClassValue}.
|
jaroslav@1981
|
50 |
* <p>
|
jaroslav@1981
|
51 |
* This method will be invoked within the first thread that accesses
|
jaroslav@1981
|
52 |
* the value with the {@link #get get} method.
|
jaroslav@1981
|
53 |
* <p>
|
jaroslav@1981
|
54 |
* Normally, this method is invoked at most once per class,
|
jaroslav@1981
|
55 |
* but it may be invoked again if there has been a call to
|
jaroslav@1981
|
56 |
* {@link #remove remove}.
|
jaroslav@1981
|
57 |
* <p>
|
jaroslav@1981
|
58 |
* If this method throws an exception, the corresponding call to {@code get}
|
jaroslav@1981
|
59 |
* will terminate abnormally with that exception, and no class value will be recorded.
|
jaroslav@1981
|
60 |
*
|
jaroslav@1981
|
61 |
* @param type the type whose class value must be computed
|
jaroslav@1981
|
62 |
* @return the newly computed value associated with this {@code ClassValue}, for the given class or interface
|
jaroslav@1981
|
63 |
* @see #get
|
jaroslav@1981
|
64 |
* @see #remove
|
jaroslav@1981
|
65 |
*/
|
jaroslav@1981
|
66 |
protected abstract T computeValue(Class<?> type);
|
jaroslav@1981
|
67 |
|
jaroslav@1981
|
68 |
/**
|
jaroslav@1981
|
69 |
* Returns the value for the given class.
|
jaroslav@1981
|
70 |
* If no value has yet been computed, it is obtained by
|
jaroslav@1981
|
71 |
* an invocation of the {@link #computeValue computeValue} method.
|
jaroslav@1981
|
72 |
* <p>
|
jaroslav@1981
|
73 |
* The actual installation of the value on the class
|
jaroslav@1981
|
74 |
* is performed atomically.
|
jaroslav@1981
|
75 |
* At that point, if several racing threads have
|
jaroslav@1981
|
76 |
* computed values, one is chosen, and returned to
|
jaroslav@1981
|
77 |
* all the racing threads.
|
jaroslav@1981
|
78 |
* <p>
|
jaroslav@1981
|
79 |
* The {@code type} parameter is typically a class, but it may be any type,
|
jaroslav@1981
|
80 |
* such as an interface, a primitive type (like {@code int.class}), or {@code void.class}.
|
jaroslav@1981
|
81 |
* <p>
|
jaroslav@1981
|
82 |
* In the absence of {@code remove} calls, a class value has a simple
|
jaroslav@1981
|
83 |
* state diagram: uninitialized and initialized.
|
jaroslav@1981
|
84 |
* When {@code remove} calls are made,
|
jaroslav@1981
|
85 |
* the rules for value observation are more complex.
|
jaroslav@1981
|
86 |
* See the documentation for {@link #remove remove} for more information.
|
jaroslav@1981
|
87 |
*
|
jaroslav@1981
|
88 |
* @param type the type whose class value must be computed or retrieved
|
jaroslav@1981
|
89 |
* @return the current value associated with this {@code ClassValue}, for the given class or interface
|
jaroslav@1981
|
90 |
* @throws NullPointerException if the argument is null
|
jaroslav@1981
|
91 |
* @see #remove
|
jaroslav@1981
|
92 |
* @see #computeValue
|
jaroslav@1981
|
93 |
*/
|
jaroslav@1981
|
94 |
public T get(Class<?> type) {
|
jaroslav@1981
|
95 |
ClassValueMap map = getMap(type);
|
jaroslav@1981
|
96 |
if (map != null) {
|
jaroslav@1981
|
97 |
Object x = map.get(this);
|
jaroslav@1981
|
98 |
if (x != null) {
|
jaroslav@1981
|
99 |
return (T) map.unmaskNull(x);
|
jaroslav@1981
|
100 |
}
|
jaroslav@1981
|
101 |
}
|
jaroslav@1981
|
102 |
return setComputedValue(type);
|
jaroslav@1981
|
103 |
}
|
jaroslav@1981
|
104 |
|
jaroslav@1981
|
105 |
/**
|
jaroslav@1981
|
106 |
* Removes the associated value for the given class.
|
jaroslav@1981
|
107 |
* If this value is subsequently {@linkplain #get read} for the same class,
|
jaroslav@1981
|
108 |
* its value will be reinitialized by invoking its {@link #computeValue computeValue} method.
|
jaroslav@1981
|
109 |
* This may result in an additional invocation of the
|
jaroslav@1981
|
110 |
* {@code computeValue} method for the given class.
|
jaroslav@1981
|
111 |
* <p>
|
jaroslav@1981
|
112 |
* In order to explain the interaction between {@code get} and {@code remove} calls,
|
jaroslav@1981
|
113 |
* we must model the state transitions of a class value to take into account
|
jaroslav@1981
|
114 |
* the alternation between uninitialized and initialized states.
|
jaroslav@1981
|
115 |
* To do this, number these states sequentially from zero, and note that
|
jaroslav@1981
|
116 |
* uninitialized (or removed) states are numbered with even numbers,
|
jaroslav@1981
|
117 |
* while initialized (or re-initialized) states have odd numbers.
|
jaroslav@1981
|
118 |
* <p>
|
jaroslav@1981
|
119 |
* When a thread {@code T} removes a class value in state {@code 2N},
|
jaroslav@1981
|
120 |
* nothing happens, since the class value is already uninitialized.
|
jaroslav@1981
|
121 |
* Otherwise, the state is advanced atomically to {@code 2N+1}.
|
jaroslav@1981
|
122 |
* <p>
|
jaroslav@1981
|
123 |
* When a thread {@code T} queries a class value in state {@code 2N},
|
jaroslav@1981
|
124 |
* the thread first attempts to initialize the class value to state {@code 2N+1}
|
jaroslav@1981
|
125 |
* by invoking {@code computeValue} and installing the resulting value.
|
jaroslav@1981
|
126 |
* <p>
|
jaroslav@1981
|
127 |
* When {@code T} attempts to install the newly computed value,
|
jaroslav@1981
|
128 |
* if the state is still at {@code 2N}, the class value will be initialized
|
jaroslav@1981
|
129 |
* with the computed value, advancing it to state {@code 2N+1}.
|
jaroslav@1981
|
130 |
* <p>
|
jaroslav@1981
|
131 |
* Otherwise, whether the new state is even or odd,
|
jaroslav@1981
|
132 |
* {@code T} will discard the newly computed value
|
jaroslav@1981
|
133 |
* and retry the {@code get} operation.
|
jaroslav@1981
|
134 |
* <p>
|
jaroslav@1981
|
135 |
* Discarding and retrying is an important proviso,
|
jaroslav@1981
|
136 |
* since otherwise {@code T} could potentially install
|
jaroslav@1981
|
137 |
* a disastrously stale value. For example:
|
jaroslav@1981
|
138 |
* <ul>
|
jaroslav@1981
|
139 |
* <li>{@code T} calls {@code CV.get(C)} and sees state {@code 2N}
|
jaroslav@1981
|
140 |
* <li>{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it
|
jaroslav@1981
|
141 |
* <li>{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time
|
jaroslav@1981
|
142 |
* <li>...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N}
|
jaroslav@1981
|
143 |
* <li>{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)}
|
jaroslav@1981
|
144 |
* <li>{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work
|
jaroslav@1981
|
145 |
* <li> the previous actions of {@code T2} are repeated several times
|
jaroslav@1981
|
146 |
* <li> also, the relevant computed values change over time: {@code V1}, {@code V2}, ...
|
jaroslav@1981
|
147 |
* <li>...meanwhile, {@code T} wakes up and attempts to install {@code V0}; <em>this must fail</em>
|
jaroslav@1981
|
148 |
* </ul>
|
jaroslav@1981
|
149 |
* We can assume in the above scenario that {@code CV.computeValue} uses locks to properly
|
jaroslav@1981
|
150 |
* observe the time-dependent states as it computes {@code V1}, etc.
|
jaroslav@1981
|
151 |
* This does not remove the threat of a stale value, since there is a window of time
|
jaroslav@1981
|
152 |
* between the return of {@code computeValue} in {@code T} and the installation
|
jaroslav@1981
|
153 |
* of the the new value. No user synchronization is possible during this time.
|
jaroslav@1981
|
154 |
*
|
jaroslav@1981
|
155 |
* @param type the type whose class value must be removed
|
jaroslav@1981
|
156 |
* @throws NullPointerException if the argument is null
|
jaroslav@1981
|
157 |
*/
|
jaroslav@1981
|
158 |
public void remove(Class<?> type) {
|
jaroslav@1981
|
159 |
ClassValueMap map = getMap(type);
|
jaroslav@1981
|
160 |
if (map != null) {
|
jaroslav@1981
|
161 |
synchronized (map) {
|
jaroslav@1981
|
162 |
map.remove(this);
|
jaroslav@1981
|
163 |
}
|
jaroslav@1981
|
164 |
}
|
jaroslav@1981
|
165 |
}
|
jaroslav@1981
|
166 |
|
jaroslav@1981
|
167 |
/// Implementation...
|
jaroslav@1981
|
168 |
// FIXME: Use a data structure here similar that of ThreadLocal (7030453).
|
jaroslav@1981
|
169 |
|
jaroslav@1981
|
170 |
private static final AtomicInteger STORE_BARRIER = new AtomicInteger();
|
jaroslav@1981
|
171 |
|
jaroslav@1981
|
172 |
/** Slow path for {@link #get}. */
|
jaroslav@1981
|
173 |
private T setComputedValue(Class<?> type) {
|
jaroslav@1981
|
174 |
ClassValueMap map = getMap(type);
|
jaroslav@1981
|
175 |
if (map == null) {
|
jaroslav@1981
|
176 |
map = initializeMap(type);
|
jaroslav@1981
|
177 |
}
|
jaroslav@1981
|
178 |
T value = computeValue(type);
|
jaroslav@1981
|
179 |
STORE_BARRIER.lazySet(0);
|
jaroslav@1981
|
180 |
// All stores pending from computeValue are completed.
|
jaroslav@1981
|
181 |
synchronized (map) {
|
jaroslav@1981
|
182 |
// Warm up the table with a null entry.
|
jaroslav@1981
|
183 |
map.preInitializeEntry(this);
|
jaroslav@1981
|
184 |
}
|
jaroslav@1981
|
185 |
STORE_BARRIER.lazySet(0);
|
jaroslav@1981
|
186 |
// All stores pending from table expansion are completed.
|
jaroslav@1981
|
187 |
synchronized (map) {
|
jaroslav@1981
|
188 |
value = (T) map.initializeEntry(this, value);
|
jaroslav@1981
|
189 |
// One might fear a possible race condition here
|
jaroslav@1981
|
190 |
// if the code for map.put has flushed the write
|
jaroslav@1981
|
191 |
// to map.table[*] before the writes to the Map.Entry
|
jaroslav@1981
|
192 |
// are done. This is not possible, since we have
|
jaroslav@1981
|
193 |
// warmed up the table with an empty entry.
|
jaroslav@1981
|
194 |
}
|
jaroslav@1981
|
195 |
return value;
|
jaroslav@1981
|
196 |
}
|
jaroslav@1981
|
197 |
|
jaroslav@1981
|
198 |
// Replace this map by a per-class slot.
|
jaroslav@1981
|
199 |
private static final WeakHashMap<Class<?>, ClassValueMap> ROOT
|
jaroslav@1981
|
200 |
= new WeakHashMap<Class<?>, ClassValueMap>();
|
jaroslav@1981
|
201 |
|
jaroslav@1981
|
202 |
private static ClassValueMap getMap(Class<?> type) {
|
jaroslav@1981
|
203 |
type.getClass(); // test for null
|
jaroslav@1981
|
204 |
return ROOT.get(type);
|
jaroslav@1981
|
205 |
}
|
jaroslav@1981
|
206 |
|
jaroslav@1981
|
207 |
private static ClassValueMap initializeMap(Class<?> type) {
|
jaroslav@1981
|
208 |
synchronized (ClassValue.class) {
|
jaroslav@1981
|
209 |
ClassValueMap map = ROOT.get(type);
|
jaroslav@1981
|
210 |
if (map == null)
|
jaroslav@1981
|
211 |
ROOT.put(type, map = new ClassValueMap());
|
jaroslav@1981
|
212 |
return map;
|
jaroslav@1981
|
213 |
}
|
jaroslav@1981
|
214 |
}
|
jaroslav@1981
|
215 |
|
jaroslav@1981
|
216 |
static class ClassValueMap extends WeakHashMap<ClassValue, Object> {
|
jaroslav@1981
|
217 |
/** Make sure this table contains an Entry for the given key, even if it is empty. */
|
jaroslav@1981
|
218 |
void preInitializeEntry(ClassValue key) {
|
jaroslav@1981
|
219 |
if (!this.containsKey(key))
|
jaroslav@1981
|
220 |
this.put(key, null);
|
jaroslav@1981
|
221 |
}
|
jaroslav@1981
|
222 |
/** Make sure this table contains a non-empty Entry for the given key. */
|
jaroslav@1981
|
223 |
Object initializeEntry(ClassValue key, Object value) {
|
jaroslav@1981
|
224 |
Object prior = this.get(key);
|
jaroslav@1981
|
225 |
if (prior != null) {
|
jaroslav@1981
|
226 |
return unmaskNull(prior);
|
jaroslav@1981
|
227 |
}
|
jaroslav@1981
|
228 |
this.put(key, maskNull(value));
|
jaroslav@1981
|
229 |
return value;
|
jaroslav@1981
|
230 |
}
|
jaroslav@1981
|
231 |
|
jaroslav@1981
|
232 |
Object maskNull(Object x) {
|
jaroslav@1981
|
233 |
return x == null ? this : x;
|
jaroslav@1981
|
234 |
}
|
jaroslav@1981
|
235 |
Object unmaskNull(Object x) {
|
jaroslav@1981
|
236 |
return x == this ? null : x;
|
jaroslav@1981
|
237 |
}
|
jaroslav@1981
|
238 |
}
|
jaroslav@1981
|
239 |
}
|