001 /*
002 * Copyright (C) 2007 Google Inc.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.collect.Multisets.checkNonnegative;
021
022 import com.google.common.annotations.VisibleForTesting;
023 import com.google.common.collect.Serialization.FieldSetter;
024 import com.google.common.primitives.Ints;
025
026 import java.io.IOException;
027 import java.io.ObjectInputStream;
028 import java.io.ObjectOutputStream;
029 import java.io.Serializable;
030 import java.util.AbstractSet;
031 import java.util.Iterator;
032 import java.util.List;
033 import java.util.Map;
034 import java.util.Set;
035 import java.util.concurrent.ConcurrentHashMap;
036 import java.util.concurrent.ConcurrentMap;
037
038 import javax.annotation.Nullable;
039
040 /**
041 * A multiset that supports concurrent modifications and that provides atomic
042 * versions of most {@code Multiset} operations (exceptions where noted). Null
043 * elements are not supported.
044 *
045 * @author Cliff L. Biffle
046 * @since 2 (imported from Google Collections Library)
047 */
048 public final class ConcurrentHashMultiset<E> extends AbstractMultiset<E>
049 implements Serializable {
050 /*
051 * The ConcurrentHashMultiset's atomic operations are implemented in terms of
052 * ConcurrentMap's atomic operations. Many of them, such as add(E, int), are
053 * read-modify-write sequences, and so are implemented as loops that wrap
054 * ConcurrentMap's compare-and-set operations (like putIfAbsent).
055 */
056
057 /** The number of occurrences of each element. */
058 private final transient ConcurrentMap<E, Integer> countMap;
059
060 // This constant allows the deserialization code to set a final field. This
061 // holder class makes sure it is not initialized unless an instance is
062 // deserialized.
063 private static class FieldSettersHolder {
064 @SuppressWarnings("unchecked")
065 // eclipse doesn't like the raw type here, but it's harmless
066 static final FieldSetter<ConcurrentHashMultiset> COUNT_MAP_FIELD_SETTER
067 = Serialization.getFieldSetter(
068 ConcurrentHashMultiset.class, "countMap");
069 }
070
071 /**
072 * Creates a new, empty {@code ConcurrentHashMultiset} using the default
073 * initial capacity, load factor, and concurrency settings.
074 */
075 public static <E> ConcurrentHashMultiset<E> create() {
076 return new ConcurrentHashMultiset<E>(new ConcurrentHashMap<E, Integer>());
077 }
078
079 /**
080 * Creates a new {@code ConcurrentHashMultiset} containing the specified
081 * elements, using the default initial capacity, load factor, and concurrency
082 * settings.
083 *
084 * @param elements the elements that the multiset should contain
085 */
086 public static <E> ConcurrentHashMultiset<E> create(
087 Iterable<? extends E> elements) {
088 ConcurrentHashMultiset<E> multiset = ConcurrentHashMultiset.create();
089 Iterables.addAll(multiset, elements);
090 return multiset;
091 }
092
093 /**
094 * Creates an instance using {@code countMap} to store elements and their
095 * counts.
096 *
097 * <p>This instance will assume ownership of {@code countMap}, and other code
098 * should not maintain references to the map or modify it in any way.
099 *
100 * @param countMap backing map for storing the elements in the multiset and
101 * their counts. It must be empty.
102 * @throws IllegalArgumentException if {@code countMap} is not empty
103 */
104 @VisibleForTesting ConcurrentHashMultiset(
105 ConcurrentMap<E, Integer> countMap) {
106 checkArgument(countMap.isEmpty());
107 this.countMap = countMap;
108 }
109
110 // Query Operations
111
112 /**
113 * Returns the number of occurrences of {@code element} in this multiset.
114 *
115 * @param element the element to look for
116 * @return the nonnegative number of occurrences of the element
117 */
118 @Override public int count(@Nullable Object element) {
119 try {
120 return unbox(countMap.get(element));
121 } catch (NullPointerException e) {
122 return 0;
123 } catch (ClassCastException e) {
124 return 0;
125 }
126 }
127
128 /**
129 * {@inheritDoc}
130 *
131 * <p>If the data in the multiset is modified by any other threads during this
132 * method, it is undefined which (if any) of these modifications will be
133 * reflected in the result.
134 */
135 @Override public int size() {
136 long sum = 0L;
137 for (Integer value : countMap.values()) {
138 sum += value;
139 }
140 return Ints.saturatedCast(sum);
141 }
142
143 /*
144 * Note: the superclass toArray() methods assume that size() gives a correct
145 * answer, which ours does not.
146 */
147
148 @Override public Object[] toArray() {
149 return snapshot().toArray();
150 }
151
152 @Override public <T> T[] toArray(T[] array) {
153 return snapshot().toArray(array);
154 }
155
156 /*
157 * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
158 * either of these would recurse back to us again!
159 */
160 private List<E> snapshot() {
161 List<E> list = Lists.newArrayListWithExpectedSize(size());
162 for (Multiset.Entry<E> entry : entrySet()) {
163 E element = entry.getElement();
164 for (int i = entry.getCount(); i > 0; i--) {
165 list.add(element);
166 }
167 }
168 return list;
169 }
170
171 // Modification Operations
172
173 /**
174 * Adds a number of occurrences of the specified element to this multiset.
175 *
176 * @param element the element to add
177 * @param occurrences the number of occurrences to add
178 * @return the previous count of the element before the operation; possibly
179 * zero
180 * @throws IllegalArgumentException if {@code occurrences} is negative, or if
181 * the resulting amount would exceed {@link Integer#MAX_VALUE}
182 */
183 @Override public int add(E element, int occurrences) {
184 if (occurrences == 0) {
185 return count(element);
186 }
187 checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);
188
189 while (true) {
190 int current = count(element);
191 if (current == 0) {
192 if (countMap.putIfAbsent(element, occurrences) == null) {
193 return 0;
194 }
195 } else {
196 checkArgument(occurrences <= Integer.MAX_VALUE - current,
197 "Overflow adding %s occurrences to a count of %s",
198 occurrences, current);
199 int next = current + occurrences;
200 if (countMap.replace(element, current, next)) {
201 return current;
202 }
203 }
204 // If we're still here, there was a race, so just try again.
205 }
206 }
207
208 /**
209 * Removes a number of occurrences of the specified element from this
210 * multiset. If the multiset contains fewer than this number of occurrences to
211 * begin with, all occurrences will be removed.
212 *
213 * @param element the element whose occurrences should be removed
214 * @param occurrences the number of occurrences of the element to remove
215 * @return the count of the element before the operation; possibly zero
216 * @throws IllegalArgumentException if {@code occurrences} is negative
217 */
218 @Override public int remove(@Nullable Object element, int occurrences) {
219 if (occurrences == 0) {
220 return count(element);
221 }
222 checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);
223
224 while (true) {
225 int current = count(element);
226 if (current == 0) {
227 return 0;
228 }
229 if (occurrences >= current) {
230 if (countMap.remove(element, current)) {
231 return current;
232 }
233 } else {
234 // We know it's an "E" because it already exists in the map.
235 @SuppressWarnings("unchecked")
236 E casted = (E) element;
237
238 if (countMap.replace(casted, current, current - occurrences)) {
239 return current;
240 }
241 }
242 // If we're still here, there was a race, so just try again.
243 }
244 }
245
246 /**
247 * Removes <b>all</b> occurrences of the specified element from this multiset.
248 * This method complements {@link Multiset#remove(Object)}, which removes only
249 * one occurrence at a time.
250 *
251 * @param element the element whose occurrences should all be removed
252 * @return the number of occurrences successfully removed, possibly zero
253 */
254 private int removeAllOccurrences(@Nullable Object element) {
255 try {
256 return unbox(countMap.remove(element));
257 } catch (NullPointerException e) {
258 return 0;
259 } catch (ClassCastException e) {
260 return 0;
261 }
262 }
263
264 /**
265 * Removes exactly the specified number of occurrences of {@code element}, or
266 * makes no change if this is not possible.
267 *
268 * <p>This method, in contrast to {@link #remove(Object, int)}, has no effect
269 * when the element count is smaller than {@code occurrences}.
270 *
271 * @param element the element to remove
272 * @param occurrences the number of occurrences of {@code element} to remove
273 * @return {@code true} if the removal was possible (including if {@code
274 * occurrences} is zero)
275 */
276 public boolean removeExactly(@Nullable Object element, int occurrences) {
277 if (occurrences == 0) {
278 return true;
279 }
280 checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences);
281
282 while (true) {
283 int current = count(element);
284 if (occurrences > current) {
285 return false;
286 }
287 if (occurrences == current) {
288 if (countMap.remove(element, occurrences)) {
289 return true;
290 }
291 } else {
292 @SuppressWarnings("unchecked") // it's in the map, must be an "E"
293 E casted = (E) element;
294 if (countMap.replace(casted, current, current - occurrences)) {
295 return true;
296 }
297 }
298 // If we're still here, there was a race, so just try again.
299 }
300 }
301
302 /**
303 * Adds or removes occurrences of {@code element} such that the {@link #count}
304 * of the element becomes {@code count}.
305 *
306 * @return the count of {@code element} in the multiset before this call
307 * @throws IllegalArgumentException if {@code count} is negative
308 */
309 @Override public int setCount(E element, int count) {
310 checkNonnegative(count, "count");
311 return (count == 0)
312 ? removeAllOccurrences(element)
313 : unbox(countMap.put(element, count));
314 }
315
316 /**
317 * Sets the number of occurrences of {@code element} to {@code newCount}, but
318 * only if the count is currently {@code oldCount}. If {@code element} does
319 * not appear in the multiset exactly {@code oldCount} times, no changes will
320 * be made.
321 *
322 * @return {@code true} if the change was successful. This usually indicates
323 * that the multiset has been modified, but not always: in the case that
324 * {@code oldCount == newCount}, the method will return {@code true} if
325 * the condition was met.
326 * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is
327 * negative
328 */
329 @Override public boolean setCount(E element, int oldCount, int newCount) {
330 checkNonnegative(oldCount, "oldCount");
331 checkNonnegative(newCount, "newCount");
332 if (newCount == 0) {
333 if (oldCount == 0) {
334 // No change to make, but must return true if the element is not present
335 return !countMap.containsKey(element);
336 } else {
337 return countMap.remove(element, oldCount);
338 }
339 }
340 if (oldCount == 0) {
341 return countMap.putIfAbsent(element, newCount) == null;
342 }
343 return countMap.replace(element, oldCount, newCount);
344 }
345
346 // Views
347
348 @Override Set<E> createElementSet() {
349 final Set<E> delegate = countMap.keySet();
350 return new ForwardingSet<E>() {
351 @Override protected Set<E> delegate() {
352 return delegate;
353 }
354 @Override public boolean remove(Object object) {
355 try {
356 return delegate.remove(object);
357 } catch (NullPointerException e) {
358 return false;
359 } catch (ClassCastException e) {
360 return false;
361 }
362 }
363 };
364 }
365
366 private transient EntrySet entrySet;
367
368 @Override public Set<Multiset.Entry<E>> entrySet() {
369 EntrySet result = entrySet;
370 if (result == null) {
371 entrySet = result = new EntrySet();
372 }
373 return result;
374 }
375
376 private class EntrySet extends AbstractSet<Multiset.Entry<E>> {
377 @Override public int size() {
378 return countMap.size();
379 }
380
381 @Override public boolean isEmpty() {
382 return countMap.isEmpty();
383 }
384
385 @Override public boolean contains(Object object) {
386 if (object instanceof Multiset.Entry) {
387 Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
388 Object element = entry.getElement();
389 int entryCount = entry.getCount();
390 return entryCount > 0 && count(element) == entryCount;
391 }
392 return false;
393 }
394
395 @Override public Iterator<Multiset.Entry<E>> iterator() {
396 final Iterator<Map.Entry<E, Integer>> backingIterator
397 = countMap.entrySet().iterator();
398 return new Iterator<Multiset.Entry<E>>() {
399 public boolean hasNext() {
400 return backingIterator.hasNext();
401 }
402
403 public Multiset.Entry<E> next() {
404 Map.Entry<E, Integer> backingEntry = backingIterator.next();
405 return Multisets.immutableEntry(
406 backingEntry.getKey(), backingEntry.getValue());
407 }
408
409 public void remove() {
410 backingIterator.remove();
411 }
412 };
413 }
414
415 /*
416 * Note: the superclass toArray() methods assume that size() gives a correct
417 * answer, which ours does not.
418 */
419
420 @Override public Object[] toArray() {
421 return snapshot().toArray();
422 }
423
424 @Override public <T> T[] toArray(T[] array) {
425 return snapshot().toArray(array);
426 }
427
428 /*
429 * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
430 * either of these would recurse back to us again!
431 */
432 private List<Multiset.Entry<E>> snapshot() {
433 List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size());
434 for (Multiset.Entry<E> entry : this) {
435 list.add(entry);
436 }
437 return list;
438 }
439
440 @Override public boolean remove(Object object) {
441 if (object instanceof Multiset.Entry) {
442 Multiset.Entry<?> entry = (Multiset.Entry<?>) object;
443 Object element = entry.getElement();
444 int entryCount = entry.getCount();
445 return countMap.remove(element, entryCount);
446 }
447 return false;
448 }
449
450 @Override public void clear() {
451 countMap.clear();
452 }
453
454 /**
455 * The hash code is the same as countMap's, though the objects aren't equal.
456 */
457 @Override public int hashCode() {
458 return countMap.hashCode();
459 }
460 }
461
462 /**
463 * We use a special form of unboxing that treats null as zero.
464 */
465 private static int unbox(Integer i) {
466 return (i == null) ? 0 : i;
467 }
468
469 /**
470 * @serialData the number of distinct elements, the first element, its count,
471 * the second element, its count, and so on
472 */
473 private void writeObject(ObjectOutputStream stream) throws IOException {
474 stream.defaultWriteObject();
475 // creating HashMultiset to handle concurrent changes
476 Serialization.writeMultiset(HashMultiset.create(this), stream);
477 }
478
479 private void readObject(ObjectInputStream stream)
480 throws IOException, ClassNotFoundException {
481 stream.defaultReadObject();
482 FieldSettersHolder.COUNT_MAP_FIELD_SETTER.set(
483 this, new ConcurrentHashMap<Object, Object>());
484 Serialization.populateMultiset(this, stream);
485 }
486
487 private static final long serialVersionUID = 0L;
488 }