diff options
Diffstat (limited to 'lib/libsqlite3/ext/rtree/rtree.c')
| -rw-r--r-- | lib/libsqlite3/ext/rtree/rtree.c | 3512 |
1 files changed, 0 insertions, 3512 deletions
diff --git a/lib/libsqlite3/ext/rtree/rtree.c b/lib/libsqlite3/ext/rtree/rtree.c deleted file mode 100644 index 4e473a22c28..00000000000 --- a/lib/libsqlite3/ext/rtree/rtree.c +++ /dev/null @@ -1,3512 +0,0 @@ -/* -** 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) - -#ifndef SQLITE_CORE - #include "sqlite3ext.h" - SQLITE_EXTENSION_INIT1 -#else - #include "sqlite3.h" -#endif - -#include <string.h> -#include <assert.h> -#include <stdio.h> - -#ifndef SQLITE_AMALGAMATION -#include "sqlite3rtree.h" -typedef sqlite3_int64 i64; -typedef unsigned char u8; -typedef unsigned short u16; -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; -typedef struct RtreeSearchPoint RtreeSearchPoint; - -/* 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 97 - -/* The xBestIndex method of this virtual table requires an estimate of -** the number of rows in the virtual table to calculate the costs of -** various strategies. If possible, this estimate is loaded from the -** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum). -** Otherwise, if no sqlite_stat1 entry is available, use -** RTREE_DEFAULT_ROWEST. -*/ -#define RTREE_DEFAULT_ROWEST 1048576 -#define RTREE_MIN_ROWEST 100 - -/* -** An rtree virtual-table object. -*/ -struct Rtree { - sqlite3_vtab base; /* Base class. Must be first */ - sqlite3 *db; /* Host database connection */ - int iNodeSize; /* Size in bytes of each node in the node table */ - u8 nDim; /* Number of dimensions */ - u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ - u8 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 */ - int nBusy; /* Current number of users of this structure */ - i64 nRowEst; /* Estimated number of rows in this table */ - - /* 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; - - RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ -}; - -/* Possible values for Rtree.eCoordType: */ -#define RTREE_COORD_REAL32 0 -#define RTREE_COORD_INT32 1 - -/* -** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will -** only deal with integer coordinates. No floating point operations -** will be done. -*/ -#ifdef SQLITE_RTREE_INT_ONLY - typedef sqlite3_int64 RtreeDValue; /* High accuracy coordinate */ - typedef int RtreeValue; /* Low accuracy coordinate */ -# define RTREE_ZERO 0 -#else - typedef double RtreeDValue; /* High accuracy coordinate */ - typedef float RtreeValue; /* Low accuracy coordinate */ -# define RTREE_ZERO 0.0 -#endif - -/* -** When doing a search of an r-tree, instances of the following structure -** record intermediate results from the tree walk. -** -** The id is always a node-id. For iLevel>=1 the id is the node-id of -** the node that the RtreeSearchPoint represents. When iLevel==0, however, -** the id is of the parent node and the cell that RtreeSearchPoint -** represents is the iCell-th entry in the parent node. -*/ -struct RtreeSearchPoint { - RtreeDValue rScore; /* The score for this node. Smallest goes first. */ - sqlite3_int64 id; /* Node ID */ - u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */ - u8 eWithin; /* PARTLY_WITHIN or FULLY_WITHIN */ - u8 iCell; /* Cell index within the node */ -}; - -/* -** 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 - - -/* -** Number of entries in the cursor RtreeNode cache. The first entry is -** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining -** entries cache the RtreeNode for the first elements of the priority queue. -*/ -#define RTREE_CACHE_SZ 5 - -/* -** An rtree cursor object. -*/ -struct RtreeCursor { - sqlite3_vtab_cursor base; /* Base class. Must be first */ - u8 atEOF; /* True if at end of search */ - u8 bPoint; /* True if sPoint is valid */ - int iStrategy; /* Copy of idxNum search parameter */ - int nConstraint; /* Number of entries in aConstraint */ - RtreeConstraint *aConstraint; /* Search constraints. */ - int nPointAlloc; /* Number of slots allocated for aPoint[] */ - int nPoint; /* Number of slots used in aPoint[] */ - int mxLevel; /* iLevel value for root of the tree */ - RtreeSearchPoint *aPoint; /* Priority queue for search points */ - RtreeSearchPoint sPoint; /* Cached next search point */ - RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */ - u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */ -}; - -/* Return the Rtree of a RtreeCursor */ -#define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab)) - -/* -** A coordinate can be either a floating point number or a integer. All -** coordinates within a single R-Tree are always of the same time. -*/ -union RtreeCoord { - RtreeValue f; /* Floating point value */ - int i; /* Integer value */ - u32 u; /* Unsigned for byte-order conversions */ -}; - -/* -** The argument is an RtreeCoord. Return the value stored within the RtreeCoord -** formatted as a RtreeDValue (double or int64). This macro assumes that local -** variable pRtree points to the Rtree structure associated with the -** RtreeCoord. -*/ -#ifdef SQLITE_RTREE_INT_ONLY -# define DCOORD(coord) ((RtreeDValue)coord.i) -#else -# define DCOORD(coord) ( \ - (pRtree->eCoordType==RTREE_COORD_REAL32) ? \ - ((double)coord.f) : \ - ((double)coord.i) \ - ) -#endif - -/* -** A search constraint. -*/ -struct RtreeConstraint { - int iCoord; /* Index of constrained coordinate */ - int op; /* Constraining operation */ - union { - RtreeDValue rValue; /* Constraint value. */ - int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*); - int (*xQueryFunc)(sqlite3_rtree_query_info*); - } u; - sqlite3_rtree_query_info *pInfo; /* xGeom and xQueryFunc argument */ -}; - -/* Possible values for RtreeConstraint.op */ -#define RTREE_EQ 0x41 /* A */ -#define RTREE_LE 0x42 /* B */ -#define RTREE_LT 0x43 /* C */ -#define RTREE_GE 0x44 /* D */ -#define RTREE_GT 0x45 /* E */ -#define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */ -#define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */ - - -/* -** An rtree structure node. -*/ -struct RtreeNode { - RtreeNode *pParent; /* Parent node */ - i64 iNode; /* The node number */ - int nRef; /* Number of references to this node */ - int isDirty; /* True if the node needs to be written to disk */ - u8 *zData; /* Content of the node, as should be on disk */ - RtreeNode *pNext; /* Next node in this hash collision chain */ -}; - -/* Return the number of cells in a node */ -#define NCELL(pNode) readInt16(&(pNode)->zData[2]) - -/* -** A single cell from a node, deserialized -*/ -struct RtreeCell { - i64 iRowid; /* Node or entry ID */ - RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */ -}; - - -/* -** This object becomes the sqlite3_user_data() for the SQL functions -** that are created by sqlite3_rtree_geometry_callback() and -** sqlite3_rtree_query_callback() and which appear on the right of MATCH -** operators in order to constrain a search. -** -** xGeom and xQueryFunc are the callback functions. Exactly one of -** xGeom and xQueryFunc fields is non-NULL, depending on whether the -** SQL function was created using sqlite3_rtree_geometry_callback() or -** sqlite3_rtree_query_callback(). -** -** This object is deleted automatically by the destructor mechanism in -** sqlite3_create_function_v2(). -*/ -struct RtreeGeomCallback { - int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*); - int (*xQueryFunc)(sqlite3_rtree_query_info*); - void (*xDestructor)(void*); - void *pContext; -}; - - -/* -** 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 (in the form of a BLOB) is returned by -** the SQL functions that sqlite3_rtree_geometry_callback() and -** sqlite3_rtree_query_callback() create, and is read as the right-hand -** operand to the MATCH operator of an R-Tree. -*/ -struct RtreeMatchArg { - u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ - RtreeGeomCallback cb; /* Info about the callback functions */ - int nParam; /* Number of parameters to the SQL function */ - sqlite3_value **apSqlParam; /* Original SQL parameter values */ - RtreeDValue aParam[1]; /* Values for parameters to the SQL function */ -}; - -#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){ - pCoord->u = ( - (((u32)p[0]) << 24) + - (((u32)p[1]) << 16) + - (((u32)p[2]) << 8) + - (((u32)p[3]) << 0) - ); -} -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 = pCoord->u; - 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 % 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_VTAB; - } - } - - /* 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_VTAB. - */ - if( pNode && rc==SQLITE_OK ){ - if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ - rc = SQLITE_CORRUPT_VTAB; - } - } - - if( rc==SQLITE_OK ){ - if( pNode!=0 ){ - nodeHashInsert(pRtree, pNode); - }else{ - rc = SQLITE_CORRUPT_VTAB; - } - *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, /* The overall R-Tree */ - RtreeNode *pNode, /* The node into which the cell is to be written */ - RtreeCell *pCell, /* The cell to write */ - int iCell /* Index into pNode into which pCell is written */ -){ - 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 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, /* The overall R-Tree */ - RtreeNode *pNode, /* Write new cell into this node */ - RtreeCell *pCell /* The cell to be inserted */ -){ - 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, /* The overall R-Tree */ - RtreeNode *pNode, /* The node from which to extract the ID */ - int iCell /* The cell index from which to extract the ID */ -){ - 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, /* The overall R-Tree */ - RtreeNode *pNode, /* The node from which to extract a coordinate */ - int iCell, /* The index of the cell within the node */ - int iCoord, /* Which coordinate to extract */ - RtreeCoord *pCoord /* OUT: 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, /* The overall R-Tree */ - RtreeNode *pNode, /* The node containing the cell to be read */ - int iCell, /* Index of the cell within the node */ - RtreeCell *pCell /* OUT: Write the cell contents here */ -){ - u8 *pData; - RtreeCoord *pCoord; - int ii; - pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); - pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); - pCoord = pCell->aCoord; - for(ii=0; ii<pRtree->nDim*2; ii++){ - readCoord(&pData[ii*4], &pCoord[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_query_info *pInfo = pCsr->aConstraint[i].pInfo; - if( pInfo ){ - if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser); - sqlite3_free(pInfo); - } - } - 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 ii; - RtreeCursor *pCsr = (RtreeCursor *)cur; - freeCursorConstraints(pCsr); - sqlite3_free(pCsr->aPoint); - for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); - sqlite3_free(pCsr); - return SQLITE_OK; -} - -/* -** 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->atEOF; -} - -/* -** Convert raw bits from the on-disk RTree record into a coordinate value. -** The on-disk format is big-endian and needs to be converted for little- -** endian platforms. The on-disk record stores integer coordinates if -** eInt is true and it stores 32-bit floating point records if eInt is -** false. a[] is the four bytes of the on-disk record to be decoded. -** Store the results in "r". -** -** There are three versions of this macro, one each for little-endian and -** big-endian processors and a third generic implementation. The endian- -** specific implementations are much faster and are preferred if the -** processor endianness is known at compile-time. The SQLITE_BYTEORDER -** macro is part of sqliteInt.h and hence the endian-specific -** implementation will only be used if this module is compiled as part -** of the amalgamation. -*/ -#if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234 -#define RTREE_DECODE_COORD(eInt, a, r) { \ - RtreeCoord c; /* Coordinate decoded */ \ - memcpy(&c.u,a,4); \ - c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \ - ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \ - r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ -} -#elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321 -#define RTREE_DECODE_COORD(eInt, a, r) { \ - RtreeCoord c; /* Coordinate decoded */ \ - memcpy(&c.u,a,4); \ - r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ -} -#else -#define RTREE_DECODE_COORD(eInt, a, r) { \ - RtreeCoord c; /* Coordinate decoded */ \ - c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \ - +((u32)a[2]<<8) + a[3]; \ - r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ -} -#endif - -/* -** Check the RTree node or entry given by pCellData and p against the MATCH -** constraint pConstraint. -*/ -static int rtreeCallbackConstraint( - RtreeConstraint *pConstraint, /* The constraint to test */ - int eInt, /* True if RTree holding integer coordinates */ - u8 *pCellData, /* Raw cell content */ - RtreeSearchPoint *pSearch, /* Container of this cell */ - sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */ - int *peWithin /* OUT: visibility of the cell */ -){ - int i; /* Loop counter */ - sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */ - int nCoord = pInfo->nCoord; /* No. of coordinates */ - int rc; /* Callback return code */ - sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */ - - assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY ); - assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 ); - - if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){ - pInfo->iRowid = readInt64(pCellData); - } - pCellData += 8; - for(i=0; i<nCoord; i++, pCellData += 4){ - RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]); - } - if( pConstraint->op==RTREE_MATCH ){ - rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo, - nCoord, aCoord, &i); - if( i==0 ) *peWithin = NOT_WITHIN; - *prScore = RTREE_ZERO; - }else{ - pInfo->aCoord = aCoord; - pInfo->iLevel = pSearch->iLevel - 1; - pInfo->rScore = pInfo->rParentScore = pSearch->rScore; - pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin; - rc = pConstraint->u.xQueryFunc(pInfo); - if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin; - if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){ - *prScore = pInfo->rScore; - } - } - return rc; -} - -/* -** Check the internal RTree node given by pCellData against constraint p. -** If this constraint cannot be satisfied by any child within the node, -** set *peWithin to NOT_WITHIN. -*/ -static void rtreeNonleafConstraint( - RtreeConstraint *p, /* The constraint to test */ - int eInt, /* True if RTree holds integer coordinates */ - u8 *pCellData, /* Raw cell content as appears on disk */ - int *peWithin /* Adjust downward, as appropriate */ -){ - sqlite3_rtree_dbl val; /* Coordinate value convert to a double */ - - /* p->iCoord might point to either a lower or upper bound coordinate - ** in a coordinate pair. But make pCellData point to the lower bound. - */ - pCellData += 8 + 4*(p->iCoord&0xfe); - - assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE - || p->op==RTREE_GT || p->op==RTREE_EQ ); - switch( p->op ){ - case RTREE_LE: - case RTREE_LT: - case RTREE_EQ: - RTREE_DECODE_COORD(eInt, pCellData, val); - /* val now holds the lower bound of the coordinate pair */ - if( p->u.rValue>=val ) return; - if( p->op!=RTREE_EQ ) break; /* RTREE_LE and RTREE_LT end here */ - /* Fall through for the RTREE_EQ case */ - - default: /* RTREE_GT or RTREE_GE, or fallthrough of RTREE_EQ */ - pCellData += 4; - RTREE_DECODE_COORD(eInt, pCellData, val); - /* val now holds the upper bound of the coordinate pair */ - if( p->u.rValue<=val ) return; - } - *peWithin = NOT_WITHIN; -} - -/* -** Check the leaf RTree cell given by pCellData against constraint p. -** If this constraint is not satisfied, set *peWithin to NOT_WITHIN. -** If the constraint is satisfied, leave *peWithin unchanged. -** -** The constraint is of the form: xN op $val -** -** The op is given by p->op. The xN is p->iCoord-th coordinate in -** pCellData. $val is given by p->u.rValue. -*/ -static void rtreeLeafConstraint( - RtreeConstraint *p, /* The constraint to test */ - int eInt, /* True if RTree holds integer coordinates */ - u8 *pCellData, /* Raw cell content as appears on disk */ - int *peWithin /* Adjust downward, as appropriate */ -){ - RtreeDValue xN; /* Coordinate value converted to a double */ - - assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE - || p->op==RTREE_GT || p->op==RTREE_EQ ); - pCellData += 8 + p->iCoord*4; - RTREE_DECODE_COORD(eInt, pCellData, xN); - switch( p->op ){ - case RTREE_LE: if( xN <= p->u.rValue ) return; break; - case RTREE_LT: if( xN < p->u.rValue ) return; break; - case RTREE_GE: if( xN >= p->u.rValue ) return; break; - case RTREE_GT: if( xN > p->u.rValue ) return; break; - default: if( xN == p->u.rValue ) return; break; - } - *peWithin = NOT_WITHIN; -} - -/* -** 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); - assert( nCell<200 ); - for(ii=0; ii<nCell; ii++){ - if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ - *piIndex = ii; - return SQLITE_OK; - } - } - return SQLITE_CORRUPT_VTAB; -} - -/* -** 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; -} - -/* -** Compare two search points. Return negative, zero, or positive if the first -** is less than, equal to, or greater than the second. -** -** The rScore is the primary key. Smaller rScore values come first. -** If the rScore is a tie, then use iLevel as the tie breaker with smaller -** iLevel values coming first. In this way, if rScore is the same for all -** SearchPoints, then iLevel becomes the deciding factor and the result -** is a depth-first search, which is the desired default behavior. -*/ -static int rtreeSearchPointCompare( - const RtreeSearchPoint *pA, - const RtreeSearchPoint *pB -){ - if( pA->rScore<pB->rScore ) return -1; - if( pA->rScore>pB->rScore ) return +1; - if( pA->iLevel<pB->iLevel ) return -1; - if( pA->iLevel>pB->iLevel ) return +1; - return 0; -} - -/* -** Interchange to search points in a cursor. -*/ -static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){ - RtreeSearchPoint t = p->aPoint[i]; - assert( i<j ); - p->aPoint[i] = p->aPoint[j]; - p->aPoint[j] = t; - i++; j++; - if( i<RTREE_CACHE_SZ ){ - if( j>=RTREE_CACHE_SZ ){ - nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); - p->aNode[i] = 0; - }else{ - RtreeNode *pTemp = p->aNode[i]; - p->aNode[i] = p->aNode[j]; - p->aNode[j] = pTemp; - } - } -} - -/* -** Return the search point with the lowest current score. -*/ -static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){ - return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0; -} - -/* -** Get the RtreeNode for the search point with the lowest score. -*/ -static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){ - sqlite3_int64 id; - int ii = 1 - pCur->bPoint; - assert( ii==0 || ii==1 ); - assert( pCur->bPoint || pCur->nPoint ); - if( pCur->aNode[ii]==0 ){ - assert( pRC!=0 ); - id = ii ? pCur->aPoint[0].id : pCur->sPoint.id; - *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]); - } - return pCur->aNode[ii]; -} - -/* -** Push a new element onto the priority queue -*/ -static RtreeSearchPoint *rtreeEnqueue( - RtreeCursor *pCur, /* The cursor */ - RtreeDValue rScore, /* Score for the new search point */ - u8 iLevel /* Level for the new search point */ -){ - int i, j; - RtreeSearchPoint *pNew; - if( pCur->nPoint>=pCur->nPointAlloc ){ - int nNew = pCur->nPointAlloc*2 + 8; - pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0])); - if( pNew==0 ) return 0; - pCur->aPoint = pNew; - pCur->nPointAlloc = nNew; - } - i = pCur->nPoint++; - pNew = pCur->aPoint + i; - pNew->rScore = rScore; - pNew->iLevel = iLevel; - assert( iLevel<=RTREE_MAX_DEPTH ); - while( i>0 ){ - RtreeSearchPoint *pParent; - j = (i-1)/2; - pParent = pCur->aPoint + j; - if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break; - rtreeSearchPointSwap(pCur, j, i); - i = j; - pNew = pParent; - } - return pNew; -} - -/* -** Allocate a new RtreeSearchPoint and return a pointer to it. Return -** NULL if malloc fails. -*/ -static RtreeSearchPoint *rtreeSearchPointNew( - RtreeCursor *pCur, /* The cursor */ - RtreeDValue rScore, /* Score for the new search point */ - u8 iLevel /* Level for the new search point */ -){ - RtreeSearchPoint *pNew, *pFirst; - pFirst = rtreeSearchPointFirst(pCur); - pCur->anQueue[iLevel]++; - if( pFirst==0 - || pFirst->rScore>rScore - || (pFirst->rScore==rScore && pFirst->iLevel>iLevel) - ){ - if( pCur->bPoint ){ - int ii; - pNew = rtreeEnqueue(pCur, rScore, iLevel); - if( pNew==0 ) return 0; - ii = (int)(pNew - pCur->aPoint) + 1; - if( ii<RTREE_CACHE_SZ ){ - assert( pCur->aNode[ii]==0 ); - pCur->aNode[ii] = pCur->aNode[0]; - }else{ - nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]); - } - pCur->aNode[0] = 0; - *pNew = pCur->sPoint; - } - pCur->sPoint.rScore = rScore; - pCur->sPoint.iLevel = iLevel; - pCur->bPoint = 1; - return &pCur->sPoint; - }else{ - return rtreeEnqueue(pCur, rScore, iLevel); - } -} - -#if 0 -/* Tracing routines for the RtreeSearchPoint queue */ -static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){ - if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); } - printf(" %d.%05lld.%02d %g %d", - p->iLevel, p->id, p->iCell, p->rScore, p->eWithin - ); - idx++; - if( idx<RTREE_CACHE_SZ ){ - printf(" %p\n", pCur->aNode[idx]); - }else{ - printf("\n"); - } -} -static void traceQueue(RtreeCursor *pCur, const char *zPrefix){ - int ii; - printf("=== %9s ", zPrefix); - if( pCur->bPoint ){ - tracePoint(&pCur->sPoint, -1, pCur); - } - for(ii=0; ii<pCur->nPoint; ii++){ - if( ii>0 || pCur->bPoint ) printf(" "); - tracePoint(&pCur->aPoint[ii], ii, pCur); - } -} -# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B) -#else -# define RTREE_QUEUE_TRACE(A,B) /* no-op */ -#endif - -/* Remove the search point with the lowest current score. -*/ -static void rtreeSearchPointPop(RtreeCursor *p){ - int i, j, k, n; - i = 1 - p->bPoint; - assert( i==0 || i==1 ); - if( p->aNode[i] ){ - nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); - p->aNode[i] = 0; - } - if( p->bPoint ){ - p->anQueue[p->sPoint.iLevel]--; - p->bPoint = 0; - }else if( p->nPoint ){ - p->anQueue[p->aPoint[0].iLevel]--; - n = --p->nPoint; - p->aPoint[0] = p->aPoint[n]; - if( n<RTREE_CACHE_SZ-1 ){ - p->aNode[1] = p->aNode[n+1]; - p->aNode[n+1] = 0; - } - i = 0; - while( (j = i*2+1)<n ){ - k = j+1; - if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){ - if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){ - rtreeSearchPointSwap(p, i, k); - i = k; - }else{ - break; - } - }else{ - if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){ - rtreeSearchPointSwap(p, i, j); - i = j; - }else{ - break; - } - } - } - } -} - - -/* -** Continue the search on cursor pCur until the front of the queue -** contains an entry suitable for returning as a result-set row, -** or until the RtreeSearchPoint queue is empty, indicating that the -** query has completed. -*/ -static int rtreeStepToLeaf(RtreeCursor *pCur){ - RtreeSearchPoint *p; - Rtree *pRtree = RTREE_OF_CURSOR(pCur); - RtreeNode *pNode; - int eWithin; - int rc = SQLITE_OK; - int nCell; - int nConstraint = pCur->nConstraint; - int ii; - int eInt; - RtreeSearchPoint x; - - eInt = pRtree->eCoordType==RTREE_COORD_INT32; - while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){ - pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc); - if( rc ) return rc; - nCell = NCELL(pNode); - assert( nCell<200 ); - while( p->iCell<nCell ){ - sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1; - u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell); - eWithin = FULLY_WITHIN; - for(ii=0; ii<nConstraint; ii++){ - RtreeConstraint *pConstraint = pCur->aConstraint + ii; - if( pConstraint->op>=RTREE_MATCH ){ - rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p, - &rScore, &eWithin); - if( rc ) return rc; - }else if( p->iLevel==1 ){ - rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin); - }else{ - rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin); - } - if( eWithin==NOT_WITHIN ) break; - } - p->iCell++; - if( eWithin==NOT_WITHIN ) continue; - x.iLevel = p->iLevel - 1; - if( x.iLevel ){ - x.id = readInt64(pCellData); - x.iCell = 0; - }else{ - x.id = p->id; - x.iCell = p->iCell - 1; - } - if( p->iCell>=nCell ){ - RTREE_QUEUE_TRACE(pCur, "POP-S:"); - rtreeSearchPointPop(pCur); - } - if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO; - p = rtreeSearchPointNew(pCur, rScore, x.iLevel); - if( p==0 ) return SQLITE_NOMEM; - p->eWithin = eWithin; - p->id = x.id; - p->iCell = x.iCell; - RTREE_QUEUE_TRACE(pCur, "PUSH-S:"); - break; - } - if( p->iCell>=nCell ){ - RTREE_QUEUE_TRACE(pCur, "POP-Se:"); - rtreeSearchPointPop(pCur); - } - } - pCur->atEOF = p==0; - return SQLITE_OK; -} - -/* -** Rtree virtual table module xNext method. -*/ -static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){ - RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; - int rc = SQLITE_OK; - - /* Move to the next entry that matches the configured constraints. */ - RTREE_QUEUE_TRACE(pCsr, "POP-Nx:"); - rtreeSearchPointPop(pCsr); - rc = rtreeStepToLeaf(pCsr); - return rc; -} - -/* -** Rtree virtual table module xRowid method. -*/ -static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ - RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; - RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); - int rc = SQLITE_OK; - RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); - if( rc==SQLITE_OK && p ){ - *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell); - } - return rc; -} - -/* -** 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; - RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); - RtreeCoord c; - int rc = SQLITE_OK; - RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); - - if( rc ) return rc; - if( p==0 ) return SQLITE_OK; - if( i==0 ){ - sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); - }else{ - if( rc ) return rc; - nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); -#ifndef SQLITE_RTREE_INT_ONLY - if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ - sqlite3_result_double(ctx, c.f); - }else -#endif - { - 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, /* RTree to search */ - i64 iRowid, /* The rowid searching for */ - RtreeNode **ppLeaf, /* Write the node here */ - sqlite3_int64 *piNode /* Write the node-id here */ -){ - 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); - if( piNode ) *piNode = iNode; - 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 *pBlob; /* BLOB returned by geometry function */ - sqlite3_rtree_query_info *pInfo; /* Callback information */ - int nBlob; /* Size of the geometry function blob */ - int nExpected; /* Expected size of the BLOB */ - - /* 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) ){ - return SQLITE_ERROR; - } - - pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob ); - if( !pInfo ) return SQLITE_NOMEM; - memset(pInfo, 0, sizeof(*pInfo)); - pBlob = (RtreeMatchArg*)&pInfo[1]; - - memcpy(pBlob, sqlite3_value_blob(pValue), nBlob); - nExpected = (int)(sizeof(RtreeMatchArg) + - pBlob->nParam*sizeof(sqlite3_value*) + - (pBlob->nParam-1)*sizeof(RtreeDValue)); - if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){ - sqlite3_free(pInfo); - return SQLITE_ERROR; - } - pInfo->pContext = pBlob->cb.pContext; - pInfo->nParam = pBlob->nParam; - pInfo->aParam = pBlob->aParam; - pInfo->apSqlParam = pBlob->apSqlParam; - - if( pBlob->cb.xGeom ){ - pCons->u.xGeom = pBlob->cb.xGeom; - }else{ - pCons->op = RTREE_QUERY; - pCons->u.xQueryFunc = pBlob->cb.xQueryFunc; - } - pCons->pInfo = pInfo; - 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; - int iCell = 0; - - rtreeReference(pRtree); - - /* Reset the cursor to the same state as rtreeOpen() leaves it in. */ - freeCursorConstraints(pCsr); - sqlite3_free(pCsr->aPoint); - memset(pCsr, 0, sizeof(RtreeCursor)); - pCsr->base.pVtab = (sqlite3_vtab*)pRtree; - - pCsr->iStrategy = idxNum; - if( idxNum==1 ){ - /* Special case - lookup by rowid. */ - RtreeNode *pLeaf; /* Leaf on which the required cell resides */ - RtreeSearchPoint *p; /* Search point for the the leaf */ - i64 iRowid = sqlite3_value_int64(argv[0]); - i64 iNode = 0; - rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); - if( rc==SQLITE_OK && pLeaf!=0 ){ - p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0); - assert( p!=0 ); /* Always returns pCsr->sPoint */ - pCsr->aNode[0] = pLeaf; - p->id = iNode; - p->eWithin = PARTLY_WITHIN; - rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); - p->iCell = iCell; - RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:"); - }else{ - pCsr->atEOF = 1; - } - }else{ - /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array - ** with the configured constraints. - */ - rc = nodeAcquire(pRtree, 1, 0, &pRoot); - if( rc==SQLITE_OK && 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); - memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); - assert( (idxStr==0 && argc==0) - || (idxStr && (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]-'0'; - 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; - } - p->pInfo->nCoord = pRtree->nDim*2; - p->pInfo->anQueue = pCsr->anQueue; - p->pInfo->mxLevel = pRtree->iDepth + 1; - }else{ -#ifdef SQLITE_RTREE_INT_ONLY - p->u.rValue = sqlite3_value_int64(argv[ii]); -#else - p->u.rValue = sqlite3_value_double(argv[ii]); -#endif - } - } - } - } - if( rc==SQLITE_OK ){ - RtreeSearchPoint *pNew; - pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1); - if( pNew==0 ) return SQLITE_NOMEM; - pNew->id = 1; - pNew->iCell = 0; - pNew->eWithin = PARTLY_WITHIN; - assert( pCsr->bPoint==1 ); - pCsr->aNode[0] = pRoot; - pRoot = 0; - RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); - rc = rtreeStepToLeaf(pCsr); - } - } - - nodeRelease(pRtree, pRoot); - rtreeRelease(pRtree); - return rc; -} - -/* -** Set the pIdxInfo->estimatedRows variable to nRow. Unless this -** extension is currently being used by a version of SQLite too old to -** support estimatedRows. In that case this function is a no-op. -*/ -static void setEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){ -#if SQLITE_VERSION_NUMBER>=3008002 - if( sqlite3_libversion_number()>=3008002 ){ - pIdxInfo->estimatedRows = nRow; - } -#endif -} - -/* -** 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){ - Rtree *pRtree = (Rtree*)tab; - int rc = SQLITE_OK; - int ii; - int bMatch = 0; /* True if there exists a MATCH constraint */ - i64 nRow; /* Estimated rows returned by this scan */ - - int iIdx = 0; - char zIdxStr[RTREE_MAX_DIMENSIONS*8+1]; - memset(zIdxStr, 0, sizeof(zIdxStr)); - - /* Check if there exists a MATCH constraint - even an unusable one. If there - ** is, do not consider the lookup-by-rowid plan as using such a plan would - ** require the VDBE to evaluate the MATCH constraint, which is not currently - ** possible. */ - for(ii=0; ii<pIdxInfo->nConstraint; ii++){ - if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){ - bMatch = 1; - } - } - - 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( bMatch==0 && 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). It is expected to return - ** a single row. - */ - pIdxInfo->estimatedCost = 30.0; - setEstimatedRows(pIdxInfo, 1); - 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 + '0'; - 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; - } - - nRow = pRtree->nRowEst / (iIdx + 1); - pIdxInfo->estimatedCost = (double)6.0 * (double)nRow; - setEstimatedRows(pIdxInfo, nRow); - - return rc; -} - -/* -** Return the N-dimensional volumn of the cell stored in *p. -*/ -static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){ - RtreeDValue area = (RtreeDValue)1; - 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 RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){ - RtreeDValue margin = (RtreeDValue)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 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 -){ - int ii; - RtreeDValue overlap = RTREE_ZERO; - for(ii=0; ii<nCell; ii++){ - int jj; - RtreeDValue o = (RtreeDValue)1; - for(jj=0; jj<(pRtree->nDim*2); jj+=2){ - RtreeDValue x1, 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 = (RtreeDValue)0; - break; - }else{ - o = o * (x2-x1); - } - } - overlap += o; - } - return overlap; -} - - -/* -** 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 = 0; - - RtreeDValue fMinGrowth = RTREE_ZERO; - RtreeDValue fMinArea = RTREE_ZERO; - - int nCell = NCELL(pNode); - RtreeCell cell; - RtreeNode *pChild; - - 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. - */ - for(iCell=0; iCell<nCell; iCell++){ - int bBest = 0; - RtreeDValue growth; - RtreeDValue area; - nodeGetCell(pRtree, pNode, iCell, &cell); - growth = cellGrowth(pRtree, &cell, pCell); - area = cellArea(pRtree, &cell); - if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){ - bBest = 1; - } - if( bBest ){ - 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_VTAB; - } - - 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); - - -/* -** 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, - RtreeDValue *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{ - RtreeDValue fLeft = aDistance[aLeft[iLeft]]; - RtreeDValue 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++){ - RtreeDValue left = aDistance[aIdx[jj-1]]; - RtreeDValue 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 ){ - RtreeDValue xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]); - RtreeDValue xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]); - RtreeDValue xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]); - RtreeDValue 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++){ - RtreeDValue xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; - RtreeDValue xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; - RtreeDValue xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; - RtreeDValue xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; - assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); - } - } -#endif - } -} - -/* -** 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 = 0; - int iBestSplit = 0; - RtreeDValue fBestMargin = RTREE_ZERO; - - 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++){ - RtreeDValue margin = RTREE_ZERO; - RtreeDValue fBestOverlap = RTREE_ZERO; - RtreeDValue fBestArea = RTREE_ZERO; - int iBestLeft = 0; - int nLeft; - - for( - nLeft=RTREE_MINCELLS(pRtree); - nLeft<=(nCell-RTREE_MINCELLS(pRtree)); - nLeft++ - ){ - RtreeCell left; - RtreeCell right; - int kk; - RtreeDValue overlap; - RtreeDValue 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); - 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; -} - - -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 = splitNodeStartree(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_VTAB; - 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 = 0; - 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; - RtreeDValue *aDistance; - int nCell; - RtreeDValue aCenterCoord[RTREE_MAX_DIMENSIONS]; - int iDim; - int ii; - int rc = SQLITE_OK; - int n; - - memset(aCenterCoord, 0, sizeof(RtreeDValue)*RTREE_MAX_DIMENSIONS); - - nCell = NCELL(pNode)+1; - n = (nCell+1)&(~1); - - /* Allocate the buffers used by this operation. The allocation is - ** relinquished before this function returns. - */ - aCell = (RtreeCell *)sqlite3_malloc(n * ( - sizeof(RtreeCell) + /* aCell array */ - sizeof(int) + /* aOrder array */ - sizeof(int) + /* aSpare array */ - sizeof(RtreeDValue) /* aDistance array */ - )); - if( !aCell ){ - return SQLITE_NOMEM; - } - aOrder = (int *)&aCell[n]; - aSpare = (int *)&aOrder[n]; - aDistance = (RtreeDValue *)&aSpare[n]; - - 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]/(nCell*(RtreeDValue)2)); - } - - for(ii=0; ii<nCell; ii++){ - aDistance[ii] = RTREE_ZERO; - for(iDim=0; iDim<pRtree->nDim; 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 && 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( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ - rc = SplitNode(pRtree, pNode, pCell, iHeight); - }else{ - pRtree->iReinsertHeight = iHeight; - rc = Reinsert(pRtree, pNode, pCell, iHeight); - } - }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, (int)pNode->iNode, &pInsert); - if( rc==SQLITE_OK ){ - int rc2; - rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)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; -} - -/* -** Remove the entry with rowid=iDelete from the r-tree structure. -*/ -static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){ - int rc; /* Return code */ - RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */ - int iCell; /* Index of iDelete cell in pLeaf */ - RtreeNode *pRoot; /* Root node of rtree structure */ - - - /* Obtain a reference to the root node to initialize 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 ){ - rc = findLeafNode(pRtree, iDelete, &pLeaf, 0); - } - - /* 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); - } - - return rc; -} - -/* -** Rounding constants for float->double conversion. -*/ -#define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */ -#define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */ - -#if !defined(SQLITE_RTREE_INT_ONLY) -/* -** Convert an sqlite3_value into an RtreeValue (presumably a float) -** while taking care to round toward negative or positive, respectively. -*/ -static RtreeValue rtreeValueDown(sqlite3_value *v){ - double d = sqlite3_value_double(v); - float f = (float)d; - if( f>d ){ - f = (float)(d*(d<0 ? RNDAWAY : RNDTOWARDS)); - } - return f; -} -static RtreeValue rtreeValueUp(sqlite3_value *v){ - double d = sqlite3_value_double(v); - float f = (float)d; - if( f<d ){ - f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY)); - } - return f; -} -#endif /* !defined(SQLITE_RTREE_INT_ONLY) */ - - -/* -** 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; - RtreeCell cell; /* New cell to insert if nData>1 */ - int bHaveRowid = 0; /* Set to 1 after new rowid is determined */ - - rtreeReference(pRtree); - assert(nData>=1); - - cell.iRowid = 0; /* Used only to suppress a compiler warning */ - - /* Constraint handling. A write operation on an r-tree table may return - ** SQLITE_CONSTRAINT for two reasons: - ** - ** 1. A duplicate rowid value, or - ** 2. The supplied data violates the "x2>=x1" constraint. - ** - ** In the first case, if the conflict-handling mode is REPLACE, then - ** the conflicting row can be removed before proceeding. In the second - ** case, SQLITE_CONSTRAINT must be returned regardless of the - ** conflict-handling mode specified by the user. - */ - if( nData>1 ){ - int ii; - - /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. - ** - ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared - ** with "column" that are interpreted as table constraints. - ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5)); - ** This problem was discovered after years of use, so we silently ignore - ** these kinds of misdeclared tables to avoid breaking any legacy. - */ - assert( nData<=(pRtree->nDim*2 + 3) ); - -#ifndef SQLITE_RTREE_INT_ONLY - if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ - for(ii=0; ii<nData-4; ii+=2){ - cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]); - cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]); - if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ - rc = SQLITE_CONSTRAINT; - goto constraint; - } - } - }else -#endif - { - for(ii=0; ii<nData-4; 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; - } - } - } - - /* If a rowid value was supplied, check if it is already present in - ** the table. If so, the constraint has failed. */ - if( sqlite3_value_type(azData[2])!=SQLITE_NULL ){ - cell.iRowid = sqlite3_value_int64(azData[2]); - if( sqlite3_value_type(azData[0])==SQLITE_NULL - || sqlite3_value_int64(azData[0])!=cell.iRowid - ){ - int steprc; - sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); - steprc = sqlite3_step(pRtree->pReadRowid); - rc = sqlite3_reset(pRtree->pReadRowid); - if( SQLITE_ROW==steprc ){ - if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){ - rc = rtreeDeleteRowid(pRtree, cell.iRowid); - }else{ - rc = SQLITE_CONSTRAINT; - goto constraint; - } - } - } - bHaveRowid = 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 ){ - rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(azData[0])); - } - - /* 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 the new record into the r-tree */ - RtreeNode *pLeaf = 0; - - /* Figure out the rowid of the new row. */ - if( bHaveRowid==0 ){ - rc = newRowid(pRtree, &cell.iRowid); - } - *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; -} - -/* -** This function populates the pRtree->nRowEst variable with an estimate -** of the number of rows in the virtual table. If possible, this is based -** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST. -*/ -static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){ - const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'"; - char *zSql; - sqlite3_stmt *p; - int rc; - i64 nRow = 0; - - zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName); - if( zSql==0 ){ - rc = SQLITE_NOMEM; - }else{ - rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0); - if( rc==SQLITE_OK ){ - if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0); - rc = sqlite3_finalize(p); - }else if( rc!=SQLITE_NOMEM ){ - rc = SQLITE_OK; - } - - if( rc==SQLITE_OK ){ - if( nRow==0 ){ - pRtree->nRowEst = RTREE_DEFAULT_ROWEST; - }else{ - pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST); - } - } - 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 */ - 0, /* xSavepoint */ - 0, /* xRelease */ - 0 /* xRollbackTo */ -}; - -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; - - rc = rtreeQueryStat1(db, pRtree); - 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 */ - char **pzErr /* OUT: Error message, if any */ -){ - int rc; - char *zSql; - if( isCreate ){ - int iPageSize = 0; - 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{ - *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); - } - }else{ - zSql = sqlite3_mprintf( - "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1", - pRtree->zDb, pRtree->zName - ); - rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize); - if( rc!=SQLITE_OK ){ - *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); - } - } - - 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 *pRtree; - int nDb; /* Length of string argv[1] */ - int nName; /* Length of string argv[2] */ - int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32); - - const char *aErrMsg[] = { - 0, /* 0 */ - "Wrong number of columns for an rtree table", /* 1 */ - "Too few columns for an rtree table", /* 2 */ - "Too many columns for an rtree table" /* 3 */ - }; - - int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2; - if( aErrMsg[iErr] ){ - *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]); - return SQLITE_ERROR; - } - - 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_malloc(sizeof(Rtree)+nDb+nName+2); - if( !pRtree ){ - return SQLITE_NOMEM; - } - memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); - pRtree->nBusy = 1; - pRtree->base.pModule = &rtreeModule; - pRtree->zDb = (char *)&pRtree[1]; - pRtree->zName = &pRtree->zDb[nDb+1]; - pRtree->nDim = (argc-4)/2; - pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2; - pRtree->eCoordType = eCoordType; - memcpy(pRtree->zDb, argv[1], nDb); - memcpy(pRtree->zName, argv[2], nName); - - /* Figure out the node size to use. */ - rc = getNodeSize(db, pRtree, isCreate, pzErr); - - /* Create/Connect to the underlying relational database schema. If - ** that is successful, call sqlite3_declare_vtab() to configure - ** the r-tree table schema. - */ - if( rc==SQLITE_OK ){ - if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){ - *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); - }else{ - char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]); - char *zTmp; - int ii; - for(ii=4; zSql && ii<argc; ii++){ - zTmp = zSql; - zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]); - sqlite3_free(zTmp); - } - if( zSql ){ - zTmp = zSql; - zSql = sqlite3_mprintf("%s);", zTmp); - sqlite3_free(zTmp); - } - if( !zSql ){ - rc = SQLITE_NOMEM; - }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){ - *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); - } - sqlite3_free(zSql); - } - } - - if( rc==SQLITE_OK ){ - *ppVtab = (sqlite3_vtab *)pRtree; - }else{ - assert( *ppVtab==0 ); - assert( pRtree->nBusy==1 ); - rtreeRelease(pRtree); - } - return rc; -} - - -/* -** Implementation of a scalar function that decodes r-tree nodes to -** human readable strings. This can be used for debugging and analysis. -** -** The scalar function takes two arguments: (1) the number of dimensions -** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing -** an r-tree node. For a two-dimensional r-tree structure called "rt", to -** deserialize all nodes, a statement like: -** -** SELECT rtreenode(2, data) FROM rt_node; -** -** The human readable string takes the form of a Tcl list with one -** entry for each cell in the r-tree node. Each entry is itself a -** list, containing the 8-byte rowid/pageno followed by the -** <num-dimension>*2 coordinates. -*/ -static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ - char *zText = 0; - RtreeNode node; - Rtree tree; - int ii; - - UNUSED_PARAMETER(nArg); - memset(&node, 0, sizeof(RtreeNode)); - memset(&tree, 0, sizeof(Rtree)); - tree.nDim = sqlite3_value_int(apArg[0]); - tree.nBytesPerCell = 8 + 8 * tree.nDim; - node.zData = (u8 *)sqlite3_value_blob(apArg[1]); - - for(ii=0; ii<NCELL(&node); ii++){ - char zCell[512]; - int nCell = 0; - RtreeCell cell; - int jj; - - nodeGetCell(&tree, &node, ii, &cell); - sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid); - nCell = (int)strlen(zCell); - for(jj=0; jj<tree.nDim*2; jj++){ -#ifndef SQLITE_RTREE_INT_ONLY - sqlite3_snprintf(512-nCell,&zCell[nCell], " %g", - (double)cell.aCoord[jj].f); -#else - sqlite3_snprintf(512-nCell,&zCell[nCell], " %d", - cell.aCoord[jj].i); -#endif - nCell = (int)strlen(zCell); - } - - if( zText ){ - char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell); - sqlite3_free(zText); - zText = zTextNew; - }else{ - zText = sqlite3_mprintf("{%s}", zCell); - } - } - - sqlite3_result_text(ctx, zText, -1, sqlite3_free); -} - -/* This routine implements an SQL function that returns the "depth" parameter -** from the front of a blob that is an r-tree node. For example: -** -** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1; -** -** The depth value is 0 for all nodes other than the root node, and the root -** node always has nodeno=1, so the example above is the primary use for this -** routine. This routine is intended for testing and analysis only. -*/ -static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ - UNUSED_PARAMETER(nArg); - if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB - || sqlite3_value_bytes(apArg[0])<2 - ){ - sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); - }else{ - u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]); - sqlite3_result_int(ctx, readInt16(zBlob)); - } -} - -/* -** Register the r-tree module with database handle db. This creates the -** virtual table module "rtree" and the debugging/analysis scalar -** function "rtreenode". -*/ -int sqlite3RtreeInit(sqlite3 *db){ - const int utf8 = SQLITE_UTF8; - int rc; - - rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0); - if( rc==SQLITE_OK ){ - rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0); - } - if( rc==SQLITE_OK ){ -#ifdef SQLITE_RTREE_INT_ONLY - void *c = (void *)RTREE_COORD_INT32; -#else - void *c = (void *)RTREE_COORD_REAL32; -#endif - rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0); - } - if( rc==SQLITE_OK ){ - void *c = (void *)RTREE_COORD_INT32; - rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); - } - - return rc; -} - -/* -** This routine deletes the RtreeGeomCallback object that was attached -** one of the SQL functions create by sqlite3_rtree_geometry_callback() -** or sqlite3_rtree_query_callback(). In other words, this routine is the -** destructor for an RtreeGeomCallback objecct. This routine is called when -** the corresponding SQL function is deleted. -*/ -static void rtreeFreeCallback(void *p){ - RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p; - if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext); - sqlite3_free(p); -} - -/* -** This routine frees the BLOB that is returned by geomCallback(). -*/ -static void rtreeMatchArgFree(void *pArg){ - int i; - RtreeMatchArg *p = (RtreeMatchArg*)pArg; - for(i=0; i<p->nParam; i++){ - sqlite3_value_free(p->apSqlParam[i]); - } - sqlite3_free(p); -} - -/* -** Each call to sqlite3_rtree_geometry_callback() or -** sqlite3_rtree_query_callback() creates an ordinary SQLite -** scalar function that is implemented by this routine. -** -** All this function does is construct an RtreeMatchArg object that -** contains the geometry-checking callback routines and a list of -** parameters to this function, then return that RtreeMatchArg object -** as a BLOB. -** -** The R-Tree MATCH operator will read the returned BLOB, deserialize -** the RtreeMatchArg object, and use the RtreeMatchArg object to figure -** out which elements of the R-Tree should be returned by the query. -*/ -static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){ - RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx); - RtreeMatchArg *pBlob; - int nBlob; - int memErr = 0; - - nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue) - + nArg*sizeof(sqlite3_value*); - pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob); - if( !pBlob ){ - sqlite3_result_error_nomem(ctx); - }else{ - int i; - pBlob->magic = RTREE_GEOMETRY_MAGIC; - pBlob->cb = pGeomCtx[0]; - pBlob->apSqlParam = (sqlite3_value**)&pBlob->aParam[nArg]; - pBlob->nParam = nArg; - for(i=0; i<nArg; i++){ - pBlob->apSqlParam[i] = sqlite3_value_dup(aArg[i]); - if( pBlob->apSqlParam[i]==0 ) memErr = 1; -#ifdef SQLITE_RTREE_INT_ONLY - pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); -#else - pBlob->aParam[i] = sqlite3_value_double(aArg[i]); -#endif - } - if( memErr ){ - sqlite3_result_error_nomem(ctx); - rtreeMatchArgFree(pBlob); - }else{ - sqlite3_result_blob(ctx, pBlob, nBlob, rtreeMatchArgFree); - } - } -} - -/* -** Register a new geometry function for use with the r-tree MATCH operator. -*/ -int sqlite3_rtree_geometry_callback( - sqlite3 *db, /* Register SQL function on this connection */ - const char *zGeom, /* Name of the new SQL function */ - int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */ - void *pContext /* Extra data associated with the callback */ -){ - RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ - - /* Allocate and populate the context object. */ - pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); - if( !pGeomCtx ) return SQLITE_NOMEM; - pGeomCtx->xGeom = xGeom; - pGeomCtx->xQueryFunc = 0; - pGeomCtx->xDestructor = 0; - pGeomCtx->pContext = pContext; - return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, - (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback - ); -} - -/* -** Register a new 2nd-generation geometry function for use with the -** r-tree MATCH operator. -*/ -int sqlite3_rtree_query_callback( - sqlite3 *db, /* Register SQL function on this connection */ - const char *zQueryFunc, /* Name of new SQL function */ - int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */ - void *pContext, /* Extra data passed into the callback */ - void (*xDestructor)(void*) /* Destructor for the extra data */ -){ - RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ - - /* Allocate and populate the context object. */ - pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); - if( !pGeomCtx ) return SQLITE_NOMEM; - pGeomCtx->xGeom = 0; - pGeomCtx->xQueryFunc = xQueryFunc; - pGeomCtx->xDestructor = xDestructor; - pGeomCtx->pContext = pContext; - return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, - (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback - ); -} - -#if !SQLITE_CORE -#ifdef _WIN32 -__declspec(dllexport) -#endif -int sqlite3_rtree_init( - sqlite3 *db, - char **pzErrMsg, - const sqlite3_api_routines *pApi -){ - SQLITE_EXTENSION_INIT2(pApi) - return sqlite3RtreeInit(db); -} -#endif - -#endif |