Symbian^3 Product Developer Library >

TBtree Class Reference

class TBtree

Provides ordering of entries by key value in a B+-tree (balanced tree) structure.

Entries and keys are handled as untyped TAny* parameters. You specify an entry in the tree to manipulate through a position (TBtreePos) variable. You can also use iterator functions, which take a TBtreeMark, to move through entries in the tree. The tree's settings can be persisted using a TBtreeToken.

To use this class, you must provide a page pool, based on MPagePool, in which to store entries in the tree, and a key handler, based on MBtreeKey, to provide order and keys.

MBtreeKey MPagePool TBtreeMark TBtreePos TBtreeToken

Public Member Functions
TBtree(TBtreeMode)
TBtree(const TBtreeToken &, TBtreeMode)
IMPORT_C voidClearL()
IMPORT_C voidConnect(MPagePool *, const MBtreeKey *, const MBtreeLeafOrg *, const MBtreeIndexOrg *)
IMPORT_C voidDeleteAtL(TBtreePos &)
IMPORT_C TBoolDeleteL(const TAny *)
IMPORT_C voidExtractAtL(const TBtreePos &, TAny *, TInt)
IMPORT_C voidExtractAtL(const TBtreeMark &, TAny *, TInt)
IMPORT_C TBoolFindL(TBtreePos &, const TAny *, TFind)
IMPORT_C TBoolFirstL(TBtreePos &)
IMPORT_C TBoolInsertL(TBtreePos &, const TAny *, TInt, TAllowDuplicates)
TBool IsBroken()
TBool IsDirty()
TBool IsEmpty()
TBool IsIntact()
IMPORT_C TBoolLastL(TBtreePos &)
voidMarkBroken()
voidMarkCurrent()
voidMarkDirty()
IMPORT_C TBoolNextL(TBtreePos &)
IMPORT_C TBoolNextL(TBtreeMark &)
IMPORT_C TBoolPreviousL(TBtreePos &)
IMPORT_C TIntRepairL()
IMPORT_C TBoolResetL(TBtreeMark &)
IMPORT_C voidSet(const TBtreeToken &, TBtreeMode)
IMPORT_C TBtreeTokenToken()
Private Member Functions
TBool AscendAtFirstL(TBtreePath &)
TBool AscendAtLastL(TBtreePath &)
voidBeginUpdateL()
voidCheckIntactL()
TPageRef ChildNodeL(const TBtreePath &)
TPageRef ChildNodeL(TBtreePath &, TInt)
voidDeleteAtL(TBtreePath &)
voidDeleteIndexNodesL(TBtreePath &, TBool)
voidDeleteIndexSetL()
voidDescendFirstL(TBtreePath &)
voidDescendLastL(TBtreePath &)
voidEndUpdate()
TAny *GetNodeL(const TBtreePath &)
voidGotoRoot(TBtreePath &)
voidInsertAtL(TBtreePath &, const TDesC8 &)
voidInsertAtL(TBtreePath &, TBtreePivot &, TPageRef)
TBool InsertAtL(TBtreePath &, const TDesC8 &, TPageRef, TBtreePivot &, TPageRef &)
TBool IsRoot(const TBtreePath &)
TPageRef LastChildNodeL(TBtreePath &)
TInt LastEntryL(const TBtreePath &)
voidMarkIntact()
voidNewPivot(const TAny *, const TAny *, TBtreePivot &)
voidNewRootL()
voidNewTreeL()
const MBtreeNodeOrg *NodeOrg(TBool)
voidPutNode(TAny *, TBool)
voidReplacePivotL(TBtreePath &, TAny *, TBtreePivot &)
TBool SearchL(TBtreePath &, const TAny *, TBool)
Public Member Enumerations
enumTFind { EGreaterEqual, EEqualTo, ELessThan, EGreaterThan, ELessEqual }
Private Attributes
TPageRef iFirst
TBtreeHeight iHeight
const MBtreeIndexOrg *iIndexOrg
const MBtreeKey *iKey
const MBtreeLeafOrg *iLeafOrg
MPagePool *iPages
TPageRef iRoot
TInt iStatus

Constructor & Destructor Documentation

TBtree(TBtreeMode)

