|
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 ** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $ |
|
16 */ |
|
17 |
|
18 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) |
|
19 |
|
20 /* |
|
21 ** This file contains an implementation of a couple of different variants |
|
22 ** of the r-tree algorithm. See the README file for further details. The |
|
23 ** same data-structure is used for all, but the algorithms for insert and |
|
24 ** delete operations vary. The variants used are selected at compile time |
|
25 ** by defining the following symbols: |
|
26 */ |
|
27 |
|
28 /* Either, both or none of the following may be set to activate |
|
29 ** r*tree variant algorithms. |
|
30 */ |
|
31 #define VARIANT_RSTARTREE_CHOOSESUBTREE 0 |
|
32 #define VARIANT_RSTARTREE_REINSERT 1 |
|
33 |
|
34 /* |
|
35 ** Exactly one of the following must be set to 1. |
|
36 */ |
|
37 #define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0 |
|
38 #define VARIANT_GUTTMAN_LINEAR_SPLIT 0 |
|
39 #define VARIANT_RSTARTREE_SPLIT 1 |
|
40 |
|
41 #define VARIANT_GUTTMAN_SPLIT \ |
|
42 (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT) |
|
43 |
|
44 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT |
|
45 #define PickNext QuadraticPickNext |
|
46 #define PickSeeds QuadraticPickSeeds |
|
47 #define AssignCells splitNodeGuttman |
|
48 #endif |
|
49 #if VARIANT_GUTTMAN_LINEAR_SPLIT |
|
50 #define PickNext LinearPickNext |
|
51 #define PickSeeds LinearPickSeeds |
|
52 #define AssignCells splitNodeGuttman |
|
53 #endif |
|
54 #if VARIANT_RSTARTREE_SPLIT |
|
55 #define AssignCells splitNodeStartree |
|
56 #endif |
|
57 |
|
58 |
|
59 #ifndef SQLITE_CORE |
|
60 #include "sqlite3ext.h" |
|
61 SQLITE_EXTENSION_INIT1 |
|
62 #else |
|
63 #include "sqlite3.h" |
|
64 #endif |
|
65 |
|
66 #include <string.h> |
|
67 #include <assert.h> |
|
68 |
|
69 #ifndef SQLITE_AMALGAMATION |
|
70 typedef sqlite3_int64 i64; |
|
71 typedef unsigned char u8; |
|
72 typedef unsigned int u32; |
|
73 #endif |
|
74 |
|
75 typedef struct Rtree Rtree; |
|
76 typedef struct RtreeCursor RtreeCursor; |
|
77 typedef struct RtreeNode RtreeNode; |
|
78 typedef struct RtreeCell RtreeCell; |
|
79 typedef struct RtreeConstraint RtreeConstraint; |
|
80 typedef union RtreeCoord RtreeCoord; |
|
81 |
|
82 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ |
|
83 #define RTREE_MAX_DIMENSIONS 5 |
|
84 |
|
85 /* Size of hash table Rtree.aHash. This hash table is not expected to |
|
86 ** ever contain very many entries, so a fixed number of buckets is |
|
87 ** used. |
|
88 */ |
|
89 #define HASHSIZE 128 |
|
90 |
|
91 /* |
|
92 ** An rtree virtual-table object. |
|
93 */ |
|
94 struct Rtree { |
|
95 sqlite3_vtab base; |
|
96 sqlite3 *db; /* Host database connection */ |
|
97 int iNodeSize; /* Size in bytes of each node in the node table */ |
|
98 int nDim; /* Number of dimensions */ |
|
99 int nBytesPerCell; /* Bytes consumed per cell */ |
|
100 int iDepth; /* Current depth of the r-tree structure */ |
|
101 char *zDb; /* Name of database containing r-tree table */ |
|
102 char *zName; /* Name of r-tree table */ |
|
103 RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ |
|
104 int nBusy; /* Current number of users of this structure */ |
|
105 |
|
106 /* List of nodes removed during a CondenseTree operation. List is |
|
107 ** linked together via the pointer normally used for hash chains - |
|
108 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree |
|
109 ** headed by the node (leaf nodes have RtreeNode.iNode==0). |
|
110 */ |
|
111 RtreeNode *pDeleted; |
|
112 int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */ |
|
113 |
|
114 /* Statements to read/write/delete a record from xxx_node */ |
|
115 sqlite3_stmt *pReadNode; |
|
116 sqlite3_stmt *pWriteNode; |
|
117 sqlite3_stmt *pDeleteNode; |
|
118 |
|
119 /* Statements to read/write/delete a record from xxx_rowid */ |
|
120 sqlite3_stmt *pReadRowid; |
|
121 sqlite3_stmt *pWriteRowid; |
|
122 sqlite3_stmt *pDeleteRowid; |
|
123 |
|
124 /* Statements to read/write/delete a record from xxx_parent */ |
|
125 sqlite3_stmt *pReadParent; |
|
126 sqlite3_stmt *pWriteParent; |
|
127 sqlite3_stmt *pDeleteParent; |
|
128 |
|
129 int eCoordType; |
|
130 }; |
|
131 |
|
132 /* Possible values for eCoordType: */ |
|
133 #define RTREE_COORD_REAL32 0 |
|
134 #define RTREE_COORD_INT32 1 |
|
135 |
|
136 /* |
|
137 ** The minimum number of cells allowed for a node is a third of the |
|
138 ** maximum. In Gutman's notation: |
|
139 ** |
|
140 ** m = M/3 |
|
141 ** |
|
142 ** If an R*-tree "Reinsert" operation is required, the same number of |
|
143 ** cells are removed from the overfull node and reinserted into the tree. |
|
144 */ |
|
145 #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3) |
|
146 #define RTREE_REINSERT(p) RTREE_MINCELLS(p) |
|
147 #define RTREE_MAXCELLS 51 |
|
148 |
|
149 /* |
|
150 ** An rtree cursor object. |
|
151 */ |
|
152 struct RtreeCursor { |
|
153 sqlite3_vtab_cursor base; |
|
154 RtreeNode *pNode; /* Node cursor is currently pointing at */ |
|
155 int iCell; /* Index of current cell in pNode */ |
|
156 int iStrategy; /* Copy of idxNum search parameter */ |
|
157 int nConstraint; /* Number of entries in aConstraint */ |
|
158 RtreeConstraint *aConstraint; /* Search constraints. */ |
|
159 }; |
|
160 |
|
161 union RtreeCoord { |
|
162 float f; |
|
163 int i; |
|
164 }; |
|
165 |
|
166 /* |
|
167 ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord |
|
168 ** formatted as a double. This macro assumes that local variable pRtree points |
|
169 ** to the Rtree structure associated with the RtreeCoord. |
|
170 */ |
|
171 #define DCOORD(coord) ( \ |
|
172 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \ |
|
173 ((double)coord.f) : \ |
|
174 ((double)coord.i) \ |
|
175 ) |
|
176 |
|
177 /* |
|
178 ** A search constraint. |
|
179 */ |
|
180 struct RtreeConstraint { |
|
181 int iCoord; /* Index of constrained coordinate */ |
|
182 int op; /* Constraining operation */ |
|
183 double rValue; /* Constraint value. */ |
|
184 }; |
|
185 |
|
186 /* Possible values for RtreeConstraint.op */ |
|
187 #define RTREE_EQ 0x41 |
|
188 #define RTREE_LE 0x42 |
|
189 #define RTREE_LT 0x43 |
|
190 #define RTREE_GE 0x44 |
|
191 #define RTREE_GT 0x45 |
|
192 |
|
193 /* |
|
194 ** An rtree structure node. |
|
195 ** |
|
196 ** Data format (RtreeNode.zData): |
|
197 ** |
|
198 ** 1. If the node is the root node (node 1), then the first 2 bytes |
|
199 ** of the node contain the tree depth as a big-endian integer. |
|
200 ** For non-root nodes, the first 2 bytes are left unused. |
|
201 ** |
|
202 ** 2. The next 2 bytes contain the number of entries currently |
|
203 ** stored in the node. |
|
204 ** |
|
205 ** 3. The remainder of the node contains the node entries. Each entry |
|
206 ** consists of a single 8-byte integer followed by an even number |
|
207 ** of 4-byte coordinates. For leaf nodes the integer is the rowid |
|
208 ** of a record. For internal nodes it is the node number of a |
|
209 ** child page. |
|
210 */ |
|
211 struct RtreeNode { |
|
212 RtreeNode *pParent; /* Parent node */ |
|
213 i64 iNode; |
|
214 int nRef; |
|
215 int isDirty; |
|
216 u8 *zData; |
|
217 RtreeNode *pNext; /* Next node in this hash chain */ |
|
218 }; |
|
219 #define NCELL(pNode) readInt16(&(pNode)->zData[2]) |
|
220 |
|
221 /* |
|
222 ** Structure to store a deserialized rtree record. |
|
223 */ |
|
224 struct RtreeCell { |
|
225 i64 iRowid; |
|
226 RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; |
|
227 }; |
|
228 |
|
229 #define MAX(x,y) ((x) < (y) ? (y) : (x)) |
|
230 #define MIN(x,y) ((x) > (y) ? (y) : (x)) |
|
231 |
|
232 /* |
|
233 ** Functions to deserialize a 16 bit integer, 32 bit real number and |
|
234 ** 64 bit integer. The deserialized value is returned. |
|
235 */ |
|
236 static int readInt16(u8 *p){ |
|
237 return (p[0]<<8) + p[1]; |
|
238 } |
|
239 static void readCoord(u8 *p, RtreeCoord *pCoord){ |
|
240 u32 i = ( |
|
241 (((u32)p[0]) << 24) + |
|
242 (((u32)p[1]) << 16) + |
|
243 (((u32)p[2]) << 8) + |
|
244 (((u32)p[3]) << 0) |
|
245 ); |
|
246 *(u32 *)pCoord = i; |
|
247 } |
|
248 static i64 readInt64(u8 *p){ |
|
249 return ( |
|
250 (((i64)p[0]) << 56) + |
|
251 (((i64)p[1]) << 48) + |
|
252 (((i64)p[2]) << 40) + |
|
253 (((i64)p[3]) << 32) + |
|
254 (((i64)p[4]) << 24) + |
|
255 (((i64)p[5]) << 16) + |
|
256 (((i64)p[6]) << 8) + |
|
257 (((i64)p[7]) << 0) |
|
258 ); |
|
259 } |
|
260 |
|
261 /* |
|
262 ** Functions to serialize a 16 bit integer, 32 bit real number and |
|
263 ** 64 bit integer. The value returned is the number of bytes written |
|
264 ** to the argument buffer (always 2, 4 and 8 respectively). |
|
265 */ |
|
266 static int writeInt16(u8 *p, int i){ |
|
267 p[0] = (i>> 8)&0xFF; |
|
268 p[1] = (i>> 0)&0xFF; |
|
269 return 2; |
|
270 } |
|
271 static int writeCoord(u8 *p, RtreeCoord *pCoord){ |
|
272 u32 i; |
|
273 assert( sizeof(RtreeCoord)==4 ); |
|
274 assert( sizeof(u32)==4 ); |
|
275 i = *(u32 *)pCoord; |
|
276 p[0] = (i>>24)&0xFF; |
|
277 p[1] = (i>>16)&0xFF; |
|
278 p[2] = (i>> 8)&0xFF; |
|
279 p[3] = (i>> 0)&0xFF; |
|
280 return 4; |
|
281 } |
|
282 static int writeInt64(u8 *p, i64 i){ |
|
283 p[0] = (i>>56)&0xFF; |
|
284 p[1] = (i>>48)&0xFF; |
|
285 p[2] = (i>>40)&0xFF; |
|
286 p[3] = (i>>32)&0xFF; |
|
287 p[4] = (i>>24)&0xFF; |
|
288 p[5] = (i>>16)&0xFF; |
|
289 p[6] = (i>> 8)&0xFF; |
|
290 p[7] = (i>> 0)&0xFF; |
|
291 return 8; |
|
292 } |
|
293 |
|
294 /* |
|
295 ** Increment the reference count of node p. |
|
296 */ |
|
297 static void nodeReference(RtreeNode *p){ |
|
298 if( p ){ |
|
299 p->nRef++; |
|
300 } |
|
301 } |
|
302 |
|
303 /* |
|
304 ** Clear the content of node p (set all bytes to 0x00). |
|
305 */ |
|
306 static void nodeZero(Rtree *pRtree, RtreeNode *p){ |
|
307 if( p ){ |
|
308 memset(&p->zData[2], 0, pRtree->iNodeSize-2); |
|
309 p->isDirty = 1; |
|
310 } |
|
311 } |
|
312 |
|
313 /* |
|
314 ** Given a node number iNode, return the corresponding key to use |
|
315 ** in the Rtree.aHash table. |
|
316 */ |
|
317 static int nodeHash(i64 iNode){ |
|
318 return ( |
|
319 (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ |
|
320 (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0) |
|
321 ) % HASHSIZE; |
|
322 } |
|
323 |
|
324 /* |
|
325 ** Search the node hash table for node iNode. If found, return a pointer |
|
326 ** to it. Otherwise, return 0. |
|
327 */ |
|
328 static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ |
|
329 RtreeNode *p; |
|
330 assert( iNode!=0 ); |
|
331 for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); |
|
332 return p; |
|
333 } |
|
334 |
|
335 /* |
|
336 ** Add node pNode to the node hash table. |
|
337 */ |
|
338 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ |
|
339 if( pNode ){ |
|
340 int iHash; |
|
341 assert( pNode->pNext==0 ); |
|
342 iHash = nodeHash(pNode->iNode); |
|
343 pNode->pNext = pRtree->aHash[iHash]; |
|
344 pRtree->aHash[iHash] = pNode; |
|
345 } |
|
346 } |
|
347 |
|
348 /* |
|
349 ** Remove node pNode from the node hash table. |
|
350 */ |
|
351 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){ |
|
352 RtreeNode **pp; |
|
353 if( pNode->iNode!=0 ){ |
|
354 pp = &pRtree->aHash[nodeHash(pNode->iNode)]; |
|
355 for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); } |
|
356 *pp = pNode->pNext; |
|
357 pNode->pNext = 0; |
|
358 } |
|
359 } |
|
360 |
|
361 /* |
|
362 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0), |
|
363 ** indicating that node has not yet been assigned a node number. It is |
|
364 ** assigned a node number when nodeWrite() is called to write the |
|
365 ** node contents out to the database. |
|
366 */ |
|
367 static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){ |
|
368 RtreeNode *pNode; |
|
369 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize); |
|
370 if( pNode ){ |
|
371 memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0)); |
|
372 pNode->zData = (u8 *)&pNode[1]; |
|
373 pNode->nRef = 1; |
|
374 pNode->pParent = pParent; |
|
375 pNode->isDirty = 1; |
|
376 nodeReference(pParent); |
|
377 } |
|
378 return pNode; |
|
379 } |
|
380 |
|
381 /* |
|
382 ** Obtain a reference to an r-tree node. |
|
383 */ |
|
384 static int |
|
385 nodeAcquire( |
|
386 Rtree *pRtree, /* R-tree structure */ |
|
387 i64 iNode, /* Node number to load */ |
|
388 RtreeNode *pParent, /* Either the parent node or NULL */ |
|
389 RtreeNode **ppNode /* OUT: Acquired node */ |
|
390 ){ |
|
391 int rc; |
|
392 RtreeNode *pNode; |
|
393 |
|
394 /* Check if the requested node is already in the hash table. If so, |
|
395 ** increase its reference count and return it. |
|
396 */ |
|
397 if( (pNode = nodeHashLookup(pRtree, iNode)) ){ |
|
398 assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); |
|
399 if( pParent ){ |
|
400 pNode->pParent = pParent; |
|
401 } |
|
402 pNode->nRef++; |
|
403 *ppNode = pNode; |
|
404 return SQLITE_OK; |
|
405 } |
|
406 |
|
407 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize); |
|
408 if( !pNode ){ |
|
409 *ppNode = 0; |
|
410 return SQLITE_NOMEM; |
|
411 } |
|
412 pNode->pParent = pParent; |
|
413 pNode->zData = (u8 *)&pNode[1]; |
|
414 pNode->nRef = 1; |
|
415 pNode->iNode = iNode; |
|
416 pNode->isDirty = 0; |
|
417 pNode->pNext = 0; |
|
418 |
|
419 sqlite3_bind_int64(pRtree->pReadNode, 1, iNode); |
|
420 rc = sqlite3_step(pRtree->pReadNode); |
|
421 if( rc==SQLITE_ROW ){ |
|
422 const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0); |
|
423 memcpy(pNode->zData, zBlob, pRtree->iNodeSize); |
|
424 nodeReference(pParent); |
|
425 }else{ |
|
426 sqlite3_free(pNode); |
|
427 pNode = 0; |
|
428 } |
|
429 |
|
430 *ppNode = pNode; |
|
431 rc = sqlite3_reset(pRtree->pReadNode); |
|
432 |
|
433 if( rc==SQLITE_OK && iNode==1 ){ |
|
434 pRtree->iDepth = readInt16(pNode->zData); |
|
435 } |
|
436 |
|
437 assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) ); |
|
438 nodeHashInsert(pRtree, pNode); |
|
439 |
|
440 return rc; |
|
441 } |
|
442 |
|
443 /* |
|
444 ** Overwrite cell iCell of node pNode with the contents of pCell. |
|
445 */ |
|
446 static void nodeOverwriteCell( |
|
447 Rtree *pRtree, |
|
448 RtreeNode *pNode, |
|
449 RtreeCell *pCell, |
|
450 int iCell |
|
451 ){ |
|
452 int ii; |
|
453 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
|
454 p += writeInt64(p, pCell->iRowid); |
|
455 for(ii=0; ii<(pRtree->nDim*2); ii++){ |
|
456 p += writeCoord(p, &pCell->aCoord[ii]); |
|
457 } |
|
458 pNode->isDirty = 1; |
|
459 } |
|
460 |
|
461 /* |
|
462 ** Remove cell the cell with index iCell from node pNode. |
|
463 */ |
|
464 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ |
|
465 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
|
466 u8 *pSrc = &pDst[pRtree->nBytesPerCell]; |
|
467 int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell; |
|
468 memmove(pDst, pSrc, nByte); |
|
469 writeInt16(&pNode->zData[2], NCELL(pNode)-1); |
|
470 pNode->isDirty = 1; |
|
471 } |
|
472 |
|
473 /* |
|
474 ** Insert the contents of cell pCell into node pNode. If the insert |
|
475 ** is successful, return SQLITE_OK. |
|
476 ** |
|
477 ** If there is not enough free space in pNode, return SQLITE_FULL. |
|
478 */ |
|
479 static int |
|
480 nodeInsertCell( |
|
481 Rtree *pRtree, |
|
482 RtreeNode *pNode, |
|
483 RtreeCell *pCell |
|
484 ){ |
|
485 int nCell; /* Current number of cells in pNode */ |
|
486 int nMaxCell; /* Maximum number of cells for pNode */ |
|
487 |
|
488 nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; |
|
489 nCell = NCELL(pNode); |
|
490 |
|
491 assert(nCell<=nMaxCell); |
|
492 |
|
493 if( nCell<nMaxCell ){ |
|
494 nodeOverwriteCell(pRtree, pNode, pCell, nCell); |
|
495 writeInt16(&pNode->zData[2], nCell+1); |
|
496 pNode->isDirty = 1; |
|
497 } |
|
498 |
|
499 return (nCell==nMaxCell); |
|
500 } |
|
501 |
|
502 /* |
|
503 ** If the node is dirty, write it out to the database. |
|
504 */ |
|
505 static int |
|
506 nodeWrite(Rtree *pRtree, RtreeNode *pNode){ |
|
507 int rc = SQLITE_OK; |
|
508 if( pNode->isDirty ){ |
|
509 sqlite3_stmt *p = pRtree->pWriteNode; |
|
510 if( pNode->iNode ){ |
|
511 sqlite3_bind_int64(p, 1, pNode->iNode); |
|
512 }else{ |
|
513 sqlite3_bind_null(p, 1); |
|
514 } |
|
515 sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC); |
|
516 sqlite3_step(p); |
|
517 pNode->isDirty = 0; |
|
518 rc = sqlite3_reset(p); |
|
519 if( pNode->iNode==0 && rc==SQLITE_OK ){ |
|
520 pNode->iNode = sqlite3_last_insert_rowid(pRtree->db); |
|
521 nodeHashInsert(pRtree, pNode); |
|
522 } |
|
523 } |
|
524 return rc; |
|
525 } |
|
526 |
|
527 /* |
|
528 ** Release a reference to a node. If the node is dirty and the reference |
|
529 ** count drops to zero, the node data is written to the database. |
|
530 */ |
|
531 static int |
|
532 nodeRelease(Rtree *pRtree, RtreeNode *pNode){ |
|
533 int rc = SQLITE_OK; |
|
534 if( pNode ){ |
|
535 assert( pNode->nRef>0 ); |
|
536 pNode->nRef--; |
|
537 if( pNode->nRef==0 ){ |
|
538 if( pNode->iNode==1 ){ |
|
539 pRtree->iDepth = -1; |
|
540 } |
|
541 if( pNode->pParent ){ |
|
542 rc = nodeRelease(pRtree, pNode->pParent); |
|
543 } |
|
544 if( rc==SQLITE_OK ){ |
|
545 rc = nodeWrite(pRtree, pNode); |
|
546 } |
|
547 nodeHashDelete(pRtree, pNode); |
|
548 sqlite3_free(pNode); |
|
549 } |
|
550 } |
|
551 return rc; |
|
552 } |
|
553 |
|
554 /* |
|
555 ** Return the 64-bit integer value associated with cell iCell of |
|
556 ** node pNode. If pNode is a leaf node, this is a rowid. If it is |
|
557 ** an internal node, then the 64-bit integer is a child page number. |
|
558 */ |
|
559 static i64 nodeGetRowid( |
|
560 Rtree *pRtree, |
|
561 RtreeNode *pNode, |
|
562 int iCell |
|
563 ){ |
|
564 assert( iCell<NCELL(pNode) ); |
|
565 return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); |
|
566 } |
|
567 |
|
568 /* |
|
569 ** Return coordinate iCoord from cell iCell in node pNode. |
|
570 */ |
|
571 static void nodeGetCoord( |
|
572 Rtree *pRtree, |
|
573 RtreeNode *pNode, |
|
574 int iCell, |
|
575 int iCoord, |
|
576 RtreeCoord *pCoord /* Space to write result to */ |
|
577 ){ |
|
578 readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); |
|
579 } |
|
580 |
|
581 /* |
|
582 ** Deserialize cell iCell of node pNode. Populate the structure pointed |
|
583 ** to by pCell with the results. |
|
584 */ |
|
585 static void nodeGetCell( |
|
586 Rtree *pRtree, |
|
587 RtreeNode *pNode, |
|
588 int iCell, |
|
589 RtreeCell *pCell |
|
590 ){ |
|
591 int ii; |
|
592 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); |
|
593 for(ii=0; ii<pRtree->nDim*2; ii++){ |
|
594 nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]); |
|
595 } |
|
596 } |
|
597 |
|
598 |
|
599 /* Forward declaration for the function that does the work of |
|
600 ** the virtual table module xCreate() and xConnect() methods. |
|
601 */ |
|
602 static int rtreeInit( |
|
603 sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int |
|
604 ); |
|
605 |
|
606 /* |
|
607 ** Rtree virtual table module xCreate method. |
|
608 */ |
|
609 static int rtreeCreate( |
|
610 sqlite3 *db, |
|
611 void *pAux, |
|
612 int argc, const char *const*argv, |
|
613 sqlite3_vtab **ppVtab, |
|
614 char **pzErr |
|
615 ){ |
|
616 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux); |
|
617 } |
|
618 |
|
619 /* |
|
620 ** Rtree virtual table module xConnect method. |
|
621 */ |
|
622 static int rtreeConnect( |
|
623 sqlite3 *db, |
|
624 void *pAux, |
|
625 int argc, const char *const*argv, |
|
626 sqlite3_vtab **ppVtab, |
|
627 char **pzErr |
|
628 ){ |
|
629 return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux); |
|
630 } |
|
631 |
|
632 /* |
|
633 ** Increment the r-tree reference count. |
|
634 */ |
|
635 static void rtreeReference(Rtree *pRtree){ |
|
636 pRtree->nBusy++; |
|
637 } |
|
638 |
|
639 /* |
|
640 ** Decrement the r-tree reference count. When the reference count reaches |
|
641 ** zero the structure is deleted. |
|
642 */ |
|
643 static void rtreeRelease(Rtree *pRtree){ |
|
644 pRtree->nBusy--; |
|
645 if( pRtree->nBusy==0 ){ |
|
646 sqlite3_finalize(pRtree->pReadNode); |
|
647 sqlite3_finalize(pRtree->pWriteNode); |
|
648 sqlite3_finalize(pRtree->pDeleteNode); |
|
649 sqlite3_finalize(pRtree->pReadRowid); |
|
650 sqlite3_finalize(pRtree->pWriteRowid); |
|
651 sqlite3_finalize(pRtree->pDeleteRowid); |
|
652 sqlite3_finalize(pRtree->pReadParent); |
|
653 sqlite3_finalize(pRtree->pWriteParent); |
|
654 sqlite3_finalize(pRtree->pDeleteParent); |
|
655 sqlite3_free(pRtree); |
|
656 } |
|
657 } |
|
658 |
|
659 /* |
|
660 ** Rtree virtual table module xDisconnect method. |
|
661 */ |
|
662 static int rtreeDisconnect(sqlite3_vtab *pVtab){ |
|
663 rtreeRelease((Rtree *)pVtab); |
|
664 return SQLITE_OK; |
|
665 } |
|
666 |
|
667 /* |
|
668 ** Rtree virtual table module xDestroy method. |
|
669 */ |
|
670 static int rtreeDestroy(sqlite3_vtab *pVtab){ |
|
671 Rtree *pRtree = (Rtree *)pVtab; |
|
672 int rc; |
|
673 char *zCreate = sqlite3_mprintf( |
|
674 "DROP TABLE '%q'.'%q_node';" |
|
675 "DROP TABLE '%q'.'%q_rowid';" |
|
676 "DROP TABLE '%q'.'%q_parent';", |
|
677 pRtree->zDb, pRtree->zName, |
|
678 pRtree->zDb, pRtree->zName, |
|
679 pRtree->zDb, pRtree->zName |
|
680 ); |
|
681 if( !zCreate ){ |
|
682 rc = SQLITE_NOMEM; |
|
683 }else{ |
|
684 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); |
|
685 sqlite3_free(zCreate); |
|
686 } |
|
687 if( rc==SQLITE_OK ){ |
|
688 rtreeRelease(pRtree); |
|
689 } |
|
690 |
|
691 return rc; |
|
692 } |
|
693 |
|
694 /* |
|
695 ** Rtree virtual table module xOpen method. |
|
696 */ |
|
697 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
|
698 int rc = SQLITE_NOMEM; |
|
699 RtreeCursor *pCsr; |
|
700 |
|
701 pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor)); |
|
702 if( pCsr ){ |
|
703 memset(pCsr, 0, sizeof(RtreeCursor)); |
|
704 pCsr->base.pVtab = pVTab; |
|
705 rc = SQLITE_OK; |
|
706 } |
|
707 *ppCursor = (sqlite3_vtab_cursor *)pCsr; |
|
708 |
|
709 return rc; |
|
710 } |
|
711 |
|
712 /* |
|
713 ** Rtree virtual table module xClose method. |
|
714 */ |
|
715 static int rtreeClose(sqlite3_vtab_cursor *cur){ |
|
716 Rtree *pRtree = (Rtree *)(cur->pVtab); |
|
717 int rc; |
|
718 RtreeCursor *pCsr = (RtreeCursor *)cur; |
|
719 sqlite3_free(pCsr->aConstraint); |
|
720 rc = nodeRelease(pRtree, pCsr->pNode); |
|
721 sqlite3_free(pCsr); |
|
722 return rc; |
|
723 } |
|
724 |
|
725 /* |
|
726 ** Rtree virtual table module xEof method. |
|
727 ** |
|
728 ** Return non-zero if the cursor does not currently point to a valid |
|
729 ** record (i.e if the scan has finished), or zero otherwise. |
|
730 */ |
|
731 static int rtreeEof(sqlite3_vtab_cursor *cur){ |
|
732 RtreeCursor *pCsr = (RtreeCursor *)cur; |
|
733 return (pCsr->pNode==0); |
|
734 } |
|
735 |
|
736 /* |
|
737 ** Cursor pCursor currently points to a cell in a non-leaf page. |
|
738 ** Return true if the sub-tree headed by the cell is filtered |
|
739 ** (excluded) by the constraints in the pCursor->aConstraint[] |
|
740 ** array, or false otherwise. |
|
741 */ |
|
742 static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){ |
|
743 RtreeCell cell; |
|
744 int ii; |
|
745 int bRes = 0; |
|
746 |
|
747 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); |
|
748 for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){ |
|
749 RtreeConstraint *p = &pCursor->aConstraint[ii]; |
|
750 double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]); |
|
751 double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]); |
|
752 |
|
753 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
|
754 || p->op==RTREE_GT || p->op==RTREE_EQ |
|
755 ); |
|
756 |
|
757 switch( p->op ){ |
|
758 case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break; |
|
759 case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break; |
|
760 case RTREE_EQ: |
|
761 bRes = (p->rValue>cell_max || p->rValue<cell_min); |
|
762 break; |
|
763 } |
|
764 } |
|
765 |
|
766 return bRes; |
|
767 } |
|
768 |
|
769 /* |
|
770 ** Return true if the cell that cursor pCursor currently points to |
|
771 ** would be filtered (excluded) by the constraints in the |
|
772 ** pCursor->aConstraint[] array, or false otherwise. |
|
773 ** |
|
774 ** This function assumes that the cell is part of a leaf node. |
|
775 */ |
|
776 static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){ |
|
777 RtreeCell cell; |
|
778 int ii; |
|
779 |
|
780 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); |
|
781 for(ii=0; ii<pCursor->nConstraint; ii++){ |
|
782 RtreeConstraint *p = &pCursor->aConstraint[ii]; |
|
783 double coord = DCOORD(cell.aCoord[p->iCoord]); |
|
784 int res; |
|
785 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
|
786 || p->op==RTREE_GT || p->op==RTREE_EQ |
|
787 ); |
|
788 switch( p->op ){ |
|
789 case RTREE_LE: res = (coord<=p->rValue); break; |
|
790 case RTREE_LT: res = (coord<p->rValue); break; |
|
791 case RTREE_GE: res = (coord>=p->rValue); break; |
|
792 case RTREE_GT: res = (coord>p->rValue); break; |
|
793 case RTREE_EQ: res = (coord==p->rValue); break; |
|
794 } |
|
795 |
|
796 if( !res ) return 1; |
|
797 } |
|
798 |
|
799 return 0; |
|
800 } |
|
801 |
|
802 /* |
|
803 ** Cursor pCursor currently points at a node that heads a sub-tree of |
|
804 ** height iHeight (if iHeight==0, then the node is a leaf). Descend |
|
805 ** to point to the left-most cell of the sub-tree that matches the |
|
806 ** configured constraints. |
|
807 */ |
|
808 static int descendToCell( |
|
809 Rtree *pRtree, |
|
810 RtreeCursor *pCursor, |
|
811 int iHeight, |
|
812 int *pEof /* OUT: Set to true if cannot descend */ |
|
813 ){ |
|
814 int isEof; |
|
815 int rc; |
|
816 int ii; |
|
817 RtreeNode *pChild; |
|
818 sqlite3_int64 iRowid; |
|
819 |
|
820 RtreeNode *pSavedNode = pCursor->pNode; |
|
821 int iSavedCell = pCursor->iCell; |
|
822 |
|
823 assert( iHeight>=0 ); |
|
824 |
|
825 if( iHeight==0 ){ |
|
826 isEof = testRtreeEntry(pRtree, pCursor); |
|
827 }else{ |
|
828 isEof = testRtreeCell(pRtree, pCursor); |
|
829 } |
|
830 if( isEof || iHeight==0 ){ |
|
831 *pEof = isEof; |
|
832 return SQLITE_OK; |
|
833 } |
|
834 |
|
835 iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell); |
|
836 rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild); |
|
837 if( rc!=SQLITE_OK ){ |
|
838 return rc; |
|
839 } |
|
840 |
|
841 nodeRelease(pRtree, pCursor->pNode); |
|
842 pCursor->pNode = pChild; |
|
843 isEof = 1; |
|
844 for(ii=0; isEof && ii<NCELL(pChild); ii++){ |
|
845 pCursor->iCell = ii; |
|
846 rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof); |
|
847 if( rc!=SQLITE_OK ){ |
|
848 return rc; |
|
849 } |
|
850 } |
|
851 |
|
852 if( isEof ){ |
|
853 assert( pCursor->pNode==pChild ); |
|
854 nodeReference(pSavedNode); |
|
855 nodeRelease(pRtree, pChild); |
|
856 pCursor->pNode = pSavedNode; |
|
857 pCursor->iCell = iSavedCell; |
|
858 } |
|
859 |
|
860 *pEof = isEof; |
|
861 return SQLITE_OK; |
|
862 } |
|
863 |
|
864 /* |
|
865 ** One of the cells in node pNode is guaranteed to have a 64-bit |
|
866 ** integer value equal to iRowid. Return the index of this cell. |
|
867 */ |
|
868 static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){ |
|
869 int ii; |
|
870 for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){ |
|
871 assert( ii<(NCELL(pNode)-1) ); |
|
872 } |
|
873 return ii; |
|
874 } |
|
875 |
|
876 /* |
|
877 ** Return the index of the cell containing a pointer to node pNode |
|
878 ** in its parent. If pNode is the root node, return -1. |
|
879 */ |
|
880 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){ |
|
881 RtreeNode *pParent = pNode->pParent; |
|
882 if( pParent ){ |
|
883 return nodeRowidIndex(pRtree, pParent, pNode->iNode); |
|
884 } |
|
885 return -1; |
|
886 } |
|
887 |
|
888 /* |
|
889 ** Rtree virtual table module xNext method. |
|
890 */ |
|
891 static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){ |
|
892 Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab); |
|
893 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
|
894 int rc = SQLITE_OK; |
|
895 |
|
896 if( pCsr->iStrategy==1 ){ |
|
897 /* This "scan" is a direct lookup by rowid. There is no next entry. */ |
|
898 nodeRelease(pRtree, pCsr->pNode); |
|
899 pCsr->pNode = 0; |
|
900 } |
|
901 |
|
902 else if( pCsr->pNode ){ |
|
903 /* Move to the next entry that matches the configured constraints. */ |
|
904 int iHeight = 0; |
|
905 while( pCsr->pNode ){ |
|
906 RtreeNode *pNode = pCsr->pNode; |
|
907 int nCell = NCELL(pNode); |
|
908 for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){ |
|
909 int isEof; |
|
910 rc = descendToCell(pRtree, pCsr, iHeight, &isEof); |
|
911 if( rc!=SQLITE_OK || !isEof ){ |
|
912 return rc; |
|
913 } |
|
914 } |
|
915 pCsr->pNode = pNode->pParent; |
|
916 pCsr->iCell = nodeParentIndex(pRtree, pNode); |
|
917 nodeReference(pCsr->pNode); |
|
918 nodeRelease(pRtree, pNode); |
|
919 iHeight++; |
|
920 } |
|
921 } |
|
922 |
|
923 return rc; |
|
924 } |
|
925 |
|
926 /* |
|
927 ** Rtree virtual table module xRowid method. |
|
928 */ |
|
929 static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ |
|
930 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; |
|
931 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
|
932 |
|
933 assert(pCsr->pNode); |
|
934 *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); |
|
935 |
|
936 return SQLITE_OK; |
|
937 } |
|
938 |
|
939 /* |
|
940 ** Rtree virtual table module xColumn method. |
|
941 */ |
|
942 static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ |
|
943 Rtree *pRtree = (Rtree *)cur->pVtab; |
|
944 RtreeCursor *pCsr = (RtreeCursor *)cur; |
|
945 |
|
946 if( i==0 ){ |
|
947 i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); |
|
948 sqlite3_result_int64(ctx, iRowid); |
|
949 }else{ |
|
950 RtreeCoord c; |
|
951 nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c); |
|
952 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
|
953 sqlite3_result_double(ctx, c.f); |
|
954 }else{ |
|
955 assert( pRtree->eCoordType==RTREE_COORD_INT32 ); |
|
956 sqlite3_result_int(ctx, c.i); |
|
957 } |
|
958 } |
|
959 |
|
960 return SQLITE_OK; |
|
961 } |
|
962 |
|
963 /* |
|
964 ** Use nodeAcquire() to obtain the leaf node containing the record with |
|
965 ** rowid iRowid. If successful, set *ppLeaf to point to the node and |
|
966 ** return SQLITE_OK. If there is no such record in the table, set |
|
967 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf |
|
968 ** to zero and return an SQLite error code. |
|
969 */ |
|
970 static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){ |
|
971 int rc; |
|
972 *ppLeaf = 0; |
|
973 sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid); |
|
974 if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){ |
|
975 i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0); |
|
976 rc = nodeAcquire(pRtree, iNode, 0, ppLeaf); |
|
977 sqlite3_reset(pRtree->pReadRowid); |
|
978 }else{ |
|
979 rc = sqlite3_reset(pRtree->pReadRowid); |
|
980 } |
|
981 return rc; |
|
982 } |
|
983 |
|
984 |
|
985 /* |
|
986 ** Rtree virtual table module xFilter method. |
|
987 */ |
|
988 static int rtreeFilter( |
|
989 sqlite3_vtab_cursor *pVtabCursor, |
|
990 int idxNum, const char *idxStr, |
|
991 int argc, sqlite3_value **argv |
|
992 ){ |
|
993 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; |
|
994 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; |
|
995 |
|
996 RtreeNode *pRoot = 0; |
|
997 int ii; |
|
998 int rc = SQLITE_OK; |
|
999 |
|
1000 rtreeReference(pRtree); |
|
1001 |
|
1002 sqlite3_free(pCsr->aConstraint); |
|
1003 pCsr->aConstraint = 0; |
|
1004 pCsr->iStrategy = idxNum; |
|
1005 |
|
1006 if( idxNum==1 ){ |
|
1007 /* Special case - lookup by rowid. */ |
|
1008 RtreeNode *pLeaf; /* Leaf on which the required cell resides */ |
|
1009 i64 iRowid = sqlite3_value_int64(argv[0]); |
|
1010 rc = findLeafNode(pRtree, iRowid, &pLeaf); |
|
1011 pCsr->pNode = pLeaf; |
|
1012 if( pLeaf && rc==SQLITE_OK ){ |
|
1013 pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid); |
|
1014 } |
|
1015 }else{ |
|
1016 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array |
|
1017 ** with the configured constraints. |
|
1018 */ |
|
1019 if( argc>0 ){ |
|
1020 pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc); |
|
1021 pCsr->nConstraint = argc; |
|
1022 if( !pCsr->aConstraint ){ |
|
1023 rc = SQLITE_NOMEM; |
|
1024 }else{ |
|
1025 assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 ); |
|
1026 for(ii=0; ii<argc; ii++){ |
|
1027 RtreeConstraint *p = &pCsr->aConstraint[ii]; |
|
1028 p->op = idxStr[ii*2]; |
|
1029 p->iCoord = idxStr[ii*2+1]-'a'; |
|
1030 p->rValue = sqlite3_value_double(argv[ii]); |
|
1031 } |
|
1032 } |
|
1033 } |
|
1034 |
|
1035 if( rc==SQLITE_OK ){ |
|
1036 pCsr->pNode = 0; |
|
1037 rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
|
1038 } |
|
1039 if( rc==SQLITE_OK ){ |
|
1040 int isEof = 1; |
|
1041 int nCell = NCELL(pRoot); |
|
1042 pCsr->pNode = pRoot; |
|
1043 for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){ |
|
1044 assert( pCsr->pNode==pRoot ); |
|
1045 rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof); |
|
1046 if( !isEof ){ |
|
1047 break; |
|
1048 } |
|
1049 } |
|
1050 if( rc==SQLITE_OK && isEof ){ |
|
1051 assert( pCsr->pNode==pRoot ); |
|
1052 nodeRelease(pRtree, pRoot); |
|
1053 pCsr->pNode = 0; |
|
1054 } |
|
1055 assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) ); |
|
1056 } |
|
1057 } |
|
1058 |
|
1059 rtreeRelease(pRtree); |
|
1060 return rc; |
|
1061 } |
|
1062 |
|
1063 /* |
|
1064 ** Rtree virtual table module xBestIndex method. There are three |
|
1065 ** table scan strategies to choose from (in order from most to |
|
1066 ** least desirable): |
|
1067 ** |
|
1068 ** idxNum idxStr Strategy |
|
1069 ** ------------------------------------------------ |
|
1070 ** 1 Unused Direct lookup by rowid. |
|
1071 ** 2 See below R-tree query. |
|
1072 ** 3 Unused Full table scan. |
|
1073 ** ------------------------------------------------ |
|
1074 ** |
|
1075 ** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy |
|
1076 ** 2 is used, idxStr is formatted to contain 2 bytes for each |
|
1077 ** constraint used. The first two bytes of idxStr correspond to |
|
1078 ** the constraint in sqlite3_index_info.aConstraintUsage[] with |
|
1079 ** (argvIndex==1) etc. |
|
1080 ** |
|
1081 ** The first of each pair of bytes in idxStr identifies the constraint |
|
1082 ** operator as follows: |
|
1083 ** |
|
1084 ** Operator Byte Value |
|
1085 ** ---------------------- |
|
1086 ** = 0x41 ('A') |
|
1087 ** <= 0x42 ('B') |
|
1088 ** < 0x43 ('C') |
|
1089 ** >= 0x44 ('D') |
|
1090 ** > 0x45 ('E') |
|
1091 ** ---------------------- |
|
1092 ** |
|
1093 ** The second of each pair of bytes identifies the coordinate column |
|
1094 ** to which the constraint applies. The leftmost coordinate column |
|
1095 ** is 'a', the second from the left 'b' etc. |
|
1096 */ |
|
1097 static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ |
|
1098 int rc = SQLITE_OK; |
|
1099 int ii, cCol; |
|
1100 |
|
1101 int iIdx = 0; |
|
1102 char zIdxStr[RTREE_MAX_DIMENSIONS*8+1]; |
|
1103 memset(zIdxStr, 0, sizeof(zIdxStr)); |
|
1104 |
|
1105 assert( pIdxInfo->idxStr==0 ); |
|
1106 for(ii=0; ii<pIdxInfo->nConstraint; ii++){ |
|
1107 struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii]; |
|
1108 |
|
1109 if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){ |
|
1110 /* We have an equality constraint on the rowid. Use strategy 1. */ |
|
1111 int jj; |
|
1112 for(jj=0; jj<ii; jj++){ |
|
1113 pIdxInfo->aConstraintUsage[jj].argvIndex = 0; |
|
1114 pIdxInfo->aConstraintUsage[jj].omit = 0; |
|
1115 } |
|
1116 pIdxInfo->idxNum = 1; |
|
1117 pIdxInfo->aConstraintUsage[ii].argvIndex = 1; |
|
1118 pIdxInfo->aConstraintUsage[jj].omit = 1; |
|
1119 |
|
1120 /* This strategy involves a two rowid lookups on an B-Tree structures |
|
1121 ** and then a linear search of an R-Tree node. This should be |
|
1122 ** considered almost as quick as a direct rowid lookup (for which |
|
1123 ** sqlite uses an internal cost of 0.0). |
|
1124 */ |
|
1125 pIdxInfo->estimatedCost = 10.0; |
|
1126 return SQLITE_OK; |
|
1127 } |
|
1128 |
|
1129 if( p->usable && p->iColumn>0 ){ |
|
1130 u8 op = 0; |
|
1131 switch( p->op ){ |
|
1132 case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break; |
|
1133 case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break; |
|
1134 case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break; |
|
1135 case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break; |
|
1136 case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; |
|
1137 } |
|
1138 if( op ){ |
|
1139 /* Make sure this particular constraint has not been used before. |
|
1140 ** If it has been used before, ignore it. |
|
1141 ** |
|
1142 ** A <= or < can be used if there is a prior >= or >. |
|
1143 ** A >= or > can be used if there is a prior < or <=. |
|
1144 ** A <= or < is disqualified if there is a prior <=, <, or ==. |
|
1145 ** A >= or > is disqualified if there is a prior >=, >, or ==. |
|
1146 ** A == is disqualifed if there is any prior constraint. |
|
1147 */ |
|
1148 int j, opmsk; |
|
1149 static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 }; |
|
1150 assert( compatible[RTREE_EQ & 7]==0 ); |
|
1151 assert( compatible[RTREE_LT & 7]==1 ); |
|
1152 assert( compatible[RTREE_LE & 7]==1 ); |
|
1153 assert( compatible[RTREE_GT & 7]==2 ); |
|
1154 assert( compatible[RTREE_GE & 7]==2 ); |
|
1155 cCol = p->iColumn - 1 + 'a'; |
|
1156 opmsk = compatible[op & 7]; |
|
1157 for(j=0; j<iIdx; j+=2){ |
|
1158 if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){ |
|
1159 op = 0; |
|
1160 break; |
|
1161 } |
|
1162 } |
|
1163 } |
|
1164 if( op ){ |
|
1165 assert( iIdx<sizeof(zIdxStr)-1 ); |
|
1166 zIdxStr[iIdx++] = op; |
|
1167 zIdxStr[iIdx++] = cCol; |
|
1168 pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); |
|
1169 pIdxInfo->aConstraintUsage[ii].omit = 1; |
|
1170 } |
|
1171 } |
|
1172 } |
|
1173 |
|
1174 pIdxInfo->idxNum = 2; |
|
1175 pIdxInfo->needToFreeIdxStr = 1; |
|
1176 if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ |
|
1177 return SQLITE_NOMEM; |
|
1178 } |
|
1179 assert( iIdx>=0 ); |
|
1180 pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1)); |
|
1181 return rc; |
|
1182 } |
|
1183 |
|
1184 /* |
|
1185 ** Return the N-dimensional volumn of the cell stored in *p. |
|
1186 */ |
|
1187 static float cellArea(Rtree *pRtree, RtreeCell *p){ |
|
1188 float area = 1.0; |
|
1189 int ii; |
|
1190 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
1191 area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
|
1192 } |
|
1193 return area; |
|
1194 } |
|
1195 |
|
1196 /* |
|
1197 ** Return the margin length of cell p. The margin length is the sum |
|
1198 ** of the objects size in each dimension. |
|
1199 */ |
|
1200 static float cellMargin(Rtree *pRtree, RtreeCell *p){ |
|
1201 float margin = 0.0; |
|
1202 int ii; |
|
1203 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
1204 margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
|
1205 } |
|
1206 return margin; |
|
1207 } |
|
1208 |
|
1209 /* |
|
1210 ** Store the union of cells p1 and p2 in p1. |
|
1211 */ |
|
1212 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
|
1213 int ii; |
|
1214 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
|
1215 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
1216 p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); |
|
1217 p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); |
|
1218 } |
|
1219 }else{ |
|
1220 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
1221 p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); |
|
1222 p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); |
|
1223 } |
|
1224 } |
|
1225 } |
|
1226 |
|
1227 /* |
|
1228 ** Return true if the area covered by p2 is a subset of the area covered |
|
1229 ** by p1. False otherwise. |
|
1230 */ |
|
1231 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
|
1232 int ii; |
|
1233 int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); |
|
1234 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
1235 RtreeCoord *a1 = &p1->aCoord[ii]; |
|
1236 RtreeCoord *a2 = &p2->aCoord[ii]; |
|
1237 if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) |
|
1238 || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) |
|
1239 ){ |
|
1240 return 0; |
|
1241 } |
|
1242 } |
|
1243 return 1; |
|
1244 } |
|
1245 |
|
1246 /* |
|
1247 ** Return the amount cell p would grow by if it were unioned with pCell. |
|
1248 */ |
|
1249 static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ |
|
1250 float area; |
|
1251 RtreeCell cell; |
|
1252 memcpy(&cell, p, sizeof(RtreeCell)); |
|
1253 area = cellArea(pRtree, &cell); |
|
1254 cellUnion(pRtree, &cell, pCell); |
|
1255 return (cellArea(pRtree, &cell)-area); |
|
1256 } |
|
1257 |
|
1258 #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT |
|
1259 static float cellOverlap( |
|
1260 Rtree *pRtree, |
|
1261 RtreeCell *p, |
|
1262 RtreeCell *aCell, |
|
1263 int nCell, |
|
1264 int iExclude |
|
1265 ){ |
|
1266 int ii; |
|
1267 float overlap = 0.0; |
|
1268 for(ii=0; ii<nCell; ii++){ |
|
1269 if( ii!=iExclude ){ |
|
1270 int jj; |
|
1271 float o = 1.0; |
|
1272 for(jj=0; jj<(pRtree->nDim*2); jj+=2){ |
|
1273 double x1; |
|
1274 double x2; |
|
1275 |
|
1276 x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); |
|
1277 x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); |
|
1278 |
|
1279 if( x2<x1 ){ |
|
1280 o = 0.0; |
|
1281 break; |
|
1282 }else{ |
|
1283 o = o * (x2-x1); |
|
1284 } |
|
1285 } |
|
1286 overlap += o; |
|
1287 } |
|
1288 } |
|
1289 return overlap; |
|
1290 } |
|
1291 #endif |
|
1292 |
|
1293 #if VARIANT_RSTARTREE_CHOOSESUBTREE |
|
1294 static float cellOverlapEnlargement( |
|
1295 Rtree *pRtree, |
|
1296 RtreeCell *p, |
|
1297 RtreeCell *pInsert, |
|
1298 RtreeCell *aCell, |
|
1299 int nCell, |
|
1300 int iExclude |
|
1301 ){ |
|
1302 float before; |
|
1303 float after; |
|
1304 before = cellOverlap(pRtree, p, aCell, nCell, iExclude); |
|
1305 cellUnion(pRtree, p, pInsert); |
|
1306 after = cellOverlap(pRtree, p, aCell, nCell, iExclude); |
|
1307 return after-before; |
|
1308 } |
|
1309 #endif |
|
1310 |
|
1311 |
|
1312 /* |
|
1313 ** This function implements the ChooseLeaf algorithm from Gutman[84]. |
|
1314 ** ChooseSubTree in r*tree terminology. |
|
1315 */ |
|
1316 static int ChooseLeaf( |
|
1317 Rtree *pRtree, /* Rtree table */ |
|
1318 RtreeCell *pCell, /* Cell to insert into rtree */ |
|
1319 int iHeight, /* Height of sub-tree rooted at pCell */ |
|
1320 RtreeNode **ppLeaf /* OUT: Selected leaf page */ |
|
1321 ){ |
|
1322 int rc; |
|
1323 int ii; |
|
1324 RtreeNode *pNode; |
|
1325 rc = nodeAcquire(pRtree, 1, 0, &pNode); |
|
1326 |
|
1327 for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ |
|
1328 int iCell; |
|
1329 sqlite3_int64 iBest; |
|
1330 |
|
1331 float fMinGrowth; |
|
1332 float fMinArea; |
|
1333 float fMinOverlap; |
|
1334 |
|
1335 int nCell = NCELL(pNode); |
|
1336 RtreeCell cell; |
|
1337 RtreeNode *pChild; |
|
1338 |
|
1339 RtreeCell *aCell = 0; |
|
1340 |
|
1341 #if VARIANT_RSTARTREE_CHOOSESUBTREE |
|
1342 if( ii==(pRtree->iDepth-1) ){ |
|
1343 int jj; |
|
1344 aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell); |
|
1345 if( !aCell ){ |
|
1346 rc = SQLITE_NOMEM; |
|
1347 nodeRelease(pRtree, pNode); |
|
1348 pNode = 0; |
|
1349 continue; |
|
1350 } |
|
1351 for(jj=0; jj<nCell; jj++){ |
|
1352 nodeGetCell(pRtree, pNode, jj, &aCell[jj]); |
|
1353 } |
|
1354 } |
|
1355 #endif |
|
1356 |
|
1357 /* Select the child node which will be enlarged the least if pCell |
|
1358 ** is inserted into it. Resolve ties by choosing the entry with |
|
1359 ** the smallest area. |
|
1360 */ |
|
1361 for(iCell=0; iCell<nCell; iCell++){ |
|
1362 float growth; |
|
1363 float area; |
|
1364 float overlap = 0.0; |
|
1365 nodeGetCell(pRtree, pNode, iCell, &cell); |
|
1366 growth = cellGrowth(pRtree, &cell, pCell); |
|
1367 area = cellArea(pRtree, &cell); |
|
1368 #if VARIANT_RSTARTREE_CHOOSESUBTREE |
|
1369 if( ii==(pRtree->iDepth-1) ){ |
|
1370 overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell); |
|
1371 } |
|
1372 #endif |
|
1373 if( (iCell==0) |
|
1374 || (overlap<fMinOverlap) |
|
1375 || (overlap==fMinOverlap && growth<fMinGrowth) |
|
1376 || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea) |
|
1377 ){ |
|
1378 fMinOverlap = overlap; |
|
1379 fMinGrowth = growth; |
|
1380 fMinArea = area; |
|
1381 iBest = cell.iRowid; |
|
1382 } |
|
1383 } |
|
1384 |
|
1385 sqlite3_free(aCell); |
|
1386 rc = nodeAcquire(pRtree, iBest, pNode, &pChild); |
|
1387 nodeRelease(pRtree, pNode); |
|
1388 pNode = pChild; |
|
1389 } |
|
1390 |
|
1391 *ppLeaf = pNode; |
|
1392 return rc; |
|
1393 } |
|
1394 |
|
1395 /* |
|
1396 ** A cell with the same content as pCell has just been inserted into |
|
1397 ** the node pNode. This function updates the bounding box cells in |
|
1398 ** all ancestor elements. |
|
1399 */ |
|
1400 static void AdjustTree( |
|
1401 Rtree *pRtree, /* Rtree table */ |
|
1402 RtreeNode *pNode, /* Adjust ancestry of this node. */ |
|
1403 RtreeCell *pCell /* This cell was just inserted */ |
|
1404 ){ |
|
1405 RtreeNode *p = pNode; |
|
1406 while( p->pParent ){ |
|
1407 RtreeCell cell; |
|
1408 RtreeNode *pParent = p->pParent; |
|
1409 int iCell = nodeParentIndex(pRtree, p); |
|
1410 |
|
1411 nodeGetCell(pRtree, pParent, iCell, &cell); |
|
1412 if( !cellContains(pRtree, &cell, pCell) ){ |
|
1413 cellUnion(pRtree, &cell, pCell); |
|
1414 nodeOverwriteCell(pRtree, pParent, &cell, iCell); |
|
1415 } |
|
1416 |
|
1417 p = pParent; |
|
1418 } |
|
1419 } |
|
1420 |
|
1421 /* |
|
1422 ** Write mapping (iRowid->iNode) to the <rtree>_rowid table. |
|
1423 */ |
|
1424 static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){ |
|
1425 sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid); |
|
1426 sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode); |
|
1427 sqlite3_step(pRtree->pWriteRowid); |
|
1428 return sqlite3_reset(pRtree->pWriteRowid); |
|
1429 } |
|
1430 |
|
1431 /* |
|
1432 ** Write mapping (iNode->iPar) to the <rtree>_parent table. |
|
1433 */ |
|
1434 static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){ |
|
1435 sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode); |
|
1436 sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); |
|
1437 sqlite3_step(pRtree->pWriteParent); |
|
1438 return sqlite3_reset(pRtree->pWriteParent); |
|
1439 } |
|
1440 |
|
1441 static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int); |
|
1442 |
|
1443 #if VARIANT_GUTTMAN_LINEAR_SPLIT |
|
1444 /* |
|
1445 ** Implementation of the linear variant of the PickNext() function from |
|
1446 ** Guttman[84]. |
|
1447 */ |
|
1448 static RtreeCell *LinearPickNext( |
|
1449 Rtree *pRtree, |
|
1450 RtreeCell *aCell, |
|
1451 int nCell, |
|
1452 RtreeCell *pLeftBox, |
|
1453 RtreeCell *pRightBox, |
|
1454 int *aiUsed |
|
1455 ){ |
|
1456 int ii; |
|
1457 for(ii=0; aiUsed[ii]; ii++); |
|
1458 aiUsed[ii] = 1; |
|
1459 return &aCell[ii]; |
|
1460 } |
|
1461 |
|
1462 /* |
|
1463 ** Implementation of the linear variant of the PickSeeds() function from |
|
1464 ** Guttman[84]. |
|
1465 */ |
|
1466 static void LinearPickSeeds( |
|
1467 Rtree *pRtree, |
|
1468 RtreeCell *aCell, |
|
1469 int nCell, |
|
1470 int *piLeftSeed, |
|
1471 int *piRightSeed |
|
1472 ){ |
|
1473 int i; |
|
1474 int iLeftSeed = 0; |
|
1475 int iRightSeed = 1; |
|
1476 float maxNormalInnerWidth = 0.0; |
|
1477 |
|
1478 /* Pick two "seed" cells from the array of cells. The algorithm used |
|
1479 ** here is the LinearPickSeeds algorithm from Gutman[1984]. The |
|
1480 ** indices of the two seed cells in the array are stored in local |
|
1481 ** variables iLeftSeek and iRightSeed. |
|
1482 */ |
|
1483 for(i=0; i<pRtree->nDim; i++){ |
|
1484 float x1 = aCell[0].aCoord[i*2]; |
|
1485 float x2 = aCell[0].aCoord[i*2+1]; |
|
1486 float x3 = x1; |
|
1487 float x4 = x2; |
|
1488 int jj; |
|
1489 |
|
1490 int iCellLeft = 0; |
|
1491 int iCellRight = 0; |
|
1492 |
|
1493 for(jj=1; jj<nCell; jj++){ |
|
1494 float left = aCell[jj].aCoord[i*2]; |
|
1495 float right = aCell[jj].aCoord[i*2+1]; |
|
1496 |
|
1497 if( left<x1 ) x1 = left; |
|
1498 if( right>x4 ) x4 = right; |
|
1499 if( left>x3 ){ |
|
1500 x3 = left; |
|
1501 iCellRight = jj; |
|
1502 } |
|
1503 if( right<x2 ){ |
|
1504 x2 = right; |
|
1505 iCellLeft = jj; |
|
1506 } |
|
1507 } |
|
1508 |
|
1509 if( x4!=x1 ){ |
|
1510 float normalwidth = (x3 - x2) / (x4 - x1); |
|
1511 if( normalwidth>maxNormalInnerWidth ){ |
|
1512 iLeftSeed = iCellLeft; |
|
1513 iRightSeed = iCellRight; |
|
1514 } |
|
1515 } |
|
1516 } |
|
1517 |
|
1518 *piLeftSeed = iLeftSeed; |
|
1519 *piRightSeed = iRightSeed; |
|
1520 } |
|
1521 #endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */ |
|
1522 |
|
1523 #if VARIANT_GUTTMAN_QUADRATIC_SPLIT |
|
1524 /* |
|
1525 ** Implementation of the quadratic variant of the PickNext() function from |
|
1526 ** Guttman[84]. |
|
1527 */ |
|
1528 static RtreeCell *QuadraticPickNext( |
|
1529 Rtree *pRtree, |
|
1530 RtreeCell *aCell, |
|
1531 int nCell, |
|
1532 RtreeCell *pLeftBox, |
|
1533 RtreeCell *pRightBox, |
|
1534 int *aiUsed |
|
1535 ){ |
|
1536 #define FABS(a) ((a)<0.0?-1.0*(a):(a)) |
|
1537 |
|
1538 int iSelect = -1; |
|
1539 float fDiff; |
|
1540 int ii; |
|
1541 for(ii=0; ii<nCell; ii++){ |
|
1542 if( aiUsed[ii]==0 ){ |
|
1543 float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]); |
|
1544 float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]); |
|
1545 float diff = FABS(right-left); |
|
1546 if( iSelect<0 || diff>fDiff ){ |
|
1547 fDiff = diff; |
|
1548 iSelect = ii; |
|
1549 } |
|
1550 } |
|
1551 } |
|
1552 aiUsed[iSelect] = 1; |
|
1553 return &aCell[iSelect]; |
|
1554 } |
|
1555 |
|
1556 /* |
|
1557 ** Implementation of the quadratic variant of the PickSeeds() function from |
|
1558 ** Guttman[84]. |
|
1559 */ |
|
1560 static void QuadraticPickSeeds( |
|
1561 Rtree *pRtree, |
|
1562 RtreeCell *aCell, |
|
1563 int nCell, |
|
1564 int *piLeftSeed, |
|
1565 int *piRightSeed |
|
1566 ){ |
|
1567 int ii; |
|
1568 int jj; |
|
1569 |
|
1570 int iLeftSeed = 0; |
|
1571 int iRightSeed = 1; |
|
1572 float fWaste = 0.0; |
|
1573 |
|
1574 for(ii=0; ii<nCell; ii++){ |
|
1575 for(jj=ii+1; jj<nCell; jj++){ |
|
1576 float right = cellArea(pRtree, &aCell[jj]); |
|
1577 float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]); |
|
1578 float waste = growth - right; |
|
1579 |
|
1580 if( waste>fWaste ){ |
|
1581 iLeftSeed = ii; |
|
1582 iRightSeed = jj; |
|
1583 fWaste = waste; |
|
1584 } |
|
1585 } |
|
1586 } |
|
1587 |
|
1588 *piLeftSeed = iLeftSeed; |
|
1589 *piRightSeed = iRightSeed; |
|
1590 } |
|
1591 #endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */ |
|
1592 |
|
1593 /* |
|
1594 ** Arguments aIdx, aDistance and aSpare all point to arrays of size |
|
1595 ** nIdx. The aIdx array contains the set of integers from 0 to |
|
1596 ** (nIdx-1) in no particular order. This function sorts the values |
|
1597 ** in aIdx according to the indexed values in aDistance. For |
|
1598 ** example, assuming the inputs: |
|
1599 ** |
|
1600 ** aIdx = { 0, 1, 2, 3 } |
|
1601 ** aDistance = { 5.0, 2.0, 7.0, 6.0 } |
|
1602 ** |
|
1603 ** this function sets the aIdx array to contain: |
|
1604 ** |
|
1605 ** aIdx = { 0, 1, 2, 3 } |
|
1606 ** |
|
1607 ** The aSpare array is used as temporary working space by the |
|
1608 ** sorting algorithm. |
|
1609 */ |
|
1610 static void SortByDistance( |
|
1611 int *aIdx, |
|
1612 int nIdx, |
|
1613 float *aDistance, |
|
1614 int *aSpare |
|
1615 ){ |
|
1616 if( nIdx>1 ){ |
|
1617 int iLeft = 0; |
|
1618 int iRight = 0; |
|
1619 |
|
1620 int nLeft = nIdx/2; |
|
1621 int nRight = nIdx-nLeft; |
|
1622 int *aLeft = aIdx; |
|
1623 int *aRight = &aIdx[nLeft]; |
|
1624 |
|
1625 SortByDistance(aLeft, nLeft, aDistance, aSpare); |
|
1626 SortByDistance(aRight, nRight, aDistance, aSpare); |
|
1627 |
|
1628 memcpy(aSpare, aLeft, sizeof(int)*nLeft); |
|
1629 aLeft = aSpare; |
|
1630 |
|
1631 while( iLeft<nLeft || iRight<nRight ){ |
|
1632 if( iLeft==nLeft ){ |
|
1633 aIdx[iLeft+iRight] = aRight[iRight]; |
|
1634 iRight++; |
|
1635 }else if( iRight==nRight ){ |
|
1636 aIdx[iLeft+iRight] = aLeft[iLeft]; |
|
1637 iLeft++; |
|
1638 }else{ |
|
1639 float fLeft = aDistance[aLeft[iLeft]]; |
|
1640 float fRight = aDistance[aRight[iRight]]; |
|
1641 if( fLeft<fRight ){ |
|
1642 aIdx[iLeft+iRight] = aLeft[iLeft]; |
|
1643 iLeft++; |
|
1644 }else{ |
|
1645 aIdx[iLeft+iRight] = aRight[iRight]; |
|
1646 iRight++; |
|
1647 } |
|
1648 } |
|
1649 } |
|
1650 |
|
1651 #if 0 |
|
1652 /* Check that the sort worked */ |
|
1653 { |
|
1654 int jj; |
|
1655 for(jj=1; jj<nIdx; jj++){ |
|
1656 float left = aDistance[aIdx[jj-1]]; |
|
1657 float right = aDistance[aIdx[jj]]; |
|
1658 assert( left<=right ); |
|
1659 } |
|
1660 } |
|
1661 #endif |
|
1662 } |
|
1663 } |
|
1664 |
|
1665 /* |
|
1666 ** Arguments aIdx, aCell and aSpare all point to arrays of size |
|
1667 ** nIdx. The aIdx array contains the set of integers from 0 to |
|
1668 ** (nIdx-1) in no particular order. This function sorts the values |
|
1669 ** in aIdx according to dimension iDim of the cells in aCell. The |
|
1670 ** minimum value of dimension iDim is considered first, the |
|
1671 ** maximum used to break ties. |
|
1672 ** |
|
1673 ** The aSpare array is used as temporary working space by the |
|
1674 ** sorting algorithm. |
|
1675 */ |
|
1676 static void SortByDimension( |
|
1677 Rtree *pRtree, |
|
1678 int *aIdx, |
|
1679 int nIdx, |
|
1680 int iDim, |
|
1681 RtreeCell *aCell, |
|
1682 int *aSpare |
|
1683 ){ |
|
1684 if( nIdx>1 ){ |
|
1685 |
|
1686 int iLeft = 0; |
|
1687 int iRight = 0; |
|
1688 |
|
1689 int nLeft = nIdx/2; |
|
1690 int nRight = nIdx-nLeft; |
|
1691 int *aLeft = aIdx; |
|
1692 int *aRight = &aIdx[nLeft]; |
|
1693 |
|
1694 SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare); |
|
1695 SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare); |
|
1696 |
|
1697 memcpy(aSpare, aLeft, sizeof(int)*nLeft); |
|
1698 aLeft = aSpare; |
|
1699 while( iLeft<nLeft || iRight<nRight ){ |
|
1700 double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]); |
|
1701 double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]); |
|
1702 double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]); |
|
1703 double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]); |
|
1704 if( (iLeft!=nLeft) && ((iRight==nRight) |
|
1705 || (xleft1<xright1) |
|
1706 || (xleft1==xright1 && xleft2<xright2) |
|
1707 )){ |
|
1708 aIdx[iLeft+iRight] = aLeft[iLeft]; |
|
1709 iLeft++; |
|
1710 }else{ |
|
1711 aIdx[iLeft+iRight] = aRight[iRight]; |
|
1712 iRight++; |
|
1713 } |
|
1714 } |
|
1715 |
|
1716 #if 0 |
|
1717 /* Check that the sort worked */ |
|
1718 { |
|
1719 int jj; |
|
1720 for(jj=1; jj<nIdx; jj++){ |
|
1721 float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; |
|
1722 float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; |
|
1723 float xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; |
|
1724 float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; |
|
1725 assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); |
|
1726 } |
|
1727 } |
|
1728 #endif |
|
1729 } |
|
1730 } |
|
1731 |
|
1732 #if VARIANT_RSTARTREE_SPLIT |
|
1733 /* |
|
1734 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990]. |
|
1735 */ |
|
1736 static int splitNodeStartree( |
|
1737 Rtree *pRtree, |
|
1738 RtreeCell *aCell, |
|
1739 int nCell, |
|
1740 RtreeNode *pLeft, |
|
1741 RtreeNode *pRight, |
|
1742 RtreeCell *pBboxLeft, |
|
1743 RtreeCell *pBboxRight |
|
1744 ){ |
|
1745 int **aaSorted; |
|
1746 int *aSpare; |
|
1747 int ii; |
|
1748 |
|
1749 int iBestDim; |
|
1750 int iBestSplit; |
|
1751 float fBestMargin; |
|
1752 |
|
1753 int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); |
|
1754 |
|
1755 aaSorted = (int **)sqlite3_malloc(nByte); |
|
1756 if( !aaSorted ){ |
|
1757 return SQLITE_NOMEM; |
|
1758 } |
|
1759 |
|
1760 aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell]; |
|
1761 memset(aaSorted, 0, nByte); |
|
1762 for(ii=0; ii<pRtree->nDim; ii++){ |
|
1763 int jj; |
|
1764 aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; |
|
1765 for(jj=0; jj<nCell; jj++){ |
|
1766 aaSorted[ii][jj] = jj; |
|
1767 } |
|
1768 SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); |
|
1769 } |
|
1770 |
|
1771 for(ii=0; ii<pRtree->nDim; ii++){ |
|
1772 float margin = 0.0; |
|
1773 float fBestOverlap; |
|
1774 float fBestArea; |
|
1775 int iBestLeft; |
|
1776 int nLeft; |
|
1777 |
|
1778 for( |
|
1779 nLeft=RTREE_MINCELLS(pRtree); |
|
1780 nLeft<=(nCell-RTREE_MINCELLS(pRtree)); |
|
1781 nLeft++ |
|
1782 ){ |
|
1783 RtreeCell left; |
|
1784 RtreeCell right; |
|
1785 int kk; |
|
1786 float overlap; |
|
1787 float area; |
|
1788 |
|
1789 memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell)); |
|
1790 memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell)); |
|
1791 for(kk=1; kk<(nCell-1); kk++){ |
|
1792 if( kk<nLeft ){ |
|
1793 cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); |
|
1794 }else{ |
|
1795 cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); |
|
1796 } |
|
1797 } |
|
1798 margin += cellMargin(pRtree, &left); |
|
1799 margin += cellMargin(pRtree, &right); |
|
1800 overlap = cellOverlap(pRtree, &left, &right, 1, -1); |
|
1801 area = cellArea(pRtree, &left) + cellArea(pRtree, &right); |
|
1802 if( (nLeft==RTREE_MINCELLS(pRtree)) |
|
1803 || (overlap<fBestOverlap) |
|
1804 || (overlap==fBestOverlap && area<fBestArea) |
|
1805 ){ |
|
1806 iBestLeft = nLeft; |
|
1807 fBestOverlap = overlap; |
|
1808 fBestArea = area; |
|
1809 } |
|
1810 } |
|
1811 |
|
1812 if( ii==0 || margin<fBestMargin ){ |
|
1813 iBestDim = ii; |
|
1814 fBestMargin = margin; |
|
1815 iBestSplit = iBestLeft; |
|
1816 } |
|
1817 } |
|
1818 |
|
1819 memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell)); |
|
1820 memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell)); |
|
1821 for(ii=0; ii<nCell; ii++){ |
|
1822 RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight; |
|
1823 RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight; |
|
1824 RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]]; |
|
1825 nodeInsertCell(pRtree, pTarget, pCell); |
|
1826 cellUnion(pRtree, pBbox, pCell); |
|
1827 } |
|
1828 |
|
1829 sqlite3_free(aaSorted); |
|
1830 return SQLITE_OK; |
|
1831 } |
|
1832 #endif |
|
1833 |
|
1834 #if VARIANT_GUTTMAN_SPLIT |
|
1835 /* |
|
1836 ** Implementation of the regular R-tree SplitNode from Guttman[1984]. |
|
1837 */ |
|
1838 static int splitNodeGuttman( |
|
1839 Rtree *pRtree, |
|
1840 RtreeCell *aCell, |
|
1841 int nCell, |
|
1842 RtreeNode *pLeft, |
|
1843 RtreeNode *pRight, |
|
1844 RtreeCell *pBboxLeft, |
|
1845 RtreeCell *pBboxRight |
|
1846 ){ |
|
1847 int iLeftSeed = 0; |
|
1848 int iRightSeed = 1; |
|
1849 int *aiUsed; |
|
1850 int i; |
|
1851 |
|
1852 aiUsed = sqlite3_malloc(sizeof(int)*nCell); |
|
1853 memset(aiUsed, 0, sizeof(int)*nCell); |
|
1854 |
|
1855 PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed); |
|
1856 |
|
1857 memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell)); |
|
1858 memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell)); |
|
1859 nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]); |
|
1860 nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]); |
|
1861 aiUsed[iLeftSeed] = 1; |
|
1862 aiUsed[iRightSeed] = 1; |
|
1863 |
|
1864 for(i=nCell-2; i>0; i--){ |
|
1865 RtreeCell *pNext; |
|
1866 pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed); |
|
1867 float diff = |
|
1868 cellGrowth(pRtree, pBboxLeft, pNext) - |
|
1869 cellGrowth(pRtree, pBboxRight, pNext) |
|
1870 ; |
|
1871 if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i) |
|
1872 || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i)) |
|
1873 ){ |
|
1874 nodeInsertCell(pRtree, pRight, pNext); |
|
1875 cellUnion(pRtree, pBboxRight, pNext); |
|
1876 }else{ |
|
1877 nodeInsertCell(pRtree, pLeft, pNext); |
|
1878 cellUnion(pRtree, pBboxLeft, pNext); |
|
1879 } |
|
1880 } |
|
1881 |
|
1882 sqlite3_free(aiUsed); |
|
1883 return SQLITE_OK; |
|
1884 } |
|
1885 #endif |
|
1886 |
|
1887 static int updateMapping( |
|
1888 Rtree *pRtree, |
|
1889 i64 iRowid, |
|
1890 RtreeNode *pNode, |
|
1891 int iHeight |
|
1892 ){ |
|
1893 int (*xSetMapping)(Rtree *, sqlite3_int64, sqlite3_int64); |
|
1894 xSetMapping = ((iHeight==0)?rowidWrite:parentWrite); |
|
1895 if( iHeight>0 ){ |
|
1896 RtreeNode *pChild = nodeHashLookup(pRtree, iRowid); |
|
1897 if( pChild ){ |
|
1898 nodeRelease(pRtree, pChild->pParent); |
|
1899 nodeReference(pNode); |
|
1900 pChild->pParent = pNode; |
|
1901 } |
|
1902 } |
|
1903 return xSetMapping(pRtree, iRowid, pNode->iNode); |
|
1904 } |
|
1905 |
|
1906 static int SplitNode( |
|
1907 Rtree *pRtree, |
|
1908 RtreeNode *pNode, |
|
1909 RtreeCell *pCell, |
|
1910 int iHeight |
|
1911 ){ |
|
1912 int i; |
|
1913 int newCellIsRight = 0; |
|
1914 |
|
1915 int rc = SQLITE_OK; |
|
1916 int nCell = NCELL(pNode); |
|
1917 RtreeCell *aCell; |
|
1918 int *aiUsed; |
|
1919 |
|
1920 RtreeNode *pLeft = 0; |
|
1921 RtreeNode *pRight = 0; |
|
1922 |
|
1923 RtreeCell leftbbox; |
|
1924 RtreeCell rightbbox; |
|
1925 |
|
1926 /* Allocate an array and populate it with a copy of pCell and |
|
1927 ** all cells from node pLeft. Then zero the original node. |
|
1928 */ |
|
1929 aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1)); |
|
1930 if( !aCell ){ |
|
1931 rc = SQLITE_NOMEM; |
|
1932 goto splitnode_out; |
|
1933 } |
|
1934 aiUsed = (int *)&aCell[nCell+1]; |
|
1935 memset(aiUsed, 0, sizeof(int)*(nCell+1)); |
|
1936 for(i=0; i<nCell; i++){ |
|
1937 nodeGetCell(pRtree, pNode, i, &aCell[i]); |
|
1938 } |
|
1939 nodeZero(pRtree, pNode); |
|
1940 memcpy(&aCell[nCell], pCell, sizeof(RtreeCell)); |
|
1941 nCell++; |
|
1942 |
|
1943 if( pNode->iNode==1 ){ |
|
1944 pRight = nodeNew(pRtree, pNode, 1); |
|
1945 pLeft = nodeNew(pRtree, pNode, 1); |
|
1946 pRtree->iDepth++; |
|
1947 pNode->isDirty = 1; |
|
1948 writeInt16(pNode->zData, pRtree->iDepth); |
|
1949 }else{ |
|
1950 pLeft = pNode; |
|
1951 pRight = nodeNew(pRtree, pLeft->pParent, 1); |
|
1952 nodeReference(pLeft); |
|
1953 } |
|
1954 |
|
1955 if( !pLeft || !pRight ){ |
|
1956 rc = SQLITE_NOMEM; |
|
1957 goto splitnode_out; |
|
1958 } |
|
1959 |
|
1960 memset(pLeft->zData, 0, pRtree->iNodeSize); |
|
1961 memset(pRight->zData, 0, pRtree->iNodeSize); |
|
1962 |
|
1963 rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox); |
|
1964 if( rc!=SQLITE_OK ){ |
|
1965 goto splitnode_out; |
|
1966 } |
|
1967 |
|
1968 /* Ensure both child nodes have node numbers assigned to them. */ |
|
1969 if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))) |
|
1970 || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft))) |
|
1971 ){ |
|
1972 goto splitnode_out; |
|
1973 } |
|
1974 |
|
1975 rightbbox.iRowid = pRight->iNode; |
|
1976 leftbbox.iRowid = pLeft->iNode; |
|
1977 |
|
1978 if( pNode->iNode==1 ){ |
|
1979 rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1); |
|
1980 if( rc!=SQLITE_OK ){ |
|
1981 goto splitnode_out; |
|
1982 } |
|
1983 }else{ |
|
1984 RtreeNode *pParent = pLeft->pParent; |
|
1985 int iCell = nodeParentIndex(pRtree, pLeft); |
|
1986 nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell); |
|
1987 AdjustTree(pRtree, pParent, &leftbbox); |
|
1988 } |
|
1989 if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){ |
|
1990 goto splitnode_out; |
|
1991 } |
|
1992 |
|
1993 for(i=0; i<NCELL(pRight); i++){ |
|
1994 i64 iRowid = nodeGetRowid(pRtree, pRight, i); |
|
1995 rc = updateMapping(pRtree, iRowid, pRight, iHeight); |
|
1996 if( iRowid==pCell->iRowid ){ |
|
1997 newCellIsRight = 1; |
|
1998 } |
|
1999 if( rc!=SQLITE_OK ){ |
|
2000 goto splitnode_out; |
|
2001 } |
|
2002 } |
|
2003 if( pNode->iNode==1 ){ |
|
2004 for(i=0; i<NCELL(pLeft); i++){ |
|
2005 i64 iRowid = nodeGetRowid(pRtree, pLeft, i); |
|
2006 rc = updateMapping(pRtree, iRowid, pLeft, iHeight); |
|
2007 if( rc!=SQLITE_OK ){ |
|
2008 goto splitnode_out; |
|
2009 } |
|
2010 } |
|
2011 }else if( newCellIsRight==0 ){ |
|
2012 rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight); |
|
2013 } |
|
2014 |
|
2015 if( rc==SQLITE_OK ){ |
|
2016 rc = nodeRelease(pRtree, pRight); |
|
2017 pRight = 0; |
|
2018 } |
|
2019 if( rc==SQLITE_OK ){ |
|
2020 rc = nodeRelease(pRtree, pLeft); |
|
2021 pLeft = 0; |
|
2022 } |
|
2023 |
|
2024 splitnode_out: |
|
2025 nodeRelease(pRtree, pRight); |
|
2026 nodeRelease(pRtree, pLeft); |
|
2027 sqlite3_free(aCell); |
|
2028 return rc; |
|
2029 } |
|
2030 |
|
2031 static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){ |
|
2032 int rc = SQLITE_OK; |
|
2033 if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){ |
|
2034 sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode); |
|
2035 if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){ |
|
2036 i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0); |
|
2037 rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent); |
|
2038 }else{ |
|
2039 rc = SQLITE_ERROR; |
|
2040 } |
|
2041 sqlite3_reset(pRtree->pReadParent); |
|
2042 if( rc==SQLITE_OK ){ |
|
2043 rc = fixLeafParent(pRtree, pLeaf->pParent); |
|
2044 } |
|
2045 } |
|
2046 return rc; |
|
2047 } |
|
2048 |
|
2049 static int deleteCell(Rtree *, RtreeNode *, int, int); |
|
2050 |
|
2051 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){ |
|
2052 int rc; |
|
2053 RtreeNode *pParent; |
|
2054 int iCell; |
|
2055 |
|
2056 assert( pNode->nRef==1 ); |
|
2057 |
|
2058 /* Remove the entry in the parent cell. */ |
|
2059 iCell = nodeParentIndex(pRtree, pNode); |
|
2060 pParent = pNode->pParent; |
|
2061 pNode->pParent = 0; |
|
2062 if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1)) |
|
2063 || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent)) |
|
2064 ){ |
|
2065 return rc; |
|
2066 } |
|
2067 |
|
2068 /* Remove the xxx_node entry. */ |
|
2069 sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode); |
|
2070 sqlite3_step(pRtree->pDeleteNode); |
|
2071 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){ |
|
2072 return rc; |
|
2073 } |
|
2074 |
|
2075 /* Remove the xxx_parent entry. */ |
|
2076 sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode); |
|
2077 sqlite3_step(pRtree->pDeleteParent); |
|
2078 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){ |
|
2079 return rc; |
|
2080 } |
|
2081 |
|
2082 /* Remove the node from the in-memory hash table and link it into |
|
2083 ** the Rtree.pDeleted list. Its contents will be re-inserted later on. |
|
2084 */ |
|
2085 nodeHashDelete(pRtree, pNode); |
|
2086 pNode->iNode = iHeight; |
|
2087 pNode->pNext = pRtree->pDeleted; |
|
2088 pNode->nRef++; |
|
2089 pRtree->pDeleted = pNode; |
|
2090 |
|
2091 return SQLITE_OK; |
|
2092 } |
|
2093 |
|
2094 static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){ |
|
2095 RtreeNode *pParent = pNode->pParent; |
|
2096 if( pParent ){ |
|
2097 int ii; |
|
2098 int nCell = NCELL(pNode); |
|
2099 RtreeCell box; /* Bounding box for pNode */ |
|
2100 nodeGetCell(pRtree, pNode, 0, &box); |
|
2101 for(ii=1; ii<nCell; ii++){ |
|
2102 RtreeCell cell; |
|
2103 nodeGetCell(pRtree, pNode, ii, &cell); |
|
2104 cellUnion(pRtree, &box, &cell); |
|
2105 } |
|
2106 box.iRowid = pNode->iNode; |
|
2107 ii = nodeParentIndex(pRtree, pNode); |
|
2108 nodeOverwriteCell(pRtree, pParent, &box, ii); |
|
2109 fixBoundingBox(pRtree, pParent); |
|
2110 } |
|
2111 } |
|
2112 |
|
2113 /* |
|
2114 ** Delete the cell at index iCell of node pNode. After removing the |
|
2115 ** cell, adjust the r-tree data structure if required. |
|
2116 */ |
|
2117 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){ |
|
2118 int rc; |
|
2119 |
|
2120 if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){ |
|
2121 return rc; |
|
2122 } |
|
2123 |
|
2124 /* Remove the cell from the node. This call just moves bytes around |
|
2125 ** the in-memory node image, so it cannot fail. |
|
2126 */ |
|
2127 nodeDeleteCell(pRtree, pNode, iCell); |
|
2128 |
|
2129 /* If the node is not the tree root and now has less than the minimum |
|
2130 ** number of cells, remove it from the tree. Otherwise, update the |
|
2131 ** cell in the parent node so that it tightly contains the updated |
|
2132 ** node. |
|
2133 */ |
|
2134 if( pNode->iNode!=1 ){ |
|
2135 RtreeNode *pParent = pNode->pParent; |
|
2136 if( (pParent->iNode!=1 || NCELL(pParent)!=1) |
|
2137 && (NCELL(pNode)<RTREE_MINCELLS(pRtree)) |
|
2138 ){ |
|
2139 rc = removeNode(pRtree, pNode, iHeight); |
|
2140 }else{ |
|
2141 fixBoundingBox(pRtree, pNode); |
|
2142 } |
|
2143 } |
|
2144 |
|
2145 return rc; |
|
2146 } |
|
2147 |
|
2148 static int Reinsert( |
|
2149 Rtree *pRtree, |
|
2150 RtreeNode *pNode, |
|
2151 RtreeCell *pCell, |
|
2152 int iHeight |
|
2153 ){ |
|
2154 int *aOrder; |
|
2155 int *aSpare; |
|
2156 RtreeCell *aCell; |
|
2157 float *aDistance; |
|
2158 int nCell; |
|
2159 float aCenterCoord[RTREE_MAX_DIMENSIONS]; |
|
2160 int iDim; |
|
2161 int ii; |
|
2162 int rc = SQLITE_OK; |
|
2163 |
|
2164 memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS); |
|
2165 |
|
2166 nCell = NCELL(pNode)+1; |
|
2167 |
|
2168 /* Allocate the buffers used by this operation. The allocation is |
|
2169 ** relinquished before this function returns. |
|
2170 */ |
|
2171 aCell = (RtreeCell *)sqlite3_malloc(nCell * ( |
|
2172 sizeof(RtreeCell) + /* aCell array */ |
|
2173 sizeof(int) + /* aOrder array */ |
|
2174 sizeof(int) + /* aSpare array */ |
|
2175 sizeof(float) /* aDistance array */ |
|
2176 )); |
|
2177 if( !aCell ){ |
|
2178 return SQLITE_NOMEM; |
|
2179 } |
|
2180 aOrder = (int *)&aCell[nCell]; |
|
2181 aSpare = (int *)&aOrder[nCell]; |
|
2182 aDistance = (float *)&aSpare[nCell]; |
|
2183 |
|
2184 for(ii=0; ii<nCell; ii++){ |
|
2185 if( ii==(nCell-1) ){ |
|
2186 memcpy(&aCell[ii], pCell, sizeof(RtreeCell)); |
|
2187 }else{ |
|
2188 nodeGetCell(pRtree, pNode, ii, &aCell[ii]); |
|
2189 } |
|
2190 aOrder[ii] = ii; |
|
2191 for(iDim=0; iDim<pRtree->nDim; iDim++){ |
|
2192 aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]); |
|
2193 aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]); |
|
2194 } |
|
2195 } |
|
2196 for(iDim=0; iDim<pRtree->nDim; iDim++){ |
|
2197 aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0); |
|
2198 } |
|
2199 |
|
2200 for(ii=0; ii<nCell; ii++){ |
|
2201 aDistance[ii] = 0.0; |
|
2202 for(iDim=0; iDim<pRtree->nDim; iDim++){ |
|
2203 float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) - |
|
2204 DCOORD(aCell[ii].aCoord[iDim*2]); |
|
2205 aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]); |
|
2206 } |
|
2207 } |
|
2208 |
|
2209 SortByDistance(aOrder, nCell, aDistance, aSpare); |
|
2210 nodeZero(pRtree, pNode); |
|
2211 |
|
2212 for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){ |
|
2213 RtreeCell *p = &aCell[aOrder[ii]]; |
|
2214 nodeInsertCell(pRtree, pNode, p); |
|
2215 if( p->iRowid==pCell->iRowid ){ |
|
2216 if( iHeight==0 ){ |
|
2217 rc = rowidWrite(pRtree, p->iRowid, pNode->iNode); |
|
2218 }else{ |
|
2219 rc = parentWrite(pRtree, p->iRowid, pNode->iNode); |
|
2220 } |
|
2221 } |
|
2222 } |
|
2223 if( rc==SQLITE_OK ){ |
|
2224 fixBoundingBox(pRtree, pNode); |
|
2225 } |
|
2226 for(; rc==SQLITE_OK && ii<nCell; ii++){ |
|
2227 /* Find a node to store this cell in. pNode->iNode currently contains |
|
2228 ** the height of the sub-tree headed by the cell. |
|
2229 */ |
|
2230 RtreeNode *pInsert; |
|
2231 RtreeCell *p = &aCell[aOrder[ii]]; |
|
2232 rc = ChooseLeaf(pRtree, p, iHeight, &pInsert); |
|
2233 if( rc==SQLITE_OK ){ |
|
2234 int rc2; |
|
2235 rc = rtreeInsertCell(pRtree, pInsert, p, iHeight); |
|
2236 rc2 = nodeRelease(pRtree, pInsert); |
|
2237 if( rc==SQLITE_OK ){ |
|
2238 rc = rc2; |
|
2239 } |
|
2240 } |
|
2241 } |
|
2242 |
|
2243 sqlite3_free(aCell); |
|
2244 return rc; |
|
2245 } |
|
2246 |
|
2247 /* |
|
2248 ** Insert cell pCell into node pNode. Node pNode is the head of a |
|
2249 ** subtree iHeight high (leaf nodes have iHeight==0). |
|
2250 */ |
|
2251 static int rtreeInsertCell( |
|
2252 Rtree *pRtree, |
|
2253 RtreeNode *pNode, |
|
2254 RtreeCell *pCell, |
|
2255 int iHeight |
|
2256 ){ |
|
2257 int rc = SQLITE_OK; |
|
2258 if( iHeight>0 ){ |
|
2259 RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid); |
|
2260 if( pChild ){ |
|
2261 nodeRelease(pRtree, pChild->pParent); |
|
2262 nodeReference(pNode); |
|
2263 pChild->pParent = pNode; |
|
2264 } |
|
2265 } |
|
2266 if( nodeInsertCell(pRtree, pNode, pCell) ){ |
|
2267 #if VARIANT_RSTARTREE_REINSERT |
|
2268 if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ |
|
2269 rc = SplitNode(pRtree, pNode, pCell, iHeight); |
|
2270 }else{ |
|
2271 pRtree->iReinsertHeight = iHeight; |
|
2272 rc = Reinsert(pRtree, pNode, pCell, iHeight); |
|
2273 } |
|
2274 #else |
|
2275 rc = SplitNode(pRtree, pNode, pCell, iHeight); |
|
2276 #endif |
|
2277 }else{ |
|
2278 AdjustTree(pRtree, pNode, pCell); |
|
2279 if( iHeight==0 ){ |
|
2280 rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); |
|
2281 }else{ |
|
2282 rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode); |
|
2283 } |
|
2284 } |
|
2285 return rc; |
|
2286 } |
|
2287 |
|
2288 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){ |
|
2289 int ii; |
|
2290 int rc = SQLITE_OK; |
|
2291 int nCell = NCELL(pNode); |
|
2292 |
|
2293 for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){ |
|
2294 RtreeNode *pInsert; |
|
2295 RtreeCell cell; |
|
2296 nodeGetCell(pRtree, pNode, ii, &cell); |
|
2297 |
|
2298 /* Find a node to store this cell in. pNode->iNode currently contains |
|
2299 ** the height of the sub-tree headed by the cell. |
|
2300 */ |
|
2301 rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert); |
|
2302 if( rc==SQLITE_OK ){ |
|
2303 int rc2; |
|
2304 rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode); |
|
2305 rc2 = nodeRelease(pRtree, pInsert); |
|
2306 if( rc==SQLITE_OK ){ |
|
2307 rc = rc2; |
|
2308 } |
|
2309 } |
|
2310 } |
|
2311 return rc; |
|
2312 } |
|
2313 |
|
2314 /* |
|
2315 ** Select a currently unused rowid for a new r-tree record. |
|
2316 */ |
|
2317 static int newRowid(Rtree *pRtree, i64 *piRowid){ |
|
2318 int rc; |
|
2319 sqlite3_bind_null(pRtree->pWriteRowid, 1); |
|
2320 sqlite3_bind_null(pRtree->pWriteRowid, 2); |
|
2321 sqlite3_step(pRtree->pWriteRowid); |
|
2322 rc = sqlite3_reset(pRtree->pWriteRowid); |
|
2323 *piRowid = sqlite3_last_insert_rowid(pRtree->db); |
|
2324 return rc; |
|
2325 } |
|
2326 |
|
2327 #ifndef NDEBUG |
|
2328 static int hashIsEmpty(Rtree *pRtree){ |
|
2329 int ii; |
|
2330 for(ii=0; ii<HASHSIZE; ii++){ |
|
2331 assert( !pRtree->aHash[ii] ); |
|
2332 } |
|
2333 return 1; |
|
2334 } |
|
2335 #endif |
|
2336 |
|
2337 /* |
|
2338 ** The xUpdate method for rtree module virtual tables. |
|
2339 */ |
|
2340 int rtreeUpdate( |
|
2341 sqlite3_vtab *pVtab, |
|
2342 int nData, |
|
2343 sqlite3_value **azData, |
|
2344 sqlite_int64 *pRowid |
|
2345 ){ |
|
2346 Rtree *pRtree = (Rtree *)pVtab; |
|
2347 int rc = SQLITE_OK; |
|
2348 |
|
2349 rtreeReference(pRtree); |
|
2350 |
|
2351 assert(nData>=1); |
|
2352 assert(hashIsEmpty(pRtree)); |
|
2353 |
|
2354 /* If azData[0] is not an SQL NULL value, it is the rowid of a |
|
2355 ** record to delete from the r-tree table. The following block does |
|
2356 ** just that. |
|
2357 */ |
|
2358 if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){ |
|
2359 i64 iDelete; /* The rowid to delete */ |
|
2360 RtreeNode *pLeaf; /* Leaf node containing record iDelete */ |
|
2361 int iCell; /* Index of iDelete cell in pLeaf */ |
|
2362 RtreeNode *pRoot; |
|
2363 |
|
2364 /* Obtain a reference to the root node to initialise Rtree.iDepth */ |
|
2365 rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
|
2366 |
|
2367 /* Obtain a reference to the leaf node that contains the entry |
|
2368 ** about to be deleted. |
|
2369 */ |
|
2370 if( rc==SQLITE_OK ){ |
|
2371 iDelete = sqlite3_value_int64(azData[0]); |
|
2372 rc = findLeafNode(pRtree, iDelete, &pLeaf); |
|
2373 } |
|
2374 |
|
2375 /* Delete the cell in question from the leaf node. */ |
|
2376 if( rc==SQLITE_OK ){ |
|
2377 int rc2; |
|
2378 iCell = nodeRowidIndex(pRtree, pLeaf, iDelete); |
|
2379 rc = deleteCell(pRtree, pLeaf, iCell, 0); |
|
2380 rc2 = nodeRelease(pRtree, pLeaf); |
|
2381 if( rc==SQLITE_OK ){ |
|
2382 rc = rc2; |
|
2383 } |
|
2384 } |
|
2385 |
|
2386 /* Delete the corresponding entry in the <rtree>_rowid table. */ |
|
2387 if( rc==SQLITE_OK ){ |
|
2388 sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete); |
|
2389 sqlite3_step(pRtree->pDeleteRowid); |
|
2390 rc = sqlite3_reset(pRtree->pDeleteRowid); |
|
2391 } |
|
2392 |
|
2393 /* Check if the root node now has exactly one child. If so, remove |
|
2394 ** it, schedule the contents of the child for reinsertion and |
|
2395 ** reduce the tree height by one. |
|
2396 ** |
|
2397 ** This is equivalent to copying the contents of the child into |
|
2398 ** the root node (the operation that Gutman's paper says to perform |
|
2399 ** in this scenario). |
|
2400 */ |
|
2401 if( rc==SQLITE_OK && pRtree->iDepth>0 ){ |
|
2402 if( rc==SQLITE_OK && NCELL(pRoot)==1 ){ |
|
2403 RtreeNode *pChild; |
|
2404 i64 iChild = nodeGetRowid(pRtree, pRoot, 0); |
|
2405 rc = nodeAcquire(pRtree, iChild, pRoot, &pChild); |
|
2406 if( rc==SQLITE_OK ){ |
|
2407 rc = removeNode(pRtree, pChild, pRtree->iDepth-1); |
|
2408 } |
|
2409 if( rc==SQLITE_OK ){ |
|
2410 pRtree->iDepth--; |
|
2411 writeInt16(pRoot->zData, pRtree->iDepth); |
|
2412 pRoot->isDirty = 1; |
|
2413 } |
|
2414 } |
|
2415 } |
|
2416 |
|
2417 /* Re-insert the contents of any underfull nodes removed from the tree. */ |
|
2418 for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){ |
|
2419 if( rc==SQLITE_OK ){ |
|
2420 rc = reinsertNodeContent(pRtree, pLeaf); |
|
2421 } |
|
2422 pRtree->pDeleted = pLeaf->pNext; |
|
2423 sqlite3_free(pLeaf); |
|
2424 } |
|
2425 |
|
2426 /* Release the reference to the root node. */ |
|
2427 if( rc==SQLITE_OK ){ |
|
2428 rc = nodeRelease(pRtree, pRoot); |
|
2429 }else{ |
|
2430 nodeRelease(pRtree, pRoot); |
|
2431 } |
|
2432 } |
|
2433 |
|
2434 /* If the azData[] array contains more than one element, elements |
|
2435 ** (azData[2]..azData[argc-1]) contain a new record to insert into |
|
2436 ** the r-tree structure. |
|
2437 */ |
|
2438 if( rc==SQLITE_OK && nData>1 ){ |
|
2439 /* Insert a new record into the r-tree */ |
|
2440 RtreeCell cell; |
|
2441 int ii; |
|
2442 RtreeNode *pLeaf; |
|
2443 |
|
2444 /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */ |
|
2445 assert( nData==(pRtree->nDim*2 + 3) ); |
|
2446 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
|
2447 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
2448 cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]); |
|
2449 cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]); |
|
2450 if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ |
|
2451 rc = SQLITE_CONSTRAINT; |
|
2452 goto constraint; |
|
2453 } |
|
2454 } |
|
2455 }else{ |
|
2456 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ |
|
2457 cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]); |
|
2458 cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]); |
|
2459 if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ |
|
2460 rc = SQLITE_CONSTRAINT; |
|
2461 goto constraint; |
|
2462 } |
|
2463 } |
|
2464 } |
|
2465 |
|
2466 /* Figure out the rowid of the new row. */ |
|
2467 if( sqlite3_value_type(azData[2])==SQLITE_NULL ){ |
|
2468 rc = newRowid(pRtree, &cell.iRowid); |
|
2469 }else{ |
|
2470 cell.iRowid = sqlite3_value_int64(azData[2]); |
|
2471 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); |
|
2472 if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){ |
|
2473 sqlite3_reset(pRtree->pReadRowid); |
|
2474 rc = SQLITE_CONSTRAINT; |
|
2475 goto constraint; |
|
2476 } |
|
2477 rc = sqlite3_reset(pRtree->pReadRowid); |
|
2478 } |
|
2479 |
|
2480 if( rc==SQLITE_OK ){ |
|
2481 rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf); |
|
2482 } |
|
2483 if( rc==SQLITE_OK ){ |
|
2484 int rc2; |
|
2485 pRtree->iReinsertHeight = -1; |
|
2486 rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0); |
|
2487 rc2 = nodeRelease(pRtree, pLeaf); |
|
2488 if( rc==SQLITE_OK ){ |
|
2489 rc = rc2; |
|
2490 } |
|
2491 } |
|
2492 } |
|
2493 |
|
2494 constraint: |
|
2495 rtreeRelease(pRtree); |
|
2496 return rc; |
|
2497 } |
|
2498 |
|
2499 /* |
|
2500 ** The xRename method for rtree module virtual tables. |
|
2501 */ |
|
2502 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){ |
|
2503 Rtree *pRtree = (Rtree *)pVtab; |
|
2504 int rc = SQLITE_NOMEM; |
|
2505 char *zSql = sqlite3_mprintf( |
|
2506 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";" |
|
2507 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";" |
|
2508 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";" |
|
2509 , pRtree->zDb, pRtree->zName, zNewName |
|
2510 , pRtree->zDb, pRtree->zName, zNewName |
|
2511 , pRtree->zDb, pRtree->zName, zNewName |
|
2512 ); |
|
2513 if( zSql ){ |
|
2514 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); |
|
2515 sqlite3_free(zSql); |
|
2516 } |
|
2517 return rc; |
|
2518 } |
|
2519 |
|
2520 static sqlite3_module rtreeModule = { |
|
2521 0, /* iVersion */ |
|
2522 rtreeCreate, /* xCreate - create a table */ |
|
2523 rtreeConnect, /* xConnect - connect to an existing table */ |
|
2524 rtreeBestIndex, /* xBestIndex - Determine search strategy */ |
|
2525 rtreeDisconnect, /* xDisconnect - Disconnect from a table */ |
|
2526 rtreeDestroy, /* xDestroy - Drop a table */ |
|
2527 rtreeOpen, /* xOpen - open a cursor */ |
|
2528 rtreeClose, /* xClose - close a cursor */ |
|
2529 rtreeFilter, /* xFilter - configure scan constraints */ |
|
2530 rtreeNext, /* xNext - advance a cursor */ |
|
2531 rtreeEof, /* xEof */ |
|
2532 rtreeColumn, /* xColumn - read data */ |
|
2533 rtreeRowid, /* xRowid - read data */ |
|
2534 rtreeUpdate, /* xUpdate - write data */ |
|
2535 0, /* xBegin - begin transaction */ |
|
2536 0, /* xSync - sync transaction */ |
|
2537 0, /* xCommit - commit transaction */ |
|
2538 0, /* xRollback - rollback transaction */ |
|
2539 0, /* xFindFunction - function overloading */ |
|
2540 rtreeRename /* xRename - rename the table */ |
|
2541 }; |
|
2542 |
|
2543 static int rtreeSqlInit( |
|
2544 Rtree *pRtree, |
|
2545 sqlite3 *db, |
|
2546 const char *zDb, |
|
2547 const char *zPrefix, |
|
2548 int isCreate |
|
2549 ){ |
|
2550 int rc = SQLITE_OK; |
|
2551 |
|
2552 #define N_STATEMENT 9 |
|
2553 static const char *azSql[N_STATEMENT] = { |
|
2554 /* Read and write the xxx_node table */ |
|
2555 "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1", |
|
2556 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)", |
|
2557 "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1", |
|
2558 |
|
2559 /* Read and write the xxx_rowid table */ |
|
2560 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1", |
|
2561 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)", |
|
2562 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1", |
|
2563 |
|
2564 /* Read and write the xxx_parent table */ |
|
2565 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1", |
|
2566 "INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)", |
|
2567 "DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1" |
|
2568 }; |
|
2569 sqlite3_stmt **appStmt[N_STATEMENT]; |
|
2570 int i; |
|
2571 |
|
2572 pRtree->db = db; |
|
2573 |
|
2574 if( isCreate ){ |
|
2575 char *zCreate = sqlite3_mprintf( |
|
2576 "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);" |
|
2577 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);" |
|
2578 "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);" |
|
2579 "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))", |
|
2580 zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize |
|
2581 ); |
|
2582 if( !zCreate ){ |
|
2583 return SQLITE_NOMEM; |
|
2584 } |
|
2585 rc = sqlite3_exec(db, zCreate, 0, 0, 0); |
|
2586 sqlite3_free(zCreate); |
|
2587 if( rc!=SQLITE_OK ){ |
|
2588 return rc; |
|
2589 } |
|
2590 } |
|
2591 |
|
2592 appStmt[0] = &pRtree->pReadNode; |
|
2593 appStmt[1] = &pRtree->pWriteNode; |
|
2594 appStmt[2] = &pRtree->pDeleteNode; |
|
2595 appStmt[3] = &pRtree->pReadRowid; |
|
2596 appStmt[4] = &pRtree->pWriteRowid; |
|
2597 appStmt[5] = &pRtree->pDeleteRowid; |
|
2598 appStmt[6] = &pRtree->pReadParent; |
|
2599 appStmt[7] = &pRtree->pWriteParent; |
|
2600 appStmt[8] = &pRtree->pDeleteParent; |
|
2601 |
|
2602 for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){ |
|
2603 char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix); |
|
2604 if( zSql ){ |
|
2605 rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); |
|
2606 }else{ |
|
2607 rc = SQLITE_NOMEM; |
|
2608 } |
|
2609 sqlite3_free(zSql); |
|
2610 } |
|
2611 |
|
2612 return rc; |
|
2613 } |
|
2614 |
|
2615 /* |
|
2616 ** This routine queries database handle db for the page-size used by |
|
2617 ** database zDb. If successful, the page-size in bytes is written to |
|
2618 ** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error |
|
2619 ** code is returned. |
|
2620 */ |
|
2621 static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){ |
|
2622 int rc = SQLITE_NOMEM; |
|
2623 char *zSql; |
|
2624 sqlite3_stmt *pStmt = 0; |
|
2625 |
|
2626 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb); |
|
2627 if( !zSql ){ |
|
2628 return SQLITE_NOMEM; |
|
2629 } |
|
2630 |
|
2631 rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
|
2632 sqlite3_free(zSql); |
|
2633 if( rc!=SQLITE_OK ){ |
|
2634 return rc; |
|
2635 } |
|
2636 |
|
2637 if( SQLITE_ROW==sqlite3_step(pStmt) ){ |
|
2638 *piPageSize = sqlite3_column_int(pStmt, 0); |
|
2639 } |
|
2640 return sqlite3_finalize(pStmt); |
|
2641 } |
|
2642 |
|
2643 /* |
|
2644 ** This function is the implementation of both the xConnect and xCreate |
|
2645 ** methods of the r-tree virtual table. |
|
2646 ** |
|
2647 ** argv[0] -> module name |
|
2648 ** argv[1] -> database name |
|
2649 ** argv[2] -> table name |
|
2650 ** argv[...] -> column names... |
|
2651 */ |
|
2652 static int rtreeInit( |
|
2653 sqlite3 *db, /* Database connection */ |
|
2654 void *pAux, /* Pointer to head of rtree list */ |
|
2655 int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ |
|
2656 sqlite3_vtab **ppVtab, /* OUT: New virtual table */ |
|
2657 char **pzErr, /* OUT: Error message, if any */ |
|
2658 int isCreate, /* True for xCreate, false for xConnect */ |
|
2659 int eCoordType /* One of the RTREE_COORD_* constants */ |
|
2660 ){ |
|
2661 int rc = SQLITE_OK; |
|
2662 int iPageSize = 0; |
|
2663 Rtree *pRtree; |
|
2664 int nDb; /* Length of string argv[1] */ |
|
2665 int nName; /* Length of string argv[2] */ |
|
2666 |
|
2667 const char *aErrMsg[] = { |
|
2668 0, /* 0 */ |
|
2669 "Wrong number of columns for an rtree table", /* 1 */ |
|
2670 "Too few columns for an rtree table", /* 2 */ |
|
2671 "Too many columns for an rtree table" /* 3 */ |
|
2672 }; |
|
2673 |
|
2674 int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2; |
|
2675 if( aErrMsg[iErr] ){ |
|
2676 *pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]); |
|
2677 return SQLITE_ERROR; |
|
2678 } |
|
2679 |
|
2680 rc = getPageSize(db, argv[1], &iPageSize); |
|
2681 if( rc!=SQLITE_OK ){ |
|
2682 return rc; |
|
2683 } |
|
2684 |
|
2685 /* Allocate the sqlite3_vtab structure */ |
|
2686 nDb = strlen(argv[1]); |
|
2687 nName = strlen(argv[2]); |
|
2688 pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2); |
|
2689 if( !pRtree ){ |
|
2690 return SQLITE_NOMEM; |
|
2691 } |
|
2692 memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); |
|
2693 pRtree->nBusy = 1; |
|
2694 pRtree->base.pModule = &rtreeModule; |
|
2695 pRtree->zDb = (char *)&pRtree[1]; |
|
2696 pRtree->zName = &pRtree->zDb[nDb+1]; |
|
2697 pRtree->nDim = (argc-4)/2; |
|
2698 pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2; |
|
2699 pRtree->eCoordType = eCoordType; |
|
2700 memcpy(pRtree->zDb, argv[1], nDb); |
|
2701 memcpy(pRtree->zName, argv[2], nName); |
|
2702 |
|
2703 /* Figure out the node size to use. By default, use 64 bytes less than |
|
2704 ** the database page-size. This ensures that each node is stored on |
|
2705 ** a single database page. |
|
2706 ** |
|
2707 ** If the databasd page-size is so large that more than RTREE_MAXCELLS |
|
2708 ** entries would fit in a single node, use a smaller node-size. |
|
2709 */ |
|
2710 pRtree->iNodeSize = iPageSize-64; |
|
2711 if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){ |
|
2712 pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS; |
|
2713 } |
|
2714 |
|
2715 /* Create/Connect to the underlying relational database schema. If |
|
2716 ** that is successful, call sqlite3_declare_vtab() to configure |
|
2717 ** the r-tree table schema. |
|
2718 */ |
|
2719 if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){ |
|
2720 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); |
|
2721 }else{ |
|
2722 char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]); |
|
2723 char *zTmp; |
|
2724 int ii; |
|
2725 for(ii=4; zSql && ii<argc; ii++){ |
|
2726 zTmp = zSql; |
|
2727 zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]); |
|
2728 sqlite3_free(zTmp); |
|
2729 } |
|
2730 if( zSql ){ |
|
2731 zTmp = zSql; |
|
2732 zSql = sqlite3_mprintf("%s);", zTmp); |
|
2733 sqlite3_free(zTmp); |
|
2734 } |
|
2735 if( !zSql || sqlite3_declare_vtab(db, zSql) ){ |
|
2736 rc = SQLITE_NOMEM; |
|
2737 } |
|
2738 sqlite3_free(zSql); |
|
2739 } |
|
2740 |
|
2741 if( rc==SQLITE_OK ){ |
|
2742 *ppVtab = (sqlite3_vtab *)pRtree; |
|
2743 }else{ |
|
2744 rtreeRelease(pRtree); |
|
2745 } |
|
2746 return rc; |
|
2747 } |
|
2748 |
|
2749 |
|
2750 /* |
|
2751 ** Implementation of a scalar function that decodes r-tree nodes to |
|
2752 ** human readable strings. This can be used for debugging and analysis. |
|
2753 ** |
|
2754 ** The scalar function takes two arguments, a blob of data containing |
|
2755 ** an r-tree node, and the number of dimensions the r-tree indexes. |
|
2756 ** For a two-dimensional r-tree structure called "rt", to deserialize |
|
2757 ** all nodes, a statement like: |
|
2758 ** |
|
2759 ** SELECT rtreenode(2, data) FROM rt_node; |
|
2760 ** |
|
2761 ** The human readable string takes the form of a Tcl list with one |
|
2762 ** entry for each cell in the r-tree node. Each entry is itself a |
|
2763 ** list, containing the 8-byte rowid/pageno followed by the |
|
2764 ** <num-dimension>*2 coordinates. |
|
2765 */ |
|
2766 static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ |
|
2767 char *zText = 0; |
|
2768 RtreeNode node; |
|
2769 Rtree tree; |
|
2770 int ii; |
|
2771 |
|
2772 memset(&node, 0, sizeof(RtreeNode)); |
|
2773 memset(&tree, 0, sizeof(Rtree)); |
|
2774 tree.nDim = sqlite3_value_int(apArg[0]); |
|
2775 tree.nBytesPerCell = 8 + 8 * tree.nDim; |
|
2776 node.zData = (u8 *)sqlite3_value_blob(apArg[1]); |
|
2777 |
|
2778 for(ii=0; ii<NCELL(&node); ii++){ |
|
2779 char zCell[512]; |
|
2780 int nCell = 0; |
|
2781 RtreeCell cell; |
|
2782 int jj; |
|
2783 |
|
2784 nodeGetCell(&tree, &node, ii, &cell); |
|
2785 sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid); |
|
2786 nCell = strlen(zCell); |
|
2787 for(jj=0; jj<tree.nDim*2; jj++){ |
|
2788 sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f); |
|
2789 nCell = strlen(zCell); |
|
2790 } |
|
2791 |
|
2792 if( zText ){ |
|
2793 char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell); |
|
2794 sqlite3_free(zText); |
|
2795 zText = zTextNew; |
|
2796 }else{ |
|
2797 zText = sqlite3_mprintf("{%s}", zCell); |
|
2798 } |
|
2799 } |
|
2800 |
|
2801 sqlite3_result_text(ctx, zText, -1, sqlite3_free); |
|
2802 } |
|
2803 |
|
2804 static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ |
|
2805 if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB |
|
2806 || sqlite3_value_bytes(apArg[0])<2 |
|
2807 ){ |
|
2808 sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); |
|
2809 }else{ |
|
2810 u8 *zBlob = (u8 *)sqlite3_value_blob(apArg[0]); |
|
2811 sqlite3_result_int(ctx, readInt16(zBlob)); |
|
2812 } |
|
2813 } |
|
2814 |
|
2815 /* |
|
2816 ** Register the r-tree module with database handle db. This creates the |
|
2817 ** virtual table module "rtree" and the debugging/analysis scalar |
|
2818 ** function "rtreenode". |
|
2819 */ |
|
2820 int sqlite3RtreeInit(sqlite3 *db){ |
|
2821 int rc = SQLITE_OK; |
|
2822 |
|
2823 if( rc==SQLITE_OK ){ |
|
2824 int utf8 = SQLITE_UTF8; |
|
2825 rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0); |
|
2826 } |
|
2827 if( rc==SQLITE_OK ){ |
|
2828 int utf8 = SQLITE_UTF8; |
|
2829 rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0); |
|
2830 } |
|
2831 if( rc==SQLITE_OK ){ |
|
2832 void *c = (void *)RTREE_COORD_REAL32; |
|
2833 rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0); |
|
2834 } |
|
2835 if( rc==SQLITE_OK ){ |
|
2836 void *c = (void *)RTREE_COORD_INT32; |
|
2837 rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); |
|
2838 } |
|
2839 |
|
2840 return rc; |
|
2841 } |
|
2842 |
|
2843 #if !SQLITE_CORE |
|
2844 int sqlite3_extension_init( |
|
2845 sqlite3 *db, |
|
2846 char **pzErrMsg, |
|
2847 const sqlite3_api_routines *pApi |
|
2848 ){ |
|
2849 SQLITE_EXTENSION_INIT2(pApi) |
|
2850 return sqlite3RtreeInit(db); |
|
2851 } |
|
2852 #endif |
|
2853 |
|
2854 #endif |