Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2007 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
 import static com.google.common.collect.CollectPreconditions.checkRemove;
 
 
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import  javax.annotation.Nullable;

A multiset that supports concurrent modifications and that provides atomic versions of most Multiset operations (exceptions where noted). Null elements are not supported.

See the Guava User Guide article on Multiset.

Author(s):
Cliff L. Biffle
mike nonemacher
Since:
2.0 (imported from Google Collections Library)
 
 public final class ConcurrentHashMultiset<E> extends AbstractMultiset<E> implements Serializable {
 
   /*
    * The ConcurrentHashMultiset's atomic operations are implemented primarily in terms of
    * AtomicInteger's atomic operations, with some help from ConcurrentMap's atomic operations on
    * creation and removal (including automatic removal of zeroes). If the modification of an
    * AtomicInteger results in zero, we compareAndSet the value to zero; if that succeeds, we remove
    * the entry from the Map. If another operation sees a zero in the map, it knows that the entry is
    * about to be removed, so this operation may remove it (often by replacing it with a new
    * AtomicInteger).
    */

  
The number of occurrences of each element.
 
   private final transient ConcurrentMap<E, AtomicIntegercountMap;
 
   // This constant allows the deserialization code to set a final field. This holder class
   // makes sure it is not initialized unless an instance is deserialized.
   private static class FieldSettersHolder {
         Serialization.getFieldSetter(ConcurrentHashMultiset.class"countMap");
   }

  
Creates a new, empty ConcurrentHashMultiset using the default initial capacity, load factor, and concurrency settings.
 
   public static <E> ConcurrentHashMultiset<E> create() {
     // TODO(schmoe): provide a way to use this class with other (possibly arbitrary)
     // ConcurrentMap implementors. One possibility is to extract most of this class into
     // an AbstractConcurrentMapMultiset.
     return new ConcurrentHashMultiset<E>(new ConcurrentHashMap<E, AtomicInteger>());
   }

  
Creates a new ConcurrentHashMultiset containing the specified elements, using the default initial capacity, load factor, and concurrency settings.

This implementation is highly efficient when elements is itself a Multiset.

Parameters:
elements the elements that the multiset should contain
 
   public static <E> ConcurrentHashMultiset<E> create(Iterable<? extends E> elements) {
     ConcurrentHashMultiset<E> multiset = ConcurrentHashMultiset.create();
    Iterables.addAll(multisetelements);
    return multiset;
  }

  
Creates a new, empty ConcurrentHashMultiset using mapMaker to construct the internal backing map.

If this MapMaker is configured to use entry eviction of any kind, this eviction applies to all occurrences of a given element as a single unit. However, most updates to the multiset do not count as map updates at all, since we're usually just mutating the value stored in the map, so MapMaker.expireAfterAccess makes sense (evict the entry that was queried or updated longest ago), but MapMaker.expireAfterWrite doesn't, because the eviction time is measured from when we saw the first occurrence of the object.

The returned multiset is serializable but any serialization caveats given in MapMaker apply.

Finally, soft/weak values can be used but are not very useful: the values are created internally and not exposed externally, so no one else will have a strong reference to the values. Weak keys on the other hand can be useful in some scenarios.

Since:
15.0 (source compatible (accepting the since removed GenericMapMaker class) since 7.0)
  @Beta
  public static <E> ConcurrentHashMultiset<E> create(MapMaker mapMaker) {
    return new ConcurrentHashMultiset<E>(mapMaker.<E, AtomicInteger>makeMap());
  }

  
Creates an instance using countMap to store elements and their counts.

This instance will assume ownership of countMap, and other code should not maintain references to the map or modify it in any way.

Parameters:
countMap backing map for storing the elements in the multiset and their counts. It must be empty.
Throws:
IllegalArgumentException if countMap is not empty
    checkArgument(countMap.isEmpty());
    this. = countMap;
  }
  // Query Operations

  
Returns the number of occurrences of element in this multiset.

Parameters:
element the element to look for
Returns:
the nonnegative number of occurrences of the element
  @Override public int count(@Nullable Object element) {
    AtomicInteger existingCounter = Maps.safeGet(element);
    return (existingCounter == null) ? 0 : existingCounter.get();
  }

  

