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

 // Class RClusterMap

 void RClusterMap::InsertL( TClusterId aCluster, TClusterId aPrevious )

 //

 // insert the entry into the map

 //

 	{

 	TIdPair* map = iMap;

 	if ( iEntries == iAlloc )

 		{	// ensure there is space

 		TInt size = iAlloc + EGranularity;

 		iMap = map = ( TIdPair* )User::ReAllocL( map, size * sizeof( TIdPair ) );

 		iAlloc = size;

 		}

 	TInt l = 0;

 	TInt r = iEntries;

 	while ( r > l )

 		{

 		TInt m = ( l + r ) >> 1;

 		TClusterId id = map[ m ].iId;

 		__ASSERT( aCluster != id );	// not already present

 		if ( aCluster < id )

 			r = m;

 		else

 			l = m + 1;

 		}

 	TIdPair* p = map + r;

 	TIdPair* e = map + iEntries++;

 	Mem::Move( p + 1, p, ( TUint8* )e - ( TUint8* )p );

 	p->iId = aCluster;

 	p->iPreviousId = aPrevious;

 	}

 RClusterMap::TIdPair* RClusterMap::At( TClusterId aCluster )

 	{

 	TInt l = 0;

 	TInt r = iEntries;

 	while ( r > l )

 		{

 		TInt m = ( l + r ) >> 1;

 		TClusterId id = iMap[ m ].iId;

 		if ( aCluster < id )

 			r = m;

 		else if ( aCluster > id )

 			l = m + 1;

 		else

 			return iMap + m;

 		}

 	return 0;

 	}

 void RClusterMap::ResetL( TClusterId aHeadCluster )

 	{

 	iComplete = EFalse;

 	iEntries = 0;

 	InsertL( aHeadCluster, KNullClusterId );

 	iLastMapped = iLastBound = aHeadCluster;

 	iSkipped = ESeparation - 1;

 	}

 TBool RClusterMap::At( TClusterId aCluster, TClusterId& aPreviousCluster )

 	{

 	TIdPair* p = At( aCluster );

 	if ( p )

 		aPreviousCluster = p->iPreviousId;

 	else if ( aCluster == iLastBound )

 		aPreviousCluster = iLastMapped;

 	else

 		return EFalse;

 	return ETrue;

 	}

 void RClusterMap::AddL( TClusterId aCluster )

 	{

 	__ASSERT( aCluster != KNullClusterId );

 	if ( --iSkipped < 0 )

 		{

 		InsertL( aCluster, iLastMapped );

 		iLastMapped = aCluster;

 		iSkipped = ESeparation - 1;

 		}

 	iLastBound = aCluster;

 	}

 void RClusterMap::DropL( TClusterId aCluster, TClusterId aNext )

 //

 // Cluster has been deleted, modify entry to contain the next cluster

 // last cluster in table is never deleted

 //

 	{

 	if ( aCluster == iLastBound )

 		iLastBound = aNext;

 	TIdPair* entry = At( aCluster );

 	if ( !entry )

 		return;		// not in the sparse map

 // remove entry for cluster->prev

 	TClusterId prev = entry->iPreviousId;

 	Mem::Move( entry, entry + 1, ( TUint8* )( iMap + --iEntries ) - ( TUint8* )entry );

 //

 	if ( aCluster == iLastMapped )

 		iLastMapped = aNext;

 	else

 		{	// find the referring entry next->cluster

 		TIdPair* pnext = iMap;

 		while ( pnext->iPreviousId != aCluster )

 			{

 			++pnext;

 			__ASSERT( pnext < iMap + iEntries );

 			}

 		if ( pnext->iId == aNext )

 			{	// referring entry is the next one => drop a link

 			pnext->iPreviousId = prev;

 			return;

 			}

 		// adjust next->new

 		pnext->iPreviousId = aNext;

 		}

 	// add in new link to replace deleted one

 	InsertL( aNext, prev );	// will not fail allocation as space available

 	}

 // Class TClusterLinkCache

 void TClusterLinkCache::Add( TClusterId aCluster, RClusterMap& aMap )

 //

 // Add an entry to the cache

 //

 	{

 	__ASSERT( iEnd != NULL );

 	TClusterId id;

 	__ASSERT( aMap.At( iMap[0], id ) );

 //

 	TClusterId* p = iEnd;

 	if ( p == &iMap[ RClusterMap::ESeparation ] )

 		{	// full, requires a shift down

 		for ( ; !aMap.At( *p, id ); --p )

 			{

 			__ASSERT( p > iMap );

 			}

 		__ASSERT( p > iMap );

 		__ASSERT( Has( id ) );

 		TClusterId* c = iMap;

 		--c;

 		while ( p <= iEnd )

 			*++c = *p++;

 		p = c;

 		}

 	*++p = aCluster;

 	iEnd = p;

 	}

 void TClusterLinkCache::Add( const TClusterId* aFirst, const TClusterId* aLast )

 //

 // Add several linked TClusterIds

 //

 	{

 	__ASSERT( iEnd != NULL );

 //

 	TClusterId* p = iEnd;

 	while ( aFirst < aLast && p < &iMap[ RClusterMap::ESeparation ] )

 		*++p = *aFirst++;

 	iEnd = p;

 	}

 void TClusterLinkCache::Drop( TClusterId aCluster, TClusterId aNext )

 //

 // Drop the item if it is in the cache

 //

 	{

 	TClusterId* p = iEnd;

 	if ( !p )

 		return;

 	if ( *p == aCluster )

 		{

 		*p = aNext;

 		return;

 		}

 	do

 		{

 		if ( p == iMap )

 			return;

 		} while ( *--p != aCluster );

 	__ASSERT( *( p + 1 ) == aNext );

 	for ( ; p < iEnd; ++p )

 		*p = *( p + 1 );

 	iEnd = p - 1;

 	}

 TBool TClusterLinkCache::Has( TClusterId aCluster ) const

 //

 // Check if the cluster id is in the cache

 // iEnd==0 is a valid state (empty cache)

 //

 	{

 	for ( const TClusterId* p = iEnd; p >= iMap; )

 		{

 		if ( *p-- == aCluster )

 			return ETrue;

 		}

 	return EFalse;

 	}

 TBool TClusterLinkCache::At( TClusterId aCluster, TClusterId& aPrevious ) const

 //

 // If aCluster is in the cache, return the previous cluster in aPrevious

 // iEnd==0 is a valid state (empty cache)

 //

 	{

 	for ( const TClusterId* p = iEnd; p > iMap; )

 		{

 		if ( *p-- == aCluster )

 			{

 			aPrevious = *p;

 			return ETrue;

 			}

 		}

 	return EFalse;

 	}

 // Class TClusterDes

 void TClusterDes::InternalizeL(RReadStream& aStream)

 	{

 	aStream>>iNext;

 	iMembership=aStream.ReadUint16L();

 	}

 void TClusterDes::ExternalizeL(RWriteStream& aStream) const

 	{

 	aStream<<iNext;

 	aStream.WriteUint16L(iMembership);

 	}

 // Class CClusterCache

 inline CClusterCache::CClusterCache(CDbStoreDatabase& aDatabase)

 	: iDatabase(aDatabase),iCache(_FOFF(CCluster,iLink))

 	{}

 CClusterCache* CClusterCache::NewL(CDbStoreDatabase& aDatabase)

 	{

 	CClusterCache* self=new(ELeave) CClusterCache(aDatabase);

 	CleanupStack::PushL(self);

 	// Add the initial clusters

 	for(TInt i=0;i<(EMaxClusters/2);++i)

 		{

 		self->AddClusterL();

 		}

 	CleanupStack::Pop();

 	return self;

 	}

 LOCAL_C void DeleteCluster(CCluster* aCluster)

 //

 // helper function which matches the Apply() prototype

 //

 	{

 	delete aCluster;

 	}

 CClusterCache::~CClusterCache()

 	{

 	Apply(DeleteCluster);

 	}

 LOCAL_C void DiscardCluster(CCluster* aCluster)

 //

 // helper function which matches the Apply() prototype

 //

 	{

 	aCluster->Discard();

 	}

 void CClusterCache::Discard()

 //

 // discard the current changes in all clusters

 //

 	{

 	Apply(DiscardCluster);

 	}

 LOCAL_C void FlushClusterL(CCluster* aCluster)

 //

 // helper function which matches the Apply() prototype

 //

 	{

 	aCluster->FlushL();

 	}

 void CClusterCache::FlushL()

 //

 // Flush all the clusters in the cache

 //

 	{

 	Apply(FlushClusterL);

 	}

 CCluster* CClusterCache::Cluster(TClusterId aCluster)

 //

 // Look for a cluster in the cache

 //

 	{

 	TDblQueIter<CCluster> iter(iCache);

 	for (CCluster* cluster;(cluster=iter++)!=0;)

 		{

 		if (cluster->Id()==aCluster)

 			return cluster;

 		}

 	return 0;

 	}

 CCluster& CClusterCache::ClusterL(TClusterId aCluster)

 //

 // Get a cluster from the cache or store and move it to the top of the cache

 // Track hits to the two clusters which most recently dropped out of the cache

 //

 	{

 	CCluster* cluster=Cluster(aCluster);	// check if it is cached

 	iFollowOnHits<<=2;

 	if (!cluster)

 		{		// get an empty cluster and read it

 		if (aCluster==iCachePlus1)

 			{	// the cluster has recently been discarded

 			iCachePlus1=iCachePlus2;	// re-sequence the cache follow-on

 			iFollowOnHits|=0x1;

 			}

 		else if (aCluster==iCachePlus2)

 			iFollowOnHits|=0x2;	// the cluster has recently been discarded

 		cluster=&NewClusterL();

 		cluster->ReadL(aCluster);

 		}

 	return Touch(*cluster);

 	}

 CCluster& CClusterCache::ClusterL()

 //

 // Get a new (empty) cluster from the cache and move it to the top

 //

 	{

 	return Touch(NewClusterL());

 	}

 CCluster& CClusterCache::Touch(CCluster& aCluster)

 //

 // Move a cluster to the top of the LRU list

 //

 	{

 	aCluster.iLink.Deque();

 	iCache.AddFirst(aCluster);

 	return aCluster;

 	}

 CCluster& CClusterCache::AddClusterL()

 //

 // Add a new cluster to the cache

 //

 	{

 	__ASSERT(iClusters<EMaxClusters);

 	CCluster& cluster=*CCluster::NewL(Database());

 	iCache.AddLast(cluster);

 	++iClusters;

 	// move +2 hits into +1 zone and clear +1 hits

 	iFollowOnHits=TUint8((TUint(iFollowOnHits)>>1)&0x55);

 	return cluster;

 	}

 CCluster& CClusterCache::NewClusterL()

 //

 // Get an empty cluster from the cache, but do not touch it

 // If the hit detector has registered enough near-misses the cache is expanded

 // by adding another cluster object

 //

 	{

 	CCluster* cluster=Cluster(KNullClusterId);	// look for a discarded cluster first

 	if (cluster)

 		return *cluster;

 // check for cache expansion

 	TUint detected=iFollowOnHits;

 	if ((detected&(detected-1))!=0 && iClusters<EMaxClusters)

 		return AddClusterL();

 // retire the last cache entry

 	cluster=iCache.Last();

 	cluster->FlushL();

 	iCachePlus2=iCachePlus1;

 	iCachePlus1=cluster->Id();

 	return *cluster;

 	}

 void CClusterCache::Apply(void (*aFunc)(CCluster*))

 //

 // Apply the function paramater to all clusters in the cache

 // This function may leave <==> the parameter function may leave

 //

 	{

 	TDblQueIter<CCluster> iter(iCache);

 	for (CCluster* cluster;(cluster=iter++)!=0;)

 		aFunc(cluster);

 	}

 // Class CCluster

 CCluster* CCluster::NewL(CDbStoreDatabase& aDatabase)

 	{

 	return new(ELeave) CCluster(aDatabase);

 	}

 CCluster::~CCluster()

 	{

 	User::Free(iMap[0]);

 	}

 void CCluster::AdjustMap(TUint8** aMapEntry,TInt aAdjust)

 //

 // Adjust all map entries after aMapEntry

 //

 	{

 	do *aMapEntry+=aAdjust; while (++aMapEntry<=&iMap[KMaxClustering]);

 	}

 TInt CCluster::SetSizeL(TInt aSize)

 //

 // Set the minimum size for the cluster buffer

 // Return the offset between the new and old cells

 //

 	{

 	if (iSize>=aSize)

 		return 0;

 //

 	aSize+=EGranularity-1;		// round to granularity

 	aSize&=~(EGranularity-1);

 	TUint8* base=iMap[0];

 	TInt offset=(TUint8*)User::ReAllocL(base,aSize)-base;

 	iSize=aSize;

 	if (offset)

 		AdjustMap(&iMap[0],offset);

 	return offset;

 	}

 void CCluster::Discard()

 //

 // discard the current changes

 //

 	{

 	iCluster=KNullClusterId;

 	iModified=EFalse;

 	}

 void CCluster::Create(TClusterId aClusterId)

 //

 // Create a new cluster

 //

 	{

 	__ASSERT(!iModified);

 //

 	iCluster=aClusterId;

 	iDes.iNext=KNullClusterId;

 	iDes.iMembership=0;

 	TUint8* base=iMap[0];

 	for (TUint8** ptr=&iMap[1];ptr<=&iMap[KMaxClustering];++ptr)

 		*ptr=base;

 	iModified=ETrue;

 	}

 void CCluster::Relink(TClusterId aNextClusterId)

 //

 // Update the cluster to link to a different cluster

 //

 	{

 	iDes.iNext=aNextClusterId;

 	iModified=ETrue;

 	}

 void CCluster::AlterL(MAlter& aAlterer)

 //

 // alter all records in the cluster

 //

 	{

 	TUint members=iDes.iMembership;

 	TUint8* wptr=iMap[0];

 	TUint8* rptr=wptr;

 	for (TUint8** map=&iMap[0];map<&iMap[KMaxClustering];members>>=1,++map)

 		{

 		if (members&1)

 			{

 			TInt size=map[1]-rptr;

 			TInt expand=wptr-rptr+aAlterer.RecordExpansion(rptr,size);

 			if (expand>0)

 				{	// requires more space for alteration

 				AdjustL(map,expand+EExpandBuffer,rptr);

 				wptr=map[0];	// compensate for possible moving cache

 				rptr=map[1]-size;	// record data is at end of this entry

 				}

 			wptr=aAlterer.AlterRecordL(wptr,rptr,size);

 			rptr+=size;

 			__ASSERT(wptr<=rptr);

 			}

 		else

 			{

 			__ASSERT(map[1]==rptr);

 			}

 		map[1]=wptr;

 		}

 	iModified=ETrue;

 	}

 TPtrC8 CCluster::RecordL(TInt aIndex)

 //

 // Read the cluster and return the record data

 //

 	{

 	if (!((iDes.iMembership>>aIndex)&1))

 		__LEAVE(KErrNotFound);

 	return TPtrC8(iMap[aIndex],iMap[aIndex+1]-iMap[aIndex]);

 	}

 TUint8* CCluster::UpdateL(TInt aIndex,TInt aNewSize)

 //

 // read the cluster and return a writable descriptor over the new record data

 //

 	{

 	SetRecordL(aIndex,aNewSize);

 	iDes.iMembership|=(1<<aIndex);

 	return iMap[aIndex];

 	}

 TBool CCluster::DeleteL(TInt aIndex)

 //

 // return whether the cluster is empty or not

 //

 	{

 	SetRecordL(aIndex,0);

 	iDes.iMembership&=~(1<<aIndex);

 	return iDes.iMembership;

 	}

 void CCluster::FlushL()

 	{

 	if (iModified)

 		{	// Externalize the cluster

 		RDbStoreWriteStream cluster(iDatabase);

 		cluster.ReplaceLC(iDatabase.Store(),iCluster);

 		cluster<<iDes;

 		TUint8** map=&iMap[0];

 		TUint8* base=*map;

 		TUint8* ptr=base;

 		for (TUint members=iDes.iMembership;members!=0;members>>=1)

 			{

 			++map;

 			if (members&1)

 				{

 				TUint8* end=*map;

 				cluster << TCardinality(end-ptr);

 				ptr=end;

 				}

 			else

 				{

 				__ASSERT(*map==ptr);

 				}

 			}

 		cluster.FilterL(cluster.EMixed,iCluster);

 		cluster.WriteL(base,ptr-base);

 		cluster.CommitL();

 		CleanupStack::PopAndDestroy();

 		iModified=EFalse;

 		}

 	}

 void CCluster::ReadL(TClusterId aCluster)

 //

 // Internalize the cluster

 //

 	{

 	__ASSERT(iCluster!=aCluster);

 	__ASSERT(!iModified);

 //

 	iCluster=KNullClusterId;

 	RDbStoreReadStream cluster(iDatabase);

 	cluster.OpenLC(iDatabase.Store(),aCluster);

 	cluster>>iDes;

 	TUint8** map=&iMap[0];

 	TUint8* base=*map;

 	TUint8* ptr=base;

 	for (TUint members=iDes.iMembership;members!=0;members>>=1)

 		{

 		if (members&1)

 			{

 			TCardinality card;

 			cluster >> card;

 			TInt size=card;

 			if (size>KDbStoreMaxRecordLength)

 				__LEAVE(KErrCorrupt);

 			ptr+=size;

 			}

 		*++map=ptr;

 		}

 	while (map<&iMap[KMaxClustering])

 		*++map=ptr;

 	TInt len=ptr-base;

 	base+=SetSizeL(len);

 	cluster.FilterL(cluster.EMixed,aCluster);

 	cluster.ReadL(base,len);

 	CleanupStack::PopAndDestroy();

 	iCluster=aCluster;

 	}

 void CCluster::SetRecordL(TInt aIndex,TInt aNewSize)

 	{

 	AdjustL(&iMap[aIndex],iMap[aIndex]+aNewSize-iMap[aIndex+1],iMap[aIndex+1]);

 	iModified=ETrue;

 	}

 void CCluster::AdjustL(TUint8** aMapEntry,TInt aAdjust,TUint8* aData)

 //

 // Adjust the record at map entry by aAdjust bytes

 // Move that entry data as well as the ones following for AlterCluster

 //

 	{

 	if (!aAdjust)

 		return;

 //

 	__ASSERT(aAdjust+aMapEntry[1]>=aMapEntry[0]);	// record cannot go -ve size

 	__ASSERT(aData>=aMapEntry[0]);					// must not save data before this record

 //

 	aData+=SetSizeL(iMap[KMaxClustering]-iMap[0]+aAdjust);

 	Mem::Copy(aData+aAdjust,aData,iMap[KMaxClustering]-aData);

 	AdjustMap(aMapEntry+1,aAdjust);

 	}

 // class CCluster::MAlter

 TInt CCluster::MAlter::RecordExpansion(const TUint8*,TInt)

 //

 // default to no expansion

 //

 	{

 	return 0;

 	}