org.jboss.util.collection

Class ConcurrentSkipListMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

org.jboss.util.collection.ConcurrentSkipListMap<K,V>

Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.util.concurrent.ConcurrentMap<K,V>, java.util.Map<K,V>, java.util.SortedMap<K,V>, ConcurrentNavigableMap<K,V>, NavigableMap<K,V>

public class ConcurrentSkipListMap<K,V>
extends java.util.AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, java.lang.Cloneable, java.io.Serializable

A scalable ConcurrentNavigableMap implementation. This class maintains a map in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the Comparator provided at 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. Additionally, the bulk operations putAll, equals, 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.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	ConcurrentSkipListMap.ComparableUsingComparator<K> Represents a key with a comparator as a Comparable.
(package private) static class	ConcurrentSkipListMap.ConcurrentSkipListSubMap<K,V> Submaps returned by ConcurrentSkipListMap submap operations represent a subrange of mappings of their underlying maps.
(package private) class	ConcurrentSkipListMap.DescendingEntryIterator
(package private) class	ConcurrentSkipListMap.DescendingEntrySet
(package private) class	ConcurrentSkipListMap.DescendingKeyIterator
(package private) class	ConcurrentSkipListMap.DescendingKeySet
(package private) class	ConcurrentSkipListMap.DescendingSubMapEntryIterator
(package private) class	ConcurrentSkipListMap.DescendingSubMapKeyIterator
(package private) class	ConcurrentSkipListMap.EntryIter Entry iterators use the same trick as in ConcurrentHashMap and elsewhere of using the iterator itself to represent entries, thus avoiding having to create entry objects in next().
(package private) class	ConcurrentSkipListMap.EntryIterator
(package private) class	ConcurrentSkipListMap.EntrySet
(package private) static class	ConcurrentSkipListMap.HeadIndex<K,V> Nodes heading each level keep track of their level.
(package private) static class	ConcurrentSkipListMap.Index<K,V> Index nodes represent the levels of the skip list.
(package private) class	ConcurrentSkipListMap.Iter Base of ten kinds of iterator classes: ascending: {map, submap} X {key, value, entry} descending: {map, submap} X {key, entry}
(package private) class	ConcurrentSkipListMap.KeyIterator
(package private) class	ConcurrentSkipListMap.KeySet
(package private) static class	ConcurrentSkipListMap.Node<K,V> Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes.
(package private) static class	ConcurrentSkipListMap.SnapshotEntry<K,V> An immutable representation of a key-value mapping as it existed at some point in time.
(package private) class	ConcurrentSkipListMap.SubMapEntryIterator
(package private) class	ConcurrentSkipListMap.SubMapKeyIterator
(package private) class	ConcurrentSkipListMap.SubMapValueIterator
(package private) class	ConcurrentSkipListMap.ValueIterator
(package private) class	ConcurrentSkipListMap.Values

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
private static java.lang.Object	BASE_HEADER Special value used to identify base-level header
private java.util.Comparator<? super K>	comparator The Comparator used to maintain order in this Map, or null if using natural order.
private ConcurrentSkipListMap.DescendingEntrySet	descendingEntrySet Lazily initialized descending entry set
private ConcurrentSkipListMap.DescendingKeySet	descendingKeySet Lazily initialized descending key set
private ConcurrentSkipListMap.EntrySet	entrySet Lazily initialized entry set
private static int	EQ
private static int	GT
(package private) ConcurrentSkipListMap.HeadIndex<K,V>	head The topmost head index of the skiplist.
private static java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap,ConcurrentSkipListMap.HeadIndex>	headUpdater Updater for casHead
private ConcurrentSkipListMap.KeySet	keySet Lazily initialized key set
private static int	LT
private int	randomSeed Seed for simple random number generator.
private static long	serialVersionUID
private ConcurrentSkipListMap.Values	values Lazily initialized values collection

Constructor Summary

Constructors

Constructor and Description
ConcurrentSkipListMap() Constructs a new empty map, sorted according to the keys' natural order.
ConcurrentSkipListMap(java.util.Comparator<? super K> c) Constructs a new empty map, sorted according to the given comparator.
ConcurrentSkipListMap(java.util.Map<? extends K,? extends V> m) Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order.
ConcurrentSkipListMap(java.util.SortedMap<K,? extends V> m) Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering.

Method Summary