If the data in the multiset is modified by any other threads during this method, it is undefined which (if any) of these modifications will be reflected in the result.

  @Override public int size() {
    long sum = 0L;
    for (AtomicInteger value : .values()) {
      sum += value.get();
    }
    return Ints.saturatedCast(sum);
  }
  /*
   * Note: the superclass toArray() methods assume that size() gives a correct
   * answer, which ours does not.
   */
  @Override public Object[] toArray() {
    return snapshot().toArray();
  }
  @Override public <T> T[] toArray(T[] array) {
    return snapshot().toArray(array);
  }
  /*
   * We'd love to use 'new ArrayList(this)' or 'list.addAll(this)', but
   * either of these would recurse back to us again!
   */
  private List<E> snapshot() {
    List<E> list = Lists.newArrayListWithExpectedSize(size());
    for (Multiset.Entry<E> entry : entrySet()) {
      E element = entry.getElement();
      for (int i = entry.getCount(); i > 0; i--) {
        list.add(element);
      }
    }
    return list;
  }
  // Modification Operations

  
Adds a number of occurrences of the specified element to this multiset.

Parameters:
element the element to add
occurrences the number of occurrences to add
Returns:
the previous count of the element before the operation; possibly zero
Throws:
IllegalArgumentException if occurrences is negative, or if the resulting amount would exceed Integer.MAX_VALUE
  @Override public int add(E elementint occurrences) {
    checkNotNull(element);
    if (occurrences == 0) {
      return count(element);
    }
    checkArgument(occurrences > 0, "Invalid occurrences: %s"occurrences);
    while (true) {
      AtomicInteger existingCounter = Maps.safeGet(element);
      if (existingCounter == null) {
        existingCounter = .putIfAbsent(elementnew AtomicInteger(occurrences));
        if (existingCounter == null) {
          return 0;
        }
        // existingCounter != null: fall through to operate against the existing AtomicInteger
      }
      while (true) {
        int oldValue = existingCounter.get();
        if (oldValue != 0) {
          try {
            int newValue = IntMath.checkedAdd(oldValueoccurrences);
            if (existingCounter.compareAndSet(oldValuenewValue)) {
              // newValue can't == 0, so no need to check & remove
              return oldValue;
            }
          } catch (ArithmeticException overflow) {
            throw new IllegalArgumentException("Overflow adding " + occurrences
                + " occurrences to a count of " + oldValue);
          }
        } else {
          // In the case of a concurrent remove, we might observe a zero value, which means another
          // thread is about to remove (element, existingCounter) from the map. Rather than wait,
          // we can just do that work here.
          AtomicInteger newCounter = new AtomicInteger(occurrences);
          if ((.putIfAbsent(elementnewCounter) == null)
              || .replace(elementexistingCounternewCounter)) {
            return 0;
          }
          break;
        }
      }
      // If we're still here, there was a race, so just try again.
    }
  }

  
Removes a number of occurrences of the specified element from this multiset. If the multiset contains fewer than this number of occurrences to begin with, all occurrences will be removed.

Parameters:
element the element whose occurrences should be removed
occurrences the number of occurrences of the element to remove
Returns:
the count of the element before the operation; possibly zero
Throws:
IllegalArgumentException if occurrences is negative
  /*
   * TODO(cpovirk): remove and removeExactly currently accept null inputs only
   * if occurrences == 0. This satisfies both NullPointerTester and
   * CollectionRemoveTester.testRemove_nullAllowed, but it's not clear that it's
   * a good policy, especially because, in order for the test to pass, the
   * parameter must be misleadingly annotated as @Nullable. I suspect that
   * we'll want to remove @Nullable, add an eager checkNotNull, and loosen up
   * testRemove_nullAllowed.
   */
  @Override public int remove(@Nullable Object elementint occurrences) {
    if (occurrences == 0) {
      return count(element);
    }
    checkArgument(occurrences > 0, "Invalid occurrences: %s"occurrences);
    AtomicInteger existingCounter = Maps.safeGet(element);
    if (existingCounter == null) {
      return 0;
    }
    while (true) {
      int oldValue = existingCounter.get();
      if (oldValue != 0) {
        int newValue = Math.max(0, oldValue - occurrences);
        if (existingCounter.compareAndSet(oldValuenewValue)) {
          if (newValue == 0) {
            // Just CASed to 0; remove the entry to clean up the map. If the removal fails,
            // another thread has already replaced it with a new counter, which is fine.
            .remove(elementexistingCounter);
          }
          return oldValue;
        }
      } else {
        return 0;
      }
    }
  }

  
