Package org.apache.derby.impl.store.access.btree

Class BranchControlRow

  • All Implemented Interfaces:
    TypedFormat, AuxObject
    public class BranchControlRow
extends ControlRow
    A branch row contains key fields and the pointer to the child page.

    • Field Detail

      • left_child_page

        protected SQLLongint left_child_page

      • child_pageno_buf

        transient SQLLongint child_pageno_buf
        Only allocate one child_pageno_buf to read the page pointer field into, then cache to "empty" object for reuse by the page itself.

      • CR_LEFTCHILD_BITMAP

        protected static final FormatableBitSet CR_LEFTCHILD_BITMAP
        bit sets used to fetch single columns at a time.

    • Constructor Detail

      • BranchControlRow

        public BranchControlRow()
        No arg constructor.

        Public no arg constructor is for the monitor to call for format id implementation, it should not be called for any other reason.

    • Method Detail

      • controlRowInit

        protected final void controlRowInit()
        Perform page specific initialization.

        Specified by:
        controlRowInit in class ControlRow

      • isLeftmostLeaf

        public boolean isLeftmostLeaf()
                       throws StandardException
        Is the current page the leftmost leaf of tree?

        Specified by:
        isLeftmostLeaf in class ControlRow
        Returns:
        true if the current page is the leftmost leaf of the tree, else return false.
        Throws:
        StandardException - Standard exception policy.

      • isRightmostLeaf

        public boolean isRightmostLeaf()
                        throws StandardException
        Is the current page the rightmost leaf of tree?

        Specified by:
        isRightmostLeaf in class ControlRow
        Returns:
        true if the current page is the rightmost leaf of the tree, else return false.
        Throws:
        StandardException - Standard exception policy.

      • getNumberOfControlRowColumns

        protected final int getNumberOfControlRowColumns()
        Get the number of columns in the control row.

        Control rows all share the first columns as defined by this class and then add columns to the end of the control row. For instance a branch control row add a child page pointer field.

        Specified by:
        getNumberOfControlRowColumns in class ControlRow
        Returns:
        The total number of columns in the control row.

      • search

        public ControlRow search​(SearchParameters sp)
                  throws StandardException
        Perform a recursive search, ultimately returning the latched leaf page and row slot after which the given key belongs. The slot is returned in the result structure. If the key exists on the page, the result.exact will be true. Otherwise, result.exact will be false, and the row slot returned will be the one immediately preceding the position at which the key belongs.
        Specified by:
        search in class ControlRow
        Throws:
        StandardException - Standard exception policy.

      • searchLeft

        protected ControlRow searchLeft​(OpenBTree btree)
                         throws StandardException
        Search and return the left most leaf page.

        Perform a recursive search, ultimately returning the leftmost leaf page which is the first leaf page in the leaf sibling chain. (This method might better be called getFirstLeafPage()).

        Specified by:
        searchLeft in class ControlRow
        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The leftmost leaf page.
        Throws:
        StandardException - Standard exception policy.

      • searchRight

        protected ControlRow searchRight​(OpenBTree btree)
                          throws StandardException
        Search and return the right most leaf page.

        Perform a recursive search, ultimately returning the rightmost leaf page which is the last leaf page in the leaf sibling chain. (This method might better be called getLastLeafPage()).

        Specified by:
        searchRight in class ControlRow
        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The rightmost leaf page.
        Throws:
        StandardException - Standard exception policy.

      • shrinkFor

        protected boolean shrinkFor​(OpenBTree open_btree,
                            DataValueDescriptor[] shrink_key)
                     throws StandardException
        Perform a recursive shrink operation for the key. If this method returns true, the caller should remove the corresponding entry for the page. This routine is not guaranteed to successfully shrink anything. The page lead to by the key might turn out not to be empty by the time shrink gets there, and shrinks will give up if there is a deadlock.

        The receiver page must be latched on entry and is returned latched.

        Specified by:
        shrinkFor in class ControlRow
        Throws:
        StandardException - Standard exception policy.

      • splitFor

        protected long splitFor​(OpenBTree open_btree,
                        DataValueDescriptor[] template,
                        BranchControlRow parent,
                        DataValueDescriptor[] splitrow,
                        int flag)
                 throws StandardException
        Perform a top down split pass making room for the the key in "row".

        Perform a split such that a subsequent call to insert given the argument index row will likely find room for it. Since latches are released the client must code for the case where another user has grabbed the space made available by the split pass and be ready to do another split.

        Latches: o PARENT : is latched on entry (unless the split is the root then there is no parent. o THISBRANCH: the current page is latched on entry. o CHILD : latch the child page which will be pointed at by the left child pointer of the new page. RESOLVE (mikem) -see comments below o NEWPAGE : Allocate and latch new page. o CHILD : release. (RESOLVE) o fixparents: latch pages and reset their parent pointers. Conditionally fix up the parent links on the pages pointed at by the newly allocated page. First get latch and release on the left child page and then loop through slots on NEWPAGE, from left to right getting and releasing latches.

        Specified by:
        splitFor in class ControlRow
        Parameters:
        open_btree - The open btree to associate latches with.
        template - A scratch area to use while searching for split pass.
        parent - The parent page of the current page in the split pass. starts at null for root.
        splitrow - The key to make room for during the split pass.
        flag - A flag used to direct where point of split should be chosen.
        Returns:
        page number of the newly allocated leaf page created by split.
        Throws:
        StandardException - Standard exception policy.

      • checkConsistency

        public int checkConsistency​(OpenBTree btree,
                            ControlRow parent,
                            boolean check_other_pages)
                     throws StandardException
        Perform consistency checks for a branch page. The checks specific to a branch page are:
      • The rows on the page are indeed branch rows, and they all have the correct number of fields (which is the b-tree's key fields plus one for the child page number.
      • The child pages pointed to by the left child pointer and the index rows are linked together in the same order that they appear on the page.
      • The child pages themselves are all consistent.
        • This method also performs the consistency checks that are common to both leaf and branch pages (see ControlRow.checkGeneric).
        Specified by:
        checkConsistency in class ControlRow
        Parameters:
        btree - The open btree to associate latches/locks with.
        parent - The parent page of this page, "null" if this page is root or if not maintaining parent links.
        check_other_pages - Should the consistency check go to other pages (this option breaks the latch protocol).
        Returns:
        The identifier to be used to open the conglomerate later.
        Throws:
        StandardException - Standard exception policy.

      • growRoot

        private static void growRoot​(OpenBTree open_btree,
                             DataValueDescriptor[] template,
                             BranchControlRow root)
                      throws StandardException
        Add a level to the tree by moving the current branch-root page up one level and adding a new page as it's left child. On exit the current root page remains the root of the tree.

        On entry, the current branch root page is expected to be latched. On exit, all latches will have been released.

        Latch order: o ROOT: on entry current root is latched. No other latches should be held. o ROOT_OLDCHILD: Get and Latch root's left child page. o ROOT_NEWCHILD: Allocate a new branch page with latch. o Conditionally fix up the parent links on the pages pointed at by the newly allocated page. Loop through slots on ROOT_NEWCHILD, from left to right getting and releasing latches. Note that fixChildrensParents() must not latch the leftchild as ROOT_OLDCHILD is already latched. RESOLVE: (mikem) does order of release matter. o ROOT : released. o ROOT_NEWCHILD: released. o ROOT_OLDCHILD: released.

        Throws:
        StandardException

      • fixChildrensParents

        private void fixChildrensParents​(OpenBTree btree,
                                 ControlRow leftchild)
                          throws StandardException
        A branch page that has just been allocated as part of a split has index rows and a left child pointer that were copied from another page. The parent link on the corresponding pages will still point to the original page. This method fixes their parent pointers so that they point to the curren page like they're supposed to.

        Note that maintaining the parent link is kind of a pain, and will slow down applications. It's only needed for consistency checks, so we may want to have implementations that don't bother to maintain it.

        This

        Throws:
        StandardException

      • getLeftChild

        public ControlRow getLeftChild​(OpenBTree open_btree)
                        throws StandardException
        Return the left child pointer for the page.

        Leaf pages don't have children, so they override this and return null.

        Specified by:
        getLeftChild in class ControlRow
        Parameters:
        open_btree - The open btree to associate latches/locks with.
        Returns:
        The page which is the leftmost child of this page.
        Throws:
        StandardException - Standard exception policy.

      • getRightChild

        protected ControlRow getRightChild​(OpenBTree open_btree)
                            throws StandardException
        Return the right child pointer for the page.

        Leaf pages don't have children, so they override this and return null.

        Specified by:
        getRightChild in class ControlRow
        Parameters:
        open_btree - The open btree to associate latches/locks with.
        Returns:
        The page which is the rightmost child of this page.
        Throws:
        StandardException - Standard exception policy.

      • getLeftChildPageno

        long getLeftChildPageno()
                 throws StandardException
        Return the left child page number for the page. Leaf pages don't have left children, so they override this and return null.
        Throws:
        StandardException

      • getTypeFormatId

        public int getTypeFormatId()
        Return my format identifier.
        Returns:
        The identifier. (A UUID stuffed in an array of 16 bytes).
        See Also:
        TypedFormat.getTypeFormatId()

      • getRowTemplate

        public DataValueDescriptor[] getRowTemplate​(OpenBTree open_btree)
                                     throws StandardException
        Return a new template for reading a data row from the current page.

        Default implementation for rows which are the same as the conglomerates template, sub-classes can alter if underlying template is different (for instance branch rows add an extra field at the end).

        Overrides:
        getRowTemplate in class ControlRow
        Returns:
        Newly allocated template.
        Throws:
        StandardException - Standard exception policy.

      • toString

        public java.lang.String toString()
        The standard toString.
        Overrides:
        toString in class ControlRow