sl@0: /*
sl@0: ** 2001 September 15
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file contains code for implementations of the r-tree and r*-tree
sl@0: ** algorithms packaged as an SQLite virtual table module.
sl@0: **
sl@0: ** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $
sl@0: */
sl@0: 
sl@0: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
sl@0: 
sl@0: /*
sl@0: ** This file contains an implementation of a couple of different variants
sl@0: ** of the r-tree algorithm. See the README file for further details. The 
sl@0: ** same data-structure is used for all, but the algorithms for insert and
sl@0: ** delete operations vary. The variants used are selected at compile time 
sl@0: ** by defining the following symbols:
sl@0: */
sl@0: 
sl@0: /* Either, both or none of the following may be set to activate 
sl@0: ** r*tree variant algorithms.
sl@0: */
sl@0: #define VARIANT_RSTARTREE_CHOOSESUBTREE 0
sl@0: #define VARIANT_RSTARTREE_REINSERT      1
sl@0: 
sl@0: /* 
sl@0: ** Exactly one of the following must be set to 1.
sl@0: */
sl@0: #define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
sl@0: #define VARIANT_GUTTMAN_LINEAR_SPLIT    0
sl@0: #define VARIANT_RSTARTREE_SPLIT         1
sl@0: 
sl@0: #define VARIANT_GUTTMAN_SPLIT \
sl@0:         (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
sl@0: 
sl@0: #if VARIANT_GUTTMAN_QUADRATIC_SPLIT
sl@0:   #define PickNext QuadraticPickNext
sl@0:   #define PickSeeds QuadraticPickSeeds
sl@0:   #define AssignCells splitNodeGuttman
sl@0: #endif
sl@0: #if VARIANT_GUTTMAN_LINEAR_SPLIT
sl@0:   #define PickNext LinearPickNext
sl@0:   #define PickSeeds LinearPickSeeds
sl@0:   #define AssignCells splitNodeGuttman
sl@0: #endif
sl@0: #if VARIANT_RSTARTREE_SPLIT
sl@0:   #define AssignCells splitNodeStartree
sl@0: #endif
sl@0: 
sl@0: 
sl@0: #ifndef SQLITE_CORE
sl@0:   #include "sqlite3ext.h"
sl@0:   SQLITE_EXTENSION_INIT1
sl@0: #else
sl@0:   #include "sqlite3.h"
sl@0: #endif
sl@0: 
sl@0: #include <string.h>
sl@0: #include <assert.h>
sl@0: 
sl@0: #ifndef SQLITE_AMALGAMATION
sl@0: typedef sqlite3_int64 i64;
sl@0: typedef unsigned char u8;
sl@0: typedef unsigned int u32;
sl@0: #endif
sl@0: 
sl@0: typedef struct Rtree Rtree;
sl@0: typedef struct RtreeCursor RtreeCursor;
sl@0: typedef struct RtreeNode RtreeNode;
sl@0: typedef struct RtreeCell RtreeCell;
sl@0: typedef struct RtreeConstraint RtreeConstraint;
sl@0: typedef union RtreeCoord RtreeCoord;
sl@0: 
sl@0: /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
sl@0: #define RTREE_MAX_DIMENSIONS 5
sl@0: 
sl@0: /* Size of hash table Rtree.aHash. This hash table is not expected to
sl@0: ** ever contain very many entries, so a fixed number of buckets is 
sl@0: ** used.
sl@0: */
sl@0: #define HASHSIZE 128
sl@0: 
sl@0: /* 
sl@0: ** An rtree virtual-table object.
sl@0: */
sl@0: struct Rtree {
sl@0:   sqlite3_vtab base;
sl@0:   sqlite3 *db;                /* Host database connection */
sl@0:   int iNodeSize;              /* Size in bytes of each node in the node table */
sl@0:   int nDim;                   /* Number of dimensions */
sl@0:   int nBytesPerCell;          /* Bytes consumed per cell */
sl@0:   int iDepth;                 /* Current depth of the r-tree structure */
sl@0:   char *zDb;                  /* Name of database containing r-tree table */
sl@0:   char *zName;                /* Name of r-tree table */ 
sl@0:   RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
sl@0:   int nBusy;                  /* Current number of users of this structure */
sl@0: 
sl@0:   /* List of nodes removed during a CondenseTree operation. List is
sl@0:   ** linked together via the pointer normally used for hash chains -
sl@0:   ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 
sl@0:   ** headed by the node (leaf nodes have RtreeNode.iNode==0).
sl@0:   */
sl@0:   RtreeNode *pDeleted;
sl@0:   int iReinsertHeight;        /* Height of sub-trees Reinsert() has run on */
sl@0: 
sl@0:   /* Statements to read/write/delete a record from xxx_node */
sl@0:   sqlite3_stmt *pReadNode;
sl@0:   sqlite3_stmt *pWriteNode;
sl@0:   sqlite3_stmt *pDeleteNode;
sl@0: 
sl@0:   /* Statements to read/write/delete a record from xxx_rowid */
sl@0:   sqlite3_stmt *pReadRowid;
sl@0:   sqlite3_stmt *pWriteRowid;
sl@0:   sqlite3_stmt *pDeleteRowid;
sl@0: 
sl@0:   /* Statements to read/write/delete a record from xxx_parent */
sl@0:   sqlite3_stmt *pReadParent;
sl@0:   sqlite3_stmt *pWriteParent;
sl@0:   sqlite3_stmt *pDeleteParent;
sl@0: 
sl@0:   int eCoordType;
sl@0: };
sl@0: 
sl@0: /* Possible values for eCoordType: */
sl@0: #define RTREE_COORD_REAL32 0
sl@0: #define RTREE_COORD_INT32  1
sl@0: 
sl@0: /*
sl@0: ** The minimum number of cells allowed for a node is a third of the 
sl@0: ** maximum. In Gutman's notation:
sl@0: **
sl@0: **     m = M/3
sl@0: **
sl@0: ** If an R*-tree "Reinsert" operation is required, the same number of
sl@0: ** cells are removed from the overfull node and reinserted into the tree.
sl@0: */
sl@0: #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
sl@0: #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
sl@0: #define RTREE_MAXCELLS 51
sl@0: 
sl@0: /* 
sl@0: ** An rtree cursor object.
sl@0: */
sl@0: struct RtreeCursor {
sl@0:   sqlite3_vtab_cursor base;
sl@0:   RtreeNode *pNode;                 /* Node cursor is currently pointing at */
sl@0:   int iCell;                        /* Index of current cell in pNode */
sl@0:   int iStrategy;                    /* Copy of idxNum search parameter */
sl@0:   int nConstraint;                  /* Number of entries in aConstraint */
sl@0:   RtreeConstraint *aConstraint;     /* Search constraints. */
sl@0: };
sl@0: 
sl@0: union RtreeCoord {
sl@0:   float f;
sl@0:   int i;
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
sl@0: ** formatted as a double. This macro assumes that local variable pRtree points
sl@0: ** to the Rtree structure associated with the RtreeCoord.
sl@0: */
sl@0: #define DCOORD(coord) (                           \
sl@0:   (pRtree->eCoordType==RTREE_COORD_REAL32) ?      \
sl@0:     ((double)coord.f) :                           \
sl@0:     ((double)coord.i)                             \
sl@0: )
sl@0: 
sl@0: /*
sl@0: ** A search constraint.
sl@0: */
sl@0: struct RtreeConstraint {
sl@0:   int iCoord;                       /* Index of constrained coordinate */
sl@0:   int op;                           /* Constraining operation */
sl@0:   double rValue;                    /* Constraint value. */
sl@0: };
sl@0: 
sl@0: /* Possible values for RtreeConstraint.op */
sl@0: #define RTREE_EQ 0x41
sl@0: #define RTREE_LE 0x42
sl@0: #define RTREE_LT 0x43
sl@0: #define RTREE_GE 0x44
sl@0: #define RTREE_GT 0x45
sl@0: 
sl@0: /* 
sl@0: ** An rtree structure node.
sl@0: **
sl@0: ** Data format (RtreeNode.zData):
sl@0: **
sl@0: **   1. If the node is the root node (node 1), then the first 2 bytes
sl@0: **      of the node contain the tree depth as a big-endian integer.
sl@0: **      For non-root nodes, the first 2 bytes are left unused.
sl@0: **
sl@0: **   2. The next 2 bytes contain the number of entries currently 
sl@0: **      stored in the node.
sl@0: **
sl@0: **   3. The remainder of the node contains the node entries. Each entry
sl@0: **      consists of a single 8-byte integer followed by an even number
sl@0: **      of 4-byte coordinates. For leaf nodes the integer is the rowid
sl@0: **      of a record. For internal nodes it is the node number of a
sl@0: **      child page.
sl@0: */
sl@0: struct RtreeNode {
sl@0:   RtreeNode *pParent;               /* Parent node */
sl@0:   i64 iNode;
sl@0:   int nRef;
sl@0:   int isDirty;
sl@0:   u8 *zData;
sl@0:   RtreeNode *pNext;                 /* Next node in this hash chain */
sl@0: };
sl@0: #define NCELL(pNode) readInt16(&(pNode)->zData[2])
sl@0: 
sl@0: /* 
sl@0: ** Structure to store a deserialized rtree record.
sl@0: */
sl@0: struct RtreeCell {
sl@0:   i64 iRowid;
sl@0:   RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
sl@0: };
sl@0: 
sl@0: #define MAX(x,y) ((x) < (y) ? (y) : (x))
sl@0: #define MIN(x,y) ((x) > (y) ? (y) : (x))
sl@0: 
sl@0: /*
sl@0: ** Functions to deserialize a 16 bit integer, 32 bit real number and
sl@0: ** 64 bit integer. The deserialized value is returned.
sl@0: */
sl@0: static int readInt16(u8 *p){
sl@0:   return (p[0]<<8) + p[1];
sl@0: }
sl@0: static void readCoord(u8 *p, RtreeCoord *pCoord){
sl@0:   u32 i = (
sl@0:     (((u32)p[0]) << 24) + 
sl@0:     (((u32)p[1]) << 16) + 
sl@0:     (((u32)p[2]) <<  8) + 
sl@0:     (((u32)p[3]) <<  0)
sl@0:   );
sl@0:   *(u32 *)pCoord = i;
sl@0: }
sl@0: static i64 readInt64(u8 *p){
sl@0:   return (
sl@0:     (((i64)p[0]) << 56) + 
sl@0:     (((i64)p[1]) << 48) + 
sl@0:     (((i64)p[2]) << 40) + 
sl@0:     (((i64)p[3]) << 32) + 
sl@0:     (((i64)p[4]) << 24) + 
sl@0:     (((i64)p[5]) << 16) + 
sl@0:     (((i64)p[6]) <<  8) + 
sl@0:     (((i64)p[7]) <<  0)
sl@0:   );
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Functions to serialize a 16 bit integer, 32 bit real number and
sl@0: ** 64 bit integer. The value returned is the number of bytes written
sl@0: ** to the argument buffer (always 2, 4 and 8 respectively).
sl@0: */
sl@0: static int writeInt16(u8 *p, int i){
sl@0:   p[0] = (i>> 8)&0xFF;
sl@0:   p[1] = (i>> 0)&0xFF;
sl@0:   return 2;
sl@0: }
sl@0: static int writeCoord(u8 *p, RtreeCoord *pCoord){
sl@0:   u32 i;
sl@0:   assert( sizeof(RtreeCoord)==4 );
sl@0:   assert( sizeof(u32)==4 );
sl@0:   i = *(u32 *)pCoord;
sl@0:   p[0] = (i>>24)&0xFF;
sl@0:   p[1] = (i>>16)&0xFF;
sl@0:   p[2] = (i>> 8)&0xFF;
sl@0:   p[3] = (i>> 0)&0xFF;
sl@0:   return 4;
sl@0: }
sl@0: static int writeInt64(u8 *p, i64 i){
sl@0:   p[0] = (i>>56)&0xFF;
sl@0:   p[1] = (i>>48)&0xFF;
sl@0:   p[2] = (i>>40)&0xFF;
sl@0:   p[3] = (i>>32)&0xFF;
sl@0:   p[4] = (i>>24)&0xFF;
sl@0:   p[5] = (i>>16)&0xFF;
sl@0:   p[6] = (i>> 8)&0xFF;
sl@0:   p[7] = (i>> 0)&0xFF;
sl@0:   return 8;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Increment the reference count of node p.
sl@0: */
sl@0: static void nodeReference(RtreeNode *p){
sl@0:   if( p ){
sl@0:     p->nRef++;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Clear the content of node p (set all bytes to 0x00).
sl@0: */
sl@0: static void nodeZero(Rtree *pRtree, RtreeNode *p){
sl@0:   if( p ){
sl@0:     memset(&p->zData[2], 0, pRtree->iNodeSize-2);
sl@0:     p->isDirty = 1;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Given a node number iNode, return the corresponding key to use
sl@0: ** in the Rtree.aHash table.
sl@0: */
sl@0: static int nodeHash(i64 iNode){
sl@0:   return (
sl@0:     (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 
sl@0:     (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
sl@0:   ) % HASHSIZE;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Search the node hash table for node iNode. If found, return a pointer
sl@0: ** to it. Otherwise, return 0.
sl@0: */
sl@0: static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
sl@0:   RtreeNode *p;
sl@0:   assert( iNode!=0 );
sl@0:   for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Add node pNode to the node hash table.
sl@0: */
sl@0: static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
sl@0:   if( pNode ){
sl@0:     int iHash;
sl@0:     assert( pNode->pNext==0 );
sl@0:     iHash = nodeHash(pNode->iNode);
sl@0:     pNode->pNext = pRtree->aHash[iHash];
sl@0:     pRtree->aHash[iHash] = pNode;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Remove node pNode from the node hash table.
sl@0: */
sl@0: static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
sl@0:   RtreeNode **pp;
sl@0:   if( pNode->iNode!=0 ){
sl@0:     pp = &pRtree->aHash[nodeHash(pNode->iNode)];
sl@0:     for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
sl@0:     *pp = pNode->pNext;
sl@0:     pNode->pNext = 0;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
sl@0: ** indicating that node has not yet been assigned a node number. It is
sl@0: ** assigned a node number when nodeWrite() is called to write the
sl@0: ** node contents out to the database.
sl@0: */
sl@0: static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){
sl@0:   RtreeNode *pNode;
sl@0:   pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
sl@0:   if( pNode ){
sl@0:     memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
sl@0:     pNode->zData = (u8 *)&pNode[1];
sl@0:     pNode->nRef = 1;
sl@0:     pNode->pParent = pParent;
sl@0:     pNode->isDirty = 1;
sl@0:     nodeReference(pParent);
sl@0:   }
sl@0:   return pNode;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Obtain a reference to an r-tree node.
sl@0: */
sl@0: static int
sl@0: nodeAcquire(
sl@0:   Rtree *pRtree,             /* R-tree structure */
sl@0:   i64 iNode,                 /* Node number to load */
sl@0:   RtreeNode *pParent,        /* Either the parent node or NULL */
sl@0:   RtreeNode **ppNode         /* OUT: Acquired node */
sl@0: ){
sl@0:   int rc;
sl@0:   RtreeNode *pNode;
sl@0: 
sl@0:   /* Check if the requested node is already in the hash table. If so,
sl@0:   ** increase its reference count and return it.
sl@0:   */
sl@0:   if( (pNode = nodeHashLookup(pRtree, iNode)) ){
sl@0:     assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
sl@0:     if( pParent ){
sl@0:       pNode->pParent = pParent;
sl@0:     }
sl@0:     pNode->nRef++;
sl@0:     *ppNode = pNode;
sl@0:     return SQLITE_OK;
sl@0:   }
sl@0: 
sl@0:   pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
sl@0:   if( !pNode ){
sl@0:     *ppNode = 0;
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0:   pNode->pParent = pParent;
sl@0:   pNode->zData = (u8 *)&pNode[1];
sl@0:   pNode->nRef = 1;
sl@0:   pNode->iNode = iNode;
sl@0:   pNode->isDirty = 0;
sl@0:   pNode->pNext = 0;
sl@0: 
sl@0:   sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
sl@0:   rc = sqlite3_step(pRtree->pReadNode);
sl@0:   if( rc==SQLITE_ROW ){
sl@0:     const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
sl@0:     memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
sl@0:     nodeReference(pParent);
sl@0:   }else{
sl@0:     sqlite3_free(pNode);
sl@0:     pNode = 0;
sl@0:   }
sl@0: 
sl@0:   *ppNode = pNode;
sl@0:   rc = sqlite3_reset(pRtree->pReadNode);
sl@0: 
sl@0:   if( rc==SQLITE_OK && iNode==1 ){
sl@0:     pRtree->iDepth = readInt16(pNode->zData);
sl@0:   }
sl@0: 
sl@0:   assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );
sl@0:   nodeHashInsert(pRtree, pNode);
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Overwrite cell iCell of node pNode with the contents of pCell.
sl@0: */
sl@0: static void nodeOverwriteCell(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode,  
sl@0:   RtreeCell *pCell, 
sl@0:   int iCell
sl@0: ){
sl@0:   int ii;
sl@0:   u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
sl@0:   p += writeInt64(p, pCell->iRowid);
sl@0:   for(ii=0; ii<(pRtree->nDim*2); ii++){
sl@0:     p += writeCoord(p, &pCell->aCoord[ii]);
sl@0:   }
sl@0:   pNode->isDirty = 1;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Remove cell the cell with index iCell from node pNode.
sl@0: */
sl@0: static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
sl@0:   u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
sl@0:   u8 *pSrc = &pDst[pRtree->nBytesPerCell];
sl@0:   int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
sl@0:   memmove(pDst, pSrc, nByte);
sl@0:   writeInt16(&pNode->zData[2], NCELL(pNode)-1);
sl@0:   pNode->isDirty = 1;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Insert the contents of cell pCell into node pNode. If the insert
sl@0: ** is successful, return SQLITE_OK.
sl@0: **
sl@0: ** If there is not enough free space in pNode, return SQLITE_FULL.
sl@0: */
sl@0: static int
sl@0: nodeInsertCell(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode, 
sl@0:   RtreeCell *pCell 
sl@0: ){
sl@0:   int nCell;                    /* Current number of cells in pNode */
sl@0:   int nMaxCell;                 /* Maximum number of cells for pNode */
sl@0: 
sl@0:   nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
sl@0:   nCell = NCELL(pNode);
sl@0: 
sl@0:   assert(nCell<=nMaxCell);
sl@0: 
sl@0:   if( nCell<nMaxCell ){
sl@0:     nodeOverwriteCell(pRtree, pNode, pCell, nCell);
sl@0:     writeInt16(&pNode->zData[2], nCell+1);
sl@0:     pNode->isDirty = 1;
sl@0:   }
sl@0: 
sl@0:   return (nCell==nMaxCell);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** If the node is dirty, write it out to the database.
sl@0: */
sl@0: static int
sl@0: nodeWrite(Rtree *pRtree, RtreeNode *pNode){
sl@0:   int rc = SQLITE_OK;
sl@0:   if( pNode->isDirty ){
sl@0:     sqlite3_stmt *p = pRtree->pWriteNode;
sl@0:     if( pNode->iNode ){
sl@0:       sqlite3_bind_int64(p, 1, pNode->iNode);
sl@0:     }else{
sl@0:       sqlite3_bind_null(p, 1);
sl@0:     }
sl@0:     sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
sl@0:     sqlite3_step(p);
sl@0:     pNode->isDirty = 0;
sl@0:     rc = sqlite3_reset(p);
sl@0:     if( pNode->iNode==0 && rc==SQLITE_OK ){
sl@0:       pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
sl@0:       nodeHashInsert(pRtree, pNode);
sl@0:     }
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Release a reference to a node. If the node is dirty and the reference
sl@0: ** count drops to zero, the node data is written to the database.
sl@0: */
sl@0: static int
sl@0: nodeRelease(Rtree *pRtree, RtreeNode *pNode){
sl@0:   int rc = SQLITE_OK;
sl@0:   if( pNode ){
sl@0:     assert( pNode->nRef>0 );
sl@0:     pNode->nRef--;
sl@0:     if( pNode->nRef==0 ){
sl@0:       if( pNode->iNode==1 ){
sl@0:         pRtree->iDepth = -1;
sl@0:       }
sl@0:       if( pNode->pParent ){
sl@0:         rc = nodeRelease(pRtree, pNode->pParent);
sl@0:       }
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = nodeWrite(pRtree, pNode);
sl@0:       }
sl@0:       nodeHashDelete(pRtree, pNode);
sl@0:       sqlite3_free(pNode);
sl@0:     }
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the 64-bit integer value associated with cell iCell of
sl@0: ** node pNode. If pNode is a leaf node, this is a rowid. If it is
sl@0: ** an internal node, then the 64-bit integer is a child page number.
sl@0: */
sl@0: static i64 nodeGetRowid(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode, 
sl@0:   int iCell
sl@0: ){
sl@0:   assert( iCell<NCELL(pNode) );
sl@0:   return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return coordinate iCoord from cell iCell in node pNode.
sl@0: */
sl@0: static void nodeGetCoord(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode, 
sl@0:   int iCell,
sl@0:   int iCoord,
sl@0:   RtreeCoord *pCoord           /* Space to write result to */
sl@0: ){
sl@0:   readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Deserialize cell iCell of node pNode. Populate the structure pointed
sl@0: ** to by pCell with the results.
sl@0: */
sl@0: static void nodeGetCell(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode, 
sl@0:   int iCell,
sl@0:   RtreeCell *pCell
sl@0: ){
sl@0:   int ii;
sl@0:   pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
sl@0:   for(ii=0; ii<pRtree->nDim*2; ii++){
sl@0:     nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
sl@0:   }
sl@0: }
sl@0: 
sl@0: 
sl@0: /* Forward declaration for the function that does the work of
sl@0: ** the virtual table module xCreate() and xConnect() methods.
sl@0: */
sl@0: static int rtreeInit(
sl@0:   sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int
sl@0: );
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xCreate method.
sl@0: */
sl@0: static int rtreeCreate(
sl@0:   sqlite3 *db,
sl@0:   void *pAux,
sl@0:   int argc, const char *const*argv,
sl@0:   sqlite3_vtab **ppVtab,
sl@0:   char **pzErr
sl@0: ){
sl@0:   return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux);
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xConnect method.
sl@0: */
sl@0: static int rtreeConnect(
sl@0:   sqlite3 *db,
sl@0:   void *pAux,
sl@0:   int argc, const char *const*argv,
sl@0:   sqlite3_vtab **ppVtab,
sl@0:   char **pzErr
sl@0: ){
sl@0:   return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Increment the r-tree reference count.
sl@0: */
sl@0: static void rtreeReference(Rtree *pRtree){
sl@0:   pRtree->nBusy++;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Decrement the r-tree reference count. When the reference count reaches
sl@0: ** zero the structure is deleted.
sl@0: */
sl@0: static void rtreeRelease(Rtree *pRtree){
sl@0:   pRtree->nBusy--;
sl@0:   if( pRtree->nBusy==0 ){
sl@0:     sqlite3_finalize(pRtree->pReadNode);
sl@0:     sqlite3_finalize(pRtree->pWriteNode);
sl@0:     sqlite3_finalize(pRtree->pDeleteNode);
sl@0:     sqlite3_finalize(pRtree->pReadRowid);
sl@0:     sqlite3_finalize(pRtree->pWriteRowid);
sl@0:     sqlite3_finalize(pRtree->pDeleteRowid);
sl@0:     sqlite3_finalize(pRtree->pReadParent);
sl@0:     sqlite3_finalize(pRtree->pWriteParent);
sl@0:     sqlite3_finalize(pRtree->pDeleteParent);
sl@0:     sqlite3_free(pRtree);
sl@0:   }
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xDisconnect method.
sl@0: */
sl@0: static int rtreeDisconnect(sqlite3_vtab *pVtab){
sl@0:   rtreeRelease((Rtree *)pVtab);
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xDestroy method.
sl@0: */
sl@0: static int rtreeDestroy(sqlite3_vtab *pVtab){
sl@0:   Rtree *pRtree = (Rtree *)pVtab;
sl@0:   int rc;
sl@0:   char *zCreate = sqlite3_mprintf(
sl@0:     "DROP TABLE '%q'.'%q_node';"
sl@0:     "DROP TABLE '%q'.'%q_rowid';"
sl@0:     "DROP TABLE '%q'.'%q_parent';",
sl@0:     pRtree->zDb, pRtree->zName, 
sl@0:     pRtree->zDb, pRtree->zName,
sl@0:     pRtree->zDb, pRtree->zName
sl@0:   );
sl@0:   if( !zCreate ){
sl@0:     rc = SQLITE_NOMEM;
sl@0:   }else{
sl@0:     rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
sl@0:     sqlite3_free(zCreate);
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     rtreeRelease(pRtree);
sl@0:   }
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xOpen method.
sl@0: */
sl@0: static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
sl@0:   int rc = SQLITE_NOMEM;
sl@0:   RtreeCursor *pCsr;
sl@0: 
sl@0:   pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));
sl@0:   if( pCsr ){
sl@0:     memset(pCsr, 0, sizeof(RtreeCursor));
sl@0:     pCsr->base.pVtab = pVTab;
sl@0:     rc = SQLITE_OK;
sl@0:   }
sl@0:   *ppCursor = (sqlite3_vtab_cursor *)pCsr;
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xClose method.
sl@0: */
sl@0: static int rtreeClose(sqlite3_vtab_cursor *cur){
sl@0:   Rtree *pRtree = (Rtree *)(cur->pVtab);
sl@0:   int rc;
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)cur;
sl@0:   sqlite3_free(pCsr->aConstraint);
sl@0:   rc = nodeRelease(pRtree, pCsr->pNode);
sl@0:   sqlite3_free(pCsr);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Rtree virtual table module xEof method.
sl@0: **
sl@0: ** Return non-zero if the cursor does not currently point to a valid 
sl@0: ** record (i.e if the scan has finished), or zero otherwise.
sl@0: */
sl@0: static int rtreeEof(sqlite3_vtab_cursor *cur){
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)cur;
sl@0:   return (pCsr->pNode==0);
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Cursor pCursor currently points to a cell in a non-leaf page.
sl@0: ** Return true if the sub-tree headed by the cell is filtered
sl@0: ** (excluded) by the constraints in the pCursor->aConstraint[] 
sl@0: ** array, or false otherwise.
sl@0: */
sl@0: static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){
sl@0:   RtreeCell cell;
sl@0:   int ii;
sl@0:   int bRes = 0;
sl@0: 
sl@0:   nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
sl@0:   for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
sl@0:     RtreeConstraint *p = &pCursor->aConstraint[ii];
sl@0:     double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
sl@0:     double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
sl@0: 
sl@0:     assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
sl@0:         || p->op==RTREE_GT || p->op==RTREE_EQ
sl@0:     );
sl@0: 
sl@0:     switch( p->op ){
sl@0:       case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break;
sl@0:       case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break;
sl@0:       case RTREE_EQ: 
sl@0:         bRes = (p->rValue>cell_max || p->rValue<cell_min);
sl@0:         break;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   return bRes;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Return true if the cell that cursor pCursor currently points to
sl@0: ** would be filtered (excluded) by the constraints in the 
sl@0: ** pCursor->aConstraint[] array, or false otherwise.
sl@0: **
sl@0: ** This function assumes that the cell is part of a leaf node.
sl@0: */
sl@0: static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){
sl@0:   RtreeCell cell;
sl@0:   int ii;
sl@0: 
sl@0:   nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
sl@0:   for(ii=0; ii<pCursor->nConstraint; ii++){
sl@0:     RtreeConstraint *p = &pCursor->aConstraint[ii];
sl@0:     double coord = DCOORD(cell.aCoord[p->iCoord]);
sl@0:     int res;
sl@0:     assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
sl@0:         || p->op==RTREE_GT || p->op==RTREE_EQ
sl@0:     );
sl@0:     switch( p->op ){
sl@0:       case RTREE_LE: res = (coord<=p->rValue); break;
sl@0:       case RTREE_LT: res = (coord<p->rValue);  break;
sl@0:       case RTREE_GE: res = (coord>=p->rValue); break;
sl@0:       case RTREE_GT: res = (coord>p->rValue);  break;
sl@0:       case RTREE_EQ: res = (coord==p->rValue); break;
sl@0:     }
sl@0: 
sl@0:     if( !res ) return 1;
sl@0:   }
sl@0: 
sl@0:   return 0;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Cursor pCursor currently points at a node that heads a sub-tree of
sl@0: ** height iHeight (if iHeight==0, then the node is a leaf). Descend
sl@0: ** to point to the left-most cell of the sub-tree that matches the 
sl@0: ** configured constraints.
sl@0: */
sl@0: static int descendToCell(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeCursor *pCursor, 
sl@0:   int iHeight,
sl@0:   int *pEof                 /* OUT: Set to true if cannot descend */
sl@0: ){
sl@0:   int isEof;
sl@0:   int rc;
sl@0:   int ii;
sl@0:   RtreeNode *pChild;
sl@0:   sqlite3_int64 iRowid;
sl@0: 
sl@0:   RtreeNode *pSavedNode = pCursor->pNode;
sl@0:   int iSavedCell = pCursor->iCell;
sl@0: 
sl@0:   assert( iHeight>=0 );
sl@0: 
sl@0:   if( iHeight==0 ){
sl@0:     isEof = testRtreeEntry(pRtree, pCursor);
sl@0:   }else{
sl@0:     isEof = testRtreeCell(pRtree, pCursor);
sl@0:   }
sl@0:   if( isEof || iHeight==0 ){
sl@0:     *pEof = isEof;
sl@0:     return SQLITE_OK;
sl@0:   }
sl@0: 
sl@0:   iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
sl@0:   rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
sl@0:   if( rc!=SQLITE_OK ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   nodeRelease(pRtree, pCursor->pNode);
sl@0:   pCursor->pNode = pChild;
sl@0:   isEof = 1;
sl@0:   for(ii=0; isEof && ii<NCELL(pChild); ii++){
sl@0:     pCursor->iCell = ii;
sl@0:     rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
sl@0:     if( rc!=SQLITE_OK ){
sl@0:       return rc;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   if( isEof ){
sl@0:     assert( pCursor->pNode==pChild );
sl@0:     nodeReference(pSavedNode);
sl@0:     nodeRelease(pRtree, pChild);
sl@0:     pCursor->pNode = pSavedNode;
sl@0:     pCursor->iCell = iSavedCell;
sl@0:   }
sl@0: 
sl@0:   *pEof = isEof;
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** One of the cells in node pNode is guaranteed to have a 64-bit 
sl@0: ** integer value equal to iRowid. Return the index of this cell.
sl@0: */
sl@0: static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){
sl@0:   int ii;
sl@0:   for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
sl@0:     assert( ii<(NCELL(pNode)-1) );
sl@0:   }
sl@0:   return ii;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the index of the cell containing a pointer to node pNode
sl@0: ** in its parent. If pNode is the root node, return -1.
sl@0: */
sl@0: static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){
sl@0:   RtreeNode *pParent = pNode->pParent;
sl@0:   if( pParent ){
sl@0:     return nodeRowidIndex(pRtree, pParent, pNode->iNode);
sl@0:   }
sl@0:   return -1;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xNext method.
sl@0: */
sl@0: static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
sl@0:   Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   if( pCsr->iStrategy==1 ){
sl@0:     /* This "scan" is a direct lookup by rowid. There is no next entry. */
sl@0:     nodeRelease(pRtree, pCsr->pNode);
sl@0:     pCsr->pNode = 0;
sl@0:   }
sl@0: 
sl@0:   else if( pCsr->pNode ){
sl@0:     /* Move to the next entry that matches the configured constraints. */
sl@0:     int iHeight = 0;
sl@0:     while( pCsr->pNode ){
sl@0:       RtreeNode *pNode = pCsr->pNode;
sl@0:       int nCell = NCELL(pNode);
sl@0:       for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
sl@0:         int isEof;
sl@0:         rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
sl@0:         if( rc!=SQLITE_OK || !isEof ){
sl@0:           return rc;
sl@0:         }
sl@0:       }
sl@0:       pCsr->pNode = pNode->pParent;
sl@0:       pCsr->iCell = nodeParentIndex(pRtree, pNode);
sl@0:       nodeReference(pCsr->pNode);
sl@0:       nodeRelease(pRtree, pNode);
sl@0:       iHeight++;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xRowid method.
sl@0: */
sl@0: static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
sl@0:   Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
sl@0: 
sl@0:   assert(pCsr->pNode);
sl@0:   *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
sl@0: 
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xColumn method.
sl@0: */
sl@0: static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
sl@0:   Rtree *pRtree = (Rtree *)cur->pVtab;
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)cur;
sl@0: 
sl@0:   if( i==0 ){
sl@0:     i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
sl@0:     sqlite3_result_int64(ctx, iRowid);
sl@0:   }else{
sl@0:     RtreeCoord c;
sl@0:     nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
sl@0:     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0:       sqlite3_result_double(ctx, c.f);
sl@0:     }else{
sl@0:       assert( pRtree->eCoordType==RTREE_COORD_INT32 );
sl@0:       sqlite3_result_int(ctx, c.i);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Use nodeAcquire() to obtain the leaf node containing the record with 
sl@0: ** rowid iRowid. If successful, set *ppLeaf to point to the node and
sl@0: ** return SQLITE_OK. If there is no such record in the table, set
sl@0: ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
sl@0: ** to zero and return an SQLite error code.
sl@0: */
sl@0: static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
sl@0:   int rc;
sl@0:   *ppLeaf = 0;
sl@0:   sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
sl@0:   if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
sl@0:     i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
sl@0:     rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
sl@0:     sqlite3_reset(pRtree->pReadRowid);
sl@0:   }else{
sl@0:     rc = sqlite3_reset(pRtree->pReadRowid);
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: 
sl@0: /* 
sl@0: ** Rtree virtual table module xFilter method.
sl@0: */
sl@0: static int rtreeFilter(
sl@0:   sqlite3_vtab_cursor *pVtabCursor, 
sl@0:   int idxNum, const char *idxStr,
sl@0:   int argc, sqlite3_value **argv
sl@0: ){
sl@0:   Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
sl@0:   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
sl@0: 
sl@0:   RtreeNode *pRoot = 0;
sl@0:   int ii;
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   rtreeReference(pRtree);
sl@0: 
sl@0:   sqlite3_free(pCsr->aConstraint);
sl@0:   pCsr->aConstraint = 0;
sl@0:   pCsr->iStrategy = idxNum;
sl@0: 
sl@0:   if( idxNum==1 ){
sl@0:     /* Special case - lookup by rowid. */
sl@0:     RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
sl@0:     i64 iRowid = sqlite3_value_int64(argv[0]);
sl@0:     rc = findLeafNode(pRtree, iRowid, &pLeaf);
sl@0:     pCsr->pNode = pLeaf; 
sl@0:     if( pLeaf && rc==SQLITE_OK ){
sl@0:       pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
sl@0:     }
sl@0:   }else{
sl@0:     /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
sl@0:     ** with the configured constraints. 
sl@0:     */
sl@0:     if( argc>0 ){
sl@0:       pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
sl@0:       pCsr->nConstraint = argc;
sl@0:       if( !pCsr->aConstraint ){
sl@0:         rc = SQLITE_NOMEM;
sl@0:       }else{
sl@0:         assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
sl@0:         for(ii=0; ii<argc; ii++){
sl@0:           RtreeConstraint *p = &pCsr->aConstraint[ii];
sl@0:           p->op = idxStr[ii*2];
sl@0:           p->iCoord = idxStr[ii*2+1]-'a';
sl@0:           p->rValue = sqlite3_value_double(argv[ii]);
sl@0:         }
sl@0:       }
sl@0:     }
sl@0:   
sl@0:     if( rc==SQLITE_OK ){
sl@0:       pCsr->pNode = 0;
sl@0:       rc = nodeAcquire(pRtree, 1, 0, &pRoot);
sl@0:     }
sl@0:     if( rc==SQLITE_OK ){
sl@0:       int isEof = 1;
sl@0:       int nCell = NCELL(pRoot);
sl@0:       pCsr->pNode = pRoot;
sl@0:       for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
sl@0:         assert( pCsr->pNode==pRoot );
sl@0:         rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
sl@0:         if( !isEof ){
sl@0:           break;
sl@0:         }
sl@0:       }
sl@0:       if( rc==SQLITE_OK && isEof ){
sl@0:         assert( pCsr->pNode==pRoot );
sl@0:         nodeRelease(pRtree, pRoot);
sl@0:         pCsr->pNode = 0;
sl@0:       }
sl@0:       assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   rtreeRelease(pRtree);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Rtree virtual table module xBestIndex method. There are three
sl@0: ** table scan strategies to choose from (in order from most to 
sl@0: ** least desirable):
sl@0: **
sl@0: **   idxNum     idxStr        Strategy
sl@0: **   ------------------------------------------------
sl@0: **     1        Unused        Direct lookup by rowid.
sl@0: **     2        See below     R-tree query.
sl@0: **     3        Unused        Full table scan.
sl@0: **   ------------------------------------------------
sl@0: **
sl@0: ** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
sl@0: ** 2 is used, idxStr is formatted to contain 2 bytes for each 
sl@0: ** constraint used. The first two bytes of idxStr correspond to 
sl@0: ** the constraint in sqlite3_index_info.aConstraintUsage[] with
sl@0: ** (argvIndex==1) etc.
sl@0: **
sl@0: ** The first of each pair of bytes in idxStr identifies the constraint
sl@0: ** operator as follows:
sl@0: **
sl@0: **   Operator    Byte Value
sl@0: **   ----------------------
sl@0: **      =        0x41 ('A')
sl@0: **     <=        0x42 ('B')
sl@0: **      <        0x43 ('C')
sl@0: **     >=        0x44 ('D')
sl@0: **      >        0x45 ('E')
sl@0: **   ----------------------
sl@0: **
sl@0: ** The second of each pair of bytes identifies the coordinate column
sl@0: ** to which the constraint applies. The leftmost coordinate column
sl@0: ** is 'a', the second from the left 'b' etc.
sl@0: */
sl@0: static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
sl@0:   int rc = SQLITE_OK;
sl@0:   int ii, cCol;
sl@0: 
sl@0:   int iIdx = 0;
sl@0:   char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
sl@0:   memset(zIdxStr, 0, sizeof(zIdxStr));
sl@0: 
sl@0:   assert( pIdxInfo->idxStr==0 );
sl@0:   for(ii=0; ii<pIdxInfo->nConstraint; ii++){
sl@0:     struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
sl@0: 
sl@0:     if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
sl@0:       /* We have an equality constraint on the rowid. Use strategy 1. */
sl@0:       int jj;
sl@0:       for(jj=0; jj<ii; jj++){
sl@0:         pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
sl@0:         pIdxInfo->aConstraintUsage[jj].omit = 0;
sl@0:       }
sl@0:       pIdxInfo->idxNum = 1;
sl@0:       pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
sl@0:       pIdxInfo->aConstraintUsage[jj].omit = 1;
sl@0: 
sl@0:       /* This strategy involves a two rowid lookups on an B-Tree structures
sl@0:       ** and then a linear search of an R-Tree node. This should be 
sl@0:       ** considered almost as quick as a direct rowid lookup (for which 
sl@0:       ** sqlite uses an internal cost of 0.0).
sl@0:       */ 
sl@0:       pIdxInfo->estimatedCost = 10.0;
sl@0:       return SQLITE_OK;
sl@0:     }
sl@0: 
sl@0:     if( p->usable && p->iColumn>0 ){
sl@0:       u8 op = 0;
sl@0:       switch( p->op ){
sl@0:         case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
sl@0:         case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
sl@0:         case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
sl@0:         case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
sl@0:         case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
sl@0:       }
sl@0:       if( op ){
sl@0:         /* Make sure this particular constraint has not been used before.
sl@0:         ** If it has been used before, ignore it.
sl@0:         **
sl@0:         ** A <= or < can be used if there is a prior >= or >.
sl@0:         ** A >= or > can be used if there is a prior < or <=.
sl@0:         ** A <= or < is disqualified if there is a prior <=, <, or ==.
sl@0:         ** A >= or > is disqualified if there is a prior >=, >, or ==.
sl@0:         ** A == is disqualifed if there is any prior constraint.
sl@0:         */
sl@0:         int j, opmsk;
sl@0:         static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
sl@0:         assert( compatible[RTREE_EQ & 7]==0 );
sl@0:         assert( compatible[RTREE_LT & 7]==1 );
sl@0:         assert( compatible[RTREE_LE & 7]==1 );
sl@0:         assert( compatible[RTREE_GT & 7]==2 );
sl@0:         assert( compatible[RTREE_GE & 7]==2 );
sl@0:         cCol = p->iColumn - 1 + 'a';
sl@0:         opmsk = compatible[op & 7];
sl@0:         for(j=0; j<iIdx; j+=2){
sl@0:           if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
sl@0:             op = 0;
sl@0:             break;
sl@0:           }
sl@0:         }
sl@0:       }
sl@0:       if( op ){
sl@0:         assert( iIdx<sizeof(zIdxStr)-1 );
sl@0:         zIdxStr[iIdx++] = op;
sl@0:         zIdxStr[iIdx++] = cCol;
sl@0:         pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
sl@0:         pIdxInfo->aConstraintUsage[ii].omit = 1;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   pIdxInfo->idxNum = 2;
sl@0:   pIdxInfo->needToFreeIdxStr = 1;
sl@0:   if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0:   assert( iIdx>=0 );
sl@0:   pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the N-dimensional volumn of the cell stored in *p.
sl@0: */
sl@0: static float cellArea(Rtree *pRtree, RtreeCell *p){
sl@0:   float area = 1.0;
sl@0:   int ii;
sl@0:   for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:     area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
sl@0:   }
sl@0:   return area;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the margin length of cell p. The margin length is the sum
sl@0: ** of the objects size in each dimension.
sl@0: */
sl@0: static float cellMargin(Rtree *pRtree, RtreeCell *p){
sl@0:   float margin = 0.0;
sl@0:   int ii;
sl@0:   for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:     margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
sl@0:   }
sl@0:   return margin;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Store the union of cells p1 and p2 in p1.
sl@0: */
sl@0: static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
sl@0:   int ii;
sl@0:   if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0:     for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:       p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
sl@0:       p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
sl@0:     }
sl@0:   }else{
sl@0:     for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:       p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
sl@0:       p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return true if the area covered by p2 is a subset of the area covered
sl@0: ** by p1. False otherwise.
sl@0: */
sl@0: static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
sl@0:   int ii;
sl@0:   int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
sl@0:   for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:     RtreeCoord *a1 = &p1->aCoord[ii];
sl@0:     RtreeCoord *a2 = &p2->aCoord[ii];
sl@0:     if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) 
sl@0:      || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) 
sl@0:     ){
sl@0:       return 0;
sl@0:     }
sl@0:   }
sl@0:   return 1;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the amount cell p would grow by if it were unioned with pCell.
sl@0: */
sl@0: static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
sl@0:   float area;
sl@0:   RtreeCell cell;
sl@0:   memcpy(&cell, p, sizeof(RtreeCell));
sl@0:   area = cellArea(pRtree, &cell);
sl@0:   cellUnion(pRtree, &cell, pCell);
sl@0:   return (cellArea(pRtree, &cell)-area);
sl@0: }
sl@0: 
sl@0: #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
sl@0: static float cellOverlap(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeCell *p, 
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   int iExclude
sl@0: ){
sl@0:   int ii;
sl@0:   float overlap = 0.0;
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     if( ii!=iExclude ){
sl@0:       int jj;
sl@0:       float o = 1.0;
sl@0:       for(jj=0; jj<(pRtree->nDim*2); jj+=2){
sl@0:         double x1;
sl@0:         double x2;
sl@0: 
sl@0:         x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
sl@0:         x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
sl@0: 
sl@0:         if( x2<x1 ){
sl@0:           o = 0.0;
sl@0:           break;
sl@0:         }else{
sl@0:           o = o * (x2-x1);
sl@0:         }
sl@0:       }
sl@0:       overlap += o;
sl@0:     }
sl@0:   }
sl@0:   return overlap;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: #if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0: static float cellOverlapEnlargement(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeCell *p, 
sl@0:   RtreeCell *pInsert, 
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   int iExclude
sl@0: ){
sl@0:   float before;
sl@0:   float after;
sl@0:   before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
sl@0:   cellUnion(pRtree, p, pInsert);
sl@0:   after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
sl@0:   return after-before;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** This function implements the ChooseLeaf algorithm from Gutman[84].
sl@0: ** ChooseSubTree in r*tree terminology.
sl@0: */
sl@0: static int ChooseLeaf(
sl@0:   Rtree *pRtree,               /* Rtree table */
sl@0:   RtreeCell *pCell,            /* Cell to insert into rtree */
sl@0:   int iHeight,                 /* Height of sub-tree rooted at pCell */
sl@0:   RtreeNode **ppLeaf           /* OUT: Selected leaf page */
sl@0: ){
sl@0:   int rc;
sl@0:   int ii;
sl@0:   RtreeNode *pNode;
sl@0:   rc = nodeAcquire(pRtree, 1, 0, &pNode);
sl@0: 
sl@0:   for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
sl@0:     int iCell;
sl@0:     sqlite3_int64 iBest;
sl@0: 
sl@0:     float fMinGrowth;
sl@0:     float fMinArea;
sl@0:     float fMinOverlap;
sl@0: 
sl@0:     int nCell = NCELL(pNode);
sl@0:     RtreeCell cell;
sl@0:     RtreeNode *pChild;
sl@0: 
sl@0:     RtreeCell *aCell = 0;
sl@0: 
sl@0: #if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0:     if( ii==(pRtree->iDepth-1) ){
sl@0:       int jj;
sl@0:       aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
sl@0:       if( !aCell ){
sl@0:         rc = SQLITE_NOMEM;
sl@0:         nodeRelease(pRtree, pNode);
sl@0:         pNode = 0;
sl@0:         continue;
sl@0:       }
sl@0:       for(jj=0; jj<nCell; jj++){
sl@0:         nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
sl@0:       }
sl@0:     }
sl@0: #endif
sl@0: 
sl@0:     /* Select the child node which will be enlarged the least if pCell
sl@0:     ** is inserted into it. Resolve ties by choosing the entry with
sl@0:     ** the smallest area.
sl@0:     */
sl@0:     for(iCell=0; iCell<nCell; iCell++){
sl@0:       float growth;
sl@0:       float area;
sl@0:       float overlap = 0.0;
sl@0:       nodeGetCell(pRtree, pNode, iCell, &cell);
sl@0:       growth = cellGrowth(pRtree, &cell, pCell);
sl@0:       area = cellArea(pRtree, &cell);
sl@0: #if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0:       if( ii==(pRtree->iDepth-1) ){
sl@0:         overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
sl@0:       }
sl@0: #endif
sl@0:       if( (iCell==0) 
sl@0:        || (overlap<fMinOverlap) 
sl@0:        || (overlap==fMinOverlap && growth<fMinGrowth)
sl@0:        || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
sl@0:       ){
sl@0:         fMinOverlap = overlap;
sl@0:         fMinGrowth = growth;
sl@0:         fMinArea = area;
sl@0:         iBest = cell.iRowid;
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     sqlite3_free(aCell);
sl@0:     rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
sl@0:     nodeRelease(pRtree, pNode);
sl@0:     pNode = pChild;
sl@0:   }
sl@0: 
sl@0:   *ppLeaf = pNode;
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** A cell with the same content as pCell has just been inserted into
sl@0: ** the node pNode. This function updates the bounding box cells in
sl@0: ** all ancestor elements.
sl@0: */
sl@0: static void AdjustTree(
sl@0:   Rtree *pRtree,                    /* Rtree table */
sl@0:   RtreeNode *pNode,                 /* Adjust ancestry of this node. */
sl@0:   RtreeCell *pCell                  /* This cell was just inserted */
sl@0: ){
sl@0:   RtreeNode *p = pNode;
sl@0:   while( p->pParent ){
sl@0:     RtreeCell cell;
sl@0:     RtreeNode *pParent = p->pParent;
sl@0:     int iCell = nodeParentIndex(pRtree, p);
sl@0: 
sl@0:     nodeGetCell(pRtree, pParent, iCell, &cell);
sl@0:     if( !cellContains(pRtree, &cell, pCell) ){
sl@0:       cellUnion(pRtree, &cell, pCell);
sl@0:       nodeOverwriteCell(pRtree, pParent, &cell, iCell);
sl@0:     }
sl@0:  
sl@0:     p = pParent;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
sl@0: */
sl@0: static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
sl@0:   sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
sl@0:   sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
sl@0:   sqlite3_step(pRtree->pWriteRowid);
sl@0:   return sqlite3_reset(pRtree->pWriteRowid);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Write mapping (iNode->iPar) to the <rtree>_parent table.
sl@0: */
sl@0: static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
sl@0:   sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
sl@0:   sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
sl@0:   sqlite3_step(pRtree->pWriteParent);
sl@0:   return sqlite3_reset(pRtree->pWriteParent);
sl@0: }
sl@0: 
sl@0: static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
sl@0: 
sl@0: #if VARIANT_GUTTMAN_LINEAR_SPLIT
sl@0: /*
sl@0: ** Implementation of the linear variant of the PickNext() function from
sl@0: ** Guttman[84].
sl@0: */
sl@0: static RtreeCell *LinearPickNext(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   RtreeCell *pLeftBox, 
sl@0:   RtreeCell *pRightBox,
sl@0:   int *aiUsed
sl@0: ){
sl@0:   int ii;
sl@0:   for(ii=0; aiUsed[ii]; ii++);
sl@0:   aiUsed[ii] = 1;
sl@0:   return &aCell[ii];
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Implementation of the linear variant of the PickSeeds() function from
sl@0: ** Guttman[84].
sl@0: */
sl@0: static void LinearPickSeeds(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   int *piLeftSeed, 
sl@0:   int *piRightSeed
sl@0: ){
sl@0:   int i;
sl@0:   int iLeftSeed = 0;
sl@0:   int iRightSeed = 1;
sl@0:   float maxNormalInnerWidth = 0.0;
sl@0: 
sl@0:   /* Pick two "seed" cells from the array of cells. The algorithm used
sl@0:   ** here is the LinearPickSeeds algorithm from Gutman[1984]. The 
sl@0:   ** indices of the two seed cells in the array are stored in local
sl@0:   ** variables iLeftSeek and iRightSeed.
sl@0:   */
sl@0:   for(i=0; i<pRtree->nDim; i++){
sl@0:     float x1 = aCell[0].aCoord[i*2];
sl@0:     float x2 = aCell[0].aCoord[i*2+1];
sl@0:     float x3 = x1;
sl@0:     float x4 = x2;
sl@0:     int jj;
sl@0: 
sl@0:     int iCellLeft = 0;
sl@0:     int iCellRight = 0;
sl@0: 
sl@0:     for(jj=1; jj<nCell; jj++){
sl@0:       float left = aCell[jj].aCoord[i*2];
sl@0:       float right = aCell[jj].aCoord[i*2+1];
sl@0: 
sl@0:       if( left<x1 ) x1 = left;
sl@0:       if( right>x4 ) x4 = right;
sl@0:       if( left>x3 ){
sl@0:         x3 = left;
sl@0:         iCellRight = jj;
sl@0:       }
sl@0:       if( right<x2 ){
sl@0:         x2 = right;
sl@0:         iCellLeft = jj;
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     if( x4!=x1 ){
sl@0:       float normalwidth = (x3 - x2) / (x4 - x1);
sl@0:       if( normalwidth>maxNormalInnerWidth ){
sl@0:         iLeftSeed = iCellLeft;
sl@0:         iRightSeed = iCellRight;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   *piLeftSeed = iLeftSeed;
sl@0:   *piRightSeed = iRightSeed;
sl@0: }
sl@0: #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
sl@0: 
sl@0: #if VARIANT_GUTTMAN_QUADRATIC_SPLIT
sl@0: /*
sl@0: ** Implementation of the quadratic variant of the PickNext() function from
sl@0: ** Guttman[84].
sl@0: */
sl@0: static RtreeCell *QuadraticPickNext(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   RtreeCell *pLeftBox, 
sl@0:   RtreeCell *pRightBox,
sl@0:   int *aiUsed
sl@0: ){
sl@0:   #define FABS(a) ((a)<0.0?-1.0*(a):(a))
sl@0: 
sl@0:   int iSelect = -1;
sl@0:   float fDiff;
sl@0:   int ii;
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     if( aiUsed[ii]==0 ){
sl@0:       float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
sl@0:       float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
sl@0:       float diff = FABS(right-left);
sl@0:       if( iSelect<0 || diff>fDiff ){
sl@0:         fDiff = diff;
sl@0:         iSelect = ii;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0:   aiUsed[iSelect] = 1;
sl@0:   return &aCell[iSelect];
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Implementation of the quadratic variant of the PickSeeds() function from
sl@0: ** Guttman[84].
sl@0: */
sl@0: static void QuadraticPickSeeds(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell, 
sl@0:   int nCell, 
sl@0:   int *piLeftSeed, 
sl@0:   int *piRightSeed
sl@0: ){
sl@0:   int ii;
sl@0:   int jj;
sl@0: 
sl@0:   int iLeftSeed = 0;
sl@0:   int iRightSeed = 1;
sl@0:   float fWaste = 0.0;
sl@0: 
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     for(jj=ii+1; jj<nCell; jj++){
sl@0:       float right = cellArea(pRtree, &aCell[jj]);
sl@0:       float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
sl@0:       float waste = growth - right;
sl@0: 
sl@0:       if( waste>fWaste ){
sl@0:         iLeftSeed = ii;
sl@0:         iRightSeed = jj;
sl@0:         fWaste = waste;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   *piLeftSeed = iLeftSeed;
sl@0:   *piRightSeed = iRightSeed;
sl@0: }
sl@0: #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
sl@0: 
sl@0: /*
sl@0: ** Arguments aIdx, aDistance and aSpare all point to arrays of size
sl@0: ** nIdx. The aIdx array contains the set of integers from 0 to 
sl@0: ** (nIdx-1) in no particular order. This function sorts the values
sl@0: ** in aIdx according to the indexed values in aDistance. For
sl@0: ** example, assuming the inputs:
sl@0: **
sl@0: **   aIdx      = { 0,   1,   2,   3 }
sl@0: **   aDistance = { 5.0, 2.0, 7.0, 6.0 }
sl@0: **
sl@0: ** this function sets the aIdx array to contain:
sl@0: **
sl@0: **   aIdx      = { 0,   1,   2,   3 }
sl@0: **
sl@0: ** The aSpare array is used as temporary working space by the
sl@0: ** sorting algorithm.
sl@0: */
sl@0: static void SortByDistance(
sl@0:   int *aIdx, 
sl@0:   int nIdx, 
sl@0:   float *aDistance, 
sl@0:   int *aSpare
sl@0: ){
sl@0:   if( nIdx>1 ){
sl@0:     int iLeft = 0;
sl@0:     int iRight = 0;
sl@0: 
sl@0:     int nLeft = nIdx/2;
sl@0:     int nRight = nIdx-nLeft;
sl@0:     int *aLeft = aIdx;
sl@0:     int *aRight = &aIdx[nLeft];
sl@0: 
sl@0:     SortByDistance(aLeft, nLeft, aDistance, aSpare);
sl@0:     SortByDistance(aRight, nRight, aDistance, aSpare);
sl@0: 
sl@0:     memcpy(aSpare, aLeft, sizeof(int)*nLeft);
sl@0:     aLeft = aSpare;
sl@0: 
sl@0:     while( iLeft<nLeft || iRight<nRight ){
sl@0:       if( iLeft==nLeft ){
sl@0:         aIdx[iLeft+iRight] = aRight[iRight];
sl@0:         iRight++;
sl@0:       }else if( iRight==nRight ){
sl@0:         aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0:         iLeft++;
sl@0:       }else{
sl@0:         float fLeft = aDistance[aLeft[iLeft]];
sl@0:         float fRight = aDistance[aRight[iRight]];
sl@0:         if( fLeft<fRight ){
sl@0:           aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0:           iLeft++;
sl@0:         }else{
sl@0:           aIdx[iLeft+iRight] = aRight[iRight];
sl@0:           iRight++;
sl@0:         }
sl@0:       }
sl@0:     }
sl@0: 
sl@0: #if 0
sl@0:     /* Check that the sort worked */
sl@0:     {
sl@0:       int jj;
sl@0:       for(jj=1; jj<nIdx; jj++){
sl@0:         float left = aDistance[aIdx[jj-1]];
sl@0:         float right = aDistance[aIdx[jj]];
sl@0:         assert( left<=right );
sl@0:       }
sl@0:     }
sl@0: #endif
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Arguments aIdx, aCell and aSpare all point to arrays of size
sl@0: ** nIdx. The aIdx array contains the set of integers from 0 to 
sl@0: ** (nIdx-1) in no particular order. This function sorts the values
sl@0: ** in aIdx according to dimension iDim of the cells in aCell. The
sl@0: ** minimum value of dimension iDim is considered first, the
sl@0: ** maximum used to break ties.
sl@0: **
sl@0: ** The aSpare array is used as temporary working space by the
sl@0: ** sorting algorithm.
sl@0: */
sl@0: static void SortByDimension(
sl@0:   Rtree *pRtree,
sl@0:   int *aIdx, 
sl@0:   int nIdx, 
sl@0:   int iDim, 
sl@0:   RtreeCell *aCell, 
sl@0:   int *aSpare
sl@0: ){
sl@0:   if( nIdx>1 ){
sl@0: 
sl@0:     int iLeft = 0;
sl@0:     int iRight = 0;
sl@0: 
sl@0:     int nLeft = nIdx/2;
sl@0:     int nRight = nIdx-nLeft;
sl@0:     int *aLeft = aIdx;
sl@0:     int *aRight = &aIdx[nLeft];
sl@0: 
sl@0:     SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
sl@0:     SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
sl@0: 
sl@0:     memcpy(aSpare, aLeft, sizeof(int)*nLeft);
sl@0:     aLeft = aSpare;
sl@0:     while( iLeft<nLeft || iRight<nRight ){
sl@0:       double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
sl@0:       double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
sl@0:       double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
sl@0:       double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
sl@0:       if( (iLeft!=nLeft) && ((iRight==nRight)
sl@0:        || (xleft1<xright1)
sl@0:        || (xleft1==xright1 && xleft2<xright2)
sl@0:       )){
sl@0:         aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0:         iLeft++;
sl@0:       }else{
sl@0:         aIdx[iLeft+iRight] = aRight[iRight];
sl@0:         iRight++;
sl@0:       }
sl@0:     }
sl@0: 
sl@0: #if 0
sl@0:     /* Check that the sort worked */
sl@0:     {
sl@0:       int jj;
sl@0:       for(jj=1; jj<nIdx; jj++){
sl@0:         float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
sl@0:         float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
sl@0:         float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
sl@0:         float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
sl@0:         assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
sl@0:       }
sl@0:     }
sl@0: #endif
sl@0:   }
sl@0: }
sl@0: 
sl@0: #if VARIANT_RSTARTREE_SPLIT
sl@0: /*
sl@0: ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
sl@0: */
sl@0: static int splitNodeStartree(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell,
sl@0:   int nCell,
sl@0:   RtreeNode *pLeft,
sl@0:   RtreeNode *pRight,
sl@0:   RtreeCell *pBboxLeft,
sl@0:   RtreeCell *pBboxRight
sl@0: ){
sl@0:   int **aaSorted;
sl@0:   int *aSpare;
sl@0:   int ii;
sl@0: 
sl@0:   int iBestDim;
sl@0:   int iBestSplit;
sl@0:   float fBestMargin;
sl@0: 
sl@0:   int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
sl@0: 
sl@0:   aaSorted = (int **)sqlite3_malloc(nByte);
sl@0:   if( !aaSorted ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0: 
sl@0:   aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
sl@0:   memset(aaSorted, 0, nByte);
sl@0:   for(ii=0; ii<pRtree->nDim; ii++){
sl@0:     int jj;
sl@0:     aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
sl@0:     for(jj=0; jj<nCell; jj++){
sl@0:       aaSorted[ii][jj] = jj;
sl@0:     }
sl@0:     SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
sl@0:   }
sl@0: 
sl@0:   for(ii=0; ii<pRtree->nDim; ii++){
sl@0:     float margin = 0.0;
sl@0:     float fBestOverlap;
sl@0:     float fBestArea;
sl@0:     int iBestLeft;
sl@0:     int nLeft;
sl@0: 
sl@0:     for(
sl@0:       nLeft=RTREE_MINCELLS(pRtree); 
sl@0:       nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 
sl@0:       nLeft++
sl@0:     ){
sl@0:       RtreeCell left;
sl@0:       RtreeCell right;
sl@0:       int kk;
sl@0:       float overlap;
sl@0:       float area;
sl@0: 
sl@0:       memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
sl@0:       memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
sl@0:       for(kk=1; kk<(nCell-1); kk++){
sl@0:         if( kk<nLeft ){
sl@0:           cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
sl@0:         }else{
sl@0:           cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
sl@0:         }
sl@0:       }
sl@0:       margin += cellMargin(pRtree, &left);
sl@0:       margin += cellMargin(pRtree, &right);
sl@0:       overlap = cellOverlap(pRtree, &left, &right, 1, -1);
sl@0:       area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
sl@0:       if( (nLeft==RTREE_MINCELLS(pRtree))
sl@0:        || (overlap<fBestOverlap)
sl@0:        || (overlap==fBestOverlap && area<fBestArea)
sl@0:       ){
sl@0:         iBestLeft = nLeft;
sl@0:         fBestOverlap = overlap;
sl@0:         fBestArea = area;
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     if( ii==0 || margin<fBestMargin ){
sl@0:       iBestDim = ii;
sl@0:       fBestMargin = margin;
sl@0:       iBestSplit = iBestLeft;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
sl@0:   memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
sl@0:     RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
sl@0:     RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
sl@0:     nodeInsertCell(pRtree, pTarget, pCell);
sl@0:     cellUnion(pRtree, pBbox, pCell);
sl@0:   }
sl@0: 
sl@0:   sqlite3_free(aaSorted);
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: #if VARIANT_GUTTMAN_SPLIT
sl@0: /*
sl@0: ** Implementation of the regular R-tree SplitNode from Guttman[1984].
sl@0: */
sl@0: static int splitNodeGuttman(
sl@0:   Rtree *pRtree,
sl@0:   RtreeCell *aCell,
sl@0:   int nCell,
sl@0:   RtreeNode *pLeft,
sl@0:   RtreeNode *pRight,
sl@0:   RtreeCell *pBboxLeft,
sl@0:   RtreeCell *pBboxRight
sl@0: ){
sl@0:   int iLeftSeed = 0;
sl@0:   int iRightSeed = 1;
sl@0:   int *aiUsed;
sl@0:   int i;
sl@0: 
sl@0:   aiUsed = sqlite3_malloc(sizeof(int)*nCell);
sl@0:   memset(aiUsed, 0, sizeof(int)*nCell);
sl@0: 
sl@0:   PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
sl@0: 
sl@0:   memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
sl@0:   memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
sl@0:   nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
sl@0:   nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
sl@0:   aiUsed[iLeftSeed] = 1;
sl@0:   aiUsed[iRightSeed] = 1;
sl@0: 
sl@0:   for(i=nCell-2; i>0; i--){
sl@0:     RtreeCell *pNext;
sl@0:     pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
sl@0:     float diff =  
sl@0:       cellGrowth(pRtree, pBboxLeft, pNext) - 
sl@0:       cellGrowth(pRtree, pBboxRight, pNext)
sl@0:     ;
sl@0:     if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
sl@0:      || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
sl@0:     ){
sl@0:       nodeInsertCell(pRtree, pRight, pNext);
sl@0:       cellUnion(pRtree, pBboxRight, pNext);
sl@0:     }else{
sl@0:       nodeInsertCell(pRtree, pLeft, pNext);
sl@0:       cellUnion(pRtree, pBboxLeft, pNext);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   sqlite3_free(aiUsed);
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: static int updateMapping(
sl@0:   Rtree *pRtree, 
sl@0:   i64 iRowid, 
sl@0:   RtreeNode *pNode, 
sl@0:   int iHeight
sl@0: ){
sl@0:   int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
sl@0:   xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
sl@0:   if( iHeight>0 ){
sl@0:     RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
sl@0:     if( pChild ){
sl@0:       nodeRelease(pRtree, pChild->pParent);
sl@0:       nodeReference(pNode);
sl@0:       pChild->pParent = pNode;
sl@0:     }
sl@0:   }
sl@0:   return xSetMapping(pRtree, iRowid, pNode->iNode);
sl@0: }
sl@0: 
sl@0: static int SplitNode(
sl@0:   Rtree *pRtree,
sl@0:   RtreeNode *pNode,
sl@0:   RtreeCell *pCell,
sl@0:   int iHeight
sl@0: ){
sl@0:   int i;
sl@0:   int newCellIsRight = 0;
sl@0: 
sl@0:   int rc = SQLITE_OK;
sl@0:   int nCell = NCELL(pNode);
sl@0:   RtreeCell *aCell;
sl@0:   int *aiUsed;
sl@0: 
sl@0:   RtreeNode *pLeft = 0;
sl@0:   RtreeNode *pRight = 0;
sl@0: 
sl@0:   RtreeCell leftbbox;
sl@0:   RtreeCell rightbbox;
sl@0: 
sl@0:   /* Allocate an array and populate it with a copy of pCell and 
sl@0:   ** all cells from node pLeft. Then zero the original node.
sl@0:   */
sl@0:   aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
sl@0:   if( !aCell ){
sl@0:     rc = SQLITE_NOMEM;
sl@0:     goto splitnode_out;
sl@0:   }
sl@0:   aiUsed = (int *)&aCell[nCell+1];
sl@0:   memset(aiUsed, 0, sizeof(int)*(nCell+1));
sl@0:   for(i=0; i<nCell; i++){
sl@0:     nodeGetCell(pRtree, pNode, i, &aCell[i]);
sl@0:   }
sl@0:   nodeZero(pRtree, pNode);
sl@0:   memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
sl@0:   nCell++;
sl@0: 
sl@0:   if( pNode->iNode==1 ){
sl@0:     pRight = nodeNew(pRtree, pNode, 1);
sl@0:     pLeft = nodeNew(pRtree, pNode, 1);
sl@0:     pRtree->iDepth++;
sl@0:     pNode->isDirty = 1;
sl@0:     writeInt16(pNode->zData, pRtree->iDepth);
sl@0:   }else{
sl@0:     pLeft = pNode;
sl@0:     pRight = nodeNew(pRtree, pLeft->pParent, 1);
sl@0:     nodeReference(pLeft);
sl@0:   }
sl@0: 
sl@0:   if( !pLeft || !pRight ){
sl@0:     rc = SQLITE_NOMEM;
sl@0:     goto splitnode_out;
sl@0:   }
sl@0: 
sl@0:   memset(pLeft->zData, 0, pRtree->iNodeSize);
sl@0:   memset(pRight->zData, 0, pRtree->iNodeSize);
sl@0: 
sl@0:   rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
sl@0:   if( rc!=SQLITE_OK ){
sl@0:     goto splitnode_out;
sl@0:   }
sl@0: 
sl@0:   /* Ensure both child nodes have node numbers assigned to them. */
sl@0:   if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
sl@0:    || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
sl@0:   ){
sl@0:     goto splitnode_out;
sl@0:   }
sl@0: 
sl@0:   rightbbox.iRowid = pRight->iNode;
sl@0:   leftbbox.iRowid = pLeft->iNode;
sl@0: 
sl@0:   if( pNode->iNode==1 ){
sl@0:     rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
sl@0:     if( rc!=SQLITE_OK ){
sl@0:       goto splitnode_out;
sl@0:     }
sl@0:   }else{
sl@0:     RtreeNode *pParent = pLeft->pParent;
sl@0:     int iCell = nodeParentIndex(pRtree, pLeft);
sl@0:     nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
sl@0:     AdjustTree(pRtree, pParent, &leftbbox);
sl@0:   }
sl@0:   if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
sl@0:     goto splitnode_out;
sl@0:   }
sl@0: 
sl@0:   for(i=0; i<NCELL(pRight); i++){
sl@0:     i64 iRowid = nodeGetRowid(pRtree, pRight, i);
sl@0:     rc = updateMapping(pRtree, iRowid, pRight, iHeight);
sl@0:     if( iRowid==pCell->iRowid ){
sl@0:       newCellIsRight = 1;
sl@0:     }
sl@0:     if( rc!=SQLITE_OK ){
sl@0:       goto splitnode_out;
sl@0:     }
sl@0:   }
sl@0:   if( pNode->iNode==1 ){
sl@0:     for(i=0; i<NCELL(pLeft); i++){
sl@0:       i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
sl@0:       rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
sl@0:       if( rc!=SQLITE_OK ){
sl@0:         goto splitnode_out;
sl@0:       }
sl@0:     }
sl@0:   }else if( newCellIsRight==0 ){
sl@0:     rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
sl@0:   }
sl@0: 
sl@0:   if( rc==SQLITE_OK ){
sl@0:     rc = nodeRelease(pRtree, pRight);
sl@0:     pRight = 0;
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     rc = nodeRelease(pRtree, pLeft);
sl@0:     pLeft = 0;
sl@0:   }
sl@0: 
sl@0: splitnode_out:
sl@0:   nodeRelease(pRtree, pRight);
sl@0:   nodeRelease(pRtree, pLeft);
sl@0:   sqlite3_free(aCell);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
sl@0:   int rc = SQLITE_OK;
sl@0:   if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
sl@0:     sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
sl@0:     if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){
sl@0:       i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
sl@0:       rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
sl@0:     }else{
sl@0:       rc = SQLITE_ERROR;
sl@0:     }
sl@0:     sqlite3_reset(pRtree->pReadParent);
sl@0:     if( rc==SQLITE_OK ){
sl@0:       rc = fixLeafParent(pRtree, pLeaf->pParent);
sl@0:     }
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: static int deleteCell(Rtree *, RtreeNode *, int, int);
sl@0: 
sl@0: static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
sl@0:   int rc;
sl@0:   RtreeNode *pParent;
sl@0:   int iCell;
sl@0: 
sl@0:   assert( pNode->nRef==1 );
sl@0: 
sl@0:   /* Remove the entry in the parent cell. */
sl@0:   iCell = nodeParentIndex(pRtree, pNode);
sl@0:   pParent = pNode->pParent;
sl@0:   pNode->pParent = 0;
sl@0:   if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1)) 
sl@0:    || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
sl@0:   ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   /* Remove the xxx_node entry. */
sl@0:   sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
sl@0:   sqlite3_step(pRtree->pDeleteNode);
sl@0:   if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   /* Remove the xxx_parent entry. */
sl@0:   sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
sl@0:   sqlite3_step(pRtree->pDeleteParent);
sl@0:   if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
sl@0:     return rc;
sl@0:   }
sl@0:   
sl@0:   /* Remove the node from the in-memory hash table and link it into
sl@0:   ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
sl@0:   */
sl@0:   nodeHashDelete(pRtree, pNode);
sl@0:   pNode->iNode = iHeight;
sl@0:   pNode->pNext = pRtree->pDeleted;
sl@0:   pNode->nRef++;
sl@0:   pRtree->pDeleted = pNode;
sl@0: 
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
sl@0:   RtreeNode *pParent = pNode->pParent;
sl@0:   if( pParent ){
sl@0:     int ii; 
sl@0:     int nCell = NCELL(pNode);
sl@0:     RtreeCell box;                            /* Bounding box for pNode */
sl@0:     nodeGetCell(pRtree, pNode, 0, &box);
sl@0:     for(ii=1; ii<nCell; ii++){
sl@0:       RtreeCell cell;
sl@0:       nodeGetCell(pRtree, pNode, ii, &cell);
sl@0:       cellUnion(pRtree, &box, &cell);
sl@0:     }
sl@0:     box.iRowid = pNode->iNode;
sl@0:     ii = nodeParentIndex(pRtree, pNode);
sl@0:     nodeOverwriteCell(pRtree, pParent, &box, ii);
sl@0:     fixBoundingBox(pRtree, pParent);
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Delete the cell at index iCell of node pNode. After removing the
sl@0: ** cell, adjust the r-tree data structure if required.
sl@0: */
sl@0: static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
sl@0:   int rc;
sl@0: 
sl@0:   if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   /* Remove the cell from the node. This call just moves bytes around
sl@0:   ** the in-memory node image, so it cannot fail.
sl@0:   */
sl@0:   nodeDeleteCell(pRtree, pNode, iCell);
sl@0: 
sl@0:   /* If the node is not the tree root and now has less than the minimum
sl@0:   ** number of cells, remove it from the tree. Otherwise, update the
sl@0:   ** cell in the parent node so that it tightly contains the updated
sl@0:   ** node.
sl@0:   */
sl@0:   if( pNode->iNode!=1 ){
sl@0:     RtreeNode *pParent = pNode->pParent;
sl@0:     if( (pParent->iNode!=1 || NCELL(pParent)!=1) 
sl@0:      && (NCELL(pNode)<RTREE_MINCELLS(pRtree))
sl@0:     ){
sl@0:       rc = removeNode(pRtree, pNode, iHeight);
sl@0:     }else{
sl@0:       fixBoundingBox(pRtree, pNode);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: static int Reinsert(
sl@0:   Rtree *pRtree, 
sl@0:   RtreeNode *pNode, 
sl@0:   RtreeCell *pCell, 
sl@0:   int iHeight
sl@0: ){
sl@0:   int *aOrder;
sl@0:   int *aSpare;
sl@0:   RtreeCell *aCell;
sl@0:   float *aDistance;
sl@0:   int nCell;
sl@0:   float aCenterCoord[RTREE_MAX_DIMENSIONS];
sl@0:   int iDim;
sl@0:   int ii;
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
sl@0: 
sl@0:   nCell = NCELL(pNode)+1;
sl@0: 
sl@0:   /* Allocate the buffers used by this operation. The allocation is
sl@0:   ** relinquished before this function returns.
sl@0:   */
sl@0:   aCell = (RtreeCell *)sqlite3_malloc(nCell * (
sl@0:     sizeof(RtreeCell) +         /* aCell array */
sl@0:     sizeof(int)       +         /* aOrder array */
sl@0:     sizeof(int)       +         /* aSpare array */
sl@0:     sizeof(float)               /* aDistance array */
sl@0:   ));
sl@0:   if( !aCell ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0:   aOrder    = (int *)&aCell[nCell];
sl@0:   aSpare    = (int *)&aOrder[nCell];
sl@0:   aDistance = (float *)&aSpare[nCell];
sl@0: 
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     if( ii==(nCell-1) ){
sl@0:       memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
sl@0:     }else{
sl@0:       nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
sl@0:     }
sl@0:     aOrder[ii] = ii;
sl@0:     for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0:       aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]);
sl@0:       aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]);
sl@0:     }
sl@0:   }
sl@0:   for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0:     aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
sl@0:   }
sl@0: 
sl@0:   for(ii=0; ii<nCell; ii++){
sl@0:     aDistance[ii] = 0.0;
sl@0:     for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0:       float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) - 
sl@0:           DCOORD(aCell[ii].aCoord[iDim*2]);
sl@0:       aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   SortByDistance(aOrder, nCell, aDistance, aSpare);
sl@0:   nodeZero(pRtree, pNode);
sl@0: 
sl@0:   for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
sl@0:     RtreeCell *p = &aCell[aOrder[ii]];
sl@0:     nodeInsertCell(pRtree, pNode, p);
sl@0:     if( p->iRowid==pCell->iRowid ){
sl@0:       if( iHeight==0 ){
sl@0:         rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
sl@0:       }else{
sl@0:         rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
sl@0:       }
sl@0:     }
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     fixBoundingBox(pRtree, pNode);
sl@0:   }
sl@0:   for(; rc==SQLITE_OK && ii<nCell; ii++){
sl@0:     /* Find a node to store this cell in. pNode->iNode currently contains
sl@0:     ** the height of the sub-tree headed by the cell.
sl@0:     */
sl@0:     RtreeNode *pInsert;
sl@0:     RtreeCell *p = &aCell[aOrder[ii]];
sl@0:     rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
sl@0:     if( rc==SQLITE_OK ){
sl@0:       int rc2;
sl@0:       rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);
sl@0:       rc2 = nodeRelease(pRtree, pInsert);
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = rc2;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   sqlite3_free(aCell);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Insert cell pCell into node pNode. Node pNode is the head of a 
sl@0: ** subtree iHeight high (leaf nodes have iHeight==0).
sl@0: */
sl@0: static int rtreeInsertCell(
sl@0:   Rtree *pRtree,
sl@0:   RtreeNode *pNode,
sl@0:   RtreeCell *pCell,
sl@0:   int iHeight
sl@0: ){
sl@0:   int rc = SQLITE_OK;
sl@0:   if( iHeight>0 ){
sl@0:     RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
sl@0:     if( pChild ){
sl@0:       nodeRelease(pRtree, pChild->pParent);
sl@0:       nodeReference(pNode);
sl@0:       pChild->pParent = pNode;
sl@0:     }
sl@0:   }
sl@0:   if( nodeInsertCell(pRtree, pNode, pCell) ){
sl@0: #if VARIANT_RSTARTREE_REINSERT
sl@0:     if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
sl@0:       rc = SplitNode(pRtree, pNode, pCell, iHeight);
sl@0:     }else{
sl@0:       pRtree->iReinsertHeight = iHeight;
sl@0:       rc = Reinsert(pRtree, pNode, pCell, iHeight);
sl@0:     }
sl@0: #else
sl@0:     rc = SplitNode(pRtree, pNode, pCell, iHeight);
sl@0: #endif
sl@0:   }else{
sl@0:     AdjustTree(pRtree, pNode, pCell);
sl@0:     if( iHeight==0 ){
sl@0:       rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
sl@0:     }else{
sl@0:       rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
sl@0:     }
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
sl@0:   int ii;
sl@0:   int rc = SQLITE_OK;
sl@0:   int nCell = NCELL(pNode);
sl@0: 
sl@0:   for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
sl@0:     RtreeNode *pInsert;
sl@0:     RtreeCell cell;
sl@0:     nodeGetCell(pRtree, pNode, ii, &cell);
sl@0: 
sl@0:     /* Find a node to store this cell in. pNode->iNode currently contains
sl@0:     ** the height of the sub-tree headed by the cell.
sl@0:     */
sl@0:     rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
sl@0:     if( rc==SQLITE_OK ){
sl@0:       int rc2;
sl@0:       rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);
sl@0:       rc2 = nodeRelease(pRtree, pInsert);
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = rc2;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Select a currently unused rowid for a new r-tree record.
sl@0: */
sl@0: static int newRowid(Rtree *pRtree, i64 *piRowid){
sl@0:   int rc;
sl@0:   sqlite3_bind_null(pRtree->pWriteRowid, 1);
sl@0:   sqlite3_bind_null(pRtree->pWriteRowid, 2);
sl@0:   sqlite3_step(pRtree->pWriteRowid);
sl@0:   rc = sqlite3_reset(pRtree->pWriteRowid);
sl@0:   *piRowid = sqlite3_last_insert_rowid(pRtree->db);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: #ifndef NDEBUG
sl@0: static int hashIsEmpty(Rtree *pRtree){
sl@0:   int ii;
sl@0:   for(ii=0; ii<HASHSIZE; ii++){
sl@0:     assert( !pRtree->aHash[ii] );
sl@0:   }
sl@0:   return 1;
sl@0: }
sl@0: #endif
sl@0: 
sl@0: /*
sl@0: ** The xUpdate method for rtree module virtual tables.
sl@0: */
sl@0: int rtreeUpdate(
sl@0:   sqlite3_vtab *pVtab, 
sl@0:   int nData, 
sl@0:   sqlite3_value **azData, 
sl@0:   sqlite_int64 *pRowid
sl@0: ){
sl@0:   Rtree *pRtree = (Rtree *)pVtab;
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   rtreeReference(pRtree);
sl@0: 
sl@0:   assert(nData>=1);
sl@0:   assert(hashIsEmpty(pRtree));
sl@0: 
sl@0:   /* If azData[0] is not an SQL NULL value, it is the rowid of a
sl@0:   ** record to delete from the r-tree table. The following block does
sl@0:   ** just that.
sl@0:   */
sl@0:   if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
sl@0:     i64 iDelete;                /* The rowid to delete */
sl@0:     RtreeNode *pLeaf;           /* Leaf node containing record iDelete */
sl@0:     int iCell;                  /* Index of iDelete cell in pLeaf */
sl@0:     RtreeNode *pRoot;
sl@0: 
sl@0:     /* Obtain a reference to the root node to initialise Rtree.iDepth */
sl@0:     rc = nodeAcquire(pRtree, 1, 0, &pRoot);
sl@0: 
sl@0:     /* Obtain a reference to the leaf node that contains the entry 
sl@0:     ** about to be deleted. 
sl@0:     */
sl@0:     if( rc==SQLITE_OK ){
sl@0:       iDelete = sqlite3_value_int64(azData[0]);
sl@0:       rc = findLeafNode(pRtree, iDelete, &pLeaf);
sl@0:     }
sl@0: 
sl@0:     /* Delete the cell in question from the leaf node. */
sl@0:     if( rc==SQLITE_OK ){
sl@0:       int rc2;
sl@0:       iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
sl@0:       rc = deleteCell(pRtree, pLeaf, iCell, 0);
sl@0:       rc2 = nodeRelease(pRtree, pLeaf);
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = rc2;
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     /* Delete the corresponding entry in the <rtree>_rowid table. */
sl@0:     if( rc==SQLITE_OK ){
sl@0:       sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
sl@0:       sqlite3_step(pRtree->pDeleteRowid);
sl@0:       rc = sqlite3_reset(pRtree->pDeleteRowid);
sl@0:     }
sl@0: 
sl@0:     /* Check if the root node now has exactly one child. If so, remove
sl@0:     ** it, schedule the contents of the child for reinsertion and 
sl@0:     ** reduce the tree height by one.
sl@0:     **
sl@0:     ** This is equivalent to copying the contents of the child into
sl@0:     ** the root node (the operation that Gutman's paper says to perform 
sl@0:     ** in this scenario).
sl@0:     */
sl@0:     if( rc==SQLITE_OK && pRtree->iDepth>0 ){
sl@0:       if( rc==SQLITE_OK && NCELL(pRoot)==1 ){
sl@0:         RtreeNode *pChild;
sl@0:         i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
sl@0:         rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
sl@0:         if( rc==SQLITE_OK ){
sl@0:           rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
sl@0:         }
sl@0:         if( rc==SQLITE_OK ){
sl@0:           pRtree->iDepth--;
sl@0:           writeInt16(pRoot->zData, pRtree->iDepth);
sl@0:           pRoot->isDirty = 1;
sl@0:         }
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     /* Re-insert the contents of any underfull nodes removed from the tree. */
sl@0:     for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = reinsertNodeContent(pRtree, pLeaf);
sl@0:       }
sl@0:       pRtree->pDeleted = pLeaf->pNext;
sl@0:       sqlite3_free(pLeaf);
sl@0:     }
sl@0: 
sl@0:     /* Release the reference to the root node. */
sl@0:     if( rc==SQLITE_OK ){
sl@0:       rc = nodeRelease(pRtree, pRoot);
sl@0:     }else{
sl@0:       nodeRelease(pRtree, pRoot);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   /* If the azData[] array contains more than one element, elements
sl@0:   ** (azData[2]..azData[argc-1]) contain a new record to insert into
sl@0:   ** the r-tree structure.
sl@0:   */
sl@0:   if( rc==SQLITE_OK && nData>1 ){
sl@0:     /* Insert a new record into the r-tree */
sl@0:     RtreeCell cell;
sl@0:     int ii;
sl@0:     RtreeNode *pLeaf;
sl@0: 
sl@0:     /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
sl@0:     assert( nData==(pRtree->nDim*2 + 3) );
sl@0:     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0:       for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:         cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
sl@0:         cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
sl@0:         if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
sl@0:           rc = SQLITE_CONSTRAINT;
sl@0:           goto constraint;
sl@0:         }
sl@0:       }
sl@0:     }else{
sl@0:       for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0:         cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
sl@0:         cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
sl@0:         if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
sl@0:           rc = SQLITE_CONSTRAINT;
sl@0:           goto constraint;
sl@0:         }
sl@0:       }
sl@0:     }
sl@0: 
sl@0:     /* Figure out the rowid of the new row. */
sl@0:     if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
sl@0:       rc = newRowid(pRtree, &cell.iRowid);
sl@0:     }else{
sl@0:       cell.iRowid = sqlite3_value_int64(azData[2]);
sl@0:       sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
sl@0:       if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
sl@0:         sqlite3_reset(pRtree->pReadRowid);
sl@0:         rc = SQLITE_CONSTRAINT;
sl@0:         goto constraint;
sl@0:       }
sl@0:       rc = sqlite3_reset(pRtree->pReadRowid);
sl@0:     }
sl@0: 
sl@0:     if( rc==SQLITE_OK ){
sl@0:       rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
sl@0:     }
sl@0:     if( rc==SQLITE_OK ){
sl@0:       int rc2;
sl@0:       pRtree->iReinsertHeight = -1;
sl@0:       rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
sl@0:       rc2 = nodeRelease(pRtree, pLeaf);
sl@0:       if( rc==SQLITE_OK ){
sl@0:         rc = rc2;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0: constraint:
sl@0:   rtreeRelease(pRtree);
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** The xRename method for rtree module virtual tables.
sl@0: */
sl@0: static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
sl@0:   Rtree *pRtree = (Rtree *)pVtab;
sl@0:   int rc = SQLITE_NOMEM;
sl@0:   char *zSql = sqlite3_mprintf(
sl@0:     "ALTER TABLE %Q.'%q_node'   RENAME TO \"%w_node\";"
sl@0:     "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
sl@0:     "ALTER TABLE %Q.'%q_rowid'  RENAME TO \"%w_rowid\";"
sl@0:     , pRtree->zDb, pRtree->zName, zNewName 
sl@0:     , pRtree->zDb, pRtree->zName, zNewName 
sl@0:     , pRtree->zDb, pRtree->zName, zNewName
sl@0:   );
sl@0:   if( zSql ){
sl@0:     rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
sl@0:     sqlite3_free(zSql);
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: static sqlite3_module rtreeModule = {
sl@0:   0,                         /* iVersion */
sl@0:   rtreeCreate,                /* xCreate - create a table */
sl@0:   rtreeConnect,               /* xConnect - connect to an existing table */
sl@0:   rtreeBestIndex,             /* xBestIndex - Determine search strategy */
sl@0:   rtreeDisconnect,            /* xDisconnect - Disconnect from a table */
sl@0:   rtreeDestroy,               /* xDestroy - Drop a table */
sl@0:   rtreeOpen,                  /* xOpen - open a cursor */
sl@0:   rtreeClose,                 /* xClose - close a cursor */
sl@0:   rtreeFilter,                /* xFilter - configure scan constraints */
sl@0:   rtreeNext,                  /* xNext - advance a cursor */
sl@0:   rtreeEof,                   /* xEof */
sl@0:   rtreeColumn,                /* xColumn - read data */
sl@0:   rtreeRowid,                 /* xRowid - read data */
sl@0:   rtreeUpdate,                /* xUpdate - write data */
sl@0:   0,                          /* xBegin - begin transaction */
sl@0:   0,                          /* xSync - sync transaction */
sl@0:   0,                          /* xCommit - commit transaction */
sl@0:   0,                          /* xRollback - rollback transaction */
sl@0:   0,                          /* xFindFunction - function overloading */
sl@0:   rtreeRename                 /* xRename - rename the table */
sl@0: };
sl@0: 
sl@0: static int rtreeSqlInit(
sl@0:   Rtree *pRtree, 
sl@0:   sqlite3 *db, 
sl@0:   const char *zDb, 
sl@0:   const char *zPrefix, 
sl@0:   int isCreate
sl@0: ){
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   #define N_STATEMENT 9
sl@0:   static const char *azSql[N_STATEMENT] = {
sl@0:     /* Read and write the xxx_node table */
sl@0:     "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
sl@0:     "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
sl@0:     "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
sl@0: 
sl@0:     /* Read and write the xxx_rowid table */
sl@0:     "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
sl@0:     "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
sl@0:     "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
sl@0: 
sl@0:     /* Read and write the xxx_parent table */
sl@0:     "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
sl@0:     "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
sl@0:     "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
sl@0:   };
sl@0:   sqlite3_stmt **appStmt[N_STATEMENT];
sl@0:   int i;
sl@0: 
sl@0:   pRtree->db = db;
sl@0: 
sl@0:   if( isCreate ){
sl@0:     char *zCreate = sqlite3_mprintf(
sl@0: "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
sl@0: "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
sl@0: "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
sl@0: "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
sl@0:       zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
sl@0:     );
sl@0:     if( !zCreate ){
sl@0:       return SQLITE_NOMEM;
sl@0:     }
sl@0:     rc = sqlite3_exec(db, zCreate, 0, 0, 0);
sl@0:     sqlite3_free(zCreate);
sl@0:     if( rc!=SQLITE_OK ){
sl@0:       return rc;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   appStmt[0] = &pRtree->pReadNode;
sl@0:   appStmt[1] = &pRtree->pWriteNode;
sl@0:   appStmt[2] = &pRtree->pDeleteNode;
sl@0:   appStmt[3] = &pRtree->pReadRowid;
sl@0:   appStmt[4] = &pRtree->pWriteRowid;
sl@0:   appStmt[5] = &pRtree->pDeleteRowid;
sl@0:   appStmt[6] = &pRtree->pReadParent;
sl@0:   appStmt[7] = &pRtree->pWriteParent;
sl@0:   appStmt[8] = &pRtree->pDeleteParent;
sl@0: 
sl@0:   for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
sl@0:     char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
sl@0:     if( zSql ){
sl@0:       rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); 
sl@0:     }else{
sl@0:       rc = SQLITE_NOMEM;
sl@0:     }
sl@0:     sqlite3_free(zSql);
sl@0:   }
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** This routine queries database handle db for the page-size used by
sl@0: ** database zDb. If successful, the page-size in bytes is written to
sl@0: ** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error 
sl@0: ** code is returned.
sl@0: */
sl@0: static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){
sl@0:   int rc = SQLITE_NOMEM;
sl@0:   char *zSql;
sl@0:   sqlite3_stmt *pStmt = 0;
sl@0: 
sl@0:   zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb);
sl@0:   if( !zSql ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0: 
sl@0:   rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
sl@0:   sqlite3_free(zSql);
sl@0:   if( rc!=SQLITE_OK ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   if( SQLITE_ROW==sqlite3_step(pStmt) ){
sl@0:     *piPageSize = sqlite3_column_int(pStmt, 0);
sl@0:   }
sl@0:   return sqlite3_finalize(pStmt);
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** This function is the implementation of both the xConnect and xCreate
sl@0: ** methods of the r-tree virtual table.
sl@0: **
sl@0: **   argv[0]   -> module name
sl@0: **   argv[1]   -> database name
sl@0: **   argv[2]   -> table name
sl@0: **   argv[...] -> column names...
sl@0: */
sl@0: static int rtreeInit(
sl@0:   sqlite3 *db,                        /* Database connection */
sl@0:   void *pAux,                         /* Pointer to head of rtree list */
sl@0:   int argc, const char *const*argv,   /* Parameters to CREATE TABLE statement */
sl@0:   sqlite3_vtab **ppVtab,              /* OUT: New virtual table */
sl@0:   char **pzErr,                       /* OUT: Error message, if any */
sl@0:   int isCreate,                       /* True for xCreate, false for xConnect */
sl@0:   int eCoordType                      /* One of the RTREE_COORD_* constants */
sl@0: ){
sl@0:   int rc = SQLITE_OK;
sl@0:   int iPageSize = 0;
sl@0:   Rtree *pRtree;
sl@0:   int nDb;              /* Length of string argv[1] */
sl@0:   int nName;            /* Length of string argv[2] */
sl@0: 
sl@0:   const char *aErrMsg[] = {
sl@0:     0,                                                    /* 0 */
sl@0:     "Wrong number of columns for an rtree table",         /* 1 */
sl@0:     "Too few columns for an rtree table",                 /* 2 */
sl@0:     "Too many columns for an rtree table"                 /* 3 */
sl@0:   };
sl@0: 
sl@0:   int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
sl@0:   if( aErrMsg[iErr] ){
sl@0:     *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
sl@0:     return SQLITE_ERROR;
sl@0:   }
sl@0: 
sl@0:   rc = getPageSize(db, argv[1], &iPageSize);
sl@0:   if( rc!=SQLITE_OK ){
sl@0:     return rc;
sl@0:   }
sl@0: 
sl@0:   /* Allocate the sqlite3_vtab structure */
sl@0:   nDb = strlen(argv[1]);
sl@0:   nName = strlen(argv[2]);
sl@0:   pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
sl@0:   if( !pRtree ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0:   memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
sl@0:   pRtree->nBusy = 1;
sl@0:   pRtree->base.pModule = &rtreeModule;
sl@0:   pRtree->zDb = (char *)&pRtree[1];
sl@0:   pRtree->zName = &pRtree->zDb[nDb+1];
sl@0:   pRtree->nDim = (argc-4)/2;
sl@0:   pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
sl@0:   pRtree->eCoordType = eCoordType;
sl@0:   memcpy(pRtree->zDb, argv[1], nDb);
sl@0:   memcpy(pRtree->zName, argv[2], nName);
sl@0: 
sl@0:   /* Figure out the node size to use. By default, use 64 bytes less than
sl@0:   ** the database page-size. This ensures that each node is stored on
sl@0:   ** a single database page.
sl@0:   **
sl@0:   ** If the databasd page-size is so large that more than RTREE_MAXCELLS
sl@0:   ** entries would fit in a single node, use a smaller node-size.
sl@0:   */
sl@0:   pRtree->iNodeSize = iPageSize-64;
sl@0:   if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
sl@0:     pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
sl@0:   }
sl@0: 
sl@0:   /* Create/Connect to the underlying relational database schema. If
sl@0:   ** that is successful, call sqlite3_declare_vtab() to configure
sl@0:   ** the r-tree table schema.
sl@0:   */
sl@0:   if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
sl@0:     *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
sl@0:   }else{
sl@0:     char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
sl@0:     char *zTmp;
sl@0:     int ii;
sl@0:     for(ii=4; zSql && ii<argc; ii++){
sl@0:       zTmp = zSql;
sl@0:       zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
sl@0:       sqlite3_free(zTmp);
sl@0:     }
sl@0:     if( zSql ){
sl@0:       zTmp = zSql;
sl@0:       zSql = sqlite3_mprintf("%s);", zTmp);
sl@0:       sqlite3_free(zTmp);
sl@0:     }
sl@0:     if( !zSql || sqlite3_declare_vtab(db, zSql) ){
sl@0:       rc = SQLITE_NOMEM;
sl@0:     }
sl@0:     sqlite3_free(zSql);
sl@0:   }
sl@0: 
sl@0:   if( rc==SQLITE_OK ){
sl@0:     *ppVtab = (sqlite3_vtab *)pRtree;
sl@0:   }else{
sl@0:     rtreeRelease(pRtree);
sl@0:   }
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** Implementation of a scalar function that decodes r-tree nodes to
sl@0: ** human readable strings. This can be used for debugging and analysis.
sl@0: **
sl@0: ** The scalar function takes two arguments, a blob of data containing
sl@0: ** an r-tree node, and the number of dimensions the r-tree indexes.
sl@0: ** For a two-dimensional r-tree structure called "rt", to deserialize
sl@0: ** all nodes, a statement like:
sl@0: **
sl@0: **   SELECT rtreenode(2, data) FROM rt_node;
sl@0: **
sl@0: ** The human readable string takes the form of a Tcl list with one
sl@0: ** entry for each cell in the r-tree node. Each entry is itself a
sl@0: ** list, containing the 8-byte rowid/pageno followed by the 
sl@0: ** <num-dimension>*2 coordinates.
sl@0: */
sl@0: static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
sl@0:   char *zText = 0;
sl@0:   RtreeNode node;
sl@0:   Rtree tree;
sl@0:   int ii;
sl@0: 
sl@0:   memset(&node, 0, sizeof(RtreeNode));
sl@0:   memset(&tree, 0, sizeof(Rtree));
sl@0:   tree.nDim = sqlite3_value_int(apArg[0]);
sl@0:   tree.nBytesPerCell = 8 + 8 * tree.nDim;
sl@0:   node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
sl@0: 
sl@0:   for(ii=0; ii<NCELL(&node); ii++){
sl@0:     char zCell[512];
sl@0:     int nCell = 0;
sl@0:     RtreeCell cell;
sl@0:     int jj;
sl@0: 
sl@0:     nodeGetCell(&tree, &node, ii, &cell);
sl@0:     sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid);
sl@0:     nCell = strlen(zCell);
sl@0:     for(jj=0; jj<tree.nDim*2; jj++){
sl@0:       sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
sl@0:       nCell = strlen(zCell);
sl@0:     }
sl@0: 
sl@0:     if( zText ){
sl@0:       char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
sl@0:       sqlite3_free(zText);
sl@0:       zText = zTextNew;
sl@0:     }else{
sl@0:       zText = sqlite3_mprintf("{%s}", zCell);
sl@0:     }
sl@0:   }
sl@0:   
sl@0:   sqlite3_result_text(ctx, zText, -1, sqlite3_free);
sl@0: }
sl@0: 
sl@0: static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
sl@0:   if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB 
sl@0:    || sqlite3_value_bytes(apArg[0])<2
sl@0:   ){
sl@0:     sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); 
sl@0:   }else{
sl@0:     u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
sl@0:     sqlite3_result_int(ctx, readInt16(zBlob));
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Register the r-tree module with database handle db. This creates the
sl@0: ** virtual table module "rtree" and the debugging/analysis scalar 
sl@0: ** function "rtreenode".
sl@0: */
sl@0: int sqlite3RtreeInit(sqlite3 *db){
sl@0:   int rc = SQLITE_OK;
sl@0: 
sl@0:   if( rc==SQLITE_OK ){
sl@0:     int utf8 = SQLITE_UTF8;
sl@0:     rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     int utf8 = SQLITE_UTF8;
sl@0:     rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     void *c = (void *)RTREE_COORD_REAL32;
sl@0:     rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
sl@0:   }
sl@0:   if( rc==SQLITE_OK ){
sl@0:     void *c = (void *)RTREE_COORD_INT32;
sl@0:     rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
sl@0:   }
sl@0: 
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: #if !SQLITE_CORE
sl@0: int sqlite3_extension_init(
sl@0:   sqlite3 *db,
sl@0:   char **pzErrMsg,
sl@0:   const sqlite3_api_routines *pApi
sl@0: ){
sl@0:   SQLITE_EXTENSION_INIT2(pApi)
sl@0:   return sqlite3RtreeInit(db);
sl@0: }
sl@0: #endif
sl@0: 
sl@0: #endif