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

    17 #include "D32COMP.H"

    18 

    19 // Class TDbStoreIndexStats::TBound

    20 

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

    22 	{iValue=aBound;}

    23 

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

    25 	{iValue=I64REAL(aBound);}

    26 

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

    28 	{

    29 	TInt64 v(0u);

    30 	const TText8* const end=aPtr+aLen;

    31 	TInt shift=48;

    32 	do

    33 		{

    34 		if (aPtr==end)

    35 			break;

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

    37 		t<<=shift;

    38 		v+=t;

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

    40 	Set(v);

    41 	}

    42 

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

    44 	{

    45 	TInt64 v(0u);

    46 	const TText16* const end=aPtr+aLen;

    47 	TInt shift=32;

    48 	do

    49 		{

    50 		if (aPtr==end)

    51 			break;

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

    53 		t<<=shift;

    54 		v+=t;

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

    56 	Set(v);

    57 	}

    58 

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

    60 	{

    61 	switch (aBound.iType)

    62 		{

    63 	default:

    64 		__ASSERT(0);

    65 	case EDbColInt64:

    66 		Set(aBound.iInt64);

    67 		break;

    68 	case EDbColDateTime:

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

    70 		break;

    71 	case EDbColReal64:

    72 		Set(aBound.iReal64);

    73 		break;

    74 	case EDbColText8:

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

    76 		break;

    77 	case EDbColText16:

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

    79 		break;

    80 		}

    81 	}

    82 

    83 // Class TDbStoreIndexStats

    84 

    85 inline TBool TDbStoreIndexStats::NeedsRefresh() const

    86 	{

    87 	return iRefresh<=ERefresh;

    88 	}

    89 

    90 inline TInt TDbStoreIndexStats::Cardinality() const

    91 	{

    92 	return iCardinality;

    93 	}

    94 

    95 // update the refresh count

    96 inline void TDbStoreIndexStats::Touch()

    97 	{

    98 	TInt r=iRefresh-1;

    99 	if (r>=ERefresh) 

   100 		iRefresh=r;

   101 	}

   102 

   103 // an entry is inserted

   104 inline void TDbStoreIndexStats::Inc()

   105 	{

   106 	++iCardinality;

   107 	Touch();

   108 	}

   109 

   110 // an entry is removed

   111 inline void TDbStoreIndexStats::Dec()

   112 	{

   113 	--iCardinality;

   114 	Touch();

   115 	}

   116 

   117 // contents have changed radically. provoke an immediate refresh

   118 inline void TDbStoreIndexStats::Reset(TInt aCardinality)

   119 	{

   120 	iCardinality=aCardinality;

   121 	iRefresh=ERefresh;

   122 	}

   123 

   124 // stats have been refreshed. set for next update

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

   126 	{

   127 	iFlags=(iFlags&~EFlgDiscrete)|aType;

   128 	iRefresh=(iCardinality>>ERefreshFactor)+1;

   129 	}

   130 

   131 //

   132 // Internalize the index statistics

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

   134 //

   135 void TDbStoreIndexStats::InternalizeL(RReadStream& aStream)

   136 	{

   137 	TCardinality c;

   138 	aStream>>c;

   139 	iCardinality=c;

   140 	TUint refresh=aStream.ReadUint32L();

   141 	iFlags=refresh&EFlagsMask;

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

   143 //

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

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

   146 //

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

   148 	if (r==KErrEof)

   149 		iRefresh=EInvalid;		// mark as invalid data

   150 	else

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

   152 	}

   153 

   154 //

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

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

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

   158 //		the flags bits are stored there

   159 //

   160 void TDbStoreIndexStats::ExternalizeL(RWriteStream& aStream) const

   161 	{

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

   163 	aStream<<TCardinality(iCardinality);

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

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

   166 	}

   167 

   168 //

   169 // Reverse the span and bounds

   170 //

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

   172 	{

   173 	__ASSERT(iLower.iValue>iUpper.iValue);

   174 	TDbStoreIndexStats stats(*this);

   175 	stats.iLower=iUpper;

   176 	stats.iUpper=iLower;

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

   178 	}

   179 

   180 //

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

   182 //

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

   184 	{

   185 	if (!IsValid())

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

   187 	if (iCardinality==0)

   188 		return 0;					// no rows at all

   189 //

   190 	if (iLower.iValue>iUpper.iValue)

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

   192 //

   193 	aInclusion&=CDbRecordIndex::EIncludeBoth;

   194 	TBound l(iLower);

   195 	if (aLower)

   196 		{

   197 		TBound bound;

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

   199 		if (bound.iValue>=l.iValue)

   200 			l=bound;

   201 		else

   202 			aInclusion|=CDbRecordIndex::EIncludeLower;

   203 		}

   204 	else

   205 		aInclusion|=CDbRecordIndex::EIncludeLower;

   206 //

   207 	TBound h(iUpper);

   208 	if (aUpper)

   209 		{

   210 		TBound bound;

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

   212 		if (bound.iValue<=h.iValue)

   213 			h=bound;

   214 		else

   215 			aInclusion|=CDbRecordIndex::EIncludeUpper;

   216 		}

   217 	else

   218 		aInclusion|=CDbRecordIndex::EIncludeUpper;

   219 //

   220 	TRealX restrict(h.iValue);

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

   222 	TRealX span(iUpper.iValue);

   223 	span.SubEq(iLower.iValue);

   224 	if (iFlags&EFlgDiscrete)

   225 		{

   226 		if (aInclusion==0)

   227 			--restrict;

   228 		else if (aInclusion==CDbRecordIndex::EIncludeBoth)

   229 			++restrict;

   230 		++span;

   231 		}

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

   233 		{

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

   235 			? CDbTable::EFullIndexSpan : 0;

   236 		}

   237 	if (restrict<=TRealX(0))

   238 		return 0;	// no overlap

   239 	restrict.DivEq(span);

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

   241 	return TInt(restrict);

   242 	}

   243 

   244 

   245 // Class CDbStoreIndex

   246 

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

   248 	{

   249 	return *iKey;

   250 	}

   251 	

   252 inline const TBtree& CDbStoreIndex::Tree() const

   253 	{

   254 	return iTree;

   255 	}

   256 	

   257 inline TInt CDbStoreIndex::Count() const

   258 	{

   259 	return iStats.Cardinality();

   260 	}

   261 

   262 

   263 // Class CDbStoreIndex::HKey

   264 

   265 NONSHARABLE_CLASS(CDbStoreIndex::HKey) : public MBtreeKey

   266 	{

   267 public:

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

   269 //

   270 	inline TInt EntrySize() const;

   271 	virtual TInt KeySize() const;

   272 	virtual TBool IncompleteKey() const;

   273 //

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

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

   276 	inline const TAny* Restriction() const;

   277 	inline void Restrict(const TAny* aRestriction);

   278 //

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

   280 	TDbStoreIndexStats::TType KeyType() const;

   281 // from MBtreeKey

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

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

   284 protected:

   285 	HKey() {}

   286 	inline TBool FullComparison() const;

   287 // from MBtreeKey

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

   289 private:

   290 	struct SKeyCol

   291 		{

   292 		TDbColNo iOrdinal;

   293 		TInt iSize;

   294 		TUint8 iType;

   295 		TUint8 iOrder;

   296 		};

   297 	const TTextOps* iTextOps;

   298 	TInt iSize;

   299 	const SKeyCol* iEndOfKeys;

   300 	const SKeyCol* iRestrictedEndOfKeys;

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

   302 	};

   303 

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

   305 	{

   306 	friend class CDbStoreIndex::HKey;

   307 private:

   308 	HDupKey() {}

   309 	TInt KeySize() const;

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

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

   312 	TBool IncompleteKey() const;

   313 	};

   314 

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

   316 	{

   317 	return iSize;

   318 	}

   319 	

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

   321 	{

   322 	return iRestrictedEndOfKeys;

   323 	}

   324 	

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

   326 	{

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

   328 	iRestrictedEndOfKeys=(const SKeyCol*)aRestriction;

   329 	}

   330 	

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

   332 	{

   333 	return iRestrictedEndOfKeys==NULL;

   334 	}

   335 

   336 //

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

   338 // and the column set provided

   339 //

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

   341 	{

   342 	TInt count=aKey.Count();

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

   344 	if (aKey.IsUnique())

   345 		new(self) HKey;

   346 	else

   347 		new(self) HDupKey;

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

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

   350 	self->iRestrictedEndOfKeys=NULL;

   351 	TInt len=sizeof(TDbRecordId);

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

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

   354 		{

   355 		const TDbKeyCol& key=aKey[ii];

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

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

   358 		if (pKey->iOrdinal==KDbNullColNo)

   359 			__LEAVE(KErrCorrupt);

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

   361 		pKey->iType=col.iType;

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

   363 		len+=Align4(pKey->iSize);

   364 		}

   365 	self->iSize=len;

   366 	if (self->KeySize()>KMaxIndexKeySize)

   367 		__LEAVE(KErrCorrupt);

   368 	CleanupStack::Pop();

   369 	return self;

   370 	}

   371 

   372 //

   373 // Construct an entry at aPtr from the record given

   374 //

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

   376 	{

   377 	TUint8* ptr=(TUint8*)aPtr;

   378 	Mem::FillZ(ptr,iSize);

   379 	*REINTERPRET_CAST(TDbRecordId*,ptr)=aRecord;

   380 	ptr+=sizeof(TDbRecordId);

   381 	const SKeyCol* const end=iEndOfKeys;

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

   383 		{

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

   385 		TInt size=key->iSize;

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

   387 			{

   388 #ifdef __DOUBLE_WORDS_SWAPPED__

   389 			if (key->iType==EDbColReal64)

   390 				{

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

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

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

   394 				}

   395 			else

   396 #endif

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

   398 				{

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

   400 				if (blob.IsInline())

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

   402 				else

   403 					{

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

   405 					CleanupStack::PopAndDestroy();	// stream buffer

   406 					}

   407 				}

   408 			else

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

   410 			}

   411 		ptr+=Align4(size);

   412 		}

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

   414 	return EntrySize();

   415 	}

   416 

   417 //

   418 // Construct an entry from a lookup key

   419 //

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

   421 	{

   422 	TUint8* ptr=(TUint8*)aPtr;

   423 	Mem::FillZ(ptr,iSize);

   424 	ptr+=sizeof(TDbRecordId);

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

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

   427 	__ASSERT(lkey<lend);

   428 	const SKeyCol* const end=iEndOfKeys;

   429 	const SKeyCol* key=&iKeys[0];

   430 	for (;;)

   431 		{

   432 		TDbColType ltype=lkey->iType;

   433 		TInt size=key->iSize;

   434 		switch (key->iType)

   435 			{

   436 		default:

   437 			__ASSERT(0);

   438 		case EDbColBit:

   439 		case EDbColUint8:

   440 		case EDbColUint16:

   441 		case EDbColUint32:

   442 			if (ltype==EDbColUint32)

   443 				{

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

   445 				break;

   446 				}

   447 			else if (ltype==EDbColInt32)

   448 				{

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

   450 					{

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

   452 					break;

   453 					}

   454 				}

   455 			else if (ltype==EDbColInt64)

   456 				{

   457 				const TInt64& v=lkey->iInt64;

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

   459 					{

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

   461 					break;

   462 					}

   463 				}

   464 			Panic(EDbWrongType);

   465 			break;

   466 		case EDbColInt8:

   467 		case EDbColInt16:

   468 		case EDbColInt32:

   469 			if (ltype==EDbColInt32)

   470 				{

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

   472 				break;

   473 				}

   474 			else if (ltype==EDbColUint32)

   475 				{

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

   477 					{

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

   479 					break;

   480 					}

   481 				}

   482 			else if (ltype==EDbColInt64)

   483 				{

   484 				const TInt64& v=lkey->iInt64;

   485 				TInt32 l=I64LOW(v);

   486 				TInt32 h=I64HIGH(v);

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

   488 					{

   489 					*(TInt32*)ptr=l;

   490 					break;

   491 					}

   492 				}

   493 			Panic(EDbWrongType);

   494 			break;

   495 		case EDbColReal32:

   496 			if (ltype==EDbColReal32)

   497 				{

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

   499 				break;

   500 				}

   501 			else if (ltype==EDbColReal64)

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

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

   504 				break;

   505 				}

   506 			Panic(EDbWrongType);

   507 			break;

   508 		case EDbColReal64:

   509 #ifdef __DOUBLE_WORDS_SWAPPED__

   510 			if (ltype==EDbColReal64)

   511 				{

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

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

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

   515 				break;

   516 				}

   517 			// drop through

   518 #endif

   519 		case EDbColInt64:

   520 		case EDbColDateTime:

   521 			if (ltype==key->iType)

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

   523 			else

   524 				Panic(EDbWrongType);

   525 			break;

   526 		case EDbColText8:

   527 		case EDbColLongText8:

   528 			if (ltype==EDbColText8)

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

   530 			else

   531 				Panic(EDbWrongType);

   532 			break;

   533 		case EDbColText16:

   534 		case EDbColLongText16:

   535 			if (ltype==EDbColText16)

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

   537 			else

   538 				Panic(EDbWrongType);

   539 			break;

   540 			}

   541 		++key;

   542 		if (++lkey==lend)

   543 			break;							// end of lookup key

   544 		if (key==end)

   545 			__LEAVE(KErrArgument);		// too many keys

   546 		ptr+=Align4(size);

   547 		}

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

   549 	return EntrySize();

   550 	}

   551 

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

   553 	{

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

   555 	switch (iKeys[0].iType)

   556 		{

   557 	default:

   558 		__ASSERT(0);

   559 	case EDbColBit:

   560 	case EDbColUint8:

   561 	case EDbColUint16:

   562 	case EDbColUint32:

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

   564 		break;

   565 	case EDbColInt8:

   566 	case EDbColInt16:

   567 	case EDbColInt32:

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

   569 		break;

   570 	case EDbColInt64:

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

   572 		break;

   573 	case EDbColDateTime:

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

   575 		break;

   576 	case EDbColReal32:

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

   578 		break;

   579 	case EDbColReal64:

   580 #if !defined(__DOUBLE_WORDS_SWAPPED__)

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

   582 #else

   583 		{

   584 		TReal64 xKey;

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

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

   587 		aBound.Set(xKey);

   588 		}

   589 #endif

   590 		break;

   591 	case EDbColText8:

   592 	case EDbColLongText8:

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

   594 		break;

   595 	case EDbColText16:

   596 	case EDbColLongText16:

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

   598 		break;

   599 		}

   600 	}

   601 

   602 // Is the index key discrete or continous?

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

   604 	{

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

   606 		? TDbStoreIndexStats::EContinuous : TDbStoreIndexStats::EDiscrete;

   607 	}

   608 

   609 TInt CDbStoreIndex::HKey::KeySize() const

   610 	{

   611 	return EntrySize()-sizeof(TDbRecordId);

   612 	}

   613 

   614 //

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

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

   617 //

   618 TBool CDbStoreIndex::HKey::IncompleteKey() const

   619 	{

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

   621 	}

   622 

   623 //

   624 // For unique keys, key is after record id

   625 //

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

   627 	{

   628 	return PtrAdd(aRecord,sizeof(TDbRecordId));

   629 	}

   630 

   631 //

   632 // compare the key part of the entry

   633 //

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

   635 	{

   636 	const SKeyCol* end=iRestrictedEndOfKeys;

   637 	if (end==NULL)

   638 		end=iEndOfKeys;

   639 	const SKeyCol* key=&iKeys[0];

   640 	for (;;)

   641 		{

   642 		TInt size=key->iSize;

   643 		TInt rr;

   644 		switch (key->iType)

   645 			{

   646 		default:

   647 			__ASSERT(0);

   648 		case EDbColBit:

   649 		case EDbColUint8:

   650 		case EDbColUint16:

   651 		case EDbColUint32:

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

   653 			break;

   654 		case EDbColInt8:

   655 		case EDbColInt16:

   656 		case EDbColInt32:

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

   658 			break;

   659 		case EDbColInt64:

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

   661 			break;

   662 		case EDbColDateTime:

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

   664 			break;

   665 		case EDbColReal32:

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

   667 			break;

   668 		case EDbColReal64:

   669 #if !defined(__DOUBLE_WORDS_SWAPPED__)

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

   671 #else

   672 			TReal64 xLeft;

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

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

   675 			TReal64 xRight;

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

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

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

   679 #endif

   680 			break;

   681 		case EDbColText8:

   682 		case EDbColLongText8:

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

   684 			break;

   685 		case EDbColText16:

   686 		case EDbColLongText16:

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

   688 			break;

   689 			}

   690 		if (rr!=0)

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

   692 		if (++key==end)

   693 			return rr;

   694 		size=Align4(size);

   695 		aLeft=PtrAdd(aLeft,size);

   696 		aRight=PtrAdd(aRight,size);

   697 		}

   698 	}

   699 

   700 //

   701 // No clever stuff yet

   702 //

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

   704 	{

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

   706 	}

   707 

   708 // Class CDbStoreIndex::HDupKey

   709 

   710 TInt CDbStoreIndex::HDupKey::KeySize() const

   711 	{

   712 	return EntrySize();

   713 	}

   714 

   715 //

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

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

   718 //

   719 TBool CDbStoreIndex::HDupKey::IncompleteKey() const

   720 	{

   721 	return Restriction()!=0;

   722 	}

   723 

   724 //

   725 // The key includes the record id

   726 //

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

   728 	{

   729 	return aRecord;

   730 	}

   731 

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

   733 	{

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

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

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

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

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

   739 	return rr;

   740 	}

   741 

   742 // Class CDbStoreIndex::CIter

   743 

   744 NONSHARABLE_CLASS(CDbStoreIndex::CIter) : public CDbRecordIter

   745 	{

   746 public:

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

   748 private:

   749 	inline CIter(CDbStoreIndex& aIndex);

   750 	~CIter();

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

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

   753 //

   754 	inline const CDbStoreIndex& Index() const;

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

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

   757 	TBool _GotoL(TDbPosition aPosition);

   758 //

   759 	TInt Count() const;

   760 	TDbRecordId CurrentL();

   761 	TBool GotoL(TDbPosition aPosition);

   762 	TBool GotoL(TDbRecordId aRecordId,RDbTableRow& aBuffer);

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

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

   765 private:

   766 	TBtreePos iPos;

   767 	TUint8 iLowerSeek;

   768 	TUint8 iLowerCheck;

   769 	TUint8 iUpperSeek;

   770 	TUint8 iUpperCheck;

   771 	TAny* iLowerBound;

   772 	const TAny* iLowerRestriction;

   773 	TAny* iUpperBound;

   774 	const TAny* iUpperRestriction;

   775 	};

   776 

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

   778 	CDbRecordIter(aIndex)

   779 	{

   780 	}

   781 	

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

   783 	{

   784 	return STATIC_CAST(CDbStoreIndex&,Host());

   785 	}

   786 

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

   788 	{

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

   790 	CleanupStack::PushL(self);

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

   792 	CleanupStack::Pop();

   793 	return self;

   794 	}

   795 

   796 CDbStoreIndex::CIter::~CIter()

   797 	{

   798 	User::Free(iLowerBound);

   799 	User::Free(iUpperBound);

   800 	}

   801 

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

   803 	{

   804 	if (aLowerBound)

   805 		{

   806 		TBtree::TFind seek=TBtree::EGreaterEqual;

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

   808 			{

   809 			seek=TBtree::EGreaterThan;

   810 			iLowerCheck=1;

   811 			}

   812 		iLowerSeek=TUint8(seek);

   813 		iLowerBound=BoundL(*aLowerBound,iLowerRestriction);

   814 		}

   815 	if (aUpperBound)

   816 		{

   817 		TBtree::TFind seek=TBtree::ELessThan;

   818 		if (aInclusion&CDbRecordIndex::EIncludeUpper)

   819 			{

   820 			seek=TBtree::ELessEqual;

   821 			iUpperCheck=1;

   822 			}

   823 		iUpperSeek=TUint8(seek);

   824 		iUpperBound=BoundL(*aUpperBound,iUpperRestriction);

   825 		}

   826 	}

   827 

   828 //

   829 // Construct and allocate a key for the boundary value

   830 //

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

   832 	{

   833 	TUint8 entry[KMaxBtreeKeyLength];

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

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

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

   837 	size-=ekey-entry;

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

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

   840 	aRestriction=key.Restriction();

   841 	return e;

   842 	}

   843 

   844 //

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

   846 //

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

   848 	{

   849 	TUint8 entry[KMaxBtreeKeyLength];

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

   851 	key.Restrict(aRestriction);

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

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

   854 	}

   855 

   856 //

   857 // return the cardinality of the index

   858 //

   859 TInt CDbStoreIndex::CIter::Count() const

   860 	{

   861 	if (iLowerBound)

   862 		return KDbUndefinedCount;

   863 	if (iUpperBound)

   864 		return KDbUndefinedCount;

   865 	return Index().Count();

   866 	}

   867 

   868 //

   869 // return the current record id

   870 //

   871 TDbRecordId CDbStoreIndex::CIter::CurrentL()

   872 	{

   873 	TDbRecordId id;

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

   875 	return id;

   876 	}

   877 

   878 //

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

   880 //

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

   882 	{

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

   884 	switch (aPosition)

   885 		{

   886 	default:	// all control paths return a value

   887 		__ASSERT(0);

   888 	case EDbNext:

   889 		return tree.NextL(iPos);

   890 	case EDbPrevious:

   891 		return tree.PreviousL(iPos);

   892 	case EDbFirst:

   893 		if (!iLowerBound)

   894 			return tree.FirstL(iPos);

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

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

   897 	case EDbLast:

   898 		if (!iUpperBound)

   899 			return tree.LastL(iPos);

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

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

   902 		}

   903 	}

   904 

   905 //

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

   907 //

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

   909 	{

   910 	TBool r=_GotoL(aPosition);

   911 	if (r)

   912 		{

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

   914 			{

   915 			if (iUpperBound)

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

   917 			}

   918 		else

   919 			{

   920 			if (iLowerBound)

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

   922 			}

   923 		}

   924 	return r;

   925 	}

   926 

   927 //

   928 // Construct the Btree key for the row and lookup

   929 //

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

   931 	{

   932 	TUint8 entry[KMaxBtreeKeyLength];

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

   934 	key.EntryL(entry,aRow,aRecordId);

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

   936 	}

   937 

   938 //

   939 // Go directly to a row

   940 //

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

   942 	{

   943 	aRow.ReadL(aRecordId);

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

   945 	}

   946 

   947 //

   948 // Do a keyed lookup in the index

   949 //

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

   951 	{

   952 	TUint8 entry[KMaxBtreeKeyLength];

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

   954 	key.EntryL(entry,aKey);

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

   956 	TBtree::TFind find;

   957 	switch (aComparison)

   958 		{

   959 	default:

   960 		__ASSERT(0);

   961 	case RDbTable::ELessThan:

   962 		find=TBtree::ELessThan;

   963 		break;

   964 	case RDbTable::ELessEqual:

   965 		find=TBtree::ELessEqual;

   966 		break;

   967 	case RDbTable::EEqualTo:

   968 		if (key.IncompleteKey())

   969 			{

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

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

   972 			// check the returned entry does match

   973 			//

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

   975 				return EFalse;	// off the end

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

   977 			}

   978 		find=TBtree::EEqualTo;

   979 		break;

   980 	case RDbTable::EGreaterEqual:

   981 		find=TBtree::EGreaterEqual;

   982 		break;

   983 	case RDbTable::EGreaterThan:

   984 		find=TBtree::EGreaterThan;

   985 		break;

   986 		}

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

   988 	}

   989 

   990 //

   991 // Set the iterator following a record deletion

   992 //

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

   994 	{

   995 	if (aRow==0)

   996 		return ENotSupported;

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

   998 	}

   999 

  1000 // Class CDbStoreIndex

  1001 

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

  1003 	iDatabase(aDatabase), 

  1004 	iTree(EBtreeFast), 

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

  1006 	{

  1007 	}

  1008 

  1009 CDbStoreIndex::~CDbStoreIndex()

  1010 	{

  1011 	delete iKey;

  1012 	}

  1013 

  1014 //

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

  1016 //

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

  1018 	{

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

  1020 	RStoreWriteStream strm;

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

  1022 	strm<<KEmptyBtreeToken<<aDef.iStats;

  1023 	strm.CommitL();

  1024 	CleanupStack::PopAndDestroy();

  1025 	return id;

  1026 	}

  1027 

  1028 //

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

  1030 //

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

  1032 	{

  1033 	RStoreReadStream strm;

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

  1035 	TBtreeToken token;

  1036 	strm>>token;

  1037 	CleanupStack::PopAndDestroy();

  1038 	return token.IsBroken();

  1039 	}

  1040 

  1041 //

  1042 // Create a StoreIndex object

  1043 //

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

  1045 	{

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

  1047 	CleanupStack::PushL(self);

  1048 	self->iTokenId=aDef.TokenId();

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

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

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

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

  1053 	CleanupStack::Pop();

  1054 	return self;

  1055 	}

  1056 

  1057 //

  1058 // restore from the Store

  1059 //

  1060 TBool CDbStoreIndex::RestoreL()

  1061 	{

  1062 	RStoreReadStream strm;

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

  1064 	TBtreeToken token;

  1065 	strm>>token>>iStats;

  1066 	CleanupStack::PopAndDestroy();

  1067 	iTree.Set(token,EBtreeFast);

  1068 	return iTree.IsBroken();

  1069 	}

  1070 

  1071 //

  1072 // Update the index statistics from the index

  1073 //

  1074 void CDbStoreIndex::RefreshStatsL()

  1075 	{

  1076 	HKey& key=Key();

  1077 	TBtreePos pos;

  1078 	if (iTree.FirstL(pos))

  1079 		{

  1080 		TUint8 entry[KMaxBtreeKeyLength];

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

  1082 		key.Bound(iStats.iLower,entry);

  1083 		iTree.LastL(pos);

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

  1085 		key.Bound(iStats.iUpper,entry);

  1086 		}

  1087 	iStats.Refresh(key.KeyType());

  1088 	}

  1089 

  1090 //

  1091 // Framework member: synchronise the persistent data

  1092 //

  1093 void CDbStoreIndex::SynchL()

  1094 	{

  1095 	if (iStats.NeedsRefresh())

  1096 		RefreshStatsL();

  1097 	RStoreWriteStream strm;

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

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

  1100 	strm.CommitL();

  1101 	CleanupStack::PopAndDestroy();

  1102 	}

  1103 

  1104 //

  1105 // Framework member: mark the persistent token dirty

  1106 //

  1107 void CDbStoreIndex::AboutToModifyL()

  1108 	{

  1109 	iDatabase.MarkL();

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

  1111 		{

  1112 		TBtreeToken token=iTree.Token();

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

  1114 		RStoreWriteStream strm;

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

  1116 		strm<<token;

  1117 		strm.CommitL();

  1118 		CleanupStack::PopAndDestroy();

  1119 		}

  1120 	}

  1121 

  1122 //

  1123 // Try to find a record in the index

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

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

  1126 //

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

  1128 	{

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

  1130 	TUint8 entry[KMaxBtreeKeyLength];

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

  1132 	TBtreePos pos;

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

  1134 		return ENoMatch;

  1135 	TDbRecordId id;