Symbian^3 Application 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 void ClearL ()
IMPORT_C void Connect ( MPagePool *, const MBtreeKey *, const MBtreeLeafOrg *, const MBtreeIndexOrg *)
IMPORT_C void DeleteAtL ( TBtreePos &)
IMPORT_C TBool DeleteL (const TAny *)
IMPORT_C void ExtractAtL (const TBtreePos &, TAny *, TInt )
IMPORT_C void ExtractAtL (const TBtreeMark &, TAny *, TInt )
IMPORT_C TBool FindL ( TBtreePos &, const TAny *, TFind )
IMPORT_C TBool FirstL ( TBtreePos &)
IMPORT_C TBool InsertL ( TBtreePos &, const TAny *, TInt , TAllowDuplicates )
TBool IsBroken ()
TBool IsDirty ()
TBool IsEmpty ()
TBool IsIntact ()
IMPORT_C TBool LastL ( TBtreePos &)
void MarkBroken ()
void MarkCurrent ()
void MarkDirty ()
IMPORT_C TBool NextL ( TBtreePos &)
IMPORT_C TBool NextL ( TBtreeMark &)
IMPORT_C TBool PreviousL ( TBtreePos &)
IMPORT_C TInt RepairL ()
IMPORT_C TBool ResetL ( TBtreeMark &)
IMPORT_C void Set (const TBtreeToken &, TBtreeMode )
IMPORT_C TBtreeToken Token ()
Private Member Functions
TBool AscendAtFirstL ( TBtreePath &)
TBool AscendAtLastL ( TBtreePath &)
void BeginUpdateL ()
void CheckIntactL ()
TPageRef ChildNodeL (const TBtreePath &)
TPageRef ChildNodeL ( TBtreePath &, TInt )
void DeleteAtL ( TBtreePath &)
void DeleteIndexNodesL ( TBtreePath &, TBool )
void DeleteIndexSetL ()
void DescendFirstL ( TBtreePath &)
void DescendLastL ( TBtreePath &)
void EndUpdate ()
TAny * GetNodeL (const TBtreePath &)
void GotoRoot ( TBtreePath &)
void InsertAtL ( TBtreePath &, const TDesC8 &)
void InsertAtL ( TBtreePath &, TBtreePivot &, TPageRef )
TBool InsertAtL ( TBtreePath &, const TDesC8 &, TPageRef , TBtreePivot &, TPageRef &)
TBool IsRoot (const TBtreePath &)
TPageRef LastChildNodeL ( TBtreePath &)
TInt LastEntryL (const TBtreePath &)
void MarkIntact ()
void NewPivot (const TAny *, const TAny *, TBtreePivot &)
void NewRootL ()
void NewTreeL ()
const MBtreeNodeOrg * NodeOrg ( TBool )
void PutNode ( TAny *, TBool )
void ReplacePivotL ( TBtreePath &, TAny *, TBtreePivot &)
TBool SearchL ( TBtreePath &, const TAny *, TBool )
Public Member Enumerations
enum TFind { 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_C TBtree ( TBtreeMode aMode )

Constructor that sets the B-tree mode.

Parameters

TBtreeMode aMode B-tree operating mode

TBtree(const TBtreeToken &, TBtreeMode)

IMPORT_C TBtree ( const TBtreeToken & aToken,
TBtreeMode aMode
)

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

Parameters

const TBtreeToken & aToken Parameters with which to initialise B-tree
TBtreeMode aMode B-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()

void BeginUpdateL ( ) [private]

CheckIntactL()

void CheckIntactL ( ) const [private]

ChildNodeL(const TBtreePath &)

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

Parameters

const TBtreePath & aPath

ChildNodeL(TBtreePath &, TInt)

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

Parameters

TBtreePath & aPath
TInt aChild

ClearL()

IMPORT_C void ClearL ( )

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 void Connect ( 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 void DeleteAtL ( TBtreePos & aPos )

Deletes the entry at the specified position

Parameters

TBtreePos & aPos Position of the entry to delete

DeleteAtL(TBtreePath &)

void DeleteAtL ( TBtreePath & aPath ) [private]

Parameters

TBtreePath & aPath

DeleteIndexNodesL(TBtreePath &, TBool)

void DeleteIndexNodesL ( TBtreePath & aPath,
TBool aLeadingEdge
) [private]

Parameters

TBtreePath & aPath
TBool aLeadingEdge

DeleteIndexSetL()

void DeleteIndexSetL ( ) [private]

DeleteL(const TAny *)

IMPORT_C TBool DeleteL ( const TAny * aKey )

Deletes an entry.

Parameters

const TAny * aKey Pointer to the key of the entry to delete

DescendFirstL(TBtreePath &)

void DescendFirstL ( TBtreePath & aPath ) const [private]

Parameters

TBtreePath & aPath

DescendLastL(TBtreePath &)

void DescendLastL ( TBtreePath & aPath ) const [private]

Parameters

TBtreePath & aPath

EndUpdate()

void EndUpdate ( ) [private]

ExtractAtL(const TBtreePos &, TAny *, TInt)

IMPORT_C void ExtractAtL ( const TBtreePos & aPos,
TAny * anEntry,
TInt aMaxLength
) const

Gets the entry at the specified position.

Parameters

const TBtreePos & aPos Position of the entry to get
TAny * anEntry Buffer into which to copy the entry
TInt aMaxLength Length 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 void ExtractAtL ( const TBtreeMark & aMark,
TAny * anEntry,
TInt aMaxLength
) const

Gets an entry at specified iterator position.

Parameters

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

FindL(TBtreePos &, const TAny *, TFind)

IMPORT_C TBool FindL ( TBtreePos & aPos,
const TAny * aKey,
TFind aMode = EEqualTo
) const

Searches for an entry and returns its position.

Parameters

TBtreePos & aPos On return, the position of the entry found
const TAny * aKey Pointer to the key of the entry for which to search
TFind aMode = EEqualTo Type of search to perform

FirstL(TBtreePos &)

IMPORT_C TBool FirstL ( TBtreePos & aPos ) const

Goes to the first entry in the B-tree.

Parameters

TBtreePos & aPos On return, the position of the first entry

GetNodeL(const TBtreePath &)

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

Parameters

const TBtreePath & aPath

GotoRoot(TBtreePath &)

void GotoRoot ( TBtreePath & aPath ) const [private]

Parameters

TBtreePath & aPath

InsertAtL(TBtreePath &, const TDesC8 &)

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

Parameters

TBtreePath & aPath
const TDesC8 & anEntry

InsertAtL(TBtreePath &, TBtreePivot &, TPageRef)

void InsertAtL ( TBtreePath & aPath,
TBtreePivot & aPivot,
TPageRef aChild
) [private]

Parameters

TBtreePath & aPath
TBtreePivot & aPivot
TPageRef aChild

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

TBool InsertAtL ( TBtreePath & aPath,
const TDesC8 & anEntry,
TPageRef aChild,
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 TBool InsertL ( TBtreePos & aPos,
const TAny * anEntry,
TInt aLength,
TAllowDuplicates aDup = ENoDuplicates
)

Inserts an entry into the tree.

Parameters

TBtreePos & aPos On return, the position of the entry inserted
const TAny * anEntry Pointer to the entry to insert
TInt aLength Length of entry
TAllowDuplicates aDup = ENoDuplicates Flag 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 TBool LastL ( TBtreePos & aPos ) const

Goes to the last entry in the B-tree.

Parameters

TBtreePos & aPos On return, the position of the last entry

MarkBroken()

void MarkBroken ( ) [inline]

Sets the broken flag.

MarkCurrent()

void MarkCurrent ( ) [inline]

Clears the dirty flag.

MarkDirty()

void MarkDirty ( ) [inline]

Sets the dirty flag.

MarkIntact()

void MarkIntact ( ) [private, inline]

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

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

Parameters

const TAny * aLeftNode
const TAny * aRightNode
TBtreePivot & aPivot

NewRootL()

void NewRootL ( ) [private]

NewTreeL()

void NewTreeL ( ) [private]

NextL(TBtreePos &)

IMPORT_C TBool NextL ( TBtreePos & aPos ) const

Gets the position of the entry following the specified entry.

Parameters

TBtreePos & aPos On return, the position of the next entry

NextL(TBtreeMark &)

IMPORT_C TBool NextL ( TBtreeMark & aMark ) const

Advances an iterator to the next entry.

Parameters

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

NodeOrg(TBool)

const MBtreeNodeOrg * NodeOrg ( TBool aLeaf ) const [private, inline]

Parameters

TBool aLeaf

PreviousL(TBtreePos &)

IMPORT_C TBool PreviousL ( TBtreePos & aPos ) const

Gets the position of the entry preceding the specified entry.

Parameters

TBtreePos & aPos On return, the position of the preceding entry

PutNode(TAny *, TBool)

void PutNode ( TAny * aNode,
TBool aLeaf
) const [private]

Parameters

TAny * aNode
TBool aLeaf

RepairL()

IMPORT_C TInt RepairL ( )

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 &)

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

Parameters

TBtreePath & aPath
TAny * aNode
TBtreePivot & aPivot

ResetL(TBtreeMark &)

IMPORT_C TBool ResetL ( TBtreeMark & aMark ) const

Resets an iterator to the root of the tree.

Parameters

TBtreeMark & aMark Iterator to set

SearchL(TBtreePath &, const TAny *, TBool)

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

Parameters

TBtreePath & aPath
const TAny * aKey
TBool aAfter = EFalse

Set(const TBtreeToken &, TBtreeMode)

IMPORT_C void Set ( const TBtreeToken & aToken,
TBtreeMode aMode
)

Initialises the B-tree.

Parameters

const TBtreeToken & aToken Parameters with which to initialise the B-tree
TBtreeMode aMode B-tree operating mode

Token()

IMPORT_C TBtreeToken Token ( ) 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.