org.apache.ignite.internal.util.offheap.unsafe

## Class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>

- java.lang.Object
- - java.util.AbstractMap<K,V>
  - - org.apache.ignite.internal.util.offheap.unsafe.GridOffHeapSnapTreeMap<K,V>

All Implemented Interfaces:
  Closeable, AutoCloseable, Cloneable, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

    public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>
    extends AbstractMap<K,V>
    implements ConcurrentNavigableMap<K,V>, Cloneable, Closeable

A concurrent AVL tree with fast cloning, based on the algorithm of Bronson, Casper, Chafi, and Olukotun, "A Practical Concurrent Binary Search Tree" published in PPoPP'10. To simplify the locking protocols rebalancing work is performed in pieces, and some removed keys are be retained as routing nodes in the tree.

This data structure honors all of the contracts of `ConcurrentSkipListMap`, with the additional contract that clone, size, toArray, and iteration are linearizable (atomic).

The tree uses optimistic concurrency control. No locks are usually required for get, containsKey, firstKey, firstEntry, lastKey, or lastEntry. Reads are not lock free (or even obstruction free), but obstructing threads perform no memory allocation, system calls, or loops, which seems to work okay in practice. All of the updates to the tree are performed in fixed- size blocks, so restoration of the AVL balance criteria may occur after a change to the tree has linearized (but before the mutating operation has returned). The tree is always properly balanced when quiescent.

To clone the tree (or produce a snapshot for consistent iteration) the root node is marked as shared, which must be (*) done while there are no pending mutations. New mutating operations are blocked if a mark is pending, and when existing mutating operations are completed the mark is made. * - It would be less disruptive if we immediately marked the root as shared, and then waited for pending operations that might not have seen the mark without blocking new mutations. This could result in imbalance being frozen into the shared portion of the tree, though. To minimize the problem we perform the mark and reenable mutation on whichever thread notices that the entry count has become zero, to reduce context switches on the critical path.

The same multi-cache line data structure required for efficiently tracking the entry and exit for mutating operations is used to maintain the current size of the tree. This means that the size can be computed by quiescing as for a clone, but without doing any marking.

Range queries such as higherKey are not amenable to the optimistic hand-over-hand locking scheme used for exact searches, so they are implemented with pessimistic concurrency control. Mutation can be considered to acquire a lock on the map in Intention-eXclusive mode, range queries, size(), and root marking acquire the lock in Shared mode.

### Nested Class Summary

### 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
`protected GridUnsafeGuard` `guard`
`protected GridUnsafeMemory` `mem`

### Constructor Summary

Constructors
Constructor and Description
`GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory, GridOffHeapSmartPointerFactory valFactory, GridUnsafeMemory mem, GridUnsafeGuard guard)`
`GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory, GridOffHeapSmartPointerFactory valFactory, GridUnsafeMemory mem, GridUnsafeGuard guard, Comparator<? super K> comparator)`

### Method Summary

