// 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 "UT_STD.H"

// PFS frame-related utilities

TInt SkipLink(TInt anExtent)

//

// anExtent is the end-of-stream, where is the next link pos?

// : add the size of the next frame link, or skip past anchor link

//

	{return anExtent+Min(KSizeFrameDes16,(-anExtent)&KMaskFrameLength16);}

inline TBool SpaceFor(TInt aSpace,TInt anEnd,TInt aLength)

// Check if there is space for at least aLength between links at aSpace and anEnd

	{return SkipLink(aSpace+aLength)<=anEnd;}

TBool Fits(TInt aSpace,TInt anEnd,TInt aLength)

//

// Check that aLength can be relocated into the space

// either an exact fit, or leaves space for a free frame of at least one byte

//

	{

	TInt end=SkipLink(aSpace+aLength);

	return end==anEnd ? ETrue : SpaceFor(end,anEnd,1);

	}

TInt ExtentL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase,TInt aStream)

//

// scan a stream to discover it's extent

//

	{

	__ASSERT_DEBUG(aMark.RelatesTo(aHost),User::Invariant());

	__ASSERT_DEBUG(aBase>=KStreamBeginning,User::Invariant());

	__ASSERT_DEBUG(aStream>=0,User::Invariant());

//

	aMark.SeekL(aHost,RFrame16Buf::Position(aBase,aStream)-KSizeFrameDes16);

	TFrameDes16 des;

	aMark.ReadL(aHost,&des,KSizeFrameDes16);

	TInt frame=des;

	if ((frame&KMaskFrameType16)!=EFrameData16)

		if ((frame&KMaskFrameType16)!=EFrameDescriptive16)

		{

		aMark.Withdraw(aHost);

		__LEAVE(KErrCorrupt);

		}

//

	TInt anchor=((aStream>>KShiftFrameLength16)+1)<<KShiftFrameLength16;

	do

		{

		frame&=KMaskFrameLength16;

		TInt lim=anchor-aStream;

		if (frame!=KFrameOpen16)

			{

			if (frame>=lim)

				{

				aMark.Withdraw(aHost);

				__LEAVE(KErrCorrupt);

				}

			return aStream+frame;

			}

		aMark.SeekL(aHost,EStreamMark,lim);

		aStream=anchor;

		anchor+=KFrameFullLength16;

		aMark.ReadL(aHost,&des,KSizeFrameDes16);

		frame=des;

		} while ((frame&KMaskFrameType16)==EFrameContinuation16);

	return aStream;

	}

// Class TRelocatorInput

// Used to transfer a frame-set within the file

const TInt KRelocatorBufferSize=0xc00;

NONSHARABLE_CLASS(TRelocatorInput) : public MStreamInput

	{

public:

	inline TRelocatorInput(TStreamExchange& aHost,TStreamMark& aMark);

	void OpenL(TFrameType16 aType,TStreamPos aBase,TInt aPos,TInt aLength,TInt aTerminator);

	void CommitL();

private:

	TInt PushL(const TAny* aPtr,TInt aMaxLength);

	TStreamTransfer ReadFromL(MStreamBuf& aSource,TStreamTransfer aTransfer);

	void DesL(TFrameType16 aType);

//

	inline TStreamExchange& Host() const;

	inline TStreamMark& Mark();

private:

	TStreamExchange* iHost;

	TStreamMark* iMark;

	TFrameType16 iType;

	TInt iRemain;

	TInt iAnchor;

	TInt iTerminator;

	};

inline TRelocatorInput::TRelocatorInput(TStreamExchange& aHost,TStreamMark& aMark)

	: iHost(&aHost),iMark(&aMark)

	{}

inline TStreamExchange& TRelocatorInput::Host() const

	{

	__ASSERT_DEBUG(iHost!=NULL,User::Invariant());

	return *iHost;

	}

inline TStreamMark& TRelocatorInput::Mark()

	{

	__ASSERT_DEBUG(iMark!=NULL,User::Invariant());

	return *iMark;

	}

