Class BranchControlRow
- java.lang.Object
-
- org.apache.derby.impl.store.access.btree.ControlRow
-
- 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
Fields Modifier and Type Field Description (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
Constructors Constructor Description BranchControlRow()
No arg constructor.BranchControlRow(OpenBTree open_btree, Page page, int level, ControlRow parent, boolean isRoot, long left_child)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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
-
-
-
-
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 classControlRow
-
isLeftmostLeaf
public boolean isLeftmostLeaf() throws StandardException
Is the current page the leftmost leaf of tree?- Specified by:
isLeftmostLeaf
in classControlRow
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- 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: This method also performs the consistency checks that are common to both leaf and branch pages (see ControlRow.checkGeneric).- Specified by:
checkConsistency
in classControlRow
- 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 classControlRow
- 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.
This
- 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 classControlRow
- 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 classControlRow
- 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 classControlRow
- Returns:
- Newly allocated template.
- Throws:
StandardException
- Standard exception policy.
-
toString
public java.lang.String toString()
The standard toString.- Overrides:
toString
in classControlRow
-
-