Methods
`protected void` `afterNodeUpdate_nl(long node, V val)` Special protected method to be overridden by extending classes.
`Map.Entry<K,V>` `ceilingEntry(K key)`
`K` `ceilingKey(K key)`
`void` `clear()`
`GridOffHeapSnapTreeMap<K,V>` `clone()`
`void` `close()` Closes tree map and reclaims memory.
`protected Comparable<? super K>` `comparable(Object key)`
`Comparator<? super K>` `comparator()`
`boolean` `containsKey(Object key)`
`NavigableSet<K>` `descendingKeySet()`
`ConcurrentNavigableMap<K,V>` `descendingMap()`
`Set<Map.Entry<K,V>>` `entrySet()`
`Map.Entry<K,V>` `firstEntry()`
`K` `firstKey()`
`Map.Entry<K,V>` `floorEntry(K key)`
`K` `floorKey(K key)`
`V` `get(Object key)`
`ConcurrentNavigableMap<K,V>` `headMap(K toKey)`
`ConcurrentNavigableMap<K,V>` `headMap(K toKey, boolean inclusive)`
`Map.Entry<K,V>` `higherEntry(K key)`
`K` `higherKey(K key)`
`boolean` `isEmpty()`
`protected void` `key(long ptr, K key)`
`protected long` `keyPtr(long node)`
`NavigableSet<K>` `keySet()`
`Map.Entry<K,V>` `lastEntry()`
`K` `lastKey()`
`Map.Entry<K,V>` `lowerEntry(K key)`
`K` `lowerKey(K key)`
`NavigableSet<K>` `navigableKeySet()`
`Map.Entry<K,V>` `pollFirstEntry()`
`Map.Entry<K,V>` `pollLastEntry()`
`V` `put(K key, V value)`
`V` `putIfAbsent(K key, V value)`
`V` `remove(Object key)`
`boolean` `remove(Object key, Object value)`
`V` `replace(K key, V value)`
`boolean` `replace(K key, V oldValue, V newValue)`
`protected void` `right(long ptr, long nodePtr)`
`int` `size()`
`ConcurrentNavigableMap<K,V>` `subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)`
`ConcurrentNavigableMap<K,V>` `subMap(K fromKey, K toKey)`
`ConcurrentNavigableMap<K,V>` `tailMap(K fromKey)`
`ConcurrentNavigableMap<K,V>` `tailMap(K fromKey, boolean inclusive)`

### Methods inherited from class java.util.AbstractMap

`containsValue, equals, hashCode, putAll, toString, values`

### Methods inherited from class java.lang.Object

`finalize, getClass, notify, notifyAll, wait, wait, wait`

### Methods inherited from interface java.util.SortedMap

`values`

### Methods inherited from interface java.util.Map

`containsValue, equals, hashCode, putAll`

### Field Detail

#### mem

    protected final GridUnsafeMemory mem

#### guard

    protected final GridUnsafeGuard guard

### Constructor Detail

#### GridOffHeapSnapTreeMap

    public GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory,
                          GridOffHeapSmartPointerFactory valFactory,
                          GridUnsafeMemory mem,
                          GridUnsafeGuard guard)

Parameters:
  `keyFactory` - Key factory.
  `valFactory` - Value factory.
  `mem` - Unsafe memory.
  `guard` - Guard.

#### GridOffHeapSnapTreeMap

    public GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory,
                          GridOffHeapSmartPointerFactory valFactory,
                          GridUnsafeMemory mem,
                          GridUnsafeGuard guard,
                          Comparator<? super K> comparator)

Parameters:
  `keyFactory` - Key factory.
  `valFactory` - Value factory.
  `mem` - Unsafe memory.
  `guard` - Guard.
  `comparator` - Comparator.

### Method Detail

#### keyPtr

    protected long keyPtr(long node)

Parameters:
  `node` - Node.
Returns:
  Key pointer.

#### right

    protected void right(long ptr,
             long nodePtr)

Parameters:
  `ptr` - Node pointer.
  `nodePtr` - Right child's pointer.

#### key

    protected void key(long ptr,
           K key)

Parameters:
  `ptr` - Node pointer.
  `key` - Key.

#### close

    public void close()

Closes tree map and reclaims memory.

Specified by:
  `close` in interface `Closeable`
Specified by:
  `close` in interface `AutoCloseable`

#### clone

    public GridOffHeapSnapTreeMap<K,V> clone()

Overrides:
  `clone` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Returns:
  Clones this map and takes data snapshot.

#### size

    public int size()

Specified by:
  `size` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `size` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### isEmpty

    public boolean isEmpty()

Specified by:
  `isEmpty` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `isEmpty` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### clear

    public void clear()

Specified by:
  `clear` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `clear` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### comparator

    public Comparator<? super K> comparator()

Specified by:
  `comparator` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### containsKey

    public boolean containsKey(Object key)

Specified by:
  `containsKey` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `containsKey` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### get

    public V get(Object key)

Specified by:
  `get` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `get` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### comparable

    protected Comparable<? super K> comparable(Object key)

Parameters:
  `key` - Key.
Returns:
  Comparable over given key.

#### firstKey

    public K firstKey()

