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
17package com.google.common.collect;
18
19import com.google.common.base.Function;
20import com.google.common.primitives.Ints;
21
22import junit.framework.TestCase;
23
24import java.util.List;
25import java.util.Random;
26import java.util.concurrent.Callable;
27import java.util.concurrent.ConcurrentHashMap;
28import java.util.concurrent.ConcurrentMap;
29import java.util.concurrent.ConcurrentSkipListMap;
30import java.util.concurrent.ExecutionException;
31import java.util.concurrent.ExecutorService;
32import java.util.concurrent.Executors;
33import java.util.concurrent.Future;
34import 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
45public 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