Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add a bugfix for b-tree deletes. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
88c8fd489d80c07d0faff822ad8a34e6 |
| User & Date: | dan 2013-09-25 19:40:34 |
Context
|
2013-09-27
| ||
| 20:25 | Begin adding routines for b-tree balancing and so on. Incomplete. check-in: 3003f1d99a user: dan tags: trunk | |
|
2013-09-25
| ||
| 19:40 | Add a bugfix for b-tree deletes. check-in: 88c8fd489d user: dan tags: trunk | |
| 18:46 | Further btree updates. check-in: 6548088566 user: dan tags: trunk | |
Changes
Changes to src/bt.h.
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr);
int sqlite4BtCsrLast(bt_cursor *pCsr);
int sqlite4BtCsrNext(bt_cursor *pCsr);
int sqlite4BtCsrPrev(bt_cursor *pCsr);
int sqlite4BtCsrValid(bt_cursor *pCsr);
int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK);
int sqlite4BtCsrData(bt_cursor *pCsr, int, int, const void **ppV, int *pnV);
int sqlite4BtReplace(bt_db*, const void *pK, int nK, const void *pV, int nV);
int sqlite4BtDelete(bt_cursor*);
int sqlite4BtSetCookie(bt_db*, unsigned int iVal);
int sqlite4BtGetCookie(bt_db*, unsigned int *piVal);
|
< |
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
*/ int sqlite4BtCsrFirst(bt_cursor *pCsr); int sqlite4BtCsrLast(bt_cursor *pCsr); int sqlite4BtCsrNext(bt_cursor *pCsr); int sqlite4BtCsrPrev(bt_cursor *pCsr); int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK); int sqlite4BtCsrData(bt_cursor *pCsr, int, int, const void **ppV, int *pnV); int sqlite4BtReplace(bt_db*, const void *pK, int nK, const void *pV, int nV); int sqlite4BtDelete(bt_cursor*); int sqlite4BtSetCookie(bt_db*, unsigned int iVal); int sqlite4BtGetCookie(bt_db*, unsigned int *piVal); |
Changes to src/bt_main.c.
245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 ... 427 428 429 430 431 432 433 434 435 436 437 438 439 440 ... 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 ... 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 |
}
return pgno;
}
#ifndef NDEBUG
static void printPage(u8 *aData, int nData){
int i;
int nCell = (int)btCellCount(aData, nData);
printf("nCell=%d\n", nCell);
printf("iFree=%d\n", (int)btFreeOffset(aData, nData));
printf("flags=%d\n", (int)btFlags(aData, nData));
printf("cell offsets:");
for(i=0; i<nCell; i++){
printf(" %d", btCellFind(aData, nData, i) - aData);
}
printf("\n");
}
#endif
/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
int rc; /* Return Code */
u32 pgno; /* Page number for next page to load */
/* Reset the cursor */
btCsrReset(pCsr);
/* Figure out the root page number */
assert( pCsr->nPg==0 );
pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);
while( rc==SQLITE4_OK ){
/* Load page number pgno into the b-tree */
rc = btCsrDescend(pCsr, pgno);
if( rc==SQLITE4_OK ){
int nByte;
u8 *pCell;
u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
/* If the cursor has descended to a leaf break out of the loop. */
pCsr->aiCell[pCsr->nPg-1] = (bLast ? btCellCount(aData, pgsz) : 0);
if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
/* Otherwise, set pgno to the left or rightmost child of the page
** just loaded, depending on whether the cursor is seeking to the
** start or end of the tree. */
if( bLast==0 ){
pCell = btCellFind(aData, pgsz, 0);
pCell += sqlite4BtVarintGet32(pCell, &nByte);
pCell += nByte;
sqlite4BtVarintGet32(pCell, (int *)&pgno);
}else{
pgno = btGetU32(&aData[1]);
}
}
}
return rc;
}
/*
** This function compares the key passed via parameters pK and nK to the
** key stored as part of cell iCell on the database page stored in buffer
** aData (size nData bytes).
**
** If the cell key is C, and the user key K, then this function sets:
**
................................................................................
}
}
}
}
return rc;
}
/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
return btCsrEnd(pCsr, 0);
}
................................................................................
/*
** Retreat to the previous entry in the tree.
*/
int sqlite4BtCsrPrev(bt_cursor *pCsr){
return btCsrStep(pCsr, 0);
}
int sqlite4BtCsrValid(bt_cursor *pCsr){
assert( 0 );
return 0;
}
int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
u8 *aData;
u8 *pCell;
int iCell = pCsr->aiCell[pCsr->nPg-1];
int nK;
................................................................................
nFree = pgsz - btFreeOffset(aData, pgsz) - (2+nCell) * 2;
}
if( nFree>=nReq ){
rc = sqlite4BtPageWrite(pLeaf);
if( rc==SQLITE4_OK ){
aData = sqlite4BtPageData(pLeaf);
/* Increase cell count */
btPutU16(&aData[pgsz-2], nCell+1);
/* Update the cell pointer array */
if( iCell!=nCell ){
u8 *aFrom = &aData[pgsz-4-iCell*2];
memmove(aFrom, &aFrom[-2], (nCell-iCell) * 2);
}
btPutU16(btCellPtrFind(aData, pgsz, iCell), iWrite);
/* Write the cell itself */
iWrite += sqlite4BtVarintPut32(&aData[iWrite], nK);
memcpy(&aData[iWrite], pK, nK);
iWrite += nK;
iWrite += sqlite4BtVarintPut32(&aData[iWrite], nV);
memcpy(&aData[iWrite], pV, nV);
|
> | | | | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < < < < < < < < < > > | > > > |
245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 ... 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 ... 519 520 521 522 523 524 525 526 527 528 529 530 531 532 ... 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 |
} return pgno; } #ifndef NDEBUG #include <stdio.h> static void printPage(u8 *aData, int nData){ int i; int nCell = (int)btCellCount(aData, nData); fprintf(stderr, "nCell=%d\n", nCell); fprintf(stderr, "iFree=%d\n", (int)btFreeOffset(aData, nData)); fprintf(stderr, "flags=%d\n", (int)btFlags(aData, nData)); fprintf(stderr, "cell offsets:"); for(i=0; i<nCell; i++){ fprintf(stderr, " %d", btCellFind(aData, nData, i) - aData); } fprintf(stderr, "\n"); } #endif /* ** This function compares the key passed via parameters pK and nK to the ** key stored as part of cell iCell on the database page stored in buffer ** aData (size nData bytes). ** ** If the cell key is C, and the user key K, then this function sets: ** ................................................................................ } } } } return rc; } /* ** This function seeks the cursor as required for either sqlite4BtCsrFirst() ** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true). */ static int btCsrEnd(bt_cursor *pCsr, int bLast){ const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager); int rc; /* Return Code */ u32 pgno; /* Page number for next page to load */ /* Reset the cursor */ btCsrReset(pCsr); /* Figure out the root page number */ assert( pCsr->nPg==0 ); pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager); while( rc==SQLITE4_OK ){ /* Load page number pgno into the b-tree */ rc = btCsrDescend(pCsr, pgno); if( rc==SQLITE4_OK ){ int nByte; u8 *pCell; u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]); /* If the cursor has descended to a leaf break out of the loop. */ pCsr->aiCell[pCsr->nPg-1] = (bLast ? btCellCount(aData, pgsz) : 0); if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break; /* Otherwise, set pgno to the left or rightmost child of the page ** just loaded, depending on whether the cursor is seeking to the ** start or end of the tree. */ if( bLast==0 ){ pCell = btCellFind(aData, pgsz, 0); pCell += sqlite4BtVarintGet32(pCell, &nByte); pCell += nByte; sqlite4BtVarintGet32(pCell, (int *)&pgno); }else{ pgno = btGetU32(&aData[1]); } } } return rc; } /* ** Position cursor pCsr to point to the smallest key in the database. */ int sqlite4BtCsrFirst(bt_cursor *pCsr){ return btCsrEnd(pCsr, 0); } ................................................................................ /* ** Retreat to the previous entry in the tree. */ int sqlite4BtCsrPrev(bt_cursor *pCsr){ return btCsrStep(pCsr, 0); } int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){ const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager); u8 *aData; u8 *pCell; int iCell = pCsr->aiCell[pCsr->nPg-1]; int nK; ................................................................................ nFree = pgsz - btFreeOffset(aData, pgsz) - (2+nCell) * 2; } if( nFree>=nReq ){ rc = sqlite4BtPageWrite(pLeaf); if( rc==SQLITE4_OK ){ aData = sqlite4BtPageData(pLeaf); /* Update the cell pointer array */ if( iCell!=nCell ){ u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1); u8 *aTo = btCellPtrFind(aData, pgsz, nCell); memmove(aTo, aFrom, (nCell-iCell) * 2); } btPutU16(btCellPtrFind(aData, pgsz, iCell), iWrite); /* Increase cell count */ btPutU16(&aData[pgsz-2], nCell+1); /* Write the cell itself */ iWrite += sqlite4BtVarintPut32(&aData[iWrite], nK); memcpy(&aData[iWrite], pK, nK); iWrite += nK; iWrite += sqlite4BtVarintPut32(&aData[iWrite], nV); memcpy(&aData[iWrite], pV, nV); |
Changes to test/simple3.test.
19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
do_test 1.0 {
sqlite4 db file:test.db?kv=bt
db close
} {}
do_test 1.1 { sqlite4 db file:test.db?kv=bt } {}
do_execsql_test 1.2 { CREATE TABLE t1(a, b) }
do_execsql_test 1.3 {
SELECT * FROM sqlite_master;
} {table t1 t1 2 {CREATE TABLE t1(a, b)}}
finish_test
|
> | > > > > > > > > > > > > > > > > > > > > |
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
do_test 1.0 {
sqlite4 db file:test.db?kv=bt
db close
} {}
do_test 1.1 { sqlite4 db file:test.db?kv=bt } {}
do_execsql_test 1.2 {
CREATE TABLE t1(a, b)
}
do_execsql_test 1.3 {
SELECT * FROM sqlite_master;
} {table t1 t1 2 {CREATE TABLE t1(a, b)}}
do_execsql_test 1.4 {
INSERT INTO t1 VALUES('abc', 'def');
INSERT INTO t1 VALUES('ghi', 'jkl');
} {}
do_execsql_test 1.5 {
SELECT rowid, a, b FROM t1;
} {1 abc def 2 ghi jkl}
do_execsql_test 1.6 {
UPDATE t1 SET b = 5;
}
do_execsql_test 1.7 {
SELECT rowid, a, b FROM t1;
} {1 abc 5 2 ghi 5}
finish_test
|