1 // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 //

    15 

    16 #include "UT_STD.H"

    17 

    18 // PFS frame-related utilities

    19 

    20 TInt SkipLink(TInt anExtent)

    21 //

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

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

    24 //

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

    26 

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

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

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

    30 

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

    32 //

    33 // Check that aLength can be relocated into the space

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

    35 //

    36 	{

    37 	TInt end=SkipLink(aSpace+aLength);

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

    39 	}

    40 

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

    42 //

    43 // scan a stream to discover it's extent

    44 //

    45 	{

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

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

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

    49 //

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

    51 	TFrameDes16 des;

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

    53 	TInt frame=des;

    54 	if ((frame&KMaskFrameType16)!=EFrameData16)

    55 		if ((frame&KMaskFrameType16)!=EFrameDescriptive16)

    56 		{

    57 		aMark.Withdraw(aHost);

    58 		__LEAVE(KErrCorrupt);

    59 		}

    60 //

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

    62 	do

    63 		{

    64 		frame&=KMaskFrameLength16;

    65 		TInt lim=anchor-aStream;

    66 		if (frame!=KFrameOpen16)

    67 			{

    68 			if (frame>=lim)

    69 				{

    70 				aMark.Withdraw(aHost);

    71 				__LEAVE(KErrCorrupt);

    72 				}

    73 			return aStream+frame;

    74 			}

    75 		aMark.SeekL(aHost,EStreamMark,lim);

    76 		aStream=anchor;

    77 		anchor+=KFrameFullLength16;

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

    79 		frame=des;

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

    81 	return aStream;

    82 	}

    83 

    84 

    85 

    86 // Class TRelocatorInput

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

    88 

    89 const TInt KRelocatorBufferSize=0xc00;

    90 

    91 NONSHARABLE_CLASS(TRelocatorInput) : public MStreamInput

    92 	{

    93 public:

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

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

    96 	void CommitL();

    97 private:

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

    99 	TStreamTransfer ReadFromL(MStreamBuf& aSource,TStreamTransfer aTransfer);

   100 	void DesL(TFrameType16 aType);

   101 //

   102 	inline TStreamExchange& Host() const;

   103 	inline TStreamMark& Mark();

   104 private:

   105 	TStreamExchange* iHost;

   106 	TStreamMark* iMark;

   107 	TFrameType16 iType;

   108 	TInt iRemain;

   109 	TInt iAnchor;

   110 	TInt iTerminator;

   111 	};

   112 

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

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

   115 	{}

   116 inline TStreamExchange& TRelocatorInput::Host() const

   117 	{

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

   119 	return *iHost;

   120 	}

   121 inline TStreamMark& TRelocatorInput::Mark()

   122 	{

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

   124 	return *iMark;

   125 	}

   126 

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

   128 //

   129 // initiate the relocated stream

   130 //

   131 	{

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

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

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

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

   136 //

   137 	iType=aType;

   138 	iRemain=aLength;

   139 	iTerminator=aTerminator;

   140 	iAnchor=KFrameFullLength16-(aPos&KMaskFrameLength16);

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

   142 	}

   143 

   144 

   145 void TRelocatorInput::CommitL()

   146 //

   147 // complete the relocated stream

   148 //

   149 	{

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

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

   152 //

   153 	if (iTerminator<0)

   154 		return;

   155 //

   156 	TFrameDes16 des[2];

   157 	des[1]=TFrameDes16(iTerminator);

   158 	TInt l=KSizeFrameDes16;

   159 	if (iAnchor<=KSizeFrameDes16)

   160 		l+=iAnchor;

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

   162 	}

   163 

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

   165 //

   166 // use a passive write through to the host

   167 //

   168 	{

   169 	return 0;

   170 	}

   171 

   172 void TRelocatorInput::DesL(TFrameType16 aType)

   173 //

   174 // Write the next frame descriptor

   175 //

   176 	{

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

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

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

   180 	}

   181 

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

   183 //

   184 // bulk of the transfer happens here

   185 //

   186 	{

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

   188 	do

   189 		{

   190 		TUint8 buf[KRelocatorBufferSize];

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

   192 		if (len==0)

   193 			break;

   194 		aTransfer-=len;

   195 		const TUint8* p=buf;

   196 		if (iType!=EFrameFree16)

   197 			{

   198 			DesL(iType);

   199 			iType=EFrameFree16;

   200 			}

   201 		for (;;)

   202 			{

   203 			if (iAnchor==0)

   204 				{	// write next anchor

   205 				iAnchor=KFrameFullLength16;

   206 				DesL(EFrameContinuation16);

   207 				}

   208 			TInt frame=Min(len,iAnchor);

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

   210 			iAnchor-=frame;

   211 			iRemain-=frame;

   212 			len-=frame;

   213 			if (len==0)

   214 				break;

   215 			p+=frame;

   216 			}

   217 		} while (aTransfer>0);

   218 	return aTransfer;

   219 	}

   220 

   221 

   222 

   223 // Class TPermanentStoreRelocator

   224 // used to locate streams for relocation in limited memory

   225 

   226 class TPermanentStoreRelocator

   227 	{

   228 #if defined(__SMALL_BUNDLE)

   229 	enum {EBundleSize=8-1};

   230 #else

   231 	enum {EBundleSize=64-1};

   232 #endif

   233 public:

   234 	typedef CPermanentStoreCollector::TEntry TEntry;

   235 public:

   236 	void Reset();

   237 	TBool Reset(TInt aPos);

   238 	TInt FillL(CPermanentStoreToc& aToc);

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

   240 //

   241 	TBool FindFit(TInt aSpace,TInt anEnd);

   242 	inline const TEntry* Current() const;

   243 	void Relocated(const TEntry* anEntry);

   244 //

   245 	TInt Extent(TInt aStream) const;

   246 	inline TInt MinLength() const;

   247 private:

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

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

   250 private:

   251 	TEntry* iNext;

   252 	const TEntry* iFinish;

   253 	TInt iMore;

   254 	TInt iPos;

   255 	TInt iCurrentMin,iMinLength;

   256 	TEntry iTable[EBundleSize];

   257 	};

   258 

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

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

   261 inline TInt TPermanentStoreRelocator::MinLength() const

   262 	{return iMinLength;}

   263 

   264 void TPermanentStoreRelocator::Reset()

   265 //

   266 // reset the cached length values

   267 //

   268 	{

   269 	iPos=0;

   270 	iMinLength=1;

   271 	}

   272 

   273 TBool TPermanentStoreRelocator::Reset(TInt aPos)

   274 //

   275 // reset the iterator for a new scan from aPos

   276 //

   277 	{

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

   279 //

   280 	iCurrentMin=KMaxTInt;

   281 	TEntry* e=iTable;

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

   283 		{	// rescan required

   284 		iFinish=iNext=NULL;

   285 		iMore=-1;

   286 		iPos=aPos;

   287 		return EFalse;

   288 		}

   289 

   290 // can use current data

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

   292 		{

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

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

   295 		}

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

   297 	iNext=e;

   298 	return ETrue;

   299 	}

   300 

   301 TBool TPermanentStoreRelocator::FillL(CPermanentStoreToc& aToc)

   302 //

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

   304 // return if there are more available

   305 //

   306 	{

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

   308 	if (!iMore)

   309 		return EFalse;

   310 //

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

   312 //

   313 	RPermanentStoreTocIter iter(aToc);

   314 	CleanupReleasePushL(iter);

   315 

   316 	TInt streams=0;

   317 	TInt from=iPos;

   318 	TEntry* table=iTable;

   319 	TEntry* last=table;

   320 	TEntry* end=table+EBundleSize;

   321 	TEntry entry;

   322 	__DEBUG(entry.len=-1);

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

   324 		{

   325 		if (entry.entry.handle<0)

   326 			continue;

   327 		TInt off=entry.entry.ref;

   328 		if (off<from)

   329 			continue;

   330 		++streams;

   331 		if (last<end)

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

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

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

   335 		}

   336 	CleanupStack::PopAndDestroy();

   337 

   338 	iMore=streams+table-last;

   339 	if (streams)

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

   341 	iNext=table;

   342 	iFinish=last;

   343 	while (--last>table)

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

   345 	return streams>0;

   346 	}

   347 

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

   349 //

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

   351 //

   352 	{

   353 	TInt ix=aHole+1-aHeap;

   354 	while (aHole>aHeap)

   355 		{

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

   357 		ix-=link;

   358 		TEntry* parent=aHole-link;

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

   360 			break;

   361 		*aHole=*parent;

   362 		aHole=parent;

   363 		}

   364 	*aHole=aValue;

   365 	}

   366 

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

   368 //

   369 // pop the top and push aValue

   370 //

   371 	{

   372 	TEntry top=*aHeap;

   373 	TEntry* hole=aHeap;

   374 	--anEnd;

   375 	TInt ix=1;

   376 	for (;;)

   377 		{

   378 		TEntry* child=hole+ix;

   379 		ix<<=1;

   380 		if (child>anEnd)

   381 			break;

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

   383 			{

   384 			++ix;

   385 			++child;

   386 			}

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

   388 			break;

   389 		*hole=*child;

   390 		hole=child;

   391 		}

   392 	*hole=aValue;

   393 	return top;

   394 	}

   395 

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

   397 //

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

   399 //

   400 	{

   401 	const TEntry* end=iFinish;

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

   403 		{

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

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

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

   407 		TInt pos=e->entry.ref;

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

   409 		}

   410 	}

   411 

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

   413 //

   414 // Find a stream which will fit into the space

   415 //

   416 	{

   417 	const TEntry* end=iFinish;

   418 	TEntry* e;

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

   420 		{

   421 		if (e->entry.handle<0)

   422 			continue;

   423 		TInt len=e->len;

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

   425 		if (Fits(aSpace,anEnd,len))

   426 			{

   427 			iNext=e;

   428 			return ETrue;

   429 			}

   430 		// len has been left behind, check for minimum

   431 		if (len<iCurrentMin)

   432 			iCurrentMin=len;

   433 		}

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

   435 	if (iMore==0)

   436 		iMinLength=iCurrentMin;

   437 	iNext=e;

   438 	return EFalse;

   439 	}

   440 

   441 void TPermanentStoreRelocator::Relocated(const TEntry* anEntry)

   442 //

   443 // Relocation has been successful

   444 //

   445 	{

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

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

   448 	e->entry.handle=-1;

   449 	iNext=e+1;

   450 	}

   451 

   452 TInt TPermanentStoreRelocator::Extent(TInt aStream) const

   453 //

   454 // Return this stream extent if we know it

   455 //

   456 	{

   457 	const TEntry* e=iTable;

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

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

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

   461 		{

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

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

   464 		}

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

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

   467 	return aStream+e->len;

   468 	}

   469 

   470 

   471 

   472 // class TPermanentStoreStreamIter

   473 

   474 void TPermanentStoreStreamIter::Reset()

   475 //

   476 // reset the iterator for a new scan

   477 //

   478 	{

   479 	iNext=NULL;

   480 	iFinish=NULL;

   481 	iMore=-1;

   482 	iPos=0;

   483 	}

   484 

   485 TInt TPermanentStoreStreamIter::FillL(CPermanentStoreToc& aToc)

   486 //

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

   488 // return the total streams left to iterate

   489 //

   490 	{

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

   492 	if (!iMore)

   493 		return 0;

   494 //

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

   496 //

   497 	RPermanentStoreTocIter iter(aToc);

   498 	CleanupReleasePushL(iter);

   499 

   500 	TInt streams=0;

   501 	TInt from=iPos;

   502 	TInt* heap=iTable;

   503 	TInt* last=heap;

   504 	TInt* end=heap+EBundleSize;

   505 	RPermanentStoreTocIter::TEntry entry;

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

   507 		{

   508 		if (entry.handle<0)

   509 			continue;

   510 		TInt off=entry.ref;

   511 		if (off<from)

   512 			continue;

   513 		++streams;

   514 		if (last<end)

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

   516 		else if (off<*heap)

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

   518 		}

   519 	CleanupStack::PopAndDestroy();

   520 

   521 	iMore=streams+(heap-last);

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

   523 	iNext=heap;

   524 	iFinish=last;

   525 	while (--last>heap)

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

   527 	return streams;

   528 	}

   529 

   530 TInt TPermanentStoreStreamIter::Next()

   531 //

   532 // return the next offset, or <0 if the table is empty

   533 //

   534 	{

   535 	__ASSERT_DEBUG(iMore>=0,User::Invariant());

   536 //

   537 	while (iNext<iFinish)

   538 		{

   539 		TInt off=*iNext++;

   540 		if (off>=0)

   541 			return off;

   542 		}

   543 	return -1;

   544 	}

   545 

   546 void TPermanentStoreStreamIter::Relocated(TInt aStream)

   547 //

   548 // aStream has been relocated, mark the table

   549 //

   550 	{

   551 	__ASSERT_DEBUG(iMore>=0,User::Invariant());

   552 //

   553 	if (aStream>=iPos)

   554 		return;

   555 	TInt* p=iNext;

   556 	for (;;)

   557 		{

   558 		if (p==iFinish)

   559 			return;

   560 		if (*p>=0)

   561 			break;

   562 		++p;

   563 		}

   564 	if (aStream<*p)

   565 		return;

   566 //

   567 	for (;*p!=aStream;++p)

   568 		{

   569 		__ASSERT_DEBUG(p<iFinish,User::Invariant());

   570 		__ASSERT_DEBUG(*p<aStream,User::Invariant());

   571 		}

   572 	if (p==iNext)

   573 		iNext=p+1;

   574 	else

   575 		*p=-1;

   576 	}

   577 

   578 void TPermanentStoreStreamIter::Push(TInt* aHeap,TInt* aHole,TInt aValue)

   579 //

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

   581 //

   582 	{

   583 	TInt ix=aHole+1-aHeap;

   584 	while (aHole>aHeap)

   585 		{

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

   587 		ix-=link;

   588 		TInt* parent=aHole-link;

   589 		if (*parent>=aValue)

   590 			break;

   591 		*aHole=*parent;

   592 		aHole=parent;

   593 		}

   594 	*aHole=aValue;

   595 	}

   596 

   597 TInt TPermanentStoreStreamIter::PopPush(TInt* aHeap,TInt* anEnd,TInt aValue)

   598 //

   599 // pop the top and push aValue

   600 //

   601 	{

   602 	TInt top=*aHeap;

   603 	TInt* hole=aHeap;

   604 	--anEnd;

   605 	TInt ix=1;

   606 	for (;;)

   607 		{

   608 		TInt* child=hole+ix;

   609 		ix<<=1;

   610 		if (child>anEnd)

   611 			break;

   612 		if (child<anEnd && *(child+1)>*child)

   613 			{

   614 			++ix;

   615 			++child;

   616 			}

   617 		if (*child<=aValue)

   618 			break;

   619 		*hole=*child;

   620 		hole=child;

   621 		}

   622 	*hole=aValue;

   623 	return top;

   624 	}

   625 

   626 

   627 

   628 // Class CPermanentStoreCollector

   629 

   630 CPermanentStoreCollector* CPermanentStoreCollector::CompactorL(CPermanentStoreCoord& aCoord)

   631 	{

   632 	CPermanentStoreCollector* self=ReclaimerL(aCoord);

   633 	CleanupStack::PushL(self);

   634 	self->iReloc=new(ELeave) TPermanentStoreRelocator;

   635 	CleanupStack::Pop();

   636 	return self;

   637 	}

   638 

   639 CPermanentStoreCollector* CPermanentStoreCollector::ReclaimerL(CPermanentStoreCoord& aCoord)

   640 	{

   641 	return new(ELeave) CPermanentStoreCollector(aCoord);

   642 	}

   643 

   644 CPermanentStoreCollector::CPermanentStoreCollector(CPermanentStoreCoord& aCoord)

   645 	: iCoord(&aCoord),iHost(&aCoord.Host()),iStreams(EGranularity,_FOFF(TEntry,entry.ref))

   646 	{

   647 	Coord().Inc();

   648 	}

   649 

   650 CPermanentStoreCollector::~CPermanentStoreCollector()

   651 	{

   652 	delete iReloc;

   653 	iStreams.Close();

   654 	iMark.Withdraw(Host());

   655 	Coord().Dec();

   656 	}

   657 

   658 void CPermanentStoreCollector::DoRelease()

   659 	{

   660 	delete this;

   661 	}

   662 

   663 void CPermanentStoreCollector::DoResetL(TInt& aCount)

   664 	{

   665 	iMark.Withdraw(Host());

   666 	iMark=KStreamBeginning;

   667 	iCoordGen=Coord().Generation();

   668 	iFree=0;

   669 	TRAPD(r, aCount = FastResetL());

   670 	if (r == KErrNone)

   671 		return;

   672 	if (r != KErrNoMemory)

   673 		User::Leave(r);

   674 // fall back to fixed memory solution

   675 	iState=EGetFree;

   676 	if (Compacting())

   677 		iReloc->Reset();

   678 	iIter.Reset();

   679 	TInt streams=iIter.FillL(Coord().ConsolidateL());

   680 	aCount=streams+1;

   681 	}

   682 

   683 const TInt KMaxStepEffort=9;

   684 

   685 void CPermanentStoreCollector::DoNextL(TInt& aStep,TInt& aTotal)

   686 //

   687 // Dispatch the next set of operations

   688 //

   689 	{

   690 	if (aStep<=0)

   691 		{

   692 		__DEBUG(Panic(TStorePanic()));

   693 		return;

   694 		}

   695 //

   696 	if (iCoordGen!=Coord().Generation() || Coord().TableL().IsVirtual())

   697 		__LEAVE(KErrNotReady);

   698 //

   699 	TInt effort=0;

   700 	do

   701 		{

   702 		switch (iState)

   703 			{

   704 		default:

   705 			__DEBUG(User::Invariant());

   706 		case EGetFree:

   707 			effort+=GetFreeL();

   708 			break;

   709 		case ESkip:

   710 			effort+=SkipL(aTotal);

   711 			--aStep;

   712 			break;

   713 		case EInitRelocator:

   714 			effort+=InitRelocator();

   715 			break;

   716 		case EFillRelocator:

   717 			effort+=FillRelocatorL();

   718 			break;

   719 		case EEvalRelocator:

   720 			effort+=EvalRelocatorL();

   721 			break;

   722 		case EScanRelocator:

   723 			effort+=ScanRelocator();

   724 			break;

   725 		case ERelocateStream:

   726 			effort+=RelocateStreamL();

   727 			--aStep;

   728 			break;

   729 		case ERelocateToc:

   730 			RelocateTocL(aTotal);

   731 			iStreams.Close();

   732 			__ASSERT_DEBUG(aStep==1,User::Invariant());

   733 			aStep=0;

   734 			return;

   735 		case EFastSort:

   736 			FastSort();

   737 			--aStep;

   738 			return;

   739 		case EFastExtent:

   740 			FastExtentL(aTotal);

   741 			--aStep;

   742 			return;

   743 		case EFastRelocate:

   744 			FastRelocateL(aTotal);

   745 			--aStep;

   746 			return;

   747 			}

   748 		} while(effort<KMaxStepEffort);

   749 	__ASSERT_DEBUG(aStep>=1,User::Invariant());

   750 	}

   751 

   752 TInt CPermanentStoreCollector::GetFreeL()

   753 //

   754 // find the end of the free space

   755 //

   756 	{

   757 	__ASSERT_DEBUG(iState==EGetFree,User::Invariant());

   758 	__ASSERT_DEBUG(iFree>=0,User::Invariant());

   759 //

   760 	TInt effort=0;

   761 	iEnd=iIter.Next();

   762 	if (iEnd<0)

   763 		{

   764 		if (iIter.FillL(Coord().ConsolidateL())==0)

   765 			{

   766 			iState=ERelocateToc;	// no more streams

   767 			return effort;

   768 			}

   769 		effort=KMaxStepEffort;

   770 		iEnd=iIter.Next();

   771 		__ASSERT_DEBUG(iEnd>=0,User::Invariant());

   772 		}

   773 	iState=Compacting() && HaveEnoughSpace() ? EInitRelocator : ESkip;

   774 	return effort;

   775 	}

   776 

   777 TInt CPermanentStoreCollector::SkipL(TInt& aTotal)

   778 //

   779 // Find some free space, iEnd was the last stream extracted from concat

   780 //

   781 	{

   782 	__ASSERT_DEBUG(iState==ESkip,User::Invariant());

   783 	__ASSERT_DEBUG(iFree>=0&&iFree<=iEnd,User::Invariant());

   784 //

   785 	aTotal+=iEnd-iFree;

   786 	iFree=SkipLink(ExtentL(iEnd));

   787 	iState=EGetFree;

   788 	return 1;		// effort

   789 	}

   790 

   791 TInt CPermanentStoreCollector::InitRelocator()

   792 //

   793 // initialise the relocator for the free space

   794 //

   795 	{

   796 	__ASSERT_DEBUG(iState==EInitRelocator,User::Invariant());

   797 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   798 //

   799 	iState=iReloc->Reset(iEnd) ? EScanRelocator : EFillRelocator;

   800 	return 0;		// no real work at all

   801 	}

   802 

   803 TInt CPermanentStoreCollector::FillRelocatorL()

   804 //

   805 // Fill the relocator table

   806 //

   807 	{

   808 	__ASSERT_DEBUG(iState==EFillRelocator,User::Invariant());

   809 	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());

   810 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   811 //

   812 	TBool more=iReloc->FillL(Coord().ConsolidateL());

   813 	iState=more ? EEvalRelocator : ESkip;

   814 	return more ? KMaxStepEffort : 0;

   815 	}

   816 

   817 TInt CPermanentStoreCollector::EvalRelocatorL()

   818 //

   819 // evaluate the extents for the relocator

   820 //

   821 	{

   822 	__ASSERT_DEBUG(iState==EEvalRelocator,User::Invariant());

   823 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   824 //

   825 	iReloc->EvaluateLengthsL(Host(),iMark,Coord().Base());

   826 	iState=EScanRelocator;

   827 	return KMaxStepEffort;

   828 	}

   829 

   830 TInt CPermanentStoreCollector::ScanRelocator()

   831 //

   832 // find a stream that will fit

   833 //

   834 	{

   835 	__ASSERT_DEBUG(iState==EScanRelocator,User::Invariant());

   836 	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());

   837 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   838 //

   839 	iState=iReloc->FindFit(iFree,iEnd) ? ERelocateStream : EFillRelocator;

   840 	return 0;

   841 	}

   842 

   843 TInt CPermanentStoreCollector::RelocateStreamL()

   844 //

   845 // find and relocate a stream

   846 //

   847 	{

   848 	__ASSERT_DEBUG(iState==ERelocateStream,User::Invariant());

   849 	__ASSERT_DEBUG(iFree>=0&&iFree<iEnd,User::Invariant());

   850 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   851 //

   852 	const TEntry& e = *iReloc->Current();

   853 	RelocateStreamL(e, iEnd);

   854 	iState=e.entry.ref==iEnd ? EGetFree : HaveEnoughSpace() ? EScanRelocator : ESkip;

   855 	iIter.Relocated(e.entry.ref);

   856 	iReloc->Relocated(&e);

   857 	return KMaxStepEffort;

   858 	}

   859 

   860 void CPermanentStoreCollector::RelocateTocL(TInt& aTotal)

   861 //

   862 // relocate the toc - return any wasted bytes

   863 //

   864 	{

   865 	__ASSERT_DEBUG(iState==ERelocateToc,User::Invariant());

   866 	__ASSERT_DEBUG(iFree>=0,User::Invariant());

   867 //

   868 	TInt toc=Coord().iToc+KOffsetTocHeader;

   869 	if (toc<0)

   870 		return;

   871 //

   872 	if (Compacting())

   873 		{

   874 		TInt len=Coord().TableL().Extent()-toc;

   875 		if (Fits(iFree,toc,len))

   876 			{

   877 			RelocateL(toc, len, EFrameDescriptive16, toc);

   878 			Coord().MoveL(iFree-KOffsetTocHeader,iFree + len);

   879 			return;

   880 			}

   881 		}

   882 	// don't move it

   883 	aTotal += toc-iFree;

   884 	}

   885 

   886 TBool CPermanentStoreCollector::HaveEnoughSpace() const

   887 	{

   888 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   889 //

   890 	return SpaceFor(iFree,iEnd,iReloc->MinLength());

   891 	}

   892 

   893 TInt CPermanentStoreCollector::ExtentL(TInt aStream)

   894 //

   895 // Check if the relocator knows before scanning the file

   896 //

   897 	{

   898 	if (Compacting())

   899 		{

   900 		TInt ext=iReloc->Extent(aStream);

   901 		if (ext>=0)

   902 			return ext;

   903 		}

   904 	return ::ExtentL(Host(),iMark,Coord().Base(),aStream);

   905 	}

   906 

   907 void CPermanentStoreCollector::RelocateStreamL(const CPermanentStoreCollector::TEntry& aReloc, TInt aExtent)

   908 //

   909 // relocate a stream into [iFree, aExtent)

   910 //

   911 	{

   912 	if (Coord().Accessed())	// must have exclusive access to relocate the stream

   913 		__LEAVE(KErrInUse);

   914 //

   915 	TInt end=RelocateL(aReloc.entry.ref,aReloc.len,aReloc.entry.handle == KHandleTocBase ? EFrameDescriptive16 : EFrameData16, aExtent);

   916 	Coord().RelocateL(aReloc.entry.handle, iFree);

   917 	iCoordGen=Coord().Generation();	// changed by relocation

   918 	iFree = end;

   919 	}

   920 

   921 TInt CPermanentStoreCollector::RelocateL(TInt aStream, TInt aLength, TFrameType16 aType, TInt aExtent)

   922 //

   923 // Relocate a data stream into [iFree, aExtent)

   924 //

   925 	{

   926 	__ASSERT_DEBUG(Fits(iFree,aExtent,aLength),User::Invariant());

   927 	__ASSERT_DEBUG(Compacting(),User::Invariant());

   928 //

   929 	TInt end=SkipLink(iFree+aLength);

   930 	TInt terminator;

   931 	if (end==aExtent)

   932 		terminator=-1;

   933 	else

   934 		{

   935 		TInt anchor=((end>>KShiftFrameLength16)+1)<<KShiftFrameLength16;

   936 		if (aExtent<anchor)

   937 			{

   938 			__ASSERT_DEBUG(aExtent-KSizeFrameDes16-end>0,User::Invariant());

   939 			terminator=EFrameFree16+(aExtent-KSizeFrameDes16-end);

   940 			}

   941 		else

   942 			terminator=EFrameFree16+KFrameOpen16;

   943 		}

   944 //

   945 	RFrame16Buf from(Coord().Base());

   946 	from.Set(Host(),aStream,aStream+aLength,MStreamBuf::ERead);

   947 	from.PushL();

   948 	TRelocatorInput input(Host(),iMark);

   949 	input.OpenL(aType,Coord().Base(),iFree,aLength,terminator);

   950 	from.ReadL(input,aLength);

   951 	input.CommitL();

   952 	CleanupStack::PopAndDestroy();

   953 //

   954 	return end;

   955 	}

   956 

   957 

   958 TInt CPermanentStoreCollector::FastResetL()

   959 //

   960 // Fill the table with the streams with data in the store

   961 //

   962 	{

   963 	iStreams.Reset();

   964 //

   965 	CleanupClosePushL(iStreams);

   966 	RPermanentStoreTocIter iter(Coord().ConsolidateL());

   967 	CleanupReleasePushL(iter);

   968 	TEntry entry;

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

   970 		{

   971 		if (entry.entry.handle<0)

   972 			continue;

   973 		if (entry.entry.ref<0)

   974 			continue;

   975 		User::LeaveIfError(iStreams.Append(entry));

   976 		}

   977 	CleanupStack::PopAndDestroy(&iter);

   978 	CleanupStack::Pop(&iStreams);

   979 //

   980 	// always have final (toc) step

   981 	iState = ERelocateToc;

   982 	TInt streams = iStreams.Count();

   983 	if (streams == 0)

   984 		return 1;

   985 	iState = EFastSort;

   986 	// ordering is 1 step and evaluating the extents is several more

   987 	TInt count = 2 + (streams + EExtentStep - 1)/EExtentStep;

   988 	if (Compacting())

   989 		count += streams;

   990 	return count;

   991 	}

   992 

   993 void CPermanentStoreCollector::FastSort()

   994 	{

   995 	__ASSERT_DEBUG(iState == EFastSort, User::Invariant());

   996 //

   997 	iStreams.SortSigned();

   998 	iNext = &iStreams[0];

   999 	iLast = iNext + iStreams.Count();

  1000 	iState = EFastExtent;

  1001 	}

  1002 

  1003 void CPermanentStoreCollector::FastExtentL(TInt& aTotal)

  1004 //

  1005 // Evaluate the lengths for all the streams

  1006 // if reclaiming, update aTotal with free space skipped

  1007 // return false until we've done the last one

  1008 //

  1009 	{

  1010 	__ASSERT_DEBUG(iState == EFastExtent, User::Invariant());

  1011 	__ASSERT_DEBUG(iNext != iLast, User::Invariant());

  1012 

  1013 	TEntry* e = iNext;

  1014 	const TEntry* end = Min(iLast, e + EExtentStep);

  1015 	do

  1016 		{

  1017 		TInt ref = e->entry.ref;

  1018 		__ASSERT_DEBUG(TUint(iFree)<=TUint(ref),User::Invariant());

  1019 		TInt ext = ::ExtentL(Host(), iMark, Coord().Base(), ref);

  1020 		e->len = ext - ref;

  1021 		if (!Compacting())

  1022 			aTotal += ref - iFree;

  1023 		iFree = SkipLink(ext);

  1024 		} while (++e < end);

  1025 	iNext = e;

  1026 //

  1027 	if (e == iLast)

  1028 		{

  1029 		if (!Compacting())

  1030 			iState = ERelocateToc;

  1031 		else

  1032 			{

  1033 			iNext = &iStreams[0];

  1034 			iFree = 0;

  1035 			iState = EFastRelocate;

  1036 			}

  1037 		}

  1038 	}

  1039 

  1040 CPermanentStoreCollector::TEntry* CPermanentStoreCollector::BestFit(TInt aPos, TInt aExt, TEntry* aFirst, TEntry* aLast)

  1041 //

  1042 // [aPos, aExt) is a hole - find the best fit to fill it in [aFirst, aLast)

  1043 //

  1044 	{

  1045 	__ASSERT_DEBUG(aPos <= aExt, User::Invariant());

  1046 	TEntry* r = 0;

  1047 	if (aPos == aExt)

  1048 		return r;

  1049 //

  1050 	if ((aExt & KMaskFrameLength16) != 0)

  1051 		aExt -= KSizeFrameDes16;

  1052 	const TInt mingap = Min(KSizeFrameDes16 + 1, (aExt & KMaskFrameLength16));

  1053 	TInt rlen = 0;

  1054 	TInt avail = aExt - aPos;

  1055 	do

  1056 		{

  1057 		TInt len;

  1058 		for (;;)

  1059 			{

  1060 			len = (--aLast)->len;

  1061 			if (len > rlen)

  1062 				break;

  1063 			if (aFirst == aLast)

  1064 				return r;

  1065 			}

  1066 		TInt d = avail - len;

  1067 		if (d < 0)

  1068 			continue;

  1069 		if (d == 0)			// exact fit

  1070 			return aLast;

  1071 		if (d < mingap)

  1072 			continue;

  1073 		r = aLast;

  1074 		rlen = len;

  1075 		} while (aFirst != aLast);

  1076 	return r;

  1077 	}

  1078 

  1079 void CPermanentStoreCollector::FastRelocateL(TInt& aTotal)

  1080 //

  1081 // Look for a stream to move. Either move a stream or fail to find a fit before returning

  1082 // fill holes from the front of the file with the biggest block that will fit (inverted current algorithm)

  1083 // return true when the last hole has been looked at

  1084 //

  1085 	{

  1086 	__ASSERT_DEBUG(iState == EFastRelocate, User::Invariant());

  1087 	__ASSERT_DEBUG(iNext != iLast, User::Invariant());

  1088 

  1089 	TEntry* e = iNext;

  1090 	TInt ext = e->entry.ref;

  1091 	__ASSERT_DEBUG(ext >= 0, User::Invariant());

  1092 

  1093 	TEntry* r = BestFit(iFree, ext, e, iLast);

  1094 	if (!r)

  1095 		{

  1096 		// Nothing fits, accumulate free space

  1097 		aTotal += ext - iFree;

  1098 		iFree = SkipLink(ext + e->len);

  1099 		}

  1100 	else

  1101 		{

  1102 		// lets move it

  1103 		RelocateStreamL(*r, ext);

  1104 		if (r != e)

  1105 			{

  1106 			// relocated a stream other than the one terminating the current hole

  1107 			// mark it at moved

  1108 			r->entry.ref = -1;

  1109 			r->len = -1;

  1110 			return;

  1111 			}

  1112 		}

  1113 	// skip through any relocated streams

  1114 	while (++e < iLast && e->entry.ref < 0)

  1115 		;

  1116 	iNext = e;

  1117 	if (e == iLast)

  1118 		iState = ERelocateToc;

  1119 	}