BTreeBuildLevel Class Reference

BTreeBuildLevel is subordinate to BTreeBuilder. More...

#include <BTreeBuildLevel.h>

Inheritance diagram for BTreeBuildLevel:

List of all members.

Public Member Functions
virtual	~BTreeBuildLevel ()
void	indexLastChild ()
Protected Member Functions
bool	isFinished () const
void	processInput (ByteInputStream &sortedInputStream)
void	unmarshalLastKey ()
BTreeNode *	allocateAndLinkNewNode ()
BTreeNode &	allocatePage ()
	BTreeBuildLevel (BTreeBuilder &builderInit, BTreeNodeAccessor &nodeAccessorInit)
virtual bool	isNodeFull (BTreeNode const &node, uint cbTuple)
virtual void	indexLastKey (bool finalize)=0
Protected Attributes
BTreeBuilder &	builder
	Owning BTreeBuilder.
BTreeNodeAccessor &	nodeAccessor
	BTreeNodeAccessor to use for accessing nodes in this level.
uint	iLevel
	0-based height of this level in tree.
RecordNum	iNode
	0-based sequence number of node being built on this level.
RecordNum	nEntriesTotal
	Total number of entries expected at this level.
BTreePageLock	pageLock
	Lock on current node.
PageId	pageId
	PageId of current node.
uint	nEntriesPerNode
	Number of entries to store on each node.
RecordNum	nEntriesProcessed
	Number of entries appended on this level so far (across all nodes).
uint	cbReserved
	Number of bytes of free space to reserve on each page (determined by fill factor).
Friends
class	BTreeBuilder

---

Detailed Description

BTreeBuildLevel is subordinate to BTreeBuilder.

It manages the build state for one level of a BTree being built.

Definition at line 40 of file BTreeBuildLevel.h.

---

Constructor & Destructor Documentation

BTreeBuildLevel::BTreeBuildLevel	(	BTreeBuilder &	builderInit,
		BTreeNodeAccessor &	nodeAccessorInit
	)			[explicit, protected]

Definition at line 33 of file BTreeBuildLevel.cpp.

References SegPageLock::accessSegment(), builder, cbReserved, iLevel, iNode, nEntriesPerNode, nEntriesProcessed, nEntriesTotal, pageLock, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

    : builder(builderInit), nodeAccessor(nodeAccessorInit)
{
    iLevel = 0;
    nEntriesTotal = 0;
    cbReserved = 0;
    iNode = 0;
    nEntriesProcessed = 0;
    nEntriesPerNode = 0;
    pageLock.accessSegment(builder.treeDescriptor.segmentAccessor);
}

BTreeBuildLevel::~BTreeBuildLevel

(

)

[virtual]

Definition at line 47 of file BTreeBuildLevel.cpp.

{
}

---

Member Function Documentation

bool BTreeBuildLevel::isFinished

(

)

const [protected]

Definition at line 51 of file BTreeBuildLevel.cpp.

References SegNodeLock< Node >::getNodeForRead(), nEntriesPerNode, nEntriesProcessed, nEntriesTotal, and pageLock.

{
    return (pageLock.getNodeForRead().nEntries == nEntriesPerNode)
        && (nEntriesProcessed == nEntriesTotal);
}

void BTreeBuildLevel::processInput

(

ByteInputStream &

sortedInputStream

)

[protected]

Definition at line 57 of file BTreeBuildLevel.cpp.

References allocateAndLinkNewNode(), BTreeNodeAccessor::allocateEntry(), builder, ByteInputStream::consumeReadPointer(), TupleAccessor::getCurrentByteCount(), SegNodeLock< Node >::getNodeForWrite(), ByteInputStream::getReadPointer(), indexLastKey(), isNodeFull(), BTreeNode::nEntries, nEntriesProcessed, nEntriesTotal, nodeAccessor, pageLock, TupleAccessor::setCurrentTupleBuf(), BTreeNodeAccessor::tupleAccessor, and BTreeAccessBase::validateTupleSize().

