org.apache.derby.impl.store.access.btree
Class BranchControlRow

java.lang.Object
  extended by org.apache.derby.impl.store.access.btree.ControlRow
      extended by org.apache.derby.impl.store.access.btree.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 Summary
(package private)  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.
private static int CR_COLID_LAST
           
private static int CR_LEFTCHILD
           
protected static FormatableBitSet CR_LEFTCHILD_BITMAP
          bit sets used to fetch single columns at a time.
private static int CR_NCOLUMNS
           
protected  SQLLongint left_child_page
           
 
Fields inherited from class org.apache.derby.impl.store.access.btree.ControlRow
CR_COLID_FIRST, CR_CONGLOM_BITSET, CR_CONGLOM_COLID, CR_ISROOT_BITSET, CR_ISROOT_COLID, CR_LEFTSIB_BITSET, CR_LEFTSIB_COLID, CR_LEVEL_BITSET, CR_LEVEL_COLID, CR_PARENT_BITSET, CR_PARENT_COLID, CR_RIGHTSIB_BITSET, CR_RIGHTSIB_COLID, CR_SLOT, CR_VERSION_BITSET, CR_VERSION_COLID, fetchDesc, last_search_result, page, row, scratch_row, SPLIT_FLAG_FIRST_IN_TABLE, SPLIT_FLAG_FIRST_ON_PAGE, SPLIT_FLAG_LAST_IN_TABLE, SPLIT_FLAG_LAST_ON_PAGE, use_last_search_result_hint
 
Constructor Summary
BranchControlRow()
          No arg constructor.
BranchControlRow(OpenBTree open_btree, Page page, int level, ControlRow parent, boolean isRoot, long left_child)
           
 
Method Summary
private static BranchControlRow allocate(OpenBTree open_btree, ControlRow leftchild, int level, ControlRow parent)
          Allocate a new leaf page to the conglomerate.
private  void checkChildOrderAgainstRowOrder(OpenBTree btree)
           
private  int checkChildren(OpenBTree btree)
           
 int checkConsistency(OpenBTree btree, ControlRow parent, boolean check_other_pages)
          Perform consistency checks for a branch page.
protected  void controlRowInit()
          Perform page specific initialization.
private  void fixChildrensParents(OpenBTree btree, ControlRow leftchild)
          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.
protected  ControlRow getChildPageAtSlot(OpenBTree open_btree, int slot)
           
private  long getChildPageIdAtSlot(OpenBTree btree, int slot)
           
 ControlRow getLeftChild(OpenBTree open_btree)
          Return the left child pointer for the page.
(package private)  long getLeftChildPageno()
          Return the left child page number for the page.
protected  int getNumberOfControlRowColumns()
          Get the number of columns in the control row.
protected  ControlRow getRightChild(OpenBTree open_btree)
          Return the right child pointer for the page.
 DataValueDescriptor[] getRowTemplate(OpenBTree open_btree)
          Return a new template for reading a data row from the current page.
 int getTypeFormatId()
          Return my format identifier.
private static void growRoot(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow root)
          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.
 boolean isLeftmostLeaf()
          Is the current page the leftmost leaf of tree?
 boolean isRightmostLeaf()
          Is the current page the rightmost leaf of tree?
 void printTree(OpenBTree btree)
          Recursively print the tree starting at current node in tree.
static long restartSplitFor(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow parent, ControlRow child, DataValueDescriptor[] newbranchrow, DataValueDescriptor[] splitrow, int flag)
           
 ControlRow search(SearchParameters sp)
          Perform a recursive search, ultimately returning the latched leaf page and row slot after which the given key belongs.
protected  ControlRow searchLeft(OpenBTree btree)
          Search and return the left most leaf page.
protected  ControlRow searchRight(OpenBTree btree)
          Search and return the right most leaf page.
protected  void setLeftChild(ControlRow leftchild)
           
protected  void setLeftChildPageno(long leftchild_pageno)
           
protected  boolean shrinkFor(OpenBTree open_btree, DataValueDescriptor[] shrink_key)
          Perform a recursive shrink operation for the key.
protected  long splitFor(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow parent, DataValueDescriptor[] splitrow, int flag)
          Perform a top down split pass making room for the the key in "row".
 java.lang.String toString()
          The standard toString.
 
Methods inherited from class org.apache.derby.impl.store.access.btree.ControlRow
auxObjectInvalidated, checkGeneric, checkRowOrder, checkSiblings, compareIndexRowFromPageToKey, compareIndexRowToKey, compareRowsOnSiblings, debugPage, get, get, getConglom, getControlRowForPage, getIsRoot, getLeftSibling, getleftSiblingPageNumber, getLevel, getNoWait, getPage, getParentPageNumber, getRightSibling, getrightSiblingPageNumber, getRow, getVersion, linkRight, release, searchForEntry, searchForEntryBackward, setIsRoot, setLeftSibling, setLevel, setParent, setRightSibling, setVersion, unlink
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

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

private static final int CR_LEFTCHILD
See Also:
Constant Field Values

CR_COLID_LAST

private static final int CR_COLID_LAST
See Also:
Constant Field Values

CR_NCOLUMNS

private static final int CR_NCOLUMNS
See Also:
Constant Field Values

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.


BranchControlRow

public BranchControlRow(OpenBTree open_btree,
                        Page page,
                        int level,
                        ControlRow parent,
                        boolean isRoot,
                        long left_child)
                 throws StandardException
Throws:
StandardException
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.

restartSplitFor

public static long restartSplitFor(OpenBTree open_btree,
                                   DataValueDescriptor[] template,
                                   BranchControlRow parent,
                                   ControlRow child,
                                   DataValueDescriptor[] newbranchrow,
                                   DataValueDescriptor[] splitrow,
                                   int flag)
                            throws StandardException
Throws:
StandardException

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.

    checkChildren

    private int checkChildren(OpenBTree btree)
                       throws StandardException
    Throws:
    StandardException

    checkChildOrderAgainstRowOrder

    private void checkChildOrderAgainstRowOrder(OpenBTree btree)
                                         throws StandardException
    Throws:
    StandardException

    printTree

    public void printTree(OpenBTree btree)
                   throws StandardException
    Recursively print the tree starting at current node in tree.

    Specified by:
    printTree in class ControlRow
    Parameters:
    btree - the open btree to print.
    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

    allocate

    private static BranchControlRow allocate(OpenBTree open_btree,
                                             ControlRow leftchild,
                                             int level,
                                             ControlRow parent)
                                      throws StandardException
    Allocate a new leaf page to the conglomerate.

    Throws:
    StandardException - Standard exception policy.

    setLeftChildPageno

    protected void setLeftChildPageno(long leftchild_pageno)
                               throws StandardException
    Throws:
    StandardException

    setLeftChild

    protected void setLeftChild(ControlRow leftchild)
                         throws StandardException
    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.

    Throws:
    StandardException

    getChildPageIdAtSlot

    private long getChildPageIdAtSlot(OpenBTree btree,
                                      int slot)
                               throws StandardException
    Throws:
    StandardException

    getChildPageAtSlot

    protected ControlRow getChildPageAtSlot(OpenBTree open_btree,
                                            int slot)
                                     throws StandardException
    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

    Built on Thu 2011-03-10 11:54:14+0000, from revision ???

    Apache Derby V10.6 Internals - Copyright © 2004,2007 The Apache Software Foundation. All Rights Reserved.