/*

** 2001 September 15

**

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

** a legal notice, here is a blessing:

**

** May you do good and not evil.

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

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

**

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

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

** algorithms packaged as an SQLite virtual table module.

*/

/*

** Database Format of R-Tree Tables

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

**

** The data structure for a single virtual r-tree table is stored in three

** native SQLite tables declared as follows. In each case, the '%' character

** in the table name is replaced with the user-supplied name of the r-tree

** table.

**

** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)

** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)

** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)

**

** The data for each node of the r-tree structure is stored in the %_node

** table. For each node that is not the root node of the r-tree, there is

** an entry in the %_parent table associating the node with its parent.

** And for each row of data in the table, there is an entry in the %_rowid

** table that maps from the entries rowid to the id of the node that it

** is stored on. If the r-tree contains auxiliary columns, those are stored

** on the end of the %_rowid table.

**

** The root node of an r-tree always exists, even if the r-tree table is

** empty. The nodeno of the root node is always 1. All other nodes in the

** table must be the same size as the root node. The content of each node

** is formatted as follows:

**

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

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

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

**

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

** stored in the node.

**

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

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

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

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

** child page.

*/

#if !defined(SQLITE_CORE) \

|| (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE))

#ifndef SQLITE_CORE

#include "sqlite3ext.h"

SQLITE_EXTENSION_INIT1

#else

#include "sqlite3.h"

#endif

#include <string.h>

#include <assert.h>

#include <stdio.h>

#ifndef SQLITE_AMALGAMATION

#include "sqlite3rtree.h"

typedef sqlite3_int64 i64;

typedef sqlite3_uint64 u64;

typedef unsigned char u8;

typedef unsigned short u16;

typedef unsigned int u32;

#endif

/* The following macro is used to suppress compiler warnings.

*/

#ifndef UNUSED_PARAMETER

# define UNUSED_PARAMETER(x) (void)(x)

#endif

typedef struct Rtree Rtree;

typedef struct RtreeCursor RtreeCursor;

typedef struct RtreeNode RtreeNode;

typedef struct RtreeCell RtreeCell;

typedef struct RtreeConstraint RtreeConstraint;

typedef struct RtreeMatchArg RtreeMatchArg;

typedef struct RtreeGeomCallback RtreeGeomCallback;

typedef union RtreeCoord RtreeCoord;

typedef struct RtreeSearchPoint RtreeSearchPoint;

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

#define RTREE_MAX_DIMENSIONS 5

/* Maximum number of auxiliary columns */

#define RTREE_MAX_AUX_COLUMN 100

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

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

** used.

*/

#define HASHSIZE 97

/* The xBestIndex method of this virtual table requires an estimate of

** the number of rows in the virtual table to calculate the costs of

** various strategies. If possible, this estimate is loaded from the

** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).

** Otherwise, if no sqlite_stat1 entry is available, use

** RTREE_DEFAULT_ROWEST.

*/

#define RTREE_DEFAULT_ROWEST 1048576

#define RTREE_MIN_ROWEST 100

/*

** An rtree virtual-table object.

*/

struct Rtree {

sqlite3_vtab base; /* Base class. Must be first */

sqlite3 *db; /* Host database connection */

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

u8 nDim; /* Number of dimensions */

u8 nDim2; /* Twice the number of dimensions */

u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */

u8 nBytesPerCell; /* Bytes consumed per cell */

u8 inWrTrans; /* True if inside write transaction */

u8 nAux; /* # of auxiliary columns in %_rowid */

u8 nAuxNotNull; /* Number of initial not-null aux columns */

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

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

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

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

i64 nRowEst; /* Estimated number of rows in this table */

u32 nCursor; /* Number of open cursors */

u32 nNodeRef; /* Number RtreeNodes with positive nRef */

char *zReadAuxSql; /* SQL for statement to read aux data */

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

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

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

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

*/

RtreeNode *pDeleted;

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

/* Blob I/O on xxx_node */

sqlite3_blob *pNodeBlob;

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

sqlite3_stmt *pWriteNode;

sqlite3_stmt *pDeleteNode;

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

sqlite3_stmt *pReadRowid;

sqlite3_stmt *pWriteRowid;

sqlite3_stmt *pDeleteRowid;

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

sqlite3_stmt *pReadParent;

sqlite3_stmt *pWriteParent;

sqlite3_stmt *pDeleteParent;

/* Statement for writing to the "aux:" fields, if there are any */

sqlite3_stmt *pWriteAux;

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

};

