Home | History | Annotate | Download | only in collect 
      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.util.concurrent.Uninterruptibles.awaitUninterruptibly;
     20 
     21 import com.google.common.base.Function;
     22 import com.google.common.collect.MapMaker.RemovalNotification;
     23 import com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener;
     24 import com.google.common.testing.NullPointerTester;
     25 
     26 import junit.framework.TestCase;
     27 
     28 import java.util.Map;
     29 import java.util.Set;
     30 import java.util.concurrent.ConcurrentMap;
     31 import java.util.concurrent.CountDownLatch;
     32 import java.util.concurrent.ExecutorService;
     33 import java.util.concurrent.Executors;
     34 import java.util.concurrent.atomic.AtomicInteger;
     35 
     36 /**
     37  * @author Charles Fry
     38  */
     39 public class MapMakerTest extends TestCase {
     40 
     41   public void testNullParameters() throws Exception {
     42     NullPointerTester tester = new NullPointerTester();
     43     tester.testAllPublicInstanceMethods(new MapMaker());
     44   }
     45 
     46   public void testRemovalNotification_clear() throws InterruptedException {
     47     // If a clear() happens while a computation is pending, we should not get a removal
     48     // notification.
     49 
     50     final CountDownLatch computingLatch = new CountDownLatch(1);
     51     Function<String, String> computingFunction = new DelayingIdentityLoader(computingLatch);
     52     QueuingRemovalListener<String, String> listener = new QueuingRemovalListener<String, String>();
     53 
     54     @SuppressWarnings("deprecation") // test of deprecated code
     55     final ConcurrentMap<String, String> map = new MapMaker()
     56         .concurrencyLevel(1)
     57         .removalListener(listener)
     58         .makeComputingMap(computingFunction);
     59 
     60     // seed the map, so its segment's count > 0
     61     map.put("a", "a");
     62 
     63     final CountDownLatch computationStarted = new CountDownLatch(1);
     64     final CountDownLatch computationComplete = new CountDownLatch(1);
     65     new Thread(new Runnable() {
     66       @Override public void run() {
     67         computationStarted.countDown();
     68         map.get("b");
     69         computationComplete.countDown();
     70       }
     71     }).start();
     72 
     73     // wait for the computingEntry to be created
     74     computationStarted.await();
     75     map.clear();
     76     // let the computation proceed
     77     computingLatch.countDown();
     78     // don't check map.size() until we know the get("b") call is complete
     79     computationComplete.await();
     80 
     81     // At this point, the listener should be holding the seed value (a -> a), and the map should
     82     // contain the computed value (b -> b), since the clear() happened before the computation
     83     // completed.
     84     assertEquals(1, listener.size());
     85     RemovalNotification<String, String> notification = listener.remove();
     86     assertEquals("a", notification.getKey());
     87     assertEquals("a", notification.getValue());
     88     assertEquals(1, map.size());
     89     assertEquals("b", map.get("b"));
     90   }
     91 
     92   // "Basher tests", where we throw a bunch of stuff at a Cache and check basic invariants.
     93 
     94   /**
     95    * This is a less carefully-controlled version of {@link #testRemovalNotification_clear} - this is
     96    * a black-box test that tries to create lots of different thread-interleavings, and asserts that
     97    * each computation is affected by a call to {@code clear()} (and therefore gets passed to the
     98    * removal listener), or else is not affected by the {@code clear()} (and therefore exists in the
     99    * map afterward).
    100    */
    101 
    102   public void testRemovalNotification_clear_basher() throws InterruptedException {
    103     // If a clear() happens close to the end of computation, one of two things should happen:
    104     // - computation ends first: the removal listener is called, and the map does not contain the
    105     //   key/value pair
    106     // - clear() happens first: the removal listener is not called, and the map contains the pair
    107     CountDownLatch computationLatch = new CountDownLatch(1);
    108     QueuingRemovalListener<String, String> listener = new QueuingRemovalListener<String, String>();
    109 
    110     @SuppressWarnings("deprecation") // test of deprecated code
    111     final Map<String, String> map = new MapMaker()
    112         .removalListener(listener)
    113         .concurrencyLevel(20)
    114         .makeComputingMap(new DelayingIdentityLoader<String>(computationLatch));
    115 
    116     int nThreads = 100;
    117     int nTasks = 1000;
    118     int nSeededEntries = 100;
    119     Set<String> expectedKeys = Sets.newHashSetWithExpectedSize(nTasks + nSeededEntries);
    120     // seed the map, so its segments have a count>0; otherwise, clear() won't visit the in-progress
    121     // entries
    122     for (int i = 0; i < nSeededEntries; i++) {
    123       String s = "b" + i;
    124       map.put(s, s);
    125       expectedKeys.add(s);
    126     }
    127 
    128     final AtomicInteger computedCount = new AtomicInteger();
    129     ExecutorService threadPool = Executors.newFixedThreadPool(nThreads);
    130     final CountDownLatch tasksFinished = new CountDownLatch(nTasks);
    131     for (int i = 0; i < nTasks; i++) {
    132       final String s = "a" + i;
    133       threadPool.submit(new Runnable() {
    134         @Override public void run() {
    135           map.get(s);
    136           computedCount.incrementAndGet();
    137           tasksFinished.countDown();
    138         }
    139       });
    140       expectedKeys.add(s);
    141     }
    142 
    143     computationLatch.countDown();
    144     // let some computations complete
    145     while (computedCount.get() < nThreads) {
    146       Thread.yield();
    147     }
    148     map.clear();
    149     tasksFinished.await();
    150 
    151     // Check all of the removal notifications we received: they should have had correctly-associated
    152     // keys and values. (An earlier bug saw removal notifications for in-progress computations,
    153     // which had real keys with null values.)
    154     Map<String, String> removalNotifications = Maps.newHashMap();
    155     for (RemovalNotification<String, String> notification : listener) {
    156       removalNotifications.put(notification.getKey(), notification.getValue());
    157       assertEquals("Unexpected key/value pair passed to removalListener",
    158           notification.getKey(), notification.getValue());
    159     }
    160 
    161     // All of the seed values should have been visible, so we should have gotten removal
    162     // notifications for all of them.
    163     for (int i = 0; i < nSeededEntries; i++) {
    164       assertEquals("b" + i, removalNotifications.get("b" + i));
    165     }
    166 
    167     // Each of the values added to the map should either still be there, or have seen a removal
    168     // notification.
    169     assertEquals(expectedKeys, Sets.union(map.keySet(), removalNotifications.keySet()));
    170     assertTrue(Sets.intersection(map.keySet(), removalNotifications.keySet()).isEmpty());
    171   }
    172 
    173   static final class DelayingIdentityLoader<T> implements Function<T, T> {
    174     private final CountDownLatch delayLatch;
    175 
    176     DelayingIdentityLoader(CountDownLatch delayLatch) {
    177       this.delayLatch = delayLatch;
    178     }
    179 
    180     @Override public T apply(T key) {
    181       awaitUninterruptibly(delayLatch);
    182       return key;
    183     }
    184   }
    185 }
    186