Class OffHeapHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
org.terracotta.offheapstore.OffHeapHashMap<K,V>
Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values
All Implemented Interfaces:
ReadWriteLock, Map<K,V>, HashingMap<K,V>, MapInternals, StorageEngine.Owner
Direct Known Subclasses:
AbstractLockedOffHeapHashMap
public class OffHeapHashMap<K,V> extends 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 Details

    • LOGGER

      private static final org.slf4j.Logger LOGGER

    • INITIAL_TABLE_SIZE

      private static final int INITIAL_TABLE_SIZE
      See Also:

    • TABLE_RESIZE_THRESHOLD

      private static final float TABLE_RESIZE_THRESHOLD
      See Also:

    • TABLE_SHRINK_THRESHOLD

      private static final float TABLE_SHRINK_THRESHOLD
      See Also:

    • INITIAL_REPROBE_LENGTH

      private static final int INITIAL_REPROBE_LENGTH
      See Also:

    • REPROBE_WARNING_THRESHOLD

      private static final int REPROBE_WARNING_THRESHOLD
      See Also:

    • ALLOCATE_ON_CLEAR_THRESHOLD_RATIO

      private static final int ALLOCATE_ON_CLEAR_THRESHOLD_RATIO
      See Also:

    • DESTROYED_TABLE

      private static final IntBuffer DESTROYED_TABLE

    • ENTRY_SIZE

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

    • ENTRY_BIT_SHIFT

      protected static final int ENTRY_BIT_SHIFT

    • STATUS

      protected static final int STATUS
      See Also:

    • KEY_HASHCODE

      protected static final int KEY_HASHCODE
      See Also:

    • ENCODING

      protected static final int ENCODING
      See Also:

    • STATUS_USED

      protected static final int STATUS_USED
      See Also:

    • STATUS_REMOVED

      protected static final int STATUS_REMOVED
      See Also:

    • RESERVED_STATUS_BITS

      public static final int RESERVED_STATUS_BITS
      See Also:

    • storageEngine

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

    • tableSource

      protected final PageSource tableSource

    • pendingTableFrees

      private final WeakIdentityHashMap<IntBuffer, OffHeapHashMap.PendingPage> pendingTableFrees

    • initialTableSize

      private final int initialTableSize

    • tableAllocationsSteal

      private final boolean tableAllocationsSteal

    • tableResizing

      private final ThreadLocal<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 IntBuffer hashtable
      The current hash-table.

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

    • hashTablePage

      protected volatile Page hashTablePage

    • entrySet

      private Set<Map.Entry<K,V>> entrySet

    • keySet

      private Set<K> keySet

    • encodingSet

      private Set<Long> encodingSet

    • removedSlots

      protected volatile int removedSlots

  • Constructor Details

    • 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 Details

    • size

      public int size()
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size 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>

    • getEncodingForHashAndBinary

      public Long getEncodingForHashAndBinary(int hash, ByteBuffer binaryKey)
      Specified by:
      getEncodingForHashAndBinary in interface StorageEngine.Owner

    • installMappingForHashAndEncoding

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

    • getMetadata

      public Integer getMetadata(Object key, int mask)

    • getAndSetMetadata

      public Integer getAndSetMetadata(Object key, int mask, int values)

    • getValueAndSetMetadata

      public V getValueAndSetMetadata(Object key, int mask, int values)

    • put

      public V put(K key, V value)
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class 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(ByteBuffer offheapBinaryKey, int pojoHash, ByteBuffer offheapBinaryValue, int metadata)

    • tryInstallEntry

      private int[] tryInstallEntry(ByteBuffer offheapBinaryKey, int pojoHash, ByteBuffer offheapBinaryValue, int metadata)

    • createEntry

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

    • remove

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

    • removeAllWithHash

      public 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(Object key)

    • clear

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

    • destroy

      public void destroy()

    • allocateOrClearTable

      private void allocateOrClearTable(int size)

    • entrySet

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

    • encodingSet

      public final Set<Long> encodingSet()
      Specified by:
      encodingSet in interface StorageEngine.Owner

    • keySet

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

    • createEntrySet

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

    • createEncodingSet

      protected Set<Long> createEncodingSet()

    • createKeySet

      protected Set<K> createKeySet()

    • isPresent

      protected static boolean isPresent(IntBuffer entry)

    • isAvailable

      protected static boolean isAvailable(IntBuffer entry)

    • isTerminating

      protected static boolean isTerminating(IntBuffer entry)

    • isTerminating

      protected static boolean isTerminating(int entryStatus)

    • isRemoved

      protected static boolean isRemoved(IntBuffer entry)

    • isRemoved

      protected static boolean isRemoved(int entryStatus)

    • readLong

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

    • readLong

      protected static long readLong(IntBuffer entry, int offset)

    • indexFor

      protected int indexFor(int hash)

    • indexFor

      protected static int indexFor(int hash, IntBuffer table)

    • keyEquals

      private boolean keyEquals(Object probeKey, int probeHash, long targetEncoding, int targetHash)

    • binaryKeyEquals

      private boolean binaryKeyEquals(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(IntBuffer table, IntBuffer entry)

    • spread

      protected static int spread(int hash)

    • allocateTable

      private Page allocateTable(int size)

    • freeTable

      private void freeTable(Page tablePage, 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, IntBuffer newEntry)

    • wipePendingTables

      private void wipePendingTables()

    • removeMapping

      protected boolean removeMapping(Object o)

    • evict

      public boolean evict(int index, boolean shrink)
      Specified by:
      evict in interface StorageEngine.Owner

    • removeAtTableOffset

      protected void removeAtTableOffset(int offset, boolean shrink)

    • getAtTableOffset

      protected V getAtTableOffset(int offset)

    • getEntryAtTableOffset

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

    • getSlotForHashAndEncoding

      public Integer getSlotForHashAndEncoding(int hash, long encoding, long mask)
      Specified by:
      getSlotForHashAndEncoding in interface StorageEngine.Owner

    • updateEncoding

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

    • updateEncodingInTable

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

    • slotRemoved

      private void slotRemoved(int position, IntBuffer entry)

    • slotAdded

      private void slotAdded(int position, IntBuffer entry)

    • slotUpdated

      private void slotUpdated(int position, IntBuffer entry, long oldEncoding)

    • added

      protected void added(int position, IntBuffer entry)

    • hit

      protected void hit(int position, IntBuffer entry)

    • removed

      protected void removed(int position, IntBuffer entry)

    • updated

      protected void updated(int position, IntBuffer entry)

    • tableExpansionFailure

      protected void tableExpansionFailure(int start, int length)

    • storageEngineFailure

      protected void storageEngineFailure(Object failure)

    • getSize

      public long getSize()
      Specified by:
      getSize in interface MapInternals
      Specified by:
      getSize in interface StorageEngine.Owner

    • getTableCapacity

      public long getTableCapacity()
      Specified by:
      getTableCapacity in interface MapInternals

    • getUsedSlotCount

      public long getUsedSlotCount()
      Specified by:
      getUsedSlotCount in interface MapInternals

    • getRemovedSlotCount

      public long getRemovedSlotCount()
      Specified by:
      getRemovedSlotCount in interface MapInternals

    • getReprobeLength

      public int getReprobeLength()
      Specified by:
      getReprobeLength in interface MapInternals

    • getAllocatedMemory

      public long getAllocatedMemory()
      Specified by:
      getAllocatedMemory in interface MapInternals

    • getOccupiedMemory

      public long getOccupiedMemory()
      Specified by:
      getOccupiedMemory in interface MapInternals

    • getVitalMemory

      public long getVitalMemory()
      Specified by:
      getVitalMemory in interface MapInternals

    • getDataAllocatedMemory

      public long getDataAllocatedMemory()
      Specified by:
      getDataAllocatedMemory in interface MapInternals

    • getDataOccupiedMemory

      public long getDataOccupiedMemory()
      Specified by:
      getDataOccupiedMemory in interface MapInternals

    • getDataVitalMemory

      public long getDataVitalMemory()
      Specified by:
      getDataVitalMemory in interface MapInternals

    • getDataSize

      public long getDataSize()
      Specified by:
      getDataSize in interface MapInternals

    • isThiefForTableAllocations

      public boolean isThiefForTableAllocations()
      Specified by:
      isThiefForTableAllocations in interface StorageEngine.Owner

    • readLock

      public Lock readLock()
      Specified by:
      readLock in interface ReadWriteLock

    • writeLock

      public Lock writeLock()
      Specified by:
      writeLock in interface ReadWriteLock

    • getStorageEngine

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

    • computeWithMetadata

      public MetadataTuple<V> computeWithMetadata(K key, BiFunction<? super K, ? super MetadataTuple<V>, ? extends MetadataTuple<V>> remappingFunction)

    • computeIfAbsentWithMetadata

      public MetadataTuple<V> computeIfAbsentWithMetadata(K key, Function<? super K, ? extends MetadataTuple<V>> mappingFunction)

    • computeIfPresentWithMetadata

      public MetadataTuple<V> computeIfPresentWithMetadata(K key, BiFunction<? super K, ? super MetadataTuple<V>, ? extends MetadataTuple<V>> remappingFunction)