Home » openjdk-7 » java » util » concurrent » [javadoc | source]
java.util.concurrent
public class: ConcurrentSkipListMap [javadoc | source]
java.lang.Object
   java.util.AbstractMap<K, V>
      java.util.concurrent.ConcurrentSkipListMap

All Implemented Interfaces:
    Cloneable, ConcurrentNavigableMap, java$io$Serializable, Map

A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException , and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.)

Beware that, unlike in most collections, the size method is not a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires a traversal of the elements, and so may report inaccurate results if this collection is modified during traversal. Additionally, the bulk operations putAll, equals, toArray, containsValue, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements.

This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces. Like most other concurrent collections, this class does not permit the use of null keys or values because some null return values cannot be reliably distinguished from the absence of elements.

This class is a member of the Java Collections Framework.

Nested Class Summary:
static final class  ConcurrentSkipListMap.Node  Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes. The list is headed by a dummy node accessible as head.node. The value field is declared only as Object because it takes special non-V values for marker and header nodes. 
static class  ConcurrentSkipListMap.Index  Index nodes represent the levels of the skip list. Note that even though both Nodes and Indexes have forward-pointing fields, they have different types and are handled in different ways, that can't nicely be captured by placing field in a shared abstract class. 
static final class  ConcurrentSkipListMap.HeadIndex  Nodes heading each level keep track of their level. 
static final class  ConcurrentSkipListMap.ComparableUsingComparator  Represents a key with a comparator as a Comparable. Because most sorted collections seem to use natural ordering on Comparables (Strings, Integers, etc), most internal methods are geared to use them. This is generally faster than checking per-comparison whether to use comparator or comparable because it doesn't require a (Comparable) cast for each comparison. (Optimizers can only sometimes remove such redundant checks themselves.) When Comparators are used, ComparableUsingComparators are created so that they act in the same way as natural orderings. This penalizes use of Comparators vs Comparables, which seems like the right tradeoff. 
abstract class  ConcurrentSkipListMap.Iter  Base of iterator classes: 
final class  ConcurrentSkipListMap.ValueIterator   
final class  ConcurrentSkipListMap.KeyIterator   
final class  ConcurrentSkipListMap.EntryIterator   
static final class  ConcurrentSkipListMap.KeySet   
static final class  ConcurrentSkipListMap.Values   
static final class  ConcurrentSkipListMap.EntrySet   
static final class  ConcurrentSkipListMap.SubMap  Submaps returned by {@link ConcurrentSkipListMap} submap operations represent a subrange of mappings of their underlying maps. Instances of this class support all methods of their underlying maps, differing in that mappings outside their range are ignored, and attempts to add mappings outside their ranges result in {@link IllegalArgumentException}. Instances of this class are constructed only using the subMap, headMap, and tailMap methods of their underlying maps. 
Fields inherited from java.util.AbstractMap:
keySet,  values
Constructor:
 public ConcurrentSkipListMap() 
 public ConcurrentSkipListMap(Comparator<? super K> comparator) 
    Constructs a new, empty map, sorted according to the specified comparator.
    Parameters:
    comparator - the comparator that will be used to order this map. If null, the {@linkplain Comparable natural ordering} of the keys will be used.
 public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) 
    Constructs a new map containing the same mappings as the given map, sorted according to the {@linkplain Comparable natural ordering} of the keys.
    Parameters:
    m - the map whose mappings are to be placed in this map
    Throws:
    ClassCastException - if the keys in m are not Comparable , or are not mutually comparable
    NullPointerException - if the specified map or any of its keys or values are null
 public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) 
    Constructs a new map containing the same mappings and using the same ordering as the specified sorted map.
    Parameters:
    m - the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map
    Throws:
    NullPointerException - if the specified sorted map or any of its keys or values are null
