Debian Codegraph @

ext/rtree/rtree.c

raw
1 /*
2 ** 2001 September 15
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
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.
10 **
11 *************************************************************************
12 ** This file contains code for implementations of the r-tree and r*-tree
13 ** algorithms packaged as an SQLite virtual table module.
14 */
15
16 /*
17 ** Database Format of R-Tree Tables
18 ** --------------------------------
19 **
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
23 ** table.
24 **
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, ...)
28 **
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.
36 **
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:
41 **
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.
45 **
46 ** 2. The next 2 bytes contain the number of entries currently
47 ** stored in the node.
48 **
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
53 ** child page.
54 */
55
56 #if !defined(SQLITE_CORE) \
57 || (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE))
58
59 #ifndef SQLITE_CORE
60 #include "sqlite3ext.h"
61 SQLITE_EXTENSION_INIT1
62 #else
63 #include "sqlite3.h"
64 #endif
65 sqlite3_int64 sqlite3GetToken(const unsigned char*,int*); /* In SQLite core */
66
67 #include <stddef.h>
68
69 /*
70 ** If building separately, we will need some setup that is normally
71 ** found in sqliteInt.h
72 */
73 #if !defined(SQLITE_AMALGAMATION)
74 #include "sqlite3rtree.h"
75 typedef sqlite3_int64 i64;
76 typedef sqlite3_uint64 u64;
77 typedef unsigned char u8;
78 typedef unsigned short u16;
79 typedef unsigned int u32;
80 #if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
81 # define NDEBUG 1
82 #endif
83 #if defined(NDEBUG) && defined(SQLITE_DEBUG)
84 # undef NDEBUG
85 #endif
86 #if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST)
87 # define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1
88 #endif
89 #if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
90 # define ALWAYS(X) (1)
91 # define NEVER(X) (0)
92 #elif !defined(NDEBUG)
93 # define ALWAYS(X) ((X)?1:(assert(0),0))
94 # define NEVER(X) ((X)?(assert(0),1):0)
95 #else
96 # define ALWAYS(X) (X)
97 # define NEVER(X) (X)
98 #endif
99 #ifndef offsetof
100 # define offsetof(ST,M) ((size_t)((char*)&((ST*)0)->M - (char*)0))
101 #endif
102 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)
103 # define FLEXARRAY
104 #else
105 # define FLEXARRAY 1
106 #endif
107 #endif /* !defined(SQLITE_AMALGAMATION) */
108
109 /* Macro to check for 4-byte alignment. Only used inside of assert() */
110 #ifdef SQLITE_DEBUG
111 # define FOUR_BYTE_ALIGNED(X) ((((char*)(X) - (char*)0) & 3)==0)
112 #endif
113
114 #include <string.h>
115 #include <stdio.h>
116 #include <assert.h>
117 #include <stdlib.h>
118
119 /* The following macro is used to suppress compiler warnings.
120 */
121 #ifndef UNUSED_PARAMETER
122 # define UNUSED_PARAMETER(x) (void)(x)
123 #endif
124
125 typedef struct Rtree Rtree;
126 typedef struct RtreeCursor RtreeCursor;
127 typedef struct RtreeNode RtreeNode;
128 typedef struct RtreeCell RtreeCell;
129 typedef struct RtreeConstraint RtreeConstraint;
130 typedef struct RtreeMatchArg RtreeMatchArg;
131 typedef struct RtreeGeomCallback RtreeGeomCallback;
132 typedef union RtreeCoord RtreeCoord;
133 typedef struct RtreeSearchPoint RtreeSearchPoint;
134
135 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
136 #define RTREE_MAX_DIMENSIONS 5
137
138 /* Maximum number of auxiliary columns */
139 #define RTREE_MAX_AUX_COLUMN 100
140
141 /* Size of hash table Rtree.aHash. This hash table is not expected to
142 ** ever contain very many entries, so a fixed number of buckets is
143 ** used.
144 */
145 #define HASHSIZE 97
146
147 /* The xBestIndex method of this virtual table requires an estimate of
148 ** the number of rows in the virtual table to calculate the costs of
149 ** various strategies. If possible, this estimate is loaded from the
150 ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
151 ** Otherwise, if no sqlite_stat1 entry is available, use
152 ** RTREE_DEFAULT_ROWEST.
153 */
154 #define RTREE_DEFAULT_ROWEST 1048576
155 #define RTREE_MIN_ROWEST 100
156
157 /*
158 ** An rtree virtual-table object.
159 */
160 struct Rtree {
161 sqlite3_vtab base; /* Base class. Must be first */
162 sqlite3 *db; /* Host database connection */
163 int iNodeSize; /* Size in bytes of each node in the node table */
164 u8 nDim; /* Number of dimensions */
165 u8 nDim2; /* Twice the number of dimensions */
166 u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
167 u8 nBytesPerCell; /* Bytes consumed per cell */
168 u8 inWrTrans; /* True if inside write transaction */
169 u16 nAux; /* # of auxiliary columns in %_rowid */
170 #ifdef SQLITE_ENABLE_GEOPOLY
171 u8 nAuxNotNull; /* Number of initial not-null aux columns */
172 #endif
173 #ifdef SQLITE_DEBUG
174 u8 bCorrupt; /* Shadow table corruption detected */
175 #endif
176 int iDepth; /* Current depth of the r-tree structure */
177 char *zDb; /* Name of database containing r-tree table */
178 char *zName; /* Name of r-tree table */
179 char *zNodeName; /* Name of the %_node table */
180 u32 nBusy; /* Current number of users of this structure */
181 i64 nRowEst; /* Estimated number of rows in this table */
182 u32 nCursor; /* Number of open cursors */
183 u32 nNodeRef; /* Number RtreeNodes with positive nRef */
184 char *zReadAuxSql; /* SQL for statement to read aux data */
185
186 /* List of nodes removed during a CondenseTree operation. List is
187 ** linked together via the pointer normally used for hash chains -
188 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
189 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
190 */
191 RtreeNode *pDeleted;
192
193 /* Blob I/O on xxx_node */
194 sqlite3_blob *pNodeBlob;
195
196 /* Statements to read/write/delete a record from xxx_node */
197 sqlite3_stmt *pWriteNode;
198 sqlite3_stmt *pDeleteNode;
199
200 /* Statements to read/write/delete a record from xxx_rowid */
201 sqlite3_stmt *pReadRowid;
202 sqlite3_stmt *pWriteRowid;
203 sqlite3_stmt *pDeleteRowid;
204
205 /* Statements to read/write/delete a record from xxx_parent */
206 sqlite3_stmt *pReadParent;
207 sqlite3_stmt *pWriteParent;
208 sqlite3_stmt *pDeleteParent;
209
210 /* Statement for writing to the "aux:" fields, if there are any */
211 sqlite3_stmt *pWriteAux;
212
213 RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
214 };
215
216 /* Possible values for Rtree.eCoordType: */
217 #define RTREE_COORD_REAL32 0
218 #define RTREE_COORD_INT32 1
219
220 /*
221 ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
222 ** only deal with integer coordinates. No floating point operations
223 ** will be done.
224 */
225 #ifdef SQLITE_RTREE_INT_ONLY
226 typedef sqlite3_int64 RtreeDValue; /* High accuracy coordinate */
227 typedef int RtreeValue; /* Low accuracy coordinate */
228 # define RTREE_ZERO 0
229 #else
230 typedef double RtreeDValue; /* High accuracy coordinate */
231 typedef float RtreeValue; /* Low accuracy coordinate */
232 # define RTREE_ZERO 0.0
233 #endif
234
235 /*
236 ** Set the Rtree.bCorrupt flag
237 */
238 #ifdef SQLITE_DEBUG
239 # define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1)
240 #else
241 # define RTREE_IS_CORRUPT(X)
242 #endif
243
244 /*
245 ** When doing a search of an r-tree, instances of the following structure
246 ** record intermediate results from the tree walk.
247 **
248 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
249 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
250 ** the id is of the parent node and the cell that RtreeSearchPoint
251 ** represents is the iCell-th entry in the parent node.
252 */
253 struct RtreeSearchPoint {
254 RtreeDValue rScore; /* The score for this node. Smallest goes first. */
255 sqlite3_int64 id; /* Node ID */
256 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
257 u8 eWithin; /* PARTLY_WITHIN or FULLY_WITHIN */
258 u8 iCell; /* Cell index within the node */
259 };
260
261 /*
262 ** The minimum number of cells allowed for a node is a third of the
263 ** maximum. In Gutman's notation:
264 **
265 ** m = M/3
266 **
267 ** If an R*-tree "Reinsert" operation is required, the same number of
268 ** cells are removed from the overfull node and reinserted into the tree.
269 */
270 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
271 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
272 #define RTREE_MAXCELLS 51
273
274 /*
275 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
276 ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
277 ** Therefore all non-root nodes must contain at least 3 entries. Since
278 ** 3^40 is greater than 2^64, an r-tree structure always has a depth of
279 ** 40 or less.
280 */
281 #define RTREE_MAX_DEPTH 40
282
283
284 /*
285 ** Number of entries in the cursor RtreeNode cache. The first entry is
286 ** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining
287 ** entries cache the RtreeNode for the first elements of the priority queue.
288 */
289 #define RTREE_CACHE_SZ 5
290
291 /*
292 ** An rtree cursor object.
293 */
294 struct RtreeCursor {
295 sqlite3_vtab_cursor base; /* Base class. Must be first */
296 u8 atEOF; /* True if at end of search */
297 u8 bPoint; /* True if sPoint is valid */
298 u8 bAuxValid; /* True if pReadAux is valid */
299 int iStrategy; /* Copy of idxNum search parameter */
300 int nConstraint; /* Number of entries in aConstraint */
301 RtreeConstraint *aConstraint; /* Search constraints. */
302 int nPointAlloc; /* Number of slots allocated for aPoint[] */
303 int nPoint; /* Number of slots used in aPoint[] */
304 int mxLevel; /* iLevel value for root of the tree */
305 RtreeSearchPoint *aPoint; /* Priority queue for search points */
306 sqlite3_stmt *pReadAux; /* Statement to read aux-data */
307 RtreeSearchPoint sPoint; /* Cached next search point */
308 RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
309 u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */
310 };
311
312 /* Return the Rtree of a RtreeCursor */
313 #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab))
314
315 /*
316 ** A coordinate can be either a floating point number or a integer. All
317 ** coordinates within a single R-Tree are always of the same time.
318 */
319 union RtreeCoord {
320 RtreeValue f; /* Floating point value */
321 int i; /* Integer value */
322 u32 u; /* Unsigned for byte-order conversions */
323 };
324
325 /*
326 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
327 ** formatted as a RtreeDValue (double or int64). This macro assumes that local
328 ** variable pRtree points to the Rtree structure associated with the
329 ** RtreeCoord.
330 */
331 #ifdef SQLITE_RTREE_INT_ONLY
332 # define DCOORD(coord) ((RtreeDValue)coord.i)
333 #else
334 # define DCOORD(coord) ( \
335 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
336 ((double)coord.f) : \
337 ((double)coord.i) \
338 )
339 #endif
340
341 /*
342 ** A search constraint.
343 */
344 struct RtreeConstraint {
345 int iCoord; /* Index of constrained coordinate */
346 int op; /* Constraining operation */
347 union {
348 RtreeDValue rValue; /* Constraint value. */
349 int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
350 int (*xQueryFunc)(sqlite3_rtree_query_info*);
351 } u;
352 sqlite3_rtree_query_info *pInfo; /* xGeom and xQueryFunc argument */
353 };
354
355 /* Possible values for RtreeConstraint.op */
356 #define RTREE_EQ 0x41 /* A */
357 #define RTREE_LE 0x42 /* B */
358 #define RTREE_LT 0x43 /* C */
359 #define RTREE_GE 0x44 /* D */
360 #define RTREE_GT 0x45 /* E */
361 #define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */
362 #define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */
363
364 /* Special operators available only on cursors. Needs to be consecutive
365 ** with the normal values above, but must be less than RTREE_MATCH. These
366 ** are used in the cursor for contraints such as x=NULL (RTREE_FALSE) or
367 ** x<'xyz' (RTREE_TRUE) */
368 #define RTREE_TRUE 0x3f /* ? */
369 #define RTREE_FALSE 0x40 /* @ */
370
371 /*
372 ** An rtree structure node.
373 */
374 struct RtreeNode {
375 RtreeNode *pParent; /* Parent node */
376 i64 iNode; /* The node number */
377 int nRef; /* Number of references to this node */
378 int isDirty; /* True if the node needs to be written to disk */
379 u8 *zData; /* Content of the node, as should be on disk */
380 RtreeNode *pNext; /* Next node in this hash collision chain */
381 };
382
383 /* Return the number of cells in a node */
384 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
385
386 /*
387 ** A single cell from a node, deserialized
388 */
389 struct RtreeCell {
390 i64 iRowid; /* Node or entry ID */
391 RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */
392 };
393
394
395 /*
396 ** This object becomes the sqlite3_user_data() for the SQL functions
397 ** that are created by sqlite3_rtree_geometry_callback() and
398 ** sqlite3_rtree_query_callback() and which appear on the right of MATCH
399 ** operators in order to constrain a search.
400 **
401 ** xGeom and xQueryFunc are the callback functions. Exactly one of
402 ** xGeom and xQueryFunc fields is non-NULL, depending on whether the
403 ** SQL function was created using sqlite3_rtree_geometry_callback() or
404 ** sqlite3_rtree_query_callback().
405 **
406 ** This object is deleted automatically by the destructor mechanism in
407 ** sqlite3_create_function_v2().
408 */
409 struct RtreeGeomCallback {
410 int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
411 int (*xQueryFunc)(sqlite3_rtree_query_info*);
412 void (*xDestructor)(void*);
413 void *pContext;
414 };
415
416 /*
417 ** An instance of this structure (in the form of a BLOB) is returned by
418 ** the SQL functions that sqlite3_rtree_geometry_callback() and
419 ** sqlite3_rtree_query_callback() create, and is read as the right-hand
420 ** operand to the MATCH operator of an R-Tree.
421 */
422 struct RtreeMatchArg {
423 u32 iSize; /* Size of this object */
424 RtreeGeomCallback cb; /* Info about the callback functions */
425 int nParam; /* Number of parameters to the SQL function */
426 sqlite3_value **apSqlParam; /* Original SQL parameter values */
427 RtreeDValue aParam[FLEXARRAY]; /* Values for parameters to the SQL function */
428 };
429
430 /* Size of an RtreeMatchArg object with N parameters */
431 #define SZ_RTREEMATCHARG(N) \
432 (offsetof(RtreeMatchArg,aParam)+(N)*sizeof(RtreeDValue))
433
434 #ifndef MAX
435 # define MAX(x,y) ((x) < (y) ? (y) : (x))
436 #endif
437 #ifndef MIN
438 # define MIN(x,y) ((x) > (y) ? (y) : (x))
439 #endif
440
441 /* What version of GCC is being used. 0 means GCC is not being used .
442 ** Note that the GCC_VERSION macro will also be set correctly when using
443 ** clang, since clang works hard to be gcc compatible. So the gcc
444 ** optimizations will also work when compiling with clang.
445 */
446 #ifndef GCC_VERSION
447 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
448 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
449 #else
450 # define GCC_VERSION 0
451 #endif
452 #endif
453
454 /* The testcase() macro should already be defined in the amalgamation. If
455 ** it is not, make it a no-op.
456 */
457 #ifndef SQLITE_AMALGAMATION
458 # if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_DEBUG)
459 unsigned int sqlite3RtreeTestcase = 0;
460 # define testcase(X) if( X ){ sqlite3RtreeTestcase += __LINE__; }
461 # else
462 # define testcase(X)
463 # endif
464 #endif
465
466 /*
467 ** Make sure that the compiler intrinsics we desire are enabled when
468 ** compiling with an appropriate version of MSVC unless prevented by
469 ** the SQLITE_DISABLE_INTRINSIC define.
470 */
471 #if !defined(SQLITE_DISABLE_INTRINSIC)
472 # if defined(_MSC_VER) && _MSC_VER>=1400
473 # if !defined(_WIN32_WCE)
474 # include <intrin.h>
475 # pragma intrinsic(_byteswap_ulong)
476 # pragma intrinsic(_byteswap_uint64)
477 # else
478 # include <cmnintrin.h>
479 # endif
480 # endif
481 #endif
482
483 /*
484 ** Macros to determine whether the machine is big or little endian,
485 ** and whether or not that determination is run-time or compile-time.
486 **
487 ** For best performance, an attempt is made to guess at the byte-order
488 ** using C-preprocessor macros. If that is unsuccessful, or if
489 ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined
490 ** at run-time.
491 */
492 #ifndef SQLITE_BYTEORDER /* Replicate changes at tag-20230904a */
493 # if defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_BIG_ENDIAN__
494 # define SQLITE_BYTEORDER 4321
495 # elif defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_LITTLE_ENDIAN__
496 # define SQLITE_BYTEORDER 1234
497 # elif defined(__BIG_ENDIAN__) && __BIG_ENDIAN__==1
498 # define SQLITE_BYTEORDER 4321
499 # elif defined(i386) || defined(__i386__) || defined(_M_IX86) || \
500 defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \
501 defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \
502 defined(__ARMEL__) || defined(__AARCH64EL__) || defined(_M_ARM64)
503 # define SQLITE_BYTEORDER 1234
504 # elif defined(sparc) || defined(__ARMEB__) || defined(__AARCH64EB__)
505 # define SQLITE_BYTEORDER 4321
506 # else
507 # define SQLITE_BYTEORDER 0
508 # endif
509 #endif
510
511
512 /* What version of MSVC is being used. 0 means MSVC is not being used */
513 #ifndef MSVC_VERSION
514 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
515 # define MSVC_VERSION _MSC_VER
516 #else
517 # define MSVC_VERSION 0
518 #endif
519 #endif
520
521 /*
522 ** Functions to deserialize a 16 bit integer, 32 bit real number and
523 ** 64 bit integer. The deserialized value is returned.
524 */
525 static int readInt16(u8 *p){
526 return (p[0]<<8) + p[1];
527 }
528 static void readCoord(u8 *p, RtreeCoord *pCoord){
529 assert( FOUR_BYTE_ALIGNED(p) );
530 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
531 pCoord->u = _byteswap_ulong(*(u32*)p);
532 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
533 pCoord->u = __builtin_bswap32(*(u32*)p);
534 #elif SQLITE_BYTEORDER==4321
535 pCoord->u = *(u32*)p;
536 #else
537 pCoord->u = (
538 (((u32)p[0]) << 24) +
539 (((u32)p[1]) << 16) +
540 (((u32)p[2]) << 8) +
541 (((u32)p[3]) << 0)
542 );
543 #endif
544 }
545 static i64 readInt64(u8 *p){
546 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
547 u64 x;
548 memcpy(&x, p, 8);
549 return (i64)_byteswap_uint64(x);
550 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
551 u64 x;
552 memcpy(&x, p, 8);
553 return (i64)__builtin_bswap64(x);
554 #elif SQLITE_BYTEORDER==4321
555 i64 x;
556 memcpy(&x, p, 8);
557 return x;
558 #else
559 return (i64)(
560 (((u64)p[0]) << 56) +
561 (((u64)p[1]) << 48) +
562 (((u64)p[2]) << 40) +
563 (((u64)p[3]) << 32) +
564 (((u64)p[4]) << 24) +
565 (((u64)p[5]) << 16) +
566 (((u64)p[6]) << 8) +
567 (((u64)p[7]) << 0)
568 );
569 #endif
570 }
571
572 /*
573 ** Functions to serialize a 16 bit integer, 32 bit real number and
574 ** 64 bit integer. The value returned is the number of bytes written
575 ** to the argument buffer (always 2, 4 and 8 respectively).
576 */
577 static void writeInt16(u8 *p, int i){
578 p[0] = (i>> 8)&0xFF;
579 p[1] = (i>> 0)&0xFF;
580 }
581 static int writeCoord(u8 *p, RtreeCoord *pCoord){
582 u32 i;
583 assert( FOUR_BYTE_ALIGNED(p) );
584 assert( sizeof(RtreeCoord)==4 );
585 assert( sizeof(u32)==4 );
586 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
587 i = __builtin_bswap32(pCoord->u);
588 memcpy(p, &i, 4);
589 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
590 i = _byteswap_ulong(pCoord->u);
591 memcpy(p, &i, 4);
592 #elif SQLITE_BYTEORDER==4321
593 i = pCoord->u;
594 memcpy(p, &i, 4);
595 #else
596 i = pCoord->u;
597 p[0] = (i>>24)&0xFF;
598 p[1] = (i>>16)&0xFF;
599 p[2] = (i>> 8)&0xFF;
600 p[3] = (i>> 0)&0xFF;
601 #endif
602 return 4;
603 }
604 static int writeInt64(u8 *p, i64 i){
605 #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
606 i = (i64)__builtin_bswap64((u64)i);
607 memcpy(p, &i, 8);
608 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
609 i = (i64)_byteswap_uint64((u64)i);
610 memcpy(p, &i, 8);
611 #elif SQLITE_BYTEORDER==4321
612 memcpy(p, &i, 8);
613 #else
614 p[0] = (i>>56)&0xFF;
615 p[1] = (i>>48)&0xFF;
616 p[2] = (i>>40)&0xFF;
617 p[3] = (i>>32)&0xFF;
618 p[4] = (i>>24)&0xFF;
619 p[5] = (i>>16)&0xFF;
620 p[6] = (i>> 8)&0xFF;
621 p[7] = (i>> 0)&0xFF;
622 #endif
623 return 8;
624 }
625
626 /*
627 ** Increment the reference count of node p.
628 */
629 static void nodeReference(RtreeNode *p){
630 if( p ){
631 assert( p->nRef>0 );
632 p->nRef++;
633 }
634 }
635
636 /*
637 ** Clear the content of node p (set all bytes to 0x00).
638 */
639 static void nodeZero(Rtree *pRtree, RtreeNode *p){
640 memset(&p->zData[2], 0, pRtree->iNodeSize-2);
641 p->isDirty = 1;
642 }
643
644 /*
645 ** Given a node number iNode, return the corresponding key to use
646 ** in the Rtree.aHash table.
647 */
648 static unsigned int nodeHash(i64 iNode){
649 return ((unsigned)iNode) % HASHSIZE;
650 }
651
652 /*
653 ** Search the node hash table for node iNode. If found, return a pointer
654 ** to it. Otherwise, return 0.
655 */
656 static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
657 RtreeNode *p;
658 for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
659 return p;
660 }
661
662 /*
663 ** Add node pNode to the node hash table.
664 */
665 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
666 int iHash;
667 assert( pNode->pNext==0 );
668 iHash = nodeHash(pNode->iNode);
669 pNode->pNext = pRtree->aHash[iHash];
670 pRtree->aHash[iHash] = pNode;
671 }
672
673 /*
674 ** Remove node pNode from the node hash table.
675 */
676 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
677 RtreeNode **pp;
678 if( pNode->iNode!=0 ){
679 pp = &pRtree->aHash[nodeHash(pNode->iNode)];
680 for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
681 *pp = pNode->pNext;
682 pNode->pNext = 0;
683 }
684 }
685
686 /*
687 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
688 ** indicating that node has not yet been assigned a node number. It is
689 ** assigned a node number when nodeWrite() is called to write the
690 ** node contents out to the database.
691 */
692 static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
693 RtreeNode *pNode;
694 pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode) + pRtree->iNodeSize);
695 if( pNode ){
696 memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
697 pNode->zData = (u8 *)&pNode[1];
698 pNode->nRef = 1;
699 pRtree->nNodeRef++;
700 pNode->pParent = pParent;
701 pNode->isDirty = 1;
702 nodeReference(pParent);
703 }
704 return pNode;
705 }
706
707 /*
708 ** Clear the Rtree.pNodeBlob object
709 */
710 static void nodeBlobReset(Rtree *pRtree){
711 sqlite3_blob *pBlob = pRtree->pNodeBlob;
712 pRtree->pNodeBlob = 0;
713 sqlite3_blob_close(pBlob);
714 }
715
716 /*
717 ** Obtain a reference to an r-tree node.
718 */
719 static int nodeAcquire(
720 Rtree *pRtree, /* R-tree structure */
721 i64 iNode, /* Node number to load */
722 RtreeNode *pParent, /* Either the parent node or NULL */
723 RtreeNode **ppNode /* OUT: Acquired node */
724 ){
725 int rc = SQLITE_OK;
726 RtreeNode *pNode = 0;
727
728 /* Check if the requested node is already in the hash table. If so,
729 ** increase its reference count and return it.
730 */
731 if( (pNode = nodeHashLookup(pRtree, iNode))!=0 ){
732 if( pParent && ALWAYS(pParent!=pNode->pParent) ){
733 RTREE_IS_CORRUPT(pRtree);
734 return SQLITE_CORRUPT_VTAB;
735 }
736 pNode->nRef++;
737 *ppNode = pNode;
738 return SQLITE_OK;
739 }
740
741 if( pRtree->pNodeBlob ){
742 sqlite3_blob *pBlob = pRtree->pNodeBlob;
743 pRtree->pNodeBlob = 0;
744 rc = sqlite3_blob_reopen(pBlob, iNode);
745 pRtree->pNodeBlob = pBlob;
746 if( rc ){
747 nodeBlobReset(pRtree);
748 if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM;
749 }
750 }
751 if( pRtree->pNodeBlob==0 ){
752 rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, pRtree->zNodeName,
753 "data", iNode, 0,
754 &pRtree->pNodeBlob);
755 }
756 if( rc ){
757 *ppNode = 0;
758 /* If unable to open an sqlite3_blob on the desired row, that can only
759 ** be because the shadow tables hold erroneous data. */
760 if( rc==SQLITE_ERROR ){
761 rc = SQLITE_CORRUPT_VTAB;
762 RTREE_IS_CORRUPT(pRtree);
763 }
764 }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){
765 pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode)+pRtree->iNodeSize);
766 if( !pNode ){
767 rc = SQLITE_NOMEM;
768 }else{
769 pNode->pParent = pParent;
770 pNode->zData = (u8 *)&pNode[1];
771 pNode->nRef = 1;
772 pRtree->nNodeRef++;
773 pNode->iNode = iNode;
774 pNode->isDirty = 0;
775 pNode->pNext = 0;
776 rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData,
777 pRtree->iNodeSize, 0);
778 }
779 }
780
781 /* If the root node was just loaded, set pRtree->iDepth to the height
782 ** of the r-tree structure. A height of zero means all data is stored on
783 ** the root node. A height of one means the children of the root node
784 ** are the leaves, and so on. If the depth as specified on the root node
785 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
786 */
787 if( rc==SQLITE_OK && pNode && iNode==1 ){
788 pRtree->iDepth = readInt16(pNode->zData);
789 if( pRtree->iDepth>RTREE_MAX_DEPTH ){
790 rc = SQLITE_CORRUPT_VTAB;
791 RTREE_IS_CORRUPT(pRtree);
792 }
793 }
794
795 /* If no error has occurred so far, check if the "number of entries"
796 ** field on the node is too large. If so, set the return code to
797 ** SQLITE_CORRUPT_VTAB.
798 */
799 if( pNode && rc==SQLITE_OK ){
800 if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
801 rc = SQLITE_CORRUPT_VTAB;
802 RTREE_IS_CORRUPT(pRtree);
803 }
804 }
805
806 if( rc==SQLITE_OK ){
807 if( pNode!=0 ){
808 nodeReference(pParent);
809 nodeHashInsert(pRtree, pNode);
810 }else{
811 rc = SQLITE_CORRUPT_VTAB;
812 RTREE_IS_CORRUPT(pRtree);
813 }
814 *ppNode = pNode;
815 }else{
816 nodeBlobReset(pRtree);
817 if( pNode ){
818 pRtree->nNodeRef--;
819 sqlite3_free(pNode);
820 }
821 *ppNode = 0;
822 }
823
824 return rc;
825 }
826
827 /*
828 ** Overwrite cell iCell of node pNode with the contents of pCell.
829 */
830 static void nodeOverwriteCell(
831 Rtree *pRtree, /* The overall R-Tree */
832 RtreeNode *pNode, /* The node into which the cell is to be written */
833 RtreeCell *pCell, /* The cell to write */
834 int iCell /* Index into pNode into which pCell is written */
835 ){
836 int ii;
837 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
838 p += writeInt64(p, pCell->iRowid);
839 for(ii=0; ii<pRtree->nDim2; ii++){
840 p += writeCoord(p, &pCell->aCoord[ii]);
841 }
842 pNode->isDirty = 1;
843 }
844
845 /*
846 ** Remove the cell with index iCell from node pNode.
847 */
848 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
849 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
850 u8 *pSrc = &pDst[pRtree->nBytesPerCell];
851 int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
852 memmove(pDst, pSrc, nByte);
853 writeInt16(&pNode->zData[2], NCELL(pNode)-1);
854 pNode->isDirty = 1;
855 }
856
857 /*
858 ** Insert the contents of cell pCell into node pNode. If the insert
859 ** is successful, return SQLITE_OK.
860 **
861 ** If there is not enough free space in pNode, return SQLITE_FULL.
862 */
863 static int nodeInsertCell(
864 Rtree *pRtree, /* The overall R-Tree */
865 RtreeNode *pNode, /* Write new cell into this node */
866 RtreeCell *pCell /* The cell to be inserted */
867 ){
868 int nCell; /* Current number of cells in pNode */
869 int nMaxCell; /* Maximum number of cells for pNode */
870
871 nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
872 nCell = NCELL(pNode);
873
874 assert( nCell<=nMaxCell );
875 if( nCell<nMaxCell ){
876 nodeOverwriteCell(pRtree, pNode, pCell, nCell);
877 writeInt16(&pNode->zData[2], nCell+1);
878 pNode->isDirty = 1;
879 }
880
881 return (nCell==nMaxCell);
882 }
883
884 /*
885 ** If the node is dirty, write it out to the database.
886 */
887 static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){
888 int rc = SQLITE_OK;
889 if( pNode->isDirty ){
890 sqlite3_stmt *p = pRtree->pWriteNode;
891 if( pNode->iNode ){
892 sqlite3_bind_int64(p, 1, pNode->iNode);
893 }else{
894 sqlite3_bind_null(p, 1);
895 }
896 sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
897 sqlite3_step(p);
898 pNode->isDirty = 0;
899 rc = sqlite3_reset(p);
900 sqlite3_bind_null(p, 2);
901 if( pNode->iNode==0 && rc==SQLITE_OK ){
902 pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
903 nodeHashInsert(pRtree, pNode);
904 }
905 }
906 return rc;
907 }
908
909 /*
910 ** Release a reference to a node. If the node is dirty and the reference
911 ** count drops to zero, the node data is written to the database.
912 */
913 static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
914 int rc = SQLITE_OK;
915 if( pNode ){
916 assert( pNode->nRef>0 );
917 assert( pRtree->nNodeRef>0 );
918 pNode->nRef--;
919 if( pNode->nRef==0 ){
920 pRtree->nNodeRef--;
921 if( pNode->iNode==1 ){
922 pRtree->iDepth = -1;
923 }
924 if( pNode->pParent ){
925 rc = nodeRelease(pRtree, pNode->pParent);
926 }
927 if( rc==SQLITE_OK ){
928 rc = nodeWrite(pRtree, pNode);
929 }
930 nodeHashDelete(pRtree, pNode);
931 sqlite3_free(pNode);
932 }
933 }
934 return rc;
935 }
936
937 /*
938 ** Return the 64-bit integer value associated with cell iCell of
939 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
940 ** an internal node, then the 64-bit integer is a child page number.
941 */
942 static i64 nodeGetRowid(
943 Rtree *pRtree, /* The overall R-Tree */
944 RtreeNode *pNode, /* The node from which to extract the ID */
945 int iCell /* The cell index from which to extract the ID */
946 ){
947 assert( iCell<NCELL(pNode) );
948 return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
949 }
950
951 /*
952 ** Return coordinate iCoord from cell iCell in node pNode.
953 */
954 static void nodeGetCoord(
955 Rtree *pRtree, /* The overall R-Tree */
956 RtreeNode *pNode, /* The node from which to extract a coordinate */
957 int iCell, /* The index of the cell within the node */
958 int iCoord, /* Which coordinate to extract */
959 RtreeCoord *pCoord /* OUT: Space to write result to */
960 ){
961 assert( iCell<NCELL(pNode) );
962 readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
963 }
964
965 /*
966 ** Deserialize cell iCell of node pNode. Populate the structure pointed
967 ** to by pCell with the results.
968 */
969 static void nodeGetCell(
970 Rtree *pRtree, /* The overall R-Tree */
971 RtreeNode *pNode, /* The node containing the cell to be read */
972 int iCell, /* Index of the cell within the node */
973 RtreeCell *pCell /* OUT: Write the cell contents here */
974 ){
975 u8 *pData;
976 RtreeCoord *pCoord;
977 int ii = 0;
978 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
979 pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
980 pCoord = pCell->aCoord;
981 do{
982 readCoord(pData, &pCoord[ii]);
983 readCoord(pData+4, &pCoord[ii+1]);
984 pData += 8;
985 ii += 2;
986 }while( ii<pRtree->nDim2 );
987 }
988
989
990 /* Forward declaration for the function that does the work of
991 ** the virtual table module xCreate() and xConnect() methods.
992 */
993 static int rtreeInit(
994 sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int
995 );
996
997 /*
998 ** Rtree virtual table module xCreate method.
999 */
1000 static int rtreeCreate(
1001 sqlite3 *db,
1002 void *pAux,
1003 int argc, const char *const*argv,
1004 sqlite3_vtab **ppVtab,
1005 char **pzErr
1006 ){
1007 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1);
1008 }
1009
1010 /*
1011 ** Rtree virtual table module xConnect method.
1012 */
1013 static int rtreeConnect(
1014 sqlite3 *db,
1015 void *pAux,
1016 int argc, const char *const*argv,
1017 sqlite3_vtab **ppVtab,
1018 char **pzErr
1019 ){
1020 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0);
1021 }
1022
1023 /*
1024 ** Increment the r-tree reference count.
1025 */
1026 static void rtreeReference(Rtree *pRtree){
1027 pRtree->nBusy++;
1028 }
1029
1030 /*
1031 ** Decrement the r-tree reference count. When the reference count reaches
1032 ** zero the structure is deleted.
1033 */
1034 static void rtreeRelease(Rtree *pRtree){
1035 pRtree->nBusy--;
1036 if( pRtree->nBusy==0 ){
1037 pRtree->inWrTrans = 0;
1038 assert( pRtree->nCursor==0 );
1039 nodeBlobReset(pRtree);
1040 if( pRtree->nNodeRef ){
1041 int i;
1042 assert( pRtree->bCorrupt );
1043 for(i=0; i<HASHSIZE; i++){
1044 while( pRtree->aHash[i] ){
1045 RtreeNode *pNext = pRtree->aHash[i]->pNext;
1046 sqlite3_free(pRtree->aHash[i]);
1047 pRtree->aHash[i] = pNext;
1048 }
1049 }
1050 }
1051 sqlite3_finalize(pRtree->pWriteNode);
1052 sqlite3_finalize(pRtree->pDeleteNode);
1053 sqlite3_finalize(pRtree->pReadRowid);
1054 sqlite3_finalize(pRtree->pWriteRowid);
1055 sqlite3_finalize(pRtree->pDeleteRowid);
1056 sqlite3_finalize(pRtree->pReadParent);
1057 sqlite3_finalize(pRtree->pWriteParent);
1058 sqlite3_finalize(pRtree->pDeleteParent);
1059 sqlite3_finalize(pRtree->pWriteAux);
1060 sqlite3_free(pRtree->zReadAuxSql);
1061 sqlite3_free(pRtree);
1062 }
1063 }
1064
1065 /*
1066 ** Rtree virtual table module xDisconnect method.
1067 */
1068 static int rtreeDisconnect(sqlite3_vtab *pVtab){
1069 rtreeRelease((Rtree *)pVtab);
1070 return SQLITE_OK;
1071 }
1072
1073 /*
1074 ** Rtree virtual table module xDestroy method.
1075 */
1076 static int rtreeDestroy(sqlite3_vtab *pVtab){
1077 Rtree *pRtree = (Rtree *)pVtab;
1078 int rc;
1079 char *zCreate = sqlite3_mprintf(
1080 "DROP TABLE '%q'.'%q_node';"
1081 "DROP TABLE '%q'.'%q_rowid';"
1082 "DROP TABLE '%q'.'%q_parent';",
1083 pRtree->zDb, pRtree->zName,
1084 pRtree->zDb, pRtree->zName,
1085 pRtree->zDb, pRtree->zName
1086 );
1087 if( !zCreate ){
1088 rc = SQLITE_NOMEM;
1089 }else{
1090 nodeBlobReset(pRtree);
1091 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
1092 sqlite3_free(zCreate);
1093 }
1094 if( rc==SQLITE_OK ){
1095 rtreeRelease(pRtree);
1096 }
1097
1098 return rc;
1099 }
1100
1101 /*
1102 ** Rtree virtual table module xOpen method.
1103 */
1104 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
1105 int rc = SQLITE_NOMEM;
1106 Rtree *pRtree = (Rtree *)pVTab;
1107 RtreeCursor *pCsr;
1108
1109 pCsr = (RtreeCursor *)sqlite3_malloc64(sizeof(RtreeCursor));
1110 if( pCsr ){
1111 memset(pCsr, 0, sizeof(RtreeCursor));
1112 pCsr->base.pVtab = pVTab;
1113 rc = SQLITE_OK;
1114 pRtree->nCursor++;
1115 }
1116 *ppCursor = (sqlite3_vtab_cursor *)pCsr;
1117
1118 return rc;
1119 }
1120
1121
1122 /*
1123 ** Reset a cursor back to its initial state.
1124 */
1125 static void resetCursor(RtreeCursor *pCsr){
1126 Rtree *pRtree = (Rtree *)(pCsr->base.pVtab);
1127 int ii;
1128 sqlite3_stmt *pStmt;
1129 if( pCsr->aConstraint ){
1130 int i; /* Used to iterate through constraint array */
1131 for(i=0; i<pCsr->nConstraint; i++){
1132 sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
1133 if( pInfo ){
1134 if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
1135 sqlite3_free(pInfo);
1136 }
1137 }
1138 sqlite3_free(pCsr->aConstraint);
1139 pCsr->aConstraint = 0;
1140 }
1141 for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
1142 sqlite3_free(pCsr->aPoint);
1143 pStmt = pCsr->pReadAux;
1144 memset(pCsr, 0, sizeof(RtreeCursor));
1145 pCsr->base.pVtab = (sqlite3_vtab*)pRtree;
1146 pCsr->pReadAux = pStmt;
1147
1148 /* The following will only fail if the previous sqlite3_step() call failed,
1149 ** in which case the error has already been caught. This statement never
1150 ** encounters an error within an sqlite3_column_xxx() function, as it
1151 ** calls sqlite3_column_value(), which does not use malloc(). So it is safe
1152 ** to ignore the error code here. */
1153 sqlite3_reset(pStmt);
1154 }
1155
1156 /*
1157 ** Rtree virtual table module xClose method.
1158 */
1159 static int rtreeClose(sqlite3_vtab_cursor *cur){
1160 Rtree *pRtree = (Rtree *)(cur->pVtab);
1161 RtreeCursor *pCsr = (RtreeCursor *)cur;
1162 assert( pRtree->nCursor>0 );
1163 resetCursor(pCsr);
1164 sqlite3_finalize(pCsr->pReadAux);
1165 sqlite3_free(pCsr);
1166 pRtree->nCursor--;
1167 if( pRtree->nCursor==0 && pRtree->inWrTrans==0 ){
1168 nodeBlobReset(pRtree);
1169 }
1170 return SQLITE_OK;
1171 }
1172
1173 /*
1174 ** Rtree virtual table module xEof method.
1175 **
1176 ** Return non-zero if the cursor does not currently point to a valid
1177 ** record (i.e if the scan has finished), or zero otherwise.
1178 */
1179 static int rtreeEof(sqlite3_vtab_cursor *cur){
1180 RtreeCursor *pCsr = (RtreeCursor *)cur;
1181 return pCsr->atEOF;
1182 }
1183
1184 /*
1185 ** Convert raw bits from the on-disk RTree record into a coordinate value.
1186 ** The on-disk format is big-endian and needs to be converted for little-
1187 ** endian platforms. The on-disk record stores integer coordinates if
1188 ** eInt is true and it stores 32-bit floating point records if eInt is
1189 ** false. a[] is the four bytes of the on-disk record to be decoded.
1190 ** Store the results in "r".
1191 **
1192 ** There are five versions of this macro. The last one is generic. The
1193 ** other four are various architectures-specific optimizations.
1194 */
1195 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1196 #define RTREE_DECODE_COORD(eInt, a, r) { \
1197 RtreeCoord c; /* Coordinate decoded */ \
1198 c.u = _byteswap_ulong(*(u32*)a); \
1199 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1200 }
1201 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1202 #define RTREE_DECODE_COORD(eInt, a, r) { \
1203 RtreeCoord c; /* Coordinate decoded */ \
1204 c.u = __builtin_bswap32(*(u32*)a); \
1205 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1206 }
1207 #elif SQLITE_BYTEORDER==1234
1208 #define RTREE_DECODE_COORD(eInt, a, r) { \
1209 RtreeCoord c; /* Coordinate decoded */ \
1210 memcpy(&c.u,a,4); \
1211 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
1212 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
1213 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1214 }
1215 #elif SQLITE_BYTEORDER==4321
1216 #define RTREE_DECODE_COORD(eInt, a, r) { \
1217 RtreeCoord c; /* Coordinate decoded */ \
1218 memcpy(&c.u,a,4); \
1219 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1220 }
1221 #else
1222 #define RTREE_DECODE_COORD(eInt, a, r) { \
1223 RtreeCoord c; /* Coordinate decoded */ \
1224 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
1225 +((u32)a[2]<<8) + a[3]; \
1226 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
1227 }
1228 #endif
1229
1230 /*
1231 ** Check the RTree node or entry given by pCellData and p against the MATCH
1232 ** constraint pConstraint.
1233 */
1234 static int rtreeCallbackConstraint(
1235 RtreeConstraint *pConstraint, /* The constraint to test */
1236 int eInt, /* True if RTree holding integer coordinates */
1237 u8 *pCellData, /* Raw cell content */
1238 RtreeSearchPoint *pSearch, /* Container of this cell */
1239 sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */
1240 int *peWithin /* OUT: visibility of the cell */
1241 ){
1242 sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
1243 int nCoord = pInfo->nCoord; /* No. of coordinates */
1244 int rc; /* Callback return code */
1245 RtreeCoord c; /* Translator union */
1246 sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */
1247
1248 assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );
1249 assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );
1250
1251 if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){
1252 pInfo->iRowid = readInt64(pCellData);
1253 }
1254 pCellData += 8;
1255 #ifndef SQLITE_RTREE_INT_ONLY
1256 if( eInt==0 ){
1257 switch( nCoord ){
1258 case 10: readCoord(pCellData+36, &c); aCoord[9] = c.f;
1259 readCoord(pCellData+32, &c); aCoord[8] = c.f;
1260 case 8: readCoord(pCellData+28, &c); aCoord[7] = c.f;
1261 readCoord(pCellData+24, &c); aCoord[6] = c.f;
1262 case 6: readCoord(pCellData+20, &c); aCoord[5] = c.f;
1263 readCoord(pCellData+16, &c); aCoord[4] = c.f;
1264 case 4: readCoord(pCellData+12, &c); aCoord[3] = c.f;
1265 readCoord(pCellData+8, &c); aCoord[2] = c.f;
1266 default: readCoord(pCellData+4, &c); aCoord[1] = c.f;
1267 readCoord(pCellData, &c); aCoord[0] = c.f;
1268 }
1269 }else
1270 #endif
1271 {
1272 switch( nCoord ){
1273 case 10: readCoord(pCellData+36, &c); aCoord[9] = c.i;
1274 readCoord(pCellData+32, &c); aCoord[8] = c.i;
1275 case 8: readCoord(pCellData+28, &c); aCoord[7] = c.i;
1276 readCoord(pCellData+24, &c); aCoord[6] = c.i;
1277 case 6: readCoord(pCellData+20, &c); aCoord[5] = c.i;
1278 readCoord(pCellData+16, &c); aCoord[4] = c.i;
1279 case 4: readCoord(pCellData+12, &c); aCoord[3] = c.i;
1280 readCoord(pCellData+8, &c); aCoord[2] = c.i;
1281 default: readCoord(pCellData+4, &c); aCoord[1] = c.i;
1282 readCoord(pCellData, &c); aCoord[0] = c.i;
1283 }
1284 }
1285 if( pConstraint->op==RTREE_MATCH ){
1286 int eWithin = 0;
1287 rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
1288 nCoord, aCoord, &eWithin);
1289 if( eWithin==0 ) *peWithin = NOT_WITHIN;
1290 *prScore = RTREE_ZERO;
1291 }else{
1292 pInfo->aCoord = aCoord;
1293 pInfo->iLevel = pSearch->iLevel - 1;
1294 pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
1295 pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
1296 rc = pConstraint->u.xQueryFunc(pInfo);
1297 if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
1298 if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
1299 *prScore = pInfo->rScore;
1300 }
1301 }
1302 return rc;
1303 }
1304
1305 /*
1306 ** Check the internal RTree node given by pCellData against constraint p.
1307 ** If this constraint cannot be satisfied by any child within the node,
1308 ** set *peWithin to NOT_WITHIN.
1309 */
1310 static void rtreeNonleafConstraint(
1311 RtreeConstraint *p, /* The constraint to test */
1312 int eInt, /* True if RTree holds integer coordinates */
1313 u8 *pCellData, /* Raw cell content as appears on disk */
1314 int *peWithin /* Adjust downward, as appropriate */
1315 ){
1316 sqlite3_rtree_dbl val; /* Coordinate value convert to a double */
1317
1318 /* p->iCoord might point to either a lower or upper bound coordinate
1319 ** in a coordinate pair. But make pCellData point to the lower bound.
1320 */
1321 pCellData += 8 + 4*(p->iCoord&0xfe);
1322
1323 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
1324 || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
1325 || p->op==RTREE_FALSE );
1326 assert( FOUR_BYTE_ALIGNED(pCellData) );
1327 switch( p->op ){
1328 case RTREE_TRUE: return; /* Always satisfied */
1329 case RTREE_FALSE: break; /* Never satisfied */
1330 case RTREE_EQ:
1331 RTREE_DECODE_COORD(eInt, pCellData, val);
1332 /* val now holds the lower bound of the coordinate pair */
1333 if( p->u.rValue>=val ){
1334 pCellData += 4;
1335 RTREE_DECODE_COORD(eInt, pCellData, val);
1336 /* val now holds the upper bound of the coordinate pair */
1337 if( p->u.rValue<=val ) return;
1338 }
1339 break;
1340 case RTREE_LE:
1341 case RTREE_LT:
1342 RTREE_DECODE_COORD(eInt, pCellData, val);
1343 /* val now holds the lower bound of the coordinate pair */
1344 if( p->u.rValue>=val ) return;
1345 break;
1346
1347 default:
1348 pCellData += 4;
1349 RTREE_DECODE_COORD(eInt, pCellData, val);
1350 /* val now holds the upper bound of the coordinate pair */
1351 if( p->u.rValue<=val ) return;
1352 break;
1353 }
1354 *peWithin = NOT_WITHIN;
1355 }
1356
1357 /*
1358 ** Check the leaf RTree cell given by pCellData against constraint p.
1359 ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
1360 ** If the constraint is satisfied, leave *peWithin unchanged.
1361 **
1362 ** The constraint is of the form: xN op $val
1363 **
1364 ** The op is given by p->op. The xN is p->iCoord-th coordinate in
1365 ** pCellData. $val is given by p->u.rValue.
1366 */
1367 static void rtreeLeafConstraint(
1368 RtreeConstraint *p, /* The constraint to test */
1369 int eInt, /* True if RTree holds integer coordinates */
1370 u8 *pCellData, /* Raw cell content as appears on disk */
1371 int *peWithin /* Adjust downward, as appropriate */
1372 ){
1373 RtreeDValue xN; /* Coordinate value converted to a double */
1374
1375 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
1376 || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
1377 || p->op==RTREE_FALSE );
1378 pCellData += 8 + p->iCoord*4;
1379 assert( FOUR_BYTE_ALIGNED(pCellData) );
1380 RTREE_DECODE_COORD(eInt, pCellData, xN);
1381 switch( p->op ){
1382 case RTREE_TRUE: return; /* Always satisfied */
1383 case RTREE_FALSE: break; /* Never satisfied */
1384 case RTREE_LE: if( xN <= p->u.rValue ) return; break;
1385 case RTREE_LT: if( xN < p->u.rValue ) return; break;
1386 case RTREE_GE: if( xN >= p->u.rValue ) return; break;
1387 case RTREE_GT: if( xN > p->u.rValue ) return; break;
1388 default: if( xN == p->u.rValue ) return; break;
1389 }
1390 *peWithin = NOT_WITHIN;
1391 }
1392
1393 /*
1394 ** One of the cells in node pNode is guaranteed to have a 64-bit
1395 ** integer value equal to iRowid. Return the index of this cell.
1396 */
1397 static int nodeRowidIndex(
1398 Rtree *pRtree,
1399 RtreeNode *pNode,
1400 i64 iRowid,
1401 int *piIndex
1402 ){
1403 int ii;
1404 int nCell = NCELL(pNode);
1405 assert( nCell<65536 && nCell>=0 );
1406 for(ii=0; ii<nCell; ii++){
1407 if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
1408 *piIndex = ii;
1409 return SQLITE_OK;
1410 }
1411 }
1412 RTREE_IS_CORRUPT(pRtree);
1413 return SQLITE_CORRUPT_VTAB;
1414 }
1415
1416 /*
1417 ** Return the index of the cell containing a pointer to node pNode
1418 ** in its parent. If pNode is the root node, return -1.
1419 */
1420 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
1421 RtreeNode *pParent = pNode->pParent;
1422 if( ALWAYS(pParent) ){
1423 return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
1424 }else{
1425 *piIndex = -1;
1426 return SQLITE_OK;
1427 }
1428 }
1429
1430 /*
1431 ** Compare two search points. Return negative, zero, or positive if the first
1432 ** is less than, equal to, or greater than the second.
1433 **
1434 ** The rScore is the primary key. Smaller rScore values come first.
1435 ** If the rScore is a tie, then use iLevel as the tie breaker with smaller
1436 ** iLevel values coming first. In this way, if rScore is the same for all
1437 ** SearchPoints, then iLevel becomes the deciding factor and the result
1438 ** is a depth-first search, which is the desired default behavior.
1439 */
1440 static int rtreeSearchPointCompare(
1441 const RtreeSearchPoint *pA,
1442 const RtreeSearchPoint *pB
1443 ){
1444 if( pA->rScore<pB->rScore ) return -1;
1445 if( pA->rScore>pB->rScore ) return +1;
1446 if( pA->iLevel<pB->iLevel ) return -1;
1447 if( pA->iLevel>pB->iLevel ) return +1;
1448 return 0;
1449 }
1450
1451 /*
1452 ** Interchange two search points in a cursor.
1453 */
1454 static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
1455 RtreeSearchPoint t = p->aPoint[i];
1456 assert( i<j );
1457 p->aPoint[i] = p->aPoint[j];
1458 p->aPoint[j] = t;
1459 i++; j++;
1460 if( i<RTREE_CACHE_SZ ){
1461 if( j>=RTREE_CACHE_SZ ){
1462 nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
1463 p->aNode[i] = 0;
1464 }else{
1465 RtreeNode *pTemp = p->aNode[i];
1466 p->aNode[i] = p->aNode[j];
1467 p->aNode[j] = pTemp;
1468 }
1469 }
1470 }
1471
1472 /*
1473 ** Return the search point with the lowest current score.
1474 */
1475 static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
1476 return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
1477 }
1478
1479 /*
1480 ** Get the RtreeNode for the search point with the lowest score.
1481 */
1482 static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
1483 sqlite3_int64 id;
1484 int ii = 1 - pCur->bPoint;
1485 assert( ii==0 || ii==1 );
1486 assert( pCur->bPoint || pCur->nPoint );
1487 if( pCur->aNode[ii]==0 ){
1488 assert( pRC!=0 );
1489 id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
1490 *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
1491 }
1492 return pCur->aNode[ii];
1493 }
1494
1495 /*
1496 ** Push a new element onto the priority queue
1497 */
1498 static RtreeSearchPoint *rtreeEnqueue(
1499 RtreeCursor *pCur, /* The cursor */
1500 RtreeDValue rScore, /* Score for the new search point */
1501 u8 iLevel /* Level for the new search point */
1502 ){
1503 int i, j;
1504 RtreeSearchPoint *pNew;
1505 if( pCur->nPoint>=pCur->nPointAlloc ){
1506 int nNew = pCur->nPointAlloc*2 + 8;
1507 pNew = sqlite3_realloc64(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
1508 if( pNew==0 ) return 0;
1509 pCur->aPoint = pNew;
1510 pCur->nPointAlloc = nNew;
1511 }
1512 i = pCur->nPoint++;
1513 pNew = pCur->aPoint + i;
1514 pNew->rScore = rScore;
1515 pNew->iLevel = iLevel;
1516 assert( iLevel<=RTREE_MAX_DEPTH );
1517 while( i>0 ){
1518 RtreeSearchPoint *pParent;
1519 j = (i-1)/2;
1520 pParent = pCur->aPoint + j;
1521 if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
1522 rtreeSearchPointSwap(pCur, j, i);
1523 i = j;
1524 pNew = pParent;
1525 }
1526 return pNew;
1527 }
1528
1529 /*
1530 ** Allocate a new RtreeSearchPoint and return a pointer to it. Return
1531 ** NULL if malloc fails.
1532 */
1533 static RtreeSearchPoint *rtreeSearchPointNew(
1534 RtreeCursor *pCur, /* The cursor */
1535 RtreeDValue rScore, /* Score for the new search point */
1536 u8 iLevel /* Level for the new search point */
1537 ){
1538 RtreeSearchPoint *pNew, *pFirst;
1539 pFirst = rtreeSearchPointFirst(pCur);
1540 pCur->anQueue[iLevel]++;
1541 if( pFirst==0
1542 || pFirst->rScore>rScore
1543 || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
1544 ){
1545 if( pCur->bPoint ){
1546 int ii;
1547 pNew = rtreeEnqueue(pCur, rScore, iLevel);
1548 if( pNew==0 ) return 0;
1549 ii = (int)(pNew - pCur->aPoint) + 1;
1550 assert( ii==1 );
1551 if( ALWAYS(ii<RTREE_CACHE_SZ) ){
1552 assert( pCur->aNode[ii]==0 );
1553 pCur->aNode[ii] = pCur->aNode[0];
1554 }else{
1555 nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
1556 }
1557 pCur->aNode[0] = 0;
1558 *pNew = pCur->sPoint;
1559 }
1560 pCur->sPoint.rScore = rScore;
1561 pCur->sPoint.iLevel = iLevel;
1562 pCur->bPoint = 1;
1563 return &pCur->sPoint;
1564 }else{
1565 return rtreeEnqueue(pCur, rScore, iLevel);
1566 }
1567 }
1568
1569 #if 0
1570 /* Tracing routines for the RtreeSearchPoint queue */
1571 static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
1572 if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
1573 printf(" %d.%05lld.%02d %g %d",
1574 p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
1575 );
1576 idx++;
1577 if( idx<RTREE_CACHE_SZ ){
1578 printf(" %p\n", pCur->aNode[idx]);
1579 }else{
1580 printf("\n");
1581 }
1582 }
1583 static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
1584 int ii;
1585 printf("=== %9s ", zPrefix);
1586 if( pCur->bPoint ){
1587 tracePoint(&pCur->sPoint, -1, pCur);
1588 }
1589 for(ii=0; ii<pCur->nPoint; ii++){
1590 if( ii>0 || pCur->bPoint ) printf(" ");
1591 tracePoint(&pCur->aPoint[ii], ii, pCur);
1592 }
1593 }
1594 # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
1595 #else
1596 # define RTREE_QUEUE_TRACE(A,B) /* no-op */
1597 #endif
1598
1599 /* Remove the search point with the lowest current score.
1600 */
1601 static void rtreeSearchPointPop(RtreeCursor *p){
1602 int i, j, k, n;
1603 i = 1 - p->bPoint;
1604 assert( i==0 || i==1 );
1605 if( p->aNode[i] ){
1606 nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
1607 p->aNode[i] = 0;
1608 }
1609 if( p->bPoint ){
1610 p->anQueue[p->sPoint.iLevel]--;
1611 p->bPoint = 0;
1612 }else if( ALWAYS(p->nPoint) ){
1613 p->anQueue[p->aPoint[0].iLevel]--;
1614 n = --p->nPoint;
1615 p->aPoint[0] = p->aPoint[n];
1616 if( n<RTREE_CACHE_SZ-1 ){
1617 p->aNode[1] = p->aNode[n+1];
1618 p->aNode[n+1] = 0;
1619 }
1620 i = 0;
1621 while( (j = i*2+1)<n ){
1622 k = j+1;
1623 if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
1624 if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
1625 rtreeSearchPointSwap(p, i, k);
1626 i = k;
1627 }else{
1628 break;
1629 }
1630 }else{
1631 if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
1632 rtreeSearchPointSwap(p, i, j);
1633 i = j;
1634 }else{
1635 break;
1636 }
1637 }
1638 }
1639 }
1640 }
1641
1642
1643 /*
1644 ** Continue the search on cursor pCur until the front of the queue
1645 ** contains an entry suitable for returning as a result-set row,
1646 ** or until the RtreeSearchPoint queue is empty, indicating that the
1647 ** query has completed.
1648 */
1649 static int rtreeStepToLeaf(RtreeCursor *pCur){
1650 RtreeSearchPoint *p;
1651 Rtree *pRtree = RTREE_OF_CURSOR(pCur);
1652 RtreeNode *pNode;
1653 int eWithin;
1654 int rc = SQLITE_OK;
1655 int nCell;
1656 int nConstraint = pCur->nConstraint;
1657 int ii;
1658 int eInt;
1659 RtreeSearchPoint x;
1660
1661 eInt = pRtree->eCoordType==RTREE_COORD_INT32;
1662 while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
1663 u8 *pCellData;
1664 pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
1665 if( rc ) return rc;
1666 nCell = NCELL(pNode);
1667 if( nCell>RTREE_MAXCELLS ){
1668 RTREE_IS_CORRUPT(pRtree);
1669 return SQLITE_CORRUPT_VTAB;
1670 }
1671 pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
1672 while( p->iCell<nCell ){
1673 sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
1674 eWithin = FULLY_WITHIN;
1675 for(ii=0; ii<nConstraint; ii++){
1676 RtreeConstraint *pConstraint = pCur->aConstraint + ii;
1677 if( pConstraint->op>=RTREE_MATCH ){
1678 rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
1679 &rScore, &eWithin);
1680 if( rc ) return rc;
1681 }else if( p->iLevel==1 ){
1682 rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin);
1683 }else{
1684 rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin);
1685 }
1686 if( eWithin==NOT_WITHIN ){
1687 p->iCell++;
1688 pCellData += pRtree->nBytesPerCell;
1689 break;
1690 }
1691 }
1692 if( eWithin==NOT_WITHIN ) continue;
1693 p->iCell++;
1694 x.iLevel = p->iLevel - 1;
1695 if( x.iLevel ){
1696 x.id = readInt64(pCellData);
1697 for(ii=0; ii<pCur->nPoint; ii++){
1698 if( pCur->aPoint[ii].id==x.id ){
1699 RTREE_IS_CORRUPT(pRtree);
1700 return SQLITE_CORRUPT_VTAB;
1701 }
1702 }
1703 x.iCell = 0;
1704 }else{
1705 x.id = p->id;
1706 x.iCell = p->iCell - 1;
1707 }
1708 if( p->iCell>=nCell ){
1709 RTREE_QUEUE_TRACE(pCur, "POP-S:");
1710 rtreeSearchPointPop(pCur);
1711 }
1712 if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
1713 p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
1714 if( p==0 ) return SQLITE_NOMEM;
1715 p->eWithin = (u8)eWithin;
1716 p->id = x.id;
1717 p->iCell = x.iCell;
1718 RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
1719 break;
1720 }
1721 if( p->iCell>=nCell ){
1722 RTREE_QUEUE_TRACE(pCur, "POP-Se:");
1723 rtreeSearchPointPop(pCur);
1724 }
1725 }
1726 pCur->atEOF = p==0;
1727 return SQLITE_OK;
1728 }
1729
1730 /*
1731 ** Rtree virtual table module xNext method.
1732 */
1733 static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
1734 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1735 int rc = SQLITE_OK;
1736
1737 /* Move to the next entry that matches the configured constraints. */
1738 RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
1739 if( pCsr->bAuxValid ){
1740 pCsr->bAuxValid = 0;
1741 sqlite3_reset(pCsr->pReadAux);
1742 }
1743 rtreeSearchPointPop(pCsr);
1744 rc = rtreeStepToLeaf(pCsr);
1745 return rc;
1746 }
1747
1748 /*
1749 ** Rtree virtual table module xRowid method.
1750 */
1751 static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
1752 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1753 RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
1754 int rc = SQLITE_OK;
1755 RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
1756 if( rc==SQLITE_OK && ALWAYS(p) ){
1757 if( p->iCell>=NCELL(pNode) ){
1758 rc = SQLITE_ABORT;
1759 }else{
1760 *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
1761 }
1762 }
1763 return rc;
1764 }
1765
1766 /*
1767 ** Rtree virtual table module xColumn method.
1768 */
1769 static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1770 Rtree *pRtree = (Rtree *)cur->pVtab;
1771 RtreeCursor *pCsr = (RtreeCursor *)cur;
1772 RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
1773 RtreeCoord c;
1774 int rc = SQLITE_OK;
1775 RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
1776
1777 if( rc ) return rc;
1778 if( NEVER(p==0) ) return SQLITE_OK;
1779 if( p->iCell>=NCELL(pNode) ) return SQLITE_ABORT;
1780 if( i==0 ){
1781 sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
1782 }else if( i<=pRtree->nDim2 ){
1783 nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
1784 #ifndef SQLITE_RTREE_INT_ONLY
1785 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1786 sqlite3_result_double(ctx, c.f);
1787 }else
1788 #endif
1789 {
1790 assert( pRtree->eCoordType==RTREE_COORD_INT32 );
1791 sqlite3_result_int(ctx, c.i);
1792 }
1793 }else{
1794 if( !pCsr->bAuxValid ){
1795 if( pCsr->pReadAux==0 ){
1796 rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0,
1797 &pCsr->pReadAux, 0);
1798 if( rc ) return rc;
1799 }
1800 sqlite3_bind_int64(pCsr->pReadAux, 1,
1801 nodeGetRowid(pRtree, pNode, p->iCell));
1802 rc = sqlite3_step(pCsr->pReadAux);
1803 if( rc==SQLITE_ROW ){
1804 pCsr->bAuxValid = 1;
1805 }else{
1806 sqlite3_reset(pCsr->pReadAux);
1807 if( rc==SQLITE_DONE ) rc = SQLITE_OK;
1808 return rc;
1809 }
1810 }
1811 sqlite3_result_value(ctx,
1812 sqlite3_column_value(pCsr->pReadAux, i - pRtree->nDim2 + 1));
1813 }
1814 return SQLITE_OK;
1815 }
1816
1817 /*
1818 ** Use nodeAcquire() to obtain the leaf node containing the record with
1819 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
1820 ** return SQLITE_OK. If there is no such record in the table, set
1821 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1822 ** to zero and return an SQLite error code.
1823 */
1824 static int findLeafNode(
1825 Rtree *pRtree, /* RTree to search */
1826 i64 iRowid, /* The rowid searching for */
1827 RtreeNode **ppLeaf, /* Write the node here */
1828 sqlite3_int64 *piNode /* Write the node-id here */
1829 ){
1830 int rc;
1831 *ppLeaf = 0;
1832 sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
1833 if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
1834 i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
1835 if( piNode ) *piNode = iNode;
1836 rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
1837 sqlite3_reset(pRtree->pReadRowid);
1838 }else{
1839 rc = sqlite3_reset(pRtree->pReadRowid);
1840 }
1841 return rc;
1842 }
1843
1844 /*
1845 ** This function is called to configure the RtreeConstraint object passed
1846 ** as the second argument for a MATCH constraint. The value passed as the
1847 ** first argument to this function is the right-hand operand to the MATCH
1848 ** operator.
1849 */
1850 static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
1851 RtreeMatchArg *pBlob, *pSrc; /* BLOB returned by geometry function */
1852 sqlite3_rtree_query_info *pInfo; /* Callback information */
1853
1854 pSrc = sqlite3_value_pointer(pValue, "RtreeMatchArg");
1855 if( pSrc==0 ) return SQLITE_ERROR;
1856 pInfo = (sqlite3_rtree_query_info*)
1857 sqlite3_malloc64( sizeof(*pInfo)+pSrc->iSize );
1858 if( !pInfo ) return SQLITE_NOMEM;
1859 memset(pInfo, 0, sizeof(*pInfo));
1860 pBlob = (RtreeMatchArg*)&pInfo[1];
1861 memcpy(pBlob, pSrc, pSrc->iSize);
1862 pInfo->pContext = pBlob->cb.pContext;
1863 pInfo->nParam = pBlob->nParam;
1864 pInfo->aParam = pBlob->aParam;
1865 pInfo->apSqlParam = pBlob->apSqlParam;
1866
1867 if( pBlob->cb.xGeom ){
1868 pCons->u.xGeom = pBlob->cb.xGeom;
1869 }else{
1870 pCons->op = RTREE_QUERY;
1871 pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
1872 }
1873 pCons->pInfo = pInfo;
1874 return SQLITE_OK;
1875 }
1876
1877 int sqlite3IntFloatCompare(i64,double);
1878
1879 /*
1880 ** Rtree virtual table module xFilter method.
1881 */
1882 static int rtreeFilter(
1883 sqlite3_vtab_cursor *pVtabCursor,
1884 int idxNum, const char *idxStr,
1885 int argc, sqlite3_value **argv
1886 ){
1887 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1888 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1889 RtreeNode *pRoot = 0;
1890 int ii;
1891 int rc = SQLITE_OK;
1892 int iCell = 0;
1893
1894 rtreeReference(pRtree);
1895
1896 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
1897 resetCursor(pCsr);
1898
1899 pCsr->iStrategy = idxNum;
1900 if( idxNum==1 ){
1901 /* Special case - lookup by rowid. */
1902 RtreeNode *pLeaf; /* Leaf on which the required cell resides */
1903 RtreeSearchPoint *p; /* Search point for the leaf */
1904 i64 iRowid = sqlite3_value_int64(argv[0]);
1905 i64 iNode = 0;
1906 int eType = sqlite3_value_numeric_type(argv[0]);
1907 if( eType==SQLITE_INTEGER
1908 || (eType==SQLITE_FLOAT
1909 && 0==sqlite3IntFloatCompare(iRowid,sqlite3_value_double(argv[0])))
1910 ){
1911 rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
1912 }else{
1913 rc = SQLITE_OK;
1914 pLeaf = 0;
1915 }
1916 if( rc==SQLITE_OK && pLeaf!=0 ){
1917 p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
1918 assert( p!=0 ); /* Always returns pCsr->sPoint */
1919 pCsr->aNode[0] = pLeaf;
1920 p->id = iNode;
1921 p->eWithin = PARTLY_WITHIN;
1922 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
1923 p->iCell = (u8)iCell;
1924 RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
1925 }else{
1926 pCsr->atEOF = 1;
1927 }
1928 }else{
1929 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1930 ** with the configured constraints.
1931 */
1932 rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1933 if( rc==SQLITE_OK && argc>0 ){
1934 pCsr->aConstraint = sqlite3_malloc64(sizeof(RtreeConstraint)*argc);
1935 pCsr->nConstraint = argc;
1936 if( !pCsr->aConstraint ){
1937 rc = SQLITE_NOMEM;
1938 }else{
1939 memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
1940 memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
1941 assert( (idxStr==0 && argc==0)
1942 || (idxStr && (int)strlen(idxStr)==argc*2) );
1943 for(ii=0; ii<argc; ii++){
1944 RtreeConstraint *p = &pCsr->aConstraint[ii];
1945 int eType = sqlite3_value_numeric_type(argv[ii]);
1946 p->op = idxStr[ii*2];
1947 p->iCoord = idxStr[ii*2+1]-'0';
1948 if( p->op>=RTREE_MATCH ){
1949 /* A MATCH operator. The right-hand-side must be a blob that
1950 ** can be cast into an RtreeMatchArg object. One created using
1951 ** an sqlite3_rtree_geometry_callback() SQL user function.
1952 */
1953 rc = deserializeGeometry(argv[ii], p);
1954 if( rc!=SQLITE_OK ){
1955 break;
1956 }
1957 p->pInfo->nCoord = pRtree->nDim2;
1958 p->pInfo->anQueue = pCsr->anQueue;
1959 p->pInfo->mxLevel = pRtree->iDepth + 1;
1960 }else if( eType==SQLITE_INTEGER ){
1961 sqlite3_int64 iVal = sqlite3_value_int64(argv[ii]);
1962 #ifdef SQLITE_RTREE_INT_ONLY
1963 p->u.rValue = iVal;
1964 #else
1965 p->u.rValue = (double)iVal;
1966 if( iVal>=((sqlite3_int64)1)<<48
1967 || iVal<=-(((sqlite3_int64)1)<<48)
1968 ){
1969 if( p->op==RTREE_LT ) p->op = RTREE_LE;
1970 if( p->op==RTREE_GT ) p->op = RTREE_GE;
1971 }
1972 #endif
1973 }else if( eType==SQLITE_FLOAT ){
1974 #ifdef SQLITE_RTREE_INT_ONLY
1975 p->u.rValue = sqlite3_value_int64(argv[ii]);
1976 #else
1977 p->u.rValue = sqlite3_value_double(argv[ii]);
1978 #endif
1979 }else{
1980 p->u.rValue = RTREE_ZERO;
1981 if( eType==SQLITE_NULL ){
1982 p->op = RTREE_FALSE;
1983 }else if( p->op==RTREE_LT || p->op==RTREE_LE ){
1984 p->op = RTREE_TRUE;
1985 }else{
1986 p->op = RTREE_FALSE;
1987 }
1988 }
1989 }
1990 }
1991 }
1992 if( rc==SQLITE_OK ){
1993 RtreeSearchPoint *pNew;
1994 assert( pCsr->bPoint==0 ); /* Due to the resetCursor() call above */
1995 pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1));
1996 if( NEVER(pNew==0) ){ /* Because pCsr->bPoint was FALSE */
1997 return SQLITE_NOMEM;
1998 }
1999 pNew->id = 1;
2000 pNew->iCell = 0;
2001 pNew->eWithin = PARTLY_WITHIN;
2002 assert( pCsr->bPoint==1 );
2003 pCsr->aNode[0] = pRoot;
2004 pRoot = 0;
2005 RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
2006 rc = rtreeStepToLeaf(pCsr);
2007 }
2008 }
2009
2010 nodeRelease(pRtree, pRoot);
2011 rtreeRelease(pRtree);
2012 return rc;
2013 }
2014
2015 /*
2016 ** Rtree virtual table module xBestIndex method. There are three
2017 ** table scan strategies to choose from (in order from most to
2018 ** least desirable):
2019 **
2020 ** idxNum idxStr Strategy
2021 ** ------------------------------------------------
2022 ** 1 Unused Direct lookup by rowid.
2023 ** 2 See below R-tree query or full-table scan.
2024 ** ------------------------------------------------
2025 **
2026 ** If strategy 1 is used, then idxStr is not meaningful. If strategy
2027 ** 2 is used, idxStr is formatted to contain 2 bytes for each
2028 ** constraint used. The first two bytes of idxStr correspond to
2029 ** the constraint in sqlite3_index_info.aConstraintUsage[] with
2030 ** (argvIndex==1) etc.
2031 **
2032 ** The first of each pair of bytes in idxStr identifies the constraint
2033 ** operator as follows:
2034 **
2035 ** Operator Byte Value
2036 ** ----------------------
2037 ** = 0x41 ('A')
2038 ** <= 0x42 ('B')
2039 ** < 0x43 ('C')
2040 ** >= 0x44 ('D')
2041 ** > 0x45 ('E')
2042 ** MATCH 0x46 ('F')
2043 ** ----------------------
2044 **
2045 ** The second of each pair of bytes identifies the coordinate column
2046 ** to which the constraint applies. The leftmost coordinate column
2047 ** is 'a', the second from the left 'b' etc.
2048 */
2049 static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
2050 Rtree *pRtree = (Rtree*)tab;
2051 int rc = SQLITE_OK;
2052 int ii;
2053 int bMatch = 0; /* True if there exists a MATCH constraint */
2054 i64 nRow; /* Estimated rows returned by this scan */
2055
2056 int iIdx = 0;
2057 char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
2058 memset(zIdxStr, 0, sizeof(zIdxStr));
2059
2060 /* Check if there exists a MATCH constraint - even an unusable one. If there
2061 ** is, do not consider the lookup-by-rowid plan as using such a plan would
2062 ** require the VDBE to evaluate the MATCH constraint, which is not currently
2063 ** possible. */
2064 for(ii=0; ii<pIdxInfo->nConstraint; ii++){
2065 if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){
2066 bMatch = 1;
2067 }
2068 }
2069
2070 assert( pIdxInfo->idxStr==0 );
2071 for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
2072 struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
2073
2074 if( bMatch==0 && p->usable
2075 && p->iColumn<=0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ
2076 ){
2077 /* We have an equality constraint on the rowid. Use strategy 1. */
2078 int jj;
2079 for(jj=0; jj<ii; jj++){
2080 pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
2081 pIdxInfo->aConstraintUsage[jj].omit = 0;
2082 }
2083 pIdxInfo->idxNum = 1;
2084 pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
2085 pIdxInfo->aConstraintUsage[jj].omit = 1;
2086
2087 /* This strategy involves a two rowid lookups on an B-Tree structures
2088 ** and then a linear search of an R-Tree node. This should be
2089 ** considered almost as quick as a direct rowid lookup (for which
2090 ** sqlite uses an internal cost of 0.0). It is expected to return
2091 ** a single row.
2092 */
2093 pIdxInfo->estimatedCost = 30.0;
2094 pIdxInfo->estimatedRows = 1;
2095 pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
2096 return SQLITE_OK;
2097 }
2098
2099 if( p->usable
2100 && ((p->iColumn>0 && p->iColumn<=pRtree->nDim2)
2101 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH)
2102 ){
2103 u8 op;
2104 u8 doOmit = 1;
2105 switch( p->op ){
2106 case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; doOmit = 0; break;
2107 case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; doOmit = 0; break;
2108 case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
2109 case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; doOmit = 0; break;
2110 case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
2111 case SQLITE_INDEX_CONSTRAINT_MATCH: op = RTREE_MATCH; break;
2112 default: op = 0; break;
2113 }
2114 if( op ){
2115 zIdxStr[iIdx++] = op;
2116 zIdxStr[iIdx++] = (char)(p->iColumn - 1 + '0');
2117 pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
2118 pIdxInfo->aConstraintUsage[ii].omit = doOmit;
2119 }
2120 }
2121 }
2122
2123 pIdxInfo->idxNum = 2;
2124 pIdxInfo->needToFreeIdxStr = 1;
2125 if( iIdx>0 ){
2126 pIdxInfo->idxStr = sqlite3_malloc( iIdx+1 );
2127 if( pIdxInfo->idxStr==0 ){
2128 return SQLITE_NOMEM;
2129 }
2130 memcpy(pIdxInfo->idxStr, zIdxStr, iIdx+1);
2131 }
2132
2133 nRow = pRtree->nRowEst >> (iIdx/2);
2134 pIdxInfo->estimatedCost = (double)6.0 * (double)nRow;
2135 pIdxInfo->estimatedRows = nRow;
2136
2137 return rc;
2138 }
2139
2140 /*
2141 ** Return the N-dimensional volume of the cell stored in *p.
2142 */
2143 static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){
2144 RtreeDValue area = (RtreeDValue)1;
2145 assert( pRtree->nDim>=1 && pRtree->nDim<=5 );
2146 #ifndef SQLITE_RTREE_INT_ONLY
2147 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
2148 switch( pRtree->nDim ){
2149 case 5: area = p->aCoord[9].f - p->aCoord[8].f;
2150 case 4: area *= p->aCoord[7].f - p->aCoord[6].f;
2151 case 3: area *= p->aCoord[5].f - p->aCoord[4].f;
2152 case 2: area *= p->aCoord[3].f - p->aCoord[2].f;
2153 default: area *= p->aCoord[1].f - p->aCoord[0].f;
2154 }
2155 }else
2156 #endif
2157 {
2158 switch( pRtree->nDim ){
2159 case 5: area = (i64)p->aCoord[9].i - (i64)p->aCoord[8].i;
2160 case 4: area *= (i64)p->aCoord[7].i - (i64)p->aCoord[6].i;
2161 case 3: area *= (i64)p->aCoord[5].i - (i64)p->aCoord[4].i;
2162 case 2: area *= (i64)p->aCoord[3].i - (i64)p->aCoord[2].i;
2163 default: area *= (i64)p->aCoord[1].i - (i64)p->aCoord[0].i;
2164 }
2165 }
2166 return area;
2167 }
2168
2169 /*
2170 ** Return the margin length of cell p. The margin length is the sum
2171 ** of the objects size in each dimension.
2172 */
2173 static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
2174 RtreeDValue margin = 0;
2175 int ii = pRtree->nDim2 - 2;
2176 do{
2177 margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
2178 ii -= 2;
2179 }while( ii>=0 );
2180 return margin;
2181 }
2182
2183 /*
2184 ** Store the union of cells p1 and p2 in p1.
2185 */
2186 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
2187 int ii = 0;
2188 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
2189 do{
2190 p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
2191 p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
2192 ii += 2;
2193 }while( ii<pRtree->nDim2 );
2194 }else{
2195 do{
2196 p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
2197 p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
2198 ii += 2;
2199 }while( ii<pRtree->nDim2 );
2200 }
2201 }
2202
2203 /*
2204 ** Return true if the area covered by p2 is a subset of the area covered
2205 ** by p1. False otherwise.
2206 */
2207 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
2208 int ii;
2209 if( pRtree->eCoordType==RTREE_COORD_INT32 ){
2210 for(ii=0; ii<pRtree->nDim2; ii+=2){
2211 RtreeCoord *a1 = &p1->aCoord[ii];
2212 RtreeCoord *a2 = &p2->aCoord[ii];
2213 if( a2[0].i<a1[0].i || a2[1].i>a1[1].i ) return 0;
2214 }
2215 }else{
2216 for(ii=0; ii<pRtree->nDim2; ii+=2){
2217 RtreeCoord *a1 = &p1->aCoord[ii];
2218 RtreeCoord *a2 = &p2->aCoord[ii];
2219 if( a2[0].f<a1[0].f || a2[1].f>a1[1].f ) return 0;
2220 }
2221 }
2222 return 1;
2223 }
2224
2225 static RtreeDValue cellOverlap(
2226 Rtree *pRtree,
2227 RtreeCell *p,
2228 RtreeCell *aCell,
2229 int nCell
2230 ){
2231 int ii;
2232 RtreeDValue overlap = RTREE_ZERO;
2233 for(ii=0; ii<nCell; ii++){
2234 int jj;
2235 RtreeDValue o = (RtreeDValue)1;
2236 for(jj=0; jj<pRtree->nDim2; jj+=2){
2237 RtreeDValue x1, x2;
2238 x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
2239 x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
2240 if( x2<x1 ){
2241 o = (RtreeDValue)0;
2242 break;
2243 }else{
2244 o = o * (x2-x1);
2245 }
2246 }
2247 overlap += o;
2248 }
2249 return overlap;
2250 }
2251
2252
2253 /*
2254 ** This function implements the ChooseLeaf algorithm from Gutman[84].
2255 ** ChooseSubTree in r*tree terminology.
2256 */
2257 static int ChooseLeaf(
2258 Rtree *pRtree, /* Rtree table */
2259 RtreeCell *pCell, /* Cell to insert into rtree */
2260 int iHeight, /* Height of sub-tree rooted at pCell */
2261 RtreeNode **ppLeaf /* OUT: Selected leaf page */
2262 ){
2263 int rc;
2264 int ii;
2265 RtreeNode *pNode = 0;
2266 rc = nodeAcquire(pRtree, 1, 0, &pNode);
2267
2268 for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
2269 int iCell;
2270 sqlite3_int64 iBest = 0;
2271 int bFound = 0;
2272 RtreeDValue fMinGrowth = RTREE_ZERO;
2273 RtreeDValue fMinArea = RTREE_ZERO;
2274 int nCell = NCELL(pNode);
2275 RtreeNode *pChild = 0;
2276
2277 /* First check to see if there is are any cells in pNode that completely
2278 ** contains pCell. If two or more cells in pNode completely contain pCell
2279 ** then pick the smallest.
2280 */
2281 for(iCell=0; iCell<nCell; iCell++){
2282 RtreeCell cell;
2283 nodeGetCell(pRtree, pNode, iCell, &cell);
2284 if( cellContains(pRtree, &cell, pCell) ){
2285 RtreeDValue area = cellArea(pRtree, &cell);
2286 if( bFound==0 || area<fMinArea ){
2287 iBest = cell.iRowid;
2288 fMinArea = area;
2289 bFound = 1;
2290 }
2291 }
2292 }
2293 if( !bFound ){
2294 /* No cells of pNode will completely contain pCell. So pick the
2295 ** cell of pNode that grows by the least amount when pCell is added.
2296 ** Break ties by selecting the smaller cell.
2297 */
2298 for(iCell=0; iCell<nCell; iCell++){
2299 RtreeCell cell;
2300 RtreeDValue growth;
2301 RtreeDValue area;
2302 nodeGetCell(pRtree, pNode, iCell, &cell);
2303 area = cellArea(pRtree, &cell);
2304 cellUnion(pRtree, &cell, pCell);
2305 growth = cellArea(pRtree, &cell)-area;
2306 if( iCell==0
2307 || growth<fMinGrowth
2308 || (growth==fMinGrowth && area<fMinArea)
2309 ){
2310 fMinGrowth = growth;
2311 fMinArea = area;
2312 iBest = cell.iRowid;
2313 }
2314 }
2315 }
2316
2317 rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
2318 nodeRelease(pRtree, pNode);
2319 pNode = pChild;
2320 }
2321
2322 *ppLeaf = pNode;
2323 return rc;
2324 }
2325
2326 /*
2327 ** A cell with the same content as pCell has just been inserted into
2328 ** the node pNode. This function updates the bounding box cells in
2329 ** all ancestor elements.
2330 */
2331 static int AdjustTree(
2332 Rtree *pRtree, /* Rtree table */
2333 RtreeNode *pNode, /* Adjust ancestry of this node. */
2334 RtreeCell *pCell /* This cell was just inserted */
2335 ){
2336 RtreeNode *p = pNode;
2337 int cnt = 0;
2338 int rc;
2339 while( p->pParent ){
2340 RtreeNode *pParent = p->pParent;
2341 RtreeCell cell;
2342 int iCell;
2343
2344 cnt++;
2345 if( cnt>100 ){
2346 RTREE_IS_CORRUPT(pRtree);
2347 return SQLITE_CORRUPT_VTAB;
2348 }
2349 rc = nodeParentIndex(pRtree, p, &iCell);
2350 if( NEVER(rc!=SQLITE_OK) ){
2351 RTREE_IS_CORRUPT(pRtree);
2352 return SQLITE_CORRUPT_VTAB;
2353 }
2354
2355 nodeGetCell(pRtree, pParent, iCell, &cell);
2356 if( !cellContains(pRtree, &cell, pCell) ){
2357 cellUnion(pRtree, &cell, pCell);
2358 nodeOverwriteCell(pRtree, pParent, &cell, iCell);
2359 }
2360
2361 p = pParent;
2362 }
2363 return SQLITE_OK;
2364 }
2365
2366 /*
2367 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
2368 */
2369 static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
2370 sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
2371 sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
2372 sqlite3_step(pRtree->pWriteRowid);
2373 return sqlite3_reset(pRtree->pWriteRowid);
2374 }
2375
2376 /*
2377 ** Write mapping (iNode->iPar) to the <rtree>_parent table.
2378 */
2379 static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
2380 sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
2381 sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
2382 sqlite3_step(pRtree->pWriteParent);
2383 return sqlite3_reset(pRtree->pWriteParent);
2384 }
2385
2386 static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
2387
2388
2389
2390 /*
2391 ** Arguments aIdx, aCell and aSpare all point to arrays of size
2392 ** nIdx. The aIdx array contains the set of integers from 0 to
2393 ** (nIdx-1) in no particular order. This function sorts the values
2394 ** in aIdx according to dimension iDim of the cells in aCell. The
2395 ** minimum value of dimension iDim is considered first, the
2396 ** maximum used to break ties.
2397 **
2398 ** The aSpare array is used as temporary working space by the
2399 ** sorting algorithm.
2400 */
2401 static void SortByDimension(
2402 Rtree *pRtree,
2403 int *aIdx,
2404 int nIdx,
2405 int iDim,
2406 RtreeCell *aCell,
2407 int *aSpare
2408 ){
2409 if( nIdx>1 ){
2410
2411 int iLeft = 0;
2412 int iRight = 0;
2413
2414 int nLeft = nIdx/2;
2415 int nRight = nIdx-nLeft;
2416 int *aLeft = aIdx;
2417 int *aRight = &aIdx[nLeft];
2418
2419 SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
2420 SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
2421
2422 memcpy(aSpare, aLeft, sizeof(int)*nLeft);
2423 aLeft = aSpare;
2424 while( iLeft<nLeft || iRight<nRight ){
2425 RtreeDValue xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
2426 RtreeDValue xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
2427 RtreeDValue xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
2428 RtreeDValue xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
2429 if( (iLeft!=nLeft) && ((iRight==nRight)
2430 || (xleft1<xright1)
2431 || (xleft1==xright1 && xleft2<xright2)
2432 )){
2433 aIdx[iLeft+iRight] = aLeft[iLeft];
2434 iLeft++;
2435 }else{
2436 aIdx[iLeft+iRight] = aRight[iRight];
2437 iRight++;
2438 }
2439 }
2440
2441 #if 0
2442 /* Check that the sort worked */
2443 {
2444 int jj;
2445 for(jj=1; jj<nIdx; jj++){
2446 RtreeDValue xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
2447 RtreeDValue xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
2448 RtreeDValue xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
2449 RtreeDValue xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
2450 assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
2451 }
2452 }
2453 #endif
2454 }
2455 }
2456
2457 /*
2458 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
2459 */
2460 static int splitNodeStartree(
2461 Rtree *pRtree,
2462 RtreeCell *aCell,
2463 int nCell,
2464 RtreeNode *pLeft,
2465 RtreeNode *pRight,
2466 RtreeCell *pBboxLeft,
2467 RtreeCell *pBboxRight
2468 ){
2469 int **aaSorted;
2470 int *aSpare;
2471 int ii;
2472
2473 int iBestDim = 0;
2474 int iBestSplit = 0;
2475 RtreeDValue fBestMargin = RTREE_ZERO;
2476
2477 sqlite3_int64 nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
2478
2479 aaSorted = (int **)sqlite3_malloc64(nByte);
2480 if( !aaSorted ){
2481 return SQLITE_NOMEM;
2482 }
2483
2484 aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
2485 memset(aaSorted, 0, nByte);
2486 for(ii=0; ii<pRtree->nDim; ii++){
2487 int jj;
2488 aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
2489 for(jj=0; jj<nCell; jj++){
2490 aaSorted[ii][jj] = jj;
2491 }
2492 SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
2493 }
2494
2495 for(ii=0; ii<pRtree->nDim; ii++){
2496 RtreeDValue margin = RTREE_ZERO;
2497 RtreeDValue fBestOverlap = RTREE_ZERO;
2498 RtreeDValue fBestArea = RTREE_ZERO;
2499 int iBestLeft = 0;
2500 int nLeft;
2501
2502 for(
2503 nLeft=RTREE_MINCELLS(pRtree);
2504 nLeft<=(nCell-RTREE_MINCELLS(pRtree));
2505 nLeft++
2506 ){
2507 RtreeCell left;
2508 RtreeCell right;
2509 int kk;
2510 RtreeDValue overlap;
2511 RtreeDValue area;
2512
2513 memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
2514 memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
2515 for(kk=1; kk<(nCell-1); kk++){
2516 if( kk<nLeft ){
2517 cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
2518 }else{
2519 cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
2520 }
2521 }
2522 margin += cellMargin(pRtree, &left);
2523 margin += cellMargin(pRtree, &right);
2524 overlap = cellOverlap(pRtree, &left, &right, 1);
2525 area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
2526 if( (nLeft==RTREE_MINCELLS(pRtree))
2527 || (overlap<fBestOverlap)
2528 || (overlap==fBestOverlap && area<fBestArea)
2529 ){
2530 iBestLeft = nLeft;
2531 fBestOverlap = overlap;
2532 fBestArea = area;
2533 }
2534 }
2535
2536 if( ii==0 || margin<fBestMargin ){
2537 iBestDim = ii;
2538 fBestMargin = margin;
2539 iBestSplit = iBestLeft;
2540 }
2541 }
2542
2543 memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
2544 memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
2545 for(ii=0; ii<nCell; ii++){
2546 RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
2547 RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
2548 RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
2549 nodeInsertCell(pRtree, pTarget, pCell);
2550 cellUnion(pRtree, pBbox, pCell);
2551 }
2552
2553 sqlite3_free(aaSorted);
2554 return SQLITE_OK;
2555 }
2556
2557
2558 static int updateMapping(
2559 Rtree *pRtree,
2560 i64 iRowid,
2561 RtreeNode *pNode,
2562 int iHeight
2563 ){
2564 int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
2565 xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
2566 if( iHeight>0 ){
2567 RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
2568 RtreeNode *p;
2569 for(p=pNode; p; p=p->pParent){
2570 if( p==pChild ) return SQLITE_CORRUPT_VTAB;
2571 }
2572 if( pChild ){
2573 nodeRelease(pRtree, pChild->pParent);
2574 nodeReference(pNode);
2575 pChild->pParent = pNode;
2576 }
2577 }
2578 if( NEVER(pNode==0) ) return SQLITE_ERROR;
2579 return xSetMapping(pRtree, iRowid, pNode->iNode);
2580 }
2581
2582 static int SplitNode(
2583 Rtree *pRtree,
2584 RtreeNode *pNode,
2585 RtreeCell *pCell,
2586 int iHeight
2587 ){
2588 int i;
2589 int newCellIsRight = 0;
2590
2591 int rc = SQLITE_OK;
2592 int nCell = NCELL(pNode);
2593 RtreeCell *aCell;
2594 int *aiUsed;
2595
2596 RtreeNode *pLeft = 0;
2597 RtreeNode *pRight = 0;
2598
2599 RtreeCell leftbbox;
2600 RtreeCell rightbbox;
2601
2602 /* Allocate an array and populate it with a copy of pCell and
2603 ** all cells from node pLeft. Then zero the original node.
2604 */
2605 aCell = sqlite3_malloc64((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
2606 if( !aCell ){
2607 rc = SQLITE_NOMEM;
2608 goto splitnode_out;
2609 }
2610 aiUsed = (int *)&aCell[nCell+1];
2611 memset(aiUsed, 0, sizeof(int)*(nCell+1));
2612 for(i=0; i<nCell; i++){
2613 nodeGetCell(pRtree, pNode, i, &aCell[i]);
2614 }
2615 nodeZero(pRtree, pNode);
2616 memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
2617 nCell++;
2618
2619 if( pNode->iNode==1 ){
2620 pRight = nodeNew(pRtree, pNode);
2621 pLeft = nodeNew(pRtree, pNode);
2622 pRtree->iDepth++;
2623 pNode->isDirty = 1;
2624 writeInt16(pNode->zData, pRtree->iDepth);
2625 }else{
2626 pLeft = pNode;
2627 pRight = nodeNew(pRtree, pLeft->pParent);
2628 pLeft->nRef++;
2629 }
2630
2631 if( !pLeft || !pRight ){
2632 rc = SQLITE_NOMEM;
2633 goto splitnode_out;
2634 }
2635
2636 memset(pLeft->zData, 0, pRtree->iNodeSize);
2637 memset(pRight->zData, 0, pRtree->iNodeSize);
2638
2639 rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
2640 &leftbbox, &rightbbox);
2641 if( rc!=SQLITE_OK ){
2642 goto splitnode_out;
2643 }
2644
2645 /* Ensure both child nodes have node numbers assigned to them by calling
2646 ** nodeWrite(). Node pRight always needs a node number, as it was created
2647 ** by nodeNew() above. But node pLeft sometimes already has a node number.
2648 ** In this case avoid the all to nodeWrite().
2649 */
2650 if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
2651 || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
2652 ){
2653 goto splitnode_out;
2654 }
2655
2656 rightbbox.iRowid = pRight->iNode;
2657 leftbbox.iRowid = pLeft->iNode;
2658
2659 if( pNode->iNode==1 ){
2660 rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
2661 if( rc!=SQLITE_OK ){
2662 goto splitnode_out;
2663 }
2664 }else{
2665 RtreeNode *pParent = pLeft->pParent;
2666 int iCell;
2667 rc = nodeParentIndex(pRtree, pLeft, &iCell);
2668 if( ALWAYS(rc==SQLITE_OK) ){
2669 nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
2670 rc = AdjustTree(pRtree, pParent, &leftbbox);
2671 assert( rc==SQLITE_OK );
2672 }
2673 if( NEVER(rc!=SQLITE_OK) ){
2674 goto splitnode_out;
2675 }
2676 }
2677 if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
2678 goto splitnode_out;
2679 }
2680
2681 for(i=0; i<NCELL(pRight); i++){
2682 i64 iRowid = nodeGetRowid(pRtree, pRight, i);
2683 rc = updateMapping(pRtree, iRowid, pRight, iHeight);
2684 if( iRowid==pCell->iRowid ){
2685 newCellIsRight = 1;
2686 }
2687 if( rc!=SQLITE_OK ){
2688 goto splitnode_out;
2689 }
2690 }
2691 if( pNode->iNode==1 ){
2692 for(i=0; i<NCELL(pLeft); i++){
2693 i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
2694 rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
2695 if( rc!=SQLITE_OK ){
2696 goto splitnode_out;
2697 }
2698 }
2699 }else if( newCellIsRight==0 ){
2700 rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
2701 }
2702
2703 splitnode_out:
2704 nodeRelease(pRtree, pRight);
2705 nodeRelease(pRtree, pLeft);
2706 sqlite3_free(aCell);
2707 return rc;
2708 }
2709
2710 /*
2711 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2712 ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2713 ** the pLeaf->pParent chain all the way up to the root node.
2714 **
2715 ** This operation is required when a row is deleted (or updated - an update
2716 ** is implemented as a delete followed by an insert). SQLite provides the
2717 ** rowid of the row to delete, which can be used to find the leaf on which
2718 ** the entry resides (argument pLeaf). Once the leaf is located, this
2719 ** function is called to determine its ancestry.
2720 */
2721 static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
2722 int rc = SQLITE_OK;
2723 RtreeNode *pChild = pLeaf;
2724 while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
2725 int rc2 = SQLITE_OK; /* sqlite3_reset() return code */
2726 sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
2727 rc = sqlite3_step(pRtree->pReadParent);
2728 if( rc==SQLITE_ROW ){
2729 RtreeNode *pTest; /* Used to test for reference loops */
2730 i64 iNode; /* Node number of parent node */
2731
2732 /* Before setting pChild->pParent, test that we are not creating a
2733 ** loop of references (as we would if, say, pChild==pParent). We don't
2734 ** want to do this as it leads to a memory leak when trying to delete
2735 ** the referenced counted node structures.
2736 */
2737 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
2738 for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
2739 if( pTest==0 ){
2740 rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
2741 }
2742 }
2743 rc = sqlite3_reset(pRtree->pReadParent);
2744 if( rc==SQLITE_OK ) rc = rc2;
2745 if( rc==SQLITE_OK && !pChild->pParent ){
2746 RTREE_IS_CORRUPT(pRtree);
2747 rc = SQLITE_CORRUPT_VTAB;
2748 }
2749 pChild = pChild->pParent;
2750 }
2751 return rc;
2752 }
2753
2754 static int deleteCell(Rtree *, RtreeNode *, int, int);
2755
2756 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
2757 int rc;
2758 int rc2;
2759 RtreeNode *pParent = 0;
2760 int iCell;
2761
2762 assert( pNode->nRef==1 );
2763
2764 /* Remove the entry in the parent cell. */
2765 rc = nodeParentIndex(pRtree, pNode, &iCell);
2766 if( rc==SQLITE_OK ){
2767 pParent = pNode->pParent;
2768 pNode->pParent = 0;
2769 rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
2770 testcase( rc!=SQLITE_OK );
2771 }
2772 rc2 = nodeRelease(pRtree, pParent);
2773 if( rc==SQLITE_OK ){
2774 rc = rc2;
2775 }
2776 if( rc!=SQLITE_OK ){
2777 return rc;
2778 }
2779
2780 /* Remove the xxx_node entry. */
2781 sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
2782 sqlite3_step(pRtree->pDeleteNode);
2783 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
2784 return rc;
2785 }
2786
2787 /* Remove the xxx_parent entry. */
2788 sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
2789 sqlite3_step(pRtree->pDeleteParent);
2790 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
2791 return rc;
2792 }
2793
2794 /* Remove the node from the in-memory hash table and link it into
2795 ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2796 */
2797 nodeHashDelete(pRtree, pNode);
2798 pNode->iNode = iHeight;
2799 pNode->pNext = pRtree->pDeleted;
2800 pNode->nRef++;
2801 pRtree->pDeleted = pNode;
2802
2803 return SQLITE_OK;
2804 }
2805
2806 static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
2807 RtreeNode *pParent = pNode->pParent;
2808 int rc = SQLITE_OK;
2809 if( pParent ){
2810 int ii;
2811 int nCell = NCELL(pNode);
2812 RtreeCell box; /* Bounding box for pNode */
2813 nodeGetCell(pRtree, pNode, 0, &box);
2814 for(ii=1; ii<nCell; ii++){
2815 RtreeCell cell;
2816 nodeGetCell(pRtree, pNode, ii, &cell);
2817 cellUnion(pRtree, &box, &cell);
2818 }
2819 box.iRowid = pNode->iNode;
2820 rc = nodeParentIndex(pRtree, pNode, &ii);
2821 if( rc==SQLITE_OK ){
2822 nodeOverwriteCell(pRtree, pParent, &box, ii);
2823 rc = fixBoundingBox(pRtree, pParent);
2824 }
2825 }
2826 return rc;
2827 }
2828
2829 /*
2830 ** Delete the cell at index iCell of node pNode. After removing the
2831 ** cell, adjust the r-tree data structure if required.
2832 */
2833 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
2834 RtreeNode *pParent;
2835 int rc;
2836
2837 if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
2838 return rc;
2839 }
2840
2841 /* Remove the cell from the node. This call just moves bytes around
2842 ** the in-memory node image, so it cannot fail.
2843 */
2844 nodeDeleteCell(pRtree, pNode, iCell);
2845
2846 /* If the node is not the tree root and now has less than the minimum
2847 ** number of cells, remove it from the tree. Otherwise, update the
2848 ** cell in the parent node so that it tightly contains the updated
2849 ** node.
2850 */
2851 pParent = pNode->pParent;
2852 assert( pParent || pNode->iNode==1 );
2853 if( pParent ){
2854 if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
2855 rc = removeNode(pRtree, pNode, iHeight);
2856 }else{
2857 rc = fixBoundingBox(pRtree, pNode);
2858 }
2859 }
2860
2861 return rc;
2862 }
2863
2864 /*
2865 ** Insert cell pCell into node pNode. Node pNode is the head of a
2866 ** subtree iHeight high (leaf nodes have iHeight==0).
2867 */
2868 static int rtreeInsertCell(
2869 Rtree *pRtree,
2870 RtreeNode *pNode,
2871 RtreeCell *pCell,
2872 int iHeight
2873 ){
2874 int rc = SQLITE_OK;
2875 if( iHeight>0 ){
2876 RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
2877 if( pChild ){
2878 nodeRelease(pRtree, pChild->pParent);
2879 nodeReference(pNode);
2880 pChild->pParent = pNode;
2881 }
2882 }
2883 if( nodeInsertCell(pRtree, pNode, pCell) ){
2884 rc = SplitNode(pRtree, pNode, pCell, iHeight);
2885 }else{
2886 rc = AdjustTree(pRtree, pNode, pCell);
2887 if( rc==SQLITE_OK ){
2888 if( iHeight==0 ){
2889 rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
2890 }else{
2891 rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
2892 }
2893 }
2894 }
2895 return rc;
2896 }
2897
2898 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
2899 int ii;
2900 int rc = SQLITE_OK;
2901 int nCell = NCELL(pNode);
2902
2903 for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
2904 RtreeNode *pInsert;
2905 RtreeCell cell;
2906 nodeGetCell(pRtree, pNode, ii, &cell);
2907
2908 /* Find a node to store this cell in. pNode->iNode currently contains
2909 ** the height of the sub-tree headed by the cell.
2910 */
2911 rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert);
2912 if( rc==SQLITE_OK ){
2913 int rc2;
2914 rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode);
2915 rc2 = nodeRelease(pRtree, pInsert);
2916 if( rc==SQLITE_OK ){
2917 rc = rc2;
2918 }
2919 }
2920 }
2921 return rc;
2922 }
2923
2924 /*
2925 ** Select a currently unused rowid for a new r-tree record.
2926 */
2927 static int rtreeNewRowid(Rtree *pRtree, i64 *piRowid){
2928 int rc;
2929 sqlite3_bind_null(pRtree->pWriteRowid, 1);
2930 sqlite3_bind_null(pRtree->pWriteRowid, 2);
2931 sqlite3_step(pRtree->pWriteRowid);
2932 rc = sqlite3_reset(pRtree->pWriteRowid);
2933 *piRowid = sqlite3_last_insert_rowid(pRtree->db);
2934 return rc;
2935 }
2936
2937 /*
2938 ** Remove the entry with rowid=iDelete from the r-tree structure.
2939 */
2940 static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){
2941 int rc; /* Return code */
2942 RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */
2943 int iCell; /* Index of iDelete cell in pLeaf */
2944 RtreeNode *pRoot = 0; /* Root node of rtree structure */
2945
2946
2947 /* Obtain a reference to the root node to initialize Rtree.iDepth */
2948 rc = nodeAcquire(pRtree, 1, 0, &pRoot);
2949
2950 /* Obtain a reference to the leaf node that contains the entry
2951 ** about to be deleted.
2952 */
2953 if( rc==SQLITE_OK ){
2954 rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
2955 }
2956
2957 #ifdef CORRUPT_DB
2958 assert( pLeaf!=0 || rc!=SQLITE_OK || CORRUPT_DB );
2959 #endif
2960
2961 /* Delete the cell in question from the leaf node. */
2962 if( rc==SQLITE_OK && pLeaf ){
2963 int rc2;
2964 rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
2965 if( rc==SQLITE_OK ){
2966 rc = deleteCell(pRtree, pLeaf, iCell, 0);
2967 }
2968 rc2 = nodeRelease(pRtree, pLeaf);
2969 if( rc==SQLITE_OK ){
2970 rc = rc2;
2971 }
2972 }
2973
2974 /* Delete the corresponding entry in the <rtree>_rowid table. */
2975 if( rc==SQLITE_OK ){
2976 sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
2977 sqlite3_step(pRtree->pDeleteRowid);
2978 rc = sqlite3_reset(pRtree->pDeleteRowid);
2979 }
2980
2981 /* Check if the root node now has exactly one child. If so, remove
2982 ** it, schedule the contents of the child for reinsertion and
2983 ** reduce the tree height by one.
2984 **
2985 ** This is equivalent to copying the contents of the child into
2986 ** the root node (the operation that Gutman's paper says to perform
2987 ** in this scenario).
2988 */
2989 if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){
2990 int rc2;
2991 RtreeNode *pChild = 0;
2992 i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
2993 rc = nodeAcquire(pRtree, iChild, pRoot, &pChild); /* tag-20210916a */
2994 if( rc==SQLITE_OK ){
2995 rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
2996 }
2997 rc2 = nodeRelease(pRtree, pChild);
2998 if( rc==SQLITE_OK ) rc = rc2;
2999 if( rc==SQLITE_OK ){
3000 pRtree->iDepth--;
3001 writeInt16(pRoot->zData, pRtree->iDepth);
3002 pRoot->isDirty = 1;
3003 }
3004 }
3005
3006 /* Re-insert the contents of any underfull nodes removed from the tree. */
3007 for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
3008 if( rc==SQLITE_OK ){
3009 rc = reinsertNodeContent(pRtree, pLeaf);
3010 }
3011 pRtree->pDeleted = pLeaf->pNext;
3012 pRtree->nNodeRef--;
3013 sqlite3_free(pLeaf);
3014 }
3015
3016 /* Release the reference to the root node. */
3017 if( rc==SQLITE_OK ){
3018 rc = nodeRelease(pRtree, pRoot);
3019 }else{
3020 nodeRelease(pRtree, pRoot);
3021 }
3022
3023 return rc;
3024 }
3025
3026 /*
3027 ** Rounding constants for float->double conversion.
3028 */
3029 #define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */
3030 #define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */
3031
3032 #if !defined(SQLITE_RTREE_INT_ONLY)
3033 /*
3034 ** Convert an sqlite3_value into an RtreeValue (presumably a float)
3035 ** while taking care to round toward negative or positive, respectively.
3036 */
3037 static RtreeValue rtreeValueDown(sqlite3_value *v){
3038 double d = sqlite3_value_double(v);
3039 float f = (float)d;
3040 if( f>d ){
3041 f = (float)(d*(d<0 ? RNDAWAY : RNDTOWARDS));
3042 }
3043 return f;
3044 }
3045 static RtreeValue rtreeValueUp(sqlite3_value *v){
3046 double d = sqlite3_value_double(v);
3047 float f = (float)d;
3048 if( f<d ){
3049 f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY));
3050 }
3051 return f;
3052 }
3053 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */
3054
3055 /*
3056 ** A constraint has failed while inserting a row into an rtree table.
3057 ** Assuming no OOM error occurs, this function sets the error message
3058 ** (at pRtree->base.zErrMsg) to an appropriate value and returns
3059 ** SQLITE_CONSTRAINT.
3060 **
3061 ** Parameter iCol is the index of the leftmost column involved in the
3062 ** constraint failure. If it is 0, then the constraint that failed is
3063 ** the unique constraint on the id column. Otherwise, it is the rtree
3064 ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed.
3065 **
3066 ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT.
3067 */
3068 static int rtreeConstraintError(Rtree *pRtree, int iCol){
3069 sqlite3_stmt *pStmt = 0;
3070 char *zSql;
3071 int rc;
3072
3073 assert( iCol==0 || iCol%2 );
3074 zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree->zDb, pRtree->zName);
3075 if( zSql ){
3076 rc = sqlite3_prepare_v2(pRtree->db, zSql, -1, &pStmt, 0);
3077 }else{
3078 rc = SQLITE_NOMEM;
3079 }
3080 sqlite3_free(zSql);
3081
3082 if( rc==SQLITE_OK ){
3083 if( iCol==0 ){
3084 const char *zCol = sqlite3_column_name(pStmt, 0);
3085 pRtree->base.zErrMsg = sqlite3_mprintf(
3086 "UNIQUE constraint failed: %s.%s", pRtree->zName, zCol
3087 );
3088 }else{
3089 const char *zCol1 = sqlite3_column_name(pStmt, iCol);
3090 const char *zCol2 = sqlite3_column_name(pStmt, iCol+1);
3091 pRtree->base.zErrMsg = sqlite3_mprintf(
3092 "rtree constraint failed: %s.(%s<=%s)", pRtree->zName, zCol1, zCol2
3093 );
3094 }
3095 }
3096
3097 sqlite3_finalize(pStmt);
3098 return (rc==SQLITE_OK ? SQLITE_CONSTRAINT : rc);
3099 }
3100
3101
3102
3103 /*
3104 ** The xUpdate method for rtree module virtual tables.
3105 */
3106 static int rtreeUpdate(
3107 sqlite3_vtab *pVtab,
3108 int nData,
3109 sqlite3_value **aData,
3110 sqlite_int64 *pRowid
3111 ){
3112 Rtree *pRtree = (Rtree *)pVtab;
3113 int rc = SQLITE_OK;
3114 RtreeCell cell; /* New cell to insert if nData>1 */
3115 int bHaveRowid = 0; /* Set to 1 after new rowid is determined */
3116
3117 if( pRtree->nNodeRef ){
3118 /* Unable to write to the btree while another cursor is reading from it,
3119 ** since the write might do a rebalance which would disrupt the read
3120 ** cursor. */
3121 return SQLITE_LOCKED_VTAB;
3122 }
3123 rtreeReference(pRtree);
3124 assert(nData>=1);
3125
3126 memset(&cell, 0, sizeof(cell));
3127
3128 /* Constraint handling. A write operation on an r-tree table may return
3129 ** SQLITE_CONSTRAINT for two reasons:
3130 **
3131 ** 1. A duplicate rowid value, or
3132 ** 2. The supplied data violates the "x2>=x1" constraint.
3133 **
3134 ** In the first case, if the conflict-handling mode is REPLACE, then
3135 ** the conflicting row can be removed before proceeding. In the second
3136 ** case, SQLITE_CONSTRAINT must be returned regardless of the
3137 ** conflict-handling mode specified by the user.
3138 */
3139 if( nData>1 ){
3140 int ii;
3141 int nn = nData - 4;
3142
3143 if( nn > pRtree->nDim2 ) nn = pRtree->nDim2;
3144 /* Populate the cell.aCoord[] array. The first coordinate is aData[3].
3145 **
3146 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
3147 ** with "column" that are interpreted as table constraints.
3148 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
3149 ** This problem was discovered after years of use, so we silently ignore
3150 ** these kinds of misdeclared tables to avoid breaking any legacy.
3151 */
3152
3153 #ifndef SQLITE_RTREE_INT_ONLY
3154 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
3155 for(ii=0; ii<nn; ii+=2){
3156 cell.aCoord[ii].f = rtreeValueDown(aData[ii+3]);
3157 cell.aCoord[ii+1].f = rtreeValueUp(aData[ii+4]);
3158 if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
3159 rc = rtreeConstraintError(pRtree, ii+1);
3160 goto constraint;
3161 }
3162 }
3163 }else
3164 #endif
3165 {
3166 for(ii=0; ii<nn; ii+=2){
3167 cell.aCoord[ii].i = sqlite3_value_int(aData[ii+3]);
3168 cell.aCoord[ii+1].i = sqlite3_value_int(aData[ii+4]);
3169 if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
3170 rc = rtreeConstraintError(pRtree, ii+1);
3171 goto constraint;
3172 }
3173 }
3174 }
3175
3176 /* If a rowid value was supplied, check if it is already present in
3177 ** the table. If so, the constraint has failed. */
3178 if( sqlite3_value_type(aData[2])!=SQLITE_NULL ){
3179 cell.iRowid = sqlite3_value_int64(aData[2]);
3180 if( sqlite3_value_type(aData[0])==SQLITE_NULL
3181 || sqlite3_value_int64(aData[0])!=cell.iRowid
3182 ){
3183 int steprc;
3184 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
3185 steprc = sqlite3_step(pRtree->pReadRowid);
3186 rc = sqlite3_reset(pRtree->pReadRowid);
3187 if( SQLITE_ROW==steprc ){
3188 if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){
3189 rc = rtreeDeleteRowid(pRtree, cell.iRowid);
3190 }else{
3191 rc = rtreeConstraintError(pRtree, 0);
3192 goto constraint;
3193 }
3194 }
3195 }
3196 bHaveRowid = 1;
3197 }
3198 }
3199
3200 /* If aData[0] is not an SQL NULL value, it is the rowid of a
3201 ** record to delete from the r-tree table. The following block does
3202 ** just that.
3203 */
3204 if( sqlite3_value_type(aData[0])!=SQLITE_NULL ){
3205 rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0]));
3206 }
3207
3208 /* If the aData[] array contains more than one element, elements
3209 ** (aData[2]..aData[argc-1]) contain a new record to insert into
3210 ** the r-tree structure.
3211 */
3212 if( rc==SQLITE_OK && nData>1 ){
3213 /* Insert the new record into the r-tree */
3214 RtreeNode *pLeaf = 0;
3215
3216 /* Figure out the rowid of the new row. */
3217 if( bHaveRowid==0 ){
3218 rc = rtreeNewRowid(pRtree, &cell.iRowid);
3219 }
3220 *pRowid = cell.iRowid;
3221
3222 if( rc==SQLITE_OK ){
3223 rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
3224 }
3225 if( rc==SQLITE_OK ){
3226 int rc2;
3227 rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
3228 rc2 = nodeRelease(pRtree, pLeaf);
3229 if( rc==SQLITE_OK ){
3230 rc = rc2;
3231 }
3232 }
3233 if( rc==SQLITE_OK && pRtree->nAux ){
3234 sqlite3_stmt *pUp = pRtree->pWriteAux;
3235 int jj;
3236 sqlite3_bind_int64(pUp, 1, *pRowid);
3237 for(jj=0; jj<pRtree->nAux; jj++){
3238 sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]);
3239 }
3240 sqlite3_step(pUp);
3241 rc = sqlite3_reset(pUp);
3242 }
3243 }
3244
3245 constraint:
3246 rtreeRelease(pRtree);
3247 return rc;
3248 }
3249
3250 /*
3251 ** Called when a transaction starts.
3252 */
3253 static int rtreeBeginTransaction(sqlite3_vtab *pVtab){
3254 Rtree *pRtree = (Rtree *)pVtab;
3255 assert( pRtree->inWrTrans==0 );
3256 pRtree->inWrTrans = 1;
3257 return SQLITE_OK;
3258 }
3259
3260 /*
3261 ** Called when a transaction completes (either by COMMIT or ROLLBACK).
3262 ** The sqlite3_blob object should be released at this point.
3263 */
3264 static int rtreeEndTransaction(sqlite3_vtab *pVtab){
3265 Rtree *pRtree = (Rtree *)pVtab;
3266 pRtree->inWrTrans = 0;
3267 nodeBlobReset(pRtree);
3268 return SQLITE_OK;
3269 }
3270 static int rtreeRollback(sqlite3_vtab *pVtab){
3271 return rtreeEndTransaction(pVtab);
3272 }
3273
3274 /*
3275 ** The xRename method for rtree module virtual tables.
3276 */
3277 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
3278 Rtree *pRtree = (Rtree *)pVtab;
3279 int rc = SQLITE_NOMEM;
3280 char *zSql = sqlite3_mprintf(
3281 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
3282 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
3283 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
3284 , pRtree->zDb, pRtree->zName, zNewName
3285 , pRtree->zDb, pRtree->zName, zNewName
3286 , pRtree->zDb, pRtree->zName, zNewName
3287 );
3288 if( zSql ){
3289 nodeBlobReset(pRtree);
3290 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
3291 sqlite3_free(zSql);
3292 }
3293 return rc;
3294 }
3295
3296 /*
3297 ** The xSavepoint method.
3298 **
3299 ** This module does not need to do anything to support savepoints. However,
3300 ** it uses this hook to close any open blob handle. This is done because a
3301 ** DROP TABLE command - which fortunately always opens a savepoint - cannot
3302 ** succeed if there are any open blob handles. i.e. if the blob handle were
3303 ** not closed here, the following would fail:
3304 **
3305 ** BEGIN;
3306 ** INSERT INTO rtree...
3307 ** DROP TABLE <tablename>; -- Would fail with SQLITE_LOCKED
3308 ** COMMIT;
3309 */
3310 static int rtreeSavepoint(sqlite3_vtab *pVtab, int iSavepoint){
3311 Rtree *pRtree = (Rtree *)pVtab;
3312 u8 iwt = pRtree->inWrTrans;
3313 UNUSED_PARAMETER(iSavepoint);
3314 pRtree->inWrTrans = 0;
3315 nodeBlobReset(pRtree);
3316 pRtree->inWrTrans = iwt;
3317 return SQLITE_OK;
3318 }
3319
3320 /*
3321 ** This function populates the pRtree->nRowEst variable with an estimate
3322 ** of the number of rows in the virtual table. If possible, this is based
3323 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
3324 */
3325 static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){
3326 const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
3327 char *zSql;
3328 sqlite3_stmt *p;
3329 int rc;
3330 i64 nRow = RTREE_MIN_ROWEST;
3331
3332 rc = sqlite3_table_column_metadata(
3333 db, pRtree->zDb, "sqlite_stat1",0,0,0,0,0,0
3334 );
3335 if( rc!=SQLITE_OK ){
3336 pRtree->nRowEst = RTREE_DEFAULT_ROWEST;
3337 return rc==SQLITE_ERROR ? SQLITE_OK : rc;
3338 }
3339 zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName);
3340 if( zSql==0 ){
3341 rc = SQLITE_NOMEM;
3342 }else{
3343 rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0);
3344 if( rc==SQLITE_OK ){
3345 if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0);
3346 rc = sqlite3_finalize(p);
3347 }
3348 sqlite3_free(zSql);
3349 }
3350 pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST);
3351 return rc;
3352 }
3353
3354
3355 /*
3356 ** Return true if zName is the extension on one of the shadow tables used
3357 ** by this module.
3358 */
3359 static int rtreeShadowName(const char *zName){
3360 static const char *azName[] = {
3361 "node", "parent", "rowid"
3362 };
3363 unsigned int i;
3364 for(i=0; i<sizeof(azName)/sizeof(azName[0]); i++){
3365 if( sqlite3_stricmp(zName, azName[i])==0 ) return 1;
3366 }
3367 return 0;
3368 }
3369
3370 /* Forward declaration */
3371 static int rtreeIntegrity(sqlite3_vtab*, const char*, const char*, int, char**);
3372
3373 static sqlite3_module rtreeModule = {
3374 4, /* iVersion */
3375 rtreeCreate, /* xCreate - create a table */
3376 rtreeConnect, /* xConnect - connect to an existing table */
3377 rtreeBestIndex, /* xBestIndex - Determine search strategy */
3378 rtreeDisconnect, /* xDisconnect - Disconnect from a table */
3379 rtreeDestroy, /* xDestroy - Drop a table */
3380 rtreeOpen, /* xOpen - open a cursor */
3381 rtreeClose, /* xClose - close a cursor */
3382 rtreeFilter, /* xFilter - configure scan constraints */
3383 rtreeNext, /* xNext - advance a cursor */
3384 rtreeEof, /* xEof */
3385 rtreeColumn, /* xColumn - read data */
3386 rtreeRowid, /* xRowid - read data */
3387 rtreeUpdate, /* xUpdate - write data */
3388 rtreeBeginTransaction, /* xBegin - begin transaction */
3389 rtreeEndTransaction, /* xSync - sync transaction */
3390 rtreeEndTransaction, /* xCommit - commit transaction */
3391 rtreeRollback, /* xRollback - rollback transaction */
3392 0, /* xFindFunction - function overloading */
3393 rtreeRename, /* xRename - rename the table */
3394 rtreeSavepoint, /* xSavepoint */
3395 0, /* xRelease */
3396 0, /* xRollbackTo */
3397 rtreeShadowName, /* xShadowName */
3398 rtreeIntegrity /* xIntegrity */
3399 };
3400
3401 static int rtreeSqlInit(
3402 Rtree *pRtree,
3403 sqlite3 *db,
3404 const char *zDb,
3405 const char *zPrefix,
3406 int isCreate
3407 ){
3408 int rc = SQLITE_OK;
3409
3410 #define N_STATEMENT 8
3411 static const char *azSql[N_STATEMENT] = {
3412 /* Write the xxx_node table */
3413 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(?1, ?2)",
3414 "DELETE FROM '%q'.'%q_node' WHERE nodeno = ?1",
3415
3416 /* Read and write the xxx_rowid table */
3417 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3418 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(?1, ?2)",
3419 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = ?1",
3420
3421 /* Read and write the xxx_parent table */
3422 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = ?1",
3423 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(?1, ?2)",
3424 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = ?1"
3425 };
3426 sqlite3_stmt **appStmt[N_STATEMENT];
3427 int i;
3428 const int f = SQLITE_PREPARE_PERSISTENT|SQLITE_PREPARE_NO_VTAB;
3429
3430 pRtree->db = db;
3431
3432 if( isCreate ){
3433 char *zCreate;
3434 sqlite3_str *p = sqlite3_str_new(db);
3435 int ii;
3436 sqlite3_str_appendf(p,
3437 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY,nodeno",
3438 zDb, zPrefix);
3439 for(ii=0; ii<pRtree->nAux; ii++){
3440 sqlite3_str_appendf(p,",a%d",ii);
3441 }
3442 sqlite3_str_appendf(p,
3443 ");CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY,data);",
3444 zDb, zPrefix);
3445 sqlite3_str_appendf(p,
3446 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,parentnode);",
3447 zDb, zPrefix);
3448 sqlite3_str_appendf(p,
3449 "INSERT INTO \"%w\".\"%w_node\"VALUES(1,zeroblob(%d))",
3450 zDb, zPrefix, pRtree->iNodeSize);
3451 zCreate = sqlite3_str_finish(p);
3452 if( !zCreate ){
3453 return SQLITE_NOMEM;
3454 }
3455 rc = sqlite3_exec(db, zCreate, 0, 0, 0);
3456 sqlite3_free(zCreate);
3457 if( rc!=SQLITE_OK ){
3458 return rc;
3459 }
3460 }
3461
3462 appStmt[0] = &pRtree->pWriteNode;
3463 appStmt[1] = &pRtree->pDeleteNode;
3464 appStmt[2] = &pRtree->pReadRowid;
3465 appStmt[3] = &pRtree->pWriteRowid;
3466 appStmt[4] = &pRtree->pDeleteRowid;
3467 appStmt[5] = &pRtree->pReadParent;
3468 appStmt[6] = &pRtree->pWriteParent;
3469 appStmt[7] = &pRtree->pDeleteParent;
3470
3471 rc = rtreeQueryStat1(db, pRtree);
3472 for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
3473 char *zSql;
3474 const char *zFormat;
3475 if( i!=3 || pRtree->nAux==0 ){
3476 zFormat = azSql[i];
3477 }else {
3478 /* An UPSERT is very slightly slower than REPLACE, but it is needed
3479 ** if there are auxiliary columns */
3480 zFormat = "INSERT INTO\"%w\".\"%w_rowid\"(rowid,nodeno)VALUES(?1,?2)"
3481 "ON CONFLICT(rowid)DO UPDATE SET nodeno=excluded.nodeno";
3482 }
3483 zSql = sqlite3_mprintf(zFormat, zDb, zPrefix);
3484 if( zSql ){
3485 rc = sqlite3_prepare_v3(db, zSql, -1, f, appStmt[i], 0);
3486 }else{
3487 rc = SQLITE_NOMEM;
3488 }
3489 sqlite3_free(zSql);
3490 }
3491 if( pRtree->nAux && rc!=SQLITE_NOMEM ){
3492 pRtree->zReadAuxSql = sqlite3_mprintf(
3493 "SELECT * FROM \"%w\".\"%w_rowid\" WHERE rowid=?1",
3494 zDb, zPrefix);
3495 if( pRtree->zReadAuxSql==0 ){
3496 rc = SQLITE_NOMEM;
3497 }else{
3498 sqlite3_str *p = sqlite3_str_new(db);
3499 int ii;
3500 char *zSql;
3501 sqlite3_str_appendf(p, "UPDATE \"%w\".\"%w_rowid\"SET ", zDb, zPrefix);
3502 for(ii=0; ii<pRtree->nAux; ii++){
3503 if( ii ) sqlite3_str_append(p, ",", 1);
3504 #ifdef SQLITE_ENABLE_GEOPOLY
3505 if( ii<pRtree->nAuxNotNull ){
3506 sqlite3_str_appendf(p,"a%d=coalesce(?%d,a%d)",ii,ii+2,ii);
3507 }else
3508 #endif
3509 {
3510 sqlite3_str_appendf(p,"a%d=?%d",ii,ii+2);
3511 }
3512 }
3513 sqlite3_str_appendf(p, " WHERE rowid=?1");
3514 zSql = sqlite3_str_finish(p);
3515 if( zSql==0 ){
3516 rc = SQLITE_NOMEM;
3517 }else{
3518 rc = sqlite3_prepare_v3(db, zSql, -1, f, &pRtree->pWriteAux, 0);
3519 sqlite3_free(zSql);
3520 }
3521 }
3522 }
3523
3524 return rc;
3525 }
3526
3527 /*
3528 ** The second argument to this function contains the text of an SQL statement
3529 ** that returns a single integer value. The statement is compiled and executed
3530 ** using database connection db. If successful, the integer value returned
3531 ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
3532 ** code is returned and the value of *piVal after returning is not defined.
3533 */
3534 static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){
3535 int rc = SQLITE_NOMEM;
3536 if( zSql ){
3537 sqlite3_stmt *pStmt = 0;
3538 rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
3539 if( rc==SQLITE_OK ){
3540 if( SQLITE_ROW==sqlite3_step(pStmt) ){
3541 *piVal = sqlite3_column_int(pStmt, 0);
3542 }
3543 rc = sqlite3_finalize(pStmt);
3544 }
3545 }
3546 return rc;
3547 }
3548
3549 /*
3550 ** This function is called from within the xConnect() or xCreate() method to
3551 ** determine the node-size used by the rtree table being created or connected
3552 ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
3553 ** Otherwise, an SQLite error code is returned.
3554 **
3555 ** If this function is being called as part of an xConnect(), then the rtree
3556 ** table already exists. In this case the node-size is determined by inspecting
3557 ** the root node of the tree.
3558 **
3559 ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
3560 ** This ensures that each node is stored on a single database page. If the
3561 ** database page-size is so large that more than RTREE_MAXCELLS entries
3562 ** would fit in a single node, use a smaller node-size.
3563 */
3564 static int getNodeSize(
3565 sqlite3 *db, /* Database handle */
3566 Rtree *pRtree, /* Rtree handle */
3567 int isCreate, /* True for xCreate, false for xConnect */
3568 char **pzErr /* OUT: Error message, if any */
3569 ){
3570 int rc;
3571 char *zSql;
3572 if( isCreate ){
3573 int iPageSize = 0;
3574 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
3575 rc = getIntFromStmt(db, zSql, &iPageSize);
3576 if( rc==SQLITE_OK ){
3577 pRtree->iNodeSize = iPageSize-64;
3578 if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
3579 pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
3580 }
3581 }else{
3582 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3583 }
3584 }else{
3585 zSql = sqlite3_mprintf(
3586 "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
3587 pRtree->zDb, pRtree->zName
3588 );
3589 rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
3590 if( rc!=SQLITE_OK ){
3591 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3592 }else if( pRtree->iNodeSize<(512-64) ){
3593 rc = SQLITE_CORRUPT_VTAB;
3594 RTREE_IS_CORRUPT(pRtree);
3595 *pzErr = sqlite3_mprintf("undersize RTree blobs in \"%q_node\"",
3596 pRtree->zName);
3597 }
3598 }
3599
3600 sqlite3_free(zSql);
3601 return rc;
3602 }
3603
3604 /*
3605 ** Return the length of a token
3606 */
3607 static int rtreeTokenLength(const char *z){
3608 int dummy = 0;
3609 return sqlite3GetToken((const unsigned char*)z,&dummy);
3610 }
3611
3612 /*
3613 ** This function is the implementation of both the xConnect and xCreate
3614 ** methods of the r-tree virtual table.
3615 **
3616 ** argv[0] -> module name
3617 ** argv[1] -> database name
3618 ** argv[2] -> table name
3619 ** argv[...] -> column names...
3620 */
3621 static int rtreeInit(
3622 sqlite3 *db, /* Database connection */
3623 void *pAux, /* One of the RTREE_COORD_* constants */
3624 int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */
3625 sqlite3_vtab **ppVtab, /* OUT: New virtual table */
3626 char **pzErr, /* OUT: Error message, if any */
3627 int isCreate /* True for xCreate, false for xConnect */
3628 ){
3629 int rc = SQLITE_OK;
3630 Rtree *pRtree;
3631 int nDb; /* Length of string argv[1] */
3632 int nName; /* Length of string argv[2] */
3633 int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
3634 sqlite3_str *pSql;
3635 char *zSql;
3636 int ii = 4;
3637 int iErr;
3638
3639 const char *aErrMsg[] = {
3640 0, /* 0 */
3641 "Wrong number of columns for an rtree table", /* 1 */
3642 "Too few columns for an rtree table", /* 2 */
3643 "Too many columns for an rtree table", /* 3 */
3644 "Auxiliary rtree columns must be last" /* 4 */
3645 };
3646
3647 assert( RTREE_MAX_AUX_COLUMN<256 );
3648 if( argc<6 || argc>RTREE_MAX_AUX_COLUMN+3 ){
3649 *pzErr = sqlite3_mprintf("%s", aErrMsg[2 + (argc>=6)]);
3650 return SQLITE_ERROR;
3651 }
3652
3653 sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
3654 sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
3655
3656
3657 /* Allocate the sqlite3_vtab structure */
3658 nDb = (int)strlen(argv[1]);
3659 nName = (int)strlen(argv[2]);
3660 pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName*2+8);
3661 if( !pRtree ){
3662 return SQLITE_NOMEM;
3663 }
3664 memset(pRtree, 0, sizeof(Rtree)+nDb+nName*2+8);
3665 pRtree->nBusy = 1;
3666 pRtree->base.pModule = &rtreeModule;
3667 pRtree->zDb = (char *)&pRtree[1];
3668 pRtree->zName = &pRtree->zDb[nDb+1];
3669 pRtree->zNodeName = &pRtree->zName[nName+1];
3670 pRtree->eCoordType = (u8)eCoordType;
3671 memcpy(pRtree->zDb, argv[1], nDb);
3672 memcpy(pRtree->zName, argv[2], nName);
3673 memcpy(pRtree->zNodeName, argv[2], nName);
3674 memcpy(&pRtree->zNodeName[nName], "_node", 6);
3675
3676
3677 /* Create/Connect to the underlying relational database schema. If
3678 ** that is successful, call sqlite3_declare_vtab() to configure
3679 ** the r-tree table schema.
3680 */
3681 pSql = sqlite3_str_new(db);
3682 sqlite3_str_appendf(pSql, "CREATE TABLE x(%.*s INT",
3683 rtreeTokenLength(argv[3]), argv[3]);
3684 for(ii=4; ii<argc; ii++){
3685 const char *zArg = argv[ii];
3686 if( zArg[0]=='+' ){
3687 pRtree->nAux++;
3688 sqlite3_str_appendf(pSql, ",%.*s", rtreeTokenLength(zArg+1), zArg+1);
3689 }else if( pRtree->nAux>0 ){
3690 break;
3691 }else{
3692 static const char *azFormat[] = {",%.*s REAL", ",%.*s INT"};
3693 pRtree->nDim2++;
3694 sqlite3_str_appendf(pSql, azFormat[eCoordType],
3695 rtreeTokenLength(zArg), zArg);
3696 }
3697 }
3698 sqlite3_str_appendf(pSql, ");");
3699 zSql = sqlite3_str_finish(pSql);
3700 if( !zSql ){
3701 rc = SQLITE_NOMEM;
3702 }else if( ii<argc ){
3703 *pzErr = sqlite3_mprintf("%s", aErrMsg[4]);
3704 rc = SQLITE_ERROR;
3705 }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
3706 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3707 }
3708 sqlite3_free(zSql);
3709 if( rc ) goto rtreeInit_fail;
3710 pRtree->nDim = pRtree->nDim2/2;
3711 if( pRtree->nDim<1 ){
3712 iErr = 2;
3713 }else if( pRtree->nDim2>RTREE_MAX_DIMENSIONS*2 ){
3714 iErr = 3;
3715 }else if( pRtree->nDim2 % 2 ){
3716 iErr = 1;
3717 }else{
3718 iErr = 0;
3719 }
3720 if( iErr ){
3721 *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
3722 goto rtreeInit_fail;
3723 }
3724 pRtree->nBytesPerCell = 8 + pRtree->nDim2*4;
3725
3726 /* Figure out the node size to use. */
3727 rc = getNodeSize(db, pRtree, isCreate, pzErr);
3728 if( rc ) goto rtreeInit_fail;
3729 rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate);
3730 if( rc ){
3731 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3732 goto rtreeInit_fail;
3733 }
3734
3735 *ppVtab = (sqlite3_vtab *)pRtree;
3736 return SQLITE_OK;
3737
3738 rtreeInit_fail:
3739 if( rc==SQLITE_OK ) rc = SQLITE_ERROR;
3740 assert( *ppVtab==0 );
3741 assert( pRtree->nBusy==1 );
3742 rtreeRelease(pRtree);
3743 return rc;
3744 }
3745
3746
3747 /*
3748 ** Implementation of a scalar function that decodes r-tree nodes to
3749 ** human readable strings. This can be used for debugging and analysis.
3750 **
3751 ** The scalar function takes two arguments: (1) the number of dimensions
3752 ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
3753 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
3754 ** deserialize all nodes, a statement like:
3755 **
3756 ** SELECT rtreenode(2, data) FROM rt_node;
3757 **
3758 ** The human readable string takes the form of a Tcl list with one
3759 ** entry for each cell in the r-tree node. Each entry is itself a
3760 ** list, containing the 8-byte rowid/pageno followed by the
3761 ** <num-dimension>*2 coordinates.
3762 */
3763 static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3764 RtreeNode node;
3765 Rtree tree;
3766 int ii;
3767 int nData;
3768 int errCode;
3769 sqlite3_str *pOut;
3770
3771 UNUSED_PARAMETER(nArg);
3772 memset(&node, 0, sizeof(RtreeNode));
3773 memset(&tree, 0, sizeof(Rtree));
3774 tree.nDim = (u8)sqlite3_value_int(apArg[0]);
3775 if( tree.nDim<1 || tree.nDim>5 ) return;
3776 tree.nDim2 = tree.nDim*2;
3777 tree.nBytesPerCell = 8 + 8 * tree.nDim;
3778 node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
3779 if( node.zData==0 ) return;
3780 nData = sqlite3_value_bytes(apArg[1]);
3781 if( nData<4 ) return;
3782 if( nData<4+NCELL(&node)*tree.nBytesPerCell ) return;
3783
3784 pOut = sqlite3_str_new(0);
3785 for(ii=0; ii<NCELL(&node); ii++){
3786 RtreeCell cell;
3787 int jj;
3788
3789 nodeGetCell(&tree, &node, ii, &cell);
3790 if( ii>0 ) sqlite3_str_append(pOut, " ", 1);
3791 sqlite3_str_appendf(pOut, "{%lld", cell.iRowid);
3792 for(jj=0; jj<tree.nDim2; jj++){
3793 #ifndef SQLITE_RTREE_INT_ONLY
3794 sqlite3_str_appendf(pOut, " %g", (double)cell.aCoord[jj].f);
3795 #else
3796 sqlite3_str_appendf(pOut, " %d", cell.aCoord[jj].i);
3797 #endif
3798 }
3799 sqlite3_str_append(pOut, "}", 1);
3800 }
3801 errCode = sqlite3_str_errcode(pOut);
3802 sqlite3_result_error_code(ctx, errCode);
3803 sqlite3_result_text(ctx, sqlite3_str_finish(pOut), -1, sqlite3_free);
3804 }
3805
3806 /* This routine implements an SQL function that returns the "depth" parameter
3807 ** from the front of a blob that is an r-tree node. For example:
3808 **
3809 ** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
3810 **
3811 ** The depth value is 0 for all nodes other than the root node, and the root
3812 ** node always has nodeno=1, so the example above is the primary use for this
3813 ** routine. This routine is intended for testing and analysis only.
3814 */
3815 static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3816 UNUSED_PARAMETER(nArg);
3817 if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB
3818 || sqlite3_value_bytes(apArg[0])<2
3819
3820 ){
3821 sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1);
3822 }else{
3823 u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
3824 if( zBlob ){
3825 sqlite3_result_int(ctx, readInt16(zBlob));
3826 }else{
3827 sqlite3_result_error_nomem(ctx);
3828 }
3829 }
3830 }
3831
3832 /*
3833 ** Context object passed between the various routines that make up the
3834 ** implementation of integrity-check function rtreecheck().
3835 */
3836 typedef struct RtreeCheck RtreeCheck;
3837 struct RtreeCheck {
3838 sqlite3 *db; /* Database handle */
3839 const char *zDb; /* Database containing rtree table */
3840 const char *zTab; /* Name of rtree table */
3841 int bInt; /* True for rtree_i32 table */
3842 int nDim; /* Number of dimensions for this rtree tbl */
3843 sqlite3_stmt *pGetNode; /* Statement used to retrieve nodes */
3844 sqlite3_stmt *aCheckMapping[2]; /* Statements to query %_parent/%_rowid */
3845 int nLeaf; /* Number of leaf cells in table */
3846 int nNonLeaf; /* Number of non-leaf cells in table */
3847 int rc; /* Return code */
3848 char *zReport; /* Message to report */
3849 int nErr; /* Number of lines in zReport */
3850 };
3851
3852 #define RTREE_CHECK_MAX_ERROR 100
3853
3854 /*
3855 ** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
3856 ** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
3857 */
3858 static void rtreeCheckReset(RtreeCheck *pCheck, sqlite3_stmt *pStmt){
3859 int rc = sqlite3_reset(pStmt);
3860 if( pCheck->rc==SQLITE_OK ) pCheck->rc = rc;
3861 }
3862
3863 /*
3864 ** The second and subsequent arguments to this function are a format string
3865 ** and printf style arguments. This function formats the string and attempts
3866 ** to compile it as an SQL statement.
3867 **
3868 ** If successful, a pointer to the new SQL statement is returned. Otherwise,
3869 ** NULL is returned and an error code left in RtreeCheck.rc.
3870 */
3871 static sqlite3_stmt *rtreeCheckPrepare(
3872 RtreeCheck *pCheck, /* RtreeCheck object */
3873 const char *zFmt, ... /* Format string and trailing args */
3874 ){
3875 va_list ap;
3876 char *z;
3877 sqlite3_stmt *pRet = 0;
3878
3879 va_start(ap, zFmt);
3880 z = sqlite3_vmprintf(zFmt, ap);
3881
3882 if( pCheck->rc==SQLITE_OK ){
3883 if( z==0 ){
3884 pCheck->rc = SQLITE_NOMEM;
3885 }else{
3886 pCheck->rc = sqlite3_prepare_v2(pCheck->db, z, -1, &pRet, 0);
3887 }
3888 }
3889
3890 sqlite3_free(z);
3891 va_end(ap);
3892 return pRet;
3893 }
3894
3895 /*
3896 ** The second and subsequent arguments to this function are a printf()
3897 ** style format string and arguments. This function formats the string and
3898 ** appends it to the report being accumulated in pCheck.
3899 */
3900 static void rtreeCheckAppendMsg(RtreeCheck *pCheck, const char *zFmt, ...){
3901 va_list ap;
3902 va_start(ap, zFmt);
3903 if( pCheck->rc==SQLITE_OK && pCheck->nErr<RTREE_CHECK_MAX_ERROR ){
3904 char *z = sqlite3_vmprintf(zFmt, ap);
3905 if( z==0 ){
3906 pCheck->rc = SQLITE_NOMEM;
3907 }else{
3908 pCheck->zReport = sqlite3_mprintf("%z%s%z",
3909 pCheck->zReport, (pCheck->zReport ? "\n" : ""), z
3910 );
3911 if( pCheck->zReport==0 ){
3912 pCheck->rc = SQLITE_NOMEM;
3913 }
3914 }
3915 pCheck->nErr++;
3916 }
3917 va_end(ap);
3918 }
3919
3920 /*
3921 ** This function is a no-op if there is already an error code stored
3922 ** in the RtreeCheck object indicated by the first argument. NULL is
3923 ** returned in this case.
3924 **
3925 ** Otherwise, the contents of rtree table node iNode are loaded from
3926 ** the database and copied into a buffer obtained from sqlite3_malloc().
3927 ** If no error occurs, a pointer to the buffer is returned and (*pnNode)
3928 ** is set to the size of the buffer in bytes.
3929 **
3930 ** Or, if an error does occur, NULL is returned and an error code left
3931 ** in the RtreeCheck object. The final value of *pnNode is undefined in
3932 ** this case.
3933 */
3934 static u8 *rtreeCheckGetNode(RtreeCheck *pCheck, i64 iNode, int *pnNode){
3935 u8 *pRet = 0; /* Return value */
3936
3937 if( pCheck->rc==SQLITE_OK && pCheck->pGetNode==0 ){
3938 pCheck->pGetNode = rtreeCheckPrepare(pCheck,
3939 "SELECT data FROM %Q.'%q_node' WHERE nodeno=?",
3940 pCheck->zDb, pCheck->zTab
3941 );
3942 }
3943
3944 if( pCheck->rc==SQLITE_OK ){
3945 sqlite3_bind_int64(pCheck->pGetNode, 1, iNode);
3946 if( sqlite3_step(pCheck->pGetNode)==SQLITE_ROW ){
3947 int nNode = sqlite3_column_bytes(pCheck->pGetNode, 0);
3948 const u8 *pNode = (const u8*)sqlite3_column_blob(pCheck->pGetNode, 0);
3949 pRet = sqlite3_malloc64(nNode);
3950 if( pRet==0 ){
3951 pCheck->rc = SQLITE_NOMEM;
3952 }else{
3953 memcpy(pRet, pNode, nNode);
3954 *pnNode = nNode;
3955 }
3956 }
3957 rtreeCheckReset(pCheck, pCheck->pGetNode);
3958 if( pCheck->rc==SQLITE_OK && pRet==0 ){
3959 rtreeCheckAppendMsg(pCheck, "Node %lld missing from database", iNode);
3960 }
3961 }
3962
3963 return pRet;
3964 }
3965
3966 /*
3967 ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
3968 ** (if bLeaf==1) table contains a specified entry. The schemas of the
3969 ** two tables are:
3970 **
3971 ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
3972 ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
3973 **
3974 ** In both cases, this function checks that there exists an entry with
3975 ** IPK value iKey and the second column set to iVal.
3976 **
3977 */
3978 static void rtreeCheckMapping(
3979 RtreeCheck *pCheck, /* RtreeCheck object */
3980 int bLeaf, /* True for a leaf cell, false for interior */
3981 i64 iKey, /* Key for mapping */
3982 i64 iVal /* Expected value for mapping */
3983 ){
3984 int rc;
3985 sqlite3_stmt *pStmt;
3986 const char *azSql[2] = {
3987 "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1",
3988 "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1"
3989 };
3990
3991 assert( bLeaf==0 || bLeaf==1 );
3992 if( pCheck->aCheckMapping[bLeaf]==0 ){
3993 pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
3994 azSql[bLeaf], pCheck->zDb, pCheck->zTab
3995 );
3996 }
3997 if( pCheck->rc!=SQLITE_OK ) return;
3998
3999 pStmt = pCheck->aCheckMapping[bLeaf];
4000 sqlite3_bind_int64(pStmt, 1, iKey);
4001 rc = sqlite3_step(pStmt);
4002 if( rc==SQLITE_DONE ){
4003 rtreeCheckAppendMsg(pCheck, "Mapping (%lld -> %lld) missing from %s table",
4004 iKey, iVal, (bLeaf ? "%_rowid" : "%_parent")
4005 );
4006 }else if( rc==SQLITE_ROW ){
4007 i64 ii = sqlite3_column_int64(pStmt, 0);
4008 if( ii!=iVal ){
4009 rtreeCheckAppendMsg(pCheck,
4010 "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
4011 iKey, ii, (bLeaf ? "%_rowid" : "%_parent"), iKey, iVal
4012 );
4013 }
4014 }
4015 rtreeCheckReset(pCheck, pStmt);
4016 }
4017
4018 /*
4019 ** Argument pCell points to an array of coordinates stored on an rtree page.
4020 ** This function checks that the coordinates are internally consistent (no
4021 ** x1>x2 conditions) and adds an error message to the RtreeCheck object
4022 ** if they are not.
4023 **
4024 ** Additionally, if pParent is not NULL, then it is assumed to point to
4025 ** the array of coordinates on the parent page that bound the page
4026 ** containing pCell. In this case it is also verified that the two
4027 ** sets of coordinates are mutually consistent and an error message added
4028 ** to the RtreeCheck object if they are not.
4029 */
4030 static void rtreeCheckCellCoord(
4031 RtreeCheck *pCheck,
4032 i64 iNode, /* Node id to use in error messages */
4033 int iCell, /* Cell number to use in error messages */
4034 u8 *pCell, /* Pointer to cell coordinates */
4035 u8 *pParent /* Pointer to parent coordinates */
4036 ){
4037 RtreeCoord c1, c2;
4038 RtreeCoord p1, p2;
4039 int i;
4040
4041 for(i=0; i<pCheck->nDim; i++){
4042 readCoord(&pCell[4*2*i], &c1);
4043 readCoord(&pCell[4*(2*i + 1)], &c2);
4044
4045 /* printf("%e, %e\n", c1.u.f, c2.u.f); */
4046 if( pCheck->bInt ? c1.i>c2.i : c1.f>c2.f ){
4047 rtreeCheckAppendMsg(pCheck,
4048 "Dimension %d of cell %d on node %lld is corrupt", i, iCell, iNode
4049 );
4050 }
4051
4052 if( pParent ){
4053 readCoord(&pParent[4*2*i], &p1);
4054 readCoord(&pParent[4*(2*i + 1)], &p2);
4055
4056 if( (pCheck->bInt ? c1.i<p1.i : c1.f<p1.f)
4057 || (pCheck->bInt ? c2.i>p2.i : c2.f>p2.f)
4058 ){
4059 rtreeCheckAppendMsg(pCheck,
4060 "Dimension %d of cell %d on node %lld is corrupt relative to parent"
4061 , i, iCell, iNode
4062 );
4063 }
4064 }
4065 }
4066 }
4067
4068 /*
4069 ** Run rtreecheck() checks on node iNode, which is at depth iDepth within
4070 ** the r-tree structure. Argument aParent points to the array of coordinates
4071 ** that bound node iNode on the parent node.
4072 **
4073 ** If any problems are discovered, an error message is appended to the
4074 ** report accumulated in the RtreeCheck object.
4075 */
4076 static void rtreeCheckNode(
4077 RtreeCheck *pCheck,
4078 int iDepth, /* Depth of iNode (0==leaf) */
4079 u8 *aParent, /* Buffer containing parent coords */
4080 i64 iNode /* Node to check */
4081 ){
4082 u8 *aNode = 0;
4083 int nNode = 0;
4084
4085 assert( iNode==1 || aParent!=0 );
4086 assert( pCheck->nDim>0 );
4087
4088 aNode = rtreeCheckGetNode(pCheck, iNode, &nNode);
4089 if( aNode ){
4090 if( nNode<4 ){
4091 rtreeCheckAppendMsg(pCheck,
4092 "Node %lld is too small (%d bytes)", iNode, nNode
4093 );
4094 }else{
4095 int nCell; /* Number of cells on page */
4096 int i; /* Used to iterate through cells */
4097 if( aParent==0 ){
4098 iDepth = readInt16(aNode);
4099 if( iDepth>RTREE_MAX_DEPTH ){
4100 rtreeCheckAppendMsg(pCheck, "Rtree depth out of range (%d)", iDepth);
4101 sqlite3_free(aNode);
4102 return;
4103 }
4104 }
4105 nCell = readInt16(&aNode[2]);
4106 if( (4 + nCell*(8 + pCheck->nDim*2*4))>nNode ){
4107 rtreeCheckAppendMsg(pCheck,
4108 "Node %lld is too small for cell count of %d (%d bytes)",
4109 iNode, nCell, nNode
4110 );
4111 }else{
4112 for(i=0; i<nCell; i++){
4113 u8 *pCell = &aNode[4 + i*(8 + pCheck->nDim*2*4)];
4114 i64 iVal = readInt64(pCell);
4115 rtreeCheckCellCoord(pCheck, iNode, i, &pCell[8], aParent);
4116
4117 if( iDepth>0 ){
4118 rtreeCheckMapping(pCheck, 0, iVal, iNode);
4119 rtreeCheckNode(pCheck, iDepth-1, &pCell[8], iVal);
4120 pCheck->nNonLeaf++;
4121 }else{
4122 rtreeCheckMapping(pCheck, 1, iVal, iNode);
4123 pCheck->nLeaf++;
4124 }
4125 }
4126 }
4127 }
4128 sqlite3_free(aNode);
4129 }
4130 }
4131
4132 /*
4133 ** The second argument to this function must be either "_rowid" or
4134 ** "_parent". This function checks that the number of entries in the
4135 ** %_rowid or %_parent table is exactly nExpect. If not, it adds
4136 ** an error message to the report in the RtreeCheck object indicated
4137 ** by the first argument.
4138 */
4139 static void rtreeCheckCount(RtreeCheck *pCheck, const char *zTbl, i64 nExpect){
4140 if( pCheck->rc==SQLITE_OK ){
4141 sqlite3_stmt *pCount;
4142 pCount = rtreeCheckPrepare(pCheck, "SELECT count(*) FROM %Q.'%q%s'",
4143 pCheck->zDb, pCheck->zTab, zTbl
4144 );
4145 if( pCount ){
4146 if( sqlite3_step(pCount)==SQLITE_ROW ){
4147 i64 nActual = sqlite3_column_int64(pCount, 0);
4148 if( nActual!=nExpect ){
4149 rtreeCheckAppendMsg(pCheck, "Wrong number of entries in %%%s table"
4150 " - expected %lld, actual %lld" , zTbl, nExpect, nActual
4151 );
4152 }
4153 }
4154 pCheck->rc = sqlite3_finalize(pCount);
4155 }
4156 }
4157 }
4158
4159 /*
4160 ** This function does the bulk of the work for the rtree integrity-check.
4161 ** It is called by rtreecheck(), which is the SQL function implementation.
4162 */
4163 static int rtreeCheckTable(
4164 sqlite3 *db, /* Database handle to access db through */
4165 const char *zDb, /* Name of db ("main", "temp" etc.) */
4166 const char *zTab, /* Name of rtree table to check */
4167 char **pzReport /* OUT: sqlite3_malloc'd report text */
4168 ){
4169 RtreeCheck check; /* Common context for various routines */
4170 sqlite3_stmt *pStmt = 0; /* Used to find column count of rtree table */
4171 int nAux = 0; /* Number of extra columns. */
4172
4173 /* Initialize the context object */
4174 memset(&check, 0, sizeof(check));
4175 check.db = db;
4176 check.zDb = zDb;
4177 check.zTab = zTab;
4178
4179 /* Find the number of auxiliary columns */
4180 pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.'%q_rowid'", zDb, zTab);
4181 if( pStmt ){
4182 nAux = sqlite3_column_count(pStmt) - 2;
4183 sqlite3_finalize(pStmt);
4184 }else
4185 if( check.rc!=SQLITE_NOMEM ){
4186 check.rc = SQLITE_OK;
4187 }
4188
4189 /* Find number of dimensions in the rtree table. */
4190 pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.%Q", zDb, zTab);
4191 if( pStmt ){
4192 int rc;
4193 check.nDim = (sqlite3_column_count(pStmt) - 1 - nAux) / 2;
4194 if( check.nDim<1 ){
4195 rtreeCheckAppendMsg(&check, "Schema corrupt or not an rtree");
4196 }else if( SQLITE_ROW==sqlite3_step(pStmt) ){
4197 check.bInt = (sqlite3_column_type(pStmt, 1)==SQLITE_INTEGER);
4198 }
4199 rc = sqlite3_finalize(pStmt);
4200 if( rc!=SQLITE_CORRUPT ) check.rc = rc;
4201 }
4202
4203 /* Do the actual integrity-check */
4204 if( check.nDim>=1 ){
4205 if( check.rc==SQLITE_OK ){
4206 rtreeCheckNode(&check, 0, 0, 1);
4207 }
4208 rtreeCheckCount(&check, "_rowid", check.nLeaf);
4209 rtreeCheckCount(&check, "_parent", check.nNonLeaf);
4210 }
4211
4212 /* Finalize SQL statements used by the integrity-check */
4213 sqlite3_finalize(check.pGetNode);
4214 sqlite3_finalize(check.aCheckMapping[0]);
4215 sqlite3_finalize(check.aCheckMapping[1]);
4216
4217 *pzReport = check.zReport;
4218 return check.rc;
4219 }
4220
4221 /*
4222 ** Implementation of the xIntegrity method for Rtree.
4223 */
4224 static int rtreeIntegrity(
4225 sqlite3_vtab *pVtab, /* The virtual table to check */
4226 const char *zSchema, /* Schema in which the virtual table lives */
4227 const char *zName, /* Name of the virtual table */
4228 int isQuick, /* True for a quick_check */
4229 char **pzErr /* Write results here */
4230 ){
4231 Rtree *pRtree = (Rtree*)pVtab;
4232 int rc;
4233 assert( pzErr!=0 && *pzErr==0 );
4234 UNUSED_PARAMETER(zSchema);
4235 UNUSED_PARAMETER(zName);
4236 UNUSED_PARAMETER(isQuick);
4237 rc = rtreeCheckTable(pRtree->db, pRtree->zDb, pRtree->zName, pzErr);
4238 if( rc==SQLITE_OK && *pzErr ){
4239 *pzErr = sqlite3_mprintf("In RTree %s.%s:\n%z",
4240 pRtree->zDb, pRtree->zName, *pzErr);
4241 if( (*pzErr)==0 ) rc = SQLITE_NOMEM;
4242 }
4243 return rc;
4244 }
4245
4246 /*
4247 ** Usage:
4248 **
4249 ** rtreecheck(<rtree-table>);
4250 ** rtreecheck(<database>, <rtree-table>);
4251 **
4252 ** Invoking this SQL function runs an integrity-check on the named rtree
4253 ** table. The integrity-check verifies the following:
4254 **
4255 ** 1. For each cell in the r-tree structure (%_node table), that:
4256 **
4257 ** a) for each dimension, (coord1 <= coord2).
4258 **
4259 ** b) unless the cell is on the root node, that the cell is bounded
4260 ** by the parent cell on the parent node.
4261 **
4262 ** c) for leaf nodes, that there is an entry in the %_rowid
4263 ** table corresponding to the cell's rowid value that
4264 ** points to the correct node.
4265 **
4266 ** d) for cells on non-leaf nodes, that there is an entry in the
4267 ** %_parent table mapping from the cell's child node to the
4268 ** node that it resides on.
4269 **
4270 ** 2. That there are the same number of entries in the %_rowid table
4271 ** as there are leaf cells in the r-tree structure, and that there
4272 ** is a leaf cell that corresponds to each entry in the %_rowid table.
4273 **
4274 ** 3. That there are the same number of entries in the %_parent table
4275 ** as there are non-leaf cells in the r-tree structure, and that
4276 ** there is a non-leaf cell that corresponds to each entry in the
4277 ** %_parent table.
4278 */
4279 static void rtreecheck(
4280 sqlite3_context *ctx,
4281 int nArg,
4282 sqlite3_value **apArg
4283 ){
4284 if( nArg!=1 && nArg!=2 ){
4285 sqlite3_result_error(ctx,
4286 "wrong number of arguments to function rtreecheck()", -1
4287 );
4288 }else{
4289 int rc;
4290 char *zReport = 0;
4291 const char *zDb = (const char*)sqlite3_value_text(apArg[0]);
4292 const char *zTab;
4293 if( nArg==1 ){
4294 zTab = zDb;
4295 zDb = "main";
4296 }else{
4297 zTab = (const char*)sqlite3_value_text(apArg[1]);
4298 }
4299 rc = rtreeCheckTable(sqlite3_context_db_handle(ctx), zDb, zTab, &zReport);
4300 if( rc==SQLITE_OK ){
4301 sqlite3_result_text(ctx, zReport ? zReport : "ok", -1, SQLITE_TRANSIENT);
4302 }else{
4303 sqlite3_result_error_code(ctx, rc);
4304 }
4305 sqlite3_free(zReport);
4306 }
4307 }
4308
4309 /* Conditionally include the geopoly code */
4310 #ifdef SQLITE_ENABLE_GEOPOLY
4311 # include "geopoly.c"
4312 #endif
4313
4314 /*
4315 ** Register the r-tree module with database handle db. This creates the
4316 ** virtual table module "rtree" and the debugging/analysis scalar
4317 ** function "rtreenode".
4318 */
4319 int sqlite3RtreeInit(sqlite3 *db){
4320 const int utf8 = SQLITE_UTF8;
4321 int rc;
4322
4323 rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
4324 if( rc==SQLITE_OK ){
4325 rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
4326 }
4327 if( rc==SQLITE_OK ){
4328 rc = sqlite3_create_function(db, "rtreecheck", -1, utf8, 0,rtreecheck, 0,0);
4329 }
4330 if( rc==SQLITE_OK ){
4331 #ifdef SQLITE_RTREE_INT_ONLY
4332 void *c = (void *)RTREE_COORD_INT32;
4333 #else
4334 void *c = (void *)RTREE_COORD_REAL32;
4335 #endif
4336 rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
4337 }
4338 if( rc==SQLITE_OK ){
4339 void *c = (void *)RTREE_COORD_INT32;
4340 rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
4341 }
4342 #ifdef SQLITE_ENABLE_GEOPOLY
4343 if( rc==SQLITE_OK ){
4344 rc = sqlite3_geopoly_init(db);
4345 }
4346 #endif
4347
4348 return rc;
4349 }
4350
4351 /*
4352 ** This routine deletes the RtreeGeomCallback object that was attached
4353 ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
4354 ** or sqlite3_rtree_query_callback(). In other words, this routine is the
4355 ** destructor for an RtreeGeomCallback objecct. This routine is called when
4356 ** the corresponding SQL function is deleted.
4357 */
4358 static void rtreeFreeCallback(void *p){
4359 RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
4360 if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
4361 sqlite3_free(p);
4362 }
4363
4364 /*
4365 ** This routine frees the BLOB that is returned by geomCallback().
4366 */
4367 static void rtreeMatchArgFree(void *pArg){
4368 int i;
4369 RtreeMatchArg *p = (RtreeMatchArg*)pArg;
4370 for(i=0; i<p->nParam; i++){
4371 sqlite3_value_free(p->apSqlParam[i]);
4372 }
4373 sqlite3_free(p);
4374 }
4375
4376 /*
4377 ** Each call to sqlite3_rtree_geometry_callback() or
4378 ** sqlite3_rtree_query_callback() creates an ordinary SQLite
4379 ** scalar function that is implemented by this routine.
4380 **
4381 ** All this function does is construct an RtreeMatchArg object that
4382 ** contains the geometry-checking callback routines and a list of
4383 ** parameters to this function, then return that RtreeMatchArg object
4384 ** as a BLOB.
4385 **
4386 ** The R-Tree MATCH operator will read the returned BLOB, deserialize
4387 ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
4388 ** out which elements of the R-Tree should be returned by the query.
4389 */
4390 static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
4391 RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
4392 RtreeMatchArg *pBlob;
4393 sqlite3_int64 nBlob;
4394 int memErr = 0;
4395
4396 nBlob = SZ_RTREEMATCHARG(nArg) + nArg*sizeof(sqlite3_value*);
4397 pBlob = (RtreeMatchArg *)sqlite3_malloc64(nBlob);
4398 if( !pBlob ){
4399 sqlite3_result_error_nomem(ctx);
4400 }else{
4401 int i;
4402 pBlob->iSize = nBlob;
4403 pBlob->cb = pGeomCtx[0];
4404 pBlob->apSqlParam = (sqlite3_value**)&pBlob->aParam[nArg];
4405 pBlob->nParam = nArg;
4406 for(i=0; i<nArg; i++){
4407 pBlob->apSqlParam[i] = sqlite3_value_dup(aArg[i]);
4408 if( pBlob->apSqlParam[i]==0 ) memErr = 1;
4409 #ifdef SQLITE_RTREE_INT_ONLY
4410 pBlob->aParam[i] = sqlite3_value_int64(aArg[i]);
4411 #else
4412 pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
4413 #endif
4414 }
4415 if( memErr ){
4416 sqlite3_result_error_nomem(ctx);
4417 rtreeMatchArgFree(pBlob);
4418 }else{
4419 sqlite3_result_pointer(ctx, pBlob, "RtreeMatchArg", rtreeMatchArgFree);
4420 }
4421 }
4422 }
4423
4424 /*
4425 ** Register a new geometry function for use with the r-tree MATCH operator.
4426 */
4427 int sqlite3_rtree_geometry_callback(
4428 sqlite3 *db, /* Register SQL function on this connection */
4429 const char *zGeom, /* Name of the new SQL function */
4430 int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */
4431 void *pContext /* Extra data associated with the callback */
4432 ){
4433 RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */
4434
4435 /* Allocate and populate the context object. */
4436 pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
4437 if( !pGeomCtx ) return SQLITE_NOMEM;
4438 pGeomCtx->xGeom = xGeom;
4439 pGeomCtx->xQueryFunc = 0;
4440 pGeomCtx->xDestructor = 0;
4441 pGeomCtx->pContext = pContext;
4442 return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY,
4443 (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
4444 );
4445 }
4446
4447 /*
4448 ** Register a new 2nd-generation geometry function for use with the
4449 ** r-tree MATCH operator.
4450 */
4451 int sqlite3_rtree_query_callback(
4452 sqlite3 *db, /* Register SQL function on this connection */
4453 const char *zQueryFunc, /* Name of new SQL function */
4454 int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */
4455 void *pContext, /* Extra data passed into the callback */
4456 void (*xDestructor)(void*) /* Destructor for the extra data */
4457 ){
4458 RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */
4459
4460 /* Allocate and populate the context object. */
4461 pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
4462 if( !pGeomCtx ){
4463 if( xDestructor ) xDestructor(pContext);
4464 return SQLITE_NOMEM;
4465 }
4466 pGeomCtx->xGeom = 0;
4467 pGeomCtx->xQueryFunc = xQueryFunc;
4468 pGeomCtx->xDestructor = xDestructor;
4469 pGeomCtx->pContext = pContext;
4470 return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY,
4471 (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
4472 );
4473 }
4474
4475 #ifndef SQLITE_CORE
4476 #ifdef _WIN32
4477 __declspec(dllexport)
4478 #endif
4479 int sqlite3_rtree_init(
4480 sqlite3 *db,
4481 char **pzErrMsg,
4482 const sqlite3_api_routines *pApi
4483 ){
4484 SQLITE_EXTENSION_INIT2(pApi)
4485 return sqlite3RtreeInit(db);
4486 }
4487 #endif
4488
4489 #endif