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