// 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;

	}