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 |