text: /*
  ** 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.
  */
  
  /*
  ** Database Format of R-Tree Tables
  ** --------------------------------
  **
  ** The data structure for a single virtual r-tree table is stored in three 
  ** native SQLite tables declared as follows. In each case, the '%' character
  ** in the table name is replaced with the user-supplied name of the r-tree
  ** table.
  **
  **   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
  **   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
  **   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
  **
  ** The data for each node of the r-tree structure is stored in the %_node
  ** table. For each node that is not the root node of the r-tree, there is
  ** an entry in the %_parent table associating the node with its parent.
  ** And for each row of data in the table, there is an entry in the %_rowid
  ** table that maps from the entries rowid to the id of the node that it
  ** is stored on.  If the r-tree contains auxiliary columns, those are stored
  ** on the end of the %_rowid table.
  **
  ** The root node of an r-tree always exists, even if the r-tree table is
  ** empty. The nodeno of the root node is always 1. All other nodes in the
  ** table must be the same size as the root node. The content of each node
  ** is formatted as follows:
  **
  **   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.
  */
  
  #if !defined(SQLITE_CORE) \
    || (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE))
  
  #ifndef SQLITE_CORE
    #include "sqlite3ext.h"
    SQLITE_EXTENSION_INIT1
  #else
    #include "sqlite3.h"
  #endif
  int sqlite3GetToken(const unsigned char*,int*); /* In the SQLite core */
  
  /*
  ** If building separately, we will need some setup that is normally
  ** found in sqliteInt.h
  */
  #if !defined(SQLITE_AMALGAMATION)
  #include "sqlite3rtree.h"
  typedef sqlite3_int64 i64;
  typedef sqlite3_uint64 u64;
  typedef unsigned char u8;
  typedef unsigned short u16;
  typedef unsigned int u32;
  #if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
  # define NDEBUG 1
  #endif
  #if defined(NDEBUG) && defined(SQLITE_DEBUG)
  # undef NDEBUG
  #endif
  #if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST)
  # define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1
  #endif
  #if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
  # define ALWAYS(X)      (1)
  # define NEVER(X)       (0)
  #elif !defined(NDEBUG)
  # define ALWAYS(X)      ((X)?1:(assert(0),0))
  # define NEVER(X)       ((X)?(assert(0),1):0)
  #else
  # define ALWAYS(X)      (X)
  # define NEVER(X)       (X)
  #endif
  #endif /* !defined(SQLITE_AMALGAMATION) */
  
  #include <string.h>
  #include <stdio.h>
  #include <assert.h>
  #include <stdlib.h>
  
  /*  The following macro is used to suppress compiler warnings.
  */
  #ifndef UNUSED_PARAMETER
  # define UNUSED_PARAMETER(x) (void)(x)
  #endif
  
  typedef struct Rtree Rtree;
  typedef struct RtreeCursor RtreeCursor;
  typedef struct RtreeNode RtreeNode;
  typedef struct RtreeCell RtreeCell;
  typedef struct RtreeConstraint RtreeConstraint;
  typedef struct RtreeMatchArg RtreeMatchArg;
  typedef struct RtreeGeomCallback RtreeGeomCallback;
  typedef union RtreeCoord RtreeCoord;
  typedef struct RtreeSearchPoint RtreeSearchPoint;
  
  /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
  #define RTREE_MAX_DIMENSIONS 5
  
  /* Maximum number of auxiliary columns */
  #define RTREE_MAX_AUX_COLUMN 100
  
  /* 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 97
  
  /* The xBestIndex method of this virtual table requires an estimate of
  ** the number of rows in the virtual table to calculate the costs of
  ** various strategies. If possible, this estimate is loaded from the
  ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
  ** Otherwise, if no sqlite_stat1 entry is available, use 
  ** RTREE_DEFAULT_ROWEST.
  */
  #define RTREE_DEFAULT_ROWEST 1048576
  #define RTREE_MIN_ROWEST         100
  
  /* 
  ** An rtree virtual-table object.
  */
  struct Rtree {
    sqlite3_vtab base;          /* Base class.  Must be first */
    sqlite3 *db;                /* Host database connection */
    int iNodeSize;              /* Size in bytes of each node in the node table */
    u8 nDim;                    /* Number of dimensions */
    u8 nDim2;                   /* Twice the number of dimensions */
    u8 eCoordType;              /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
    u8 nBytesPerCell;           /* Bytes consumed per cell */
    u8 inWrTrans;               /* True if inside write transaction */
    u8 nAux;                    /* # of auxiliary columns in %_rowid */
  #ifdef SQLITE_ENABLE_GEOPOLY
    u8 nAuxNotNull;             /* Number of initial not-null aux columns */
  #endif
  #ifdef SQLITE_DEBUG
    u8 bCorrupt;                /* Shadow table corruption detected */
  #endif
    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 */ 
    u32 nBusy;                  /* Current number of users of this structure */
    i64 nRowEst;                /* Estimated number of rows in this table */
    u32 nCursor;                /* Number of open cursors */
    u32 nNodeRef;               /* Number RtreeNodes with positive nRef */
    char *zReadAuxSql;          /* SQL for statement to read aux data */
  
    /* 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 */
  
    /* Blob I/O on xxx_node */
    sqlite3_blob *pNodeBlob;
  
    /* Statements to read/write/delete a record from xxx_node */
    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;
  
    /* Statement for writing to the "aux:" fields, if there are any */
    sqlite3_stmt *pWriteAux;
  
    RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
  };
  
  /* Possible values for Rtree.eCoordType: */
  #define RTREE_COORD_REAL32 0
  #define RTREE_COORD_INT32  1
  
  /*
  ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
  ** only deal with integer coordinates.  No floating point operations
  ** will be done.
  */
  #ifdef SQLITE_RTREE_INT_ONLY
    typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
    typedef int RtreeValue;                  /* Low accuracy coordinate */
  # define RTREE_ZERO 0
  #else
    typedef double RtreeDValue;              /* High accuracy coordinate */
    typedef float RtreeValue;                /* Low accuracy coordinate */
  # define RTREE_ZERO 0.0
  #endif
  
  /*
  ** Set the Rtree.bCorrupt flag
  */
  #ifdef SQLITE_DEBUG
  # define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1)
  #else
  # define RTREE_IS_CORRUPT(X)
  #endif
  
  /*
  ** When doing a search of an r-tree, instances of the following structure
  ** record intermediate results from the tree walk.
  **
  ** The id is always a node-id.  For iLevel>=1 the id is the node-id of
  ** the node that the RtreeSearchPoint represents.  When iLevel==0, however,
  ** the id is of the parent node and the cell that RtreeSearchPoint
  ** represents is the iCell-th entry in the parent node.
  */
  struct RtreeSearchPoint {
    RtreeDValue rScore;    /* The score for this node.  Smallest goes first. */
    sqlite3_int64 id;      /* Node ID */
    u8 iLevel;             /* 0=entries.  1=leaf node.  2+ for higher */
    u8 eWithin;            /* PARTLY_WITHIN or FULLY_WITHIN */
    u8 iCell;              /* Cell index within the node */
  };
  
  /*
  ** 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
  
  /*
  ** The smallest possible node-size is (512-64)==448 bytes. And the largest
  ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
  ** Therefore all non-root nodes must contain at least 3 entries. Since 
  ** 3^40 is greater than 2^64, an r-tree structure always has a depth of
  ** 40 or less.
  */
  #define RTREE_MAX_DEPTH 40
  
  
  /*
  ** Number of entries in the cursor RtreeNode cache.  The first entry is
  ** used to cache the RtreeNode for RtreeCursor.sPoint.  The remaining
  ** entries cache the RtreeNode for the first elements of the priority queue.
  */
  #define RTREE_CACHE_SZ  5
  
  /* 
  ** An rtree cursor object.
  */
  struct RtreeCursor {
    sqlite3_vtab_cursor base;         /* Base class.  Must be first */
    u8 atEOF;                         /* True if at end of search */
    u8 bPoint;                        /* True if sPoint is valid */
    u8 bAuxValid;                     /* True if pReadAux is valid */
    int iStrategy;                    /* Copy of idxNum search parameter */
    int nConstraint;                  /* Number of entries in aConstraint */
    RtreeConstraint *aConstraint;     /* Search constraints. */
    int nPointAlloc;                  /* Number of slots allocated for aPoint[] */
    int nPoint;                       /* Number of slots used in aPoint[] */
    int mxLevel;                      /* iLevel value for root of the tree */
    RtreeSearchPoint *aPoint;         /* Priority queue for search points */
    sqlite3_stmt *pReadAux;           /* Statement to read aux-data */
    RtreeSearchPoint sPoint;          /* Cached next search point */
    RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
    u32 anQueue[RTREE_MAX_DEPTH+1];   /* Number of queued entries by iLevel */
  };
  
  /* Return the Rtree of a RtreeCursor */
  #define RTREE_OF_CURSOR(X)   ((Rtree*)((X)->base.pVtab))
  
  /*
  ** A coordinate can be either a floating point number or a integer.  All
  ** coordinates within a single R-Tree are always of the same time.
  */
  union RtreeCoord {
    RtreeValue f;      /* Floating point value */
    int i;             /* Integer value */
    u32 u;             /* Unsigned for byte-order conversions */
  };
  
  /*
  ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
  ** formatted as a RtreeDValue (double or int64). This macro assumes that local
  ** variable pRtree points to the Rtree structure associated with the
  ** RtreeCoord.
  */
  #ifdef SQLITE_RTREE_INT_ONLY
  # define DCOORD(coord) ((RtreeDValue)coord.i)
  #else
  # define DCOORD(coord) (                           \
      (pRtree->eCoordType==RTREE_COORD_REAL32) ?      \
        ((double)coord.f) :                           \
        ((double)coord.i)                             \
    )
  #endif
  
  /*
  ** A search constraint.
  */
  struct RtreeConstraint {
    int iCoord;                     /* Index of constrained coordinate */
    int op;                         /* Constraining operation */
    union {
      RtreeDValue rValue;             /* Constraint value. */
      int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
      int (*xQueryFunc)(sqlite3_rtree_query_info*);
    } u;
    sqlite3_rtree_query_info *pInfo;  /* xGeom and xQueryFunc argument */
  };
  
  /* Possible values for RtreeConstraint.op */
  #define RTREE_EQ    0x41  /* A */
  #define RTREE_LE    0x42  /* B */
  #define RTREE_LT    0x43  /* C */
  #define RTREE_GE    0x44  /* D */
  #define RTREE_GT    0x45  /* E */
  #define RTREE_MATCH 0x46  /* F: Old-style sqlite3_rtree_geometry_callback() */
  #define RTREE_QUERY 0x47  /* G: New-style sqlite3_rtree_query_callback() */
  
  /* Special operators available only on cursors.  Needs to be consecutive
  ** with the normal values above, but must be less than RTREE_MATCH.  These
  ** are used in the cursor for contraints such as x=NULL (RTREE_FALSE) or
  ** x<'xyz' (RTREE_TRUE) */
  #define RTREE_TRUE  0x3f  /* ? */
  #define RTREE_FALSE 0x40  /* @ */
  
  /* 
  ** An rtree structure node.
  */
  struct RtreeNode {
    RtreeNode *pParent;         /* Parent node */
    i64 iNode;                  /* The node number */
    int nRef;                   /* Number of references to this node */
    int isDirty;                /* True if the node needs to be written to disk */
    u8 *zData;                  /* Content of the node, as should be on disk */
    RtreeNode *pNext;           /* Next node in this hash collision chain */
  };
  
  /* Return the number of cells in a node  */
  #define NCELL(pNode) readInt16(&(pNode)->zData[2])
  
  /* 
  ** A single cell from a node, deserialized
  */
  struct RtreeCell {
    i64 iRowid;                                 /* Node or entry ID */
    RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];  /* Bounding box coordinates */
  };
  
  
  /*
  ** This object becomes the sqlite3_user_data() for the SQL functions
  ** that are created by sqlite3_rtree_geometry_callback() and
  ** sqlite3_rtree_query_callback() and which appear on the right of MATCH
  ** operators in order to constrain a search.
  **
  ** xGeom and xQueryFunc are the callback functions.  Exactly one of 
  ** xGeom and xQueryFunc fields is non-NULL, depending on whether the
  ** SQL function was created using sqlite3_rtree_geometry_callback() or
  ** sqlite3_rtree_query_callback().
  ** 
  ** This object is deleted automatically by the destructor mechanism in
  ** sqlite3_create_function_v2().
  */
  struct RtreeGeomCallback {
    int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
    int (*xQueryFunc)(sqlite3_rtree_query_info*);
    void (*xDestructor)(void*);
    void *pContext;
  };
  
  /*
  ** An instance of this structure (in the form of a BLOB) is returned by
  ** the SQL functions that sqlite3_rtree_geometry_callback() and
  ** sqlite3_rtree_query_callback() create, and is read as the right-hand
  ** operand to the MATCH operator of an R-Tree.
  */
  struct RtreeMatchArg {
    u32 iSize;                  /* Size of this object */
    RtreeGeomCallback cb;       /* Info about the callback functions */
    int nParam;                 /* Number of parameters to the SQL function */
    sqlite3_value **apSqlParam; /* Original SQL parameter values */
    RtreeDValue aParam[1];      /* Values for parameters to the SQL function */
  };
  
  #ifndef MAX
  # define MAX(x,y) ((x) < (y) ? (y) : (x))
  #endif
  #ifndef MIN
  # define MIN(x,y) ((x) > (y) ? (y) : (x))
  #endif
  
  /* What version of GCC is being used.  0 means GCC is not being used .
  ** Note that the GCC_VERSION macro will also be set correctly when using
  ** clang, since clang works hard to be gcc compatible.  So the gcc
  ** optimizations will also work when compiling with clang.
  */
  #ifndef GCC_VERSION
  #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
  # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
  #else
  # define GCC_VERSION 0
  #endif
  #endif
  
  /* The testcase() macro should already be defined in the amalgamation.  If
  ** it is not, make it a no-op.
  */
  #ifndef SQLITE_AMALGAMATION
  # if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_DEBUG)
      unsigned int sqlite3RtreeTestcase = 0;
  #   define testcase(X)  if( X ){ sqlite3RtreeTestcase += __LINE__; }
  # else
  #   define testcase(X)
  # endif
  #endif
  
  /*
  ** Make sure that the compiler intrinsics we desire are enabled when
  ** compiling with an appropriate version of MSVC unless prevented by
  ** the SQLITE_DISABLE_INTRINSIC define.
  */
  #if !defined(SQLITE_DISABLE_INTRINSIC)
  #  if defined(_MSC_VER) && _MSC_VER>=1400
  #    if !defined(_WIN32_WCE)
  #      include <intrin.h>
  #      pragma intrinsic(_byteswap_ulong)
  #      pragma intrinsic(_byteswap_uint64)
  #    else
  #      include <cmnintrin.h>
  #    endif
  #  endif
  #endif
  
  /*
  ** Macros to determine whether the machine is big or little endian,
  ** and whether or not that determination is run-time or compile-time.
  **
  ** For best performance, an attempt is made to guess at the byte-order
  ** using C-preprocessor macros.  If that is unsuccessful, or if
  ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined
  ** at run-time.
  */
  #ifndef SQLITE_BYTEORDER
  #if defined(i386)     || defined(__i386__)   || defined(_M_IX86) ||    \
      defined(__x86_64) || defined(__x86_64__) || defined(_M_X64)  ||    \
      defined(_M_AMD64) || defined(_M_ARM)     || defined(__x86)   ||    \
      defined(__arm__)
  # define SQLITE_BYTEORDER    1234
  #elif defined(sparc)    || defined(__ppc__)
  # define SQLITE_BYTEORDER    4321
  #else
  # define SQLITE_BYTEORDER    0     /* 0 means "unknown at compile-time" */
  #endif
  #endif
  
  
  /* What version of MSVC is being used.  0 means MSVC is not being used */
  #ifndef MSVC_VERSION
  #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
  # define MSVC_VERSION _MSC_VER
  #else
  # define MSVC_VERSION 0
  #endif
  #endif
  
  /*
  ** 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){
    assert( ((((char*)p) - (char*)0)&3)==0 );  /* p is always 4-byte aligned */
  #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
    pCoord->u = _byteswap_ulong(*(u32*)p);
  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
    pCoord->u = __builtin_bswap32(*(u32*)p);
  #elif SQLITE_BYTEORDER==4321
    pCoord->u = *(u32*)p;
  #else
    pCoord->u = (
      (((u32)p[0]) << 24) + 
      (((u32)p[1]) << 16) + 
      (((u32)p[2]) <<  8) + 
      (((u32)p[3]) <<  0)
    );
  #endif
  }
  static i64 readInt64(u8 *p){
  #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
    u64 x;
    memcpy(&x, p, 8);
    return (i64)_byteswap_uint64(x);
  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
    u64 x;
    memcpy(&x, p, 8);
    return (i64)__builtin_bswap64(x);
  #elif SQLITE_BYTEORDER==4321
    i64 x;
    memcpy(&x, p, 8);
    return x;
  #else
    return (i64)(
      (((u64)p[0]) << 56) + 
      (((u64)p[1]) << 48) + 
      (((u64)p[2]) << 40) + 
      (((u64)p[3]) << 32) + 
      (((u64)p[4]) << 24) + 
      (((u64)p[5]) << 16) + 
      (((u64)p[6]) <<  8) + 
      (((u64)p[7]) <<  0)
    );
  #endif
  }
  
  /*
  ** 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 void writeInt16(u8 *p, int i){
    p[0] = (i>> 8)&0xFF;
    p[1] = (i>> 0)&0xFF;
  }
  static int writeCoord(u8 *p, RtreeCoord *pCoord){
    u32 i;
    assert( ((((char*)p) - (char*)0)&3)==0 );  /* p is always 4-byte aligned */
    assert( sizeof(RtreeCoord)==4 );
    assert( sizeof(u32)==4 );
  #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
    i = __builtin_bswap32(pCoord->u);
    memcpy(p, &i, 4);
  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
    i = _byteswap_ulong(pCoord->u);
    memcpy(p, &i, 4);
  #elif SQLITE_BYTEORDER==4321
    i = pCoord->u;
    memcpy(p, &i, 4);
  #else
    i = pCoord->u;
    p[0] = (i>>24)&0xFF;
    p[1] = (i>>16)&0xFF;
    p[2] = (i>> 8)&0xFF;
    p[3] = (i>> 0)&0xFF;
  #endif
    return 4;
  }
  static int writeInt64(u8 *p, i64 i){
  #if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
    i = (i64)__builtin_bswap64((u64)i);
    memcpy(p, &i, 8);
  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
    i = (i64)_byteswap_uint64((u64)i);
    memcpy(p, &i, 8);
  #elif SQLITE_BYTEORDER==4321
    memcpy(p, &i, 8);
  #else
    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;
  #endif
    return 8;
  }
  
  /*
  ** Increment the reference count of node p.
  */
  static void nodeReference(RtreeNode *p){
    if( p ){
      assert( p->nRef>0 );
      p->nRef++;
    }
  }
  
  /*
  ** Clear the content of node p (set all bytes to 0x00).
  */
  static void nodeZero(Rtree *pRtree, RtreeNode *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 unsigned int nodeHash(i64 iNode){
    return ((unsigned)iNode) % 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;
    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){
    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){
    RtreeNode *pNode;
    pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode) + pRtree->iNodeSize);
    if( pNode ){
      memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
      pNode->zData = (u8 *)&pNode[1];
      pNode->nRef = 1;
      pRtree->nNodeRef++;
      pNode->pParent = pParent;
      pNode->isDirty = 1;
      nodeReference(pParent);
    }
    return pNode;
  }
  
  /*
  ** Clear the Rtree.pNodeBlob object
  */
  static void nodeBlobReset(Rtree *pRtree){
    if( pRtree->pNodeBlob && pRtree->inWrTrans==0 && pRtree->nCursor==0 ){
      sqlite3_blob *pBlob = pRtree->pNodeBlob;
      pRtree->pNodeBlob = 0;
      sqlite3_blob_close(pBlob);
    }
  }
  
  /*
  ** 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 = SQLITE_OK;
    RtreeNode *pNode = 0;
  
    /* 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))!=0 ){
      if( pParent && pParent!=pNode->pParent ){
        RTREE_IS_CORRUPT(pRtree);
        return SQLITE_CORRUPT_VTAB;
      }
      pNode->nRef++;
      *ppNode = pNode;
      return SQLITE_OK;
    }
  
    if( pRtree->pNodeBlob ){
      sqlite3_blob *pBlob = pRtree->pNodeBlob;
      pRtree->pNodeBlob = 0;
      rc = sqlite3_blob_reopen(pBlob, iNode);
      pRtree->pNodeBlob = pBlob;
      if( rc ){
        nodeBlobReset(pRtree);
        if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM;
      }
    }
    if( pRtree->pNodeBlob==0 ){
      char *zTab = sqlite3_mprintf("%s_node", pRtree->zName);
      if( zTab==0 ) return SQLITE_NOMEM;
      rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, zTab, "data", iNode, 0,
                             &pRtree->pNodeBlob);
      sqlite3_free(zTab);
    }
    if( rc ){
      nodeBlobReset(pRtree);
      *ppNode = 0;
      /* If unable to open an sqlite3_blob on the desired row, that can only
      ** be because the shadow tables hold erroneous data. */
      if( rc==SQLITE_ERROR ){
        rc = SQLITE_CORRUPT_VTAB;
        RTREE_IS_CORRUPT(pRtree);
      }
    }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){
      pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode)+pRtree->iNodeSize);
      if( !pNode ){
        rc = SQLITE_NOMEM;
      }else{
        pNode->pParent = pParent;
        pNode->zData = (u8 *)&pNode[1];
        pNode->nRef = 1;
        pRtree->nNodeRef++;
        pNode->iNode = iNode;
        pNode->isDirty = 0;
        pNode->pNext = 0;
        rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData,
                               pRtree->iNodeSize, 0);
      }
    }
  
    /* If the root node was just loaded, set pRtree->iDepth to the height
    ** of the r-tree structure. A height of zero means all data is stored on
    ** the root node. A height of one means the children of the root node
    ** are the leaves, and so on. If the depth as specified on the root node
    ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
    */
    if( rc==SQLITE_OK && pNode && iNode==1 ){
      pRtree->iDepth = readInt16(pNode->zData);
      if( pRtree->iDepth>RTREE_MAX_DEPTH ){
        rc = SQLITE_CORRUPT_VTAB;
        RTREE_IS_CORRUPT(pRtree);
      }
    }
  
    /* If no error has occurred so far, check if the "number of entries"
    ** field on the node is too large. If so, set the return code to 
    ** SQLITE_CORRUPT_VTAB.
    */
    if( pNode && rc==SQLITE_OK ){
      if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
        rc = SQLITE_CORRUPT_VTAB;
        RTREE_IS_CORRUPT(pRtree);
      }
    }
  
    if( rc==SQLITE_OK ){
      if( pNode!=0 ){
        nodeReference(pParent);
        nodeHashInsert(pRtree, pNode);
      }else{
        rc = SQLITE_CORRUPT_VTAB;
        RTREE_IS_CORRUPT(pRtree);
      }
      *ppNode = pNode;
    }else{
      if( pNode ){
        pRtree->nNodeRef--;
        sqlite3_free(pNode);
      }
      *ppNode = 0;
    }
  
    return rc;
  }
  
  /*
  ** Overwrite cell iCell of node pNode with the contents of pCell.
  */
  static void nodeOverwriteCell(
    Rtree *pRtree,             /* The overall R-Tree */
    RtreeNode *pNode,          /* The node into which the cell is to be written */
    RtreeCell *pCell,          /* The cell to write */
    int iCell                  /* Index into pNode into which pCell is written */
  ){
    int ii;
    u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
    p += writeInt64(p, pCell->iRowid);
    for(ii=0; ii<pRtree->nDim2; ii++){
      p += writeCoord(p, &pCell->aCoord[ii]);
    }
    pNode->isDirty = 1;
  }
  
  /*
  ** Remove 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,                /* The overall R-Tree */
    RtreeNode *pNode,             /* Write new cell into this node */
    RtreeCell *pCell              /* The cell to be inserted */
  ){
    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);
      sqlite3_bind_null(p, 2);
      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 );
      assert( pRtree->nNodeRef>0 );
      pNode->nRef--;
      if( pNode->nRef==0 ){
        pRtree->nNodeRef--;
        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,       /* The overall R-Tree */
    RtreeNode *pNode,    /* The node from which to extract the ID */
    int iCell            /* The cell index from which to extract the ID */
  ){
    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,               /* The overall R-Tree */
    RtreeNode *pNode,            /* The node from which to extract a coordinate */
    int iCell,                   /* The index of the cell within the node */
    int iCoord,                  /* Which coordinate to extract */
    RtreeCoord *pCoord           /* OUT: 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,               /* The overall R-Tree */
    RtreeNode *pNode,            /* The node containing the cell to be read */
    int iCell,                   /* Index of the cell within the node */
    RtreeCell *pCell             /* OUT: Write the cell contents here */
  ){
    u8 *pData;
    RtreeCoord *pCoord;
    int ii = 0;
    pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
    pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
    pCoord = pCell->aCoord;
    do{
      readCoord(pData, &pCoord[ii]);
      readCoord(pData+4, &pCoord[ii+1]);
      pData += 8;
      ii += 2;
    }while( ii<pRtree->nDim2 );
  }
  
  
  /* 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
  );
  
  /* 
  ** 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);
  }
  
  /* 
  ** 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);
  }
  
  /*
  ** 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 ){
      pRtree->inWrTrans = 0;
      assert( pRtree->nCursor==0 );
      nodeBlobReset(pRtree);
      assert( pRtree->nNodeRef==0 || pRtree->bCorrupt );
      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_finalize(pRtree->pWriteAux);
      sqlite3_free(pRtree->zReadAuxSql);
      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{
      nodeBlobReset(pRtree);
      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;
    Rtree *pRtree = (Rtree *)pVTab;
    RtreeCursor *pCsr;
  
    pCsr = (RtreeCursor *)sqlite3_malloc64(sizeof(RtreeCursor));
    if( pCsr ){
      memset(pCsr, 0, sizeof(RtreeCursor));
      pCsr->base.pVtab = pVTab;
      rc = SQLITE_OK;
      pRtree->nCursor++;
    }
    *ppCursor = (sqlite3_vtab_cursor *)pCsr;
  
    return rc;
  }
  
  
  /*
  ** Reset a cursor back to its initial state.
  */
  static void resetCursor(RtreeCursor *pCsr){
    Rtree *pRtree = (Rtree *)(pCsr->base.pVtab);
    int ii;
    sqlite3_stmt *pStmt;
    if( pCsr->aConstraint ){
      int i;                        /* Used to iterate through constraint array */
      for(i=0; i<pCsr->nConstraint; i++){
        sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
        if( pInfo ){
          if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
          sqlite3_free(pInfo);
        }
      }
      sqlite3_free(pCsr->aConstraint);
      pCsr->aConstraint = 0;
    }
    for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
    sqlite3_free(pCsr->aPoint);
    pStmt = pCsr->pReadAux;
    memset(pCsr, 0, sizeof(RtreeCursor));
    pCsr->base.pVtab = (sqlite3_vtab*)pRtree;
    pCsr->pReadAux = pStmt;
  
  }
  
  /* 
  ** Rtree virtual table module xClose method.
  */
  static int rtreeClose(sqlite3_vtab_cursor *cur){
    Rtree *pRtree = (Rtree *)(cur->pVtab);
    RtreeCursor *pCsr = (RtreeCursor *)cur;
    assert( pRtree->nCursor>0 );
    resetCursor(pCsr);
    sqlite3_finalize(pCsr->pReadAux);
    sqlite3_free(pCsr);
    pRtree->nCursor--;
    nodeBlobReset(pRtree);
    return SQLITE_OK;
  }
  
  /*
  ** 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->atEOF;
  }
  
  /*
  ** Convert raw bits from the on-disk RTree record into a coordinate value.
  ** The on-disk format is big-endian and needs to be converted for little-
  ** endian platforms.  The on-disk record stores integer coordinates if
  ** eInt is true and it stores 32-bit floating point records if eInt is
  ** false.  a[] is the four bytes of the on-disk record to be decoded.
  ** Store the results in "r".
  **
  ** There are five versions of this macro.  The last one is generic.  The
  ** other four are various architectures-specific optimizations.
  */
  #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
  #define RTREE_DECODE_COORD(eInt, a, r) {                        \
      RtreeCoord c;    /* Coordinate decoded */                   \
      c.u = _byteswap_ulong(*(u32*)a);                            \
      r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
  }
  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
  #define RTREE_DECODE_COORD(eInt, a, r) {                        \
      RtreeCoord c;    /* Coordinate decoded */                   \
      c.u = __builtin_bswap32(*(u32*)a);                          \
      r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
  }
  #elif SQLITE_BYTEORDER==1234
  #define RTREE_DECODE_COORD(eInt, a, r) {                        \
      RtreeCoord c;    /* Coordinate decoded */                   \
      memcpy(&c.u,a,4);                                           \
      c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)|                   \
            ((c.u&0xff)<<24)|((c.u&0xff00)<<8);                   \
      r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
  }
  #elif SQLITE_BYTEORDER==4321
  #define RTREE_DECODE_COORD(eInt, a, r) {                        \
      RtreeCoord c;    /* Coordinate decoded */                   \
      memcpy(&c.u,a,4);                                           \
      r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
  }
  #else
  #define RTREE_DECODE_COORD(eInt, a, r) {                        \
      RtreeCoord c;    /* Coordinate decoded */                   \
      c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16)                     \
             +((u32)a[2]<<8) + a[3];                              \
      r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
  }
  #endif
  
  /*
  ** Check the RTree node or entry given by pCellData and p against the MATCH
  ** constraint pConstraint.  
  */
  static int rtreeCallbackConstraint(
    RtreeConstraint *pConstraint,  /* The constraint to test */
    int eInt,                      /* True if RTree holding integer coordinates */
    u8 *pCellData,                 /* Raw cell content */
    RtreeSearchPoint *pSearch,     /* Container of this cell */
    sqlite3_rtree_dbl *prScore,    /* OUT: score for the cell */
    int *peWithin                  /* OUT: visibility of the cell */
  ){
    sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
    int nCoord = pInfo->nCoord;                           /* No. of coordinates */
    int rc;                                             /* Callback return code */
    RtreeCoord c;                                       /* Translator union */
    sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2];   /* Decoded coordinates */
  
    assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );
    assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );
  
    if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){
      pInfo->iRowid = readInt64(pCellData);
    }
    pCellData += 8;
  #ifndef SQLITE_RTREE_INT_ONLY
    if( eInt==0 ){
      switch( nCoord ){
        case 10:  readCoord(pCellData+36, &c); aCoord[9] = c.f;
                  readCoord(pCellData+32, &c); aCoord[8] = c.f;
        case 8:   readCoord(pCellData+28, &c); aCoord[7] = c.f;
                  readCoord(pCellData+24, &c); aCoord[6] = c.f;
        case 6:   readCoord(pCellData+20, &c); aCoord[5] = c.f;
                  readCoord(pCellData+16, &c); aCoord[4] = c.f;
        case 4:   readCoord(pCellData+12, &c); aCoord[3] = c.f;
                  readCoord(pCellData+8,  &c); aCoord[2] = c.f;
        default:  readCoord(pCellData+4,  &c); aCoord[1] = c.f;
                  readCoord(pCellData,    &c); aCoord[0] = c.f;
      }
    }else
  #endif
    {
      switch( nCoord ){
        case 10:  readCoord(pCellData+36, &c); aCoord[9] = c.i;
                  readCoord(pCellData+32, &c); aCoord[8] = c.i;
        case 8:   readCoord(pCellData+28, &c); aCoord[7] = c.i;
                  readCoord(pCellData+24, &c); aCoord[6] = c.i;
        case 6:   readCoord(pCellData+20, &c); aCoord[5] = c.i;
                  readCoord(pCellData+16, &c); aCoord[4] = c.i;
        case 4:   readCoord(pCellData+12, &c); aCoord[3] = c.i;
                  readCoord(pCellData+8,  &c); aCoord[2] = c.i;
        default:  readCoord(pCellData+4,  &c); aCoord[1] = c.i;
                  readCoord(pCellData,    &c); aCoord[0] = c.i;
      }
    }
    if( pConstraint->op==RTREE_MATCH ){
      int eWithin = 0;
      rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
                                nCoord, aCoord, &eWithin);
      if( eWithin==0 ) *peWithin = NOT_WITHIN;
      *prScore = RTREE_ZERO;
    }else{
      pInfo->aCoord = aCoord;
      pInfo->iLevel = pSearch->iLevel - 1;
      pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
      pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
      rc = pConstraint->u.xQueryFunc(pInfo);
      if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
      if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
        *prScore = pInfo->rScore;
      }
    }
    return rc;
  }
  
  /* 
  ** Check the internal RTree node given by pCellData against constraint p.
  ** If this constraint cannot be satisfied by any child within the node,
  ** set *peWithin to NOT_WITHIN.
  */
  static void rtreeNonleafConstraint(
    RtreeConstraint *p,        /* The constraint to test */
    int eInt,                  /* True if RTree holds integer coordinates */
    u8 *pCellData,             /* Raw cell content as appears on disk */
    int *peWithin              /* Adjust downward, as appropriate */
  ){
    sqlite3_rtree_dbl val;     /* Coordinate value convert to a double */
  
    /* p->iCoord might point to either a lower or upper bound coordinate
    ** in a coordinate pair.  But make pCellData point to the lower bound.
    */
    pCellData += 8 + 4*(p->iCoord&0xfe);
  
    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
        || p->op==RTREE_FALSE );
    assert( ((((char*)pCellData) - (char*)0)&3)==0 );  /* 4-byte aligned */
    switch( p->op ){
      case RTREE_TRUE:  return;   /* Always satisfied */
      case RTREE_FALSE: break;    /* Never satisfied */
      case RTREE_LE:
      case RTREE_LT:
      case RTREE_EQ:
        RTREE_DECODE_COORD(eInt, pCellData, val);
        /* val now holds the lower bound of the coordinate pair */
        if( p->u.rValue>=val ) return;
        if( p->op!=RTREE_EQ ) break;  /* RTREE_LE and RTREE_LT end here */
        /* Fall through for the RTREE_EQ case */
  
      default: /* RTREE_GT or RTREE_GE,  or fallthrough of RTREE_EQ */
        pCellData += 4;
        RTREE_DECODE_COORD(eInt, pCellData, val);
        /* val now holds the upper bound of the coordinate pair */
        if( p->u.rValue<=val ) return;
    }
    *peWithin = NOT_WITHIN;
  }
  
  /*
  ** Check the leaf RTree cell given by pCellData against constraint p.
  ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
  ** If the constraint is satisfied, leave *peWithin unchanged.
  **
  ** The constraint is of the form:  xN op $val
  **
  ** The op is given by p->op.  The xN is p->iCoord-th coordinate in
  ** pCellData.  $val is given by p->u.rValue.
  */
  static void rtreeLeafConstraint(
    RtreeConstraint *p,        /* The constraint to test */
    int eInt,                  /* True if RTree holds integer coordinates */
    u8 *pCellData,             /* Raw cell content as appears on disk */
    int *peWithin              /* Adjust downward, as appropriate */
  ){
    RtreeDValue xN;      /* Coordinate value converted to a double */
  
    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
        || p->op==RTREE_FALSE );
    pCellData += 8 + p->iCoord*4;
    assert( ((((char*)pCellData) - (char*)0)&3)==0 );  /* 4-byte aligned */
    RTREE_DECODE_COORD(eInt, pCellData, xN);
    switch( p->op ){
      case RTREE_TRUE:  return;   /* Always satisfied */
      case RTREE_FALSE: break;    /* Never satisfied */
      case RTREE_LE:    if( xN <= p->u.rValue ) return;  break;
      case RTREE_LT:    if( xN <  p->u.rValue ) return;  break;
      case RTREE_GE:    if( xN >= p->u.rValue ) return;  break;
      case RTREE_GT:    if( xN >  p->u.rValue ) return;  break;
      default:          if( xN == p->u.rValue ) return;  break;
    }
    *peWithin = NOT_WITHIN;
  }
  
  /*
  ** 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 *piIndex
  ){
    int ii;
    int nCell = NCELL(pNode);
    assert( nCell<200 );
    for(ii=0; ii<nCell; ii++){
      if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
        *piIndex = ii;
        return SQLITE_OK;
      }
    }
    RTREE_IS_CORRUPT(pRtree);
    return SQLITE_CORRUPT_VTAB;
  }
  
  /*
  ** 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, int *piIndex){
    RtreeNode *pParent = pNode->pParent;
    if( ALWAYS(pParent) ){
      return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
    }else{
      *piIndex = -1;
      return SQLITE_OK;
    }
  }
  
  /*
  ** Compare two search points.  Return negative, zero, or positive if the first
  ** is less than, equal to, or greater than the second.
  **
  ** The rScore is the primary key.  Smaller rScore values come first.
  ** If the rScore is a tie, then use iLevel as the tie breaker with smaller
  ** iLevel values coming first.  In this way, if rScore is the same for all
  ** SearchPoints, then iLevel becomes the deciding factor and the result
  ** is a depth-first search, which is the desired default behavior.
  */
  static int rtreeSearchPointCompare(
    const RtreeSearchPoint *pA,
    const RtreeSearchPoint *pB
  ){
    if( pA->rScore<pB->rScore ) return -1;
    if( pA->rScore>pB->rScore ) return +1;
    if( pA->iLevel<pB->iLevel ) return -1;
    if( pA->iLevel>pB->iLevel ) return +1;
    return 0;
  }
  
  /*
  ** Interchange two search points in a cursor.
  */
  static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
    RtreeSearchPoint t = p->aPoint[i];
    assert( i<j );
    p->aPoint[i] = p->aPoint[j];
    p->aPoint[j] = t;
    i++; j++;
    if( i<RTREE_CACHE_SZ ){
      if( j>=RTREE_CACHE_SZ ){
        nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
        p->aNode[i] = 0;
      }else{
        RtreeNode *pTemp = p->aNode[i];
        p->aNode[i] = p->aNode[j];
        p->aNode[j] = pTemp;
      }
    }
  }
  
  /*
  ** Return the search point with the lowest current score.
  */
  static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
    return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
  }
  
  /*
  ** Get the RtreeNode for the search point with the lowest score.
  */
  static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
    sqlite3_int64 id;
    int ii = 1 - pCur->bPoint;
    assert( ii==0 || ii==1 );
    assert( pCur->bPoint || pCur->nPoint );
    if( pCur->aNode[ii]==0 ){
      assert( pRC!=0 );
      id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
      *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
    }
    return pCur->aNode[ii];
  }
  
  /*
  ** Push a new element onto the priority queue
  */
  static RtreeSearchPoint *rtreeEnqueue(
    RtreeCursor *pCur,    /* The cursor */
    RtreeDValue rScore,   /* Score for the new search point */
    u8 iLevel             /* Level for the new search point */
  ){
    int i, j;
    RtreeSearchPoint *pNew;
    if( pCur->nPoint>=pCur->nPointAlloc ){
      int nNew = pCur->nPointAlloc*2 + 8;
      pNew = sqlite3_realloc64(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
      if( pNew==0 ) return 0;
      pCur->aPoint = pNew;
      pCur->nPointAlloc = nNew;
    }
    i = pCur->nPoint++;
    pNew = pCur->aPoint + i;
    pNew->rScore = rScore;
    pNew->iLevel = iLevel;
    assert( iLevel<=RTREE_MAX_DEPTH );
    while( i>0 ){
      RtreeSearchPoint *pParent;
      j = (i-1)/2;
      pParent = pCur->aPoint + j;
      if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
      rtreeSearchPointSwap(pCur, j, i);
      i = j;
      pNew = pParent;
    }
    return pNew;
  }
  
  /*
  ** Allocate a new RtreeSearchPoint and return a pointer to it.  Return
  ** NULL if malloc fails.
  */
  static RtreeSearchPoint *rtreeSearchPointNew(
    RtreeCursor *pCur,    /* The cursor */
    RtreeDValue rScore,   /* Score for the new search point */
    u8 iLevel             /* Level for the new search point */
  ){
    RtreeSearchPoint *pNew, *pFirst;
    pFirst = rtreeSearchPointFirst(pCur);
    pCur->anQueue[iLevel]++;
    if( pFirst==0
     || pFirst->rScore>rScore 
     || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
    ){
      if( pCur->bPoint ){
        int ii;
        pNew = rtreeEnqueue(pCur, rScore, iLevel);
        if( pNew==0 ) return 0;
        ii = (int)(pNew - pCur->aPoint) + 1;
        assert( ii==1 );
        if( ALWAYS(ii<RTREE_CACHE_SZ) ){
          assert( pCur->aNode[ii]==0 );
          pCur->aNode[ii] = pCur->aNode[0];
        }else{
          nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
        }
        pCur->aNode[0] = 0;
        *pNew = pCur->sPoint;
      }
      pCur->sPoint.rScore = rScore;
      pCur->sPoint.iLevel = iLevel;
      pCur->bPoint = 1;
      return &pCur->sPoint;
    }else{
      return rtreeEnqueue(pCur, rScore, iLevel);
    }
  }
  
  #if 0
  /* Tracing routines for the RtreeSearchPoint queue */
  static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
    if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
    printf(" %d.%05lld.%02d %g %d",
      p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
    );
    idx++;
    if( idx<RTREE_CACHE_SZ ){
      printf(" %p\n", pCur->aNode[idx]);
    }else{
      printf("\n");
    }
  }
  static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
    int ii;
    printf("=== %9s ", zPrefix);
    if( pCur->bPoint ){
      tracePoint(&pCur->sPoint, -1, pCur);
    }
    for(ii=0; ii<pCur->nPoint; ii++){
      if( ii>0 || pCur->bPoint ) printf("              ");
      tracePoint(&pCur->aPoint[ii], ii, pCur);
    }
  }
  # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
  #else
  # define RTREE_QUEUE_TRACE(A,B)   /* no-op */
  #endif
  
  /* Remove the search point with the lowest current score.
  */
  static void rtreeSearchPointPop(RtreeCursor *p){
    int i, j, k, n;
    i = 1 - p->bPoint;
    assert( i==0 || i==1 );
    if( p->aNode[i] ){
      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
      p->aNode[i] = 0;
    }
    if( p->bPoint ){
      p->anQueue[p->sPoint.iLevel]--;
      p->bPoint = 0;
    }else if( ALWAYS(p->nPoint) ){
      p->anQueue[p->aPoint[0].iLevel]--;
      n = --p->nPoint;
      p->aPoint[0] = p->aPoint[n];
      if( n<RTREE_CACHE_SZ-1 ){
        p->aNode[1] = p->aNode[n+1];
        p->aNode[n+1] = 0;
      }
      i = 0;
      while( (j = i*2+1)<n ){
        k = j+1;
        if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
          if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
            rtreeSearchPointSwap(p, i, k);
            i = k;
          }else{
            break;
          }
        }else{
          if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
            rtreeSearchPointSwap(p, i, j);
            i = j;
          }else{
            break;
          }
        }
      }
    }
  }
  
  
  /*
  ** Continue the search on cursor pCur until the front of the queue
  ** contains an entry suitable for returning as a result-set row,
  ** or until the RtreeSearchPoint queue is empty, indicating that the
  ** query has completed.
  */
  static int rtreeStepToLeaf(RtreeCursor *pCur){
    RtreeSearchPoint *p;
    Rtree *pRtree = RTREE_OF_CURSOR(pCur);
    RtreeNode *pNode;
    int eWithin;
    int rc = SQLITE_OK;
    int nCell;
    int nConstraint = pCur->nConstraint;
    int ii;
    int eInt;
    RtreeSearchPoint x;
  
    eInt = pRtree->eCoordType==RTREE_COORD_INT32;
    while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
      u8 *pCellData;
      pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
      if( rc ) return rc;
      nCell = NCELL(pNode);
      assert( nCell<200 );
      pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
      while( p->iCell<nCell ){
        sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
        eWithin = FULLY_WITHIN;
        for(ii=0; ii<nConstraint; ii++){
          RtreeConstraint *pConstraint = pCur->aConstraint + ii;
          if( pConstraint->op>=RTREE_MATCH ){
            rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
                                         &rScore, &eWithin);
            if( rc ) return rc;
          }else if( p->iLevel==1 ){
            rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin);
          }else{
            rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin);
          }
          if( eWithin==NOT_WITHIN ){
            p->iCell++;
            pCellData += pRtree->nBytesPerCell;
            break;
          }
        }
        if( eWithin==NOT_WITHIN ) continue;
        p->iCell++;
        x.iLevel = p->iLevel - 1;
        if( x.iLevel ){
          x.id = readInt64(pCellData);
          for(ii=0; ii<pCur->nPoint; ii++){
            if( pCur->aPoint[ii].id==x.id ){
              RTREE_IS_CORRUPT(pRtree);
              return SQLITE_CORRUPT_VTAB;
            }
          }
          x.iCell = 0;
        }else{
          x.id = p->id;
          x.iCell = p->iCell - 1;
        }
        if( p->iCell>=nCell ){
          RTREE_QUEUE_TRACE(pCur, "POP-S:");
          rtreeSearchPointPop(pCur);
        }
        if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
        p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
        if( p==0 ) return SQLITE_NOMEM;
        p->eWithin = (u8)eWithin;
        p->id = x.id;
        p->iCell = x.iCell;
        RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
        break;
      }
      if( p->iCell>=nCell ){
        RTREE_QUEUE_TRACE(pCur, "POP-Se:");
        rtreeSearchPointPop(pCur);
      }
    }
    pCur->atEOF = p==0;
    return SQLITE_OK;
  }
  
  /* 
  ** Rtree virtual table module xNext method.
  */
  static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
    RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
    int rc = SQLITE_OK;
  
    /* Move to the next entry that matches the configured constraints. */
    RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
    if( pCsr->bAuxValid ){
      pCsr->bAuxValid = 0;
      sqlite3_reset(pCsr->pReadAux);
    }
    rtreeSearchPointPop(pCsr);
    rc = rtreeStepToLeaf(pCsr);
    return rc;
  }
  
  /* 
  ** Rtree virtual table module xRowid method.
  */
  static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
    RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
    RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
    int rc = SQLITE_OK;
    RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
    if( rc==SQLITE_OK && ALWAYS(p) ){
      *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
    }
    return rc;
  }
  
  /* 
  ** 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;
    RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
    RtreeCoord c;
    int rc = SQLITE_OK;
    RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
  
    if( rc ) return rc;
    if( NEVER(p==0) ) return SQLITE_OK;
    if( i==0 ){
      sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
    }else if( i<=pRtree->nDim2 ){
      nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
  #ifndef SQLITE_RTREE_INT_ONLY
      if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
        sqlite3_result_double(ctx, c.f);
      }else
  #endif
      {
        assert( pRtree->eCoordType==RTREE_COORD_INT32 );
        sqlite3_result_int(ctx, c.i);
      }
    }else{
      if( !pCsr->bAuxValid ){
        if( pCsr->pReadAux==0 ){
          rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0,
                                  &pCsr->pReadAux, 0);
          if( rc ) return rc;
        }
        sqlite3_bind_int64(pCsr->pReadAux, 1, 
            nodeGetRowid(pRtree, pNode, p->iCell));
        rc = sqlite3_step(pCsr->pReadAux);
        if( rc==SQLITE_ROW ){
          pCsr->bAuxValid = 1;
        }else{
          sqlite3_reset(pCsr->pReadAux);
          if( rc==SQLITE_DONE ) rc = SQLITE_OK;
          return rc;
        }
      }
      sqlite3_result_value(ctx,
           sqlite3_column_value(pCsr->pReadAux, i - pRtree->nDim2 + 1));
    }  
    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,              /* RTree to search */
    i64 iRowid,                 /* The rowid searching for */
    RtreeNode **ppLeaf,         /* Write the node here */
    sqlite3_int64 *piNode       /* Write the node-id here */
  ){
    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);
      if( piNode ) *piNode = iNode;
      rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
      sqlite3_reset(pRtree->pReadRowid);
    }else{
      rc = sqlite3_reset(pRtree->pReadRowid);
    }
    return rc;
  }
  
  /*
  ** This function is called to configure the RtreeConstraint object passed
  ** as the second argument for a MATCH constraint. The value passed as the
  ** first argument to this function is the right-hand operand to the MATCH
  ** operator.
  */
  static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
    RtreeMatchArg *pBlob, *pSrc;       /* BLOB returned by geometry function */
    sqlite3_rtree_query_info *pInfo;   /* Callback information */
  
    pSrc = sqlite3_value_pointer(pValue, "RtreeMatchArg");
    if( pSrc==0 ) return SQLITE_ERROR;
    pInfo = (sqlite3_rtree_query_info*)
                  sqlite3_malloc64( sizeof(*pInfo)+pSrc->iSize );
    if( !pInfo ) return SQLITE_NOMEM;
    memset(pInfo, 0, sizeof(*pInfo));
    pBlob = (RtreeMatchArg*)&pInfo[1];
    memcpy(pBlob, pSrc, pSrc->iSize);
    pInfo->pContext = pBlob->cb.pContext;
    pInfo->nParam = pBlob->nParam;
    pInfo->aParam = pBlob->aParam;
    pInfo->apSqlParam = pBlob->apSqlParam;
  
    if( pBlob->cb.xGeom ){
      pCons->u.xGeom = pBlob->cb.xGeom;
    }else{
      pCons->op = RTREE_QUERY;
      pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
    }
    pCons->pInfo = pInfo;
    return SQLITE_OK;
  }
  
  /* 
  ** 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;
    int iCell = 0;
  
    rtreeReference(pRtree);
  
    /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
    resetCursor(pCsr);
  
    pCsr->iStrategy = idxNum;
    if( idxNum==1 ){
      /* Special case - lookup by rowid. */
      RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
      RtreeSearchPoint *p;     /* Search point for the leaf */
      i64 iRowid = sqlite3_value_int64(argv[0]);
      i64 iNode = 0;
      int eType = sqlite3_value_numeric_type(argv[0]);
      if( eType==SQLITE_INTEGER
       || (eType==SQLITE_FLOAT && sqlite3_value_double(argv[0])==iRowid)
      ){
        rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
      }else{
        rc = SQLITE_OK;
        pLeaf = 0;
      }
      if( rc==SQLITE_OK && pLeaf!=0 ){
        p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
        assert( p!=0 );  /* Always returns pCsr->sPoint */
        pCsr->aNode[0] = pLeaf;
        p->id = iNode;
        p->eWithin = PARTLY_WITHIN;
        rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
        p->iCell = (u8)iCell;
        RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
      }else{
        pCsr->atEOF = 1;
      }
    }else{
      /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
      ** with the configured constraints. 
      */
      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
      if( rc==SQLITE_OK && argc>0 ){
        pCsr->aConstraint = sqlite3_malloc64(sizeof(RtreeConstraint)*argc);
        pCsr->nConstraint = argc;
        if( !pCsr->aConstraint ){
          rc = SQLITE_NOMEM;
        }else{
          memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
          memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
          assert( (idxStr==0 && argc==0)
                  || (idxStr && (int)strlen(idxStr)==argc*2) );
          for(ii=0; ii<argc; ii++){
            RtreeConstraint *p = &pCsr->aConstraint[ii];
            int eType = sqlite3_value_numeric_type(argv[ii]);
            p->op = idxStr[ii*2];
            p->iCoord = idxStr[ii*2+1]-'0';
            if( p->op>=RTREE_MATCH ){
              /* A MATCH operator. The right-hand-side must be a blob that
              ** can be cast into an RtreeMatchArg object. One created using
              ** an sqlite3_rtree_geometry_callback() SQL user function.
              */
              rc = deserializeGeometry(argv[ii], p);
              if( rc!=SQLITE_OK ){
                break;
              }
              p->pInfo->nCoord = pRtree->nDim2;
              p->pInfo->anQueue = pCsr->anQueue;
              p->pInfo->mxLevel = pRtree->iDepth + 1;
            }else if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
  #ifdef SQLITE_RTREE_INT_ONLY
              p->u.rValue = sqlite3_value_int64(argv[ii]);
  #else
              p->u.rValue = sqlite3_value_double(argv[ii]);
  #endif
            }else{
              p->u.rValue = RTREE_ZERO;
              if( eType==SQLITE_NULL ){
                p->op = RTREE_FALSE;
              }else if( p->op==RTREE_LT || p->op==RTREE_LE ){
                p->op = RTREE_TRUE;
              }else{
                p->op = RTREE_FALSE;
              }
            }
          }
        }
      }
      if( rc==SQLITE_OK ){
        RtreeSearchPoint *pNew;
        assert( pCsr->bPoint==0 );  /* Due to the resetCursor() call above */
        pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1));
        if( NEVER(pNew==0) ){       /* Because pCsr->bPoint was FALSE */
          return SQLITE_NOMEM;
        }
        pNew->id = 1;
        pNew->iCell = 0;
        pNew->eWithin = PARTLY_WITHIN;
        assert( pCsr->bPoint==1 );
        pCsr->aNode[0] = pRoot;
        pRoot = 0;
        RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
        rc = rtreeStepToLeaf(pCsr);
      }
    }
  
    nodeRelease(pRtree, pRoot);
    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 or full-table scan.
  **   ------------------------------------------------
  **
  ** If strategy 1 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')
  **   MATCH       0x46 ('F')
  **   ----------------------
  **
  ** 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){
    Rtree *pRtree = (Rtree*)tab;
    int rc = SQLITE_OK;
    int ii;
    int bMatch = 0;                 /* True if there exists a MATCH constraint */
    i64 nRow;                       /* Estimated rows returned by this scan */
  
    int iIdx = 0;
    char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
    memset(zIdxStr, 0, sizeof(zIdxStr));
  
    /* Check if there exists a MATCH constraint - even an unusable one. If there
    ** is, do not consider the lookup-by-rowid plan as using such a plan would
    ** require the VDBE to evaluate the MATCH constraint, which is not currently
    ** possible. */
    for(ii=0; ii<pIdxInfo->nConstraint; ii++){
      if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){
        bMatch = 1;
      }
    }
  
    assert( pIdxInfo->idxStr==0 );
    for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
      struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
  
      if( bMatch==0 && 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). It is expected to return
        ** a single row.
        */ 
        pIdxInfo->estimatedCost = 30.0;
        pIdxInfo->estimatedRows = 1;
        pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
        return SQLITE_OK;
      }
  
      if( p->usable
      && ((p->iColumn>0 && p->iColumn<=pRtree->nDim2)
          || p->op==SQLITE_INDEX_CONSTRAINT_MATCH)
      ){
        u8 op;
        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;
          case SQLITE_INDEX_CONSTRAINT_MATCH: op = RTREE_MATCH; break;
          default:                            op = 0;           break;
        }
        if( op ){
          zIdxStr[iIdx++] = op;
          zIdxStr[iIdx++] = (char)(p->iColumn - 1 + '0');
          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;
    }
  
    nRow = pRtree->nRowEst >> (iIdx/2);
    pIdxInfo->estimatedCost = (double)6.0 * (double)nRow;
    pIdxInfo->estimatedRows = nRow;
  
    return rc;
  }
  
  /*
  ** Return the N-dimensional volumn of the cell stored in *p.
  */
  static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){
    RtreeDValue area = (RtreeDValue)1;
    assert( pRtree->nDim>=1 && pRtree->nDim<=5 );
  #ifndef SQLITE_RTREE_INT_ONLY
    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
      switch( pRtree->nDim ){
        case 5:  area  = p->aCoord[9].f - p->aCoord[8].f;
        case 4:  area *= p->aCoord[7].f - p->aCoord[6].f;
        case 3:  area *= p->aCoord[5].f - p->aCoord[4].f;
        case 2:  area *= p->aCoord[3].f - p->aCoord[2].f;
        default: area *= p->aCoord[1].f - p->aCoord[0].f;
      }
    }else
  #endif
    {
      switch( pRtree->nDim ){
        case 5:  area  = (i64)p->aCoord[9].i - (i64)p->aCoord[8].i;
        case 4:  area *= (i64)p->aCoord[7].i - (i64)p->aCoord[6].i;
        case 3:  area *= (i64)p->aCoord[5].i - (i64)p->aCoord[4].i;
        case 2:  area *= (i64)p->aCoord[3].i - (i64)p->aCoord[2].i;
        default: area *= (i64)p->aCoord[1].i - (i64)p->aCoord[0].i;
      }
    }
    return area;
  }
  
  /*
  ** Return the margin length of cell p. The margin length is the sum
  ** of the objects size in each dimension.
  */
  static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
    RtreeDValue margin = 0;
    int ii = pRtree->nDim2 - 2;
    do{
      margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
      ii -= 2;
    }while( ii>=0 );
    return margin;
  }
  
  /*
  ** Store the union of cells p1 and p2 in p1.
  */
  static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
    int ii = 0;
    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
      do{
        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);
        ii += 2;
      }while( ii<pRtree->nDim2 );
    }else{
      do{
        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);
        ii += 2;
      }while( ii<pRtree->nDim2 );
    }
  }
  
  /*
  ** 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->nDim2; 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 RtreeDValue cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
    RtreeDValue area;
    RtreeCell cell;
    memcpy(&cell, p, sizeof(RtreeCell));
    area = cellArea(pRtree, &cell);
    cellUnion(pRtree, &cell, pCell);
    return (cellArea(pRtree, &cell)-area);
  }
  
  static RtreeDValue cellOverlap(
    Rtree *pRtree, 
    RtreeCell *p, 
    RtreeCell *aCell, 
    int nCell
  ){
    int ii;
    RtreeDValue overlap = RTREE_ZERO;
    for(ii=0; ii<nCell; ii++){
      int jj;
      RtreeDValue o = (RtreeDValue)1;
      for(jj=0; jj<pRtree->nDim2; jj+=2){
        RtreeDValue x1, 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 = (RtreeDValue)0;
          break;
        }else{
          o = o * (x2-x1);
        }
      }
      overlap += o;
    }
    return overlap;
  }
  
  
  /*
  ** 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 = 0;
    rc = nodeAcquire(pRtree, 1, 0, &pNode);
  
    for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
      int iCell;
      sqlite3_int64 iBest = 0;
  
      RtreeDValue fMinGrowth = RTREE_ZERO;
      RtreeDValue fMinArea = RTREE_ZERO;
  
      int nCell = NCELL(pNode);
      RtreeCell cell;
      RtreeNode *pChild = 0;
  
      RtreeCell *aCell = 0;
  
      /* 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++){
        int bBest = 0;
        RtreeDValue growth;
        RtreeDValue area;
        nodeGetCell(pRtree, pNode, iCell, &cell);
        growth = cellGrowth(pRtree, &cell, pCell);
        area = cellArea(pRtree, &cell);
        if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
          bBest = 1;
        }
        if( bBest ){
          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 int AdjustTree(
    Rtree *pRtree,                    /* Rtree table */
    RtreeNode *pNode,                 /* Adjust ancestry of this node. */
    RtreeCell *pCell                  /* This cell was just inserted */
  ){
    RtreeNode *p = pNode;
    int cnt = 0;
    int rc;
    while( p->pParent ){
      RtreeNode *pParent = p->pParent;
      RtreeCell cell;
      int iCell;
  
      cnt++;
      if( NEVER(cnt>100) ){
        RTREE_IS_CORRUPT(pRtree);
        return SQLITE_CORRUPT_VTAB;
      }
      rc = nodeParentIndex(pRtree, p, &iCell);
      if( NEVER(rc!=SQLITE_OK) ){
        RTREE_IS_CORRUPT(pRtree);
        return SQLITE_CORRUPT_VTAB;
      }
  
      nodeGetCell(pRtree, pParent, iCell, &cell);
      if( !cellContains(pRtree, &cell, pCell) ){
        cellUnion(pRtree, &cell, pCell);
        nodeOverwriteCell(pRtree, pParent, &cell, iCell);
      }
   
      p = pParent;
    }
    return SQLITE_OK;
  }
  
  /*
  ** 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);
  
  
  /*
  ** 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, 
    RtreeDValue *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{
          RtreeDValue fLeft = aDistance[aLeft[iLeft]];
          RtreeDValue 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++){
          RtreeDValue left = aDistance[aIdx[jj-1]];
          RtreeDValue 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 ){
        RtreeDValue xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
        RtreeDValue xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
        RtreeDValue xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
        RtreeDValue 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++){
          RtreeDValue xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
          RtreeDValue xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
          RtreeDValue xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
          RtreeDValue xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
          assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
        }
      }
  #endif
    }
  }
  
  /*
  ** 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 = 0;
    int iBestSplit = 0;
    RtreeDValue fBestMargin = RTREE_ZERO;
  
    sqlite3_int64 nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
  
    aaSorted = (int **)sqlite3_malloc64(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++){
      RtreeDValue margin = RTREE_ZERO;
      RtreeDValue fBestOverlap = RTREE_ZERO;
      RtreeDValue fBestArea = RTREE_ZERO;
      int iBestLeft = 0;
      int nLeft;
  
      for(
        nLeft=RTREE_MINCELLS(pRtree); 
        nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 
        nLeft++
      ){
        RtreeCell left;
        RtreeCell right;
        int kk;
        RtreeDValue overlap;
        RtreeDValue 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);
        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;
  }
  
  
  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);
      RtreeNode *p;
      for(p=pNode; p; p=p->pParent){
        if( p==pChild ) return SQLITE_CORRUPT_VTAB;
      }
      if( pChild ){
        nodeRelease(pRtree, pChild->pParent);
        nodeReference(pNode);
        pChild->pParent = pNode;
      }
    }
    if( NEVER(pNode==0) ) return SQLITE_ERROR;
    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_malloc64((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);
      pLeft = nodeNew(pRtree, pNode);
      pRtree->iDepth++;
      pNode->isDirty = 1;
      writeInt16(pNode->zData, pRtree->iDepth);
    }else{
      pLeft = pNode;
      pRight = nodeNew(pRtree, pLeft->pParent);
      pLeft->nRef++;
    }
  
    if( !pLeft || !pRight ){
      rc = SQLITE_NOMEM;
      goto splitnode_out;
    }
  
    memset(pLeft->zData, 0, pRtree->iNodeSize);
    memset(pRight->zData, 0, pRtree->iNodeSize);
  
    rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
                           &leftbbox, &rightbbox);
    if( rc!=SQLITE_OK ){
      goto splitnode_out;
    }
  
    /* Ensure both child nodes have node numbers assigned to them by calling
    ** nodeWrite(). Node pRight always needs a node number, as it was created
    ** by nodeNew() above. But node pLeft sometimes already has a node number.
    ** In this case avoid the all to nodeWrite().
    */
    if( 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;
      rc = nodeParentIndex(pRtree, pLeft, &iCell);
      if( ALWAYS(rc==SQLITE_OK) ){
        nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
        rc = AdjustTree(pRtree, pParent, &leftbbox);
        assert( rc==SQLITE_OK );
      }
      if( NEVER(rc!=SQLITE_OK) ){
        goto splitnode_out;
      }
    }
    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;
  }
  
  /*
  ** If node pLeaf is not the root of the r-tree and its pParent pointer is 
  ** still NULL, load all ancestor nodes of pLeaf into memory and populate
  ** the pLeaf->pParent chain all the way up to the root node.
  **
  ** This operation is required when a row is deleted (or updated - an update
  ** is implemented as a delete followed by an insert). SQLite provides the
  ** rowid of the row to delete, which can be used to find the leaf on which
  ** the entry resides (argument pLeaf). Once the leaf is located, this 
  ** function is called to determine its ancestry.
  */
  static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
    int rc = SQLITE_OK;
    RtreeNode *pChild = pLeaf;
    while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
      int rc2 = SQLITE_OK;          /* sqlite3_reset() return code */
      sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
      rc = sqlite3_step(pRtree->pReadParent);
      if( rc==SQLITE_ROW ){
        RtreeNode *pTest;           /* Used to test for reference loops */
        i64 iNode;                  /* Node number of parent node */
  
        /* Before setting pChild->pParent, test that we are not creating a
        ** loop of references (as we would if, say, pChild==pParent). We don't
        ** want to do this as it leads to a memory leak when trying to delete
        ** the referenced counted node structures.
        */
        iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
        for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
        if( pTest==0 ){
          rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
        }
      }
      rc = sqlite3_reset(pRtree->pReadParent);
      if( rc==SQLITE_OK ) rc = rc2;
      if( rc==SQLITE_OK && !pChild->pParent ){
        RTREE_IS_CORRUPT(pRtree);
        rc = SQLITE_CORRUPT_VTAB;
      }
      pChild = pChild->pParent;
    }
    return rc;
  }
  
  static int deleteCell(Rtree *, RtreeNode *, int, int);
  
  static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
    int rc;
    int rc2;
    RtreeNode *pParent = 0;
    int iCell;
  
    assert( pNode->nRef==1 );
  
    /* Remove the entry in the parent cell. */
    rc = nodeParentIndex(pRtree, pNode, &iCell);
    if( rc==SQLITE_OK ){
      pParent = pNode->pParent;
      pNode->pParent = 0;
      rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
      testcase( rc!=SQLITE_OK );
    }
    rc2 = nodeRelease(pRtree, pParent);
    if( rc==SQLITE_OK ){
      rc = rc2;
    }
    if( rc!=SQLITE_OK ){
      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 int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
    RtreeNode *pParent = pNode->pParent;
    int rc = SQLITE_OK; 
    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;
      rc = nodeParentIndex(pRtree, pNode, &ii);
      if( rc==SQLITE_OK ){
        nodeOverwriteCell(pRtree, pParent, &box, ii);
        rc = fixBoundingBox(pRtree, pParent);
      }
    }
    return rc;
  }
  
  /*
  ** 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){
    RtreeNode *pParent;
    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.
    */
    pParent = pNode->pParent;
    assert( pParent || pNode->iNode==1 );
    if( pParent ){
      if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
        rc = removeNode(pRtree, pNode, iHeight);
      }else{
        rc = fixBoundingBox(pRtree, pNode);
      }
    }
  
    return rc;
  }
  
  static int Reinsert(
    Rtree *pRtree, 
    RtreeNode *pNode, 
    RtreeCell *pCell, 
    int iHeight
  ){
    int *aOrder;
    int *aSpare;
    RtreeCell *aCell;
    RtreeDValue *aDistance;
    int nCell;
    RtreeDValue aCenterCoord[RTREE_MAX_DIMENSIONS];
    int iDim;
    int ii;
    int rc = SQLITE_OK;
    int n;
  
    memset(aCenterCoord, 0, sizeof(RtreeDValue)*RTREE_MAX_DIMENSIONS);
  
    nCell = NCELL(pNode)+1;
    n = (nCell+1)&(~1);
  
    /* Allocate the buffers used by this operation. The allocation is
    ** relinquished before this function returns.
    */
    aCell = (RtreeCell *)sqlite3_malloc64(n * (
      sizeof(RtreeCell)     +         /* aCell array */
      sizeof(int)           +         /* aOrder array */
      sizeof(int)           +         /* aSpare array */
      sizeof(RtreeDValue)             /* aDistance array */
    ));
    if( !aCell ){
      return SQLITE_NOMEM;
    }
    aOrder    = (int *)&aCell[n];
    aSpare    = (int *)&aOrder[n];
    aDistance = (RtreeDValue *)&aSpare[n];
  
    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]/(nCell*(RtreeDValue)2));
    }
  
    for(ii=0; ii<nCell; ii++){
      aDistance[ii] = RTREE_ZERO;
      for(iDim=0; iDim<pRtree->nDim; iDim++){
        RtreeDValue 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 ){
      rc = 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( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
        rc = SplitNode(pRtree, pNode, pCell, iHeight);
      }else{
        pRtree->iReinsertHeight = iHeight;
        rc = Reinsert(pRtree, pNode, pCell, iHeight);
      }
    }else{
      rc = AdjustTree(pRtree, pNode, pCell);
      if( ALWAYS(rc==SQLITE_OK) ){
        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, (int)pNode->iNode, &pInsert);
      if( rc==SQLITE_OK ){
        int rc2;
        rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)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 rtreeNewRowid(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;
  }
  
  /*
  ** Remove the entry with rowid=iDelete from the r-tree structure.
  */
  static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){
    int rc;                         /* Return code */
    RtreeNode *pLeaf = 0;           /* Leaf node containing record iDelete */
    int iCell;                      /* Index of iDelete cell in pLeaf */
    RtreeNode *pRoot = 0;           /* Root node of rtree structure */
  
  
    /* Obtain a reference to the root node to initialize 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 ){
      rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
    }
  
  #ifdef CORRUPT_DB
    assert( pLeaf!=0 || rc!=SQLITE_OK || CORRUPT_DB );
  #endif
  
    /* Delete the cell in question from the leaf node. */
    if( rc==SQLITE_OK && pLeaf ){
      int rc2;
      rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
      if( rc==SQLITE_OK ){
        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 && NCELL(pRoot)==1 ){
      int rc2;
      RtreeNode *pChild = 0;
      i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
      rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);  /* tag-20210916a */
      if( rc==SQLITE_OK ){
        rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
      }
      rc2 = nodeRelease(pRtree, pChild);
      if( rc==SQLITE_OK ) rc = rc2;
      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;
      pRtree->nNodeRef--;
      sqlite3_free(pLeaf);
    }
  
    /* Release the reference to the root node. */
    if( rc==SQLITE_OK ){
      rc = nodeRelease(pRtree, pRoot);
    }else{
      nodeRelease(pRtree, pRoot);
    }
  
    return rc;
  }
  
  /*
  ** Rounding constants for float->double conversion.
  */
  #define RNDTOWARDS  (1.0 - 1.0/8388608.0)  /* Round towards zero */
  #define RNDAWAY     (1.0 + 1.0/8388608.0)  /* Round away from zero */
  
  #if !defined(SQLITE_RTREE_INT_ONLY)
  /*
  ** Convert an sqlite3_value into an RtreeValue (presumably a float)
  ** while taking care to round toward negative or positive, respectively.
  */
  static RtreeValue rtreeValueDown(sqlite3_value *v){
    double d = sqlite3_value_double(v);
    float f = (float)d;
    if( f>d ){
      f = (float)(d*(d<0 ? RNDAWAY : RNDTOWARDS));
    }
    return f;
  }
  static RtreeValue rtreeValueUp(sqlite3_value *v){
    double d = sqlite3_value_double(v);
    float f = (float)d;
    if( f<d ){
      f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY));
    }
    return f;
  }
  #endif /* !defined(SQLITE_RTREE_INT_ONLY) */
  
  /*
  ** A constraint has failed while inserting a row into an rtree table. 
  ** Assuming no OOM error occurs, this function sets the error message 
  ** (at pRtree->base.zErrMsg) to an appropriate value and returns
  ** SQLITE_CONSTRAINT.
  **
  ** Parameter iCol is the index of the leftmost column involved in the
  ** constraint failure. If it is 0, then the constraint that failed is
  ** the unique constraint on the id column. Otherwise, it is the rtree
  ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed.
  **
  ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT.
  */
  static int rtreeConstraintError(Rtree *pRtree, int iCol){
    sqlite3_stmt *pStmt = 0;
    char *zSql; 
    int rc;
  
    assert( iCol==0 || iCol%2 );
    zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree->zDb, pRtree->zName);
    if( zSql ){
      rc = sqlite3_prepare_v2(pRtree->db, zSql, -1, &pStmt, 0);
    }else{
      rc = SQLITE_NOMEM;
    }
    sqlite3_free(zSql);
  
    if( rc==SQLITE_OK ){
      if( iCol==0 ){
        const char *zCol = sqlite3_column_name(pStmt, 0);
        pRtree->base.zErrMsg = sqlite3_mprintf(
            "UNIQUE constraint failed: %s.%s", pRtree->zName, zCol
        );
      }else{
        const char *zCol1 = sqlite3_column_name(pStmt, iCol);
        const char *zCol2 = sqlite3_column_name(pStmt, iCol+1);
        pRtree->base.zErrMsg = sqlite3_mprintf(
            "rtree constraint failed: %s.(%s<=%s)", pRtree->zName, zCol1, zCol2
        );
      }
    }
  
    sqlite3_finalize(pStmt);
    return (rc==SQLITE_OK ? SQLITE_CONSTRAINT : rc);
  }
  
  
  
  /*
  ** The xUpdate method for rtree module virtual tables.
  */
  static int rtreeUpdate(
    sqlite3_vtab *pVtab, 
    int nData, 
    sqlite3_value **aData, 
    sqlite_int64 *pRowid
  ){
    Rtree *pRtree = (Rtree *)pVtab;
    int rc = SQLITE_OK;
    RtreeCell cell;                 /* New cell to insert if nData>1 */
    int bHaveRowid = 0;             /* Set to 1 after new rowid is determined */
  
    if( pRtree->nNodeRef ){
      /* Unable to write to the btree while another cursor is reading from it,
      ** since the write might do a rebalance which would disrupt the read
      ** cursor. */
      return SQLITE_LOCKED_VTAB;
    }
    rtreeReference(pRtree);
    assert(nData>=1);
  
    cell.iRowid = 0;  /* Used only to suppress a compiler warning */
  
    /* Constraint handling. A write operation on an r-tree table may return
    ** SQLITE_CONSTRAINT for two reasons:
    **
    **   1. A duplicate rowid value, or
    **   2. The supplied data violates the "x2>=x1" constraint.
    **
    ** In the first case, if the conflict-handling mode is REPLACE, then
    ** the conflicting row can be removed before proceeding. In the second
    ** case, SQLITE_CONSTRAINT must be returned regardless of the
    ** conflict-handling mode specified by the user.
    */
    if( nData>1 ){
      int ii;
      int nn = nData - 4;
  
      if( nn > pRtree->nDim2 ) nn = pRtree->nDim2;
      /* Populate the cell.aCoord[] array. The first coordinate is aData[3].
      **
      ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
      ** with "column" that are interpreted as table constraints.
      ** Example:  CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
      ** This problem was discovered after years of use, so we silently ignore
      ** these kinds of misdeclared tables to avoid breaking any legacy.
      */
  
  #ifndef SQLITE_RTREE_INT_ONLY
      if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
        for(ii=0; ii<nn; ii+=2){
          cell.aCoord[ii].f = rtreeValueDown(aData[ii+3]);
          cell.aCoord[ii+1].f = rtreeValueUp(aData[ii+4]);
          if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
            rc = rtreeConstraintError(pRtree, ii+1);
            goto constraint;
          }
        }
      }else
  #endif
      {
        for(ii=0; ii<nn; ii+=2){
          cell.aCoord[ii].i = sqlite3_value_int(aData[ii+3]);
          cell.aCoord[ii+1].i = sqlite3_value_int(aData[ii+4]);
          if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
            rc = rtreeConstraintError(pRtree, ii+1);
            goto constraint;
          }
        }
      }
  
      /* If a rowid value was supplied, check if it is already present in 
      ** the table. If so, the constraint has failed. */
      if( sqlite3_value_type(aData[2])!=SQLITE_NULL ){
        cell.iRowid = sqlite3_value_int64(aData[2]);
        if( sqlite3_value_type(aData[0])==SQLITE_NULL
         || sqlite3_value_int64(aData[0])!=cell.iRowid
        ){
          int steprc;
          sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
          steprc = sqlite3_step(pRtree->pReadRowid);
          rc = sqlite3_reset(pRtree->pReadRowid);
          if( SQLITE_ROW==steprc ){
            if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){
              rc = rtreeDeleteRowid(pRtree, cell.iRowid);
            }else{
              rc = rtreeConstraintError(pRtree, 0);
              goto constraint;
            }
          }
        }
        bHaveRowid = 1;
      }
    }
  
    /* If aData[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(aData[0])!=SQLITE_NULL ){
      rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0]));
    }
  
    /* If the aData[] array contains more than one element, elements
    ** (aData[2]..aData[argc-1]) contain a new record to insert into
    ** the r-tree structure.
    */
    if( rc==SQLITE_OK && nData>1 ){
      /* Insert the new record into the r-tree */
      RtreeNode *pLeaf = 0;
  
      /* Figure out the rowid of the new row. */
      if( bHaveRowid==0 ){
        rc = rtreeNewRowid(pRtree, &cell.iRowid);
      }
      *pRowid = cell.iRowid;
  
      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;
        }
      }
      if( rc==SQLITE_OK && pRtree->nAux ){
        sqlite3_stmt *pUp = pRtree->pWriteAux;
        int jj;
        sqlite3_bind_int64(pUp, 1, *pRowid);
        for(jj=0; jj<pRtree->nAux; jj++){
          sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]);
        }
        sqlite3_step(pUp);
        rc = sqlite3_reset(pUp);
      }
    }
  
  constraint:
    rtreeRelease(pRtree);
    return rc;
  }
  
  /*
  ** Called when a transaction starts.
  */
  static int rtreeBeginTransaction(sqlite3_vtab *pVtab){
    Rtree *pRtree = (Rtree *)pVtab;
    assert( pRtree->inWrTrans==0 );
    pRtree->inWrTrans++;
    return SQLITE_OK;
  }
  
  /*
  ** Called when a transaction completes (either by COMMIT or ROLLBACK).
  ** The sqlite3_blob object should be released at this point.
  */
  static int rtreeEndTransaction(sqlite3_vtab *pVtab){
    Rtree *pRtree = (Rtree *)pVtab;
    pRtree->inWrTrans = 0;
    nodeBlobReset(pRtree);
    return SQLITE_OK;
  }
  
  /*
  ** 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 ){
      nodeBlobReset(pRtree);
      rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
      sqlite3_free(zSql);
    }
    return rc;
  }
  
  /*
  ** The xSavepoint method.
  **
  ** This module does not need to do anything to support savepoints. However,
  ** it uses this hook to close any open blob handle. This is done because a 
  ** DROP TABLE command - which fortunately always opens a savepoint - cannot 
  ** succeed if there are any open blob handles. i.e. if the blob handle were
  ** not closed here, the following would fail:
  **
  **   BEGIN;
  **     INSERT INTO rtree...
  **     DROP TABLE <tablename>;    -- Would fail with SQLITE_LOCKED
  **   COMMIT;
  */
  static int rtreeSavepoint(sqlite3_vtab *pVtab, int iSavepoint){
    Rtree *pRtree = (Rtree *)pVtab;
    u8 iwt = pRtree->inWrTrans;
    UNUSED_PARAMETER(iSavepoint);
    pRtree->inWrTrans = 0;
    nodeBlobReset(pRtree);
    pRtree->inWrTrans = iwt;
    return SQLITE_OK;
  }
  
  /*
  ** This function populates the pRtree->nRowEst variable with an estimate
  ** of the number of rows in the virtual table. If possible, this is based
  ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
  */
  static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){
    const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
    char *zSql;
    sqlite3_stmt *p;
    int rc;
    i64 nRow = RTREE_MIN_ROWEST;
  
    rc = sqlite3_table_column_metadata(
        db, pRtree->zDb, "sqlite_stat1",0,0,0,0,0,0
    );
    if( rc!=SQLITE_OK ){
      pRtree->nRowEst = RTREE_DEFAULT_ROWEST;
      return rc==SQLITE_ERROR ? SQLITE_OK : rc;
    }
    zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName);
    if( zSql==0 ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0);
      if( rc==SQLITE_OK ){
        if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0);
        rc = sqlite3_finalize(p);
      }
      sqlite3_free(zSql);
    }
    pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST);
    return rc;
  }
  
  
  /*
  ** Return true if zName is the extension on one of the shadow tables used
  ** by this module.
  */
  static int rtreeShadowName(const char *zName){
    static const char *azName[] = {
      "node", "parent", "rowid"
    };
    unsigned int i;
    for(i=0; i<sizeof(azName)/sizeof(azName[0]); i++){
      if( sqlite3_stricmp(zName, azName[i])==0 ) return 1;
    }
    return 0;
  }
  
  static sqlite3_module rtreeModule = {
    3,                          /* 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 */
    rtreeBeginTransaction,      /* xBegin - begin transaction */
    rtreeEndTransaction,        /* xSync - sync transaction */
    rtreeEndTransaction,        /* xCommit - commit transaction */
    rtreeEndTransaction,        /* xRollback - rollback transaction */
    0,                          /* xFindFunction - function overloading */
    rtreeRename,                /* xRename - rename the table */
    rtreeSavepoint,             /* xSavepoint */
    0,                          /* xRelease */
    0,                          /* xRollbackTo */
    rtreeShadowName             /* xShadowName */
  };
  
  static int rtreeSqlInit(
    Rtree *pRtree, 
    sqlite3 *db, 
    const char *zDb, 
    const char *zPrefix, 
    int isCreate
  ){
    int rc = SQLITE_OK;
  
    #define N_STATEMENT 8
    static const char *azSql[N_STATEMENT] = {
      /* Write the xxx_node table */
      "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;
    const int f = SQLITE_PREPARE_PERSISTENT|SQLITE_PREPARE_NO_VTAB;
  
    pRtree->db = db;
  
    if( isCreate ){
      char *zCreate;
      sqlite3_str *p = sqlite3_str_new(db);
      int ii;
      sqlite3_str_appendf(p,
         "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY,nodeno",
         zDb, zPrefix);
      for(ii=0; ii<pRtree->nAux; ii++){
        sqlite3_str_appendf(p,",a%d",ii);
      }
      sqlite3_str_appendf(p,
        ");CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY,data);",
        zDb, zPrefix);
      sqlite3_str_appendf(p,
      "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,parentnode);",
        zDb, zPrefix);
      sqlite3_str_appendf(p,
         "INSERT INTO \"%w\".\"%w_node\"VALUES(1,zeroblob(%d))",
         zDb, zPrefix, pRtree->iNodeSize);
      zCreate = sqlite3_str_finish(p);
      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->pWriteNode;
    appStmt[1] = &pRtree->pDeleteNode;
    appStmt[2] = &pRtree->pReadRowid;
    appStmt[3] = &pRtree->pWriteRowid;
    appStmt[4] = &pRtree->pDeleteRowid;
    appStmt[5] = &pRtree->pReadParent;
    appStmt[6] = &pRtree->pWriteParent;
    appStmt[7] = &pRtree->pDeleteParent;
  
    rc = rtreeQueryStat1(db, pRtree);
    for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
      char *zSql;
      const char *zFormat;
      if( i!=3 || pRtree->nAux==0 ){
         zFormat = azSql[i];
      }else {
         /* An UPSERT is very slightly slower than REPLACE, but it is needed
         ** if there are auxiliary columns */
         zFormat = "INSERT INTO\"%w\".\"%w_rowid\"(rowid,nodeno)VALUES(?1,?2)"
                    "ON CONFLICT(rowid)DO UPDATE SET nodeno=excluded.nodeno";
      }
      zSql = sqlite3_mprintf(zFormat, zDb, zPrefix);
      if( zSql ){
        rc = sqlite3_prepare_v3(db, zSql, -1, f, appStmt[i], 0); 
      }else{
        rc = SQLITE_NOMEM;
      }
      sqlite3_free(zSql);
    }
    if( pRtree->nAux ){
      pRtree->zReadAuxSql = sqlite3_mprintf(
         "SELECT * FROM \"%w\".\"%w_rowid\" WHERE rowid=?1",
         zDb, zPrefix);
      if( pRtree->zReadAuxSql==0 ){
        rc = SQLITE_NOMEM;
      }else{
        sqlite3_str *p = sqlite3_str_new(db);
        int ii;
        char *zSql;
        sqlite3_str_appendf(p, "UPDATE \"%w\".\"%w_rowid\"SET ", zDb, zPrefix);
        for(ii=0; ii<pRtree->nAux; ii++){
          if( ii ) sqlite3_str_append(p, ",", 1);
  #ifdef SQLITE_ENABLE_GEOPOLY
          if( ii<pRtree->nAuxNotNull ){
            sqlite3_str_appendf(p,"a%d=coalesce(?%d,a%d)",ii,ii+2,ii);
          }else
  #endif
          {
            sqlite3_str_appendf(p,"a%d=?%d",ii,ii+2);
          }
        }
        sqlite3_str_appendf(p, " WHERE rowid=?1");
        zSql = sqlite3_str_finish(p);
        if( zSql==0 ){
          rc = SQLITE_NOMEM;
        }else{
          rc = sqlite3_prepare_v3(db, zSql, -1, f, &pRtree->pWriteAux, 0); 
          sqlite3_free(zSql);
        }
      }
    }
  
    return rc;
  }
  
  /*
  ** The second argument to this function contains the text of an SQL statement
  ** that returns a single integer value. The statement is compiled and executed
  ** using database connection db. If successful, the integer value returned
  ** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error
  ** code is returned and the value of *piVal after returning is not defined.
  */
  static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){
    int rc = SQLITE_NOMEM;
    if( zSql ){
      sqlite3_stmt *pStmt = 0;
      rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
      if( rc==SQLITE_OK ){
        if( SQLITE_ROW==sqlite3_step(pStmt) ){
          *piVal = sqlite3_column_int(pStmt, 0);
        }
        rc = sqlite3_finalize(pStmt);
      }
    }
    return rc;
  }
  
  /*
  ** This function is called from within the xConnect() or xCreate() method to
  ** determine the node-size used by the rtree table being created or connected
  ** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned.
  ** Otherwise, an SQLite error code is returned.
  **
  ** If this function is being called as part of an xConnect(), then the rtree
  ** table already exists. In this case the node-size is determined by inspecting
  ** the root node of the tree.
  **
  ** Otherwise, for an xCreate(), use 64 bytes less than the database page-size. 
  ** This ensures that each node is stored on a single database page. If the 
  ** database page-size is so large that more than RTREE_MAXCELLS entries 
  ** would fit in a single node, use a smaller node-size.
  */
  static int getNodeSize(
    sqlite3 *db,                    /* Database handle */
    Rtree *pRtree,                  /* Rtree handle */
    int isCreate,                   /* True for xCreate, false for xConnect */
    char **pzErr                    /* OUT: Error message, if any */
  ){
    int rc;
    char *zSql;
    if( isCreate ){
      int iPageSize = 0;
      zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb);
      rc = getIntFromStmt(db, zSql, &iPageSize);
      if( rc==SQLITE_OK ){
        pRtree->iNodeSize = iPageSize-64;
        if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
          pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
        }
      }else{
        *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
      }
    }else{
      zSql = sqlite3_mprintf(
          "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
          pRtree->zDb, pRtree->zName
      );
      rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
      if( rc!=SQLITE_OK ){
        *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
      }else if( pRtree->iNodeSize<(512-64) ){
        rc = SQLITE_CORRUPT_VTAB;
        RTREE_IS_CORRUPT(pRtree);
        *pzErr = sqlite3_mprintf("undersize RTree blobs in \"%q_node\"",
                                 pRtree->zName);
      }
    }
  
    sqlite3_free(zSql);
    return rc;
  }
  
  /*
  ** Return the length of a token
  */
  static int rtreeTokenLength(const char *z){
    int dummy = 0;
    return sqlite3GetToken((const unsigned char*)z,&dummy);
  }
  
  /* 
  ** 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 */
    void *pAux,                         /* One of the RTREE_COORD_* constants */
    int argc, const char *const*argv,   /* Parameters to CREATE TABLE statement */
    sqlite3_vtab **ppVtab,              /* OUT: New virtual table */
    char **pzErr,                       /* OUT: Error message, if any */
    int isCreate                        /* True for xCreate, false for xConnect */
  ){
    int rc = SQLITE_OK;
    Rtree *pRtree;
    int nDb;              /* Length of string argv[1] */
    int nName;            /* Length of string argv[2] */
    int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
    sqlite3_str *pSql;
    char *zSql;
    int ii = 4;
    int iErr;
  
    const char *aErrMsg[] = {
      0,                                                    /* 0 */
      "Wrong number of columns for an rtree table",         /* 1 */
      "Too few columns for an rtree table",                 /* 2 */
      "Too many columns for an rtree table",                /* 3 */
      "Auxiliary rtree columns must be last"                /* 4 */
    };
  
    assert( RTREE_MAX_AUX_COLUMN<256 ); /* Aux columns counted by a u8 */
    if( argc<6 || argc>RTREE_MAX_AUX_COLUMN+3 ){
      *pzErr = sqlite3_mprintf("%s", aErrMsg[2 + (argc>=6)]);
      return SQLITE_ERROR;
    }
  
    sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
  
    /* Allocate the sqlite3_vtab structure */
    nDb = (int)strlen(argv[1]);
    nName = (int)strlen(argv[2]);
    pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName+2);
    if( !pRtree ){
      return SQLITE_NOMEM;
    }
    memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
    pRtree->nBusy = 1;
    pRtree->base.pModule = &rtreeModule;
    pRtree->zDb = (char *)&pRtree[1];
    pRtree->zName = &pRtree->zDb[nDb+1];
    pRtree->eCoordType = (u8)eCoordType;
    memcpy(pRtree->zDb, argv[1], nDb);
    memcpy(pRtree->zName, argv[2], nName);
  
  
    /* Create/Connect to the underlying relational database schema. If
    ** that is successful, call sqlite3_declare_vtab() to configure
    ** the r-tree table schema.
    */
    pSql = sqlite3_str_new(db);
    sqlite3_str_appendf(pSql, "CREATE TABLE x(%.*s INT", 
                        rtreeTokenLength(argv[3]), argv[3]);
    for(ii=4; ii<argc; ii++){
      const char *zArg = argv[ii];
      if( zArg[0]=='+' ){
        pRtree->nAux++;
        sqlite3_str_appendf(pSql, ",%.*s", rtreeTokenLength(zArg+1), zArg+1);
      }else if( pRtree->nAux>0 ){
        break;
      }else{
        static const char *azFormat[] = {",%.*s REAL", ",%.*s INT"};
        pRtree->nDim2++;
        sqlite3_str_appendf(pSql, azFormat[eCoordType],
                            rtreeTokenLength(zArg), zArg);
      }
    }
    sqlite3_str_appendf(pSql, ");");
    zSql = sqlite3_str_finish(pSql);
    if( !zSql ){
      rc = SQLITE_NOMEM;
    }else if( ii<argc ){
      *pzErr = sqlite3_mprintf("%s", aErrMsg[4]);
      rc = SQLITE_ERROR;
    }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
      *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
    }
    sqlite3_free(zSql);
    if( rc ) goto rtreeInit_fail;
    pRtree->nDim = pRtree->nDim2/2;
    if( pRtree->nDim<1 ){
      iErr = 2;
    }else if( pRtree->nDim2>RTREE_MAX_DIMENSIONS*2 ){
      iErr = 3;
    }else if( pRtree->nDim2 % 2 ){
      iErr = 1;
    }else{
      iErr = 0;
    }
    if( iErr ){
      *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
      goto rtreeInit_fail;
    }
    pRtree->nBytesPerCell = 8 + pRtree->nDim2*4;
  
    /* Figure out the node size to use. */
    rc = getNodeSize(db, pRtree, isCreate, pzErr);
    if( rc ) goto rtreeInit_fail;
    rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate);
    if( rc ){
      *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
      goto rtreeInit_fail;
    }
  
    *ppVtab = (sqlite3_vtab *)pRtree;
    return SQLITE_OK;
  
  rtreeInit_fail:
    if( rc==SQLITE_OK ) rc = SQLITE_ERROR;
    assert( *ppVtab==0 );
    assert( pRtree->nBusy==1 );
    rtreeRelease(pRtree);
    return rc;
  }
  
  
  /*
  ** Implementation of a scalar function that decodes r-tree nodes to
  ** human readable strings. This can be used for debugging and analysis.
  **
  ** The scalar function takes two arguments: (1) the number of dimensions
  ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
  ** an r-tree node.  For a two-dimensional r-tree structure called "rt", to
  ** deserialize all nodes, a statement like:
  **
  **   SELECT rtreenode(2, data) FROM rt_node;
  **
  ** The human readable string takes the form of a Tcl list with one
  ** entry for each cell in the r-tree node. Each entry is itself a
  ** list, containing the 8-byte rowid/pageno followed by the 
  ** <num-dimension>*2 coordinates.
  */
  static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
    RtreeNode node;
    Rtree tree;
    int ii;
    int nData;
    int errCode;
    sqlite3_str *pOut;
  
    UNUSED_PARAMETER(nArg);
    memset(&node, 0, sizeof(RtreeNode));
    memset(&tree, 0, sizeof(Rtree));
    tree.nDim = (u8)sqlite3_value_int(apArg[0]);
    if( tree.nDim<1 || tree.nDim>5 ) return;
    tree.nDim2 = tree.nDim*2;
    tree.nBytesPerCell = 8 + 8 * tree.nDim;
    node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
    if( node.zData==0 ) return;
    nData = sqlite3_value_bytes(apArg[1]);
    if( nData<4 ) return;
    if( nData<NCELL(&node)*tree.nBytesPerCell ) return;
  
    pOut = sqlite3_str_new(0);
    for(ii=0; ii<NCELL(&node); ii++){
      RtreeCell cell;
      int jj;
  
      nodeGetCell(&tree, &node, ii, &cell);
      if( ii>0 ) sqlite3_str_append(pOut, " ", 1);
      sqlite3_str_appendf(pOut, "{%lld", cell.iRowid);
      for(jj=0; jj<tree.nDim2; jj++){
  #ifndef SQLITE_RTREE_INT_ONLY
        sqlite3_str_appendf(pOut, " %g", (double)cell.aCoord[jj].f);
  #else
        sqlite3_str_appendf(pOut, " %d", cell.aCoord[jj].i);
  #endif
      }
      sqlite3_str_append(pOut, "}", 1);
    }
    errCode = sqlite3_str_errcode(pOut);
    sqlite3_result_text(ctx, sqlite3_str_finish(pOut), -1, sqlite3_free);
    sqlite3_result_error_code(ctx, errCode);
  }
  
  /* This routine implements an SQL function that returns the "depth" parameter
  ** from the front of a blob that is an r-tree node.  For example:
  **
  **     SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
  **
  ** The depth value is 0 for all nodes other than the root node, and the root
  ** node always has nodeno=1, so the example above is the primary use for this
  ** routine.  This routine is intended for testing and analysis only.
  */
  static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
    UNUSED_PARAMETER(nArg);
    if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB 
     || sqlite3_value_bytes(apArg[0])<2
  
    ){
      sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); 
    }else{
      u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
      if( zBlob ){
        sqlite3_result_int(ctx, readInt16(zBlob));
      }else{
        sqlite3_result_error_nomem(ctx);
      }
    }
  }
  
  /*
  ** Context object passed between the various routines that make up the
  ** implementation of integrity-check function rtreecheck().
  */
  typedef struct RtreeCheck RtreeCheck;
  struct RtreeCheck {
    sqlite3 *db;                    /* Database handle */
    const char *zDb;                /* Database containing rtree table */
    const char *zTab;               /* Name of rtree table */
    int bInt;                       /* True for rtree_i32 table */
    int nDim;                       /* Number of dimensions for this rtree tbl */
    sqlite3_stmt *pGetNode;         /* Statement used to retrieve nodes */
    sqlite3_stmt *aCheckMapping[2]; /* Statements to query %_parent/%_rowid */
    int nLeaf;                      /* Number of leaf cells in table */
    int nNonLeaf;                   /* Number of non-leaf cells in table */
    int rc;                         /* Return code */
    char *zReport;                  /* Message to report */
    int nErr;                       /* Number of lines in zReport */
  };
  
  #define RTREE_CHECK_MAX_ERROR 100
  
  /*
  ** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error,
  ** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code.
  */
  static void rtreeCheckReset(RtreeCheck *pCheck, sqlite3_stmt *pStmt){
    int rc = sqlite3_reset(pStmt);
    if( pCheck->rc==SQLITE_OK ) pCheck->rc = rc;
  }
  
  /*
  ** The second and subsequent arguments to this function are a format string
  ** and printf style arguments. This function formats the string and attempts
  ** to compile it as an SQL statement.
  **
  ** If successful, a pointer to the new SQL statement is returned. Otherwise,
  ** NULL is returned and an error code left in RtreeCheck.rc.
  */
  static sqlite3_stmt *rtreeCheckPrepare(
    RtreeCheck *pCheck,             /* RtreeCheck object */
    const char *zFmt, ...           /* Format string and trailing args */
  ){
    va_list ap;
    char *z;
    sqlite3_stmt *pRet = 0;
  
    va_start(ap, zFmt);
    z = sqlite3_vmprintf(zFmt, ap);
  
    if( pCheck->rc==SQLITE_OK ){
      if( z==0 ){
        pCheck->rc = SQLITE_NOMEM;
      }else{
        pCheck->rc = sqlite3_prepare_v2(pCheck->db, z, -1, &pRet, 0);
      }
    }
  
    sqlite3_free(z);
    va_end(ap);
    return pRet;
  }
  
  /*
  ** The second and subsequent arguments to this function are a printf()
  ** style format string and arguments. This function formats the string and
  ** appends it to the report being accumuated in pCheck.
  */
  static void rtreeCheckAppendMsg(RtreeCheck *pCheck, const char *zFmt, ...){
    va_list ap;
    va_start(ap, zFmt);
    if( pCheck->rc==SQLITE_OK && pCheck->nErr<RTREE_CHECK_MAX_ERROR ){
      char *z = sqlite3_vmprintf(zFmt, ap);
      if( z==0 ){
        pCheck->rc = SQLITE_NOMEM;
      }else{
        pCheck->zReport = sqlite3_mprintf("%z%s%z", 
            pCheck->zReport, (pCheck->zReport ? "\n" : ""), z
        );
        if( pCheck->zReport==0 ){
          pCheck->rc = SQLITE_NOMEM;
        }
      }
      pCheck->nErr++;
    }
    va_end(ap);
  }
  
  /*
  ** This function is a no-op if there is already an error code stored
  ** in the RtreeCheck object indicated by the first argument. NULL is
  ** returned in this case.
  **
  ** Otherwise, the contents of rtree table node iNode are loaded from
  ** the database and copied into a buffer obtained from sqlite3_malloc().
  ** If no error occurs, a pointer to the buffer is returned and (*pnNode)
  ** is set to the size of the buffer in bytes.
  **
  ** Or, if an error does occur, NULL is returned and an error code left
  ** in the RtreeCheck object. The final value of *pnNode is undefined in
  ** this case.
  */
  static u8 *rtreeCheckGetNode(RtreeCheck *pCheck, i64 iNode, int *pnNode){
    u8 *pRet = 0;                   /* Return value */
  
    if( pCheck->rc==SQLITE_OK && pCheck->pGetNode==0 ){
      pCheck->pGetNode = rtreeCheckPrepare(pCheck,
          "SELECT data FROM %Q.'%q_node' WHERE nodeno=?", 
          pCheck->zDb, pCheck->zTab
      );
    }
  
    if( pCheck->rc==SQLITE_OK ){
      sqlite3_bind_int64(pCheck->pGetNode, 1, iNode);
      if( sqlite3_step(pCheck->pGetNode)==SQLITE_ROW ){
        int nNode = sqlite3_column_bytes(pCheck->pGetNode, 0);
        const u8 *pNode = (const u8*)sqlite3_column_blob(pCheck->pGetNode, 0);
        pRet = sqlite3_malloc64(nNode);
        if( pRet==0 ){
          pCheck->rc = SQLITE_NOMEM;
        }else{
          memcpy(pRet, pNode, nNode);
          *pnNode = nNode;
        }
      }
      rtreeCheckReset(pCheck, pCheck->pGetNode);
      if( pCheck->rc==SQLITE_OK && pRet==0 ){
        rtreeCheckAppendMsg(pCheck, "Node %lld missing from database", iNode);
      }
    }
  
    return pRet;
  }
  
  /*
  ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
  ** (if bLeaf==1) table contains a specified entry. The schemas of the
  ** two tables are:
  **
  **   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
  **   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
  **
  ** In both cases, this function checks that there exists an entry with
  ** IPK value iKey and the second column set to iVal.
  **
  */
  static void rtreeCheckMapping(
    RtreeCheck *pCheck,             /* RtreeCheck object */
    int bLeaf,                      /* True for a leaf cell, false for interior */
    i64 iKey,                       /* Key for mapping */
    i64 iVal                        /* Expected value for mapping */
  ){
    int rc;
    sqlite3_stmt *pStmt;
    const char *azSql[2] = {
      "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1",
      "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1"
    };
  
    assert( bLeaf==0 || bLeaf==1 );
    if( pCheck->aCheckMapping[bLeaf]==0 ){
      pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
          azSql[bLeaf], pCheck->zDb, pCheck->zTab
      );
    }
    if( pCheck->rc!=SQLITE_OK ) return;
  
    pStmt = pCheck->aCheckMapping[bLeaf];
    sqlite3_bind_int64(pStmt, 1, iKey);
    rc = sqlite3_step(pStmt);
    if( rc==SQLITE_DONE ){
      rtreeCheckAppendMsg(pCheck, "Mapping (%lld -> %lld) missing from %s table",
          iKey, iVal, (bLeaf ? "%_rowid" : "%_parent")
      );
    }else if( rc==SQLITE_ROW ){
      i64 ii = sqlite3_column_int64(pStmt, 0);
      if( ii!=iVal ){
        rtreeCheckAppendMsg(pCheck, 
            "Found (%lld -> %lld) in %s table, expected (%lld -> %lld)",
            iKey, ii, (bLeaf ? "%_rowid" : "%_parent"), iKey, iVal
        );
      }
    }
    rtreeCheckReset(pCheck, pStmt);
  }
  
  /*
  ** Argument pCell points to an array of coordinates stored on an rtree page.
  ** This function checks that the coordinates are internally consistent (no
  ** x1>x2 conditions) and adds an error message to the RtreeCheck object
  ** if they are not.
  **
  ** Additionally, if pParent is not NULL, then it is assumed to point to
  ** the array of coordinates on the parent page that bound the page 
  ** containing pCell. In this case it is also verified that the two
  ** sets of coordinates are mutually consistent and an error message added
  ** to the RtreeCheck object if they are not.
  */
  static void rtreeCheckCellCoord(
    RtreeCheck *pCheck, 
    i64 iNode,                      /* Node id to use in error messages */
    int iCell,                      /* Cell number to use in error messages */
    u8 *pCell,                      /* Pointer to cell coordinates */
    u8 *pParent                     /* Pointer to parent coordinates */
  ){
    RtreeCoord c1, c2;
    RtreeCoord p1, p2;
    int i;
  
    for(i=0; i<pCheck->nDim; i++){
      readCoord(&pCell[4*2*i], &c1);
      readCoord(&pCell[4*(2*i + 1)], &c2);
  
      /* printf("%e, %e\n", c1.u.f, c2.u.f); */
      if( pCheck->bInt ? c1.i>c2.i : c1.f>c2.f ){
        rtreeCheckAppendMsg(pCheck, 
            "Dimension %d of cell %d on node %lld is corrupt", i, iCell, iNode
        );
      }
  
      if( pParent ){
        readCoord(&pParent[4*2*i], &p1);
        readCoord(&pParent[4*(2*i + 1)], &p2);
  
        if( (pCheck->bInt ? c1.i<p1.i : c1.f<p1.f) 
         || (pCheck->bInt ? c2.i>p2.i : c2.f>p2.f)
        ){
          rtreeCheckAppendMsg(pCheck, 
              "Dimension %d of cell %d on node %lld is corrupt relative to parent"
              , i, iCell, iNode
          );
        }
      }
    }
  }
  
  /*
  ** Run rtreecheck() checks on node iNode, which is at depth iDepth within
  ** the r-tree structure. Argument aParent points to the array of coordinates
  ** that bound node iNode on the parent node.
  **
  ** If any problems are discovered, an error message is appended to the
  ** report accumulated in the RtreeCheck object.
  */
  static void rtreeCheckNode(
    RtreeCheck *pCheck,
    int iDepth,                     /* Depth of iNode (0==leaf) */
    u8 *aParent,                    /* Buffer containing parent coords */
    i64 iNode                       /* Node to check */
  ){
    u8 *aNode = 0;
    int nNode = 0;
  
    assert( iNode==1 || aParent!=0 );
    assert( pCheck->nDim>0 );
  
    aNode = rtreeCheckGetNode(pCheck, iNode, &nNode);
    if( aNode ){
      if( nNode<4 ){
        rtreeCheckAppendMsg(pCheck, 
            "Node %lld is too small (%d bytes)", iNode, nNode
        );
      }else{
        int nCell;                  /* Number of cells on page */
        int i;                      /* Used to iterate through cells */
        if( aParent==0 ){
          iDepth = readInt16(aNode);
          if( iDepth>RTREE_MAX_DEPTH ){
            rtreeCheckAppendMsg(pCheck, "Rtree depth out of range (%d)", iDepth);
            sqlite3_free(aNode);
            return;
          }
        }
        nCell = readInt16(&aNode[2]);
        if( (4 + nCell*(8 + pCheck->nDim*2*4))>nNode ){
          rtreeCheckAppendMsg(pCheck, 
              "Node %lld is too small for cell count of %d (%d bytes)", 
              iNode, nCell, nNode
          );
        }else{
          for(i=0; i<nCell; i++){
            u8 *pCell = &aNode[4 + i*(8 + pCheck->nDim*2*4)];
            i64 iVal = readInt64(pCell);
            rtreeCheckCellCoord(pCheck, iNode, i, &pCell[8], aParent);
  
            if( iDepth>0 ){
              rtreeCheckMapping(pCheck, 0, iVal, iNode);
              rtreeCheckNode(pCheck, iDepth-1, &pCell[8], iVal);
              pCheck->nNonLeaf++;
            }else{
              rtreeCheckMapping(pCheck, 1, iVal, iNode);
              pCheck->nLeaf++;
            }
          }
        }
      }
      sqlite3_free(aNode);
    }
  }
  
  /*
  ** The second argument to this function must be either "_rowid" or
  ** "_parent". This function checks that the number of entries in the
  ** %_rowid or %_parent table is exactly nExpect. If not, it adds
  ** an error message to the report in the RtreeCheck object indicated
  ** by the first argument.
  */
  static void rtreeCheckCount(RtreeCheck *pCheck, const char *zTbl, i64 nExpect){
    if( pCheck->rc==SQLITE_OK ){
      sqlite3_stmt *pCount;
      pCount = rtreeCheckPrepare(pCheck, "SELECT count(*) FROM %Q.'%q%s'",
          pCheck->zDb, pCheck->zTab, zTbl
      );
      if( pCount ){
        if( sqlite3_step(pCount)==SQLITE_ROW ){
          i64 nActual = sqlite3_column_int64(pCount, 0);
          if( nActual!=nExpect ){
            rtreeCheckAppendMsg(pCheck, "Wrong number of entries in %%%s table"
                " - expected %lld, actual %lld" , zTbl, nExpect, nActual
            );
          }
        }
        pCheck->rc = sqlite3_finalize(pCount);
      }
    }
  }
  
  /*
  ** This function does the bulk of the work for the rtree integrity-check.
  ** It is called by rtreecheck(), which is the SQL function implementation.
  */
  static int rtreeCheckTable(
    sqlite3 *db,                    /* Database handle to access db through */
    const char *zDb,                /* Name of db ("main", "temp" etc.) */
    const char *zTab,               /* Name of rtree table to check */
    char **pzReport                 /* OUT: sqlite3_malloc'd report text */
  ){
    RtreeCheck check;               /* Common context for various routines */
    sqlite3_stmt *pStmt = 0;        /* Used to find column count of rtree table */
    int bEnd = 0;                   /* True if transaction should be closed */
    int nAux = 0;                   /* Number of extra columns. */
  
    /* Initialize the context object */
    memset(&check, 0, sizeof(check));
    check.db = db;
    check.zDb = zDb;
    check.zTab = zTab;
  
    /* If there is not already an open transaction, open one now. This is
    ** to ensure that the queries run as part of this integrity-check operate
    ** on a consistent snapshot.  */
    if( sqlite3_get_autocommit(db) ){
      check.rc = sqlite3_exec(db, "BEGIN", 0, 0, 0);
      bEnd = 1;
    }
  
    /* Find the number of auxiliary columns */
    if( check.rc==SQLITE_OK ){
      pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.'%q_rowid'", zDb, zTab);
      if( pStmt ){
        nAux = sqlite3_column_count(pStmt) - 2;
        sqlite3_finalize(pStmt);
      }else 
      if( check.rc!=SQLITE_NOMEM ){
        check.rc = SQLITE_OK;
      }
    }
  
    /* Find number of dimensions in the rtree table. */
    pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.%Q", zDb, zTab);
    if( pStmt ){
      int rc;
      check.nDim = (sqlite3_column_count(pStmt) - 1 - nAux) / 2;
      if( check.nDim<1 ){
        rtreeCheckAppendMsg(&check, "Schema corrupt or not an rtree");
      }else if( SQLITE_ROW==sqlite3_step(pStmt) ){
        check.bInt = (sqlite3_column_type(pStmt, 1)==SQLITE_INTEGER);
      }
      rc = sqlite3_finalize(pStmt);
      if( rc!=SQLITE_CORRUPT ) check.rc = rc;
    }
  
    /* Do the actual integrity-check */
    if( check.nDim>=1 ){
      if( check.rc==SQLITE_OK ){
        rtreeCheckNode(&check, 0, 0, 1);
      }
      rtreeCheckCount(&check, "_rowid", check.nLeaf);
      rtreeCheckCount(&check, "_parent", check.nNonLeaf);
    }
  
    /* Finalize SQL statements used by the integrity-check */
    sqlite3_finalize(check.pGetNode);
    sqlite3_finalize(check.aCheckMapping[0]);
    sqlite3_finalize(check.aCheckMapping[1]);
  
    /* If one was opened, close the transaction */
    if( bEnd ){
      int rc = sqlite3_exec(db, "END", 0, 0, 0);
      if( check.rc==SQLITE_OK ) check.rc = rc;
    }
    *pzReport = check.zReport;
    return check.rc;
  }
  
  /*
  ** Usage:
  **
  **   rtreecheck(<rtree-table>);
  **   rtreecheck(<database>, <rtree-table>);
  **
  ** Invoking this SQL function runs an integrity-check on the named rtree
  ** table. The integrity-check verifies the following:
  **
  **   1. For each cell in the r-tree structure (%_node table), that:
  **
  **       a) for each dimension, (coord1 <= coord2).
  **
  **       b) unless the cell is on the root node, that the cell is bounded
  **          by the parent cell on the parent node.
  **
  **       c) for leaf nodes, that there is an entry in the %_rowid 
  **          table corresponding to the cell's rowid value that 
  **          points to the correct node.
  **
  **       d) for cells on non-leaf nodes, that there is an entry in the 
  **          %_parent table mapping from the cell's child node to the
  **          node that it resides on.
  **
  **   2. That there are the same number of entries in the %_rowid table
  **      as there are leaf cells in the r-tree structure, and that there
  **      is a leaf cell that corresponds to each entry in the %_rowid table.
  **
  **   3. That there are the same number of entries in the %_parent table
  **      as there are non-leaf cells in the r-tree structure, and that 
  **      there is a non-leaf cell that corresponds to each entry in the 
  **      %_parent table.
  */
  static void rtreecheck(
    sqlite3_context *ctx, 
    int nArg, 
    sqlite3_value **apArg
  ){
    if( nArg!=1 && nArg!=2 ){
      sqlite3_result_error(ctx, 
          "wrong number of arguments to function rtreecheck()", -1
      );
    }else{
      int rc;
      char *zReport = 0;
      const char *zDb = (const char*)sqlite3_value_text(apArg[0]);
      const char *zTab;
      if( nArg==1 ){
        zTab = zDb;
        zDb = "main";
      }else{
        zTab = (const char*)sqlite3_value_text(apArg[1]);
      }
      rc = rtreeCheckTable(sqlite3_context_db_handle(ctx), zDb, zTab, &zReport);
      if( rc==SQLITE_OK ){
        sqlite3_result_text(ctx, zReport ? zReport : "ok", -1, SQLITE_TRANSIENT);
      }else{
        sqlite3_result_error_code(ctx, rc);
      }
      sqlite3_free(zReport);
    }
  }
  
  /* Conditionally include the geopoly code */
  #ifdef SQLITE_ENABLE_GEOPOLY
  # include "geopoly.c"
  #endif
  
  /*
  ** Register the r-tree module with database handle db. This creates the
  ** virtual table module "rtree" and the debugging/analysis scalar 
  ** function "rtreenode".
  */
  int sqlite3RtreeInit(sqlite3 *db){
    const int utf8 = SQLITE_UTF8;
    int rc;
  
    rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
    if( rc==SQLITE_OK ){
      rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
    }
    if( rc==SQLITE_OK ){
      rc = sqlite3_create_function(db, "rtreecheck", -1, utf8, 0,rtreecheck, 0,0);
    }
    if( rc==SQLITE_OK ){
  #ifdef SQLITE_RTREE_INT_ONLY
      void *c = (void *)RTREE_COORD_INT32;
  #else
      void *c = (void *)RTREE_COORD_REAL32;
  #endif
      rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
    }
    if( rc==SQLITE_OK ){
      void *c = (void *)RTREE_COORD_INT32;
      rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
    }
  #ifdef SQLITE_ENABLE_GEOPOLY
    if( rc==SQLITE_OK ){
      rc = sqlite3_geopoly_init(db);
    }
  #endif
  
    return rc;
  }
  
  /*
  ** This routine deletes the RtreeGeomCallback object that was attached
  ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
  ** or sqlite3_rtree_query_callback().  In other words, this routine is the
  ** destructor for an RtreeGeomCallback objecct.  This routine is called when
  ** the corresponding SQL function is deleted.
  */
  static void rtreeFreeCallback(void *p){
    RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
    if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
    sqlite3_free(p);
  }
  
  /*
  ** This routine frees the BLOB that is returned by geomCallback().
  */
  static void rtreeMatchArgFree(void *pArg){
    int i;
    RtreeMatchArg *p = (RtreeMatchArg*)pArg;
    for(i=0; i<p->nParam; i++){
      sqlite3_value_free(p->apSqlParam[i]);
    }
    sqlite3_free(p);
  }
  
  /*
  ** Each call to sqlite3_rtree_geometry_callback() or
  ** sqlite3_rtree_query_callback() creates an ordinary SQLite
  ** scalar function that is implemented by this routine.
  **
  ** All this function does is construct an RtreeMatchArg object that
  ** contains the geometry-checking callback routines and a list of
  ** parameters to this function, then return that RtreeMatchArg object
  ** as a BLOB.
  **
  ** The R-Tree MATCH operator will read the returned BLOB, deserialize
  ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
  ** out which elements of the R-Tree should be returned by the query.
  */
  static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
    RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
    RtreeMatchArg *pBlob;
    sqlite3_int64 nBlob;
    int memErr = 0;
  
    nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue)
             + nArg*sizeof(sqlite3_value*);
    pBlob = (RtreeMatchArg *)sqlite3_malloc64(nBlob);
    if( !pBlob ){
      sqlite3_result_error_nomem(ctx);
    }else{
      int i;
      pBlob->iSize = nBlob;
      pBlob->cb = pGeomCtx[0];
      pBlob->apSqlParam = (sqlite3_value**)&pBlob->aParam[nArg];
      pBlob->nParam = nArg;
      for(i=0; i<nArg; i++){
        pBlob->apSqlParam[i] = sqlite3_value_dup(aArg[i]);
        if( pBlob->apSqlParam[i]==0 ) memErr = 1;
  #ifdef SQLITE_RTREE_INT_ONLY
        pBlob->aParam[i] = sqlite3_value_int64(aArg[i]);
  #else
        pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
  #endif
      }
      if( memErr ){
        sqlite3_result_error_nomem(ctx);
        rtreeMatchArgFree(pBlob);
      }else{
        sqlite3_result_pointer(ctx, pBlob, "RtreeMatchArg", rtreeMatchArgFree);
      }
    }
  }
  
  /*
  ** Register a new geometry function for use with the r-tree MATCH operator.
  */
  int sqlite3_rtree_geometry_callback(
    sqlite3 *db,                  /* Register SQL function on this connection */
    const char *zGeom,            /* Name of the new SQL function */
    int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */
    void *pContext                /* Extra data associated with the callback */
  ){
    RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
  
    /* Allocate and populate the context object. */
    pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
    if( !pGeomCtx ) return SQLITE_NOMEM;
    pGeomCtx->xGeom = xGeom;
    pGeomCtx->xQueryFunc = 0;
    pGeomCtx->xDestructor = 0;
    pGeomCtx->pContext = pContext;
    return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
        (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
    );
  }
  
  /*
  ** Register a new 2nd-generation geometry function for use with the
  ** r-tree MATCH operator.
  */
  int sqlite3_rtree_query_callback(
    sqlite3 *db,                 /* Register SQL function on this connection */
    const char *zQueryFunc,      /* Name of new SQL function */
    int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */
    void *pContext,              /* Extra data passed into the callback */
    void (*xDestructor)(void*)   /* Destructor for the extra data */
  ){
    RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
  
    /* Allocate and populate the context object. */
    pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
    if( !pGeomCtx ){
      if( xDestructor ) xDestructor(pContext);
      return SQLITE_NOMEM;
    }
    pGeomCtx->xGeom = 0;
    pGeomCtx->xQueryFunc = xQueryFunc;
    pGeomCtx->xDestructor = xDestructor;
    pGeomCtx->pContext = pContext;
    return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, 
        (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
    );
  }
  
  #if !SQLITE_CORE
  #ifdef _WIN32
  __declspec(dllexport)
  #endif
  int sqlite3_rtree_init(
    sqlite3 *db,
    char **pzErrMsg,
    const sqlite3_api_routines *pApi
  ){
    SQLITE_EXTENSION_INIT2(pApi)
    return sqlite3RtreeInit(db);
  }
  #endif
  
  #endif
  