Method from java.util.concurrent.ConcurrentSkipListMap Summary:
ceilingEntry,   ceilingKey,   clear,   clone,   comparator,   compare,   containsKey,   containsValue,   descendingKeySet,   descendingMap,   doRemove,   doRemoveFirstEntry,   doRemoveLastEntry,   entryIterator,   entrySet,   equals,   findFirst,   findLast,   findNear,   firstEntry,   firstKey,   floorEntry,   floorKey,   get,   getNear,   headMap,   headMap,   higherEntry,   higherKey,   inHalfOpenRange,   inOpenRange,   initialize,   isEmpty,   keyIterator,   keySet,   lastEntry,   lastKey,   lowerEntry,   lowerKey,   navigableKeySet,   pollFirstEntry,   pollLastEntry,   put,   putIfAbsent,   remove,   remove,   replace,   replace,   size,   subMap,   subMap,   tailMap,   tailMap,   toList,   valueIterator,   values
Methods from java.util.AbstractMap:
clear,   clone,   containsKey,   containsValue,   entrySet,   equals,   get,   hashCode,   isEmpty,   keySet,   put,   putAll,   remove,   size,   toString,   values
Methods from java.lang.Object:
clone,   equals,   finalize,   getClass,   hashCode,   notify,   notifyAll,   toString,   wait,   wait,   wait
Method from java.util.concurrent.ConcurrentSkipListMap Detail:
 public Entry<K, V> ceilingEntry(K key) 
    Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such entry. The returned entry does not support the Entry.setValue method.
 public K ceilingKey(K key) 
 public  void clear() 
    Removes all of the mappings from this map.
 public ConcurrentSkipListMap<K, V> clone() 
    Returns a shallow copy of this ConcurrentSkipListMap instance. (The keys and values themselves are not cloned.)
 public Comparator<? super K> comparator() 
 int compare(K k1,
    K k2) throws ClassCastException 
    Compares using comparator or natural ordering. Used when the ComparableUsingComparator approach doesn't apply.
 public boolean containsKey(Object key) 
    Returns true if this map contains a mapping for the specified key.
 public boolean containsValue(Object value) 
    Returns true if this map maps one or more keys to the specified value. This operation requires time linear in the map size. Additionally, it is possible for the map to change during execution of this method, in which case the returned result may be inaccurate.
 public NavigableSet<K> descendingKeySet() 
 public ConcurrentNavigableMap<K, V> descendingMap() 
 final V doRemove(Object okey,
    Object value) 
    Main deletion method. Locates node, nulls value, appends a deletion marker, unlinks predecessor, removes associated index nodes, and possibly reduces head index level. Index nodes are cleared out simply by calling findPredecessor. which unlinks indexes to deleted nodes found along path to key, which will include the indexes to this node. This is done unconditionally. We can't check beforehand whether there are index nodes because it might be the case that some or all indexes hadn't been inserted yet for this node during initial search for it, and we'd like to ensure lack of garbage retention, so must call to be sure.
 Entry<K, V> doRemoveFirstEntry() 
    Removes first entry; returns its snapshot.
 Entry<K, V> doRemoveLastEntry() 
    Removes last entry; returns its snapshot. Specialized variant of doRemove.
 Iterator<K, V> entryIterator() 
 public Set<K, V> entrySet() 
    Returns a Set view of the mappings contained in this map. The set's iterator returns the entries in ascending key order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.

    The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException , and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

    The Map.Entry elements returned by iterator.next() do not support the setValue operation.

 public boolean equals(Object o) 
    Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This operation may return misleading results if either map is concurrently modified during execution of this method.
 Node<K, V> findFirst() 
    Specialized variant of findNode to get first valid node.
 Node<K, V> findLast() 
    Specialized version of find to get last valid node.
 Node<K, V> findNear(K kkey,
    int rel) 
    Utility for ceiling, floor, lower, higher methods.
 public Entry<K, V> firstEntry() 
    Returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
 public K firstKey() 
 public Entry<K, V> floorEntry(K key) 
    Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method.
 public K floorKey(K key) 
 public V get(Object key) 
    Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key.

    More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that {@code key} compares equal to {@code k} according to the map's ordering, then this method returns {@code v}; otherwise it returns {@code null}. (There can be at most one such mapping.)

 SimpleImmutableEntry<K, V> getNear(K key,
    int rel) 
    Returns SimpleImmutableEntry for results of findNear.
 public ConcurrentNavigableMap<K, V> headMap(K toKey) 
 public ConcurrentNavigableMap<K, V> headMap(K toKey,
    boolean inclusive) 
 public Entry<K, V> higherEntry(K key) 
    Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method.
 public K higherKey(K key) 
 boolean inHalfOpenRange(K key,
    K least,
    K fence) 
    Returns true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence are null. Needed mainly in submap operations.
 boolean inOpenRange(K key,
    K least,
    K fence) 
    Returns true if given key greater than or equal to least and less or equal to fence. Needed mainly in submap operations.
 final  void initialize() 
    Initializes or resets state. Needed by constructors, clone, clear, readObject. and ConcurrentSkipListSet.clone. (Note that comparator must be separately initialized.)
 public boolean isEmpty() 
    Returns true if this map contains no key-value mappings.
 Iterator<K> keyIterator() 
 public NavigableSet<K> keySet() 
    Returns a NavigableSet view of the keys contained in this map. The set's iterator returns the keys in ascending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.

    The view's {@code iterator} is a "weakly consistent" iterator that will never throw ConcurrentModificationException , and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

    This method is equivalent to method {@code navigableKeySet}.

 public Entry<K, V> lastEntry() 
    Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
 public K lastKey() 
 public Entry<K, V> lowerEntry(K key) 
    Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key. The returned entry does not support the Entry.setValue method.
 public K lowerKey(K key) 
 public NavigableSet<K> navigableKeySet() 
 public Entry<K, V> pollFirstEntry() 
    Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
 public Entry<K, V> pollLastEntry() 
    Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty. The returned entry does not support the Entry.setValue method.
 public V put(K key,
    V value) 
    Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
 public V putIfAbsent(K key,
    V value) 
    {@inheritDoc}
 public V remove(Object key) 
    Removes the mapping for the specified key from this map if present.
 public boolean remove(Object key,
    Object value) 
    {@inheritDoc}
 public V replace(K key,
    V value) 
    {@inheritDoc}
 public boolean replace(K key,
    V oldValue,
    V newValue) 
    {@inheritDoc}
 public int size() 
    Returns the number of key-value mappings in this map. If this map contains more than Integer.MAX_VALUE elements, it returns Integer.MAX_VALUE.

    Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires traversing them all to count them. Additionally, it is possible for the size to change during execution of this method, in which case the returned result will be inaccurate. Thus, this method is typically not very useful in concurrent applications.

 public ConcurrentNavigableMap<K, V> subMap(K fromKey,
    K toKey) 
 public ConcurrentNavigableMap<K, V> subMap(K fromKey,
    boolean fromInclusive,
    K toKey,
    boolean toInclusive) 
 public ConcurrentNavigableMap<K, V> tailMap(K fromKey) 
 public ConcurrentNavigableMap<K, V> tailMap(K fromKey,
    boolean inclusive) 
 static final List<E> toList(Collection<E> c) 
 Iterator<V> valueIterator() 
 public Collection<V> values() 
    Returns a Collection view of the values contained in this map. The collection's iterator returns the values in ascending order of the corresponding keys. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.

    The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException , and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.