Package org.terracotta.offheapstore

Class OffHeapHashMap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this map
    V - the type of mapped values
    All Implemented Interfaces:
    java.util.concurrent.locks.ReadWriteLock, java.util.Map<K,​V>, HashingMap<K,​V>, MapInternals, StorageEngine.Owner
    Direct Known Subclasses:
    AbstractLockedOffHeapHashMap
    public class OffHeapHashMap<K,​V>
extends java.util.AbstractMap<K,​V>
implements MapInternals, StorageEngine.Owner, HashingMap<K,​V>
    A hash-table implementation whose table is stored in an NIO direct buffer.

    The map stores keys and values encoded as integers, in an open-addressed linear-reprobing hashtable. Entries are 16-bytes wide, and consist of:

    • int status marker
    • int cached key hashcode
    • long {key:value} representation
    Key and value representations are generated by the StorageEngine instance provided at construction time.

    This Map implementation is not thread-safe and does not support null keys or values.

    • Field Detail

      • LOGGER

        private static final org.slf4j.Logger LOGGER

      • TABLE_RESIZE_THRESHOLD

        private static final float TABLE_RESIZE_THRESHOLD
        See Also:
        Constant Field Values

      • TABLE_SHRINK_THRESHOLD

        private static final float TABLE_SHRINK_THRESHOLD
        See Also:
        Constant Field Values

      • INITIAL_REPROBE_LENGTH

        private static final int INITIAL_REPROBE_LENGTH
        See Also:
        Constant Field Values

      • REPROBE_WARNING_THRESHOLD

        private static final int REPROBE_WARNING_THRESHOLD
        See Also:
        Constant Field Values

      • ALLOCATE_ON_CLEAR_THRESHOLD_RATIO

        private static final int ALLOCATE_ON_CLEAR_THRESHOLD_RATIO
        See Also:
        Constant Field Values

      • DESTROYED_TABLE

        private static final java.nio.IntBuffer DESTROYED_TABLE

      • ENTRY_SIZE

        protected static final int ENTRY_SIZE
        Size of a table entry in primitive int units
        See Also:
        Constant Field Values

      • ENTRY_BIT_SHIFT

        protected static final int ENTRY_BIT_SHIFT

      • storageEngine

        protected final StorageEngine<? super K,​? super V> storageEngine

      • tableSource

        protected final PageSource tableSource

      • initialTableSize

        private final int initialTableSize

      • tableAllocationsSteal

        private final boolean tableAllocationsSteal

      • tableResizing

        private final java.lang.ThreadLocal<java.lang.Boolean> tableResizing

      • size

        protected volatile int size

      • modCount

        protected volatile int modCount

      • reprobeLimit

        protected int reprobeLimit

      • currentTableShrinkThreshold

        private float currentTableShrinkThreshold

      • hasUsedIterators

        private volatile boolean hasUsedIterators

      • hashtable

        protected volatile java.nio.IntBuffer hashtable
        The current hash-table.

        A list of: int[] {status, hashCode, encoding-high, encoding-low}

      • hashTablePage

        protected volatile Page hashTablePage

      • entrySet

        private java.util.Set<java.util.Map.Entry<K,​V>> entrySet

      • keySet

        private java.util.Set<K> keySet

      • encodingSet

        private java.util.Set<java.lang.Long> encodingSet

      • removedSlots

        protected volatile int removedSlots

    • Constructor Detail

      • OffHeapHashMap

        public OffHeapHashMap​(PageSource source,
                      StorageEngine<? super K,​? super V> storageEngine)
        Construct an instance using a custom BufferSource for the hashtable.
        Parameters:
        source - source for the hashtable allocations
        storageEngine - engine used to encode the keys and values

      • OffHeapHashMap

        public OffHeapHashMap​(PageSource source,
                      boolean tableAllocationsSteal,
                      StorageEngine<? super K,​? super V> storageEngine)

      • OffHeapHashMap

        public OffHeapHashMap​(PageSource source,
                      StorageEngine<? super K,​? super V> storageEngine,
                      boolean bootstrap)

      • OffHeapHashMap

        public OffHeapHashMap​(PageSource source,
                      StorageEngine<? super K,​? super V> storageEngine,
                      int tableSize)
        Construct an instance using a custom BufferSource for the hashtable and a custom initial table size.
        Parameters:
        source - source for the hashtable allocations
        storageEngine - engine used to encode the keys and values
        tableSize - the initial table size

      • OffHeapHashMap

        public OffHeapHashMap​(PageSource source,
                      boolean tableAllocationsSteal,
                      StorageEngine<? super K,​? super V> storageEngine,
                      int tableSize)

      • OffHeapHashMap

        protected OffHeapHashMap​(PageSource source,
                         boolean tableAllocationsSteal,
                         StorageEngine<? super K,​? super V> storageEngine,
                         int tableSize,
                         boolean bootstrap)

    • Method Detail

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>

      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>

      • installMappingForHashAndEncoding

        public long installMappingForHashAndEncoding​(int pojoHash,
                                             java.nio.ByteBuffer offheapBinaryKey,
                                             java.nio.ByteBuffer offheapBinaryValue,
                                             int metadata)
        Specified by:
        installMappingForHashAndEncoding in interface StorageEngine.Owner

      • getMetadata

        public java.lang.Integer getMetadata​(java.lang.Object key,
                                     int mask)

      • getAndSetMetadata

        public java.lang.Integer getAndSetMetadata​(java.lang.Object key,
                                           int mask,
                                           int values)

      • getValueAndSetMetadata

        public V getValueAndSetMetadata​(java.lang.Object key,
                                int mask,
                                int values)

      • put

        public V put​(K key,
             V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>

      • put

        public V put​(K key,
             V value,
             int metadata)

      • fill

        public V fill​(K key,
              V value)
        Associates the specified value with the specified key in this map. If the map does not contain a mapping for the key, the new mapping is only installed if there is room. If the map previously contained a mapping for the key, the old value is replaced by the specified value even if this results in a failure or eviction.
        Parameters:
        key - key with which the specified value is to be associated
        value - value to be associated with the specified key
        Returns:
        the previous value associated with key, or null if there was no mapping for key (irrespective of whether the value was successfully installed).

      • fill

        public V fill​(K key,
              V value,
              int metadata)

      • fill

        protected final V fill​(K key,
                       V value,
                       int hash,
                       int[] newEntry,
                       int metadata)

      • writeEntry

        private int[] writeEntry​(K key,
                         int hash,
                         V value,
                         int metadata)

      • tryWriteEntry

        private int[] tryWriteEntry​(K key,
                            int hash,
                            V value,
                            int metadata)

      • installEntry

        private int[] installEntry​(java.nio.ByteBuffer offheapBinaryKey,
                           int pojoHash,
                           java.nio.ByteBuffer offheapBinaryValue,
                           int metadata)

      • tryInstallEntry

        private int[] tryInstallEntry​(java.nio.ByteBuffer offheapBinaryKey,
                              int pojoHash,
                              java.nio.ByteBuffer offheapBinaryValue,
                              int metadata)

      • createEntry

        private static int[] createEntry​(int hash,
                                 long encoding,
                                 int metadata)

      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>

      • removeAllWithHash

        public java.util.Map<K,​V> removeAllWithHash​(int hash)
        Description copied from interface: HashingMap
        Remove all keys having a specific hashcode.
        Specified by:
        removeAllWithHash in interface HashingMap<K,​V>
        Parameters:
        hash - the hashcode of the keys to be removed.
        Returns:
        a Map containing the removed mappings.

      • removeNoReturn

        public boolean removeNoReturn​(java.lang.Object key)

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>

      • destroy

        public void destroy()

      • allocateOrClearTable

        private void allocateOrClearTable​(int size)

      • entrySet

        public final java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>

      • keySet

        public final java.util.Set<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>

      • createEntrySet

        protected java.util.Set<java.util.Map.Entry<K,​V>> createEntrySet()

      • createEncodingSet

        protected java.util.Set<java.lang.Long> createEncodingSet()

      • createKeySet

        protected java.util.Set<K> createKeySet()

      • isPresent

        protected static boolean isPresent​(java.nio.IntBuffer entry)

      • isAvailable

        protected static boolean isAvailable​(java.nio.IntBuffer entry)

      • isTerminating

        protected static boolean isTerminating​(java.nio.IntBuffer entry)

      • isTerminating

        protected static boolean isTerminating​(int entryStatus)

      • isRemoved

        protected static boolean isRemoved​(java.nio.IntBuffer entry)

      • isRemoved

        protected static boolean isRemoved​(int entryStatus)

      • readLong

        protected static long readLong​(int[] array,
                               int offset)

      • readLong

        protected static long readLong​(java.nio.IntBuffer entry,
                               int offset)

      • indexFor

        protected int indexFor​(int hash)

      • indexFor

        protected static int indexFor​(int hash,
                              java.nio.IntBuffer table)

      • keyEquals

        private boolean keyEquals​(java.lang.Object probeKey,
                          int probeHash,
                          long targetEncoding,
                          int targetHash)

      • binaryKeyEquals

        private boolean binaryKeyEquals​(java.nio.ByteBuffer binaryProbeKey,
                                int probeHash,
                                long targetEncoding,
                                int targetHash)

      • expand

        private void expand​(int start,
                    int length)

      • tryExpand

        private boolean tryExpand()

      • tryExpandTable

        private boolean tryExpandTable()

      • expandTable

        private Page expandTable​(int scale)

      • tryIncreaseReprobe

        protected boolean tryIncreaseReprobe()

      • shrinkTable

        protected void shrinkTable()

      • shrink

        private void shrink()

      • shrinkTableImpl

        private void shrinkTableImpl()

      • shrinkTableImpl

        private Page shrinkTableImpl​(int scale)

      • writeEntry

        private boolean writeEntry​(java.nio.IntBuffer table,
                           java.nio.IntBuffer entry)

      • spread

        protected static int spread​(int hash)

      • allocateTable

        private Page allocateTable​(int size)

      • freeTable

        private void freeTable​(Page tablePage,
                       java.nio.IntBuffer table,
                       int finalReprobe)

      • freeTable

        private void freeTable​(Page tablePage)

      • reprobeLimit

        private int reprobeLimit()

      • freePendingTables

        protected void freePendingTables()

      • updatePendingTables

        private void updatePendingTables​(int hash,
                                 long oldEncoding,
                                 java.nio.IntBuffer newEntry)

      • wipePendingTables

        private void wipePendingTables()

      • removeMapping

        protected boolean removeMapping​(java.lang.Object o)

      • removeAtTableOffset

        protected void removeAtTableOffset​(int offset,
                                   boolean shrink)

      • getAtTableOffset

        protected V getAtTableOffset​(int offset)

      • getEntryAtTableOffset

        protected java.util.Map.Entry<K,​V> getEntryAtTableOffset​(int offset)

      • updateEncoding

        public boolean updateEncoding​(int hash,
                              long oldEncoding,
                              long newEncoding,
                              long mask)
        Specified by:
        updateEncoding in interface StorageEngine.Owner

      • updateEncodingInTable

        private static boolean updateEncodingInTable​(java.nio.IntBuffer table,
                                             int limit,
                                             int hash,
                                             long oldEncoding,
                                             long newEncoding,
                                             long mask)

      • slotRemoved

        private void slotRemoved​(int position,
                         java.nio.IntBuffer entry)

      • slotAdded

        private void slotAdded​(int position,
                       java.nio.IntBuffer entry)

      • slotUpdated

        private void slotUpdated​(int position,
                         java.nio.IntBuffer entry,
                         long oldEncoding)

      • added

        protected void added​(int position,
                     java.nio.IntBuffer entry)

      • hit

        protected void hit​(int position,
                   java.nio.IntBuffer entry)

      • removed

        protected void removed​(int position,
                       java.nio.IntBuffer entry)

      • updated

        protected void updated​(int position,
                       java.nio.IntBuffer entry)

      • tableExpansionFailure

        protected void tableExpansionFailure​(int start,
                                     int length)

      • storageEngineFailure

        protected void storageEngineFailure​(java.lang.Object failure)

      • readLock

        public java.util.concurrent.locks.Lock readLock()
        Specified by:
        readLock in interface java.util.concurrent.locks.ReadWriteLock

      • writeLock

        public java.util.concurrent.locks.Lock writeLock()
        Specified by:
        writeLock in interface java.util.concurrent.locks.ReadWriteLock

      • getStorageEngine

        public StorageEngine<? super K,​? super V> getStorageEngine()

      • computeIfAbsentWithMetadata

        public MetadataTuple<V> computeIfAbsentWithMetadata​(K key,
                                                    java.util.function.Function<? super K,​? extends MetadataTuple<V>> mappingFunction)