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) || defined(SQLITE_ENABLE_RTREE)
58 #include "sqlite3ext.h"
59 SQLITE_EXTENSION_INIT1
68 #ifndef SQLITE_AMALGAMATION
69 #include "sqlite3rtree.h"
70 typedef sqlite3_int64 i64
;
71 typedef sqlite3_uint64 u64
;
72 typedef unsigned char u8
;
73 typedef unsigned short u16
;
74 typedef unsigned int u32
;
77 /* The following macro is used to suppress compiler warnings.
79 #ifndef UNUSED_PARAMETER
80 # define UNUSED_PARAMETER(x) (void)(x)
83 typedef struct Rtree Rtree
;
84 typedef struct RtreeCursor RtreeCursor
;
85 typedef struct RtreeNode RtreeNode
;
86 typedef struct RtreeCell RtreeCell
;
87 typedef struct RtreeConstraint RtreeConstraint
;
88 typedef struct RtreeMatchArg RtreeMatchArg
;
89 typedef struct RtreeGeomCallback RtreeGeomCallback
;
90 typedef union RtreeCoord RtreeCoord
;
91 typedef struct RtreeSearchPoint RtreeSearchPoint
;
93 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
94 #define RTREE_MAX_DIMENSIONS 5
96 /* Size of hash table Rtree.aHash. This hash table is not expected to
97 ** ever contain very many entries, so a fixed number of buckets is
102 /* The xBestIndex method of this virtual table requires an estimate of
103 ** the number of rows in the virtual table to calculate the costs of
104 ** various strategies. If possible, this estimate is loaded from the
105 ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
106 ** Otherwise, if no sqlite_stat1 entry is available, use
107 ** RTREE_DEFAULT_ROWEST.
109 #define RTREE_DEFAULT_ROWEST 1048576
110 #define RTREE_MIN_ROWEST 100
113 ** An rtree virtual-table object.
116 sqlite3_vtab base
; /* Base class. Must be first */
117 sqlite3
*db
; /* Host database connection */
118 int iNodeSize
; /* Size in bytes of each node in the node table */
119 u8 nDim
; /* Number of dimensions */
120 u8 nDim2
; /* Twice the number of dimensions */
121 u8 eCoordType
; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
122 u8 nBytesPerCell
; /* Bytes consumed per cell */
123 u8 inWrTrans
; /* True if inside write transaction */
124 int iDepth
; /* Current depth of the r-tree structure */
125 char *zDb
; /* Name of database containing r-tree table */
126 char *zName
; /* Name of r-tree table */
127 u32 nBusy
; /* Current number of users of this structure */
128 i64 nRowEst
; /* Estimated number of rows in this table */
129 u32 nCursor
; /* Number of open cursors */
131 /* List of nodes removed during a CondenseTree operation. List is
132 ** linked together via the pointer normally used for hash chains -
133 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
134 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
137 int iReinsertHeight
; /* Height of sub-trees Reinsert() has run on */
139 /* Blob I/O on xxx_node */
140 sqlite3_blob
*pNodeBlob
;
142 /* Statements to read/write/delete a record from xxx_node */
143 sqlite3_stmt
*pWriteNode
;
144 sqlite3_stmt
*pDeleteNode
;
146 /* Statements to read/write/delete a record from xxx_rowid */
147 sqlite3_stmt
*pReadRowid
;
148 sqlite3_stmt
*pWriteRowid
;
149 sqlite3_stmt
*pDeleteRowid
;
151 /* Statements to read/write/delete a record from xxx_parent */
152 sqlite3_stmt
*pReadParent
;
153 sqlite3_stmt
*pWriteParent
;
154 sqlite3_stmt
*pDeleteParent
;
156 RtreeNode
*aHash
[HASHSIZE
]; /* Hash table of in-memory nodes. */
159 /* Possible values for Rtree.eCoordType: */
160 #define RTREE_COORD_REAL32 0
161 #define RTREE_COORD_INT32 1
164 ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
165 ** only deal with integer coordinates. No floating point operations
168 #ifdef SQLITE_RTREE_INT_ONLY
169 typedef sqlite3_int64 RtreeDValue
; /* High accuracy coordinate */
170 typedef int RtreeValue
; /* Low accuracy coordinate */
171 # define RTREE_ZERO 0
173 typedef double RtreeDValue
; /* High accuracy coordinate */
174 typedef float RtreeValue
; /* Low accuracy coordinate */
175 # define RTREE_ZERO 0.0
179 ** When doing a search of an r-tree, instances of the following structure
180 ** record intermediate results from the tree walk.
182 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
183 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
184 ** the id is of the parent node and the cell that RtreeSearchPoint
185 ** represents is the iCell-th entry in the parent node.
187 struct RtreeSearchPoint
{
188 RtreeDValue rScore
; /* The score for this node. Smallest goes first. */
189 sqlite3_int64 id
; /* Node ID */
190 u8 iLevel
; /* 0=entries. 1=leaf node. 2+ for higher */
191 u8 eWithin
; /* PARTLY_WITHIN or FULLY_WITHIN */
192 u8 iCell
; /* Cell index within the node */
196 ** The minimum number of cells allowed for a node is a third of the
197 ** maximum. In Gutman's notation:
201 ** If an R*-tree "Reinsert" operation is required, the same number of
202 ** cells are removed from the overfull node and reinserted into the tree.
204 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
205 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
206 #define RTREE_MAXCELLS 51
209 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
210 ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
211 ** Therefore all non-root nodes must contain at least 3 entries. Since
212 ** 3^40 is greater than 2^64, an r-tree structure always has a depth of
215 #define RTREE_MAX_DEPTH 40
219 ** Number of entries in the cursor RtreeNode cache. The first entry is
220 ** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining
221 ** entries cache the RtreeNode for the first elements of the priority queue.
223 #define RTREE_CACHE_SZ 5
226 ** An rtree cursor object.
229 sqlite3_vtab_cursor base
; /* Base class. Must be first */
230 u8 atEOF
; /* True if at end of search */
231 u8 bPoint
; /* True if sPoint is valid */
232 int iStrategy
; /* Copy of idxNum search parameter */
233 int nConstraint
; /* Number of entries in aConstraint */
234 RtreeConstraint
*aConstraint
; /* Search constraints. */
235 int nPointAlloc
; /* Number of slots allocated for aPoint[] */
236 int nPoint
; /* Number of slots used in aPoint[] */
237 int mxLevel
; /* iLevel value for root of the tree */
238 RtreeSearchPoint
*aPoint
; /* Priority queue for search points */
239 RtreeSearchPoint sPoint
; /* Cached next search point */
240 RtreeNode
*aNode
[RTREE_CACHE_SZ
]; /* Rtree node cache */
241 u32 anQueue
[RTREE_MAX_DEPTH
+1]; /* Number of queued entries by iLevel */
244 /* Return the Rtree of a RtreeCursor */
245 #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab))
248 ** A coordinate can be either a floating point number or a integer. All
249 ** coordinates within a single R-Tree are always of the same time.
252 RtreeValue f
; /* Floating point value */
253 int i
; /* Integer value */
254 u32 u
; /* Unsigned for byte-order conversions */
258 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
259 ** formatted as a RtreeDValue (double or int64). This macro assumes that local
260 ** variable pRtree points to the Rtree structure associated with the
263 #ifdef SQLITE_RTREE_INT_ONLY
264 # define DCOORD(coord) ((RtreeDValue)coord.i)
266 # define DCOORD(coord) ( \
267 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
268 ((double)coord.f) : \
274 ** A search constraint.
276 struct RtreeConstraint
{
277 int iCoord
; /* Index of constrained coordinate */
278 int op
; /* Constraining operation */
280 RtreeDValue rValue
; /* Constraint value. */
281 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*);
282 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
284 sqlite3_rtree_query_info
*pInfo
; /* xGeom and xQueryFunc argument */
287 /* Possible values for RtreeConstraint.op */
288 #define RTREE_EQ 0x41 /* A */
289 #define RTREE_LE 0x42 /* B */
290 #define RTREE_LT 0x43 /* C */
291 #define RTREE_GE 0x44 /* D */
292 #define RTREE_GT 0x45 /* E */
293 #define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */
294 #define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */
298 ** An rtree structure node.
301 RtreeNode
*pParent
; /* Parent node */
302 i64 iNode
; /* The node number */
303 int nRef
; /* Number of references to this node */
304 int isDirty
; /* True if the node needs to be written to disk */
305 u8
*zData
; /* Content of the node, as should be on disk */
306 RtreeNode
*pNext
; /* Next node in this hash collision chain */
309 /* Return the number of cells in a node */
310 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
313 ** A single cell from a node, deserialized
316 i64 iRowid
; /* Node or entry ID */
317 RtreeCoord aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Bounding box coordinates */
322 ** This object becomes the sqlite3_user_data() for the SQL functions
323 ** that are created by sqlite3_rtree_geometry_callback() and
324 ** sqlite3_rtree_query_callback() and which appear on the right of MATCH
325 ** operators in order to constrain a search.
327 ** xGeom and xQueryFunc are the callback functions. Exactly one of
328 ** xGeom and xQueryFunc fields is non-NULL, depending on whether the
329 ** SQL function was created using sqlite3_rtree_geometry_callback() or
330 ** sqlite3_rtree_query_callback().
332 ** This object is deleted automatically by the destructor mechanism in
333 ** sqlite3_create_function_v2().
335 struct RtreeGeomCallback
{
336 int (*xGeom
)(sqlite3_rtree_geometry
*, int, RtreeDValue
*, int*);
337 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
338 void (*xDestructor
)(void*);
343 ** An instance of this structure (in the form of a BLOB) is returned by
344 ** the SQL functions that sqlite3_rtree_geometry_callback() and
345 ** sqlite3_rtree_query_callback() create, and is read as the right-hand
346 ** operand to the MATCH operator of an R-Tree.
348 struct RtreeMatchArg
{
349 u32 iSize
; /* Size of this object */
350 RtreeGeomCallback cb
; /* Info about the callback functions */
351 int nParam
; /* Number of parameters to the SQL function */
352 sqlite3_value
**apSqlParam
; /* Original SQL parameter values */
353 RtreeDValue aParam
[1]; /* Values for parameters to the SQL function */
357 # define MAX(x,y) ((x) < (y) ? (y) : (x))
360 # define MIN(x,y) ((x) > (y) ? (y) : (x))
363 /* What version of GCC is being used. 0 means GCC is not being used .
364 ** Note that the GCC_VERSION macro will also be set correctly when using
365 ** clang, since clang works hard to be gcc compatible. So the gcc
366 ** optimizations will also work when compiling with clang.
369 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
370 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
372 # define GCC_VERSION 0
376 /* The testcase() macro should already be defined in the amalgamation. If
377 ** it is not, make it a no-op.
379 #ifndef SQLITE_AMALGAMATION
384 ** Macros to determine whether the machine is big or little endian,
385 ** and whether or not that determination is run-time or compile-time.
387 ** For best performance, an attempt is made to guess at the byte-order
388 ** using C-preprocessor macros. If that is unsuccessful, or if
389 ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined
392 #ifndef SQLITE_BYTEORDER
393 #if defined(i386) || defined(__i386__) || defined(_M_IX86) || \
394 defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \
395 defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \
397 # define SQLITE_BYTEORDER 1234
398 #elif defined(sparc) || defined(__ppc__)
399 # define SQLITE_BYTEORDER 4321
401 # define SQLITE_BYTEORDER 0 /* 0 means "unknown at compile-time" */
406 /* What version of MSVC is being used. 0 means MSVC is not being used */
408 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
409 # define MSVC_VERSION _MSC_VER
411 # define MSVC_VERSION 0
416 ** Functions to deserialize a 16 bit integer, 32 bit real number and
417 ** 64 bit integer. The deserialized value is returned.
419 static int readInt16(u8
*p
){
420 return (p
[0]<<8) + p
[1];
422 static void readCoord(u8
*p
, RtreeCoord
*pCoord
){
423 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
424 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
425 pCoord
->u
= _byteswap_ulong(*(u32
*)p
);
426 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
427 pCoord
->u
= __builtin_bswap32(*(u32
*)p
);
428 #elif SQLITE_BYTEORDER==4321
429 pCoord
->u
= *(u32
*)p
;
432 (((u32
)p
[0]) << 24) +
433 (((u32
)p
[1]) << 16) +
439 static i64
readInt64(u8
*p
){
440 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
443 return (i64
)_byteswap_uint64(x
);
444 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
447 return (i64
)__builtin_bswap64(x
);
448 #elif SQLITE_BYTEORDER==4321
454 (((u64
)p
[0]) << 56) +
455 (((u64
)p
[1]) << 48) +
456 (((u64
)p
[2]) << 40) +
457 (((u64
)p
[3]) << 32) +
458 (((u64
)p
[4]) << 24) +
459 (((u64
)p
[5]) << 16) +
467 ** Functions to serialize a 16 bit integer, 32 bit real number and
468 ** 64 bit integer. The value returned is the number of bytes written
469 ** to the argument buffer (always 2, 4 and 8 respectively).
471 static void writeInt16(u8
*p
, int i
){
475 static int writeCoord(u8
*p
, RtreeCoord
*pCoord
){
477 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
478 assert( sizeof(RtreeCoord
)==4 );
479 assert( sizeof(u32
)==4 );
480 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
481 i
= __builtin_bswap32(pCoord
->u
);
483 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
484 i
= _byteswap_ulong(pCoord
->u
);
486 #elif SQLITE_BYTEORDER==4321
498 static int writeInt64(u8
*p
, i64 i
){
499 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
500 i
= (i64
)__builtin_bswap64((u64
)i
);
502 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
503 i
= (i64
)_byteswap_uint64((u64
)i
);
505 #elif SQLITE_BYTEORDER==4321
521 ** Increment the reference count of node p.
523 static void nodeReference(RtreeNode
*p
){
530 ** Clear the content of node p (set all bytes to 0x00).
532 static void nodeZero(Rtree
*pRtree
, RtreeNode
*p
){
533 memset(&p
->zData
[2], 0, pRtree
->iNodeSize
-2);
538 ** Given a node number iNode, return the corresponding key to use
539 ** in the Rtree.aHash table.
541 static int nodeHash(i64 iNode
){
542 return iNode
% HASHSIZE
;
546 ** Search the node hash table for node iNode. If found, return a pointer
547 ** to it. Otherwise, return 0.
549 static RtreeNode
*nodeHashLookup(Rtree
*pRtree
, i64 iNode
){
551 for(p
=pRtree
->aHash
[nodeHash(iNode
)]; p
&& p
->iNode
!=iNode
; p
=p
->pNext
);
556 ** Add node pNode to the node hash table.
558 static void nodeHashInsert(Rtree
*pRtree
, RtreeNode
*pNode
){
560 assert( pNode
->pNext
==0 );
561 iHash
= nodeHash(pNode
->iNode
);
562 pNode
->pNext
= pRtree
->aHash
[iHash
];
563 pRtree
->aHash
[iHash
] = pNode
;
567 ** Remove node pNode from the node hash table.
569 static void nodeHashDelete(Rtree
*pRtree
, RtreeNode
*pNode
){
571 if( pNode
->iNode
!=0 ){
572 pp
= &pRtree
->aHash
[nodeHash(pNode
->iNode
)];
573 for( ; (*pp
)!=pNode
; pp
= &(*pp
)->pNext
){ assert(*pp
); }
580 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
581 ** indicating that node has not yet been assigned a node number. It is
582 ** assigned a node number when nodeWrite() is called to write the
583 ** node contents out to the database.
585 static RtreeNode
*nodeNew(Rtree
*pRtree
, RtreeNode
*pParent
){
587 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
) + pRtree
->iNodeSize
);
589 memset(pNode
, 0, sizeof(RtreeNode
) + pRtree
->iNodeSize
);
590 pNode
->zData
= (u8
*)&pNode
[1];
592 pNode
->pParent
= pParent
;
594 nodeReference(pParent
);
600 ** Clear the Rtree.pNodeBlob object
602 static void nodeBlobReset(Rtree
*pRtree
){
603 if( pRtree
->pNodeBlob
&& pRtree
->inWrTrans
==0 && pRtree
->nCursor
==0 ){
604 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
605 pRtree
->pNodeBlob
= 0;
606 sqlite3_blob_close(pBlob
);
611 ** Obtain a reference to an r-tree node.
613 static int nodeAcquire(
614 Rtree
*pRtree
, /* R-tree structure */
615 i64 iNode
, /* Node number to load */
616 RtreeNode
*pParent
, /* Either the parent node or NULL */
617 RtreeNode
**ppNode
/* OUT: Acquired node */
620 RtreeNode
*pNode
= 0;
622 /* Check if the requested node is already in the hash table. If so,
623 ** increase its reference count and return it.
625 if( (pNode
= nodeHashLookup(pRtree
, iNode
)) ){
626 assert( !pParent
|| !pNode
->pParent
|| pNode
->pParent
==pParent
);
627 if( pParent
&& !pNode
->pParent
){
628 nodeReference(pParent
);
629 pNode
->pParent
= pParent
;
636 if( pRtree
->pNodeBlob
){
637 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
638 pRtree
->pNodeBlob
= 0;
639 rc
= sqlite3_blob_reopen(pBlob
, iNode
);
640 pRtree
->pNodeBlob
= pBlob
;
642 nodeBlobReset(pRtree
);
643 if( rc
==SQLITE_NOMEM
) return SQLITE_NOMEM
;
646 if( pRtree
->pNodeBlob
==0 ){
647 char *zTab
= sqlite3_mprintf("%s_node", pRtree
->zName
);
648 if( zTab
==0 ) return SQLITE_NOMEM
;
649 rc
= sqlite3_blob_open(pRtree
->db
, pRtree
->zDb
, zTab
, "data", iNode
, 0,
654 nodeBlobReset(pRtree
);
656 /* If unable to open an sqlite3_blob on the desired row, that can only
657 ** be because the shadow tables hold erroneous data. */
658 if( rc
==SQLITE_ERROR
) rc
= SQLITE_CORRUPT_VTAB
;
659 }else if( pRtree
->iNodeSize
==sqlite3_blob_bytes(pRtree
->pNodeBlob
) ){
660 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
)+pRtree
->iNodeSize
);
664 pNode
->pParent
= pParent
;
665 pNode
->zData
= (u8
*)&pNode
[1];
667 pNode
->iNode
= iNode
;
670 rc
= sqlite3_blob_read(pRtree
->pNodeBlob
, pNode
->zData
,
671 pRtree
->iNodeSize
, 0);
672 nodeReference(pParent
);
676 /* If the root node was just loaded, set pRtree->iDepth to the height
677 ** of the r-tree structure. A height of zero means all data is stored on
678 ** the root node. A height of one means the children of the root node
679 ** are the leaves, and so on. If the depth as specified on the root node
680 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
682 if( pNode
&& iNode
==1 ){
683 pRtree
->iDepth
= readInt16(pNode
->zData
);
684 if( pRtree
->iDepth
>RTREE_MAX_DEPTH
){
685 rc
= SQLITE_CORRUPT_VTAB
;
689 /* If no error has occurred so far, check if the "number of entries"
690 ** field on the node is too large. If so, set the return code to
691 ** SQLITE_CORRUPT_VTAB.
693 if( pNode
&& rc
==SQLITE_OK
){
694 if( NCELL(pNode
)>((pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
) ){
695 rc
= SQLITE_CORRUPT_VTAB
;
701 nodeHashInsert(pRtree
, pNode
);
703 rc
= SQLITE_CORRUPT_VTAB
;
715 ** Overwrite cell iCell of node pNode with the contents of pCell.
717 static void nodeOverwriteCell(
718 Rtree
*pRtree
, /* The overall R-Tree */
719 RtreeNode
*pNode
, /* The node into which the cell is to be written */
720 RtreeCell
*pCell
, /* The cell to write */
721 int iCell
/* Index into pNode into which pCell is written */
724 u8
*p
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
725 p
+= writeInt64(p
, pCell
->iRowid
);
726 for(ii
=0; ii
<pRtree
->nDim2
; ii
++){
727 p
+= writeCoord(p
, &pCell
->aCoord
[ii
]);
733 ** Remove the cell with index iCell from node pNode.
735 static void nodeDeleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
){
736 u8
*pDst
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
737 u8
*pSrc
= &pDst
[pRtree
->nBytesPerCell
];
738 int nByte
= (NCELL(pNode
) - iCell
- 1) * pRtree
->nBytesPerCell
;
739 memmove(pDst
, pSrc
, nByte
);
740 writeInt16(&pNode
->zData
[2], NCELL(pNode
)-1);
745 ** Insert the contents of cell pCell into node pNode. If the insert
746 ** is successful, return SQLITE_OK.
748 ** If there is not enough free space in pNode, return SQLITE_FULL.
750 static int nodeInsertCell(
751 Rtree
*pRtree
, /* The overall R-Tree */
752 RtreeNode
*pNode
, /* Write new cell into this node */
753 RtreeCell
*pCell
/* The cell to be inserted */
755 int nCell
; /* Current number of cells in pNode */
756 int nMaxCell
; /* Maximum number of cells for pNode */
758 nMaxCell
= (pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
;
759 nCell
= NCELL(pNode
);
761 assert( nCell
<=nMaxCell
);
762 if( nCell
<nMaxCell
){
763 nodeOverwriteCell(pRtree
, pNode
, pCell
, nCell
);
764 writeInt16(&pNode
->zData
[2], nCell
+1);
768 return (nCell
==nMaxCell
);
772 ** If the node is dirty, write it out to the database.
774 static int nodeWrite(Rtree
*pRtree
, RtreeNode
*pNode
){
776 if( pNode
->isDirty
){
777 sqlite3_stmt
*p
= pRtree
->pWriteNode
;
779 sqlite3_bind_int64(p
, 1, pNode
->iNode
);
781 sqlite3_bind_null(p
, 1);
783 sqlite3_bind_blob(p
, 2, pNode
->zData
, pRtree
->iNodeSize
, SQLITE_STATIC
);
786 rc
= sqlite3_reset(p
);
787 if( pNode
->iNode
==0 && rc
==SQLITE_OK
){
788 pNode
->iNode
= sqlite3_last_insert_rowid(pRtree
->db
);
789 nodeHashInsert(pRtree
, pNode
);
796 ** Release a reference to a node. If the node is dirty and the reference
797 ** count drops to zero, the node data is written to the database.
799 static int nodeRelease(Rtree
*pRtree
, RtreeNode
*pNode
){
802 assert( pNode
->nRef
>0 );
804 if( pNode
->nRef
==0 ){
805 if( pNode
->iNode
==1 ){
808 if( pNode
->pParent
){
809 rc
= nodeRelease(pRtree
, pNode
->pParent
);
812 rc
= nodeWrite(pRtree
, pNode
);
814 nodeHashDelete(pRtree
, pNode
);
822 ** Return the 64-bit integer value associated with cell iCell of
823 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
824 ** an internal node, then the 64-bit integer is a child page number.
826 static i64
nodeGetRowid(
827 Rtree
*pRtree
, /* The overall R-Tree */
828 RtreeNode
*pNode
, /* The node from which to extract the ID */
829 int iCell
/* The cell index from which to extract the ID */
831 assert( iCell
<NCELL(pNode
) );
832 return readInt64(&pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
]);
836 ** Return coordinate iCoord from cell iCell in node pNode.
838 static void nodeGetCoord(
839 Rtree
*pRtree
, /* The overall R-Tree */
840 RtreeNode
*pNode
, /* The node from which to extract a coordinate */
841 int iCell
, /* The index of the cell within the node */
842 int iCoord
, /* Which coordinate to extract */
843 RtreeCoord
*pCoord
/* OUT: Space to write result to */
845 readCoord(&pNode
->zData
[12 + pRtree
->nBytesPerCell
*iCell
+ 4*iCoord
], pCoord
);
849 ** Deserialize cell iCell of node pNode. Populate the structure pointed
850 ** to by pCell with the results.
852 static void nodeGetCell(
853 Rtree
*pRtree
, /* The overall R-Tree */
854 RtreeNode
*pNode
, /* The node containing the cell to be read */
855 int iCell
, /* Index of the cell within the node */
856 RtreeCell
*pCell
/* OUT: Write the cell contents here */
861 pCell
->iRowid
= nodeGetRowid(pRtree
, pNode
, iCell
);
862 pData
= pNode
->zData
+ (12 + pRtree
->nBytesPerCell
*iCell
);
863 pCoord
= pCell
->aCoord
;
865 readCoord(pData
, &pCoord
[ii
]);
866 readCoord(pData
+4, &pCoord
[ii
+1]);
869 }while( ii
<pRtree
->nDim2
);
873 /* Forward declaration for the function that does the work of
874 ** the virtual table module xCreate() and xConnect() methods.
876 static int rtreeInit(
877 sqlite3
*, void *, int, const char *const*, sqlite3_vtab
**, char **, int
881 ** Rtree virtual table module xCreate method.
883 static int rtreeCreate(
886 int argc
, const char *const*argv
,
887 sqlite3_vtab
**ppVtab
,
890 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 1);
894 ** Rtree virtual table module xConnect method.
896 static int rtreeConnect(
899 int argc
, const char *const*argv
,
900 sqlite3_vtab
**ppVtab
,
903 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 0);
907 ** Increment the r-tree reference count.
909 static void rtreeReference(Rtree
*pRtree
){
914 ** Decrement the r-tree reference count. When the reference count reaches
915 ** zero the structure is deleted.
917 static void rtreeRelease(Rtree
*pRtree
){
919 if( pRtree
->nBusy
==0 ){
920 pRtree
->inWrTrans
= 0;
922 nodeBlobReset(pRtree
);
923 sqlite3_finalize(pRtree
->pWriteNode
);
924 sqlite3_finalize(pRtree
->pDeleteNode
);
925 sqlite3_finalize(pRtree
->pReadRowid
);
926 sqlite3_finalize(pRtree
->pWriteRowid
);
927 sqlite3_finalize(pRtree
->pDeleteRowid
);
928 sqlite3_finalize(pRtree
->pReadParent
);
929 sqlite3_finalize(pRtree
->pWriteParent
);
930 sqlite3_finalize(pRtree
->pDeleteParent
);
931 sqlite3_free(pRtree
);
936 ** Rtree virtual table module xDisconnect method.
938 static int rtreeDisconnect(sqlite3_vtab
*pVtab
){
939 rtreeRelease((Rtree
*)pVtab
);
944 ** Rtree virtual table module xDestroy method.
946 static int rtreeDestroy(sqlite3_vtab
*pVtab
){
947 Rtree
*pRtree
= (Rtree
*)pVtab
;
949 char *zCreate
= sqlite3_mprintf(
950 "DROP TABLE '%q'.'%q_node';"
951 "DROP TABLE '%q'.'%q_rowid';"
952 "DROP TABLE '%q'.'%q_parent';",
953 pRtree
->zDb
, pRtree
->zName
,
954 pRtree
->zDb
, pRtree
->zName
,
955 pRtree
->zDb
, pRtree
->zName
960 nodeBlobReset(pRtree
);
961 rc
= sqlite3_exec(pRtree
->db
, zCreate
, 0, 0, 0);
962 sqlite3_free(zCreate
);
965 rtreeRelease(pRtree
);
972 ** Rtree virtual table module xOpen method.
974 static int rtreeOpen(sqlite3_vtab
*pVTab
, sqlite3_vtab_cursor
**ppCursor
){
975 int rc
= SQLITE_NOMEM
;
976 Rtree
*pRtree
= (Rtree
*)pVTab
;
979 pCsr
= (RtreeCursor
*)sqlite3_malloc(sizeof(RtreeCursor
));
981 memset(pCsr
, 0, sizeof(RtreeCursor
));
982 pCsr
->base
.pVtab
= pVTab
;
986 *ppCursor
= (sqlite3_vtab_cursor
*)pCsr
;
993 ** Free the RtreeCursor.aConstraint[] array and its contents.
995 static void freeCursorConstraints(RtreeCursor
*pCsr
){
996 if( pCsr
->aConstraint
){
997 int i
; /* Used to iterate through constraint array */
998 for(i
=0; i
<pCsr
->nConstraint
; i
++){
999 sqlite3_rtree_query_info
*pInfo
= pCsr
->aConstraint
[i
].pInfo
;
1001 if( pInfo
->xDelUser
) pInfo
->xDelUser(pInfo
->pUser
);
1002 sqlite3_free(pInfo
);
1005 sqlite3_free(pCsr
->aConstraint
);
1006 pCsr
->aConstraint
= 0;
1011 ** Rtree virtual table module xClose method.
1013 static int rtreeClose(sqlite3_vtab_cursor
*cur
){
1014 Rtree
*pRtree
= (Rtree
*)(cur
->pVtab
);
1016 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1017 assert( pRtree
->nCursor
>0 );
1018 freeCursorConstraints(pCsr
);
1019 sqlite3_free(pCsr
->aPoint
);
1020 for(ii
=0; ii
<RTREE_CACHE_SZ
; ii
++) nodeRelease(pRtree
, pCsr
->aNode
[ii
]);
1023 nodeBlobReset(pRtree
);
1028 ** Rtree virtual table module xEof method.
1030 ** Return non-zero if the cursor does not currently point to a valid
1031 ** record (i.e if the scan has finished), or zero otherwise.
1033 static int rtreeEof(sqlite3_vtab_cursor
*cur
){
1034 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1039 ** Convert raw bits from the on-disk RTree record into a coordinate value.
1040 ** The on-disk format is big-endian and needs to be converted for little-
1041 ** endian platforms. The on-disk record stores integer coordinates if
1042 ** eInt is true and it stores 32-bit floating point records if eInt is
1043 ** false. a[] is the four bytes of the on-disk record to be decoded.
1044 ** Store the results in "r".
1046 ** There are five versions of this macro. The last one is generic. The
1047 ** other four are various architectures-specific optimizations.
1049 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1050 #define RTREE_DECODE_COORD(eInt, a, r) { \
1051 RtreeCoord c; /* Coordinate decoded */ \
1052 c.u = _byteswap_ulong(*(u32*)a); \
1053 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1055 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1056 #define RTREE_DECODE_COORD(eInt, a, r) { \
1057 RtreeCoord c; /* Coordinate decoded */ \
1058 c.u = __builtin_bswap32(*(u32*)a); \
1059 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1061 #elif SQLITE_BYTEORDER==1234
1062 #define RTREE_DECODE_COORD(eInt, a, r) { \
1063 RtreeCoord c; /* Coordinate decoded */ \
1065 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
1066 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
1067 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1069 #elif SQLITE_BYTEORDER==4321
1070 #define RTREE_DECODE_COORD(eInt, a, r) { \
1071 RtreeCoord c; /* Coordinate decoded */ \
1073 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1076 #define RTREE_DECODE_COORD(eInt, a, r) { \
1077 RtreeCoord c; /* Coordinate decoded */ \
1078 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
1079 +((u32)a[2]<<8) + a[3]; \
1080 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1085 ** Check the RTree node or entry given by pCellData and p against the MATCH
1086 ** constraint pConstraint.
1088 static int rtreeCallbackConstraint(
1089 RtreeConstraint
*pConstraint
, /* The constraint to test */
1090 int eInt
, /* True if RTree holding integer coordinates */
1091 u8
*pCellData
, /* Raw cell content */
1092 RtreeSearchPoint
*pSearch
, /* Container of this cell */
1093 sqlite3_rtree_dbl
*prScore
, /* OUT: score for the cell */
1094 int *peWithin
/* OUT: visibility of the cell */
1096 sqlite3_rtree_query_info
*pInfo
= pConstraint
->pInfo
; /* Callback info */
1097 int nCoord
= pInfo
->nCoord
; /* No. of coordinates */
1098 int rc
; /* Callback return code */
1099 RtreeCoord c
; /* Translator union */
1100 sqlite3_rtree_dbl aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Decoded coordinates */
1102 assert( pConstraint
->op
==RTREE_MATCH
|| pConstraint
->op
==RTREE_QUERY
);
1103 assert( nCoord
==2 || nCoord
==4 || nCoord
==6 || nCoord
==8 || nCoord
==10 );
1105 if( pConstraint
->op
==RTREE_QUERY
&& pSearch
->iLevel
==1 ){
1106 pInfo
->iRowid
= readInt64(pCellData
);
1109 #ifndef SQLITE_RTREE_INT_ONLY
1112 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.f
;
1113 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.f
;
1114 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.f
;
1115 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.f
;
1116 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.f
;
1117 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.f
;
1118 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.f
;
1119 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.f
;
1120 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.f
;
1121 readCoord(pCellData
, &c
); aCoord
[0] = c
.f
;
1127 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.i
;
1128 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.i
;
1129 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.i
;
1130 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.i
;
1131 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.i
;
1132 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.i
;
1133 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.i
;
1134 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.i
;
1135 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.i
;
1136 readCoord(pCellData
, &c
); aCoord
[0] = c
.i
;
1139 if( pConstraint
->op
==RTREE_MATCH
){
1141 rc
= pConstraint
->u
.xGeom((sqlite3_rtree_geometry
*)pInfo
,
1142 nCoord
, aCoord
, &eWithin
);
1143 if( eWithin
==0 ) *peWithin
= NOT_WITHIN
;
1144 *prScore
= RTREE_ZERO
;
1146 pInfo
->aCoord
= aCoord
;
1147 pInfo
->iLevel
= pSearch
->iLevel
- 1;
1148 pInfo
->rScore
= pInfo
->rParentScore
= pSearch
->rScore
;
1149 pInfo
->eWithin
= pInfo
->eParentWithin
= pSearch
->eWithin
;
1150 rc
= pConstraint
->u
.xQueryFunc(pInfo
);
1151 if( pInfo
->eWithin
<*peWithin
) *peWithin
= pInfo
->eWithin
;
1152 if( pInfo
->rScore
<*prScore
|| *prScore
<RTREE_ZERO
){
1153 *prScore
= pInfo
->rScore
;
1160 ** Check the internal RTree node given by pCellData against constraint p.
1161 ** If this constraint cannot be satisfied by any child within the node,
1162 ** set *peWithin to NOT_WITHIN.
1164 static void rtreeNonleafConstraint(
1165 RtreeConstraint
*p
, /* The constraint to test */
1166 int eInt
, /* True if RTree holds integer coordinates */
1167 u8
*pCellData
, /* Raw cell content as appears on disk */
1168 int *peWithin
/* Adjust downward, as appropriate */
1170 sqlite3_rtree_dbl val
; /* Coordinate value convert to a double */
1172 /* p->iCoord might point to either a lower or upper bound coordinate
1173 ** in a coordinate pair. But make pCellData point to the lower bound.
1175 pCellData
+= 8 + 4*(p
->iCoord
&0xfe);
1177 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1178 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1179 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1184 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1185 /* val now holds the lower bound of the coordinate pair */
1186 if( p
->u
.rValue
>=val
) return;
1187 if( p
->op
!=RTREE_EQ
) break; /* RTREE_LE and RTREE_LT end here */
1188 /* Fall through for the RTREE_EQ case */
1190 default: /* RTREE_GT or RTREE_GE, or fallthrough of RTREE_EQ */
1192 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1193 /* val now holds the upper bound of the coordinate pair */
1194 if( p
->u
.rValue
<=val
) return;
1196 *peWithin
= NOT_WITHIN
;
1200 ** Check the leaf RTree cell given by pCellData against constraint p.
1201 ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
1202 ** If the constraint is satisfied, leave *peWithin unchanged.
1204 ** The constraint is of the form: xN op $val
1206 ** The op is given by p->op. The xN is p->iCoord-th coordinate in
1207 ** pCellData. $val is given by p->u.rValue.
1209 static void rtreeLeafConstraint(
1210 RtreeConstraint
*p
, /* The constraint to test */
1211 int eInt
, /* True if RTree holds integer coordinates */
1212 u8
*pCellData
, /* Raw cell content as appears on disk */
1213 int *peWithin
/* Adjust downward, as appropriate */
1215 RtreeDValue xN
; /* Coordinate value converted to a double */
1217 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1218 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1219 pCellData
+= 8 + p
->iCoord
*4;
1220 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1221 RTREE_DECODE_COORD(eInt
, pCellData
, xN
);
1223 case RTREE_LE
: if( xN
<= p
->u
.rValue
) return; break;
1224 case RTREE_LT
: if( xN
< p
->u
.rValue
) return; break;
1225 case RTREE_GE
: if( xN
>= p
->u
.rValue
) return; break;
1226 case RTREE_GT
: if( xN
> p
->u
.rValue
) return; break;
1227 default: if( xN
== p
->u
.rValue
) return; break;
1229 *peWithin
= NOT_WITHIN
;
1233 ** One of the cells in node pNode is guaranteed to have a 64-bit
1234 ** integer value equal to iRowid. Return the index of this cell.
1236 static int nodeRowidIndex(
1243 int nCell
= NCELL(pNode
);
1244 assert( nCell
<200 );
1245 for(ii
=0; ii
<nCell
; ii
++){
1246 if( nodeGetRowid(pRtree
, pNode
, ii
)==iRowid
){
1251 return SQLITE_CORRUPT_VTAB
;
1255 ** Return the index of the cell containing a pointer to node pNode
1256 ** in its parent. If pNode is the root node, return -1.
1258 static int nodeParentIndex(Rtree
*pRtree
, RtreeNode
*pNode
, int *piIndex
){
1259 RtreeNode
*pParent
= pNode
->pParent
;
1261 return nodeRowidIndex(pRtree
, pParent
, pNode
->iNode
, piIndex
);
1268 ** Compare two search points. Return negative, zero, or positive if the first
1269 ** is less than, equal to, or greater than the second.
1271 ** The rScore is the primary key. Smaller rScore values come first.
1272 ** If the rScore is a tie, then use iLevel as the tie breaker with smaller
1273 ** iLevel values coming first. In this way, if rScore is the same for all
1274 ** SearchPoints, then iLevel becomes the deciding factor and the result
1275 ** is a depth-first search, which is the desired default behavior.
1277 static int rtreeSearchPointCompare(
1278 const RtreeSearchPoint
*pA
,
1279 const RtreeSearchPoint
*pB
1281 if( pA
->rScore
<pB
->rScore
) return -1;
1282 if( pA
->rScore
>pB
->rScore
) return +1;
1283 if( pA
->iLevel
<pB
->iLevel
) return -1;
1284 if( pA
->iLevel
>pB
->iLevel
) return +1;
1289 ** Interchange two search points in a cursor.
1291 static void rtreeSearchPointSwap(RtreeCursor
*p
, int i
, int j
){
1292 RtreeSearchPoint t
= p
->aPoint
[i
];
1294 p
->aPoint
[i
] = p
->aPoint
[j
];
1297 if( i
<RTREE_CACHE_SZ
){
1298 if( j
>=RTREE_CACHE_SZ
){
1299 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1302 RtreeNode
*pTemp
= p
->aNode
[i
];
1303 p
->aNode
[i
] = p
->aNode
[j
];
1304 p
->aNode
[j
] = pTemp
;
1310 ** Return the search point with the lowest current score.
1312 static RtreeSearchPoint
*rtreeSearchPointFirst(RtreeCursor
*pCur
){
1313 return pCur
->bPoint
? &pCur
->sPoint
: pCur
->nPoint
? pCur
->aPoint
: 0;
1317 ** Get the RtreeNode for the search point with the lowest score.
1319 static RtreeNode
*rtreeNodeOfFirstSearchPoint(RtreeCursor
*pCur
, int *pRC
){
1321 int ii
= 1 - pCur
->bPoint
;
1322 assert( ii
==0 || ii
==1 );
1323 assert( pCur
->bPoint
|| pCur
->nPoint
);
1324 if( pCur
->aNode
[ii
]==0 ){
1326 id
= ii
? pCur
->aPoint
[0].id
: pCur
->sPoint
.id
;
1327 *pRC
= nodeAcquire(RTREE_OF_CURSOR(pCur
), id
, 0, &pCur
->aNode
[ii
]);
1329 return pCur
->aNode
[ii
];
1333 ** Push a new element onto the priority queue
1335 static RtreeSearchPoint
*rtreeEnqueue(
1336 RtreeCursor
*pCur
, /* The cursor */
1337 RtreeDValue rScore
, /* Score for the new search point */
1338 u8 iLevel
/* Level for the new search point */
1341 RtreeSearchPoint
*pNew
;
1342 if( pCur
->nPoint
>=pCur
->nPointAlloc
){
1343 int nNew
= pCur
->nPointAlloc
*2 + 8;
1344 pNew
= sqlite3_realloc(pCur
->aPoint
, nNew
*sizeof(pCur
->aPoint
[0]));
1345 if( pNew
==0 ) return 0;
1346 pCur
->aPoint
= pNew
;
1347 pCur
->nPointAlloc
= nNew
;
1350 pNew
= pCur
->aPoint
+ i
;
1351 pNew
->rScore
= rScore
;
1352 pNew
->iLevel
= iLevel
;
1353 assert( iLevel
<=RTREE_MAX_DEPTH
);
1355 RtreeSearchPoint
*pParent
;
1357 pParent
= pCur
->aPoint
+ j
;
1358 if( rtreeSearchPointCompare(pNew
, pParent
)>=0 ) break;
1359 rtreeSearchPointSwap(pCur
, j
, i
);
1367 ** Allocate a new RtreeSearchPoint and return a pointer to it. Return
1368 ** NULL if malloc fails.
1370 static RtreeSearchPoint
*rtreeSearchPointNew(
1371 RtreeCursor
*pCur
, /* The cursor */
1372 RtreeDValue rScore
, /* Score for the new search point */
1373 u8 iLevel
/* Level for the new search point */
1375 RtreeSearchPoint
*pNew
, *pFirst
;
1376 pFirst
= rtreeSearchPointFirst(pCur
);
1377 pCur
->anQueue
[iLevel
]++;
1379 || pFirst
->rScore
>rScore
1380 || (pFirst
->rScore
==rScore
&& pFirst
->iLevel
>iLevel
)
1384 pNew
= rtreeEnqueue(pCur
, rScore
, iLevel
);
1385 if( pNew
==0 ) return 0;
1386 ii
= (int)(pNew
- pCur
->aPoint
) + 1;
1387 if( ii
<RTREE_CACHE_SZ
){
1388 assert( pCur
->aNode
[ii
]==0 );
1389 pCur
->aNode
[ii
] = pCur
->aNode
[0];
1391 nodeRelease(RTREE_OF_CURSOR(pCur
), pCur
->aNode
[0]);
1394 *pNew
= pCur
->sPoint
;
1396 pCur
->sPoint
.rScore
= rScore
;
1397 pCur
->sPoint
.iLevel
= iLevel
;
1399 return &pCur
->sPoint
;
1401 return rtreeEnqueue(pCur
, rScore
, iLevel
);
1406 /* Tracing routines for the RtreeSearchPoint queue */
1407 static void tracePoint(RtreeSearchPoint
*p
, int idx
, RtreeCursor
*pCur
){
1408 if( idx
<0 ){ printf(" s"); }else{ printf("%2d", idx
); }
1409 printf(" %d.%05lld.%02d %g %d",
1410 p
->iLevel
, p
->id
, p
->iCell
, p
->rScore
, p
->eWithin
1413 if( idx
<RTREE_CACHE_SZ
){
1414 printf(" %p\n", pCur
->aNode
[idx
]);
1419 static void traceQueue(RtreeCursor
*pCur
, const char *zPrefix
){
1421 printf("=== %9s ", zPrefix
);
1423 tracePoint(&pCur
->sPoint
, -1, pCur
);
1425 for(ii
=0; ii
<pCur
->nPoint
; ii
++){
1426 if( ii
>0 || pCur
->bPoint
) printf(" ");
1427 tracePoint(&pCur
->aPoint
[ii
], ii
, pCur
);
1430 # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
1432 # define RTREE_QUEUE_TRACE(A,B) /* no-op */
1435 /* Remove the search point with the lowest current score.
1437 static void rtreeSearchPointPop(RtreeCursor
*p
){
1440 assert( i
==0 || i
==1 );
1442 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1446 p
->anQueue
[p
->sPoint
.iLevel
]--;
1448 }else if( p
->nPoint
){
1449 p
->anQueue
[p
->aPoint
[0].iLevel
]--;
1451 p
->aPoint
[0] = p
->aPoint
[n
];
1452 if( n
<RTREE_CACHE_SZ
-1 ){
1453 p
->aNode
[1] = p
->aNode
[n
+1];
1457 while( (j
= i
*2+1)<n
){
1459 if( k
<n
&& rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[j
])<0 ){
1460 if( rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[i
])<0 ){
1461 rtreeSearchPointSwap(p
, i
, k
);
1467 if( rtreeSearchPointCompare(&p
->aPoint
[j
], &p
->aPoint
[i
])<0 ){
1468 rtreeSearchPointSwap(p
, i
, j
);
1480 ** Continue the search on cursor pCur until the front of the queue
1481 ** contains an entry suitable for returning as a result-set row,
1482 ** or until the RtreeSearchPoint queue is empty, indicating that the
1483 ** query has completed.
1485 static int rtreeStepToLeaf(RtreeCursor
*pCur
){
1486 RtreeSearchPoint
*p
;
1487 Rtree
*pRtree
= RTREE_OF_CURSOR(pCur
);
1492 int nConstraint
= pCur
->nConstraint
;
1497 eInt
= pRtree
->eCoordType
==RTREE_COORD_INT32
;
1498 while( (p
= rtreeSearchPointFirst(pCur
))!=0 && p
->iLevel
>0 ){
1499 pNode
= rtreeNodeOfFirstSearchPoint(pCur
, &rc
);
1501 nCell
= NCELL(pNode
);
1502 assert( nCell
<200 );
1503 while( p
->iCell
<nCell
){
1504 sqlite3_rtree_dbl rScore
= (sqlite3_rtree_dbl
)-1;
1505 u8
*pCellData
= pNode
->zData
+ (4+pRtree
->nBytesPerCell
*p
->iCell
);
1506 eWithin
= FULLY_WITHIN
;
1507 for(ii
=0; ii
<nConstraint
; ii
++){
1508 RtreeConstraint
*pConstraint
= pCur
->aConstraint
+ ii
;
1509 if( pConstraint
->op
>=RTREE_MATCH
){
1510 rc
= rtreeCallbackConstraint(pConstraint
, eInt
, pCellData
, p
,
1513 }else if( p
->iLevel
==1 ){
1514 rtreeLeafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1516 rtreeNonleafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1518 if( eWithin
==NOT_WITHIN
) break;
1521 if( eWithin
==NOT_WITHIN
) continue;
1522 x
.iLevel
= p
->iLevel
- 1;
1524 x
.id
= readInt64(pCellData
);
1528 x
.iCell
= p
->iCell
- 1;
1530 if( p
->iCell
>=nCell
){
1531 RTREE_QUEUE_TRACE(pCur
, "POP-S:");
1532 rtreeSearchPointPop(pCur
);
1534 if( rScore
<RTREE_ZERO
) rScore
= RTREE_ZERO
;
1535 p
= rtreeSearchPointNew(pCur
, rScore
, x
.iLevel
);
1536 if( p
==0 ) return SQLITE_NOMEM
;
1537 p
->eWithin
= (u8
)eWithin
;
1540 RTREE_QUEUE_TRACE(pCur
, "PUSH-S:");
1543 if( p
->iCell
>=nCell
){
1544 RTREE_QUEUE_TRACE(pCur
, "POP-Se:");
1545 rtreeSearchPointPop(pCur
);
1553 ** Rtree virtual table module xNext method.
1555 static int rtreeNext(sqlite3_vtab_cursor
*pVtabCursor
){
1556 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1559 /* Move to the next entry that matches the configured constraints. */
1560 RTREE_QUEUE_TRACE(pCsr
, "POP-Nx:");
1561 rtreeSearchPointPop(pCsr
);
1562 rc
= rtreeStepToLeaf(pCsr
);
1567 ** Rtree virtual table module xRowid method.
1569 static int rtreeRowid(sqlite3_vtab_cursor
*pVtabCursor
, sqlite_int64
*pRowid
){
1570 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1571 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1573 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1574 if( rc
==SQLITE_OK
&& p
){
1575 *pRowid
= nodeGetRowid(RTREE_OF_CURSOR(pCsr
), pNode
, p
->iCell
);
1581 ** Rtree virtual table module xColumn method.
1583 static int rtreeColumn(sqlite3_vtab_cursor
*cur
, sqlite3_context
*ctx
, int i
){
1584 Rtree
*pRtree
= (Rtree
*)cur
->pVtab
;
1585 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1586 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1589 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1592 if( p
==0 ) return SQLITE_OK
;
1594 sqlite3_result_int64(ctx
, nodeGetRowid(pRtree
, pNode
, p
->iCell
));
1596 nodeGetCoord(pRtree
, pNode
, p
->iCell
, i
-1, &c
);
1597 #ifndef SQLITE_RTREE_INT_ONLY
1598 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1599 sqlite3_result_double(ctx
, c
.f
);
1603 assert( pRtree
->eCoordType
==RTREE_COORD_INT32
);
1604 sqlite3_result_int(ctx
, c
.i
);
1611 ** Use nodeAcquire() to obtain the leaf node containing the record with
1612 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
1613 ** return SQLITE_OK. If there is no such record in the table, set
1614 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1615 ** to zero and return an SQLite error code.
1617 static int findLeafNode(
1618 Rtree
*pRtree
, /* RTree to search */
1619 i64 iRowid
, /* The rowid searching for */
1620 RtreeNode
**ppLeaf
, /* Write the node here */
1621 sqlite3_int64
*piNode
/* Write the node-id here */
1625 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, iRowid
);
1626 if( sqlite3_step(pRtree
->pReadRowid
)==SQLITE_ROW
){
1627 i64 iNode
= sqlite3_column_int64(pRtree
->pReadRowid
, 0);
1628 if( piNode
) *piNode
= iNode
;
1629 rc
= nodeAcquire(pRtree
, iNode
, 0, ppLeaf
);
1630 sqlite3_reset(pRtree
->pReadRowid
);
1632 rc
= sqlite3_reset(pRtree
->pReadRowid
);
1638 ** This function is called to configure the RtreeConstraint object passed
1639 ** as the second argument for a MATCH constraint. The value passed as the
1640 ** first argument to this function is the right-hand operand to the MATCH
1643 static int deserializeGeometry(sqlite3_value
*pValue
, RtreeConstraint
*pCons
){
1644 RtreeMatchArg
*pBlob
, *pSrc
; /* BLOB returned by geometry function */
1645 sqlite3_rtree_query_info
*pInfo
; /* Callback information */
1647 pSrc
= sqlite3_value_pointer(pValue
, "RtreeMatchArg");
1648 if( pSrc
==0 ) return SQLITE_ERROR
;
1649 pInfo
= (sqlite3_rtree_query_info
*)
1650 sqlite3_malloc64( sizeof(*pInfo
)+pSrc
->iSize
);
1651 if( !pInfo
) return SQLITE_NOMEM
;
1652 memset(pInfo
, 0, sizeof(*pInfo
));
1653 pBlob
= (RtreeMatchArg
*)&pInfo
[1];
1654 memcpy(pBlob
, pSrc
, pSrc
->iSize
);
1655 pInfo
->pContext
= pBlob
->cb
.pContext
;
1656 pInfo
->nParam
= pBlob
->nParam
;
1657 pInfo
->aParam
= pBlob
->aParam
;
1658 pInfo
->apSqlParam
= pBlob
->apSqlParam
;
1660 if( pBlob
->cb
.xGeom
){
1661 pCons
->u
.xGeom
= pBlob
->cb
.xGeom
;
1663 pCons
->op
= RTREE_QUERY
;
1664 pCons
->u
.xQueryFunc
= pBlob
->cb
.xQueryFunc
;
1666 pCons
->pInfo
= pInfo
;
1671 ** Rtree virtual table module xFilter method.
1673 static int rtreeFilter(
1674 sqlite3_vtab_cursor
*pVtabCursor
,
1675 int idxNum
, const char *idxStr
,
1676 int argc
, sqlite3_value
**argv
1678 Rtree
*pRtree
= (Rtree
*)pVtabCursor
->pVtab
;
1679 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1680 RtreeNode
*pRoot
= 0;
1685 rtreeReference(pRtree
);
1687 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
1688 freeCursorConstraints(pCsr
);
1689 sqlite3_free(pCsr
->aPoint
);
1690 memset(pCsr
, 0, sizeof(RtreeCursor
));
1691 pCsr
->base
.pVtab
= (sqlite3_vtab
*)pRtree
;
1693 pCsr
->iStrategy
= idxNum
;
1695 /* Special case - lookup by rowid. */
1696 RtreeNode
*pLeaf
; /* Leaf on which the required cell resides */
1697 RtreeSearchPoint
*p
; /* Search point for the leaf */
1698 i64 iRowid
= sqlite3_value_int64(argv
[0]);
1700 rc
= findLeafNode(pRtree
, iRowid
, &pLeaf
, &iNode
);
1701 if( rc
==SQLITE_OK
&& pLeaf
!=0 ){
1702 p
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, 0);
1703 assert( p
!=0 ); /* Always returns pCsr->sPoint */
1704 pCsr
->aNode
[0] = pLeaf
;
1706 p
->eWithin
= PARTLY_WITHIN
;
1707 rc
= nodeRowidIndex(pRtree
, pLeaf
, iRowid
, &iCell
);
1708 p
->iCell
= (u8
)iCell
;
1709 RTREE_QUEUE_TRACE(pCsr
, "PUSH-F1:");
1714 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1715 ** with the configured constraints.
1717 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
1718 if( rc
==SQLITE_OK
&& argc
>0 ){
1719 pCsr
->aConstraint
= sqlite3_malloc(sizeof(RtreeConstraint
)*argc
);
1720 pCsr
->nConstraint
= argc
;
1721 if( !pCsr
->aConstraint
){
1724 memset(pCsr
->aConstraint
, 0, sizeof(RtreeConstraint
)*argc
);
1725 memset(pCsr
->anQueue
, 0, sizeof(u32
)*(pRtree
->iDepth
+ 1));
1726 assert( (idxStr
==0 && argc
==0)
1727 || (idxStr
&& (int)strlen(idxStr
)==argc
*2) );
1728 for(ii
=0; ii
<argc
; ii
++){
1729 RtreeConstraint
*p
= &pCsr
->aConstraint
[ii
];
1730 p
->op
= idxStr
[ii
*2];
1731 p
->iCoord
= idxStr
[ii
*2+1]-'0';
1732 if( p
->op
>=RTREE_MATCH
){
1733 /* A MATCH operator. The right-hand-side must be a blob that
1734 ** can be cast into an RtreeMatchArg object. One created using
1735 ** an sqlite3_rtree_geometry_callback() SQL user function.
1737 rc
= deserializeGeometry(argv
[ii
], p
);
1738 if( rc
!=SQLITE_OK
){
1741 p
->pInfo
->nCoord
= pRtree
->nDim2
;
1742 p
->pInfo
->anQueue
= pCsr
->anQueue
;
1743 p
->pInfo
->mxLevel
= pRtree
->iDepth
+ 1;
1745 #ifdef SQLITE_RTREE_INT_ONLY
1746 p
->u
.rValue
= sqlite3_value_int64(argv
[ii
]);
1748 p
->u
.rValue
= sqlite3_value_double(argv
[ii
]);
1754 if( rc
==SQLITE_OK
){
1755 RtreeSearchPoint
*pNew
;
1756 pNew
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, (u8
)(pRtree
->iDepth
+1));
1757 if( pNew
==0 ) return SQLITE_NOMEM
;
1760 pNew
->eWithin
= PARTLY_WITHIN
;
1761 assert( pCsr
->bPoint
==1 );
1762 pCsr
->aNode
[0] = pRoot
;
1764 RTREE_QUEUE_TRACE(pCsr
, "PUSH-Fm:");
1765 rc
= rtreeStepToLeaf(pCsr
);
1769 nodeRelease(pRtree
, pRoot
);
1770 rtreeRelease(pRtree
);
1775 ** Rtree virtual table module xBestIndex method. There are three
1776 ** table scan strategies to choose from (in order from most to
1777 ** least desirable):
1779 ** idxNum idxStr Strategy
1780 ** ------------------------------------------------
1781 ** 1 Unused Direct lookup by rowid.
1782 ** 2 See below R-tree query or full-table scan.
1783 ** ------------------------------------------------
1785 ** If strategy 1 is used, then idxStr is not meaningful. If strategy
1786 ** 2 is used, idxStr is formatted to contain 2 bytes for each
1787 ** constraint used. The first two bytes of idxStr correspond to
1788 ** the constraint in sqlite3_index_info.aConstraintUsage[] with
1789 ** (argvIndex==1) etc.
1791 ** The first of each pair of bytes in idxStr identifies the constraint
1792 ** operator as follows:
1794 ** Operator Byte Value
1795 ** ----------------------
1802 ** ----------------------
1804 ** The second of each pair of bytes identifies the coordinate column
1805 ** to which the constraint applies. The leftmost coordinate column
1806 ** is 'a', the second from the left 'b' etc.
1808 static int rtreeBestIndex(sqlite3_vtab
*tab
, sqlite3_index_info
*pIdxInfo
){
1809 Rtree
*pRtree
= (Rtree
*)tab
;
1812 int bMatch
= 0; /* True if there exists a MATCH constraint */
1813 i64 nRow
; /* Estimated rows returned by this scan */
1816 char zIdxStr
[RTREE_MAX_DIMENSIONS
*8+1];
1817 memset(zIdxStr
, 0, sizeof(zIdxStr
));
1819 /* Check if there exists a MATCH constraint - even an unusable one. If there
1820 ** is, do not consider the lookup-by-rowid plan as using such a plan would
1821 ** require the VDBE to evaluate the MATCH constraint, which is not currently
1823 for(ii
=0; ii
<pIdxInfo
->nConstraint
; ii
++){
1824 if( pIdxInfo
->aConstraint
[ii
].op
==SQLITE_INDEX_CONSTRAINT_MATCH
){
1829 assert( pIdxInfo
->idxStr
==0 );
1830 for(ii
=0; ii
<pIdxInfo
->nConstraint
&& iIdx
<(int)(sizeof(zIdxStr
)-1); ii
++){
1831 struct sqlite3_index_constraint
*p
= &pIdxInfo
->aConstraint
[ii
];
1833 if( bMatch
==0 && p
->usable
1834 && p
->iColumn
==0 && p
->op
==SQLITE_INDEX_CONSTRAINT_EQ
1836 /* We have an equality constraint on the rowid. Use strategy 1. */
1838 for(jj
=0; jj
<ii
; jj
++){
1839 pIdxInfo
->aConstraintUsage
[jj
].argvIndex
= 0;
1840 pIdxInfo
->aConstraintUsage
[jj
].omit
= 0;
1842 pIdxInfo
->idxNum
= 1;
1843 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= 1;
1844 pIdxInfo
->aConstraintUsage
[jj
].omit
= 1;
1846 /* This strategy involves a two rowid lookups on an B-Tree structures
1847 ** and then a linear search of an R-Tree node. This should be
1848 ** considered almost as quick as a direct rowid lookup (for which
1849 ** sqlite uses an internal cost of 0.0). It is expected to return
1852 pIdxInfo
->estimatedCost
= 30.0;
1853 pIdxInfo
->estimatedRows
= 1;
1857 if( p
->usable
&& (p
->iColumn
>0 || p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
) ){
1860 case SQLITE_INDEX_CONSTRAINT_EQ
: op
= RTREE_EQ
; break;
1861 case SQLITE_INDEX_CONSTRAINT_GT
: op
= RTREE_GT
; break;
1862 case SQLITE_INDEX_CONSTRAINT_LE
: op
= RTREE_LE
; break;
1863 case SQLITE_INDEX_CONSTRAINT_LT
: op
= RTREE_LT
; break;
1864 case SQLITE_INDEX_CONSTRAINT_GE
: op
= RTREE_GE
; break;
1866 assert( p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
);
1870 zIdxStr
[iIdx
++] = op
;
1871 zIdxStr
[iIdx
++] = (char)(p
->iColumn
- 1 + '0');
1872 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= (iIdx
/2);
1873 pIdxInfo
->aConstraintUsage
[ii
].omit
= 1;
1877 pIdxInfo
->idxNum
= 2;
1878 pIdxInfo
->needToFreeIdxStr
= 1;
1879 if( iIdx
>0 && 0==(pIdxInfo
->idxStr
= sqlite3_mprintf("%s", zIdxStr
)) ){
1880 return SQLITE_NOMEM
;
1883 nRow
= pRtree
->nRowEst
>> (iIdx
/2);
1884 pIdxInfo
->estimatedCost
= (double)6.0 * (double)nRow
;
1885 pIdxInfo
->estimatedRows
= nRow
;
1891 ** Return the N-dimensional volumn of the cell stored in *p.
1893 static RtreeDValue
cellArea(Rtree
*pRtree
, RtreeCell
*p
){
1894 RtreeDValue area
= (RtreeDValue
)1;
1895 assert( pRtree
->nDim
>=1 && pRtree
->nDim
<=5 );
1896 #ifndef SQLITE_RTREE_INT_ONLY
1897 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1898 switch( pRtree
->nDim
){
1899 case 5: area
= p
->aCoord
[9].f
- p
->aCoord
[8].f
;
1900 case 4: area
*= p
->aCoord
[7].f
- p
->aCoord
[6].f
;
1901 case 3: area
*= p
->aCoord
[5].f
- p
->aCoord
[4].f
;
1902 case 2: area
*= p
->aCoord
[3].f
- p
->aCoord
[2].f
;
1903 default: area
*= p
->aCoord
[1].f
- p
->aCoord
[0].f
;
1908 switch( pRtree
->nDim
){
1909 case 5: area
= p
->aCoord
[9].i
- p
->aCoord
[8].i
;
1910 case 4: area
*= p
->aCoord
[7].i
- p
->aCoord
[6].i
;
1911 case 3: area
*= p
->aCoord
[5].i
- p
->aCoord
[4].i
;
1912 case 2: area
*= p
->aCoord
[3].i
- p
->aCoord
[2].i
;
1913 default: area
*= p
->aCoord
[1].i
- p
->aCoord
[0].i
;
1920 ** Return the margin length of cell p. The margin length is the sum
1921 ** of the objects size in each dimension.
1923 static RtreeDValue
cellMargin(Rtree
*pRtree
, RtreeCell
*p
){
1924 RtreeDValue margin
= 0;
1925 int ii
= pRtree
->nDim2
- 2;
1927 margin
+= (DCOORD(p
->aCoord
[ii
+1]) - DCOORD(p
->aCoord
[ii
]));
1934 ** Store the union of cells p1 and p2 in p1.
1936 static void cellUnion(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
1938 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1940 p1
->aCoord
[ii
].f
= MIN(p1
->aCoord
[ii
].f
, p2
->aCoord
[ii
].f
);
1941 p1
->aCoord
[ii
+1].f
= MAX(p1
->aCoord
[ii
+1].f
, p2
->aCoord
[ii
+1].f
);
1943 }while( ii
<pRtree
->nDim2
);
1946 p1
->aCoord
[ii
].i
= MIN(p1
->aCoord
[ii
].i
, p2
->aCoord
[ii
].i
);
1947 p1
->aCoord
[ii
+1].i
= MAX(p1
->aCoord
[ii
+1].i
, p2
->aCoord
[ii
+1].i
);
1949 }while( ii
<pRtree
->nDim2
);
1954 ** Return true if the area covered by p2 is a subset of the area covered
1955 ** by p1. False otherwise.
1957 static int cellContains(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
1959 int isInt
= (pRtree
->eCoordType
==RTREE_COORD_INT32
);
1960 for(ii
=0; ii
<pRtree
->nDim2
; ii
+=2){
1961 RtreeCoord
*a1
= &p1
->aCoord
[ii
];
1962 RtreeCoord
*a2
= &p2
->aCoord
[ii
];
1963 if( (!isInt
&& (a2
[0].f
<a1
[0].f
|| a2
[1].f
>a1
[1].f
))
1964 || ( isInt
&& (a2
[0].i
<a1
[0].i
|| a2
[1].i
>a1
[1].i
))
1973 ** Return the amount cell p would grow by if it were unioned with pCell.
1975 static RtreeDValue
cellGrowth(Rtree
*pRtree
, RtreeCell
*p
, RtreeCell
*pCell
){
1978 memcpy(&cell
, p
, sizeof(RtreeCell
));
1979 area
= cellArea(pRtree
, &cell
);
1980 cellUnion(pRtree
, &cell
, pCell
);
1981 return (cellArea(pRtree
, &cell
)-area
);
1984 static RtreeDValue
cellOverlap(
1991 RtreeDValue overlap
= RTREE_ZERO
;
1992 for(ii
=0; ii
<nCell
; ii
++){
1994 RtreeDValue o
= (RtreeDValue
)1;
1995 for(jj
=0; jj
<pRtree
->nDim2
; jj
+=2){
1997 x1
= MAX(DCOORD(p
->aCoord
[jj
]), DCOORD(aCell
[ii
].aCoord
[jj
]));
1998 x2
= MIN(DCOORD(p
->aCoord
[jj
+1]), DCOORD(aCell
[ii
].aCoord
[jj
+1]));
2013 ** This function implements the ChooseLeaf algorithm from Gutman[84].
2014 ** ChooseSubTree in r*tree terminology.
2016 static int ChooseLeaf(
2017 Rtree
*pRtree
, /* Rtree table */
2018 RtreeCell
*pCell
, /* Cell to insert into rtree */
2019 int iHeight
, /* Height of sub-tree rooted at pCell */
2020 RtreeNode
**ppLeaf
/* OUT: Selected leaf page */
2025 rc
= nodeAcquire(pRtree
, 1, 0, &pNode
);
2027 for(ii
=0; rc
==SQLITE_OK
&& ii
<(pRtree
->iDepth
-iHeight
); ii
++){
2029 sqlite3_int64 iBest
= 0;
2031 RtreeDValue fMinGrowth
= RTREE_ZERO
;
2032 RtreeDValue fMinArea
= RTREE_ZERO
;
2034 int nCell
= NCELL(pNode
);
2038 RtreeCell
*aCell
= 0;
2040 /* Select the child node which will be enlarged the least if pCell
2041 ** is inserted into it. Resolve ties by choosing the entry with
2042 ** the smallest area.
2044 for(iCell
=0; iCell
<nCell
; iCell
++){
2048 nodeGetCell(pRtree
, pNode
, iCell
, &cell
);
2049 growth
= cellGrowth(pRtree
, &cell
, pCell
);
2050 area
= cellArea(pRtree
, &cell
);
2051 if( iCell
==0||growth
<fMinGrowth
||(growth
==fMinGrowth
&& area
<fMinArea
) ){
2055 fMinGrowth
= growth
;
2057 iBest
= cell
.iRowid
;
2061 sqlite3_free(aCell
);
2062 rc
= nodeAcquire(pRtree
, iBest
, pNode
, &pChild
);
2063 nodeRelease(pRtree
, pNode
);
2072 ** A cell with the same content as pCell has just been inserted into
2073 ** the node pNode. This function updates the bounding box cells in
2074 ** all ancestor elements.
2076 static int AdjustTree(
2077 Rtree
*pRtree
, /* Rtree table */
2078 RtreeNode
*pNode
, /* Adjust ancestry of this node. */
2079 RtreeCell
*pCell
/* This cell was just inserted */
2081 RtreeNode
*p
= pNode
;
2082 while( p
->pParent
){
2083 RtreeNode
*pParent
= p
->pParent
;
2087 if( nodeParentIndex(pRtree
, p
, &iCell
) ){
2088 return SQLITE_CORRUPT_VTAB
;
2091 nodeGetCell(pRtree
, pParent
, iCell
, &cell
);
2092 if( !cellContains(pRtree
, &cell
, pCell
) ){
2093 cellUnion(pRtree
, &cell
, pCell
);
2094 nodeOverwriteCell(pRtree
, pParent
, &cell
, iCell
);
2103 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
2105 static int rowidWrite(Rtree
*pRtree
, sqlite3_int64 iRowid
, sqlite3_int64 iNode
){
2106 sqlite3_bind_int64(pRtree
->pWriteRowid
, 1, iRowid
);
2107 sqlite3_bind_int64(pRtree
->pWriteRowid
, 2, iNode
);
2108 sqlite3_step(pRtree
->pWriteRowid
);
2109 return sqlite3_reset(pRtree
->pWriteRowid
);
2113 ** Write mapping (iNode->iPar) to the <rtree>_parent table.
2115 static int parentWrite(Rtree
*pRtree
, sqlite3_int64 iNode
, sqlite3_int64 iPar
){
2116 sqlite3_bind_int64(pRtree
->pWriteParent
, 1, iNode
);
2117 sqlite3_bind_int64(pRtree
->pWriteParent
, 2, iPar
);
2118 sqlite3_step(pRtree
->pWriteParent
);
2119 return sqlite3_reset(pRtree
->pWriteParent
);
2122 static int rtreeInsertCell(Rtree
*, RtreeNode
*, RtreeCell
*, int);
2126 ** Arguments aIdx, aDistance and aSpare all point to arrays of size
2127 ** nIdx. The aIdx array contains the set of integers from 0 to
2128 ** (nIdx-1) in no particular order. This function sorts the values
2129 ** in aIdx according to the indexed values in aDistance. For
2130 ** example, assuming the inputs:
2132 ** aIdx = { 0, 1, 2, 3 }
2133 ** aDistance = { 5.0, 2.0, 7.0, 6.0 }
2135 ** this function sets the aIdx array to contain:
2137 ** aIdx = { 0, 1, 2, 3 }
2139 ** The aSpare array is used as temporary working space by the
2140 ** sorting algorithm.
2142 static void SortByDistance(
2145 RtreeDValue
*aDistance
,
2153 int nRight
= nIdx
-nLeft
;
2155 int *aRight
= &aIdx
[nLeft
];
2157 SortByDistance(aLeft
, nLeft
, aDistance
, aSpare
);
2158 SortByDistance(aRight
, nRight
, aDistance
, aSpare
);
2160 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2163 while( iLeft
<nLeft
|| iRight
<nRight
){
2165 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2167 }else if( iRight
==nRight
){
2168 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2171 RtreeDValue fLeft
= aDistance
[aLeft
[iLeft
]];
2172 RtreeDValue fRight
= aDistance
[aRight
[iRight
]];
2174 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2177 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2184 /* Check that the sort worked */
2187 for(jj
=1; jj
<nIdx
; jj
++){
2188 RtreeDValue left
= aDistance
[aIdx
[jj
-1]];
2189 RtreeDValue right
= aDistance
[aIdx
[jj
]];
2190 assert( left
<=right
);
2198 ** Arguments aIdx, aCell and aSpare all point to arrays of size
2199 ** nIdx. The aIdx array contains the set of integers from 0 to
2200 ** (nIdx-1) in no particular order. This function sorts the values
2201 ** in aIdx according to dimension iDim of the cells in aCell. The
2202 ** minimum value of dimension iDim is considered first, the
2203 ** maximum used to break ties.
2205 ** The aSpare array is used as temporary working space by the
2206 ** sorting algorithm.
2208 static void SortByDimension(
2222 int nRight
= nIdx
-nLeft
;
2224 int *aRight
= &aIdx
[nLeft
];
2226 SortByDimension(pRtree
, aLeft
, nLeft
, iDim
, aCell
, aSpare
);
2227 SortByDimension(pRtree
, aRight
, nRight
, iDim
, aCell
, aSpare
);
2229 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2231 while( iLeft
<nLeft
|| iRight
<nRight
){
2232 RtreeDValue xleft1
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2]);
2233 RtreeDValue xleft2
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2+1]);
2234 RtreeDValue xright1
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2]);
2235 RtreeDValue xright2
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2+1]);
2236 if( (iLeft
!=nLeft
) && ((iRight
==nRight
)
2238 || (xleft1
==xright1
&& xleft2
<xright2
)
2240 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2243 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2249 /* Check that the sort worked */
2252 for(jj
=1; jj
<nIdx
; jj
++){
2253 RtreeDValue xleft1
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2];
2254 RtreeDValue xleft2
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2+1];
2255 RtreeDValue xright1
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2];
2256 RtreeDValue xright2
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2+1];
2257 assert( xleft1
<=xright1
&& (xleft1
<xright1
|| xleft2
<=xright2
) );
2265 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
2267 static int splitNodeStartree(
2273 RtreeCell
*pBboxLeft
,
2274 RtreeCell
*pBboxRight
2282 RtreeDValue fBestMargin
= RTREE_ZERO
;
2284 int nByte
= (pRtree
->nDim
+1)*(sizeof(int*)+nCell
*sizeof(int));
2286 aaSorted
= (int **)sqlite3_malloc(nByte
);
2288 return SQLITE_NOMEM
;
2291 aSpare
= &((int *)&aaSorted
[pRtree
->nDim
])[pRtree
->nDim
*nCell
];
2292 memset(aaSorted
, 0, nByte
);
2293 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2295 aaSorted
[ii
] = &((int *)&aaSorted
[pRtree
->nDim
])[ii
*nCell
];
2296 for(jj
=0; jj
<nCell
; jj
++){
2297 aaSorted
[ii
][jj
] = jj
;
2299 SortByDimension(pRtree
, aaSorted
[ii
], nCell
, ii
, aCell
, aSpare
);
2302 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2303 RtreeDValue margin
= RTREE_ZERO
;
2304 RtreeDValue fBestOverlap
= RTREE_ZERO
;
2305 RtreeDValue fBestArea
= RTREE_ZERO
;
2310 nLeft
=RTREE_MINCELLS(pRtree
);
2311 nLeft
<=(nCell
-RTREE_MINCELLS(pRtree
));
2317 RtreeDValue overlap
;
2320 memcpy(&left
, &aCell
[aaSorted
[ii
][0]], sizeof(RtreeCell
));
2321 memcpy(&right
, &aCell
[aaSorted
[ii
][nCell
-1]], sizeof(RtreeCell
));
2322 for(kk
=1; kk
<(nCell
-1); kk
++){
2324 cellUnion(pRtree
, &left
, &aCell
[aaSorted
[ii
][kk
]]);
2326 cellUnion(pRtree
, &right
, &aCell
[aaSorted
[ii
][kk
]]);
2329 margin
+= cellMargin(pRtree
, &left
);
2330 margin
+= cellMargin(pRtree
, &right
);
2331 overlap
= cellOverlap(pRtree
, &left
, &right
, 1);
2332 area
= cellArea(pRtree
, &left
) + cellArea(pRtree
, &right
);
2333 if( (nLeft
==RTREE_MINCELLS(pRtree
))
2334 || (overlap
<fBestOverlap
)
2335 || (overlap
==fBestOverlap
&& area
<fBestArea
)
2338 fBestOverlap
= overlap
;
2343 if( ii
==0 || margin
<fBestMargin
){
2345 fBestMargin
= margin
;
2346 iBestSplit
= iBestLeft
;
2350 memcpy(pBboxLeft
, &aCell
[aaSorted
[iBestDim
][0]], sizeof(RtreeCell
));
2351 memcpy(pBboxRight
, &aCell
[aaSorted
[iBestDim
][iBestSplit
]], sizeof(RtreeCell
));
2352 for(ii
=0; ii
<nCell
; ii
++){
2353 RtreeNode
*pTarget
= (ii
<iBestSplit
)?pLeft
:pRight
;
2354 RtreeCell
*pBbox
= (ii
<iBestSplit
)?pBboxLeft
:pBboxRight
;
2355 RtreeCell
*pCell
= &aCell
[aaSorted
[iBestDim
][ii
]];
2356 nodeInsertCell(pRtree
, pTarget
, pCell
);
2357 cellUnion(pRtree
, pBbox
, pCell
);
2360 sqlite3_free(aaSorted
);
2365 static int updateMapping(
2371 int (*xSetMapping
)(Rtree
*, sqlite3_int64
, sqlite3_int64
);
2372 xSetMapping
= ((iHeight
==0)?rowidWrite
:parentWrite
);
2374 RtreeNode
*pChild
= nodeHashLookup(pRtree
, iRowid
);
2376 nodeRelease(pRtree
, pChild
->pParent
);
2377 nodeReference(pNode
);
2378 pChild
->pParent
= pNode
;
2381 return xSetMapping(pRtree
, iRowid
, pNode
->iNode
);
2384 static int SplitNode(
2391 int newCellIsRight
= 0;
2394 int nCell
= NCELL(pNode
);
2398 RtreeNode
*pLeft
= 0;
2399 RtreeNode
*pRight
= 0;
2402 RtreeCell rightbbox
;
2404 /* Allocate an array and populate it with a copy of pCell and
2405 ** all cells from node pLeft. Then zero the original node.
2407 aCell
= sqlite3_malloc((sizeof(RtreeCell
)+sizeof(int))*(nCell
+1));
2412 aiUsed
= (int *)&aCell
[nCell
+1];
2413 memset(aiUsed
, 0, sizeof(int)*(nCell
+1));
2414 for(i
=0; i
<nCell
; i
++){
2415 nodeGetCell(pRtree
, pNode
, i
, &aCell
[i
]);
2417 nodeZero(pRtree
, pNode
);
2418 memcpy(&aCell
[nCell
], pCell
, sizeof(RtreeCell
));
2421 if( pNode
->iNode
==1 ){
2422 pRight
= nodeNew(pRtree
, pNode
);
2423 pLeft
= nodeNew(pRtree
, pNode
);
2426 writeInt16(pNode
->zData
, pRtree
->iDepth
);
2429 pRight
= nodeNew(pRtree
, pLeft
->pParent
);
2430 nodeReference(pLeft
);
2433 if( !pLeft
|| !pRight
){
2438 memset(pLeft
->zData
, 0, pRtree
->iNodeSize
);
2439 memset(pRight
->zData
, 0, pRtree
->iNodeSize
);
2441 rc
= splitNodeStartree(pRtree
, aCell
, nCell
, pLeft
, pRight
,
2442 &leftbbox
, &rightbbox
);
2443 if( rc
!=SQLITE_OK
){
2447 /* Ensure both child nodes have node numbers assigned to them by calling
2448 ** nodeWrite(). Node pRight always needs a node number, as it was created
2449 ** by nodeNew() above. But node pLeft sometimes already has a node number.
2450 ** In this case avoid the all to nodeWrite().
2452 if( SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pRight
))
2453 || (0==pLeft
->iNode
&& SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pLeft
)))
2458 rightbbox
.iRowid
= pRight
->iNode
;
2459 leftbbox
.iRowid
= pLeft
->iNode
;
2461 if( pNode
->iNode
==1 ){
2462 rc
= rtreeInsertCell(pRtree
, pLeft
->pParent
, &leftbbox
, iHeight
+1);
2463 if( rc
!=SQLITE_OK
){
2467 RtreeNode
*pParent
= pLeft
->pParent
;
2469 rc
= nodeParentIndex(pRtree
, pLeft
, &iCell
);
2470 if( rc
==SQLITE_OK
){
2471 nodeOverwriteCell(pRtree
, pParent
, &leftbbox
, iCell
);
2472 rc
= AdjustTree(pRtree
, pParent
, &leftbbox
);
2474 if( rc
!=SQLITE_OK
){
2478 if( (rc
= rtreeInsertCell(pRtree
, pRight
->pParent
, &rightbbox
, iHeight
+1)) ){
2482 for(i
=0; i
<NCELL(pRight
); i
++){
2483 i64 iRowid
= nodeGetRowid(pRtree
, pRight
, i
);
2484 rc
= updateMapping(pRtree
, iRowid
, pRight
, iHeight
);
2485 if( iRowid
==pCell
->iRowid
){
2488 if( rc
!=SQLITE_OK
){
2492 if( pNode
->iNode
==1 ){
2493 for(i
=0; i
<NCELL(pLeft
); i
++){
2494 i64 iRowid
= nodeGetRowid(pRtree
, pLeft
, i
);
2495 rc
= updateMapping(pRtree
, iRowid
, pLeft
, iHeight
);
2496 if( rc
!=SQLITE_OK
){
2500 }else if( newCellIsRight
==0 ){
2501 rc
= updateMapping(pRtree
, pCell
->iRowid
, pLeft
, iHeight
);
2504 if( rc
==SQLITE_OK
){
2505 rc
= nodeRelease(pRtree
, pRight
);
2508 if( rc
==SQLITE_OK
){
2509 rc
= nodeRelease(pRtree
, pLeft
);
2514 nodeRelease(pRtree
, pRight
);
2515 nodeRelease(pRtree
, pLeft
);
2516 sqlite3_free(aCell
);
2521 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2522 ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2523 ** the pLeaf->pParent chain all the way up to the root node.
2525 ** This operation is required when a row is deleted (or updated - an update
2526 ** is implemented as a delete followed by an insert). SQLite provides the
2527 ** rowid of the row to delete, which can be used to find the leaf on which
2528 ** the entry resides (argument pLeaf). Once the leaf is located, this
2529 ** function is called to determine its ancestry.
2531 static int fixLeafParent(Rtree
*pRtree
, RtreeNode
*pLeaf
){
2533 RtreeNode
*pChild
= pLeaf
;
2534 while( rc
==SQLITE_OK
&& pChild
->iNode
!=1 && pChild
->pParent
==0 ){
2535 int rc2
= SQLITE_OK
; /* sqlite3_reset() return code */
2536 sqlite3_bind_int64(pRtree
->pReadParent
, 1, pChild
->iNode
);
2537 rc
= sqlite3_step(pRtree
->pReadParent
);
2538 if( rc
==SQLITE_ROW
){
2539 RtreeNode
*pTest
; /* Used to test for reference loops */
2540 i64 iNode
; /* Node number of parent node */
2542 /* Before setting pChild->pParent, test that we are not creating a
2543 ** loop of references (as we would if, say, pChild==pParent). We don't
2544 ** want to do this as it leads to a memory leak when trying to delete
2545 ** the referenced counted node structures.
2547 iNode
= sqlite3_column_int64(pRtree
->pReadParent
, 0);
2548 for(pTest
=pLeaf
; pTest
&& pTest
->iNode
!=iNode
; pTest
=pTest
->pParent
);
2550 rc2
= nodeAcquire(pRtree
, iNode
, 0, &pChild
->pParent
);
2553 rc
= sqlite3_reset(pRtree
->pReadParent
);
2554 if( rc
==SQLITE_OK
) rc
= rc2
;
2555 if( rc
==SQLITE_OK
&& !pChild
->pParent
) rc
= SQLITE_CORRUPT_VTAB
;
2556 pChild
= pChild
->pParent
;
2561 static int deleteCell(Rtree
*, RtreeNode
*, int, int);
2563 static int removeNode(Rtree
*pRtree
, RtreeNode
*pNode
, int iHeight
){
2566 RtreeNode
*pParent
= 0;
2569 assert( pNode
->nRef
==1 );
2571 /* Remove the entry in the parent cell. */
2572 rc
= nodeParentIndex(pRtree
, pNode
, &iCell
);
2573 if( rc
==SQLITE_OK
){
2574 pParent
= pNode
->pParent
;
2576 rc
= deleteCell(pRtree
, pParent
, iCell
, iHeight
+1);
2578 rc2
= nodeRelease(pRtree
, pParent
);
2579 if( rc
==SQLITE_OK
){
2582 if( rc
!=SQLITE_OK
){
2586 /* Remove the xxx_node entry. */
2587 sqlite3_bind_int64(pRtree
->pDeleteNode
, 1, pNode
->iNode
);
2588 sqlite3_step(pRtree
->pDeleteNode
);
2589 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteNode
)) ){
2593 /* Remove the xxx_parent entry. */
2594 sqlite3_bind_int64(pRtree
->pDeleteParent
, 1, pNode
->iNode
);
2595 sqlite3_step(pRtree
->pDeleteParent
);
2596 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteParent
)) ){
2600 /* Remove the node from the in-memory hash table and link it into
2601 ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2603 nodeHashDelete(pRtree
, pNode
);
2604 pNode
->iNode
= iHeight
;
2605 pNode
->pNext
= pRtree
->pDeleted
;
2607 pRtree
->pDeleted
= pNode
;
2612 static int fixBoundingBox(Rtree
*pRtree
, RtreeNode
*pNode
){
2613 RtreeNode
*pParent
= pNode
->pParent
;
2617 int nCell
= NCELL(pNode
);
2618 RtreeCell box
; /* Bounding box for pNode */
2619 nodeGetCell(pRtree
, pNode
, 0, &box
);
2620 for(ii
=1; ii
<nCell
; ii
++){
2622 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2623 cellUnion(pRtree
, &box
, &cell
);
2625 box
.iRowid
= pNode
->iNode
;
2626 rc
= nodeParentIndex(pRtree
, pNode
, &ii
);
2627 if( rc
==SQLITE_OK
){
2628 nodeOverwriteCell(pRtree
, pParent
, &box
, ii
);
2629 rc
= fixBoundingBox(pRtree
, pParent
);
2636 ** Delete the cell at index iCell of node pNode. After removing the
2637 ** cell, adjust the r-tree data structure if required.
2639 static int deleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
, int iHeight
){
2643 if( SQLITE_OK
!=(rc
= fixLeafParent(pRtree
, pNode
)) ){
2647 /* Remove the cell from the node. This call just moves bytes around
2648 ** the in-memory node image, so it cannot fail.
2650 nodeDeleteCell(pRtree
, pNode
, iCell
);
2652 /* If the node is not the tree root and now has less than the minimum
2653 ** number of cells, remove it from the tree. Otherwise, update the
2654 ** cell in the parent node so that it tightly contains the updated
2657 pParent
= pNode
->pParent
;
2658 assert( pParent
|| pNode
->iNode
==1 );
2660 if( NCELL(pNode
)<RTREE_MINCELLS(pRtree
) ){
2661 rc
= removeNode(pRtree
, pNode
, iHeight
);
2663 rc
= fixBoundingBox(pRtree
, pNode
);
2670 static int Reinsert(
2679 RtreeDValue
*aDistance
;
2681 RtreeDValue aCenterCoord
[RTREE_MAX_DIMENSIONS
];
2687 memset(aCenterCoord
, 0, sizeof(RtreeDValue
)*RTREE_MAX_DIMENSIONS
);
2689 nCell
= NCELL(pNode
)+1;
2692 /* Allocate the buffers used by this operation. The allocation is
2693 ** relinquished before this function returns.
2695 aCell
= (RtreeCell
*)sqlite3_malloc(n
* (
2696 sizeof(RtreeCell
) + /* aCell array */
2697 sizeof(int) + /* aOrder array */
2698 sizeof(int) + /* aSpare array */
2699 sizeof(RtreeDValue
) /* aDistance array */
2702 return SQLITE_NOMEM
;
2704 aOrder
= (int *)&aCell
[n
];
2705 aSpare
= (int *)&aOrder
[n
];
2706 aDistance
= (RtreeDValue
*)&aSpare
[n
];
2708 for(ii
=0; ii
<nCell
; ii
++){
2709 if( ii
==(nCell
-1) ){
2710 memcpy(&aCell
[ii
], pCell
, sizeof(RtreeCell
));
2712 nodeGetCell(pRtree
, pNode
, ii
, &aCell
[ii
]);
2715 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2716 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2]);
2717 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]);
2720 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2721 aCenterCoord
[iDim
] = (aCenterCoord
[iDim
]/(nCell
*(RtreeDValue
)2));
2724 for(ii
=0; ii
<nCell
; ii
++){
2725 aDistance
[ii
] = RTREE_ZERO
;
2726 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2727 RtreeDValue coord
= (DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]) -
2728 DCOORD(aCell
[ii
].aCoord
[iDim
*2]));
2729 aDistance
[ii
] += (coord
-aCenterCoord
[iDim
])*(coord
-aCenterCoord
[iDim
]);
2733 SortByDistance(aOrder
, nCell
, aDistance
, aSpare
);
2734 nodeZero(pRtree
, pNode
);
2736 for(ii
=0; rc
==SQLITE_OK
&& ii
<(nCell
-(RTREE_MINCELLS(pRtree
)+1)); ii
++){
2737 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2738 nodeInsertCell(pRtree
, pNode
, p
);
2739 if( p
->iRowid
==pCell
->iRowid
){
2741 rc
= rowidWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2743 rc
= parentWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2747 if( rc
==SQLITE_OK
){
2748 rc
= fixBoundingBox(pRtree
, pNode
);
2750 for(; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2751 /* Find a node to store this cell in. pNode->iNode currently contains
2752 ** the height of the sub-tree headed by the cell.
2755 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2756 rc
= ChooseLeaf(pRtree
, p
, iHeight
, &pInsert
);
2757 if( rc
==SQLITE_OK
){
2759 rc
= rtreeInsertCell(pRtree
, pInsert
, p
, iHeight
);
2760 rc2
= nodeRelease(pRtree
, pInsert
);
2761 if( rc
==SQLITE_OK
){
2767 sqlite3_free(aCell
);
2772 ** Insert cell pCell into node pNode. Node pNode is the head of a
2773 ** subtree iHeight high (leaf nodes have iHeight==0).
2775 static int rtreeInsertCell(
2783 RtreeNode
*pChild
= nodeHashLookup(pRtree
, pCell
->iRowid
);
2785 nodeRelease(pRtree
, pChild
->pParent
);
2786 nodeReference(pNode
);
2787 pChild
->pParent
= pNode
;
2790 if( nodeInsertCell(pRtree
, pNode
, pCell
) ){
2791 if( iHeight
<=pRtree
->iReinsertHeight
|| pNode
->iNode
==1){
2792 rc
= SplitNode(pRtree
, pNode
, pCell
, iHeight
);
2794 pRtree
->iReinsertHeight
= iHeight
;
2795 rc
= Reinsert(pRtree
, pNode
, pCell
, iHeight
);
2798 rc
= AdjustTree(pRtree
, pNode
, pCell
);
2799 if( rc
==SQLITE_OK
){
2801 rc
= rowidWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2803 rc
= parentWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2810 static int reinsertNodeContent(Rtree
*pRtree
, RtreeNode
*pNode
){
2813 int nCell
= NCELL(pNode
);
2815 for(ii
=0; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2818 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2820 /* Find a node to store this cell in. pNode->iNode currently contains
2821 ** the height of the sub-tree headed by the cell.
2823 rc
= ChooseLeaf(pRtree
, &cell
, (int)pNode
->iNode
, &pInsert
);
2824 if( rc
==SQLITE_OK
){
2826 rc
= rtreeInsertCell(pRtree
, pInsert
, &cell
, (int)pNode
->iNode
);
2827 rc2
= nodeRelease(pRtree
, pInsert
);
2828 if( rc
==SQLITE_OK
){
2837 ** Select a currently unused rowid for a new r-tree record.
2839 static int newRowid(Rtree
*pRtree
, i64
*piRowid
){
2841 sqlite3_bind_null(pRtree
->pWriteRowid
, 1);
2842 sqlite3_bind_null(pRtree
->pWriteRowid
, 2);
2843 sqlite3_step(pRtree
->pWriteRowid
);
2844 rc
= sqlite3_reset(pRtree
->pWriteRowid
);
2845 *piRowid
= sqlite3_last_insert_rowid(pRtree
->db
);
2850 ** Remove the entry with rowid=iDelete from the r-tree structure.
2852 static int rtreeDeleteRowid(Rtree
*pRtree
, sqlite3_int64 iDelete
){
2853 int rc
; /* Return code */
2854 RtreeNode
*pLeaf
= 0; /* Leaf node containing record iDelete */
2855 int iCell
; /* Index of iDelete cell in pLeaf */
2856 RtreeNode
*pRoot
= 0; /* Root node of rtree structure */
2859 /* Obtain a reference to the root node to initialize Rtree.iDepth */
2860 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
2862 /* Obtain a reference to the leaf node that contains the entry
2863 ** about to be deleted.
2865 if( rc
==SQLITE_OK
){
2866 rc
= findLeafNode(pRtree
, iDelete
, &pLeaf
, 0);
2869 /* Delete the cell in question from the leaf node. */
2870 if( rc
==SQLITE_OK
){
2872 rc
= nodeRowidIndex(pRtree
, pLeaf
, iDelete
, &iCell
);
2873 if( rc
==SQLITE_OK
){
2874 rc
= deleteCell(pRtree
, pLeaf
, iCell
, 0);
2876 rc2
= nodeRelease(pRtree
, pLeaf
);
2877 if( rc
==SQLITE_OK
){
2882 /* Delete the corresponding entry in the <rtree>_rowid table. */
2883 if( rc
==SQLITE_OK
){
2884 sqlite3_bind_int64(pRtree
->pDeleteRowid
, 1, iDelete
);
2885 sqlite3_step(pRtree
->pDeleteRowid
);
2886 rc
= sqlite3_reset(pRtree
->pDeleteRowid
);
2889 /* Check if the root node now has exactly one child. If so, remove
2890 ** it, schedule the contents of the child for reinsertion and
2891 ** reduce the tree height by one.
2893 ** This is equivalent to copying the contents of the child into
2894 ** the root node (the operation that Gutman's paper says to perform
2895 ** in this scenario).
2897 if( rc
==SQLITE_OK
&& pRtree
->iDepth
>0 && NCELL(pRoot
)==1 ){
2900 i64 iChild
= nodeGetRowid(pRtree
, pRoot
, 0);
2901 rc
= nodeAcquire(pRtree
, iChild
, pRoot
, &pChild
);
2902 if( rc
==SQLITE_OK
){
2903 rc
= removeNode(pRtree
, pChild
, pRtree
->iDepth
-1);
2905 rc2
= nodeRelease(pRtree
, pChild
);
2906 if( rc
==SQLITE_OK
) rc
= rc2
;
2907 if( rc
==SQLITE_OK
){
2909 writeInt16(pRoot
->zData
, pRtree
->iDepth
);
2914 /* Re-insert the contents of any underfull nodes removed from the tree. */
2915 for(pLeaf
=pRtree
->pDeleted
; pLeaf
; pLeaf
=pRtree
->pDeleted
){
2916 if( rc
==SQLITE_OK
){
2917 rc
= reinsertNodeContent(pRtree
, pLeaf
);
2919 pRtree
->pDeleted
= pLeaf
->pNext
;
2920 sqlite3_free(pLeaf
);
2923 /* Release the reference to the root node. */
2924 if( rc
==SQLITE_OK
){
2925 rc
= nodeRelease(pRtree
, pRoot
);
2927 nodeRelease(pRtree
, pRoot
);
2934 ** Rounding constants for float->double conversion.
2936 #define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */
2937 #define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */
2939 #if !defined(SQLITE_RTREE_INT_ONLY)
2941 ** Convert an sqlite3_value into an RtreeValue (presumably a float)
2942 ** while taking care to round toward negative or positive, respectively.
2944 static RtreeValue
rtreeValueDown(sqlite3_value
*v
){
2945 double d
= sqlite3_value_double(v
);
2948 f
= (float)(d
*(d
<0 ? RNDAWAY
: RNDTOWARDS
));
2952 static RtreeValue
rtreeValueUp(sqlite3_value
*v
){
2953 double d
= sqlite3_value_double(v
);
2956 f
= (float)(d
*(d
<0 ? RNDTOWARDS
: RNDAWAY
));
2960 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */
2963 ** A constraint has failed while inserting a row into an rtree table.
2964 ** Assuming no OOM error occurs, this function sets the error message
2965 ** (at pRtree->base.zErrMsg) to an appropriate value and returns
2966 ** SQLITE_CONSTRAINT.
2968 ** Parameter iCol is the index of the leftmost column involved in the
2969 ** constraint failure. If it is 0, then the constraint that failed is
2970 ** the unique constraint on the id column. Otherwise, it is the rtree
2971 ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed.
2973 ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT.
2975 static int rtreeConstraintError(Rtree
*pRtree
, int iCol
){
2976 sqlite3_stmt
*pStmt
= 0;
2980 assert( iCol
==0 || iCol
%2 );
2981 zSql
= sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree
->zDb
, pRtree
->zName
);
2983 rc
= sqlite3_prepare_v2(pRtree
->db
, zSql
, -1, &pStmt
, 0);
2989 if( rc
==SQLITE_OK
){
2991 const char *zCol
= sqlite3_column_name(pStmt
, 0);
2992 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
2993 "UNIQUE constraint failed: %s.%s", pRtree
->zName
, zCol
2996 const char *zCol1
= sqlite3_column_name(pStmt
, iCol
);
2997 const char *zCol2
= sqlite3_column_name(pStmt
, iCol
+1);
2998 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
2999 "rtree constraint failed: %s.(%s<=%s)", pRtree
->zName
, zCol1
, zCol2
3004 sqlite3_finalize(pStmt
);
3005 return (rc
==SQLITE_OK
? SQLITE_CONSTRAINT
: rc
);
3011 ** The xUpdate method for rtree module virtual tables.
3013 static int rtreeUpdate(
3014 sqlite3_vtab
*pVtab
,
3016 sqlite3_value
**azData
,
3017 sqlite_int64
*pRowid
3019 Rtree
*pRtree
= (Rtree
*)pVtab
;
3021 RtreeCell cell
; /* New cell to insert if nData>1 */
3022 int bHaveRowid
= 0; /* Set to 1 after new rowid is determined */
3024 rtreeReference(pRtree
);
3027 cell
.iRowid
= 0; /* Used only to suppress a compiler warning */
3029 /* Constraint handling. A write operation on an r-tree table may return
3030 ** SQLITE_CONSTRAINT for two reasons:
3032 ** 1. A duplicate rowid value, or
3033 ** 2. The supplied data violates the "x2>=x1" constraint.
3035 ** In the first case, if the conflict-handling mode is REPLACE, then
3036 ** the conflicting row can be removed before proceeding. In the second
3037 ** case, SQLITE_CONSTRAINT must be returned regardless of the
3038 ** conflict-handling mode specified by the user.
3043 /* Populate the cell.aCoord[] array. The first coordinate is azData[3].
3045 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
3046 ** with "column" that are interpreted as table constraints.
3047 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
3048 ** This problem was discovered after years of use, so we silently ignore
3049 ** these kinds of misdeclared tables to avoid breaking any legacy.
3051 assert( nData
<=(pRtree
->nDim2
+ 3) );
3053 #ifndef SQLITE_RTREE_INT_ONLY
3054 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
3055 for(ii
=0; ii
<nData
-4; ii
+=2){
3056 cell
.aCoord
[ii
].f
= rtreeValueDown(azData
[ii
+3]);
3057 cell
.aCoord
[ii
+1].f
= rtreeValueUp(azData
[ii
+4]);
3058 if( cell
.aCoord
[ii
].f
>cell
.aCoord
[ii
+1].f
){
3059 rc
= rtreeConstraintError(pRtree
, ii
+1);
3066 for(ii
=0; ii
<nData
-4; ii
+=2){
3067 cell
.aCoord
[ii
].i
= sqlite3_value_int(azData
[ii
+3]);
3068 cell
.aCoord
[ii
+1].i
= sqlite3_value_int(azData
[ii
+4]);
3069 if( cell
.aCoord
[ii
].i
>cell
.aCoord
[ii
+1].i
){
3070 rc
= rtreeConstraintError(pRtree
, ii
+1);
3076 /* If a rowid value was supplied, check if it is already present in
3077 ** the table. If so, the constraint has failed. */
3078 if( sqlite3_value_type(azData
[2])!=SQLITE_NULL
){
3079 cell
.iRowid
= sqlite3_value_int64(azData
[2]);
3080 if( sqlite3_value_type(azData
[0])==SQLITE_NULL
3081 || sqlite3_value_int64(azData
[0])!=cell
.iRowid
3084 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, cell
.iRowid
);
3085 steprc
= sqlite3_step(pRtree
->pReadRowid
);
3086 rc
= sqlite3_reset(pRtree
->pReadRowid
);
3087 if( SQLITE_ROW
==steprc
){
3088 if( sqlite3_vtab_on_conflict(pRtree
->db
)==SQLITE_REPLACE
){
3089 rc
= rtreeDeleteRowid(pRtree
, cell
.iRowid
);
3091 rc
= rtreeConstraintError(pRtree
, 0);
3100 /* If azData[0] is not an SQL NULL value, it is the rowid of a
3101 ** record to delete from the r-tree table. The following block does
3104 if( sqlite3_value_type(azData
[0])!=SQLITE_NULL
){
3105 rc
= rtreeDeleteRowid(pRtree
, sqlite3_value_int64(azData
[0]));
3108 /* If the azData[] array contains more than one element, elements
3109 ** (azData[2]..azData[argc-1]) contain a new record to insert into
3110 ** the r-tree structure.
3112 if( rc
==SQLITE_OK
&& nData
>1 ){
3113 /* Insert the new record into the r-tree */
3114 RtreeNode
*pLeaf
= 0;
3116 /* Figure out the rowid of the new row. */
3117 if( bHaveRowid
==0 ){
3118 rc
= newRowid(pRtree
, &cell
.iRowid
);
3120 *pRowid
= cell
.iRowid
;
3122 if( rc
==SQLITE_OK
){
3123 rc
= ChooseLeaf(pRtree
, &cell
, 0, &pLeaf
);
3125 if( rc
==SQLITE_OK
){
3127 pRtree
->iReinsertHeight
= -1;
3128 rc
= rtreeInsertCell(pRtree
, pLeaf
, &cell
, 0);
3129 rc2
= nodeRelease(pRtree
, pLeaf
);
3130 if( rc
==SQLITE_OK
){
3137 rtreeRelease(pRtree
);
3142 ** Called when a transaction starts.
3144 static int rtreeBeginTransaction(sqlite3_vtab
*pVtab
){
3145 Rtree
*pRtree
= (Rtree
*)pVtab
;
3146 assert( pRtree
->inWrTrans
==0 );
3147 pRtree
->inWrTrans
++;
3152 ** Called when a transaction completes (either by COMMIT or ROLLBACK).
3153 ** The sqlite3_blob object should be released at this point.
3155 static int rtreeEndTransaction(sqlite3_vtab
*pVtab
){
3156 Rtree
*pRtree
= (Rtree
*)pVtab
;
3157 pRtree
->inWrTrans
= 0;
3158 nodeBlobReset(pRtree
);
3163 ** The xRename method for rtree module virtual tables.
3165 static int rtreeRename(sqlite3_vtab
*pVtab
, const char *zNewName
){
3166 Rtree
*pRtree
= (Rtree
*)pVtab
;
3167 int rc
= SQLITE_NOMEM
;
3168 char *zSql
= sqlite3_mprintf(
3169 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
3170 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
3171 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
3172 , pRtree
->zDb
, pRtree
->zName
, zNewName
3173 , pRtree
->zDb
, pRtree
->zName
, zNewName
3174 , pRtree
->zDb
, pRtree
->zName
, zNewName
3177 nodeBlobReset(pRtree
);
3178 rc
= sqlite3_exec(pRtree
->db
, zSql
, 0, 0, 0);
3185 ** The xSavepoint method.
3187 ** This module does not need to do anything to support savepoints. However,
3188 ** it uses this hook to close any open blob handle. This is done because a
3189 ** DROP TABLE command - which fortunately always opens a savepoint - cannot
3190 ** succeed if there are any open blob handles. i.e. if the blob handle were
3191 ** not closed here, the following would fail:
3194 ** INSERT INTO rtree...
3195 ** DROP TABLE <tablename>; -- Would fail with SQLITE_LOCKED
3198 static int rtreeSavepoint(sqlite3_vtab
*pVtab
, int iSavepoint
){
3199 Rtree
*pRtree
= (Rtree
*)pVtab
;
3200 int iwt
= pRtree
->inWrTrans
;
3201 UNUSED_PARAMETER(iSavepoint
);
3202 pRtree
->inWrTrans
= 0;
3203 nodeBlobReset(pRtree
);
3204 pRtree
->inWrTrans
= iwt
;
3209 ** This function populates the pRtree->nRowEst variable with an estimate
3210 ** of the number of rows in the virtual table. If possible, this is based
3211 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
3213 static int rtreeQueryStat1(sqlite3
*db
, Rtree
*pRtree
){
3214 const char *zFmt
= "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
3220 rc
= sqlite3_table_column_metadata(
3221 db
, pRtree
->zDb
, "sqlite_stat1",0,0,0,0,0,0
3223 if( rc
!=SQLITE_OK
){
3224 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3225 return rc
==SQLITE_ERROR
? SQLITE_OK
: rc
;
3227 zSql
= sqlite3_mprintf(zFmt
, pRtree
->zDb
, pRtree
->zName
);
3231 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &p
, 0);
3232 if( rc
==SQLITE_OK
){
3233 if( sqlite3_step(p
)==SQLITE_ROW
) nRow
= sqlite3_column_int64(p
, 0);
3234 rc
= sqlite3_finalize(p
);
3235 }else if( rc
!=SQLITE_NOMEM
){
3239 if( rc
==SQLITE_OK
){
3241 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3243 pRtree
->nRowEst
= MAX(nRow
, RTREE_MIN_ROWEST
);
3252 static sqlite3_module rtreeModule
= {
3254 rtreeCreate
, /* xCreate - create a table */
3255 rtreeConnect
, /* xConnect - connect to an existing table */
3256 rtreeBestIndex
, /* xBestIndex - Determine search strategy */
3257 rtreeDisconnect
, /* xDisconnect - Disconnect from a table */
3258 rtreeDestroy
, /* xDestroy - Drop a table */
3259 rtreeOpen
, /* xOpen - open a cursor */
3260 rtreeClose
, /* xClose - close a cursor */
3261 rtreeFilter
, /* xFilter - configure scan constraints */
3262 rtreeNext
, /* xNext - advance a cursor */
3263 rtreeEof
, /* xEof */
3264 rtreeColumn
, /* xColumn - read data */
3265 rtreeRowid
, /* xRowid - read data */
3266 rtreeUpdate
, /* xUpdate - write data */
3267 rtreeBeginTransaction
, /* xBegin - begin transaction */
3268 rtreeEndTransaction
, /* xSync - sync transaction */
3269 rtreeEndTransaction
, /* xCommit - commit transaction */
3270 rtreeEndTransaction
, /* xRollback - rollback transaction */
3271 0, /* xFindFunction - function overloading */
3272 rtreeRename
, /* xRename - rename the table */
3273 rtreeSavepoint
, /* xSavepoint */
3275 0, /* xRollbackTo */
3278 static int rtreeSqlInit(
3282 const char *zPrefix
,
3287 #define N_STATEMENT 8
3288 static const char *azSql
[N_STATEMENT
] = {
3289 /* Write the xxx_node table */
3290 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
3291 "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
3293 /* Read and write the xxx_rowid table */
3294 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
3295 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
3296 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
3298 /* Read and write the xxx_parent table */
3299 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
3300 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
3301 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
3303 sqlite3_stmt
**appStmt
[N_STATEMENT
];
3309 char *zCreate
= sqlite3_mprintf(
3310 "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
3311 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
3312 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
3313 " parentnode INTEGER);"
3314 "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
3315 zDb
, zPrefix
, zDb
, zPrefix
, zDb
, zPrefix
, zDb
, zPrefix
, pRtree
->iNodeSize
3318 return SQLITE_NOMEM
;
3320 rc
= sqlite3_exec(db
, zCreate
, 0, 0, 0);
3321 sqlite3_free(zCreate
);
3322 if( rc
!=SQLITE_OK
){
3327 appStmt
[0] = &pRtree
->pWriteNode
;
3328 appStmt
[1] = &pRtree
->pDeleteNode
;
3329 appStmt
[2] = &pRtree
->pReadRowid
;
3330 appStmt
[3] = &pRtree
->pWriteRowid
;
3331 appStmt
[4] = &pRtree
->pDeleteRowid
;
3332 appStmt
[5] = &pRtree
->pReadParent
;
3333 appStmt
[6] = &pRtree
->pWriteParent
;
3334 appStmt
[7] = &pRtree
->pDeleteParent
;
3336 rc
= rtreeQueryStat1(db
, pRtree
);
3337 for(i
=0; i
<N_STATEMENT
&& rc
==SQLITE_OK
; i
++){
3338 char *zSql
= sqlite3_mprintf(azSql
[i
], zDb
, zPrefix
);
3340 rc
= sqlite3_prepare_v3(db
, zSql
, -1, SQLITE_PREPARE_PERSISTENT
,
3352 ** The second argument to this function contains the text of an SQL statement
3353 ** that returns a single integer value. The statement is compiled and executed
3354 ** using database connection db. If successful, the integer value returned
3355 ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
3356 ** code is returned and the value of *piVal after returning is not defined.
3358 static int getIntFromStmt(sqlite3
*db
, const char *zSql
, int *piVal
){
3359 int rc
= SQLITE_NOMEM
;
3361 sqlite3_stmt
*pStmt
= 0;
3362 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &pStmt
, 0);
3363 if( rc
==SQLITE_OK
){
3364 if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
3365 *piVal
= sqlite3_column_int(pStmt
, 0);
3367 rc
= sqlite3_finalize(pStmt
);
3374 ** This function is called from within the xConnect() or xCreate() method to
3375 ** determine the node-size used by the rtree table being created or connected
3376 ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
3377 ** Otherwise, an SQLite error code is returned.
3379 ** If this function is being called as part of an xConnect(), then the rtree
3380 ** table already exists. In this case the node-size is determined by inspecting
3381 ** the root node of the tree.
3383 ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
3384 ** This ensures that each node is stored on a single database page. If the
3385 ** database page-size is so large that more than RTREE_MAXCELLS entries
3386 ** would fit in a single node, use a smaller node-size.
3388 static int getNodeSize(
3389 sqlite3
*db
, /* Database handle */
3390 Rtree
*pRtree
, /* Rtree handle */
3391 int isCreate
, /* True for xCreate, false for xConnect */
3392 char **pzErr
/* OUT: Error message, if any */
3398 zSql
= sqlite3_mprintf("PRAGMA %Q.page_size", pRtree
->zDb
);
3399 rc
= getIntFromStmt(db
, zSql
, &iPageSize
);
3400 if( rc
==SQLITE_OK
){
3401 pRtree
->iNodeSize
= iPageSize
-64;
3402 if( (4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
)<pRtree
->iNodeSize
){
3403 pRtree
->iNodeSize
= 4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
;
3406 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3409 zSql
= sqlite3_mprintf(
3410 "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
3411 pRtree
->zDb
, pRtree
->zName
3413 rc
= getIntFromStmt(db
, zSql
, &pRtree
->iNodeSize
);
3414 if( rc
!=SQLITE_OK
){
3415 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3416 }else if( pRtree
->iNodeSize
<(512-64) ){
3417 rc
= SQLITE_CORRUPT_VTAB
;
3418 *pzErr
= sqlite3_mprintf("undersize RTree blobs in \"%q_node\"",
3428 ** This function is the implementation of both the xConnect and xCreate
3429 ** methods of the r-tree virtual table.
3431 ** argv[0] -> module name
3432 ** argv[1] -> database name
3433 ** argv[2] -> table name
3434 ** argv[...] -> column names...
3436 static int rtreeInit(
3437 sqlite3
*db
, /* Database connection */
3438 void *pAux
, /* One of the RTREE_COORD_* constants */
3439 int argc
, const char *const*argv
, /* Parameters to CREATE TABLE statement */
3440 sqlite3_vtab
**ppVtab
, /* OUT: New virtual table */
3441 char **pzErr
, /* OUT: Error message, if any */
3442 int isCreate
/* True for xCreate, false for xConnect */
3446 int nDb
; /* Length of string argv[1] */
3447 int nName
; /* Length of string argv[2] */
3448 int eCoordType
= (pAux
? RTREE_COORD_INT32
: RTREE_COORD_REAL32
);
3450 const char *aErrMsg
[] = {
3452 "Wrong number of columns for an rtree table", /* 1 */
3453 "Too few columns for an rtree table", /* 2 */
3454 "Too many columns for an rtree table" /* 3 */
3457 int iErr
= (argc
<6) ? 2 : argc
>(RTREE_MAX_DIMENSIONS
*2+4) ? 3 : argc
%2;
3458 if( aErrMsg
[iErr
] ){
3459 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[iErr
]);
3460 return SQLITE_ERROR
;
3463 sqlite3_vtab_config(db
, SQLITE_VTAB_CONSTRAINT_SUPPORT
, 1);
3465 /* Allocate the sqlite3_vtab structure */
3466 nDb
= (int)strlen(argv
[1]);
3467 nName
= (int)strlen(argv
[2]);
3468 pRtree
= (Rtree
*)sqlite3_malloc(sizeof(Rtree
)+nDb
+nName
+2);
3470 return SQLITE_NOMEM
;
3472 memset(pRtree
, 0, sizeof(Rtree
)+nDb
+nName
+2);
3474 pRtree
->base
.pModule
= &rtreeModule
;
3475 pRtree
->zDb
= (char *)&pRtree
[1];
3476 pRtree
->zName
= &pRtree
->zDb
[nDb
+1];
3477 pRtree
->nDim
= (u8
)((argc
-4)/2);
3478 pRtree
->nDim2
= pRtree
->nDim
*2;
3479 pRtree
->nBytesPerCell
= 8 + pRtree
->nDim2
*4;
3480 pRtree
->eCoordType
= (u8
)eCoordType
;
3481 memcpy(pRtree
->zDb
, argv
[1], nDb
);
3482 memcpy(pRtree
->zName
, argv
[2], nName
);
3484 /* Figure out the node size to use. */
3485 rc
= getNodeSize(db
, pRtree
, isCreate
, pzErr
);
3487 /* Create/Connect to the underlying relational database schema. If
3488 ** that is successful, call sqlite3_declare_vtab() to configure
3489 ** the r-tree table schema.
3491 if( rc
==SQLITE_OK
){
3492 if( (rc
= rtreeSqlInit(pRtree
, db
, argv
[1], argv
[2], isCreate
)) ){
3493 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3495 char *zSql
= sqlite3_mprintf("CREATE TABLE x(%s", argv
[3]);
3498 for(ii
=4; zSql
&& ii
<argc
; ii
++){
3500 zSql
= sqlite3_mprintf("%s, %s", zTmp
, argv
[ii
]);
3505 zSql
= sqlite3_mprintf("%s);", zTmp
);
3510 }else if( SQLITE_OK
!=(rc
= sqlite3_declare_vtab(db
, zSql
)) ){
3511 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3517 if( rc
==SQLITE_OK
){
3518 *ppVtab
= (sqlite3_vtab
*)pRtree
;
3520 assert( *ppVtab
==0 );
3521 assert( pRtree
->nBusy
==1 );
3522 rtreeRelease(pRtree
);
3529 ** Implementation of a scalar function that decodes r-tree nodes to
3530 ** human readable strings. This can be used for debugging and analysis.
3532 ** The scalar function takes two arguments: (1) the number of dimensions
3533 ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
3534 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
3535 ** deserialize all nodes, a statement like:
3537 ** SELECT rtreenode(2, data) FROM rt_node;
3539 ** The human readable string takes the form of a Tcl list with one
3540 ** entry for each cell in the r-tree node. Each entry is itself a
3541 ** list, containing the 8-byte rowid/pageno followed by the
3542 ** <num-dimension>*2 coordinates.
3544 static void rtreenode(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3550 UNUSED_PARAMETER(nArg
);
3551 memset(&node
, 0, sizeof(RtreeNode
));
3552 memset(&tree
, 0, sizeof(Rtree
));
3553 tree
.nDim
= (u8
)sqlite3_value_int(apArg
[0]);
3554 tree
.nDim2
= tree
.nDim
*2;
3555 tree
.nBytesPerCell
= 8 + 8 * tree
.nDim
;
3556 node
.zData
= (u8
*)sqlite3_value_blob(apArg
[1]);
3558 for(ii
=0; ii
<NCELL(&node
); ii
++){
3564 nodeGetCell(&tree
, &node
, ii
, &cell
);
3565 sqlite3_snprintf(512-nCell
,&zCell
[nCell
],"%lld", cell
.iRowid
);
3566 nCell
= (int)strlen(zCell
);
3567 for(jj
=0; jj
<tree
.nDim2
; jj
++){
3568 #ifndef SQLITE_RTREE_INT_ONLY
3569 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %g",
3570 (double)cell
.aCoord
[jj
].f
);
3572 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %d",
3575 nCell
= (int)strlen(zCell
);
3579 char *zTextNew
= sqlite3_mprintf("%s {%s}", zText
, zCell
);
3580 sqlite3_free(zText
);
3583 zText
= sqlite3_mprintf("{%s}", zCell
);
3587 sqlite3_result_text(ctx
, zText
, -1, sqlite3_free
);
3590 /* This routine implements an SQL function that returns the "depth" parameter
3591 ** from the front of a blob that is an r-tree node. For example:
3593 ** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
3595 ** The depth value is 0 for all nodes other than the root node, and the root
3596 ** node always has nodeno=1, so the example above is the primary use for this
3597 ** routine. This routine is intended for testing and analysis only.
3599 static void rtreedepth(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3600 UNUSED_PARAMETER(nArg
);
3601 if( sqlite3_value_type(apArg
[0])!=SQLITE_BLOB
3602 || sqlite3_value_bytes(apArg
[0])<2
3604 sqlite3_result_error(ctx
, "Invalid argument to rtreedepth()", -1);
3606 u8
*zBlob
= (u8
*)sqlite3_value_blob(apArg
[0]);
3607 sqlite3_result_int(ctx
, readInt16(zBlob
));
3612 ** Context object passed between the various routines that make up the
3613 ** implementation of integrity-check function rtreecheck().
3615 typedef struct RtreeCheck RtreeCheck
;
3617 sqlite3
*db
; /* Database handle */
3618 const char *zDb
; /* Database containing rtree table */
3619 const char *zTab
; /* Name of rtree table */
3620 int bInt
; /* True for rtree_i32 table */
3621 int nDim
; /* Number of dimensions for this rtree tbl */
3622 sqlite3_stmt
*pGetNode
; /* Statement used to retrieve nodes */
3623 sqlite3_stmt
*aCheckMapping
[2]; /* Statements to query %_parent/%_rowid */
3624 int nLeaf
; /* Number of leaf cells in table */
3625 int nNonLeaf
; /* Number of non-leaf cells in table */
3626 int rc
; /* Return code */
3627 char *zReport
; /* Message to report */
3628 int nErr
; /* Number of lines in zReport */
3631 #define RTREE_CHECK_MAX_ERROR 100
3634 ** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
3635 ** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
3637 static void rtreeCheckReset(RtreeCheck
*pCheck
, sqlite3_stmt
*pStmt
){
3638 int rc
= sqlite3_reset(pStmt
);
3639 if( pCheck
->rc
==SQLITE_OK
) pCheck
->rc
= rc
;
3643 ** The second and subsequent arguments to this function are a format string
3644 ** and printf style arguments. This function formats the string and attempts
3645 ** to compile it as an SQL statement.
3647 ** If successful, a pointer to the new SQL statement is returned. Otherwise,
3648 ** NULL is returned and an error code left in RtreeCheck.rc.
3650 static sqlite3_stmt
*rtreeCheckPrepare(
3651 RtreeCheck
*pCheck
, /* RtreeCheck object */
3652 const char *zFmt
, ... /* Format string and trailing args */
3656 sqlite3_stmt
*pRet
= 0;
3659 z
= sqlite3_vmprintf(zFmt
, ap
);
3661 if( pCheck
->rc
==SQLITE_OK
){
3663 pCheck
->rc
= SQLITE_NOMEM
;
3665 pCheck
->rc
= sqlite3_prepare_v2(pCheck
->db
, z
, -1, &pRet
, 0);
3675 ** The second and subsequent arguments to this function are a printf()
3676 ** style format string and arguments. This function formats the string and
3677 ** appends it to the report being accumuated in pCheck.
3679 static void rtreeCheckAppendMsg(RtreeCheck
*pCheck
, const char *zFmt
, ...){
3682 if( pCheck
->rc
==SQLITE_OK
&& pCheck
->nErr
<RTREE_CHECK_MAX_ERROR
){
3683 char *z
= sqlite3_vmprintf(zFmt
, ap
);
3685 pCheck
->rc
= SQLITE_NOMEM
;
3687 pCheck
->zReport
= sqlite3_mprintf("%z%s%z",
3688 pCheck
->zReport
, (pCheck
->zReport
? "\n" : ""), z
3690 if( pCheck
->zReport
==0 ){
3691 pCheck
->rc
= SQLITE_NOMEM
;
3700 ** This function is a no-op if there is already an error code stored
3701 ** in the RtreeCheck object indicated by the first argument. NULL is
3702 ** returned in this case.
3704 ** Otherwise, the contents of rtree table node iNode are loaded from
3705 ** the database and copied into a buffer obtained from sqlite3_malloc().
3706 ** If no error occurs, a pointer to the buffer is returned and (*pnNode)
3707 ** is set to the size of the buffer in bytes.
3709 ** Or, if an error does occur, NULL is returned and an error code left
3710 ** in the RtreeCheck object. The final value of *pnNode is undefined in
3713 static u8
*rtreeCheckGetNode(RtreeCheck
*pCheck
, i64 iNode
, int *pnNode
){
3714 u8
*pRet
= 0; /* Return value */
3716 assert( pCheck
->rc
==SQLITE_OK
);
3717 if( pCheck
->pGetNode
==0 ){
3718 pCheck
->pGetNode
= rtreeCheckPrepare(pCheck
,
3719 "SELECT data FROM %Q.'%q_node' WHERE nodeno=?",
3720 pCheck
->zDb
, pCheck
->zTab
3724 if( pCheck
->rc
==SQLITE_OK
){
3725 sqlite3_bind_int64(pCheck
->pGetNode
, 1, iNode
);
3726 if( sqlite3_step(pCheck
->pGetNode
)==SQLITE_ROW
){
3727 int nNode
= sqlite3_column_bytes(pCheck
->pGetNode
, 0);
3728 const u8
*pNode
= (const u8
*)sqlite3_column_blob(pCheck
->pGetNode
, 0);
3729 pRet
= sqlite3_malloc(nNode
);
3731 pCheck
->rc
= SQLITE_NOMEM
;
3733 memcpy(pRet
, pNode
, nNode
);
3737 rtreeCheckReset(pCheck
, pCheck
->pGetNode
);
3738 if( pCheck
->rc
==SQLITE_OK
&& pRet
==0 ){
3739 rtreeCheckAppendMsg(pCheck
, "Node %lld missing from database", iNode
);
3747 ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
3748 ** (if bLeaf==1) table contains a specified entry. The schemas of the
3751 ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
3752 ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
3754 ** In both cases, this function checks that there exists an entry with
3755 ** IPK value iKey and the second column set to iVal.
3758 static void rtreeCheckMapping(
3759 RtreeCheck
*pCheck
, /* RtreeCheck object */
3760 int bLeaf
, /* True for a leaf cell, false for interior */
3761 i64 iKey
, /* Key for mapping */
3762 i64 iVal
/* Expected value for mapping */
3765 sqlite3_stmt
*pStmt
;
3766 const char *azSql
[2] = {
3767 "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?",
3768 "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?"
3771 assert( bLeaf
==0 || bLeaf
==1 );
3772 if( pCheck
->aCheckMapping
[bLeaf
]==0 ){
3773 pCheck
->aCheckMapping
[bLeaf
] = rtreeCheckPrepare(pCheck
,
3774 azSql
[bLeaf
], pCheck
->zDb
, pCheck
->zTab
3777 if( pCheck
->rc
!=SQLITE_OK
) return;
3779 pStmt
= pCheck
->aCheckMapping
[bLeaf
];
3780 sqlite3_bind_int64(pStmt
, 1, iKey
);
3781 rc
= sqlite3_step(pStmt
);
3782 if( rc
==SQLITE_DONE
){
3783 rtreeCheckAppendMsg(pCheck
, "Mapping (%lld -> %lld) missing from %s table",
3784 iKey
, iVal
, (bLeaf
? "%_rowid" : "%_parent")
3786 }else if( rc
==SQLITE_ROW
){
3787 i64 ii
= sqlite3_column_int64(pStmt
, 0);
3789 rtreeCheckAppendMsg(pCheck
,
3790 "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
3791 iKey
, ii
, (bLeaf
? "%_rowid" : "%_parent"), iKey
, iVal
3795 rtreeCheckReset(pCheck
, pStmt
);
3799 ** Argument pCell points to an array of coordinates stored on an rtree page.
3800 ** This function checks that the coordinates are internally consistent (no
3801 ** x1>x2 conditions) and adds an error message to the RtreeCheck object
3804 ** Additionally, if pParent is not NULL, then it is assumed to point to
3805 ** the array of coordinates on the parent page that bound the page
3806 ** containing pCell. In this case it is also verified that the two
3807 ** sets of coordinates are mutually consistent and an error message added
3808 ** to the RtreeCheck object if they are not.
3810 static void rtreeCheckCellCoord(
3812 i64 iNode
, /* Node id to use in error messages */
3813 int iCell
, /* Cell number to use in error messages */
3814 u8
*pCell
, /* Pointer to cell coordinates */
3815 u8
*pParent
/* Pointer to parent coordinates */
3821 for(i
=0; i
<pCheck
->nDim
; i
++){
3822 readCoord(&pCell
[4*2*i
], &c1
);
3823 readCoord(&pCell
[4*(2*i
+ 1)], &c2
);
3825 /* printf("%e, %e\n", c1.u.f, c2.u.f); */
3826 if( pCheck
->bInt
? c1
.i
>c2
.i
: c1
.f
>c2
.f
){
3827 rtreeCheckAppendMsg(pCheck
,
3828 "Dimension %d of cell %d on node %lld is corrupt", i
, iCell
, iNode
3833 readCoord(&pParent
[4*2*i
], &p1
);
3834 readCoord(&pParent
[4*(2*i
+ 1)], &p2
);
3836 if( (pCheck
->bInt
? c1
.i
<p1
.i
: c1
.f
<p1
.f
)
3837 || (pCheck
->bInt
? c2
.i
>p2
.i
: c2
.f
>p2
.f
)
3839 rtreeCheckAppendMsg(pCheck
,
3840 "Dimension %d of cell %d on node %lld is corrupt relative to parent"
3849 ** Run rtreecheck() checks on node iNode, which is at depth iDepth within
3850 ** the r-tree structure. Argument aParent points to the array of coordinates
3851 ** that bound node iNode on the parent node.
3853 ** If any problems are discovered, an error message is appended to the
3854 ** report accumulated in the RtreeCheck object.
3856 static void rtreeCheckNode(
3858 int iDepth
, /* Depth of iNode (0==leaf) */
3859 u8
*aParent
, /* Buffer containing parent coords */
3860 i64 iNode
/* Node to check */
3865 assert( iNode
==1 || aParent
!=0 );
3866 assert( pCheck
->nDim
>0 );
3868 aNode
= rtreeCheckGetNode(pCheck
, iNode
, &nNode
);
3871 rtreeCheckAppendMsg(pCheck
,
3872 "Node %lld is too small (%d bytes)", iNode
, nNode
3875 int nCell
; /* Number of cells on page */
3876 int i
; /* Used to iterate through cells */
3878 iDepth
= readInt16(aNode
);
3879 if( iDepth
>RTREE_MAX_DEPTH
){
3880 rtreeCheckAppendMsg(pCheck
, "Rtree depth out of range (%d)", iDepth
);
3881 sqlite3_free(aNode
);
3885 nCell
= readInt16(&aNode
[2]);
3886 if( (4 + nCell
*(8 + pCheck
->nDim
*2*4))>nNode
){
3887 rtreeCheckAppendMsg(pCheck
,
3888 "Node %lld is too small for cell count of %d (%d bytes)",
3892 for(i
=0; i
<nCell
; i
++){
3893 u8
*pCell
= &aNode
[4 + i
*(8 + pCheck
->nDim
*2*4)];
3894 i64 iVal
= readInt64(pCell
);
3895 rtreeCheckCellCoord(pCheck
, iNode
, i
, &pCell
[8], aParent
);
3898 rtreeCheckMapping(pCheck
, 0, iVal
, iNode
);
3899 rtreeCheckNode(pCheck
, iDepth
-1, &pCell
[8], iVal
);
3902 rtreeCheckMapping(pCheck
, 1, iVal
, iNode
);
3908 sqlite3_free(aNode
);
3913 ** The second argument to this function must be either "_rowid" or
3914 ** "_parent". This function checks that the number of entries in the
3915 ** %_rowid or %_parent table is exactly nExpect. If not, it adds
3916 ** an error message to the report in the RtreeCheck object indicated
3917 ** by the first argument.
3919 static void rtreeCheckCount(RtreeCheck
*pCheck
, const char *zTbl
, i64 nExpect
){
3920 if( pCheck
->rc
==SQLITE_OK
){
3921 sqlite3_stmt
*pCount
;
3922 pCount
= rtreeCheckPrepare(pCheck
, "SELECT count(*) FROM %Q.'%q%s'",
3923 pCheck
->zDb
, pCheck
->zTab
, zTbl
3926 if( sqlite3_step(pCount
)==SQLITE_ROW
){
3927 i64 nActual
= sqlite3_column_int64(pCount
, 0);
3928 if( nActual
!=nExpect
){
3929 rtreeCheckAppendMsg(pCheck
, "Wrong number of entries in %%%s table"
3930 " - expected %lld, actual %lld" , zTbl
, nExpect
, nActual
3934 pCheck
->rc
= sqlite3_finalize(pCount
);
3940 ** This function does the bulk of the work for the rtree integrity-check.
3941 ** It is called by rtreecheck(), which is the SQL function implementation.
3943 static int rtreeCheckTable(
3944 sqlite3
*db
, /* Database handle to access db through */
3945 const char *zDb
, /* Name of db ("main", "temp" etc.) */
3946 const char *zTab
, /* Name of rtree table to check */
3947 char **pzReport
/* OUT: sqlite3_malloc'd report text */
3949 RtreeCheck check
; /* Common context for various routines */
3950 sqlite3_stmt
*pStmt
= 0; /* Used to find column count of rtree table */
3951 int bEnd
= 0; /* True if transaction should be closed */
3953 /* Initialize the context object */
3954 memset(&check
, 0, sizeof(check
));
3959 /* If there is not already an open transaction, open one now. This is
3960 ** to ensure that the queries run as part of this integrity-check operate
3961 ** on a consistent snapshot. */
3962 if( sqlite3_get_autocommit(db
) ){
3963 check
.rc
= sqlite3_exec(db
, "BEGIN", 0, 0, 0);
3967 /* Find number of dimensions in the rtree table. */
3968 pStmt
= rtreeCheckPrepare(&check
, "SELECT * FROM %Q.%Q", zDb
, zTab
);
3971 check
.nDim
= (sqlite3_column_count(pStmt
) - 1) / 2;
3973 rtreeCheckAppendMsg(&check
, "Schema corrupt or not an rtree");
3974 }else if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
3975 check
.bInt
= (sqlite3_column_type(pStmt
, 1)==SQLITE_INTEGER
);
3977 rc
= sqlite3_finalize(pStmt
);
3978 if( rc
!=SQLITE_CORRUPT
) check
.rc
= rc
;
3981 /* Do the actual integrity-check */
3982 if( check
.nDim
>=1 ){
3983 if( check
.rc
==SQLITE_OK
){
3984 rtreeCheckNode(&check
, 0, 0, 1);
3986 rtreeCheckCount(&check
, "_rowid", check
.nLeaf
);
3987 rtreeCheckCount(&check
, "_parent", check
.nNonLeaf
);
3990 /* Finalize SQL statements used by the integrity-check */
3991 sqlite3_finalize(check
.pGetNode
);
3992 sqlite3_finalize(check
.aCheckMapping
[0]);
3993 sqlite3_finalize(check
.aCheckMapping
[1]);
3995 /* If one was opened, close the transaction */
3997 int rc
= sqlite3_exec(db
, "END", 0, 0, 0);
3998 if( check
.rc
==SQLITE_OK
) check
.rc
= rc
;
4000 *pzReport
= check
.zReport
;
4007 ** rtreecheck(<rtree-table>);
4008 ** rtreecheck(<database>, <rtree-table>);
4010 ** Invoking this SQL function runs an integrity-check on the named rtree
4011 ** table. The integrity-check verifies the following:
4013 ** 1. For each cell in the r-tree structure (%_node table), that:
4015 ** a) for each dimension, (coord1 <= coord2).
4017 ** b) unless the cell is on the root node, that the cell is bounded
4018 ** by the parent cell on the parent node.
4020 ** c) for leaf nodes, that there is an entry in the %_rowid
4021 ** table corresponding to the cell's rowid value that
4022 ** points to the correct node.
4024 ** d) for cells on non-leaf nodes, that there is an entry in the
4025 ** %_parent table mapping from the cell's child node to the
4026 ** node that it resides on.
4028 ** 2. That there are the same number of entries in the %_rowid table
4029 ** as there are leaf cells in the r-tree structure, and that there
4030 ** is a leaf cell that corresponds to each entry in the %_rowid table.
4032 ** 3. That there are the same number of entries in the %_parent table
4033 ** as there are non-leaf cells in the r-tree structure, and that
4034 ** there is a non-leaf cell that corresponds to each entry in the
4037 static void rtreecheck(
4038 sqlite3_context
*ctx
,
4040 sqlite3_value
**apArg
4042 if( nArg
!=1 && nArg
!=2 ){
4043 sqlite3_result_error(ctx
,
4044 "wrong number of arguments to function rtreecheck()", -1
4049 const char *zDb
= (const char*)sqlite3_value_text(apArg
[0]);
4055 zTab
= (const char*)sqlite3_value_text(apArg
[1]);
4057 rc
= rtreeCheckTable(sqlite3_context_db_handle(ctx
), zDb
, zTab
, &zReport
);
4058 if( rc
==SQLITE_OK
){
4059 sqlite3_result_text(ctx
, zReport
? zReport
: "ok", -1, SQLITE_TRANSIENT
);
4061 sqlite3_result_error_code(ctx
, rc
);
4063 sqlite3_free(zReport
);
4069 ** Register the r-tree module with database handle db. This creates the
4070 ** virtual table module "rtree" and the debugging/analysis scalar
4071 ** function "rtreenode".
4073 int sqlite3RtreeInit(sqlite3
*db
){
4074 const int utf8
= SQLITE_UTF8
;
4077 rc
= sqlite3_create_function(db
, "rtreenode", 2, utf8
, 0, rtreenode
, 0, 0);
4078 if( rc
==SQLITE_OK
){
4079 rc
= sqlite3_create_function(db
, "rtreedepth", 1, utf8
, 0,rtreedepth
, 0, 0);
4081 if( rc
==SQLITE_OK
){
4082 rc
= sqlite3_create_function(db
, "rtreecheck", -1, utf8
, 0,rtreecheck
, 0,0);
4084 if( rc
==SQLITE_OK
){
4085 #ifdef SQLITE_RTREE_INT_ONLY
4086 void *c
= (void *)RTREE_COORD_INT32
;
4088 void *c
= (void *)RTREE_COORD_REAL32
;
4090 rc
= sqlite3_create_module_v2(db
, "rtree", &rtreeModule
, c
, 0);
4092 if( rc
==SQLITE_OK
){
4093 void *c
= (void *)RTREE_COORD_INT32
;
4094 rc
= sqlite3_create_module_v2(db
, "rtree_i32", &rtreeModule
, c
, 0);
4101 ** This routine deletes the RtreeGeomCallback object that was attached
4102 ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
4103 ** or sqlite3_rtree_query_callback(). In other words, this routine is the
4104 ** destructor for an RtreeGeomCallback objecct. This routine is called when
4105 ** the corresponding SQL function is deleted.
4107 static void rtreeFreeCallback(void *p
){
4108 RtreeGeomCallback
*pInfo
= (RtreeGeomCallback
*)p
;
4109 if( pInfo
->xDestructor
) pInfo
->xDestructor(pInfo
->pContext
);
4114 ** This routine frees the BLOB that is returned by geomCallback().
4116 static void rtreeMatchArgFree(void *pArg
){
4118 RtreeMatchArg
*p
= (RtreeMatchArg
*)pArg
;
4119 for(i
=0; i
<p
->nParam
; i
++){
4120 sqlite3_value_free(p
->apSqlParam
[i
]);
4126 ** Each call to sqlite3_rtree_geometry_callback() or
4127 ** sqlite3_rtree_query_callback() creates an ordinary SQLite
4128 ** scalar function that is implemented by this routine.
4130 ** All this function does is construct an RtreeMatchArg object that
4131 ** contains the geometry-checking callback routines and a list of
4132 ** parameters to this function, then return that RtreeMatchArg object
4135 ** The R-Tree MATCH operator will read the returned BLOB, deserialize
4136 ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
4137 ** out which elements of the R-Tree should be returned by the query.
4139 static void geomCallback(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**aArg
){
4140 RtreeGeomCallback
*pGeomCtx
= (RtreeGeomCallback
*)sqlite3_user_data(ctx
);
4141 RtreeMatchArg
*pBlob
;
4145 nBlob
= sizeof(RtreeMatchArg
) + (nArg
-1)*sizeof(RtreeDValue
)
4146 + nArg
*sizeof(sqlite3_value
*);
4147 pBlob
= (RtreeMatchArg
*)sqlite3_malloc(nBlob
);
4149 sqlite3_result_error_nomem(ctx
);
4152 pBlob
->iSize
= nBlob
;
4153 pBlob
->cb
= pGeomCtx
[0];
4154 pBlob
->apSqlParam
= (sqlite3_value
**)&pBlob
->aParam
[nArg
];
4155 pBlob
->nParam
= nArg
;
4156 for(i
=0; i
<nArg
; i
++){
4157 pBlob
->apSqlParam
[i
] = sqlite3_value_dup(aArg
[i
]);
4158 if( pBlob
->apSqlParam
[i
]==0 ) memErr
= 1;
4159 #ifdef SQLITE_RTREE_INT_ONLY
4160 pBlob
->aParam
[i
] = sqlite3_value_int64(aArg
[i
]);
4162 pBlob
->aParam
[i
] = sqlite3_value_double(aArg
[i
]);
4166 sqlite3_result_error_nomem(ctx
);
4167 rtreeMatchArgFree(pBlob
);
4169 sqlite3_result_pointer(ctx
, pBlob
, "RtreeMatchArg", rtreeMatchArgFree
);
4175 ** Register a new geometry function for use with the r-tree MATCH operator.
4177 int sqlite3_rtree_geometry_callback(
4178 sqlite3
*db
, /* Register SQL function on this connection */
4179 const char *zGeom
, /* Name of the new SQL function */
4180 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*), /* Callback */
4181 void *pContext
/* Extra data associated with the callback */
4183 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4185 /* Allocate and populate the context object. */
4186 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4187 if( !pGeomCtx
) return SQLITE_NOMEM
;
4188 pGeomCtx
->xGeom
= xGeom
;
4189 pGeomCtx
->xQueryFunc
= 0;
4190 pGeomCtx
->xDestructor
= 0;
4191 pGeomCtx
->pContext
= pContext
;
4192 return sqlite3_create_function_v2(db
, zGeom
, -1, SQLITE_ANY
,
4193 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4198 ** Register a new 2nd-generation geometry function for use with the
4199 ** r-tree MATCH operator.
4201 int sqlite3_rtree_query_callback(
4202 sqlite3
*db
, /* Register SQL function on this connection */
4203 const char *zQueryFunc
, /* Name of new SQL function */
4204 int (*xQueryFunc
)(sqlite3_rtree_query_info
*), /* Callback */
4205 void *pContext
, /* Extra data passed into the callback */
4206 void (*xDestructor
)(void*) /* Destructor for the extra data */
4208 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4210 /* Allocate and populate the context object. */
4211 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4212 if( !pGeomCtx
) return SQLITE_NOMEM
;
4213 pGeomCtx
->xGeom
= 0;
4214 pGeomCtx
->xQueryFunc
= xQueryFunc
;
4215 pGeomCtx
->xDestructor
= xDestructor
;
4216 pGeomCtx
->pContext
= pContext
;
4217 return sqlite3_create_function_v2(db
, zQueryFunc
, -1, SQLITE_ANY
,
4218 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4224 __declspec(dllexport
)
4226 int sqlite3_rtree_init(
4229 const sqlite3_api_routines
*pApi
4231 SQLITE_EXTENSION_INIT2(pApi
)
4232 return sqlite3RtreeInit(db
);