src/third_party/sqlite/src/ext/rtree/rtree.c

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