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 com.google.common.base.Function;
20 import com.google.common.primitives.Ints;
21 
22 import junit.framework.TestCase;
23 
24 import java.util.List;
25 import java.util.Random;
26 import java.util.concurrent.Callable;
27 import java.util.concurrent.ConcurrentHashMap;
28 import java.util.concurrent.ConcurrentMap;
29 import java.util.concurrent.ConcurrentSkipListMap;
30 import java.util.concurrent.ExecutionException;
31 import java.util.concurrent.ExecutorService;
32 import java.util.concurrent.Executors;
33 import java.util.concurrent.Future;
34 import java.util.concurrent.atomic.AtomicInteger;
35 
36 /**
37  * Basher test for {@link ConcurrentHashMultiset}: start a bunch of threads, have each of them
38  * do operations at random. Each thread keeps track of the per-key deltas that it's directly
39  * responsible for; after all threads have completed, we sum the per-key deltas and compare to the
40  * existing multiset values.
41  *
42  * @author mike nonemacher
43  */
44 
45 public class ConcurrentHashMultisetBasherTest extends TestCase {
46 
testAddAndRemove_ConcurrentHashMap()47   public void testAddAndRemove_ConcurrentHashMap() throws Exception {
48     testAddAndRemove(new ConcurrentHashMap<String, AtomicInteger>());
49   }
50 
testAddAndRemove_ConcurrentSkipListMap()51   public void testAddAndRemove_ConcurrentSkipListMap() throws Exception {
52     testAddAndRemove(new ConcurrentSkipListMap<String, AtomicInteger>());
53   }
54 
testAddAndRemove_MapMakerMap()55   public void testAddAndRemove_MapMakerMap() throws Exception {
56     MapMaker mapMaker = new MapMaker();
57     // force MapMaker to use its own MapMakerInternalMap
58     mapMaker.useCustomMap = true;
59     testAddAndRemove(mapMaker.<String, AtomicInteger>makeMap());
60   }
61 
testAddAndRemove(ConcurrentMap<String, AtomicInteger> map)62   private void testAddAndRemove(ConcurrentMap<String, AtomicInteger> map)
63       throws ExecutionException, InterruptedException {
64 
65     final ConcurrentHashMultiset<String> multiset = new ConcurrentHashMultiset<String>(map);
66     int nThreads = 20;
67     int tasksPerThread = 10;
68     int nTasks = nThreads * tasksPerThread;
69     ExecutorService pool = Executors.newFixedThreadPool(nThreads);
70     ImmutableList<String> keys = ImmutableList.of("a", "b", "c");
71     try {
72       List<Future<int[]>> futures = Lists.newArrayListWithExpectedSize(nTasks);
73       for (int i = 0; i < nTasks; i++) {
74         futures.add(pool.submit(new MutateTask(multiset, keys)));
75       }
76 
77       int[] deltas = new int[3];
78       for (Future<int[]> future : futures) {
79         int[] taskDeltas = future.get();
80         for (int i = 0; i < deltas.length; i++) {
81           deltas[i] += taskDeltas[i];
82         }
83       }
84 
85       List<Integer> actualCounts = Lists.transform(keys,
86           new Function<String, Integer>() {
87             @Override public Integer apply(String key) {
88               return multiset.count(key);
89             }
90           });
91       assertEquals("Counts not as expected", Ints.asList(deltas), actualCounts);
92     } finally {
93       pool.shutdownNow();
94     }
95 
96     // Since we have access to the backing map, verify that there are no zeroes in the map
97     for (AtomicInteger value : map.values()) {
98       assertTrue("map should not contain a zero", value.get() != 0);
99     }
100   }
101 
102   private static class MutateTask implements Callable<int[]> {
103     private final ConcurrentHashMultiset<String> multiset;
104     private final ImmutableList<String> keys;
105     private final Random random = new Random();
106 
MutateTask(ConcurrentHashMultiset<String> multiset, ImmutableList<String> keys)107     private MutateTask(ConcurrentHashMultiset<String> multiset, ImmutableList<String> keys) {
108       this.multiset = multiset;
109       this.keys = keys;
110     }
111 
call()112     @Override public int[] call() throws Exception {
113       int iterations = 100000;
114       int nKeys = keys.size();
115       int[] deltas = new int[nKeys];
116       Operation[] operations = Operation.values();
117       for (int i = 0; i < iterations; i++) {
118         int keyIndex = random.nextInt(nKeys);
119         String key = keys.get(keyIndex);
120         Operation op = operations[random.nextInt(operations.length)];
121         switch (op) {
122           case ADD: {
123             int delta = random.nextInt(10);
124             multiset.add(key, delta);
125             deltas[keyIndex] += delta;
126             break;
127           }
128           case SET_COUNT: {
129             int newValue = random.nextInt(3);
130             int oldValue = multiset.setCount(key, newValue);
131             deltas[keyIndex] += (newValue - oldValue);
132             break;
133           }
134           case SET_COUNT_IF: {
135             int newValue = random.nextInt(3);
136             int oldValue = multiset.count(key);
137             if (multiset.setCount(key, oldValue, newValue)) {
138               deltas[keyIndex] += (newValue - oldValue);
139             }
140             break;
141           }
142           case REMOVE: {
143             int delta = random.nextInt(6);  // [0, 5]
144             int oldValue = multiset.remove(key, delta);
145             deltas[keyIndex] -= Math.min(delta, oldValue);
146             break;
147           }
148           case REMOVE_EXACTLY: {
149             int delta = random.nextInt(5);  // [0, 4]
150             if (multiset.removeExactly(key, delta)) {
151               deltas[keyIndex] -= delta;
152             }
153             break;
154           }
155         }
156       }
157       return deltas;
158     }
159 
160     private enum Operation {
161       ADD,
162       SET_COUNT,
163       SET_COUNT_IF,
164       REMOVE,
165       REMOVE_EXACTLY,
166       ;
167     }
168   }
169 }
170