Index: ext/rtree/geopoly.c ================================================================== --- ext/rtree/geopoly.c +++ ext/rtree/geopoly.c @@ -1254,24 +1254,27 @@ sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1); /* Allocate the sqlite3_vtab structure */ nDb = strlen(argv[1]); nName = strlen(argv[2]); - pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName+2); + pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName*2+8); if( !pRtree ){ return SQLITE_NOMEM; } - memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); + memset(pRtree, 0, sizeof(Rtree)+nDb+nName*2+8); pRtree->nBusy = 1; pRtree->base.pModule = &rtreeModule; pRtree->zDb = (char *)&pRtree[1]; pRtree->zName = &pRtree->zDb[nDb+1]; + pRtree->zNodeName = &pRtree->zName[nName+1]; pRtree->eCoordType = RTREE_COORD_REAL32; pRtree->nDim = 2; pRtree->nDim2 = 4; memcpy(pRtree->zDb, argv[1], nDb); memcpy(pRtree->zName, argv[2], nName); + memcpy(pRtree->zNodeName, argv[2], nName); + memcpy(&pRtree->zNodeName[nName], "_node", 6); /* Create/Connect to the underlying relational database schema. If ** that is successful, call sqlite3_declare_vtab() to configure ** the r-tree table schema. @@ -1681,11 +1684,10 @@ if( rc==SQLITE_OK ){ rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf); } if( rc==SQLITE_OK ){ int rc2; - pRtree->iReinsertHeight = -1; rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0); rc2 = nodeRelease(pRtree, pLeaf); if( rc==SQLITE_OK ){ rc = rc2; } Index: ext/rtree/rtree.c ================================================================== --- ext/rtree/rtree.c +++ ext/rtree/rtree.c @@ -164,10 +164,11 @@ u8 bCorrupt; /* Shadow table corruption detected */ #endif int iDepth; /* Current depth of the r-tree structure */ char *zDb; /* Name of database containing r-tree table */ char *zName; /* Name of r-tree table */ + char *zNodeName; /* Name of the %_node table */ u32 nBusy; /* Current number of users of this structure */ i64 nRowEst; /* Estimated number of rows in this table */ u32 nCursor; /* Number of open cursors */ u32 nNodeRef; /* Number RtreeNodes with positive nRef */ char *zReadAuxSql; /* SQL for statement to read aux data */ @@ -176,11 +177,10 @@ ** linked together via the pointer normally used for hash chains - ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree ** headed by the node (leaf nodes have RtreeNode.iNode==0). */ RtreeNode *pDeleted; - int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */ /* Blob I/O on xxx_node */ sqlite3_blob *pNodeBlob; /* Statements to read/write/delete a record from xxx_node */ @@ -198,11 +198,11 @@ sqlite3_stmt *pDeleteParent; /* Statement for writing to the "aux:" fields, if there are any */ sqlite3_stmt *pWriteAux; - RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ + RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ }; /* Possible values for Rtree.eCoordType: */ #define RTREE_COORD_REAL32 0 #define RTREE_COORD_INT32 1 @@ -735,15 +735,13 @@ nodeBlobReset(pRtree); if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; } } if( pRtree->pNodeBlob==0 ){ - char *zTab = sqlite3_mprintf("%s_node", pRtree->zName); - if( zTab==0 ) return SQLITE_NOMEM; - rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, zTab, "data", iNode, 0, + rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, pRtree->zNodeName, + "data", iNode, 0, &pRtree->pNodeBlob); - sqlite3_free(zTab); } if( rc ){ nodeBlobReset(pRtree); *ppNode = 0; /* If unable to open an sqlite3_blob on the desired row, that can only @@ -2080,12 +2078,16 @@ } } pIdxInfo->idxNum = 2; pIdxInfo->needToFreeIdxStr = 1; - if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ - return SQLITE_NOMEM; + if( iIdx>0 ){ + pIdxInfo->idxStr = sqlite3_malloc( iIdx+1 ); + if( pIdxInfo->idxStr==0 ){ + return SQLITE_NOMEM; + } + memcpy(pIdxInfo->idxStr, zIdxStr, iIdx+1); } nRow = pRtree->nRowEst >> (iIdx/2); pIdxInfo->estimatedCost = (double)6.0 * (double)nRow; pIdxInfo->estimatedRows = nRow; @@ -2160,35 +2162,26 @@ ** Return true if the area covered by p2 is a subset of the area covered ** by p1. False otherwise. */ static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ int ii; - int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); - for(ii=0; iinDim2; ii+=2){ - RtreeCoord *a1 = &p1->aCoord[ii]; - RtreeCoord *a2 = &p2->aCoord[ii]; - if( (!isInt && (a2[0].fa1[1].f)) - || ( isInt && (a2[0].ia1[1].i)) - ){ - return 0; + if( pRtree->eCoordType==RTREE_COORD_INT32 ){ + for(ii=0; iinDim2; ii+=2){ + RtreeCoord *a1 = &p1->aCoord[ii]; + RtreeCoord *a2 = &p2->aCoord[ii]; + if( a2[0].ia1[1].i ) return 0; + } + }else{ + for(ii=0; iinDim2; ii+=2){ + RtreeCoord *a1 = &p1->aCoord[ii]; + RtreeCoord *a2 = &p2->aCoord[ii]; + if( a2[0].fa1[1].f ) return 0; } } return 1; } -/* -** Return the amount cell p would grow by if it were unioned with pCell. -*/ -static RtreeDValue cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ - RtreeDValue area; - RtreeCell cell; - memcpy(&cell, p, sizeof(RtreeCell)); - area = cellArea(pRtree, &cell); - cellUnion(pRtree, &cell, pCell); - return (cellArea(pRtree, &cell)-area); -} - static RtreeDValue cellOverlap( Rtree *pRtree, RtreeCell *p, RtreeCell *aCell, int nCell @@ -2231,42 +2224,56 @@ rc = nodeAcquire(pRtree, 1, 0, &pNode); for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ int iCell; sqlite3_int64 iBest = 0; - + int bFound = 0; RtreeDValue fMinGrowth = RTREE_ZERO; RtreeDValue fMinArea = RTREE_ZERO; - int nCell = NCELL(pNode); - RtreeCell cell; RtreeNode *pChild = 0; - RtreeCell *aCell = 0; - - /* Select the child node which will be enlarged the least if pCell - ** is inserted into it. Resolve ties by choosing the entry with - ** the smallest area. + /* First check to see if there is are any cells in pNode that completely + ** contains pCell. If two or more cells in pNode completely contain pCell + ** then pick the smallest. */ for(iCell=0; iCell1 ){ - int iLeft = 0; - int iRight = 0; - - int nLeft = nIdx/2; - int nRight = nIdx-nLeft; - int *aLeft = aIdx; - int *aRight = &aIdx[nLeft]; - - SortByDistance(aLeft, nLeft, aDistance, aSpare); - SortByDistance(aRight, nRight, aDistance, aSpare); - - memcpy(aSpare, aLeft, sizeof(int)*nLeft); - aLeft = aSpare; - - while( iLeftnDim; iDim++){ - aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]); - aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]); - } - } - for(iDim=0; iDimnDim; iDim++){ - aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2)); - } - - for(ii=0; iinDim; iDim++){ - RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) - - DCOORD(aCell[ii].aCoord[iDim*2])); - aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]); - } - } - - SortByDistance(aOrder, nCell, aDistance, aSpare); - nodeZero(pRtree, pNode); - - for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){ - RtreeCell *p = &aCell[aOrder[ii]]; - nodeInsertCell(pRtree, pNode, p); - if( p->iRowid==pCell->iRowid ){ - if( iHeight==0 ){ - 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 && iiiNode currently contains - ** the height of the sub-tree headed by the cell. - */ - RtreeNode *pInsert; - RtreeCell *p = &aCell[aOrder[ii]]; - rc = ChooseLeaf(pRtree, p, iHeight, &pInsert); - if( rc==SQLITE_OK ){ - int rc2; - rc = rtreeInsertCell(pRtree, pInsert, p, iHeight); - rc2 = nodeRelease(pRtree, pInsert); - if( rc==SQLITE_OK ){ - rc = rc2; - } - } - } - - sqlite3_free(aCell); - return rc; -} - + /* ** Insert cell pCell into node pNode. Node pNode is the head of a ** subtree iHeight high (leaf nodes have iHeight==0). */ static int rtreeInsertCell( @@ -3011,16 +2846,11 @@ nodeReference(pNode); pChild->pParent = pNode; } } if( nodeInsertCell(pRtree, pNode, pCell) ){ - if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ - rc = SplitNode(pRtree, pNode, pCell, iHeight); - }else{ - pRtree->iReinsertHeight = iHeight; - rc = Reinsert(pRtree, pNode, pCell, iHeight); - } + rc = SplitNode(pRtree, pNode, pCell, iHeight); }else{ rc = AdjustTree(pRtree, pNode, pCell); if( ALWAYS(rc==SQLITE_OK) ){ if( iHeight==0 ){ rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); @@ -3359,11 +3189,10 @@ if( rc==SQLITE_OK ){ rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf); } if( rc==SQLITE_OK ){ int rc2; - pRtree->iReinsertHeight = -1; rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0); rc2 = nodeRelease(pRtree, pLeaf); if( rc==SQLITE_OK ){ rc = rc2; } @@ -3788,22 +3617,25 @@ sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1); /* Allocate the sqlite3_vtab structure */ nDb = (int)strlen(argv[1]); nName = (int)strlen(argv[2]); - pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName+2); + pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName*2+8); if( !pRtree ){ return SQLITE_NOMEM; } - memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); + memset(pRtree, 0, sizeof(Rtree)+nDb+nName*2+8); pRtree->nBusy = 1; pRtree->base.pModule = &rtreeModule; pRtree->zDb = (char *)&pRtree[1]; pRtree->zName = &pRtree->zDb[nDb+1]; + pRtree->zNodeName = &pRtree->zName[nName+1]; pRtree->eCoordType = (u8)eCoordType; memcpy(pRtree->zDb, argv[1], nDb); memcpy(pRtree->zName, argv[2], nName); + memcpy(pRtree->zNodeName, argv[2], nName); + memcpy(&pRtree->zNodeName[nName], "_node", 6); /* Create/Connect to the underlying relational database schema. If ** that is successful, call sqlite3_declare_vtab() to configure ** the r-tree table schema. Index: ext/rtree/rtree8.test ================================================================== --- ext/rtree/rtree8.test +++ ext/rtree/rtree8.test @@ -73,11 +73,11 @@ # table, causing a collision in the hash-table used to store r-tree # nodes internally. # populate_t1 1500 do_rtree_integrity_test rtree8-1.3.0 t1 -do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {164} +do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {183} do_test rtree8-1.3.2 { set rowids [execsql {SELECT min(rowid) FROM t1_rowid GROUP BY nodeno}] set stmt_list [list] foreach row $rowids { set stmt [sqlite3_prepare db "SELECT * FROM t1 WHERE id = $row" -1 tail] Index: ext/rtree/rtreeA.test ================================================================== --- ext/rtree/rtreeA.test +++ ext/rtree/rtreeA.test @@ -111,11 +111,11 @@ do_execsql_test rtreeA-1.1.1 { SELECT rtreecheck('main', 't1') } {{Node 1 missing from database Wrong number of entries in %_rowid table - expected 0, actual 500 -Wrong number of entries in %_parent table - expected 0, actual 23}} +Wrong number of entries in %_parent table - expected 0, actual 25}} do_execsql_test rtreeA-1.2.0 { DROP TABLE t1_node } {} do_corruption_tests rtreeA-1.2 -error "database disk image is malformed" { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" @@ -189,11 +189,11 @@ do_execsql_test rtreeA-3.3.3.4 { SELECT rtreecheck('main', 't1') } {{Rtree depth out of range (65535) Wrong number of entries in %_rowid table - expected 0, actual 499 -Wrong number of entries in %_parent table - expected 0, actual 23}} +Wrong number of entries in %_parent table - expected 0, actual 25}} #------------------------------------------------------------------------- # Set the "number of entries" field on some nodes incorrectly. # create_t1 Index: ext/rtree/rtreedoc.test ================================================================== --- ext/rtree/rtreedoc.test +++ ext/rtree/rtreedoc.test @@ -599,15 +599,25 @@ } {$step < 100} do_execsql_test 2.5.2 { SELECT A.id FROM demo_index AS A, demo_index AS B WHERE A.maxX>=B.minX AND A.minX<=B.maxX AND A.maxY>=B.minY AND A.minY<=B.maxY - AND B.id=28269; + AND B.id=28269 ORDER BY +A.id; } { - 28293 28216 28322 28286 28269 - 28215 28336 28262 28291 28320 - 28313 28298 28287 + 28215 + 28216 + 28262 + 28269 + 28286 + 28287 + 28291 + 28293 + 28298 + 28313 + 28320 + 28322 + 28336 } # EVIDENCE-OF: R-02723-34107 Note that it is not necessary for all # coordinates in an R*Tree index to be constrained in order for the # index search to be efficient. @@ -1573,11 +1583,11 @@ # entry in the %_parent table. execsql BEGIN do_test 3.6 { execsql { INSERT INTO rt2_parent VALUES(1000, 1000) } execsql { SELECT rtreecheck('rt2') } -} {{Wrong number of entries in %_parent table - expected 9, actual 10}} +} {{Wrong number of entries in %_parent table - expected 10, actual 11}} execsql ROLLBACK finish_test Index: ext/rtree/rtreefuzz001.test ================================================================== --- ext/rtree/rtreefuzz001.test +++ ext/rtree/rtreefuzz001.test @@ -1041,11 +1041,11 @@ | 2880: ff ff ff 06 00 00 00 0c 00 00 00 01 00 00 00 0b ................ | 2896: 00 00 00 00 00 00 00 02 40 00 00 00 00 00 00 00 ........@....... | end crash-2e81f5dce5cbd4.db}] execsql { PRAGMA writable_schema = 1;} catchsql {UPDATE t1 SET ex= ex ISNULL} -} {1 {database disk image is malformed}} +} {0 {}} do_test rtreefuzz001-600 { sqlite3 db {} db deserialize [decode_hexdb { | size 20480 pagesize 4096 filename crash-7b37d80f000235.db