Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Modify the merge-sort in wal.c so that it does not use recursion. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
daea6c054cee3564d8460d876b78a325 |
User & Date: | dan 2010-06-25 11:35:52.000 |
Context
2010-06-25
| ||
12:52 | Change the name of the shared-memory file on windows from *-wal-index to *-shm, for consistency with unix. (check-in: 5995cb1508 user: drh tags: trunk) | |
11:35 | Modify the merge-sort in wal.c so that it does not use recursion. (check-in: daea6c054c user: dan tags: trunk) | |
2010-06-24
| ||
19:16 | Add test cases to pager1.test and pagerfault.test. (check-in: 4941e437d2 user: dan tags: trunk) | |
Changes
Changes to src/wal.c.
︙ | ︙ | |||
1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 | } } *piPage = p->iPrior = iRet; return (iRet==0xFFFFFFFF); } 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[] */ ){ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | > > | > | | | | | < < < | > > < < > | > > > > > | < < < | < | | < | > > > | | < < | | | < | 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 | } } *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 || iLeft<nLeft ){ ht_slot logpage; Pgno dbpage; if( (iLeft<nLeft) && (iRight>=nRight || aContent[aLeft[iLeft]]<aContent[aRight[iRight]]) ){ logpage = aLeft[iLeft++]; }else{ logpage = aRight[iRight++]; } dbpage = aContent[logpage]; aTmp[iOut++] = logpage; if( iLeft<nLeft && aContent[aLeft[iLeft]]==dbpage ) iLeft++; assert( 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[] */ ){ 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; iList<nList; iList++){ nMerge = 1; aMerge = &aList[iList]; for(iSub=0; iList & (1<<iSub); iSub++){ struct Sublist *p = &aSub[iSub]; assert( p->aList && p->nList<=(1<<iSub) ); walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer); } aSub[iSub].aList = aMerge; aSub[iSub].nList = nMerge; } for(iSub++; iSub<ArraySize(aSub); iSub++){ if( nList & (1<<iSub) ){ struct Sublist *p = &aSub[iSub]; assert( p->nList<=(2<<iSub) ); walMerge(aContent, p->aList, p->nList, &aMerge, &nMerge, aBuffer); } } assert( aMerge==aList ); *pnList = nMerge; #ifdef SQLITE_DEBUG { int i; for(i=1; i<*pnList; i++){ assert( aContent[aList[i]] > aContent[aList[i-1]] ); } |
︙ | ︙ | |||
1470 1471 1472 1473 1474 1475 1476 1477 1478 | WalIterator *pIter = 0; /* Wal iterator context */ u32 iDbpage = 0; /* Next database page to write */ 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 */ /* Allocate the iterator */ rc = walIteratorInit(pWal, &pIter); | > > | > | 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 | WalIterator *pIter = 0; /* Wal iterator context */ u32 iDbpage = 0; /* Next database page to write */ 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 ){ 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; } |
︙ | ︙ |