void TRelocatorInput::OpenL(TFrameType16 aType,TStreamPos aBase,TInt aPos,TInt aLength,TInt aTerminator)

//

// initiate the relocated stream

//

	{

	__ASSERT_DEBUG(aType!=EFrameFree16,User::Invariant());

	__ASSERT_DEBUG(aBase>=KStreamBeginning,User::Invariant());

	__ASSERT_DEBUG(aPos>=0,User::Invariant());

	__ASSERT_DEBUG(aLength>0,User::Invariant());

//

	iType=aType;

	iRemain=aLength;

	iTerminator=aTerminator;

	iAnchor=KFrameFullLength16-(aPos&KMaskFrameLength16);

	Mark().SeekL(Host(),RFrame16Buf::Position(aBase,aPos)-KSizeFrameDes16);

	}

void TRelocatorInput::CommitL()

//

// complete the relocated stream

//

	{

	__ASSERT_DEBUG(iRemain==0,User::Invariant());

	__ASSERT_DEBUG(iAnchor>=0,User::Invariant());

//

	if (iTerminator<0)

		return;

//

	TFrameDes16 des[2];

	des[1]=TFrameDes16(iTerminator);

	TInt l=KSizeFrameDes16;

	if (iAnchor<=KSizeFrameDes16)

		l+=iAnchor;

	Mark().WriteL(Host(),(const TUint8*)&des[2]-l,l);

	}

TInt TRelocatorInput::PushL(const TAny*,TInt)

//

// use a passive write through to the host

//

	{

	return 0;

	}

void TRelocatorInput::DesL(TFrameType16 aType)

//

// Write the next frame descriptor

//

	{

	__ASSERT_DEBUG(aType!=EFrameFree16,User::Invariant());

	TFrameDes16 des=TFrameDes16(iRemain<iAnchor ? aType+iRemain : aType+KFrameOpen16);

	Mark().WriteL(Host(),&des,KSizeFrameDes16);

	}

TStreamTransfer TRelocatorInput::ReadFromL(MStreamBuf& aSource,TStreamTransfer aTransfer)

//

// bulk of the transfer happens here

//

	{

	__ASSERT_DEBUG(!(aTransfer>iRemain),User::Invariant());

	do

		{

		TUint8 buf[KRelocatorBufferSize];

		TInt len=aSource.ReadL(buf,aTransfer[sizeof(buf)]);

		if (len==0)

			break;

		aTransfer-=len;

		const TUint8* p=buf;

		if (iType!=EFrameFree16)

			{

			DesL(iType);

			iType=EFrameFree16;

			}

		for (;;)

			{

			if (iAnchor==0)

				{	// write next anchor

				iAnchor=KFrameFullLength16;

				DesL(EFrameContinuation16);

				}

			TInt frame=Min(len,iAnchor);

			Mark().WriteL(Host(),p,frame);

			iAnchor-=frame;

			iRemain-=frame;

			len-=frame;

			if (len==0)

				break;

			p+=frame;

			}

		} while (aTransfer>0);

	return aTransfer;

	}

// Class TPermanentStoreRelocator

// used to locate streams for relocation in limited memory

class TPermanentStoreRelocator

	{

#if defined(__SMALL_BUNDLE)

	enum {EBundleSize=8-1};

#else

	enum {EBundleSize=64-1};

#endif

public:

	typedef CPermanentStoreCollector::TEntry TEntry;

public:

	void Reset();

	TBool Reset(TInt aPos);

	TInt FillL(CPermanentStoreToc& aToc);

	void EvaluateLengthsL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase);

//

	TBool FindFit(TInt aSpace,TInt anEnd);

	inline const TEntry* Current() const;

	void Relocated(const TEntry* anEntry);

//

	TInt Extent(TInt aStream) const;

	inline TInt MinLength() const;

private:

	static void Push(TEntry* aHeap,TEntry* aHole,const TEntry& aValue);

	static TEntry PopPush(TEntry* aHeap,TEntry* anEnd,const TEntry& aValue);