Modifier and Type	Method and Description
private void	addIndex(ConcurrentSkipListMap.Index<K,V> idx, ConcurrentSkipListMap.HeadIndex<K,V> h, int indexLevel) Add given index nodes from given level down to 1.
private void	buildFromSorted(java.util.SortedMap<K,? extends V> map) Streamlined bulk insertion to initialize from elements of given sorted map.
private boolean	casHead(ConcurrentSkipListMap.HeadIndex<K,V> cmp, ConcurrentSkipListMap.HeadIndex<K,V> val) compareAndSet head node
java.util.Map.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.
K	ceilingKey(K key) Returns least key greater than or equal to the given key, or null if there is no such key.
void	clear() Removes all mappings from this map.
private void	clearIndexToFirst() Clear out index nodes associated with deleted first entry.
java.lang.Object	clone() Returns a shallow copy of this Map instance.
private java.lang.Comparable<K>	comparable(java.lang.Object key) If using comparator, return a ComparableUsingComparator, else cast key as Comparator, which may cause ClassCastException, which is propagated back to caller.
java.util.Comparator<? super K>	comparator() Returns the comparator used to order this map, or null if this map uses its keys' natural order.
(package private) int	compare(K k1, K k2) Compare using comparator or natural ordering.
(package private) static <K,V> boolean	containsAllMappings(java.util.Map<K,V> a, java.util.Map<K,V> b) Helper for equals -- check for containment, avoiding nulls.
boolean	containsKey(java.lang.Object key) Returns true if this map contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) Returns true if this map maps one or more keys to the specified value.
java.util.Set<java.util.Map.Entry<K,V>>	descendingEntrySet() Returns a collection view of the mappings contained in this map, in descending order.
(package private) java.util.Iterator<K>	descendingKeyIterator()
java.util.Set<K>	descendingKeySet() Returns a set view of the keys contained in this map in descending order.
(package private) ConcurrentSkipListMap.DescendingSubMapEntryIterator	descendingSubMapEntryIterator(K least, K fence)
(package private) ConcurrentSkipListMap.DescendingSubMapKeyIterator	descendingSubMapKeyIterator(K least, K fence)
private V	doGet(java.lang.Object okey) Specialized variant of findNode to perform Map.get.
private V	doPut(K kkey, V value, boolean onlyIfAbsent) Main insertion method.
private V	doRemove(java.lang.Object okey, java.lang.Object value) Main deletion method.
(package private) java.lang.Object	doRemoveFirst(boolean keyOnly) Remove first entry; return either its key or a snapshot.
(package private) java.lang.Object	doRemoveLast(boolean keyOnly) Specialized version of doRemove for last entry.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns a collection view of the mappings contained in this map.
boolean	equals(java.lang.Object o) Compares the specified object with this map for equality.
(package private) ConcurrentSkipListMap.Node<K,V>	findCeiling(K key) Return ceiling, or first node if key is null
(package private) ConcurrentSkipListMap.Node<K,V>	findFirst() Specialized variant of findNode to get first valid node
(package private) ConcurrentSkipListMap.Node<K,V>	findLast() Specialized version of find to get last valid node
(package private) ConcurrentSkipListMap.Node<K,V>	findLower(K key) Return lower node, or last node if key is null
(package private) ConcurrentSkipListMap.Node<K,V>	findNear(K kkey, int rel) Utility for ceiling, floor, lower, higher methods.
private ConcurrentSkipListMap.Node<K,V>	findNode(java.lang.Comparable<K> key) Return node holding key or null if no such, clearing out any deleted nodes seen along the way.
private ConcurrentSkipListMap.Node<K,V>	findPredecessor(java.lang.Comparable<K> key) Return a base-level node with key strictly less than given key, or the base-level header if there is no such node.
private ConcurrentSkipListMap.Node<K,V>	findPredecessorOfLast() Specialized variant of findPredecessor to get predecessor of last valid node.
java.util.Map.Entry<K,V>	firstEntry() Returns a key-value mapping associated with the least key in this map, or null if the map is empty.
K	firstKey() Returns the first (lowest) key currently in this map.
java.util.Map.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 entry.
K	floorKey(K key) Returns the greatest key less than or equal to the given key, or null if there is no such key.
V	get(java.lang.Object key) Returns the value to which this map maps the specified key.
(package private) ConcurrentSkipListMap.SnapshotEntry<K,V>	getNear(K kkey, int rel) Return SnapshotEntry for results of findNear.
(package private) java.lang.Object	getNear(K kkey, int rel, K least, K fence, boolean keyOnly) Return SnapshotEntry or key for results of findNear ofter screening to ensure result is in given range.
private V	getUsingFindNode(java.lang.Comparable<K> key) Perform map.get via findNode.
ConcurrentNavigableMap<K,V>	headMap(K toKey) Returns a view of the portion of this map whose keys are strictly less than toKey.
java.util.Map.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 entry.
K	higherKey(K key) Returns the least key strictly greater than the given key, or null if there is no such key.
(package private) boolean	inHalfOpenRange(K key, K least, K fence) Return true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence oare null.
(package private) void	initialize() Initialize or reset state.
(package private) boolean	inOpenRange(K key, K least, K fence) Return true if given key greater than or equal to least and less or equal to fence.
private void	insertIndex(ConcurrentSkipListMap.Node<K,V> z, int level) Create and add index nodes for given node.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
(package private) java.util.Iterator<K>	keyIterator()
java.util.Set<K>	keySet() Returns a set view of the keys contained in this map.
java.util.Map.Entry<K,V>	lastEntry() Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
K	lastKey() Returns the last (highest) key currently in this map.
java.util.Map.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 entry.
K	lowerKey(K key) Returns the greatest key strictly less than the given key, or null if there is no such key.
java.util.Map.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.
(package private) K	pollFirstKey() Remove first entry; return key or null if empty.
java.util.Map.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.
(package private) K	pollLastKey() Remove last entry; return key or null if empty.
V	put(K key, V value) Associates the specified value with the specified key in this map.
V	putIfAbsent(K key, V value) If the specified key is not already associated with a value, associate it with the given value.
private int	randomLevel() Return a random level for inserting a new node.
private void	readObject(java.io.ObjectInputStream s) Reconstitute the Map instance from a stream.
V	remove(java.lang.Object key) Removes the mapping for this key from this Map if present.
boolean	remove(java.lang.Object key, java.lang.Object value) Remove entry for key only if currently mapped to given value.
(package private) java.lang.Object	removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) Find and remove least element of subrange.
(package private) java.lang.Object	removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) Find and remove greatest element of subrange.
(package private) boolean	removep(java.lang.Object key) Version of remove with boolean return.
V	replace(K key, V value) Replace entry for key only if currently mapped to some value.
boolean	replace(K key, V oldValue, V newValue) Replace entry for key only if currently mapped to given value.
int	size() Returns the number of elements in this map.
ConcurrentNavigableMap<K,V>	subMap(K fromKey, K toKey) Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
(package private) ConcurrentSkipListMap.SubMapEntryIterator	subMapEntryIterator(K least, K fence)
(package private) ConcurrentSkipListMap.SubMapKeyIterator	subMapKeyIterator(K least, K fence)
(package private) ConcurrentSkipListMap.SubMapValueIterator	subMapValueIterator(K least, K fence)
ConcurrentNavigableMap<K,V>	tailMap(K fromKey) Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
private void	tryReduceLevel() Possibly reduce head level if it has no nodes.
java.util.Collection<V>	values() Returns a collection view of the values contained in this map.
private void	writeObject(java.io.ObjectOutputStream s) Save the state of the Map instance to a stream.