Referenced by BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), and BTreeBuilder::buildUnbalanced().

{
    BTreeNode *pNode = &(pageLock.getNodeForWrite());

    for (;;) {
        // Read one tuple.
        uint cbActual;
        PConstBuffer pCurrentTupleBuf =
            sortedInputStream.getReadPointer(1,&cbActual);
        if (!pCurrentTupleBuf) {
            break;
        }
        if (nEntriesTotal) {
            assert(nEntriesProcessed < nEntriesTotal);
        }
        nodeAccessor.tupleAccessor.setCurrentTupleBuf(pCurrentTupleBuf);
        uint cbTuple = nodeAccessor.tupleAccessor.getCurrentByteCount();
        assert(cbActual >= cbTuple);

        builder.validateTupleSize(nodeAccessor.tupleAccessor);

        // Make sure we have enough room.
        if (isNodeFull(*pNode,cbTuple)) {
            indexLastKey(false);
            pNode = allocateAndLinkNewNode();
            assert(!isNodeFull(*pNode,cbTuple));
            // indexLastKey used tupleAccessor, so have to rebind it
            nodeAccessor.tupleAccessor.setCurrentTupleBuf(pCurrentTupleBuf);
        }

        // Append the current tuple.
        PBuffer pEntry = nodeAccessor.allocateEntry(
            *pNode,
            pNode->nEntries,
            cbTuple);
        memcpy(
            pEntry,
            pCurrentTupleBuf,
            cbTuple);
        ++nEntriesProcessed;

        // Advance to the next input tuple.
        sortedInputStream.consumeReadPointer(cbTuple);
    }
}

void BTreeBuildLevel::unmarshalLastKey

(

)

[protected]

Definition at line 135 of file BTreeBuildLevel.cpp.

References BTreeNodeAccessor::accessTuple(), builder, SegNodeLock< Node >::getNodeForRead(), BTreeNode::nEntries, nodeAccessor, pageLock, BTreeAccessBase::pNonLeafNodeAccessor, and BTreeNodeAccessor::unmarshalKey().

Referenced by indexLastChild(), DynamicBuildLevel::indexLastKey(), VariableBuildLevel::indexLastKey(), and FixedBuildLevel::indexLastKey().

{
    BTreeNode const &node = pageLock.getNodeForRead();
    nodeAccessor.accessTuple(node,node.nEntries - 1);
    nodeAccessor.unmarshalKey(builder.pNonLeafNodeAccessor->tupleData);
}

BTreeNode * BTreeBuildLevel::allocateAndLinkNewNode

(

)

[protected]

Definition at line 142 of file BTreeBuildLevel.cpp.

References SegPageLock::accessSegment(), allocatePage(), builder, BTreeBuilder::calculateChildEntriesPerNode(), BTreeAccessBase::getCacheAccessor(), BTreeBuilder::getLevel(), SegNodeLock< Node >::getNodeForWrite(), SegPageLock::getPage(), iLevel, iNode, SegPageLock::lockExclusive(), nEntriesPerNode, nEntriesTotal, pageId, BTreeDescriptor::segmentAccessor, BTreeAccessBase::setRightSibling(), and BTreeAccessBase::treeDescriptor.

Referenced by indexLastChild(), and processInput().

{
    PageId prevPageId = pageId;

    BTreeNode &node = allocatePage();

    // Ugly:  we have to go back and fix up the rightSibling link on the
    // previous page.  There are better ways, but they require messing with
    // SegPageLock.
    BTreePageLock prevPageLock;
    prevPageLock.accessSegment(builder.treeDescriptor.segmentAccessor);
    prevPageLock.lockExclusive(prevPageId);
    BTreeNode &prevNode = prevPageLock.getNodeForWrite();
    builder.setRightSibling(
        prevNode,
        prevPageId,
        pageId);

    // Let the cache know we're not planning to revisit the page we just
    // finished.
    builder.getCacheAccessor()->nicePage(prevPageLock.getPage());

    ++iNode;
    if (nEntriesPerNode) {
        // Recalculate balancing.
        nEntriesPerNode = builder.calculateChildEntriesPerNode(
            builder.getLevel(iLevel + 1).nEntriesTotal,
            nEntriesTotal,
            iNode);
    }
    return &node;
}

