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