Import 'rtree' extension. (CVS 5159)
FossilOrigin-Name: b104dcd6adadbd3fe15a348fe9d4d290119e139e
diff --git a/ext/rtree/README b/ext/rtree/README
new file mode 100644
index 0000000..f2bb907
--- /dev/null
+++ b/ext/rtree/README
@@ -0,0 +1,123 @@
+
+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 greater than 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);
+ CREATE VIRTUAL TABLE boxes USING rtree(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 faster
+ 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 ICU 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, libSqliteIcu.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..1d26859
--- /dev/null
+++ b/ext/rtree/rtree.c
@@ -0,0 +1,2753 @@
+/*
+** 2001 September 15
+**
+** The author disclaims copyright to this source code. In place of
+** a legal notice, here is a blessing:
+**
+** May you do good and not evil.
+** May you find forgiveness for yourself and forgive others.
+** May you share freely, never taking more than you give.
+**
+*************************************************************************
+** This file contains code for implementations of the r-tree and r*-tree
+** algorithms packaged as an SQLite virtual table module.
+**
+** $Id: rtree.c,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+*/
+
+#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
+
+/*
+** This file contains an implementation of a couple of different variants
+** of the r-tree algorithm. See the README file for further details. The
+** same data-structure is used for all, but the algorithms for insert and
+** delete operations vary. The variants used are selected at compile time
+** by defining the following symbols:
+*/
+
+/* Either, both or none of the following may be set to activate
+** r*tree variant algorithms.
+*/
+#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
+#define VARIANT_RSTARTREE_REINSERT 1
+
+/*
+** Exactly one of the following must be set to 1.
+*/
+#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
+#define VARIANT_GUTTMAN_LINEAR_SPLIT 0
+#define VARIANT_RSTARTREE_SPLIT 1
+
+#define VARIANT_GUTTMAN_SPLIT \
+ (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
+
+#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
+ #define PickNext QuadraticPickNext
+ #define PickSeeds QuadraticPickSeeds
+ #define AssignCells splitNodeGuttman
+#endif
+#if VARIANT_GUTTMAN_LINEAR_SPLIT
+ #define PickNext LinearPickNext
+ #define PickSeeds LinearPickSeeds
+ #define AssignCells splitNodeGuttman
+#endif
+#if VARIANT_RSTARTREE_SPLIT
+ #define AssignCells splitNodeStartree
+#endif
+
+
+#ifndef SQLITE_CORE
+ #include "sqlite3ext.h"
+ SQLITE_EXTENSION_INIT1
+#else
+ #include "sqlite3.h"
+#endif
+
+#include <string.h>
+#include <assert.h>
+
+typedef sqlite3_int64 i64;
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+typedef struct Rtree Rtree;
+typedef struct RtreeCursor RtreeCursor;
+typedef struct RtreeNode RtreeNode;
+typedef struct RtreeCell RtreeCell;
+typedef struct RtreeConstraint RtreeConstraint;
+
+/* 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;
+};
+
+/*
+** The minimum number of cells allowed for a node is a third of the
+** maximum. In Gutman's notation:
+**
+** m = M/3
+**
+** If an R*-tree "Reinsert" operation is required, the same number of
+** cells are removed from the overfull node and reinserted into the tree.
+*/
+#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
+#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
+#define RTREE_MAXCELLS 51
+
+/*
+** An rtree cursor object.
+*/
+struct RtreeCursor {
+ sqlite3_vtab_cursor base;
+ RtreeNode *pNode; /* Node cursor is currently pointing at */
+ int iCell; /* Index of current cell in pNode */
+ int iStrategy; /* Copy of idxNum search parameter */
+ int nConstraint; /* Number of entries in aConstraint */
+ RtreeConstraint *aConstraint; /* Search constraints. */
+};
+
+/*
+** A search constraint.
+*/
+struct RtreeConstraint {
+ int iCoord; /* Index of constrained coordinate */
+ int op; /* Constraining operation */
+ float rValue; /* Constraint value. */
+};
+
+/* Possible values for RtreeConstraint.op */
+#define RTREE_EQ 0x41
+#define RTREE_LE 0x42
+#define RTREE_LT 0x43
+#define RTREE_GE 0x44
+#define RTREE_GT 0x45
+
+/*
+** An rtree structure node.
+**
+** Data format (RtreeNode.zData):
+**
+** 1. If the node is the root node (node 1), then the first 2 bytes
+** of the node contain the tree depth as a big-endian integer.
+** For non-root nodes, the first 2 bytes are left unused.
+**
+** 2. The next 2 bytes contain the number of entries currently
+** stored in the node.
+**
+** 3. The remainder of the node contains the node entries. Each entry
+** consists of a single 8-byte integer followed by an even number
+** of 4-byte coordinates. For leaf nodes the integer is the rowid
+** of a record. For internal nodes it is the node number of a
+** child page.
+*/
+struct RtreeNode {
+ RtreeNode *pParent; /* Parent node */
+ i64 iNode;
+ int nRef;
+ int isDirty;
+ u8 *zData;
+ RtreeNode *pNext; /* Next node in this hash chain */
+};
+#define NCELL(pNode) readInt16(&(pNode)->zData[2])
+
+/*
+** Structure to store a deserialized rtree record.
+*/
+struct RtreeCell {
+ i64 iRowid;
+ float aCoord[RTREE_MAX_DIMENSIONS*2];
+};
+
+#define MAX(x,y) ((x) < (y) ? (y) : (x))
+#define MIN(x,y) ((x) > (y) ? (y) : (x))
+
+/*
+** Functions to deserialize a 16 bit integer, 32 bit real number and
+** 64 bit integer. The deserialized value is returned.
+*/
+static int readInt16(u8 *p){
+ return (p[0]<<8) + p[1];
+}
+static float readReal32(u8 *p){
+ u32 i = (
+ (((u32)p[0]) << 24) +
+ (((u32)p[1]) << 16) +
+ (((u32)p[2]) << 8) +
+ (((u32)p[3]) << 0)
+ );
+ return *(float *)&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 writeReal32(u8 *p, float f){
+ u32 i;
+ assert( sizeof(float)==4 );
+ assert( sizeof(u32)==4 );
+ i = *(u32 *)&f;
+ p[0] = (i>>24)&0xFF;
+ p[1] = (i>>16)&0xFF;
+ p[2] = (i>> 8)&0xFF;
+ p[3] = (i>> 0)&0xFF;
+ return 4;
+}
+static int writeInt64(u8 *p, i64 i){
+ p[0] = (i>>56)&0xFF;
+ p[1] = (i>>48)&0xFF;
+ p[2] = (i>>40)&0xFF;
+ p[3] = (i>>32)&0xFF;
+ p[4] = (i>>24)&0xFF;
+ p[5] = (i>>16)&0xFF;
+ p[6] = (i>> 8)&0xFF;
+ p[7] = (i>> 0)&0xFF;
+ return 8;
+}
+
+/*
+** Increment the reference count of node p.
+*/
+static void nodeReference(RtreeNode *p){
+ if( p ){
+ p->nRef++;
+ }
+}
+
+/*
+** Clear the content of node p (set all bytes to 0x00).
+*/
+static void nodeZero(Rtree *pRtree, RtreeNode *p){
+ if( p ){
+ memset(&p->zData[2], 0, pRtree->iNodeSize-2);
+ p->isDirty = 1;
+ }
+}
+
+/*
+** Given a node number iNode, return the corresponding key to use
+** in the Rtree.aHash table.
+*/
+static int nodeHash(i64 iNode){
+ return (
+ (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^
+ (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
+ ) % HASHSIZE;
+}
+
+/*
+** Search the node hash table for node iNode. If found, return a pointer
+** to it. Otherwise, return 0.
+*/
+static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
+ RtreeNode *p;
+ assert( iNode!=0 );
+ for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
+ return p;
+}
+
+/*
+** Add node pNode to the node hash table.
+*/
+static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
+ if( pNode ){
+ int iHash;
+ assert( pNode->pNext==0 );
+ iHash = nodeHash(pNode->iNode);
+ pNode->pNext = pRtree->aHash[iHash];
+ pRtree->aHash[iHash] = pNode;
+ }
+}
+
+/*
+** Remove node pNode from the node hash table.
+*/
+static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
+ RtreeNode **pp;
+ if( pNode->iNode!=0 ){
+ pp = &pRtree->aHash[nodeHash(pNode->iNode)];
+ for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
+ *pp = pNode->pNext;
+ pNode->pNext = 0;
+ }
+}
+
+/*
+** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
+** indicating that node has not yet been assigned a node number. It is
+** assigned a node number when nodeWrite() is called to write the
+** node contents out to the database.
+*/
+static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){
+ RtreeNode *pNode;
+ pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
+ if( pNode ){
+ memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
+ pNode->zData = (u8 *)&pNode[1];
+ pNode->nRef = 1;
+ pNode->pParent = pParent;
+ pNode->isDirty = 1;
+ nodeReference(pParent);
+ }
+ return pNode;
+}
+
+/*
+** Obtain a reference to an r-tree node.
+*/
+static int
+nodeAcquire(
+ Rtree *pRtree, /* R-tree structure */
+ i64 iNode, /* Node number to load */
+ RtreeNode *pParent, /* Either the parent node or NULL */
+ RtreeNode **ppNode /* OUT: Acquired node */
+){
+ int rc;
+ RtreeNode *pNode;
+
+ /* Check if the requested node is already in the hash table. If so,
+ ** increase its reference count and return it.
+ */
+ if( (pNode = nodeHashLookup(pRtree, iNode)) ){
+ assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
+ if( pParent ){
+ pNode->pParent = pParent;
+ }
+ pNode->nRef++;
+ *ppNode = pNode;
+ return SQLITE_OK;
+ }
+
+ pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
+ if( !pNode ){
+ *ppNode = 0;
+ return SQLITE_NOMEM;
+ }
+ pNode->pParent = pParent;
+ pNode->zData = (u8 *)&pNode[1];
+ pNode->nRef = 1;
+ pNode->iNode = iNode;
+ pNode->isDirty = 0;
+ pNode->pNext = 0;
+
+ sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
+ rc = sqlite3_step(pRtree->pReadNode);
+ if( rc==SQLITE_ROW ){
+ const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
+ memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
+ nodeReference(pParent);
+ }else{
+ sqlite3_free(pNode);
+ pNode = 0;
+ }
+
+ *ppNode = pNode;
+ rc = sqlite3_reset(pRtree->pReadNode);
+
+ if( rc==SQLITE_OK && iNode==1 ){
+ pRtree->iDepth = readInt16(pNode->zData);
+ }
+
+ assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );
+ nodeHashInsert(pRtree, pNode);
+
+ return rc;
+}
+
+/*
+** Overwrite cell iCell of node pNode with the contents of pCell.
+*/
+static void nodeOverwriteCell(
+ Rtree *pRtree,
+ RtreeNode *pNode,
+ RtreeCell *pCell,
+ int iCell
+){
+ int ii;
+ u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
+ p += writeInt64(p, pCell->iRowid);
+ for(ii=0; ii<(pRtree->nDim*2); ii++){
+ p += writeReal32(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 float nodeGetCoord(
+ Rtree *pRtree,
+ RtreeNode *pNode,
+ int iCell,
+ int iCoord
+){
+ return readReal32(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord]);
+}
+
+/*
+** 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++){
+ pCell->aCoord[ii] = nodeGetCoord(pRtree, pNode, iCell, 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;
+}
+
+/*
+** Rtree virtual table module xClose method.
+*/
+static int rtreeClose(sqlite3_vtab_cursor *cur){
+ Rtree *pRtree = (Rtree *)(cur->pVtab);
+ int rc;
+ RtreeCursor *pCsr = (RtreeCursor *)cur;
+ sqlite3_free(pCsr->aConstraint);
+ rc = nodeRelease(pRtree, pCsr->pNode);
+ sqlite3_free(pCsr);
+ return rc;
+}
+
+/*
+** Rtree virtual table module xEof method.
+**
+** Return non-zero if the cursor does not currently point to a valid
+** record (i.e if the scan has finished), or zero otherwise.
+*/
+static int rtreeEof(sqlite3_vtab_cursor *cur){
+ RtreeCursor *pCsr = (RtreeCursor *)cur;
+ return (pCsr->pNode==0);
+}
+
+/*
+** Cursor pCursor currently points to a cell in a non-leaf page.
+** Return true if the sub-tree headed by the cell is filtered
+** (excluded) by the constraints in the pCursor->aConstraint[]
+** array, or false otherwise.
+*/
+static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){
+ RtreeCell cell;
+ int ii;
+
+ nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
+ for(ii=0; ii<pCursor->nConstraint; ii++){
+ RtreeConstraint *p = &pCursor->aConstraint[ii];
+
+ float cell_min = cell.aCoord[(p->iCoord>>1)*2];
+ float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
+ assert( cell_min<=cell_max );
+
+ switch( p->op ){
+ case RTREE_LE: case RTREE_LT: {
+ if( p->rValue<cell_min ){
+ return 1;
+ }
+ break;
+ }
+
+ case RTREE_GE: case RTREE_GT: {
+ if( p->rValue>cell_max ){
+ return 1;
+ }
+ break;
+ }
+
+ case RTREE_EQ: {
+ if( p->rValue>cell_max || p->rValue<cell_min ){
+ return 1;
+ }
+ break;
+ }
+#ifndef NDEBUG
+ default: assert(!"Internal error");
+#endif
+ }
+ }
+
+ return 0;
+}
+
+/*
+** Return true if the cell that cursor pCursor currently points to
+** would be filtered (excluded) by the constraints in the
+** pCursor->aConstraint[] array, or false otherwise.
+**
+** This function assumes that the cell is part of a leaf node.
+*/
+static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){
+ RtreeCell cell;
+ int ii;
+
+ nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
+ for(ii=0; ii<pCursor->nConstraint; ii++){
+ RtreeConstraint *p = &pCursor->aConstraint[ii];
+ float cell_val = cell.aCoord[p->iCoord];
+ int res;
+ switch( p->op ){
+ case RTREE_LE: res = (cell_val<=p->rValue); break;
+ case RTREE_LT: res = (cell_val<p->rValue); break;
+ case RTREE_GE: res = (cell_val>=p->rValue); break;
+ case RTREE_GT: res = (cell_val>p->rValue); break;
+ case RTREE_EQ: res = (cell_val==p->rValue); break;
+#ifndef NDEBUG
+ default: assert(!"Internal error");
+#endif
+ }
+ if( !res ) return 1;
+ }
+
+ return 0;
+}
+
+/*
+** Cursor pCursor currently points at a node that heads a sub-tree of
+** height iHeight (if iHeight==0, then the node is a leaf). Descend
+** to point to the left-most cell of the sub-tree that matches the
+** configured constraints.
+*/
+static int descendToCell(
+ Rtree *pRtree,
+ RtreeCursor *pCursor,
+ int iHeight,
+ int *pEof /* OUT: Set to true if cannot descend */
+){
+ int isEof;
+ int rc;
+ int ii;
+ RtreeNode *pChild;
+ sqlite3_int64 iRowid;
+
+ RtreeNode *pSavedNode = pCursor->pNode;
+ int iSavedCell = pCursor->iCell;
+
+ assert( iHeight>=0 );
+
+ if( iHeight==0 ){
+ isEof = testRtreeEntry(pRtree, pCursor);
+ }else{
+ isEof = testRtreeCell(pRtree, pCursor);
+ }
+ if( isEof || iHeight==0 ){
+ *pEof = isEof;
+ return SQLITE_OK;
+ }
+
+ iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
+ rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
+ if( rc!=SQLITE_OK ){
+ return rc;
+ }
+
+ nodeRelease(pRtree, pCursor->pNode);
+ pCursor->pNode = pChild;
+ isEof = 1;
+ for(ii=0; isEof && ii<NCELL(pChild); ii++){
+ pCursor->iCell = ii;
+ rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
+ if( rc!=SQLITE_OK ){
+ return rc;
+ }
+ }
+
+ if( isEof ){
+ assert( pCursor->pNode==pChild );
+ nodeReference(pSavedNode);
+ nodeRelease(pRtree, pChild);
+ pCursor->pNode = pSavedNode;
+ pCursor->iCell = iSavedCell;
+ }
+
+ *pEof = isEof;
+ return SQLITE_OK;
+}
+
+/*
+** One of the cells in node pNode is guaranteed to have a 64-bit
+** integer value equal to iRowid. Return the index of this cell.
+*/
+static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){
+ int ii;
+ for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
+ assert( ii<(NCELL(pNode)-1) );
+ }
+ return ii;
+}
+
+/*
+** Return the index of the cell containing a pointer to node pNode
+** in its parent. If pNode is the root node, return -1.
+*/
+static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){
+ RtreeNode *pParent = pNode->pParent;
+ if( pParent ){
+ return nodeRowidIndex(pRtree, pParent, pNode->iNode);
+ }
+ return -1;
+}
+
+/*
+** Rtree virtual table module xNext method.
+*/
+static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
+ Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
+ RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+ int rc = SQLITE_OK;
+
+ if( pCsr->iStrategy==1 ){
+ /* This "scan" is a direct lookup by rowid. There is no next entry. */
+ nodeRelease(pRtree, pCsr->pNode);
+ pCsr->pNode = 0;
+ }
+
+ else if( pCsr->pNode ){
+ /* Move to the next entry that matches the configured constraints. */
+ int iHeight = 0;
+ while( pCsr->pNode ){
+ RtreeNode *pNode = pCsr->pNode;
+ int nCell = NCELL(pNode);
+ for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
+ int isEof;
+ rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
+ if( rc!=SQLITE_OK || !isEof ){
+ return rc;
+ }
+ }
+ pCsr->pNode = pNode->pParent;
+ pCsr->iCell = nodeParentIndex(pRtree, pNode);
+ nodeReference(pCsr->pNode);
+ nodeRelease(pRtree, pNode);
+ iHeight++;
+ }
+ }
+
+ return rc;
+}
+
+/*
+** Rtree virtual table module xRowid method.
+*/
+static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
+ Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
+ RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+
+ assert(pCsr->pNode);
+ *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
+
+ return SQLITE_OK;
+}
+
+/*
+** Rtree virtual table module xColumn method.
+*/
+static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
+ Rtree *pRtree = (Rtree *)cur->pVtab;
+ RtreeCursor *pCsr = (RtreeCursor *)cur;
+
+ if( i==0 ){
+ i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
+ sqlite3_result_int64(ctx, iRowid);
+ }else{
+ float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1);
+ sqlite3_result_double(ctx, fCoord);
+ }
+
+ return SQLITE_OK;
+}
+
+/*
+** Use nodeAcquire() to obtain the leaf node containing the record with
+** rowid iRowid. If successful, set *ppLeaf to point to the node and
+** return SQLITE_OK. If there is no such record in the table, set
+** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
+** to zero and return an SQLite error code.
+*/
+static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
+ int rc;
+ *ppLeaf = 0;
+ sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
+ if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
+ i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
+ rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
+ sqlite3_reset(pRtree->pReadRowid);
+ }else{
+ rc = sqlite3_reset(pRtree->pReadRowid);
+ }
+ return rc;
+}
+
+
+/*
+** Rtree virtual table module xFilter method.
+*/
+static int rtreeFilter(
+ sqlite3_vtab_cursor *pVtabCursor,
+ int idxNum, const char *idxStr,
+ int argc, sqlite3_value **argv
+){
+ Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
+ RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+
+ RtreeNode *pRoot = 0;
+ int ii;
+ int rc = SQLITE_OK;
+
+ rtreeReference(pRtree);
+
+ sqlite3_free(pCsr->aConstraint);
+ pCsr->aConstraint = 0;
+ pCsr->iStrategy = idxNum;
+
+ if( idxNum==1 ){
+ /* Special case - lookup by rowid. */
+ RtreeNode *pLeaf; /* Leaf on which the required cell resides */
+ i64 iRowid = sqlite3_value_int64(argv[0]);
+ rc = findLeafNode(pRtree, iRowid, &pLeaf);
+ pCsr->pNode = pLeaf;
+ if( pLeaf && rc==SQLITE_OK ){
+ pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
+ }
+ }else{
+ /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
+ ** with the configured constraints.
+ */
+ if( argc>0 ){
+ pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
+ pCsr->nConstraint = argc;
+ if( !pCsr->aConstraint ){
+ rc = SQLITE_NOMEM;
+ }else{
+ assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
+ for(ii=0; ii<argc; ii++){
+ RtreeConstraint *p = &pCsr->aConstraint[ii];
+ p->op = idxStr[ii*2];
+ p->iCoord = idxStr[ii*2+1]-'a';
+ p->rValue = sqlite3_value_double(argv[ii]);
+ }
+ }
+ }
+
+ if( rc==SQLITE_OK ){
+ pCsr->pNode = 0;
+ rc = nodeAcquire(pRtree, 1, 0, &pRoot);
+ }
+ if( rc==SQLITE_OK ){
+ int isEof = 1;
+ int nCell = NCELL(pRoot);
+ pCsr->pNode = pRoot;
+ for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
+ assert( pCsr->pNode==pRoot );
+ rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
+ if( !isEof ){
+ break;
+ }
+ }
+ if( rc==SQLITE_OK && isEof ){
+ assert( pCsr->pNode==pRoot );
+ nodeRelease(pRtree, pRoot);
+ pCsr->pNode = 0;
+ }
+ assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
+ }
+ }
+
+ rtreeRelease(pRtree);
+ return rc;
+}
+
+/*
+** Rtree virtual table module xBestIndex method. There are three
+** table scan strategies to choose from (in order from most to
+** least desirable):
+**
+** idxNum idxStr Strategy
+** ------------------------------------------------
+** 1 Unused Direct lookup by rowid.
+** 2 See below R-tree query.
+** 3 Unused Full table scan.
+** ------------------------------------------------
+**
+** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
+** 2 is used, idxStr is formatted to contain 2 bytes for each
+** constraint used. The first two bytes of idxStr correspond to
+** the constraint in sqlite3_index_info.aConstraintUsage[] with
+** (argvIndex==1) etc.
+**
+** The first of each pair of bytes in idxStr identifies the constraint
+** operator as follows:
+**
+** Operator Byte Value
+** ----------------------
+** = 0x41 ('A')
+** <= 0x42 ('B')
+** < 0x43 ('C')
+** >= 0x44 ('D')
+** > 0x45 ('E')
+** ----------------------
+**
+** The second of each pair of bytes identifies the coordinate column
+** to which the constraint applies. The leftmost coordinate column
+** is 'a', the second from the left 'b' etc.
+*/
+static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
+ int rc = SQLITE_OK;
+ int ii;
+
+ int iIdx = 0;
+ char zIdxStr[RTREE_MAX_DIMENSIONS*2+1];
+ memset(zIdxStr, 0, RTREE_MAX_DIMENSIONS*2+1);
+
+ assert( pIdxInfo->idxStr==0 );
+ for(ii=0; ii<pIdxInfo->nConstraint; ii++){
+ struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
+
+ if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
+ /* We have an equality constraint on the rowid. Use strategy 1. */
+ int jj;
+ for(jj=0; jj<ii; jj++){
+ pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
+ pIdxInfo->aConstraintUsage[jj].omit = 0;
+ }
+ pIdxInfo->idxNum = 1;
+ pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
+ pIdxInfo->aConstraintUsage[jj].omit = 1;
+ return SQLITE_OK;
+ }
+
+ if( p->usable && p->iColumn>0 ){
+ u8 op = 0;
+ switch( p->op ){
+ case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
+ case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
+ case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
+ case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
+ case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
+ }
+ if( op ){
+ zIdxStr[iIdx++] = op;
+ zIdxStr[iIdx++] = (char)(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;
+ }
+ return rc;
+}
+
+/*
+** Return the N-dimensional volumn of the cell stored in *p.
+*/
+static float cellArea(Rtree *pRtree, RtreeCell *p){
+ float area = 1.0;
+ int ii;
+ for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+ area = area * (p->aCoord[ii+1] - 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 += (p->aCoord[ii+1] - 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;
+ for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+ p1->aCoord[ii] = MIN(p1->aCoord[ii], p2->aCoord[ii]);
+ p1->aCoord[ii+1] = MAX(p1->aCoord[ii+1], p2->aCoord[ii+1]);
+ }
+}
+
+/*
+** Return the amount cell p would grow by if it were unioned with pCell.
+*/
+static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
+ float area;
+ RtreeCell cell;
+ memcpy(&cell, p, sizeof(RtreeCell));
+ area = cellArea(pRtree, &cell);
+ cellUnion(pRtree, &cell, pCell);
+ return (cellArea(pRtree, &cell)-area);
+}
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
+static float cellOverlap(
+ Rtree *pRtree,
+ RtreeCell *p,
+ RtreeCell *aCell,
+ int nCell,
+ int iExclude
+){
+ int ii;
+ float overlap = 0.0;
+ for(ii=0; ii<nCell; ii++){
+ if( ii!=iExclude ){
+ int jj;
+ float o = 1.0;
+ for(jj=0; jj<(pRtree->nDim*2); jj+=2){
+
+ float x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]);
+ float x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord[jj+1]);
+
+ if( x2<x1 ){
+ o = 0.0;
+ break;
+ }else{
+ o = o * (x2-x1);
+ }
+ }
+ overlap += o;
+ }
+ }
+ return overlap;
+}
+#endif
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+static float cellOverlapEnlargement(
+ Rtree *pRtree,
+ RtreeCell *p,
+ RtreeCell *pInsert,
+ RtreeCell *aCell,
+ int nCell,
+ int iExclude
+){
+ float before;
+ float after;
+ before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
+ cellUnion(pRtree, p, pInsert);
+ after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
+ return after-before;
+}
+#endif
+
+
+/*
+** This function implements the ChooseLeaf algorithm from Gutman[84].
+** ChooseSubTree in r*tree terminology.
+*/
+static int ChooseLeaf(
+ Rtree *pRtree, /* Rtree table */
+ RtreeCell *pCell, /* Cell to insert into rtree */
+ int iHeight, /* Height of sub-tree rooted at pCell */
+ RtreeNode **ppLeaf /* OUT: Selected leaf page */
+){
+ int rc;
+ int ii;
+ RtreeNode *pNode;
+ rc = nodeAcquire(pRtree, 1, 0, &pNode);
+
+ for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
+ int iCell;
+ sqlite3_int64 iBest;
+
+ float fMinGrowth;
+ float fMinArea;
+ float fMinOverlap;
+
+ int nCell = NCELL(pNode);
+ RtreeCell cell;
+ RtreeNode *pChild;
+
+ RtreeCell *aCell = 0;
+
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+ if( ii==(pRtree->iDepth-1) ){
+ int jj;
+ aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
+ if( !aCell ){
+ rc = SQLITE_NOMEM;
+ nodeRelease(pRtree, pNode);
+ pNode = 0;
+ continue;
+ }
+ for(jj=0; jj<nCell; jj++){
+ nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
+ }
+ }
+#endif
+
+ /* Select the child node which will be enlarged the least if pCell
+ ** is inserted into it. Resolve ties by choosing the entry with
+ ** the smallest area.
+ */
+ for(iCell=0; iCell<nCell; iCell++){
+ float growth;
+ float area;
+ float overlap = 0.0;
+ nodeGetCell(pRtree, pNode, iCell, &cell);
+ growth = cellGrowth(pRtree, &cell, pCell);
+ area = cellArea(pRtree, &cell);
+#if VARIANT_RSTARTREE_CHOOSESUBTREE
+ if( ii==(pRtree->iDepth-1) ){
+ overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
+ }
+#endif
+ if( (iCell==0)
+ || (overlap<fMinOverlap)
+ || (overlap==fMinOverlap && growth<fMinGrowth)
+ || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
+ ){
+ fMinOverlap = overlap;
+ fMinGrowth = growth;
+ fMinArea = area;
+ iBest = cell.iRowid;
+ }
+ }
+
+ sqlite3_free(aCell);
+ rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
+ nodeRelease(pRtree, pNode);
+ pNode = pChild;
+ }
+
+ *ppLeaf = pNode;
+ return rc;
+}
+
+/*
+** A cell with the same content as pCell has just been inserted into
+** the node pNode. This function updates the bounding box cells in
+** all ancestor elements.
+*/
+static void AdjustTree(
+ Rtree *pRtree, /* Rtree table */
+ RtreeNode *pNode, /* Adjust ancestry of this node. */
+ RtreeCell *pCell /* This cell was just inserted */
+){
+ RtreeNode *p = pNode;
+ while( p->pParent ){
+ RtreeCell cell;
+ RtreeNode *pParent = p->pParent;
+ int iCell = nodeParentIndex(pRtree, p);
+
+ nodeGetCell(pRtree, pParent, iCell, &cell);
+ if( cellGrowth(pRtree, &cell, pCell)>0.0 ){
+ cellUnion(pRtree, &cell, pCell);
+ nodeOverwriteCell(pRtree, pParent, &cell, iCell);
+ }
+
+ p = pParent;
+ }
+}
+
+/*
+** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
+*/
+static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
+ sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
+ sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
+ sqlite3_step(pRtree->pWriteRowid);
+ return sqlite3_reset(pRtree->pWriteRowid);
+}
+
+/*
+** Write mapping (iNode->iPar) to the <rtree>_parent table.
+*/
+static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
+ sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
+ sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
+ sqlite3_step(pRtree->pWriteParent);
+ return sqlite3_reset(pRtree->pWriteParent);
+}
+
+static int insertCell(Rtree *, RtreeNode *, RtreeCell *, int);
+
+#if VARIANT_GUTTMAN_LINEAR_SPLIT
+/*
+** Implementation of the linear variant of the PickNext() function from
+** Guttman[84].
+*/
+static RtreeCell *LinearPickNext(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ RtreeCell *pLeftBox,
+ RtreeCell *pRightBox,
+ int *aiUsed
+){
+ int ii;
+ for(ii=0; aiUsed[ii]; ii++);
+ aiUsed[ii] = 1;
+ return &aCell[ii];
+}
+
+/*
+** Implementation of the linear variant of the PickSeeds() function from
+** Guttman[84].
+*/
+static void LinearPickSeeds(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ int *piLeftSeed,
+ int *piRightSeed
+){
+ int i;
+ int iLeftSeed = 0;
+ int iRightSeed = 1;
+ float maxNormalInnerWidth = 0.0;
+
+ /* Pick two "seed" cells from the array of cells. The algorithm used
+ ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
+ ** indices of the two seed cells in the array are stored in local
+ ** variables iLeftSeek and iRightSeed.
+ */
+ for(i=0; i<pRtree->nDim; i++){
+ float x1 = aCell[0].aCoord[i*2];
+ float x2 = aCell[0].aCoord[i*2+1];
+ float x3 = x1;
+ float x4 = x2;
+ int jj;
+
+ int iCellLeft = 0;
+ int iCellRight = 0;
+
+ for(jj=1; jj<nCell; jj++){
+ float left = aCell[jj].aCoord[i*2];
+ float right = aCell[jj].aCoord[i*2+1];
+
+ if( left<x1 ) x1 = left;
+ if( right>x4 ) x4 = right;
+ if( left>x3 ){
+ x3 = left;
+ iCellRight = jj;
+ }
+ if( right<x2 ){
+ x2 = right;
+ iCellLeft = jj;
+ }
+ }
+
+ if( x4!=x1 ){
+ float normalwidth = (x3 - x2) / (x4 - x1);
+ if( normalwidth>maxNormalInnerWidth ){
+ iLeftSeed = iCellLeft;
+ iRightSeed = iCellRight;
+ }
+ }
+ }
+
+ *piLeftSeed = iLeftSeed;
+ *piRightSeed = iRightSeed;
+}
+#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
+
+#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
+/*
+** Implementation of the quadratic variant of the PickNext() function from
+** Guttman[84].
+*/
+static RtreeCell *QuadraticPickNext(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ RtreeCell *pLeftBox,
+ RtreeCell *pRightBox,
+ int *aiUsed
+){
+ #define FABS(a) ((a)<0.0?-1.0*(a):(a))
+
+ int iSelect = -1;
+ float fDiff;
+ int ii;
+ for(ii=0; ii<nCell; ii++){
+ if( aiUsed[ii]==0 ){
+ float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
+ float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
+ float diff = FABS(right-left);
+ if( iSelect<0 || diff>fDiff ){
+ fDiff = diff;
+ iSelect = ii;
+ }
+ }
+ }
+ aiUsed[iSelect] = 1;
+ return &aCell[iSelect];
+}
+
+/*
+** Implementation of the quadratic variant of the PickSeeds() function from
+** Guttman[84].
+*/
+static void QuadraticPickSeeds(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ int *piLeftSeed,
+ int *piRightSeed
+){
+ int ii;
+ int jj;
+
+ int iLeftSeed = 0;
+ int iRightSeed = 1;
+ float fWaste = 0.0;
+
+ for(ii=0; ii<nCell; ii++){
+ for(jj=ii+1; jj<nCell; jj++){
+ float right = cellArea(pRtree, &aCell[jj]);
+ float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
+ float waste = growth - right;
+
+ if( waste>fWaste ){
+ iLeftSeed = ii;
+ iRightSeed = jj;
+ fWaste = waste;
+ }
+ }
+ }
+
+ *piLeftSeed = iLeftSeed;
+ *piRightSeed = iRightSeed;
+}
+#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
+
+/*
+** Arguments aIdx, aDistance and aSpare all point to arrays of size
+** nIdx. The aIdx array contains the set of integers from 0 to
+** (nIdx-1) in no particular order. This function sorts the values
+** in aIdx according to the indexed values in aDistance. For
+** example, assuming the inputs:
+**
+** aIdx = { 0, 1, 2, 3 }
+** aDistance = { 5.0, 2.0, 7.0, 6.0 }
+**
+** this function sets the aIdx array to contain:
+**
+** aIdx = { 0, 1, 2, 3 }
+**
+** The aSpare array is used as temporary working space by the
+** sorting algorithm.
+*/
+static void SortByDistance(
+ int *aIdx,
+ int nIdx,
+ float *aDistance,
+ int *aSpare
+){
+ if( nIdx>1 ){
+ int iLeft = 0;
+ int iRight = 0;
+
+ int nLeft = nIdx/2;
+ int nRight = nIdx-nLeft;
+ int *aLeft = aIdx;
+ int *aRight = &aIdx[nLeft];
+
+ SortByDistance(aLeft, nLeft, aDistance, aSpare);
+ SortByDistance(aRight, nRight, aDistance, aSpare);
+
+ memcpy(aSpare, aLeft, sizeof(int)*nLeft);
+ aLeft = aSpare;
+
+ while( iLeft<nLeft || iRight<nRight ){
+ if( iLeft==nLeft ){
+ aIdx[iLeft+iRight] = aRight[iRight];
+ iRight++;
+ }else if( iRight==nRight ){
+ aIdx[iLeft+iRight] = aLeft[iLeft];
+ iLeft++;
+ }else{
+ float fLeft = aDistance[aLeft[iLeft]];
+ float fRight = aDistance[aRight[iRight]];
+ if( fLeft<fRight ){
+ aIdx[iLeft+iRight] = aLeft[iLeft];
+ iLeft++;
+ }else{
+ aIdx[iLeft+iRight] = aRight[iRight];
+ iRight++;
+ }
+ }
+ }
+
+#if 0
+ /* Check that the sort worked */
+ {
+ int jj;
+ for(jj=1; jj<nIdx; jj++){
+ float left = aDistance[aIdx[jj-1]];
+ float right = aDistance[aIdx[jj]];
+ assert( left<=right );
+ }
+ }
+#endif
+ }
+}
+
+/*
+** Arguments aIdx, aCell and aSpare all point to arrays of size
+** nIdx. The aIdx array contains the set of integers from 0 to
+** (nIdx-1) in no particular order. This function sorts the values
+** in aIdx according to dimension iDim of the cells in aCell. The
+** minimum value of dimension iDim is considered first, the
+** maximum used to break ties.
+**
+** The aSpare array is used as temporary working space by the
+** sorting algorithm.
+*/
+static void SortByDimension(
+ 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(aLeft, nLeft, iDim, aCell, aSpare);
+ SortByDimension(aRight, nRight, iDim, aCell, aSpare);
+
+ memcpy(aSpare, aLeft, sizeof(int)*nLeft);
+ aLeft = aSpare;
+ while( iLeft<nLeft || iRight<nRight ){
+ float xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2];
+ float xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1];
+ float xright1 = aCell[aRight[iRight]].aCoord[iDim*2];
+ float xright2 = aCell[aRight[iRight]].aCoord[iDim*2+1];
+
+ if( (iLeft!=nLeft) && ((iRight==nRight)
+ || (xleft1<xright1)
+ || (xleft1==xright1 && xleft2<xright2)
+ )){
+ aIdx[iLeft+iRight] = aLeft[iLeft];
+ iLeft++;
+ }else{
+ aIdx[iLeft+iRight] = aRight[iRight];
+ iRight++;
+ }
+ }
+
+#if 0
+ /* Check that the sort worked */
+ {
+ int jj;
+ for(jj=1; jj<nIdx; jj++){
+ float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
+ float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
+ float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
+ float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
+ assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
+ }
+ }
+#endif
+ }
+}
+
+#if VARIANT_RSTARTREE_SPLIT
+/*
+** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
+*/
+static int splitNodeStartree(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ RtreeNode *pLeft,
+ RtreeNode *pRight,
+ RtreeCell *pBboxLeft,
+ RtreeCell *pBboxRight
+){
+ int **aaSorted;
+ int *aSpare;
+ int ii;
+
+ int iBestDim;
+ int iBestSplit;
+ float fBestMargin;
+
+ int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
+
+ aaSorted = (int **)sqlite3_malloc(nByte);
+ if( !aaSorted ){
+ return SQLITE_NOMEM;
+ }
+
+ aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
+ memset(aaSorted, 0, nByte);
+ for(ii=0; ii<pRtree->nDim; ii++){
+ int jj;
+ aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
+ for(jj=0; jj<nCell; jj++){
+ aaSorted[ii][jj] = jj;
+ }
+ SortByDimension(aaSorted[ii], nCell, ii, aCell, aSpare);
+ }
+
+ for(ii=0; ii<pRtree->nDim; ii++){
+ float margin = 0.0;
+ float fBestOverlap;
+ float fBestArea;
+ int iBestLeft;
+ int nLeft;
+
+ for(
+ nLeft=RTREE_MINCELLS(pRtree);
+ nLeft<=(nCell-RTREE_MINCELLS(pRtree));
+ nLeft++
+ ){
+ RtreeCell left;
+ RtreeCell right;
+ int kk;
+ float overlap;
+ float area;
+
+ memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
+ memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
+ for(kk=1; kk<(nCell-1); kk++){
+ if( kk<nLeft ){
+ cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
+ }else{
+ cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
+ }
+ }
+ margin += cellMargin(pRtree, &left);
+ margin += cellMargin(pRtree, &right);
+ overlap = cellOverlap(pRtree, &left, &right, 1, -1);
+ area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
+ if( (nLeft==RTREE_MINCELLS(pRtree))
+ || (overlap<fBestOverlap)
+ || (overlap==fBestOverlap && area<fBestArea)
+ ){
+ iBestLeft = nLeft;
+ fBestOverlap = overlap;
+ fBestArea = area;
+ }
+ }
+
+ if( ii==0 || margin<fBestMargin ){
+ iBestDim = ii;
+ fBestMargin = margin;
+ iBestSplit = iBestLeft;
+ }
+ }
+
+ memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
+ memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
+ for(ii=0; ii<nCell; ii++){
+ RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
+ RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
+ RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
+ nodeInsertCell(pRtree, pTarget, pCell);
+ cellUnion(pRtree, pBbox, pCell);
+ }
+
+ sqlite3_free(aaSorted);
+ return SQLITE_OK;
+}
+#endif
+
+#if VARIANT_GUTTMAN_SPLIT
+/*
+** Implementation of the regular R-tree SplitNode from Guttman[1984].
+*/
+static int splitNodeGuttman(
+ Rtree *pRtree,
+ RtreeCell *aCell,
+ int nCell,
+ RtreeNode *pLeft,
+ RtreeNode *pRight,
+ RtreeCell *pBboxLeft,
+ RtreeCell *pBboxRight
+){
+ int iLeftSeed = 0;
+ int iRightSeed = 1;
+ int *aiUsed;
+ int i;
+
+ aiUsed = sqlite3_malloc(sizeof(int)*nCell);
+ memset(aiUsed, 0, sizeof(int)*nCell);
+
+ PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
+
+ memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
+ memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
+ nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
+ nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
+ aiUsed[iLeftSeed] = 1;
+ aiUsed[iRightSeed] = 1;
+
+ for(i=nCell-2; i>0; i--){
+ RtreeCell *pNext;
+ pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
+ float diff =
+ cellGrowth(pRtree, pBboxLeft, pNext) -
+ cellGrowth(pRtree, pBboxRight, pNext)
+ ;
+ if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
+ || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
+ ){
+ nodeInsertCell(pRtree, pRight, pNext);
+ cellUnion(pRtree, pBboxRight, pNext);
+ }else{
+ nodeInsertCell(pRtree, pLeft, pNext);
+ cellUnion(pRtree, pBboxLeft, pNext);
+ }
+ }
+
+ sqlite3_free(aiUsed);
+ return SQLITE_OK;
+}
+#endif
+
+static int updateMapping(
+ Rtree *pRtree,
+ i64 iRowid,
+ RtreeNode *pNode,
+ int iHeight
+){
+ int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
+ xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
+ if( iHeight>0 ){
+ RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
+ if( pChild ){
+ nodeRelease(pRtree, pChild->pParent);
+ nodeReference(pNode);
+ pChild->pParent = pNode;
+ }
+ }
+ return xSetMapping(pRtree, iRowid, pNode->iNode);
+}
+
+static int SplitNode(
+ Rtree *pRtree,
+ RtreeNode *pNode,
+ RtreeCell *pCell,
+ int iHeight
+){
+ int i;
+ int newCellIsRight = 0;
+
+ int rc = SQLITE_OK;
+ int nCell = NCELL(pNode);
+ RtreeCell *aCell;
+ int *aiUsed;
+
+ RtreeNode *pLeft = 0;
+ RtreeNode *pRight = 0;
+
+ RtreeCell leftbbox;
+ RtreeCell rightbbox;
+
+ /* Allocate an array and populate it with a copy of pCell and
+ ** all cells from node pLeft. Then zero the original node.
+ */
+ aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
+ if( !aCell ){
+ rc = SQLITE_NOMEM;
+ goto splitnode_out;
+ }
+ aiUsed = (int *)&aCell[nCell+1];
+ memset(aiUsed, 0, sizeof(int)*(nCell+1));
+ for(i=0; i<nCell; i++){
+ nodeGetCell(pRtree, pNode, i, &aCell[i]);
+ }
+ nodeZero(pRtree, pNode);
+ memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
+ nCell++;
+
+ if( pNode->iNode==1 ){
+ pRight = nodeNew(pRtree, pNode, 1);
+ pLeft = nodeNew(pRtree, pNode, 1);
+ pRtree->iDepth++;
+ pNode->isDirty = 1;
+ writeInt16(pNode->zData, pRtree->iDepth);
+ }else{
+ pLeft = pNode;
+ pRight = nodeNew(pRtree, pLeft->pParent, 1);
+ nodeReference(pLeft);
+ }
+
+ if( !pLeft || !pRight ){
+ rc = SQLITE_NOMEM;
+ goto splitnode_out;
+ }
+
+ memset(pLeft->zData, 0, pRtree->iNodeSize);
+ memset(pRight->zData, 0, pRtree->iNodeSize);
+
+ rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
+ if( rc!=SQLITE_OK ){
+ goto splitnode_out;
+ }
+
+ /* Ensure both child nodes have node numbers assigned to them. */
+ if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
+ || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
+ ){
+ goto splitnode_out;
+ }
+
+ rightbbox.iRowid = pRight->iNode;
+ leftbbox.iRowid = pLeft->iNode;
+
+ if( pNode->iNode==1 ){
+ rc = insertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
+ if( rc!=SQLITE_OK ){
+ goto splitnode_out;
+ }
+ }else{
+ RtreeNode *pParent = pLeft->pParent;
+ int iCell = nodeParentIndex(pRtree, pLeft);
+ nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
+ AdjustTree(pRtree, pParent, &leftbbox);
+ }
+ if( (rc = insertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
+ goto splitnode_out;
+ }
+
+ for(i=0; i<NCELL(pRight); i++){
+ i64 iRowid = nodeGetRowid(pRtree, pRight, i);
+ rc = updateMapping(pRtree, iRowid, pRight, iHeight);
+ if( iRowid==pCell->iRowid ){
+ newCellIsRight = 1;
+ }
+ if( rc!=SQLITE_OK ){
+ goto splitnode_out;
+ }
+ }
+ if( pNode->iNode==1 ){
+ for(i=0; i<NCELL(pLeft); i++){
+ i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
+ rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
+ if( rc!=SQLITE_OK ){
+ goto splitnode_out;
+ }
+ }
+ }else if( newCellIsRight==0 ){
+ rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
+ }
+
+ if( rc==SQLITE_OK ){
+ rc = nodeRelease(pRtree, pRight);
+ pRight = 0;
+ }
+ if( rc==SQLITE_OK ){
+ rc = nodeRelease(pRtree, pLeft);
+ pLeft = 0;
+ }
+
+splitnode_out:
+ nodeRelease(pRtree, pRight);
+ nodeRelease(pRtree, pLeft);
+ sqlite3_free(aCell);
+ return rc;
+}
+
+static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
+ int rc = SQLITE_OK;
+ if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
+ sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
+ if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){
+ i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
+ rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
+ }else{
+ rc = SQLITE_ERROR;
+ }
+ sqlite3_reset(pRtree->pReadParent);
+ if( rc==SQLITE_OK ){
+ rc = fixLeafParent(pRtree, pLeaf->pParent);
+ }
+ }
+ return rc;
+}
+
+static int deleteCell(Rtree *, RtreeNode *, int, int);
+
+static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
+ int rc;
+ RtreeNode *pParent;
+ int iCell;
+
+ assert( pNode->nRef==1 );
+
+ /* Remove the entry in the parent cell. */
+ iCell = nodeParentIndex(pRtree, pNode);
+ pParent = pNode->pParent;
+ pNode->pParent = 0;
+ if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1))
+ || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
+ ){
+ return rc;
+ }
+
+ /* Remove the xxx_node entry. */
+ sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
+ sqlite3_step(pRtree->pDeleteNode);
+ if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
+ return rc;
+ }
+
+ /* Remove the xxx_parent entry. */
+ sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
+ sqlite3_step(pRtree->pDeleteParent);
+ if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
+ return rc;
+ }
+
+ /* Remove the node from the in-memory hash table and link it into
+ ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
+ */
+ nodeHashDelete(pRtree, pNode);
+ pNode->iNode = iHeight;
+ pNode->pNext = pRtree->pDeleted;
+ pNode->nRef++;
+ pRtree->pDeleted = pNode;
+
+ return SQLITE_OK;
+}
+
+static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
+ RtreeNode *pParent = pNode->pParent;
+ if( pParent ){
+ int ii;
+ int nCell = NCELL(pNode);
+ RtreeCell box; /* Bounding box for pNode */
+ nodeGetCell(pRtree, pNode, 0, &box);
+ for(ii=1; ii<nCell; ii++){
+ RtreeCell cell;
+ nodeGetCell(pRtree, pNode, ii, &cell);
+ cellUnion(pRtree, &box, &cell);
+ }
+ box.iRowid = pNode->iNode;
+ ii = nodeParentIndex(pRtree, pNode);
+ nodeOverwriteCell(pRtree, pParent, &box, ii);
+ fixBoundingBox(pRtree, pParent);
+ }
+}
+
+/*
+** Delete the cell at index iCell of node pNode. After removing the
+** cell, adjust the r-tree data structure if required.
+*/
+static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
+ int rc;
+
+ if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
+ return rc;
+ }
+
+ /* Remove the cell from the node. This call just moves bytes around
+ ** the in-memory node image, so it cannot fail.
+ */
+ nodeDeleteCell(pRtree, pNode, iCell);
+
+ /* If the node is not the tree root and now has less than the minimum
+ ** number of cells, remove it from the tree. Otherwise, update the
+ ** cell in the parent node so that it tightly contains the updated
+ ** node.
+ */
+ if( pNode->iNode!=1 ){
+ RtreeNode *pParent = pNode->pParent;
+ if( (pParent->iNode!=1 || NCELL(pParent)!=1)
+ && (NCELL(pNode)<RTREE_MINCELLS(pRtree))
+ ){
+ rc = removeNode(pRtree, pNode, iHeight);
+ }else{
+ fixBoundingBox(pRtree, pNode);
+ }
+ }
+
+ return rc;
+}
+
+static int Reinsert(
+ Rtree *pRtree,
+ RtreeNode *pNode,
+ RtreeCell *pCell,
+ int iHeight
+){
+ int *aOrder;
+ int *aSpare;
+ RtreeCell *aCell;
+ float *aDistance;
+ int nCell;
+ float aCenterCoord[RTREE_MAX_DIMENSIONS];
+ int iDim;
+ int ii;
+ int rc = SQLITE_OK;
+
+ memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
+
+ nCell = NCELL(pNode)+1;
+
+ /* Allocate the buffers used by this operation. The allocation is
+ ** relinquished before this function returns.
+ */
+ aCell = (RtreeCell *)sqlite3_malloc(nCell * (
+ sizeof(RtreeCell) + /* aCell array */
+ sizeof(int) + /* aOrder array */
+ sizeof(int) + /* aSpare array */
+ sizeof(float) /* aDistance array */
+ ));
+ if( !aCell ){
+ return SQLITE_NOMEM;
+ }
+ aOrder = (int *)&aCell[nCell];
+ aSpare = (int *)&aOrder[nCell];
+ aDistance = (float *)&aSpare[nCell];
+
+ for(ii=0; ii<nCell; ii++){
+ if( ii==(nCell-1) ){
+ memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
+ }else{
+ nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
+ }
+ aOrder[ii] = ii;
+ for(iDim=0; iDim<pRtree->nDim; iDim++){
+ aCenterCoord[iDim] += aCell[ii].aCoord[iDim*2];
+ aCenterCoord[iDim] += aCell[ii].aCoord[iDim*2+1];
+ }
+ }
+ for(iDim=0; iDim<pRtree->nDim; iDim++){
+ aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
+ }
+
+ for(ii=0; ii<nCell; ii++){
+ aDistance[ii] = 0.0;
+ for(iDim=0; iDim<pRtree->nDim; iDim++){
+ float coord = aCell[ii].aCoord[iDim*2+1] - aCell[ii].aCoord[iDim*2];
+ aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
+ }
+ }
+
+ SortByDistance(aOrder, nCell, aDistance, aSpare);
+ nodeZero(pRtree, pNode);
+
+ for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
+ RtreeCell *p = &aCell[aOrder[ii]];
+ nodeInsertCell(pRtree, pNode, p);
+ if( p->iRowid==pCell->iRowid ){
+ if( iHeight==0 ){
+ rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
+ }else{
+ rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
+ }
+ }
+ }
+ if( rc==SQLITE_OK ){
+ fixBoundingBox(pRtree, pNode);
+ }
+ for(; rc==SQLITE_OK && ii<nCell; ii++){
+ /* Find a node to store this cell in. pNode->iNode currently contains
+ ** the height of the sub-tree headed by the cell.
+ */
+ RtreeNode *pInsert;
+ RtreeCell *p = &aCell[aOrder[ii]];
+ rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
+ if( rc==SQLITE_OK ){
+ int rc2;
+ rc = insertCell(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 insertCell(
+ Rtree *pRtree,
+ RtreeNode *pNode,
+ RtreeCell *pCell,
+ int iHeight
+){
+ int rc = SQLITE_OK;
+ if( iHeight>0 ){
+ RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
+ if( pChild ){
+ nodeRelease(pRtree, pChild->pParent);
+ nodeReference(pNode);
+ pChild->pParent = pNode;
+ }
+ }
+ if( nodeInsertCell(pRtree, pNode, pCell) ){
+#if VARIANT_RSTARTREE_REINSERT
+ if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
+ rc = SplitNode(pRtree, pNode, pCell, iHeight);
+ }else{
+ pRtree->iReinsertHeight = iHeight;
+ rc = Reinsert(pRtree, pNode, pCell, iHeight);
+ }
+#else
+ rc = SplitNode(pRtree, pNode, pCell, iHeight);
+#endif
+ }else{
+ AdjustTree(pRtree, pNode, pCell);
+ if( iHeight==0 ){
+ rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
+ }else{
+ rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
+ }
+ }
+ return rc;
+}
+
+static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
+ int ii;
+ int rc = SQLITE_OK;
+ int nCell = NCELL(pNode);
+
+ for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
+ RtreeNode *pInsert;
+ RtreeCell cell;
+ nodeGetCell(pRtree, pNode, ii, &cell);
+
+ /* Find a node to store this cell in. pNode->iNode currently contains
+ ** the height of the sub-tree headed by the cell.
+ */
+ rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
+ if( rc==SQLITE_OK ){
+ int rc2;
+ rc = insertCell(pRtree, pInsert, &cell, pNode->iNode);
+ rc2 = nodeRelease(pRtree, pInsert);
+ if( rc==SQLITE_OK ){
+ rc = rc2;
+ }
+ }
+ }
+ return rc;
+}
+
+/*
+** Select a currently unused rowid for a new r-tree record.
+*/
+static int newRowid(Rtree *pRtree, i64 *piRowid){
+ int rc;
+ sqlite3_bind_null(pRtree->pWriteRowid, 1);
+ sqlite3_bind_null(pRtree->pWriteRowid, 2);
+ sqlite3_step(pRtree->pWriteRowid);
+ rc = sqlite3_reset(pRtree->pWriteRowid);
+ *piRowid = sqlite3_last_insert_rowid(pRtree->db);
+ return rc;
+}
+
+#ifndef NDEBUG
+static int hashIsEmpty(Rtree *pRtree){
+ int ii;
+ for(ii=0; ii<HASHSIZE; ii++){
+ assert( !pRtree->aHash[ii] );
+ }
+ return 1;
+}
+#endif
+
+/*
+** The xUpdate method for rtree module virtual tables.
+*/
+int rtreeUpdate(
+ sqlite3_vtab *pVtab,
+ int nData,
+ sqlite3_value **azData,
+ sqlite_int64 *pRowid
+){
+ Rtree *pRtree = (Rtree *)pVtab;
+ int rc = SQLITE_OK;
+
+ rtreeReference(pRtree);
+
+ assert(nData>=1);
+ assert(hashIsEmpty(pRtree));
+
+ /* If azData[0] is not an SQL NULL value, it is the rowid of a
+ ** record to delete from the r-tree table. The following block does
+ ** just that.
+ */
+ if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
+ i64 iDelete; /* The rowid to delete */
+ RtreeNode *pLeaf; /* Leaf node containing record iDelete */
+ int iCell; /* Index of iDelete cell in pLeaf */
+ RtreeNode *pRoot;
+
+ /* Obtain a reference to the root node to initialise Rtree.iDepth */
+ rc = nodeAcquire(pRtree, 1, 0, &pRoot);
+
+ /* Obtain a reference to the leaf node that contains the entry
+ ** about to be deleted.
+ */
+ if( rc==SQLITE_OK ){
+ iDelete = sqlite3_value_int64(azData[0]);
+ rc = findLeafNode(pRtree, iDelete, &pLeaf);
+ }
+
+ /* Delete the cell in question from the leaf node. */
+ if( rc==SQLITE_OK ){
+ int rc2;
+ iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
+ rc = deleteCell(pRtree, pLeaf, iCell, 0);
+ rc2 = nodeRelease(pRtree, pLeaf);
+ if( rc==SQLITE_OK ){
+ rc = rc2;
+ }
+ }
+
+ /* Delete the corresponding entry in the <rtree>_rowid table. */
+ if( rc==SQLITE_OK ){
+ sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
+ sqlite3_step(pRtree->pDeleteRowid);
+ rc = sqlite3_reset(pRtree->pDeleteRowid);
+ }
+
+ /* Check if the root node now has exactly one child. If so, remove
+ ** it, schedule the contents of the child for reinsertion and
+ ** reduce the tree height by one.
+ **
+ ** This is equivalent to copying the contents of the child into
+ ** the root node (the operation that Gutman's paper says to perform
+ ** in this scenario).
+ */
+ if( rc==SQLITE_OK && pRtree->iDepth>0 ){
+ if( rc==SQLITE_OK && NCELL(pRoot)==1 ){
+ RtreeNode *pChild;
+ i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
+ rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
+ if( rc==SQLITE_OK ){
+ rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
+ }
+ if( rc==SQLITE_OK ){
+ pRtree->iDepth--;
+ writeInt16(pRoot->zData, pRtree->iDepth);
+ pRoot->isDirty = 1;
+ }
+ }
+ }
+
+ /* Re-insert the contents of any underfull nodes removed from the tree. */
+ for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
+ if( rc==SQLITE_OK ){
+ rc = reinsertNodeContent(pRtree, pLeaf);
+ }
+ pRtree->pDeleted = pLeaf->pNext;
+ sqlite3_free(pLeaf);
+ }
+
+ /* Release the reference to the root node. */
+ if( rc==SQLITE_OK ){
+ rc = nodeRelease(pRtree, pRoot);
+ }else{
+ nodeRelease(pRtree, pRoot);
+ }
+ }
+
+ /* If the azData[] array contains more than one element, elements
+ ** (azData[2]..azData[argc-1]) contain a new record to insert into
+ ** the r-tree structure.
+ */
+ if( rc==SQLITE_OK && nData>1 ){
+ /* Insert a new record into the r-tree */
+ RtreeCell cell;
+ int ii;
+ RtreeNode *pLeaf;
+
+ /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
+ assert( nData==(pRtree->nDim*2 + 3) );
+ for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+ cell.aCoord[ii] = (float)sqlite3_value_double(azData[ii+3]);
+ cell.aCoord[ii+1] = (float)sqlite3_value_double(azData[ii+4]);
+ if( cell.aCoord[ii]>cell.aCoord[ii+1] ){
+ rc = SQLITE_CONSTRAINT;
+ goto constraint;
+ }
+ }
+
+ /* Figure out the rowid of the new row. */
+ if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
+ rc = newRowid(pRtree, &cell.iRowid);
+ }else{
+ cell.iRowid = sqlite3_value_int64(azData[2]);
+ sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
+ if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
+ sqlite3_reset(pRtree->pReadRowid);
+ rc = SQLITE_CONSTRAINT;
+ goto constraint;
+ }
+ rc = sqlite3_reset(pRtree->pReadRowid);
+ }
+
+ if( rc==SQLITE_OK ){
+ rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
+ }
+ if( rc==SQLITE_OK ){
+ int rc2;
+ pRtree->iReinsertHeight = -1;
+ rc = insertCell(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 '%q_node';"
+ "ALTER TABLE %Q.'%q_parent' RENAME TO '%q_parent';"
+ "ALTER TABLE %Q.'%q_rowid' RENAME TO '%q_rowid';"
+ , pRtree->zDb, pRtree->zName, zNewName
+ , pRtree->zDb, pRtree->zName, zNewName
+ , pRtree->zDb, pRtree->zName, zNewName
+ );
+ if( zSql ){
+ rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
+ sqlite3_free(zSql);
+ }
+ return rc;
+}
+
+static sqlite3_module rtreeModule = {
+ 0, /* iVersion */
+ rtreeCreate, /* xCreate - create a table */
+ rtreeConnect, /* xConnect - connect to an existing table */
+ rtreeBestIndex, /* xBestIndex - Determine search strategy */
+ rtreeDisconnect, /* xDisconnect - Disconnect from a table */
+ rtreeDestroy, /* xDestroy - Drop a table */
+ rtreeOpen, /* xOpen - open a cursor */
+ rtreeClose, /* xClose - close a cursor */
+ rtreeFilter, /* xFilter - configure scan constraints */
+ rtreeNext, /* xNext - advance a cursor */
+ rtreeEof, /* xEof */
+ rtreeColumn, /* xColumn - read data */
+ rtreeRowid, /* xRowid - read data */
+ rtreeUpdate, /* xUpdate - write data */
+ 0, /* xBegin - begin transaction */
+ 0, /* xSync - sync transaction */
+ 0, /* xCommit - commit transaction */
+ 0, /* xRollback - rollback transaction */
+ 0, /* xFindFunction - function overloading */
+ rtreeRename /* xRename - rename the table */
+};
+
+static int rtreeSqlInit(
+ Rtree *pRtree,
+ sqlite3 *db,
+ const char *zDb,
+ const char *zPrefix,
+ int isCreate
+){
+ int rc = SQLITE_OK;
+
+ #define N_STATEMENT 9
+ static const char *azSql[N_STATEMENT] = {
+ /* Read and write the xxx_node table */
+ "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
+ "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
+ "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
+
+ /* Read and write the xxx_rowid table */
+ "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
+ "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
+ "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
+
+ /* Read and write the xxx_parent table */
+ "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
+ "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
+ "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
+ };
+ sqlite3_stmt **appStmt[N_STATEMENT];
+ int i;
+
+ pRtree->db = db;
+
+ if( isCreate ){
+ char *zCreate = sqlite3_mprintf(
+"CREATE TABLE '%q'.'%q_node'(nodeno INTEGER PRIMARY KEY, data BLOB);"
+"CREATE TABLE '%q'.'%q_rowid'(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
+"CREATE TABLE '%q'.'%q_parent'(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
+"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
+ zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
+ );
+ if( !zCreate ){
+ return SQLITE_NOMEM;
+ }
+ rc = sqlite3_exec(db, zCreate, 0, 0, 0);
+ sqlite3_free(zCreate);
+ if( rc!=SQLITE_OK ){
+ return rc;
+ }
+ }
+
+ appStmt[0] = &pRtree->pReadNode;
+ appStmt[1] = &pRtree->pWriteNode;
+ appStmt[2] = &pRtree->pDeleteNode;
+ appStmt[3] = &pRtree->pReadRowid;
+ appStmt[4] = &pRtree->pWriteRowid;
+ appStmt[5] = &pRtree->pDeleteRowid;
+ appStmt[6] = &pRtree->pReadParent;
+ appStmt[7] = &pRtree->pWriteParent;
+ appStmt[8] = &pRtree->pDeleteParent;
+
+ for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
+ char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
+ if( zSql ){
+ rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0);
+ }else{
+ rc = SQLITE_NOMEM;
+ }
+ sqlite3_free(zSql);
+ }
+
+ return rc;
+}
+
+/*
+** This routine queries database handle db for the page-size used by
+** database zDb. If successful, the page-size in bytes is written to
+** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error
+** code is returned.
+*/
+static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){
+ int rc = SQLITE_NOMEM;
+ char *zSql;
+ sqlite3_stmt *pStmt = 0;
+
+ zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb);
+ if( !zSql ){
+ return SQLITE_NOMEM;
+ }
+
+ rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
+ sqlite3_free(zSql);
+ if( rc!=SQLITE_OK ){
+ return rc;
+ }
+
+ if( SQLITE_ROW==sqlite3_step(pStmt) ){
+ *piPageSize = sqlite3_column_int(pStmt, 0);
+ }
+ return sqlite3_finalize(pStmt);
+}
+
+/*
+** This function is the implementation of both the xConnect and xCreate
+** methods of the r-tree virtual table.
+**
+** argv[0] -> module name
+** argv[1] -> database name
+** argv[2] -> table name
+** argv[...] -> column names...
+*/
+static int rtreeInit(
+ sqlite3 *db, /* Database connection */
+ void *pAux, /* Pointer to head of rtree list */
+ 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;
+ int iPageSize = 0;
+ Rtree *pRtree;
+ int nDb; /* Length of string argv[1] */
+ int nName; /* Length of string argv[2] */
+
+ 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;
+ }
+
+ rc = getPageSize(db, argv[1], &iPageSize);
+ if( rc!=SQLITE_OK ){
+ return rc;
+ }
+
+ /* 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;
+ memcpy(pRtree->zDb, argv[1], nDb);
+ memcpy(pRtree->zName, argv[2], nName);
+
+ /* Figure out the node size to use. By default, use 64 bytes less than
+ ** the database page-size. This ensures that each node is stored on
+ ** a single database page.
+ **
+ ** If the databasd page-size is so large that more than RTREE_MAXCELLS
+ ** entries would fit in a single node, use a smaller node-size.
+ */
+ pRtree->iNodeSize = iPageSize-64;
+ if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
+ pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
+ }
+
+ /* 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 = 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 || sqlite3_declare_vtab(db, zSql) ){
+ rc = SQLITE_NOMEM;
+ }
+ 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;
+
+ 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],"%d", cell.iRowid);
+ nCell = strlen(zCell);
+ for(jj=0; jj<tree.nDim*2; jj++){
+ sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj]);
+ 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){
+ 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){
+ int rc = SQLITE_OK;
+
+ if( rc==SQLITE_OK ){
+ int utf8 = SQLITE_UTF8;
+ rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
+ }
+ if( rc==SQLITE_OK ){
+ int utf8 = SQLITE_UTF8;
+ rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
+ }
+ if( rc==SQLITE_OK ){
+ rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, 0, 0);
+ }
+
+ return rc;
+}
+
+#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.test b/ext/rtree/rtree.test
new file mode 100644
index 0000000..1dbfddf
--- /dev/null
+++ b/ext/rtree/rtree.test
@@ -0,0 +1,43 @@
+#
+# 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 runs all rtree related tests.
+#
+# $Id: rtree.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+
+set testdir [file join [file dirname $argv0] .. .. test]
+source $testdir/tester.tcl
+rename finish_test really_finish_test
+proc finish_test {} {}
+set ISQUICK 1
+
+set EXCLUDE {
+ rtree.test
+}
+
+# Files to include in the test. If this list is empty then everything
+# that is not in the EXCLUDE list is run.
+#
+set INCLUDE {
+}
+
+foreach testfile [lsort -dictionary [glob [file dirname $argv0]/*.test]] {
+ set tail [file tail $testfile]
+ if {[lsearch -exact $EXCLUDE $tail]>=0} continue
+ if {[llength $INCLUDE]>0 && [lsearch -exact $INCLUDE $tail]<0} continue
+ source $testfile
+ catch {db close}
+ if {$sqlite_open_file_count>0} {
+ puts "$tail did not close all files: $sqlite_open_file_count"
+ incr nErr
+ lappend ::failList $tail
+ set sqlite_open_file_count 0
+ }
+}
+
+set sqlite_open_file_count 0
+really_finish_test
+
diff --git a/ext/rtree/rtree1.test b/ext/rtree/rtree1.test
new file mode 100644
index 0000000..15cdbea
--- /dev/null
+++ b/ext/rtree/rtree1.test
@@ -0,0 +1,361 @@
+# 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.
+#
+# $Id: rtree1.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+#
+
+set testdir [file join [file dirname $argv0] .. .. test]
+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.
+#
+
+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 {
+ 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}
+
+
+finish_test
+
diff --git a/ext/rtree/rtree2.test b/ext/rtree/rtree2.test
new file mode 100644
index 0000000..43c455f
--- /dev/null
+++ b/ext/rtree/rtree2.test
@@ -0,0 +1,144 @@
+# 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.
+#
+# $Id: rtree2.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+#
+
+set testdir [file join [file dirname $argv0] .. .. test]
+source $testdir/tester.tcl
+source [file join [file dirname $argv0] rtree_util.tcl]
+
+ifcapable !rtree {
+ finish_test
+ return
+}
+
+set ::NROW 1000
+set ::NDEL 10
+set ::NSELECT 100
+
+for {set nDim 1} {$nDim <= 5} {incr nDim} {
+
+ do_test rtree2-$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 rtree(ii, $cols);
+ CREATE TABLE t2 (ii, $cols);
+ "
+ } {}
+
+ do_test rtree2-$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-$nDim.3 {
+ rtree_check db t1
+ } 0
+
+ set OPS [list < > <= >= =]
+ for {set ii 0} {$ii < $::NSELECT} {incr ii} {
+ do_test rtree2-$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-$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-$nDim.5.$ii.2 {
+ rtree_check db t1
+ } {0}
+ }
+
+ do_test rtree2-$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..667b04e
--- /dev/null
+++ b/ext/rtree/rtree3.test
@@ -0,0 +1,72 @@
+# 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.
+#
+# $Id: rtree3.test,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+#
+
+set testdir [file join [file dirname $argv0] .. .. test]
+source $testdir/tester.tcl
+
+ifcapable !rtree {
+ finish_test
+ return
+}
+
+# Only run these tests if memory debugging is turned on.
+#
+source $testdir/malloc_common.tcl
+if {!$MEMDEBUG} {
+ puts "Skipping malloc tests: not compiled with -DSQLITE_MEMDEBUG..."
+ finish_test
+ return
+}
+
+do_malloc_test rtree3-1 -sqlbody {
+ 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_malloc_test rtree3-2 -sqlprep {
+ CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
+ INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
+} -sqlbody {
+ DROP TABLE rt;
+}
+
+
+do_malloc_test rtree3-3 -sqlprep {
+ CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
+ INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
+} -tclbody {
+ 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
+ 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
+}
+
+finish_test
+
diff --git a/ext/rtree/rtree_perf.tcl b/ext/rtree/rtree_perf.tcl
new file mode 100644
index 0000000..fa3a4d3
--- /dev/null
+++ b/ext/rtree/rtree_perf.tcl
@@ -0,0 +1,76 @@
+
+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..55482e4
--- /dev/null
+++ b/ext/rtree/rtree_util.tcl
@@ -0,0 +1,195 @@
+# 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.
+#
+# $Id: rtree_util.tcl,v 1.1 2008/05/26 18:41:54 danielk1977 Exp $
+#
+
+
+#--------------------------------------------------------------------------
+# 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/viewrtree.tcl b/ext/rtree/viewrtree.tcl
new file mode 100644
index 0000000..2b4dd1b
--- /dev/null
+++ b/ext/rtree/viewrtree.tcl
@@ -0,0 +1,189 @@
+
+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
+
diff --git a/main.mk b/main.mk
index 6505f38..c841b29 100644
--- a/main.mk
+++ b/main.mk
@@ -58,7 +58,7 @@
select.o table.o $(TCLOBJ) tokenize.o trigger.o \
update.o util.o vacuum.o \
vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbefifo.o vdbemem.o \
- where.o utf.o legacy.o vtab.o
+ where.o utf.o legacy.o vtab.o rtree.o
EXTOBJ = icu.o
EXTOBJ += fts1.o \
@@ -412,6 +412,9 @@
fts3_tokenizer1.o: $(TOP)/ext/fts3/fts3_tokenizer1.c $(HDR) $(EXTHDR)
$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/fts3/fts3_tokenizer1.c
+rtree.o: $(TOP)/ext/rtree/rtree.c $(HDR) $(EXTHDR)
+ $(TCCX) -DSQLITE_CORE -c $(TOP)/ext/rtree/rtree.c
+
# Rules for building test programs and for running tests
#
diff --git a/manifest b/manifest
index 760d6dc..cb7d520 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Fix\sthe\sLIKE\squery\soptimizer\sso\sthat\sit\sworks\swith\sLIKE\spatterns\nending\sin\s'@%'\son\sNOCASE\scolumns.\s\sTicket\s#3139.\s(CVS\s5158)
-D 2008-05-26T18:33:41
+C Import\s'rtree'\sextension.\s(CVS\s5159)
+D 2008-05-26T18:41:54
F Makefile.arm-wince-mingw32ce-gcc ac5f7b2cef0cd850d6f755ba6ee4ab961b1fadf7
F Makefile.in 79aeba12300a54903f1b1257c1e7c190234045dd
F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654
@@ -63,9 +63,18 @@
F ext/fts3/mkfts3amal.tcl 252ecb7fe6467854f2aa237bf2c390b74e71f100
F ext/icu/README.txt 3b130aa66e7a681136f6add198b076a2f90d1e33
F ext/icu/icu.c 12e763d288d23b5a49de37caa30737b971a2f1e2
+F ext/rtree/README decb7976cfacf834074d15028af99344439e30c3
+F ext/rtree/rtree.c f56f8a5888d3584f5b19112ade2855db5a985690
+F ext/rtree/rtree.test ec173a9420ff012e4d29b3063add143583a597a7
+F ext/rtree/rtree1.test 96563843773129eaec544f52768853f06be61d9c
+F ext/rtree/rtree2.test 98f3c39b03577330566abf3c7e1e0baf8f9aa521
+F ext/rtree/rtree3.test 46d1959aa651d3df8b64d93762d3061c62b38105
+F ext/rtree/rtree_perf.tcl 0fabb6d5c48cb8024e042ce5d4bb88998b6ec1cb
+F ext/rtree/rtree_util.tcl ee0a0311eb12175319d78bfb37302320496cee6e
+F ext/rtree/viewrtree.tcl 09526398dae87a5a87c5aac2b3854dbaf8376869
F install-sh 9d4de14ab9fb0facae2f48780b874848cbf2f895
F ltmain.sh 09fe5815427dc7d0abb188bbcdf0e34896577210
-F main.mk 6a916bb5c17cf2a753346b32cc0869ffdc1ed4b3
+F main.mk 6c01687f355dc8c7dff14a952a7c720b3a4c11a6
F mkdll.sh 712e74f3efe08a6ba12b2945d018a29a89d7fe3b
F mkextu.sh 416f9b7089d80e5590a29692c9d9280a10dbad9f
F mkextw.sh 1a866b53637dab137191341cc875575a5ca110fb
@@ -102,7 +111,7 @@
F src/journal.c cffd2cd214e58c0e99c3ff632b3bee6c7cbb260e
F src/legacy.c 8f5a2b25d9673b4004287cf2bf51dbf7d0738406
F src/loadext.c eac6c61810a3b531808774bec7f3d238cfe261f3
-F src/main.c cf415e0920dc9f66806dd766ad72ba5cda533363
+F src/main.c 51f02209493572630dfcf4d4c8855f08aae21b9b
F src/malloc.c 12c1ae98ef1eff34b13c9eb526e0b7b479e1e820
F src/md5.c 008216bbb5d34c6fbab5357aa68575ad8a31516a
F src/mem1.c fc716ff521b6dd3e43eaa211967383308800e70a
@@ -148,7 +157,7 @@
F src/test_async.c 0d26a72361022f6f732dd1174c6615bad6e587ff
F src/test_autoext.c 5e892ab84aece3f0428920bf46923f16ac83962a
F src/test_btree.c c1308ba0b88ab577fa56c9e493a09829dfcded9c
-F src/test_config.c b910754c5ba311abf149457cdbfd66144e715b35
+F src/test_config.c 982bba6221b854a86427ae64e9c65b313b0f6e03
F src/test_devsym.c 76cf28b79c6f01658083ae2a972647b97a362a01
F src/test_func.c f4aafa10f17d52c43a64b47717265802e6e552b3
F src/test_hexio.c 2f1122aa3f012fa0142ee3c36ce5c902a70cd12f
@@ -637,7 +646,7 @@
F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0
F www/version3.tcl 890248cf7b70e60c383b0e84d77d5132b3ead42b
F www/whentouse.tcl fc46eae081251c3c181bd79c5faef8195d7991a5
-P 77d5a7aa1c7ea715298228ed2dbd0497cacbd0e4
-R d32b39a4864ba1e92f958c456cb9d453
-U drh
-Z b0b4c859c49b7350ba450c2f85000be9
+P 33548744369643cc8843b74ad1fc1b7d5988d7a4
+R 675fcc0cf171d37f901dfc59fa943c1b
+U danielk1977
+Z a3cfe87334f3bee1a0f0c75b4054c9e1
diff --git a/manifest.uuid b/manifest.uuid
index 22d93c1..b1fda07 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-33548744369643cc8843b74ad1fc1b7d5988d7a4
\ No newline at end of file
+b104dcd6adadbd3fe15a348fe9d4d290119e139e
\ No newline at end of file
diff --git a/src/main.c b/src/main.c
index 00ea04d..ecdc8e9 100644
--- a/src/main.c
+++ b/src/main.c
@@ -14,7 +14,7 @@
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
-** $Id: main.c,v 1.440 2008/05/22 13:56:17 danielk1977 Exp $
+** $Id: main.c,v 1.441 2008/05/26 18:41:54 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
@@ -1184,6 +1184,14 @@
rc = sqlite3IcuInit(db);
}
#endif
+
+#ifdef SQLITE_ENABLE_RTREE
+ if( !db->mallocFailed && rc==SQLITE_OK){
+ extern int sqlite3RtreeInit(sqlite3*);
+ rc = sqlite3RtreeInit(db);
+ }
+#endif
+
sqlite3Error(db, rc, 0);
/* -DSQLITE_DEFAULT_LOCKING_MODE=1 makes EXCLUSIVE the default locking
diff --git a/src/test_config.c b/src/test_config.c
index a82f5af..b1f23b9 100644
--- a/src/test_config.c
+++ b/src/test_config.c
@@ -16,7 +16,7 @@
** The focus of this file is providing the TCL testing layer
** access to compile-time constants.
**
-** $Id: test_config.c,v 1.25 2008/04/14 01:00:58 drh Exp $
+** $Id: test_config.c,v 1.26 2008/05/26 18:41:54 danielk1977 Exp $
*/
#include "sqliteLimit.h"
@@ -338,6 +338,12 @@
Tcl_SetVar2(interp, "sqlite_options", "reindex", "1", TCL_GLOBAL_ONLY);
#endif
+#ifdef SQLITE_ENABLE_RTREE
+ Tcl_SetVar2(interp, "sqlite_options", "rtree", "1", TCL_GLOBAL_ONLY);
+#else
+ Tcl_SetVar2(interp, "sqlite_options", "rtree", "0", TCL_GLOBAL_ONLY);
+#endif
+
#ifdef SQLITE_OMIT_SCHEMA_PRAGMAS
Tcl_SetVar2(interp, "sqlite_options", "schema_pragmas", "0", TCL_GLOBAL_ONLY);
#else