1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/dbms/pcdbms/utable/UT_ORDER.CPP Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,871 @@
1.4 +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// Order-by stage for the cursor data "pipeline"
1.18 +//
1.19 +//
1.20 +
1.21 +#include "UT_STD.H"
1.22 +#include "D32COMP.H"
1.23 +
1.24 +#ifdef _DEBUG
1.25 +#define _CHECK_ORDERING // forces a full test of the ordering after sorting
1.26 +#endif
1.27 +
1.28 +#define MAX( a, b ) ( (a) > (b) ? (a) : (b) )
1.29 +
1.30 +/* The key structure.
1.31 +
1.32 +Each key value is always aligned on a 32-bit boundary to allow word reads and writes
1.33 +integral values are always atored as 32-bit values just as for the row buffer
1.34 +Text columns are encoded as follows (trailing padding is omitted from the description)
1.35 +
1.36 + Text8 columns <byte n><n ASCII characters>
1.37 + n is the [character] length of the column
1.38 +
1.39 + Text16 columns <short n><n UNICODE characters>
1.40 + n is the [character] length of the column
1.41 +
1.42 + LongText8 columns <word n><n ASCII characters>
1.43 + or <word n|ETrunc><32 ASCII characters><blobId>
1.44 + n is [byte] size of the column
1.45 +
1.46 + LongText16 columns <word n><n/2 UNICODE characters>
1.47 + or <word n|ETrunc><16 UNICODE characters><blobId>
1.48 + n is [byte] size of the column
1.49 +
1.50 +*/
1.51 +
1.52 +
1.53 +class CDbOrderByStage::HOrdering
1.54 + {
1.55 +private:
1.56 + struct TKeyCol
1.57 + {
1.58 + TDbColNo iOrdinal;
1.59 + TUint8 iType;
1.60 + TUint8 iOrder;
1.61 + TUint8 iLength;
1.62 + };
1.63 + struct TBlobKey
1.64 + {
1.65 + enum {ETrunc=(TInt)0x80000000};
1.66 + enum {ETruncSize=32}; // store 32 bytes of truncated BLOBs
1.67 + public:
1.68 + inline TInt Size() const;
1.69 + public:
1.70 + TInt iSize;
1.71 + union {TUint8 iData8[ETruncSize]; TUint16 iData16[ETruncSize>>1];};
1.72 + TDbBlobId iId;
1.73 + };
1.74 +public:
1.75 + static HOrdering* NewL(CDbTable& aTable,const CDbKey& aKey);
1.76 + TAny* EntryL(TAny* aPtr,const RDbTableRow& aRow) const;
1.77 + TInt CompareL(const TAny* aLeft,const TAny* aRight) const;
1.78 + TInt MaxSize() const;
1.79 +private:
1.80 + inline HOrdering(TInt aCount,TDbTextComparison aComparison,CDbTable& aTable);
1.81 + MStreamBuf* BlobLC(TDbBlobId aId,TDbColType aType) const;
1.82 + TInt CompareLongText8L(const TBlobKey& aLeft,const TBlobKey& aRight) const;
1.83 + TInt CompareLongText16L(const TBlobKey& aLeft,const TBlobKey& aRight) const;
1.84 +private:
1.85 + CDbTable& iTable;
1.86 + const TTextOps& iTextOps;
1.87 + const TKeyCol* iEndOfKeys;
1.88 + TKeyCol iKeys[1]; // one or more keys
1.89 + };
1.90 +
1.91 +// Class HDbOrdering
1.92 +
1.93 +inline TInt CDbOrderByStage::HOrdering::TBlobKey::Size() const
1.94 + {
1.95 + TInt size=_FOFF(TBlobKey,iData8[iSize+3]);
1.96 + return (size&ETrunc) ? sizeof(TBlobKey) : size&~3;
1.97 + }
1.98 +
1.99 +inline CDbOrderByStage::HOrdering::HOrdering(TInt aCount,TDbTextComparison aComparison,CDbTable& aTable) :
1.100 + iTable(aTable),
1.101 + iTextOps(TTextOps::Ops(aComparison)),
1.102 + iEndOfKeys(&iKeys[aCount])
1.103 + {
1.104 + }
1.105 +
1.106 +//
1.107 +// Construct the ordering based on the key definition (must be valid for the table)
1.108 +// and the column set provided
1.109 +//
1.110 +CDbOrderByStage::HOrdering* CDbOrderByStage::HOrdering::NewL(CDbTable& aTable,const CDbKey& aKey)
1.111 + {
1.112 + TInt count=aKey.Count();
1.113 + __ASSERT(count>0);
1.114 + HOrdering* self=new(User::AllocLC(_FOFF(HOrdering,iKeys[count])))
1.115 + HOrdering(count,aKey.Comparison(),aTable);
1.116 + TKeyCol* pKey=&self->iKeys[0];
1.117 + const HDbColumnSet& columns=aTable.Def().Columns();
1.118 + for (TInt ii=0;ii<count;++pKey,++ii)
1.119 + {
1.120 + const TDbKeyCol& key=aKey[ii];
1.121 + pKey->iOrder=TUint8(key.iOrder);
1.122 + pKey->iOrdinal=columns.ColNoL(key.iName);
1.123 + if (pKey->iOrdinal==KDbNullColNo)
1.124 + __LEAVE(KErrNotFound);
1.125 + const TDbColumnDef& col=columns[pKey->iOrdinal];
1.126 + switch (pKey->iType=col.iType)
1.127 + {
1.128 + default:
1.129 + break;
1.130 + case EDbColText8:
1.131 + case EDbColText16:
1.132 + {
1.133 + TInt l=col.iMaxLength;
1.134 + if (l<256)
1.135 + {
1.136 + pKey->iLength=TUint8(l);
1.137 + break;
1.138 + }
1.139 + }
1.140 + // fall through to argument error
1.141 + case EDbColBinary:
1.142 + case EDbColLongBinary:
1.143 + __LEAVE(KErrArgument);
1.144 + }
1.145 + }
1.146 + CleanupStack::Pop();
1.147 + return self;
1.148 + }
1.149 +
1.150 +TInt CDbOrderByStage::HOrdering::MaxSize() const
1.151 + {
1.152 + TInt maxsize=0;
1.153 + const TKeyCol* const end=iEndOfKeys;
1.154 + const TKeyCol* key=&iKeys[0];
1.155 + __ASSERT(key<end);
1.156 + do {
1.157 + TInt s;
1.158 + switch (key->iType)
1.159 + {
1.160 + default:
1.161 + s=sizeof(TUint32);
1.162 + break;
1.163 + case EDbColInt64:
1.164 + s=sizeof(TInt64);
1.165 + break;
1.166 + case EDbColDateTime:
1.167 + s=sizeof(TTime);
1.168 + break;
1.169 + case EDbColReal64:
1.170 + s=sizeof(TReal64);
1.171 + break;
1.172 + case EDbColText8:
1.173 + s=Align4(key->iLength+1);
1.174 + break;
1.175 + case EDbColText16:
1.176 + s=Align4((key->iLength<<1)+1);
1.177 + break;
1.178 + case EDbColLongText8:
1.179 + case EDbColLongText16:
1.180 + s=MAX(__Align8(sizeof(TUint32)+KDbMaxInlineBlobSize),sizeof(TBlobKey));
1.181 + break;
1.182 + }
1.183 + maxsize+=s;
1.184 + } while (++key<end);
1.185 + return maxsize;
1.186 + }
1.187 +
1.188 +MStreamBuf* CDbOrderByStage::HOrdering::BlobLC(TDbBlobId aId,TDbColType aType) const
1.189 + {
1.190 + return iTable.BlobsL()->ReadLC(aId,aType);
1.191 + }
1.192 +
1.193 +//
1.194 +// Construct an entry at aPtr from the record given
1.195 +// iMaxSize bytes are assumed to be available at aPtr
1.196 +// return the actual size of the entry
1.197 +//
1.198 +TAny* CDbOrderByStage::HOrdering::EntryL(TAny* aPtr,const RDbTableRow& aRow) const
1.199 + {
1.200 + __ASSERT(Align4(aPtr)==aPtr);
1.201 + TUint32* ptr=(TUint32*)aPtr; // 32-bit words are nice
1.202 + const TKeyCol* const end=iEndOfKeys;
1.203 + const TKeyCol* key=iKeys;
1.204 + __ASSERT(key<end);
1.205 + do {
1.206 + const TDbCell* cell=aRow.ColCell(key->iOrdinal);
1.207 + TDbColType type=TDbColType(key->iType);
1.208 + if (cell->Length()==0)
1.209 + { // null column
1.210 + const TUint K64BitColumnMask=(1u<<EDbColInt64)|(1u<<EDbColReal64)|(1u<<EDbColDateTime);
1.211 + *ptr++=0;
1.212 + if (K64BitColumnMask&(1u<<type))
1.213 + *ptr++=0; // 8-byte column
1.214 + continue;
1.215 + }
1.216 + switch (type)
1.217 + {
1.218 + default:
1.219 + __ASSERT(0);
1.220 + case EDbColBit:
1.221 + case EDbColUint8:
1.222 + case EDbColUint16:
1.223 + case EDbColUint32:
1.224 + case EDbColInt8:
1.225 + case EDbColInt16:
1.226 + case EDbColInt32:
1.227 + case EDbColReal32:
1.228 + *ptr++=*(const TUint32*)cell->Data();
1.229 + break;
1.230 + case EDbColInt64:
1.231 + case EDbColDateTime:
1.232 + case EDbColReal64:
1.233 + {
1.234 + const TUint32* data=(const TUint32*)cell->Data();
1.235 + *ptr++=*data++;
1.236 + *ptr++=*data;
1.237 + }
1.238 + break;
1.239 + case EDbColText8:
1.240 + {
1.241 + TInt size=cell->Length();
1.242 + *(TUint8*)ptr=TUint8(size);
1.243 + ptr=(TUint32*)Align4(Mem::Copy(PtrAdd(ptr,1),cell->Data(),size));
1.244 + }
1.245 + break;
1.246 + case EDbColText16:
1.247 + {
1.248 + TInt size=cell->Length();
1.249 + *(TUint16*)ptr=TUint16(size>>1);
1.250 + ptr=(TUint32*)Align4(Mem::Copy(PtrAdd(ptr,2),cell->Data(),size));
1.251 + }
1.252 + break;
1.253 + case EDbColLongText8:
1.254 + case EDbColLongText16:
1.255 + {
1.256 + const TDbBlob& blob=*(const TDbBlob*)cell->Data();
1.257 + TInt size=blob.Size();
1.258 + if (blob.IsInline())
1.259 + {
1.260 + *ptr++=size;
1.261 + ptr=(TUint32*)Align4(Mem::Copy(ptr,blob.Data(),size));
1.262 + }
1.263 + else
1.264 + {
1.265 + TInt rsize=size;
1.266 + if (size>TBlobKey::ETruncSize)
1.267 + {
1.268 + size|=TBlobKey::ETrunc;
1.269 + rsize=TBlobKey::ETruncSize;
1.270 + }
1.271 + *ptr++=size;
1.272 + BlobLC(blob.Id(),TDbColType(key->iType))->ReadL(ptr,rsize);
1.273 + CleanupStack::PopAndDestroy();
1.274 + ptr=Align4(PtrAdd(ptr,rsize));
1.275 + if (size&TBlobKey::ETrunc)
1.276 + *ptr++=blob.Id();
1.277 + }
1.278 + }
1.279 + break;
1.280 + }
1.281 + } while (++key<end);
1.282 + return ptr;
1.283 + }
1.284 +
1.285 +TInt CDbOrderByStage::HOrdering::CompareLongText8L( const CDbOrderByStage::HOrdering::TBlobKey& aLeft, const CDbOrderByStage::HOrdering::TBlobKey& aRight ) const
1.286 + {
1.287 + TUint sizel = aLeft.iSize;
1.288 + TUint sizer = aRight.iSize;
1.289 + TUint s = sizel;
1.290 + if ( sizer < s )
1.291 + s = sizer;
1.292 + if ( s > static_cast<TUint>( TBlobKey::ETruncSize ) && ( ( sizel | sizer ) & static_cast<TUint>( TBlobKey::ETrunc ) ) )
1.293 + s = TBlobKey::ETruncSize;
1.294 + TInt rr = iTextOps.Compare( aLeft.iData8, s, aRight.iData8, s );
1.295 + if ( rr )
1.296 + return rr;
1.297 +//
1.298 +// matches up to the same-length inlined data...
1.299 +// now it gets interesting
1.300 +//
1.301 + if ( ( ( sizel | sizer ) & static_cast<TUint>( TBlobKey::ETrunc ) ) == 0 )
1.302 + return sizel - sizer; // neither are truncated
1.303 + if ( s == sizel )
1.304 + return -1; // left completely match against truncated right
1.305 + if ( s == sizer )
1.306 + return 1; // right completely matched against truncated left
1.307 +
1.308 + s = Min( TInt( sizel & ~TBlobKey::ETrunc ), TInt( sizer & ~TBlobKey::ETrunc ) ); // minimum real length
1.309 + if ( sizel & static_cast<TUint>( TBlobKey::ETrunc ) )
1.310 + {
1.311 + MStreamBuf& bufL = *BlobLC( aLeft.iId, EDbColLongText8 );
1.312 + if ( sizer & static_cast<TUint>( TBlobKey::ETrunc ) )
1.313 + { // both out-of-line
1.314 + rr = Comp::Compare8L( bufL, *BlobLC( aRight.iId, EDbColLongText8 ), s, iTextOps );
1.315 + CleanupStack::PopAndDestroy();
1.316 + }
1.317 + else // left side only out-of-line
1.318 + rr = Comp::Compare8L( bufL, aRight.iData8, s, iTextOps );
1.319 + }
1.320 + else
1.321 + { // right side only out-of-line
1.322 + __ASSERT( sizer & static_cast<TUint>( TBlobKey::ETrunc ) );
1.323 + rr = -Comp::Compare8L( *BlobLC( aRight.iId, EDbColLongText8 ), aLeft.iData8, s, iTextOps );
1.324 + }
1.325 + CleanupStack::PopAndDestroy();
1.326 + return rr ? rr : ( sizel & ~TBlobKey::ETrunc ) - ( sizer & ~TBlobKey::ETrunc );
1.327 + }
1.328 +
1.329 +TInt CDbOrderByStage::HOrdering::CompareLongText16L( const CDbOrderByStage::HOrdering::TBlobKey& aLeft, const CDbOrderByStage::HOrdering::TBlobKey& aRight ) const
1.330 + {
1.331 + TUint sizeL = aLeft.iSize & ~TBlobKey::ETrunc; // set truncation bit to 0 to get true size
1.332 + TUint sizeR = aRight.iSize & ~TBlobKey::ETrunc;
1.333 + TBool truncL = aLeft.iSize & TBlobKey::ETrunc; // data is truncated if TBlobKey::ETrunc bit is 1
1.334 + TBool truncR = aRight.iSize & TBlobKey::ETrunc;
1.335 +
1.336 + if (!(truncL | truncR)) // neither side is truncated, compare full strings
1.337 + {
1.338 + return iTextOps.Order( aLeft.iData16, sizeL>>1, aRight.iData16, sizeR>>1 );
1.339 + }
1.340 +
1.341 + TInt result;
1.342 + TUint sizeMin = Min( TInt(sizeL), TInt(sizeR) ); // minimum real length
1.343 + if ( truncL )
1.344 + {
1.345 + MStreamBuf& bufL = *BlobLC( aLeft.iId, EDbColLongText16 );
1.346 + if ( truncR )
1.347 + { // both out-of-line
1.348 + result = Comp::Compare16L( bufL, *BlobLC( aRight.iId, EDbColLongText16 ), sizeMin, iTextOps );
1.349 + CleanupStack::PopAndDestroy();
1.350 + }
1.351 + else // left side only out-of-line
1.352 + result = Comp::Compare16L( bufL, aRight.iData16, sizeMin, iTextOps );
1.353 + }
1.354 + else
1.355 + { // right side only out-of-line
1.356 + __ASSERT( truncR );
1.357 + result = -Comp::Compare16L( *BlobLC( aRight.iId, EDbColLongText16 ), aLeft.iData16, sizeMin, iTextOps );
1.358 + }
1.359 + CleanupStack::PopAndDestroy();
1.360 + return result ? result : ( sizeL ) - ( sizeR );
1.361 + }
1.362 +
1.363 +TInt CDbOrderByStage::HOrdering::CompareL(const TAny* aLeft,const TAny* aRight) const
1.364 +//
1.365 +// compare the keys
1.366 +//
1.367 + {
1.368 + const TUint8* left=(const TUint8*)aLeft;
1.369 + const TUint8* right=(const TUint8*)aRight;
1.370 + const TKeyCol* end=iEndOfKeys;
1.371 + const TKeyCol* key=&iKeys[0];
1.372 + TInt rr;
1.373 + for (;;)
1.374 + {
1.375 + switch (key->iType)
1.376 + {
1.377 + default:
1.378 + __ASSERT(0);
1.379 + case EDbColBit:
1.380 + case EDbColUint8:
1.381 + case EDbColUint16:
1.382 + case EDbColUint32:
1.383 + rr=Comp::Compare(*(const TUint32*)left,*(const TUint32*)right);
1.384 + left+=sizeof(TUint32);
1.385 + right+=sizeof(TUint32);
1.386 + break;
1.387 + case EDbColInt8:
1.388 + case EDbColInt16:
1.389 + case EDbColInt32:
1.390 + rr=Comp::Compare(*(const TInt32*)left,*(const TInt32*)right);
1.391 + left+=sizeof(TInt32);
1.392 + right+=sizeof(TInt32);
1.393 + break;
1.394 + case EDbColInt64:
1.395 + rr=Comp::Compare(*(const TInt64*)left,*(const TInt64*)right);
1.396 + left+=sizeof(TInt64);
1.397 + right+=sizeof(TInt64);
1.398 + break;
1.399 + case EDbColDateTime:
1.400 + rr=Comp::Compare(*(const TTime*)left,*(const TTime*)right);
1.401 + left+=sizeof(TTime);
1.402 + right+=sizeof(TTime);
1.403 + break;
1.404 + case EDbColReal32:
1.405 + rr=Comp::Compare(*(const TReal32*)left,*(const TReal32*)right);
1.406 + left+=sizeof(TReal32);
1.407 + right+=sizeof(TReal32);
1.408 + break;
1.409 + case EDbColReal64:
1.410 + rr=Comp::Compare(*(const TReal64*)left,*(const TReal64*)right);
1.411 + left+=sizeof(TReal64);
1.412 + right+=sizeof(TReal64);
1.413 + break;
1.414 + case EDbColText8:
1.415 + {
1.416 + TInt sizel=*left++;
1.417 + TInt sizer=*right++;
1.418 + rr=iTextOps.Compare(left,sizel,right,sizer);
1.419 + left=Align4(left+sizel);
1.420 + right=Align4(right+sizer);
1.421 + }
1.422 + break;
1.423 + case EDbColText16:
1.424 + {
1.425 + const TUint16* l16=reinterpret_cast<const TUint16*>(left);
1.426 + const TUint16* r16=reinterpret_cast<const TUint16*>(right);
1.427 + TInt sizel=*l16++;
1.428 + TInt sizer=*r16++;
1.429 + rr=iTextOps.Order(l16,sizel,r16,sizer);
1.430 + left=Align4(reinterpret_cast<const TUint8*>(l16+sizel));
1.431 + right=Align4(reinterpret_cast<const TUint8*>(r16+sizer));
1.432 + }
1.433 + break;
1.434 + case EDbColLongText8:
1.435 + {
1.436 + const TBlobKey* ltext=(const TBlobKey*)left;
1.437 + const TBlobKey* rtext=(const TBlobKey*)right;
1.438 + rr=CompareLongText8L(*ltext,*rtext);
1.439 + left+=ltext->Size();
1.440 + right+=rtext->Size();
1.441 + }
1.442 + break;
1.443 + case EDbColLongText16:
1.444 + {
1.445 + const TBlobKey* ltext=(const TBlobKey*)left;
1.446 + const TBlobKey* rtext=(const TBlobKey*)right;
1.447 + rr=CompareLongText16L(*ltext,*rtext);
1.448 + left+=ltext->Size();
1.449 + right+=rtext->Size();
1.450 + }
1.451 + break;
1.452 + }
1.453 + if (rr!=0)
1.454 + break;
1.455 + if (++key==end)
1.456 + break;
1.457 + }
1.458 + return key->iOrder==TDbKeyCol::EAsc ? rr : -rr;
1.459 + }
1.460 +
1.461 +//
1.462 +
1.463 +NONSHARABLE_CLASS(CDbOrderByStage::CKeys) : public CBase
1.464 + {
1.465 +public: // should be private but VC++ 4.0 whinges
1.466 + struct TKey
1.467 + {
1.468 + TUint32 iId;
1.469 + TUint8 iKey[4]; // and then some
1.470 + };
1.471 +private:
1.472 + enum {EKeysGranularity=32};
1.473 + struct TPage
1.474 + {
1.475 + TPage* iNext;
1.476 + TKey iEntries[1];
1.477 + };
1.478 + enum {EMinPageSize=0x200,EMinKeyElements=2};
1.479 +public:
1.480 + CKeys(TInt aMaxKeySize);
1.481 + ~CKeys();
1.482 +//
1.483 + void AddL(TDbRecordId aRecordId,const RDbTableRow& aRow,const HOrdering& aOrder);
1.484 + void SortL(const HOrdering& aOrder);
1.485 + void GetRecordsL(CArrayFix<TDbRecordId>& aRecords);
1.486 +#ifdef _CHECK_ORDERING
1.487 + void VerifyOrderingL(const HOrdering& aOrder);
1.488 +#endif
1.489 +private:
1.490 + void SortL(TKey* aData[],TInt aElem,const HOrdering& aOrder);
1.491 + TKey& NewKeyL();
1.492 + void KeyComplete(TAny* aEnd);
1.493 + void Release();
1.494 +private:
1.495 + RPointerArray<TKey> iKeys;
1.496 + TInt iMaxKeySize;
1.497 + TInt iPageSize;
1.498 + TPage* iPages;
1.499 + TKey* iNext;
1.500 + TKey* iEnd;
1.501 + };
1.502 +
1.503 +// Class CDbOrderByStage::CKeys
1.504 +
1.505 +CDbOrderByStage::CKeys::CKeys(TInt aMaxKeySize)
1.506 + :iKeys(EKeysGranularity),iMaxKeySize(_FOFF(TKey,iKey[aMaxKeySize])),
1.507 + iPageSize(Max(EMinPageSize+iMaxKeySize,iMaxKeySize*EMinKeyElements))
1.508 + {}
1.509 +
1.510 +CDbOrderByStage::CKeys::~CKeys()
1.511 + {
1.512 + iKeys.Close();
1.513 + Release();
1.514 + }
1.515 +
1.516 +void CDbOrderByStage::CKeys::SortL(CDbOrderByStage::CKeys::TKey* aData[],TInt aElem,const HOrdering& aOrder)
1.517 +//
1.518 +// Sort the array of row keys
1.519 +// Uses Heap-sort
1.520 +//
1.521 + {
1.522 + __ASSERT(aElem>1);
1.523 + TInt heap=aElem>>1;
1.524 + --aElem;
1.525 + for (;;)
1.526 + {
1.527 + TKey* key;
1.528 + if (heap!=0)
1.529 + key=aData[--heap];
1.530 + else
1.531 + {
1.532 + key=aData[aElem];
1.533 + aData[aElem]=aData[0];
1.534 + if (--aElem==0)
1.535 + {
1.536 + aData[0]=key;
1.537 + break;
1.538 + }
1.539 + }
1.540 + TInt ix=heap;
1.541 + TInt parent;
1.542 + for (parent=ix;;parent=ix)
1.543 + {
1.544 + ix=(ix<<1)+1;
1.545 + if (ix<=aElem)
1.546 + {
1.547 + if (ix<aElem && aOrder.CompareL(aData[ix]->iKey,aData[ix+1]->iKey)<0)
1.548 + ++ix;
1.549 + }
1.550 + else
1.551 + break;
1.552 + if (aOrder.CompareL(aData[ix]->iKey,key->iKey)<=0)
1.553 + break;
1.554 + aData[parent]=aData[ix];
1.555 + }
1.556 + aData[parent]=key;
1.557 + }
1.558 + }
1.559 +
1.560 +void CDbOrderByStage::CKeys::AddL(TDbRecordId aRecordId,const RDbTableRow& aRow,const HOrdering& aOrder)
1.561 +//
1.562 +// Create a key for the row and store it
1.563 +//
1.564 + {
1.565 + TKey& key=NewKeyL();
1.566 + key.iId=aRecordId.Value();
1.567 + TAny* end=aOrder.EntryL(&key.iKey[0],aRow);
1.568 + __LEAVE_IF_ERROR(iKeys.Append(&key));
1.569 + KeyComplete(end);
1.570 + }
1.571 +
1.572 +void CDbOrderByStage::CKeys::SortL(const HOrdering& aOrder)
1.573 + {
1.574 + TInt elem=iKeys.Count();
1.575 + if (elem>1)
1.576 + SortL(&iKeys[0],elem,aOrder);
1.577 + }
1.578 +
1.579 +void CDbOrderByStage::CKeys::GetRecordsL(CArrayFix<TDbRecordId>& aRecords)
1.580 + {
1.581 + TInt elem=iKeys.Count();
1.582 + if (elem==0)
1.583 + return;
1.584 + TKey** const base=&iKeys[0];
1.585 + TKey** ptr=base+elem;
1.586 + do {
1.587 + --ptr;
1.588 + *REINTERPRET_CAST(TDbRecordId*,ptr)=(*ptr)->iId;
1.589 + } while (ptr>base);
1.590 + Release(); // discard key memory before adding records
1.591 + aRecords.InsertL(0,REINTERPRET_CAST(const TDbRecordId*,base),elem);
1.592 + iKeys.Reset();
1.593 + }
1.594 +
1.595 +void CDbOrderByStage::CKeys::Release()
1.596 +//
1.597 +// Discard all of the allocated pages
1.598 +//
1.599 + {
1.600 + TPage* p=iPages;
1.601 + while (p)
1.602 + {
1.603 + TPage* n=p->iNext;
1.604 + User::Free(p);
1.605 + p=n;
1.606 + }
1.607 + iPages=0;
1.608 + iNext=iEnd=0;
1.609 + }
1.610 +
1.611 +CDbOrderByStage::CKeys::TKey& CDbOrderByStage::CKeys::NewKeyL()
1.612 +//
1.613 +// Allocate a key entry for the raw key data
1.614 +//
1.615 + {
1.616 + TKey* p=iNext;
1.617 + if (PtrAdd(p,iMaxKeySize)>iEnd)
1.618 + { // not enough space for a maximum key
1.619 + TPage* page=iPages;
1.620 + if (page)
1.621 + { // compress the current page
1.622 + __DEBUG(page=(TPage*))User::ReAlloc(page,(TUint8*)iNext-(TUint8*)page);
1.623 + __ASSERT(page==iPages); // if it moves we are dead
1.624 + }
1.625 + page=(TPage*)User::AllocL(_FOFF(TPage,iEntries)+iPageSize);
1.626 + page->iNext=iPages;
1.627 + iPages=page;
1.628 + p=iNext=&page->iEntries[0];
1.629 + iEnd=PtrAdd(p,iPageSize);
1.630 + }
1.631 + return *p;
1.632 + }
1.633 +
1.634 +void CDbOrderByStage::CKeys::KeyComplete(TAny* aEnd)
1.635 +//
1.636 +// Key is complete, prepare for the next one
1.637 +//
1.638 + {
1.639 + __ASSERT(aEnd==Align4(aEnd));
1.640 + __ASSERT(iNext<=aEnd&&aEnd<=iEnd);
1.641 + iNext=STATIC_CAST(TKey*,aEnd);
1.642 + }
1.643 +
1.644 +#ifdef _CHECK_ORDERING
1.645 +void CDbOrderByStage::CKeys::VerifyOrderingL(const HOrdering& aOrder)
1.646 + {
1.647 +// this performs a full O(N*N) comparison of the record set
1.648 + if (iKeys.Count()==0)
1.649 + return;
1.650 + TKey* const* data=&iKeys[0];
1.651 + for (TInt ii=iKeys.Count();--ii>=0;)
1.652 + {
1.653 + for (TInt jj=iKeys.Count();--jj>=0;)
1.654 + {
1.655 + TInt rr=aOrder.CompareL(data[ii]->iKey,data[jj]->iKey);
1.656 + if (ii==jj)
1.657 + __ASSERT_ALWAYS(rr==0,User::Invariant());
1.658 + else if (ii<jj)
1.659 + __ASSERT_ALWAYS(rr<=0,User::Invariant());
1.660 + else
1.661 + __ASSERT_ALWAYS(rr>=0,User::Invariant());
1.662 + }
1.663 + }
1.664 + }
1.665 +#endif
1.666 +
1.667 +// Class CDbOrderByStage
1.668 +
1.669 +inline const RDbTableRow& CDbOrderByStage::Row()
1.670 + {return iRow;}
1.671 +inline CDbOrderByStage::CKeys& CDbOrderByStage::Keys()
1.672 + {__ASSERT(iKeys);return *iKeys;}
1.673 +inline const CDbOrderByStage::HOrdering& CDbOrderByStage::Order()
1.674 + {__ASSERT(iOrder);return *iOrder;}
1.675 +
1.676 +CDbOrderByStage::CDbOrderByStage(const RDbTableRow& aRow)
1.677 + : CDbBasicWindowStage(KDbUnlimitedWindow),iRow(aRow)
1.678 + {
1.679 + __ASSERT(iState==EReset);
1.680 + }
1.681 +
1.682 +CDbOrderByStage::~CDbOrderByStage()
1.683 + {
1.684 + delete iOrder;
1.685 + delete iKeys;
1.686 + }
1.687 +
1.688 +void CDbOrderByStage::ConstructL(const CDbKey& aOrderBy)
1.689 +//
1.690 +// Build the key structures to support the partial and complete ordering
1.691 +//
1.692 + {
1.693 + iOrder=HOrdering::NewL(Row().Table(),aOrderBy);
1.694 + }
1.695 +
1.696 +void CDbOrderByStage::Reset()
1.697 +//
1.698 +// Reset the window to initial state
1.699 +//
1.700 + {
1.701 + delete iKeys;
1.702 + iKeys=0;
1.703 + iState=EReset;
1.704 + CDbBasicWindowStage::Reset();
1.705 + }
1.706 +
1.707 +TBool CDbOrderByStage::ReadL(TInt& aWork,TDbPosition aNext)
1.708 +//
1.709 +// Read some more record keys
1.710 +//
1.711 + {
1.712 + TDbRecordId id(KDbNullRecordIdValue);
1.713 + TGoto r;
1.714 + while ((r=CDbDataStage::GotoL(aWork,aNext,id))==ESuccess)
1.715 + {
1.716 + CDbDataStage::ReadRowL(id);
1.717 + Keys().AddL(id,Row(),Order());
1.718 + aNext=EDbNext;
1.719 + }
1.720 + switch (r)
1.721 + {
1.722 + default:
1.723 + __ASSERT(0);
1.724 + case ESynchFailure:
1.725 + __LEAVE(KErrNotReady);
1.726 + case EExhausted:
1.727 + return ETrue;
1.728 + case ENoRow:
1.729 + return EFalse;
1.730 + }
1.731 + }
1.732 +
1.733 +TBool CDbOrderByStage::DoEvaluateL(TInt& aWork)
1.734 +//
1.735 +// Build the key collection, and finally sort it
1.736 +//
1.737 + {
1.738 + TState s=iState;
1.739 + iState=EFailed;
1.740 + switch (s)
1.741 + {
1.742 + default:
1.743 + __ASSERT(0);
1.744 + case EFailed:
1.745 + __LEAVE(KErrNotReady);
1.746 + case EReset:
1.747 + __ASSERT(!iKeys);
1.748 + iKeys=new(ELeave) CKeys(Order().MaxSize());
1.749 + // drop through to EEvaluate
1.750 + case EEvaluate:
1.751 + if (ReadL(aWork,s==EReset ? EDbFirst : EDbNext))
1.752 + {
1.753 + iState=EEvaluate;
1.754 + return ETrue;
1.755 + }
1.756 + // drop through to ESort
1.757 + case ESort:
1.758 + Keys().SortL(Order());
1.759 +#ifdef _CHECK_ORDERING
1.760 + Keys().VerifyOrderingL(Order());
1.761 +#endif
1.762 + // drop through to EAdd
1.763 + case EAdd:
1.764 + Keys().GetRecordsL(iRecords);
1.765 + delete iKeys;
1.766 + iKeys=0;
1.767 + // drop through to EComplete
1.768 + case EComplete:
1.769 + iState=EComplete;
1.770 + return EFalse;
1.771 + }
1.772 + }
1.773 +
1.774 +TBool CDbOrderByStage::Unevaluated()
1.775 +//
1.776 +// Return whether it is worth Evaluating
1.777 +//
1.778 + {
1.779 + if (iState==EComplete)
1.780 + return CDbDataStage::Unevaluated();
1.781 + return iState!=EFailed;
1.782 + }
1.783 +
1.784 +
1.785 +// Class CDbReorderWindowStage
1.786 +
1.787 +CDbReorderWindowStage::CDbReorderWindowStage()
1.788 + : CDbBasicWindowStage(KDbUnlimitedWindow),iRows(EGranularity)
1.789 + {
1.790 + __ASSERT(iState==EReset);
1.791 + }
1.792 +
1.793 +CDbReorderWindowStage::~CDbReorderWindowStage()
1.794 + {
1.795 + iRows.Close();
1.796 + }
1.797 +
1.798 +void CDbReorderWindowStage::Reset()
1.799 +//
1.800 +// Reset the window to initial state
1.801 +//
1.802 + {
1.803 + iRows.Reset();
1.804 + iState=EReset;
1.805 + CDbBasicWindowStage::Reset();
1.806 + }
1.807 +
1.808 +TBool CDbReorderWindowStage::ReadL(TInt& aWork,TDbPosition aNext)
1.809 +//
1.810 +// Read some more row ids
1.811 +//
1.812 + {
1.813 + TDbRecordId id(KDbNullRecordIdValue);
1.814 + TGoto r;
1.815 + while ((r=CDbDataStage::GotoL(aWork,aNext,id))==ESuccess)
1.816 + {
1.817 + __LEAVE_IF_ERROR(iRows.Append(id.Value()));
1.818 + aNext=EDbNext;
1.819 + }
1.820 + switch (r)
1.821 + {
1.822 + default:
1.823 + __ASSERT(0);
1.824 + case ESynchFailure:
1.825 + __LEAVE(KErrNotReady);
1.826 + case EExhausted:
1.827 + return ETrue;
1.828 + case ENoRow:
1.829 + return EFalse;
1.830 + }
1.831 + }
1.832 +
1.833 +TBool CDbReorderWindowStage::DoEvaluateL(TInt& aWork)
1.834 +//
1.835 +// Build the key collection, and finally sort it
1.836 +//
1.837 + {
1.838 + TState s=iState;
1.839 + iState=EFailed;
1.840 + switch (s)
1.841 + {
1.842 + default:
1.843 + __ASSERT(0);
1.844 + case EFailed:
1.845 + __LEAVE(KErrNotReady);
1.846 + case EReset:
1.847 + case EEvaluate:
1.848 + if (ReadL(aWork,s==EReset ? EDbFirst : EDbNext))
1.849 + {
1.850 + iState=EEvaluate;
1.851 + return ETrue;
1.852 + }
1.853 + if (iRows.Count())
1.854 + {
1.855 + iRows.Sort();
1.856 + iRecords.AppendL((const TDbRecordId*)&iRows[0],iRows.Count());
1.857 + iRows.Reset();
1.858 + }
1.859 + case EComplete:
1.860 + iState=EComplete;
1.861 + return EFalse;
1.862 + }
1.863 + }
1.864 +
1.865 +TBool CDbReorderWindowStage::Unevaluated()
1.866 +//
1.867 +// Return whether it is worth Evaluating
1.868 +//
1.869 + {
1.870 + if (iState==EComplete)
1.871 + return CDbDataStage::Unevaluated();
1.872 + return iState!=EFailed;
1.873 + }
1.874 +