/*

** 2001 September 15

**

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

** a legal notice, here is a blessing:

**

** May you do good and not evil.

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

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

**

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

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

** algorithms packaged as an SQLite virtual table module.

*/

/*

** Database Format of R-Tree Tables

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

**

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

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

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

** table.

**

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

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

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

**

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

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

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

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

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

** is stored on.

**

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

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

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

** is formatted as follows:

**

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

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

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

**

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

** stored in the node.

**

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

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

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

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

** child page.

*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*

** This file contains an implementation of a couple of different variants

** of the r-tree algorithm. See the README file for further details. The

** same data-structure is used for all, but the algorithms for insert and

** delete operations vary. The variants used are selected at compile time

** by defining the following symbols:

*/

/* Either, both or none of the following may be set to activate

** r*tree variant algorithms.

*/

#define VARIANT_RSTARTREE_CHOOSESUBTREE 0

#define VARIANT_RSTARTREE_REINSERT 1

/*

** Exactly one of the following must be set to 1.

*/

#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0

#define VARIANT_GUTTMAN_LINEAR_SPLIT 0

#define VARIANT_RSTARTREE_SPLIT 1

#define VARIANT_GUTTMAN_SPLIT \

(VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)

#if VARIANT_GUTTMAN_QUADRATIC_SPLIT

#define PickNext QuadraticPickNext

#define PickSeeds QuadraticPickSeeds

#define AssignCells splitNodeGuttman

#endif

#if VARIANT_GUTTMAN_LINEAR_SPLIT

#define PickNext LinearPickNext

#define PickSeeds LinearPickSeeds

#define AssignCells splitNodeGuttman

#endif

#if VARIANT_RSTARTREE_SPLIT

#define AssignCells splitNodeStartree

#endif

#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)

# define NDEBUG 1

#endif

#ifndef SQLITE_CORE

#include "sqlite3ext.h"

SQLITE_EXTENSION_INIT1

#else

#include "sqlite3.h"

#endif

#include <string.h>

#include <assert.h>

#ifndef SQLITE_AMALGAMATION

#include "sqlite3rtree.h"

typedef sqlite3_int64 i64;

typedef unsigned char u8;

typedef unsigned int u32;

#endif

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

*/

#ifndef UNUSED_PARAMETER

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

#endif

typedef struct Rtree Rtree;

typedef struct RtreeCursor RtreeCursor;

typedef struct RtreeNode RtreeNode;

typedef struct RtreeCell RtreeCell;

typedef struct RtreeConstraint RtreeConstraint;

typedef struct RtreeMatchArg RtreeMatchArg;

typedef struct RtreeGeomCallback RtreeGeomCallback;

typedef union RtreeCoord RtreeCoord;

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

#define RTREE_MAX_DIMENSIONS 5

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

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

** used.

*/

#define HASHSIZE 128

/*

** An rtree virtual-table object.

*/

struct Rtree {

sqlite3_vtab base;

sqlite3 *db; /* Host database connection */

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

int nDim; /* Number of dimensions */

int nBytesPerCell; /* Bytes consumed per cell */

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

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

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

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

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

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

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

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

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

*/

RtreeNode *pDeleted;

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

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

sqlite3_stmt *pReadNode;

sqlite3_stmt *pWriteNode;

sqlite3_stmt *pDeleteNode;

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

sqlite3_stmt *pReadRowid;

sqlite3_stmt *pWriteRowid;

sqlite3_stmt *pDeleteRowid;

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

sqlite3_stmt *pReadParent;

sqlite3_stmt *pWriteParent;

sqlite3_stmt *pDeleteParent;

int eCoordType;

};

/* Possible values for eCoordType: */

#define RTREE_COORD_REAL32 0

#define RTREE_COORD_INT32 1

/*

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

** maximum. In Gutman's notation:

**

** m = M/3

**

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

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

*/

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

#define RTREE_REINSERT(p) RTREE_MINCELLS(p)

#define RTREE_MAXCELLS 51

/*

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

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

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

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

** 40 or less.

*/

#define RTREE_MAX_DEPTH 40

