ControlRow

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> org >> apache >> derby >> impl >> store >> access >> [ btree overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

Sourc code of org.apache.derby.impl.store.access.btree.ControlRow

SOURCE |

Download org.apache.derby.impl.store.access.btree.ControlRow

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

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

java.lang.Object
  org.apache.derby.impl.store.access.btree.ControlRow

All Implemented Interfaces:: org.apache.derby.iapi.store.raw.AuxObject, org.apache.derby.iapi.services.io.TypedFormat

Direct Known Subclasses:: BranchControlRow, LeafControlRow

public abstract class ControlRow
extends java.lang.Object
implements org.apache.derby.iapi.store.raw.AuxObject, org.apache.derby.iapi.services.io.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

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 org.apache.derby.iapi.services.io.FormatableBitSet CR_CONGLOM_BITSET


protected static int CR_CONGLOM_COLID


protected static org.apache.derby.iapi.services.io.FormatableBitSet CR_ISROOT_BITSET


protected static int CR_ISROOT_COLID


protected static org.apache.derby.iapi.services.io.FormatableBitSet CR_LEFTSIB_BITSET


protected static int CR_LEFTSIB_COLID


protected static org.apache.derby.iapi.services.io.FormatableBitSet CR_LEVEL_BITSET


protected static int CR_LEVEL_COLID


protected static int CR_NCOLUMNS


protected static org.apache.derby.iapi.services.io.FormatableBitSet CR_PARENT_BITSET


protected static int CR_PARENT_COLID


protected static org.apache.derby.iapi.services.io.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 org.apache.derby.iapi.services.io.FormatableBitSet CR_VERSION_BITSET
          bit sets used to fetch single columns at a time.

protected static int CR_VERSION_COLID


protected org.apache.derby.iapi.store.raw.FetchDescriptor fetchDesc
          FetchDescriptor used to replace fetchFieldFromSlot() calls.

private org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.SQLLongint leftSiblingPageNumber
          Pointer to page which is "left" at the current level.

private org.apache.derby.iapi.types.SQLLongint level
          The level of the btree.

protected org.apache.derby.iapi.store.raw.Page page
          The page that this control row describes.

private org.apache.derby.iapi.types.SQLLongint parentPageNumber
          The parent page of the current page.

private org.apache.derby.iapi.types.SQLLongint rightSiblingPageNumber
          Pointer to page which is "right" at the current level.

protected org.apache.derby.iapi.types.DataValueDescriptor[] row
          The page that this control row describes.

protected org.apache.derby.iapi.types.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 org.apache.derby.impl.store.access.StorableFormatId version
          Version indentifier of the control row within the page.

Constructor Summary

protected ControlRow()
          No arg constructor.

protected ControlRow(org.apache.derby.iapi.store.raw.ContainerHandle container, org.apache.derby.iapi.store.raw.Page page)
          Constructor for making a control row for an existing page.

protected ControlRow(OpenBTree btree, org.apache.derby.iapi.store.raw.Page page, int level, ControlRow parent, boolean isRoot)
          Constructor for making a new control row as part of allocating a new page.

Method Summary

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, org.apache.derby.iapi.types.DataValueDescriptor[] indexrow, org.apache.derby.iapi.types.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(org.apache.derby.iapi.types.DataValueDescriptor[] indexrow, org.apache.derby.iapi.types.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(org.apache.derby.iapi.store.raw.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(org.apache.derby.iapi.store.raw.ContainerHandle container, org.apache.derby.iapi.store.raw.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.

org.apache.derby.iapi.store.raw.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 org.apache.derby.iapi.types.DataValueDescriptor[] getRow()
          Get the row.

org.apache.derby.iapi.types.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.

private void setConglom(BTree btree)
          Set the conglomerate field in the btree.

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, org.apache.derby.iapi.types.DataValueDescriptor[] key)
          Perform a recursive shrink operation for the key.

protected abstract long splitFor(OpenBTree open_btree, org.apache.derby.iapi.types.DataValueDescriptor[] template, BranchControlRow parentpage, org.apache.derby.iapi.types.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 org.apache.derby.impl.store.access.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 org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.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 org.apache.derby.iapi.store.raw.Page page

The page that this control row describes.

row

protected org.apache.derby.iapi.types.DataValueDescriptor[] row

The page that this control row describes.

scratch_row

protected org.apache.derby.iapi.types.DataValueDescriptor[] scratch_row

row used to replace fetchFieldFromSlot() calls.

fetchDesc

protected org.apache.derby.iapi.store.raw.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 org.apache.derby.iapi.services.io.FormatableBitSet CR_VERSION_BITSET

bit sets used to fetch single columns at a time.

CR_LEFTSIB_BITSET

protected static final org.apache.derby.iapi.services.io.FormatableBitSet CR_LEFTSIB_BITSET

CR_RIGHTSIB_BITSET

protected static final org.apache.derby.iapi.services.io.FormatableBitSet CR_RIGHTSIB_BITSET

CR_PARENT_BITSET

protected static final org.apache.derby.iapi.services.io.FormatableBitSet CR_PARENT_BITSET

CR_LEVEL_BITSET

protected static final org.apache.derby.iapi.services.io.FormatableBitSet CR_LEVEL_BITSET

CR_ISROOT_BITSET

protected static final org.apache.derby.iapi.services.io.FormatableBitSet CR_ISROOT_BITSET

CR_CONGLOM_BITSET

protected static final org.apache.derby.iapi.services.io.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,
                     org.apache.derby.iapi.store.raw.Page page,
                     int level,
                     ControlRow parent,
                     boolean isRoot)
              throws org.apache.derby.iapi.error.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).

ControlRow

protected ControlRow(org.apache.derby.iapi.store.raw.ContainerHandle container,
                     org.apache.derby.iapi.store.raw.Page page)
              throws org.apache.derby.iapi.error.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).

Method Detail

getVersion

protected int getVersion()
                  throws org.apache.derby.iapi.error.StandardException

Get version of the control row.

Returns the version of the control row, faulting it in from the page if necessary.

setVersion

protected void setVersion(int version)
                   throws org.apache.derby.iapi.error.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.

getLeftSibling

public ControlRow getLeftSibling(OpenBTree btree)
                          throws org.apache.derby.iapi.error.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.

setLeftSibling

protected void setLeftSibling(ControlRow leftsib)
                       throws org.apache.derby.iapi.error.StandardException

getRightSibling

protected ControlRow getRightSibling(OpenBTree open_btree)
                              throws org.apache.derby.iapi.error.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.

setRightSibling

protected void setRightSibling(ControlRow rightsib)
                        throws org.apache.derby.iapi.error.StandardException

getleftSiblingPageNumber

public long getleftSiblingPageNumber()
                              throws org.apache.derby.iapi.error.StandardException

Get the page number of the left sibling. Fault it's value in if it hasn't been yet.

getrightSiblingPageNumber

protected long getrightSiblingPageNumber()
                                  throws org.apache.derby.iapi.error.StandardException

Get the page number of the right sibling. Fault it's value in if it hasn't been yet.

getParentPageNumber

protected long getParentPageNumber()
                            throws org.apache.derby.iapi.error.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.

setParent

void setParent(long parent)
         throws org.apache.derby.iapi.error.StandardException

getLevel

protected int getLevel()
                throws org.apache.derby.iapi.error.StandardException

setLevel

protected void setLevel(int newlevel)
                 throws org.apache.derby.iapi.error.StandardException

getIsRoot

protected boolean getIsRoot()
                     throws org.apache.derby.iapi.error.StandardException

setIsRoot

protected void setIsRoot(boolean isRoot)
                  throws org.apache.derby.iapi.error.StandardException

getConglom

public BTree getConglom(int format_id)
                 throws org.apache.derby.iapi.error.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.

setConglom

private void setConglom(BTree btree)
                 throws org.apache.derby.iapi.error.StandardException

Set the conglomerate field in the btree.

Sets the btree field of the control row. Updates just the disk copy.

Get

public static ControlRow Get(OpenBTree open_btree,
                             long pageNumber)
                      throws org.apache.derby.iapi.error.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).

