org.gridgain.grid.util.offheap.unsafe

Class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer>

java.lang.Object

java.util.AbstractMap<K,V>

org.gridgain.grid.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.

Author:

Nathan Bronson

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>

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
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

Constructor Detail

GridOffHeapSnapTreeMap

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

Parameters:

keyFactory - Key factory.

valFactory - Value factory.

mem - Unsafe memory.

GridOffHeapSnapTreeMap

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

Parameters:

keyFactory - Key factory.

valFactory - Value factory.

mem - Unsafe memory.

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>