/*

** An rtree cursor object.

*/

struct RtreeCursor {

sqlite3_vtab_cursor base;

RtreeNode *pNode; /* Node cursor is currently pointing at */

int iCell; /* Index of current cell in pNode */

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

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

RtreeConstraint *aConstraint; /* Search constraints. */

};

union RtreeCoord {

float f;

int i;

};

/*

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

** formatted as a double. This macro assumes that local variable pRtree points

** to the Rtree structure associated with the RtreeCoord.

*/

#define DCOORD(coord) ( \

(pRtree->eCoordType==RTREE_COORD_REAL32) ? \

((double)coord.f) : \

((double)coord.i) \

)

/*

** A search constraint.

*/

struct RtreeConstraint {

int iCoord; /* Index of constrained coordinate */

int op; /* Constraining operation */

double rValue; /* Constraint value. */

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

sqlite3_rtree_geometry *pGeom; /* Constraint callback argument for a MATCH */

};

/* Possible values for RtreeConstraint.op */

#define RTREE_EQ 0x41

#define RTREE_LE 0x42

#define RTREE_LT 0x43

#define RTREE_GE 0x44

#define RTREE_GT 0x45

#define RTREE_MATCH 0x46

/*

** An rtree structure node.

*/

struct RtreeNode {

RtreeNode *pParent; /* Parent node */

i64 iNode;

int nRef;

int isDirty;

u8 *zData;

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

};

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

/*

** Structure to store a deserialized rtree record.

*/

struct RtreeCell {

i64 iRowid;

RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];

};

/*

** Value for the first field of every RtreeMatchArg object. The MATCH

** operator tests that the first field of a blob operand matches this

** value to avoid operating on invalid blobs (which could cause a segfault).

*/

#define RTREE_GEOMETRY_MAGIC 0x891245AB

/*

** An instance of this structure must be supplied as a blob argument to

** the right-hand-side of an SQL MATCH operator used to constrain an

** r-tree query.

*/

struct RtreeMatchArg {

u32 magic; /* Always RTREE_GEOMETRY_MAGIC */

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

void *pContext;

int nParam;

double aParam[1];

};

/*

** When a geometry callback is created (see sqlite3_rtree_geometry_callback),

** a single instance of the following structure is allocated. It is used

** as the context for the user-function created by by s_r_g_c(). The object

** is eventually deleted by the destructor mechanism provided by

** sqlite3_create_function_v2() (which is called by s_r_g_c() to create

** the geometry callback function).

*/

struct RtreeGeomCallback {

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

void *pContext;

};

#ifndef MAX

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

#endif

#ifndef MIN

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

#endif

/*

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

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

*/

static int readInt16(u8 *p){

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

}

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

u32 i = (

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

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

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

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

);

*(u32 *)pCoord = i;

}

static i64 readInt64(u8 *p){

return (

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

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

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

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

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

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

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

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

);

}

/*

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

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

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

*/

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

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

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

return 2;

}

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

u32 i;

assert( sizeof(RtreeCoord)==4 );

assert( sizeof(u32)==4 );

i = *(u32 *)pCoord;

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

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

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

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

return 4;

}

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

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

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

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

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

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

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

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

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

return 8;

}

/*

** Increment the reference count of node p.

*/

static void nodeReference(RtreeNode *p){

if( p ){

p->nRef++;

}

}

/*

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

*/

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

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

p->isDirty = 1;

}

/*

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

** in the Rtree.aHash table.

*/

static int nodeHash(i64 iNode){

return (

(iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^

(iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)

) % HASHSIZE;

}

/*

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

** to it. Otherwise, return 0.

*/

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

RtreeNode *p;

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

return p;

}

/*

** Add node pNode to the node hash table.

*/

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

int iHash;

assert( pNode->pNext==0 );

iHash = nodeHash(pNode->iNode);

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

pRtree->aHash[iHash] = pNode;

}

/*

** Remove node pNode from the node hash table.

*/

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

RtreeNode **pp;

if( pNode->iNode!=0 ){

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

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

*pp = pNode->pNext;

pNode->pNext = 0;

}

}

