1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.MapMakerInternalMap.Strength.STRONG;
20 import static com.google.common.collect.MapMakerInternalMap.Strength.WEAK;
21 import static com.google.common.testing.SerializableTester.reserializeAndAssert;
22 import static java.util.Arrays.asList;
23 import static org.easymock.EasyMock.eq;
24 import static org.easymock.EasyMock.expect;
25 import static org.easymock.EasyMock.isA;
26
27 import com.google.common.base.Equivalence;
28 import com.google.common.collect.MapMaker.RemovalListener;
29 import com.google.common.collect.MapMaker.RemovalNotification;
30 import com.google.common.collect.testing.features.CollectionFeature;
31 import com.google.common.collect.testing.features.CollectionSize;
32 import com.google.common.collect.testing.google.MultisetTestSuiteBuilder;
33 import com.google.common.collect.testing.google.TestStringMultisetGenerator;
34
35 import junit.framework.Test;
36 import junit.framework.TestCase;
37 import junit.framework.TestSuite;
38
39 import org.easymock.EasyMock;
40
41 import java.util.Collections;
42 import java.util.Iterator;
43 import java.util.List;
44 import java.util.concurrent.ConcurrentMap;
45 import java.util.concurrent.ConcurrentSkipListMap;
46 import java.util.concurrent.TimeUnit;
47 import java.util.concurrent.atomic.AtomicInteger;
48
49
50
51
52
53
54
55 public class ConcurrentHashMultisetTest extends TestCase {
56
57 public static Test suite() {
58 TestSuite suite = new TestSuite();
59 suite.addTest(MultisetTestSuiteBuilder.using(concurrentHashMultisetGenerator())
60 .withFeatures(CollectionSize.ANY,
61 CollectionFeature.GENERAL_PURPOSE,
62 CollectionFeature.SERIALIZABLE,
63 CollectionFeature.ALLOWS_NULL_QUERIES)
64 .named("ConcurrentHashMultiset")
65 .createTestSuite());
66 suite.addTest(MultisetTestSuiteBuilder.using(concurrentSkipListMultisetGenerator())
67 .withFeatures(CollectionSize.ANY,
68 CollectionFeature.KNOWN_ORDER,
69 CollectionFeature.GENERAL_PURPOSE,
70 CollectionFeature.SERIALIZABLE,
71 CollectionFeature.ALLOWS_NULL_QUERIES)
72 .named("ConcurrentSkipListMultiset")
73 .createTestSuite());
74 suite.addTestSuite(ConcurrentHashMultisetTest.class);
75 return suite;
76 }
77
78 private static TestStringMultisetGenerator concurrentHashMultisetGenerator() {
79 return new TestStringMultisetGenerator() {
80 @Override protected Multiset<String> create(String[] elements) {
81 return ConcurrentHashMultiset.create(asList(elements));
82 }
83 };
84 }
85
86 private static TestStringMultisetGenerator concurrentSkipListMultisetGenerator() {
87 return new TestStringMultisetGenerator() {
88 @Override protected Multiset<String> create(String[] elements) {
89 Multiset<String> multiset = new ConcurrentHashMultiset<String>(
90 new ConcurrentSkipListMap<String, AtomicInteger>());
91 Collections.addAll(multiset, elements);
92 return multiset;
93 }
94
95 @Override
96 public List<String> order(List<String> insertionOrder) {
97 return Ordering.natural().sortedCopy(insertionOrder);
98 }
99 };
100 }
101
102 private static final String KEY = "puppies";
103
104 ConcurrentMap<String, AtomicInteger> backingMap;
105 ConcurrentHashMultiset<String> multiset;
106
107 @SuppressWarnings("unchecked")
108 @Override protected void setUp() {
109 backingMap = EasyMock.createMock(ConcurrentMap.class);
110 expect(backingMap.isEmpty()).andReturn(true);
111 replay();
112
113 multiset = new ConcurrentHashMultiset<String>(backingMap);
114 verify();
115 reset();
116 }
117
118 public void testCount_elementPresent() {
119 final int COUNT = 12;
120 expect(backingMap.get(KEY)).andReturn(new AtomicInteger(COUNT));
121 replay();
122
123 assertEquals(COUNT, multiset.count(KEY));
124 verify();
125 }
126
127 public void testCount_elementAbsent() {
128 expect(backingMap.get(KEY)).andReturn(null);
129 replay();
130
131 assertEquals(0, multiset.count(KEY));
132 verify();
133 }
134
135 public void testAdd_zero() {
136 final int INITIAL_COUNT = 32;
137
138 expect(backingMap.get(KEY)).andReturn(new AtomicInteger(INITIAL_COUNT));
139 replay();
140 assertEquals(INITIAL_COUNT, multiset.add(KEY, 0));
141 verify();
142 }
143
144 public void testAdd_firstFewWithSuccess() {
145 final int COUNT = 400;
146
147 expect(backingMap.get(KEY)).andReturn(null);
148 expect(backingMap.putIfAbsent(eq(KEY), isA(AtomicInteger.class))).andReturn(null);
149 replay();
150
151 assertEquals(0, multiset.add(KEY, COUNT));
152 verify();
153 }
154
155 public void testAdd_laterFewWithSuccess() {
156 int INITIAL_COUNT = 32;
157 int COUNT_TO_ADD = 400;
158
159 AtomicInteger initial = new AtomicInteger(INITIAL_COUNT);
160 expect(backingMap.get(KEY)).andReturn(initial);
161 replay();
162
163 assertEquals(INITIAL_COUNT, multiset.add(KEY, COUNT_TO_ADD));
164 assertEquals(INITIAL_COUNT + COUNT_TO_ADD, initial.get());
165 verify();
166 }
167
168 public void testAdd_laterFewWithOverflow() {
169 final int INITIAL_COUNT = 92384930;
170 final int COUNT_TO_ADD = Integer.MAX_VALUE - INITIAL_COUNT + 1;
171
172 expect(backingMap.get(KEY)).andReturn(new AtomicInteger(INITIAL_COUNT));
173 replay();
174
175 try {
176 multiset.add(KEY, COUNT_TO_ADD);
177 fail("Must reject arguments that would cause counter overflow.");
178 } catch (IllegalArgumentException e) {
179
180 }
181 verify();
182 }
183
184
185
186
187
188
189
190 public void testAdd_withFailures() {
191 AtomicInteger existing = new AtomicInteger(12);
192 AtomicInteger existingZero = new AtomicInteger(0);
193
194
195 expect(backingMap.get(KEY)).andReturn(null);
196
197 expect(backingMap.putIfAbsent(eq(KEY), isA(AtomicInteger.class))).andReturn(existingZero);
198
199 expect(backingMap.replace(eq(KEY), eq(existingZero), isA(AtomicInteger.class)))
200 .andReturn(false);
201
202 expect(backingMap.putIfAbsent(eq(KEY), isA(AtomicInteger.class))).andReturn(existing);
203
204
205 expect(backingMap.get(KEY)).andReturn(existingZero);
206
207 expect(backingMap.replace(eq(KEY), eq(existingZero), isA(AtomicInteger.class)))
208 .andReturn(false);
209 expect(backingMap.putIfAbsent(eq(KEY), isA(AtomicInteger.class))).andReturn(existing);
210
211
212 expect(backingMap.get(KEY)).andReturn(existing);
213
214
215 replay();
216
217 assertEquals(multiset.add(KEY, 3), 12);
218 assertEquals(15, existing.get());
219
220 verify();
221 }
222
223 public void testRemove_zeroFromSome() {
224 final int INITIAL_COUNT = 14;
225 expect(backingMap.get(KEY)).andReturn(new AtomicInteger(INITIAL_COUNT));
226 replay();
227
228 assertEquals(INITIAL_COUNT, multiset.remove(KEY, 0));
229 verify();
230 }
231
232 public void testRemove_zeroFromNone() {
233 expect(backingMap.get(KEY)).andReturn(null);
234 replay();
235
236 assertEquals(0, multiset.remove(KEY, 0));
237 verify();
238 }
239
240 public void testRemove_nonePresent() {
241 expect(backingMap.get(KEY)).andReturn(null);
242 replay();
243
244 assertEquals(0, multiset.remove(KEY, 400));
245 verify();
246 }
247
248 public void testRemove_someRemaining() {
249 int countToRemove = 30;
250 int countRemaining = 1;
251 AtomicInteger current = new AtomicInteger(countToRemove + countRemaining);
252
253 expect(backingMap.get(KEY)).andReturn(current);
254 replay();
255
256 assertEquals(countToRemove + countRemaining, multiset.remove(KEY, countToRemove));
257 assertEquals(countRemaining, current.get());
258 verify();
259 }
260
261 public void testRemove_noneRemaining() {
262 int countToRemove = 30;
263 AtomicInteger current = new AtomicInteger(countToRemove);
264
265 expect(backingMap.get(KEY)).andReturn(current);
266
267 expect(backingMap.remove(KEY, current)).andReturn(false);
268 replay();
269
270 assertEquals(countToRemove, multiset.remove(KEY, countToRemove));
271 assertEquals(0, current.get());
272 verify();
273 }
274
275 public void testRemoveExactly() {
276 ConcurrentHashMultiset<String> cms = ConcurrentHashMultiset.create();
277 cms.add("a", 2);
278 cms.add("b", 3);
279
280 try {
281 cms.removeExactly("a", -2);
282 } catch (IllegalArgumentException expected) {}
283
284 assertTrue(cms.removeExactly("a", 0));
285 assertEquals(2, cms.count("a"));
286 assertTrue(cms.removeExactly("c", 0));
287 assertEquals(0, cms.count("c"));
288
289 assertFalse(cms.removeExactly("a", 4));
290 assertEquals(2, cms.count("a"));
291 assertTrue(cms.removeExactly("a", 2));
292 assertEquals(0, cms.count("a"));
293 assertTrue(cms.removeExactly("b", 2));
294 assertEquals(1, cms.count("b"));
295 }
296
297 public void testIteratorRemove_actualMap() {
298
299 multiset = ConcurrentHashMultiset.create();
300
301 multiset.add(KEY);
302 multiset.add(KEY + "_2");
303 multiset.add(KEY);
304
305 int mutations = 0;
306 for (Iterator<String> it = multiset.iterator(); it.hasNext(); ) {
307 it.next();
308 it.remove();
309 mutations++;
310 }
311 assertTrue(multiset.isEmpty());
312 assertEquals(3, mutations);
313 }
314
315 public void testSetCount_basic() {
316 int initialCount = 20;
317 int countToSet = 40;
318 AtomicInteger current = new AtomicInteger(initialCount);
319
320 expect(backingMap.get(KEY)).andReturn(current);
321 replay();
322
323 assertEquals(initialCount, multiset.setCount(KEY, countToSet));
324 assertEquals(countToSet, current.get());
325 verify();
326 }
327
328 public void testSetCount_asRemove() {
329 int countToRemove = 40;
330 AtomicInteger current = new AtomicInteger(countToRemove);
331
332 expect(backingMap.get(KEY)).andReturn(current);
333 expect(backingMap.remove(KEY, current)).andReturn(true);
334 replay();
335
336 assertEquals(countToRemove, multiset.setCount(KEY, 0));
337 assertEquals(0, current.get());
338 verify();
339 }
340
341 public void testSetCount_0_nonePresent() {
342 expect(backingMap.get(KEY)).andReturn(null);
343 replay();
344
345 assertEquals(0, multiset.setCount(KEY, 0));
346 verify();
347 }
348
349 public void testCreate() {
350 ConcurrentHashMultiset<Integer> multiset = ConcurrentHashMultiset.create();
351 assertTrue(multiset.isEmpty());
352 reserializeAndAssert(multiset);
353 }
354
355 public void testCreateFromIterable() {
356 Iterable<Integer> iterable = asList(1, 2, 2, 3, 4);
357 ConcurrentHashMultiset<Integer> multiset
358 = ConcurrentHashMultiset.create(iterable);
359 assertEquals(2, multiset.count(2));
360 reserializeAndAssert(multiset);
361 }
362
363 public void testIdentityKeyEquality_strongKeys() {
364 testIdentityKeyEquality(STRONG);
365 }
366
367 public void testIdentityKeyEquality_weakKeys() {
368 testIdentityKeyEquality(WEAK);
369 }
370
371 private void testIdentityKeyEquality(
372 MapMakerInternalMap.Strength keyStrength) {
373
374 MapMaker mapMaker = new MapMaker()
375 .setKeyStrength(keyStrength)
376 .keyEquivalence(Equivalence.identity());
377
378 ConcurrentHashMultiset<String> multiset =
379 ConcurrentHashMultiset.create(mapMaker);
380
381 String s1 = new String("a");
382 String s2 = new String("a");
383 assertEquals(s1, s2);
384 assertTrue(s1 != s2);
385
386 multiset.add(s1);
387 assertTrue(multiset.contains(s1));
388 assertFalse(multiset.contains(s2));
389 assertEquals(1, multiset.count(s1));
390 assertEquals(0, multiset.count(s2));
391
392 multiset.add(s1);
393 multiset.add(s2, 3);
394 assertEquals(2, multiset.count(s1));
395 assertEquals(3, multiset.count(s2));
396
397 multiset.remove(s1);
398 assertEquals(1, multiset.count(s1));
399 assertEquals(3, multiset.count(s2));
400 }
401
402 public void testLogicalKeyEquality_strongKeys() {
403 testLogicalKeyEquality(STRONG);
404 }
405
406 public void testLogicalKeyEquality_weakKeys() {
407 testLogicalKeyEquality(WEAK);
408 }
409
410 private void testLogicalKeyEquality(
411 MapMakerInternalMap.Strength keyStrength) {
412
413 MapMaker mapMaker = new MapMaker()
414 .setKeyStrength(keyStrength)
415 .keyEquivalence(Equivalence.equals());
416
417 ConcurrentHashMultiset<String> multiset =
418 ConcurrentHashMultiset.create(mapMaker);
419
420 String s1 = new String("a");
421 String s2 = new String("a");
422 assertEquals(s1, s2);
423
424 multiset.add(s1);
425 assertTrue(multiset.contains(s1));
426 assertTrue(multiset.contains(s2));
427 assertEquals(1, multiset.count(s1));
428 assertEquals(1, multiset.count(s2));
429
430 multiset.add(s2, 3);
431 assertEquals(4, multiset.count(s1));
432 assertEquals(4, multiset.count(s2));
433
434 multiset.remove(s1);
435 assertEquals(3, multiset.count(s1));
436 assertEquals(3, multiset.count(s2));
437 }
438
439 public void testSerializationWithMapMaker1() {
440 MapMaker mapMaker = new MapMaker();
441 multiset = ConcurrentHashMultiset.create(mapMaker);
442 reserializeAndAssert(multiset);
443 }
444
445 public void testSerializationWithMapMaker2() {
446 MapMaker mapMaker = new MapMaker();
447 multiset = ConcurrentHashMultiset.create(mapMaker);
448 multiset.addAll(ImmutableList.of("a", "a", "b", "c", "d", "b"));
449 reserializeAndAssert(multiset);
450 }
451
452 public void testSerializationWithMapMaker3() {
453 MapMaker mapMaker = new MapMaker().expireAfterWrite(1, TimeUnit.SECONDS);
454 multiset = ConcurrentHashMultiset.create(mapMaker);
455 multiset.addAll(ImmutableList.of("a", "a", "b", "c", "d", "b"));
456 reserializeAndAssert(multiset);
457 }
458
459 public void testSerializationWithMapMaker_preservesIdentityKeyEquivalence() {
460 MapMaker mapMaker = new MapMaker()
461 .keyEquivalence(Equivalence.identity());
462
463 ConcurrentHashMultiset<String> multiset =
464 ConcurrentHashMultiset.create(mapMaker);
465 multiset = reserializeAndAssert(multiset);
466
467 String s1 = new String("a");
468 String s2 = new String("a");
469 assertEquals(s1, s2);
470 assertTrue(s1 != s2);
471
472 multiset.add(s1);
473 assertTrue(multiset.contains(s1));
474 assertFalse(multiset.contains(s2));
475 assertEquals(1, multiset.count(s1));
476 assertEquals(0, multiset.count(s2));
477 }
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533 public void testWithMapMakerEvictionListener() {
534 final List<RemovalNotification<String, Number>> notificationQueue = Lists.newArrayList();
535 RemovalListener<String, Number> removalListener =
536 new RemovalListener<String, Number>() {
537 @Override public void onRemoval(RemovalNotification<String, Number> notification) {
538 notificationQueue.add(notification);
539 }
540 };
541
542 @SuppressWarnings("deprecation")
543 MapMaker mapMaker = new MapMaker()
544 .concurrencyLevel(1)
545 .maximumSize(1);
546
547
548
549
550
551 mapMaker.removalListener(removalListener);
552
553 ConcurrentHashMultiset<String> multiset = ConcurrentHashMultiset.create(mapMaker);
554
555 multiset.add("a", 5);
556 assertTrue(multiset.contains("a"));
557 assertEquals(5, multiset.count("a"));
558
559 multiset.add("b", 3);
560
561 assertFalse(multiset.contains("a"));
562 assertTrue(multiset.contains("b"));
563 assertEquals(3, multiset.count("b"));
564 RemovalNotification<String, Number> notification = Iterables.getOnlyElement(notificationQueue);
565 assertEquals("a", notification.getKey());
566
567 assertEquals(5, notification.getValue().intValue());
568 }
569
570 private void replay() {
571 EasyMock.replay(backingMap);
572 }
573
574 private void verify() {
575 EasyMock.verify(backingMap);
576 }
577
578 private void reset() {
579 EasyMock.reset(backingMap);
580 }
581 }