// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

//

#include "UB_STD.H"

//#pragma message( __FILE__ " : 'TBtreePath' does not track insertion position" )

//#pragma message( __FILE__ " : 'TBtreePath' record of last entry unused" )

//#pragma message( __FILE__ " : 'TBtree' lots of opportunities for on-the-fly integrity checking" )

EXPORT_C void TBtreeToken::ExternalizeL(RWriteStream& aStream) const

/** Externalises a TBtreeToken object to a stream.

@param aStream Stream to which the object should be externalised. */

	{

	aStream<<iFirst;

	aStream<<iRoot;

	aStream.WriteInt8L(iHeight);

	}

EXPORT_C void TBtreeToken::InternalizeL(RReadStream& aStream)

/** Internalises a TBtreeToken object from a stream.

@param aStream Stream from which the object should be internalised. */

	{

	aStream>>iFirst;

	aStream>>iRoot;

	TInt height=aStream.ReadInt8L();

	if (height<0||height>KMaxBtreeHeight)

		__LEAVE(KErrCorrupt);

//

	iHeight=height;

	}

EXPORT_C void TBtreeToken::Clear()

	{

	iFirst=KNullPageRef;

	iRoot=KNullPageRef;

	iHeight=0;

	}

void TBtreePath::Push(TPageRef aRef,TInt aEntry)

	{

	__ASSERT_DEBUG(aEntry==TInt(TUint8(aEntry)),Panic(EBadEntryPos));

	TInt end=--iEnd;

	__ASSERT_DEBUG(end>=0,Panic(EPathUnderflow));

	iNodes[end]=aRef;

	iEntries[end]=TUint8(aEntry);

	}

void TBtreePath::GotoRoot(TBtreeHeight aHeight,TPageRef aRoot)

//

// Set the end of path to height and root-node given.

//

	{

	__ASSERT_DEBUG(aHeight>0&&aHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));

	iEnd=--aHeight;

	iNodes[aHeight]=aRoot;

	iEntries[aHeight]=0;

	}

EXPORT_C TBtree::TBtree(TBtreeMode aMode)

	: iPages(NULL),iFirst(KNullPageRef),iRoot(KNullPageRef),iHeight(0),iStatus(aMode)

/** Constructor that sets the B-tree mode.

@param aMode B-tree operating mode */

	{}

EXPORT_C TBtree::TBtree(const TBtreeToken& aToken,TBtreeMode aMode)

	: iPages(NULL)

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

@param aToken Parameters with which to initialise B-tree

@param aMode B-tree operating mode */

	{

	Set(aToken,aMode);

	__ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));

	}

EXPORT_C void TBtree::Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg)

	{

	iPages=aPool;

	iKey=aKey;

	iLeafOrg=aLeafOrg;

	iIndexOrg=anIndexOrg;

	}

EXPORT_C void TBtree::Set(const TBtreeToken& aToken,TBtreeMode aMode)

/** Initialises the B-tree.

@param aToken Parameters with which to initialise the B-tree

@param aMode B-tree operating mode */

	{

	iFirst=aToken.iFirst;

	iRoot=aToken.iRoot;

	iHeight=aToken.iHeight;

	iStatus=aToken.IsBroken()?aMode|EBroken:aMode;

	__ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));

	}

EXPORT_C TBtreeToken TBtree::Token() const

/** Gets an object that encapsulates the TBtree settings. 

That object can then be used to externalise the settings.

@return Encapsulates the TBtree settings. */

	{

	return TBtreeToken(iFirst,iRoot,IsIntact()?iHeight:0);

	}

EXPORT_C TBool TBtree::FirstL(TBtreePos& aPos) const

/** Goes to the first entry in the B-tree.

@param aPos On return, the position of the first entry

@return True if there is a first entry, otherwise false */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	CheckIntactL();

	if (IsEmpty())

		return EFalse;

//

	TBtreePath& path=aPos.iPath;

	GotoRoot(path);

	DescendFirstL(path);

	return ETrue;

	}

EXPORT_C TBool TBtree::LastL(TBtreePos& aPos) const

/** Goes to the last entry in the B-tree.

@param aPos On return, the position of the last entry

@return True if there are any entries, otherwise false */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	CheckIntactL();

	if (IsEmpty())

		return EFalse;

//

	TBtreePath& path=aPos.iPath;

	GotoRoot(path);

	DescendLastL(path);

	return ETrue;

	}

EXPORT_C TBool TBtree::NextL(TBtreePos& aPos) const

/** Gets the position of the entry following the specified entry.

@param aPos On return, the position of the next entry

@return True if there are any more entries, otherwise false */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	TBtreePath& path=aPos.iPath;

	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));

	CheckIntactL();

	if (IsEmpty()||!AscendAtLastL(path))

		return EFalse;

//

	DescendFirstL(path);

	return ETrue;

	}

