Index: src/wal.c ================================================================== --- src/wal.c +++ src/wal.c @@ -1285,53 +1285,99 @@ *piPage = p->iPrior = iRet; return (iRet==0xFFFFFFFF); } +/* +** This function merges two sorted lists into a single sorted list. +*/ +static void walMerge( + u32 *aContent, /* Pages in wal */ + ht_slot *aLeft, /* IN: Left hand input list */ + int nLeft, /* IN: Elements in array *paLeft */ + ht_slot **paRight, /* IN/OUT: Right hand input list */ + int *pnRight, /* IN/OUT: Elements in *paRight */ + ht_slot *aTmp /* Temporary buffer */ +){ + int iLeft = 0; /* Current index in aLeft */ + int iRight = 0; /* Current index in aRight */ + int iOut = 0; /* Current index in output buffer */ + int nRight = *pnRight; + ht_slot *aRight = *paRight; + assert( nLeft>0 && nRight>0 ); + while( iRight=nRight || aContent[aLeft[iLeft]]=nLeft || aContent[aLeft[iLeft]]>dbpage ); + assert( iRight>=nRight || aContent[aRight[iRight]]>dbpage ); + } + + *paRight = aLeft; + *pnRight = iOut; + memcpy(aLeft, aTmp, sizeof(aTmp[0])*iOut); +} + +/* +** Sort the elements in list aList, removing any duplicates. +*/ static void walMergesort( u32 *aContent, /* Pages in wal */ ht_slot *aBuffer, /* Buffer of at least *pnList items to use */ ht_slot *aList, /* IN/OUT: List to sort */ int *pnList /* IN/OUT: Number of elements in aList[] */ ){ - int nList = *pnList; - if( nList>1 ){ - int nLeft = nList / 2; /* Elements in left list */ - int nRight = nList - nLeft; /* Elements in right list */ - int iLeft = 0; /* Current index in aLeft */ - int iRight = 0; /* Current index in aright */ - int iOut = 0; /* Current index in output buffer */ - ht_slot *aLeft = aList; /* Left list */ - ht_slot *aRight = aList+nLeft;/* Right list */ - - /* TODO: Change to non-recursive version. */ - walMergesort(aContent, aBuffer, aLeft, &nLeft); - walMergesort(aContent, aBuffer, aRight, &nRight); - - while( iRight=nRight || aContent[aLeft[iLeft]]=nLeft || aContent[aLeft[iLeft]]>dbpage ); - assert( iRight>=nRight || aContent[aRight[iRight]]>dbpage ); - } - memcpy(aList, aBuffer, sizeof(aList[0])*iOut); - *pnList = iOut; - } + struct Sublist { + int nList; /* Number of elements in aList */ + ht_slot *aList; /* Pointer to sub-list content */ + }; + + const int nList = *pnList; /* Size of input list */ + int nMerge; /* Number of elements in list aMerge */ + ht_slot *aMerge; /* List to be merged */ + int iList; /* Index into input list */ + int iSub; /* Index into aSub array */ + struct Sublist aSub[13]; /* Array of sub-lists */ + + memset(aSub, 0, sizeof(aSub)); + assert( nList<=HASHTABLE_NPAGE && nList>0 ); + assert( HASHTABLE_NPAGE==(1<<(ArraySize(aSub)-1)) ); + + for(iList=0; iListaList && p->nList<=(1<aList, p->nList, &aMerge, &nMerge, aBuffer); + } + aSub[iSub].aList = aMerge; + aSub[iSub].nList = nMerge; + } + + for(iSub++; iSubnList<=(2<aList, p->nList, &aMerge, &nMerge, aBuffer); + } + } + assert( aMerge==aList ); + *pnList = nMerge; #ifdef SQLITE_DEBUG { int i; for(i=1; i<*pnList; i++){ @@ -1472,15 +1518,18 @@ u32 iFrame = 0; /* Wal frame containing data for iDbpage */ u32 mxSafeFrame; /* Max frame that can be backfilled */ int i; /* Loop counter */ volatile WalCkptInfo *pInfo; /* The checkpoint status information */ + if( pWal->hdr.mxFrame==0 ) return SQLITE_OK; + /* Allocate the iterator */ rc = walIteratorInit(pWal, &pIter); - if( rc!=SQLITE_OK || pWal->hdr.mxFrame==0 ){ + if( rc!=SQLITE_OK ){ goto walcheckpoint_out; } + assert( pIter ); /*** TODO: Move this test out to the caller. Make it an assert() here ***/ if( pWal->hdr.szPage!=nBuf ){ rc = SQLITE_CORRUPT_BKPT; goto walcheckpoint_out;