Get

public static ControlRow Get(org.apache.derby.iapi.store.raw.ContainerHandle container,
                             long pageNumber)
                      throws org.apache.derby.iapi.error.StandardException

GetNoWait

public static ControlRow GetNoWait(OpenBTree open_btree,
                                   long pageNumber)
                            throws org.apache.derby.iapi.error.StandardException

Get the control row for the given page if the latch on the page can be obtained without waiting, else return null.

GetControlRowForPage

protected static ControlRow GetControlRowForPage(org.apache.derby.iapi.store.raw.ContainerHandle container,
                                                 org.apache.derby.iapi.store.raw.Page page)
                                          throws org.apache.derby.iapi.error.StandardException

release

public void release()

Release this control row's resources.

searchForEntry

protected void searchForEntry(SearchParameters params)
                       throws org.apache.derby.iapi.error.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.

searchForEntryBackward

protected void searchForEntryBackward(SearchParameters params)
                               throws org.apache.derby.iapi.error.StandardException

CompareIndexRowFromPageToKey

public static int CompareIndexRowFromPageToKey(ControlRow indexpage,
                                               int slot,
                                               org.apache.derby.iapi.types.DataValueDescriptor[] indexrow,
                                               org.apache.derby.iapi.types.DataValueDescriptor[] key,
                                               int nCompareCols,
                                               int partialKeyOrder,
                                               boolean[] ascOrDesc)
                                        throws org.apache.derby.iapi.error.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.

CompareIndexRowToKey

public static int CompareIndexRowToKey(org.apache.derby.iapi.types.DataValueDescriptor[] indexrow,
                                       org.apache.derby.iapi.types.DataValueDescriptor[] key,
                                       int nCompareCols,
                                       int partialKeyOrder,
                                       boolean[] ascOrDesc)
                                throws org.apache.derby.iapi.error.StandardException

checkGeneric

protected void checkGeneric(OpenBTree btree,
                            ControlRow parent,
                            boolean check_other_pages)
                     throws org.apache.derby.iapi.error.StandardException

Perform consistency checks which are common to all pages that derive from ControlRow (both leaf and branch pages). The checks are:

This page thinks the parent argument is actually its parent.

The level of this page is 1 less than the level of the parent.

All the rows on the page are in order.

Both left and right siblings, if they exist, are at the same level of this page.

This page is the left sibling of its right sibling, and it's the right sibling of its left sibling.

The last row on the left sibling is < the first row on this page.

The first row on the right sibling is > than the the last row on this page.

Note that these last two are really only true if there are never duplicate keys.

checkRowOrder

protected boolean checkRowOrder(OpenBTree btree,
                                ControlRow parent)
                         throws org.apache.derby.iapi.error.StandardException

Check that all rows on the page are in order. This means that each key is > than the previous key.

compareRowsOnSiblings

protected boolean compareRowsOnSiblings(OpenBTree btree,
                                        ControlRow left_sib,
                                        ControlRow right_sib)
                                 throws org.apache.derby.iapi.error.StandardException

checkSiblings

protected void checkSiblings(OpenBTree btree)
                      throws org.apache.derby.iapi.error.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.

linkRight

void linkRight(OpenBTree btree,
               ControlRow target)
         throws org.apache.derby.iapi.error.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.

unlink

boolean unlink(OpenBTree btree)
         throws org.apache.derby.iapi.error.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.

getPage

public org.apache.derby.iapi.store.raw.Page getPage()

getRow

protected final org.apache.derby.iapi.types.DataValueDescriptor[] getRow()

Get the row.

Return the object array that represents the control row for use in raw store fetch, insert, and/or update.

checkConsistency

