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.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 * @author Charles Fry 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 // constructor tests 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 // computation tests 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 // access some of the elements 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") // test of deprecated method 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 // TODO(user): May be a good candidate to play with the MultithreadedTestCase 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)); // force notifications 296 assertNotified(listener, one, computedObject, RemovalCause.REPLACED); 297 assertTrue(listener.isEmpty()); 298 } 299 300 // computing functions 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 } 343