private:

	TEntry* iNext;

	const TEntry* iFinish;

	TInt iMore;

	TInt iPos;

	TInt iCurrentMin,iMinLength;

	TEntry iTable[EBundleSize];

	};

inline const TPermanentStoreRelocator::TEntry* TPermanentStoreRelocator::Current() const

	{__ASSERT_DEBUG(iNext>=iTable&&iNext<iFinish,User::Invariant());return iNext;}

inline TInt TPermanentStoreRelocator::MinLength() const

	{return iMinLength;}

void TPermanentStoreRelocator::Reset()

//

// reset the cached length values

//

	{

	iPos=0;

	iMinLength=1;

	}

TBool TPermanentStoreRelocator::Reset(TInt aPos)

//

// reset the iterator for a new scan from aPos

//

	{

	__ASSERT_DEBUG(aPos>=0,User::Invariant());

//

	iCurrentMin=KMaxTInt;

	TEntry* e=iTable;

	if (aPos>=iPos || e==iFinish || aPos<e->entry.ref)

		{	// rescan required

		iFinish=iNext=NULL;

		iMore=-1;

		iPos=aPos;

		return EFalse;

		}

// can use current data

	for (;e->entry.ref!=aPos;++e)

		{

		__ASSERT_DEBUG(e->entry.ref<aPos,User::Invariant());

		__ASSERT_DEBUG(e<iFinish,User::Invariant());

		}

	__ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());

	iNext=e;

	return ETrue;

	}

TBool TPermanentStoreRelocator::FillL(CPermanentStoreToc& aToc)

//

// Fill the table with the next bundle of stream offsets

// return if there are more available

//

	{

	__ASSERT_DEBUG(iNext==iFinish,User::Invariant());

	if (!iMore)

		return EFalse;

//

	__ASSERT_DEBUG(iPos>=0,User::Invariant());

//

	RPermanentStoreTocIter iter(aToc);

	CleanupReleasePushL(iter);

	TInt streams=0;

	TInt from=iPos;

	TEntry* table=iTable;

	TEntry* last=table;

	TEntry* end=table+EBundleSize;

	TEntry entry;

	__DEBUG(entry.len=-1);

	for (iter.ResetL();iter.NextL(entry.entry);)

		{

		if (entry.entry.handle<0)

			continue;

		TInt off=entry.entry.ref;

		if (off<from)

			continue;

		++streams;

		if (last<end)

			Push(table,last++,entry);	// push onto the bottom

		else if (off<table->entry.ref)

			PopPush(table,last,entry);	// replace item in heap

		}

	CleanupStack::PopAndDestroy();

	iMore=streams+table-last;

	if (streams)

		iPos=table->entry.ref+1;		// largest offset in table

	iNext=table;

	iFinish=last;

	while (--last>table)

		*last=PopPush(table,last,*last);

	return streams>0;

	}

void TPermanentStoreRelocator::Push(TEntry* aHeap,TEntry* aHole,const TEntry& aValue)

//

// push aValue onto the heap (which will grow)

//

	{

	TInt ix=aHole+1-aHeap;

	while (aHole>aHeap)

		{

		TInt link=ix-(ix>>1);

		ix-=link;

		TEntry* parent=aHole-link;

		if (parent->entry.ref>=aValue.entry.ref)

			break;

		*aHole=*parent;

		aHole=parent;

		}

	*aHole=aValue;

	}

TPermanentStoreRelocator::TEntry TPermanentStoreRelocator::PopPush(TEntry* aHeap,TEntry* anEnd,const TEntry& aValue)

//

// pop the top and push aValue

//

	{

	TEntry top=*aHeap;

	TEntry* hole=aHeap;

	--anEnd;

	TInt ix=1;

	for (;;)

		{

		TEntry* child=hole+ix;

		ix<<=1;

		if (child>anEnd)

			break;

		if (child<anEnd && (child+1)->entry.ref>child->entry.ref)

			{

			++ix;

			++child;

			}

		if (child->entry.ref<=aValue.entry.ref)

			break;

		*hole=*child;

		hole=child;

		}

	*hole=aValue;

	return top;

	}

