Skip navigation links

Overview | Package | Class | Tree | Index | Help
| Oracle® Coherence Java API Reference Release 3.6.1.0 E18814-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. 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.

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)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 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
`java.util.Map.Entry`

Field Summary
`protected static java.lang.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 java.util.concurrent.atomic.AtomicReferenceFieldUpdater` | `m_atomicUpdaterTopNode` AtomicUpdater for the casTopNode operation.
`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_nSpan` The span of the map.
`protected java.util.Random` | `m_random` The random-number generator for the map.
`protected static java.lang.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(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)^(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).
`java.util.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(java.lang.Object oKey)` Returns `true` if this map contains a mapping for the specified key.
`java.lang.String` | `dump()` Return a human-readable description of this map's internal state.
`java.util.Set` | `entrySet()` Returns a set view of the mappings contained in this map.
`protected SafeSortedMap.EntryNode` | `findNearest(SafeSortedMap.IndexNode nodeTop, java.lang.Object oKey, int nMode, boolean fFixLinks)` Return the SkipNode closest to the specified key, or null.
`protected SafeSortedMap.EntryNode` | `findNearestIndexedEntry(SafeSortedMap.IndexNode nodeTop, java.lang.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, java.lang.Object oKey)` Return an EntryNode that compares strictly less than the specified key, or the synthetic base node if there is none.
`java.lang.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.
`java.lang.Object` | `get(java.lang.Object oKey)` Returns the value to which this map maps the specified key.
`protected SafeSortedMap.BaseEntryNode` | `getBaseNode()` Return the base entry node.
`java.util.Map.Entry` | `getEntry(java.lang.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 java.util.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.
`java.util.SortedMap` | `headMap(java.lang.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.
`java.lang.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.
`java.lang.Object` | `put(java.lang.Object oKey, java.lang.Object oValue)` Associates the specified value with the specified key in this map (optional operation).
`java.lang.Object` | `remove(java.lang.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(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)` Returns a view of the portion of this sorted map whose keys range from `fromKey`, inclusive, to `toKey`, exclusive.
`java.util.SortedMap` | `tailMap(java.lang.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

### 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 java.lang.Object NO_VALUE

  Placeholder for a non-existent (deleted) value.

### BASE_VALUE

    protected static final java.lang.Object BASE_VALUE

  Placeholder for a non-existent (deleted) value.

### m_atomicUpdaterTopNode

    protected static final java.util.concurrent.atomic.AtomicReferenceFieldUpdater m_atomicUpdaterTopNode

  AtomicUpdater for the casTopNode operation.

### 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_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 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, 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()

  Returns the number of key-value mappings in this map. If the map contains more than `Integer.MAX_VALUE` elements, returns `Integer.MAX_VALUE`.

  This implementation returns `entrySet().size()`.

  Specified by:
    `size` in interface `java.util.Map`
  Overrides:
    `size` in class `java.util.AbstractMap`
  Returns:
    the number of key-value mappings in this map.

### containsKey

    public boolean containsKey(java.lang.Object oKey)

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

  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.

  Specified by:
    `containsKey` in interface `java.util.Map`
  Overrides:
    `containsKey` in class `java.util.AbstractMap`
  Parameters:
    `oKey` - key whose presence in this map is to be tested.
  Returns:
    `true` if this map contains a mapping for the specified key.

### entrySet

    public java.util.Set entrySet()

  Returns a set view of the mappings contained in this map. Each element in this set is a Map.Entry. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. (If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.) The set supports element removal, which removes the corresponding entry from the map, via the `Iterator.remove`, `Set.remove`, `removeAll`, `retainAll` and `clear` operations. It does not support the `add` or `addAll` operations.
  Specified by:
    `entrySet` in interface `java.util.Map`
  Specified by:
    `entrySet` in class `java.util.AbstractMap`
  Returns:
    a set view of the mappings contained in this map.

### put

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

  Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for this key, the old value is replaced.

  This implementation always throws an `UnsupportedOperationException`.

  Specified by:
    `put` in interface `java.util.Map`
  Overrides:
    `put` in class `java.util.AbstractMap`
  Parameters:
    `oKey` - key with which the specified value is to be associated.
    `oValue` - value to be associated with the specified key.
  Returns:
    previous value associated with specified key, or `null` if there was no mapping for key. (A `null` return can also indicate that the map previously associated `null` with the specified key, if the implementation supports `null` values.)

### get

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

  Returns the value to which this map maps the specified key. Returns `null` if the map contains no mapping for this key. A return value of `null` does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to `null`. The containsKey operation may be used to distinguish these two cases.

  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.

  Specified by:
    `get` in interface `java.util.Map`
  Overrides:
    `get` in class `java.util.AbstractMap`
  Parameters:
    `oKey` - key whose associated value is to be returned.
  Returns:
    the value to which this map maps the specified key.
  See Also:
    `AbstractMap.containsKey(Object)`

### getEntry

    public java.util.Map.Entry getEntry(java.lang.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 java.lang.Object remove(java.lang.Object oKey)

  Removes the mapping for this key from this map if present (optional operation).

  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.

  Specified by:
    `remove` in interface `java.util.Map`
  Overrides:
    `remove` in class `java.util.AbstractMap`
  Parameters:
    `oKey` - key whose mapping is to be removed from the map.
  Returns:
    previous value associated with specified key, or `null` if there was no entry for key. (A `null` return can also indicate that the map previously associated `null` with the specified key, if the implementation supports `null` values.)

### clear

    public void clear()

  Removes all mappings from this map (optional operation).

  This implementation calls `entrySet().clear()`. Note that this implementation throws an `UnsupportedOperationException` if the `entrySet` does not support the `clear` operation.

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

### comparator

    public java.util.Comparator comparator()

  Returns the comparator associated with this sorted map, or `null` if it uses its keys' natural ordering.
  Specified by:
    `comparator` in interface `java.util.SortedMap`
  Returns:
    the comparator associated with this sorted map, or `null` if it uses its keys' natural ordering.

### subMap

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

  Returns a view of the portion of this sorted 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 sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The returned Map supports all optional map operations that this sorted map supports.

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

  Specified by:
    `subMap` in interface `java.util.SortedMap`
  Parameters:
    `fromKey` - low endpoint (inclusive) of the subMap.
    `toKey` - high endpoint (exclusive) of the subMap.
  Returns:
    a view of the specified range within this sorted map.

### headMap

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

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

  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");

  Specified by:
    `headMap` in interface `java.util.SortedMap`
  Parameters:
    `toKey` - high endpoint (exclusive) of the subMap.
  Returns:
    a view of the specified initial range of this sorted map.

### tailMap

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

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

  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");

  Specified by:
    `tailMap` in interface `java.util.SortedMap`
  Parameters:
    `fromKey` - low endpoint (inclusive) of the tailMap.
  Returns:
    a view of the specified final range of this sorted map.

### firstKey

    public java.lang.Object firstKey()

  Returns the first (lowest) key currently in this sorted map.
  Specified by:
    `firstKey` in interface `java.util.SortedMap`
  Returns:
    the first (lowest) key currently in this sorted map.

### lastKey

    public java.lang.Object lastKey()

  Returns the last (highest) key currently in this sorted map.
  Specified by:
    `lastKey` in interface `java.util.SortedMap`
  Returns:
    the last (highest) key currently in this sorted map.

### 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 java.util.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,
                                                  java.lang.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,
                                                      java.lang.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,
                                                              java.lang.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]<i/> &lteq; v < threshold[l-1]<i/>
  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 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

Skip navigation links

Overview | Package | Class | Tree | Index | Help
| Oracle® Coherence Java API Reference Release 3.6.1.0 E18814-01
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2000, 2010, Oracle and/or its affiliates. All rights reserved.