--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/store/USTOR/UT_COLL.CPP Fri Jan 22 11:06:30 2010 +0200
@@ -0,0 +1,1119 @@
+// 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);
+ }
+
+void CPermanentStoreCollector::RelocateStreamL(const CPermanentStoreCollector::TEntry& aReloc, TInt aExtent)
+//
+// relocate a stream into [iFree, 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);
+ Coord().RelocateL(aReloc.entry.handle, iFree);
+ 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;
+ }