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
34 ** is stored on. If the r-tree contains auxiliary columns, those are stored
35 ** on the end of the %_rowid table.
37 ** The root node of an r-tree always exists, even if the r-tree table is
38 ** empty. The nodeno of the root node is always 1. All other nodes in the
39 ** table must be the same size as the root node. The content of each node
40 ** is formatted as follows:
42 ** 1. If the node is the root node (node 1), then the first 2 bytes
43 ** of the node contain the tree depth as a big-endian integer.
44 ** For non-root nodes, the first 2 bytes are left unused.
46 ** 2. The next 2 bytes contain the number of entries currently
47 ** stored in the node.
49 ** 3. The remainder of the node contains the node entries. Each entry
50 ** consists of a single 8-byte integer followed by an even number
51 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
52 ** of a record. For internal nodes it is the node number of a
56 #if !defined(SQLITE_CORE) \
57 || (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE))
60 #include "sqlite3ext.h"
61 SQLITE_EXTENSION_INIT1
70 #ifndef SQLITE_AMALGAMATION
71 #include "sqlite3rtree.h"
72 typedef sqlite3_int64 i64
;
73 typedef sqlite3_uint64 u64
;
74 typedef unsigned char u8
;
75 typedef unsigned short u16
;
76 typedef unsigned int u32
;
79 /* The following macro is used to suppress compiler warnings.
81 #ifndef UNUSED_PARAMETER
82 # define UNUSED_PARAMETER(x) (void)(x)
85 typedef struct Rtree Rtree
;
86 typedef struct RtreeCursor RtreeCursor
;
87 typedef struct RtreeNode RtreeNode
;
88 typedef struct RtreeCell RtreeCell
;
89 typedef struct RtreeConstraint RtreeConstraint
;
90 typedef struct RtreeMatchArg RtreeMatchArg
;
91 typedef struct RtreeGeomCallback RtreeGeomCallback
;
92 typedef union RtreeCoord RtreeCoord
;
93 typedef struct RtreeSearchPoint RtreeSearchPoint
;
95 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
96 #define RTREE_MAX_DIMENSIONS 5
98 /* Maximum number of auxiliary columns */
99 #define RTREE_MAX_AUX_COLUMN 100
101 /* Size of hash table Rtree.aHash. This hash table is not expected to
102 ** ever contain very many entries, so a fixed number of buckets is
107 /* The xBestIndex method of this virtual table requires an estimate of
108 ** the number of rows in the virtual table to calculate the costs of
109 ** various strategies. If possible, this estimate is loaded from the
110 ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
111 ** Otherwise, if no sqlite_stat1 entry is available, use
112 ** RTREE_DEFAULT_ROWEST.
114 #define RTREE_DEFAULT_ROWEST 1048576
115 #define RTREE_MIN_ROWEST 100
118 ** An rtree virtual-table object.
121 sqlite3_vtab base
; /* Base class. Must be first */
122 sqlite3
*db
; /* Host database connection */
123 int iNodeSize
; /* Size in bytes of each node in the node table */
124 u8 nDim
; /* Number of dimensions */
125 u8 nDim2
; /* Twice the number of dimensions */
126 u8 eCoordType
; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
127 u8 nBytesPerCell
; /* Bytes consumed per cell */
128 u8 inWrTrans
; /* True if inside write transaction */
129 u8 nAux
; /* # of auxiliary columns in %_rowid */
130 int iDepth
; /* Current depth of the r-tree structure */
131 char *zDb
; /* Name of database containing r-tree table */
132 char *zName
; /* Name of r-tree table */
133 u32 nBusy
; /* Current number of users of this structure */
134 i64 nRowEst
; /* Estimated number of rows in this table */
135 u32 nCursor
; /* Number of open cursors */
136 char *zReadAuxSql
; /* SQL for statement to read aux data */
138 /* List of nodes removed during a CondenseTree operation. List is
139 ** linked together via the pointer normally used for hash chains -
140 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
141 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
144 int iReinsertHeight
; /* Height of sub-trees Reinsert() has run on */
146 /* Blob I/O on xxx_node */
147 sqlite3_blob
*pNodeBlob
;
149 /* Statements to read/write/delete a record from xxx_node */
150 sqlite3_stmt
*pWriteNode
;
151 sqlite3_stmt
*pDeleteNode
;
153 /* Statements to read/write/delete a record from xxx_rowid */
154 sqlite3_stmt
*pReadRowid
;
155 sqlite3_stmt
*pWriteRowid
;
156 sqlite3_stmt
*pDeleteRowid
;
158 /* Statements to read/write/delete a record from xxx_parent */
159 sqlite3_stmt
*pReadParent
;
160 sqlite3_stmt
*pWriteParent
;
161 sqlite3_stmt
*pDeleteParent
;
163 /* Statement for writing to the "aux:" fields, if there are any */
164 sqlite3_stmt
*pWriteAux
;
166 RtreeNode
*aHash
[HASHSIZE
]; /* Hash table of in-memory nodes. */
169 /* Possible values for Rtree.eCoordType: */
170 #define RTREE_COORD_REAL32 0
171 #define RTREE_COORD_INT32 1
174 ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
175 ** only deal with integer coordinates. No floating point operations
178 #ifdef SQLITE_RTREE_INT_ONLY
179 typedef sqlite3_int64 RtreeDValue
; /* High accuracy coordinate */
180 typedef int RtreeValue
; /* Low accuracy coordinate */
181 # define RTREE_ZERO 0
183 typedef double RtreeDValue
; /* High accuracy coordinate */
184 typedef float RtreeValue
; /* Low accuracy coordinate */
185 # define RTREE_ZERO 0.0
189 ** When doing a search of an r-tree, instances of the following structure
190 ** record intermediate results from the tree walk.
192 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
193 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
194 ** the id is of the parent node and the cell that RtreeSearchPoint
195 ** represents is the iCell-th entry in the parent node.
197 struct RtreeSearchPoint
{
198 RtreeDValue rScore
; /* The score for this node. Smallest goes first. */
199 sqlite3_int64 id
; /* Node ID */
200 u8 iLevel
; /* 0=entries. 1=leaf node. 2+ for higher */
201 u8 eWithin
; /* PARTLY_WITHIN or FULLY_WITHIN */
202 u8 iCell
; /* Cell index within the node */
206 ** The minimum number of cells allowed for a node is a third of the
207 ** maximum. In Gutman's notation:
211 ** If an R*-tree "Reinsert" operation is required, the same number of
212 ** cells are removed from the overfull node and reinserted into the tree.
214 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
215 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
216 #define RTREE_MAXCELLS 51
219 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
220 ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
221 ** Therefore all non-root nodes must contain at least 3 entries. Since
222 ** 3^40 is greater than 2^64, an r-tree structure always has a depth of
225 #define RTREE_MAX_DEPTH 40
229 ** Number of entries in the cursor RtreeNode cache. The first entry is
230 ** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining
231 ** entries cache the RtreeNode for the first elements of the priority queue.
233 #define RTREE_CACHE_SZ 5
236 ** An rtree cursor object.
239 sqlite3_vtab_cursor base
; /* Base class. Must be first */
240 u8 atEOF
; /* True if at end of search */
241 u8 bPoint
; /* True if sPoint is valid */
242 u8 bAuxValid
; /* True if pReadAux is valid */
243 int iStrategy
; /* Copy of idxNum search parameter */
244 int nConstraint
; /* Number of entries in aConstraint */
245 RtreeConstraint
*aConstraint
; /* Search constraints. */
246 int nPointAlloc
; /* Number of slots allocated for aPoint[] */
247 int nPoint
; /* Number of slots used in aPoint[] */
248 int mxLevel
; /* iLevel value for root of the tree */
249 RtreeSearchPoint
*aPoint
; /* Priority queue for search points */
250 sqlite3_stmt
*pReadAux
; /* Statement to read aux-data */
251 RtreeSearchPoint sPoint
; /* Cached next search point */
252 RtreeNode
*aNode
[RTREE_CACHE_SZ
]; /* Rtree node cache */
253 u32 anQueue
[RTREE_MAX_DEPTH
+1]; /* Number of queued entries by iLevel */
256 /* Return the Rtree of a RtreeCursor */
257 #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab))
260 ** A coordinate can be either a floating point number or a integer. All
261 ** coordinates within a single R-Tree are always of the same time.
264 RtreeValue f
; /* Floating point value */
265 int i
; /* Integer value */
266 u32 u
; /* Unsigned for byte-order conversions */
270 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
271 ** formatted as a RtreeDValue (double or int64). This macro assumes that local
272 ** variable pRtree points to the Rtree structure associated with the
275 #ifdef SQLITE_RTREE_INT_ONLY
276 # define DCOORD(coord) ((RtreeDValue)coord.i)
278 # define DCOORD(coord) ( \
279 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
280 ((double)coord.f) : \
286 ** A search constraint.
288 struct RtreeConstraint
{
289 int iCoord
; /* Index of constrained coordinate */
290 int op
; /* Constraining operation */
292 RtreeDValue rValue
; /* Constraint value. */
293 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*);
294 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
296 sqlite3_rtree_query_info
*pInfo
; /* xGeom and xQueryFunc argument */
299 /* Possible values for RtreeConstraint.op */
300 #define RTREE_EQ 0x41 /* A */
301 #define RTREE_LE 0x42 /* B */
302 #define RTREE_LT 0x43 /* C */
303 #define RTREE_GE 0x44 /* D */
304 #define RTREE_GT 0x45 /* E */
305 #define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */
306 #define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */
310 ** An rtree structure node.
313 RtreeNode
*pParent
; /* Parent node */
314 i64 iNode
; /* The node number */
315 int nRef
; /* Number of references to this node */
316 int isDirty
; /* True if the node needs to be written to disk */
317 u8
*zData
; /* Content of the node, as should be on disk */
318 RtreeNode
*pNext
; /* Next node in this hash collision chain */
321 /* Return the number of cells in a node */
322 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
325 ** A single cell from a node, deserialized
328 i64 iRowid
; /* Node or entry ID */
329 RtreeCoord aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Bounding box coordinates */
334 ** This object becomes the sqlite3_user_data() for the SQL functions
335 ** that are created by sqlite3_rtree_geometry_callback() and
336 ** sqlite3_rtree_query_callback() and which appear on the right of MATCH
337 ** operators in order to constrain a search.
339 ** xGeom and xQueryFunc are the callback functions. Exactly one of
340 ** xGeom and xQueryFunc fields is non-NULL, depending on whether the
341 ** SQL function was created using sqlite3_rtree_geometry_callback() or
342 ** sqlite3_rtree_query_callback().
344 ** This object is deleted automatically by the destructor mechanism in
345 ** sqlite3_create_function_v2().
347 struct RtreeGeomCallback
{
348 int (*xGeom
)(sqlite3_rtree_geometry
*, int, RtreeDValue
*, int*);
349 int (*xQueryFunc
)(sqlite3_rtree_query_info
*);
350 void (*xDestructor
)(void*);
355 ** An instance of this structure (in the form of a BLOB) is returned by
356 ** the SQL functions that sqlite3_rtree_geometry_callback() and
357 ** sqlite3_rtree_query_callback() create, and is read as the right-hand
358 ** operand to the MATCH operator of an R-Tree.
360 struct RtreeMatchArg
{
361 u32 iSize
; /* Size of this object */
362 RtreeGeomCallback cb
; /* Info about the callback functions */
363 int nParam
; /* Number of parameters to the SQL function */
364 sqlite3_value
**apSqlParam
; /* Original SQL parameter values */
365 RtreeDValue aParam
[1]; /* Values for parameters to the SQL function */
369 # define MAX(x,y) ((x) < (y) ? (y) : (x))
372 # define MIN(x,y) ((x) > (y) ? (y) : (x))
375 /* What version of GCC is being used. 0 means GCC is not being used .
376 ** Note that the GCC_VERSION macro will also be set correctly when using
377 ** clang, since clang works hard to be gcc compatible. So the gcc
378 ** optimizations will also work when compiling with clang.
381 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
382 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
384 # define GCC_VERSION 0
388 /* The testcase() macro should already be defined in the amalgamation. If
389 ** it is not, make it a no-op.
391 #ifndef SQLITE_AMALGAMATION
396 ** Macros to determine whether the machine is big or little endian,
397 ** and whether or not that determination is run-time or compile-time.
399 ** For best performance, an attempt is made to guess at the byte-order
400 ** using C-preprocessor macros. If that is unsuccessful, or if
401 ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined
404 #ifndef SQLITE_BYTEORDER
405 #if defined(i386) || defined(__i386__) || defined(_M_IX86) || \
406 defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \
407 defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \
409 # define SQLITE_BYTEORDER 1234
410 #elif defined(sparc) || defined(__ppc__)
411 # define SQLITE_BYTEORDER 4321
413 # define SQLITE_BYTEORDER 0 /* 0 means "unknown at compile-time" */
418 /* What version of MSVC is being used. 0 means MSVC is not being used */
420 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
421 # define MSVC_VERSION _MSC_VER
423 # define MSVC_VERSION 0
428 ** Functions to deserialize a 16 bit integer, 32 bit real number and
429 ** 64 bit integer. The deserialized value is returned.
431 static int readInt16(u8
*p
){
432 return (p
[0]<<8) + p
[1];
434 static void readCoord(u8
*p
, RtreeCoord
*pCoord
){
435 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
436 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
437 pCoord
->u
= _byteswap_ulong(*(u32
*)p
);
438 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
439 pCoord
->u
= __builtin_bswap32(*(u32
*)p
);
440 #elif SQLITE_BYTEORDER==4321
441 pCoord
->u
= *(u32
*)p
;
444 (((u32
)p
[0]) << 24) +
445 (((u32
)p
[1]) << 16) +
451 static i64
readInt64(u8
*p
){
452 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
455 return (i64
)_byteswap_uint64(x
);
456 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
459 return (i64
)__builtin_bswap64(x
);
460 #elif SQLITE_BYTEORDER==4321
466 (((u64
)p
[0]) << 56) +
467 (((u64
)p
[1]) << 48) +
468 (((u64
)p
[2]) << 40) +
469 (((u64
)p
[3]) << 32) +
470 (((u64
)p
[4]) << 24) +
471 (((u64
)p
[5]) << 16) +
479 ** Functions to serialize a 16 bit integer, 32 bit real number and
480 ** 64 bit integer. The value returned is the number of bytes written
481 ** to the argument buffer (always 2, 4 and 8 respectively).
483 static void writeInt16(u8
*p
, int i
){
487 static int writeCoord(u8
*p
, RtreeCoord
*pCoord
){
489 assert( ((((char*)p
) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */
490 assert( sizeof(RtreeCoord
)==4 );
491 assert( sizeof(u32
)==4 );
492 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
493 i
= __builtin_bswap32(pCoord
->u
);
495 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
496 i
= _byteswap_ulong(pCoord
->u
);
498 #elif SQLITE_BYTEORDER==4321
510 static int writeInt64(u8
*p
, i64 i
){
511 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
512 i
= (i64
)__builtin_bswap64((u64
)i
);
514 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
515 i
= (i64
)_byteswap_uint64((u64
)i
);
517 #elif SQLITE_BYTEORDER==4321
533 ** Increment the reference count of node p.
535 static void nodeReference(RtreeNode
*p
){
542 ** Clear the content of node p (set all bytes to 0x00).
544 static void nodeZero(Rtree
*pRtree
, RtreeNode
*p
){
545 memset(&p
->zData
[2], 0, pRtree
->iNodeSize
-2);
550 ** Given a node number iNode, return the corresponding key to use
551 ** in the Rtree.aHash table.
553 static int nodeHash(i64 iNode
){
554 return iNode
% HASHSIZE
;
558 ** Search the node hash table for node iNode. If found, return a pointer
559 ** to it. Otherwise, return 0.
561 static RtreeNode
*nodeHashLookup(Rtree
*pRtree
, i64 iNode
){
563 for(p
=pRtree
->aHash
[nodeHash(iNode
)]; p
&& p
->iNode
!=iNode
; p
=p
->pNext
);
568 ** Add node pNode to the node hash table.
570 static void nodeHashInsert(Rtree
*pRtree
, RtreeNode
*pNode
){
572 assert( pNode
->pNext
==0 );
573 iHash
= nodeHash(pNode
->iNode
);
574 pNode
->pNext
= pRtree
->aHash
[iHash
];
575 pRtree
->aHash
[iHash
] = pNode
;
579 ** Remove node pNode from the node hash table.
581 static void nodeHashDelete(Rtree
*pRtree
, RtreeNode
*pNode
){
583 if( pNode
->iNode
!=0 ){
584 pp
= &pRtree
->aHash
[nodeHash(pNode
->iNode
)];
585 for( ; (*pp
)!=pNode
; pp
= &(*pp
)->pNext
){ assert(*pp
); }
592 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
593 ** indicating that node has not yet been assigned a node number. It is
594 ** assigned a node number when nodeWrite() is called to write the
595 ** node contents out to the database.
597 static RtreeNode
*nodeNew(Rtree
*pRtree
, RtreeNode
*pParent
){
599 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
) + pRtree
->iNodeSize
);
601 memset(pNode
, 0, sizeof(RtreeNode
) + pRtree
->iNodeSize
);
602 pNode
->zData
= (u8
*)&pNode
[1];
604 pNode
->pParent
= pParent
;
606 nodeReference(pParent
);
612 ** Clear the Rtree.pNodeBlob object
614 static void nodeBlobReset(Rtree
*pRtree
){
615 if( pRtree
->pNodeBlob
&& pRtree
->inWrTrans
==0 && pRtree
->nCursor
==0 ){
616 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
617 pRtree
->pNodeBlob
= 0;
618 sqlite3_blob_close(pBlob
);
623 ** Obtain a reference to an r-tree node.
625 static int nodeAcquire(
626 Rtree
*pRtree
, /* R-tree structure */
627 i64 iNode
, /* Node number to load */
628 RtreeNode
*pParent
, /* Either the parent node or NULL */
629 RtreeNode
**ppNode
/* OUT: Acquired node */
632 RtreeNode
*pNode
= 0;
634 /* Check if the requested node is already in the hash table. If so,
635 ** increase its reference count and return it.
637 if( (pNode
= nodeHashLookup(pRtree
, iNode
)) ){
638 assert( !pParent
|| !pNode
->pParent
|| pNode
->pParent
==pParent
);
639 if( pParent
&& !pNode
->pParent
){
640 nodeReference(pParent
);
641 pNode
->pParent
= pParent
;
648 if( pRtree
->pNodeBlob
){
649 sqlite3_blob
*pBlob
= pRtree
->pNodeBlob
;
650 pRtree
->pNodeBlob
= 0;
651 rc
= sqlite3_blob_reopen(pBlob
, iNode
);
652 pRtree
->pNodeBlob
= pBlob
;
654 nodeBlobReset(pRtree
);
655 if( rc
==SQLITE_NOMEM
) return SQLITE_NOMEM
;
658 if( pRtree
->pNodeBlob
==0 ){
659 char *zTab
= sqlite3_mprintf("%s_node", pRtree
->zName
);
660 if( zTab
==0 ) return SQLITE_NOMEM
;
661 rc
= sqlite3_blob_open(pRtree
->db
, pRtree
->zDb
, zTab
, "data", iNode
, 0,
666 nodeBlobReset(pRtree
);
668 /* If unable to open an sqlite3_blob on the desired row, that can only
669 ** be because the shadow tables hold erroneous data. */
670 if( rc
==SQLITE_ERROR
) rc
= SQLITE_CORRUPT_VTAB
;
671 }else if( pRtree
->iNodeSize
==sqlite3_blob_bytes(pRtree
->pNodeBlob
) ){
672 pNode
= (RtreeNode
*)sqlite3_malloc(sizeof(RtreeNode
)+pRtree
->iNodeSize
);
676 pNode
->pParent
= pParent
;
677 pNode
->zData
= (u8
*)&pNode
[1];
679 pNode
->iNode
= iNode
;
682 rc
= sqlite3_blob_read(pRtree
->pNodeBlob
, pNode
->zData
,
683 pRtree
->iNodeSize
, 0);
684 nodeReference(pParent
);
688 /* If the root node was just loaded, set pRtree->iDepth to the height
689 ** of the r-tree structure. A height of zero means all data is stored on
690 ** the root node. A height of one means the children of the root node
691 ** are the leaves, and so on. If the depth as specified on the root node
692 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
694 if( pNode
&& iNode
==1 ){
695 pRtree
->iDepth
= readInt16(pNode
->zData
);
696 if( pRtree
->iDepth
>RTREE_MAX_DEPTH
){
697 rc
= SQLITE_CORRUPT_VTAB
;
701 /* If no error has occurred so far, check if the "number of entries"
702 ** field on the node is too large. If so, set the return code to
703 ** SQLITE_CORRUPT_VTAB.
705 if( pNode
&& rc
==SQLITE_OK
){
706 if( NCELL(pNode
)>((pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
) ){
707 rc
= SQLITE_CORRUPT_VTAB
;
713 nodeHashInsert(pRtree
, pNode
);
715 rc
= SQLITE_CORRUPT_VTAB
;
727 ** Overwrite cell iCell of node pNode with the contents of pCell.
729 static void nodeOverwriteCell(
730 Rtree
*pRtree
, /* The overall R-Tree */
731 RtreeNode
*pNode
, /* The node into which the cell is to be written */
732 RtreeCell
*pCell
, /* The cell to write */
733 int iCell
/* Index into pNode into which pCell is written */
736 u8
*p
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
737 p
+= writeInt64(p
, pCell
->iRowid
);
738 for(ii
=0; ii
<pRtree
->nDim2
; ii
++){
739 p
+= writeCoord(p
, &pCell
->aCoord
[ii
]);
745 ** Remove the cell with index iCell from node pNode.
747 static void nodeDeleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
){
748 u8
*pDst
= &pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
];
749 u8
*pSrc
= &pDst
[pRtree
->nBytesPerCell
];
750 int nByte
= (NCELL(pNode
) - iCell
- 1) * pRtree
->nBytesPerCell
;
751 memmove(pDst
, pSrc
, nByte
);
752 writeInt16(&pNode
->zData
[2], NCELL(pNode
)-1);
757 ** Insert the contents of cell pCell into node pNode. If the insert
758 ** is successful, return SQLITE_OK.
760 ** If there is not enough free space in pNode, return SQLITE_FULL.
762 static int nodeInsertCell(
763 Rtree
*pRtree
, /* The overall R-Tree */
764 RtreeNode
*pNode
, /* Write new cell into this node */
765 RtreeCell
*pCell
/* The cell to be inserted */
767 int nCell
; /* Current number of cells in pNode */
768 int nMaxCell
; /* Maximum number of cells for pNode */
770 nMaxCell
= (pRtree
->iNodeSize
-4)/pRtree
->nBytesPerCell
;
771 nCell
= NCELL(pNode
);
773 assert( nCell
<=nMaxCell
);
774 if( nCell
<nMaxCell
){
775 nodeOverwriteCell(pRtree
, pNode
, pCell
, nCell
);
776 writeInt16(&pNode
->zData
[2], nCell
+1);
780 return (nCell
==nMaxCell
);
784 ** If the node is dirty, write it out to the database.
786 static int nodeWrite(Rtree
*pRtree
, RtreeNode
*pNode
){
788 if( pNode
->isDirty
){
789 sqlite3_stmt
*p
= pRtree
->pWriteNode
;
791 sqlite3_bind_int64(p
, 1, pNode
->iNode
);
793 sqlite3_bind_null(p
, 1);
795 sqlite3_bind_blob(p
, 2, pNode
->zData
, pRtree
->iNodeSize
, SQLITE_STATIC
);
798 rc
= sqlite3_reset(p
);
799 sqlite3_bind_null(p
, 2);
800 if( pNode
->iNode
==0 && rc
==SQLITE_OK
){
801 pNode
->iNode
= sqlite3_last_insert_rowid(pRtree
->db
);
802 nodeHashInsert(pRtree
, pNode
);
809 ** Release a reference to a node. If the node is dirty and the reference
810 ** count drops to zero, the node data is written to the database.
812 static int nodeRelease(Rtree
*pRtree
, RtreeNode
*pNode
){
815 assert( pNode
->nRef
>0 );
817 if( pNode
->nRef
==0 ){
818 if( pNode
->iNode
==1 ){
821 if( pNode
->pParent
){
822 rc
= nodeRelease(pRtree
, pNode
->pParent
);
825 rc
= nodeWrite(pRtree
, pNode
);
827 nodeHashDelete(pRtree
, pNode
);
835 ** Return the 64-bit integer value associated with cell iCell of
836 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
837 ** an internal node, then the 64-bit integer is a child page number.
839 static i64
nodeGetRowid(
840 Rtree
*pRtree
, /* The overall R-Tree */
841 RtreeNode
*pNode
, /* The node from which to extract the ID */
842 int iCell
/* The cell index from which to extract the ID */
844 assert( iCell
<NCELL(pNode
) );
845 return readInt64(&pNode
->zData
[4 + pRtree
->nBytesPerCell
*iCell
]);
849 ** Return coordinate iCoord from cell iCell in node pNode.
851 static void nodeGetCoord(
852 Rtree
*pRtree
, /* The overall R-Tree */
853 RtreeNode
*pNode
, /* The node from which to extract a coordinate */
854 int iCell
, /* The index of the cell within the node */
855 int iCoord
, /* Which coordinate to extract */
856 RtreeCoord
*pCoord
/* OUT: Space to write result to */
858 readCoord(&pNode
->zData
[12 + pRtree
->nBytesPerCell
*iCell
+ 4*iCoord
], pCoord
);
862 ** Deserialize cell iCell of node pNode. Populate the structure pointed
863 ** to by pCell with the results.
865 static void nodeGetCell(
866 Rtree
*pRtree
, /* The overall R-Tree */
867 RtreeNode
*pNode
, /* The node containing the cell to be read */
868 int iCell
, /* Index of the cell within the node */
869 RtreeCell
*pCell
/* OUT: Write the cell contents here */
874 pCell
->iRowid
= nodeGetRowid(pRtree
, pNode
, iCell
);
875 pData
= pNode
->zData
+ (12 + pRtree
->nBytesPerCell
*iCell
);
876 pCoord
= pCell
->aCoord
;
878 readCoord(pData
, &pCoord
[ii
]);
879 readCoord(pData
+4, &pCoord
[ii
+1]);
882 }while( ii
<pRtree
->nDim2
);
886 /* Forward declaration for the function that does the work of
887 ** the virtual table module xCreate() and xConnect() methods.
889 static int rtreeInit(
890 sqlite3
*, void *, int, const char *const*, sqlite3_vtab
**, char **, int
894 ** Rtree virtual table module xCreate method.
896 static int rtreeCreate(
899 int argc
, const char *const*argv
,
900 sqlite3_vtab
**ppVtab
,
903 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 1);
907 ** Rtree virtual table module xConnect method.
909 static int rtreeConnect(
912 int argc
, const char *const*argv
,
913 sqlite3_vtab
**ppVtab
,
916 return rtreeInit(db
, pAux
, argc
, argv
, ppVtab
, pzErr
, 0);
920 ** Increment the r-tree reference count.
922 static void rtreeReference(Rtree
*pRtree
){
927 ** Decrement the r-tree reference count. When the reference count reaches
928 ** zero the structure is deleted.
930 static void rtreeRelease(Rtree
*pRtree
){
932 if( pRtree
->nBusy
==0 ){
933 pRtree
->inWrTrans
= 0;
935 nodeBlobReset(pRtree
);
936 sqlite3_finalize(pRtree
->pWriteNode
);
937 sqlite3_finalize(pRtree
->pDeleteNode
);
938 sqlite3_finalize(pRtree
->pReadRowid
);
939 sqlite3_finalize(pRtree
->pWriteRowid
);
940 sqlite3_finalize(pRtree
->pDeleteRowid
);
941 sqlite3_finalize(pRtree
->pReadParent
);
942 sqlite3_finalize(pRtree
->pWriteParent
);
943 sqlite3_finalize(pRtree
->pDeleteParent
);
944 sqlite3_finalize(pRtree
->pWriteAux
);
945 sqlite3_free(pRtree
->zReadAuxSql
);
946 sqlite3_free(pRtree
);
951 ** Rtree virtual table module xDisconnect method.
953 static int rtreeDisconnect(sqlite3_vtab
*pVtab
){
954 rtreeRelease((Rtree
*)pVtab
);
959 ** Rtree virtual table module xDestroy method.
961 static int rtreeDestroy(sqlite3_vtab
*pVtab
){
962 Rtree
*pRtree
= (Rtree
*)pVtab
;
964 char *zCreate
= sqlite3_mprintf(
965 "DROP TABLE '%q'.'%q_node';"
966 "DROP TABLE '%q'.'%q_rowid';"
967 "DROP TABLE '%q'.'%q_parent';",
968 pRtree
->zDb
, pRtree
->zName
,
969 pRtree
->zDb
, pRtree
->zName
,
970 pRtree
->zDb
, pRtree
->zName
975 nodeBlobReset(pRtree
);
976 rc
= sqlite3_exec(pRtree
->db
, zCreate
, 0, 0, 0);
977 sqlite3_free(zCreate
);
980 rtreeRelease(pRtree
);
987 ** Rtree virtual table module xOpen method.
989 static int rtreeOpen(sqlite3_vtab
*pVTab
, sqlite3_vtab_cursor
**ppCursor
){
990 int rc
= SQLITE_NOMEM
;
991 Rtree
*pRtree
= (Rtree
*)pVTab
;
994 pCsr
= (RtreeCursor
*)sqlite3_malloc(sizeof(RtreeCursor
));
996 memset(pCsr
, 0, sizeof(RtreeCursor
));
997 pCsr
->base
.pVtab
= pVTab
;
1001 *ppCursor
= (sqlite3_vtab_cursor
*)pCsr
;
1008 ** Free the RtreeCursor.aConstraint[] array and its contents.
1010 static void freeCursorConstraints(RtreeCursor
*pCsr
){
1011 if( pCsr
->aConstraint
){
1012 int i
; /* Used to iterate through constraint array */
1013 for(i
=0; i
<pCsr
->nConstraint
; i
++){
1014 sqlite3_rtree_query_info
*pInfo
= pCsr
->aConstraint
[i
].pInfo
;
1016 if( pInfo
->xDelUser
) pInfo
->xDelUser(pInfo
->pUser
);
1017 sqlite3_free(pInfo
);
1020 sqlite3_free(pCsr
->aConstraint
);
1021 pCsr
->aConstraint
= 0;
1026 ** Rtree virtual table module xClose method.
1028 static int rtreeClose(sqlite3_vtab_cursor
*cur
){
1029 Rtree
*pRtree
= (Rtree
*)(cur
->pVtab
);
1031 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1032 assert( pRtree
->nCursor
>0 );
1033 freeCursorConstraints(pCsr
);
1034 sqlite3_finalize(pCsr
->pReadAux
);
1035 sqlite3_free(pCsr
->aPoint
);
1036 for(ii
=0; ii
<RTREE_CACHE_SZ
; ii
++) nodeRelease(pRtree
, pCsr
->aNode
[ii
]);
1039 nodeBlobReset(pRtree
);
1044 ** Rtree virtual table module xEof method.
1046 ** Return non-zero if the cursor does not currently point to a valid
1047 ** record (i.e if the scan has finished), or zero otherwise.
1049 static int rtreeEof(sqlite3_vtab_cursor
*cur
){
1050 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1055 ** Convert raw bits from the on-disk RTree record into a coordinate value.
1056 ** The on-disk format is big-endian and needs to be converted for little-
1057 ** endian platforms. The on-disk record stores integer coordinates if
1058 ** eInt is true and it stores 32-bit floating point records if eInt is
1059 ** false. a[] is the four bytes of the on-disk record to be decoded.
1060 ** Store the results in "r".
1062 ** There are five versions of this macro. The last one is generic. The
1063 ** other four are various architectures-specific optimizations.
1065 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1066 #define RTREE_DECODE_COORD(eInt, a, r) { \
1067 RtreeCoord c; /* Coordinate decoded */ \
1068 c.u = _byteswap_ulong(*(u32*)a); \
1069 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1071 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1072 #define RTREE_DECODE_COORD(eInt, a, r) { \
1073 RtreeCoord c; /* Coordinate decoded */ \
1074 c.u = __builtin_bswap32(*(u32*)a); \
1075 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1077 #elif SQLITE_BYTEORDER==1234
1078 #define RTREE_DECODE_COORD(eInt, a, r) { \
1079 RtreeCoord c; /* Coordinate decoded */ \
1081 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
1082 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
1083 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1085 #elif SQLITE_BYTEORDER==4321
1086 #define RTREE_DECODE_COORD(eInt, a, r) { \
1087 RtreeCoord c; /* Coordinate decoded */ \
1089 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1092 #define RTREE_DECODE_COORD(eInt, a, r) { \
1093 RtreeCoord c; /* Coordinate decoded */ \
1094 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
1095 +((u32)a[2]<<8) + a[3]; \
1096 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1101 ** Check the RTree node or entry given by pCellData and p against the MATCH
1102 ** constraint pConstraint.
1104 static int rtreeCallbackConstraint(
1105 RtreeConstraint
*pConstraint
, /* The constraint to test */
1106 int eInt
, /* True if RTree holding integer coordinates */
1107 u8
*pCellData
, /* Raw cell content */
1108 RtreeSearchPoint
*pSearch
, /* Container of this cell */
1109 sqlite3_rtree_dbl
*prScore
, /* OUT: score for the cell */
1110 int *peWithin
/* OUT: visibility of the cell */
1112 sqlite3_rtree_query_info
*pInfo
= pConstraint
->pInfo
; /* Callback info */
1113 int nCoord
= pInfo
->nCoord
; /* No. of coordinates */
1114 int rc
; /* Callback return code */
1115 RtreeCoord c
; /* Translator union */
1116 sqlite3_rtree_dbl aCoord
[RTREE_MAX_DIMENSIONS
*2]; /* Decoded coordinates */
1118 assert( pConstraint
->op
==RTREE_MATCH
|| pConstraint
->op
==RTREE_QUERY
);
1119 assert( nCoord
==2 || nCoord
==4 || nCoord
==6 || nCoord
==8 || nCoord
==10 );
1121 if( pConstraint
->op
==RTREE_QUERY
&& pSearch
->iLevel
==1 ){
1122 pInfo
->iRowid
= readInt64(pCellData
);
1125 #ifndef SQLITE_RTREE_INT_ONLY
1128 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.f
;
1129 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.f
;
1130 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.f
;
1131 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.f
;
1132 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.f
;
1133 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.f
;
1134 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.f
;
1135 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.f
;
1136 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.f
;
1137 readCoord(pCellData
, &c
); aCoord
[0] = c
.f
;
1143 case 10: readCoord(pCellData
+36, &c
); aCoord
[9] = c
.i
;
1144 readCoord(pCellData
+32, &c
); aCoord
[8] = c
.i
;
1145 case 8: readCoord(pCellData
+28, &c
); aCoord
[7] = c
.i
;
1146 readCoord(pCellData
+24, &c
); aCoord
[6] = c
.i
;
1147 case 6: readCoord(pCellData
+20, &c
); aCoord
[5] = c
.i
;
1148 readCoord(pCellData
+16, &c
); aCoord
[4] = c
.i
;
1149 case 4: readCoord(pCellData
+12, &c
); aCoord
[3] = c
.i
;
1150 readCoord(pCellData
+8, &c
); aCoord
[2] = c
.i
;
1151 default: readCoord(pCellData
+4, &c
); aCoord
[1] = c
.i
;
1152 readCoord(pCellData
, &c
); aCoord
[0] = c
.i
;
1155 if( pConstraint
->op
==RTREE_MATCH
){
1157 rc
= pConstraint
->u
.xGeom((sqlite3_rtree_geometry
*)pInfo
,
1158 nCoord
, aCoord
, &eWithin
);
1159 if( eWithin
==0 ) *peWithin
= NOT_WITHIN
;
1160 *prScore
= RTREE_ZERO
;
1162 pInfo
->aCoord
= aCoord
;
1163 pInfo
->iLevel
= pSearch
->iLevel
- 1;
1164 pInfo
->rScore
= pInfo
->rParentScore
= pSearch
->rScore
;
1165 pInfo
->eWithin
= pInfo
->eParentWithin
= pSearch
->eWithin
;
1166 rc
= pConstraint
->u
.xQueryFunc(pInfo
);
1167 if( pInfo
->eWithin
<*peWithin
) *peWithin
= pInfo
->eWithin
;
1168 if( pInfo
->rScore
<*prScore
|| *prScore
<RTREE_ZERO
){
1169 *prScore
= pInfo
->rScore
;
1176 ** Check the internal RTree node given by pCellData against constraint p.
1177 ** If this constraint cannot be satisfied by any child within the node,
1178 ** set *peWithin to NOT_WITHIN.
1180 static void rtreeNonleafConstraint(
1181 RtreeConstraint
*p
, /* The constraint to test */
1182 int eInt
, /* True if RTree holds integer coordinates */
1183 u8
*pCellData
, /* Raw cell content as appears on disk */
1184 int *peWithin
/* Adjust downward, as appropriate */
1186 sqlite3_rtree_dbl val
; /* Coordinate value convert to a double */
1188 /* p->iCoord might point to either a lower or upper bound coordinate
1189 ** in a coordinate pair. But make pCellData point to the lower bound.
1191 pCellData
+= 8 + 4*(p
->iCoord
&0xfe);
1193 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1194 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1195 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1200 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1201 /* val now holds the lower bound of the coordinate pair */
1202 if( p
->u
.rValue
>=val
) return;
1203 if( p
->op
!=RTREE_EQ
) break; /* RTREE_LE and RTREE_LT end here */
1204 /* Fall through for the RTREE_EQ case */
1206 default: /* RTREE_GT or RTREE_GE, or fallthrough of RTREE_EQ */
1208 RTREE_DECODE_COORD(eInt
, pCellData
, val
);
1209 /* val now holds the upper bound of the coordinate pair */
1210 if( p
->u
.rValue
<=val
) return;
1212 *peWithin
= NOT_WITHIN
;
1216 ** Check the leaf RTree cell given by pCellData against constraint p.
1217 ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
1218 ** If the constraint is satisfied, leave *peWithin unchanged.
1220 ** The constraint is of the form: xN op $val
1222 ** The op is given by p->op. The xN is p->iCoord-th coordinate in
1223 ** pCellData. $val is given by p->u.rValue.
1225 static void rtreeLeafConstraint(
1226 RtreeConstraint
*p
, /* The constraint to test */
1227 int eInt
, /* True if RTree holds integer coordinates */
1228 u8
*pCellData
, /* Raw cell content as appears on disk */
1229 int *peWithin
/* Adjust downward, as appropriate */
1231 RtreeDValue xN
; /* Coordinate value converted to a double */
1233 assert(p
->op
==RTREE_LE
|| p
->op
==RTREE_LT
|| p
->op
==RTREE_GE
1234 || p
->op
==RTREE_GT
|| p
->op
==RTREE_EQ
);
1235 pCellData
+= 8 + p
->iCoord
*4;
1236 assert( ((((char*)pCellData
) - (char*)0)&3)==0 ); /* 4-byte aligned */
1237 RTREE_DECODE_COORD(eInt
, pCellData
, xN
);
1239 case RTREE_LE
: if( xN
<= p
->u
.rValue
) return; break;
1240 case RTREE_LT
: if( xN
< p
->u
.rValue
) return; break;
1241 case RTREE_GE
: if( xN
>= p
->u
.rValue
) return; break;
1242 case RTREE_GT
: if( xN
> p
->u
.rValue
) return; break;
1243 default: if( xN
== p
->u
.rValue
) return; break;
1245 *peWithin
= NOT_WITHIN
;
1249 ** One of the cells in node pNode is guaranteed to have a 64-bit
1250 ** integer value equal to iRowid. Return the index of this cell.
1252 static int nodeRowidIndex(
1259 int nCell
= NCELL(pNode
);
1260 assert( nCell
<200 );
1261 for(ii
=0; ii
<nCell
; ii
++){
1262 if( nodeGetRowid(pRtree
, pNode
, ii
)==iRowid
){
1267 return SQLITE_CORRUPT_VTAB
;
1271 ** Return the index of the cell containing a pointer to node pNode
1272 ** in its parent. If pNode is the root node, return -1.
1274 static int nodeParentIndex(Rtree
*pRtree
, RtreeNode
*pNode
, int *piIndex
){
1275 RtreeNode
*pParent
= pNode
->pParent
;
1277 return nodeRowidIndex(pRtree
, pParent
, pNode
->iNode
, piIndex
);
1284 ** Compare two search points. Return negative, zero, or positive if the first
1285 ** is less than, equal to, or greater than the second.
1287 ** The rScore is the primary key. Smaller rScore values come first.
1288 ** If the rScore is a tie, then use iLevel as the tie breaker with smaller
1289 ** iLevel values coming first. In this way, if rScore is the same for all
1290 ** SearchPoints, then iLevel becomes the deciding factor and the result
1291 ** is a depth-first search, which is the desired default behavior.
1293 static int rtreeSearchPointCompare(
1294 const RtreeSearchPoint
*pA
,
1295 const RtreeSearchPoint
*pB
1297 if( pA
->rScore
<pB
->rScore
) return -1;
1298 if( pA
->rScore
>pB
->rScore
) return +1;
1299 if( pA
->iLevel
<pB
->iLevel
) return -1;
1300 if( pA
->iLevel
>pB
->iLevel
) return +1;
1305 ** Interchange two search points in a cursor.
1307 static void rtreeSearchPointSwap(RtreeCursor
*p
, int i
, int j
){
1308 RtreeSearchPoint t
= p
->aPoint
[i
];
1310 p
->aPoint
[i
] = p
->aPoint
[j
];
1313 if( i
<RTREE_CACHE_SZ
){
1314 if( j
>=RTREE_CACHE_SZ
){
1315 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1318 RtreeNode
*pTemp
= p
->aNode
[i
];
1319 p
->aNode
[i
] = p
->aNode
[j
];
1320 p
->aNode
[j
] = pTemp
;
1326 ** Return the search point with the lowest current score.
1328 static RtreeSearchPoint
*rtreeSearchPointFirst(RtreeCursor
*pCur
){
1329 return pCur
->bPoint
? &pCur
->sPoint
: pCur
->nPoint
? pCur
->aPoint
: 0;
1333 ** Get the RtreeNode for the search point with the lowest score.
1335 static RtreeNode
*rtreeNodeOfFirstSearchPoint(RtreeCursor
*pCur
, int *pRC
){
1337 int ii
= 1 - pCur
->bPoint
;
1338 assert( ii
==0 || ii
==1 );
1339 assert( pCur
->bPoint
|| pCur
->nPoint
);
1340 if( pCur
->aNode
[ii
]==0 ){
1342 id
= ii
? pCur
->aPoint
[0].id
: pCur
->sPoint
.id
;
1343 *pRC
= nodeAcquire(RTREE_OF_CURSOR(pCur
), id
, 0, &pCur
->aNode
[ii
]);
1345 return pCur
->aNode
[ii
];
1349 ** Push a new element onto the priority queue
1351 static RtreeSearchPoint
*rtreeEnqueue(
1352 RtreeCursor
*pCur
, /* The cursor */
1353 RtreeDValue rScore
, /* Score for the new search point */
1354 u8 iLevel
/* Level for the new search point */
1357 RtreeSearchPoint
*pNew
;
1358 if( pCur
->nPoint
>=pCur
->nPointAlloc
){
1359 int nNew
= pCur
->nPointAlloc
*2 + 8;
1360 pNew
= sqlite3_realloc(pCur
->aPoint
, nNew
*sizeof(pCur
->aPoint
[0]));
1361 if( pNew
==0 ) return 0;
1362 pCur
->aPoint
= pNew
;
1363 pCur
->nPointAlloc
= nNew
;
1366 pNew
= pCur
->aPoint
+ i
;
1367 pNew
->rScore
= rScore
;
1368 pNew
->iLevel
= iLevel
;
1369 assert( iLevel
<=RTREE_MAX_DEPTH
);
1371 RtreeSearchPoint
*pParent
;
1373 pParent
= pCur
->aPoint
+ j
;
1374 if( rtreeSearchPointCompare(pNew
, pParent
)>=0 ) break;
1375 rtreeSearchPointSwap(pCur
, j
, i
);
1383 ** Allocate a new RtreeSearchPoint and return a pointer to it. Return
1384 ** NULL if malloc fails.
1386 static RtreeSearchPoint
*rtreeSearchPointNew(
1387 RtreeCursor
*pCur
, /* The cursor */
1388 RtreeDValue rScore
, /* Score for the new search point */
1389 u8 iLevel
/* Level for the new search point */
1391 RtreeSearchPoint
*pNew
, *pFirst
;
1392 pFirst
= rtreeSearchPointFirst(pCur
);
1393 pCur
->anQueue
[iLevel
]++;
1395 || pFirst
->rScore
>rScore
1396 || (pFirst
->rScore
==rScore
&& pFirst
->iLevel
>iLevel
)
1400 pNew
= rtreeEnqueue(pCur
, rScore
, iLevel
);
1401 if( pNew
==0 ) return 0;
1402 ii
= (int)(pNew
- pCur
->aPoint
) + 1;
1403 if( ii
<RTREE_CACHE_SZ
){
1404 assert( pCur
->aNode
[ii
]==0 );
1405 pCur
->aNode
[ii
] = pCur
->aNode
[0];
1407 nodeRelease(RTREE_OF_CURSOR(pCur
), pCur
->aNode
[0]);
1410 *pNew
= pCur
->sPoint
;
1412 pCur
->sPoint
.rScore
= rScore
;
1413 pCur
->sPoint
.iLevel
= iLevel
;
1415 return &pCur
->sPoint
;
1417 return rtreeEnqueue(pCur
, rScore
, iLevel
);
1422 /* Tracing routines for the RtreeSearchPoint queue */
1423 static void tracePoint(RtreeSearchPoint
*p
, int idx
, RtreeCursor
*pCur
){
1424 if( idx
<0 ){ printf(" s"); }else{ printf("%2d", idx
); }
1425 printf(" %d.%05lld.%02d %g %d",
1426 p
->iLevel
, p
->id
, p
->iCell
, p
->rScore
, p
->eWithin
1429 if( idx
<RTREE_CACHE_SZ
){
1430 printf(" %p\n", pCur
->aNode
[idx
]);
1435 static void traceQueue(RtreeCursor
*pCur
, const char *zPrefix
){
1437 printf("=== %9s ", zPrefix
);
1439 tracePoint(&pCur
->sPoint
, -1, pCur
);
1441 for(ii
=0; ii
<pCur
->nPoint
; ii
++){
1442 if( ii
>0 || pCur
->bPoint
) printf(" ");
1443 tracePoint(&pCur
->aPoint
[ii
], ii
, pCur
);
1446 # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
1448 # define RTREE_QUEUE_TRACE(A,B) /* no-op */
1451 /* Remove the search point with the lowest current score.
1453 static void rtreeSearchPointPop(RtreeCursor
*p
){
1456 assert( i
==0 || i
==1 );
1458 nodeRelease(RTREE_OF_CURSOR(p
), p
->aNode
[i
]);
1462 p
->anQueue
[p
->sPoint
.iLevel
]--;
1464 }else if( p
->nPoint
){
1465 p
->anQueue
[p
->aPoint
[0].iLevel
]--;
1467 p
->aPoint
[0] = p
->aPoint
[n
];
1468 if( n
<RTREE_CACHE_SZ
-1 ){
1469 p
->aNode
[1] = p
->aNode
[n
+1];
1473 while( (j
= i
*2+1)<n
){
1475 if( k
<n
&& rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[j
])<0 ){
1476 if( rtreeSearchPointCompare(&p
->aPoint
[k
], &p
->aPoint
[i
])<0 ){
1477 rtreeSearchPointSwap(p
, i
, k
);
1483 if( rtreeSearchPointCompare(&p
->aPoint
[j
], &p
->aPoint
[i
])<0 ){
1484 rtreeSearchPointSwap(p
, i
, j
);
1496 ** Continue the search on cursor pCur until the front of the queue
1497 ** contains an entry suitable for returning as a result-set row,
1498 ** or until the RtreeSearchPoint queue is empty, indicating that the
1499 ** query has completed.
1501 static int rtreeStepToLeaf(RtreeCursor
*pCur
){
1502 RtreeSearchPoint
*p
;
1503 Rtree
*pRtree
= RTREE_OF_CURSOR(pCur
);
1508 int nConstraint
= pCur
->nConstraint
;
1513 eInt
= pRtree
->eCoordType
==RTREE_COORD_INT32
;
1514 while( (p
= rtreeSearchPointFirst(pCur
))!=0 && p
->iLevel
>0 ){
1515 pNode
= rtreeNodeOfFirstSearchPoint(pCur
, &rc
);
1517 nCell
= NCELL(pNode
);
1518 assert( nCell
<200 );
1519 while( p
->iCell
<nCell
){
1520 sqlite3_rtree_dbl rScore
= (sqlite3_rtree_dbl
)-1;
1521 u8
*pCellData
= pNode
->zData
+ (4+pRtree
->nBytesPerCell
*p
->iCell
);
1522 eWithin
= FULLY_WITHIN
;
1523 for(ii
=0; ii
<nConstraint
; ii
++){
1524 RtreeConstraint
*pConstraint
= pCur
->aConstraint
+ ii
;
1525 if( pConstraint
->op
>=RTREE_MATCH
){
1526 rc
= rtreeCallbackConstraint(pConstraint
, eInt
, pCellData
, p
,
1529 }else if( p
->iLevel
==1 ){
1530 rtreeLeafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1532 rtreeNonleafConstraint(pConstraint
, eInt
, pCellData
, &eWithin
);
1534 if( eWithin
==NOT_WITHIN
) break;
1537 if( eWithin
==NOT_WITHIN
) continue;
1538 x
.iLevel
= p
->iLevel
- 1;
1540 x
.id
= readInt64(pCellData
);
1544 x
.iCell
= p
->iCell
- 1;
1546 if( p
->iCell
>=nCell
){
1547 RTREE_QUEUE_TRACE(pCur
, "POP-S:");
1548 rtreeSearchPointPop(pCur
);
1550 if( rScore
<RTREE_ZERO
) rScore
= RTREE_ZERO
;
1551 p
= rtreeSearchPointNew(pCur
, rScore
, x
.iLevel
);
1552 if( p
==0 ) return SQLITE_NOMEM
;
1553 p
->eWithin
= (u8
)eWithin
;
1556 RTREE_QUEUE_TRACE(pCur
, "PUSH-S:");
1559 if( p
->iCell
>=nCell
){
1560 RTREE_QUEUE_TRACE(pCur
, "POP-Se:");
1561 rtreeSearchPointPop(pCur
);
1569 ** Rtree virtual table module xNext method.
1571 static int rtreeNext(sqlite3_vtab_cursor
*pVtabCursor
){
1572 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1575 /* Move to the next entry that matches the configured constraints. */
1576 RTREE_QUEUE_TRACE(pCsr
, "POP-Nx:");
1577 if( pCsr
->bAuxValid
){
1578 pCsr
->bAuxValid
= 0;
1579 sqlite3_reset(pCsr
->pReadAux
);
1581 rtreeSearchPointPop(pCsr
);
1582 rc
= rtreeStepToLeaf(pCsr
);
1587 ** Rtree virtual table module xRowid method.
1589 static int rtreeRowid(sqlite3_vtab_cursor
*pVtabCursor
, sqlite_int64
*pRowid
){
1590 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1591 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1593 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1594 if( rc
==SQLITE_OK
&& p
){
1595 *pRowid
= nodeGetRowid(RTREE_OF_CURSOR(pCsr
), pNode
, p
->iCell
);
1601 ** Rtree virtual table module xColumn method.
1603 static int rtreeColumn(sqlite3_vtab_cursor
*cur
, sqlite3_context
*ctx
, int i
){
1604 Rtree
*pRtree
= (Rtree
*)cur
->pVtab
;
1605 RtreeCursor
*pCsr
= (RtreeCursor
*)cur
;
1606 RtreeSearchPoint
*p
= rtreeSearchPointFirst(pCsr
);
1609 RtreeNode
*pNode
= rtreeNodeOfFirstSearchPoint(pCsr
, &rc
);
1612 if( p
==0 ) return SQLITE_OK
;
1614 sqlite3_result_int64(ctx
, nodeGetRowid(pRtree
, pNode
, p
->iCell
));
1615 }else if( i
<=pRtree
->nDim2
){
1616 nodeGetCoord(pRtree
, pNode
, p
->iCell
, i
-1, &c
);
1617 #ifndef SQLITE_RTREE_INT_ONLY
1618 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1619 sqlite3_result_double(ctx
, c
.f
);
1623 assert( pRtree
->eCoordType
==RTREE_COORD_INT32
);
1624 sqlite3_result_int(ctx
, c
.i
);
1627 if( !pCsr
->bAuxValid
){
1628 if( pCsr
->pReadAux
==0 ){
1629 rc
= sqlite3_prepare_v3(pRtree
->db
, pRtree
->zReadAuxSql
, -1, 0,
1630 &pCsr
->pReadAux
, 0);
1633 sqlite3_bind_int64(pCsr
->pReadAux
, 1,
1634 nodeGetRowid(pRtree
, pNode
, p
->iCell
));
1635 rc
= sqlite3_step(pCsr
->pReadAux
);
1636 if( rc
==SQLITE_ROW
){
1637 pCsr
->bAuxValid
= 1;
1639 sqlite3_reset(pCsr
->pReadAux
);
1640 if( rc
==SQLITE_DONE
) rc
= SQLITE_OK
;
1644 sqlite3_result_value(ctx
,
1645 sqlite3_column_value(pCsr
->pReadAux
, i
- pRtree
->nDim2
+ 1));
1651 ** Use nodeAcquire() to obtain the leaf node containing the record with
1652 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
1653 ** return SQLITE_OK. If there is no such record in the table, set
1654 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1655 ** to zero and return an SQLite error code.
1657 static int findLeafNode(
1658 Rtree
*pRtree
, /* RTree to search */
1659 i64 iRowid
, /* The rowid searching for */
1660 RtreeNode
**ppLeaf
, /* Write the node here */
1661 sqlite3_int64
*piNode
/* Write the node-id here */
1665 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, iRowid
);
1666 if( sqlite3_step(pRtree
->pReadRowid
)==SQLITE_ROW
){
1667 i64 iNode
= sqlite3_column_int64(pRtree
->pReadRowid
, 0);
1668 if( piNode
) *piNode
= iNode
;
1669 rc
= nodeAcquire(pRtree
, iNode
, 0, ppLeaf
);
1670 sqlite3_reset(pRtree
->pReadRowid
);
1672 rc
= sqlite3_reset(pRtree
->pReadRowid
);
1678 ** This function is called to configure the RtreeConstraint object passed
1679 ** as the second argument for a MATCH constraint. The value passed as the
1680 ** first argument to this function is the right-hand operand to the MATCH
1683 static int deserializeGeometry(sqlite3_value
*pValue
, RtreeConstraint
*pCons
){
1684 RtreeMatchArg
*pBlob
, *pSrc
; /* BLOB returned by geometry function */
1685 sqlite3_rtree_query_info
*pInfo
; /* Callback information */
1687 pSrc
= sqlite3_value_pointer(pValue
, "RtreeMatchArg");
1688 if( pSrc
==0 ) return SQLITE_ERROR
;
1689 pInfo
= (sqlite3_rtree_query_info
*)
1690 sqlite3_malloc64( sizeof(*pInfo
)+pSrc
->iSize
);
1691 if( !pInfo
) return SQLITE_NOMEM
;
1692 memset(pInfo
, 0, sizeof(*pInfo
));
1693 pBlob
= (RtreeMatchArg
*)&pInfo
[1];
1694 memcpy(pBlob
, pSrc
, pSrc
->iSize
);
1695 pInfo
->pContext
= pBlob
->cb
.pContext
;
1696 pInfo
->nParam
= pBlob
->nParam
;
1697 pInfo
->aParam
= pBlob
->aParam
;
1698 pInfo
->apSqlParam
= pBlob
->apSqlParam
;
1700 if( pBlob
->cb
.xGeom
){
1701 pCons
->u
.xGeom
= pBlob
->cb
.xGeom
;
1703 pCons
->op
= RTREE_QUERY
;
1704 pCons
->u
.xQueryFunc
= pBlob
->cb
.xQueryFunc
;
1706 pCons
->pInfo
= pInfo
;
1711 ** Rtree virtual table module xFilter method.
1713 static int rtreeFilter(
1714 sqlite3_vtab_cursor
*pVtabCursor
,
1715 int idxNum
, const char *idxStr
,
1716 int argc
, sqlite3_value
**argv
1718 Rtree
*pRtree
= (Rtree
*)pVtabCursor
->pVtab
;
1719 RtreeCursor
*pCsr
= (RtreeCursor
*)pVtabCursor
;
1720 RtreeNode
*pRoot
= 0;
1725 rtreeReference(pRtree
);
1727 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
1728 freeCursorConstraints(pCsr
);
1729 sqlite3_free(pCsr
->aPoint
);
1730 memset(pCsr
, 0, sizeof(RtreeCursor
));
1731 pCsr
->base
.pVtab
= (sqlite3_vtab
*)pRtree
;
1733 pCsr
->iStrategy
= idxNum
;
1735 /* Special case - lookup by rowid. */
1736 RtreeNode
*pLeaf
; /* Leaf on which the required cell resides */
1737 RtreeSearchPoint
*p
; /* Search point for the leaf */
1738 i64 iRowid
= sqlite3_value_int64(argv
[0]);
1740 rc
= findLeafNode(pRtree
, iRowid
, &pLeaf
, &iNode
);
1741 if( rc
==SQLITE_OK
&& pLeaf
!=0 ){
1742 p
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, 0);
1743 assert( p
!=0 ); /* Always returns pCsr->sPoint */
1744 pCsr
->aNode
[0] = pLeaf
;
1746 p
->eWithin
= PARTLY_WITHIN
;
1747 rc
= nodeRowidIndex(pRtree
, pLeaf
, iRowid
, &iCell
);
1748 p
->iCell
= (u8
)iCell
;
1749 RTREE_QUEUE_TRACE(pCsr
, "PUSH-F1:");
1754 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1755 ** with the configured constraints.
1757 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
1758 if( rc
==SQLITE_OK
&& argc
>0 ){
1759 pCsr
->aConstraint
= sqlite3_malloc(sizeof(RtreeConstraint
)*argc
);
1760 pCsr
->nConstraint
= argc
;
1761 if( !pCsr
->aConstraint
){
1764 memset(pCsr
->aConstraint
, 0, sizeof(RtreeConstraint
)*argc
);
1765 memset(pCsr
->anQueue
, 0, sizeof(u32
)*(pRtree
->iDepth
+ 1));
1766 assert( (idxStr
==0 && argc
==0)
1767 || (idxStr
&& (int)strlen(idxStr
)==argc
*2) );
1768 for(ii
=0; ii
<argc
; ii
++){
1769 RtreeConstraint
*p
= &pCsr
->aConstraint
[ii
];
1770 p
->op
= idxStr
[ii
*2];
1771 p
->iCoord
= idxStr
[ii
*2+1]-'0';
1772 if( p
->op
>=RTREE_MATCH
){
1773 /* A MATCH operator. The right-hand-side must be a blob that
1774 ** can be cast into an RtreeMatchArg object. One created using
1775 ** an sqlite3_rtree_geometry_callback() SQL user function.
1777 rc
= deserializeGeometry(argv
[ii
], p
);
1778 if( rc
!=SQLITE_OK
){
1781 p
->pInfo
->nCoord
= pRtree
->nDim2
;
1782 p
->pInfo
->anQueue
= pCsr
->anQueue
;
1783 p
->pInfo
->mxLevel
= pRtree
->iDepth
+ 1;
1785 #ifdef SQLITE_RTREE_INT_ONLY
1786 p
->u
.rValue
= sqlite3_value_int64(argv
[ii
]);
1788 p
->u
.rValue
= sqlite3_value_double(argv
[ii
]);
1794 if( rc
==SQLITE_OK
){
1795 RtreeSearchPoint
*pNew
;
1796 pNew
= rtreeSearchPointNew(pCsr
, RTREE_ZERO
, (u8
)(pRtree
->iDepth
+1));
1797 if( pNew
==0 ) return SQLITE_NOMEM
;
1800 pNew
->eWithin
= PARTLY_WITHIN
;
1801 assert( pCsr
->bPoint
==1 );
1802 pCsr
->aNode
[0] = pRoot
;
1804 RTREE_QUEUE_TRACE(pCsr
, "PUSH-Fm:");
1805 rc
= rtreeStepToLeaf(pCsr
);
1809 nodeRelease(pRtree
, pRoot
);
1810 rtreeRelease(pRtree
);
1815 ** Rtree virtual table module xBestIndex method. There are three
1816 ** table scan strategies to choose from (in order from most to
1817 ** least desirable):
1819 ** idxNum idxStr Strategy
1820 ** ------------------------------------------------
1821 ** 1 Unused Direct lookup by rowid.
1822 ** 2 See below R-tree query or full-table scan.
1823 ** ------------------------------------------------
1825 ** If strategy 1 is used, then idxStr is not meaningful. If strategy
1826 ** 2 is used, idxStr is formatted to contain 2 bytes for each
1827 ** constraint used. The first two bytes of idxStr correspond to
1828 ** the constraint in sqlite3_index_info.aConstraintUsage[] with
1829 ** (argvIndex==1) etc.
1831 ** The first of each pair of bytes in idxStr identifies the constraint
1832 ** operator as follows:
1834 ** Operator Byte Value
1835 ** ----------------------
1842 ** ----------------------
1844 ** The second of each pair of bytes identifies the coordinate column
1845 ** to which the constraint applies. The leftmost coordinate column
1846 ** is 'a', the second from the left 'b' etc.
1848 static int rtreeBestIndex(sqlite3_vtab
*tab
, sqlite3_index_info
*pIdxInfo
){
1849 Rtree
*pRtree
= (Rtree
*)tab
;
1852 int bMatch
= 0; /* True if there exists a MATCH constraint */
1853 i64 nRow
; /* Estimated rows returned by this scan */
1856 char zIdxStr
[RTREE_MAX_DIMENSIONS
*8+1];
1857 memset(zIdxStr
, 0, sizeof(zIdxStr
));
1859 /* Check if there exists a MATCH constraint - even an unusable one. If there
1860 ** is, do not consider the lookup-by-rowid plan as using such a plan would
1861 ** require the VDBE to evaluate the MATCH constraint, which is not currently
1863 for(ii
=0; ii
<pIdxInfo
->nConstraint
; ii
++){
1864 if( pIdxInfo
->aConstraint
[ii
].op
==SQLITE_INDEX_CONSTRAINT_MATCH
){
1869 assert( pIdxInfo
->idxStr
==0 );
1870 for(ii
=0; ii
<pIdxInfo
->nConstraint
&& iIdx
<(int)(sizeof(zIdxStr
)-1); ii
++){
1871 struct sqlite3_index_constraint
*p
= &pIdxInfo
->aConstraint
[ii
];
1873 if( bMatch
==0 && p
->usable
1874 && p
->iColumn
==0 && p
->op
==SQLITE_INDEX_CONSTRAINT_EQ
1876 /* We have an equality constraint on the rowid. Use strategy 1. */
1878 for(jj
=0; jj
<ii
; jj
++){
1879 pIdxInfo
->aConstraintUsage
[jj
].argvIndex
= 0;
1880 pIdxInfo
->aConstraintUsage
[jj
].omit
= 0;
1882 pIdxInfo
->idxNum
= 1;
1883 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= 1;
1884 pIdxInfo
->aConstraintUsage
[jj
].omit
= 1;
1886 /* This strategy involves a two rowid lookups on an B-Tree structures
1887 ** and then a linear search of an R-Tree node. This should be
1888 ** considered almost as quick as a direct rowid lookup (for which
1889 ** sqlite uses an internal cost of 0.0). It is expected to return
1892 pIdxInfo
->estimatedCost
= 30.0;
1893 pIdxInfo
->estimatedRows
= 1;
1898 && ((p
->iColumn
>0 && p
->iColumn
<=pRtree
->nDim2
)
1899 || p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
)
1903 case SQLITE_INDEX_CONSTRAINT_EQ
: op
= RTREE_EQ
; break;
1904 case SQLITE_INDEX_CONSTRAINT_GT
: op
= RTREE_GT
; break;
1905 case SQLITE_INDEX_CONSTRAINT_LE
: op
= RTREE_LE
; break;
1906 case SQLITE_INDEX_CONSTRAINT_LT
: op
= RTREE_LT
; break;
1907 case SQLITE_INDEX_CONSTRAINT_GE
: op
= RTREE_GE
; break;
1909 assert( p
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
);
1913 zIdxStr
[iIdx
++] = op
;
1914 zIdxStr
[iIdx
++] = (char)(p
->iColumn
- 1 + '0');
1915 pIdxInfo
->aConstraintUsage
[ii
].argvIndex
= (iIdx
/2);
1916 pIdxInfo
->aConstraintUsage
[ii
].omit
= 1;
1920 pIdxInfo
->idxNum
= 2;
1921 pIdxInfo
->needToFreeIdxStr
= 1;
1922 if( iIdx
>0 && 0==(pIdxInfo
->idxStr
= sqlite3_mprintf("%s", zIdxStr
)) ){
1923 return SQLITE_NOMEM
;
1926 nRow
= pRtree
->nRowEst
>> (iIdx
/2);
1927 pIdxInfo
->estimatedCost
= (double)6.0 * (double)nRow
;
1928 pIdxInfo
->estimatedRows
= nRow
;
1934 ** Return the N-dimensional volumn of the cell stored in *p.
1936 static RtreeDValue
cellArea(Rtree
*pRtree
, RtreeCell
*p
){
1937 RtreeDValue area
= (RtreeDValue
)1;
1938 assert( pRtree
->nDim
>=1 && pRtree
->nDim
<=5 );
1939 #ifndef SQLITE_RTREE_INT_ONLY
1940 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1941 switch( pRtree
->nDim
){
1942 case 5: area
= p
->aCoord
[9].f
- p
->aCoord
[8].f
;
1943 case 4: area
*= p
->aCoord
[7].f
- p
->aCoord
[6].f
;
1944 case 3: area
*= p
->aCoord
[5].f
- p
->aCoord
[4].f
;
1945 case 2: area
*= p
->aCoord
[3].f
- p
->aCoord
[2].f
;
1946 default: area
*= p
->aCoord
[1].f
- p
->aCoord
[0].f
;
1951 switch( pRtree
->nDim
){
1952 case 5: area
= p
->aCoord
[9].i
- p
->aCoord
[8].i
;
1953 case 4: area
*= p
->aCoord
[7].i
- p
->aCoord
[6].i
;
1954 case 3: area
*= p
->aCoord
[5].i
- p
->aCoord
[4].i
;
1955 case 2: area
*= p
->aCoord
[3].i
- p
->aCoord
[2].i
;
1956 default: area
*= p
->aCoord
[1].i
- p
->aCoord
[0].i
;
1963 ** Return the margin length of cell p. The margin length is the sum
1964 ** of the objects size in each dimension.
1966 static RtreeDValue
cellMargin(Rtree
*pRtree
, RtreeCell
*p
){
1967 RtreeDValue margin
= 0;
1968 int ii
= pRtree
->nDim2
- 2;
1970 margin
+= (DCOORD(p
->aCoord
[ii
+1]) - DCOORD(p
->aCoord
[ii
]));
1977 ** Store the union of cells p1 and p2 in p1.
1979 static void cellUnion(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
1981 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
1983 p1
->aCoord
[ii
].f
= MIN(p1
->aCoord
[ii
].f
, p2
->aCoord
[ii
].f
);
1984 p1
->aCoord
[ii
+1].f
= MAX(p1
->aCoord
[ii
+1].f
, p2
->aCoord
[ii
+1].f
);
1986 }while( ii
<pRtree
->nDim2
);
1989 p1
->aCoord
[ii
].i
= MIN(p1
->aCoord
[ii
].i
, p2
->aCoord
[ii
].i
);
1990 p1
->aCoord
[ii
+1].i
= MAX(p1
->aCoord
[ii
+1].i
, p2
->aCoord
[ii
+1].i
);
1992 }while( ii
<pRtree
->nDim2
);
1997 ** Return true if the area covered by p2 is a subset of the area covered
1998 ** by p1. False otherwise.
2000 static int cellContains(Rtree
*pRtree
, RtreeCell
*p1
, RtreeCell
*p2
){
2002 int isInt
= (pRtree
->eCoordType
==RTREE_COORD_INT32
);
2003 for(ii
=0; ii
<pRtree
->nDim2
; ii
+=2){
2004 RtreeCoord
*a1
= &p1
->aCoord
[ii
];
2005 RtreeCoord
*a2
= &p2
->aCoord
[ii
];
2006 if( (!isInt
&& (a2
[0].f
<a1
[0].f
|| a2
[1].f
>a1
[1].f
))
2007 || ( isInt
&& (a2
[0].i
<a1
[0].i
|| a2
[1].i
>a1
[1].i
))
2016 ** Return the amount cell p would grow by if it were unioned with pCell.
2018 static RtreeDValue
cellGrowth(Rtree
*pRtree
, RtreeCell
*p
, RtreeCell
*pCell
){
2021 memcpy(&cell
, p
, sizeof(RtreeCell
));
2022 area
= cellArea(pRtree
, &cell
);
2023 cellUnion(pRtree
, &cell
, pCell
);
2024 return (cellArea(pRtree
, &cell
)-area
);
2027 static RtreeDValue
cellOverlap(
2034 RtreeDValue overlap
= RTREE_ZERO
;
2035 for(ii
=0; ii
<nCell
; ii
++){
2037 RtreeDValue o
= (RtreeDValue
)1;
2038 for(jj
=0; jj
<pRtree
->nDim2
; jj
+=2){
2040 x1
= MAX(DCOORD(p
->aCoord
[jj
]), DCOORD(aCell
[ii
].aCoord
[jj
]));
2041 x2
= MIN(DCOORD(p
->aCoord
[jj
+1]), DCOORD(aCell
[ii
].aCoord
[jj
+1]));
2056 ** This function implements the ChooseLeaf algorithm from Gutman[84].
2057 ** ChooseSubTree in r*tree terminology.
2059 static int ChooseLeaf(
2060 Rtree
*pRtree
, /* Rtree table */
2061 RtreeCell
*pCell
, /* Cell to insert into rtree */
2062 int iHeight
, /* Height of sub-tree rooted at pCell */
2063 RtreeNode
**ppLeaf
/* OUT: Selected leaf page */
2067 RtreeNode
*pNode
= 0;
2068 rc
= nodeAcquire(pRtree
, 1, 0, &pNode
);
2070 for(ii
=0; rc
==SQLITE_OK
&& ii
<(pRtree
->iDepth
-iHeight
); ii
++){
2072 sqlite3_int64 iBest
= 0;
2074 RtreeDValue fMinGrowth
= RTREE_ZERO
;
2075 RtreeDValue fMinArea
= RTREE_ZERO
;
2077 int nCell
= NCELL(pNode
);
2081 RtreeCell
*aCell
= 0;
2083 /* Select the child node which will be enlarged the least if pCell
2084 ** is inserted into it. Resolve ties by choosing the entry with
2085 ** the smallest area.
2087 for(iCell
=0; iCell
<nCell
; iCell
++){
2091 nodeGetCell(pRtree
, pNode
, iCell
, &cell
);
2092 growth
= cellGrowth(pRtree
, &cell
, pCell
);
2093 area
= cellArea(pRtree
, &cell
);
2094 if( iCell
==0||growth
<fMinGrowth
||(growth
==fMinGrowth
&& area
<fMinArea
) ){
2098 fMinGrowth
= growth
;
2100 iBest
= cell
.iRowid
;
2104 sqlite3_free(aCell
);
2105 rc
= nodeAcquire(pRtree
, iBest
, pNode
, &pChild
);
2106 nodeRelease(pRtree
, pNode
);
2115 ** A cell with the same content as pCell has just been inserted into
2116 ** the node pNode. This function updates the bounding box cells in
2117 ** all ancestor elements.
2119 static int AdjustTree(
2120 Rtree
*pRtree
, /* Rtree table */
2121 RtreeNode
*pNode
, /* Adjust ancestry of this node. */
2122 RtreeCell
*pCell
/* This cell was just inserted */
2124 RtreeNode
*p
= pNode
;
2125 while( p
->pParent
){
2126 RtreeNode
*pParent
= p
->pParent
;
2130 if( nodeParentIndex(pRtree
, p
, &iCell
) ){
2131 return SQLITE_CORRUPT_VTAB
;
2134 nodeGetCell(pRtree
, pParent
, iCell
, &cell
);
2135 if( !cellContains(pRtree
, &cell
, pCell
) ){
2136 cellUnion(pRtree
, &cell
, pCell
);
2137 nodeOverwriteCell(pRtree
, pParent
, &cell
, iCell
);
2146 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
2148 static int rowidWrite(Rtree
*pRtree
, sqlite3_int64 iRowid
, sqlite3_int64 iNode
){
2149 sqlite3_bind_int64(pRtree
->pWriteRowid
, 1, iRowid
);
2150 sqlite3_bind_int64(pRtree
->pWriteRowid
, 2, iNode
);
2151 sqlite3_step(pRtree
->pWriteRowid
);
2152 return sqlite3_reset(pRtree
->pWriteRowid
);
2156 ** Write mapping (iNode->iPar) to the <rtree>_parent table.
2158 static int parentWrite(Rtree
*pRtree
, sqlite3_int64 iNode
, sqlite3_int64 iPar
){
2159 sqlite3_bind_int64(pRtree
->pWriteParent
, 1, iNode
);
2160 sqlite3_bind_int64(pRtree
->pWriteParent
, 2, iPar
);
2161 sqlite3_step(pRtree
->pWriteParent
);
2162 return sqlite3_reset(pRtree
->pWriteParent
);
2165 static int rtreeInsertCell(Rtree
*, RtreeNode
*, RtreeCell
*, int);
2169 ** Arguments aIdx, aDistance and aSpare all point to arrays of size
2170 ** nIdx. The aIdx array contains the set of integers from 0 to
2171 ** (nIdx-1) in no particular order. This function sorts the values
2172 ** in aIdx according to the indexed values in aDistance. For
2173 ** example, assuming the inputs:
2175 ** aIdx = { 0, 1, 2, 3 }
2176 ** aDistance = { 5.0, 2.0, 7.0, 6.0 }
2178 ** this function sets the aIdx array to contain:
2180 ** aIdx = { 0, 1, 2, 3 }
2182 ** The aSpare array is used as temporary working space by the
2183 ** sorting algorithm.
2185 static void SortByDistance(
2188 RtreeDValue
*aDistance
,
2196 int nRight
= nIdx
-nLeft
;
2198 int *aRight
= &aIdx
[nLeft
];
2200 SortByDistance(aLeft
, nLeft
, aDistance
, aSpare
);
2201 SortByDistance(aRight
, nRight
, aDistance
, aSpare
);
2203 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2206 while( iLeft
<nLeft
|| iRight
<nRight
){
2208 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2210 }else if( iRight
==nRight
){
2211 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2214 RtreeDValue fLeft
= aDistance
[aLeft
[iLeft
]];
2215 RtreeDValue fRight
= aDistance
[aRight
[iRight
]];
2217 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2220 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2227 /* Check that the sort worked */
2230 for(jj
=1; jj
<nIdx
; jj
++){
2231 RtreeDValue left
= aDistance
[aIdx
[jj
-1]];
2232 RtreeDValue right
= aDistance
[aIdx
[jj
]];
2233 assert( left
<=right
);
2241 ** Arguments aIdx, aCell and aSpare all point to arrays of size
2242 ** nIdx. The aIdx array contains the set of integers from 0 to
2243 ** (nIdx-1) in no particular order. This function sorts the values
2244 ** in aIdx according to dimension iDim of the cells in aCell. The
2245 ** minimum value of dimension iDim is considered first, the
2246 ** maximum used to break ties.
2248 ** The aSpare array is used as temporary working space by the
2249 ** sorting algorithm.
2251 static void SortByDimension(
2265 int nRight
= nIdx
-nLeft
;
2267 int *aRight
= &aIdx
[nLeft
];
2269 SortByDimension(pRtree
, aLeft
, nLeft
, iDim
, aCell
, aSpare
);
2270 SortByDimension(pRtree
, aRight
, nRight
, iDim
, aCell
, aSpare
);
2272 memcpy(aSpare
, aLeft
, sizeof(int)*nLeft
);
2274 while( iLeft
<nLeft
|| iRight
<nRight
){
2275 RtreeDValue xleft1
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2]);
2276 RtreeDValue xleft2
= DCOORD(aCell
[aLeft
[iLeft
]].aCoord
[iDim
*2+1]);
2277 RtreeDValue xright1
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2]);
2278 RtreeDValue xright2
= DCOORD(aCell
[aRight
[iRight
]].aCoord
[iDim
*2+1]);
2279 if( (iLeft
!=nLeft
) && ((iRight
==nRight
)
2281 || (xleft1
==xright1
&& xleft2
<xright2
)
2283 aIdx
[iLeft
+iRight
] = aLeft
[iLeft
];
2286 aIdx
[iLeft
+iRight
] = aRight
[iRight
];
2292 /* Check that the sort worked */
2295 for(jj
=1; jj
<nIdx
; jj
++){
2296 RtreeDValue xleft1
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2];
2297 RtreeDValue xleft2
= aCell
[aIdx
[jj
-1]].aCoord
[iDim
*2+1];
2298 RtreeDValue xright1
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2];
2299 RtreeDValue xright2
= aCell
[aIdx
[jj
]].aCoord
[iDim
*2+1];
2300 assert( xleft1
<=xright1
&& (xleft1
<xright1
|| xleft2
<=xright2
) );
2308 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
2310 static int splitNodeStartree(
2316 RtreeCell
*pBboxLeft
,
2317 RtreeCell
*pBboxRight
2325 RtreeDValue fBestMargin
= RTREE_ZERO
;
2327 int nByte
= (pRtree
->nDim
+1)*(sizeof(int*)+nCell
*sizeof(int));
2329 aaSorted
= (int **)sqlite3_malloc(nByte
);
2331 return SQLITE_NOMEM
;
2334 aSpare
= &((int *)&aaSorted
[pRtree
->nDim
])[pRtree
->nDim
*nCell
];
2335 memset(aaSorted
, 0, nByte
);
2336 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2338 aaSorted
[ii
] = &((int *)&aaSorted
[pRtree
->nDim
])[ii
*nCell
];
2339 for(jj
=0; jj
<nCell
; jj
++){
2340 aaSorted
[ii
][jj
] = jj
;
2342 SortByDimension(pRtree
, aaSorted
[ii
], nCell
, ii
, aCell
, aSpare
);
2345 for(ii
=0; ii
<pRtree
->nDim
; ii
++){
2346 RtreeDValue margin
= RTREE_ZERO
;
2347 RtreeDValue fBestOverlap
= RTREE_ZERO
;
2348 RtreeDValue fBestArea
= RTREE_ZERO
;
2353 nLeft
=RTREE_MINCELLS(pRtree
);
2354 nLeft
<=(nCell
-RTREE_MINCELLS(pRtree
));
2360 RtreeDValue overlap
;
2363 memcpy(&left
, &aCell
[aaSorted
[ii
][0]], sizeof(RtreeCell
));
2364 memcpy(&right
, &aCell
[aaSorted
[ii
][nCell
-1]], sizeof(RtreeCell
));
2365 for(kk
=1; kk
<(nCell
-1); kk
++){
2367 cellUnion(pRtree
, &left
, &aCell
[aaSorted
[ii
][kk
]]);
2369 cellUnion(pRtree
, &right
, &aCell
[aaSorted
[ii
][kk
]]);
2372 margin
+= cellMargin(pRtree
, &left
);
2373 margin
+= cellMargin(pRtree
, &right
);
2374 overlap
= cellOverlap(pRtree
, &left
, &right
, 1);
2375 area
= cellArea(pRtree
, &left
) + cellArea(pRtree
, &right
);
2376 if( (nLeft
==RTREE_MINCELLS(pRtree
))
2377 || (overlap
<fBestOverlap
)
2378 || (overlap
==fBestOverlap
&& area
<fBestArea
)
2381 fBestOverlap
= overlap
;
2386 if( ii
==0 || margin
<fBestMargin
){
2388 fBestMargin
= margin
;
2389 iBestSplit
= iBestLeft
;
2393 memcpy(pBboxLeft
, &aCell
[aaSorted
[iBestDim
][0]], sizeof(RtreeCell
));
2394 memcpy(pBboxRight
, &aCell
[aaSorted
[iBestDim
][iBestSplit
]], sizeof(RtreeCell
));
2395 for(ii
=0; ii
<nCell
; ii
++){
2396 RtreeNode
*pTarget
= (ii
<iBestSplit
)?pLeft
:pRight
;
2397 RtreeCell
*pBbox
= (ii
<iBestSplit
)?pBboxLeft
:pBboxRight
;
2398 RtreeCell
*pCell
= &aCell
[aaSorted
[iBestDim
][ii
]];
2399 nodeInsertCell(pRtree
, pTarget
, pCell
);
2400 cellUnion(pRtree
, pBbox
, pCell
);
2403 sqlite3_free(aaSorted
);
2408 static int updateMapping(
2414 int (*xSetMapping
)(Rtree
*, sqlite3_int64
, sqlite3_int64
);
2415 xSetMapping
= ((iHeight
==0)?rowidWrite
:parentWrite
);
2417 RtreeNode
*pChild
= nodeHashLookup(pRtree
, iRowid
);
2419 nodeRelease(pRtree
, pChild
->pParent
);
2420 nodeReference(pNode
);
2421 pChild
->pParent
= pNode
;
2424 return xSetMapping(pRtree
, iRowid
, pNode
->iNode
);
2427 static int SplitNode(
2434 int newCellIsRight
= 0;
2437 int nCell
= NCELL(pNode
);
2441 RtreeNode
*pLeft
= 0;
2442 RtreeNode
*pRight
= 0;
2445 RtreeCell rightbbox
;
2447 /* Allocate an array and populate it with a copy of pCell and
2448 ** all cells from node pLeft. Then zero the original node.
2450 aCell
= sqlite3_malloc((sizeof(RtreeCell
)+sizeof(int))*(nCell
+1));
2455 aiUsed
= (int *)&aCell
[nCell
+1];
2456 memset(aiUsed
, 0, sizeof(int)*(nCell
+1));
2457 for(i
=0; i
<nCell
; i
++){
2458 nodeGetCell(pRtree
, pNode
, i
, &aCell
[i
]);
2460 nodeZero(pRtree
, pNode
);
2461 memcpy(&aCell
[nCell
], pCell
, sizeof(RtreeCell
));
2464 if( pNode
->iNode
==1 ){
2465 pRight
= nodeNew(pRtree
, pNode
);
2466 pLeft
= nodeNew(pRtree
, pNode
);
2469 writeInt16(pNode
->zData
, pRtree
->iDepth
);
2472 pRight
= nodeNew(pRtree
, pLeft
->pParent
);
2473 nodeReference(pLeft
);
2476 if( !pLeft
|| !pRight
){
2481 memset(pLeft
->zData
, 0, pRtree
->iNodeSize
);
2482 memset(pRight
->zData
, 0, pRtree
->iNodeSize
);
2484 rc
= splitNodeStartree(pRtree
, aCell
, nCell
, pLeft
, pRight
,
2485 &leftbbox
, &rightbbox
);
2486 if( rc
!=SQLITE_OK
){
2490 /* Ensure both child nodes have node numbers assigned to them by calling
2491 ** nodeWrite(). Node pRight always needs a node number, as it was created
2492 ** by nodeNew() above. But node pLeft sometimes already has a node number.
2493 ** In this case avoid the all to nodeWrite().
2495 if( SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pRight
))
2496 || (0==pLeft
->iNode
&& SQLITE_OK
!=(rc
= nodeWrite(pRtree
, pLeft
)))
2501 rightbbox
.iRowid
= pRight
->iNode
;
2502 leftbbox
.iRowid
= pLeft
->iNode
;
2504 if( pNode
->iNode
==1 ){
2505 rc
= rtreeInsertCell(pRtree
, pLeft
->pParent
, &leftbbox
, iHeight
+1);
2506 if( rc
!=SQLITE_OK
){
2510 RtreeNode
*pParent
= pLeft
->pParent
;
2512 rc
= nodeParentIndex(pRtree
, pLeft
, &iCell
);
2513 if( rc
==SQLITE_OK
){
2514 nodeOverwriteCell(pRtree
, pParent
, &leftbbox
, iCell
);
2515 rc
= AdjustTree(pRtree
, pParent
, &leftbbox
);
2517 if( rc
!=SQLITE_OK
){
2521 if( (rc
= rtreeInsertCell(pRtree
, pRight
->pParent
, &rightbbox
, iHeight
+1)) ){
2525 for(i
=0; i
<NCELL(pRight
); i
++){
2526 i64 iRowid
= nodeGetRowid(pRtree
, pRight
, i
);
2527 rc
= updateMapping(pRtree
, iRowid
, pRight
, iHeight
);
2528 if( iRowid
==pCell
->iRowid
){
2531 if( rc
!=SQLITE_OK
){
2535 if( pNode
->iNode
==1 ){
2536 for(i
=0; i
<NCELL(pLeft
); i
++){
2537 i64 iRowid
= nodeGetRowid(pRtree
, pLeft
, i
);
2538 rc
= updateMapping(pRtree
, iRowid
, pLeft
, iHeight
);
2539 if( rc
!=SQLITE_OK
){
2543 }else if( newCellIsRight
==0 ){
2544 rc
= updateMapping(pRtree
, pCell
->iRowid
, pLeft
, iHeight
);
2547 if( rc
==SQLITE_OK
){
2548 rc
= nodeRelease(pRtree
, pRight
);
2551 if( rc
==SQLITE_OK
){
2552 rc
= nodeRelease(pRtree
, pLeft
);
2557 nodeRelease(pRtree
, pRight
);
2558 nodeRelease(pRtree
, pLeft
);
2559 sqlite3_free(aCell
);
2564 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2565 ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2566 ** the pLeaf->pParent chain all the way up to the root node.
2568 ** This operation is required when a row is deleted (or updated - an update
2569 ** is implemented as a delete followed by an insert). SQLite provides the
2570 ** rowid of the row to delete, which can be used to find the leaf on which
2571 ** the entry resides (argument pLeaf). Once the leaf is located, this
2572 ** function is called to determine its ancestry.
2574 static int fixLeafParent(Rtree
*pRtree
, RtreeNode
*pLeaf
){
2576 RtreeNode
*pChild
= pLeaf
;
2577 while( rc
==SQLITE_OK
&& pChild
->iNode
!=1 && pChild
->pParent
==0 ){
2578 int rc2
= SQLITE_OK
; /* sqlite3_reset() return code */
2579 sqlite3_bind_int64(pRtree
->pReadParent
, 1, pChild
->iNode
);
2580 rc
= sqlite3_step(pRtree
->pReadParent
);
2581 if( rc
==SQLITE_ROW
){
2582 RtreeNode
*pTest
; /* Used to test for reference loops */
2583 i64 iNode
; /* Node number of parent node */
2585 /* Before setting pChild->pParent, test that we are not creating a
2586 ** loop of references (as we would if, say, pChild==pParent). We don't
2587 ** want to do this as it leads to a memory leak when trying to delete
2588 ** the referenced counted node structures.
2590 iNode
= sqlite3_column_int64(pRtree
->pReadParent
, 0);
2591 for(pTest
=pLeaf
; pTest
&& pTest
->iNode
!=iNode
; pTest
=pTest
->pParent
);
2593 rc2
= nodeAcquire(pRtree
, iNode
, 0, &pChild
->pParent
);
2596 rc
= sqlite3_reset(pRtree
->pReadParent
);
2597 if( rc
==SQLITE_OK
) rc
= rc2
;
2598 if( rc
==SQLITE_OK
&& !pChild
->pParent
) rc
= SQLITE_CORRUPT_VTAB
;
2599 pChild
= pChild
->pParent
;
2604 static int deleteCell(Rtree
*, RtreeNode
*, int, int);
2606 static int removeNode(Rtree
*pRtree
, RtreeNode
*pNode
, int iHeight
){
2609 RtreeNode
*pParent
= 0;
2612 assert( pNode
->nRef
==1 );
2614 /* Remove the entry in the parent cell. */
2615 rc
= nodeParentIndex(pRtree
, pNode
, &iCell
);
2616 if( rc
==SQLITE_OK
){
2617 pParent
= pNode
->pParent
;
2619 rc
= deleteCell(pRtree
, pParent
, iCell
, iHeight
+1);
2621 rc2
= nodeRelease(pRtree
, pParent
);
2622 if( rc
==SQLITE_OK
){
2625 if( rc
!=SQLITE_OK
){
2629 /* Remove the xxx_node entry. */
2630 sqlite3_bind_int64(pRtree
->pDeleteNode
, 1, pNode
->iNode
);
2631 sqlite3_step(pRtree
->pDeleteNode
);
2632 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteNode
)) ){
2636 /* Remove the xxx_parent entry. */
2637 sqlite3_bind_int64(pRtree
->pDeleteParent
, 1, pNode
->iNode
);
2638 sqlite3_step(pRtree
->pDeleteParent
);
2639 if( SQLITE_OK
!=(rc
= sqlite3_reset(pRtree
->pDeleteParent
)) ){
2643 /* Remove the node from the in-memory hash table and link it into
2644 ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2646 nodeHashDelete(pRtree
, pNode
);
2647 pNode
->iNode
= iHeight
;
2648 pNode
->pNext
= pRtree
->pDeleted
;
2650 pRtree
->pDeleted
= pNode
;
2655 static int fixBoundingBox(Rtree
*pRtree
, RtreeNode
*pNode
){
2656 RtreeNode
*pParent
= pNode
->pParent
;
2660 int nCell
= NCELL(pNode
);
2661 RtreeCell box
; /* Bounding box for pNode */
2662 nodeGetCell(pRtree
, pNode
, 0, &box
);
2663 for(ii
=1; ii
<nCell
; ii
++){
2665 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2666 cellUnion(pRtree
, &box
, &cell
);
2668 box
.iRowid
= pNode
->iNode
;
2669 rc
= nodeParentIndex(pRtree
, pNode
, &ii
);
2670 if( rc
==SQLITE_OK
){
2671 nodeOverwriteCell(pRtree
, pParent
, &box
, ii
);
2672 rc
= fixBoundingBox(pRtree
, pParent
);
2679 ** Delete the cell at index iCell of node pNode. After removing the
2680 ** cell, adjust the r-tree data structure if required.
2682 static int deleteCell(Rtree
*pRtree
, RtreeNode
*pNode
, int iCell
, int iHeight
){
2686 if( SQLITE_OK
!=(rc
= fixLeafParent(pRtree
, pNode
)) ){
2690 /* Remove the cell from the node. This call just moves bytes around
2691 ** the in-memory node image, so it cannot fail.
2693 nodeDeleteCell(pRtree
, pNode
, iCell
);
2695 /* If the node is not the tree root and now has less than the minimum
2696 ** number of cells, remove it from the tree. Otherwise, update the
2697 ** cell in the parent node so that it tightly contains the updated
2700 pParent
= pNode
->pParent
;
2701 assert( pParent
|| pNode
->iNode
==1 );
2703 if( NCELL(pNode
)<RTREE_MINCELLS(pRtree
) ){
2704 rc
= removeNode(pRtree
, pNode
, iHeight
);
2706 rc
= fixBoundingBox(pRtree
, pNode
);
2713 static int Reinsert(
2722 RtreeDValue
*aDistance
;
2724 RtreeDValue aCenterCoord
[RTREE_MAX_DIMENSIONS
];
2730 memset(aCenterCoord
, 0, sizeof(RtreeDValue
)*RTREE_MAX_DIMENSIONS
);
2732 nCell
= NCELL(pNode
)+1;
2735 /* Allocate the buffers used by this operation. The allocation is
2736 ** relinquished before this function returns.
2738 aCell
= (RtreeCell
*)sqlite3_malloc(n
* (
2739 sizeof(RtreeCell
) + /* aCell array */
2740 sizeof(int) + /* aOrder array */
2741 sizeof(int) + /* aSpare array */
2742 sizeof(RtreeDValue
) /* aDistance array */
2745 return SQLITE_NOMEM
;
2747 aOrder
= (int *)&aCell
[n
];
2748 aSpare
= (int *)&aOrder
[n
];
2749 aDistance
= (RtreeDValue
*)&aSpare
[n
];
2751 for(ii
=0; ii
<nCell
; ii
++){
2752 if( ii
==(nCell
-1) ){
2753 memcpy(&aCell
[ii
], pCell
, sizeof(RtreeCell
));
2755 nodeGetCell(pRtree
, pNode
, ii
, &aCell
[ii
]);
2758 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2759 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2]);
2760 aCenterCoord
[iDim
] += DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]);
2763 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2764 aCenterCoord
[iDim
] = (aCenterCoord
[iDim
]/(nCell
*(RtreeDValue
)2));
2767 for(ii
=0; ii
<nCell
; ii
++){
2768 aDistance
[ii
] = RTREE_ZERO
;
2769 for(iDim
=0; iDim
<pRtree
->nDim
; iDim
++){
2770 RtreeDValue coord
= (DCOORD(aCell
[ii
].aCoord
[iDim
*2+1]) -
2771 DCOORD(aCell
[ii
].aCoord
[iDim
*2]));
2772 aDistance
[ii
] += (coord
-aCenterCoord
[iDim
])*(coord
-aCenterCoord
[iDim
]);
2776 SortByDistance(aOrder
, nCell
, aDistance
, aSpare
);
2777 nodeZero(pRtree
, pNode
);
2779 for(ii
=0; rc
==SQLITE_OK
&& ii
<(nCell
-(RTREE_MINCELLS(pRtree
)+1)); ii
++){
2780 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2781 nodeInsertCell(pRtree
, pNode
, p
);
2782 if( p
->iRowid
==pCell
->iRowid
){
2784 rc
= rowidWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2786 rc
= parentWrite(pRtree
, p
->iRowid
, pNode
->iNode
);
2790 if( rc
==SQLITE_OK
){
2791 rc
= fixBoundingBox(pRtree
, pNode
);
2793 for(; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2794 /* Find a node to store this cell in. pNode->iNode currently contains
2795 ** the height of the sub-tree headed by the cell.
2798 RtreeCell
*p
= &aCell
[aOrder
[ii
]];
2799 rc
= ChooseLeaf(pRtree
, p
, iHeight
, &pInsert
);
2800 if( rc
==SQLITE_OK
){
2802 rc
= rtreeInsertCell(pRtree
, pInsert
, p
, iHeight
);
2803 rc2
= nodeRelease(pRtree
, pInsert
);
2804 if( rc
==SQLITE_OK
){
2810 sqlite3_free(aCell
);
2815 ** Insert cell pCell into node pNode. Node pNode is the head of a
2816 ** subtree iHeight high (leaf nodes have iHeight==0).
2818 static int rtreeInsertCell(
2826 RtreeNode
*pChild
= nodeHashLookup(pRtree
, pCell
->iRowid
);
2828 nodeRelease(pRtree
, pChild
->pParent
);
2829 nodeReference(pNode
);
2830 pChild
->pParent
= pNode
;
2833 if( nodeInsertCell(pRtree
, pNode
, pCell
) ){
2834 if( iHeight
<=pRtree
->iReinsertHeight
|| pNode
->iNode
==1){
2835 rc
= SplitNode(pRtree
, pNode
, pCell
, iHeight
);
2837 pRtree
->iReinsertHeight
= iHeight
;
2838 rc
= Reinsert(pRtree
, pNode
, pCell
, iHeight
);
2841 rc
= AdjustTree(pRtree
, pNode
, pCell
);
2842 if( rc
==SQLITE_OK
){
2844 rc
= rowidWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2846 rc
= parentWrite(pRtree
, pCell
->iRowid
, pNode
->iNode
);
2853 static int reinsertNodeContent(Rtree
*pRtree
, RtreeNode
*pNode
){
2856 int nCell
= NCELL(pNode
);
2858 for(ii
=0; rc
==SQLITE_OK
&& ii
<nCell
; ii
++){
2861 nodeGetCell(pRtree
, pNode
, ii
, &cell
);
2863 /* Find a node to store this cell in. pNode->iNode currently contains
2864 ** the height of the sub-tree headed by the cell.
2866 rc
= ChooseLeaf(pRtree
, &cell
, (int)pNode
->iNode
, &pInsert
);
2867 if( rc
==SQLITE_OK
){
2869 rc
= rtreeInsertCell(pRtree
, pInsert
, &cell
, (int)pNode
->iNode
);
2870 rc2
= nodeRelease(pRtree
, pInsert
);
2871 if( rc
==SQLITE_OK
){
2880 ** Select a currently unused rowid for a new r-tree record.
2882 static int newRowid(Rtree
*pRtree
, i64
*piRowid
){
2884 sqlite3_bind_null(pRtree
->pWriteRowid
, 1);
2885 sqlite3_bind_null(pRtree
->pWriteRowid
, 2);
2886 sqlite3_step(pRtree
->pWriteRowid
);
2887 rc
= sqlite3_reset(pRtree
->pWriteRowid
);
2888 *piRowid
= sqlite3_last_insert_rowid(pRtree
->db
);
2893 ** Remove the entry with rowid=iDelete from the r-tree structure.
2895 static int rtreeDeleteRowid(Rtree
*pRtree
, sqlite3_int64 iDelete
){
2896 int rc
; /* Return code */
2897 RtreeNode
*pLeaf
= 0; /* Leaf node containing record iDelete */
2898 int iCell
; /* Index of iDelete cell in pLeaf */
2899 RtreeNode
*pRoot
= 0; /* Root node of rtree structure */
2902 /* Obtain a reference to the root node to initialize Rtree.iDepth */
2903 rc
= nodeAcquire(pRtree
, 1, 0, &pRoot
);
2905 /* Obtain a reference to the leaf node that contains the entry
2906 ** about to be deleted.
2908 if( rc
==SQLITE_OK
){
2909 rc
= findLeafNode(pRtree
, iDelete
, &pLeaf
, 0);
2912 /* Delete the cell in question from the leaf node. */
2913 if( rc
==SQLITE_OK
){
2915 rc
= nodeRowidIndex(pRtree
, pLeaf
, iDelete
, &iCell
);
2916 if( rc
==SQLITE_OK
){
2917 rc
= deleteCell(pRtree
, pLeaf
, iCell
, 0);
2919 rc2
= nodeRelease(pRtree
, pLeaf
);
2920 if( rc
==SQLITE_OK
){
2925 /* Delete the corresponding entry in the <rtree>_rowid table. */
2926 if( rc
==SQLITE_OK
){
2927 sqlite3_bind_int64(pRtree
->pDeleteRowid
, 1, iDelete
);
2928 sqlite3_step(pRtree
->pDeleteRowid
);
2929 rc
= sqlite3_reset(pRtree
->pDeleteRowid
);
2932 /* Check if the root node now has exactly one child. If so, remove
2933 ** it, schedule the contents of the child for reinsertion and
2934 ** reduce the tree height by one.
2936 ** This is equivalent to copying the contents of the child into
2937 ** the root node (the operation that Gutman's paper says to perform
2938 ** in this scenario).
2940 if( rc
==SQLITE_OK
&& pRtree
->iDepth
>0 && NCELL(pRoot
)==1 ){
2942 RtreeNode
*pChild
= 0;
2943 i64 iChild
= nodeGetRowid(pRtree
, pRoot
, 0);
2944 rc
= nodeAcquire(pRtree
, iChild
, pRoot
, &pChild
);
2945 if( rc
==SQLITE_OK
){
2946 rc
= removeNode(pRtree
, pChild
, pRtree
->iDepth
-1);
2948 rc2
= nodeRelease(pRtree
, pChild
);
2949 if( rc
==SQLITE_OK
) rc
= rc2
;
2950 if( rc
==SQLITE_OK
){
2952 writeInt16(pRoot
->zData
, pRtree
->iDepth
);
2957 /* Re-insert the contents of any underfull nodes removed from the tree. */
2958 for(pLeaf
=pRtree
->pDeleted
; pLeaf
; pLeaf
=pRtree
->pDeleted
){
2959 if( rc
==SQLITE_OK
){
2960 rc
= reinsertNodeContent(pRtree
, pLeaf
);
2962 pRtree
->pDeleted
= pLeaf
->pNext
;
2963 sqlite3_free(pLeaf
);
2966 /* Release the reference to the root node. */
2967 if( rc
==SQLITE_OK
){
2968 rc
= nodeRelease(pRtree
, pRoot
);
2970 nodeRelease(pRtree
, pRoot
);
2977 ** Rounding constants for float->double conversion.
2979 #define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */
2980 #define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */
2982 #if !defined(SQLITE_RTREE_INT_ONLY)
2984 ** Convert an sqlite3_value into an RtreeValue (presumably a float)
2985 ** while taking care to round toward negative or positive, respectively.
2987 static RtreeValue
rtreeValueDown(sqlite3_value
*v
){
2988 double d
= sqlite3_value_double(v
);
2991 f
= (float)(d
*(d
<0 ? RNDAWAY
: RNDTOWARDS
));
2995 static RtreeValue
rtreeValueUp(sqlite3_value
*v
){
2996 double d
= sqlite3_value_double(v
);
2999 f
= (float)(d
*(d
<0 ? RNDTOWARDS
: RNDAWAY
));
3003 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */
3006 ** A constraint has failed while inserting a row into an rtree table.
3007 ** Assuming no OOM error occurs, this function sets the error message
3008 ** (at pRtree->base.zErrMsg) to an appropriate value and returns
3009 ** SQLITE_CONSTRAINT.
3011 ** Parameter iCol is the index of the leftmost column involved in the
3012 ** constraint failure. If it is 0, then the constraint that failed is
3013 ** the unique constraint on the id column. Otherwise, it is the rtree
3014 ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed.
3016 ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT.
3018 static int rtreeConstraintError(Rtree
*pRtree
, int iCol
){
3019 sqlite3_stmt
*pStmt
= 0;
3023 assert( iCol
==0 || iCol
%2 );
3024 zSql
= sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree
->zDb
, pRtree
->zName
);
3026 rc
= sqlite3_prepare_v2(pRtree
->db
, zSql
, -1, &pStmt
, 0);
3032 if( rc
==SQLITE_OK
){
3034 const char *zCol
= sqlite3_column_name(pStmt
, 0);
3035 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
3036 "UNIQUE constraint failed: %s.%s", pRtree
->zName
, zCol
3039 const char *zCol1
= sqlite3_column_name(pStmt
, iCol
);
3040 const char *zCol2
= sqlite3_column_name(pStmt
, iCol
+1);
3041 pRtree
->base
.zErrMsg
= sqlite3_mprintf(
3042 "rtree constraint failed: %s.(%s<=%s)", pRtree
->zName
, zCol1
, zCol2
3047 sqlite3_finalize(pStmt
);
3048 return (rc
==SQLITE_OK
? SQLITE_CONSTRAINT
: rc
);
3054 ** The xUpdate method for rtree module virtual tables.
3056 static int rtreeUpdate(
3057 sqlite3_vtab
*pVtab
,
3059 sqlite3_value
**aData
,
3060 sqlite_int64
*pRowid
3062 Rtree
*pRtree
= (Rtree
*)pVtab
;
3064 RtreeCell cell
; /* New cell to insert if nData>1 */
3065 int bHaveRowid
= 0; /* Set to 1 after new rowid is determined */
3067 rtreeReference(pRtree
);
3070 cell
.iRowid
= 0; /* Used only to suppress a compiler warning */
3072 /* Constraint handling. A write operation on an r-tree table may return
3073 ** SQLITE_CONSTRAINT for two reasons:
3075 ** 1. A duplicate rowid value, or
3076 ** 2. The supplied data violates the "x2>=x1" constraint.
3078 ** In the first case, if the conflict-handling mode is REPLACE, then
3079 ** the conflicting row can be removed before proceeding. In the second
3080 ** case, SQLITE_CONSTRAINT must be returned regardless of the
3081 ** conflict-handling mode specified by the user.
3087 if( nn
> pRtree
->nDim2
) nn
= pRtree
->nDim2
;
3088 /* Populate the cell.aCoord[] array. The first coordinate is aData[3].
3090 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
3091 ** with "column" that are interpreted as table constraints.
3092 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
3093 ** This problem was discovered after years of use, so we silently ignore
3094 ** these kinds of misdeclared tables to avoid breaking any legacy.
3097 #ifndef SQLITE_RTREE_INT_ONLY
3098 if( pRtree
->eCoordType
==RTREE_COORD_REAL32
){
3099 for(ii
=0; ii
<nn
; ii
+=2){
3100 cell
.aCoord
[ii
].f
= rtreeValueDown(aData
[ii
+3]);
3101 cell
.aCoord
[ii
+1].f
= rtreeValueUp(aData
[ii
+4]);
3102 if( cell
.aCoord
[ii
].f
>cell
.aCoord
[ii
+1].f
){
3103 rc
= rtreeConstraintError(pRtree
, ii
+1);
3110 for(ii
=0; ii
<nn
; ii
+=2){
3111 cell
.aCoord
[ii
].i
= sqlite3_value_int(aData
[ii
+3]);
3112 cell
.aCoord
[ii
+1].i
= sqlite3_value_int(aData
[ii
+4]);
3113 if( cell
.aCoord
[ii
].i
>cell
.aCoord
[ii
+1].i
){
3114 rc
= rtreeConstraintError(pRtree
, ii
+1);
3120 /* If a rowid value was supplied, check if it is already present in
3121 ** the table. If so, the constraint has failed. */
3122 if( sqlite3_value_type(aData
[2])!=SQLITE_NULL
){
3123 cell
.iRowid
= sqlite3_value_int64(aData
[2]);
3124 if( sqlite3_value_type(aData
[0])==SQLITE_NULL
3125 || sqlite3_value_int64(aData
[0])!=cell
.iRowid
3128 sqlite3_bind_int64(pRtree
->pReadRowid
, 1, cell
.iRowid
);
3129 steprc
= sqlite3_step(pRtree
->pReadRowid
);
3130 rc
= sqlite3_reset(pRtree
->pReadRowid
);
3131 if( SQLITE_ROW
==steprc
){
3132 if( sqlite3_vtab_on_conflict(pRtree
->db
)==SQLITE_REPLACE
){
3133 rc
= rtreeDeleteRowid(pRtree
, cell
.iRowid
);
3135 rc
= rtreeConstraintError(pRtree
, 0);
3144 /* If aData[0] is not an SQL NULL value, it is the rowid of a
3145 ** record to delete from the r-tree table. The following block does
3148 if( sqlite3_value_type(aData
[0])!=SQLITE_NULL
){
3149 rc
= rtreeDeleteRowid(pRtree
, sqlite3_value_int64(aData
[0]));
3152 /* If the aData[] array contains more than one element, elements
3153 ** (aData[2]..aData[argc-1]) contain a new record to insert into
3154 ** the r-tree structure.
3156 if( rc
==SQLITE_OK
&& nData
>1 ){
3157 /* Insert the new record into the r-tree */
3158 RtreeNode
*pLeaf
= 0;
3160 /* Figure out the rowid of the new row. */
3161 if( bHaveRowid
==0 ){
3162 rc
= newRowid(pRtree
, &cell
.iRowid
);
3164 *pRowid
= cell
.iRowid
;
3166 if( rc
==SQLITE_OK
){
3167 rc
= ChooseLeaf(pRtree
, &cell
, 0, &pLeaf
);
3169 if( rc
==SQLITE_OK
){
3171 pRtree
->iReinsertHeight
= -1;
3172 rc
= rtreeInsertCell(pRtree
, pLeaf
, &cell
, 0);
3173 rc2
= nodeRelease(pRtree
, pLeaf
);
3174 if( rc
==SQLITE_OK
){
3179 sqlite3_stmt
*pUp
= pRtree
->pWriteAux
;
3181 sqlite3_bind_int64(pUp
, 1, *pRowid
);
3182 for(jj
=0; jj
<pRtree
->nAux
; jj
++){
3183 sqlite3_bind_value(pUp
, jj
+2, aData
[pRtree
->nDim2
+3+jj
]);
3186 rc
= sqlite3_reset(pUp
);
3191 rtreeRelease(pRtree
);
3196 ** Called when a transaction starts.
3198 static int rtreeBeginTransaction(sqlite3_vtab
*pVtab
){
3199 Rtree
*pRtree
= (Rtree
*)pVtab
;
3200 assert( pRtree
->inWrTrans
==0 );
3201 pRtree
->inWrTrans
++;
3206 ** Called when a transaction completes (either by COMMIT or ROLLBACK).
3207 ** The sqlite3_blob object should be released at this point.
3209 static int rtreeEndTransaction(sqlite3_vtab
*pVtab
){
3210 Rtree
*pRtree
= (Rtree
*)pVtab
;
3211 pRtree
->inWrTrans
= 0;
3212 nodeBlobReset(pRtree
);
3217 ** The xRename method for rtree module virtual tables.
3219 static int rtreeRename(sqlite3_vtab
*pVtab
, const char *zNewName
){
3220 Rtree
*pRtree
= (Rtree
*)pVtab
;
3221 int rc
= SQLITE_NOMEM
;
3222 char *zSql
= sqlite3_mprintf(
3223 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
3224 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
3225 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
3226 , pRtree
->zDb
, pRtree
->zName
, zNewName
3227 , pRtree
->zDb
, pRtree
->zName
, zNewName
3228 , pRtree
->zDb
, pRtree
->zName
, zNewName
3231 nodeBlobReset(pRtree
);
3232 rc
= sqlite3_exec(pRtree
->db
, zSql
, 0, 0, 0);
3239 ** The xSavepoint method.
3241 ** This module does not need to do anything to support savepoints. However,
3242 ** it uses this hook to close any open blob handle. This is done because a
3243 ** DROP TABLE command - which fortunately always opens a savepoint - cannot
3244 ** succeed if there are any open blob handles. i.e. if the blob handle were
3245 ** not closed here, the following would fail:
3248 ** INSERT INTO rtree...
3249 ** DROP TABLE <tablename>; -- Would fail with SQLITE_LOCKED
3252 static int rtreeSavepoint(sqlite3_vtab
*pVtab
, int iSavepoint
){
3253 Rtree
*pRtree
= (Rtree
*)pVtab
;
3254 int iwt
= pRtree
->inWrTrans
;
3255 UNUSED_PARAMETER(iSavepoint
);
3256 pRtree
->inWrTrans
= 0;
3257 nodeBlobReset(pRtree
);
3258 pRtree
->inWrTrans
= iwt
;
3263 ** This function populates the pRtree->nRowEst variable with an estimate
3264 ** of the number of rows in the virtual table. If possible, this is based
3265 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
3267 static int rtreeQueryStat1(sqlite3
*db
, Rtree
*pRtree
){
3268 const char *zFmt
= "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
3274 rc
= sqlite3_table_column_metadata(
3275 db
, pRtree
->zDb
, "sqlite_stat1",0,0,0,0,0,0
3277 if( rc
!=SQLITE_OK
){
3278 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3279 return rc
==SQLITE_ERROR
? SQLITE_OK
: rc
;
3281 zSql
= sqlite3_mprintf(zFmt
, pRtree
->zDb
, pRtree
->zName
);
3285 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &p
, 0);
3286 if( rc
==SQLITE_OK
){
3287 if( sqlite3_step(p
)==SQLITE_ROW
) nRow
= sqlite3_column_int64(p
, 0);
3288 rc
= sqlite3_finalize(p
);
3289 }else if( rc
!=SQLITE_NOMEM
){
3293 if( rc
==SQLITE_OK
){
3295 pRtree
->nRowEst
= RTREE_DEFAULT_ROWEST
;
3297 pRtree
->nRowEst
= MAX(nRow
, RTREE_MIN_ROWEST
);
3306 static sqlite3_module rtreeModule
= {
3308 rtreeCreate
, /* xCreate - create a table */
3309 rtreeConnect
, /* xConnect - connect to an existing table */
3310 rtreeBestIndex
, /* xBestIndex - Determine search strategy */
3311 rtreeDisconnect
, /* xDisconnect - Disconnect from a table */
3312 rtreeDestroy
, /* xDestroy - Drop a table */
3313 rtreeOpen
, /* xOpen - open a cursor */
3314 rtreeClose
, /* xClose - close a cursor */
3315 rtreeFilter
, /* xFilter - configure scan constraints */
3316 rtreeNext
, /* xNext - advance a cursor */
3317 rtreeEof
, /* xEof */
3318 rtreeColumn
, /* xColumn - read data */
3319 rtreeRowid
, /* xRowid - read data */
3320 rtreeUpdate
, /* xUpdate - write data */
3321 rtreeBeginTransaction
, /* xBegin - begin transaction */
3322 rtreeEndTransaction
, /* xSync - sync transaction */
3323 rtreeEndTransaction
, /* xCommit - commit transaction */
3324 rtreeEndTransaction
, /* xRollback - rollback transaction */
3325 0, /* xFindFunction - function overloading */
3326 rtreeRename
, /* xRename - rename the table */
3327 rtreeSavepoint
, /* xSavepoint */
3329 0, /* xRollbackTo */
3332 static int rtreeSqlInit(
3336 const char *zPrefix
,
3341 #define N_STATEMENT 8
3342 static const char *azSql
[N_STATEMENT
] = {
3343 /* Write the xxx_node table */
3344 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(?1, ?2)",
3345 "DELETE FROM '%q'.'%q_node' WHERE nodeno = ?1",
3347 /* Read and write the xxx_rowid table */
3348 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3349 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(?1, ?2)",
3350 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3352 /* Read and write the xxx_parent table */
3353 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = ?1",
3354 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(?1, ?2)",
3355 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = ?1"
3357 sqlite3_stmt
**appStmt
[N_STATEMENT
];
3364 sqlite3_str
*p
= sqlite3_str_new(db
);
3366 sqlite3_str_appendf(p
,
3367 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY,nodeno",
3369 for(ii
=0; ii
<pRtree
->nAux
; ii
++){
3370 sqlite3_str_appendf(p
,",a%d",ii
);
3372 sqlite3_str_appendf(p
,
3373 ");CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY,data);",
3375 sqlite3_str_appendf(p
,
3376 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,parentnode);",
3378 sqlite3_str_appendf(p
,
3379 "INSERT INTO \"%w\".\"%w_node\"VALUES(1,zeroblob(%d))",
3380 zDb
, zPrefix
, pRtree
->iNodeSize
);
3381 zCreate
= sqlite3_str_finish(p
);
3383 return SQLITE_NOMEM
;
3385 rc
= sqlite3_exec(db
, zCreate
, 0, 0, 0);
3386 sqlite3_free(zCreate
);
3387 if( rc
!=SQLITE_OK
){
3392 appStmt
[0] = &pRtree
->pWriteNode
;
3393 appStmt
[1] = &pRtree
->pDeleteNode
;
3394 appStmt
[2] = &pRtree
->pReadRowid
;
3395 appStmt
[3] = &pRtree
->pWriteRowid
;
3396 appStmt
[4] = &pRtree
->pDeleteRowid
;
3397 appStmt
[5] = &pRtree
->pReadParent
;
3398 appStmt
[6] = &pRtree
->pWriteParent
;
3399 appStmt
[7] = &pRtree
->pDeleteParent
;
3401 rc
= rtreeQueryStat1(db
, pRtree
);
3402 for(i
=0; i
<N_STATEMENT
&& rc
==SQLITE_OK
; i
++){
3404 const char *zFormat
;
3405 if( i
!=3 || pRtree
->nAux
==0 ){
3408 /* An UPSERT is very slightly slower than REPLACE, but it is needed
3409 ** if there are auxiliary columns */
3410 zFormat
= "INSERT INTO\"%w\".\"%w_rowid\"(rowid,nodeno)VALUES(?1,?2)"
3411 "ON CONFLICT(rowid)DO UPDATE SET nodeno=excluded.nodeno";
3413 zSql
= sqlite3_mprintf(zFormat
, zDb
, zPrefix
);
3415 rc
= sqlite3_prepare_v3(db
, zSql
, -1, SQLITE_PREPARE_PERSISTENT
,
3423 pRtree
->zReadAuxSql
= sqlite3_mprintf(
3424 "SELECT * FROM \"%w\".\"%w_rowid\" WHERE rowid=?1",
3426 if( pRtree
->zReadAuxSql
==0 ){
3429 sqlite3_str
*p
= sqlite3_str_new(db
);
3432 sqlite3_str_appendf(p
, "UPDATE \"%w\".\"%w_rowid\"SET ", zDb
, zPrefix
);
3433 for(ii
=0; ii
<pRtree
->nAux
; ii
++){
3434 if( ii
) sqlite3_str_append(p
, ",", 1);
3435 sqlite3_str_appendf(p
,"a%d=?%d",ii
,ii
+2);
3437 sqlite3_str_appendf(p
, " WHERE rowid=?1");
3438 zSql
= sqlite3_str_finish(p
);
3442 rc
= sqlite3_prepare_v3(db
, zSql
, -1, SQLITE_PREPARE_PERSISTENT
,
3443 &pRtree
->pWriteAux
, 0);
3453 ** The second argument to this function contains the text of an SQL statement
3454 ** that returns a single integer value. The statement is compiled and executed
3455 ** using database connection db. If successful, the integer value returned
3456 ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
3457 ** code is returned and the value of *piVal after returning is not defined.
3459 static int getIntFromStmt(sqlite3
*db
, const char *zSql
, int *piVal
){
3460 int rc
= SQLITE_NOMEM
;
3462 sqlite3_stmt
*pStmt
= 0;
3463 rc
= sqlite3_prepare_v2(db
, zSql
, -1, &pStmt
, 0);
3464 if( rc
==SQLITE_OK
){
3465 if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
3466 *piVal
= sqlite3_column_int(pStmt
, 0);
3468 rc
= sqlite3_finalize(pStmt
);
3475 ** This function is called from within the xConnect() or xCreate() method to
3476 ** determine the node-size used by the rtree table being created or connected
3477 ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
3478 ** Otherwise, an SQLite error code is returned.
3480 ** If this function is being called as part of an xConnect(), then the rtree
3481 ** table already exists. In this case the node-size is determined by inspecting
3482 ** the root node of the tree.
3484 ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
3485 ** This ensures that each node is stored on a single database page. If the
3486 ** database page-size is so large that more than RTREE_MAXCELLS entries
3487 ** would fit in a single node, use a smaller node-size.
3489 static int getNodeSize(
3490 sqlite3
*db
, /* Database handle */
3491 Rtree
*pRtree
, /* Rtree handle */
3492 int isCreate
, /* True for xCreate, false for xConnect */
3493 char **pzErr
/* OUT: Error message, if any */
3499 zSql
= sqlite3_mprintf("PRAGMA %Q.page_size", pRtree
->zDb
);
3500 rc
= getIntFromStmt(db
, zSql
, &iPageSize
);
3501 if( rc
==SQLITE_OK
){
3502 pRtree
->iNodeSize
= iPageSize
-64;
3503 if( (4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
)<pRtree
->iNodeSize
){
3504 pRtree
->iNodeSize
= 4+pRtree
->nBytesPerCell
*RTREE_MAXCELLS
;
3507 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3510 zSql
= sqlite3_mprintf(
3511 "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
3512 pRtree
->zDb
, pRtree
->zName
3514 rc
= getIntFromStmt(db
, zSql
, &pRtree
->iNodeSize
);
3515 if( rc
!=SQLITE_OK
){
3516 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3517 }else if( pRtree
->iNodeSize
<(512-64) ){
3518 rc
= SQLITE_CORRUPT_VTAB
;
3519 *pzErr
= sqlite3_mprintf("undersize RTree blobs in \"%q_node\"",
3529 ** This function is the implementation of both the xConnect and xCreate
3530 ** methods of the r-tree virtual table.
3532 ** argv[0] -> module name
3533 ** argv[1] -> database name
3534 ** argv[2] -> table name
3535 ** argv[...] -> column names...
3537 static int rtreeInit(
3538 sqlite3
*db
, /* Database connection */
3539 void *pAux
, /* One of the RTREE_COORD_* constants */
3540 int argc
, const char *const*argv
, /* Parameters to CREATE TABLE statement */
3541 sqlite3_vtab
**ppVtab
, /* OUT: New virtual table */
3542 char **pzErr
, /* OUT: Error message, if any */
3543 int isCreate
/* True for xCreate, false for xConnect */
3547 int nDb
; /* Length of string argv[1] */
3548 int nName
; /* Length of string argv[2] */
3549 int eCoordType
= (pAux
? RTREE_COORD_INT32
: RTREE_COORD_REAL32
);
3555 const char *aErrMsg
[] = {
3557 "Wrong number of columns for an rtree table", /* 1 */
3558 "Too few columns for an rtree table", /* 2 */
3559 "Too many columns for an rtree table", /* 3 */
3560 "Auxiliary rtree columns must be last" /* 4 */
3563 assert( RTREE_MAX_AUX_COLUMN
<256 ); /* Aux columns counted by a u8 */
3564 if( argc
>RTREE_MAX_AUX_COLUMN
+3 ){
3565 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[3]);
3566 return SQLITE_ERROR
;
3569 sqlite3_vtab_config(db
, SQLITE_VTAB_CONSTRAINT_SUPPORT
, 1);
3571 /* Allocate the sqlite3_vtab structure */
3572 nDb
= (int)strlen(argv
[1]);
3573 nName
= (int)strlen(argv
[2]);
3574 pRtree
= (Rtree
*)sqlite3_malloc(sizeof(Rtree
)+nDb
+nName
+2);
3576 return SQLITE_NOMEM
;
3578 memset(pRtree
, 0, sizeof(Rtree
)+nDb
+nName
+2);
3580 pRtree
->base
.pModule
= &rtreeModule
;
3581 pRtree
->zDb
= (char *)&pRtree
[1];
3582 pRtree
->zName
= &pRtree
->zDb
[nDb
+1];
3583 pRtree
->eCoordType
= (u8
)eCoordType
;
3584 memcpy(pRtree
->zDb
, argv
[1], nDb
);
3585 memcpy(pRtree
->zName
, argv
[2], nName
);
3588 /* Create/Connect to the underlying relational database schema. If
3589 ** that is successful, call sqlite3_declare_vtab() to configure
3590 ** the r-tree table schema.
3592 pSql
= sqlite3_str_new(db
);
3593 sqlite3_str_appendf(pSql
, "CREATE TABLE x(%s", argv
[3]);
3594 for(ii
=4; ii
<argc
; ii
++){
3595 if( argv
[ii
][0]=='+' ){
3597 sqlite3_str_appendf(pSql
, ",%s", argv
[ii
]+1);
3598 }else if( pRtree
->nAux
>0 ){
3602 sqlite3_str_appendf(pSql
, ",%s", argv
[ii
]);
3605 sqlite3_str_appendf(pSql
, ");");
3606 zSql
= sqlite3_str_finish(pSql
);
3609 }else if( ii
<argc
){
3610 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[4]);
3612 }else if( SQLITE_OK
!=(rc
= sqlite3_declare_vtab(db
, zSql
)) ){
3613 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3616 if( rc
) goto rtreeInit_fail
;
3617 pRtree
->nDim
= pRtree
->nDim2
/2;
3618 if( pRtree
->nDim
<1 ){
3620 }else if( pRtree
->nDim2
>RTREE_MAX_DIMENSIONS
*2 ){
3622 }else if( pRtree
->nDim2
% 2 ){
3628 *pzErr
= sqlite3_mprintf("%s", aErrMsg
[iErr
]);
3629 goto rtreeInit_fail
;
3631 pRtree
->nBytesPerCell
= 8 + pRtree
->nDim2
*4;
3633 /* Figure out the node size to use. */
3634 rc
= getNodeSize(db
, pRtree
, isCreate
, pzErr
);
3635 if( rc
) goto rtreeInit_fail
;
3636 rc
= rtreeSqlInit(pRtree
, db
, argv
[1], argv
[2], isCreate
);
3638 *pzErr
= sqlite3_mprintf("%s", sqlite3_errmsg(db
));
3639 goto rtreeInit_fail
;
3642 *ppVtab
= (sqlite3_vtab
*)pRtree
;
3646 if( rc
==SQLITE_OK
) rc
= SQLITE_ERROR
;
3647 assert( *ppVtab
==0 );
3648 assert( pRtree
->nBusy
==1 );
3649 rtreeRelease(pRtree
);
3655 ** Implementation of a scalar function that decodes r-tree nodes to
3656 ** human readable strings. This can be used for debugging and analysis.
3658 ** The scalar function takes two arguments: (1) the number of dimensions
3659 ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
3660 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
3661 ** deserialize all nodes, a statement like:
3663 ** SELECT rtreenode(2, data) FROM rt_node;
3665 ** The human readable string takes the form of a Tcl list with one
3666 ** entry for each cell in the r-tree node. Each entry is itself a
3667 ** list, containing the 8-byte rowid/pageno followed by the
3668 ** <num-dimension>*2 coordinates.
3670 static void rtreenode(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3676 UNUSED_PARAMETER(nArg
);
3677 memset(&node
, 0, sizeof(RtreeNode
));
3678 memset(&tree
, 0, sizeof(Rtree
));
3679 tree
.nDim
= (u8
)sqlite3_value_int(apArg
[0]);
3680 tree
.nDim2
= tree
.nDim
*2;
3681 tree
.nBytesPerCell
= 8 + 8 * tree
.nDim
;
3682 node
.zData
= (u8
*)sqlite3_value_blob(apArg
[1]);
3684 for(ii
=0; ii
<NCELL(&node
); ii
++){
3690 nodeGetCell(&tree
, &node
, ii
, &cell
);
3691 sqlite3_snprintf(512-nCell
,&zCell
[nCell
],"%lld", cell
.iRowid
);
3692 nCell
= (int)strlen(zCell
);
3693 for(jj
=0; jj
<tree
.nDim2
; jj
++){
3694 #ifndef SQLITE_RTREE_INT_ONLY
3695 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %g",
3696 (double)cell
.aCoord
[jj
].f
);
3698 sqlite3_snprintf(512-nCell
,&zCell
[nCell
], " %d",
3701 nCell
= (int)strlen(zCell
);
3705 char *zTextNew
= sqlite3_mprintf("%s {%s}", zText
, zCell
);
3706 sqlite3_free(zText
);
3709 zText
= sqlite3_mprintf("{%s}", zCell
);
3713 sqlite3_result_text(ctx
, zText
, -1, sqlite3_free
);
3716 /* This routine implements an SQL function that returns the "depth" parameter
3717 ** from the front of a blob that is an r-tree node. For example:
3719 ** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
3721 ** The depth value is 0 for all nodes other than the root node, and the root
3722 ** node always has nodeno=1, so the example above is the primary use for this
3723 ** routine. This routine is intended for testing and analysis only.
3725 static void rtreedepth(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**apArg
){
3726 UNUSED_PARAMETER(nArg
);
3727 if( sqlite3_value_type(apArg
[0])!=SQLITE_BLOB
3728 || sqlite3_value_bytes(apArg
[0])<2
3730 sqlite3_result_error(ctx
, "Invalid argument to rtreedepth()", -1);
3732 u8
*zBlob
= (u8
*)sqlite3_value_blob(apArg
[0]);
3733 sqlite3_result_int(ctx
, readInt16(zBlob
));
3738 ** Context object passed between the various routines that make up the
3739 ** implementation of integrity-check function rtreecheck().
3741 typedef struct RtreeCheck RtreeCheck
;
3743 sqlite3
*db
; /* Database handle */
3744 const char *zDb
; /* Database containing rtree table */
3745 const char *zTab
; /* Name of rtree table */
3746 int bInt
; /* True for rtree_i32 table */
3747 int nDim
; /* Number of dimensions for this rtree tbl */
3748 sqlite3_stmt
*pGetNode
; /* Statement used to retrieve nodes */
3749 sqlite3_stmt
*aCheckMapping
[2]; /* Statements to query %_parent/%_rowid */
3750 int nLeaf
; /* Number of leaf cells in table */
3751 int nNonLeaf
; /* Number of non-leaf cells in table */
3752 int rc
; /* Return code */
3753 char *zReport
; /* Message to report */
3754 int nErr
; /* Number of lines in zReport */
3757 #define RTREE_CHECK_MAX_ERROR 100
3760 ** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
3761 ** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
3763 static void rtreeCheckReset(RtreeCheck
*pCheck
, sqlite3_stmt
*pStmt
){
3764 int rc
= sqlite3_reset(pStmt
);
3765 if( pCheck
->rc
==SQLITE_OK
) pCheck
->rc
= rc
;
3769 ** The second and subsequent arguments to this function are a format string
3770 ** and printf style arguments. This function formats the string and attempts
3771 ** to compile it as an SQL statement.
3773 ** If successful, a pointer to the new SQL statement is returned. Otherwise,
3774 ** NULL is returned and an error code left in RtreeCheck.rc.
3776 static sqlite3_stmt
*rtreeCheckPrepare(
3777 RtreeCheck
*pCheck
, /* RtreeCheck object */
3778 const char *zFmt
, ... /* Format string and trailing args */
3782 sqlite3_stmt
*pRet
= 0;
3785 z
= sqlite3_vmprintf(zFmt
, ap
);
3787 if( pCheck
->rc
==SQLITE_OK
){
3789 pCheck
->rc
= SQLITE_NOMEM
;
3791 pCheck
->rc
= sqlite3_prepare_v2(pCheck
->db
, z
, -1, &pRet
, 0);
3801 ** The second and subsequent arguments to this function are a printf()
3802 ** style format string and arguments. This function formats the string and
3803 ** appends it to the report being accumuated in pCheck.
3805 static void rtreeCheckAppendMsg(RtreeCheck
*pCheck
, const char *zFmt
, ...){
3808 if( pCheck
->rc
==SQLITE_OK
&& pCheck
->nErr
<RTREE_CHECK_MAX_ERROR
){
3809 char *z
= sqlite3_vmprintf(zFmt
, ap
);
3811 pCheck
->rc
= SQLITE_NOMEM
;
3813 pCheck
->zReport
= sqlite3_mprintf("%z%s%z",
3814 pCheck
->zReport
, (pCheck
->zReport
? "\n" : ""), z
3816 if( pCheck
->zReport
==0 ){
3817 pCheck
->rc
= SQLITE_NOMEM
;
3826 ** This function is a no-op if there is already an error code stored
3827 ** in the RtreeCheck object indicated by the first argument. NULL is
3828 ** returned in this case.
3830 ** Otherwise, the contents of rtree table node iNode are loaded from
3831 ** the database and copied into a buffer obtained from sqlite3_malloc().
3832 ** If no error occurs, a pointer to the buffer is returned and (*pnNode)
3833 ** is set to the size of the buffer in bytes.
3835 ** Or, if an error does occur, NULL is returned and an error code left
3836 ** in the RtreeCheck object. The final value of *pnNode is undefined in
3839 static u8
*rtreeCheckGetNode(RtreeCheck
*pCheck
, i64 iNode
, int *pnNode
){
3840 u8
*pRet
= 0; /* Return value */
3842 assert( pCheck
->rc
==SQLITE_OK
);
3843 if( pCheck
->pGetNode
==0 ){
3844 pCheck
->pGetNode
= rtreeCheckPrepare(pCheck
,
3845 "SELECT data FROM %Q.'%q_node' WHERE nodeno=?",
3846 pCheck
->zDb
, pCheck
->zTab
3850 if( pCheck
->rc
==SQLITE_OK
){
3851 sqlite3_bind_int64(pCheck
->pGetNode
, 1, iNode
);
3852 if( sqlite3_step(pCheck
->pGetNode
)==SQLITE_ROW
){
3853 int nNode
= sqlite3_column_bytes(pCheck
->pGetNode
, 0);
3854 const u8
*pNode
= (const u8
*)sqlite3_column_blob(pCheck
->pGetNode
, 0);
3855 pRet
= sqlite3_malloc(nNode
);
3857 pCheck
->rc
= SQLITE_NOMEM
;
3859 memcpy(pRet
, pNode
, nNode
);
3863 rtreeCheckReset(pCheck
, pCheck
->pGetNode
);
3864 if( pCheck
->rc
==SQLITE_OK
&& pRet
==0 ){
3865 rtreeCheckAppendMsg(pCheck
, "Node %lld missing from database", iNode
);
3873 ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
3874 ** (if bLeaf==1) table contains a specified entry. The schemas of the
3877 ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
3878 ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
3880 ** In both cases, this function checks that there exists an entry with
3881 ** IPK value iKey and the second column set to iVal.
3884 static void rtreeCheckMapping(
3885 RtreeCheck
*pCheck
, /* RtreeCheck object */
3886 int bLeaf
, /* True for a leaf cell, false for interior */
3887 i64 iKey
, /* Key for mapping */
3888 i64 iVal
/* Expected value for mapping */
3891 sqlite3_stmt
*pStmt
;
3892 const char *azSql
[2] = {
3893 "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1",
3894 "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1"
3897 assert( bLeaf
==0 || bLeaf
==1 );
3898 if( pCheck
->aCheckMapping
[bLeaf
]==0 ){
3899 pCheck
->aCheckMapping
[bLeaf
] = rtreeCheckPrepare(pCheck
,
3900 azSql
[bLeaf
], pCheck
->zDb
, pCheck
->zTab
3903 if( pCheck
->rc
!=SQLITE_OK
) return;
3905 pStmt
= pCheck
->aCheckMapping
[bLeaf
];
3906 sqlite3_bind_int64(pStmt
, 1, iKey
);
3907 rc
= sqlite3_step(pStmt
);
3908 if( rc
==SQLITE_DONE
){
3909 rtreeCheckAppendMsg(pCheck
, "Mapping (%lld -> %lld) missing from %s table",
3910 iKey
, iVal
, (bLeaf
? "%_rowid" : "%_parent")
3912 }else if( rc
==SQLITE_ROW
){
3913 i64 ii
= sqlite3_column_int64(pStmt
, 0);
3915 rtreeCheckAppendMsg(pCheck
,
3916 "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
3917 iKey
, ii
, (bLeaf
? "%_rowid" : "%_parent"), iKey
, iVal
3921 rtreeCheckReset(pCheck
, pStmt
);
3925 ** Argument pCell points to an array of coordinates stored on an rtree page.
3926 ** This function checks that the coordinates are internally consistent (no
3927 ** x1>x2 conditions) and adds an error message to the RtreeCheck object
3930 ** Additionally, if pParent is not NULL, then it is assumed to point to
3931 ** the array of coordinates on the parent page that bound the page
3932 ** containing pCell. In this case it is also verified that the two
3933 ** sets of coordinates are mutually consistent and an error message added
3934 ** to the RtreeCheck object if they are not.
3936 static void rtreeCheckCellCoord(
3938 i64 iNode
, /* Node id to use in error messages */
3939 int iCell
, /* Cell number to use in error messages */
3940 u8
*pCell
, /* Pointer to cell coordinates */
3941 u8
*pParent
/* Pointer to parent coordinates */
3947 for(i
=0; i
<pCheck
->nDim
; i
++){
3948 readCoord(&pCell
[4*2*i
], &c1
);
3949 readCoord(&pCell
[4*(2*i
+ 1)], &c2
);
3951 /* printf("%e, %e\n", c1.u.f, c2.u.f); */
3952 if( pCheck
->bInt
? c1
.i
>c2
.i
: c1
.f
>c2
.f
){
3953 rtreeCheckAppendMsg(pCheck
,
3954 "Dimension %d of cell %d on node %lld is corrupt", i
, iCell
, iNode
3959 readCoord(&pParent
[4*2*i
], &p1
);
3960 readCoord(&pParent
[4*(2*i
+ 1)], &p2
);
3962 if( (pCheck
->bInt
? c1
.i
<p1
.i
: c1
.f
<p1
.f
)
3963 || (pCheck
->bInt
? c2
.i
>p2
.i
: c2
.f
>p2
.f
)
3965 rtreeCheckAppendMsg(pCheck
,
3966 "Dimension %d of cell %d on node %lld is corrupt relative to parent"
3975 ** Run rtreecheck() checks on node iNode, which is at depth iDepth within
3976 ** the r-tree structure. Argument aParent points to the array of coordinates
3977 ** that bound node iNode on the parent node.
3979 ** If any problems are discovered, an error message is appended to the
3980 ** report accumulated in the RtreeCheck object.
3982 static void rtreeCheckNode(
3984 int iDepth
, /* Depth of iNode (0==leaf) */
3985 u8
*aParent
, /* Buffer containing parent coords */
3986 i64 iNode
/* Node to check */
3991 assert( iNode
==1 || aParent
!=0 );
3992 assert( pCheck
->nDim
>0 );
3994 aNode
= rtreeCheckGetNode(pCheck
, iNode
, &nNode
);
3997 rtreeCheckAppendMsg(pCheck
,
3998 "Node %lld is too small (%d bytes)", iNode
, nNode
4001 int nCell
; /* Number of cells on page */
4002 int i
; /* Used to iterate through cells */
4004 iDepth
= readInt16(aNode
);
4005 if( iDepth
>RTREE_MAX_DEPTH
){
4006 rtreeCheckAppendMsg(pCheck
, "Rtree depth out of range (%d)", iDepth
);
4007 sqlite3_free(aNode
);
4011 nCell
= readInt16(&aNode
[2]);
4012 if( (4 + nCell
*(8 + pCheck
->nDim
*2*4))>nNode
){
4013 rtreeCheckAppendMsg(pCheck
,
4014 "Node %lld is too small for cell count of %d (%d bytes)",
4018 for(i
=0; i
<nCell
; i
++){
4019 u8
*pCell
= &aNode
[4 + i
*(8 + pCheck
->nDim
*2*4)];
4020 i64 iVal
= readInt64(pCell
);
4021 rtreeCheckCellCoord(pCheck
, iNode
, i
, &pCell
[8], aParent
);
4024 rtreeCheckMapping(pCheck
, 0, iVal
, iNode
);
4025 rtreeCheckNode(pCheck
, iDepth
-1, &pCell
[8], iVal
);
4028 rtreeCheckMapping(pCheck
, 1, iVal
, iNode
);
4034 sqlite3_free(aNode
);
4039 ** The second argument to this function must be either "_rowid" or
4040 ** "_parent". This function checks that the number of entries in the
4041 ** %_rowid or %_parent table is exactly nExpect. If not, it adds
4042 ** an error message to the report in the RtreeCheck object indicated
4043 ** by the first argument.
4045 static void rtreeCheckCount(RtreeCheck
*pCheck
, const char *zTbl
, i64 nExpect
){
4046 if( pCheck
->rc
==SQLITE_OK
){
4047 sqlite3_stmt
*pCount
;
4048 pCount
= rtreeCheckPrepare(pCheck
, "SELECT count(*) FROM %Q.'%q%s'",
4049 pCheck
->zDb
, pCheck
->zTab
, zTbl
4052 if( sqlite3_step(pCount
)==SQLITE_ROW
){
4053 i64 nActual
= sqlite3_column_int64(pCount
, 0);
4054 if( nActual
!=nExpect
){
4055 rtreeCheckAppendMsg(pCheck
, "Wrong number of entries in %%%s table"
4056 " - expected %lld, actual %lld" , zTbl
, nExpect
, nActual
4060 pCheck
->rc
= sqlite3_finalize(pCount
);
4066 ** This function does the bulk of the work for the rtree integrity-check.
4067 ** It is called by rtreecheck(), which is the SQL function implementation.
4069 static int rtreeCheckTable(
4070 sqlite3
*db
, /* Database handle to access db through */
4071 const char *zDb
, /* Name of db ("main", "temp" etc.) */
4072 const char *zTab
, /* Name of rtree table to check */
4073 char **pzReport
/* OUT: sqlite3_malloc'd report text */
4075 RtreeCheck check
; /* Common context for various routines */
4076 sqlite3_stmt
*pStmt
= 0; /* Used to find column count of rtree table */
4077 int bEnd
= 0; /* True if transaction should be closed */
4078 int nAux
= 0; /* Number of extra columns. */
4080 /* Initialize the context object */
4081 memset(&check
, 0, sizeof(check
));
4086 /* If there is not already an open transaction, open one now. This is
4087 ** to ensure that the queries run as part of this integrity-check operate
4088 ** on a consistent snapshot. */
4089 if( sqlite3_get_autocommit(db
) ){
4090 check
.rc
= sqlite3_exec(db
, "BEGIN", 0, 0, 0);
4094 /* Find the number of auxiliary columns */
4095 if( check
.rc
==SQLITE_OK
){
4096 pStmt
= rtreeCheckPrepare(&check
, "SELECT * FROM %Q.'%q_rowid'", zDb
, zTab
);
4098 nAux
= sqlite3_column_count(pStmt
) - 2;
4099 sqlite3_finalize(pStmt
);
4101 check
.rc
= SQLITE_OK
;
4104 /* Find number of dimensions in the rtree table. */
4105 pStmt
= rtreeCheckPrepare(&check
, "SELECT * FROM %Q.%Q", zDb
, zTab
);
4108 check
.nDim
= (sqlite3_column_count(pStmt
) - 1 - nAux
) / 2;
4110 rtreeCheckAppendMsg(&check
, "Schema corrupt or not an rtree");
4111 }else if( SQLITE_ROW
==sqlite3_step(pStmt
) ){
4112 check
.bInt
= (sqlite3_column_type(pStmt
, 1)==SQLITE_INTEGER
);
4114 rc
= sqlite3_finalize(pStmt
);
4115 if( rc
!=SQLITE_CORRUPT
) check
.rc
= rc
;
4118 /* Do the actual integrity-check */
4119 if( check
.nDim
>=1 ){
4120 if( check
.rc
==SQLITE_OK
){
4121 rtreeCheckNode(&check
, 0, 0, 1);
4123 rtreeCheckCount(&check
, "_rowid", check
.nLeaf
);
4124 rtreeCheckCount(&check
, "_parent", check
.nNonLeaf
);
4127 /* Finalize SQL statements used by the integrity-check */
4128 sqlite3_finalize(check
.pGetNode
);
4129 sqlite3_finalize(check
.aCheckMapping
[0]);
4130 sqlite3_finalize(check
.aCheckMapping
[1]);
4132 /* If one was opened, close the transaction */
4134 int rc
= sqlite3_exec(db
, "END", 0, 0, 0);
4135 if( check
.rc
==SQLITE_OK
) check
.rc
= rc
;
4137 *pzReport
= check
.zReport
;
4144 ** rtreecheck(<rtree-table>);
4145 ** rtreecheck(<database>, <rtree-table>);
4147 ** Invoking this SQL function runs an integrity-check on the named rtree
4148 ** table. The integrity-check verifies the following:
4150 ** 1. For each cell in the r-tree structure (%_node table), that:
4152 ** a) for each dimension, (coord1 <= coord2).
4154 ** b) unless the cell is on the root node, that the cell is bounded
4155 ** by the parent cell on the parent node.
4157 ** c) for leaf nodes, that there is an entry in the %_rowid
4158 ** table corresponding to the cell's rowid value that
4159 ** points to the correct node.
4161 ** d) for cells on non-leaf nodes, that there is an entry in the
4162 ** %_parent table mapping from the cell's child node to the
4163 ** node that it resides on.
4165 ** 2. That there are the same number of entries in the %_rowid table
4166 ** as there are leaf cells in the r-tree structure, and that there
4167 ** is a leaf cell that corresponds to each entry in the %_rowid table.
4169 ** 3. That there are the same number of entries in the %_parent table
4170 ** as there are non-leaf cells in the r-tree structure, and that
4171 ** there is a non-leaf cell that corresponds to each entry in the
4174 static void rtreecheck(
4175 sqlite3_context
*ctx
,
4177 sqlite3_value
**apArg
4179 if( nArg
!=1 && nArg
!=2 ){
4180 sqlite3_result_error(ctx
,
4181 "wrong number of arguments to function rtreecheck()", -1
4186 const char *zDb
= (const char*)sqlite3_value_text(apArg
[0]);
4192 zTab
= (const char*)sqlite3_value_text(apArg
[1]);
4194 rc
= rtreeCheckTable(sqlite3_context_db_handle(ctx
), zDb
, zTab
, &zReport
);
4195 if( rc
==SQLITE_OK
){
4196 sqlite3_result_text(ctx
, zReport
? zReport
: "ok", -1, SQLITE_TRANSIENT
);
4198 sqlite3_result_error_code(ctx
, rc
);
4200 sqlite3_free(zReport
);
4206 ** Register the r-tree module with database handle db. This creates the
4207 ** virtual table module "rtree" and the debugging/analysis scalar
4208 ** function "rtreenode".
4210 int sqlite3RtreeInit(sqlite3
*db
){
4211 const int utf8
= SQLITE_UTF8
;
4214 rc
= sqlite3_create_function(db
, "rtreenode", 2, utf8
, 0, rtreenode
, 0, 0);
4215 if( rc
==SQLITE_OK
){
4216 rc
= sqlite3_create_function(db
, "rtreedepth", 1, utf8
, 0,rtreedepth
, 0, 0);
4218 if( rc
==SQLITE_OK
){
4219 rc
= sqlite3_create_function(db
, "rtreecheck", -1, utf8
, 0,rtreecheck
, 0,0);
4221 if( rc
==SQLITE_OK
){
4222 #ifdef SQLITE_RTREE_INT_ONLY
4223 void *c
= (void *)RTREE_COORD_INT32
;
4225 void *c
= (void *)RTREE_COORD_REAL32
;
4227 rc
= sqlite3_create_module_v2(db
, "rtree", &rtreeModule
, c
, 0);
4229 if( rc
==SQLITE_OK
){
4230 void *c
= (void *)RTREE_COORD_INT32
;
4231 rc
= sqlite3_create_module_v2(db
, "rtree_i32", &rtreeModule
, c
, 0);
4238 ** This routine deletes the RtreeGeomCallback object that was attached
4239 ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
4240 ** or sqlite3_rtree_query_callback(). In other words, this routine is the
4241 ** destructor for an RtreeGeomCallback objecct. This routine is called when
4242 ** the corresponding SQL function is deleted.
4244 static void rtreeFreeCallback(void *p
){
4245 RtreeGeomCallback
*pInfo
= (RtreeGeomCallback
*)p
;
4246 if( pInfo
->xDestructor
) pInfo
->xDestructor(pInfo
->pContext
);
4251 ** This routine frees the BLOB that is returned by geomCallback().
4253 static void rtreeMatchArgFree(void *pArg
){
4255 RtreeMatchArg
*p
= (RtreeMatchArg
*)pArg
;
4256 for(i
=0; i
<p
->nParam
; i
++){
4257 sqlite3_value_free(p
->apSqlParam
[i
]);
4263 ** Each call to sqlite3_rtree_geometry_callback() or
4264 ** sqlite3_rtree_query_callback() creates an ordinary SQLite
4265 ** scalar function that is implemented by this routine.
4267 ** All this function does is construct an RtreeMatchArg object that
4268 ** contains the geometry-checking callback routines and a list of
4269 ** parameters to this function, then return that RtreeMatchArg object
4272 ** The R-Tree MATCH operator will read the returned BLOB, deserialize
4273 ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
4274 ** out which elements of the R-Tree should be returned by the query.
4276 static void geomCallback(sqlite3_context
*ctx
, int nArg
, sqlite3_value
**aArg
){
4277 RtreeGeomCallback
*pGeomCtx
= (RtreeGeomCallback
*)sqlite3_user_data(ctx
);
4278 RtreeMatchArg
*pBlob
;
4282 nBlob
= sizeof(RtreeMatchArg
) + (nArg
-1)*sizeof(RtreeDValue
)
4283 + nArg
*sizeof(sqlite3_value
*);
4284 pBlob
= (RtreeMatchArg
*)sqlite3_malloc(nBlob
);
4286 sqlite3_result_error_nomem(ctx
);
4289 pBlob
->iSize
= nBlob
;
4290 pBlob
->cb
= pGeomCtx
[0];
4291 pBlob
->apSqlParam
= (sqlite3_value
**)&pBlob
->aParam
[nArg
];
4292 pBlob
->nParam
= nArg
;
4293 for(i
=0; i
<nArg
; i
++){
4294 pBlob
->apSqlParam
[i
] = sqlite3_value_dup(aArg
[i
]);
4295 if( pBlob
->apSqlParam
[i
]==0 ) memErr
= 1;
4296 #ifdef SQLITE_RTREE_INT_ONLY
4297 pBlob
->aParam
[i
] = sqlite3_value_int64(aArg
[i
]);
4299 pBlob
->aParam
[i
] = sqlite3_value_double(aArg
[i
]);
4303 sqlite3_result_error_nomem(ctx
);
4304 rtreeMatchArgFree(pBlob
);
4306 sqlite3_result_pointer(ctx
, pBlob
, "RtreeMatchArg", rtreeMatchArgFree
);
4312 ** Register a new geometry function for use with the r-tree MATCH operator.
4314 int sqlite3_rtree_geometry_callback(
4315 sqlite3
*db
, /* Register SQL function on this connection */
4316 const char *zGeom
, /* Name of the new SQL function */
4317 int (*xGeom
)(sqlite3_rtree_geometry
*,int,RtreeDValue
*,int*), /* Callback */
4318 void *pContext
/* Extra data associated with the callback */
4320 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4322 /* Allocate and populate the context object. */
4323 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4324 if( !pGeomCtx
) return SQLITE_NOMEM
;
4325 pGeomCtx
->xGeom
= xGeom
;
4326 pGeomCtx
->xQueryFunc
= 0;
4327 pGeomCtx
->xDestructor
= 0;
4328 pGeomCtx
->pContext
= pContext
;
4329 return sqlite3_create_function_v2(db
, zGeom
, -1, SQLITE_ANY
,
4330 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4335 ** Register a new 2nd-generation geometry function for use with the
4336 ** r-tree MATCH operator.
4338 int sqlite3_rtree_query_callback(
4339 sqlite3
*db
, /* Register SQL function on this connection */
4340 const char *zQueryFunc
, /* Name of new SQL function */
4341 int (*xQueryFunc
)(sqlite3_rtree_query_info
*), /* Callback */
4342 void *pContext
, /* Extra data passed into the callback */
4343 void (*xDestructor
)(void*) /* Destructor for the extra data */
4345 RtreeGeomCallback
*pGeomCtx
; /* Context object for new user-function */
4347 /* Allocate and populate the context object. */
4348 pGeomCtx
= (RtreeGeomCallback
*)sqlite3_malloc(sizeof(RtreeGeomCallback
));
4349 if( !pGeomCtx
) return SQLITE_NOMEM
;
4350 pGeomCtx
->xGeom
= 0;
4351 pGeomCtx
->xQueryFunc
= xQueryFunc
;
4352 pGeomCtx
->xDestructor
= xDestructor
;
4353 pGeomCtx
->pContext
= pContext
;
4354 return sqlite3_create_function_v2(db
, zQueryFunc
, -1, SQLITE_ANY
,
4355 (void *)pGeomCtx
, geomCallback
, 0, 0, rtreeFreeCallback
4361 __declspec(dllexport
)
4363 int sqlite3_rtree_init(
4366 const sqlite3_api_routines
*pApi
4368 SQLITE_EXTENSION_INIT2(pApi
)
4369 return sqlite3RtreeInit(db
);