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 | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
7ff3574b9c581b5e1f2b6f98028106c6 |
| User & Date: | dan 2010-09-22 19:06:03 |
Context
|
2010-09-23
| ||
| 18:47 | Add tests to e_delete.test. check-in: fab3b383 user: dan tags: trunk | |
|
2010-09-22
| ||
| 19:06 | Further tests and changes to make the r-tree module more robust. check-in: 7ff3574b 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: 68a305fd 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 ... 481 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 .... 1039 1040 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 .... 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 .... 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 .... 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 .... 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 .... 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 .... 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 .... 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 .... 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 .... 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 .... 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 .... 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 |
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 );
................................................................................
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 ){
rc = 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 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.
*/
................................................................................
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 ii;
for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
assert( ii<(NCELL(pNode)-1) );
}
return ii;
}
/*
** 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){
RtreeNode *pParent = pNode->pParent;
if( pParent ){
return nodeRowidIndex(pRtree, pParent, pNode->iNode);
}
return -1;
}
/*
** Rtree virtual table module xNext method.
*/
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
................................................................................
int isEof;
rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
if( rc!=SQLITE_OK || !isEof ){
return rc;
}
}
pCsr->pNode = pNode->pParent;
pCsr->iCell = nodeParentIndex(pRtree, pNode);
nodeReference(pCsr->pNode);
nodeRelease(pRtree, pNode);
iHeight++;
}
}
return rc;
................................................................................
/* 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 );
pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
}
}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);
................................................................................
}
/*
** 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 void 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 ){
RtreeCell cell;
RtreeNode *pParent = p->pParent;
int iCell = nodeParentIndex(pRtree, p);
nodeGetCell(pRtree, pParent, iCell, &cell);
if( !cellContains(pRtree, &cell, pCell) ){
cellUnion(pRtree, &cell, pCell);
nodeOverwriteCell(pRtree, pParent, &cell, iCell);
}
p = pParent;
}
}
/*
** 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);
................................................................................
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 = nodeParentIndex(pRtree, pLeft);
nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
AdjustTree(pRtree, pParent, &leftbbox);
}
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);
................................................................................
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, locate the parent node of pLeaf and populate
** pLeaf->pParent.
*/
static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
int rc = SQLITE_OK;
if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
int rc2; /* sqlite3_reset() return code */
sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
rc = sqlite3_step(pRtree->pReadParent);
if( rc==SQLITE_ROW ){
i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
}else if( rc==SQLITE_DONE ){
rc = SQLITE_CORRUPT;
}
rc2 = sqlite3_reset(pRtree->pReadParent);
if( rc==SQLITE_OK ){
rc = rc2;
}
if( rc==SQLITE_OK ){
rc = fixLeafParent(pRtree, pLeaf->pParent);
}
}
return rc;
}
static int deleteCell(Rtree *, RtreeNode *, int, int);
static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
................................................................................
int rc2;
RtreeNode *pParent;
int iCell;
assert( pNode->nRef==1 );
/* Remove the entry in the parent cell. */
iCell = nodeParentIndex(pRtree, pNode);
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;
}
................................................................................
pNode->pNext = pRtree->pDeleted;
pNode->nRef++;
pRtree->pDeleted = pNode;
return SQLITE_OK;
}
static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
RtreeNode *pParent = pNode->pParent;
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;
ii = nodeParentIndex(pRtree, pNode);
nodeOverwriteCell(pRtree, pParent, &box, ii);
fixBoundingBox(pRtree, pParent);
}
}
/*
** 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){
................................................................................
*/
pParent = pNode->pParent;
assert( pParent || pNode->iNode==1 );
if( pParent ){
if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
rc = removeNode(pRtree, pNode, iHeight);
}else{
fixBoundingBox(pRtree, pNode);
}
}
return rc;
}
static int Reinsert(
................................................................................
rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
}else{
rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
}
}
}
if( rc==SQLITE_OK ){
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]];
................................................................................
pRtree->iReinsertHeight = iHeight;
rc = Reinsert(pRtree, pNode, pCell, iHeight);
}
#else
rc = SplitNode(pRtree, pNode, pCell, iHeight);
#endif
}else{
AdjustTree(pRtree, pNode, pCell);
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;
................................................................................
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;
iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
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. */
|
> | > | > > > > > > > | < > > | > | | | > | | > > > | | < > > > | > > > > | > | | > > > > | | | | | | | | | | | | | | | | | | | | | > | | | > | > | > | | | > > | | | > | | | | > | > | > |
458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 ... 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 .... 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 .... 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 .... 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 .... 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 .... 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 .... 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 .... 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 .... 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 .... 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 .... 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 .... 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 .... 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 |
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 );
................................................................................
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.
*/
................................................................................
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);
................................................................................
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;
................................................................................
/* 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);
................................................................................
}
/*
** 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);
................................................................................
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);
................................................................................
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 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;
}
................................................................................
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){
................................................................................
*/
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(
................................................................................
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]];
................................................................................
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;
................................................................................
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
187
188
189
190
191
192
193
194
...
199
200
201
202
203
204
205
206
207
|
# 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}
breakpoint
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"
}
................................................................................
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"
}
finish_test
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
|
180
181
182
183
184
185
186
187
188
189
190
191
192
193
...
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"
}
................................................................................
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);
|