1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD;
20 import static com.google.common.collect.MapMakerInternalMapTest.SMALL_MAX_SIZE;
21 import static com.google.common.collect.MapMakerInternalMapTest.allEvictingMakers;
22 import static com.google.common.collect.MapMakerInternalMapTest.assertNotified;
23 import static com.google.common.collect.MapMakerInternalMapTest.checkAndDrainRecencyQueue;
24 import static com.google.common.collect.MapMakerInternalMapTest.checkEvictionQueues;
25 import static com.google.common.collect.MapMakerInternalMapTest.checkExpirationTimes;
26
27 import com.google.common.base.Function;
28 import com.google.common.base.Functions;
29 import com.google.common.collect.MapMaker.ComputingMapAdapter;
30 import com.google.common.collect.MapMaker.RemovalCause;
31 import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
32 import com.google.common.collect.MapMakerInternalMap.Segment;
33 import com.google.common.collect.MapMakerInternalMapTest.DummyEntry;
34 import com.google.common.collect.MapMakerInternalMapTest.DummyValueReference;
35 import com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener;
36 import com.google.common.testing.NullPointerTester;
37
38 import junit.framework.TestCase;
39
40 import java.util.Iterator;
41 import java.util.List;
42 import java.util.Random;
43 import java.util.concurrent.CountDownLatch;
44 import java.util.concurrent.ExecutionException;
45 import java.util.concurrent.TimeUnit;
46 import java.util.concurrent.atomic.AtomicInteger;
47 import java.util.concurrent.atomic.AtomicReferenceArray;
48
49
50
51
52 public class ComputingConcurrentHashMapTest extends TestCase {
53
54 private static <K, V> ComputingConcurrentHashMap<K, V> makeComputingMap(
55 MapMaker maker, Function<? super K, ? extends V> computingFunction) {
56 return new ComputingConcurrentHashMap<K, V>(
57 maker, computingFunction);
58 }
59
60 private static <K, V> ComputingMapAdapter<K, V> makeAdaptedMap(
61 MapMaker maker, Function<? super K, ? extends V> computingFunction) {
62 return new ComputingMapAdapter<K, V>(
63 maker, computingFunction);
64 }
65
66 private MapMaker createMapMaker() {
67 MapMaker maker = new MapMaker();
68 maker.useCustomMap = true;
69 return maker;
70 }
71
72
73
74 public void testComputingFunction() {
75 Function<Object, Object> computingFunction = Functions.identity();
76 ComputingConcurrentHashMap<Object, Object> map =
77 makeComputingMap(createMapMaker(), computingFunction);
78 assertSame(computingFunction, map.computingFunction);
79 }
80
81
82
83 public void testCompute() throws ExecutionException {
84 CountingFunction computingFunction = new CountingFunction();
85 ComputingConcurrentHashMap<Object, Object> map =
86 makeComputingMap(createMapMaker(), computingFunction);
87 assertEquals(0, computingFunction.getCount());
88
89 Object key = new Object();
90 Object value = map.getOrCompute(key);
91 assertEquals(1, computingFunction.getCount());
92 assertEquals(value, map.getOrCompute(key));
93 assertEquals(1, computingFunction.getCount());
94 }
95
96 public void testComputeNull() {
97 Function<Object, Object> computingFunction = new ConstantLoader<Object, Object>(null);
98 ComputingMapAdapter<Object, Object> map = makeAdaptedMap(createMapMaker(), computingFunction);
99 try {
100 map.get(new Object());
101 fail();
102 } catch (NullPointerException expected) {}
103 }
104
105 public void testRecordReadOnCompute() throws ExecutionException {
106 CountingFunction computingFunction = new CountingFunction();
107 for (MapMaker maker : allEvictingMakers()) {
108 ComputingConcurrentHashMap<Object, Object> map =
109 makeComputingMap(maker.concurrencyLevel(1), computingFunction);
110 Segment<Object, Object> segment = map.segments[0];
111 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
112 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
113 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
114 Object key = new Object();
115 int hash = map.hash(key);
116
117 map.getOrCompute(key);
118 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
119 writeOrder.add(entry);
120 readOrder.add(entry);
121 }
122
123 checkEvictionQueues(map, segment, readOrder, writeOrder);
124 checkExpirationTimes(map);
125 assertTrue(segment.recencyQueue.isEmpty());
126
127
128 Random random = new Random();
129 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
130 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
131 while (i.hasNext()) {
132 ReferenceEntry<Object, Object> entry = i.next();
133 if (random.nextBoolean()) {
134 map.getOrCompute(entry.getKey());
135 reads.add(entry);
136 i.remove();
137 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
138 }
139 }
140 int undrainedIndex = reads.size() - segment.recencyQueue.size();
141 checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
142 readOrder.addAll(reads);
143
144 checkEvictionQueues(map, segment, readOrder, writeOrder);
145 checkExpirationTimes(map);
146 }
147 }
148
149 public void testComputeExistingEntry() throws ExecutionException {
150 CountingFunction computingFunction = new CountingFunction();
151 ComputingConcurrentHashMap<Object, Object> map =
152 makeComputingMap(createMapMaker(), computingFunction);
153 assertEquals(0, computingFunction.getCount());
154
155 Object key = new Object();
156 Object value = new Object();
157 map.put(key, value);
158
159 assertEquals(value, map.getOrCompute(key));
160 assertEquals(0, computingFunction.getCount());
161 }
162
163 public void testComputePartiallyCollectedKey() throws ExecutionException {
164 MapMaker maker = createMapMaker().concurrencyLevel(1);
165 CountingFunction computingFunction = new CountingFunction();
166 ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
167 Segment<Object, Object> segment = map.segments[0];
168 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
169 assertEquals(0, computingFunction.getCount());
170
171 Object key = new Object();
172 int hash = map.hash(key);
173 Object value = new Object();
174 int index = hash & (table.length() - 1);
175
176 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
177 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
178 entry.setValueReference(valueRef);
179 table.set(index, entry);
180 segment.count++;
181
182 assertSame(value, map.getOrCompute(key));
183 assertEquals(0, computingFunction.getCount());
184 assertEquals(1, segment.count);
185
186 entry.clearKey();
187 assertNotSame(value, map.getOrCompute(key));
188 assertEquals(1, computingFunction.getCount());
189 assertEquals(2, segment.count);
190 }
191
192 public void testComputePartiallyCollectedValue() throws ExecutionException {
193 MapMaker maker = createMapMaker().concurrencyLevel(1);
194 CountingFunction computingFunction = new CountingFunction();
195 ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
196 Segment<Object, Object> segment = map.segments[0];
197 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
198 assertEquals(0, computingFunction.getCount());
199
200 Object key = new Object();
201 int hash = map.hash(key);
202 Object value = new Object();
203 int index = hash & (table.length() - 1);
204
205 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
206 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
207 entry.setValueReference(valueRef);
208 table.set(index, entry);
209 segment.count++;
210
211 assertSame(value, map.getOrCompute(key));
212 assertEquals(0, computingFunction.getCount());
213 assertEquals(1, segment.count);
214
215 valueRef.clear(null);
216 assertNotSame(value, map.getOrCompute(key));
217 assertEquals(1, computingFunction.getCount());
218 assertEquals(1, segment.count);
219 }
220
221 @SuppressWarnings("deprecation")
222 public void testComputeExpiredEntry() throws ExecutionException {
223 MapMaker maker = createMapMaker().expireAfterWrite(1, TimeUnit.NANOSECONDS);
224 CountingFunction computingFunction = new CountingFunction();
225 ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
226 assertEquals(0, computingFunction.getCount());
227
228 Object key = new Object();
229 Object one = map.getOrCompute(key);
230 assertEquals(1, computingFunction.getCount());
231
232 Object two = map.getOrCompute(key);
233 assertNotSame(one, two);
234 assertEquals(2, computingFunction.getCount());
235 }
236
237 public void testRemovalListener_replaced() {
238
239 final CountDownLatch startSignal = new CountDownLatch(1);
240 final CountDownLatch computingSignal = new CountDownLatch(1);
241 final CountDownLatch doneSignal = new CountDownLatch(1);
242 final Object computedObject = new Object();
243
244 Function<Object, Object> computingFunction = new Function<Object, Object>() {
245 @Override
246 public Object apply(Object key) {
247 computingSignal.countDown();
248 try {
249 startSignal.await();
250 } catch (InterruptedException e) {
251 throw new RuntimeException(e);
252 }
253 return computedObject;
254 }
255 };
256
257 QueuingRemovalListener<Object, Object> listener =
258 new QueuingRemovalListener<Object, Object>();
259 MapMaker maker = (MapMaker) createMapMaker().removalListener(listener);
260 final ComputingConcurrentHashMap<Object, Object> map =
261 makeComputingMap(maker, computingFunction);
262 assertTrue(listener.isEmpty());
263
264 final Object one = new Object();
265 final Object two = new Object();
266 final Object three = new Object();
267
268 new Thread() {
269 @Override
270 public void run() {
271 try {
272 map.getOrCompute(one);
273 } catch (ExecutionException e) {
274 throw new RuntimeException(e);
275 }
276 doneSignal.countDown();
277 }
278 }.start();
279
280 try {
281 computingSignal.await();
282 } catch (InterruptedException e) {
283 throw new RuntimeException(e);
284 }
285
286 map.put(one, two);
287 startSignal.countDown();
288
289 try {
290 doneSignal.await();
291 } catch (InterruptedException e) {
292 throw new RuntimeException(e);
293 }
294
295 assertNotNull(map.putIfAbsent(one, three));
296 assertNotified(listener, one, computedObject, RemovalCause.REPLACED);
297 assertTrue(listener.isEmpty());
298 }
299
300
301
302 private static class CountingFunction implements Function<Object, Object> {
303 private final AtomicInteger count = new AtomicInteger();
304
305 @Override
306 public Object apply(Object from) {
307 count.incrementAndGet();
308 return new Object();
309 }
310
311 public int getCount() {
312 return count.get();
313 }
314 }
315
316 public void testNullParameters() throws Exception {
317 NullPointerTester tester = new NullPointerTester();
318 Function<Object, Object> computingFunction = new IdentityLoader<Object>();
319 tester.testAllPublicInstanceMethods(makeComputingMap(createMapMaker(), computingFunction));
320 }
321
322 static final class ConstantLoader<K, V> implements Function<K, V> {
323 private final V constant;
324
325 public ConstantLoader(V constant) {
326 this.constant = constant;
327 }
328
329 @Override
330 public V apply(K key) {
331 return constant;
332 }
333 }
334
335 static final class IdentityLoader<T> implements Function<T, T> {
336 @Override
337 public T apply(T key) {
338 return key;
339 }
340 }
341
342 }