diff -r 000000000000 -r bde4ae8d615e os/persistentdata/persistentstorage/store/UBTREE/UB_TREE.CPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/os/persistentdata/persistentstorage/store/UBTREE/UB_TREE.CPP	Fri Jun 15 03:10:57 2012 +0200
@@ -0,0 +1,928 @@
+// 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();
+	if (InsertAtL(aPath,anEntry,KNullPageRef,pivot,promote))
+		InsertAtL(aPath,pivot,promote);
+	EndUpdate();
+	}
+
+void TBtree::NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const
+//
+// Get the key organisation to generate a new pivot between the given leaf nodes.
+//
+	{
+	const TAny* left=iLeafOrg->EntryPtr(aLeftNode,iLeafOrg->LastEntry(aLeftNode)-1);
+	const TAny* right=iLeafOrg->EntryPtr(aRightNode,0);
+	iKey->Between(iKey->Key(left),iKey->Key(right),aPivot);
+	__DEBUG(TInt cleft=iKey->Compare(iKey->Key(left),aPivot.Ptr()));
+	__DEBUG(TInt cright=iKey->Compare(iKey->Key(right),aPivot.Ptr()));
+	__ASSERT_DEBUG((cleft<=0&&cright>0)||(cleft==0&&cright==0),Panic(EIllegalPivot));
+	}
+
+void TBtree::ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot)
+//
+// Replace current pivot entry in aPath with aPivot.
+//
+	{
+	TInt entry=aPath.Entry();
+	// update the pivot in the parent
+	if (iIndexOrg->Update(aNode,entry,aPivot))
+		iPages->Unlock(aNode,EPageDirty);
+	else
+		{	// have to delete the old pivot and insert new one
+		TPageRef child=iIndexOrg->ChildNode(aNode,entry+1);
+		iIndexOrg->Delete(aNode,entry);
+		iPages->Unlock(aNode,EPageDirty);
+		InsertAtL(aPath,aPivot,child);
+		}
+	}
+
+void TBtree::InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild)
+	{
+	TBtreePivot togglePivot;
+	for (;;)
+		{
+		if (!InsertAtL(aPath,aPivot,aChild,togglePivot,aChild))
+			break;
+		if (!InsertAtL(aPath,togglePivot,aChild,aPivot,aChild))
+			break;
+		}
+	}
+
+TBool TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote)
+//
+// Insert entry on this level. Return requirement to propagate with aPromote, aChild and aPath ready.
+//
+	{
+	TBool leaf=aPath.IsLeaf();
+	const MBtreeNodeOrg* nodeOrg=NodeOrg(leaf);
+	TInt entry=aPath.Entry();
+	TAny* pNode=GetNodeL(aPath);
+
+	if (leaf?iLeafOrg->Insert(pNode,entry,anEntry):iIndexOrg->Insert(pNode,entry,anEntry,aChild))
+		{
+		PutNode(pNode,leaf);
+		return EFalse;
+		}
+	// whatever happens next, we will affect the index set
+	MarkBroken();
+	// attempt an overflow insertion
+	if (!IsRoot(aPath))
+		{ // we have an ancestor
+		TPageRef node=aPath.Node(); // save this in case we cannot overflow
+		aPath.Pop();
+		TInt child=aPath.Entry();
+		TAny* pParent=GetNodeL(aPath);
+		TAny* pSibling;
+		if (child<iIndexOrg->LastEntry(pParent))
+			{ // try to overflow to the right
+			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child+1));
+			if (leaf)
+				{
+				if (iLeafOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry))
+					{
+					NewPivot(pNode,pSibling,aPivot);
+overflowOK:			PutNode(pSibling,leaf);
+					PutNode(pNode,leaf);
+					aPath.SetEntry(child);
+					ReplacePivotL(aPath,pParent,aPivot);
+					return EFalse; // completed insertion
+					}
+				}
+			else
+				{
+				const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
+				if (iIndexOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry,aChild,pivot,aPivot))
+					goto overflowOK;
+				}
+			iPages->Unlock(pSibling);
+			}
+		if (--child>=0)
+			{
+			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child));
+			if (leaf)
+				{
+				if (iLeafOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry))
+					{
+					NewPivot(pSibling,pNode,aPivot);
+					goto overflowOK;
+					}
+				}
+			else
+				{
+				const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
+				if (iIndexOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry,aChild,pivot,aPivot))
+					goto overflowOK;
+				}
+			iPages->Unlock(pSibling);
+			}
+			// cannot overflow, so...
+		iPages->Unlock(pParent);
+		aPath.Push(node);
+		}
+
+		// do a split insertion
+	TAny* pSibling=iPages->AllocL();
+	nodeOrg->Init(pSibling);
+	if (leaf)
+		{
+		iLeafOrg->InsertSplit(pNode,pSibling,entry,anEntry);
+		NewPivot(pNode,pSibling,aPivot);
+		aPromote=iPages->AssignL(pSibling); // non-reclaimable, mustn't lose track of leaves
+		iLeafOrg->SetLinkNode(pNode,aPromote); // set up sequencing
+		iPages->Unlock(pNode,EPageUpdate);
+		}
+	else
+		{
+		iIndexOrg->InsertSplit(pNode,pSibling,entry,anEntry,aChild,aPivot);
+		aPromote=iPages->AssignL(pSibling,EPageReclaimable);
+		iPages->Unlock(pNode,EPageDirty);
+		}
+		// propagate insert up the tree
+	if (IsRoot(aPath))
+		{ // new root node needed
+		NewRootL();
+		GotoRoot(aPath);
+		}
+	else
+		aPath.Pop();
+	return ETrue;
+	}
+
+void TBtree::DeleteAtL(TBtreePath& aPath)
+//
+// Delete the current entry on the path
+//
+	{
+	__ASSERT_DEBUG(aPath.IsLeaf(),Panic(EInvalidTreePos));
+	TBool leaf=ETrue;
+	const MBtreeNodeOrg* nodeOrg=iLeafOrg;
+	TAny* pNode=GetNodeL(aPath);
+	BeginUpdateL();
+	TBtreePivot newPivot;
+//
+	for (;;)
+		{
+		TPageRef node=aPath.Node();
+		TInt entry=aPath.Entry();
+		if (nodeOrg->Delete(pNode,entry))
+			{ // success, no underflow
+			if (leaf&&iLeafOrg->LastEntry(pNode)==entry)
+				{ // we deleted the last entry so... replace the pivot to ensure invariant
+				TPageRef next=iLeafOrg->LinkNode(pNode);
+				if (next!=KNullPageRef)
+					{ // replace the pivot
+					MarkBroken();
+					TAny* pSibling=iPages->LockL(next);
+					NewPivot(pNode,pSibling,newPivot);
+					iPages->Unlock(pSibling);
+					PutNode(pNode,leaf);
+						// find dividing pivot which we know is there
+					do aPath.Pop(); while (aPath.Entry()==LastEntryL(aPath));
+					ReplacePivotL(aPath,GetNodeL(aPath),newPivot);
+					break;
+					}
+				}
+			PutNode(pNode,leaf);
+			break;
+			}
+		if (IsRoot(aPath))
+			{ // the root! If it has entries then we're done
+			if (nodeOrg->LastEntry(pNode)>0)
+				PutNode(pNode,leaf);
+			else
+				{
+				if (--iHeight!=0) // get child as root
+					iRoot=iIndexOrg->ChildNode(pNode,0);
+				else // tree is empty
+					iRoot=iFirst=KNullPageRef;
+				iPages->DeleteL(node);
+				}
+			break;
+			}
+		// will definitely affect the index set
+		MarkBroken();
+			// block has underflowed.. must try to redistribute or concatenate
+		aPath.Pop();
+		TAny* pParent=GetNodeL(aPath);
+		TAny* pSibling;
+		entry=aPath.Entry();
+		if (entry>0)
+			{
+			aPath.SetEntry(--entry);
+			pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,entry)); // on left
+			}
+		else
+			{ // There must be a sibling for non-root nodes!
+			__ASSERT_DEBUG(iIndexOrg->LastEntry(pParent)>0,Panic(EBadEntryCount));
+			pSibling=pNode;
+			node=iIndexOrg->ChildNode(pParent,1); // on right of first child
+			pNode=iPages->LockL(node);
+			}
+			// redistribute between nodes
+		if (leaf)
+			{
+			if (iLeafOrg->Redistribute(pSibling,pNode))
+				{
+				NewPivot(pSibling,pNode,newPivot);
+redistributeOK:	PutNode(pSibling,leaf);
+				PutNode(pNode,leaf);
+				ReplacePivotL(aPath,pParent,newPivot);
+				break;
+				}
+				// failed so concatenate
+			iLeafOrg->Concatenate(pSibling,pNode);
+			iPages->UpdateL(pSibling); // must change it here and now: link target is being deleted
+			}
+		else
+			{
+			TPtrC8 pivot=iIndexOrg->Entry(pParent,entry);
+			if (iIndexOrg->Redistribute(pSibling,pNode,pivot,newPivot))
+				goto redistributeOK;
+				// failed so concatenate
+			iIndexOrg->Concatenate(pSibling,pNode,pivot);
+			iPages->Unlock(pSibling,EPageDirty);
+			}
+		iPages->DeleteL(node);
+		leaf=EFalse;
+		nodeOrg=iIndexOrg;
+		pNode=pParent;
+		}
+	EndUpdate();
+	}
+
+void TBtree::DeleteIndexSetL()
+//
+// Destroy the index set, handle broken state too
+//
+	{
+	__ASSERT_DEBUG(!IsEmpty(),User::Invariant());
+	if (IsIntact())
+		{
+		TBtreePath path;
+		GotoRoot(path);
+		if (!path.IsLeaf())
+			{
+			MarkBroken();
+			DeleteIndexNodesL(path,ETrue);
+			}
+		}
+	// delete the leading edge
+	while (iRoot!=iFirst)
+		{
+		TPageRef edge=iIndexOrg->ChildNode(iPages->LockL(iRoot),0);
+		iPages->DeleteL(iRoot);
+		iRoot=edge;
+		}
+	}
+
+void TBtree::DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge)
+//
+// Destroy the children of the node in aPath, then destroy the node itself.
+// do not destroy the sequence set or the leading edge
+//
+	{
+	if (aPath.End()>1)
+		{	// erase children
+		for (TInt ii=LastEntryL(aPath);ii>=0;--ii)
+			{
+			aPath.Push(ChildNodeL(aPath,ii));
+			DeleteIndexNodesL(aPath,aLeadingEdge && ii==0);
+			aPath.Pop();
+			}
+		}
+	if (!aLeadingEdge)
+		iPages->DeleteL(aPath.Node());
+	}
+
+void TBtree::NewTreeL()
+//
+// Construct the initial node on empty tree.
+//
+	{
+	TAny* first=iPages->AllocL();
+	iLeafOrg->Init(first);
+	iRoot=iFirst=iPages->AssignL(first); // non-reclaimable, it's a leaf as well as the initial root
+	iHeight=1;
+	}
+
+void TBtree::NewRootL()
+//
+// Create a new root node and set its child to the current root.
+//
+	{
+	if (iHeight==KMaxBtreeHeight)
+		__LEAVE(KErrOverflow); // tree is max height
+	TAny* root=iPages->AllocL();
+	iIndexOrg->Init(root);
+	iIndexOrg->MakeRoot(root,iRoot);
+	iRoot=iPages->AssignL(root); // non-reclaimable, mustn't lose track of successive roots
+	++iHeight;
+	}
+
+void TBtree::BeginUpdateL()
+//
+// Prepare to update the tree. Mark it dirty and ensure locked pages are abandoned on failure.
+//
+	{
+	iPages->PushL();
+	MarkDirty();
+	}
+
+void TBtree::EndUpdate()
+//
+// Update complete, clear the broken flag and discard page pool acquisition
+//
+	{
+	iPages->Pop();
+	MarkIntact();
+	}
+
+void TBtree::CheckIntactL() const
+	{
+	if (IsBroken())
+		__LEAVE(KErrCorrupt);
+	}
+
+void TBtree::GotoRoot(TBtreePath& aPath) const
+//
+// Set the path to the root of the tree.
+//
+	{
+	__ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));
+	aPath.GotoRoot(iHeight,iRoot);
+	}
+
+TAny* TBtree::GetNodeL(const TBtreePath& aPath) const
+	{
+	return iPages->LockL(aPath.Node());
+	}
+
+void TBtree::PutNode(TAny* aNode,TBool aLeaf) const
+	{
+	iPages->Unlock(aNode,aLeaf&&(iStatus&ESecure)?EPageUpdate:EPageDirty);
+	}
+
+TInt TBtree::LastEntryL(const TBtreePath& aPath) const
+	{
+//#pragma message( __FILE__ " : 'TBtree::LastEntryL()' should have this information without having to look at the tree" )
+	TAny* pp=GetNodeL(aPath);
+	TInt cc=NodeOrg(aPath.IsLeaf())->LastEntry(pp);
+	iPages->Unlock(pp);
+	return cc;
+	}
+
+TPageRef TBtree::ChildNodeL(const TBtreePath& aPath) const
+//
+// Get current child node.
+//
+	{
+	__ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
+	TAny* pp=GetNodeL(aPath);
+	TPageRef pg=iIndexOrg->ChildNode(pp,aPath.Entry());
+	iPages->Unlock(pp);
+	return pg;
+	}
+
+TPageRef TBtree::ChildNodeL(TBtreePath& aPath,TInt aChild) const
+	{
+	aPath.SetEntry(aChild);
+	return ChildNodeL(aPath);
+	}
+
+TPageRef TBtree::LastChildNodeL(TBtreePath& aPath) const
+	{
+	__ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
+	TAny* pp=GetNodeL(aPath);
+	TInt entry=iIndexOrg->LastEntry(pp);
+	aPath.SetEntry(entry);
+	TPageRef pg=iIndexOrg->ChildNode(pp,entry);
+	iPages->Unlock(pp);
+	return pg;
+	}
+