protected abstract int checkConsistency(OpenBTree btree,
                                        ControlRow parent,
                                        boolean check_other_pages)
                                 throws org.apache.derby.iapi.error.StandardException

Check consistency of the page and its children, returning the number of pages seen, and throwing errors if inconsistencies are found.

getLeftChild

protected abstract ControlRow getLeftChild(OpenBTree btree)
                                    throws org.apache.derby.iapi.error.StandardException

Return the left child pointer for the page.

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

getRightChild

protected abstract ControlRow getRightChild(OpenBTree btree)
                                     throws org.apache.derby.iapi.error.StandardException

Return the right child pointer for the page.

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

ControlRowInit

protected abstract void ControlRowInit()

Perform page specific initialization.

isLeftmostLeaf

public abstract boolean isLeftmostLeaf()
                                throws org.apache.derby.iapi.error.StandardException

Is the current page the leftmost leaf of tree?

isRightmostLeaf

public abstract boolean isRightmostLeaf()
                                 throws org.apache.derby.iapi.error.StandardException

Is the current page the rightmost leaf of tree?

search

public abstract ControlRow search(SearchParameters search_params)
                           throws org.apache.derby.iapi.error.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.

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.

searchLeft

protected abstract ControlRow searchLeft(OpenBTree btree)
                                  throws org.apache.derby.iapi.error.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()).

searchRight

protected abstract ControlRow searchRight(OpenBTree btree)
                                   throws org.apache.derby.iapi.error.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()).

shrinkFor

protected abstract boolean shrinkFor(OpenBTree btree,
                                     org.apache.derby.iapi.types.DataValueDescriptor[] key)
                              throws org.apache.derby.iapi.error.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.

splitFor

protected abstract long splitFor(OpenBTree open_btree,
                                 org.apache.derby.iapi.types.DataValueDescriptor[] template,
                                 BranchControlRow parentpage,
                                 org.apache.derby.iapi.types.DataValueDescriptor[] row,
                                 int flag)
                          throws org.apache.derby.iapi.error.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.

printTree

public abstract void printTree(OpenBTree btree)
                        throws org.apache.derby.iapi.error.StandardException

Recursively print the tree starting at current node in tree.

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 interface org.apache.derby.iapi.store.raw.AuxObject

getRowTemplate

public org.apache.derby.iapi.types.DataValueDescriptor[] getRowTemplate(OpenBTree open_btree)
                                                                 throws org.apache.derby.iapi.error.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).

debugPage

public java.lang.String debugPage(OpenBTree open_btree)
                           throws org.apache.derby.iapi.error.StandardException

