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