11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMap.DRAIN_THRESHOLD; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.SMALL_MAX_SIZE; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.allEvictingMakers; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.assertNotified; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.checkAndDrainRecencyQueue; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.checkEvictionQueues; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.MapMakerInternalMapTest.checkExpirationTimes; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.ComputingConcurrentHashMap.ComputingMapAdapter; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMaker.RemovalCause; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMap.ReferenceEntry; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMap.Segment; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMapTest.DummyEntry; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMapTest.DummyValueReference; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.NullPointerTester; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.TestCase; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Random; 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.CountDownLatch; 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ExecutionException; 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.TimeUnit; 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.atomic.AtomicInteger; 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.atomic.AtomicReferenceArray; 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Charles Fry 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class ComputingConcurrentHashMapTest extends TestCase { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> ComputingConcurrentHashMap<K, V> makeComputingMap( 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker, Function<? super K, ? extends V> computingFunction) { 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ComputingConcurrentHashMap<K, V>( 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert maker, computingFunction); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> ComputingMapAdapter<K, V> makeAdaptedMap( 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker, Function<? super K, ? extends V> computingFunction) { 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ComputingMapAdapter<K, V>( 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert maker, computingFunction); 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private MapMaker createMapMaker() { 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker = new MapMaker(); 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert maker.useCustomMap = true; 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return maker; 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // constructor tests 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputingFunction() { 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<Object, Object> computingFunction = new Function<Object, Object>() { 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Object apply(Object from) { 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return from; 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert makeComputingMap(createMapMaker(), computingFunction); 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(computingFunction, map.computingFunction); 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // computation tests 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCompute() throws ExecutionException { 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert makeComputingMap(createMapMaker(), computingFunction); 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object value = map.getOrCompute(key); 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, computingFunction.getCount()); 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(value, map.getOrCompute(key)); 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, computingFunction.getCount()); 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputeNull() { 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<Object, Object> computingFunction = new ConstantLoader<Object, Object>(null); 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingMapAdapter<Object, Object> map = makeAdaptedMap(createMapMaker(), computingFunction); 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.get(new Object()); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail(); 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException expected) {} 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRecordReadOnCompute() throws ExecutionException { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (MapMaker maker : allEvictingMakers()) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert makeComputingMap(maker.concurrencyLevel(1), computingFunction); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Segment<Object, Object> segment = map.segments[0]; 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList(); 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList(); 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < SMALL_MAX_SIZE; i++) { 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int hash = map.hash(key); 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.getOrCompute(key); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash); 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert writeOrder.add(entry); 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert readOrder.add(entry); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkEvictionQueues(map, segment, readOrder, writeOrder); 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkExpirationTimes(map); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(segment.recencyQueue.isEmpty()); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // access some of the elements 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(); 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList(); 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator(); 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (i.hasNext()) { 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ReferenceEntry<Object, Object> entry = i.next(); 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (random.nextBoolean()) { 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.getOrCompute(entry.getKey()); 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert reads.add(entry); 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert i.remove(); 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD); 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int undrainedIndex = reads.size() - segment.recencyQueue.size(); 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size())); 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert readOrder.addAll(reads); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkEvictionQueues(map, segment, readOrder, writeOrder); 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkExpirationTimes(map); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputeExistingEntry() throws ExecutionException { 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert makeComputingMap(createMapMaker(), computingFunction); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object value = new Object(); 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.put(key, value); 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(value, map.getOrCompute(key)); 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputePartiallyCollectedKey() throws ExecutionException { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker = createMapMaker().concurrencyLevel(1); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Segment<Object, Object> segment = map.segments[0]; 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int hash = map.hash(key); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object value = new Object(); 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index = hash & (table.length() - 1); 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry); 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entry.setValueReference(valueRef); 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert table.set(index, entry); 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert segment.count++; 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(value, map.getOrCompute(key)); 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, segment.count); 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entry.clearKey(); 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNotSame(value, map.getOrCompute(key)); 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, computingFunction.getCount()); 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, segment.count); 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputePartiallyCollectedValue() throws ExecutionException { 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker = createMapMaker().concurrencyLevel(1); 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction); 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Segment<Object, Object> segment = map.segments[0]; 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table; 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int hash = map.hash(key); 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object value = new Object(); 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index = hash & (table.length() - 1); 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry); 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entry.setValueReference(valueRef); 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert table.set(index, entry); 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert segment.count++; 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(value, map.getOrCompute(key)); 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, segment.count); 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert valueRef.clear(null); 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNotSame(value, map.getOrCompute(key)); 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, computingFunction.getCount()); 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, segment.count); 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("deprecation") // test of deprecated method 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testComputeExpiredEntry() throws ExecutionException { 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker = createMapMaker().expireAfterWrite(1, TimeUnit.NANOSECONDS); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountingFunction computingFunction = new CountingFunction(); 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, computingFunction.getCount()); 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key = new Object(); 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object one = map.getOrCompute(key); 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, computingFunction.getCount()); 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object two = map.getOrCompute(key); 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNotSame(one, two); 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, computingFunction.getCount()); 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemovalListener_replaced() { 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): May be a good candidate to play with the MultithreadedTestCase 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch startSignal = new CountDownLatch(1); 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch computingSignal = new CountDownLatch(1); 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch doneSignal = new CountDownLatch(1); 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Object computedObject = new Object(); 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<Object, Object> computingFunction = new Function<Object, Object>() { 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Object apply(Object key) { 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computingSignal.countDown(); 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert startSignal.await(); 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (InterruptedException e) { 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new RuntimeException(e); 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return computedObject; 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert QueuingRemovalListener<Object, Object> listener = 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new QueuingRemovalListener<Object, Object>(); 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapMaker maker = (MapMaker) createMapMaker().removalListener(listener); 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ComputingConcurrentHashMap<Object, Object> map = 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert makeComputingMap(maker, computingFunction); 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(listener.isEmpty()); 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Object one = new Object(); 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Object two = new Object(); 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Object three = new Object(); 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new Thread() { 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void run() { 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.getOrCompute(one); 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ExecutionException e) { 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new RuntimeException(e); 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert doneSignal.countDown(); 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }.start(); 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computingSignal.await(); 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (InterruptedException e) { 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new RuntimeException(e); 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.put(one, two); 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert startSignal.countDown(); 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert doneSignal.await(); 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (InterruptedException e) { 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new RuntimeException(e); 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNotNull(map.putIfAbsent(one, three)); // force notifications 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNotified(listener, one, computedObject, RemovalCause.REPLACED); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(listener.isEmpty()); 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // computing functions 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class CountingFunction implements Function<Object, Object> { 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final AtomicInteger count = new AtomicInteger(); 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Object apply(Object from) { 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert count.incrementAndGet(); 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Object(); 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int getCount() { 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count.get(); 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testNullParameters() throws Exception { 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NullPointerTester tester = new NullPointerTester(); 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<Object, Object> computingFunction = new IdentityLoader<Object>(); 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicInstanceMethods(makeComputingMap(createMapMaker(), computingFunction)); 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class ConstantLoader<K, V> implements Function<K, V> { 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final V constant; 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public ConstantLoader(V constant) { 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.constant = constant; 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public V apply(K key) { 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return constant; 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class IdentityLoader<T> implements Function<T, T> { 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public T apply(T key) { 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return key; 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 347