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