Class MVMap<K,​V>

  • Type Parameters:
    K - the key class
    V - the value class
    All Implemented Interfaces:
    java.util.concurrent.ConcurrentMap<K,​V>, java.util.Map<K,​V>
    Direct Known Subclasses:
    MVRTreeMap, TransactionStore.TxMapBuilder.TMVMap

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

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

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  MVMap.BasicBuilder<M extends MVMap<K,​V>,​K,​V>
      A builder for this class.
      static class  MVMap.Builder<K,​V>
      A builder for this class.
      static class  MVMap.Decision
      The decision on what to do on an update.
      static class  MVMap.DecisionMaker<V>
      Class DecisionMaker provides callback interface (and should become a such in Java 8) for MVMap.operate method.
      private static class  MVMap.EqualsDecisionMaker<V>  
      private static class  MVMap.IntValueHolder  
      static interface  MVMap.MapBuilder<M extends MVMap<K,​V>,​K,​V>
      A builder for maps.
      private static class  MVMap.RewriteDecisionMaker<V>  
      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected MVMap​(java.util.Map<java.lang.String,​java.lang.Object> config, DataType<K> keyType, DataType<V> valueType)  
      protected MVMap​(MVMap<K,​V> source)  
      (package private) MVMap​(MVStore store, int id, DataType<K> keyType, DataType<V> valueType)  
      private MVMap​(MVStore store, DataType<K> keyType, DataType<V> valueType, int id, long createVersion, java.util.concurrent.atomic.AtomicReference<RootReference<K,​V>> root, int keysPerPage, boolean singleWriter)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void append​(K key, V value)
      Appends entry to this map.
      (package private) static <X> boolean areValuesEqual​(DataType<X> datatype, X a, X b)
      Check whether the two values are equal.
      protected java.lang.String asString​(java.lang.String name)
      Get the map metadata as a string.
      protected void beforeWrite()
      This method is called before writing to the map.
      private static <T> int calculateMemory​(DataType<T> keyType, T[] storage, int count)  
      K ceilingKey​(K key)
      Get the smallest key that is larger or equal to this key.
      void clear()
      Remove all entries.
      (package private) RootReference<K,​V> clearIt()
      Remove all entries and return the root reference.
      protected MVMap<K,​V> cloneIt()
      Clone the current map.
      (package private) void close()
      Close the map.
      (package private) int compare​(K a, K b)
      Compare two keys.
      (package private) boolean compareAndSetRoot​(RootReference<K,​V> expectedRootReference, RootReference<K,​V> updatedRootReference)
      Compare and set the root reference.
      boolean containsKey​(java.lang.Object key)  
      private void copy​(Page<K,​V> source, Page<K,​V> parent, int index)  
      (package private) void copyFrom​(MVMap<K,​V> sourceMap)
      Copy a map.
      protected Page<K,​V> createEmptyLeaf()
      Create empty leaf node page.
      protected Page<K,​V> createEmptyNode()
      Create empty internal node page.
      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.
      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.
      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.
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()  
      boolean equals​(java.lang.Object o)  
      (package private) int evaluateMemoryForKey​(K key)  
      (package private) int evaluateMemoryForKeys​(K[] storage, int count)  
      (package private) int evaluateMemoryForValue​(V value)  
      (package private) int evaluateMemoryForValues​(V[] storage, int count)  
      K firstKey()
      Get the first key, or null if the map is empty.
      K floorKey​(K key)
      Get the largest key that is smaller or equal to this key.
      RootReference<K,​V> flushAndGetRoot()
      Get the root reference, flushing any current append buffer.
      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.
      V get​(java.lang.Object key)
      Get the value for the given key, or null if not found.
      V get​(Page<K,​V> p, K key)
      Get the value for the given key from a snapshot, or null if not found.
      protected int getChildPageCount​(Page<K,​V> p)
      Get the child page count for this page.
      (package private) long getCreateVersion()  
      private K getFirstLast​(boolean first)
      Get the first (lowest) or last (largest) key.
      private K getFirstLast​(Page<K,​V> p, boolean first)  
      int getId()
      Get the map id.
      K getKey​(long index)
      Get the key at the given index.
      long getKeyIndex​(K key)
      Get the index of the given key in the map.
      DataType<K> getKeyType()
      Get the key type.
      (package private) static java.lang.String getMapKey​(int mapId)
      Get the metadata key for the given map id.
      (package private) static java.lang.String getMapRootKey​(int mapId)
      Get the metadata key for the root of the given map id.
      private K getMinMax​(K key, boolean min, boolean excluding)
      Get the smallest or largest key using the given bounds.
      private K getMinMax​(Page<K,​V> p, K key, boolean min, boolean excluding)  
      private K getMinMax​(RootReference<K,​V> rootRef, K key, boolean min, boolean excluding)  
      java.lang.String getName()
      Get the map name.
      RootReference<K,​V> getRoot()  
      Page<K,​V> getRootPage()
      The current root page (may not be null).
      MVStore getStore()  
      java.lang.String getType()
      Get the map type.
      DataType<V> getValueType()
      Get the value type.
      long getVersion()
      Get version of the map, which is the version of the store, at the moment when map was modified last time.
      (package private) boolean hasChangesSince​(long version)
      Does the root have changes since the specified version?
      int hashCode()  
      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.
      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.
      boolean isClosed()  
      boolean isEmpty()  
      (package private) boolean isMemoryEstimationAllowed()  
      protected boolean isPersistent()  
      boolean isReadOnly()  
      (package private) boolean isSingleWriter()  
      boolean isVolatile()
      Whether this is volatile map, meaning that changes are not persisted.
      java.util.Iterator<K> keyIterator​(K from)
      Iterate over a number of keys.
      java.util.Iterator<K> keyIteratorReverse​(K from)
      Iterate over a number of keys in reverse order
      java.util.List<K> keyList()
      Get the key list.
      java.util.Set<K> keySet()  
      K lastKey()
      Get the last key, or null if the map is empty.
      private RootReference<K,​V> lockRoot​(RootReference<K,​V> rootReference, int attempt)  
      K lowerKey​(K key)
      Get the largest key that is smaller than the given key, or null if no such key exists.
      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.
      private void notifyWaiters()  
      (package private) MVMap<K,​V> openReadOnly​(long rootPos, long version)
      Open a copy of the map in read-only mode.
      private MVMap<K,​V> openReadOnly​(Page<K,​V> root, long version)  
      MVMap<K,​V> openVersion​(long version)
      Open an old version for the given map.
      V operate​(K key, V value, MVMap.DecisionMaker<? super V> decisionMaker)
      Add, replace or remove a key-value pair.
      V put​(K key, V value)
      Add or replace a key-value pair.
      V putIfAbsent​(K key, V value)
      Add a key-value pair if it does not yet exist.
      private Page<K,​V> readOrCreateRootPage​(long rootPos)  
      (package private) Page<K,​V> readPage​(long pos)
      Read a page.
      V remove​(java.lang.Object key)
      Remove a key-value pair, if the key exists.
      boolean remove​(java.lang.Object key, java.lang.Object value)
      Remove a key-value pair if the value matches the stored one.
      private void removeUnusedOldVersions​(RootReference<K,​V> rootReference)
      Forget those old versions that are no longer needed.
      V replace​(K key, V value)
      Replace a value for an existing key.
      boolean replace​(K key, V oldValue, V newValue)
      Replace a value for an existing key, if the value matches.
      private static <K,​V>
      Page<K,​V>
      replacePage​(CursorPos<K,​V> path, Page<K,​V> replacement, MVMap.IntValueHolder unsavedMemoryHolder)  
      (package private) boolean rewritePage​(long pagePos)  
      (package private) boolean rollbackRoot​(long version)
      Roll the root back to the specified version.
      (package private) void rollbackTo​(long version)
      Rollback to the given version.
      (package private) static int samplingPct​(java.util.concurrent.atomic.AtomicLong stats)  
      (package private) void setInitialRoot​(Page<K,​V> rootPage, long version)
      Set the initial root.
      (package private) void setRootPos​(long rootPos, long version)
      Set the position of the root page.
      void setVolatile​(boolean isVolatile)
      Set the volatile flag of the map.
      (package private) RootReference<K,​V> setWriteVersion​(long writeVersion)  
      int size()
      Get the number of entries, as a integer.
      long sizeAsLong()
      Get the number of entries, as a long.
      java.lang.String toString()  
      void trimLast()
      Removes last entry from this map.
      protected RootReference<K,​V> tryLock​(RootReference<K,​V> rootReference, int attempt)
      Try to lock the root.
      private RootReference<K,​V> unlockRoot()
      Unlock the root page, the new root being null.
      private void unlockRoot​(int appendCounter)  
      protected RootReference<K,​V> unlockRoot​(Page<K,​V> newRootPage)
      Unlock the root page.
      private RootReference<K,​V> unlockRoot​(Page<K,​V> newRootPage, int appendCounter)  
      protected static <K,​V>
      boolean
      updateRoot​(RootReference<K,​V> expectedRootReference, Page<K,​V> newRootPage, int attemptUpdateCounter)
      Use the new root page from now on.
      • Methods inherited from class java.util.AbstractMap

        clone, containsValue, putAll, 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.Map

        containsValue, putAll, values
    • Field Detail

      • store

        public final MVStore store
        The store.
      • root

        private final java.util.concurrent.atomic.AtomicReference<RootReference<K,​V>> root
        Reference to the current root page.
      • id

        private final int id
      • createVersion

        private final long createVersion
      • 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 java.lang.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 java.util.concurrent.atomic.AtomicLong avgKeySize
      • avgValSize

        private final java.util.concurrent.atomic.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:
        Constant Field Values
    • Constructor Detail

      • MVMap

        protected MVMap​(java.util.Map<java.lang.String,​java.lang.Object> config,
                        DataType<K> keyType,
                        DataType<V> valueType)
      • MVMap

        protected MVMap​(MVMap<K,​V> source)
      • MVMap

        private MVMap​(MVStore store,
                      DataType<K> keyType,
                      DataType<V> valueType,
                      int id,
                      long createVersion,
                      java.util.concurrent.atomic.AtomicReference<RootReference<K,​V>> root,
                      int keysPerPage,
                      boolean singleWriter)
    • Method Detail

      • cloneIt

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

        static java.lang.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 java.lang.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 java.util.Map<K,​V>
        Overrides:
        put in class java.util.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 java.util.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​(java.lang.Object key)
        Get the value for the given key, or null if not found.
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
        Parameters:
        key - the key
        Returns:
        the value, or null if not found
        Throws:
        java.lang.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:
        java.lang.ClassCastException - if type of the specified key is not compatible with this map
      • containsKey

        public final 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>
      • clear

        public void clear()
        Remove all entries.
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.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​(java.lang.Object key)
        Remove a key-value pair, if the key exists.
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
        Parameters:
        key - the key (may not be null)
        Returns:
        the old value if the key existed, or null otherwise
        Throws:
        java.lang.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 java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        putIfAbsent in interface java.util.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​(java.lang.Object key,
                              java.lang.Object value)
        Remove a key-value pair if the value matches the stored one.
        Specified by:
        remove in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        remove in interface java.util.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:
        a - the first value
        b - the second value
        datatype - to use for comparison
        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 java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.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 java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.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 java.util.Iterator<K> keyIterator​(K from)
        Iterate over a number of keys.
        Parameters:
        from - the first key to return
        Returns:
        the iterator
      • keyIteratorReverse

        public final java.util.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 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 java.util.Set<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
      • getName

        public final java.lang.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
      • 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:
        java.lang.UnsupportedOperationException - if the map is read-only, or if another thread is concurrently writing
      • hashCode

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

        public final boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Map<K,​V>
        Overrides:
        equals in class java.util.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 java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
        Returns:
        the number of entries, as an integer
        See Also:
        sizeAsLong()
      • 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 java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.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 java.lang.String getType()
        Get the map type. When opening an existing map, the map type must match.
        Returns:
        the map type
      • asString

        protected java.lang.String asString​(java.lang.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
      • 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 java.lang.String toString()
        Overrides:
        toString in class java.util.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
      • 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​(java.util.concurrent.atomic.AtomicLong stats)