Annotation of embedaddon/sqlite3/ext/rtree/rtree.c, revision 1.1
1.1 ! misho 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