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

 #include "D32COMP.H"

 // Class TDbStoreIndexStats::TBound

 inline void TDbStoreIndexStats::TBound::Set(TReal64 aBound)

 	{iValue=aBound;}

 void TDbStoreIndexStats::TBound::Set(const TInt64& aBound)

 	{iValue=I64REAL(aBound);}

 void TDbStoreIndexStats::TBound::Set(const TText8* aPtr,TInt aLen,const TTextOps& aConv)

 	{

 	TInt64 v(0u);

 	const TText8* const end=aPtr+aLen;

 	TInt shift=48;

 	do

 		{

 		if (aPtr==end)

 			break;

 		TInt64 t(aConv.Fold(*aPtr++));

 		t<<=shift;

 		v+=t;

 		} while ((shift-=8)>=0);

 	Set(v);

 	}

 void TDbStoreIndexStats::TBound::Set(const TText16* aPtr,TInt aLen,const TTextOps& aConv)

 	{

 	TInt64 v(0u);

 	const TText16* const end=aPtr+aLen;

 	TInt shift=32;

 	do

 		{

 		if (aPtr==end)

 			break;

 		TInt64 t(aConv.Fold(*aPtr++));

 		t<<=shift;

 		v+=t;

 		} while ((shift-=16)>=0);

 	Set(v);

 	}

 void TDbStoreIndexStats::TBound::Set(const TDbLookupKey::SColumn& aBound,const TTextOps& aConv)

 	{

 	switch (aBound.iType)

 		{

 	default:

 		__ASSERT(0);

 	case EDbColInt64:

 		Set(aBound.iInt64);

 		break;

 	case EDbColDateTime:

 		Set(aBound.iTime().Int64());

 		break;

 	case EDbColReal64:

 		Set(aBound.iReal64);

 		break;

 	case EDbColText8:

 		Set(aBound.iDes8.iPtr,aBound.iDes8.iLength,aConv);

 		break;

 	case EDbColText16:

 		Set(aBound.iDes16.iPtr,aBound.iDes16.iLength,aConv);

 		break;

 		}

 	}

 // Class TDbStoreIndexStats

 inline TBool TDbStoreIndexStats::NeedsRefresh() const

 	{

 	return iRefresh<=ERefresh;

 	}

 inline TInt TDbStoreIndexStats::Cardinality() const

 	{

 	return iCardinality;

 	}

 // update the refresh count

 inline void TDbStoreIndexStats::Touch()

 	{

 	TInt r=iRefresh-1;

 	if (r>=ERefresh) 

 		iRefresh=r;

 	}

 // an entry is inserted

 inline void TDbStoreIndexStats::Inc()

 	{

 	++iCardinality;

 	Touch();

 	}

 // an entry is removed

 inline void TDbStoreIndexStats::Dec()

 	{

 	--iCardinality;

 	Touch();

 	}

 // contents have changed radically. provoke an immediate refresh

 inline void TDbStoreIndexStats::Reset(TInt aCardinality)

 	{

 	iCardinality=aCardinality;

 	iRefresh=ERefresh;

 	}

 // stats have been refreshed. set for next update

 inline void TDbStoreIndexStats::Refresh(TDbStoreIndexStats::TType aType)

 	{

 	iFlags=(iFlags&~EFlgDiscrete)|aType;

 	iRefresh=(iCardinality>>ERefreshFactor)+1;

 	}

 //

 // Internalize the index statistics

 // This must handle a stream externalized by builds before 052

 //

 void TDbStoreIndexStats::InternalizeL(RReadStream& aStream)

 	{

 	TCardinality c;

 	aStream>>c;

 	iCardinality=c;

 	TUint refresh=aStream.ReadUint32L();

 	iFlags=refresh&EFlagsMask;

 	iRefresh=TInt(refresh>>ERefreshShift)+EInvalid;

 //

 // pre-build-052 data would run out here

 // if there is no more data, mark the (non-cardinality) stats as invalid

 //

 	TRAPD(r,aStream>>iLower.iValue>>iUpper.iValue;)

 	if (r==KErrEof)

 		iRefresh=EInvalid;		// mark as invalid data

 	else

 		__LEAVE_IF_ERROR(r);	// just an "ordinary" error

 	}

 //

 // Notes: iCardinality cannot exceed 2^29 (due to storage mechanism)

 //		thus iRefresh cannot exceed 2^(29-ERefreshFactor)+1

 //		this leaves the 5 m.s.b. clear in iRefresh-EInvalid

 //		the flags bits are stored there

 //

 void TDbStoreIndexStats::ExternalizeL(RWriteStream& aStream) const

 	{

 	__ASSERT((iFlags&~EFlagsMask)==0);

 	aStream<<TCardinality(iCardinality);

 	aStream<<TUint32((TUint(iRefresh-EInvalid)<<ERefreshShift)|iFlags);

 	aStream<<iLower.iValue<<iUpper.iValue;

 	}

 //

 // Reverse the span and bounds

 //

 TInt TDbStoreIndexStats::ReverseSpan(TUint aInclusion,const TDbLookupKey* aLower,const TDbLookupKey* aUpper,const TTextOps& aConv) const

 	{

 	__ASSERT(iLower.iValue>iUpper.iValue);

 	TDbStoreIndexStats stats(*this);

 	stats.iLower=iUpper;

 	stats.iUpper=iLower;

 	return stats.Span((aInclusion<<1)|(aInclusion>>1),aUpper,aLower,aConv);

 	}

 //

 // Evaluate the probable proportion of the index set contained within the bounds

 //

 TInt TDbStoreIndexStats::Span(TUint aInclusion,const TDbLookupKey* aLower,const TDbLookupKey* aUpper,const TTextOps& aConv) const

 	{

 	if (!IsValid())

 		return CDbTable::EUnavailableSpan;	// No valid index data

 	if (iCardinality==0)

 		return 0;					// no rows at all

 //

 	if (iLower.iValue>iUpper.iValue)

 		return ReverseSpan(aInclusion,aLower,aUpper,aConv);	// descending index

 //

 	aInclusion&=CDbRecordIndex::EIncludeBoth;

 	TBound l(iLower);

 	if (aLower)

 		{

 		TBound bound;

 		bound.Set(*aLower->First(),aConv);

 		if (bound.iValue>=l.iValue)

 			l=bound;

 		else

 			aInclusion|=CDbRecordIndex::EIncludeLower;

 		}

 	else

 		aInclusion|=CDbRecordIndex::EIncludeLower;

 //

 	TBound h(iUpper);

 	if (aUpper)

 		{

 		TBound bound;

 		bound.Set(*aUpper->First(),aConv);

 		if (bound.iValue<=h.iValue)

 			h=bound;

 		else

 			aInclusion|=CDbRecordIndex::EIncludeUpper;

 		}

 	else

 		aInclusion|=CDbRecordIndex::EIncludeUpper;

 //

 	TRealX restrict(h.iValue);

 	restrict.SubEq(l.iValue);		// extended precision--no errors

 	TRealX span(iUpper.iValue);

 	span.SubEq(iLower.iValue);

 	if (iFlags&EFlgDiscrete)

 		{

 		if (aInclusion==0)

 			--restrict;

 		else if (aInclusion==CDbRecordIndex::EIncludeBoth)

 			++restrict;

 		++span;

 		}

 	else if (restrict.IsZero())		// single value continuous range

 		{

 		return (span.IsZero() && aInclusion==CDbRecordIndex::EIncludeBoth)

 			? CDbTable::EFullIndexSpan : 0;

 		}

 	if (restrict<=TRealX(0))

 		return 0;	// no overlap

 	restrict.DivEq(span);

 	restrict.MultEq(TInt(CDbTable::EFullIndexSpan));

 	return TInt(restrict);

 	}

 // Class CDbStoreIndex

 inline CDbStoreIndex::HKey& CDbStoreIndex::Key() const

 	{

 	return *iKey;

 	}

 inline const TBtree& CDbStoreIndex::Tree() const

 	{

 	return iTree;

 	}

 inline TInt CDbStoreIndex::Count() const

 	{

 	return iStats.Cardinality();

 	}

 // Class CDbStoreIndex::HKey

 NONSHARABLE_CLASS(CDbStoreIndex::HKey) : public MBtreeKey

 	{

 public:

 	static HKey* NewL(const CDbKey& aKey,const HDbColumnSet& aColSet);

 //

 	inline TInt EntrySize() const;

 	virtual TInt KeySize() const;

 	virtual TBool IncompleteKey() const;

 //

 	TInt EntryL(TAny* aPtr,const RDbTableRow& aRow,TDbRecordId aRecord);

 	TInt EntryL(TAny* aPtr,const TDbLookupKey& aKey);

 	inline const TAny* Restriction() const;

 	inline void Restrict(const TAny* aRestriction);

 //

 	void Bound(TDbStoreIndexStats::TBound& aBound,const TAny* aEntry);

 	TDbStoreIndexStats::TType KeyType() const;

 // from MBtreeKey

 	const TAny* Key(const TAny* aRecord) const;

 	TInt Compare(const TAny* aLeft,const TAny* aRight) const;

 protected:

 	HKey() {}

 	inline TBool FullComparison() const;

 // from MBtreeKey

 	void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const;

 private:

 	struct SKeyCol

 		{

 		TDbColNo iOrdinal;

 		TInt iSize;

 		TUint8 iType;

 		TUint8 iOrder;

 		};

 	const TTextOps* iTextOps;

 	TInt iSize;

 	const SKeyCol* iEndOfKeys;

 	const SKeyCol* iRestrictedEndOfKeys;

 	SKeyCol iKeys[1];	// one or more keys

 	};

 NONSHARABLE_CLASS(CDbStoreIndex::HDupKey) : public CDbStoreIndex::HKey

 	{

 	friend class CDbStoreIndex::HKey;

 private:

 	HDupKey() {}

 	TInt KeySize() const;

 	const TAny* Key(const TAny* aRecord) const;

 	TInt Compare(const TAny* aLeft,const TAny* aRight) const;

 	TBool IncompleteKey() const;

 	};

 inline TInt CDbStoreIndex::HKey::EntrySize() const

 	{

 	return iSize;

 	}

 inline const TAny* CDbStoreIndex::HKey::Restriction() const

 	{

 	return iRestrictedEndOfKeys;

 	}

 inline void CDbStoreIndex::HKey::Restrict(const TAny* aRestriction)

 	{

 	__ASSERT(aRestriction==0||(aRestriction>=iKeys&&aRestriction<=iEndOfKeys));

 	iRestrictedEndOfKeys=(const SKeyCol*)aRestriction;

 	}

 inline TBool CDbStoreIndex::HKey::FullComparison() const

 	{

 	return iRestrictedEndOfKeys==NULL;

 	}

 //

 // Construct the key based on the key definition (must be valid for the table)

 // and the column set provided

 //

 CDbStoreIndex::HKey* CDbStoreIndex::HKey::NewL(const CDbKey& aKey,const HDbColumnSet& aColumns)

 	{

 	TInt count=aKey.Count();

 	HKey* self=(HKey*)User::AllocLC(_FOFF(HKey,iKeys[count]));

 	if (aKey.IsUnique())

 		new(self) HKey;

 	else

 		new(self) HDupKey;

 	self->iTextOps=&TTextOps::Ops(aKey.Comparison());

 	self->iEndOfKeys=&self->iKeys[count];

 	self->iRestrictedEndOfKeys=NULL;

 	TInt len=sizeof(TDbRecordId);

 	SKeyCol* pKey=&self->iKeys[0];

 	for (TInt ii=0;ii<count;++pKey,++ii)

 		{

 		const TDbKeyCol& key=aKey[ii];

 		pKey->iOrder=TUint8(key.iOrder);

 		pKey->iOrdinal=aColumns.ColNoL(key.iName);

 		if (pKey->iOrdinal==KDbNullColNo)

 			__LEAVE(KErrCorrupt);

 		const TDbColumnDef& col=aColumns[pKey->iOrdinal];

 		pKey->iType=col.iType;

 		pKey->iSize=CDbStoreIndexDef::KeySize(key,col);

 		len+=Align4(pKey->iSize);

 		}

 	self->iSize=len;

 	if (self->KeySize()>KMaxIndexKeySize)

 		__LEAVE(KErrCorrupt);

 	CleanupStack::Pop();

 	return self;

 	}

 //

 // Construct an entry at aPtr from the record given

 //

 TInt CDbStoreIndex::HKey::EntryL(TAny* aPtr,const RDbTableRow& aRow,TDbRecordId aRecord)

 	{

 	TUint8* ptr=(TUint8*)aPtr;

 	Mem::FillZ(ptr,iSize);

 	*REINTERPRET_CAST(TDbRecordId*,ptr)=aRecord;

 	ptr+=sizeof(TDbRecordId);

 	const SKeyCol* const end=iEndOfKeys;

 	for (const SKeyCol* key=&iKeys[0];key<end;++key)

 		{

 		const TDbCell* cell=aRow.ColCell(key->iOrdinal);

 		TInt size=key->iSize;

 		if (cell->Length()!=0)

 			{

 #ifdef __DOUBLE_WORDS_SWAPPED__

 			if (key->iType==EDbColReal64)

 				{

 				const TUint32* data=(TUint32*)cell->Data();

 				((TUint32*)ptr)[0]=data[1];

 				((TUint32*)ptr)[1]=data[0];

 				}

 			else

 #endif

 			if (TDbCol::IsLong(TDbColType(key->iType)))

 				{

 				const TDbBlob& blob=*(const TDbBlob*)cell->Data();

 				if (blob.IsInline())

 					Mem::Copy(ptr,blob.Data(),Min(size,blob.Size()));

 				else

 					{

 					aRow.Table().BlobsL()->ReadLC(blob.Id(),TDbColType(key->iType))->ReadL(ptr,size);

 					CleanupStack::PopAndDestroy();	// stream buffer

 					}

 				}

 			else

 				Mem::Copy(ptr,cell->Data(),Min(size,cell->Length()));

 			}

 		ptr+=Align4(size);

 		}

 	iRestrictedEndOfKeys=NULL;		// use the full key for comparison

 	return EntrySize();

 	}

 //

 // Construct an entry from a lookup key

 //

 TInt CDbStoreIndex::HKey::EntryL(TAny* aPtr,const TDbLookupKey& aKey)

 	{

 	TUint8* ptr=(TUint8*)aPtr;

 	Mem::FillZ(ptr,iSize);

 	ptr+=sizeof(TDbRecordId);

 	const TDbLookupKey::SColumn* lkey=aKey.First();

 	const TDbLookupKey::SColumn* const lend=lkey+aKey.Count();

 	__ASSERT(lkey<lend);

 	const SKeyCol* const end=iEndOfKeys;

 	const SKeyCol* key=&iKeys[0];

 	for (;;)

 		{

 		TDbColType ltype=lkey->iType;

 		TInt size=key->iSize;

 		switch (key->iType)

 			{

 		default:

 			__ASSERT(0);

 		case EDbColBit:

 		case EDbColUint8:

 		case EDbColUint16:

 		case EDbColUint32:

 			if (ltype==EDbColUint32)

 				{

 				*(TUint32*)ptr=lkey->iUint32;

 				break;

 				}

 			else if (ltype==EDbColInt32)

 				{

 				if (lkey->iInt32>=0)	// domain check, unsigned value

 					{

 					*(TUint32*)ptr=lkey->iInt32;

 					break;

 					}

 				}

 			else if (ltype==EDbColInt64)

 				{

 				const TInt64& v=lkey->iInt64;

 				if (I64HIGH(v)==0)		// domain check, in unsigned 32-bit range

 					{

 					*(TUint32*)ptr=I64LOW(v);

 					break;

 					}

 				}

 			Panic(EDbWrongType);

 			break;

 		case EDbColInt8:

 		case EDbColInt16:

 		case EDbColInt32:

 			if (ltype==EDbColInt32)

 				{

 				*(TInt32*)ptr=lkey->iInt32;

 				break;

 				}

 			else if (ltype==EDbColUint32)

 				{

 				if (lkey->iUint32<=TUint(KMaxTInt))	// domain check, in signed range

 					{

 					*(TInt32*)ptr=lkey->iUint32;

 					break;

 					}

 				}

 			else if (ltype==EDbColInt64)

 				{

 				const TInt64& v=lkey->iInt64;

 				TInt32 l=I64LOW(v);

 				TInt32 h=I64HIGH(v);

 				if (h==(l>>31))	// domain check, in signed 32-bit range

 					{

 					*(TInt32*)ptr=l;

 					break;

 					}

 				}

 			Panic(EDbWrongType);

 			break;

 		case EDbColReal32:

 			if (ltype==EDbColReal32)

 				{

 				*(TReal32*)ptr=lkey->iReal32;

 				break;

 				}

 			else if (ltype==EDbColReal64)

 				{	// convert to TReal32, storing +-#inf if reqd.

 				TRealX(lkey->iReal64).GetTReal(*(TReal32*)ptr);

 				break;

 				}

 			Panic(EDbWrongType);

 			break;

 		case EDbColReal64:

 #ifdef __DOUBLE_WORDS_SWAPPED__

 			if (ltype==EDbColReal64)

 				{

 				const TUint32* data=(TUint32*)&lkey->iReal64;

 				((TUint32*)ptr)[0]=data[1];

 				((TUint32*)ptr)[1]=data[0];

 				break;

 				}

 			// drop through

 #endif

 		case EDbColInt64:

 		case EDbColDateTime:

 			if (ltype==key->iType)

 				Mem::Copy(ptr,&lkey->iInt64,size);	// all at same address

 			else

 				Panic(EDbWrongType);

 			break;

 		case EDbColText8:

 		case EDbColLongText8:

 			if (ltype==EDbColText8)

 				Mem::Copy(ptr,lkey->iDes8.iPtr,Min(size,lkey->iDes8.iLength));

 			else

 				Panic(EDbWrongType);

 			break;

 		case EDbColText16:

 		case EDbColLongText16:

 			if (ltype==EDbColText16)

 				Mem::Copy(ptr,lkey->iDes16.iPtr,Min(size,lkey->iDes16.iLength<<1));

 			else

 				Panic(EDbWrongType);

 			break;

 			}

 		++key;

 		if (++lkey==lend)

 			break;							// end of lookup key

 		if (key==end)

 			__LEAVE(KErrArgument);		// too many keys

 		ptr+=Align4(size);

 		}

 	iRestrictedEndOfKeys=key;				// use only the keys in the lookup for comparison

 	return EntrySize();

 	}

 void CDbStoreIndex::HKey::Bound(TDbStoreIndexStats::TBound& aBound,const TAny* aEntry)

 	{

 	aEntry=PtrAdd(aEntry,sizeof(TDbRecordId));	// get to real key data

 	switch (iKeys[0].iType)

 		{

 	default:

 		__ASSERT(0);

 	case EDbColBit:

 	case EDbColUint8:

 	case EDbColUint16:

 	case EDbColUint32:

 		aBound.Set(TInt64(TUint(*STATIC_CAST(const TUint32*,aEntry))));

 		break;

 	case EDbColInt8:

 	case EDbColInt16:

 	case EDbColInt32:

 		aBound.Set(TInt64(TInt(*STATIC_CAST(const TInt32*,aEntry))));

 		break;

 	case EDbColInt64:

 		aBound.Set(*STATIC_CAST(const TInt64*,aEntry));

 		break;

 	case EDbColDateTime:

 		aBound.Set(STATIC_CAST(const TTime*,aEntry)->Int64());

 		break;

 	case EDbColReal32:

 		aBound.Set(TReal64(*STATIC_CAST(const TReal32*,aEntry)));

 		break;

 	case EDbColReal64:

 #if !defined(__DOUBLE_WORDS_SWAPPED__)

 		aBound.Set(*STATIC_CAST(const TReal64*,aEntry));

 #else

 		{

 		TReal64 xKey;

 		((TUint32*)&xKey)[0]=STATIC_CAST(const TUint32*,aEntry)[1];

 		((TUint32*)&xKey)[1]=STATIC_CAST(const TUint32*,aEntry)[0];

 		aBound.Set(xKey);

 		}

 #endif

 		break;

 	case EDbColText8:

 	case EDbColLongText8:

 		aBound.Set(STATIC_CAST(const TUint8*,aEntry),iKeys[0].iSize,*iTextOps);

 		break;

 	case EDbColText16:

 	case EDbColLongText16:

 		aBound.Set(STATIC_CAST(const TUint16*,aEntry),iKeys[0].iSize>>1,*iTextOps);

 		break;

 		}

 	}

 // Is the index key discrete or continous?

 inline TDbStoreIndexStats::TType CDbStoreIndex::HKey::KeyType() const

 	{

 	return iKeys[0].iType==EDbColReal32 || iKeys[0].iType==EDbColReal64

 		? TDbStoreIndexStats::EContinuous : TDbStoreIndexStats::EDiscrete;

 	}

 TInt CDbStoreIndex::HKey::KeySize() const

 	{

 	return EntrySize()-sizeof(TDbRecordId);

 	}

 //

 // Report 'true' if the lookup key is not the entire B+tree key

 // For a unique index this is if there is a restriction to less than the full key

 //

 TBool CDbStoreIndex::HKey::IncompleteKey() const

 	{

 	return iRestrictedEndOfKeys!=0 && iRestrictedEndOfKeys!=iEndOfKeys;

 	}

 //

 // For unique keys, key is after record id

 //

 const TAny* CDbStoreIndex::HKey::Key(const TAny* aRecord) const

 	{

 	return PtrAdd(aRecord,sizeof(TDbRecordId));

 	}

 //

 // compare the key part of the entry

 //

 TInt CDbStoreIndex::HKey::Compare(const TAny* aLeft,const TAny* aRight) const

 	{

 	const SKeyCol* end=iRestrictedEndOfKeys;

 	if (end==NULL)

 		end=iEndOfKeys;

 	const SKeyCol* key=&iKeys[0];

 	for (;;)

 		{

 		TInt size=key->iSize;

 		TInt rr;

 		switch (key->iType)

 			{

 		default:

 			__ASSERT(0);

 		case EDbColBit:

 		case EDbColUint8:

 		case EDbColUint16:

 		case EDbColUint32:

 			rr=Comp::Compare(*STATIC_CAST(const TUint32*,aLeft),*STATIC_CAST(const TUint32*,aRight));

 			break;

 		case EDbColInt8:

 		case EDbColInt16:

 		case EDbColInt32:

 			rr=Comp::Compare(*STATIC_CAST(const TInt32*,aLeft),*STATIC_CAST(const TInt32*,aRight));

 			break;

 		case EDbColInt64:

 			rr=Comp::Compare(*STATIC_CAST(const TInt64*,aLeft),*STATIC_CAST(const TInt64*,aRight));

 			break;

 		case EDbColDateTime:

 			rr=Comp::Compare(*STATIC_CAST(const TTime*,aLeft),*STATIC_CAST(const TTime*,aRight));

 			break;

 		case EDbColReal32:

 			rr=Comp::Compare(*STATIC_CAST(const TReal32*,aLeft),*STATIC_CAST(const TReal32*,aRight));

 			break;

 		case EDbColReal64:

 #if !defined(__DOUBLE_WORDS_SWAPPED__)

 			rr=Comp::Compare(*STATIC_CAST(const TReal64*,aLeft),*STATIC_CAST(const TReal64*,aRight));

 #else

 			TReal64 xLeft;

 			((TUint32*)&xLeft)[0]=STATIC_CAST(const TUint32*,aLeft)[1];

 			((TUint32*)&xLeft)[1]=STATIC_CAST(const TUint32*,aLeft)[0];

 			TReal64 xRight;

 			((TUint32*)&xRight)[0]=STATIC_CAST(const TUint32*,aRight)[1];

 			((TUint32*)&xRight)[1]=STATIC_CAST(const TUint32*,aRight)[0];

 			rr=Comp::Compare(xLeft,xRight);

 #endif

 			break;

 		case EDbColText8:

 		case EDbColLongText8:

 			rr=iTextOps->Compare(STATIC_CAST(const TUint8*,aLeft),size,STATIC_CAST(const TUint8*,aRight),size);

 			break;

 		case EDbColText16:

 		case EDbColLongText16:

 			rr=iTextOps->Order(STATIC_CAST(const TUint16*,aLeft),size>>1,STATIC_CAST(const TUint16*,aRight),size>>1);

 			break;

 			}

 		if (rr!=0)

 			return key->iOrder==TDbKeyCol::EAsc ? rr : -rr;

 		if (++key==end)

 			return rr;

 		size=Align4(size);

 		aLeft=PtrAdd(aLeft,size);

 		aRight=PtrAdd(aRight,size);

 		}

 	}

 //

 // No clever stuff yet

 //

 void CDbStoreIndex::HKey::Between(const TAny* aLeft,const TAny* /*aRight*/,TBtreePivot& aPivot) const

 	{

 	aPivot.Copy((const TUint8*)aLeft,KeySize());

 	}

 // Class CDbStoreIndex::HDupKey

 TInt CDbStoreIndex::HDupKey::KeySize() const

 	{

 	return EntrySize();

 	}

 //

 // Report 'true' if the lookup key is not the entire B+tree key

 // For a duplicates index this is if there is a restriction (as record id is ingored)

 //

 TBool CDbStoreIndex::HDupKey::IncompleteKey() const

 	{

 	return Restriction()!=0;

 	}

 //

 // The key includes the record id

 //

 const TAny* CDbStoreIndex::HDupKey::Key(const TAny* aRecord) const

 	{

 	return aRecord;

 	}

 TInt CDbStoreIndex::HDupKey::Compare(const TAny* aLeft,const TAny* aRight) const

 	{

 	const TDbRecordId* const left=(const TDbRecordId*)aLeft;

 	const TDbRecordId* const right=(const TDbRecordId*)aRight;

 	TInt rr=HKey::Compare(left+1,right+1);

 	if (rr==0 && FullComparison())

 		return Comp::Compare(left->Value(),right->Value());

 	return rr;

 	}

 // Class CDbStoreIndex::CIter

 NONSHARABLE_CLASS(CDbStoreIndex::CIter) : public CDbRecordIter

 	{

 public:

 	static CIter* NewL(CDbStoreIndex& aIndex,TUint aInclusion,const TDbLookupKey* aLowerBound,const TDbLookupKey* aUpperBound);

 private:

 	inline CIter(CDbStoreIndex& aIndex);

 	~CIter();

 	void ConstructL(TUint aInclusion,const TDbLookupKey* aLowerBound,const TDbLookupKey* aUpperBound);

 	TAny* BoundL(const TDbLookupKey& aBound,const TAny*& aRestriction);

 //

 	inline const CDbStoreIndex& Index() const;

 	TBool FindL(TDbRecordId aRecordId,const RDbTableRow& aRow,TBtree::TFind aFind);

 	TInt CompareL(const TAny* aBound,const TAny* aRestriction);

 	TBool _GotoL(TDbPosition aPosition);

 //

 	TInt Count() const;

 	TDbRecordId CurrentL();

 	TBool GotoL(TDbPosition aPosition);

 	TBool GotoL(TDbRecordId aRecordId,RDbTableRow& aBuffer);

 	TBool SeekL(const TDbLookupKey& aKey,RDbTable::TComparison aComparison);

 	TDeleted DoDeletedL(TDbPosition aPosition,TDbRecordId aRecordId,const RDbTableRow* aRow);

 private:

 	TBtreePos iPos;

 	TUint8 iLowerSeek;

 	TUint8 iLowerCheck;

 	TUint8 iUpperSeek;

 	TUint8 iUpperCheck;

 	TAny* iLowerBound;

 	const TAny* iLowerRestriction;

 	TAny* iUpperBound;

 	const TAny* iUpperRestriction;

 	};

 inline CDbStoreIndex::CIter::CIter(CDbStoreIndex& aIndex) :

 	CDbRecordIter(aIndex)

 	{

 	}

 inline const CDbStoreIndex& CDbStoreIndex::CIter::Index() const

 	{

 	return STATIC_CAST(CDbStoreIndex&,Host());

 	}

 CDbStoreIndex::CIter* CDbStoreIndex::CIter::NewL(CDbStoreIndex& aIndex,TUint aInclusion,const TDbLookupKey* aLowerBound,const TDbLookupKey* aUpperBound)

 	{

 	CIter* self=new(ELeave) CIter(aIndex);

 	CleanupStack::PushL(self);

 	self->ConstructL(aInclusion,aLowerBound,aUpperBound);

 	CleanupStack::Pop();

 	return self;

 	}

 CDbStoreIndex::CIter::~CIter()

 	{

 	User::Free(iLowerBound);

 	User::Free(iUpperBound);

 	}

 void CDbStoreIndex::CIter::ConstructL(TUint aInclusion,const TDbLookupKey* aLowerBound,const TDbLookupKey* aUpperBound)

 	{

 	if (aLowerBound)

 		{

 		TBtree::TFind seek=TBtree::EGreaterEqual;

 		if ((aInclusion&CDbRecordIndex::EIncludeLower)==0)

 			{

 			seek=TBtree::EGreaterThan;

 			iLowerCheck=1;

 			}

 		iLowerSeek=TUint8(seek);

 		iLowerBound=BoundL(*aLowerBound,iLowerRestriction);

 		}

 	if (aUpperBound)

 		{

 		TBtree::TFind seek=TBtree::ELessThan;

 		if (aInclusion&CDbRecordIndex::EIncludeUpper)

 			{

 			seek=TBtree::ELessEqual;

 			iUpperCheck=1;

 			}

 		iUpperSeek=TUint8(seek);

 		iUpperBound=BoundL(*aUpperBound,iUpperRestriction);

 		}

 	}

 //

 // Construct and allocate a key for the boundary value

 //

 TAny* CDbStoreIndex::CIter::BoundL(const TDbLookupKey& aBound,const TAny*& aRestriction)

 	{

 	TUint8 entry[KMaxBtreeKeyLength];

 	HKey& key=Index().Key();

 	TInt size=key.EntryL(entry,aBound);

 	const TUint8* ekey=(const TUint8*)key.Key(entry);

 	size-=ekey-entry;

 	TAny* e=User::AllocL(size);

 	Mem::Copy(e,ekey,size);

 	aRestriction=key.Restriction();

 	return e;

 	}

 //

 // Extract the current key and compare it with a boundary key

 //

 TInt CDbStoreIndex::CIter::CompareL(const TAny* aBound,const TAny* aRestriction)

 	{

 	TUint8 entry[KMaxBtreeKeyLength];

 	HKey& key=Index().Key();

 	key.Restrict(aRestriction);

 	Index().Tree().ExtractAtL(iPos,entry,key.EntrySize());

 	return key.Compare(key.Key(entry),aBound);

 	}

 //

 // return the cardinality of the index

 //

 TInt CDbStoreIndex::CIter::Count() const

 	{

 	if (iLowerBound)

 		return KDbUndefinedCount;

 	if (iUpperBound)

 		return KDbUndefinedCount;

 	return Index().Count();

 	}

 //

 // return the current record id

 //

 TDbRecordId CDbStoreIndex::CIter::CurrentL()

 	{

 	TDbRecordId id;

 	Index().Tree().ExtractAtL(iPos,&id,sizeof(id));

 	return id;

 	}

 //

 // iterate to the required position, does not test the boundary condition

 //

 TBool CDbStoreIndex::CIter::_GotoL(TDbPosition aPosition)

 	{

 	const TBtree& tree=Index().Tree();

 	switch (aPosition)

 		{

 	default:	// all control paths return a value

 		__ASSERT(0);

 	case EDbNext:

 		return tree.NextL(iPos);

 	case EDbPrevious:

 		return tree.PreviousL(iPos);

 	case EDbFirst:

 		if (!iLowerBound)

 			return tree.FirstL(iPos);

 		Index().Key().Restrict(iLowerRestriction);

 		return tree.FindL(iPos,iLowerBound,TBtree::TFind(iLowerSeek));

 	case EDbLast:

 		if (!iUpperBound)

 			return tree.LastL(iPos);

 		Index().Key().Restrict(iUpperRestriction);

 		return tree.FindL(iPos,iUpperBound,TBtree::TFind(iUpperSeek));

 		}

 	}

 //

 // iterate to the required position and check that it is in bounds

 //

 TBool CDbStoreIndex::CIter::GotoL(TDbPosition aPosition)

 	{

 	TBool r=_GotoL(aPosition);

 	if (r)

 		{

 		if (aPosition==EDbFirst || aPosition==EDbNext)

 			{

 			if (iUpperBound)

 				return CompareL(iUpperBound,iUpperRestriction)-iUpperCheck<0;

 			}

 		else

 			{

 			if (iLowerBound)

 				return CompareL(iLowerBound,iLowerRestriction)-iLowerCheck>=0;

 			}

 		}

 	return r;

 	}

 //

 // Construct the Btree key for the row and lookup

 //

 TBool CDbStoreIndex::CIter::FindL(TDbRecordId aRecordId,const RDbTableRow& aRow,TBtree::TFind aFind)

 	{

 	TUint8 entry[KMaxBtreeKeyLength];

 	HKey& key=Index().Key();

 	key.EntryL(entry,aRow,aRecordId);

 	return Index().Tree().FindL(iPos,key.Key(entry),aFind);

 	}

 //

 // Go directly to a row

 //

 TBool CDbStoreIndex::CIter::GotoL(TDbRecordId aRecordId,RDbTableRow& aRow)

 	{

 	aRow.ReadL(aRecordId);

 	return FindL(aRecordId,aRow,TBtree::EEqualTo);

 	}

 //

 // Do a keyed lookup in the index

 //

 TBool CDbStoreIndex::CIter::SeekL(const TDbLookupKey& aKey,RDbTable::TComparison aComparison)

 	{

 	TUint8 entry[KMaxBtreeKeyLength];

 	HKey& key=Index().Key();

 	key.EntryL(entry,aKey);

 	const TAny* ekey=key.Key(entry);

 	TBtree::TFind find;

 	switch (aComparison)

 		{

 	default:

 		__ASSERT(0);

 	case RDbTable::ELessThan:

 		find=TBtree::ELessThan;

 		break;

 	case RDbTable::ELessEqual:

 		find=TBtree::ELessEqual;

 		break;

 	case RDbTable::EEqualTo:

 		if (key.IncompleteKey())

 			{

 			// The B+tree search code cannot correctly do a == search when the

 			// comparison key is not complete. Instead we do a >= search and then

 			// check the returned entry does match

 			//

 			if (!Index().Tree().FindL(iPos,ekey,TBtree::EGreaterEqual))

 				return EFalse;	// off the end

 			return CompareL(ekey,key.Restriction())==0;

 			}

 		find=TBtree::EEqualTo;

 		break;

 	case RDbTable::EGreaterEqual:

 		find=TBtree::EGreaterEqual;

 		break;

 	case RDbTable::EGreaterThan:

 		find=TBtree::EGreaterThan;

 		break;

 		}

 	return Index().Tree().FindL(iPos,ekey,find);

 	}

 //

 // Set the iterator following a record deletion

 //

 CDbStoreIndex::CIter::TDeleted CDbStoreIndex::CIter::DoDeletedL(TDbPosition aPosition,TDbRecordId aRecordId,const RDbTableRow* aRow)

 	{

 	if (aRow==0)

 		return ENotSupported;

 	return FindL(aRecordId,*aRow,aPosition==EDbNext ? TBtree::EGreaterEqual : TBtree::ELessEqual) ? EAtRow : ENoRow;

 	}

 // Class CDbStoreIndex

 CDbStoreIndex::CDbStoreIndex(CDbStoreDatabase& aDatabase,const CDbStoreIndexDef& aDef) :

 	iDatabase(aDatabase), 

 	iTree(EBtreeFast), 

 	iStats(MUTABLE_CAST(TDbStoreIndexStats&,aDef.iStats))

 	{

 	}

 CDbStoreIndex::~CDbStoreIndex()

 	{

 	delete iKey;

 	}

 //

 // Create the persistent representation of the index in the store

 //

 TStreamId CDbStoreIndex::CreateL(CDbStoreDatabase& aDatabase,const CDbStoreIndexDef& aDef)

 	{

 	MUTABLE_CAST(TDbStoreIndexStats&,aDef.iStats).Reset();

 	RStoreWriteStream strm;

 	TStreamId id=strm.CreateLC(aDatabase.Store());

 	strm<<KEmptyBtreeToken<<aDef.iStats;

 	strm.CommitL();

 	CleanupStack::PopAndDestroy();

 	return id;

 	}

 //

 // Check the index for damage (without constructing the object)

 //

 TBool CDbStoreIndex::IsDamagedL(CDbStoreDatabase& aDatabase,const CDbStoreIndexDef& aDef)

 	{

 	RStoreReadStream strm;

 	strm.OpenLC(aDatabase.Store(),aDef.TokenId());

 	TBtreeToken token;

 	strm>>token;

 	CleanupStack::PopAndDestroy();

 	return token.IsBroken();

 	}

 //

 // Create a StoreIndex object

 //

 CDbStoreIndex* CDbStoreIndex::NewL(CDbStoreDatabase& aDatabase,const CDbStoreIndexDef& aDef,const CDbTableDef& aTable)

 	{

 	CDbStoreIndex* self=new(ELeave) CDbStoreIndex(aDatabase,aDef);

 	CleanupStack::PushL(self);

 	self->iTokenId=aDef.TokenId();

 	HKey* key=self->iKey=HKey::NewL(aDef.Key(),aTable.Columns());

 	self->iLeafOrg.SetEntrySize(key->EntrySize());

 	self->iIndexOrg.SetEntrySize(key->KeySize());

 	self->iTree.Connect(&aDatabase.PagePoolL(),key,&self->iLeafOrg,&self->iIndexOrg);

 	CleanupStack::Pop();

 	return self;

 	}

 //

 // restore from the Store

 //

 TBool CDbStoreIndex::RestoreL()

 	{

 	RStoreReadStream strm;

 	strm.OpenLC(iDatabase.Store(),iTokenId);

 	TBtreeToken token;

 	strm>>token>>iStats;

 	CleanupStack::PopAndDestroy();

 	iTree.Set(token,EBtreeFast);

 	return iTree.IsBroken();

 	}

 //

 // Update the index statistics from the index

 //

 void CDbStoreIndex::RefreshStatsL()

 	{

 	HKey& key=Key();

 	TBtreePos pos;

 	if (iTree.FirstL(pos))

 		{

 		TUint8 entry[KMaxBtreeKeyLength];

 		Tree().ExtractAtL(pos,entry,key.EntrySize());

 		key.Bound(iStats.iLower,entry);

 		iTree.LastL(pos);

 		Tree().ExtractAtL(pos,entry,key.EntrySize());

 		key.Bound(iStats.iUpper,entry);

 		}

 	iStats.Refresh(key.KeyType());

 	}

 //

 // Framework member: synchronise the persistent data

 //

 void CDbStoreIndex::SynchL()

 	{

 	if (iStats.NeedsRefresh())

 		RefreshStatsL();

 	RStoreWriteStream strm;

 	strm.ReplaceLC(iDatabase.Store(),iTokenId);

 	strm<<iTree.Token()<<iStats;

 	strm.CommitL();

 	CleanupStack::PopAndDestroy();

 	}

 //

 // Framework member: mark the persistent token dirty

 //

 void CDbStoreIndex::AboutToModifyL()

 	{

 	iDatabase.MarkL();

 	if (!iTree.IsEmpty())	// empty btrees are unbreakable

 		{

 		TBtreeToken token=iTree.Token();

 		token.Touch();		// mark persistent data as broken

 		RStoreWriteStream strm;

 		strm.OpenLC(iDatabase.Store(),iTokenId);

 		strm<<token;

 		strm.CommitL();

 		CleanupStack::PopAndDestroy();

 		}

 	}

 //

 // Try to find a record in the index

 // return ENoMatch if no key match, EEntryMatch if entire entry is present

 // EKeyMatch if only key matches (only for unique indexes)

 //

 CDbStoreIndex::TFind CDbStoreIndex::FindL(TDbRecordId aRecordId,const RDbTableRow& aRow)

 	{

 	__ASSERT((!iTree.IsEmpty())==(Count()!=0));

 	TUint8 entry[KMaxBtreeKeyLength];

 	iKey->EntryL(entry,aRow,aRecordId);

 	TBtreePos pos;

 	if (!iTree.FindL(pos,iKey->Key(entry)))

 		return ENoMatch;

 	TDbRecordId id;

 	iTree.ExtractAtL(pos,&id,sizeof(id));

 	return id==aRecordId ? EEntryMatch : EKeyMatch;

 	}

 //

 // Add the row to the index

 // return True if insertion was good, false if duplicate found

 //

 TBool CDbStoreIndex::DoInsertL(TDbRecordId aRecordId,const RDbTableRow& aRow)

 	{

 	__ASSERT((!iTree.IsEmpty())==(Count()!=0));

 	TUint8 entry[KMaxBtreeKeyLength];

 	TInt len=iKey->EntryL(entry,aRow,aRecordId);

 	TBtreePos pos;

 	TBool insert=iTree.InsertL(pos,entry,len);

 	if (insert)

 		iStats.Inc();

 	return insert;

 	}

 //

 // Remove row from index

 //

 void CDbStoreIndex::DoDeleteL(TDbRecordId aRecordId,const RDbTableRow& aRow)

 	{

 	__ASSERT((!iTree.IsEmpty())==(Count()!=0));

 	TUint8 entry[KMaxBtreeKeyLength];

 	iKey->EntryL(entry,aRow,aRecordId);

 	__DEBUG(TInt dbgchk=) iTree.DeleteL(iKey->Key(entry));

 	__ASSERT(dbgchk);

 	iStats.Dec();

 	}

 //

 // Provide an iterator for the index ordering

 //

 CDbRecordIter* CDbStoreIndex::IteratorL(TUint aInclusion,const TDbLookupKey* aLowerBound,const TDbLookupKey* aUpperBound)

 	{

 	return CIter::NewL(*this,aInclusion,aLowerBound,aUpperBound);

 	}

 //

 // repair the tree from the sequence set after reclamation of the page pool

 //

 void CDbStoreIndex::RepairL()

 	{

 	if (!iTree.IsEmpty())	// empty trees are unbreakable

 		{

 		TouchL();

 		iTree.MarkBroken();

 		iStats.Reset(iTree.RepairL());

 		SynchL();

 		}

 	}

 //

 // Throw away the index data, also used prior to a recovering rebuild

 //

 void CDbStoreIndex::DiscardL()

 	{

 	TouchL();

 	iTree.ClearL();

 	iStats.Reset();

 	MarkIntact();

 	}

 //

 // Throw away the token

 //

 void CDbStoreIndex::DestroyL()

 	{

 	iDatabase.Store().DeleteL(iTokenId);

 	}

 // Class CDbStoreIndex::CDiscarder

 CDbStoreIndex::CDiscarder::CDiscarder()

 	{}

 CDbStoreIndex::CDiscarder::~CDiscarder()

 	{

 	delete iIndex;

 	}

 TInt CDbStoreIndex::CDiscarder::Open(CDbStoreIndex* anIndex)

 	{

 	__ASSERT(!iIndex);

 	iIndex=anIndex;

 	return 1;

 	}

 //

 // Do the single step of index discard

 //

 TInt CDbStoreIndex::CDiscarder::StepL(TInt)

 	{

 	__ASSERT(iIndex);

 	CDbStoreIndex& index=*iIndex;

 	index.DiscardL();

 	index.DestroyL();

 	return 0;

 	}