Class Page<K,​V>

  • All Implemented Interfaces:
    java.lang.Cloneable
    Direct Known Subclasses:
    Page.Leaf, Page.NonLeaf

    public abstract class Page<K,​V>
    extends java.lang.Object
    implements java.lang.Cloneable
    A page (a node or a leaf).

    For b-tree nodes, the key at a given index is larger than the largest key of the child at the same index.

    Serialized format: length of a serialized page in bytes (including this field): int check value: short page number (0-based sequential number within a chunk): varInt map id: varInt number of keys: varInt type: byte (0: leaf, 1: node; +2: compressed) children of the non-leaf node (1 more than keys) compressed: bytes saved (varInt) keys values of the leaf node (one for each key)

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int cachedCompare
      The last result of a find operation is cached.
      private int diskSpaceUsed
      Amount of used disk space by this page only in persistent case.
      private static int IN_MEMORY
      Marker value for memory field, meaning that memory accounting is replaced by key count.
      private K[] keys
      The keys.
      MVMap<K,​V> map
      Map this page belongs to
      private int memory
      The estimated memory used in persistent case, IN_MEMORY marker value otherwise.
      (package private) static int PAGE_LEAF_MEMORY
      The estimated number of bytes used per empty leaf page.
      private static int PAGE_MEMORY
      The estimated number of bytes used per base page.
      (package private) static int PAGE_MEMORY_CHILD
      The estimated number of bytes used per child entry.
      (package private) static int PAGE_NODE_MEMORY
      The estimated number of bytes used per empty internal page object.
      int pageNo
      Sequential 0-based number of the page within containing chunk.
      private long pos
      Position of this page's saved image within a Chunk or 0 if this page has not been saved yet or 1 if this page has not been saved yet, but already removed This "removed" flag is to keep track of pages that concurrently changed while they are being stored, in which case the live bookkeeping needs to be aware of such cases.
      private static java.util.concurrent.atomic.AtomicLongFieldUpdater<Page> posUpdater
      Updater for pos field, which can be updated when page is saved, but can be concurrently marked as removed
      private static Page.PageReference[] SINGLE_EMPTY  
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void addMemory​(int mem)
      Increase estimated memory used in persistent case.
      (package private) int binarySearch​(K key)
      Search the key in this page using a binary search.
      protected int calculateMemory()
      Calculate estimated memory used in persistent case.
      protected Page<K,​V> clone()  
      Page<K,​V> copy()
      Create a copy of this page.
      (package private) abstract Page<K,​V> copy​(MVMap<K,​V> map, boolean eraseChildrenRefs)
      Create a copy of this page with potentially different owning map.
      (package private) static <K,​V>
      Page<K,​V>
      createEmptyLeaf​(MVMap<K,​V> map)
      Create a new, empty leaf page.
      (package private) static <K,​V>
      Page<K,​V>
      createEmptyNode​(MVMap<K,​V> map)
      Create a new, empty internal node page.
      K[] createKeyStorage​(int size)
      Create array for keys storage.
      (package private) static <K,​V>
      Page<K,​V>
      createLeaf​(MVMap<K,​V> map, K[] keys, V[] values, int memory)
      Create a new leaf page.
      static <K,​V>
      Page<K,​V>
      createNode​(MVMap<K,​V> map, K[] keys, Page.PageReference<K,​V>[] children, long totalCount, int memory)
      Create a new non-leaf page.
      static <K,​V>
      Page.PageReference<K,​V>[]
      createRefStorage​(int size)
      Create an array of page references.
      (package private) V[] createValueStorage​(int size)
      Create array for values storage.
      protected void dump​(java.lang.StringBuilder buff)
      Dump debug data for this page.
      (package private) abstract void expand​(int extraKeyCount, K[] extraKeys, V[] extraValues)
      Append additional key/value mappings to this Page.
      (package private) void expandKeys​(int extraKeyCount, K[] extraKeys)
      Expand the keys array.
      (package private) static <K,​V>
      V
      get​(Page<K,​V> p, K key)
      Get the value for the given key, or null if not found.
      abstract CursorPos<K,​V> getAppendCursorPos​(CursorPos<K,​V> cursorPos)
      Extend path from a given CursorPos chain to "append point" in a B-tree, rooted at this Page.
      abstract Page<K,​V> getChildPage​(int index)
      Get the child page at the given index.
      abstract long getChildPagePos​(int index)
      Get the position of the child.
      (package private) abstract long getCounts​(int index)
      Get the number of key-value pairs for a given child.
      long getDiskSpaceUsed()
      Amount of used disk space in persistent case including child pages.
      K getKey​(int index)
      Get the key at the given index.
      int getKeyCount()
      Get the number of keys in this page.
      int getMapId()
      Get the id of the page's owner map
      int getMemory()  
      abstract int getNodeType()  
      long getPos()
      Get the position of the page
      abstract CursorPos<K,​V> getPrependCursorPos​(CursorPos<K,​V> cursorPos)
      Extend path from a given CursorPos chain to "prepend point" in a B-tree, rooted at this Page.
      abstract int getRawChildPageCount()  
      abstract long getTotalCount()
      Get the total number of key-value pairs, including child pages.
      abstract V getValue​(int index)
      Get the value at the given index.
      private void initMemoryAccount​(int memoryCount)  
      (package private) void insertKey​(int index, K key)
      Insert a key into the key array
      abstract void insertLeaf​(int index, K key, V value)
      Insert a key-value pair into this leaf.
      abstract void insertNode​(int index, K key, Page<K,​V> childPage)
      Insert a child page into this node.
      boolean isComplete()  
      boolean isLeaf()
      Check whether this is a leaf page.
      protected boolean isPersistent()  
      boolean isRemoved()  
      boolean isSaved()  
      private boolean markAsRemoved()
      Mark this page as removed "in memory".
      private void read​(java.nio.ByteBuffer buff)
      Read the page from the buffer.
      (package private) static <K,​V>
      Page<K,​V>
      read​(java.nio.ByteBuffer buff, long pos, MVMap<K,​V> map)
      Read a page.
      protected abstract void readPayLoad​(java.nio.ByteBuffer buff)
      Read the page payload from the buffer.
      (package private) void recalculateMemory()
      Recalculate estimated memory used in persistent case.
      (package private) abstract void releaseSavedPages()
      Unlink the children recursively after all data is written.
      void remove​(int index)
      Remove the key and value (or child) at the given index.
      abstract int removeAllRecursive​(long version)
      Remove all page data recursively.
      int removePage​(long version)
      Make accounting changes (chunk occupancy or "unsaved" RAM), related to this page removal.
      abstract void setChild​(int index, Page<K,​V> c)
      Replace the child page.
      void setComplete()
      Called when done with copying page.
      void setKey​(int index, K key)
      Replace the key at an index in this page.
      abstract V setValue​(int index, V value)
      Replace the value at an index in this page.
      (package private) abstract Page<K,​V> split​(int at)
      Split the page.
      (package private) K[] splitKeys​(int aCount, int bCount)
      Split the current keys array into two arrays.
      java.lang.String toString()  
      protected int write​(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
      Store the page and update the position.
      protected abstract void writeChildren​(WriteBuffer buff, boolean withCounts)
      Write page children to the buff.
      (package private) abstract void writeUnsavedRecursive​(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
      Store this page and all children that are changed, in reverse order, and update the position and the children.
      protected abstract void writeValues​(WriteBuffer buff)
      Write values that the buffer contains to the buff.
      • Methods inherited from class java.lang.Object

        equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • map

        public final MVMap<K,​V> map
        Map this page belongs to
      • pos

        private volatile long pos
        Position of this page's saved image within a Chunk or 0 if this page has not been saved yet or 1 if this page has not been saved yet, but already removed This "removed" flag is to keep track of pages that concurrently changed while they are being stored, in which case the live bookkeeping needs to be aware of such cases. Field need to be volatile to avoid races between saving thread setting it and other thread reading it to access the page. On top of this update atomicity is required so removal mark and saved position can be set concurrently.
        See Also:
        for field format details
      • pageNo

        public int pageNo
        Sequential 0-based number of the page within containing chunk.
      • cachedCompare

        private int cachedCompare
        The last result of a find operation is cached.
      • memory

        private int memory
        The estimated memory used in persistent case, IN_MEMORY marker value otherwise.
      • diskSpaceUsed

        private int diskSpaceUsed
        Amount of used disk space by this page only in persistent case.
      • keys

        private K[] keys
        The keys.
      • posUpdater

        private static final java.util.concurrent.atomic.AtomicLongFieldUpdater<Page> posUpdater
        Updater for pos field, which can be updated when page is saved, but can be concurrently marked as removed
      • PAGE_MEMORY_CHILD

        static final int PAGE_MEMORY_CHILD
        The estimated number of bytes used per child entry.
        See Also:
        Constant Field Values
      • PAGE_MEMORY

        private static final int PAGE_MEMORY
        The estimated number of bytes used per base page.
        See Also:
        Constant Field Values
      • PAGE_NODE_MEMORY

        static final int PAGE_NODE_MEMORY
        The estimated number of bytes used per empty internal page object.
        See Also:
        Constant Field Values
      • PAGE_LEAF_MEMORY

        static final int PAGE_LEAF_MEMORY
        The estimated number of bytes used per empty leaf page.
        See Also:
        Constant Field Values
      • IN_MEMORY

        private static final int IN_MEMORY
        Marker value for memory field, meaning that memory accounting is replaced by key count.
        See Also:
        Constant Field Values
    • Method Detail

      • createEmptyLeaf

        static <K,​V> Page<K,​V> createEmptyLeaf​(MVMap<K,​V> map)
        Create a new, empty leaf page.
        Type Parameters:
        K - key type
        V - value type
        Parameters:
        map - the map
        Returns:
        the new page
      • createEmptyNode

        static <K,​V> Page<K,​V> createEmptyNode​(MVMap<K,​V> map)
        Create a new, empty internal node page.
        Type Parameters:
        K - key type
        V - value type
        Parameters:
        map - the map
        Returns:
        the new page
      • createNode

        public static <K,​V> Page<K,​V> createNode​(MVMap<K,​V> map,
                                                             K[] keys,
                                                             Page.PageReference<K,​V>[] children,
                                                             long totalCount,
                                                             int memory)
        Create a new non-leaf page. The arrays are not cloned.
        Type Parameters:
        K - the key class
        V - the value class
        Parameters:
        map - the map
        keys - the keys
        children - the child page positions
        totalCount - the total number of keys
        memory - the memory used in bytes
        Returns:
        the page
      • createLeaf

        static <K,​V> Page<K,​V> createLeaf​(MVMap<K,​V> map,
                                                      K[] keys,
                                                      V[] values,
                                                      int memory)
        Create a new leaf page. The arrays are not cloned.
        Type Parameters:
        K - key type
        V - value type
        Parameters:
        map - the map
        keys - the keys
        values - the values
        memory - the memory used in bytes
        Returns:
        the page
      • initMemoryAccount

        private void initMemoryAccount​(int memoryCount)
      • get

        static <K,​V> V get​(Page<K,​V> p,
                                 K key)
        Get the value for the given key, or null if not found. Search is done in the tree rooted at given page.
        Type Parameters:
        K - key type
        V - value type
        Parameters:
        key - the key
        p - the root page
        Returns:
        the value, or null if not found
      • read

        static <K,​V> Page<K,​V> read​(java.nio.ByteBuffer buff,
                                                long pos,
                                                MVMap<K,​V> map)
        Read a page.
        Type Parameters:
        K - key type
        V - value type
        Parameters:
        buff - ByteBuffer containing serialized page info
        pos - the position
        map - the map
        Returns:
        the page
      • getMapId

        public final int getMapId()
        Get the id of the page's owner map
        Returns:
        id
      • copy

        abstract Page<K,​V> copy​(MVMap<K,​V> map,
                                      boolean eraseChildrenRefs)
        Create a copy of this page with potentially different owning map. This is used exclusively during bulk map copying. Child page references for nodes are cleared (re-pointed to an empty page) to be filled-in later to copying procedure. This way it can be saved mid-process without tree integrity violation
        Parameters:
        map - new map to own resulting page
        eraseChildrenRefs - whether cloned Page should have no child references or keep originals
        Returns:
        the page
      • getKey

        public K getKey​(int index)
        Get the key at the given index.
        Parameters:
        index - the index
        Returns:
        the key
      • getChildPage

        public abstract Page<K,​V> getChildPage​(int index)
        Get the child page at the given index.
        Parameters:
        index - the index
        Returns:
        the child page
      • getChildPagePos

        public abstract long getChildPagePos​(int index)
        Get the position of the child.
        Parameters:
        index - the index
        Returns:
        the position
      • getValue

        public abstract V getValue​(int index)
        Get the value at the given index.
        Parameters:
        index - the index
        Returns:
        the value
      • getKeyCount

        public final int getKeyCount()
        Get the number of keys in this page.
        Returns:
        the number of keys
      • isLeaf

        public final boolean isLeaf()
        Check whether this is a leaf page.
        Returns:
        true if it is a leaf
      • getNodeType

        public abstract int getNodeType()
      • getPos

        public final long getPos()
        Get the position of the page
        Returns:
        the position
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • dump

        protected void dump​(java.lang.StringBuilder buff)
        Dump debug data for this page.
        Parameters:
        buff - append buffer
      • copy

        public final Page<K,​V> copy()
        Create a copy of this page.
        Returns:
        a mutable copy of this page
      • clone

        protected final Page<K,​V> clone()
        Overrides:
        clone in class java.lang.Object
      • binarySearch

        int binarySearch​(K key)
        Search the key in this page using a binary search. Instead of always starting the search in the middle, the last found index is cached.

        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 in this page. See also Arrays.binarySearch.

        Parameters:
        key - the key
        Returns:
        the value or null
      • split

        abstract Page<K,​V> split​(int at)
        Split the page. This modifies the current page.
        Parameters:
        at - the split index
        Returns:
        the page with the entries after the split index
      • splitKeys

        final K[] splitKeys​(int aCount,
                            int bCount)
        Split the current keys array into two arrays.
        Parameters:
        aCount - size of the first array.
        bCount - size of the second array/
        Returns:
        the second array.
      • expand

        abstract void expand​(int extraKeyCount,
                             K[] extraKeys,
                             V[] extraValues)
        Append additional key/value mappings to this Page. New mappings suppose to be in correct key order.
        Parameters:
        extraKeyCount - number of mappings to be added
        extraKeys - to be added
        extraValues - to be added
      • expandKeys

        final void expandKeys​(int extraKeyCount,
                              K[] extraKeys)
        Expand the keys array.
        Parameters:
        extraKeyCount - number of extra key entries to create
        extraKeys - extra key values
      • getTotalCount

        public abstract long getTotalCount()
        Get the total number of key-value pairs, including child pages.
        Returns:
        the number of key-value pairs
      • getCounts

        abstract long getCounts​(int index)
        Get the number of key-value pairs for a given child.
        Parameters:
        index - the child index
        Returns:
        the descendant count
      • setChild

        public abstract void setChild​(int index,
                                      Page<K,​V> c)
        Replace the child page.
        Parameters:
        index - the index
        c - the new child page
      • setKey

        public final void setKey​(int index,
                                 K key)
        Replace the key at an index in this page.
        Parameters:
        index - the index
        key - the new key
      • setValue

        public abstract V setValue​(int index,
                                   V value)
        Replace the value at an index in this page.
        Parameters:
        index - the index
        value - the new value
        Returns:
        the old value
      • insertLeaf

        public abstract void insertLeaf​(int index,
                                        K key,
                                        V value)
        Insert a key-value pair into this leaf.
        Parameters:
        index - the index
        key - the key
        value - the value
      • insertNode

        public abstract void insertNode​(int index,
                                        K key,
                                        Page<K,​V> childPage)
        Insert a child page into this node.
        Parameters:
        index - the index
        key - the key
        childPage - the child page
      • insertKey

        final void insertKey​(int index,
                             K key)
        Insert a key into the key array
        Parameters:
        index - index to insert at
        key - the key value
      • remove

        public void remove​(int index)
        Remove the key and value (or child) at the given index.
        Parameters:
        index - the index
      • read

        private void read​(java.nio.ByteBuffer buff)
        Read the page from the buffer.
        Parameters:
        buff - the buffer to read from
      • readPayLoad

        protected abstract void readPayLoad​(java.nio.ByteBuffer buff)
        Read the page payload from the buffer.
        Parameters:
        buff - the buffer
      • isSaved

        public final boolean isSaved()
      • isRemoved

        public final boolean isRemoved()
      • markAsRemoved

        private boolean markAsRemoved()
        Mark this page as removed "in memory". That means that only adjustment of "unsaved memory" amount is required. On the other hand, if page was persisted, it's removal should be reflected in occupancy of the containing chunk.
        Returns:
        true if it was marked by this call or has been marked already, false if page has been saved already.
      • write

        protected final int write​(Chunk chunk,
                                  WriteBuffer buff,
                                  java.util.List<java.lang.Long> toc)
        Store the page and update the position.
        Parameters:
        chunk - the chunk
        buff - the target buffer
        toc - prospective table of content
        Returns:
        the position of the buffer just after the type
      • writeValues

        protected abstract void writeValues​(WriteBuffer buff)
        Write values that the buffer contains to the buff.
        Parameters:
        buff - the target buffer
      • writeChildren

        protected abstract void writeChildren​(WriteBuffer buff,
                                              boolean withCounts)
        Write page children to the buff.
        Parameters:
        buff - the target buffer
        withCounts - true if the descendant counts should be written
      • writeUnsavedRecursive

        abstract void writeUnsavedRecursive​(Chunk chunk,
                                            WriteBuffer buff,
                                            java.util.List<java.lang.Long> toc)
        Store this page and all children that are changed, in reverse order, and update the position and the children.
        Parameters:
        chunk - the chunk
        buff - the target buffer
        toc - prospective table of content
      • releaseSavedPages

        abstract void releaseSavedPages()
        Unlink the children recursively after all data is written.
      • getRawChildPageCount

        public abstract int getRawChildPageCount()
      • isPersistent

        protected final boolean isPersistent()
      • getMemory

        public final int getMemory()
      • getDiskSpaceUsed

        public long getDiskSpaceUsed()
        Amount of used disk space in persistent case including child pages.
        Returns:
        amount of used disk space in persistent case
      • addMemory

        final void addMemory​(int mem)
        Increase estimated memory used in persistent case.
        Parameters:
        mem - additional memory size.
      • recalculateMemory

        final void recalculateMemory()
        Recalculate estimated memory used in persistent case.
      • calculateMemory

        protected int calculateMemory()
        Calculate estimated memory used in persistent case.
        Returns:
        memory in bytes
      • isComplete

        public boolean isComplete()
      • setComplete

        public void setComplete()
        Called when done with copying page.
      • removePage

        public final int removePage​(long version)
        Make accounting changes (chunk occupancy or "unsaved" RAM), related to this page removal.
        Parameters:
        version - at which page was removed
        Returns:
        amount (negative), by which "unsaved memory" should be adjusted, if page is unsaved one, and 0 for page that was already saved, or in case of non-persistent map
      • getPrependCursorPos

        public abstract CursorPos<K,​V> getPrependCursorPos​(CursorPos<K,​V> cursorPos)
        Extend path from a given CursorPos chain to "prepend point" in a B-tree, rooted at this Page.
        Parameters:
        cursorPos - presumably pointing to this Page (null if real root), to build upon
        Returns:
        new head of the CursorPos chain
      • getAppendCursorPos

        public abstract CursorPos<K,​V> getAppendCursorPos​(CursorPos<K,​V> cursorPos)
        Extend path from a given CursorPos chain to "append point" in a B-tree, rooted at this Page.
        Parameters:
        cursorPos - presumably pointing to this Page (null if real root), to build upon
        Returns:
        new head of the CursorPos chain
      • removeAllRecursive

        public abstract int removeAllRecursive​(long version)
        Remove all page data recursively.
        Parameters:
        version - at which page got removed
        Returns:
        adjustment for "unsaved memory" amount
      • createKeyStorage

        public final K[] createKeyStorage​(int size)
        Create array for keys storage.
        Parameters:
        size - number of entries
        Returns:
        values array
      • createValueStorage

        final V[] createValueStorage​(int size)
        Create array for values storage.
        Parameters:
        size - number of entries
        Returns:
        values array
      • createRefStorage

        public static <K,​V> Page.PageReference<K,​V>[] createRefStorage​(int size)
        Create an array of page references.
        Type Parameters:
        K - the key class
        V - the value class
        Parameters:
        size - the number of entries
        Returns:
        the array