Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further tests and changes to make the r-tree module more robust. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
7ff3574b9c581b5e1f2b6f98028106c6 |
User & Date: | dan 2010-09-22 19:06:03.000 |
Context
2010-09-23
| ||
18:47 | Add tests to e_delete.test. (check-in: fab3b383bb user: dan tags: trunk) | |
2010-09-22
| ||
19:06 | Further tests and changes to make the r-tree module more robust. (check-in: 7ff3574b9c user: dan tags: trunk) | |
14:19 | Add new file rtreeA.test, to test that the r-tree extension doesn't crash if it encounters a corrupt or inconsistent database. (check-in: 68a305fd5a user: dan tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
458 459 460 461 462 463 464 465 466 467 468 469 470 471 | nodeAcquire( Rtree *pRtree, /* R-tree structure */ i64 iNode, /* Node number to load */ RtreeNode *pParent, /* Either the parent node or NULL */ RtreeNode **ppNode /* OUT: Acquired node */ ){ int rc; RtreeNode *pNode; /* Check if the requested node is already in the hash table. If so, ** increase its reference count and return it. */ if( (pNode = nodeHashLookup(pRtree, iNode)) ){ assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); | > | 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 | nodeAcquire( Rtree *pRtree, /* R-tree structure */ i64 iNode, /* Node number to load */ RtreeNode *pParent, /* Either the parent node or NULL */ RtreeNode **ppNode /* OUT: Acquired node */ ){ int rc; int rc2 = SQLITE_OK; RtreeNode *pNode; /* Check if the requested node is already in the hash table. If so, ** increase its reference count and return it. */ if( (pNode = nodeHashLookup(pRtree, iNode)) ){ assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); |
︙ | ︙ | |||
481 482 483 484 485 486 487 | sqlite3_bind_int64(pRtree->pReadNode, 1, iNode); rc = sqlite3_step(pRtree->pReadNode); if( rc==SQLITE_ROW ){ const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0); if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){ pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); if( !pNode ){ | | > | 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 | sqlite3_bind_int64(pRtree->pReadNode, 1, iNode); rc = sqlite3_step(pRtree->pReadNode); if( rc==SQLITE_ROW ){ const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0); if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){ pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); if( !pNode ){ rc2 = SQLITE_NOMEM; }else{ pNode->pParent = pParent; pNode->zData = (u8 *)&pNode[1]; pNode->nRef = 1; pNode->iNode = iNode; pNode->isDirty = 0; pNode->pNext = 0; memcpy(pNode->zData, zBlob, pRtree->iNodeSize); nodeReference(pParent); } } } rc = sqlite3_reset(pRtree->pReadNode); if( rc==SQLITE_OK ) rc = rc2; /* If the root node was just loaded, set pRtree->iDepth to the height ** of the r-tree structure. A height of zero means all data is stored on ** the root node. A height of one means the children of the root node ** are the leaves, and so on. If the depth as specified on the root node ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt. */ |
︙ | ︙ | |||
1039 1040 1041 1042 1043 1044 1045 | return SQLITE_OK; } /* ** One of the cells in node pNode is guaranteed to have a 64-bit ** integer value equal to iRowid. Return the index of this cell. */ | | > > > > > > > | | > | > | | | > | | 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 | return SQLITE_OK; } /* ** One of the cells in node pNode is guaranteed to have a 64-bit ** integer value equal to iRowid. Return the index of this cell. */ static int nodeRowidIndex( Rtree *pRtree, RtreeNode *pNode, i64 iRowid, int *piIndex ){ int ii; int nCell = NCELL(pNode); for(ii=0; ii<nCell; ii++){ if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ *piIndex = ii; return SQLITE_OK; } } return SQLITE_CORRUPT; } /* ** Return the index of the cell containing a pointer to node pNode ** in its parent. If pNode is the root node, return -1. */ static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){ RtreeNode *pParent = pNode->pParent; if( pParent ){ return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex); } *piIndex = -1; return SQLITE_OK; } /* ** Rtree virtual table module xNext method. */ static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){ Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab); |
︙ | ︙ | |||
1091 1092 1093 1094 1095 1096 1097 | int isEof; rc = descendToCell(pRtree, pCsr, iHeight, &isEof); if( rc!=SQLITE_OK || !isEof ){ return rc; } } pCsr->pNode = pNode->pParent; | | > > > | 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 | int isEof; rc = descendToCell(pRtree, pCsr, iHeight, &isEof); if( rc!=SQLITE_OK || !isEof ){ return rc; } } pCsr->pNode = pNode->pParent; rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell); if( rc!=SQLITE_OK ){ return rc; } nodeReference(pCsr->pNode); nodeRelease(pRtree, pNode); iHeight++; } } return rc; |
︙ | ︙ | |||
1233 1234 1235 1236 1237 1238 1239 | /* Special case - lookup by rowid. */ RtreeNode *pLeaf; /* Leaf on which the required cell resides */ i64 iRowid = sqlite3_value_int64(argv[0]); rc = findLeafNode(pRtree, iRowid, &pLeaf); pCsr->pNode = pLeaf; if( pLeaf ){ assert( rc==SQLITE_OK ); | | | 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 | /* Special case - lookup by rowid. */ RtreeNode *pLeaf; /* Leaf on which the required cell resides */ i64 iRowid = sqlite3_value_int64(argv[0]); rc = findLeafNode(pRtree, iRowid, &pLeaf); pCsr->pNode = pLeaf; if( pLeaf ){ assert( rc==SQLITE_OK ); rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell); } }else{ /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array ** with the configured constraints. */ if( argc>0 ){ pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc); |
︙ | ︙ | |||
1650 1651 1652 1653 1654 1655 1656 | } /* ** A cell with the same content as pCell has just been inserted into ** the node pNode. This function updates the bounding box cells in ** all ancestor elements. */ | | > > | | > > > | 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 | } /* ** A cell with the same content as pCell has just been inserted into ** the node pNode. This function updates the bounding box cells in ** all ancestor elements. */ static int AdjustTree( Rtree *pRtree, /* Rtree table */ RtreeNode *pNode, /* Adjust ancestry of this node. */ RtreeCell *pCell /* This cell was just inserted */ ){ RtreeNode *p = pNode; while( p->pParent ){ RtreeNode *pParent = p->pParent; RtreeCell cell; int iCell; if( nodeParentIndex(pRtree, p, &iCell) ){ return SQLITE_CORRUPT; } nodeGetCell(pRtree, pParent, iCell, &cell); if( !cellContains(pRtree, &cell, pCell) ){ cellUnion(pRtree, &cell, pCell); nodeOverwriteCell(pRtree, pParent, &cell, iCell); } p = pParent; } return SQLITE_OK; } /* ** Write mapping (iRowid->iNode) to the <rtree>_rowid table. */ static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){ sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid); |
︙ | ︙ | |||
2242 2243 2244 2245 2246 2247 2248 | if( pNode->iNode==1 ){ rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1); if( rc!=SQLITE_OK ){ goto splitnode_out; } }else{ RtreeNode *pParent = pLeft->pParent; | > | > | | > > > > | 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 | if( pNode->iNode==1 ){ rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1); if( rc!=SQLITE_OK ){ goto splitnode_out; } }else{ RtreeNode *pParent = pLeft->pParent; int iCell; rc = nodeParentIndex(pRtree, pLeft, &iCell); if( rc==SQLITE_OK ){ nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell); rc = AdjustTree(pRtree, pParent, &leftbbox); } if( rc!=SQLITE_OK ){ goto splitnode_out; } } if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){ goto splitnode_out; } for(i=0; i<NCELL(pRight); i++){ i64 iRowid = nodeGetRowid(pRtree, pRight, i); |
︙ | ︙ | |||
2289 2290 2291 2292 2293 2294 2295 | nodeRelease(pRtree, pRight); nodeRelease(pRtree, pLeft); sqlite3_free(aCell); return rc; } /* | | | | > | | | > > > | < < | > | | < < | | < | > | | | > | 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 | nodeRelease(pRtree, pRight); nodeRelease(pRtree, pLeft); sqlite3_free(aCell); return rc; } /* ** If node pLeaf is not the root of the r-tree and its pParent pointer is ** still NULL, load all ancestor nodes of pLeaf into memory and populate ** the pLeaf->pParent chain all the way up to the root node. */ static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){ int rc = SQLITE_OK; RtreeNode *pChild = pLeaf; while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){ int rc2 = SQLITE_OK; /* sqlite3_reset() return code */ sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode); rc = sqlite3_step(pRtree->pReadParent); if( rc==SQLITE_ROW ){ RtreeNode *pTest; i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0); for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent); if( !pTest ){ rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent); } } rc = sqlite3_reset(pRtree->pReadParent); if( rc==SQLITE_OK ) rc = rc2; if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT; pChild = pChild->pParent; } return rc; } static int deleteCell(Rtree *, RtreeNode *, int, int); static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){ int rc; int rc2; RtreeNode *pParent; int iCell; assert( pNode->nRef==1 ); /* Remove the entry in the parent cell. */ rc = nodeParentIndex(pRtree, pNode, &iCell); if( rc==SQLITE_OK ){ pParent = pNode->pParent; pNode->pParent = 0; rc = deleteCell(pRtree, pParent, iCell, iHeight+1); } rc2 = nodeRelease(pRtree, pParent); if( rc==SQLITE_OK ){ rc = rc2; } if( rc!=SQLITE_OK ){ return rc; } |
︙ | ︙ | |||
2365 2366 2367 2368 2369 2370 2371 | pNode->pNext = pRtree->pDeleted; pNode->nRef++; pRtree->pDeleted = pNode; return SQLITE_OK; } | | > | > | | | > > | 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 | pNode->pNext = pRtree->pDeleted; pNode->nRef++; pRtree->pDeleted = pNode; return SQLITE_OK; } static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){ RtreeNode *pParent = pNode->pParent; int rc = SQLITE_OK; if( pParent ){ int ii; int nCell = NCELL(pNode); RtreeCell box; /* Bounding box for pNode */ nodeGetCell(pRtree, pNode, 0, &box); for(ii=1; ii<nCell; ii++){ RtreeCell cell; nodeGetCell(pRtree, pNode, ii, &cell); cellUnion(pRtree, &box, &cell); } box.iRowid = pNode->iNode; rc = nodeParentIndex(pRtree, pNode, &ii); if( rc==SQLITE_OK ){ nodeOverwriteCell(pRtree, pParent, &box, ii); rc = fixBoundingBox(pRtree, pParent); } } return rc; } /* ** Delete the cell at index iCell of node pNode. After removing the ** cell, adjust the r-tree data structure if required. */ static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){ |
︙ | ︙ | |||
2412 2413 2414 2415 2416 2417 2418 | */ pParent = pNode->pParent; assert( pParent || pNode->iNode==1 ); if( pParent ){ if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){ rc = removeNode(pRtree, pNode, iHeight); }else{ | | | 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 | */ pParent = pNode->pParent; assert( pParent || pNode->iNode==1 ); if( pParent ){ if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){ rc = removeNode(pRtree, pNode, iHeight); }else{ rc = fixBoundingBox(pRtree, pNode); } } return rc; } static int Reinsert( |
︙ | ︙ | |||
2495 2496 2497 2498 2499 2500 2501 | rc = rowidWrite(pRtree, p->iRowid, pNode->iNode); }else{ rc = parentWrite(pRtree, p->iRowid, pNode->iNode); } } } if( rc==SQLITE_OK ){ | | | 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 | rc = rowidWrite(pRtree, p->iRowid, pNode->iNode); }else{ rc = parentWrite(pRtree, p->iRowid, pNode->iNode); } } } if( rc==SQLITE_OK ){ rc = fixBoundingBox(pRtree, pNode); } for(; rc==SQLITE_OK && ii<nCell; ii++){ /* Find a node to store this cell in. pNode->iNode currently contains ** the height of the sub-tree headed by the cell. */ RtreeNode *pInsert; RtreeCell *p = &aCell[aOrder[ii]]; |
︙ | ︙ | |||
2549 2550 2551 2552 2553 2554 2555 | pRtree->iReinsertHeight = iHeight; rc = Reinsert(pRtree, pNode, pCell, iHeight); } #else rc = SplitNode(pRtree, pNode, pCell, iHeight); #endif }else{ | | > | | | | > | 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 | pRtree->iReinsertHeight = iHeight; rc = Reinsert(pRtree, pNode, pCell, iHeight); } #else rc = SplitNode(pRtree, pNode, pCell, iHeight); #endif }else{ rc = AdjustTree(pRtree, pNode, pCell); if( rc==SQLITE_OK ){ if( iHeight==0 ){ rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); }else{ rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode); } } } return rc; } static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){ int ii; |
︙ | ︙ | |||
2648 2649 2650 2651 2652 2653 2654 | iDelete = sqlite3_value_int64(azData[0]); rc = findLeafNode(pRtree, iDelete, &pLeaf); } /* Delete the cell in question from the leaf node. */ if( rc==SQLITE_OK ){ int rc2; | | > | > | 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 | iDelete = sqlite3_value_int64(azData[0]); rc = findLeafNode(pRtree, iDelete, &pLeaf); } /* Delete the cell in question from the leaf node. */ if( rc==SQLITE_OK ){ int rc2; rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell); if( rc==SQLITE_OK ){ rc = deleteCell(pRtree, pLeaf, iCell, 0); } rc2 = nodeRelease(pRtree, pLeaf); if( rc==SQLITE_OK ){ rc = rc2; } } /* Delete the corresponding entry in the <rtree>_rowid table. */ |
︙ | ︙ |
Changes to ext/rtree/rtreeA.test.
︙ | ︙ | |||
180 181 182 183 184 185 186 | # Set the "number of entries" field on some nodes incorrectly. # create_t1 populate_t1 do_test rtreeA-4.1.0 { set_entry_count t1 1 4000 } {4000} | < > > > > > > > > > > > > > | 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | # Set the "number of entries" field on some nodes incorrectly. # create_t1 populate_t1 do_test rtreeA-4.1.0 { set_entry_count t1 1 4000 } {4000} do_corruption_tests rtreeA-4.1 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } #------------------------------------------------------------------------- # Remove entries from the %_parent table and check that this does not # cause a crash. # create_t1 populate_t1 do_execsql_test rtreeA-5.1.0 { DELETE FROM t1_parent } {} do_corruption_tests rtreeA-5.1 { 1 "DELETE FROM t1 WHERE rowid = 5" 2 "DELETE FROM t1" } #------------------------------------------------------------------------- # Add some bad entries to the %_parent table. # create_t1 populate_t1 do_execsql_test rtreeA-6.1.0 { UPDATE t1_parent set parentnode = parentnode+1 } {} do_corruption_tests rtreeA-6.1 { 1 "DELETE FROM t1 WHERE rowid = 5" } finish_test |
Changes to src/pcache1.c.
︙ | ︙ | |||
763 764 765 766 767 768 769 770 771 772 773 774 775 776 | /* ** Implementation of the sqlite3_pcache.xDestroy method. ** ** Destroy a cache allocated using pcache1Create(). */ static void pcache1Destroy(sqlite3_pcache *p){ PCache1 *pCache = (PCache1 *)p; pcache1EnterMutex(); pcache1TruncateUnsafe(pCache, 0); pcache1.nMaxPage -= pCache->nMax; pcache1.nMinPage -= pCache->nMin; pcache1EnforceMaxPage(); pcache1LeaveMutex(); sqlite3_free(pCache->apHash); | > | 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 | /* ** Implementation of the sqlite3_pcache.xDestroy method. ** ** Destroy a cache allocated using pcache1Create(). */ static void pcache1Destroy(sqlite3_pcache *p){ PCache1 *pCache = (PCache1 *)p; assert( pCache->bPurgeable || (pCache->nMax==0 && pCache->nMin==0) ); pcache1EnterMutex(); pcache1TruncateUnsafe(pCache, 0); pcache1.nMaxPage -= pCache->nMax; pcache1.nMinPage -= pCache->nMin; pcache1EnforceMaxPage(); pcache1LeaveMutex(); sqlite3_free(pCache->apHash); |
︙ | ︙ |