| /* |
| ** 2001 September 15 |
| ** |
| ** The author disclaims copyright to this source code. In place of |
| ** a legal notice, here is a blessing: |
| ** |
| ** May you do good and not evil. |
| ** May you find forgiveness for yourself and forgive others. |
| ** May you share freely, never taking more than you give. |
| ** |
| ************************************************************************* |
| ** This file contains code for implementations of the r-tree and r*-tree |
| ** algorithms packaged as an SQLite virtual table module. |
| */ |
| |
| /* |
| ** Database Format of R-Tree Tables |
| ** -------------------------------- |
| ** |
| ** The data structure for a single virtual r-tree table is stored in three |
| ** native SQLite tables declared as follows. In each case, the '%' character |
| ** in the table name is replaced with the user-supplied name of the r-tree |
| ** table. |
| ** |
| ** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB) |
| ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) |
| ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER) |
| ** |
| ** The data for each node of the r-tree structure is stored in the %_node |
| ** table. For each node that is not the root node of the r-tree, there is |
| ** an entry in the %_parent table associating the node with its parent. |
| ** And for each row of data in the table, there is an entry in the %_rowid |
| ** table that maps from the entries rowid to the id of the node that it |
| ** is stored on. |
| ** |
| ** The root node of an r-tree always exists, even if the r-tree table is |
| ** empty. The nodeno of the root node is always 1. All other nodes in the |
| ** table must be the same size as the root node. The content of each node |
| ** is formatted as follows: |
| ** |
| ** 1. If the node is the root node (node 1), then the first 2 bytes |
| ** of the node contain the tree depth as a big-endian integer. |
| ** For non-root nodes, the first 2 bytes are left unused. |
| ** |
| ** 2. The next 2 bytes contain the number of entries currently |
| ** stored in the node. |
| ** |
| ** 3. The remainder of the node contains the node entries. Each entry |
| ** consists of a single 8-byte integer followed by an even number |
| ** of 4-byte coordinates. For leaf nodes the integer is the rowid |
| ** of a record. For internal nodes it is the node number of a |
| ** child page. |
| */ |
| |
| #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) |
| |
| /* |
| ** This file contains an implementation of a couple of different variants |
| ** of the r-tree algorithm. See the README file for further details. The |
| ** same data-structure is used for all, but the algorithms for insert and |
| ** delete operations vary. The variants used are selected at compile time |
| ** by defining the following symbols: |
| */ |
| |
| /* Either, both or none of the following may be set to activate |
| ** r*tree variant algorithms. |
| */ |
| #define VARIANT_RSTARTREE_CHOOSESUBTREE 0 |
| #define VARIANT_RSTARTREE_REINSERT 1 |
| |
| /* |
| ** Exactly one of the following must be set to 1. |
| */ |
| #define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0 |
| #define VARIANT_GUTTMAN_LINEAR_SPLIT 0 |
| #define VARIANT_RSTARTREE_SPLIT 1 |
| |
| #define VARIANT_GUTTMAN_SPLIT \ |
| (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT) |
| |
| #if VARIANT_GUTTMAN_QUADRATIC_SPLIT |
| #define PickNext QuadraticPickNext |
| #define PickSeeds QuadraticPickSeeds |
| #define AssignCells splitNodeGuttman |
| #endif |
| #if VARIANT_GUTTMAN_LINEAR_SPLIT |
| #define PickNext LinearPickNext |
| #define PickSeeds LinearPickSeeds |
| #define AssignCells splitNodeGuttman |
| #endif |
| #if VARIANT_RSTARTREE_SPLIT |
| #define AssignCells splitNodeStartree |
| #endif |
| |
| #if !defined(NDEBUG) && !defined(SQLITE_DEBUG) |
| # define NDEBUG 1 |
| #endif |
| |
| #ifndef SQLITE_CORE |
| #include "sqlite3ext.h" |
| SQLITE_EXTENSION_INIT1 |
| #else |
| #include "sqlite3.h" |
| #endif |
| |
| #include <string.h> |
| #include <assert.h> |
| |
| #ifndef SQLITE_AMALGAMATION |
| #include "sqlite3rtree.h" |
| typedef sqlite3_int64 i64; |
| typedef unsigned char u8; |
| typedef unsigned int u32; |
| #endif |
| |
| /* The following macro is used to suppress compiler warnings. |
| */ |
| #ifndef UNUSED_PARAMETER |
| # define UNUSED_PARAMETER(x) (void)(x) |
| #endif |
| |
| typedef struct Rtree Rtree; |
| typedef struct RtreeCursor RtreeCursor; |
| typedef struct RtreeNode RtreeNode; |
| typedef struct RtreeCell RtreeCell; |
| typedef struct RtreeConstraint RtreeConstraint; |
| typedef struct RtreeMatchArg RtreeMatchArg; |
| typedef struct RtreeGeomCallback RtreeGeomCallback; |
| typedef union RtreeCoord RtreeCoord; |
| |
| /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ |
| #define RTREE_MAX_DIMENSIONS 5 |
| |
| /* Size of hash table Rtree.aHash. This hash table is not expected to |
| ** ever contain very many entries, so a fixed number of buckets is |
| ** used. |
| */ |
| #define HASHSIZE 128 |
| |
| /* |
| ** An rtree virtual-table object. |
| */ |
| struct Rtree { |
| sqlite3_vtab base; |
| sqlite3 *db; /* Host database connection */ |
| int iNodeSize; /* Size in bytes of each node in the node table */ |
| int nDim; /* Number of dimensions */ |
| int nBytesPerCell; /* Bytes consumed per cell */ |
| 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 */ |
| RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ |
| int nBusy; /* Current number of users of this structure */ |
| |
| /* List of nodes removed during a CondenseTree operation. List is |
| ** 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 */ |
| |
| /* Statements to read/write/delete a record from xxx_node */ |
| sqlite3_stmt *pReadNode; |
| sqlite3_stmt *pWriteNode; |
| sqlite3_stmt *pDeleteNode; |
| |
| /* Statements to read/write/delete a record from xxx_rowid */ |
| sqlite3_stmt *pReadRowid; |
| sqlite3_stmt *pWriteRowid; |
| sqlite3_stmt *pDeleteRowid; |
| |
| /* Statements to read/write/delete a record from xxx_parent */ |
| sqlite3_stmt *pReadParent; |
| sqlite3_stmt *pWriteParent; |
| sqlite3_stmt *pDeleteParent; |
| |
| int eCoordType; |
| }; |
| |
| /* Possible values for eCoordType: */ |
| #define RTREE_COORD_REAL32 0 |
| #define RTREE_COORD_INT32 1 |
| |
| /* |
| ** The minimum number of cells allowed for a node is a third of the |
| ** maximum. In Gutman's notation: |
| ** |
| ** m = M/3 |
| ** |
| ** If an R*-tree "Reinsert" operation is required, the same number of |
| ** cells are removed from the overfull node and reinserted into the tree. |
| */ |
| #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3) |
| #define RTREE_REINSERT(p) RTREE_MINCELLS(p) |
| #define RTREE_MAXCELLS 51 |
| |
| /* |
| ** The smallest possible node-size is (512-64)==448 bytes. And the largest |
| ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates). |
| ** Therefore all non-root nodes must contain at least 3 entries. Since |
| ** 2^40 is greater than 2^64, an r-tree structure always has a depth of |
| ** 40 or less. |
| */ |
| #define RTREE_MAX_DEPTH 40 |
| |
| /* |
| ** An rtree cursor object. |
| */ |
| struct RtreeCursor { |
| sqlite3_vtab_cursor base; |
| RtreeNode *pNode; /* Node cursor is currently pointing at */ |
| int iCell; /* Index of current cell in pNode */ |
| int iStrategy; /* Copy of idxNum search parameter */ |
| int nConstraint; /* Number of entries in aConstraint */ |
| RtreeConstraint *aConstraint; /* Search constraints. */ |
| }; |
| |
| union RtreeCoord { |
| float f; |
| int i; |
| }; |
| |
| /* |
| ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord |
| ** formatted as a double. This macro assumes that local variable pRtree points |
| ** to the Rtree structure associated with the RtreeCoord. |
| */ |
| #define DCOORD(coord) ( \ |
| (pRtree->eCoordType==RTREE_COORD_REAL32) ? \ |
| ((double)coord.f) : \ |
| ((double)coord.i) \ |
| ) |
| |
| /* |
| ** A search constraint. |
| */ |
| struct RtreeConstraint { |
| int iCoord; /* Index of constrained coordinate */ |
| int op; /* Constraining operation */ |
| double rValue; /* Constraint value. */ |
| int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *); |
| sqlite3_rtree_geometry *pGeom; /* Constraint callback argument for a MATCH */ |
| }; |
| |
| /* Possible values for RtreeConstraint.op */ |
| #define RTREE_EQ 0x41 |
| #define RTREE_LE 0x42 |
| #define RTREE_LT 0x43 |
| #define RTREE_GE 0x44 |
| #define RTREE_GT 0x45 |
| #define RTREE_MATCH 0x46 |
| |
| /* |
| ** An rtree structure node. |
| */ |
| struct RtreeNode { |
| RtreeNode *pParent; /* Parent node */ |
| i64 iNode; |
| int nRef; |
| int isDirty; |
| u8 *zData; |
| RtreeNode *pNext; /* Next node in this hash chain */ |
| }; |
| #define NCELL(pNode) readInt16(&(pNode)->zData[2]) |
| |
| /* |
| ** Structure to store a deserialized rtree record. |
| */ |
| struct RtreeCell { |
| i64 iRowid; |
| RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; |
| }; |
| |
| |
| /* |
| ** Value for the first field of every RtreeMatchArg object. The MATCH |
| ** operator tests that the first field of a blob operand matches this |
| ** value to avoid operating on invalid blobs (which could cause a segfault). |
| */ |
| #define RTREE_GEOMETRY_MAGIC 0x891245AB |
| |
| /* |
| ** An instance of this structure must be supplied as a blob argument to |
| ** the right-hand-side of an SQL MATCH operator used to constrain an |
| ** r-tree query. |
| */ |
| struct RtreeMatchArg { |
| u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ |
| int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *); |
| void *pContext; |
| int nParam; |
| double aParam[1]; |
| }; |
| |
| /* |
| ** When a geometry callback is created (see sqlite3_rtree_geometry_callback), |
| ** a single instance of the following structure is allocated. It is used |
| ** as the context for the user-function created by by s_r_g_c(). The object |
| ** is eventually deleted by the destructor mechanism provided by |
| ** sqlite3_create_function_v2() (which is called by s_r_g_c() to create |
| ** the geometry callback function). |
| */ |
| struct RtreeGeomCallback { |
| int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *); |
| void *pContext; |
| }; |
| |
| #ifndef MAX |
| # define MAX(x,y) ((x) < (y) ? (y) : (x)) |
| #endif |
| #ifndef MIN |
| # define MIN(x,y) ((x) > (y) ? (y) : (x)) |
| #endif |
| |
| /* |
| ** Functions to deserialize a 16 bit integer, 32 bit real number and |
| ** 64 bit integer. The deserialized value is returned. |
| */ |
| static int readInt16(u8 *p){ |
| return (p[0]<<8) + p[1]; |
| } |
| static void readCoord(u8 *p, RtreeCoord *pCoord){ |
| u32 i = ( |
| (((u32)p[0]) << 24) + |
| (((u32)p[1]) << 16) + |
| (((u32)p[2]) << 8) + |
| (((u32)p[3]) << 0) |
| ); |
| *(u32 *)pCoord = i; |
| } |
| static i64 readInt64(u8 *p){ |
| return ( |
| (((i64)p[0]) << 56) + |
| (((i64)p[1]) << 48) + |
| (((i64)p[2]) << 40) + |
| (((i64)p[3]) << 32) + |
| (((i64)p[4]) << 24) + |
| (((i64)p[5]) << 16) + |
| (((i64)p[6]) << 8) + |
| (((i64)p[7]) << 0) |
| ); |
| } |
| |
| /* |
| ** Functions to serialize a 16 bit integer, 32 bit real number and |
| ** 64 bit integer. The value returned is the number of bytes written |
| ** to the argument buffer (always 2, 4 and 8 respectively). |
| */ |
| static int writeInt16(u8 *p, int i){ |
| p[0] = (i>> 8)&0xFF; |
| p[1] = (i>> 0)&0xFF; |
| return 2; |
| } |
| static int writeCoord(u8 *p, RtreeCoord *pCoord){ |
| u32 i; |
| assert( sizeof(RtreeCoord)==4 ); |
| assert( sizeof(u32)==4 ); |
| i = *(u32 *)pCoord; |
| p[0] = (i>>24)&0xFF; |
| p[1] = (i>>16)&0xFF; |
| p[2] = (i>> 8)&0xFF; |
| p[3] = (i>> 0)&0xFF; |
| return 4; |
| } |
| static int writeInt64(u8 *p, i64 i){ |
| p[0] = (i>>56)&0xFF; |
| p[1] = (i>>48)&0xFF; |
| p[2] = (i>>40)&0xFF; |
| p[3] = (i>>32)&0xFF; |
| p[4] = (i>>24)&0xFF; |
| p[5] = (i>>16)&0xFF; |
| p[6] = (i>> 8)&0xFF; |
| p[7] = (i>> 0)&0xFF; |
| return 8; |
| } |
| |
| /* |
| ** Increment the reference count of node p. |
| */ |
| static void nodeReference(RtreeNode *p){ |
| if( p ){ |
| p->nRef++; |
| } |
| } |
| |
| /* |
| ** Clear the content of node p (set all bytes to 0x00). |
| */ |
| static void nodeZero(Rtree *pRtree, RtreeNode *p){ |
| memset(&p->zData[2], 0, pRtree->iNodeSize-2); |
| p->isDirty = 1; |
| } |
| |
| /* |
| ** Given a node number iNode, return the corresponding key to use |
| ** in the Rtree.aHash table. |
| */ |
| static int nodeHash(i64 iNode){ |
| return ( |
| (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ |
| (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0) |
| ) % HASHSIZE; |
| } |
| |
| /* |
| ** Search the node hash table for node iNode. If found, return a pointer |
| ** to it. Otherwise, return 0. |
| */ |
| static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ |
| RtreeNode *p; |
| for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); |
| return p; |
| } |
| |
| /* |
| ** Add node pNode to the node hash table. |
| */ |
| static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ |
| int iHash; |
| assert( pNode->pNext==0 ); |
| iHash = nodeHash(pNode->iNode); |
| pNode->pNext = pRtree->aHash[iHash]; |
| pRtree->aHash[iHash] = pNode; |
| } |
| |
| /* |
| ** Remove node pNode from the node hash table. |
| */ |
| static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){ |
| RtreeNode **pp; |
| if( pNode->iNode!=0 ){ |
| pp = &pRtree->aHash[nodeHash(pNode->iNode)]; |
| for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); } |
| *pp = pNode->pNext; |
| pNode->pNext = 0; |
| } |
| } |
| |
| /* |
| ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0), |
| ** indicating that node has not yet been assigned a node number. It is |
| ** assigned a node number when nodeWrite() is called to write the |
| ** node contents out to the database. |
| */ |
| static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){ |
| RtreeNode *pNode; |
| pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize); |
| if( pNode ){ |
| memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize); |
| pNode->zData = (u8 *)&pNode[1]; |
| pNode->nRef = 1; |
| pNode->pParent = pParent; |
| pNode->isDirty = 1; |
| nodeReference(pParent); |
| } |
| return pNode; |
| } |
| |
| /* |
| ** Obtain a reference to an r-tree node. |
| */ |
| static int |
| 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 ); |
| if( pParent && !pNode->pParent ){ |
| nodeReference(pParent); |
| pNode->pParent = pParent; |
| } |
| pNode->nRef++; |
| *ppNode = pNode; |
| return SQLITE_OK; |
| } |
| |
| 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. |
| */ |
| if( pNode && iNode==1 ){ |
| pRtree->iDepth = readInt16(pNode->zData); |
| if( pRtree->iDepth>RTREE_MAX_DEPTH ){ |
| rc = SQLITE_CORRUPT; |
| } |
| } |
| |
| /* If no error has occurred so far, check if the "number of entries" |
| ** field on the node is too large. If so, set the return code to |
| ** SQLITE_CORRUPT. |
| */ |
| if( pNode && rc==SQLITE_OK ){ |
| if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ |
| rc = SQLITE_CORRUPT; |
| } |
| } |
| |
| if( rc==SQLITE_OK ){ |
| if( pNode!=0 ){ |
| nodeHashInsert(pRtree, pNode); |
| }else{ |
| rc = SQLITE_CORRUPT; |
| } |
| *ppNode = pNode; |
| }else{ |
| sqlite3_free(pNode); |
| *ppNode = 0; |
| } |
| |
| return rc; |
| } |
| |
| /* |
| ** Overwrite cell iCell of node pNode with the contents of pCell. |
| */ |
| static void nodeOverwriteCell( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| RtreeCell *pCell, |
| int iCell |
| ){ |
| int ii; |
| u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
| p += writeInt64(p, pCell->iRowid); |
| for(ii=0; ii<(pRtree->nDim*2); ii++){ |
| p += writeCoord(p, &pCell->aCoord[ii]); |
| } |
| pNode->isDirty = 1; |
| } |
| |
| /* |
| ** Remove cell the cell with index iCell from node pNode. |
| */ |
| static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ |
| u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
| u8 *pSrc = &pDst[pRtree->nBytesPerCell]; |
| int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell; |
| memmove(pDst, pSrc, nByte); |
| writeInt16(&pNode->zData[2], NCELL(pNode)-1); |
| pNode->isDirty = 1; |
| } |
| |
| /* |
| ** Insert the contents of cell pCell into node pNode. If the insert |
| ** is successful, return SQLITE_OK. |
| ** |
| ** If there is not enough free space in pNode, return SQLITE_FULL. |
| */ |
| static int |
| nodeInsertCell( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| RtreeCell *pCell |
| ){ |
| int nCell; /* Current number of cells in pNode */ |
| int nMaxCell; /* Maximum number of cells for pNode */ |
| |
| nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; |
| nCell = NCELL(pNode); |
| |
| assert( nCell<=nMaxCell ); |
| if( nCell<nMaxCell ){ |
| nodeOverwriteCell(pRtree, pNode, pCell, nCell); |
| writeInt16(&pNode->zData[2], nCell+1); |
| pNode->isDirty = 1; |
| } |
| |
| return (nCell==nMaxCell); |
| } |
| |
| /* |
| ** If the node is dirty, write it out to the database. |
| */ |
| static int |
| nodeWrite(Rtree *pRtree, RtreeNode *pNode){ |
| int rc = SQLITE_OK; |
| if( pNode->isDirty ){ |
| sqlite3_stmt *p = pRtree->pWriteNode; |
| if( pNode->iNode ){ |
| sqlite3_bind_int64(p, 1, pNode->iNode); |
| }else{ |
| sqlite3_bind_null(p, 1); |
| } |
| sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC); |
| sqlite3_step(p); |
| pNode->isDirty = 0; |
| rc = sqlite3_reset(p); |
| if( pNode->iNode==0 && rc==SQLITE_OK ){ |
| pNode->iNode = sqlite3_last_insert_rowid(pRtree->db); |
| nodeHashInsert(pRtree, pNode); |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** Release a reference to a node. If the node is dirty and the reference |
| ** count drops to zero, the node data is written to the database. |
| */ |
| static int |
| nodeRelease(Rtree *pRtree, RtreeNode *pNode){ |
| int rc = SQLITE_OK; |
| if( pNode ){ |
| assert( pNode->nRef>0 ); |
| pNode->nRef--; |
| if( pNode->nRef==0 ){ |
| if( pNode->iNode==1 ){ |
| pRtree->iDepth = -1; |
| } |
| if( pNode->pParent ){ |
| rc = nodeRelease(pRtree, pNode->pParent); |
| } |
| if( rc==SQLITE_OK ){ |
| rc = nodeWrite(pRtree, pNode); |
| } |
| nodeHashDelete(pRtree, pNode); |
| sqlite3_free(pNode); |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** Return the 64-bit integer value associated with cell iCell of |
| ** node pNode. If pNode is a leaf node, this is a rowid. If it is |
| ** an internal node, then the 64-bit integer is a child page number. |
| */ |
| static i64 nodeGetRowid( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| int iCell |
| ){ |
| assert( iCell<NCELL(pNode) ); |
| return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); |
| } |
| |
| /* |
| ** Return coordinate iCoord from cell iCell in node pNode. |
| */ |
| static void nodeGetCoord( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| int iCell, |
| int iCoord, |
| RtreeCoord *pCoord /* Space to write result to */ |
| ){ |
| readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); |
| } |
| |
| /* |
| ** Deserialize cell iCell of node pNode. Populate the structure pointed |
| ** to by pCell with the results. |
| */ |
| static void nodeGetCell( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| int iCell, |
| RtreeCell *pCell |
| ){ |
| int ii; |
| pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); |
| for(ii=0; ii<pRtree->nDim*2; ii++){ |
| nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]); |
| } |
| } |
| |
| |
| /* Forward declaration for the function that does the work of |
| ** the virtual table module xCreate() and xConnect() methods. |
| */ |
| static int rtreeInit( |
| sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int |
| ); |
| |
| /* |
| ** Rtree virtual table module xCreate method. |
| */ |
| static int rtreeCreate( |
| sqlite3 *db, |
| void *pAux, |
| int argc, const char *const*argv, |
| sqlite3_vtab **ppVtab, |
| char **pzErr |
| ){ |
| return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1); |
| } |
| |
| /* |
| ** Rtree virtual table module xConnect method. |
| */ |
| static int rtreeConnect( |
| sqlite3 *db, |
| void *pAux, |
| int argc, const char *const*argv, |
| sqlite3_vtab **ppVtab, |
| char **pzErr |
| ){ |
| return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0); |
| } |
| |
| /* |
| ** Increment the r-tree reference count. |
| */ |
| static void rtreeReference(Rtree *pRtree){ |
| pRtree->nBusy++; |
| } |
| |
| /* |
| ** Decrement the r-tree reference count. When the reference count reaches |
| ** zero the structure is deleted. |
| */ |
| static void rtreeRelease(Rtree *pRtree){ |
| pRtree->nBusy--; |
| if( pRtree->nBusy==0 ){ |
| sqlite3_finalize(pRtree->pReadNode); |
| sqlite3_finalize(pRtree->pWriteNode); |
| sqlite3_finalize(pRtree->pDeleteNode); |
| sqlite3_finalize(pRtree->pReadRowid); |
| sqlite3_finalize(pRtree->pWriteRowid); |
| sqlite3_finalize(pRtree->pDeleteRowid); |
| sqlite3_finalize(pRtree->pReadParent); |
| sqlite3_finalize(pRtree->pWriteParent); |
| sqlite3_finalize(pRtree->pDeleteParent); |
| sqlite3_free(pRtree); |
| } |
| } |
| |
| /* |
| ** Rtree virtual table module xDisconnect method. |
| */ |
| static int rtreeDisconnect(sqlite3_vtab *pVtab){ |
| rtreeRelease((Rtree *)pVtab); |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Rtree virtual table module xDestroy method. |
| */ |
| static int rtreeDestroy(sqlite3_vtab *pVtab){ |
| Rtree *pRtree = (Rtree *)pVtab; |
| int rc; |
| char *zCreate = sqlite3_mprintf( |
| "DROP TABLE '%q'.'%q_node';" |
| "DROP TABLE '%q'.'%q_rowid';" |
| "DROP TABLE '%q'.'%q_parent';", |
| pRtree->zDb, pRtree->zName, |
| pRtree->zDb, pRtree->zName, |
| pRtree->zDb, pRtree->zName |
| ); |
| if( !zCreate ){ |
| rc = SQLITE_NOMEM; |
| }else{ |
| rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); |
| sqlite3_free(zCreate); |
| } |
| if( rc==SQLITE_OK ){ |
| rtreeRelease(pRtree); |
| } |
| |
| return rc; |
| } |
| |
| /* |
| ** Rtree virtual table module xOpen method. |
| */ |
| static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
| int rc = SQLITE_NOMEM; |
| RtreeCursor *pCsr; |
| |
| pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor)); |
| if( pCsr ){ |
| memset(pCsr, 0, sizeof(RtreeCursor)); |
| pCsr->base.pVtab = pVTab; |
| rc = SQLITE_OK; |
| } |
| *ppCursor = (sqlite3_vtab_cursor *)pCsr; |
| |
| return rc; |
| } |
| |
| |
| /* |
| ** Free the RtreeCursor.aConstraint[] array and its contents. |
| */ |
| static void freeCursorConstraints(RtreeCursor *pCsr){ |
| if( pCsr->aConstraint ){ |
| int i; /* Used to iterate through constraint array */ |
| for(i=0; i<pCsr->nConstraint; i++){ |
| sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom; |
| if( pGeom ){ |
| if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser); |
| sqlite3_free(pGeom); |
| } |
| } |
| sqlite3_free(pCsr->aConstraint); |
| pCsr->aConstraint = 0; |
| } |
| } |
| |
| /* |
| ** Rtree virtual table module xClose method. |
| */ |
| static int rtreeClose(sqlite3_vtab_cursor *cur){ |
| Rtree *pRtree = (Rtree *)(cur->pVtab); |
| int rc; |
| RtreeCursor *pCsr = (RtreeCursor *)cur; |
| freeCursorConstraints(pCsr); |
| rc = nodeRelease(pRtree, pCsr->pNode); |
| sqlite3_free(pCsr); |
| return rc; |
| } |
| |
| /* |
| ** Rtree virtual table module xEof method. |
| ** |
| ** Return non-zero if the cursor does not currently point to a valid |
| ** record (i.e if the scan has finished), or zero otherwise. |
| */ |
| static int rtreeEof(sqlite3_vtab_cursor *cur){ |
| RtreeCursor *pCsr = (RtreeCursor *)cur; |
| return (pCsr->pNode==0); |
| } |
| |
| /* |
| ** The r-tree constraint passed as the second argument to this function is |
| ** guaranteed to be a MATCH constraint. |
| */ |
| static int testRtreeGeom( |
| Rtree *pRtree, /* R-Tree object */ |
| RtreeConstraint *pConstraint, /* MATCH constraint to test */ |
| RtreeCell *pCell, /* Cell to test */ |
| int *pbRes /* OUT: Test result */ |
| ){ |
| int i; |
| double aCoord[RTREE_MAX_DIMENSIONS*2]; |
| int nCoord = pRtree->nDim*2; |
| |
| assert( pConstraint->op==RTREE_MATCH ); |
| assert( pConstraint->pGeom ); |
| |
| for(i=0; i<nCoord; i++){ |
| aCoord[i] = DCOORD(pCell->aCoord[i]); |
| } |
| return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes); |
| } |
| |
| /* |
| ** Cursor pCursor currently points to a cell in a non-leaf page. |
| ** Set *pbEof to true if the sub-tree headed by the cell is filtered |
| ** (excluded) by the constraints in the pCursor->aConstraint[] |
| ** array, or false otherwise. |
| ** |
| ** Return SQLITE_OK if successful or an SQLite error code if an error |
| ** occurs within a geometry callback. |
| */ |
| static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){ |
| RtreeCell cell; |
| int ii; |
| int bRes = 0; |
| int rc = SQLITE_OK; |
| |
| nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); |
| for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){ |
| RtreeConstraint *p = &pCursor->aConstraint[ii]; |
| double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]); |
| double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]); |
| |
| assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
| || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH |
| ); |
| |
| switch( p->op ){ |
| case RTREE_LE: case RTREE_LT: |
| bRes = p->rValue<cell_min; |
| break; |
| |
| case RTREE_GE: case RTREE_GT: |
| bRes = p->rValue>cell_max; |
| break; |
| |
| case RTREE_EQ: |
| bRes = (p->rValue>cell_max || p->rValue<cell_min); |
| break; |
| |
| default: { |
| assert( p->op==RTREE_MATCH ); |
| rc = testRtreeGeom(pRtree, p, &cell, &bRes); |
| bRes = !bRes; |
| break; |
| } |
| } |
| } |
| |
| *pbEof = bRes; |
| return rc; |
| } |
| |
| /* |
| ** Test if the cell that cursor pCursor currently points to |
| ** would be filtered (excluded) by the constraints in the |
| ** pCursor->aConstraint[] array. If so, set *pbEof to true before |
| ** returning. If the cell is not filtered (excluded) by the constraints, |
| ** set pbEof to zero. |
| ** |
| ** Return SQLITE_OK if successful or an SQLite error code if an error |
| ** occurs within a geometry callback. |
| ** |
| ** This function assumes that the cell is part of a leaf node. |
| */ |
| static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){ |
| RtreeCell cell; |
| int ii; |
| *pbEof = 0; |
| |
| nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); |
| for(ii=0; ii<pCursor->nConstraint; ii++){ |
| RtreeConstraint *p = &pCursor->aConstraint[ii]; |
| double coord = DCOORD(cell.aCoord[p->iCoord]); |
| int res; |
| assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
| || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH |
| ); |
| switch( p->op ){ |
| case RTREE_LE: res = (coord<=p->rValue); break; |
| case RTREE_LT: res = (coord<p->rValue); break; |
| case RTREE_GE: res = (coord>=p->rValue); break; |
| case RTREE_GT: res = (coord>p->rValue); break; |
| case RTREE_EQ: res = (coord==p->rValue); break; |
| default: { |
| int rc; |
| assert( p->op==RTREE_MATCH ); |
| rc = testRtreeGeom(pRtree, p, &cell, &res); |
| if( rc!=SQLITE_OK ){ |
| return rc; |
| } |
| break; |
| } |
| } |
| |
| if( !res ){ |
| *pbEof = 1; |
| return SQLITE_OK; |
| } |
| } |
| |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Cursor pCursor currently points at a node that heads a sub-tree of |
| ** height iHeight (if iHeight==0, then the node is a leaf). Descend |
| ** to point to the left-most cell of the sub-tree that matches the |
| ** configured constraints. |
| */ |
| static int descendToCell( |
| Rtree *pRtree, |
| RtreeCursor *pCursor, |
| int iHeight, |
| int *pEof /* OUT: Set to true if cannot descend */ |
| ){ |
| int isEof; |
| int rc; |
| int ii; |
| RtreeNode *pChild; |
| sqlite3_int64 iRowid; |
| |
| RtreeNode *pSavedNode = pCursor->pNode; |
| int iSavedCell = pCursor->iCell; |
| |
| assert( iHeight>=0 ); |
| |
| if( iHeight==0 ){ |
| rc = testRtreeEntry(pRtree, pCursor, &isEof); |
| }else{ |
| rc = testRtreeCell(pRtree, pCursor, &isEof); |
| } |
| if( rc!=SQLITE_OK || isEof || iHeight==0 ){ |
| goto descend_to_cell_out; |
| } |
| |
| iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell); |
| rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild); |
| if( rc!=SQLITE_OK ){ |
| goto descend_to_cell_out; |
| } |
| |
| nodeRelease(pRtree, pCursor->pNode); |
| pCursor->pNode = pChild; |
| isEof = 1; |
| for(ii=0; isEof && ii<NCELL(pChild); ii++){ |
| pCursor->iCell = ii; |
| rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof); |
| if( rc!=SQLITE_OK ){ |
| goto descend_to_cell_out; |
| } |
| } |
| |
| if( isEof ){ |
| assert( pCursor->pNode==pChild ); |
| nodeReference(pSavedNode); |
| nodeRelease(pRtree, pChild); |
| pCursor->pNode = pSavedNode; |
| pCursor->iCell = iSavedCell; |
| } |
| |
| descend_to_cell_out: |
| *pEof = isEof; |
| return rc; |
| } |
| |
| /* |
| ** 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); |
| RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| int rc = SQLITE_OK; |
| |
| /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is |
| ** already at EOF. It is against the rules to call the xNext() method of |
| ** a cursor that has already reached EOF. |
| */ |
| assert( pCsr->pNode ); |
| |
| if( pCsr->iStrategy==1 ){ |
| /* This "scan" is a direct lookup by rowid. There is no next entry. */ |
| nodeRelease(pRtree, pCsr->pNode); |
| pCsr->pNode = 0; |
| }else{ |
| /* Move to the next entry that matches the configured constraints. */ |
| int iHeight = 0; |
| while( pCsr->pNode ){ |
| RtreeNode *pNode = pCsr->pNode; |
| int nCell = NCELL(pNode); |
| for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){ |
| 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; |
| } |
| |
| /* |
| ** Rtree virtual table module xRowid method. |
| */ |
| static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ |
| Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; |
| RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| |
| assert(pCsr->pNode); |
| *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); |
| |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Rtree virtual table module xColumn method. |
| */ |
| static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ |
| Rtree *pRtree = (Rtree *)cur->pVtab; |
| RtreeCursor *pCsr = (RtreeCursor *)cur; |
| |
| if( i==0 ){ |
| i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); |
| sqlite3_result_int64(ctx, iRowid); |
| }else{ |
| RtreeCoord c; |
| nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c); |
| if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| sqlite3_result_double(ctx, c.f); |
| }else{ |
| assert( pRtree->eCoordType==RTREE_COORD_INT32 ); |
| sqlite3_result_int(ctx, c.i); |
| } |
| } |
| |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Use nodeAcquire() to obtain the leaf node containing the record with |
| ** rowid iRowid. If successful, set *ppLeaf to point to the node and |
| ** return SQLITE_OK. If there is no such record in the table, set |
| ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf |
| ** to zero and return an SQLite error code. |
| */ |
| static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){ |
| int rc; |
| *ppLeaf = 0; |
| sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid); |
| if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){ |
| i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0); |
| rc = nodeAcquire(pRtree, iNode, 0, ppLeaf); |
| sqlite3_reset(pRtree->pReadRowid); |
| }else{ |
| rc = sqlite3_reset(pRtree->pReadRowid); |
| } |
| return rc; |
| } |
| |
| /* |
| ** This function is called to configure the RtreeConstraint object passed |
| ** as the second argument for a MATCH constraint. The value passed as the |
| ** first argument to this function is the right-hand operand to the MATCH |
| ** operator. |
| */ |
| static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){ |
| RtreeMatchArg *p; |
| sqlite3_rtree_geometry *pGeom; |
| int nBlob; |
| |
| /* Check that value is actually a blob. */ |
| if( !sqlite3_value_type(pValue)==SQLITE_BLOB ) return SQLITE_ERROR; |
| |
| /* Check that the blob is roughly the right size. */ |
| nBlob = sqlite3_value_bytes(pValue); |
| if( nBlob<(int)sizeof(RtreeMatchArg) |
| || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0 |
| ){ |
| return SQLITE_ERROR; |
| } |
| |
| pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc( |
| sizeof(sqlite3_rtree_geometry) + nBlob |
| ); |
| if( !pGeom ) return SQLITE_NOMEM; |
| memset(pGeom, 0, sizeof(sqlite3_rtree_geometry)); |
| p = (RtreeMatchArg *)&pGeom[1]; |
| |
| memcpy(p, sqlite3_value_blob(pValue), nBlob); |
| if( p->magic!=RTREE_GEOMETRY_MAGIC |
| || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double)) |
| ){ |
| sqlite3_free(pGeom); |
| return SQLITE_ERROR; |
| } |
| |
| pGeom->pContext = p->pContext; |
| pGeom->nParam = p->nParam; |
| pGeom->aParam = p->aParam; |
| |
| pCons->xGeom = p->xGeom; |
| pCons->pGeom = pGeom; |
| return SQLITE_OK; |
| } |
| |
| /* |
| ** Rtree virtual table module xFilter method. |
| */ |
| static int rtreeFilter( |
| sqlite3_vtab_cursor *pVtabCursor, |
| int idxNum, const char *idxStr, |
| int argc, sqlite3_value **argv |
| ){ |
| Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; |
| RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| |
| RtreeNode *pRoot = 0; |
| int ii; |
| int rc = SQLITE_OK; |
| |
| rtreeReference(pRtree); |
| |
| freeCursorConstraints(pCsr); |
| pCsr->iStrategy = idxNum; |
| |
| if( idxNum==1 ){ |
| /* 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); |
| pCsr->nConstraint = argc; |
| if( !pCsr->aConstraint ){ |
| rc = SQLITE_NOMEM; |
| }else{ |
| memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc); |
| assert( (idxStr==0 && argc==0) || (int)strlen(idxStr)==argc*2 ); |
| for(ii=0; ii<argc; ii++){ |
| RtreeConstraint *p = &pCsr->aConstraint[ii]; |
| p->op = idxStr[ii*2]; |
| p->iCoord = idxStr[ii*2+1]-'a'; |
| if( p->op==RTREE_MATCH ){ |
| /* A MATCH operator. The right-hand-side must be a blob that |
| ** can be cast into an RtreeMatchArg object. One created using |
| ** an sqlite3_rtree_geometry_callback() SQL user function. |
| */ |
| rc = deserializeGeometry(argv[ii], p); |
| if( rc!=SQLITE_OK ){ |
| break; |
| } |
| }else{ |
| p->rValue = sqlite3_value_double(argv[ii]); |
| } |
| } |
| } |
| } |
| |
| if( rc==SQLITE_OK ){ |
| pCsr->pNode = 0; |
| rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
| } |
| if( rc==SQLITE_OK ){ |
| int isEof = 1; |
| int nCell = NCELL(pRoot); |
| pCsr->pNode = pRoot; |
| for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){ |
| assert( pCsr->pNode==pRoot ); |
| rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof); |
| if( !isEof ){ |
| break; |
| } |
| } |
| if( rc==SQLITE_OK && isEof ){ |
| assert( pCsr->pNode==pRoot ); |
| nodeRelease(pRtree, pRoot); |
| pCsr->pNode = 0; |
| } |
| assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) ); |
| } |
| } |
| |
| rtreeRelease(pRtree); |
| return rc; |
| } |
| |
| /* |
| ** Rtree virtual table module xBestIndex method. There are three |
| ** table scan strategies to choose from (in order from most to |
| ** least desirable): |
| ** |
| ** idxNum idxStr Strategy |
| ** ------------------------------------------------ |
| ** 1 Unused Direct lookup by rowid. |
| ** 2 See below R-tree query or full-table scan. |
| ** ------------------------------------------------ |
| ** |
| ** If strategy 1 is used, then idxStr is not meaningful. If strategy |
| ** 2 is used, idxStr is formatted to contain 2 bytes for each |
| ** constraint used. The first two bytes of idxStr correspond to |
| ** the constraint in sqlite3_index_info.aConstraintUsage[] with |
| ** (argvIndex==1) etc. |
| ** |
| ** The first of each pair of bytes in idxStr identifies the constraint |
| ** operator as follows: |
| ** |
| ** Operator Byte Value |
| ** ---------------------- |
| ** = 0x41 ('A') |
| ** <= 0x42 ('B') |
| ** < 0x43 ('C') |
| ** >= 0x44 ('D') |
| ** > 0x45 ('E') |
| ** MATCH 0x46 ('F') |
| ** ---------------------- |
| ** |
| ** The second of each pair of bytes identifies the coordinate column |
| ** to which the constraint applies. The leftmost coordinate column |
| ** is 'a', the second from the left 'b' etc. |
| */ |
| static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ |
| int rc = SQLITE_OK; |
| int ii; |
| |
| int iIdx = 0; |
| char zIdxStr[RTREE_MAX_DIMENSIONS*8+1]; |
| memset(zIdxStr, 0, sizeof(zIdxStr)); |
| UNUSED_PARAMETER(tab); |
| |
| assert( pIdxInfo->idxStr==0 ); |
| for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){ |
| struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii]; |
| |
| if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){ |
| /* We have an equality constraint on the rowid. Use strategy 1. */ |
| int jj; |
| for(jj=0; jj<ii; jj++){ |
| pIdxInfo->aConstraintUsage[jj].argvIndex = 0; |
| pIdxInfo->aConstraintUsage[jj].omit = 0; |
| } |
| pIdxInfo->idxNum = 1; |
| pIdxInfo->aConstraintUsage[ii].argvIndex = 1; |
| pIdxInfo->aConstraintUsage[jj].omit = 1; |
| |
| /* This strategy involves a two rowid lookups on an B-Tree structures |
| ** and then a linear search of an R-Tree node. This should be |
| ** considered almost as quick as a direct rowid lookup (for which |
| ** sqlite uses an internal cost of 0.0). |
| */ |
| pIdxInfo->estimatedCost = 10.0; |
| return SQLITE_OK; |
| } |
| |
| if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){ |
| u8 op; |
| switch( p->op ){ |
| case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break; |
| case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break; |
| case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break; |
| case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break; |
| case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; |
| default: |
| assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH ); |
| op = RTREE_MATCH; |
| break; |
| } |
| zIdxStr[iIdx++] = op; |
| zIdxStr[iIdx++] = p->iColumn - 1 + 'a'; |
| pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); |
| pIdxInfo->aConstraintUsage[ii].omit = 1; |
| } |
| } |
| |
| pIdxInfo->idxNum = 2; |
| pIdxInfo->needToFreeIdxStr = 1; |
| if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ |
| return SQLITE_NOMEM; |
| } |
| assert( iIdx>=0 ); |
| pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1)); |
| return rc; |
| } |
| |
| /* |
| ** Return the N-dimensional volumn of the cell stored in *p. |
| */ |
| static float cellArea(Rtree *pRtree, RtreeCell *p){ |
| float area = 1.0; |
| int ii; |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
| } |
| return area; |
| } |
| |
| /* |
| ** Return the margin length of cell p. The margin length is the sum |
| ** of the objects size in each dimension. |
| */ |
| static float cellMargin(Rtree *pRtree, RtreeCell *p){ |
| float margin = 0.0; |
| int ii; |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
| } |
| return margin; |
| } |
| |
| /* |
| ** Store the union of cells p1 and p2 in p1. |
| */ |
| static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
| int ii; |
| if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); |
| p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); |
| } |
| }else{ |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); |
| p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); |
| } |
| } |
| } |
| |
| /* |
| ** 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; ii<(pRtree->nDim*2); ii+=2){ |
| RtreeCoord *a1 = &p1->aCoord[ii]; |
| RtreeCoord *a2 = &p2->aCoord[ii]; |
| if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) |
| || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) |
| ){ |
| return 0; |
| } |
| } |
| return 1; |
| } |
| |
| /* |
| ** Return the amount cell p would grow by if it were unioned with pCell. |
| */ |
| static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ |
| float area; |
| RtreeCell cell; |
| memcpy(&cell, p, sizeof(RtreeCell)); |
| area = cellArea(pRtree, &cell); |
| cellUnion(pRtree, &cell, pCell); |
| return (cellArea(pRtree, &cell)-area); |
| } |
| |
| #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT |
| static float cellOverlap( |
| Rtree *pRtree, |
| RtreeCell *p, |
| RtreeCell *aCell, |
| int nCell, |
| int iExclude |
| ){ |
| int ii; |
| float overlap = 0.0; |
| for(ii=0; ii<nCell; ii++){ |
| #if VARIANT_RSTARTREE_CHOOSESUBTREE |
| if( ii!=iExclude ) |
| #else |
| assert( iExclude==-1 ); |
| UNUSED_PARAMETER(iExclude); |
| #endif |
| { |
| int jj; |
| float o = 1.0; |
| for(jj=0; jj<(pRtree->nDim*2); jj+=2){ |
| double x1; |
| double x2; |
| |
| x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); |
| x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); |
| |
| if( x2<x1 ){ |
| o = 0.0; |
| break; |
| }else{ |
| o = o * (x2-x1); |
| } |
| } |
| overlap += o; |
| } |
| } |
| return overlap; |
| } |
| #endif |
| |
| #if VARIANT_RSTARTREE_CHOOSESUBTREE |
| static float cellOverlapEnlargement( |
| Rtree *pRtree, |
| RtreeCell *p, |
| RtreeCell *pInsert, |
| RtreeCell *aCell, |
| int nCell, |
| int iExclude |
| ){ |
| float before; |
| float after; |
| before = cellOverlap(pRtree, p, aCell, nCell, iExclude); |
| cellUnion(pRtree, p, pInsert); |
| after = cellOverlap(pRtree, p, aCell, nCell, iExclude); |
| return after-before; |
| } |
| #endif |
| |
| |
| /* |
| ** This function implements the ChooseLeaf algorithm from Gutman[84]. |
| ** ChooseSubTree in r*tree terminology. |
| */ |
| static int ChooseLeaf( |
| Rtree *pRtree, /* Rtree table */ |
| RtreeCell *pCell, /* Cell to insert into rtree */ |
| int iHeight, /* Height of sub-tree rooted at pCell */ |
| RtreeNode **ppLeaf /* OUT: Selected leaf page */ |
| ){ |
| int rc; |
| int ii; |
| RtreeNode *pNode; |
| rc = nodeAcquire(pRtree, 1, 0, &pNode); |
| |
| for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ |
| int iCell; |
| sqlite3_int64 iBest; |
| |
| float fMinGrowth; |
| float fMinArea; |
| float fMinOverlap; |
| |
| int nCell = NCELL(pNode); |
| RtreeCell cell; |
| RtreeNode *pChild; |
| |
| RtreeCell *aCell = 0; |
| |
| #if VARIANT_RSTARTREE_CHOOSESUBTREE |
| if( ii==(pRtree->iDepth-1) ){ |
| int jj; |
| aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell); |
| if( !aCell ){ |
| rc = SQLITE_NOMEM; |
| nodeRelease(pRtree, pNode); |
| pNode = 0; |
| continue; |
| } |
| for(jj=0; jj<nCell; jj++){ |
| nodeGetCell(pRtree, pNode, jj, &aCell[jj]); |
| } |
| } |
| #endif |
| |
| /* 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. |
| */ |
| for(iCell=0; iCell<nCell; iCell++){ |
| int bBest = 0; |
| float growth; |
| float area; |
| float overlap = 0.0; |
| nodeGetCell(pRtree, pNode, iCell, &cell); |
| growth = cellGrowth(pRtree, &cell, pCell); |
| area = cellArea(pRtree, &cell); |
| |
| #if VARIANT_RSTARTREE_CHOOSESUBTREE |
| if( ii==(pRtree->iDepth-1) ){ |
| overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell); |
| } |
| if( (iCell==0) |
| || (overlap<fMinOverlap) |
| || (overlap==fMinOverlap && growth<fMinGrowth) |
| || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea) |
| ){ |
| bBest = 1; |
| } |
| #else |
| if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){ |
| bBest = 1; |
| } |
| #endif |
| if( bBest ){ |
| fMinOverlap = overlap; |
| fMinGrowth = growth; |
| fMinArea = area; |
| iBest = cell.iRowid; |
| } |
| } |
| |
| sqlite3_free(aCell); |
| rc = nodeAcquire(pRtree, iBest, pNode, &pChild); |
| nodeRelease(pRtree, pNode); |
| pNode = pChild; |
| } |
| |
| *ppLeaf = pNode; |
| return rc; |
| } |
| |
| /* |
| ** 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); |
| sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode); |
| sqlite3_step(pRtree->pWriteRowid); |
| return sqlite3_reset(pRtree->pWriteRowid); |
| } |
| |
| /* |
| ** Write mapping (iNode->iPar) to the <rtree>_parent table. |
| */ |
| static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){ |
| sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode); |
| sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); |
| sqlite3_step(pRtree->pWriteParent); |
| return sqlite3_reset(pRtree->pWriteParent); |
| } |
| |
| static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int); |
| |
| #if VARIANT_GUTTMAN_LINEAR_SPLIT |
| /* |
| ** Implementation of the linear variant of the PickNext() function from |
| ** Guttman[84]. |
| */ |
| static RtreeCell *LinearPickNext( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| RtreeCell *pLeftBox, |
| RtreeCell *pRightBox, |
| int *aiUsed |
| ){ |
| int ii; |
| for(ii=0; aiUsed[ii]; ii++); |
| aiUsed[ii] = 1; |
| return &aCell[ii]; |
| } |
| |
| /* |
| ** Implementation of the linear variant of the PickSeeds() function from |
| ** Guttman[84]. |
| */ |
| static void LinearPickSeeds( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| int *piLeftSeed, |
| int *piRightSeed |
| ){ |
| int i; |
| int iLeftSeed = 0; |
| int iRightSeed = 1; |
| float maxNormalInnerWidth = 0.0; |
| |
| /* Pick two "seed" cells from the array of cells. The algorithm used |
| ** here is the LinearPickSeeds algorithm from Gutman[1984]. The |
| ** indices of the two seed cells in the array are stored in local |
| ** variables iLeftSeek and iRightSeed. |
| */ |
| for(i=0; i<pRtree->nDim; i++){ |
| float x1 = DCOORD(aCell[0].aCoord[i*2]); |
| float x2 = DCOORD(aCell[0].aCoord[i*2+1]); |
| float x3 = x1; |
| float x4 = x2; |
| int jj; |
| |
| int iCellLeft = 0; |
| int iCellRight = 0; |
| |
| for(jj=1; jj<nCell; jj++){ |
| float left = DCOORD(aCell[jj].aCoord[i*2]); |
| float right = DCOORD(aCell[jj].aCoord[i*2+1]); |
| |
| if( left<x1 ) x1 = left; |
| if( right>x4 ) x4 = right; |
| if( left>x3 ){ |
| x3 = left; |
| iCellRight = jj; |
| } |
| if( right<x2 ){ |
| x2 = right; |
| iCellLeft = jj; |
| } |
| } |
| |
| if( x4!=x1 ){ |
| float normalwidth = (x3 - x2) / (x4 - x1); |
| if( normalwidth>maxNormalInnerWidth ){ |
| iLeftSeed = iCellLeft; |
| iRightSeed = iCellRight; |
| } |
| } |
| } |
| |
| *piLeftSeed = iLeftSeed; |
| *piRightSeed = iRightSeed; |
| } |
| #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */ |
| |
| #if VARIANT_GUTTMAN_QUADRATIC_SPLIT |
| /* |
| ** Implementation of the quadratic variant of the PickNext() function from |
| ** Guttman[84]. |
| */ |
| static RtreeCell *QuadraticPickNext( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| RtreeCell *pLeftBox, |
| RtreeCell *pRightBox, |
| int *aiUsed |
| ){ |
| #define FABS(a) ((a)<0.0?-1.0*(a):(a)) |
| |
| int iSelect = -1; |
| float fDiff; |
| int ii; |
| for(ii=0; ii<nCell; ii++){ |
| if( aiUsed[ii]==0 ){ |
| float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]); |
| float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]); |
| float diff = FABS(right-left); |
| if( iSelect<0 || diff>fDiff ){ |
| fDiff = diff; |
| iSelect = ii; |
| } |
| } |
| } |
| aiUsed[iSelect] = 1; |
| return &aCell[iSelect]; |
| } |
| |
| /* |
| ** Implementation of the quadratic variant of the PickSeeds() function from |
| ** Guttman[84]. |
| */ |
| static void QuadraticPickSeeds( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| int *piLeftSeed, |
| int *piRightSeed |
| ){ |
| int ii; |
| int jj; |
| |
| int iLeftSeed = 0; |
| int iRightSeed = 1; |
| float fWaste = 0.0; |
| |
| for(ii=0; ii<nCell; ii++){ |
| for(jj=ii+1; jj<nCell; jj++){ |
| float right = cellArea(pRtree, &aCell[jj]); |
| float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]); |
| float waste = growth - right; |
| |
| if( waste>fWaste ){ |
| iLeftSeed = ii; |
| iRightSeed = jj; |
| fWaste = waste; |
| } |
| } |
| } |
| |
| *piLeftSeed = iLeftSeed; |
| *piRightSeed = iRightSeed; |
| } |
| #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */ |
| |
| /* |
| ** Arguments aIdx, aDistance and aSpare all point to arrays of size |
| ** nIdx. The aIdx array contains the set of integers from 0 to |
| ** (nIdx-1) in no particular order. This function sorts the values |
| ** in aIdx according to the indexed values in aDistance. For |
| ** example, assuming the inputs: |
| ** |
| ** aIdx = { 0, 1, 2, 3 } |
| ** aDistance = { 5.0, 2.0, 7.0, 6.0 } |
| ** |
| ** this function sets the aIdx array to contain: |
| ** |
| ** aIdx = { 0, 1, 2, 3 } |
| ** |
| ** The aSpare array is used as temporary working space by the |
| ** sorting algorithm. |
| */ |
| static void SortByDistance( |
| int *aIdx, |
| int nIdx, |
| float *aDistance, |
| int *aSpare |
| ){ |
| if( nIdx>1 ){ |
| 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( iLeft<nLeft || iRight<nRight ){ |
| if( iLeft==nLeft ){ |
| aIdx[iLeft+iRight] = aRight[iRight]; |
| iRight++; |
| }else if( iRight==nRight ){ |
| aIdx[iLeft+iRight] = aLeft[iLeft]; |
| iLeft++; |
| }else{ |
| float fLeft = aDistance[aLeft[iLeft]]; |
| float fRight = aDistance[aRight[iRight]]; |
| if( fLeft<fRight ){ |
| aIdx[iLeft+iRight] = aLeft[iLeft]; |
| iLeft++; |
| }else{ |
| aIdx[iLeft+iRight] = aRight[iRight]; |
| iRight++; |
| } |
| } |
| } |
| |
| #if 0 |
| /* Check that the sort worked */ |
| { |
| int jj; |
| for(jj=1; jj<nIdx; jj++){ |
| float left = aDistance[aIdx[jj-1]]; |
| float right = aDistance[aIdx[jj]]; |
| assert( left<=right ); |
| } |
| } |
| #endif |
| } |
| } |
| |
| /* |
| ** Arguments aIdx, aCell and aSpare all point to arrays of size |
| ** nIdx. The aIdx array contains the set of integers from 0 to |
| ** (nIdx-1) in no particular order. This function sorts the values |
| ** in aIdx according to dimension iDim of the cells in aCell. The |
| ** minimum value of dimension iDim is considered first, the |
| ** maximum used to break ties. |
| ** |
| ** The aSpare array is used as temporary working space by the |
| ** sorting algorithm. |
| */ |
| static void SortByDimension( |
| Rtree *pRtree, |
| int *aIdx, |
| int nIdx, |
| int iDim, |
| RtreeCell *aCell, |
| int *aSpare |
| ){ |
| if( nIdx>1 ){ |
| |
| int iLeft = 0; |
| int iRight = 0; |
| |
| int nLeft = nIdx/2; |
| int nRight = nIdx-nLeft; |
| int *aLeft = aIdx; |
| int *aRight = &aIdx[nLeft]; |
| |
| SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare); |
| SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare); |
| |
| memcpy(aSpare, aLeft, sizeof(int)*nLeft); |
| aLeft = aSpare; |
| while( iLeft<nLeft || iRight<nRight ){ |
| double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]); |
| double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]); |
| double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]); |
| double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]); |
| if( (iLeft!=nLeft) && ((iRight==nRight) |
| || (xleft1<xright1) |
| || (xleft1==xright1 && xleft2<xright2) |
| )){ |
| aIdx[iLeft+iRight] = aLeft[iLeft]; |
| iLeft++; |
| }else{ |
| aIdx[iLeft+iRight] = aRight[iRight]; |
| iRight++; |
| } |
| } |
| |
| #if 0 |
| /* Check that the sort worked */ |
| { |
| int jj; |
| for(jj=1; jj<nIdx; jj++){ |
| float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; |
| float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; |
| float xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; |
| float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; |
| assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); |
| } |
| } |
| #endif |
| } |
| } |
| |
| #if VARIANT_RSTARTREE_SPLIT |
| /* |
| ** Implementation of the R*-tree variant of SplitNode from Beckman[1990]. |
| */ |
| static int splitNodeStartree( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| RtreeNode *pLeft, |
| RtreeNode *pRight, |
| RtreeCell *pBboxLeft, |
| RtreeCell *pBboxRight |
| ){ |
| int **aaSorted; |
| int *aSpare; |
| int ii; |
| |
| int iBestDim; |
| int iBestSplit; |
| float fBestMargin; |
| |
| int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); |
| |
| aaSorted = (int **)sqlite3_malloc(nByte); |
| if( !aaSorted ){ |
| return SQLITE_NOMEM; |
| } |
| |
| aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell]; |
| memset(aaSorted, 0, nByte); |
| for(ii=0; ii<pRtree->nDim; ii++){ |
| int jj; |
| aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; |
| for(jj=0; jj<nCell; jj++){ |
| aaSorted[ii][jj] = jj; |
| } |
| SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); |
| } |
| |
| for(ii=0; ii<pRtree->nDim; ii++){ |
| float margin = 0.0; |
| float fBestOverlap; |
| float fBestArea; |
| int iBestLeft; |
| int nLeft; |
| |
| for( |
| nLeft=RTREE_MINCELLS(pRtree); |
| nLeft<=(nCell-RTREE_MINCELLS(pRtree)); |
| nLeft++ |
| ){ |
| RtreeCell left; |
| RtreeCell right; |
| int kk; |
| float overlap; |
| float area; |
| |
| memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell)); |
| memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell)); |
| for(kk=1; kk<(nCell-1); kk++){ |
| if( kk<nLeft ){ |
| cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); |
| }else{ |
| cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); |
| } |
| } |
| margin += cellMargin(pRtree, &left); |
| margin += cellMargin(pRtree, &right); |
| overlap = cellOverlap(pRtree, &left, &right, 1, -1); |
| area = cellArea(pRtree, &left) + cellArea(pRtree, &right); |
| if( (nLeft==RTREE_MINCELLS(pRtree)) |
| || (overlap<fBestOverlap) |
| || (overlap==fBestOverlap && area<fBestArea) |
| ){ |
| iBestLeft = nLeft; |
| fBestOverlap = overlap; |
| fBestArea = area; |
| } |
| } |
| |
| if( ii==0 || margin<fBestMargin ){ |
| iBestDim = ii; |
| fBestMargin = margin; |
| iBestSplit = iBestLeft; |
| } |
| } |
| |
| memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell)); |
| memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell)); |
| for(ii=0; ii<nCell; ii++){ |
| RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight; |
| RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight; |
| RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]]; |
| nodeInsertCell(pRtree, pTarget, pCell); |
| cellUnion(pRtree, pBbox, pCell); |
| } |
| |
| sqlite3_free(aaSorted); |
| return SQLITE_OK; |
| } |
| #endif |
| |
| #if VARIANT_GUTTMAN_SPLIT |
| /* |
| ** Implementation of the regular R-tree SplitNode from Guttman[1984]. |
| */ |
| static int splitNodeGuttman( |
| Rtree *pRtree, |
| RtreeCell *aCell, |
| int nCell, |
| RtreeNode *pLeft, |
| RtreeNode *pRight, |
| RtreeCell *pBboxLeft, |
| RtreeCell *pBboxRight |
| ){ |
| int iLeftSeed = 0; |
| int iRightSeed = 1; |
| int *aiUsed; |
| int i; |
| |
| aiUsed = sqlite3_malloc(sizeof(int)*nCell); |
| if( !aiUsed ){ |
| return SQLITE_NOMEM; |
| } |
| memset(aiUsed, 0, sizeof(int)*nCell); |
| |
| PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed); |
| |
| memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell)); |
| memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell)); |
| nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]); |
| nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]); |
| aiUsed[iLeftSeed] = 1; |
| aiUsed[iRightSeed] = 1; |
| |
| for(i=nCell-2; i>0; i--){ |
| RtreeCell *pNext; |
| pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed); |
| float diff = |
| cellGrowth(pRtree, pBboxLeft, pNext) - |
| cellGrowth(pRtree, pBboxRight, pNext) |
| ; |
| if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i) |
| || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i)) |
| ){ |
| nodeInsertCell(pRtree, pRight, pNext); |
| cellUnion(pRtree, pBboxRight, pNext); |
| }else{ |
| nodeInsertCell(pRtree, pLeft, pNext); |
| cellUnion(pRtree, pBboxLeft, pNext); |
| } |
| } |
| |
| sqlite3_free(aiUsed); |
| return SQLITE_OK; |
| } |
| #endif |
| |
| static int updateMapping( |
| Rtree *pRtree, |
| i64 iRowid, |
| RtreeNode *pNode, |
| int iHeight |
| ){ |
| int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64); |
| xSetMapping = ((iHeight==0)?rowidWrite:parentWrite); |
| if( iHeight>0 ){ |
| RtreeNode *pChild = nodeHashLookup(pRtree, iRowid); |
| if( pChild ){ |
| nodeRelease(pRtree, pChild->pParent); |
| nodeReference(pNode); |
| pChild->pParent = pNode; |
| } |
| } |
| return xSetMapping(pRtree, iRowid, pNode->iNode); |
| } |
| |
| static int SplitNode( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| RtreeCell *pCell, |
| int iHeight |
| ){ |
| int i; |
| int newCellIsRight = 0; |
| |
| int rc = SQLITE_OK; |
| int nCell = NCELL(pNode); |
| RtreeCell *aCell; |
| int *aiUsed; |
| |
| RtreeNode *pLeft = 0; |
| RtreeNode *pRight = 0; |
| |
| RtreeCell leftbbox; |
| RtreeCell rightbbox; |
| |
| /* Allocate an array and populate it with a copy of pCell and |
| ** all cells from node pLeft. Then zero the original node. |
| */ |
| aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1)); |
| if( !aCell ){ |
| rc = SQLITE_NOMEM; |
| goto splitnode_out; |
| } |
| aiUsed = (int *)&aCell[nCell+1]; |
| memset(aiUsed, 0, sizeof(int)*(nCell+1)); |
| for(i=0; i<nCell; i++){ |
| nodeGetCell(pRtree, pNode, i, &aCell[i]); |
| } |
| nodeZero(pRtree, pNode); |
| memcpy(&aCell[nCell], pCell, sizeof(RtreeCell)); |
| nCell++; |
| |
| if( pNode->iNode==1 ){ |
| pRight = nodeNew(pRtree, pNode); |
| pLeft = nodeNew(pRtree, pNode); |
| pRtree->iDepth++; |
| pNode->isDirty = 1; |
| writeInt16(pNode->zData, pRtree->iDepth); |
| }else{ |
| pLeft = pNode; |
| pRight = nodeNew(pRtree, pLeft->pParent); |
| nodeReference(pLeft); |
| } |
| |
| if( !pLeft || !pRight ){ |
| rc = SQLITE_NOMEM; |
| goto splitnode_out; |
| } |
| |
| memset(pLeft->zData, 0, pRtree->iNodeSize); |
| memset(pRight->zData, 0, pRtree->iNodeSize); |
| |
| rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox); |
| if( rc!=SQLITE_OK ){ |
| goto splitnode_out; |
| } |
| |
| /* Ensure both child nodes have node numbers assigned to them by calling |
| ** nodeWrite(). Node pRight always needs a node number, as it was created |
| ** by nodeNew() above. But node pLeft sometimes already has a node number. |
| ** In this case avoid the all to nodeWrite(). |
| */ |
| if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)) |
| || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft))) |
| ){ |
| goto splitnode_out; |
| } |
| |
| rightbbox.iRowid = pRight->iNode; |
| leftbbox.iRowid = pLeft->iNode; |
| |
| 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); |
| rc = updateMapping(pRtree, iRowid, pRight, iHeight); |
| if( iRowid==pCell->iRowid ){ |
| newCellIsRight = 1; |
| } |
| if( rc!=SQLITE_OK ){ |
| goto splitnode_out; |
| } |
| } |
| if( pNode->iNode==1 ){ |
| for(i=0; i<NCELL(pLeft); i++){ |
| i64 iRowid = nodeGetRowid(pRtree, pLeft, i); |
| rc = updateMapping(pRtree, iRowid, pLeft, iHeight); |
| if( rc!=SQLITE_OK ){ |
| goto splitnode_out; |
| } |
| } |
| }else if( newCellIsRight==0 ){ |
| rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight); |
| } |
| |
| if( rc==SQLITE_OK ){ |
| rc = nodeRelease(pRtree, pRight); |
| pRight = 0; |
| } |
| if( rc==SQLITE_OK ){ |
| rc = nodeRelease(pRtree, pLeft); |
| pLeft = 0; |
| } |
| |
| splitnode_out: |
| 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. |
| ** |
| ** This operation is required when a row is deleted (or updated - an update |
| ** is implemented as a delete followed by an insert). SQLite provides the |
| ** rowid of the row to delete, which can be used to find the leaf on which |
| ** the entry resides (argument pLeaf). Once the leaf is located, this |
| ** function is called to determine its ancestry. |
| */ |
| 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; /* Used to test for reference loops */ |
| i64 iNode; /* Node number of parent node */ |
| |
| /* Before setting pChild->pParent, test that we are not creating a |
| ** loop of references (as we would if, say, pChild==pParent). We don't |
| ** want to do this as it leads to a memory leak when trying to delete |
| ** the referenced counted node structures. |
| */ |
| 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; |
| } |
| |
| /* Remove the xxx_node entry. */ |
| sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode); |
| sqlite3_step(pRtree->pDeleteNode); |
| if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){ |
| return rc; |
| } |
| |
| /* Remove the xxx_parent entry. */ |
| sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode); |
| sqlite3_step(pRtree->pDeleteParent); |
| if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){ |
| return rc; |
| } |
| |
| /* Remove the node from the in-memory hash table and link it into |
| ** the Rtree.pDeleted list. Its contents will be re-inserted later on. |
| */ |
| nodeHashDelete(pRtree, pNode); |
| pNode->iNode = iHeight; |
| 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){ |
| RtreeNode *pParent; |
| int rc; |
| |
| if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){ |
| return rc; |
| } |
| |
| /* Remove the cell from the node. This call just moves bytes around |
| ** the in-memory node image, so it cannot fail. |
| */ |
| nodeDeleteCell(pRtree, pNode, iCell); |
| |
| /* If the node is not the tree root and now has less than the minimum |
| ** number of cells, remove it from the tree. Otherwise, update the |
| ** cell in the parent node so that it tightly contains the updated |
| ** node. |
| */ |
| 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( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| RtreeCell *pCell, |
| int iHeight |
| ){ |
| int *aOrder; |
| int *aSpare; |
| RtreeCell *aCell; |
| float *aDistance; |
| int nCell; |
| float aCenterCoord[RTREE_MAX_DIMENSIONS]; |
| int iDim; |
| int ii; |
| int rc = SQLITE_OK; |
| |
| memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS); |
| |
| nCell = NCELL(pNode)+1; |
| |
| /* Allocate the buffers used by this operation. The allocation is |
| ** relinquished before this function returns. |
| */ |
| aCell = (RtreeCell *)sqlite3_malloc(nCell * ( |
| sizeof(RtreeCell) + /* aCell array */ |
| sizeof(int) + /* aOrder array */ |
| sizeof(int) + /* aSpare array */ |
| sizeof(float) /* aDistance array */ |
| )); |
| if( !aCell ){ |
| return SQLITE_NOMEM; |
| } |
| aOrder = (int *)&aCell[nCell]; |
| aSpare = (int *)&aOrder[nCell]; |
| aDistance = (float *)&aSpare[nCell]; |
| |
| for(ii=0; ii<nCell; ii++){ |
| if( ii==(nCell-1) ){ |
| memcpy(&aCell[ii], pCell, sizeof(RtreeCell)); |
| }else{ |
| nodeGetCell(pRtree, pNode, ii, &aCell[ii]); |
| } |
| aOrder[ii] = ii; |
| for(iDim=0; iDim<pRtree->nDim; iDim++){ |
| aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]); |
| aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]); |
| } |
| } |
| for(iDim=0; iDim<pRtree->nDim; iDim++){ |
| aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0); |
| } |
| |
| for(ii=0; ii<nCell; ii++){ |
| aDistance[ii] = 0.0; |
| for(iDim=0; iDim<pRtree->nDim; iDim++){ |
| float 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 && 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]]; |
| 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( |
| Rtree *pRtree, |
| RtreeNode *pNode, |
| RtreeCell *pCell, |
| int iHeight |
| ){ |
| int rc = SQLITE_OK; |
| if( iHeight>0 ){ |
| RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid); |
| if( pChild ){ |
| nodeRelease(pRtree, pChild->pParent); |
| nodeReference(pNode); |
| pChild->pParent = pNode; |
| } |
| } |
| if( nodeInsertCell(pRtree, pNode, pCell) ){ |
| #if VARIANT_RSTARTREE_REINSERT |
| if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ |
| rc = SplitNode(pRtree, pNode, pCell, iHeight); |
| }else{ |
| 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; |
| int rc = SQLITE_OK; |
| int nCell = NCELL(pNode); |
| |
| for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){ |
| RtreeNode *pInsert; |
| RtreeCell cell; |
| nodeGetCell(pRtree, pNode, ii, &cell); |
| |
| /* Find a node to store this cell in. pNode->iNode currently contains |
| ** the height of the sub-tree headed by the cell. |
| */ |
| rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert); |
| if( rc==SQLITE_OK ){ |
| int rc2; |
| rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode); |
| rc2 = nodeRelease(pRtree, pInsert); |
| if( rc==SQLITE_OK ){ |
| rc = rc2; |
| } |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** Select a currently unused rowid for a new r-tree record. |
| */ |
| static int newRowid(Rtree *pRtree, i64 *piRowid){ |
| int rc; |
| sqlite3_bind_null(pRtree->pWriteRowid, 1); |
| sqlite3_bind_null(pRtree->pWriteRowid, 2); |
| sqlite3_step(pRtree->pWriteRowid); |
| rc = sqlite3_reset(pRtree->pWriteRowid); |
| *piRowid = sqlite3_last_insert_rowid(pRtree->db); |
| return rc; |
| } |
| |
| /* |
| ** The xUpdate method for rtree module virtual tables. |
| */ |
| static int rtreeUpdate( |
| sqlite3_vtab *pVtab, |
| int nData, |
| sqlite3_value **azData, |
| sqlite_int64 *pRowid |
| ){ |
| Rtree *pRtree = (Rtree *)pVtab; |
| int rc = SQLITE_OK; |
| |
| rtreeReference(pRtree); |
| |
| assert(nData>=1); |
| |
| /* If azData[0] is not an SQL NULL value, it is the rowid of a |
| ** record to delete from the r-tree table. The following block does |
| ** just that. |
| */ |
| if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){ |
| i64 iDelete; /* The rowid to delete */ |
| RtreeNode *pLeaf; /* Leaf node containing record iDelete */ |
| int iCell; /* Index of iDelete cell in pLeaf */ |
| RtreeNode *pRoot; |
| |
| /* Obtain a reference to the root node to initialise Rtree.iDepth */ |
| rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
| |
| /* Obtain a reference to the leaf node that contains the entry |
| ** about to be deleted. |
| */ |
| if( rc==SQLITE_OK ){ |
| 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. */ |
| if( rc==SQLITE_OK ){ |
| sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete); |
| sqlite3_step(pRtree->pDeleteRowid); |
| rc = sqlite3_reset(pRtree->pDeleteRowid); |
| } |
| |
| /* Check if the root node now has exactly one child. If so, remove |
| ** it, schedule the contents of the child for reinsertion and |
| ** reduce the tree height by one. |
| ** |
| ** This is equivalent to copying the contents of the child into |
| ** the root node (the operation that Gutman's paper says to perform |
| ** in this scenario). |
| */ |
| if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){ |
| int rc2; |
| RtreeNode *pChild; |
| i64 iChild = nodeGetRowid(pRtree, pRoot, 0); |
| rc = nodeAcquire(pRtree, iChild, pRoot, &pChild); |
| if( rc==SQLITE_OK ){ |
| rc = removeNode(pRtree, pChild, pRtree->iDepth-1); |
| } |
| rc2 = nodeRelease(pRtree, pChild); |
| if( rc==SQLITE_OK ) rc = rc2; |
| if( rc==SQLITE_OK ){ |
| pRtree->iDepth--; |
| writeInt16(pRoot->zData, pRtree->iDepth); |
| pRoot->isDirty = 1; |
| } |
| } |
| |
| /* Re-insert the contents of any underfull nodes removed from the tree. */ |
| for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){ |
| if( rc==SQLITE_OK ){ |
| rc = reinsertNodeContent(pRtree, pLeaf); |
| } |
| pRtree->pDeleted = pLeaf->pNext; |
| sqlite3_free(pLeaf); |
| } |
| |
| /* Release the reference to the root node. */ |
| if( rc==SQLITE_OK ){ |
| rc = nodeRelease(pRtree, pRoot); |
| }else{ |
| nodeRelease(pRtree, pRoot); |
| } |
| } |
| |
| /* If the azData[] array contains more than one element, elements |
| ** (azData[2]..azData[argc-1]) contain a new record to insert into |
| ** the r-tree structure. |
| */ |
| if( rc==SQLITE_OK && nData>1 ){ |
| /* Insert a new record into the r-tree */ |
| RtreeCell cell; |
| int ii; |
| RtreeNode *pLeaf; |
| |
| /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */ |
| assert( nData==(pRtree->nDim*2 + 3) ); |
| if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]); |
| cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]); |
| if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ |
| rc = SQLITE_CONSTRAINT; |
| goto constraint; |
| } |
| } |
| }else{ |
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
| cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]); |
| cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]); |
| if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ |
| rc = SQLITE_CONSTRAINT; |
| goto constraint; |
| } |
| } |
| } |
| |
| /* Figure out the rowid of the new row. */ |
| if( sqlite3_value_type(azData[2])==SQLITE_NULL ){ |
| rc = newRowid(pRtree, &cell.iRowid); |
| }else{ |
| cell.iRowid = sqlite3_value_int64(azData[2]); |
| sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); |
| if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){ |
| sqlite3_reset(pRtree->pReadRowid); |
| rc = SQLITE_CONSTRAINT; |
| goto constraint; |
| } |
| rc = sqlite3_reset(pRtree->pReadRowid); |
| } |
| *pRowid = cell.iRowid; |
| |
| 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; |
| } |
| } |
| } |
| |
| constraint: |
| rtreeRelease(pRtree); |
| return rc; |
| } |
| |
| /* |
| ** The xRename method for rtree module virtual tables. |
| */ |
| static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){ |
| Rtree *pRtree = (Rtree *)pVtab; |
| int rc = SQLITE_NOMEM; |
| char *zSql = sqlite3_mprintf( |
| "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";" |
| "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";" |
| "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";" |
| , pRtree->zDb, pRtree->zName, zNewName |
| , pRtree->zDb, pRtree->zName, zNewName |
| , pRtree->zDb, pRtree->zName, zNewName |
| ); |
| if( zSql ){ |
| rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); |
| sqlite3_free(zSql); |
| } |
| return rc; |
| } |
| |
| static sqlite3_module rtreeModule = { |
| 0, /* iVersion */ |
| rtreeCreate, /* xCreate - create a table */ |
| rtreeConnect, /* xConnect - connect to an existing table */ |
| rtreeBestIndex, /* xBestIndex - Determine search strategy */ |
| rtreeDisconnect, /* xDisconnect - Disconnect from a table */ |
| rtreeDestroy, /* xDestroy - Drop a table */ |
| rtreeOpen, /* xOpen - open a cursor */ |
| rtreeClose, /* xClose - close a cursor */ |
| rtreeFilter, /* xFilter - configure scan constraints */ |
| rtreeNext, /* xNext - advance a cursor */ |
| rtreeEof, /* xEof */ |
| rtreeColumn, /* xColumn - read data */ |
| rtreeRowid, /* xRowid - read data */ |
| rtreeUpdate, /* xUpdate - write data */ |
| 0, /* xBegin - begin transaction */ |
| 0, /* xSync - sync transaction */ |
| 0, /* xCommit - commit transaction */ |
| 0, /* xRollback - rollback transaction */ |
| 0, /* xFindFunction - function overloading */ |
| rtreeRename /* xRename - rename the table */ |
| }; |
| |
| static int rtreeSqlInit( |
| Rtree *pRtree, |
| sqlite3 *db, |
| const char *zDb, |
| const char *zPrefix, |
| int isCreate |
| ){ |
| int rc = SQLITE_OK; |
| |
| #define N_STATEMENT 9 |
| static const char *azSql[N_STATEMENT] = { |
| /* Read and write the xxx_node table */ |
| "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1", |
| "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)", |
| "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1", |
| |
| /* Read and write the xxx_rowid table */ |
| "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1", |
| "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)", |
| "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1", |
| |
| /* Read and write the xxx_parent table */ |
| "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1", |
| "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)", |
| "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1" |
| }; |
| sqlite3_stmt **appStmt[N_STATEMENT]; |
| int i; |
| |
| pRtree->db = db; |
| |
| if( isCreate ){ |
| char *zCreate = sqlite3_mprintf( |
| "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);" |
| "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);" |
| "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);" |
| "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))", |
| zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize |
| ); |
| if( !zCreate ){ |
| return SQLITE_NOMEM; |
| } |
| rc = sqlite3_exec(db, zCreate, 0, 0, 0); |
| sqlite3_free(zCreate); |
| if( rc!=SQLITE_OK ){ |
| return rc; |
| } |
| } |
| |
| appStmt[0] = &pRtree->pReadNode; |
| appStmt[1] = &pRtree->pWriteNode; |
| appStmt[2] = &pRtree->pDeleteNode; |
| appStmt[3] = &pRtree->pReadRowid; |
| appStmt[4] = &pRtree->pWriteRowid; |
| appStmt[5] = &pRtree->pDeleteRowid; |
| appStmt[6] = &pRtree->pReadParent; |
| appStmt[7] = &pRtree->pWriteParent; |
| appStmt[8] = &pRtree->pDeleteParent; |
| |
| for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){ |
| char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix); |
| if( zSql ){ |
| rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); |
| }else{ |
| rc = SQLITE_NOMEM; |
| } |
| sqlite3_free(zSql); |
| } |
| |
| return rc; |
| } |
| |
| /* |
| ** The second argument to this function contains the text of an SQL statement |
| ** that returns a single integer value. The statement is compiled and executed |
| ** using database connection db. If successful, the integer value returned |
| ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error |
| ** code is returned and the value of *piVal after returning is not defined. |
| */ |
| static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){ |
| int rc = SQLITE_NOMEM; |
| if( zSql ){ |
| sqlite3_stmt *pStmt = 0; |
| rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
| if( rc==SQLITE_OK ){ |
| if( SQLITE_ROW==sqlite3_step(pStmt) ){ |
| *piVal = sqlite3_column_int(pStmt, 0); |
| } |
| rc = sqlite3_finalize(pStmt); |
| } |
| } |
| return rc; |
| } |
| |
| /* |
| ** This function is called from within the xConnect() or xCreate() method to |
| ** determine the node-size used by the rtree table being created or connected |
| ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned. |
| ** Otherwise, an SQLite error code is returned. |
| ** |
| ** If this function is being called as part of an xConnect(), then the rtree |
| ** table already exists. In this case the node-size is determined by inspecting |
| ** the root node of the tree. |
| ** |
| ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size. |
| ** This ensures that each node is stored on a single database page. If the |
| ** database page-size is so large that more than RTREE_MAXCELLS entries |
| ** would fit in a single node, use a smaller node-size. |
| */ |
| static int getNodeSize( |
| sqlite3 *db, /* Database handle */ |
| Rtree *pRtree, /* Rtree handle */ |
| int isCreate /* True for xCreate, false for xConnect */ |
| ){ |
| int rc; |
| char *zSql; |
| if( isCreate ){ |
| int iPageSize; |
| zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb); |
| rc = getIntFromStmt(db, zSql, &iPageSize); |
| if( rc==SQLITE_OK ){ |
| pRtree->iNodeSize = iPageSize-64; |
| if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){ |
| pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS; |
| } |
| } |
| }else{ |
| zSql = sqlite3_mprintf( |
| "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1", |
| pRtree->zDb, pRtree->zName |
| ); |
| rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize); |
| } |
| |
| sqlite3_free(zSql); |
| return rc; |
| } |
| |
| /* |
| ** This function is the implementation of both the xConnect and xCreate |
| ** methods of the r-tree virtual table. |
| ** |
| ** argv[0] -> module name |
| ** argv[1] -> database name |
| ** argv[2] -> table name |
| ** argv[...] -> column names... |
| */ |
| static int rtreeInit( |
| sqlite3 *db, /* Database connection */ |
| void *pAux, /* One of the RTREE_COORD_* constants */ |
| int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ |
| sqlite3_vtab **ppVtab, /* OUT: New virtual table */ |
| char **pzErr, /* OUT: Error message, if any */ |
| int isCreate /* True for xCreate, false for xConnect */ |
| ){ |
| int rc = SQLITE_OK; |
| Rtree |