/*

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

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

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

** node contents out to the database.

*/

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

RtreeNode *pNode;

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

if( pNode ){

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

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

pNode->nRef = 1;

pNode->pParent = pParent;

pNode->isDirty = 1;

nodeReference(pParent);

}

return pNode;

}

/*

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

*/

static int

nodeAcquire(

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

i64 iNode, /* Node number to load */

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

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

){

int rc;

int rc2 = SQLITE_OK;

RtreeNode *pNode;

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

** increase its reference count and return it.

*/

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

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

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

nodeReference(pParent);

pNode->pParent = pParent;

}

pNode->nRef++;

*ppNode = pNode;

return SQLITE_OK;

}

sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);

rc = sqlite3_step(pRtree->pReadNode);

if( rc==SQLITE_ROW ){

const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);

if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){

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

if( !pNode ){

rc2 = SQLITE_NOMEM;

}else{

pNode->pParent = pParent;

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

pNode->nRef = 1;

pNode->iNode = iNode;

pNode->isDirty = 0;

pNode->pNext = 0;

memcpy(pNode->zData, zBlob, pRtree->iNodeSize);

nodeReference(pParent);

}

}

}

rc = sqlite3_reset(pRtree->pReadNode);

if( rc==SQLITE_OK ) rc = rc2;

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

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

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

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

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

*/

if( pNode && iNode==1 ){

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

if( pRtree->iDepth>RTREE_MAX_DEPTH ){

rc = SQLITE_CORRUPT_VTAB;

}

}

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

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

** SQLITE_CORRUPT_VTAB.

*/

if( pNode && rc==SQLITE_OK ){

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

rc = SQLITE_CORRUPT_VTAB;

}

}

if( rc==SQLITE_OK ){

if( pNode!=0 ){

nodeHashInsert(pRtree, pNode);

}else{

rc = SQLITE_CORRUPT_VTAB;

}

*ppNode = pNode;

}else{

sqlite3_free(pNode);

*ppNode = 0;

}

return rc;

}

/*

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

*/

static void nodeOverwriteCell(

Rtree *pRtree,

RtreeNode *pNode,

RtreeCell *pCell,

int iCell

){

int ii;

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

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

for(ii=0; ii<(pRtree->nDim*2); ii++){

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

}

pNode->isDirty = 1;

}

/*

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

*/

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

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

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

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

memmove(pDst, pSrc, nByte);

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

pNode->isDirty = 1;

}

/*

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

** is successful, return SQLITE_OK.

**

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

*/

static int

nodeInsertCell(

Rtree *pRtree,

RtreeNode *pNode,

RtreeCell *pCell

){

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

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

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

nCell = NCELL(pNode);

assert( nCell<=nMaxCell );

if( nCell<nMaxCell ){

nodeOverwriteCell(pRtree, pNode, pCell, nCell);

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

pNode->isDirty = 1;

}

return (nCell==nMaxCell);

}

/*

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

*/

static int

nodeWrite(Rtree *pRtree, RtreeNode *pNode){

int rc = SQLITE_OK;

if( pNode->isDirty ){

sqlite3_stmt *p = pRtree->pWriteNode;

if( pNode->iNode ){

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

}else{

sqlite3_bind_null(p, 1);

}

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

sqlite3_step(p);

pNode->isDirty = 0;

rc = sqlite3_reset(p);

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

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

nodeHashInsert(pRtree, pNode);

}

}

return rc;

}

/*

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

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

*/

static int

nodeRelease(Rtree *pRtree, RtreeNode *pNode){

int rc = SQLITE_OK;

if( pNode ){

assert( pNode->nRef>0 );

pNode->nRef--;

if( pNode->nRef==0 ){

if( pNode->iNode==1 ){

pRtree->iDepth = -1;

}

if( pNode->pParent ){

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

}

if( rc==SQLITE_OK ){

rc = nodeWrite(pRtree, pNode);

}

nodeHashDelete(pRtree, pNode);

sqlite3_free(pNode);

}

}

return rc;

}

/*

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

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

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

*/

static i64 nodeGetRowid(

Rtree *pRtree,

RtreeNode *pNode,

int iCell

){

assert( iCell<NCELL(pNode) );

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

}

/*

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

*/

static void nodeGetCoord(

Rtree *pRtree,

RtreeNode *pNode,

int iCell,

int iCoord,

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

){

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

}

/*

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

** to by pCell with the results.

*/

static void nodeGetCell(

Rtree *pRtree,

RtreeNode *pNode,

int iCell,

RtreeCell *pCell

){

int ii;

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

for(ii=0; ii<pRtree->nDim*2; ii++){

nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);

}

}

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

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

*/

static int rtreeInit(

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

);

/*

** Rtree virtual table module xCreate method.

*/

static int rtreeCreate(

sqlite3 *db,

void *pAux,

int argc, const char *const*argv,

sqlite3_vtab **ppVtab,

char **pzErr

){

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

}

/*

** Rtree virtual table module xConnect method.

*/

static int rtreeConnect(

sqlite3 *db,

void *pAux,

int argc, const char *const*argv,

sqlite3_vtab **ppVtab,

char **pzErr

){

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

}

/*

** Increment the r-tree reference count.

*/

static void rtreeReference(Rtree *pRtree){

pRtree->nBusy++;

}

/*

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

** zero the structure is deleted.

*/

static void rtreeRelease(Rtree *pRtree){

pRtree->nBusy--;

if( pRtree->nBusy==0 ){

sqlite3_finalize(pRtree->pReadNode);

sqlite3_finalize(pRtree->pWriteNode);

sqlite3_finalize(pRtree->pDeleteNode);

sqlite3_finalize(pRtree->pReadRowid);

sqlite3_finalize(pRtree->pWriteRowid);

sqlite3_finalize(pRtree->pDeleteRowid);

sqlite3_finalize(pRtree->pReadParent);

sqlite3_finalize(pRtree->pWriteParent);

sqlite3_finalize(pRtree->pDeleteParent);

sqlite3_free(pRtree);

}

}

/*

** Rtree virtual table module xDisconnect method.

*/

static int rtreeDisconnect(sqlite3_vtab *pVtab){

rtreeRelease((Rtree *)pVtab);

return SQLITE_OK;

}

/*

** Rtree virtual table module xDestroy method.

*/

static int rtreeDestroy(sqlite3_vtab *pVtab){

Rtree *pRtree = (Rtree *)pVtab;

int rc;

char *zCreate = sqlite3_mprintf(

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

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

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

pRtree->zDb, pRtree->zName,

pRtree->zDb, pRtree->zName,

pRtree->zDb, pRtree->zName

);

if( !zCreate ){

rc = SQLITE_NOMEM;

}else{

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

sqlite3_free(zCreate);

}

if( rc==SQLITE_OK ){

rtreeRelease(pRtree);

}

return rc;

}

/*

** Rtree virtual table module xOpen method.

*/

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

int rc = SQLITE_NOMEM;

RtreeCursor *pCsr;

pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));

if( pCsr ){

memset(pCsr, 0, sizeof(RtreeCursor));

pCsr->base.pVtab = pVTab;

rc = SQLITE_OK;

}

*ppCursor = (sqlite3_vtab_cursor *)pCsr;

return rc;

}

/*

** Free the RtreeCursor.aConstraint[] array and its contents.

*/

static void freeCursorConstraints(RtreeCursor *pCsr){

if( pCsr->aConstraint ){

int i; /* Used to iterate through constraint array */

for(i=0; i<pCsr->nConstraint; i++){

sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;

if( pGeom ){

if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);

sqlite3_free(pGeom);

}

}

sqlite3_free(pCsr->aConstraint);

pCsr->aConstraint = 0;

}

}

/*

** Rtree virtual table module xClose method.

*/

static int rtreeClose(sqlite3_vtab_cursor *cur){

Rtree *pRtree = (Rtree *)(cur->pVtab);

int rc;

RtreeCursor *pCsr = (RtreeCursor *)cur;

freeCursorConstraints(pCsr);

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

sqlite3_free(pCsr);

return rc;

}

