From 569c6676a6ddb0ff73821d7693b5e18ddef809b9 Mon Sep 17 00:00:00 2001 From: Hans-Christoph Steiner Date: Thu, 16 Oct 2014 22:51:35 -0400 Subject: Imported Upstream version 3.2.0 --- src/vdbesort.c | 111 +++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 84 insertions(+), 27 deletions(-) (limited to 'src/vdbesort.c') diff --git a/src/vdbesort.c b/src/vdbesort.c index fdfc4a7..6a5855f 100644 --- a/src/vdbesort.c +++ b/src/vdbesort.c @@ -54,7 +54,7 @@ typedef struct FileWriter FileWriter; ** other key value. If the keys are equal (only possible with two EOF ** values), it doesn't matter which index is stored. ** -** The (N/4) elements of aTree[] that preceed the final (N/2) described +** The (N/4) elements of aTree[] that precede the final (N/2) described ** above contains the index of the smallest of each block of 4 iterators. ** And so on. So that aTree[1] contains the index of the iterator that ** currently points to the smallest key value. aTree[0] is unused. @@ -350,7 +350,6 @@ static int vdbeSorterIterInit( rc = sqlite3OsRead( pSorter->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart ); - assert( rc!=SQLITE_IOERR_SHORT_READ ); } if( rc==SQLITE_OK ){ @@ -386,7 +385,7 @@ static int vdbeSorterIterInit( */ static void vdbeSorterCompare( const VdbeCursor *pCsr, /* Cursor object (for pKeyInfo) */ - int bOmitRowid, /* Ignore rowid field at end of keys */ + int nKeyCol, /* Num of columns. 0 means "all" */ const void *pKey1, int nKey1, /* Left side of comparison */ const void *pKey2, int nKey2, /* Right side of comparison */ int *pRes /* OUT: Result of comparison */ @@ -400,19 +399,18 @@ static void vdbeSorterCompare( sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2); } - if( bOmitRowid ){ - r2->nField = pKeyInfo->nField; - assert( r2->nField>0 ); - for(i=0; inField; i++){ + if( nKeyCol ){ + r2->nField = nKeyCol; + for(i=0; iaMem[i].flags & MEM_Null ){ *pRes = -1; return; } } - r2->flags |= UNPACKED_PREFIX_MATCH; + assert( r2->default_rc==0 ); } - *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2); + *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2, 0); } /* @@ -504,23 +502,40 @@ static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){ } } +/* +** Reset a sorting cursor back to its original empty state. +*/ +void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){ + if( pSorter->aIter ){ + int i; + for(i=0; inTree; i++){ + vdbeSorterIterZero(db, &pSorter->aIter[i]); + } + sqlite3DbFree(db, pSorter->aIter); + pSorter->aIter = 0; + } + if( pSorter->pTemp1 ){ + sqlite3OsCloseFree(pSorter->pTemp1); + pSorter->pTemp1 = 0; + } + vdbeSorterRecordFree(db, pSorter->pRecord); + pSorter->pRecord = 0; + pSorter->iWriteOff = 0; + pSorter->iReadOff = 0; + pSorter->nInMemory = 0; + pSorter->nTree = 0; + pSorter->nPMA = 0; + pSorter->aTree = 0; +} + + /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; if( pSorter ){ - if( pSorter->aIter ){ - int i; - for(i=0; inTree; i++){ - vdbeSorterIterZero(db, &pSorter->aIter[i]); - } - sqlite3DbFree(db, pSorter->aIter); - } - if( pSorter->pTemp1 ){ - sqlite3OsCloseFree(pSorter->pTemp1); - } - vdbeSorterRecordFree(db, pSorter->pRecord); + sqlite3VdbeSorterReset(db, pSorter); sqlite3DbFree(db, pSorter->pUnpacked); sqlite3DbFree(db, pSorter); pCsr->pSorter = 0; @@ -956,14 +971,55 @@ int sqlite3VdbeSorterNext(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){ if( pSorter->aTree ){ int iPrev = pSorter->aTree[1];/* Index of iterator to advance */ - int i; /* Index of aTree[] to recalculate */ - rc = vdbeSorterIterNext(db, &pSorter->aIter[iPrev]); - for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){ - rc = vdbeSorterDoCompare(pCsr, i); - } + if( rc==SQLITE_OK ){ + int i; /* Index of aTree[] to recalculate */ + VdbeSorterIter *pIter1; /* First iterator to compare */ + VdbeSorterIter *pIter2; /* Second iterator to compare */ + u8 *pKey2; /* To pIter2->aKey, or 0 if record cached */ + + /* Find the first two iterators to compare. The one that was just + ** advanced (iPrev) and the one next to it in the array. */ + pIter1 = &pSorter->aIter[(iPrev & 0xFFFE)]; + pIter2 = &pSorter->aIter[(iPrev | 0x0001)]; + pKey2 = pIter2->aKey; + + for(i=(pSorter->nTree+iPrev)/2; i>0; i=i/2){ + /* Compare pIter1 and pIter2. Store the result in variable iRes. */ + int iRes; + if( pIter1->pFile==0 ){ + iRes = +1; + }else if( pIter2->pFile==0 ){ + iRes = -1; + }else{ + vdbeSorterCompare(pCsr, 0, + pIter1->aKey, pIter1->nKey, pKey2, pIter2->nKey, &iRes + ); + } - *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0); + /* If pIter1 contained the smaller value, set aTree[i] to its index. + ** Then set pIter2 to the next iterator to compare to pIter1. In this + ** case there is no cache of pIter2 in pSorter->pUnpacked, so set + ** pKey2 to point to the record belonging to pIter2. + ** + ** Alternatively, if pIter2 contains the smaller of the two values, + ** set aTree[i] to its index and update pIter1. If vdbeSorterCompare() + ** was actually called above, then pSorter->pUnpacked now contains + ** a value equivalent to pIter2. So set pKey2 to NULL to prevent + ** vdbeSorterCompare() from decoding pIter2 again. */ + if( iRes<=0 ){ + pSorter->aTree[i] = (int)(pIter1 - pSorter->aIter); + pIter2 = &pSorter->aIter[ pSorter->aTree[i ^ 0x0001] ]; + pKey2 = pIter2->aKey; + }else{ + if( pIter1->pFile ) pKey2 = 0; + pSorter->aTree[i] = (int)(pIter2 - pSorter->aIter); + pIter1 = &pSorter->aIter[ pSorter->aTree[i ^ 0x0001] ]; + } + + } + *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0); + } }else{ SorterRecord *pFree = pSorter->pRecord; pSorter->pRecord = pFree->pNext; @@ -1027,12 +1083,13 @@ int sqlite3VdbeSorterRowkey(const VdbeCursor *pCsr, Mem *pOut){ int sqlite3VdbeSorterCompare( const VdbeCursor *pCsr, /* Sorter cursor */ Mem *pVal, /* Value to compare to current sorter key */ + int nKeyCol, /* Only compare this many fields */ int *pRes /* OUT: Result of comparison */ ){ VdbeSorter *pSorter = pCsr->pSorter; void *pKey; int nKey; /* Sorter key to compare pVal with */ pKey = vdbeSorterRowkey(pSorter, &nKey); - vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes); + vdbeSorterCompare(pCsr, nKeyCol, pVal->z, pVal->n, pKey, nKey, pRes); return SQLITE_OK; } -- cgit v1.2.3