Class MVMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
org.h2.mvstore.MVMap<K,V>
Type Parameters:
K - the key class
V - the value class
All Implemented Interfaces:
ConcurrentMap<K,V>, Map<K,V>
Direct Known Subclasses:
MVRTreeMap, TransactionStore.TxMapBuilder.TMVMap

public class MVMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>
A stored map.

All read and write operations can happen concurrently with all other operations, without risk of corruption.

  • Field Details

    • store

      public final MVStore store
      The store.
    • root

      private final AtomicReference<RootReference<K,V>> root
      Reference to the current root page.
    • id

      private final int id
    • createVersion

      private final long createVersion
    • keyType

      private final DataType<K> keyType
    • valueType

      private final DataType<V> valueType
    • keysPerPage

      private final int keysPerPage
    • singleWriter

      private final boolean singleWriter
    • keysBuffer

      private final K[] keysBuffer
    • valuesBuffer

      private final V[] valuesBuffer
    • lock

      private final Object lock
    • notificationRequested

      private volatile boolean notificationRequested
    • closed

      private volatile boolean closed
      Whether the map is closed. Volatile so we don't accidentally write to a closed map in multithreaded mode.
    • readOnly

      private boolean readOnly
    • isVolatile

      private boolean isVolatile
    • avgKeySize

      private final AtomicLong avgKeySize
    • avgValSize

      private final AtomicLong avgValSize
    • INITIAL_VERSION

      static final long INITIAL_VERSION
      This designates the "last stored" version for a store which was just open for the first time.
      See Also:
  • Constructor Details

  • Method Details

    • cloneIt

      protected MVMap<K,V> cloneIt()
      Clone the current map.
      Returns:
      clone of this.
    • getMapRootKey

      static String getMapRootKey(int mapId)
      Get the metadata key for the root of the given map id.
      Parameters:
      mapId - the map id
      Returns:
      the metadata key
    • getMapKey

      static String getMapKey(int mapId)
      Get the metadata key for the given map id.
      Parameters:
      mapId - the map id
      Returns:
      the metadata key
    • put

      public V put(K key, V value)
      Add or replace a key-value pair.
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
      Parameters:
      key - the key (may not be null)
      value - the value (may not be null)
      Returns:
      the old value if the key existed, or null otherwise
    • firstKey

      public final K firstKey()
      Get the first key, or null if the map is empty.
      Returns:
      the first key, or null
    • lastKey

      public final K lastKey()
      Get the last key, or null if the map is empty.
      Returns:
      the last key, or null
    • getKey

      public final K getKey(long index)
      Get the key at the given index.

      This is a O(log(size)) operation.

      Parameters:
      index - the index
      Returns:
      the key
    • keyList

      public final List<K> keyList()
      Get the key list. The list is a read-only representation of all keys.

      The get and indexOf methods are O(log(size)) operations. The result of indexOf is cast to an int.

      Returns:
      the key list
    • getKeyIndex

      public final long getKeyIndex(K key)
      Get the index of the given key in the map.

      This is a O(log(size)) operation.

      If the key was found, the returned value is the index in the key array. If not found, the returned value is negative, where -1 means the provided key is smaller than any keys. See also Arrays.binarySearch.

      Parameters:
      key - the key
      Returns:
      the index
    • getFirstLast

      private K getFirstLast(boolean first)
      Get the first (lowest) or last (largest) key.
      Parameters:
      first - whether to retrieve the first key
      Returns:
      the key, or null if the map is empty
    • getFirstLast

      private K getFirstLast(Page<K,V> p, boolean first)
    • higherKey

      public final K higherKey(K key)
      Get the smallest key that is larger than the given key (next key in ascending order), or null if no such key exists.
      Parameters:
      key - the key
      Returns:
      the result
    • higherKey

      public final K higherKey(RootReference<K,V> rootRef, K key)
      Get the smallest key that is larger than the given key, for the given root page, or null if no such key exists.
      Parameters:
      rootRef - the root reference of the map
      key - to start from
      Returns:
      the result
    • ceilingKey

      public final K ceilingKey(K key)
      Get the smallest key that is larger or equal to this key.
      Parameters:
      key - the key
      Returns:
      the result
    • floorKey

      public final K floorKey(K key)
      Get the largest key that is smaller or equal to this key.
      Parameters:
      key - the key
      Returns:
      the result
    • lowerKey

      public final K lowerKey(K key)
      Get the largest key that is smaller than the given key, or null if no such key exists.
      Parameters:
      key - the key
      Returns:
      the result
    • lowerKey

      public final K lowerKey(RootReference<K,V> rootRef, K key)
      Get the largest key that is smaller than the given key, for the given root page, or null if no such key exists.
      Parameters:
      rootRef - the root page
      key - the key
      Returns:
      the result
    • getMinMax

      private K getMinMax(K key, boolean min, boolean excluding)
      Get the smallest or largest key using the given bounds.
      Parameters:
      key - the key
      min - whether to retrieve the smallest key
      excluding - if the given upper/lower bound is exclusive
      Returns:
      the key, or null if no such key exists
    • getMinMax

      private K getMinMax(RootReference<K,V> rootRef, K key, boolean min, boolean excluding)
    • getMinMax

      private K getMinMax(Page<K,V> p, K key, boolean min, boolean excluding)
    • get

      public final V get(Object key)
      Get the value for the given key, or null if not found.
      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
      Parameters:
      key - the key
      Returns:
      the value, or null if not found
      Throws:
      ClassCastException - if type of the specified key is not compatible with this map
    • get

      public V get(Page<K,V> p, K key)
      Get the value for the given key from a snapshot, or null if not found.
      Parameters:
      p - the root of a snapshot
      key - the key
      Returns:
      the value, or null if not found
      Throws:
      ClassCastException - if type of the specified key is not compatible with this map
    • containsKey

      public final boolean containsKey(Object key)
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
    • clear

      public void clear()
      Remove all entries.
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
    • clearIt

      RootReference<K,V> clearIt()
      Remove all entries and return the root reference.
      Returns:
      the new root reference
    • close

      final void close()
      Close the map. Accessing the data is still possible (to allow concurrent reads), but it is marked as closed.
    • isClosed

      public final boolean isClosed()
    • remove

      public V remove(Object key)
      Remove a key-value pair, if the key exists.
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
      Parameters:
      key - the key (may not be null)
      Returns:
      the old value if the key existed, or null otherwise
      Throws:
      ClassCastException - if type of the specified key is not compatible with this map
    • putIfAbsent

      public final V putIfAbsent(K key, V value)
      Add a key-value pair if it does not yet exist.
      Specified by:
      putIfAbsent in interface ConcurrentMap<K,V>
      Specified by:
      putIfAbsent in interface Map<K,V>
      Parameters:
      key - the key (may not be null)
      value - the new value
      Returns:
      the old value if the key existed, or null otherwise
    • remove

      public boolean remove(Object key, Object value)
      Remove a key-value pair if the value matches the stored one.
      Specified by:
      remove in interface ConcurrentMap<K,V>
      Specified by:
      remove in interface Map<K,V>
      Parameters:
      key - the key (may not be null)
      value - the expected value
      Returns:
      true if the item was removed
    • areValuesEqual

      static <X> boolean areValuesEqual(DataType<X> datatype, X a, X b)
      Check whether the two values are equal.
      Type Parameters:
      X - type of values to compare
      Parameters:
      datatype - to use for comparison
      a - the first value
      b - the second value
      Returns:
      true if they are equal
    • replace

      public final boolean replace(K key, V oldValue, V newValue)
      Replace a value for an existing key, if the value matches.
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
      Parameters:
      key - the key (may not be null)
      oldValue - the expected value
      newValue - the new value
      Returns:
      true if the value was replaced
    • replace

      public final V replace(K key, V value)
      Replace a value for an existing key.
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
      Parameters:
      key - the key (may not be null)
      value - the new value
      Returns:
      the old value, if the value was replaced, or null
    • compare

      final int compare(K a, K b)
      Compare two keys.
      Parameters:
      a - the first key
      b - the second key
      Returns:
      -1 if the first key is smaller, 1 if bigger, 0 if equal
    • getKeyType

      public final DataType<K> getKeyType()
      Get the key type.
      Returns:
      the key type
    • getValueType

      public final DataType<V> getValueType()
      Get the value type.
      Returns:
      the value type
    • isSingleWriter

      boolean isSingleWriter()
    • readPage

      final Page<K,V> readPage(long pos)
      Read a page.
      Parameters:
      pos - the position of the page
      Returns:
      the page
    • setRootPos

      final void setRootPos(long rootPos, long version)
      Set the position of the root page.
      Parameters:
      rootPos - the position, 0 for empty
      version - to set for this map
    • readOrCreateRootPage

      private Page<K,V> readOrCreateRootPage(long rootPos)
    • keyIterator

      public final Iterator<K> keyIterator(K from)
      Iterate over a number of keys.
      Parameters:
      from - the first key to return
      Returns:
      the iterator
    • keyIteratorReverse

      public final Iterator<K> keyIteratorReverse(K from)
      Iterate over a number of keys in reverse order
      Parameters:
      from - the first key to return
      Returns:
      the iterator
    • rewritePage

      final boolean rewritePage(long pagePos)
    • cursor

      public final Cursor<K,V> cursor(K from)
      Get a cursor to iterate over a number of keys and values in the latest version of this map.
      Parameters:
      from - the first key to return
      Returns:
      the cursor
    • cursor

      public final Cursor<K,V> cursor(K from, K to, boolean reverse)
      Get a cursor to iterate over a number of keys and values in the latest version of this map.
      Parameters:
      from - the first key to return
      to - the last key to return
      reverse - if true, iterate in reverse (descending) order
      Returns:
      the cursor
    • cursor

      public Cursor<K,V> cursor(RootReference<K,V> rootReference, K from, K to, boolean reverse)
      Get a cursor to iterate over a number of keys and values.
      Parameters:
      rootReference - of this map's version to iterate over
      from - the first key to return
      to - the last key to return
      reverse - if true, iterate in reverse (descending) order
      Returns:
      the cursor
    • 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>
    • keySet

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

      public final String getName()
      Get the map name.
      Returns:
      the name
    • getStore

      public final MVStore getStore()
    • isPersistent

      protected final boolean isPersistent()
    • getId

      public final int getId()
      Get the map id. Please note the map id may be different after compacting a store.
      Returns:
      the map id
    • getRootPage

      public final Page<K,V> getRootPage()
      The current root page (may not be null).
      Returns:
      the root page
    • getRoot

      public RootReference<K,V> getRoot()
    • flushAndGetRoot

      public RootReference<K,V> flushAndGetRoot()
      Get the root reference, flushing any current append buffer.
      Returns:
      current root reference
    • setInitialRoot

      final void setInitialRoot(Page<K,V> rootPage, long version)
      Set the initial root.
      Parameters:
      rootPage - root page
      version - initial version
    • compareAndSetRoot

      final boolean compareAndSetRoot(RootReference<K,V> expectedRootReference, RootReference<K,V> updatedRootReference)
      Compare and set the root reference.
      Parameters:
      expectedRootReference - the old (expected)
      updatedRootReference - the new
      Returns:
      whether updating worked
    • rollbackTo

      final void rollbackTo(long version)
      Rollback to the given version.
      Parameters:
      version - the version
    • rollbackRoot

      boolean rollbackRoot(long version)
      Roll the root back to the specified version.
      Parameters:
      version - to rollback to
      Returns:
      true if rollback was a success, false if there was not enough in-memory history
    • updateRoot

      protected static <K, V> boolean updateRoot(RootReference<K,V> expectedRootReference, Page<K,V> newRootPage, int attemptUpdateCounter)
      Use the new root page from now on.
      Type Parameters:
      K - the key class
      V - the value class
      Parameters:
      expectedRootReference - expected current root reference
      newRootPage - the new root page
      attemptUpdateCounter - how many attempt (including current) were made to update root
      Returns:
      new RootReference or null if update failed
    • removeUnusedOldVersions

      private void removeUnusedOldVersions(RootReference<K,V> rootReference)
      Forget those old versions that are no longer needed.
      Parameters:
      rootReference - to inspect
    • isReadOnly

      public final boolean isReadOnly()
    • setVolatile

      public final void setVolatile(boolean isVolatile)
      Set the volatile flag of the map.
      Parameters:
      isVolatile - the volatile flag
    • isVolatile

      public final boolean isVolatile()
      Whether this is volatile map, meaning that changes are not persisted. By default (even if the store is not persisted), maps are not volatile.
      Returns:
      whether this map is volatile
    • beforeWrite

      protected final void beforeWrite()
      This method is called before writing to the map. The default implementation checks whether writing is allowed, and tries to detect concurrent modification.
      Throws:
      UnsupportedOperationException - if the map is read-only, or if another thread is concurrently writing
    • hashCode

      public final int hashCode()
      Specified by:
      hashCode in interface Map<K,V>
      Overrides:
      hashCode in class AbstractMap<K,V>
    • equals

      public final boolean equals(Object o)
      Specified by:
      equals in interface Map<K,V>
      Overrides:
      equals in class AbstractMap<K,V>
    • size

      public final int size()
      Get the number of entries, as a integer. Integer.MAX_VALUE is returned if there are more than this entries.
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
      Returns:
      the number of entries, as an integer
      See Also:
    • sizeAsLong

      public final long sizeAsLong()
      Get the number of entries, as a long.
      Returns:
      the number of entries
    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
    • getCreateVersion

      final long getCreateVersion()
    • openVersion

      public final MVMap<K,V> openVersion(long version)
      Open an old version for the given map. It will restore map at last known state of the version specified. (at the point right before the commit() call, which advanced map to the next version) Map is opened in read-only mode.
      Parameters:
      version - the version
      Returns:
      the map
    • openReadOnly

      final MVMap<K,V> openReadOnly(long rootPos, long version)
      Open a copy of the map in read-only mode.
      Parameters:
      rootPos - position of the root page
      version - to open
      Returns:
      the opened map
    • openReadOnly

      private MVMap<K,V> openReadOnly(Page<K,V> root, long version)
    • getVersion

      public final long getVersion()
      Get version of the map, which is the version of the store, at the moment when map was modified last time.
      Returns:
      version
    • hasChangesSince

      final boolean hasChangesSince(long version)
      Does the root have changes since the specified version?
      Parameters:
      version - root version
      Returns:
      true if has changes
    • getChildPageCount

      protected int getChildPageCount(Page<K,V> p)
      Get the child page count for this page. This is to allow another map implementation to override the default, in case the last child is not to be used.
      Parameters:
      p - the page
      Returns:
      the number of direct children
    • getType

      public String getType()
      Get the map type. When opening an existing map, the map type must match.
      Returns:
      the map type
    • asString

      protected String asString(String name)
      Get the map metadata as a string.
      Parameters:
      name - the map name (or null)
      Returns:
      the string
    • setWriteVersion

      final RootReference<K,V> setWriteVersion(long writeVersion)
    • createEmptyLeaf

      protected Page<K,V> createEmptyLeaf()
      Create empty leaf node page.
      Returns:
      new page
    • createEmptyNode

      protected Page<K,V> createEmptyNode()
      Create empty internal node page.
      Returns:
      new page
    • copyFrom

      final void copyFrom(MVMap<K,V> sourceMap)
      Copy a map. All pages are copied.
      Parameters:
      sourceMap - the source map
    • copy

      private void copy(Page<K,V> source, Page<K,V> parent, int index)
    • flushAppendBuffer

      private RootReference<K,V> flushAppendBuffer(RootReference<K,V> rootReference, boolean fullFlush)
      If map was used in append mode, this method will ensure that append buffer is flushed - emptied with all entries inserted into map as a new leaf.
      Parameters:
      rootReference - current RootReference
      fullFlush - whether buffer should be completely flushed, otherwise just a single empty slot is required
      Returns:
      potentially updated RootReference
    • replacePage

      private static <K, V> Page<K,V> replacePage(CursorPos<K,V> path, Page<K,V> replacement, MVMap.IntValueHolder unsavedMemoryHolder)
    • append

      public void append(K key, V value)
      Appends entry to this map. this method is NOT thread safe and can not be used neither concurrently, nor in combination with any method that updates this map. Non-updating method may be used concurrently, but latest appended values are not guaranteed to be visible.
      Parameters:
      key - should be higher in map's order than any existing key
      value - to be appended
    • trimLast

      public void trimLast()
      Removes last entry from this map. this method is NOT thread safe and can not be used neither concurrently, nor in combination with any method that updates this map. Non-updating method may be used concurrently, but latest removal may not be visible.
    • toString

      public final String toString()
      Overrides:
      toString in class AbstractMap<K,V>
    • operate

      public V operate(K key, V value, MVMap.DecisionMaker<? super V> decisionMaker)
      Add, replace or remove a key-value pair.
      Parameters:
      key - the key (may not be null)
      value - new value, it may be null when removal is intended
      decisionMaker - command object to make choices during transaction.
      Returns:
      previous value, if mapping for that key existed, or null otherwise
    • lockRoot

      private RootReference<K,V> lockRoot(RootReference<K,V> rootReference, int attempt)
    • tryLock

      protected RootReference<K,V> tryLock(RootReference<K,V> rootReference, int attempt)
      Try to lock the root.
      Parameters:
      rootReference - the old root reference
      attempt - the number of attempts so far
      Returns:
      the new root reference
    • unlockRoot

      private RootReference<K,V> unlockRoot()
      Unlock the root page, the new root being null.
      Returns:
      the new root reference (never null)
    • unlockRoot

      protected RootReference<K,V> unlockRoot(Page<K,V> newRootPage)
      Unlock the root page.
      Parameters:
      newRootPage - the new root
      Returns:
      the new root reference (never null)
    • unlockRoot

      private void unlockRoot(int appendCounter)
    • unlockRoot

      private RootReference<K,V> unlockRoot(Page<K,V> newRootPage, int appendCounter)
    • notifyWaiters

      private void notifyWaiters()
    • isMemoryEstimationAllowed

      final boolean isMemoryEstimationAllowed()
    • evaluateMemoryForKeys

      final int evaluateMemoryForKeys(K[] storage, int count)
    • evaluateMemoryForValues

      final int evaluateMemoryForValues(V[] storage, int count)
    • calculateMemory

      private static <T> int calculateMemory(DataType<T> keyType, T[] storage, int count)
    • evaluateMemoryForKey

      final int evaluateMemoryForKey(K key)
    • evaluateMemoryForValue

      final int evaluateMemoryForValue(V value)
    • samplingPct

      static int samplingPct(AtomicLong stats)