Methods inherited from class java.util.AbstractMap

hashCode, putAll, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Methods inherited from interface java.util.Map

hashCode, putAll

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

BASE_HEADER

private static final java.lang.Object BASE_HEADER

Special value used to identify base-level header

head

transient volatile ConcurrentSkipListMap.HeadIndex<K,V> head

The topmost head index of the skiplist.

comparator

private final java.util.Comparator<? super K> comparator

The Comparator used to maintain order in this Map, or null if using natural order.

randomSeed

private transient int randomSeed

Seed for simple random number generator. Not volatile since it doesn't matter too much if different threads don't see updates.

keySet

private transient ConcurrentSkipListMap.KeySet keySet

Lazily initialized key set

entrySet

private transient ConcurrentSkipListMap.EntrySet entrySet

Lazily initialized entry set

values

private transient ConcurrentSkipListMap.Values values

Lazily initialized values collection

descendingKeySet

private transient ConcurrentSkipListMap.DescendingKeySet descendingKeySet

Lazily initialized descending key set

descendingEntrySet

private transient ConcurrentSkipListMap.DescendingEntrySet descendingEntrySet

Lazily initialized descending entry set

headUpdater

private static final java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap,ConcurrentSkipListMap.HeadIndex> headUpdater

Updater for casHead

EQ

private static final int EQ

See Also:

Constant Field Values

LT

private static final int LT

See Also:

Constant Field Values

GT

private static final int GT

See Also:

Constant Field Values

Constructor Detail

ConcurrentSkipListMap

public ConcurrentSkipListMap()

Constructs a new empty map, sorted according to the keys' natural order.

ConcurrentSkipListMap

public ConcurrentSkipListMap(java.util.Comparator<? super K> c)

Constructs a new empty map, sorted according to the given comparator.

Parameters:

c - the comparator that will be used to sort this map. A null value indicates that the keys' natural ordering should be used.

ConcurrentSkipListMap

public ConcurrentSkipListMap(java.util.Map<? extends K,? extends V> m)

Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order.

Parameters:

m - the map whose mappings are to be placed in this map.

Throws:

java.lang.ClassCastException - if the keys in m are not Comparable, or are not mutually comparable.

java.lang.NullPointerException - if the specified map is null.

ConcurrentSkipListMap

public ConcurrentSkipListMap(java.util.SortedMap<K,? extends V> m)

Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering.

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:

java.lang.NullPointerException - if the specified sorted map is null.

Method Detail

initialize

final void initialize()

Initialize or reset state. Needed by constructors, clone, clear, readObject. and ConcurrentSkipListSet.clone. (Note that comparator must be separately initialized.)

casHead

private boolean casHead(ConcurrentSkipListMap.HeadIndex<K,V> cmp,
                        ConcurrentSkipListMap.HeadIndex<K,V> val)

compareAndSet head node

comparable

private java.lang.Comparable<K> comparable(java.lang.Object key)
                                    throws java.lang.ClassCastException

If using comparator, return a ComparableUsingComparator, else cast key as Comparator, which may cause ClassCastException, which is propagated back to caller.

Throws:

java.lang.ClassCastException

compare

int compare(K k1,
            K k2)
     throws java.lang.ClassCastException

Compare using comparator or natural ordering. Used when the ComparableUsingComparator approach doesn't apply.

Throws:

java.lang.ClassCastException

inHalfOpenRange

boolean inHalfOpenRange(K key,
                        K least,
                        K fence)

Return true if given key greater than or equal to least and strictly less than fence, bypassing either test if least or fence oare null. Needed mainly in submap operations.

inOpenRange

boolean inOpenRange(K key,
                    K least,
                    K fence)

Return true if given key greater than or equal to least and less or equal to fence. Needed mainly in submap operations.

findPredecessor

private ConcurrentSkipListMap.Node<K,V> findPredecessor(java.lang.Comparable<K> key)

Return a base-level node with key strictly less than given key, or the base-level header if there is no such node. Also unlinks indexes to deleted nodes found along the way. Callers rely on this side-effect of clearing indices to deleted nodes.

Parameters:

key - the key

Returns:

a predecessor of key

findNode

private ConcurrentSkipListMap.Node<K,V> findNode(java.lang.Comparable<K> key)

