11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkState; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.Multisets.checkNonnegative; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.VisibleForTesting; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.Serialization.FieldSetter; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.math.IntMath; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.IOException; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.ObjectInputStream; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.ObjectOutputStream; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ConcurrentHashMap; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ConcurrentMap; 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.atomic.AtomicInteger; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A multiset that supports concurrent modifications and that provides atomic versions of most 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Multiset} operations (exceptions where noted). Null elements are not supported. 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Cliff L. Biffle 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author mike nonemacher 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class ConcurrentHashMultiset<E> extends AbstractMultiset<E> implements Serializable { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The ConcurrentHashMultiset's atomic operations are implemented primarily in terms of 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * AtomicInteger's atomic operations, with some help from ConcurrentMap's atomic operations on 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * creation and removal (including automatic removal of zeroes). If the modification of an 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * AtomicInteger results in zero, we compareAndSet the value to zero; if that succeeds, we remove 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the entry from the Map. If another operation sees a zero in the map, it knows that the entry is 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * about to be removed, so this operation may remove it (often by replacing it with a new 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * AtomicInteger). 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** The number of occurrences of each element. */ 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final transient ConcurrentMap<E, AtomicInteger> countMap; 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This constant allows the deserialization code to set a final field. This holder class 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // makes sure it is not initialized unless an instance is deserialized. 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class FieldSettersHolder { 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final FieldSetter<ConcurrentHashMultiset> COUNT_MAP_FIELD_SETTER = 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Serialization.getFieldSetter(ConcurrentHashMultiset.class, "countMap"); 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new, empty {@code ConcurrentHashMultiset} using the default 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * initial capacity, load factor, and concurrency settings. 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ConcurrentHashMultiset<E> create() { 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(schmoe): provide a way to use this class with other (possibly arbitrary) 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // ConcurrentMap implementors. One possibility is to extract most of this class into 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // an AbstractConcurrentMapMultiset. 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ConcurrentHashMultiset<E>(new ConcurrentHashMap<E, AtomicInteger>()); 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new {@code ConcurrentHashMultiset} containing the specified elements, using 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the default initial capacity, load factor, and concurrency settings. 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This implementation is highly efficient when {@code elements} is itself a {@link Multiset}. 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param elements the elements that the multiset should contain 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ConcurrentHashMultiset<E> create(Iterable<? extends E> elements) { 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ConcurrentHashMultiset<E> multiset = ConcurrentHashMultiset.create(); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(multiset, elements); 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset; 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a new, empty {@code ConcurrentHashMultiset} using {@code mapMaker} 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to construct the internal backing map. 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If this {@link MapMaker} is configured to use entry eviction of any kind, this eviction 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * applies to all occurrences of a given element as a single unit. However, most updates to the 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset do not count as map updates at all, since we're usually just mutating the value 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * stored in the map, so {@link MapMaker#expireAfterAccess} makes sense (evict the entry that 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * was queried or updated longest ago), but {@link MapMaker#expireAfterWrite} doesn't, because 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the eviction time is measured from when we saw the first occurrence of the object. 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset is serializable but any serialization caveats 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * given in {@code MapMaker} apply. 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Finally, soft/weak values can be used but are not very useful: the values are created 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * internally and not exposed externally, so no one else will have a strong reference to the 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values. Weak keys on the other hand can be useful in some scenarios. 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 7.0 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ConcurrentHashMultiset<E> create( 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert GenericMapMaker<? super E, ? super Number> mapMaker) { 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ConcurrentHashMultiset<E>(mapMaker.<E, AtomicInteger>makeMap()); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an instance using {@code countMap} to store elements and their counts. 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This instance will assume ownership of {@code countMap}, and other code 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * should not maintain references to the map or modify it in any way. 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param countMap backing map for storing the elements in the multiset and 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * their counts. It must be empty. 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code countMap} is not empty 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting ConcurrentHashMultiset(ConcurrentMap<E, AtomicInteger> countMap) { 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(countMap.isEmpty()); 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.countMap = countMap; 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Query Operations 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the number of occurrences of {@code element} in this multiset. 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to look for 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the nonnegative number of occurrences of the element 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int count(@Nullable Object element) { 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (existingCounter == null) ? 0 : existingCounter.get(); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Depending on the type of the underlying map, map.get may throw NullPointerException or 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ClassCastException, if the object is null or of the wrong type. We usually just want to treat 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * those cases as if the element isn't in the map, by catching the exceptions and returning null. 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private AtomicInteger safeGet(Object element) { 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countMap.get(element); 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return null; 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If the data in the multiset is modified by any other threads during this method, 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * it is undefined which (if any) of these modifications will be reflected in the result. 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long sum = 0L; 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (AtomicInteger value : countMap.values()) { 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sum += value.get(); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.saturatedCast(sum); 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Note: the superclass toArray() methods assume that size() gives a correct 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * answer, which ours does not. 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Object[] toArray() { 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return snapshot().toArray(); 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public <T> T[] toArray(T[] array) { 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return snapshot().toArray(array); 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * either of these would recurse back to us again! 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private List<E> snapshot() { 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<E> list = Lists.newArrayListWithExpectedSize(size()); 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Multiset.Entry<E> entry : entrySet()) { 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E element = entry.getElement(); 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = entry.getCount(); i > 0; i--) { 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list.add(element); 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return list; 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Modification Operations 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds a number of occurrences of the specified element to this multiset. 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to add 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param occurrences the number of occurrences to add 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the previous count of the element before the operation; possibly zero 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code occurrences} is negative, or if 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the resulting amount would exceed {@link Integer#MAX_VALUE} 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int add(E element, int occurrences) { 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (occurrences == 0) { 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count(element); 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert existingCounter = countMap.putIfAbsent(element, new AtomicInteger(occurrences)); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // existingCounter != null: fall through to operate against the existing AtomicInteger 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldValue = existingCounter.get(); 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue != 0) { 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newValue = IntMath.checkedAdd(oldValue, occurrences); 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter.compareAndSet(oldValue, newValue)) { 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // newValue can't == 0, so no need to check & remove 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldValue; 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ArithmeticException overflow) { 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new IllegalArgumentException("Overflow adding " + occurrences 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert + " occurrences to a count of " + oldValue); 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // In the case of a concurrent remove, we might observe a zero value, which means another 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // thread is about to remove (element, existingCounter) from the map. Rather than wait, 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // we can just do that work here. 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger newCounter = new AtomicInteger(occurrences); 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if ((countMap.putIfAbsent(element, newCounter) == null) 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert || countMap.replace(element, existingCounter, newCounter)) { 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // If we're still here, there was a race, so just try again. 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Removes a number of occurrences of the specified element from this multiset. If the multiset 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * contains fewer than this number of occurrences to begin with, all occurrences will be removed. 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element whose occurrences should be removed 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param occurrences the number of occurrences of the element to remove 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the count of the element before the operation; possibly zero 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code occurrences} is negative 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int remove(@Nullable Object element, int occurrences) { 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (occurrences == 0) { 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count(element); 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldValue = existingCounter.get(); 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue != 0) { 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newValue = Math.max(0, oldValue - occurrences); 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter.compareAndSet(oldValue, newValue)) { 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (newValue == 0) { 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Just CASed to 0; remove the entry to clean up the map. If the removal fails, 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // another thread has already replaced it with a new counter, which is fine. 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.remove(element, existingCounter); 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldValue; 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Removes exactly the specified number of occurrences of {@code element}, or makes no 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * change if this is not possible. 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method, in contrast to {@link #remove(Object, int)}, has no effect when the 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element count is smaller than {@code occurrences}. 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to remove 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param occurrences the number of occurrences of {@code element} to remove 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code true} if the removal was possible (including if {@code occurrences} is zero) 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean removeExactly(@Nullable Object element, int occurrences) { 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (occurrences == 0) { 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(occurrences > 0, "Invalid occurrences: %s", occurrences); 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldValue = existingCounter.get(); 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue < occurrences) { 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newValue = oldValue - occurrences; 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter.compareAndSet(oldValue, newValue)) { 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (newValue == 0) { 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Just CASed to 0; remove the entry to clean up the map. If the removal fails, 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // another thread has already replaced it with a new counter, which is fine. 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.remove(element, existingCounter); 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds or removes occurrences of {@code element} such that the {@link #count} of the 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element becomes {@code count}. 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the count of {@code element} in the multiset before this call 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code count} is negative 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int setCount(E element, int count) { 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(count, "count"); 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count == 0) { 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert existingCounter = countMap.putIfAbsent(element, new AtomicInteger(count)); 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // existingCounter != null: fall through 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldValue = existingCounter.get(); 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue == 0) { 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count == 0) { 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger newCounter = new AtomicInteger(count); 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if ((countMap.putIfAbsent(element, newCounter) == null) 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert || countMap.replace(element, existingCounter, newCounter)) { 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter.compareAndSet(oldValue, count)) { 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count == 0) { 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Just CASed to 0; remove the entry to clean up the map. If the removal fails, 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // another thread has already replaced it with a new counter, which is fine. 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.remove(element, existingCounter); 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldValue; 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Sets the number of occurrences of {@code element} to {@code newCount}, but only if 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the count is currently {@code expectedOldCount}. If {@code element} does not appear 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in the multiset exactly {@code expectedOldCount} times, no changes will be made. 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code true} if the change was successful. This usually indicates 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that the multiset has been modified, but not always: in the case that 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code expectedOldCount == newCount}, the method will return {@code true} if 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the condition was met. 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code expectedOldCount} or {@code newCount} is negative 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean setCount(E element, int expectedOldCount, int newCount) { 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(expectedOldCount, "oldCount"); 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(newCount, "newCount"); 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger existingCounter = safeGet(element); 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter == null) { 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (expectedOldCount != 0) { 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (newCount == 0) { 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if our write lost the race, it must have lost to a nonzero value, so we can stop 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countMap.putIfAbsent(element, new AtomicInteger(newCount)) == null; 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldValue = existingCounter.get(); 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue == expectedOldCount) { 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (oldValue == 0) { 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (newCount == 0) { 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Just observed a 0; try to remove the entry to clean up the map 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.remove(element, existingCounter); 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger newCounter = new AtomicInteger(newCount); 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (countMap.putIfAbsent(element, newCounter) == null) 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert || countMap.replace(element, existingCounter, newCounter); 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (existingCounter.compareAndSet(oldValue, newCount)) { 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (newCount == 0) { 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Just CASed to 0; remove the entry to clean up the map. If the removal fails, 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // another thread has already replaced it with a new counter, which is fine. 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.remove(element, existingCounter); 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Views 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Set<E> createElementSet() { 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Set<E> delegate = countMap.keySet(); 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ForwardingSet<E>() { 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected Set<E> delegate() { 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return delegate; 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean remove(Object object) { 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return delegate.remove(object); 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient EntrySet entrySet; 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Set<Multiset.Entry<E>> entrySet() { 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert EntrySet result = entrySet; 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (result == null) { 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entrySet = result = new EntrySet(); 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override int distinctElements() { 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countMap.size(); 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean isEmpty() { 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return countMap.isEmpty(); 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Iterator<Entry<E>> entryIterator() { 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // AbstractIterator makes this fairly clean, but it doesn't support remove(). To support 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // remove(), we create an AbstractIterator, and then use ForwardingIterator to delegate to it. 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Entry<E>> readOnlyIterator = 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new AbstractIterator<Entry<E>>() { 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Iterator<Map.Entry<E, AtomicInteger>> mapEntries = countMap.entrySet().iterator(); 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected Entry<E> computeNext() { 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!mapEntries.hasNext()) { 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return endOfData(); 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, AtomicInteger> mapEntry = mapEntries.next(); 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = mapEntry.getValue().get(); 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count != 0) { 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Multisets.immutableEntry(mapEntry.getKey(), count); 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ForwardingIterator<Entry<E>>() { 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Entry<E> last; 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected Iterator<Entry<E>> delegate() { 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return readOnlyIterator; 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Entry<E> next() { 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert last = super.next(); 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return last; 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public void remove() { 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkState(last != null); 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ConcurrentHashMultiset.this.setCount(last.getElement(), 0); 5171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert last = null; 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public void clear() { 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert countMap.clear(); 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private class EntrySet extends AbstractMultiset<E>.EntrySet { 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override ConcurrentHashMultiset<E> multiset() { 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ConcurrentHashMultiset.this; 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Note: the superclass toArray() methods assume that size() gives a correct 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * answer, which ours does not. 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Object[] toArray() { 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return snapshot().toArray(); 5381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public <T> T[] toArray(T[] array) { 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return snapshot().toArray(array); 5421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private List<Multiset.Entry<E>> snapshot() { 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size()); 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Not Iterables.addAll(list, this), because that'll forward right back here. 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterators.addAll(list, iterator()); 5481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return list; 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean remove(Object object) { 5521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object instanceof Multiset.Entry) { 5531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset.Entry<?> entry = (Multiset.Entry<?>) object; 5541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object element = entry.getElement(); 5551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int entryCount = entry.getCount(); 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (entryCount != 0) { 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Safe as long as we never add a new entry, which we won't. 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset<Object> multiset = (Multiset) multiset(); 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset.setCount(element, entryCount, 0); 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 5641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @serialData the ConcurrentMap of elements and their counts. 5691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void writeObject(ObjectOutputStream stream) throws IOException { 5711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.defaultWriteObject(); 5721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.writeObject(countMap); 5731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 5761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert stream.defaultReadObject(); 5771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // reading data stored by writeObject 5781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ConcurrentMap<E, Integer> deserializedCountMap = 5791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert (ConcurrentMap<E, Integer>) stream.readObject(); 5801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FieldSettersHolder.COUNT_MAP_FIELD_SETTER.set(this, deserializedCountMap); 5811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 1; 5841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 585