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: */
320: static int readInt16(u8 *p){
321: return (p[0]<<8) + p[1];
322: }
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: }
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: */
350: static int writeInt16(u8 *p, int i){
351: p[0] = (i>> 8)&0xFF;
352: p[1] = (i>> 0)&0xFF;
353: return 2;
354: }
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: }
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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
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_VTAB;
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_VTAB.
527: */
528: if( pNode && rc==SQLITE_OK ){
529: if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
530: rc = SQLITE_CORRUPT_VTAB;
531: }
532: }
533:
534: if( rc==SQLITE_OK ){
535: if( pNode!=0 ){
536: nodeHashInsert(pRtree, pNode);
537: }else{
538: rc = SQLITE_CORRUPT_VTAB;
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: */
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: */
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
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
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
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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_VTAB;
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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)
1272: || (idxStr && (int)strlen(idxStr)==argc*2) );
1273: for(ii=0; ii<argc; ii++){
1274: RtreeConstraint *p = &pCsr->aConstraint[ii];
1275: p->op = idxStr[ii*2];
1276: p->iCoord = idxStr[ii*2+1]-'a';
1277: if( p->op==RTREE_MATCH ){
1278: /* A MATCH operator. The right-hand-side must be a blob that
1279: ** can be cast into an RtreeMatchArg object. One created using
1280: ** an sqlite3_rtree_geometry_callback() SQL user function.
1281: */
1282: rc = deserializeGeometry(argv[ii], p);
1283: if( rc!=SQLITE_OK ){
1284: break;
1285: }
1286: }else{
1287: p->rValue = sqlite3_value_double(argv[ii]);
1288: }
1289: }
1290: }
1291: }
1292:
1293: if( rc==SQLITE_OK ){
1294: pCsr->pNode = 0;
1295: rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1296: }
1297: if( rc==SQLITE_OK ){
1298: int isEof = 1;
1299: int nCell = NCELL(pRoot);
1300: pCsr->pNode = pRoot;
1301: for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
1302: assert( pCsr->pNode==pRoot );
1303: rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
1304: if( !isEof ){
1305: break;
1306: }
1307: }
1308: if( rc==SQLITE_OK && isEof ){
1309: assert( pCsr->pNode==pRoot );
1310: nodeRelease(pRtree, pRoot);
1311: pCsr->pNode = 0;
1312: }
1313: assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
1314: }
1315: }
1316:
1317: rtreeRelease(pRtree);
1318: return rc;
1319: }
1320:
1321: /*
1322: ** Rtree virtual table module xBestIndex method. There are three
1323: ** table scan strategies to choose from (in order from most to
1324: ** least desirable):
1325: **
1326: ** idxNum idxStr Strategy
1327: ** ------------------------------------------------
1328: ** 1 Unused Direct lookup by rowid.
1329: ** 2 See below R-tree query or full-table scan.
1330: ** ------------------------------------------------
1331: **
1332: ** If strategy 1 is used, then idxStr is not meaningful. If strategy
1333: ** 2 is used, idxStr is formatted to contain 2 bytes for each
1334: ** constraint used. The first two bytes of idxStr correspond to
1335: ** the constraint in sqlite3_index_info.aConstraintUsage[] with
1336: ** (argvIndex==1) etc.
1337: **
1338: ** The first of each pair of bytes in idxStr identifies the constraint
1339: ** operator as follows:
1340: **
1341: ** Operator Byte Value
1342: ** ----------------------
1343: ** = 0x41 ('A')
1344: ** <= 0x42 ('B')
1345: ** < 0x43 ('C')
1346: ** >= 0x44 ('D')
1347: ** > 0x45 ('E')
1348: ** MATCH 0x46 ('F')
1349: ** ----------------------
1350: **
1351: ** The second of each pair of bytes identifies the coordinate column
1352: ** to which the constraint applies. The leftmost coordinate column
1353: ** is 'a', the second from the left 'b' etc.
1354: */
1355: static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
1356: int rc = SQLITE_OK;
1357: int ii;
1358:
1359: int iIdx = 0;
1360: char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
1361: memset(zIdxStr, 0, sizeof(zIdxStr));
1362: UNUSED_PARAMETER(tab);
1363:
1364: assert( pIdxInfo->idxStr==0 );
1365: for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
1366: struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
1367:
1368: if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
1369: /* We have an equality constraint on the rowid. Use strategy 1. */
1370: int jj;
1371: for(jj=0; jj<ii; jj++){
1372: pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
1373: pIdxInfo->aConstraintUsage[jj].omit = 0;
1374: }
1375: pIdxInfo->idxNum = 1;
1376: pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
1377: pIdxInfo->aConstraintUsage[jj].omit = 1;
1378:
1379: /* This strategy involves a two rowid lookups on an B-Tree structures
1380: ** and then a linear search of an R-Tree node. This should be
1381: ** considered almost as quick as a direct rowid lookup (for which
1382: ** sqlite uses an internal cost of 0.0).
1383: */
1384: pIdxInfo->estimatedCost = 10.0;
1385: return SQLITE_OK;
1386: }
1387:
1388: if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){
1389: u8 op;
1390: switch( p->op ){
1391: case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
1392: case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
1393: case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
1394: case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
1395: case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
1396: default:
1397: assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
1398: op = RTREE_MATCH;
1399: break;
1400: }
1401: zIdxStr[iIdx++] = op;
1402: zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
1403: pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
1404: pIdxInfo->aConstraintUsage[ii].omit = 1;
1405: }
1406: }
1407:
1408: pIdxInfo->idxNum = 2;
1409: pIdxInfo->needToFreeIdxStr = 1;
1410: if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
1411: return SQLITE_NOMEM;
1412: }
1413: assert( iIdx>=0 );
1414: pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
1415: return rc;
1416: }
1417:
1418: /*
1419: ** Return the N-dimensional volumn of the cell stored in *p.
1420: */
1421: static float cellArea(Rtree *pRtree, RtreeCell *p){
1422: float area = 1.0;
1423: int ii;
1424: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1425: area = (float)(area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])));
1426: }
1427: return area;
1428: }
1429:
1430: /*
1431: ** Return the margin length of cell p. The margin length is the sum
1432: ** of the objects size in each dimension.
1433: */
1434: static float cellMargin(Rtree *pRtree, RtreeCell *p){
1435: float margin = 0.0;
1436: int ii;
1437: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1438: margin += (float)(DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
1439: }
1440: return margin;
1441: }
1442:
1443: /*
1444: ** Store the union of cells p1 and p2 in p1.
1445: */
1446: static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1447: int ii;
1448: if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1449: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1450: p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
1451: p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
1452: }
1453: }else{
1454: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1455: p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
1456: p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
1457: }
1458: }
1459: }
1460:
1461: /*
1462: ** Return true if the area covered by p2 is a subset of the area covered
1463: ** by p1. False otherwise.
1464: */
1465: static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1466: int ii;
1467: int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
1468: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1469: RtreeCoord *a1 = &p1->aCoord[ii];
1470: RtreeCoord *a2 = &p2->aCoord[ii];
1471: if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f))
1472: || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i))
1473: ){
1474: return 0;
1475: }
1476: }
1477: return 1;
1478: }
1479:
1480: /*
1481: ** Return the amount cell p would grow by if it were unioned with pCell.
1482: */
1483: static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
1484: float area;
1485: RtreeCell cell;
1486: memcpy(&cell, p, sizeof(RtreeCell));
1487: area = cellArea(pRtree, &cell);
1488: cellUnion(pRtree, &cell, pCell);
1489: return (cellArea(pRtree, &cell)-area);
1490: }
1491:
1492: #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
1493: static float cellOverlap(
1494: Rtree *pRtree,
1495: RtreeCell *p,
1496: RtreeCell *aCell,
1497: int nCell,
1498: int iExclude
1499: ){
1500: int ii;
1501: float overlap = 0.0;
1502: for(ii=0; ii<nCell; ii++){
1503: #if VARIANT_RSTARTREE_CHOOSESUBTREE
1504: if( ii!=iExclude )
1505: #else
1506: assert( iExclude==-1 );
1507: UNUSED_PARAMETER(iExclude);
1508: #endif
1509: {
1510: int jj;
1511: float o = 1.0;
1512: for(jj=0; jj<(pRtree->nDim*2); jj+=2){
1513: double x1;
1514: double x2;
1515:
1516: x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
1517: x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
1518:
1519: if( x2<x1 ){
1520: o = 0.0;
1521: break;
1522: }else{
1523: o = o * (float)(x2-x1);
1524: }
1525: }
1526: overlap += o;
1527: }
1528: }
1529: return overlap;
1530: }
1531: #endif
1532:
1533: #if VARIANT_RSTARTREE_CHOOSESUBTREE
1534: static float cellOverlapEnlargement(
1535: Rtree *pRtree,
1536: RtreeCell *p,
1537: RtreeCell *pInsert,
1538: RtreeCell *aCell,
1539: int nCell,
1540: int iExclude
1541: ){
1542: double before;
1543: double after;
1544: before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1545: cellUnion(pRtree, p, pInsert);
1546: after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1547: return (float)(after-before);
1548: }
1549: #endif
1550:
1551:
1552: /*
1553: ** This function implements the ChooseLeaf algorithm from Gutman[84].
1554: ** ChooseSubTree in r*tree terminology.
1555: */
1556: static int ChooseLeaf(
1557: Rtree *pRtree, /* Rtree table */
1558: RtreeCell *pCell, /* Cell to insert into rtree */
1559: int iHeight, /* Height of sub-tree rooted at pCell */
1560: RtreeNode **ppLeaf /* OUT: Selected leaf page */
1561: ){
1562: int rc;
1563: int ii;
1564: RtreeNode *pNode;
1565: rc = nodeAcquire(pRtree, 1, 0, &pNode);
1566:
1567: for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
1568: int iCell;
1569: sqlite3_int64 iBest = 0;
1570:
1571: float fMinGrowth = 0.0;
1572: float fMinArea = 0.0;
1573: #if VARIANT_RSTARTREE_CHOOSESUBTREE
1574: float fMinOverlap = 0.0;
1575: float overlap;
1576: #endif
1577:
1578: int nCell = NCELL(pNode);
1579: RtreeCell cell;
1580: RtreeNode *pChild;
1581:
1582: RtreeCell *aCell = 0;
1583:
1584: #if VARIANT_RSTARTREE_CHOOSESUBTREE
1585: if( ii==(pRtree->iDepth-1) ){
1586: int jj;
1587: aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
1588: if( !aCell ){
1589: rc = SQLITE_NOMEM;
1590: nodeRelease(pRtree, pNode);
1591: pNode = 0;
1592: continue;
1593: }
1594: for(jj=0; jj<nCell; jj++){
1595: nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
1596: }
1597: }
1598: #endif
1599:
1600: /* Select the child node which will be enlarged the least if pCell
1601: ** is inserted into it. Resolve ties by choosing the entry with
1602: ** the smallest area.
1603: */
1604: for(iCell=0; iCell<nCell; iCell++){
1605: int bBest = 0;
1606: float growth;
1607: float area;
1608: nodeGetCell(pRtree, pNode, iCell, &cell);
1609: growth = cellGrowth(pRtree, &cell, pCell);
1610: area = cellArea(pRtree, &cell);
1611:
1612: #if VARIANT_RSTARTREE_CHOOSESUBTREE
1613: if( ii==(pRtree->iDepth-1) ){
1614: overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
1615: }else{
1616: overlap = 0.0;
1617: }
1618: if( (iCell==0)
1619: || (overlap<fMinOverlap)
1620: || (overlap==fMinOverlap && growth<fMinGrowth)
1621: || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
1622: ){
1623: bBest = 1;
1624: fMinOverlap = overlap;
1625: }
1626: #else
1627: if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
1628: bBest = 1;
1629: }
1630: #endif
1631: if( bBest ){
1632: fMinGrowth = growth;
1633: fMinArea = area;
1634: iBest = cell.iRowid;
1635: }
1636: }
1637:
1638: sqlite3_free(aCell);
1639: rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
1640: nodeRelease(pRtree, pNode);
1641: pNode = pChild;
1642: }
1643:
1644: *ppLeaf = pNode;
1645: return rc;
1646: }
1647:
1648: /*
1649: ** A cell with the same content as pCell has just been inserted into
1650: ** the node pNode. This function updates the bounding box cells in
1651: ** all ancestor elements.
1652: */
1653: static int AdjustTree(
1654: Rtree *pRtree, /* Rtree table */
1655: RtreeNode *pNode, /* Adjust ancestry of this node. */
1656: RtreeCell *pCell /* This cell was just inserted */
1657: ){
1658: RtreeNode *p = pNode;
1659: while( p->pParent ){
1660: RtreeNode *pParent = p->pParent;
1661: RtreeCell cell;
1662: int iCell;
1663:
1664: if( nodeParentIndex(pRtree, p, &iCell) ){
1665: return SQLITE_CORRUPT_VTAB;
1666: }
1667:
1668: nodeGetCell(pRtree, pParent, iCell, &cell);
1669: if( !cellContains(pRtree, &cell, pCell) ){
1670: cellUnion(pRtree, &cell, pCell);
1671: nodeOverwriteCell(pRtree, pParent, &cell, iCell);
1672: }
1673:
1674: p = pParent;
1675: }
1676: return SQLITE_OK;
1677: }
1678:
1679: /*
1680: ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
1681: */
1682: static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
1683: sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
1684: sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
1685: sqlite3_step(pRtree->pWriteRowid);
1686: return sqlite3_reset(pRtree->pWriteRowid);
1687: }
1688:
1689: /*
1690: ** Write mapping (iNode->iPar) to the <rtree>_parent table.
1691: */
1692: static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
1693: sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
1694: sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
1695: sqlite3_step(pRtree->pWriteParent);
1696: return sqlite3_reset(pRtree->pWriteParent);
1697: }
1698:
1699: static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
1700:
1701: #if VARIANT_GUTTMAN_LINEAR_SPLIT
1702: /*
1703: ** Implementation of the linear variant of the PickNext() function from
1704: ** Guttman[84].
1705: */
1706: static RtreeCell *LinearPickNext(
1707: Rtree *pRtree,
1708: RtreeCell *aCell,
1709: int nCell,
1710: RtreeCell *pLeftBox,
1711: RtreeCell *pRightBox,
1712: int *aiUsed
1713: ){
1714: int ii;
1715: for(ii=0; aiUsed[ii]; ii++);
1716: aiUsed[ii] = 1;
1717: return &aCell[ii];
1718: }
1719:
1720: /*
1721: ** Implementation of the linear variant of the PickSeeds() function from
1722: ** Guttman[84].
1723: */
1724: static void LinearPickSeeds(
1725: Rtree *pRtree,
1726: RtreeCell *aCell,
1727: int nCell,
1728: int *piLeftSeed,
1729: int *piRightSeed
1730: ){
1731: int i;
1732: int iLeftSeed = 0;
1733: int iRightSeed = 1;
1734: float maxNormalInnerWidth = 0.0;
1735:
1736: /* Pick two "seed" cells from the array of cells. The algorithm used
1737: ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
1738: ** indices of the two seed cells in the array are stored in local
1739: ** variables iLeftSeek and iRightSeed.
1740: */
1741: for(i=0; i<pRtree->nDim; i++){
1742: float x1 = DCOORD(aCell[0].aCoord[i*2]);
1743: float x2 = DCOORD(aCell[0].aCoord[i*2+1]);
1744: float x3 = x1;
1745: float x4 = x2;
1746: int jj;
1747:
1748: int iCellLeft = 0;
1749: int iCellRight = 0;
1750:
1751: for(jj=1; jj<nCell; jj++){
1752: float left = DCOORD(aCell[jj].aCoord[i*2]);
1753: float right = DCOORD(aCell[jj].aCoord[i*2+1]);
1754:
1755: if( left<x1 ) x1 = left;
1756: if( right>x4 ) x4 = right;
1757: if( left>x3 ){
1758: x3 = left;
1759: iCellRight = jj;
1760: }
1761: if( right<x2 ){
1762: x2 = right;
1763: iCellLeft = jj;
1764: }
1765: }
1766:
1767: if( x4!=x1 ){
1768: float normalwidth = (x3 - x2) / (x4 - x1);
1769: if( normalwidth>maxNormalInnerWidth ){
1770: iLeftSeed = iCellLeft;
1771: iRightSeed = iCellRight;
1772: }
1773: }
1774: }
1775:
1776: *piLeftSeed = iLeftSeed;
1777: *piRightSeed = iRightSeed;
1778: }
1779: #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
1780:
1781: #if VARIANT_GUTTMAN_QUADRATIC_SPLIT
1782: /*
1783: ** Implementation of the quadratic variant of the PickNext() function from
1784: ** Guttman[84].
1785: */
1786: static RtreeCell *QuadraticPickNext(
1787: Rtree *pRtree,
1788: RtreeCell *aCell,
1789: int nCell,
1790: RtreeCell *pLeftBox,
1791: RtreeCell *pRightBox,
1792: int *aiUsed
1793: ){
1794: #define FABS(a) ((a)<0.0?-1.0*(a):(a))
1795:
1796: int iSelect = -1;
1797: float fDiff;
1798: int ii;
1799: for(ii=0; ii<nCell; ii++){
1800: if( aiUsed[ii]==0 ){
1801: float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1802: float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1803: float diff = FABS(right-left);
1804: if( iSelect<0 || diff>fDiff ){
1805: fDiff = diff;
1806: iSelect = ii;
1807: }
1808: }
1809: }
1810: aiUsed[iSelect] = 1;
1811: return &aCell[iSelect];
1812: }
1813:
1814: /*
1815: ** Implementation of the quadratic variant of the PickSeeds() function from
1816: ** Guttman[84].
1817: */
1818: static void QuadraticPickSeeds(
1819: Rtree *pRtree,
1820: RtreeCell *aCell,
1821: int nCell,
1822: int *piLeftSeed,
1823: int *piRightSeed
1824: ){
1825: int ii;
1826: int jj;
1827:
1828: int iLeftSeed = 0;
1829: int iRightSeed = 1;
1830: float fWaste = 0.0;
1831:
1832: for(ii=0; ii<nCell; ii++){
1833: for(jj=ii+1; jj<nCell; jj++){
1834: float right = cellArea(pRtree, &aCell[jj]);
1835: float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
1836: float waste = growth - right;
1837:
1838: if( waste>fWaste ){
1839: iLeftSeed = ii;
1840: iRightSeed = jj;
1841: fWaste = waste;
1842: }
1843: }
1844: }
1845:
1846: *piLeftSeed = iLeftSeed;
1847: *piRightSeed = iRightSeed;
1848: }
1849: #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
1850:
1851: /*
1852: ** Arguments aIdx, aDistance and aSpare all point to arrays of size
1853: ** nIdx. The aIdx array contains the set of integers from 0 to
1854: ** (nIdx-1) in no particular order. This function sorts the values
1855: ** in aIdx according to the indexed values in aDistance. For
1856: ** example, assuming the inputs:
1857: **
1858: ** aIdx = { 0, 1, 2, 3 }
1859: ** aDistance = { 5.0, 2.0, 7.0, 6.0 }
1860: **
1861: ** this function sets the aIdx array to contain:
1862: **
1863: ** aIdx = { 0, 1, 2, 3 }
1864: **
1865: ** The aSpare array is used as temporary working space by the
1866: ** sorting algorithm.
1867: */
1868: static void SortByDistance(
1869: int *aIdx,
1870: int nIdx,
1871: float *aDistance,
1872: int *aSpare
1873: ){
1874: if( nIdx>1 ){
1875: int iLeft = 0;
1876: int iRight = 0;
1877:
1878: int nLeft = nIdx/2;
1879: int nRight = nIdx-nLeft;
1880: int *aLeft = aIdx;
1881: int *aRight = &aIdx[nLeft];
1882:
1883: SortByDistance(aLeft, nLeft, aDistance, aSpare);
1884: SortByDistance(aRight, nRight, aDistance, aSpare);
1885:
1886: memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1887: aLeft = aSpare;
1888:
1889: while( iLeft<nLeft || iRight<nRight ){
1890: if( iLeft==nLeft ){
1891: aIdx[iLeft+iRight] = aRight[iRight];
1892: iRight++;
1893: }else if( iRight==nRight ){
1894: aIdx[iLeft+iRight] = aLeft[iLeft];
1895: iLeft++;
1896: }else{
1897: float fLeft = aDistance[aLeft[iLeft]];
1898: float fRight = aDistance[aRight[iRight]];
1899: if( fLeft<fRight ){
1900: aIdx[iLeft+iRight] = aLeft[iLeft];
1901: iLeft++;
1902: }else{
1903: aIdx[iLeft+iRight] = aRight[iRight];
1904: iRight++;
1905: }
1906: }
1907: }
1908:
1909: #if 0
1910: /* Check that the sort worked */
1911: {
1912: int jj;
1913: for(jj=1; jj<nIdx; jj++){
1914: float left = aDistance[aIdx[jj-1]];
1915: float right = aDistance[aIdx[jj]];
1916: assert( left<=right );
1917: }
1918: }
1919: #endif
1920: }
1921: }
1922:
1923: /*
1924: ** Arguments aIdx, aCell and aSpare all point to arrays of size
1925: ** nIdx. The aIdx array contains the set of integers from 0 to
1926: ** (nIdx-1) in no particular order. This function sorts the values
1927: ** in aIdx according to dimension iDim of the cells in aCell. The
1928: ** minimum value of dimension iDim is considered first, the
1929: ** maximum used to break ties.
1930: **
1931: ** The aSpare array is used as temporary working space by the
1932: ** sorting algorithm.
1933: */
1934: static void SortByDimension(
1935: Rtree *pRtree,
1936: int *aIdx,
1937: int nIdx,
1938: int iDim,
1939: RtreeCell *aCell,
1940: int *aSpare
1941: ){
1942: if( nIdx>1 ){
1943:
1944: int iLeft = 0;
1945: int iRight = 0;
1946:
1947: int nLeft = nIdx/2;
1948: int nRight = nIdx-nLeft;
1949: int *aLeft = aIdx;
1950: int *aRight = &aIdx[nLeft];
1951:
1952: SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
1953: SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
1954:
1955: memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1956: aLeft = aSpare;
1957: while( iLeft<nLeft || iRight<nRight ){
1958: double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
1959: double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
1960: double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
1961: double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
1962: if( (iLeft!=nLeft) && ((iRight==nRight)
1963: || (xleft1<xright1)
1964: || (xleft1==xright1 && xleft2<xright2)
1965: )){
1966: aIdx[iLeft+iRight] = aLeft[iLeft];
1967: iLeft++;
1968: }else{
1969: aIdx[iLeft+iRight] = aRight[iRight];
1970: iRight++;
1971: }
1972: }
1973:
1974: #if 0
1975: /* Check that the sort worked */
1976: {
1977: int jj;
1978: for(jj=1; jj<nIdx; jj++){
1979: float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
1980: float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
1981: float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
1982: float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
1983: assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
1984: }
1985: }
1986: #endif
1987: }
1988: }
1989:
1990: #if VARIANT_RSTARTREE_SPLIT
1991: /*
1992: ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
1993: */
1994: static int splitNodeStartree(
1995: Rtree *pRtree,
1996: RtreeCell *aCell,
1997: int nCell,
1998: RtreeNode *pLeft,
1999: RtreeNode *pRight,
2000: RtreeCell *pBboxLeft,
2001: RtreeCell *pBboxRight
2002: ){
2003: int **aaSorted;
2004: int *aSpare;
2005: int ii;
2006:
2007: int iBestDim = 0;
2008: int iBestSplit = 0;
2009: float fBestMargin = 0.0;
2010:
2011: int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
2012:
2013: aaSorted = (int **)sqlite3_malloc(nByte);
2014: if( !aaSorted ){
2015: return SQLITE_NOMEM;
2016: }
2017:
2018: aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
2019: memset(aaSorted, 0, nByte);
2020: for(ii=0; ii<pRtree->nDim; ii++){
2021: int jj;
2022: aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
2023: for(jj=0; jj<nCell; jj++){
2024: aaSorted[ii][jj] = jj;
2025: }
2026: SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
2027: }
2028:
2029: for(ii=0; ii<pRtree->nDim; ii++){
2030: float margin = 0.0;
2031: float fBestOverlap = 0.0;
2032: float fBestArea = 0.0;
2033: int iBestLeft = 0;
2034: int nLeft;
2035:
2036: for(
2037: nLeft=RTREE_MINCELLS(pRtree);
2038: nLeft<=(nCell-RTREE_MINCELLS(pRtree));
2039: nLeft++
2040: ){
2041: RtreeCell left;
2042: RtreeCell right;
2043: int kk;
2044: float overlap;
2045: float area;
2046:
2047: memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
2048: memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
2049: for(kk=1; kk<(nCell-1); kk++){
2050: if( kk<nLeft ){
2051: cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
2052: }else{
2053: cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
2054: }
2055: }
2056: margin += cellMargin(pRtree, &left);
2057: margin += cellMargin(pRtree, &right);
2058: overlap = cellOverlap(pRtree, &left, &right, 1, -1);
2059: area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
2060: if( (nLeft==RTREE_MINCELLS(pRtree))
2061: || (overlap<fBestOverlap)
2062: || (overlap==fBestOverlap && area<fBestArea)
2063: ){
2064: iBestLeft = nLeft;
2065: fBestOverlap = overlap;
2066: fBestArea = area;
2067: }
2068: }
2069:
2070: if( ii==0 || margin<fBestMargin ){
2071: iBestDim = ii;
2072: fBestMargin = margin;
2073: iBestSplit = iBestLeft;
2074: }
2075: }
2076:
2077: memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
2078: memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
2079: for(ii=0; ii<nCell; ii++){
2080: RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
2081: RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
2082: RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
2083: nodeInsertCell(pRtree, pTarget, pCell);
2084: cellUnion(pRtree, pBbox, pCell);
2085: }
2086:
2087: sqlite3_free(aaSorted);
2088: return SQLITE_OK;
2089: }
2090: #endif
2091:
2092: #if VARIANT_GUTTMAN_SPLIT
2093: /*
2094: ** Implementation of the regular R-tree SplitNode from Guttman[1984].
2095: */
2096: static int splitNodeGuttman(
2097: Rtree *pRtree,
2098: RtreeCell *aCell,
2099: int nCell,
2100: RtreeNode *pLeft,
2101: RtreeNode *pRight,
2102: RtreeCell *pBboxLeft,
2103: RtreeCell *pBboxRight
2104: ){
2105: int iLeftSeed = 0;
2106: int iRightSeed = 1;
2107: int *aiUsed;
2108: int i;
2109:
2110: aiUsed = sqlite3_malloc(sizeof(int)*nCell);
2111: if( !aiUsed ){
2112: return SQLITE_NOMEM;
2113: }
2114: memset(aiUsed, 0, sizeof(int)*nCell);
2115:
2116: PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
2117:
2118: memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
2119: memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
2120: nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
2121: nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
2122: aiUsed[iLeftSeed] = 1;
2123: aiUsed[iRightSeed] = 1;
2124:
2125: for(i=nCell-2; i>0; i--){
2126: RtreeCell *pNext;
2127: pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
2128: float diff =
2129: cellGrowth(pRtree, pBboxLeft, pNext) -
2130: cellGrowth(pRtree, pBboxRight, pNext)
2131: ;
2132: if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
2133: || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
2134: ){
2135: nodeInsertCell(pRtree, pRight, pNext);
2136: cellUnion(pRtree, pBboxRight, pNext);
2137: }else{
2138: nodeInsertCell(pRtree, pLeft, pNext);
2139: cellUnion(pRtree, pBboxLeft, pNext);
2140: }
2141: }
2142:
2143: sqlite3_free(aiUsed);
2144: return SQLITE_OK;
2145: }
2146: #endif
2147:
2148: static int updateMapping(
2149: Rtree *pRtree,
2150: i64 iRowid,
2151: RtreeNode *pNode,
2152: int iHeight
2153: ){
2154: int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
2155: xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
2156: if( iHeight>0 ){
2157: RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
2158: if( pChild ){
2159: nodeRelease(pRtree, pChild->pParent);
2160: nodeReference(pNode);
2161: pChild->pParent = pNode;
2162: }
2163: }
2164: return xSetMapping(pRtree, iRowid, pNode->iNode);
2165: }
2166:
2167: static int SplitNode(
2168: Rtree *pRtree,
2169: RtreeNode *pNode,
2170: RtreeCell *pCell,
2171: int iHeight
2172: ){
2173: int i;
2174: int newCellIsRight = 0;
2175:
2176: int rc = SQLITE_OK;
2177: int nCell = NCELL(pNode);
2178: RtreeCell *aCell;
2179: int *aiUsed;
2180:
2181: RtreeNode *pLeft = 0;
2182: RtreeNode *pRight = 0;
2183:
2184: RtreeCell leftbbox;
2185: RtreeCell rightbbox;
2186:
2187: /* Allocate an array and populate it with a copy of pCell and
2188: ** all cells from node pLeft. Then zero the original node.
2189: */
2190: aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
2191: if( !aCell ){
2192: rc = SQLITE_NOMEM;
2193: goto splitnode_out;
2194: }
2195: aiUsed = (int *)&aCell[nCell+1];
2196: memset(aiUsed, 0, sizeof(int)*(nCell+1));
2197: for(i=0; i<nCell; i++){
2198: nodeGetCell(pRtree, pNode, i, &aCell[i]);
2199: }
2200: nodeZero(pRtree, pNode);
2201: memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
2202: nCell++;
2203:
2204: if( pNode->iNode==1 ){
2205: pRight = nodeNew(pRtree, pNode);
2206: pLeft = nodeNew(pRtree, pNode);
2207: pRtree->iDepth++;
2208: pNode->isDirty = 1;
2209: writeInt16(pNode->zData, pRtree->iDepth);
2210: }else{
2211: pLeft = pNode;
2212: pRight = nodeNew(pRtree, pLeft->pParent);
2213: nodeReference(pLeft);
2214: }
2215:
2216: if( !pLeft || !pRight ){
2217: rc = SQLITE_NOMEM;
2218: goto splitnode_out;
2219: }
2220:
2221: memset(pLeft->zData, 0, pRtree->iNodeSize);
2222: memset(pRight->zData, 0, pRtree->iNodeSize);
2223:
2224: rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
2225: if( rc!=SQLITE_OK ){
2226: goto splitnode_out;
2227: }
2228:
2229: /* Ensure both child nodes have node numbers assigned to them by calling
2230: ** nodeWrite(). Node pRight always needs a node number, as it was created
2231: ** by nodeNew() above. But node pLeft sometimes already has a node number.
2232: ** In this case avoid the all to nodeWrite().
2233: */
2234: if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
2235: || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
2236: ){
2237: goto splitnode_out;
2238: }
2239:
2240: rightbbox.iRowid = pRight->iNode;
2241: leftbbox.iRowid = pLeft->iNode;
2242:
2243: if( pNode->iNode==1 ){
2244: rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
2245: if( rc!=SQLITE_OK ){
2246: goto splitnode_out;
2247: }
2248: }else{
2249: RtreeNode *pParent = pLeft->pParent;
2250: int iCell;
2251: rc = nodeParentIndex(pRtree, pLeft, &iCell);
2252: if( rc==SQLITE_OK ){
2253: nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
2254: rc = AdjustTree(pRtree, pParent, &leftbbox);
2255: }
2256: if( rc!=SQLITE_OK ){
2257: goto splitnode_out;
2258: }
2259: }
2260: if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
2261: goto splitnode_out;
2262: }
2263:
2264: for(i=0; i<NCELL(pRight); i++){
2265: i64 iRowid = nodeGetRowid(pRtree, pRight, i);
2266: rc = updateMapping(pRtree, iRowid, pRight, iHeight);
2267: if( iRowid==pCell->iRowid ){
2268: newCellIsRight = 1;
2269: }
2270: if( rc!=SQLITE_OK ){
2271: goto splitnode_out;
2272: }
2273: }
2274: if( pNode->iNode==1 ){
2275: for(i=0; i<NCELL(pLeft); i++){
2276: i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
2277: rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
2278: if( rc!=SQLITE_OK ){
2279: goto splitnode_out;
2280: }
2281: }
2282: }else if( newCellIsRight==0 ){
2283: rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
2284: }
2285:
2286: if( rc==SQLITE_OK ){
2287: rc = nodeRelease(pRtree, pRight);
2288: pRight = 0;
2289: }
2290: if( rc==SQLITE_OK ){
2291: rc = nodeRelease(pRtree, pLeft);
2292: pLeft = 0;
2293: }
2294:
2295: splitnode_out:
2296: nodeRelease(pRtree, pRight);
2297: nodeRelease(pRtree, pLeft);
2298: sqlite3_free(aCell);
2299: return rc;
2300: }
2301:
2302: /*
2303: ** If node pLeaf is not the root of the r-tree and its pParent pointer is
2304: ** still NULL, load all ancestor nodes of pLeaf into memory and populate
2305: ** the pLeaf->pParent chain all the way up to the root node.
2306: **
2307: ** This operation is required when a row is deleted (or updated - an update
2308: ** is implemented as a delete followed by an insert). SQLite provides the
2309: ** rowid of the row to delete, which can be used to find the leaf on which
2310: ** the entry resides (argument pLeaf). Once the leaf is located, this
2311: ** function is called to determine its ancestry.
2312: */
2313: static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
2314: int rc = SQLITE_OK;
2315: RtreeNode *pChild = pLeaf;
2316: while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
2317: int rc2 = SQLITE_OK; /* sqlite3_reset() return code */
2318: sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
2319: rc = sqlite3_step(pRtree->pReadParent);
2320: if( rc==SQLITE_ROW ){
2321: RtreeNode *pTest; /* Used to test for reference loops */
2322: i64 iNode; /* Node number of parent node */
2323:
2324: /* Before setting pChild->pParent, test that we are not creating a
2325: ** loop of references (as we would if, say, pChild==pParent). We don't
2326: ** want to do this as it leads to a memory leak when trying to delete
2327: ** the referenced counted node structures.
2328: */
2329: iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
2330: for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
2331: if( !pTest ){
2332: rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
2333: }
2334: }
2335: rc = sqlite3_reset(pRtree->pReadParent);
2336: if( rc==SQLITE_OK ) rc = rc2;
2337: if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT_VTAB;
2338: pChild = pChild->pParent;
2339: }
2340: return rc;
2341: }
2342:
2343: static int deleteCell(Rtree *, RtreeNode *, int, int);
2344:
2345: static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
2346: int rc;
2347: int rc2;
2348: RtreeNode *pParent = 0;
2349: int iCell;
2350:
2351: assert( pNode->nRef==1 );
2352:
2353: /* Remove the entry in the parent cell. */
2354: rc = nodeParentIndex(pRtree, pNode, &iCell);
2355: if( rc==SQLITE_OK ){
2356: pParent = pNode->pParent;
2357: pNode->pParent = 0;
2358: rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
2359: }
2360: rc2 = nodeRelease(pRtree, pParent);
2361: if( rc==SQLITE_OK ){
2362: rc = rc2;
2363: }
2364: if( rc!=SQLITE_OK ){
2365: return rc;
2366: }
2367:
2368: /* Remove the xxx_node entry. */
2369: sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
2370: sqlite3_step(pRtree->pDeleteNode);
2371: if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
2372: return rc;
2373: }
2374:
2375: /* Remove the xxx_parent entry. */
2376: sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
2377: sqlite3_step(pRtree->pDeleteParent);
2378: if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
2379: return rc;
2380: }
2381:
2382: /* Remove the node from the in-memory hash table and link it into
2383: ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
2384: */
2385: nodeHashDelete(pRtree, pNode);
2386: pNode->iNode = iHeight;
2387: pNode->pNext = pRtree->pDeleted;
2388: pNode->nRef++;
2389: pRtree->pDeleted = pNode;
2390:
2391: return SQLITE_OK;
2392: }
2393:
2394: static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
2395: RtreeNode *pParent = pNode->pParent;
2396: int rc = SQLITE_OK;
2397: if( pParent ){
2398: int ii;
2399: int nCell = NCELL(pNode);
2400: RtreeCell box; /* Bounding box for pNode */
2401: nodeGetCell(pRtree, pNode, 0, &box);
2402: for(ii=1; ii<nCell; ii++){
2403: RtreeCell cell;
2404: nodeGetCell(pRtree, pNode, ii, &cell);
2405: cellUnion(pRtree, &box, &cell);
2406: }
2407: box.iRowid = pNode->iNode;
2408: rc = nodeParentIndex(pRtree, pNode, &ii);
2409: if( rc==SQLITE_OK ){
2410: nodeOverwriteCell(pRtree, pParent, &box, ii);
2411: rc = fixBoundingBox(pRtree, pParent);
2412: }
2413: }
2414: return rc;
2415: }
2416:
2417: /*
2418: ** Delete the cell at index iCell of node pNode. After removing the
2419: ** cell, adjust the r-tree data structure if required.
2420: */
2421: static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
2422: RtreeNode *pParent;
2423: int rc;
2424:
2425: if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
2426: return rc;
2427: }
2428:
2429: /* Remove the cell from the node. This call just moves bytes around
2430: ** the in-memory node image, so it cannot fail.
2431: */
2432: nodeDeleteCell(pRtree, pNode, iCell);
2433:
2434: /* If the node is not the tree root and now has less than the minimum
2435: ** number of cells, remove it from the tree. Otherwise, update the
2436: ** cell in the parent node so that it tightly contains the updated
2437: ** node.
2438: */
2439: pParent = pNode->pParent;
2440: assert( pParent || pNode->iNode==1 );
2441: if( pParent ){
2442: if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
2443: rc = removeNode(pRtree, pNode, iHeight);
2444: }else{
2445: rc = fixBoundingBox(pRtree, pNode);
2446: }
2447: }
2448:
2449: return rc;
2450: }
2451:
2452: static int Reinsert(
2453: Rtree *pRtree,
2454: RtreeNode *pNode,
2455: RtreeCell *pCell,
2456: int iHeight
2457: ){
2458: int *aOrder;
2459: int *aSpare;
2460: RtreeCell *aCell;
2461: float *aDistance;
2462: int nCell;
2463: float aCenterCoord[RTREE_MAX_DIMENSIONS];
2464: int iDim;
2465: int ii;
2466: int rc = SQLITE_OK;
2467:
2468: memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
2469:
2470: nCell = NCELL(pNode)+1;
2471:
2472: /* Allocate the buffers used by this operation. The allocation is
2473: ** relinquished before this function returns.
2474: */
2475: aCell = (RtreeCell *)sqlite3_malloc(nCell * (
2476: sizeof(RtreeCell) + /* aCell array */
2477: sizeof(int) + /* aOrder array */
2478: sizeof(int) + /* aSpare array */
2479: sizeof(float) /* aDistance array */
2480: ));
2481: if( !aCell ){
2482: return SQLITE_NOMEM;
2483: }
2484: aOrder = (int *)&aCell[nCell];
2485: aSpare = (int *)&aOrder[nCell];
2486: aDistance = (float *)&aSpare[nCell];
2487:
2488: for(ii=0; ii<nCell; ii++){
2489: if( ii==(nCell-1) ){
2490: memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
2491: }else{
2492: nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
2493: }
2494: aOrder[ii] = ii;
2495: for(iDim=0; iDim<pRtree->nDim; iDim++){
2496: aCenterCoord[iDim] += (float)DCOORD(aCell[ii].aCoord[iDim*2]);
2497: aCenterCoord[iDim] += (float)DCOORD(aCell[ii].aCoord[iDim*2+1]);
2498: }
2499: }
2500: for(iDim=0; iDim<pRtree->nDim; iDim++){
2501: aCenterCoord[iDim] = (float)(aCenterCoord[iDim]/((float)nCell*2.0));
2502: }
2503:
2504: for(ii=0; ii<nCell; ii++){
2505: aDistance[ii] = 0.0;
2506: for(iDim=0; iDim<pRtree->nDim; iDim++){
2507: float coord = (float)(DCOORD(aCell[ii].aCoord[iDim*2+1]) -
2508: DCOORD(aCell[ii].aCoord[iDim*2]));
2509: aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
2510: }
2511: }
2512:
2513: SortByDistance(aOrder, nCell, aDistance, aSpare);
2514: nodeZero(pRtree, pNode);
2515:
2516: for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
2517: RtreeCell *p = &aCell[aOrder[ii]];
2518: nodeInsertCell(pRtree, pNode, p);
2519: if( p->iRowid==pCell->iRowid ){
2520: if( iHeight==0 ){
2521: rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
2522: }else{
2523: rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
2524: }
2525: }
2526: }
2527: if( rc==SQLITE_OK ){
2528: rc = fixBoundingBox(pRtree, pNode);
2529: }
2530: for(; rc==SQLITE_OK && ii<nCell; ii++){
2531: /* Find a node to store this cell in. pNode->iNode currently contains
2532: ** the height of the sub-tree headed by the cell.
2533: */
2534: RtreeNode *pInsert;
2535: RtreeCell *p = &aCell[aOrder[ii]];
2536: rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
2537: if( rc==SQLITE_OK ){
2538: int rc2;
2539: rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);
2540: rc2 = nodeRelease(pRtree, pInsert);
2541: if( rc==SQLITE_OK ){
2542: rc = rc2;
2543: }
2544: }
2545: }
2546:
2547: sqlite3_free(aCell);
2548: return rc;
2549: }
2550:
2551: /*
2552: ** Insert cell pCell into node pNode. Node pNode is the head of a
2553: ** subtree iHeight high (leaf nodes have iHeight==0).
2554: */
2555: static int rtreeInsertCell(
2556: Rtree *pRtree,
2557: RtreeNode *pNode,
2558: RtreeCell *pCell,
2559: int iHeight
2560: ){
2561: int rc = SQLITE_OK;
2562: if( iHeight>0 ){
2563: RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
2564: if( pChild ){
2565: nodeRelease(pRtree, pChild->pParent);
2566: nodeReference(pNode);
2567: pChild->pParent = pNode;
2568: }
2569: }
2570: if( nodeInsertCell(pRtree, pNode, pCell) ){
2571: #if VARIANT_RSTARTREE_REINSERT
2572: if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
2573: rc = SplitNode(pRtree, pNode, pCell, iHeight);
2574: }else{
2575: pRtree->iReinsertHeight = iHeight;
2576: rc = Reinsert(pRtree, pNode, pCell, iHeight);
2577: }
2578: #else
2579: rc = SplitNode(pRtree, pNode, pCell, iHeight);
2580: #endif
2581: }else{
2582: rc = AdjustTree(pRtree, pNode, pCell);
2583: if( rc==SQLITE_OK ){
2584: if( iHeight==0 ){
2585: rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
2586: }else{
2587: rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
2588: }
2589: }
2590: }
2591: return rc;
2592: }
2593:
2594: static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
2595: int ii;
2596: int rc = SQLITE_OK;
2597: int nCell = NCELL(pNode);
2598:
2599: for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
2600: RtreeNode *pInsert;
2601: RtreeCell cell;
2602: nodeGetCell(pRtree, pNode, ii, &cell);
2603:
2604: /* Find a node to store this cell in. pNode->iNode currently contains
2605: ** the height of the sub-tree headed by the cell.
2606: */
2607: rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert);
2608: if( rc==SQLITE_OK ){
2609: int rc2;
2610: rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode);
2611: rc2 = nodeRelease(pRtree, pInsert);
2612: if( rc==SQLITE_OK ){
2613: rc = rc2;
2614: }
2615: }
2616: }
2617: return rc;
2618: }
2619:
2620: /*
2621: ** Select a currently unused rowid for a new r-tree record.
2622: */
2623: static int newRowid(Rtree *pRtree, i64 *piRowid){
2624: int rc;
2625: sqlite3_bind_null(pRtree->pWriteRowid, 1);
2626: sqlite3_bind_null(pRtree->pWriteRowid, 2);
2627: sqlite3_step(pRtree->pWriteRowid);
2628: rc = sqlite3_reset(pRtree->pWriteRowid);
2629: *piRowid = sqlite3_last_insert_rowid(pRtree->db);
2630: return rc;
2631: }
2632:
2633: /*
2634: ** Remove the entry with rowid=iDelete from the r-tree structure.
2635: */
2636: static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){
2637: int rc; /* Return code */
2638: RtreeNode *pLeaf; /* Leaf node containing record iDelete */
2639: int iCell; /* Index of iDelete cell in pLeaf */
2640: RtreeNode *pRoot; /* Root node of rtree structure */
2641:
2642:
2643: /* Obtain a reference to the root node to initialise Rtree.iDepth */
2644: rc = nodeAcquire(pRtree, 1, 0, &pRoot);
2645:
2646: /* Obtain a reference to the leaf node that contains the entry
2647: ** about to be deleted.
2648: */
2649: if( rc==SQLITE_OK ){
2650: rc = findLeafNode(pRtree, iDelete, &pLeaf);
2651: }
2652:
2653: /* Delete the cell in question from the leaf node. */
2654: if( rc==SQLITE_OK ){
2655: int rc2;
2656: rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
2657: if( rc==SQLITE_OK ){
2658: rc = deleteCell(pRtree, pLeaf, iCell, 0);
2659: }
2660: rc2 = nodeRelease(pRtree, pLeaf);
2661: if( rc==SQLITE_OK ){
2662: rc = rc2;
2663: }
2664: }
2665:
2666: /* Delete the corresponding entry in the <rtree>_rowid table. */
2667: if( rc==SQLITE_OK ){
2668: sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
2669: sqlite3_step(pRtree->pDeleteRowid);
2670: rc = sqlite3_reset(pRtree->pDeleteRowid);
2671: }
2672:
2673: /* Check if the root node now has exactly one child. If so, remove
2674: ** it, schedule the contents of the child for reinsertion and
2675: ** reduce the tree height by one.
2676: **
2677: ** This is equivalent to copying the contents of the child into
2678: ** the root node (the operation that Gutman's paper says to perform
2679: ** in this scenario).
2680: */
2681: if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){
2682: int rc2;
2683: RtreeNode *pChild;
2684: i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
2685: rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
2686: if( rc==SQLITE_OK ){
2687: rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
2688: }
2689: rc2 = nodeRelease(pRtree, pChild);
2690: if( rc==SQLITE_OK ) rc = rc2;
2691: if( rc==SQLITE_OK ){
2692: pRtree->iDepth--;
2693: writeInt16(pRoot->zData, pRtree->iDepth);
2694: pRoot->isDirty = 1;
2695: }
2696: }
2697:
2698: /* Re-insert the contents of any underfull nodes removed from the tree. */
2699: for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
2700: if( rc==SQLITE_OK ){
2701: rc = reinsertNodeContent(pRtree, pLeaf);
2702: }
2703: pRtree->pDeleted = pLeaf->pNext;
2704: sqlite3_free(pLeaf);
2705: }
2706:
2707: /* Release the reference to the root node. */
2708: if( rc==SQLITE_OK ){
2709: rc = nodeRelease(pRtree, pRoot);
2710: }else{
2711: nodeRelease(pRtree, pRoot);
2712: }
2713:
2714: return rc;
2715: }
2716:
2717: /*
2718: ** The xUpdate method for rtree module virtual tables.
2719: */
2720: static int rtreeUpdate(
2721: sqlite3_vtab *pVtab,
2722: int nData,
2723: sqlite3_value **azData,
2724: sqlite_int64 *pRowid
2725: ){
2726: Rtree *pRtree = (Rtree *)pVtab;
2727: int rc = SQLITE_OK;
2728: RtreeCell cell; /* New cell to insert if nData>1 */
2729: int bHaveRowid = 0; /* Set to 1 after new rowid is determined */
2730:
2731: rtreeReference(pRtree);
2732: assert(nData>=1);
2733:
2734: /* Constraint handling. A write operation on an r-tree table may return
2735: ** SQLITE_CONSTRAINT for two reasons:
2736: **
2737: ** 1. A duplicate rowid value, or
2738: ** 2. The supplied data violates the "x2>=x1" constraint.
2739: **
2740: ** In the first case, if the conflict-handling mode is REPLACE, then
2741: ** the conflicting row can be removed before proceeding. In the second
2742: ** case, SQLITE_CONSTRAINT must be returned regardless of the
2743: ** conflict-handling mode specified by the user.
2744: */
2745: if( nData>1 ){
2746: int ii;
2747:
2748: /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
2749: assert( nData==(pRtree->nDim*2 + 3) );
2750: if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
2751: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
2752: cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
2753: cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
2754: if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
2755: rc = SQLITE_CONSTRAINT;
2756: goto constraint;
2757: }
2758: }
2759: }else{
2760: for(ii=0; ii<(pRtree->nDim*2); ii+=2){
2761: cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
2762: cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
2763: if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
2764: rc = SQLITE_CONSTRAINT;
2765: goto constraint;
2766: }
2767: }
2768: }
2769:
2770: /* If a rowid value was supplied, check if it is already present in
2771: ** the table. If so, the constraint has failed. */
2772: if( sqlite3_value_type(azData[2])!=SQLITE_NULL ){
2773: cell.iRowid = sqlite3_value_int64(azData[2]);
2774: if( sqlite3_value_type(azData[0])==SQLITE_NULL
2775: || sqlite3_value_int64(azData[0])!=cell.iRowid
2776: ){
2777: int steprc;
2778: sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
2779: steprc = sqlite3_step(pRtree->pReadRowid);
2780: rc = sqlite3_reset(pRtree->pReadRowid);
2781: if( SQLITE_ROW==steprc ){
2782: if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){
2783: rc = rtreeDeleteRowid(pRtree, cell.iRowid);
2784: }else{
2785: rc = SQLITE_CONSTRAINT;
2786: goto constraint;
2787: }
2788: }
2789: }
2790: bHaveRowid = 1;
2791: }
2792: }
2793:
2794: /* If azData[0] is not an SQL NULL value, it is the rowid of a
2795: ** record to delete from the r-tree table. The following block does
2796: ** just that.
2797: */
2798: if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
2799: rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(azData[0]));
2800: }
2801:
2802: /* If the azData[] array contains more than one element, elements
2803: ** (azData[2]..azData[argc-1]) contain a new record to insert into
2804: ** the r-tree structure.
2805: */
2806: if( rc==SQLITE_OK && nData>1 ){
2807: /* Insert the new record into the r-tree */
2808: RtreeNode *pLeaf;
2809:
2810: /* Figure out the rowid of the new row. */
2811: if( bHaveRowid==0 ){
2812: rc = newRowid(pRtree, &cell.iRowid);
2813: }
2814: *pRowid = cell.iRowid;
2815:
2816: if( rc==SQLITE_OK ){
2817: rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
2818: }
2819: if( rc==SQLITE_OK ){
2820: int rc2;
2821: pRtree->iReinsertHeight = -1;
2822: rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
2823: rc2 = nodeRelease(pRtree, pLeaf);
2824: if( rc==SQLITE_OK ){
2825: rc = rc2;
2826: }
2827: }
2828: }
2829:
2830: constraint:
2831: rtreeRelease(pRtree);
2832: return rc;
2833: }
2834:
2835: /*
2836: ** The xRename method for rtree module virtual tables.
2837: */
2838: static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
2839: Rtree *pRtree = (Rtree *)pVtab;
2840: int rc = SQLITE_NOMEM;
2841: char *zSql = sqlite3_mprintf(
2842: "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
2843: "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
2844: "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
2845: , pRtree->zDb, pRtree->zName, zNewName
2846: , pRtree->zDb, pRtree->zName, zNewName
2847: , pRtree->zDb, pRtree->zName, zNewName
2848: );
2849: if( zSql ){
2850: rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
2851: sqlite3_free(zSql);
2852: }
2853: return rc;
2854: }
2855:
2856: static sqlite3_module rtreeModule = {
2857: 0, /* iVersion */
2858: rtreeCreate, /* xCreate - create a table */
2859: rtreeConnect, /* xConnect - connect to an existing table */
2860: rtreeBestIndex, /* xBestIndex - Determine search strategy */
2861: rtreeDisconnect, /* xDisconnect - Disconnect from a table */
2862: rtreeDestroy, /* xDestroy - Drop a table */
2863: rtreeOpen, /* xOpen - open a cursor */
2864: rtreeClose, /* xClose - close a cursor */
2865: rtreeFilter, /* xFilter - configure scan constraints */
2866: rtreeNext, /* xNext - advance a cursor */
2867: rtreeEof, /* xEof */
2868: rtreeColumn, /* xColumn - read data */
2869: rtreeRowid, /* xRowid - read data */
2870: rtreeUpdate, /* xUpdate - write data */
2871: 0, /* xBegin - begin transaction */
2872: 0, /* xSync - sync transaction */
2873: 0, /* xCommit - commit transaction */
2874: 0, /* xRollback - rollback transaction */
2875: 0, /* xFindFunction - function overloading */
2876: rtreeRename, /* xRename - rename the table */
2877: 0, /* xSavepoint */
2878: 0, /* xRelease */
2879: 0 /* xRollbackTo */
2880: };
2881:
2882: static int rtreeSqlInit(
2883: Rtree *pRtree,
2884: sqlite3 *db,
2885: const char *zDb,
2886: const char *zPrefix,
2887: int isCreate
2888: ){
2889: int rc = SQLITE_OK;
2890:
2891: #define N_STATEMENT 9
2892: static const char *azSql[N_STATEMENT] = {
2893: /* Read and write the xxx_node table */
2894: "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
2895: "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
2896: "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
2897:
2898: /* Read and write the xxx_rowid table */
2899: "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
2900: "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
2901: "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
2902:
2903: /* Read and write the xxx_parent table */
2904: "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
2905: "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
2906: "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
2907: };
2908: sqlite3_stmt **appStmt[N_STATEMENT];
2909: int i;
2910:
2911: pRtree->db = db;
2912:
2913: if( isCreate ){
2914: char *zCreate = sqlite3_mprintf(
2915: "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
2916: "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
2917: "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
2918: "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
2919: zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
2920: );
2921: if( !zCreate ){
2922: return SQLITE_NOMEM;
2923: }
2924: rc = sqlite3_exec(db, zCreate, 0, 0, 0);
2925: sqlite3_free(zCreate);
2926: if( rc!=SQLITE_OK ){
2927: return rc;
2928: }
2929: }
2930:
2931: appStmt[0] = &pRtree->pReadNode;
2932: appStmt[1] = &pRtree->pWriteNode;
2933: appStmt[2] = &pRtree->pDeleteNode;
2934: appStmt[3] = &pRtree->pReadRowid;
2935: appStmt[4] = &pRtree->pWriteRowid;
2936: appStmt[5] = &pRtree->pDeleteRowid;
2937: appStmt[6] = &pRtree->pReadParent;
2938: appStmt[7] = &pRtree->pWriteParent;
2939: appStmt[8] = &pRtree->pDeleteParent;
2940:
2941: for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
2942: char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
2943: if( zSql ){
2944: rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0);
2945: }else{
2946: rc = SQLITE_NOMEM;
2947: }
2948: sqlite3_free(zSql);
2949: }
2950:
2951: return rc;
2952: }
2953:
2954: /*
2955: ** The second argument to this function contains the text of an SQL statement
2956: ** that returns a single integer value. The statement is compiled and executed
2957: ** using database connection db. If successful, the integer value returned
2958: ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
2959: ** code is returned and the value of *piVal after returning is not defined.
2960: */
2961: static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){
2962: int rc = SQLITE_NOMEM;
2963: if( zSql ){
2964: sqlite3_stmt *pStmt = 0;
2965: rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
2966: if( rc==SQLITE_OK ){
2967: if( SQLITE_ROW==sqlite3_step(pStmt) ){
2968: *piVal = sqlite3_column_int(pStmt, 0);
2969: }
2970: rc = sqlite3_finalize(pStmt);
2971: }
2972: }
2973: return rc;
2974: }
2975:
2976: /*
2977: ** This function is called from within the xConnect() or xCreate() method to
2978: ** determine the node-size used by the rtree table being created or connected
2979: ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
2980: ** Otherwise, an SQLite error code is returned.
2981: **
2982: ** If this function is being called as part of an xConnect(), then the rtree
2983: ** table already exists. In this case the node-size is determined by inspecting
2984: ** the root node of the tree.
2985: **
2986: ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size.
2987: ** This ensures that each node is stored on a single database page. If the
2988: ** database page-size is so large that more than RTREE_MAXCELLS entries
2989: ** would fit in a single node, use a smaller node-size.
2990: */
2991: static int getNodeSize(
2992: sqlite3 *db, /* Database handle */
2993: Rtree *pRtree, /* Rtree handle */
2994: int isCreate /* True for xCreate, false for xConnect */
2995: ){
2996: int rc;
2997: char *zSql;
2998: if( isCreate ){
2999: int iPageSize = 0;
3000: zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
3001: rc = getIntFromStmt(db, zSql, &iPageSize);
3002: if( rc==SQLITE_OK ){
3003: pRtree->iNodeSize = iPageSize-64;
3004: if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
3005: pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
3006: }
3007: }
3008: }else{
3009: zSql = sqlite3_mprintf(
3010: "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
3011: pRtree->zDb, pRtree->zName
3012: );
3013: rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
3014: }
3015:
3016: sqlite3_free(zSql);
3017: return rc;
3018: }
3019:
3020: /*
3021: ** This function is the implementation of both the xConnect and xCreate
3022: ** methods of the r-tree virtual table.
3023: **
3024: ** argv[0] -> module name
3025: ** argv[1] -> database name
3026: ** argv[2] -> table name
3027: ** argv[...] -> column names...
3028: */
3029: static int rtreeInit(
3030: sqlite3 *db, /* Database connection */
3031: void *pAux, /* One of the RTREE_COORD_* constants */
3032: int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */
3033: sqlite3_vtab **ppVtab, /* OUT: New virtual table */
3034: char **pzErr, /* OUT: Error message, if any */
3035: int isCreate /* True for xCreate, false for xConnect */
3036: ){
3037: int rc = SQLITE_OK;
3038: Rtree *pRtree;
3039: int nDb; /* Length of string argv[1] */
3040: int nName; /* Length of string argv[2] */
3041: int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
3042:
3043: const char *aErrMsg[] = {
3044: 0, /* 0 */
3045: "Wrong number of columns for an rtree table", /* 1 */
3046: "Too few columns for an rtree table", /* 2 */
3047: "Too many columns for an rtree table" /* 3 */
3048: };
3049:
3050: int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
3051: if( aErrMsg[iErr] ){
3052: *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
3053: return SQLITE_ERROR;
3054: }
3055:
3056: sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
3057:
3058: /* Allocate the sqlite3_vtab structure */
3059: nDb = strlen(argv[1]);
3060: nName = strlen(argv[2]);
3061: pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
3062: if( !pRtree ){
3063: return SQLITE_NOMEM;
3064: }
3065: memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
3066: pRtree->nBusy = 1;
3067: pRtree->base.pModule = &rtreeModule;
3068: pRtree->zDb = (char *)&pRtree[1];
3069: pRtree->zName = &pRtree->zDb[nDb+1];
3070: pRtree->nDim = (argc-4)/2;
3071: pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
3072: pRtree->eCoordType = eCoordType;
3073: memcpy(pRtree->zDb, argv[1], nDb);
3074: memcpy(pRtree->zName, argv[2], nName);
3075:
3076: /* Figure out the node size to use. */
3077: rc = getNodeSize(db, pRtree, isCreate);
3078:
3079: /* Create/Connect to the underlying relational database schema. If
3080: ** that is successful, call sqlite3_declare_vtab() to configure
3081: ** the r-tree table schema.
3082: */
3083: if( rc==SQLITE_OK ){
3084: if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
3085: *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3086: }else{
3087: char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
3088: char *zTmp;
3089: int ii;
3090: for(ii=4; zSql && ii<argc; ii++){
3091: zTmp = zSql;
3092: zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
3093: sqlite3_free(zTmp);
3094: }
3095: if( zSql ){
3096: zTmp = zSql;
3097: zSql = sqlite3_mprintf("%s);", zTmp);
3098: sqlite3_free(zTmp);
3099: }
3100: if( !zSql ){
3101: rc = SQLITE_NOMEM;
3102: }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
3103: *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
3104: }
3105: sqlite3_free(zSql);
3106: }
3107: }
3108:
3109: if( rc==SQLITE_OK ){
3110: *ppVtab = (sqlite3_vtab *)pRtree;
3111: }else{
3112: rtreeRelease(pRtree);
3113: }
3114: return rc;
3115: }
3116:
3117:
3118: /*
3119: ** Implementation of a scalar function that decodes r-tree nodes to
3120: ** human readable strings. This can be used for debugging and analysis.
3121: **
3122: ** The scalar function takes two arguments, a blob of data containing
3123: ** an r-tree node, and the number of dimensions the r-tree indexes.
3124: ** For a two-dimensional r-tree structure called "rt", to deserialize
3125: ** all nodes, a statement like:
3126: **
3127: ** SELECT rtreenode(2, data) FROM rt_node;
3128: **
3129: ** The human readable string takes the form of a Tcl list with one
3130: ** entry for each cell in the r-tree node. Each entry is itself a
3131: ** list, containing the 8-byte rowid/pageno followed by the
3132: ** <num-dimension>*2 coordinates.
3133: */
3134: static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3135: char *zText = 0;
3136: RtreeNode node;
3137: Rtree tree;
3138: int ii;
3139:
3140: UNUSED_PARAMETER(nArg);
3141: memset(&node, 0, sizeof(RtreeNode));
3142: memset(&tree, 0, sizeof(Rtree));
3143: tree.nDim = sqlite3_value_int(apArg[0]);
3144: tree.nBytesPerCell = 8 + 8 * tree.nDim;
3145: node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
3146:
3147: for(ii=0; ii<NCELL(&node); ii++){
3148: char zCell[512];
3149: int nCell = 0;
3150: RtreeCell cell;
3151: int jj;
3152:
3153: nodeGetCell(&tree, &node, ii, &cell);
3154: sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
3155: nCell = strlen(zCell);
3156: for(jj=0; jj<tree.nDim*2; jj++){
3157: sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
3158: nCell = strlen(zCell);
3159: }
3160:
3161: if( zText ){
3162: char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
3163: sqlite3_free(zText);
3164: zText = zTextNew;
3165: }else{
3166: zText = sqlite3_mprintf("{%s}", zCell);
3167: }
3168: }
3169:
3170: sqlite3_result_text(ctx, zText, -1, sqlite3_free);
3171: }
3172:
3173: static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
3174: UNUSED_PARAMETER(nArg);
3175: if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB
3176: || sqlite3_value_bytes(apArg[0])<2
3177: ){
3178: sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1);
3179: }else{
3180: u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
3181: sqlite3_result_int(ctx, readInt16(zBlob));
3182: }
3183: }
3184:
3185: /*
3186: ** Register the r-tree module with database handle db. This creates the
3187: ** virtual table module "rtree" and the debugging/analysis scalar
3188: ** function "rtreenode".
3189: */
3190: int sqlite3RtreeInit(sqlite3 *db){
3191: const int utf8 = SQLITE_UTF8;
3192: int rc;
3193:
3194: rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
3195: if( rc==SQLITE_OK ){
3196: rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
3197: }
3198: if( rc==SQLITE_OK ){
3199: void *c = (void *)RTREE_COORD_REAL32;
3200: rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
3201: }
3202: if( rc==SQLITE_OK ){
3203: void *c = (void *)RTREE_COORD_INT32;
3204: rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
3205: }
3206:
3207: return rc;
3208: }
3209:
3210: /*
3211: ** A version of sqlite3_free() that can be used as a callback. This is used
3212: ** in two places - as the destructor for the blob value returned by the
3213: ** invocation of a geometry function, and as the destructor for the geometry
3214: ** functions themselves.
3215: */
3216: static void doSqlite3Free(void *p){
3217: sqlite3_free(p);
3218: }
3219:
3220: /*
3221: ** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
3222: ** scalar user function. This C function is the callback used for all such
3223: ** registered SQL functions.
3224: **
3225: ** The scalar user functions return a blob that is interpreted by r-tree
3226: ** table MATCH operators.
3227: */
3228: static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
3229: RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
3230: RtreeMatchArg *pBlob;
3231: int nBlob;
3232:
3233: nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
3234: pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
3235: if( !pBlob ){
3236: sqlite3_result_error_nomem(ctx);
3237: }else{
3238: int i;
3239: pBlob->magic = RTREE_GEOMETRY_MAGIC;
3240: pBlob->xGeom = pGeomCtx->xGeom;
3241: pBlob->pContext = pGeomCtx->pContext;
3242: pBlob->nParam = nArg;
3243: for(i=0; i<nArg; i++){
3244: pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
3245: }
3246: sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
3247: }
3248: }
3249:
3250: /*
3251: ** Register a new geometry function for use with the r-tree MATCH operator.
3252: */
3253: int sqlite3_rtree_geometry_callback(
3254: sqlite3 *db,
3255: const char *zGeom,
3256: int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
3257: void *pContext
3258: ){
3259: RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */
3260:
3261: /* Allocate and populate the context object. */
3262: pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
3263: if( !pGeomCtx ) return SQLITE_NOMEM;
3264: pGeomCtx->xGeom = xGeom;
3265: pGeomCtx->pContext = pContext;
3266:
3267: /* Create the new user-function. Register a destructor function to delete
3268: ** the context object when it is no longer required. */
3269: return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY,
3270: (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
3271: );
3272: }
3273:
3274: #if !SQLITE_CORE
3275: int sqlite3_extension_init(
3276: sqlite3 *db,
3277: char **pzErrMsg,
3278: const sqlite3_api_routines *pApi
3279: ){
3280: SQLITE_EXTENSION_INIT2(pApi)
3281: return sqlite3RtreeInit(db);
3282: }
3283: #endif
3284:
3285: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rtree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / rtree