Package org.h2.mvstore
Class MVMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
org.h2.mvstore.MVMap<K,V>
- Type Parameters:
K
- the key classV
- the value class
- All Implemented Interfaces:
ConcurrentMap<K,
,V> Map<K,
V>
- Direct Known Subclasses:
MVRTreeMap
,TransactionStore.TxMapBuilder.TMVMap
A stored map.
All read and write operations can happen concurrently with all other operations, without risk of corruption.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
A builder for this class.static class
A builder for this class.static enum
The decision on what to do on an update.static class
Class DecisionMaker provides callback interface (and should become a such in Java 8) for MVMap.operate method.private static final class
private static final class
static interface
A builder for maps.private static final class
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final AtomicLong
private final AtomicLong
private boolean
Whether the map is closed.private final long
private final int
(package private) static final long
This designates the "last stored" version for a store which was just open for the first time.private boolean
private final K[]
private final int
private final Object
private boolean
private boolean
private final AtomicReference
<RootReference<K, V>> Reference to the current root page.private final boolean
final MVStore
The store.private final V[]
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
protected
(package private)
private
MVMap
(MVStore store, DataType<K> keyType, DataType<V> valueType, int id, long createVersion, AtomicReference<RootReference<K, V>> root, int keysPerPage, boolean singleWriter) -
Method Summary
Modifier and TypeMethodDescriptionvoid
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 String
Get the map metadata as a string.protected final void
This method is called before writing to the map.private static <T> int
calculateMemory
(DataType<T> keyType, T[] storage, int count) final 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.cloneIt()
Clone the current map.(package private) final void
close()
Close the map.(package private) final int
Compare two keys.(package private) final boolean
compareAndSetRoot
(RootReference<K, V> expectedRootReference, RootReference<K, V> updatedRootReference) Compare and set the root reference.final boolean
containsKey
(Object key) private void
(package private) final void
Copy a map.Create empty leaf node page.Create empty internal node page.Get a cursor to iterate over a number of keys and values in the latest version of this map.Get a cursor to iterate over a number of keys and values in the latest version of this map.Get a cursor to iterate over a number of keys and values.entrySet()
final boolean
(package private) final int
evaluateMemoryForKey
(K key) (package private) final int
evaluateMemoryForKeys
(K[] storage, int count) (package private) final int
evaluateMemoryForValue
(V value) (package private) final int
evaluateMemoryForValues
(V[] storage, int count) final K
firstKey()
Get the first key, or null if the map is empty.final K
Get the largest key that is smaller or equal to this key.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.final V
Get the value for the given key, or null if not found.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) final long
private K
getFirstLast
(boolean first) Get the first (lowest) or last (largest) key.private K
getFirstLast
(Page<K, V> p, boolean first) final int
getId()
Get the map id.final K
getKey
(long index) Get the key at the given index.final long
getKeyIndex
(K key) Get the index of the given key in the map.Get the key type.(package private) static String
getMapKey
(int mapId) Get the metadata key for the given map id.(package private) static String
getMapRootKey
(int mapId) Get the metadata key for the root of the given map id.private K
Get the smallest or largest key using the given bounds.private K
private K
getMinMax
(RootReference<K, V> rootRef, K key, boolean min, boolean excluding) final String
getName()
Get the map name.getRoot()
The current root page (may not be null).final MVStore
getStore()
getType()
Get the map type.Get the value type.final long
Get version of the map, which is the version of the store, at the moment when map was modified last time.(package private) final boolean
hasChangesSince
(long version) Does the root have changes since the specified version?final int
hashCode()
final K
Get the smallest key that is larger than the given key (next key in ascending order), or null if no such key exists.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.final boolean
isClosed()
boolean
isEmpty()
(package private) final boolean
protected final boolean
final boolean
(package private) boolean
final boolean
Whether this is volatile map, meaning that changes are not persisted.keyIterator
(K from) Iterate over a number of keys.keyIteratorReverse
(K from) Iterate over a number of keys in reverse orderkeyList()
Get the key list.keySet()
final K
lastKey()
Get the last key, or null if the map is empty.private RootReference
<K, V> lockRoot
(RootReference<K, V> rootReference, int attempt) final K
Get the largest key that is smaller than the given key, or null if no such key exists.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.private void
openReadOnly
(long rootPos, long version) Open a copy of the map in read-only mode.openReadOnly
(Page<K, V> root, long version) openVersion
(long version) Open an old version for the given map.operate
(K key, V value, MVMap.DecisionMaker<? super V> decisionMaker) Add, replace or remove a key-value pair.Add or replace a key-value pair.final V
putIfAbsent
(K key, V value) Add a key-value pair if it does not yet exist.readOrCreateRootPage
(long rootPos) readPage
(long pos) Read a page.Remove a key-value pair, if the key exists.boolean
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.final V
Replace a value for an existing key.final boolean
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) final boolean
rewritePage
(long pagePos) (package private) boolean
rollbackRoot
(long version) Roll the root back to the specified version.(package private) final void
rollbackTo
(long version) Rollback to the given version.(package private) static int
samplingPct
(AtomicLong stats) (package private) final void
setInitialRoot
(Page<K, V> rootPage, long version) Set the initial root.(package private) final void
setRootPos
(long rootPos, long version) Set the position of the root page.final void
setVolatile
(boolean isVolatile) Set the volatile flag of the map.(package private) final RootReference
<K, V> setWriteVersion
(long writeVersion) final int
size()
Get the number of entries, as a integer.final long
Get the number of entries, as a long.final 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> 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 Details
-
store
The store. -
root
Reference to the current root page. -
id
private final int id -
createVersion
private final long createVersion -
keyType
-
valueType
-
keysPerPage
private final int keysPerPage -
singleWriter
private final boolean singleWriter -
keysBuffer
-
valuesBuffer
-
lock
-
notificationRequested
private volatile boolean notificationRequested -
closed
private volatile boolean closedWhether 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
-
avgValSize
-
INITIAL_VERSION
static final long INITIAL_VERSIONThis designates the "last stored" version for a store which was just open for the first time.- See Also:
-
-
Constructor Details
-
MVMap
-
MVMap
-
MVMap
-
MVMap
private MVMap(MVStore store, DataType<K> keyType, DataType<V> valueType, int id, long createVersion, AtomicReference<RootReference<K, V>> root, int keysPerPage, boolean singleWriter)
-
-
Method Details
-
cloneIt
Clone the current map.- Returns:
- clone of this.
-
getMapRootKey
Get the metadata key for the root of the given map id.- Parameters:
mapId
- the map id- Returns:
- the metadata key
-
getMapKey
Get the metadata key for the given map id.- Parameters:
mapId
- the map id- Returns:
- the metadata key
-
put
Add or replace a key-value pair. -
firstKey
Get the first key, or null if the map is empty.- Returns:
- the first key, or null
-
lastKey
Get the last key, or null if the map is empty.- Returns:
- the last key, or null
-
getKey
Get the key at the given index.This is a O(log(size)) operation.
- Parameters:
index
- the index- Returns:
- the key
-
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
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
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
-
higherKey
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
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 mapkey
- to start from- Returns:
- the result
-
ceilingKey
Get the smallest key that is larger or equal to this key.- Parameters:
key
- the key- Returns:
- the result
-
floorKey
Get the largest key that is smaller or equal to this key.- Parameters:
key
- the key- Returns:
- the result
-
lowerKey
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
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 pagekey
- the key- Returns:
- the result
-
getMinMax
Get the smallest or largest key using the given bounds.- Parameters:
key
- the keymin
- whether to retrieve the smallest keyexcluding
- if the given upper/lower bound is exclusive- Returns:
- the key, or null if no such key exists
-
getMinMax
-
getMinMax
-
get
Get the value for the given key, or null if not found.- Specified by:
get
in interfaceMap<K,
V> - Overrides:
get
in classAbstractMap<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
Get the value for the given key from a snapshot, or null if not found.- Parameters:
p
- the root of a snapshotkey
- 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
- Specified by:
containsKey
in interfaceMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V>
-
clear
public void clear()Remove all entries. -
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
Remove a key-value pair, if the key exists.- Specified by:
remove
in interfaceMap<K,
V> - Overrides:
remove
in classAbstractMap<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
Add a key-value pair if it does not yet exist.- Specified by:
putIfAbsent
in interfaceConcurrentMap<K,
V> - Specified by:
putIfAbsent
in interfaceMap<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
Remove a key-value pair if the value matches the stored one. -
areValuesEqual
Check whether the two values are equal.- Type Parameters:
X
- type of values to compare- Parameters:
datatype
- to use for comparisona
- the first valueb
- the second value- Returns:
- true if they are equal
-
replace
Replace a value for an existing key, if the value matches. -
replace
Replace a value for an existing key. -
compare
Compare two keys.- Parameters:
a
- the first keyb
- the second key- Returns:
- -1 if the first key is smaller, 1 if bigger, 0 if equal
-
getKeyType
Get the key type.- Returns:
- the key type
-
getValueType
Get the value type.- Returns:
- the value type
-
isSingleWriter
boolean isSingleWriter() -
readPage
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 emptyversion
- to set for this map
-
readOrCreateRootPage
-
keyIterator
Iterate over a number of keys.- Parameters:
from
- the first key to return- Returns:
- the iterator
-
keyIteratorReverse
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
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
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 returnto
- the last key to returnreverse
- if true, iterate in reverse (descending) order- Returns:
- the cursor
-
cursor
Get a cursor to iterate over a number of keys and values.- Parameters:
rootReference
- of this map's version to iterate overfrom
- the first key to returnto
- the last key to returnreverse
- if true, iterate in reverse (descending) order- Returns:
- the cursor
-
entrySet
-
keySet
-
getName
Get the map name.- Returns:
- the name
-
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
The current root page (may not be null).- Returns:
- the root page
-
getRoot
-
flushAndGetRoot
Get the root reference, flushing any current append buffer.- Returns:
- current root reference
-
setInitialRoot
Set the initial root.- Parameters:
rootPage
- root pageversion
- 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 classV
- the value class- Parameters:
expectedRootReference
- expected current root referencenewRootPage
- the new root pageattemptUpdateCounter
- how many attempt (including current) were made to update root- Returns:
- new RootReference or null if update failed
-
removeUnusedOldVersions
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() -
equals
-
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. -
sizeAsLong
public final long sizeAsLong()Get the number of entries, as a long.- Returns:
- the number of entries
-
isEmpty
public boolean isEmpty() -
getCreateVersion
final long getCreateVersion() -
openVersion
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
Open a copy of the map in read-only mode.- Parameters:
rootPos
- position of the root pageversion
- to open- Returns:
- the opened map
-
openReadOnly
-
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
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
Get the map type. When opening an existing map, the map type must match.- Returns:
- the map type
-
asString
Get the map metadata as a string.- Parameters:
name
- the map name (or null)- Returns:
- the string
-
setWriteVersion
-
createEmptyLeaf
Create empty leaf node page.- Returns:
- new page
-
createEmptyNode
Create empty internal node page.- Returns:
- new page
-
copyFrom
Copy a map. All pages are copied.- Parameters:
sourceMap
- the source map
-
copy
-
flushAppendBuffer
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 RootReferencefullFlush
- 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
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 keyvalue
- 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
- Overrides:
toString
in classAbstractMap<K,
V>
-
operate
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 intendeddecisionMaker
- command object to make choices during transaction.- Returns:
- previous value, if mapping for that key existed, or null otherwise
-
lockRoot
-
tryLock
Try to lock the root.- Parameters:
rootReference
- the old root referenceattempt
- the number of attempts so far- Returns:
- the new root reference
-
unlockRoot
Unlock the root page, the new root being null.- Returns:
- the new root reference (never null)
-
unlockRoot
Unlock the root page.- Parameters:
newRootPage
- the new root- Returns:
- the new root reference (never null)
-
unlockRoot
private void unlockRoot(int appendCounter) -
unlockRoot
-
notifyWaiters
private void notifyWaiters() -
isMemoryEstimationAllowed
final boolean isMemoryEstimationAllowed() -
evaluateMemoryForKeys
-
evaluateMemoryForValues
-
calculateMemory
-
evaluateMemoryForKey
-
evaluateMemoryForValue
-
samplingPct
-