EXPORT_C TBool TBtree::PreviousL(TBtreePos& aPos) const

/** Gets the position of the entry preceding the specified entry.

@param aPos On return, the position of the preceding entry

@return True if there is a preceding entry, otherwise false */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	TBtreePath& path=aPos.iPath;

	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));

	CheckIntactL();

	if (IsEmpty()||!AscendAtFirstL(path))

		return EFalse;

//

	if (!path.IsLeaf())

		{

		path.Push(ChildNodeL(path));

		DescendLastL(path);

		}

	return ETrue;

	}

EXPORT_C void TBtree::ClearL()

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

pages. */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	if (IsEmpty())

		return;

	BeginUpdateL();

	DeleteIndexSetL();

	while (iFirst!=KNullPageRef)

		{

		TPageRef link=iLeafOrg->LinkNode(iPages->LockL(iFirst));

		iPages->DeleteL(iFirst);

		iFirst=link;

		}

	EndUpdate();

	}

EXPORT_C TInt TBtree::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.

@return Number of leaves in the tree

@see TBtreeMode */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	if (IsEmpty())

		return 0;

	BeginUpdateL();

	DeleteIndexSetL();

// create the new index set, insert pivots on the end of the index set

	iHeight=1;

	iRoot=iFirst;

	TBtreePath path;

	TBtreePivot pivot;

	TInt count=0;

	TAny* seq=iPages->LockL(iFirst);

	for (;;)

		{

		count+=iLeafOrg->LastEntry(seq);

		TPageRef link=iLeafOrg->LinkNode(seq);

		if (link==KNullPageRef)

			break;

		TAny* next=iPages->LockL(link);

		NewPivot(seq,next,pivot);

		iPages->Unlock(seq);

		seq=next;

		if (iHeight==1)

			{	// first insertion, create a new index set

			iRoot=iFirst;

			NewRootL();

			GotoRoot(path);

			}

		TBtreeHeight end=path.End();

		InsertAtL(path,pivot,link);

		if (path.End()!=end)

			{	// path has been messed up by insertion, set path to last index entry

			GotoRoot(path);

			do path.Push(LastChildNodeL(path)); while (!path.IsLeaf());

			path.Pop();

			}

		else

			path.SetEntry(path.Entry()+1);

		}

	iPages->Unlock(seq);

	EndUpdate();

	return count;

	}

EXPORT_C TBool TBtree::FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode) const

/** Searches for an entry and returns its position. 

@param aPos On return, the position of the entry found

@param aKey Pointer to the key of the entry for which to search

@param aMode Type of search to perform

@return True if search was successful, else false */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	CheckIntactL();

	if (IsEmpty())

		return EFalse;

	TBtreePath& path=aPos.iPath;

	TBool match=SearchL(path,aKey,aMode==ELessEqual||aMode==EGreaterThan);

	switch (aMode)

		{

	case EGreaterThan:

	case EGreaterEqual:	// move on if at end of node

		if (LastEntryL(path)==path.Entry())

			return NextL(aPos);

		return ETrue;

	case ELessThan:

	case ELessEqual:

		return PreviousL(aPos);

	case EEqualTo:

		break;

		}

	return match;

	}

EXPORT_C TBool TBtree::InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup)

/** Inserts an entry into the tree.

@param aPos On return, the position of the entry inserted

@param anEntry Pointer to the entry to insert

@param aLength Length of entry

@param aDup Flag to indicate whether duplicate entries are allowed in the tree

@return True if successful, false if the entry was a duplicate and aDup was 

set to ENoDuplicates */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	CheckIntactL();

	TBtreePath& path=aPos.iPath;

	if (IsEmpty())

		{

		NewTreeL();

		GotoRoot(path);

		}

	else

		{

		if (SearchL(path,iKey->Key(anEntry))&&aDup==ENoDuplicates)

			return EFalse;	// oops a duplicate

		}

	InsertAtL(path,TPtrC8((const TUint8*)anEntry,aLength));

	return ETrue;

	}

EXPORT_C TBool TBtree::DeleteL(const TAny* aKey)

/** Deletes an entry.

@param aKey Pointer to the key of the entry to delete

@return True if successful, false if the entry was not found */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	CheckIntactL();

	TBtreePath path;

	if (IsEmpty()||SearchL(path,aKey)==0)

		return EFalse;		// not found

	DeleteAtL(path);

	return ETrue;

	}

EXPORT_C void TBtree::DeleteAtL(TBtreePos& aPos)

/** Deletes the entry at the specified position

@param aPos Position of the entry to delete */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	TBtreePath& path=aPos.iPath;

	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));

	CheckIntactL();

	DeleteAtL(path);

	}

EXPORT_C void TBtree::ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const

