sl@0: // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // Order-by stage for the cursor data "pipeline"
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include "UT_STD.H"
sl@0: #include "D32COMP.H"
sl@0: 
sl@0: #ifdef _DEBUG
sl@0: #define _CHECK_ORDERING		// forces a full test of the ordering after sorting
sl@0: #endif
sl@0: 
sl@0: #define MAX( a, b ) ( (a) > (b) ? (a) : (b) )
sl@0: 
sl@0: /* The key structure.
sl@0: 
sl@0: Each key value is always aligned on a 32-bit boundary to allow word reads and writes
sl@0: integral values are always atored as 32-bit values just as for the row buffer
sl@0: Text columns are encoded as follows (trailing padding is omitted from the description)
sl@0: 
sl@0:   Text8 columns			<byte n><n ASCII characters>
sl@0:   n is the [character] length of the column
sl@0: 
sl@0:   Text16 columns		<short n><n UNICODE characters>
sl@0:   n is the [character] length of the column
sl@0: 
sl@0:   LongText8 columns		<word n><n ASCII characters>
sl@0:                  or		<word n|ETrunc><32 ASCII characters><blobId>
sl@0:   n is [byte] size of the column
sl@0: 
sl@0:   LongText16 columns	<word n><n/2 UNICODE characters>
sl@0:                   or	<word n|ETrunc><16 UNICODE characters><blobId>
sl@0:   n is [byte] size of the column
sl@0: 
sl@0: */
sl@0: 
sl@0: 
sl@0: class CDbOrderByStage::HOrdering
sl@0: 	{
sl@0: private:
sl@0: 	struct TKeyCol
sl@0: 		{
sl@0: 		TDbColNo iOrdinal;
sl@0: 		TUint8 iType;
sl@0: 		TUint8 iOrder;
sl@0: 		TUint8 iLength;
sl@0: 		};
sl@0: 	struct TBlobKey
sl@0: 		{
sl@0: 		enum {ETrunc=(TInt)0x80000000};
sl@0: 		enum {ETruncSize=32};		// store 32 bytes of truncated BLOBs
sl@0: 	public:
sl@0: 		inline TInt Size() const;
sl@0: 	public:
sl@0: 		TInt iSize;
sl@0: 		union {TUint8 iData8[ETruncSize]; TUint16 iData16[ETruncSize>>1];};
sl@0: 		TDbBlobId iId;
sl@0: 		};
sl@0: public:
sl@0: 	static HOrdering* NewL(CDbTable& aTable,const CDbKey& aKey);
sl@0: 	TAny* EntryL(TAny* aPtr,const RDbTableRow& aRow) const;
sl@0: 	TInt CompareL(const TAny* aLeft,const TAny* aRight) const;
sl@0: 	TInt MaxSize() const;
sl@0: private:
sl@0: 	inline HOrdering(TInt aCount,TDbTextComparison aComparison,CDbTable& aTable);
sl@0: 	MStreamBuf* BlobLC(TDbBlobId aId,TDbColType aType) const;
sl@0: 	TInt CompareLongText8L(const TBlobKey& aLeft,const TBlobKey& aRight) const;
sl@0: 	TInt CompareLongText16L(const TBlobKey& aLeft,const TBlobKey& aRight) const;
sl@0: private:
sl@0: 	CDbTable& iTable;
sl@0: 	const TTextOps& iTextOps;
sl@0: 	const TKeyCol* iEndOfKeys;
sl@0: 	TKeyCol iKeys[1];	// one or more keys
sl@0: 	};
sl@0: 
sl@0: // Class HDbOrdering
sl@0: 
sl@0: inline TInt CDbOrderByStage::HOrdering::TBlobKey::Size() const
sl@0: 	{
sl@0: 	TInt size=_FOFF(TBlobKey,iData8[iSize+3]);
sl@0: 	return (size&ETrunc) ? sizeof(TBlobKey) : size&~3;
sl@0: 	}
sl@0: 
sl@0: inline CDbOrderByStage::HOrdering::HOrdering(TInt aCount,TDbTextComparison aComparison,CDbTable& aTable) :
sl@0: 	iTable(aTable),
sl@0: 	iTextOps(TTextOps::Ops(aComparison)),
sl@0: 	iEndOfKeys(&iKeys[aCount])
sl@0: 	{
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Construct the ordering based on the key definition (must be valid for the table)
sl@0: // and the column set provided
sl@0: //
sl@0: CDbOrderByStage::HOrdering* CDbOrderByStage::HOrdering::NewL(CDbTable& aTable,const CDbKey& aKey)
sl@0: 	{
sl@0: 	TInt count=aKey.Count();
sl@0: 	__ASSERT(count>0);
sl@0: 	HOrdering* self=new(User::AllocLC(_FOFF(HOrdering,iKeys[count])))
sl@0: 								HOrdering(count,aKey.Comparison(),aTable);
sl@0: 	TKeyCol* pKey=&self->iKeys[0];
sl@0: 	const HDbColumnSet& columns=aTable.Def().Columns();
sl@0: 	for (TInt ii=0;ii<count;++pKey,++ii)
sl@0: 		{
sl@0: 		const TDbKeyCol& key=aKey[ii];
sl@0: 		pKey->iOrder=TUint8(key.iOrder);
sl@0: 		pKey->iOrdinal=columns.ColNoL(key.iName);
sl@0: 		if (pKey->iOrdinal==KDbNullColNo)
sl@0: 			__LEAVE(KErrNotFound);
sl@0: 		const TDbColumnDef& col=columns[pKey->iOrdinal];
sl@0: 		switch (pKey->iType=col.iType)
sl@0: 			{
sl@0: 		default:
sl@0: 			break;
sl@0: 		case EDbColText8:
sl@0: 		case EDbColText16:
sl@0: 			{
sl@0: 			TInt l=col.iMaxLength;
sl@0: 			if (l<256)
sl@0: 				{
sl@0: 				pKey->iLength=TUint8(l);
sl@0: 				break;
sl@0: 				}
sl@0: 			}
sl@0: 			// fall through to argument error
sl@0: 		case EDbColBinary:
sl@0: 		case EDbColLongBinary:
sl@0: 			__LEAVE(KErrArgument);
sl@0: 			}
sl@0: 		}
sl@0: 	CleanupStack::Pop();
sl@0: 	return self;
sl@0: 	}
sl@0: 
sl@0: TInt CDbOrderByStage::HOrdering::MaxSize() const
sl@0: 	{
sl@0: 	TInt maxsize=0;
sl@0: 	const TKeyCol* const end=iEndOfKeys;
sl@0: 	const TKeyCol* key=&iKeys[0];
sl@0: 	__ASSERT(key<end);
sl@0: 	do	{
sl@0: 		TInt s;
sl@0: 		switch (key->iType)
sl@0: 			{
sl@0: 		default:
sl@0: 			s=sizeof(TUint32);
sl@0: 			break;
sl@0: 		case EDbColInt64:
sl@0: 			s=sizeof(TInt64);
sl@0: 			break;
sl@0: 		case EDbColDateTime:
sl@0: 			s=sizeof(TTime);
sl@0: 			break;
sl@0: 		case EDbColReal64:
sl@0: 			s=sizeof(TReal64);
sl@0: 			break;
sl@0: 		case EDbColText8:
sl@0: 			s=Align4(key->iLength+1);
sl@0: 			break;
sl@0: 		case EDbColText16:
sl@0: 			s=Align4((key->iLength<<1)+1);
sl@0: 			break;
sl@0: 		case EDbColLongText8:
sl@0: 		case EDbColLongText16:
sl@0: 			s=MAX(__Align8(sizeof(TUint32)+KDbMaxInlineBlobSize),sizeof(TBlobKey));
sl@0: 			break;
sl@0: 			}
sl@0: 		maxsize+=s;
sl@0: 		} while (++key<end);
sl@0: 	return maxsize;
sl@0: 	}
sl@0: 
sl@0: MStreamBuf* CDbOrderByStage::HOrdering::BlobLC(TDbBlobId aId,TDbColType aType) const
sl@0: 	{
sl@0: 	return iTable.BlobsL()->ReadLC(aId,aType);
sl@0: 	}
sl@0: 
sl@0: //
sl@0: // Construct an entry at aPtr from the record given
sl@0: // iMaxSize bytes are assumed to be available at aPtr
sl@0: // return the actual size of the entry
sl@0: //
sl@0: TAny* CDbOrderByStage::HOrdering::EntryL(TAny* aPtr,const RDbTableRow& aRow) const
sl@0: 	{
sl@0: 	__ASSERT(Align4(aPtr)==aPtr);
sl@0: 	TUint32* ptr=(TUint32*)aPtr;		// 32-bit words are nice
sl@0: 	const TKeyCol* const end=iEndOfKeys;
sl@0: 	const TKeyCol* key=iKeys;
sl@0: 	__ASSERT(key<end);
sl@0: 	do	{
sl@0: 		const TDbCell* cell=aRow.ColCell(key->iOrdinal);
sl@0: 		TDbColType type=TDbColType(key->iType);
sl@0: 		if (cell->Length()==0)
sl@0: 			{	// null column
sl@0: 			const TUint K64BitColumnMask=(1u<<EDbColInt64)|(1u<<EDbColReal64)|(1u<<EDbColDateTime);
sl@0: 			*ptr++=0;
sl@0: 			if (K64BitColumnMask&(1u<<type))
sl@0: 				*ptr++=0;		// 8-byte column
sl@0: 			continue;
sl@0: 			}
sl@0: 		switch (type)
sl@0: 			{
sl@0: 		default:
sl@0: 			__ASSERT(0);
sl@0: 		case EDbColBit:
sl@0: 		case EDbColUint8:
sl@0: 		case EDbColUint16:
sl@0: 		case EDbColUint32:
sl@0: 		case EDbColInt8:
sl@0: 		case EDbColInt16:
sl@0: 		case EDbColInt32:
sl@0: 		case EDbColReal32:
sl@0: 			*ptr++=*(const TUint32*)cell->Data();
sl@0: 			break;
sl@0: 		case EDbColInt64:
sl@0: 		case EDbColDateTime:
sl@0: 		case EDbColReal64:
sl@0: 			{
sl@0: 			const TUint32* data=(const TUint32*)cell->Data();
sl@0: 			*ptr++=*data++;
sl@0: 			*ptr++=*data;
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColText8:
sl@0: 			{
sl@0: 			TInt size=cell->Length();
sl@0: 			*(TUint8*)ptr=TUint8(size);
sl@0: 			ptr=(TUint32*)Align4(Mem::Copy(PtrAdd(ptr,1),cell->Data(),size));
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColText16:
sl@0: 			{
sl@0: 			TInt size=cell->Length();
sl@0: 			*(TUint16*)ptr=TUint16(size>>1);
sl@0: 			ptr=(TUint32*)Align4(Mem::Copy(PtrAdd(ptr,2),cell->Data(),size));
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColLongText8:
sl@0: 		case EDbColLongText16:
sl@0: 			{
sl@0: 			const TDbBlob& blob=*(const TDbBlob*)cell->Data();
sl@0: 			TInt size=blob.Size();
sl@0: 			if (blob.IsInline())
sl@0: 				{
sl@0: 				*ptr++=size;
sl@0: 				ptr=(TUint32*)Align4(Mem::Copy(ptr,blob.Data(),size));
sl@0: 				}
sl@0: 			else
sl@0: 				{
sl@0: 				TInt rsize=size;
sl@0: 				if (size>TBlobKey::ETruncSize)
sl@0: 					{
sl@0: 					size|=TBlobKey::ETrunc;
sl@0: 					rsize=TBlobKey::ETruncSize;
sl@0: 					}
sl@0: 				*ptr++=size;
sl@0: 				BlobLC(blob.Id(),TDbColType(key->iType))->ReadL(ptr,rsize);
sl@0: 				CleanupStack::PopAndDestroy();
sl@0: 				ptr=Align4(PtrAdd(ptr,rsize));
sl@0: 				if (size&TBlobKey::ETrunc)
sl@0: 					*ptr++=blob.Id();
sl@0: 				}
sl@0: 			}
sl@0: 			break;
sl@0: 			}
sl@0: 		} while (++key<end);
sl@0: 	return ptr;
sl@0: 	}
sl@0: 
sl@0: TInt CDbOrderByStage::HOrdering::CompareLongText8L( const CDbOrderByStage::HOrdering::TBlobKey& aLeft, const CDbOrderByStage::HOrdering::TBlobKey& aRight ) const
sl@0: 	{
sl@0: 	TUint sizel = aLeft.iSize;
sl@0: 	TUint sizer = aRight.iSize;
sl@0: 	TUint s = sizel;
sl@0: 	if ( sizer < s )
sl@0: 		s = sizer;
sl@0: 	if ( s > static_cast<TUint>( TBlobKey::ETruncSize ) && ( ( sizel | sizer ) & static_cast<TUint>( TBlobKey::ETrunc ) ) )
sl@0: 		s = TBlobKey::ETruncSize;
sl@0: 	TInt rr = iTextOps.Compare( aLeft.iData8, s, aRight.iData8, s );
sl@0: 	if ( rr )
sl@0: 		return rr;
sl@0: //
sl@0: // matches up to the same-length inlined data...
sl@0: // now it gets interesting
sl@0: //
sl@0: 	if ( ( ( sizel | sizer ) & static_cast<TUint>( TBlobKey::ETrunc ) ) == 0 )
sl@0: 		return sizel - sizer;		// neither are truncated
sl@0: 	if ( s == sizel )
sl@0: 		return -1;		// left completely match against truncated right
sl@0: 	if ( s == sizer )
sl@0: 		return 1;		// right completely matched against truncated left
sl@0: 
sl@0: 	s = Min( TInt( sizel & ~TBlobKey::ETrunc ), TInt( sizer & ~TBlobKey::ETrunc ) );		// minimum real length
sl@0: 	if ( sizel & static_cast<TUint>( TBlobKey::ETrunc ) )
sl@0: 		{
sl@0: 		MStreamBuf& bufL = *BlobLC( aLeft.iId, EDbColLongText8 );
sl@0: 		if ( sizer & static_cast<TUint>( TBlobKey::ETrunc ) )
sl@0: 			{	// both out-of-line
sl@0: 			rr = Comp::Compare8L( bufL, *BlobLC( aRight.iId, EDbColLongText8 ), s, iTextOps );
sl@0: 			CleanupStack::PopAndDestroy();
sl@0: 			}
sl@0: 		else	// left side only out-of-line
sl@0: 			rr = Comp::Compare8L( bufL, aRight.iData8, s, iTextOps );
sl@0: 		}
sl@0: 	else
sl@0: 		{	// right side only out-of-line
sl@0: 		__ASSERT( sizer & static_cast<TUint>( TBlobKey::ETrunc ) );
sl@0: 		rr = -Comp::Compare8L( *BlobLC( aRight.iId, EDbColLongText8 ), aLeft.iData8, s, iTextOps );
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy();
sl@0: 	return rr ? rr : ( sizel & ~TBlobKey::ETrunc ) - ( sizer & ~TBlobKey::ETrunc );
sl@0: 	}
sl@0: 
sl@0: TInt CDbOrderByStage::HOrdering::CompareLongText16L( const CDbOrderByStage::HOrdering::TBlobKey& aLeft, const CDbOrderByStage::HOrdering::TBlobKey& aRight ) const
sl@0: 	{
sl@0: 	TUint sizeL = aLeft.iSize  & ~TBlobKey::ETrunc; // set truncation bit to 0 to get true size
sl@0: 	TUint sizeR = aRight.iSize & ~TBlobKey::ETrunc;
sl@0: 	TBool truncL = aLeft.iSize  & TBlobKey::ETrunc; // data is truncated if TBlobKey::ETrunc bit is 1
sl@0: 	TBool truncR = aRight.iSize & TBlobKey::ETrunc;
sl@0: 	
sl@0: 	if (!(truncL | truncR)) // neither side is truncated, compare full strings
sl@0: 		{		
sl@0: 		return iTextOps.Order( aLeft.iData16, sizeL>>1, aRight.iData16, sizeR>>1 );
sl@0: 		}
sl@0: 		
sl@0: 	TInt result;
sl@0: 	TUint sizeMin = Min( TInt(sizeL), TInt(sizeR) ); // minimum real length
sl@0: 	if ( truncL )
sl@0: 		{
sl@0: 		MStreamBuf& bufL = *BlobLC( aLeft.iId, EDbColLongText16 );
sl@0: 		if ( truncR )
sl@0: 			{	// both out-of-line
sl@0: 			result = Comp::Compare16L( bufL, *BlobLC( aRight.iId, EDbColLongText16 ), sizeMin, iTextOps );
sl@0: 			CleanupStack::PopAndDestroy();
sl@0: 			}
sl@0: 		else	// left side only out-of-line
sl@0: 			result = Comp::Compare16L( bufL, aRight.iData16, sizeMin, iTextOps );
sl@0: 		}
sl@0: 	else
sl@0: 		{	// right side only out-of-line
sl@0: 		__ASSERT( truncR );
sl@0: 		result = -Comp::Compare16L( *BlobLC( aRight.iId, EDbColLongText16 ), aLeft.iData16, sizeMin, iTextOps );
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy();
sl@0: 	return result ? result : ( sizeL ) - ( sizeR );
sl@0: 	}
sl@0: 
sl@0: TInt CDbOrderByStage::HOrdering::CompareL(const TAny* aLeft,const TAny* aRight) const
sl@0: //
sl@0: // compare the keys
sl@0: //
sl@0: 	{
sl@0: 	const TUint8* left=(const TUint8*)aLeft;
sl@0: 	const TUint8* right=(const TUint8*)aRight;
sl@0: 	const TKeyCol* end=iEndOfKeys;
sl@0: 	const TKeyCol* key=&iKeys[0];
sl@0: 	TInt rr;
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		switch (key->iType)
sl@0: 			{
sl@0: 		default:
sl@0: 			__ASSERT(0);
sl@0: 		case EDbColBit:
sl@0: 		case EDbColUint8:
sl@0: 		case EDbColUint16:
sl@0: 		case EDbColUint32:
sl@0: 			rr=Comp::Compare(*(const TUint32*)left,*(const TUint32*)right);
sl@0: 			left+=sizeof(TUint32);
sl@0: 			right+=sizeof(TUint32);
sl@0: 			break;
sl@0: 		case EDbColInt8:
sl@0: 		case EDbColInt16:
sl@0: 		case EDbColInt32:
sl@0: 			rr=Comp::Compare(*(const TInt32*)left,*(const TInt32*)right);
sl@0: 			left+=sizeof(TInt32);
sl@0: 			right+=sizeof(TInt32);
sl@0: 			break;
sl@0: 		case EDbColInt64:
sl@0: 			rr=Comp::Compare(*(const TInt64*)left,*(const TInt64*)right);
sl@0: 			left+=sizeof(TInt64);
sl@0: 			right+=sizeof(TInt64);
sl@0: 			break;
sl@0: 		case EDbColDateTime:
sl@0: 			rr=Comp::Compare(*(const TTime*)left,*(const TTime*)right);
sl@0: 			left+=sizeof(TTime);
sl@0: 			right+=sizeof(TTime);
sl@0: 			break;
sl@0: 		case EDbColReal32:
sl@0: 			rr=Comp::Compare(*(const TReal32*)left,*(const TReal32*)right);
sl@0: 			left+=sizeof(TReal32);
sl@0: 			right+=sizeof(TReal32);
sl@0: 			break;
sl@0: 		case EDbColReal64:
sl@0: 			rr=Comp::Compare(*(const TReal64*)left,*(const TReal64*)right);
sl@0: 			left+=sizeof(TReal64);
sl@0: 			right+=sizeof(TReal64);
sl@0: 			break;
sl@0: 		case EDbColText8:
sl@0: 			{
sl@0: 			TInt sizel=*left++;
sl@0: 			TInt sizer=*right++;
sl@0: 			rr=iTextOps.Compare(left,sizel,right,sizer);
sl@0: 			left=Align4(left+sizel);
sl@0: 			right=Align4(right+sizer);
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColText16:
sl@0: 			{
sl@0: 			const TUint16* l16=reinterpret_cast<const TUint16*>(left);
sl@0: 			const TUint16* r16=reinterpret_cast<const TUint16*>(right);
sl@0: 			TInt sizel=*l16++;
sl@0: 			TInt sizer=*r16++;
sl@0: 			rr=iTextOps.Order(l16,sizel,r16,sizer);
sl@0: 			left=Align4(reinterpret_cast<const TUint8*>(l16+sizel));
sl@0: 			right=Align4(reinterpret_cast<const TUint8*>(r16+sizer));
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColLongText8:
sl@0: 			{
sl@0: 			const TBlobKey* ltext=(const TBlobKey*)left;
sl@0: 			const TBlobKey* rtext=(const TBlobKey*)right;
sl@0: 			rr=CompareLongText8L(*ltext,*rtext);
sl@0: 			left+=ltext->Size();
sl@0: 			right+=rtext->Size();
sl@0: 			}
sl@0: 			break;
sl@0: 		case EDbColLongText16:
sl@0: 			{
sl@0: 			const TBlobKey* ltext=(const TBlobKey*)left;
sl@0: 			const TBlobKey* rtext=(const TBlobKey*)right;
sl@0: 			rr=CompareLongText16L(*ltext,*rtext);
sl@0: 			left+=ltext->Size();
sl@0: 			right+=rtext->Size();
sl@0: 			}
sl@0: 			break;
sl@0: 			}
sl@0: 		if (rr!=0)
sl@0: 			break;
sl@0: 		if (++key==end)
sl@0: 			break;
sl@0: 		}
sl@0: 	return key->iOrder==TDbKeyCol::EAsc ? rr : -rr;
sl@0: 	}
sl@0: 
sl@0: //
sl@0: 
sl@0: NONSHARABLE_CLASS(CDbOrderByStage::CKeys) : public CBase
sl@0: 	{
sl@0: public:		// should be private but VC++ 4.0 whinges
sl@0: 	struct TKey
sl@0: 		{
sl@0: 		TUint32 iId;
sl@0: 		TUint8 iKey[4];		// and then some
sl@0: 		};
sl@0: private:
sl@0: 	enum {EKeysGranularity=32};
sl@0: 	struct TPage
sl@0: 		{
sl@0: 		TPage* iNext;
sl@0: 		TKey iEntries[1];
sl@0: 		};
sl@0: 	enum {EMinPageSize=0x200,EMinKeyElements=2};
sl@0: public:
sl@0: 	CKeys(TInt aMaxKeySize);
sl@0: 	~CKeys();
sl@0: //
sl@0: 	void AddL(TDbRecordId aRecordId,const RDbTableRow& aRow,const HOrdering& aOrder);
sl@0: 	void SortL(const HOrdering& aOrder);
sl@0: 	void GetRecordsL(CArrayFix<TDbRecordId>& aRecords);
sl@0: #ifdef _CHECK_ORDERING
sl@0: 	void VerifyOrderingL(const HOrdering& aOrder);
sl@0: #endif
sl@0: private:
sl@0: 	void SortL(TKey* aData[],TInt aElem,const HOrdering& aOrder);
sl@0: 	TKey& NewKeyL();
sl@0: 	void KeyComplete(TAny* aEnd);
sl@0: 	void Release();
sl@0: private:
sl@0: 	RPointerArray<TKey> iKeys;
sl@0: 	TInt iMaxKeySize;
sl@0: 	TInt iPageSize;
sl@0: 	TPage* iPages;
sl@0: 	TKey* iNext;
sl@0: 	TKey* iEnd;
sl@0: 	};
sl@0: 
sl@0: // Class CDbOrderByStage::CKeys
sl@0: 
sl@0: CDbOrderByStage::CKeys::CKeys(TInt aMaxKeySize)
sl@0: 	:iKeys(EKeysGranularity),iMaxKeySize(_FOFF(TKey,iKey[aMaxKeySize])),
sl@0: 	 iPageSize(Max(EMinPageSize+iMaxKeySize,iMaxKeySize*EMinKeyElements))
sl@0: 	{}
sl@0: 
sl@0: CDbOrderByStage::CKeys::~CKeys()
sl@0: 	{
sl@0: 	iKeys.Close();
sl@0: 	Release();
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::SortL(CDbOrderByStage::CKeys::TKey* aData[],TInt aElem,const HOrdering& aOrder)
sl@0: //
sl@0: // Sort the array of row keys
sl@0: // Uses Heap-sort
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT(aElem>1);
sl@0: 	TInt heap=aElem>>1;
sl@0: 	--aElem;
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		TKey* key;
sl@0: 		if (heap!=0)
sl@0: 			key=aData[--heap];
sl@0: 		else
sl@0: 			{
sl@0: 			key=aData[aElem];
sl@0: 			aData[aElem]=aData[0];
sl@0: 			if (--aElem==0)
sl@0: 				{
sl@0: 				aData[0]=key;
sl@0: 				break;
sl@0: 				}
sl@0: 			}
sl@0: 		TInt ix=heap;
sl@0: 		TInt parent;
sl@0: 		for (parent=ix;;parent=ix)
sl@0: 			{
sl@0: 			ix=(ix<<1)+1;
sl@0: 			if (ix<=aElem)
sl@0: 				{
sl@0: 				if (ix<aElem && aOrder.CompareL(aData[ix]->iKey,aData[ix+1]->iKey)<0)
sl@0: 					++ix;
sl@0: 				}
sl@0: 			else
sl@0: 				break;
sl@0: 			if (aOrder.CompareL(aData[ix]->iKey,key->iKey)<=0)
sl@0: 				break;
sl@0: 			aData[parent]=aData[ix];
sl@0: 			}
sl@0: 		aData[parent]=key;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::AddL(TDbRecordId aRecordId,const RDbTableRow& aRow,const HOrdering& aOrder)
sl@0: //
sl@0: // Create a key for the row and store it
sl@0: //
sl@0: 	{
sl@0: 	TKey& key=NewKeyL();
sl@0: 	key.iId=aRecordId.Value();
sl@0: 	TAny* end=aOrder.EntryL(&key.iKey[0],aRow);
sl@0: 	__LEAVE_IF_ERROR(iKeys.Append(&key));
sl@0: 	KeyComplete(end);
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::SortL(const HOrdering& aOrder)
sl@0: 	{
sl@0: 	TInt elem=iKeys.Count();
sl@0: 	if (elem>1)
sl@0: 		SortL(&iKeys[0],elem,aOrder);
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::GetRecordsL(CArrayFix<TDbRecordId>& aRecords)
sl@0: 	{
sl@0: 	TInt elem=iKeys.Count();
sl@0: 	if (elem==0)
sl@0: 		return;
sl@0: 	TKey** const base=&iKeys[0];
sl@0: 	TKey** ptr=base+elem;
sl@0: 	do	{
sl@0: 		--ptr;
sl@0: 		*REINTERPRET_CAST(TDbRecordId*,ptr)=(*ptr)->iId;
sl@0: 		} while (ptr>base);
sl@0: 	Release();		// discard key memory before adding records
sl@0: 	aRecords.InsertL(0,REINTERPRET_CAST(const TDbRecordId*,base),elem);
sl@0: 	iKeys.Reset();
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::Release()
sl@0: //
sl@0: // Discard all of the allocated pages
sl@0: //
sl@0: 	{
sl@0: 	TPage* p=iPages;
sl@0: 	while (p)
sl@0: 		{
sl@0: 		TPage* n=p->iNext;
sl@0: 		User::Free(p);
sl@0: 		p=n;
sl@0: 		}
sl@0: 	iPages=0;
sl@0: 	iNext=iEnd=0;
sl@0: 	}
sl@0: 
sl@0: CDbOrderByStage::CKeys::TKey& CDbOrderByStage::CKeys::NewKeyL()
sl@0: //
sl@0: // Allocate a key entry for the raw key data
sl@0: //
sl@0: 	{
sl@0: 	TKey* p=iNext;
sl@0: 	if (PtrAdd(p,iMaxKeySize)>iEnd)
sl@0: 		{	// not enough space for a maximum key
sl@0: 		TPage* page=iPages;
sl@0: 		if (page)
sl@0: 			{	// compress the current page
sl@0: 			__DEBUG(page=(TPage*))User::ReAlloc(page,(TUint8*)iNext-(TUint8*)page);
sl@0: 			__ASSERT(page==iPages);		// if it moves we are dead
sl@0: 			}
sl@0: 		page=(TPage*)User::AllocL(_FOFF(TPage,iEntries)+iPageSize);
sl@0: 		page->iNext=iPages;
sl@0: 		iPages=page;
sl@0: 		p=iNext=&page->iEntries[0];
sl@0: 		iEnd=PtrAdd(p,iPageSize);
sl@0: 		}
sl@0: 	return *p;
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::CKeys::KeyComplete(TAny* aEnd)
sl@0: //
sl@0: // Key is complete, prepare for the next one
sl@0: //
sl@0: 	{
sl@0: 	__ASSERT(aEnd==Align4(aEnd));
sl@0: 	__ASSERT(iNext<=aEnd&&aEnd<=iEnd);
sl@0: 	iNext=STATIC_CAST(TKey*,aEnd);
sl@0: 	}
sl@0: 
sl@0: #ifdef _CHECK_ORDERING
sl@0: void CDbOrderByStage::CKeys::VerifyOrderingL(const HOrdering& aOrder)
sl@0: 	{
sl@0: // this performs a full O(N*N) comparison of the record set
sl@0: 	if (iKeys.Count()==0)
sl@0: 		return;
sl@0: 	TKey* const* data=&iKeys[0];
sl@0: 	for (TInt ii=iKeys.Count();--ii>=0;)
sl@0: 		{
sl@0: 		for (TInt jj=iKeys.Count();--jj>=0;)
sl@0: 			{
sl@0: 			TInt rr=aOrder.CompareL(data[ii]->iKey,data[jj]->iKey);
sl@0: 			if (ii==jj)
sl@0: 				__ASSERT_ALWAYS(rr==0,User::Invariant());
sl@0: 			else if (ii<jj)
sl@0: 				__ASSERT_ALWAYS(rr<=0,User::Invariant());
sl@0: 			else
sl@0: 				__ASSERT_ALWAYS(rr>=0,User::Invariant());
sl@0: 			}
sl@0: 		}
sl@0: 	}
sl@0: #endif
sl@0: 
sl@0: // Class CDbOrderByStage
sl@0: 
sl@0: inline const RDbTableRow& CDbOrderByStage::Row()
sl@0: 	{return iRow;}
sl@0: inline CDbOrderByStage::CKeys& CDbOrderByStage::Keys()
sl@0: 	{__ASSERT(iKeys);return *iKeys;}
sl@0: inline const CDbOrderByStage::HOrdering& CDbOrderByStage::Order()
sl@0: 	{__ASSERT(iOrder);return *iOrder;}
sl@0: 
sl@0: CDbOrderByStage::CDbOrderByStage(const RDbTableRow& aRow)
sl@0: 	: CDbBasicWindowStage(KDbUnlimitedWindow),iRow(aRow)
sl@0: 	{
sl@0: 	__ASSERT(iState==EReset);
sl@0: 	}
sl@0: 
sl@0: CDbOrderByStage::~CDbOrderByStage()
sl@0: 	{
sl@0: 	delete iOrder;
sl@0: 	delete iKeys;
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::ConstructL(const CDbKey& aOrderBy)
sl@0: //
sl@0: // Build the key structures to support the partial and complete ordering
sl@0: //
sl@0: 	{
sl@0: 	iOrder=HOrdering::NewL(Row().Table(),aOrderBy);
sl@0: 	}
sl@0: 
sl@0: void CDbOrderByStage::Reset()
sl@0: //
sl@0: // Reset the window to initial state
sl@0: //
sl@0: 	{
sl@0: 	delete iKeys;
sl@0: 	iKeys=0;
sl@0: 	iState=EReset;
sl@0: 	CDbBasicWindowStage::Reset();
sl@0: 	}
sl@0: 
sl@0: TBool CDbOrderByStage::ReadL(TInt& aWork,TDbPosition aNext)
sl@0: //
sl@0: // Read some more record keys
sl@0: //
sl@0: 	{
sl@0: 	TDbRecordId id(KDbNullRecordIdValue);
sl@0: 	TGoto r;
sl@0: 	while ((r=CDbDataStage::GotoL(aWork,aNext,id))==ESuccess)
sl@0: 		{
sl@0: 		CDbDataStage::ReadRowL(id);
sl@0: 		Keys().AddL(id,Row(),Order());
sl@0: 		aNext=EDbNext;
sl@0: 		}
sl@0: 	switch (r)
sl@0: 		{
sl@0: 	default:
sl@0: 		__ASSERT(0);
sl@0: 	case ESynchFailure:
sl@0: 		__LEAVE(KErrNotReady);
sl@0: 	case EExhausted:
sl@0: 		return ETrue;
sl@0: 	case ENoRow:
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool CDbOrderByStage::DoEvaluateL(TInt& aWork)
sl@0: //
sl@0: // Build the key collection, and finally sort it
sl@0: //
sl@0: 	{
sl@0: 	TState s=iState;
sl@0: 	iState=EFailed;
sl@0: 	switch (s)
sl@0: 		{
sl@0: 	default:
sl@0: 		__ASSERT(0);
sl@0: 	case EFailed:
sl@0: 		__LEAVE(KErrNotReady);
sl@0: 	case EReset:
sl@0: 		__ASSERT(!iKeys);
sl@0: 		iKeys=new(ELeave) CKeys(Order().MaxSize());
sl@0: 		// drop through to EEvaluate
sl@0: 	case EEvaluate:
sl@0: 		if (ReadL(aWork,s==EReset ? EDbFirst : EDbNext))
sl@0: 			{
sl@0: 			iState=EEvaluate;
sl@0: 			return ETrue;
sl@0: 			}
sl@0: 		// drop through to ESort
sl@0: 	case ESort:
sl@0: 		Keys().SortL(Order());
sl@0: #ifdef _CHECK_ORDERING
sl@0: 		Keys().VerifyOrderingL(Order());
sl@0: #endif
sl@0: 		// drop through to EAdd
sl@0: 	case EAdd:
sl@0: 		Keys().GetRecordsL(iRecords);
sl@0: 		delete iKeys;
sl@0: 		iKeys=0;
sl@0: 		// drop through to EComplete
sl@0: 	case EComplete:
sl@0: 		iState=EComplete;
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool CDbOrderByStage::Unevaluated()
sl@0: //
sl@0: // Return whether it is worth Evaluating
sl@0: //
sl@0: 	{
sl@0: 	if (iState==EComplete)
sl@0: 		return CDbDataStage::Unevaluated();
sl@0: 	return iState!=EFailed;
sl@0: 	}
sl@0: 
sl@0: 
sl@0: // Class CDbReorderWindowStage
sl@0: 
sl@0: CDbReorderWindowStage::CDbReorderWindowStage()
sl@0: 	: CDbBasicWindowStage(KDbUnlimitedWindow),iRows(EGranularity)
sl@0: 	{
sl@0: 	__ASSERT(iState==EReset);
sl@0: 	}
sl@0: 
sl@0: CDbReorderWindowStage::~CDbReorderWindowStage()
sl@0: 	{
sl@0: 	iRows.Close();
sl@0: 	}
sl@0: 
sl@0: void CDbReorderWindowStage::Reset()
sl@0: //
sl@0: // Reset the window to initial state
sl@0: //
sl@0: 	{
sl@0: 	iRows.Reset();
sl@0: 	iState=EReset;
sl@0: 	CDbBasicWindowStage::Reset();
sl@0: 	}
sl@0: 
sl@0: TBool CDbReorderWindowStage::ReadL(TInt& aWork,TDbPosition aNext)
sl@0: //
sl@0: // Read some more row ids
sl@0: //
sl@0: 	{
sl@0: 	TDbRecordId id(KDbNullRecordIdValue);
sl@0: 	TGoto r;
sl@0: 	while ((r=CDbDataStage::GotoL(aWork,aNext,id))==ESuccess)
sl@0: 		{
sl@0: 		__LEAVE_IF_ERROR(iRows.Append(id.Value()));
sl@0: 		aNext=EDbNext;
sl@0: 		}
sl@0: 	switch (r)
sl@0: 		{
sl@0: 	default:
sl@0: 		__ASSERT(0);
sl@0: 	case ESynchFailure:
sl@0: 		__LEAVE(KErrNotReady);
sl@0: 	case EExhausted:
sl@0: 		return ETrue;
sl@0: 	case ENoRow:
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool CDbReorderWindowStage::DoEvaluateL(TInt& aWork)
sl@0: //
sl@0: // Build the key collection, and finally sort it
sl@0: //
sl@0: 	{
sl@0: 	TState s=iState;
sl@0: 	iState=EFailed;
sl@0: 	switch (s)
sl@0: 		{
sl@0: 	default:
sl@0: 		__ASSERT(0);
sl@0: 	case EFailed:
sl@0: 		__LEAVE(KErrNotReady);
sl@0: 	case EReset:
sl@0: 	case EEvaluate:
sl@0: 		if (ReadL(aWork,s==EReset ? EDbFirst : EDbNext))
sl@0: 			{
sl@0: 			iState=EEvaluate;
sl@0: 			return ETrue;
sl@0: 			}
sl@0: 		if (iRows.Count())
sl@0: 			{
sl@0: 			iRows.Sort();
sl@0: 			iRecords.AppendL((const TDbRecordId*)&iRows[0],iRows.Count());
sl@0: 			iRows.Reset();
sl@0: 			}
sl@0: 	case EComplete:
sl@0: 		iState=EComplete;
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TBool CDbReorderWindowStage::Unevaluated()
sl@0: //
sl@0: // Return whether it is worth Evaluating
sl@0: //
sl@0: 	{
sl@0: 	if (iState==EComplete)
sl@0: 		return CDbDataStage::Unevaluated();
sl@0: 	return iState!=EFailed;
sl@0: 	}
sl@0: