SafeSortedMap (Java API Reference for Oracle® Coherence Community Edition)

java.lang.Object
- java.util.AbstractMap
- - com.tangosol.util.SafeSortedMap

All Implemented Interfaces:

Map, SortedMap
```
public class SafeSortedMap
extends AbstractMap
implements SortedMap
```
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.
Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.
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 ->
 
```
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:
1. compare E4 with S5 on index level 3; move down to level 2
2. compare E4 with S2 on index level 2; move right
3. compare E4 with S5 on index level 2; move down to level 1
4. compare E4 with S4 on index level 1; move right
5. move down
The search path for the element E7 in the above example would be:
1. compare E7 with S5 on index level 3; move right
2. move down to level 2
3. move down to level 1
4. compare E7 with S7 on index level 1; move right
5. move down
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.
In the above example, the steps to remove entry E3 would be:
1. find LT search-path of Top->I3->S2->S2->E2
2. create new marker node D3
3. set D3 -> E4
4. set E3 -> D3
5. set E2 -> E3
The steps to remove E4 (indexed to level 1) would be:
1. find LT search-path of Top->I3->S2->S2->E3
2. create new marker node D4
3. set D4 -> E5
4. set E4 -> D4
5. set E3 -> E5
6. move up to level 1
7. set D4' -> S5
8. set S4 -> D4'
9. set S2 -> S5
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)ⁿ 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:
1. find LT search-path of Top->I3->S2->S2->E2
2. create new entry node E3.5
3. set E3.5 -> E4
4. set E2 -> E3.5
5. move up to level 1
6. create new entry node S3.5
7. set S3.5 -> S4
8. set S2 -> S3.5
Since:

Coherence 3.5

Author:

rhl 2009.03.31

See Also:

Bill Pugh's original paper

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`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 class java.util.AbstractMap
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map
Map.Entry<K,V>

Field Summary

Fields
Modifier and Type	Field and Description
`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

Constructors
Constructor and Description
`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

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`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()`
`Comparator`	`comparator()`
`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)`
`String`	`dump()` Return a human-readable description of this map's internal state.
`Set`	`entrySet()`
`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()`
`protected SafeSortedMap.EntryNode`	`firstNode()` Return the first valid EntryNode, or null if there are none.
`Object`	`get(Object oKey)`
`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)`
`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()`
`protected SafeSortedMap.EntryNode`	`lastNode()` Return the last valid EntryNode, or null if there are none.
`Object`	`put(Object oKey, Object oValue)`
`Object`	`remove(Object oKey)`
`protected void`	`setTopNode(SafeSortedMap.IndexNode nodeTop)` Set the top index node in the map.
`int`	`size()`
`SafeSortedMap.Split`	`split(Object oKey)` Return a `SafeSortedMap.Split` of this map at the specified key.
`SortedMap`	`subMap(Object fromKey, Object toKey)`
`SortedMap`	`tailMap(Object fromKey)`

Methods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, isEmpty, keySet, putAll, toString, values

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.SortedMap
keySet, values

Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll

- Field Detail
  - DEFAULT_SPAN
```
protected static final int DEFAULT_SPAN
```
    The default span value.
    
    See Also:
    
    Constant Field Values
  - DEFAULT_MAX_LEVEL
```
protected static final int DEFAULT_MAX_LEVEL
```
    The default limit on the index-level.
    
    See Also:
    
    Constant Field Values
  - SEARCH_EQ
```
protected static final int SEARCH_EQ
```
    Search mode for equal-to.
    
    See Also:
    
    Constant Field Values
  - SEARCH_LT
```
protected static final int SEARCH_LT
```
    Search mode for strictly less-than.
    
    See Also:
    
    Constant Field Values
  - SEARCH_GT
```
protected static final int SEARCH_GT
```
    Search mode for strictly greater-than.
    
    See Also:
    
    Constant Field Values
  - SEARCH_LTEQ
```
protected static final int SEARCH_LTEQ
```
    Search mode for less-than or equal.
    
    See Also:
    
    Constant Field Values
  - SEARCH_GTEQ
```
protected static final int SEARCH_GTEQ
```
    Search mode for greater-than or equal.
    
    See Also:
    
    Constant Field Values
  - NO_VALUE
```
protected static final Object NO_VALUE
```
    Placeholder for a non-existent (deleted) value.
  - BASE_VALUE
```
protected static final Object BASE_VALUE
```
    Placeholder for a non-existent (deleted) value.
  - m_atomicUpdaterTopNode
```
protected static final AtomicReferenceFieldUpdater m_atomicUpdaterTopNode
```
    AtomicUpdater for the casTopNode operation.
  - m_comparator
```
protected final Comparator m_comparator
```
    The comparator used to sort this map.
  - m_nLevelMax
```
protected final int m_nLevelMax
```
    The maximum number of index levels to use for this map.
  - m_aflProbabilityThresholds
```
protected final float[] m_aflProbabilityThresholds
```
    The array of pre-computed probability thresholds for each level.
  - m_nSpan
```
protected int m_nSpan
```
    The span of the map.
  - m_mapView
```
protected final SafeSortedMap.ViewMap m_mapView
```
    The default ViewMap (over the entire map's range).
  - m_nodeTop
```
protected volatile SafeSortedMap.IndexNode m_nodeTop
```
    The top index node. This is declared volatile so read operations can be unsynchronized.
  - m_random
```
protected Random m_random
```
    The random-number generator for the map.
- Constructor Detail
  - SafeSortedMap
```
public SafeSortedMap()
```
    Construct a new SafeSortedMap using the natural ordering of the Comparable keys in this map.
  - SafeSortedMap
```
public SafeSortedMap(Comparator comparator)
```
    Construct a new SafeSortedMap with the specified Comparator.
    
    Parameters:
    
    comparator - the comparator used to sort this map
  - SafeSortedMap
```
public SafeSortedMap(Comparator comparator,
                     int nSpan,
                     int nLevelMax)
```
    Construct a new SafeSortedMap with the specified parameters.
    
    Parameters:
    
    comparator - the comparator used to sort this map, or null for the entries' natural ordering
    
    nSpan - the average span to use for each index-level
    
    nLevelMax - the maximum index-level to use for this map
- Method Detail
  - size
```
public int size()
```
    Specified by:
    
    size in interface Map
    
    Overrides:
    
    size in class AbstractMap
  - containsKey
```
public boolean containsKey(Object oKey)
```
    Specified by:
    
    containsKey in interface Map
    
    Overrides:
    
    containsKey in class AbstractMap
  - entrySet
```
public Set entrySet()
```
    Specified by:
    
    entrySet in interface Map
    
    Specified by:
    
    entrySet in interface SortedMap
    
    Specified by:
    
    entrySet in class AbstractMap
  - put
```
public Object put(Object oKey,
                  Object oValue)
```
    Specified by:
    
    put in interface Map
    
    Overrides:
    
    put in class AbstractMap
  - get
```
public Object get(Object oKey)
```
    Specified by:
    
    get in interface Map
    
    Overrides:
    
    get in class AbstractMap
  - getEntry
```
public Map.Entry getEntry(Object oKey)
```
    Locate a Map.Entry in this map based on its key.
    Note: the behaviour of {#setValue} on the returned Entry is undefined in the presence of concurrent modifications
    
    Parameters:
    
    oKey - the key to return an Entry for
    
    Returns:
    
    an Entry corresponding to the specified key, or null if none exists
  - remove
```
public Object remove(Object oKey)
```
    Specified by:
    
    remove in interface Map
    
    Overrides:
    
    remove in class AbstractMap
  - clear
```
public void clear()
```
    Specified by:
    
    clear in interface Map
    
    Overrides:
    
    clear in class AbstractMap
  - comparator
```
public Comparator comparator()
```
    Specified by:
    
    comparator in interface SortedMap
  - subMap
```
public SortedMap subMap(Object fromKey,
                        Object toKey)
```
    Specified by:
    
    subMap in interface SortedMap
  - headMap
```
public SortedMap headMap(Object toKey)
```
    Specified by:
    
    headMap in interface SortedMap
  - tailMap
```
public SortedMap tailMap(Object fromKey)
```
    Specified by:
    
    tailMap in interface SortedMap
  - firstKey
```
public Object firstKey()
```
    Specified by:
    
    firstKey in interface SortedMap
  - lastKey
```
public Object lastKey()
```
    Specified by:
    
    lastKey in interface SortedMap
  - getViewMap
```
protected SafeSortedMap.ViewMap getViewMap()
```
    Return a view of the entire map.
    
    Returns:
    
    a view of the entire map
  - getProbabilityThresholds
```
protected float[] getProbabilityThresholds()
```
    Return the precomputed array of probability thresholds used by this map to determine what index levels to build.
    
    Returns:
    
    the precomputed array of probability thresholds
    
    See Also:
    
    calculateRandomLevel()
  - getRandom
```
protected Random getRandom()
```
    Return the random number generator for this map.
    
    Returns:
    
    the random number generator for this map
  - getMaxLevel
```
protected int getMaxLevel()
```
    Return the maximum index-level that this map is allowed to reach.
    
    Returns:
    
    the maximum index-level that this map is allowed to reach
  - getSpan
```
protected int getSpan()
```
    Return the span of this map.
    
    Returns:
    
    the span of this map
  - initialize
```
protected void initialize()
```
    Initialize the index nodes.
  - getTopNode
```
protected SafeSortedMap.IndexNode getTopNode()
```
    Return the top index node in the map.
    
    Returns:
    
    the top index node in the map
  - setTopNode
```
protected void setTopNode(SafeSortedMap.IndexNode nodeTop)
```
    Set the top index node in the map.
    
    Parameters:
    
    nodeTop - the new top index node
  - casTopNode
```
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.
    
    Parameters:
    
    nodeTopAssume - the IndexNode assumed to be the current top node
    
    nodeTopNew - the new top node
    
    Returns:
    
    true iff the top node is successfully updated
  - getBaseNode
```
protected SafeSortedMap.BaseEntryNode getBaseNode()
```
    Return the base entry node.
    
    Returns:
    
    the base entry node
  - firstNode
```
protected SafeSortedMap.EntryNode firstNode()
```
    Return the first valid EntryNode, or null if there are none.
    
    Returns:
    
    the first EntryNode or null if empty
  - lastNode
```
protected SafeSortedMap.EntryNode lastNode()
```
    Return the last valid EntryNode, or null if there are none.
    
    Returns:
    
    the last valid EntryNode or null if empty
  - insertIndex
```
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. Return true if the key was inserted, or false otherwise (if an intervening insert was made for the same key).
    
    Parameters:
    
    nodeTop - the top index node
    
    nodeNew - the newly inserted EntryNode
    
    nLevelThis - the level at which to index the specified EntryNode
  - findNearest
```
protected SafeSortedMap.EntryNode findNearest(SafeSortedMap.IndexNode nodeTop,
                                              Object oKey,
                                              int nMode,
                                              boolean fFixLinks)
```
    Return the SkipNode closest to the specified key, or null.
    
    Parameters:
    
    nodeTop - the top index node
    
    oKey - the key to search for
    
    nMode - one of the SEARCH_* constants
    
    fFixLinks - true iff deletion links must be fixed
    
    Returns:
    
    the SkipNode closest to the specified key, or null
  - findPredecessor
```
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.
    Note: this method is merely guaranteed to return some EntryNode that is less than the specified node, not necessarily the node that is immediately less than the specified node
    
    Parameters:
    
    nodeTop - the top index node
    
    oKey - the key to find a predecessor for
    
    Returns:
    
    an EntryNode that is strictly less than the specified key
  - findNearestIndexedEntry
```
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.
    
    Parameters:
    
    nodeTop - the top index node
    
    oKey - the key to find an indexed EntryNode for
    
    nMode - SEARCH_LT or SEARCH_LTEQ)
    
    Returns:
    
    an indexed EntryNode that is nearest to the specified key according to the specified search mode
  - computeProbabilityThresholds
```
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.
    Threshold values are in the range [0, 1). A randomly chosen value v in that range corresponds to a level l iff the following condition holds: threshold[l-1] <= v < threshold[l-1]
    
    Parameters:
    
    nLevelMax - the maximum number of levels to compute thresholds for
    
    nSpan - the span of this map
    
    Returns:
    
    an array containing the distribution probabilities
  - calculateRandomLevel
```
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).
    For example, the probabilities (with span=2, and weight of 2) of returning the following levels are: 0 (no-index) - 3/4 1 - 1/8 2 - 1/16 3 - 1/32 ...
    
    Returns:
    
    a random level number between 0 and MAX_LEVEL
  - dump
```
public String dump()
```
    Return a human-readable description of this map's internal state.
    
    Returns:
    
    a human-readable description of this map's internal state
  - split
```
public SafeSortedMap.Split split(Object oKey)
```
    Return a SafeSortedMap.Split of this map at the specified key.
    
    Parameters:
    
    oKey - the key at which to split the map
    
    Returns:
    
    a Split of this map at the specified key

Class SafeSortedMap

Nested Class Summary

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

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

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.SortedMap

Methods inherited from interface java.util.Map

Field Detail

DEFAULT_SPAN

DEFAULT_MAX_LEVEL

SEARCH_EQ

SEARCH_LT

SEARCH_GT

SEARCH_LTEQ

SEARCH_GTEQ

NO_VALUE

BASE_VALUE

m_atomicUpdaterTopNode

m_comparator

m_nLevelMax

m_aflProbabilityThresholds

m_nSpan

m_mapView

m_nodeTop

m_random

Constructor Detail

SafeSortedMap

SafeSortedMap

SafeSortedMap

Method Detail

size

containsKey

entrySet

put

get

getEntry

remove

clear

comparator

subMap

headMap

tailMap

firstKey

lastKey

getViewMap

getProbabilityThresholds

getRandom

getMaxLevel

getSpan

initialize

getTopNode

setTopNode

casTopNode

getBaseNode

firstNode

lastNode

insertIndex

findNearest

findPredecessor

findNearestIndexedEntry

computeProbabilityThresholds

calculateRandomLevel

dump

split