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 mapV
- 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 scalableConcurrentNavigableMap
implementation. This class maintains a map in ascending key order, sorted according to the natural order for the key's class (seeComparable
), or by theComparator
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
andIterator
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 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 byConcurrentSkipListMap
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
-
Field Summary
Fields Modifier and Type Field Description private static java.lang.Object
BASE_HEADER
Special value used to identify base-level headerprivate 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 setprivate ConcurrentSkipListMap.DescendingKeySet
descendingKeySet
Lazily initialized descending key setprivate ConcurrentSkipListMap.EntrySet
entrySet
Lazily initialized entry setprivate 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 casHeadprivate ConcurrentSkipListMap.KeySet
keySet
Lazily initialized key setprivate 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 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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 nodejava.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>
booleancontainsAllMappings(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.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
-
-
-
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 keyvalue
- the value that must be associated with keyonlyIfAbsent
- 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 nodelevel
- 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 insertedh
- the value of head to use to insert. This must be snapshotted by callers to provide correct insertion levelindexLevel
- 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 keyvalue
- 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 keyrel
- 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 keyrel
- 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 keyrel
- the relation -- OR'ed combination of EQ, LT, GTleast
- minimum allowed key valuefence
- key greater than maximum allowed key valuekeyOnly
- 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 valuefence
- key greater than maximum allowed key valuekeyOnly
- 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 valuefence
- key greater than maximum allowed key valuekeyOnly
- 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.)
-
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 interfacejava.util.Map<K,V>
- Overrides:
containsKey
in classjava.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 interfacejava.util.Map<K,V>
- Overrides:
get
in classjava.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 interfacejava.util.Map<K,V>
- Overrides:
put
in classjava.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 interfacejava.util.Map<K,V>
- Overrides:
remove
in classjava.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 interfacejava.util.Map<K,V>
- Overrides:
containsValue
in classjava.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.
-
isEmpty
public boolean isEmpty()
Returns true if this map contains no key-value mappings.
-
clear
public void clear()
Removes all mappings from this map.
-
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 throwConcurrentModificationException
, 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.
-
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 throwConcurrentModificationException
, 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 interfaceNavigableMap<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 throwConcurrentModificationException
, 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.
-
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 throwConcurrentModificationException
, 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.
-
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 throwConcurrentModificationException
, 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 interfaceNavigableMap<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.
-
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 toif (!map.containsKey(key)) return map.put(key, value); else return map.get(key);
except that the action is performed atomically.- Specified by:
putIfAbsent
in interfacejava.util.concurrent.ConcurrentMap<K,V>
- Specified by:
putIfAbsent
in interfacejava.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 asif ((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 interfacejava.util.concurrent.ConcurrentMap<K,V>
- Specified by:
remove
in interfacejava.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 asif ((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 interfacejava.util.concurrent.ConcurrentMap<K,V>
- Specified by:
replace
in interfacejava.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 asif ((map.containsKey(key)) { return map.put(key, value); } else return null;
except that the action is performed atomically.- Specified by:
replace
in interfacejava.util.concurrent.ConcurrentMap<K,V>
- Specified by:
replace
in interfacejava.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.
-
firstKey
public K firstKey()
Returns the first (lowest) key currently in this map.
-
lastKey
public K lastKey()
Returns the last (highest) key currently in this map.
-
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 interfaceConcurrentNavigableMap<K,V>
- Specified by:
subMap
in interfaceNavigableMap<K,V>
- Specified by:
subMap
in interfacejava.util.SortedMap<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 interfaceConcurrentNavigableMap<K,V>
- Specified by:
headMap
in interfaceNavigableMap<K,V>
- Specified by:
headMap
in interfacejava.util.SortedMap<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 interfaceConcurrentNavigableMap<K,V>
- Specified by:
tailMap
in interfaceNavigableMap<K,V>
- Specified by:
tailMap
in interfacejava.util.SortedMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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 interfaceNavigableMap<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)
-
-