Return node holding key or null if no such, clearing out any deleted nodes seen along the way. Repeatedly traverses at base-level looking for key starting at predecessor returned from findPredecessor, processing base-level deletions as encountered. Some callers rely on this side-effect of clearing deleted nodes. Restarts occur, at traversal step centered on node n, if: (1) After reading n's next field, n is no longer assumed predecessor b's current successor, which means that we don't have a consistent 3-node snapshot and so cannot unlink any subsequent deleted nodes encountered. (2) n's value field is null, indicating n is deleted, in which case we help out an ongoing structural deletion before retrying. Even though there are cases where such unlinking doesn't require restart, they aren't sorted out here because doing so would not usually outweigh cost of restarting. (3) n is a marker or n's predecessor's value field is null, indicating (among other possibilities) that findPredecessor returned a deleted node. We can't unlink the node because we don't know its predecessor, so rely on another call to findPredecessor to notice and return some earlier predecessor, which it will do. This check is only strictly needed at beginning of loop, (and the b.value check isn't strictly needed at all) but is done each iteration to help avoid contention with other threads by callers that will fail to be able to change links, and so will retry anyway. The traversal loops in doPut, doRemove, and findNear all include the same three kinds of checks. And specialized versions appear in doRemoveFirst, doRemoveLast, findFirst, and findLast. They can't easily share code because each uses the reads of fields held in locals occurring in the orders they were performed.

Parameters:

key - the key

Returns:

node holding key, or null if no such.

doGet

private V doGet(java.lang.Object okey)

Specialized variant of findNode to perform Map.get. Does a weak traversal, not bothering to fix any deleted index nodes, returning early if it happens to see key in index, and passing over any deleted base nodes, falling back to getUsingFindNode only if it would otherwise return value from an ongoing deletion. Also uses "bound" to eliminate need for some comparisons (see Pugh Cookbook). Also folds uses of null checks and node-skipping because markers have null keys.

Parameters:

okey - the key

Returns:

the value, or null if absent

getUsingFindNode

private V getUsingFindNode(java.lang.Comparable<K> key)

Perform map.get via findNode. Used as a backup if doGet encounters an in-progress deletion.

Parameters:

key - the key

Returns:

the value, or null if absent

doPut

private V doPut(K kkey,
                V value,
                boolean onlyIfAbsent)

Main insertion method. Adds element if not present, or replaces value if present and onlyIfAbsent is false.

Parameters:

kkey - the key

value - the value that must be associated with key

onlyIfAbsent - if should not insert if already present

Returns:

the old value, or null if newly inserted

randomLevel

private int randomLevel()

Return a random level for inserting a new node. Hardwired to k=1, p=0.5, max 31. This uses a cheap pseudo-random function that according to http://home1.gte.net/deleyd/random/random4.html was used in Turbo Pascal. It seems the fastest usable one here. The low bits are apparently not very random (the original used only upper 16 bits) so we traverse from highest bit down (i.e., test sign), thus hardly ever use lower bits.

insertIndex

private void insertIndex(ConcurrentSkipListMap.Node<K,V> z,
                         int level)

Create and add index nodes for given node.

Parameters:

z - the node

level - the level of the index

addIndex

private void addIndex(ConcurrentSkipListMap.Index<K,V> idx,
                      ConcurrentSkipListMap.HeadIndex<K,V> h,
                      int indexLevel)

Add given index nodes from given level down to 1.

Parameters:

idx - the topmost index node being inserted

h - the value of head to use to insert. This must be snapshotted by callers to provide correct insertion level

indexLevel - the level of the index

doRemove

private V doRemove(java.lang.Object okey,
                   java.lang.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.

Parameters:

okey - the key

value - if non-null, the value that must be associated with key

Returns:

the node, or null if not found

tryReduceLevel

private void tryReduceLevel()

Possibly reduce head level if it has no nodes. This method can (rarely) make mistakes, in which case levels can disappear even though they are about to contain index nodes. This impacts performance, not correctness. To minimize mistakes as well as to reduce hysteresis, the level is reduced by one only if the topmost three levels look empty. Also, if the removed level looks non-empty after CAS, we try to change it back quick before anyone notices our mistake! (This trick works pretty well because this method will practically never make mistakes unless current thread stalls immediately before first CAS, in which case it is very unlikely to stall again immediately afterwards, so will recover.) We put up with all this rather than just let levels grow because otherwise, even a small map that has undergone a large number of insertions and removals will have a lot of levels, slowing down access more than would an occasional unwanted reduction.

removep

boolean removep(java.lang.Object key)

Version of remove with boolean return. Needed by view classes

findFirst

ConcurrentSkipListMap.Node<K,V> findFirst()

Specialized variant of findNode to get first valid node

Returns:

first node or null if empty

doRemoveFirst

java.lang.Object doRemoveFirst(boolean keyOnly)

Remove first entry; return either its key or a snapshot.

Parameters:

keyOnly - if true return key, else return SnapshotEntry (This is a little ugly, but avoids code duplication.)

Returns:

null if empty, first key if keyOnly true, else key,value entry

clearIndexToFirst

private void clearIndexToFirst()

Clear out index nodes associated with deleted first entry. Needed by doRemoveFirst

pollFirstKey

K pollFirstKey()

Remove first entry; return key or null if empty.

findLast

ConcurrentSkipListMap.Node<K,V> findLast()

Specialized version of find to get last valid node

Returns:

last node or null if empty

doRemoveLast

java.lang.Object doRemoveLast(boolean keyOnly)

Specialized version of doRemove for last entry.

Parameters:

keyOnly - if true return key, else return SnapshotEntry

Returns:

null if empty, last key if keyOnly true, else key,value entry

findPredecessorOfLast

private ConcurrentSkipListMap.Node<K,V> findPredecessorOfLast()

Specialized variant of findPredecessor to get predecessor of last valid node. Needed by doRemoveLast. It is possible that all successors of returned node will have been deleted upon return, in which case this method can be retried.

Returns:

likely predecessor of last node.

pollLastKey

K pollLastKey()

Remove last entry; return key or null if empty.

findNear

ConcurrentSkipListMap.Node<K,V> findNear(K kkey,
                                         int rel)

Utility for ceiling, floor, lower, higher methods.

Parameters:

kkey - the key

rel - the relation -- OR'ed combination of EQ, LT, GT

Returns:

nearest node fitting relation, or null if no such

getNear

ConcurrentSkipListMap.SnapshotEntry<K,V> getNear(K kkey,
                                                 int rel)

Return SnapshotEntry for results of findNear.

Parameters:

kkey - the key

rel - the relation -- OR'ed combination of EQ, LT, GT

Returns:

Entry fitting relation, or null if no such

findCeiling

ConcurrentSkipListMap.Node<K,V> findCeiling(K key)

Return ceiling, or first node if key is null

findLower

ConcurrentSkipListMap.Node<K,V> findLower(K key)

Return lower node, or last node if key is null

getNear

java.lang.Object getNear(K kkey,
                         int rel,
                         K least,
                         K fence,
                         boolean keyOnly)

Return SnapshotEntry or key for results of findNear ofter screening to ensure result is in given range. Needed by submaps.

Parameters:

kkey - the key

rel - the relation -- OR'ed combination of EQ, LT, GT

least - minimum allowed key value

fence - key greater than maximum allowed key value

keyOnly - if true return key, else return SnapshotEntry

Returns:

Key or Entry fitting relation, or null if no such

removeFirstEntryOfSubrange

java.lang.Object removeFirstEntryOfSubrange(K least,
                                            K fence,
                                            boolean keyOnly)

Find and remove least element of subrange.

Parameters:

least - minimum allowed key value

fence - key greater than maximum allowed key value

keyOnly - if true return key, else return SnapshotEntry

Returns:

least Key or Entry, or null if no such

removeLastEntryOfSubrange

java.lang.Object removeLastEntryOfSubrange(K least,
                                           K fence,
                                           boolean keyOnly)

Find and remove greatest element of subrange.

Parameters:

least - minimum allowed key value

fence - key greater than maximum allowed key value

keyOnly - if true return key, else return SnapshotEntry

Returns:

least Key or Entry, or null if no such

clone

public java.lang.Object clone()

Returns a shallow copy of this Map instance. (The keys and values themselves are not cloned.)

Overrides:

clone in class java.util.AbstractMap<K,V>

Returns:

a shallow copy of this Map.

buildFromSorted

private void buildFromSorted(java.util.SortedMap<K,? extends V> map)

Streamlined bulk insertion to initialize from elements of given sorted map. Call only from constructor or clone method.

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException

Save the state of the Map instance to a stream.

Throws:

java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Reconstitute the Map instance from a stream.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if this map contains a mapping for the specified key.

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

Parameters:

key - key whose presence in this map is to be tested.

Returns:

true if this map contains a mapping for the specified key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key is null.

get

public V get(java.lang.Object key)

Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key.

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

Parameters:

key - key whose associated value is to be returned.

Returns:

the value to which this map maps the specified key, or null if the map contains no mapping for the key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key is null.

put

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 this key, the old value is replaced.

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

Parameters:

key - key with which the specified value is to be associated.

value - value to be associated with the specified key.

Returns:

previous value associated with specified key, or null if there was no mapping for key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key or value are null.

remove

public V remove(java.lang.Object key)

Removes the mapping for this key from this Map if present.

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

Parameters:

key - key for which mapping should be removed

Returns:

previous value associated with specified key, or null if there was no mapping for key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key is null.

containsValue

public boolean containsValue(java.lang.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.

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

Parameters:

value - value whose presence in this Map is to be tested.

Returns:

true if a mapping to value exists; false otherwise.

Throws:

java.lang.NullPointerException - if the value is null.

size

public int size()

Returns the number of elements 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.

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

Returns:

the number of elements in this map.

isEmpty

public boolean isEmpty()

Returns true if this map contains no key-value mappings.

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

Returns:

true if this map contains no key-value mappings.

clear

public void clear()

Removes all mappings from this map.

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

keySet

public java.util.Set<K> keySet()

Returns a set view of the keys contained in this map. 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 this 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.

Specified by:

keySet in interface java.util.Map<K,V>

Specified by:

keySet in interface java.util.SortedMap<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

Returns:

a set view of the keys contained in this map.

descendingKeySet

public java.util.Set<K> descendingKeySet()

Returns a set view of the keys contained in this map in descending 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 this 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.

Specified by:

descendingKeySet in interface NavigableMap<K,V>

Returns:

a set view of the keys contained in this map.

values

public java.util.Collection<V> values()

Returns a collection view of the values contained in this map. 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 this 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.

Specified by:

values in interface java.util.Map<K,V>

Specified by:

values in interface java.util.SortedMap<K,V>

Overrides:

values in class java.util.AbstractMap<K,V>

Returns:

a collection view of the values contained in this map.

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Returns a collection view of the mappings contained in this map. Each element in the returned collection is a Map.Entry. 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. The Map.Entry elements returned by iterator.next() do not support the setValue operation.

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in interface java.util.SortedMap<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

Returns:

a collection view of the mappings contained in this map.

descendingEntrySet

public java.util.Set<java.util.Map.Entry<K,V>> descendingEntrySet()

Returns a collection view of the mappings contained in this map, in descending order. Each element in the returned collection is a Map.Entry. 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. The Map.Entry elements returned by iterator.next() do not support the setValue operation.

Specified by:

descendingEntrySet in interface NavigableMap<K,V>

Returns:

a collection view of the mappings contained in this map.

equals

public boolean equals(java.lang.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 t1 and t2 represent the same mappings if t1.keySet().equals(t2.keySet()) and for every key k in t1.keySet(), (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k))) . This operation may return misleading results if either map is concurrently modified during execution of this method.

Specified by:

equals in interface java.util.Map<K,V>

Overrides:

equals in class java.util.AbstractMap<K,V>

Parameters:

o - object to be compared for equality with this map.

Returns:

true if the specified object is equal to this map.

containsAllMappings

static <K,V> boolean containsAllMappings(java.util.Map<K,V> a,
                                         java.util.Map<K,V> b)

Helper for equals -- check for containment, avoiding nulls.

putIfAbsent

public V putIfAbsent(K key,
                     V value)

If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

   if (!map.containsKey(key))
      return map.put(key, value);
   else
      return map.get(key);
 

except that the action is performed atomically.

Specified by:

putIfAbsent in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

putIfAbsent in interface java.util.Map<K,V>

Parameters:

key - key with which the specified value is to be associated.

value - value to be associated with the specified key.

Returns:

previous value associated with specified key, or null if there was no mapping for key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key or value are null.

remove

public boolean remove(java.lang.Object key,
                      java.lang.Object value)

Remove entry for key only if currently mapped to given value. Acts as

  if ((map.containsKey(key) && map.get(key).equals(value)) {
     map.remove(key);
     return true;
 } else return false;
 

except that the action is performed atomically.

Specified by:

remove in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

remove in interface java.util.Map<K,V>

Parameters:

key - key with which the specified value is associated.

value - value associated with the specified key.

Returns:

true if the value was removed, false otherwise

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key or value are null.

replace

public boolean replace(K key,
                       V oldValue,
                       V newValue)

Replace entry for key only if currently mapped to given value. Acts as

  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
     map.put(key, newValue);
     return true;
 } else return false;
 

except that the action is performed atomically.

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

Parameters:

key - key with which the specified value is associated.

oldValue - value expected to be associated with the specified key.

newValue - value to be associated with the specified key.

Returns:

true if the value was replaced

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key, oldValue or newValue are null.

replace

public V replace(K key,
                 V value)

Replace entry for key only if currently mapped to some value. Acts as

  if ((map.containsKey(key)) {
     return map.put(key, value);
 } else return null;
 

except that the action is performed atomically.

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

Parameters:

key - key with which the specified value is associated.

value - value to be associated with the specified key.

Returns:

previous value associated with specified key, or null if there was no mapping for key.

Throws:

java.lang.ClassCastException - if the key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if the key or value are null.

comparator

public java.util.Comparator<? super K> comparator()

Returns the comparator used to order this map, or null if this map uses its keys' natural order.

Specified by:

comparator in interface java.util.SortedMap<K,V>

Returns:

the comparator associated with this map, or null if it uses its keys' natural sort method.

firstKey

public K firstKey()

Returns the first (lowest) key currently in this map.

Specified by:

firstKey in interface java.util.SortedMap<K,V>

Returns:

the first (lowest) key currently in this map.

Throws:

java.util.NoSuchElementException - Map is empty.

lastKey

public K lastKey()

Returns the last (highest) key currently in this map.

Specified by:

lastKey in interface java.util.SortedMap<K,V>

Returns:

the last (highest) key currently in this map.

Throws:

java.util.NoSuchElementException - Map is empty.

subMap

public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                          K toKey)

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey and toKey are equal, the returned sorted map is empty.) The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.

Specified by:

subMap in interface java.util.SortedMap<K,V>

Specified by:

subMap in interface ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface NavigableMap<K,V>

Parameters:

fromKey - low endpoint (inclusive) of the subMap.

toKey - high endpoint (exclusive) of the subMap.

Returns:

a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

Throws:

java.lang.ClassCastException - if fromKey and toKey cannot be compared to one another using this map's comparator (or, if the map has no comparator, using natural ordering).

java.lang.IllegalArgumentException - if fromKey is greater than toKey.

java.lang.NullPointerException - if fromKey or toKey is null.

headMap

public ConcurrentNavigableMap<K,V> headMap(K toKey)

Returns a view of the portion of this map whose keys are strictly less than toKey. The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.

Specified by:

headMap in interface java.util.SortedMap<K,V>

Specified by:

headMap in interface ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface NavigableMap<K,V>

Parameters:

toKey - high endpoint (exclusive) of the headMap.

Returns:

a view of the portion of this map whose keys are strictly less than toKey.

Throws:

java.lang.ClassCastException - if toKey is not compatible with this map's comparator (or, if the map has no comparator, if toKey does not implement Comparable).

java.lang.NullPointerException - if toKey is null.

tailMap

public ConcurrentNavigableMap<K,V> tailMap(K fromKey)

Returns a view of the portion of this map whose keys are greater than or equal to fromKey. The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and vice-versa.

Specified by:

tailMap in interface java.util.SortedMap<K,V>

Specified by:

tailMap in interface ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface NavigableMap<K,V>

Parameters:

fromKey - low endpoint (inclusive) of the tailMap.

Returns:

a view of the portion of this map whose keys are greater than or equal to fromKey.

Throws:

java.lang.ClassCastException - if fromKey is not compatible with this map's comparator (or, if the map has no comparator, if fromKey does not implement Comparable).

java.lang.NullPointerException - if fromKey is null.

ceilingEntry

public java.util.Map.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.

Specified by:

ceilingEntry in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

an Entry associated with ceiling of given key, or null if there is no such Entry.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

ceilingKey

public K ceilingKey(K key)

Returns least key greater than or equal to the given key, or null if there is no such key.

Specified by:

ceilingKey in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

the ceiling key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

lowerEntry

public java.util.Map.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 entry. The returned entry does not support the Entry.setValue method.

Specified by:

lowerEntry in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

an Entry with greatest key less than the given key, or null if there is no such Entry.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

lowerKey

public K lowerKey(K key)

Returns the greatest key strictly less than the given key, or null if there is no such key.

Specified by:

lowerKey in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

the greatest key less than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

floorEntry

public java.util.Map.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 entry. The returned entry does not support the Entry.setValue method.

Specified by:

floorEntry in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

an Entry associated with floor of given key, or null if there is no such Entry.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

floorKey

public K floorKey(K key)

Returns the greatest key less than or equal to the given key, or null if there is no such key.

Specified by:

floorKey in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

the floor of given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

higherEntry

public java.util.Map.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 entry. The returned entry does not support the Entry.setValue method.

Specified by:

higherEntry in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

an Entry with least key greater than the given key, or null if there is no such Entry.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

higherKey

public K higherKey(K key)

Returns the least key strictly greater than the given key, or null if there is no such key.

Specified by:

higherKey in interface NavigableMap<K,V>

Parameters:

key - the key.

Returns:

the least key greater than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if key cannot be compared with the keys currently in the map.

java.lang.NullPointerException - if key is null.

firstEntry

public java.util.Map.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.

Specified by:

firstEntry in interface NavigableMap<K,V>

Returns:

an Entry with least key, or null if the map is empty.

lastEntry

public java.util.Map.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.

Specified by:

lastEntry in interface NavigableMap<K,V>

Returns:

an Entry with greatest key, or null if the map is empty.

pollFirstEntry

public java.util.Map.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.

Specified by:

pollFirstEntry in interface NavigableMap<K,V>

Returns:

the removed first entry of this map, or null if the map is empty.

pollLastEntry

public java.util.Map.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.

Specified by:

pollLastEntry in interface NavigableMap<K,V>

Returns:

the removed last entry of this map, or null if the map is empty.

keyIterator

java.util.Iterator<K> keyIterator()

descendingKeyIterator

java.util.Iterator<K> descendingKeyIterator()

subMapEntryIterator

ConcurrentSkipListMap.SubMapEntryIterator subMapEntryIterator(K least,
                                                              K fence)

descendingSubMapEntryIterator

ConcurrentSkipListMap.DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least,
                                                                                  K fence)

subMapKeyIterator

ConcurrentSkipListMap.SubMapKeyIterator subMapKeyIterator(K least,
                                                          K fence)

descendingSubMapKeyIterator

ConcurrentSkipListMap.DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least,
                                                                              K fence)

subMapValueIterator

ConcurrentSkipListMap.SubMapValueIterator subMapValueIterator(K least,
                                                              K fence)