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 47 public void testAddAndRemove_ConcurrentHashMap() throws Exception { 48 testAddAndRemove(new ConcurrentHashMap<String, AtomicInteger>()); 49 } 50 51 public void testAddAndRemove_ConcurrentSkipListMap() throws Exception { 52 testAddAndRemove(new ConcurrentSkipListMap<String, AtomicInteger>()); 53 } 54 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 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 107 private MutateTask(ConcurrentHashMultiset<String> multiset, ImmutableList<String> keys) { 108 this.multiset = multiset; 109 this.keys = keys; 110 } 111 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