Removes exactly the specified number of occurrences of element, or makes no change if this is not possible.

This method, in contrast to remove(Object, int), has no effect when the element count is smaller than occurrences.

Parameters:
element the element to remove
occurrences the number of occurrences of element to remove
Returns:
true if the removal was possible (including if occurrences is zero)
  public boolean removeExactly(@Nullable Object elementint occurrences) {
    if (occurrences == 0) {
      return true;
    }
    checkArgument(occurrences > 0, "Invalid occurrences: %s"occurrences);
    AtomicInteger existingCounter = Maps.safeGet(element);
    if (existingCounter == null) {
      return false;
    }
    while (true) {
      int oldValue = existingCounter.get();
      if (oldValue < occurrences) {
        return false;
      }
      int newValue = oldValue - occurrences;
      if (existingCounter.compareAndSet(oldValuenewValue)) {
        if (newValue == 0) {
          // Just CASed to 0; remove the entry to clean up the map. If the removal fails,
          // another thread has already replaced it with a new counter, which is fine.
          .remove(elementexistingCounter);
        }
        return true;
      }
    }
  }

  
Adds or removes occurrences of element such that the count of the element becomes count.

Returns:
the count of element in the multiset before this call
Throws:
IllegalArgumentException if count is negative
  @Override public int setCount(E elementint count) {
    checkNotNull(element);
    checkNonnegative(count"count");
    while (true) {
      AtomicInteger existingCounter = Maps.safeGet(element);
      if (existingCounter == null) {
        if (count == 0) {
          return 0;
        } else {
          existingCounter = .putIfAbsent(elementnew AtomicInteger(count));
          if (existingCounter == null) {
            return 0;
          }
          // existingCounter != null: fall through
        }
      }
      while (true) {
        int oldValue = existingCounter.get();
        if (oldValue == 0) {
          if (count == 0) {
            return 0;
          } else {
            AtomicInteger newCounter = new AtomicInteger(count);
            if ((.putIfAbsent(elementnewCounter) == null)
                || .replace(elementexistingCounternewCounter)) {
              return 0;
            }
          }
          break;
        } else {
          if (existingCounter.compareAndSet(oldValuecount)) {
            if (count == 0) {
              // Just CASed to 0; remove the entry to clean up the map. If the removal fails,
              // another thread has already replaced it with a new counter, which is fine.
              .remove(elementexistingCounter);
            }
            return oldValue;
          }
        }
      }
    }
  }

  
Sets the number of occurrences of element to newCount, but only if the count is currently expectedOldCount. If element does not appear in the multiset exactly expectedOldCount times, no changes will be made.

