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