|
Oracle® Coherence Java API Reference Release 3.6.0.0 E15725-01 |
|||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object
java.util.AbstractMap
com.tangosol.util.SafeSortedMap
public class SafeSortedMap
SafeSortedMap is an implementation of SortedMap
based on a skip-list that is structurally thread-safe. SafeSortedMap uses lockless (CAS-based) algorithms so all operations are performed without synchronization. In the presence of concurrent updates, SafeSortedMap iterators will reflect some state of the map, but will not throw ConcurrentModificationException or other unexpected exceptions. <p/> The structure of the SafeSortedMap is maintained in a 2-dimensional lattice:
Top | I3 -------------------------------> S5 -------------> | | I2 -------------> S2 -------------> S5 -------------> | | | I1 -------> S1 -> S2 -------> S4 -> S5 -------> S7 -> | | | | | | E -> E0 -> E1 -> E2 -> E3 -> E4 -> E5 -> E6 -> E7 ->
<p/> Searching for a key involves traversing, starting from the top index node, as far to the right at each index level, then down. For example, the search path for the element E4 in the above example would be:
The search path for the element E7 in the above example would be:
<p/> Removing a key involves inserting a temporary marker-entry while the entry pointers are fixed up. The marker node allows uncontended read threads to traverse the safely. Additionally, removing a key causes any index nodes for that key to be removed as well. <p/> In the above example, the steps to remove entry E3 would be:
The steps to remove E4 (indexed to level 1) would be:
Inserting a key happens in 'bottom-up' fashion, with the entry node being inserted first, (possibly) followed by index nodes of increasing level. Inserts are fully synchronized on the map. When inserting a new entry, an index level randomly computed such that, the probability that a given insertion will be indexed to level n is approximately given by: (1/k)n where k is the average span of each index level. In the above example, the steps to insert entry E3.5 at index-level 1 would be:
<p/>
Nested Class Summary | |
---|---|
protected static class |
SafeSortedMap.BaseEntryNode BaseEntryNode is a synthetic EntryNode that serves as the "head" of the base entry list. |
protected static class |
SafeSortedMap.EntryNode EntryNode represents a key-value mapping in this map. |
protected class |
SafeSortedMap.IndexNode IndexNode represents the start node in the map's lattice representation at a given index-level. |
protected static class |
SafeSortedMap.SkipNode SkipNode is an entry or index node in the lattice for a SafeSortedMap's representation. |
class |
SafeSortedMap.Split Split encapsulates the headMap and tailMap of the SafeSortedMap at a given split-key and could be used as an optimization facility when both head and tail portions of the SortedMap are needed. |
protected class |
SafeSortedMap.ViewMap ViewMap provides a SortedMap view over a subset of the SafeSortedMap. |
Nested classes/interfaces inherited from interface java.util.Map |
---|
Map.Entry |
Field Summary | |
---|---|
protected static Object |
BASE_VALUE Placeholder for a non-existent (deleted) value. |
protected static int |
DEFAULT_MAX_LEVEL The default limit on the index-level. |
protected static int |
DEFAULT_SPAN The default span value. |
protected float[] |
m_aflProbabilityThresholds The array of pre-computed probability thresholds for each level. |
protected static AtomicReferenceFieldUpdater |
m_atomicUpdaterTopNode AtomicUpdater for the casTopNode operation. |
protected Comparator |
m_comparator The comparator used to sort this map. |
protected SafeSortedMap.ViewMap |
m_mapView The default ViewMap (over the entire map's range). |
protected int |
m_nLevelMax The maximum number of index levels to use for this map. |
protected SafeSortedMap.IndexNode |
m_nodeTop The top index node. |
protected int |
m_nSpan The span of the map. |
protected Random |
m_random The random-number generator for the map. |
protected static Object |
NO_VALUE Placeholder for a non-existent (deleted) value. |
protected static int |
SEARCH_EQ Search mode for equal-to. |
protected static int |
SEARCH_GT Search mode for strictly greater-than. |
protected static int |
SEARCH_GTEQ Search mode for greater-than or equal. |
protected static int |
SEARCH_LT Search mode for strictly less-than. |
protected static int |
SEARCH_LTEQ Search mode for less-than or equal. |
Constructor Summary | |
---|---|
SafeSortedMap() Construct a new SafeSortedMap using the natural ordering of the Comparable keys in this map. |
|
SafeSortedMap(Comparator comparator) Construct a new SafeSortedMap with the specified Comparator. |
|
SafeSortedMap(Comparator comparator, int nSpan, int nLevelMax) Construct a new SafeSortedMap with the specified parameters. |
Method Summary | |
---|---|
protected int |
calculateRandomLevel() Randomly generate a level value 0 <= L <= MAX_LEVEL, in such a way that the probability p(l) of generating level l is equal to p(l)=(1/span)^(l+1) and p(0)=1-(sum of p(l) over l=1..MAX_LEVEL). |
protected boolean |
casTopNode(SafeSortedMap.IndexNode nodeTopAssume, SafeSortedMap.IndexNode nodeTopNew) Atomically set specified IndexNode to the top node iff the current top node is the expected top node. |
void |
clear() Removes all mappings from this map (optional operation). |
Comparator |
comparator() Returns the comparator associated with this sorted map, or null if it uses its keys' natural ordering. |
protected static float[] |
computeProbabilityThresholds(int nLevelMax, int nSpan) Compute and return an array, indexed by level, of the probability thresholds used to determine what level an entry should be indexed to. |
boolean |
containsKey(Object oKey) Returns true if this map contains a mapping for the specified key. |
String |
dump() Return a human-readable description of this map's internal state. |
Set |
entrySet() Returns a set view of the mappings contained in this map. |
protected SafeSortedMap.EntryNode |
findNearest(SafeSortedMap.IndexNode nodeTop, Object oKey, int nMode, boolean fFixLinks) Return the SkipNode closest to the specified key, or null. |
protected SafeSortedMap.EntryNode |
findNearestIndexedEntry(SafeSortedMap.IndexNode nodeTop, Object oKey, int nMode) Return the EntryNode nearest to the specified key according to the specified search mode, or the synthetic base node if there is none. |
protected SafeSortedMap.EntryNode |
findPredecessor(SafeSortedMap.IndexNode nodeTop, Object oKey) Return an EntryNode that compares strictly less than the specified key, or the synthetic base node if there is none. |
Object |
firstKey() Returns the first (lowest) key currently in this sorted map. |
protected SafeSortedMap.EntryNode |
firstNode() Return the first valid EntryNode, or null if there are none. |
Object |
get(Object oKey) Returns the value to which this map maps the specified key. |
protected SafeSortedMap.BaseEntryNode |
getBaseNode() Return the base entry node. |
Map.Entry |
getEntry(Object oKey) Locate a Map.Entry in this map based on its key. |
protected int |
getMaxLevel() Return the maximum index-level that this map is allowed to reach. |
protected float[] |
getProbabilityThresholds() Return the precomputed array of probability thresholds used by this map to determine what index levels to build. |
protected Random |
getRandom() Return the random number generator for this map. |
protected int |
getSpan() Return the span of this map. |
protected SafeSortedMap.IndexNode |
getTopNode() Return the top index node in the map. |
protected SafeSortedMap.ViewMap |
getViewMap() Return a view of the entire map. |
SortedMap |
headMap(Object toKey) Returns a view of the portion of this sorted map whose keys are strictly less than toKey. |
protected void |
initialize() Initialize the index nodes. |
protected void |
insertIndex(SafeSortedMap.IndexNode nodeTop, SafeSortedMap.EntryNode nodeNew, int nLevelThis) Insert a index nodes for the specified newly inserted EntryNode, up to a random index-level. |
Object |
lastKey() Returns the last (highest) key currently in this sorted map. |
protected SafeSortedMap.EntryNode |
lastNode() Return the last valid EntryNode, or null if there are none. |
Object |
put(Object oKey, Object oValue) Associates the specified value with the specified key in this map (optional operation). |
Object |
remove(Object oKey) Removes the mapping for this key from this map if present (optional operation). |
protected void |
setTopNode(SafeSortedMap.IndexNode nodeTop) Set the top index node in the map. |
int |
size() Returns the number of key-value mappings in this map. |
SafeSortedMap.Split |
split(Object oKey) Return a SafeSortedMap.Split of this map at the specified key. |
SortedMap |
subMap(Object fromKey, Object toKey) Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive. |
SortedMap |
tailMap(Object fromKey) Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey. |
Methods inherited from class java.util.AbstractMap |
---|
clone, containsValue, equals, hashCode, isEmpty, keySet, putAll, toString, values |
Methods inherited from interface java.util.Map |
---|
containsValue, equals, hashCode, isEmpty, keySet, putAll, values |
Field Detail |
---|
protected static final int DEFAULT_SPAN
protected static final int DEFAULT_MAX_LEVEL
protected static final int SEARCH_EQ
protected static final int SEARCH_LT
protected static final int SEARCH_GT
protected static final int SEARCH_LTEQ
protected static final int SEARCH_GTEQ
protected static final Object NO_VALUE
protected static final Object BASE_VALUE
protected static final AtomicReferenceFieldUpdater m_atomicUpdaterTopNode
protected final Comparator m_comparator
protected final int m_nLevelMax
protected final float[] m_aflProbabilityThresholds
protected int m_nSpan
protected final SafeSortedMap.ViewMap m_mapView
protected volatile SafeSortedMap.IndexNode m_nodeTop
protected Random m_random
Constructor Detail |
---|
public SafeSortedMap()
public SafeSortedMap(Comparator comparator)
comparator
- the comparator used to sort this mappublic SafeSortedMap(Comparator comparator, int nSpan, int nLevelMax)
comparator
- the comparator used to sort this mapnSpan
- the average span to use for each index-levelnLevelMax
- the maximum index-level to use for this mapMethod Detail |
---|
public int size()
This implementation returns entrySet().size().
size
in interface Map
size
in class AbstractMap
public boolean containsKey(Object oKey)
This implementation iterates over entrySet() searching for an entry with the specified key. If such an entry is found, true is returned. If the iteration terminates without finding such an entry, false is returned. Note that this implementation requires linear time in the size of the map; many implementations will override this method.
containsKey
in interface Map
containsKey
in class AbstractMap
oKey
- key whose presence in this map is to be tested.public Set entrySet()
entrySet
in interface Map
entrySet
in class AbstractMap
public Object put(Object oKey, Object oValue)
This implementation always throws an UnsupportedOperationException.
put
in interface Map
put
in class AbstractMap
oKey
- key with which the specified value is to be associated.oValue
- value to be associated with the specified key.public Object get(Object oKey)
This implementation iterates over entrySet() searching for an entry with the specified key. If such an entry is found, the entry's value is returned. If the iteration terminates without finding such an entry, null is returned. Note that this implementation requires linear time in the size of the map; many implementations will override this method.
get
in interface Map
get
in class AbstractMap
oKey
- key whose associated value is to be returned.AbstractMap.containsKey(Object)
public Map.Entry getEntry(Object oKey)
oKey
- the key to return an Entry forpublic Object remove(Object oKey)
This implementation iterates over entrySet() searching for an entry with the specified key. If such an entry is found, its value is obtained with its getValue operation, the entry is removed from the Collection (and the backing map) with the iterator's remove operation, and the saved value is returned. If the iteration terminates without finding such an entry, null is returned. Note that this implementation requires linear time in the size of the map; many implementations will override this method.
Note that this implementation throws an UnsupportedOperationException if the entrySet iterator does not support the remove method and this map contains a mapping for the specified key.
remove
in interface Map
remove
in class AbstractMap
oKey
- key whose mapping is to be removed from the map.public void clear()
This implementation calls entrySet().clear(). Note that this implementation throws an UnsupportedOperationException if the entrySet does not support the clear operation.
clear
in interface Map
clear
in class AbstractMap
public Comparator comparator()
comparator
in interface SortedMap
public SortedMap subMap(Object fromKey, Object toKey)
The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.
Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need a closed range (which includes both endpoints), and the key type allows for calculation of the successor a given key, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, inclusive:
Map sub = m.subMap(low, high+"\0");A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, exclusive:
Map sub = m.subMap(low+"\0", high);
subMap
in interface SortedMap
fromKey
- low endpoint (inclusive) of the subMap.toKey
- high endpoint (exclusive) of the subMap.public SortedMap headMap(Object toKey)
The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.
Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by successor(highEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are less than or equal to high:
Map head = m.headMap(high+"\0");
headMap
in interface SortedMap
toKey
- high endpoint (exclusive) of the subMap.public SortedMap tailMap(Object fromKey)
The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.
Note: this method always returns a view that contains its (low) endpoint. If you need a view that does not contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a tailMap bounded by successor(lowEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are strictly greater than low:
Map tail = m.tailMap(low+"\0");
tailMap
in interface SortedMap
fromKey
- low endpoint (inclusive) of the tailMap.public Object firstKey()
firstKey
in interface SortedMap
public Object lastKey()
lastKey
in interface SortedMap
protected SafeSortedMap.ViewMap getViewMap()
protected float[] getProbabilityThresholds()
calculateRandomLevel()
protected Random getRandom()
protected int getMaxLevel()
protected int getSpan()
protected void initialize()
protected SafeSortedMap.IndexNode getTopNode()
protected void setTopNode(SafeSortedMap.IndexNode nodeTop)
nodeTop
- the new top index nodeprotected boolean casTopNode(SafeSortedMap.IndexNode nodeTopAssume, SafeSortedMap.IndexNode nodeTopNew)
nodeTopAssume
- the IndexNode assumed to be the current top nodenodeTopNew
- the new top nodeprotected SafeSortedMap.BaseEntryNode getBaseNode()
protected SafeSortedMap.EntryNode firstNode()
protected SafeSortedMap.EntryNode lastNode()
protected void insertIndex(SafeSortedMap.IndexNode nodeTop, SafeSortedMap.EntryNode nodeNew, int nLevelThis)
nodeTop
- the top index nodenodeNew
- the newly inserted EntryNodenLevelThis
- the level at which to index the specified EntryNodeprotected SafeSortedMap.EntryNode findNearest(SafeSortedMap.IndexNode nodeTop, Object oKey, int nMode, boolean fFixLinks)
nodeTop
- the top index nodeoKey
- the key to search fornMode
- one of the SEARCH_* constantsfFixLinks
- true iff deletion links must be fixedprotected SafeSortedMap.EntryNode findPredecessor(SafeSortedMap.IndexNode nodeTop, Object oKey)
nodeTop
- the top index nodeoKey
- the key to find a predecessor forprotected SafeSortedMap.EntryNode findNearestIndexedEntry(SafeSortedMap.IndexNode nodeTop, Object oKey, int nMode)
nodeTop
- the top index nodeoKey
- the key to find an indexed EntryNode fornMode
- SEARCH_LT or SEARCH_LTEQ)protected static float[] computeProbabilityThresholds(int nLevelMax, int nSpan)
nLevelMax
- the maximum number of levels to compute thresholds fornSpan
- the span of this mapprotected int calculateRandomLevel()
public String dump()
public SafeSortedMap.Split split(Object oKey)
SafeSortedMap.Split
of this map at the specified key.oKey
- the key at which to split the map
|
Oracle® Coherence Java API Reference Release 3.6.0.0 E15725-01 |
|||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |