remove lib/libsqlite3, it has moved back to ports

23 files changed, 0 insertions, 7018 deletions

diff --git a/lib/libsqlite3/ext/rtree/README b/lib/libsqlite3/ext/rtree/README
deleted file mode 100644
index 3736f45c5fd..00000000000
--- a/lib/libsqlite3/ext/rtree/README
+++ /dev/null
@@ -1,120 +0,0 @@
-
-This directory contains an SQLite extension that implements a virtual 
-table type that allows users to create, query and manipulate r-tree[1] 
-data structures inside of SQLite databases. Users create, populate 
-and query r-tree structures using ordinary SQL statements.
-
-    1.  SQL Interface
-
-        1.1  Table Creation
-        1.2  Data Manipulation
-        1.3  Data Querying
-        1.4  Introspection and Analysis
-
-    2.  Compilation and Deployment
-
-    3.  References
-
-
-1. SQL INTERFACE
-
-  1.1 Table Creation.
-
-    All r-tree virtual tables have an odd number of columns between
-    3 and 11. Unlike regular SQLite tables, r-tree tables are strongly 
-    typed. 
-
-    The leftmost column is always the pimary key and contains 64-bit 
-    integer values. Each subsequent column contains a 32-bit real
-    value. For each pair of real values, the first (leftmost) must be 
-    less than or equal to the second. R-tree tables may be 
-    constructed using the following syntax:
-
-      CREATE VIRTUAL TABLE <name> USING rtree(<column-names>)
-
-    For example:
-
-      CREATE VIRTUAL TABLE boxes USING rtree(boxno, xmin, xmax, ymin, ymax);
-      INSERT INTO boxes VALUES(1, 1.0, 3.0, 2.0, 4.0);
-
-    Constructing a virtual r-tree table <name> creates the following three
-    real tables in the database to store the data structure:
-
-      <name>_node
-      <name>_rowid
-      <name>_parent
-
-    Dropping or modifying the contents of these tables directly will
-    corrupt the r-tree structure. To delete an r-tree from a database,
-    use a regular DROP TABLE statement:
-
-      DROP TABLE <name>;
-
-    Dropping the main r-tree table automatically drops the automatically
-    created tables. 
-
-  1.2 Data Manipulation (INSERT, UPDATE, DELETE).
-
-    The usual INSERT, UPDATE or DELETE syntax is used to manipulate data
-    stored in an r-tree table. Please note the following:
-
-      * Inserting a NULL value into the primary key column has the
-        same effect as inserting a NULL into an INTEGER PRIMARY KEY
-        column of a regular table. The system automatically assigns
-        an unused integer key value to the new record. Usually, this
-        is one greater than the largest primary key value currently
-        present in the table.
-
-      * Attempting to insert a duplicate primary key value fails with
-        an SQLITE_CONSTRAINT error.
-
-      * Attempting to insert or modify a record such that the value
-        stored in the (N*2)th column is greater than that stored in
-        the (N*2+1)th column fails with an SQLITE_CONSTRAINT error.
-
-      * When a record is inserted, values are always converted to 
-        the required type (64-bit integer or 32-bit real) as if they
-        were part of an SQL CAST expression. Non-numeric strings are
-        converted to zero.
-
-  1.3 Queries.
-
-    R-tree tables may be queried using all of the same SQL syntax supported
-    by regular tables. However, some query patterns are more efficient
-    than others.
-
-    R-trees support fast lookup by primary key value (O(logN), like 
-    regular tables).
-
-    Any combination of equality and range (<, <=, >, >=) constraints
-    on spatial data columns may be used to optimize other queries. This
-    is the key advantage to using r-tree tables instead of creating 
-    indices on regular tables.
-
-  1.4 Introspection and Analysis.
-
-    TODO: Describe rtreenode() and rtreedepth() functions.
-
-
-2. COMPILATION AND USAGE
-
-  The easiest way to compile and use the RTREE extension is to build
-  and use it as a dynamically loadable SQLite extension. To do this
-  using gcc on *nix:
-
-    gcc -shared rtree.c -o libSqliteRtree.so
-
-  You may need to add "-I" flags so that gcc can find sqlite3ext.h
-  and sqlite3.h. The resulting shared lib, libSqliteRtree.so, may be
-  loaded into sqlite in the same way as any other dynamicly loadable
-  extension.
-
-
-3. REFERENCES
-
-  [1]  Atonin Guttman, "R-trees - A Dynamic Index Structure For Spatial 
-       Searching", University of California Berkeley, 1984.
-
-  [2]  Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger,
-       "The R*-tree: An Efficient and Robust Access Method for Points and
-       Rectangles", Universitaet Bremen, 1990.
diff --git a/lib/libsqlite3/ext/rtree/rtree.c b/lib/libsqlite3/ext/rtree/rtree.c
deleted file mode 100644
index 4e473a22c28..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree.c
+++ /dev/null
@@ -1,3512 +0,0 @@
-/*
-** 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.
-**
-** 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)
-
-#ifndef SQLITE_CORE
-  #include "sqlite3ext.h"
-  SQLITE_EXTENSION_INIT1
-#else
-  #include "sqlite3.h"
-#endif
-
-#include <string.h>
-#include <assert.h>
-#include <stdio.h>
-
-#ifndef SQLITE_AMALGAMATION
-#include "sqlite3rtree.h"
-typedef sqlite3_int64 i64;
-typedef unsigned char u8;
-typedef unsigned short u16;
-typedef unsigned int u32;
-#endif
-
-/*  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
-
-/* 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 eCoordType;              /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
-  u8 nBytesPerCell;           /* Bytes consumed per cell */
-  int iDepth;                 /* Current depth of the r-tree structure */
-  char *zDb;                  /* Name of database containing r-tree table */
-  char *zName;                /* Name of r-tree table */ 
-  int nBusy;                  /* Current number of users of this structure */
-  i64 nRowEst;                /* Estimated number of rows in this table */
-
-  /* List of nodes removed during a CondenseTree operation. List is
-  ** linked together via the pointer normally used for hash chains -
-  ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 
-  ** headed by the node (leaf nodes have RtreeNode.iNode==0).
-  */
-  RtreeNode *pDeleted;
-  int iReinsertHeight;        /* Height of sub-trees Reinsert() has run on */
-
-  /* Statements to read/write/delete a record from xxx_node */
-  sqlite3_stmt *pReadNode;
-  sqlite3_stmt *pWriteNode;
-  sqlite3_stmt *pDeleteNode;
-
-  /* Statements to read/write/delete a record from xxx_rowid */
-  sqlite3_stmt *pReadRowid;
-  sqlite3_stmt *pWriteRowid;
-  sqlite3_stmt *pDeleteRowid;
-
-  /* Statements to read/write/delete a record from xxx_parent */
-  sqlite3_stmt *pReadParent;
-  sqlite3_stmt *pWriteParent;
-  sqlite3_stmt *pDeleteParent;
-
-  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
-
-/*
-** 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 
-** 2^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 */
-  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 */
-  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() */
-
-
-/* 
-** 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;
-};
-
-
-/*
-** Value for the first field of every RtreeMatchArg object. The MATCH
-** operator tests that the first field of a blob operand matches this
-** value to avoid operating on invalid blobs (which could cause a segfault).
-*/
-#define RTREE_GEOMETRY_MAGIC 0x891245AB
-
-/*
-** 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 magic;                  /* Always RTREE_GEOMETRY_MAGIC */
-  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
-
-/*
-** 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){
-  pCoord->u = (
-    (((u32)p[0]) << 24) + 
-    (((u32)p[1]) << 16) + 
-    (((u32)p[2]) <<  8) + 
-    (((u32)p[3]) <<  0)
-  );
-}
-static i64 readInt64(u8 *p){
-  return (
-    (((i64)p[0]) << 56) + 
-    (((i64)p[1]) << 48) + 
-    (((i64)p[2]) << 40) + 
-    (((i64)p[3]) << 32) + 
-    (((i64)p[4]) << 24) + 
-    (((i64)p[5]) << 16) + 
-    (((i64)p[6]) <<  8) + 
-    (((i64)p[7]) <<  0)
-  );
-}
-
-/*
-** Functions to serialize a 16 bit integer, 32 bit real number and
-** 64 bit integer. The value returned is the number of bytes written
-** to the argument buffer (always 2, 4 and 8 respectively).
-*/
-static int writeInt16(u8 *p, int i){
-  p[0] = (i>> 8)&0xFF;
-  p[1] = (i>> 0)&0xFF;
-  return 2;
-}
-static int writeCoord(u8 *p, RtreeCoord *pCoord){
-  u32 i;
-  assert( sizeof(RtreeCoord)==4 );
-  assert( sizeof(u32)==4 );
-  i = pCoord->u;
-  p[0] = (i>>24)&0xFF;
-  p[1] = (i>>16)&0xFF;
-  p[2] = (i>> 8)&0xFF;
-  p[3] = (i>> 0)&0xFF;
-  return 4;
-}
-static int writeInt64(u8 *p, i64 i){
-  p[0] = (i>>56)&0xFF;
-  p[1] = (i>>48)&0xFF;
-  p[2] = (i>>40)&0xFF;
-  p[3] = (i>>32)&0xFF;
-  p[4] = (i>>24)&0xFF;
-  p[5] = (i>>16)&0xFF;
-  p[6] = (i>> 8)&0xFF;
-  p[7] = (i>> 0)&0xFF;
-  return 8;
-}
-
-/*
-** Increment the reference count of node p.
-*/
-static void nodeReference(RtreeNode *p){
-  if( p ){
-    p->nRef++;
-  }
-}
-
-/*
-** Clear the content of node p (set all bytes to 0x00).
-*/
-static void nodeZero(Rtree *pRtree, RtreeNode *p){
-  memset(&p->zData[2], 0, pRtree->iNodeSize-2);
-  p->isDirty = 1;
-}
-
-/*
-** Given a node number iNode, return the corresponding key to use
-** in the Rtree.aHash table.
-*/
-static int nodeHash(i64 iNode){
-  return iNode % 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_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
-  if( pNode ){
-    memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
-    pNode->zData = (u8 *)&pNode[1];
-    pNode->nRef = 1;
-    pNode->pParent = pParent;
-    pNode->isDirty = 1;
-    nodeReference(pParent);
-  }
-  return pNode;
-}
-
-/*
-** Obtain a reference to an r-tree node.
-*/
-static int nodeAcquire(
-  Rtree *pRtree,             /* R-tree structure */
-  i64 iNode,                 /* Node number to load */
-  RtreeNode *pParent,        /* Either the parent node or NULL */
-  RtreeNode **ppNode         /* OUT: Acquired node */
-){
-  int rc;
-  int rc2 = SQLITE_OK;
-  RtreeNode *pNode;
-
-  /* Check if the requested node is already in the hash table. If so,
-  ** increase its reference count and return it.
-  */
-  if( (pNode = nodeHashLookup(pRtree, iNode)) ){
-    assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
-    if( pParent && !pNode->pParent ){
-      nodeReference(pParent);
-      pNode->pParent = pParent;
-    }
-    pNode->nRef++;
-    *ppNode = pNode;
-    return SQLITE_OK;
-  }
-
-  sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
-  rc = sqlite3_step(pRtree->pReadNode);
-  if( rc==SQLITE_ROW ){
-    const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
-    if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){
-      pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize);
-      if( !pNode ){
-        rc2 = SQLITE_NOMEM;
-      }else{
-        pNode->pParent = pParent;
-        pNode->zData = (u8 *)&pNode[1];
-        pNode->nRef = 1;
-        pNode->iNode = iNode;
-        pNode->isDirty = 0;
-        pNode->pNext = 0;
-        memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
-        nodeReference(pParent);
-      }
-    }
-  }
-  rc = sqlite3_reset(pRtree->pReadNode);
-  if( rc==SQLITE_OK ) rc = rc2;
-
-  /* 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( pNode && iNode==1 ){
-    pRtree->iDepth = readInt16(pNode->zData);
-    if( pRtree->iDepth>RTREE_MAX_DEPTH ){
-      rc = SQLITE_CORRUPT_VTAB;
-    }
-  }
-
-  /* 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;
-    }
-  }
-
-  if( rc==SQLITE_OK ){
-    if( pNode!=0 ){
-      nodeHashInsert(pRtree, pNode);
-    }else{
-      rc = SQLITE_CORRUPT_VTAB;
-    }
-    *ppNode = pNode;
-  }else{
-    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->nDim*2); 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);
-    if( pNode->iNode==0 && rc==SQLITE_OK ){
-      pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
-      nodeHashInsert(pRtree, pNode);
-    }
-  }
-  return rc;
-}
-
-/*
-** Release a reference to a node. If the node is dirty and the reference
-** count drops to zero, the node data is written to the database.
-*/
-static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
-  int rc = SQLITE_OK;
-  if( pNode ){
-    assert( pNode->nRef>0 );
-    pNode->nRef--;
-    if( pNode->nRef==0 ){
-      if( pNode->iNode==1 ){
-        pRtree->iDepth = -1;
-      }
-      if( pNode->pParent ){
-        rc = nodeRelease(pRtree, pNode->pParent);
-      }
-      if( rc==SQLITE_OK ){
-        rc = nodeWrite(pRtree, pNode);
-      }
-      nodeHashDelete(pRtree, pNode);
-      sqlite3_free(pNode);
-    }
-  }
-  return rc;
-}
-
-/*
-** Return the 64-bit integer value associated with cell iCell of
-** node pNode. If pNode is a leaf node, this is a rowid. If it is
-** an internal node, then the 64-bit integer is a child page number.
-*/
-static i64 nodeGetRowid(
-  Rtree *pRtree,       /* 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;
-  pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
-  pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
-  pCoord = pCell->aCoord;
-  for(ii=0; ii<pRtree->nDim*2; ii++){
-    readCoord(&pData[ii*4], &pCoord[ii]);
-  }
-}
-
-
-/* Forward declaration for the function that does the work of
-** the virtual table module xCreate() and xConnect() methods.
-*/
-static int rtreeInit(
-  sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int
-);
-
-/* 
-** 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 ){
-    sqlite3_finalize(pRtree->pReadNode);
-    sqlite3_finalize(pRtree->pWriteNode);
-    sqlite3_finalize(pRtree->pDeleteNode);
-    sqlite3_finalize(pRtree->pReadRowid);
-    sqlite3_finalize(pRtree->pWriteRowid);
-    sqlite3_finalize(pRtree->pDeleteRowid);
-    sqlite3_finalize(pRtree->pReadParent);
-    sqlite3_finalize(pRtree->pWriteParent);
-    sqlite3_finalize(pRtree->pDeleteParent);
-    sqlite3_free(pRtree);
-  }
-}
-
-/* 
-** Rtree virtual table module xDisconnect method.
-*/
-static int rtreeDisconnect(sqlite3_vtab *pVtab){
-  rtreeRelease((Rtree *)pVtab);
-  return SQLITE_OK;
-}
-
-/* 
-** Rtree virtual table module xDestroy method.
-*/
-static int rtreeDestroy(sqlite3_vtab *pVtab){
-  Rtree *pRtree = (Rtree *)pVtab;
-  int rc;
-  char *zCreate = sqlite3_mprintf(
-    "DROP TABLE '%q'.'%q_node';"
-    "DROP TABLE '%q'.'%q_rowid';"
-    "DROP TABLE '%q'.'%q_parent';",
-    pRtree->zDb, pRtree->zName, 
-    pRtree->zDb, pRtree->zName,
-    pRtree->zDb, pRtree->zName
-  );
-  if( !zCreate ){
-    rc = SQLITE_NOMEM;
-  }else{
-    rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
-    sqlite3_free(zCreate);
-  }
-  if( rc==SQLITE_OK ){
-    rtreeRelease(pRtree);
-  }
-
-  return rc;
-}
-
-/* 
-** Rtree virtual table module xOpen method.
-*/
-static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
-  int rc = SQLITE_NOMEM;
-  RtreeCursor *pCsr;
-
-  pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));
-  if( pCsr ){
-    memset(pCsr, 0, sizeof(RtreeCursor));
-    pCsr->base.pVtab = pVTab;
-    rc = SQLITE_OK;
-  }
-  *ppCursor = (sqlite3_vtab_cursor *)pCsr;
-
-  return rc;
-}
-
-
-/*
-** Free the RtreeCursor.aConstraint[] array and its contents.
-*/
-static void freeCursorConstraints(RtreeCursor *pCsr){
-  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;
-  }
-}
-
-/* 
-** Rtree virtual table module xClose method.
-*/
-static int rtreeClose(sqlite3_vtab_cursor *cur){
-  Rtree *pRtree = (Rtree *)(cur->pVtab);
-  int ii;
-  RtreeCursor *pCsr = (RtreeCursor *)cur;
-  freeCursorConstraints(pCsr);
-  sqlite3_free(pCsr->aPoint);
-  for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
-  sqlite3_free(pCsr);
-  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 three versions of this macro, one each for little-endian and
-** big-endian processors and a third generic implementation.  The endian-
-** specific implementations are much faster and are preferred if the
-** processor endianness is known at compile-time.  The SQLITE_BYTEORDER
-** macro is part of sqliteInt.h and hence the endian-specific
-** implementation will only be used if this module is compiled as part
-** of the amalgamation.
-*/
-#if defined(SQLITE_BYTEORDER) && 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 defined(SQLITE_BYTEORDER) && 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 */
-){
-  int i;                                                /* Loop counter */
-  sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
-  int nCoord = pInfo->nCoord;                           /* No. of coordinates */
-  int rc;                                             /* Callback return code */
-  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;
-  for(i=0; i<nCoord; i++, pCellData += 4){
-    RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]);
-  }
-  if( pConstraint->op==RTREE_MATCH ){
-    rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
-                              nCoord, aCoord, &i);
-    if( i==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 );
-  switch( p->op ){
-    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 );
-  pCellData += 8 + p->iCoord*4;
-  RTREE_DECODE_COORD(eInt, pCellData, xN);
-  switch( p->op ){
-    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;
-    }
-  }
-  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( pParent ){
-    return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
-  }
-  *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 to 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_realloc(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;
-      if( 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( 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 ){
-    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
-    if( rc ) return rc;
-    nCell = NCELL(pNode);
-    assert( nCell<200 );
-    while( p->iCell<nCell ){
-      sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
-      u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
-      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 ) break;
-      }
-      p->iCell++;
-      if( eWithin==NOT_WITHIN ) continue;
-      x.iLevel = p->iLevel - 1;
-      if( x.iLevel ){
-        x.id = readInt64(pCellData);
-        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 = 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:");
-  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 && 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( p==0 ) return SQLITE_OK;
-  if( i==0 ){
-    sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
-  }else{
-    if( rc ) return rc;
-    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);
-    }
-  }
-  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;              /* BLOB returned by geometry function */
-  sqlite3_rtree_query_info *pInfo;   /* Callback information */
-  int nBlob;                         /* Size of the geometry function blob */
-  int nExpected;                     /* Expected size of the BLOB */
-
-  /* Check that value is actually a blob. */
-  if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
-
-  /* Check that the blob is roughly the right size. */
-  nBlob = sqlite3_value_bytes(pValue);
-  if( nBlob<(int)sizeof(RtreeMatchArg) ){
-    return SQLITE_ERROR;
-  }
-
-  pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob );
-  if( !pInfo ) return SQLITE_NOMEM;
-  memset(pInfo, 0, sizeof(*pInfo));
-  pBlob = (RtreeMatchArg*)&pInfo[1];
-
-  memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
-  nExpected = (int)(sizeof(RtreeMatchArg) +
-                    pBlob->nParam*sizeof(sqlite3_value*) +
-                    (pBlob->nParam-1)*sizeof(RtreeDValue));
-  if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){
-    sqlite3_free(pInfo);
-    return SQLITE_ERROR;
-  }
-  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. */
-  freeCursorConstraints(pCsr);
-  sqlite3_free(pCsr->aPoint);
-  memset(pCsr, 0, sizeof(RtreeCursor));
-  pCsr->base.pVtab = (sqlite3_vtab*)pRtree;
-
-  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 the leaf */
-    i64 iRowid = sqlite3_value_int64(argv[0]);
-    i64 iNode = 0;
-    rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
-    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 = 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_malloc(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];
-          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->nDim*2;
-            p->pInfo->anQueue = pCsr->anQueue;
-            p->pInfo->mxLevel = pRtree->iDepth + 1;
-          }else{
-#ifdef SQLITE_RTREE_INT_ONLY
-            p->u.rValue = sqlite3_value_int64(argv[ii]);
-#else
-            p->u.rValue = sqlite3_value_double(argv[ii]);
-#endif
-          }
-        }
-      }
-    }
-    if( rc==SQLITE_OK ){
-      RtreeSearchPoint *pNew;
-      pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1);
-      if( pNew==0 ) 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;
-}
-
-/*
-** Set the pIdxInfo->estimatedRows variable to nRow. Unless this
-** extension is currently being used by a version of SQLite too old to
-** support estimatedRows. In that case this function is a no-op.
-*/
-static void setEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){
-#if SQLITE_VERSION_NUMBER>=3008002
-  if( sqlite3_libversion_number()>=3008002 ){
-    pIdxInfo->estimatedRows = nRow;
-  }
-#endif
-}
-
-/*
-** 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;
-      setEstimatedRows(pIdxInfo, 1);
-      return SQLITE_OK;
-    }
-
-    if( p->usable && (p->iColumn>0 || 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;
-        default:
-          assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
-          op = RTREE_MATCH; 
-          break;
-      }
-      zIdxStr[iIdx++] = op;
-      zIdxStr[iIdx++] = 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 + 1);
-  pIdxInfo->estimatedCost = (double)6.0 * (double)nRow;
-  setEstimatedRows(pIdxInfo, 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;
-  int ii;
-  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
-    area = (area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])));
-  }
-  return area;
-}
-
-/*
-** Return the margin length of cell p. The margin length is the sum
-** of the objects size in each dimension.
-*/
-static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
-  RtreeDValue margin = (RtreeDValue)0;
-  int ii;
-  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
-    margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
-  }
-  return margin;
-}
-
-/*
-** Store the union of cells p1 and p2 in p1.
-*/
-static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
-  int ii;
-  if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
-    for(ii=0; ii<(pRtree->nDim*2); ii+=2){
-      p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
-      p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
-    }
-  }else{
-    for(ii=0; ii<(pRtree->nDim*2); ii+=2){
-      p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
-      p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
-    }
-  }
-}
-
-/*
-** Return true if the area covered by p2 is a subset of the area covered
-** by p1. False otherwise.
-*/
-static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
-  int ii;
-  int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
-  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
-    RtreeCoord *a1 = &p1->aCoord[ii];
-    RtreeCoord *a2 = &p2->aCoord[ii];
-    if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) 
-     || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) 
-    ){
-      return 0;
-    }
-  }
-  return 1;
-}
-
-/*
-** Return the amount cell p would grow by if it were unioned with pCell.
-*/
-static 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->nDim*2); 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;
-  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;
-
-    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;
-  while( p->pParent ){
-    RtreeNode *pParent = p->pParent;
-    RtreeCell cell;
-    int iCell;
-
-    if( nodeParentIndex(pRtree, p, &iCell) ){
-      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;
-
-  int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
-
-  aaSorted = (int **)sqlite3_malloc(nByte);
-  if( !aaSorted ){
-    return SQLITE_NOMEM;
-  }
-
-  aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
-  memset(aaSorted, 0, nByte);
-  for(ii=0; ii<pRtree->nDim; ii++){
-    int jj;
-    aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
-    for(jj=0; jj<nCell; jj++){
-      aaSorted[ii][jj] = jj;
-    }
-    SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
-  }
-
-  for(ii=0; ii<pRtree->nDim; ii++){
-    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);
-    if( pChild ){
-      nodeRelease(pRtree, pChild->pParent);
-      nodeReference(pNode);
-      pChild->pParent = pNode;
-    }
-  }
-  return xSetMapping(pRtree, iRowid, pNode->iNode);
-}
-
-static int SplitNode(
-  Rtree *pRtree,
-  RtreeNode *pNode,
-  RtreeCell *pCell,
-  int iHeight
-){
-  int i;
-  int newCellIsRight = 0;
-
-  int rc = SQLITE_OK;
-  int nCell = NCELL(pNode);
-  RtreeCell *aCell;
-  int *aiUsed;
-
-  RtreeNode *pLeft = 0;
-  RtreeNode *pRight = 0;
-
-  RtreeCell leftbbox;
-  RtreeCell rightbbox;
-
-  /* Allocate an array and populate it with a copy of pCell and 
-  ** all cells from node pLeft. Then zero the original node.
-  */
-  aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
-  if( !aCell ){
-    rc = SQLITE_NOMEM;
-    goto splitnode_out;
-  }
-  aiUsed = (int *)&aCell[nCell+1];
-  memset(aiUsed, 0, sizeof(int)*(nCell+1));
-  for(i=0; i<nCell; i++){
-    nodeGetCell(pRtree, pNode, i, &aCell[i]);
-  }
-  nodeZero(pRtree, pNode);
-  memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
-  nCell++;
-
-  if( pNode->iNode==1 ){
-    pRight = nodeNew(pRtree, pNode);
-    pLeft = nodeNew(pRtree, pNode);
-    pRtree->iDepth++;
-    pNode->isDirty = 1;
-    writeInt16(pNode->zData, pRtree->iDepth);
-  }else{
-    pLeft = pNode;
-    pRight = nodeNew(pRtree, pLeft->pParent);
-    nodeReference(pLeft);
-  }
-
-  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( rc==SQLITE_OK ){
-      nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
-      rc = AdjustTree(pRtree, pParent, &leftbbox);
-    }
-    if( 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 ){
-        rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
-      }
-    }
-    rc = sqlite3_reset(pRtree->pReadParent);
-    if( rc==SQLITE_OK ) rc = rc2;
-    if( rc==SQLITE_OK && !pChild->pParent ) 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);
-  }
-  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_malloc(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( 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 newRowid(Rtree *pRtree, i64 *piRowid){
-  int rc;
-  sqlite3_bind_null(pRtree->pWriteRowid, 1);
-  sqlite3_bind_null(pRtree->pWriteRowid, 2);
-  sqlite3_step(pRtree->pWriteRowid);
-  rc = sqlite3_reset(pRtree->pWriteRowid);
-  *piRowid = sqlite3_last_insert_rowid(pRtree->db);
-  return rc;
-}
-
-/*
-** 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;               /* 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);
-  }
-
-  /* Delete the cell in question from the leaf node. */
-  if( rc==SQLITE_OK ){
-    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;
-    i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
-    rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
-    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;
-    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) */
-
-
-/*
-** The xUpdate method for rtree module virtual tables.
-*/
-static int rtreeUpdate(
-  sqlite3_vtab *pVtab, 
-  int nData, 
-  sqlite3_value **azData, 
-  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 */
-
-  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;
-
-    /* Populate the cell.aCoord[] array. The first coordinate is azData[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.
-    */
-    assert( nData<=(pRtree->nDim*2 + 3) );
-
-#ifndef SQLITE_RTREE_INT_ONLY
-    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
-      for(ii=0; ii<nData-4; ii+=2){
-        cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]);
-        cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]);
-        if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
-          rc = SQLITE_CONSTRAINT;
-          goto constraint;
-        }
-      }
-    }else
-#endif
-    {
-      for(ii=0; ii<nData-4; ii+=2){
-        cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
-        cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
-        if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
-          rc = SQLITE_CONSTRAINT;
-          goto constraint;
-        }
-      }
-    }
-
-    /* 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(azData[2])!=SQLITE_NULL ){
-      cell.iRowid = sqlite3_value_int64(azData[2]);
-      if( sqlite3_value_type(azData[0])==SQLITE_NULL
-       || sqlite3_value_int64(azData[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 = SQLITE_CONSTRAINT;
-            goto constraint;
-          }
-        }
-      }
-      bHaveRowid = 1;
-    }
-  }
-
-  /* If azData[0] is not an SQL NULL value, it is the rowid of a
-  ** record to delete from the r-tree table. The following block does
-  ** just that.
-  */
-  if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
-    rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(azData[0]));
-  }
-
-  /* If the azData[] array contains more than one element, elements
-  ** (azData[2]..azData[argc-1]) contain a new record to insert into
-  ** the r-tree structure.
-  */
-  if( rc==SQLITE_OK && nData>1 ){
-    /* Insert the new record into the r-tree */
-    RtreeNode *pLeaf = 0;
-
-    /* Figure out the rowid of the new row. */
-    if( bHaveRowid==0 ){
-      rc = newRowid(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;
-      }
-    }
-  }
-
-constraint:
-  rtreeRelease(pRtree);
-  return rc;
-}
-
-/*
-** The xRename method for rtree module virtual tables.
-*/
-static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
-  Rtree *pRtree = (Rtree *)pVtab;
-  int rc = SQLITE_NOMEM;
-  char *zSql = sqlite3_mprintf(
-    "ALTER TABLE %Q.'%q_node'   RENAME TO \"%w_node\";"
-    "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
-    "ALTER TABLE %Q.'%q_rowid'  RENAME TO \"%w_rowid\";"
-    , pRtree->zDb, pRtree->zName, zNewName 
-    , pRtree->zDb, pRtree->zName, zNewName 
-    , pRtree->zDb, pRtree->zName, zNewName
-  );
-  if( zSql ){
-    rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
-    sqlite3_free(zSql);
-  }
-  return rc;
-}
-
-/*
-** 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 = 0;
-
-  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);
-    }else if( rc!=SQLITE_NOMEM ){
-      rc = SQLITE_OK;
-    }
-
-    if( rc==SQLITE_OK ){
-      if( nRow==0 ){
-        pRtree->nRowEst = RTREE_DEFAULT_ROWEST;
-      }else{
-        pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST);
-      }
-    }
-    sqlite3_free(zSql);
-  }
-
-  return rc;
-}
-
-static sqlite3_module rtreeModule = {
-  0,                          /* iVersion */
-  rtreeCreate,                /* xCreate - create a table */
-  rtreeConnect,               /* xConnect - connect to an existing table */
-  rtreeBestIndex,             /* xBestIndex - Determine search strategy */
-  rtreeDisconnect,            /* xDisconnect - Disconnect from a table */
-  rtreeDestroy,               /* xDestroy - Drop a table */
-  rtreeOpen,                  /* xOpen - open a cursor */
-  rtreeClose,                 /* xClose - close a cursor */
-  rtreeFilter,                /* xFilter - configure scan constraints */
-  rtreeNext,                  /* xNext - advance a cursor */
-  rtreeEof,                   /* xEof */
-  rtreeColumn,                /* xColumn - read data */
-  rtreeRowid,                 /* xRowid - read data */
-  rtreeUpdate,                /* xUpdate - write data */
-  0,                          /* xBegin - begin transaction */
-  0,                          /* xSync - sync transaction */
-  0,                          /* xCommit - commit transaction */
-  0,                          /* xRollback - rollback transaction */
-  0,                          /* xFindFunction - function overloading */
-  rtreeRename,                /* xRename - rename the table */
-  0,                          /* xSavepoint */
-  0,                          /* xRelease */
-  0                           /* xRollbackTo */
-};
-
-static int rtreeSqlInit(
-  Rtree *pRtree, 
-  sqlite3 *db, 
-  const char *zDb, 
-  const char *zPrefix, 
-  int isCreate
-){
-  int rc = SQLITE_OK;
-
-  #define N_STATEMENT 9
-  static const char *azSql[N_STATEMENT] = {
-    /* Read and write the xxx_node table */
-    "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
-    "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
-    "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
-
-    /* Read and write the xxx_rowid table */
-    "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
-    "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
-    "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
-
-    /* Read and write the xxx_parent table */
-    "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
-    "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
-    "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
-  };
-  sqlite3_stmt **appStmt[N_STATEMENT];
-  int i;
-
-  pRtree->db = db;
-
-  if( isCreate ){
-    char *zCreate = sqlite3_mprintf(
-"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
-"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
-"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
-                                  " parentnode INTEGER);"
-"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
-      zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
-    );
-    if( !zCreate ){
-      return SQLITE_NOMEM;
-    }
-    rc = sqlite3_exec(db, zCreate, 0, 0, 0);
-    sqlite3_free(zCreate);
-    if( rc!=SQLITE_OK ){
-      return rc;
-    }
-  }
-
-  appStmt[0] = &pRtree->pReadNode;
-  appStmt[1] = &pRtree->pWriteNode;
-  appStmt[2] = &pRtree->pDeleteNode;
-  appStmt[3] = &pRtree->pReadRowid;
-  appStmt[4] = &pRtree->pWriteRowid;
-  appStmt[5] = &pRtree->pDeleteRowid;
-  appStmt[6] = &pRtree->pReadParent;
-  appStmt[7] = &pRtree->pWriteParent;
-  appStmt[8] = &pRtree->pDeleteParent;
-
-  rc = rtreeQueryStat1(db, pRtree);
-  for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
-    char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
-    if( zSql ){
-      rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); 
-    }else{
-      rc = SQLITE_NOMEM;
-    }
-    sqlite3_free(zSql);
-  }
-
-  return rc;
-}
-
-/*
-** 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));
-    }
-  }
-
-  sqlite3_free(zSql);
-  return rc;
-}
-
-/* 
-** 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);
-
-  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 */
-  };
-
-  int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
-  if( aErrMsg[iErr] ){
-    *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
-    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_malloc(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->nDim = (argc-4)/2;
-  pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
-  pRtree->eCoordType = eCoordType;
-  memcpy(pRtree->zDb, argv[1], nDb);
-  memcpy(pRtree->zName, argv[2], nName);
-
-  /* Figure out the node size to use. */
-  rc = getNodeSize(db, pRtree, isCreate, pzErr);
-
-  /* Create/Connect to the underlying relational database schema. If
-  ** that is successful, call sqlite3_declare_vtab() to configure
-  ** the r-tree table schema.
-  */
-  if( rc==SQLITE_OK ){
-    if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
-      *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
-    }else{
-      char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
-      char *zTmp;
-      int ii;
-      for(ii=4; zSql && ii<argc; ii++){
-        zTmp = zSql;
-        zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
-        sqlite3_free(zTmp);
-      }
-      if( zSql ){
-        zTmp = zSql;
-        zSql = sqlite3_mprintf("%s);", zTmp);
-        sqlite3_free(zTmp);
-      }
-      if( !zSql ){
-        rc = SQLITE_NOMEM;
-      }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
-        *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
-      }
-      sqlite3_free(zSql);
-    }
-  }
-
-  if( rc==SQLITE_OK ){
-    *ppVtab = (sqlite3_vtab *)pRtree;
-  }else{
-    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){
-  char *zText = 0;
-  RtreeNode node;
-  Rtree tree;
-  int ii;
-
-  UNUSED_PARAMETER(nArg);
-  memset(&node, 0, sizeof(RtreeNode));
-  memset(&tree, 0, sizeof(Rtree));
-  tree.nDim = sqlite3_value_int(apArg[0]);
-  tree.nBytesPerCell = 8 + 8 * tree.nDim;
-  node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
-
-  for(ii=0; ii<NCELL(&node); ii++){
-    char zCell[512];
-    int nCell = 0;
-    RtreeCell cell;
-    int jj;
-
-    nodeGetCell(&tree, &node, ii, &cell);
-    sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
-    nCell = (int)strlen(zCell);
-    for(jj=0; jj<tree.nDim*2; jj++){
-#ifndef SQLITE_RTREE_INT_ONLY
-      sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
-                       (double)cell.aCoord[jj].f);
-#else
-      sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
-                       cell.aCoord[jj].i);
-#endif
-      nCell = (int)strlen(zCell);
-    }
-
-    if( zText ){
-      char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
-      sqlite3_free(zText);
-      zText = zTextNew;
-    }else{
-      zText = sqlite3_mprintf("{%s}", zCell);
-    }
-  }
-  
-  sqlite3_result_text(ctx, zText, -1, sqlite3_free);
-}
-
-/* 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]);
-    sqlite3_result_int(ctx, readInt16(zBlob));
-  }
-}
-
-/*
-** 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 ){
-#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);
-  }
-
-  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;
-  int nBlob;
-  int memErr = 0;
-
-  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue)
-           + nArg*sizeof(sqlite3_value*);
-  pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
-  if( !pBlob ){
-    sqlite3_result_error_nomem(ctx);
-  }else{
-    int i;
-    pBlob->magic = RTREE_GEOMETRY_MAGIC;
-    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_blob(ctx, pBlob, nBlob, 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 ) 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
diff --git a/lib/libsqlite3/ext/rtree/rtree.h b/lib/libsqlite3/ext/rtree/rtree.h
deleted file mode 100644
index 1fdbcccc5ef..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree.h
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
-** 2008 May 26
-**
-** 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 header file is used by programs that want to link against the
-** RTREE library.  All it does is declare the sqlite3RtreeInit() interface.
-*/
-#include "sqlite3.h"
-
-#ifdef __cplusplus
-extern "C" {
-#endif  /* __cplusplus */
-
-int sqlite3RtreeInit(sqlite3 *db);
-
-#ifdef __cplusplus
-}  /* extern "C" */
-#endif  /* __cplusplus */
diff --git a/lib/libsqlite3/ext/rtree/rtree1.test b/lib/libsqlite3/ext/rtree/rtree1.test
deleted file mode 100644
index c9192de192e..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree1.test
+++ /dev/null
@@ -1,593 +0,0 @@
-# 2008 Feb 19
-#
-# 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.
-#
-#***********************************************************************
-#
-# The focus of this file is testing the r-tree extension.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-}
-source [file join [file dirname [info script]] rtree_util.tcl]
-source $testdir/tester.tcl
-set testprefix rtree1
-
-# Test plan:
-#
-#   rtree-1.*: Creating/destroying r-tree tables.
-#   rtree-2.*: Test the implicit constraints - unique rowid and
-#              (coord[N]<=coord[N+1]) for even values of N. Also
-#              automatic assigning of rowid values.
-#   rtree-3.*: Linear scans of r-tree data.
-#   rtree-4.*: Test INSERT
-#   rtree-5.*: Test DELETE
-#   rtree-6.*: Test UPDATE
-#   rtree-7.*: Test renaming an r-tree table.
-#   rtree-8.*: Test constrained scans of r-tree data.
-#
-#   rtree-12.*: Test that on-conflict clauses are supported.
-#   rtree-13.*: Test that bug [d2889096e7bdeac6d] has been fixed.
-#   rtree-14.*: Test if a non-integer is inserted into the PK column of an
-#               r-tree table, it is converted to an integer before being
-#               inserted. Also that if a non-numeric is inserted into one
-#               of the min/max dimension columns, it is converted to the
-#               required type before being inserted.
-#
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-1.* test CREATE and DROP table statements.
-#
-
-# Test creating and dropping an rtree table.
-#
-do_test rtree-1.1.1 {
-  execsql { CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2) }
-} {}
-do_test rtree-1.1.2 {
-  execsql { SELECT name FROM sqlite_master ORDER BY name }
-} {t1 t1_node t1_parent t1_rowid}
-do_test rtree-1.1.3 {
-  execsql { 
-    DROP TABLE t1; 
-    SELECT name FROM sqlite_master ORDER BY name;
-  }
-} {}
-
-# Test creating and dropping an rtree table with an odd name in
-# an attached database.
-#
-do_test rtree-1.2.1 {
-  file delete -force test2.db
-  execsql {
-    ATTACH 'test2.db' AS aux;
-    CREATE VIRTUAL TABLE aux.'a" "b' USING rtree(ii, x1, x2, y1, y2);
-  }
-} {}
-do_test rtree-1.2.2 {
-  execsql { SELECT name FROM sqlite_master ORDER BY name }
-} {}
-do_test rtree-1.2.3 {
-  execsql { SELECT name FROM aux.sqlite_master ORDER BY name }
-} {{a" "b} {a" "b_node} {a" "b_parent} {a" "b_rowid}}
-do_test rtree-1.2.4 {
-  execsql { 
-    DROP TABLE aux.'a" "b'; 
-    SELECT name FROM aux.sqlite_master ORDER BY name;
-  }
-} {}
-
-# Test that the logic for checking the number of columns specified
-# for an rtree table. Acceptable values are odd numbers between 3 and
-# 11, inclusive.
-#
-set cols [list i1 i2 i3 i4 i5 i6 i7 i8 i9 iA iB iC iD iE iF iG iH iI iJ iK]
-for {set nCol 1} {$nCol<[llength $cols]} {incr nCol} {
-
-  set columns [join [lrange $cols 0 [expr {$nCol-1}]] ,]
-
-  set X {0 {}}
-  if {$nCol%2 == 0}  { set X {1 {Wrong number of columns for an rtree table}} }
-  if {$nCol < 3}     { set X {1 {Too few columns for an rtree table}} }
-  if {$nCol > 11}    { set X {1 {Too many columns for an rtree table}} }
-
-  do_test rtree-1.3.$nCol {
-    catchsql " 
-      CREATE VIRTUAL TABLE t1 USING rtree($columns);
-    "
-  } $X
-
-  catchsql { DROP TABLE t1 }
-}
-
-# Like execsql except display output as integer where that can be
-# done without loss of information.
-#
-proc execsql_intout {sql} {
-  set out {}
-  foreach term [execsql $sql] {
-    regsub {\.0$} $term {} term
-    lappend out $term
-  }
-  return $out
-}
-
-# Test that it is possible to open an existing database that contains
-# r-tree tables.
-#
-do_execsql_test rtree-1.4.1a {
-  CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
-  INSERT INTO t1 VALUES(1, 5.0, 10.0);
-  SELECT substr(hex(data),1,40) FROM t1_node;
-} {00000001000000000000000140A0000041200000}
-do_execsql_test rtree-1.4.1b {
-  INSERT INTO t1 VALUES(2, 15.0, 20.0);
-} {}
-do_test rtree-1.4.2 {
-  db close
-  sqlite3 db test.db
-  execsql_intout { SELECT * FROM t1 ORDER BY ii }
-} {1 5 10 2 15 20}
-do_test rtree-1.4.3 {
-  execsql { DROP TABLE t1 }
-} {}
-
-# Test that it is possible to create an r-tree table with ridiculous
-# column names.
-#
-do_test rtree-1.5.1 {
-  execsql_intout {
-    CREATE VIRTUAL TABLE t1 USING rtree("the key", "x dim.", "x2'dim");
-    INSERT INTO t1 VALUES(1, 2, 3);
-    SELECT "the key", "x dim.", "x2'dim" FROM t1;
-  }
-} {1 2 3}
-do_test rtree-1.5.1 {
-  execsql { DROP TABLE t1 }
-} {}
-
-# Force the r-tree constructor to fail.
-#
-do_test rtree-1.6.1 {
-  execsql { CREATE TABLE t1_rowid(a); }
-  catchsql {
-    CREATE VIRTUAL TABLE t1 USING rtree("the key", "x dim.", "x2'dim");
-  }
-} {1 {table "t1_rowid" already exists}}
-do_test rtree-1.6.1 {
-  execsql { DROP TABLE t1_rowid }
-} {}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-2.* 
-#
-do_test rtree-2.1.1 {
-  execsql { 
-    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
-    SELECT * FROM t1;
-  }
-} {}
-
-do_test rtree-2.1.2 {
-  execsql { INSERT INTO t1 VALUES(NULL, 1, 3, 2, 4) }
-  execsql_intout { SELECT * FROM t1 }
-} {1 1 3 2 4}
-do_test rtree-2.1.3 {
-  execsql { INSERT INTO t1 VALUES(NULL, 1, 3, 2, 4) }
-  execsql { SELECT rowid FROM t1 ORDER BY rowid }
-} {1 2}
-do_test rtree-2.1.3 {
-  execsql { INSERT INTO t1 VALUES(NULL, 1, 3, 2, 4) }
-  execsql { SELECT ii FROM t1 ORDER BY ii }
-} {1 2 3}
-
-do_test rtree-2.2.1 {
-  catchsql { INSERT INTO t1 VALUES(2, 1, 3, 2, 4) }
-} {1 {constraint failed}}
-do_test rtree-2.2.2 {
-  catchsql { INSERT INTO t1 VALUES(4, 1, 3, 4, 2) }
-} {1 {constraint failed}}
-do_test rtree-2.2.3 {
-  catchsql { INSERT INTO t1 VALUES(4, 3, 1, 2, 4) }
-} {1 {constraint failed}}
-do_test rtree-2.2.4 {
-  execsql { SELECT ii FROM t1 ORDER BY ii }
-} {1 2 3}
-
-do_test rtree-2.X {
-  execsql { DROP TABLE t1 }
-} {}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-3.* test linear scans of r-tree table data. To test
-# this we have to insert some data into an r-tree, but that is not the
-# focus of these tests.
-#
-do_test rtree-3.1.1 {
-  execsql { 
-    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
-    SELECT * FROM t1;
-  }
-} {}
-do_test rtree-3.1.2 {
-  execsql_intout { 
-    INSERT INTO t1 VALUES(5, 1, 3, 2, 4);
-    SELECT * FROM t1;
-  }
-} {5 1 3 2 4}
-do_test rtree-3.1.3 {
-  execsql_intout {
-    INSERT INTO t1 VALUES(6, 2, 6, 4, 8);
-    SELECT * FROM t1;
-  }
-} {5 1 3 2 4 6 2 6 4 8}
-
-# Test the constraint on the coordinates (c[i]<=c[i+1] where (i%2==0)):
-do_test rtree-3.2.1 {
-  catchsql { INSERT INTO t1 VALUES(7, 2, 6, 4, 3) }
-} {1 {constraint failed}}
-do_test rtree-3.2.2 {
-  catchsql { INSERT INTO t1 VALUES(8, 2, 6, 3, 3) }
-} {0 {}}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-5.* test DELETE operations.
-#
-do_test rtree-5.1.1 {
-  execsql { CREATE VIRTUAL TABLE t2 USING rtree(ii, x1, x2) }
-} {}
-do_test rtree-5.1.2 {
-  execsql_intout { 
-    INSERT INTO t2 VALUES(1, 10, 20);
-    INSERT INTO t2 VALUES(2, 30, 40);
-    INSERT INTO t2 VALUES(3, 50, 60);
-    SELECT * FROM t2 ORDER BY ii;
-  }
-} {1 10 20 2 30 40 3 50 60}
-do_test rtree-5.1.3 {
-  execsql_intout { 
-    DELETE FROM t2 WHERE ii=2;
-    SELECT * FROM t2 ORDER BY ii;
-  }
-} {1 10 20 3 50 60}
-do_test rtree-5.1.4 {
-  execsql_intout { 
-    DELETE FROM t2 WHERE ii=1;
-    SELECT * FROM t2 ORDER BY ii;
-  }
-} {3 50 60}
-do_test rtree-5.1.5 {
-  execsql { 
-    DELETE FROM t2 WHERE ii=3;
-    SELECT * FROM t2 ORDER BY ii;
-  }
-} {}
-do_test rtree-5.1.6 {
-  execsql { SELECT * FROM t2_rowid }
-} {}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-5.* test UPDATE operations.
-#
-do_test rtree-6.1.1 {
-  execsql { CREATE VIRTUAL TABLE t3 USING rtree(ii, x1, x2, y1, y2) }
-} {}
-do_test rtree-6.1.2 {
-  execsql_intout {
-    INSERT INTO t3 VALUES(1, 2, 3, 4, 5);
-    UPDATE t3 SET x2=5;
-    SELECT * FROM t3;
-  }
-} {1 2 5 4 5}
-do_test rtree-6.1.3 {
-  execsql { UPDATE t3 SET ii = 2 }
-  execsql_intout { SELECT * FROM t3 }
-} {2 2 5 4 5}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-7.* test rename operations.
-#
-do_test rtree-7.1.1 {
-  execsql {
-    CREATE VIRTUAL TABLE t4 USING rtree(ii, x1, x2, y1, y2, z1, z2);
-    INSERT INTO t4 VALUES(1, 2, 3, 4, 5, 6, 7);
-  }
-} {}
-do_test rtree-7.1.2 {
-  execsql { ALTER TABLE t4 RENAME TO t5 }
-  execsql_intout { SELECT * FROM t5 }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.1.3 {
-  db close
-  sqlite3 db test.db
-  execsql_intout { SELECT * FROM t5 }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.1.4 {
-  execsql { ALTER TABLE t5 RENAME TO 'raisara "one"'''}
-  execsql_intout { SELECT * FROM "raisara ""one""'" }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.1.5 {
-  execsql_intout { SELECT * FROM 'raisara "one"''' }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.1.6 {
-  execsql { ALTER TABLE "raisara ""one""'" RENAME TO "abc 123" }
-  execsql_intout { SELECT * FROM "abc 123" }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.1.7 {
-  db close
-  sqlite3 db test.db
-  execsql_intout { SELECT * FROM "abc 123" }
-} {1 2 3 4 5 6 7}
-
-# An error midway through a rename operation.
-do_test rtree-7.2.1 {
-  execsql { 
-    CREATE TABLE t4_node(a);
-  }
-  catchsql { ALTER TABLE "abc 123" RENAME TO t4 }
-} {1 {SQL logic error or missing database}}
-do_test rtree-7.2.2 {
-  execsql_intout { SELECT * FROM "abc 123" }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.2.3 {
-  execsql { 
-    DROP TABLE t4_node;
-    CREATE TABLE t4_rowid(a);
-  }
-  catchsql { ALTER TABLE "abc 123" RENAME TO t4 }
-} {1 {SQL logic error or missing database}}
-do_test rtree-7.2.4 {
-  db close
-  sqlite3 db test.db
-  execsql_intout { SELECT * FROM "abc 123" }
-} {1 2 3 4 5 6 7}
-do_test rtree-7.2.5 {
-  execsql { DROP TABLE t4_rowid }
-  execsql { ALTER TABLE "abc 123" RENAME TO t4 }
-  execsql_intout { SELECT * FROM t4 }
-} {1 2 3 4 5 6 7}
-
-
-#----------------------------------------------------------------------------
-# Test cases rtree-8.*
-#
-
-# Test that the function to determine if a leaf cell is part of the
-# result set works.
-do_test rtree-8.1.1 {
-  execsql {
-    CREATE VIRTUAL TABLE t6 USING rtree(ii, x1, x2);
-    INSERT INTO t6 VALUES(1, 3, 7);
-    INSERT INTO t6 VALUES(2, 4, 6);
-  }
-} {}
-do_test rtree-8.1.2 { execsql { SELECT ii FROM t6 WHERE x1>2 } } {1 2}
-do_test rtree-8.1.3 { execsql { SELECT ii FROM t6 WHERE x1>3 } } {2}
-do_test rtree-8.1.4 { execsql { SELECT ii FROM t6 WHERE x1>4 } } {}
-do_test rtree-8.1.5 { execsql { SELECT ii FROM t6 WHERE x1>5 } } {}
-do_test rtree-8.1.6 { execsql { SELECT ii FROM t6 WHERE x1<3 } } {}
-do_test rtree-8.1.7 { execsql { SELECT ii FROM t6 WHERE x1<4 } } {1}
-do_test rtree-8.1.8 { execsql { SELECT ii FROM t6 WHERE x1<5 } } {1 2}
-
-#----------------------------------------------------------------------------
-# Test cases rtree-9.*
-#
-# Test that ticket #3549 is fixed.
-do_test rtree-9.1 {
-  execsql {
-    CREATE TABLE foo (id INTEGER PRIMARY KEY);
-    CREATE VIRTUAL TABLE bar USING rtree (id, minX, maxX, minY, maxY);
-    INSERT INTO foo VALUES (null);
-    INSERT INTO foo SELECT null FROM foo;
-    INSERT INTO foo SELECT null FROM foo;
-    INSERT INTO foo SELECT null FROM foo;
-    INSERT INTO foo SELECT null FROM foo;
-    INSERT INTO foo SELECT null FROM foo;
-    INSERT INTO foo SELECT null FROM foo;
-    DELETE FROM foo WHERE id > 40;
-    INSERT INTO bar SELECT NULL, 0, 0, 0, 0 FROM foo;
-  }
-} {}
-
-# This used to crash.
-do_test rtree-9.2 {
-  execsql {
-    SELECT count(*) FROM bar b1, bar b2, foo s1 WHERE s1.id = b1.id;
-  }
-} {1600}
-do_test rtree-9.3 {
-  execsql {
-    SELECT count(*) FROM bar b1, bar b2, foo s1 
-    WHERE b1.minX <= b2.maxX AND s1.id = b1.id;
-  }
-} {1600}
-
-#-------------------------------------------------------------------------
-# Ticket #3970: Check that the error message is meaningful when a 
-# keyword is used as a column name.
-#
-do_test rtree-10.1 {
-  catchsql { CREATE VIRTUAL TABLE t7 USING rtree(index, x1, y1, x2, y2) }
-} {1 {near "index": syntax error}}
-
-#-------------------------------------------------------------------------
-# Test last_insert_rowid().
-# 
-do_test rtree-11.1 {
-  execsql {
-    CREATE VIRTUAL TABLE t8 USING rtree(idx, x1, x2, y1, y2);
-    INSERT INTO t8 VALUES(1, 1.0, 1.0, 2.0, 2.0);
-    SELECT last_insert_rowid();
-  }
-} {1}
-do_test rtree-11.2 {
-  execsql {
-    INSERT INTO t8 VALUES(NULL, 1.0, 1.0, 2.0, 2.0);
-    SELECT last_insert_rowid();
-  }
-} {2}
-
-#-------------------------------------------------------------------------
-# Test on-conflict clause handling.
-#
-db_delete_and_reopen
-do_execsql_test 12.0.1 {
-  CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
-  INSERT INTO t1 VALUES(1,   1, 2, 3, 4);
-  SELECT substr(hex(data),1,56) FROM t1_node;
-} {00000001000000000000000100000001000000020000000300000004}
-do_execsql_test 12.0.2 {
-  INSERT INTO t1 VALUES(2,   2, 3, 4, 5);
-  INSERT INTO t1 VALUES(3,   3, 4, 5, 6);
-
-  CREATE TABLE source(idx, x1, x2, y1, y2);
-  INSERT INTO source VALUES(5, 8, 8, 8, 8);
-  INSERT INTO source VALUES(2, 7, 7, 7, 7);
-}
-db_save_and_close
-foreach {tn sql_template testdata} {
-  1    "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" {
-    ROLLBACK 0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
-    ABORT    0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    IGNORE   0 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    FAIL     0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    REPLACE  0 0 {1 1 2 3 4   2 7 7 7 7   3 3 4 5 6   4 4 5 6 7}
-  }
-
-  2    "INSERT %CONF% INTO t1 SELECT * FROM source" {
-    ROLLBACK 1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
-    ABORT    1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    IGNORE   1 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7  5 8 8 8 8}
-    FAIL     1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7  5 8 8 8 8}
-    REPLACE  1 0 {1 1 2 3 4   2 7 7 7 7   3 3 4 5 6   4 4 5 6 7  5 8 8 8 8}
-  }
-
-  3    "UPDATE %CONF% t1 SET idx = 2 WHERE idx = 4" {
-    ROLLBACK 1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
-    ABORT    1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    IGNORE   1 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    FAIL     1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    REPLACE  1 0 {1 1 2 3 4   2 4 5 6 7   3 3 4 5 6}
-  }
-
-  3    "UPDATE %CONF% t1 SET idx = ((idx+1)%5)+1 WHERE idx > 2" {
-    ROLLBACK 1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
-    ABORT    1 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    IGNORE   1 0 {1 1 2 3 4   2 2 3 4 5               4 4 5 6 7   5 3 4 5 6}
-    FAIL     1 1 {1 1 2 3 4   2 2 3 4 5               4 4 5 6 7   5 3 4 5 6}
-    REPLACE  1 0 {1 4 5 6 7   2 2 3 4 5                           5 3 4 5 6}
-  }
-
-  4    "INSERT %CONF% INTO t1 VALUES(2, 7, 6, 7, 7)" {
-    ROLLBACK 0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
-    ABORT    0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    IGNORE   0 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    FAIL     0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-    REPLACE  0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
-  }
-
-} {
-  foreach {mode uses error data} $testdata {
-    db_restore_and_reopen
-
-    set sql [string map [list %CONF% "OR $mode"] $sql_template]
-    set testname "12.$tn.[string tolower $mode]"
-
-    execsql {
-      BEGIN;
-        INSERT INTO t1 VALUES(4,   4, 5, 6, 7);
-    }
-
-    set res(0) {0 {}}
-    set res(1) {1 {constraint failed}}
-    do_catchsql_test $testname.1 $sql $res($error)
-    do_test $testname.2 [list sql_uses_stmt db $sql] $uses
-    do_execsql_test $testname.3 { SELECT * FROM t1 ORDER BY idx } $data
-
-    do_test $testname.4 { rtree_check db t1 } 0
-    db close
-  }
-}
-
-#-------------------------------------------------------------------------
-# Test that bug [d2889096e7bdeac6d] has been fixed.
-#
-reset_db
-do_execsql_test 13.1 {
-  CREATE VIRTUAL TABLE t9 USING rtree(id, xmin, xmax);
-  INSERT INTO t9 VALUES(1,0,0);            
-  INSERT INTO t9 VALUES(2,0,0);
-  SELECT * FROM t9 WHERE id IN (1, 2);
-} {1 0.0 0.0 2 0.0 0.0}
-
-do_execsql_test 13.2 {
-  WITH r(x) AS (
-    SELECT 1 UNION ALL
-    SELECT 2 UNION ALL
-    SELECT 3
-  )
-  SELECT * FROM r CROSS JOIN t9 WHERE id=x;
-} {1 1 0.0 0.0 2 2 0.0 0.0}
-
-#-------------------------------------------------------------------------
-# Test if a non-integer is inserted into the PK column of an r-tree
-# table, it is converted to an integer before being inserted. Also
-# that if a non-numeric is inserted into one of the min/max dimension
-# columns, it is converted to the required type before being inserted.
-#
-do_execsql_test 14.1 {
-  CREATE VIRTUAL TABLE t10 USING rtree(ii, x1, x2);
-}
-
-do_execsql_test 14.2 {
-  INSERT INTO t10 VALUES(NULL,   1, 2);
-  INSERT INTO t10 VALUES(NULL,   2, 3);
-  INSERT INTO t10 VALUES('4xxx', 3, 4);
-  INSERT INTO t10 VALUES(5.0,    4, 5);
-  INSERT INTO t10 VALUES(6.4,    5, 6);
-}
-do_execsql_test 14.3 {
-  SELECT * FROM t10;
-} {
-  1 1.0 2.0   2 2.0 3.0   4 3.0 4.0   5 4.0 5.0   6 5.0 6.0
-}
-
-do_execsql_test 14.4 {
-  DELETE FROM t10;
-  INSERT INTO t10 VALUES(1, 'one', 'two');
-  INSERT INTO t10 VALUES(2, '52xyz', '81...');
-}
-do_execsql_test 14.5 {
-  SELECT * FROM t10;
-} {
-  1 0.0 0.0
-  2 52.0 81.0
-}
-
-do_execsql_test 14.4 {
-  DROP TABLE t10;
-  CREATE VIRTUAL TABLE t10 USING rtree_i32(ii, x1, x2);
-  INSERT INTO t10 VALUES(1, 'one', 'two');
-  INSERT INTO t10 VALUES(2, '52xyz', '81...');
-  INSERT INTO t10 VALUES(3, 42.3, 49.9);
-}
-do_execsql_test 14.5 {
-  SELECT * FROM t10;
-} {
-  1 0 0
-  2 52 81
-  3 42 49
-}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree2.test b/lib/libsqlite3/ext/rtree/rtree2.test
deleted file mode 100644
index f5d15cc6b93..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree2.test
+++ /dev/null
@@ -1,150 +0,0 @@
-# 2008 Feb 19
-#
-# 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.
-#
-#***********************************************************************
-#
-# The focus of this file is testing the r-tree extension.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source [file join [file dirname [info script]] rtree_util.tcl]
-source $testdir/tester.tcl
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-set ::NROW   1000
-set ::NDEL     10
-set ::NSELECT 100
-
-if {[info exists G(isquick)] && $G(isquick)} {
-  set ::NROW 100
-  set ::NSELECT 10
-}
-
-foreach module {rtree_i32 rtree} {
-  for {set nDim 1} {$nDim <= 5} {incr nDim} {
-  
-    do_test rtree2-$module.$nDim.1 {
-      set cols [list]
-      foreach c [list c0 c1 c2 c3 c4 c5 c6 c7 c8 c9] {
-        lappend cols "$c REAL"
-      }
-      set cols [join [lrange $cols 0 [expr {$nDim*2-1}]] ", "]
-      execsql " 
-        CREATE VIRTUAL TABLE t1 USING ${module}(ii, $cols);
-        CREATE TABLE t2 (ii, $cols);
-      "
-    } {}
-  
-    do_test rtree2-$module.$nDim.2 {
-      db transaction {
-        for {set ii 0} {$ii < $::NROW} {incr ii} {
-          #puts "Row $ii"
-          set values [list]
-          for {set jj 0} {$jj<$nDim*2} {incr jj} {
-            lappend values [expr int(rand()*1000)]
-          }
-          set values [join $values ,]
-          #puts [rtree_treedump db t1]
-          #puts "INSERT INTO t2 VALUES($ii, $values)"
-          set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}]
-          if {$rc} {
-            incr ii -1
-          } else {
-            db eval "INSERT INTO t2 VALUES($ii, $values)"
-          }
-          #if {[rtree_check db t1]} {
-            #puts [rtree_treedump db t1]
-            #exit
-          #}
-        }
-      }
-  
-      set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
-      set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
-      set rc [expr {$t1 eq $t2}]
-      if {$rc != 1} {
-        puts $t1
-        puts $t2
-      }
-      set rc
-    } {1}
-  
-    do_test rtree2-$module.$nDim.3 {
-      rtree_check db t1
-    } 0
-  
-    set OPS [list < > <= >= =]
-    for {set ii 0} {$ii < $::NSELECT} {incr ii} {
-      do_test rtree2-$module.$nDim.4.$ii.1 {
-        set where [list]
-        foreach look_three_dots! {. . .} {
-          set colidx [expr int(rand()*($nDim*2+1))-1]
-          if {$colidx<0} {
-            set col ii
-          } else {
-            set col "c$colidx"
-          }
-          set op  [lindex $OPS [expr int(rand()*[llength $OPS])]]
-          set val [expr int(rand()*1000)]
-          lappend where "$col $op $val"
-        }
-        set where [join $where " AND "]
-  
-        set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
-        set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"]
-        set rc [expr {$t1 eq $t2}]
-        if {$rc != 1} {
-          #puts $where
-          puts $t1
-          puts $t2
-          #puts [rtree_treedump db t1]
-          #breakpoint
-          #set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"]
-          #exit
-        }
-        set rc
-      } {1}
-    }
-  
-    for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} {
-      #puts [rtree_treedump db t1]
-      do_test rtree2-$module.$nDim.5.$ii.1 {
-        execsql "DELETE FROM t2 WHERE ii <= $::ii"
-        execsql "DELETE FROM t1 WHERE ii <= $::ii"
-  
-        set t1 [execsql {SELECT * FROM t1 ORDER BY ii}]
-        set t2 [execsql {SELECT * FROM t2 ORDER BY ii}]
-        set rc [expr {$t1 eq $t2}]
-        if {$rc != 1} {
-          puts $t1
-          puts $t2
-        }
-        set rc
-      } {1}
-      do_test rtree2-$module.$nDim.5.$ii.2 {
-        rtree_check db t1
-      } {0}
-    }
-  
-    do_test rtree2-$module.$nDim.6 {
-      execsql {
-        DROP TABLE t1;
-        DROP TABLE t2;
-      }
-    } {}
-  }
-}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree3.test b/lib/libsqlite3/ext/rtree/rtree3.test
deleted file mode 100644
index fea5513069b..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree3.test
+++ /dev/null
@@ -1,237 +0,0 @@
-# 2008 Feb 19
-#
-# 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.
-#
-#***********************************************************************
-#
-# The focus of this file is testing that the r-tree correctly handles
-# out-of-memory conditions.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-source $testdir/malloc_common.tcl
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-# Test summary:
-#
-#   rtree3-1: Test OOM in simple CREATE TABLE, INSERT, DELETE and SELECT 
-#             commands on an almost empty table.
-#
-#   rtree3-2: Test OOM in a DROP TABLE command.
-#
-#   rtree3-3a: Test OOM during a transaction to insert 100 pseudo-random rows.
-#
-#   rtree3-3b: Test OOM during a transaction deleting all entries in the
-#              database constructed in [rtree3-3a] in pseudo-random order.
-#
-#   rtree3-4a: OOM during "SELECT count(*) FROM ..." on a big table.
-#
-#   rtree3-4b: OOM while deleting rows from a big table.
-#
-#   rtree3-5: Test OOM while inserting rows into a big table.
-#
-#   rtree3-6: Test OOM while deleting all rows of a table, one at a time.
-#
-#   rtree3-7: OOM during an ALTER TABLE RENAME TABLE command.
-#
-#   rtree3-8: Test OOM while registering the r-tree module with sqlite.
-#
-
-do_faultsim_test rtree3-1 -faults oom* -prep {
-  faultsim_delete_and_reopen
-} -body {
-  execsql {
-    BEGIN TRANSACTION;
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
-    INSERT INTO rt VALUES(NULL, 13, 15, 17, 19);
-    DELETE FROM rt WHERE ii = 1;
-    SELECT * FROM rt;
-    SELECT ii FROM rt WHERE ii = 2;
-    COMMIT;
-  }
-}
-
-do_test rtree3-2.prep {
-  faultsim_delete_and_reopen
-  execsql {
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
-  }
-  faultsim_save_and_close
-} {}
-do_faultsim_test rtree3-2 -faults oom* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  execsql { DROP TABLE rt } 
-}
-
-do_malloc_test rtree3-3.prep {
-  faultsim_delete_and_reopen
-  execsql {
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
-  }
-  faultsim_save_and_close
-} {}
-
-do_faultsim_test rtree3-3a -faults oom* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  db eval BEGIN
-  for {set ii 0} {$ii < 100} {incr ii} {
-    set f [expr rand()]
-    db eval {INSERT INTO rt VALUES(NULL, $f*10.0, $f*10.0, $f*15.0, $f*15.0)}
-  }
-  db eval COMMIT
-}
-faultsim_save_and_close
-
-do_faultsim_test rtree3-3b -faults oom* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  db eval BEGIN
-  for {set ii 0} {$ii < 100} {incr ii} {
-    set f [expr rand()]
-    db eval { DELETE FROM rt WHERE x1<($f*10.0) AND x1>($f*10.5) }
-  }
-  db eval COMMIT
-} 
-
-do_test rtree3-4.prep {
-  faultsim_delete_and_reopen
-  execsql {
-    BEGIN;
-    PRAGMA page_size = 512;
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-  }
-  for {set i 0} {$i < 1500} {incr i} {
-    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
-  }
-  execsql { COMMIT }
-  faultsim_save_and_close
-} {}
-
-do_faultsim_test rtree3-4a -faults oom-* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  db eval { SELECT count(*) FROM rt }
-} -test {
-  faultsim_test_result {0 1500}
-}
-
-do_faultsim_test rtree3-4b -faults oom-transient -prep {
-  faultsim_restore_and_reopen
-} -body {
-  db eval { DELETE FROM rt WHERE ii BETWEEN 1 AND 100 }
-} -test {
-  faultsim_test_result {0 {}}
-}
-
-do_test rtree3-5.prep {
-  faultsim_delete_and_reopen
-  execsql {
-    BEGIN;
-    PRAGMA page_size = 512;
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-  }
-  for {set i 0} {$i < 100} {incr i} {
-    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
-  }
-  execsql { COMMIT }
-  faultsim_save_and_close
-} {}
-do_faultsim_test rtree3-5 -faults oom-* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  for {set i 100} {$i < 110} {incr i} {
-    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
-  }
-} -test {
-  faultsim_test_result {0 {}}
-}
-
-do_test rtree3-6.prep {
-  faultsim_delete_and_reopen
-  execsql {
-    BEGIN;
-    PRAGMA page_size = 512;
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
-  }
-  for {set i 0} {$i < 50} {incr i} {
-    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
-  }
-  execsql { COMMIT }
-  faultsim_save_and_close
-} {}
-do_faultsim_test rtree3-6 -faults oom-* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  execsql BEGIN
-  for {set i 0} {$i < 50} {incr i} {
-    execsql { DELETE FROM rt WHERE ii=$i }
-  }
-  execsql COMMIT
-} -test {
-  faultsim_test_result {0 {}}
-}
-
-do_test rtree3-7.prep {
-  faultsim_delete_and_reopen
-  execsql { CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2) }
-  faultsim_save_and_close
-} {}
-do_faultsim_test rtree3-7 -faults oom-* -prep {
-  faultsim_restore_and_reopen
-} -body {
-  execsql { ALTER TABLE rt RENAME TO rt2 }
-} -test {
-  faultsim_test_result {0 {}}
-}
-
-do_faultsim_test rtree3-8 -faults oom-* -prep {
-  catch { db close }
-} -body {
-  sqlite3 db test.db
-} 
-
-do_faultsim_test rtree3-9 -faults oom-* -prep {
-  sqlite3 db :memory:
-} -body {
-  set rc [register_cube_geom db]
-  if {$rc != "SQLITE_OK"} { error $rc }
-} -test {
-  faultsim_test_result {0 {}} {1 SQLITE_NOMEM}
-}
-
-do_test rtree3-10.prep {
-  faultsim_delete_and_reopen
-  execsql { 
-    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2, z1, z2);
-    INSERT INTO rt VALUES(1,  10, 10, 10, 11, 11, 11);
-    INSERT INTO rt VALUES(2,  5, 6, 6, 7, 7, 8);
-  }
-  faultsim_save_and_close
-} {}
-do_faultsim_test rtree3-10 -faults oom-* -prep {
-  faultsim_restore_and_reopen
-  register_cube_geom db
-  execsql { SELECT * FROM rt }
-} -body {
-  execsql { SELECT ii FROM rt WHERE ii MATCH cube(4.5, 5.5, 6.5, 1, 1, 1) }
-} -test {
-  faultsim_test_result {0 2}
-}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree4.test b/lib/libsqlite3/ext/rtree/rtree4.test
deleted file mode 100644
index a3872b07356..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree4.test
+++ /dev/null
@@ -1,251 +0,0 @@
-# 2008 May 23
-#
-# 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.
-#
-#***********************************************************************
-#
-# Randomized test cases for the rtree extension.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-set ::NROW 2500
-if {[info exists G(isquick)] && $G(isquick)} {
-  set ::NROW 250
-}
-
-ifcapable !rtree_int_only {
-  # Return a floating point number between -X and X.
-  # 
-  proc rand {X} {
-    return [expr {int((rand()-0.5)*1024.0*$X)/512.0}]
-  }
-  
-  # Return a positive floating point number less than or equal to X
-  #
-  proc randincr {X} {
-    while 1 {
-      set r [expr {int(rand()*$X*32.0)/32.0}]
-      if {$r>0.0} {return $r}
-    }
-  }
-} else {
-  # For rtree_int_only, return an number between -X and X.
-  # 
-  proc rand {X} {
-    return [expr {int((rand()-0.5)*2*$X)}]
-  }
-  
-  # Return a positive integer less than or equal to X
-  #
-  proc randincr {X} {
-    while 1 {
-      set r [expr {int(rand()*$X)+1}]
-      if {$r>0} {return $r}
-    }
-  }
-}
-  
-# Scramble the $inlist into a random order.
-#
-proc scramble {inlist} {
-  set y {}
-  foreach x $inlist {
-    lappend y [list [expr {rand()}] $x]
-  }
-  set y [lsort $y]
-  set outlist {}
-  foreach x $y {
-    lappend outlist [lindex $x 1]
-  }
-  return $outlist
-}
-
-# Always use the same random seed so that the sequence of tests
-# is repeatable.
-#
-expr {srand(1234)}
-
-# Run these tests for all number of dimensions between 1 and 5.
-#
-for {set nDim 1} {$nDim<=5} {incr nDim} {
-
-  # Construct an rtree virtual table and an ordinary btree table
-  # to mirror it.  The ordinary table should be much slower (since
-  # it has to do a full table scan) but should give the exact same
-  # answers.
-  #
-  do_test rtree4-$nDim.1 {
-    set clist {}
-    set cklist {}
-    for {set i 0} {$i<$nDim} {incr i} {
-      lappend clist mn$i mx$i
-      lappend cklist "mn$i<mx$i"
-    }
-    db eval "DROP TABLE IF EXISTS rx"
-    db eval "DROP TABLE IF EXISTS bx"
-    db eval "CREATE VIRTUAL TABLE rx USING rtree(id, [join $clist ,])"
-    db eval "CREATE TABLE bx(id INTEGER PRIMARY KEY,\
-                [join $clist ,], CHECK( [join $cklist { AND }] ))"
-  } {}
-
-  # Do many insertions of small objects.  Do both overlapping and
-  # contained-within queries after each insert to verify that all
-  # is well.
-  #
-  unset -nocomplain where
-  for {set i 1} {$i<$::NROW} {incr i} {
-    # Do a random insert
-    #
-    do_test rtree4-$nDim.2.$i.1 {
-      set vlist {}
-      for {set j 0} {$j<$nDim} {incr j} {
-        set mn [rand 10000]
-        set mx [expr {$mn+[randincr 50]}]
-        lappend vlist $mn $mx
-      }
-      db eval "INSERT INTO rx VALUES(NULL, [join $vlist ,])"
-      db eval "INSERT INTO bx VALUES(NULL, [join $vlist ,])"
-    } {}
-
-    # Do a contained-in query on all dimensions
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mn$j>=$mn mx$j<=$mx
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.2 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do an overlaps query on all dimensions
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mx$j>=$mn mn$j<=$mx
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.3 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do a contained-in query with surplus contraints at the beginning.
-    # This should force a full-table scan on the rtree.
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      lappend where mn$j>-10000 mx$j<10000
-    }
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mn$j>=$mn mx$j<=$mx
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.3 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do an overlaps query with surplus contraints at the beginning.
-    # This should force a full-table scan on the rtree.
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      lappend where mn$j>=-10000 mx$j<=10000
-    }
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mx$j>$mn mn$j<$mx
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.4 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do a contained-in query with surplus contraints at the end
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mn$j>=$mn mx$j<$mx
-    }
-    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
-      lappend where mn$j>=-10000 mx$j<10000
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.5 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do an overlaps query with surplus contraints at the end
-    #
-    set where {}
-    for {set j [expr {$nDim-1}]} {$j>=0} {incr j -1} {
-      set mn [rand 10000]
-      set mx [expr {$mn+[randincr 500]}]
-      lappend where mx$j>$mn mn$j<=$mx
-    }
-    for {set j 0} {$j<$nDim} {incr j} {
-      lappend where mx$j>-10000 mn$j<=10000
-    }
-    set where "WHERE [join $where { AND }]"
-    do_test rtree4-$nDim.2.$i.6 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do a contained-in query with surplus contraints where the 
-    # constraints appear in a random order.
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn1 [rand 10000]
-      set mn2 [expr {$mn1+[randincr 100]}]
-      set mx1 [expr {$mn2+[randincr 400]}]
-      set mx2 [expr {$mx1+[randincr 100]}]
-      lappend where mn$j>=$mn1 mn$j>$mn2 mx$j<$mx1 mx$j<=$mx2
-    }
-    set where "WHERE [join [scramble $where] { AND }]"
-    do_test rtree4-$nDim.2.$i.7 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-
-    # Do an overlaps query with surplus contraints where the
-    # constraints appear in a random order.
-    #
-    set where {}
-    for {set j 0} {$j<$nDim} {incr j} {
-      set mn1 [rand 10000]
-      set mn2 [expr {$mn1+[randincr 100]}]
-      set mx1 [expr {$mn2+[randincr 400]}]
-      set mx2 [expr {$mx1+[randincr 100]}]
-      lappend where mx$j>=$mn1 mx$j>$mn2 mn$j<$mx1 mn$j<=$mx2
-    }
-    set where "WHERE [join [scramble $where] { AND }]"
-    do_test rtree4-$nDim.2.$i.8 {
-      list $where [db eval "SELECT id FROM rx $where ORDER BY id"]
-    } [list $where [db eval "SELECT id FROM bx $where ORDER BY id"]]
-  }
-
-}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree5.test b/lib/libsqlite3/ext/rtree/rtree5.test
deleted file mode 100644
index 8ff90b0cb70..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree5.test
+++ /dev/null
@@ -1,80 +0,0 @@
-# 2008 Jul 14
-#
-# 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.
-#
-#***********************************************************************
-#
-# The focus of this file is testing the r-tree extension when it is
-# configured to store values as 32 bit integers.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-do_test rtree5-1.0 {
-  execsql { CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2, y1, y2) }
-} {}
-do_test rtree5-1.1 {
-  execsql { INSERT INTO t1 VALUES(1, 5, 10, 4, 11.2) }
-} {}
-do_test rtree5-1.2 { 
-  execsql { SELECT * FROM t1 }
-} {1 5 10 4 11}
-do_test rtree5-1.3 { 
-  execsql { SELECT typeof(x1) FROM t1 }
-} {integer}
-
-do_test rtree5-1.4 { 
-  execsql { SELECT x1==5 FROM t1 }
-} {1}
-do_test rtree5-1.5 { 
-  execsql { SELECT x1==5.2 FROM t1 }
-} {0}
-do_test rtree5-1.6 { 
-  execsql { SELECT x1==5.0 FROM t1 }
-} {1}
-
-do_test rtree5-1.7 { 
-  execsql { SELECT count(*) FROM t1 WHERE x1==5 }
-} {1}
-ifcapable !rtree_int_only {
-  do_test rtree5-1.8 { 
-    execsql { SELECT count(*) FROM t1 WHERE x1==5.2 }
-  } {0}
-}
-do_test rtree5-1.9 { 
-  execsql { SELECT count(*) FROM t1 WHERE x1==5.0 }
-} {1}
-
-do_test rtree5-1.10 { 
-  execsql { SELECT (1<<31)-5, (1<<31)-1, -1*(1<<31), -1*(1<<31)+5 }
-} {2147483643 2147483647 -2147483648 -2147483643}
-do_test rtree5-1.11 { 
-  execsql { 
-    INSERT INTO t1 VALUES(2, (1<<31)-5, (1<<31)-1, -1*(1<<31), -1*(1<<31)+5) 
-  }
-} {}
-do_test rtree5-1.12 { 
-  execsql { SELECT * FROM t1 WHERE id=2 }
-} {2 2147483643 2147483647 -2147483648 -2147483643}
-do_test rtree5-1.13 { 
-  execsql { 
-    SELECT * FROM t1 WHERE 
-        x1=2147483643 AND x2=2147483647 AND 
-        y1=-2147483648 AND y2=-2147483643
-  }
-} {2 2147483643 2147483647 -2147483648 -2147483643}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree6.test b/lib/libsqlite3/ext/rtree/rtree6.test
deleted file mode 100644
index c9c87e8ad91..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree6.test
+++ /dev/null
@@ -1,162 +0,0 @@
-# 2008 Sep 1
-#
-# 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.
-#
-#***********************************************************************
-# 
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-
-ifcapable {!rtree || rtree_int_only} {
-  finish_test
-  return
-}
-
-#   Operator    Byte Value
-#   ----------------------
-#      =        0x41 ('A')
-#     <=        0x42 ('B')
-#      <        0x43 ('C')
-#     >=        0x44 ('D')
-#      >        0x45 ('E')
-#   ----------------------
-
-proc rtree_strategy {sql} {
-  set ret [list]
-  db eval "explain $sql" a {
-    if {$a(opcode) eq "VFilter"} {
-      lappend ret $a(p4)
-    }
-  }
-  set ret
-}
-
-proc query_plan {sql} {
-  set ret [list]
-  db eval "explain query plan $sql" a {
-    lappend ret $a(detail)
-  }
-  set ret
-}
-
-do_test rtree6-1.1 {
-  execsql {
-    CREATE TABLE t2(k INTEGER PRIMARY KEY, v);
-    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
-  }
-} {}
-
-do_test rtree6-1.2 {
-  rtree_strategy {SELECT * FROM t1 WHERE x1>10}
-} {E0}
-
-do_test rtree6-1.3 {
-  rtree_strategy {SELECT * FROM t1 WHERE x1<10}
-} {C0}
-
-do_test rtree6-1.4 {
-  rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
-} {C0}
-
-do_test rtree6-1.5 {
-  rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
-} {C0}
-
-do_eqp_test rtree6.2.1 {
-  SELECT * FROM t1,t2 WHERE k=+ii AND x1<10
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
-  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
-}
-
-do_eqp_test rtree6.2.2 {
-  SELECT * FROM t1,t2 WHERE k=ii AND x1<10
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
-  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
-}
-
-do_eqp_test rtree6.2.3 {
-  SELECT * FROM t1,t2 WHERE k=ii
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
-  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
-}
-
-do_eqp_test rtree6.2.4.1 {
-  SELECT * FROM t1,t2 WHERE v=+ii and x1<10 and x2>10
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
-  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
-}
-do_eqp_test rtree6.2.4.2 {
-  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
-  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC PARTIAL COVERING INDEX (v=?)}
-}
-
-do_eqp_test rtree6.2.5 {
-  SELECT * FROM t1,t2 WHERE k=ii AND x1<v
-} {
-  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
-  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
-}
-
-do_execsql_test rtree6-3.1 {
-  CREATE VIRTUAL TABLE t3 USING rtree(id, x1, x2, y1, y2);
-  INSERT INTO t3 VALUES(NULL, 1, 1, 2, 2);
-  SELECT * FROM t3 WHERE 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5;
-} {1 1.0 1.0 2.0 2.0}
-
-do_test rtree6.3.2 {
-  rtree_strategy {
-    SELECT * FROM t3 WHERE 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 
-  }
-} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
-do_test rtree6.3.3 {
-  rtree_strategy {
-    SELECT * FROM t3 WHERE 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5
-  }
-} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
-
-do_execsql_test rtree6-3.4 {
-  SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1
-} {}
-do_execsql_test rtree6-3.5 {
-  SELECT * FROM t3 WHERE 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
-    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>1.1
-} {}
-
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree7.test b/lib/libsqlite3/ext/rtree/rtree7.test
deleted file mode 100644
index 4eee4c219a6..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree7.test
+++ /dev/null
@@ -1,70 +0,0 @@
-# 2010 February 16
-#
-# 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.
-#
-#***********************************************************************
-# 
-# Test that nothing goes wrong if an rtree table is created, then the
-# database page-size is modified. At one point (3.6.22), this was causing
-# malfunctions.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-
-ifcapable !rtree||!vacuum {
-  finish_test
-  return
-}
-
-# Like execsql except display output as integer where that can be
-# done without loss of information.
-#
-proc execsql_intout {sql} {
-  set out {}
-  foreach term [execsql $sql] {
-    regsub {\.0$} $term {} term
-    lappend out $term
-  }
-  return $out
-}
-
-do_test rtree7-1.1 {
-  execsql {
-    PRAGMA page_size = 1024;
-    CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2, y1, y2);
-    INSERT INTO rt VALUES(1, 1, 2, 3, 4);
-  }
-} {}
-do_test rtree7-1.2 {
-  execsql_intout { SELECT * FROM rt }
-} {1 1 2 3 4}
-do_test rtree7-1.3 {
-  execsql_intout { 
-    PRAGMA page_size = 2048;
-    VACUUM;
-    SELECT * FROM rt;
-  }
-} {1 1 2 3 4}
-do_test rtree7-1.4 {
-  for {set i 2} {$i <= 51} {incr i} {
-    execsql { INSERT INTO rt VALUES($i, 1, 2, 3, 4) }
-  }
-  execsql_intout { SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt }
-} {51 102 153 204}
-do_test rtree7-1.5 {
-  execsql_intout { 
-    PRAGMA page_size = 512;
-    VACUUM;
-    SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt
-  }
-} {51 102 153 204}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree8.test b/lib/libsqlite3/ext/rtree/rtree8.test
deleted file mode 100644
index 578a1468b8b..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree8.test
+++ /dev/null
@@ -1,170 +0,0 @@
-# 2010 February 16
-#
-# 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.
-#
-#***********************************************************************
-# 
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-
-#-------------------------------------------------------------------------
-# The following block of tests - rtree8-1.* - feature reading and writing
-# an r-tree table while there exist open cursors on it.
-#
-proc populate_t1 {n} {
-  execsql { DELETE FROM t1 }
-  for {set i 1} {$i <= $n} {incr i} {
-    execsql { INSERT INTO t1 VALUES($i, $i, $i+2) }
-  }
-}
-
-# A DELETE while a cursor is reading the table.
-#
-do_test rtree8-1.1.1 {
-  execsql { PRAGMA page_size = 512 }
-  execsql { CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2) }
-  populate_t1 5
-} {}
-do_test rtree8-1.1.2 {
-  set res [list]
-  db eval { SELECT * FROM t1 } { 
-    lappend res $x1 $x2
-    if {$id==3} { db eval { DELETE FROM t1 WHERE id>3 } }
-  }
-  set res
-} {1 3 2 4 3 5}
-do_test rtree8-1.1.3 {
-  execsql { SELECT * FROM t1 }
-} {1 1 3 2 2 4 3 3 5}
-
-# Many SELECTs on the same small table.
-#
-proc nested_select {n} {
-  set ::max $n
-  db eval { SELECT * FROM t1 } {
-    if {$id == $n} { nested_select [expr $n+1] }
-  }
-  return $::max
-}
-do_test rtree8-1.2.1 { populate_t1 50  } {}
-do_test rtree8-1.2.2 { nested_select 1 } {51}
-
-# This test runs many SELECT queries simultaneously against a large 
-# table, causing a collision in the hash-table used to store r-tree 
-# nodes internally.
-#
-populate_t1 1500
-do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {164}
-do_test rtree8-1.3.2 {
-  set rowids [execsql {SELECT min(rowid) FROM t1_rowid GROUP BY nodeno}]
-  set stmt_list [list]
-  foreach row $rowids {
-    set stmt [sqlite3_prepare db "SELECT * FROM t1 WHERE id = $row" -1 tail]
-    sqlite3_step $stmt
-    lappend res_list [sqlite3_column_int $stmt 0]
-    lappend stmt_list $stmt 
-  }
-} {}
-do_test rtree8-1.3.3 { set res_list } $rowids
-do_execsql_test rtree8-1.3.4 { SELECT count(*) FROM t1 } {1500}
-do_test rtree8-1.3.5 { 
-  foreach stmt $stmt_list { sqlite3_finalize $stmt }
-} {}
-
-
-#-------------------------------------------------------------------------
-# The following block of tests - rtree8-2.* - test a couple of database
-# corruption cases. In this case things are not corrupted at the b-tree
-# level, but the contents of the various tables used internally by an
-# r-tree table are inconsistent.
-#
-populate_t1 50
-do_execsql_test rtree8-2.1.1 { SELECT max(nodeno) FROM t1_node } {5}
-do_execsql_test rtree8-2.1.2 { DELETE FROM t1_node } {}
-for {set i 1} {$i <= 50} {incr i} {
-  do_catchsql_test rtree8-2.1.3.$i { 
-    SELECT * FROM t1 WHERE id = $i 
-  } {1 {database disk image is malformed}}
-}
-do_catchsql_test rtree8-2.1.4 { 
-  SELECT * FROM t1
-} {1 {database disk image is malformed}}
-do_catchsql_test rtree8-2.1.5 { 
-  DELETE FROM t1
-} {1 {database disk image is malformed}}
-
-do_execsql_test rtree8-2.1.6 { 
-  DROP TABLE t1;
-  CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2);
-} {}
-
-
-populate_t1 50
-do_execsql_test rtree8-2.2.1 {
-  DELETE FROM t1_parent
-} {}
-do_catchsql_test rtree8-2.2.2 {
-  DELETE FROM t1 WHERE id=25
-} {1 {database disk image is malformed}}
-do_execsql_test rtree8-2.2.3 { 
-  DROP TABLE t1;
-  CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2);
-} {}
-
-
-#-------------------------------------------------------------------------
-# Test that trying to use the MATCH operator with the r-tree module does
-# not confuse it. 
-#
-populate_t1 10
-do_catchsql_test rtree8-3.1 { 
-  SELECT * FROM t1 WHERE x1 MATCH '1234'
-} {1 {SQL logic error or missing database}}
-
-#-------------------------------------------------------------------------
-# Test a couple of invalid arguments to rtreedepth().
-#
-do_catchsql_test rtree8-4.1 {
-  SELECT rtreedepth('hello world')
-} {1 {Invalid argument to rtreedepth()}}
-do_catchsql_test rtree8-4.2 {
-  SELECT rtreedepth(X'00')
-} {1 {Invalid argument to rtreedepth()}}
-
-
-#-------------------------------------------------------------------------
-# Delete half of a lopsided tree.
-#
-do_execsql_test rtree8-5.1 { 
-  CREATE VIRTUAL TABLE t2 USING rtree_i32(id, x1, x2) 
-} {}
-do_test rtree8-5.2 {
-  execsql BEGIN
-  for {set i 0} {$i < 100} {incr i} {
-    execsql { INSERT INTO t2 VALUES($i, 100, 101) }
-  }
-  for {set i 100} {$i < 200} {incr i} {
-    execsql { INSERT INTO t2 VALUES($i, 1000, 1001) }
-  }
-  execsql COMMIT
-} {}
-do_test rtree8-5.3 {
-  execsql BEGIN
-  for {set i 0} {$i < 200} {incr i} {
-    execsql { DELETE FROM t2 WHERE id = $i }
-  }
-  execsql COMMIT
-} {}
-
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree9.test b/lib/libsqlite3/ext/rtree/rtree9.test
deleted file mode 100644
index 571341b2a93..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree9.test
+++ /dev/null
@@ -1,125 +0,0 @@
-# 2010 August 28
-#
-# 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 tests for the r-tree module. Specifically, it tests
-# that custom r-tree queries (geometry callbacks) work.
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-ifcapable rtree_int_only { finish_test; return }
-
-register_cube_geom db
-
-do_execsql_test rtree9-1.1 {
-  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2, y1, y2, z1, z2);
-  INSERT INTO rt VALUES(1, 1, 2, 1, 2, 1, 2);
-} {}
-do_execsql_test rtree9-1.2 {
-  SELECT * FROM rt WHERE id MATCH cube(0, 0, 0, 2, 2, 2);
-} {1 1.0 2.0 1.0 2.0 1.0 2.0}
-do_execsql_test rtree9-1.3 {
-  SELECT * FROM rt WHERE id MATCH cube(3, 3, 3, 2, 2, 2);
-} {}
-do_execsql_test rtree9-1.4 {
-  DELETE FROM rt;
-} {}
-
-
-for {set i 0} {$i < 1000} {incr i} {
-  set x [expr $i%10]
-  set y [expr ($i/10)%10]
-  set z [expr ($i/100)%10]
-  execsql { INSERT INTO rt VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
-}
-do_execsql_test rtree9-2.1 {
-  SELECT id FROM rt WHERE id MATCH cube(2.5, 2.5, 2.5, 1, 1, 1) ORDER BY id;
-} {222 223 232 233 322 323 332 333}
-do_execsql_test rtree9-2.2 {
-  SELECT id FROM rt WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
-} {555 556 565 566 655 656 665 666}
-
-
-do_execsql_test rtree9-3.1 {
-  CREATE VIRTUAL TABLE rt32 USING rtree_i32(id, x1, x2, y1, y2, z1, z2);
-} {} 
-for {set i 0} {$i < 1000} {incr i} {
-  set x [expr $i%10]
-  set y [expr ($i/10)%10]
-  set z [expr ($i/100)%10]
-  execsql { INSERT INTO rt32 VALUES($i, $x, $x+1, $y, $y+1, $z, $z+1) }
-}
-do_execsql_test rtree9-3.2 {
-  SELECT id FROM rt32 WHERE id MATCH cube(3, 3, 3, 1, 1, 1) ORDER BY id;
-} {222 223 224 232 233 234 242 243 244 322 323 324 332 333 334 342 343 344 422 423 424 432 433 434 442 443 444}
-do_execsql_test rtree9-3.3 {
-  SELECT id FROM rt32 WHERE id MATCH cube(5.5, 5.5, 5.5, 1, 1, 1) ORDER BY id;
-} {555 556 565 566 655 656 665 666}
-
-
-do_catchsql_test rtree9-4.1 {
-  SELECT id FROM rt32 WHERE id MATCH cube(5.5, 5.5, 1, 1, 1) ORDER BY id;
-} {1 {SQL logic error or missing database}}
-for {set x 2} {$x<200} {incr x 2} {
-  do_catchsql_test rtree9-4.2.[expr $x/2] {
-    SELECT id FROM rt WHERE id MATCH randomblob($x)
-  } {1 {SQL logic error or missing database}}
-}
-do_catchsql_test rtree9-4.3 {
-  SELECT id FROM rt WHERE id MATCH CAST( 
-    (cube(5.5, 5.5, 5.5, 1, 1, 1) || X'1234567812345678') AS blob 
-  )
-} {1 {SQL logic error or missing database}}
-
-
-#-------------------------------------------------------------------------
-# Test the example 2d "circle" geometry callback.
-#
-register_circle_geom db
-
-do_execsql_test rtree9-5.1 {
-  CREATE VIRTUAL TABLE rt2 USING rtree(id, xmin, xmax, ymin, ymax);
-
-  INSERT INTO rt2 VALUES(1,    1,   2,  1,  2);
-  INSERT INTO rt2 VALUES(2,    1,   2, -2, -1);
-  INSERT INTO rt2 VALUES(3,    -2, -1, -2, -1);
-  INSERT INTO rt2 VALUES(4,    -2, -1,  1,  2);
-
-  INSERT INTO rt2 VALUES(5,    2,   3,  2,  3);
-  INSERT INTO rt2 VALUES(6,    2,   3, -3, -2);
-  INSERT INTO rt2 VALUES(7,    -3, -2, -3, -2);
-  INSERT INTO rt2 VALUES(8,    -3, -2,  2,  3);
-
-  INSERT INTO rt2 VALUES(9,    1.8,   3,  1.8,  3);
-  INSERT INTO rt2 VALUES(10,   1.8,   3, -3, -1.8);
-  INSERT INTO rt2 VALUES(11,   -3, -1.8, -3, -1.8);
-  INSERT INTO rt2 VALUES(12,   -3, -1.8,  1.8,  3);
-
-  INSERT INTO rt2 VALUES(13,   -15, 15, 1.8, 2.2);
-  INSERT INTO rt2 VALUES(14,   -15, 15, -2.2, -1.8);
-  INSERT INTO rt2 VALUES(15,   1.8, 2.2, -15, 15);
-  INSERT INTO rt2 VALUES(16,   -2.2, -1.8, -15, 15);
-
-  INSERT INTO rt2 VALUES(17,   -100, 100, -100, 100);
-} {}
-
-do_execsql_test rtree9-5.2 {
-  SELECT id FROM rt2 WHERE id MATCH circle(0.0, 0.0, 2.0);
-} {1 2 3 4 13 14 15 16 17}
-
-do_execsql_test rtree9-5.3 {
-  UPDATE rt2 SET xmin=xmin+5, ymin=ymin+5, xmax=xmax+5, ymax=ymax+5;
-  SELECT id FROM rt2 WHERE id MATCH circle(5.0, 5.0, 2.0);
-} {1 2 3 4 13 14 15 16 17}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeA.test b/lib/libsqlite3/ext/rtree/rtreeA.test
deleted file mode 100644
index e377b013c13..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeA.test
+++ /dev/null
@@ -1,220 +0,0 @@
-# 2010 September 22
-#
-# 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 tests for the r-tree module. Specifically, it tests
-# that corrupt or inconsistent databases do not cause crashes in the r-tree
-# module.
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-
-proc create_t1 {} {
-  db close
-  forcedelete test.db
-  sqlite3 db test.db
-  execsql {
-    PRAGMA page_size = 1024;
-    CREATE VIRTUAL TABLE t1 USING rtree(id, x1, x2, y1, y2);
-  }
-}
-proc populate_t1 {} {
-  execsql BEGIN
-  for {set i 0} {$i < 500} {incr i} {
-    set x2 [expr $i+5]
-    set y2 [expr $i+5]
-    execsql { INSERT INTO t1 VALUES($i, $i, $x2, $i, $y2) }
-  }
-  execsql COMMIT
-}
-
-proc truncate_node {nodeno nTrunc} {
-  set blob [db one {SELECT data FROM t1_node WHERE nodeno=$nodeno}]
-  if {$nTrunc<0} {set nTrunc "end-$nTrunc"}
-  set blob [string range $blob 0 $nTrunc]
-  db eval { UPDATE t1_node SET data = $blob WHERE nodeno=$nodeno }
-}
-
-proc set_tree_depth {tbl {newvalue ""}} {
-  set blob [db one "SELECT data FROM ${tbl}_node WHERE nodeno=1"]
-
-  if {$newvalue == ""} {
-    binary scan $blob Su oldvalue
-    return $oldvalue
-  }
-
-  set blob [binary format Sua* $newvalue [string range $blob 2 end]]
-  db eval "UPDATE ${tbl}_node SET data = \$blob WHERE nodeno=1"
-  return [set_tree_depth $tbl]
-}
-
-proc set_entry_count {tbl nodeno {newvalue ""}} {
-  set blob [db one "SELECT data FROM ${tbl}_node WHERE nodeno=$nodeno"]
-
-  if {$newvalue == ""} {
-    binary scan [string range $blob 2 end] Su oldvalue
-    return $oldvalue
-  }
-
-  set blob [binary format a*Sua* \
-    [string range $blob 0 1] $newvalue [string range $blob 4 end]
-  ]
-  db eval "UPDATE ${tbl}_node SET data = \$blob WHERE nodeno=$nodeno"
-  return [set_entry_count $tbl $nodeno]
-}
-
-
-proc do_corruption_tests {prefix args} {
-  set testarray [lindex $args end]
-  set errormsg {database disk image is malformed}
-
-  foreach {z value} [lrange $args 0 end-1] {
-    set n [string length $z]
-    if {$n>=2 && [string equal -length $n $z "-error"]} {
-      set errormsg $value
-    }
-  }
-
-  foreach {tn sql} $testarray {
-    do_catchsql_test $prefix.$tn $sql [list 1 $errormsg]
-  }
-}
-
-#-------------------------------------------------------------------------
-# Test the libraries response if the %_node table is completely empty
-# (i.e. the root node is missing), or has been removed from the database
-# entirely.
-#
-create_t1
-populate_t1
-do_execsql_test rtreeA-1.0 {
-  DELETE FROM t1_node;
-} {}
-
-do_corruption_tests rtreeA-1.1 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
-}
-
-do_execsql_test  rtreeA-1.2.0 { DROP TABLE t1_node } {}
-do_corruption_tests rtreeA-1.2 -error "SQL logic error or missing database" {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
-}
-
-#-------------------------------------------------------------------------
-# Test the libraries response if some of the entries in the %_node table 
-# are the wrong size.
-#
-create_t1
-populate_t1
-do_test rtreeA-2.1.0 {
-  set nodes [db eval {select nodeno FROM t1_node}]
-  foreach {a b c} $nodes { truncate_node $c 200 }
-} {}
-do_corruption_tests rtreeA-2.1 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
-}
-
-create_t1
-populate_t1
-do_test rtreeA-2.2.0 { truncate_node 1 200 } {}
-do_corruption_tests rtreeA-2.2 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
-}
-
-#-------------------------------------------------------------------------
-# Set the "depth" of the tree stored on the root node incorrectly. Test
-# that this does not cause any problems.
-#
-create_t1
-populate_t1
-do_test rtreeA-3.1.0.1 { set_tree_depth t1 } {1}
-do_test rtreeA-3.1.0.2 { set_tree_depth t1 3 } {3}
-do_corruption_tests rtreeA-3.1 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-}
-
-do_test rtreeA-3.2.0 { set_tree_depth t1 1000 } {1000}
-do_corruption_tests rtreeA-3.2 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-}
-
-create_t1
-populate_t1
-do_test rtreeA-3.3.0 { 
-  execsql { DELETE FROM t1 WHERE rowid = 0 }
-  set_tree_depth t1 65535
-} {65535}
-do_corruption_tests rtreeA-3.3 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-}
-
-#-------------------------------------------------------------------------
-# Set the "number of entries" field on some nodes incorrectly.
-#
-create_t1
-populate_t1
-do_test rtreeA-4.1.0 { 
-  set_entry_count t1 1 4000
-} {4000}
-do_corruption_tests rtreeA-4.1 {
-  1   "SELECT * FROM t1"
-  2   "SELECT * FROM t1 WHERE rowid=5"
-  3   "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)"
-  4   "SELECT * FROM t1 WHERE x1<10 AND x2>12"
-}
-
-#-------------------------------------------------------------------------
-# Remove entries from the %_parent table and check that this does not
-# cause a crash.
-#
-create_t1
-populate_t1
-do_execsql_test rtreeA-5.1.0 { DELETE FROM t1_parent } {}
-do_corruption_tests rtreeA-5.1 {
-  1   "DELETE FROM t1 WHERE rowid = 5"
-  2   "DELETE FROM t1"
-}
-
-#-------------------------------------------------------------------------
-# Add some bad entries to the %_parent table.
-#
-create_t1
-populate_t1
-do_execsql_test rtreeA-6.1.0 { 
-  UPDATE t1_parent set parentnode = parentnode+1
-} {}
-do_corruption_tests rtreeA-6.1 {
-  1   "DELETE FROM t1 WHERE rowid = 5"
-  2   "UPDATE t1 SET x1=x1+1, x2=x2+1"
-}
-
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeB.test b/lib/libsqlite3/ext/rtree/rtreeB.test
deleted file mode 100644
index aeb308eca7e..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeB.test
+++ /dev/null
@@ -1,47 +0,0 @@
-# 2011 March 2
-#
-# 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.
-#
-#***********************************************************************
-# Make sure the rtreenode() testing function can handle entries with
-# 64-bit rowids.
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-
-ifcapable rtree_int_only {
-  do_test rtreeB-1.1-intonly {
-    db eval {
-      CREATE VIRTUAL TABLE t1 USING rtree(ii, x0, y0, x1, y1);
-      INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
-      INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
-      INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
-      INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
-      INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
-      SELECT rtreenode(2, data) FROM t1_node;
-    }
-  } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
-} else {  
-  do_test rtreeB-1.1 {
-    db eval {
-      CREATE VIRTUAL TABLE t1 USING rtree(ii, x0, y0, x1, y1);
-      INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
-      INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
-      INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
-      INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
-      INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
-      SELECT rtreenode(2, data) FROM t1_node;
-    }
-  } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
-}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeC.test b/lib/libsqlite3/ext/rtree/rtreeC.test
deleted file mode 100644
index 9a64df51d53..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeC.test
+++ /dev/null
@@ -1,356 +0,0 @@
-# 2011 March 2
-#
-# 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.
-#
-#***********************************************************************
-# Make sure the rtreenode() testing function can handle entries with
-# 64-bit rowids.
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-set testprefix rtreeC
-
-do_execsql_test 1.0 {
-  CREATE VIRTUAL TABLE r_tree USING rtree(id, min_x, max_x, min_y, max_y);
-  CREATE TABLE t(x, y);
-}
-
-do_eqp_test 1.1 {
-  SELECT * FROM r_tree, t 
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
-} {
-  0 0 1 {SCAN TABLE t}
-  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 1.2 {
-  SELECT * FROM t, r_tree
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
-} {
-  0 0 0 {SCAN TABLE t}
-  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 1.3 {
-  SELECT * FROM t, r_tree
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
-} {
-  0 0 0 {SCAN TABLE t}
-  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 1.5 {
-  SELECT * FROM t, r_tree
-} {
-  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
-  0 1 0 {SCAN TABLE t} 
-}
-
-do_execsql_test 2.0 {
-  INSERT INTO t VALUES(0, 0);
-  INSERT INTO t VALUES(0, 1);
-  INSERT INTO t VALUES(0, 2);
-  INSERT INTO t VALUES(0, 3);
-  INSERT INTO t VALUES(0, 4);
-  INSERT INTO t VALUES(0, 5);
-  INSERT INTO t VALUES(0, 6);
-  INSERT INTO t VALUES(0, 7);
-  INSERT INTO t VALUES(0, 8);
-  INSERT INTO t VALUES(0, 9);
-
-  INSERT INTO t SELECT x+1, y FROM t;
-  INSERT INTO t SELECT x+2, y FROM t;
-  INSERT INTO t SELECT x+4, y FROM t;
-  INSERT INTO r_tree SELECT NULL, x-1, x+1, y-1, y+1 FROM t;
-  ANALYZE;
-}
-
-db close
-sqlite3 db test.db
-
-do_eqp_test 2.1 {
-  SELECT * FROM r_tree, t 
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
-} {
-  0 0 1 {SCAN TABLE t}
-  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 2.2 {
-  SELECT * FROM t, r_tree
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
-} {
-  0 0 0 {SCAN TABLE t}
-  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 2.3 {
-  SELECT * FROM t, r_tree
-  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
-} {
-  0 0 0 {SCAN TABLE t}
-  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
-}
-
-do_eqp_test 2.5 {
-  SELECT * FROM t, r_tree
-} {
-  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
-  0 1 0 {SCAN TABLE t} 
-}
-
-#-------------------------------------------------------------------------
-# Test that the special CROSS JOIN handling works with rtree tables.
-#
-do_execsql_test 3.1 {
-  CREATE TABLE t1(x);
-  CREATE TABLE t2(y);
-  CREATE VIRTUAL TABLE t3 USING rtree(z, x1,x2, y1,y2);
-}
-
-do_eqp_test 3.2.1 { SELECT * FROM t1 CROSS JOIN t2 } {
-  0 0 0 {SCAN TABLE t1} 
-  0 1 1 {SCAN TABLE t2}
-}
-do_eqp_test 3.2.2 { SELECT * FROM t2 CROSS JOIN t1 } {
-  0 0 0 {SCAN TABLE t2} 0 1 1 {SCAN TABLE t1}
-}
-
-do_eqp_test 3.3.1 { SELECT * FROM t1 CROSS JOIN t3 } {
-  0 0 0 {SCAN TABLE t1}
-  0 1 1 {SCAN TABLE t3 VIRTUAL TABLE INDEX 2:} 
-}
-do_eqp_test 3.3.2 { SELECT * FROM t3 CROSS JOIN t1 } {
-  0 0 0 {SCAN TABLE t3 VIRTUAL TABLE INDEX 2:} 
-  0 1 1 {SCAN TABLE t1}
-}
-
-#--------------------------------------------------------------------
-# Test that LEFT JOINs are not reordered if the right-hand-side is
-# a virtual table.
-#
-reset_db
-do_execsql_test 4.1 {
-  CREATE TABLE t1(a);
-  CREATE VIRTUAL TABLE t2 USING rtree(b, x1,x2);
-
-  INSERT INTO t1 VALUES(1);
-  INSERT INTO t1 VALUES(2);
-
-  INSERT INTO t2 VALUES(1, 0.0, 0.1);
-  INSERT INTO t2 VALUES(3, 0.0, 0.1);
-}
-
-do_execsql_test 4.2 {
-  SELECT a, b FROM t1 LEFT JOIN t2 ON (+a = +b);
-} {1 1 2 {}}
-
-do_execsql_test 4.3 {
-  SELECT b, a FROM t2 LEFT JOIN t1 ON (+a = +b);
-} {1 1 3 {}}
-
-#--------------------------------------------------------------------
-# Test that the sqlite_stat1 data is used correctly.
-#
-reset_db
-do_execsql_test 5.1 {
-  CREATE TABLE t1(x PRIMARY KEY, y);
-  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);
-
-  INSERT INTO t1(x) VALUES(1);
-  INSERT INTO t1(x) SELECT x+1 FROM t1;   --   2
-  INSERT INTO t1(x) SELECT x+2 FROM t1;   --   4
-  INSERT INTO t1(x) SELECT x+4 FROM t1;   --   8
-  INSERT INTO t1(x) SELECT x+8 FROM t1;   --  16
-  INSERT INTO t1(x) SELECT x+16 FROM t1;  --  32
-  INSERT INTO t1(x) SELECT x+32 FROM t1;  --  64
-  INSERT INTO t1(x) SELECT x+64 FROM t1;  -- 128
-  INSERT INTO t1(x) SELECT x+128 FROM t1; -- 256
-  INSERT INTO t1(x) SELECT x+256 FROM t1; -- 512
-  INSERT INTO t1(x) SELECT x+512 FROM t1; --1024
-
-  INSERT INTO rt SELECT x, x, x+1 FROM t1 WHERE x<=5;
-}
-
-# First test a query with no ANALYZE data at all. The outer loop is
-# real table "t1".
-#
-do_eqp_test 5.2 {
-  SELECT * FROM t1, rt WHERE x==id;
-} {
-  0 0 0 {SCAN TABLE t1} 
-  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
-}
-
-# Now create enough ANALYZE data to tell SQLite that virtual table "rt"
-# contains very few rows. This causes it to move "rt" to the outer loop.
-#
-do_execsql_test 5.3 {
-  ANALYZE;
-  DELETE FROM sqlite_stat1 WHERE tbl='t1';
-}
-db close
-sqlite3 db test.db
-do_eqp_test 5.4 {
-  SELECT * FROM t1, rt WHERE x==id;
-} {
-  0 0 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:} 
-  0 1 0 {SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (x=?)}
-}
-
-# Delete the ANALYZE data. "t1" should be the outer loop again.
-#
-do_execsql_test 5.5 { DROP TABLE sqlite_stat1; }
-db close
-sqlite3 db test.db
-do_eqp_test 5.6 {
-  SELECT * FROM t1, rt WHERE x==id;
-} {
-  0 0 0 {SCAN TABLE t1} 
-  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
-}
-
-# This time create and attach a database that contains ANALYZE data for
-# tables of the same names as those used internally by virtual table
-# "rt". Check that the rtree module is not fooled into using this data.
-# Table "t1" should remain the outer loop.
-#
-do_test 5.7 {
-  db backup test.db2
-  sqlite3 db2 test.db2
-  db2 eval {
-    ANALYZE;
-    DELETE FROM sqlite_stat1 WHERE tbl='t1';
-  }
-  db2 close
-  db close
-  sqlite3 db test.db
-  execsql { ATTACH 'test.db2' AS aux; }
-} {}
-do_eqp_test 5.8 {
-  SELECT * FROM t1, rt WHERE x==id;
-} {
-  0 0 0 {SCAN TABLE t1} 
-  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
-}
-
-#--------------------------------------------------------------------
-# Test that having a second connection drop the sqlite_stat1 table
-# before it is required by rtreeConnect() does not cause problems.
-#
-ifcapable rtree {
-  reset_db
-  do_execsql_test 6.1 {
-    CREATE TABLE t1(x);
-    CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);
-    INSERT INTO t1 VALUES(1);
-    INSERT INTO rt VALUES(1,2,3);
-    ANALYZE;
-  }
-  db close
-  sqlite3 db test.db
-  do_execsql_test 6.2 { SELECT * FROM t1 } {1}
-  
-  do_test 6.3 {
-    sqlite3 db2 test.db
-    db2 eval { DROP TABLE sqlite_stat1 }
-    db2 close
-    execsql { SELECT * FROM rt }
-  } {1 2.0 3.0}
-  db close
-}
-
-#--------------------------------------------------------------------
-# Test that queries featuring LEFT or CROSS JOINS are handled correctly.
-# Handled correctly in this case means:
-#
-#   * Terms with prereqs that appear to the left of a LEFT JOIN against
-#     the virtual table are always available to xBestIndex.
-#
-#   * Terms with prereqs that appear to the right of a LEFT JOIN against
-#     the virtual table are never available to xBestIndex.
-#
-# And the same behaviour for CROSS joins.
-#
-reset_db
-do_execsql_test 7.0 {
-  CREATE TABLE xdir(x1);
-  CREATE TABLE ydir(y1);
-  CREATE VIRTUAL TABLE rt USING rtree_i32(id, xmin, xmax, ymin, ymax);
-
-  INSERT INTO xdir VALUES(5);
-  INSERT INTO ydir VALUES(10);
-
-  INSERT INTO rt VALUES(1, 2, 7, 12, 14);      -- Not a hit
-  INSERT INTO rt VALUES(2, 2, 7, 8, 12);       -- A hit!
-  INSERT INTO rt VALUES(3, 7, 11, 8, 12);      -- Not a hit!
-  INSERT INTO rt VALUES(4, 5, 5, 10, 10);      -- A hit!
-
-}
-
-proc do_eqp_execsql_test {tn sql res} {
-  set query "EXPLAIN QUERY PLAN $sql ; $sql "
-  uplevel [list do_execsql_test $tn $query $res]
-}
-
-do_eqp_execsql_test 7.1 {
-  SELECT id FROM xdir, rt, ydir 
-  ON (y1 BETWEEN ymin AND ymax)
-  WHERE (x1 BETWEEN xmin AND xmax);
-} {
-  0 0 0 {SCAN TABLE xdir} 
-  0 1 2 {SCAN TABLE ydir} 
-  0 2 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B2D3B0D1}
-  2 4
-}
-
-do_eqp_execsql_test 7.2 {
-  SELECT * FROM xdir, rt LEFT JOIN ydir 
-  ON (y1 BETWEEN ymin AND ymax)
-  WHERE (x1 BETWEEN xmin AND xmax);
-} {
-  0 0 0 {SCAN TABLE xdir} 
-  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
-  0 2 2 {SCAN TABLE ydir} 
-
-  5 1 2 7 12 14 {}
-  5 2 2 7  8 12 10
-  5 4 5 5 10 10 10
-}
-
-do_eqp_execsql_test 7.3 {
-  SELECT id FROM xdir, rt CROSS JOIN ydir 
-  ON (y1 BETWEEN ymin AND ymax)
-  WHERE (x1 BETWEEN xmin AND xmax);
-} {
-  0 0 0 {SCAN TABLE xdir} 
-  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
-  0 2 2 {SCAN TABLE ydir} 
-  2 4
-}
-
-do_eqp_execsql_test 7.4 {
-  SELECT id FROM rt, xdir CROSS JOIN ydir 
-  ON (y1 BETWEEN ymin AND ymax)
-  WHERE (x1 BETWEEN xmin AND xmax);
-} {
-  0 0 1 {SCAN TABLE xdir} 
-  0 1 0 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
-  0 2 2 {SCAN TABLE ydir} 
-  2 4
-}
-
-finish_test
-
-
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeD.test b/lib/libsqlite3/ext/rtree/rtreeD.test
deleted file mode 100644
index c4a7d22e2e5..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeD.test
+++ /dev/null
@@ -1,57 +0,0 @@
-# 2014 March 11
-#
-# 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.
-#
-#***********************************************************************
-#
-# Miscellaneous tests for errors in the rtree constructor.
-#
-
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source [file join [file dirname [info script]] rtree_util.tcl]
-source $testdir/tester.tcl
-source $testdir/lock_common.tcl
-ifcapable !rtree {
-  finish_test
-  return
-}
-set testprefix rtreeD
-
-#-------------------------------------------------------------------------
-# Test that if an SQLITE_BUSY is encountered within the vtable 
-# constructor, a relevant error message is returned.
-#
-do_multiclient_test tn {
-  do_test 1.$tn.1 {
-    sql1 {
-      CREATE TABLE t1(a, b);
-      INSERT INTO t1 VALUES(1,2);
-      CREATE VIRTUAL TABLE rt USING rtree(id, minx, maxx, miny, maxy);
-      INSERT INTO rt VALUES(1,2,3,4,5);
-    }
-  } {}
-
-  do_test 1.$tn.2 {
-    sql2 { SELECT * FROM t1; }
-  } {1 2}
-
-  do_test 1.$tn.3 {
-    sql1 { BEGIN EXCLUSIVE; INSERT INTO t1 VALUES(3, 4); }
-  } {}
-
-  do_test 1.$tn.4 {
-    list [catch { sql2 { SELECT * FROM rt } } msg] $msg
-  } {1 {database is locked}}
-}
-
-finish_test
-
-
diff --git a/lib/libsqlite3/ext/rtree/rtreeE.test b/lib/libsqlite3/ext/rtree/rtreeE.test
deleted file mode 100644
index 3e5ba3a67fa..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeE.test
+++ /dev/null
@@ -1,140 +0,0 @@
-# 2010 August 28
-#
-# 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 tests for the r-tree module. Specifically, it tests
-# that new-style custom r-tree queries (geometry callbacks) work.
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-ifcapable rtree_int_only { finish_test; return }
-
-
-#-------------------------------------------------------------------------
-# Test the example 2d "circle" geometry callback.
-#
-register_circle_geom db
-
-do_execsql_test rtreeE-1.1 {
-  PRAGMA page_size=512;
-  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
-  
-  /* A tight pattern of small boxes near 0,0 */
-  WITH RECURSIVE
-    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
-    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
-  INSERT INTO rt1 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;
-
-  /* A looser pattern of small boxes near 100, 0 */
-  WITH RECURSIVE
-    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
-    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
-  INSERT INTO rt1 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;
-
-  /* A looser pattern of larger boxes near 0, 200 */
-  WITH RECURSIVE
-    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
-    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
-  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
-} {}
-
-# Queries against each of the three clusters */
-do_execsql_test rtreeE-1.1 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
-} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
-do_execsql_test rtreeE-1.1x {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle('x:0 y:0 r:50.0 e:3') ORDER BY id;
-} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
-do_execsql_test rtreeE-1.2 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id;
-} {100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124}
-do_execsql_test rtreeE-1.3 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id;
-} {200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224}
-
-# The Qcircle geometry function gives a lower score to larger leaf-nodes.
-# This causes the 200s to sort before the 100s and the 0s to sort before
-# last.
-#
-do_execsql_test rtreeE-1.4 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle('r:1000 e:3') AND id%100==0
-} {200 100 0}
-
-# Exclude odd rowids on a depth-first search
-do_execsql_test rtreeE-1.5 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle('r:1000 e:4') ORDER BY +id
-} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
-
-# Exclude odd rowids on a breadth-first search.
-do_execsql_test rtreeE-1.6 {
-  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,5) ORDER BY +id
-} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
-
-# Test that rtree prefers MATCH to lookup-by-rowid.
-#
-do_execsql_test rtreeE-1.7 {
-  SELECT id FROM rt1 WHERE id=18 AND id MATCH Qcircle(0,0,1000,5)
-} {18}
-
-
-# Construct a large 2-D RTree with thousands of random entries.
-#
-do_test rtreeE-2.1 {
-  db eval {
-    CREATE TABLE t2(id,x0,x1,y0,y1);
-    CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
-    BEGIN;
-  }
-  expr srand(0)
-  for {set i 1} {$i<=10000} {incr i} {
-    set dx [expr {int(rand()*40)+1}]
-    set dy [expr {int(rand()*40)+1}]
-    set x0 [expr {int(rand()*(10000 - $dx))}]
-    set x1 [expr {$x0+$dx}]
-    set y0 [expr {int(rand()*(10000 - $dy))}]
-    set y1 [expr {$y0+$dy}]
-    set id [expr {$i+10000}]
-    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
-  }
-  db eval {
-    INSERT INTO rt2 SELECT * FROM t2;
-    COMMIT;
-  }
-} {}
-
-for {set i 1} {$i<=200} {incr i} {
-  set dx [expr {int(rand()*100)}]
-  set dy [expr {int(rand()*100)}]
-  set x0 [expr {int(rand()*(10000 - $dx))}]
-  set x1 [expr {$x0+$dx}]
-  set y0 [expr {int(rand()*(10000 - $dy))}]
-  set y1 [expr {$y0+$dy}]
-  set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}]
-  do_execsql_test rtreeE-2.2.$i {
-    SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id
-  } $ans
-}
-
-# Run query that have very deep priority queues
-#
-set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}]
-do_execsql_test rtreeE-2.3 {
-  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id
-} $ans
-set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}]
-do_execsql_test rtreeE-2.4 {
-  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id
-} $ans
-
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeF.test b/lib/libsqlite3/ext/rtree/rtreeF.test
deleted file mode 100644
index c9620d34f7e..00000000000
--- a/lib/libsqlite3/ext/rtree/rtreeF.test
+++ /dev/null
@@ -1,81 +0,0 @@
-# 2014-08-21
-#
-# 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 tests for the r-tree module.
-#
-# This file contains test cases for the ticket
-# [369d57fb8e5ccdff06f197a37147a88f9de95cda] (2014-08-21)
-#
-#  The following SQL causes an assertion fault while running
-#  sqlite3_prepare() on the DELETE statement:
-#
-#     CREATE TABLE t1(x);
-#     CREATE TABLE t2(y);
-#     CREATE VIRTUAL TABLE t3 USING rtree(a,b,c);
-#     CREATE TRIGGER t2del AFTER DELETE ON t2 WHEN (SELECT 1 from t1) BEGIN 
-#       DELETE FROM t3 WHERE a=old.y; 
-#     END;
-#     DELETE FROM t2 WHERE y=1;
-# 
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-} 
-source $testdir/tester.tcl
-ifcapable !rtree { finish_test ; return }
-
-do_execsql_test rtreeF-1.1 {
-  CREATE TABLE t1(x);
-  CREATE TABLE t2(y);
-  CREATE VIRTUAL TABLE t3 USING rtree(a,b,c);
-  CREATE TRIGGER t2dwl AFTER DELETE ON t2 WHEN (SELECT 1 from t1) BEGIN 
-    DELETE FROM t3 WHERE a=old.y; 
-  END;
-
-  INSERT INTO t1(x) VALUES(999);
-  INSERT INTO t2(y) VALUES(1),(2),(3),(4),(5);
-  INSERT INTO t3(a,b,c) VALUES(1,2,3),(2,3,4),(3,4,5),(4,5,6),(5,6,7);
-
-  SELECT a FROM t3 ORDER BY a;
-  SELECT '|';
-  SELECT y FROM t2 ORDER BY y;
-} {1 2 3 4 5 | 1 2 3 4 5}
-do_execsql_test rtreeF-1.2 {
-  DELETE FROM t2 WHERE y=3;
-
-  SELECT a FROM t3 ORDER BY a;
-  SELECT '|';
-  SELECT y FROM t2 ORDER BY y;
-} {1 2 4 5 | 1 2 4 5}
-do_execsql_test rtreeF-1.3 {
-  DELETE FROM t1;
-  DELETE FROM t2 WHERE y=5;
-
-  SELECT a FROM t3 ORDER BY a;
-  SELECT '|';
-  SELECT y FROM t2 ORDER BY y;
-} {1 2 4 5 | 1 2 4}
-do_execsql_test rtreeF-1.4 {
-  INSERT INTO t1 DEFAULT VALUES;
-  DELETE FROM t2 WHERE y=5;
-
-  SELECT a FROM t3 ORDER BY a;
-  SELECT '|';
-  SELECT y FROM t2 ORDER BY y;
-} {1 2 4 5 | 1 2 4}
-do_execsql_test rtreeF-1.5 {
-  DELETE FROM t2 WHERE y=2;
-
-  SELECT a FROM t3 ORDER BY a;
-  SELECT '|';
-  SELECT y FROM t2 ORDER BY y;
-} {1 4 5 | 1 4}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree_perf.tcl b/lib/libsqlite3/ext/rtree/rtree_perf.tcl
deleted file mode 100644
index e42e6855061..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree_perf.tcl
+++ /dev/null
@@ -1,74 +0,0 @@
-
-set testdir [file join [file dirname $argv0] .. .. test]
-source $testdir/tester.tcl
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-set NROW   10000
-set NQUERY   500
-
-puts "Generating $NROW rows of data..."
-set data [list]
-for {set ii 0} {$ii < $NROW} {incr ii} {
-  set x1 [expr {rand()*1000}]
-  set x2 [expr {$x1+rand()*50}]
-  set y1 [expr {rand()*1000}]
-  set y2 [expr {$y1+rand()*50}]
-  lappend data $x1 $x2 $y1 $y2
-}
-puts "Finished generating data"
-
-
-set sql1 {CREATE TABLE btree(ii INTEGER PRIMARY KEY, x1, x2, y1, y2)}
-set sql2 {CREATE VIRTUAL TABLE rtree USING rtree(ii, x1, x2, y1, y2)}
-puts "Creating tables:"
-puts "  $sql1"
-puts "  $sql2"
-db eval $sql1
-db eval $sql2
-
-db eval "pragma cache_size=100"
-
-puts -nonewline "Inserting into btree... "
-flush stdout
-set btree_time [time {db transaction {
-  set ii 1
-  foreach {x1 x2 y1 y2} $data {
-    db eval {INSERT INTO btree VALUES($ii, $x1, $x2, $y1, $y2)}
-    incr ii
-  }
-}}]
-puts "$btree_time"
-
-puts -nonewline "Inserting into rtree... "
-flush stdout
-set rtree_time [time {db transaction {
-  set ii 1
-  foreach {x1 x2 y1 y2} $data {
-    incr ii
-    db eval {INSERT INTO rtree VALUES($ii, $x1, $x2, $y1, $y2)}
-  }
-}}]
-puts "$rtree_time"
-
-
-puts -nonewline "Selecting from btree... "
-flush stdout
-set btree_select_time [time {
-  foreach {x1 x2 y1 y2} [lrange $data 0 [expr $NQUERY*4-1]] {
-    db eval {SELECT * FROM btree WHERE x1<$x1 AND x2>$x2 AND y1<$y1 AND y2>$y2}
- }
-}]
-puts "$btree_select_time"
-
-puts -nonewline "Selecting from rtree... "
-flush stdout
-set rtree_select_time [time {
-  foreach {x1 x2 y1 y2} [lrange $data 0 [expr $NQUERY*4-1]] {
-    db eval {SELECT * FROM rtree WHERE x1<$x1 AND x2>$x2 AND y1<$y1 AND y2>$y2}
-  }
-}]
-puts "$rtree_select_time"
diff --git a/lib/libsqlite3/ext/rtree/rtree_util.tcl b/lib/libsqlite3/ext/rtree/rtree_util.tcl
deleted file mode 100644
index 50a1b580651..00000000000
--- a/lib/libsqlite3/ext/rtree/rtree_util.tcl
+++ /dev/null
@@ -1,192 +0,0 @@
-# 2008 Feb 19
-#
-# 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 Tcl code that may be useful for testing or
-# analyzing r-tree structures created with this module. It is
-# used by both test procedures and the r-tree viewer application.
-#
-
-
-#--------------------------------------------------------------------------
-# PUBLIC API:
-#
-#   rtree_depth
-#   rtree_ndim
-#   rtree_node
-#   rtree_mincells
-#   rtree_check
-#   rtree_dump
-#   rtree_treedump
-#
-
-proc rtree_depth {db zTab} {
-  $db one "SELECT rtreedepth(data) FROM ${zTab}_node WHERE nodeno=1"
-}
-
-proc rtree_nodedepth {db zTab iNode} {
-  set iDepth [rtree_depth $db $zTab]
-  
-  set ii $iNode
-  while {$ii != 1} {
-    set sql "SELECT parentnode FROM ${zTab}_parent WHERE nodeno = $ii"
-    set ii [db one $sql]
-    incr iDepth -1
-  }
-  
-  return $iDepth
-}
-
-# Return the number of dimensions of the rtree.
-#
-proc rtree_ndim {db zTab} {
-  set nDim [expr {(([llength [$db eval "pragma table_info($zTab)"]]/6)-1)/2}]
-}
-
-# Return the contents of rtree node $iNode.
-#
-proc rtree_node {db zTab iNode {iPrec 6}} {
-  set nDim [rtree_ndim $db $zTab]
-  set sql "
-    SELECT rtreenode($nDim, data) FROM ${zTab}_node WHERE nodeno = $iNode
-  "
-  set node [db one $sql]
-
-  set nCell [llength $node]
-  set nCoord [expr $nDim*2]
-  for {set ii 0} {$ii < $nCell} {incr ii} {
-    for {set jj 1} {$jj <= $nCoord} {incr jj} {
-      set newval [format "%.${iPrec}f" [lindex $node $ii $jj]]
-      lset node $ii $jj $newval
-    }
-  }
-  set node
-}
-
-proc rtree_mincells {db zTab} {
-  set n [$db one "select length(data) FROM ${zTab}_node LIMIT 1"]
-  set nMax [expr {int(($n-4)/(8+[rtree_ndim $db $zTab]*2*4))}]
-  return [expr {int($nMax/3)}]
-}
-
-# An integrity check for the rtree $zTab accessible via database 
-# connection $db.
-#
-proc rtree_check {db zTab} {
-  array unset ::checked
- 
-  # Check each r-tree node.
-  set rc [catch {
-    rtree_node_check $db $zTab 1 [rtree_depth $db $zTab]
-  } msg]
-  if {$rc && $msg ne ""} { error $msg }
-
-  # Check that the _rowid and _parent tables have the right 
-  # number of entries.
-  set nNode   [$db one "SELECT count(*) FROM ${zTab}_node"]
-  set nRow    [$db one "SELECT count(*) FROM ${zTab}"]
-  set nRowid  [$db one "SELECT count(*) FROM ${zTab}_rowid"]
-  set nParent [$db one "SELECT count(*) FROM ${zTab}_parent"]
-
-  if {$nNode != ($nParent+1)} { 
-    error "Wrong number of entries in ${zTab}_parent"
-  }
-  if {$nRow != $nRowid} { 
-    error "Wrong number of entries in ${zTab}_rowid"
-  }
-  
-  return $rc
-}
-
-proc rtree_node_check {db zTab iNode iDepth} {
-  if {[info exists ::checked($iNode)]} { error "Second ref to $iNode" }
-  set ::checked($iNode) 1
-
-  set node [rtree_node $db $zTab $iNode]
-  if {$iNode!=1 && [llength $node]==0} { error "No such node: $iNode" }
-
-  if {$iNode != 1 && [llength $node]<[rtree_mincells $db $zTab]} {
-    puts "Node $iNode: Has only [llength $node] cells"
-    error ""
-  }
-  if {$iNode == 1 && [llength $node]==1 && [rtree_depth $db $zTab]>0} {
-    set depth [rtree_depth $db $zTab]
-    puts "Node $iNode: Has only 1 child (tree depth is $depth)"
-    error ""
-  }
-
-  set nDim [expr {([llength [lindex $node 0]]-1)/2}]
-
-  if {$iDepth > 0} {
-    set d [expr $iDepth-1]
-    foreach cell $node {
-      set shouldbe [rtree_node_check $db $zTab [lindex $cell 0] $d]
-      if {$cell ne $shouldbe} {
-        puts "Node $iNode: Cell is: {$cell}, should be {$shouldbe}"
-        error ""
-      }
-    }
-  }
-
-  set mapping_table "${zTab}_parent" 
-  set mapping_sql "SELECT parentnode FROM $mapping_table WHERE rowid = \$rowid"
-  if {$iDepth==0} { 
-    set mapping_table "${zTab}_rowid"
-    set mapping_sql "SELECT nodeno FROM $mapping_table WHERE rowid = \$rowid"
-  }
-  foreach cell $node {
-    set rowid [lindex $cell 0]
-    set mapping [db one $mapping_sql]
-    if {$mapping != $iNode} {
-      puts "Node $iNode: $mapping_table entry for cell $rowid is $mapping"
-      error ""
-    }
-  }
-
-  set ret [list $iNode]
-  for {set ii 1} {$ii <= $nDim*2} {incr ii} {
-    set f [lindex $node 0 $ii]
-    foreach cell $node {
-      set f2 [lindex $cell $ii]
-      if {($ii%2)==1 && $f2<$f} {set f $f2}
-      if {($ii%2)==0 && $f2>$f} {set f $f2}
-    }
-    lappend ret $f
-  }
-  return $ret
-}
-
-proc rtree_dump {db zTab} {
-  set zRet ""
-  set nDim [expr {(([llength [$db eval "pragma table_info($zTab)"]]/6)-1)/2}]
-  set sql "SELECT nodeno, rtreenode($nDim, data) AS node FROM ${zTab}_node"
-  $db eval $sql {
-    append zRet [format "% -10s %s\n" $nodeno $node]
-  }
-  set zRet
-}
-
-proc rtree_nodetreedump {db zTab zIndent iDepth iNode} {
-  set ret ""
-  set node [rtree_node $db $zTab $iNode 1]
-  append ret [format "%-3d %s%s\n" $iNode $zIndent $node]
-  if {$iDepth>0} {
-    foreach cell $node {
-      set i [lindex $cell 0]
-      append ret [rtree_nodetreedump $db $zTab "$zIndent  " [expr $iDepth-1] $i]
-    }
-  }
-  set ret
-}
-
-proc rtree_treedump {db zTab} {
-  set d [rtree_depth $db $zTab]
-  rtree_nodetreedump $db $zTab "" $d 1
-}
diff --git a/lib/libsqlite3/ext/rtree/sqlite3rtree.h b/lib/libsqlite3/ext/rtree/sqlite3rtree.h
deleted file mode 100644
index f683fc610af..00000000000
--- a/lib/libsqlite3/ext/rtree/sqlite3rtree.h
+++ /dev/null
@@ -1,117 +0,0 @@
-/*
-** 2010 August 30
-**
-** 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.
-**
-*************************************************************************
-*/
-
-#ifndef _SQLITE3RTREE_H_
-#define _SQLITE3RTREE_H_
-
-#include <sqlite3.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
-typedef struct sqlite3_rtree_query_info sqlite3_rtree_query_info;
-
-/* The double-precision datatype used by RTree depends on the
-** SQLITE_RTREE_INT_ONLY compile-time option.
-*/
-#ifdef SQLITE_RTREE_INT_ONLY
-  typedef sqlite3_int64 sqlite3_rtree_dbl;
-#else
-  typedef double sqlite3_rtree_dbl;
-#endif
-
-/*
-** Register a geometry callback named zGeom that can be used as part of an
-** R-Tree geometry query as follows:
-**
-**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...)
-*/
-int sqlite3_rtree_geometry_callback(
-  sqlite3 *db,
-  const char *zGeom,
-  int (*xGeom)(sqlite3_rtree_geometry*, int, sqlite3_rtree_dbl*,int*),
-  void *pContext
-);
-
-
-/*
-** A pointer to a structure of the following type is passed as the first
-** argument to callbacks registered using rtree_geometry_callback().
-*/
-struct sqlite3_rtree_geometry {
-  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
-  int nParam;                     /* Size of array aParam[] */
-  sqlite3_rtree_dbl *aParam;      /* Parameters passed to SQL geom function */
-  void *pUser;                    /* Callback implementation user data */
-  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
-};
-
-/*
-** Register a 2nd-generation geometry callback named zScore that can be 
-** used as part of an R-Tree geometry query as follows:
-**
-**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zQueryFunc(... params ...)
-*/
-int sqlite3_rtree_query_callback(
-  sqlite3 *db,
-  const char *zQueryFunc,
-  int (*xQueryFunc)(sqlite3_rtree_query_info*),
-  void *pContext,
-  void (*xDestructor)(void*)
-);
-
-
-/*
-** A pointer to a structure of the following type is passed as the 
-** argument to scored geometry callback registered using
-** sqlite3_rtree_query_callback().
-**
-** Note that the first 5 fields of this structure are identical to
-** sqlite3_rtree_geometry.  This structure is a subclass of
-** sqlite3_rtree_geometry.
-*/
-struct sqlite3_rtree_query_info {
-  void *pContext;                   /* pContext from when function registered */
-  int nParam;                       /* Number of function parameters */
-  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
-  void *pUser;                      /* callback can use this, if desired */
-  void (*xDelUser)(void*);          /* function to free pUser */
-  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
-  unsigned int *anQueue;            /* Number of pending entries in the queue */
-  int nCoord;                       /* Number of coordinates */
-  int iLevel;                       /* Level of current node or entry */
-  int mxLevel;                      /* The largest iLevel value in the tree */
-  sqlite3_int64 iRowid;             /* Rowid for current entry */
-  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
-  int eParentWithin;                /* Visibility of parent node */
-  int eWithin;                      /* OUT: Visiblity */
-  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
-  /* The following fields are only available in 3.8.11 and later */
-  sqlite3_value **apSqlParam;       /* Original SQL values of parameters */
-};
-
-/*
-** Allowed values for sqlite3_rtree_query.eWithin and .eParentWithin.
-*/
-#define NOT_WITHIN       0   /* Object completely outside of query region */
-#define PARTLY_WITHIN    1   /* Object partially overlaps query region */
-#define FULLY_WITHIN     2   /* Object fully contained within query region */
-
-
-#ifdef __cplusplus
-}  /* end of the 'extern "C"' block */
-#endif
-
-#endif  /* ifndef _SQLITE3RTREE_H_ */
diff --git a/lib/libsqlite3/ext/rtree/tkt3363.test b/lib/libsqlite3/ext/rtree/tkt3363.test
deleted file mode 100644
index db05ed527a1..00000000000
--- a/lib/libsqlite3/ext/rtree/tkt3363.test
+++ /dev/null
@@ -1,50 +0,0 @@
-# 2008 Sep 08
-#
-# 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.
-#
-#***********************************************************************
-#
-# The focus of this file is testing that ticket #3363 is fixed.
-#
-
-if {![info exists testdir]} {
-  set testdir [file join [file dirname [info script]] .. .. test]
-}
-source [file join [file dirname [info script]] rtree_util.tcl]
-source $testdir/tester.tcl
-
-ifcapable !rtree {
-  finish_test
-  return
-}
-
-do_test tkt3363.1.1 {
-  execsql { CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2) }
-} {}
-
-do_test tkt3363.1.2 {
-  for {set ii 1} {$ii < 50} {incr ii} {
-    set x 1000000
-    set y [expr 4000000 + $ii*10]
-    execsql { INSERT INTO t1 VALUES($ii, $x, $x, $y, $y) }
-  }
-} {}
-
-do_test tkt3363.1.3 {
-  execsql { 
-    SELECT count(*) FROM t1 WHERE +y2>4000425.0;
-  }
-} {7}
-
-do_test tkt3363.1.4 {
-  execsql { 
-    SELECT count(*) FROM t1 WHERE y2>4000425.0;
-  }
-} {7}
-
-finish_test
diff --git a/lib/libsqlite3/ext/rtree/viewrtree.tcl b/lib/libsqlite3/ext/rtree/viewrtree.tcl
deleted file mode 100644
index 794677f5a37..00000000000
--- a/lib/libsqlite3/ext/rtree/viewrtree.tcl
+++ /dev/null
@@ -1,188 +0,0 @@
-
-load ./libsqlite3.dylib
-#package require sqlite3
-source [file join [file dirname $argv0] rtree_util.tcl]
-
-wm title . "SQLite r-tree viewer"
-
-if {[llength $argv]!=1} {
-  puts stderr "Usage: $argv0 <database-file>"
-  puts stderr ""
-  exit
-}
-sqlite3 db [lindex $argv 0]
-
-canvas .c -background white -width 400 -height 300 -highlightthickness 0
-
-button .b -text "Parent Node" -command {
-  set sql "SELECT parentnode FROM $::O(zTab)_parent WHERE nodeno = $::O(iNode)"
-  set ::O(iNode) [db one $sql]
-  if {$::O(iNode) eq ""} {set ::O(iNode) 1}
-  view_node
-}
-
-set O(iNode) 1
-set O(zTab) ""
-set O(listbox_captions)  [list]
-set O(listbox_itemmap)   [list]
-set O(listbox_highlight) -1
-
-listbox   .l -listvariable ::O(listbox_captions) -yscrollcommand {.ls set}
-scrollbar .ls -command {.l yview}
-label     .status -font courier -anchor w
-label     .title -anchor w -text "Node 1:" -background white -borderwidth 0
-
-
-set rtree_tables [list]
-db eval {
-  SELECT name 
-  FROM sqlite_master 
-  WHERE type='table' AND sql LIKE '%virtual%table%using%rtree%'
-} {
-  set nCol [expr [llength [db eval "pragma table_info($name)"]]/6]
-  if {$nCol != 5} {
-    puts stderr "Not viewing $name - is not 2-dimensional"
-  } else {
-    lappend rtree_tables [list Table $name]
-  }
-}
-if {$rtree_tables eq ""} {
-  puts stderr "Cannot find an r-tree table in database [lindex $argv 0]"
-  puts stderr ""
-  exit
-}
-eval tk_optionMenu .select option_var $rtree_tables
-trace add variable option_var write set_option_var
-proc set_option_var {args} {
-  set ::O(zTab) [lindex $::option_var 1]
-  set ::O(iNode) 1
-  view_node
-}
-set ::O(zTab) [lindex $::rtree_tables 0 1]
-
-bind .l <1> {listbox_click [.l nearest %y]}
-bind .l <Motion> {listbox_mouseover [.l nearest %y]}
-bind .l <Leave>  {listbox_mouseover -1}
-
-proc listbox_click {sel} {
-  if {$sel ne ""} {
-    set ::O(iNode) [lindex $::O(listbox_captions) $sel 1]
-    view_node
-  }
-}
-proc listbox_mouseover {i} {
-  set oldid [lindex $::O(listbox_itemmap) $::O(listbox_highlight)]
-  .c itemconfigure $oldid -fill ""
-
-  .l selection clear 0 end
-  .status configure -text ""
-  if {$i>=0} {
-    set id [lindex $::O(listbox_itemmap) $i]
-    .c itemconfigure $id -fill grey
-    .c lower $id
-    set ::O(listbox_highlight) $i
-    .l selection set $i
-    .status configure -text [cell_report db $::O(zTab) $::O(iNode) $i]
-  }
-}
-
-grid configure .select  -row 0 -column 0 -columnspan 2 -sticky nsew
-grid configure .b       -row 1 -column 0 -columnspan 2 -sticky nsew
-grid configure .l       -row 2 -column 0               -sticky nsew
-grid configure .status  -row 3 -column 0 -columnspan 3 -sticky nsew
-
-grid configure .title   -row 0 -column 2               -sticky nsew
-grid configure .c       -row 1 -column 2 -rowspan 2    -sticky nsew
-grid configure .ls      -row 2 -column 1               -sticky nsew
-
-grid columnconfigure . 2 -weight 1
-grid rowconfigure    . 2 -weight 1
-
-proc node_bbox {data} {
-  set xmin 0
-  set xmax 0
-  set ymin 0
-  set ymax 0
-  foreach {rowid xmin xmax ymin ymax} [lindex $data 0] break
-  foreach cell [lrange $data 1 end] {
-    foreach {rowid x1 x2 y1 y2} $cell break
-    if {$x1 < $xmin} {set xmin $x1}
-    if {$x2 > $xmax} {set xmax $x2}
-    if {$y1 < $ymin} {set ymin $y1}
-    if {$y2 > $ymax} {set ymax $y2}
-  }
-  list $xmin $xmax $ymin $ymax
-}
-
-proc view_node {} {
-  set iNode $::O(iNode)
-  set zTab $::O(zTab)
-
-  set data [rtree_node db $zTab $iNode 12]
-  set depth [rtree_nodedepth db $zTab $iNode]
-
-  .c delete all
-  set ::O(listbox_captions) [list]
-  set ::O(listbox_itemmap) [list]
-  set $::O(listbox_highlight) -1
-
-  .b configure -state normal
-  if {$iNode == 1} {.b configure -state disabled}
-  .title configure -text "Node $iNode: [cell_report db $zTab $iNode -1]"
-
-  foreach {xmin xmax ymin ymax} [node_bbox $data] break
-  set total_area 0.0
-
-  set xscale [expr {double([winfo width .c]-20)/($xmax-$xmin)}]
-  set yscale [expr {double([winfo height .c]-20)/($ymax-$ymin)}]
-
-  set xoff [expr {10.0 - $xmin*$xscale}]
-  set yoff [expr {10.0 - $ymin*$yscale}]
-
-  foreach cell $data {
-    foreach {rowid x1 x2 y1 y2} $cell break
-    set total_area [expr {$total_area + ($x2-$x1)*($y2-$y1)}]
-    set x1 [expr {$x1*$xscale + $xoff}]
-    set x2 [expr {$x2*$xscale + $xoff}]
-    set y1 [expr {$y1*$yscale + $yoff}]
-    set y2 [expr {$y2*$yscale + $yoff}]
-
-    set id [.c create rectangle $x1 $y1 $x2 $y2]
-    if {$depth>0} {
-      lappend ::O(listbox_captions) "Node $rowid"
-      lappend ::O(listbox_itemmap) $id
-    }
-  }
-}
-
-proc cell_report {db zTab iParent iCell} {
-  set data [rtree_node db $zTab $iParent 12]
-  set cell [lindex $data $iCell]
-
-  foreach {xmin xmax ymin ymax} [node_bbox $data] break
-  set total_area [expr ($xmax-$xmin)*($ymax-$ymin)]
-
-  if {$cell eq ""} {
-    set cell_area 0.0
-    foreach cell $data {
-      foreach {rowid x1 x2 y1 y2} $cell break
-      set cell_area [expr $cell_area+($x2-$x1)*($y2-$y1)]
-    }
-    set cell_area [expr $cell_area/[llength $data]]
-    set zReport [format "Size = %.1f x %.1f    Average child area = %.1f%%" \
-      [expr $xmax-$xmin] [expr $ymax-$ymin] [expr 100.0*$cell_area/$total_area]\
-    ]
-    append zReport "   Sub-tree height: [rtree_nodedepth db $zTab $iParent]"
-  } else {
-    foreach {rowid x1 x2 y1 y2} $cell break
-    set cell_area  [expr ($x2-$x1)*($y2-$y1)]
-    set zReport [format "Size = %.1f x %.1f    Area = %.1f%%" \
-      [expr $x2-$x1] [expr $y2-$y1] [expr 100.0*$cell_area/$total_area]
-    ]
-  }
-
-  return $zReport
-}
-
-view_node
-bind .c <Configure> view_node