Returns:
true if the change was successful. This usually indicates that the multiset has been modified, but not always: in the case that expectedOldCount == newCount, the method will return true if the condition was met.
Throws:
IllegalArgumentException if expectedOldCount or newCount is negative
  @Override public boolean setCount(E elementint expectedOldCountint newCount) {
    checkNotNull(element);
    checkNonnegative(expectedOldCount"oldCount");
    checkNonnegative(newCount"newCount");
    AtomicInteger existingCounter = Maps.safeGet(element);
    if (existingCounter == null) {
      if (expectedOldCount != 0) {
        return false;
      } else if (newCount == 0) {
        return true;
      } else {
        // if our write lost the race, it must have lost to a nonzero value, so we can stop
        return .putIfAbsent(elementnew AtomicInteger(newCount)) == null;
      }
    }
    int oldValue = existingCounter.get();
    if (oldValue == expectedOldCount) {
      if (oldValue == 0) {
        if (newCount == 0) {
          // Just observed a 0; try to remove the entry to clean up the map
          .remove(elementexistingCounter);
          return true;
        } else {
          AtomicInteger newCounter = new AtomicInteger(newCount);
          return (.putIfAbsent(elementnewCounter) == null)
              || .replace(elementexistingCounternewCounter);
        }
      } else {
        if (existingCounter.compareAndSet(oldValuenewCount)) {
          if (newCount == 0) {
            // Just CASed to 0; remove the entry to clean up the map. If the removal fails,
            // another thread has already replaced it with a new counter, which is fine.
            .remove(elementexistingCounter);
          }
          return true;
        }
      }
    }
    return false;
  }
  // Views
    final Set<E> delegate = .keySet();
    return new ForwardingSet<E>() {
      @Override protected Set<E> delegate() {
        return delegate;
      }
      @Override
      public boolean contains(@Nullable Object object) {
        return object != null && Collections2.safeContains(delegateobject);
      }
      @Override
      public boolean containsAll(Collection<?> collection) {
        return standardContainsAll(collection);
      }
      @Override public boolean remove(Object object) {
        return object != null && Collections2.safeRemove(delegateobject);
      }
      @Override public boolean removeAll(Collection<?> c) {
        return standardRemoveAll(c);
      }
    };
  }
  private transient EntrySet entrySet;
  @Override public Set<Multiset.Entry<E>> entrySet() {
    EntrySet result = ;
    if (result == null) {
       = result = new EntrySet();
    }
    return result;
  }
    return .size();
  }
  @Override public boolean isEmpty() {
    return .isEmpty();
  }
    // AbstractIterator makes this fairly clean, but it doesn't support remove(). To support
    // remove(), we create an AbstractIterator, and then use ForwardingIterator to delegate to it.
    final Iterator<Entry<E>> readOnlyIterator =
        new AbstractIterator<Entry<E>>() {
          private Iterator<Map.Entry<E, AtomicInteger>> mapEntries = .entrySet().iterator();
          @Override protected Entry<E> computeNext() {
            while (true) {
              if (!.hasNext()) {
                return endOfData();
              }
              Map.Entry<E, AtomicIntegermapEntry = .next();
              int count = mapEntry.getValue().get();
              if (count != 0) {
                return Multisets.immutableEntry(mapEntry.getKey(), count);
              }
            }
          }
        };
    return new ForwardingIterator<Entry<E>>() {
      private Entry<E> last;
      @Override protected Iterator<Entry<E>> delegate() {
        return readOnlyIterator;
      }
      @Override public Entry<E> next() {
         = super.next();
        return ;
      }
      @Override public void remove() {
        checkRemove( != null);
        ConcurrentHashMultiset.this.setCount(.getElement(), 0);
         = null;
      }
    };
  }
  @Override public void clear() {
    .clear();
  }
  private class EntrySet extends AbstractMultiset<E>.EntrySet {
      return ConcurrentHashMultiset.this;
    }
    /*
     * Note: the superclass toArray() methods assume that size() gives a correct
     * answer, which ours does not.
     */
    @Override public Object[] toArray() {
      return snapshot().toArray();
    }
    @Override public <T> T[] toArray(T[] array) {
      return snapshot().toArray(array);
    }
    private List<Multiset.Entry<E>> snapshot() {
      List<Multiset.Entry<E>> list = Lists.newArrayListWithExpectedSize(size());
      // Not Iterables.addAll(list, this), because that'll forward right back here.
      Iterators.addAll(listiterator());
      return list;
    }
  }

  

SerialData:
the ConcurrentMap of elements and their counts.
  private void writeObject(ObjectOutputStream streamthrows IOException {
    stream.defaultWriteObject();
    stream.writeObject();
  }
  private void readObject(ObjectInputStream streamthrows IOExceptionClassNotFoundException {
    stream.defaultReadObject();
    @SuppressWarnings("unchecked"// reading data stored by writeObject
    ConcurrentMap<E, IntegerdeserializedCountMap =
        (ConcurrentMap<E, Integer>) stream.readObject();
    ..set(thisdeserializedCountMap);
  }
  private static final long serialVersionUID = 1;
New to GrepCode? Check out our FAQ X