BTreeNode & BTreeBuildLevel::allocatePage

(

)

[protected]

Definition at line 181 of file BTreeBuildLevel.cpp.

References SegNodeLock< Node >::allocatePage(), builder, BTreeNodeAccessor::clearNode(), SegNodeLock< Node >::getNodeForWrite(), BTreeAccessBase::getPageOwnerId(), BTreeAccessBase::getSegment(), BTreeNode::height, iLevel, nodeAccessor, pageId, and pageLock.

Referenced by allocateAndLinkNewNode(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), and BTreeBuilder::growTree().

{
    pageId = pageLock.allocatePage(builder.getPageOwnerId());
    BTreeNode &node = pageLock.getNodeForWrite();
    nodeAccessor.clearNode(
        node,builder.getSegment()->getUsablePageSize());
    node.height = iLevel;
    return node;
}

bool BTreeBuildLevel::isNodeFull	(	BTreeNode const &	node,
		uint	cbTuple
	)			[protected, virtual]

Reimplemented in FixedBuildLevel.

Definition at line 175 of file BTreeBuildLevel.cpp.

References BTreeNodeAccessor::calculateCapacity(), BTreeNodeAccessor::CAN_FIT, cbReserved, and nodeAccessor.

Referenced by indexLastChild(), and processInput().

{
    return nodeAccessor.calculateCapacity(node,cbReserved + cbTuple)
        != BTreeNodeAccessor::CAN_FIT;
}

virtual void BTreeBuildLevel::indexLastKey

(

bool

finalize

)

[protected, pure virtual]

Implemented in FixedBuildLevel, VariableBuildLevel, and DynamicBuildLevel.

Referenced by BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), indexLastChild(), and processInput().

void BTreeBuildLevel::indexLastChild

(

)

Definition at line 103 of file BTreeBuildLevel.cpp.

References allocateAndLinkNewNode(), BTreeNodeAccessor::allocateEntry(), builder, TupleAccessor::getByteCount(), BTreeBuilder::getLevel(), SegNodeLock< Node >::getNodeForWrite(), iLevel, indexLastKey(), isNodeFull(), TupleAccessor::marshal(), BTreeNode::nEntries, nEntriesProcessed, nEntriesTotal, nodeAccessor, pageId, pageLock, BTreeNodeAccessor::tupleAccessor, BTreeNodeAccessor::tupleData, and unmarshalLastKey().

Referenced by DynamicBuildLevel::indexLastKey(), and FixedBuildLevel::indexLastKey().

{
    assert(iLevel > 0);
    if (nEntriesTotal) {
        assert(nEntriesProcessed < nEntriesTotal);
    }

    uint cbTuple = nodeAccessor.tupleAccessor.getByteCount(
        nodeAccessor.tupleData);

    BTreeNode *pNode = &(pageLock.getNodeForWrite());
    if (isNodeFull(*pNode,cbTuple)) {
        indexLastKey(false);
        pNode = allocateAndLinkNewNode();

        // FIXME: should override fillfactor here, or provide a proper error
        // msg; same thing somewhere else
        assert(!isNodeFull(*pNode,cbTuple));

        // indexLastKey used tupleData, so have to rebind it
        builder.getLevel(iLevel - 1).unmarshalLastKey();
    }

    // Now append the child entry.
    nodeAccessor.tupleData.back().pData =
        reinterpret_cast<PConstBuffer>(&(builder.getLevel(iLevel-1).pageId));
    PBuffer pEntry = nodeAccessor.allocateEntry(
        *pNode,pNode->nEntries,cbTuple);
    nodeAccessor.tupleAccessor.marshal(nodeAccessor.tupleData,pEntry);
    ++nEntriesProcessed;
}