/* Possible values for Rtree.eCoordType: */

#define RTREE_COORD_REAL32 0

#define RTREE_COORD_INT32 1

/*

** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will

** only deal with integer coordinates. No floating point operations

** will be done.

*/

#ifdef SQLITE_RTREE_INT_ONLY

typedef sqlite3_int64 RtreeDValue; /* High accuracy coordinate */

typedef int RtreeValue; /* Low accuracy coordinate */

# define RTREE_ZERO 0

#else

typedef double RtreeDValue; /* High accuracy coordinate */

typedef float RtreeValue; /* Low accuracy coordinate */

# define RTREE_ZERO 0.0

#endif

/*

** When doing a search of an r-tree, instances of the following structure

** record intermediate results from the tree walk.

**

** The id is always a node-id. For iLevel>=1 the id is the node-id of

** the node that the RtreeSearchPoint represents. When iLevel==0, however,

** the id is of the parent node and the cell that RtreeSearchPoint

** represents is the iCell-th entry in the parent node.

*/

struct RtreeSearchPoint {

RtreeDValue rScore; /* The score for this node. Smallest goes first. */

sqlite3_int64 id; /* Node ID */

u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */

u8 eWithin; /* PARTLY_WITHIN or FULLY_WITHIN */

u8 iCell; /* Cell index within the node */

};

/*

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

** maximum. In Gutman's notation:

**

** m = M/3

**

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

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

*/

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

#define RTREE_REINSERT(p) RTREE_MINCELLS(p)

#define RTREE_MAXCELLS 51

/*

** The smallest possible node-size is (512-64)==448 bytes. And the largest

** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).

** Therefore all non-root nodes must contain at least 3 entries. Since

** 3^40 is greater than 2^64, an r-tree structure always has a depth of

** 40 or less.

*/

#define RTREE_MAX_DEPTH 40

/*

** Number of entries in the cursor RtreeNode cache. The first entry is

** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining

** entries cache the RtreeNode for the first elements of the priority queue.

*/

#define RTREE_CACHE_SZ 5

/*

** An rtree cursor object.

*/

struct RtreeCursor {

sqlite3_vtab_cursor base; /* Base class. Must be first */

u8 atEOF; /* True if at end of search */

u8 bPoint; /* True if sPoint is valid */

u8 bAuxValid; /* True if pReadAux is valid */

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

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

RtreeConstraint *aConstraint; /* Search constraints. */

int nPointAlloc; /* Number of slots allocated for aPoint[] */

int nPoint; /* Number of slots used in aPoint[] */

int mxLevel; /* iLevel value for root of the tree */

RtreeSearchPoint *aPoint; /* Priority queue for search points */

sqlite3_stmt *pReadAux; /* Statement to read aux-data */

RtreeSearchPoint sPoint; /* Cached next search point */

RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */

u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */

};

/* Return the Rtree of a RtreeCursor */

#define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab))

/*

** A coordinate can be either a floating point number or a integer. All

** coordinates within a single R-Tree are always of the same time.

*/

union RtreeCoord {

RtreeValue f; /* Floating point value */

int i; /* Integer value */

u32 u; /* Unsigned for byte-order conversions */

};

/*

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

** formatted as a RtreeDValue (double or int64). This macro assumes that local

** variable pRtree points to the Rtree structure associated with the

** RtreeCoord.

*/

#ifdef SQLITE_RTREE_INT_ONLY

# define DCOORD(coord) ((RtreeDValue)coord.i)

#else

# define DCOORD(coord) ( \

(pRtree->eCoordType==RTREE_COORD_REAL32) ? \

((double)coord.f) : \

((double)coord.i) \

)

#endif

/*

** A search constraint.

*/

struct RtreeConstraint {

int iCoord; /* Index of constrained coordinate */

int op; /* Constraining operation */

union {

RtreeDValue rValue; /* Constraint value. */

int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);

int (*xQueryFunc)(sqlite3_rtree_query_info*);

} u;

sqlite3_rtree_query_info *pInfo; /* xGeom and xQueryFunc argument */

};

/* Possible values for RtreeConstraint.op */

#define RTREE_EQ 0x41 /* A */

#define RTREE_LE 0x42 /* B */

#define RTREE_LT 0x43 /* C */

#define RTREE_GE 0x44 /* D */

#define RTREE_GT 0x45 /* E */

#define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */

#define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */

/*

** An rtree structure node.

*/

struct RtreeNode {

RtreeNode *pParent; /* Parent node */

i64 iNode; /* The node number */

int nRef; /* Number of references to this node */

int isDirty; /* True if the node needs to be written to disk */

u8 *zData; /* Content of the node, as should be on disk */

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

};

/* Return the number of cells in a node */

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

/*

** A single cell from a node, deserialized

*/

struct RtreeCell {

i64 iRowid; /* Node or entry ID */

RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */

};

/*

** This object becomes the sqlite3_user_data() for the SQL functions

** that are created by sqlite3_rtree_geometry_callback() and

** sqlite3_rtree_query_callback() and which appear on the right of MATCH

** operators in order to constrain a search.

**

** xGeom and xQueryFunc are the callback functions. Exactly one of

** xGeom and xQueryFunc fields is non-NULL, depending on whether the

** SQL function was created using sqlite3_rtree_geometry_callback() or

** sqlite3_rtree_query_callback().

**

** This object is deleted automatically by the destructor mechanism in

** sqlite3_create_function_v2().

*/

struct RtreeGeomCallback {

int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);

int (*xQueryFunc)(sqlite3_rtree_query_info*);

void (*xDestructor)(void*);

void *pContext;

};

/*

** An instance of this structure (in the form of a BLOB) is returned by

** the SQL functions that sqlite3_rtree_geometry_callback() and

** sqlite3_rtree_query_callback() create, and is read as the right-hand

** operand to the MATCH operator of an R-Tree.

*/

struct RtreeMatchArg {

u32 iSize; /* Size of this object */

RtreeGeomCallback cb; /* Info about the callback functions */

int nParam; /* Number of parameters to the SQL function */

sqlite3_value **apSqlParam; /* Original SQL parameter values */

RtreeDValue aParam[1]; /* Values for parameters to the SQL function */

};

#ifndef MAX

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

#endif

#ifndef MIN

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

#endif

/* What version of GCC is being used. 0 means GCC is not being used .

** Note that the GCC_VERSION macro will also be set correctly when using

** clang, since clang works hard to be gcc compatible. So the gcc

** optimizations will also work when compiling with clang.

*/

#ifndef GCC_VERSION

#if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)

# define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)

#else

# define GCC_VERSION 0

#endif

#endif

/* The testcase() macro should already be defined in the amalgamation. If

** it is not, make it a no-op.

*/

#ifndef SQLITE_AMALGAMATION

# define testcase(X)

#endif

/*

** Macros to determine whether the machine is big or little endian,

** and whether or not that determination is run-time or compile-time.

**

** For best performance, an attempt is made to guess at the byte-order

** using C-preprocessor macros. If that is unsuccessful, or if

** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined

** at run-time.

*/

#ifndef SQLITE_BYTEORDER

#if defined(i386) || defined(__i386__) || defined(_M_IX86) || \

defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \

defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \

defined(__arm__)

# define SQLITE_BYTEORDER 1234

#elif defined(sparc) || defined(__ppc__)

# define SQLITE_BYTEORDER 4321

#else

# define SQLITE_BYTEORDER 0 /* 0 means "unknown at compile-time" */

#endif

#endif

/* What version of MSVC is being used. 0 means MSVC is not being used */

#ifndef MSVC_VERSION

#if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)

# define MSVC_VERSION _MSC_VER

#else

