| 1 |
/* |
| 2 |
** 2001 September 15 |
| 3 |
** |
| 4 |
** The author disclaims copyright to this source code. In place of |
| 5 |
** a legal notice, here is a blessing: |
| 6 |
** |
| 7 |
** May you do good and not evil. |
| 8 |
** May you find forgiveness for yourself and forgive others. |
| 9 |
** May you share freely, never taking more than you give. |
| 10 |
** |
| 11 |
************************************************************************* |
| 12 |
** This file contains code for implementations of the r-tree and r*-tree |
| 13 |
** algorithms packaged as an SQLite virtual table module. |
| 14 |
*/ |
| 15 |
|
| 16 |
/* |
| 17 |
** Database Format of R-Tree Tables |
| 18 |
** -------------------------------- |
| 19 |
** |
| 20 |
** The data structure for a single virtual r-tree table is stored in three |
| 21 |
** native SQLite tables declared as follows. In each case, the '%' character |
| 22 |
** in the table name is replaced with the user-supplied name of the r-tree |
| 23 |
** table. |
| 24 |
** |
| 25 |
** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB) |
| 26 |
** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) |
| 27 |
** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...) |
| 28 |
** |
| 29 |
** The data for each node of the r-tree structure is stored in the %_node |
| 30 |
** table. For each node that is not the root node of the r-tree, there is |
| 31 |
** an entry in the %_parent table associating the node with its parent. |
| 32 |
** And for each row of data in the table, there is an entry in the %_rowid |
| 33 |
** table that maps from the entries rowid to the id of the node that it |
| 34 |
** is stored on. If the r-tree contains auxiliary columns, those are stored |
| 35 |
** on the end of the %_rowid table. |
| 36 |
** |
| 37 |
** The root node of an r-tree always exists, even if the r-tree table is |
| 38 |
** empty. The nodeno of the root node is always 1. All other nodes in the |
| 39 |
** table must be the same size as the root node. The content of each node |
| 40 |
** is formatted as follows: |
| 41 |
** |
| 42 |
** 1. If the node is the root node (node 1), then the first 2 bytes |
| 43 |
** of the node contain the tree depth as a big-endian integer. |
| 44 |
** For non-root nodes, the first 2 bytes are left unused. |
| 45 |
** |
| 46 |
** 2. The next 2 bytes contain the number of entries currently |
| 47 |
** stored in the node. |
| 48 |
** |
| 49 |
** 3. The remainder of the node contains the node entries. Each entry |
| 50 |
** consists of a single 8-byte integer followed by an even number |
| 51 |
** of 4-byte coordinates. For leaf nodes the integer is the rowid |
| 52 |
** of a record. For internal nodes it is the node number of a |
| 53 |
** child page. |
| 54 |
*/ |
| 55 |
|
| 56 |
#if !defined(SQLITE_CORE) \ |
| 57 |
|| (defined(SQLITE_ENABLE_RTREE) && !defined(SQLITE_OMIT_VIRTUALTABLE)) |
| 58 |
|
| 59 |
#ifndef SQLITE_CORE |
| 60 |
#include "sqlite3ext.h" |
| 61 |
SQLITE_EXTENSION_INIT1 |
| 62 |
#else |
| 63 |
#include "sqlite3.h" |
| 64 |
#endif |
| 65 |
sqlite3_int64 sqlite3GetToken(const unsigned char*,int*); /* In SQLite core */ |
| 66 |
|
| 67 |
#include <stddef.h> |
| 68 |
|
| 69 |
/* |
| 70 |
** If building separately, we will need some setup that is normally |
| 71 |
** found in sqliteInt.h |
| 72 |
*/ |
| 73 |
#if !defined(SQLITE_AMALGAMATION) |
| 74 |
#include "sqlite3rtree.h" |
| 75 |
typedef sqlite3_int64 i64; |
| 76 |
typedef sqlite3_uint64 u64; |
| 77 |
typedef unsigned char u8; |
| 78 |
typedef unsigned short u16; |
| 79 |
typedef unsigned int u32; |
| 80 |
#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) |
| 81 |
# define NDEBUG 1 |
| 82 |
#endif |
| 83 |
#if defined(NDEBUG) && defined(SQLITE_DEBUG) |
| 84 |
# undef NDEBUG |
| 85 |
#endif |
| 86 |
#if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST) |
| 87 |
# define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1 |
| 88 |
#endif |
| 89 |
#if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS) |
| 90 |
# define ALWAYS(X) (1) |
| 91 |
# define NEVER(X) (0) |
| 92 |
#elif !defined(NDEBUG) |
| 93 |
# define ALWAYS(X) ((X)?1:(assert(0),0)) |
| 94 |
# define NEVER(X) ((X)?(assert(0),1):0) |
| 95 |
#else |
| 96 |
# define ALWAYS(X) (X) |
| 97 |
# define NEVER(X) (X) |
| 98 |
#endif |
| 99 |
#ifndef offsetof |
| 100 |
# define offsetof(ST,M) ((size_t)((char*)&((ST*)0)->M - (char*)0)) |
| 101 |
#endif |
| 102 |
#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) |
| 103 |
# define FLEXARRAY |
| 104 |
#else |
| 105 |
# define FLEXARRAY 1 |
| 106 |
#endif |
| 107 |
#endif /* !defined(SQLITE_AMALGAMATION) */ |
| 108 |
|
| 109 |
/* Macro to check for 4-byte alignment. Only used inside of assert() */ |
| 110 |
#ifdef SQLITE_DEBUG |
| 111 |
# define FOUR_BYTE_ALIGNED(X) ((((char*)(X) - (char*)0) & 3)==0) |
| 112 |
#endif |
| 113 |
|
| 114 |
#include <string.h> |
| 115 |
#include <stdio.h> |
| 116 |
#include <assert.h> |
| 117 |
#include <stdlib.h> |
| 118 |
|
| 119 |
/* The following macro is used to suppress compiler warnings. |
| 120 |
*/ |
| 121 |
#ifndef UNUSED_PARAMETER |
| 122 |
# define UNUSED_PARAMETER(x) (void)(x) |
| 123 |
#endif |
| 124 |
|
| 125 |
typedef struct Rtree Rtree; |
| 126 |
typedef struct RtreeCursor RtreeCursor; |
| 127 |
typedef struct RtreeNode RtreeNode; |
| 128 |
typedef struct RtreeCell RtreeCell; |
| 129 |
typedef struct RtreeConstraint RtreeConstraint; |
| 130 |
typedef struct RtreeMatchArg RtreeMatchArg; |
| 131 |
typedef struct RtreeGeomCallback RtreeGeomCallback; |
| 132 |
typedef union RtreeCoord RtreeCoord; |
| 133 |
typedef struct RtreeSearchPoint RtreeSearchPoint; |
| 134 |
|
| 135 |
/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ |
| 136 |
#define RTREE_MAX_DIMENSIONS 5 |
| 137 |
|
| 138 |
/* Maximum number of auxiliary columns */ |
| 139 |
#define RTREE_MAX_AUX_COLUMN 100 |
| 140 |
|
| 141 |
/* Size of hash table Rtree.aHash. This hash table is not expected to |
| 142 |
** ever contain very many entries, so a fixed number of buckets is |
| 143 |
** used. |
| 144 |
*/ |
| 145 |
#define HASHSIZE 97 |
| 146 |
|
| 147 |
/* The xBestIndex method of this virtual table requires an estimate of |
| 148 |
** the number of rows in the virtual table to calculate the costs of |
| 149 |
** various strategies. If possible, this estimate is loaded from the |
| 150 |
** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum). |
| 151 |
** Otherwise, if no sqlite_stat1 entry is available, use |
| 152 |
** RTREE_DEFAULT_ROWEST. |
| 153 |
*/ |
| 154 |
#define RTREE_DEFAULT_ROWEST 1048576 |
| 155 |
#define RTREE_MIN_ROWEST 100 |
| 156 |
|
| 157 |
/* |
| 158 |
** An rtree virtual-table object. |
| 159 |
*/ |
| 160 |
struct Rtree { |
| 161 |
sqlite3_vtab base; /* Base class. Must be first */ |
| 162 |
sqlite3 *db; /* Host database connection */ |
| 163 |
int iNodeSize; /* Size in bytes of each node in the node table */ |
| 164 |
u8 nDim; /* Number of dimensions */ |
| 165 |
u8 nDim2; /* Twice the number of dimensions */ |
| 166 |
u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ |
| 167 |
u8 nBytesPerCell; /* Bytes consumed per cell */ |
| 168 |
u8 inWrTrans; /* True if inside write transaction */ |
| 169 |
u16 nAux; /* # of auxiliary columns in %_rowid */ |
| 170 |
#ifdef SQLITE_ENABLE_GEOPOLY |
| 171 |
u8 nAuxNotNull; /* Number of initial not-null aux columns */ |
| 172 |
#endif |
| 173 |
#ifdef SQLITE_DEBUG |
| 174 |
u8 bCorrupt; /* Shadow table corruption detected */ |
| 175 |
#endif |
| 176 |
int iDepth; /* Current depth of the r-tree structure */ |
| 177 |
char *zDb; /* Name of database containing r-tree table */ |
| 178 |
char *zName; /* Name of r-tree table */ |
| 179 |
char *zNodeName; /* Name of the %_node table */ |
| 180 |
u32 nBusy; /* Current number of users of this structure */ |
| 181 |
i64 nRowEst; /* Estimated number of rows in this table */ |
| 182 |
u32 nCursor; /* Number of open cursors */ |
| 183 |
u32 nNodeRef; /* Number RtreeNodes with positive nRef */ |
| 184 |
char *zReadAuxSql; /* SQL for statement to read aux data */ |
| 185 |
|
| 186 |
/* List of nodes removed during a CondenseTree operation. List is |
| 187 |
** linked together via the pointer normally used for hash chains - |
| 188 |
** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree |
| 189 |
** headed by the node (leaf nodes have RtreeNode.iNode==0). |
| 190 |
*/ |
| 191 |
RtreeNode *pDeleted; |
| 192 |
|
| 193 |
/* Blob I/O on xxx_node */ |
| 194 |
sqlite3_blob *pNodeBlob; |
| 195 |
|
| 196 |
/* Statements to read/write/delete a record from xxx_node */ |
| 197 |
sqlite3_stmt *pWriteNode; |
| 198 |
sqlite3_stmt *pDeleteNode; |
| 199 |
|
| 200 |
/* Statements to read/write/delete a record from xxx_rowid */ |
| 201 |
sqlite3_stmt *pReadRowid; |
| 202 |
sqlite3_stmt *pWriteRowid; |
| 203 |
sqlite3_stmt *pDeleteRowid; |
| 204 |
|
| 205 |
/* Statements to read/write/delete a record from xxx_parent */ |
| 206 |
sqlite3_stmt *pReadParent; |
| 207 |
sqlite3_stmt *pWriteParent; |
| 208 |
sqlite3_stmt *pDeleteParent; |
| 209 |
|
| 210 |
/* Statement for writing to the "aux:" fields, if there are any */ |
| 211 |
sqlite3_stmt *pWriteAux; |
| 212 |
|
| 213 |
RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ |
| 214 |
}; |
| 215 |
|
| 216 |
/* Possible values for Rtree.eCoordType: */ |
| 217 |
#define RTREE_COORD_REAL32 0 |
| 218 |
#define RTREE_COORD_INT32 1 |
| 219 |
|
| 220 |
/* |
| 221 |
** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will |
| 222 |
** only deal with integer coordinates. No floating point operations |
| 223 |
** will be done. |
| 224 |
*/ |
| 225 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 226 |
typedef sqlite3_int64 RtreeDValue; /* High accuracy coordinate */ |
| 227 |
typedef int RtreeValue; /* Low accuracy coordinate */ |
| 228 |
# define RTREE_ZERO 0 |
| 229 |
#else |
| 230 |
typedef double RtreeDValue; /* High accuracy coordinate */ |
| 231 |
typedef float RtreeValue; /* Low accuracy coordinate */ |
| 232 |
# define RTREE_ZERO 0.0 |
| 233 |
#endif |
| 234 |
|
| 235 |
/* |
| 236 |
** Set the Rtree.bCorrupt flag |
| 237 |
*/ |
| 238 |
#ifdef SQLITE_DEBUG |
| 239 |
# define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1) |
| 240 |
#else |
| 241 |
# define RTREE_IS_CORRUPT(X) |
| 242 |
#endif |
| 243 |
|
| 244 |
/* |
| 245 |
** When doing a search of an r-tree, instances of the following structure |
| 246 |
** record intermediate results from the tree walk. |
| 247 |
** |
| 248 |
** The id is always a node-id. For iLevel>=1 the id is the node-id of |
| 249 |
** the node that the RtreeSearchPoint represents. When iLevel==0, however, |
| 250 |
** the id is of the parent node and the cell that RtreeSearchPoint |
| 251 |
** represents is the iCell-th entry in the parent node. |
| 252 |
*/ |
| 253 |
struct RtreeSearchPoint { |
| 254 |
RtreeDValue rScore; /* The score for this node. Smallest goes first. */ |
| 255 |
sqlite3_int64 id; /* Node ID */ |
| 256 |
u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */ |
| 257 |
u8 eWithin; /* PARTLY_WITHIN or FULLY_WITHIN */ |
| 258 |
u8 iCell; /* Cell index within the node */ |
| 259 |
}; |
| 260 |
|
| 261 |
/* |
| 262 |
** The minimum number of cells allowed for a node is a third of the |
| 263 |
** maximum. In Gutman's notation: |
| 264 |
** |
| 265 |
** m = M/3 |
| 266 |
** |
| 267 |
** If an R*-tree "Reinsert" operation is required, the same number of |
| 268 |
** cells are removed from the overfull node and reinserted into the tree. |
| 269 |
*/ |
| 270 |
#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3) |
| 271 |
#define RTREE_REINSERT(p) RTREE_MINCELLS(p) |
| 272 |
#define RTREE_MAXCELLS 51 |
| 273 |
|
| 274 |
/* |
| 275 |
** The smallest possible node-size is (512-64)==448 bytes. And the largest |
| 276 |
** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates). |
| 277 |
** Therefore all non-root nodes must contain at least 3 entries. Since |
| 278 |
** 3^40 is greater than 2^64, an r-tree structure always has a depth of |
| 279 |
** 40 or less. |
| 280 |
*/ |
| 281 |
#define RTREE_MAX_DEPTH 40 |
| 282 |
|
| 283 |
|
| 284 |
/* |
| 285 |
** Number of entries in the cursor RtreeNode cache. The first entry is |
| 286 |
** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining |
| 287 |
** entries cache the RtreeNode for the first elements of the priority queue. |
| 288 |
*/ |
| 289 |
#define RTREE_CACHE_SZ 5 |
| 290 |
|
| 291 |
/* |
| 292 |
** An rtree cursor object. |
| 293 |
*/ |
| 294 |
struct RtreeCursor { |
| 295 |
sqlite3_vtab_cursor base; /* Base class. Must be first */ |
| 296 |
u8 atEOF; /* True if at end of search */ |
| 297 |
u8 bPoint; /* True if sPoint is valid */ |
| 298 |
u8 bAuxValid; /* True if pReadAux is valid */ |
| 299 |
int iStrategy; /* Copy of idxNum search parameter */ |
| 300 |
int nConstraint; /* Number of entries in aConstraint */ |
| 301 |
RtreeConstraint *aConstraint; /* Search constraints. */ |
| 302 |
int nPointAlloc; /* Number of slots allocated for aPoint[] */ |
| 303 |
int nPoint; /* Number of slots used in aPoint[] */ |
| 304 |
int mxLevel; /* iLevel value for root of the tree */ |
| 305 |
RtreeSearchPoint *aPoint; /* Priority queue for search points */ |
| 306 |
sqlite3_stmt *pReadAux; /* Statement to read aux-data */ |
| 307 |
RtreeSearchPoint sPoint; /* Cached next search point */ |
| 308 |
RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */ |
| 309 |
u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */ |
| 310 |
}; |
| 311 |
|
| 312 |
/* Return the Rtree of a RtreeCursor */ |
| 313 |
#define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab)) |
| 314 |
|
| 315 |
/* |
| 316 |
** A coordinate can be either a floating point number or a integer. All |
| 317 |
** coordinates within a single R-Tree are always of the same time. |
| 318 |
*/ |
| 319 |
union RtreeCoord { |
| 320 |
RtreeValue f; /* Floating point value */ |
| 321 |
int i; /* Integer value */ |
| 322 |
u32 u; /* Unsigned for byte-order conversions */ |
| 323 |
}; |
| 324 |
|
| 325 |
/* |
| 326 |
** The argument is an RtreeCoord. Return the value stored within the RtreeCoord |
| 327 |
** formatted as a RtreeDValue (double or int64). This macro assumes that local |
| 328 |
** variable pRtree points to the Rtree structure associated with the |
| 329 |
** RtreeCoord. |
| 330 |
*/ |
| 331 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 332 |
# define DCOORD(coord) ((RtreeDValue)coord.i) |
| 333 |
#else |
| 334 |
# define DCOORD(coord) ( \ |
| 335 |
(pRtree->eCoordType==RTREE_COORD_REAL32) ? \ |
| 336 |
((double)coord.f) : \ |
| 337 |
((double)coord.i) \ |
| 338 |
) |
| 339 |
#endif |
| 340 |
|
| 341 |
/* |
| 342 |
** A search constraint. |
| 343 |
*/ |
| 344 |
struct RtreeConstraint { |
| 345 |
int iCoord; /* Index of constrained coordinate */ |
| 346 |
int op; /* Constraining operation */ |
| 347 |
union { |
| 348 |
RtreeDValue rValue; /* Constraint value. */ |
| 349 |
int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*); |
| 350 |
int (*xQueryFunc)(sqlite3_rtree_query_info*); |
| 351 |
} u; |
| 352 |
sqlite3_rtree_query_info *pInfo; /* xGeom and xQueryFunc argument */ |
| 353 |
}; |
| 354 |
|
| 355 |
/* Possible values for RtreeConstraint.op */ |
| 356 |
#define RTREE_EQ 0x41 /* A */ |
| 357 |
#define RTREE_LE 0x42 /* B */ |
| 358 |
#define RTREE_LT 0x43 /* C */ |
| 359 |
#define RTREE_GE 0x44 /* D */ |
| 360 |
#define RTREE_GT 0x45 /* E */ |
| 361 |
#define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */ |
| 362 |
#define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */ |
| 363 |
|
| 364 |
/* Special operators available only on cursors. Needs to be consecutive |
| 365 |
** with the normal values above, but must be less than RTREE_MATCH. These |
| 366 |
** are used in the cursor for contraints such as x=NULL (RTREE_FALSE) or |
| 367 |
** x<'xyz' (RTREE_TRUE) */ |
| 368 |
#define RTREE_TRUE 0x3f /* ? */ |
| 369 |
#define RTREE_FALSE 0x40 /* @ */ |
| 370 |
|
| 371 |
/* |
| 372 |
** An rtree structure node. |
| 373 |
*/ |
| 374 |
struct RtreeNode { |
| 375 |
RtreeNode *pParent; /* Parent node */ |
| 376 |
i64 iNode; /* The node number */ |
| 377 |
int nRef; /* Number of references to this node */ |
| 378 |
int isDirty; /* True if the node needs to be written to disk */ |
| 379 |
u8 *zData; /* Content of the node, as should be on disk */ |
| 380 |
RtreeNode *pNext; /* Next node in this hash collision chain */ |
| 381 |
}; |
| 382 |
|
| 383 |
/* Return the number of cells in a node */ |
| 384 |
#define NCELL(pNode) readInt16(&(pNode)->zData[2]) |
| 385 |
|
| 386 |
/* |
| 387 |
** A single cell from a node, deserialized |
| 388 |
*/ |
| 389 |
struct RtreeCell { |
| 390 |
i64 iRowid; /* Node or entry ID */ |
| 391 |
RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */ |
| 392 |
}; |
| 393 |
|
| 394 |
|
| 395 |
/* |
| 396 |
** This object becomes the sqlite3_user_data() for the SQL functions |
| 397 |
** that are created by sqlite3_rtree_geometry_callback() and |
| 398 |
** sqlite3_rtree_query_callback() and which appear on the right of MATCH |
| 399 |
** operators in order to constrain a search. |
| 400 |
** |
| 401 |
** xGeom and xQueryFunc are the callback functions. Exactly one of |
| 402 |
** xGeom and xQueryFunc fields is non-NULL, depending on whether the |
| 403 |
** SQL function was created using sqlite3_rtree_geometry_callback() or |
| 404 |
** sqlite3_rtree_query_callback(). |
| 405 |
** |
| 406 |
** This object is deleted automatically by the destructor mechanism in |
| 407 |
** sqlite3_create_function_v2(). |
| 408 |
*/ |
| 409 |
struct RtreeGeomCallback { |
| 410 |
int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*); |
| 411 |
int (*xQueryFunc)(sqlite3_rtree_query_info*); |
| 412 |
void (*xDestructor)(void*); |
| 413 |
void *pContext; |
| 414 |
}; |
| 415 |
|
| 416 |
/* |
| 417 |
** An instance of this structure (in the form of a BLOB) is returned by |
| 418 |
** the SQL functions that sqlite3_rtree_geometry_callback() and |
| 419 |
** sqlite3_rtree_query_callback() create, and is read as the right-hand |
| 420 |
** operand to the MATCH operator of an R-Tree. |
| 421 |
*/ |
| 422 |
struct RtreeMatchArg { |
| 423 |
u32 iSize; /* Size of this object */ |
| 424 |
RtreeGeomCallback cb; /* Info about the callback functions */ |
| 425 |
int nParam; /* Number of parameters to the SQL function */ |
| 426 |
sqlite3_value **apSqlParam; /* Original SQL parameter values */ |
| 427 |
RtreeDValue aParam[FLEXARRAY]; /* Values for parameters to the SQL function */ |
| 428 |
}; |
| 429 |
|
| 430 |
/* Size of an RtreeMatchArg object with N parameters */ |
| 431 |
#define SZ_RTREEMATCHARG(N) \ |
| 432 |
(offsetof(RtreeMatchArg,aParam)+(N)*sizeof(RtreeDValue)) |
| 433 |
|
| 434 |
#ifndef MAX |
| 435 |
# define MAX(x,y) ((x) < (y) ? (y) : (x)) |
| 436 |
#endif |
| 437 |
#ifndef MIN |
| 438 |
# define MIN(x,y) ((x) > (y) ? (y) : (x)) |
| 439 |
#endif |
| 440 |
|
| 441 |
/* What version of GCC is being used. 0 means GCC is not being used . |
| 442 |
** Note that the GCC_VERSION macro will also be set correctly when using |
| 443 |
** clang, since clang works hard to be gcc compatible. So the gcc |
| 444 |
** optimizations will also work when compiling with clang. |
| 445 |
*/ |
| 446 |
#ifndef GCC_VERSION |
| 447 |
#if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 448 |
# define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__) |
| 449 |
#else |
| 450 |
# define GCC_VERSION 0 |
| 451 |
#endif |
| 452 |
#endif |
| 453 |
|
| 454 |
/* The testcase() macro should already be defined in the amalgamation. If |
| 455 |
** it is not, make it a no-op. |
| 456 |
*/ |
| 457 |
#ifndef SQLITE_AMALGAMATION |
| 458 |
# if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_DEBUG) |
| 459 |
unsigned int sqlite3RtreeTestcase = 0; |
| 460 |
# define testcase(X) if( X ){ sqlite3RtreeTestcase += __LINE__; } |
| 461 |
# else |
| 462 |
# define testcase(X) |
| 463 |
# endif |
| 464 |
#endif |
| 465 |
|
| 466 |
/* |
| 467 |
** Make sure that the compiler intrinsics we desire are enabled when |
| 468 |
** compiling with an appropriate version of MSVC unless prevented by |
| 469 |
** the SQLITE_DISABLE_INTRINSIC define. |
| 470 |
*/ |
| 471 |
#if !defined(SQLITE_DISABLE_INTRINSIC) |
| 472 |
# if defined(_MSC_VER) && _MSC_VER>=1400 |
| 473 |
# if !defined(_WIN32_WCE) |
| 474 |
# include <intrin.h> |
| 475 |
# pragma intrinsic(_byteswap_ulong) |
| 476 |
# pragma intrinsic(_byteswap_uint64) |
| 477 |
# else |
| 478 |
# include <cmnintrin.h> |
| 479 |
# endif |
| 480 |
# endif |
| 481 |
#endif |
| 482 |
|
| 483 |
/* |
| 484 |
** Macros to determine whether the machine is big or little endian, |
| 485 |
** and whether or not that determination is run-time or compile-time. |
| 486 |
** |
| 487 |
** For best performance, an attempt is made to guess at the byte-order |
| 488 |
** using C-preprocessor macros. If that is unsuccessful, or if |
| 489 |
** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined |
| 490 |
** at run-time. |
| 491 |
*/ |
| 492 |
#ifndef SQLITE_BYTEORDER /* Replicate changes at tag-20230904a */ |
| 493 |
# if defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_BIG_ENDIAN__ |
| 494 |
# define SQLITE_BYTEORDER 4321 |
| 495 |
# elif defined(__BYTE_ORDER__) && __BYTE_ORDER__==__ORDER_LITTLE_ENDIAN__ |
| 496 |
# define SQLITE_BYTEORDER 1234 |
| 497 |
# elif defined(__BIG_ENDIAN__) && __BIG_ENDIAN__==1 |
| 498 |
# define SQLITE_BYTEORDER 4321 |
| 499 |
# elif defined(i386) || defined(__i386__) || defined(_M_IX86) || \ |
| 500 |
defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \ |
| 501 |
defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \ |
| 502 |
defined(__ARMEL__) || defined(__AARCH64EL__) || defined(_M_ARM64) |
| 503 |
# define SQLITE_BYTEORDER 1234 |
| 504 |
# elif defined(sparc) || defined(__ARMEB__) || defined(__AARCH64EB__) |
| 505 |
# define SQLITE_BYTEORDER 4321 |
| 506 |
# else |
| 507 |
# define SQLITE_BYTEORDER 0 |
| 508 |
# endif |
| 509 |
#endif |
| 510 |
|
| 511 |
|
| 512 |
/* What version of MSVC is being used. 0 means MSVC is not being used */ |
| 513 |
#ifndef MSVC_VERSION |
| 514 |
#if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 515 |
# define MSVC_VERSION _MSC_VER |
| 516 |
#else |
| 517 |
# define MSVC_VERSION 0 |
| 518 |
#endif |
| 519 |
#endif |
| 520 |
|
| 521 |
/* |
| 522 |
** Functions to deserialize a 16 bit integer, 32 bit real number and |
| 523 |
** 64 bit integer. The deserialized value is returned. |
| 524 |
*/ |
| 525 |
static int readInt16(u8 *p){ |
| 526 |
return (p[0]<<8) + p[1]; |
| 527 |
} |
| 528 |
static void readCoord(u8 *p, RtreeCoord *pCoord){ |
| 529 |
assert( FOUR_BYTE_ALIGNED(p) ); |
| 530 |
#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 531 |
pCoord->u = _byteswap_ulong(*(u32*)p); |
| 532 |
#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000 |
| 533 |
pCoord->u = __builtin_bswap32(*(u32*)p); |
| 534 |
#elif SQLITE_BYTEORDER==4321 |
| 535 |
pCoord->u = *(u32*)p; |
| 536 |
#else |
| 537 |
pCoord->u = ( |
| 538 |
(((u32)p[0]) << 24) + |
| 539 |
(((u32)p[1]) << 16) + |
| 540 |
(((u32)p[2]) << 8) + |
| 541 |
(((u32)p[3]) << 0) |
| 542 |
); |
| 543 |
#endif |
| 544 |
} |
| 545 |
static i64 readInt64(u8 *p){ |
| 546 |
#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 547 |
u64 x; |
| 548 |
memcpy(&x, p, 8); |
| 549 |
return (i64)_byteswap_uint64(x); |
| 550 |
#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000 |
| 551 |
u64 x; |
| 552 |
memcpy(&x, p, 8); |
| 553 |
return (i64)__builtin_bswap64(x); |
| 554 |
#elif SQLITE_BYTEORDER==4321 |
| 555 |
i64 x; |
| 556 |
memcpy(&x, p, 8); |
| 557 |
return x; |
| 558 |
#else |
| 559 |
return (i64)( |
| 560 |
(((u64)p[0]) << 56) + |
| 561 |
(((u64)p[1]) << 48) + |
| 562 |
(((u64)p[2]) << 40) + |
| 563 |
(((u64)p[3]) << 32) + |
| 564 |
(((u64)p[4]) << 24) + |
| 565 |
(((u64)p[5]) << 16) + |
| 566 |
(((u64)p[6]) << 8) + |
| 567 |
(((u64)p[7]) << 0) |
| 568 |
); |
| 569 |
#endif |
| 570 |
} |
| 571 |
|
| 572 |
/* |
| 573 |
** Functions to serialize a 16 bit integer, 32 bit real number and |
| 574 |
** 64 bit integer. The value returned is the number of bytes written |
| 575 |
** to the argument buffer (always 2, 4 and 8 respectively). |
| 576 |
*/ |
| 577 |
static void writeInt16(u8 *p, int i){ |
| 578 |
p[0] = (i>> 8)&0xFF; |
| 579 |
p[1] = (i>> 0)&0xFF; |
| 580 |
} |
| 581 |
static int writeCoord(u8 *p, RtreeCoord *pCoord){ |
| 582 |
u32 i; |
| 583 |
assert( FOUR_BYTE_ALIGNED(p) ); |
| 584 |
assert( sizeof(RtreeCoord)==4 ); |
| 585 |
assert( sizeof(u32)==4 ); |
| 586 |
#if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000 |
| 587 |
i = __builtin_bswap32(pCoord->u); |
| 588 |
memcpy(p, &i, 4); |
| 589 |
#elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 590 |
i = _byteswap_ulong(pCoord->u); |
| 591 |
memcpy(p, &i, 4); |
| 592 |
#elif SQLITE_BYTEORDER==4321 |
| 593 |
i = pCoord->u; |
| 594 |
memcpy(p, &i, 4); |
| 595 |
#else |
| 596 |
i = pCoord->u; |
| 597 |
p[0] = (i>>24)&0xFF; |
| 598 |
p[1] = (i>>16)&0xFF; |
| 599 |
p[2] = (i>> 8)&0xFF; |
| 600 |
p[3] = (i>> 0)&0xFF; |
| 601 |
#endif |
| 602 |
return 4; |
| 603 |
} |
| 604 |
static int writeInt64(u8 *p, i64 i){ |
| 605 |
#if SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000 |
| 606 |
i = (i64)__builtin_bswap64((u64)i); |
| 607 |
memcpy(p, &i, 8); |
| 608 |
#elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 609 |
i = (i64)_byteswap_uint64((u64)i); |
| 610 |
memcpy(p, &i, 8); |
| 611 |
#elif SQLITE_BYTEORDER==4321 |
| 612 |
memcpy(p, &i, 8); |
| 613 |
#else |
| 614 |
p[0] = (i>>56)&0xFF; |
| 615 |
p[1] = (i>>48)&0xFF; |
| 616 |
p[2] = (i>>40)&0xFF; |
| 617 |
p[3] = (i>>32)&0xFF; |
| 618 |
p[4] = (i>>24)&0xFF; |
| 619 |
p[5] = (i>>16)&0xFF; |
| 620 |
p[6] = (i>> 8)&0xFF; |
| 621 |
p[7] = (i>> 0)&0xFF; |
| 622 |
#endif |
| 623 |
return 8; |
| 624 |
} |
| 625 |
|
| 626 |
/* |
| 627 |
** Increment the reference count of node p. |
| 628 |
*/ |
| 629 |
static void nodeReference(RtreeNode *p){ |
| 630 |
if( p ){ |
| 631 |
assert( p->nRef>0 ); |
| 632 |
p->nRef++; |
| 633 |
} |
| 634 |
} |
| 635 |
|
| 636 |
/* |
| 637 |
** Clear the content of node p (set all bytes to 0x00). |
| 638 |
*/ |
| 639 |
static void nodeZero(Rtree *pRtree, RtreeNode *p){ |
| 640 |
memset(&p->zData[2], 0, pRtree->iNodeSize-2); |
| 641 |
p->isDirty = 1; |
| 642 |
} |
| 643 |
|
| 644 |
/* |
| 645 |
** Given a node number iNode, return the corresponding key to use |
| 646 |
** in the Rtree.aHash table. |
| 647 |
*/ |
| 648 |
static unsigned int nodeHash(i64 iNode){ |
| 649 |
return ((unsigned)iNode) % HASHSIZE; |
| 650 |
} |
| 651 |
|
| 652 |
/* |
| 653 |
** Search the node hash table for node iNode. If found, return a pointer |
| 654 |
** to it. Otherwise, return 0. |
| 655 |
*/ |
| 656 |
static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ |
| 657 |
RtreeNode *p; |
| 658 |
for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); |
| 659 |
return p; |
| 660 |
} |
| 661 |
|
| 662 |
/* |
| 663 |
** Add node pNode to the node hash table. |
| 664 |
*/ |
| 665 |
static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ |
| 666 |
int iHash; |
| 667 |
assert( pNode->pNext==0 ); |
| 668 |
iHash = nodeHash(pNode->iNode); |
| 669 |
pNode->pNext = pRtree->aHash[iHash]; |
| 670 |
pRtree->aHash[iHash] = pNode; |
| 671 |
} |
| 672 |
|
| 673 |
/* |
| 674 |
** Remove node pNode from the node hash table. |
| 675 |
*/ |
| 676 |
static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){ |
| 677 |
RtreeNode **pp; |
| 678 |
if( pNode->iNode!=0 ){ |
| 679 |
pp = &pRtree->aHash[nodeHash(pNode->iNode)]; |
| 680 |
for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); } |
| 681 |
*pp = pNode->pNext; |
| 682 |
pNode->pNext = 0; |
| 683 |
} |
| 684 |
} |
| 685 |
|
| 686 |
/* |
| 687 |
** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0), |
| 688 |
** indicating that node has not yet been assigned a node number. It is |
| 689 |
** assigned a node number when nodeWrite() is called to write the |
| 690 |
** node contents out to the database. |
| 691 |
*/ |
| 692 |
static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){ |
| 693 |
RtreeNode *pNode; |
| 694 |
pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode) + pRtree->iNodeSize); |
| 695 |
if( pNode ){ |
| 696 |
memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize); |
| 697 |
pNode->zData = (u8 *)&pNode[1]; |
| 698 |
pNode->nRef = 1; |
| 699 |
pRtree->nNodeRef++; |
| 700 |
pNode->pParent = pParent; |
| 701 |
pNode->isDirty = 1; |
| 702 |
nodeReference(pParent); |
| 703 |
} |
| 704 |
return pNode; |
| 705 |
} |
| 706 |
|
| 707 |
/* |
| 708 |
** Clear the Rtree.pNodeBlob object |
| 709 |
*/ |
| 710 |
static void nodeBlobReset(Rtree *pRtree){ |
| 711 |
sqlite3_blob *pBlob = pRtree->pNodeBlob; |
| 712 |
pRtree->pNodeBlob = 0; |
| 713 |
sqlite3_blob_close(pBlob); |
| 714 |
} |
| 715 |
|
| 716 |
/* |
| 717 |
** Obtain a reference to an r-tree node. |
| 718 |
*/ |
| 719 |
static int nodeAcquire( |
| 720 |
Rtree *pRtree, /* R-tree structure */ |
| 721 |
i64 iNode, /* Node number to load */ |
| 722 |
RtreeNode *pParent, /* Either the parent node or NULL */ |
| 723 |
RtreeNode **ppNode /* OUT: Acquired node */ |
| 724 |
){ |
| 725 |
int rc = SQLITE_OK; |
| 726 |
RtreeNode *pNode = 0; |
| 727 |
|
| 728 |
/* Check if the requested node is already in the hash table. If so, |
| 729 |
** increase its reference count and return it. |
| 730 |
*/ |
| 731 |
if( (pNode = nodeHashLookup(pRtree, iNode))!=0 ){ |
| 732 |
if( pParent && ALWAYS(pParent!=pNode->pParent) ){ |
| 733 |
RTREE_IS_CORRUPT(pRtree); |
| 734 |
return SQLITE_CORRUPT_VTAB; |
| 735 |
} |
| 736 |
pNode->nRef++; |
| 737 |
*ppNode = pNode; |
| 738 |
return SQLITE_OK; |
| 739 |
} |
| 740 |
|
| 741 |
if( pRtree->pNodeBlob ){ |
| 742 |
sqlite3_blob *pBlob = pRtree->pNodeBlob; |
| 743 |
pRtree->pNodeBlob = 0; |
| 744 |
rc = sqlite3_blob_reopen(pBlob, iNode); |
| 745 |
pRtree->pNodeBlob = pBlob; |
| 746 |
if( rc ){ |
| 747 |
nodeBlobReset(pRtree); |
| 748 |
if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; |
| 749 |
} |
| 750 |
} |
| 751 |
if( pRtree->pNodeBlob==0 ){ |
| 752 |
rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, pRtree->zNodeName, |
| 753 |
"data", iNode, 0, |
| 754 |
&pRtree->pNodeBlob); |
| 755 |
} |
| 756 |
if( rc ){ |
| 757 |
*ppNode = 0; |
| 758 |
/* If unable to open an sqlite3_blob on the desired row, that can only |
| 759 |
** be because the shadow tables hold erroneous data. */ |
| 760 |
if( rc==SQLITE_ERROR ){ |
| 761 |
rc = SQLITE_CORRUPT_VTAB; |
| 762 |
RTREE_IS_CORRUPT(pRtree); |
| 763 |
} |
| 764 |
}else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){ |
| 765 |
pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode)+pRtree->iNodeSize); |
| 766 |
if( !pNode ){ |
| 767 |
rc = SQLITE_NOMEM; |
| 768 |
}else{ |
| 769 |
pNode->pParent = pParent; |
| 770 |
pNode->zData = (u8 *)&pNode[1]; |
| 771 |
pNode->nRef = 1; |
| 772 |
pRtree->nNodeRef++; |
| 773 |
pNode->iNode = iNode; |
| 774 |
pNode->isDirty = 0; |
| 775 |
pNode->pNext = 0; |
| 776 |
rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData, |
| 777 |
pRtree->iNodeSize, 0); |
| 778 |
} |
| 779 |
} |
| 780 |
|
| 781 |
/* If the root node was just loaded, set pRtree->iDepth to the height |
| 782 |
** of the r-tree structure. A height of zero means all data is stored on |
| 783 |
** the root node. A height of one means the children of the root node |
| 784 |
** are the leaves, and so on. If the depth as specified on the root node |
| 785 |
** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt. |
| 786 |
*/ |
| 787 |
if( rc==SQLITE_OK && pNode && iNode==1 ){ |
| 788 |
pRtree->iDepth = readInt16(pNode->zData); |
| 789 |
if( pRtree->iDepth>RTREE_MAX_DEPTH ){ |
| 790 |
rc = SQLITE_CORRUPT_VTAB; |
| 791 |
RTREE_IS_CORRUPT(pRtree); |
| 792 |
} |
| 793 |
} |
| 794 |
|
| 795 |
/* If no error has occurred so far, check if the "number of entries" |
| 796 |
** field on the node is too large. If so, set the return code to |
| 797 |
** SQLITE_CORRUPT_VTAB. |
| 798 |
*/ |
| 799 |
if( pNode && rc==SQLITE_OK ){ |
| 800 |
if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ |
| 801 |
rc = SQLITE_CORRUPT_VTAB; |
| 802 |
RTREE_IS_CORRUPT(pRtree); |
| 803 |
} |
| 804 |
} |
| 805 |
|
| 806 |
if( rc==SQLITE_OK ){ |
| 807 |
if( pNode!=0 ){ |
| 808 |
nodeReference(pParent); |
| 809 |
nodeHashInsert(pRtree, pNode); |
| 810 |
}else{ |
| 811 |
rc = SQLITE_CORRUPT_VTAB; |
| 812 |
RTREE_IS_CORRUPT(pRtree); |
| 813 |
} |
| 814 |
*ppNode = pNode; |
| 815 |
}else{ |
| 816 |
nodeBlobReset(pRtree); |
| 817 |
if( pNode ){ |
| 818 |
pRtree->nNodeRef--; |
| 819 |
sqlite3_free(pNode); |
| 820 |
} |
| 821 |
*ppNode = 0; |
| 822 |
} |
| 823 |
|
| 824 |
return rc; |
| 825 |
} |
| 826 |
|
| 827 |
/* |
| 828 |
** Overwrite cell iCell of node pNode with the contents of pCell. |
| 829 |
*/ |
| 830 |
static void nodeOverwriteCell( |
| 831 |
Rtree *pRtree, /* The overall R-Tree */ |
| 832 |
RtreeNode *pNode, /* The node into which the cell is to be written */ |
| 833 |
RtreeCell *pCell, /* The cell to write */ |
| 834 |
int iCell /* Index into pNode into which pCell is written */ |
| 835 |
){ |
| 836 |
int ii; |
| 837 |
u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
| 838 |
p += writeInt64(p, pCell->iRowid); |
| 839 |
for(ii=0; ii<pRtree->nDim2; ii++){ |
| 840 |
p += writeCoord(p, &pCell->aCoord[ii]); |
| 841 |
} |
| 842 |
pNode->isDirty = 1; |
| 843 |
} |
| 844 |
|
| 845 |
/* |
| 846 |
** Remove the cell with index iCell from node pNode. |
| 847 |
*/ |
| 848 |
static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ |
| 849 |
u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
| 850 |
u8 *pSrc = &pDst[pRtree->nBytesPerCell]; |
| 851 |
int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell; |
| 852 |
memmove(pDst, pSrc, nByte); |
| 853 |
writeInt16(&pNode->zData[2], NCELL(pNode)-1); |
| 854 |
pNode->isDirty = 1; |
| 855 |
} |
| 856 |
|
| 857 |
/* |
| 858 |
** Insert the contents of cell pCell into node pNode. If the insert |
| 859 |
** is successful, return SQLITE_OK. |
| 860 |
** |
| 861 |
** If there is not enough free space in pNode, return SQLITE_FULL. |
| 862 |
*/ |
| 863 |
static int nodeInsertCell( |
| 864 |
Rtree *pRtree, /* The overall R-Tree */ |
| 865 |
RtreeNode *pNode, /* Write new cell into this node */ |
| 866 |
RtreeCell *pCell /* The cell to be inserted */ |
| 867 |
){ |
| 868 |
int nCell; /* Current number of cells in pNode */ |
| 869 |
int nMaxCell; /* Maximum number of cells for pNode */ |
| 870 |
|
| 871 |
nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; |
| 872 |
nCell = NCELL(pNode); |
| 873 |
|
| 874 |
assert( nCell<=nMaxCell ); |
| 875 |
if( nCell<nMaxCell ){ |
| 876 |
nodeOverwriteCell(pRtree, pNode, pCell, nCell); |
| 877 |
writeInt16(&pNode->zData[2], nCell+1); |
| 878 |
pNode->isDirty = 1; |
| 879 |
} |
| 880 |
|
| 881 |
return (nCell==nMaxCell); |
| 882 |
} |
| 883 |
|
| 884 |
/* |
| 885 |
** If the node is dirty, write it out to the database. |
| 886 |
*/ |
| 887 |
static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){ |
| 888 |
int rc = SQLITE_OK; |
| 889 |
if( pNode->isDirty ){ |
| 890 |
sqlite3_stmt *p = pRtree->pWriteNode; |
| 891 |
if( pNode->iNode ){ |
| 892 |
sqlite3_bind_int64(p, 1, pNode->iNode); |
| 893 |
}else{ |
| 894 |
sqlite3_bind_null(p, 1); |
| 895 |
} |
| 896 |
sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC); |
| 897 |
sqlite3_step(p); |
| 898 |
pNode->isDirty = 0; |
| 899 |
rc = sqlite3_reset(p); |
| 900 |
sqlite3_bind_null(p, 2); |
| 901 |
if( pNode->iNode==0 && rc==SQLITE_OK ){ |
| 902 |
pNode->iNode = sqlite3_last_insert_rowid(pRtree->db); |
| 903 |
nodeHashInsert(pRtree, pNode); |
| 904 |
} |
| 905 |
} |
| 906 |
return rc; |
| 907 |
} |
| 908 |
|
| 909 |
/* |
| 910 |
** Release a reference to a node. If the node is dirty and the reference |
| 911 |
** count drops to zero, the node data is written to the database. |
| 912 |
*/ |
| 913 |
static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){ |
| 914 |
int rc = SQLITE_OK; |
| 915 |
if( pNode ){ |
| 916 |
assert( pNode->nRef>0 ); |
| 917 |
assert( pRtree->nNodeRef>0 ); |
| 918 |
pNode->nRef--; |
| 919 |
if( pNode->nRef==0 ){ |
| 920 |
pRtree->nNodeRef--; |
| 921 |
if( pNode->iNode==1 ){ |
| 922 |
pRtree->iDepth = -1; |
| 923 |
} |
| 924 |
if( pNode->pParent ){ |
| 925 |
rc = nodeRelease(pRtree, pNode->pParent); |
| 926 |
} |
| 927 |
if( rc==SQLITE_OK ){ |
| 928 |
rc = nodeWrite(pRtree, pNode); |
| 929 |
} |
| 930 |
nodeHashDelete(pRtree, pNode); |
| 931 |
sqlite3_free(pNode); |
| 932 |
} |
| 933 |
} |
| 934 |
return rc; |
| 935 |
} |
| 936 |
|
| 937 |
/* |
| 938 |
** Return the 64-bit integer value associated with cell iCell of |
| 939 |
** node pNode. If pNode is a leaf node, this is a rowid. If it is |
| 940 |
** an internal node, then the 64-bit integer is a child page number. |
| 941 |
*/ |
| 942 |
static i64 nodeGetRowid( |
| 943 |
Rtree *pRtree, /* The overall R-Tree */ |
| 944 |
RtreeNode *pNode, /* The node from which to extract the ID */ |
| 945 |
int iCell /* The cell index from which to extract the ID */ |
| 946 |
){ |
| 947 |
assert( iCell<NCELL(pNode) ); |
| 948 |
return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); |
| 949 |
} |
| 950 |
|
| 951 |
/* |
| 952 |
** Return coordinate iCoord from cell iCell in node pNode. |
| 953 |
*/ |
| 954 |
static void nodeGetCoord( |
| 955 |
Rtree *pRtree, /* The overall R-Tree */ |
| 956 |
RtreeNode *pNode, /* The node from which to extract a coordinate */ |
| 957 |
int iCell, /* The index of the cell within the node */ |
| 958 |
int iCoord, /* Which coordinate to extract */ |
| 959 |
RtreeCoord *pCoord /* OUT: Space to write result to */ |
| 960 |
){ |
| 961 |
assert( iCell<NCELL(pNode) ); |
| 962 |
readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); |
| 963 |
} |
| 964 |
|
| 965 |
/* |
| 966 |
** Deserialize cell iCell of node pNode. Populate the structure pointed |
| 967 |
** to by pCell with the results. |
| 968 |
*/ |
| 969 |
static void nodeGetCell( |
| 970 |
Rtree *pRtree, /* The overall R-Tree */ |
| 971 |
RtreeNode *pNode, /* The node containing the cell to be read */ |
| 972 |
int iCell, /* Index of the cell within the node */ |
| 973 |
RtreeCell *pCell /* OUT: Write the cell contents here */ |
| 974 |
){ |
| 975 |
u8 *pData; |
| 976 |
RtreeCoord *pCoord; |
| 977 |
int ii = 0; |
| 978 |
pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); |
| 979 |
pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); |
| 980 |
pCoord = pCell->aCoord; |
| 981 |
do{ |
| 982 |
readCoord(pData, &pCoord[ii]); |
| 983 |
readCoord(pData+4, &pCoord[ii+1]); |
| 984 |
pData += 8; |
| 985 |
ii += 2; |
| 986 |
}while( ii<pRtree->nDim2 ); |
| 987 |
} |
| 988 |
|
| 989 |
|
| 990 |
/* Forward declaration for the function that does the work of |
| 991 |
** the virtual table module xCreate() and xConnect() methods. |
| 992 |
*/ |
| 993 |
static int rtreeInit( |
| 994 |
sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int |
| 995 |
); |
| 996 |
|
| 997 |
/* |
| 998 |
** Rtree virtual table module xCreate method. |
| 999 |
*/ |
| 1000 |
static int rtreeCreate( |
| 1001 |
sqlite3 *db, |
| 1002 |
void *pAux, |
| 1003 |
int argc, const char *const*argv, |
| 1004 |
sqlite3_vtab **ppVtab, |
| 1005 |
char **pzErr |
| 1006 |
){ |
| 1007 |
return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1); |
| 1008 |
} |
| 1009 |
|
| 1010 |
/* |
| 1011 |
** Rtree virtual table module xConnect method. |
| 1012 |
*/ |
| 1013 |
static int rtreeConnect( |
| 1014 |
sqlite3 *db, |
| 1015 |
void *pAux, |
| 1016 |
int argc, const char *const*argv, |
| 1017 |
sqlite3_vtab **ppVtab, |
| 1018 |
char **pzErr |
| 1019 |
){ |
| 1020 |
return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0); |
| 1021 |
} |
| 1022 |
|
| 1023 |
/* |
| 1024 |
** Increment the r-tree reference count. |
| 1025 |
*/ |
| 1026 |
static void rtreeReference(Rtree *pRtree){ |
| 1027 |
pRtree->nBusy++; |
| 1028 |
} |
| 1029 |
|
| 1030 |
/* |
| 1031 |
** Decrement the r-tree reference count. When the reference count reaches |
| 1032 |
** zero the structure is deleted. |
| 1033 |
*/ |
| 1034 |
static void rtreeRelease(Rtree *pRtree){ |
| 1035 |
pRtree->nBusy--; |
| 1036 |
if( pRtree->nBusy==0 ){ |
| 1037 |
pRtree->inWrTrans = 0; |
| 1038 |
assert( pRtree->nCursor==0 ); |
| 1039 |
nodeBlobReset(pRtree); |
| 1040 |
if( pRtree->nNodeRef ){ |
| 1041 |
int i; |
| 1042 |
assert( pRtree->bCorrupt ); |
| 1043 |
for(i=0; i<HASHSIZE; i++){ |
| 1044 |
while( pRtree->aHash[i] ){ |
| 1045 |
RtreeNode *pNext = pRtree->aHash[i]->pNext; |
| 1046 |
sqlite3_free(pRtree->aHash[i]); |
| 1047 |
pRtree->aHash[i] = pNext; |
| 1048 |
} |
| 1049 |
} |
| 1050 |
} |
| 1051 |
sqlite3_finalize(pRtree->pWriteNode); |
| 1052 |
sqlite3_finalize(pRtree->pDeleteNode); |
| 1053 |
sqlite3_finalize(pRtree->pReadRowid); |
| 1054 |
sqlite3_finalize(pRtree->pWriteRowid); |
| 1055 |
sqlite3_finalize(pRtree->pDeleteRowid); |
| 1056 |
sqlite3_finalize(pRtree->pReadParent); |
| 1057 |
sqlite3_finalize(pRtree->pWriteParent); |
| 1058 |
sqlite3_finalize(pRtree->pDeleteParent); |
| 1059 |
sqlite3_finalize(pRtree->pWriteAux); |
| 1060 |
sqlite3_free(pRtree->zReadAuxSql); |
| 1061 |
sqlite3_free(pRtree); |
| 1062 |
} |
| 1063 |
} |
| 1064 |
|
| 1065 |
/* |
| 1066 |
** Rtree virtual table module xDisconnect method. |
| 1067 |
*/ |
| 1068 |
static int rtreeDisconnect(sqlite3_vtab *pVtab){ |
| 1069 |
rtreeRelease((Rtree *)pVtab); |
| 1070 |
return SQLITE_OK; |
| 1071 |
} |
| 1072 |
|
| 1073 |
/* |
| 1074 |
** Rtree virtual table module xDestroy method. |
| 1075 |
*/ |
| 1076 |
static int rtreeDestroy(sqlite3_vtab *pVtab){ |
| 1077 |
Rtree *pRtree = (Rtree *)pVtab; |
| 1078 |
int rc; |
| 1079 |
char *zCreate = sqlite3_mprintf( |
| 1080 |
"DROP TABLE '%q'.'%q_node';" |
| 1081 |
"DROP TABLE '%q'.'%q_rowid';" |
| 1082 |
"DROP TABLE '%q'.'%q_parent';", |
| 1083 |
pRtree->zDb, pRtree->zName, |
| 1084 |
pRtree->zDb, pRtree->zName, |
| 1085 |
pRtree->zDb, pRtree->zName |
| 1086 |
); |
| 1087 |
if( !zCreate ){ |
| 1088 |
rc = SQLITE_NOMEM; |
| 1089 |
}else{ |
| 1090 |
nodeBlobReset(pRtree); |
| 1091 |
rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); |
| 1092 |
sqlite3_free(zCreate); |
| 1093 |
} |
| 1094 |
if( rc==SQLITE_OK ){ |
| 1095 |
rtreeRelease(pRtree); |
| 1096 |
} |
| 1097 |
|
| 1098 |
return rc; |
| 1099 |
} |
| 1100 |
|
| 1101 |
/* |
| 1102 |
** Rtree virtual table module xOpen method. |
| 1103 |
*/ |
| 1104 |
static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
| 1105 |
int rc = SQLITE_NOMEM; |
| 1106 |
Rtree *pRtree = (Rtree *)pVTab; |
| 1107 |
RtreeCursor *pCsr; |
| 1108 |
|
| 1109 |
pCsr = (RtreeCursor *)sqlite3_malloc64(sizeof(RtreeCursor)); |
| 1110 |
if( pCsr ){ |
| 1111 |
memset(pCsr, 0, sizeof(RtreeCursor)); |
| 1112 |
pCsr->base.pVtab = pVTab; |
| 1113 |
rc = SQLITE_OK; |
| 1114 |
pRtree->nCursor++; |
| 1115 |
} |
| 1116 |
*ppCursor = (sqlite3_vtab_cursor *)pCsr; |
| 1117 |
|
| 1118 |
return rc; |
| 1119 |
} |
| 1120 |
|
| 1121 |
|
| 1122 |
/* |
| 1123 |
** Reset a cursor back to its initial state. |
| 1124 |
*/ |
| 1125 |
static void resetCursor(RtreeCursor *pCsr){ |
| 1126 |
Rtree *pRtree = (Rtree *)(pCsr->base.pVtab); |
| 1127 |
int ii; |
| 1128 |
sqlite3_stmt *pStmt; |
| 1129 |
if( pCsr->aConstraint ){ |
| 1130 |
int i; /* Used to iterate through constraint array */ |
| 1131 |
for(i=0; i<pCsr->nConstraint; i++){ |
| 1132 |
sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo; |
| 1133 |
if( pInfo ){ |
| 1134 |
if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser); |
| 1135 |
sqlite3_free(pInfo); |
| 1136 |
} |
| 1137 |
} |
| 1138 |
sqlite3_free(pCsr->aConstraint); |
| 1139 |
pCsr->aConstraint = 0; |
| 1140 |
} |
| 1141 |
for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); |
| 1142 |
sqlite3_free(pCsr->aPoint); |
| 1143 |
pStmt = pCsr->pReadAux; |
| 1144 |
memset(pCsr, 0, sizeof(RtreeCursor)); |
| 1145 |
pCsr->base.pVtab = (sqlite3_vtab*)pRtree; |
| 1146 |
pCsr->pReadAux = pStmt; |
| 1147 |
|
| 1148 |
/* The following will only fail if the previous sqlite3_step() call failed, |
| 1149 |
** in which case the error has already been caught. This statement never |
| 1150 |
** encounters an error within an sqlite3_column_xxx() function, as it |
| 1151 |
** calls sqlite3_column_value(), which does not use malloc(). So it is safe |
| 1152 |
** to ignore the error code here. */ |
| 1153 |
sqlite3_reset(pStmt); |
| 1154 |
} |
| 1155 |
|
| 1156 |
/* |
| 1157 |
** Rtree virtual table module xClose method. |
| 1158 |
*/ |
| 1159 |
static int rtreeClose(sqlite3_vtab_cursor *cur){ |
| 1160 |
Rtree *pRtree = (Rtree *)(cur->pVtab); |
| 1161 |
RtreeCursor *pCsr = (RtreeCursor *)cur; |
| 1162 |
assert( pRtree->nCursor>0 ); |
| 1163 |
resetCursor(pCsr); |
| 1164 |
sqlite3_finalize(pCsr->pReadAux); |
| 1165 |
sqlite3_free(pCsr); |
| 1166 |
pRtree->nCursor--; |
| 1167 |
if( pRtree->nCursor==0 && pRtree->inWrTrans==0 ){ |
| 1168 |
nodeBlobReset(pRtree); |
| 1169 |
} |
| 1170 |
return SQLITE_OK; |
| 1171 |
} |
| 1172 |
|
| 1173 |
/* |
| 1174 |
** Rtree virtual table module xEof method. |
| 1175 |
** |
| 1176 |
** Return non-zero if the cursor does not currently point to a valid |
| 1177 |
** record (i.e if the scan has finished), or zero otherwise. |
| 1178 |
*/ |
| 1179 |
static int rtreeEof(sqlite3_vtab_cursor *cur){ |
| 1180 |
RtreeCursor *pCsr = (RtreeCursor *)cur; |
| 1181 |
return pCsr->atEOF; |
| 1182 |
} |
| 1183 |
|
| 1184 |
/* |
| 1185 |
** Convert raw bits from the on-disk RTree record into a coordinate value. |
| 1186 |
** The on-disk format is big-endian and needs to be converted for little- |
| 1187 |
** endian platforms. The on-disk record stores integer coordinates if |
| 1188 |
** eInt is true and it stores 32-bit floating point records if eInt is |
| 1189 |
** false. a[] is the four bytes of the on-disk record to be decoded. |
| 1190 |
** Store the results in "r". |
| 1191 |
** |
| 1192 |
** There are five versions of this macro. The last one is generic. The |
| 1193 |
** other four are various architectures-specific optimizations. |
| 1194 |
*/ |
| 1195 |
#if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 1196 |
#define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1197 |
RtreeCoord c; /* Coordinate decoded */ \ |
| 1198 |
c.u = _byteswap_ulong(*(u32*)a); \ |
| 1199 |
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1200 |
} |
| 1201 |
#elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000 |
| 1202 |
#define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1203 |
RtreeCoord c; /* Coordinate decoded */ \ |
| 1204 |
c.u = __builtin_bswap32(*(u32*)a); \ |
| 1205 |
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1206 |
} |
| 1207 |
#elif SQLITE_BYTEORDER==1234 |
| 1208 |
#define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1209 |
RtreeCoord c; /* Coordinate decoded */ \ |
| 1210 |
memcpy(&c.u,a,4); \ |
| 1211 |
c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \ |
| 1212 |
((c.u&0xff)<<24)|((c.u&0xff00)<<8); \ |
| 1213 |
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1214 |
} |
| 1215 |
#elif SQLITE_BYTEORDER==4321 |
| 1216 |
#define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1217 |
RtreeCoord c; /* Coordinate decoded */ \ |
| 1218 |
memcpy(&c.u,a,4); \ |
| 1219 |
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1220 |
} |
| 1221 |
#else |
| 1222 |
#define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1223 |
RtreeCoord c; /* Coordinate decoded */ \ |
| 1224 |
c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \ |
| 1225 |
+((u32)a[2]<<8) + a[3]; \ |
| 1226 |
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1227 |
} |
| 1228 |
#endif |
| 1229 |
|
| 1230 |
/* |
| 1231 |
** Check the RTree node or entry given by pCellData and p against the MATCH |
| 1232 |
** constraint pConstraint. |
| 1233 |
*/ |
| 1234 |
static int rtreeCallbackConstraint( |
| 1235 |
RtreeConstraint *pConstraint, /* The constraint to test */ |
| 1236 |
int eInt, /* True if RTree holding integer coordinates */ |
| 1237 |
u8 *pCellData, /* Raw cell content */ |
| 1238 |
RtreeSearchPoint *pSearch, /* Container of this cell */ |
| 1239 |
sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */ |
| 1240 |
int *peWithin /* OUT: visibility of the cell */ |
| 1241 |
){ |
| 1242 |
sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */ |
| 1243 |
int nCoord = pInfo->nCoord; /* No. of coordinates */ |
| 1244 |
int rc; /* Callback return code */ |
| 1245 |
RtreeCoord c; /* Translator union */ |
| 1246 |
sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */ |
| 1247 |
|
| 1248 |
assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY ); |
| 1249 |
assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 ); |
| 1250 |
|
| 1251 |
if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){ |
| 1252 |
pInfo->iRowid = readInt64(pCellData); |
| 1253 |
} |
| 1254 |
pCellData += 8; |
| 1255 |
#ifndef SQLITE_RTREE_INT_ONLY |
| 1256 |
if( eInt==0 ){ |
| 1257 |
switch( nCoord ){ |
| 1258 |
case 10: readCoord(pCellData+36, &c); aCoord[9] = c.f; |
| 1259 |
readCoord(pCellData+32, &c); aCoord[8] = c.f; |
| 1260 |
case 8: readCoord(pCellData+28, &c); aCoord[7] = c.f; |
| 1261 |
readCoord(pCellData+24, &c); aCoord[6] = c.f; |
| 1262 |
case 6: readCoord(pCellData+20, &c); aCoord[5] = c.f; |
| 1263 |
readCoord(pCellData+16, &c); aCoord[4] = c.f; |
| 1264 |
case 4: readCoord(pCellData+12, &c); aCoord[3] = c.f; |
| 1265 |
readCoord(pCellData+8, &c); aCoord[2] = c.f; |
| 1266 |
default: readCoord(pCellData+4, &c); aCoord[1] = c.f; |
| 1267 |
readCoord(pCellData, &c); aCoord[0] = c.f; |
| 1268 |
} |
| 1269 |
}else |
| 1270 |
#endif |
| 1271 |
{ |
| 1272 |
switch( nCoord ){ |
| 1273 |
case 10: readCoord(pCellData+36, &c); aCoord[9] = c.i; |
| 1274 |
readCoord(pCellData+32, &c); aCoord[8] = c.i; |
| 1275 |
case 8: readCoord(pCellData+28, &c); aCoord[7] = c.i; |
| 1276 |
readCoord(pCellData+24, &c); aCoord[6] = c.i; |
| 1277 |
case 6: readCoord(pCellData+20, &c); aCoord[5] = c.i; |
| 1278 |
readCoord(pCellData+16, &c); aCoord[4] = c.i; |
| 1279 |
case 4: readCoord(pCellData+12, &c); aCoord[3] = c.i; |
| 1280 |
readCoord(pCellData+8, &c); aCoord[2] = c.i; |
| 1281 |
default: readCoord(pCellData+4, &c); aCoord[1] = c.i; |
| 1282 |
readCoord(pCellData, &c); aCoord[0] = c.i; |
| 1283 |
} |
| 1284 |
} |
| 1285 |
if( pConstraint->op==RTREE_MATCH ){ |
| 1286 |
int eWithin = 0; |
| 1287 |
rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo, |
| 1288 |
nCoord, aCoord, &eWithin); |
| 1289 |
if( eWithin==0 ) *peWithin = NOT_WITHIN; |
| 1290 |
*prScore = RTREE_ZERO; |
| 1291 |
}else{ |
| 1292 |
pInfo->aCoord = aCoord; |
| 1293 |
pInfo->iLevel = pSearch->iLevel - 1; |
| 1294 |
pInfo->rScore = pInfo->rParentScore = pSearch->rScore; |
| 1295 |
pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin; |
| 1296 |
rc = pConstraint->u.xQueryFunc(pInfo); |
| 1297 |
if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin; |
| 1298 |
if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){ |
| 1299 |
*prScore = pInfo->rScore; |
| 1300 |
} |
| 1301 |
} |
| 1302 |
return rc; |
| 1303 |
} |
| 1304 |
|
| 1305 |
/* |
| 1306 |
** Check the internal RTree node given by pCellData against constraint p. |
| 1307 |
** If this constraint cannot be satisfied by any child within the node, |
| 1308 |
** set *peWithin to NOT_WITHIN. |
| 1309 |
*/ |
| 1310 |
static void rtreeNonleafConstraint( |
| 1311 |
RtreeConstraint *p, /* The constraint to test */ |
| 1312 |
int eInt, /* True if RTree holds integer coordinates */ |
| 1313 |
u8 *pCellData, /* Raw cell content as appears on disk */ |
| 1314 |
int *peWithin /* Adjust downward, as appropriate */ |
| 1315 |
){ |
| 1316 |
sqlite3_rtree_dbl val; /* Coordinate value convert to a double */ |
| 1317 |
|
| 1318 |
/* p->iCoord might point to either a lower or upper bound coordinate |
| 1319 |
** in a coordinate pair. But make pCellData point to the lower bound. |
| 1320 |
*/ |
| 1321 |
pCellData += 8 + 4*(p->iCoord&0xfe); |
| 1322 |
|
| 1323 |
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
| 1324 |
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE |
| 1325 |
|| p->op==RTREE_FALSE ); |
| 1326 |
assert( FOUR_BYTE_ALIGNED(pCellData) ); |
| 1327 |
switch( p->op ){ |
| 1328 |
case RTREE_TRUE: return; /* Always satisfied */ |
| 1329 |
case RTREE_FALSE: break; /* Never satisfied */ |
| 1330 |
case RTREE_EQ: |
| 1331 |
RTREE_DECODE_COORD(eInt, pCellData, val); |
| 1332 |
/* val now holds the lower bound of the coordinate pair */ |
| 1333 |
if( p->u.rValue>=val ){ |
| 1334 |
pCellData += 4; |
| 1335 |
RTREE_DECODE_COORD(eInt, pCellData, val); |
| 1336 |
/* val now holds the upper bound of the coordinate pair */ |
| 1337 |
if( p->u.rValue<=val ) return; |
| 1338 |
} |
| 1339 |
break; |
| 1340 |
case RTREE_LE: |
| 1341 |
case RTREE_LT: |
| 1342 |
RTREE_DECODE_COORD(eInt, pCellData, val); |
| 1343 |
/* val now holds the lower bound of the coordinate pair */ |
| 1344 |
if( p->u.rValue>=val ) return; |
| 1345 |
break; |
| 1346 |
|
| 1347 |
default: |
| 1348 |
pCellData += 4; |
| 1349 |
RTREE_DECODE_COORD(eInt, pCellData, val); |
| 1350 |
/* val now holds the upper bound of the coordinate pair */ |
| 1351 |
if( p->u.rValue<=val ) return; |
| 1352 |
break; |
| 1353 |
} |
| 1354 |
*peWithin = NOT_WITHIN; |
| 1355 |
} |
| 1356 |
|
| 1357 |
/* |
| 1358 |
** Check the leaf RTree cell given by pCellData against constraint p. |
| 1359 |
** If this constraint is not satisfied, set *peWithin to NOT_WITHIN. |
| 1360 |
** If the constraint is satisfied, leave *peWithin unchanged. |
| 1361 |
** |
| 1362 |
** The constraint is of the form: xN op $val |
| 1363 |
** |
| 1364 |
** The op is given by p->op. The xN is p->iCoord-th coordinate in |
| 1365 |
** pCellData. $val is given by p->u.rValue. |
| 1366 |
*/ |
| 1367 |
static void rtreeLeafConstraint( |
| 1368 |
RtreeConstraint *p, /* The constraint to test */ |
| 1369 |
int eInt, /* True if RTree holds integer coordinates */ |
| 1370 |
u8 *pCellData, /* Raw cell content as appears on disk */ |
| 1371 |
int *peWithin /* Adjust downward, as appropriate */ |
| 1372 |
){ |
| 1373 |
RtreeDValue xN; /* Coordinate value converted to a double */ |
| 1374 |
|
| 1375 |
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
| 1376 |
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_TRUE |
| 1377 |
|| p->op==RTREE_FALSE ); |
| 1378 |
pCellData += 8 + p->iCoord*4; |
| 1379 |
assert( FOUR_BYTE_ALIGNED(pCellData) ); |
| 1380 |
RTREE_DECODE_COORD(eInt, pCellData, xN); |
| 1381 |
switch( p->op ){ |
| 1382 |
case RTREE_TRUE: return; /* Always satisfied */ |
| 1383 |
case RTREE_FALSE: break; /* Never satisfied */ |
| 1384 |
case RTREE_LE: if( xN <= p->u.rValue ) return; break; |
| 1385 |
case RTREE_LT: if( xN < p->u.rValue ) return; break; |
| 1386 |
case RTREE_GE: if( xN >= p->u.rValue ) return; break; |
| 1387 |
case RTREE_GT: if( xN > p->u.rValue ) return; break; |
| 1388 |
default: if( xN == p->u.rValue ) return; break; |
| 1389 |
} |
| 1390 |
*peWithin = NOT_WITHIN; |
| 1391 |
} |
| 1392 |
|
| 1393 |
/* |
| 1394 |
** One of the cells in node pNode is guaranteed to have a 64-bit |
| 1395 |
** integer value equal to iRowid. Return the index of this cell. |
| 1396 |
*/ |
| 1397 |
static int nodeRowidIndex( |
| 1398 |
Rtree *pRtree, |
| 1399 |
RtreeNode *pNode, |
| 1400 |
i64 iRowid, |
| 1401 |
int *piIndex |
| 1402 |
){ |
| 1403 |
int ii; |
| 1404 |
int nCell = NCELL(pNode); |
| 1405 |
assert( nCell<65536 && nCell>=0 ); |
| 1406 |
for(ii=0; ii<nCell; ii++){ |
| 1407 |
if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ |
| 1408 |
*piIndex = ii; |
| 1409 |
return SQLITE_OK; |
| 1410 |
} |
| 1411 |
} |
| 1412 |
RTREE_IS_CORRUPT(pRtree); |
| 1413 |
return SQLITE_CORRUPT_VTAB; |
| 1414 |
} |
| 1415 |
|
| 1416 |
/* |
| 1417 |
** Return the index of the cell containing a pointer to node pNode |
| 1418 |
** in its parent. If pNode is the root node, return -1. |
| 1419 |
*/ |
| 1420 |
static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){ |
| 1421 |
RtreeNode *pParent = pNode->pParent; |
| 1422 |
if( ALWAYS(pParent) ){ |
| 1423 |
return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex); |
| 1424 |
}else{ |
| 1425 |
*piIndex = -1; |
| 1426 |
return SQLITE_OK; |
| 1427 |
} |
| 1428 |
} |
| 1429 |
|
| 1430 |
/* |
| 1431 |
** Compare two search points. Return negative, zero, or positive if the first |
| 1432 |
** is less than, equal to, or greater than the second. |
| 1433 |
** |
| 1434 |
** The rScore is the primary key. Smaller rScore values come first. |
| 1435 |
** If the rScore is a tie, then use iLevel as the tie breaker with smaller |
| 1436 |
** iLevel values coming first. In this way, if rScore is the same for all |
| 1437 |
** SearchPoints, then iLevel becomes the deciding factor and the result |
| 1438 |
** is a depth-first search, which is the desired default behavior. |
| 1439 |
*/ |
| 1440 |
static int rtreeSearchPointCompare( |
| 1441 |
const RtreeSearchPoint *pA, |
| 1442 |
const RtreeSearchPoint *pB |
| 1443 |
){ |
| 1444 |
if( pA->rScore<pB->rScore ) return -1; |
| 1445 |
if( pA->rScore>pB->rScore ) return +1; |
| 1446 |
if( pA->iLevel<pB->iLevel ) return -1; |
| 1447 |
if( pA->iLevel>pB->iLevel ) return +1; |
| 1448 |
return 0; |
| 1449 |
} |
| 1450 |
|
| 1451 |
/* |
| 1452 |
** Interchange two search points in a cursor. |
| 1453 |
*/ |
| 1454 |
static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){ |
| 1455 |
RtreeSearchPoint t = p->aPoint[i]; |
| 1456 |
assert( i<j ); |
| 1457 |
p->aPoint[i] = p->aPoint[j]; |
| 1458 |
p->aPoint[j] = t; |
| 1459 |
i++; j++; |
| 1460 |
if( i<RTREE_CACHE_SZ ){ |
| 1461 |
if( j>=RTREE_CACHE_SZ ){ |
| 1462 |
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); |
| 1463 |
p->aNode[i] = 0; |
| 1464 |
}else{ |
| 1465 |
RtreeNode *pTemp = p->aNode[i]; |
| 1466 |
p->aNode[i] = p->aNode[j]; |
| 1467 |
p->aNode[j] = pTemp; |
| 1468 |
} |
| 1469 |
} |
| 1470 |
} |
| 1471 |
|
| 1472 |
/* |
| 1473 |
** Return the search point with the lowest current score. |
| 1474 |
*/ |
| 1475 |
static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){ |
| 1476 |
return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0; |
| 1477 |
} |
| 1478 |
|
| 1479 |
/* |
| 1480 |
** Get the RtreeNode for the search point with the lowest score. |
| 1481 |
*/ |
| 1482 |
static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){ |
| 1483 |
sqlite3_int64 id; |
| 1484 |
int ii = 1 - pCur->bPoint; |
| 1485 |
assert( ii==0 || ii==1 ); |
| 1486 |
assert( pCur->bPoint || pCur->nPoint ); |
| 1487 |
if( pCur->aNode[ii]==0 ){ |
| 1488 |
assert( pRC!=0 ); |
| 1489 |
id = ii ? pCur->aPoint[0].id : pCur->sPoint.id; |
| 1490 |
*pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]); |
| 1491 |
} |
| 1492 |
return pCur->aNode[ii]; |
| 1493 |
} |
| 1494 |
|
| 1495 |
/* |
| 1496 |
** Push a new element onto the priority queue |
| 1497 |
*/ |
| 1498 |
static RtreeSearchPoint *rtreeEnqueue( |
| 1499 |
RtreeCursor *pCur, /* The cursor */ |
| 1500 |
RtreeDValue rScore, /* Score for the new search point */ |
| 1501 |
u8 iLevel /* Level for the new search point */ |
| 1502 |
){ |
| 1503 |
int i, j; |
| 1504 |
RtreeSearchPoint *pNew; |
| 1505 |
if( pCur->nPoint>=pCur->nPointAlloc ){ |
| 1506 |
int nNew = pCur->nPointAlloc*2 + 8; |
| 1507 |
pNew = sqlite3_realloc64(pCur->aPoint, nNew*sizeof(pCur->aPoint[0])); |
| 1508 |
if( pNew==0 ) return 0; |
| 1509 |
pCur->aPoint = pNew; |
| 1510 |
pCur->nPointAlloc = nNew; |
| 1511 |
} |
| 1512 |
i = pCur->nPoint++; |
| 1513 |
pNew = pCur->aPoint + i; |
| 1514 |
pNew->rScore = rScore; |
| 1515 |
pNew->iLevel = iLevel; |
| 1516 |
assert( iLevel<=RTREE_MAX_DEPTH ); |
| 1517 |
while( i>0 ){ |
| 1518 |
RtreeSearchPoint *pParent; |
| 1519 |
j = (i-1)/2; |
| 1520 |
pParent = pCur->aPoint + j; |
| 1521 |
if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break; |
| 1522 |
rtreeSearchPointSwap(pCur, j, i); |
| 1523 |
i = j; |
| 1524 |
pNew = pParent; |
| 1525 |
} |
| 1526 |
return pNew; |
| 1527 |
} |
| 1528 |
|
| 1529 |
/* |
| 1530 |
** Allocate a new RtreeSearchPoint and return a pointer to it. Return |
| 1531 |
** NULL if malloc fails. |
| 1532 |
*/ |
| 1533 |
static RtreeSearchPoint *rtreeSearchPointNew( |
| 1534 |
RtreeCursor *pCur, /* The cursor */ |
| 1535 |
RtreeDValue rScore, /* Score for the new search point */ |
| 1536 |
u8 iLevel /* Level for the new search point */ |
| 1537 |
){ |
| 1538 |
RtreeSearchPoint *pNew, *pFirst; |
| 1539 |
pFirst = rtreeSearchPointFirst(pCur); |
| 1540 |
pCur->anQueue[iLevel]++; |
| 1541 |
if( pFirst==0 |
| 1542 |
|| pFirst->rScore>rScore |
| 1543 |
|| (pFirst->rScore==rScore && pFirst->iLevel>iLevel) |
| 1544 |
){ |
| 1545 |
if( pCur->bPoint ){ |
| 1546 |
int ii; |
| 1547 |
pNew = rtreeEnqueue(pCur, rScore, iLevel); |
| 1548 |
if( pNew==0 ) return 0; |
| 1549 |
ii = (int)(pNew - pCur->aPoint) + 1; |
| 1550 |
assert( ii==1 ); |
| 1551 |
if( ALWAYS(ii<RTREE_CACHE_SZ) ){ |
| 1552 |
assert( pCur->aNode[ii]==0 ); |
| 1553 |
pCur->aNode[ii] = pCur->aNode[0]; |
| 1554 |
}else{ |
| 1555 |
nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]); |
| 1556 |
} |
| 1557 |
pCur->aNode[0] = 0; |
| 1558 |
*pNew = pCur->sPoint; |
| 1559 |
} |
| 1560 |
pCur->sPoint.rScore = rScore; |
| 1561 |
pCur->sPoint.iLevel = iLevel; |
| 1562 |
pCur->bPoint = 1; |
| 1563 |
return &pCur->sPoint; |
| 1564 |
}else{ |
| 1565 |
return rtreeEnqueue(pCur, rScore, iLevel); |
| 1566 |
} |
| 1567 |
} |
| 1568 |
|
| 1569 |
#if 0 |
| 1570 |
/* Tracing routines for the RtreeSearchPoint queue */ |
| 1571 |
static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){ |
| 1572 |
if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); } |
| 1573 |
printf(" %d.%05lld.%02d %g %d", |
| 1574 |
p->iLevel, p->id, p->iCell, p->rScore, p->eWithin |
| 1575 |
); |
| 1576 |
idx++; |
| 1577 |
if( idx<RTREE_CACHE_SZ ){ |
| 1578 |
printf(" %p\n", pCur->aNode[idx]); |
| 1579 |
}else{ |
| 1580 |
printf("\n"); |
| 1581 |
} |
| 1582 |
} |
| 1583 |
static void traceQueue(RtreeCursor *pCur, const char *zPrefix){ |
| 1584 |
int ii; |
| 1585 |
printf("=== %9s ", zPrefix); |
| 1586 |
if( pCur->bPoint ){ |
| 1587 |
tracePoint(&pCur->sPoint, -1, pCur); |
| 1588 |
} |
| 1589 |
for(ii=0; ii<pCur->nPoint; ii++){ |
| 1590 |
if( ii>0 || pCur->bPoint ) printf(" "); |
| 1591 |
tracePoint(&pCur->aPoint[ii], ii, pCur); |
| 1592 |
} |
| 1593 |
} |
| 1594 |
# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B) |
| 1595 |
#else |
| 1596 |
# define RTREE_QUEUE_TRACE(A,B) /* no-op */ |
| 1597 |
#endif |
| 1598 |
|
| 1599 |
/* Remove the search point with the lowest current score. |
| 1600 |
*/ |
| 1601 |
static void rtreeSearchPointPop(RtreeCursor *p){ |
| 1602 |
int i, j, k, n; |
| 1603 |
i = 1 - p->bPoint; |
| 1604 |
assert( i==0 || i==1 ); |
| 1605 |
if( p->aNode[i] ){ |
| 1606 |
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); |
| 1607 |
p->aNode[i] = 0; |
| 1608 |
} |
| 1609 |
if( p->bPoint ){ |
| 1610 |
p->anQueue[p->sPoint.iLevel]--; |
| 1611 |
p->bPoint = 0; |
| 1612 |
}else if( ALWAYS(p->nPoint) ){ |
| 1613 |
p->anQueue[p->aPoint[0].iLevel]--; |
| 1614 |
n = --p->nPoint; |
| 1615 |
p->aPoint[0] = p->aPoint[n]; |
| 1616 |
if( n<RTREE_CACHE_SZ-1 ){ |
| 1617 |
p->aNode[1] = p->aNode[n+1]; |
| 1618 |
p->aNode[n+1] = 0; |
| 1619 |
} |
| 1620 |
i = 0; |
| 1621 |
while( (j = i*2+1)<n ){ |
| 1622 |
k = j+1; |
| 1623 |
if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){ |
| 1624 |
if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){ |
| 1625 |
rtreeSearchPointSwap(p, i, k); |
| 1626 |
i = k; |
| 1627 |
}else{ |
| 1628 |
break; |
| 1629 |
} |
| 1630 |
}else{ |
| 1631 |
if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){ |
| 1632 |
rtreeSearchPointSwap(p, i, j); |
| 1633 |
i = j; |
| 1634 |
}else{ |
| 1635 |
break; |
| 1636 |
} |
| 1637 |
} |
| 1638 |
} |
| 1639 |
} |
| 1640 |
} |
| 1641 |
|
| 1642 |
|
| 1643 |
/* |
| 1644 |
** Continue the search on cursor pCur until the front of the queue |
| 1645 |
** contains an entry suitable for returning as a result-set row, |
| 1646 |
** or until the RtreeSearchPoint queue is empty, indicating that the |
| 1647 |
** query has completed. |
| 1648 |
*/ |
| 1649 |
static int rtreeStepToLeaf(RtreeCursor *pCur){ |
| 1650 |
RtreeSearchPoint *p; |
| 1651 |
Rtree *pRtree = RTREE_OF_CURSOR(pCur); |
| 1652 |
RtreeNode *pNode; |
| 1653 |
int eWithin; |
| 1654 |
int rc = SQLITE_OK; |
| 1655 |
int nCell; |
| 1656 |
int nConstraint = pCur->nConstraint; |
| 1657 |
int ii; |
| 1658 |
int eInt; |
| 1659 |
RtreeSearchPoint x; |
| 1660 |
|
| 1661 |
eInt = pRtree->eCoordType==RTREE_COORD_INT32; |
| 1662 |
while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){ |
| 1663 |
u8 *pCellData; |
| 1664 |
pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc); |
| 1665 |
if( rc ) return rc; |
| 1666 |
nCell = NCELL(pNode); |
| 1667 |
if( nCell>RTREE_MAXCELLS ){ |
| 1668 |
RTREE_IS_CORRUPT(pRtree); |
| 1669 |
return SQLITE_CORRUPT_VTAB; |
| 1670 |
} |
| 1671 |
pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell); |
| 1672 |
while( p->iCell<nCell ){ |
| 1673 |
sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1; |
| 1674 |
eWithin = FULLY_WITHIN; |
| 1675 |
for(ii=0; ii<nConstraint; ii++){ |
| 1676 |
RtreeConstraint *pConstraint = pCur->aConstraint + ii; |
| 1677 |
if( pConstraint->op>=RTREE_MATCH ){ |
| 1678 |
rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p, |
| 1679 |
&rScore, &eWithin); |
| 1680 |
if( rc ) return rc; |
| 1681 |
}else if( p->iLevel==1 ){ |
| 1682 |
rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin); |
| 1683 |
}else{ |
| 1684 |
rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin); |
| 1685 |
} |
| 1686 |
if( eWithin==NOT_WITHIN ){ |
| 1687 |
p->iCell++; |
| 1688 |
pCellData += pRtree->nBytesPerCell; |
| 1689 |
break; |
| 1690 |
} |
| 1691 |
} |
| 1692 |
if( eWithin==NOT_WITHIN ) continue; |
| 1693 |
p->iCell++; |
| 1694 |
x.iLevel = p->iLevel - 1; |
| 1695 |
if( x.iLevel ){ |
| 1696 |
x.id = readInt64(pCellData); |
| 1697 |
for(ii=0; ii<pCur->nPoint; ii++){ |
| 1698 |
if( pCur->aPoint[ii].id==x.id ){ |
| 1699 |
RTREE_IS_CORRUPT(pRtree); |
| 1700 |
return SQLITE_CORRUPT_VTAB; |
| 1701 |
} |
| 1702 |
} |
| 1703 |
x.iCell = 0; |
| 1704 |
}else{ |
| 1705 |
x.id = p->id; |
| 1706 |
x.iCell = p->iCell - 1; |
| 1707 |
} |
| 1708 |
if( p->iCell>=nCell ){ |
| 1709 |
RTREE_QUEUE_TRACE(pCur, "POP-S:"); |
| 1710 |
rtreeSearchPointPop(pCur); |
| 1711 |
} |
| 1712 |
if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO; |
| 1713 |
p = rtreeSearchPointNew(pCur, rScore, x.iLevel); |
| 1714 |
if( p==0 ) return SQLITE_NOMEM; |
| 1715 |
p->eWithin = (u8)eWithin; |
| 1716 |
p->id = x.id; |
| 1717 |
p->iCell = x.iCell; |
| 1718 |
RTREE_QUEUE_TRACE(pCur, "PUSH-S:"); |
| 1719 |
break; |
| 1720 |
} |
| 1721 |
if( p->iCell>=nCell ){ |
| 1722 |
RTREE_QUEUE_TRACE(pCur, "POP-Se:"); |
| 1723 |
rtreeSearchPointPop(pCur); |
| 1724 |
} |
| 1725 |
} |
| 1726 |
pCur->atEOF = p==0; |
| 1727 |
return SQLITE_OK; |
| 1728 |
} |
| 1729 |
|
| 1730 |
/* |
| 1731 |
** Rtree virtual table module xNext method. |
| 1732 |
*/ |
| 1733 |
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){ |
| 1734 |
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| 1735 |
int rc = SQLITE_OK; |
| 1736 |
|
| 1737 |
/* Move to the next entry that matches the configured constraints. */ |
| 1738 |
RTREE_QUEUE_TRACE(pCsr, "POP-Nx:"); |
| 1739 |
if( pCsr->bAuxValid ){ |
| 1740 |
pCsr->bAuxValid = 0; |
| 1741 |
sqlite3_reset(pCsr->pReadAux); |
| 1742 |
} |
| 1743 |
rtreeSearchPointPop(pCsr); |
| 1744 |
rc = rtreeStepToLeaf(pCsr); |
| 1745 |
return rc; |
| 1746 |
} |
| 1747 |
|
| 1748 |
/* |
| 1749 |
** Rtree virtual table module xRowid method. |
| 1750 |
*/ |
| 1751 |
static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ |
| 1752 |
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| 1753 |
RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); |
| 1754 |
int rc = SQLITE_OK; |
| 1755 |
RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); |
| 1756 |
if( rc==SQLITE_OK && ALWAYS(p) ){ |
| 1757 |
if( p->iCell>=NCELL(pNode) ){ |
| 1758 |
rc = SQLITE_ABORT; |
| 1759 |
}else{ |
| 1760 |
*pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell); |
| 1761 |
} |
| 1762 |
} |
| 1763 |
return rc; |
| 1764 |
} |
| 1765 |
|
| 1766 |
/* |
| 1767 |
** Rtree virtual table module xColumn method. |
| 1768 |
*/ |
| 1769 |
static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ |
| 1770 |
Rtree *pRtree = (Rtree *)cur->pVtab; |
| 1771 |
RtreeCursor *pCsr = (RtreeCursor *)cur; |
| 1772 |
RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); |
| 1773 |
RtreeCoord c; |
| 1774 |
int rc = SQLITE_OK; |
| 1775 |
RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); |
| 1776 |
|
| 1777 |
if( rc ) return rc; |
| 1778 |
if( NEVER(p==0) ) return SQLITE_OK; |
| 1779 |
if( p->iCell>=NCELL(pNode) ) return SQLITE_ABORT; |
| 1780 |
if( i==0 ){ |
| 1781 |
sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); |
| 1782 |
}else if( i<=pRtree->nDim2 ){ |
| 1783 |
nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); |
| 1784 |
#ifndef SQLITE_RTREE_INT_ONLY |
| 1785 |
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| 1786 |
sqlite3_result_double(ctx, c.f); |
| 1787 |
}else |
| 1788 |
#endif |
| 1789 |
{ |
| 1790 |
assert( pRtree->eCoordType==RTREE_COORD_INT32 ); |
| 1791 |
sqlite3_result_int(ctx, c.i); |
| 1792 |
} |
| 1793 |
}else{ |
| 1794 |
if( !pCsr->bAuxValid ){ |
| 1795 |
if( pCsr->pReadAux==0 ){ |
| 1796 |
rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0, |
| 1797 |
&pCsr->pReadAux, 0); |
| 1798 |
if( rc ) return rc; |
| 1799 |
} |
| 1800 |
sqlite3_bind_int64(pCsr->pReadAux, 1, |
| 1801 |
nodeGetRowid(pRtree, pNode, p->iCell)); |
| 1802 |
rc = sqlite3_step(pCsr->pReadAux); |
| 1803 |
if( rc==SQLITE_ROW ){ |
| 1804 |
pCsr->bAuxValid = 1; |
| 1805 |
}else{ |
| 1806 |
sqlite3_reset(pCsr->pReadAux); |
| 1807 |
if( rc==SQLITE_DONE ) rc = SQLITE_OK; |
| 1808 |
return rc; |
| 1809 |
} |
| 1810 |
} |
| 1811 |
sqlite3_result_value(ctx, |
| 1812 |
sqlite3_column_value(pCsr->pReadAux, i - pRtree->nDim2 + 1)); |
| 1813 |
} |
| 1814 |
return SQLITE_OK; |
| 1815 |
} |
| 1816 |
|
| 1817 |
/* |
| 1818 |
** Use nodeAcquire() to obtain the leaf node containing the record with |
| 1819 |
** rowid iRowid. If successful, set *ppLeaf to point to the node and |
| 1820 |
** return SQLITE_OK. If there is no such record in the table, set |
| 1821 |
** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf |
| 1822 |
** to zero and return an SQLite error code. |
| 1823 |
*/ |
| 1824 |
static int findLeafNode( |
| 1825 |
Rtree *pRtree, /* RTree to search */ |
| 1826 |
i64 iRowid, /* The rowid searching for */ |
| 1827 |
RtreeNode **ppLeaf, /* Write the node here */ |
| 1828 |
sqlite3_int64 *piNode /* Write the node-id here */ |
| 1829 |
){ |
| 1830 |
int rc; |
| 1831 |
*ppLeaf = 0; |
| 1832 |
sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid); |
| 1833 |
if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){ |
| 1834 |
i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0); |
| 1835 |
if( piNode ) *piNode = iNode; |
| 1836 |
rc = nodeAcquire(pRtree, iNode, 0, ppLeaf); |
| 1837 |
sqlite3_reset(pRtree->pReadRowid); |
| 1838 |
}else{ |
| 1839 |
rc = sqlite3_reset(pRtree->pReadRowid); |
| 1840 |
} |
| 1841 |
return rc; |
| 1842 |
} |
| 1843 |
|
| 1844 |
/* |
| 1845 |
** This function is called to configure the RtreeConstraint object passed |
| 1846 |
** as the second argument for a MATCH constraint. The value passed as the |
| 1847 |
** first argument to this function is the right-hand operand to the MATCH |
| 1848 |
** operator. |
| 1849 |
*/ |
| 1850 |
static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){ |
| 1851 |
RtreeMatchArg *pBlob, *pSrc; /* BLOB returned by geometry function */ |
| 1852 |
sqlite3_rtree_query_info *pInfo; /* Callback information */ |
| 1853 |
|
| 1854 |
pSrc = sqlite3_value_pointer(pValue, "RtreeMatchArg"); |
| 1855 |
if( pSrc==0 ) return SQLITE_ERROR; |
| 1856 |
pInfo = (sqlite3_rtree_query_info*) |
| 1857 |
sqlite3_malloc64( sizeof(*pInfo)+pSrc->iSize ); |
| 1858 |
if( !pInfo ) return SQLITE_NOMEM; |
| 1859 |
memset(pInfo, 0, sizeof(*pInfo)); |
| 1860 |
pBlob = (RtreeMatchArg*)&pInfo[1]; |
| 1861 |
memcpy(pBlob, pSrc, pSrc->iSize); |
| 1862 |
pInfo->pContext = pBlob->cb.pContext; |
| 1863 |
pInfo->nParam = pBlob->nParam; |
| 1864 |
pInfo->aParam = pBlob->aParam; |
| 1865 |
pInfo->apSqlParam = pBlob->apSqlParam; |
| 1866 |
|
| 1867 |
if( pBlob->cb.xGeom ){ |
| 1868 |
pCons->u.xGeom = pBlob->cb.xGeom; |
| 1869 |
}else{ |
| 1870 |
pCons->op = RTREE_QUERY; |
| 1871 |
pCons->u.xQueryFunc = pBlob->cb.xQueryFunc; |
| 1872 |
} |
| 1873 |
pCons->pInfo = pInfo; |
| 1874 |
return SQLITE_OK; |
| 1875 |
} |
| 1876 |
|
| 1877 |
int sqlite3IntFloatCompare(i64,double); |
| 1878 |
|
| 1879 |
/* |
| 1880 |
** Rtree virtual table module xFilter method. |
| 1881 |
*/ |
| 1882 |
static int rtreeFilter( |
| 1883 |
sqlite3_vtab_cursor *pVtabCursor, |
| 1884 |
int idxNum, const char *idxStr, |
| 1885 |
int argc, sqlite3_value **argv |
| 1886 |
){ |
| 1887 |
Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; |
| 1888 |
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
| 1889 |
RtreeNode *pRoot = 0; |
| 1890 |
int ii; |
| 1891 |
int rc = SQLITE_OK; |
| 1892 |
int iCell = 0; |
| 1893 |
|
| 1894 |
rtreeReference(pRtree); |
| 1895 |
|
| 1896 |
/* Reset the cursor to the same state as rtreeOpen() leaves it in. */ |
| 1897 |
resetCursor(pCsr); |
| 1898 |
|
| 1899 |
pCsr->iStrategy = idxNum; |
| 1900 |
if( idxNum==1 ){ |
| 1901 |
/* Special case - lookup by rowid. */ |
| 1902 |
RtreeNode *pLeaf; /* Leaf on which the required cell resides */ |
| 1903 |
RtreeSearchPoint *p; /* Search point for the leaf */ |
| 1904 |
i64 iRowid = sqlite3_value_int64(argv[0]); |
| 1905 |
i64 iNode = 0; |
| 1906 |
int eType = sqlite3_value_numeric_type(argv[0]); |
| 1907 |
if( eType==SQLITE_INTEGER |
| 1908 |
|| (eType==SQLITE_FLOAT |
| 1909 |
&& 0==sqlite3IntFloatCompare(iRowid,sqlite3_value_double(argv[0]))) |
| 1910 |
){ |
| 1911 |
rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); |
| 1912 |
}else{ |
| 1913 |
rc = SQLITE_OK; |
| 1914 |
pLeaf = 0; |
| 1915 |
} |
| 1916 |
if( rc==SQLITE_OK && pLeaf!=0 ){ |
| 1917 |
p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0); |
| 1918 |
assert( p!=0 ); /* Always returns pCsr->sPoint */ |
| 1919 |
pCsr->aNode[0] = pLeaf; |
| 1920 |
p->id = iNode; |
| 1921 |
p->eWithin = PARTLY_WITHIN; |
| 1922 |
rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); |
| 1923 |
p->iCell = (u8)iCell; |
| 1924 |
RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:"); |
| 1925 |
}else{ |
| 1926 |
pCsr->atEOF = 1; |
| 1927 |
} |
| 1928 |
}else{ |
| 1929 |
/* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array |
| 1930 |
** with the configured constraints. |
| 1931 |
*/ |
| 1932 |
rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
| 1933 |
if( rc==SQLITE_OK && argc>0 ){ |
| 1934 |
pCsr->aConstraint = sqlite3_malloc64(sizeof(RtreeConstraint)*argc); |
| 1935 |
pCsr->nConstraint = argc; |
| 1936 |
if( !pCsr->aConstraint ){ |
| 1937 |
rc = SQLITE_NOMEM; |
| 1938 |
}else{ |
| 1939 |
memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc); |
| 1940 |
memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); |
| 1941 |
assert( (idxStr==0 && argc==0) |
| 1942 |
|| (idxStr && (int)strlen(idxStr)==argc*2) ); |
| 1943 |
for(ii=0; ii<argc; ii++){ |
| 1944 |
RtreeConstraint *p = &pCsr->aConstraint[ii]; |
| 1945 |
int eType = sqlite3_value_numeric_type(argv[ii]); |
| 1946 |
p->op = idxStr[ii*2]; |
| 1947 |
p->iCoord = idxStr[ii*2+1]-'0'; |
| 1948 |
if( p->op>=RTREE_MATCH ){ |
| 1949 |
/* A MATCH operator. The right-hand-side must be a blob that |
| 1950 |
** can be cast into an RtreeMatchArg object. One created using |
| 1951 |
** an sqlite3_rtree_geometry_callback() SQL user function. |
| 1952 |
*/ |
| 1953 |
rc = deserializeGeometry(argv[ii], p); |
| 1954 |
if( rc!=SQLITE_OK ){ |
| 1955 |
break; |
| 1956 |
} |
| 1957 |
p->pInfo->nCoord = pRtree->nDim2; |
| 1958 |
p->pInfo->anQueue = pCsr->anQueue; |
| 1959 |
p->pInfo->mxLevel = pRtree->iDepth + 1; |
| 1960 |
}else if( eType==SQLITE_INTEGER ){ |
| 1961 |
sqlite3_int64 iVal = sqlite3_value_int64(argv[ii]); |
| 1962 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 1963 |
p->u.rValue = iVal; |
| 1964 |
#else |
| 1965 |
p->u.rValue = (double)iVal; |
| 1966 |
if( iVal>=((sqlite3_int64)1)<<48 |
| 1967 |
|| iVal<=-(((sqlite3_int64)1)<<48) |
| 1968 |
){ |
| 1969 |
if( p->op==RTREE_LT ) p->op = RTREE_LE; |
| 1970 |
if( p->op==RTREE_GT ) p->op = RTREE_GE; |
| 1971 |
} |
| 1972 |
#endif |
| 1973 |
}else if( eType==SQLITE_FLOAT ){ |
| 1974 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 1975 |
p->u.rValue = sqlite3_value_int64(argv[ii]); |
| 1976 |
#else |
| 1977 |
p->u.rValue = sqlite3_value_double(argv[ii]); |
| 1978 |
#endif |
| 1979 |
}else{ |
| 1980 |
p->u.rValue = RTREE_ZERO; |
| 1981 |
if( eType==SQLITE_NULL ){ |
| 1982 |
p->op = RTREE_FALSE; |
| 1983 |
}else if( p->op==RTREE_LT || p->op==RTREE_LE ){ |
| 1984 |
p->op = RTREE_TRUE; |
| 1985 |
}else{ |
| 1986 |
p->op = RTREE_FALSE; |
| 1987 |
} |
| 1988 |
} |
| 1989 |
} |
| 1990 |
} |
| 1991 |
} |
| 1992 |
if( rc==SQLITE_OK ){ |
| 1993 |
RtreeSearchPoint *pNew; |
| 1994 |
assert( pCsr->bPoint==0 ); /* Due to the resetCursor() call above */ |
| 1995 |
pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1)); |
| 1996 |
if( NEVER(pNew==0) ){ /* Because pCsr->bPoint was FALSE */ |
| 1997 |
return SQLITE_NOMEM; |
| 1998 |
} |
| 1999 |
pNew->id = 1; |
| 2000 |
pNew->iCell = 0; |
| 2001 |
pNew->eWithin = PARTLY_WITHIN; |
| 2002 |
assert( pCsr->bPoint==1 ); |
| 2003 |
pCsr->aNode[0] = pRoot; |
| 2004 |
pRoot = 0; |
| 2005 |
RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); |
| 2006 |
rc = rtreeStepToLeaf(pCsr); |
| 2007 |
} |
| 2008 |
} |
| 2009 |
|
| 2010 |
nodeRelease(pRtree, pRoot); |
| 2011 |
rtreeRelease(pRtree); |
| 2012 |
return rc; |
| 2013 |
} |
| 2014 |
|
| 2015 |
/* |
| 2016 |
** Rtree virtual table module xBestIndex method. There are three |
| 2017 |
** table scan strategies to choose from (in order from most to |
| 2018 |
** least desirable): |
| 2019 |
** |
| 2020 |
** idxNum idxStr Strategy |
| 2021 |
** ------------------------------------------------ |
| 2022 |
** 1 Unused Direct lookup by rowid. |
| 2023 |
** 2 See below R-tree query or full-table scan. |
| 2024 |
** ------------------------------------------------ |
| 2025 |
** |
| 2026 |
** If strategy 1 is used, then idxStr is not meaningful. If strategy |
| 2027 |
** 2 is used, idxStr is formatted to contain 2 bytes for each |
| 2028 |
** constraint used. The first two bytes of idxStr correspond to |
| 2029 |
** the constraint in sqlite3_index_info.aConstraintUsage[] with |
| 2030 |
** (argvIndex==1) etc. |
| 2031 |
** |
| 2032 |
** The first of each pair of bytes in idxStr identifies the constraint |
| 2033 |
** operator as follows: |
| 2034 |
** |
| 2035 |
** Operator Byte Value |
| 2036 |
** ---------------------- |
| 2037 |
** = 0x41 ('A') |
| 2038 |
** <= 0x42 ('B') |
| 2039 |
** < 0x43 ('C') |
| 2040 |
** >= 0x44 ('D') |
| 2041 |
** > 0x45 ('E') |
| 2042 |
** MATCH 0x46 ('F') |
| 2043 |
** ---------------------- |
| 2044 |
** |
| 2045 |
** The second of each pair of bytes identifies the coordinate column |
| 2046 |
** to which the constraint applies. The leftmost coordinate column |
| 2047 |
** is 'a', the second from the left 'b' etc. |
| 2048 |
*/ |
| 2049 |
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ |
| 2050 |
Rtree *pRtree = (Rtree*)tab; |
| 2051 |
int rc = SQLITE_OK; |
| 2052 |
int ii; |
| 2053 |
int bMatch = 0; /* True if there exists a MATCH constraint */ |
| 2054 |
i64 nRow; /* Estimated rows returned by this scan */ |
| 2055 |
|
| 2056 |
int iIdx = 0; |
| 2057 |
char zIdxStr[RTREE_MAX_DIMENSIONS*8+1]; |
| 2058 |
memset(zIdxStr, 0, sizeof(zIdxStr)); |
| 2059 |
|
| 2060 |
/* Check if there exists a MATCH constraint - even an unusable one. If there |
| 2061 |
** is, do not consider the lookup-by-rowid plan as using such a plan would |
| 2062 |
** require the VDBE to evaluate the MATCH constraint, which is not currently |
| 2063 |
** possible. */ |
| 2064 |
for(ii=0; ii<pIdxInfo->nConstraint; ii++){ |
| 2065 |
if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){ |
| 2066 |
bMatch = 1; |
| 2067 |
} |
| 2068 |
} |
| 2069 |
|
| 2070 |
assert( pIdxInfo->idxStr==0 ); |
| 2071 |
for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){ |
| 2072 |
struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii]; |
| 2073 |
|
| 2074 |
if( bMatch==0 && p->usable |
| 2075 |
&& p->iColumn<=0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ |
| 2076 |
){ |
| 2077 |
/* We have an equality constraint on the rowid. Use strategy 1. */ |
| 2078 |
int jj; |
| 2079 |
for(jj=0; jj<ii; jj++){ |
| 2080 |
pIdxInfo->aConstraintUsage[jj].argvIndex = 0; |
| 2081 |
pIdxInfo->aConstraintUsage[jj].omit = 0; |
| 2082 |
} |
| 2083 |
pIdxInfo->idxNum = 1; |
| 2084 |
pIdxInfo->aConstraintUsage[ii].argvIndex = 1; |
| 2085 |
pIdxInfo->aConstraintUsage[jj].omit = 1; |
| 2086 |
|
| 2087 |
/* This strategy involves a two rowid lookups on an B-Tree structures |
| 2088 |
** and then a linear search of an R-Tree node. This should be |
| 2089 |
** considered almost as quick as a direct rowid lookup (for which |
| 2090 |
** sqlite uses an internal cost of 0.0). It is expected to return |
| 2091 |
** a single row. |
| 2092 |
*/ |
| 2093 |
pIdxInfo->estimatedCost = 30.0; |
| 2094 |
pIdxInfo->estimatedRows = 1; |
| 2095 |
pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE; |
| 2096 |
return SQLITE_OK; |
| 2097 |
} |
| 2098 |
|
| 2099 |
if( p->usable |
| 2100 |
&& ((p->iColumn>0 && p->iColumn<=pRtree->nDim2) |
| 2101 |
|| p->op==SQLITE_INDEX_CONSTRAINT_MATCH) |
| 2102 |
){ |
| 2103 |
u8 op; |
| 2104 |
u8 doOmit = 1; |
| 2105 |
switch( p->op ){ |
| 2106 |
case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; doOmit = 0; break; |
| 2107 |
case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; doOmit = 0; break; |
| 2108 |
case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break; |
| 2109 |
case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; doOmit = 0; break; |
| 2110 |
case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; |
| 2111 |
case SQLITE_INDEX_CONSTRAINT_MATCH: op = RTREE_MATCH; break; |
| 2112 |
default: op = 0; break; |
| 2113 |
} |
| 2114 |
if( op ){ |
| 2115 |
zIdxStr[iIdx++] = op; |
| 2116 |
zIdxStr[iIdx++] = (char)(p->iColumn - 1 + '0'); |
| 2117 |
pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); |
| 2118 |
pIdxInfo->aConstraintUsage[ii].omit = doOmit; |
| 2119 |
} |
| 2120 |
} |
| 2121 |
} |
| 2122 |
|
| 2123 |
pIdxInfo->idxNum = 2; |
| 2124 |
pIdxInfo->needToFreeIdxStr = 1; |
| 2125 |
if( iIdx>0 ){ |
| 2126 |
pIdxInfo->idxStr = sqlite3_malloc( iIdx+1 ); |
| 2127 |
if( pIdxInfo->idxStr==0 ){ |
| 2128 |
return SQLITE_NOMEM; |
| 2129 |
} |
| 2130 |
memcpy(pIdxInfo->idxStr, zIdxStr, iIdx+1); |
| 2131 |
} |
| 2132 |
|
| 2133 |
nRow = pRtree->nRowEst >> (iIdx/2); |
| 2134 |
pIdxInfo->estimatedCost = (double)6.0 * (double)nRow; |
| 2135 |
pIdxInfo->estimatedRows = nRow; |
| 2136 |
|
| 2137 |
return rc; |
| 2138 |
} |
| 2139 |
|
| 2140 |
/* |
| 2141 |
** Return the N-dimensional volume of the cell stored in *p. |
| 2142 |
*/ |
| 2143 |
static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){ |
| 2144 |
RtreeDValue area = (RtreeDValue)1; |
| 2145 |
assert( pRtree->nDim>=1 && pRtree->nDim<=5 ); |
| 2146 |
#ifndef SQLITE_RTREE_INT_ONLY |
| 2147 |
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| 2148 |
switch( pRtree->nDim ){ |
| 2149 |
case 5: area = p->aCoord[9].f - p->aCoord[8].f; |
| 2150 |
case 4: area *= p->aCoord[7].f - p->aCoord[6].f; |
| 2151 |
case 3: area *= p->aCoord[5].f - p->aCoord[4].f; |
| 2152 |
case 2: area *= p->aCoord[3].f - p->aCoord[2].f; |
| 2153 |
default: area *= p->aCoord[1].f - p->aCoord[0].f; |
| 2154 |
} |
| 2155 |
}else |
| 2156 |
#endif |
| 2157 |
{ |
| 2158 |
switch( pRtree->nDim ){ |
| 2159 |
case 5: area = (i64)p->aCoord[9].i - (i64)p->aCoord[8].i; |
| 2160 |
case 4: area *= (i64)p->aCoord[7].i - (i64)p->aCoord[6].i; |
| 2161 |
case 3: area *= (i64)p->aCoord[5].i - (i64)p->aCoord[4].i; |
| 2162 |
case 2: area *= (i64)p->aCoord[3].i - (i64)p->aCoord[2].i; |
| 2163 |
default: area *= (i64)p->aCoord[1].i - (i64)p->aCoord[0].i; |
| 2164 |
} |
| 2165 |
} |
| 2166 |
return area; |
| 2167 |
} |
| 2168 |
|
| 2169 |
/* |
| 2170 |
** Return the margin length of cell p. The margin length is the sum |
| 2171 |
** of the objects size in each dimension. |
| 2172 |
*/ |
| 2173 |
static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){ |
| 2174 |
RtreeDValue margin = 0; |
| 2175 |
int ii = pRtree->nDim2 - 2; |
| 2176 |
do{ |
| 2177 |
margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
| 2178 |
ii -= 2; |
| 2179 |
}while( ii>=0 ); |
| 2180 |
return margin; |
| 2181 |
} |
| 2182 |
|
| 2183 |
/* |
| 2184 |
** Store the union of cells p1 and p2 in p1. |
| 2185 |
*/ |
| 2186 |
static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
| 2187 |
int ii = 0; |
| 2188 |
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| 2189 |
do{ |
| 2190 |
p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); |
| 2191 |
p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); |
| 2192 |
ii += 2; |
| 2193 |
}while( ii<pRtree->nDim2 ); |
| 2194 |
}else{ |
| 2195 |
do{ |
| 2196 |
p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); |
| 2197 |
p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); |
| 2198 |
ii += 2; |
| 2199 |
}while( ii<pRtree->nDim2 ); |
| 2200 |
} |
| 2201 |
} |
| 2202 |
|
| 2203 |
/* |
| 2204 |
** Return true if the area covered by p2 is a subset of the area covered |
| 2205 |
** by p1. False otherwise. |
| 2206 |
*/ |
| 2207 |
static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
| 2208 |
int ii; |
| 2209 |
if( pRtree->eCoordType==RTREE_COORD_INT32 ){ |
| 2210 |
for(ii=0; ii<pRtree->nDim2; ii+=2){ |
| 2211 |
RtreeCoord *a1 = &p1->aCoord[ii]; |
| 2212 |
RtreeCoord *a2 = &p2->aCoord[ii]; |
| 2213 |
if( a2[0].i<a1[0].i || a2[1].i>a1[1].i ) return 0; |
| 2214 |
} |
| 2215 |
}else{ |
| 2216 |
for(ii=0; ii<pRtree->nDim2; ii+=2){ |
| 2217 |
RtreeCoord *a1 = &p1->aCoord[ii]; |
| 2218 |
RtreeCoord *a2 = &p2->aCoord[ii]; |
| 2219 |
if( a2[0].f<a1[0].f || a2[1].f>a1[1].f ) return 0; |
| 2220 |
} |
| 2221 |
} |
| 2222 |
return 1; |
| 2223 |
} |
| 2224 |
|
| 2225 |
static RtreeDValue cellOverlap( |
| 2226 |
Rtree *pRtree, |
| 2227 |
RtreeCell *p, |
| 2228 |
RtreeCell *aCell, |
| 2229 |
int nCell |
| 2230 |
){ |
| 2231 |
int ii; |
| 2232 |
RtreeDValue overlap = RTREE_ZERO; |
| 2233 |
for(ii=0; ii<nCell; ii++){ |
| 2234 |
int jj; |
| 2235 |
RtreeDValue o = (RtreeDValue)1; |
| 2236 |
for(jj=0; jj<pRtree->nDim2; jj+=2){ |
| 2237 |
RtreeDValue x1, x2; |
| 2238 |
x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); |
| 2239 |
x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); |
| 2240 |
if( x2<x1 ){ |
| 2241 |
o = (RtreeDValue)0; |
| 2242 |
break; |
| 2243 |
}else{ |
| 2244 |
o = o * (x2-x1); |
| 2245 |
} |
| 2246 |
} |
| 2247 |
overlap += o; |
| 2248 |
} |
| 2249 |
return overlap; |
| 2250 |
} |
| 2251 |
|
| 2252 |
|
| 2253 |
/* |
| 2254 |
** This function implements the ChooseLeaf algorithm from Gutman[84]. |
| 2255 |
** ChooseSubTree in r*tree terminology. |
| 2256 |
*/ |
| 2257 |
static int ChooseLeaf( |
| 2258 |
Rtree *pRtree, /* Rtree table */ |
| 2259 |
RtreeCell *pCell, /* Cell to insert into rtree */ |
| 2260 |
int iHeight, /* Height of sub-tree rooted at pCell */ |
| 2261 |
RtreeNode **ppLeaf /* OUT: Selected leaf page */ |
| 2262 |
){ |
| 2263 |
int rc; |
| 2264 |
int ii; |
| 2265 |
RtreeNode *pNode = 0; |
| 2266 |
rc = nodeAcquire(pRtree, 1, 0, &pNode); |
| 2267 |
|
| 2268 |
for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ |
| 2269 |
int iCell; |
| 2270 |
sqlite3_int64 iBest = 0; |
| 2271 |
int bFound = 0; |
| 2272 |
RtreeDValue fMinGrowth = RTREE_ZERO; |
| 2273 |
RtreeDValue fMinArea = RTREE_ZERO; |
| 2274 |
int nCell = NCELL(pNode); |
| 2275 |
RtreeNode *pChild = 0; |
| 2276 |
|
| 2277 |
/* First check to see if there is are any cells in pNode that completely |
| 2278 |
** contains pCell. If two or more cells in pNode completely contain pCell |
| 2279 |
** then pick the smallest. |
| 2280 |
*/ |
| 2281 |
for(iCell=0; iCell<nCell; iCell++){ |
| 2282 |
RtreeCell cell; |
| 2283 |
nodeGetCell(pRtree, pNode, iCell, &cell); |
| 2284 |
if( cellContains(pRtree, &cell, pCell) ){ |
| 2285 |
RtreeDValue area = cellArea(pRtree, &cell); |
| 2286 |
if( bFound==0 || area<fMinArea ){ |
| 2287 |
iBest = cell.iRowid; |
| 2288 |
fMinArea = area; |
| 2289 |
bFound = 1; |
| 2290 |
} |
| 2291 |
} |
| 2292 |
} |
| 2293 |
if( !bFound ){ |
| 2294 |
/* No cells of pNode will completely contain pCell. So pick the |
| 2295 |
** cell of pNode that grows by the least amount when pCell is added. |
| 2296 |
** Break ties by selecting the smaller cell. |
| 2297 |
*/ |
| 2298 |
for(iCell=0; iCell<nCell; iCell++){ |
| 2299 |
RtreeCell cell; |
| 2300 |
RtreeDValue growth; |
| 2301 |
RtreeDValue area; |
| 2302 |
nodeGetCell(pRtree, pNode, iCell, &cell); |
| 2303 |
area = cellArea(pRtree, &cell); |
| 2304 |
cellUnion(pRtree, &cell, pCell); |
| 2305 |
growth = cellArea(pRtree, &cell)-area; |
| 2306 |
if( iCell==0 |
| 2307 |
|| growth<fMinGrowth |
| 2308 |
|| (growth==fMinGrowth && area<fMinArea) |
| 2309 |
){ |
| 2310 |
fMinGrowth = growth; |
| 2311 |
fMinArea = area; |
| 2312 |
iBest = cell.iRowid; |
| 2313 |
} |
| 2314 |
} |
| 2315 |
} |
| 2316 |
|
| 2317 |
rc = nodeAcquire(pRtree, iBest, pNode, &pChild); |
| 2318 |
nodeRelease(pRtree, pNode); |
| 2319 |
pNode = pChild; |
| 2320 |
} |
| 2321 |
|
| 2322 |
*ppLeaf = pNode; |
| 2323 |
return rc; |
| 2324 |
} |
| 2325 |
|
| 2326 |
/* |
| 2327 |
** A cell with the same content as pCell has just been inserted into |
| 2328 |
** the node pNode. This function updates the bounding box cells in |
| 2329 |
** all ancestor elements. |
| 2330 |
*/ |
| 2331 |
static int AdjustTree( |
| 2332 |
Rtree *pRtree, /* Rtree table */ |
| 2333 |
RtreeNode *pNode, /* Adjust ancestry of this node. */ |
| 2334 |
RtreeCell *pCell /* This cell was just inserted */ |
| 2335 |
){ |
| 2336 |
RtreeNode *p = pNode; |
| 2337 |
int cnt = 0; |
| 2338 |
int rc; |
| 2339 |
while( p->pParent ){ |
| 2340 |
RtreeNode *pParent = p->pParent; |
| 2341 |
RtreeCell cell; |
| 2342 |
int iCell; |
| 2343 |
|
| 2344 |
cnt++; |
| 2345 |
if( cnt>100 ){ |
| 2346 |
RTREE_IS_CORRUPT(pRtree); |
| 2347 |
return SQLITE_CORRUPT_VTAB; |
| 2348 |
} |
| 2349 |
rc = nodeParentIndex(pRtree, p, &iCell); |
| 2350 |
if( NEVER(rc!=SQLITE_OK) ){ |
| 2351 |
RTREE_IS_CORRUPT(pRtree); |
| 2352 |
return SQLITE_CORRUPT_VTAB; |
| 2353 |
} |
| 2354 |
|
| 2355 |
nodeGetCell(pRtree, pParent, iCell, &cell); |
| 2356 |
if( !cellContains(pRtree, &cell, pCell) ){ |
| 2357 |
cellUnion(pRtree, &cell, pCell); |
| 2358 |
nodeOverwriteCell(pRtree, pParent, &cell, iCell); |
| 2359 |
} |
| 2360 |
|
| 2361 |
p = pParent; |
| 2362 |
} |
| 2363 |
return SQLITE_OK; |
| 2364 |
} |
| 2365 |
|
| 2366 |
/* |
| 2367 |
** Write mapping (iRowid->iNode) to the <rtree>_rowid table. |
| 2368 |
*/ |
| 2369 |
static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){ |
| 2370 |
sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid); |
| 2371 |
sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode); |
| 2372 |
sqlite3_step(pRtree->pWriteRowid); |
| 2373 |
return sqlite3_reset(pRtree->pWriteRowid); |
| 2374 |
} |
| 2375 |
|
| 2376 |
/* |
| 2377 |
** Write mapping (iNode->iPar) to the <rtree>_parent table. |
| 2378 |
*/ |
| 2379 |
static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){ |
| 2380 |
sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode); |
| 2381 |
sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); |
| 2382 |
sqlite3_step(pRtree->pWriteParent); |
| 2383 |
return sqlite3_reset(pRtree->pWriteParent); |
| 2384 |
} |
| 2385 |
|
| 2386 |
static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int); |
| 2387 |
|
| 2388 |
|
| 2389 |
|
| 2390 |
/* |
| 2391 |
** Arguments aIdx, aCell and aSpare all point to arrays of size |
| 2392 |
** nIdx. The aIdx array contains the set of integers from 0 to |
| 2393 |
** (nIdx-1) in no particular order. This function sorts the values |
| 2394 |
** in aIdx according to dimension iDim of the cells in aCell. The |
| 2395 |
** minimum value of dimension iDim is considered first, the |
| 2396 |
** maximum used to break ties. |
| 2397 |
** |
| 2398 |
** The aSpare array is used as temporary working space by the |
| 2399 |
** sorting algorithm. |
| 2400 |
*/ |
| 2401 |
static void SortByDimension( |
| 2402 |
Rtree *pRtree, |
| 2403 |
int *aIdx, |
| 2404 |
int nIdx, |
| 2405 |
int iDim, |
| 2406 |
RtreeCell *aCell, |
| 2407 |
int *aSpare |
| 2408 |
){ |
| 2409 |
if( nIdx>1 ){ |
| 2410 |
|
| 2411 |
int iLeft = 0; |
| 2412 |
int iRight = 0; |
| 2413 |
|
| 2414 |
int nLeft = nIdx/2; |
| 2415 |
int nRight = nIdx-nLeft; |
| 2416 |
int *aLeft = aIdx; |
| 2417 |
int *aRight = &aIdx[nLeft]; |
| 2418 |
|
| 2419 |
SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare); |
| 2420 |
SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare); |
| 2421 |
|
| 2422 |
memcpy(aSpare, aLeft, sizeof(int)*nLeft); |
| 2423 |
aLeft = aSpare; |
| 2424 |
while( iLeft<nLeft || iRight<nRight ){ |
| 2425 |
RtreeDValue xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]); |
| 2426 |
RtreeDValue xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]); |
| 2427 |
RtreeDValue xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]); |
| 2428 |
RtreeDValue xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]); |
| 2429 |
if( (iLeft!=nLeft) && ((iRight==nRight) |
| 2430 |
|| (xleft1<xright1) |
| 2431 |
|| (xleft1==xright1 && xleft2<xright2) |
| 2432 |
)){ |
| 2433 |
aIdx[iLeft+iRight] = aLeft[iLeft]; |
| 2434 |
iLeft++; |
| 2435 |
}else{ |
| 2436 |
aIdx[iLeft+iRight] = aRight[iRight]; |
| 2437 |
iRight++; |
| 2438 |
} |
| 2439 |
} |
| 2440 |
|
| 2441 |
#if 0 |
| 2442 |
/* Check that the sort worked */ |
| 2443 |
{ |
| 2444 |
int jj; |
| 2445 |
for(jj=1; jj<nIdx; jj++){ |
| 2446 |
RtreeDValue xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; |
| 2447 |
RtreeDValue xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; |
| 2448 |
RtreeDValue xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; |
| 2449 |
RtreeDValue xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; |
| 2450 |
assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); |
| 2451 |
} |
| 2452 |
} |
| 2453 |
#endif |
| 2454 |
} |
| 2455 |
} |
| 2456 |
|
| 2457 |
/* |
| 2458 |
** Implementation of the R*-tree variant of SplitNode from Beckman[1990]. |
| 2459 |
*/ |
| 2460 |
static int splitNodeStartree( |
| 2461 |
Rtree *pRtree, |
| 2462 |
RtreeCell *aCell, |
| 2463 |
int nCell, |
| 2464 |
RtreeNode *pLeft, |
| 2465 |
RtreeNode *pRight, |
| 2466 |
RtreeCell *pBboxLeft, |
| 2467 |
RtreeCell *pBboxRight |
| 2468 |
){ |
| 2469 |
int **aaSorted; |
| 2470 |
int *aSpare; |
| 2471 |
int ii; |
| 2472 |
|
| 2473 |
int iBestDim = 0; |
| 2474 |
int iBestSplit = 0; |
| 2475 |
RtreeDValue fBestMargin = RTREE_ZERO; |
| 2476 |
|
| 2477 |
sqlite3_int64 nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); |
| 2478 |
|
| 2479 |
aaSorted = (int **)sqlite3_malloc64(nByte); |
| 2480 |
if( !aaSorted ){ |
| 2481 |
return SQLITE_NOMEM; |
| 2482 |
} |
| 2483 |
|
| 2484 |
aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell]; |
| 2485 |
memset(aaSorted, 0, nByte); |
| 2486 |
for(ii=0; ii<pRtree->nDim; ii++){ |
| 2487 |
int jj; |
| 2488 |
aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; |
| 2489 |
for(jj=0; jj<nCell; jj++){ |
| 2490 |
aaSorted[ii][jj] = jj; |
| 2491 |
} |
| 2492 |
SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); |
| 2493 |
} |
| 2494 |
|
| 2495 |
for(ii=0; ii<pRtree->nDim; ii++){ |
| 2496 |
RtreeDValue margin = RTREE_ZERO; |
| 2497 |
RtreeDValue fBestOverlap = RTREE_ZERO; |
| 2498 |
RtreeDValue fBestArea = RTREE_ZERO; |
| 2499 |
int iBestLeft = 0; |
| 2500 |
int nLeft; |
| 2501 |
|
| 2502 |
for( |
| 2503 |
nLeft=RTREE_MINCELLS(pRtree); |
| 2504 |
nLeft<=(nCell-RTREE_MINCELLS(pRtree)); |
| 2505 |
nLeft++ |
| 2506 |
){ |
| 2507 |
RtreeCell left; |
| 2508 |
RtreeCell right; |
| 2509 |
int kk; |
| 2510 |
RtreeDValue overlap; |
| 2511 |
RtreeDValue area; |
| 2512 |
|
| 2513 |
memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell)); |
| 2514 |
memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell)); |
| 2515 |
for(kk=1; kk<(nCell-1); kk++){ |
| 2516 |
if( kk<nLeft ){ |
| 2517 |
cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); |
| 2518 |
}else{ |
| 2519 |
cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); |
| 2520 |
} |
| 2521 |
} |
| 2522 |
margin += cellMargin(pRtree, &left); |
| 2523 |
margin += cellMargin(pRtree, &right); |
| 2524 |
overlap = cellOverlap(pRtree, &left, &right, 1); |
| 2525 |
area = cellArea(pRtree, &left) + cellArea(pRtree, &right); |
| 2526 |
if( (nLeft==RTREE_MINCELLS(pRtree)) |
| 2527 |
|| (overlap<fBestOverlap) |
| 2528 |
|| (overlap==fBestOverlap && area<fBestArea) |
| 2529 |
){ |
| 2530 |
iBestLeft = nLeft; |
| 2531 |
fBestOverlap = overlap; |
| 2532 |
fBestArea = area; |
| 2533 |
} |
| 2534 |
} |
| 2535 |
|
| 2536 |
if( ii==0 || margin<fBestMargin ){ |
| 2537 |
iBestDim = ii; |
| 2538 |
fBestMargin = margin; |
| 2539 |
iBestSplit = iBestLeft; |
| 2540 |
} |
| 2541 |
} |
| 2542 |
|
| 2543 |
memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell)); |
| 2544 |
memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell)); |
| 2545 |
for(ii=0; ii<nCell; ii++){ |
| 2546 |
RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight; |
| 2547 |
RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight; |
| 2548 |
RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]]; |
| 2549 |
nodeInsertCell(pRtree, pTarget, pCell); |
| 2550 |
cellUnion(pRtree, pBbox, pCell); |
| 2551 |
} |
| 2552 |
|
| 2553 |
sqlite3_free(aaSorted); |
| 2554 |
return SQLITE_OK; |
| 2555 |
} |
| 2556 |
|
| 2557 |
|
| 2558 |
static int updateMapping( |
| 2559 |
Rtree *pRtree, |
| 2560 |
i64 iRowid, |
| 2561 |
RtreeNode *pNode, |
| 2562 |
int iHeight |
| 2563 |
){ |
| 2564 |
int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64); |
| 2565 |
xSetMapping = ((iHeight==0)?rowidWrite:parentWrite); |
| 2566 |
if( iHeight>0 ){ |
| 2567 |
RtreeNode *pChild = nodeHashLookup(pRtree, iRowid); |
| 2568 |
RtreeNode *p; |
| 2569 |
for(p=pNode; p; p=p->pParent){ |
| 2570 |
if( p==pChild ) return SQLITE_CORRUPT_VTAB; |
| 2571 |
} |
| 2572 |
if( pChild ){ |
| 2573 |
nodeRelease(pRtree, pChild->pParent); |
| 2574 |
nodeReference(pNode); |
| 2575 |
pChild->pParent = pNode; |
| 2576 |
} |
| 2577 |
} |
| 2578 |
if( NEVER(pNode==0) ) return SQLITE_ERROR; |
| 2579 |
return xSetMapping(pRtree, iRowid, pNode->iNode); |
| 2580 |
} |
| 2581 |
|
| 2582 |
static int SplitNode( |
| 2583 |
Rtree *pRtree, |
| 2584 |
RtreeNode *pNode, |
| 2585 |
RtreeCell *pCell, |
| 2586 |
int iHeight |
| 2587 |
){ |
| 2588 |
int i; |
| 2589 |
int newCellIsRight = 0; |
| 2590 |
|
| 2591 |
int rc = SQLITE_OK; |
| 2592 |
int nCell = NCELL(pNode); |
| 2593 |
RtreeCell *aCell; |
| 2594 |
int *aiUsed; |
| 2595 |
|
| 2596 |
RtreeNode *pLeft = 0; |
| 2597 |
RtreeNode *pRight = 0; |
| 2598 |
|
| 2599 |
RtreeCell leftbbox; |
| 2600 |
RtreeCell rightbbox; |
| 2601 |
|
| 2602 |
/* Allocate an array and populate it with a copy of pCell and |
| 2603 |
** all cells from node pLeft. Then zero the original node. |
| 2604 |
*/ |
| 2605 |
aCell = sqlite3_malloc64((sizeof(RtreeCell)+sizeof(int))*(nCell+1)); |
| 2606 |
if( !aCell ){ |
| 2607 |
rc = SQLITE_NOMEM; |
| 2608 |
goto splitnode_out; |
| 2609 |
} |
| 2610 |
aiUsed = (int *)&aCell[nCell+1]; |
| 2611 |
memset(aiUsed, 0, sizeof(int)*(nCell+1)); |
| 2612 |
for(i=0; i<nCell; i++){ |
| 2613 |
nodeGetCell(pRtree, pNode, i, &aCell[i]); |
| 2614 |
} |
| 2615 |
nodeZero(pRtree, pNode); |
| 2616 |
memcpy(&aCell[nCell], pCell, sizeof(RtreeCell)); |
| 2617 |
nCell++; |
| 2618 |
|
| 2619 |
if( pNode->iNode==1 ){ |
| 2620 |
pRight = nodeNew(pRtree, pNode); |
| 2621 |
pLeft = nodeNew(pRtree, pNode); |
| 2622 |
pRtree->iDepth++; |
| 2623 |
pNode->isDirty = 1; |
| 2624 |
writeInt16(pNode->zData, pRtree->iDepth); |
| 2625 |
}else{ |
| 2626 |
pLeft = pNode; |
| 2627 |
pRight = nodeNew(pRtree, pLeft->pParent); |
| 2628 |
pLeft->nRef++; |
| 2629 |
} |
| 2630 |
|
| 2631 |
if( !pLeft || !pRight ){ |
| 2632 |
rc = SQLITE_NOMEM; |
| 2633 |
goto splitnode_out; |
| 2634 |
} |
| 2635 |
|
| 2636 |
memset(pLeft->zData, 0, pRtree->iNodeSize); |
| 2637 |
memset(pRight->zData, 0, pRtree->iNodeSize); |
| 2638 |
|
| 2639 |
rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight, |
| 2640 |
&leftbbox, &rightbbox); |
| 2641 |
if( rc!=SQLITE_OK ){ |
| 2642 |
goto splitnode_out; |
| 2643 |
} |
| 2644 |
|
| 2645 |
/* Ensure both child nodes have node numbers assigned to them by calling |
| 2646 |
** nodeWrite(). Node pRight always needs a node number, as it was created |
| 2647 |
** by nodeNew() above. But node pLeft sometimes already has a node number. |
| 2648 |
** In this case avoid the all to nodeWrite(). |
| 2649 |
*/ |
| 2650 |
if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)) |
| 2651 |
|| (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft))) |
| 2652 |
){ |
| 2653 |
goto splitnode_out; |
| 2654 |
} |
| 2655 |
|
| 2656 |
rightbbox.iRowid = pRight->iNode; |
| 2657 |
leftbbox.iRowid = pLeft->iNode; |
| 2658 |
|
| 2659 |
if( pNode->iNode==1 ){ |
| 2660 |
rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1); |
| 2661 |
if( rc!=SQLITE_OK ){ |
| 2662 |
goto splitnode_out; |
| 2663 |
} |
| 2664 |
}else{ |
| 2665 |
RtreeNode *pParent = pLeft->pParent; |
| 2666 |
int iCell; |
| 2667 |
rc = nodeParentIndex(pRtree, pLeft, &iCell); |
| 2668 |
if( ALWAYS(rc==SQLITE_OK) ){ |
| 2669 |
nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell); |
| 2670 |
rc = AdjustTree(pRtree, pParent, &leftbbox); |
| 2671 |
assert( rc==SQLITE_OK ); |
| 2672 |
} |
| 2673 |
if( NEVER(rc!=SQLITE_OK) ){ |
| 2674 |
goto splitnode_out; |
| 2675 |
} |
| 2676 |
} |
| 2677 |
if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){ |
| 2678 |
goto splitnode_out; |
| 2679 |
} |
| 2680 |
|
| 2681 |
for(i=0; i<NCELL(pRight); i++){ |
| 2682 |
i64 iRowid = nodeGetRowid(pRtree, pRight, i); |
| 2683 |
rc = updateMapping(pRtree, iRowid, pRight, iHeight); |
| 2684 |
if( iRowid==pCell->iRowid ){ |
| 2685 |
newCellIsRight = 1; |
| 2686 |
} |
| 2687 |
if( rc!=SQLITE_OK ){ |
| 2688 |
goto splitnode_out; |
| 2689 |
} |
| 2690 |
} |
| 2691 |
if( pNode->iNode==1 ){ |
| 2692 |
for(i=0; i<NCELL(pLeft); i++){ |
| 2693 |
i64 iRowid = nodeGetRowid(pRtree, pLeft, i); |
| 2694 |
rc = updateMapping(pRtree, iRowid, pLeft, iHeight); |
| 2695 |
if( rc!=SQLITE_OK ){ |
| 2696 |
goto splitnode_out; |
| 2697 |
} |
| 2698 |
} |
| 2699 |
}else if( newCellIsRight==0 ){ |
| 2700 |
rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight); |
| 2701 |
} |
| 2702 |
|
| 2703 |
splitnode_out: |
| 2704 |
nodeRelease(pRtree, pRight); |
| 2705 |
nodeRelease(pRtree, pLeft); |
| 2706 |
sqlite3_free(aCell); |
| 2707 |
return rc; |
| 2708 |
} |
| 2709 |
|
| 2710 |
/* |
| 2711 |
** If node pLeaf is not the root of the r-tree and its pParent pointer is |
| 2712 |
** still NULL, load all ancestor nodes of pLeaf into memory and populate |
| 2713 |
** the pLeaf->pParent chain all the way up to the root node. |
| 2714 |
** |
| 2715 |
** This operation is required when a row is deleted (or updated - an update |
| 2716 |
** is implemented as a delete followed by an insert). SQLite provides the |
| 2717 |
** rowid of the row to delete, which can be used to find the leaf on which |
| 2718 |
** the entry resides (argument pLeaf). Once the leaf is located, this |
| 2719 |
** function is called to determine its ancestry. |
| 2720 |
*/ |
| 2721 |
static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){ |
| 2722 |
int rc = SQLITE_OK; |
| 2723 |
RtreeNode *pChild = pLeaf; |
| 2724 |
while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){ |
| 2725 |
int rc2 = SQLITE_OK; /* sqlite3_reset() return code */ |
| 2726 |
sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode); |
| 2727 |
rc = sqlite3_step(pRtree->pReadParent); |
| 2728 |
if( rc==SQLITE_ROW ){ |
| 2729 |
RtreeNode *pTest; /* Used to test for reference loops */ |
| 2730 |
i64 iNode; /* Node number of parent node */ |
| 2731 |
|
| 2732 |
/* Before setting pChild->pParent, test that we are not creating a |
| 2733 |
** loop of references (as we would if, say, pChild==pParent). We don't |
| 2734 |
** want to do this as it leads to a memory leak when trying to delete |
| 2735 |
** the referenced counted node structures. |
| 2736 |
*/ |
| 2737 |
iNode = sqlite3_column_int64(pRtree->pReadParent, 0); |
| 2738 |
for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent); |
| 2739 |
if( pTest==0 ){ |
| 2740 |
rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent); |
| 2741 |
} |
| 2742 |
} |
| 2743 |
rc = sqlite3_reset(pRtree->pReadParent); |
| 2744 |
if( rc==SQLITE_OK ) rc = rc2; |
| 2745 |
if( rc==SQLITE_OK && !pChild->pParent ){ |
| 2746 |
RTREE_IS_CORRUPT(pRtree); |
| 2747 |
rc = SQLITE_CORRUPT_VTAB; |
| 2748 |
} |
| 2749 |
pChild = pChild->pParent; |
| 2750 |
} |
| 2751 |
return rc; |
| 2752 |
} |
| 2753 |
|
| 2754 |
static int deleteCell(Rtree *, RtreeNode *, int, int); |
| 2755 |
|
| 2756 |
static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){ |
| 2757 |
int rc; |
| 2758 |
int rc2; |
| 2759 |
RtreeNode *pParent = 0; |
| 2760 |
int iCell; |
| 2761 |
|
| 2762 |
assert( pNode->nRef==1 ); |
| 2763 |
|
| 2764 |
/* Remove the entry in the parent cell. */ |
| 2765 |
rc = nodeParentIndex(pRtree, pNode, &iCell); |
| 2766 |
if( rc==SQLITE_OK ){ |
| 2767 |
pParent = pNode->pParent; |
| 2768 |
pNode->pParent = 0; |
| 2769 |
rc = deleteCell(pRtree, pParent, iCell, iHeight+1); |
| 2770 |
testcase( rc!=SQLITE_OK ); |
| 2771 |
} |
| 2772 |
rc2 = nodeRelease(pRtree, pParent); |
| 2773 |
if( rc==SQLITE_OK ){ |
| 2774 |
rc = rc2; |
| 2775 |
} |
| 2776 |
if( rc!=SQLITE_OK ){ |
| 2777 |
return rc; |
| 2778 |
} |
| 2779 |
|
| 2780 |
/* Remove the xxx_node entry. */ |
| 2781 |
sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode); |
| 2782 |
sqlite3_step(pRtree->pDeleteNode); |
| 2783 |
if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){ |
| 2784 |
return rc; |
| 2785 |
} |
| 2786 |
|
| 2787 |
/* Remove the xxx_parent entry. */ |
| 2788 |
sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode); |
| 2789 |
sqlite3_step(pRtree->pDeleteParent); |
| 2790 |
if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){ |
| 2791 |
return rc; |
| 2792 |
} |
| 2793 |
|
| 2794 |
/* Remove the node from the in-memory hash table and link it into |
| 2795 |
** the Rtree.pDeleted list. Its contents will be re-inserted later on. |
| 2796 |
*/ |
| 2797 |
nodeHashDelete(pRtree, pNode); |
| 2798 |
pNode->iNode = iHeight; |
| 2799 |
pNode->pNext = pRtree->pDeleted; |
| 2800 |
pNode->nRef++; |
| 2801 |
pRtree->pDeleted = pNode; |
| 2802 |
|
| 2803 |
return SQLITE_OK; |
| 2804 |
} |
| 2805 |
|
| 2806 |
static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){ |
| 2807 |
RtreeNode *pParent = pNode->pParent; |
| 2808 |
int rc = SQLITE_OK; |
| 2809 |
if( pParent ){ |
| 2810 |
int ii; |
| 2811 |
int nCell = NCELL(pNode); |
| 2812 |
RtreeCell box; /* Bounding box for pNode */ |
| 2813 |
nodeGetCell(pRtree, pNode, 0, &box); |
| 2814 |
for(ii=1; ii<nCell; ii++){ |
| 2815 |
RtreeCell cell; |
| 2816 |
nodeGetCell(pRtree, pNode, ii, &cell); |
| 2817 |
cellUnion(pRtree, &box, &cell); |
| 2818 |
} |
| 2819 |
box.iRowid = pNode->iNode; |
| 2820 |
rc = nodeParentIndex(pRtree, pNode, &ii); |
| 2821 |
if( rc==SQLITE_OK ){ |
| 2822 |
nodeOverwriteCell(pRtree, pParent, &box, ii); |
| 2823 |
rc = fixBoundingBox(pRtree, pParent); |
| 2824 |
} |
| 2825 |
} |
| 2826 |
return rc; |
| 2827 |
} |
| 2828 |
|
| 2829 |
/* |
| 2830 |
** Delete the cell at index iCell of node pNode. After removing the |
| 2831 |
** cell, adjust the r-tree data structure if required. |
| 2832 |
*/ |
| 2833 |
static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){ |
| 2834 |
RtreeNode *pParent; |
| 2835 |
int rc; |
| 2836 |
|
| 2837 |
if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){ |
| 2838 |
return rc; |
| 2839 |
} |
| 2840 |
|
| 2841 |
/* Remove the cell from the node. This call just moves bytes around |
| 2842 |
** the in-memory node image, so it cannot fail. |
| 2843 |
*/ |
| 2844 |
nodeDeleteCell(pRtree, pNode, iCell); |
| 2845 |
|
| 2846 |
/* If the node is not the tree root and now has less than the minimum |
| 2847 |
** number of cells, remove it from the tree. Otherwise, update the |
| 2848 |
** cell in the parent node so that it tightly contains the updated |
| 2849 |
** node. |
| 2850 |
*/ |
| 2851 |
pParent = pNode->pParent; |
| 2852 |
assert( pParent || pNode->iNode==1 ); |
| 2853 |
if( pParent ){ |
| 2854 |
if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){ |
| 2855 |
rc = removeNode(pRtree, pNode, iHeight); |
| 2856 |
}else{ |
| 2857 |
rc = fixBoundingBox(pRtree, pNode); |
| 2858 |
} |
| 2859 |
} |
| 2860 |
|
| 2861 |
return rc; |
| 2862 |
} |
| 2863 |
|
| 2864 |
/* |
| 2865 |
** Insert cell pCell into node pNode. Node pNode is the head of a |
| 2866 |
** subtree iHeight high (leaf nodes have iHeight==0). |
| 2867 |
*/ |
| 2868 |
static int rtreeInsertCell( |
| 2869 |
Rtree *pRtree, |
| 2870 |
RtreeNode *pNode, |
| 2871 |
RtreeCell *pCell, |
| 2872 |
int iHeight |
| 2873 |
){ |
| 2874 |
int rc = SQLITE_OK; |
| 2875 |
if( iHeight>0 ){ |
| 2876 |
RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid); |
| 2877 |
if( pChild ){ |
| 2878 |
nodeRelease(pRtree, pChild->pParent); |
| 2879 |
nodeReference(pNode); |
| 2880 |
pChild->pParent = pNode; |
| 2881 |
} |
| 2882 |
} |
| 2883 |
if( nodeInsertCell(pRtree, pNode, pCell) ){ |
| 2884 |
rc = SplitNode(pRtree, pNode, pCell, iHeight); |
| 2885 |
}else{ |
| 2886 |
rc = AdjustTree(pRtree, pNode, pCell); |
| 2887 |
if( rc==SQLITE_OK ){ |
| 2888 |
if( iHeight==0 ){ |
| 2889 |
rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); |
| 2890 |
}else{ |
| 2891 |
rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode); |
| 2892 |
} |
| 2893 |
} |
| 2894 |
} |
| 2895 |
return rc; |
| 2896 |
} |
| 2897 |
|
| 2898 |
static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){ |
| 2899 |
int ii; |
| 2900 |
int rc = SQLITE_OK; |
| 2901 |
int nCell = NCELL(pNode); |
| 2902 |
|
| 2903 |
for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){ |
| 2904 |
RtreeNode *pInsert; |
| 2905 |
RtreeCell cell; |
| 2906 |
nodeGetCell(pRtree, pNode, ii, &cell); |
| 2907 |
|
| 2908 |
/* Find a node to store this cell in. pNode->iNode currently contains |
| 2909 |
** the height of the sub-tree headed by the cell. |
| 2910 |
*/ |
| 2911 |
rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert); |
| 2912 |
if( rc==SQLITE_OK ){ |
| 2913 |
int rc2; |
| 2914 |
rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode); |
| 2915 |
rc2 = nodeRelease(pRtree, pInsert); |
| 2916 |
if( rc==SQLITE_OK ){ |
| 2917 |
rc = rc2; |
| 2918 |
} |
| 2919 |
} |
| 2920 |
} |
| 2921 |
return rc; |
| 2922 |
} |
| 2923 |
|
| 2924 |
/* |
| 2925 |
** Select a currently unused rowid for a new r-tree record. |
| 2926 |
*/ |
| 2927 |
static int rtreeNewRowid(Rtree *pRtree, i64 *piRowid){ |
| 2928 |
int rc; |
| 2929 |
sqlite3_bind_null(pRtree->pWriteRowid, 1); |
| 2930 |
sqlite3_bind_null(pRtree->pWriteRowid, 2); |
| 2931 |
sqlite3_step(pRtree->pWriteRowid); |
| 2932 |
rc = sqlite3_reset(pRtree->pWriteRowid); |
| 2933 |
*piRowid = sqlite3_last_insert_rowid(pRtree->db); |
| 2934 |
return rc; |
| 2935 |
} |
| 2936 |
|
| 2937 |
/* |
| 2938 |
** Remove the entry with rowid=iDelete from the r-tree structure. |
| 2939 |
*/ |
| 2940 |
static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){ |
| 2941 |
int rc; /* Return code */ |
| 2942 |
RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */ |
| 2943 |
int iCell; /* Index of iDelete cell in pLeaf */ |
| 2944 |
RtreeNode *pRoot = 0; /* Root node of rtree structure */ |
| 2945 |
|
| 2946 |
|
| 2947 |
/* Obtain a reference to the root node to initialize Rtree.iDepth */ |
| 2948 |
rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
| 2949 |
|
| 2950 |
/* Obtain a reference to the leaf node that contains the entry |
| 2951 |
** about to be deleted. |
| 2952 |
*/ |
| 2953 |
if( rc==SQLITE_OK ){ |
| 2954 |
rc = findLeafNode(pRtree, iDelete, &pLeaf, 0); |
| 2955 |
} |
| 2956 |
|
| 2957 |
#ifdef CORRUPT_DB |
| 2958 |
assert( pLeaf!=0 || rc!=SQLITE_OK || CORRUPT_DB ); |
| 2959 |
#endif |
| 2960 |
|
| 2961 |
/* Delete the cell in question from the leaf node. */ |
| 2962 |
if( rc==SQLITE_OK && pLeaf ){ |
| 2963 |
int rc2; |
| 2964 |
rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell); |
| 2965 |
if( rc==SQLITE_OK ){ |
| 2966 |
rc = deleteCell(pRtree, pLeaf, iCell, 0); |
| 2967 |
} |
| 2968 |
rc2 = nodeRelease(pRtree, pLeaf); |
| 2969 |
if( rc==SQLITE_OK ){ |
| 2970 |
rc = rc2; |
| 2971 |
} |
| 2972 |
} |
| 2973 |
|
| 2974 |
/* Delete the corresponding entry in the <rtree>_rowid table. */ |
| 2975 |
if( rc==SQLITE_OK ){ |
| 2976 |
sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete); |
| 2977 |
sqlite3_step(pRtree->pDeleteRowid); |
| 2978 |
rc = sqlite3_reset(pRtree->pDeleteRowid); |
| 2979 |
} |
| 2980 |
|
| 2981 |
/* Check if the root node now has exactly one child. If so, remove |
| 2982 |
** it, schedule the contents of the child for reinsertion and |
| 2983 |
** reduce the tree height by one. |
| 2984 |
** |
| 2985 |
** This is equivalent to copying the contents of the child into |
| 2986 |
** the root node (the operation that Gutman's paper says to perform |
| 2987 |
** in this scenario). |
| 2988 |
*/ |
| 2989 |
if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){ |
| 2990 |
int rc2; |
| 2991 |
RtreeNode *pChild = 0; |
| 2992 |
i64 iChild = nodeGetRowid(pRtree, pRoot, 0); |
| 2993 |
rc = nodeAcquire(pRtree, iChild, pRoot, &pChild); /* tag-20210916a */ |
| 2994 |
if( rc==SQLITE_OK ){ |
| 2995 |
rc = removeNode(pRtree, pChild, pRtree->iDepth-1); |
| 2996 |
} |
| 2997 |
rc2 = nodeRelease(pRtree, pChild); |
| 2998 |
if( rc==SQLITE_OK ) rc = rc2; |
| 2999 |
if( rc==SQLITE_OK ){ |
| 3000 |
pRtree->iDepth--; |
| 3001 |
writeInt16(pRoot->zData, pRtree->iDepth); |
| 3002 |
pRoot->isDirty = 1; |
| 3003 |
} |
| 3004 |
} |
| 3005 |
|
| 3006 |
/* Re-insert the contents of any underfull nodes removed from the tree. */ |
| 3007 |
for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){ |
| 3008 |
if( rc==SQLITE_OK ){ |
| 3009 |
rc = reinsertNodeContent(pRtree, pLeaf); |
| 3010 |
} |
| 3011 |
pRtree->pDeleted = pLeaf->pNext; |
| 3012 |
pRtree->nNodeRef--; |
| 3013 |
sqlite3_free(pLeaf); |
| 3014 |
} |
| 3015 |
|
| 3016 |
/* Release the reference to the root node. */ |
| 3017 |
if( rc==SQLITE_OK ){ |
| 3018 |
rc = nodeRelease(pRtree, pRoot); |
| 3019 |
}else{ |
| 3020 |
nodeRelease(pRtree, pRoot); |
| 3021 |
} |
| 3022 |
|
| 3023 |
return rc; |
| 3024 |
} |
| 3025 |
|
| 3026 |
/* |
| 3027 |
** Rounding constants for float->double conversion. |
| 3028 |
*/ |
| 3029 |
#define RNDTOWARDS (1.0 - 1.0/8388608.0) /* Round towards zero */ |
| 3030 |
#define RNDAWAY (1.0 + 1.0/8388608.0) /* Round away from zero */ |
| 3031 |
|
| 3032 |
#if !defined(SQLITE_RTREE_INT_ONLY) |
| 3033 |
/* |
| 3034 |
** Convert an sqlite3_value into an RtreeValue (presumably a float) |
| 3035 |
** while taking care to round toward negative or positive, respectively. |
| 3036 |
*/ |
| 3037 |
static RtreeValue rtreeValueDown(sqlite3_value *v){ |
| 3038 |
double d = sqlite3_value_double(v); |
| 3039 |
float f = (float)d; |
| 3040 |
if( f>d ){ |
| 3041 |
f = (float)(d*(d<0 ? RNDAWAY : RNDTOWARDS)); |
| 3042 |
} |
| 3043 |
return f; |
| 3044 |
} |
| 3045 |
static RtreeValue rtreeValueUp(sqlite3_value *v){ |
| 3046 |
double d = sqlite3_value_double(v); |
| 3047 |
float f = (float)d; |
| 3048 |
if( f<d ){ |
| 3049 |
f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY)); |
| 3050 |
} |
| 3051 |
return f; |
| 3052 |
} |
| 3053 |
#endif /* !defined(SQLITE_RTREE_INT_ONLY) */ |
| 3054 |
|
| 3055 |
/* |
| 3056 |
** A constraint has failed while inserting a row into an rtree table. |
| 3057 |
** Assuming no OOM error occurs, this function sets the error message |
| 3058 |
** (at pRtree->base.zErrMsg) to an appropriate value and returns |
| 3059 |
** SQLITE_CONSTRAINT. |
| 3060 |
** |
| 3061 |
** Parameter iCol is the index of the leftmost column involved in the |
| 3062 |
** constraint failure. If it is 0, then the constraint that failed is |
| 3063 |
** the unique constraint on the id column. Otherwise, it is the rtree |
| 3064 |
** (c1<=c2) constraint on columns iCol and iCol+1 that has failed. |
| 3065 |
** |
| 3066 |
** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT. |
| 3067 |
*/ |
| 3068 |
static int rtreeConstraintError(Rtree *pRtree, int iCol){ |
| 3069 |
sqlite3_stmt *pStmt = 0; |
| 3070 |
char *zSql; |
| 3071 |
int rc; |
| 3072 |
|
| 3073 |
assert( iCol==0 || iCol%2 ); |
| 3074 |
zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree->zDb, pRtree->zName); |
| 3075 |
if( zSql ){ |
| 3076 |
rc = sqlite3_prepare_v2(pRtree->db, zSql, -1, &pStmt, 0); |
| 3077 |
}else{ |
| 3078 |
rc = SQLITE_NOMEM; |
| 3079 |
} |
| 3080 |
sqlite3_free(zSql); |
| 3081 |
|
| 3082 |
if( rc==SQLITE_OK ){ |
| 3083 |
if( iCol==0 ){ |
| 3084 |
const char *zCol = sqlite3_column_name(pStmt, 0); |
| 3085 |
pRtree->base.zErrMsg = sqlite3_mprintf( |
| 3086 |
"UNIQUE constraint failed: %s.%s", pRtree->zName, zCol |
| 3087 |
); |
| 3088 |
}else{ |
| 3089 |
const char *zCol1 = sqlite3_column_name(pStmt, iCol); |
| 3090 |
const char *zCol2 = sqlite3_column_name(pStmt, iCol+1); |
| 3091 |
pRtree->base.zErrMsg = sqlite3_mprintf( |
| 3092 |
"rtree constraint failed: %s.(%s<=%s)", pRtree->zName, zCol1, zCol2 |
| 3093 |
); |
| 3094 |
} |
| 3095 |
} |
| 3096 |
|
| 3097 |
sqlite3_finalize(pStmt); |
| 3098 |
return (rc==SQLITE_OK ? SQLITE_CONSTRAINT : rc); |
| 3099 |
} |
| 3100 |
|
| 3101 |
|
| 3102 |
|
| 3103 |
/* |
| 3104 |
** The xUpdate method for rtree module virtual tables. |
| 3105 |
*/ |
| 3106 |
static int rtreeUpdate( |
| 3107 |
sqlite3_vtab *pVtab, |
| 3108 |
int nData, |
| 3109 |
sqlite3_value **aData, |
| 3110 |
sqlite_int64 *pRowid |
| 3111 |
){ |
| 3112 |
Rtree *pRtree = (Rtree *)pVtab; |
| 3113 |
int rc = SQLITE_OK; |
| 3114 |
RtreeCell cell; /* New cell to insert if nData>1 */ |
| 3115 |
int bHaveRowid = 0; /* Set to 1 after new rowid is determined */ |
| 3116 |
|
| 3117 |
if( pRtree->nNodeRef ){ |
| 3118 |
/* Unable to write to the btree while another cursor is reading from it, |
| 3119 |
** since the write might do a rebalance which would disrupt the read |
| 3120 |
** cursor. */ |
| 3121 |
return SQLITE_LOCKED_VTAB; |
| 3122 |
} |
| 3123 |
rtreeReference(pRtree); |
| 3124 |
assert(nData>=1); |
| 3125 |
|
| 3126 |
memset(&cell, 0, sizeof(cell)); |
| 3127 |
|
| 3128 |
/* Constraint handling. A write operation on an r-tree table may return |
| 3129 |
** SQLITE_CONSTRAINT for two reasons: |
| 3130 |
** |
| 3131 |
** 1. A duplicate rowid value, or |
| 3132 |
** 2. The supplied data violates the "x2>=x1" constraint. |
| 3133 |
** |
| 3134 |
** In the first case, if the conflict-handling mode is REPLACE, then |
| 3135 |
** the conflicting row can be removed before proceeding. In the second |
| 3136 |
** case, SQLITE_CONSTRAINT must be returned regardless of the |
| 3137 |
** conflict-handling mode specified by the user. |
| 3138 |
*/ |
| 3139 |
if( nData>1 ){ |
| 3140 |
int ii; |
| 3141 |
int nn = nData - 4; |
| 3142 |
|
| 3143 |
if( nn > pRtree->nDim2 ) nn = pRtree->nDim2; |
| 3144 |
/* Populate the cell.aCoord[] array. The first coordinate is aData[3]. |
| 3145 |
** |
| 3146 |
** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared |
| 3147 |
** with "column" that are interpreted as table constraints. |
| 3148 |
** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5)); |
| 3149 |
** This problem was discovered after years of use, so we silently ignore |
| 3150 |
** these kinds of misdeclared tables to avoid breaking any legacy. |
| 3151 |
*/ |
| 3152 |
|
| 3153 |
#ifndef SQLITE_RTREE_INT_ONLY |
| 3154 |
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| 3155 |
for(ii=0; ii<nn; ii+=2){ |
| 3156 |
cell.aCoord[ii].f = rtreeValueDown(aData[ii+3]); |
| 3157 |
cell.aCoord[ii+1].f = rtreeValueUp(aData[ii+4]); |
| 3158 |
if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ |
| 3159 |
rc = rtreeConstraintError(pRtree, ii+1); |
| 3160 |
goto constraint; |
| 3161 |
} |
| 3162 |
} |
| 3163 |
}else |
| 3164 |
#endif |
| 3165 |
{ |
| 3166 |
for(ii=0; ii<nn; ii+=2){ |
| 3167 |
cell.aCoord[ii].i = sqlite3_value_int(aData[ii+3]); |
| 3168 |
cell.aCoord[ii+1].i = sqlite3_value_int(aData[ii+4]); |
| 3169 |
if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ |
| 3170 |
rc = rtreeConstraintError(pRtree, ii+1); |
| 3171 |
goto constraint; |
| 3172 |
} |
| 3173 |
} |
| 3174 |
} |
| 3175 |
|
| 3176 |
/* If a rowid value was supplied, check if it is already present in |
| 3177 |
** the table. If so, the constraint has failed. */ |
| 3178 |
if( sqlite3_value_type(aData[2])!=SQLITE_NULL ){ |
| 3179 |
cell.iRowid = sqlite3_value_int64(aData[2]); |
| 3180 |
if( sqlite3_value_type(aData[0])==SQLITE_NULL |
| 3181 |
|| sqlite3_value_int64(aData[0])!=cell.iRowid |
| 3182 |
){ |
| 3183 |
int steprc; |
| 3184 |
sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); |
| 3185 |
steprc = sqlite3_step(pRtree->pReadRowid); |
| 3186 |
rc = sqlite3_reset(pRtree->pReadRowid); |
| 3187 |
if( SQLITE_ROW==steprc ){ |
| 3188 |
if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){ |
| 3189 |
rc = rtreeDeleteRowid(pRtree, cell.iRowid); |
| 3190 |
}else{ |
| 3191 |
rc = rtreeConstraintError(pRtree, 0); |
| 3192 |
goto constraint; |
| 3193 |
} |
| 3194 |
} |
| 3195 |
} |
| 3196 |
bHaveRowid = 1; |
| 3197 |
} |
| 3198 |
} |
| 3199 |
|
| 3200 |
/* If aData[0] is not an SQL NULL value, it is the rowid of a |
| 3201 |
** record to delete from the r-tree table. The following block does |
| 3202 |
** just that. |
| 3203 |
*/ |
| 3204 |
if( sqlite3_value_type(aData[0])!=SQLITE_NULL ){ |
| 3205 |
rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0])); |
| 3206 |
} |
| 3207 |
|
| 3208 |
/* If the aData[] array contains more than one element, elements |
| 3209 |
** (aData[2]..aData[argc-1]) contain a new record to insert into |
| 3210 |
** the r-tree structure. |
| 3211 |
*/ |
| 3212 |
if( rc==SQLITE_OK && nData>1 ){ |
| 3213 |
/* Insert the new record into the r-tree */ |
| 3214 |
RtreeNode *pLeaf = 0; |
| 3215 |
|
| 3216 |
/* Figure out the rowid of the new row. */ |
| 3217 |
if( bHaveRowid==0 ){ |
| 3218 |
rc = rtreeNewRowid(pRtree, &cell.iRowid); |
| 3219 |
} |
| 3220 |
*pRowid = cell.iRowid; |
| 3221 |
|
| 3222 |
if( rc==SQLITE_OK ){ |
| 3223 |
rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf); |
| 3224 |
} |
| 3225 |
if( rc==SQLITE_OK ){ |
| 3226 |
int rc2; |
| 3227 |
rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0); |
| 3228 |
rc2 = nodeRelease(pRtree, pLeaf); |
| 3229 |
if( rc==SQLITE_OK ){ |
| 3230 |
rc = rc2; |
| 3231 |
} |
| 3232 |
} |
| 3233 |
if( rc==SQLITE_OK && pRtree->nAux ){ |
| 3234 |
sqlite3_stmt *pUp = pRtree->pWriteAux; |
| 3235 |
int jj; |
| 3236 |
sqlite3_bind_int64(pUp, 1, *pRowid); |
| 3237 |
for(jj=0; jj<pRtree->nAux; jj++){ |
| 3238 |
sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]); |
| 3239 |
} |
| 3240 |
sqlite3_step(pUp); |
| 3241 |
rc = sqlite3_reset(pUp); |
| 3242 |
} |
| 3243 |
} |
| 3244 |
|
| 3245 |
constraint: |
| 3246 |
rtreeRelease(pRtree); |
| 3247 |
return rc; |
| 3248 |
} |
| 3249 |
|
| 3250 |
/* |
| 3251 |
** Called when a transaction starts. |
| 3252 |
*/ |
| 3253 |
static int rtreeBeginTransaction(sqlite3_vtab *pVtab){ |
| 3254 |
Rtree *pRtree = (Rtree *)pVtab; |
| 3255 |
assert( pRtree->inWrTrans==0 ); |
| 3256 |
pRtree->inWrTrans = 1; |
| 3257 |
return SQLITE_OK; |
| 3258 |
} |
| 3259 |
|
| 3260 |
/* |
| 3261 |
** Called when a transaction completes (either by COMMIT or ROLLBACK). |
| 3262 |
** The sqlite3_blob object should be released at this point. |
| 3263 |
*/ |
| 3264 |
static int rtreeEndTransaction(sqlite3_vtab *pVtab){ |
| 3265 |
Rtree *pRtree = (Rtree *)pVtab; |
| 3266 |
pRtree->inWrTrans = 0; |
| 3267 |
nodeBlobReset(pRtree); |
| 3268 |
return SQLITE_OK; |
| 3269 |
} |
| 3270 |
static int rtreeRollback(sqlite3_vtab *pVtab){ |
| 3271 |
return rtreeEndTransaction(pVtab); |
| 3272 |
} |
| 3273 |
|
| 3274 |
/* |
| 3275 |
** The xRename method for rtree module virtual tables. |
| 3276 |
*/ |
| 3277 |
static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){ |
| 3278 |
Rtree *pRtree = (Rtree *)pVtab; |
| 3279 |
int rc = SQLITE_NOMEM; |
| 3280 |
char *zSql = sqlite3_mprintf( |
| 3281 |
"ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";" |
| 3282 |
"ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";" |
| 3283 |
"ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";" |
| 3284 |
, pRtree->zDb, pRtree->zName, zNewName |
| 3285 |
, pRtree->zDb, pRtree->zName, zNewName |
| 3286 |
, pRtree->zDb, pRtree->zName, zNewName |
| 3287 |
); |
| 3288 |
if( zSql ){ |
| 3289 |
nodeBlobReset(pRtree); |
| 3290 |
rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); |
| 3291 |
sqlite3_free(zSql); |
| 3292 |
} |
| 3293 |
return rc; |
| 3294 |
} |
| 3295 |
|
| 3296 |
/* |
| 3297 |
** The xSavepoint method. |
| 3298 |
** |
| 3299 |
** This module does not need to do anything to support savepoints. However, |
| 3300 |
** it uses this hook to close any open blob handle. This is done because a |
| 3301 |
** DROP TABLE command - which fortunately always opens a savepoint - cannot |
| 3302 |
** succeed if there are any open blob handles. i.e. if the blob handle were |
| 3303 |
** not closed here, the following would fail: |
| 3304 |
** |
| 3305 |
** BEGIN; |
| 3306 |
** INSERT INTO rtree... |
| 3307 |
** DROP TABLE <tablename>; -- Would fail with SQLITE_LOCKED |
| 3308 |
** COMMIT; |
| 3309 |
*/ |
| 3310 |
static int rtreeSavepoint(sqlite3_vtab *pVtab, int iSavepoint){ |
| 3311 |
Rtree *pRtree = (Rtree *)pVtab; |
| 3312 |
u8 iwt = pRtree->inWrTrans; |
| 3313 |
UNUSED_PARAMETER(iSavepoint); |
| 3314 |
pRtree->inWrTrans = 0; |
| 3315 |
nodeBlobReset(pRtree); |
| 3316 |
pRtree->inWrTrans = iwt; |
| 3317 |
return SQLITE_OK; |
| 3318 |
} |
| 3319 |
|
| 3320 |
/* |
| 3321 |
** This function populates the pRtree->nRowEst variable with an estimate |
| 3322 |
** of the number of rows in the virtual table. If possible, this is based |
| 3323 |
** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST. |
| 3324 |
*/ |
| 3325 |
static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){ |
| 3326 |
const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'"; |
| 3327 |
char *zSql; |
| 3328 |
sqlite3_stmt *p; |
| 3329 |
int rc; |
| 3330 |
i64 nRow = RTREE_MIN_ROWEST; |
| 3331 |
|
| 3332 |
rc = sqlite3_table_column_metadata( |
| 3333 |
db, pRtree->zDb, "sqlite_stat1",0,0,0,0,0,0 |
| 3334 |
); |
| 3335 |
if( rc!=SQLITE_OK ){ |
| 3336 |
pRtree->nRowEst = RTREE_DEFAULT_ROWEST; |
| 3337 |
return rc==SQLITE_ERROR ? SQLITE_OK : rc; |
| 3338 |
} |
| 3339 |
zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName); |
| 3340 |
if( zSql==0 ){ |
| 3341 |
rc = SQLITE_NOMEM; |
| 3342 |
}else{ |
| 3343 |
rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0); |
| 3344 |
if( rc==SQLITE_OK ){ |
| 3345 |
if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0); |
| 3346 |
rc = sqlite3_finalize(p); |
| 3347 |
} |
| 3348 |
sqlite3_free(zSql); |
| 3349 |
} |
| 3350 |
pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST); |
| 3351 |
return rc; |
| 3352 |
} |
| 3353 |
|
| 3354 |
|
| 3355 |
/* |
| 3356 |
** Return true if zName is the extension on one of the shadow tables used |
| 3357 |
** by this module. |
| 3358 |
*/ |
| 3359 |
static int rtreeShadowName(const char *zName){ |
| 3360 |
static const char *azName[] = { |
| 3361 |
"node", "parent", "rowid" |
| 3362 |
}; |
| 3363 |
unsigned int i; |
| 3364 |
for(i=0; i<sizeof(azName)/sizeof(azName[0]); i++){ |
| 3365 |
if( sqlite3_stricmp(zName, azName[i])==0 ) return 1; |
| 3366 |
} |
| 3367 |
return 0; |
| 3368 |
} |
| 3369 |
|
| 3370 |
/* Forward declaration */ |
| 3371 |
static int rtreeIntegrity(sqlite3_vtab*, const char*, const char*, int, char**); |
| 3372 |
|
| 3373 |
static sqlite3_module rtreeModule = { |
| 3374 |
4, /* iVersion */ |
| 3375 |
rtreeCreate, /* xCreate - create a table */ |
| 3376 |
rtreeConnect, /* xConnect - connect to an existing table */ |
| 3377 |
rtreeBestIndex, /* xBestIndex - Determine search strategy */ |
| 3378 |
rtreeDisconnect, /* xDisconnect - Disconnect from a table */ |
| 3379 |
rtreeDestroy, /* xDestroy - Drop a table */ |
| 3380 |
rtreeOpen, /* xOpen - open a cursor */ |
| 3381 |
rtreeClose, /* xClose - close a cursor */ |
| 3382 |
rtreeFilter, /* xFilter - configure scan constraints */ |
| 3383 |
rtreeNext, /* xNext - advance a cursor */ |
| 3384 |
rtreeEof, /* xEof */ |
| 3385 |
rtreeColumn, /* xColumn - read data */ |
| 3386 |
rtreeRowid, /* xRowid - read data */ |
| 3387 |
rtreeUpdate, /* xUpdate - write data */ |
| 3388 |
rtreeBeginTransaction, /* xBegin - begin transaction */ |
| 3389 |
rtreeEndTransaction, /* xSync - sync transaction */ |
| 3390 |
rtreeEndTransaction, /* xCommit - commit transaction */ |
| 3391 |
rtreeRollback, /* xRollback - rollback transaction */ |
| 3392 |
0, /* xFindFunction - function overloading */ |
| 3393 |
rtreeRename, /* xRename - rename the table */ |
| 3394 |
rtreeSavepoint, /* xSavepoint */ |
| 3395 |
0, /* xRelease */ |
| 3396 |
0, /* xRollbackTo */ |
| 3397 |
rtreeShadowName, /* xShadowName */ |
| 3398 |
rtreeIntegrity /* xIntegrity */ |
| 3399 |
}; |
| 3400 |
|
| 3401 |
static int rtreeSqlInit( |
| 3402 |
Rtree *pRtree, |
| 3403 |
sqlite3 *db, |
| 3404 |
const char *zDb, |
| 3405 |
const char *zPrefix, |
| 3406 |
int isCreate |
| 3407 |
){ |
| 3408 |
int rc = SQLITE_OK; |
| 3409 |
|
| 3410 |
#define N_STATEMENT 8 |
| 3411 |
static const char *azSql[N_STATEMENT] = { |
| 3412 |
/* Write the xxx_node table */ |
| 3413 |
"INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(?1, ?2)", |
| 3414 |
"DELETE FROM '%q'.'%q_node' WHERE nodeno = ?1", |
| 3415 |
|
| 3416 |
/* Read and write the xxx_rowid table */ |
| 3417 |
"SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = ?1", |
| 3418 |
"INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(?1, ?2)", |
| 3419 |
"DELETE FROM '%q'.'%q_rowid' WHERE rowid = ?1", |
| 3420 |
|
| 3421 |
/* Read and write the xxx_parent table */ |
| 3422 |
"SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = ?1", |
| 3423 |
"INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(?1, ?2)", |
| 3424 |
"DELETE FROM '%q'.'%q_parent' WHERE nodeno = ?1" |
| 3425 |
}; |
| 3426 |
sqlite3_stmt **appStmt[N_STATEMENT]; |
| 3427 |
int i; |
| 3428 |
const int f = SQLITE_PREPARE_PERSISTENT|SQLITE_PREPARE_NO_VTAB; |
| 3429 |
|
| 3430 |
pRtree->db = db; |
| 3431 |
|
| 3432 |
if( isCreate ){ |
| 3433 |
char *zCreate; |
| 3434 |
sqlite3_str *p = sqlite3_str_new(db); |
| 3435 |
int ii; |
| 3436 |
sqlite3_str_appendf(p, |
| 3437 |
"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY,nodeno", |
| 3438 |
zDb, zPrefix); |
| 3439 |
for(ii=0; ii<pRtree->nAux; ii++){ |
| 3440 |
sqlite3_str_appendf(p,",a%d",ii); |
| 3441 |
} |
| 3442 |
sqlite3_str_appendf(p, |
| 3443 |
");CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY,data);", |
| 3444 |
zDb, zPrefix); |
| 3445 |
sqlite3_str_appendf(p, |
| 3446 |
"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,parentnode);", |
| 3447 |
zDb, zPrefix); |
| 3448 |
sqlite3_str_appendf(p, |
| 3449 |
"INSERT INTO \"%w\".\"%w_node\"VALUES(1,zeroblob(%d))", |
| 3450 |
zDb, zPrefix, pRtree->iNodeSize); |
| 3451 |
zCreate = sqlite3_str_finish(p); |
| 3452 |
if( !zCreate ){ |
| 3453 |
return SQLITE_NOMEM; |
| 3454 |
} |
| 3455 |
rc = sqlite3_exec(db, zCreate, 0, 0, 0); |
| 3456 |
sqlite3_free(zCreate); |
| 3457 |
if( rc!=SQLITE_OK ){ |
| 3458 |
return rc; |
| 3459 |
} |
| 3460 |
} |
| 3461 |
|
| 3462 |
appStmt[0] = &pRtree->pWriteNode; |
| 3463 |
appStmt[1] = &pRtree->pDeleteNode; |
| 3464 |
appStmt[2] = &pRtree->pReadRowid; |
| 3465 |
appStmt[3] = &pRtree->pWriteRowid; |
| 3466 |
appStmt[4] = &pRtree->pDeleteRowid; |
| 3467 |
appStmt[5] = &pRtree->pReadParent; |
| 3468 |
appStmt[6] = &pRtree->pWriteParent; |
| 3469 |
appStmt[7] = &pRtree->pDeleteParent; |
| 3470 |
|
| 3471 |
rc = rtreeQueryStat1(db, pRtree); |
| 3472 |
for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){ |
| 3473 |
char *zSql; |
| 3474 |
const char *zFormat; |
| 3475 |
if( i!=3 || pRtree->nAux==0 ){ |
| 3476 |
zFormat = azSql[i]; |
| 3477 |
}else { |
| 3478 |
/* An UPSERT is very slightly slower than REPLACE, but it is needed |
| 3479 |
** if there are auxiliary columns */ |
| 3480 |
zFormat = "INSERT INTO\"%w\".\"%w_rowid\"(rowid,nodeno)VALUES(?1,?2)" |
| 3481 |
"ON CONFLICT(rowid)DO UPDATE SET nodeno=excluded.nodeno"; |
| 3482 |
} |
| 3483 |
zSql = sqlite3_mprintf(zFormat, zDb, zPrefix); |
| 3484 |
if( zSql ){ |
| 3485 |
rc = sqlite3_prepare_v3(db, zSql, -1, f, appStmt[i], 0); |
| 3486 |
}else{ |
| 3487 |
rc = SQLITE_NOMEM; |
| 3488 |
} |
| 3489 |
sqlite3_free(zSql); |
| 3490 |
} |
| 3491 |
if( pRtree->nAux && rc!=SQLITE_NOMEM ){ |
| 3492 |
pRtree->zReadAuxSql = sqlite3_mprintf( |
| 3493 |
"SELECT * FROM \"%w\".\"%w_rowid\" WHERE rowid=?1", |
| 3494 |
zDb, zPrefix); |
| 3495 |
if( pRtree->zReadAuxSql==0 ){ |
| 3496 |
rc = SQLITE_NOMEM; |
| 3497 |
}else{ |
| 3498 |
sqlite3_str *p = sqlite3_str_new(db); |
| 3499 |
int ii; |
| 3500 |
char *zSql; |
| 3501 |
sqlite3_str_appendf(p, "UPDATE \"%w\".\"%w_rowid\"SET ", zDb, zPrefix); |
| 3502 |
for(ii=0; ii<pRtree->nAux; ii++){ |
| 3503 |
if( ii ) sqlite3_str_append(p, ",", 1); |
| 3504 |
#ifdef SQLITE_ENABLE_GEOPOLY |
| 3505 |
if( ii<pRtree->nAuxNotNull ){ |
| 3506 |
sqlite3_str_appendf(p,"a%d=coalesce(?%d,a%d)",ii,ii+2,ii); |
| 3507 |
}else |
| 3508 |
#endif |
| 3509 |
{ |
| 3510 |
sqlite3_str_appendf(p,"a%d=?%d",ii,ii+2); |
| 3511 |
} |
| 3512 |
} |
| 3513 |
sqlite3_str_appendf(p, " WHERE rowid=?1"); |
| 3514 |
zSql = sqlite3_str_finish(p); |
| 3515 |
if( zSql==0 ){ |
| 3516 |
rc = SQLITE_NOMEM; |
| 3517 |
}else{ |
| 3518 |
rc = sqlite3_prepare_v3(db, zSql, -1, f, &pRtree->pWriteAux, 0); |
| 3519 |
sqlite3_free(zSql); |
| 3520 |
} |
| 3521 |
} |
| 3522 |
} |
| 3523 |
|
| 3524 |
return rc; |
| 3525 |
} |
| 3526 |
|
| 3527 |
/* |
| 3528 |
** The second argument to this function contains the text of an SQL statement |
| 3529 |
** that returns a single integer value. The statement is compiled and executed |
| 3530 |
** using database connection db. If successful, the integer value returned |
| 3531 |
** is written to *piVal and SQLITE_OK returned. Otherwise, an SQLite error |
| 3532 |
** code is returned and the value of *piVal after returning is not defined. |
| 3533 |
*/ |
| 3534 |
static int getIntFromStmt(sqlite3 *db, const char *zSql, int *piVal){ |
| 3535 |
int rc = SQLITE_NOMEM; |
| 3536 |
if( zSql ){ |
| 3537 |
sqlite3_stmt *pStmt = 0; |
| 3538 |
rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
| 3539 |
if( rc==SQLITE_OK ){ |
| 3540 |
if( SQLITE_ROW==sqlite3_step(pStmt) ){ |
| 3541 |
*piVal = sqlite3_column_int(pStmt, 0); |
| 3542 |
} |
| 3543 |
rc = sqlite3_finalize(pStmt); |
| 3544 |
} |
| 3545 |
} |
| 3546 |
return rc; |
| 3547 |
} |
| 3548 |
|
| 3549 |
/* |
| 3550 |
** This function is called from within the xConnect() or xCreate() method to |
| 3551 |
** determine the node-size used by the rtree table being created or connected |
| 3552 |
** to. If successful, pRtree->iNodeSize is populated and SQLITE_OK returned. |
| 3553 |
** Otherwise, an SQLite error code is returned. |
| 3554 |
** |
| 3555 |
** If this function is being called as part of an xConnect(), then the rtree |
| 3556 |
** table already exists. In this case the node-size is determined by inspecting |
| 3557 |
** the root node of the tree. |
| 3558 |
** |
| 3559 |
** Otherwise, for an xCreate(), use 64 bytes less than the database page-size. |
| 3560 |
** This ensures that each node is stored on a single database page. If the |
| 3561 |
** database page-size is so large that more than RTREE_MAXCELLS entries |
| 3562 |
** would fit in a single node, use a smaller node-size. |
| 3563 |
*/ |
| 3564 |
static int getNodeSize( |
| 3565 |
sqlite3 *db, /* Database handle */ |
| 3566 |
Rtree *pRtree, /* Rtree handle */ |
| 3567 |
int isCreate, /* True for xCreate, false for xConnect */ |
| 3568 |
char **pzErr /* OUT: Error message, if any */ |
| 3569 |
){ |
| 3570 |
int rc; |
| 3571 |
char *zSql; |
| 3572 |
if( isCreate ){ |
| 3573 |
int iPageSize = 0; |
| 3574 |
zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb); |
| 3575 |
rc = getIntFromStmt(db, zSql, &iPageSize); |
| 3576 |
if( rc==SQLITE_OK ){ |
| 3577 |
pRtree->iNodeSize = iPageSize-64; |
| 3578 |
if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){ |
| 3579 |
pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS; |
| 3580 |
} |
| 3581 |
}else{ |
| 3582 |
*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); |
| 3583 |
} |
| 3584 |
}else{ |
| 3585 |
zSql = sqlite3_mprintf( |
| 3586 |
"SELECT length(data) FROM '%q'.'%q_node' WHERE nodeno = 1", |
| 3587 |
pRtree->zDb, pRtree->zName |
| 3588 |
); |
| 3589 |
rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize); |
| 3590 |
if( rc!=SQLITE_OK ){ |
| 3591 |
*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); |
| 3592 |
}else if( pRtree->iNodeSize<(512-64) ){ |
| 3593 |
rc = SQLITE_CORRUPT_VTAB; |
| 3594 |
RTREE_IS_CORRUPT(pRtree); |
| 3595 |
*pzErr = sqlite3_mprintf("undersize RTree blobs in \"%q_node\"", |
| 3596 |
pRtree->zName); |
| 3597 |
} |
| 3598 |
} |
| 3599 |
|
| 3600 |
sqlite3_free(zSql); |
| 3601 |
return rc; |
| 3602 |
} |
| 3603 |
|
| 3604 |
/* |
| 3605 |
** Return the length of a token |
| 3606 |
*/ |
| 3607 |
static int rtreeTokenLength(const char *z){ |
| 3608 |
int dummy = 0; |
| 3609 |
return sqlite3GetToken((const unsigned char*)z,&dummy); |
| 3610 |
} |
| 3611 |
|
| 3612 |
/* |
| 3613 |
** This function is the implementation of both the xConnect and xCreate |
| 3614 |
** methods of the r-tree virtual table. |
| 3615 |
** |
| 3616 |
** argv[0] -> module name |
| 3617 |
** argv[1] -> database name |
| 3618 |
** argv[2] -> table name |
| 3619 |
** argv[...] -> column names... |
| 3620 |
*/ |
| 3621 |
static int rtreeInit( |
| 3622 |
sqlite3 *db, /* Database connection */ |
| 3623 |
void *pAux, /* One of the RTREE_COORD_* constants */ |
| 3624 |
int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ |
| 3625 |
sqlite3_vtab **ppVtab, /* OUT: New virtual table */ |
| 3626 |
char **pzErr, /* OUT: Error message, if any */ |
| 3627 |
int isCreate /* True for xCreate, false for xConnect */ |
| 3628 |
){ |
| 3629 |
int rc = SQLITE_OK; |
| 3630 |
Rtree *pRtree; |
| 3631 |
int nDb; /* Length of string argv[1] */ |
| 3632 |
int nName; /* Length of string argv[2] */ |
| 3633 |
int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32); |
| 3634 |
sqlite3_str *pSql; |
| 3635 |
char *zSql; |
| 3636 |
int ii = 4; |
| 3637 |
int iErr; |
| 3638 |
|
| 3639 |
const char *aErrMsg[] = { |
| 3640 |
0, /* 0 */ |
| 3641 |
"Wrong number of columns for an rtree table", /* 1 */ |
| 3642 |
"Too few columns for an rtree table", /* 2 */ |
| 3643 |
"Too many columns for an rtree table", /* 3 */ |
| 3644 |
"Auxiliary rtree columns must be last" /* 4 */ |
| 3645 |
}; |
| 3646 |
|
| 3647 |
assert( RTREE_MAX_AUX_COLUMN<256 ); |
| 3648 |
if( argc<6 || argc>RTREE_MAX_AUX_COLUMN+3 ){ |
| 3649 |
*pzErr = sqlite3_mprintf("%s", aErrMsg[2 + (argc>=6)]); |
| 3650 |
return SQLITE_ERROR; |
| 3651 |
} |
| 3652 |
|
| 3653 |
sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1); |
| 3654 |
sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS); |
| 3655 |
|
| 3656 |
|
| 3657 |
/* Allocate the sqlite3_vtab structure */ |
| 3658 |
nDb = (int)strlen(argv[1]); |
| 3659 |
nName = (int)strlen(argv[2]); |
| 3660 |
pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName*2+8); |
| 3661 |
if( !pRtree ){ |
| 3662 |
return SQLITE_NOMEM; |
| 3663 |
} |
| 3664 |
memset(pRtree, 0, sizeof(Rtree)+nDb+nName*2+8); |
| 3665 |
pRtree->nBusy = 1; |
| 3666 |
pRtree->base.pModule = &rtreeModule; |
| 3667 |
pRtree->zDb = (char *)&pRtree[1]; |
| 3668 |
pRtree->zName = &pRtree->zDb[nDb+1]; |
| 3669 |
pRtree->zNodeName = &pRtree->zName[nName+1]; |
| 3670 |
pRtree->eCoordType = (u8)eCoordType; |
| 3671 |
memcpy(pRtree->zDb, argv[1], nDb); |
| 3672 |
memcpy(pRtree->zName, argv[2], nName); |
| 3673 |
memcpy(pRtree->zNodeName, argv[2], nName); |
| 3674 |
memcpy(&pRtree->zNodeName[nName], "_node", 6); |
| 3675 |
|
| 3676 |
|
| 3677 |
/* Create/Connect to the underlying relational database schema. If |
| 3678 |
** that is successful, call sqlite3_declare_vtab() to configure |
| 3679 |
** the r-tree table schema. |
| 3680 |
*/ |
| 3681 |
pSql = sqlite3_str_new(db); |
| 3682 |
sqlite3_str_appendf(pSql, "CREATE TABLE x(%.*s INT", |
| 3683 |
rtreeTokenLength(argv[3]), argv[3]); |
| 3684 |
for(ii=4; ii<argc; ii++){ |
| 3685 |
const char *zArg = argv[ii]; |
| 3686 |
if( zArg[0]=='+' ){ |
| 3687 |
pRtree->nAux++; |
| 3688 |
sqlite3_str_appendf(pSql, ",%.*s", rtreeTokenLength(zArg+1), zArg+1); |
| 3689 |
}else if( pRtree->nAux>0 ){ |
| 3690 |
break; |
| 3691 |
}else{ |
| 3692 |
static const char *azFormat[] = {",%.*s REAL", ",%.*s INT"}; |
| 3693 |
pRtree->nDim2++; |
| 3694 |
sqlite3_str_appendf(pSql, azFormat[eCoordType], |
| 3695 |
rtreeTokenLength(zArg), zArg); |
| 3696 |
} |
| 3697 |
} |
| 3698 |
sqlite3_str_appendf(pSql, ");"); |
| 3699 |
zSql = sqlite3_str_finish(pSql); |
| 3700 |
if( !zSql ){ |
| 3701 |
rc = SQLITE_NOMEM; |
| 3702 |
}else if( ii<argc ){ |
| 3703 |
*pzErr = sqlite3_mprintf("%s", aErrMsg[4]); |
| 3704 |
rc = SQLITE_ERROR; |
| 3705 |
}else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){ |
| 3706 |
*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); |
| 3707 |
} |
| 3708 |
sqlite3_free(zSql); |
| 3709 |
if( rc ) goto rtreeInit_fail; |
| 3710 |
pRtree->nDim = pRtree->nDim2/2; |
| 3711 |
if( pRtree->nDim<1 ){ |
| 3712 |
iErr = 2; |
| 3713 |
}else if( pRtree->nDim2>RTREE_MAX_DIMENSIONS*2 ){ |
| 3714 |
iErr = 3; |
| 3715 |
}else if( pRtree->nDim2 % 2 ){ |
| 3716 |
iErr = 1; |
| 3717 |
}else{ |
| 3718 |
iErr = 0; |
| 3719 |
} |
| 3720 |
if( iErr ){ |
| 3721 |
*pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]); |
| 3722 |
goto rtreeInit_fail; |
| 3723 |
} |
| 3724 |
pRtree->nBytesPerCell = 8 + pRtree->nDim2*4; |
| 3725 |
|
| 3726 |
/* Figure out the node size to use. */ |
| 3727 |
rc = getNodeSize(db, pRtree, isCreate, pzErr); |
| 3728 |
if( rc ) goto rtreeInit_fail; |
| 3729 |
rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate); |
| 3730 |
if( rc ){ |
| 3731 |
*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); |
| 3732 |
goto rtreeInit_fail; |
| 3733 |
} |
| 3734 |
|
| 3735 |
*ppVtab = (sqlite3_vtab *)pRtree; |
| 3736 |
return SQLITE_OK; |
| 3737 |
|
| 3738 |
rtreeInit_fail: |
| 3739 |
if( rc==SQLITE_OK ) rc = SQLITE_ERROR; |
| 3740 |
assert( *ppVtab==0 ); |
| 3741 |
assert( pRtree->nBusy==1 ); |
| 3742 |
rtreeRelease(pRtree); |
| 3743 |
return rc; |
| 3744 |
} |
| 3745 |
|
| 3746 |
|
| 3747 |
/* |
| 3748 |
** Implementation of a scalar function that decodes r-tree nodes to |
| 3749 |
** human readable strings. This can be used for debugging and analysis. |
| 3750 |
** |
| 3751 |
** The scalar function takes two arguments: (1) the number of dimensions |
| 3752 |
** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing |
| 3753 |
** an r-tree node. For a two-dimensional r-tree structure called "rt", to |
| 3754 |
** deserialize all nodes, a statement like: |
| 3755 |
** |
| 3756 |
** SELECT rtreenode(2, data) FROM rt_node; |
| 3757 |
** |
| 3758 |
** The human readable string takes the form of a Tcl list with one |
| 3759 |
** entry for each cell in the r-tree node. Each entry is itself a |
| 3760 |
** list, containing the 8-byte rowid/pageno followed by the |
| 3761 |
** <num-dimension>*2 coordinates. |
| 3762 |
*/ |
| 3763 |
static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ |
| 3764 |
RtreeNode node; |
| 3765 |
Rtree tree; |
| 3766 |
int ii; |
| 3767 |
int nData; |
| 3768 |
int errCode; |
| 3769 |
sqlite3_str *pOut; |
| 3770 |
|
| 3771 |
UNUSED_PARAMETER(nArg); |
| 3772 |
memset(&node, 0, sizeof(RtreeNode)); |
| 3773 |
memset(&tree, 0, sizeof(Rtree)); |
| 3774 |
tree.nDim = (u8)sqlite3_value_int(apArg[0]); |
| 3775 |
if( tree.nDim<1 || tree.nDim>5 ) return; |
| 3776 |
tree.nDim2 = tree.nDim*2; |
| 3777 |
tree.nBytesPerCell = 8 + 8 * tree.nDim; |
| 3778 |
node.zData = (u8 *)sqlite3_value_blob(apArg[1]); |
| 3779 |
if( node.zData==0 ) return; |
| 3780 |
nData = sqlite3_value_bytes(apArg[1]); |
| 3781 |
if( nData<4 ) return; |
| 3782 |
if( nData<4+NCELL(&node)*tree.nBytesPerCell ) return; |
| 3783 |
|
| 3784 |
pOut = sqlite3_str_new(0); |
| 3785 |
for(ii=0; ii<NCELL(&node); ii++){ |
| 3786 |
RtreeCell cell; |
| 3787 |
int jj; |
| 3788 |
|
| 3789 |
nodeGetCell(&tree, &node, ii, &cell); |
| 3790 |
if( ii>0 ) sqlite3_str_append(pOut, " ", 1); |
| 3791 |
sqlite3_str_appendf(pOut, "{%lld", cell.iRowid); |
| 3792 |
for(jj=0; jj<tree.nDim2; jj++){ |
| 3793 |
#ifndef SQLITE_RTREE_INT_ONLY |
| 3794 |
sqlite3_str_appendf(pOut, " %g", (double)cell.aCoord[jj].f); |
| 3795 |
#else |
| 3796 |
sqlite3_str_appendf(pOut, " %d", cell.aCoord[jj].i); |
| 3797 |
#endif |
| 3798 |
} |
| 3799 |
sqlite3_str_append(pOut, "}", 1); |
| 3800 |
} |
| 3801 |
errCode = sqlite3_str_errcode(pOut); |
| 3802 |
sqlite3_result_error_code(ctx, errCode); |
| 3803 |
sqlite3_result_text(ctx, sqlite3_str_finish(pOut), -1, sqlite3_free); |
| 3804 |
} |
| 3805 |
|
| 3806 |
/* This routine implements an SQL function that returns the "depth" parameter |
| 3807 |
** from the front of a blob that is an r-tree node. For example: |
| 3808 |
** |
| 3809 |
** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1; |
| 3810 |
** |
| 3811 |
** The depth value is 0 for all nodes other than the root node, and the root |
| 3812 |
** node always has nodeno=1, so the example above is the primary use for this |
| 3813 |
** routine. This routine is intended for testing and analysis only. |
| 3814 |
*/ |
| 3815 |
static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ |
| 3816 |
UNUSED_PARAMETER(nArg); |
| 3817 |
if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB |
| 3818 |
|| sqlite3_value_bytes(apArg[0])<2 |
| 3819 |
|
| 3820 |
){ |
| 3821 |
sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); |
| 3822 |
}else{ |
| 3823 |
u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]); |
| 3824 |
if( zBlob ){ |
| 3825 |
sqlite3_result_int(ctx, readInt16(zBlob)); |
| 3826 |
}else{ |
| 3827 |
sqlite3_result_error_nomem(ctx); |
| 3828 |
} |
| 3829 |
} |
| 3830 |
} |
| 3831 |
|
| 3832 |
/* |
| 3833 |
** Context object passed between the various routines that make up the |
| 3834 |
** implementation of integrity-check function rtreecheck(). |
| 3835 |
*/ |
| 3836 |
typedef struct RtreeCheck RtreeCheck; |
| 3837 |
struct RtreeCheck { |
| 3838 |
sqlite3 *db; /* Database handle */ |
| 3839 |
const char *zDb; /* Database containing rtree table */ |
| 3840 |
const char *zTab; /* Name of rtree table */ |
| 3841 |
int bInt; /* True for rtree_i32 table */ |
| 3842 |
int nDim; /* Number of dimensions for this rtree tbl */ |
| 3843 |
sqlite3_stmt *pGetNode; /* Statement used to retrieve nodes */ |
| 3844 |
sqlite3_stmt *aCheckMapping[2]; /* Statements to query %_parent/%_rowid */ |
| 3845 |
int nLeaf; /* Number of leaf cells in table */ |
| 3846 |
int nNonLeaf; /* Number of non-leaf cells in table */ |
| 3847 |
int rc; /* Return code */ |
| 3848 |
char *zReport; /* Message to report */ |
| 3849 |
int nErr; /* Number of lines in zReport */ |
| 3850 |
}; |
| 3851 |
|
| 3852 |
#define RTREE_CHECK_MAX_ERROR 100 |
| 3853 |
|
| 3854 |
/* |
| 3855 |
** Reset SQL statement pStmt. If the sqlite3_reset() call returns an error, |
| 3856 |
** and RtreeCheck.rc==SQLITE_OK, set RtreeCheck.rc to the error code. |
| 3857 |
*/ |
| 3858 |
static void rtreeCheckReset(RtreeCheck *pCheck, sqlite3_stmt *pStmt){ |
| 3859 |
int rc = sqlite3_reset(pStmt); |
| 3860 |
if( pCheck->rc==SQLITE_OK ) pCheck->rc = rc; |
| 3861 |
} |
| 3862 |
|
| 3863 |
/* |
| 3864 |
** The second and subsequent arguments to this function are a format string |
| 3865 |
** and printf style arguments. This function formats the string and attempts |
| 3866 |
** to compile it as an SQL statement. |
| 3867 |
** |
| 3868 |
** If successful, a pointer to the new SQL statement is returned. Otherwise, |
| 3869 |
** NULL is returned and an error code left in RtreeCheck.rc. |
| 3870 |
*/ |
| 3871 |
static sqlite3_stmt *rtreeCheckPrepare( |
| 3872 |
RtreeCheck *pCheck, /* RtreeCheck object */ |
| 3873 |
const char *zFmt, ... /* Format string and trailing args */ |
| 3874 |
){ |
| 3875 |
va_list ap; |
| 3876 |
char *z; |
| 3877 |
sqlite3_stmt *pRet = 0; |
| 3878 |
|
| 3879 |
va_start(ap, zFmt); |
| 3880 |
z = sqlite3_vmprintf(zFmt, ap); |
| 3881 |
|
| 3882 |
if( pCheck->rc==SQLITE_OK ){ |
| 3883 |
if( z==0 ){ |
| 3884 |
pCheck->rc = SQLITE_NOMEM; |
| 3885 |
}else{ |
| 3886 |
pCheck->rc = sqlite3_prepare_v2(pCheck->db, z, -1, &pRet, 0); |
| 3887 |
} |
| 3888 |
} |
| 3889 |
|
| 3890 |
sqlite3_free(z); |
| 3891 |
va_end(ap); |
| 3892 |
return pRet; |
| 3893 |
} |
| 3894 |
|
| 3895 |
/* |
| 3896 |
** The second and subsequent arguments to this function are a printf() |
| 3897 |
** style format string and arguments. This function formats the string and |
| 3898 |
** appends it to the report being accumulated in pCheck. |
| 3899 |
*/ |
| 3900 |
static void rtreeCheckAppendMsg(RtreeCheck *pCheck, const char *zFmt, ...){ |
| 3901 |
va_list ap; |
| 3902 |
va_start(ap, zFmt); |
| 3903 |
if( pCheck->rc==SQLITE_OK && pCheck->nErr<RTREE_CHECK_MAX_ERROR ){ |
| 3904 |
char *z = sqlite3_vmprintf(zFmt, ap); |
| 3905 |
if( z==0 ){ |
| 3906 |
pCheck->rc = SQLITE_NOMEM; |
| 3907 |
}else{ |
| 3908 |
pCheck->zReport = sqlite3_mprintf("%z%s%z", |
| 3909 |
pCheck->zReport, (pCheck->zReport ? "\n" : ""), z |
| 3910 |
); |
| 3911 |
if( pCheck->zReport==0 ){ |
| 3912 |
pCheck->rc = SQLITE_NOMEM; |
| 3913 |
} |
| 3914 |
} |
| 3915 |
pCheck->nErr++; |
| 3916 |
} |
| 3917 |
va_end(ap); |
| 3918 |
} |
| 3919 |
|
| 3920 |
/* |
| 3921 |
** This function is a no-op if there is already an error code stored |
| 3922 |
** in the RtreeCheck object indicated by the first argument. NULL is |
| 3923 |
** returned in this case. |
| 3924 |
** |
| 3925 |
** Otherwise, the contents of rtree table node iNode are loaded from |
| 3926 |
** the database and copied into a buffer obtained from sqlite3_malloc(). |
| 3927 |
** If no error occurs, a pointer to the buffer is returned and (*pnNode) |
| 3928 |
** is set to the size of the buffer in bytes. |
| 3929 |
** |
| 3930 |
** Or, if an error does occur, NULL is returned and an error code left |
| 3931 |
** in the RtreeCheck object. The final value of *pnNode is undefined in |
| 3932 |
** this case. |
| 3933 |
*/ |
| 3934 |
static u8 *rtreeCheckGetNode(RtreeCheck *pCheck, i64 iNode, int *pnNode){ |
| 3935 |
u8 *pRet = 0; /* Return value */ |
| 3936 |
|
| 3937 |
if( pCheck->rc==SQLITE_OK && pCheck->pGetNode==0 ){ |
| 3938 |
pCheck->pGetNode = rtreeCheckPrepare(pCheck, |
| 3939 |
"SELECT data FROM %Q.'%q_node' WHERE nodeno=?", |
| 3940 |
pCheck->zDb, pCheck->zTab |
| 3941 |
); |
| 3942 |
} |
| 3943 |
|
| 3944 |
if( pCheck->rc==SQLITE_OK ){ |
| 3945 |
sqlite3_bind_int64(pCheck->pGetNode, 1, iNode); |
| 3946 |
if( sqlite3_step(pCheck->pGetNode)==SQLITE_ROW ){ |
| 3947 |
int nNode = sqlite3_column_bytes(pCheck->pGetNode, 0); |
| 3948 |
const u8 *pNode = (const u8*)sqlite3_column_blob(pCheck->pGetNode, 0); |
| 3949 |
pRet = sqlite3_malloc64(nNode); |
| 3950 |
if( pRet==0 ){ |
| 3951 |
pCheck->rc = SQLITE_NOMEM; |
| 3952 |
}else{ |
| 3953 |
memcpy(pRet, pNode, nNode); |
| 3954 |
*pnNode = nNode; |
| 3955 |
} |
| 3956 |
} |
| 3957 |
rtreeCheckReset(pCheck, pCheck->pGetNode); |
| 3958 |
if( pCheck->rc==SQLITE_OK && pRet==0 ){ |
| 3959 |
rtreeCheckAppendMsg(pCheck, "Node %lld missing from database", iNode); |
| 3960 |
} |
| 3961 |
} |
| 3962 |
|
| 3963 |
return pRet; |
| 3964 |
} |
| 3965 |
|
| 3966 |
/* |
| 3967 |
** This function is used to check that the %_parent (if bLeaf==0) or %_rowid |
| 3968 |
** (if bLeaf==1) table contains a specified entry. The schemas of the |
| 3969 |
** two tables are: |
| 3970 |
** |
| 3971 |
** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) |
| 3972 |
** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...) |
| 3973 |
** |
| 3974 |
** In both cases, this function checks that there exists an entry with |
| 3975 |
** IPK value iKey and the second column set to iVal. |
| 3976 |
** |
| 3977 |
*/ |
| 3978 |
static void rtreeCheckMapping( |
| 3979 |
RtreeCheck *pCheck, /* RtreeCheck object */ |
| 3980 |
int bLeaf, /* True for a leaf cell, false for interior */ |
| 3981 |
i64 iKey, /* Key for mapping */ |
| 3982 |
i64 iVal /* Expected value for mapping */ |
| 3983 |
){ |
| 3984 |
int rc; |
| 3985 |
sqlite3_stmt *pStmt; |
| 3986 |
const char *azSql[2] = { |
| 3987 |
"SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1", |
| 3988 |
"SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1" |
| 3989 |
}; |
| 3990 |
|
| 3991 |
assert( bLeaf==0 || bLeaf==1 ); |
| 3992 |
if( pCheck->aCheckMapping[bLeaf]==0 ){ |
| 3993 |
pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck, |
| 3994 |
azSql[bLeaf], pCheck->zDb, pCheck->zTab |
| 3995 |
); |
| 3996 |
} |
| 3997 |
if( pCheck->rc!=SQLITE_OK ) return; |
| 3998 |
|
| 3999 |
pStmt = pCheck->aCheckMapping[bLeaf]; |
| 4000 |
sqlite3_bind_int64(pStmt, 1, iKey); |
| 4001 |
rc = sqlite3_step(pStmt); |
| 4002 |
if( rc==SQLITE_DONE ){ |
| 4003 |
rtreeCheckAppendMsg(pCheck, "Mapping (%lld -> %lld) missing from %s table", |
| 4004 |
iKey, iVal, (bLeaf ? "%_rowid" : "%_parent") |
| 4005 |
); |
| 4006 |
}else if( rc==SQLITE_ROW ){ |
| 4007 |
i64 ii = sqlite3_column_int64(pStmt, 0); |
| 4008 |
if( ii!=iVal ){ |
| 4009 |
rtreeCheckAppendMsg(pCheck, |
| 4010 |
"Found (%lld -> %lld) in %s table, expected (%lld -> %lld)", |
| 4011 |
iKey, ii, (bLeaf ? "%_rowid" : "%_parent"), iKey, iVal |
| 4012 |
); |
| 4013 |
} |
| 4014 |
} |
| 4015 |
rtreeCheckReset(pCheck, pStmt); |
| 4016 |
} |
| 4017 |
|
| 4018 |
/* |
| 4019 |
** Argument pCell points to an array of coordinates stored on an rtree page. |
| 4020 |
** This function checks that the coordinates are internally consistent (no |
| 4021 |
** x1>x2 conditions) and adds an error message to the RtreeCheck object |
| 4022 |
** if they are not. |
| 4023 |
** |
| 4024 |
** Additionally, if pParent is not NULL, then it is assumed to point to |
| 4025 |
** the array of coordinates on the parent page that bound the page |
| 4026 |
** containing pCell. In this case it is also verified that the two |
| 4027 |
** sets of coordinates are mutually consistent and an error message added |
| 4028 |
** to the RtreeCheck object if they are not. |
| 4029 |
*/ |
| 4030 |
static void rtreeCheckCellCoord( |
| 4031 |
RtreeCheck *pCheck, |
| 4032 |
i64 iNode, /* Node id to use in error messages */ |
| 4033 |
int iCell, /* Cell number to use in error messages */ |
| 4034 |
u8 *pCell, /* Pointer to cell coordinates */ |
| 4035 |
u8 *pParent /* Pointer to parent coordinates */ |
| 4036 |
){ |
| 4037 |
RtreeCoord c1, c2; |
| 4038 |
RtreeCoord p1, p2; |
| 4039 |
int i; |
| 4040 |
|
| 4041 |
for(i=0; i<pCheck->nDim; i++){ |
| 4042 |
readCoord(&pCell[4*2*i], &c1); |
| 4043 |
readCoord(&pCell[4*(2*i + 1)], &c2); |
| 4044 |
|
| 4045 |
/* printf("%e, %e\n", c1.u.f, c2.u.f); */ |
| 4046 |
if( pCheck->bInt ? c1.i>c2.i : c1.f>c2.f ){ |
| 4047 |
rtreeCheckAppendMsg(pCheck, |
| 4048 |
"Dimension %d of cell %d on node %lld is corrupt", i, iCell, iNode |
| 4049 |
); |
| 4050 |
} |
| 4051 |
|
| 4052 |
if( pParent ){ |
| 4053 |
readCoord(&pParent[4*2*i], &p1); |
| 4054 |
readCoord(&pParent[4*(2*i + 1)], &p2); |
| 4055 |
|
| 4056 |
if( (pCheck->bInt ? c1.i<p1.i : c1.f<p1.f) |
| 4057 |
|| (pCheck->bInt ? c2.i>p2.i : c2.f>p2.f) |
| 4058 |
){ |
| 4059 |
rtreeCheckAppendMsg(pCheck, |
| 4060 |
"Dimension %d of cell %d on node %lld is corrupt relative to parent" |
| 4061 |
, i, iCell, iNode |
| 4062 |
); |
| 4063 |
} |
| 4064 |
} |
| 4065 |
} |
| 4066 |
} |
| 4067 |
|
| 4068 |
/* |
| 4069 |
** Run rtreecheck() checks on node iNode, which is at depth iDepth within |
| 4070 |
** the r-tree structure. Argument aParent points to the array of coordinates |
| 4071 |
** that bound node iNode on the parent node. |
| 4072 |
** |
| 4073 |
** If any problems are discovered, an error message is appended to the |
| 4074 |
** report accumulated in the RtreeCheck object. |
| 4075 |
*/ |
| 4076 |
static void rtreeCheckNode( |
| 4077 |
RtreeCheck *pCheck, |
| 4078 |
int iDepth, /* Depth of iNode (0==leaf) */ |
| 4079 |
u8 *aParent, /* Buffer containing parent coords */ |
| 4080 |
i64 iNode /* Node to check */ |
| 4081 |
){ |
| 4082 |
u8 *aNode = 0; |
| 4083 |
int nNode = 0; |
| 4084 |
|
| 4085 |
assert( iNode==1 || aParent!=0 ); |
| 4086 |
assert( pCheck->nDim>0 ); |
| 4087 |
|
| 4088 |
aNode = rtreeCheckGetNode(pCheck, iNode, &nNode); |
| 4089 |
if( aNode ){ |
| 4090 |
if( nNode<4 ){ |
| 4091 |
rtreeCheckAppendMsg(pCheck, |
| 4092 |
"Node %lld is too small (%d bytes)", iNode, nNode |
| 4093 |
); |
| 4094 |
}else{ |
| 4095 |
int nCell; /* Number of cells on page */ |
| 4096 |
int i; /* Used to iterate through cells */ |
| 4097 |
if( aParent==0 ){ |
| 4098 |
iDepth = readInt16(aNode); |
| 4099 |
if( iDepth>RTREE_MAX_DEPTH ){ |
| 4100 |
rtreeCheckAppendMsg(pCheck, "Rtree depth out of range (%d)", iDepth); |
| 4101 |
sqlite3_free(aNode); |
| 4102 |
return; |
| 4103 |
} |
| 4104 |
} |
| 4105 |
nCell = readInt16(&aNode[2]); |
| 4106 |
if( (4 + nCell*(8 + pCheck->nDim*2*4))>nNode ){ |
| 4107 |
rtreeCheckAppendMsg(pCheck, |
| 4108 |
"Node %lld is too small for cell count of %d (%d bytes)", |
| 4109 |
iNode, nCell, nNode |
| 4110 |
); |
| 4111 |
}else{ |
| 4112 |
for(i=0; i<nCell; i++){ |
| 4113 |
u8 *pCell = &aNode[4 + i*(8 + pCheck->nDim*2*4)]; |
| 4114 |
i64 iVal = readInt64(pCell); |
| 4115 |
rtreeCheckCellCoord(pCheck, iNode, i, &pCell[8], aParent); |
| 4116 |
|
| 4117 |
if( iDepth>0 ){ |
| 4118 |
rtreeCheckMapping(pCheck, 0, iVal, iNode); |
| 4119 |
rtreeCheckNode(pCheck, iDepth-1, &pCell[8], iVal); |
| 4120 |
pCheck->nNonLeaf++; |
| 4121 |
}else{ |
| 4122 |
rtreeCheckMapping(pCheck, 1, iVal, iNode); |
| 4123 |
pCheck->nLeaf++; |
| 4124 |
} |
| 4125 |
} |
| 4126 |
} |
| 4127 |
} |
| 4128 |
sqlite3_free(aNode); |
| 4129 |
} |
| 4130 |
} |
| 4131 |
|
| 4132 |
/* |
| 4133 |
** The second argument to this function must be either "_rowid" or |
| 4134 |
** "_parent". This function checks that the number of entries in the |
| 4135 |
** %_rowid or %_parent table is exactly nExpect. If not, it adds |
| 4136 |
** an error message to the report in the RtreeCheck object indicated |
| 4137 |
** by the first argument. |
| 4138 |
*/ |
| 4139 |
static void rtreeCheckCount(RtreeCheck *pCheck, const char *zTbl, i64 nExpect){ |
| 4140 |
if( pCheck->rc==SQLITE_OK ){ |
| 4141 |
sqlite3_stmt *pCount; |
| 4142 |
pCount = rtreeCheckPrepare(pCheck, "SELECT count(*) FROM %Q.'%q%s'", |
| 4143 |
pCheck->zDb, pCheck->zTab, zTbl |
| 4144 |
); |
| 4145 |
if( pCount ){ |
| 4146 |
if( sqlite3_step(pCount)==SQLITE_ROW ){ |
| 4147 |
i64 nActual = sqlite3_column_int64(pCount, 0); |
| 4148 |
if( nActual!=nExpect ){ |
| 4149 |
rtreeCheckAppendMsg(pCheck, "Wrong number of entries in %%%s table" |
| 4150 |
" - expected %lld, actual %lld" , zTbl, nExpect, nActual |
| 4151 |
); |
| 4152 |
} |
| 4153 |
} |
| 4154 |
pCheck->rc = sqlite3_finalize(pCount); |
| 4155 |
} |
| 4156 |
} |
| 4157 |
} |
| 4158 |
|
| 4159 |
/* |
| 4160 |
** This function does the bulk of the work for the rtree integrity-check. |
| 4161 |
** It is called by rtreecheck(), which is the SQL function implementation. |
| 4162 |
*/ |
| 4163 |
static int rtreeCheckTable( |
| 4164 |
sqlite3 *db, /* Database handle to access db through */ |
| 4165 |
const char *zDb, /* Name of db ("main", "temp" etc.) */ |
| 4166 |
const char *zTab, /* Name of rtree table to check */ |
| 4167 |
char **pzReport /* OUT: sqlite3_malloc'd report text */ |
| 4168 |
){ |
| 4169 |
RtreeCheck check; /* Common context for various routines */ |
| 4170 |
sqlite3_stmt *pStmt = 0; /* Used to find column count of rtree table */ |
| 4171 |
int nAux = 0; /* Number of extra columns. */ |
| 4172 |
|
| 4173 |
/* Initialize the context object */ |
| 4174 |
memset(&check, 0, sizeof(check)); |
| 4175 |
check.db = db; |
| 4176 |
check.zDb = zDb; |
| 4177 |
check.zTab = zTab; |
| 4178 |
|
| 4179 |
/* Find the number of auxiliary columns */ |
| 4180 |
pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.'%q_rowid'", zDb, zTab); |
| 4181 |
if( pStmt ){ |
| 4182 |
nAux = sqlite3_column_count(pStmt) - 2; |
| 4183 |
sqlite3_finalize(pStmt); |
| 4184 |
}else |
| 4185 |
if( check.rc!=SQLITE_NOMEM ){ |
| 4186 |
check.rc = SQLITE_OK; |
| 4187 |
} |
| 4188 |
|
| 4189 |
/* Find number of dimensions in the rtree table. */ |
| 4190 |
pStmt = rtreeCheckPrepare(&check, "SELECT * FROM %Q.%Q", zDb, zTab); |
| 4191 |
if( pStmt ){ |
| 4192 |
int rc; |
| 4193 |
check.nDim = (sqlite3_column_count(pStmt) - 1 - nAux) / 2; |
| 4194 |
if( check.nDim<1 ){ |
| 4195 |
rtreeCheckAppendMsg(&check, "Schema corrupt or not an rtree"); |
| 4196 |
}else if( SQLITE_ROW==sqlite3_step(pStmt) ){ |
| 4197 |
check.bInt = (sqlite3_column_type(pStmt, 1)==SQLITE_INTEGER); |
| 4198 |
} |
| 4199 |
rc = sqlite3_finalize(pStmt); |
| 4200 |
if( rc!=SQLITE_CORRUPT ) check.rc = rc; |
| 4201 |
} |
| 4202 |
|
| 4203 |
/* Do the actual integrity-check */ |
| 4204 |
if( check.nDim>=1 ){ |
| 4205 |
if( check.rc==SQLITE_OK ){ |
| 4206 |
rtreeCheckNode(&check, 0, 0, 1); |
| 4207 |
} |
| 4208 |
rtreeCheckCount(&check, "_rowid", check.nLeaf); |
| 4209 |
rtreeCheckCount(&check, "_parent", check.nNonLeaf); |
| 4210 |
} |
| 4211 |
|
| 4212 |
/* Finalize SQL statements used by the integrity-check */ |
| 4213 |
sqlite3_finalize(check.pGetNode); |
| 4214 |
sqlite3_finalize(check.aCheckMapping[0]); |
| 4215 |
sqlite3_finalize(check.aCheckMapping[1]); |
| 4216 |
|
| 4217 |
*pzReport = check.zReport; |
| 4218 |
return check.rc; |
| 4219 |
} |
| 4220 |
|
| 4221 |
/* |
| 4222 |
** Implementation of the xIntegrity method for Rtree. |
| 4223 |
*/ |
| 4224 |
static int rtreeIntegrity( |
| 4225 |
sqlite3_vtab *pVtab, /* The virtual table to check */ |
| 4226 |
const char *zSchema, /* Schema in which the virtual table lives */ |
| 4227 |
const char *zName, /* Name of the virtual table */ |
| 4228 |
int isQuick, /* True for a quick_check */ |
| 4229 |
char **pzErr /* Write results here */ |
| 4230 |
){ |
| 4231 |
Rtree *pRtree = (Rtree*)pVtab; |
| 4232 |
int rc; |
| 4233 |
assert( pzErr!=0 && *pzErr==0 ); |
| 4234 |
UNUSED_PARAMETER(zSchema); |
| 4235 |
UNUSED_PARAMETER(zName); |
| 4236 |
UNUSED_PARAMETER(isQuick); |
| 4237 |
rc = rtreeCheckTable(pRtree->db, pRtree->zDb, pRtree->zName, pzErr); |
| 4238 |
if( rc==SQLITE_OK && *pzErr ){ |
| 4239 |
*pzErr = sqlite3_mprintf("In RTree %s.%s:\n%z", |
| 4240 |
pRtree->zDb, pRtree->zName, *pzErr); |
| 4241 |
if( (*pzErr)==0 ) rc = SQLITE_NOMEM; |
| 4242 |
} |
| 4243 |
return rc; |
| 4244 |
} |
| 4245 |
|
| 4246 |
/* |
| 4247 |
** Usage: |
| 4248 |
** |
| 4249 |
** rtreecheck(<rtree-table>); |
| 4250 |
** rtreecheck(<database>, <rtree-table>); |
| 4251 |
** |
| 4252 |
** Invoking this SQL function runs an integrity-check on the named rtree |
| 4253 |
** table. The integrity-check verifies the following: |
| 4254 |
** |
| 4255 |
** 1. For each cell in the r-tree structure (%_node table), that: |
| 4256 |
** |
| 4257 |
** a) for each dimension, (coord1 <= coord2). |
| 4258 |
** |
| 4259 |
** b) unless the cell is on the root node, that the cell is bounded |
| 4260 |
** by the parent cell on the parent node. |
| 4261 |
** |
| 4262 |
** c) for leaf nodes, that there is an entry in the %_rowid |
| 4263 |
** table corresponding to the cell's rowid value that |
| 4264 |
** points to the correct node. |
| 4265 |
** |
| 4266 |
** d) for cells on non-leaf nodes, that there is an entry in the |
| 4267 |
** %_parent table mapping from the cell's child node to the |
| 4268 |
** node that it resides on. |
| 4269 |
** |
| 4270 |
** 2. That there are the same number of entries in the %_rowid table |
| 4271 |
** as there are leaf cells in the r-tree structure, and that there |
| 4272 |
** is a leaf cell that corresponds to each entry in the %_rowid table. |
| 4273 |
** |
| 4274 |
** 3. That there are the same number of entries in the %_parent table |
| 4275 |
** as there are non-leaf cells in the r-tree structure, and that |
| 4276 |
** there is a non-leaf cell that corresponds to each entry in the |
| 4277 |
** %_parent table. |
| 4278 |
*/ |
| 4279 |
static void rtreecheck( |
| 4280 |
sqlite3_context *ctx, |
| 4281 |
int nArg, |
| 4282 |
sqlite3_value **apArg |
| 4283 |
){ |
| 4284 |
if( nArg!=1 && nArg!=2 ){ |
| 4285 |
sqlite3_result_error(ctx, |
| 4286 |
"wrong number of arguments to function rtreecheck()", -1 |
| 4287 |
); |
| 4288 |
}else{ |
| 4289 |
int rc; |
| 4290 |
char *zReport = 0; |
| 4291 |
const char *zDb = (const char*)sqlite3_value_text(apArg[0]); |
| 4292 |
const char *zTab; |
| 4293 |
if( nArg==1 ){ |
| 4294 |
zTab = zDb; |
| 4295 |
zDb = "main"; |
| 4296 |
}else{ |
| 4297 |
zTab = (const char*)sqlite3_value_text(apArg[1]); |
| 4298 |
} |
| 4299 |
rc = rtreeCheckTable(sqlite3_context_db_handle(ctx), zDb, zTab, &zReport); |
| 4300 |
if( rc==SQLITE_OK ){ |
| 4301 |
sqlite3_result_text(ctx, zReport ? zReport : "ok", -1, SQLITE_TRANSIENT); |
| 4302 |
}else{ |
| 4303 |
sqlite3_result_error_code(ctx, rc); |
| 4304 |
} |
| 4305 |
sqlite3_free(zReport); |
| 4306 |
} |
| 4307 |
} |
| 4308 |
|
| 4309 |
/* Conditionally include the geopoly code */ |
| 4310 |
#ifdef SQLITE_ENABLE_GEOPOLY |
| 4311 |
# include "geopoly.c" |
| 4312 |
#endif |
| 4313 |
|
| 4314 |
/* |
| 4315 |
** Register the r-tree module with database handle db. This creates the |
| 4316 |
** virtual table module "rtree" and the debugging/analysis scalar |
| 4317 |
** function "rtreenode". |
| 4318 |
*/ |
| 4319 |
int sqlite3RtreeInit(sqlite3 *db){ |
| 4320 |
const int utf8 = SQLITE_UTF8; |
| 4321 |
int rc; |
| 4322 |
|
| 4323 |
rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0); |
| 4324 |
if( rc==SQLITE_OK ){ |
| 4325 |
rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0); |
| 4326 |
} |
| 4327 |
if( rc==SQLITE_OK ){ |
| 4328 |
rc = sqlite3_create_function(db, "rtreecheck", -1, utf8, 0,rtreecheck, 0,0); |
| 4329 |
} |
| 4330 |
if( rc==SQLITE_OK ){ |
| 4331 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 4332 |
void *c = (void *)RTREE_COORD_INT32; |
| 4333 |
#else |
| 4334 |
void *c = (void *)RTREE_COORD_REAL32; |
| 4335 |
#endif |
| 4336 |
rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0); |
| 4337 |
} |
| 4338 |
if( rc==SQLITE_OK ){ |
| 4339 |
void *c = (void *)RTREE_COORD_INT32; |
| 4340 |
rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); |
| 4341 |
} |
| 4342 |
#ifdef SQLITE_ENABLE_GEOPOLY |
| 4343 |
if( rc==SQLITE_OK ){ |
| 4344 |
rc = sqlite3_geopoly_init(db); |
| 4345 |
} |
| 4346 |
#endif |
| 4347 |
|
| 4348 |
return rc; |
| 4349 |
} |
| 4350 |
|
| 4351 |
/* |
| 4352 |
** This routine deletes the RtreeGeomCallback object that was attached |
| 4353 |
** one of the SQL functions create by sqlite3_rtree_geometry_callback() |
| 4354 |
** or sqlite3_rtree_query_callback(). In other words, this routine is the |
| 4355 |
** destructor for an RtreeGeomCallback objecct. This routine is called when |
| 4356 |
** the corresponding SQL function is deleted. |
| 4357 |
*/ |
| 4358 |
static void rtreeFreeCallback(void *p){ |
| 4359 |
RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p; |
| 4360 |
if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext); |
| 4361 |
sqlite3_free(p); |
| 4362 |
} |
| 4363 |
|
| 4364 |
/* |
| 4365 |
** This routine frees the BLOB that is returned by geomCallback(). |
| 4366 |
*/ |
| 4367 |
static void rtreeMatchArgFree(void *pArg){ |
| 4368 |
int i; |
| 4369 |
RtreeMatchArg *p = (RtreeMatchArg*)pArg; |
| 4370 |
for(i=0; i<p->nParam; i++){ |
| 4371 |
sqlite3_value_free(p->apSqlParam[i]); |
| 4372 |
} |
| 4373 |
sqlite3_free(p); |
| 4374 |
} |
| 4375 |
|
| 4376 |
/* |
| 4377 |
** Each call to sqlite3_rtree_geometry_callback() or |
| 4378 |
** sqlite3_rtree_query_callback() creates an ordinary SQLite |
| 4379 |
** scalar function that is implemented by this routine. |
| 4380 |
** |
| 4381 |
** All this function does is construct an RtreeMatchArg object that |
| 4382 |
** contains the geometry-checking callback routines and a list of |
| 4383 |
** parameters to this function, then return that RtreeMatchArg object |
| 4384 |
** as a BLOB. |
| 4385 |
** |
| 4386 |
** The R-Tree MATCH operator will read the returned BLOB, deserialize |
| 4387 |
** the RtreeMatchArg object, and use the RtreeMatchArg object to figure |
| 4388 |
** out which elements of the R-Tree should be returned by the query. |
| 4389 |
*/ |
| 4390 |
static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){ |
| 4391 |
RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx); |
| 4392 |
RtreeMatchArg *pBlob; |
| 4393 |
sqlite3_int64 nBlob; |
| 4394 |
int memErr = 0; |
| 4395 |
|
| 4396 |
nBlob = SZ_RTREEMATCHARG(nArg) + nArg*sizeof(sqlite3_value*); |
| 4397 |
pBlob = (RtreeMatchArg *)sqlite3_malloc64(nBlob); |
| 4398 |
if( !pBlob ){ |
| 4399 |
sqlite3_result_error_nomem(ctx); |
| 4400 |
}else{ |
| 4401 |
int i; |
| 4402 |
pBlob->iSize = nBlob; |
| 4403 |
pBlob->cb = pGeomCtx[0]; |
| 4404 |
pBlob->apSqlParam = (sqlite3_value**)&pBlob->aParam[nArg]; |
| 4405 |
pBlob->nParam = nArg; |
| 4406 |
for(i=0; i<nArg; i++){ |
| 4407 |
pBlob->apSqlParam[i] = sqlite3_value_dup(aArg[i]); |
| 4408 |
if( pBlob->apSqlParam[i]==0 ) memErr = 1; |
| 4409 |
#ifdef SQLITE_RTREE_INT_ONLY |
| 4410 |
pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); |
| 4411 |
#else |
| 4412 |
pBlob->aParam[i] = sqlite3_value_double(aArg[i]); |
| 4413 |
#endif |
| 4414 |
} |
| 4415 |
if( memErr ){ |
| 4416 |
sqlite3_result_error_nomem(ctx); |
| 4417 |
rtreeMatchArgFree(pBlob); |
| 4418 |
}else{ |
| 4419 |
sqlite3_result_pointer(ctx, pBlob, "RtreeMatchArg", rtreeMatchArgFree); |
| 4420 |
} |
| 4421 |
} |
| 4422 |
} |
| 4423 |
|
| 4424 |
/* |
| 4425 |
** Register a new geometry function for use with the r-tree MATCH operator. |
| 4426 |
*/ |
| 4427 |
int sqlite3_rtree_geometry_callback( |
| 4428 |
sqlite3 *db, /* Register SQL function on this connection */ |
| 4429 |
const char *zGeom, /* Name of the new SQL function */ |
| 4430 |
int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */ |
| 4431 |
void *pContext /* Extra data associated with the callback */ |
| 4432 |
){ |
| 4433 |
RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ |
| 4434 |
|
| 4435 |
/* Allocate and populate the context object. */ |
| 4436 |
pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); |
| 4437 |
if( !pGeomCtx ) return SQLITE_NOMEM; |
| 4438 |
pGeomCtx->xGeom = xGeom; |
| 4439 |
pGeomCtx->xQueryFunc = 0; |
| 4440 |
pGeomCtx->xDestructor = 0; |
| 4441 |
pGeomCtx->pContext = pContext; |
| 4442 |
return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, |
| 4443 |
(void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback |
| 4444 |
); |
| 4445 |
} |
| 4446 |
|
| 4447 |
/* |
| 4448 |
** Register a new 2nd-generation geometry function for use with the |
| 4449 |
** r-tree MATCH operator. |
| 4450 |
*/ |
| 4451 |
int sqlite3_rtree_query_callback( |
| 4452 |
sqlite3 *db, /* Register SQL function on this connection */ |
| 4453 |
const char *zQueryFunc, /* Name of new SQL function */ |
| 4454 |
int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */ |
| 4455 |
void *pContext, /* Extra data passed into the callback */ |
| 4456 |
void (*xDestructor)(void*) /* Destructor for the extra data */ |
| 4457 |
){ |
| 4458 |
RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ |
| 4459 |
|
| 4460 |
/* Allocate and populate the context object. */ |
| 4461 |
pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); |
| 4462 |
if( !pGeomCtx ){ |
| 4463 |
if( xDestructor ) xDestructor(pContext); |
| 4464 |
return SQLITE_NOMEM; |
| 4465 |
} |
| 4466 |
pGeomCtx->xGeom = 0; |
| 4467 |
pGeomCtx->xQueryFunc = xQueryFunc; |
| 4468 |
pGeomCtx->xDestructor = xDestructor; |
| 4469 |
pGeomCtx->pContext = pContext; |
| 4470 |
return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, |
| 4471 |
(void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback |
| 4472 |
); |
| 4473 |
} |
| 4474 |
|
| 4475 |
#ifndef SQLITE_CORE |
| 4476 |
#ifdef _WIN32 |
| 4477 |
__declspec(dllexport) |
| 4478 |
#endif |
| 4479 |
int sqlite3_rtree_init( |
| 4480 |
sqlite3 *db, |
| 4481 |
char **pzErrMsg, |
| 4482 |
const sqlite3_api_routines *pApi |
| 4483 |
){ |
| 4484 |
SQLITE_EXTENSION_INIT2(pApi) |
| 4485 |
return sqlite3RtreeInit(db); |
| 4486 |
} |
| 4487 |
#endif |
| 4488 |
|
| 4489 |
#endif |