Imported Upstream version 2.0.3

19 files changed, 5954 insertions, 0 deletions

diff --git a/ext/rtree/README b/ext/rtree/README
new file mode 100644
index 0000000..3736f45
--- /dev/null
+++ b/ext/rtree/README
@@ -0,0 +1,120 @@
+
+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/ext/rtree/rtree.c b/ext/rtree/rtree.c
new file mode 100644
index 0000000..884482e
--- /dev/null
+++ b/ext/rtree/rtree.c
@@ -0,0 +1,3285 @@
+/*
+** 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)
+
+/*
+** This file contains an implementation of a couple of different variants
+** of the r-tree algorithm. See the README file for further details. The 
+** same data-structure is used for all, but the algorithms for insert and
+** delete operations vary. The variants used are selected at compile time 
+** by defining the following symbols:
+*/
+
+/* Either, both or none of the following may be set to activate 
+** r*tree variant algorithms.
+*/
+#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
+#define VARIANT_RSTARTREE_REINSERT      1
+
+/* 
+** Exactly one of the following must be set to 1.
+*/
+#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
+#define VARIANT_GUTTMAN_LINEAR_SPLIT    0
+#define VARIANT_RSTARTREE_SPLIT         1
+
+#define VARIANT_GUTTMAN_SPLIT \
+        (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
+
+#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
+  #define PickNext QuadraticPickNext
+  #define PickSeeds QuadraticPickSeeds
+  #define AssignCells splitNodeGuttman
+#endif
+#if VARIANT_GUTTMAN_LINEAR_SPLIT
+  #define PickNext LinearPickNext
+  #define PickSeeds LinearPickSeeds
+  #define AssignCells splitNodeGuttman
+#endif
+#if VARIANT_RSTARTREE_SPLIT
+  #define AssignCells splitNodeStartree
+#endif
+
+#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) 
+# define NDEBUG 1
+#endif
+
+#ifndef SQLITE_CORE
+  #include "sqlite3ext.h"
+  SQLITE_EXTENSION_INIT1
+#else
+  #include "sqlite3.h"
+#endif
+
+#include <string.h>
+#include <assert.h>
+
+#ifndef SQLITE_AMALGAMATION
+#include "sqlite3rtree.h"
+typedef sqlite3_int64 i64;
+typedef unsigned char u8;
+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;
+
+/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
+#define RTREE_MAX_DIMENSIONS 5
+
+/* Size of hash table Rtree.aHash. This hash table is not expected to
+** ever contain very many entries, so a fixed number of buckets is 
+** used.
+*/
+#define HASHSIZE 128
+
+/* 
+** An rtree virtual-table object.
+*/
+struct Rtree {
+  sqlite3_vtab base;
+  sqlite3 *db;                /* Host database connection */
+  int iNodeSize;              /* Size in bytes of each node in the node table */
+  int nDim;                   /* Number of dimensions */
+  int nBytesPerCell;          /* Bytes consumed per cell */
+  int iDepth;                 /* Current depth of the r-tree structure */
+  char *zDb;                  /* Name of database containing r-tree table */
+  char *zName;                /* Name of r-tree table */ 
+  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
+  int nBusy;                  /* Current number of users of this structure */
+
+  /* List of nodes removed during a CondenseTree operation. List is
+  ** linked together via the pointer normally used for hash chains -
+  ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 
+  ** headed by the node (leaf nodes have RtreeNode.iNode==0).
+  */
+  RtreeNode *pDeleted;
+  int iReinsertHeight;        /* Height of sub-trees Reinsert() has run on */
+
+  /* Statements to read/write/delete a record from xxx_node */
+  sqlite3_stmt *pReadNode;
+  sqlite3_stmt *pWriteNode;
+  sqlite3_stmt *pDeleteNode;
+
+  /* Statements to read/write/delete a record from xxx_rowid */
+  sqlite3_stmt *pReadRowid;
+  sqlite3_stmt *pWriteRowid;
+  sqlite3_stmt *pDeleteRowid;
+
+  /* Statements to read/write/delete a record from xxx_parent */
+  sqlite3_stmt *pReadParent;
+  sqlite3_stmt *pWriteParent;
+  sqlite3_stmt *pDeleteParent;
+
+  int eCoordType;
+};
+
+/* Possible values for eCoordType: */
+#define RTREE_COORD_REAL32 0
+#define RTREE_COORD_INT32  1
+
+/*
+** The minimum number of cells allowed for a node is a third of the 
+** maximum. In Gutman's notation:
+**
+**     m = M/3
+**
+** If an R*-tree "Reinsert" operation is required, the same number of
+** cells are removed from the overfull node and reinserted into the tree.
+*/
+#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
+#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
+#define RTREE_MAXCELLS 51
+
+/*
+** 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
+
+/* 
+** An rtree cursor object.
+*/
+struct RtreeCursor {
+  sqlite3_vtab_cursor base;
+  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
+  int iCell;                        /* Index of current cell in pNode */
+  int iStrategy;                    /* Copy of idxNum search parameter */
+  int nConstraint;                  /* Number of entries in aConstraint */
+  RtreeConstraint *aConstraint;     /* Search constraints. */
+};
+
+union RtreeCoord {
+  float f;
+  int i;
+};
+
+/*
+** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
+** formatted as a double. This macro assumes that local variable pRtree points
+** to the Rtree structure associated with the RtreeCoord.
+*/
+#define DCOORD(coord) (                           \
+  (pRtree->eCoordType==RTREE_COORD_REAL32) ?      \
+    ((double)coord.f) :                           \
+    ((double)coord.i)                             \
+)
+
+/*
+** A search constraint.
+*/
+struct RtreeConstraint {
+  int iCoord;                     /* Index of constrained coordinate */
+  int op;                         /* Constraining operation */
+  double rValue;                  /* Constraint value. */
+  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
+  sqlite3_rtree_geometry *pGeom;  /* Constraint callback argument for a MATCH */
+};
+
+/* Possible values for RtreeConstraint.op */
+#define RTREE_EQ    0x41
+#define RTREE_LE    0x42
+#define RTREE_LT    0x43
+#define RTREE_GE    0x44
+#define RTREE_GT    0x45
+#define RTREE_MATCH 0x46
+
+/* 
+** An rtree structure node.
+*/
+struct RtreeNode {
+  RtreeNode *pParent;               /* Parent node */
+  i64 iNode;
+  int nRef;
+  int isDirty;
+  u8 *zData;
+  RtreeNode *pNext;                 /* Next node in this hash chain */
+};
+#define NCELL(pNode) readInt16(&(pNode)->zData[2])
+
+/* 
+** Structure to store a deserialized rtree record.
+*/
+struct RtreeCell {
+  i64 iRowid;
+  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
+};
+
+
+/*
+** 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 must be supplied as a blob argument to
+** the right-hand-side of an SQL MATCH operator used to constrain an
+** r-tree query.
+*/
+struct RtreeMatchArg {
+  u32 magic;                      /* Always RTREE_GEOMETRY_MAGIC */
+  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
+  void *pContext;
+  int nParam;
+  double aParam[1];
+};
+
+/*
+** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
+** a single instance of the following structure is allocated. It is used
+** as the context for the user-function created by by s_r_g_c(). The object
+** is eventually deleted by the destructor mechanism provided by
+** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
+** the geometry callback function).
+*/
+struct RtreeGeomCallback {
+  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
+  void *pContext;
+};
+
+#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){
+  u32 i = (
+    (((u32)p[0]) << 24) + 
+    (((u32)p[1]) << 16) + 
+    (((u32)p[2]) <<  8) + 
+    (((u32)p[3]) <<  0)
+  );
+  *(u32 *)pCoord = i;
+}
+static i64 readInt64(u8 *p){
+  return (
+    (((i64)p[0]) << 56) + 
+    (((i64)p[1]) << 48) + 
+    (((i64)p[2]) << 40) + 
+    (((i64)p[3]) << 32) + 
+    (((i64)p[4]) << 24) + 
+    (((i64)p[5]) << 16) + 
+    (((i64)p[6]) <<  8) + 
+    (((i64)p[7]) <<  0)
+  );
+}
+
+/*
+** Functions to serialize a 16 bit integer, 32 bit real number and
+** 64 bit integer. The value returned is the number of bytes written
+** to the argument buffer (always 2, 4 and 8 respectively).
+*/
+static int writeInt16(u8 *p, int i){
+  p[0] = (i>> 8)&0xFF;
+  p[1] = (i>> 0)&0xFF;
+  return 2;
+}
+static int writeCoord(u8 *p, RtreeCoord *pCoord){
+  u32 i;
+  assert( sizeof(RtreeCoord)==4 );
+  assert( sizeof(u32)==4 );
+  i = *(u32 *)pCoord;
+  p[0] = (i>>24)&0xFF;
+  p[1] = (i>>16)&0xFF;
+  p[2] = (i>> 8)&0xFF;
+  p[3] = (i>> 0)&0xFF;
+  return 4;
+}
+static int writeInt64(u8 *p, i64 i){
+  p[0] = (i>>56)&0xFF;
+  p[1] = (i>>48)&0xFF;
+  p[2] = (i>>40)&0xFF;
+  p[3] = (i>>32)&0xFF;
+  p[4] = (i>>24)&0xFF;
+  p[5] = (i>>16)&0xFF;
+  p[6] = (i>> 8)&0xFF;
+  p[7] = (i>> 0)&0xFF;
+  return 8;
+}
+
+/*
+** Increment the reference count of node p.
+*/
+static void nodeReference(RtreeNode *p){
+  if( p ){
+    p->nRef++;
+  }
+}
+
+/*
+** Clear the content of node p (set all bytes to 0x00).
+*/
+static void nodeZero(Rtree *pRtree, RtreeNode *p){
+  memset(&p->zData[2], 0, pRtree->iNodeSize-2);
+  p->isDirty = 1;
+}
+
+/*
+** Given a node number iNode, return the corresponding key to use
+** in the Rtree.aHash table.
+*/
+static int nodeHash(i64 iNode){
+  return (
+    (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 
+    (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
+  ) % HASHSIZE;
+}
+
+/*
+** Search the node hash table for node iNode. If found, return a pointer
+** to it. Otherwise, return 0.
+*/
+static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
+  RtreeNode *p;
+  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, 
+  RtreeNode *pNode,  
+  RtreeCell *pCell, 
+  int iCell
+){
+  int ii;
+  u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
+  p += writeInt64(p, pCell->iRowid);
+  for(ii=0; ii<(pRtree->nDim*2); ii++){
+    p += writeCoord(p, &pCell->aCoord[ii]);
+  }
+  pNode->isDirty = 1;
+}
+
+/*
+** Remove cell the cell with index iCell from node pNode.
+*/
+static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
+  u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
+  u8 *pSrc = &pDst[pRtree->nBytesPerCell];
+  int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
+  memmove(pDst, pSrc, nByte);
+  writeInt16(&pNode->zData[2], NCELL(pNode)-1);
+  pNode->isDirty = 1;
+}
+
+/*
+** Insert the contents of cell pCell into node pNode. If the insert
+** is successful, return SQLITE_OK.
+**
+** If there is not enough free space in pNode, return SQLITE_FULL.
+*/
+static int
+nodeInsertCell(
+  Rtree *pRtree, 
+  RtreeNode *pNode, 
+  RtreeCell *pCell 
+){
+  int nCell;                    /* Current number of cells in pNode */
+  int nMaxCell;                 /* Maximum number of cells for pNode */
+
+  nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
+  nCell = NCELL(pNode);
+
+  assert( nCell<=nMaxCell );
+  if( nCell<nMaxCell ){
+    nodeOverwriteCell(pRtree, pNode, pCell, nCell);
+    writeInt16(&pNode->zData[2], nCell+1);
+    pNode->isDirty = 1;
+  }
+
+  return (nCell==nMaxCell);
+}
+
+/*
+** If the node is dirty, write it out to the database.
+*/
+static int
+nodeWrite(Rtree *pRtree, RtreeNode *pNode){
+  int rc = SQLITE_OK;
+  if( pNode->isDirty ){
+    sqlite3_stmt *p = pRtree->pWriteNode;
+    if( pNode->iNode ){
+      sqlite3_bind_int64(p, 1, pNode->iNode);
+    }else{
+      sqlite3_bind_null(p, 1);
+    }
+    sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
+    sqlite3_step(p);
+    pNode->isDirty = 0;
+    rc = sqlite3_reset(p);
+    if( pNode->iNode==0 && rc==SQLITE_OK ){
+      pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
+      nodeHashInsert(pRtree, pNode);
+    }
+  }
+  return rc;
+}
+
+/*
+** Release a reference to a node. If the node is dirty and the reference
+** count drops to zero, the node data is written to the database.
+*/
+static int
+nodeRelease(Rtree *pRtree, RtreeNode *pNode){
+  int rc = SQLITE_OK;
+  if( pNode ){
+    assert( pNode->nRef>0 );
+    pNode->nRef--;
+    if( pNode->nRef==0 ){
+      if( pNode->iNode==1 ){
+        pRtree->iDepth = -1;
+      }
+      if( pNode->pParent ){
+        rc = nodeRelease(pRtree, pNode->pParent);
+      }
+      if( rc==SQLITE_OK ){
+        rc = nodeWrite(pRtree, pNode);
+      }
+      nodeHashDelete(pRtree, pNode);
+      sqlite3_free(pNode);
+    }
+  }
+  return rc;
+}
+
+/*
+** Return the 64-bit integer value associated with cell iCell of
+** node pNode. If pNode is a leaf node, this is a rowid. If it is
+** an internal node, then the 64-bit integer is a child page number.
+*/
+static i64 nodeGetRowid(
+  Rtree *pRtree, 
+  RtreeNode *pNode, 
+  int iCell
+){
+  assert( iCell<NCELL(pNode) );
+  return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
+}
+
+/*
+** Return coordinate iCoord from cell iCell in node pNode.
+*/
+static void nodeGetCoord(
+  Rtree *pRtree, 
+  RtreeNode *pNode, 
+  int iCell,
+  int iCoord,
+  RtreeCoord *pCoord           /* Space to write result to */
+){
+  readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
+}
+
+/*
+** Deserialize cell iCell of node pNode. Populate the structure pointed
+** to by pCell with the results.
+*/
+static void nodeGetCell(
+  Rtree *pRtree, 
+  RtreeNode *pNode, 
+  int iCell,
+  RtreeCell *pCell
+){
+  int ii;
+  pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
+  for(ii=0; ii<pRtree->nDim*2; ii++){
+    nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
+  }
+}
+
+
+/* Forward declaration for the function that does the work of
+** the virtual table module xCreate() and xConnect() methods.
+*/
+static int rtreeInit(
+  sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int
+);
+
+/* 
+** 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_geometry *pGeom = pCsr->aConstraint[i].pGeom;
+      if( pGeom ){
+        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
+        sqlite3_free(pGeom);
+      }
+    }
+    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 rc;
+  RtreeCursor *pCsr = (RtreeCursor *)cur;
+  freeCursorConstraints(pCsr);
+  rc = nodeRelease(pRtree, pCsr->pNode);
+  sqlite3_free(pCsr);
+  return rc;
+}
+
+/*
+** Rtree virtual table module xEof method.
+**
+** Return non-zero if the cursor does not currently point to a valid 
+** record (i.e if the scan has finished), or zero otherwise.
+*/
+static int rtreeEof(sqlite3_vtab_cursor *cur){
+  RtreeCursor *pCsr = (RtreeCursor *)cur;
+  return (pCsr->pNode==0);
+}
+
+/*
+** The r-tree constraint passed as the second argument to this function is
+** guaranteed to be a MATCH constraint.
+*/
+static int testRtreeGeom(
+  Rtree *pRtree,                  /* R-Tree object */
+  RtreeConstraint *pConstraint,   /* MATCH constraint to test */
+  RtreeCell *pCell,               /* Cell to test */
+  int *pbRes                      /* OUT: Test result */
+){
+  int i;
+  double aCoord[RTREE_MAX_DIMENSIONS*2];
+  int nCoord = pRtree->nDim*2;
+
+  assert( pConstraint->op==RTREE_MATCH );
+  assert( pConstraint->pGeom );
+
+  for(i=0; i<nCoord; i++){
+    aCoord[i] = DCOORD(pCell->aCoord[i]);
+  }
+  return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
+}
+
+/* 
+** Cursor pCursor currently points to a cell in a non-leaf page.
+** Set *pbEof to true if the sub-tree headed by the cell is filtered
+** (excluded) by the constraints in the pCursor->aConstraint[] 
+** array, or false otherwise.
+**
+** Return SQLITE_OK if successful or an SQLite error code if an error
+** occurs within a geometry callback.
+*/
+static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
+  RtreeCell cell;
+  int ii;
+  int bRes = 0;
+  int rc = SQLITE_OK;
+
+  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
+  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
+    RtreeConstraint *p = &pCursor->aConstraint[ii];
+    double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
+    double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
+
+    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
+        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
+    );
+
+    switch( p->op ){
+      case RTREE_LE: case RTREE_LT: 
+        bRes = p->rValue<cell_min; 
+        break;
+
+      case RTREE_GE: case RTREE_GT: 
+        bRes = p->rValue>cell_max; 
+        break;
+
+      case RTREE_EQ:
+        bRes = (p->rValue>cell_max || p->rValue<cell_min);
+        break;
+
+      default: {
+        assert( p->op==RTREE_MATCH );
+        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
+        bRes = !bRes;
+        break;
+      }
+    }
+  }
+
+  *pbEof = bRes;
+  return rc;
+}
+
+/* 
+** Test if the cell that cursor pCursor currently points to
+** would be filtered (excluded) by the constraints in the 
+** pCursor->aConstraint[] array. If so, set *pbEof to true before
+** returning. If the cell is not filtered (excluded) by the constraints,
+** set pbEof to zero.
+**
+** Return SQLITE_OK if successful or an SQLite error code if an error
+** occurs within a geometry callback.
+**
+** This function assumes that the cell is part of a leaf node.
+*/
+static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
+  RtreeCell cell;
+  int ii;
+  *pbEof = 0;
+
+  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
+  for(ii=0; ii<pCursor->nConstraint; ii++){
+    RtreeConstraint *p = &pCursor->aConstraint[ii];
+    double coord = DCOORD(cell.aCoord[p->iCoord]);
+    int res;
+    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
+        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
+    );
+    switch( p->op ){
+      case RTREE_LE: res = (coord<=p->rValue); break;
+      case RTREE_LT: res = (coord<p->rValue);  break;
+      case RTREE_GE: res = (coord>=p->rValue); break;
+      case RTREE_GT: res = (coord>p->rValue);  break;
+      case RTREE_EQ: res = (coord==p->rValue); break;
+      default: {
+        int rc;
+        assert( p->op==RTREE_MATCH );
+        rc = testRtreeGeom(pRtree, p, &cell, &res);
+        if( rc!=SQLITE_OK ){
+          return rc;
+        }
+        break;
+      }
+    }
+
+    if( !res ){
+      *pbEof = 1;
+      return SQLITE_OK;
+    }
+  }
+
+  return SQLITE_OK;
+}
+
+/*
+** Cursor pCursor currently points at a node that heads a sub-tree of
+** height iHeight (if iHeight==0, then the node is a leaf). Descend
+** to point to the left-most cell of the sub-tree that matches the 
+** configured constraints.
+*/
+static int descendToCell(
+  Rtree *pRtree, 
+  RtreeCursor *pCursor, 
+  int iHeight,
+  int *pEof                 /* OUT: Set to true if cannot descend */
+){
+  int isEof;
+  int rc;
+  int ii;
+  RtreeNode *pChild;
+  sqlite3_int64 iRowid;
+
+  RtreeNode *pSavedNode = pCursor->pNode;
+  int iSavedCell = pCursor->iCell;
+
+  assert( iHeight>=0 );
+
+  if( iHeight==0 ){
+    rc = testRtreeEntry(pRtree, pCursor, &isEof);
+  }else{
+    rc = testRtreeCell(pRtree, pCursor, &isEof);
+  }
+  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
+    goto descend_to_cell_out;
+  }
+
+  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
+  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
+  if( rc!=SQLITE_OK ){
+    goto descend_to_cell_out;
+  }
+
+  nodeRelease(pRtree, pCursor->pNode);
+  pCursor->pNode = pChild;
+  isEof = 1;
+  for(ii=0; isEof && ii<NCELL(pChild); ii++){
+    pCursor->iCell = ii;
+    rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
+    if( rc!=SQLITE_OK ){
+      goto descend_to_cell_out;
+    }
+  }
+
+  if( isEof ){
+    assert( pCursor->pNode==pChild );
+    nodeReference(pSavedNode);
+    nodeRelease(pRtree, pChild);
+    pCursor->pNode = pSavedNode;
+    pCursor->iCell = iSavedCell;
+  }
+
+descend_to_cell_out:
+  *pEof = isEof;
+  return rc;
+}
+
+/*
+** 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);
+  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;
+}
+
+/* 
+** Rtree virtual table module xNext method.
+*/
+static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
+  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
+  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+  int rc = SQLITE_OK;
+
+  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
+  ** already at EOF. It is against the rules to call the xNext() method of
+  ** a cursor that has already reached EOF.
+  */
+  assert( pCsr->pNode );
+
+  if( pCsr->iStrategy==1 ){
+    /* This "scan" is a direct lookup by rowid. There is no next entry. */
+    nodeRelease(pRtree, pCsr->pNode);
+    pCsr->pNode = 0;
+  }else{
+    /* Move to the next entry that matches the configured constraints. */
+    int iHeight = 0;
+    while( pCsr->pNode ){
+      RtreeNode *pNode = pCsr->pNode;
+      int nCell = NCELL(pNode);
+      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
+        int isEof;
+        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
+        if( rc!=SQLITE_OK || !isEof ){
+          return rc;
+        }
+      }
+      pCsr->pNode = pNode->pParent;
+      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
+      if( rc!=SQLITE_OK ){
+        return rc;
+      }
+      nodeReference(pCsr->pNode);
+      nodeRelease(pRtree, pNode);
+      iHeight++;
+    }
+  }
+
+  return rc;
+}
+
+/* 
+** Rtree virtual table module xRowid method.
+*/
+static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
+  Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
+  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+
+  assert(pCsr->pNode);
+  *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
+
+  return SQLITE_OK;
+}
+
+/* 
+** Rtree virtual table module xColumn method.
+*/
+static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
+  Rtree *pRtree = (Rtree *)cur->pVtab;
+  RtreeCursor *pCsr = (RtreeCursor *)cur;
+
+  if( i==0 ){
+    i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
+    sqlite3_result_int64(ctx, iRowid);
+  }else{
+    RtreeCoord c;
+    nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
+    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
+      sqlite3_result_double(ctx, c.f);
+    }else{
+      assert( pRtree->eCoordType==RTREE_COORD_INT32 );
+      sqlite3_result_int(ctx, c.i);
+    }
+  }
+
+  return SQLITE_OK;
+}
+
+/* 
+** Use nodeAcquire() to obtain the leaf node containing the record with 
+** rowid iRowid. If successful, set *ppLeaf to point to the node and
+** return SQLITE_OK. If there is no such record in the table, set
+** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
+** to zero and return an SQLite error code.
+*/
+static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
+  int rc;
+  *ppLeaf = 0;
+  sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
+  if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
+    i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
+    rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
+    sqlite3_reset(pRtree->pReadRowid);
+  }else{
+    rc = sqlite3_reset(pRtree->pReadRowid);
+  }
+  return rc;
+}
+
+/*
+** 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 *p;
+  sqlite3_rtree_geometry *pGeom;
+  int nBlob;
+
+  /* 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) 
+   || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0
+  ){
+    return SQLITE_ERROR;
+  }
+
+  pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
+      sizeof(sqlite3_rtree_geometry) + nBlob
+  );
+  if( !pGeom ) return SQLITE_NOMEM;
+  memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
+  p = (RtreeMatchArg *)&pGeom[1];
+
+  memcpy(p, sqlite3_value_blob(pValue), nBlob);
+  if( p->magic!=RTREE_GEOMETRY_MAGIC 
+   || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double))
+  ){
+    sqlite3_free(pGeom);
+    return SQLITE_ERROR;
+  }
+
+  pGeom->pContext = p->pContext;
+  pGeom->nParam = p->nParam;
+  pGeom->aParam = p->aParam;
+
+  pCons->xGeom = p->xGeom;
+  pCons->pGeom = pGeom;
+  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;
+
+  rtreeReference(pRtree);
+
+  freeCursorConstraints(pCsr);
+  pCsr->iStrategy = idxNum;
+
+  if( idxNum==1 ){
+    /* Special case - lookup by rowid. */
+    RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
+    i64 iRowid = sqlite3_value_int64(argv[0]);
+    rc = findLeafNode(pRtree, iRowid, &pLeaf);
+    pCsr->pNode = pLeaf; 
+    if( pLeaf ){
+      assert( rc==SQLITE_OK );
+      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
+    }
+  }else{
+    /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
+    ** with the configured constraints. 
+    */
+    if( argc>0 ){
+      pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
+      pCsr->nConstraint = argc;
+      if( !pCsr->aConstraint ){
+        rc = SQLITE_NOMEM;
+      }else{
+        memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
+        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]-'a';
+          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;
+            }
+          }else{
+            p->rValue = sqlite3_value_double(argv[ii]);
+          }
+        }
+      }
+    }
+  
+    if( rc==SQLITE_OK ){
+      pCsr->pNode = 0;
+      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
+    }
+    if( rc==SQLITE_OK ){
+      int isEof = 1;
+      int nCell = NCELL(pRoot);
+      pCsr->pNode = pRoot;
+      for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
+        assert( pCsr->pNode==pRoot );
+        rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
+        if( !isEof ){
+          break;
+        }
+      }
+      if( rc==SQLITE_OK && isEof ){
+        assert( pCsr->pNode==pRoot );
+        nodeRelease(pRtree, pRoot);
+        pCsr->pNode = 0;
+      }
+      assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
+    }
+  }
+
+  rtreeRelease(pRtree);
+  return rc;
+}
+
+/*
+** Rtree virtual table module xBestIndex method. There are three
+** table scan strategies to choose from (in order from most to 
+** least desirable):
+**
+**   idxNum     idxStr        Strategy
+**   ------------------------------------------------
+**     1        Unused        Direct lookup by rowid.
+**     2        See below     R-tree query 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){
+  int rc = SQLITE_OK;
+  int ii;
+
+  int iIdx = 0;
+  char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
+  memset(zIdxStr, 0, sizeof(zIdxStr));
+  UNUSED_PARAMETER(tab);
+
+  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( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
+      /* We have an equality constraint on the rowid. Use strategy 1. */
+      int jj;
+      for(jj=0; jj<ii; jj++){
+        pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
+        pIdxInfo->aConstraintUsage[jj].omit = 0;
+      }
+      pIdxInfo->idxNum = 1;
+      pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
+      pIdxInfo->aConstraintUsage[jj].omit = 1;
+
+      /* This strategy involves a two rowid lookups on an B-Tree structures
+      ** and then a linear search of an R-Tree node. This should be 
+      ** considered almost as quick as a direct rowid lookup (for which 
+      ** sqlite uses an internal cost of 0.0).
+      */ 
+      pIdxInfo->estimatedCost = 10.0;
+      return SQLITE_OK;
+    }
+
+    if( p->usable && (p->iColumn>0 || 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 + 'a';
+      pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
+      pIdxInfo->aConstraintUsage[ii].omit = 1;
+    }
+  }
+
+  pIdxInfo->idxNum = 2;
+  pIdxInfo->needToFreeIdxStr = 1;
+  if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
+    return SQLITE_NOMEM;
+  }
+  assert( iIdx>=0 );
+  pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
+  return rc;
+}
+
+/*
+** Return the N-dimensional volumn of the cell stored in *p.
+*/
+static float cellArea(Rtree *pRtree, RtreeCell *p){
+  float area = 1.0;
+  int ii;
+  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+    area = (float)(area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])));
+  }
+  return area;
+}
+
+/*
+** Return the margin length of cell p. The margin length is the sum
+** of the objects size in each dimension.
+*/
+static float cellMargin(Rtree *pRtree, RtreeCell *p){
+  float margin = 0.0;
+  int ii;
+  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+    margin += (float)(DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
+  }
+  return margin;
+}
+
+/*
+** Store the union of cells p1 and p2 in p1.
+*/
+static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
+  int ii;
+  if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
+    for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+      p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
+      p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
+    }
+  }else{
+    for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+      p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
+      p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
+    }
+  }
+}
+
+/*
+** Return true if the area covered by p2 is a subset of the area covered
+** by p1. False otherwise.
+*/
+static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
+  int ii;
+  int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
+  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+    RtreeCoord *a1 = &p1->aCoord[ii];
+    RtreeCoord *a2 = &p2->aCoord[ii];
+    if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) 
+     || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) 
+    ){
+      return 0;
+    }
+  }
+  return 1;
+}
+
+/*
+** Return the amount cell p would grow by if it were unioned with pCell.
+*/
+static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
+  float area;
+  RtreeCell cell;
+  memcpy(&cell, p, sizeof(RtreeCell));
+  area = cellArea(pRtree, &cell);
+  cellUnion(pRtree, &cell, pCell);
+  return (cellArea(pRtree, &cell)-area);
+}
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
+static float cellOverlap(
+  Rtree *pRtree, 
+  RtreeCell *p, 
+  RtreeCell *aCell, 
+  int nCell, 
+  int iExclude
+){
+  int ii;
+  float overlap = 0.0;
+  for(ii=0; ii<nCell; ii++){
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+    if( ii!=iExclude )
+#else
+    assert( iExclude==-1 );
+    UNUSED_PARAMETER(iExclude);
+#endif
+    {
+      int jj;
+      float o = 1.0;
+      for(jj=0; jj<(pRtree->nDim*2); jj+=2){
+        double x1;
+        double x2;
+
+        x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
+        x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
+
+        if( x2<x1 ){
+          o = 0.0;
+          break;
+        }else{
+          o = o * (float)(x2-x1);
+        }
+      }
+      overlap += o;
+    }
+  }
+  return overlap;
+}
+#endif
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+static float cellOverlapEnlargement(
+  Rtree *pRtree, 
+  RtreeCell *p, 
+  RtreeCell *pInsert, 
+  RtreeCell *aCell, 
+  int nCell, 
+  int iExclude
+){
+  double before;
+  double after;
+  before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
+  cellUnion(pRtree, p, pInsert);
+  after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
+  return (float)(after-before);
+}
+#endif
+
+
+/*
+** This function implements the ChooseLeaf algorithm from Gutman[84].
+** ChooseSubTree in r*tree terminology.
+*/
+static int ChooseLeaf(
+  Rtree *pRtree,               /* Rtree table */
+  RtreeCell *pCell,            /* Cell to insert into rtree */
+  int iHeight,                 /* Height of sub-tree rooted at pCell */
+  RtreeNode **ppLeaf           /* OUT: Selected leaf page */
+){
+  int rc;
+  int ii;
+  RtreeNode *pNode;
+  rc = nodeAcquire(pRtree, 1, 0, &pNode);
+
+  for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
+    int iCell;
+    sqlite3_int64 iBest = 0;
+
+    float fMinGrowth = 0.0;
+    float fMinArea = 0.0;
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+    float fMinOverlap = 0.0;
+    float overlap;
+#endif
+
+    int nCell = NCELL(pNode);
+    RtreeCell cell;
+    RtreeNode *pChild;
+
+    RtreeCell *aCell = 0;
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+    if( ii==(pRtree->iDepth-1) ){
+      int jj;
+      aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
+      if( !aCell ){
+        rc = SQLITE_NOMEM;
+        nodeRelease(pRtree, pNode);
+        pNode = 0;
+        continue;
+      }
+      for(jj=0; jj<nCell; jj++){
+        nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
+      }
+    }
+#endif
+
+    /* Select the child node which will be enlarged the least if pCell
+    ** is inserted into it. Resolve ties by choosing the entry with
+    ** the smallest area.
+    */
+    for(iCell=0; iCell<nCell; iCell++){
+      int bBest = 0;
+      float growth;
+      float area;
+      nodeGetCell(pRtree, pNode, iCell, &cell);
+      growth = cellGrowth(pRtree, &cell, pCell);
+      area = cellArea(pRtree, &cell);
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+      if( ii==(pRtree->iDepth-1) ){
+        overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
+      }else{
+        overlap = 0.0;
+      }
+      if( (iCell==0) 
+       || (overlap<fMinOverlap) 
+       || (overlap==fMinOverlap && growth<fMinGrowth)
+       || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
+      ){
+        bBest = 1;
+        fMinOverlap = overlap;
+      }
+#else
+      if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
+        bBest = 1;
+      }
+#endif
+      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);
+
+#if VARIANT_GUTTMAN_LINEAR_SPLIT
+/*
+** Implementation of the linear variant of the PickNext() function from
+** Guttman[84].
+*/
+static RtreeCell *LinearPickNext(
+  Rtree *pRtree,
+  RtreeCell *aCell, 
+  int nCell, 
+  RtreeCell *pLeftBox, 
+  RtreeCell *pRightBox,
+  int *aiUsed
+){
+  int ii;
+  for(ii=0; aiUsed[ii]; ii++);
+  aiUsed[ii] = 1;
+  return &aCell[ii];
+}
+
+/*
+** Implementation of the linear variant of the PickSeeds() function from
+** Guttman[84].
+*/
+static void LinearPickSeeds(
+  Rtree *pRtree,
+  RtreeCell *aCell, 
+  int nCell, 
+  int *piLeftSeed, 
+  int *piRightSeed
+){
+  int i;
+  int iLeftSeed = 0;
+  int iRightSeed = 1;
+  float maxNormalInnerWidth = 0.0;
+
+  /* Pick two "seed" cells from the array of cells. The algorithm used
+  ** here is the LinearPickSeeds algorithm from Gutman[1984]. The 
+  ** indices of the two seed cells in the array are stored in local
+  ** variables iLeftSeek and iRightSeed.
+  */
+  for(i=0; i<pRtree->nDim; i++){
+    float x1 = DCOORD(aCell[0].aCoord[i*2]);
+    float x2 = DCOORD(aCell[0].aCoord[i*2+1]);
+    float x3 = x1;
+    float x4 = x2;
+    int jj;
+
+    int iCellLeft = 0;
+    int iCellRight = 0;
+
+    for(jj=1; jj<nCell; jj++){
+      float left = DCOORD(aCell[jj].aCoord[i*2]);
+      float right = DCOORD(aCell[jj].aCoord[i*2+1]);
+
+      if( left<x1 ) x1 = left;
+      if( right>x4 ) x4 = right;
+      if( left>x3 ){
+        x3 = left;
+        iCellRight = jj;
+      }
+      if( right<x2 ){
+        x2 = right;
+        iCellLeft = jj;
+      }
+    }
+
+    if( x4!=x1 ){
+      float normalwidth = (x3 - x2) / (x4 - x1);
+      if( normalwidth>maxNormalInnerWidth ){
+        iLeftSeed = iCellLeft;
+        iRightSeed = iCellRight;
+      }
+    }
+  }
+
+  *piLeftSeed = iLeftSeed;
+  *piRightSeed = iRightSeed;
+}
+#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
+
+#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
+/*
+** Implementation of the quadratic variant of the PickNext() function from
+** Guttman[84].
+*/
+static RtreeCell *QuadraticPickNext(
+  Rtree *pRtree,
+  RtreeCell *aCell, 
+  int nCell, 
+  RtreeCell *pLeftBox, 
+  RtreeCell *pRightBox,
+  int *aiUsed
+){
+  #define FABS(a) ((a)<0.0?-1.0*(a):(a))
+
+  int iSelect = -1;
+  float fDiff;
+  int ii;
+  for(ii=0; ii<nCell; ii++){
+    if( aiUsed[ii]==0 ){
+      float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
+      float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
+      float diff = FABS(right-left);
+      if( iSelect<0 || diff>fDiff ){
+        fDiff = diff;
+        iSelect = ii;
+      }
+    }
+  }
+  aiUsed[iSelect] = 1;
+  return &aCell[iSelect];
+}
+
+/*
+** Implementation of the quadratic variant of the PickSeeds() function from
+** Guttman[84].
+*/
+static void QuadraticPickSeeds(
+  Rtree *pRtree,
+  RtreeCell *aCell, 
+  int nCell, 
+  int *piLeftSeed, 
+  int *piRightSeed
+){
+  int ii;
+  int jj;
+
+  int iLeftSeed = 0;
+  int iRightSeed = 1;
+  float fWaste = 0.0;
+
+  for(ii=0; ii<nCell; ii++){
+    for(jj=ii+1; jj<nCell; jj++){
+      float right = cellArea(pRtree, &aCell[jj]);
+      float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
+      float waste = growth - right;
+
+      if( waste>fWaste ){
+        iLeftSeed = ii;
+        iRightSeed = jj;
+        fWaste = waste;
+      }
+    }
+  }
+
+  *piLeftSeed = iLeftSeed;
+  *piRightSeed = iRightSeed;
+}
+#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
+
+/*
+** Arguments aIdx, aDistance and aSpare all point to arrays of size
+** nIdx. The aIdx array contains the set of integers from 0 to 
+** (nIdx-1) in no particular order. This function sorts the values
+** in aIdx according to the indexed values in aDistance. For
+** example, assuming the inputs:
+**
+**   aIdx      = { 0,   1,   2,   3 }
+**   aDistance = { 5.0, 2.0, 7.0, 6.0 }
+**
+** this function sets the aIdx array to contain:
+**
+**   aIdx      = { 0,   1,   2,   3 }
+**
+** The aSpare array is used as temporary working space by the
+** sorting algorithm.
+*/
+static void SortByDistance(
+  int *aIdx, 
+  int nIdx, 
+  float *aDistance, 
+  int *aSpare
+){
+  if( nIdx>1 ){
+    int iLeft = 0;
+    int iRight = 0;
+
+    int nLeft = nIdx/2;
+    int nRight = nIdx-nLeft;
+    int *aLeft = aIdx;
+    int *aRight = &aIdx[nLeft];
+
+    SortByDistance(aLeft, nLeft, aDistance, aSpare);
+    SortByDistance(aRight, nRight, aDistance, aSpare);
+
+    memcpy(aSpare, aLeft, sizeof(int)*nLeft);
+    aLeft = aSpare;
+
+    while( iLeft<nLeft || iRight<nRight ){
+      if( iLeft==nLeft ){
+        aIdx[iLeft+iRight] = aRight[iRight];
+        iRight++;
+      }else if( iRight==nRight ){
+        aIdx[iLeft+iRight] = aLeft[iLeft];
+        iLeft++;
+      }else{
+        float fLeft = aDistance[aLeft[iLeft]];
+        float fRight = aDistance[aRight[iRight]];
+        if( fLeft<fRight ){
+          aIdx[iLeft+iRight] = aLeft[iLeft];
+          iLeft++;
+        }else{
+          aIdx[iLeft+iRight] = aRight[iRight];
+          iRight++;
+        }
+      }
+    }
+
+#if 0
+    /* Check that the sort worked */
+    {
+      int jj;
+      for(jj=1; jj<nIdx; jj++){
+        float left = aDistance[aIdx[jj-1]];
+        float right = aDistance[aIdx[jj]];
+        assert( left<=right );
+      }
+    }
+#endif
+  }
+}
+
+/*
+** Arguments aIdx, aCell and aSpare all point to arrays of size
+** nIdx. The aIdx array contains the set of integers from 0 to 
+** (nIdx-1) in no particular order. This function sorts the values
+** in aIdx according to dimension iDim of the cells in aCell. The
+** minimum value of dimension iDim is considered first, the
+** maximum used to break ties.
+**
+** The aSpare array is used as temporary working space by the
+** sorting algorithm.
+*/
+static void SortByDimension(
+  Rtree *pRtree,
+  int *aIdx, 
+  int nIdx, 
+  int iDim, 
+  RtreeCell *aCell, 
+  int *aSpare
+){
+  if( nIdx>1 ){
+
+    int iLeft = 0;
+    int iRight = 0;
+
+    int nLeft = nIdx/2;
+    int nRight = nIdx-nLeft;
+    int *aLeft = aIdx;
+    int *aRight = &aIdx[nLeft];
+
+    SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
+    SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
+
+    memcpy(aSpare, aLeft, sizeof(int)*nLeft);
+    aLeft = aSpare;
+    while( iLeft<nLeft || iRight<nRight ){
+      double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
+      double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
+      double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
+      double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
+      if( (iLeft!=nLeft) && ((iRight==nRight)
+       || (xleft1<xright1)
+       || (xleft1==xright1 && xleft2<xright2)
+      )){
+        aIdx[iLeft+iRight] = aLeft[iLeft];
+        iLeft++;
+      }else{
+        aIdx[iLeft+iRight] = aRight[iRight];
+        iRight++;
+      }
+    }
+
+#if 0
+    /* Check that the sort worked */
+    {
+      int jj;
+      for(jj=1; jj<nIdx; jj++){
+        float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
+        float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
+        float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
+        float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
+        assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
+      }
+    }
+#endif
+  }
+}
+
+#if VARIANT_RSTARTREE_SPLIT
+/*
+** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
+*/
+static int splitNodeStartree(
+  Rtree *pRtree,
+  RtreeCell *aCell,
+  int nCell,
+  RtreeNode *pLeft,
+  RtreeNode *pRight,
+  RtreeCell *pBboxLeft,
+  RtreeCell *pBboxRight
+){
+  int **aaSorted;
+  int *aSpare;
+  int ii;
+
+  int iBestDim = 0;
+  int iBestSplit = 0;
+  float fBestMargin = 0.0;
+
+  int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
+
+  aaSorted = (int **)sqlite3_malloc(nByte);
+  if( !aaSorted ){
+    return SQLITE_NOMEM;
+  }
+
+  aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
+  memset(aaSorted, 0, nByte);
+  for(ii=0; ii<pRtree->nDim; ii++){
+    int jj;
+    aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
+    for(jj=0; jj<nCell; jj++){
+      aaSorted[ii][jj] = jj;
+    }
+    SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
+  }
+
+  for(ii=0; ii<pRtree->nDim; ii++){
+    float margin = 0.0;
+    float fBestOverlap = 0.0;
+    float fBestArea = 0.0;
+    int iBestLeft = 0;
+    int nLeft;
+
+    for(
+      nLeft=RTREE_MINCELLS(pRtree); 
+      nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 
+      nLeft++
+    ){
+      RtreeCell left;
+      RtreeCell right;
+      int kk;
+      float overlap;
+      float area;
+
+      memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
+      memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
+      for(kk=1; kk<(nCell-1); kk++){
+        if( kk<nLeft ){
+          cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
+        }else{
+          cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
+        }
+      }
+      margin += cellMargin(pRtree, &left);
+      margin += cellMargin(pRtree, &right);
+      overlap = cellOverlap(pRtree, &left, &right, 1, -1);
+      area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
+      if( (nLeft==RTREE_MINCELLS(pRtree))
+       || (overlap<fBestOverlap)
+       || (overlap==fBestOverlap && area<fBestArea)
+      ){
+        iBestLeft = nLeft;
+        fBestOverlap = overlap;
+        fBestArea = area;
+      }
+    }
+
+    if( ii==0 || margin<fBestMargin ){
+      iBestDim = ii;
+      fBestMargin = margin;
+      iBestSplit = iBestLeft;
+    }
+  }
+
+  memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
+  memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
+  for(ii=0; ii<nCell; ii++){
+    RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
+    RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
+    RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
+    nodeInsertCell(pRtree, pTarget, pCell);
+    cellUnion(pRtree, pBbox, pCell);
+  }
+
+  sqlite3_free(aaSorted);
+  return SQLITE_OK;
+}
+#endif
+
+#if VARIANT_GUTTMAN_SPLIT
+/*
+** Implementation of the regular R-tree SplitNode from Guttman[1984].
+*/
+static int splitNodeGuttman(
+  Rtree *pRtree,
+  RtreeCell *aCell,
+  int nCell,
+  RtreeNode *pLeft,
+  RtreeNode *pRight,
+  RtreeCell *pBboxLeft,
+  RtreeCell *pBboxRight
+){
+  int iLeftSeed = 0;
+  int iRightSeed = 1;
+  int *aiUsed;
+  int i;
+
+  aiUsed = sqlite3_malloc(sizeof(int)*nCell);
+  if( !aiUsed ){
+    return SQLITE_NOMEM;
+  }
+  memset(aiUsed, 0, sizeof(int)*nCell);
+
+  PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
+
+  memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
+  memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
+  nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
+  nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
+  aiUsed[iLeftSeed] = 1;
+  aiUsed[iRightSeed] = 1;
+
+  for(i=nCell-2; i>0; i--){
+    RtreeCell *pNext;
+    pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
+    float diff =  
+      cellGrowth(pRtree, pBboxLeft, pNext) - 
+      cellGrowth(pRtree, pBboxRight, pNext)
+    ;
+    if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
+     || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
+    ){
+      nodeInsertCell(pRtree, pRight, pNext);
+      cellUnion(pRtree, pBboxRight, pNext);
+    }else{
+      nodeInsertCell(pRtree, pLeft, pNext);
+      cellUnion(pRtree, pBboxLeft, pNext);
+    }
+  }
+
+  sqlite3_free(aiUsed);
+  return SQLITE_OK;
+}
+#endif
+
+static int updateMapping(
+  Rtree *pRtree, 
+  i64 iRowid, 
+  RtreeNode *pNode, 
+  int iHeight
+){
+  int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
+  xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
+  if( iHeight>0 ){
+    RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
+    if( pChild ){
+      nodeRelease(pRtree, pChild->pParent);
+      nodeReference(pNode);
+      pChild->pParent = pNode;
+    }
+  }
+  return xSetMapping(pRtree, iRowid, pNode->iNode);
+}
+
+static int SplitNode(
+  Rtree *pRtree,
+  RtreeNode *pNode,
+  RtreeCell *pCell,
+  int iHeight
+){
+  int i;
+  int newCellIsRight = 0;
+
+  int rc = SQLITE_OK;
+  int nCell = NCELL(pNode);
+  RtreeCell *aCell;
+  int *aiUsed;
+
+  RtreeNode *pLeft = 0;
+  RtreeNode *pRight = 0;
+
+  RtreeCell leftbbox;
+  RtreeCell rightbbox;
+
+  /* Allocate an array and populate it with a copy of pCell and 
+  ** all cells from node pLeft. Then zero the original node.
+  */
+  aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
+  if( !aCell ){
+    rc = SQLITE_NOMEM;
+    goto splitnode_out;
+  }
+  aiUsed = (int *)&aCell[nCell+1];
+  memset(aiUsed, 0, sizeof(int)*(nCell+1));
+  for(i=0; i<nCell; i++){
+    nodeGetCell(pRtree, pNode, i, &aCell[i]);
+  }
+  nodeZero(pRtree, pNode);
+  memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
+  nCell++;
+
+  if( pNode->iNode==1 ){
+    pRight = nodeNew(pRtree, pNode);
+    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 = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
+  if( rc!=SQLITE_OK ){
+    goto splitnode_out;
+  }
+
+  /* Ensure both child nodes have node numbers assigned to them 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;
+  float *aDistance;
+  int nCell;
+  float aCenterCoord[RTREE_MAX_DIMENSIONS];
+  int iDim;
+  int ii;
+  int rc = SQLITE_OK;
+
+  memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
+
+  nCell = NCELL(pNode)+1;
+
+  /* Allocate the buffers used by this operation. The allocation is
+  ** relinquished before this function returns.
+  */
+  aCell = (RtreeCell *)sqlite3_malloc(nCell * (
+    sizeof(RtreeCell) +         /* aCell array */
+    sizeof(int)       +         /* aOrder array */
+    sizeof(int)       +         /* aSpare array */
+    sizeof(float)               /* aDistance array */
+  ));
+  if( !aCell ){
+    return SQLITE_NOMEM;
+  }
+  aOrder    = (int *)&aCell[nCell];
+  aSpare    = (int *)&aOrder[nCell];
+  aDistance = (float *)&aSpare[nCell];
+
+  for(ii=0; ii<nCell; ii++){
+    if( ii==(nCell-1) ){
+      memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
+    }else{
+      nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
+    }
+    aOrder[ii] = ii;
+    for(iDim=0; iDim<pRtree->nDim; iDim++){
+      aCenterCoord[iDim] += (float)DCOORD(aCell[ii].aCoord[iDim*2]);
+      aCenterCoord[iDim] += (float)DCOORD(aCell[ii].aCoord[iDim*2+1]);
+    }
+  }
+  for(iDim=0; iDim<pRtree->nDim; iDim++){
+    aCenterCoord[iDim] = (float)(aCenterCoord[iDim]/((float)nCell*2.0));
+  }
+
+  for(ii=0; ii<nCell; ii++){
+    aDistance[ii] = 0.0;
+    for(iDim=0; iDim<pRtree->nDim; iDim++){
+      float coord = (float)(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 VARIANT_RSTARTREE_REINSERT
+    if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
+      rc = SplitNode(pRtree, pNode, pCell, iHeight);
+    }else{
+      pRtree->iReinsertHeight = iHeight;
+      rc = Reinsert(pRtree, pNode, pCell, iHeight);
+    }
+#else
+    rc = SplitNode(pRtree, pNode, pCell, iHeight);
+#endif
+  }else{
+    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;               /* 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 initialise Rtree.iDepth */
+  rc = nodeAcquire(pRtree, 1, 0, &pRoot);
+
+  /* Obtain a reference to the leaf node that contains the entry 
+  ** about to be deleted. 
+  */
+  if( rc==SQLITE_OK ){
+    rc = findLeafNode(pRtree, iDelete, &pLeaf);
+  }
+
+  /* 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;
+}
+
+/*
+** 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);
+
+  /* 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]. */
+    assert( nData==(pRtree->nDim*2 + 3) );
+    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
+      for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+        cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
+        cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
+        if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
+          rc = SQLITE_CONSTRAINT;
+          goto constraint;
+        }
+      }
+    }else{
+      for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+        cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
+        cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
+        if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
+          rc = SQLITE_CONSTRAINT;
+          goto constraint;
+        }
+      }
+    }
+
+    /* 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;
+
+    /* 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;
+}
+
+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;
+
+  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 */
+){
+  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{
+    zSql = sqlite3_mprintf(
+        "SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1",
+        pRtree->zDb, pRtree->zName
+    );
+    rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize);
+  }
+
+  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 = strlen(argv[1]);
+  nName = 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);
+
+  /* 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{
+    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, a blob of data containing
+** an r-tree node, and the number of dimensions the r-tree indexes.
+** 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 = strlen(zCell);
+    for(jj=0; jj<tree.nDim*2; jj++){
+      sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
+      nCell = 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);
+}
+
+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 ){
+    void *c = (void *)RTREE_COORD_REAL32;
+    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;
+}
+
+/*
+** A version of sqlite3_free() that can be used as a callback. This is used
+** in two places - as the destructor for the blob value returned by the
+** invocation of a geometry function, and as the destructor for the geometry
+** functions themselves.
+*/
+static void doSqlite3Free(void *p){
+  sqlite3_free(p);
+}
+
+/*
+** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
+** scalar user function. This C function is the callback used for all such
+** registered SQL functions.
+**
+** The scalar user functions return a blob that is interpreted by r-tree
+** table MATCH operators.
+*/
+static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
+  RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
+  RtreeMatchArg *pBlob;
+  int nBlob;
+
+  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
+  pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
+  if( !pBlob ){
+    sqlite3_result_error_nomem(ctx);
+  }else{
+    int i;
+    pBlob->magic = RTREE_GEOMETRY_MAGIC;
+    pBlob->xGeom = pGeomCtx->xGeom;
+    pBlob->pContext = pGeomCtx->pContext;
+    pBlob->nParam = nArg;
+    for(i=0; i<nArg; i++){
+      pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
+    }
+    sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
+  }
+}
+
+/*
+** Register a new geometry function for use with the r-tree MATCH operator.
+*/
+int sqlite3_rtree_geometry_callback(
+  sqlite3 *db,
+  const char *zGeom,
+  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
+  void *pContext
+){
+  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->pContext = pContext;
+
+  /* Create the new user-function. Register a destructor function to delete
+  ** the context object when it is no longer required.  */
+  return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
+      (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
+  );
+}
+
+#if !SQLITE_CORE
+int sqlite3_extension_init(
+  sqlite3 *db,
+  char **pzErrMsg,
+  const sqlite3_api_routines *pApi
+){
+  SQLITE_EXTENSION_INIT2(pApi)
+  return sqlite3RtreeInit(db);
+}
+#endif
+
+#endif
diff --git a/ext/rtree/rtree.h b/ext/rtree/rtree.h
new file mode 100644
index 0000000..1fdbccc
--- /dev/null
+++ b/ext/rtree/rtree.h
@@ -0,0 +1,26 @@
+/*
+** 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/ext/rtree/rtree1.test b/ext/rtree/rtree1.test
new file mode 100644
index 0000000..583b028
--- /dev/null
+++ b/ext/rtree/rtree1.test
@@ -0,0 +1,500 @@
+# 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
+
+# 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.
+#
+
+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 }
+}
+
+# Test that it is possible to open an existing database that contains
+# r-tree tables.
+#
+do_test rtree-1.4.1 {
+  execsql {
+    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
+    INSERT INTO t1 VALUES(1, 5.0, 10.0);
+    INSERT INTO t1 VALUES(2, 15.0, 20.0);
+  }
+} {}
+do_test rtree-1.4.2 {
+  db close
+  sqlite3 db test.db
+  execsql { SELECT * FROM t1 ORDER BY ii }
+} {1 5.0 10.0 2 15.0 20.0}
+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 {
+    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.0 3.0}
+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 { SELECT * FROM t1 }
+} {1 1.0 3.0 2.0 4.0}
+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 { 
+    INSERT INTO t1 VALUES(5, 1, 3, 2, 4);
+    SELECT * FROM t1;
+  }
+} {5 1.0 3.0 2.0 4.0}
+do_test rtree-3.1.3 {
+  execsql {
+    INSERT INTO t1 VALUES(6, 2, 6, 4, 8);
+    SELECT * FROM t1;
+  }
+} {5 1.0 3.0 2.0 4.0 6 2.0 6.0 4.0 8.0}
+
+# 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 { 
+    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.0 20.0 2 30.0 40.0 3 50.0 60.0}
+do_test rtree-5.1.3 {
+  execsql { 
+    DELETE FROM t2 WHERE ii=2;
+    SELECT * FROM t2 ORDER BY ii;
+  }
+} {1 10.0 20.0 3 50.0 60.0}
+do_test rtree-5.1.4 {
+  execsql { 
+    DELETE FROM t2 WHERE ii=1;
+    SELECT * FROM t2 ORDER BY ii;
+  }
+} {3 50.0 60.0}
+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 {
+    INSERT INTO t3 VALUES(1, 2, 3, 4, 5);
+    UPDATE t3 SET x2=5;
+    SELECT * FROM t3;
+  }
+} {1 2.0 5.0 4.0 5.0}
+do_test rtree-6.1.3 {
+  execsql { UPDATE t3 SET ii = 2 }
+  execsql { SELECT * FROM t3 }
+} {2 2.0 5.0 4.0 5.0}
+
+#----------------------------------------------------------------------------
+# 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 { SELECT * FROM t5 }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.1.3 {
+  db close
+  sqlite3 db test.db
+  execsql { SELECT * FROM t5 }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.1.4 {
+  execsql { ALTER TABLE t5 RENAME TO 'raisara "one"'''}
+  execsql { SELECT * FROM "raisara ""one""'" }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.1.5 {
+  execsql { SELECT * FROM 'raisara "one"''' }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.1.6 {
+  execsql { ALTER TABLE "raisara ""one""'" RENAME TO "abc 123" }
+  execsql { SELECT * FROM "abc 123" }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.1.7 {
+  db close
+  sqlite3 db test.db
+  execsql { SELECT * FROM "abc 123" }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+
+# 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 { SELECT * FROM "abc 123" }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+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 { SELECT * FROM "abc 123" }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+do_test rtree-7.2.5 {
+  execsql { DROP TABLE t4_rowid }
+  execsql { ALTER TABLE "abc 123" RENAME TO t4 }
+  execsql { SELECT * FROM t4 }
+} {1 2.0 3.0 4.0 5.0 6.0 7.0}
+
+
+#----------------------------------------------------------------------------
+# 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 {
+  CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
+  INSERT INTO t1 VALUES(1,   1, 2, 3, 4);
+  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
+  }
+}
+finish_test
diff --git a/ext/rtree/rtree2.test b/ext/rtree/rtree2.test
new file mode 100644
index 0000000..f5d15cc
--- /dev/null
+++ b/ext/rtree/rtree2.test
@@ -0,0 +1,150 @@
+# 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/ext/rtree/rtree3.test b/ext/rtree/rtree3.test
new file mode 100644
index 0000000..fea5513
--- /dev/null
+++ b/ext/rtree/rtree3.test
@@ -0,0 +1,237 @@
+# 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/ext/rtree/rtree4.test b/ext/rtree/rtree4.test
new file mode 100644
index 0000000..708d335
--- /dev/null
+++ b/ext/rtree/rtree4.test
@@ -0,0 +1,234 @@
+# 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
+}
+
+# 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}
+  }
+}
+
+# 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/ext/rtree/rtree5.test b/ext/rtree/rtree5.test
new file mode 100644
index 0000000..ea2946f
--- /dev/null
+++ b/ext/rtree/rtree5.test
@@ -0,0 +1,78 @@
+# 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}
+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.10 { 
+  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/ext/rtree/rtree6.test b/ext/rtree/rtree6.test
new file mode 100644
index 0000000..ba0e53c
--- /dev/null
+++ b/ext/rtree/rtree6.test
@@ -0,0 +1,156 @@
+# 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 {
+  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}
+} {Ea}
+
+do_test rtree6-1.3 {
+  rtree_strategy {SELECT * FROM t1 WHERE x1<10}
+} {Ca}
+
+do_test rtree6-1.4 {
+  rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
+} {Ca}
+
+do_test rtree6-1.5 {
+  rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
+} {Ca}
+
+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:Ca (~0 rows)} 
+  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
+}
+
+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:Ca (~0 rows)} 
+  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
+}
+
+do_eqp_test rtree6.2.3 {
+  SELECT * FROM t1,t2 WHERE k=ii
+} {
+  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2: (~0 rows)} 
+  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
+}
+
+do_eqp_test rtree6.2.4 {
+  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
+} {
+  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:CaEb (~0 rows)} 
+  0 1 1 {SCAN TABLE t2 (~100000 rows)}
+}
+
+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 rows)} 
+  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?) (~1 rows)}
+}
+
+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 
+  }
+} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}
+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
+  }
+} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}
+
+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/ext/rtree/rtree7.test b/ext/rtree/rtree7.test
new file mode 100644
index 0000000..31dae0c
--- /dev/null
+++ b/ext/rtree/rtree7.test
@@ -0,0 +1,58 @@
+# 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
+}
+
+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 { SELECT * FROM rt }
+} {1 1.0 2.0 3.0 4.0}
+do_test rtree7-1.3 {
+  execsql { 
+    PRAGMA page_size = 2048;
+    VACUUM;
+    SELECT * FROM rt;
+  }
+} {1 1.0 2.0 3.0 4.0}
+do_test rtree7-1.4 {
+  for {set i 2} {$i <= 51} {incr i} {
+    execsql { INSERT INTO rt VALUES($i, 1, 2, 3, 4) }
+  }
+  execsql { SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt }
+} {51.0 102.0 153.0 204.0}
+do_test rtree7-1.5 {
+  execsql { 
+    PRAGMA page_size = 512;
+    VACUUM;
+    SELECT sum(x1), sum(x2), sum(y1), sum(y2) FROM rt
+  }
+} {51.0 102.0 153.0 204.0}
+
+finish_test
diff --git a/ext/rtree/rtree8.test b/ext/rtree/rtree8.test
new file mode 100644
index 0000000..bf22cbf
--- /dev/null
+++ b/ext/rtree/rtree8.test
@@ -0,0 +1,171 @@
+# 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/ext/rtree/rtree9.test b/ext/rtree/rtree9.test
new file mode 100644
index 0000000..ddee277
--- /dev/null
+++ b/ext/rtree/rtree9.test
@@ -0,0 +1,125 @@
+# 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 }
+
+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
+
+breakpoint
+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/ext/rtree/rtreeA.test b/ext/rtree/rtreeA.test
new file mode 100644
index 0000000..e377b01
--- /dev/null
+++ b/ext/rtree/rtreeA.test
@@ -0,0 +1,220 @@
+# 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/ext/rtree/rtreeB.test b/ext/rtree/rtreeB.test
new file mode 100644
index 0000000..2756fce
--- /dev/null
+++ b/ext/rtree/rtreeB.test
@@ -0,0 +1,34 @@
+# 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 }
+
+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.000000 0.000000 100.000000 100.000000} {2147483646 0.000000 0.000000 200.000000 200.000000} {4294967296 0.000000 0.000000 300.000000 300.000000} {8589934592 20.000000 20.000000 150.000000 150.000000} {9223372036854775807 150.000000 150.000000 400.000000 400.000000}}}
+
+
+finish_test
diff --git a/ext/rtree/rtree_perf.tcl b/ext/rtree/rtree_perf.tcl
new file mode 100644
index 0000000..e42e685
--- /dev/null
+++ b/ext/rtree/rtree_perf.tcl
@@ -0,0 +1,74 @@
+
+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/ext/rtree/rtree_util.tcl b/ext/rtree/rtree_util.tcl
new file mode 100644
index 0000000..50a1b58
--- /dev/null
+++ b/ext/rtree/rtree_util.tcl
@@ -0,0 +1,192 @@
+# 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/ext/rtree/sqlite3rtree.h b/ext/rtree/sqlite3rtree.h
new file mode 100644
index 0000000..cffb300
--- /dev/null
+++ b/ext/rtree/sqlite3rtree.h
@@ -0,0 +1,56 @@
+/*
+** 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;
+
+/*
+** 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 nCoord, double *aCoord, int *pRes),
+  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[] */
+  double *aParam;                 /* Parameters passed to SQL geom function */
+  void *pUser;                    /* Callback implementation user data */
+  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
+};
+
+
+#ifdef __cplusplus
+}  /* end of the 'extern "C"' block */
+#endif
+
+#endif  /* ifndef _SQLITE3RTREE_H_ */
diff --git a/ext/rtree/tkt3363.test b/ext/rtree/tkt3363.test
new file mode 100644
index 0000000..db05ed5
--- /dev/null
+++ b/ext/rtree/tkt3363.test
@@ -0,0 +1,50 @@
+# 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/ext/rtree/viewrtree.tcl b/ext/rtree/viewrtree.tcl
new file mode 100644
index 0000000..794677f
--- /dev/null
+++ b/ext/rtree/viewrtree.tcl
@@ -0,0 +1,188 @@
+
+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