# define MSVC_VERSION 0

#endif

#endif

/*

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

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

*/

static int readInt16(u8 *p){

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

}

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

assert( ((((char*)p) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */

#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300

pCoord->u = _byteswap_ulong(*(u32*)p);

#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000

pCoord->u = __builtin_bswap32(*(u32*)p);

#elif SQLITE_BYTEORDER==4321

pCoord->u = *(u32*)p;

#else

pCoord->u = (

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

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

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

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

);

#endif

}

static i64 readInt64(u8 *p){

#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300

u64 x;

memcpy(&x, p, 8);

return (i64)_byteswap_uint64(x);

#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000

u64 x;

memcpy(&x, p, 8);

return (i64)__builtin_bswap64(x);

#elif SQLITE_BYTEORDER==4321

i64 x;

memcpy(&x, p, 8);

return x;

#else

return (i64)(

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

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

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

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

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

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

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

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

);

#endif

}

/*

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

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

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

*/

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

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

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

}

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

u32 i;

assert( ((((char*)p) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */

assert( sizeof(RtreeCoord)==4 );

assert( sizeof(u32)==4 );

#if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000

i = __builtin_bswap32(pCoord->u);

memcpy(p, &i, 4);

#elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300

i = _byteswap_ulong(pCoord->u);

memcpy(p, &i, 4);

#elif SQLITE_BYTEORDER==4321

i = pCoord->u;

memcpy(p, &i, 4);

#else

i = pCoord->u;

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

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

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

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

#endif

return 4;

}

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

#if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000

i = (i64)__builtin_bswap64((u64)i);

memcpy(p, &i, 8);

#elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300

i = (i64)_byteswap_uint64((u64)i);

memcpy(p, &i, 8);

#elif SQLITE_BYTEORDER==4321

memcpy(p, &i, 8);

#else

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

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

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

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

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

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

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

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

#endif

return 8;

}

/*

** Increment the reference count of node p.

*/

static void nodeReference(RtreeNode *p){

if( p ){

assert( p->nRef>0 );

p->nRef++;

}

}

/*

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

*/

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

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

p->isDirty = 1;

}

/*

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

** in the Rtree.aHash table.

*/

static int nodeHash(i64 iNode){

return iNode % HASHSIZE;

}

/*

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

** to it. Otherwise, return 0.

*/

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

RtreeNode *p;

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

return p;

}

/*

** Add node pNode to the node hash table.

*/

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

int iHash;

assert( pNode->pNext==0 );

iHash = nodeHash(pNode->iNode);

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

pRtree->aHash[iHash] = pNode;

}

/*

** Remove node pNode from the node hash table.

*/

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

RtreeNode **pp;

if( pNode->iNode!=0 ){

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

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

*pp = pNode->pNext;

pNode->pNext = 0;

}

}

/*

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

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

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

** node contents out to the database.

*/

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

RtreeNode *pNode;

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

if( pNode ){

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

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

pNode->nRef = 1;

pRtree->nNodeRef++;

pNode->pParent = pParent;

pNode->isDirty = 1;

nodeReference(pParent);

}

return pNode;

}

/*

** Clear the Rtree.pNodeBlob object

*/

static void nodeBlobReset(Rtree *pRtree){

if( pRtree->pNodeBlob && pRtree->inWrTrans==0 && pRtree->nCursor==0 ){

sqlite3_blob *pBlob = pRtree->pNodeBlob;

pRtree->pNodeBlob = 0;

sqlite3_blob_close(pBlob);

}

}

/*

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

*/

static int nodeAcquire(

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

i64 iNode, /* Node number to load */

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

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

){

int rc = SQLITE_OK;

RtreeNode *pNode = 0;

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

** increase its reference count and return it.

*/

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

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

if( pParent && !pNode->pParent ){

pParent->nRef++;

pNode->pParent = pParent;

}

pNode->nRef++;

*ppNode = pNode;

return SQLITE_OK;

}