void TPermanentStoreRelocator::EvaluateLengthsL(TStreamExchange& aHost,TStreamMark& aMark,TStreamPos aBase)

//

// Evaluate the lengths for all the entries in the table

//

	{

	const TEntry* end=iFinish;

	for (TEntry* e=iTable;e<end;++e)

		{

		__ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());

		__ASSERT_DEBUG(e->entry.ref>=0,User::Invariant());

		__ASSERT_DEBUG(e->len==-1,User::Invariant());

		TInt pos=e->entry.ref;

		e->len=ExtentL(aHost,aMark,aBase,pos)-pos;

		}

	}

TBool TPermanentStoreRelocator::FindFit(TInt aSpace,TInt anEnd)

//

// Find a stream which will fit into the space

//

	{

	const TEntry* end=iFinish;

	TEntry* e;

	for (e=iNext;e<end;++e)

		{

		if (e->entry.handle<0)

			continue;

		TInt len=e->len;

		__ASSERT_DEBUG(len>0,User::Invariant());

		if (Fits(aSpace,anEnd,len))

			{

			iNext=e;

			return ETrue;

			}

		// len has been left behind, check for minimum

		if (len<iCurrentMin)

			iCurrentMin=len;

		}

// if no more data, use current min as cached value

	if (iMore==0)

		iMinLength=iCurrentMin;

	iNext=e;

	return EFalse;

	}

void TPermanentStoreRelocator::Relocated(const TEntry* anEntry)

//

// Relocation has been successful

//

	{

	__ASSERT_DEBUG(anEntry==iNext,User::Invariant());

	TEntry* e=CONST_CAST(TEntry*,anEntry);

	e->entry.handle=-1;

	iNext=e+1;

	}

TInt TPermanentStoreRelocator::Extent(TInt aStream) const

//

// Return this stream extent if we know it

//

	{

	const TEntry* e=iTable;

	if (aStream>=iPos || e==iFinish || aStream<e->entry.ref)

		return -1;	// we don't know it

	for (;e->entry.ref!=aStream;++e)

		{

		__ASSERT_DEBUG(e->entry.ref<aStream,User::Invariant());

		__ASSERT_DEBUG(e<iFinish,User::Invariant());

		}

	__ASSERT_DEBUG(e->entry.handle>=0,User::Invariant());

	__ASSERT_DEBUG(e->len>=0,User::Invariant());

	return aStream+e->len;

	}

// class TPermanentStoreStreamIter

void TPermanentStoreStreamIter::Reset()

//

// reset the iterator for a new scan

//

	{

	iNext=NULL;

	iFinish=NULL;

	iMore=-1;

	iPos=0;

	}

TInt TPermanentStoreStreamIter::FillL(CPermanentStoreToc& aToc)

//

// Fill the table with the next bundle of stream offsets

// return the total streams left to iterate

//

	{

	__ASSERT_DEBUG(iNext==iFinish,User::Invariant());

	if (!iMore)

		return 0;

//

	__ASSERT_DEBUG(iPos>=0,User::Invariant());

//

	RPermanentStoreTocIter iter(aToc);

	CleanupReleasePushL(iter);

	TInt streams=0;

	TInt from=iPos;

	TInt* heap=iTable;

	TInt* last=heap;

	TInt* end=heap+EBundleSize;

	RPermanentStoreTocIter::TEntry entry;

	for (iter.ResetL();iter.NextL(entry);)

		{

		if (entry.handle<0)

			continue;

		TInt off=entry.ref;

		if (off<from)

			continue;

		++streams;

		if (last<end)

			Push(heap,last++,off);	// push onto the bottom

		else if (off<*heap)

			PopPush(heap,last,off);	// replace item in heap

		}

	CleanupStack::PopAndDestroy();

	iMore=streams+(heap-last);

	iPos=*heap+1;		// largest offset in table

	iNext=heap;

	iFinish=last;

	while (--last>heap)

		*last=PopPush(heap,last,*last);

	return streams;

	}