4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
11 *************************************************************************
12 ** This file contains code for implementations of the r-tree and r*-tree
13 ** algorithms packaged as an SQLite virtual table module.
17 ** Database Format of R-Tree Tables
18 ** --------------------------------
20 ** The data structure for a single virtual r-tree table is stored in three
21 ** native SQLite tables declared as follows. In each case, the '%' character
22 ** in the table name is replaced with the user-supplied name of the r-tree
25 ** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
26 ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
27 ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
29 ** The data for each node of the r-tree structure is stored in the %_node
30 ** table. For each node that is not the root node of the r-tree, there is
31 ** an entry in the %_parent table associating the node with its parent.
32 ** And for each row of data in the table, there is an entry in the %_rowid
33 ** table that maps from the entries rowid to the id of the node that it
36 ** The root node of an r-tree always exists, even if the r-tree table is
37 ** empty. The nodeno of the root node is always 1. All other nodes in the
38 ** table must be the same size as the root node. The content of each node
39 ** is formatted as follows:
41 ** 1. If the node is the root node (node 1), then the first 2 bytes
42 ** of the node contain the tree depth as a big-endian integer.
43 ** For non-root nodes, the first 2 bytes are left unused.
45 ** 2. The next 2 bytes contain the number of entries currently
46 ** stored in the node.
48 ** 3. The remainder of the node contains the node entries. Each entry
49 ** consists of a single 8-byte integer followed by an even number
50 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
51 ** of a record. For internal nodes it is the node number of a
55 #if !defined(SQLITE_CORE) \
56 || (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE))
59 #include "sqlite3ext.h"
60 SQLITE_EXTENSION_INIT1
69 #ifndef SQLITE_AMALGAMATION
70 #include "sqlite3rtree.h"
71 typedef sqlite3_int64 i64
;
72 typedef sqlite3_uint64 u64
;
73 typedef unsigned char u8
;
74 typedef unsigned short u16
;
75 typedef unsigned int u32
;
78 /* The following macro is used to suppress compiler warnings.
80 #ifndef UNUSED_PARAMETER
81 # define UNUSED_PARAMETER(x) (void)(x)
84 typedef struct Rtree Rtree
;
85 typedef struct RtreeCursor RtreeCursor
;
86 typedef struct RtreeNode RtreeNode
;
87 typedef struct RtreeCell RtreeCell
;
88 typedef struct RtreeConstraint RtreeConstraint
;
89 typedef struct RtreeMatchArg RtreeMatchArg
;
90 typedef struct RtreeGeomCallback RtreeGeomCallback
;
91 typedef union RtreeCoord RtreeCoord
;
92 typedef struct RtreeSearchPoint RtreeSearchPoint
;
94 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
95 #define RTREE_MAX_DIMENSIONS 5
97 /* Size of hash table Rtree.aHash. This hash table is not expected to
98 ** ever contain very many entries, so a fixed number of buckets is
103 /* The xBestIndex method of this virtual table requires an estimate of
104 ** the number of rows in the virtual table to calculate the costs of
105 ** various strategies. If possible, this estimate is loaded from the
106 ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
107 ** Otherwise, if no sqlite_stat1 entry is available, use
108 ** RTREE_DEFAULT_ROWEST.
110 #define RTREE_DEFAULT_ROWEST 1048576
111 #define RTREE_MIN_ROWEST 100
114 ** An rtree virtual-table object.
117 sqlite3_vtab base
; /* Base class. Must be first */
118 sqlite3
*db
; /* Host database connection */
119 int iNodeSize
; /* Size in bytes of each node in the node table */
120 u8 nDim
; /* Number of dimensions */
121 u8 nDim2
; /* Twice the number of dimensions */
122 u8 eCoordType
; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
123 u8 nBytesPerCell
; /* Bytes consumed per cell */
124 u8 inWrTrans
; /* True if inside write transaction */
125 u8 nAux
; /* # of auxiliary columns in %_rowid */
126 int iDepth
; /* Current depth of the r-tree structure */
127 char *zDb
; /* Name of database containing r-tree table */
128 char *zName
; /* Name of r-tree table */
129 u32 nBusy
; /* Current number of users of this structure */
130 i64 nRowEst
; /* Estimated number of rows in this table */
131 u32 nCursor
; /* Number of open cursors */
132 char *zReadAuxSql
; /* SQL for statement to read aux data */
134 /* List of nodes removed during a CondenseTree operation. List is
135 ** linked together via the pointer normally used for hash chains -
136 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
137 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
140 int iReinsertHeight
; /* Height of sub-trees Reinsert() has run on */
142 /* Blob I/O on xxx_node */
143 sqlite3_blob
*pNodeBlob
;
145 /* Statements to read/write/delete a record from xxx_node */
146 sqlite3_stmt
*pWriteNode
;
147 sqlite3_stmt
*pDeleteNode
;
149 /* Statements to read/write/delete a record from xxx_rowid */
150 sqlite3_stmt
*pReadRowid
;
151 sqlite3_stmt
*pWriteRowid
;
152 sqlite3_stmt
*pDeleteRowid
;
154 /* Statements to read/write/delete a record from xxx_parent */
155 sqlite3_stmt
*pReadParent
;
156 sqlite3_stmt
*pWriteParent
;
157 sqlite3_stmt
*pDeleteParent
;
159 /* Statement for writing to the "aux:" fields, if there are any */
160 sqlite3_stmt
*pWriteAux
;
162 RtreeNode
*aHash
[HASHSIZE
]; /* Hash table of in-memory nodes. */
165 /* Possible values for Rtree.eCoordType: */
166 #define RTREE_COORD_REAL32 0
167 #define RTREE_COORD_INT32 1
170 ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
171 ** only deal with integer coordinates. No floating point operations
174 #ifdef SQLITE_RTREE_INT_ONLY
175 typedef sqlite3_int64 RtreeDValue
; /* High accuracy coordinate */
176 typedef int RtreeValue
; /* Low accuracy coordinate */
177 # define RTREE_ZERO 0
179 typedef double RtreeDValue
; /* High accuracy coordinate */
180 typedef float RtreeValue
; /* Low accuracy coordinate */
181 # define RTREE_ZERO 0.0
185 ** When doing a search of an r-tree, instances of the following structure
186 ** record intermediate results from the tree walk.
188 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
189 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
190 ** the id is of the parent node and the cell that RtreeSearchPoint
191 ** represents is the iCell-th entry in the parent node.
193 struct RtreeSearchPoint
{
194 RtreeDValue rScore
; /* The score for this node. Smallest goes first. */
195 sqlite3_int64 id
; /* Node ID */
196 u8 iLevel
; /* 0=entries. 1=leaf node. 2+ for higher */
197 u8 eWithin
; /* PARTLY_WITHIN or FULLY_WITHIN */
198 u8 iCell
; /* Cell index within the node */
202 ** The minimum number of cells allowed for a node is a third of the
203 ** maximum. In Gutman's notation:
207 ** If an R*-tree "Reinsert" operation is required, the same number of
208 ** cells are removed from the overfull node and reinserted into the tree.
210 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
211 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
212 #define RTREE_MAXCELLS 51
215 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
216 ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
217 ** Therefore all non-root nodes must contain at least 3 entries. Since
218 ** 3^40 is greater than 2^64, an r-tree structure always has a depth of
221 #define RTREE_MAX_DEPTH 40
225 ** Number of entries in the cursor RtreeNode cache. The first entry is
226 ** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining
227 ** entries cache the RtreeNode for the first elements of the priority queue.
229 #define RTREE_CACHE_SZ 5
232 ** An rtree cursor object.
235 sqlite3_vtab_cursor base
; /* Base class. Must be first */
236 u8 atEOF
; /* True if at end of search */
237 u8 bPoint
; /* True if sPoint is valid */
238 u8 bAuxValid
; /* True if pReadAux is valid */
239 int iStrategy
; /* Copy of idxNum search parameter */
240 int nConstraint
; /* Number of entries in aConstraint */
241 RtreeConstraint
*aConstraint
; /* Search constraints. */
242 int nPointAlloc
; /* Number of slots allocated for aPoint[] */
243 int nPoint
; /* Number of slots used in aPoint[] */
244 int mxLevel
; /* iLevel value for root of the tree */
245 RtreeSearchPoint
*aPoint
; /* Priority queue for search points */
246 sqlite3_stmt
*pReadAux
; /* Statement to read aux-data */
247 RtreeSearchPoint sPoint
; /* Cached next search point */
248 RtreeNode
*aNode
[RTREE_CACHE_SZ
]; /* Rtree node cache */
249 u32 anQueue
[RTREE_MAX_DEPTH
+1]; /* Number of queued entries by iLevel */
252 /* Return the Rtree of a RtreeCursor */
253 #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab))
256 ** A coordinate can be either a floating point number or a integer. All
257 ** coordinates within a single R-Tree are always of the same time.
260 RtreeValue f
; /* Floating point value */
261 int i
; /* Integer value */
262 u32 u
; /* Unsigned for byte-order conversions */
266 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
267 ** formatted as a RtreeDValue (double or int64). This macro assumes that local
268 ** variable pRtree points to the Rtree structure associated with the
271 #ifdef SQLITE_RTREE_INT_ONLY
272 # define DCOORD(coord) ((RtreeDValue)coord.i)
274 # define DCOORD(coord) ( \
275 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
276 ((double)coord.f) : \
282 ** A search constraint.
284 struct RtreeConstraint
{
285 int iCoord
; /* Index of constrained coordinate */
286 int op
; /* Constraining operation */
288 RtreeDValue rValue
; /* Constraint value. */
289 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*);
290 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
292 sqlite3_rtree_query_info
*pInfo
; /* xGeom and xQueryFunc argument */
295 /* Possible values for RtreeConstraint.op */
296 #define RTREE_EQ 0x41 /* A */
297 #define RTREE_LE 0x42 /* B */
298 #define RTREE_LT 0x43 /* C */
299 #define RTREE_GE 0x44 /* D */
300 #define RTREE_GT 0x45 /* E */
301 #define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */
302 #define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */
306 ** An rtree structure node.
309 RtreeNode
*pParent
; /* Parent node */
310 i64 iNode
; /* The node number */
311 int nRef
; /* Number of references to this node */
312 int isDirty
; /* True if the node needs to be written to disk */
313 u8
*zData
; /* Content of the node, as should be on disk */
314 RtreeNode
*pNext
; /* Next node in this hash collision chain */
317 /* Return the number of cells in a node */
318 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
321 ** A single cell from a node, deserialized
324 i64 iRowid
; /* Node or entry ID */
325 RtreeCoord aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Bounding box coordinates */
330 ** This object becomes the sqlite3_user_data() for the SQL functions
331 ** that are created by sqlite3_rtree_geometry_callback() and
332 ** sqlite3_rtree_query_callback() and which appear on the right of MATCH
333 ** operators in order to constrain a search.
335 ** xGeom and xQueryFunc are the callback functions. Exactly one of
336 ** xGeom and xQueryFunc fields is non-NULL, depending on whether the
337 ** SQL function was created using sqlite3_rtree_geometry_callback() or
338 ** sqlite3_rtree_query_callback().
340 ** This object is deleted automatically by the destructor mechanism in
341 ** sqlite3_create_function_v2().
343 struct RtreeGeomCallback
{
344 int (*xGeom
)(sqlite3_rtree_geometry
*, int, RtreeDValue
*, int*);
345 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
346 void (*xDestructor
)(void*);
351 ** An instance of this structure (in the form of a BLOB) is returned by
352 ** the SQL functions that sqlite3_rtree_geometry_callback() and
353 ** sqlite3_rtree_query_callback() create, and is read as the right-hand
354 ** operand to the MATCH operator of an R-Tree.
356 struct RtreeMatchArg
{
357 u32 iSize
; /* Size of this object */
358 RtreeGeomCallback cb
; /* Info about the callback functions */
359 int nParam
; /* Number of parameters to the SQL function */
360 sqlite3_value
**apSqlParam
; /* Original SQL parameter values */
361 RtreeDValue aParam
[1]; /* Values for parameters to the SQL function */
365 # define MAX(x,y) ((x) < (y) ? (y) : (x))
368 # define MIN(x,y) ((x) > (y) ? (y) : (x))
371 /* What version of GCC is being used. 0 means GCC is not being used .
372 ** Note that the GCC_VERSION macro will also be set correctly when using
373 ** clang, since clang works hard to be gcc compatible. So the gcc
374 ** optimizations will also work when compiling with clang.
377 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
378 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
380 # define GCC_VERSION 0
384 /* The testcase() macro should already be defined in the amalgamation. If
385 ** it is not, make it a no-op.
387 #ifndef SQLITE_AMALGAMATION
392 ** Macros to determine whether the machine is big or little endian,
393 ** and whether or not that determination is run-time or compile-time.
395 ** For best performance, an attempt is made to guess at the byte-order
396 ** using C-preprocessor macros. If that is unsuccessful, or if
397 ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined
400 #ifndef SQLITE_BYTEORDER
401 #if defined(i386) || defined(__i386__) || defined(_M_IX86) || \
402 defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \
403 defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \
405 # define SQLITE_BYTEORDER 1234
406 #elif defined(sparc) || defined(__ppc__)
407 # define SQLITE_BYTEORDER 4321
409 # define SQLITE_BYTEORDER 0 /* 0 means "unknown at compile-time" */
414 /* What version of MSVC is being used. 0 means MSVC is not being used */
416 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
417 # define MSVC_VERSION _MSC_VER
419 # define MSVC_VERSION 0
424 ** Functions to deserialize a 16 bit integer, 32 bit real number and
425 ** 64 bit integer. The deserialized value is returned.
427 static int readInt16(u8
*p
){
428 return (p
[0]<<8) + p
[1];
430 static void readCoord(u8
*p
, RtreeCoord
*pCoord
){
431 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
432 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
433 pCoord
->u
= _byteswap_ulong(*(u32
*)p
);
434 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
435 pCoord
->u
= __builtin_bswap32(*(u32
*)p
);
436 #elif SQLITE_BYTEORDER==4321
437 pCoord
->u
= *(u32
*)p
;
440 (((u32
)p
[0]) << 24) +
441 (((u32
)p
[1]) << 16) +
447 static i64
readInt64(u8
*p
){
448 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
451 return (i64
)_byteswap_uint64(x
);
452 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
455 return (i64
)__builtin_bswap64(x
);
456 #elif SQLITE_BYTEORDER==4321
462 (((u64
)p
[0]) << 56) +
463 (((u64
)p
[1]) << 48) +
464 (((u64
)p
[2]) << 40) +
465 (((u64
)p
[3]) << 32) +
466 (((u64
)p
[4]) << 24) +
467 (((u64
)p
[5]) << 16) +
475 ** Functions to serialize a 16 bit integer, 32 bit real number and
476 ** 64 bit integer. The value returned is the number of bytes written
477 ** to the argument buffer (always 2, 4 and 8 respectively).
479 static void writeInt16(u8
*p
, int i
){
483 static int writeCoord(u8
*p
, RtreeCoord
*pCoord
){
485 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
486 assert( sizeof(RtreeCoord
)==4 );
487 assert( sizeof(u32
)==4 );
488 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
489 i
= __builtin_bswap32(pCoord
->u
);
491 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
492 i
= _byteswap_ulong(pCoord
->u
);
494 #elif SQLITE_BYTEORDER==4321
506 static int writeInt64(u8
*p
, i64 i
){
507 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
508 i
= (i64
)__builtin_bswap64((u64
)i
);
510 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
511 i
= (i64
)_byteswap_uint64((u64
)i
);
513 #elif SQLITE_BYTEORDER==4321
529 ** Increment the reference count of node p.
531 static void nodeReference(RtreeNode
*p
){
538 ** Clear the content of node p (set all bytes to 0x00).
540 static void nodeZero(Rtree
*pRtree
, RtreeNode
*p
){
541 memset(&p
->zData
[2], 0, pRtree
->iNodeSize
-2);
546 ** Given a node number iNode, return the corresponding key to use
547 ** in the Rtree.aHash table.
549 static int nodeHash(i64 iNode
){
550 return iNode
% HASHSIZE
;
554 ** Search the node hash table for node iNode. If found, return a pointer
555 ** to it. Otherwise, return 0.
557 static RtreeNode
*nodeHashLookup(Rtree
*pRtree
, i64 iNode
){
559 for(p
=pRtree
->aHash
[nodeHash(iNode
)]; p
&& p
->iNode
!=iNode
; p
=p
->pNext
);
564 ** Add node pNode to the node hash table.
566 static void nodeHashInsert(Rtree
*pRtree
, RtreeNode
*pNode
){
568 assert( pNode
->pNext
==0 );
569 iHash
= nodeHash(pNode
->iNode
);
570 pNode
->pNext
= pRtree
->aHash
[iHash
];
571 pRtree
->aHash
[iHash
] = pNode
;
575 ** Remove node pNode from the node hash table.
577 static void nodeHashDelete(Rtree
*pRtree
, RtreeNode
*pNode
){
579 if( pNode
->iNode
!=0 ){
580 pp
= &pRtree
->aHash
[nodeHash(pNode
->iNode
)];
581 for( ; (*pp
)!=pNode
; pp
= &(*pp
)->pNext
){ assert(*pp
); }
588 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
589 ** indicating that node has not yet been assigned a node number. It is
590 ** assigned a node number when nodeWrite() is called to write the
591 ** node contents out to the database.
593 static RtreeNode
*nodeNew(Rtree
*pRtree
, RtreeNode
*pParent
){
595 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
) + pRtree
->iNodeSize
);
597 memset(pNode
, 0, sizeof(RtreeNode
) + pRtree
->iNodeSize
);
598 pNode
->zData
= (u8
*)&pNode
[1];
600 pNode
->pParent
= pParent
;
602 nodeReference(pParent
);
608 ** Clear the Rtree.pNodeBlob object
610 static void nodeBlobReset(Rtree
*pRtree
){
611 if( pRtree
->pNodeBlob
&& pRtree
->inWrTrans
==0 && pRtree
->nCursor
==0 ){
612 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
613 pRtree
->pNodeBlob
= 0;
614 sqlite3_blob_close(pBlob
);
619 ** Obtain a reference to an r-tree node.
621 static int nodeAcquire(
622 Rtree
*pRtree
, /* R-tree structure */
623 i64 iNode
, /* Node number to load */
624 RtreeNode
*pParent
, /* Either the parent node or NULL */
625 RtreeNode
**ppNode
/* OUT: Acquired node */
628 RtreeNode
*pNode
= 0;
630 /* Check if the requested node is already in the hash table. If so,
631 ** increase its reference count and return it.
633 if( (pNode
= nodeHashLookup(pRtree
, iNode
)) ){
634 assert( !pParent
|| !pNode
->pParent
|| pNode
->pParent
==pParent
);
635 if( pParent
&& !pNode
->pParent
){
636 nodeReference(pParent
);
637 pNode
->pParent
= pParent
;
644 if( pRtree
->pNodeBlob
){
645 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
646 pRtree
->pNodeBlob
= 0;
647 rc
= sqlite3_blob_reopen(pBlob
, iNode
);
648 pRtree
->pNodeBlob
= pBlob
;
650 nodeBlobReset(pRtree
);
651 if( rc
==SQLITE_NOMEM
) return SQLITE_NOMEM
;
654 if( pRtree
->pNodeBlob
==0 ){
655 char *zTab
= sqlite3_mprintf("%s_node", pRtree
->zName
);
656 if( zTab
==0 ) return SQLITE_NOMEM
;
657 rc
= sqlite3_blob_open(pRtree
->db
, pRtree
->zDb
, zTab
, "data", iNode
, 0,
662 nodeBlobReset(pRtree
);
664 /* If unable to open an sqlite3_blob on the desired row, that can only
665 ** be because the shadow tables hold erroneous data. */
666 if( rc
==SQLITE_ERROR
) rc
= SQLITE_CORRUPT_VTAB
;
667 }else if( pRtree
->iNodeSize
==sqlite3_blob_bytes(pRtree
->pNodeBlob
) ){
668 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
)+pRtree
->iNodeSize
);
672 pNode
->pParent
= pParent
;
673 pNode
->zData
= (u8
*)&pNode
[1];
675 pNode
->iNode
= iNode
;
678 rc
= sqlite3_blob_read(pRtree
->pNodeBlob
, pNode
->zData
,
679 pRtree
->iNodeSize
, 0);
680 nodeReference(pParent
);
684 /* If the root node was just loaded, set pRtree->iDepth to the height
685 ** of the r-tree structure. A height of zero means all data is stored on
686 ** the root node. A height of one means the children of the root node
687 ** are the leaves, and so on. If the depth as specified on the root node
688 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
690 if( pNode
&& iNode
==1 ){
691 pRtree
->iDepth
= readInt16(pNode
->zData
);
692 if( pRtree
->iDepth
>RTREE_MAX_DEPTH
){
693 rc
= SQLITE_CORRUPT_VTAB
;
697 /* If no error has occurred so far, check if the "number of entries"
698 ** field on the node is too large. If so, set the return code to
699 ** SQLITE_CORRUPT_VTAB.
701 if( pNode
&& rc
==SQLITE_OK
){
702 if( NCELL(pNode
)>((pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
) ){
703 rc
= SQLITE_CORRUPT_VTAB
;
709 nodeHashInsert(pRtree
, pNode
);
711 rc
= SQLITE_CORRUPT_VTAB
;
723 ** Overwrite cell iCell of node pNode with the contents of pCell.
725 static void nodeOverwriteCell(
726 Rtree
*pRtree
, /* The overall R-Tree */
727 RtreeNode
*pNode
, /* The node into which the cell is to be written */
728 RtreeCell
*pCell
, /* The cell to write */
729 int iCell
/* Index into pNode into which pCell is written */
732 u8
*p
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
733 p
+= writeInt64(p
, pCell
->iRowid
);
734 for(ii
=0; ii
<pRtree
->nDim2
; ii
++){
735 p
+= writeCoord(p
, &pCell
->aCoord
[ii
]);
741 ** Remove the cell with index iCell from node pNode.
743 static void nodeDeleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
){
744 u8
*pDst
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
745 u8
*pSrc
= &pDst
[pRtree
->nBytesPerCell
];
746 int nByte
= (NCELL(pNode
) - iCell
- 1) * pRtree
->nBytesPerCell
;
747 memmove(pDst
, pSrc
, nByte
);
748 writeInt16(&pNode
->zData
[2], NCELL(pNode
)-1);
753 ** Insert the contents of cell pCell into node pNode. If the insert
754 ** is successful, return SQLITE_OK.
756 ** If there is not enough free space in pNode, return SQLITE_FULL.
758 static int nodeInsertCell(
759 Rtree
*pRtree
, /* The overall R-Tree */
760 RtreeNode
*pNode
, /* Write new cell into this node */
761 RtreeCell
*pCell
/* The cell to be inserted */
763 int nCell
; /* Current number of cells in pNode */
764 int nMaxCell
; /* Maximum number of cells for pNode */
766 nMaxCell
= (pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
;
767 nCell
= NCELL(pNode
);
769 assert( nCell
<=nMaxCell
);
770 if( nCell
<nMaxCell
){
771 nodeOverwriteCell(pRtree
, pNode
, pCell
, nCell
);
772 writeInt16(&pNode
->zData
[2], nCell
+1);
776 return (nCell
==nMaxCell
);
780 ** If the node is dirty, write it out to the database.
782 static int nodeWrite(Rtree
*pRtree
, RtreeNode
*pNode
){
784 if( pNode
->isDirty
){
785 sqlite3_stmt
*p
= pRtree
->pWriteNode
;
787 sqlite3_bind_int64(p
, 1, pNode
->iNode
);
789 sqlite3_bind_null(p
, 1);
791 sqlite3_bind_blob(p
, 2, pNode
->zData
, pRtree
->iNodeSize
, SQLITE_STATIC
);
794 rc
= sqlite3_reset(p
);
795 sqlite3_bind_null(p
, 2);
796 if( pNode
->iNode
==0 && rc
==SQLITE_OK
){
797 pNode
->iNode
= sqlite3_last_insert_rowid(pRtree
->db
);
798 nodeHashInsert(pRtree
, pNode
);
805 ** Release a reference to a node. If the node is dirty and the reference
806 ** count drops to zero, the node data is written to the database.
808 static int nodeRelease(Rtree
*pRtree
, RtreeNode
*pNode
){
811 assert( pNode
->nRef
>0 );
813 if( pNode
->nRef
==0 ){
814 if( pNode
->iNode
==1 ){
817 if( pNode
->pParent
){
818 rc
= nodeRelease(pRtree
, pNode
->pParent
);
821 rc
= nodeWrite(pRtree
, pNode
);
823 nodeHashDelete(pRtree
, pNode
);
831 ** Return the 64-bit integer value associated with cell iCell of
832 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
833 ** an internal node, then the 64-bit integer is a child page number.
835 static i64
nodeGetRowid(
836 Rtree
*pRtree
, /* The overall R-Tree */
837 RtreeNode
*pNode
, /* The node from which to extract the ID */
838 int iCell
/* The cell index from which to extract the ID */
840 assert( iCell
<NCELL(pNode
) );
841 return readInt64(&pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
]);
845 ** Return coordinate iCoord from cell iCell in node pNode.
847 static void nodeGetCoord(
848 Rtree
*pRtree
, /* The overall R-Tree */
849 RtreeNode
*pNode
, /* The node from which to extract a coordinate */
850 int iCell
, /* The index of the cell within the node */
851 int iCoord
, /* Which coordinate to extract */
852 RtreeCoord
*pCoord
/* OUT: Space to write result to */
854 readCoord(&pNode
->zData
[12 + pRtree
->nBytesPerCell
*iCell
+ 4*iCoord
], pCoord
);
858 ** Deserialize cell iCell of node pNode. Populate the structure pointed
859 ** to by pCell with the results.
861 static void nodeGetCell(
862 Rtree
*pRtree
, /* The overall R-Tree */
863 RtreeNode
*pNode
, /* The node containing the cell to be read */
864 int iCell
, /* Index of the cell within the node */
865 RtreeCell
*pCell
/* OUT: Write the cell contents here */
870 pCell
->iRowid
= nodeGetRowid(pRtree
, pNode
, iCell
);
871 pData
= pNode
->zData
+ (12 + pRtree
->nBytesPerCell
*iCell
);
872 pCoord
= pCell
->aCoord
;
874 readCoord(pData
, &pCoord
[ii
]);
875 readCoord(pData
+4, &pCoord
[ii
+1]);
878 }while( ii
<pRtree
->nDim2
);
882 /* Forward declaration for the function that does the work of
883 ** the virtual table module xCreate() and xConnect() methods.
885 static int rtreeInit(
886 sqlite3
*, void *, int, const char *const*, sqlite3_vtab
**, char **, int
890 ** Rtree virtual table module xCreate method.
892 static int rtreeCreate(
895 int argc
, const char *const*argv
,
896 sqlite3_vtab
**ppVtab
,
899 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 1);
903 ** Rtree virtual table module xConnect method.
905 static int rtreeConnect(
908 int argc
, const char *const*argv
,
909 sqlite3_vtab
**ppVtab
,
912 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 0);
916 ** Increment the r-tree reference count.
918 static void rtreeReference(Rtree
*pRtree
){
923 ** Decrement the r-tree reference count. When the reference count reaches
924 ** zero the structure is deleted.
926 static void rtreeRelease(Rtree
*pRtree
){
928 if( pRtree
->nBusy
==0 ){
929 pRtree
->inWrTrans
= 0;
931 nodeBlobReset(pRtree
);
932 sqlite3_finalize(pRtree
->pWriteNode
);
933 sqlite3_finalize(pRtree
->pDeleteNode
);
934 sqlite3_finalize(pRtree
->pReadRowid
);
935 sqlite3_finalize(pRtree
->pWriteRowid
);
936 sqlite3_finalize(pRtree
->pDeleteRowid
);
937 sqlite3_finalize(pRtree
->pReadParent
);
938 sqlite3_finalize(pRtree
->pWriteParent
);
939 sqlite3_finalize(pRtree
->pDeleteParent
);
940 sqlite3_finalize(pRtree
->pWriteAux
);
941 sqlite3_free(pRtree
->zReadAuxSql
);
942 sqlite3_free(pRtree
);
947 ** Rtree virtual table module xDisconnect method.
949 static int rtreeDisconnect(sqlite3_vtab
*pVtab
){
950 rtreeRelease((Rtree
*)pVtab
);
955 ** Rtree virtual table module xDestroy method.
957 static int rtreeDestroy(sqlite3_vtab
*pVtab
){
958 Rtree
*pRtree
= (Rtree
*)pVtab
;
960 char *zCreate
= sqlite3_mprintf(
961 "DROP TABLE '%q'.'%q_node';"
962 "DROP TABLE '%q'.'%q_rowid';"
963 "DROP TABLE '%q'.'%q_parent';",
964 pRtree
->zDb
, pRtree
->zName
,
965 pRtree
->zDb
, pRtree
->zName
,
966 pRtree
->zDb
, pRtree
->zName
971 nodeBlobReset(pRtree
);
972 rc
= sqlite3_exec(pRtree
->db
, zCreate
, 0, 0, 0);
973 sqlite3_free(zCreate
);
976 rtreeRelease(pRtree
);
983 ** Rtree virtual table module xOpen method.
985 static int rtreeOpen(sqlite3_vtab
*pVTab
, sqlite3_vtab_cursor
**ppCursor
){
986 int rc
= SQLITE_NOMEM
;
987 Rtree
*pRtree
= (Rtree
*)pVTab
;
990 pCsr
= (RtreeCursor
*)sqlite3_malloc(sizeof(RtreeCursor
));
992 memset(pCsr
, 0, sizeof(RtreeCursor
));
993 pCsr
->base
.pVtab
= pVTab
;
997 *ppCursor
= (sqlite3_vtab_cursor
*)pCsr
;
1004 ** Free the RtreeCursor.aConstraint[] array and its contents.
1006 static void freeCursorConstraints(RtreeCursor
*pCsr
){
1007 if( pCsr
->aConstraint
){
1008 int i
; /* Used to iterate through constraint array */
1009 for(i
=0; i
<pCsr
->nConstraint
; i
++){
1010 sqlite3_rtree_query_info
*pInfo
= pCsr
->aConstraint
[i
].pInfo
;
1012 if( pInfo
->xDelUser
) pInfo
->xDelUser(pInfo
->pUser
);
1013 sqlite3_free(pInfo
);
1016 sqlite3_free(pCsr
->aConstraint
);
1017 pCsr
->aConstraint
= 0;
1022 ** Rtree virtual table module xClose method.
1024 static int rtreeClose(sqlite3_vtab_cursor
*cur
){
1025 Rtree
*pRtree
= (Rtree
*)(cur
->pVtab
);
1027 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1028 assert( pRtree
->nCursor
>0 );
1029 freeCursorConstraints(pCsr
);
1030 sqlite3_finalize(pCsr
->pReadAux
);
1031 sqlite3_free(pCsr
->aPoint
);
1032 for(ii
=0; ii
<RTREE_CACHE_SZ
; ii
++) nodeRelease(pRtree
, pCsr
->aNode
[ii
]);
1035 nodeBlobReset(pRtree
);
1040 ** Rtree virtual table module xEof method.
1042 ** Return non-zero if the cursor does not currently point to a valid
1043 ** record (i.e if the scan has finished), or zero otherwise.
1045 static int rtreeEof(sqlite3_vtab_cursor
*cur
){
1046 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1051 ** Convert raw bits from the on-disk RTree record into a coordinate value.
1052 ** The on-disk format is big-endian and needs to be converted for little-
1053 ** endian platforms. The on-disk record stores integer coordinates if
1054 ** eInt is true and it stores 32-bit floating point records if eInt is
1055 ** false. a[] is the four bytes of the on-disk record to be decoded.
1056 ** Store the results in "r".
1058 ** There are five versions of this macro. The last one is generic. The
1059 ** other four are various architectures-specific optimizations.
1061 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1062 #define RTREE_DECODE_COORD(eInt, a, r) { \
1063 RtreeCoord c; /* Coordinate decoded */ \
1064 c.u = _byteswap_ulong(*(u32*)a); \
1065 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1067 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1068 #define RTREE_DECODE_COORD(eInt, a, r) { \
1069 RtreeCoord c; /* Coordinate decoded */ \
1070 c.u = __builtin_bswap32(*(u32*)a); \
1071 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1073 #elif SQLITE_BYTEORDER==1234
1074 #define RTREE_DECODE_COORD(eInt, a, r) { \
1075 RtreeCoord c; /* Coordinate decoded */ \
1077 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
1078 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
1079 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1081 #elif SQLITE_BYTEORDER==4321
1082 #define RTREE_DECODE_COORD(eInt, a, r) { \
1083 RtreeCoord c; /* Coordinate decoded */ \
1085 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1088 #define RTREE_DECODE_COORD(eInt, a, r) { \
1089 RtreeCoord c; /* Coordinate decoded */ \
1090 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
1091 +((u32)a[2]<<8) + a[3]; \
1092 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1097 ** Check the RTree node or entry given by pCellData and p against the MATCH
1098 ** constraint pConstraint.
1100 static int rtreeCallbackConstraint(
1101 RtreeConstraint
*pConstraint
, /* The constraint to test */
1102 int eInt
, /* True if RTree holding integer coordinates */
1103 u8
*pCellData
, /* Raw cell content */
1104 RtreeSearchPoint
*pSearch
, /* Container of this cell */
1105 sqlite3_rtree_dbl
*prScore
, /* OUT: score for the cell */
1106 int *peWithin
/* OUT: visibility of the cell */
1108 sqlite3_rtree_query_info
*pInfo
= pConstraint
->pInfo
; /* Callback info */
1109 int nCoord
= pInfo
->nCoord
; /* No. of coordinates */
1110 int rc
; /* Callback return code */
1111 RtreeCoord c
; /* Translator union */
1112 sqlite3_rtree_dbl aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Decoded coordinates */
1114 assert( pConstraint
->op
==RTREE_MATCH
|| pConstraint
->op
==RTREE_QUERY
);
1115 assert( nCoord
==2 || nCoord
==4 || nCoord
==6 || nCoord
==8 || nCoord
==10 );
1117 if( pConstraint
->op
==RTREE_QUERY
&& pSearch
->iLevel
==1 ){
1118 pInfo
->iRowid
= readInt64(pCellData
);
1121 #ifndef SQLITE_RTREE_INT_ONLY
1124 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.f
;
1125 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.f
;
1126 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.f
;
1127 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.f
;
1128 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.f
;
1129 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.f
;
1130 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.f
;
1131 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.f
;
1132 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.f
;
1133 readCoord(pCellData
, &c
); aCoord
[0] = c
.f
;
1139 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.i
;
1140 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.i
;
1141 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.i
;
1142 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.i
;
1143 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.i
;
1144 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.i
;
1145 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.i
;
1146 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.i
;
1147 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.i
;
1148 readCoord(pCellData
, &c
); aCoord
[0] = c
.i
;
1151 if( pConstraint
->op
==RTREE_MATCH
){
1153 rc
= pConstraint
->u
.xGeom((sqlite3_rtree_geometry
*)pInfo
,
1154 nCoord
, aCoord
, &eWithin
);
1155 if( eWithin
==0 ) *peWithin
= NOT_WITHIN
;
1156 *prScore
= RTREE_ZERO
;
1158 pInfo
->aCoord
= aCoord
;
1159 pInfo
->iLevel
= pSearch
->iLevel
- 1;
1160 pInfo
->rScore
= pInfo
->rParentScore
= pSearch
->rScore
;
1161 pInfo
->eWithin
= pInfo
->eParentWithin
= pSearch
->eWithin
;
1162 rc
= pConstraint
->u
.xQueryFunc(pInfo
);
1163 if( pInfo
->eWithin
<*peWithin
) *peWithin
= pInfo
->eWithin
;
1164 if( pInfo
->rScore
<*prScore
|| *prScore
<RTREE_ZERO
){
1165 *prScore
= pInfo
->rScore
;
1172 ** Check the internal RTree node given by pCellData against constraint p.
1173 ** If this constraint cannot be satisfied by any child within the node,
1174 ** set *peWithin to NOT_WITHIN.
1176 static void rtreeNonleafConstraint(
1177 RtreeConstraint
*p
, /* The constraint to test */
1178 int eInt
, /* True if RTree holds integer coordinates */
1179 u8
*pCellData
, /* Raw cell content as appears on disk */
1180 int *peWithin
/* Adjust downward, as appropriate */
1182 sqlite3_rtree_dbl val
; /* Coordinate value convert to a double */
1184 /* p->iCoord might point to either a lower or upper bound coordinate
1185 ** in a coordinate pair. But make pCellData point to the lower bound.
1187 pCellData
+= 8 + 4*(p
->iCoord
&0xfe);
1189 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1190 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1191 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1196 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1197 /* val now holds the lower bound of the coordinate pair */
1198 if( p
->u
.rValue
>=val
) return;
1199 if( p
->op
!=RTREE_EQ
) break; /* RTREE_LE and RTREE_LT end here */
1200 /* Fall through for the RTREE_EQ case */
1202 default: /* RTREE_GT or RTREE_GE, or fallthrough of RTREE_EQ */
1204 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1205 /* val now holds the upper bound of the coordinate pair */
1206 if( p
->u
.rValue
<=val
) return;
1208 *peWithin
= NOT_WITHIN
;
1212 ** Check the leaf RTree cell given by pCellData against constraint p.
1213 ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
1214 ** If the constraint is satisfied, leave *peWithin unchanged.
1216 ** The constraint is of the form: xN op $val
1218 ** The op is given by p->op. The xN is p->iCoord-th coordinate in
1219 ** pCellData. $val is given by p->u.rValue.
1221 static void rtreeLeafConstraint(
1222 RtreeConstraint
*p
, /* The constraint to test */
1223 int eInt
, /* True if RTree holds integer coordinates */
1224 u8
*pCellData
, /* Raw cell content as appears on disk */
1225 int *peWithin
/* Adjust downward, as appropriate */
1227 RtreeDValue xN
; /* Coordinate value converted to a double */
1229 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1230 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1231 pCellData
+= 8 + p
->iCoord
*4;
1232 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1233 RTREE_DECODE_COORD(eInt
, pCellData
, xN
);
1235 case RTREE_LE
: if( xN
<= p
->u
.rValue
) return; break;
1236 case RTREE_LT
: if( xN
< p
->u
.rValue
) return; break;
1237 case RTREE_GE
: if( xN
>= p
->u
.rValue
) return; break;
1238 case RTREE_GT
: if( xN
> p
->u
.rValue
) return; break;
1239 default: if( xN
== p
->u
.rValue
) return; break;
1241 *peWithin
= NOT_WITHIN
;
1245 ** One of the cells in node pNode is guaranteed to have a 64-bit
1246 ** integer value equal to iRowid. Return the index of this cell.
1248 static int nodeRowidIndex(
1255 int nCell
= NCELL(pNode
);
1256 assert( nCell
<200 );
1257 for(ii
=0; ii
<nCell
; ii
++){
1258 if( nodeGetRowid(pRtree
, pNode
, ii
)==iRowid
){
1263 return SQLITE_CORRUPT_VTAB
;
1267 ** Return the index of the cell containing a pointer to node pNode
1268 ** in its parent. If pNode is the root node, return -1.
1270 static int nodeParentIndex(Rtree
*pRtree
, RtreeNode
*pNode
, int *piIndex
){
1271 RtreeNode
*pParent
= pNode
->pParent
;
1273 return nodeRowidIndex(pRtree
, pParent
, pNode
->iNode
, piIndex
);
1280 ** Compare two search points. Return negative, zero, or positive if the first
1281 ** is less than, equal to, or greater than the second.
1283 ** The rScore is the primary key. Smaller rScore values come first.
1284 ** If the rScore is a tie, then use iLevel as the tie breaker with smaller
1285 ** iLevel values coming first. In this way, if rScore is the same for all
1286 ** SearchPoints, then iLevel becomes the deciding factor and the result
1287 ** is a depth-first search, which is the desired default behavior.
1289 static int rtreeSearchPointCompare(
1290 const RtreeSearchPoint
*pA
,
1291 const RtreeSearchPoint
*pB
1293 if( pA
->rScore
<pB
->rScore
) return -1;
1294 if( pA
->rScore
>pB
->rScore
) return +1;
1295 if( pA
->iLevel
<pB
->iLevel
) return -1;
1296 if( pA
->iLevel
>pB
->iLevel
) return +1;
1301 ** Interchange two search points in a cursor.
1303 static void rtreeSearchPointSwap(RtreeCursor
*p
, int i
, int j
){
1304 RtreeSearchPoint t
= p
->aPoint
[i
];
1306 p
->aPoint
[i
] = p
->aPoint
[j
];
1309 if( i
<RTREE_CACHE_SZ
){
1310 if( j
>=RTREE_CACHE_SZ
){
1311 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1314 RtreeNode
*pTemp
= p
->aNode
[i
];
1315 p
->aNode
[i
] = p
->aNode
[j
];
1316 p
->aNode
[j
] = pTemp
;
1322 ** Return the search point with the lowest current score.
1324 static RtreeSearchPoint
*rtreeSearchPointFirst(RtreeCursor
*pCur
){
1325 return pCur
->bPoint
? &pCur
->sPoint
: pCur
->nPoint
? pCur
->aPoint
: 0;
1329 ** Get the RtreeNode for the search point with the lowest score.
1331 static RtreeNode
*rtreeNodeOfFirstSearchPoint(RtreeCursor
*pCur
, int *pRC
){
1333 int ii
= 1 - pCur
->bPoint
;
1334 assert( ii
==0 || ii
==1 );
1335 assert( pCur
->bPoint
|| pCur
->nPoint
);
1336 if( pCur
->aNode
[ii
]==0 ){
1338 id
= ii
? pCur
->aPoint
[0].id
: pCur
->sPoint
.id
;
1339 *pRC
= nodeAcquire(RTREE_OF_CURSOR(pCur
), id
, 0, &pCur
->aNode
[ii
]);
1341 return pCur
->aNode
[ii
];
1345 ** Push a new element onto the priority queue
1347 static RtreeSearchPoint
*rtreeEnqueue(
1348 RtreeCursor
*pCur
, /* The cursor */
1349 RtreeDValue rScore
, /* Score for the new search point */
1350 u8 iLevel
/* Level for the new search point */
1353 RtreeSearchPoint
*pNew
;
1354 if( pCur
->nPoint
>=pCur
->nPointAlloc
){
1355 int nNew
= pCur
->nPointAlloc
*2 + 8;
1356 pNew
= sqlite3_realloc(pCur
->aPoint
, nNew
*sizeof(pCur
->aPoint
[0]));
1357 if( pNew
==0 ) return 0;
1358 pCur
->aPoint
= pNew
;
1359 pCur
->nPointAlloc
= nNew
;
1362 pNew
= pCur
->aPoint
+ i
;
1363 pNew
->rScore
= rScore
;
1364 pNew
->iLevel
= iLevel
;
1365 assert( iLevel
<=RTREE_MAX_DEPTH
);
1367 RtreeSearchPoint
*pParent
;
1369 pParent
= pCur
->aPoint
+ j
;
1370 if( rtreeSearchPointCompare(pNew
, pParent
)>=0 ) break;
1371 rtreeSearchPointSwap(pCur
, j
, i
);
1379 ** Allocate a new RtreeSearchPoint and return a pointer to it. Return
1380 ** NULL if malloc fails.
1382 static RtreeSearchPoint
*rtreeSearchPointNew(
1383 RtreeCursor
*pCur
, /* The cursor */
1384 RtreeDValue rScore
, /* Score for the new search point */
1385 u8 iLevel
/* Level for the new search point */
1387 RtreeSearchPoint
*pNew
, *pFirst
;
1388 pFirst
= rtreeSearchPointFirst(pCur
);
1389 pCur
->anQueue
[iLevel
]++;
1391 || pFirst
->rScore
>rScore
1392 || (pFirst
->rScore
==rScore
&& pFirst
->iLevel
>iLevel
)
1396 pNew
= rtreeEnqueue(pCur
, rScore
, iLevel
);
1397 if( pNew
==0 ) return 0;
1398 ii
= (int)(pNew
- pCur
->aPoint
) + 1;
1399 if( ii
<RTREE_CACHE_SZ
){
1400 assert( pCur
->aNode
[ii
]==0 );
1401 pCur
->aNode
[ii
] = pCur
->aNode
[0];
1403 nodeRelease(RTREE_OF_CURSOR(pCur
), pCur
->aNode
[0]);
1406 *pNew
= pCur
->sPoint
;
1408 pCur
->sPoint
.rScore
= rScore
;
1409 pCur
->sPoint
.iLevel
= iLevel
;
1411 return &pCur
->sPoint
;
1413 return rtreeEnqueue(pCur
, rScore
, iLevel
);
1418 /* Tracing routines for the RtreeSearchPoint queue */
1419 static void tracePoint(RtreeSearchPoint
*p
, int idx
, RtreeCursor
*pCur
){
1420 if( idx
<0 ){ printf(" s"); }else{ printf("%2d", idx
); }
1421 printf(" %d.%05lld.%02d %g %d",
1422 p
->iLevel
, p
->id
, p
->iCell
, p
->rScore
, p
->eWithin
1425 if( idx
<RTREE_CACHE_SZ
){
1426 printf(" %p\n", pCur
->aNode
[idx
]);
1431 static void traceQueue(RtreeCursor
*pCur
, const char *zPrefix
){
1433 printf("=== %9s ", zPrefix
);
1435 tracePoint(&pCur
->sPoint
, -1, pCur
);
1437 for(ii
=0; ii
<pCur
->nPoint
; ii
++){
1438 if( ii
>0 || pCur
->bPoint
) printf(" ");
1439 tracePoint(&pCur
->aPoint
[ii
], ii
, pCur
);
1442 # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
1444 # define RTREE_QUEUE_TRACE(A,B) /* no-op */
1447 /* Remove the search point with the lowest current score.
1449 static void rtreeSearchPointPop(RtreeCursor
*p
){
1452 assert( i
==0 || i
==1 );
1454 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1458 p
->anQueue
[p
->sPoint
.iLevel
]--;
1460 }else if( p
->nPoint
){
1461 p
->anQueue
[p
->aPoint
[0].iLevel
]--;
1463 p
->aPoint
[0] = p
->aPoint
[n
];
1464 if( n
<RTREE_CACHE_SZ
-1 ){
1465 p
->aNode
[1] = p
->aNode
[n
+1];
1469 while( (j
= i
*2+1)<n
){
1471 if( k
<n
&& rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[j
])<0 ){
1472 if( rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[i
])<0 ){
1473 rtreeSearchPointSwap(p
, i
, k
);
1479 if( rtreeSearchPointCompare(&p
->aPoint
[j
], &p
->aPoint
[i
])<0 ){
1480 rtreeSearchPointSwap(p
, i
, j
);
1492 ** Continue the search on cursor pCur until the front of the queue
1493 ** contains an entry suitable for returning as a result-set row,
1494 ** or until the RtreeSearchPoint queue is empty, indicating that the
1495 ** query has completed.
1497 static int rtreeStepToLeaf(RtreeCursor
*pCur
){
1498 RtreeSearchPoint
*p
;
1499 Rtree
*pRtree
= RTREE_OF_CURSOR(pCur
);
1504 int nConstraint
= pCur
->nConstraint
;
1509 eInt
= pRtree
->eCoordType
==RTREE_COORD_INT32
;
1510 while( (p
= rtreeSearchPointFirst(pCur
))!=0 && p
->iLevel
>0 ){
1511 pNode
= rtreeNodeOfFirstSearchPoint(pCur
, &rc
);
1513 nCell
= NCELL(pNode
);
1514 assert( nCell
<200 );
1515 while( p
->iCell
<nCell
){
1516 sqlite3_rtree_dbl rScore
= (sqlite3_rtree_dbl
)-1;
1517 u8
*pCellData
= pNode
->zData
+ (4+pRtree
->nBytesPerCell
*p
->iCell
);
1518 eWithin
= FULLY_WITHIN
;
1519 for(ii
=0; ii
<nConstraint
; ii
++){
1520 RtreeConstraint
*pConstraint
= pCur
->aConstraint
+ ii
;
1521 if( pConstraint
->op
>=RTREE_MATCH
){
1522 rc
= rtreeCallbackConstraint(pConstraint
, eInt
, pCellData
, p
,
1525 }else if( p
->iLevel
==1 ){
1526 rtreeLeafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1528 rtreeNonleafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1530 if( eWithin
==NOT_WITHIN
) break;
1533 if( eWithin
==NOT_WITHIN
) continue;
1534 x
.iLevel
= p
->iLevel
- 1;
1536 x
.id
= readInt64(pCellData
);
1540 x
.iCell
= p
->iCell
- 1;
1542 if( p
->iCell
>=nCell
){
1543 RTREE_QUEUE_TRACE(pCur
, "POP-S:");
1544 rtreeSearchPointPop(pCur
);
1546 if( rScore
<RTREE_ZERO
) rScore
= RTREE_ZERO
;
1547 p
= rtreeSearchPointNew(pCur
, rScore
, x
.iLevel
);
1548 if( p
==0 ) return SQLITE_NOMEM
;
1549 p
->eWithin
= (u8
)eWithin
;
1552 RTREE_QUEUE_TRACE(pCur
, "PUSH-S:");
1555 if( p
->iCell
>=nCell
){
1556 RTREE_QUEUE_TRACE(pCur
, "POP-Se:");
1557 rtreeSearchPointPop(pCur
);
1565 ** Rtree virtual table module xNext method.
1567 static int rtreeNext(sqlite3_vtab_cursor
*pVtabCursor
){
1568 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1571 /* Move to the next entry that matches the configured constraints. */
1572 RTREE_QUEUE_TRACE(pCsr
, "POP-Nx:");
1573 if( pCsr
->bAuxValid
){
1574 pCsr
->bAuxValid
= 0;
1575 sqlite3_reset(pCsr
->pReadAux
);
1577 rtreeSearchPointPop(pCsr
);
1578 rc
= rtreeStepToLeaf(pCsr
);
1583 ** Rtree virtual table module xRowid method.
1585 static int rtreeRowid(sqlite3_vtab_cursor
*pVtabCursor
, sqlite_int64
*pRowid
){
1586 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1587 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1589 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1590 if( rc
==SQLITE_OK
&& p
){
1591 *pRowid
= nodeGetRowid(RTREE_OF_CURSOR(pCsr
), pNode
, p
->iCell
);
1597 ** Rtree virtual table module xColumn method.
1599 static int rtreeColumn(sqlite3_vtab_cursor
*cur
, sqlite3_context
*ctx
, int i
){
1600 Rtree
*pRtree
= (Rtree
*)cur
->pVtab
;
1601 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1602 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1605 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1608 if( p
==0 ) return SQLITE_OK
;
1610 sqlite3_result_int64(ctx
, nodeGetRowid(pRtree
, pNode
, p
->iCell
));
1611 }else if( i
<=pRtree
->nDim2
){
1612 nodeGetCoord(pRtree
, pNode
, p
->iCell
, i
-1, &c
);
1613 #ifndef SQLITE_RTREE_INT_ONLY
1614 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1615 sqlite3_result_double(ctx
, c
.f
);
1619 assert( pRtree
->eCoordType
==RTREE_COORD_INT32
);
1620 sqlite3_result_int(ctx
, c
.i
);
1623 if( !pCsr
->bAuxValid
){
1624 if( pCsr
->pReadAux
==0 ){
1625 rc
= sqlite3_prepare_v3(pRtree
->db
, pRtree
->zReadAuxSql
, -1, 0,
1626 &pCsr
->pReadAux
, 0);
1629 sqlite3_bind_int64(pCsr
->pReadAux
, 1,
1630 nodeGetRowid(pRtree
, pNode
, p
->iCell
));
1631 rc
= sqlite3_step(pCsr
->pReadAux
);
1632 if( rc
==SQLITE_ROW
){
1633 pCsr
->bAuxValid
= 1;
1635 sqlite3_reset(pCsr
->pReadAux
);
1636 if( rc
==SQLITE_DONE
) rc
= SQLITE_OK
;
1640 sqlite3_result_value(ctx
,
1641 sqlite3_column_value(pCsr
->pReadAux
, i
- pRtree
->nDim2
+ 1));
1647 ** Use nodeAcquire() to obtain the leaf node containing the record with
1648 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
1649 ** return SQLITE_OK. If there is no such record in the table, set
1650 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1651 ** to zero and return an SQLite error code.
1653 static int findLeafNode(
1654 Rtree
*pRtree
, /* RTree to search */
1655 i64 iRowid
, /* The rowid searching for */
1656 RtreeNode
**ppLeaf
, /* Write the node here */
1657 sqlite3_int64
*piNode
/* Write the node-id here */
1661 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, iRowid
);
1662 if( sqlite3_step(pRtree
->pReadRowid
)==SQLITE_ROW
){
1663 i64 iNode
= sqlite3_column_int64(pRtree
->pReadRowid
, 0);
1664 if( piNode
) *piNode
= iNode
;
1665 rc
= nodeAcquire(pRtree
, iNode
, 0, ppLeaf
);
1666 sqlite3_reset(pRtree
->pReadRowid
);
1668 rc
= sqlite3_reset(pRtree
->pReadRowid
);
1674 ** This function is called to configure the RtreeConstraint object passed
1675 ** as the second argument for a MATCH constraint. The value passed as the
1676 ** first argument to this function is the right-hand operand to the MATCH
1679 static int deserializeGeometry(sqlite3_value
*pValue
, RtreeConstraint
*pCons
){
1680 RtreeMatchArg
*pBlob
, *pSrc
; /* BLOB returned by geometry function */
1681 sqlite3_rtree_query_info
*pInfo
; /* Callback information */
1683 pSrc
= sqlite3_value_pointer(pValue
, "RtreeMatchArg");
1684 if( pSrc
==0 ) return SQLITE_ERROR
;
1685 pInfo
= (sqlite3_rtree_query_info
*)
1686 sqlite3_malloc64( sizeof(*pInfo
)+pSrc
->iSize
);
1687 if( !pInfo
) return SQLITE_NOMEM
;
1688 memset(pInfo
, 0, sizeof(*pInfo
));
1689 pBlob
= (RtreeMatchArg
*)&pInfo
[1];
1690 memcpy(pBlob
, pSrc
, pSrc
->iSize
);
1691 pInfo
->pContext
= pBlob
->cb
.pContext
;
1692 pInfo
->nParam
= pBlob
->nParam
;
1693 pInfo
->aParam
= pBlob
->aParam
;
1694 pInfo
->apSqlParam
= pBlob
->apSqlParam
;
1696 if( pBlob
->cb
.xGeom
){
1697 pCons
->u
.xGeom
= pBlob
->cb
.xGeom
;
1699 pCons
->op
= RTREE_QUERY
;
1700 pCons
->u
.xQueryFunc
= pBlob
->cb
.xQueryFunc
;
1702 pCons
->pInfo
= pInfo
;
1707 ** Rtree virtual table module xFilter method.
1709 static int rtreeFilter(
1710 sqlite3_vtab_cursor
*pVtabCursor
,
1711 int idxNum
, const char *idxStr
,
1712 int argc
, sqlite3_value
**argv
1714 Rtree
*pRtree
= (Rtree
*)pVtabCursor
->pVtab
;
1715 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1716 RtreeNode
*pRoot
= 0;
1721 rtreeReference(pRtree
);
1723 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
1724 freeCursorConstraints(pCsr
);
1725 sqlite3_free(pCsr
->aPoint
);
1726 memset(pCsr
, 0, sizeof(RtreeCursor
));
1727 pCsr
->base
.pVtab
= (sqlite3_vtab
*)pRtree
;
1729 pCsr
->iStrategy
= idxNum
;
1731 /* Special case - lookup by rowid. */
1732 RtreeNode
*pLeaf
; /* Leaf on which the required cell resides */
1733 RtreeSearchPoint
*p
; /* Search point for the leaf */
1734 i64 iRowid
= sqlite3_value_int64(argv
[0]);
1736 rc
= findLeafNode(pRtree
, iRowid
, &pLeaf
, &iNode
);
1737 if( rc
==SQLITE_OK
&& pLeaf
!=0 ){
1738 p
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, 0);
1739 assert( p
!=0 ); /* Always returns pCsr->sPoint */
1740 pCsr
->aNode
[0] = pLeaf
;
1742 p
->eWithin
= PARTLY_WITHIN
;
1743 rc
= nodeRowidIndex(pRtree
, pLeaf
, iRowid
, &iCell
);
1744 p
->iCell
= (u8
)iCell
;
1745 RTREE_QUEUE_TRACE(pCsr
, "PUSH-F1:");
1750 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1751 ** with the configured constraints.
1753 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
1754 if( rc
==SQLITE_OK
&& argc
>0 ){
1755 pCsr
->aConstraint
= sqlite3_malloc(sizeof(RtreeConstraint
)*argc
);
1756 pCsr
->nConstraint
= argc
;
1757 if( !pCsr
->aConstraint
){
1760 memset(pCsr
->aConstraint
, 0, sizeof(RtreeConstraint
)*argc
);
1761 memset(pCsr
->anQueue
, 0, sizeof(u32
)*(pRtree
->iDepth
+ 1));
1762 assert( (idxStr
==0 && argc
==0)
1763 || (idxStr
&& (int)strlen(idxStr
)==argc
*2) );
1764 for(ii
=0; ii
<argc
; ii
++){
1765 RtreeConstraint
*p
= &pCsr
->aConstraint
[ii
];
1766 p
->op
= idxStr
[ii
*2];
1767 p
->iCoord
= idxStr
[ii
*2+1]-'0';
1768 if( p
->op
>=RTREE_MATCH
){
1769 /* A MATCH operator. The right-hand-side must be a blob that
1770 ** can be cast into an RtreeMatchArg object. One created using
1771 ** an sqlite3_rtree_geometry_callback() SQL user function.
1773 rc
= deserializeGeometry(argv
[ii
], p
);
1774 if( rc
!=SQLITE_OK
){
1777 p
->pInfo
->nCoord
= pRtree
->nDim2
;
1778 p
->pInfo
->anQueue
= pCsr
->anQueue
;
1779 p
->pInfo
->mxLevel
= pRtree
->iDepth
+ 1;
1781 #ifdef SQLITE_RTREE_INT_ONLY
1782 p
->u
.rValue
= sqlite3_value_int64(argv
[ii
]);
1784 p
->u
.rValue
= sqlite3_value_double(argv
[ii
]);
1790 if( rc
==SQLITE_OK
){
1791 RtreeSearchPoint
*pNew
;
1792 pNew
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, (u8
)(pRtree
->iDepth
+1));
1793 if( pNew
==0 ) return SQLITE_NOMEM
;
1796 pNew
->eWithin
= PARTLY_WITHIN
;
1797 assert( pCsr
->bPoint
==1 );
1798 pCsr
->aNode
[0] = pRoot
;
1800 RTREE_QUEUE_TRACE(pCsr
, "PUSH-Fm:");
1801 rc
= rtreeStepToLeaf(pCsr
);
1805 nodeRelease(pRtree
, pRoot
);
1806 rtreeRelease(pRtree
);
1811 ** Rtree virtual table module xBestIndex method. There are three
1812 ** table scan strategies to choose from (in order from most to
1813 ** least desirable):
1815 ** idxNum idxStr Strategy
1816 ** ------------------------------------------------
1817 ** 1 Unused Direct lookup by rowid.
1818 ** 2 See below R-tree query or full-table scan.
1819 ** ------------------------------------------------
1821 ** If strategy 1 is used, then idxStr is not meaningful. If strategy
1822 ** 2 is used, idxStr is formatted to contain 2 bytes for each
1823 ** constraint used. The first two bytes of idxStr correspond to
1824 ** the constraint in sqlite3_index_info.aConstraintUsage[] with
1825 ** (argvIndex==1) etc.
1827 ** The first of each pair of bytes in idxStr identifies the constraint
1828 ** operator as follows:
1830 ** Operator Byte Value
1831 ** ----------------------
1838 ** ----------------------
1840 ** The second of each pair of bytes identifies the coordinate column
1841 ** to which the constraint applies. The leftmost coordinate column
1842 ** is 'a', the second from the left 'b' etc.
1844 static int rtreeBestIndex(sqlite3_vtab
*tab
, sqlite3_index_info
*pIdxInfo
){
1845 Rtree
*pRtree
= (Rtree
*)tab
;
1848 int bMatch
= 0; /* True if there exists a MATCH constraint */
1849 i64 nRow
; /* Estimated rows returned by this scan */
1852 char zIdxStr
[RTREE_MAX_DIMENSIONS
*8+1];
1853 memset(zIdxStr
, 0, sizeof(zIdxStr
));
1855 /* Check if there exists a MATCH constraint - even an unusable one. If there
1856 ** is, do not consider the lookup-by-rowid plan as using such a plan would
1857 ** require the VDBE to evaluate the MATCH constraint, which is not currently
1859 for(ii
=0; ii
<pIdxInfo
->nConstraint
; ii
++){
1860 if( pIdxInfo
->aConstraint
[ii
].op
==SQLITE_INDEX_CONSTRAINT_MATCH
){
1865 assert( pIdxInfo
->idxStr
==0 );
1866 for(ii
=0; ii
<pIdxInfo
->nConstraint
&& iIdx
<(int)(sizeof(zIdxStr
)-1); ii
++){
1867 struct sqlite3_index_constraint
*p
= &pIdxInfo
->aConstraint
[ii
];
1869 if( bMatch
==0 && p
->usable
1870 && p
->iColumn
==0 && p
->op
==SQLITE_INDEX_CONSTRAINT_EQ
1872 /* We have an equality constraint on the rowid. Use strategy 1. */
1874 for(jj
=0; jj
<ii
; jj
++){
1875 pIdxInfo
->aConstraintUsage
[jj
].argvIndex
= 0;
1876 pIdxInfo
->aConstraintUsage
[jj
].omit
= 0;
1878 pIdxInfo
->idxNum
= 1;
1879 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= 1;
1880 pIdxInfo
->aConstraintUsage
[jj
].omit
= 1;
1882 /* This strategy involves a two rowid lookups on an B-Tree structures
1883 ** and then a linear search of an R-Tree node. This should be
1884 ** considered almost as quick as a direct rowid lookup (for which
1885 ** sqlite uses an internal cost of 0.0). It is expected to return
1888 pIdxInfo
->estimatedCost
= 30.0;
1889 pIdxInfo
->estimatedRows
= 1;
1893 if( p
->usable
&& (p
->iColumn
>0 || p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
) ){
1896 case SQLITE_INDEX_CONSTRAINT_EQ
: op
= RTREE_EQ
; break;
1897 case SQLITE_INDEX_CONSTRAINT_GT
: op
= RTREE_GT
; break;
1898 case SQLITE_INDEX_CONSTRAINT_LE
: op
= RTREE_LE
; break;
1899 case SQLITE_INDEX_CONSTRAINT_LT
: op
= RTREE_LT
; break;
1900 case SQLITE_INDEX_CONSTRAINT_GE
: op
= RTREE_GE
; break;
1902 assert( p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
);
1906 zIdxStr
[iIdx
++] = op
;
1907 zIdxStr
[iIdx
++] = (char)(p
->iColumn
- 1 + '0');
1908 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= (iIdx
/2);
1909 pIdxInfo
->aConstraintUsage
[ii
].omit
= 1;
1913 pIdxInfo
->idxNum
= 2;
1914 pIdxInfo
->needToFreeIdxStr
= 1;
1915 if( iIdx
>0 && 0==(pIdxInfo
->idxStr
= sqlite3_mprintf("%s", zIdxStr
)) ){
1916 return SQLITE_NOMEM
;
1919 nRow
= pRtree
->nRowEst
>> (iIdx
/2);
1920 pIdxInfo
->estimatedCost
= (double)6.0 * (double)nRow
;
1921 pIdxInfo
->estimatedRows
= nRow
;
1927 ** Return the N-dimensional volumn of the cell stored in *p.
1929 static RtreeDValue
cellArea(Rtree
*pRtree
, RtreeCell
*p
){
1930 RtreeDValue area
= (RtreeDValue
)1;
1931 assert( pRtree
->nDim
>=1 && pRtree
->nDim
<=5 );
1932 #ifndef SQLITE_RTREE_INT_ONLY
1933 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1934 switch( pRtree
->nDim
){
1935 case 5: area
= p
->aCoord
[9].f
- p
->aCoord
[8].f
;
1936 case 4: area
*= p
->aCoord
[7].f
- p
->aCoord
[6].f
;
1937 case 3: area
*= p
->aCoord
[5].f
- p
->aCoord
[4].f
;
1938 case 2: area
*= p
->aCoord
[3].f
- p
->aCoord
[2].f
;
1939 default: area
*= p
->aCoord
[1].f
- p
->aCoord
[0].f
;
1944 switch( pRtree
->nDim
){
1945 case 5: area
= p
->aCoord
[9].i
- p
->aCoord
[8].i
;
1946 case 4: area
*= p
->aCoord
[7].i
- p
->aCoord
[6].i
;
1947 case 3: area
*= p
->aCoord
[5].i
- p
->aCoord
[4].i
;
1948 case 2: area
*= p
->aCoord
[3].i
- p
->aCoord
[2].i
;
1949 default: area
*= p
->aCoord
[1].i
- p
->aCoord
[0].i
;
1956 ** Return the margin length of cell p. The margin length is the sum
1957 ** of the objects size in each dimension.
1959 static RtreeDValue
cellMargin(Rtree
*pRtree
, RtreeCell
*p
){
1960 RtreeDValue margin
= 0;
1961 int ii
= pRtree
->nDim2
- 2;
1963 margin
+= (DCOORD(p
->aCoord
[ii
+1]) - DCOORD(p
->aCoord
[ii
]));
1970 ** Store the union of cells p1 and p2 in p1.
1972 static void cellUnion(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
1974 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1976 p1
->aCoord
[ii
].f
= MIN(p1
->aCoord
[ii
].f
, p2
->aCoord
[ii
].f
);
1977 p1
->aCoord
[ii
+1].f
= MAX(p1
->aCoord
[ii
+1].f
, p2
->aCoord
[ii
+1].f
);
1979 }while( ii
<pRtree
->nDim2
);
1982 p1
->aCoord
[ii
].i
= MIN(p1
->aCoord
[ii
].i
, p2
->aCoord
[ii
].i
);
1983 p1
->aCoord
[ii
+1].i
= MAX(p1
->aCoord
[ii
+1].i
, p2
->aCoord
[ii
+1].i
);
1985 }while( ii
<pRtree
->nDim2
);
1990 ** Return true if the area covered by p2 is a subset of the area covered
1991 ** by p1. False otherwise.
1993 static int cellContains(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
1995 int isInt
= (pRtree
->eCoordType
==RTREE_COORD_INT32
);
1996 for(ii
=0; ii
<pRtree
->nDim2
; ii
+=2){
1997 RtreeCoord
*a1
= &p1
->aCoord
[ii
];
1998 RtreeCoord
*a2
= &p2
->aCoord
[ii
];
1999 if( (!isInt
&& (a2
[0].f
<a1
[0].f
|| a2
[1].f
>a1
[1].f
))
2000 || ( isInt
&& (a2
[0].i
<a1
[0].i
|| a2
[1].i
>a1
[1].i
))
2009 ** Return the amount cell p would grow by if it were unioned with pCell.
2011 static RtreeDValue
cellGrowth(Rtree
*pRtree
, RtreeCell
*p
, RtreeCell
*pCell
){
2014 memcpy(&cell
, p
, sizeof(RtreeCell
));
2015 area
= cellArea(pRtree
, &cell
);
2016 cellUnion(pRtree
, &cell
, pCell
);
2017 return (cellArea(pRtree
, &cell
)-area
);
2020 static RtreeDValue
cellOverlap(
2027 RtreeDValue overlap
= RTREE_ZERO
;
2028 for(ii
=0; ii
<nCell
; ii
++){
2030 RtreeDValue o
= (RtreeDValue
)1;
2031 for(jj
=0; jj
<pRtree
->nDim2
; jj
+=2){
2033 x1
= MAX(DCOORD(p
->aCoord
[jj
]), DCOORD(aCell
[ii
].aCoord
[jj
]));
2034 x2
= MIN(DCOORD(p
->aCoord
[jj
+1]), DCOORD(aCell
[ii
].aCoord
[jj
+1]));
2049 ** This function implements the ChooseLeaf algorithm from Gutman[84].
2050 ** ChooseSubTree in r*tree terminology.
2052 static int ChooseLeaf(
2053 Rtree
*pRtree
, /* Rtree table */
2054 RtreeCell
*pCell
, /* Cell to insert into rtree */
2055 int iHeight
, /* Height of sub-tree rooted at pCell */
2056 RtreeNode
**ppLeaf
/* OUT: Selected leaf page */
2060 RtreeNode
*pNode
= 0;
2061 rc
= nodeAcquire(pRtree
, 1, 0, &pNode
);
2063 for(ii
=0; rc
==SQLITE_OK
&& ii
<(pRtree
->iDepth
-iHeight
); ii
++){
2065 sqlite3_int64 iBest
= 0;
2067 RtreeDValue fMinGrowth
= RTREE_ZERO
;
2068 RtreeDValue fMinArea
= RTREE_ZERO
;
2070 int nCell
= NCELL(pNode
);
2074 RtreeCell
*aCell
= 0;
2076 /* Select the child node which will be enlarged the least if pCell
2077 ** is inserted into it. Resolve ties by choosing the entry with
2078 ** the smallest area.
2080 for(iCell
=0; iCell
<nCell
; iCell
++){
2084 nodeGetCell(pRtree
, pNode
, iCell
, &cell
);
2085 growth
= cellGrowth(pRtree
, &cell
, pCell
);
2086 area
= cellArea(pRtree
, &cell
);
2087 if( iCell
==0||growth
<fMinGrowth
||(growth
==fMinGrowth
&& area
<fMinArea
) ){
2091 fMinGrowth
= growth
;
2093 iBest
= cell
.iRowid
;
2097 sqlite3_free(aCell
);
2098 rc
= nodeAcquire(pRtree
, iBest
, pNode
, &pChild
);
2099 nodeRelease(pRtree
, pNode
);
2108 ** A cell with the same content as pCell has just been inserted into
2109 ** the node pNode. This function updates the bounding box cells in
2110 ** all ancestor elements.
2112 static int AdjustTree(
2113 Rtree
*pRtree
, /* Rtree table */
2114 RtreeNode
*pNode
, /* Adjust ancestry of this node. */
2115 RtreeCell
*pCell
/* This cell was just inserted */
2117 RtreeNode
*p
= pNode
;
2118 while( p
->pParent
){
2119 RtreeNode
*pParent
= p
->pParent
;
2123 if( nodeParentIndex(pRtree
, p
, &iCell
) ){
2124 return SQLITE_CORRUPT_VTAB
;
2127 nodeGetCell(pRtree
, pParent
, iCell
, &cell
);
2128 if( !cellContains(pRtree
, &cell
, pCell
) ){
2129 cellUnion(pRtree
, &cell
, pCell
);
2130 nodeOverwriteCell(pRtree
, pParent
, &cell
, iCell
);
2139 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
2141 static int rowidWrite(Rtree
*pRtree
, sqlite3_int64 iRowid
, sqlite3_int64 iNode
){
2142 sqlite3_bind_int64(pRtree
->pWriteRowid
, 1, iRowid
);
2143 sqlite3_bind_int64(pRtree
->pWriteRowid
, 2, iNode
);
2144 sqlite3_step(pRtree
->pWriteRowid
);
2145 return sqlite3_reset(pRtree
->pWriteRowid
);
2149 ** Write mapping (iNode->iPar) to the <rtree>_parent table.
2151 static int parentWrite(Rtree
*pRtree
, sqlite3_int64 iNode
, sqlite3_int64 iPar
){
2152 sqlite3_bind_int64(pRtree
->pWriteParent
, 1, iNode
);
2153 sqlite3_bind_int64(pRtree
->pWriteParent
, 2, iPar
);
2154 sqlite3_step(pRtree
->pWriteParent
);
2155 return sqlite3_reset(pRtree
->pWriteParent
);
2158 static int rtreeInsertCell(Rtree
*, RtreeNode
*, RtreeCell
*, int);
2162 ** Arguments aIdx, aDistance and aSpare all point to arrays of size
2163 ** nIdx. The aIdx array contains the set of integers from 0 to
2164 ** (nIdx-1) in no particular order. This function sorts the values
2165 ** in aIdx according to the indexed values in aDistance. For
2166 ** example, assuming the inputs:
2168 ** aIdx = { 0, 1, 2, 3 }
2169 ** aDistance = { 5.0, 2.0, 7.0, 6.0 }
2171 ** this function sets the aIdx array to contain:
2173 ** aIdx = { 0, 1, 2, 3 }
2175 ** The aSpare array is used as temporary working space by the
2176 ** sorting algorithm.
2178 static void SortByDistance(
2181 RtreeDValue
*aDistance
,
2189 int nRight
= nIdx
-nLeft
;
2191 int *aRight
= &aIdx
[nLeft
];
2193 SortByDistance(aLeft
, nLeft
, aDistance
, aSpare
);
2194 SortByDistance(aRight
, nRight
, aDistance
, aSpare
);
2196 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2199 while( iLeft
<nLeft
|| iRight
<nRight
){
2201 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2203 }else if( iRight
==nRight
){
2204 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2207 RtreeDValue fLeft
= aDistance
[aLeft
[iLeft
]];
2208 RtreeDValue fRight
= aDistance
[aRight
[iRight
]];
2210 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2213 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2220 /* Check that the sort worked */
2223 for(jj
=1; jj
<nIdx
; jj
++){
2224 RtreeDValue left
= aDistance
[aIdx
[jj
-1]];
2225 RtreeDValue right
= aDistance
[aIdx
[jj
]];
2226 assert( left
<=right
);
2234 ** Arguments aIdx, aCell and aSpare all point to arrays of size
2235 ** nIdx. The aIdx array contains the set of integers from 0 to
2236 ** (nIdx-1) in no particular order. This function sorts the values
2237 ** in aIdx according to dimension iDim of the cells in aCell. The
2238 ** minimum value of dimension iDim is considered first, the
2239 ** maximum used to break ties.
2241 ** The aSpare array is used as temporary working space by the
2242 ** sorting algorithm.
2244 static void SortByDimension(
2258 int nRight
= nIdx
-nLeft
;
2260 int *aRight
= &aIdx
[nLeft
];
2262 SortByDimension(pRtree
, aLeft
, nLeft
, iDim
, aCell
, aSpare
);
2263 SortByDimension(pRtree
, aRight
, nRight
, iDim
, aCell
, aSpare
);
2265 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2267 while( iLeft
<nLeft
|| iRight
<nRight
){
2268 RtreeDValue xleft1
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2]);
2269 RtreeDValue xleft2
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2+1]);
2270 RtreeDValue xright1
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2]);
2271 RtreeDValue xright2
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2+1]);
2272 if( (iLeft
!=nLeft
) && ((iRight
==nRight
)
2274 || (xleft1
==xright1
&& xleft2
<xright2
)
2276 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2279 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2285 /* Check that the sort worked */
2288 for(jj
=1; jj
<nIdx
; jj
++){
2289 RtreeDValue xleft1
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2];
2290 RtreeDValue xleft2
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2+1];
2291 RtreeDValue xright1
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2];
2292 RtreeDValue xright2
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2+1];
2293 assert( xleft1
<=xright1
&& (xleft1
<xright1
|| xleft2
<=xright2
) );
2301 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
2303 static int splitNodeStartree(
2309 RtreeCell
*pBboxLeft
,
2310 RtreeCell
*pBboxRight
2318 RtreeDValue fBestMargin
= RTREE_ZERO
;
2320 int nByte
= (pRtree
->nDim
+1)*(sizeof(int*)+nCell
*sizeof(int));
2322 aaSorted
= (int **)sqlite3_malloc(nByte
);
2324 return SQLITE_NOMEM
;
2327 aSpare
= &((int *)&aaSorted
[pRtree
->nDim
])[pRtree
->nDim
*nCell
];
2328 memset(aaSorted
, 0, nByte
);
2329 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2331 aaSorted
[ii
] = &((int *)&aaSorted
[pRtree
->nDim
])[ii
*nCell
];
2332 for(jj
=0; jj
<nCell
; jj
++){
2333 aaSorted
[ii
][jj
] = jj
;
2335 SortByDimension(pRtree
, aaSorted
[ii
], nCell
, ii
, aCell
, aSpare
);
2338 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2339 RtreeDValue margin
= RTREE_ZERO
;
2340 RtreeDValue fBestOverlap
= RTREE_ZERO
;
2341 RtreeDValue fBestArea
= RTREE_ZERO
;
2346 nLeft
=RTREE_MINCELLS(pRtree
);
2347 nLeft
<=(nCell
-RTREE_MINCELLS(pRtree
));
2353 RtreeDValue overlap
;
2356 memcpy(&left
, &aCell
[aaSorted
[ii
][0]], sizeof(RtreeCell
));
2357 memcpy(&right
, &aCell
[aaSorted
[ii
][nCell
-1]], sizeof(RtreeCell
));
2358 for(kk
=1; kk
<(nCell
-1); kk
++){
2360 cellUnion(pRtree
, &left
, &aCell
[aaSorted
[ii
][kk
]]);
2362 cellUnion(pRtree
, &right
, &aCell
[aaSorted
[ii
][kk
]]);
2365 margin
+= cellMargin(pRtree
, &left
);
2366 margin
+= cellMargin(pRtree
, &right
);
2367 overlap
= cellOverlap(pRtree
, &left
, &right
, 1);
2368 area
= cellArea(pRtree
, &left
) + cellArea(pRtree
, &right
);
2369 if( (nLeft
==RTREE_MINCELLS(pRtree
))
2370 || (overlap
<fBestOverlap
)
2371 || (overlap
==fBestOverlap
&& area
<fBestArea
)
2374 fBestOverlap
= overlap
;
2379 if( ii
==0 || margin
<fBestMargin
){
2381 fBestMargin
= margin
;
2382 iBestSplit
= iBestLeft
;
2386 memcpy(pBboxLeft
, &aCell
[aaSorted
[iBestDim
][0]], sizeof(RtreeCell
));
2387 memcpy(pBboxRight
, &aCell
[aaSorted
[iBestDim
][iBestSplit
]], sizeof(RtreeCell
));
2388 for(ii
=0; ii
<nCell
; ii
++){
2389 RtreeNode
*pTarget
= (ii
<iBestSplit
)?pLeft
:pRight
;
2390 RtreeCell
*pBbox
= (ii
<iBestSplit
)?pBboxLeft
:pBboxRight
;
2391 RtreeCell
*pCell
= &aCell
[aaSorted
[iBestDim
][ii
]];
2392 nodeInsertCell(pRtree
, pTarget
, pCell
);
2393 cellUnion(pRtree
, pBbox
, pCell
);
2396 sqlite3_free(aaSorted
);
2401 static int updateMapping(
2407 int (*xSetMapping
)(Rtree
*, sqlite3_int64
, sqlite3_int64
);
2408 xSetMapping
= ((iHeight
==0)?rowidWrite
:parentWrite
);
2410 RtreeNode
*pChild
= nodeHashLookup(pRtree
, iRowid
);
2412 nodeRelease(pRtree
, pChild
->pParent
);
2413 nodeReference(pNode
);
2414 pChild
->pParent
= pNode
;
2417 return xSetMapping(pRtree
, iRowid
, pNode
->iNode
);
2420 static int SplitNode(
2427 int newCellIsRight
= 0;
2430 int nCell
= NCELL(pNode
);
2434 RtreeNode
*pLeft
= 0;
2435 RtreeNode
*pRight
= 0;
2438 RtreeCell rightbbox
;
2440 /* Allocate an array and populate it with a copy of pCell and
2441 ** all cells from node pLeft. Then zero the original node.
2443 aCell
= sqlite3_malloc((sizeof(RtreeCell
)+sizeof(int))*(nCell
+1));
2448 aiUsed
= (int *)&aCell
[nCell
+1];
2449 memset(aiUsed
, 0, sizeof(int)*(nCell
+1));
2450 for(i
=0; i
<nCell
; i
++){
2451 nodeGetCell(pRtree
, pNode
, i
, &aCell
[i
]);
2453 nodeZero(pRtree
, pNode
);
2454 memcpy(&aCell
[nCell
], pCell
, sizeof(RtreeCell
));
2457 if( pNode
->iNode
==1 ){
2458 pRight
= nodeNew(pRtree
, pNode
);
2459 pLeft
= nodeNew(pRtree
, pNode
);
2462 writeInt16(pNode
->zData
, pRtree
->iDepth
);
2465 pRight
= nodeNew(pRtree
, pLeft
->pParent
);
2466 nodeReference(pLeft
);
2469 if( !pLeft
|| !pRight
){
2474 memset(pLeft
->zData
, 0, pRtree
->iNodeSize
);
2475 memset(pRight
->zData
, 0, pRtree
->iNodeSize
);
2477 rc
= splitNodeStartree(pRtree
, aCell
, nCell
, pLeft
, pRight
,
2478 &leftbbox
, &rightbbox
);
2479 if( rc
!=SQLITE_OK
){
2483 /* Ensure both child nodes have node numbers assigned to them by calling
2484 ** nodeWrite(). Node pRight always needs a node number, as it was created
2485 ** by nodeNew() above. But node pLeft sometimes already has a node number.
2486 ** In this case avoid the all to nodeWrite().
2488 if( SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pRight
))
2489 || (0==pLeft
->iNode
&& SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pLeft
)))
2494 rightbbox
.iRowid
= pRight
->iNode
;
2495 leftbbox
.iRowid
= pLeft
->iNode
;
2497 if( pNode
->iNode
==1 ){
2498 rc
= rtreeInsertCell(pRtree
, pLeft
->pParent
, &leftbbox
, iHeight
+1);
2499 if( rc
!=SQLITE_OK
){
2503 RtreeNode
*pParent
= pLeft
->pParent
;
2505 rc
= nodeParentIndex(pRtree
, pLeft
, &iCell
);
2506 if( rc
==SQLITE_OK
){
2507 nodeOverwriteCell(pRtree
, pParent
, &leftbbox
, iCell
);
2508 rc
= AdjustTree(pRtree
, pParent
, &leftbbox
);
2510 if( rc
!=SQLITE_OK
){
2514 if( (rc
= rtreeInsertCell(pRtree
, pRight
->pParent
, &rightbbox
, iHeight
+1)) ){
2518 for(i
=0; i
<NCELL(pRight
); i
++){
2519 i64 iRowid
= nodeGetRowid(pRtree
, pRight
, i
);
2520 rc
= updateMapping(pRtree
, iRowid
, pRight
, iHeight
);
2521 if( iRowid
==pCell
->iRowid
){
2524 if( rc
!=SQLITE_OK
){
2528 if( pNode
->iNode
==1 ){
2529 for(i
=0; i
<NCELL(pLeft
); i
++){
2530 i64 iRowid
= nodeGetRowid(pRtree
, pLeft
, i
);
2531 rc
= updateMapping(pRtree
, iRowid
, pLeft
, iHeight
);
2532 if( rc
!=SQLITE_OK
){
2536 }else if( newCellIsRight
==0 ){
2537 rc
= updateMapping(pRtree
, pCell
->iRowid
, pLeft
, iHeight
);
2540 if( rc
==SQLITE_OK
){
2541 rc
= nodeRelease(pRtree
, pRight
);
2544 if( rc
==SQLITE_OK
){
2545 rc
= nodeRelease(pRtree
, pLeft
);
2550 nodeRelease(pRtree
, pRight
);
2551 nodeRelease(pRtree
, pLeft
);
2552 sqlite3_free(aCell
);
2557 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2558 ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2559 ** the pLeaf->pParent chain all the way up to the root node.
2561 ** This operation is required when a row is deleted (or updated - an update
2562 ** is implemented as a delete followed by an insert). SQLite provides the
2563 ** rowid of the row to delete, which can be used to find the leaf on which
2564 ** the entry resides (argument pLeaf). Once the leaf is located, this
2565 ** function is called to determine its ancestry.
2567 static int fixLeafParent(Rtree
*pRtree
, RtreeNode
*pLeaf
){
2569 RtreeNode
*pChild
= pLeaf
;
2570 while( rc
==SQLITE_OK
&& pChild
->iNode
!=1 && pChild
->pParent
==0 ){
2571 int rc2
= SQLITE_OK
; /* sqlite3_reset() return code */
2572 sqlite3_bind_int64(pRtree
->pReadParent
, 1, pChild
->iNode
);
2573 rc
= sqlite3_step(pRtree
->pReadParent
);
2574 if( rc
==SQLITE_ROW
){
2575 RtreeNode
*pTest
; /* Used to test for reference loops */
2576 i64 iNode
; /* Node number of parent node */
2578 /* Before setting pChild->pParent, test that we are not creating a
2579 ** loop of references (as we would if, say, pChild==pParent). We don't
2580 ** want to do this as it leads to a memory leak when trying to delete
2581 ** the referenced counted node structures.
2583 iNode
= sqlite3_column_int64(pRtree
->pReadParent
, 0);
2584 for(pTest
=pLeaf
; pTest
&& pTest
->iNode
!=iNode
; pTest
=pTest
->pParent
);
2586 rc2
= nodeAcquire(pRtree
, iNode
, 0, &pChild
->pParent
);
2589 rc
= sqlite3_reset(pRtree
->pReadParent
);
2590 if( rc
==SQLITE_OK
) rc
= rc2
;
2591 if( rc
==SQLITE_OK
&& !pChild
->pParent
) rc
= SQLITE_CORRUPT_VTAB
;
2592 pChild
= pChild
->pParent
;
2597 static int deleteCell(Rtree
*, RtreeNode
*, int, int);
2599 static int removeNode(Rtree
*pRtree
, RtreeNode
*pNode
, int iHeight
){
2602 RtreeNode
*pParent
= 0;
2605 assert( pNode
->nRef
==1 );
2607 /* Remove the entry in the parent cell. */
2608 rc
= nodeParentIndex(pRtree
, pNode
, &iCell
);
2609 if( rc
==SQLITE_OK
){
2610 pParent
= pNode
->pParent
;
2612 rc
= deleteCell(pRtree
, pParent
, iCell
, iHeight
+1);
2614 rc2
= nodeRelease(pRtree
, pParent
);
2615 if( rc
==SQLITE_OK
){
2618 if( rc
!=SQLITE_OK
){
2622 /* Remove the xxx_node entry. */
2623 sqlite3_bind_int64(pRtree
->pDeleteNode
, 1, pNode
->iNode
);
2624 sqlite3_step(pRtree
->pDeleteNode
);
2625 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteNode
)) ){
2629 /* Remove the xxx_parent entry. */
2630 sqlite3_bind_int64(pRtree
->pDeleteParent
, 1, pNode
->iNode
);
2631 sqlite3_step(pRtree
->pDeleteParent
);
2632 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteParent
)) ){
2636 /* Remove the node from the in-memory hash table and link it into
2637 ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2639 nodeHashDelete(pRtree
, pNode
);
2640 pNode
->iNode
= iHeight
;
2641 pNode
->pNext
= pRtree
->pDeleted
;
2643 pRtree
->pDeleted
= pNode
;
2648 static int fixBoundingBox(Rtree
*pRtree
, RtreeNode
*pNode
){
2649 RtreeNode
*pParent
= pNode
->pParent
;
2653 int nCell
= NCELL(pNode
);
2654 RtreeCell box
; /* Bounding box for pNode */
2655 nodeGetCell(pRtree
, pNode
, 0, &box
);
2656 for(ii
=1; ii
<nCell
; ii
++){
2658 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2659 cellUnion(pRtree
, &box
, &cell
);
2661 box
.iRowid
= pNode
->iNode
;
2662 rc
= nodeParentIndex(pRtree
, pNode
, &ii
);
2663 if( rc
==SQLITE_OK
){
2664 nodeOverwriteCell(pRtree
, pParent
, &box
, ii
);
2665 rc
= fixBoundingBox(pRtree
, pParent
);
2672 ** Delete the cell at index iCell of node pNode. After removing the
2673 ** cell, adjust the r-tree data structure if required.
2675 static int deleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
, int iHeight
){
2679 if( SQLITE_OK
!=(rc
= fixLeafParent(pRtree
, pNode
)) ){
2683 /* Remove the cell from the node. This call just moves bytes around
2684 ** the in-memory node image, so it cannot fail.
2686 nodeDeleteCell(pRtree
, pNode
, iCell
);
2688 /* If the node is not the tree root and now has less than the minimum
2689 ** number of cells, remove it from the tree. Otherwise, update the
2690 ** cell in the parent node so that it tightly contains the updated
2693 pParent
= pNode
->pParent
;
2694 assert( pParent
|| pNode
->iNode
==1 );
2696 if( NCELL(pNode
)<RTREE_MINCELLS(pRtree
) ){
2697 rc
= removeNode(pRtree
, pNode
, iHeight
);
2699 rc
= fixBoundingBox(pRtree
, pNode
);
2706 static int Reinsert(
2715 RtreeDValue
*aDistance
;
2717 RtreeDValue aCenterCoord
[RTREE_MAX_DIMENSIONS
];
2723 memset(aCenterCoord
, 0, sizeof(RtreeDValue
)*RTREE_MAX_DIMENSIONS
);
2725 nCell
= NCELL(pNode
)+1;
2728 /* Allocate the buffers used by this operation. The allocation is
2729 ** relinquished before this function returns.
2731 aCell
= (RtreeCell
*)sqlite3_malloc(n
* (
2732 sizeof(RtreeCell
) + /* aCell array */
2733 sizeof(int) + /* aOrder array */
2734 sizeof(int) + /* aSpare array */
2735 sizeof(RtreeDValue
) /* aDistance array */
2738 return SQLITE_NOMEM
;
2740 aOrder
= (int *)&aCell
[n
];
2741 aSpare
= (int *)&aOrder
[n
];
2742 aDistance
= (RtreeDValue
*)&aSpare
[n
];
2744 for(ii
=0; ii
<nCell
; ii
++){
2745 if( ii
==(nCell
-1) ){
2746 memcpy(&aCell
[ii
], pCell
, sizeof(RtreeCell
));
2748 nodeGetCell(pRtree
, pNode
, ii
, &aCell
[ii
]);
2751 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2752 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2]);
2753 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]);
2756 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2757 aCenterCoord
[iDim
] = (aCenterCoord
[iDim
]/(nCell
*(RtreeDValue
)2));
2760 for(ii
=0; ii
<nCell
; ii
++){
2761 aDistance
[ii
] = RTREE_ZERO
;
2762 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2763 RtreeDValue coord
= (DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]) -
2764 DCOORD(aCell
[ii
].aCoord
[iDim
*2]));
2765 aDistance
[ii
] += (coord
-aCenterCoord
[iDim
])*(coord
-aCenterCoord
[iDim
]);
2769 SortByDistance(aOrder
, nCell
, aDistance
, aSpare
);
2770 nodeZero(pRtree
, pNode
);
2772 for(ii
=0; rc
==SQLITE_OK
&& ii
<(nCell
-(RTREE_MINCELLS(pRtree
)+1)); ii
++){
2773 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2774 nodeInsertCell(pRtree
, pNode
, p
);
2775 if( p
->iRowid
==pCell
->iRowid
){
2777 rc
= rowidWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2779 rc
= parentWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2783 if( rc
==SQLITE_OK
){
2784 rc
= fixBoundingBox(pRtree
, pNode
);
2786 for(; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2787 /* Find a node to store this cell in. pNode->iNode currently contains
2788 ** the height of the sub-tree headed by the cell.
2791 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2792 rc
= ChooseLeaf(pRtree
, p
, iHeight
, &pInsert
);
2793 if( rc
==SQLITE_OK
){
2795 rc
= rtreeInsertCell(pRtree
, pInsert
, p
, iHeight
);
2796 rc2
= nodeRelease(pRtree
, pInsert
);
2797 if( rc
==SQLITE_OK
){
2803 sqlite3_free(aCell
);
2808 ** Insert cell pCell into node pNode. Node pNode is the head of a
2809 ** subtree iHeight high (leaf nodes have iHeight==0).
2811 static int rtreeInsertCell(
2819 RtreeNode
*pChild
= nodeHashLookup(pRtree
, pCell
->iRowid
);
2821 nodeRelease(pRtree
, pChild
->pParent
);
2822 nodeReference(pNode
);
2823 pChild
->pParent
= pNode
;
2826 if( nodeInsertCell(pRtree
, pNode
, pCell
) ){
2827 if( iHeight
<=pRtree
->iReinsertHeight
|| pNode
->iNode
==1){
2828 rc
= SplitNode(pRtree
, pNode
, pCell
, iHeight
);
2830 pRtree
->iReinsertHeight
= iHeight
;
2831 rc
= Reinsert(pRtree
, pNode
, pCell
, iHeight
);
2834 rc
= AdjustTree(pRtree
, pNode
, pCell
);
2835 if( rc
==SQLITE_OK
){
2837 rc
= rowidWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2839 rc
= parentWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2846 static int reinsertNodeContent(Rtree
*pRtree
, RtreeNode
*pNode
){
2849 int nCell
= NCELL(pNode
);
2851 for(ii
=0; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2854 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2856 /* Find a node to store this cell in. pNode->iNode currently contains
2857 ** the height of the sub-tree headed by the cell.
2859 rc
= ChooseLeaf(pRtree
, &cell
, (int)pNode
->iNode
, &pInsert
);
2860 if( rc
==SQLITE_OK
){
2862 rc
= rtreeInsertCell(pRtree
, pInsert
, &cell
, (int)pNode
->iNode
);
2863 rc2
= nodeRelease(pRtree
, pInsert
);
2864 if( rc
==SQLITE_OK
){
2873 ** Select a currently unused rowid for a new r-tree record.
2875 static int newRowid(Rtree
*pRtree
, i64
*piRowid
){
2877 sqlite3_bind_null(pRtree
->pWriteRowid
, 1);
2878 sqlite3_bind_null(pRtree
->pWriteRowid
, 2);
2879 sqlite3_step(pRtree
->pWriteRowid
);
2880 rc
= sqlite3_reset(pRtree
->pWriteRowid
);
2881 *piRowid
= sqlite3_last_insert_rowid(pRtree
->db
);
2886 ** Remove the entry with rowid=iDelete from the r-tree structure.
2888 static int rtreeDeleteRowid(Rtree
*pRtree
, sqlite3_int64 iDelete
){
2889 int rc
; /* Return code */
2890 RtreeNode
*pLeaf
= 0; /* Leaf node containing record iDelete */
2891 int iCell
; /* Index of iDelete cell in pLeaf */
2892 RtreeNode
*pRoot
= 0; /* Root node of rtree structure */
2895 /* Obtain a reference to the root node to initialize Rtree.iDepth */
2896 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
2898 /* Obtain a reference to the leaf node that contains the entry
2899 ** about to be deleted.
2901 if( rc
==SQLITE_OK
){
2902 rc
= findLeafNode(pRtree
, iDelete
, &pLeaf
, 0);
2905 /* Delete the cell in question from the leaf node. */
2906 if( rc
==SQLITE_OK
){
2908 rc
= nodeRowidIndex(pRtree
, pLeaf
, iDelete
, &iCell
);
2909 if( rc
==SQLITE_OK
){
2910 rc
= deleteCell(pRtree
, pLeaf
, iCell
, 0);
2912 rc2
= nodeRelease(pRtree
, pLeaf
);
2913 if( rc
==SQLITE_OK
){
2918 /* Delete the corresponding entry in the <rtree>_rowid table. */
2919 if( rc
==SQLITE_OK
){
2920 sqlite3_bind_int64(pRtree
->pDeleteRowid
, 1, iDelete
);
2921 sqlite3_step(pRtree
->pDeleteRowid
);
2922 rc
= sqlite3_reset(pRtree
->pDeleteRowid
);
2925 /* Check if the root node now has exactly one child. If so, remove
2926 ** it, schedule the contents of the child for reinsertion and
2927 ** reduce the tree height by one.
2929 ** This is equivalent to copying the contents of the child into
2930 ** the root node (the operation that Gutman's paper says to perform
2931 ** in this scenario).
2933 if( rc
==SQLITE_OK
&& pRtree
->iDepth
>0 && NCELL(pRoot
)==1 ){
2935 RtreeNode
*pChild
= 0;
2936 i64 iChild
= nodeGetRowid(pRtree
, pRoot
, 0);
2937 rc
= nodeAcquire(pRtree
, iChild
, pRoot
, &pChild
);
2938 if( rc
==SQLITE_OK
){
2939 rc
= removeNode(pRtree
, pChild
, pRtree
->iDepth
-1);
2941 rc2
= nodeRelease(pRtree
, pChild
);
2942 if( rc
==SQLITE_OK
) rc
= rc2
;
2943 if( rc
==SQLITE_OK
){
2945 writeInt16(pRoot
->zData
, pRtree
->iDepth
);
2950 /* Re-insert the contents of any underfull nodes removed from the tree. */
2951 for(pLeaf
=pRtree
->pDeleted
; pLeaf
; pLeaf
=pRtree
->pDeleted
){
2952 if( rc
==SQLITE_OK
){
2953 rc
= reinsertNodeContent(pRtree
, pLeaf
);
2955 pRtree
->pDeleted
= pLeaf
->pNext
;
2956 sqlite3_free(pLeaf
);
2959 /* Release the reference to the root node. */
2960 if( rc
==SQLITE_OK
){
2961 rc
= nodeRelease(pRtree
, pRoot
);
2963 nodeRelease(pRtree
, pRoot
);
2970 ** Rounding constants for float->double conversion.
2972 #define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */
2973 #define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */
2975 #if !defined(SQLITE_RTREE_INT_ONLY)
2977 ** Convert an sqlite3_value into an RtreeValue (presumably a float)
2978 ** while taking care to round toward negative or positive, respectively.
2980 static RtreeValue
rtreeValueDown(sqlite3_value
*v
){
2981 double d
= sqlite3_value_double(v
);
2984 f
= (float)(d
*(d
<0 ? RNDAWAY
: RNDTOWARDS
));
2988 static RtreeValue
rtreeValueUp(sqlite3_value
*v
){
2989 double d
= sqlite3_value_double(v
);
2992 f
= (float)(d
*(d
<0 ? RNDTOWARDS
: RNDAWAY
));
2996 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */
2999 ** A constraint has failed while inserting a row into an rtree table.
3000 ** Assuming no OOM error occurs, this function sets the error message
3001 ** (at pRtree->base.zErrMsg) to an appropriate value and returns
3002 ** SQLITE_CONSTRAINT.
3004 ** Parameter iCol is the index of the leftmost column involved in the
3005 ** constraint failure. If it is 0, then the constraint that failed is
3006 ** the unique constraint on the id column. Otherwise, it is the rtree
3007 ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed.
3009 ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT.
3011 static int rtreeConstraintError(Rtree
*pRtree
, int iCol
){
3012 sqlite3_stmt
*pStmt
= 0;
3016 assert( iCol
==0 || iCol
%2 );
3017 zSql
= sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree
->zDb
, pRtree
->zName
);
3019 rc
= sqlite3_prepare_v2(pRtree
->db
, zSql
, -1, &pStmt
, 0);
3025 if( rc
==SQLITE_OK
){
3027 const char *zCol
= sqlite3_column_name(pStmt
, 0);
3028 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
3029 "UNIQUE constraint failed: %s.%s", pRtree
->zName
, zCol
3032 const char *zCol1
= sqlite3_column_name(pStmt
, iCol
);
3033 const char *zCol2
= sqlite3_column_name(pStmt
, iCol
+1);
3034 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
3035 "rtree constraint failed: %s.(%s<=%s)", pRtree
->zName
, zCol1
, zCol2
3040 sqlite3_finalize(pStmt
);
3041 return (rc
==SQLITE_OK
? SQLITE_CONSTRAINT
: rc
);
3047 ** The xUpdate method for rtree module virtual tables.
3049 static int rtreeUpdate(
3050 sqlite3_vtab
*pVtab
,
3052 sqlite3_value
**aData
,
3053 sqlite_int64
*pRowid
3055 Rtree
*pRtree
= (Rtree
*)pVtab
;
3057 RtreeCell cell
; /* New cell to insert if nData>1 */
3058 int bHaveRowid
= 0; /* Set to 1 after new rowid is determined */
3060 rtreeReference(pRtree
);
3063 cell
.iRowid
= 0; /* Used only to suppress a compiler warning */
3065 /* Constraint handling. A write operation on an r-tree table may return
3066 ** SQLITE_CONSTRAINT for two reasons:
3068 ** 1. A duplicate rowid value, or
3069 ** 2. The supplied data violates the "x2>=x1" constraint.
3071 ** In the first case, if the conflict-handling mode is REPLACE, then
3072 ** the conflicting row can be removed before proceeding. In the second
3073 ** case, SQLITE_CONSTRAINT must be returned regardless of the
3074 ** conflict-handling mode specified by the user.
3080 if( nn
> pRtree
->nDim2
) nn
= pRtree
->nDim2
;
3081 /* Populate the cell.aCoord[] array. The first coordinate is aData[3].
3083 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
3084 ** with "column" that are interpreted as table constraints.
3085 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
3086 ** This problem was discovered after years of use, so we silently ignore
3087 ** these kinds of misdeclared tables to avoid breaking any legacy.
3090 #ifndef SQLITE_RTREE_INT_ONLY
3091 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
3092 for(ii
=0; ii
<nn
; ii
+=2){
3093 cell
.aCoord
[ii
].f
= rtreeValueDown(aData
[ii
+3]);
3094 cell
.aCoord
[ii
+1].f
= rtreeValueUp(aData
[ii
+4]);
3095 if( cell
.aCoord
[ii
].f
>cell
.aCoord
[ii
+1].f
){
3096 rc
= rtreeConstraintError(pRtree
, ii
+1);
3103 for(ii
=0; ii
<nn
; ii
+=2){
3104 cell
.aCoord
[ii
].i
= sqlite3_value_int(aData
[ii
+3]);
3105 cell
.aCoord
[ii
+1].i
= sqlite3_value_int(aData
[ii
+4]);
3106 if( cell
.aCoord
[ii
].i
>cell
.aCoord
[ii
+1].i
){
3107 rc
= rtreeConstraintError(pRtree
, ii
+1);
3113 /* If a rowid value was supplied, check if it is already present in
3114 ** the table. If so, the constraint has failed. */
3115 if( sqlite3_value_type(aData
[2])!=SQLITE_NULL
){
3116 cell
.iRowid
= sqlite3_value_int64(aData
[2]);
3117 if( sqlite3_value_type(aData
[0])==SQLITE_NULL
3118 || sqlite3_value_int64(aData
[0])!=cell
.iRowid
3121 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, cell
.iRowid
);
3122 steprc
= sqlite3_step(pRtree
->pReadRowid
);
3123 rc
= sqlite3_reset(pRtree
->pReadRowid
);
3124 if( SQLITE_ROW
==steprc
){
3125 if( sqlite3_vtab_on_conflict(pRtree
->db
)==SQLITE_REPLACE
){
3126 rc
= rtreeDeleteRowid(pRtree
, cell
.iRowid
);
3128 rc
= rtreeConstraintError(pRtree
, 0);
3137 /* If aData[0] is not an SQL NULL value, it is the rowid of a
3138 ** record to delete from the r-tree table. The following block does
3141 if( sqlite3_value_type(aData
[0])!=SQLITE_NULL
){
3142 rc
= rtreeDeleteRowid(pRtree
, sqlite3_value_int64(aData
[0]));
3145 /* If the aData[] array contains more than one element, elements
3146 ** (aData[2]..aData[argc-1]) contain a new record to insert into
3147 ** the r-tree structure.
3149 if( rc
==SQLITE_OK
&& nData
>1 ){
3150 /* Insert the new record into the r-tree */
3151 RtreeNode
*pLeaf
= 0;
3153 /* Figure out the rowid of the new row. */
3154 if( bHaveRowid
==0 ){
3155 rc
= newRowid(pRtree
, &cell
.iRowid
);
3157 *pRowid
= cell
.iRowid
;
3159 if( rc
==SQLITE_OK
){
3160 rc
= ChooseLeaf(pRtree
, &cell
, 0, &pLeaf
);
3162 if( rc
==SQLITE_OK
){
3164 pRtree
->iReinsertHeight
= -1;
3165 rc
= rtreeInsertCell(pRtree
, pLeaf
, &cell
, 0);
3166 rc2
= nodeRelease(pRtree
, pLeaf
);
3167 if( rc
==SQLITE_OK
){
3172 sqlite3_stmt
*pUp
= pRtree
->pWriteAux
;
3174 sqlite3_bind_int64(pUp
, 1, *pRowid
);
3175 for(jj
=0; jj
<pRtree
->nAux
; jj
++){
3176 sqlite3_bind_value(pUp
, jj
+2, aData
[pRtree
->nDim2
+3+jj
]);
3179 rc
= sqlite3_reset(pUp
);
3184 rtreeRelease(pRtree
);
3189 ** Called when a transaction starts.
3191 static int rtreeBeginTransaction(sqlite3_vtab
*pVtab
){
3192 Rtree
*pRtree
= (Rtree
*)pVtab
;
3193 assert( pRtree
->inWrTrans
==0 );
3194 pRtree
->inWrTrans
++;
3199 ** Called when a transaction completes (either by COMMIT or ROLLBACK).
3200 ** The sqlite3_blob object should be released at this point.
3202 static int rtreeEndTransaction(sqlite3_vtab
*pVtab
){
3203 Rtree
*pRtree
= (Rtree
*)pVtab
;
3204 pRtree
->inWrTrans
= 0;
3205 nodeBlobReset(pRtree
);
3210 ** The xRename method for rtree module virtual tables.
3212 static int rtreeRename(sqlite3_vtab
*pVtab
, const char *zNewName
){
3213 Rtree
*pRtree
= (Rtree
*)pVtab
;
3214 int rc
= SQLITE_NOMEM
;
3215 char *zSql
= sqlite3_mprintf(
3216 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
3217 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
3218 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
3219 , pRtree
->zDb
, pRtree
->zName
, zNewName
3220 , pRtree
->zDb
, pRtree
->zName
, zNewName
3221 , pRtree
->zDb
, pRtree
->zName
, zNewName
3224 nodeBlobReset(pRtree
);
3225 rc
= sqlite3_exec(pRtree
->db
, zSql
, 0, 0, 0);
3232 ** The xSavepoint method.
3234 ** This module does not need to do anything to support savepoints. However,
3235 ** it uses this hook to close any open blob handle. This is done because a
3236 ** DROP TABLE command - which fortunately always opens a savepoint - cannot
3237 ** succeed if there are any open blob handles. i.e. if the blob handle were
3238 ** not closed here, the following would fail:
3241 ** INSERT INTO rtree...
3242 ** DROP TABLE <tablename>; -- Would fail with SQLITE_LOCKED
3245 static int rtreeSavepoint(sqlite3_vtab
*pVtab
, int iSavepoint
){
3246 Rtree
*pRtree
= (Rtree
*)pVtab
;
3247 int iwt
= pRtree
->inWrTrans
;
3248 UNUSED_PARAMETER(iSavepoint
);
3249 pRtree
->inWrTrans
= 0;
3250 nodeBlobReset(pRtree
);
3251 pRtree
->inWrTrans
= iwt
;
3256 ** This function populates the pRtree->nRowEst variable with an estimate
3257 ** of the number of rows in the virtual table. If possible, this is based
3258 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
3260 static int rtreeQueryStat1(sqlite3
*db
, Rtree
*pRtree
){
3261 const char *zFmt
= "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
3267 rc
= sqlite3_table_column_metadata(
3268 db
, pRtree
->zDb
, "sqlite_stat1",0,0,0,0,0,0
3270 if( rc
!=SQLITE_OK
){
3271 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3272 return rc
==SQLITE_ERROR
? SQLITE_OK
: rc
;
3274 zSql
= sqlite3_mprintf(zFmt
, pRtree
->zDb
, pRtree
->zName
);
3278 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &p
, 0);
3279 if( rc
==SQLITE_OK
){
3280 if( sqlite3_step(p
)==SQLITE_ROW
) nRow
= sqlite3_column_int64(p
, 0);
3281 rc
= sqlite3_finalize(p
);
3282 }else if( rc
!=SQLITE_NOMEM
){
3286 if( rc
==SQLITE_OK
){
3288 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3290 pRtree
->nRowEst
= MAX(nRow
, RTREE_MIN_ROWEST
);
3299 static sqlite3_module rtreeModule
= {
3301 rtreeCreate
, /* xCreate - create a table */
3302 rtreeConnect
, /* xConnect - connect to an existing table */
3303 rtreeBestIndex
, /* xBestIndex - Determine search strategy */
3304 rtreeDisconnect
, /* xDisconnect - Disconnect from a table */
3305 rtreeDestroy
, /* xDestroy - Drop a table */
3306 rtreeOpen
, /* xOpen - open a cursor */
3307 rtreeClose
, /* xClose - close a cursor */
3308 rtreeFilter
, /* xFilter - configure scan constraints */
3309 rtreeNext
, /* xNext - advance a cursor */
3310 rtreeEof
, /* xEof */
3311 rtreeColumn
, /* xColumn - read data */
3312 rtreeRowid
, /* xRowid - read data */
3313 rtreeUpdate
, /* xUpdate - write data */
3314 rtreeBeginTransaction
, /* xBegin - begin transaction */
3315 rtreeEndTransaction
, /* xSync - sync transaction */
3316 rtreeEndTransaction
, /* xCommit - commit transaction */
3317 rtreeEndTransaction
, /* xRollback - rollback transaction */
3318 0, /* xFindFunction - function overloading */
3319 rtreeRename
, /* xRename - rename the table */
3320 rtreeSavepoint
, /* xSavepoint */
3322 0, /* xRollbackTo */
3325 static int rtreeSqlInit(
3329 const char *zPrefix
,
3334 #define N_STATEMENT 8
3335 static const char *azSql
[N_STATEMENT
] = {
3336 /* Write the xxx_node table */
3337 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(?1, ?2)",
3338 "DELETE FROM '%q'.'%q_node' WHERE nodeno = ?1",
3340 /* Read and write the xxx_rowid table */
3341 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3342 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(?1, ?2)",
3343 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3345 /* Read and write the xxx_parent table */
3346 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = ?1",
3347 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(?1, ?2)",
3348 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = ?1"
3350 sqlite3_stmt
**appStmt
[N_STATEMENT
];
3357 sqlite3_str
*p
= sqlite3_str_new(db
);
3359 sqlite3_str_appendf(p
,
3360 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY,nodeno",
3362 for(ii
=0; ii
<pRtree
->nAux
; ii
++){
3363 sqlite3_str_appendf(p
,",a%d",ii
);
3365 sqlite3_str_appendf(p
,
3366 ");CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY,data);",
3368 sqlite3_str_appendf(p
,
3369 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,parentnode);",
3371 sqlite3_str_appendf(p
,
3372 "INSERT INTO \"%w\".\"%w_node\"VALUES(1,zeroblob(%d))",
3373 zDb
, zPrefix
, pRtree
->iNodeSize
);
3374 zCreate
= sqlite3_str_finish(p
);
3376 return SQLITE_NOMEM
;
3378 rc
= sqlite3_exec(db
, zCreate
, 0, 0, 0);
3379 sqlite3_free(zCreate
);
3380 if( rc
!=SQLITE_OK
){
3385 appStmt
[0] = &pRtree
->pWriteNode
;
3386 appStmt
[1] = &pRtree
->pDeleteNode
;
3387 appStmt
[2] = &pRtree
->pReadRowid
;
3388 appStmt
[3] = &pRtree
->pWriteRowid
;
3389 appStmt
[4] = &pRtree
->pDeleteRowid
;
3390 appStmt
[5] = &pRtree
->pReadParent
;
3391 appStmt
[6] = &pRtree
->pWriteParent
;
3392 appStmt
[7] = &pRtree
->pDeleteParent
;
3394 rc
= rtreeQueryStat1(db
, pRtree
);
3395 for(i
=0; i
<N_STATEMENT
&& rc
==SQLITE_OK
; i
++){
3397 const char *zFormat
;
3398 if( i
!=3 || pRtree
->nAux
==0 ){
3401 /* An UPSERT is very slightly slower than REPLACE, but it is needed
3402 ** if there are auxiliary columns */
3403 zFormat
= "INSERT INTO\"%w\".\"%w_rowid\"(rowid,nodeno)VALUES(?1,?2)"
3404 "ON CONFLICT(rowid)DO UPDATE SET nodeno=excluded.nodeno";
3406 zSql
= sqlite3_mprintf(zFormat
, zDb
, zPrefix
);
3408 rc
= sqlite3_prepare_v3(db
, zSql
, -1, SQLITE_PREPARE_PERSISTENT
,
3416 pRtree
->zReadAuxSql
= sqlite3_mprintf(
3417 "SELECT * FROM \"%w\".\"%w_rowid\" WHERE rowid=?1",
3419 if( pRtree
->zReadAuxSql
==0 ){
3422 sqlite3_str
*p
= sqlite3_str_new(db
);
3425 sqlite3_str_appendf(p
, "UPDATE \"%w\".\"%w_rowid\"SET ", zDb
, zPrefix
);
3426 for(ii
=0; ii
<pRtree
->nAux
; ii
++){
3427 if( ii
) sqlite3_str_append(p
, ",", 1);
3428 sqlite3_str_appendf(p
,"a%d=?%d",ii
,ii
+2);
3430 sqlite3_str_appendf(p
, " WHERE rowid=?1");
3431 zSql
= sqlite3_str_finish(p
);
3435 rc
= sqlite3_prepare_v3(db
, zSql
, -1, SQLITE_PREPARE_PERSISTENT
,
3436 &pRtree
->pWriteAux
, 0);
3446 ** The second argument to this function contains the text of an SQL statement
3447 ** that returns a single integer value. The statement is compiled and executed
3448 ** using database connection db. If successful, the integer value returned
3449 ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
3450 ** code is returned and the value of *piVal after returning is not defined.
3452 static int getIntFromStmt(sqlite3
*db
, const char *zSql
, int *piVal
){
3453 int rc
= SQLITE_NOMEM
;
3455 sqlite3_stmt
*pStmt
= 0;
3456 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &pStmt
, 0);
3457 if( rc
==SQLITE_OK
){
3458 if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
3459 *piVal
= sqlite3_column_int(pStmt
, 0);
3461 rc
= sqlite3_finalize(pStmt
);
3468 ** This function is called from within the xConnect() or xCreate() method to
3469 ** determine the node-size used by the rtree table being created or connected
3470 ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
3471 ** Otherwise, an SQLite error code is returned.
3473 ** If this function is being called as part of an xConnect(), then the rtree
3474 ** table already exists. In this case the node-size is determined by inspecting
3475 ** the root node of the tree.
3477 ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
3478 ** This ensures that each node is stored on a single database page. If the
3479 ** database page-size is so large that more than RTREE_MAXCELLS entries
3480 ** would fit in a single node, use a smaller node-size.
3482 static int getNodeSize(
3483 sqlite3
*db
, /* Database handle */
3484 Rtree
*pRtree
, /* Rtree handle */
3485 int isCreate
, /* True for xCreate, false for xConnect */
3486 char **pzErr
/* OUT: Error message, if any */
3492 zSql
= sqlite3_mprintf("PRAGMA %Q.page_size", pRtree
->zDb
);
3493 rc
= getIntFromStmt(db
, zSql
, &iPageSize
);
3494 if( rc
==SQLITE_OK
){
3495 pRtree
->iNodeSize
= iPageSize
-64;
3496 if( (4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
)<pRtree
->iNodeSize
){
3497 pRtree
->iNodeSize
= 4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
;
3500 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3503 zSql
= sqlite3_mprintf(
3504 "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
3505 pRtree
->zDb
, pRtree
->zName
3507 rc
= getIntFromStmt(db
, zSql
, &pRtree
->iNodeSize
);
3508 if( rc
!=SQLITE_OK
){
3509 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3510 }else if( pRtree
->iNodeSize
<(512-64) ){
3511 rc
= SQLITE_CORRUPT_VTAB
;
3512 *pzErr
= sqlite3_mprintf("undersize RTree blobs in \"%q_node\"",
3522 ** This function is the implementation of both the xConnect and xCreate
3523 ** methods of the r-tree virtual table.
3525 ** argv[0] -> module name
3526 ** argv[1] -> database name
3527 ** argv[2] -> table name
3528 ** argv[...] -> column names...
3530 static int rtreeInit(
3531 sqlite3
*db
, /* Database connection */
3532 void *pAux
, /* One of the RTREE_COORD_* constants */
3533 int argc
, const char *const*argv
, /* Parameters to CREATE TABLE statement */
3534 sqlite3_vtab
**ppVtab
, /* OUT: New virtual table */
3535 char **pzErr
, /* OUT: Error message, if any */
3536 int isCreate
/* True for xCreate, false for xConnect */
3540 int nDb
; /* Length of string argv[1] */
3541 int nName
; /* Length of string argv[2] */
3542 int eCoordType
= (pAux
? RTREE_COORD_INT32
: RTREE_COORD_REAL32
);
3548 const char *aErrMsg
[] = {
3550 "Wrong number of columns for an rtree table", /* 1 */
3551 "Too few columns for an rtree table", /* 2 */
3552 "Too many columns for an rtree table", /* 3 */
3553 "AUX: columns must be last" /* 4 */
3557 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[3]);
3558 return SQLITE_ERROR
;
3561 sqlite3_vtab_config(db
, SQLITE_VTAB_CONSTRAINT_SUPPORT
, 1);
3563 /* Allocate the sqlite3_vtab structure */
3564 nDb
= (int)strlen(argv
[1]);
3565 nName
= (int)strlen(argv
[2]);
3566 pRtree
= (Rtree
*)sqlite3_malloc(sizeof(Rtree
)+nDb
+nName
+2);
3568 return SQLITE_NOMEM
;
3570 memset(pRtree
, 0, sizeof(Rtree
)+nDb
+nName
+2);
3572 pRtree
->base
.pModule
= &rtreeModule
;
3573 pRtree
->zDb
= (char *)&pRtree
[1];
3574 pRtree
->zName
= &pRtree
->zDb
[nDb
+1];
3575 pRtree
->eCoordType
= (u8
)eCoordType
;
3576 memcpy(pRtree
->zDb
, argv
[1], nDb
);
3577 memcpy(pRtree
->zName
, argv
[2], nName
);
3580 /* Create/Connect to the underlying relational database schema. If
3581 ** that is successful, call sqlite3_declare_vtab() to configure
3582 ** the r-tree table schema.
3584 pSql
= sqlite3_str_new(db
);
3585 sqlite3_str_appendf(pSql
, "CREATE TABLE x(%s", argv
[3]);
3586 for(ii
=4; ii
<argc
; ii
++){
3587 if( sqlite3_strlike("aux:%", argv
[ii
], 0)==0 ){
3589 sqlite3_str_appendf(pSql
, ",%s", argv
[ii
]+4);
3590 }else if( pRtree
->nAux
>0 ){
3594 sqlite3_str_appendf(pSql
, ",%s", argv
[ii
]);
3597 sqlite3_str_appendf(pSql
, ");");
3598 zSql
= sqlite3_str_finish(pSql
);
3601 }else if( ii
<argc
){
3602 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[4]);
3604 }else if( SQLITE_OK
!=(rc
= sqlite3_declare_vtab(db
, zSql
)) ){
3605 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3608 if( rc
) goto rtreeInit_fail
;
3609 pRtree
->nDim
= pRtree
->nDim2
/2;
3610 if( pRtree
->nDim
<1 ){
3612 }else if( pRtree
->nDim2
>RTREE_MAX_DIMENSIONS
*2 ){
3614 }else if( pRtree
->nDim2
% 2 ){
3620 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[iErr
]);
3621 goto rtreeInit_fail
;
3623 pRtree
->nBytesPerCell
= 8 + pRtree
->nDim2
*4;
3625 /* Figure out the node size to use. */
3626 rc
= getNodeSize(db
, pRtree
, isCreate
, pzErr
);
3627 if( rc
) goto rtreeInit_fail
;
3628 rc
= rtreeSqlInit(pRtree
, db
, argv
[1], argv
[2], isCreate
);
3630 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3631 goto rtreeInit_fail
;
3634 *ppVtab
= (sqlite3_vtab
*)pRtree
;
3638 if( rc
==SQLITE_OK
) rc
= SQLITE_ERROR
;
3639 assert( *ppVtab
==0 );
3640 assert( pRtree
->nBusy
==1 );
3641 rtreeRelease(pRtree
);
3647 ** Implementation of a scalar function that decodes r-tree nodes to
3648 ** human readable strings. This can be used for debugging and analysis.
3650 ** The scalar function takes two arguments: (1) the number of dimensions
3651 ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
3652 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
3653 ** deserialize all nodes, a statement like:
3655 ** SELECT rtreenode(2, data) FROM rt_node;
3657 ** The human readable string takes the form of a Tcl list with one
3658 ** entry for each cell in the r-tree node. Each entry is itself a
3659 ** list, containing the 8-byte rowid/pageno followed by the
3660 ** <num-dimension>*2 coordinates.
3662 static void rtreenode(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3668 UNUSED_PARAMETER(nArg
);
3669 memset(&node
, 0, sizeof(RtreeNode
));
3670 memset(&tree
, 0, sizeof(Rtree
));
3671 tree
.nDim
= (u8
)sqlite3_value_int(apArg
[0]);
3672 tree
.nDim2
= tree
.nDim
*2;
3673 tree
.nBytesPerCell
= 8 + 8 * tree
.nDim
;
3674 node
.zData
= (u8
*)sqlite3_value_blob(apArg
[1]);
3676 for(ii
=0; ii
<NCELL(&node
); ii
++){
3682 nodeGetCell(&tree
, &node
, ii
, &cell
);
3683 sqlite3_snprintf(512-nCell
,&zCell
[nCell
],"%lld", cell
.iRowid
);
3684 nCell
= (int)strlen(zCell
);
3685 for(jj
=0; jj
<tree
.nDim2
; jj
++){
3686 #ifndef SQLITE_RTREE_INT_ONLY
3687 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %g",
3688 (double)cell
.aCoord
[jj
].f
);
3690 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %d",
3693 nCell
= (int)strlen(zCell
);
3697 char *zTextNew
= sqlite3_mprintf("%s {%s}", zText
, zCell
);
3698 sqlite3_free(zText
);
3701 zText
= sqlite3_mprintf("{%s}", zCell
);
3705 sqlite3_result_text(ctx
, zText
, -1, sqlite3_free
);
3708 /* This routine implements an SQL function that returns the "depth" parameter
3709 ** from the front of a blob that is an r-tree node. For example:
3711 ** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
3713 ** The depth value is 0 for all nodes other than the root node, and the root
3714 ** node always has nodeno=1, so the example above is the primary use for this
3715 ** routine. This routine is intended for testing and analysis only.
3717 static void rtreedepth(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3718 UNUSED_PARAMETER(nArg
);
3719 if( sqlite3_value_type(apArg
[0])!=SQLITE_BLOB
3720 || sqlite3_value_bytes(apArg
[0])<2
3722 sqlite3_result_error(ctx
, "Invalid argument to rtreedepth()", -1);
3724 u8
*zBlob
= (u8
*)sqlite3_value_blob(apArg
[0]);
3725 sqlite3_result_int(ctx
, readInt16(zBlob
));
3730 ** Context object passed between the various routines that make up the
3731 ** implementation of integrity-check function rtreecheck().
3733 typedef struct RtreeCheck RtreeCheck
;
3735 sqlite3
*db
; /* Database handle */
3736 const char *zDb
; /* Database containing rtree table */
3737 const char *zTab
; /* Name of rtree table */
3738 int bInt
; /* True for rtree_i32 table */
3739 int nDim
; /* Number of dimensions for this rtree tbl */
3740 sqlite3_stmt
*pGetNode
; /* Statement used to retrieve nodes */
3741 sqlite3_stmt
*aCheckMapping
[2]; /* Statements to query %_parent/%_rowid */
3742 int nLeaf
; /* Number of leaf cells in table */
3743 int nNonLeaf
; /* Number of non-leaf cells in table */
3744 int rc
; /* Return code */
3745 char *zReport
; /* Message to report */
3746 int nErr
; /* Number of lines in zReport */
3749 #define RTREE_CHECK_MAX_ERROR 100
3752 ** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
3753 ** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
3755 static void rtreeCheckReset(RtreeCheck
*pCheck
, sqlite3_stmt
*pStmt
){
3756 int rc
= sqlite3_reset(pStmt
);
3757 if( pCheck
->rc
==SQLITE_OK
) pCheck
->rc
= rc
;
3761 ** The second and subsequent arguments to this function are a format string
3762 ** and printf style arguments. This function formats the string and attempts
3763 ** to compile it as an SQL statement.
3765 ** If successful, a pointer to the new SQL statement is returned. Otherwise,
3766 ** NULL is returned and an error code left in RtreeCheck.rc.
3768 static sqlite3_stmt
*rtreeCheckPrepare(
3769 RtreeCheck
*pCheck
, /* RtreeCheck object */
3770 const char *zFmt
, ... /* Format string and trailing args */
3774 sqlite3_stmt
*pRet
= 0;
3777 z
= sqlite3_vmprintf(zFmt
, ap
);
3779 if( pCheck
->rc
==SQLITE_OK
){
3781 pCheck
->rc
= SQLITE_NOMEM
;
3783 pCheck
->rc
= sqlite3_prepare_v2(pCheck
->db
, z
, -1, &pRet
, 0);
3793 ** The second and subsequent arguments to this function are a printf()
3794 ** style format string and arguments. This function formats the string and
3795 ** appends it to the report being accumuated in pCheck.
3797 static void rtreeCheckAppendMsg(RtreeCheck
*pCheck
, const char *zFmt
, ...){
3800 if( pCheck
->rc
==SQLITE_OK
&& pCheck
->nErr
<RTREE_CHECK_MAX_ERROR
){
3801 char *z
= sqlite3_vmprintf(zFmt
, ap
);
3803 pCheck
->rc
= SQLITE_NOMEM
;
3805 pCheck
->zReport
= sqlite3_mprintf("%z%s%z",
3806 pCheck
->zReport
, (pCheck
->zReport
? "\n" : ""), z
3808 if( pCheck
->zReport
==0 ){
3809 pCheck
->rc
= SQLITE_NOMEM
;
3818 ** This function is a no-op if there is already an error code stored
3819 ** in the RtreeCheck object indicated by the first argument. NULL is
3820 ** returned in this case.
3822 ** Otherwise, the contents of rtree table node iNode are loaded from
3823 ** the database and copied into a buffer obtained from sqlite3_malloc().
3824 ** If no error occurs, a pointer to the buffer is returned and (*pnNode)
3825 ** is set to the size of the buffer in bytes.
3827 ** Or, if an error does occur, NULL is returned and an error code left
3828 ** in the RtreeCheck object. The final value of *pnNode is undefined in
3831 static u8
*rtreeCheckGetNode(RtreeCheck
*pCheck
, i64 iNode
, int *pnNode
){
3832 u8
*pRet
= 0; /* Return value */
3834 assert( pCheck
->rc
==SQLITE_OK
);
3835 if( pCheck
->pGetNode
==0 ){
3836 pCheck
->pGetNode
= rtreeCheckPrepare(pCheck
,
3837 "SELECT data FROM %Q.'%q_node' WHERE nodeno=?",
3838 pCheck
->zDb
, pCheck
->zTab
3842 if( pCheck
->rc
==SQLITE_OK
){
3843 sqlite3_bind_int64(pCheck
->pGetNode
, 1, iNode
);
3844 if( sqlite3_step(pCheck
->pGetNode
)==SQLITE_ROW
){
3845 int nNode
= sqlite3_column_bytes(pCheck
->pGetNode
, 0);
3846 const u8
*pNode
= (const u8
*)sqlite3_column_blob(pCheck
->pGetNode
, 0);
3847 pRet
= sqlite3_malloc(nNode
);
3849 pCheck
->rc
= SQLITE_NOMEM
;
3851 memcpy(pRet
, pNode
, nNode
);
3855 rtreeCheckReset(pCheck
, pCheck
->pGetNode
);
3856 if( pCheck
->rc
==SQLITE_OK
&& pRet
==0 ){
3857 rtreeCheckAppendMsg(pCheck
, "Node %lld missing from database", iNode
);
3865 ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
3866 ** (if bLeaf==1) table contains a specified entry. The schemas of the
3869 ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
3870 ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
3872 ** In both cases, this function checks that there exists an entry with
3873 ** IPK value iKey and the second column set to iVal.
3876 static void rtreeCheckMapping(
3877 RtreeCheck
*pCheck
, /* RtreeCheck object */
3878 int bLeaf
, /* True for a leaf cell, false for interior */
3879 i64 iKey
, /* Key for mapping */
3880 i64 iVal
/* Expected value for mapping */
3883 sqlite3_stmt
*pStmt
;
3884 const char *azSql
[2] = {
3885 "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?",
3886 "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?"
3889 assert( bLeaf
==0 || bLeaf
==1 );
3890 if( pCheck
->aCheckMapping
[bLeaf
]==0 ){
3891 pCheck
->aCheckMapping
[bLeaf
] = rtreeCheckPrepare(pCheck
,
3892 azSql
[bLeaf
], pCheck
->zDb
, pCheck
->zTab
3895 if( pCheck
->rc
!=SQLITE_OK
) return;
3897 pStmt
= pCheck
->aCheckMapping
[bLeaf
];
3898 sqlite3_bind_int64(pStmt
, 1, iKey
);
3899 rc
= sqlite3_step(pStmt
);
3900 if( rc
==SQLITE_DONE
){
3901 rtreeCheckAppendMsg(pCheck
, "Mapping (%lld -> %lld) missing from %s table",
3902 iKey
, iVal
, (bLeaf
? "%_rowid" : "%_parent")
3904 }else if( rc
==SQLITE_ROW
){
3905 i64 ii
= sqlite3_column_int64(pStmt
, 0);
3907 rtreeCheckAppendMsg(pCheck
,
3908 "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
3909 iKey
, ii
, (bLeaf
? "%_rowid" : "%_parent"), iKey
, iVal
3913 rtreeCheckReset(pCheck
, pStmt
);
3917 ** Argument pCell points to an array of coordinates stored on an rtree page.
3918 ** This function checks that the coordinates are internally consistent (no
3919 ** x1>x2 conditions) and adds an error message to the RtreeCheck object
3922 ** Additionally, if pParent is not NULL, then it is assumed to point to
3923 ** the array of coordinates on the parent page that bound the page
3924 ** containing pCell. In this case it is also verified that the two
3925 ** sets of coordinates are mutually consistent and an error message added
3926 ** to the RtreeCheck object if they are not.
3928 static void rtreeCheckCellCoord(
3930 i64 iNode
, /* Node id to use in error messages */
3931 int iCell
, /* Cell number to use in error messages */
3932 u8
*pCell
, /* Pointer to cell coordinates */
3933 u8
*pParent
/* Pointer to parent coordinates */
3939 for(i
=0; i
<pCheck
->nDim
; i
++){
3940 readCoord(&pCell
[4*2*i
], &c1
);
3941 readCoord(&pCell
[4*(2*i
+ 1)], &c2
);
3943 /* printf("%e, %e\n", c1.u.f, c2.u.f); */
3944 if( pCheck
->bInt
? c1
.i
>c2
.i
: c1
.f
>c2
.f
){
3945 rtreeCheckAppendMsg(pCheck
,
3946 "Dimension %d of cell %d on node %lld is corrupt", i
, iCell
, iNode
3951 readCoord(&pParent
[4*2*i
], &p1
);
3952 readCoord(&pParent
[4*(2*i
+ 1)], &p2
);
3954 if( (pCheck
->bInt
? c1
.i
<p1
.i
: c1
.f
<p1
.f
)
3955 || (pCheck
->bInt
? c2
.i
>p2
.i
: c2
.f
>p2
.f
)
3957 rtreeCheckAppendMsg(pCheck
,
3958 "Dimension %d of cell %d on node %lld is corrupt relative to parent"
3967 ** Run rtreecheck() checks on node iNode, which is at depth iDepth within
3968 ** the r-tree structure. Argument aParent points to the array of coordinates
3969 ** that bound node iNode on the parent node.
3971 ** If any problems are discovered, an error message is appended to the
3972 ** report accumulated in the RtreeCheck object.
3974 static void rtreeCheckNode(
3976 int iDepth
, /* Depth of iNode (0==leaf) */
3977 u8
*aParent
, /* Buffer containing parent coords */
3978 i64 iNode
/* Node to check */
3983 assert( iNode
==1 || aParent
!=0 );
3984 assert( pCheck
->nDim
>0 );
3986 aNode
= rtreeCheckGetNode(pCheck
, iNode
, &nNode
);
3989 rtreeCheckAppendMsg(pCheck
,
3990 "Node %lld is too small (%d bytes)", iNode
, nNode
3993 int nCell
; /* Number of cells on page */
3994 int i
; /* Used to iterate through cells */
3996 iDepth
= readInt16(aNode
);
3997 if( iDepth
>RTREE_MAX_DEPTH
){
3998 rtreeCheckAppendMsg(pCheck
, "Rtree depth out of range (%d)", iDepth
);
3999 sqlite3_free(aNode
);
4003 nCell
= readInt16(&aNode
[2]);
4004 if( (4 + nCell
*(8 + pCheck
->nDim
*2*4))>nNode
){
4005 rtreeCheckAppendMsg(pCheck
,
4006 "Node %lld is too small for cell count of %d (%d bytes)",
4010 for(i
=0; i
<nCell
; i
++){
4011 u8
*pCell
= &aNode
[4 + i
*(8 + pCheck
->nDim
*2*4)];
4012 i64 iVal
= readInt64(pCell
);
4013 rtreeCheckCellCoord(pCheck
, iNode
, i
, &pCell
[8], aParent
);
4016 rtreeCheckMapping(pCheck
, 0, iVal
, iNode
);
4017 rtreeCheckNode(pCheck
, iDepth
-1, &pCell
[8], iVal
);
4020 rtreeCheckMapping(pCheck
, 1, iVal
, iNode
);
4026 sqlite3_free(aNode
);
4031 ** The second argument to this function must be either "_rowid" or
4032 ** "_parent". This function checks that the number of entries in the
4033 ** %_rowid or %_parent table is exactly nExpect. If not, it adds
4034 ** an error message to the report in the RtreeCheck object indicated
4035 ** by the first argument.
4037 static void rtreeCheckCount(RtreeCheck
*pCheck
, const char *zTbl
, i64 nExpect
){
4038 if( pCheck
->rc
==SQLITE_OK
){
4039 sqlite3_stmt
*pCount
;
4040 pCount
= rtreeCheckPrepare(pCheck
, "SELECT count(*) FROM %Q.'%q%s'",
4041 pCheck
->zDb
, pCheck
->zTab
, zTbl
4044 if( sqlite3_step(pCount
)==SQLITE_ROW
){
4045 i64 nActual
= sqlite3_column_int64(pCount
, 0);
4046 if( nActual
!=nExpect
){
4047 rtreeCheckAppendMsg(pCheck
, "Wrong number of entries in %%%s table"
4048 " - expected %lld, actual %lld" , zTbl
, nExpect
, nActual
4052 pCheck
->rc
= sqlite3_finalize(pCount
);
4058 ** This function does the bulk of the work for the rtree integrity-check.
4059 ** It is called by rtreecheck(), which is the SQL function implementation.
4061 static int rtreeCheckTable(
4062 sqlite3
*db
, /* Database handle to access db through */
4063 const char *zDb
, /* Name of db ("main", "temp" etc.) */
4064 const char *zTab
, /* Name of rtree table to check */
4065 char **pzReport
/* OUT: sqlite3_malloc'd report text */
4067 RtreeCheck check
; /* Common context for various routines */
4068 sqlite3_stmt
*pStmt
= 0; /* Used to find column count of rtree table */
4069 int bEnd
= 0; /* True if transaction should be closed */
4071 /* Initialize the context object */
4072 memset(&check
, 0, sizeof(check
));
4077 /* If there is not already an open transaction, open one now. This is
4078 ** to ensure that the queries run as part of this integrity-check operate
4079 ** on a consistent snapshot. */
4080 if( sqlite3_get_autocommit(db
) ){
4081 check
.rc
= sqlite3_exec(db
, "BEGIN", 0, 0, 0);
4085 /* Find number of dimensions in the rtree table. */
4086 pStmt
= rtreeCheckPrepare(&check
, "SELECT * FROM %Q.%Q", zDb
, zTab
);
4089 check
.nDim
= (sqlite3_column_count(pStmt
) - 1) / 2;
4091 rtreeCheckAppendMsg(&check
, "Schema corrupt or not an rtree");
4092 }else if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
4093 check
.bInt
= (sqlite3_column_type(pStmt
, 1)==SQLITE_INTEGER
);
4095 rc
= sqlite3_finalize(pStmt
);
4096 if( rc
!=SQLITE_CORRUPT
) check
.rc
= rc
;
4099 /* Do the actual integrity-check */
4100 if( check
.nDim
>=1 ){
4101 if( check
.rc
==SQLITE_OK
){
4102 rtreeCheckNode(&check
, 0, 0, 1);
4104 rtreeCheckCount(&check
, "_rowid", check
.nLeaf
);
4105 rtreeCheckCount(&check
, "_parent", check
.nNonLeaf
);
4108 /* Finalize SQL statements used by the integrity-check */
4109 sqlite3_finalize(check
.pGetNode
);
4110 sqlite3_finalize(check
.aCheckMapping
[0]);
4111 sqlite3_finalize(check
.aCheckMapping
[1]);
4113 /* If one was opened, close the transaction */
4115 int rc
= sqlite3_exec(db
, "END", 0, 0, 0);
4116 if( check
.rc
==SQLITE_OK
) check
.rc
= rc
;
4118 *pzReport
= check
.zReport
;
4125 ** rtreecheck(<rtree-table>);
4126 ** rtreecheck(<database>, <rtree-table>);
4128 ** Invoking this SQL function runs an integrity-check on the named rtree
4129 ** table. The integrity-check verifies the following:
4131 ** 1. For each cell in the r-tree structure (%_node table), that:
4133 ** a) for each dimension, (coord1 <= coord2).
4135 ** b) unless the cell is on the root node, that the cell is bounded
4136 ** by the parent cell on the parent node.
4138 ** c) for leaf nodes, that there is an entry in the %_rowid
4139 ** table corresponding to the cell's rowid value that
4140 ** points to the correct node.
4142 ** d) for cells on non-leaf nodes, that there is an entry in the
4143 ** %_parent table mapping from the cell's child node to the
4144 ** node that it resides on.
4146 ** 2. That there are the same number of entries in the %_rowid table
4147 ** as there are leaf cells in the r-tree structure, and that there
4148 ** is a leaf cell that corresponds to each entry in the %_rowid table.
4150 ** 3. That there are the same number of entries in the %_parent table
4151 ** as there are non-leaf cells in the r-tree structure, and that
4152 ** there is a non-leaf cell that corresponds to each entry in the
4155 static void rtreecheck(
4156 sqlite3_context
*ctx
,
4158 sqlite3_value
**apArg
4160 if( nArg
!=1 && nArg
!=2 ){
4161 sqlite3_result_error(ctx
,
4162 "wrong number of arguments to function rtreecheck()", -1
4167 const char *zDb
= (const char*)sqlite3_value_text(apArg
[0]);
4173 zTab
= (const char*)sqlite3_value_text(apArg
[1]);
4175 rc
= rtreeCheckTable(sqlite3_context_db_handle(ctx
), zDb
, zTab
, &zReport
);
4176 if( rc
==SQLITE_OK
){
4177 sqlite3_result_text(ctx
, zReport
? zReport
: "ok", -1, SQLITE_TRANSIENT
);
4179 sqlite3_result_error_code(ctx
, rc
);
4181 sqlite3_free(zReport
);
4187 ** Register the r-tree module with database handle db. This creates the
4188 ** virtual table module "rtree" and the debugging/analysis scalar
4189 ** function "rtreenode".
4191 int sqlite3RtreeInit(sqlite3
*db
){
4192 const int utf8
= SQLITE_UTF8
;
4195 rc
= sqlite3_create_function(db
, "rtreenode", 2, utf8
, 0, rtreenode
, 0, 0);
4196 if( rc
==SQLITE_OK
){
4197 rc
= sqlite3_create_function(db
, "rtreedepth", 1, utf8
, 0,rtreedepth
, 0, 0);
4199 if( rc
==SQLITE_OK
){
4200 rc
= sqlite3_create_function(db
, "rtreecheck", -1, utf8
, 0,rtreecheck
, 0,0);
4202 if( rc
==SQLITE_OK
){
4203 #ifdef SQLITE_RTREE_INT_ONLY
4204 void *c
= (void *)RTREE_COORD_INT32
;
4206 void *c
= (void *)RTREE_COORD_REAL32
;
4208 rc
= sqlite3_create_module_v2(db
, "rtree", &rtreeModule
, c
, 0);
4210 if( rc
==SQLITE_OK
){
4211 void *c
= (void *)RTREE_COORD_INT32
;
4212 rc
= sqlite3_create_module_v2(db
, "rtree_i32", &rtreeModule
, c
, 0);
4219 ** This routine deletes the RtreeGeomCallback object that was attached
4220 ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
4221 ** or sqlite3_rtree_query_callback(). In other words, this routine is the
4222 ** destructor for an RtreeGeomCallback objecct. This routine is called when
4223 ** the corresponding SQL function is deleted.
4225 static void rtreeFreeCallback(void *p
){
4226 RtreeGeomCallback
*pInfo
= (RtreeGeomCallback
*)p
;
4227 if( pInfo
->xDestructor
) pInfo
->xDestructor(pInfo
->pContext
);
4232 ** This routine frees the BLOB that is returned by geomCallback().
4234 static void rtreeMatchArgFree(void *pArg
){
4236 RtreeMatchArg
*p
= (RtreeMatchArg
*)pArg
;
4237 for(i
=0; i
<p
->nParam
; i
++){
4238 sqlite3_value_free(p
->apSqlParam
[i
]);
4244 ** Each call to sqlite3_rtree_geometry_callback() or
4245 ** sqlite3_rtree_query_callback() creates an ordinary SQLite
4246 ** scalar function that is implemented by this routine.
4248 ** All this function does is construct an RtreeMatchArg object that
4249 ** contains the geometry-checking callback routines and a list of
4250 ** parameters to this function, then return that RtreeMatchArg object
4253 ** The R-Tree MATCH operator will read the returned BLOB, deserialize
4254 ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
4255 ** out which elements of the R-Tree should be returned by the query.
4257 static void geomCallback(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**aArg
){
4258 RtreeGeomCallback
*pGeomCtx
= (RtreeGeomCallback
*)sqlite3_user_data(ctx
);
4259 RtreeMatchArg
*pBlob
;
4263 nBlob
= sizeof(RtreeMatchArg
) + (nArg
-1)*sizeof(RtreeDValue
)
4264 + nArg
*sizeof(sqlite3_value
*);
4265 pBlob
= (RtreeMatchArg
*)sqlite3_malloc(nBlob
);
4267 sqlite3_result_error_nomem(ctx
);
4270 pBlob
->iSize
= nBlob
;
4271 pBlob
->cb
= pGeomCtx
[0];
4272 pBlob
->apSqlParam
= (sqlite3_value
**)&pBlob
->aParam
[nArg
];
4273 pBlob
->nParam
= nArg
;
4274 for(i
=0; i
<nArg
; i
++){
4275 pBlob
->apSqlParam
[i
] = sqlite3_value_dup(aArg
[i
]);
4276 if( pBlob
->apSqlParam
[i
]==0 ) memErr
= 1;
4277 #ifdef SQLITE_RTREE_INT_ONLY
4278 pBlob
->aParam
[i
] = sqlite3_value_int64(aArg
[i
]);
4280 pBlob
->aParam
[i
] = sqlite3_value_double(aArg
[i
]);
4284 sqlite3_result_error_nomem(ctx
);
4285 rtreeMatchArgFree(pBlob
);
4287 sqlite3_result_pointer(ctx
, pBlob
, "RtreeMatchArg", rtreeMatchArgFree
);
4293 ** Register a new geometry function for use with the r-tree MATCH operator.
4295 int sqlite3_rtree_geometry_callback(
4296 sqlite3
*db
, /* Register SQL function on this connection */
4297 const char *zGeom
, /* Name of the new SQL function */
4298 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*), /* Callback */
4299 void *pContext
/* Extra data associated with the callback */
4301 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4303 /* Allocate and populate the context object. */
4304 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4305 if( !pGeomCtx
) return SQLITE_NOMEM
;
4306 pGeomCtx
->xGeom
= xGeom
;
4307 pGeomCtx
->xQueryFunc
= 0;
4308 pGeomCtx
->xDestructor
= 0;
4309 pGeomCtx
->pContext
= pContext
;
4310 return sqlite3_create_function_v2(db
, zGeom
, -1, SQLITE_ANY
,
4311 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4316 ** Register a new 2nd-generation geometry function for use with the
4317 ** r-tree MATCH operator.
4319 int sqlite3_rtree_query_callback(
4320 sqlite3
*db
, /* Register SQL function on this connection */
4321 const char *zQueryFunc
, /* Name of new SQL function */
4322 int (*xQueryFunc
)(sqlite3_rtree_query_info
*), /* Callback */
4323 void *pContext
, /* Extra data passed into the callback */
4324 void (*xDestructor
)(void*) /* Destructor for the extra data */
4326 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4328 /* Allocate and populate the context object. */
4329 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4330 if( !pGeomCtx
) return SQLITE_NOMEM
;
4331 pGeomCtx
->xGeom
= 0;
4332 pGeomCtx
->xQueryFunc
= xQueryFunc
;
4333 pGeomCtx
->xDestructor
= xDestructor
;
4334 pGeomCtx
->pContext
= pContext
;
4335 return sqlite3_create_function_v2(db
, zQueryFunc
, -1, SQLITE_ANY
,
4336 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4342 __declspec(dllexport
)
4344 int sqlite3_rtree_init(
4347 const sqlite3_api_routines
*pApi
4349 SQLITE_EXTENSION_INIT2(pApi
)
4350 return sqlite3RtreeInit(db
);