diff -r 000000000000 -r bde4ae8d615e os/persistentdata/persistentstorage/store/USTOR/UT_COLL.CPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/os/persistentdata/persistentstorage/store/USTOR/UT_COLL.CPP	Fri Jun 15 03:10:57 2012 +0200
@@ -0,0 +1,1155 @@
+// 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;
+	}
+
+TInt TPermanentStoreStreamIter::Next()
+//
+// return the next offset, or <0 if the table is empty
+//
+	{
+	__ASSERT_DEBUG(iMore>=0,User::Invariant());
+//
+	while (iNext<iFinish)
+		{
+		TInt off=*iNext++;
+		if (off>=0)
+			return off;
+		}
+	return -1;
+	}
+
+void TPermanentStoreStreamIter::Relocated(TInt aStream)
+//
+// aStream has been relocated, mark the table
+//
+	{
+	__ASSERT_DEBUG(iMore>=0,User::Invariant());
+//
+	if (aStream>=iPos)
+		return;
+	TInt* p=iNext;
+	for (;;)
+		{
+		if (p==iFinish)
+			return;
+		if (*p>=0)
+			break;
+		++p;
+		}
+	if (aStream<*p)
+		return;
+//
+	for (;*p!=aStream;++p)
+		{
+		__ASSERT_DEBUG(p<iFinish,User::Invariant());
+		__ASSERT_DEBUG(*p<aStream,User::Invariant());
+		}
+	if (p==iNext)
+		iNext=p+1;
+	else
+		*p=-1;
+	}
+
+void TPermanentStoreStreamIter::Push(TInt* aHeap,TInt* aHole,TInt aValue)
+//
+// push aValue onto the heap (which will grow)
+//
+	{
+	TInt ix=aHole+1-aHeap;
+	while (aHole>aHeap)
+		{
+		TInt link=ix-(ix>>1);
+		ix-=link;
+		TInt* parent=aHole-link;
+		if (*parent>=aValue)
+			break;
+		*aHole=*parent;
+		aHole=parent;
+		}
+	*aHole=aValue;
+	}
+
+TInt TPermanentStoreStreamIter::PopPush(TInt* aHeap,TInt* anEnd,TInt aValue)
+//
+// pop the top and push aValue
+//
+	{
+	TInt top=*aHeap;
+	TInt* hole=aHeap;
+	--anEnd;
+	TInt ix=1;
+	for (;;)
+		{
+		TInt* child=hole+ix;
+		ix<<=1;
+		if (child>anEnd)
+			break;
+		if (child<anEnd && *(child+1)>*child)
+			{
+			++ix;
+			++child;
+			}
+		if (*child<=aValue)
+			break;
+		*hole=*child;
+		hole=child;
+		}
+	*hole=aValue;
+	return top;
+	}
+
+
+
+// Class CPermanentStoreCollector
+
+CPermanentStoreCollector* CPermanentStoreCollector::CompactorL(CPermanentStoreCoord& aCoord)
+	{
+	CPermanentStoreCollector* self=ReclaimerL(aCoord);
+	CleanupStack::PushL(self);
+	self->iReloc=new(ELeave) TPermanentStoreRelocator;
+	CleanupStack::Pop();
+	return self;
+	}
+
+CPermanentStoreCollector* CPermanentStoreCollector::ReclaimerL(CPermanentStoreCoord& aCoord)
+	{
+	return new(ELeave) CPermanentStoreCollector(aCoord);
+	}
+
+CPermanentStoreCollector::CPermanentStoreCollector(CPermanentStoreCoord& aCoord)
+	: iCoord(&aCoord),iHost(&aCoord.Host()),iStreams(EGranularity,_FOFF(TEntry,entry.ref))
+	{
+	Coord().Inc();
+	}
+
+CPermanentStoreCollector::~CPermanentStoreCollector()
+	{
+	delete iReloc;
+	iStreams.Close();
+	iMark.Withdraw(Host());
+	Coord().Dec();
+	}
+
+void CPermanentStoreCollector::DoRelease()
+	{
+	delete this;
+	}
+
+void CPermanentStoreCollector::DoResetL(TInt& aCount)
+	{
+	iMark.Withdraw(Host());
+	iMark=KStreamBeginning;
+	iCoordGen=Coord().Generation();
+	iFree=0;
+	TRAPD(r, aCount = FastResetL());
+	if (r == KErrNone)
+		return;
+	if (r != KErrNoMemory)
+		User::Leave(r);
+// fall back to fixed memory solution
+	iState=EGetFree;
+	if (Compacting())
+		iReloc->Reset();
+	iIter.Reset();
+	TInt streams=iIter.FillL(Coord().ConsolidateL());
+	aCount=streams+1;
+	}
+
+const TInt KMaxStepEffort=9;
+
+void CPermanentStoreCollector::DoNextL(TInt& aStep,TInt& aTotal)
+//
+// Dispatch the next set of operations
+//
+	{
+	if (aStep<=0)
+		{
+		__DEBUG(Panic(TStorePanic()));
+		return;
+		}
+//
+	if (iCoordGen!=Coord().Generation() || Coord().TableL().IsVirtual())
+		__LEAVE(KErrNotReady);
+//
+	TInt effort=0;
+	do
+		{
+		switch (iState)
+			{
+		default:
+			__DEBUG(User::Invariant());
+		case EGetFree:
+			effort+=GetFreeL();
+			break;
+		case ESkip:
+			effort+=SkipL(aTotal);
+			--aStep;
+			break;
+		case EInitRelocator:
+			effort+=InitRelocator();
+			break;
+		case EFillRelocator:
+			effort+=FillRelocatorL();
+			break;
+		case EEvalRelocator:
+			effort+=EvalRelocatorL();
+			break;
+		case EScanRelocator:
+			effort+=ScanRelocator();
+			break;
+		case ERelocateStream:
+			effort+=RelocateStreamL();
+			--aStep;
+			break;
+		case ERelocateToc:
+			RelocateTocL(aTotal);
+			iStreams.Close();
+			__ASSERT_DEBUG(aStep==1,User::Invariant());
+			aStep=0;
+			return;
+		case EFastSort:
+			FastSort();
+			--aStep;
+			return;
+		case EFastExtent:
+			FastExtentL(aTotal);
+			--aStep;
+			return;
+		case EFastRelocate:
+			FastRelocateL(aTotal);
+			--aStep;
+			return;
+			}
+		} while(effort<KMaxStepEffort);
+	__ASSERT_DEBUG(aStep>=1,User::Invariant());
+	}
+
+TInt CPermanentStoreCollector::GetFreeL()
+//
+// find the end of the free space
+//
+	{
+	__ASSERT_DEBUG(iState==EGetFree,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0,User::Invariant());
+//
+	TInt effort=0;
+	iEnd=iIter.Next();
+	if (iEnd<0)
+		{
+		if (iIter.FillL(Coord().ConsolidateL())==0)
+			{
+			iState=ERelocateToc;	// no more streams
+			return effort;
+			}
+		effort=KMaxStepEffort;
+		iEnd=iIter.Next();
+		__ASSERT_DEBUG(iEnd>=0,User::Invariant());
+		}
+	iState=Compacting() && HaveEnoughSpace() ? EInitRelocator : ESkip;
+	return effort;
+	}
+
+TInt CPermanentStoreCollector::SkipL(TInt& aTotal)
+//
+// Find some free space, iEnd was the last stream extracted from concat
+//
+	{
+	__ASSERT_DEBUG(iState==ESkip,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0&&iFree<=iEnd,User::Invariant());
+//
+	aTotal+=iEnd-iFree;
+	iFree=SkipLink(ExtentL(iEnd));
+	iState=EGetFree;
+	return 1;		// effort
+	}
+
+TInt CPermanentStoreCollector::InitRelocator()
+//
+// initialise the relocator for the free space
+//
+	{
+	__ASSERT_DEBUG(iState==EInitRelocator,User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	iState=iReloc->Reset(iEnd) ? EScanRelocator : EFillRelocator;
+	return 0;		// no real work at all
+	}
+
+TInt CPermanentStoreCollector::FillRelocatorL()
+//
+// Fill the relocator table
+//
+	{
+	__ASSERT_DEBUG(iState==EFillRelocator,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	TBool more=iReloc->FillL(Coord().ConsolidateL());
+	iState=more ? EEvalRelocator : ESkip;
+	return more ? KMaxStepEffort : 0;
+	}
+
+TInt CPermanentStoreCollector::EvalRelocatorL()
+//
+// evaluate the extents for the relocator
+//
+	{
+	__ASSERT_DEBUG(iState==EEvalRelocator,User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	iReloc->EvaluateLengthsL(Host(),iMark,Coord().Base());
+	iState=EScanRelocator;
+	return KMaxStepEffort;
+	}
+
+TInt CPermanentStoreCollector::ScanRelocator()
+//
+// find a stream that will fit
+//
+	{
+	__ASSERT_DEBUG(iState==EScanRelocator,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	iState=iReloc->FindFit(iFree,iEnd) ? ERelocateStream : EFillRelocator;
+	return 0;
+	}
+
+TInt CPermanentStoreCollector::RelocateStreamL()
+//
+// find and relocate a stream
+//
+	{
+	__ASSERT_DEBUG(iState==ERelocateStream,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	const TEntry& e = *iReloc->Current();
+	RelocateStreamL(e, iEnd);
+	iState=e.entry.ref==iEnd ? EGetFree : HaveEnoughSpace() ? EScanRelocator : ESkip;
+	iIter.Relocated(e.entry.ref);
+	iReloc->Relocated(&e);
+	return KMaxStepEffort;
+	}
+
+void CPermanentStoreCollector::RelocateTocL(TInt& aTotal)
+//
+// relocate the toc - return any wasted bytes
+//
+	{
+	__ASSERT_DEBUG(iState==ERelocateToc,User::Invariant());
+	__ASSERT_DEBUG(iFree>=0,User::Invariant());
+//
+	TInt toc=Coord().iToc+KOffsetTocHeader;
+	if (toc<0)
+		return;
+//
+	if (Compacting())
+		{
+		TInt len=Coord().TableL().Extent()-toc;
+		if (Fits(iFree,toc,len))
+			{
+			RelocateL(toc, len, EFrameDescriptive16, toc);
+			Coord().MoveL(iFree-KOffsetTocHeader,iFree + len);
+			return;
+			}
+		}
+	// don't move it
+	aTotal += toc-iFree;
+	}
+
+TBool CPermanentStoreCollector::HaveEnoughSpace() const
+	{
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	return SpaceFor(iFree,iEnd,iReloc->MinLength());
+	}
+
+TInt CPermanentStoreCollector::ExtentL(TInt aStream)
+//
+// Check if the relocator knows before scanning the file
+//
+	{
+	if (Compacting())
+		{
+		TInt ext=iReloc->Extent(aStream);
+		if (ext>=0)
+			return ext;
+		}
+	return ::ExtentL(Host(),iMark,Coord().Base(),aStream);
+	}
+
+/* relocate a stream into [iFree, aExtent)
+
+During compaction, for each string which is to be moved from position A1 to B1, the sequence of operations is:
+
+1.  Copy stream S1 content from position A1 to position B1 . The copy never overlaps so the old stream content is still good at this point.
+2.  Optionally rewrite the file header to state that stream S1 is being relocated to B1 (more about the ‘optional below’)
+3.  Overwrite the TOC entry for S1 to state that the content is now at B1
+
+This function completes 3 steps above and will be called again and again for every string to be moved.
+
+In terms of data consistency, first consider the impact of a mid-write failure in any of these steps (when write caching is disabled):
+1.  If step #1 only partially completes the file is good as the original content is intact and the new content was being written to otherwise free space
+2.  If step #2 only partially completes the header CRC fails and only the TOC reference is considered valid (so the corrupt stream relocation record is ignored).
+		 The TOC will be good because it is being overwritten with the same content.
+3.  If step #3 only partially completes the entry for S1 in the TOC is corrupt, BUT the relocation record for S1 in the file header is good and will
+ override the entry in the TOC.
+
+In all cases the file is never broken by a crash in mid-compaction.
+
+Step #2 is optional – there are many cases when step #3 cannot fail ‘halfway through’ because the underlying media makes atomic block/page based
+updates and the write does not cross any block boundaries. In STORE we assume that blocks cannot be smaller than 512 bytes and any flash based
+media provides the required behavior. Thus 99% of the step #2 writes are eliminated.
+
+Note that sequencing MATTERS even for just one stream. If the TOC update hits the disk before the content is moved, and then the device fails
+we will have a broken file: S1 points to B1 which contains garbage.  Equally in the case where step #2 is required (i.e. when step #3 straddles
+a block boundary and could fail) step 2 has to go before the step 3. Otherwise write #3 could go to disk and fail part way through before write #2 
+and leave the TOC corrupt with no recovery in the file header.
+
+Consider the case that step 2 was omitted, so the Store relies on step 3 being completed in order to know that S1 is in location B1;
+and that no flush is done after step 3. In step 4 the stream S2 is moved – at this point the old space for stream S1 at A1 is considered empty
+– and suppose it gets moved from A2 to B2 where B2 overlaps/overwrites A1. If the writes in step 3 and step 4 are re-ordered and the step 3
+write does not happen – then the TOC will claim that S1 is still at A1 but this location in the file has been overwritten with data from S2.
+A corrupted file.
+
+Based on the knowledge above, it is strongly recommended to set EFileWriteDirectIO bit when opening the file so that the order is maintained
+when writing to the file.
+*/
+void CPermanentStoreCollector::RelocateStreamL(const CPermanentStoreCollector::TEntry& aReloc, TInt aExtent)
+	{
+	if (Coord().Accessed())	// must have exclusive access to relocate the stream
+		__LEAVE(KErrInUse);
+//
+	TInt end=RelocateL(aReloc.entry.ref,aReloc.len,aReloc.entry.handle == KHandleTocBase ? EFrameDescriptive16 : EFrameData16, aExtent);
+	//Step 1, 4,....
+	Coord().RelocateL(aReloc.entry.handle, iFree);
+	// Step 2 & 3, 5 & 6,...
+	iCoordGen=Coord().Generation();	// changed by relocation
+	iFree = end;
+	}
+
+TInt CPermanentStoreCollector::RelocateL(TInt aStream, TInt aLength, TFrameType16 aType, TInt aExtent)
+//
+// Relocate a data stream into [iFree, aExtent)
+//
+	{
+	__ASSERT_DEBUG(Fits(iFree,aExtent,aLength),User::Invariant());
+	__ASSERT_DEBUG(Compacting(),User::Invariant());
+//
+	TInt end=SkipLink(iFree+aLength);
+	TInt terminator;
+	if (end==aExtent)
+		terminator=-1;
+	else
+		{
+		TInt anchor=((end>>KShiftFrameLength16)+1)<<KShiftFrameLength16;
+		if (aExtent<anchor)
+			{
+			__ASSERT_DEBUG(aExtent-KSizeFrameDes16-end>0,User::Invariant());
+			terminator=EFrameFree16+(aExtent-KSizeFrameDes16-end);
+			}
+		else
+			terminator=EFrameFree16+KFrameOpen16;
+		}
+//
+	RFrame16Buf from(Coord().Base());
+	from.Set(Host(),aStream,aStream+aLength,MStreamBuf::ERead);
+	from.PushL();
+	TRelocatorInput input(Host(),iMark);
+	input.OpenL(aType,Coord().Base(),iFree,aLength,terminator);
+	from.ReadL(input,aLength);
+	input.CommitL();
+	CleanupStack::PopAndDestroy();
+//
+	return end;
+	}
+
+
+TInt CPermanentStoreCollector::FastResetL()
+//
+// Fill the table with the streams with data in the store
+//
+	{
+	iStreams.Reset();
+//
+	CleanupClosePushL(iStreams);
+	RPermanentStoreTocIter iter(Coord().ConsolidateL());
+	CleanupReleasePushL(iter);
+	TEntry entry;
+	for (iter.ResetL();iter.NextL(entry.entry);)
+		{
+		if (entry.entry.handle<0)
+			continue;
+		if (entry.entry.ref<0)
+			continue;
+		User::LeaveIfError(iStreams.Append(entry));
+		}
+	CleanupStack::PopAndDestroy(&iter);
+	CleanupStack::Pop(&iStreams);
+//
+	// always have final (toc) step
+	iState = ERelocateToc;
+	TInt streams = iStreams.Count();
+	if (streams == 0)
+		return 1;
+	iState = EFastSort;
+	// ordering is 1 step and evaluating the extents is several more
+	TInt count = 2 + (streams + EExtentStep - 1)/EExtentStep;
+	if (Compacting())
+		count += streams;
+	return count;
+	}
+
+void CPermanentStoreCollector::FastSort()
+	{
+	__ASSERT_DEBUG(iState == EFastSort, User::Invariant());
+//
+	iStreams.SortSigned();
+	iNext = &iStreams[0];
+	iLast = iNext + iStreams.Count();
+	iState = EFastExtent;
+	}
+
+void CPermanentStoreCollector::FastExtentL(TInt& aTotal)
+//
+// Evaluate the lengths for all the streams
+// if reclaiming, update aTotal with free space skipped
+// return false until we've done the last one
+//
+	{
+	__ASSERT_DEBUG(iState == EFastExtent, User::Invariant());
+	__ASSERT_DEBUG(iNext != iLast, User::Invariant());
+
+	TEntry* e = iNext;
+	const TEntry* end = Min(iLast, e + EExtentStep);
+	do
+		{
+		TInt ref = e->entry.ref;
+		__ASSERT_DEBUG(TUint(iFree)<=TUint(ref),User::Invariant());
+		TInt ext = ::ExtentL(Host(), iMark, Coord().Base(), ref);
+		e->len = ext - ref;
+		if (!Compacting())
+			aTotal += ref - iFree;
+		iFree = SkipLink(ext);
+		} while (++e < end);
+	iNext = e;
+//
+	if (e == iLast)
+		{
+		if (!Compacting())
+			iState = ERelocateToc;
+		else
+			{
+			iNext = &iStreams[0];
+			iFree = 0;
+			iState = EFastRelocate;
+			}
+		}
+	}
+
+CPermanentStoreCollector::TEntry* CPermanentStoreCollector::BestFit(TInt aPos, TInt aExt, TEntry* aFirst, TEntry* aLast)
+//
+// [aPos, aExt) is a hole - find the best fit to fill it in [aFirst, aLast)
+//
+	{
+	__ASSERT_DEBUG(aPos <= aExt, User::Invariant());
+	TEntry* r = 0;
+	if (aPos == aExt)
+		return r;
+//
+	if ((aExt & KMaskFrameLength16) != 0)
+		aExt -= KSizeFrameDes16;
+	const TInt mingap = Min(KSizeFrameDes16 + 1, (aExt & KMaskFrameLength16));
+	TInt rlen = 0;
+	TInt avail = aExt - aPos;
+	do
+		{
+		TInt len;
+		for (;;)
+			{
+			len = (--aLast)->len;
+			if (len > rlen)
+				break;
+			if (aFirst == aLast)
+				return r;
+			}
+		TInt d = avail - len;
+		if (d < 0)
+			continue;
+		if (d == 0)			// exact fit
+			return aLast;
+		if (d < mingap)
+			continue;
+		r = aLast;
+		rlen = len;
+		} while (aFirst != aLast);
+	return r;
+	}
+
+void CPermanentStoreCollector::FastRelocateL(TInt& aTotal)
+//
+// Look for a stream to move. Either move a stream or fail to find a fit before returning
+// fill holes from the front of the file with the biggest block that will fit (inverted current algorithm)
+// return true when the last hole has been looked at
+//
+	{
+	__ASSERT_DEBUG(iState == EFastRelocate, User::Invariant());
+	__ASSERT_DEBUG(iNext != iLast, User::Invariant());
+
+	TEntry* e = iNext;
+	TInt ext = e->entry.ref;
+	__ASSERT_DEBUG(ext >= 0, User::Invariant());
+
+	TEntry* r = BestFit(iFree, ext, e, iLast);
+	if (!r)
+		{
+		// Nothing fits, accumulate free space
+		aTotal += ext - iFree;
+		iFree = SkipLink(ext + e->len);
+		}
+	else
+		{
+		// lets move it
+		RelocateStreamL(*r, ext);
+		if (r != e)
+			{
+			// relocated a stream other than the one terminating the current hole
+			// mark it at moved
+			r->entry.ref = -1;
+			r->len = -1;
+			return;
+			}
+		}
+	// skip through any relocated streams
+	while (++e < iLast && e->entry.ref < 0)
+		;
+	iNext = e;
+	if (e == iLast)
+		iState = ERelocateToc;
+	}