/*

 ** 2001 September 15

 **

 ** The author disclaims copyright to this source code.  In place of

 ** a legal notice, here is a blessing:

 **

 **    May you do good and not evil.

 **    May you find forgiveness for yourself and forgive others.

 **    May you share freely, never taking more than you give.

 **

 *************************************************************************

 ** This file contains code for implementations of the r-tree and r*-tree

 ** algorithms packaged as an SQLite virtual table module.

 **

 ** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $

 */

 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

 /*

 ** This file contains an implementation of a couple of different variants

 ** of the r-tree algorithm. See the README file for further details. The 

 ** same data-structure is used for all, but the algorithms for insert and

 ** delete operations vary. The variants used are selected at compile time 

 ** by defining the following symbols:

 */

 /* Either, both or none of the following may be set to activate 

 ** r*tree variant algorithms.

 */

 #define VARIANT_RSTARTREE_CHOOSESUBTREE 0

 #define VARIANT_RSTARTREE_REINSERT      1

 /* 

 ** Exactly one of the following must be set to 1.

 */

 #define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0

 #define VARIANT_GUTTMAN_LINEAR_SPLIT    0

 #define VARIANT_RSTARTREE_SPLIT         1

 #define VARIANT_GUTTMAN_SPLIT \

         (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)

 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT

   #define PickNext QuadraticPickNext

   #define PickSeeds QuadraticPickSeeds

   #define AssignCells splitNodeGuttman

 #endif

 #if VARIANT_GUTTMAN_LINEAR_SPLIT

   #define PickNext LinearPickNext

   #define PickSeeds LinearPickSeeds

   #define AssignCells splitNodeGuttman

 #endif

 #if VARIANT_RSTARTREE_SPLIT

   #define AssignCells splitNodeStartree

 #endif

 #ifndef SQLITE_CORE

   #include "sqlite3ext.h"

   SQLITE_EXTENSION_INIT1

 #else

   #include "sqlite3.h"

 #endif

 #include <string.h>

 #include <assert.h>

 #ifndef SQLITE_AMALGAMATION

 typedef sqlite3_int64 i64;

 typedef unsigned char u8;

 typedef unsigned int u32;

 #endif

 typedef struct Rtree Rtree;

 typedef struct RtreeCursor RtreeCursor;

 typedef struct RtreeNode RtreeNode;

 typedef struct RtreeCell RtreeCell;

 typedef struct RtreeConstraint RtreeConstraint;

 typedef union RtreeCoord RtreeCoord;

 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */

 #define RTREE_MAX_DIMENSIONS 5

 /* Size of hash table Rtree.aHash. This hash table is not expected to

 ** ever contain very many entries, so a fixed number of buckets is 

 ** used.

 */

 #define HASHSIZE 128

 /* 

 ** An rtree virtual-table object.

 */

 struct Rtree {

   sqlite3_vtab base;

   sqlite3 *db;                /* Host database connection */

   int iNodeSize;              /* Size in bytes of each node in the node table */

   int nDim;                   /* Number of dimensions */

   int nBytesPerCell;          /* Bytes consumed per cell */

   int iDepth;                 /* Current depth of the r-tree structure */

   char *zDb;                  /* Name of database containing r-tree table */

   char *zName;                /* Name of r-tree table */ 

   RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 

   int nBusy;                  /* Current number of users of this structure */

   /* List of nodes removed during a CondenseTree operation. List is

   ** linked together via the pointer normally used for hash chains -

   ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 

   ** headed by the node (leaf nodes have RtreeNode.iNode==0).

   */

   RtreeNode *pDeleted;

   int iReinsertHeight;        /* Height of sub-trees Reinsert() has run on */

   /* Statements to read/write/delete a record from xxx_node */

   sqlite3_stmt *pReadNode;

   sqlite3_stmt *pWriteNode;

   sqlite3_stmt *pDeleteNode;

   /* Statements to read/write/delete a record from xxx_rowid */

   sqlite3_stmt *pReadRowid;

   sqlite3_stmt *pWriteRowid;

   sqlite3_stmt *pDeleteRowid;

   /* Statements to read/write/delete a record from xxx_parent */

   sqlite3_stmt *pReadParent;

   sqlite3_stmt *pWriteParent;

   sqlite3_stmt *pDeleteParent;

   int eCoordType;

 };

 /* Possible values for eCoordType: */

 #define RTREE_COORD_REAL32 0

 #define RTREE_COORD_INT32  1

 /*

 ** The minimum number of cells allowed for a node is a third of the 

 ** maximum. In Gutman's notation:

 **

 **     m = M/3

 **

 ** If an R*-tree "Reinsert" operation is required, the same number of

 ** cells are removed from the overfull node and reinserted into the tree.

 */

 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)

 #define RTREE_REINSERT(p) RTREE_MINCELLS(p)

 #define RTREE_MAXCELLS 51

 /* 

 ** An rtree cursor object.

 */

 struct RtreeCursor {

   sqlite3_vtab_cursor base;

   RtreeNode *pNode;                 /* Node cursor is currently pointing at */

   int iCell;                        /* Index of current cell in pNode */

   int iStrategy;                    /* Copy of idxNum search parameter */

   int nConstraint;                  /* Number of entries in aConstraint */

   RtreeConstraint *aConstraint;     /* Search constraints. */

 };

 union RtreeCoord {

   float f;

   int i;

 };

 /*

 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord

 ** formatted as a double. This macro assumes that local variable pRtree points

 ** to the Rtree structure associated with the RtreeCoord.

 */

 #define DCOORD(coord) (                           \

   (pRtree->eCoordType==RTREE_COORD_REAL32) ?      \

     ((double)coord.f) :                           \

     ((double)coord.i)                             \

 )

 /*

 ** A search constraint.

 */

 struct RtreeConstraint {

   int iCoord;                       /* Index of constrained coordinate */

   int op;                           /* Constraining operation */

   double rValue;                    /* Constraint value. */

 };

 /* Possible values for RtreeConstraint.op */

 #define RTREE_EQ 0x41

 #define RTREE_LE 0x42

 #define RTREE_LT 0x43

 #define RTREE_GE 0x44

 #define RTREE_GT 0x45

 /* 

 ** An rtree structure node.

 **

 ** Data format (RtreeNode.zData):

 **

 **   1. If the node is the root node (node 1), then the first 2 bytes

 **      of the node contain the tree depth as a big-endian integer.

 **      For non-root nodes, the first 2 bytes are left unused.

 **

 **   2. The next 2 bytes contain the number of entries currently 

 **      stored in the node.

 **

 **   3. The remainder of the node contains the node entries. Each entry

 **      consists of a single 8-byte integer followed by an even number

 **      of 4-byte coordinates. For leaf nodes the integer is the rowid

 **      of a record. For internal nodes it is the node number of a

 **      child page.

 */

 struct RtreeNode {

   RtreeNode *pParent;               /* Parent node */

   i64 iNode;

   int nRef;

   int isDirty;

   u8 *zData;

   RtreeNode *pNext;                 /* Next node in this hash chain */

 };

 #define NCELL(pNode) readInt16(&(pNode)->zData[2])

 /* 

 ** Structure to store a deserialized rtree record.

 */

 struct RtreeCell {

   i64 iRowid;

   RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];

 };

 #define MAX(x,y) ((x) < (y) ? (y) : (x))

 #define MIN(x,y) ((x) > (y) ? (y) : (x))

 /*

 ** Functions to deserialize a 16 bit integer, 32 bit real number and

 ** 64 bit integer. The deserialized value is returned.

 */

 static int readInt16(u8 *p){

   return (p[0]<<8) + p[1];

 }

 static void readCoord(u8 *p, RtreeCoord *pCoord){

   u32 i = (

     (((u32)p[0]) << 24) + 

     (((u32)p[1]) << 16) + 

     (((u32)p[2]) <<  8) + 

     (((u32)p[3]) <<  0)

   );

   *(u32 *)pCoord = i;

 }

 static i64 readInt64(u8 *p){

   return (

     (((i64)p[0]) << 56) + 

     (((i64)p[1]) << 48) + 

     (((i64)p[2]) << 40) + 

     (((i64)p[3]) << 32) + 

     (((i64)p[4]) << 24) + 

     (((i64)p[5]) << 16) + 

     (((i64)p[6]) <<  8) + 

     (((i64)p[7]) <<  0)

   );

 }

 /*

 ** Functions to serialize a 16 bit integer, 32 bit real number and

 ** 64 bit integer. The value returned is the number of bytes written

 ** to the argument buffer (always 2, 4 and 8 respectively).

 */

 static int writeInt16(u8 *p, int i){

   p[0] = (i>> 8)&0xFF;

   p[1] = (i>> 0)&0xFF;

   return 2;

 }

 static int writeCoord(u8 *p, RtreeCoord *pCoord){

   u32 i;

   assert( sizeof(RtreeCoord)==4 );

   assert( sizeof(u32)==4 );

   i = *(u32 *)pCoord;

   p[0] = (i>>24)&0xFF;

   p[1] = (i>>16)&0xFF;

   p[2] = (i>> 8)&0xFF;

   p[3] = (i>> 0)&0xFF;

   return 4;

 }

 static int writeInt64(u8 *p, i64 i){

   p[0] = (i>>56)&0xFF;

   p[1] = (i>>48)&0xFF;

   p[2] = (i>>40)&0xFF;

   p[3] = (i>>32)&0xFF;

   p[4] = (i>>24)&0xFF;

   p[5] = (i>>16)&0xFF;

   p[6] = (i>> 8)&0xFF;

   p[7] = (i>> 0)&0xFF;

   return 8;

 }

 /*

 ** Increment the reference count of node p.

 */

 static void nodeReference(RtreeNode *p){

   if( p ){

     p->nRef++;

   }

 }

 /*

 ** Clear the content of node p (set all bytes to 0x00).

 */

 static void nodeZero(Rtree *pRtree, RtreeNode *p){

   if( p ){

     memset(&p->zData[2], 0, pRtree->iNodeSize-2);

     p->isDirty = 1;

   }

 }

 /*

 ** Given a node number iNode, return the corresponding key to use

 ** in the Rtree.aHash table.

 */

 static int nodeHash(i64 iNode){

   return (

     (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 

     (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)

   ) % HASHSIZE;

 }

 /*

 ** Search the node hash table for node iNode. If found, return a pointer

 ** to it. Otherwise, return 0.

 */

 static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){

   RtreeNode *p;

   assert( iNode!=0 );

   for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);

   return p;

 }

 /*

 ** Add node pNode to the node hash table.

 */

 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){

   if( pNode ){

     int iHash;

     assert( pNode->pNext==0 );

     iHash = nodeHash(pNode->iNode);

     pNode->pNext = pRtree->aHash[iHash];

     pRtree->aHash[iHash] = pNode;

   }

 }

 /*

 ** Remove node pNode from the node hash table.

 */

 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){

   RtreeNode **pp;

   if( pNode->iNode!=0 ){

     pp = &pRtree->aHash[nodeHash(pNode->iNode)];

     for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }

     *pp = pNode->pNext;

     pNode->pNext = 0;

   }

 }

 /*

 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),

 ** indicating that node has not yet been assigned a node number. It is

 ** assigned a node number when nodeWrite() is called to write the

 ** node contents out to the database.

 */

 static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){

   RtreeNode *pNode;

   pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);

   if( pNode ){

     memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));

     pNode->zData = (u8 *)&pNode[1];

     pNode->nRef = 1;

     pNode->pParent = pParent;

     pNode->isDirty = 1;

     nodeReference(pParent);

   }

   return pNode;

 }

 /*

 ** Obtain a reference to an r-tree node.

 */

 static int

 nodeAcquire(

   Rtree *pRtree,             /* R-tree structure */

   i64 iNode,                 /* Node number to load */

   RtreeNode *pParent,        /* Either the parent node or NULL */

   RtreeNode **ppNode         /* OUT: Acquired node */

 ){

   int rc;

   RtreeNode *pNode;

   /* Check if the requested node is already in the hash table. If so,

   ** increase its reference count and return it.

   */

   if( (pNode = nodeHashLookup(pRtree, iNode)) ){

     assert( !pParent || !pNode->pParent || pNode->pParent==pParent );

     if( pParent ){

       pNode->pParent = pParent;

     }

     pNode->nRef++;

     *ppNode = pNode;

     return SQLITE_OK;

   }

   pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);

   if( !pNode ){

     *ppNode = 0;

     return SQLITE_NOMEM;

   }

   pNode->pParent = pParent;

   pNode->zData = (u8 *)&pNode[1];

   pNode->nRef = 1;

   pNode->iNode = iNode;

   pNode->isDirty = 0;

   pNode->pNext = 0;

   sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);

   rc = sqlite3_step(pRtree->pReadNode);

   if( rc==SQLITE_ROW ){

     const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);

     memcpy(pNode->zData, zBlob, pRtree->iNodeSize);

     nodeReference(pParent);

   }else{

     sqlite3_free(pNode);

     pNode = 0;

   }

   *ppNode = pNode;

   rc = sqlite3_reset(pRtree->pReadNode);

   if( rc==SQLITE_OK && iNode==1 ){

     pRtree->iDepth = readInt16(pNode->zData);

   }

   assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );

   nodeHashInsert(pRtree, pNode);

   return rc;

 }

 /*

 ** Overwrite cell iCell of node pNode with the contents of pCell.

 */

 static void nodeOverwriteCell(

   Rtree *pRtree, 

   RtreeNode *pNode,  

   RtreeCell *pCell, 

   int iCell

 ){

   int ii;

   u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];

   p += writeInt64(p, pCell->iRowid);

   for(ii=0; ii<(pRtree->nDim*2); ii++){

     p += writeCoord(p, &pCell->aCoord[ii]);

   }

   pNode->isDirty = 1;

 }

 /*

 ** Remove cell the cell with index iCell from node pNode.

 */

 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){

   u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];

   u8 *pSrc = &pDst[pRtree->nBytesPerCell];

   int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;

   memmove(pDst, pSrc, nByte);

   writeInt16(&pNode->zData[2], NCELL(pNode)-1);

   pNode->isDirty = 1;

 }

 /*

 ** Insert the contents of cell pCell into node pNode. If the insert

 ** is successful, return SQLITE_OK.

 **

 ** If there is not enough free space in pNode, return SQLITE_FULL.

 */

 static int

 nodeInsertCell(

   Rtree *pRtree, 

   RtreeNode *pNode, 

   RtreeCell *pCell 

 ){

   int nCell;                    /* Current number of cells in pNode */

   int nMaxCell;                 /* Maximum number of cells for pNode */

   nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;

   nCell = NCELL(pNode);

   assert(nCell<=nMaxCell);

   if( nCell<nMaxCell ){

     nodeOverwriteCell(pRtree, pNode, pCell, nCell);

     writeInt16(&pNode->zData[2], nCell+1);

     pNode->isDirty = 1;

   }

   return (nCell==nMaxCell);

 }

 /*

 ** If the node is dirty, write it out to the database.

 */

 static int

 nodeWrite(Rtree *pRtree, RtreeNode *pNode){

   int rc = SQLITE_OK;

   if( pNode->isDirty ){

     sqlite3_stmt *p = pRtree->pWriteNode;

     if( pNode->iNode ){

       sqlite3_bind_int64(p, 1, pNode->iNode);

     }else{

       sqlite3_bind_null(p, 1);

     }

     sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);

     sqlite3_step(p);

     pNode->isDirty = 0;

     rc = sqlite3_reset(p);

     if( pNode->iNode==0 && rc==SQLITE_OK ){

       pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);

       nodeHashInsert(pRtree, pNode);

     }

   }

   return rc;

 }

 /*

 ** Release a reference to a node. If the node is dirty and the reference

 ** count drops to zero, the node data is written to the database.

 */

 static int

 nodeRelease(Rtree *pRtree, RtreeNode *pNode){

   int rc = SQLITE_OK;

   if( pNode ){

     assert( pNode->nRef>0 );

     pNode->nRef--;

     if( pNode->nRef==0 ){

       if( pNode->iNode==1 ){

         pRtree->iDepth = -1;

       }

       if( pNode->pParent ){

         rc = nodeRelease(pRtree, pNode->pParent);

       }

       if( rc==SQLITE_OK ){

         rc = nodeWrite(pRtree, pNode);

       }

       nodeHashDelete(pRtree, pNode);

       sqlite3_free(pNode);

     }

   }

   return rc;

 }

 /*

 ** Return the 64-bit integer value associated with cell iCell of

 ** node pNode. If pNode is a leaf node, this is a rowid. If it is

 ** an internal node, then the 64-bit integer is a child page number.

 */

 static i64 nodeGetRowid(

   Rtree *pRtree, 

   RtreeNode *pNode, 

   int iCell

 ){

   assert( iCell<NCELL(pNode) );

   return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);

 }

 /*

 ** Return coordinate iCoord from cell iCell in node pNode.

 */

 static void nodeGetCoord(

   Rtree *pRtree, 

   RtreeNode *pNode, 

   int iCell,

   int iCoord,

   RtreeCoord *pCoord           /* Space to write result to */

 ){

   readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);

 }

 /*

 ** Deserialize cell iCell of node pNode. Populate the structure pointed

 ** to by pCell with the results.

 */

 static void nodeGetCell(

   Rtree *pRtree, 

   RtreeNode *pNode, 

   int iCell,

   RtreeCell *pCell

 ){

   int ii;

   pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);

   for(ii=0; ii<pRtree->nDim*2; ii++){

     nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);

   }

 }

 /* Forward declaration for the function that does the work of

 ** the virtual table module xCreate() and xConnect() methods.

 */

 static int rtreeInit(

   sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int

 );

 /* 

 ** Rtree virtual table module xCreate method.

 */

 static int rtreeCreate(

   sqlite3 *db,

   void *pAux,

   int argc, const char *const*argv,

   sqlite3_vtab **ppVtab,

   char **pzErr

 ){

   return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux);

 }

 /* 

 ** Rtree virtual table module xConnect method.

 */

 static int rtreeConnect(

   sqlite3 *db,

   void *pAux,

   int argc, const char *const*argv,

   sqlite3_vtab **ppVtab,

   char **pzErr

 ){

   return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux);

 }

 /*

 ** Increment the r-tree reference count.

 */

 static void rtreeReference(Rtree *pRtree){

   pRtree->nBusy++;

 }

 /*

 ** Decrement the r-tree reference count. When the reference count reaches

 ** zero the structure is deleted.

 */

 static void rtreeRelease(Rtree *pRtree){

   pRtree->nBusy--;

   if( pRtree->nBusy==0 ){

     sqlite3_finalize(pRtree->pReadNode);

     sqlite3_finalize(pRtree->pWriteNode);

     sqlite3_finalize(pRtree->pDeleteNode);

     sqlite3_finalize(pRtree->pReadRowid);

     sqlite3_finalize(pRtree->pWriteRowid);

     sqlite3_finalize(pRtree->pDeleteRowid);

     sqlite3_finalize(pRtree->pReadParent);

     sqlite3_finalize(pRtree->pWriteParent);

     sqlite3_finalize(pRtree->pDeleteParent);

     sqlite3_free(pRtree);

   }

 }

 /* 

 ** Rtree virtual table module xDisconnect method.

 */

 static int rtreeDisconnect(sqlite3_vtab *pVtab){

   rtreeRelease((Rtree *)pVtab);

   return SQLITE_OK;

 }

 /* 

 ** Rtree virtual table module xDestroy method.

 */

 static int rtreeDestroy(sqlite3_vtab *pVtab){

   Rtree *pRtree = (Rtree *)pVtab;

   int rc;

   char *zCreate = sqlite3_mprintf(

     "DROP TABLE '%q'.'%q_node';"

     "DROP TABLE '%q'.'%q_rowid';"

     "DROP TABLE '%q'.'%q_parent';",

     pRtree->zDb, pRtree->zName, 

     pRtree->zDb, pRtree->zName,

     pRtree->zDb, pRtree->zName

   );

   if( !zCreate ){

     rc = SQLITE_NOMEM;

   }else{

     rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);

     sqlite3_free(zCreate);

   }

   if( rc==SQLITE_OK ){

     rtreeRelease(pRtree);

   }

   return rc;

 }

 /* 

 ** Rtree virtual table module xOpen method.

 */

 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){

   int rc = SQLITE_NOMEM;

   RtreeCursor *pCsr;

   pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));

   if( pCsr ){

     memset(pCsr, 0, sizeof(RtreeCursor));

     pCsr->base.pVtab = pVTab;

     rc = SQLITE_OK;

   }

   *ppCursor = (sqlite3_vtab_cursor *)pCsr;

   return rc;

 }

 /* 

 ** Rtree virtual table module xClose method.

 */

 static int rtreeClose(sqlite3_vtab_cursor *cur){

   Rtree *pRtree = (Rtree *)(cur->pVtab);

   int rc;

   RtreeCursor *pCsr = (RtreeCursor *)cur;

   sqlite3_free(pCsr->aConstraint);

   rc = nodeRelease(pRtree, pCsr->pNode);

   sqlite3_free(pCsr);

   return rc;

 }

 /*

 ** Rtree virtual table module xEof method.

 **

 ** Return non-zero if the cursor does not currently point to a valid 

 ** record (i.e if the scan has finished), or zero otherwise.

 */

 static int rtreeEof(sqlite3_vtab_cursor *cur){

   RtreeCursor *pCsr = (RtreeCursor *)cur;

   return (pCsr->pNode==0);

 }

 /* 

 ** Cursor pCursor currently points to a cell in a non-leaf page.

 ** Return true if the sub-tree headed by the cell is filtered

 ** (excluded) by the constraints in the pCursor->aConstraint[] 

 ** array, or false otherwise.

 */

 static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){

   RtreeCell cell;

   int ii;

   int bRes = 0;

   nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);

   for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){

     RtreeConstraint *p = &pCursor->aConstraint[ii];

     double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);

     double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);

     assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 

         || p->op==RTREE_GT || p->op==RTREE_EQ

     );

     switch( p->op ){

       case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break;

       case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break;

       case RTREE_EQ: 

         bRes = (p->rValue>cell_max || p->rValue<cell_min);

         break;

     }

   }

   return bRes;

 }

 /* 

 ** Return true if the cell that cursor pCursor currently points to

 ** would be filtered (excluded) by the constraints in the 

 ** pCursor->aConstraint[] array, or false otherwise.

 **

 ** This function assumes that the cell is part of a leaf node.

 */

 static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){

   RtreeCell cell;

   int ii;

   nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);

   for(ii=0; ii<pCursor->nConstraint; ii++){

     RtreeConstraint *p = &pCursor->aConstraint[ii];

     double coord = DCOORD(cell.aCoord[p->iCoord]);

     int res;

     assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 

         || p->op==RTREE_GT || p->op==RTREE_EQ

     );

     switch( p->op ){

       case RTREE_LE: res = (coord<=p->rValue); break;

       case RTREE_LT: res = (coord<p->rValue);  break;

       case RTREE_GE: res = (coord>=p->rValue); break;

       case RTREE_GT: res = (coord>p->rValue);  break;

       case RTREE_EQ: res = (coord==p->rValue); break;

     }

     if( !res ) return 1;

   }

   return 0;

 }

 /*

 ** Cursor pCursor currently points at a node that heads a sub-tree of

 ** height iHeight (if iHeight==0, then the node is a leaf). Descend

 ** to point to the left-most cell of the sub-tree that matches the 

 ** configured constraints.

 */

 static int descendToCell(

   Rtree *pRtree, 

   RtreeCursor *pCursor, 

   int iHeight,

   int *pEof                 /* OUT: Set to true if cannot descend */

 ){

   int isEof;

   int rc;

   int ii;

   RtreeNode *pChild;

   sqlite3_int64 iRowid;

   RtreeNode *pSavedNode = pCursor->pNode;

   int iSavedCell = pCursor->iCell;

   assert( iHeight>=0 );

   if( iHeight==0 ){

     isEof = testRtreeEntry(pRtree, pCursor);

   }else{

     isEof = testRtreeCell(pRtree, pCursor);

   }

   if( isEof || iHeight==0 ){

     *pEof = isEof;

     return SQLITE_OK;

   }

   iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);

   rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);

   if( rc!=SQLITE_OK ){

     return rc;

   }

   nodeRelease(pRtree, pCursor->pNode);

   pCursor->pNode = pChild;

   isEof = 1;

   for(ii=0; isEof && ii<NCELL(pChild); ii++){

     pCursor->iCell = ii;

     rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);

     if( rc!=SQLITE_OK ){

       return rc;

     }

   }

   if( isEof ){

     assert( pCursor->pNode==pChild );

     nodeReference(pSavedNode);

     nodeRelease(pRtree, pChild);

     pCursor->pNode = pSavedNode;

     pCursor->iCell = iSavedCell;

   }

   *pEof = isEof;

   return SQLITE_OK;

 }

 /*

 ** One of the cells in node pNode is guaranteed to have a 64-bit 

 ** integer value equal to iRowid. Return the index of this cell.

 */

 static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){

   int ii;

   for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){

     assert( ii<(NCELL(pNode)-1) );

   }

   return ii;

 }

 /*

 ** Return the index of the cell containing a pointer to node pNode

 ** in its parent. If pNode is the root node, return -1.

 */

 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){

   RtreeNode *pParent = pNode->pParent;

   if( pParent ){

     return nodeRowidIndex(pRtree, pParent, pNode->iNode);

   }

   return -1;

 }

 /* 

 ** Rtree virtual table module xNext method.

 */

 static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){

   Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);

   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;

   int rc = SQLITE_OK;

   if( pCsr->iStrategy==1 ){

     /* This "scan" is a direct lookup by rowid. There is no next entry. */

     nodeRelease(pRtree, pCsr->pNode);

     pCsr->pNode = 0;

   }

   else if( pCsr->pNode ){

     /* Move to the next entry that matches the configured constraints. */

     int iHeight = 0;

     while( pCsr->pNode ){

       RtreeNode *pNode = pCsr->pNode;

       int nCell = NCELL(pNode);

       for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){

         int isEof;

         rc = descendToCell(pRtree, pCsr, iHeight, &isEof);

         if( rc!=SQLITE_OK || !isEof ){

           return rc;

         }

       }

       pCsr->pNode = pNode->pParent;

       pCsr->iCell = nodeParentIndex(pRtree, pNode);

       nodeReference(pCsr->pNode);

       nodeRelease(pRtree, pNode);

       iHeight++;

     }

   }

   return rc;

 }

 /* 

 ** Rtree virtual table module xRowid method.

 */

 static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){

   Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;

   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;

   assert(pCsr->pNode);

   *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);

   return SQLITE_OK;

 }

 /* 

 ** Rtree virtual table module xColumn method.

 */

 static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){

   Rtree *pRtree = (Rtree *)cur->pVtab;

   RtreeCursor *pCsr = (RtreeCursor *)cur;

   if( i==0 ){

     i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);

     sqlite3_result_int64(ctx, iRowid);

   }else{

     RtreeCoord c;

     nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);

     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){

       sqlite3_result_double(ctx, c.f);

     }else{

       assert( pRtree->eCoordType==RTREE_COORD_INT32 );

       sqlite3_result_int(ctx, c.i);

     }

   }

   return SQLITE_OK;

 }

 /* 

 ** Use nodeAcquire() to obtain the leaf node containing the record with 

 ** rowid iRowid. If successful, set *ppLeaf to point to the node and

 ** return SQLITE_OK. If there is no such record in the table, set

 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf

 ** to zero and return an SQLite error code.

 */

 static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){

   int rc;

   *ppLeaf = 0;

   sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);

   if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){

     i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);

     rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);

     sqlite3_reset(pRtree->pReadRowid);

   }else{

     rc = sqlite3_reset(pRtree->pReadRowid);

   }

   return rc;

 }

 /* 

 ** Rtree virtual table module xFilter method.

 */

 static int rtreeFilter(

   sqlite3_vtab_cursor *pVtabCursor, 

   int idxNum, const char *idxStr,

   int argc, sqlite3_value **argv

 ){

   Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;

   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;

   RtreeNode *pRoot = 0;

   int ii;

   int rc = SQLITE_OK;

   rtreeReference(pRtree);

   sqlite3_free(pCsr->aConstraint);

   pCsr->aConstraint = 0;

   pCsr->iStrategy = idxNum;

   if( idxNum==1 ){

     /* Special case - lookup by rowid. */

     RtreeNode *pLeaf;        /* Leaf on which the required cell resides */

     i64 iRowid = sqlite3_value_int64(argv[0]);

     rc = findLeafNode(pRtree, iRowid, &pLeaf);

     pCsr->pNode = pLeaf; 

     if( pLeaf && rc==SQLITE_OK ){

       pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);

     }

   }else{

     /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 

     ** with the configured constraints. 

     */

     if( argc>0 ){

       pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);

       pCsr->nConstraint = argc;

       if( !pCsr->aConstraint ){

         rc = SQLITE_NOMEM;

       }else{

         assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );

         for(ii=0; ii<argc; ii++){

           RtreeConstraint *p = &pCsr->aConstraint[ii];

           p->op = idxStr[ii*2];

           p->iCoord = idxStr[ii*2+1]-'a';

           p->rValue = sqlite3_value_double(argv[ii]);

         }

       }

     }

     if( rc==SQLITE_OK ){

       pCsr->pNode = 0;

       rc = nodeAcquire(pRtree, 1, 0, &pRoot);

     }

     if( rc==SQLITE_OK ){

       int isEof = 1;

       int nCell = NCELL(pRoot);

       pCsr->pNode = pRoot;

       for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){

         assert( pCsr->pNode==pRoot );

         rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);

         if( !isEof ){

           break;

         }

       }

       if( rc==SQLITE_OK && isEof ){

         assert( pCsr->pNode==pRoot );

         nodeRelease(pRtree, pRoot);

         pCsr->pNode = 0;

       }

       assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );

     }

   }

   rtreeRelease(pRtree);

   return rc;

 }

 /*

 ** Rtree virtual table module xBestIndex method. There are three

 ** table scan strategies to choose from (in order from most to 

 ** least desirable):

 **

 **   idxNum     idxStr        Strategy

 **   ------------------------------------------------

 **     1        Unused        Direct lookup by rowid.

 **     2        See below     R-tree query.

 **     3        Unused        Full table scan.

 **   ------------------------------------------------

 **

 ** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy

 ** 2 is used, idxStr is formatted to contain 2 bytes for each 

 ** constraint used. The first two bytes of idxStr correspond to 

 ** the constraint in sqlite3_index_info.aConstraintUsage[] with

 ** (argvIndex==1) etc.

 **

 ** The first of each pair of bytes in idxStr identifies the constraint

 ** operator as follows:

 **

 **   Operator    Byte Value

 **   ----------------------

 **      =        0x41 ('A')

 **     <=        0x42 ('B')

 **      <        0x43 ('C')

 **     >=        0x44 ('D')

 **      >        0x45 ('E')

 **   ----------------------

 **

 ** The second of each pair of bytes identifies the coordinate column

 ** to which the constraint applies. The leftmost coordinate column

 ** is 'a', the second from the left 'b' etc.

 */

 static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){

   int rc = SQLITE_OK;

   int ii, cCol;

   int iIdx = 0;

   char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];

   memset(zIdxStr, 0, sizeof(zIdxStr));

   assert( pIdxInfo->idxStr==0 );

   for(ii=0; ii<pIdxInfo->nConstraint; ii++){

     struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

     if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){

       /* We have an equality constraint on the rowid. Use strategy 1. */

       int jj;

       for(jj=0; jj<ii; jj++){

         pIdxInfo->aConstraintUsage[jj].argvIndex = 0;

         pIdxInfo->aConstraintUsage[jj].omit = 0;

       }

       pIdxInfo->idxNum = 1;

       pIdxInfo->aConstraintUsage[ii].argvIndex = 1;

       pIdxInfo->aConstraintUsage[jj].omit = 1;

       /* This strategy involves a two rowid lookups on an B-Tree structures

       ** and then a linear search of an R-Tree node. This should be 

       ** considered almost as quick as a direct rowid lookup (for which 

       ** sqlite uses an internal cost of 0.0).

       */ 

       pIdxInfo->estimatedCost = 10.0;

       return SQLITE_OK;

     }

     if( p->usable && p->iColumn>0 ){

       u8 op = 0;

       switch( p->op ){

         case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;

         case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;

         case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;

         case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;

         case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;

       }

       if( op ){

         /* Make sure this particular constraint has not been used before.

         ** If it has been used before, ignore it.

         **

         ** A <= or < can be used if there is a prior >= or >.

         ** A >= or > can be used if there is a prior < or <=.

         ** A <= or < is disqualified if there is a prior <=, <, or ==.

         ** A >= or > is disqualified if there is a prior >=, >, or ==.

         ** A == is disqualifed if there is any prior constraint.

         */

         int j, opmsk;

         static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };

         assert( compatible[RTREE_EQ & 7]==0 );

         assert( compatible[RTREE_LT & 7]==1 );

         assert( compatible[RTREE_LE & 7]==1 );

         assert( compatible[RTREE_GT & 7]==2 );

         assert( compatible[RTREE_GE & 7]==2 );

         cCol = p->iColumn - 1 + 'a';

         opmsk = compatible[op & 7];

         for(j=0; j<iIdx; j+=2){

           if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){

             op = 0;

             break;

           }

         }

       }

       if( op ){

         assert( iIdx<sizeof(zIdxStr)-1 );

         zIdxStr[iIdx++] = op;

         zIdxStr[iIdx++] = cCol;

         pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);

         pIdxInfo->aConstraintUsage[ii].omit = 1;

       }

     }

   }

   pIdxInfo->idxNum = 2;

   pIdxInfo->needToFreeIdxStr = 1;

   if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){

     return SQLITE_NOMEM;

   }

   assert( iIdx>=0 );

   pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));

   return rc;

 }

 /*

 ** Return the N-dimensional volumn of the cell stored in *p.

 */

 static float cellArea(Rtree *pRtree, RtreeCell *p){

   float area = 1.0;

   int ii;

   for(ii=0; ii<(pRtree->nDim*2); ii+=2){

     area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));

   }

   return area;

 }

 /*

 ** Return the margin length of cell p. The margin length is the sum

 ** of the objects size in each dimension.

 */

 static float cellMargin(Rtree *pRtree, RtreeCell *p){

   float margin = 0.0;

   int ii;

   for(ii=0; ii<(pRtree->nDim*2); ii+=2){

     margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));

   }

   return margin;

 }

 /*

 ** Store the union of cells p1 and p2 in p1.

 */

 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){

   int ii;

   if( pRtree->eCoordType==RTREE_COORD_REAL32 ){

     for(ii=0; ii<(pRtree->nDim*2); ii+=2){

       p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);

       p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);

     }

   }else{

     for(ii=0; ii<(pRtree->nDim*2); ii+=2){

       p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);

       p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);

     }

   }

 }

 /*

 ** Return true if the area covered by p2 is a subset of the area covered

 ** by p1. False otherwise.

 */

 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){

   int ii;

   int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);

   for(ii=0; ii<(pRtree->nDim*2); ii+=2){

     RtreeCoord *a1 = &p1->aCoord[ii];

     RtreeCoord *a2 = &p2->aCoord[ii];

     if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) 

      || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) 

     ){

       return 0;

     }

   }

   return 1;

 }

 /*

 ** Return the amount cell p would grow by if it were unioned with pCell.

 */

 static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){

   float area;

   RtreeCell cell;

   memcpy(&cell, p, sizeof(RtreeCell));

   area = cellArea(pRtree, &cell);

   cellUnion(pRtree, &cell, pCell);

   return (cellArea(pRtree, &cell)-area);

 }

 #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT

 static float cellOverlap(

   Rtree *pRtree, 

   RtreeCell *p, 

   RtreeCell *aCell, 

   int nCell, 

   int iExclude

 ){

   int ii;

   float overlap = 0.0;

   for(ii=0; ii<nCell; ii++){

     if( ii!=iExclude ){

       int jj;

       float o = 1.0;

       for(jj=0; jj<(pRtree->nDim*2); jj+=2){

         double x1;

         double x2;

         x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));

         x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));

         if( x2<x1 ){

           o = 0.0;

           break;

         }else{

           o = o * (x2-x1);

         }

       }

       overlap += o;

     }

   }

   return overlap;

 }

 #endif

 #if VARIANT_RSTARTREE_CHOOSESUBTREE

 static float cellOverlapEnlargement(

   Rtree *pRtree, 

   RtreeCell *p, 

   RtreeCell *pInsert, 

   RtreeCell *aCell, 

   int nCell, 

   int iExclude

 ){

   float before;

   float after;

   before = cellOverlap(pRtree, p, aCell, nCell, iExclude);

   cellUnion(pRtree, p, pInsert);

   after = cellOverlap(pRtree, p, aCell, nCell, iExclude);

   return after-before;

 }

 #endif

 /*

 ** This function implements the ChooseLeaf algorithm from Gutman[84].

 ** ChooseSubTree in r*tree terminology.

 */

 static int ChooseLeaf(

   Rtree *pRtree,               /* Rtree table */

   RtreeCell *pCell,            /* Cell to insert into rtree */

   int iHeight,                 /* Height of sub-tree rooted at pCell */

   RtreeNode **ppLeaf           /* OUT: Selected leaf page */

 ){

   int rc;

   int ii;

   RtreeNode *pNode;

   rc = nodeAcquire(pRtree, 1, 0, &pNode);

   for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){

     int iCell;

     sqlite3_int64 iBest;

     float fMinGrowth;

     float fMinArea;

     float fMinOverlap;

     int nCell = NCELL(pNode);

     RtreeCell cell;

     RtreeNode *pChild;

     RtreeCell *aCell = 0;

 #if VARIANT_RSTARTREE_CHOOSESUBTREE

     if( ii==(pRtree->iDepth-1) ){

       int jj;

       aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);

       if( !aCell ){

         rc = SQLITE_NOMEM;

         nodeRelease(pRtree, pNode);

         pNode = 0;

         continue;

       }

       for(jj=0; jj<nCell; jj++){

         nodeGetCell(pRtree, pNode, jj, &aCell[jj]);

       }

     }

 #endif

     /* Select the child node which will be enlarged the least if pCell

     ** is inserted into it. Resolve ties by choosing the entry with

     ** the smallest area.

     */

     for(iCell=0; iCell<nCell; iCell++){

       float growth;

       float area;

       float overlap = 0.0;

       nodeGetCell(pRtree, pNode, iCell, &cell);

       growth = cellGrowth(pRtree, &cell, pCell);

       area = cellArea(pRtree, &cell);

 #if VARIANT_RSTARTREE_CHOOSESUBTREE

       if( ii==(pRtree->iDepth-1) ){

         overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);

       }

 #endif

       if( (iCell==0) 

        || (overlap<fMinOverlap) 

        || (overlap==fMinOverlap && growth<fMinGrowth)

        || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)

       ){

         fMinOverlap = overlap;

         fMinGrowth = growth;

         fMinArea = area;

         iBest = cell.iRowid;

       }

     }

     sqlite3_free(aCell);

     rc = nodeAcquire(pRtree, iBest, pNode, &pChild);

     nodeRelease(pRtree, pNode);

     pNode = pChild;

   }

   *ppLeaf = pNode;

   return rc;

 }

 /*

 ** A cell with the same content as pCell has just been inserted into

 ** the node pNode. This function updates the bounding box cells in

 ** all ancestor elements.

 */

 static void AdjustTree(

   Rtree *pRtree,                    /* Rtree table */

   RtreeNode *pNode,                 /* Adjust ancestry of this node. */

   RtreeCell *pCell                  /* This cell was just inserted */

 ){

   RtreeNode *p = pNode;

   while( p->pParent ){

     RtreeCell cell;

     RtreeNode *pParent = p->pParent;

     int iCell = nodeParentIndex(pRtree, p);

     nodeGetCell(pRtree, pParent, iCell, &cell);

     if( !cellContains(pRtree, &cell, pCell) ){

       cellUnion(pRtree, &cell, pCell);

       nodeOverwriteCell(pRtree, pParent, &cell, iCell);

     }

     p = pParent;

   }

 }

 /*

 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.

 */

 static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){

   sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);

   sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);

   sqlite3_step(pRtree->pWriteRowid);

   return sqlite3_reset(pRtree->pWriteRowid);

 }

 /*

 ** Write mapping (iNode->iPar) to the <rtree>_parent table.

 */

 static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){

   sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);

   sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);

   sqlite3_step(pRtree->pWriteParent);

   return sqlite3_reset(pRtree->pWriteParent);

 }

 static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);

 #if VARIANT_GUTTMAN_LINEAR_SPLIT

 /*

 ** Implementation of the linear variant of the PickNext() function from

 ** Guttman[84].

 */

 static RtreeCell *LinearPickNext(

   Rtree *pRtree,

   RtreeCell *aCell, 

   int nCell, 

   RtreeCell *pLeftBox, 

   RtreeCell *pRightBox,

   int *aiUsed

 ){

   int ii;

   for(ii=0; aiUsed[ii]; ii++);

   aiUsed[ii] = 1;

   return &aCell[ii];

 }

 /*

 ** Implementation of the linear variant of the PickSeeds() function from

 ** Guttman[84].

 */

 static void LinearPickSeeds(

   Rtree *pRtree,

   RtreeCell *aCell, 

   int nCell, 

   int *piLeftSeed, 

   int *piRightSeed

 ){

   int i;

   int iLeftSeed = 0;

   int iRightSeed = 1;

   float maxNormalInnerWidth = 0.0;

   /* Pick two "seed" cells from the array of cells. The algorithm used

   ** here is the LinearPickSeeds algorithm from Gutman[1984]. The 

   ** indices of the two seed cells in the array are stored in local

   ** variables iLeftSeek and iRightSeed.

   */

   for(i=0; i<pRtree->nDim; i++){

     float x1 = aCell[0].aCoord[i*2];

     float x2 = aCell[0].aCoord[i*2+1];

     float x3 = x1;

     float x4 = x2;

     int jj;

     int iCellLeft = 0;

     int iCellRight = 0;

     for(jj=1; jj<nCell; jj++){

       float left = aCell[jj].aCoord[i*2];

       float right = aCell[jj].aCoord[i*2+1];

       if( left<x1 ) x1 = left;

       if( right>x4 ) x4 = right;

       if( left>x3 ){

         x3 = left;

         iCellRight = jj;

       }

       if( right<x2 ){

         x2 = right;

         iCellLeft = jj;

       }

     }

     if( x4!=x1 ){

       float normalwidth = (x3 - x2) / (x4 - x1);

       if( normalwidth>maxNormalInnerWidth ){

         iLeftSeed = iCellLeft;

         iRightSeed = iCellRight;

       }

     }

   }

   *piLeftSeed = iLeftSeed;

   *piRightSeed = iRightSeed;

 }

 #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */

 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT

 /*

 ** Implementation of the quadratic variant of the PickNext() function from

 ** Guttman[84].

 */

 static RtreeCell *QuadraticPickNext(

   Rtree *pRtree,

   RtreeCell *aCell, 

   int nCell, 

   RtreeCell *pLeftBox, 

   RtreeCell *pRightBox,

   int *aiUsed

 ){

   #define FABS(a) ((a)<0.0?-1.0*(a):(a))

   int iSelect = -1;

   float fDiff;

   int ii;

   for(ii=0; ii<nCell; ii++){

     if( aiUsed[ii]==0 ){

       float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);

       float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);

       float diff = FABS(right-left);

       if( iSelect<0 || diff>fDiff ){

         fDiff = diff;

         iSelect = ii;

       }

     }

   }

   aiUsed[iSelect] = 1;

   return &aCell[iSelect];

 }

 /*

 ** Implementation of the quadratic variant of the PickSeeds() function from

 ** Guttman[84].

 */

 static void QuadraticPickSeeds(

   Rtree *pRtree,

   RtreeCell *aCell, 

   int nCell, 

   int *piLeftSeed, 

   int *piRightSeed

 ){

   int ii;

   int jj;

   int iLeftSeed = 0;

   int iRightSeed = 1;

   float fWaste = 0.0;

   for(ii=0; ii<nCell; ii++){

     for(jj=ii+1; jj<nCell; jj++){

       float right = cellArea(pRtree, &aCell[jj]);

       float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);

       float waste = growth - right;

       if( waste>fWaste ){

         iLeftSeed = ii;

         iRightSeed = jj;

         fWaste = waste;

       }

     }

   }

   *piLeftSeed = iLeftSeed;

   *piRightSeed = iRightSeed;

 }

 #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */

 /*

 ** Arguments aIdx, aDistance and aSpare all point to arrays of size

 ** nIdx. The aIdx array contains the set of integers from 0 to 

 ** (nIdx-1) in no particular order. This function sorts the values

 ** in aIdx according to the indexed values in aDistance. For

 ** example, assuming the inputs:

 **

 **   aIdx      = { 0,   1,   2,   3 }

 **   aDistance = { 5.0, 2.0, 7.0, 6.0 }

 **

 ** this function sets the aIdx array to contain:

 **

 **   aIdx      = { 0,   1,   2,   3 }

 **

 ** The aSpare array is used as temporary working space by the

 ** sorting algorithm.

 */

 static void SortByDistance(

   int *aIdx, 

   int nIdx, 

   float *aDistance, 

   int *aSpare

 ){

   if( nIdx>1 ){

     int iLeft = 0;

     int iRight = 0;

     int nLeft = nIdx/2;

     int nRight = nIdx-nLeft;

     int *aLeft = aIdx;

     int *aRight = &aIdx[nLeft];

     SortByDistance(aLeft, nLeft, aDistance, aSpare);

     SortByDistance(aRight, nRight, aDistance, aSpare);

     memcpy(aSpare, aLeft, sizeof(int)*nLeft);

     aLeft = aSpare;

     while( iLeft<nLeft || iRight<nRight ){

       if( iLeft==nLeft ){

         aIdx[iLeft+iRight] = aRight[iRight];

         iRight++;

       }else if( iRight==nRight ){

         aIdx[iLeft+iRight] = aLeft[iLeft];

         iLeft++;

       }else{

         float fLeft = aDistance[aLeft[iLeft]];

         float fRight = aDistance[aRight[iRight]];

         if( fLeft<fRight ){

           aIdx[iLeft+iRight] = aLeft[iLeft];

           iLeft++;

         }else{

           aIdx[iLeft+iRight] = aRight[iRight];

           iRight++;

         }

       }

     }

 #if 0

     /* Check that the sort worked */

     {

       int jj;

       for(jj=1; jj<nIdx; jj++){

         float left = aDistance[aIdx[jj-1]];

         float right = aDistance[aIdx[jj]];

         assert( left<=right );

       }

     }

 #endif

   }

 }

 /*

 ** Arguments aIdx, aCell and aSpare all point to arrays of size

 ** nIdx. The aIdx array contains the set of integers from 0 to 

 ** (nIdx-1) in no particular order. This function sorts the values

 ** in aIdx according to dimension iDim of the cells in aCell. The

 ** minimum value of dimension iDim is considered first, the

 ** maximum used to break ties.

 **

 ** The aSpare array is used as temporary working space by the

 ** sorting algorithm.

 */

 static void SortByDimension(

   Rtree *pRtree,

   int *aIdx, 

   int nIdx, 

   int iDim, 

   RtreeCell *aCell, 

   int *aSpare

 ){

   if( nIdx>1 ){

     int iLeft = 0;

     int iRight = 0;

     int nLeft = nIdx/2;

     int nRight = nIdx-nLeft;

     int *aLeft = aIdx;

     int *aRight = &aIdx[nLeft];

     SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);

     SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);

     memcpy(aSpare, aLeft, sizeof(int)*nLeft);

     aLeft = aSpare;

     while( iLeft<nLeft || iRight<nRight ){

       double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);

       double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);

       double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);

       double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);

       if( (iLeft!=nLeft) && ((iRight==nRight)

        || (xleft1<xright1)

        || (xleft1==xright1 && xleft2<xright2)

       )){

         aIdx[iLeft+iRight] = aLeft[iLeft];

         iLeft++;

       }else{

         aIdx[iLeft+iRight] = aRight[iRight];

         iRight++;

       }

     }

 #if 0

     /* Check that the sort worked */

     {

       int jj;

       for(jj=1; jj<nIdx; jj++){

         float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];

         float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];

         float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];

         float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];

         assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );

       }

     }

 #endif

   }

 }

 #if VARIANT_RSTARTREE_SPLIT

 /*

 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].

 */

 static int splitNodeStartree(

   Rtree *pRtree,

   RtreeCell *aCell,

   int nCell,

   RtreeNode *pLeft,

   RtreeNode *pRight,

   RtreeCell *pBboxLeft,

   RtreeCell *pBboxRight

 ){

   int **aaSorted;

   int *aSpare;

   int ii;

   int iBestDim;

   int iBestSplit;

   float fBestMargin;

   int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));

   aaSorted = (int **)sqlite3_malloc(nByte);

   if( !aaSorted ){

     return SQLITE_NOMEM;

   }

   aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];

   memset(aaSorted, 0, nByte);

   for(ii=0; ii<pRtree->nDim; ii++){

     int jj;

     aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];

     for(jj=0; jj<nCell; jj++){

       aaSorted[ii][jj] = jj;

     }

     SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);

   }

   for(ii=0; ii<pRtree->nDim; ii++){

     float margin = 0.0;

     float fBestOverlap;

     float fBestArea;

     int iBestLeft;

     int nLeft;

     for(

       nLeft=RTREE_MINCELLS(pRtree); 

       nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 

       nLeft++

     ){

       RtreeCell left;

       RtreeCell right;

       int kk;

       float overlap;

       float area;

       memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));

       memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));

       for(kk=1; kk<(nCell-1); kk++){

         if( kk<nLeft ){

           cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);

         }else{

           cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);

         }

       }

       margin += cellMargin(pRtree, &left);

       margin += cellMargin(pRtree, &right);

       overlap = cellOverlap(pRtree, &left, &right, 1, -1);

       area = cellArea(pRtree, &left) + cellArea(pRtree, &right);

       if( (nLeft==RTREE_MINCELLS(pRtree))

        || (overlap<fBestOverlap)

        || (overlap==fBestOverlap && area<fBestArea)

       ){

         iBestLeft = nLeft;

         fBestOverlap = overlap;

         fBestArea = area;

       }

     }

     if( ii==0 || margin<fBestMargin ){

       iBestDim = ii;

       fBestMargin = margin;

       iBestSplit = iBestLeft;

     }

   }

   memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));

   memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));

   for(ii=0; ii<nCell; ii++){

     RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;

     RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;

     RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];

     nodeInsertCell(pRtree, pTarget, pCell);

     cellUnion(pRtree, pBbox, pCell);

   }

   sqlite3_free(aaSorted);

   return SQLITE_OK;

 }

 #endif

 #if VARIANT_GUTTMAN_SPLIT

 /*

 ** Implementation of the regular R-tree SplitNode from Guttman[1984].

 */

 static int splitNodeGuttman(

   Rtree *pRtree,

   RtreeCell *aCell,

   int nCell,

   RtreeNode *pLeft,

   RtreeNode *pRight,

   RtreeCell *pBboxLeft,

   RtreeCell *pBboxRight

 ){

   int iLeftSeed = 0;

   int iRightSeed = 1;

   int *aiUsed;

   int i;

   aiUsed = sqlite3_malloc(sizeof(int)*nCell);

   memset(aiUsed, 0, sizeof(int)*nCell);

   PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);

   memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));

   memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));

   nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);

   nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);

   aiUsed[iLeftSeed] = 1;

   aiUsed[iRightSeed] = 1;

   for(i=nCell-2; i>0; i--){

     RtreeCell *pNext;

     pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);

     float diff =  

       cellGrowth(pRtree, pBboxLeft, pNext) - 

       cellGrowth(pRtree, pBboxRight, pNext)

     ;

     if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)

      || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))

     ){

       nodeInsertCell(pRtree, pRight, pNext);

       cellUnion(pRtree, pBboxRight, pNext);

     }else{

       nodeInsertCell(pRtree, pLeft, pNext);

       cellUnion(pRtree, pBboxLeft, pNext);

     }

   }

   sqlite3_free(aiUsed);

   return SQLITE_OK;

 }

 #endif

 static int updateMapping(

   Rtree *pRtree, 

   i64 iRowid, 

   RtreeNode *pNode, 

   int iHeight

 ){

   int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);

   xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);

   if( iHeight>0 ){

     RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);

     if( pChild ){

       nodeRelease(pRtree, pChild->pParent);

       nodeReference(pNode);

       pChild->pParent = pNode;

     }

   }

   return xSetMapping(pRtree, iRowid, pNode->iNode);

 }

 static int SplitNode(

   Rtree *pRtree,

   RtreeNode *pNode,

   RtreeCell *pCell,

   int iHeight

 ){

   int i;

   int newCellIsRight = 0;

   int rc = SQLITE_OK;

   int nCell = NCELL(pNode);

   RtreeCell *aCell;

   int *aiUsed;

   RtreeNode *pLeft = 0;

   RtreeNode *pRight = 0;

   RtreeCell leftbbox;

   RtreeCell rightbbox;

   /* Allocate an array and populate it with a copy of pCell and 

   ** all cells from node pLeft. Then zero the original node.

   */

   aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));

   if( !aCell ){

     rc = SQLITE_NOMEM;

     goto splitnode_out;

   }

   aiUsed = (int *)&aCell[nCell+1];

   memset(aiUsed, 0, sizeof(int)*(nCell+1));

   for(i=0; i<nCell; i++){

     nodeGetCell(pRtree, pNode, i, &aCell[i]);

   }

   nodeZero(pRtree, pNode);

   memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));

   nCell++;

   if( pNode->iNode==1 ){

     pRight = nodeNew(pRtree, pNode, 1);

     pLeft = nodeNew(pRtree, pNode, 1);

     pRtree->iDepth++;

     pNode->isDirty = 1;

     writeInt16(pNode->zData, pRtree->iDepth);

   }else{

     pLeft = pNode;

     pRight = nodeNew(pRtree, pLeft->pParent, 1);

     nodeReference(pLeft);

   }

   if( !pLeft || !pRight ){

     rc = SQLITE_NOMEM;

     goto splitnode_out;

   }

   memset(pLeft->zData, 0, pRtree->iNodeSize);

   memset(pRight->zData, 0, pRtree->iNodeSize);

   rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);

   if( rc!=SQLITE_OK ){

     goto splitnode_out;

   }

   /* Ensure both child nodes have node numbers assigned to them. */

   if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))

    || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))

   ){

     goto splitnode_out;

   }

   rightbbox.iRowid = pRight->iNode;

   leftbbox.iRowid = pLeft->iNode;

   if( pNode->iNode==1 ){

     rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);

     if( rc!=SQLITE_OK ){

       goto splitnode_out;

     }

   }else{

     RtreeNode *pParent = pLeft->pParent;

     int iCell = nodeParentIndex(pRtree, pLeft);

     nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);

     AdjustTree(pRtree, pParent, &leftbbox);

   }

   if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){

     goto splitnode_out;

   }

   for(i=0; i<NCELL(pRight); i++){

     i64 iRowid = nodeGetRowid(pRtree, pRight, i);

     rc = updateMapping(pRtree, iRowid, pRight, iHeight);

     if( iRowid==pCell->iRowid ){

       newCellIsRight = 1;

     }

     if( rc!=SQLITE_OK ){

       goto splitnode_out;

     }

   }

   if( pNode->iNode==1 ){

     for(i=0; i<NCELL(pLeft); i++){

       i64 iRowid = nodeGetRowid(pRtree, pLeft, i);

       rc = updateMapping(pRtree, iRowid, pLeft, iHeight);

       if( rc!=SQLITE_OK ){

         goto splitnode_out;

       }

     }

   }else if( newCellIsRight==0 ){

     rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);

   }

   if( rc==SQLITE_OK ){

     rc = nodeRelease(pRtree, pRight);

     pRight = 0;

   }

   if( rc==SQLITE_OK ){

     rc = nodeRelease(pRtree, pLeft);

     pLeft = 0;

   }

 splitnode_out:

   nodeRelease(pRtree, pRight);

   nodeRelease(pRtree, pLeft);

   sqlite3_free(aCell);

   return rc;

 }

 static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){

   int rc = SQLITE_OK;

   if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){

     sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);

     if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){

       i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);

       rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);

     }else{

       rc = SQLITE_ERROR;

     }

     sqlite3_reset(pRtree->pReadParent);

     if( rc==SQLITE_OK ){

       rc = fixLeafParent(pRtree, pLeaf->pParent);

     }

   }

   return rc;

 }

 static int deleteCell(Rtree *, RtreeNode *, int, int);

 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){

   int rc;

   RtreeNode *pParent;

   int iCell;

   assert( pNode->nRef==1 );

   /* Remove the entry in the parent cell. */

   iCell = nodeParentIndex(pRtree, pNode);

   pParent = pNode->pParent;

   pNode->pParent = 0;

   if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1)) 

    || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))

   ){

     return rc;

   }

   /* Remove the xxx_node entry. */

   sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);

   sqlite3_step(pRtree->pDeleteNode);

   if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){

     return rc;

   }

   /* Remove the xxx_parent entry. */

   sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);

   sqlite3_step(pRtree->pDeleteParent);

   if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){

     return rc;

   }

   /* Remove the node from the in-memory hash table and link it into

   ** the Rtree.pDeleted list. Its contents will be re-inserted later on.

   */

   nodeHashDelete(pRtree, pNode);

   pNode->iNode = iHeight;

   pNode->pNext = pRtree->pDeleted;

   pNode->nRef++;

   pRtree->pDeleted = pNode;

   return SQLITE_OK;

 }

 static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){

   RtreeNode *pParent = pNode->pParent;

   if( pParent ){

     int ii; 

     int nCell = NCELL(pNode);

     RtreeCell box;                            /* Bounding box for pNode */

     nodeGetCell(pRtree, pNode, 0, &box);

     for(ii=1; ii<nCell; ii++){

       RtreeCell cell;

       nodeGetCell(pRtree, pNode, ii, &cell);

       cellUnion(pRtree, &box, &cell);

     }

     box.iRowid = pNode->iNode;

     ii = nodeParentIndex(pRtree, pNode);

     nodeOverwriteCell(pRtree, pParent, &box, ii);

     fixBoundingBox(pRtree, pParent);

   }

 }

 /*

 ** Delete the cell at index iCell of node pNode. After removing the

 ** cell, adjust the r-tree data structure if required.

 */

 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){

   int rc;

   if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){

     return rc;

   }

   /* Remove the cell from the node. This call just moves bytes around

   ** the in-memory node image, so it cannot fail.

   */

   nodeDeleteCell(pRtree, pNode, iCell);

   /* If the node is not the tree root and now has less than the minimum

   ** number of cells, remove it from the tree. Otherwise, update the

   ** cell in the parent node so that it tightly contains the updated

   ** node.

   */

   if( pNode->iNode!=1 ){

     RtreeNode *pParent = pNode->pParent;

     if( (pParent->iNode!=1 || NCELL(pParent)!=1) 

      && (NCELL(pNode)<RTREE_MINCELLS(pRtree))

     ){

       rc = removeNode(pRtree, pNode, iHeight);

     }else{

       fixBoundingBox(pRtree, pNode);

     }

   }

   return rc;

 }

 static int Reinsert(

   Rtree *pRtree, 

   RtreeNode *pNode, 

   RtreeCell *pCell, 

   int iHeight

 ){

   int *aOrder;

   int *aSpare;

   RtreeCell *aCell;

   float *aDistance;

   int nCell;

   float aCenterCoord[RTREE_MAX_DIMENSIONS];

   int iDim;

   int ii;

   int rc = SQLITE_OK;

   memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);

   nCell = NCELL(pNode)+1;

   /* Allocate the buffers used by this operation. The allocation is

   ** relinquished before this function returns.

   */

   aCell = (RtreeCell *)sqlite3_malloc(nCell * (

     sizeof(RtreeCell) +         /* aCell array */

     sizeof(int)       +         /* aOrder array */

     sizeof(int)       +         /* aSpare array */

     sizeof(float)               /* aDistance array */

   ));

   if( !aCell ){

     return SQLITE_NOMEM;

   }

   aOrder    = (int *)&aCell[nCell];

   aSpare    = (int *)&aOrder[nCell];

   aDistance = (float *)&aSpare[nCell];

   for(ii=0; ii<nCell; ii++){

     if( ii==(nCell-1) ){

       memcpy(&aCell[ii], pCell, sizeof(RtreeCell));

     }else{

       nodeGetCell(pRtree, pNode, ii, &aCell[ii]);

     }

     aOrder[ii] = ii;

     for(iDim=0; iDim<pRtree->nDim; iDim++){

       aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]);

       aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]);

     }

   }

   for(iDim=0; iDim<pRtree->nDim; iDim++){

     aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);

   }

   for(ii=0; ii<nCell; ii++){

     aDistance[ii] = 0.0;

     for(iDim=0; iDim<pRtree->nDim; iDim++){

       float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) - 

           DCOORD(aCell[ii].aCoord[iDim*2]);

       aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);

     }

   }

   SortByDistance(aOrder, nCell, aDistance, aSpare);

   nodeZero(pRtree, pNode);

   for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){

     RtreeCell *p = &aCell[aOrder[ii]];

     nodeInsertCell(pRtree, pNode, p);

     if( p->iRowid==pCell->iRowid ){

       if( iHeight==0 ){

         rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);

       }else{

         rc = parentWrite(pRtree, p->iRowid, pNode->iNode);

       }

     }

   }

   if( rc==SQLITE_OK ){

     fixBoundingBox(pRtree, pNode);

   }

   for(; rc==SQLITE_OK && ii<nCell; ii++){

     /* Find a node to store this cell in. pNode->iNode currently contains

     ** the height of the sub-tree headed by the cell.

     */

     RtreeNode *pInsert;

     RtreeCell *p = &aCell[aOrder[ii]];

     rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);

     if( rc==SQLITE_OK ){

       int rc2;

       rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);

       rc2 = nodeRelease(pRtree, pInsert);

       if( rc==SQLITE_OK ){

         rc = rc2;

       }

     }

   }

   sqlite3_free(aCell);

   return rc;

 }

 /*

 ** Insert cell pCell into node pNode. Node pNode is the head of a 

 ** subtree iHeight high (leaf nodes have iHeight==0).

 */

 static int rtreeInsertCell(

   Rtree *pRtree,

   RtreeNode *pNode,

   RtreeCell *pCell,

   int iHeight

 ){

   int rc = SQLITE_OK;

   if( iHeight>0 ){

     RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);

     if( pChild ){

       nodeRelease(pRtree, pChild->pParent);

       nodeReference(pNode);

       pChild->pParent = pNode;

     }

   }

   if( nodeInsertCell(pRtree, pNode, pCell) ){

 #if VARIANT_RSTARTREE_REINSERT

     if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){

       rc = SplitNode(pRtree, pNode, pCell, iHeight);

     }else{

       pRtree->iReinsertHeight = iHeight;

       rc = Reinsert(pRtree, pNode, pCell, iHeight);

     }

 #else

     rc = SplitNode(pRtree, pNode, pCell, iHeight);

 #endif

   }else{

     AdjustTree(pRtree, pNode, pCell);

     if( iHeight==0 ){

       rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);

     }else{

       rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);

     }

   }

   return rc;

 }

 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){

   int ii;

   int rc = SQLITE_OK;

   int nCell = NCELL(pNode);

   for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){

     RtreeNode *pInsert;

     RtreeCell cell;

     nodeGetCell(pRtree, pNode, ii, &cell);

     /* Find a node to store this cell in. pNode->iNode currently contains

     ** the height of the sub-tree headed by the cell.

     */

     rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);

     if( rc==SQLITE_OK ){

       int rc2;

       rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);

       rc2 = nodeRelease(pRtree, pInsert);

       if( rc==SQLITE_OK ){

         rc = rc2;

       }

     }

   }

   return rc;

 }

 /*

 ** Select a currently unused rowid for a new r-tree record.

 */

 static int newRowid(Rtree *pRtree, i64 *piRowid){

   int rc;

   sqlite3_bind_null(pRtree->pWriteRowid, 1);

   sqlite3_bind_null(pRtree->pWriteRowid, 2);

   sqlite3_step(pRtree->pWriteRowid);

   rc = sqlite3_reset(pRtree->pWriteRowid);

   *piRowid = sqlite3_last_insert_rowid(pRtree->db);

   return rc;

 }

 #ifndef NDEBUG

 static int hashIsEmpty(Rtree *pRtree){

   int ii;

   for(ii=0; ii<HASHSIZE; ii++){

     assert( !pRtree->aHash[ii] );

   }

   return 1;

 }

 #endif

 /*

 ** The xUpdate method for rtree module virtual tables.

 */

 int rtreeUpdate(

   sqlite3_vtab *pVtab, 

   int nData, 

   sqlite3_value **azData, 

   sqlite_int64 *pRowid

 ){

   Rtree *pRtree = (Rtree *)pVtab;

   int rc = SQLITE_OK;

   rtreeReference(pRtree);

   assert(nData>=1);

   assert(hashIsEmpty(pRtree));

   /* If azData[0] is not an SQL NULL value, it is the rowid of a

   ** record to delete from the r-tree table. The following block does

   ** just that.

   */

   if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){

     i64 iDelete;                /* The rowid to delete */

     RtreeNode *pLeaf;           /* Leaf node containing record iDelete */

     int iCell;                  /* Index of iDelete cell in pLeaf */

     RtreeNode *pRoot;

     /* Obtain a reference to the root node to initialise Rtree.iDepth */

     rc = nodeAcquire(pRtree, 1, 0, &pRoot);

     /* Obtain a reference to the leaf node that contains the entry 

     ** about to be deleted. 

     */

     if( rc==SQLITE_OK ){

       iDelete = sqlite3_value_int64(azData[0]);

       rc = findLeafNode(pRtree, iDelete, &pLeaf);

     }

     /* Delete the cell in question from the leaf node. */

     if( rc==SQLITE_OK ){

       int rc2;

       iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);

       rc = deleteCell(pRtree, pLeaf, iCell, 0);

       rc2 = nodeRelease(pRtree, pLeaf);

       if( rc==SQLITE_OK ){

         rc = rc2;

       }

     }

     /* Delete the corresponding entry in the <rtree>_rowid table. */

     if( rc==SQLITE_OK ){

       sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);

       sqlite3_step(pRtree->pDeleteRowid);

       rc = sqlite3_reset(pRtree->pDeleteRowid);

     }

     /* Check if the root node now has exactly one child. If so, remove

     ** it, schedule the contents of the child for reinsertion and 

     ** reduce the tree height by one.

     **

     ** This is equivalent to copying the contents of the child into

     ** the root node (the operation that Gutman's paper says to perform 

     ** in this scenario).

     */

     if( rc==SQLITE_OK && pRtree->iDepth>0 ){

       if( rc==SQLITE_OK && NCELL(pRoot)==1 ){

         RtreeNode *pChild;

         i64 iChild = nodeGetRowid(pRtree, pRoot, 0);

         rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);

         if( rc==SQLITE_OK ){

           rc = removeNode(pRtree, pChild, pRtree->iDepth-1);

         }

         if( rc==SQLITE_OK ){

           pRtree->iDepth--;

           writeInt16(pRoot->zData, pRtree->iDepth);

           pRoot->isDirty = 1;

         }

       }

     }

     /* Re-insert the contents of any underfull nodes removed from the tree. */

     for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){

       if( rc==SQLITE_OK ){

         rc = reinsertNodeContent(pRtree, pLeaf);

       }

       pRtree->pDeleted = pLeaf->pNext;

       sqlite3_free(pLeaf);

     }

     /* Release the reference to the root node. */

     if( rc==SQLITE_OK ){

       rc = nodeRelease(pRtree, pRoot);

     }else{

       nodeRelease(pRtree, pRoot);

     }

   }

   /* If the azData[] array contains more than one element, elements

   ** (azData[2]..azData[argc-1]) contain a new record to insert into

   ** the r-tree structure.

   */

   if( rc==SQLITE_OK && nData>1 ){

     /* Insert a new record into the r-tree */

     RtreeCell cell;

     int ii;

     RtreeNode *pLeaf;

     /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */

     assert( nData==(pRtree->nDim*2 + 3) );

     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){

       for(ii=0; ii<(pRtree->nDim*2); ii+=2){

         cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);

         cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);

         if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){

           rc = SQLITE_CONSTRAINT;

           goto constraint;

         }

       }

     }else{

       for(ii=0; ii<(pRtree->nDim*2); ii+=2){

         cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);

         cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);

         if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){

           rc = SQLITE_CONSTRAINT;

           goto constraint;

         }

       }

     }

     /* Figure out the rowid of the new row. */

     if( sqlite3_value_type(azData[2])==SQLITE_NULL ){

       rc = newRowid(pRtree, &cell.iRowid);

     }else{

       cell.iRowid = sqlite3_value_int64(azData[2]);

       sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);

       if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){

         sqlite3_reset(pRtree->pReadRowid);

         rc = SQLITE_CONSTRAINT;

         goto constraint;

       }

       rc = sqlite3_reset(pRtree->pReadRowid);

     }

     if( rc==SQLITE_OK ){

       rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);

     }

     if( rc==SQLITE_OK ){

       int rc2;

       pRtree->iReinsertHeight = -1;

       rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);

       rc2 = nodeRelease(pRtree, pLeaf);

       if( rc==SQLITE_OK ){

         rc = rc2;

       }

     }

   }

 constraint:

   rtreeRelease(pRtree);

   return rc;

 }

 /*

 ** The xRename method for rtree module virtual tables.

 */

 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){

   Rtree *pRtree = (Rtree *)pVtab;

   int rc = SQLITE_NOMEM;

   char *zSql = sqlite3_mprintf(

     "ALTER TABLE %Q.'%q_node'   RENAME TO \"%w_node\";"

     "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"

     "ALTER TABLE %Q.'%q_rowid'  RENAME TO \"%w_rowid\";"

     , pRtree->zDb, pRtree->zName, zNewName 

     , pRtree->zDb, pRtree->zName, zNewName 

     , pRtree->zDb, pRtree->zName, zNewName

   );

   if( zSql ){

     rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);

     sqlite3_free(zSql);

   }

   return rc;

 }

 static sqlite3_module rtreeModule = {

   0,                         /* iVersion */

   rtreeCreate,                /* xCreate - create a table */

   rtreeConnect,               /* xConnect - connect to an existing table */

   rtreeBestIndex,             /* xBestIndex - Determine search strategy */

   rtreeDisconnect,            /* xDisconnect - Disconnect from a table */

   rtreeDestroy,               /* xDestroy - Drop a table */

   rtreeOpen,                  /* xOpen - open a cursor */

   rtreeClose,                 /* xClose - close a cursor */

   rtreeFilter,                /* xFilter - configure scan constraints */

   rtreeNext,                  /* xNext - advance a cursor */

   rtreeEof,                   /* xEof */

   rtreeColumn,                /* xColumn - read data */

   rtreeRowid,                 /* xRowid - read data */

   rtreeUpdate,                /* xUpdate - write data */

   0,                          /* xBegin - begin transaction */

   0,                          /* xSync - sync transaction */

   0,                          /* xCommit - commit transaction */

   0,                          /* xRollback - rollback transaction */

   0,                          /* xFindFunction - function overloading */

   rtreeRename                 /* xRename - rename the table */

 };

 static int rtreeSqlInit(

   Rtree *pRtree, 

   sqlite3 *db, 

   const char *zDb, 

   const char *zPrefix, 

   int isCreate

 ){

   int rc = SQLITE_OK;

   #define N_STATEMENT 9

   static const char *azSql[N_STATEMENT] = {

     /* Read and write the xxx_node table */

     "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",

     "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",

     "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",

     /* Read and write the xxx_rowid table */

     "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",

     "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",

     "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",

     /* Read and write the xxx_parent table */

     "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",

     "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",

     "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"

   };

   sqlite3_stmt **appStmt[N_STATEMENT];

   int i;

   pRtree->db = db;

   if( isCreate ){

     char *zCreate = sqlite3_mprintf(

 "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"

 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"

 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"

 "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",

       zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize

     );

     if( !zCreate ){

       return SQLITE_NOMEM;

     }

     rc = sqlite3_exec(db, zCreate, 0, 0, 0);

     sqlite3_free(zCreate);

     if( rc!=SQLITE_OK ){

       return rc;

     }

   }

   appStmt[0] = &pRtree->pReadNode;

   appStmt[1] = &pRtree->pWriteNode;

   appStmt[2] = &pRtree->pDeleteNode;

   appStmt[3] = &pRtree->pReadRowid;

   appStmt[4] = &pRtree->pWriteRowid;

   appStmt[5] = &pRtree->pDeleteRowid;

   appStmt[6] = &pRtree->pReadParent;

   appStmt[7] = &pRtree->pWriteParent;

   appStmt[8] = &pRtree->pDeleteParent;

   for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){

     char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);

     if( zSql ){

       rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); 

     }else{

       rc = SQLITE_NOMEM;

     }

     sqlite3_free(zSql);

   }

   return rc;

 }

 /*

 ** This routine queries database handle db for the page-size used by

 ** database zDb. If successful, the page-size in bytes is written to

 ** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error 

 ** code is returned.

 */

 static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){

   int rc = SQLITE_NOMEM;

   char *zSql;

   sqlite3_stmt *pStmt = 0;

   zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb);

   if( !zSql ){

     return SQLITE_NOMEM;

   }

   rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);

   sqlite3_free(zSql);

   if( rc!=SQLITE_OK ){

     return rc;

   }

   if( SQLITE_ROW==sqlite3_step(pStmt) ){

     *piPageSize = sqlite3_column_int(pStmt, 0);

   }

   return sqlite3_finalize(pStmt);

 }

 /* 

 ** This function is the implementation of both the xConnect and xCreate

 ** methods of the r-tree virtual table.

 **

 **   argv[0]   -> module name

 **   argv[1]   -> database name

 **   argv[2]   -> table name

 **   argv[...] -> column names...

 */

 static int rtreeInit(

   sqlite3 *db,                        /* Database connection */