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.collect.MapMakerInternalMap.DRAIN_THRESHOLD;
20import static com.google.common.collect.MapMakerInternalMapTest.SMALL_MAX_SIZE;
21import static com.google.common.collect.MapMakerInternalMapTest.allEvictingMakers;
22import static com.google.common.collect.MapMakerInternalMapTest.assertNotified;
23import static com.google.common.collect.MapMakerInternalMapTest.checkAndDrainRecencyQueue;
24import static com.google.common.collect.MapMakerInternalMapTest.checkEvictionQueues;
25import static com.google.common.collect.MapMakerInternalMapTest.checkExpirationTimes;
26
27import com.google.common.base.Function;
28import com.google.common.base.Functions;
29import com.google.common.collect.MapMaker.ComputingMapAdapter;
30import com.google.common.collect.MapMaker.RemovalCause;
31import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
32import com.google.common.collect.MapMakerInternalMap.Segment;
33import com.google.common.collect.MapMakerInternalMapTest.DummyEntry;
34import com.google.common.collect.MapMakerInternalMapTest.DummyValueReference;
35import com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener;
36import com.google.common.testing.NullPointerTester;
37
38import junit.framework.TestCase;
39
40import java.util.Iterator;
41import java.util.List;
42import java.util.Random;
43import java.util.concurrent.CountDownLatch;
44import java.util.concurrent.ExecutionException;
45import java.util.concurrent.TimeUnit;
46import java.util.concurrent.atomic.AtomicInteger;
47import java.util.concurrent.atomic.AtomicReferenceArray;
48
49/**
50 * @author Charles Fry
51 */
52public 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