Home | History | Annotate | Download | only in concurrent 
      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.util.concurrent;
     18 
     19 import com.google.common.annotations.GwtCompatible;
     20 import com.google.common.annotations.GwtIncompatible;
     21 import com.google.common.collect.ImmutableMap;
     22 import com.google.common.collect.Sets;
     23 import com.google.common.testing.NullPointerTester;
     24 
     25 import junit.framework.TestCase;
     26 
     27 import java.util.Map;
     28 import java.util.Random;
     29 import java.util.Set;
     30 import java.util.concurrent.ExecutorService;
     31 import java.util.concurrent.Executors;
     32 import java.util.concurrent.TimeUnit;
     33 import java.util.concurrent.atomic.AtomicLong;
     34 
     35 /**
     36  * Tests for {@link AtomicLongMap}.
     37  *
     38  * @author mike nonemacher
     39  */
     40 @GwtCompatible(emulated = true)
     41 public class AtomicLongMapTest extends TestCase {
     42   private static final int ITERATIONS = 100;
     43   private static final int MAX_ADDEND = 100;
     44 
     45   private Random random = new Random(301);
     46 
     47   @GwtIncompatible("NullPointerTester")
     48   public void testNulls() {
     49     NullPointerTester tester = new NullPointerTester();
     50     tester.testAllPublicConstructors(AtomicLongMap.class);
     51     tester.testAllPublicStaticMethods(AtomicLongMap.class);
     52     AtomicLongMap<Object> map = AtomicLongMap.create();
     53     tester.testAllPublicInstanceMethods(map);
     54   }
     55 
     56   public void testCreate_map() {
     57     Map<String, Long> in = ImmutableMap.of("1", 1L, "2", 2L, "3", 3L);
     58     AtomicLongMap<String> map = AtomicLongMap.create(in);
     59     assertFalse(map.isEmpty());
     60     assertSame(3, map.size());
     61     assertTrue(map.containsKey("1"));
     62     assertTrue(map.containsKey("2"));
     63     assertTrue(map.containsKey("3"));
     64     assertEquals(1L, map.get("1"));
     65     assertEquals(2L, map.get("2"));
     66     assertEquals(3L, map.get("3"));
     67   }
     68 
     69   public void testIncrementAndGet() {
     70     AtomicLongMap<String> map = AtomicLongMap.create();
     71     String key = "key";
     72     for (int i = 0; i < ITERATIONS; i++) {
     73       long before = map.get(key);
     74       long result = map.incrementAndGet(key);
     75       long after = map.get(key);
     76       assertEquals(before + 1, after);
     77       assertEquals(after, result);
     78     }
     79     assertEquals(1, map.size());
     80     assertTrue(!map.isEmpty());
     81     assertTrue(map.containsKey(key));
     82     assertEquals(ITERATIONS, (int) map.get(key));
     83   }
     84 
     85   public void testIncrementAndGet_zero() {
     86     AtomicLongMap<String> map = AtomicLongMap.create();
     87     String key = "key";
     88     assertEquals(0L, map.get(key));
     89     assertFalse(map.containsKey(key));
     90 
     91     assertEquals(1L, map.incrementAndGet(key));
     92     assertEquals(1L, map.get(key));
     93 
     94     assertEquals(0L, map.decrementAndGet(key));
     95     assertEquals(0L, map.get(key));
     96     assertTrue(map.containsKey(key));
     97 
     98     assertEquals(1L, map.incrementAndGet(key));
     99     assertEquals(1L, map.get(key));
    100   }
    101 
    102   public void testGetAndIncrement() {
    103     AtomicLongMap<String> map = AtomicLongMap.create();
    104     String key = "key";
    105     for (int i = 0; i < ITERATIONS; i++) {
    106       long before = map.get(key);
    107       long result = map.getAndIncrement(key);
    108       long after = map.get(key);
    109       assertEquals(before + 1, after);
    110       assertEquals(before, result);
    111     }
    112     assertEquals(1, map.size());
    113     assertTrue(!map.isEmpty());
    114     assertTrue(map.containsKey(key));
    115     assertEquals(ITERATIONS, (int) map.get(key));
    116   }
    117 
    118   public void testGetAndIncrement_zero() {
    119     AtomicLongMap<String> map = AtomicLongMap.create();
    120     String key = "key";
    121     assertEquals(0L, map.get(key));
    122     assertFalse(map.containsKey(key));
    123 
    124     assertEquals(0L, map.getAndIncrement(key));
    125     assertEquals(1L, map.get(key));
    126 
    127     assertEquals(1L, map.getAndDecrement(key));
    128     assertEquals(0L, map.get(key));
    129     assertTrue(map.containsKey(key));
    130 
    131     assertEquals(0L, map.getAndIncrement(key));
    132     assertEquals(1L, map.get(key));
    133   }
    134 
    135   public void testDecrementAndGet() {
    136     AtomicLongMap<String> map = AtomicLongMap.create();
    137     String key = "key";
    138     for (int i = 0; i < ITERATIONS; i++) {
    139       long before = map.get(key);
    140       long result = map.decrementAndGet(key);
    141       long after = map.get(key);
    142       assertEquals(before - 1, after);
    143       assertEquals(after, result);
    144     }
    145     assertEquals(1, map.size());
    146     assertTrue(!map.isEmpty());
    147     assertTrue(map.containsKey(key));
    148     assertEquals(-1 * ITERATIONS, (int) map.get(key));
    149   }
    150 
    151   public void testDecrementAndGet_zero() {
    152     AtomicLongMap<String> map = AtomicLongMap.create();
    153     String key = "key";
    154     assertEquals(0L, map.get(key));
    155     assertFalse(map.containsKey(key));
    156 
    157     assertEquals(-1L, map.decrementAndGet(key));
    158     assertEquals(-1L, map.get(key));
    159 
    160     assertEquals(0L, map.incrementAndGet(key));
    161     assertEquals(0L, map.get(key));
    162     assertTrue(map.containsKey(key));
    163 
    164     assertEquals(-1L, map.decrementAndGet(key));
    165     assertEquals(-1L, map.get(key));
    166   }
    167 
    168   public void testGetAndDecrement() {
    169     AtomicLongMap<String> map = AtomicLongMap.create();
    170     String key = "key";
    171     for (int i = 0; i < ITERATIONS; i++) {
    172       long before = map.get(key);
    173       long result = map.getAndDecrement(key);
    174       long after = map.get(key);
    175       assertEquals(before - 1, after);
    176       assertEquals(before, result);
    177     }
    178     assertEquals(1, map.size());
    179     assertTrue(!map.isEmpty());
    180     assertTrue(map.containsKey(key));
    181     assertEquals(-1 * ITERATIONS, (int) map.get(key));
    182   }
    183 
    184   public void testGetAndDecrement_zero() {
    185     AtomicLongMap<String> map = AtomicLongMap.create();
    186     String key = "key";
    187     assertEquals(0L, map.get(key));
    188     assertFalse(map.containsKey(key));
    189 
    190     assertEquals(0L, map.getAndDecrement(key));
    191     assertEquals(-1L, map.get(key));
    192 
    193     assertEquals(-1L, map.getAndIncrement(key));
    194     assertEquals(0L, map.get(key));
    195     assertTrue(map.containsKey(key));
    196 
    197     assertEquals(0L, map.getAndDecrement(key));
    198     assertEquals(-1L, map.get(key));
    199   }
    200 
    201   public void testAddAndGet() {
    202     AtomicLongMap<String> map = AtomicLongMap.create();
    203     String key = "key";
    204     long addend = random.nextInt(MAX_ADDEND);
    205     for (int i = 0; i < ITERATIONS; i++) {
    206       long before = map.get(key);
    207       long result = map.addAndGet(key, addend);
    208       long after = map.get(key);
    209       assertEquals(before + addend, after);
    210       assertEquals(after, result);
    211       addend = after;
    212     }
    213     assertEquals(1, map.size());
    214     assertTrue(!map.isEmpty());
    215     assertTrue(map.containsKey(key));
    216   }
    217 
    218   public void testAddAndGet_zero() {
    219     AtomicLongMap<String> map = AtomicLongMap.create();
    220     String key = "key";
    221     long value = random.nextInt(MAX_ADDEND);
    222     assertEquals(0L, map.get(key));
    223     assertFalse(map.containsKey(key));
    224 
    225     assertEquals(value, map.addAndGet(key, value));
    226     assertEquals(value, map.get(key));
    227 
    228     assertEquals(0L, map.addAndGet(key, -1 * value));
    229     assertEquals(0L, map.get(key));
    230     assertTrue(map.containsKey(key));
    231 
    232     assertEquals(value, map.addAndGet(key, value));
    233     assertEquals(value, map.get(key));
    234   }
    235 
    236   public void testGetAndAdd() {
    237     AtomicLongMap<String> map = AtomicLongMap.create();
    238     String key = "key";
    239     long addend = random.nextInt(MAX_ADDEND);
    240     for (int i = 0; i < ITERATIONS; i++) {
    241       long before = map.get(key);
    242       long result = map.getAndAdd(key, addend);
    243       long after = map.get(key);
    244       assertEquals(before + addend, after);
    245       assertEquals(before, result);
    246       addend = after;
    247     }
    248     assertEquals(1, map.size());
    249     assertTrue(!map.isEmpty());
    250     assertTrue(map.containsKey(key));
    251   }
    252 
    253   public void testGetAndAdd_zero() {
    254     AtomicLongMap<String> map = AtomicLongMap.create();
    255     String key = "key";
    256     long value = random.nextInt(MAX_ADDEND);
    257     assertEquals(0L, map.get(key));
    258     assertFalse(map.containsKey(key));
    259 
    260     assertEquals(0L, map.getAndAdd(key, value));
    261     assertEquals(value, map.get(key));
    262 
    263     assertEquals(value, map.getAndAdd(key, -1 * value));
    264     assertEquals(0L, map.get(key));
    265     assertTrue(map.containsKey(key));
    266 
    267     assertEquals(0L, map.getAndAdd(key, value));
    268     assertEquals(value, map.get(key));
    269   }
    270 
    271   public void testPut() {
    272     AtomicLongMap<String> map = AtomicLongMap.create();
    273     String key = "key";
    274     long newValue = random.nextInt(MAX_ADDEND);
    275     for (int i = 0; i < ITERATIONS; i++) {
    276       long before = map.get(key);
    277       long result = map.put(key, newValue);
    278       long after = map.get(key);
    279       assertEquals(newValue, after);
    280       assertEquals(before, result);
    281       newValue += newValue;
    282     }
    283     assertEquals(1, map.size());
    284     assertTrue(!map.isEmpty());
    285     assertTrue(map.containsKey(key));
    286   }
    287 
    288   public void testPut_zero() {
    289     AtomicLongMap<String> map = AtomicLongMap.create();
    290     String key = "key";
    291     long value = random.nextInt(MAX_ADDEND);
    292     assertEquals(0L, map.get(key));
    293     assertFalse(map.containsKey(key));
    294 
    295     assertEquals(0L, map.put(key, value));
    296     assertEquals(value, map.get(key));
    297 
    298     assertEquals(value, map.put(key, 0L));
    299     assertEquals(0L, map.get(key));
    300     assertTrue(map.containsKey(key));
    301 
    302     assertEquals(0L, map.put(key, value));
    303     assertEquals(value, map.get(key));
    304   }
    305 
    306   public void testPutAll() {
    307     Map<String, Long> in = ImmutableMap.of("1", 1L, "2", 2L, "3", 3L);
    308     AtomicLongMap<String> map = AtomicLongMap.create();
    309     assertTrue(map.isEmpty());
    310     assertSame(0, map.size());
    311     assertFalse(map.containsKey("1"));
    312     assertFalse(map.containsKey("2"));
    313     assertFalse(map.containsKey("3"));
    314     assertEquals(0L, map.get("1"));
    315     assertEquals(0L, map.get("2"));
    316     assertEquals(0L, map.get("3"));
    317 
    318     map.putAll(in);
    319     assertFalse(map.isEmpty());
    320     assertSame(3, map.size());
    321     assertTrue(map.containsKey("1"));
    322     assertTrue(map.containsKey("2"));
    323     assertTrue(map.containsKey("3"));
    324     assertEquals(1L, map.get("1"));
    325     assertEquals(2L, map.get("2"));
    326     assertEquals(3L, map.get("3"));
    327   }
    328 
    329   public void testPutIfAbsent() {
    330     AtomicLongMap<String> map = AtomicLongMap.create();
    331     String key = "key";
    332     long newValue = random.nextInt(MAX_ADDEND);
    333     for (int i = 0; i < ITERATIONS; i++) {
    334       long before = map.get(key);
    335       long result = map.putIfAbsent(key, newValue);
    336       long after = map.get(key);
    337       assertEquals(before, result);
    338       assertEquals(before == 0 ? newValue : before, after);
    339 
    340       map.remove(key);
    341       before = map.get(key);
    342       result = map.putIfAbsent(key, newValue);
    343       after = map.get(key);
    344       assertEquals(0, before);
    345       assertEquals(before, result);
    346       assertEquals(newValue, after);
    347 
    348       map.put(key, 0L);
    349       before = map.get(key);
    350       result = map.putIfAbsent(key, newValue);
    351       after = map.get(key);
    352       assertEquals(0, before);
    353       assertEquals(before, result);
    354       assertEquals(newValue, after);
    355 
    356       newValue += newValue;
    357     }
    358     assertEquals(1, map.size());
    359     assertTrue(!map.isEmpty());
    360     assertTrue(map.containsKey(key));
    361   }
    362 
    363   public void testPutIfAbsent_zero() {
    364     AtomicLongMap<String> map = AtomicLongMap.create();
    365     String key = "key";
    366     long value = random.nextInt(MAX_ADDEND);
    367     assertEquals(0L, map.get(key));
    368     assertFalse(map.containsKey(key));
    369 
    370     assertEquals(0L, map.putIfAbsent(key, value));
    371     assertEquals(value, map.get(key));
    372 
    373     assertEquals(value, map.put(key, 0L));
    374     assertEquals(0L, map.get(key));
    375     assertTrue(map.containsKey(key));
    376 
    377     assertEquals(0L, map.putIfAbsent(key, value));
    378     assertEquals(value, map.get(key));
    379   }
    380 
    381   public void testReplace() {
    382     AtomicLongMap<String> map = AtomicLongMap.create();
    383     String key = "key";
    384     long newValue = random.nextInt(MAX_ADDEND);
    385     for (int i = 0; i < ITERATIONS; i++) {
    386       long before = map.get(key);
    387       assertFalse(map.replace(key, before + 1, newValue + 1));
    388       assertFalse(map.replace(key, before - 1, newValue - 1));
    389       assertTrue(map.replace(key, before, newValue));
    390       long after = map.get(key);
    391       assertEquals(newValue, after);
    392       newValue += newValue;
    393     }
    394     assertEquals(1, map.size());
    395     assertTrue(!map.isEmpty());
    396     assertTrue(map.containsKey(key));
    397   }
    398 
    399   public void testReplace_zero() {
    400     AtomicLongMap<String> map = AtomicLongMap.create();
    401     String key = "key";
    402     long value = random.nextInt(MAX_ADDEND);
    403     assertEquals(0L, map.get(key));
    404     assertFalse(map.containsKey(key));
    405 
    406     assertTrue(map.replace(key, 0L, value));
    407     assertEquals(value, map.get(key));
    408 
    409     assertTrue(map.replace(key, value, 0L));
    410     assertEquals(0L, map.get(key));
    411     assertTrue(map.containsKey(key));
    412 
    413     assertTrue(map.replace(key, 0L, value));
    414     assertEquals(value, map.get(key));
    415   }
    416 
    417   public void testRemove() {
    418     AtomicLongMap<String> map = AtomicLongMap.create();
    419     String key = "key";
    420     assertEquals(0, map.size());
    421     assertTrue(map.isEmpty());
    422     assertEquals(0L, map.remove(key));
    423 
    424     long newValue = random.nextInt(MAX_ADDEND);
    425     for (int i = 0; i < ITERATIONS; i++) {
    426       map.put(key, newValue);
    427       assertTrue(map.containsKey(key));
    428 
    429       long before = map.get(key);
    430       long result = map.remove(key);
    431       long after = map.get(key);
    432       assertFalse(map.containsKey(key));
    433       assertEquals(before, result);
    434       assertEquals(0L, after);
    435       newValue += newValue;
    436     }
    437     assertEquals(0, map.size());
    438     assertTrue(map.isEmpty());
    439   }
    440 
    441   public void testRemove_zero() {
    442     AtomicLongMap<String> map = AtomicLongMap.create();
    443     String key = "key";
    444     assertEquals(0L, map.get(key));
    445     assertFalse(map.containsKey(key));
    446 
    447     assertEquals(0L, map.remove(key));
    448     assertEquals(0L, map.get(key));
    449     assertFalse(map.containsKey(key));
    450 
    451     assertEquals(0L, map.put(key, 0L));
    452     assertEquals(0L, map.get(key));
    453     assertTrue(map.containsKey(key));
    454 
    455     assertEquals(0L, map.remove(key));
    456     assertEquals(0L, map.get(key));
    457     assertFalse(map.containsKey(key));
    458   }
    459 
    460   public void testRemoveValue() {
    461     AtomicLongMap<String> map = AtomicLongMap.create();
    462     String key = "key";
    463     assertEquals(0, map.size());
    464     assertTrue(map.isEmpty());
    465     assertFalse(map.remove(key, 0L));
    466 
    467     long newValue = random.nextInt(MAX_ADDEND);
    468     for (int i = 0; i < ITERATIONS; i++) {
    469       map.put(key, newValue);
    470       assertTrue(map.containsKey(key));
    471 
    472       long before = map.get(key);
    473       assertFalse(map.remove(key, newValue + 1));
    474       assertFalse(map.remove(key, newValue - 1));
    475       assertTrue(map.remove(key, newValue));
    476       long after = map.get(key);
    477       assertFalse(map.containsKey(key));
    478       assertEquals(0L, after);
    479       newValue += newValue;
    480     }
    481     assertEquals(0, map.size());
    482     assertTrue(map.isEmpty());
    483   }
    484 
    485   public void testRemoveValue_zero() {
    486     AtomicLongMap<String> map = AtomicLongMap.create();
    487     String key = "key";
    488     assertEquals(0L, map.get(key));
    489     assertFalse(map.containsKey(key));
    490 
    491     assertFalse(map.remove(key, 0L));
    492     assertEquals(0L, map.get(key));
    493     assertFalse(map.containsKey(key));
    494 
    495     assertEquals(0L, map.put(key, 0L));
    496     assertEquals(0L, map.get(key));
    497     assertTrue(map.containsKey(key));
    498 
    499     assertTrue(map.remove(key, 0L));
    500     assertEquals(0L, map.get(key));
    501     assertFalse(map.containsKey(key));
    502   }
    503 
    504   public void testRemoveZeros() {
    505     AtomicLongMap<Object> map = AtomicLongMap.create();
    506     Set<Object> nonZeroKeys = Sets.newHashSet();
    507     for (int i = 0; i < ITERATIONS; i++) {
    508       Object key = new Object();
    509       long value = i % 2;
    510       map.put(key, value);
    511       if (value != 0L) {
    512         nonZeroKeys.add(key);
    513       }
    514     }
    515     assertEquals(ITERATIONS, map.size());
    516     assertTrue(map.asMap().containsValue(0L));
    517 
    518     map.removeAllZeros();
    519     assertFalse(map.asMap().containsValue(0L));
    520     assertEquals(ITERATIONS / 2, map.size());
    521     assertEquals(nonZeroKeys, map.asMap().keySet());
    522   }
    523 
    524   public void testClear() {
    525     AtomicLongMap<Object> map = AtomicLongMap.create();
    526     for (int i = 0; i < ITERATIONS; i++) {
    527       map.put(new Object(), i);
    528     }
    529     assertEquals(ITERATIONS, map.size());
    530 
    531     map.clear();
    532     assertEquals(0, map.size());
    533     assertTrue(map.isEmpty());
    534   }
    535 
    536   public void testSum() {
    537     AtomicLongMap<Object> map = AtomicLongMap.create();
    538     long sum = 0;
    539     for (int i = 0; i < ITERATIONS; i++) {
    540       map.put(new Object(), i);
    541       sum += i;
    542     }
    543     assertEquals(ITERATIONS, map.size());
    544     assertEquals(sum, map.sum());
    545   }
    546 
    547   public void testEmpty() {
    548     AtomicLongMap<String> map = AtomicLongMap.create();
    549     assertEquals(0L, map.get("a"));
    550     assertEquals(0, map.size());
    551     assertTrue(map.isEmpty());
    552     assertFalse(map.remove("a", 1L));
    553     assertFalse(map.remove("a", 0L));
    554     assertFalse(map.replace("a", 1L, 0L));
    555   }
    556 
    557   @GwtIncompatible("threads")
    558   public void testModify_basher() throws InterruptedException {
    559     int nTasks = 3000;
    560     int nThreads = 100;
    561     final int getsPerTask = 1000;
    562     final int deltaRange = 10000;
    563     final String key = "key";
    564 
    565     final AtomicLong sum = new AtomicLong();
    566     final AtomicLongMap<String> map = AtomicLongMap.create();
    567 
    568     ExecutorService threadPool = Executors.newFixedThreadPool(nThreads);
    569     for (int i = 0; i < nTasks; i++) {
    570       threadPool.submit(new Runnable() {
    571         @Override public void run() {
    572           int threadSum = 0;
    573           for (int j = 0; j < getsPerTask; j++) {
    574             long delta = random.nextInt(deltaRange);
    575             int behavior = random.nextInt(10);
    576             switch (behavior) {
    577               case 0:
    578                 map.incrementAndGet(key);
    579                 threadSum++;
    580                 break;
    581               case 1:
    582                 map.decrementAndGet(key);
    583                 threadSum--;
    584                 break;
    585               case 2:
    586                 map.addAndGet(key, delta);
    587                 threadSum += delta;
    588                 break;
    589               case 3:
    590                 map.getAndIncrement(key);
    591                 threadSum++;
    592                 break;
    593               case 4:
    594                 map.getAndDecrement(key);
    595                 threadSum--;
    596                 break;
    597               case 5:
    598                 map.getAndAdd(key, delta);
    599                 threadSum += delta;
    600                 break;
    601               case 6:
    602                 long oldValue = map.put(key, delta);
    603                 threadSum += delta - oldValue;
    604                 break;
    605               case 7:
    606                 oldValue = map.get(key);
    607                 if (map.replace(key, oldValue, delta)) {
    608                   threadSum += delta - oldValue;
    609                 }
    610                 break;
    611               case 8:
    612                 oldValue = map.remove(key);
    613                 threadSum -= oldValue;
    614                 break;
    615               case 9:
    616                 oldValue = map.get(key);
    617                 if (map.remove(key, oldValue)) {
    618                   threadSum -= oldValue;
    619                 }
    620                 break;
    621               default:
    622                 throw new AssertionError();
    623             }
    624           }
    625           sum.addAndGet(threadSum);
    626         }
    627       });
    628     }
    629 
    630     threadPool.shutdown();
    631     assertTrue(threadPool.awaitTermination(300, TimeUnit.SECONDS));
    632 
    633     assertEquals(sum.get(), map.get(key));
    634   }
    635 }
    636