1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sqlite3api/SQLite/rtree.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,2854 @@
1.4 +/*
1.5 +** 2001 September 15
1.6 +**
1.7 +** The author disclaims copyright to this source code. In place of
1.8 +** a legal notice, here is a blessing:
1.9 +**
1.10 +** May you do good and not evil.
1.11 +** May you find forgiveness for yourself and forgive others.
1.12 +** May you share freely, never taking more than you give.
1.13 +**
1.14 +*************************************************************************
1.15 +** This file contains code for implementations of the r-tree and r*-tree
1.16 +** algorithms packaged as an SQLite virtual table module.
1.17 +**
1.18 +** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $
1.19 +*/
1.20 +
1.21 +#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
1.22 +
1.23 +/*
1.24 +** This file contains an implementation of a couple of different variants
1.25 +** of the r-tree algorithm. See the README file for further details. The
1.26 +** same data-structure is used for all, but the algorithms for insert and
1.27 +** delete operations vary. The variants used are selected at compile time
1.28 +** by defining the following symbols:
1.29 +*/
1.30 +
1.31 +/* Either, both or none of the following may be set to activate
1.32 +** r*tree variant algorithms.
1.33 +*/
1.34 +#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
1.35 +#define VARIANT_RSTARTREE_REINSERT 1
1.36 +
1.37 +/*
1.38 +** Exactly one of the following must be set to 1.
1.39 +*/
1.40 +#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
1.41 +#define VARIANT_GUTTMAN_LINEAR_SPLIT 0
1.42 +#define VARIANT_RSTARTREE_SPLIT 1
1.43 +
1.44 +#define VARIANT_GUTTMAN_SPLIT \
1.45 + (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
1.46 +
1.47 +#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
1.48 + #define PickNext QuadraticPickNext
1.49 + #define PickSeeds QuadraticPickSeeds
1.50 + #define AssignCells splitNodeGuttman
1.51 +#endif
1.52 +#if VARIANT_GUTTMAN_LINEAR_SPLIT
1.53 + #define PickNext LinearPickNext
1.54 + #define PickSeeds LinearPickSeeds
1.55 + #define AssignCells splitNodeGuttman
1.56 +#endif
1.57 +#if VARIANT_RSTARTREE_SPLIT
1.58 + #define AssignCells splitNodeStartree
1.59 +#endif
1.60 +
1.61 +
1.62 +#ifndef SQLITE_CORE
1.63 + #include "sqlite3ext.h"
1.64 + SQLITE_EXTENSION_INIT1
1.65 +#else
1.66 + #include "sqlite3.h"
1.67 +#endif
1.68 +
1.69 +#include <string.h>
1.70 +#include <assert.h>
1.71 +
1.72 +#ifndef SQLITE_AMALGAMATION
1.73 +typedef sqlite3_int64 i64;
1.74 +typedef unsigned char u8;
1.75 +typedef unsigned int u32;
1.76 +#endif
1.77 +
1.78 +typedef struct Rtree Rtree;
1.79 +typedef struct RtreeCursor RtreeCursor;
1.80 +typedef struct RtreeNode RtreeNode;
1.81 +typedef struct RtreeCell RtreeCell;
1.82 +typedef struct RtreeConstraint RtreeConstraint;
1.83 +typedef union RtreeCoord RtreeCoord;
1.84 +
1.85 +/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
1.86 +#define RTREE_MAX_DIMENSIONS 5
1.87 +
1.88 +/* Size of hash table Rtree.aHash. This hash table is not expected to
1.89 +** ever contain very many entries, so a fixed number of buckets is
1.90 +** used.
1.91 +*/
1.92 +#define HASHSIZE 128
1.93 +
1.94 +/*
1.95 +** An rtree virtual-table object.
1.96 +*/
1.97 +struct Rtree {
1.98 + sqlite3_vtab base;
1.99 + sqlite3 *db; /* Host database connection */
1.100 + int iNodeSize; /* Size in bytes of each node in the node table */
1.101 + int nDim; /* Number of dimensions */
1.102 + int nBytesPerCell; /* Bytes consumed per cell */
1.103 + int iDepth; /* Current depth of the r-tree structure */
1.104 + char *zDb; /* Name of database containing r-tree table */
1.105 + char *zName; /* Name of r-tree table */
1.106 + RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
1.107 + int nBusy; /* Current number of users of this structure */
1.108 +
1.109 + /* List of nodes removed during a CondenseTree operation. List is
1.110 + ** linked together via the pointer normally used for hash chains -
1.111 + ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
1.112 + ** headed by the node (leaf nodes have RtreeNode.iNode==0).
1.113 + */
1.114 + RtreeNode *pDeleted;
1.115 + int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */
1.116 +
1.117 + /* Statements to read/write/delete a record from xxx_node */
1.118 + sqlite3_stmt *pReadNode;
1.119 + sqlite3_stmt *pWriteNode;
1.120 + sqlite3_stmt *pDeleteNode;
1.121 +
1.122 + /* Statements to read/write/delete a record from xxx_rowid */
1.123 + sqlite3_stmt *pReadRowid;
1.124 + sqlite3_stmt *pWriteRowid;
1.125 + sqlite3_stmt *pDeleteRowid;
1.126 +
1.127 + /* Statements to read/write/delete a record from xxx_parent */
1.128 + sqlite3_stmt *pReadParent;
1.129 + sqlite3_stmt *pWriteParent;
1.130 + sqlite3_stmt *pDeleteParent;
1.131 +
1.132 + int eCoordType;
1.133 +};
1.134 +
1.135 +/* Possible values for eCoordType: */
1.136 +#define RTREE_COORD_REAL32 0
1.137 +#define RTREE_COORD_INT32 1
1.138 +
1.139 +/*
1.140 +** The minimum number of cells allowed for a node is a third of the
1.141 +** maximum. In Gutman's notation:
1.142 +**
1.143 +** m = M/3
1.144 +**
1.145 +** If an R*-tree "Reinsert" operation is required, the same number of
1.146 +** cells are removed from the overfull node and reinserted into the tree.
1.147 +*/
1.148 +#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
1.149 +#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
1.150 +#define RTREE_MAXCELLS 51
1.151 +
1.152 +/*
1.153 +** An rtree cursor object.
1.154 +*/
1.155 +struct RtreeCursor {
1.156 + sqlite3_vtab_cursor base;
1.157 + RtreeNode *pNode; /* Node cursor is currently pointing at */
1.158 + int iCell; /* Index of current cell in pNode */
1.159 + int iStrategy; /* Copy of idxNum search parameter */
1.160 + int nConstraint; /* Number of entries in aConstraint */
1.161 + RtreeConstraint *aConstraint; /* Search constraints. */
1.162 +};
1.163 +
1.164 +union RtreeCoord {
1.165 + float f;
1.166 + int i;
1.167 +};
1.168 +
1.169 +/*
1.170 +** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
1.171 +** formatted as a double. This macro assumes that local variable pRtree points
1.172 +** to the Rtree structure associated with the RtreeCoord.
1.173 +*/
1.174 +#define DCOORD(coord) ( \
1.175 + (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
1.176 + ((double)coord.f) : \
1.177 + ((double)coord.i) \
1.178 +)
1.179 +
1.180 +/*
1.181 +** A search constraint.
1.182 +*/
1.183 +struct RtreeConstraint {
1.184 + int iCoord; /* Index of constrained coordinate */
1.185 + int op; /* Constraining operation */
1.186 + double rValue; /* Constraint value. */
1.187 +};
1.188 +
1.189 +/* Possible values for RtreeConstraint.op */
1.190 +#define RTREE_EQ 0x41
1.191 +#define RTREE_LE 0x42
1.192 +#define RTREE_LT 0x43
1.193 +#define RTREE_GE 0x44
1.194 +#define RTREE_GT 0x45
1.195 +
1.196 +/*
1.197 +** An rtree structure node.
1.198 +**
1.199 +** Data format (RtreeNode.zData):
1.200 +**
1.201 +** 1. If the node is the root node (node 1), then the first 2 bytes
1.202 +** of the node contain the tree depth as a big-endian integer.
1.203 +** For non-root nodes, the first 2 bytes are left unused.
1.204 +**
1.205 +** 2. The next 2 bytes contain the number of entries currently
1.206 +** stored in the node.
1.207 +**
1.208 +** 3. The remainder of the node contains the node entries. Each entry
1.209 +** consists of a single 8-byte integer followed by an even number
1.210 +** of 4-byte coordinates. For leaf nodes the integer is the rowid
1.211 +** of a record. For internal nodes it is the node number of a
1.212 +** child page.
1.213 +*/
1.214 +struct RtreeNode {
1.215 + RtreeNode *pParent; /* Parent node */
1.216 + i64 iNode;
1.217 + int nRef;
1.218 + int isDirty;
1.219 + u8 *zData;
1.220 + RtreeNode *pNext; /* Next node in this hash chain */
1.221 +};
1.222 +#define NCELL(pNode) readInt16(&(pNode)->zData[2])
1.223 +
1.224 +/*
1.225 +** Structure to store a deserialized rtree record.
1.226 +*/
1.227 +struct RtreeCell {
1.228 + i64 iRowid;
1.229 + RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
1.230 +};
1.231 +
1.232 +#define MAX(x,y) ((x) < (y) ? (y) : (x))
1.233 +#define MIN(x,y) ((x) > (y) ? (y) : (x))
1.234 +
1.235 +/*
1.236 +** Functions to deserialize a 16 bit integer, 32 bit real number and
1.237 +** 64 bit integer. The deserialized value is returned.
1.238 +*/
1.239 +static int readInt16(u8 *p){
1.240 + return (p[0]<<8) + p[1];
1.241 +}
1.242 +static void readCoord(u8 *p, RtreeCoord *pCoord){
1.243 + u32 i = (
1.244 + (((u32)p[0]) << 24) +
1.245 + (((u32)p[1]) << 16) +
1.246 + (((u32)p[2]) << 8) +
1.247 + (((u32)p[3]) << 0)
1.248 + );
1.249 + *(u32 *)pCoord = i;
1.250 +}
1.251 +static i64 readInt64(u8 *p){
1.252 + return (
1.253 + (((i64)p[0]) << 56) +
1.254 + (((i64)p[1]) << 48) +
1.255 + (((i64)p[2]) << 40) +
1.256 + (((i64)p[3]) << 32) +
1.257 + (((i64)p[4]) << 24) +
1.258 + (((i64)p[5]) << 16) +
1.259 + (((i64)p[6]) << 8) +
1.260 + (((i64)p[7]) << 0)
1.261 + );
1.262 +}
1.263 +
1.264 +/*
1.265 +** Functions to serialize a 16 bit integer, 32 bit real number and
1.266 +** 64 bit integer. The value returned is the number of bytes written
1.267 +** to the argument buffer (always 2, 4 and 8 respectively).
1.268 +*/
1.269 +static int writeInt16(u8 *p, int i){
1.270 + p[0] = (i>> 8)&0xFF;
1.271 + p[1] = (i>> 0)&0xFF;
1.272 + return 2;
1.273 +}
1.274 +static int writeCoord(u8 *p, RtreeCoord *pCoord){
1.275 + u32 i;
1.276 + assert( sizeof(RtreeCoord)==4 );
1.277 + assert( sizeof(u32)==4 );
1.278 + i = *(u32 *)pCoord;
1.279 + p[0] = (i>>24)&0xFF;
1.280 + p[1] = (i>>16)&0xFF;
1.281 + p[2] = (i>> 8)&0xFF;
1.282 + p[3] = (i>> 0)&0xFF;
1.283 + return 4;
1.284 +}
1.285 +static int writeInt64(u8 *p, i64 i){
1.286 + p[0] = (i>>56)&0xFF;
1.287 + p[1] = (i>>48)&0xFF;
1.288 + p[2] = (i>>40)&0xFF;
1.289 + p[3] = (i>>32)&0xFF;
1.290 + p[4] = (i>>24)&0xFF;
1.291 + p[5] = (i>>16)&0xFF;
1.292 + p[6] = (i>> 8)&0xFF;
1.293 + p[7] = (i>> 0)&0xFF;
1.294 + return 8;
1.295 +}
1.296 +
1.297 +/*
1.298 +** Increment the reference count of node p.
1.299 +*/
1.300 +static void nodeReference(RtreeNode *p){
1.301 + if( p ){
1.302 + p->nRef++;
1.303 + }
1.304 +}
1.305 +
1.306 +/*
1.307 +** Clear the content of node p (set all bytes to 0x00).
1.308 +*/
1.309 +static void nodeZero(Rtree *pRtree, RtreeNode *p){
1.310 + if( p ){
1.311 + memset(&p->zData[2], 0, pRtree->iNodeSize-2);
1.312 + p->isDirty = 1;
1.313 + }
1.314 +}
1.315 +
1.316 +/*
1.317 +** Given a node number iNode, return the corresponding key to use
1.318 +** in the Rtree.aHash table.
1.319 +*/
1.320 +static int nodeHash(i64 iNode){
1.321 + return (
1.322 + (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^
1.323 + (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
1.324 + ) % HASHSIZE;
1.325 +}
1.326 +
1.327 +/*
1.328 +** Search the node hash table for node iNode. If found, return a pointer
1.329 +** to it. Otherwise, return 0.
1.330 +*/
1.331 +static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
1.332 + RtreeNode *p;
1.333 + assert( iNode!=0 );
1.334 + for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
1.335 + return p;
1.336 +}
1.337 +
1.338 +/*
1.339 +** Add node pNode to the node hash table.
1.340 +*/
1.341 +static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
1.342 + if( pNode ){
1.343 + int iHash;
1.344 + assert( pNode->pNext==0 );
1.345 + iHash = nodeHash(pNode->iNode);
1.346 + pNode->pNext = pRtree->aHash[iHash];
1.347 + pRtree->aHash[iHash] = pNode;
1.348 + }
1.349 +}
1.350 +
1.351 +/*
1.352 +** Remove node pNode from the node hash table.
1.353 +*/
1.354 +static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
1.355 + RtreeNode **pp;
1.356 + if( pNode->iNode!=0 ){
1.357 + pp = &pRtree->aHash[nodeHash(pNode->iNode)];
1.358 + for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
1.359 + *pp = pNode->pNext;
1.360 + pNode->pNext = 0;
1.361 + }
1.362 +}
1.363 +
1.364 +/*
1.365 +** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
1.366 +** indicating that node has not yet been assigned a node number. It is
1.367 +** assigned a node number when nodeWrite() is called to write the
1.368 +** node contents out to the database.
1.369 +*/
1.370 +static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){
1.371 + RtreeNode *pNode;
1.372 + pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
1.373 + if( pNode ){
1.374 + memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
1.375 + pNode->zData = (u8 *)&pNode[1];
1.376 + pNode->nRef = 1;
1.377 + pNode->pParent = pParent;
1.378 + pNode->isDirty = 1;
1.379 + nodeReference(pParent);
1.380 + }
1.381 + return pNode;
1.382 +}
1.383 +
1.384 +/*
1.385 +** Obtain a reference to an r-tree node.
1.386 +*/
1.387 +static int
1.388 +nodeAcquire(
1.389 + Rtree *pRtree, /* R-tree structure */
1.390 + i64 iNode, /* Node number to load */
1.391 + RtreeNode *pParent, /* Either the parent node or NULL */
1.392 + RtreeNode **ppNode /* OUT: Acquired node */
1.393 +){
1.394 + int rc;
1.395 + RtreeNode *pNode;
1.396 +
1.397 + /* Check if the requested node is already in the hash table. If so,
1.398 + ** increase its reference count and return it.
1.399 + */
1.400 + if( (pNode = nodeHashLookup(pRtree, iNode)) ){
1.401 + assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
1.402 + if( pParent ){
1.403 + pNode->pParent = pParent;
1.404 + }
1.405 + pNode->nRef++;
1.406 + *ppNode = pNode;
1.407 + return SQLITE_OK;
1.408 + }
1.409 +
1.410 + pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
1.411 + if( !pNode ){
1.412 + *ppNode = 0;
1.413 + return SQLITE_NOMEM;
1.414 + }
1.415 + pNode->pParent = pParent;
1.416 + pNode->zData = (u8 *)&pNode[1];
1.417 + pNode->nRef = 1;
1.418 + pNode->iNode = iNode;
1.419 + pNode->isDirty = 0;
1.420 + pNode->pNext = 0;
1.421 +
1.422 + sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
1.423 + rc = sqlite3_step(pRtree->pReadNode);
1.424 + if( rc==SQLITE_ROW ){
1.425 + const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
1.426 + memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
1.427 + nodeReference(pParent);
1.428 + }else{
1.429 + sqlite3_free(pNode);
1.430 + pNode = 0;
1.431 + }
1.432 +
1.433 + *ppNode = pNode;
1.434 + rc = sqlite3_reset(pRtree->pReadNode);
1.435 +
1.436 + if( rc==SQLITE_OK && iNode==1 ){
1.437 + pRtree->iDepth = readInt16(pNode->zData);
1.438 + }
1.439 +
1.440 + assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );
1.441 + nodeHashInsert(pRtree, pNode);
1.442 +
1.443 + return rc;
1.444 +}
1.445 +
1.446 +/*
1.447 +** Overwrite cell iCell of node pNode with the contents of pCell.
1.448 +*/
1.449 +static void nodeOverwriteCell(
1.450 + Rtree *pRtree,
1.451 + RtreeNode *pNode,
1.452 + RtreeCell *pCell,
1.453 + int iCell
1.454 +){
1.455 + int ii;
1.456 + u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
1.457 + p += writeInt64(p, pCell->iRowid);
1.458 + for(ii=0; ii<(pRtree->nDim*2); ii++){
1.459 + p += writeCoord(p, &pCell->aCoord[ii]);
1.460 + }
1.461 + pNode->isDirty = 1;
1.462 +}
1.463 +
1.464 +/*
1.465 +** Remove cell the cell with index iCell from node pNode.
1.466 +*/
1.467 +static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
1.468 + u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
1.469 + u8 *pSrc = &pDst[pRtree->nBytesPerCell];
1.470 + int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
1.471 + memmove(pDst, pSrc, nByte);
1.472 + writeInt16(&pNode->zData[2], NCELL(pNode)-1);
1.473 + pNode->isDirty = 1;
1.474 +}
1.475 +
1.476 +/*
1.477 +** Insert the contents of cell pCell into node pNode. If the insert
1.478 +** is successful, return SQLITE_OK.
1.479 +**
1.480 +** If there is not enough free space in pNode, return SQLITE_FULL.
1.481 +*/
1.482 +static int
1.483 +nodeInsertCell(
1.484 + Rtree *pRtree,
1.485 + RtreeNode *pNode,
1.486 + RtreeCell *pCell
1.487 +){
1.488 + int nCell; /* Current number of cells in pNode */
1.489 + int nMaxCell; /* Maximum number of cells for pNode */
1.490 +
1.491 + nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
1.492 + nCell = NCELL(pNode);
1.493 +
1.494 + assert(nCell<=nMaxCell);
1.495 +
1.496 + if( nCell<nMaxCell ){
1.497 + nodeOverwriteCell(pRtree, pNode, pCell, nCell);
1.498 + writeInt16(&pNode->zData[2], nCell+1);
1.499 + pNode->isDirty = 1;
1.500 + }
1.501 +
1.502 + return (nCell==nMaxCell);
1.503 +}
1.504 +
1.505 +/*
1.506 +** If the node is dirty, write it out to the database.
1.507 +*/
1.508 +static int
1.509 +nodeWrite(Rtree *pRtree, RtreeNode *pNode){
1.510 + int rc = SQLITE_OK;
1.511 + if( pNode->isDirty ){
1.512 + sqlite3_stmt *p = pRtree->pWriteNode;
1.513 + if( pNode->iNode ){
1.514 + sqlite3_bind_int64(p, 1, pNode->iNode);
1.515 + }else{
1.516 + sqlite3_bind_null(p, 1);
1.517 + }
1.518 + sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
1.519 + sqlite3_step(p);
1.520 + pNode->isDirty = 0;
1.521 + rc = sqlite3_reset(p);
1.522 + if( pNode->iNode==0 && rc==SQLITE_OK ){
1.523 + pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
1.524 + nodeHashInsert(pRtree, pNode);
1.525 + }
1.526 + }
1.527 + return rc;
1.528 +}
1.529 +
1.530 +/*
1.531 +** Release a reference to a node. If the node is dirty and the reference
1.532 +** count drops to zero, the node data is written to the database.
1.533 +*/
1.534 +static int
1.535 +nodeRelease(Rtree *pRtree, RtreeNode *pNode){
1.536 + int rc = SQLITE_OK;
1.537 + if( pNode ){
1.538 + assert( pNode->nRef>0 );
1.539 + pNode->nRef--;
1.540 + if( pNode->nRef==0 ){
1.541 + if( pNode->iNode==1 ){
1.542 + pRtree->iDepth = -1;
1.543 + }
1.544 + if( pNode->pParent ){
1.545 + rc = nodeRelease(pRtree, pNode->pParent);
1.546 + }
1.547 + if( rc==SQLITE_OK ){
1.548 + rc = nodeWrite(pRtree, pNode);
1.549 + }
1.550 + nodeHashDelete(pRtree, pNode);
1.551 + sqlite3_free(pNode);
1.552 + }
1.553 + }
1.554 + return rc;
1.555 +}
1.556 +
1.557 +/*
1.558 +** Return the 64-bit integer value associated with cell iCell of
1.559 +** node pNode. If pNode is a leaf node, this is a rowid. If it is
1.560 +** an internal node, then the 64-bit integer is a child page number.
1.561 +*/
1.562 +static i64 nodeGetRowid(
1.563 + Rtree *pRtree,
1.564 + RtreeNode *pNode,
1.565 + int iCell
1.566 +){
1.567 + assert( iCell<NCELL(pNode) );
1.568 + return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
1.569 +}
1.570 +
1.571 +/*
1.572 +** Return coordinate iCoord from cell iCell in node pNode.
1.573 +*/
1.574 +static void nodeGetCoord(
1.575 + Rtree *pRtree,
1.576 + RtreeNode *pNode,
1.577 + int iCell,
1.578 + int iCoord,
1.579 + RtreeCoord *pCoord /* Space to write result to */
1.580 +){
1.581 + readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
1.582 +}
1.583 +
1.584 +/*
1.585 +** Deserialize cell iCell of node pNode. Populate the structure pointed
1.586 +** to by pCell with the results.
1.587 +*/
1.588 +static void nodeGetCell(
1.589 + Rtree *pRtree,
1.590 + RtreeNode *pNode,
1.591 + int iCell,
1.592 + RtreeCell *pCell
1.593 +){
1.594 + int ii;
1.595 + pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
1.596 + for(ii=0; ii<pRtree->nDim*2; ii++){
1.597 + nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
1.598 + }
1.599 +}
1.600 +
1.601 +
1.602 +/* Forward declaration for the function that does the work of
1.603 +** the virtual table module xCreate() and xConnect() methods.
1.604 +*/
1.605 +static int rtreeInit(
1.606 + sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int
1.607 +);
1.608 +
1.609 +/*
1.610 +** Rtree virtual table module xCreate method.
1.611 +*/
1.612 +static int rtreeCreate(
1.613 + sqlite3 *db,
1.614 + void *pAux,
1.615 + int argc, const char *const*argv,
1.616 + sqlite3_vtab **ppVtab,
1.617 + char **pzErr
1.618 +){
1.619 + return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux);
1.620 +}
1.621 +
1.622 +/*
1.623 +** Rtree virtual table module xConnect method.
1.624 +*/
1.625 +static int rtreeConnect(
1.626 + sqlite3 *db,
1.627 + void *pAux,
1.628 + int argc, const char *const*argv,
1.629 + sqlite3_vtab **ppVtab,
1.630 + char **pzErr
1.631 +){
1.632 + return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux);
1.633 +}
1.634 +
1.635 +/*
1.636 +** Increment the r-tree reference count.
1.637 +*/
1.638 +static void rtreeReference(Rtree *pRtree){
1.639 + pRtree->nBusy++;
1.640 +}
1.641 +
1.642 +/*
1.643 +** Decrement the r-tree reference count. When the reference count reaches
1.644 +** zero the structure is deleted.
1.645 +*/
1.646 +static void rtreeRelease(Rtree *pRtree){
1.647 + pRtree->nBusy--;
1.648 + if( pRtree->nBusy==0 ){
1.649 + sqlite3_finalize(pRtree->pReadNode);
1.650 + sqlite3_finalize(pRtree->pWriteNode);
1.651 + sqlite3_finalize(pRtree->pDeleteNode);
1.652 + sqlite3_finalize(pRtree->pReadRowid);
1.653 + sqlite3_finalize(pRtree->pWriteRowid);
1.654 + sqlite3_finalize(pRtree->pDeleteRowid);
1.655 + sqlite3_finalize(pRtree->pReadParent);
1.656 + sqlite3_finalize(pRtree->pWriteParent);
1.657 + sqlite3_finalize(pRtree->pDeleteParent);
1.658 + sqlite3_free(pRtree);
1.659 + }
1.660 +}
1.661 +
1.662 +/*
1.663 +** Rtree virtual table module xDisconnect method.
1.664 +*/
1.665 +static int rtreeDisconnect(sqlite3_vtab *pVtab){
1.666 + rtreeRelease((Rtree *)pVtab);
1.667 + return SQLITE_OK;
1.668 +}
1.669 +
1.670 +/*
1.671 +** Rtree virtual table module xDestroy method.
1.672 +*/
1.673 +static int rtreeDestroy(sqlite3_vtab *pVtab){
1.674 + Rtree *pRtree = (Rtree *)pVtab;
1.675 + int rc;
1.676 + char *zCreate = sqlite3_mprintf(
1.677 + "DROP TABLE '%q'.'%q_node';"
1.678 + "DROP TABLE '%q'.'%q_rowid';"
1.679 + "DROP TABLE '%q'.'%q_parent';",
1.680 + pRtree->zDb, pRtree->zName,
1.681 + pRtree->zDb, pRtree->zName,
1.682 + pRtree->zDb, pRtree->zName
1.683 + );
1.684 + if( !zCreate ){
1.685 + rc = SQLITE_NOMEM;
1.686 + }else{
1.687 + rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
1.688 + sqlite3_free(zCreate);
1.689 + }
1.690 + if( rc==SQLITE_OK ){
1.691 + rtreeRelease(pRtree);
1.692 + }
1.693 +
1.694 + return rc;
1.695 +}
1.696 +
1.697 +/*
1.698 +** Rtree virtual table module xOpen method.
1.699 +*/
1.700 +static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
1.701 + int rc = SQLITE_NOMEM;
1.702 + RtreeCursor *pCsr;
1.703 +
1.704 + pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));
1.705 + if( pCsr ){
1.706 + memset(pCsr, 0, sizeof(RtreeCursor));
1.707 + pCsr->base.pVtab = pVTab;
1.708 + rc = SQLITE_OK;
1.709 + }
1.710 + *ppCursor = (sqlite3_vtab_cursor *)pCsr;
1.711 +
1.712 + return rc;
1.713 +}
1.714 +
1.715 +/*
1.716 +** Rtree virtual table module xClose method.
1.717 +*/
1.718 +static int rtreeClose(sqlite3_vtab_cursor *cur){
1.719 + Rtree *pRtree = (Rtree *)(cur->pVtab);
1.720 + int rc;
1.721 + RtreeCursor *pCsr = (RtreeCursor *)cur;
1.722 + sqlite3_free(pCsr->aConstraint);
1.723 + rc = nodeRelease(pRtree, pCsr->pNode);
1.724 + sqlite3_free(pCsr);
1.725 + return rc;
1.726 +}
1.727 +
1.728 +/*
1.729 +** Rtree virtual table module xEof method.
1.730 +**
1.731 +** Return non-zero if the cursor does not currently point to a valid
1.732 +** record (i.e if the scan has finished), or zero otherwise.
1.733 +*/
1.734 +static int rtreeEof(sqlite3_vtab_cursor *cur){
1.735 + RtreeCursor *pCsr = (RtreeCursor *)cur;
1.736 + return (pCsr->pNode==0);
1.737 +}
1.738 +
1.739 +/*
1.740 +** Cursor pCursor currently points to a cell in a non-leaf page.
1.741 +** Return true if the sub-tree headed by the cell is filtered
1.742 +** (excluded) by the constraints in the pCursor->aConstraint[]
1.743 +** array, or false otherwise.
1.744 +*/
1.745 +static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){
1.746 + RtreeCell cell;
1.747 + int ii;
1.748 + int bRes = 0;
1.749 +
1.750 + nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
1.751 + for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
1.752 + RtreeConstraint *p = &pCursor->aConstraint[ii];
1.753 + double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
1.754 + double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
1.755 +
1.756 + assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
1.757 + || p->op==RTREE_GT || p->op==RTREE_EQ
1.758 + );
1.759 +
1.760 + switch( p->op ){
1.761 + case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break;
1.762 + case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break;
1.763 + case RTREE_EQ:
1.764 + bRes = (p->rValue>cell_max || p->rValue<cell_min);
1.765 + break;
1.766 + }
1.767 + }
1.768 +
1.769 + return bRes;
1.770 +}
1.771 +
1.772 +/*
1.773 +** Return true if the cell that cursor pCursor currently points to
1.774 +** would be filtered (excluded) by the constraints in the
1.775 +** pCursor->aConstraint[] array, or false otherwise.
1.776 +**
1.777 +** This function assumes that the cell is part of a leaf node.
1.778 +*/
1.779 +static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){
1.780 + RtreeCell cell;
1.781 + int ii;
1.782 +
1.783 + nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
1.784 + for(ii=0; ii<pCursor->nConstraint; ii++){
1.785 + RtreeConstraint *p = &pCursor->aConstraint[ii];
1.786 + double coord = DCOORD(cell.aCoord[p->iCoord]);
1.787 + int res;
1.788 + assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
1.789 + || p->op==RTREE_GT || p->op==RTREE_EQ
1.790 + );
1.791 + switch( p->op ){
1.792 + case RTREE_LE: res = (coord<=p->rValue); break;
1.793 + case RTREE_LT: res = (coord<p->rValue); break;
1.794 + case RTREE_GE: res = (coord>=p->rValue); break;
1.795 + case RTREE_GT: res = (coord>p->rValue); break;
1.796 + case RTREE_EQ: res = (coord==p->rValue); break;
1.797 + }
1.798 +
1.799 + if( !res ) return 1;
1.800 + }
1.801 +
1.802 + return 0;
1.803 +}
1.804 +
1.805 +/*
1.806 +** Cursor pCursor currently points at a node that heads a sub-tree of
1.807 +** height iHeight (if iHeight==0, then the node is a leaf). Descend
1.808 +** to point to the left-most cell of the sub-tree that matches the
1.809 +** configured constraints.
1.810 +*/
1.811 +static int descendToCell(
1.812 + Rtree *pRtree,
1.813 + RtreeCursor *pCursor,
1.814 + int iHeight,
1.815 + int *pEof /* OUT: Set to true if cannot descend */
1.816 +){
1.817 + int isEof;
1.818 + int rc;
1.819 + int ii;
1.820 + RtreeNode *pChild;
1.821 + sqlite3_int64 iRowid;
1.822 +
1.823 + RtreeNode *pSavedNode = pCursor->pNode;
1.824 + int iSavedCell = pCursor->iCell;
1.825 +
1.826 + assert( iHeight>=0 );
1.827 +
1.828 + if( iHeight==0 ){
1.829 + isEof = testRtreeEntry(pRtree, pCursor);
1.830 + }else{
1.831 + isEof = testRtreeCell(pRtree, pCursor);
1.832 + }
1.833 + if( isEof || iHeight==0 ){
1.834 + *pEof = isEof;
1.835 + return SQLITE_OK;
1.836 + }
1.837 +
1.838 + iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
1.839 + rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
1.840 + if( rc!=SQLITE_OK ){
1.841 + return rc;
1.842 + }
1.843 +
1.844 + nodeRelease(pRtree, pCursor->pNode);
1.845 + pCursor->pNode = pChild;
1.846 + isEof = 1;
1.847 + for(ii=0; isEof && ii<NCELL(pChild); ii++){
1.848 + pCursor->iCell = ii;
1.849 + rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
1.850 + if( rc!=SQLITE_OK ){
1.851 + return rc;
1.852 + }
1.853 + }
1.854 +
1.855 + if( isEof ){
1.856 + assert( pCursor->pNode==pChild );
1.857 + nodeReference(pSavedNode);
1.858 + nodeRelease(pRtree, pChild);
1.859 + pCursor->pNode = pSavedNode;
1.860 + pCursor->iCell = iSavedCell;
1.861 + }
1.862 +
1.863 + *pEof = isEof;
1.864 + return SQLITE_OK;
1.865 +}
1.866 +
1.867 +/*
1.868 +** One of the cells in node pNode is guaranteed to have a 64-bit
1.869 +** integer value equal to iRowid. Return the index of this cell.
1.870 +*/
1.871 +static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){
1.872 + int ii;
1.873 + for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
1.874 + assert( ii<(NCELL(pNode)-1) );
1.875 + }
1.876 + return ii;
1.877 +}
1.878 +
1.879 +/*
1.880 +** Return the index of the cell containing a pointer to node pNode
1.881 +** in its parent. If pNode is the root node, return -1.
1.882 +*/
1.883 +static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){
1.884 + RtreeNode *pParent = pNode->pParent;
1.885 + if( pParent ){
1.886 + return nodeRowidIndex(pRtree, pParent, pNode->iNode);
1.887 + }
1.888 + return -1;
1.889 +}
1.890 +
1.891 +/*
1.892 +** Rtree virtual table module xNext method.
1.893 +*/
1.894 +static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
1.895 + Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
1.896 + RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1.897 + int rc = SQLITE_OK;
1.898 +
1.899 + if( pCsr->iStrategy==1 ){
1.900 + /* This "scan" is a direct lookup by rowid. There is no next entry. */
1.901 + nodeRelease(pRtree, pCsr->pNode);
1.902 + pCsr->pNode = 0;
1.903 + }
1.904 +
1.905 + else if( pCsr->pNode ){
1.906 + /* Move to the next entry that matches the configured constraints. */
1.907 + int iHeight = 0;
1.908 + while( pCsr->pNode ){
1.909 + RtreeNode *pNode = pCsr->pNode;
1.910 + int nCell = NCELL(pNode);
1.911 + for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
1.912 + int isEof;
1.913 + rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
1.914 + if( rc!=SQLITE_OK || !isEof ){
1.915 + return rc;
1.916 + }
1.917 + }
1.918 + pCsr->pNode = pNode->pParent;
1.919 + pCsr->iCell = nodeParentIndex(pRtree, pNode);
1.920 + nodeReference(pCsr->pNode);
1.921 + nodeRelease(pRtree, pNode);
1.922 + iHeight++;
1.923 + }
1.924 + }
1.925 +
1.926 + return rc;
1.927 +}
1.928 +
1.929 +/*
1.930 +** Rtree virtual table module xRowid method.
1.931 +*/
1.932 +static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
1.933 + Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1.934 + RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1.935 +
1.936 + assert(pCsr->pNode);
1.937 + *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1.938 +
1.939 + return SQLITE_OK;
1.940 +}
1.941 +
1.942 +/*
1.943 +** Rtree virtual table module xColumn method.
1.944 +*/
1.945 +static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1.946 + Rtree *pRtree = (Rtree *)cur->pVtab;
1.947 + RtreeCursor *pCsr = (RtreeCursor *)cur;
1.948 +
1.949 + if( i==0 ){
1.950 + i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1.951 + sqlite3_result_int64(ctx, iRowid);
1.952 + }else{
1.953 + RtreeCoord c;
1.954 + nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
1.955 + if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1.956 + sqlite3_result_double(ctx, c.f);
1.957 + }else{
1.958 + assert( pRtree->eCoordType==RTREE_COORD_INT32 );
1.959 + sqlite3_result_int(ctx, c.i);
1.960 + }
1.961 + }
1.962 +
1.963 + return SQLITE_OK;
1.964 +}
1.965 +
1.966 +/*
1.967 +** Use nodeAcquire() to obtain the leaf node containing the record with
1.968 +** rowid iRowid. If successful, set *ppLeaf to point to the node and
1.969 +** return SQLITE_OK. If there is no such record in the table, set
1.970 +** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
1.971 +** to zero and return an SQLite error code.
1.972 +*/
1.973 +static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
1.974 + int rc;
1.975 + *ppLeaf = 0;
1.976 + sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
1.977 + if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
1.978 + i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
1.979 + rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
1.980 + sqlite3_reset(pRtree->pReadRowid);
1.981 + }else{
1.982 + rc = sqlite3_reset(pRtree->pReadRowid);
1.983 + }
1.984 + return rc;
1.985 +}
1.986 +
1.987 +
1.988 +/*
1.989 +** Rtree virtual table module xFilter method.
1.990 +*/
1.991 +static int rtreeFilter(
1.992 + sqlite3_vtab_cursor *pVtabCursor,
1.993 + int idxNum, const char *idxStr,
1.994 + int argc, sqlite3_value **argv
1.995 +){
1.996 + Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1.997 + RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1.998 +
1.999 + RtreeNode *pRoot = 0;
1.1000 + int ii;
1.1001 + int rc = SQLITE_OK;
1.1002 +
1.1003 + rtreeReference(pRtree);
1.1004 +
1.1005 + sqlite3_free(pCsr->aConstraint);
1.1006 + pCsr->aConstraint = 0;
1.1007 + pCsr->iStrategy = idxNum;
1.1008 +
1.1009 + if( idxNum==1 ){
1.1010 + /* Special case - lookup by rowid. */
1.1011 + RtreeNode *pLeaf; /* Leaf on which the required cell resides */
1.1012 + i64 iRowid = sqlite3_value_int64(argv[0]);
1.1013 + rc = findLeafNode(pRtree, iRowid, &pLeaf);
1.1014 + pCsr->pNode = pLeaf;
1.1015 + if( pLeaf && rc==SQLITE_OK ){
1.1016 + pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
1.1017 + }
1.1018 + }else{
1.1019 + /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1.1020 + ** with the configured constraints.
1.1021 + */
1.1022 + if( argc>0 ){
1.1023 + pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
1.1024 + pCsr->nConstraint = argc;
1.1025 + if( !pCsr->aConstraint ){
1.1026 + rc = SQLITE_NOMEM;
1.1027 + }else{
1.1028 + assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
1.1029 + for(ii=0; ii<argc; ii++){
1.1030 + RtreeConstraint *p = &pCsr->aConstraint[ii];
1.1031 + p->op = idxStr[ii*2];
1.1032 + p->iCoord = idxStr[ii*2+1]-'a';
1.1033 + p->rValue = sqlite3_value_double(argv[ii]);
1.1034 + }
1.1035 + }
1.1036 + }
1.1037 +
1.1038 + if( rc==SQLITE_OK ){
1.1039 + pCsr->pNode = 0;
1.1040 + rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1.1041 + }
1.1042 + if( rc==SQLITE_OK ){
1.1043 + int isEof = 1;
1.1044 + int nCell = NCELL(pRoot);
1.1045 + pCsr->pNode = pRoot;
1.1046 + for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
1.1047 + assert( pCsr->pNode==pRoot );
1.1048 + rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
1.1049 + if( !isEof ){
1.1050 + break;
1.1051 + }
1.1052 + }
1.1053 + if( rc==SQLITE_OK && isEof ){
1.1054 + assert( pCsr->pNode==pRoot );
1.1055 + nodeRelease(pRtree, pRoot);
1.1056 + pCsr->pNode = 0;
1.1057 + }
1.1058 + assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
1.1059 + }
1.1060 + }
1.1061 +
1.1062 + rtreeRelease(pRtree);
1.1063 + return rc;
1.1064 +}
1.1065 +
1.1066 +/*
1.1067 +** Rtree virtual table module xBestIndex method. There are three
1.1068 +** table scan strategies to choose from (in order from most to
1.1069 +** least desirable):
1.1070 +**
1.1071 +** idxNum idxStr Strategy
1.1072 +** ------------------------------------------------
1.1073 +** 1 Unused Direct lookup by rowid.
1.1074 +** 2 See below R-tree query.
1.1075 +** 3 Unused Full table scan.
1.1076 +** ------------------------------------------------
1.1077 +**
1.1078 +** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
1.1079 +** 2 is used, idxStr is formatted to contain 2 bytes for each
1.1080 +** constraint used. The first two bytes of idxStr correspond to
1.1081 +** the constraint in sqlite3_index_info.aConstraintUsage[] with
1.1082 +** (argvIndex==1) etc.
1.1083 +**
1.1084 +** The first of each pair of bytes in idxStr identifies the constraint
1.1085 +** operator as follows:
1.1086 +**
1.1087 +** Operator Byte Value
1.1088 +** ----------------------
1.1089 +** = 0x41 ('A')
1.1090 +** <= 0x42 ('B')
1.1091 +** < 0x43 ('C')
1.1092 +** >= 0x44 ('D')
1.1093 +** > 0x45 ('E')
1.1094 +** ----------------------
1.1095 +**
1.1096 +** The second of each pair of bytes identifies the coordinate column
1.1097 +** to which the constraint applies. The leftmost coordinate column
1.1098 +** is 'a', the second from the left 'b' etc.
1.1099 +*/
1.1100 +static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
1.1101 + int rc = SQLITE_OK;
1.1102 + int ii, cCol;
1.1103 +
1.1104 + int iIdx = 0;
1.1105 + char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
1.1106 + memset(zIdxStr, 0, sizeof(zIdxStr));
1.1107 +
1.1108 + assert( pIdxInfo->idxStr==0 );
1.1109 + for(ii=0; ii<pIdxInfo->nConstraint; ii++){
1.1110 + struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
1.1111 +
1.1112 + if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
1.1113 + /* We have an equality constraint on the rowid. Use strategy 1. */
1.1114 + int jj;
1.1115 + for(jj=0; jj<ii; jj++){
1.1116 + pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
1.1117 + pIdxInfo->aConstraintUsage[jj].omit = 0;
1.1118 + }
1.1119 + pIdxInfo->idxNum = 1;
1.1120 + pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
1.1121 + pIdxInfo->aConstraintUsage[jj].omit = 1;
1.1122 +
1.1123 + /* This strategy involves a two rowid lookups on an B-Tree structures
1.1124 + ** and then a linear search of an R-Tree node. This should be
1.1125 + ** considered almost as quick as a direct rowid lookup (for which
1.1126 + ** sqlite uses an internal cost of 0.0).
1.1127 + */
1.1128 + pIdxInfo->estimatedCost = 10.0;
1.1129 + return SQLITE_OK;
1.1130 + }
1.1131 +
1.1132 + if( p->usable && p->iColumn>0 ){
1.1133 + u8 op = 0;
1.1134 + switch( p->op ){
1.1135 + case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
1.1136 + case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
1.1137 + case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
1.1138 + case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
1.1139 + case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
1.1140 + }
1.1141 + if( op ){
1.1142 + /* Make sure this particular constraint has not been used before.
1.1143 + ** If it has been used before, ignore it.
1.1144 + **
1.1145 + ** A <= or < can be used if there is a prior >= or >.
1.1146 + ** A >= or > can be used if there is a prior < or <=.
1.1147 + ** A <= or < is disqualified if there is a prior <=, <, or ==.
1.1148 + ** A >= or > is disqualified if there is a prior >=, >, or ==.
1.1149 + ** A == is disqualifed if there is any prior constraint.
1.1150 + */
1.1151 + int j, opmsk;
1.1152 + static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
1.1153 + assert( compatible[RTREE_EQ & 7]==0 );
1.1154 + assert( compatible[RTREE_LT & 7]==1 );
1.1155 + assert( compatible[RTREE_LE & 7]==1 );
1.1156 + assert( compatible[RTREE_GT & 7]==2 );
1.1157 + assert( compatible[RTREE_GE & 7]==2 );
1.1158 + cCol = p->iColumn - 1 + 'a';
1.1159 + opmsk = compatible[op & 7];
1.1160 + for(j=0; j<iIdx; j+=2){
1.1161 + if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
1.1162 + op = 0;
1.1163 + break;
1.1164 + }
1.1165 + }
1.1166 + }
1.1167 + if( op ){
1.1168 + assert( iIdx<sizeof(zIdxStr)-1 );
1.1169 + zIdxStr[iIdx++] = op;
1.1170 + zIdxStr[iIdx++] = cCol;
1.1171 + pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
1.1172 + pIdxInfo->aConstraintUsage[ii].omit = 1;
1.1173 + }
1.1174 + }
1.1175 + }
1.1176 +
1.1177 + pIdxInfo->idxNum = 2;
1.1178 + pIdxInfo->needToFreeIdxStr = 1;
1.1179 + if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
1.1180 + return SQLITE_NOMEM;
1.1181 + }
1.1182 + assert( iIdx>=0 );
1.1183 + pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
1.1184 + return rc;
1.1185 +}
1.1186 +
1.1187 +/*
1.1188 +** Return the N-dimensional volumn of the cell stored in *p.
1.1189 +*/
1.1190 +static float cellArea(Rtree *pRtree, RtreeCell *p){
1.1191 + float area = 1.0;
1.1192 + int ii;
1.1193 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.1194 + area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
1.1195 + }
1.1196 + return area;
1.1197 +}
1.1198 +
1.1199 +/*
1.1200 +** Return the margin length of cell p. The margin length is the sum
1.1201 +** of the objects size in each dimension.
1.1202 +*/
1.1203 +static float cellMargin(Rtree *pRtree, RtreeCell *p){
1.1204 + float margin = 0.0;
1.1205 + int ii;
1.1206 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.1207 + margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
1.1208 + }
1.1209 + return margin;
1.1210 +}
1.1211 +
1.1212 +/*
1.1213 +** Store the union of cells p1 and p2 in p1.
1.1214 +*/
1.1215 +static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1.1216 + int ii;
1.1217 + if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1.1218 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.1219 + p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
1.1220 + p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
1.1221 + }
1.1222 + }else{
1.1223 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.1224 + p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
1.1225 + p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
1.1226 + }
1.1227 + }
1.1228 +}
1.1229 +
1.1230 +/*
1.1231 +** Return true if the area covered by p2 is a subset of the area covered
1.1232 +** by p1. False otherwise.
1.1233 +*/
1.1234 +static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
1.1235 + int ii;
1.1236 + int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
1.1237 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.1238 + RtreeCoord *a1 = &p1->aCoord[ii];
1.1239 + RtreeCoord *a2 = &p2->aCoord[ii];
1.1240 + if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f))
1.1241 + || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i))
1.1242 + ){
1.1243 + return 0;
1.1244 + }
1.1245 + }
1.1246 + return 1;
1.1247 +}
1.1248 +
1.1249 +/*
1.1250 +** Return the amount cell p would grow by if it were unioned with pCell.
1.1251 +*/
1.1252 +static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
1.1253 + float area;
1.1254 + RtreeCell cell;
1.1255 + memcpy(&cell, p, sizeof(RtreeCell));
1.1256 + area = cellArea(pRtree, &cell);
1.1257 + cellUnion(pRtree, &cell, pCell);
1.1258 + return (cellArea(pRtree, &cell)-area);
1.1259 +}
1.1260 +
1.1261 +#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
1.1262 +static float cellOverlap(
1.1263 + Rtree *pRtree,
1.1264 + RtreeCell *p,
1.1265 + RtreeCell *aCell,
1.1266 + int nCell,
1.1267 + int iExclude
1.1268 +){
1.1269 + int ii;
1.1270 + float overlap = 0.0;
1.1271 + for(ii=0; ii<nCell; ii++){
1.1272 + if( ii!=iExclude ){
1.1273 + int jj;
1.1274 + float o = 1.0;
1.1275 + for(jj=0; jj<(pRtree->nDim*2); jj+=2){
1.1276 + double x1;
1.1277 + double x2;
1.1278 +
1.1279 + x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
1.1280 + x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
1.1281 +
1.1282 + if( x2<x1 ){
1.1283 + o = 0.0;
1.1284 + break;
1.1285 + }else{
1.1286 + o = o * (x2-x1);
1.1287 + }
1.1288 + }
1.1289 + overlap += o;
1.1290 + }
1.1291 + }
1.1292 + return overlap;
1.1293 +}
1.1294 +#endif
1.1295 +
1.1296 +#if VARIANT_RSTARTREE_CHOOSESUBTREE
1.1297 +static float cellOverlapEnlargement(
1.1298 + Rtree *pRtree,
1.1299 + RtreeCell *p,
1.1300 + RtreeCell *pInsert,
1.1301 + RtreeCell *aCell,
1.1302 + int nCell,
1.1303 + int iExclude
1.1304 +){
1.1305 + float before;
1.1306 + float after;
1.1307 + before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1.1308 + cellUnion(pRtree, p, pInsert);
1.1309 + after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
1.1310 + return after-before;
1.1311 +}
1.1312 +#endif
1.1313 +
1.1314 +
1.1315 +/*
1.1316 +** This function implements the ChooseLeaf algorithm from Gutman[84].
1.1317 +** ChooseSubTree in r*tree terminology.
1.1318 +*/
1.1319 +static int ChooseLeaf(
1.1320 + Rtree *pRtree, /* Rtree table */
1.1321 + RtreeCell *pCell, /* Cell to insert into rtree */
1.1322 + int iHeight, /* Height of sub-tree rooted at pCell */
1.1323 + RtreeNode **ppLeaf /* OUT: Selected leaf page */
1.1324 +){
1.1325 + int rc;
1.1326 + int ii;
1.1327 + RtreeNode *pNode;
1.1328 + rc = nodeAcquire(pRtree, 1, 0, &pNode);
1.1329 +
1.1330 + for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
1.1331 + int iCell;
1.1332 + sqlite3_int64 iBest;
1.1333 +
1.1334 + float fMinGrowth;
1.1335 + float fMinArea;
1.1336 + float fMinOverlap;
1.1337 +
1.1338 + int nCell = NCELL(pNode);
1.1339 + RtreeCell cell;
1.1340 + RtreeNode *pChild;
1.1341 +
1.1342 + RtreeCell *aCell = 0;
1.1343 +
1.1344 +#if VARIANT_RSTARTREE_CHOOSESUBTREE
1.1345 + if( ii==(pRtree->iDepth-1) ){
1.1346 + int jj;
1.1347 + aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
1.1348 + if( !aCell ){
1.1349 + rc = SQLITE_NOMEM;
1.1350 + nodeRelease(pRtree, pNode);
1.1351 + pNode = 0;
1.1352 + continue;
1.1353 + }
1.1354 + for(jj=0; jj<nCell; jj++){
1.1355 + nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
1.1356 + }
1.1357 + }
1.1358 +#endif
1.1359 +
1.1360 + /* Select the child node which will be enlarged the least if pCell
1.1361 + ** is inserted into it. Resolve ties by choosing the entry with
1.1362 + ** the smallest area.
1.1363 + */
1.1364 + for(iCell=0; iCell<nCell; iCell++){
1.1365 + float growth;
1.1366 + float area;
1.1367 + float overlap = 0.0;
1.1368 + nodeGetCell(pRtree, pNode, iCell, &cell);
1.1369 + growth = cellGrowth(pRtree, &cell, pCell);
1.1370 + area = cellArea(pRtree, &cell);
1.1371 +#if VARIANT_RSTARTREE_CHOOSESUBTREE
1.1372 + if( ii==(pRtree->iDepth-1) ){
1.1373 + overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
1.1374 + }
1.1375 +#endif
1.1376 + if( (iCell==0)
1.1377 + || (overlap<fMinOverlap)
1.1378 + || (overlap==fMinOverlap && growth<fMinGrowth)
1.1379 + || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
1.1380 + ){
1.1381 + fMinOverlap = overlap;
1.1382 + fMinGrowth = growth;
1.1383 + fMinArea = area;
1.1384 + iBest = cell.iRowid;
1.1385 + }
1.1386 + }
1.1387 +
1.1388 + sqlite3_free(aCell);
1.1389 + rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
1.1390 + nodeRelease(pRtree, pNode);
1.1391 + pNode = pChild;
1.1392 + }
1.1393 +
1.1394 + *ppLeaf = pNode;
1.1395 + return rc;
1.1396 +}
1.1397 +
1.1398 +/*
1.1399 +** A cell with the same content as pCell has just been inserted into
1.1400 +** the node pNode. This function updates the bounding box cells in
1.1401 +** all ancestor elements.
1.1402 +*/
1.1403 +static void AdjustTree(
1.1404 + Rtree *pRtree, /* Rtree table */
1.1405 + RtreeNode *pNode, /* Adjust ancestry of this node. */
1.1406 + RtreeCell *pCell /* This cell was just inserted */
1.1407 +){
1.1408 + RtreeNode *p = pNode;
1.1409 + while( p->pParent ){
1.1410 + RtreeCell cell;
1.1411 + RtreeNode *pParent = p->pParent;
1.1412 + int iCell = nodeParentIndex(pRtree, p);
1.1413 +
1.1414 + nodeGetCell(pRtree, pParent, iCell, &cell);
1.1415 + if( !cellContains(pRtree, &cell, pCell) ){
1.1416 + cellUnion(pRtree, &cell, pCell);
1.1417 + nodeOverwriteCell(pRtree, pParent, &cell, iCell);
1.1418 + }
1.1419 +
1.1420 + p = pParent;
1.1421 + }
1.1422 +}
1.1423 +
1.1424 +/*
1.1425 +** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
1.1426 +*/
1.1427 +static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
1.1428 + sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
1.1429 + sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
1.1430 + sqlite3_step(pRtree->pWriteRowid);
1.1431 + return sqlite3_reset(pRtree->pWriteRowid);
1.1432 +}
1.1433 +
1.1434 +/*
1.1435 +** Write mapping (iNode->iPar) to the <rtree>_parent table.
1.1436 +*/
1.1437 +static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
1.1438 + sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
1.1439 + sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
1.1440 + sqlite3_step(pRtree->pWriteParent);
1.1441 + return sqlite3_reset(pRtree->pWriteParent);
1.1442 +}
1.1443 +
1.1444 +static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
1.1445 +
1.1446 +#if VARIANT_GUTTMAN_LINEAR_SPLIT
1.1447 +/*
1.1448 +** Implementation of the linear variant of the PickNext() function from
1.1449 +** Guttman[84].
1.1450 +*/
1.1451 +static RtreeCell *LinearPickNext(
1.1452 + Rtree *pRtree,
1.1453 + RtreeCell *aCell,
1.1454 + int nCell,
1.1455 + RtreeCell *pLeftBox,
1.1456 + RtreeCell *pRightBox,
1.1457 + int *aiUsed
1.1458 +){
1.1459 + int ii;
1.1460 + for(ii=0; aiUsed[ii]; ii++);
1.1461 + aiUsed[ii] = 1;
1.1462 + return &aCell[ii];
1.1463 +}
1.1464 +
1.1465 +/*
1.1466 +** Implementation of the linear variant of the PickSeeds() function from
1.1467 +** Guttman[84].
1.1468 +*/
1.1469 +static void LinearPickSeeds(
1.1470 + Rtree *pRtree,
1.1471 + RtreeCell *aCell,
1.1472 + int nCell,
1.1473 + int *piLeftSeed,
1.1474 + int *piRightSeed
1.1475 +){
1.1476 + int i;
1.1477 + int iLeftSeed = 0;
1.1478 + int iRightSeed = 1;
1.1479 + float maxNormalInnerWidth = 0.0;
1.1480 +
1.1481 + /* Pick two "seed" cells from the array of cells. The algorithm used
1.1482 + ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
1.1483 + ** indices of the two seed cells in the array are stored in local
1.1484 + ** variables iLeftSeek and iRightSeed.
1.1485 + */
1.1486 + for(i=0; i<pRtree->nDim; i++){
1.1487 + float x1 = aCell[0].aCoord[i*2];
1.1488 + float x2 = aCell[0].aCoord[i*2+1];
1.1489 + float x3 = x1;
1.1490 + float x4 = x2;
1.1491 + int jj;
1.1492 +
1.1493 + int iCellLeft = 0;
1.1494 + int iCellRight = 0;
1.1495 +
1.1496 + for(jj=1; jj<nCell; jj++){
1.1497 + float left = aCell[jj].aCoord[i*2];
1.1498 + float right = aCell[jj].aCoord[i*2+1];
1.1499 +
1.1500 + if( left<x1 ) x1 = left;
1.1501 + if( right>x4 ) x4 = right;
1.1502 + if( left>x3 ){
1.1503 + x3 = left;
1.1504 + iCellRight = jj;
1.1505 + }
1.1506 + if( right<x2 ){
1.1507 + x2 = right;
1.1508 + iCellLeft = jj;
1.1509 + }
1.1510 + }
1.1511 +
1.1512 + if( x4!=x1 ){
1.1513 + float normalwidth = (x3 - x2) / (x4 - x1);
1.1514 + if( normalwidth>maxNormalInnerWidth ){
1.1515 + iLeftSeed = iCellLeft;
1.1516 + iRightSeed = iCellRight;
1.1517 + }
1.1518 + }
1.1519 + }
1.1520 +
1.1521 + *piLeftSeed = iLeftSeed;
1.1522 + *piRightSeed = iRightSeed;
1.1523 +}
1.1524 +#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
1.1525 +
1.1526 +#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
1.1527 +/*
1.1528 +** Implementation of the quadratic variant of the PickNext() function from
1.1529 +** Guttman[84].
1.1530 +*/
1.1531 +static RtreeCell *QuadraticPickNext(
1.1532 + Rtree *pRtree,
1.1533 + RtreeCell *aCell,
1.1534 + int nCell,
1.1535 + RtreeCell *pLeftBox,
1.1536 + RtreeCell *pRightBox,
1.1537 + int *aiUsed
1.1538 +){
1.1539 + #define FABS(a) ((a)<0.0?-1.0*(a):(a))
1.1540 +
1.1541 + int iSelect = -1;
1.1542 + float fDiff;
1.1543 + int ii;
1.1544 + for(ii=0; ii<nCell; ii++){
1.1545 + if( aiUsed[ii]==0 ){
1.1546 + float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1.1547 + float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
1.1548 + float diff = FABS(right-left);
1.1549 + if( iSelect<0 || diff>fDiff ){
1.1550 + fDiff = diff;
1.1551 + iSelect = ii;
1.1552 + }
1.1553 + }
1.1554 + }
1.1555 + aiUsed[iSelect] = 1;
1.1556 + return &aCell[iSelect];
1.1557 +}
1.1558 +
1.1559 +/*
1.1560 +** Implementation of the quadratic variant of the PickSeeds() function from
1.1561 +** Guttman[84].
1.1562 +*/
1.1563 +static void QuadraticPickSeeds(
1.1564 + Rtree *pRtree,
1.1565 + RtreeCell *aCell,
1.1566 + int nCell,
1.1567 + int *piLeftSeed,
1.1568 + int *piRightSeed
1.1569 +){
1.1570 + int ii;
1.1571 + int jj;
1.1572 +
1.1573 + int iLeftSeed = 0;
1.1574 + int iRightSeed = 1;
1.1575 + float fWaste = 0.0;
1.1576 +
1.1577 + for(ii=0; ii<nCell; ii++){
1.1578 + for(jj=ii+1; jj<nCell; jj++){
1.1579 + float right = cellArea(pRtree, &aCell[jj]);
1.1580 + float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
1.1581 + float waste = growth - right;
1.1582 +
1.1583 + if( waste>fWaste ){
1.1584 + iLeftSeed = ii;
1.1585 + iRightSeed = jj;
1.1586 + fWaste = waste;
1.1587 + }
1.1588 + }
1.1589 + }
1.1590 +
1.1591 + *piLeftSeed = iLeftSeed;
1.1592 + *piRightSeed = iRightSeed;
1.1593 +}
1.1594 +#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
1.1595 +
1.1596 +/*
1.1597 +** Arguments aIdx, aDistance and aSpare all point to arrays of size
1.1598 +** nIdx. The aIdx array contains the set of integers from 0 to
1.1599 +** (nIdx-1) in no particular order. This function sorts the values
1.1600 +** in aIdx according to the indexed values in aDistance. For
1.1601 +** example, assuming the inputs:
1.1602 +**
1.1603 +** aIdx = { 0, 1, 2, 3 }
1.1604 +** aDistance = { 5.0, 2.0, 7.0, 6.0 }
1.1605 +**
1.1606 +** this function sets the aIdx array to contain:
1.1607 +**
1.1608 +** aIdx = { 0, 1, 2, 3 }
1.1609 +**
1.1610 +** The aSpare array is used as temporary working space by the
1.1611 +** sorting algorithm.
1.1612 +*/
1.1613 +static void SortByDistance(
1.1614 + int *aIdx,
1.1615 + int nIdx,
1.1616 + float *aDistance,
1.1617 + int *aSpare
1.1618 +){
1.1619 + if( nIdx>1 ){
1.1620 + int iLeft = 0;
1.1621 + int iRight = 0;
1.1622 +
1.1623 + int nLeft = nIdx/2;
1.1624 + int nRight = nIdx-nLeft;
1.1625 + int *aLeft = aIdx;
1.1626 + int *aRight = &aIdx[nLeft];
1.1627 +
1.1628 + SortByDistance(aLeft, nLeft, aDistance, aSpare);
1.1629 + SortByDistance(aRight, nRight, aDistance, aSpare);
1.1630 +
1.1631 + memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1.1632 + aLeft = aSpare;
1.1633 +
1.1634 + while( iLeft<nLeft || iRight<nRight ){
1.1635 + if( iLeft==nLeft ){
1.1636 + aIdx[iLeft+iRight] = aRight[iRight];
1.1637 + iRight++;
1.1638 + }else if( iRight==nRight ){
1.1639 + aIdx[iLeft+iRight] = aLeft[iLeft];
1.1640 + iLeft++;
1.1641 + }else{
1.1642 + float fLeft = aDistance[aLeft[iLeft]];
1.1643 + float fRight = aDistance[aRight[iRight]];
1.1644 + if( fLeft<fRight ){
1.1645 + aIdx[iLeft+iRight] = aLeft[iLeft];
1.1646 + iLeft++;
1.1647 + }else{
1.1648 + aIdx[iLeft+iRight] = aRight[iRight];
1.1649 + iRight++;
1.1650 + }
1.1651 + }
1.1652 + }
1.1653 +
1.1654 +#if 0
1.1655 + /* Check that the sort worked */
1.1656 + {
1.1657 + int jj;
1.1658 + for(jj=1; jj<nIdx; jj++){
1.1659 + float left = aDistance[aIdx[jj-1]];
1.1660 + float right = aDistance[aIdx[jj]];
1.1661 + assert( left<=right );
1.1662 + }
1.1663 + }
1.1664 +#endif
1.1665 + }
1.1666 +}
1.1667 +
1.1668 +/*
1.1669 +** Arguments aIdx, aCell and aSpare all point to arrays of size
1.1670 +** nIdx. The aIdx array contains the set of integers from 0 to
1.1671 +** (nIdx-1) in no particular order. This function sorts the values
1.1672 +** in aIdx according to dimension iDim of the cells in aCell. The
1.1673 +** minimum value of dimension iDim is considered first, the
1.1674 +** maximum used to break ties.
1.1675 +**
1.1676 +** The aSpare array is used as temporary working space by the
1.1677 +** sorting algorithm.
1.1678 +*/
1.1679 +static void SortByDimension(
1.1680 + Rtree *pRtree,
1.1681 + int *aIdx,
1.1682 + int nIdx,
1.1683 + int iDim,
1.1684 + RtreeCell *aCell,
1.1685 + int *aSpare
1.1686 +){
1.1687 + if( nIdx>1 ){
1.1688 +
1.1689 + int iLeft = 0;
1.1690 + int iRight = 0;
1.1691 +
1.1692 + int nLeft = nIdx/2;
1.1693 + int nRight = nIdx-nLeft;
1.1694 + int *aLeft = aIdx;
1.1695 + int *aRight = &aIdx[nLeft];
1.1696 +
1.1697 + SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
1.1698 + SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
1.1699 +
1.1700 + memcpy(aSpare, aLeft, sizeof(int)*nLeft);
1.1701 + aLeft = aSpare;
1.1702 + while( iLeft<nLeft || iRight<nRight ){
1.1703 + double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
1.1704 + double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
1.1705 + double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
1.1706 + double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
1.1707 + if( (iLeft!=nLeft) && ((iRight==nRight)
1.1708 + || (xleft1<xright1)
1.1709 + || (xleft1==xright1 && xleft2<xright2)
1.1710 + )){
1.1711 + aIdx[iLeft+iRight] = aLeft[iLeft];
1.1712 + iLeft++;
1.1713 + }else{
1.1714 + aIdx[iLeft+iRight] = aRight[iRight];
1.1715 + iRight++;
1.1716 + }
1.1717 + }
1.1718 +
1.1719 +#if 0
1.1720 + /* Check that the sort worked */
1.1721 + {
1.1722 + int jj;
1.1723 + for(jj=1; jj<nIdx; jj++){
1.1724 + float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
1.1725 + float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
1.1726 + float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
1.1727 + float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
1.1728 + assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
1.1729 + }
1.1730 + }
1.1731 +#endif
1.1732 + }
1.1733 +}
1.1734 +
1.1735 +#if VARIANT_RSTARTREE_SPLIT
1.1736 +/*
1.1737 +** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
1.1738 +*/
1.1739 +static int splitNodeStartree(
1.1740 + Rtree *pRtree,
1.1741 + RtreeCell *aCell,
1.1742 + int nCell,
1.1743 + RtreeNode *pLeft,
1.1744 + RtreeNode *pRight,
1.1745 + RtreeCell *pBboxLeft,
1.1746 + RtreeCell *pBboxRight
1.1747 +){
1.1748 + int **aaSorted;
1.1749 + int *aSpare;
1.1750 + int ii;
1.1751 +
1.1752 + int iBestDim;
1.1753 + int iBestSplit;
1.1754 + float fBestMargin;
1.1755 +
1.1756 + int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
1.1757 +
1.1758 + aaSorted = (int **)sqlite3_malloc(nByte);
1.1759 + if( !aaSorted ){
1.1760 + return SQLITE_NOMEM;
1.1761 + }
1.1762 +
1.1763 + aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell];
1.1764 + memset(aaSorted, 0, nByte);
1.1765 + for(ii=0; ii<pRtree->nDim; ii++){
1.1766 + int jj;
1.1767 + aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell];
1.1768 + for(jj=0; jj<nCell; jj++){
1.1769 + aaSorted[ii][jj] = jj;
1.1770 + }
1.1771 + SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
1.1772 + }
1.1773 +
1.1774 + for(ii=0; ii<pRtree->nDim; ii++){
1.1775 + float margin = 0.0;
1.1776 + float fBestOverlap;
1.1777 + float fBestArea;
1.1778 + int iBestLeft;
1.1779 + int nLeft;
1.1780 +
1.1781 + for(
1.1782 + nLeft=RTREE_MINCELLS(pRtree);
1.1783 + nLeft<=(nCell-RTREE_MINCELLS(pRtree));
1.1784 + nLeft++
1.1785 + ){
1.1786 + RtreeCell left;
1.1787 + RtreeCell right;
1.1788 + int kk;
1.1789 + float overlap;
1.1790 + float area;
1.1791 +
1.1792 + memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
1.1793 + memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
1.1794 + for(kk=1; kk<(nCell-1); kk++){
1.1795 + if( kk<nLeft ){
1.1796 + cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
1.1797 + }else{
1.1798 + cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
1.1799 + }
1.1800 + }
1.1801 + margin += cellMargin(pRtree, &left);
1.1802 + margin += cellMargin(pRtree, &right);
1.1803 + overlap = cellOverlap(pRtree, &left, &right, 1, -1);
1.1804 + area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
1.1805 + if( (nLeft==RTREE_MINCELLS(pRtree))
1.1806 + || (overlap<fBestOverlap)
1.1807 + || (overlap==fBestOverlap && area<fBestArea)
1.1808 + ){
1.1809 + iBestLeft = nLeft;
1.1810 + fBestOverlap = overlap;
1.1811 + fBestArea = area;
1.1812 + }
1.1813 + }
1.1814 +
1.1815 + if( ii==0 || margin<fBestMargin ){
1.1816 + iBestDim = ii;
1.1817 + fBestMargin = margin;
1.1818 + iBestSplit = iBestLeft;
1.1819 + }
1.1820 + }
1.1821 +
1.1822 + memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
1.1823 + memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
1.1824 + for(ii=0; ii<nCell; ii++){
1.1825 + RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
1.1826 + RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
1.1827 + RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
1.1828 + nodeInsertCell(pRtree, pTarget, pCell);
1.1829 + cellUnion(pRtree, pBbox, pCell);
1.1830 + }
1.1831 +
1.1832 + sqlite3_free(aaSorted);
1.1833 + return SQLITE_OK;
1.1834 +}
1.1835 +#endif
1.1836 +
1.1837 +#if VARIANT_GUTTMAN_SPLIT
1.1838 +/*
1.1839 +** Implementation of the regular R-tree SplitNode from Guttman[1984].
1.1840 +*/
1.1841 +static int splitNodeGuttman(
1.1842 + Rtree *pRtree,
1.1843 + RtreeCell *aCell,
1.1844 + int nCell,
1.1845 + RtreeNode *pLeft,
1.1846 + RtreeNode *pRight,
1.1847 + RtreeCell *pBboxLeft,
1.1848 + RtreeCell *pBboxRight
1.1849 +){
1.1850 + int iLeftSeed = 0;
1.1851 + int iRightSeed = 1;
1.1852 + int *aiUsed;
1.1853 + int i;
1.1854 +
1.1855 + aiUsed = sqlite3_malloc(sizeof(int)*nCell);
1.1856 + memset(aiUsed, 0, sizeof(int)*nCell);
1.1857 +
1.1858 + PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
1.1859 +
1.1860 + memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
1.1861 + memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
1.1862 + nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
1.1863 + nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
1.1864 + aiUsed[iLeftSeed] = 1;
1.1865 + aiUsed[iRightSeed] = 1;
1.1866 +
1.1867 + for(i=nCell-2; i>0; i--){
1.1868 + RtreeCell *pNext;
1.1869 + pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
1.1870 + float diff =
1.1871 + cellGrowth(pRtree, pBboxLeft, pNext) -
1.1872 + cellGrowth(pRtree, pBboxRight, pNext)
1.1873 + ;
1.1874 + if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
1.1875 + || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
1.1876 + ){
1.1877 + nodeInsertCell(pRtree, pRight, pNext);
1.1878 + cellUnion(pRtree, pBboxRight, pNext);
1.1879 + }else{
1.1880 + nodeInsertCell(pRtree, pLeft, pNext);
1.1881 + cellUnion(pRtree, pBboxLeft, pNext);
1.1882 + }
1.1883 + }
1.1884 +
1.1885 + sqlite3_free(aiUsed);
1.1886 + return SQLITE_OK;
1.1887 +}
1.1888 +#endif
1.1889 +
1.1890 +static int updateMapping(
1.1891 + Rtree *pRtree,
1.1892 + i64 iRowid,
1.1893 + RtreeNode *pNode,
1.1894 + int iHeight
1.1895 +){
1.1896 + int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64);
1.1897 + xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
1.1898 + if( iHeight>0 ){
1.1899 + RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
1.1900 + if( pChild ){
1.1901 + nodeRelease(pRtree, pChild->pParent);
1.1902 + nodeReference(pNode);
1.1903 + pChild->pParent = pNode;
1.1904 + }
1.1905 + }
1.1906 + return xSetMapping(pRtree, iRowid, pNode->iNode);
1.1907 +}
1.1908 +
1.1909 +static int SplitNode(
1.1910 + Rtree *pRtree,
1.1911 + RtreeNode *pNode,
1.1912 + RtreeCell *pCell,
1.1913 + int iHeight
1.1914 +){
1.1915 + int i;
1.1916 + int newCellIsRight = 0;
1.1917 +
1.1918 + int rc = SQLITE_OK;
1.1919 + int nCell = NCELL(pNode);
1.1920 + RtreeCell *aCell;
1.1921 + int *aiUsed;
1.1922 +
1.1923 + RtreeNode *pLeft = 0;
1.1924 + RtreeNode *pRight = 0;
1.1925 +
1.1926 + RtreeCell leftbbox;
1.1927 + RtreeCell rightbbox;
1.1928 +
1.1929 + /* Allocate an array and populate it with a copy of pCell and
1.1930 + ** all cells from node pLeft. Then zero the original node.
1.1931 + */
1.1932 + aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
1.1933 + if( !aCell ){
1.1934 + rc = SQLITE_NOMEM;
1.1935 + goto splitnode_out;
1.1936 + }
1.1937 + aiUsed = (int *)&aCell[nCell+1];
1.1938 + memset(aiUsed, 0, sizeof(int)*(nCell+1));
1.1939 + for(i=0; i<nCell; i++){
1.1940 + nodeGetCell(pRtree, pNode, i, &aCell[i]);
1.1941 + }
1.1942 + nodeZero(pRtree, pNode);
1.1943 + memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
1.1944 + nCell++;
1.1945 +
1.1946 + if( pNode->iNode==1 ){
1.1947 + pRight = nodeNew(pRtree, pNode, 1);
1.1948 + pLeft = nodeNew(pRtree, pNode, 1);
1.1949 + pRtree->iDepth++;
1.1950 + pNode->isDirty = 1;
1.1951 + writeInt16(pNode->zData, pRtree->iDepth);
1.1952 + }else{
1.1953 + pLeft = pNode;
1.1954 + pRight = nodeNew(pRtree, pLeft->pParent, 1);
1.1955 + nodeReference(pLeft);
1.1956 + }
1.1957 +
1.1958 + if( !pLeft || !pRight ){
1.1959 + rc = SQLITE_NOMEM;
1.1960 + goto splitnode_out;
1.1961 + }
1.1962 +
1.1963 + memset(pLeft->zData, 0, pRtree->iNodeSize);
1.1964 + memset(pRight->zData, 0, pRtree->iNodeSize);
1.1965 +
1.1966 + rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
1.1967 + if( rc!=SQLITE_OK ){
1.1968 + goto splitnode_out;
1.1969 + }
1.1970 +
1.1971 + /* Ensure both child nodes have node numbers assigned to them. */
1.1972 + if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
1.1973 + || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
1.1974 + ){
1.1975 + goto splitnode_out;
1.1976 + }
1.1977 +
1.1978 + rightbbox.iRowid = pRight->iNode;
1.1979 + leftbbox.iRowid = pLeft->iNode;
1.1980 +
1.1981 + if( pNode->iNode==1 ){
1.1982 + rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
1.1983 + if( rc!=SQLITE_OK ){
1.1984 + goto splitnode_out;
1.1985 + }
1.1986 + }else{
1.1987 + RtreeNode *pParent = pLeft->pParent;
1.1988 + int iCell = nodeParentIndex(pRtree, pLeft);
1.1989 + nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
1.1990 + AdjustTree(pRtree, pParent, &leftbbox);
1.1991 + }
1.1992 + if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
1.1993 + goto splitnode_out;
1.1994 + }
1.1995 +
1.1996 + for(i=0; i<NCELL(pRight); i++){
1.1997 + i64 iRowid = nodeGetRowid(pRtree, pRight, i);
1.1998 + rc = updateMapping(pRtree, iRowid, pRight, iHeight);
1.1999 + if( iRowid==pCell->iRowid ){
1.2000 + newCellIsRight = 1;
1.2001 + }
1.2002 + if( rc!=SQLITE_OK ){
1.2003 + goto splitnode_out;
1.2004 + }
1.2005 + }
1.2006 + if( pNode->iNode==1 ){
1.2007 + for(i=0; i<NCELL(pLeft); i++){
1.2008 + i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
1.2009 + rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
1.2010 + if( rc!=SQLITE_OK ){
1.2011 + goto splitnode_out;
1.2012 + }
1.2013 + }
1.2014 + }else if( newCellIsRight==0 ){
1.2015 + rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
1.2016 + }
1.2017 +
1.2018 + if( rc==SQLITE_OK ){
1.2019 + rc = nodeRelease(pRtree, pRight);
1.2020 + pRight = 0;
1.2021 + }
1.2022 + if( rc==SQLITE_OK ){
1.2023 + rc = nodeRelease(pRtree, pLeft);
1.2024 + pLeft = 0;
1.2025 + }
1.2026 +
1.2027 +splitnode_out:
1.2028 + nodeRelease(pRtree, pRight);
1.2029 + nodeRelease(pRtree, pLeft);
1.2030 + sqlite3_free(aCell);
1.2031 + return rc;
1.2032 +}
1.2033 +
1.2034 +static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
1.2035 + int rc = SQLITE_OK;
1.2036 + if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
1.2037 + sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
1.2038 + if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){
1.2039 + i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
1.2040 + rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
1.2041 + }else{
1.2042 + rc = SQLITE_ERROR;
1.2043 + }
1.2044 + sqlite3_reset(pRtree->pReadParent);
1.2045 + if( rc==SQLITE_OK ){
1.2046 + rc = fixLeafParent(pRtree, pLeaf->pParent);
1.2047 + }
1.2048 + }
1.2049 + return rc;
1.2050 +}
1.2051 +
1.2052 +static int deleteCell(Rtree *, RtreeNode *, int, int);
1.2053 +
1.2054 +static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
1.2055 + int rc;
1.2056 + RtreeNode *pParent;
1.2057 + int iCell;
1.2058 +
1.2059 + assert( pNode->nRef==1 );
1.2060 +
1.2061 + /* Remove the entry in the parent cell. */
1.2062 + iCell = nodeParentIndex(pRtree, pNode);
1.2063 + pParent = pNode->pParent;
1.2064 + pNode->pParent = 0;
1.2065 + if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1))
1.2066 + || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
1.2067 + ){
1.2068 + return rc;
1.2069 + }
1.2070 +
1.2071 + /* Remove the xxx_node entry. */
1.2072 + sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
1.2073 + sqlite3_step(pRtree->pDeleteNode);
1.2074 + if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
1.2075 + return rc;
1.2076 + }
1.2077 +
1.2078 + /* Remove the xxx_parent entry. */
1.2079 + sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
1.2080 + sqlite3_step(pRtree->pDeleteParent);
1.2081 + if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
1.2082 + return rc;
1.2083 + }
1.2084 +
1.2085 + /* Remove the node from the in-memory hash table and link it into
1.2086 + ** the Rtree.pDeleted list. Its contents will be re-inserted later on.
1.2087 + */
1.2088 + nodeHashDelete(pRtree, pNode);
1.2089 + pNode->iNode = iHeight;
1.2090 + pNode->pNext = pRtree->pDeleted;
1.2091 + pNode->nRef++;
1.2092 + pRtree->pDeleted = pNode;
1.2093 +
1.2094 + return SQLITE_OK;
1.2095 +}
1.2096 +
1.2097 +static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
1.2098 + RtreeNode *pParent = pNode->pParent;
1.2099 + if( pParent ){
1.2100 + int ii;
1.2101 + int nCell = NCELL(pNode);
1.2102 + RtreeCell box; /* Bounding box for pNode */
1.2103 + nodeGetCell(pRtree, pNode, 0, &box);
1.2104 + for(ii=1; ii<nCell; ii++){
1.2105 + RtreeCell cell;
1.2106 + nodeGetCell(pRtree, pNode, ii, &cell);
1.2107 + cellUnion(pRtree, &box, &cell);
1.2108 + }
1.2109 + box.iRowid = pNode->iNode;
1.2110 + ii = nodeParentIndex(pRtree, pNode);
1.2111 + nodeOverwriteCell(pRtree, pParent, &box, ii);
1.2112 + fixBoundingBox(pRtree, pParent);
1.2113 + }
1.2114 +}
1.2115 +
1.2116 +/*
1.2117 +** Delete the cell at index iCell of node pNode. After removing the
1.2118 +** cell, adjust the r-tree data structure if required.
1.2119 +*/
1.2120 +static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
1.2121 + int rc;
1.2122 +
1.2123 + if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
1.2124 + return rc;
1.2125 + }
1.2126 +
1.2127 + /* Remove the cell from the node. This call just moves bytes around
1.2128 + ** the in-memory node image, so it cannot fail.
1.2129 + */
1.2130 + nodeDeleteCell(pRtree, pNode, iCell);
1.2131 +
1.2132 + /* If the node is not the tree root and now has less than the minimum
1.2133 + ** number of cells, remove it from the tree. Otherwise, update the
1.2134 + ** cell in the parent node so that it tightly contains the updated
1.2135 + ** node.
1.2136 + */
1.2137 + if( pNode->iNode!=1 ){
1.2138 + RtreeNode *pParent = pNode->pParent;
1.2139 + if( (pParent->iNode!=1 || NCELL(pParent)!=1)
1.2140 + && (NCELL(pNode)<RTREE_MINCELLS(pRtree))
1.2141 + ){
1.2142 + rc = removeNode(pRtree, pNode, iHeight);
1.2143 + }else{
1.2144 + fixBoundingBox(pRtree, pNode);
1.2145 + }
1.2146 + }
1.2147 +
1.2148 + return rc;
1.2149 +}
1.2150 +
1.2151 +static int Reinsert(
1.2152 + Rtree *pRtree,
1.2153 + RtreeNode *pNode,
1.2154 + RtreeCell *pCell,
1.2155 + int iHeight
1.2156 +){
1.2157 + int *aOrder;
1.2158 + int *aSpare;
1.2159 + RtreeCell *aCell;
1.2160 + float *aDistance;
1.2161 + int nCell;
1.2162 + float aCenterCoord[RTREE_MAX_DIMENSIONS];
1.2163 + int iDim;
1.2164 + int ii;
1.2165 + int rc = SQLITE_OK;
1.2166 +
1.2167 + memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
1.2168 +
1.2169 + nCell = NCELL(pNode)+1;
1.2170 +
1.2171 + /* Allocate the buffers used by this operation. The allocation is
1.2172 + ** relinquished before this function returns.
1.2173 + */
1.2174 + aCell = (RtreeCell *)sqlite3_malloc(nCell * (
1.2175 + sizeof(RtreeCell) + /* aCell array */
1.2176 + sizeof(int) + /* aOrder array */
1.2177 + sizeof(int) + /* aSpare array */
1.2178 + sizeof(float) /* aDistance array */
1.2179 + ));
1.2180 + if( !aCell ){
1.2181 + return SQLITE_NOMEM;
1.2182 + }
1.2183 + aOrder = (int *)&aCell[nCell];
1.2184 + aSpare = (int *)&aOrder[nCell];
1.2185 + aDistance = (float *)&aSpare[nCell];
1.2186 +
1.2187 + for(ii=0; ii<nCell; ii++){
1.2188 + if( ii==(nCell-1) ){
1.2189 + memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
1.2190 + }else{
1.2191 + nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
1.2192 + }
1.2193 + aOrder[ii] = ii;
1.2194 + for(iDim=0; iDim<pRtree->nDim; iDim++){
1.2195 + aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]);
1.2196 + aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]);
1.2197 + }
1.2198 + }
1.2199 + for(iDim=0; iDim<pRtree->nDim; iDim++){
1.2200 + aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
1.2201 + }
1.2202 +
1.2203 + for(ii=0; ii<nCell; ii++){
1.2204 + aDistance[ii] = 0.0;
1.2205 + for(iDim=0; iDim<pRtree->nDim; iDim++){
1.2206 + float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) -
1.2207 + DCOORD(aCell[ii].aCoord[iDim*2]);
1.2208 + aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
1.2209 + }
1.2210 + }
1.2211 +
1.2212 + SortByDistance(aOrder, nCell, aDistance, aSpare);
1.2213 + nodeZero(pRtree, pNode);
1.2214 +
1.2215 + for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
1.2216 + RtreeCell *p = &aCell[aOrder[ii]];
1.2217 + nodeInsertCell(pRtree, pNode, p);
1.2218 + if( p->iRowid==pCell->iRowid ){
1.2219 + if( iHeight==0 ){
1.2220 + rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
1.2221 + }else{
1.2222 + rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
1.2223 + }
1.2224 + }
1.2225 + }
1.2226 + if( rc==SQLITE_OK ){
1.2227 + fixBoundingBox(pRtree, pNode);
1.2228 + }
1.2229 + for(; rc==SQLITE_OK && ii<nCell; ii++){
1.2230 + /* Find a node to store this cell in. pNode->iNode currently contains
1.2231 + ** the height of the sub-tree headed by the cell.
1.2232 + */
1.2233 + RtreeNode *pInsert;
1.2234 + RtreeCell *p = &aCell[aOrder[ii]];
1.2235 + rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
1.2236 + if( rc==SQLITE_OK ){
1.2237 + int rc2;
1.2238 + rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);
1.2239 + rc2 = nodeRelease(pRtree, pInsert);
1.2240 + if( rc==SQLITE_OK ){
1.2241 + rc = rc2;
1.2242 + }
1.2243 + }
1.2244 + }
1.2245 +
1.2246 + sqlite3_free(aCell);
1.2247 + return rc;
1.2248 +}
1.2249 +
1.2250 +/*
1.2251 +** Insert cell pCell into node pNode. Node pNode is the head of a
1.2252 +** subtree iHeight high (leaf nodes have iHeight==0).
1.2253 +*/
1.2254 +static int rtreeInsertCell(
1.2255 + Rtree *pRtree,
1.2256 + RtreeNode *pNode,
1.2257 + RtreeCell *pCell,
1.2258 + int iHeight
1.2259 +){
1.2260 + int rc = SQLITE_OK;
1.2261 + if( iHeight>0 ){
1.2262 + RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
1.2263 + if( pChild ){
1.2264 + nodeRelease(pRtree, pChild->pParent);
1.2265 + nodeReference(pNode);
1.2266 + pChild->pParent = pNode;
1.2267 + }
1.2268 + }
1.2269 + if( nodeInsertCell(pRtree, pNode, pCell) ){
1.2270 +#if VARIANT_RSTARTREE_REINSERT
1.2271 + if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
1.2272 + rc = SplitNode(pRtree, pNode, pCell, iHeight);
1.2273 + }else{
1.2274 + pRtree->iReinsertHeight = iHeight;
1.2275 + rc = Reinsert(pRtree, pNode, pCell, iHeight);
1.2276 + }
1.2277 +#else
1.2278 + rc = SplitNode(pRtree, pNode, pCell, iHeight);
1.2279 +#endif
1.2280 + }else{
1.2281 + AdjustTree(pRtree, pNode, pCell);
1.2282 + if( iHeight==0 ){
1.2283 + rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
1.2284 + }else{
1.2285 + rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
1.2286 + }
1.2287 + }
1.2288 + return rc;
1.2289 +}
1.2290 +
1.2291 +static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
1.2292 + int ii;
1.2293 + int rc = SQLITE_OK;
1.2294 + int nCell = NCELL(pNode);
1.2295 +
1.2296 + for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
1.2297 + RtreeNode *pInsert;
1.2298 + RtreeCell cell;
1.2299 + nodeGetCell(pRtree, pNode, ii, &cell);
1.2300 +
1.2301 + /* Find a node to store this cell in. pNode->iNode currently contains
1.2302 + ** the height of the sub-tree headed by the cell.
1.2303 + */
1.2304 + rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
1.2305 + if( rc==SQLITE_OK ){
1.2306 + int rc2;
1.2307 + rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);
1.2308 + rc2 = nodeRelease(pRtree, pInsert);
1.2309 + if( rc==SQLITE_OK ){
1.2310 + rc = rc2;
1.2311 + }
1.2312 + }
1.2313 + }
1.2314 + return rc;
1.2315 +}
1.2316 +
1.2317 +/*
1.2318 +** Select a currently unused rowid for a new r-tree record.
1.2319 +*/
1.2320 +static int newRowid(Rtree *pRtree, i64 *piRowid){
1.2321 + int rc;
1.2322 + sqlite3_bind_null(pRtree->pWriteRowid, 1);
1.2323 + sqlite3_bind_null(pRtree->pWriteRowid, 2);
1.2324 + sqlite3_step(pRtree->pWriteRowid);
1.2325 + rc = sqlite3_reset(pRtree->pWriteRowid);
1.2326 + *piRowid = sqlite3_last_insert_rowid(pRtree->db);
1.2327 + return rc;
1.2328 +}
1.2329 +
1.2330 +#ifndef NDEBUG
1.2331 +static int hashIsEmpty(Rtree *pRtree){
1.2332 + int ii;
1.2333 + for(ii=0; ii<HASHSIZE; ii++){
1.2334 + assert( !pRtree->aHash[ii] );
1.2335 + }
1.2336 + return 1;
1.2337 +}
1.2338 +#endif
1.2339 +
1.2340 +/*
1.2341 +** The xUpdate method for rtree module virtual tables.
1.2342 +*/
1.2343 +int rtreeUpdate(
1.2344 + sqlite3_vtab *pVtab,
1.2345 + int nData,
1.2346 + sqlite3_value **azData,
1.2347 + sqlite_int64 *pRowid
1.2348 +){
1.2349 + Rtree *pRtree = (Rtree *)pVtab;
1.2350 + int rc = SQLITE_OK;
1.2351 +
1.2352 + rtreeReference(pRtree);
1.2353 +
1.2354 + assert(nData>=1);
1.2355 + assert(hashIsEmpty(pRtree));
1.2356 +
1.2357 + /* If azData[0] is not an SQL NULL value, it is the rowid of a
1.2358 + ** record to delete from the r-tree table. The following block does
1.2359 + ** just that.
1.2360 + */
1.2361 + if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
1.2362 + i64 iDelete; /* The rowid to delete */
1.2363 + RtreeNode *pLeaf; /* Leaf node containing record iDelete */
1.2364 + int iCell; /* Index of iDelete cell in pLeaf */
1.2365 + RtreeNode *pRoot;
1.2366 +
1.2367 + /* Obtain a reference to the root node to initialise Rtree.iDepth */
1.2368 + rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1.2369 +
1.2370 + /* Obtain a reference to the leaf node that contains the entry
1.2371 + ** about to be deleted.
1.2372 + */
1.2373 + if( rc==SQLITE_OK ){
1.2374 + iDelete = sqlite3_value_int64(azData[0]);
1.2375 + rc = findLeafNode(pRtree, iDelete, &pLeaf);
1.2376 + }
1.2377 +
1.2378 + /* Delete the cell in question from the leaf node. */
1.2379 + if( rc==SQLITE_OK ){
1.2380 + int rc2;
1.2381 + iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
1.2382 + rc = deleteCell(pRtree, pLeaf, iCell, 0);
1.2383 + rc2 = nodeRelease(pRtree, pLeaf);
1.2384 + if( rc==SQLITE_OK ){
1.2385 + rc = rc2;
1.2386 + }
1.2387 + }
1.2388 +
1.2389 + /* Delete the corresponding entry in the <rtree>_rowid table. */
1.2390 + if( rc==SQLITE_OK ){
1.2391 + sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
1.2392 + sqlite3_step(pRtree->pDeleteRowid);
1.2393 + rc = sqlite3_reset(pRtree->pDeleteRowid);
1.2394 + }
1.2395 +
1.2396 + /* Check if the root node now has exactly one child. If so, remove
1.2397 + ** it, schedule the contents of the child for reinsertion and
1.2398 + ** reduce the tree height by one.
1.2399 + **
1.2400 + ** This is equivalent to copying the contents of the child into
1.2401 + ** the root node (the operation that Gutman's paper says to perform
1.2402 + ** in this scenario).
1.2403 + */
1.2404 + if( rc==SQLITE_OK && pRtree->iDepth>0 ){
1.2405 + if( rc==SQLITE_OK && NCELL(pRoot)==1 ){
1.2406 + RtreeNode *pChild;
1.2407 + i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
1.2408 + rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
1.2409 + if( rc==SQLITE_OK ){
1.2410 + rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
1.2411 + }
1.2412 + if( rc==SQLITE_OK ){
1.2413 + pRtree->iDepth--;
1.2414 + writeInt16(pRoot->zData, pRtree->iDepth);
1.2415 + pRoot->isDirty = 1;
1.2416 + }
1.2417 + }
1.2418 + }
1.2419 +
1.2420 + /* Re-insert the contents of any underfull nodes removed from the tree. */
1.2421 + for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
1.2422 + if( rc==SQLITE_OK ){
1.2423 + rc = reinsertNodeContent(pRtree, pLeaf);
1.2424 + }
1.2425 + pRtree->pDeleted = pLeaf->pNext;
1.2426 + sqlite3_free(pLeaf);
1.2427 + }
1.2428 +
1.2429 + /* Release the reference to the root node. */
1.2430 + if( rc==SQLITE_OK ){
1.2431 + rc = nodeRelease(pRtree, pRoot);
1.2432 + }else{
1.2433 + nodeRelease(pRtree, pRoot);
1.2434 + }
1.2435 + }
1.2436 +
1.2437 + /* If the azData[] array contains more than one element, elements
1.2438 + ** (azData[2]..azData[argc-1]) contain a new record to insert into
1.2439 + ** the r-tree structure.
1.2440 + */
1.2441 + if( rc==SQLITE_OK && nData>1 ){
1.2442 + /* Insert a new record into the r-tree */
1.2443 + RtreeCell cell;
1.2444 + int ii;
1.2445 + RtreeNode *pLeaf;
1.2446 +
1.2447 + /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
1.2448 + assert( nData==(pRtree->nDim*2 + 3) );
1.2449 + if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
1.2450 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.2451 + cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
1.2452 + cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
1.2453 + if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
1.2454 + rc = SQLITE_CONSTRAINT;
1.2455 + goto constraint;
1.2456 + }
1.2457 + }
1.2458 + }else{
1.2459 + for(ii=0; ii<(pRtree->nDim*2); ii+=2){
1.2460 + cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
1.2461 + cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
1.2462 + if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
1.2463 + rc = SQLITE_CONSTRAINT;
1.2464 + goto constraint;
1.2465 + }
1.2466 + }
1.2467 + }
1.2468 +
1.2469 + /* Figure out the rowid of the new row. */
1.2470 + if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
1.2471 + rc = newRowid(pRtree, &cell.iRowid);
1.2472 + }else{
1.2473 + cell.iRowid = sqlite3_value_int64(azData[2]);
1.2474 + sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
1.2475 + if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
1.2476 + sqlite3_reset(pRtree->pReadRowid);
1.2477 + rc = SQLITE_CONSTRAINT;
1.2478 + goto constraint;
1.2479 + }
1.2480 + rc = sqlite3_reset(pRtree->pReadRowid);
1.2481 + }
1.2482 +
1.2483 + if( rc==SQLITE_OK ){
1.2484 + rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
1.2485 + }
1.2486 + if( rc==SQLITE_OK ){
1.2487 + int rc2;
1.2488 + pRtree->iReinsertHeight = -1;
1.2489 + rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
1.2490 + rc2 = nodeRelease(pRtree, pLeaf);
1.2491 + if( rc==SQLITE_OK ){
1.2492 + rc = rc2;
1.2493 + }
1.2494 + }
1.2495 + }
1.2496 +
1.2497 +constraint:
1.2498 + rtreeRelease(pRtree);
1.2499 + return rc;
1.2500 +}
1.2501 +
1.2502 +/*
1.2503 +** The xRename method for rtree module virtual tables.
1.2504 +*/
1.2505 +static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
1.2506 + Rtree *pRtree = (Rtree *)pVtab;
1.2507 + int rc = SQLITE_NOMEM;
1.2508 + char *zSql = sqlite3_mprintf(
1.2509 + "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
1.2510 + "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
1.2511 + "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
1.2512 + , pRtree->zDb, pRtree->zName, zNewName
1.2513 + , pRtree->zDb, pRtree->zName, zNewName
1.2514 + , pRtree->zDb, pRtree->zName, zNewName
1.2515 + );
1.2516 + if( zSql ){
1.2517 + rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
1.2518 + sqlite3_free(zSql);
1.2519 + }
1.2520 + return rc;
1.2521 +}
1.2522 +
1.2523 +static sqlite3_module rtreeModule = {
1.2524 + 0, /* iVersion */
1.2525 + rtreeCreate, /* xCreate - create a table */
1.2526 + rtreeConnect, /* xConnect - connect to an existing table */
1.2527 + rtreeBestIndex, /* xBestIndex - Determine search strategy */
1.2528 + rtreeDisconnect, /* xDisconnect - Disconnect from a table */
1.2529 + rtreeDestroy, /* xDestroy - Drop a table */
1.2530 + rtreeOpen, /* xOpen - open a cursor */
1.2531 + rtreeClose, /* xClose - close a cursor */
1.2532 + rtreeFilter, /* xFilter - configure scan constraints */
1.2533 + rtreeNext, /* xNext - advance a cursor */
1.2534 + rtreeEof, /* xEof */
1.2535 + rtreeColumn, /* xColumn - read data */
1.2536 + rtreeRowid, /* xRowid - read data */
1.2537 + rtreeUpdate, /* xUpdate - write data */
1.2538 + 0, /* xBegin - begin transaction */
1.2539 + 0, /* xSync - sync transaction */
1.2540 + 0, /* xCommit - commit transaction */
1.2541 + 0, /* xRollback - rollback transaction */
1.2542 + 0, /* xFindFunction - function overloading */
1.2543 + rtreeRename /* xRename - rename the table */
1.2544 +};
1.2545 +
1.2546 +static int rtreeSqlInit(
1.2547 + Rtree *pRtree,
1.2548 + sqlite3 *db,
1.2549 + const char *zDb,
1.2550 + const char *zPrefix,
1.2551 + int isCreate
1.2552 +){
1.2553 + int rc = SQLITE_OK;
1.2554 +
1.2555 + #define N_STATEMENT 9
1.2556 + static const char *azSql[N_STATEMENT] = {
1.2557 + /* Read and write the xxx_node table */
1.2558 + "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
1.2559 + "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
1.2560 + "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
1.2561 +
1.2562 + /* Read and write the xxx_rowid table */
1.2563 + "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
1.2564 + "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
1.2565 + "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
1.2566 +
1.2567 + /* Read and write the xxx_parent table */
1.2568 + "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
1.2569 + "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
1.2570 + "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
1.2571 + };
1.2572 + sqlite3_stmt **appStmt[N_STATEMENT];
1.2573 + int i;
1.2574 +
1.2575 + pRtree->db = db;
1.2576 +
1.2577 + if( isCreate ){
1.2578 + char *zCreate = sqlite3_mprintf(
1.2579 +"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
1.2580 +"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
1.2581 +"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
1.2582 +"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
1.2583 + zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
1.2584 + );
1.2585 + if( !zCreate ){
1.2586 + return SQLITE_NOMEM;
1.2587 + }
1.2588 + rc = sqlite3_exec(db, zCreate, 0, 0, 0);
1.2589 + sqlite3_free(zCreate);
1.2590 + if( rc!=SQLITE_OK ){
1.2591 + return rc;
1.2592 + }
1.2593 + }
1.2594 +
1.2595 + appStmt[0] = &pRtree->pReadNode;
1.2596 + appStmt[1] = &pRtree->pWriteNode;
1.2597 + appStmt[2] = &pRtree->pDeleteNode;
1.2598 + appStmt[3] = &pRtree->pReadRowid;
1.2599 + appStmt[4] = &pRtree->pWriteRowid;
1.2600 + appStmt[5] = &pRtree->pDeleteRowid;
1.2601 + appStmt[6] = &pRtree->pReadParent;
1.2602 + appStmt[7] = &pRtree->pWriteParent;
1.2603 + appStmt[8] = &pRtree->pDeleteParent;
1.2604 +
1.2605 + for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
1.2606 + char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
1.2607 + if( zSql ){
1.2608 + rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0);
1.2609 + }else{
1.2610 + rc = SQLITE_NOMEM;
1.2611 + }
1.2612 + sqlite3_free(zSql);
1.2613 + }
1.2614 +
1.2615 + return rc;
1.2616 +}
1.2617 +
1.2618 +/*
1.2619 +** This routine queries database handle db for the page-size used by
1.2620 +** database zDb. If successful, the page-size in bytes is written to
1.2621 +** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error
1.2622 +** code is returned.
1.2623 +*/
1.2624 +static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){
1.2625 + int rc = SQLITE_NOMEM;
1.2626 + char *zSql;
1.2627 + sqlite3_stmt *pStmt = 0;
1.2628 +
1.2629 + zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb);
1.2630 + if( !zSql ){
1.2631 + return SQLITE_NOMEM;
1.2632 + }
1.2633 +
1.2634 + rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
1.2635 + sqlite3_free(zSql);
1.2636 + if( rc!=SQLITE_OK ){
1.2637 + return rc;
1.2638 + }
1.2639 +
1.2640 + if( SQLITE_ROW==sqlite3_step(pStmt) ){
1.2641 + *piPageSize = sqlite3_column_int(pStmt, 0);
1.2642 + }
1.2643 + return sqlite3_finalize(pStmt);
1.2644 +}
1.2645 +
1.2646 +/*
1.2647 +** This function is the implementation of both the xConnect and xCreate
1.2648 +** methods of the r-tree virtual table.
1.2649 +**
1.2650 +** argv[0] -> module name
1.2651 +** argv[1] -> database name
1.2652 +** argv[2] -> table name
1.2653 +** argv[...] -> column names...
1.2654 +*/
1.2655 +static int rtreeInit(
1.2656 + sqlite3 *db, /* Database connection */
1.2657 + void *pAux, /* Pointer to head of rtree list */
1.2658 + int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */
1.2659 + sqlite3_vtab **ppVtab, /* OUT: New virtual table */
1.2660 + char **pzErr, /* OUT: Error message, if any */
1.2661 + int isCreate, /* True for xCreate, false for xConnect */
1.2662 + int eCoordType /* One of the RTREE_COORD_* constants */
1.2663 +){
1.2664 + int rc = SQLITE_OK;
1.2665 + int iPageSize = 0;
1.2666 + Rtree *pRtree;
1.2667 + int nDb; /* Length of string argv[1] */
1.2668 + int nName; /* Length of string argv[2] */
1.2669 +
1.2670 + const char *aErrMsg[] = {
1.2671 + 0, /* 0 */
1.2672 + "Wrong number of columns for an rtree table", /* 1 */
1.2673 + "Too few columns for an rtree table", /* 2 */
1.2674 + "Too many columns for an rtree table" /* 3 */
1.2675 + };
1.2676 +
1.2677 + int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
1.2678 + if( aErrMsg[iErr] ){
1.2679 + *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
1.2680 + return SQLITE_ERROR;
1.2681 + }
1.2682 +
1.2683 + rc = getPageSize(db, argv[1], &iPageSize);
1.2684 + if( rc!=SQLITE_OK ){
1.2685 + return rc;
1.2686 + }
1.2687 +
1.2688 + /* Allocate the sqlite3_vtab structure */
1.2689 + nDb = strlen(argv[1]);
1.2690 + nName = strlen(argv[2]);
1.2691 + pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
1.2692 + if( !pRtree ){
1.2693 + return SQLITE_NOMEM;
1.2694 + }
1.2695 + memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
1.2696 + pRtree->nBusy = 1;
1.2697 + pRtree->base.pModule = &rtreeModule;
1.2698 + pRtree->zDb = (char *)&pRtree[1];
1.2699 + pRtree->zName = &pRtree->zDb[nDb+1];
1.2700 + pRtree->nDim = (argc-4)/2;
1.2701 + pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
1.2702 + pRtree->eCoordType = eCoordType;
1.2703 + memcpy(pRtree->zDb, argv[1], nDb);
1.2704 + memcpy(pRtree->zName, argv[2], nName);
1.2705 +
1.2706 + /* Figure out the node size to use. By default, use 64 bytes less than
1.2707 + ** the database page-size. This ensures that each node is stored on
1.2708 + ** a single database page.
1.2709 + **
1.2710 + ** If the databasd page-size is so large that more than RTREE_MAXCELLS
1.2711 + ** entries would fit in a single node, use a smaller node-size.
1.2712 + */
1.2713 + pRtree->iNodeSize = iPageSize-64;
1.2714 + if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
1.2715 + pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
1.2716 + }
1.2717 +
1.2718 + /* Create/Connect to the underlying relational database schema. If
1.2719 + ** that is successful, call sqlite3_declare_vtab() to configure
1.2720 + ** the r-tree table schema.
1.2721 + */
1.2722 + if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
1.2723 + *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
1.2724 + }else{
1.2725 + char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
1.2726 + char *zTmp;
1.2727 + int ii;
1.2728 + for(ii=4; zSql && ii<argc; ii++){
1.2729 + zTmp = zSql;
1.2730 + zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
1.2731 + sqlite3_free(zTmp);
1.2732 + }
1.2733 + if( zSql ){
1.2734 + zTmp = zSql;
1.2735 + zSql = sqlite3_mprintf("%s);", zTmp);
1.2736 + sqlite3_free(zTmp);
1.2737 + }
1.2738 + if( !zSql || sqlite3_declare_vtab(db, zSql) ){
1.2739 + rc = SQLITE_NOMEM;
1.2740 + }
1.2741 + sqlite3_free(zSql);
1.2742 + }
1.2743 +
1.2744 + if( rc==SQLITE_OK ){
1.2745 + *ppVtab = (sqlite3_vtab *)pRtree;
1.2746 + }else{
1.2747 + rtreeRelease(pRtree);
1.2748 + }
1.2749 + return rc;
1.2750 +}
1.2751 +
1.2752 +
1.2753 +/*
1.2754 +** Implementation of a scalar function that decodes r-tree nodes to
1.2755 +** human readable strings. This can be used for debugging and analysis.
1.2756 +**
1.2757 +** The scalar function takes two arguments, a blob of data containing
1.2758 +** an r-tree node, and the number of dimensions the r-tree indexes.
1.2759 +** For a two-dimensional r-tree structure called "rt", to deserialize
1.2760 +** all nodes, a statement like:
1.2761 +**
1.2762 +** SELECT rtreenode(2, data) FROM rt_node;
1.2763 +**
1.2764 +** The human readable string takes the form of a Tcl list with one
1.2765 +** entry for each cell in the r-tree node. Each entry is itself a
1.2766 +** list, containing the 8-byte rowid/pageno followed by the
1.2767 +** <num-dimension>*2 coordinates.
1.2768 +*/
1.2769 +static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
1.2770 + char *zText = 0;
1.2771 + RtreeNode node;
1.2772 + Rtree tree;
1.2773 + int ii;
1.2774 +
1.2775 + memset(&node, 0, sizeof(RtreeNode));
1.2776 + memset(&tree, 0, sizeof(Rtree));
1.2777 + tree.nDim = sqlite3_value_int(apArg[0]);
1.2778 + tree.nBytesPerCell = 8 + 8 * tree.nDim;
1.2779 + node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
1.2780 +
1.2781 + for(ii=0; ii<NCELL(&node); ii++){
1.2782 + char zCell[512];
1.2783 + int nCell = 0;
1.2784 + RtreeCell cell;
1.2785 + int jj;
1.2786 +
1.2787 + nodeGetCell(&tree, &node, ii, &cell);
1.2788 + sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid);
1.2789 + nCell = strlen(zCell);
1.2790 + for(jj=0; jj<tree.nDim*2; jj++){
1.2791 + sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
1.2792 + nCell = strlen(zCell);
1.2793 + }
1.2794 +
1.2795 + if( zText ){
1.2796 + char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
1.2797 + sqlite3_free(zText);
1.2798 + zText = zTextNew;
1.2799 + }else{
1.2800 + zText = sqlite3_mprintf("{%s}", zCell);
1.2801 + }
1.2802 + }
1.2803 +
1.2804 + sqlite3_result_text(ctx, zText, -1, sqlite3_free);
1.2805 +}
1.2806 +
1.2807 +static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
1.2808 + if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB
1.2809 + || sqlite3_value_bytes(apArg[0])<2
1.2810 + ){
1.2811 + sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1);
1.2812 + }else{
1.2813 + u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]);
1.2814 + sqlite3_result_int(ctx, readInt16(zBlob));
1.2815 + }
1.2816 +}
1.2817 +
1.2818 +/*
1.2819 +** Register the r-tree module with database handle db. This creates the
1.2820 +** virtual table module "rtree" and the debugging/analysis scalar
1.2821 +** function "rtreenode".
1.2822 +*/
1.2823 +int sqlite3RtreeInit(sqlite3 *db){
1.2824 + int rc = SQLITE_OK;
1.2825 +
1.2826 + if( rc==SQLITE_OK ){
1.2827 + int utf8 = SQLITE_UTF8;
1.2828 + rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
1.2829 + }
1.2830 + if( rc==SQLITE_OK ){
1.2831 + int utf8 = SQLITE_UTF8;
1.2832 + rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
1.2833 + }
1.2834 + if( rc==SQLITE_OK ){
1.2835 + void *c = (void *)RTREE_COORD_REAL32;
1.2836 + rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
1.2837 + }
1.2838 + if( rc==SQLITE_OK ){
1.2839 + void *c = (void *)RTREE_COORD_INT32;
1.2840 + rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
1.2841 + }
1.2842 +
1.2843 + return rc;
1.2844 +}
1.2845 +
1.2846 +#if !SQLITE_CORE
1.2847 +int sqlite3_extension_init(
1.2848 + sqlite3 *db,
1.2849 + char **pzErrMsg,
1.2850 + const sqlite3_api_routines *pApi
1.2851 +){
1.2852 + SQLITE_EXTENSION_INIT2(pApi)
1.2853 + return sqlite3RtreeInit(db);
1.2854 +}
1.2855 +#endif
1.2856 +
1.2857 +#endif