Class ControlRow
- java.lang.Object
-
- org.apache.derby.impl.store.access.btree.ControlRow
-
- All Implemented Interfaces:
TypedFormat
,AuxObject
- Direct Known Subclasses:
BranchControlRow
,LeafControlRow
public abstract class ControlRow extends java.lang.Object implements AuxObject, TypedFormat
Base class for leaf and branch control rows.Concurrency Notes
All access through control rows is serialized by an exclusive latch on the page the control row is for. The page is latched when the control row is "gotten" (ControlRow#Get), and unlatched when the control row is released (ControlRow#release).
To Do List
- [NOTE1] The code is arranged to fault in fields from the row as necessary. many of the fields of a control row are rarely used (left sibling, parent). The accessors fault in the underlying column only when requested by allocating the appropriate object and calling fetchFromSlot and only fetching the requested field.
- [NOTE2] Currently, all the fields of the control row are stored as StorableU8s for simplicity. This is too few bits to hold the long page numbers, and too many to hold the version, level, and isRoot flag. Some consideration will have to be given to the appropriate storage format for these values.
- [NOTE3] The implementation relies on the existance of page "auxiliary" pointers which keep Object versions of the control row.
-
-
Field Summary
Fields Modifier and Type Field Description private BTree
btree
A copy of the Conglomerate that describes the owning conglom.protected static int
CR_COLID_FIRST
Column number assignments for columns of the control row.protected static int
CR_COLID_LAST
protected static FormatableBitSet
CR_CONGLOM_BITSET
protected static int
CR_CONGLOM_COLID
protected static FormatableBitSet
CR_ISROOT_BITSET
protected static int
CR_ISROOT_COLID
protected static FormatableBitSet
CR_LEFTSIB_BITSET
protected static int
CR_LEFTSIB_COLID
protected static FormatableBitSet
CR_LEVEL_BITSET
protected static int
CR_LEVEL_COLID
protected static int
CR_NCOLUMNS
protected static FormatableBitSet
CR_PARENT_BITSET
protected static int
CR_PARENT_COLID
protected static FormatableBitSet
CR_RIGHTSIB_BITSET
protected static int
CR_RIGHTSIB_COLID
protected static int
CR_SLOT
The slot at which all control rows reside.protected static FormatableBitSet
CR_VERSION_BITSET
bit sets used to fetch single columns at a time.protected static int
CR_VERSION_COLID
protected FetchDescriptor
fetchDesc
FetchDescriptor used to replace fetchFieldFromSlot() calls.private SQLLongint
isRoot
Is this page the root of the btree?protected int
last_search_result
In memory hint about where to begin the binary search to find a key on the the current control page.private SQLLongint
leftSiblingPageNumber
Pointer to page which is "left" at the current level.private SQLLongint
level
The level of the btree.protected Page
page
The page that this control row describes.private SQLLongint
parentPageNumber
The parent page of the current page.private SQLLongint
rightSiblingPageNumber
Pointer to page which is "right" at the current level.protected DataValueDescriptor[]
row
The page that this control row describes.protected DataValueDescriptor[]
scratch_row
row used to replace fetchFieldFromSlot() calls.static int
SPLIT_FLAG_FIRST_IN_TABLE
static int
SPLIT_FLAG_FIRST_ON_PAGE
static int
SPLIT_FLAG_LAST_IN_TABLE
static int
SPLIT_FLAG_LAST_ON_PAGE
Values passed in the flag argument to splitFor.protected boolean
use_last_search_result_hint
In memory hint about whether to use the last_search_result hint during search.private StorableFormatId
version
Version indentifier of the control row within the page.
-
Constructor Summary
Constructors Modifier Constructor Description protected
ControlRow()
No arg constructor.protected
ControlRow(ContainerHandle container, Page page)
Constructor for making a control row for an existing page.protected
ControlRow(OpenBTree btree, Page page, int level, ControlRow parent, boolean isRoot)
Constructor for making a new control row as part of allocating a new page.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
auxObjectInvalidated()
Called when the page is being evicted from cache or when a rollback happened on the page and may possibly have changed the control row's valueprotected abstract int
checkConsistency(OpenBTree btree, ControlRow parent, boolean check_other_pages)
Check consistency of the page and its children, returning the number of pages seen, and throwing errors if inconsistencies are found.protected void
checkGeneric(OpenBTree btree, ControlRow parent, boolean check_other_pages)
Perform consistency checks which are common to all pages that derive from ControlRow (both leaf and branch pages).protected boolean
checkRowOrder(OpenBTree btree, ControlRow parent)
Check that all rows on the page are in order.protected void
checkSiblings(OpenBTree btree)
Perform checks on the siblings of this page: make sure that they're at the same level as this page, that they're mutually linked together, and that the first/last keys on sibling pages are in order.static int
compareIndexRowFromPageToKey(ControlRow indexpage, int slot, DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc)
Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1 depending on whether the first row (indexrow) is less than, equal to, or greater than the second (key).static int
compareIndexRowToKey(DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc)
protected boolean
compareRowsOnSiblings(OpenBTree btree, ControlRow left_sib, ControlRow right_sib)
protected abstract void
controlRowInit()
Perform page specific initialization.java.lang.String
debugPage(OpenBTree open_btree)
Dump complete information about control row and rows on the page.static ControlRow
get(ContainerHandle container, long pageNumber)
static ControlRow
get(OpenBTree open_btree, long pageNumber)
Get the control row from the given page in the b-tree.BTree
getConglom(int format_id)
Get format id information for row on page.protected static ControlRow
getControlRowForPage(ContainerHandle container, Page page)
protected boolean
getIsRoot()
protected abstract ControlRow
getLeftChild(OpenBTree btree)
Return the left child pointer for the page.ControlRow
getLeftSibling(OpenBTree btree)
Get the control row for this page's left sibling, or null if there is no left sibling (which probably means it's the leftmost page at its level).long
getleftSiblingPageNumber()
Get the page number of the left sibling.protected int
getLevel()
static ControlRow
getNoWait(OpenBTree open_btree, long pageNumber)
Get the control row for the given page if the latch on the page can be obtained without waiting, else return null.protected abstract int
getNumberOfControlRowColumns()
Get the number of columns in the control row.Page
getPage()
protected long
getParentPageNumber()
Get the page number of the parent, if it's being maintained.protected abstract ControlRow
getRightChild(OpenBTree btree)
Return the right child pointer for the page.protected ControlRow
getRightSibling(OpenBTree open_btree)
Return the control row for this page's right sibling.protected long
getrightSiblingPageNumber()
Get the page number of the right sibling.protected DataValueDescriptor[]
getRow()
Get the row.DataValueDescriptor[]
getRowTemplate(OpenBTree open_btree)
Return a new template for reading a data row from the current page.protected int
getVersion()
Get version of the control row.abstract boolean
isLeftmostLeaf()
Is the current page the leftmost leaf of tree?abstract boolean
isRightmostLeaf()
Is the current page the rightmost leaf of tree?(package private) void
linkRight(OpenBTree btree, ControlRow target)
Link this page to the right of the target page.abstract void
printTree(OpenBTree btree)
Recursively print the tree starting at current node in tree.void
release()
Release this control row's resources.abstract ControlRow
search(SearchParameters search_params)
Perform a recursive search, ultimately returning the latched leaf page and row slot after which the given key belongs.protected void
searchForEntry(SearchParameters params)
Search this index page.protected void
searchForEntryBackward(SearchParameters params)
protected abstract ControlRow
searchLeft(OpenBTree btree)
Search and return the left most leaf page.protected abstract ControlRow
searchRight(OpenBTree btree)
Search and return the right most leaf page.protected void
setIsRoot(boolean isRoot)
protected void
setLeftSibling(ControlRow leftsib)
protected void
setLevel(int newlevel)
(package private) void
setParent(long parent)
protected void
setRightSibling(ControlRow rightsib)
protected void
setVersion(int version)
Set version of the control row.protected abstract boolean
shrinkFor(OpenBTree btree, DataValueDescriptor[] key)
Perform a recursive shrink operation for the key.protected abstract long
splitFor(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow parentpage, DataValueDescriptor[] row, int flag)
Perform a top down split pass making room for the the key in "row".java.lang.String
toString()
The standard toString().(package private) boolean
unlink(OpenBTree btree)
Unlink this page from its siblings.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface org.apache.derby.iapi.services.io.TypedFormat
getTypeFormatId
-
-
-
-
Field Detail
-
version
private StorableFormatId version
Version indentifier of the control row within the page.This is the format id of the control row. The format id is currently one of either StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_ID or StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_ID.
-
leftSiblingPageNumber
private SQLLongint leftSiblingPageNumber
Pointer to page which is "left" at the current level.Currently all pages at a level are doubly linked. The leftmost page in a level has a leftSiblingPageNumber == ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which is left must precede the first key value on the current page.
-
rightSiblingPageNumber
private SQLLongint rightSiblingPageNumber
Pointer to page which is "right" at the current level.Currently all pages at a level are doubly linked. The rightmost page in a level has a rightSiblingPageNumber == ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which is right of the current page must follow the last key value on the current page.
-
parentPageNumber
private SQLLongint parentPageNumber
The parent page of the current page.For consistency checking it is useful to maintain the parentPageNumber field of the current page. The root page has a value of ContainerHandle.INVALID_PAGE_NUMBER in it's parentPageNumber field.
RESOLVE (mikem) - we need to come up with some way to not maintain these, maybe by providing a property on secondary index or a different 2nd index.
-
level
private SQLLongint level
The level of the btree.The leaf level of the btree is 0. The first branch level (parent level of the leaf), is level 1. The height of the btree is (level + 1).
The smallest btree is a one page btree with only a leaf, and no branch pages.
-
isRoot
private SQLLongint isRoot
Is this page the root of the btree?Currently "1" if the page is the root page, else "0".
RESOLVE (mikem) When real datatype come about, this value should probably be just a bit in some status word.
-
btree
private BTree btree
A copy of the Conglomerate that describes the owning conglom.This information is used during logical undo to get the type information so that rows can be compared and searched for. We may be able to get away with a subset of the information stored in the conglomerate.
RESOLVE (mikem) - change this to only store the info on the root page.
-
page
protected Page page
The page that this control row describes.
-
row
protected DataValueDescriptor[] row
The page that this control row describes.
-
scratch_row
protected DataValueDescriptor[] scratch_row
row used to replace fetchFieldFromSlot() calls.
-
fetchDesc
protected FetchDescriptor fetchDesc
FetchDescriptor used to replace fetchFieldFromSlot() calls.
-
use_last_search_result_hint
protected transient boolean use_last_search_result_hint
In memory hint about whether to use the last_search_result hint during search.
-
last_search_result
protected transient int last_search_result
In memory hint about where to begin the binary search to find a key on the the current control page.
-
CR_COLID_FIRST
protected static final int CR_COLID_FIRST
Column number assignments for columns of the control row.The control row is stored as the first row in a btree page. The row is an array of columns. The Control row columns are the columns numbered from ControlRow.CR_COLID_FIRST through ControlRow.CR_COLID_LAST. The classes which implement the concrete derived classes of ControlRow may add columns to the control row, but they must be added after the ControlRow columns.
- See Also:
- Constant Field Values
-
CR_VERSION_COLID
protected static final int CR_VERSION_COLID
- See Also:
- Constant Field Values
-
CR_LEFTSIB_COLID
protected static final int CR_LEFTSIB_COLID
- See Also:
- Constant Field Values
-
CR_RIGHTSIB_COLID
protected static final int CR_RIGHTSIB_COLID
- See Also:
- Constant Field Values
-
CR_PARENT_COLID
protected static final int CR_PARENT_COLID
- See Also:
- Constant Field Values
-
CR_LEVEL_COLID
protected static final int CR_LEVEL_COLID
- See Also:
- Constant Field Values
-
CR_ISROOT_COLID
protected static final int CR_ISROOT_COLID
- See Also:
- Constant Field Values
-
CR_CONGLOM_COLID
protected static final int CR_CONGLOM_COLID
- See Also:
- Constant Field Values
-
CR_COLID_LAST
protected static final int CR_COLID_LAST
- See Also:
- Constant Field Values
-
CR_NCOLUMNS
protected static final int CR_NCOLUMNS
- See Also:
- Constant Field Values
-
CR_VERSION_BITSET
protected static final FormatableBitSet CR_VERSION_BITSET
bit sets used to fetch single columns at a time.
-
CR_LEFTSIB_BITSET
protected static final FormatableBitSet CR_LEFTSIB_BITSET
-
CR_RIGHTSIB_BITSET
protected static final FormatableBitSet CR_RIGHTSIB_BITSET
-
CR_PARENT_BITSET
protected static final FormatableBitSet CR_PARENT_BITSET
-
CR_LEVEL_BITSET
protected static final FormatableBitSet CR_LEVEL_BITSET
-
CR_ISROOT_BITSET
protected static final FormatableBitSet CR_ISROOT_BITSET
-
CR_CONGLOM_BITSET
protected static final FormatableBitSet CR_CONGLOM_BITSET
-
SPLIT_FLAG_LAST_ON_PAGE
public static final int SPLIT_FLAG_LAST_ON_PAGE
Values passed in the flag argument to splitFor.- See Also:
- Constant Field Values
-
SPLIT_FLAG_LAST_IN_TABLE
public static final int SPLIT_FLAG_LAST_IN_TABLE
- See Also:
- Constant Field Values
-
SPLIT_FLAG_FIRST_ON_PAGE
public static final int SPLIT_FLAG_FIRST_ON_PAGE
- See Also:
- Constant Field Values
-
SPLIT_FLAG_FIRST_IN_TABLE
public static final int SPLIT_FLAG_FIRST_IN_TABLE
- See Also:
- Constant Field Values
-
CR_SLOT
protected static final int CR_SLOT
The slot at which all control rows reside.- See Also:
- Constant Field Values
-
-
Constructor Detail
-
ControlRow
protected ControlRow()
No arg constructor.GetControlRowForPage() will call this constructor when it uses the monitor to create a control row dynamically given a given format id.
-
ControlRow
protected ControlRow(OpenBTree btree, Page page, int level, ControlRow parent, boolean isRoot) throws StandardException
Constructor for making a new control row as part of allocating a new page. Fills in all the fields but does not write them anywhere.Changes to this constructor will probably require changes to the corresponding accessor(s).
- Parameters:
btree
- Static information about the btree.page
- The page described by this control row.parent
- The parent page of this page, "null" if this page is root or if not maintaining parent links.isRoot
- Is this page the root of the tree?- Throws:
StandardException
- Standard exception policy.
-
ControlRow
protected ControlRow(ContainerHandle container, Page page) throws StandardException
Constructor for making a control row for an existing page.Not all the fields are filled in; their values will get faulted in from the page as necessary.
Classes which extend ControlRow must delegate to this constructor and may want to override it as well. Changes to this constructor will probably require changes to the corresponding accessor(s).
- Parameters:
container
- Open containerpage
- The page described by this control row.- Throws:
StandardException
- Standard exception policy.
-
-
Method Detail
-
getVersion
protected int getVersion() throws StandardException
Get version of the control row.Returns the version of the control row, faulting it in from the page if necessary.
- Returns:
- version of the control row.
- Throws:
StandardException
- Standard exception policy.
-
setVersion
protected void setVersion(int version) throws StandardException
Set version of the control row.Sets the version of the control row. Updates both the in-memory control row and the disk copy.
- Throws:
StandardException
- Standard exception policy.
-
getLeftSibling
public ControlRow getLeftSibling(OpenBTree btree) throws StandardException, WaitError
Get the control row for this page's left sibling, or null if there is no left sibling (which probably means it's the leftmost page at its level). Since right-to-left traversal of an index level is deadlock-prone, this method will only get get the left sibling if it can latch it without waiting.- Throws:
WaitError
- if the latch request would have had to wait.StandardException
- Standard exception policy.
-
setLeftSibling
protected void setLeftSibling(ControlRow leftsib) throws StandardException
- Throws:
StandardException
-
getRightSibling
protected ControlRow getRightSibling(OpenBTree open_btree) throws StandardException
Return the control row for this page's right sibling. Unlike getting the left sibling, it's ok to wait for the right sibling latch since left-to-right is the deadlock-free ordering.- Throws:
StandardException
- Standard exception policy.
-
setRightSibling
protected void setRightSibling(ControlRow rightsib) throws StandardException
- Throws:
StandardException
-
getleftSiblingPageNumber
public long getleftSiblingPageNumber() throws StandardException
Get the page number of the left sibling. Fault it's value in if it hasn't been yet.- Throws:
StandardException
- Standard exception policy.
-
getrightSiblingPageNumber
protected long getrightSiblingPageNumber() throws StandardException
Get the page number of the right sibling. Fault it's value in if it hasn't been yet.- Throws:
StandardException
- Standard exception policy.
-
getParentPageNumber
protected long getParentPageNumber() throws StandardException
Get the page number of the parent, if it's being maintained. Note that there is intentionally no way to get the control row for the parent page - the b-tree code NEVER traverses up the tree, even in consistency checks.- Throws:
StandardException
- Standard exception policy.
-
setParent
void setParent(long parent) throws StandardException
- Throws:
StandardException
-
getLevel
protected int getLevel() throws StandardException
- Throws:
StandardException
-
setLevel
protected void setLevel(int newlevel) throws StandardException
- Throws:
StandardException
-
getIsRoot
protected boolean getIsRoot() throws StandardException
- Throws:
StandardException
-
setIsRoot
protected void setIsRoot(boolean isRoot) throws StandardException
- Throws:
StandardException
-
getConglom
public BTree getConglom(int format_id) throws StandardException
Get format id information for row on page.Returns the format id information for a row on the page. faulting it in from the page if necessary.
- Returns:
- format id of a row on the page.
- Throws:
StandardException
- Standard exception policy.
-
get
public static ControlRow get(OpenBTree open_btree, long pageNumber) throws StandardException
Get the control row from the given page in the b-tree. The returned control row will be of the correct type for the page (i.e., either a LeafControlRow or a BranchControlRow).- Throws:
StandardException
- Standard exception policy.
-
get
public static ControlRow get(ContainerHandle container, long pageNumber) throws StandardException
- Throws:
StandardException
-
getNoWait
public static ControlRow getNoWait(OpenBTree open_btree, long pageNumber) throws StandardException
Get the control row for the given page if the latch on the page can be obtained without waiting, else return null.- Throws:
StandardException
- Standard exception policy.
-
getControlRowForPage
protected static ControlRow getControlRowForPage(ContainerHandle container, Page page) throws StandardException
- Throws:
StandardException
-
release
public void release()
Release this control row's resources.
-
searchForEntry
protected void searchForEntry(SearchParameters params) throws StandardException
Search this index page.This method is very performance sensitive. It is the intention that no object allocations occur during the execution of this method.
This method performs a binary search on the page and finds the entry i on the page such that entry[i] <= key < entry[i+1]. The result of the search is filled into the passed in params structure.
- Parameters:
params
- the parameters of the search- Throws:
StandardException
- could be thrown by underlying raw store operations.- See Also:
SearchParameters
-
searchForEntryBackward
protected void searchForEntryBackward(SearchParameters params) throws StandardException
- Throws:
StandardException
-
compareIndexRowFromPageToKey
public static int compareIndexRowFromPageToKey(ControlRow indexpage, int slot, DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc) throws StandardException
Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1 depending on whether the first row (indexrow) is less than, equal to, or greater than the second (key). The key may have fewer columns present than nCompareCols. In such a case, if all the columns of the partial key match all of the corresponding columns in the index row, then the value passed in in partialKeyOrder is returned. The caller should pass in partialKeyOrder=1 if the index rows which match a partial key should be considered to be greater than the partial key, and -1 if they should be considered to be less. This routine only reads objects off the page if it needs them, so if a multi-part key differs in the first column the subsequent columns are not read.- Parameters:
indexpage
- Controlrow of page to get target row from.slot
- Slot to get control row from.indexrow
- template of the target row (the row in the index).key
- the (possibly partial) search key.nCompareCols
- the number of columns to compare.partialKeyOrder
- what to return on a partial key match.ascOrDesc
- column sort order information- Throws:
StandardException
- if lower levels have a problem.
-
compareIndexRowToKey
public static int compareIndexRowToKey(DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc) throws StandardException
- Throws:
StandardException
-
checkGeneric
protected void checkGeneric(OpenBTree btree, ControlRow parent, boolean check_other_pages) throws StandardException
Perform consistency checks which are common to all pages that derive from ControlRow (both leaf and branch pages). The checks are: Note that these last two are really only true if there are never duplicate keys.- Throws:
StandardException
- Standard exception policy.
-
checkRowOrder
protected boolean checkRowOrder(OpenBTree btree, ControlRow parent) throws StandardException
Check that all rows on the page are in order. This means that each key is > than the previous key.- Throws:
StandardException
- Standard exception policy.
-
compareRowsOnSiblings
protected boolean compareRowsOnSiblings(OpenBTree btree, ControlRow left_sib, ControlRow right_sib) throws StandardException
- Throws:
StandardException
-
checkSiblings
protected void checkSiblings(OpenBTree btree) throws StandardException
Perform checks on the siblings of this page: make sure that they're at the same level as this page, that they're mutually linked together, and that the first/last keys on sibling pages are in order.- Throws:
StandardException
- Standard exception policy.
-
linkRight
void linkRight(OpenBTree btree, ControlRow target) throws StandardException
Link this page to the right of the target page.Upon entry, this page and the target must be latched. Upon exit, this page and the target remain latched.
This method carefully acquires pages from left to right in order to avoid deadlocks.
- Throws:
StandardException
- Standard exception policy.
-
unlink
boolean unlink(OpenBTree btree) throws StandardException
Unlink this page from its siblings. This method will give up and return false rather than run the risk of a deadlock.On entry this page must be latched. The siblings are latched and unlatched during the operation. Upon exit, this page will remain latched, but unlinked from its siblings and deallocated from the container.
The seemingly odd situation that this page will be returned latched but deallocated is intentional. The container will not be able to reuse this page until the latch is released, and the caller may still need to read information out of it.
- Throws:
StandardException
- Standard exception policy.
-
getPage
public Page getPage()
-
getRow
protected final DataValueDescriptor[] getRow()
Get the row.Return the object array that represents the control row for use in raw store fetch, insert, and/or update.
- Returns:
- The row.
-
checkConsistency
protected abstract int checkConsistency(OpenBTree btree, ControlRow parent, boolean check_other_pages) throws StandardException
Check consistency of the page and its children, returning the number of pages seen, and throwing errors if inconsistencies are found.- 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.
-
getLeftChild
protected abstract ControlRow getLeftChild(OpenBTree btree) throws StandardException
Return the left child pointer for the page.Leaf pages don't have children, so they override this and return null.
- Parameters:
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 abstract ControlRow getRightChild(OpenBTree btree) throws StandardException
Return the right child pointer for the page.Leaf pages don't have children, so they override this and return null.
- Parameters:
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.
-
controlRowInit
protected abstract void controlRowInit()
Perform page specific initialization.
-
isLeftmostLeaf
public abstract boolean isLeftmostLeaf() throws StandardException
Is the current page the leftmost leaf of tree?- Returns:
- true if the current page is the leftmost leaf of the tree, else return false.
- Throws:
StandardException
- Standard exception policy.
-
isRightmostLeaf
public abstract boolean isRightmostLeaf() throws StandardException
Is the current page the rightmost leaf of tree?- Returns:
- true if the current page is the rightmost leaf of the tree, else return false.
- Throws:
StandardException
- Standard exception policy.
-
search
public abstract ControlRow search(SearchParameters search_params) 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 resultExact field will be true. Otherwise, resultExact field will be false, and the row slot returned will be the one immediately preceding the position at which the key belongs.- Throws:
StandardException
- Standard exception policy.
-
getNumberOfControlRowColumns
protected abstract 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.
- Returns:
- The total number of columns in the control row.
-
searchLeft
protected abstract 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()).
- Parameters:
btree
- The open btree to associate latches/locks with.- Returns:
- The leftmost leaf page.
- Throws:
StandardException
- Standard exception policy.
-
searchRight
protected abstract 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()).
- Parameters:
btree
- The open btree to associate latches/locks with.- Returns:
- The rightmost leaf page.
- Throws:
StandardException
- Standard exception policy.
-
shrinkFor
protected abstract boolean shrinkFor(OpenBTree btree, DataValueDescriptor[] 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.As currently implemented shrinkFor must be executed while holding an exclusive container lock on the entire table. It is expected that this call is made within an internal transaction which has been called by a post commit thread. Latches are released by the code. The raw store guarantees that deallocated pages are not seen by other xacts until the transaction has been committed.
Note that a non-table level lock implementation must hold latches on pages affected until end transaction.
On entry, the current page is latched. On exit, all pages will have been unlatched.
- Throws:
StandardException
- Standard exception policy.
-
splitFor
protected abstract long splitFor(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow parentpage, DataValueDescriptor[] row, 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.
- Parameters:
open_btree
- The open btree to associate latches with.template
- A scratch area to use while searching for split pass.parentpage
- The parent page of the current page in the split pass. starts at null for root.row
- 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.
-
printTree
public abstract void printTree(OpenBTree btree) throws StandardException
Recursively print the tree starting at current node in tree.- Throws:
StandardException
- Standard exception policy.
-
auxObjectInvalidated
public void auxObjectInvalidated()
Called when the page is being evicted from cache or when a rollback happened on the page and may possibly have changed the control row's value- Specified by:
auxObjectInvalidated
in interfaceAuxObject
- See Also:
AuxObject.auxObjectInvalidated()
-
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).
- Returns:
- Newly allocated template.
- Throws:
StandardException
- Standard exception policy.
-
debugPage
public java.lang.String debugPage(OpenBTree open_btree) throws StandardException
Dump complete information about control row and rows on the page.- Returns:
- string with all info.
- Throws:
StandardException
- Standard exception policy.
-
toString
public java.lang.String toString()
The standard toString().This is a concise print out of the info in the control row, does not include anything the page.
- Overrides:
toString
in classjava.lang.Object
-
-