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