if( pRtree->pNodeBlob ){

sqlite3_blob *pBlob = pRtree->pNodeBlob;

pRtree->pNodeBlob = 0;

rc = sqlite3_blob_reopen(pBlob, iNode);

pRtree->pNodeBlob = pBlob;

if( rc ){

nodeBlobReset(pRtree);

if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM;

}

}

if( pRtree->pNodeBlob==0 ){

char *zTab = sqlite3_mprintf("%s_node", pRtree->zName);

if( zTab==0 ) return SQLITE_NOMEM;

rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, zTab, "data", iNode, 0,

&pRtree->pNodeBlob);

sqlite3_free(zTab);

}

if( rc ){

nodeBlobReset(pRtree);

*ppNode = 0;

/* If unable to open an sqlite3_blob on the desired row, that can only

** be because the shadow tables hold erroneous data. */

if( rc==SQLITE_ERROR ) rc = SQLITE_CORRUPT_VTAB;

}else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){

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

if( !pNode ){

rc = SQLITE_NOMEM;

}else{

pNode->pParent = pParent;

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

pNode->nRef = 1;

pRtree->nNodeRef++;

pNode->iNode = iNode;

pNode->isDirty = 0;

pNode->pNext = 0;

rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData,

pRtree->iNodeSize, 0);

nodeReference(pParent);

}

}

/* If the root node was just loaded, set pRtree->iDepth to the height

** of the r-tree structure. A height of zero means all data is stored on

** the root node. A height of one means the children of the root node

** are the leaves, and so on. If the depth as specified on the root node

** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.

*/

if( pNode && iNode==1 ){

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

if( pRtree->iDepth>RTREE_MAX_DEPTH ){

rc = SQLITE_CORRUPT_VTAB;

}

}

/* If no error has occurred so far, check if the "number of entries"

** field on the node is too large. If so, set the return code to

** SQLITE_CORRUPT_VTAB.

*/

if( pNode && rc==SQLITE_OK ){

if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){

rc = SQLITE_CORRUPT_VTAB;

}

}

if( rc==SQLITE_OK ){

if( pNode!=0 ){

nodeHashInsert(pRtree, pNode);

}else{

rc = SQLITE_CORRUPT_VTAB;

}

*ppNode = pNode;

}else{

if( pNode ){

pRtree->nNodeRef--;

sqlite3_free(pNode);

}

*ppNode = 0;

}

return rc;

}

/*

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

*/

static void nodeOverwriteCell(

Rtree *pRtree, /* The overall R-Tree */

RtreeNode *pNode, /* The node into which the cell is to be written */

RtreeCell *pCell, /* The cell to write */

int iCell /* Index into pNode into which pCell is written */

){

int ii;

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

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

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

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

}

pNode->isDirty = 1;

}

/*

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

*/

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

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

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

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

memmove(pDst, pSrc, nByte);

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

pNode->isDirty = 1;

}

/*

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

** is successful, return SQLITE_OK.

**

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

*/

static int nodeInsertCell(

Rtree *pRtree, /* The overall R-Tree */

RtreeNode *pNode, /* Write new cell into this node */

RtreeCell *pCell /* The cell to be inserted */

){

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

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

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

nCell = NCELL(pNode);

assert( nCell<=nMaxCell );

if( nCell<nMaxCell ){

nodeOverwriteCell(pRtree, pNode, pCell, nCell);

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

pNode->isDirty = 1;

}

return (nCell==nMaxCell);

}

/*

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

*/

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

int rc = SQLITE_OK;

if( pNode->isDirty ){

sqlite3_stmt *p = pRtree->pWriteNode;

if( pNode->iNode ){

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

}else{

sqlite3_bind_null(p, 1);

}

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

sqlite3_step(p);

pNode->isDirty = 0;

rc = sqlite3_reset(p);

sqlite3_bind_null(p, 2);

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

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

nodeHashInsert(pRtree, pNode);

}

}

return rc;

}

/*

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

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

*/

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

int rc = SQLITE_OK;

