FixedBuildLevel Class Reference

#include <BTreeBuildLevel.h>

Inheritance diagram for FixedBuildLevel:

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 ()
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
	FixedBuildLevel (BTreeBuilder &builderInit, BTreeNodeAccessor &nodeAccessorInit)
virtual void	indexLastKey (bool finalize)
virtual bool	isNodeFull (BTreeNode const &node, uint cbTuple)
Friends
class	BTreeBuilder

---

Detailed Description

Definition at line 124 of file BTreeBuildLevel.h.

---

Constructor & Destructor Documentation

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

Definition at line 191 of file BTreeBuildLevel.cpp.

    : BTreeBuildLevel(builderInit,nodeAccessorInit)
{
}

---

Member Function Documentation

void FixedBuildLevel::indexLastKey

(

bool

finalize

)

[private, virtual]

Implements BTreeBuildLevel.

Definition at line 198 of file BTreeBuildLevel.cpp.

References BTreeBuildLevel::builder, BTreeBuilder::getLevel(), SegNodeLock< Node >::getNodeForRead(), BTreeBuilder::getRootHeight(), BTreeBuildLevel::iLevel, BTreeBuildLevel::indexLastChild(), BTreeBuildLevel::nEntriesPerNode, BTreeBuildLevel::pageLock, and BTreeBuildLevel::unmarshalLastKey().

{
    assert(pageLock.getNodeForRead().nEntries == nEntriesPerNode);
    if (iLevel == builder.getRootHeight()) {
        assert(finalize);
        return;
    }
    unmarshalLastKey();
    builder.getLevel(iLevel + 1).indexLastChild();
}

bool FixedBuildLevel::isNodeFull	(	BTreeNode const &	node,
		uint	cbTuple
	)			[private, virtual]

Reimplemented from BTreeBuildLevel.

Definition at line 209 of file BTreeBuildLevel.cpp.

References BTreeNode::nEntries, and BTreeBuildLevel::nEntriesPerNode.

{
    return (node.nEntries >= nEntriesPerNode);
}

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(), DynamicBuildLevel::indexLastKey(), VariableBuildLevel::indexLastKey(), and 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;
}

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 DynamicBuildLevel::indexLastKey(), and 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 127 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(), DynamicBuildLevel::indexLastKey(), VariableBuildLevel::indexLastKey(), 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(), DynamicBuildLevel::indexLastKey(), and 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(), 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(), indexLastKey(), BTreeBuildLevel::isFinished(), and 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

---