--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/store/UBTREE/UB_INL.CPP	Fri Jan 22 11:06:30 2010 +0200
@@ -0,0 +1,408 @@
+// 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:
+// Inline entry node organisations
+// 
+//
+
+#include "UB_STD.H"
+
+EXPORT_C TBtreeInlineLeafOrg::TBtreeInlineLeafOrg()
+	{}
+
+EXPORT_C void TBtreeInlineLeafOrg::SetEntrySize(TInt aSize)
+	{
+	__ASSERT_DEBUG(aSize<=KMaxBtreeKeyLength,Panic(EBadEntrySize));
+	iEntrySize=Align4(aSize);
+	iMaxEntries=(KPoolPageSize-sizeof(SHeader))/iEntrySize;
+	}
+
+EXPORT_C TBool TBtreeInlineLeafOrg::Insert(TAny *aNode,TInt aPos,const TDesC8& anEntry) const
+	{
+	SNode* const pn=Node(aNode);
+	__ASSERT_DEBUG(aPos<=pn->iHead.iCount,Panic(EBadEntryPos));
+	if (pn->iHead.iCount==iMaxEntries)
+		return EFalse;
+	TUint8* pe=Entry(pn,aPos);
+	Mem::Copy(pe+iEntrySize,pe,iEntrySize*(pn->iHead.iCount-aPos));
+	TInt size=anEntry.Size();
+	__ASSERT_ALWAYS(size<=iEntrySize,Panic(EBadEntrySize));
+	Mem::Copy(pe,anEntry.Ptr(),size);
+	++pn->iHead.iCount;
+	return ETrue;
+	}
+
+TAny *TBtreeInlineLeafOrg::DoRedistribute(TAny *aLeftNode,TAny *aRightNode,TInt aInsertPos) const
+//
+// Even out the distibution of entries in LeftNode and RightNode
+// if aInsertPos>=0 we want to insert at this cumulative position so take into account for redistribution
+// If total entries <=iMaxEntries or >iMaxEntries*2 then return 0
+// Otherwise return the node into which insertion should take place
+//
+	{
+	SNode* const pl=Node(aLeftNode);
+	SNode* const pr=Node(aRightNode);
+	TAny *insertNode=aRightNode;
+	TInt lCount=pl->iHead.iCount;
+	TInt rCount=pr->iHead.iCount;
+	TInt total=lCount+rCount;
+	TInt left=(total+1)>>1;
+	if (aInsertPos>=0)
+		{	// call from Insertoverflow
+		__ASSERT_DEBUG(aInsertPos<=total,Panic(EBadEntryPos));
+		if (aInsertPos<left)
+			{
+			insertNode=aLeftNode;
+			--left;
+			}
+		if (total>=iMaxEntries<<1)
+			return 0;	// no space
+		}
+	else
+		{ // from Redistribute
+		if (total<=iMaxEntries)
+			return 0;		// underflow state
+		}
+	pl->iHead.iCount=left;
+	pr->iHead.iCount=total-left;
+	if (lCount>left)
+		{ // move right
+		TInt move=lCount-left;
+		Mem::Copy(Entry(pr,move),pr->iEntries,rCount*iEntrySize);
+		Mem::Copy(pr->iEntries,Entry(pl,left),move*iEntrySize);
+		}
+	else if (lCount<left)
+		{ // move left
+		TInt move=left-lCount;
+		Mem::Copy(Entry(pl,lCount),pr->iEntries,move*iEntrySize);
+		Mem::Copy(pr->iEntries,Entry(pr,move),(rCount-move)*iEntrySize);
+		}
+	return insertNode;
+	}
+
+EXPORT_C TBool TBtreeInlineLeafOrg::InsertOverflow(TAny *aLeftNode,TAny *aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const
+//
+// Redistribute keys in aLeftNode and aRightNode to insert a new entry, return success or failure
+// We know that the insertion node is full (see code for CBplusTree::InsertAtCurrentL)
+// promotion done by manager
+//
+	{
+	__ASSERT_DEBUG(Node(aInsertOnLeft?aLeftNode:aRightNode)->iHead.iCount==iMaxEntries,Panic(EIllegalOverflow));
+	if (!aInsertOnLeft)
+		aPos+=Node(aLeftNode)->iHead.iCount;
+	TAny* iNode=DoRedistribute(aLeftNode,aRightNode,aPos);
+	if (!iNode)
+		return EFalse;
+	if (iNode==aRightNode)
+		aPos-=Node(aLeftNode)->iHead.iCount;
+	return Insert(iNode,aPos,anEntry);
+	}
+
+EXPORT_C void TBtreeInlineLeafOrg::InsertSplit(TAny *aLeftNode,TAny *aRightNode,TInt aPos,const TDesC8& anEntry) const
+//
+// Split contents of left node into left and right and insert entry
+// copy link node from left to right
+//
+	{
+	__ASSERT_DEBUG(Node(aLeftNode)->iHead.iCount==iMaxEntries,Panic(EIllegalSplit));
+	__ASSERT_DEBUG(Node(aRightNode)->iHead.iCount==0,Panic(EIllegalSplit));
+	TAny* iNode=DoRedistribute(aLeftNode,aRightNode,aPos);
+	if (iNode==aRightNode)
+		aPos-=Node(aLeftNode)->iHead.iCount;
+	Insert(iNode,aPos,anEntry);
+	Node(aRightNode)->iHead.iLink=Node(aLeftNode)->iHead.iLink;
+	}
+
+EXPORT_C TBool TBtreeInlineLeafOrg::Delete(TAny *aNode,TInt aPos) const
+//
+// Delete the specified entry from the node
+// Part of the contract is to garauntee that the entry is deleted, even if undeflowed
+//
+	{
+	SNode* const pn=Node(aNode);
+	__ASSERT_DEBUG(aPos<pn->iHead.iCount,Panic(EBadEntryPos));
+
+	--pn->iHead.iCount;
+	TUint8* pe=Entry(pn,aPos);
+	Mem::Copy(pe,pe+iEntrySize,(pn->iHead.iCount-aPos)*iEntrySize);
+	return pn->iHead.iCount>=iMaxEntries>>1;		// underflow criterion
+	}
+
+EXPORT_C TBool TBtreeInlineLeafOrg::Redistribute(TAny *aLeftNode,TAny *aRightNode) const
+//
+// Even out the distibution of entries in LeftNode and RightNode if enough keys
+// leaf nodes do not set the pivot, done by manager
+//
+	{
+	return DoRedistribute(aLeftNode,aRightNode)!=0;
+	}
+
+EXPORT_C void TBtreeInlineLeafOrg::Concatenate(TAny *aLeftNode,const TAny *aRightNode) const
+//
+// Join LeftNode and RightNode together in LeftNode, set link
+// contract says that it will fit
+//
+	{
+	SNode* const pl=Node(aLeftNode);
+	const SNode* const pr=Node(aRightNode);
+	TInt rCount=pr->iHead.iCount;
+	__ASSERT_DEBUG(pl->iHead.iCount+rCount<=iMaxEntries,Panic(ECannotConcatenate));
+	Mem::Copy(Entry(pl,pl->iHead.iCount),pr->iEntries,rCount*iEntrySize);
+	pl->iHead.iCount+=rCount;
+	pl->iHead.iLink=pr->iHead.iLink;
+	}
+
+EXPORT_C TInt TBtreeInlineLeafOrg::LastEntry(const TAny* aNode) const
+	{
+	return Node(aNode)->iHead.iCount;
+	}
+
+EXPORT_C const TAny *TBtreeInlineLeafOrg::EntryPtr(const TAny* aNode,TInt aPos) const
+	{
+	__ASSERT_DEBUG(aPos<Node(aNode)->iHead.iCount,Panic(EBadEntryPos));
+	return Entry(Node(aNode),aPos);
+	}
+
+EXPORT_C TPtrC8 TBtreeInlineLeafOrg::Entry(const TAny* aNode,TInt aPos) const
+	{
+	return TPtrC8((const TUint8*)EntryPtr(aNode,aPos),iEntrySize);
+	}
+
+EXPORT_C TPageRef TBtreeInlineLeafOrg::LinkNode(const TAny* aNode) const
+	{
+	return Node(aNode)->iHead.iLink;
+	}
+
+EXPORT_C void TBtreeInlineLeafOrg::SetLinkNode(TAny* aNode,TPageRef aNextNode) const
+	{
+	Node(aNode)->iHead.iLink=aNextNode;
+	}
+
+
+// class TBtreeInlineIndexOrg
+
+EXPORT_C TBtreeInlineIndexOrg::TBtreeInlineIndexOrg()
+	{}
+
+EXPORT_C void TBtreeInlineIndexOrg::SetEntrySize(TInt aSize)
+	{
+	__ASSERT_DEBUG(aSize<=KMaxBtreeKeyLength,Panic(EBadEntrySize));
+	iEntrySize=_FOFF(SEntry,iKey[Align4(aSize)]);
+	iMaxEntries=(KPoolPageSize-sizeof(SHeader)-sizeof(TPageRef))/iEntrySize;
+	}
+
+EXPORT_C TBool TBtreeInlineIndexOrg::Insert(TAny *aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const
+	{
+	SNode* const pn=Node(aNode);
+	__ASSERT_DEBUG(aPos<=pn->iHead.iCount,Panic(EBadEntryPos));
+	if (pn->iHead.iCount==iMaxEntries)
+		return EFalse;
+	TUint8* pe=Entry(pn,aPos)->iKey;
+	Mem::Copy(pe+iEntrySize,pe,iEntrySize*(pn->iHead.iCount-aPos));
+	TInt size=anEntry.Size();
+	__ASSERT_ALWAYS(size<=KeySize(),Panic(EBadEntrySize));
+	*(TPageRef*)Mem::Copy(pe,anEntry.Ptr(),size)=aChild;
+	++pn->iHead.iCount;
+	return ETrue;
+	}
+
+TBtreeInlineIndexOrg::SNode* TBtreeInlineIndexOrg::DoRedistribute(TAny *aLeftNode,TAny *aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot,TInt aInsertPos) const
+//
+// Even out the distibution of entries in LeftNode and RightNode
+// if aInsertPos>=0 we want to insert at this cumulative position so take into account for redistribution
+// If total entries <=iMaxEntries or >iMaxEntries*2 then return 0
+// Otherwise return the node into which insertion should take place
+// If insertion should be promoted insert position is beyond end of left node, otherwise
+// the new pivot is copied to aNewPivot
+//
+	{
+	SNode* const pl=Node(aLeftNode);
+	SNode* const pr=Node(aRightNode);
+	SNode *insertNode=pr;
+	TInt lCount=pl->iHead.iCount;
+	TInt rCount=pr->iHead.iCount;
+	TInt total=lCount+rCount+1;			// including pivot entry
+	TInt left=total>>1;
+	if (aInsertPos>=0)
+		{	// call from InsertOverflow
+		__ASSERT_DEBUG(aInsertPos<=total,Panic(EBadEntryPos));
+		if (total>iMaxEntries<<1)
+			return NULL;		// no space to insert
+		if (aInsertPos<=left)
+			{
+			if (aInsertPos<left)
+				--left;
+			insertNode=pl;
+			}
+		}
+	else
+		{ // from Redistribute
+		if (total<=iMaxEntries)
+			return NULL;		// underflow state
+		}
+	pl->iHead.iCount=left;
+	pr->iHead.iCount=total-left-1;		// pivot not included
+	TInt pSize=aPivot.Size();
+	__ASSERT_DEBUG(pSize<=KeySize(),Panic(EBadEntrySize));
+	if (lCount>left)
+		{ // move right
+		TInt move=lCount-left;
+		Mem::Copy(Entry(pr,move),pr->iEntries,rCount*iEntrySize+sizeof(TPageRef));
+		TUint8 *pp=Mem::Copy(pr->iEntries,Entry(pl,left+1),(move-1)*iEntrySize+sizeof(TPageRef));
+		Mem::Copy(pp,aPivot.Ptr(),pSize);
+		aNewPivot.Copy(Entry(pl,left)->iKey,KeySize());		// new pivot
+		}
+	else if (lCount<left)
+		{ // move left
+		TInt move=left-lCount-1;
+		TUint8 *pp=Mem::Copy(Entry(pl,lCount)->iKey,aPivot.Ptr(),pSize);
+		Mem::Copy(pp,pr->iEntries,move*iEntrySize+sizeof(TPageRef));
+		aNewPivot.Copy(Entry(pr,move)->iKey,KeySize());
+		Mem::Copy(pr->iEntries,Entry(pr,move+1),(rCount-move-1)*iEntrySize+sizeof(TPageRef));
+		}
+	else
+		{	// should we ever get here?	(lCount==left)
+		aNewPivot=aPivot;
+		}
+	return insertNode;
+	}
+
+EXPORT_C TBool TBtreeInlineIndexOrg::InsertOverflow(TAny *aLeftNode,TAny *aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,
+													 TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const
+//
+// Redistribute keys in aNodePtr and aRight to insert a new entry, return success or failure
+// We know that aNodePtr is full (see code for Insert)
+//
+	{
+	SNode* const pl=Node(aLeftNode);
+	if (!aInsertOnLeft)
+		aPos+=pl->iHead.iCount+1;		// cumulative insertion point
+	SNode* insert=DoRedistribute(aLeftNode,aRightNode,aPivot,aNewPivot,aPos);
+	if (insert==NULL)							// no space
+		return EFalse;
+	TInt lCount=pl->iHead.iCount;
+	if (insert==aRightNode)
+		aPos-=lCount+1;					// insert position in right node
+	else
+		{
+		// check for the special situation [aPos]:[aPos-1]
+		// in which case re-arrange to promote the new entry
+		SNode* pr=Node(aRightNode);
+		if (aPos==lCount && pr->iHead.iCount<lCount)
+			{
+			Insert(pr,0,aNewPivot,Entry(pr,0)->iChild);
+			Entry(pr,0)->iChild=aChild;
+			aNewPivot=anEntry;
+			return ETrue;
+			}
+		}
+	__ASSERT_DEBUG(insert->iHead.iCount<iMaxEntries,User::Invariant());
+	Insert(insert,aPos,anEntry,aChild);
+	return ETrue;
+	}
+
+EXPORT_C void TBtreeInlineIndexOrg::InsertSplit(TAny *aLeftNode,TAny *aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const
+//
+// part of the contract is not to use aPromote before anEntry
+// We know that aNodePtr is full
+// prepare right node and use insert-overflow
+//
+	{
+	__ASSERT_DEBUG(Node(aLeftNode)->iHead.iCount==iMaxEntries,Panic(EIllegalSplit));
+	__ASSERT_DEBUG(Node(aRightNode)->iHead.iCount==0,Panic(EIllegalSplit));
+	SNode* const pl=Node(aLeftNode);
+	SNode* const pr=Node(aRightNode);
+	SEntry *pe=Entry(pl,pl->iHead.iCount);
+	--pl->iHead.iCount;
+	Entry(pr,0)->iChild=pe->iChild;
+	TPtrC8 pivot((TUint8*)pe-KeySize(),KeySize());
+	InsertOverflow(aLeftNode,aRightNode,aPos,ETrue,anEntry,aChild,pivot,aPromote);
+	}
+
+EXPORT_C TBool TBtreeInlineIndexOrg::Update(TAny *aNode,TInt aPos,const TDesC8& anEntry) const
+	{
+	__ASSERT_DEBUG(anEntry.Size()<=KeySize(),Panic(EBadEntrySize));
+	__ASSERT_DEBUG(aPos<Node(aNode)->iHead.iCount,Panic(EBadEntryPos));
+	Mem::Copy(Entry(Node(aNode),aPos)->iKey,anEntry.Ptr(),KeySize());
+	return ETrue;
+	}
+
+EXPORT_C TBool TBtreeInlineIndexOrg::Delete(TAny *aNode,TInt aPos) const
+//
+// Delete the specified key and following child reference from the node
+// Part of the contract is to garauntee that the entry is deleted, even if undeflowed
+//
+	{
+	SNode* const pn=Node(aNode);
+	__ASSERT_DEBUG(aPos<pn->iHead.iCount,Panic(EBadEntryPos));
+
+	--pn->iHead.iCount;
+	TUint8* pe=Entry(pn,aPos)->iKey;
+	Mem::Copy(pe,pe+iEntrySize,(pn->iHead.iCount-aPos)*iEntrySize);
+	return pn->iHead.iCount>=iMaxEntries>>1;		// underflow criterion
+	}
+
+EXPORT_C TBool TBtreeInlineIndexOrg::Redistribute(TAny *aLeftNode,TAny *aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const
+	{
+	return DoRedistribute(aLeftNode,aRightNode,aPivot,aNewPivot)!=NULL;
+	}
+
+EXPORT_C void TBtreeInlineIndexOrg::Concatenate(TAny *aLeftNode,const TAny *aRightNode,const TDesC8& aPivot) const
+//
+// Join LeftNode and RightNode together in LeftNode
+// contract says that it will fit
+//
+	{
+	SNode* const pl=Node(aLeftNode);
+	const SNode* const pr=Node(aRightNode);
+	TInt rCount=pr->iHead.iCount;
+	TInt lCount=pl->iHead.iCount;
+	__ASSERT_DEBUG(lCount+rCount+1<=iMaxEntries,Panic(ECannotConcatenate));
+	TInt pSize=aPivot.Size();
+	__ASSERT_DEBUG(pSize<=KeySize(),Panic(EBadEntrySize));
+	TUint8* pp=Mem::Copy(Entry(pl,lCount)->iKey,aPivot.Ptr(),pSize);
+	Mem::Copy(pp,pr->iEntries,rCount*iEntrySize+sizeof(TPageRef));
+	pl->iHead.iCount+=rCount+1;
+	}
+
+EXPORT_C void TBtreeInlineIndexOrg::MakeRoot(TAny* aNode,TPageRef aChild) const
+	{
+	__ASSERT_DEBUG(Node(aNode)->iHead.iCount==0,Panic(ECannotMakeRoot));
+	Entry(Node(aNode),0)->iChild=aChild;
+	}
+
+EXPORT_C TInt TBtreeInlineIndexOrg::LastEntry(const TAny* aNode) const
+	{
+	return Node(aNode)->iHead.iCount;
+	}
+
+EXPORT_C const TAny *TBtreeInlineIndexOrg::EntryPtr(const TAny* aNode,TInt aPos) const
+	{
+	__ASSERT_DEBUG(aPos<Node(aNode)->iHead.iCount,Panic(EBadEntryPos));
+	return Entry(Node(aNode),aPos)->iKey;
+	}
+
+EXPORT_C TPtrC8 TBtreeInlineIndexOrg::Entry(const TAny* aNode,TInt aPos) const
+	{
+	return TPtrC8((const TUint8*)EntryPtr(aNode,aPos),KeySize());
+	}
+
+EXPORT_C TPageRef TBtreeInlineIndexOrg::ChildNode(const TAny* aNode,TInt aPos) const
+//
+// Entries are always aligned
+// 
+	{
+	__ASSERT_DEBUG(aPos<=Node(aNode)->iHead.iCount,Panic(EBadEntryPos));
+	return Entry(Node(aNode),aPos)->iChild;
+	}
+