Overview | Package | Class | Tree | Index | Help

Oracle® Coherence Java API Reference
v3.5.3
E15583-01
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## com.tangosol.util
Class SafeSortedMap

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

All Implemented Interfaces:
  java.util.Map, java.util.SortedMap

    public class SafeSortedMap

extends java.util.AbstractMap
implements java.util.SortedMap

SafeSortedMap is an implementation of `SortedMap` based on a skip-list that is structurally thread-safe. Read-only operations are performed without synchronization; mutations synchronize on the map. In the presence of concurrent updates, SafeSortedMap iterators will reflect some state of the map, but will not throw ConcurrentModificationException or other unexpected exceptions.

The structure of the SafeSortedMap is maintained in a 2-dimensional lattice:

      Top
       |
      I3 -------------------------------> S5 ------------->
       |                                   |
      I2 -------------> S2 -------------> S5 ------------->
       |                 |                 |
      I1 -------> S1 -> S2 -------> S4 -> S5 -------> S7 ->
       |           |     |           |     |           |
      I0 -> 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. Removals are synchronized on the map and proceed bottom up, removing the entry first followed by any index nodes in increasing index-level order.

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)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:

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
`protected class` | `SafeSortedMap.DeletedNode` DeletedNode is a SkipNode that is used as a marker during deletion.
`protected 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 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
`java.util.Map.Entry`

Field Summary
`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_aflProbability` The array of pre-computed probabilities for each level.
`protected SafeSortedMap.SkipNode[]` | `m_aNodeBuffer` The scratch buffer used by mutation operations to store the search path to the insertion/deletion site.
`protected java.util.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_nSize` The memoized size of the map.
`protected int` | `m_nSpan` The span of the map.
`protected java.util.Random` | `m_random` The random-number generator for the map.
`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(java.util.Comparator comparator)` Construct a new SafeSortedMap with the specified Comparator.
`SafeSortedMap(java.util.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 and p(0)=1/span.
`void` | `clear()`
`java.util.Comparator` | `comparator()`
`boolean` | `containsKey(java.lang.Object oKey)`
`protected java.lang.Object` | `deleteNode(SafeSortedMap.EntryNode node)` Delete the specified node, as well any associated index nodes.
`java.lang.String` | `dump()` Return a human-readable description of this map's internal state.
`java.util.Set` | `entrySet()`
`protected SafeSortedMap.EntryNode` | `findKey(java.lang.Object oKey)` Return the EntryNode for the specified key if it is contained in this map, or null otherwise.
`protected SafeSortedMap.SkipNode` | `findNearest(java.lang.Object oKey, int nMode)` Return the SkipNode closest to the specified key, or null.
`protected SafeSortedMap.SkipNode[]` | `findNearestPath(java.lang.Object oKey, int nMode)` Return the search/index path to the node closest to the specified key.
`protected SafeSortedMap.SkipNode[]` | `findNearestPath(java.lang.Object oKey, int nMode, SafeSortedMap.SkipNode[] aNodePath)` Return the search/index path to the node closest to the specified key.
`protected SafeSortedMap.SkipNode` | `findOnSameLevel(SafeSortedMap.SkipNode nodeStart, java.lang.Object oKey, int nMode)` Find the closest SkipNode (according to the specified search mode) to the specified key, starting from the specified SkipNode.
`java.lang.Object` | `firstKey()`
`java.lang.Object` | `get(java.lang.Object oKey)`
`java.util.Map.Entry` | `getEntry(java.lang.Object key)` Locate an Entry in the this map based on its key.
`protected int` | `getLevel()` Return the current maximum level of this map's index (the highest level that any key has built an index node for).
`protected int` | `getMaxLevel()` Return the maximum index-level that this map is allowed to reach.
`protected float[]` | `getProbabilities()` Return the precomputed array of probability values used by this map to determine what index levels to build.
`protected java.util.Random` | `getRandom()` Return the random number generator for this map.
`protected SafeSortedMap.SkipNode[]` | `getSearchBuffer()` Return the buffer used to hold the search path for insertion/deletion operations.
`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.
`java.util.SortedMap` | `headMap(java.lang.Object toKey)`
`protected boolean` | `insertNode(java.lang.Object oKey, java.lang.Object oValue)` Insert a new EntryNode and (possibly) SkipNode(s) for the specified key and value in this skip-list, up to a random index-level.
`java.lang.Object` | `lastKey()`
`java.lang.Object` | `put(java.lang.Object oKey, java.lang.Object oValue)`
`java.lang.Object` | `remove(java.lang.Object oKey)`
`protected SafeSortedMap.SkipNode` | `search(java.lang.Object oKey, int nMode, SafeSortedMap.IndexNode nodeTop, SafeSortedMap.SkipNode[] aNodePath)` Return the search/index path to the node closest to the specified key.
`protected void` | `setSearchBuffer(SafeSortedMap.SkipNode[] aNodeBuffer)` Set the buffer used to hold the search path for insertion/deletion operations.
`protected void` | `setSize(int nSize)` Set the size of this map (cached to make the size() operation less expensive, since we already synchronize on all updates).
`protected void` | `setTopNode(SafeSortedMap.IndexNode nodeTop)` Set the top index node in the map.
`int` | `size()`
`SafeSortedMap.Split` | `split(java.lang.Object oKey)` Return a `SafeSortedMap.Split` of this map at the specified key.
`java.util.SortedMap` | `subMap(java.lang.Object fromKey, java.lang.Object toKey)`
`java.util.SortedMap` | `tailMap(java.lang.Object 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

### 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

### m_comparator

    protected final java.util.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_aflProbability

    protected final float[] m_aflProbability

  The array of pre-computed probabilities 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_aNodeBuffer

    protected transient SafeSortedMap.SkipNode[] m_aNodeBuffer

  The scratch buffer used by mutation operations to store the search path to the insertion/deletion site.

### m_nSize

    protected int m_nSize

  The memoized size of the map. This is cached for efficiency.

### m_random

    protected java.util.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(java.util.Comparator comparator)

  Construct a new SafeSortedMap with the specified Comparator.

  Parameters:
    `comparator` - the comparator used to sort this map

### SafeSortedMap

    public SafeSortedMap(java.util.Comparator comparator,
                         int nSpan,
                         int nLevelMax)

  Construct a new SafeSortedMap with the specified parameters.

  Parameters:
    `comparator` - the comparator used to sort this map
    `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 `java.util.Map`
  Overrides:
    `size` in class `java.util.AbstractMap`

### containsKey

    public boolean containsKey(java.lang.Object oKey)

  Specified by:
    `containsKey` in interface `java.util.Map`
  Overrides:
    `containsKey` in class `java.util.AbstractMap`

### entrySet

    public java.util.Set entrySet()

  Specified by:
    `entrySet` in interface `java.util.Map`
  Specified by:
    `entrySet` in class `java.util.AbstractMap`

### put

    public java.lang.Object put(java.lang.Object oKey,
                                java.lang.Object oValue)

  Specified by:
    `put` in interface `java.util.Map`
  Overrides:
    `put` in class `java.util.AbstractMap`

### get

    public java.lang.Object get(java.lang.Object oKey)

  Specified by:
    `get` in interface `java.util.Map`
  Overrides:
    `get` in class `java.util.AbstractMap`

### getEntry

    public java.util.Map.Entry getEntry(java.lang.Object key)

  Locate an Entry in the this map based on its key.

  Parameters:
    `key` - the key object to search for
  Returns:
    the Entry or null if the entry does not exist

### remove

    public java.lang.Object remove(java.lang.Object oKey)

  Specified by:
    `remove` in interface `java.util.Map`
  Overrides:
    `remove` in class `java.util.AbstractMap`

### clear

    public void clear()

  Specified by:
    `clear` in interface `java.util.Map`
  Overrides:
    `clear` in class `java.util.AbstractMap`

### comparator

    public java.util.Comparator comparator()

  Specified by:
    `comparator` in interface `java.util.SortedMap`

### subMap

    public java.util.SortedMap subMap(java.lang.Object fromKey,
                                      java.lang.Object toKey)

  Specified by:
    `subMap` in interface `java.util.SortedMap`

### headMap

    public java.util.SortedMap headMap(java.lang.Object toKey)

  Specified by:
    `headMap` in interface `java.util.SortedMap`

### tailMap

    public java.util.SortedMap tailMap(java.lang.Object fromKey)

  Specified by:
    `tailMap` in interface `java.util.SortedMap`

### firstKey

    public java.lang.Object firstKey()

  Specified by:
    `firstKey` in interface `java.util.SortedMap`

### lastKey

    public java.lang.Object lastKey()

  Specified by:
    `lastKey` in interface `java.util.SortedMap`

### getViewMap

    protected SafeSortedMap.ViewMap getViewMap()

  Return a view of the entire map.

  Returns:
    a view of the entire map

### setSize

    protected void setSize(int nSize)

  Set the size of this map (cached to make the size() operation less expensive, since we already synchronize on all updates).

  Note: caller must hold synchronization on the map

  Parameters:
    `nSize` - the new size of the map

### getProbabilities

    protected float[] getProbabilities()

  Return the precomputed array of probability values used by this map to determine what index levels to build.

  Returns:
    the precomputed array of probability values
  See Also:
    `calculateRandomLevel()`

### getRandom

    protected java.util.Random getRandom()

  Return the random number generator for this map.

  Returns:
    the random number generator for this map

### getLevel

    protected int getLevel()

  Return the current maximum level of this map's index (the highest level that any key has built an index node for).

  Returns:
    the current maximum level this map's index

### 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

### 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.

  Note: caller must hold synchronization on the map

  Parameters:
    `nodeTop` - the new top index node

### getSearchBuffer

    protected SafeSortedMap.SkipNode[] getSearchBuffer()

  Return the buffer used to hold the search path for insertion/deletion operations.

  Returns:
    the search path buffer

### setSearchBuffer

    protected void setSearchBuffer(SafeSortedMap.SkipNode[] aNodeBuffer)

  Set the buffer used to hold the search path for insertion/deletion operations.

  Note: caller must hold synchronization on the map

  Parameters:
    `aNodeBuffer` - the new search path buffer

### insertNode

    protected boolean insertNode(java.lang.Object oKey,
                                 java.lang.Object oValue)

  Insert a new EntryNode and (possibly) SkipNode(s) for the specified key and value in this skip-list, 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:
    `oKey` - the key to insert
    `oValue` - the value to insert
  Returns:
    true if the key was successfully inserted, false otherwise

### deleteNode

    protected java.lang.Object deleteNode(SafeSortedMap.EntryNode node)

  Delete the specified node, as well any associated index nodes. Return the previous value associated with the node, or null if the node was already removed by an intervening thread.

  Returns:
    the previous value associated with the node, or null

### findOnSameLevel

    protected SafeSortedMap.SkipNode findOnSameLevel(SafeSortedMap.SkipNode nodeStart,
                                                     java.lang.Object oKey,
                                                     int nMode)

  Find the closest SkipNode (according to the specified search mode) to the specified key, starting from the specified SkipNode.

  Note: SEARCH_GT* modes that exhaust the level, return null while SEARCH_LT* modes may return the synthetic IndexNode.

  Note: this method does not synchronize internally, so it is possible that the returned node has been or will be deleted from the map.

  Parameters:
    `nodeStart` - the SkipNode to start searching from
    `oKey` - the key to search for
    `nMode` - one of the SEARCH_* constants
  Returns:
    the SkipNode that matches the key most closely, or null

### findKey

    protected SafeSortedMap.EntryNode findKey(java.lang.Object oKey)

  Return the EntryNode for the specified key if it is contained in this map, or null otherwise.

  Parameters:
    `oKey` - the key to search for
  Returns:
    the EntryNode for the specified key, or null if the key is not found

### findNearest

    protected SafeSortedMap.SkipNode findNearest(java.lang.Object oKey,
                                                 int nMode)

  Return the SkipNode closest to the specified key, or null.

  Parameters:
    `oKey` - the key to search for
    `nMode` - one of the SEARCH_* constants
  Returns:
    the SkipNode closest to the specified key, or null

### findNearestPath

    protected SafeSortedMap.SkipNode[] findNearestPath(java.lang.Object oKey,
                                                       int nMode)

  Return the search/index path to the node closest to the specified key.

  Note: the caller must hold synchronization on the map.

  Parameters:
    `oKey` - the key to search for
    `nMode` - one of the SEARCH_* constants
  Returns:
    the search/index path to the node closest to the specified key

### findNearestPath

    protected SafeSortedMap.SkipNode[] findNearestPath(java.lang.Object oKey,
                                                       int nMode,
                                                       SafeSortedMap.SkipNode[] aNodePath)

  Return the search/index path to the node closest to the specified key.

  Parameters:
    `oKey` - the key to search for
    `nMode` - one of the SEARCH_* constants
    `aNodePath` - the array into which the search path will be stored if it is the correct size; otherwise a new array will be allocated
  Returns:
    the search/index path to the node closest to the specified key

### search

    protected SafeSortedMap.SkipNode search(java.lang.Object oKey,
                                            int nMode,
                                            SafeSortedMap.IndexNode nodeTop,
                                            SafeSortedMap.SkipNode[] aNodePath)

  Return the search/index path to the node closest to the specified key.

  Parameters:
    `oKey` - the key to search for
    `nMode` - one of the SEARCH_* constants
    `nodeTop` - the top index node to start searching from
    `aNodePath` - the search/index path recorded by the search to the node closest to the specified key, according to the specified search mode. May be null.
  Returns:
    the IndexNode or EntryNode at level 0, closest to the specified key, according to the specified search mode

### 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 and p(0)=1/span.

  Returns:
    a random level number between 0 and `MAX_LEVEL`

### dump

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

Overview | Package | Class | Tree | Index | Help

Oracle® Coherence Java API Reference
v3.5.3
E15583-01
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2000, 2010, Oracle. All rights reserved.