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.util.concurrent;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.annotations.GwtIncompatible;
21import com.google.common.collect.ImmutableMap;
22import com.google.common.collect.Sets;
23import com.google.common.testing.NullPointerTester;
24
25import junit.framework.TestCase;
26
27import java.util.Map;
28import java.util.Random;
29import java.util.Set;
30import java.util.concurrent.ExecutorService;
31import java.util.concurrent.Executors;
32import java.util.concurrent.TimeUnit;
33import java.util.concurrent.atomic.AtomicLong;
34
35/**
36 * Tests for {@link AtomicLongMap}.
37 *
38 * @author mike nonemacher
39 */
40@GwtCompatible(emulated = true)
41public 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