Specified by:
  `firstKey` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### firstEntry

    public Map.Entry<K,V> firstEntry()

Specified by:
  `firstEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### lastKey

    public K lastKey()

Specified by:
  `lastKey` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### lastEntry

    public Map.Entry<K,V> lastEntry()

Specified by:
  `lastEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### lowerKey

    public K lowerKey(K key)

Specified by:
  `lowerKey` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### floorKey

    public K floorKey(K key)

Specified by:
  `floorKey` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### ceilingKey

    public K ceilingKey(K key)

Specified by:
  `ceilingKey` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### higherKey

    public K higherKey(K key)

Specified by:
  `higherKey` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### lowerEntry

    public Map.Entry<K,V> lowerEntry(K key)

Specified by:
  `lowerEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### floorEntry

    public Map.Entry<K,V> floorEntry(K key)

Specified by:
  `floorEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### ceilingEntry

    public Map.Entry<K,V> ceilingEntry(K key)

Specified by:
  `ceilingEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### higherEntry

    public Map.Entry<K,V> higherEntry(K key)

Specified by:
  `higherEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### put

    public V put(K key,
        V value)

Specified by:
  `put` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `put` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### putIfAbsent

    public V putIfAbsent(K key,
                V value)

Specified by:
  `putIfAbsent` in interface `ConcurrentMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### replace

    public V replace(K key,
            V value)

Specified by:
  `replace` in interface `ConcurrentMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### replace

    public boolean replace(K key,
                  V oldValue,
                  V newValue)

Specified by:
  `replace` in interface `ConcurrentMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### remove

    public V remove(Object key)

Specified by:
  `remove` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `remove` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### remove

    public boolean remove(Object key,
                 Object value)

Specified by:
  `remove` in interface `ConcurrentMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### afterNodeUpdate_nl

    protected void afterNodeUpdate_nl(long node,
                          V val)

Special protected method to be overridden by extending classes.

Parameters:
  `node` - Node pointer.
  `val` - Value.

#### pollFirstEntry

    public Map.Entry<K,V> pollFirstEntry()

Specified by:
  `pollFirstEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### pollLastEntry

    public Map.Entry<K,V> pollLastEntry()

Specified by:
  `pollLastEntry` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### keySet

    public NavigableSet<K> keySet()

Specified by:
  `keySet` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `keySet` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `keySet` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Overrides:
  `keySet` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### entrySet

    public Set<Map.Entry<K,V>> entrySet()

Specified by:
  `entrySet` in interface `Map<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `entrySet` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `entrySet` in class `AbstractMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### navigableKeySet

    public NavigableSet<K> navigableKeySet()

Specified by:
  `navigableKeySet` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `navigableKeySet` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### descendingKeySet

    public NavigableSet<K> descendingKeySet()

Specified by:
  `descendingKeySet` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `descendingKeySet` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### subMap

    public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                     boolean fromInclusive,
                                     K toKey,
                                     boolean toInclusive)

Specified by:
  `subMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `subMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### headMap

    public ConcurrentNavigableMap<K,V> headMap(K toKey,
                                      boolean inclusive)

Specified by:
  `headMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `headMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### tailMap

    public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
                                      boolean inclusive)

Specified by:
  `tailMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `tailMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### subMap

    public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                     K toKey)

Specified by:
  `subMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `subMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `subMap` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### headMap

    public ConcurrentNavigableMap<K,V> headMap(K toKey)

Specified by:
  `headMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `headMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `headMap` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### tailMap

    public ConcurrentNavigableMap<K,V> tailMap(K fromKey)

Specified by:
  `tailMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `tailMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `tailMap` in interface `SortedMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

#### descendingMap

    public ConcurrentNavigableMap<K,V> descendingMap()

Specified by:
  `descendingMap` in interface `ConcurrentNavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`
Specified by:
  `descendingMap` in interface `NavigableMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>`

2015 Copyright © Apache Software Foundation

Follow @ApacheIgnite

Ignite Fabric | : ver. 1.4.0
Release Date | : September 24 2015