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