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.util.concurrent.Uninterruptibles.awaitUninterruptibly; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMaker.RemovalNotification; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.NullPointerTester; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.TestCase; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ConcurrentMap; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.CountDownLatch; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ExecutorService; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.Executors; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.atomic.AtomicInteger; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Charles Fry 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class MapMakerTest extends TestCase { 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testNullParameters() throws Exception { 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NullPointerTester tester = new NullPointerTester(); 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicInstanceMethods(new MapMaker()); 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemovalNotification_clear() throws InterruptedException { 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // If a clear() happens while a computation is pending, we should not get a removal 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // notification. 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch computingLatch = new CountDownLatch(1); 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<String, String> computingFunction = new DelayingIdentityLoader(computingLatch); 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert QueuingRemovalListener<String, String> listener = new QueuingRemovalListener<String, String>(); 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("deprecation") // test of deprecated code 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ConcurrentMap<String, String> map = new MapMaker() 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .concurrencyLevel(1) 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .removalListener(listener) 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .makeComputingMap(computingFunction); 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // seed the map, so its segment's count > 0 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.put("a", "a"); 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch computationStarted = new CountDownLatch(1); 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch computationComplete = new CountDownLatch(1); 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new Thread(new Runnable() { 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public void run() { 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computationStarted.countDown(); 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.get("b"); 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computationComplete.countDown(); 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }).start(); 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // wait for the computingEntry to be created 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computationStarted.await(); 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.clear(); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // let the computation proceed 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computingLatch.countDown(); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // don't check map.size() until we know the get("b") call is complete 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computationComplete.await(); 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // At this point, the listener should be holding the seed value (a -> a), and the map should 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // contain the computed value (b -> b), since the clear() happened before the computation 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // completed. 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, listener.size()); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert RemovalNotification<String, String> notification = listener.remove(); 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("a", notification.getKey()); 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("a", notification.getValue()); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, map.size()); 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("b", map.get("b")); 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // "Basher tests", where we throw a bunch of stuff at a Cache and check basic invariants. 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This is a less carefully-controlled version of {@link #testRemovalNotification_clear} - this is 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * a black-box test that tries to create lots of different thread-interleavings, and asserts that 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * each computation is affected by a call to {@code clear()} (and therefore gets passed to the 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * removal listener), or else is not affected by the {@code clear()} (and therefore exists in the 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * map afterward). 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemovalNotification_clear_basher() throws InterruptedException { 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // If a clear() happens close to the end of computation, one of two things should happen: 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // - computation ends first: the removal listener is called, and the map does not contain the 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // key/value pair 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // - clear() happens first: the removal listener is not called, and the map contains the pair 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CountDownLatch computationLatch = new CountDownLatch(1); 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert QueuingRemovalListener<String, String> listener = new QueuingRemovalListener<String, String>(); 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("deprecation") // test of deprecated code 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Map<String, String> map = new MapMaker() 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .removalListener(listener) 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .concurrencyLevel(20) 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .makeComputingMap(new DelayingIdentityLoader<String>(computationLatch)); 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int nThreads = 100; 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int nTasks = 1000; 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int nSeededEntries = 100; 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<String> expectedKeys = Sets.newHashSetWithExpectedSize(nTasks + nSeededEntries); 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // seed the map, so its segments have a count>0; otherwise, clear() won't visit the in-progress 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // entries 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < nSeededEntries; i++) { 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert String s = "b" + i; 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.put(s, s); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert expectedKeys.add(s); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final AtomicInteger computedCount = new AtomicInteger(); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ExecutorService threadPool = Executors.newFixedThreadPool(nThreads); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final CountDownLatch tasksFinished = new CountDownLatch(nTasks); 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < nTasks; i++) { 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final String s = "a" + i; 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert threadPool.submit(new Runnable() { 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public void run() { 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.get(s); 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computedCount.incrementAndGet(); 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tasksFinished.countDown(); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }); 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert expectedKeys.add(s); 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert computationLatch.countDown(); 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // let some computations complete 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (computedCount.get() < nThreads) { 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Thread.yield(); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert map.clear(); 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tasksFinished.await(); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Check all of the removal notifications we received: they should have had correctly-associated 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // keys and values. (An earlier bug saw removal notifications for in-progress computations, 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // which had real keys with null values.) 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<String, String> removalNotifications = Maps.newHashMap(); 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (RemovalNotification<String, String> notification : listener) { 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert removalNotifications.put(notification.getKey(), notification.getValue()); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Unexpected key/value pair passed to removalListener", 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert notification.getKey(), notification.getValue()); 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // All of the seed values should have been visible, so we should have gotten removal 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // notifications for all of them. 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < nSeededEntries; i++) { 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("b" + i, removalNotifications.get("b" + i)); 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Each of the values added to the map should either still be there, or have seen a removal 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // notification. 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(expectedKeys, Sets.union(map.keySet(), removalNotifications.keySet())); 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(Sets.intersection(map.keySet(), removalNotifications.keySet()).isEmpty()); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class DelayingIdentityLoader<T> implements Function<T, T> { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final CountDownLatch delayLatch; 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert DelayingIdentityLoader(CountDownLatch delayLatch) { 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.delayLatch = delayLatch; 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public T apply(T key) { 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert awaitUninterruptibly(delayLatch); 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return key; 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 186