| Index: third_party/sqlite/src/ext/rtree/rtree.c
|
| diff --git a/third_party/sqlite/src/ext/rtree/rtree.c b/third_party/sqlite/src/ext/rtree/rtree.c
|
| index ebf430a98c6218d3970fa3dafd977c20c8aee46b..8150538d452d1b31ebc91b54b5fcb3e6dad8f3aa 100644
|
| --- a/third_party/sqlite/src/ext/rtree/rtree.c
|
| +++ b/third_party/sqlite/src/ext/rtree/rtree.c
|
| @@ -54,48 +54,6 @@
|
|
|
| #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
|
|
|
| -/*
|
| -** This file contains an implementation of a couple of different variants
|
| -** of the r-tree algorithm. See the README file for further details. The
|
| -** same data-structure is used for all, but the algorithms for insert and
|
| -** delete operations vary. The variants used are selected at compile time
|
| -** by defining the following symbols:
|
| -*/
|
| -
|
| -/* Either, both or none of the following may be set to activate
|
| -** r*tree variant algorithms.
|
| -*/
|
| -#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
|
| -#define VARIANT_RSTARTREE_REINSERT 1
|
| -
|
| -/*
|
| -** Exactly one of the following must be set to 1.
|
| -*/
|
| -#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
|
| -#define VARIANT_GUTTMAN_LINEAR_SPLIT 0
|
| -#define VARIANT_RSTARTREE_SPLIT 1
|
| -
|
| -#define VARIANT_GUTTMAN_SPLIT \
|
| - (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
|
| -
|
| -#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
|
| - #define PickNext QuadraticPickNext
|
| - #define PickSeeds QuadraticPickSeeds
|
| - #define AssignCells splitNodeGuttman
|
| -#endif
|
| -#if VARIANT_GUTTMAN_LINEAR_SPLIT
|
| - #define PickNext LinearPickNext
|
| - #define PickSeeds LinearPickSeeds
|
| - #define AssignCells splitNodeGuttman
|
| -#endif
|
| -#if VARIANT_RSTARTREE_SPLIT
|
| - #define AssignCells splitNodeStartree
|
| -#endif
|
| -
|
| -#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
|
| -# define NDEBUG 1
|
| -#endif
|
| -
|
| #ifndef SQLITE_CORE
|
| #include "sqlite3ext.h"
|
| SQLITE_EXTENSION_INIT1
|
| @@ -105,11 +63,13 @@
|
|
|
| #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
|
|
|
| @@ -127,6 +87,7 @@ 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
|
| @@ -135,22 +96,33 @@ typedef union RtreeCoord RtreeCoord;
|
| ** ever contain very many entries, so a fixed number of buckets is
|
| ** used.
|
| */
|
| -#define HASHSIZE 128
|
| +#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;
|
| + 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 */
|
| - int nDim; /* Number of dimensions */
|
| - int nBytesPerCell; /* Bytes consumed per cell */
|
| + 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 */
|
| - RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
|
| 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 -
|
| @@ -175,14 +147,46 @@ struct Rtree {
|
| sqlite3_stmt *pWriteParent;
|
| sqlite3_stmt *pDeleteParent;
|
|
|
| - int eCoordType;
|
| + RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
|
| };
|
|
|
| -/* Possible values for eCoordType: */
|
| +/* 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:
|
| **
|
| @@ -204,33 +208,61 @@ struct Rtree {
|
| */
|
| #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;
|
| - RtreeNode *pNode; /* Node cursor is currently pointing at */
|
| - int iCell; /* Index of current cell in pNode */
|
| + 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 {
|
| - float f;
|
| - int i;
|
| + 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 double. This macro assumes that local variable pRtree points
|
| -** to the Rtree structure associated with 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.
|
| */
|
| -#define DCOORD(coord) ( \
|
| - (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
|
| - ((double)coord.f) : \
|
| - ((double)coord.i) \
|
| -)
|
| +#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.
|
| @@ -238,38 +270,67 @@ union RtreeCoord {
|
| struct RtreeConstraint {
|
| int iCoord; /* Index of constrained coordinate */
|
| int op; /* Constraining operation */
|
| - double rValue; /* Constraint value. */
|
| - int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
|
| - sqlite3_rtree_geometry *pGeom; /* Constraint callback argument for a MATCH */
|
| + 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
|
| -#define RTREE_LE 0x42
|
| -#define RTREE_LT 0x43
|
| -#define RTREE_GE 0x44
|
| -#define RTREE_GT 0x45
|
| -#define RTREE_MATCH 0x46
|
| +#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;
|
| - int nRef;
|
| - int isDirty;
|
| - u8 *zData;
|
| - RtreeNode *pNext; /* Next node in this hash chain */
|
| + 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])
|
|
|
| /*
|
| -** Structure to store a deserialized rtree record.
|
| +** A single cell from a node, deserialized
|
| */
|
| struct RtreeCell {
|
| - i64 iRowid;
|
| - RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
|
| + 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;
|
| };
|
|
|
|
|
| @@ -281,29 +342,16 @@ struct RtreeCell {
|
| #define RTREE_GEOMETRY_MAGIC 0x891245AB
|
|
|
| /*
|
| -** An instance of this structure must be supplied as a blob argument to
|
| -** the right-hand-side of an SQL MATCH operator used to constrain an
|
| -** r-tree query.
|
| +** 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 */
|
| - int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
|
| - void *pContext;
|
| - int nParam;
|
| - double aParam[1];
|
| -};
|
| -
|
| -/*
|
| -** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
|
| -** a single instance of the following structure is allocated. It is used
|
| -** as the context for the user-function created by by s_r_g_c(). The object
|
| -** is eventually deleted by the destructor mechanism provided by
|
| -** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
|
| -** the geometry callback function).
|
| -*/
|
| -struct RtreeGeomCallback {
|
| - int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
|
| - void *pContext;
|
| + u32 magic; /* Always RTREE_GEOMETRY_MAGIC */
|
| + RtreeGeomCallback cb; /* Info about the callback functions */
|
| + int nParam; /* Number of parameters to the SQL function */
|
| + RtreeDValue aParam[1]; /* Values for parameters to the SQL function */
|
| };
|
|
|
| #ifndef MAX
|
| @@ -397,10 +445,7 @@ static void nodeZero(Rtree *pRtree, RtreeNode *p){
|
| ** in the Rtree.aHash table.
|
| */
|
| static int nodeHash(i64 iNode){
|
| - return (
|
| - (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^
|
| - (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
|
| - ) % HASHSIZE;
|
| + return iNode % HASHSIZE;
|
| }
|
|
|
| /*
|
| @@ -460,8 +505,7 @@ static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
|
| /*
|
| ** Obtain a reference to an r-tree node.
|
| */
|
| -static int
|
| -nodeAcquire(
|
| +static int nodeAcquire(
|
| Rtree *pRtree, /* R-tree structure */
|
| i64 iNode, /* Node number to load */
|
| RtreeNode *pParent, /* Either the parent node or NULL */
|
| @@ -517,17 +561,17 @@ nodeAcquire(
|
| if( pNode && iNode==1 ){
|
| pRtree->iDepth = readInt16(pNode->zData);
|
| if( pRtree->iDepth>RTREE_MAX_DEPTH ){
|
| - rc = SQLITE_CORRUPT;
|
| + 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.
|
| + ** SQLITE_CORRUPT_VTAB.
|
| */
|
| if( pNode && rc==SQLITE_OK ){
|
| if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
|
| - rc = SQLITE_CORRUPT;
|
| + rc = SQLITE_CORRUPT_VTAB;
|
| }
|
| }
|
|
|
| @@ -535,7 +579,7 @@ nodeAcquire(
|
| if( pNode!=0 ){
|
| nodeHashInsert(pRtree, pNode);
|
| }else{
|
| - rc = SQLITE_CORRUPT;
|
| + rc = SQLITE_CORRUPT_VTAB;
|
| }
|
| *ppNode = pNode;
|
| }else{
|
| @@ -550,10 +594,10 @@ nodeAcquire(
|
| ** Overwrite cell iCell of node pNode with the contents of pCell.
|
| */
|
| static void nodeOverwriteCell(
|
| - Rtree *pRtree,
|
| - RtreeNode *pNode,
|
| - RtreeCell *pCell,
|
| - int iCell
|
| + 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];
|
| @@ -565,7 +609,7 @@ static void nodeOverwriteCell(
|
| }
|
|
|
| /*
|
| -** Remove cell the cell with index iCell from node pNode.
|
| +** 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];
|
| @@ -582,11 +626,10 @@ static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
|
| **
|
| ** If there is not enough free space in pNode, return SQLITE_FULL.
|
| */
|
| -static int
|
| -nodeInsertCell(
|
| - Rtree *pRtree,
|
| - RtreeNode *pNode,
|
| - RtreeCell *pCell
|
| +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 */
|
| @@ -607,8 +650,7 @@ nodeInsertCell(
|
| /*
|
| ** If the node is dirty, write it out to the database.
|
| */
|
| -static int
|
| -nodeWrite(Rtree *pRtree, RtreeNode *pNode){
|
| +static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){
|
| int rc = SQLITE_OK;
|
| if( pNode->isDirty ){
|
| sqlite3_stmt *p = pRtree->pWriteNode;
|
| @@ -633,8 +675,7 @@ nodeWrite(Rtree *pRtree, RtreeNode *pNode){
|
| ** 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){
|
| +static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
|
| int rc = SQLITE_OK;
|
| if( pNode ){
|
| assert( pNode->nRef>0 );
|
| @@ -662,9 +703,9 @@ nodeRelease(Rtree *pRtree, RtreeNode *pNode){
|
| ** an internal node, then the 64-bit integer is a child page number.
|
| */
|
| static i64 nodeGetRowid(
|
| - Rtree *pRtree,
|
| - RtreeNode *pNode,
|
| - int iCell
|
| + 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]);
|
| @@ -674,11 +715,11 @@ static i64 nodeGetRowid(
|
| ** Return coordinate iCoord from cell iCell in node pNode.
|
| */
|
| static void nodeGetCoord(
|
| - Rtree *pRtree,
|
| - RtreeNode *pNode,
|
| - int iCell,
|
| - int iCoord,
|
| - RtreeCoord *pCoord /* Space to write result to */
|
| + 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);
|
| }
|
| @@ -688,15 +729,20 @@ static void nodeGetCoord(
|
| ** to by pCell with the results.
|
| */
|
| static void nodeGetCell(
|
| - Rtree *pRtree,
|
| - RtreeNode *pNode,
|
| - int iCell,
|
| - RtreeCell *pCell
|
| + 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 */
|
| ){
|
| - int ii;
|
| + u8 *pData;
|
| + u8 *pEnd;
|
| + RtreeCoord *pCoord;
|
| pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
|
| - for(ii=0; ii<pRtree->nDim*2; ii++){
|
| - nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
|
| + pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
|
| + pEnd = pData + pRtree->nDim*8;
|
| + pCoord = pCell->aCoord;
|
| + for(; pData<pEnd; pData+=4, pCoord++){
|
| + readCoord(pData, pCoord);
|
| }
|
| }
|
|
|
| @@ -822,10 +868,10 @@ static void freeCursorConstraints(RtreeCursor *pCsr){
|
| if( pCsr->aConstraint ){
|
| int i; /* Used to iterate through constraint array */
|
| for(i=0; i<pCsr->nConstraint; i++){
|
| - sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
|
| - if( pGeom ){
|
| - if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
|
| - sqlite3_free(pGeom);
|
| + sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
|
| + if( pInfo ){
|
| + if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
|
| + sqlite3_free(pInfo);
|
| }
|
| }
|
| sqlite3_free(pCsr->aConstraint);
|
| @@ -838,12 +884,13 @@ static void freeCursorConstraints(RtreeCursor *pCsr){
|
| */
|
| static int rtreeClose(sqlite3_vtab_cursor *cur){
|
| Rtree *pRtree = (Rtree *)(cur->pVtab);
|
| - int rc;
|
| + int ii;
|
| RtreeCursor *pCsr = (RtreeCursor *)cur;
|
| freeCursorConstraints(pCsr);
|
| - rc = nodeRelease(pRtree, pCsr->pNode);
|
| + sqlite3_free(pCsr->aPoint);
|
| + for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
|
| sqlite3_free(pCsr);
|
| - return rc;
|
| + return SQLITE_OK;
|
| }
|
|
|
| /*
|
| @@ -854,194 +901,164 @@ static int rtreeClose(sqlite3_vtab_cursor *cur){
|
| */
|
| static int rtreeEof(sqlite3_vtab_cursor *cur){
|
| RtreeCursor *pCsr = (RtreeCursor *)cur;
|
| - return (pCsr->pNode==0);
|
| + return pCsr->atEOF;
|
| }
|
|
|
| /*
|
| -** The r-tree constraint passed as the second argument to this function is
|
| -** guaranteed to be a MATCH constraint.
|
| -*/
|
| -static int testRtreeGeom(
|
| - Rtree *pRtree, /* R-Tree object */
|
| - RtreeConstraint *pConstraint, /* MATCH constraint to test */
|
| - RtreeCell *pCell, /* Cell to test */
|
| - int *pbRes /* OUT: Test result */
|
| -){
|
| - int i;
|
| - double aCoord[RTREE_MAX_DIMENSIONS*2];
|
| - int nCoord = pRtree->nDim*2;
|
| -
|
| - assert( pConstraint->op==RTREE_MATCH );
|
| - assert( pConstraint->pGeom );
|
| -
|
| - for(i=0; i<nCoord; i++){
|
| - aCoord[i] = DCOORD(pCell->aCoord[i]);
|
| - }
|
| - return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
|
| +** 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
|
|
|
| -/*
|
| -** Cursor pCursor currently points to a cell in a non-leaf page.
|
| -** Set *pbEof to true if the sub-tree headed by the cell is filtered
|
| -** (excluded) by the constraints in the pCursor->aConstraint[]
|
| -** array, or false otherwise.
|
| -**
|
| -** Return SQLITE_OK if successful or an SQLite error code if an error
|
| -** occurs within a geometry callback.
|
| +/*
|
| +** Check the RTree node or entry given by pCellData and p against the MATCH
|
| +** constraint pConstraint.
|
| */
|
| -static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
|
| - RtreeCell cell;
|
| - int ii;
|
| - int bRes = 0;
|
| - int rc = SQLITE_OK;
|
| -
|
| - nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
|
| - for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
|
| - RtreeConstraint *p = &pCursor->aConstraint[ii];
|
| - double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
|
| - double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
|
| -
|
| - assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|
| - || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
|
| - );
|
| -
|
| - switch( p->op ){
|
| - case RTREE_LE: case RTREE_LT:
|
| - bRes = p->rValue<cell_min;
|
| - break;
|
| -
|
| - case RTREE_GE: case RTREE_GT:
|
| - bRes = p->rValue>cell_max;
|
| - break;
|
| -
|
| - case RTREE_EQ:
|
| - bRes = (p->rValue>cell_max || p->rValue<cell_min);
|
| - break;
|
| -
|
| - default: {
|
| - assert( p->op==RTREE_MATCH );
|
| - rc = testRtreeGeom(pRtree, p, &cell, &bRes);
|
| - bRes = !bRes;
|
| - break;
|
| - }
|
| +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;
|
| }
|
| }
|
| -
|
| - *pbEof = bRes;
|
| return rc;
|
| }
|
|
|
| /*
|
| -** Test if the cell that cursor pCursor currently points to
|
| -** would be filtered (excluded) by the constraints in the
|
| -** pCursor->aConstraint[] array. If so, set *pbEof to true before
|
| -** returning. If the cell is not filtered (excluded) by the constraints,
|
| -** set pbEof to zero.
|
| -**
|
| -** Return SQLITE_OK if successful or an SQLite error code if an error
|
| -** occurs within a geometry callback.
|
| -**
|
| -** This function assumes that the cell is part of a leaf node.
|
| -*/
|
| -static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
|
| - RtreeCell cell;
|
| - int ii;
|
| - *pbEof = 0;
|
| -
|
| - nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
|
| - for(ii=0; ii<pCursor->nConstraint; ii++){
|
| - RtreeConstraint *p = &pCursor->aConstraint[ii];
|
| - double coord = DCOORD(cell.aCoord[p->iCoord]);
|
| - int res;
|
| - assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|
| - || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
|
| - );
|
| - switch( p->op ){
|
| - case RTREE_LE: res = (coord<=p->rValue); break;
|
| - case RTREE_LT: res = (coord<p->rValue); break;
|
| - case RTREE_GE: res = (coord>=p->rValue); break;
|
| - case RTREE_GT: res = (coord>p->rValue); break;
|
| - case RTREE_EQ: res = (coord==p->rValue); break;
|
| - default: {
|
| - int rc;
|
| - assert( p->op==RTREE_MATCH );
|
| - rc = testRtreeGeom(pRtree, p, &cell, &res);
|
| - if( rc!=SQLITE_OK ){
|
| - return rc;
|
| - }
|
| - break;
|
| - }
|
| - }
|
| -
|
| - if( !res ){
|
| - *pbEof = 1;
|
| - return SQLITE_OK;
|
| - }
|
| - }
|
| -
|
| - return SQLITE_OK;
|
| -}
|
| -
|
| -/*
|
| -** Cursor pCursor currently points at a node that heads a sub-tree of
|
| -** height iHeight (if iHeight==0, then the node is a leaf). Descend
|
| -** to point to the left-most cell of the sub-tree that matches the
|
| -** configured constraints.
|
| -*/
|
| -static int descendToCell(
|
| - Rtree *pRtree,
|
| - RtreeCursor *pCursor,
|
| - int iHeight,
|
| - int *pEof /* OUT: Set to true if cannot descend */
|
| +** 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 */
|
| ){
|
| - int isEof;
|
| - int rc;
|
| - int ii;
|
| - RtreeNode *pChild;
|
| - sqlite3_int64 iRowid;
|
| -
|
| - RtreeNode *pSavedNode = pCursor->pNode;
|
| - int iSavedCell = pCursor->iCell;
|
| + sqlite3_rtree_dbl val; /* Coordinate value convert to a double */
|
|
|
| - assert( iHeight>=0 );
|
| + /* 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);
|
|
|
| - if( iHeight==0 ){
|
| - rc = testRtreeEntry(pRtree, pCursor, &isEof);
|
| - }else{
|
| - rc = testRtreeCell(pRtree, pCursor, &isEof);
|
| - }
|
| - if( rc!=SQLITE_OK || isEof || iHeight==0 ){
|
| - goto descend_to_cell_out;
|
| - }
|
| + 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 */
|
|
|
| - iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
|
| - rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
|
| - if( rc!=SQLITE_OK ){
|
| - goto descend_to_cell_out;
|
| + 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;
|
| +}
|
|
|
| - nodeRelease(pRtree, pCursor->pNode);
|
| - pCursor->pNode = pChild;
|
| - isEof = 1;
|
| - for(ii=0; isEof && ii<NCELL(pChild); ii++){
|
| - pCursor->iCell = ii;
|
| - rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
|
| - if( rc!=SQLITE_OK ){
|
| - goto descend_to_cell_out;
|
| - }
|
| - }
|
| +/*
|
| +** 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 */
|
|
|
| - if( isEof ){
|
| - assert( pCursor->pNode==pChild );
|
| - nodeReference(pSavedNode);
|
| - nodeRelease(pRtree, pChild);
|
| - pCursor->pNode = pSavedNode;
|
| - pCursor->iCell = iSavedCell;
|
| + 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;
|
| }
|
| -
|
| -descend_to_cell_out:
|
| - *pEof = isEof;
|
| - return rc;
|
| + *peWithin = NOT_WITHIN;
|
| }
|
|
|
| /*
|
| @@ -1056,13 +1073,14 @@ static int nodeRowidIndex(
|
| ){
|
| 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;
|
| + return SQLITE_CORRUPT_VTAB;
|
| }
|
|
|
| /*
|
| @@ -1078,48 +1096,302 @@ static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
|
| return SQLITE_OK;
|
| }
|
|
|
| -/*
|
| -** Rtree virtual table module xNext method.
|
| +/*
|
| +** 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 int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
|
| - Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
|
| - RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
|
| - int rc = SQLITE_OK;
|
| +static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
|
| + return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
|
| +}
|
|
|
| - /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
|
| - ** already at EOF. It is against the rules to call the xNext() method of
|
| - ** a cursor that has already reached EOF.
|
| - */
|
| - assert( pCsr->pNode );
|
| +/*
|
| +** 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>=0 && 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( pCsr->iStrategy==1 ){
|
| - /* This "scan" is a direct lookup by rowid. There is no next entry. */
|
| - nodeRelease(pRtree, pCsr->pNode);
|
| - pCsr->pNode = 0;
|
| +#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{
|
| - /* Move to the next entry that matches the configured constraints. */
|
| - int iHeight = 0;
|
| - while( pCsr->pNode ){
|
| - RtreeNode *pNode = pCsr->pNode;
|
| - int nCell = NCELL(pNode);
|
| - for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
|
| - int isEof;
|
| - rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
|
| - if( rc!=SQLITE_OK || !isEof ){
|
| - return rc;
|
| + 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;
|
| }
|
| }
|
| - pCsr->pNode = pNode->pParent;
|
| - rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
|
| - if( rc!=SQLITE_OK ){
|
| - return rc;
|
| + }
|
| + }
|
| +}
|
| +
|
| +
|
| +/*
|
| +** 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);
|
| }
|
| - nodeReference(pCsr->pNode);
|
| - nodeRelease(pRtree, pNode);
|
| - iHeight++;
|
| + 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;
|
| }
|
|
|
| @@ -1127,13 +1399,14 @@ static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
|
| ** Rtree virtual table module xRowid method.
|
| */
|
| static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
|
| - Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
|
| RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
|
| -
|
| - assert(pCsr->pNode);
|
| - *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
|
| -
|
| - return SQLITE_OK;
|
| + 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;
|
| }
|
|
|
| /*
|
| @@ -1142,21 +1415,28 @@ static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
|
| 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 ){
|
| - i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
|
| - sqlite3_result_int64(ctx, iRowid);
|
| + sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
|
| }else{
|
| - RtreeCoord c;
|
| - nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
|
| + 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{
|
| + }else
|
| +#endif
|
| + {
|
| assert( pRtree->eCoordType==RTREE_COORD_INT32 );
|
| sqlite3_result_int(ctx, c.i);
|
| }
|
| }
|
| -
|
| return SQLITE_OK;
|
| }
|
|
|
| @@ -1167,12 +1447,18 @@ static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
|
| ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
|
| ** to zero and return an SQLite error code.
|
| */
|
| -static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
|
| +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{
|
| @@ -1188,42 +1474,45 @@ static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
|
| ** operator.
|
| */
|
| static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
|
| - RtreeMatchArg *p;
|
| - sqlite3_rtree_geometry *pGeom;
|
| - int nBlob;
|
| + 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;
|
| + if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
|
|
|
| /* Check that the blob is roughly the right size. */
|
| nBlob = sqlite3_value_bytes(pValue);
|
| if( nBlob<(int)sizeof(RtreeMatchArg)
|
| - || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0
|
| + || ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
|
| ){
|
| return SQLITE_ERROR;
|
| }
|
|
|
| - pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
|
| - sizeof(sqlite3_rtree_geometry) + nBlob
|
| - );
|
| - if( !pGeom ) return SQLITE_NOMEM;
|
| - memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
|
| - p = (RtreeMatchArg *)&pGeom[1];
|
| + 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(p, sqlite3_value_blob(pValue), nBlob);
|
| - if( p->magic!=RTREE_GEOMETRY_MAGIC
|
| - || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double))
|
| - ){
|
| - sqlite3_free(pGeom);
|
| + memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
|
| + nExpected = (int)(sizeof(RtreeMatchArg) +
|
| + (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;
|
|
|
| - pGeom->pContext = p->pContext;
|
| - pGeom->nParam = p->nParam;
|
| - pGeom->aParam = p->aParam;
|
| -
|
| - pCons->xGeom = p->xGeom;
|
| - pCons->pGeom = pGeom;
|
| + 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;
|
| }
|
|
|
| @@ -1237,43 +1526,59 @@ static int rtreeFilter(
|
| ){
|
| 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);
|
| - pCsr->iStrategy = idxNum;
|
| + 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]);
|
| - rc = findLeafNode(pRtree, iRowid, &pLeaf);
|
| - pCsr->pNode = pLeaf;
|
| - if( pLeaf ){
|
| - assert( rc==SQLITE_OK );
|
| - rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
|
| + 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.
|
| */
|
| - if( argc>0 ){
|
| + 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);
|
| - assert( (idxStr==0 && argc==0) || (int)strlen(idxStr)==argc*2 );
|
| + 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]-'a';
|
| - if( p->op==RTREE_MATCH ){
|
| + 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.
|
| @@ -1282,42 +1587,53 @@ static int rtreeFilter(
|
| if( rc!=SQLITE_OK ){
|
| break;
|
| }
|
| + p->pInfo->nCoord = pRtree->nDim*2;
|
| + p->pInfo->anQueue = pCsr->anQueue;
|
| + p->pInfo->mxLevel = pRtree->iDepth + 1;
|
| }else{
|
| - p->rValue = sqlite3_value_double(argv[ii]);
|
| +#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 ){
|
| - pCsr->pNode = 0;
|
| - rc = nodeAcquire(pRtree, 1, 0, &pRoot);
|
| - }
|
| - if( rc==SQLITE_OK ){
|
| - int isEof = 1;
|
| - int nCell = NCELL(pRoot);
|
| - pCsr->pNode = pRoot;
|
| - for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
|
| - assert( pCsr->pNode==pRoot );
|
| - rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
|
| - if( !isEof ){
|
| - break;
|
| - }
|
| - }
|
| - if( rc==SQLITE_OK && isEof ){
|
| - assert( pCsr->pNode==pRoot );
|
| - nodeRelease(pRtree, pRoot);
|
| - pCsr->pNode = 0;
|
| - }
|
| - assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
|
| + 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):
|
| @@ -1352,13 +1668,14 @@ static int rtreeFilter(
|
| ** 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;
|
| + i64 nRow; /* Estimated rows returned by this scan */
|
|
|
| int iIdx = 0;
|
| char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
|
| memset(zIdxStr, 0, sizeof(zIdxStr));
|
| - UNUSED_PARAMETER(tab);
|
|
|
| assert( pIdxInfo->idxStr==0 );
|
| for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
|
| @@ -1378,9 +1695,11 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
|
| /* 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).
|
| + ** sqlite uses an internal cost of 0.0). It is expected to return
|
| + ** a single row.
|
| */
|
| - pIdxInfo->estimatedCost = 10.0;
|
| + pIdxInfo->estimatedCost = 30.0;
|
| + setEstimatedRows(pIdxInfo, 1);
|
| return SQLITE_OK;
|
| }
|
|
|
| @@ -1398,7 +1717,7 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
|
| break;
|
| }
|
| zIdxStr[iIdx++] = op;
|
| - zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
|
| + zIdxStr[iIdx++] = p->iColumn - 1 + '0';
|
| pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
|
| pIdxInfo->aConstraintUsage[ii].omit = 1;
|
| }
|
| @@ -1409,19 +1728,22 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
|
| if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
|
| return SQLITE_NOMEM;
|
| }
|
| - assert( iIdx>=0 );
|
| - pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
|
| +
|
| + 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 float cellArea(Rtree *pRtree, RtreeCell *p){
|
| - float area = 1.0;
|
| +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]));
|
| + area = (area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])));
|
| }
|
| return area;
|
| }
|
| @@ -1430,8 +1752,8 @@ static float cellArea(Rtree *pRtree, RtreeCell *p){
|
| ** Return the margin length of cell p. The margin length is the sum
|
| ** of the objects size in each dimension.
|
| */
|
| -static float cellMargin(Rtree *pRtree, RtreeCell *p){
|
| - float margin = 0.0;
|
| +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]));
|
| @@ -1479,8 +1801,8 @@ static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
|
| /*
|
| ** Return the amount cell p would grow by if it were unioned with pCell.
|
| */
|
| -static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
|
| - float area;
|
| +static RtreeDValue cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
|
| + RtreeDValue area;
|
| RtreeCell cell;
|
| memcpy(&cell, p, sizeof(RtreeCell));
|
| area = cellArea(pRtree, &cell);
|
| @@ -1488,64 +1810,32 @@ static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
|
| return (cellArea(pRtree, &cell)-area);
|
| }
|
|
|
| -#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
|
| -static float cellOverlap(
|
| +static RtreeDValue cellOverlap(
|
| Rtree *pRtree,
|
| RtreeCell *p,
|
| RtreeCell *aCell,
|
| - int nCell,
|
| - int iExclude
|
| + int nCell
|
| ){
|
| int ii;
|
| - float overlap = 0.0;
|
| + RtreeDValue overlap = RTREE_ZERO;
|
| for(ii=0; ii<nCell; ii++){
|
| -#if VARIANT_RSTARTREE_CHOOSESUBTREE
|
| - if( ii!=iExclude )
|
| -#else
|
| - assert( iExclude==-1 );
|
| - UNUSED_PARAMETER(iExclude);
|
| -#endif
|
| - {
|
| - int jj;
|
| - float o = 1.0;
|
| - for(jj=0; jj<(pRtree->nDim*2); jj+=2){
|
| - double x1;
|
| - double x2;
|
| -
|
| - x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
|
| - x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
|
| -
|
| - if( x2<x1 ){
|
| - o = 0.0;
|
| - break;
|
| - }else{
|
| - o = o * (x2-x1);
|
| - }
|
| + 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;
|
| }
|
| + overlap += o;
|
| }
|
| return overlap;
|
| }
|
| -#endif
|
| -
|
| -#if VARIANT_RSTARTREE_CHOOSESUBTREE
|
| -static float cellOverlapEnlargement(
|
| - Rtree *pRtree,
|
| - RtreeCell *p,
|
| - RtreeCell *pInsert,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - int iExclude
|
| -){
|
| - float before;
|
| - float after;
|
| - before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
|
| - cellUnion(pRtree, p, pInsert);
|
| - after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
|
| - return after-before;
|
| -}
|
| -#endif
|
|
|
|
|
| /*
|
| @@ -1565,65 +1855,32 @@ static int ChooseLeaf(
|
|
|
| for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
|
| int iCell;
|
| - sqlite3_int64 iBest;
|
| + sqlite3_int64 iBest = 0;
|
|
|
| - float fMinGrowth;
|
| - float fMinArea;
|
| - float fMinOverlap;
|
| + RtreeDValue fMinGrowth = RTREE_ZERO;
|
| + RtreeDValue fMinArea = RTREE_ZERO;
|
|
|
| int nCell = NCELL(pNode);
|
| RtreeCell cell;
|
| RtreeNode *pChild;
|
|
|
| - RtreeCell *aCell = 0;
|
| -
|
| -#if VARIANT_RSTARTREE_CHOOSESUBTREE
|
| - if( ii==(pRtree->iDepth-1) ){
|
| - int jj;
|
| - aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
|
| - if( !aCell ){
|
| - rc = SQLITE_NOMEM;
|
| - nodeRelease(pRtree, pNode);
|
| - pNode = 0;
|
| - continue;
|
| - }
|
| - for(jj=0; jj<nCell; jj++){
|
| - nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
|
| - }
|
| - }
|
| -#endif
|
| -
|
| + 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;
|
| - float growth;
|
| - float area;
|
| - float overlap = 0.0;
|
| + RtreeDValue growth;
|
| + RtreeDValue area;
|
| nodeGetCell(pRtree, pNode, iCell, &cell);
|
| growth = cellGrowth(pRtree, &cell, pCell);
|
| area = cellArea(pRtree, &cell);
|
| -
|
| -#if VARIANT_RSTARTREE_CHOOSESUBTREE
|
| - if( ii==(pRtree->iDepth-1) ){
|
| - overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
|
| - }
|
| - if( (iCell==0)
|
| - || (overlap<fMinOverlap)
|
| - || (overlap==fMinOverlap && growth<fMinGrowth)
|
| - || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
|
| - ){
|
| - bBest = 1;
|
| - }
|
| -#else
|
| if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
|
| bBest = 1;
|
| }
|
| -#endif
|
| if( bBest ){
|
| - fMinOverlap = overlap;
|
| fMinGrowth = growth;
|
| fMinArea = area;
|
| iBest = cell.iRowid;
|
| @@ -1657,7 +1914,7 @@ static int AdjustTree(
|
| int iCell;
|
|
|
| if( nodeParentIndex(pRtree, p, &iCell) ){
|
| - return SQLITE_CORRUPT;
|
| + return SQLITE_CORRUPT_VTAB;
|
| }
|
|
|
| nodeGetCell(pRtree, pParent, iCell, &cell);
|
| @@ -1693,155 +1950,6 @@ static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
|
|
|
| static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
|
|
|
| -#if VARIANT_GUTTMAN_LINEAR_SPLIT
|
| -/*
|
| -** Implementation of the linear variant of the PickNext() function from
|
| -** Guttman[84].
|
| -*/
|
| -static RtreeCell *LinearPickNext(
|
| - Rtree *pRtree,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - RtreeCell *pLeftBox,
|
| - RtreeCell *pRightBox,
|
| - int *aiUsed
|
| -){
|
| - int ii;
|
| - for(ii=0; aiUsed[ii]; ii++);
|
| - aiUsed[ii] = 1;
|
| - return &aCell[ii];
|
| -}
|
| -
|
| -/*
|
| -** Implementation of the linear variant of the PickSeeds() function from
|
| -** Guttman[84].
|
| -*/
|
| -static void LinearPickSeeds(
|
| - Rtree *pRtree,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - int *piLeftSeed,
|
| - int *piRightSeed
|
| -){
|
| - int i;
|
| - int iLeftSeed = 0;
|
| - int iRightSeed = 1;
|
| - float maxNormalInnerWidth = 0.0;
|
| -
|
| - /* Pick two "seed" cells from the array of cells. The algorithm used
|
| - ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
|
| - ** indices of the two seed cells in the array are stored in local
|
| - ** variables iLeftSeek and iRightSeed.
|
| - */
|
| - for(i=0; i<pRtree->nDim; i++){
|
| - float x1 = DCOORD(aCell[0].aCoord[i*2]);
|
| - float x2 = DCOORD(aCell[0].aCoord[i*2+1]);
|
| - float x3 = x1;
|
| - float x4 = x2;
|
| - int jj;
|
| -
|
| - int iCellLeft = 0;
|
| - int iCellRight = 0;
|
| -
|
| - for(jj=1; jj<nCell; jj++){
|
| - float left = DCOORD(aCell[jj].aCoord[i*2]);
|
| - float right = DCOORD(aCell[jj].aCoord[i*2+1]);
|
| -
|
| - if( left<x1 ) x1 = left;
|
| - if( right>x4 ) x4 = right;
|
| - if( left>x3 ){
|
| - x3 = left;
|
| - iCellRight = jj;
|
| - }
|
| - if( right<x2 ){
|
| - x2 = right;
|
| - iCellLeft = jj;
|
| - }
|
| - }
|
| -
|
| - if( x4!=x1 ){
|
| - float normalwidth = (x3 - x2) / (x4 - x1);
|
| - if( normalwidth>maxNormalInnerWidth ){
|
| - iLeftSeed = iCellLeft;
|
| - iRightSeed = iCellRight;
|
| - }
|
| - }
|
| - }
|
| -
|
| - *piLeftSeed = iLeftSeed;
|
| - *piRightSeed = iRightSeed;
|
| -}
|
| -#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
|
| -
|
| -#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
|
| -/*
|
| -** Implementation of the quadratic variant of the PickNext() function from
|
| -** Guttman[84].
|
| -*/
|
| -static RtreeCell *QuadraticPickNext(
|
| - Rtree *pRtree,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - RtreeCell *pLeftBox,
|
| - RtreeCell *pRightBox,
|
| - int *aiUsed
|
| -){
|
| - #define FABS(a) ((a)<0.0?-1.0*(a):(a))
|
| -
|
| - int iSelect = -1;
|
| - float fDiff;
|
| - int ii;
|
| - for(ii=0; ii<nCell; ii++){
|
| - if( aiUsed[ii]==0 ){
|
| - float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
|
| - float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
|
| - float diff = FABS(right-left);
|
| - if( iSelect<0 || diff>fDiff ){
|
| - fDiff = diff;
|
| - iSelect = ii;
|
| - }
|
| - }
|
| - }
|
| - aiUsed[iSelect] = 1;
|
| - return &aCell[iSelect];
|
| -}
|
| -
|
| -/*
|
| -** Implementation of the quadratic variant of the PickSeeds() function from
|
| -** Guttman[84].
|
| -*/
|
| -static void QuadraticPickSeeds(
|
| - Rtree *pRtree,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - int *piLeftSeed,
|
| - int *piRightSeed
|
| -){
|
| - int ii;
|
| - int jj;
|
| -
|
| - int iLeftSeed = 0;
|
| - int iRightSeed = 1;
|
| - float fWaste = 0.0;
|
| -
|
| - for(ii=0; ii<nCell; ii++){
|
| - for(jj=ii+1; jj<nCell; jj++){
|
| - float right = cellArea(pRtree, &aCell[jj]);
|
| - float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
|
| - float waste = growth - right;
|
| -
|
| - if( waste>fWaste ){
|
| - iLeftSeed = ii;
|
| - iRightSeed = jj;
|
| - fWaste = waste;
|
| - }
|
| - }
|
| - }
|
| -
|
| - *piLeftSeed = iLeftSeed;
|
| - *piRightSeed = iRightSeed;
|
| -}
|
| -#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
|
|
|
| /*
|
| ** Arguments aIdx, aDistance and aSpare all point to arrays of size
|
| @@ -1863,7 +1971,7 @@ static void QuadraticPickSeeds(
|
| static void SortByDistance(
|
| int *aIdx,
|
| int nIdx,
|
| - float *aDistance,
|
| + RtreeDValue *aDistance,
|
| int *aSpare
|
| ){
|
| if( nIdx>1 ){
|
| @@ -1889,8 +1997,8 @@ static void SortByDistance(
|
| aIdx[iLeft+iRight] = aLeft[iLeft];
|
| iLeft++;
|
| }else{
|
| - float fLeft = aDistance[aLeft[iLeft]];
|
| - float fRight = aDistance[aRight[iRight]];
|
| + RtreeDValue fLeft = aDistance[aLeft[iLeft]];
|
| + RtreeDValue fRight = aDistance[aRight[iRight]];
|
| if( fLeft<fRight ){
|
| aIdx[iLeft+iRight] = aLeft[iLeft];
|
| iLeft++;
|
| @@ -1906,8 +2014,8 @@ static void SortByDistance(
|
| {
|
| int jj;
|
| for(jj=1; jj<nIdx; jj++){
|
| - float left = aDistance[aIdx[jj-1]];
|
| - float right = aDistance[aIdx[jj]];
|
| + RtreeDValue left = aDistance[aIdx[jj-1]];
|
| + RtreeDValue right = aDistance[aIdx[jj]];
|
| assert( left<=right );
|
| }
|
| }
|
| @@ -1950,10 +2058,10 @@ static void SortByDimension(
|
| memcpy(aSpare, aLeft, sizeof(int)*nLeft);
|
| aLeft = aSpare;
|
| while( iLeft<nLeft || iRight<nRight ){
|
| - double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
|
| - double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
|
| - double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
|
| - double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
|
| + 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)
|
| @@ -1971,10 +2079,10 @@ static void SortByDimension(
|
| {
|
| int jj;
|
| for(jj=1; jj<nIdx; jj++){
|
| - float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
|
| - float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
|
| - float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
|
| - float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
|
| + 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) );
|
| }
|
| }
|
| @@ -1982,7 +2090,6 @@ static void SortByDimension(
|
| }
|
| }
|
|
|
| -#if VARIANT_RSTARTREE_SPLIT
|
| /*
|
| ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
|
| */
|
| @@ -1999,9 +2106,9 @@ static int splitNodeStartree(
|
| int *aSpare;
|
| int ii;
|
|
|
| - int iBestDim;
|
| - int iBestSplit;
|
| - float fBestMargin;
|
| + int iBestDim = 0;
|
| + int iBestSplit = 0;
|
| + RtreeDValue fBestMargin = RTREE_ZERO;
|
|
|
| int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
|
|
|
| @@ -2022,10 +2129,10 @@ static int splitNodeStartree(
|
| }
|
|
|
| for(ii=0; ii<pRtree->nDim; ii++){
|
| - float margin = 0.0;
|
| - float fBestOverlap;
|
| - float fBestArea;
|
| - int iBestLeft;
|
| + RtreeDValue margin = RTREE_ZERO;
|
| + RtreeDValue fBestOverlap = RTREE_ZERO;
|
| + RtreeDValue fBestArea = RTREE_ZERO;
|
| + int iBestLeft = 0;
|
| int nLeft;
|
|
|
| for(
|
| @@ -2036,8 +2143,8 @@ static int splitNodeStartree(
|
| RtreeCell left;
|
| RtreeCell right;
|
| int kk;
|
| - float overlap;
|
| - float area;
|
| + RtreeDValue overlap;
|
| + RtreeDValue area;
|
|
|
| memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
|
| memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
|
| @@ -2050,7 +2157,7 @@ static int splitNodeStartree(
|
| }
|
| margin += cellMargin(pRtree, &left);
|
| margin += cellMargin(pRtree, &right);
|
| - overlap = cellOverlap(pRtree, &left, &right, 1, -1);
|
| + overlap = cellOverlap(pRtree, &left, &right, 1);
|
| area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
|
| if( (nLeft==RTREE_MINCELLS(pRtree))
|
| || (overlap<fBestOverlap)
|
| @@ -2082,63 +2189,7 @@ static int splitNodeStartree(
|
| sqlite3_free(aaSorted);
|
| return SQLITE_OK;
|
| }
|
| -#endif
|
| -
|
| -#if VARIANT_GUTTMAN_SPLIT
|
| -/*
|
| -** Implementation of the regular R-tree SplitNode from Guttman[1984].
|
| -*/
|
| -static int splitNodeGuttman(
|
| - Rtree *pRtree,
|
| - RtreeCell *aCell,
|
| - int nCell,
|
| - RtreeNode *pLeft,
|
| - RtreeNode *pRight,
|
| - RtreeCell *pBboxLeft,
|
| - RtreeCell *pBboxRight
|
| -){
|
| - int iLeftSeed = 0;
|
| - int iRightSeed = 1;
|
| - int *aiUsed;
|
| - int i;
|
| -
|
| - aiUsed = sqlite3_malloc(sizeof(int)*nCell);
|
| - if( !aiUsed ){
|
| - return SQLITE_NOMEM;
|
| - }
|
| - memset(aiUsed, 0, sizeof(int)*nCell);
|
| -
|
| - PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
|
| -
|
| - memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
|
| - memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
|
| - nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
|
| - nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
|
| - aiUsed[iLeftSeed] = 1;
|
| - aiUsed[iRightSeed] = 1;
|
| -
|
| - for(i=nCell-2; i>0; i--){
|
| - RtreeCell *pNext;
|
| - pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
|
| - float diff =
|
| - cellGrowth(pRtree, pBboxLeft, pNext) -
|
| - cellGrowth(pRtree, pBboxRight, pNext)
|
| - ;
|
| - if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
|
| - || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
|
| - ){
|
| - nodeInsertCell(pRtree, pRight, pNext);
|
| - cellUnion(pRtree, pBboxRight, pNext);
|
| - }else{
|
| - nodeInsertCell(pRtree, pLeft, pNext);
|
| - cellUnion(pRtree, pBboxLeft, pNext);
|
| - }
|
| - }
|
|
|
| - sqlite3_free(aiUsed);
|
| - return SQLITE_OK;
|
| -}
|
| -#endif
|
|
|
| static int updateMapping(
|
| Rtree *pRtree,
|
| @@ -2216,7 +2267,8 @@ static int SplitNode(
|
| memset(pLeft->zData, 0, pRtree->iNodeSize);
|
| memset(pRight->zData, 0, pRtree->iNodeSize);
|
|
|
| - rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
|
| + rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
|
| + &leftbbox, &rightbbox);
|
| if( rc!=SQLITE_OK ){
|
| goto splitnode_out;
|
| }
|
| @@ -2329,7 +2381,7 @@ static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
|
| }
|
| rc = sqlite3_reset(pRtree->pReadParent);
|
| if( rc==SQLITE_OK ) rc = rc2;
|
| - if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT;
|
| + if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT_VTAB;
|
| pChild = pChild->pParent;
|
| }
|
| return rc;
|
| @@ -2340,7 +2392,7 @@ static int deleteCell(Rtree *, RtreeNode *, int, int);
|
| static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
|
| int rc;
|
| int rc2;
|
| - RtreeNode *pParent;
|
| + RtreeNode *pParent = 0;
|
| int iCell;
|
|
|
| assert( pNode->nRef==1 );
|
| @@ -2453,32 +2505,34 @@ static int Reinsert(
|
| int *aOrder;
|
| int *aSpare;
|
| RtreeCell *aCell;
|
| - float *aDistance;
|
| + RtreeDValue *aDistance;
|
| int nCell;
|
| - float aCenterCoord[RTREE_MAX_DIMENSIONS];
|
| + RtreeDValue aCenterCoord[RTREE_MAX_DIMENSIONS];
|
| int iDim;
|
| int ii;
|
| int rc = SQLITE_OK;
|
| + int n;
|
|
|
| - memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
|
| + 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(nCell * (
|
| - sizeof(RtreeCell) + /* aCell array */
|
| - sizeof(int) + /* aOrder array */
|
| - sizeof(int) + /* aSpare array */
|
| - sizeof(float) /* aDistance array */
|
| + 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[nCell];
|
| - aSpare = (int *)&aOrder[nCell];
|
| - aDistance = (float *)&aSpare[nCell];
|
| + aOrder = (int *)&aCell[n];
|
| + aSpare = (int *)&aOrder[n];
|
| + aDistance = (RtreeDValue *)&aSpare[n];
|
|
|
| for(ii=0; ii<nCell; ii++){
|
| if( ii==(nCell-1) ){
|
| @@ -2493,14 +2547,14 @@ static int Reinsert(
|
| }
|
| }
|
| for(iDim=0; iDim<pRtree->nDim; iDim++){
|
| - aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
|
| + aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2));
|
| }
|
|
|
| for(ii=0; ii<nCell; ii++){
|
| - aDistance[ii] = 0.0;
|
| + aDistance[ii] = RTREE_ZERO;
|
| for(iDim=0; iDim<pRtree->nDim; iDim++){
|
| - float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) -
|
| - DCOORD(aCell[ii].aCoord[iDim*2]);
|
| + RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) -
|
| + DCOORD(aCell[ii].aCoord[iDim*2]));
|
| aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
|
| }
|
| }
|
| @@ -2563,16 +2617,12 @@ static int rtreeInsertCell(
|
| }
|
| }
|
| if( nodeInsertCell(pRtree, pNode, pCell) ){
|
| -#if VARIANT_RSTARTREE_REINSERT
|
| if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
|
| rc = SplitNode(pRtree, pNode, pCell, iHeight);
|
| }else{
|
| pRtree->iReinsertHeight = iHeight;
|
| rc = Reinsert(pRtree, pNode, pCell, iHeight);
|
| }
|
| -#else
|
| - rc = SplitNode(pRtree, pNode, pCell, iHeight);
|
| -#endif
|
| }else{
|
| rc = AdjustTree(pRtree, pNode, pCell);
|
| if( rc==SQLITE_OK ){
|
| @@ -2599,10 +2649,10 @@ static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
|
| /* Find a node to store this cell in. pNode->iNode currently contains
|
| ** the height of the sub-tree headed by the cell.
|
| */
|
| - rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
|
| + rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert);
|
| if( rc==SQLITE_OK ){
|
| int rc2;
|
| - rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);
|
| + rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode);
|
| rc2 = nodeRelease(pRtree, pInsert);
|
| if( rc==SQLITE_OK ){
|
| rc = rc2;
|
| @@ -2626,126 +2676,165 @@ static int newRowid(Rtree *pRtree, i64 *piRowid){
|
| }
|
|
|
| /*
|
| -** The xUpdate method for rtree module virtual tables.
|
| +** Remove the entry with rowid=iDelete from the r-tree structure.
|
| */
|
| -static int rtreeUpdate(
|
| - sqlite3_vtab *pVtab,
|
| - int nData,
|
| - sqlite3_value **azData,
|
| - sqlite_int64 *pRowid
|
| -){
|
| - Rtree *pRtree = (Rtree *)pVtab;
|
| - int rc = SQLITE_OK;
|
| +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 */
|
|
|
| - rtreeReference(pRtree);
|
|
|
| - assert(nData>=1);
|
| + /* Obtain a reference to the root node to initialize Rtree.iDepth */
|
| + rc = nodeAcquire(pRtree, 1, 0, &pRoot);
|
|
|
| - /* 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.
|
| + /* Obtain a reference to the leaf node that contains the entry
|
| + ** about to be deleted.
|
| */
|
| - if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
|
| - i64 iDelete; /* The rowid to delete */
|
| - RtreeNode *pLeaf; /* Leaf node containing record iDelete */
|
| - int iCell; /* Index of iDelete cell in pLeaf */
|
| - RtreeNode *pRoot;
|
| -
|
| - /* Obtain a reference to the root node to initialise Rtree.iDepth */
|
| - rc = nodeAcquire(pRtree, 1, 0, &pRoot);
|
| + if( rc==SQLITE_OK ){
|
| + rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
|
| + }
|
|
|
| - /* Obtain a reference to the leaf node that contains the entry
|
| - ** about to be deleted.
|
| - */
|
| + /* 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 ){
|
| - iDelete = sqlite3_value_int64(azData[0]);
|
| - rc = findLeafNode(pRtree, iDelete, &pLeaf);
|
| + rc = deleteCell(pRtree, pLeaf, iCell, 0);
|
| }
|
| -
|
| - /* Delete the cell in question from the leaf node. */
|
| + rc2 = nodeRelease(pRtree, pLeaf);
|
| 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;
|
| - }
|
| + rc = rc2;
|
| }
|
| + }
|
|
|
| - /* Delete the corresponding entry in the <rtree>_rowid table. */
|
| + /* 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 ){
|
| - 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;
|
| - }
|
| + rc = removeNode(pRtree, pChild, pRtree->iDepth-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);
|
| + rc2 = nodeRelease(pRtree, pChild);
|
| + if( rc==SQLITE_OK ) rc = rc2;
|
| + if( rc==SQLITE_OK ){
|
| + pRtree->iDepth--;
|
| + writeInt16(pRoot->zData, pRtree->iDepth);
|
| + pRoot->isDirty = 1;
|
| }
|
| + }
|
|
|
| - /* Release the reference to the root node. */
|
| + /* 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 = nodeRelease(pRtree, pRoot);
|
| - }else{
|
| - nodeRelease(pRtree, pRoot);
|
| + rc = reinsertNodeContent(pRtree, pLeaf);
|
| }
|
| + pRtree->pDeleted = pLeaf->pNext;
|
| + sqlite3_free(pLeaf);
|
| }
|
|
|
| - /* 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.
|
| + /* 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);
|
| +
|
| + /* 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( rc==SQLITE_OK && nData>1 ){
|
| - /* Insert a new record into the r-tree */
|
| - RtreeCell cell;
|
| + if( nData>1 ){
|
| int ii;
|
| - RtreeNode *pLeaf;
|
|
|
| /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
|
| assert( nData==(pRtree->nDim*2 + 3) );
|
| +#ifndef SQLITE_RTREE_INT_ONLY
|
| if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
|
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){
|
| - cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
|
| - cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
|
| + 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{
|
| + }else
|
| +#endif
|
| + {
|
| for(ii=0; ii<(pRtree->nDim*2); ii+=2){
|
| cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
|
| cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
|
| @@ -2756,18 +2845,49 @@ static int rtreeUpdate(
|
| }
|
| }
|
|
|
| - /* Figure out the rowid of the new row. */
|
| - if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
|
| - rc = newRowid(pRtree, &cell.iRowid);
|
| - }else{
|
| + /* 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]);
|
| - sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
|
| - if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
|
| - sqlite3_reset(pRtree->pReadRowid);
|
| - rc = SQLITE_CONSTRAINT;
|
| - goto constraint;
|
| + 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;
|
| + }
|
| + }
|
| }
|
| - rc = sqlite3_reset(pRtree->pReadRowid);
|
| + 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;
|
|
|
| @@ -2811,8 +2931,45 @@ static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
|
| 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 */
|
| + 0, /* iVersion */
|
| rtreeCreate, /* xCreate - create a table */
|
| rtreeConnect, /* xConnect - connect to an existing table */
|
| rtreeBestIndex, /* xBestIndex - Determine search strategy */
|
| @@ -2831,7 +2988,10 @@ static sqlite3_module rtreeModule = {
|
| 0, /* xCommit - commit transaction */
|
| 0, /* xRollback - rollback transaction */
|
| 0, /* xFindFunction - function overloading */
|
| - rtreeRename /* xRename - rename the table */
|
| + rtreeRename, /* xRename - rename the table */
|
| + 0, /* xSavepoint */
|
| + 0, /* xRelease */
|
| + 0 /* xRollbackTo */
|
| };
|
|
|
| static int rtreeSqlInit(
|
| @@ -2869,7 +3029,8 @@ static int rtreeSqlInit(
|
| 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);"
|
| +"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
|
| );
|
| @@ -2893,6 +3054,7 @@ static int rtreeSqlInit(
|
| 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 ){
|
| @@ -2946,12 +3108,13 @@ static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){
|
| static int getNodeSize(
|
| sqlite3 *db, /* Database handle */
|
| Rtree *pRtree, /* Rtree handle */
|
| - int isCreate /* True for xCreate, false for xConnect */
|
| + int isCreate, /* True for xCreate, false for xConnect */
|
| + char **pzErr /* OUT: Error message, if any */
|
| ){
|
| int rc;
|
| char *zSql;
|
| if( isCreate ){
|
| - int iPageSize;
|
| + int iPageSize = 0;
|
| zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
|
| rc = getIntFromStmt(db, zSql, &iPageSize);
|
| if( rc==SQLITE_OK ){
|
| @@ -2959,6 +3122,8 @@ static int getNodeSize(
|
| 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(
|
| @@ -2966,6 +3131,9 @@ static int getNodeSize(
|
| pRtree->zDb, pRtree->zName
|
| );
|
| rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
|
| + if( rc!=SQLITE_OK ){
|
| + *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
|
| + }
|
| }
|
|
|
| sqlite3_free(zSql);
|
| @@ -3008,9 +3176,11 @@ static int rtreeInit(
|
| return SQLITE_ERROR;
|
| }
|
|
|
| + sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
|
| +
|
| /* Allocate the sqlite3_vtab structure */
|
| - nDb = strlen(argv[1]);
|
| - nName = strlen(argv[2]);
|
| + nDb = (int)strlen(argv[1]);
|
| + nName = (int)strlen(argv[2]);
|
| pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
|
| if( !pRtree ){
|
| return SQLITE_NOMEM;
|
| @@ -3027,7 +3197,7 @@ static int rtreeInit(
|
| memcpy(pRtree->zName, argv[2], nName);
|
|
|
| /* Figure out the node size to use. */
|
| - rc = getNodeSize(db, pRtree, isCreate);
|
| + rc = getNodeSize(db, pRtree, isCreate, pzErr);
|
|
|
| /* Create/Connect to the underlying relational database schema. If
|
| ** that is successful, call sqlite3_declare_vtab() to configure
|
| @@ -3062,6 +3232,8 @@ static int rtreeInit(
|
| if( rc==SQLITE_OK ){
|
| *ppVtab = (sqlite3_vtab *)pRtree;
|
| }else{
|
| + assert( *ppVtab==0 );
|
| + assert( pRtree->nBusy==1 );
|
| rtreeRelease(pRtree);
|
| }
|
| return rc;
|
| @@ -3072,10 +3244,10 @@ static int rtreeInit(
|
| ** 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, a blob of data containing
|
| -** an r-tree node, and the number of dimensions the r-tree indexes.
|
| -** For a two-dimensional r-tree structure called "rt", to deserialize
|
| -** all nodes, a statement like:
|
| +** 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;
|
| **
|
| @@ -3105,10 +3277,16 @@ static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
|
|
|
| nodeGetCell(&tree, &node, ii, &cell);
|
| sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
|
| - nCell = strlen(zCell);
|
| + nCell = (int)strlen(zCell);
|
| for(jj=0; jj<tree.nDim*2; jj++){
|
| - sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
|
| - nCell = strlen(zCell);
|
| +#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 ){
|
| @@ -3123,6 +3301,15 @@ static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
|
| 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
|
| @@ -3149,7 +3336,11 @@ int sqlite3RtreeInit(sqlite3 *db){
|
| 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 ){
|
| @@ -3161,42 +3352,54 @@ int sqlite3RtreeInit(sqlite3 *db){
|
| }
|
|
|
| /*
|
| -** A version of sqlite3_free() that can be used as a callback. This is used
|
| -** in two places - as the destructor for the blob value returned by the
|
| -** invocation of a geometry function, and as the destructor for the geometry
|
| -** functions themselves.
|
| +** 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 doSqlite3Free(void *p){
|
| +static void rtreeFreeCallback(void *p){
|
| + RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
|
| + if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
|
| sqlite3_free(p);
|
| }
|
|
|
| /*
|
| -** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
|
| -** scalar user function. This C function is the callback used for all such
|
| -** registered SQL functions.
|
| +** Each call to sqlite3_rtree_geometry_callback() or
|
| +** sqlite3_rtree_query_callback() creates an ordinary SQLite
|
| +** scalar function that is implemented by this routine.
|
| **
|
| -** The scalar user functions return a blob that is interpreted by r-tree
|
| -** table MATCH operators.
|
| +** 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;
|
|
|
| - nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
|
| + nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue);
|
| pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
|
| if( !pBlob ){
|
| sqlite3_result_error_nomem(ctx);
|
| }else{
|
| int i;
|
| pBlob->magic = RTREE_GEOMETRY_MAGIC;
|
| - pBlob->xGeom = pGeomCtx->xGeom;
|
| - pBlob->pContext = pGeomCtx->pContext;
|
| + pBlob->cb = pGeomCtx[0];
|
| pBlob->nParam = nArg;
|
| for(i=0; i<nArg; i++){
|
| +#ifdef SQLITE_RTREE_INT_ONLY
|
| + pBlob->aParam[i] = sqlite3_value_int64(aArg[i]);
|
| +#else
|
| pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
|
| +#endif
|
| }
|
| - sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
|
| + sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free);
|
| }
|
| }
|
|
|
| @@ -3204,10 +3407,10 @@ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
|
| ** Register a new geometry function for use with the r-tree MATCH operator.
|
| */
|
| int sqlite3_rtree_geometry_callback(
|
| - sqlite3 *db,
|
| - const char *zGeom,
|
| - int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
|
| - void *pContext
|
| + 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 */
|
|
|
| @@ -3215,17 +3418,44 @@ int sqlite3_rtree_geometry_callback(
|
| pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
|
| if( !pGeomCtx ) return SQLITE_NOMEM;
|
| pGeomCtx->xGeom = xGeom;
|
| + pGeomCtx->xQueryFunc = 0;
|
| + pGeomCtx->xDestructor = 0;
|
| pGeomCtx->pContext = pContext;
|
| -
|
| - /* Create the new user-function. Register a destructor function to delete
|
| - ** the context object when it is no longer required. */
|
| return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY,
|
| - (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
|
| + (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
|
| -int sqlite3_extension_init(
|
| +#ifdef _WIN32
|
| +__declspec(dllexport)
|
| +#endif
|
| +int sqlite3_rtree_init(
|
| sqlite3 *db,
|
| char **pzErrMsg,
|
| const sqlite3_api_routines *pApi
|
|
|
Chromium Code Reviews
Issue 901033002:
Import SQLite 3.8.7.4. (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master