DynamicBuildLevel Class Reference

#include <BTreeBuildLevel.h>

Inheritance diagram for DynamicBuildLevel:

List of all members.

Public Member Functions
void	indexLastChild ()
Protected Member Functions
bool	isFinished () const
void	processInput (ByteInputStream &sortedInputStream)
void	unmarshalLastKey ()
BTreeNode *	allocateAndLinkNewNode ()
BTreeNode &	allocatePage ()
virtual bool	isNodeFull (BTreeNode const &node, uint cbTuple)
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).
Private Member Functions
	DynamicBuildLevel (BTreeBuilder &builderInit, BTreeNodeAccessor &nodeAccessorInit)
virtual void	indexLastKey (bool finalize)
Friends
class	BTreeBuilder

---

Detailed Description

Definition at line 158 of file BTreeBuildLevel.h.

---

Constructor & Destructor Documentation

DynamicBuildLevel::DynamicBuildLevel	(	BTreeBuilder &	builderInit,
		BTreeNodeAccessor &	nodeAccessorInit
	)			[explicit, private]

Definition at line 265 of file BTreeBuildLevel.cpp.

    : BTreeBuildLevel(builderInit,nodeAccessorInit)
{
}

---

Member Function Documentation

void DynamicBuildLevel::indexLastKey

(

bool

finalize

)

[private, virtual]

Implements BTreeBuildLevel.

Definition at line 272 of file BTreeBuildLevel.cpp.

References BTreeBuildLevel::builder, BTreeBuilder::getLevel(), BTreeBuilder::getRootHeight(), BTreeBuilder::growTree(), BTreeBuildLevel::iLevel, BTreeBuildLevel::indexLastChild(), and BTreeBuildLevel::unmarshalLastKey().

{
    if (iLevel == builder.getRootHeight()) {
        if (finalize) {
            return;
        } else {
            builder.growTree();
        }
    }
    unmarshalLastKey();
    builder.getLevel(iLevel + 1).indexLastChild();
}

bool BTreeBuildLevel::isFinished

(

)

const [protected, inherited]

Definition at line 51 of file BTreeBuildLevel.cpp.

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

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

void BTreeBuildLevel::processInput

(

ByteInputStream &

sortedInputStream

)

[protected, inherited]

Definition at line 57 of file BTreeBuildLevel.cpp.

References BTreeBuildLevel::allocateAndLinkNewNode(), BTreeNodeAccessor::allocateEntry(), BTreeBuildLevel::builder, ByteInputStream::consumeReadPointer(), TupleAccessor::getCurrentByteCount(), SegNodeLock< Node >::getNodeForWrite(), ByteInputStream::getReadPointer(), BTreeBuildLevel::indexLastKey(), BTreeBuildLevel::isNodeFull(), BTreeNode::nEntries, BTreeBuildLevel::nEntriesProcessed, BTreeBuildLevel::nEntriesTotal, BTreeBuildLevel::nodeAccessor, BTreeBuildLevel::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, inherited]

Definition at line 135 of file BTreeBuildLevel.cpp.

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

Referenced by BTreeBuildLevel::indexLastChild(), 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, inherited]

Definition at line 142 of file BTreeBuildLevel.cpp.

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

Referenced by BTreeBuildLevel::indexLastChild(), and BTreeBuildLevel::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, inherited]

Definition at line 181 of file BTreeBuildLevel.cpp.

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

Referenced by BTreeBuildLevel::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, inherited]

Reimplemented in FixedBuildLevel.

Definition at line 175 of file BTreeBuildLevel.cpp.

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

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

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

void BTreeBuildLevel::indexLastChild

(

)

[inherited]

Definition at line 103 of file BTreeBuildLevel.cpp.

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

Referenced by 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 from BTreeBuildLevel.

Definition at line 161 of file BTreeBuildLevel.h.

---

Member Data Documentation

BTreeBuilder& BTreeBuildLevel::builder [protected, inherited]

Owning BTreeBuilder.

Definition at line 48 of file BTreeBuildLevel.h.

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

BTreeNodeAccessor& BTreeBuildLevel::nodeAccessor [protected, inherited]

BTreeNodeAccessor to use for accessing nodes in this level.

Definition at line 53 of file BTreeBuildLevel.h.

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

uint BTreeBuildLevel::iLevel [protected, inherited]

0-based height of this level in tree.

Definition at line 58 of file BTreeBuildLevel.h.

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

RecordNum BTreeBuildLevel::iNode [protected, inherited]

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

Definition at line 63 of file BTreeBuildLevel.h.

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

RecordNum BTreeBuildLevel::nEntriesTotal [protected, inherited]

Total number of entries expected at this level.

If 0, total is unknown.

Definition at line 68 of file BTreeBuildLevel.h.

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

BTreePageLock BTreeBuildLevel::pageLock [protected, inherited]

Lock on current node.

Definition at line 73 of file BTreeBuildLevel.h.

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

PageId BTreeBuildLevel::pageId [protected, inherited]

PageId of current node.

Definition at line 78 of file BTreeBuildLevel.h.

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

uint BTreeBuildLevel::nEntriesPerNode [protected, inherited]

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 BTreeBuildLevel::allocateAndLinkNewNode(), BTreeBuildLevel::BTreeBuildLevel(), BTreeBuilder::buildBalanced(), FixedBuildLevel::indexLastKey(), BTreeBuildLevel::isFinished(), and FixedBuildLevel::isNodeFull().

RecordNum BTreeBuildLevel::nEntriesProcessed [protected, inherited]

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::BTreeBuildLevel(), BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::isFinished(), and BTreeBuildLevel::processInput().

uint BTreeBuildLevel::cbReserved [protected, inherited]

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::BTreeBuildLevel(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeBuilder::growTree(), and BTreeBuildLevel::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

---