if( pNode ){

assert( pNode->nRef>0 );

assert( pRtree->nNodeRef>0 );

pNode->nRef--;

if( pNode->nRef==0 ){

pRtree->nNodeRef--;

if( pNode->iNode==1 ){

pRtree->iDepth = -1;

}

if( pNode->pParent ){

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

}

if( rc==SQLITE_OK ){

rc = nodeWrite(pRtree, pNode);

}

nodeHashDelete(pRtree, pNode);

sqlite3_free(pNode);

}

}

return rc;

}

/*

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

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

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

*/

static i64 nodeGetRowid(

Rtree *pRtree, /* The overall R-Tree */

RtreeNode *pNode, /* The node from which to extract the ID */

int iCell /* The cell index from which to extract the ID */

){

assert( iCell<NCELL(pNode) );

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

}

/*

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

*/

static void nodeGetCoord(

Rtree *pRtree, /* The overall R-Tree */

RtreeNode *pNode, /* The node from which to extract a coordinate */

int iCell, /* The index of the cell within the node */

int iCoord, /* Which coordinate to extract */

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

){

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

}

/*

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

** to by pCell with the results.

*/

static void nodeGetCell(

Rtree *pRtree, /* The overall R-Tree */

RtreeNode *pNode, /* The node containing the cell to be read */

int iCell, /* Index of the cell within the node */

RtreeCell *pCell /* OUT: Write the cell contents here */

){

u8 *pData;

RtreeCoord *pCoord;

int ii = 0;

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

pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);

pCoord = pCell->aCoord;

do{

readCoord(pData, &pCoord[ii]);

readCoord(pData+4, &pCoord[ii+1]);

pData += 8;

ii += 2;

}while( ii<pRtree->nDim2 );

}

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

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

*/

static int rtreeInit(

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

);

/*

** Rtree virtual table module xCreate method.

*/

static int rtreeCreate(

sqlite3 *db,

void *pAux,

int argc, const char *const*argv,

sqlite3_vtab **ppVtab,

char **pzErr

){

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

}

/*

** Rtree virtual table module xConnect method.

*/

static int rtreeConnect(

sqlite3 *db,

void *pAux,

int argc, const char *const*argv,

sqlite3_vtab **ppVtab,

char **pzErr

){

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

}

/*

** Increment the r-tree reference count.

*/

static void rtreeReference(Rtree *pRtree){

pRtree->nBusy++;

}

/*

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

** zero the structure is deleted.

*/

static void rtreeRelease(Rtree *pRtree){

pRtree->nBusy--;

if( pRtree->nBusy==0 ){

pRtree->inWrTrans = 0;

assert( pRtree->nCursor==0 );

nodeBlobReset(pRtree);

assert( pRtree->nNodeRef==0 );

sqlite3_finalize(pRtree->pWriteNode);

sqlite3_finalize(pRtree->pDeleteNode);

sqlite3_finalize(pRtree->pReadRowid);

sqlite3_finalize(pRtree->pWriteRowid);

sqlite3_finalize(pRtree->pDeleteRowid);

sqlite3_finalize(pRtree->pReadParent);

sqlite3_finalize(pRtree->pWriteParent);

sqlite3_finalize(pRtree->pDeleteParent);

sqlite3_finalize(pRtree->pWriteAux);

sqlite3_free(pRtree->zReadAuxSql);

sqlite3_free(pRtree);

}

}

/*

** Rtree virtual table module xDisconnect method.

*/

static int rtreeDisconnect(sqlite3_vtab *pVtab){

rtreeRelease((Rtree *)pVtab);

return SQLITE_OK;

}

/*

** Rtree virtual table module xDestroy method.

*/

static int rtreeDestroy(sqlite3_vtab *pVtab){

Rtree *pRtree = (Rtree *)pVtab;

int rc;

char *zCreate = sqlite3_mprintf(

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

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

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

pRtree->zDb, pRtree->zName,

pRtree->zDb, pRtree->zName,

pRtree->zDb, pRtree->zName

);

if( !zCreate ){

rc = SQLITE_NOMEM;

}else{

nodeBlobReset(pRtree);

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

sqlite3_free(zCreate);

}

if( rc==SQLITE_OK ){

rtreeRelease(pRtree);

}

return rc;

}

/*

** Rtree virtual table module xOpen method.

*/

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