// 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_DYNAMIC(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;
	}