/*

** Rtree virtual table module xEof method.

**

** Return non-zero if the cursor does not currently point to a valid

** record (i.e if the scan has finished), or zero otherwise.

*/

static int rtreeEof(sqlite3_vtab_cursor *cur){

RtreeCursor *pCsr = (RtreeCursor *)cur;

return (pCsr->pNode==0);

}

/*

** The r-tree constraint passed as the second argument to this function is

** guaranteed to be a MATCH constraint.

*/

static int testRtreeGeom(

Rtree *pRtree, /* R-Tree object */

RtreeConstraint *pConstraint, /* MATCH constraint to test */

RtreeCell *pCell, /* Cell to test */

int *pbRes /* OUT: Test result */

){

int i;

double aCoord[RTREE_MAX_DIMENSIONS*2];

int nCoord = pRtree->nDim*2;

assert( pConstraint->op==RTREE_MATCH );

assert( pConstraint->pGeom );

for(i=0; i<nCoord; i++){

aCoord[i] = DCOORD(pCell->aCoord[i]);

}

return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);

}

/*

** Cursor pCursor currently points to a cell in a non-leaf page.

** Set *pbEof to true if the sub-tree headed by the cell is filtered

** (excluded) by the constraints in the pCursor->aConstraint[]

** array, or false otherwise.

**

** Return SQLITE_OK if successful or an SQLite error code if an error

** occurs within a geometry callback.

*/

static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){

RtreeCell cell;

int ii;

int bRes = 0;

int rc = SQLITE_OK;

nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);

for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){

RtreeConstraint *p = &pCursor->aConstraint[ii];

double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);

double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);

assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE

|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH

);

switch( p->op ){

case RTREE_LE: case RTREE_LT:

bRes = p->rValue<cell_min;

break;

case RTREE_GE: case RTREE_GT:

bRes = p->rValue>cell_max;

break;

case RTREE_EQ:

bRes = (p->rValue>cell_max || p->rValue<cell_min);

break;

default: {

assert( p->op==RTREE_MATCH );

rc = testRtreeGeom(pRtree, p, &cell, &bRes);

bRes = !bRes;

break;

}

}

}

*pbEof = bRes;

return rc;

}

/*

** Test if the cell that cursor pCursor currently points to

** would be filtered (excluded) by the constraints in the

** pCursor->aConstraint[] array. If so, set *pbEof to true before

** returning. If the cell is not filtered (excluded) by the constraints,

** set pbEof to zero.

**

** Return SQLITE_OK if successful or an SQLite error code if an error

** occurs within a geometry callback.

**

** This function assumes that the cell is part of a leaf node.

*/

static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){

RtreeCell cell;

int ii;

*pbEof = 0;

nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);

for(ii=0; ii<pCursor->nConstraint; ii++){

RtreeConstraint *p = &pCursor->aConstraint[ii];

double coord = DCOORD(cell.aCoord[p->iCoord]);

int res;

assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE

|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH

);

switch( p->op ){

case RTREE_LE: res = (coord<=p->rValue); break;

case RTREE_LT: res = (coord<p->rValue); break;

case RTREE_GE: res = (coord>=p->rValue); break;

case RTREE_GT: res = (coord>p->rValue); break;

case RTREE_EQ: res = (coord==p->rValue); break;

default: {

int rc;

assert( p->op==RTREE_MATCH );

rc = testRtreeGeom(pRtree, p, &cell, &res);

if( rc!=SQLITE_OK ){

return rc;

}

break;

}

}

if( !res ){

*pbEof = 1;

return SQLITE_OK;

}

}

return SQLITE_OK;

}

/*

** Cursor pCursor currently points at a node that heads a sub-tree of

** height iHeight (if iHeight==0, then the node is a leaf). Descend

** to point to the left-most cell of the sub-tree that matches the

** configured constraints.

*/

static int descendToCell(

Rtree *pRtree,

RtreeCursor *pCursor,

int iHeight,

int *pEof /* OUT: Set to true if cannot descend */

){

int isEof;

int rc;

int ii;

RtreeNode *pChild;