org.apache.ignite.internal.util.snaptree

## Class SnapTreeMap<K,V>

- java.lang.Object
- - java.util.AbstractMap<K,V>
  - - org.apache.ignite.internal.util.snaptree.SnapTreeMap<K,V>

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

    public class SnapTreeMap<K,V>
    extends AbstractMap<K,V>
    implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable

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.

See Also:
  Serialized Form

### Nested Class Summary

Nested Classes
`protected static class` `SnapTreeMap.Node<K,V>`

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

### Constructor Summary

Constructors
Constructor and Description
`SnapTreeMap()`
`SnapTreeMap(Comparator<? super K> comparator)`
`SnapTreeMap(Map<? extends K,? extends V> source)`
`SnapTreeMap(SortedMap<K,? extends V> source)`

### Method Summary

All Methods Instance Methods Concrete Methods
`protected void` `afterNodeUpdate_nl(SnapTreeMap.Node<K,V> node, Object val)`
`Map.Entry<K,V>` `ceilingEntry(K key)`
`K` `ceilingKey(K key)`
`void` `clear()`
`SnapTreeMap<K,V>` `clone()`
`protected Comparable<? super K>` `comparable(Object key)`
`Comparator<? super K>` `comparator()`
`boolean` `containsKey(Object key)`
`boolean` `containsValue(Object value)`
`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()`
`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)`
`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

`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.concurrent.ConcurrentMap

`compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll`

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

`values`

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

`equals, hashCode, putAll`

### Constructor Detail

#### SnapTreeMap

    public SnapTreeMap()

#### SnapTreeMap

    public SnapTreeMap(Comparator<? super K> comparator)

#### SnapTreeMap

    public SnapTreeMap(Map<? extends K,? extends V> source)

#### SnapTreeMap

    public SnapTreeMap(SortedMap<K,? extends V> source)

### Method Detail

#### clone

    public SnapTreeMap<K,V> clone()

Overrides:
  `clone` in class `AbstractMap<K,V>`

#### size

    public int size()

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

#### isEmpty

    public boolean isEmpty()

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

#### clear

    public void clear()

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

#### comparator

    public Comparator<? super K> comparator()

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

#### containsValue

    public boolean containsValue(Object value)

Specified by:
  `containsValue` in interface `Map<K,V>`
Overrides:
  `containsValue` in class `AbstractMap<K,V>`

#### containsKey

    public boolean containsKey(Object key)

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

#### get

    public V get(Object key)

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

#### comparable

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

#### firstKey

    public K firstKey()

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

#### firstEntry

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

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

#### lastKey

    public K lastKey()

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

#### lastEntry

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

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

#### lowerKey

    public K lowerKey(K key)

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

#### floorKey

    public K floorKey(K key)

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

#### ceilingKey

    public K ceilingKey(K key)

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

#### higherKey

    public K higherKey(K key)

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

#### lowerEntry

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

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

#### floorEntry

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

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

#### ceilingEntry

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

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

#### higherEntry

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

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

#### put

    public V put(K key,
                 V value)

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

#### putIfAbsent

    public V putIfAbsent(K key,
                         V value)

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

#### replace

    public V replace(K key,
                     V value)

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

#### replace

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

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

#### remove

    public V remove(Object key)

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

#### remove

    public boolean remove(Object key,
                          Object value)

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

#### afterNodeUpdate_nl

    protected void afterNodeUpdate_nl(SnapTreeMap.Node<K,V> node,
                                      Object val)

#### pollFirstEntry

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

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

#### pollLastEntry

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

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

#### keySet

    public NavigableSet<K> keySet()

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

#### entrySet

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

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

#### navigableKeySet

    public NavigableSet<K> navigableKeySet()

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

#### descendingKeySet

    public NavigableSet<K> descendingKeySet()

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

#### subMap

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

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

#### headMap

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

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

#### tailMap

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

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

#### subMap

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

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

#### headMap

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

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

#### tailMap

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

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

#### descendingMap

    public ConcurrentNavigableMap<K,V> descendingMap()

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

2018 Copyright © Apache Software Foundation

Follow @ApacheIgnite

Ignite Fabric | : ver. 2.4.0
Release Date | : March 5 2018