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.collect.ComputingConcurrentHashMap.ComputingMapAdapter;
29import com.google.common.collect.MapMaker.RemovalCause;
30import com.google.common.collect.MapMakerInternalMap.ReferenceEntry;
31import com.google.common.collect.MapMakerInternalMap.Segment;
32import com.google.common.collect.MapMakerInternalMapTest.DummyEntry;
33import com.google.common.collect.MapMakerInternalMapTest.DummyValueReference;
34import com.google.common.collect.MapMakerInternalMapTest.QueuingRemovalListener;
35import com.google.common.testing.NullPointerTester;
36
37import junit.framework.TestCase;
38
39import java.util.Iterator;
40import java.util.List;
41import java.util.Random;
42import java.util.concurrent.CountDownLatch;
43import java.util.concurrent.ExecutionException;
44import java.util.concurrent.TimeUnit;
45import java.util.concurrent.atomic.AtomicInteger;
46import java.util.concurrent.atomic.AtomicReferenceArray;
47
48/**
49 * @author Charles Fry
50 */
51public class ComputingConcurrentHashMapTest extends TestCase {
52
53  private static <K, V> ComputingConcurrentHashMap<K, V> makeComputingMap(
54      MapMaker maker, Function<? super K, ? extends V> computingFunction) {
55    return new ComputingConcurrentHashMap<K, V>(
56        maker, computingFunction);
57  }
58
59  private static <K, V> ComputingMapAdapter<K, V> makeAdaptedMap(
60      MapMaker maker, Function<? super K, ? extends V> computingFunction) {
61    return new ComputingMapAdapter<K, V>(
62        maker, computingFunction);
63  }
64
65  private MapMaker createMapMaker() {
66    MapMaker maker = new MapMaker();
67    maker.useCustomMap = true;
68    return maker;
69  }
70
71  // constructor tests
72
73  public void testComputingFunction() {
74    Function<Object, Object> computingFunction = new Function<Object, Object>() {
75      @Override
76      public Object apply(Object from) {
77        return from;
78      }
79    };
80    ComputingConcurrentHashMap<Object, Object> map =
81        makeComputingMap(createMapMaker(), computingFunction);
82    assertSame(computingFunction, map.computingFunction);
83  }
84
85  // computation tests
86
87  public void testCompute() throws ExecutionException {
88    CountingFunction computingFunction = new CountingFunction();
89    ComputingConcurrentHashMap<Object, Object> map =
90        makeComputingMap(createMapMaker(), computingFunction);
91    assertEquals(0, computingFunction.getCount());
92
93    Object key = new Object();
94    Object value = map.getOrCompute(key);
95    assertEquals(1, computingFunction.getCount());
96    assertEquals(value, map.getOrCompute(key));
97    assertEquals(1, computingFunction.getCount());
98  }
99
100  public void testComputeNull() {
101    Function<Object, Object> computingFunction = new ConstantLoader<Object, Object>(null);
102    ComputingMapAdapter<Object, Object> map = makeAdaptedMap(createMapMaker(), computingFunction);
103    try {
104      map.get(new Object());
105      fail();
106    } catch (NullPointerException expected) {}
107  }
108
109  public void testRecordReadOnCompute() throws ExecutionException {
110    CountingFunction computingFunction = new CountingFunction();
111    for (MapMaker maker : allEvictingMakers()) {
112      ComputingConcurrentHashMap<Object, Object> map =
113          makeComputingMap(maker.concurrencyLevel(1), computingFunction);
114      Segment<Object, Object> segment = map.segments[0];
115      List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
116      List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
117      for (int i = 0; i < SMALL_MAX_SIZE; i++) {
118        Object key = new Object();
119        int hash = map.hash(key);
120
121        map.getOrCompute(key);
122        ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
123        writeOrder.add(entry);
124        readOrder.add(entry);
125      }
126
127      checkEvictionQueues(map, segment, readOrder, writeOrder);
128      checkExpirationTimes(map);
129      assertTrue(segment.recencyQueue.isEmpty());
130
131      // access some of the elements
132      Random random = new Random();
133      List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
134      Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
135      while (i.hasNext()) {
136        ReferenceEntry<Object, Object> entry = i.next();
137        if (random.nextBoolean()) {
138          map.getOrCompute(entry.getKey());
139          reads.add(entry);
140          i.remove();
141          assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
142        }
143      }
144      int undrainedIndex = reads.size() - segment.recencyQueue.size();
145      checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
146      readOrder.addAll(reads);
147
148      checkEvictionQueues(map, segment, readOrder, writeOrder);
149      checkExpirationTimes(map);
150    }
151  }
152
153  public void testComputeExistingEntry() throws ExecutionException {
154    CountingFunction computingFunction = new CountingFunction();
155    ComputingConcurrentHashMap<Object, Object> map =
156        makeComputingMap(createMapMaker(), computingFunction);
157    assertEquals(0, computingFunction.getCount());
158
159    Object key = new Object();
160    Object value = new Object();
161    map.put(key, value);
162
163    assertEquals(value, map.getOrCompute(key));
164    assertEquals(0, computingFunction.getCount());
165  }
166
167  public void testComputePartiallyCollectedKey() throws ExecutionException {
168    MapMaker maker = createMapMaker().concurrencyLevel(1);
169    CountingFunction computingFunction = new CountingFunction();
170    ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
171    Segment<Object, Object> segment = map.segments[0];
172    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
173    assertEquals(0, computingFunction.getCount());
174
175    Object key = new Object();
176    int hash = map.hash(key);
177    Object value = new Object();
178    int index = hash & (table.length() - 1);
179
180    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
181    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
182    entry.setValueReference(valueRef);
183    table.set(index, entry);
184    segment.count++;
185
186    assertSame(value, map.getOrCompute(key));
187    assertEquals(0, computingFunction.getCount());
188    assertEquals(1, segment.count);
189
190    entry.clearKey();
191    assertNotSame(value, map.getOrCompute(key));
192    assertEquals(1, computingFunction.getCount());
193    assertEquals(2, segment.count);
194  }
195
196  public void testComputePartiallyCollectedValue() throws ExecutionException {
197    MapMaker maker = createMapMaker().concurrencyLevel(1);
198    CountingFunction computingFunction = new CountingFunction();
199    ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
200    Segment<Object, Object> segment = map.segments[0];
201    AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
202    assertEquals(0, computingFunction.getCount());
203
204    Object key = new Object();
205    int hash = map.hash(key);
206    Object value = new Object();
207    int index = hash & (table.length() - 1);
208
209    DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
210    DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value, entry);
211    entry.setValueReference(valueRef);
212    table.set(index, entry);
213    segment.count++;
214
215    assertSame(value, map.getOrCompute(key));
216    assertEquals(0, computingFunction.getCount());
217    assertEquals(1, segment.count);
218
219    valueRef.clear(null);
220    assertNotSame(value, map.getOrCompute(key));
221    assertEquals(1, computingFunction.getCount());
222    assertEquals(1, segment.count);
223  }
224
225  @SuppressWarnings("deprecation") // test of deprecated method
226  public void testComputeExpiredEntry() throws ExecutionException {
227    MapMaker maker = createMapMaker().expireAfterWrite(1, TimeUnit.NANOSECONDS);
228    CountingFunction computingFunction = new CountingFunction();
229    ComputingConcurrentHashMap<Object, Object> map = makeComputingMap(maker, computingFunction);
230    assertEquals(0, computingFunction.getCount());
231
232    Object key = new Object();
233    Object one = map.getOrCompute(key);
234    assertEquals(1, computingFunction.getCount());
235
236    Object two = map.getOrCompute(key);
237    assertNotSame(one, two);
238    assertEquals(2, computingFunction.getCount());
239  }
240
241  public void testRemovalListener_replaced() {
242    // TODO(user): May be a good candidate to play with the MultithreadedTestCase
243    final CountDownLatch startSignal = new CountDownLatch(1);
244    final CountDownLatch computingSignal = new CountDownLatch(1);
245    final CountDownLatch doneSignal = new CountDownLatch(1);
246    final Object computedObject = new Object();
247
248    Function<Object, Object> computingFunction = new Function<Object, Object>() {
249      @Override
250      public Object apply(Object key) {
251        computingSignal.countDown();
252        try {
253          startSignal.await();
254        } catch (InterruptedException e) {
255          throw new RuntimeException(e);
256        }
257        return computedObject;
258      }
259    };
260
261    QueuingRemovalListener<Object, Object> listener =
262        new QueuingRemovalListener<Object, Object>();
263    MapMaker maker = (MapMaker) createMapMaker().removalListener(listener);
264    final ComputingConcurrentHashMap<Object, Object> map =
265        makeComputingMap(maker, computingFunction);
266    assertTrue(listener.isEmpty());
267
268    final Object one = new Object();
269    final Object two = new Object();
270    final Object three = new Object();
271
272    new Thread() {
273      @Override
274      public void run() {
275        try {
276          map.getOrCompute(one);
277        } catch (ExecutionException e) {
278          throw new RuntimeException(e);
279        }
280        doneSignal.countDown();
281      }
282    }.start();
283
284    try {
285      computingSignal.await();
286    } catch (InterruptedException e) {
287      throw new RuntimeException(e);
288    }
289
290    map.put(one, two);
291    startSignal.countDown();
292
293    try {
294      doneSignal.await();
295    } catch (InterruptedException e) {
296      throw new RuntimeException(e);
297    }
298
299    assertNotNull(map.putIfAbsent(one, three)); // force notifications
300    assertNotified(listener, one, computedObject, RemovalCause.REPLACED);
301    assertTrue(listener.isEmpty());
302  }
303
304  // computing functions
305
306  private static class CountingFunction implements Function<Object, Object> {
307    private final AtomicInteger count = new AtomicInteger();
308
309    @Override
310    public Object apply(Object from) {
311      count.incrementAndGet();
312      return new Object();
313    }
314
315    public int getCount() {
316      return count.get();
317    }
318  }
319
320  public void testNullParameters() throws Exception {
321    NullPointerTester tester = new NullPointerTester();
322    Function<Object, Object> computingFunction = new IdentityLoader<Object>();
323    tester.testAllPublicInstanceMethods(makeComputingMap(createMapMaker(), computingFunction));
324  }
325
326  static final class ConstantLoader<K, V> implements Function<K, V> {
327    private final V constant;
328
329    public ConstantLoader(V constant) {
330      this.constant = constant;
331    }
332
333    @Override
334    public V apply(K key) {
335      return constant;
336    }
337  }
338
339  static final class IdentityLoader<T> implements Function<T, T> {
340    @Override
341    public T apply(T key) {
342      return key;
343    }
344  }
345
346}
347