29 import java.util.concurrent.atomic.AtomicInteger; |
29 import java.util.concurrent.atomic.AtomicInteger; |
30 import java.util.concurrent.atomic.AtomicReference; |
30 import java.util.concurrent.atomic.AtomicReference; |
31 import java.lang.reflect.UndeclaredThrowableException; |
31 import java.lang.reflect.UndeclaredThrowableException; |
32 |
32 |
33 /** |
33 /** |
34 * Lazily associate a computed value with (potentially) every class. |
34 * Lazily associate a computed value with (potentially) every type. |
|
35 * For example, if a dynamic language needs to construct a message dispatch |
|
36 * table for each class encountered at a message send call site, |
|
37 * it can use a {@code ClassValue} to cache information needed to |
|
38 * perform the message send quickly, for each class encountered. |
35 * @author John Rose, JSR 292 EG |
39 * @author John Rose, JSR 292 EG |
36 */ |
40 */ |
37 public class ClassValue<T> { |
41 public abstract class ClassValue<T> { |
38 /** |
42 /** |
39 * Compute the given class's derived value for this {@code ClassValue}. |
43 * Compute the given class's derived value for this {@code ClassValue}. |
40 * <p> |
44 * <p> |
41 * This method will be invoked within the first thread that accesses |
45 * This method will be invoked within the first thread that accesses |
42 * the value with the {@link #get get} method. |
46 * the value with the {@link #get get} method. |
43 * <p> |
47 * <p> |
44 * Normally, this method is invoked at most once per class, |
48 * Normally, this method is invoked at most once per class, |
45 * but it may be invoked again if there has been a call to |
49 * but it may be invoked again if there has been a call to |
46 * {@link #remove remove}. |
50 * {@link #remove remove}. |
47 * <p> |
51 * <p> |
48 * If there is no override from a subclass, this method returns |
52 * If this method throws an exception, the corresponding call to {@code get} |
49 * the result of applying the {@code ClassValue}'s {@code computeValue} |
53 * will terminate abnormally with that exception, and no class value will be recorded. |
50 * method handle, which was supplied at construction time. |
|
51 * |
54 * |
|
55 * @param type the type whose class value must be computed |
52 * @return the newly computed value associated with this {@code ClassValue}, for the given class or interface |
56 * @return the newly computed value associated with this {@code ClassValue}, for the given class or interface |
53 * @throws UndeclaredThrowableException if the {@code computeValue} method handle invocation throws something other than a {@code RuntimeException} or {@code Error} |
57 * @see #get |
54 * @throws UnsupportedOperationException if the {@code computeValue} method handle is null (subclasses must override) |
58 * @see #remove |
55 */ |
59 */ |
56 protected T computeValue(Class<?> type) { |
60 protected abstract T computeValue(Class<?> type); |
57 if (computeValue == null) |
|
58 return null; |
|
59 try { |
|
60 return (T) (Object) computeValue.invokeGeneric(type); |
|
61 } catch (Throwable ex) { |
|
62 if (ex instanceof Error) throw (Error) ex; |
|
63 if (ex instanceof RuntimeException) throw (RuntimeException) ex; |
|
64 throw new UndeclaredThrowableException(ex); |
|
65 } |
|
66 } |
|
67 |
|
68 private final MethodHandle computeValue; |
|
69 |
|
70 /** |
|
71 * Creates a new class value. |
|
72 * Subclasses which use this constructor must override |
|
73 * the {@link #computeValue computeValue} method, |
|
74 * since the default {@code computeValue} method requires a method handle, |
|
75 * which this constructor does not provide. |
|
76 */ |
|
77 protected ClassValue() { |
|
78 this.computeValue = null; |
|
79 } |
|
80 |
|
81 /** |
|
82 * Creates a new class value, whose {@link #computeValue computeValue} method |
|
83 * will return the result of {@code computeValue.invokeGeneric(type)}. |
|
84 * @throws NullPointerException if the method handle parameter is null |
|
85 */ |
|
86 public ClassValue(MethodHandle computeValue) { |
|
87 computeValue.getClass(); // trigger NPE if null |
|
88 this.computeValue = computeValue; |
|
89 } |
|
90 |
61 |
91 /** |
62 /** |
92 * Returns the value for the given class. |
63 * Returns the value for the given class. |
93 * If no value has yet been computed, it is obtained by |
64 * If no value has yet been computed, it is obtained by |
94 * by an invocation of the {@link #computeValue computeValue} method. |
65 * an invocation of the {@link #computeValue computeValue} method. |
95 * <p> |
66 * <p> |
96 * The actual installation of the value on the class |
67 * The actual installation of the value on the class |
97 * is performed atomically. |
68 * is performed atomically. |
98 * At that point, if racing threads have |
69 * At that point, if several racing threads have |
99 * computed values, one is chosen, and returned to |
70 * computed values, one is chosen, and returned to |
100 * all the racing threads. |
71 * all the racing threads. |
|
72 * <p> |
|
73 * The {@code type} parameter is typically a class, but it may be any type, |
|
74 * such as an interface, a primitive type (like {@code int.class}), or {@code void.class}. |
|
75 * <p> |
|
76 * In the absence of {@code remove} calls, a class value has a simple |
|
77 * state diagram: uninitialized and initialized. |
|
78 * When {@code remove} calls are made, |
|
79 * the rules for value observation are more complex. |
|
80 * See the documentation for {@link #remove remove} for more information. |
101 * |
81 * |
|
82 * @param type the type whose class value must be computed or retrieved |
102 * @return the current value associated with this {@code ClassValue}, for the given class or interface |
83 * @return the current value associated with this {@code ClassValue}, for the given class or interface |
|
84 * @throws NullPointerException if the argument is null |
|
85 * @see #remove |
|
86 * @see #computeValue |
103 */ |
87 */ |
104 public T get(Class<?> type) { |
88 public T get(Class<?> type) { |
105 ClassValueMap map = getMap(type); |
89 ClassValueMap map = getMap(type); |
106 if (map != null) { |
90 if (map != null) { |
107 Object x = map.get(this); |
91 Object x = map.get(this); |
117 * If this value is subsequently {@linkplain #get read} for the same class, |
101 * If this value is subsequently {@linkplain #get read} for the same class, |
118 * its value will be reinitialized by invoking its {@link #computeValue computeValue} method. |
102 * its value will be reinitialized by invoking its {@link #computeValue computeValue} method. |
119 * This may result in an additional invocation of the |
103 * This may result in an additional invocation of the |
120 * {@code computeValue computeValue} method for the given class. |
104 * {@code computeValue computeValue} method for the given class. |
121 * <p> |
105 * <p> |
122 * If racing threads perform a combination of {@code get} and {@code remove} calls, |
106 * In order to explain the interaction between {@code get} and {@code remove} calls, |
123 * the calls are serialized. |
107 * we must model the state transitions of a class value to take into account |
124 * A value produced by a call to {@code computeValue} will be discarded, if |
108 * the alternation between uninitialized and initialized states. |
125 * the corresponding {@code get} call was followed by a {@code remove} call |
109 * To do this, number these states sequentially from zero, and note that |
126 * before the {@code computeValue} could complete. |
110 * uninitialized (or removed) states are numbered with even numbers, |
127 * In such a case, the {@code get} call will re-invoke {@code computeValue}. |
111 * while initialized (or re-initialized) states have odd numbers. |
|
112 * <p> |
|
113 * When a thread {@code T} removes a class value in state {@code 2N}, |
|
114 * nothing happens, since the class value is already uninitialized. |
|
115 * Otherwise, the state is advanced atomically to {@code 2N+1}. |
|
116 * <p> |
|
117 * When a thread {@code T} queries a class value in state {@code 2N}, |
|
118 * the thread first attempts to initialize the class value to state {@code 2N+1} |
|
119 * by invoking {@code computeValue} and installing the resulting value. |
|
120 * <p> |
|
121 * When {@code T} attempts to install the newly computed value, |
|
122 * if the state is still at {@code 2N}, the class value will be initialized |
|
123 * with the computed value, advancing it to state {@code 2N+1}. |
|
124 * <p> |
|
125 * Otherwise, whether the new state is even or odd, |
|
126 * {@code T} will discard the newly computed value |
|
127 * and retry the {@code get} operation. |
|
128 * <p> |
|
129 * Discarding and retrying is an important proviso, |
|
130 * since otherwise {@code T} could potentially install |
|
131 * a disastrously stale value. For example: |
|
132 * <ul> |
|
133 * <li>{@code T} calls {@code CV.get(C)} and sees state {@code 2N} |
|
134 * <li>{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it |
|
135 * <li>{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time |
|
136 * <li>...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N} |
|
137 * <li>{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)} |
|
138 * <li>{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work |
|
139 * <li> the previous actions of {@code T2} are repeated several times |
|
140 * <li> also, the relevant computed values change over time: {@code V1}, {@code V2}, ... |
|
141 * <li>...meanwhile, {@code T} wakes up and attempts to install {@code V0}; <em>this must fail</em> |
|
142 * </ul> |
|
143 * We can assume in the above scenario that {@code CV.computeValue} uses locks to properly |
|
144 * observe the time-dependent states as it computes {@code V1}, etc. |
|
145 * This does not remove the threat of a stale value, since there is a window of time |
|
146 * between the return of {@code computeValue} in {@code T} and the installation |
|
147 * of the the new value. No user synchronization is possible during this time. |
|
148 * |
|
149 * @param type the type whose class value must be removed |
|
150 * @throws NullPointerException if the argument is null |
128 */ |
151 */ |
129 public void remove(Class<?> type) { |
152 public void remove(Class<?> type) { |
130 ClassValueMap map = getMap(type); |
153 ClassValueMap map = getMap(type); |
131 if (map != null) { |
154 if (map != null) { |
132 synchronized (map) { |
155 synchronized (map) { |