Dump complete information about control row and rows on the page.

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.

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> org >> apache >> derby >> impl >> store >> access >> [ btree overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Field Summary
`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 org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_CONGLOM_BITSET`
`protected static int`	`CR_CONGLOM_COLID`
`protected static org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_ISROOT_BITSET`
`protected static int`	`CR_ISROOT_COLID`
`protected static org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_LEFTSIB_BITSET`
`protected static int`	`CR_LEFTSIB_COLID`
`protected static org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_LEVEL_BITSET`
`protected static int`	`CR_LEVEL_COLID`
`protected static int`	`CR_NCOLUMNS`
`protected static org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_PARENT_BITSET`
`protected static int`	`CR_PARENT_COLID`
`protected static org.apache.derby.iapi.services.io.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 org.apache.derby.iapi.services.io.FormatableBitSet`	`CR_VERSION_BITSET` bit sets used to fetch single columns at a time.
`protected static int`	`CR_VERSION_COLID`
`protected org.apache.derby.iapi.store.raw.FetchDescriptor`	`fetchDesc` FetchDescriptor used to replace fetchFieldFromSlot() calls.
`private org.apache.derby.iapi.types.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 org.apache.derby.iapi.types.SQLLongint`	`leftSiblingPageNumber` Pointer to page which is "left" at the current level.
`private org.apache.derby.iapi.types.SQLLongint`	`level` The level of the btree.
`protected org.apache.derby.iapi.store.raw.Page`	`page` The page that this control row describes.
`private org.apache.derby.iapi.types.SQLLongint`	`parentPageNumber` The parent page of the current page.
`private org.apache.derby.iapi.types.SQLLongint`	`rightSiblingPageNumber` Pointer to page which is "right" at the current level.
`protected org.apache.derby.iapi.types.DataValueDescriptor[]`	`row` The page that this control row describes.
`protected org.apache.derby.iapi.types.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 org.apache.derby.impl.store.access.StorableFormatId`	`version` Version indentifier of the control row within the page.

Constructor Summary
`protected`	`ControlRow()` No arg constructor.
`protected`	`ControlRow(org.apache.derby.iapi.store.raw.ContainerHandle container, org.apache.derby.iapi.store.raw.Page page)` Constructor for making a control row for an existing page.
`protected`	`ControlRow(OpenBTree btree, org.apache.derby.iapi.store.raw.Page page, int level, ControlRow parent, boolean isRoot)` Constructor for making a new control row as part of allocating a new page.

Method Summary
`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, org.apache.derby.iapi.types.DataValueDescriptor[] indexrow, org.apache.derby.iapi.types.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(org.apache.derby.iapi.types.DataValueDescriptor[] indexrow, org.apache.derby.iapi.types.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(org.apache.derby.iapi.store.raw.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(org.apache.derby.iapi.store.raw.ContainerHandle container, org.apache.derby.iapi.store.raw.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.
`org.apache.derby.iapi.store.raw.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 org.apache.derby.iapi.types.DataValueDescriptor[]`	`getRow()` Get the row.
`org.apache.derby.iapi.types.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.
`private void`	`setConglom(BTree btree)` Set the conglomerate field in the btree.
`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, org.apache.derby.iapi.types.DataValueDescriptor[] key)` Perform a recursive shrink operation for the key.
`protected abstract long`	`splitFor(OpenBTree open_btree, org.apache.derby.iapi.types.DataValueDescriptor[] template, BranchControlRow parentpage, org.apache.derby.iapi.types.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.

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

version

leftSiblingPageNumber

rightSiblingPageNumber

parentPageNumber

level

isRoot

btree

page

row

scratch_row

fetchDesc

use_last_search_result_hint

last_search_result

CR_COLID_FIRST

CR_VERSION_COLID

CR_LEFTSIB_COLID

CR_RIGHTSIB_COLID

CR_PARENT_COLID

CR_LEVEL_COLID

CR_ISROOT_COLID

CR_CONGLOM_COLID

CR_COLID_LAST

CR_NCOLUMNS

CR_VERSION_BITSET

CR_LEFTSIB_BITSET

CR_RIGHTSIB_BITSET

CR_PARENT_BITSET

CR_LEVEL_BITSET

CR_ISROOT_BITSET

CR_CONGLOM_BITSET

SPLIT_FLAG_LAST_ON_PAGE

SPLIT_FLAG_LAST_IN_TABLE

SPLIT_FLAG_FIRST_ON_PAGE

SPLIT_FLAG_FIRST_IN_TABLE

CR_SLOT

ControlRow

ControlRow

ControlRow

getVersion

setVersion

getLeftSibling

setLeftSibling

getRightSibling

setRightSibling

getleftSiblingPageNumber

getrightSiblingPageNumber

getParentPageNumber

setParent

getLevel

setLevel

getIsRoot

setIsRoot

getConglom

setConglom

Get

Get

GetNoWait

GetControlRowForPage

release

searchForEntry

searchForEntryBackward

CompareIndexRowFromPageToKey

CompareIndexRowToKey

checkGeneric

checkRowOrder

compareRowsOnSiblings

checkSiblings

linkRight

unlink

getPage

getRow

checkConsistency

getLeftChild

getRightChild

ControlRowInit

isLeftmostLeaf

isRightmostLeaf

search

getNumberOfControlRowColumns

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