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.
35 **
36 ** The root node of an r-tree always exists, even if the r-tree table is
37 ** empty. The nodeno of the root node is always 1. All other nodes in the
38 ** table must be the same size as the root node. The content of each node
39 ** is formatted as follows:
40 **
41 ** 1. If the node is the root node (node 1), then the first 2 bytes
42 ** of the node contain the tree depth as a big-endian integer.
43 ** For non-root nodes, the first 2 bytes are left unused.
44 **
45 ** 2. The next 2 bytes contain the number of entries currently
46 ** stored in the node.
47 **
48 ** 3. The remainder of the node contains the node entries. Each entry
49 ** consists of a single 8-byte integer followed by an even number
50 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
51 ** of a record. For internal nodes it is the node number of a
52 ** child page.
53 */
54
55 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
56
57 /*
58 ** This file contains an implementation of a couple of different variants
59 ** of the r-tree algorithm. See the README file for further details. The
60 ** same data-structure is used for all, but the algorithms for insert and
61 ** delete operations vary. The variants used are selected at compile time
62 ** by defining the following symbols:
63 */
64
65 /* Either, both or none of the following may be set to activate
66 ** r*tree variant algorithms.
67 */
68 #define VARIANT_RSTARTREE_CHOOSESUBTREE 0
69 #define VARIANT_RSTARTREE_REINSERT 1
70
71 /*
72 ** Exactly one of the following must be set to 1.
73 */
74 #define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
75 #define VARIANT_GUTTMAN_LINEAR_SPLIT 0
76 #define VARIANT_RSTARTREE_SPLIT 1
77
78 #define VARIANT_GUTTMAN_SPLIT \
79 (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
80
81 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT
82 #define PickNext QuadraticPickNext
83 #define PickSeeds QuadraticPickSeeds
84 #define AssignCells splitNodeGuttman
85 #endif
86 #if VARIANT_GUTTMAN_LINEAR_SPLIT
87 #define PickNext LinearPickNext
88 #define PickSeeds LinearPickSeeds
89 #define AssignCells splitNodeGuttman
90 #endif
91 #if VARIANT_RSTARTREE_SPLIT
92 #define AssignCells splitNodeStartree
93 #endif
94
95 #if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
96 # define NDEBUG 1
97 #endif
98
99 #ifndef SQLITE_CORE
100 #include "sqlite3ext.h"
101 SQLITE_EXTENSION_INIT1
102 #else
103 #include "sqlite3.h"
104 #endif
105
106 #include <string.h>
107 #include <assert.h>
108
109 #ifndef SQLITE_AMALGAMATION
110 #include "sqlite3rtree.h"
111 typedef sqlite3_int64 i64;
112 typedef unsigned char u8;
113 typedef unsigned int u32;
114 #endif
115
116 /* The following macro is used to suppress compiler warnings.
117 */
118 #ifndef UNUSED_PARAMETER
119 # define UNUSED_PARAMETER(x) (void)(x)
120 #endif
121
122 typedef struct Rtree Rtree;
123 typedef struct RtreeCursor RtreeCursor;
124 typedef struct RtreeNode RtreeNode;
125 typedef struct RtreeCell RtreeCell;
126 typedef struct RtreeConstraint RtreeConstraint;
127 typedef struct RtreeMatchArg RtreeMatchArg;
128 typedef struct RtreeGeomCallback RtreeGeomCallback;
129 typedef union RtreeCoord RtreeCoord;
130
131 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
132 #define RTREE_MAX_DIMENSIONS 5
133
134 /* Size of hash table Rtree.aHash. This hash table is not expected to
135 ** ever contain very many entries, so a fixed number of buckets is
136 ** used.
137 */
138 #define HASHSIZE 128
139
140 /*
141 ** An rtree virtual-table object.
142 */
143 struct Rtree {
144 sqlite3_vtab base;
145 sqlite3 *db; /* Host database connection */
146 int iNodeSize; /* Size in bytes of each node in the node table */
147 int nDim; /* Number of dimensions */
148 int nBytesPerCell; /* Bytes consumed per cell */
149 int iDepth; /* Current depth of the r-tree structure */
150 char *zDb; /* Name of database containing r-tree table */
151 char *zName; /* Name of r-tree table */
152 RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
153 int nBusy; /* Current number of users of this structure */
154
155 /* List of nodes removed during a CondenseTree operation. List is
156 ** linked together via the pointer normally used for hash chains -
157 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
158 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
159 */
160 RtreeNode *pDeleted;
161 int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */
162
163 /* Statements to read/write/delete a record from xxx_node */
164 sqlite3_stmt *pReadNode;
165 sqlite3_stmt *pWriteNode;
166 sqlite3_stmt *pDeleteNode;
167
168 /* Statements to read/write/delete a record from xxx_rowid */
169 sqlite3_stmt *pReadRowid;
170 sqlite3_stmt *pWriteRowid;
171 sqlite3_stmt *pDeleteRowid;
172
173 /* Statements to read/write/delete a record from xxx_parent */
174 sqlite3_stmt *pReadParent;
175 sqlite3_stmt *pWriteParent;
176 sqlite3_stmt *pDeleteParent;
177
178 int eCoordType;
179 };
180
181 /* Possible values for eCoordType: */
182 #define RTREE_COORD_REAL32 0
183 #define RTREE_COORD_INT32 1
184
185 /*
186 ** The minimum number of cells allowed for a node is a third of the
187 ** maximum. In Gutman's notation:
188 **
189 ** m = M/3
190 **
191 ** If an R*-tree "Reinsert" operation is required, the same number of
192 ** cells are removed from the overfull node and reinserted into the tree.
193 */
194 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
195 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
196 #define RTREE_MAXCELLS 51
197
198 /*
199 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
200 ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
201 ** Therefore all non-root nodes must contain at least 3 entries. Since
202 ** 2^40 is greater than 2^64, an r-tree structure always has a depth of
203 ** 40 or less.
204 */
205 #define RTREE_MAX_DEPTH 40
206
207 /*
208 ** An rtree cursor object.
209 */
210 struct RtreeCursor {
211 sqlite3_vtab_cursor base;
212 RtreeNode *pNode; /* Node cursor is currently pointing at */
213 int iCell; /* Index of current cell in pNode */
214 int iStrategy; /* Copy of idxNum search parameter */
215 int nConstraint; /* Number of entries in aConstraint */
216 RtreeConstraint *aConstraint; /* Search constraints. */
217 };
218
219 union RtreeCoord {
220 float f;
221 int i;
222 };
223
224 /*
225 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
226 ** formatted as a double. This macro assumes that local variable pRtree points
227 ** to the Rtree structure associated with the RtreeCoord.
228 */
229 #define DCOORD(coord) ( \
230 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
231 ((double)coord.f) : \
232 ((double)coord.i) \
233 )
234
235 /*
236 ** A search constraint.
237 */
238 struct RtreeConstraint {
239 int iCoord; /* Index of constrained coordinate */
240 int op; /* Constraining operation */
241 double rValue; /* Constraint value. */
242 int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
243 sqlite3_rtree_geometry *pGeom; /* Constraint callback argument for a MATCH */
244 };
245
246 /* Possible values for RtreeConstraint.op */
247 #define RTREE_EQ 0x41
248 #define RTREE_LE 0x42
249 #define RTREE_LT 0x43
250 #define RTREE_GE 0x44
251 #define RTREE_GT 0x45
252 #define RTREE_MATCH 0x46
253
254 /*
255 ** An rtree structure node.
256 */
257 struct RtreeNode {
258 RtreeNode *pParent; /* Parent node */
259 i64 iNode;
260 int nRef;
261 int isDirty;
262 u8 *zData;
263 RtreeNode *pNext; /* Next node in this hash chain */
264 };
265 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
266
267 /*
268 ** Structure to store a deserialized rtree record.
269 */
270 struct RtreeCell {
271 i64 iRowid;
272 RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
273 };
274
275
276 /*
277 ** Value for the first field of every RtreeMatchArg object. The MATCH
278 ** operator tests that the first field of a blob operand matches this
279 ** value to avoid operating on invalid blobs (which could cause a segfault).
280 */
281 #define RTREE_GEOMETRY_MAGIC 0x891245AB
282
283 /*
284 ** An instance of this structure must be supplied as a blob argument to
285 ** the right-hand-side of an SQL MATCH operator used to constrain an
286 ** r-tree query.
287 */
288 struct RtreeMatchArg {
289 u32 magic; /* Always RTREE_GEOMETRY_MAGIC */
290 int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
291 void *pContext;
292 int nParam;
293 double aParam[1];
294 };
295
296 /*
297 ** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
298 ** a single instance of the following structure is allocated. It is used
299 ** as the context for the user-function created by by s_r_g_c(). The object
300 ** is eventually deleted by the destructor mechanism provided by
301 ** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
302 ** the geometry callback function).
303 */
304 struct RtreeGeomCallback {
305 int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
306 void *pContext;
307 };
308
309 #ifndef MAX
310 # define MAX(x,y) ((x) < (y) ? (y) : (x))
311 #endif
312 #ifndef MIN
313 # define MIN(x,y) ((x) > (y) ? (y) : (x))
314 #endif
315
316 /*
317 ** Functions to deserialize a 16 bit integer, 32 bit real number and
318 ** 64 bit integer. The deserialized value is returned.
319 */
readInt16(u8 * p)320 static int readInt16(u8 *p){
321 return (p[0]<<8) + p[1];
322 }
readCoord(u8 * p,RtreeCoord * pCoord)323 static void readCoord(u8 *p, RtreeCoord *pCoord){
324 u32 i = (
325 (((u32)p[0]) << 24) +
326 (((u32)p[1]) << 16) +
327 (((u32)p[2]) << 8) +
328 (((u32)p[3]) << 0)
329 );
330 *(u32 *)pCoord = i;
331 }
readInt64(u8 * p)332 static i64 readInt64(u8 *p){
333 return (
334 (((i64)p[0]) << 56) +
335 (((i64)p[1]) << 48) +
336 (((i64)p[2]) << 40) +
337 (((i64)p[3]) << 32) +
338 (((i64)p[4]) << 24) +
339 (((i64)p[5]) << 16) +
340 (((i64)p[6]) << 8) +
341 (((i64)p[7]) << 0)
342 );
343 }
344
345 /*
346 ** Functions to serialize a 16 bit integer, 32 bit real number and
347 ** 64 bit integer. The value returned is the number of bytes written
348 ** to the argument buffer (always 2, 4 and 8 respectively).
349 */
writeInt16(u8 * p,int i)350 static int writeInt16(u8 *p, int i){
351 p[0] = (i>> 8)&0xFF;
352 p[1] = (i>> 0)&0xFF;
353 return 2;
354 }
writeCoord(u8 * p,RtreeCoord * pCoord)355 static int writeCoord(u8 *p, RtreeCoord *pCoord){
356 u32 i;
357 assert( sizeof(RtreeCoord)==4 );
358 assert( sizeof(u32)==4 );
359 i = *(u32 *)pCoord;
360 p[0] = (i>>24)&0xFF;
361 p[1] = (i>>16)&0xFF;
362 p[2] = (i>> 8)&0xFF;
363 p[3] = (i>> 0)&0xFF;
364 return 4;
365 }
writeInt64(u8 * p,i64 i)366 static int writeInt64(u8 *p, i64 i){
367 p[0] = (i>>56)&0xFF;
368 p[1] = (i>>48)&0xFF;
369 p[2] = (i>>40)&0xFF;
370 p[3] = (i>>32)&0xFF;
371 p[4] = (i>>24)&0xFF;
372 p[5] = (i>>16)&0xFF;
373 p[6] = (i>> 8)&0xFF;
374 p[7] = (i>> 0)&0xFF;
375 return 8;
376 }
377
378 /*
379 ** Increment the reference count of node p.
380 */
nodeReference(RtreeNode * p)381 static void nodeReference(RtreeNode *p){
382 if( p ){
383 p->nRef++;
384 }
385 }
386
387 /*
388 ** Clear the content of node p (set all bytes to 0x00).
389 */
nodeZero(Rtree * pRtree,RtreeNode * p)390 static void nodeZero(Rtree *pRtree, RtreeNode *p){
391 memset(&p->zData[2], 0, pRtree->iNodeSize-2);
392 p->isDirty = 1;
393 }
394
395 /*
396 ** Given a node number iNode, return the corresponding key to use
397 ** in the Rtree.aHash table.
398 */
nodeHash(i64 iNode)399 static int nodeHash(i64 iNode){
400 return (
401 (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^
402 (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
403 ) % HASHSIZE;
404 }
405
406 /*
407 ** Search the node hash table for node iNode. If found, return a pointer
408 ** to it. Otherwise, return 0.
409 */
nodeHashLookup(Rtree * pRtree,i64 iNode)410 static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
411 RtreeNode *p;
412 for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
413 return p;
414 }
415
416 /*
417 ** Add node pNode to the node hash table.
418 */
nodeHashInsert(Rtree * pRtree,RtreeNode * pNode)419 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
420 int iHash;
421 assert( pNode->pNext==0 );
422 iHash = nodeHash(pNode->iNode);
423 pNode->pNext = pRtree->aHash[iHash];
424 pRtree->aHash[iHash] = pNode;
425 }
426
427 /*
428 ** Remove node pNode from the node hash table.
429 */
nodeHashDelete(Rtree * pRtree,RtreeNode * pNode)430 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
431 RtreeNode **pp;
432 if( pNode->iNode!=0 ){
433 pp = &pRtree->aHash[nodeHash(pNode->iNode)];
434 for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
435 *pp = pNode->pNext;
436 pNode->pNext = 0;
437 }
438 }
439
440 /*
441 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
442 ** indicating that node has not yet been assigned a node number. It is
443 ** assigned a node number when nodeWrite() is called to write the
444 ** node contents out to the database.
445 */
nodeNew(Rtree * pRtree,RtreeNode * pParent)446 static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
447 RtreeNode *pNode;
448 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
449 if( pNode ){
450 memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
451 pNode->zData = (u8 *)&pNode[1];
452 pNode->nRef = 1;
453 pNode->pParent = pParent;
454 pNode->isDirty = 1;
455 nodeReference(pParent);
456 }
457 return pNode;
458 }
459
460 /*
461 ** Obtain a reference to an r-tree node.
462 */
463 static int
nodeAcquire(Rtree * pRtree,i64 iNode,RtreeNode * pParent,RtreeNode ** ppNode)464 nodeAcquire(
465 Rtree *pRtree, /* R-tree structure */
466 i64 iNode, /* Node number to load */
467 RtreeNode *pParent, /* Either the parent node or NULL */
468 RtreeNode **ppNode /* OUT: Acquired node */
469 ){
470 int rc;
471 int rc2 = SQLITE_OK;
472 RtreeNode *pNode;
473
474 /* Check if the requested node is already in the hash table. If so,
475 ** increase its reference count and return it.
476 */
477 if( (pNode = nodeHashLookup(pRtree, iNode)) ){
478 assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
479 if( pParent && !pNode->pParent ){
480 nodeReference(pParent);
481 pNode->pParent = pParent;
482 }
483 pNode->nRef++;
484 *ppNode = pNode;
485 return SQLITE_OK;
486 }
487
488 sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
489 rc = sqlite3_step(pRtree->pReadNode);
490 if( rc==SQLITE_ROW ){
491 const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
492 if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){
493 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize);
494 if( !pNode ){
495 rc2 = SQLITE_NOMEM;
496 }else{
497 pNode->pParent = pParent;
498 pNode->zData = (u8 *)&pNode[1];
499 pNode->nRef = 1;
500 pNode->iNode = iNode;
501 pNode->isDirty = 0;
502 pNode->pNext = 0;
503 memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
504 nodeReference(pParent);
505 }
506 }
507 }
508 rc = sqlite3_reset(pRtree->pReadNode);
509 if( rc==SQLITE_OK ) rc = rc2;
510
511 /* If the root node was just loaded, set pRtree->iDepth to the height
512 ** of the r-tree structure. A height of zero means all data is stored on
513 ** the root node. A height of one means the children of the root node
514 ** are the leaves, and so on. If the depth as specified on the root node
515 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
516 */
517 if( pNode && iNode==1 ){
518 pRtree->iDepth = readInt16(pNode->zData);
519 if( pRtree->iDepth>RTREE_MAX_DEPTH ){
520 rc = SQLITE_CORRUPT;
521 }
522 }
523
524 /* If no error has occurred so far, check if the "number of entries"
525 ** field on the node is too large. If so, set the return code to
526 ** SQLITE_CORRUPT.
527 */
528 if( pNode && rc==SQLITE_OK ){
529 if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
530 rc = SQLITE_CORRUPT;
531 }
532 }
533
534 if( rc==SQLITE_OK ){
535 if( pNode!=0 ){
536 nodeHashInsert(pRtree, pNode);
537 }else{
538 rc = SQLITE_CORRUPT;
539 }
540 *ppNode = pNode;
541 }else{
542 sqlite3_free(pNode);
543 *ppNode = 0;
544 }
545
546 return rc;
547 }
548
549 /*
550 ** Overwrite cell iCell of node pNode with the contents of pCell.
551 */
nodeOverwriteCell(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell,int iCell)552 static void nodeOverwriteCell(
553 Rtree *pRtree,
554 RtreeNode *pNode,
555 RtreeCell *pCell,
556 int iCell
557 ){
558 int ii;
559 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
560 p += writeInt64(p, pCell->iRowid);
561 for(ii=0; ii<(pRtree->nDim*2); ii++){
562 p += writeCoord(p, &pCell->aCoord[ii]);
563 }
564 pNode->isDirty = 1;
565 }
566
567 /*
568 ** Remove cell the cell with index iCell from node pNode.
569 */
nodeDeleteCell(Rtree * pRtree,RtreeNode * pNode,int iCell)570 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
571 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
572 u8 *pSrc = &pDst[pRtree->nBytesPerCell];
573 int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
574 memmove(pDst, pSrc, nByte);
575 writeInt16(&pNode->zData[2], NCELL(pNode)-1);
576 pNode->isDirty = 1;
577 }
578
579 /*
580 ** Insert the contents of cell pCell into node pNode. If the insert
581 ** is successful, return SQLITE_OK.
582 **
583 ** If there is not enough free space in pNode, return SQLITE_FULL.
584 */
585 static int
nodeInsertCell(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell)586 nodeInsertCell(
587 Rtree *pRtree,
588 RtreeNode *pNode,
589 RtreeCell *pCell
590 ){
591 int nCell; /* Current number of cells in pNode */
592 int nMaxCell; /* Maximum number of cells for pNode */
593
594 nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
595 nCell = NCELL(pNode);
596
597 assert( nCell<=nMaxCell );
598 if( nCell<nMaxCell ){
599 nodeOverwriteCell(pRtree, pNode, pCell, nCell);
600 writeInt16(&pNode->zData[2], nCell+1);
601 pNode->isDirty = 1;
602 }
603
604 return (nCell==nMaxCell);
605 }
606
607 /*
608 ** If the node is dirty, write it out to the database.
609 */
610 static int
nodeWrite(Rtree * pRtree,RtreeNode * pNode)611 nodeWrite(Rtree *pRtree, RtreeNode *pNode){
612 int rc = SQLITE_OK;
613 if( pNode->isDirty ){
614 sqlite3_stmt *p = pRtree->pWriteNode;
615 if( pNode->iNode ){
616 sqlite3_bind_int64(p, 1, pNode->iNode);
617 }else{
618 sqlite3_bind_null(p, 1);
619 }
620 sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
621 sqlite3_step(p);
622 pNode->isDirty = 0;
623 rc = sqlite3_reset(p);
624 if( pNode->iNode==0 && rc==SQLITE_OK ){
625 pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
626 nodeHashInsert(pRtree, pNode);
627 }
628 }
629 return rc;
630 }
631
632 /*
633 ** Release a reference to a node. If the node is dirty and the reference
634 ** count drops to zero, the node data is written to the database.
635 */
636 static int
nodeRelease(Rtree * pRtree,RtreeNode * pNode)637 nodeRelease(Rtree *pRtree, RtreeNode *pNode){
638 int rc = SQLITE_OK;
639 if( pNode ){
640 assert( pNode->nRef>0 );
641 pNode->nRef--;
642 if( pNode->nRef==0 ){
643 if( pNode->iNode==1 ){
644 pRtree->iDepth = -1;
645 }
646 if( pNode->pParent ){
647 rc = nodeRelease(pRtree, pNode->pParent);
648 }
649 if( rc==SQLITE_OK ){
650 rc = nodeWrite(pRtree, pNode);
651 }
652 nodeHashDelete(pRtree, pNode);
653 sqlite3_free(pNode);
654 }
655 }
656 return rc;
657 }
658
659 /*
660 ** Return the 64-bit integer value associated with cell iCell of
661 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
662 ** an internal node, then the 64-bit integer is a child page number.
663 */
nodeGetRowid(Rtree * pRtree,RtreeNode * pNode,int iCell)664 static i64 nodeGetRowid(
665 Rtree *pRtree,
666 RtreeNode *pNode,
667 int iCell
668 ){
669 assert( iCell<NCELL(pNode) );
670 return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
671 }
672
673 /*
674 ** Return coordinate iCoord from cell iCell in node pNode.
675 */
nodeGetCoord(Rtree * pRtree,RtreeNode * pNode,int iCell,int iCoord,RtreeCoord * pCoord)676 static void nodeGetCoord(
677 Rtree *pRtree,
678 RtreeNode *pNode,
679 int iCell,
680 int iCoord,
681 RtreeCoord *pCoord /* Space to write result to */
682 ){
683 readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
684 }
685
686 /*
687 ** Deserialize cell iCell of node pNode. Populate the structure pointed
688 ** to by pCell with the results.
689 */
nodeGetCell(Rtree * pRtree,RtreeNode * pNode,int iCell,RtreeCell * pCell)690 static void nodeGetCell(
691 Rtree *pRtree,
692 RtreeNode *pNode,
693 int iCell,
694 RtreeCell *pCell
695 ){
696 int ii;
697 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
698 for(ii=0; ii<pRtree->nDim*2; ii++){
699 nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
700 }
701 }
702
703
704 /* Forward declaration for the function that does the work of
705 ** the virtual table module xCreate() and xConnect() methods.
706 */
707 static int rtreeInit(
708 sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int
709 );
710
711 /*
712 ** Rtree virtual table module xCreate method.
713 */
rtreeCreate(sqlite3 * db,void * pAux,int argc,const char * const * argv,sqlite3_vtab ** ppVtab,char ** pzErr)714 static int rtreeCreate(
715 sqlite3 *db,
716 void *pAux,
717 int argc, const char *const*argv,
718 sqlite3_vtab **ppVtab,
719 char **pzErr
720 ){
721 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1);
722 }
723
724 /*
725 ** Rtree virtual table module xConnect method.
726 */
rtreeConnect(sqlite3 * db,void * pAux,int argc,const char * const * argv,sqlite3_vtab ** ppVtab,char ** pzErr)727 static int rtreeConnect(
728 sqlite3 *db,
729 void *pAux,
730 int argc, const char *const*argv,
731 sqlite3_vtab **ppVtab,
732 char **pzErr
733 ){
734 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0);
735 }
736
737 /*
738 ** Increment the r-tree reference count.
739 */
rtreeReference(Rtree * pRtree)740 static void rtreeReference(Rtree *pRtree){
741 pRtree->nBusy++;
742 }
743
744 /*
745 ** Decrement the r-tree reference count. When the reference count reaches
746 ** zero the structure is deleted.
747 */
rtreeRelease(Rtree * pRtree)748 static void rtreeRelease(Rtree *pRtree){
749 pRtree->nBusy--;
750 if( pRtree->nBusy==0 ){
751 sqlite3_finalize(pRtree->pReadNode);
752 sqlite3_finalize(pRtree->pWriteNode);
753 sqlite3_finalize(pRtree->pDeleteNode);
754 sqlite3_finalize(pRtree->pReadRowid);
755 sqlite3_finalize(pRtree->pWriteRowid);
756 sqlite3_finalize(pRtree->pDeleteRowid);
757 sqlite3_finalize(pRtree->pReadParent);
758 sqlite3_finalize(pRtree->pWriteParent);
759 sqlite3_finalize(pRtree->pDeleteParent);
760 sqlite3_free(pRtree);
761 }
762 }
763
764 /*
765 ** Rtree virtual table module xDisconnect method.
766 */
rtreeDisconnect(sqlite3_vtab * pVtab)767 static int rtreeDisconnect(sqlite3_vtab *pVtab){
768 rtreeRelease((Rtree *)pVtab);
769 return SQLITE_OK;
770 }
771
772 /*
773 ** Rtree virtual table module xDestroy method.
774 */
rtreeDestroy(sqlite3_vtab * pVtab)775 static int rtreeDestroy(sqlite3_vtab *pVtab){
776 Rtree *pRtree = (Rtree *)pVtab;
777 int rc;
778 char *zCreate = sqlite3_mprintf(
779 "DROP TABLE '%q'.'%q_node';"
780 "DROP TABLE '%q'.'%q_rowid';"
781 "DROP TABLE '%q'.'%q_parent';",
782 pRtree->zDb, pRtree->zName,
783 pRtree->zDb, pRtree->zName,
784 pRtree->zDb, pRtree->zName
785 );
786 if( !zCreate ){
787 rc = SQLITE_NOMEM;
788 }else{
789 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
790 sqlite3_free(zCreate);
791 }
792 if( rc==SQLITE_OK ){
793 rtreeRelease(pRtree);
794 }
795
796 return rc;
797 }
798
799 /*
800 ** Rtree virtual table module xOpen method.
801 */
rtreeOpen(sqlite3_vtab * pVTab,sqlite3_vtab_cursor ** ppCursor)802 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
803 int rc = SQLITE_NOMEM;
804 RtreeCursor *pCsr;
805
806 pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));
807 if( pCsr ){
808 memset(pCsr, 0, sizeof(RtreeCursor));
809 pCsr->base.pVtab = pVTab;
810 rc = SQLITE_OK;
811 }
812 *ppCursor = (sqlite3_vtab_cursor *)pCsr;
813
814 return rc;
815 }
816
817
818 /*
819 ** Free the RtreeCursor.aConstraint[] array and its contents.
820 */
freeCursorConstraints(RtreeCursor * pCsr)821 static void freeCursorConstraints(RtreeCursor *pCsr){
822 if( pCsr->aConstraint ){
823 int i; /* Used to iterate through constraint array */
824 for(i=0; i<pCsr->nConstraint; i++){
825 sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
826 if( pGeom ){
827 if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
828 sqlite3_free(pGeom);
829 }
830 }
831 sqlite3_free(pCsr->aConstraint);
832 pCsr->aConstraint = 0;
833 }
834 }
835
836 /*
837 ** Rtree virtual table module xClose method.
838 */
rtreeClose(sqlite3_vtab_cursor * cur)839 static int rtreeClose(sqlite3_vtab_cursor *cur){
840 Rtree *pRtree = (Rtree *)(cur->pVtab);
841 int rc;
842 RtreeCursor *pCsr = (RtreeCursor *)cur;
843 freeCursorConstraints(pCsr);
844 rc = nodeRelease(pRtree, pCsr->pNode);
845 sqlite3_free(pCsr);
846 return rc;
847 }
848
849 /*
850 ** Rtree virtual table module xEof method.
851 **
852 ** Return non-zero if the cursor does not currently point to a valid
853 ** record (i.e if the scan has finished), or zero otherwise.
854 */
rtreeEof(sqlite3_vtab_cursor * cur)855 static int rtreeEof(sqlite3_vtab_cursor *cur){
856 RtreeCursor *pCsr = (RtreeCursor *)cur;
857 return (pCsr->pNode==0);
858 }
859
860 /*
861 ** The r-tree constraint passed as the second argument to this function is
862 ** guaranteed to be a MATCH constraint.
863 */
testRtreeGeom(Rtree * pRtree,RtreeConstraint * pConstraint,RtreeCell * pCell,int * pbRes)864 static int testRtreeGeom(
865 Rtree *pRtree, /* R-Tree object */
866 RtreeConstraint *pConstraint, /* MATCH constraint to test */
867 RtreeCell *pCell, /* Cell to test */
868 int *pbRes /* OUT: Test result */
869 ){
870 int i;
871 double aCoord[RTREE_MAX_DIMENSIONS*2];
872 int nCoord = pRtree->nDim*2;
873
874 assert( pConstraint->op==RTREE_MATCH );
875 assert( pConstraint->pGeom );
876
877 for(i=0; i<nCoord; i++){
878 aCoord[i] = DCOORD(pCell->aCoord[i]);
879 }
880 return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
881 }
882
883 /*
884 ** Cursor pCursor currently points to a cell in a non-leaf page.
885 ** Set *pbEof to true if the sub-tree headed by the cell is filtered
886 ** (excluded) by the constraints in the pCursor->aConstraint[]
887 ** array, or false otherwise.
888 **
889 ** Return SQLITE_OK if successful or an SQLite error code if an error
890 ** occurs within a geometry callback.
891 */
testRtreeCell(Rtree * pRtree,RtreeCursor * pCursor,int * pbEof)892 static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
893 RtreeCell cell;
894 int ii;
895 int bRes = 0;
896 int rc = SQLITE_OK;
897
898 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
899 for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
900 RtreeConstraint *p = &pCursor->aConstraint[ii];
901 double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
902 double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
903
904 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
905 || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
906 );
907
908 switch( p->op ){
909 case RTREE_LE: case RTREE_LT:
910 bRes = p->rValue<cell_min;
911 break;
912
913 case RTREE_GE: case RTREE_GT:
914 bRes = p->rValue>cell_max;
915 break;
916
917 case RTREE_EQ:
918 bRes = (p->rValue>cell_max || p->rValue<cell_min);
919 break;
920
921 default: {
922 assert( p->op==RTREE_MATCH );
923 rc = testRtreeGeom(pRtree, p, &cell, &bRes);
924 bRes = !bRes;
925 break;
926 }
927 }
928 }
929
930 *pbEof = bRes;
931 return rc;
932 }
933
934 /*
935 ** Test if the cell that cursor pCursor currently points to
936 ** would be filtered (excluded) by the constraints in the
937 ** pCursor->aConstraint[] array. If so, set *pbEof to true before
938 ** returning. If the cell is not filtered (excluded) by the constraints,
939 ** set pbEof to zero.
940 **
941 ** Return SQLITE_OK if successful or an SQLite error code if an error
942 ** occurs within a geometry callback.
943 **
944 ** This function assumes that the cell is part of a leaf node.
945 */
testRtreeEntry(Rtree * pRtree,RtreeCursor * pCursor,int * pbEof)946 static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
947 RtreeCell cell;
948 int ii;
949 *pbEof = 0;
950
951 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
952 for(ii=0; ii<pCursor->nConstraint; ii++){
953 RtreeConstraint *p = &pCursor->aConstraint[ii];
954 double coord = DCOORD(cell.aCoord[p->iCoord]);
955 int res;
956 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
957 || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
958 );
959 switch( p->op ){
960 case RTREE_LE: res = (coord<=p->rValue); break;
961 case RTREE_LT: res = (coord<p->rValue); break;
962 case RTREE_GE: res = (coord>=p->rValue); break;
963 case RTREE_GT: res = (coord>p->rValue); break;
964 case RTREE_EQ: res = (coord==p->rValue); break;
965 default: {
966 int rc;
967 assert( p->op==RTREE_MATCH );
968 rc = testRtreeGeom(pRtree, p, &cell, &res);
969 if( rc!=SQLITE_OK ){
970 return rc;
971 }
972 break;
973 }
974 }
975
976 if( !res ){
977 *pbEof = 1;
978 return SQLITE_OK;
979 }
980 }
981
982 return SQLITE_OK;
983 }
984
985 /*
986 ** Cursor pCursor currently points at a node that heads a sub-tree of
987 ** height iHeight (if iHeight==0, then the node is a leaf). Descend
988 ** to point to the left-most cell of the sub-tree that matches the
989 ** configured constraints.
990 */
descendToCell(Rtree * pRtree,RtreeCursor * pCursor,int iHeight,int * pEof)991 static int descendToCell(
992 Rtree *pRtree,
993 RtreeCursor *pCursor,
994 int iHeight,
995 int *pEof /* OUT: Set to true if cannot descend */
996 ){
997 int isEof;
998 int rc;
999 int ii;
1000 RtreeNode *pChild;
1001 sqlite3_int64 iRowid;
1002
1003 RtreeNode *pSavedNode = pCursor->pNode;
1004 int iSavedCell = pCursor->iCell;
1005
1006 assert( iHeight>=0 );
1007
1008 if( iHeight==0 ){
1009 rc = testRtreeEntry(pRtree, pCursor, &isEof);
1010 }else{
1011 rc = testRtreeCell(pRtree, pCursor, &isEof);
1012 }
1013 if( rc!=SQLITE_OK || isEof || iHeight==0 ){
1014 goto descend_to_cell_out;
1015 }
1016
1017 iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
1018 rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
1019 if( rc!=SQLITE_OK ){
1020 goto descend_to_cell_out;
1021 }
1022
1023 nodeRelease(pRtree, pCursor->pNode);
1024 pCursor->pNode = pChild;
1025 isEof = 1;
1026 for(ii=0; isEof && ii<NCELL(pChild); ii++){
1027 pCursor->iCell = ii;
1028 rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
1029 if( rc!=SQLITE_OK ){
1030 goto descend_to_cell_out;
1031 }
1032 }
1033
1034 if( isEof ){
1035 assert( pCursor->pNode==pChild );
1036 nodeReference(pSavedNode);
1037 nodeRelease(pRtree, pChild);
1038 pCursor->pNode = pSavedNode;
1039 pCursor->iCell = iSavedCell;
1040 }
1041
1042 descend_to_cell_out:
1043 *pEof = isEof;
1044 return rc;
1045 }
1046
1047 /*
1048 ** One of the cells in node pNode is guaranteed to have a 64-bit
1049 ** integer value equal to iRowid. Return the index of this cell.
1050 */
nodeRowidIndex(Rtree * pRtree,RtreeNode * pNode,i64 iRowid,int * piIndex)1051 static int nodeRowidIndex(
1052 Rtree *pRtree,
1053 RtreeNode *pNode,
1054 i64 iRowid,
1055 int *piIndex
1056 ){
1057 int ii;
1058 int nCell = NCELL(pNode);
1059 for(ii=0; ii<nCell; ii++){
1060 if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
1061 *piIndex = ii;
1062 return SQLITE_OK;
1063 }
1064 }
1065 return SQLITE_CORRUPT;
1066 }
1067
1068 /*
1069 ** Return the index of the cell containing a pointer to node pNode
1070 ** in its parent. If pNode is the root node, return -1.
1071 */
nodeParentIndex(Rtree * pRtree,RtreeNode * pNode,int * piIndex)1072 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
1073 RtreeNode *pParent = pNode->pParent;
1074 if( pParent ){
1075 return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
1076 }
1077 *piIndex = -1;
1078 return SQLITE_OK;
1079 }
1080
1081 /*
1082 ** Rtree virtual table module xNext method.
1083 */
rtreeNext(sqlite3_vtab_cursor * pVtabCursor)1084 static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
1085 Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
1086 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1087 int rc = SQLITE_OK;
1088
1089 /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
1090 ** already at EOF. It is against the rules to call the xNext() method of
1091 ** a cursor that has already reached EOF.
1092 */
1093 assert( pCsr->pNode );
1094
1095 if( pCsr->iStrategy==1 ){
1096 /* This "scan" is a direct lookup by rowid. There is no next entry. */
1097 nodeRelease(pRtree, pCsr->pNode);
1098 pCsr->pNode = 0;
1099 }else{
1100 /* Move to the next entry that matches the configured constraints. */
1101 int iHeight = 0;
1102 while( pCsr->pNode ){
1103 RtreeNode *pNode = pCsr->pNode;
1104 int nCell = NCELL(pNode);
1105 for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
1106 int isEof;
1107 rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
1108 if( rc!=SQLITE_OK || !isEof ){
1109 return rc;
1110 }
1111 }
1112 pCsr->pNode = pNode->pParent;
1113 rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
1114 if( rc!=SQLITE_OK ){
1115 return rc;
1116 }
1117 nodeReference(pCsr->pNode);
1118 nodeRelease(pRtree, pNode);
1119 iHeight++;
1120 }
1121 }
1122
1123 return rc;
1124 }
1125
1126 /*
1127 ** Rtree virtual table module xRowid method.
1128 */
rtreeRowid(sqlite3_vtab_cursor * pVtabCursor,sqlite_int64 * pRowid)1129 static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
1130 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1131 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1132
1133 assert(pCsr->pNode);
1134 *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1135
1136 return SQLITE_OK;
1137 }
1138
1139 /*
1140 ** Rtree virtual table module xColumn method.
1141 */
rtreeColumn(sqlite3_vtab_cursor * cur,sqlite3_context * ctx,int i)1142 static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1143 Rtree *pRtree = (Rtree *)cur->pVtab;
1144 RtreeCursor *pCsr = (RtreeCursor *)cur;
1145
1146 if( i==0 ){
1147 i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1148 sqlite3_result_int64(ctx, iRowid);
1149 }else{
1150 RtreeCoord c;
1151 nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
1152 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1153 sqlite3_result_double(ctx, c.f);
1154 }else{
1155 assert( pRtree->eCoordType==RTREE_COORD_INT32 );
1156 sqlite3_result_int(ctx, c.i);
1157 }
1158 }
1159
1160 return SQLITE_OK;
1161 }
1162
1163 /*
1164 ** Use nodeAcquire() to obtain the leaf node containing the record with
1165 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
1166 ** return SQLITE_OK. If there is no such record in the table, set
1167 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1168 ** to zero and return an SQLite error code.
1169 */
findLeafNode(Rtree * pRtree,i64 iRowid,RtreeNode ** ppLeaf)1170 static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
1171 int rc;
1172 *ppLeaf = 0;
1173 sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
1174 if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
1175 i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
1176 rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
1177 sqlite3_reset(pRtree->pReadRowid);
1178 }else{
1179 rc = sqlite3_reset(pRtree->pReadRowid);
1180 }
1181 return rc;
1182 }
1183
1184 /*
1185 ** This function is called to configure the RtreeConstraint object passed
1186 ** as the second argument for a MATCH constraint. The value passed as the
1187 ** first argument to this function is the right-hand operand to the MATCH
1188 ** operator.
1189 */
deserializeGeometry(sqlite3_value * pValue,RtreeConstraint * pCons)1190 static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
1191 RtreeMatchArg *p;
1192 sqlite3_rtree_geometry *pGeom;
1193 int nBlob;
1194
1195 /* Check that value is actually a blob. */
1196 if( !sqlite3_value_type(pValue)==SQLITE_BLOB ) return SQLITE_ERROR;
1197
1198 /* Check that the blob is roughly the right size. */
1199 nBlob = sqlite3_value_bytes(pValue);
1200 if( nBlob<(int)sizeof(RtreeMatchArg)
1201 || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0
1202 ){
1203 return SQLITE_ERROR;
1204 }
1205
1206 pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
1207 sizeof(sqlite3_rtree_geometry) + nBlob
1208 );
1209 if( !pGeom ) return SQLITE_NOMEM;
1210 memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
1211 p = (RtreeMatchArg *)&pGeom[1];
1212
1213 memcpy(p, sqlite3_value_blob(pValue), nBlob);
1214 if( p->magic!=RTREE_GEOMETRY_MAGIC
1215 || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double))
1216 ){
1217 sqlite3_free(pGeom);
1218 return SQLITE_ERROR;
1219 }
1220
1221 pGeom->pContext = p->pContext;
1222 pGeom->nParam = p->nParam;
1223 pGeom->aParam = p->aParam;
1224
1225 pCons->xGeom = p->xGeom;
1226 pCons->pGeom = pGeom;
1227 return SQLITE_OK;
1228 }
1229
1230 /*
1231 ** Rtree virtual table module xFilter method.
1232 */
rtreeFilter(sqlite3_vtab_cursor * pVtabCursor,int idxNum,const char * idxStr,int argc,sqlite3_value ** argv)1233 static int rtreeFilter(
1234 sqlite3_vtab_cursor *pVtabCursor,
1235 int idxNum, const char *idxStr,
1236 int argc, sqlite3_value **argv
1237 ){
1238 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1239 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1240
1241 RtreeNode *pRoot = 0;
1242 int ii;
1243 int rc = SQLITE_OK;
1244
1245 rtreeReference(pRtree);
1246
1247 freeCursorConstraints(pCsr);
1248 pCsr->iStrategy = idxNum;
1249
1250 if( idxNum==1 ){
1251 /* Special case - lookup by rowid. */
1252 RtreeNode *pLeaf; /* Leaf on which the required cell resides */
1253 i64 iRowid = sqlite3_value_int64(argv[0]);
1254 rc = findLeafNode(pRtree, iRowid, &pLeaf);
1255 pCsr->pNode = pLeaf;
1256 if( pLeaf ){
1257 assert( rc==SQLITE_OK );
1258 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
1259 }
1260 }else{
1261 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1262 ** with the configured constraints.
1263 */
1264 if( argc>0 ){
1265 pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
1266 pCsr->nConstraint = argc;
1267 if( !pCsr->aConstraint ){
1268 rc = SQLITE_NOMEM;
1269 }else{
1270 memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
1271 assert( (idxStr==0 && argc==0) || (int)strlen(idxStr)==argc*2 );
1272 for(ii=0; ii<argc; ii++){
1273 RtreeConstraint *p = &pCsr->aConstraint[ii];
1274 p->op = idxStr[ii*2];
1275 p->iCoord = idxStr[ii*2+1]-'a';
1276 if( p->op==RTREE_MATCH ){
1277 /* A MATCH operator. The right-hand-side must be a blob that
1278 ** can be cast into an RtreeMatchArg object. One created using
1279 ** an sqlite3_rtree_geometry_callback() SQL user function.
1280 */
1281 rc = deserializeGeometry(argv[ii], p);
1282 if( rc!=SQLITE_OK ){
1283 break;
1284 }
1285 }else{
1286 p->rValue = sqlite3_value_double(argv[ii]);
1287 }
1288 }
1289 }
1290 }
1291
1292 if( rc==SQLITE_OK ){
1293 pCsr->pNode = 0;
1294 rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1295 }
1296 if( rc==SQLITE_OK ){
1297 int isEof = 1;
1298 int nCell = NCELL(pRoot);
1299 pCsr->pNode = pRoot;
1300 for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
1301 assert( pCsr->pNode==pRoot );
1302 rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
1303 if( !isEof ){
1304 break;
1305 }
1306 }
1307 if( rc==SQLITE_OK && isEof ){
1308 assert( pCsr->pNode==pRoot );
1309 nodeRelease(pRtree, pRoot);
1310 pCsr->pNode = 0;
1311 }
1312 assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
1313 }
1314 }
1315
1316 rtreeRelease(pRtree);
1317 return rc;
1318 }
1319
1320 /*
1321 ** Rtree virtual table module xBestIndex method. There are three
1322 ** table scan strategies to choose from (in order from most to
1323 ** least desirable):
1324 **
1325 ** idxNum idxStr Strategy
1326 ** ------------------------------------------------
1327 ** 1 Unused Direct lookup by rowid.
1328 ** 2 See below R-tree query or full-table scan.
1329 ** ------------------------------------------------
1330 **
1331 ** If strategy 1 is used, then idxStr is not meaningful. If strategy
1332 ** 2 is used, idxStr is formatted to contain 2 bytes for each
1333 ** constraint used. The first two bytes of idxStr correspond to
1334 ** the constraint in sqlite3_index_info.aConstraintUsage[] with
1335 ** (argvIndex==1) etc.
1336 **
1337 ** The first of each pair of bytes in idxStr identifies the constraint
1338 ** operator as follows:
1339 **
1340 ** Operator Byte Value
1341 ** ----------------------
1342 ** = 0x41 ('A')
1343 ** <= 0x42 ('B')
1344 ** < 0x43 ('C')
1345 ** >= 0x44 ('D')
1346 ** > 0x45 ('E')
1347 ** MATCH 0x46 ('F')
1348 ** ----------------------
1349 **
1350 ** The second of each pair of bytes identifies the coordinate column
1351 ** to which the constraint applies. The leftmost coordinate column
1352 ** is 'a', the second from the left 'b' etc.
1353 */
rtreeBestIndex(sqlite3_vtab * tab,sqlite3_index_info * pIdxInfo)1354 static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
1355 int rc = SQLITE_OK;
1356 int ii;
1357
1358 int iIdx = 0;
1359 char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
1360 memset(zIdxStr, 0, sizeof(zIdxStr));
1361 UNUSED_PARAMETER(tab);
1362
1363 assert( pIdxInfo->idxStr==0 );
1364 for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
1365 struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
1366
1367 if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
1368 /* We have an equality constraint on the rowid. Use strategy 1. */
1369 int jj;
1370 for(jj=0; jj<ii; jj++){
1371 pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
1372 pIdxInfo->aConstraintUsage[jj].omit = 0;
1373 }
1374 pIdxInfo->idxNum = 1;
1375 pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
1376 pIdxInfo->aConstraintUsage[jj].omit = 1;
1377
1378 /* This strategy involves a two rowid lookups on an B-Tree structures
1379 ** and then a linear search of an R-Tree node. This should be
1380 ** considered almost as quick as a direct rowid lookup (for which
1381 ** sqlite uses an internal cost of 0.0).
1382 */
1383 pIdxInfo->estimatedCost = 10.0;
1384 return SQLITE_OK;
1385 }
1386
1387 if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){
1388 u8 op;
1389 switch( p->op ){
1390 case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
1391 case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
1392 case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
1393 case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
1394 case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
1395 default:
1396 assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
1397 op = RTREE_MATCH;
1398 break;
1399 }
1400 zIdxStr[iIdx++] = op;
1401 zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
1402 pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
1403 pIdxInfo->aConstraintUsage[ii].omit = 1;
1404 }
1405 }
1406
1407 pIdxInfo->idxNum = 2;
1408 pIdxInfo->needToFreeIdxStr = 1;
1409 if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
1410 return SQLITE_NOMEM;
1411 }
1412 assert( iIdx>=0 );
1413 pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
1414 return rc;
1415 }
1416
1417 /*
1418 ** Return the N-dimensional volumn of the cell stored in *p.
1419 */
cellArea(Rtree * pRtree,RtreeCell * p)1420 static float cellArea(Rtree *pRtree, RtreeCell *p){
1421 float area = 1.0;
1422 int ii;
1423 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1424 area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
1425 }
1426 return area;
1427 }
1428
1429 /*
1430 ** Return the margin length of cell p. The margin length is the sum
1431 ** of the objects size in each dimension.
1432 */
cellMargin(Rtree * pRtree,RtreeCell * p)1433 static float cellMargin(Rtree *pRtree, RtreeCell *p){
1434 float margin = 0.0;
1435 int ii;
1436 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1437 margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
1438 }
1439 return margin;
1440 }
1441
1442 /*
1443 ** Store the union of cells p1 and p2 in p1.
1444 */
cellUnion(Rtree * pRtree,RtreeCell * p1,RtreeCell * p2)1445 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1446 int ii;
1447 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1448 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1449 p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
1450 p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
1451 }
1452 }else{
1453 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1454 p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
1455 p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
1456 }
1457 }
1458 }
1459
1460 /*
1461 ** Return true if the area covered by p2 is a subset of the area covered
1462 ** by p1. False otherwise.
1463 */
cellContains(Rtree * pRtree,RtreeCell * p1,RtreeCell * p2)1464 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1465 int ii;
1466 int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
1467 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1468 RtreeCoord *a1 = &p1->aCoord[ii];
1469 RtreeCoord *a2 = &p2->aCoord[ii];
1470 if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f))
1471 || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i))
1472 ){
1473 return 0;
1474 }
1475 }
1476 return 1;
1477 }
1478
1479 /*
1480 ** Return the amount cell p would grow by if it were unioned with pCell.
1481 */
cellGrowth(Rtree * pRtree,RtreeCell * p,RtreeCell * pCell)1482 static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
1483 float area;
1484 RtreeCell cell;
1485 memcpy(&cell, p, sizeof(RtreeCell));
1486 area = cellArea(pRtree, &cell);
1487 cellUnion(pRtree, &cell, pCell);
1488 return (cellArea(pRtree, &cell)-area);
1489 }
1490
1491 #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
cellOverlap(Rtree * pRtree,RtreeCell * p,RtreeCell * aCell,int nCell,int iExclude)1492 static float cellOverlap(
1493 Rtree *pRtree,
1494 RtreeCell *p,
1495 RtreeCell *aCell,
1496 int nCell,
1497 int iExclude
1498 ){
1499 int ii;
1500 float overlap = 0.0;
1501 for(ii=0; ii<nCell; ii++){
1502 #if VARIANT_RSTARTREE_CHOOSESUBTREE
1503 if( ii!=iExclude )
1504 #else
1505 assert( iExclude==-1 );
1506 UNUSED_PARAMETER(iExclude);
1507 #endif
1508 {
1509 int jj;
1510 float o = 1.0;
1511 for(jj=0; jj<(pRtree->nDim*2); jj+=2){
1512 double x1;
1513 double x2;
1514
1515 x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
1516 x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
1517
1518 if( x2<x1 ){
1519 o = 0.0;
1520 break;
1521 }else{
1522 o = o * (x2-x1);
1523 }
1524 }
1525 overlap += o;
1526 }
1527 }
1528 return overlap;
1529 }
1530 #endif
1531
1532 #if VARIANT_RSTARTREE_CHOOSESUBTREE
cellOverlapEnlargement(Rtree * pRtree,RtreeCell * p,RtreeCell * pInsert,RtreeCell * aCell,int nCell,int iExclude)1533 static float cellOverlapEnlargement(
1534 Rtree *pRtree,
1535 RtreeCell *p,
1536 RtreeCell *pInsert,
1537 RtreeCell *aCell,
1538 int nCell,
1539 int iExclude
1540 ){
1541 float before;
1542 float after;
1543 before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1544 cellUnion(pRtree, p, pInsert);
1545 after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1546 return after-before;
1547 }
1548 #endif
1549
1550
1551 /*
1552 ** This function implements the ChooseLeaf algorithm from Gutman[84].
1553 ** ChooseSubTree in r*tree terminology.
1554 */
ChooseLeaf(Rtree * pRtree,RtreeCell * pCell,int iHeight,RtreeNode ** ppLeaf)1555 static int ChooseLeaf(
1556 Rtree *pRtree, /* Rtree table */
1557 RtreeCell *pCell, /* Cell to insert into rtree */
1558 int iHeight, /* Height of sub-tree rooted at pCell */
1559 RtreeNode **ppLeaf /* OUT: Selected leaf page */
1560 ){
1561 int rc;
1562 int ii;
1563 RtreeNode *pNode;
1564 rc = nodeAcquire(pRtree, 1, 0, &pNode);
1565
1566 for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
1567 int iCell;
1568 sqlite3_int64 iBest;
1569
1570 float fMinGrowth;
1571 float fMinArea;
1572 float fMinOverlap;
1573
1574 int nCell = NCELL(pNode);
1575 RtreeCell cell;
1576 RtreeNode *pChild;
1577
1578 RtreeCell *aCell = 0;
1579
1580 #if VARIANT_RSTARTREE_CHOOSESUBTREE
1581 if( ii==(pRtree->iDepth-1) ){
1582 int jj;
1583 aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
1584 if( !aCell ){
1585 rc = SQLITE_NOMEM;
1586 nodeRelease(pRtree, pNode);
1587 pNode = 0;
1588 continue;
1589 }
1590 for(jj=0; jj<nCell; jj++){
1591 nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
1592 }
1593 }
1594 #endif
1595
1596 /* Select the child node which will be enlarged the least if pCell
1597 ** is inserted into it. Resolve ties by choosing the entry with
1598 ** the smallest area.
1599 */
1600 for(iCell=0; iCell<nCell; iCell++){
1601 int bBest = 0;
1602 float growth;
1603 float area;
1604 float overlap = 0.0;
1605 nodeGetCell(pRtree, pNode, iCell, &cell);
1606 growth = cellGrowth(pRtree, &cell, pCell);
1607 area = cellArea(pRtree, &cell);
1608
1609 #if VARIANT_RSTARTREE_CHOOSESUBTREE
1610 if( ii==(pRtree->iDepth-1) ){
1611 overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
1612 }
1613 if( (iCell==0)
1614 || (overlap<fMinOverlap)
1615 || (overlap==fMinOverlap && growth<fMinGrowth)
1616 || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
1617 ){
1618 bBest = 1;
1619 }
1620 #else
1621 if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
1622 bBest = 1;
1623 }
1624 #endif
1625 if( bBest ){
1626 fMinOverlap = overlap;
1627 fMinGrowth = growth;
1628 fMinArea = area;
1629 iBest = cell.iRowid;
1630 }
1631 }
1632
1633 sqlite3_free(aCell);
1634 rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
1635 nodeRelease(pRtree, pNode);
1636 pNode = pChild;
1637 }
1638
1639 *ppLeaf = pNode;
1640 return rc;
1641 }
1642
1643 /*
1644 ** A cell with the same content as pCell has just been inserted into
1645 ** the node pNode. This function updates the bounding box cells in
1646 ** all ancestor elements.
1647 */
AdjustTree(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell)1648 static int AdjustTree(
1649 Rtree *pRtree, /* Rtree table */
1650 RtreeNode *pNode, /* Adjust ancestry of this node. */
1651 RtreeCell *pCell /* This cell was just inserted */
1652 ){
1653 RtreeNode *p = pNode;
1654 while( p->pParent ){
1655 RtreeNode *pParent = p->pParent;
1656 RtreeCell cell;
1657 int iCell;
1658
1659 if( nodeParentIndex(pRtree, p, &iCell) ){
1660 return SQLITE_CORRUPT;
1661 }
1662
1663 nodeGetCell(pRtree, pParent, iCell, &cell);
1664 if( !cellContains(pRtree, &cell, pCell) ){
1665 cellUnion(pRtree, &cell, pCell);
1666 nodeOverwriteCell(pRtree, pParent, &cell, iCell);
1667 }
1668
1669 p = pParent;
1670 }
1671 return SQLITE_OK;
1672 }
1673
1674 /*
1675 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
1676 */
rowidWrite(Rtree * pRtree,sqlite3_int64 iRowid,sqlite3_int64 iNode)1677 static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
1678 sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
1679 sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
1680 sqlite3_step(pRtree->pWriteRowid);
1681 return sqlite3_reset(pRtree->pWriteRowid);
1682 }
1683
1684 /*
1685 ** Write mapping (iNode->iPar) to the <rtree>_parent table.
1686 */
parentWrite(Rtree * pRtree,sqlite3_int64 iNode,sqlite3_int64 iPar)1687 static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
1688 sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
1689 sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
1690 sqlite3_step(pRtree->pWriteParent);
1691 return sqlite3_reset(pRtree->pWriteParent);
1692 }
1693
1694 static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
1695
1696 #if VARIANT_GUTTMAN_LINEAR_SPLIT
1697 /*
1698 ** Implementation of the linear variant of the PickNext() function from
1699 ** Guttman[84].
1700 */
LinearPickNext(Rtree * pRtree,RtreeCell * aCell,int nCell,RtreeCell * pLeftBox,RtreeCell * pRightBox,int * aiUsed)1701 static RtreeCell *LinearPickNext(
1702 Rtree *pRtree,
1703 RtreeCell *aCell,
1704 int nCell,
1705 RtreeCell *pLeftBox,
1706 RtreeCell *pRightBox,
1707 int *aiUsed
1708 ){
1709 int ii;
1710 for(ii=0; aiUsed[ii]; ii++);
1711 aiUsed[ii] = 1;
1712 return &aCell[ii];
1713 }
1714
1715 /*
1716 ** Implementation of the linear variant of the PickSeeds() function from
1717 ** Guttman[84].
1718 */
LinearPickSeeds(Rtree * pRtree,RtreeCell * aCell,int nCell,int * piLeftSeed,int * piRightSeed)1719 static void LinearPickSeeds(
1720 Rtree *pRtree,
1721 RtreeCell *aCell,
1722 int nCell,
1723 int *piLeftSeed,
1724 int *piRightSeed
1725 ){
1726 int i;
1727 int iLeftSeed = 0;
1728 int iRightSeed = 1;
1729 float maxNormalInnerWidth = 0.0;
1730
1731 /* Pick two "seed" cells from the array of cells. The algorithm used
1732 ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
1733 ** indices of the two seed cells in the array are stored in local
1734 ** variables iLeftSeek and iRightSeed.
1735 */
1736 for(i=0; i<pRtree->nDim; i++){
1737 float x1 = DCOORD(aCell[0].aCoord[i*2]);
1738 float x2 = DCOORD(aCell[0].aCoord[i*2+1]);
1739 float x3 = x1;
1740 float x4 = x2;
1741 int jj;
1742
1743 int iCellLeft = 0;
1744 int iCellRight = 0;
1745
1746 for(jj=1; jj<nCell; jj++){
1747 float left = DCOORD(aCell[jj].aCoord[i*2]);
1748 float right = DCOORD(aCell[jj].aCoord[i*2+1]);
1749
1750 if( left<x1 ) x1 = left;
1751 if( right>x4 ) x4 = right;
1752 if( left>x3 ){
1753 x3 = left;
1754 iCellRight = jj;
1755 }
1756 if( right<x2 ){
1757 x2 = right;
1758 iCellLeft = jj;
1759 }
1760 }
1761
1762 if( x4!=x1 ){
1763 float normalwidth = (x3 - x2) / (x4 - x1);
1764 if( normalwidth>maxNormalInnerWidth ){
1765 iLeftSeed = iCellLeft;
1766 iRightSeed = iCellRight;
1767 }
1768 }
1769 }
1770
1771 *piLeftSeed = iLeftSeed;
1772 *piRightSeed = iRightSeed;
1773 }
1774 #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
1775
1776 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT
1777 /*
1778 ** Implementation of the quadratic variant of the PickNext() function from
1779 ** Guttman[84].
1780 */
QuadraticPickNext(Rtree * pRtree,RtreeCell * aCell,int nCell,RtreeCell * pLeftBox,RtreeCell * pRightBox,int * aiUsed)1781 static RtreeCell *QuadraticPickNext(
1782 Rtree *pRtree,
1783 RtreeCell *aCell,
1784 int nCell,
1785 RtreeCell *pLeftBox,
1786 RtreeCell *pRightBox,
1787 int *aiUsed
1788 ){
1789 #define FABS(a) ((a)<0.0?-1.0*(a):(a))
1790
1791 int iSelect = -1;
1792 float fDiff;
1793 int ii;
1794 for(ii=0; ii<nCell; ii++){
1795 if( aiUsed[ii]==0 ){
1796 float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1797 float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1798 float diff = FABS(right-left);
1799 if( iSelect<0 || diff>fDiff ){
1800 fDiff = diff;
1801 iSelect = ii;
1802 }
1803 }
1804 }
1805 aiUsed[iSelect] = 1;
1806 return &aCell[iSelect];
1807 }
1808
1809 /*
1810 ** Implementation of the quadratic variant of the PickSeeds() function from
1811 ** Guttman[84].
1812 */
QuadraticPickSeeds(Rtree * pRtree,RtreeCell * aCell,int nCell,int * piLeftSeed,int * piRightSeed)1813 static void QuadraticPickSeeds(
1814 Rtree *pRtree,
1815 RtreeCell *aCell,
1816 int nCell,
1817 int *piLeftSeed,
1818 int *piRightSeed
1819 ){
1820 int ii;
1821 int jj;
1822
1823 int iLeftSeed = 0;
1824 int iRightSeed = 1;
1825 float fWaste = 0.0;
1826
1827 for(ii=0; ii<nCell; ii++){
1828 for(jj=ii+1; jj<nCell; jj++){
1829 float right = cellArea(pRtree, &aCell[jj]);
1830 float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
1831 float waste = growth - right;
1832
1833 if( waste>fWaste ){
1834 iLeftSeed = ii;
1835 iRightSeed = jj;
1836 fWaste = waste;
1837 }
1838 }
1839 }
1840
1841 *piLeftSeed = iLeftSeed;
1842 *piRightSeed = iRightSeed;
1843 }
1844 #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
1845
1846 /*
1847 ** Arguments aIdx, aDistance and aSpare all point to arrays of size
1848 ** nIdx. The aIdx array contains the set of integers from 0 to
1849 ** (nIdx-1) in no particular order. This function sorts the values
1850 ** in aIdx according to the indexed values in aDistance. For
1851 ** example, assuming the inputs:
1852 **
1853 ** aIdx = { 0, 1, 2, 3 }
1854 ** aDistance = { 5.0, 2.0, 7.0, 6.0 }
1855 **
1856 ** this function sets the aIdx array to contain:
1857 **
1858 ** aIdx = { 0, 1, 2, 3 }
1859 **
1860 ** The aSpare array is used as temporary working space by the
1861 ** sorting algorithm.
1862 */
SortByDistance(int * aIdx,int nIdx,float * aDistance,int * aSpare)1863 static void SortByDistance(
1864 int *aIdx,
1865 int nIdx,
1866 float *aDistance,
1867 int *aSpare
1868 ){
1869 if( nIdx>1 ){
1870 int iLeft = 0;
1871 int iRight = 0;
1872
1873 int nLeft = nIdx/2;
1874 int nRight = nIdx-nLeft;
1875 int *aLeft = aIdx;
1876 int *aRight = &aIdx[nLeft];
1877
1878 SortByDistance(aLeft, nLeft, aDistance, aSpare);
1879 SortByDistance(aRight, nRight, aDistance, aSpare);
1880
1881 memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1882 aLeft = aSpare;
1883
1884 while( iLeft<nLeft || iRight<nRight ){
1885 if( iLeft==nLeft ){
1886 aIdx[iLeft+iRight] = aRight[iRight];
1887 iRight++;
1888 }else if( iRight==nRight ){
1889 aIdx[iLeft+iRight] = aLeft[iLeft];
1890 iLeft++;
1891 }else{
1892 float fLeft = aDistance[aLeft[iLeft]];
1893 float fRight = aDistance[aRight[iRight]];
1894 if( fLeft<fRight ){
1895 aIdx[iLeft+iRight] = aLeft[iLeft];
1896 iLeft++;
1897 }else{
1898 aIdx[iLeft+iRight] = aRight[iRight];
1899 iRight++;
1900 }
1901 }
1902 }
1903
1904 #if 0
1905 /* Check that the sort worked */
1906 {
1907 int jj;
1908 for(jj=1; jj<nIdx; jj++){
1909 float left = aDistance[aIdx[jj-1]];
1910 float right = aDistance[aIdx[jj]];
1911 assert( left<=right );
1912 }
1913 }
1914 #endif
1915 }
1916 }
1917
1918 /*
1919 ** Arguments aIdx, aCell and aSpare all point to arrays of size
1920 ** nIdx. The aIdx array contains the set of integers from 0 to
1921 ** (nIdx-1) in no particular order. This function sorts the values
1922 ** in aIdx according to dimension iDim of the cells in aCell. The
1923 ** minimum value of dimension iDim is considered first, the
1924 ** maximum used to break ties.
1925 **
1926 ** The aSpare array is used as temporary working space by the
1927 ** sorting algorithm.
1928 */
SortByDimension(Rtree * pRtree,int * aIdx,int nIdx,int iDim,RtreeCell * aCell,int * aSpare)1929 static void SortByDimension(
1930 Rtree *pRtree,
1931 int *aIdx,
1932 int nIdx,
1933 int iDim,
1934 RtreeCell *aCell,
1935 int *aSpare
1936 ){
1937 if( nIdx>1 ){
1938
1939 int iLeft = 0;
1940 int iRight = 0;
1941
1942 int nLeft = nIdx/2;
1943 int nRight = nIdx-nLeft;
1944 int *aLeft = aIdx;
1945 int *aRight = &aIdx[nLeft];
1946
1947 SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
1948 SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
1949
1950 memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1951 aLeft = aSpare;
1952 while( iLeft<nLeft || iRight<nRight ){
1953 double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
1954 double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
1955 double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
1956 double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
1957 if( (iLeft!=nLeft) && ((iRight==nRight)
1958 || (xleft1<xright1)
1959 || (xleft1==xright1 && xleft2<xright2)
1960 )){
1961 aIdx[iLeft+iRight] = aLeft[iLeft];
1962 iLeft++;
1963 }else{
1964 aIdx[iLeft+iRight] = aRight[iRight];
1965 iRight++;
1966 }
1967 }
1968
1969 #if 0
1970 /* Check that the sort worked */
1971 {
1972 int jj;
1973 for(jj=1; jj<nIdx; jj++){
1974 float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
1975 float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
1976 float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
1977 float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
1978 assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
1979 }
1980 }
1981 #endif
1982 }
1983 }
1984
1985 #if VARIANT_RSTARTREE_SPLIT
1986 /*
1987 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
1988 */
splitNodeStartree(Rtree * pRtree,RtreeCell * aCell,int nCell,RtreeNode * pLeft,RtreeNode * pRight,RtreeCell * pBboxLeft,RtreeCell * pBboxRight)1989 static int splitNodeStartree(
1990 Rtree *pRtree,
1991 RtreeCell *aCell,
1992 int nCell,
1993 RtreeNode *pLeft,
1994 RtreeNode *pRight,
1995 RtreeCell *pBboxLeft,
1996 RtreeCell *pBboxRight
1997 ){
1998 int **aaSorted;
1999 int *aSpare;
2000 int ii;
2001
2002 int iBestDim;
2003 int iBestSplit;
2004 float fBestMargin;
2005
2006 int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
2007
2008 aaSorted = (int **)sqlite3_malloc(nByte);
2009 if( !aaSorted ){
2010 return SQLITE_NOMEM;
2011 }
2012
2013 aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
2014 memset(aaSorted, 0, nByte);
2015 for(ii=0; ii<pRtree->nDim; ii++){
2016 int jj;
2017 aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
2018 for(jj=0; jj<nCell; jj++){
2019 aaSorted[ii][jj] = jj;
2020 }
2021 SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
2022 }
2023
2024 for(ii=0; ii<pRtree->nDim; ii++){
2025 float margin = 0.0;
2026 float fBestOverlap;
2027 float fBestArea;
2028 int iBestLeft;
2029 int nLeft;
2030
2031 for(
2032 nLeft=RTREE_MINCELLS(pRtree);
2033 nLeft<=(nCell-RTREE_MINCELLS(pRtree));
2034 nLeft++
2035 ){
2036 RtreeCell left;
2037 RtreeCell right;
2038 int kk;
2039 float overlap;
2040 float area;
2041
2042 memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
2043 memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
2044 for(kk=1; kk<(nCell-1); kk++){
2045 if( kk<nLeft ){
2046 cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
2047 }else{
2048 cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
2049 }
2050 }
2051 margin += cellMargin(pRtree, &left);
2052 margin += cellMargin(pRtree, &right);
2053 overlap = cellOverlap(pRtree, &left, &right, 1, -1);
2054 area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
2055 if( (nLeft==RTREE_MINCELLS(pRtree))
2056 || (overlap<fBestOverlap)
2057 || (overlap==fBestOverlap && area<fBestArea)
2058 ){
2059 iBestLeft = nLeft;
2060 fBestOverlap = overlap;
2061 fBestArea = area;
2062 }
2063 }
2064
2065 if( ii==0 || margin<fBestMargin ){
2066 iBestDim = ii;
2067 fBestMargin = margin;
2068 iBestSplit = iBestLeft;
2069 }
2070 }
2071
2072 memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
2073 memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
2074 for(ii=0; ii<nCell; ii++){
2075 RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
2076 RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
2077 RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
2078 nodeInsertCell(pRtree, pTarget, pCell);
2079 cellUnion(pRtree, pBbox, pCell);
2080 }
2081
2082 sqlite3_free(aaSorted);
2083 return SQLITE_OK;
2084 }
2085 #endif
2086
2087 #if VARIANT_GUTTMAN_SPLIT
2088 /*
2089 ** Implementation of the regular R-tree SplitNode from Guttman[1984].
2090 */
splitNodeGuttman(Rtree * pRtree,RtreeCell * aCell,int nCell,RtreeNode * pLeft,RtreeNode * pRight,RtreeCell * pBboxLeft,RtreeCell * pBboxRight)2091 static int splitNodeGuttman(
2092 Rtree *pRtree,
2093 RtreeCell *aCell,
2094 int nCell,
2095 RtreeNode *pLeft,
2096 RtreeNode *pRight,
2097 RtreeCell *pBboxLeft,
2098 RtreeCell *pBboxRight
2099 ){
2100 int iLeftSeed = 0;
2101 int iRightSeed = 1;
2102 int *aiUsed;
2103 int i;
2104
2105 aiUsed = sqlite3_malloc(sizeof(int)*nCell);
2106 if( !aiUsed ){
2107 return SQLITE_NOMEM;
2108 }
2109 memset(aiUsed, 0, sizeof(int)*nCell);
2110
2111 PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
2112
2113 memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
2114 memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
2115 nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
2116 nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
2117 aiUsed[iLeftSeed] = 1;
2118 aiUsed[iRightSeed] = 1;
2119
2120 for(i=nCell-2; i>0; i--){
2121 RtreeCell *pNext;
2122 pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
2123 float diff =
2124 cellGrowth(pRtree, pBboxLeft, pNext) -
2125 cellGrowth(pRtree, pBboxRight, pNext)
2126 ;
2127 if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
2128 || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
2129 ){
2130 nodeInsertCell(pRtree, pRight, pNext);
2131 cellUnion(pRtree, pBboxRight, pNext);
2132 }else{
2133 nodeInsertCell(pRtree, pLeft, pNext);
2134 cellUnion(pRtree, pBboxLeft, pNext);
2135 }
2136 }
2137
2138 sqlite3_free(aiUsed);
2139 return SQLITE_OK;
2140 }
2141 #endif
2142
updateMapping(Rtree * pRtree,i64 iRowid,RtreeNode * pNode,int iHeight)2143 static int updateMapping(
2144 Rtree *pRtree,
2145 i64 iRowid,
2146 RtreeNode *pNode,
2147 int iHeight
2148 ){
2149 int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
2150 xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
2151 if( iHeight>0 ){
2152 RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
2153 if( pChild ){
2154 nodeRelease(pRtree, pChild->pParent);
2155 nodeReference(pNode);
2156 pChild->pParent = pNode;
2157 }
2158 }
2159 return xSetMapping(pRtree, iRowid, pNode->iNode);
2160 }
2161
SplitNode(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell,int iHeight)2162 static int SplitNode(
2163 Rtree *pRtree,
2164 RtreeNode *pNode,
2165 RtreeCell *pCell,
2166 int iHeight
2167 ){
2168 int i;
2169 int newCellIsRight = 0;
2170
2171 int rc = SQLITE_OK;
2172 int nCell = NCELL(pNode);
2173 RtreeCell *aCell;
2174 int *aiUsed;
2175
2176 RtreeNode *pLeft = 0;
2177 RtreeNode *pRight = 0;
2178
2179 RtreeCell leftbbox;
2180 RtreeCell rightbbox;
2181
2182 /* Allocate an array and populate it with a copy of pCell and
2183 ** all cells from node pLeft. Then zero the original node.
2184 */
2185 aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
2186 if( !aCell ){
2187 rc = SQLITE_NOMEM;
2188 goto splitnode_out;
2189 }
2190 aiUsed = (int *)&aCell[nCell+1];
2191 memset(aiUsed, 0, sizeof(int)*(nCell+1));
2192 for(i=0; i<nCell; i++){
2193 nodeGetCell(pRtree, pNode, i, &aCell[i]);
2194 }
2195 nodeZero(pRtree, pNode);
2196 memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
2197 nCell++;
2198
2199 if( pNode->iNode==1 ){
2200 pRight = nodeNew(pRtree, pNode);
2201 pLeft = nodeNew(pRtree, pNode);
2202 pRtree->iDepth++;
2203 pNode->isDirty = 1;
2204 writeInt16(pNode->zData, pRtree->iDepth);
2205 }else{
2206 pLeft = pNode;
2207 pRight = nodeNew(pRtree, pLeft->pParent);
2208 nodeReference(pLeft);
2209 }
2210
2211 if( !pLeft || !pRight ){
2212 rc = SQLITE_NOMEM;
2213 goto splitnode_out;
2214 }
2215
2216 memset(pLeft->zData, 0, pRtree->iNodeSize);
2217 memset(pRight->zData, 0, pRtree->iNodeSize);
2218
2219 rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
2220 if( rc!=SQLITE_OK ){
2221 goto splitnode_out;
2222 }
2223
2224 /* Ensure both child nodes have node numbers assigned to them by calling
2225 ** nodeWrite(). Node pRight always needs a node number, as it was created
2226 ** by nodeNew() above. But node pLeft sometimes already has a node number.
2227 ** In this case avoid the all to nodeWrite().
2228 */
2229 if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
2230 || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
2231 ){
2232 goto splitnode_out;
2233 }
2234
2235 rightbbox.iRowid = pRight->iNode;
2236 leftbbox.iRowid = pLeft->iNode;
2237
2238 if( pNode->iNode==1 ){
2239 rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
2240 if( rc!=SQLITE_OK ){
2241 goto splitnode_out;
2242 }
2243 }else{
2244 RtreeNode *pParent = pLeft->pParent;
2245 int iCell;
2246 rc = nodeParentIndex(pRtree, pLeft, &iCell);
2247 if( rc==SQLITE_OK ){
2248 nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
2249 rc = AdjustTree(pRtree, pParent, &leftbbox);
2250 }
2251 if( rc!=SQLITE_OK ){
2252 goto splitnode_out;
2253 }
2254 }
2255 if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
2256 goto splitnode_out;
2257 }
2258
2259 for(i=0; i<NCELL(pRight); i++){
2260 i64 iRowid = nodeGetRowid(pRtree, pRight, i);
2261 rc = updateMapping(pRtree, iRowid, pRight, iHeight);
2262 if( iRowid==pCell->iRowid ){
2263 newCellIsRight = 1;
2264 }
2265 if( rc!=SQLITE_OK ){
2266 goto splitnode_out;
2267 }
2268 }
2269 if( pNode->iNode==1 ){
2270 for(i=0; i<NCELL(pLeft); i++){
2271 i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
2272 rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
2273 if( rc!=SQLITE_OK ){
2274 goto splitnode_out;
2275 }
2276 }
2277 }else if( newCellIsRight==0 ){
2278 rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
2279 }
2280
2281 if( rc==SQLITE_OK ){
2282 rc = nodeRelease(pRtree, pRight);
2283 pRight = 0;
2284 }
2285 if( rc==SQLITE_OK ){
2286 rc = nodeRelease(pRtree, pLeft);
2287 pLeft = 0;
2288 }
2289
2290 splitnode_out:
2291 nodeRelease(pRtree, pRight);
2292 nodeRelease(pRtree, pLeft);
2293 sqlite3_free(aCell);
2294 return rc;
2295 }
2296
2297 /*
2298 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2299 ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2300 ** the pLeaf->pParent chain all the way up to the root node.
2301 **
2302 ** This operation is required when a row is deleted (or updated - an update
2303 ** is implemented as a delete followed by an insert). SQLite provides the
2304 ** rowid of the row to delete, which can be used to find the leaf on which
2305 ** the entry resides (argument pLeaf). Once the leaf is located, this
2306 ** function is called to determine its ancestry.
2307 */
fixLeafParent(Rtree * pRtree,RtreeNode * pLeaf)2308 static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
2309 int rc = SQLITE_OK;
2310 RtreeNode *pChild = pLeaf;
2311 while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
2312 int rc2 = SQLITE_OK; /* sqlite3_reset() return code */
2313 sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
2314 rc = sqlite3_step(pRtree->pReadParent);
2315 if( rc==SQLITE_ROW ){
2316 RtreeNode *pTest; /* Used to test for reference loops */
2317 i64 iNode; /* Node number of parent node */
2318
2319 /* Before setting pChild->pParent, test that we are not creating a
2320 ** loop of references (as we would if, say, pChild==pParent). We don't
2321 ** want to do this as it leads to a memory leak when trying to delete
2322 ** the referenced counted node structures.
2323 */
2324 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
2325 for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
2326 if( !pTest ){
2327 rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
2328 }
2329 }
2330 rc = sqlite3_reset(pRtree->pReadParent);
2331 if( rc==SQLITE_OK ) rc = rc2;
2332 if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT;
2333 pChild = pChild->pParent;
2334 }
2335 return rc;
2336 }
2337
2338 static int deleteCell(Rtree *, RtreeNode *, int, int);
2339
removeNode(Rtree * pRtree,RtreeNode * pNode,int iHeight)2340 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
2341 int rc;
2342 int rc2;
2343 RtreeNode *pParent;
2344 int iCell;
2345
2346 assert( pNode->nRef==1 );
2347
2348 /* Remove the entry in the parent cell. */
2349 rc = nodeParentIndex(pRtree, pNode, &iCell);
2350 if( rc==SQLITE_OK ){
2351 pParent = pNode->pParent;
2352 pNode->pParent = 0;
2353 rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
2354 }
2355 rc2 = nodeRelease(pRtree, pParent);
2356 if( rc==SQLITE_OK ){
2357 rc = rc2;
2358 }
2359 if( rc!=SQLITE_OK ){
2360 return rc;
2361 }
2362
2363 /* Remove the xxx_node entry. */
2364 sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
2365 sqlite3_step(pRtree->pDeleteNode);
2366 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
2367 return rc;
2368 }
2369
2370 /* Remove the xxx_parent entry. */
2371 sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
2372 sqlite3_step(pRtree->pDeleteParent);
2373 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
2374 return rc;
2375 }
2376
2377 /* Remove the node from the in-memory hash table and link it into
2378 ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2379 */
2380 nodeHashDelete(pRtree, pNode);
2381 pNode->iNode = iHeight;
2382 pNode->pNext = pRtree->pDeleted;
2383 pNode->nRef++;
2384 pRtree->pDeleted = pNode;
2385
2386 return SQLITE_OK;
2387 }
2388
fixBoundingBox(Rtree * pRtree,RtreeNode * pNode)2389 static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
2390 RtreeNode *pParent = pNode->pParent;
2391 int rc = SQLITE_OK;
2392 if( pParent ){
2393 int ii;
2394 int nCell = NCELL(pNode);
2395 RtreeCell box; /* Bounding box for pNode */
2396 nodeGetCell(pRtree, pNode, 0, &box);
2397 for(ii=1; ii<nCell; ii++){
2398 RtreeCell cell;
2399 nodeGetCell(pRtree, pNode, ii, &cell);
2400 cellUnion(pRtree, &box, &cell);
2401 }
2402 box.iRowid = pNode->iNode;
2403 rc = nodeParentIndex(pRtree, pNode, &ii);
2404 if( rc==SQLITE_OK ){
2405 nodeOverwriteCell(pRtree, pParent, &box, ii);
2406 rc = fixBoundingBox(pRtree, pParent);
2407 }
2408 }
2409 return rc;
2410 }
2411
2412 /*
2413 ** Delete the cell at index iCell of node pNode. After removing the
2414 ** cell, adjust the r-tree data structure if required.
2415 */
deleteCell(Rtree * pRtree,RtreeNode * pNode,int iCell,int iHeight)2416 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
2417 RtreeNode *pParent;
2418 int rc;
2419
2420 if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
2421 return rc;
2422 }
2423
2424 /* Remove the cell from the node. This call just moves bytes around
2425 ** the in-memory node image, so it cannot fail.
2426 */
2427 nodeDeleteCell(pRtree, pNode, iCell);
2428
2429 /* If the node is not the tree root and now has less than the minimum
2430 ** number of cells, remove it from the tree. Otherwise, update the
2431 ** cell in the parent node so that it tightly contains the updated
2432 ** node.
2433 */
2434 pParent = pNode->pParent;
2435 assert( pParent || pNode->iNode==1 );
2436 if( pParent ){
2437 if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
2438 rc = removeNode(pRtree, pNode, iHeight);
2439 }else{
2440 rc = fixBoundingBox(pRtree, pNode);
2441 }
2442 }
2443
2444 return rc;
2445 }
2446
Reinsert(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell,int iHeight)2447 static int Reinsert(
2448 Rtree *pRtree,
2449 RtreeNode *pNode,
2450 RtreeCell *pCell,
2451 int iHeight
2452 ){
2453 int *aOrder;
2454 int *aSpare;
2455 RtreeCell *aCell;
2456 float *aDistance;
2457 int nCell;
2458 float aCenterCoord[RTREE_MAX_DIMENSIONS];
2459 int iDim;
2460 int ii;
2461 int rc = SQLITE_OK;
2462
2463 memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
2464
2465 nCell = NCELL(pNode)+1;
2466
2467 /* Allocate the buffers used by this operation. The allocation is
2468 ** relinquished before this function returns.
2469 */
2470 aCell = (RtreeCell *)sqlite3_malloc(nCell * (
2471 sizeof(RtreeCell) + /* aCell array */
2472 sizeof(int) + /* aOrder array */
2473 sizeof(int) + /* aSpare array */
2474 sizeof(float) /* aDistance array */
2475 ));
2476 if( !aCell ){
2477 return SQLITE_NOMEM;
2478 }
2479 aOrder = (int *)&aCell[nCell];
2480 aSpare = (int *)&aOrder[nCell];
2481 aDistance = (float *)&aSpare[nCell];
2482
2483 for(ii=0; ii<nCell; ii++){
2484 if( ii==(nCell-1) ){
2485 memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
2486 }else{
2487 nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
2488 }
2489 aOrder[ii] = ii;
2490 for(iDim=0; iDim<pRtree->nDim; iDim++){
2491 aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]);
2492 aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]);
2493 }
2494 }
2495 for(iDim=0; iDim<pRtree->nDim; iDim++){
2496 aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
2497 }
2498
2499 for(ii=0; ii<nCell; ii++){
2500 aDistance[ii] = 0.0;
2501 for(iDim=0; iDim<pRtree->nDim; iDim++){
2502 float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) -
2503 DCOORD(aCell[ii].aCoord[iDim*2]);
2504 aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
2505 }
2506 }
2507
2508 SortByDistance(aOrder, nCell, aDistance, aSpare);
2509 nodeZero(pRtree, pNode);
2510
2511 for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
2512 RtreeCell *p = &aCell[aOrder[ii]];
2513 nodeInsertCell(pRtree, pNode, p);
2514 if( p->iRowid==pCell->iRowid ){
2515 if( iHeight==0 ){
2516 rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
2517 }else{
2518 rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
2519 }
2520 }
2521 }
2522 if( rc==SQLITE_OK ){
2523 rc = fixBoundingBox(pRtree, pNode);
2524 }
2525 for(; rc==SQLITE_OK && ii<nCell; ii++){
2526 /* Find a node to store this cell in. pNode->iNode currently contains
2527 ** the height of the sub-tree headed by the cell.
2528 */
2529 RtreeNode *pInsert;
2530 RtreeCell *p = &aCell[aOrder[ii]];
2531 rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
2532 if( rc==SQLITE_OK ){
2533 int rc2;
2534 rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);
2535 rc2 = nodeRelease(pRtree, pInsert);
2536 if( rc==SQLITE_OK ){
2537 rc = rc2;
2538 }
2539 }
2540 }
2541
2542 sqlite3_free(aCell);
2543 return rc;
2544 }
2545
2546 /*
2547 ** Insert cell pCell into node pNode. Node pNode is the head of a
2548 ** subtree iHeight high (leaf nodes have iHeight==0).
2549 */
rtreeInsertCell(Rtree * pRtree,RtreeNode * pNode,RtreeCell * pCell,int iHeight)2550 static int rtreeInsertCell(
2551 Rtree *pRtree,
2552 RtreeNode *pNode,
2553 RtreeCell *pCell,
2554 int iHeight
2555 ){
2556 int rc = SQLITE_OK;
2557 if( iHeight>0 ){
2558 RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
2559 if( pChild ){
2560 nodeRelease(pRtree, pChild->pParent);
2561 nodeReference(pNode);
2562 pChild->pParent = pNode;
2563 }
2564 }
2565 if( nodeInsertCell(pRtree, pNode, pCell) ){
2566 #if VARIANT_RSTARTREE_REINSERT
2567 if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
2568 rc = SplitNode(pRtree, pNode, pCell, iHeight);
2569 }else{
2570 pRtree->iReinsertHeight = iHeight;
2571 rc = Reinsert(pRtree, pNode, pCell, iHeight);
2572 }
2573 #else
2574 rc = SplitNode(pRtree, pNode, pCell, iHeight);
2575 #endif
2576 }else{
2577 rc = AdjustTree(pRtree, pNode, pCell);
2578 if( rc==SQLITE_OK ){
2579 if( iHeight==0 ){
2580 rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
2581 }else{
2582 rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
2583 }
2584 }
2585 }
2586 return rc;
2587 }
2588
reinsertNodeContent(Rtree * pRtree,RtreeNode * pNode)2589 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
2590 int ii;
2591 int rc = SQLITE_OK;
2592 int nCell = NCELL(pNode);
2593
2594 for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
2595 RtreeNode *pInsert;
2596 RtreeCell cell;
2597 nodeGetCell(pRtree, pNode, ii, &cell);
2598
2599 /* Find a node to store this cell in. pNode->iNode currently contains
2600 ** the height of the sub-tree headed by the cell.
2601 */
2602 rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
2603 if( rc==SQLITE_OK ){
2604 int rc2;
2605 rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);
2606 rc2 = nodeRelease(pRtree, pInsert);
2607 if( rc==SQLITE_OK ){
2608 rc = rc2;
2609 }
2610 }
2611 }
2612 return rc;
2613 }
2614
2615 /*
2616 ** Select a currently unused rowid for a new r-tree record.
2617 */
newRowid(Rtree * pRtree,i64 * piRowid)2618 static int newRowid(Rtree *pRtree, i64 *piRowid){
2619 int rc;
2620 sqlite3_bind_null(pRtree->pWriteRowid, 1);
2621 sqlite3_bind_null(pRtree->pWriteRowid, 2);
2622 sqlite3_step(pRtree->pWriteRowid);
2623 rc = sqlite3_reset(pRtree->pWriteRowid);
2624 *piRowid = sqlite3_last_insert_rowid(pRtree->db);
2625 return rc;
2626 }
2627
2628 /*
2629 ** The xUpdate method for rtree module virtual tables.
2630 */
rtreeUpdate(sqlite3_vtab * pVtab,int nData,sqlite3_value ** azData,sqlite_int64 * pRowid)2631 static int rtreeUpdate(
2632 sqlite3_vtab *pVtab,
2633 int nData,
2634 sqlite3_value **azData,
2635 sqlite_int64 *pRowid
2636 ){
2637 Rtree *pRtree = (Rtree *)pVtab;
2638 int rc = SQLITE_OK;
2639
2640 rtreeReference(pRtree);
2641
2642 assert(nData>=1);
2643
2644 /* If azData[0] is not an SQL NULL value, it is the rowid of a
2645 ** record to delete from the r-tree table. The following block does
2646 ** just that.
2647 */
2648 if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
2649 i64 iDelete; /* The rowid to delete */
2650 RtreeNode *pLeaf; /* Leaf node containing record iDelete */
2651 int iCell; /* Index of iDelete cell in pLeaf */
2652 RtreeNode *pRoot;
2653
2654 /* Obtain a reference to the root node to initialise Rtree.iDepth */
2655 rc = nodeAcquire(pRtree, 1, 0, &pRoot);
2656
2657 /* Obtain a reference to the leaf node that contains the entry
2658 ** about to be deleted.
2659 */
2660 if( rc==SQLITE_OK ){
2661 iDelete = sqlite3_value_int64(azData[0]);
2662 rc = findLeafNode(pRtree, iDelete, &pLeaf);
2663 }
2664
2665 /* Delete the cell in question from the leaf node. */
2666 if( rc==SQLITE_OK ){
2667 int rc2;
2668 rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
2669 if( rc==SQLITE_OK ){
2670 rc = deleteCell(pRtree, pLeaf, iCell, 0);
2671 }
2672 rc2 = nodeRelease(pRtree, pLeaf);
2673 if( rc==SQLITE_OK ){
2674 rc = rc2;
2675 }
2676 }
2677
2678 /* Delete the corresponding entry in the <rtree>_rowid table. */
2679 if( rc==SQLITE_OK ){
2680 sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
2681 sqlite3_step(pRtree->pDeleteRowid);
2682 rc = sqlite3_reset(pRtree->pDeleteRowid);
2683 }
2684
2685 /* Check if the root node now has exactly one child. If so, remove
2686 ** it, schedule the contents of the child for reinsertion and
2687 ** reduce the tree height by one.
2688 **
2689 ** This is equivalent to copying the contents of the child into
2690 ** the root node (the operation that Gutman's paper says to perform
2691 ** in this scenario).
2692 */
2693 if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){
2694 int rc2;
2695 RtreeNode *pChild;
2696 i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
2697 rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
2698 if( rc==SQLITE_OK ){
2699 rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
2700 }
2701 rc2 = nodeRelease(pRtree, pChild);
2702 if( rc==SQLITE_OK ) rc = rc2;
2703 if( rc==SQLITE_OK ){
2704 pRtree->iDepth--;
2705 writeInt16(pRoot->zData, pRtree->iDepth);
2706 pRoot->isDirty = 1;
2707 }
2708 }
2709
2710 /* Re-insert the contents of any underfull nodes removed from the tree. */
2711 for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
2712 if( rc==SQLITE_OK ){
2713 rc = reinsertNodeContent(pRtree, pLeaf);
2714 }
2715 pRtree->pDeleted = pLeaf->pNext;
2716 sqlite3_free(pLeaf);
2717 }
2718
2719 /* Release the reference to the root node. */
2720 if( rc==SQLITE_OK ){
2721 rc = nodeRelease(pRtree, pRoot);
2722 }else{
2723 nodeRelease(pRtree, pRoot);
2724 }
2725 }
2726
2727 /* If the azData[] array contains more than one element, elements
2728 ** (azData[2]..azData[argc-1]) contain a new record to insert into
2729 ** the r-tree structure.
2730 */
2731 if( rc==SQLITE_OK && nData>1 ){
2732 /* Insert a new record into the r-tree */
2733 RtreeCell cell;
2734 int ii;
2735 RtreeNode *pLeaf;
2736
2737 /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
2738 assert( nData==(pRtree->nDim*2 + 3) );
2739 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
2740 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
2741 cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
2742 cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
2743 if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
2744 rc = SQLITE_CONSTRAINT;
2745 goto constraint;
2746 }
2747 }
2748 }else{
2749 for(ii=0; ii<(pRtree->nDim*2); ii+=2){
2750 cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
2751 cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
2752 if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
2753 rc = SQLITE_CONSTRAINT;
2754 goto constraint;
2755 }
2756 }
2757 }
2758
2759 /* Figure out the rowid of the new row. */
2760 if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
2761 rc = newRowid(pRtree, &cell.iRowid);
2762 }else{
2763 cell.iRowid = sqlite3_value_int64(azData[2]);
2764 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
2765 if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
2766 sqlite3_reset(pRtree->pReadRowid);
2767 rc = SQLITE_CONSTRAINT;
2768 goto constraint;
2769 }
2770 rc = sqlite3_reset(pRtree->pReadRowid);
2771 }
2772 *pRowid = cell.iRowid;
2773
2774 if( rc==SQLITE_OK ){
2775 rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
2776 }
2777 if( rc==SQLITE_OK ){
2778 int rc2;
2779 pRtree->iReinsertHeight = -1;
2780 rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
2781 rc2 = nodeRelease(pRtree, pLeaf);
2782 if( rc==SQLITE_OK ){
2783 rc = rc2;
2784 }
2785 }
2786 }
2787
2788 constraint:
2789 rtreeRelease(pRtree);
2790 return rc;
2791 }
2792
2793 /*
2794 ** The xRename method for rtree module virtual tables.
2795 */
rtreeRename(sqlite3_vtab * pVtab,const char * zNewName)2796 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
2797 Rtree *pRtree = (Rtree *)pVtab;
2798 int rc = SQLITE_NOMEM;
2799 char *zSql = sqlite3_mprintf(
2800 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
2801 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
2802 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
2803 , pRtree->zDb, pRtree->zName, zNewName
2804 , pRtree->zDb, pRtree->zName, zNewName
2805 , pRtree->zDb, pRtree->zName, zNewName
2806 );
2807 if( zSql ){
2808 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
2809 sqlite3_free(zSql);
2810 }
2811 return rc;
2812 }
2813
2814 static sqlite3_module rtreeModule = {
2815 0, /* iVersion */
2816 rtreeCreate, /* xCreate - create a table */
2817 rtreeConnect, /* xConnect - connect to an existing table */
2818 rtreeBestIndex, /* xBestIndex - Determine search strategy */
2819 rtreeDisconnect, /* xDisconnect - Disconnect from a table */
2820 rtreeDestroy, /* xDestroy - Drop a table */
2821 rtreeOpen, /* xOpen - open a cursor */
2822 rtreeClose, /* xClose - close a cursor */
2823 rtreeFilter, /* xFilter - configure scan constraints */
2824 rtreeNext, /* xNext - advance a cursor */
2825 rtreeEof, /* xEof */
2826 rtreeColumn, /* xColumn - read data */
2827 rtreeRowid, /* xRowid - read data */
2828 rtreeUpdate, /* xUpdate - write data */
2829 0, /* xBegin - begin transaction */
2830 0, /* xSync - sync transaction */
2831 0, /* xCommit - commit transaction */
2832 0, /* xRollback - rollback transaction */
2833 0, /* xFindFunction - function overloading */
2834 rtreeRename /* xRename - rename the table */
2835 };
2836
rtreeSqlInit(Rtree * pRtree,sqlite3 * db,const char * zDb,const char * zPrefix,int isCreate)2837 static int rtreeSqlInit(
2838 Rtree *pRtree,
2839 sqlite3 *db,
2840 const char *zDb,
2841 const char *zPrefix,
2842 int isCreate
2843 ){
2844 int rc = SQLITE_OK;
2845
2846 #define N_STATEMENT 9
2847 static const char *azSql[N_STATEMENT] = {
2848 /* Read and write the xxx_node table */
2849 "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
2850 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
2851 "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
2852
2853 /* Read and write the xxx_rowid table */
2854 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
2855 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
2856 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
2857
2858 /* Read and write the xxx_parent table */
2859 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
2860 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
2861 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
2862 };
2863 sqlite3_stmt **appStmt[N_STATEMENT];
2864 int i;
2865
2866 pRtree->db = db;
2867
2868 if( isCreate ){
2869 char *zCreate = sqlite3_mprintf(
2870 "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
2871 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
2872 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
2873 "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
2874 zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
2875 );
2876 if( !zCreate ){
2877 return SQLITE_NOMEM;
2878 }
2879 rc = sqlite3_exec(db, zCreate, 0, 0, 0);
2880 sqlite3_free(zCreate);
2881 if( rc!=SQLITE_OK ){
2882 return rc;
2883 }
2884 }
2885
2886 appStmt[0] = &pRtree->pReadNode;
2887 appStmt[1] = &pRtree->pWriteNode;
2888 appStmt[2] = &pRtree->pDeleteNode;
2889 appStmt[3] = &pRtree->pReadRowid;
2890 appStmt[4] = &pRtree->pWriteRowid;
2891 appStmt[5] = &pRtree->pDeleteRowid;
2892 appStmt[6] = &pRtree->pReadParent;
2893 appStmt[7] = &pRtree->pWriteParent;
2894 appStmt[8] = &pRtree->pDeleteParent;
2895
2896 for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
2897 char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
2898 if( zSql ){
2899 rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0);
2900 }else{
2901 rc = SQLITE_NOMEM;
2902 }
2903 sqlite3_free(zSql);
2904 }
2905
2906 return rc;
2907 }
2908
2909 /*
2910 ** The second argument to this function contains the text of an SQL statement
2911 ** that returns a single integer value. The statement is compiled and executed
2912 ** using database connection db. If successful, the integer value returned
2913 ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
2914 ** code is returned and the value of *piVal after returning is not defined.
2915 */
getIntFromStmt(sqlite3 * db,const char * zSql,int * piVal)2916 static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){
2917 int rc = SQLITE_NOMEM;
2918 if( zSql ){
2919 sqlite3_stmt *pStmt = 0;
2920 rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
2921 if( rc==SQLITE_OK ){
2922 if( SQLITE_ROW==sqlite3_step(pStmt) ){
2923 *piVal = sqlite3_column_int(pStmt, 0);
2924 }
2925 rc = sqlite3_finalize(pStmt);
2926 }
2927 }
2928 return rc;
2929 }
2930
2931 /*
2932 ** This function is called from within the xConnect() or xCreate() method to
2933 ** determine the node-size used by the rtree table being created or connected
2934 ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
2935 ** Otherwise, an SQLite error code is returned.
2936 **
2937 ** If this function is being called as part of an xConnect(), then the rtree
2938 ** table already exists. In this case the node-size is determined by inspecting
2939 ** the root node of the tree.
2940 **
2941 ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
2942 ** This ensures that each node is stored on a single database page. If the
2943 ** database page-size is so large that more than RTREE_MAXCELLS entries
2944 ** would fit in a single node, use a smaller node-size.
2945 */
getNodeSize(sqlite3 * db,Rtree * pRtree,int isCreate)2946 static int getNodeSize(
2947 sqlite3 *db, /* Database handle */
2948 Rtree *pRtree, /* Rtree handle */
2949 int isCreate /* True for xCreate, false for xConnect */
2950 ){
2951 int rc;
2952 char *zSql;
2953 if( isCreate ){
2954 int iPageSize;
2955 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
2956 rc = getIntFromStmt(db, zSql, &iPageSize);
2957 if( rc==SQLITE_OK ){
2958 pRtree->iNodeSize = iPageSize-64;
2959 if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
2960 pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
2961 }
2962 }
2963 }else{
2964 zSql = sqlite3_mprintf(
2965 "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
2966 pRtree->zDb, pRtree->zName
2967 );
2968 rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
2969 }
2970
2971 sqlite3_free(zSql);
2972 return rc;
2973 }
2974
2975 /*
2976 ** This function is the implementation of both the xConnect and xCreate
2977 ** methods of the r-tree virtual table.
2978 **
2979 ** argv[0] -> module name
2980 ** argv[1] -> database name
2981 ** argv[2] -> table name
2982 ** argv[...] -> column names...
2983 */
rtreeInit(sqlite3 * db,void * pAux,int argc,const char * const * argv,sqlite3_vtab ** ppVtab,char ** pzErr,int isCreate)2984 static int rtreeInit(
2985 sqlite3 *db, /* Database connection */
2986 void *pAux, /* One of the RTREE_COORD_* constants */
2987 int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */
2988 sqlite3_vtab **ppVtab, /* OUT: New virtual table */
2989 char **pzErr, /* OUT: Error message, if any */
2990 int isCreate /* True for xCreate, false for xConnect */
2991 ){
2992 int rc = SQLITE_OK;
2993 Rtree *pRtree;
2994 int nDb; /* Length of string argv[1] */
2995 int nName; /* Length of string argv[2] */
2996 int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
2997
2998 const char *aErrMsg[] = {
2999 0, /* 0 */
3000 "Wrong number of columns for an rtree table", /* 1 */
3001 "Too few columns for an rtree table", /* 2 */
3002 "Too many columns for an rtree table" /* 3 */
3003 };
3004
3005 int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
3006 if( aErrMsg[iErr] ){
3007 *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
3008 return SQLITE_ERROR;
3009 }
3010
3011 /* Allocate the sqlite3_vtab structure */
3012 nDb = strlen(argv[1]);
3013 nName = strlen(argv[2]);
3014 pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
3015 if( !pRtree ){
3016 return SQLITE_NOMEM;
3017 }
3018 memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
3019 pRtree->nBusy = 1;
3020 pRtree->base.pModule = &rtreeModule;
3021 pRtree->zDb = (char *)&pRtree[1];
3022 pRtree->zName = &pRtree->zDb[nDb+1];
3023 pRtree->nDim = (argc-4)/2;
3024 pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
3025 pRtree->eCoordType = eCoordType;
3026 memcpy(pRtree->zDb, argv[1], nDb);
3027 memcpy(pRtree->zName, argv[2], nName);
3028
3029 /* Figure out the node size to use. */
3030 rc = getNodeSize(db, pRtree, isCreate);
3031
3032 /* Create/Connect to the underlying relational database schema. If
3033 ** that is successful, call sqlite3_declare_vtab() to configure
3034 ** the r-tree table schema.
3035 */
3036 if( rc==SQLITE_OK ){
3037 if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
3038 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3039 }else{
3040 char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
3041 char *zTmp;
3042 int ii;
3043 for(ii=4; zSql && ii<argc; ii++){
3044 zTmp = zSql;
3045 zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
3046 sqlite3_free(zTmp);
3047 }
3048 if( zSql ){
3049 zTmp = zSql;
3050 zSql = sqlite3_mprintf("%s);", zTmp);
3051 sqlite3_free(zTmp);
3052 }
3053 if( !zSql ){
3054 rc = SQLITE_NOMEM;
3055 }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
3056 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3057 }
3058 sqlite3_free(zSql);
3059 }
3060 }
3061
3062 if( rc==SQLITE_OK ){
3063 *ppVtab = (sqlite3_vtab *)pRtree;
3064 }else{
3065 rtreeRelease(pRtree);
3066 }
3067 return rc;
3068 }
3069
3070
3071 /*
3072 ** Implementation of a scalar function that decodes r-tree nodes to
3073 ** human readable strings. This can be used for debugging and analysis.
3074 **
3075 ** The scalar function takes two arguments, a blob of data containing
3076 ** an r-tree node, and the number of dimensions the r-tree indexes.
3077 ** For a two-dimensional r-tree structure called "rt", to deserialize
3078 ** all nodes, a statement like:
3079 **
3080 ** SELECT rtreenode(2, data) FROM rt_node;
3081 **
3082 ** The human readable string takes the form of a Tcl list with one
3083 ** entry for each cell in the r-tree node. Each entry is itself a
3084 ** list, containing the 8-byte rowid/pageno followed by the
3085 ** <num-dimension>*2 coordinates.
3086 */
rtreenode(sqlite3_context * ctx,int nArg,sqlite3_value ** apArg)3087 static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3088 char *zText = 0;
3089 RtreeNode node;
3090 Rtree tree;
3091 int ii;
3092
3093 UNUSED_PARAMETER(nArg);
3094 memset(&node, 0, sizeof(RtreeNode));
3095 memset(&tree, 0, sizeof(Rtree));
3096 tree.nDim = sqlite3_value_int(apArg[0]);
3097 tree.nBytesPerCell = 8 + 8 * tree.nDim;
3098 node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
3099
3100 for(ii=0; ii<NCELL(&node); ii++){
3101 char zCell[512];
3102 int nCell = 0;
3103 RtreeCell cell;
3104 int jj;
3105
3106 nodeGetCell(&tree, &node, ii, &cell);
3107 sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
3108 nCell = strlen(zCell);
3109 for(jj=0; jj<tree.nDim*2; jj++){
3110 sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
3111 nCell = strlen(zCell);
3112 }
3113
3114 if( zText ){
3115 char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
3116 sqlite3_free(zText);
3117 zText = zTextNew;
3118 }else{
3119 zText = sqlite3_mprintf("{%s}", zCell);
3120 }
3121 }
3122
3123 sqlite3_result_text(ctx, zText, -1, sqlite3_free);
3124 }
3125
rtreedepth(sqlite3_context * ctx,int nArg,sqlite3_value ** apArg)3126 static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3127 UNUSED_PARAMETER(nArg);
3128 if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB
3129 || sqlite3_value_bytes(apArg[0])<2
3130 ){
3131 sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1);
3132 }else{
3133 u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
3134 sqlite3_result_int(ctx, readInt16(zBlob));
3135 }
3136 }
3137
3138 /*
3139 ** Register the r-tree module with database handle db. This creates the
3140 ** virtual table module "rtree" and the debugging/analysis scalar
3141 ** function "rtreenode".
3142 */
sqlite3RtreeInit(sqlite3 * db)3143 int sqlite3RtreeInit(sqlite3 *db){
3144 const int utf8 = SQLITE_UTF8;
3145 int rc;
3146
3147 rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
3148 if( rc==SQLITE_OK ){
3149 rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
3150 }
3151 if( rc==SQLITE_OK ){
3152 void *c = (void *)RTREE_COORD_REAL32;
3153 rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
3154 }
3155 if( rc==SQLITE_OK ){
3156 void *c = (void *)RTREE_COORD_INT32;
3157 rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
3158 }
3159
3160 return rc;
3161 }
3162
3163 /*
3164 ** A version of sqlite3_free() that can be used as a callback. This is used
3165 ** in two places - as the destructor for the blob value returned by the
3166 ** invocation of a geometry function, and as the destructor for the geometry
3167 ** functions themselves.
3168 */
doSqlite3Free(void * p)3169 static void doSqlite3Free(void *p){
3170 sqlite3_free(p);
3171 }
3172
3173 /*
3174 ** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
3175 ** scalar user function. This C function is the callback used for all such
3176 ** registered SQL functions.
3177 **
3178 ** The scalar user functions return a blob that is interpreted by r-tree
3179 ** table MATCH operators.
3180 */
geomCallback(sqlite3_context * ctx,int nArg,sqlite3_value ** aArg)3181 static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
3182 RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
3183 RtreeMatchArg *pBlob;
3184 int nBlob;
3185
3186 nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
3187 pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
3188 if( !pBlob ){
3189 sqlite3_result_error_nomem(ctx);
3190 }else{
3191 int i;
3192 pBlob->magic = RTREE_GEOMETRY_MAGIC;
3193 pBlob->xGeom = pGeomCtx->xGeom;
3194 pBlob->pContext = pGeomCtx->pContext;
3195 pBlob->nParam = nArg;
3196 for(i=0; i<nArg; i++){
3197 pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
3198 }
3199 sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
3200 }
3201 }
3202
3203 /*
3204 ** Register a new geometry function for use with the r-tree MATCH operator.
3205 */
sqlite3_rtree_geometry_callback(sqlite3 * db,const char * zGeom,int (* xGeom)(sqlite3_rtree_geometry *,int,double *,int *),void * pContext)3206 int sqlite3_rtree_geometry_callback(
3207 sqlite3 *db,
3208 const char *zGeom,
3209 int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
3210 void *pContext
3211 ){
3212 RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */
3213
3214 /* Allocate and populate the context object. */
3215 pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
3216 if( !pGeomCtx ) return SQLITE_NOMEM;
3217 pGeomCtx->xGeom = xGeom;
3218 pGeomCtx->pContext = pContext;
3219
3220 /* Create the new user-function. Register a destructor function to delete
3221 ** the context object when it is no longer required. */
3222 return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY,
3223 (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
3224 );
3225 }
3226
3227 #if !SQLITE_CORE
sqlite3_extension_init(sqlite3 * db,char ** pzErrMsg,const sqlite3_api_routines * pApi)3228 int sqlite3_extension_init(
3229 sqlite3 *db,
3230 char **pzErrMsg,
3231 const sqlite3_api_routines *pApi
3232 ){
3233 SQLITE_EXTENSION_INIT2(pApi)
3234 return sqlite3RtreeInit(db);
3235 }
3236 #endif
3237
3238 #endif
3239