sl@0: // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: //
sl@0: 
sl@0: #include "UB_STD.H"
sl@0: 
sl@0: //#pragma message( __FILE__ " : 'TBtreePath' does not track insertion position" )
sl@0: //#pragma message( __FILE__ " : 'TBtreePath' record of last entry unused" )
sl@0: //#pragma message( __FILE__ " : 'TBtree' lots of opportunities for on-the-fly integrity checking" )
sl@0: 
sl@0: EXPORT_C void TBtreeToken::ExternalizeL(RWriteStream& aStream) const
sl@0: /** Externalises a TBtreeToken object to a stream.
sl@0: 
sl@0: @param aStream Stream to which the object should be externalised. */
sl@0: 	{
sl@0: 	aStream<<iFirst;
sl@0: 	aStream<<iRoot;
sl@0: 	aStream.WriteInt8L(iHeight);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtreeToken::InternalizeL(RReadStream& aStream)
sl@0: /** Internalises a TBtreeToken object from a stream.
sl@0: 
sl@0: @param aStream Stream from which the object should be internalised. */
sl@0: 	{
sl@0: 	aStream>>iFirst;
sl@0: 	aStream>>iRoot;
sl@0: 	TInt height=aStream.ReadInt8L();
sl@0: 	if (height<0||height>KMaxBtreeHeight)
sl@0: 		__LEAVE(KErrCorrupt);
sl@0: //
sl@0: 	iHeight=height;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtreeToken::Clear()
sl@0: 	{
sl@0: 	iFirst=KNullPageRef;
sl@0: 	iRoot=KNullPageRef;
sl@0: 	iHeight=0;
sl@0: 	}
sl@0: 
sl@0: void TBtreePath::Push(TPageRef aRef,TInt aEntry)
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(aEntry==TInt(TUint8(aEntry)),Panic(EBadEntryPos));
sl@0: 	TInt end=--iEnd;
sl@0: 	__ASSERT_DEBUG(end>=0,Panic(EPathUnderflow));
sl@0: 	iNodes[end]=aRef;
sl@0: 	iEntries[end]=TUint8(aEntry);
sl@0: 	}
sl@0: 
sl@0: void TBtreePath::GotoRoot(TBtreeHeight aHeight,TPageRef aRoot)
sl@0: //
sl@0: // Set the end of path to height and root-node given.
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(aHeight>0&&aHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
sl@0: 	iEnd=--aHeight;
sl@0: 	iNodes[aHeight]=aRoot;
sl@0: 	iEntries[aHeight]=0;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBtree::TBtree(TBtreeMode aMode)
sl@0: 	: iPages(NULL),iFirst(KNullPageRef),iRoot(KNullPageRef),iHeight(0),iStatus(aMode)
sl@0: /** Constructor that sets the B-tree mode.
sl@0: 
sl@0: @param aMode B-tree operating mode */
sl@0: 	{}
sl@0: 
sl@0: EXPORT_C TBtree::TBtree(const TBtreeToken& aToken,TBtreeMode aMode)
sl@0: 	: iPages(NULL)
sl@0: /** Constructor that sets the B-tree mode and initialisation parameters.
sl@0: 
sl@0: @param aToken Parameters with which to initialise B-tree
sl@0: @param aMode B-tree operating mode */
sl@0: 	{
sl@0: 	Set(aToken,aMode);
sl@0: 	__ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg)
sl@0: 	{
sl@0: 	iPages=aPool;
sl@0: 	iKey=aKey;
sl@0: 	iLeafOrg=aLeafOrg;
sl@0: 	iIndexOrg=anIndexOrg;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::Set(const TBtreeToken& aToken,TBtreeMode aMode)
sl@0: /** Initialises the B-tree.
sl@0: 
sl@0: @param aToken Parameters with which to initialise the B-tree
sl@0: @param aMode B-tree operating mode */
sl@0: 	{
sl@0: 	iFirst=aToken.iFirst;
sl@0: 	iRoot=aToken.iRoot;
sl@0: 	iHeight=aToken.iHeight;
sl@0: 	iStatus=aToken.IsBroken()?aMode|EBroken:aMode;
sl@0: 	__ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBtreeToken TBtree::Token() const
sl@0: /** Gets an object that encapsulates the TBtree settings. 
sl@0: 
sl@0: That object can then be used to externalise the settings.
sl@0: 
sl@0: @return Encapsulates the TBtree settings. */
sl@0: 	{
sl@0: 	return TBtreeToken(iFirst,iRoot,IsIntact()?iHeight:0);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::FirstL(TBtreePos& aPos) const
sl@0: /** Goes to the first entry in the B-tree.
sl@0: 
sl@0: @param aPos On return, the position of the first entry
sl@0: @return True if there is a first entry, otherwise false */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	CheckIntactL();
sl@0: 	if (IsEmpty())
sl@0: 		return EFalse;
sl@0: //
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	GotoRoot(path);
sl@0: 	DescendFirstL(path);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::LastL(TBtreePos& aPos) const
sl@0: /** Goes to the last entry in the B-tree.
sl@0: 
sl@0: @param aPos On return, the position of the last entry
sl@0: @return True if there are any entries, otherwise false */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	CheckIntactL();
sl@0: 	if (IsEmpty())
sl@0: 		return EFalse;
sl@0: //
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	GotoRoot(path);
sl@0: 	DescendLastL(path);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::NextL(TBtreePos& aPos) const
sl@0: /** Gets the position of the entry following the specified entry.
sl@0: 
sl@0: @param aPos On return, the position of the next entry
sl@0: @return True if there are any more entries, otherwise false */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	CheckIntactL();
sl@0: 	if (IsEmpty()||!AscendAtLastL(path))
sl@0: 		return EFalse;
sl@0: //
sl@0: 	DescendFirstL(path);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::PreviousL(TBtreePos& aPos) const
sl@0: /** Gets the position of the entry preceding the specified entry.
sl@0: 
sl@0: @param aPos On return, the position of the preceding entry
sl@0: @return True if there is a preceding entry, otherwise false */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	CheckIntactL();
sl@0: 	if (IsEmpty()||!AscendAtFirstL(path))
sl@0: 		return EFalse;
sl@0: //
sl@0: 	if (!path.IsLeaf())
sl@0: 		{
sl@0: 		path.Push(ChildNodeL(path));
sl@0: 		DescendLastL(path);
sl@0: 		}
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::ClearL()
sl@0: /** Resets the B-tree to have zero-height, and a null root, and deletes all index 
sl@0: pages. */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	if (IsEmpty())
sl@0: 		return;
sl@0: 	BeginUpdateL();
sl@0: 	DeleteIndexSetL();
sl@0: 	while (iFirst!=KNullPageRef)
sl@0: 		{
sl@0: 		TPageRef link=iLeafOrg->LinkNode(iPages->LockL(iFirst));
sl@0: 		iPages->DeleteL(iFirst);
sl@0: 		iFirst=link;
sl@0: 		}
sl@0: 	EndUpdate();
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TInt TBtree::RepairL()
sl@0: /** Attempts to repair a broken B-tree.
sl@0: 
sl@0: If the operating mode (TBtreeMode) is set to EBtreeSecure, then the tree can 
sl@0: be repaired without any loss of data. Otherwise, the tree must be deleted 
sl@0: entirely using ClearL(), and reconstructed using other means. 
sl@0: 
sl@0: Note that if multiple B-trees share a single store page pool, then reclaiming 
sl@0: the pool will break all the other B-trees (but the Broken flag will not be 
sl@0: set automatically). These trees can be repaired by calling MarkBroken() and 
sl@0: then RepairL(), even if they were not of the EBtreeSecure type.
sl@0: 
sl@0: @return Number of leaves in the tree
sl@0: @see TBtreeMode */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	if (IsEmpty())
sl@0: 		return 0;
sl@0: 	BeginUpdateL();
sl@0: 	DeleteIndexSetL();
sl@0: // create the new index set, insert pivots on the end of the index set
sl@0: 	iHeight=1;
sl@0: 	iRoot=iFirst;
sl@0: 	TBtreePath path;
sl@0: 	TBtreePivot pivot;
sl@0: 	TInt count=0;
sl@0: 	TAny* seq=iPages->LockL(iFirst);
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		count+=iLeafOrg->LastEntry(seq);
sl@0: 		TPageRef link=iLeafOrg->LinkNode(seq);
sl@0: 		if (link==KNullPageRef)
sl@0: 			break;
sl@0: 		TAny* next=iPages->LockL(link);
sl@0: 		NewPivot(seq,next,pivot);
sl@0: 		iPages->Unlock(seq);
sl@0: 		seq=next;
sl@0: 		if (iHeight==1)
sl@0: 			{	// first insertion, create a new index set
sl@0: 			iRoot=iFirst;
sl@0: 			NewRootL();
sl@0: 			GotoRoot(path);
sl@0: 			}
sl@0: 		TBtreeHeight end=path.End();
sl@0: 		InsertAtL(path,pivot,link);
sl@0: 		if (path.End()!=end)
sl@0: 			{	// path has been messed up by insertion, set path to last index entry
sl@0: 			GotoRoot(path);
sl@0: 			do path.Push(LastChildNodeL(path)); while (!path.IsLeaf());
sl@0: 			path.Pop();
sl@0: 			}
sl@0: 		else
sl@0: 			path.SetEntry(path.Entry()+1);
sl@0: 		}
sl@0: 	iPages->Unlock(seq);
sl@0: 	EndUpdate();
sl@0: 	return count;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode) const
sl@0: /** Searches for an entry and returns its position. 
sl@0: 
sl@0: @param aPos On return, the position of the entry found
sl@0: @param aKey Pointer to the key of the entry for which to search
sl@0: @param aMode Type of search to perform
sl@0: @return True if search was successful, else false */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	CheckIntactL();
sl@0: 	if (IsEmpty())
sl@0: 		return EFalse;
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	TBool match=SearchL(path,aKey,aMode==ELessEqual||aMode==EGreaterThan);
sl@0: 	switch (aMode)
sl@0: 		{
sl@0: 	case EGreaterThan:
sl@0: 	case EGreaterEqual:	// move on if at end of node
sl@0: 		if (LastEntryL(path)==path.Entry())
sl@0: 			return NextL(aPos);
sl@0: 		return ETrue;
sl@0: 	case ELessThan:
sl@0: 	case ELessEqual:
sl@0: 		return PreviousL(aPos);
sl@0: 	case EEqualTo:
sl@0: 		break;
sl@0: 		}
sl@0: 	return match;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup)
sl@0: /** Inserts an entry into the tree.
sl@0: 
sl@0: @param aPos On return, the position of the entry inserted
sl@0: @param anEntry Pointer to the entry to insert
sl@0: @param aLength Length of entry
sl@0: @param aDup Flag to indicate whether duplicate entries are allowed in the tree
sl@0: @return True if successful, false if the entry was a duplicate and aDup was 
sl@0: set to ENoDuplicates */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	CheckIntactL();
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	if (IsEmpty())
sl@0: 		{
sl@0: 		NewTreeL();
sl@0: 		GotoRoot(path);
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		if (SearchL(path,iKey->Key(anEntry))&&aDup==ENoDuplicates)
sl@0: 			return EFalse;	// oops a duplicate
sl@0: 		}
sl@0: 	InsertAtL(path,TPtrC8((const TUint8*)anEntry,aLength));
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::DeleteL(const TAny* aKey)
sl@0: /** Deletes an entry.
sl@0: 
sl@0: @param aKey Pointer to the key of the entry to delete
sl@0: @return True if successful, false if the entry was not found */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	CheckIntactL();
sl@0: 	TBtreePath path;
sl@0: 	if (IsEmpty()||SearchL(path,aKey)==0)
sl@0: 		return EFalse;		// not found
sl@0: 	DeleteAtL(path);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::DeleteAtL(TBtreePos& aPos)
sl@0: /** Deletes the entry at the specified position
sl@0: 
sl@0: @param aPos Position of the entry to delete */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	TBtreePath& path=aPos.iPath;
sl@0: 	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	CheckIntactL();
sl@0: 	DeleteAtL(path);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const
sl@0: /** Gets the entry at the specified position.
sl@0: 
sl@0: @param aPos Position of the entry to get
sl@0: @param anEntry Buffer into which to copy the entry
sl@0: @param aMaxLength Length of the anEntry buffer. If the entry is longer than 
sl@0: this, only the first aMaxLength bytes will be copied. */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	const TBtreePath& path=aPos.iPath;
sl@0: 	__ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	CheckIntactL();
sl@0: 	TAny* pp=GetNodeL(path);
sl@0: 	TPtrC8 entry=iLeafOrg->Entry(pp,path.Entry());
sl@0: 	Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));
sl@0: 	iPages->Unlock(pp);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::ResetL(TBtreeMark& aMark) const
sl@0: /** Resets an iterator to the root of the tree.
sl@0: 
sl@0: @param aMark Iterator to set
sl@0: @return True if successful, false if the B-tree is empty */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	if (IsEmpty())
sl@0: 		return EFalse;
sl@0: //
sl@0: 	TAny* first=iPages->LockL(iFirst);
sl@0: 	aMark.iLeaf=iFirst;
sl@0: 	aMark.iLink=iLeafOrg->LinkNode(first);
sl@0: 	aMark.iEntry=0;
sl@0: 	aMark.iLast=TUint8(iLeafOrg->LastEntry(first));
sl@0: 	iPages->Unlock(first);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TBtree::NextL(TBtreeMark& aMark) const
sl@0: /** Advances an iterator to the next entry.
sl@0: 
sl@0: @param aMark Iterator to use. On return, the iterator is advanced to the next 
sl@0: entry.
sl@0: @return True if successful, false if there is no next entry */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	if (IsEmpty())
sl@0: 		return EFalse;
sl@0: //
sl@0: 	++aMark.iEntry;
sl@0: 	if (aMark.iEntry<aMark.iLast)
sl@0: 		return ETrue;
sl@0: //
sl@0: 	if (aMark.iLink!=KNullPageRef)
sl@0: 		{
sl@0: 		TAny* next=iPages->LockL(aMark.iLink);
sl@0: 		aMark.iLeaf=aMark.iLink;
sl@0: 		aMark.iLink=iLeafOrg->LinkNode(next);
sl@0: 		aMark.iEntry=0;
sl@0: 		aMark.iLast=TUint8(iLeafOrg->LastEntry(next));
sl@0: 		iPages->Unlock(next);
sl@0: 		return ETrue;
sl@0: 		}
sl@0: //
sl@0: 	return EFalse;
sl@0: 	}
sl@0: 
sl@0: EXPORT_C void TBtree::ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const
sl@0: /** Gets an entry at specified iterator position.
sl@0: 
sl@0: @param aMark Position of the entry to get
sl@0: @param anEntry Buffer into which to copy the entry
sl@0: @param aMaxLength Length of anEntry buffer. If the entry is longer than this, 
sl@0: only the first aMaxLength bytes are copied. */
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
sl@0: 	TAny* pp=iPages->LockL(aMark.iLeaf);
sl@0: 	TPtrC8 entry=iLeafOrg->Entry(pp,aMark.iEntry);
sl@0: 	Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));
sl@0: 	iPages->Unlock(pp);
sl@0: 	}
sl@0: 
sl@0: TBool TBtree::AscendAtLastL(TBtreePath& aPath) const
sl@0: //
sl@0: // While aPath is at the end of its node, ascend.
sl@0: // If not at end, then move right and return true. Return false if we've run out of tree.
sl@0: //
sl@0: 	{
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TInt last=LastEntryL(aPath);
sl@0: 		if (aPath.IsLeaf())
sl@0: 			--last;
sl@0: 		TInt entry=aPath.Entry();
sl@0: 		if (entry<last)
sl@0: 			{
sl@0: 			aPath.SetEntry(entry+1);
sl@0: 			return ETrue;	// have a next entry at this level
sl@0: 			}
sl@0: 		if (IsRoot(aPath))
sl@0: 			return EFalse;		// end of tree
sl@0: 		aPath.Pop();
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool TBtree::AscendAtFirstL(TBtreePath& aPath) const
sl@0: //
sl@0: // While aPath is at the beginning of its node, ascend.
sl@0: // If not at start, then move left and return true. Return false if we've run out of tree.
sl@0: //
sl@0: 	{
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TInt entry=aPath.Entry();
sl@0: 		if (entry>0)
sl@0: 			{
sl@0: 			aPath.SetEntry(entry-1);
sl@0: 			return ETrue;		// have a previous entry at this level
sl@0: 			}
sl@0: 		if (IsRoot(aPath))
sl@0: 			return EFalse;		// beginning of sequence
sl@0: 		aPath.Pop();
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TBtree::DescendFirstL(TBtreePath& aPath) const
sl@0: //
sl@0: // Descend the tree to next entry on the bottom level.
sl@0: //
sl@0: 	{
sl@0: 	while (!aPath.IsLeaf())
sl@0: 		aPath.Push(ChildNodeL(aPath));
sl@0: 	}
sl@0: 
sl@0: void TBtree::DescendLastL(TBtreePath& aPath) const
sl@0: //
sl@0: // Descend the tree to the last entry on the bottom level.
sl@0: //
sl@0: 	{
sl@0: 	while (!aPath.IsLeaf())
sl@0: 		aPath.Push(LastChildNodeL(aPath));
sl@0: 	aPath.SetEntry(LastEntryL(aPath)-1);
sl@0: 	}
sl@0: 
sl@0: TBool TBtree::SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter) const
sl@0: //
sl@0: // Search the B-tree for an entry. Return true if an exact match is found at base level.
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));
sl@0: 	TInt entry;
sl@0: 	GotoRoot(aPath);
sl@0: 	while (!aPath.IsLeaf())
sl@0: 		{
sl@0: 		TAny* pp=GetNodeL(aPath);
sl@0: 		iIndexOrg->Search(pp,aKey,*iKey,aAfter,entry);
sl@0: 		aPath.SetEntry(entry);
sl@0: 		aPath.Push(iIndexOrg->ChildNode(pp,entry));
sl@0: 		iPages->Unlock(pp);
sl@0: 		}
sl@0: 	TAny* pp=GetNodeL(aPath);
sl@0: 	TBool found=iLeafOrg->Search(pp,aKey,*iKey,aAfter,entry);
sl@0: 	aPath.SetEntry(entry);
sl@0: 	iPages->Unlock(pp);
sl@0: 	return found;
sl@0: 	}
sl@0: 
sl@0: void TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry)
sl@0: //
sl@0: // Insert anEntry at the current entry in aPath.
sl@0: //
sl@0: 	{
sl@0: 	TBtreePivot pivot;
sl@0: 	TPageRef promote;
sl@0: 	BeginUpdateL();
sl@0: 	if (InsertAtL(aPath,anEntry,KNullPageRef,pivot,promote))
sl@0: 		InsertAtL(aPath,pivot,promote);
sl@0: 	EndUpdate();
sl@0: 	}
sl@0: 
sl@0: void TBtree::NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const
sl@0: //
sl@0: // Get the key organisation to generate a new pivot between the given leaf nodes.
sl@0: //
sl@0: 	{
sl@0: 	const TAny* left=iLeafOrg->EntryPtr(aLeftNode,iLeafOrg->LastEntry(aLeftNode)-1);
sl@0: 	const TAny* right=iLeafOrg->EntryPtr(aRightNode,0);
sl@0: 	iKey->Between(iKey->Key(left),iKey->Key(right),aPivot);
sl@0: 	__DEBUG(TInt cleft=iKey->Compare(iKey->Key(left),aPivot.Ptr()));
sl@0: 	__DEBUG(TInt cright=iKey->Compare(iKey->Key(right),aPivot.Ptr()));
sl@0: 	__ASSERT_DEBUG((cleft<=0&&cright>0)||(cleft==0&&cright==0),Panic(EIllegalPivot));
sl@0: 	}
sl@0: 
sl@0: void TBtree::ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot)
sl@0: //
sl@0: // Replace current pivot entry in aPath with aPivot.
sl@0: //
sl@0: 	{
sl@0: 	TInt entry=aPath.Entry();
sl@0: 	// update the pivot in the parent
sl@0: 	if (iIndexOrg->Update(aNode,entry,aPivot))
sl@0: 		iPages->Unlock(aNode,EPageDirty);
sl@0: 	else
sl@0: 		{	// have to delete the old pivot and insert new one
sl@0: 		TPageRef child=iIndexOrg->ChildNode(aNode,entry+1);
sl@0: 		iIndexOrg->Delete(aNode,entry);
sl@0: 		iPages->Unlock(aNode,EPageDirty);
sl@0: 		InsertAtL(aPath,aPivot,child);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TBtree::InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild)
sl@0: 	{
sl@0: 	TBtreePivot togglePivot;
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		if (!InsertAtL(aPath,aPivot,aChild,togglePivot,aChild))
sl@0: 			break;
sl@0: 		if (!InsertAtL(aPath,togglePivot,aChild,aPivot,aChild))
sl@0: 			break;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote)
sl@0: //
sl@0: // Insert entry on this level. Return requirement to propagate with aPromote, aChild and aPath ready.
sl@0: //
sl@0: 	{
sl@0: 	TBool leaf=aPath.IsLeaf();
sl@0: 	const MBtreeNodeOrg* nodeOrg=NodeOrg(leaf);
sl@0: 	TInt entry=aPath.Entry();
sl@0: 	TAny* pNode=GetNodeL(aPath);
sl@0: 
sl@0: 	if (leaf?iLeafOrg->Insert(pNode,entry,anEntry):iIndexOrg->Insert(pNode,entry,anEntry,aChild))
sl@0: 		{
sl@0: 		PutNode(pNode,leaf);
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	// whatever happens next, we will affect the index set
sl@0: 	MarkBroken();
sl@0: 	// attempt an overflow insertion
sl@0: 	if (!IsRoot(aPath))
sl@0: 		{ // we have an ancestor
sl@0: 		TPageRef node=aPath.Node(); // save this in case we cannot overflow
sl@0: 		aPath.Pop();
sl@0: 		TInt child=aPath.Entry();
sl@0: 		TAny* pParent=GetNodeL(aPath);
sl@0: 		TAny* pSibling;
sl@0: 		if (child<iIndexOrg->LastEntry(pParent))
sl@0: 			{ // try to overflow to the right
sl@0: 			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child+1));
sl@0: 			if (leaf)
sl@0: 				{
sl@0: 				if (iLeafOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry))
sl@0: 					{
sl@0: 					NewPivot(pNode,pSibling,aPivot);
sl@0: overflowOK:			PutNode(pSibling,leaf);
sl@0: 					PutNode(pNode,leaf);
sl@0: 					aPath.SetEntry(child);
sl@0: 					ReplacePivotL(aPath,pParent,aPivot);
sl@0: 					return EFalse; // completed insertion
sl@0: 					}
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
sl@0: 				if (iIndexOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry,aChild,pivot,aPivot))
sl@0: 					goto overflowOK;
sl@0: 				}
sl@0: 			iPages->Unlock(pSibling);
sl@0: 			}
sl@0: 		if (--child>=0)
sl@0: 			{
sl@0: 			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child));
sl@0: 			if (leaf)
sl@0: 				{
sl@0: 				if (iLeafOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry))
sl@0: 					{
sl@0: 					NewPivot(pSibling,pNode,aPivot);
sl@0: 					goto overflowOK;
sl@0: 					}
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
sl@0: 				if (iIndexOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry,aChild,pivot,aPivot))
sl@0: 					goto overflowOK;
sl@0: 				}
sl@0: 			iPages->Unlock(pSibling);
sl@0: 			}
sl@0: 			// cannot overflow, so...
sl@0: 		iPages->Unlock(pParent);
sl@0: 		aPath.Push(node);
sl@0: 		}
sl@0: 
sl@0: 		// do a split insertion
sl@0: 	TAny* pSibling=iPages->AllocL();
sl@0: 	nodeOrg->Init(pSibling);
sl@0: 	if (leaf)
sl@0: 		{
sl@0: 		iLeafOrg->InsertSplit(pNode,pSibling,entry,anEntry);
sl@0: 		NewPivot(pNode,pSibling,aPivot);
sl@0: 		aPromote=iPages->AssignL(pSibling); // non-reclaimable, mustn't lose track of leaves
sl@0: 		iLeafOrg->SetLinkNode(pNode,aPromote); // set up sequencing
sl@0: 		iPages->Unlock(pNode,EPageUpdate);
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		iIndexOrg->InsertSplit(pNode,pSibling,entry,anEntry,aChild,aPivot);
sl@0: 		aPromote=iPages->AssignL(pSibling,EPageReclaimable);
sl@0: 		iPages->Unlock(pNode,EPageDirty);
sl@0: 		}
sl@0: 		// propagate insert up the tree
sl@0: 	if (IsRoot(aPath))
sl@0: 		{ // new root node needed
sl@0: 		NewRootL();
sl@0: 		GotoRoot(aPath);
sl@0: 		}
sl@0: 	else
sl@0: 		aPath.Pop();
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: void TBtree::DeleteAtL(TBtreePath& aPath)
sl@0: //
sl@0: // Delete the current entry on the path
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(aPath.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	TBool leaf=ETrue;
sl@0: 	const MBtreeNodeOrg* nodeOrg=iLeafOrg;
sl@0: 	TAny* pNode=GetNodeL(aPath);
sl@0: 	BeginUpdateL();
sl@0: 	TBtreePivot newPivot;
sl@0: //
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TPageRef node=aPath.Node();
sl@0: 		TInt entry=aPath.Entry();
sl@0: 		if (nodeOrg->Delete(pNode,entry))
sl@0: 			{ // success, no underflow
sl@0: 			if (leaf&&iLeafOrg->LastEntry(pNode)==entry)
sl@0: 				{ // we deleted the last entry so... replace the pivot to ensure invariant
sl@0: 				TPageRef next=iLeafOrg->LinkNode(pNode);
sl@0: 				if (next!=KNullPageRef)
sl@0: 					{ // replace the pivot
sl@0: 					MarkBroken();
sl@0: 					TAny* pSibling=iPages->LockL(next);
sl@0: 					NewPivot(pNode,pSibling,newPivot);
sl@0: 					iPages->Unlock(pSibling);
sl@0: 					PutNode(pNode,leaf);
sl@0: 						// find dividing pivot which we know is there
sl@0: 					do aPath.Pop(); while (aPath.Entry()==LastEntryL(aPath));
sl@0: 					ReplacePivotL(aPath,GetNodeL(aPath),newPivot);
sl@0: 					break;
sl@0: 					}
sl@0: 				}
sl@0: 			PutNode(pNode,leaf);
sl@0: 			break;
sl@0: 			}
sl@0: 		if (IsRoot(aPath))
sl@0: 			{ // the root! If it has entries then we're done
sl@0: 			if (nodeOrg->LastEntry(pNode)>0)
sl@0: 				PutNode(pNode,leaf);
sl@0: 			else
sl@0: 				{
sl@0: 				if (--iHeight!=0) // get child as root
sl@0: 					iRoot=iIndexOrg->ChildNode(pNode,0);
sl@0: 				else // tree is empty
sl@0: 					iRoot=iFirst=KNullPageRef;
sl@0: 				iPages->DeleteL(node);
sl@0: 				}
sl@0: 			break;
sl@0: 			}
sl@0: 		// will definitely affect the index set
sl@0: 		MarkBroken();
sl@0: 			// block has underflowed.. must try to redistribute or concatenate
sl@0: 		aPath.Pop();
sl@0: 		TAny* pParent=GetNodeL(aPath);
sl@0: 		TAny* pSibling;
sl@0: 		entry=aPath.Entry();
sl@0: 		if (entry>0)
sl@0: 			{
sl@0: 			aPath.SetEntry(--entry);
sl@0: 			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,entry)); // on left
sl@0: 			}
sl@0: 		else
sl@0: 			{ // There must be a sibling for non-root nodes!
sl@0: 			__ASSERT_DEBUG(iIndexOrg->LastEntry(pParent)>0,Panic(EBadEntryCount));
sl@0: 			pSibling=pNode;
sl@0: 			node=iIndexOrg->ChildNode(pParent,1); // on right of first child
sl@0: 			pNode=iPages->LockL(node);
sl@0: 			}
sl@0: 			// redistribute between nodes
sl@0: 		if (leaf)
sl@0: 			{
sl@0: 			if (iLeafOrg->Redistribute(pSibling,pNode))
sl@0: 				{
sl@0: 				NewPivot(pSibling,pNode,newPivot);
sl@0: redistributeOK:	PutNode(pSibling,leaf);
sl@0: 				PutNode(pNode,leaf);
sl@0: 				ReplacePivotL(aPath,pParent,newPivot);
sl@0: 				break;
sl@0: 				}
sl@0: 				// failed so concatenate
sl@0: 			iLeafOrg->Concatenate(pSibling,pNode);
sl@0: 			iPages->UpdateL(pSibling); // must change it here and now: link target is being deleted
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			TPtrC8 pivot=iIndexOrg->Entry(pParent,entry);
sl@0: 			if (iIndexOrg->Redistribute(pSibling,pNode,pivot,newPivot))
sl@0: 				goto redistributeOK;
sl@0: 				// failed so concatenate
sl@0: 			iIndexOrg->Concatenate(pSibling,pNode,pivot);
sl@0: 			iPages->Unlock(pSibling,EPageDirty);
sl@0: 			}
sl@0: 		iPages->DeleteL(node);
sl@0: 		leaf=EFalse;
sl@0: 		nodeOrg=iIndexOrg;
sl@0: 		pNode=pParent;
sl@0: 		}
sl@0: 	EndUpdate();
sl@0: 	}
sl@0: 
sl@0: void TBtree::DeleteIndexSetL()
sl@0: //
sl@0: // Destroy the index set, handle broken state too
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(!IsEmpty(),User::Invariant());
sl@0: 	if (IsIntact())
sl@0: 		{
sl@0: 		TBtreePath path;
sl@0: 		GotoRoot(path);
sl@0: 		if (!path.IsLeaf())
sl@0: 			{
sl@0: 			MarkBroken();
sl@0: 			DeleteIndexNodesL(path,ETrue);
sl@0: 			}
sl@0: 		}
sl@0: 	// delete the leading edge
sl@0: 	while (iRoot!=iFirst)
sl@0: 		{
sl@0: 		TPageRef edge=iIndexOrg->ChildNode(iPages->LockL(iRoot),0);
sl@0: 		iPages->DeleteL(iRoot);
sl@0: 		iRoot=edge;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TBtree::DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge)
sl@0: //
sl@0: // Destroy the children of the node in aPath, then destroy the node itself.
sl@0: // do not destroy the sequence set or the leading edge
sl@0: //
sl@0: 	{
sl@0: 	if (aPath.End()>1)
sl@0: 		{	// erase children
sl@0: 		for (TInt ii=LastEntryL(aPath);ii>=0;--ii)
sl@0: 			{
sl@0: 			aPath.Push(ChildNodeL(aPath,ii));
sl@0: 			DeleteIndexNodesL(aPath,aLeadingEdge && ii==0);
sl@0: 			aPath.Pop();
sl@0: 			}
sl@0: 		}
sl@0: 	if (!aLeadingEdge)
sl@0: 		iPages->DeleteL(aPath.Node());
sl@0: 	}
sl@0: 
sl@0: void TBtree::NewTreeL()
sl@0: //
sl@0: // Construct the initial node on empty tree.
sl@0: //
sl@0: 	{
sl@0: 	TAny* first=iPages->AllocL();
sl@0: 	iLeafOrg->Init(first);
sl@0: 	iRoot=iFirst=iPages->AssignL(first); // non-reclaimable, it's a leaf as well as the initial root
sl@0: 	iHeight=1;
sl@0: 	}
sl@0: 
sl@0: void TBtree::NewRootL()
sl@0: //
sl@0: // Create a new root node and set its child to the current root.
sl@0: //
sl@0: 	{
sl@0: 	if (iHeight==KMaxBtreeHeight)
sl@0: 		__LEAVE(KErrOverflow); // tree is max height
sl@0: 	TAny* root=iPages->AllocL();
sl@0: 	iIndexOrg->Init(root);
sl@0: 	iIndexOrg->MakeRoot(root,iRoot);
sl@0: 	iRoot=iPages->AssignL(root); // non-reclaimable, mustn't lose track of successive roots
sl@0: 	++iHeight;
sl@0: 	}
sl@0: 
sl@0: void TBtree::BeginUpdateL()
sl@0: //
sl@0: // Prepare to update the tree. Mark it dirty and ensure locked pages are abandoned on failure.
sl@0: //
sl@0: 	{
sl@0: 	iPages->PushL();
sl@0: 	MarkDirty();
sl@0: 	}
sl@0: 
sl@0: void TBtree::EndUpdate()
sl@0: //
sl@0: // Update complete, clear the broken flag and discard page pool acquisition
sl@0: //
sl@0: 	{
sl@0: 	iPages->Pop();
sl@0: 	MarkIntact();
sl@0: 	}
sl@0: 
sl@0: void TBtree::CheckIntactL() const
sl@0: 	{
sl@0: 	if (IsBroken())
sl@0: 		__LEAVE(KErrCorrupt);
sl@0: 	}
sl@0: 
sl@0: void TBtree::GotoRoot(TBtreePath& aPath) const
sl@0: //
sl@0: // Set the path to the root of the tree.
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));
sl@0: 	aPath.GotoRoot(iHeight,iRoot);
sl@0: 	}
sl@0: 
sl@0: TAny* TBtree::GetNodeL(const TBtreePath& aPath) const
sl@0: 	{
sl@0: 	return iPages->LockL(aPath.Node());
sl@0: 	}
sl@0: 
sl@0: void TBtree::PutNode(TAny* aNode,TBool aLeaf) const
sl@0: 	{
sl@0: 	iPages->Unlock(aNode,aLeaf&&(iStatus&ESecure)?EPageUpdate:EPageDirty);
sl@0: 	}
sl@0: 
sl@0: TInt TBtree::LastEntryL(const TBtreePath& aPath) const
sl@0: 	{
sl@0: //#pragma message( __FILE__ " : 'TBtree::LastEntryL()' should have this information without having to look at the tree" )
sl@0: 	TAny* pp=GetNodeL(aPath);
sl@0: 	TInt cc=NodeOrg(aPath.IsLeaf())->LastEntry(pp);
sl@0: 	iPages->Unlock(pp);
sl@0: 	return cc;
sl@0: 	}
sl@0: 
sl@0: TPageRef TBtree::ChildNodeL(const TBtreePath& aPath) const
sl@0: //
sl@0: // Get current child node.
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	TAny* pp=GetNodeL(aPath);
sl@0: 	TPageRef pg=iIndexOrg->ChildNode(pp,aPath.Entry());
sl@0: 	iPages->Unlock(pp);
sl@0: 	return pg;
sl@0: 	}
sl@0: 
sl@0: TPageRef TBtree::ChildNodeL(TBtreePath& aPath,TInt aChild) const
sl@0: 	{
sl@0: 	aPath.SetEntry(aChild);
sl@0: 	return ChildNodeL(aPath);
sl@0: 	}
sl@0: 
sl@0: TPageRef TBtree::LastChildNodeL(TBtreePath& aPath) const
sl@0: 	{
sl@0: 	__ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
sl@0: 	TAny* pp=GetNodeL(aPath);
sl@0: 	TInt entry=iIndexOrg->LastEntry(pp);
sl@0: 	aPath.SetEntry(entry);
sl@0: 	TPageRef pg=iIndexOrg->ChildNode(pp,entry);
sl@0: 	iPages->Unlock(pp);
sl@0: 	return pg;
sl@0: 	}
sl@0: