diff -r 000000000000 -r bde4ae8d615e os/persistentdata/persistentstorage/dbms/ustor/US_CLSTR.CPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/os/persistentdata/persistentstorage/dbms/ustor/US_CLSTR.CPP	Fri Jun 15 03:10:57 2012 +0200
@@ -0,0 +1,656 @@
+// 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;
+	}