Google Git
Sign in
chromium / chromium / deps / sqlite / refs/tags/upstream/major-release / . / ext / rtree / rtree.c
blob: 8ed8978bdebf740b282a77cd4ae8d99dbac473d7 [file] [log] [blame]
/*
** 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
int sqlite3GetToken(const unsigned char*,int*); /* In the SQLite core */
/*
** If building separately, we will need some setup that is normally
** found in sqliteInt.h
*/
#if !defined(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;
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG)
# define NDEBUG 1
#endif
#if defined(NDEBUG) && defined(SQLITE_DEBUG)
# undef NDEBUG
#endif
#if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST)
# define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1
#endif
#if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
# define ALWAYS(X) (1)
# define NEVER(X) (0)
#elif !defined(NDEBUG)
# define ALWAYS(X) ((X)?1:(assert(0),0))
# define NEVER(X) ((X)?(assert(0),1):0)
#else
# define ALWAYS(X) (X)
# define NEVER(X) (X)
#endif
#endif /* !defined(SQLITE_AMALGAMATION) */
/* Macro to check for 4-byte alignment. Only used inside of assert() */
#ifdef SQLITE_DEBUG
# define FOUR_BYTE_ALIGNED(X) ((((char*)(X) - (char*)0) & 3)==0)
#endif
#include <string.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
/* 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 */
#ifdef SQLITE_ENABLE_GEOPOLY
u8 nAuxNotNull; /* Number of initial not-null aux columns */
#endif
#ifdef SQLITE_DEBUG
u8 bCorrupt; /* Shadow table corruption detected */
#endif
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 */
char *zNodeName; /* Name of the %_node 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;
/* 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
/*
** Set the Rtree.bCorrupt flag
*/
#ifdef SQLITE_DEBUG
# define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1)
#else
# define RTREE_IS_CORRUPT(X)
#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() */
/* Special operators available only on cursors. Needs to be consecutive
** with the normal values above, but must be less than RTREE_MATCH. These
** are used in the cursor for contraints such as x=NULL (RTREE_FALSE) or
** x<'xyz' (RTREE_TRUE) */
#define RTREE_TRUE 0x3f /* ? */
#define RTREE_FALSE 0x40 /* @ */
/*
** 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
# if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_DEBUG)
unsigned int sqlite3RtreeTestcase = 0;
# define testcase(X) if( X ){ sqlite3RtreeTestcase += __LINE__; }
# else
# define testcase(X)
# endif
#endif
/*
** Make sure that the compiler intrinsics we desire are enabled when
** compiling with an appropriate version of MSVC unless prevented by
** the SQLITE_DISABLE_INTRINSIC define.
*/
#if !defined(SQLITE_DISABLE_INTRINSIC)
# if defined(_MSC_VER) && _MSC_VER>=1400
# if !defined(_WIN32_WCE)
# include <intrin.h>
# pragma intrinsic(_byteswap_ulong)
# pragma intrinsic(_byteswap_uint64)
# else
# include <cmnintrin.h>
# endif
# endif
#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 /* Replicate changes at tag-20230904a */
# if defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_BIG_ENDIAN__
# define SQLITE_BYTEORDER 4321
# elif defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_LITTLE_ENDIAN__
# define SQLITE_BYTEORDER 1234
# elif defined(__BIG_ENDIAN__) && __BIG_ENDIAN__==1
# define SQLITE_BYTEORDER 4321
# elif 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(__ARMEL__) || defined(__AARCH64EL__) || defined(_M_ARM64)
# define SQLITE_BYTEORDER 1234
# elif defined(sparc) || defined(__ARMEB__) || defined(__AARCH64EB__)
# define SQLITE_BYTEORDER 4321
# else
# define SQLITE_BYTEORDER 0
# 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( FOUR_BYTE_ALIGNED(p) );
#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( FOUR_BYTE_ALIGNED(p) );
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 unsigned int nodeHash(i64 iNode){
return ((unsigned)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_malloc64(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){
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 ){
if( pParent && ALWAYS(pParent!=pNode->pParent) ){
RTREE_IS_CORRUPT(pRtree);
return SQLITE_CORRUPT_VTAB;
}
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 ){
rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, pRtree->zNodeName,
"data", iNode, 0,
&pRtree->pNodeBlob);
}
if( rc ){
*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;
RTREE_IS_CORRUPT(pRtree);
}
}else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){
pNode = (RtreeNode *)sqlite3_malloc64(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);
}
}
/* 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( rc==SQLITE_OK && pNode && iNode==1 ){
pRtree->iDepth = readInt16(pNode->zData);
if( pRtree->iDepth>RTREE_MAX_DEPTH ){
rc = SQLITE_CORRUPT_VTAB;
RTREE_IS_CORRUPT(pRtree);
}
}
/* 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;
RTREE_IS_CORRUPT(pRtree);
}
}
if( rc==SQLITE_OK ){
if( pNode!=0 ){
nodeReference(pParent);
nodeHashInsert(pRtree, pNode);
}else{
rc = SQLITE_CORRUPT_VTAB;
RTREE_IS_CORRUPT(pRtree);
}
*ppNode = pNode;
}else{
nodeBlobReset(pRtree);
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 */
){
assert( iCell<NCELL(pNode) );
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 || pRtree->bCorrupt );
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){
int rc = SQLITE_NOMEM;
Rtree *pRtree = (Rtree *)pVTab;
RtreeCursor *pCsr;
pCsr = (RtreeCursor *)sqlite3_malloc64(sizeof(RtreeCursor));
if( pCsr ){
memset(pCsr, 0, sizeof(RtreeCursor));
pCsr->base.pVtab = pVTab;
rc = SQLITE_OK;
pRtree->nCursor++;
}
*ppCursor = (sqlite3_vtab_cursor *)pCsr;
return rc;
}
/*
** Reset a cursor back to its initial state.
*/
static void resetCursor(RtreeCursor *pCsr){
Rtree *pRtree = (Rtree *)(pCsr->base.pVtab);
int ii;
sqlite3_stmt *pStmt;
if( pCsr->aConstraint ){
int i; /* Used to iterate through constraint array */
for(i=0; i<pCsr->nConstraint; i++){
sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
if( pInfo ){
if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
sqlite3_free(pInfo);
}
}
sqlite3_free(pCsr->aConstraint);
pCsr->aConstraint = 0;
}
for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
sqlite3_free(pCsr->aPoint);
pStmt = pCsr->pReadAux;
memset(pCsr, 0, sizeof(RtreeCursor));
pCsr->base.pVtab = (sqlite3_vtab*)pRtree;
pCsr->pReadAux = pStmt;
}
/*
** Rtree virtual table module xClose method.
*/
static int rtreeClose(sqlite3_vtab_cursor *cur){
Rtree *pRtree = (Rtree *)(cur->pVtab);
RtreeCursor *pCsr = (RtreeCursor *)cur;
assert( pRtree->nCursor>0 );
resetCursor(pCsr);
sqlite3_finalize(pCsr->pReadAux);
sqlite3_free(pCsr);
pRtree->nCursor--;
if( pRtree->nCursor==0 && pRtree->inWrTrans==0 ){
nodeBlobReset(pRtree);
}
return SQLITE_OK;
}
/*
** Rtree virtual table module xEof method.
**
** Return non-zero if the cursor does not currently point to a valid
** record (i.e if the scan has finished), or zero otherwise.
*/
static int rtreeEof(sqlite3_vtab_cursor *cur){
RtreeCursor *pCsr = (RtreeCursor *)cur;
return pCsr->atEOF;
}
/*
** Convert raw bits from the on-disk RTree record into a coordinate value.
** The on-disk format is big-endian and needs to be converted for little-
** endian platforms. The on-disk record stores integer coordinates if
** eInt is true and it stores 32-bit floating point records if eInt is
** false. a[] is the four bytes of the on-disk record to be decoded.
** Store the results in "r".
**
** There are five versions of this macro. The last one is generic. The
** other four are various architectures-specific optimizations.
*/
#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
c.u = _byteswap_ulong(*(u32*)a); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
c.u = __builtin_bswap32(*(u32*)a); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#elif SQLITE_BYTEORDER==1234
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
memcpy(&c.u,a,4); \
c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#elif SQLITE_BYTEORDER==4321
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
memcpy(&c.u,a,4); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#else
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
+((u32)a[2]<<8) + a[3]; \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#endif
/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.
*/
static int rtreeCallbackConstraint(
RtreeConstraint *pConstraint, /* The constraint to test */
int eInt, /* True if RTree holding integer coordinates */
u8 *pCellData, /* Raw cell content */
RtreeSearchPoint *pSearch, /* Container of this cell */
sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */
int *peWithin /* OUT: visibility of the cell */
){
sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
int nCoord = pInfo->nCoord; /* No. of coordinates */
int rc; /* Callback return code */
RtreeCoord c; /* Translator union */
sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */
assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );
assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );
if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){
pInfo->iRowid = readInt64(pCellData);
}
pCellData += 8;
#ifndef SQLITE_RTREE_INT_ONLY
if( eInt==0 ){
switch( nCoord ){
case 10: readCoord(pCellData+36, &c); aCoord[9] = c.f;
readCoord(pCellData+32, &c); aCoord[8] = c.f;
case 8: readCoord(pCellData+28, &c); aCoord[7] = c.f;
readCoord(pCellData+24, &c); aCoord[6] = c.f;
case 6: readCoord(pCellData+20, &c); aCoord[5] = c.f;
readCoord(pCellData+16, &c); aCoord[4] = c.f;
case 4: readCoord(pCellData+12, &c); aCoord[3] = c.f;
readCoord(pCellData+8, &c); aCoord[2] = c.f;
default: readCoord(pCellData+4, &c); aCoord[1] = c.f;
readCoord(pCellData, &c); aCoord[0] = c.f;
}
}else
#endif
{
switch( nCoord ){
case 10: readCoord(pCellData+36, &c); aCoord[9] = c.i;
readCoord(pCellData+32, &c); aCoord[8] = c.i;
case 8: readCoord(pCellData+28, &c); aCoord[7] = c.i;
readCoord(pCellData+24, &c); aCoord[6] = c.i;
case 6: readCoord(pCellData+20, &c); aCoord[5] = c.i;
readCoord(pCellData+16, &c); aCoord[4] = c.i;
case 4: readCoord(pCellData+12, &c); aCoord[3] = c.i;
readCoord(pCellData+8, &c); aCoord[2] = c.i;
default: readCoord(pCellData+4, &c); aCoord[1] = c.i;
readCoord(pCellData, &c); aCoord[0] = c.i;
}
}
if( pConstraint->op==RTREE_MATCH ){
int eWithin = 0;
rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
nCoord, aCoord, &eWithin);
if( eWithin==0 ) *peWithin = NOT_WITHIN;
*prScore = RTREE_ZERO;
}else{
pInfo->aCoord = aCoord;
pInfo->iLevel = pSearch->iLevel - 1;
pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
rc = pConstraint->u.xQueryFunc(pInfo);
if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
*prScore = pInfo->rScore;
}
}
return rc;
}
/*
** Check the internal RTree node given by pCellData against constraint p.
** If this constraint cannot be satisfied by any child within the node,
** set *peWithin to NOT_WITHIN.
*/
static void rtreeNonleafConstraint(
RtreeConstraint *p, /* The constraint to test */
int eInt, /* True if RTree holds integer coordinates */
u8 *pCellData, /* Raw cell content as appears on disk */
int *peWithin /* Adjust downward, as appropriate */
){
sqlite3_rtree_dbl val; /* Coordinate value convert to a double */
/* p->iCoord might point to either a lower or upper bound coordinate
** in a coordinate pair. But make pCellData point to the lower bound.
*/
pCellData += 8 + 4*(p->iCoord&0xfe);
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
|| p->op==RTREE_FALSE );
assert( FOUR_BYTE_ALIGNED(pCellData) );
switch( p->op ){
case RTREE_TRUE: return; /* Always satisfied */
case RTREE_FALSE: break; /* Never satisfied */
case RTREE_EQ:
RTREE_DECODE_COORD(eInt, pCellData, val);
/* val now holds the lower bound of the coordinate pair */
if( p->u.rValue>=val ){
pCellData += 4;
RTREE_DECODE_COORD(eInt, pCellData, val);
/* val now holds the upper bound of the coordinate pair */
if( p->u.rValue<=val ) return;
}
break;
case RTREE_LE:
case RTREE_LT:
RTREE_DECODE_COORD(eInt, pCellData, val);
/* val now holds the lower bound of the coordinate pair */
if( p->u.rValue>=val ) return;
break;
default:
pCellData += 4;
RTREE_DECODE_COORD(eInt, pCellData, val);
/* val now holds the upper bound of the coordinate pair */
if( p->u.rValue<=val ) return;
break;
}
*peWithin = NOT_WITHIN;
}
/*
** Check the leaf RTree cell given by pCellData against constraint p.
** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
** If the constraint is satisfied, leave *peWithin unchanged.
**
** The constraint is of the form: xN op $val
**
** The op is given by p->op. The xN is p->iCoord-th coordinate in
** pCellData. $val is given by p->u.rValue.
*/
static void rtreeLeafConstraint(
RtreeConstraint *p, /* The constraint to test */
int eInt, /* True if RTree holds integer coordinates */
u8 *pCellData, /* Raw cell content as appears on disk */
int *peWithin /* Adjust downward, as appropriate */
){
RtreeDValue xN; /* Coordinate value converted to a double */
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE
|| p->op==RTREE_FALSE );
pCellData += 8 + p->iCoord*4;
assert( FOUR_BYTE_ALIGNED(pCellData) );
RTREE_DECODE_COORD(eInt, pCellData, xN);
switch( p->op ){
case RTREE_TRUE: return; /* Always satisfied */
case RTREE_FALSE: break; /* Never satisfied */
case RTREE_LE: if( xN <= p->u.rValue ) return; break;
case RTREE_LT: if( xN < p->u.rValue ) return; break;
case RTREE_GE: if( xN >= p->u.rValue ) return; break;
case RTREE_GT: if( xN > p->u.rValue ) return; break;
default: if( xN == p->u.rValue ) return; break;
}
*peWithin = NOT_WITHIN;
}
/*
** One of the cells in node pNode is guaranteed to have a 64-bit
** integer value equal to iRowid. Return the index of this cell.
*/
static int nodeRowidIndex(
Rtree *pRtree,
RtreeNode *pNode,
i64 iRowid,
int *piIndex
){
int ii;
int nCell = NCELL(pNode);
assert( nCell<200 );
for(ii=0; ii<nCell; ii++){
if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
*piIndex = ii;
return SQLITE_OK;
}
}
RTREE_IS_CORRUPT(pRtree);
return SQLITE_CORRUPT_VTAB;
}
/*
** Return the index of the cell containing a pointer to node pNode
** in its parent. If pNode is the root node, return -1.
*/
static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
RtreeNode *pParent = pNode->pParent;
if( ALWAYS(pParent) ){
return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
}else{
*piIndex = -1;
return SQLITE_OK;
}
}
/*
** Compare two search points. Return negative, zero, or positive if the first
** is less than, equal to, or greater than the second.
**
** The rScore is the primary key. Smaller rScore values come first.
** If the rScore is a tie, then use iLevel as the tie breaker with smaller
** iLevel values coming first. In this way, if rScore is the same for all
** SearchPoints, then iLevel becomes the deciding factor and the result
** is a depth-first search, which is the desired default behavior.
*/
static int rtreeSearchPointCompare(
const RtreeSearchPoint *pA,
const RtreeSearchPoint *pB
){
if( pA->rScore<pB->rScore ) return -1;
if( pA->rScore>pB->rScore ) return +1;
if( pA->iLevel<pB->iLevel ) return -1;
if( pA->iLevel>pB->iLevel ) return +1;
return 0;
}
/*
** Interchange two search points in a cursor.
*/
static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
RtreeSearchPoint t = p->aPoint[i];
assert( i<j );
p->aPoint[i] = p->aPoint[j];
p->aPoint[j] = t;
i++; j++;
if( i<RTREE_CACHE_SZ ){
if( j>=RTREE_CACHE_SZ ){
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
p->aNode[i] = 0;
}else{
RtreeNode *pTemp = p->aNode[i];
p->aNode[i] = p->aNode[j];
p->aNode[j] = pTemp;
}
}
}
/*
** Return the search point with the lowest current score.
*/
static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
}
/*
** Get the RtreeNode for the search point with the lowest score.
*/
static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
sqlite3_int64 id;
int ii = 1 - pCur->bPoint;
assert( ii==0 || ii==1 );
assert( pCur->bPoint || pCur->nPoint );
if( pCur->aNode[ii]==0 ){
assert( pRC!=0 );
id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
*pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
}
return pCur->aNode[ii];
}
/*
** Push a new element onto the priority queue
*/
static RtreeSearchPoint *rtreeEnqueue(
RtreeCursor *pCur, /* The cursor */
RtreeDValue rScore, /* Score for the new search point */
u8 iLevel /* Level for the new search point */
){
int i, j;
RtreeSearchPoint *pNew;
if( pCur->nPoint>=pCur->nPointAlloc ){
int nNew = pCur->nPointAlloc*2 + 8;
pNew = sqlite3_realloc64(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
if( pNew==0 ) return 0;
pCur->aPoint = pNew;
pCur->nPointAlloc = nNew;
}
i = pCur->nPoint++;
pNew = pCur->aPoint + i;
pNew->rScore = rScore;
pNew->iLevel = iLevel;
assert( iLevel<=RTREE_MAX_DEPTH );
while( i>0 ){
RtreeSearchPoint *pParent;
j = (i-1)/2;
pParent = pCur->aPoint + j;
if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
rtreeSearchPointSwap(pCur, j, i);
i = j;
pNew = pParent;
}
return pNew;
}
/*
** Allocate a new RtreeSearchPoint and return a pointer to it. Return
** NULL if malloc fails.
*/
static RtreeSearchPoint *rtreeSearchPointNew(
RtreeCursor *pCur, /* The cursor */
RtreeDValue rScore, /* Score for the new search point */
u8 iLevel /* Level for the new search point */
){
RtreeSearchPoint *pNew, *pFirst;
pFirst = rtreeSearchPointFirst(pCur);
pCur->anQueue[iLevel]++;
if( pFirst==0
|| pFirst->rScore>rScore
|| (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
){
if( pCur->bPoint ){
int ii;
pNew = rtreeEnqueue(pCur, rScore, iLevel);
if( pNew==0 ) return 0;
ii = (int)(pNew - pCur->aPoint) + 1;
assert( ii==1 );
if( ALWAYS(ii<RTREE_CACHE_SZ) ){
assert( pCur->aNode[ii]==0 );
pCur->aNode[ii] = pCur->aNode[0];
}else{
nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
}
pCur->aNode[0] = 0;
*pNew = pCur->sPoint;
}
pCur->sPoint.rScore = rScore;
pCur->sPoint.iLevel = iLevel;
pCur->bPoint = 1;
return &pCur->sPoint;
}else{
return rtreeEnqueue(pCur, rScore, iLevel);
}
}
#if 0
/* Tracing routines for the RtreeSearchPoint queue */
static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
printf(" %d.%05lld.%02d %g %d",
p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
);
idx++;
if( idx<RTREE_CACHE_SZ ){
printf(" %p\n", pCur->aNode[idx]);
}else{
printf("\n");
}
}
static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
int ii;
printf("=== %9s ", zPrefix);
if( pCur->bPoint ){
tracePoint(&pCur->sPoint, -1, pCur);
}
for(ii=0; ii<pCur->nPoint; ii++){
if( ii>0 || pCur->bPoint ) printf(" ");
tracePoint(&pCur->aPoint[ii], ii, pCur);
}
}
# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
#else
# define RTREE_QUEUE_TRACE(A,B) /* no-op */
#endif
/* Remove the search point with the lowest current score.
*/
static void rtreeSearchPointPop(RtreeCursor *p){
int i, j, k, n;
i = 1 - p->bPoint;
assert( i==0 || i==1 );
if( p->aNode[i] ){
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
p->aNode[i] = 0;
}
if( p->bPoint ){
p->anQueue[p->sPoint.iLevel]--;
p->bPoint = 0;
}else if( ALWAYS(p->nPoint) ){
p->anQueue[p->aPoint[0].iLevel]--;
n = --p->nPoint;
p->aPoint[0] = p->aPoint[n];
if( n<RTREE_CACHE_SZ-1 ){
p->aNode[1] = p->aNode[n+1];
p->aNode[n+1] = 0;
}
i = 0;
while( (j = i*2+1)<n ){
k = j+1;
if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
rtreeSearchPointSwap(p, i, k);
i = k;
}else{
break;
}
}else{
if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
rtreeSearchPointSwap(p, i, j);
i = j;
}else{
break;
}
}
}
}
}
/*
** Continue the search on cursor pCur until the front of the queue
** contains an entry suitable for returning as a result-set row,
** or until the RtreeSearchPoint queue is empty, indicating that the
** query has completed.
*/
static int rtreeStepToLeaf(RtreeCursor *pCur){
RtreeSearchPoint *p;
Rtree *pRtree = RTREE_OF_CURSOR(pCur);
RtreeNode *pNode;
int eWithin;
int rc = SQLITE_OK;
int nCell;
int nConstraint = pCur->nConstraint;
int ii;
int eInt;
RtreeSearchPoint x;
eInt = pRtree->eCoordType==RTREE_COORD_INT32;
while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
u8 *pCellData;
pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
if( rc ) return rc;
nCell = NCELL(pNode);
assert( nCell<200 );
pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
while( p->iCell<nCell ){
sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
eWithin = FULLY_WITHIN;
for(ii=0; ii<nConstraint; ii++){
RtreeConstraint *pConstraint = pCur->aConstraint + ii;
if( pConstraint->op>=RTREE_MATCH ){
rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
&rScore, &eWithin);
if( rc ) return rc;
}else if( p->iLevel==1 ){
rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin);
}else{
rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin);
}
if( eWithin==NOT_WITHIN ){
p->iCell++;
pCellData += pRtree->nBytesPerCell;
break;
}
}
if( eWithin==NOT_WITHIN ) continue;
p->iCell++;
x.iLevel = p->iLevel - 1;
if( x.iLevel ){
x.id = readInt64(pCellData);
for(ii=0; ii<pCur->nPoint; ii++){
if( pCur->aPoint[ii].id==x.id ){
RTREE_IS_CORRUPT(pRtree);
return SQLITE_CORRUPT_VTAB;
}
}
x.iCell = 0;
}else{
x.id = p->id;
x.iCell = p->iCell - 1;
}
if( p->iCell>=nCell ){
RTREE_QUEUE_TRACE(pCur, "POP-S:");
rtreeSearchPointPop(pCur);
}
if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
if( p==0 ) return SQLITE_NOMEM;
p->eWithin = (u8)eWithin;
p->id = x.id;
p->iCell = x.iCell;
RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
break;
}
if( p->iCell>=nCell ){
RTREE_QUEUE_TRACE(pCur, "POP-Se:");
rtreeSearchPointPop(pCur);
}
}
pCur->atEOF = p==0;
return SQLITE_OK;
}
/*
** Rtree virtual table module xNext method.
*/
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
int rc = SQLITE_OK;
/* Move to the next entry that matches the configured constraints. */
RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
if( pCsr->bAuxValid ){
pCsr->bAuxValid = 0;
sqlite3_reset(pCsr->pReadAux);
}
rtreeSearchPointPop(pCsr);
rc = rtreeStepToLeaf(pCsr);
return rc;
}
/*
** Rtree virtual table module xRowid method.
*/
static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
int rc = SQLITE_OK;
RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
if( rc==SQLITE_OK && ALWAYS(p) ){
if( p->iCell>=NCELL(pNode) ){
rc = SQLITE_ABORT;
}else{
*pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
}
}
return rc;
}
/*
** Rtree virtual table module xColumn method.
*/
static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
Rtree *pRtree = (Rtree *)cur->pVtab;
RtreeCursor *pCsr = (RtreeCursor *)cur;
RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
RtreeCoord c;
int rc = SQLITE_OK;
RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
if( rc ) return rc;
if( NEVER(p==0) ) return SQLITE_OK;
if( p->iCell>=NCELL(pNode) ) return SQLITE_ABORT;
if( i==0 ){
sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
}else if( i<=pRtree->nDim2 ){
nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
#ifndef SQLITE_RTREE_INT_ONLY
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sqlite3_result_double(ctx, c.f);
}else
#endif
{
assert( pRtree->eCoordType==RTREE_COORD_INT32 );
sqlite3_result_int(ctx, c.i);
}
}else{
if( !pCsr->bAuxValid ){
if( pCsr->pReadAux==0 ){
rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0,
&pCsr->pReadAux, 0);
if( rc ) return rc;
}
sqlite3_bind_int64(pCsr->pReadAux, 1,
nodeGetRowid(pRtree, pNode, p->iCell));
rc = sqlite3_step(pCsr->pReadAux);
if( rc==SQLITE_ROW ){
pCsr->bAuxValid = 1;
}else{
sqlite3_reset(pCsr->pReadAux);
if( rc==SQLITE_DONE ) rc = SQLITE_OK;
return rc;
}
}
sqlite3_result_value(ctx,
sqlite3_column_value(pCsr->pReadAux, i - pRtree->nDim2 + 1));
}
return SQLITE_OK;
}
/*
** Use nodeAcquire() to obtain the leaf node containing the record with
** rowid iRowid. If successful, set *ppLeaf to point to the node and
** return SQLITE_OK. If there is no such record in the table, set
** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
** to zero and return an SQLite error code.
*/
static int findLeafNode(
Rtree *pRtree, /* RTree to search */
i64 iRowid, /* The rowid searching for */
RtreeNode **ppLeaf, /* Write the node here */
sqlite3_int64 *piNode /* Write the node-id here */
){
int rc;
*ppLeaf = 0;
sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
if( piNode ) *piNode = iNode;
rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
sqlite3_reset(pRtree->pReadRowid);
}else{
rc = sqlite3_reset(pRtree->pReadRowid);
}
return rc;
}
/*
** This function is called to configure the RtreeConstraint object passed
** as the second argument for a MATCH constraint. The value passed as the
** first argument to this function is the right-hand operand to the MATCH
** operator.
*/
static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
RtreeMatchArg *pBlob, *pSrc; /* BLOB returned by geometry function */
sqlite3_rtree_query_info *pInfo; /* Callback information */
pSrc = sqlite3_value_pointer(pValue, "RtreeMatchArg");
if( pSrc==0 ) return SQLITE_ERROR;
pInfo = (sqlite3_rtree_query_info*)
sqlite3_malloc64( sizeof(*pInfo)+pSrc->iSize );
if( !pInfo ) return SQLITE_NOMEM;
memset(pInfo, 0, sizeof(*pInfo));
pBlob = (RtreeMatchArg*)&pInfo[1];
memcpy(pBlob, pSrc, pSrc->iSize);
pInfo->pContext = pBlob->cb.pContext;
pInfo->nParam = pBlob->nParam;
pInfo->aParam = pBlob->aParam;
pInfo->apSqlParam = pBlob->apSqlParam;
if( pBlob->cb.xGeom ){
pCons->u.xGeom = pBlob->cb.xGeom;
}else{
pCons->op = RTREE_QUERY;
pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
}
pCons->pInfo = pInfo;
return SQLITE_OK;
}
int sqlite3IntFloatCompare(i64,double);
/*
** Rtree virtual table module xFilter method.
*/
static int rtreeFilter(
sqlite3_vtab_cursor *pVtabCursor,
int idxNum, const char *idxStr,
int argc, sqlite3_value **argv
){
Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
RtreeNode *pRoot = 0;
int ii;
int rc = SQLITE_OK;
int iCell = 0;
rtreeReference(pRtree);
/* Reset the cursor to the same state as rtreeOpen() leaves it in. */
resetCursor(pCsr);
pCsr->iStrategy = idxNum;
if( idxNum==1 ){
/* Special case - lookup by rowid. */
RtreeNode *pLeaf; /* Leaf on which the required cell resides */
RtreeSearchPoint *p; /* Search point for the leaf */
i64 iRowid = sqlite3_value_int64(argv[0]);
i64 iNode = 0;
int eType = sqlite3_value_numeric_type(argv[0]);
if( eType==SQLITE_INTEGER
|| (eType==SQLITE_FLOAT
&& 0==sqlite3IntFloatCompare(iRowid,sqlite3_value_double(argv[0])))
){
rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
}else{
rc = SQLITE_OK;
pLeaf = 0;
}
if( rc==SQLITE_OK && pLeaf!=0 ){
p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
assert( p!=0 ); /* Always returns pCsr->sPoint */
pCsr->aNode[0] = pLeaf;
p->id = iNode;
p->eWithin = PARTLY_WITHIN;
rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
p->iCell = (u8)iCell;
RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
}else{
pCsr->atEOF = 1;
}
}else{
/* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
** with the configured constraints.
*/
rc = nodeAcquire(pRtree, 1, 0, &pRoot);
if( rc==SQLITE_OK && argc>0 ){
pCsr->aConstraint = sqlite3_malloc64(sizeof(RtreeConstraint)*argc);
pCsr->nConstraint = argc;
if( !pCsr->aConstraint ){
rc = SQLITE_NOMEM;
}else{
memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
assert( (idxStr==0 && argc==0)
|| (idxStr && (int)strlen(idxStr)==argc*2) );
for(ii=0; ii<argc; ii++){
RtreeConstraint *p = &pCsr->aConstraint[ii];
int eType = sqlite3_value_numeric_type(argv[ii]);
p->op = idxStr[ii*2];
p->iCoord = idxStr[ii*2+1]-'0';
if( p->op>=RTREE_MATCH ){
/* A MATCH operator. The right-hand-side must be a blob that
** can be cast into an RtreeMatchArg object. One created using
** an sqlite3_rtree_geometry_callback() SQL user function.
*/
rc = deserializeGeometry(argv[ii], p);
if( rc!=SQLITE_OK ){
break;
}
p->pInfo->nCoord = pRtree->nDim2;
p->pInfo->anQueue = pCsr->anQueue;
p->pInfo->mxLevel = pRtree->iDepth + 1;
}else if( eType==SQLITE_INTEGER ){
sqlite3_int64 iVal = sqlite3_value_int64(argv[ii]);
#ifdef SQLITE_RTREE_INT_ONLY
p->u.rValue = iVal;
#else
p->u.rValue = (double)iVal;
if( iVal>=((sqlite3_int64)1)<<48
|| iVal<=-(((sqlite3_int64)1)<<48)
){
if( p->op==RTREE_LT ) p->op = RTREE_LE;
if( p->op==RTREE_GT ) p->op = RTREE_GE;
}
#endif
}else if( eType==SQLITE_FLOAT ){
#ifdef SQLITE_RTREE_INT_ONLY
p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
p->u.rValue = sqlite3_value_double(argv[ii]);
#endif
}else{
p->u.rValue = RTREE_ZERO;
if( eType==SQLITE_NULL ){
p->op = RTREE_FALSE;
}else if( p->op==RTREE_LT || p->op==RTREE_LE ){
p->op = RTREE_TRUE;
}else{
p->op = RTREE_FALSE;
}
}
}
}
}
if( rc==SQLITE_OK ){
RtreeSearchPoint *pNew;
assert( pCsr->bPoint==0 ); /* Due to the resetCursor() call above */
pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1));
if( NEVER(pNew==0) ){ /* Because pCsr->bPoint was FALSE */
return SQLITE_NOMEM;
}
pNew->id = 1;
pNew->iCell = 0;
pNew->eWithin = PARTLY_WITHIN;
assert( pCsr->bPoint==1 );
pCsr->aNode[0] = pRoot;
pRoot = 0;
RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
rc = rtreeStepToLeaf(pCsr);
}
}
nodeRelease(pRtree, pRoot);
rtreeRelease(pRtree);
return rc;
}
/*
** Rtree virtual table module xBestIndex method. There are three
** table scan strategies to choose from (in order from most to
** least desirable):
**
** idxNum idxStr Strategy
** ------------------------------------------------
** 1 Unused Direct lookup by rowid.
** 2 See below R-tree query or full-table scan.
** ------------------------------------------------
**
** If strategy 1 is used, then idxStr is not meaningful. If strategy
** 2 is used, idxStr is formatted to contain 2 bytes for each
** constraint used. The first two bytes of idxStr correspond to
** the constraint in sqlite3_index_info.aConstraintUsage[] with
** (argvIndex==1) etc.
**
** The first of each pair of bytes in idxStr identifies the constraint
** operator as follows:
**
** Operator Byte Value
** ----------------------
** = 0x41 ('A')
** <= 0x42 ('B')
** < 0x43 ('C')
** >= 0x44 ('D')
** > 0x45 ('E')
** MATCH 0x46 ('F')
** ----------------------
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
Rtree *pRtree = (Rtree*)tab;
int rc = SQLITE_OK;
int ii;
int bMatch = 0; /* True if there exists a MATCH constraint */
i64 nRow; /* Estimated rows returned by this scan */
int iIdx = 0;
char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
memset(zIdxStr, 0, sizeof(zIdxStr));
/* Check if there exists a MATCH constraint - even an unusable one. If there
** is, do not consider the lookup-by-rowid plan as using such a plan would
** require the VDBE to evaluate the MATCH constraint, which is not currently
** possible. */
for(ii=0; ii<pIdxInfo->nConstraint; ii++){
if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){
bMatch = 1;
}
}
assert( pIdxInfo->idxStr==0 );
for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
if( bMatch==0 && p->usable
&& p->iColumn<=0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ
){
/* We have an equality constraint on the rowid. Use strategy 1. */
int jj;
for(jj=0; jj<ii; jj++){
pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
pIdxInfo->aConstraintUsage[jj].omit = 0;
}
pIdxInfo->idxNum = 1;
pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
pIdxInfo->aConstraintUsage[jj].omit = 1;
/* This strategy involves a two rowid lookups on an B-Tree structures
** and then a linear search of an R-Tree node. This should be
** considered almost as quick as a direct rowid lookup (for which
** sqlite uses an internal cost of 0.0). It is expected to return
** a single row.
*/
pIdxInfo->estimatedCost = 30.0;
pIdxInfo->estimatedRows = 1;
pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
return SQLITE_OK;
}
if( p->usable
&& ((p->iColumn>0 && p->iColumn<=pRtree->nDim2)
|| p->op==SQLITE_INDEX_CONSTRAINT_MATCH)
){
u8 op;
u8 doOmit = 1;
switch( p->op ){
case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; doOmit = 0; break;
case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; doOmit = 0; break;
case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; doOmit = 0; break;
case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
case SQLITE_INDEX_CONSTRAINT_MATCH: op = RTREE_MATCH; break;
default: op = 0; break;
}
if( op ){
zIdxStr[iIdx++] = op;
zIdxStr[iIdx++] = (char)(p->iColumn - 1 + '0');
pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
pIdxInfo->aConstraintUsage[ii].omit = doOmit;
}
}
}
pIdxInfo->idxNum = 2;
pIdxInfo->needToFreeIdxStr = 1;
if( iIdx>0 ){
pIdxInfo->idxStr = sqlite3_malloc( iIdx+1 );
if( pIdxInfo->idxStr==0 ){
return SQLITE_NOMEM;
}
memcpy(pIdxInfo->idxStr, zIdxStr, iIdx+1);
}
nRow = pRtree->nRowEst >> (iIdx/2);
pIdxInfo->estimatedCost = (double)6.0 * (double)nRow;
pIdxInfo->estimatedRows = nRow;
return rc;
}
/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){
RtreeDValue area = (RtreeDValue)1;
assert( pRtree->nDim>=1 && pRtree->nDim<=5 );
#ifndef SQLITE_RTREE_INT_ONLY
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
switch( pRtree->nDim ){
case 5: area = p->aCoord[9].f - p->aCoord[8].f;
case 4: area *= p->aCoord[7].f - p->aCoord[6].f;
case 3: area *= p->aCoord[5].f - p->aCoord[4].f;
case 2: area *= p->aCoord[3].f - p->aCoord[2].f;
default: area *= p->aCoord[1].f - p->aCoord[0].f;
}
}else
#endif
{
switch( pRtree->nDim ){
case 5: area = (i64)p->aCoord[9].i - (i64)p->aCoord[8].i;
case 4: area *= (i64)p->aCoord[7].i - (i64)p->aCoord[6].i;
case 3: area *= (i64)p->aCoord[5].i - (i64)p->aCoord[4].i;
case 2: area *= (i64)p->aCoord[3].i - (i64)p->aCoord[2].i;
default: area *= (i64)p->aCoord[1].i - (i64)p->aCoord[0].i;
}
}
return area;
}
/*
** Return the margin length of cell p. The margin length is the sum
** of the objects size in each dimension.
*/
static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
RtreeDValue margin = 0;
int ii = pRtree->nDim2 - 2;
do{
margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
ii -= 2;
}while( ii>=0 );
return margin;
}
/*
** Store the union of cells p1 and p2 in p1.
*/
static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
int ii = 0;
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
do{
p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
ii += 2;
}while( ii<pRtree->nDim2 );
}else{
do{
p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
ii += 2;
}while( ii<pRtree->nDim2 );
}
}
/*
** Return true if the area covered by p2 is a subset of the area covered
** by p1. False otherwise.
*/
static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
int ii;
if( pRtree->eCoordType==RTREE_COORD_INT32 ){
for(ii=0; ii<pRtree->nDim2; ii+=2){
RtreeCoord *a1 = &p1->aCoord[ii];
RtreeCoord *a2 = &p2->aCoord[ii];
if( a2[0].i<a1[0].i || a2[1].i>a1[1].i ) return 0;
}
}else{
for(ii=0; ii<pRtree->nDim2; ii+=2){
RtreeCoord *a1 = &p1->aCoord[ii];
RtreeCoord *a2 = &p2->aCoord[ii];
if( a2[0].f<a1[0].f || a2[1].f>a1[1].f ) return 0;
}
}
return 1;
}
static RtreeDValue cellOverlap(
Rtree *pRtree,
RtreeCell *p,
RtreeCell *aCell,
int nCell
){
int ii;
RtreeDValue overlap = RTREE_ZERO;
for(ii=0; ii<nCell; ii++){
int jj;
RtreeDValue o = (RtreeDValue)1;
for(jj=0; jj<pRtree->nDim2; jj+=2){
RtreeDValue x1, x2;
x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
if( x2<x1 ){
o = (RtreeDValue)0;
break;
}else{
o = o * (x2-x1);
}
}
overlap += o;
}
return overlap;
}
/*
** This function implements the ChooseLeaf algorithm from Gutman[84].
** ChooseSubTree in r*tree terminology.
*/
static int ChooseLeaf(
Rtree *pRtree, /* Rtree table */
RtreeCell *pCell, /* Cell to insert into rtree */
int iHeight, /* Height of sub-tree rooted at pCell */
RtreeNode **ppLeaf /* OUT: Selected leaf page */
){
int rc;
int ii;
RtreeNode *pNode = 0;
rc = nodeAcquire(pRtree, 1, 0, &pNode);
for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
int iCell;
sqlite3_int64 iBest = 0;
int bFound = 0;
RtreeDValue fMinGrowth = RTREE_ZERO;
RtreeDValue fMinArea = RTREE_ZERO;
int nCell = NCELL(pNode);
RtreeNode *pChild = 0;
/* First check to see if there is are any cells in pNode that completely
** contains pCell. If two or more cells in pNode completely contain pCell
** then pick the smallest.
*/
for(iCell=0; iCell<nCell; iCell++){
RtreeCell cell;
nodeGetCell(pRtree, pNode, iCell, &cell);
if( cellContains(pRtree, &cell, pCell) ){
RtreeDValue area = cellArea(pRtree, &cell);
if( bFound==0 || area<fMinArea ){
iBest = cell.iRowid;
fMinArea = area;
bFound = 1;
}
}
}
if( !bFound ){
/* No cells of pNode will completely contain pCell. So pick the
** cell of pNode that grows by the least amount when pCell is added.
** Break ties by selecting the smaller cell.
*/
for(iCell=0; iCell<nCell; iCell++){
RtreeCell cell;
RtreeDValue growth;
RtreeDValue area;
nodeGetCell(pRtree, pNode, iCell, &cell);
area = cellArea(pRtree, &cell);
cellUnion(pRtree, &cell, pCell);
growth = cellArea(pRtree, &cell)-area;
if( iCell==0
|| growth<fMinGrowth
|| (growth==fMinGrowth && area<fMinArea)
){
fMinGrowth = growth;
fMinArea = area;
iBest = cell.iRowid;
}
}
}
rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
nodeRelease(pRtree, pNode);
pNode = pChild;
}
*ppLeaf = pNode;
return rc;
}
/*
** A cell with the same content as pCell has just been inserted into
** the node pNode. This function updates the bounding box cells in
** all ancestor elements.
*/
static int AdjustTree(
Rtree *pRtree, /* Rtree table */
RtreeNode *pNode, /* Adjust ancestry of this node. */
RtreeCell *pCell /* This cell was just inserted */
){
RtreeNode *p = pNode;
int cnt = 0;
int rc;
while( p->pParent ){
RtreeNode *pParent = p->pParent;
RtreeCell cell;
int iCell;
cnt++;
if( NEVER(cnt>100) ){
RTREE_IS_CORRUPT(pRtree);
return SQLITE_CORRUPT_VTAB;
}
rc = nodeParentIndex(pRtree, p, &iCell);
if( NEVER(rc!=SQLITE_OK) ){
RTREE_IS_CORRUPT(pRtree);
return SQLITE_CORRUPT_VTAB;
}
nodeGetCell(pRtree, pParent, iCell, &cell);
if( !cellContains(pRtree, &cell, pCell) ){
cellUnion(pRtree, &cell, pCell);
nodeOverwriteCell(pRtree, pParent, &cell, iCell);
}
p = pParent;
}
return SQLITE_OK;
}
/*
** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
*/
static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
sqlite3_step(pRtree->pWriteRowid);
return sqlite3_reset(pRtree->pWriteRowid);
}
/*
** Write mapping (iNode->iPar) to the <rtree>_parent table.
*/
static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
sqlite3_step(pRtree->pWriteParent);
return sqlite3_reset(pRtree->pWriteParent);
}
static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
/*
** Arguments aIdx, aCell and aSpare all point to arrays of size
** nIdx. The aIdx array contains the set of integers from 0 to
** (nIdx-1) in no particular order. This function sorts the values
** in aIdx according to dimension iDim of the cells in aCell. The
** minimum value of dimension iDim is considered first, the
** maximum used to break ties.
**
** The aSpare array is used as temporary working space by the
** sorting algorithm.
*/
static void SortByDimension(
Rtree *pRtree,
int *aIdx,
int nIdx,
int iDim,
RtreeCell *aCell,
int *aSpare
){
if( nIdx>1 ){
int iLeft = 0;
int iRight = 0;
int nLeft = nIdx/2;
int nRight = nIdx-nLeft;
int *aLeft = aIdx;
int *aRight = &aIdx[nLeft];
SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
memcpy(aSpare, aLeft, sizeof(int)*nLeft);
aLeft = aSpare;
while( iLeft<nLeft || iRight<nRight ){
RtreeDValue xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
RtreeDValue xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
RtreeDValue xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
RtreeDValue xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
if( (iLeft!=nLeft) && ((iRight==nRight)
|| (xleft1<xright1)
|| (xleft1==xright1 && xleft2<xright2)
)){
aIdx[iLeft+iRight] = aLeft[iLeft];
iLeft++;
}else{
aIdx[iLeft+iRight] = aRight[iRight];
iRight++;
}
}
#if 0
/* Check that the sort worked */
{
int jj;
for(jj=1; jj<nIdx; jj++){
RtreeDValue xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
RtreeDValue xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
RtreeDValue xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
RtreeDValue xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
}
}
#endif
}
}
/*
** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
*/
static int splitNodeStartree(
Rtree *pRtree,
RtreeCell *aCell,
int nCell,
RtreeNode *pLeft,
RtreeNode *pRight,
RtreeCell *pBboxLeft,
RtreeCell *pBboxRight
){
int **aaSorted;
int *aSpare;
int ii;
int iBestDim = 0;
int iBestSplit = 0;
RtreeDValue fBestMargin = RTREE_ZERO;
sqlite3_int64 nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
aaSorted = (int **)sqlite3_malloc64(nByte);
if( !aaSorted ){
return SQLITE_NOMEM;
}
aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
memset(aaSorted, 0, nByte);
for(ii=0; ii<pRtree->nDim; ii++){
int jj;
aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
for(jj=0; jj<nCell; jj++){
aaSorted[ii][jj] = jj;
}
SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
}
for(ii=0; ii<pRtree->nDim; ii++){
RtreeDValue margin = RTREE_ZERO;
RtreeDValue fBestOverlap = RTREE_ZERO;
RtreeDValue fBestArea = RTREE_ZERO;
int iBestLeft = 0;
int nLeft;
for(
nLeft=RTREE_MINCELLS(pRtree);
nLeft<=(nCell-RTREE_MINCELLS(pRtree));
nLeft++
){
RtreeCell left;
RtreeCell right;
int kk;
RtreeDValue overlap;
RtreeDValue area;
memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
for(kk=1; kk<(nCell-1); kk++){
if( kk<nLeft ){
cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
}else{
cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
}
}
margin += cellMargin(pRtree, &left);
margin += cellMargin(pRtree, &right);
overlap = cellOverlap(pRtree, &left, &right, 1);
area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
if( (nLeft==RTREE_MINCELLS(pRtree))
|| (overlap<fBestOverlap)
|| (overlap==fBestOverlap && area<fBestArea)
){
iBestLeft = nLeft;
fBestOverlap = overlap;
fBestArea = area;
}
}
if( ii==0 || margin<fBestMargin ){
iBestDim = ii;
fBestMargin = margin;
iBestSplit = iBestLeft;
}
}
memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
for(ii=0; ii<nCell; ii++){
RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
nodeInsertCell(pRtree, pTarget, pCell);
cellUnion(pRtree, pBbox, pCell);
}
sqlite3_free(aaSorted);
return SQLITE_OK;
}
static int updateMapping(
Rtree *pRtree,
i64 iRowid,
RtreeNode *pNode,
int iHeight
){
int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
if( iHeight>0 ){
RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
RtreeNode *p;
for(p=pNode; p; p=p->pParent){
if( p==pChild ) return SQLITE_CORRUPT_VTAB;
}
if( pChild ){
nodeRelease(pRtree, pChild->pParent);
nodeReference(pNode);
pChild->pParent = pNode;
}
}
if( NEVER(pNode==0) ) return SQLITE_ERROR;
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_malloc64((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
if( !aCell ){
rc = SQLITE_NOMEM;
goto splitnode_out;
}
aiUsed = (int *)&aCell[nCell+1];
memset(aiUsed, 0, sizeof(int)*(nCell+1));
for(i=0; i<nCell; i++){
nodeGetCell(pRtree, pNode, i, &aCell[i]);
}
nodeZero(pRtree, pNode);
memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
nCell++;
if( pNode->iNode==1 ){
pRight = nodeNew(pRtree, pNode);
pLeft = nodeNew(pRtree, pNode);
pRtree->iDepth++;
pNode->isDirty = 1;
writeInt16(pNode->zData, pRtree->iDepth);
}else{
pLeft = pNode;
pRight = nodeNew(pRtree, pLeft->pParent);
pLeft->nRef++;
}
if( !pLeft || !pRight ){
rc = SQLITE_NOMEM;
goto splitnode_out;
}
memset(pLeft->zData, 0, pRtree->iNodeSize);
memset(pRight->zData, 0, pRtree->iNodeSize);
rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
&leftbbox, &rightbbox);
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
/* Ensure both child nodes have node numbers assigned to them by calling
** nodeWrite(). Node pRight always needs a node number, as it was created
** by nodeNew() above. But node pLeft sometimes already has a node number.
** In this case avoid the all to nodeWrite().
*/
if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
|| (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
){
goto splitnode_out;
}
rightbbox.iRowid = pRight->iNode;
leftbbox.iRowid = pLeft->iNode;
if( pNode->iNode==1 ){
rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
}else{
RtreeNode *pParent = pLeft->pParent;
int iCell;
rc = nodeParentIndex(pRtree, pLeft, &iCell);
if( ALWAYS(rc==SQLITE_OK) ){
nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
rc = AdjustTree(pRtree, pParent, &leftbbox);
assert( rc==SQLITE_OK );
}
if( NEVER(rc!=SQLITE_OK) ){
goto splitnode_out;
}
}
if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
goto splitnode_out;
}
for(i=0; i<NCELL(pRight); i++){
i64 iRowid = nodeGetRowid(pRtree, pRight, i);
rc = updateMapping(pRtree, iRowid, pRight, iHeight);
if( iRowid==pCell->iRowid ){
newCellIsRight = 1;
}
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
}
if( pNode->iNode==1 ){
for(i=0; i<NCELL(pLeft); i++){
i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
}
}else if( newCellIsRight==0 ){
rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
}
if( rc==SQLITE_OK ){
rc = nodeRelease(pRtree, pRight);
pRight = 0;
}
if( rc==SQLITE_OK ){
rc = nodeRelease(pRtree, pLeft);
pLeft = 0;
}
splitnode_out:
nodeRelease(pRtree, pRight);
nodeRelease(pRtree, pLeft);
sqlite3_free(aCell);
return rc;
}
/*
** If node pLeaf is not the root of the r-tree and its pParent pointer is
** still NULL, load all ancestor nodes of pLeaf into memory and populate
** the pLeaf->pParent chain all the way up to the root node.
**
** This operation is required when a row is deleted (or updated - an update
** is implemented as a delete followed by an insert). SQLite provides the
** rowid of the row to delete, which can be used to find the leaf on which
** the entry resides (argument pLeaf). Once the leaf is located, this
** function is called to determine its ancestry.
*/
static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
int rc = SQLITE_OK;
RtreeNode *pChild = pLeaf;
while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
int rc2 = SQLITE_OK; /* sqlite3_reset() return code */
sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
rc = sqlite3_step(pRtree->pReadParent);
if( rc==SQLITE_ROW ){
RtreeNode *pTest; /* Used to test for reference loops */
i64 iNode; /* Node number of parent node */
/* Before setting pChild->pParent, test that we are not creating a
** loop of references (as we would if, say, pChild==pParent). We don't
** want to do this as it leads to a memory leak when trying to delete
** the referenced counted node structures.
*/
iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
if( pTest==0 ){
rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
}
}
rc = sqlite3_reset(pRtree->pReadParent);
if( rc==SQLITE_OK ) rc = rc2;
if( rc==SQLITE_OK && !pChild->pParent ){
RTREE_IS_CORRUPT(pRtree);
rc = SQLITE_CORRUPT_VTAB;
}
pChild = pChild->pParent;
}
return rc;
}
static int deleteCell(Rtree *, RtreeNode *, int, int);
static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
int rc;
int rc2;
RtreeNode *pParent = 0;
int iCell;
assert( pNode->nRef==1 );
/* Remove the entry in the parent cell. */
rc = nodeParentIndex(pRtree, pNode, &iCell);
if( rc==SQLITE_OK ){
pParent = pNode->pParent;
pNode->pParent = 0;
rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
testcase( rc!=SQLITE_OK );
}
rc2 = nodeRelease(pRtree, pParent);
if( rc==SQLITE_OK ){
rc = rc2;
}
if( rc!=SQLITE_OK ){
return rc;
}
/* Remove the xxx_node entry. */
sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
sqlite3_step(pRtree->pDeleteNode);
if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
return rc;
}
/* Remove the xxx_parent entry. */
sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
sqlite3_step(pRtree->pDeleteParent);
if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
return rc;
}
/* Remove the node from the in-memory hash table and link it into
** the Rtree.pDeleted list. Its contents will be re-inserted later on.
*/
nodeHashDelete(pRtree, pNode);
pNode->iNode = iHeight;
pNode->pNext = pRtree->pDeleted;
pNode->nRef++;
pRtree->pDeleted = pNode;
return SQLITE_OK;
}
static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
RtreeNode *pParent = pNode->pParent;
int rc = SQLITE_OK;
if( pParent ){
int ii;
int nCell = NCELL(pNode);
RtreeCell box; /* Bounding box for pNode */
nodeGetCell(pRtree, pNode, 0, &box);
for(ii=1; ii<nCell; ii++){
RtreeCell cell;
nodeGetCell(pRtree, pNode, ii, &cell);
cellUnion(pRtree, &box, &cell);
}
box.iRowid = pNode->iNode;
rc = nodeParentIndex(pRtree, pNode, &ii);
if( rc==SQLITE_OK ){
nodeOverwriteCell(pRtree, pParent, &box, ii);
rc = fixBoundingBox(pRtree, pParent);
}
}
return rc;
}
/*
** Delete the cell at index iCell of node pNode. After removing the
** cell, adjust the r-tree data structure if required.
*/
static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
RtreeNode *pParent;
int rc;
if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
return rc;
}
/* Remove the cell from the node. This call just moves bytes around
** the in-memory node image, so it cannot fail.
*/
nodeDeleteCell(pRtree, pNode, iCell);
/* If the node is not the tree root and now has less than the minimum
** number of cells, remove it from the tree. Otherwise, update the
** cell in the parent node so that it tightly contains the updated
** node.
*/
pParent = pNode->pParent;
assert( pParent || pNode->iNode==1 );
if( pParent ){
if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
rc = removeNode(pRtree, pNode, iHeight);
}else{
rc = fixBoundingBox(pRtree, pNode);
}
}
return rc;
}
/*
** Insert cell pCell into node pNode. Node pNode is the head of a
** subtree iHeight high (leaf nodes have iHeight==0).
*/
static int rtreeInsertCell(
Rtree *pRtree,
RtreeNode *pNode,
RtreeCell *pCell,
int iHeight
){
int rc = SQLITE_OK;
if( iHeight>0 ){
RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
if( pChild ){
nodeRelease(pRtree, pChild->pParent);
nodeReference(pNode);
pChild->pParent = pNode;
}
}
if( nodeInsertCell(pRtree, pNode, pCell) ){
rc = SplitNode(pRtree, pNode, pCell, iHeight);
}else{
rc = AdjustTree(pRtree, pNode, pCell);
if( ALWAYS(rc==SQLITE_OK) ){
if( iHeight==0 ){
rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
}else{
rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
}
}
}
return rc;
}
static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
int ii;
int rc = SQLITE_OK;
int nCell = NCELL(pNode);
for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
RtreeNode *pInsert;
RtreeCell cell;
nodeGetCell(pRtree, pNode, ii, &cell);
/* Find a node to store this cell in. pNode->iNode currently contains
** the height of the sub-tree headed by the cell.
*/
rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert);
if( rc==SQLITE_OK ){
int rc2;
rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode);
rc2 = nodeRelease(pRtree, pInsert);
if( rc==SQLITE_OK ){
rc = rc2;
}
}
}
return rc;
}
/*
** Select a currently unused rowid for a new r-tree record.
*/
static int rtreeNewRowid(Rtree *pRtree, i64 *piRowid){
int rc;
sqlite3_bind_null(pRtree->pWriteRowid, 1);
sqlite3_bind_null(pRtree->pWriteRowid, 2);
sqlite3_step(pRtree->pWriteRowid);