---

Friends And Related Function Documentation

friend class BTreeBuilder [friend]

Reimplemented in FixedBuildLevel, VariableBuildLevel, and DynamicBuildLevel.

Definition at line 42 of file BTreeBuildLevel.h.

---

Member Data Documentation

BTreeBuilder& BTreeBuildLevel::builder [protected]

Owning BTreeBuilder.

Definition at line 48 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), allocatePage(), BTreeBuildLevel(), VariableBuildLevel::getParentKeyStream(), indexLastChild(), DynamicBuildLevel::indexLastKey(), VariableBuildLevel::indexLastKey(), FixedBuildLevel::indexLastKey(), processInput(), unmarshalLastKey(), and VariableBuildLevel::VariableBuildLevel().

BTreeNodeAccessor& BTreeBuildLevel::nodeAccessor [protected]

BTreeNodeAccessor to use for accessing nodes in this level.

Definition at line 53 of file BTreeBuildLevel.h.

Referenced by allocatePage(), BTreeBuilder::buildBalanced(), indexLastChild(), isNodeFull(), processInput(), and unmarshalLastKey().

uint BTreeBuildLevel::iLevel [protected]

0-based height of this level in tree.

Definition at line 58 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), allocatePage(), BTreeBuildLevel(), BTreeBuilder::buildBalanced(), BTreeBuilder::growTree(), indexLastChild(), DynamicBuildLevel::indexLastKey(), and FixedBuildLevel::indexLastKey().

RecordNum BTreeBuildLevel::iNode [protected]

0-based sequence number of node being built on this level.

Definition at line 63 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), BTreeBuildLevel(), and BTreeBuilder::buildTwoPass().

RecordNum BTreeBuildLevel::nEntriesTotal [protected]

Total number of entries expected at this level.

If 0, total is unknown.

Definition at line 68 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), BTreeBuildLevel(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), indexLastChild(), isFinished(), and processInput().

BTreePageLock BTreeBuildLevel::pageLock [protected]

Lock on current node.

Definition at line 73 of file BTreeBuildLevel.h.

Referenced by allocatePage(), BTreeBuildLevel(), BTreeBuilder::buildBalanced(), indexLastChild(), FixedBuildLevel::indexLastKey(), isFinished(), processInput(), BTreeBuilder::swapRoot(), and unmarshalLastKey().

PageId BTreeBuildLevel::pageId [protected]

PageId of current node.

Definition at line 78 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), allocatePage(), BTreeBuilder::buildBalanced(), indexLastChild(), VariableBuildLevel::indexLastKey(), and BTreeBuilder::swapRoot().

uint BTreeBuildLevel::nEntriesPerNode [protected]

Number of entries to store on each node.

This varies over the level to achieve the desired balancing. If 0, no balancing is being performed.

Definition at line 85 of file BTreeBuildLevel.h.

Referenced by allocateAndLinkNewNode(), BTreeBuildLevel(), BTreeBuilder::buildBalanced(), FixedBuildLevel::indexLastKey(), isFinished(), and FixedBuildLevel::isNodeFull().

RecordNum BTreeBuildLevel::nEntriesProcessed [protected]

Number of entries appended on this level so far (across all nodes).

For non-leaf levels, this should stay in sync with the iNode of the child level.

Definition at line 92 of file BTreeBuildLevel.h.

Referenced by BTreeBuildLevel(), indexLastChild(), isFinished(), and processInput().

uint BTreeBuildLevel::cbReserved [protected]

Number of bytes of free space to reserve on each page (determined by fill factor).

0 for fixed-width entries.

Definition at line 98 of file BTreeBuildLevel.h.

Referenced by BTreeBuildLevel(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeBuilder::growTree(), and isNodeFull().

---

The documentation for this class was generated from the following files:

• /home/pub/open/dev/fennel/btree/BTreeBuildLevel.h
• /home/pub/open/dev/fennel/btree/BTreeBuildLevel.cpp

---