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
17package com.google.common.collect;
18
19import static com.google.common.util.concurrent.Uninterruptibles.awaitUninterruptibly;
20
21import com.google.common.base.Function;
22import com.google.common.collect.MapMaker.RemovalNotification;
23import com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener;
24import com.google.common.testing.NullPointerTester;
25
26import junit.framework.TestCase;
27
28import java.util.Map;
29import java.util.Set;
30import java.util.concurrent.ConcurrentMap;
31import java.util.concurrent.CountDownLatch;
32import java.util.concurrent.ExecutorService;
33import java.util.concurrent.Executors;
34import java.util.concurrent.atomic.AtomicInteger;
35
36/**
37 * @author Charles Fry
38 */
39public 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