IMPORT_CTBtree(TBtreeModeaMode)

Constructor that sets the B-tree mode.

Parameters

TBtreeMode aModeB-tree operating mode

TBtree(const TBtreeToken &, TBtreeMode)

IMPORT_CTBtree(const TBtreeToken &aToken,
TBtreeModeaMode
)

Constructor that sets the B-tree mode and initialisation parameters.

Parameters

const TBtreeToken & aTokenParameters with which to initialise B-tree
TBtreeMode aModeB-tree operating mode

Member Functions Documentation

AscendAtFirstL(TBtreePath &)

TBool AscendAtFirstL(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

AscendAtLastL(TBtreePath &)

TBool AscendAtLastL(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

BeginUpdateL()

voidBeginUpdateL()[private]

CheckIntactL()

voidCheckIntactL()const [private]

ChildNodeL(const TBtreePath &)

TPageRef ChildNodeL(const TBtreePath &aPath)const [private]

Parameters

const TBtreePath & aPath

ChildNodeL(TBtreePath &, TInt)

TPageRef ChildNodeL(TBtreePath &aPath,
TIntaChild
)const [private]

Parameters

TBtreePath & aPath
TInt aChild

ClearL()

IMPORT_C voidClearL()

Resets the B-tree to have zero-height, and a null root, and deletes all index pages.

Connect(MPagePool *, const MBtreeKey *, const MBtreeLeafOrg *, const MBtreeIndexOrg *)

IMPORT_C voidConnect(MPagePool *aPool,
const MBtreeKey *aKey,
const MBtreeLeafOrg *aLeafOrg,
const MBtreeIndexOrg *anIndexOrg
)

Parameters

MPagePool * aPool
const MBtreeKey * aKey
const MBtreeLeafOrg * aLeafOrg
const MBtreeIndexOrg * anIndexOrg

DeleteAtL(TBtreePos &)

IMPORT_C voidDeleteAtL(TBtreePos &aPos)

Deletes the entry at the specified position

Parameters

TBtreePos & aPosPosition of the entry to delete

DeleteAtL(TBtreePath &)

voidDeleteAtL(TBtreePath &aPath)[private]

Parameters

TBtreePath & aPath

DeleteIndexNodesL(TBtreePath &, TBool)

voidDeleteIndexNodesL(TBtreePath &aPath,
TBoolaLeadingEdge
)[private]

Parameters

TBtreePath & aPath
TBool aLeadingEdge

DeleteIndexSetL()

voidDeleteIndexSetL()[private]

DeleteL(const TAny *)

IMPORT_C TBoolDeleteL(const TAny *aKey)

Deletes an entry.

Parameters

const TAny * aKeyPointer to the key of the entry to delete

DescendFirstL(TBtreePath &)

voidDescendFirstL(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

DescendLastL(TBtreePath &)

voidDescendLastL(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

EndUpdate()

voidEndUpdate()[private]

ExtractAtL(const TBtreePos &, TAny *, TInt)

IMPORT_C voidExtractAtL(const TBtreePos &aPos,
TAny *anEntry,
TIntaMaxLength
)const

Gets the entry at the specified position.

Parameters

const TBtreePos & aPosPosition of the entry to get
TAny * anEntryBuffer into which to copy the entry
TInt aMaxLengthLength of the anEntry buffer. If the entry is longer than this, only the first aMaxLength bytes will be copied.

ExtractAtL(const TBtreeMark &, TAny *, TInt)

IMPORT_C voidExtractAtL(const TBtreeMark &aMark,
TAny *anEntry,
TIntaMaxLength
)const

Gets an entry at specified iterator position.

Parameters

const TBtreeMark & aMarkPosition of the entry to get
TAny * anEntryBuffer into which to copy the entry
TInt aMaxLengthLength of anEntry buffer. If the entry is longer than this, only the first aMaxLength bytes are copied.

FindL(TBtreePos &, const TAny *, TFind)

IMPORT_C TBoolFindL(TBtreePos &aPos,
const TAny *aKey,
TFindaMode = EEqualTo
)const

Searches for an entry and returns its position.

Parameters

TBtreePos & aPosOn return, the position of the entry found
const TAny * aKeyPointer to the key of the entry for which to search
TFind aMode = EEqualToType of search to perform

FirstL(TBtreePos &)

IMPORT_C TBoolFirstL(TBtreePos &aPos)const

Goes to the first entry in the B-tree.

Parameters

TBtreePos & aPosOn return, the position of the first entry

GetNodeL(const TBtreePath &)

TAny *GetNodeL(const TBtreePath &aPath)const [private]

Parameters

const TBtreePath & aPath

GotoRoot(TBtreePath &)

voidGotoRoot(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

InsertAtL(TBtreePath &, const TDesC8 &)

voidInsertAtL(TBtreePath &aPath,
const TDesC8 &anEntry
)[private]

Parameters

TBtreePath & aPath
const TDesC8 & anEntry

InsertAtL(TBtreePath &, TBtreePivot &, TPageRef)

voidInsertAtL(TBtreePath &aPath,
TBtreePivot &aPivot,
TPageRefaChild
)[private]

Parameters

TBtreePath & aPath
TBtreePivot & aPivot
TPageRef aChild

InsertAtL(TBtreePath &, const TDesC8 &, TPageRef, TBtreePivot &, TPageRef &)

TBool InsertAtL(TBtreePath &aPath,
const TDesC8 &anEntry,
TPageRefaChild,
TBtreePivot &aPivot,
TPageRef &aPromote
)[private]

Parameters

TBtreePath & aPath
const TDesC8 & anEntry
TPageRef aChild
TBtreePivot & aPivot
TPageRef & aPromote

InsertL(TBtreePos &, const TAny *, TInt, TAllowDuplicates)

IMPORT_C TBoolInsertL(TBtreePos &aPos,
const TAny *anEntry,
TIntaLength,
TAllowDuplicatesaDup = ENoDuplicates
)

Inserts an entry into the tree.

Parameters

TBtreePos & aPosOn return, the position of the entry inserted
const TAny * anEntryPointer to the entry to insert
TInt aLengthLength of entry
TAllowDuplicates aDup = ENoDuplicatesFlag to indicate whether duplicate entries are allowed in the tree

IsBroken()

TBool IsBroken()const [inline]

Tests if the broken flag has been set on the B-tree.

Any updates to the B-tree that fail will leave this flag set on the TBtree object. This indicates that the persistent tree data is broken (corrupt) and the tree needs to be repaired. In this state, none of the functions which use a TBtreePos will work, only those taking a TBtreeMark.

IsDirty()

TBool IsDirty()const [inline]

Tests if the dirty flag has been set on the B-tree.

Any updates to the B-tree will set this flag on the TBtree object. Applications can use this to determine if they need to flush the page pool and re-save the B-tree token, after which they can call MarkCurrent() to indicate that the persistent storage is now up-to-date with the TBtree object.

IsEmpty()

TBool IsEmpty()const [inline]

Tests if the B-tree is empty.

IsIntact()

TBool IsIntact()const [inline]

Tests if the broken flag has not been set on the B-tree .

IsRoot(const TBtreePath &)

TBool IsRoot(const TBtreePath &aPath)const [private, inline]

Parameters

const TBtreePath & aPath

LastChildNodeL(TBtreePath &)

TPageRef LastChildNodeL(TBtreePath &aPath)const [private]

Parameters

TBtreePath & aPath

LastEntryL(const TBtreePath &)

TInt LastEntryL(const TBtreePath &aPath)const [private]

Parameters

const TBtreePath & aPath

LastL(TBtreePos &)

IMPORT_C TBoolLastL(TBtreePos &aPos)const

Goes to the last entry in the B-tree.

Parameters

TBtreePos & aPosOn return, the position of the last entry

MarkBroken()

voidMarkBroken()[inline]

Sets the broken flag.

MarkCurrent()

voidMarkCurrent()[inline]

Clears the dirty flag.

MarkDirty()

voidMarkDirty()[inline]

Sets the dirty flag.

MarkIntact()

voidMarkIntact()[private, inline]

NewPivot(const TAny *, const TAny *, TBtreePivot &)

voidNewPivot(const TAny *aLeftNode,
const TAny *aRightNode,
TBtreePivot &aPivot
)const [private]

Parameters

const TAny * aLeftNode
const TAny * aRightNode
TBtreePivot & aPivot

NewRootL()

voidNewRootL()[private]

NewTreeL()

voidNewTreeL()[private]

NextL(TBtreePos &)

IMPORT_C TBoolNextL(TBtreePos &aPos)const

Gets the position of the entry following the specified entry.

Parameters

TBtreePos & aPosOn return, the position of the next entry

NextL(TBtreeMark &)

IMPORT_C TBoolNextL(TBtreeMark &aMark)const

Advances an iterator to the next entry.

Parameters

TBtreeMark & aMarkIterator to use. On return, the iterator is advanced to the next entry.

NodeOrg(TBool)

const MBtreeNodeOrg *NodeOrg(TBoolaLeaf)const [private, inline]

Parameters

TBool aLeaf

PreviousL(TBtreePos &)

IMPORT_C TBoolPreviousL(TBtreePos &aPos)const

Gets the position of the entry preceding the specified entry.

Parameters

TBtreePos & aPosOn return, the position of the preceding entry

PutNode(TAny *, TBool)

voidPutNode(TAny *aNode,
TBoolaLeaf
)const [private]

Parameters

TAny * aNode
TBool aLeaf

RepairL()

IMPORT_C TIntRepairL()

Attempts to repair a broken B-tree.

If the operating mode (TBtreeMode) is set to EBtreeSecure, then the tree can be repaired without any loss of data. Otherwise, the tree must be deleted entirely using ClearL(), and reconstructed using other means.

Note that if multiple B-trees share a single store page pool, then reclaiming the pool will break all the other B-trees (but the Broken flag will not be set automatically). These trees can be repaired by calling MarkBroken() and then RepairL(), even if they were not of the EBtreeSecure type.

TBtreeMode

ReplacePivotL(TBtreePath &, TAny *, TBtreePivot &)

voidReplacePivotL(TBtreePath &aPath,
TAny *aNode,
TBtreePivot &aPivot
)[private]

Parameters

TBtreePath & aPath
TAny * aNode
TBtreePivot & aPivot

ResetL(TBtreeMark &)

IMPORT_C TBoolResetL(TBtreeMark &aMark)const

Resets an iterator to the root of the tree.

Parameters

TBtreeMark & aMarkIterator to set

SearchL(TBtreePath &, const TAny *, TBool)

TBool SearchL(TBtreePath &aPath,
const TAny *aKey,
TBoolaAfter = EFalse
)const [private]

Parameters

TBtreePath & aPath
const TAny * aKey
TBool aAfter = EFalse

Set(const TBtreeToken &, TBtreeMode)

IMPORT_C voidSet(const TBtreeToken &aToken,
TBtreeModeaMode
)

Initialises the B-tree.

Parameters

const TBtreeToken & aTokenParameters with which to initialise the B-tree
TBtreeMode aModeB-tree operating mode

Token()

IMPORT_C TBtreeTokenToken()const

Gets an object that encapsulates the TBtree settings.

That object can then be used to externalise the settings.

Member Enumerations Documentation

Enum TFind

Sets the condition for a successful match when calling TBtree::Find().

Enumerators

EGreaterEqual

Find the first entry greater than or equal to the search target.

EEqualTo

Find the first entry equal to the search target.

ELessThan

Find the last entry less than the search target.

EGreaterThan

Find the first entry greater than the search target.

ELessEqual

Find the last entry less than or equal to the search target.

Member Data Documentation

TPageRef iFirst

TPageRef iFirst[private]

TBtreeHeight iHeight

TBtreeHeight iHeight[private]

const MBtreeIndexOrg * iIndexOrg

const MBtreeIndexOrg *iIndexOrg[private]

const MBtreeKey * iKey

const MBtreeKey *iKey[private]

const MBtreeLeafOrg * iLeafOrg

const MBtreeLeafOrg *iLeafOrg[private]

MPagePool * iPages

MPagePool *iPages[private]

TPageRef iRoot

TPageRef iRoot[private]

TInt iStatus

TInt iStatus[private]

Copyright ©2010 Nokia Corporation and/or its subsidiary(-ies).
All rights reserved. Unless otherwise stated, these materials are provided under the terms of the Eclipse Public License v1.0.