/** Gets the entry at the specified position.

@param aPos Position of the entry to get

@param anEntry Buffer into which to copy the entry

@param aMaxLength Length of the anEntry buffer. If the entry is longer than 

this, only the first aMaxLength bytes will be copied. */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	const TBtreePath& path=aPos.iPath;

	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));

	CheckIntactL();

	TAny* pp=GetNodeL(path);

	TPtrC8 entry=iLeafOrg->Entry(pp,path.Entry());

	Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));

	iPages->Unlock(pp);

	}

EXPORT_C TBool TBtree::ResetL(TBtreeMark& aMark) const

/** Resets an iterator to the root of the tree.

@param aMark Iterator to set

@return True if successful, false if the B-tree is empty */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	if (IsEmpty())

		return EFalse;

//

	TAny* first=iPages->LockL(iFirst);

	aMark.iLeaf=iFirst;

	aMark.iLink=iLeafOrg->LinkNode(first);

	aMark.iEntry=0;

	aMark.iLast=TUint8(iLeafOrg->LastEntry(first));

	iPages->Unlock(first);

	return ETrue;

	}

EXPORT_C TBool TBtree::NextL(TBtreeMark& aMark) const

/** Advances an iterator to the next entry.

@param aMark Iterator to use. On return, the iterator is advanced to the next 

entry.

@return True if successful, false if there is no next entry */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	if (IsEmpty())

		return EFalse;

//

	++aMark.iEntry;

	if (aMark.iEntry<aMark.iLast)

		return ETrue;

//

	if (aMark.iLink!=KNullPageRef)

		{

		TAny* next=iPages->LockL(aMark.iLink);

		aMark.iLeaf=aMark.iLink;

		aMark.iLink=iLeafOrg->LinkNode(next);

		aMark.iEntry=0;

		aMark.iLast=TUint8(iLeafOrg->LastEntry(next));

		iPages->Unlock(next);

		return ETrue;

		}

//

	return EFalse;

	}

EXPORT_C void TBtree::ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const

/** Gets an entry at specified iterator position.

@param aMark Position of the entry to get

@param anEntry Buffer into which to copy the entry

@param aMaxLength Length of anEntry buffer. If the entry is longer than this, 

only the first aMaxLength bytes are copied. */

	{

	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));

	TAny* pp=iPages->LockL(aMark.iLeaf);

	TPtrC8 entry=iLeafOrg->Entry(pp,aMark.iEntry);

	Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));

	iPages->Unlock(pp);

	}

TBool TBtree::AscendAtLastL(TBtreePath& aPath) const

//

// While aPath is at the end of its node, ascend.

// If not at end, then move right and return true. Return false if we've run out of tree.

//

	{

	for (;;)

		{

		TInt last=LastEntryL(aPath);

		if (aPath.IsLeaf())

			--last;

		TInt entry=aPath.Entry();

		if (entry<last)

			{

			aPath.SetEntry(entry+1);

			return ETrue;	// have a next entry at this level

			}

		if (IsRoot(aPath))

			return EFalse;		// end of tree

		aPath.Pop();

		}

	}

TBool TBtree::AscendAtFirstL(TBtreePath& aPath) const

//

// While aPath is at the beginning of its node, ascend.

// If not at start, then move left and return true. Return false if we've run out of tree.

//

	{

	for (;;)

		{

		TInt entry=aPath.Entry();

		if (entry>0)

			{

			aPath.SetEntry(entry-1);

			return ETrue;		// have a previous entry at this level

			}

		if (IsRoot(aPath))

			return EFalse;		// beginning of sequence

		aPath.Pop();

		}

	}

void TBtree::DescendFirstL(TBtreePath& aPath) const

//

// Descend the tree to next entry on the bottom level.

//

	{

	while (!aPath.IsLeaf())

		aPath.Push(ChildNodeL(aPath));

	}

void TBtree::DescendLastL(TBtreePath& aPath) const

//

// Descend the tree to the last entry on the bottom level.

//

	{

	while (!aPath.IsLeaf())

		aPath.Push(LastChildNodeL(aPath));

	aPath.SetEntry(LastEntryL(aPath)-1);

	}

TBool TBtree::SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter) const

//

// Search the B-tree for an entry. Return true if an exact match is found at base level.

//

	{

	__ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));

	TInt entry;

	GotoRoot(aPath);

	while (!aPath.IsLeaf())

		{

		TAny* pp=GetNodeL(aPath);

		iIndexOrg->Search(pp,aKey,*iKey,aAfter,entry);

		aPath.SetEntry(entry);

		aPath.Push(iIndexOrg->ChildNode(pp,entry));

		iPages->Unlock(pp);

		}

	TAny* pp=GetNodeL(aPath);

	TBool found=iLeafOrg->Search(pp,aKey,*iKey,aAfter,entry);

	aPath.SetEntry(entry);

	iPages->Unlock(pp);

	return found;

	}

void TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry)

//

// Insert anEntry at the current entry in aPath.

//

	{

	TBtreePivot pivot;

	TPageRef promote;

	BeginUpdateL();