TypedFormat
, AuxObject
BranchControlRow
, LeafControlRow
public abstract class ControlRow extends java.lang.Object implements AuxObject, TypedFormat
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
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.
|
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.
|
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
value
|
protected 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.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
getTypeFormatId
private StorableFormatId version
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.
private SQLLongint leftSiblingPageNumber
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.
private SQLLongint rightSiblingPageNumber
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.
private SQLLongint parentPageNumber
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.
private SQLLongint level
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.
private SQLLongint isRoot
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.
private BTree btree
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.
protected Page page
protected DataValueDescriptor[] row
protected DataValueDescriptor[] scratch_row
protected FetchDescriptor fetchDesc
protected transient boolean use_last_search_result_hint
protected transient int last_search_result
protected static final int CR_COLID_FIRST
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.
protected static final int CR_VERSION_COLID
protected static final int CR_LEFTSIB_COLID
protected static final int CR_RIGHTSIB_COLID
protected static final int CR_PARENT_COLID
protected static final int CR_LEVEL_COLID
protected static final int CR_ISROOT_COLID
protected static final int CR_CONGLOM_COLID
protected static final int CR_COLID_LAST
protected static final int CR_NCOLUMNS
protected static final FormatableBitSet CR_VERSION_BITSET
protected static final FormatableBitSet CR_LEFTSIB_BITSET
protected static final FormatableBitSet CR_RIGHTSIB_BITSET
protected static final FormatableBitSet CR_PARENT_BITSET
protected static final FormatableBitSet CR_LEVEL_BITSET
protected static final FormatableBitSet CR_ISROOT_BITSET
protected static final FormatableBitSet CR_CONGLOM_BITSET
public static final int SPLIT_FLAG_LAST_ON_PAGE
public static final int SPLIT_FLAG_LAST_IN_TABLE
public static final int SPLIT_FLAG_FIRST_ON_PAGE
public static final int SPLIT_FLAG_FIRST_IN_TABLE
protected static final int CR_SLOT
protected ControlRow()
GetControlRowForPage() will call this constructor when it uses the monitor to create a control row dynamically given a given format id.
protected ControlRow(OpenBTree btree, Page page, int level, ControlRow parent, boolean isRoot) throws StandardException
Changes to this constructor will probably require changes to the corresponding accessor(s).
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?StandardException
- Standard exception policy.protected ControlRow(ContainerHandle container, Page page) throws StandardException
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).
container
- Open containerpage
- The page described by this control row.StandardException
- Standard exception policy.protected int getVersion() throws StandardException
Returns the version of the control row, faulting it in from the page if necessary.
StandardException
- Standard exception policy.protected void setVersion(int version) throws StandardException
Sets the version of the control row. Updates both the in-memory control row and the disk copy.
StandardException
- Standard exception policy.public ControlRow getLeftSibling(OpenBTree btree) throws StandardException, WaitError
WaitError
- if the latch request would have had to wait.StandardException
- Standard exception policy.protected void setLeftSibling(ControlRow leftsib) throws StandardException
StandardException
protected ControlRow getRightSibling(OpenBTree open_btree) throws StandardException
StandardException
- Standard exception policy.protected void setRightSibling(ControlRow rightsib) throws StandardException
StandardException
public long getleftSiblingPageNumber() throws StandardException
StandardException
- Standard exception policy.protected long getrightSiblingPageNumber() throws StandardException
StandardException
- Standard exception policy.protected long getParentPageNumber() throws StandardException
StandardException
- Standard exception policy.void setParent(long parent) throws StandardException
StandardException
protected int getLevel() throws StandardException
StandardException
protected void setLevel(int newlevel) throws StandardException
StandardException
protected boolean getIsRoot() throws StandardException
StandardException
protected void setIsRoot(boolean isRoot) throws StandardException
StandardException
public BTree getConglom(int format_id) throws StandardException
Returns the format id information for a row on the page. faulting it in from the page if necessary.
StandardException
- Standard exception policy.public static ControlRow get(OpenBTree open_btree, long pageNumber) throws StandardException
StandardException
- Standard exception policy.public static ControlRow get(ContainerHandle container, long pageNumber) throws StandardException
StandardException
public static ControlRow getNoWait(OpenBTree open_btree, long pageNumber) throws StandardException
StandardException
- Standard exception policy.protected static ControlRow getControlRowForPage(ContainerHandle container, Page page) throws StandardException
StandardException
public void release()
protected void searchForEntry(SearchParameters params) throws StandardException
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.
params
- the parameters of the searchStandardException
- could be thrown by underlying raw store
operations.SearchParameters
protected void searchForEntryBackward(SearchParameters params) throws StandardException
StandardException
public static int compareIndexRowFromPageToKey(ControlRow indexpage, int slot, DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc) throws StandardException
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 informationStandardException
- if lower levels have a problem.public static int compareIndexRowToKey(DataValueDescriptor[] indexrow, DataValueDescriptor[] key, int nCompareCols, int partialKeyOrder, boolean[] ascOrDesc) throws StandardException
StandardException
protected void checkGeneric(OpenBTree btree, ControlRow parent, boolean check_other_pages) throws StandardException
StandardException
- Standard exception policy.protected boolean checkRowOrder(OpenBTree btree, ControlRow parent) throws StandardException
StandardException
- Standard exception policy.protected boolean compareRowsOnSiblings(OpenBTree btree, ControlRow left_sib, ControlRow right_sib) throws StandardException
StandardException
protected void checkSiblings(OpenBTree btree) throws StandardException
StandardException
- Standard exception policy.void linkRight(OpenBTree btree, ControlRow target) throws StandardException
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.
StandardException
- Standard exception policy.boolean unlink(OpenBTree btree) throws StandardException
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.
StandardException
- Standard exception policy.public Page getPage()
protected final DataValueDescriptor[] getRow()
Return the object array that represents the control row for use in raw store fetch, insert, and/or update.
protected abstract int checkConsistency(OpenBTree btree, ControlRow parent, boolean check_other_pages) throws StandardException
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).StandardException
- Standard exception policy.protected abstract ControlRow getLeftChild(OpenBTree btree) throws StandardException
Leaf pages don't have children, so they override this and return null.
btree
- The open btree to associate latches/locks with.StandardException
- Standard exception policy.protected abstract ControlRow getRightChild(OpenBTree btree) throws StandardException
Leaf pages don't have children, so they override this and return null.
btree
- The open btree to associate latches/locks with.StandardException
- Standard exception policy.protected abstract void controlRowInit()
public abstract boolean isLeftmostLeaf() throws StandardException
StandardException
- Standard exception policy.public abstract boolean isRightmostLeaf() throws StandardException
StandardException
- Standard exception policy.public abstract ControlRow search(SearchParameters search_params) throws StandardException
StandardException
- Standard exception policy.protected abstract int getNumberOfControlRowColumns()
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.
protected abstract ControlRow searchLeft(OpenBTree btree) throws StandardException
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()).
btree
- The open btree to associate latches/locks with.StandardException
- Standard exception policy.protected abstract ControlRow searchRight(OpenBTree btree) throws StandardException
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()).
btree
- The open btree to associate latches/locks with.StandardException
- Standard exception policy.protected abstract boolean shrinkFor(OpenBTree btree, DataValueDescriptor[] key) throws StandardException
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.
StandardException
- Standard exception policy.protected abstract long splitFor(OpenBTree open_btree, DataValueDescriptor[] template, BranchControlRow parentpage, DataValueDescriptor[] row, int flag) throws StandardException
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.
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.StandardException
- Standard exception policy.public abstract void printTree(OpenBTree btree) throws StandardException
StandardException
- Standard exception policy.public void auxObjectInvalidated()
auxObjectInvalidated
in interface AuxObject
AuxObject.auxObjectInvalidated()
public DataValueDescriptor[] getRowTemplate(OpenBTree open_btree) throws StandardException
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).
StandardException
- Standard exception policy.public java.lang.String debugPage(OpenBTree open_btree) throws StandardException
StandardException
- Standard exception policy.public java.lang.String toString()
This is a concise print out of the info in the control row, does not include anything the page.
toString
in class java.lang.Object
Apache Derby V10.14 Internals - Copyright © 2004,2018 The Apache Software Foundation. All Rights Reserved.