OLD | NEW |
1 /* | 1 /* |
2 ** 2001 September 15 | 2 ** 2001 September 15 |
3 ** | 3 ** |
4 ** The author disclaims copyright to this source code. In place of | 4 ** The author disclaims copyright to this source code. In place of |
5 ** a legal notice, here is a blessing: | 5 ** a legal notice, here is a blessing: |
6 ** | 6 ** |
7 ** May you do good and not evil. | 7 ** May you do good and not evil. |
8 ** May you find forgiveness for yourself and forgive others. | 8 ** May you find forgiveness for yourself and forgive others. |
9 ** May you share freely, never taking more than you give. | 9 ** May you share freely, never taking more than you give. |
10 ** | 10 ** |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
61 #include "sqlite3.h" | 61 #include "sqlite3.h" |
62 #endif | 62 #endif |
63 | 63 |
64 #include <string.h> | 64 #include <string.h> |
65 #include <assert.h> | 65 #include <assert.h> |
66 #include <stdio.h> | 66 #include <stdio.h> |
67 | 67 |
68 #ifndef SQLITE_AMALGAMATION | 68 #ifndef SQLITE_AMALGAMATION |
69 #include "sqlite3rtree.h" | 69 #include "sqlite3rtree.h" |
70 typedef sqlite3_int64 i64; | 70 typedef sqlite3_int64 i64; |
| 71 typedef sqlite3_uint64 u64; |
71 typedef unsigned char u8; | 72 typedef unsigned char u8; |
72 typedef unsigned short u16; | 73 typedef unsigned short u16; |
73 typedef unsigned int u32; | 74 typedef unsigned int u32; |
74 #endif | 75 #endif |
75 | 76 |
76 /* The following macro is used to suppress compiler warnings. | 77 /* The following macro is used to suppress compiler warnings. |
77 */ | 78 */ |
78 #ifndef UNUSED_PARAMETER | 79 #ifndef UNUSED_PARAMETER |
79 # define UNUSED_PARAMETER(x) (void)(x) | 80 # define UNUSED_PARAMETER(x) (void)(x) |
80 #endif | 81 #endif |
(...skipping 28 matching lines...) Expand all Loading... |
109 #define RTREE_MIN_ROWEST 100 | 110 #define RTREE_MIN_ROWEST 100 |
110 | 111 |
111 /* | 112 /* |
112 ** An rtree virtual-table object. | 113 ** An rtree virtual-table object. |
113 */ | 114 */ |
114 struct Rtree { | 115 struct Rtree { |
115 sqlite3_vtab base; /* Base class. Must be first */ | 116 sqlite3_vtab base; /* Base class. Must be first */ |
116 sqlite3 *db; /* Host database connection */ | 117 sqlite3 *db; /* Host database connection */ |
117 int iNodeSize; /* Size in bytes of each node in the node table */ | 118 int iNodeSize; /* Size in bytes of each node in the node table */ |
118 u8 nDim; /* Number of dimensions */ | 119 u8 nDim; /* Number of dimensions */ |
| 120 u8 nDim2; /* Twice the number of dimensions */ |
119 u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ | 121 u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ |
120 u8 nBytesPerCell; /* Bytes consumed per cell */ | 122 u8 nBytesPerCell; /* Bytes consumed per cell */ |
| 123 u8 inWrTrans; /* True if inside write transaction */ |
121 int iDepth; /* Current depth of the r-tree structure */ | 124 int iDepth; /* Current depth of the r-tree structure */ |
122 char *zDb; /* Name of database containing r-tree table */ | 125 char *zDb; /* Name of database containing r-tree table */ |
123 char *zName; /* Name of r-tree table */ | 126 char *zName; /* Name of r-tree table */ |
124 int nBusy; /* Current number of users of this structure */ | 127 u32 nBusy; /* Current number of users of this structure */ |
125 i64 nRowEst; /* Estimated number of rows in this table */ | 128 i64 nRowEst; /* Estimated number of rows in this table */ |
| 129 u32 nCursor; /* Number of open cursors */ |
126 | 130 |
127 /* List of nodes removed during a CondenseTree operation. List is | 131 /* List of nodes removed during a CondenseTree operation. List is |
128 ** linked together via the pointer normally used for hash chains - | 132 ** linked together via the pointer normally used for hash chains - |
129 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree | 133 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree |
130 ** headed by the node (leaf nodes have RtreeNode.iNode==0). | 134 ** headed by the node (leaf nodes have RtreeNode.iNode==0). |
131 */ | 135 */ |
132 RtreeNode *pDeleted; | 136 RtreeNode *pDeleted; |
133 int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */ | 137 int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */ |
134 | 138 |
| 139 /* Blob I/O on xxx_node */ |
| 140 sqlite3_blob *pNodeBlob; |
| 141 |
135 /* Statements to read/write/delete a record from xxx_node */ | 142 /* Statements to read/write/delete a record from xxx_node */ |
136 sqlite3_stmt *pReadNode; | |
137 sqlite3_stmt *pWriteNode; | 143 sqlite3_stmt *pWriteNode; |
138 sqlite3_stmt *pDeleteNode; | 144 sqlite3_stmt *pDeleteNode; |
139 | 145 |
140 /* Statements to read/write/delete a record from xxx_rowid */ | 146 /* Statements to read/write/delete a record from xxx_rowid */ |
141 sqlite3_stmt *pReadRowid; | 147 sqlite3_stmt *pReadRowid; |
142 sqlite3_stmt *pWriteRowid; | 148 sqlite3_stmt *pWriteRowid; |
143 sqlite3_stmt *pDeleteRowid; | 149 sqlite3_stmt *pDeleteRowid; |
144 | 150 |
145 /* Statements to read/write/delete a record from xxx_parent */ | 151 /* Statements to read/write/delete a record from xxx_parent */ |
146 sqlite3_stmt *pReadParent; | 152 sqlite3_stmt *pReadParent; |
(...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
355 RtreeDValue aParam[1]; /* Values for parameters to the SQL function */ | 361 RtreeDValue aParam[1]; /* Values for parameters to the SQL function */ |
356 }; | 362 }; |
357 | 363 |
358 #ifndef MAX | 364 #ifndef MAX |
359 # define MAX(x,y) ((x) < (y) ? (y) : (x)) | 365 # define MAX(x,y) ((x) < (y) ? (y) : (x)) |
360 #endif | 366 #endif |
361 #ifndef MIN | 367 #ifndef MIN |
362 # define MIN(x,y) ((x) > (y) ? (y) : (x)) | 368 # define MIN(x,y) ((x) > (y) ? (y) : (x)) |
363 #endif | 369 #endif |
364 | 370 |
| 371 /* What version of GCC is being used. 0 means GCC is not being used */ |
| 372 #ifndef GCC_VERSION |
| 373 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 374 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__) |
| 375 #else |
| 376 # define GCC_VERSION 0 |
| 377 #endif |
| 378 #endif |
| 379 |
| 380 /* What version of CLANG is being used. 0 means CLANG is not being used */ |
| 381 #ifndef CLANG_VERSION |
| 382 #if defined(__clang__) && !defined(_WIN32) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 383 # define CLANG_VERSION \ |
| 384 (__clang_major__*1000000+__clang_minor__*1000+__clang_patchlevel__) |
| 385 #else |
| 386 # define CLANG_VERSION 0 |
| 387 #endif |
| 388 #endif |
| 389 |
| 390 /* The testcase() macro should already be defined in the amalgamation. If |
| 391 ** it is not, make it a no-op. |
| 392 */ |
| 393 #ifndef SQLITE_AMALGAMATION |
| 394 # define testcase(X) |
| 395 #endif |
| 396 |
| 397 /* |
| 398 ** Macros to determine whether the machine is big or little endian, |
| 399 ** and whether or not that determination is run-time or compile-time. |
| 400 ** |
| 401 ** For best performance, an attempt is made to guess at the byte-order |
| 402 ** using C-preprocessor macros. If that is unsuccessful, or if |
| 403 ** -DSQLITE_RUNTIME_BYTEORDER=1 is set, then byte-order is determined |
| 404 ** at run-time. |
| 405 */ |
| 406 #ifndef SQLITE_BYTEORDER |
| 407 #if defined(i386) || defined(__i386__) || defined(_M_IX86) || \ |
| 408 defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \ |
| 409 defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \ |
| 410 defined(__arm__) |
| 411 # define SQLITE_BYTEORDER 1234 |
| 412 #elif defined(sparc) || defined(__ppc__) |
| 413 # define SQLITE_BYTEORDER 4321 |
| 414 #else |
| 415 # define SQLITE_BYTEORDER 0 /* 0 means "unknown at compile-time" */ |
| 416 #endif |
| 417 #endif |
| 418 |
| 419 |
| 420 /* What version of MSVC is being used. 0 means MSVC is not being used */ |
| 421 #ifndef MSVC_VERSION |
| 422 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC) |
| 423 # define MSVC_VERSION _MSC_VER |
| 424 #else |
| 425 # define MSVC_VERSION 0 |
| 426 #endif |
| 427 #endif |
| 428 |
365 /* | 429 /* |
366 ** Functions to deserialize a 16 bit integer, 32 bit real number and | 430 ** Functions to deserialize a 16 bit integer, 32 bit real number and |
367 ** 64 bit integer. The deserialized value is returned. | 431 ** 64 bit integer. The deserialized value is returned. |
368 */ | 432 */ |
369 static int readInt16(u8 *p){ | 433 static int readInt16(u8 *p){ |
370 return (p[0]<<8) + p[1]; | 434 return (p[0]<<8) + p[1]; |
371 } | 435 } |
372 static void readCoord(u8 *p, RtreeCoord *pCoord){ | 436 static void readCoord(u8 *p, RtreeCoord *pCoord){ |
| 437 assert( ((((char*)p) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */ |
| 438 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 439 pCoord->u = _byteswap_ulong(*(u32*)p); |
| 440 #elif SQLITE_BYTEORDER==1234 && (GCC_VERSION>=4003000 || CLANG_VERSION>=3000000) |
| 441 pCoord->u = __builtin_bswap32(*(u32*)p); |
| 442 #elif SQLITE_BYTEORDER==4321 |
| 443 pCoord->u = *(u32*)p; |
| 444 #else |
373 pCoord->u = ( | 445 pCoord->u = ( |
374 (((u32)p[0]) << 24) + | 446 (((u32)p[0]) << 24) + |
375 (((u32)p[1]) << 16) + | 447 (((u32)p[1]) << 16) + |
376 (((u32)p[2]) << 8) + | 448 (((u32)p[2]) << 8) + |
377 (((u32)p[3]) << 0) | 449 (((u32)p[3]) << 0) |
378 ); | 450 ); |
| 451 #endif |
379 } | 452 } |
380 static i64 readInt64(u8 *p){ | 453 static i64 readInt64(u8 *p){ |
| 454 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 455 u64 x; |
| 456 memcpy(&x, p, 8); |
| 457 return (i64)_byteswap_uint64(x); |
| 458 #elif SQLITE_BYTEORDER==1234 && (GCC_VERSION>=4003000 || CLANG_VERSION>=3000000) |
| 459 u64 x; |
| 460 memcpy(&x, p, 8); |
| 461 return (i64)__builtin_bswap64(x); |
| 462 #elif SQLITE_BYTEORDER==4321 |
| 463 i64 x; |
| 464 memcpy(&x, p, 8); |
| 465 return x; |
| 466 #else |
381 return ( | 467 return ( |
382 (((i64)p[0]) << 56) + | 468 (((i64)p[0]) << 56) + |
383 (((i64)p[1]) << 48) + | 469 (((i64)p[1]) << 48) + |
384 (((i64)p[2]) << 40) + | 470 (((i64)p[2]) << 40) + |
385 (((i64)p[3]) << 32) + | 471 (((i64)p[3]) << 32) + |
386 (((i64)p[4]) << 24) + | 472 (((i64)p[4]) << 24) + |
387 (((i64)p[5]) << 16) + | 473 (((i64)p[5]) << 16) + |
388 (((i64)p[6]) << 8) + | 474 (((i64)p[6]) << 8) + |
389 (((i64)p[7]) << 0) | 475 (((i64)p[7]) << 0) |
390 ); | 476 ); |
| 477 #endif |
391 } | 478 } |
392 | 479 |
393 /* | 480 /* |
394 ** Functions to serialize a 16 bit integer, 32 bit real number and | 481 ** Functions to serialize a 16 bit integer, 32 bit real number and |
395 ** 64 bit integer. The value returned is the number of bytes written | 482 ** 64 bit integer. The value returned is the number of bytes written |
396 ** to the argument buffer (always 2, 4 and 8 respectively). | 483 ** to the argument buffer (always 2, 4 and 8 respectively). |
397 */ | 484 */ |
398 static int writeInt16(u8 *p, int i){ | 485 static void writeInt16(u8 *p, int i){ |
399 p[0] = (i>> 8)&0xFF; | 486 p[0] = (i>> 8)&0xFF; |
400 p[1] = (i>> 0)&0xFF; | 487 p[1] = (i>> 0)&0xFF; |
401 return 2; | |
402 } | 488 } |
403 static int writeCoord(u8 *p, RtreeCoord *pCoord){ | 489 static int writeCoord(u8 *p, RtreeCoord *pCoord){ |
404 u32 i; | 490 u32 i; |
| 491 assert( ((((char*)p) - (char*)0)&3)==0 ); /* p is always 4-byte aligned */ |
405 assert( sizeof(RtreeCoord)==4 ); | 492 assert( sizeof(RtreeCoord)==4 ); |
406 assert( sizeof(u32)==4 ); | 493 assert( sizeof(u32)==4 ); |
| 494 #if SQLITE_BYTEORDER==1234 && (GCC_VERSION>=4003000 || CLANG_VERSION>=3000000) |
| 495 i = __builtin_bswap32(pCoord->u); |
| 496 memcpy(p, &i, 4); |
| 497 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 498 i = _byteswap_ulong(pCoord->u); |
| 499 memcpy(p, &i, 4); |
| 500 #elif SQLITE_BYTEORDER==4321 |
| 501 i = pCoord->u; |
| 502 memcpy(p, &i, 4); |
| 503 #else |
407 i = pCoord->u; | 504 i = pCoord->u; |
408 p[0] = (i>>24)&0xFF; | 505 p[0] = (i>>24)&0xFF; |
409 p[1] = (i>>16)&0xFF; | 506 p[1] = (i>>16)&0xFF; |
410 p[2] = (i>> 8)&0xFF; | 507 p[2] = (i>> 8)&0xFF; |
411 p[3] = (i>> 0)&0xFF; | 508 p[3] = (i>> 0)&0xFF; |
| 509 #endif |
412 return 4; | 510 return 4; |
413 } | 511 } |
414 static int writeInt64(u8 *p, i64 i){ | 512 static int writeInt64(u8 *p, i64 i){ |
| 513 #if SQLITE_BYTEORDER==1234 && (GCC_VERSION>=4003000 || CLANG_VERSION>=3000000) |
| 514 i = (i64)__builtin_bswap64((u64)i); |
| 515 memcpy(p, &i, 8); |
| 516 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 517 i = (i64)_byteswap_uint64((u64)i); |
| 518 memcpy(p, &i, 8); |
| 519 #elif SQLITE_BYTEORDER==4321 |
| 520 memcpy(p, &i, 8); |
| 521 #else |
415 p[0] = (i>>56)&0xFF; | 522 p[0] = (i>>56)&0xFF; |
416 p[1] = (i>>48)&0xFF; | 523 p[1] = (i>>48)&0xFF; |
417 p[2] = (i>>40)&0xFF; | 524 p[2] = (i>>40)&0xFF; |
418 p[3] = (i>>32)&0xFF; | 525 p[3] = (i>>32)&0xFF; |
419 p[4] = (i>>24)&0xFF; | 526 p[4] = (i>>24)&0xFF; |
420 p[5] = (i>>16)&0xFF; | 527 p[5] = (i>>16)&0xFF; |
421 p[6] = (i>> 8)&0xFF; | 528 p[6] = (i>> 8)&0xFF; |
422 p[7] = (i>> 0)&0xFF; | 529 p[7] = (i>> 0)&0xFF; |
| 530 #endif |
423 return 8; | 531 return 8; |
424 } | 532 } |
425 | 533 |
426 /* | 534 /* |
427 ** Increment the reference count of node p. | 535 ** Increment the reference count of node p. |
428 */ | 536 */ |
429 static void nodeReference(RtreeNode *p){ | 537 static void nodeReference(RtreeNode *p){ |
430 if( p ){ | 538 if( p ){ |
431 p->nRef++; | 539 p->nRef++; |
432 } | 540 } |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
496 pNode->zData = (u8 *)&pNode[1]; | 604 pNode->zData = (u8 *)&pNode[1]; |
497 pNode->nRef = 1; | 605 pNode->nRef = 1; |
498 pNode->pParent = pParent; | 606 pNode->pParent = pParent; |
499 pNode->isDirty = 1; | 607 pNode->isDirty = 1; |
500 nodeReference(pParent); | 608 nodeReference(pParent); |
501 } | 609 } |
502 return pNode; | 610 return pNode; |
503 } | 611 } |
504 | 612 |
505 /* | 613 /* |
| 614 ** Clear the Rtree.pNodeBlob object |
| 615 */ |
| 616 static void nodeBlobReset(Rtree *pRtree){ |
| 617 if( pRtree->pNodeBlob && pRtree->inWrTrans==0 && pRtree->nCursor==0 ){ |
| 618 sqlite3_blob *pBlob = pRtree->pNodeBlob; |
| 619 pRtree->pNodeBlob = 0; |
| 620 sqlite3_blob_close(pBlob); |
| 621 } |
| 622 } |
| 623 |
| 624 /* |
506 ** Obtain a reference to an r-tree node. | 625 ** Obtain a reference to an r-tree node. |
507 */ | 626 */ |
508 static int nodeAcquire( | 627 static int nodeAcquire( |
509 Rtree *pRtree, /* R-tree structure */ | 628 Rtree *pRtree, /* R-tree structure */ |
510 i64 iNode, /* Node number to load */ | 629 i64 iNode, /* Node number to load */ |
511 RtreeNode *pParent, /* Either the parent node or NULL */ | 630 RtreeNode *pParent, /* Either the parent node or NULL */ |
512 RtreeNode **ppNode /* OUT: Acquired node */ | 631 RtreeNode **ppNode /* OUT: Acquired node */ |
513 ){ | 632 ){ |
514 int rc; | 633 int rc = SQLITE_OK; |
515 int rc2 = SQLITE_OK; | 634 RtreeNode *pNode = 0; |
516 RtreeNode *pNode; | |
517 | 635 |
518 /* Check if the requested node is already in the hash table. If so, | 636 /* Check if the requested node is already in the hash table. If so, |
519 ** increase its reference count and return it. | 637 ** increase its reference count and return it. |
520 */ | 638 */ |
521 if( (pNode = nodeHashLookup(pRtree, iNode)) ){ | 639 if( (pNode = nodeHashLookup(pRtree, iNode)) ){ |
522 assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); | 640 assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); |
523 if( pParent && !pNode->pParent ){ | 641 if( pParent && !pNode->pParent ){ |
524 nodeReference(pParent); | 642 nodeReference(pParent); |
525 pNode->pParent = pParent; | 643 pNode->pParent = pParent; |
526 } | 644 } |
527 pNode->nRef++; | 645 pNode->nRef++; |
528 *ppNode = pNode; | 646 *ppNode = pNode; |
529 return SQLITE_OK; | 647 return SQLITE_OK; |
530 } | 648 } |
531 | 649 |
532 sqlite3_bind_int64(pRtree->pReadNode, 1, iNode); | 650 if( pRtree->pNodeBlob ){ |
533 rc = sqlite3_step(pRtree->pReadNode); | 651 sqlite3_blob *pBlob = pRtree->pNodeBlob; |
534 if( rc==SQLITE_ROW ){ | 652 pRtree->pNodeBlob = 0; |
535 const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0); | 653 rc = sqlite3_blob_reopen(pBlob, iNode); |
536 if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){ | 654 pRtree->pNodeBlob = pBlob; |
537 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); | 655 if( rc ){ |
538 if( !pNode ){ | 656 nodeBlobReset(pRtree); |
539 rc2 = SQLITE_NOMEM; | 657 if( rc==SQLITE_NOMEM ) return SQLITE_NOMEM; |
540 }else{ | |
541 pNode->pParent = pParent; | |
542 pNode->zData = (u8 *)&pNode[1]; | |
543 pNode->nRef = 1; | |
544 pNode->iNode = iNode; | |
545 pNode->isDirty = 0; | |
546 pNode->pNext = 0; | |
547 memcpy(pNode->zData, zBlob, pRtree->iNodeSize); | |
548 nodeReference(pParent); | |
549 } | |
550 } | 658 } |
551 } | 659 } |
552 rc = sqlite3_reset(pRtree->pReadNode); | 660 if( pRtree->pNodeBlob==0 ){ |
553 if( rc==SQLITE_OK ) rc = rc2; | 661 char *zTab = sqlite3_mprintf("%s_node", pRtree->zName); |
| 662 if( zTab==0 ) return SQLITE_NOMEM; |
| 663 rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, zTab, "data", iNode, 0, |
| 664 &pRtree->pNodeBlob); |
| 665 sqlite3_free(zTab); |
| 666 } |
| 667 if( rc ){ |
| 668 nodeBlobReset(pRtree); |
| 669 *ppNode = 0; |
| 670 /* If unable to open an sqlite3_blob on the desired row, that can only |
| 671 ** be because the shadow tables hold erroneous data. */ |
| 672 if( rc==SQLITE_ERROR ) rc = SQLITE_CORRUPT_VTAB; |
| 673 }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){ |
| 674 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); |
| 675 if( !pNode ){ |
| 676 rc = SQLITE_NOMEM; |
| 677 }else{ |
| 678 pNode->pParent = pParent; |
| 679 pNode->zData = (u8 *)&pNode[1]; |
| 680 pNode->nRef = 1; |
| 681 pNode->iNode = iNode; |
| 682 pNode->isDirty = 0; |
| 683 pNode->pNext = 0; |
| 684 rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData, |
| 685 pRtree->iNodeSize, 0); |
| 686 nodeReference(pParent); |
| 687 } |
| 688 } |
554 | 689 |
555 /* If the root node was just loaded, set pRtree->iDepth to the height | 690 /* If the root node was just loaded, set pRtree->iDepth to the height |
556 ** of the r-tree structure. A height of zero means all data is stored on | 691 ** of the r-tree structure. A height of zero means all data is stored on |
557 ** the root node. A height of one means the children of the root node | 692 ** the root node. A height of one means the children of the root node |
558 ** are the leaves, and so on. If the depth as specified on the root node | 693 ** are the leaves, and so on. If the depth as specified on the root node |
559 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt. | 694 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt. |
560 */ | 695 */ |
561 if( pNode && iNode==1 ){ | 696 if( pNode && iNode==1 ){ |
562 pRtree->iDepth = readInt16(pNode->zData); | 697 pRtree->iDepth = readInt16(pNode->zData); |
563 if( pRtree->iDepth>RTREE_MAX_DEPTH ){ | 698 if( pRtree->iDepth>RTREE_MAX_DEPTH ){ |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
595 */ | 730 */ |
596 static void nodeOverwriteCell( | 731 static void nodeOverwriteCell( |
597 Rtree *pRtree, /* The overall R-Tree */ | 732 Rtree *pRtree, /* The overall R-Tree */ |
598 RtreeNode *pNode, /* The node into which the cell is to be written */ | 733 RtreeNode *pNode, /* The node into which the cell is to be written */ |
599 RtreeCell *pCell, /* The cell to write */ | 734 RtreeCell *pCell, /* The cell to write */ |
600 int iCell /* Index into pNode into which pCell is written */ | 735 int iCell /* Index into pNode into which pCell is written */ |
601 ){ | 736 ){ |
602 int ii; | 737 int ii; |
603 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; | 738 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
604 p += writeInt64(p, pCell->iRowid); | 739 p += writeInt64(p, pCell->iRowid); |
605 for(ii=0; ii<(pRtree->nDim*2); ii++){ | 740 for(ii=0; ii<pRtree->nDim2; ii++){ |
606 p += writeCoord(p, &pCell->aCoord[ii]); | 741 p += writeCoord(p, &pCell->aCoord[ii]); |
607 } | 742 } |
608 pNode->isDirty = 1; | 743 pNode->isDirty = 1; |
609 } | 744 } |
610 | 745 |
611 /* | 746 /* |
612 ** Remove the cell with index iCell from node pNode. | 747 ** Remove the cell with index iCell from node pNode. |
613 */ | 748 */ |
614 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ | 749 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ |
615 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; | 750 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
729 ** to by pCell with the results. | 864 ** to by pCell with the results. |
730 */ | 865 */ |
731 static void nodeGetCell( | 866 static void nodeGetCell( |
732 Rtree *pRtree, /* The overall R-Tree */ | 867 Rtree *pRtree, /* The overall R-Tree */ |
733 RtreeNode *pNode, /* The node containing the cell to be read */ | 868 RtreeNode *pNode, /* The node containing the cell to be read */ |
734 int iCell, /* Index of the cell within the node */ | 869 int iCell, /* Index of the cell within the node */ |
735 RtreeCell *pCell /* OUT: Write the cell contents here */ | 870 RtreeCell *pCell /* OUT: Write the cell contents here */ |
736 ){ | 871 ){ |
737 u8 *pData; | 872 u8 *pData; |
738 RtreeCoord *pCoord; | 873 RtreeCoord *pCoord; |
739 int ii; | 874 int ii = 0; |
740 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); | 875 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); |
741 pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); | 876 pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); |
742 pCoord = pCell->aCoord; | 877 pCoord = pCell->aCoord; |
743 for(ii=0; ii<pRtree->nDim*2; ii++){ | 878 do{ |
744 readCoord(&pData[ii*4], &pCoord[ii]); | 879 readCoord(pData, &pCoord[ii]); |
745 } | 880 readCoord(pData+4, &pCoord[ii+1]); |
| 881 pData += 8; |
| 882 ii += 2; |
| 883 }while( ii<pRtree->nDim2 ); |
746 } | 884 } |
747 | 885 |
748 | 886 |
749 /* Forward declaration for the function that does the work of | 887 /* Forward declaration for the function that does the work of |
750 ** the virtual table module xCreate() and xConnect() methods. | 888 ** the virtual table module xCreate() and xConnect() methods. |
751 */ | 889 */ |
752 static int rtreeInit( | 890 static int rtreeInit( |
753 sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int | 891 sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int |
754 ); | 892 ); |
755 | 893 |
(...skipping 30 matching lines...) Expand all Loading... |
786 pRtree->nBusy++; | 924 pRtree->nBusy++; |
787 } | 925 } |
788 | 926 |
789 /* | 927 /* |
790 ** Decrement the r-tree reference count. When the reference count reaches | 928 ** Decrement the r-tree reference count. When the reference count reaches |
791 ** zero the structure is deleted. | 929 ** zero the structure is deleted. |
792 */ | 930 */ |
793 static void rtreeRelease(Rtree *pRtree){ | 931 static void rtreeRelease(Rtree *pRtree){ |
794 pRtree->nBusy--; | 932 pRtree->nBusy--; |
795 if( pRtree->nBusy==0 ){ | 933 if( pRtree->nBusy==0 ){ |
796 sqlite3_finalize(pRtree->pReadNode); | 934 pRtree->inWrTrans = 0; |
| 935 pRtree->nCursor = 0; |
| 936 nodeBlobReset(pRtree); |
797 sqlite3_finalize(pRtree->pWriteNode); | 937 sqlite3_finalize(pRtree->pWriteNode); |
798 sqlite3_finalize(pRtree->pDeleteNode); | 938 sqlite3_finalize(pRtree->pDeleteNode); |
799 sqlite3_finalize(pRtree->pReadRowid); | 939 sqlite3_finalize(pRtree->pReadRowid); |
800 sqlite3_finalize(pRtree->pWriteRowid); | 940 sqlite3_finalize(pRtree->pWriteRowid); |
801 sqlite3_finalize(pRtree->pDeleteRowid); | 941 sqlite3_finalize(pRtree->pDeleteRowid); |
802 sqlite3_finalize(pRtree->pReadParent); | 942 sqlite3_finalize(pRtree->pReadParent); |
803 sqlite3_finalize(pRtree->pWriteParent); | 943 sqlite3_finalize(pRtree->pWriteParent); |
804 sqlite3_finalize(pRtree->pDeleteParent); | 944 sqlite3_finalize(pRtree->pDeleteParent); |
805 sqlite3_free(pRtree); | 945 sqlite3_free(pRtree); |
806 } | 946 } |
(...skipping 17 matching lines...) Expand all Loading... |
824 "DROP TABLE '%q'.'%q_node';" | 964 "DROP TABLE '%q'.'%q_node';" |
825 "DROP TABLE '%q'.'%q_rowid';" | 965 "DROP TABLE '%q'.'%q_rowid';" |
826 "DROP TABLE '%q'.'%q_parent';", | 966 "DROP TABLE '%q'.'%q_parent';", |
827 pRtree->zDb, pRtree->zName, | 967 pRtree->zDb, pRtree->zName, |
828 pRtree->zDb, pRtree->zName, | 968 pRtree->zDb, pRtree->zName, |
829 pRtree->zDb, pRtree->zName | 969 pRtree->zDb, pRtree->zName |
830 ); | 970 ); |
831 if( !zCreate ){ | 971 if( !zCreate ){ |
832 rc = SQLITE_NOMEM; | 972 rc = SQLITE_NOMEM; |
833 }else{ | 973 }else{ |
| 974 nodeBlobReset(pRtree); |
834 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); | 975 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); |
835 sqlite3_free(zCreate); | 976 sqlite3_free(zCreate); |
836 } | 977 } |
837 if( rc==SQLITE_OK ){ | 978 if( rc==SQLITE_OK ){ |
838 rtreeRelease(pRtree); | 979 rtreeRelease(pRtree); |
839 } | 980 } |
840 | 981 |
841 return rc; | 982 return rc; |
842 } | 983 } |
843 | 984 |
844 /* | 985 /* |
845 ** Rtree virtual table module xOpen method. | 986 ** Rtree virtual table module xOpen method. |
846 */ | 987 */ |
847 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ | 988 static int rtreeOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
848 int rc = SQLITE_NOMEM; | 989 int rc = SQLITE_NOMEM; |
| 990 Rtree *pRtree = (Rtree *)pVTab; |
849 RtreeCursor *pCsr; | 991 RtreeCursor *pCsr; |
850 | 992 |
851 pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor)); | 993 pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor)); |
852 if( pCsr ){ | 994 if( pCsr ){ |
853 memset(pCsr, 0, sizeof(RtreeCursor)); | 995 memset(pCsr, 0, sizeof(RtreeCursor)); |
854 pCsr->base.pVtab = pVTab; | 996 pCsr->base.pVtab = pVTab; |
855 rc = SQLITE_OK; | 997 rc = SQLITE_OK; |
| 998 pRtree->nCursor++; |
856 } | 999 } |
857 *ppCursor = (sqlite3_vtab_cursor *)pCsr; | 1000 *ppCursor = (sqlite3_vtab_cursor *)pCsr; |
858 | 1001 |
859 return rc; | 1002 return rc; |
860 } | 1003 } |
861 | 1004 |
862 | 1005 |
863 /* | 1006 /* |
864 ** Free the RtreeCursor.aConstraint[] array and its contents. | 1007 ** Free the RtreeCursor.aConstraint[] array and its contents. |
865 */ | 1008 */ |
(...skipping 12 matching lines...) Expand all Loading... |
878 } | 1021 } |
879 } | 1022 } |
880 | 1023 |
881 /* | 1024 /* |
882 ** Rtree virtual table module xClose method. | 1025 ** Rtree virtual table module xClose method. |
883 */ | 1026 */ |
884 static int rtreeClose(sqlite3_vtab_cursor *cur){ | 1027 static int rtreeClose(sqlite3_vtab_cursor *cur){ |
885 Rtree *pRtree = (Rtree *)(cur->pVtab); | 1028 Rtree *pRtree = (Rtree *)(cur->pVtab); |
886 int ii; | 1029 int ii; |
887 RtreeCursor *pCsr = (RtreeCursor *)cur; | 1030 RtreeCursor *pCsr = (RtreeCursor *)cur; |
| 1031 assert( pRtree->nCursor>0 ); |
888 freeCursorConstraints(pCsr); | 1032 freeCursorConstraints(pCsr); |
889 sqlite3_free(pCsr->aPoint); | 1033 sqlite3_free(pCsr->aPoint); |
890 for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); | 1034 for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); |
891 sqlite3_free(pCsr); | 1035 sqlite3_free(pCsr); |
| 1036 pRtree->nCursor--; |
| 1037 nodeBlobReset(pRtree); |
892 return SQLITE_OK; | 1038 return SQLITE_OK; |
893 } | 1039 } |
894 | 1040 |
895 /* | 1041 /* |
896 ** Rtree virtual table module xEof method. | 1042 ** Rtree virtual table module xEof method. |
897 ** | 1043 ** |
898 ** Return non-zero if the cursor does not currently point to a valid | 1044 ** Return non-zero if the cursor does not currently point to a valid |
899 ** record (i.e if the scan has finished), or zero otherwise. | 1045 ** record (i.e if the scan has finished), or zero otherwise. |
900 */ | 1046 */ |
901 static int rtreeEof(sqlite3_vtab_cursor *cur){ | 1047 static int rtreeEof(sqlite3_vtab_cursor *cur){ |
902 RtreeCursor *pCsr = (RtreeCursor *)cur; | 1048 RtreeCursor *pCsr = (RtreeCursor *)cur; |
903 return pCsr->atEOF; | 1049 return pCsr->atEOF; |
904 } | 1050 } |
905 | 1051 |
906 /* | 1052 /* |
907 ** Convert raw bits from the on-disk RTree record into a coordinate value. | 1053 ** Convert raw bits from the on-disk RTree record into a coordinate value. |
908 ** The on-disk format is big-endian and needs to be converted for little- | 1054 ** The on-disk format is big-endian and needs to be converted for little- |
909 ** endian platforms. The on-disk record stores integer coordinates if | 1055 ** endian platforms. The on-disk record stores integer coordinates if |
910 ** eInt is true and it stores 32-bit floating point records if eInt is | 1056 ** eInt is true and it stores 32-bit floating point records if eInt is |
911 ** false. a[] is the four bytes of the on-disk record to be decoded. | 1057 ** false. a[] is the four bytes of the on-disk record to be decoded. |
912 ** Store the results in "r". | 1058 ** Store the results in "r". |
913 ** | 1059 ** |
914 ** There are three versions of this macro, one each for little-endian and | 1060 ** There are five versions of this macro. The last one is generic. The |
915 ** big-endian processors and a third generic implementation. The endian- | 1061 ** other four are various architectures-specific optimizations. |
916 ** specific implementations are much faster and are preferred if the | |
917 ** processor endianness is known at compile-time. The SQLITE_BYTEORDER | |
918 ** macro is part of sqliteInt.h and hence the endian-specific | |
919 ** implementation will only be used if this module is compiled as part | |
920 ** of the amalgamation. | |
921 */ | 1062 */ |
922 #if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234 | 1063 #if SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300 |
| 1064 #define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1065 RtreeCoord c; /* Coordinate decoded */ \ |
| 1066 c.u = _byteswap_ulong(*(u32*)a); \ |
| 1067 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1068 } |
| 1069 #elif SQLITE_BYTEORDER==1234 && (GCC_VERSION>=4003000 || CLANG_VERSION>=3000000) |
| 1070 #define RTREE_DECODE_COORD(eInt, a, r) { \ |
| 1071 RtreeCoord c; /* Coordinate decoded */ \ |
| 1072 c.u = __builtin_bswap32(*(u32*)a); \ |
| 1073 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
| 1074 } |
| 1075 #elif SQLITE_BYTEORDER==1234 |
923 #define RTREE_DECODE_COORD(eInt, a, r) { \ | 1076 #define RTREE_DECODE_COORD(eInt, a, r) { \ |
924 RtreeCoord c; /* Coordinate decoded */ \ | 1077 RtreeCoord c; /* Coordinate decoded */ \ |
925 memcpy(&c.u,a,4); \ | 1078 memcpy(&c.u,a,4); \ |
926 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \ | 1079 c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \ |
927 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \ | 1080 ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \ |
928 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ | 1081 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
929 } | 1082 } |
930 #elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321 | 1083 #elif SQLITE_BYTEORDER==4321 |
931 #define RTREE_DECODE_COORD(eInt, a, r) { \ | 1084 #define RTREE_DECODE_COORD(eInt, a, r) { \ |
932 RtreeCoord c; /* Coordinate decoded */ \ | 1085 RtreeCoord c; /* Coordinate decoded */ \ |
933 memcpy(&c.u,a,4); \ | 1086 memcpy(&c.u,a,4); \ |
934 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ | 1087 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
935 } | 1088 } |
936 #else | 1089 #else |
937 #define RTREE_DECODE_COORD(eInt, a, r) { \ | 1090 #define RTREE_DECODE_COORD(eInt, a, r) { \ |
938 RtreeCoord c; /* Coordinate decoded */ \ | 1091 RtreeCoord c; /* Coordinate decoded */ \ |
939 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \ | 1092 c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \ |
940 +((u32)a[2]<<8) + a[3]; \ | 1093 +((u32)a[2]<<8) + a[3]; \ |
941 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ | 1094 r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ |
942 } | 1095 } |
943 #endif | 1096 #endif |
944 | 1097 |
945 /* | 1098 /* |
946 ** Check the RTree node or entry given by pCellData and p against the MATCH | 1099 ** Check the RTree node or entry given by pCellData and p against the MATCH |
947 ** constraint pConstraint. | 1100 ** constraint pConstraint. |
948 */ | 1101 */ |
949 static int rtreeCallbackConstraint( | 1102 static int rtreeCallbackConstraint( |
950 RtreeConstraint *pConstraint, /* The constraint to test */ | 1103 RtreeConstraint *pConstraint, /* The constraint to test */ |
951 int eInt, /* True if RTree holding integer coordinates */ | 1104 int eInt, /* True if RTree holding integer coordinates */ |
952 u8 *pCellData, /* Raw cell content */ | 1105 u8 *pCellData, /* Raw cell content */ |
953 RtreeSearchPoint *pSearch, /* Container of this cell */ | 1106 RtreeSearchPoint *pSearch, /* Container of this cell */ |
954 sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */ | 1107 sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */ |
955 int *peWithin /* OUT: visibility of the cell */ | 1108 int *peWithin /* OUT: visibility of the cell */ |
956 ){ | 1109 ){ |
957 int i; /* Loop counter */ | |
958 sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */ | 1110 sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */ |
959 int nCoord = pInfo->nCoord; /* No. of coordinates */ | 1111 int nCoord = pInfo->nCoord; /* No. of coordinates */ |
960 int rc; /* Callback return code */ | 1112 int rc; /* Callback return code */ |
| 1113 RtreeCoord c; /* Translator union */ |
961 sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */ | 1114 sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */ |
962 | 1115 |
963 assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY ); | 1116 assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY ); |
964 assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 ); | 1117 assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 ); |
965 | 1118 |
966 if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){ | 1119 if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){ |
967 pInfo->iRowid = readInt64(pCellData); | 1120 pInfo->iRowid = readInt64(pCellData); |
968 } | 1121 } |
969 pCellData += 8; | 1122 pCellData += 8; |
970 for(i=0; i<nCoord; i++, pCellData += 4){ | 1123 #ifndef SQLITE_RTREE_INT_ONLY |
971 RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]); | 1124 if( eInt==0 ){ |
| 1125 switch( nCoord ){ |
| 1126 case 10: readCoord(pCellData+36, &c); aCoord[9] = c.f; |
| 1127 readCoord(pCellData+32, &c); aCoord[8] = c.f; |
| 1128 case 8: readCoord(pCellData+28, &c); aCoord[7] = c.f; |
| 1129 readCoord(pCellData+24, &c); aCoord[6] = c.f; |
| 1130 case 6: readCoord(pCellData+20, &c); aCoord[5] = c.f; |
| 1131 readCoord(pCellData+16, &c); aCoord[4] = c.f; |
| 1132 case 4: readCoord(pCellData+12, &c); aCoord[3] = c.f; |
| 1133 readCoord(pCellData+8, &c); aCoord[2] = c.f; |
| 1134 default: readCoord(pCellData+4, &c); aCoord[1] = c.f; |
| 1135 readCoord(pCellData, &c); aCoord[0] = c.f; |
| 1136 } |
| 1137 }else |
| 1138 #endif |
| 1139 { |
| 1140 switch( nCoord ){ |
| 1141 case 10: readCoord(pCellData+36, &c); aCoord[9] = c.i; |
| 1142 readCoord(pCellData+32, &c); aCoord[8] = c.i; |
| 1143 case 8: readCoord(pCellData+28, &c); aCoord[7] = c.i; |
| 1144 readCoord(pCellData+24, &c); aCoord[6] = c.i; |
| 1145 case 6: readCoord(pCellData+20, &c); aCoord[5] = c.i; |
| 1146 readCoord(pCellData+16, &c); aCoord[4] = c.i; |
| 1147 case 4: readCoord(pCellData+12, &c); aCoord[3] = c.i; |
| 1148 readCoord(pCellData+8, &c); aCoord[2] = c.i; |
| 1149 default: readCoord(pCellData+4, &c); aCoord[1] = c.i; |
| 1150 readCoord(pCellData, &c); aCoord[0] = c.i; |
| 1151 } |
972 } | 1152 } |
973 if( pConstraint->op==RTREE_MATCH ){ | 1153 if( pConstraint->op==RTREE_MATCH ){ |
| 1154 int eWithin = 0; |
974 rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo, | 1155 rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo, |
975 nCoord, aCoord, &i); | 1156 nCoord, aCoord, &eWithin); |
976 if( i==0 ) *peWithin = NOT_WITHIN; | 1157 if( eWithin==0 ) *peWithin = NOT_WITHIN; |
977 *prScore = RTREE_ZERO; | 1158 *prScore = RTREE_ZERO; |
978 }else{ | 1159 }else{ |
979 pInfo->aCoord = aCoord; | 1160 pInfo->aCoord = aCoord; |
980 pInfo->iLevel = pSearch->iLevel - 1; | 1161 pInfo->iLevel = pSearch->iLevel - 1; |
981 pInfo->rScore = pInfo->rParentScore = pSearch->rScore; | 1162 pInfo->rScore = pInfo->rParentScore = pSearch->rScore; |
982 pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin; | 1163 pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin; |
983 rc = pConstraint->u.xQueryFunc(pInfo); | 1164 rc = pConstraint->u.xQueryFunc(pInfo); |
984 if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin; | 1165 if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin; |
985 if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){ | 1166 if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){ |
986 *prScore = pInfo->rScore; | 1167 *prScore = pInfo->rScore; |
(...skipping 15 matching lines...) Expand all Loading... |
1002 ){ | 1183 ){ |
1003 sqlite3_rtree_dbl val; /* Coordinate value convert to a double */ | 1184 sqlite3_rtree_dbl val; /* Coordinate value convert to a double */ |
1004 | 1185 |
1005 /* p->iCoord might point to either a lower or upper bound coordinate | 1186 /* p->iCoord might point to either a lower or upper bound coordinate |
1006 ** in a coordinate pair. But make pCellData point to the lower bound. | 1187 ** in a coordinate pair. But make pCellData point to the lower bound. |
1007 */ | 1188 */ |
1008 pCellData += 8 + 4*(p->iCoord&0xfe); | 1189 pCellData += 8 + 4*(p->iCoord&0xfe); |
1009 | 1190 |
1010 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE | 1191 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
1011 || p->op==RTREE_GT || p->op==RTREE_EQ ); | 1192 || p->op==RTREE_GT || p->op==RTREE_EQ ); |
| 1193 assert( ((((char*)pCellData) - (char*)0)&3)==0 ); /* 4-byte aligned */ |
1012 switch( p->op ){ | 1194 switch( p->op ){ |
1013 case RTREE_LE: | 1195 case RTREE_LE: |
1014 case RTREE_LT: | 1196 case RTREE_LT: |
1015 case RTREE_EQ: | 1197 case RTREE_EQ: |
1016 RTREE_DECODE_COORD(eInt, pCellData, val); | 1198 RTREE_DECODE_COORD(eInt, pCellData, val); |
1017 /* val now holds the lower bound of the coordinate pair */ | 1199 /* val now holds the lower bound of the coordinate pair */ |
1018 if( p->u.rValue>=val ) return; | 1200 if( p->u.rValue>=val ) return; |
1019 if( p->op!=RTREE_EQ ) break; /* RTREE_LE and RTREE_LT end here */ | 1201 if( p->op!=RTREE_EQ ) break; /* RTREE_LE and RTREE_LT end here */ |
1020 /* Fall through for the RTREE_EQ case */ | 1202 /* Fall through for the RTREE_EQ case */ |
1021 | 1203 |
(...skipping 20 matching lines...) Expand all Loading... |
1042 RtreeConstraint *p, /* The constraint to test */ | 1224 RtreeConstraint *p, /* The constraint to test */ |
1043 int eInt, /* True if RTree holds integer coordinates */ | 1225 int eInt, /* True if RTree holds integer coordinates */ |
1044 u8 *pCellData, /* Raw cell content as appears on disk */ | 1226 u8 *pCellData, /* Raw cell content as appears on disk */ |
1045 int *peWithin /* Adjust downward, as appropriate */ | 1227 int *peWithin /* Adjust downward, as appropriate */ |
1046 ){ | 1228 ){ |
1047 RtreeDValue xN; /* Coordinate value converted to a double */ | 1229 RtreeDValue xN; /* Coordinate value converted to a double */ |
1048 | 1230 |
1049 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE | 1231 assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE |
1050 || p->op==RTREE_GT || p->op==RTREE_EQ ); | 1232 || p->op==RTREE_GT || p->op==RTREE_EQ ); |
1051 pCellData += 8 + p->iCoord*4; | 1233 pCellData += 8 + p->iCoord*4; |
| 1234 assert( ((((char*)pCellData) - (char*)0)&3)==0 ); /* 4-byte aligned */ |
1052 RTREE_DECODE_COORD(eInt, pCellData, xN); | 1235 RTREE_DECODE_COORD(eInt, pCellData, xN); |
1053 switch( p->op ){ | 1236 switch( p->op ){ |
1054 case RTREE_LE: if( xN <= p->u.rValue ) return; break; | 1237 case RTREE_LE: if( xN <= p->u.rValue ) return; break; |
1055 case RTREE_LT: if( xN < p->u.rValue ) return; break; | 1238 case RTREE_LT: if( xN < p->u.rValue ) return; break; |
1056 case RTREE_GE: if( xN >= p->u.rValue ) return; break; | 1239 case RTREE_GE: if( xN >= p->u.rValue ) return; break; |
1057 case RTREE_GT: if( xN > p->u.rValue ) return; break; | 1240 case RTREE_GT: if( xN > p->u.rValue ) return; break; |
1058 default: if( xN == p->u.rValue ) return; break; | 1241 default: if( xN == p->u.rValue ) return; break; |
1059 } | 1242 } |
1060 *peWithin = NOT_WITHIN; | 1243 *peWithin = NOT_WITHIN; |
1061 } | 1244 } |
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1110 const RtreeSearchPoint *pB | 1293 const RtreeSearchPoint *pB |
1111 ){ | 1294 ){ |
1112 if( pA->rScore<pB->rScore ) return -1; | 1295 if( pA->rScore<pB->rScore ) return -1; |
1113 if( pA->rScore>pB->rScore ) return +1; | 1296 if( pA->rScore>pB->rScore ) return +1; |
1114 if( pA->iLevel<pB->iLevel ) return -1; | 1297 if( pA->iLevel<pB->iLevel ) return -1; |
1115 if( pA->iLevel>pB->iLevel ) return +1; | 1298 if( pA->iLevel>pB->iLevel ) return +1; |
1116 return 0; | 1299 return 0; |
1117 } | 1300 } |
1118 | 1301 |
1119 /* | 1302 /* |
1120 ** Interchange to search points in a cursor. | 1303 ** Interchange two search points in a cursor. |
1121 */ | 1304 */ |
1122 static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){ | 1305 static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){ |
1123 RtreeSearchPoint t = p->aPoint[i]; | 1306 RtreeSearchPoint t = p->aPoint[i]; |
1124 assert( i<j ); | 1307 assert( i<j ); |
1125 p->aPoint[i] = p->aPoint[j]; | 1308 p->aPoint[i] = p->aPoint[j]; |
1126 p->aPoint[j] = t; | 1309 p->aPoint[j] = t; |
1127 i++; j++; | 1310 i++; j++; |
1128 if( i<RTREE_CACHE_SZ ){ | 1311 if( i<RTREE_CACHE_SZ ){ |
1129 if( j>=RTREE_CACHE_SZ ){ | 1312 if( j>=RTREE_CACHE_SZ ){ |
1130 nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); | 1313 nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); |
(...skipping 227 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1358 x.id = p->id; | 1541 x.id = p->id; |
1359 x.iCell = p->iCell - 1; | 1542 x.iCell = p->iCell - 1; |
1360 } | 1543 } |
1361 if( p->iCell>=nCell ){ | 1544 if( p->iCell>=nCell ){ |
1362 RTREE_QUEUE_TRACE(pCur, "POP-S:"); | 1545 RTREE_QUEUE_TRACE(pCur, "POP-S:"); |
1363 rtreeSearchPointPop(pCur); | 1546 rtreeSearchPointPop(pCur); |
1364 } | 1547 } |
1365 if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO; | 1548 if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO; |
1366 p = rtreeSearchPointNew(pCur, rScore, x.iLevel); | 1549 p = rtreeSearchPointNew(pCur, rScore, x.iLevel); |
1367 if( p==0 ) return SQLITE_NOMEM; | 1550 if( p==0 ) return SQLITE_NOMEM; |
1368 p->eWithin = eWithin; | 1551 p->eWithin = (u8)eWithin; |
1369 p->id = x.id; | 1552 p->id = x.id; |
1370 p->iCell = x.iCell; | 1553 p->iCell = x.iCell; |
1371 RTREE_QUEUE_TRACE(pCur, "PUSH-S:"); | 1554 RTREE_QUEUE_TRACE(pCur, "PUSH-S:"); |
1372 break; | 1555 break; |
1373 } | 1556 } |
1374 if( p->iCell>=nCell ){ | 1557 if( p->iCell>=nCell ){ |
1375 RTREE_QUEUE_TRACE(pCur, "POP-Se:"); | 1558 RTREE_QUEUE_TRACE(pCur, "POP-Se:"); |
1376 rtreeSearchPointPop(pCur); | 1559 rtreeSearchPointPop(pCur); |
1377 } | 1560 } |
1378 } | 1561 } |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1417 RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); | 1600 RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); |
1418 RtreeCoord c; | 1601 RtreeCoord c; |
1419 int rc = SQLITE_OK; | 1602 int rc = SQLITE_OK; |
1420 RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); | 1603 RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); |
1421 | 1604 |
1422 if( rc ) return rc; | 1605 if( rc ) return rc; |
1423 if( p==0 ) return SQLITE_OK; | 1606 if( p==0 ) return SQLITE_OK; |
1424 if( i==0 ){ | 1607 if( i==0 ){ |
1425 sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); | 1608 sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); |
1426 }else{ | 1609 }else{ |
1427 if( rc ) return rc; | |
1428 nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); | 1610 nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); |
1429 #ifndef SQLITE_RTREE_INT_ONLY | 1611 #ifndef SQLITE_RTREE_INT_ONLY |
1430 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ | 1612 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
1431 sqlite3_result_double(ctx, c.f); | 1613 sqlite3_result_double(ctx, c.f); |
1432 }else | 1614 }else |
1433 #endif | 1615 #endif |
1434 { | 1616 { |
1435 assert( pRtree->eCoordType==RTREE_COORD_INT32 ); | 1617 assert( pRtree->eCoordType==RTREE_COORD_INT32 ); |
1436 sqlite3_result_int(ctx, c.i); | 1618 sqlite3_result_int(ctx, c.i); |
1437 } | 1619 } |
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1535 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */ | 1717 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */ |
1536 freeCursorConstraints(pCsr); | 1718 freeCursorConstraints(pCsr); |
1537 sqlite3_free(pCsr->aPoint); | 1719 sqlite3_free(pCsr->aPoint); |
1538 memset(pCsr, 0, sizeof(RtreeCursor)); | 1720 memset(pCsr, 0, sizeof(RtreeCursor)); |
1539 pCsr->base.pVtab = (sqlite3_vtab*)pRtree; | 1721 pCsr->base.pVtab = (sqlite3_vtab*)pRtree; |
1540 | 1722 |
1541 pCsr->iStrategy = idxNum; | 1723 pCsr->iStrategy = idxNum; |
1542 if( idxNum==1 ){ | 1724 if( idxNum==1 ){ |
1543 /* Special case - lookup by rowid. */ | 1725 /* Special case - lookup by rowid. */ |
1544 RtreeNode *pLeaf; /* Leaf on which the required cell resides */ | 1726 RtreeNode *pLeaf; /* Leaf on which the required cell resides */ |
1545 RtreeSearchPoint *p; /* Search point for the the leaf */ | 1727 RtreeSearchPoint *p; /* Search point for the leaf */ |
1546 i64 iRowid = sqlite3_value_int64(argv[0]); | 1728 i64 iRowid = sqlite3_value_int64(argv[0]); |
1547 i64 iNode = 0; | 1729 i64 iNode = 0; |
1548 rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); | 1730 rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); |
1549 if( rc==SQLITE_OK && pLeaf!=0 ){ | 1731 if( rc==SQLITE_OK && pLeaf!=0 ){ |
1550 p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0); | 1732 p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0); |
1551 assert( p!=0 ); /* Always returns pCsr->sPoint */ | 1733 assert( p!=0 ); /* Always returns pCsr->sPoint */ |
1552 pCsr->aNode[0] = pLeaf; | 1734 pCsr->aNode[0] = pLeaf; |
1553 p->id = iNode; | 1735 p->id = iNode; |
1554 p->eWithin = PARTLY_WITHIN; | 1736 p->eWithin = PARTLY_WITHIN; |
1555 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); | 1737 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); |
1556 p->iCell = iCell; | 1738 p->iCell = (u8)iCell; |
1557 RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:"); | 1739 RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:"); |
1558 }else{ | 1740 }else{ |
1559 pCsr->atEOF = 1; | 1741 pCsr->atEOF = 1; |
1560 } | 1742 } |
1561 }else{ | 1743 }else{ |
1562 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array | 1744 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array |
1563 ** with the configured constraints. | 1745 ** with the configured constraints. |
1564 */ | 1746 */ |
1565 rc = nodeAcquire(pRtree, 1, 0, &pRoot); | 1747 rc = nodeAcquire(pRtree, 1, 0, &pRoot); |
1566 if( rc==SQLITE_OK && argc>0 ){ | 1748 if( rc==SQLITE_OK && argc>0 ){ |
(...skipping 12 matching lines...) Expand all Loading... |
1579 p->iCoord = idxStr[ii*2+1]-'0'; | 1761 p->iCoord = idxStr[ii*2+1]-'0'; |
1580 if( p->op>=RTREE_MATCH ){ | 1762 if( p->op>=RTREE_MATCH ){ |
1581 /* A MATCH operator. The right-hand-side must be a blob that | 1763 /* A MATCH operator. The right-hand-side must be a blob that |
1582 ** can be cast into an RtreeMatchArg object. One created using | 1764 ** can be cast into an RtreeMatchArg object. One created using |
1583 ** an sqlite3_rtree_geometry_callback() SQL user function. | 1765 ** an sqlite3_rtree_geometry_callback() SQL user function. |
1584 */ | 1766 */ |
1585 rc = deserializeGeometry(argv[ii], p); | 1767 rc = deserializeGeometry(argv[ii], p); |
1586 if( rc!=SQLITE_OK ){ | 1768 if( rc!=SQLITE_OK ){ |
1587 break; | 1769 break; |
1588 } | 1770 } |
1589 p->pInfo->nCoord = pRtree->nDim*2; | 1771 p->pInfo->nCoord = pRtree->nDim2; |
1590 p->pInfo->anQueue = pCsr->anQueue; | 1772 p->pInfo->anQueue = pCsr->anQueue; |
1591 p->pInfo->mxLevel = pRtree->iDepth + 1; | 1773 p->pInfo->mxLevel = pRtree->iDepth + 1; |
1592 }else{ | 1774 }else{ |
1593 #ifdef SQLITE_RTREE_INT_ONLY | 1775 #ifdef SQLITE_RTREE_INT_ONLY |
1594 p->u.rValue = sqlite3_value_int64(argv[ii]); | 1776 p->u.rValue = sqlite3_value_int64(argv[ii]); |
1595 #else | 1777 #else |
1596 p->u.rValue = sqlite3_value_double(argv[ii]); | 1778 p->u.rValue = sqlite3_value_double(argv[ii]); |
1597 #endif | 1779 #endif |
1598 } | 1780 } |
1599 } | 1781 } |
1600 } | 1782 } |
1601 } | 1783 } |
1602 if( rc==SQLITE_OK ){ | 1784 if( rc==SQLITE_OK ){ |
1603 RtreeSearchPoint *pNew; | 1785 RtreeSearchPoint *pNew; |
1604 pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1); | 1786 pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1)); |
1605 if( pNew==0 ) return SQLITE_NOMEM; | 1787 if( pNew==0 ) return SQLITE_NOMEM; |
1606 pNew->id = 1; | 1788 pNew->id = 1; |
1607 pNew->iCell = 0; | 1789 pNew->iCell = 0; |
1608 pNew->eWithin = PARTLY_WITHIN; | 1790 pNew->eWithin = PARTLY_WITHIN; |
1609 assert( pCsr->bPoint==1 ); | 1791 assert( pCsr->bPoint==1 ); |
1610 pCsr->aNode[0] = pRoot; | 1792 pCsr->aNode[0] = pRoot; |
1611 pRoot = 0; | 1793 pRoot = 0; |
1612 RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); | 1794 RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); |
1613 rc = rtreeStepToLeaf(pCsr); | 1795 rc = rtreeStepToLeaf(pCsr); |
1614 } | 1796 } |
1615 } | 1797 } |
1616 | 1798 |
1617 nodeRelease(pRtree, pRoot); | 1799 nodeRelease(pRtree, pRoot); |
1618 rtreeRelease(pRtree); | 1800 rtreeRelease(pRtree); |
1619 return rc; | 1801 return rc; |
1620 } | 1802 } |
1621 | 1803 |
1622 /* | 1804 /* |
1623 ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this | |
1624 ** extension is currently being used by a version of SQLite too old to | |
1625 ** support estimatedRows. In that case this function is a no-op. | |
1626 */ | |
1627 static void setEstimatedRows(sqlite3_index_info *pIdxInfo, i64 nRow){ | |
1628 #if SQLITE_VERSION_NUMBER>=3008002 | |
1629 if( sqlite3_libversion_number()>=3008002 ){ | |
1630 pIdxInfo->estimatedRows = nRow; | |
1631 } | |
1632 #endif | |
1633 } | |
1634 | |
1635 /* | |
1636 ** Rtree virtual table module xBestIndex method. There are three | 1805 ** Rtree virtual table module xBestIndex method. There are three |
1637 ** table scan strategies to choose from (in order from most to | 1806 ** table scan strategies to choose from (in order from most to |
1638 ** least desirable): | 1807 ** least desirable): |
1639 ** | 1808 ** |
1640 ** idxNum idxStr Strategy | 1809 ** idxNum idxStr Strategy |
1641 ** ------------------------------------------------ | 1810 ** ------------------------------------------------ |
1642 ** 1 Unused Direct lookup by rowid. | 1811 ** 1 Unused Direct lookup by rowid. |
1643 ** 2 See below R-tree query or full-table scan. | 1812 ** 2 See below R-tree query or full-table scan. |
1644 ** ------------------------------------------------ | 1813 ** ------------------------------------------------ |
1645 ** | 1814 ** |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1704 pIdxInfo->aConstraintUsage[ii].argvIndex = 1; | 1873 pIdxInfo->aConstraintUsage[ii].argvIndex = 1; |
1705 pIdxInfo->aConstraintUsage[jj].omit = 1; | 1874 pIdxInfo->aConstraintUsage[jj].omit = 1; |
1706 | 1875 |
1707 /* This strategy involves a two rowid lookups on an B-Tree structures | 1876 /* This strategy involves a two rowid lookups on an B-Tree structures |
1708 ** and then a linear search of an R-Tree node. This should be | 1877 ** and then a linear search of an R-Tree node. This should be |
1709 ** considered almost as quick as a direct rowid lookup (for which | 1878 ** considered almost as quick as a direct rowid lookup (for which |
1710 ** sqlite uses an internal cost of 0.0). It is expected to return | 1879 ** sqlite uses an internal cost of 0.0). It is expected to return |
1711 ** a single row. | 1880 ** a single row. |
1712 */ | 1881 */ |
1713 pIdxInfo->estimatedCost = 30.0; | 1882 pIdxInfo->estimatedCost = 30.0; |
1714 setEstimatedRows(pIdxInfo, 1); | 1883 pIdxInfo->estimatedRows = 1; |
1715 return SQLITE_OK; | 1884 return SQLITE_OK; |
1716 } | 1885 } |
1717 | 1886 |
1718 if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){ | 1887 if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){ |
1719 u8 op; | 1888 u8 op; |
1720 switch( p->op ){ | 1889 switch( p->op ){ |
1721 case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break; | 1890 case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break; |
1722 case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break; | 1891 case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break; |
1723 case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break; | 1892 case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break; |
1724 case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break; | 1893 case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break; |
1725 case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; | 1894 case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; |
1726 default: | 1895 default: |
1727 assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH ); | 1896 assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH ); |
1728 op = RTREE_MATCH; | 1897 op = RTREE_MATCH; |
1729 break; | 1898 break; |
1730 } | 1899 } |
1731 zIdxStr[iIdx++] = op; | 1900 zIdxStr[iIdx++] = op; |
1732 zIdxStr[iIdx++] = p->iColumn - 1 + '0'; | 1901 zIdxStr[iIdx++] = (char)(p->iColumn - 1 + '0'); |
1733 pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); | 1902 pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); |
1734 pIdxInfo->aConstraintUsage[ii].omit = 1; | 1903 pIdxInfo->aConstraintUsage[ii].omit = 1; |
1735 } | 1904 } |
1736 } | 1905 } |
1737 | 1906 |
1738 pIdxInfo->idxNum = 2; | 1907 pIdxInfo->idxNum = 2; |
1739 pIdxInfo->needToFreeIdxStr = 1; | 1908 pIdxInfo->needToFreeIdxStr = 1; |
1740 if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ | 1909 if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ |
1741 return SQLITE_NOMEM; | 1910 return SQLITE_NOMEM; |
1742 } | 1911 } |
1743 | 1912 |
1744 nRow = pRtree->nRowEst / (iIdx + 1); | 1913 nRow = pRtree->nRowEst >> (iIdx/2); |
1745 pIdxInfo->estimatedCost = (double)6.0 * (double)nRow; | 1914 pIdxInfo->estimatedCost = (double)6.0 * (double)nRow; |
1746 setEstimatedRows(pIdxInfo, nRow); | 1915 pIdxInfo->estimatedRows = nRow; |
1747 | 1916 |
1748 return rc; | 1917 return rc; |
1749 } | 1918 } |
1750 | 1919 |
1751 /* | 1920 /* |
1752 ** Return the N-dimensional volumn of the cell stored in *p. | 1921 ** Return the N-dimensional volumn of the cell stored in *p. |
1753 */ | 1922 */ |
1754 static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){ | 1923 static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){ |
1755 RtreeDValue area = (RtreeDValue)1; | 1924 RtreeDValue area = (RtreeDValue)1; |
1756 int ii; | 1925 assert( pRtree->nDim>=1 && pRtree->nDim<=5 ); |
1757 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | 1926 #ifndef SQLITE_RTREE_INT_ONLY |
1758 area = (area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]))); | 1927 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
| 1928 switch( pRtree->nDim ){ |
| 1929 case 5: area = p->aCoord[9].f - p->aCoord[8].f; |
| 1930 case 4: area *= p->aCoord[7].f - p->aCoord[6].f; |
| 1931 case 3: area *= p->aCoord[5].f - p->aCoord[4].f; |
| 1932 case 2: area *= p->aCoord[3].f - p->aCoord[2].f; |
| 1933 default: area *= p->aCoord[1].f - p->aCoord[0].f; |
| 1934 } |
| 1935 }else |
| 1936 #endif |
| 1937 { |
| 1938 switch( pRtree->nDim ){ |
| 1939 case 5: area = p->aCoord[9].i - p->aCoord[8].i; |
| 1940 case 4: area *= p->aCoord[7].i - p->aCoord[6].i; |
| 1941 case 3: area *= p->aCoord[5].i - p->aCoord[4].i; |
| 1942 case 2: area *= p->aCoord[3].i - p->aCoord[2].i; |
| 1943 default: area *= p->aCoord[1].i - p->aCoord[0].i; |
| 1944 } |
1759 } | 1945 } |
1760 return area; | 1946 return area; |
1761 } | 1947 } |
1762 | 1948 |
1763 /* | 1949 /* |
1764 ** Return the margin length of cell p. The margin length is the sum | 1950 ** Return the margin length of cell p. The margin length is the sum |
1765 ** of the objects size in each dimension. | 1951 ** of the objects size in each dimension. |
1766 */ | 1952 */ |
1767 static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){ | 1953 static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){ |
1768 RtreeDValue margin = (RtreeDValue)0; | 1954 RtreeDValue margin = 0; |
1769 int ii; | 1955 int ii = pRtree->nDim2 - 2; |
1770 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | 1956 do{ |
1771 margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); | 1957 margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); |
1772 } | 1958 ii -= 2; |
| 1959 }while( ii>=0 ); |
1773 return margin; | 1960 return margin; |
1774 } | 1961 } |
1775 | 1962 |
1776 /* | 1963 /* |
1777 ** Store the union of cells p1 and p2 in p1. | 1964 ** Store the union of cells p1 and p2 in p1. |
1778 */ | 1965 */ |
1779 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ | 1966 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
1780 int ii; | 1967 int ii = 0; |
1781 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ | 1968 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
1782 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | 1969 do{ |
1783 p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); | 1970 p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); |
1784 p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); | 1971 p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); |
1785 } | 1972 ii += 2; |
| 1973 }while( ii<pRtree->nDim2 ); |
1786 }else{ | 1974 }else{ |
1787 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | 1975 do{ |
1788 p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); | 1976 p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); |
1789 p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); | 1977 p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); |
1790 } | 1978 ii += 2; |
| 1979 }while( ii<pRtree->nDim2 ); |
1791 } | 1980 } |
1792 } | 1981 } |
1793 | 1982 |
1794 /* | 1983 /* |
1795 ** Return true if the area covered by p2 is a subset of the area covered | 1984 ** Return true if the area covered by p2 is a subset of the area covered |
1796 ** by p1. False otherwise. | 1985 ** by p1. False otherwise. |
1797 */ | 1986 */ |
1798 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ | 1987 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ |
1799 int ii; | 1988 int ii; |
1800 int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); | 1989 int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); |
1801 for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | 1990 for(ii=0; ii<pRtree->nDim2; ii+=2){ |
1802 RtreeCoord *a1 = &p1->aCoord[ii]; | 1991 RtreeCoord *a1 = &p1->aCoord[ii]; |
1803 RtreeCoord *a2 = &p2->aCoord[ii]; | 1992 RtreeCoord *a2 = &p2->aCoord[ii]; |
1804 if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) | 1993 if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) |
1805 || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) | 1994 || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) |
1806 ){ | 1995 ){ |
1807 return 0; | 1996 return 0; |
1808 } | 1997 } |
1809 } | 1998 } |
1810 return 1; | 1999 return 1; |
1811 } | 2000 } |
(...skipping 14 matching lines...) Expand all Loading... |
1826 Rtree *pRtree, | 2015 Rtree *pRtree, |
1827 RtreeCell *p, | 2016 RtreeCell *p, |
1828 RtreeCell *aCell, | 2017 RtreeCell *aCell, |
1829 int nCell | 2018 int nCell |
1830 ){ | 2019 ){ |
1831 int ii; | 2020 int ii; |
1832 RtreeDValue overlap = RTREE_ZERO; | 2021 RtreeDValue overlap = RTREE_ZERO; |
1833 for(ii=0; ii<nCell; ii++){ | 2022 for(ii=0; ii<nCell; ii++){ |
1834 int jj; | 2023 int jj; |
1835 RtreeDValue o = (RtreeDValue)1; | 2024 RtreeDValue o = (RtreeDValue)1; |
1836 for(jj=0; jj<(pRtree->nDim*2); jj+=2){ | 2025 for(jj=0; jj<pRtree->nDim2; jj+=2){ |
1837 RtreeDValue x1, x2; | 2026 RtreeDValue x1, x2; |
1838 x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); | 2027 x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); |
1839 x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); | 2028 x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); |
1840 if( x2<x1 ){ | 2029 if( x2<x1 ){ |
1841 o = (RtreeDValue)0; | 2030 o = (RtreeDValue)0; |
1842 break; | 2031 break; |
1843 }else{ | 2032 }else{ |
1844 o = o * (x2-x1); | 2033 o = o * (x2-x1); |
1845 } | 2034 } |
1846 } | 2035 } |
(...skipping 946 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2793 static RtreeValue rtreeValueUp(sqlite3_value *v){ | 2982 static RtreeValue rtreeValueUp(sqlite3_value *v){ |
2794 double d = sqlite3_value_double(v); | 2983 double d = sqlite3_value_double(v); |
2795 float f = (float)d; | 2984 float f = (float)d; |
2796 if( f<d ){ | 2985 if( f<d ){ |
2797 f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY)); | 2986 f = (float)(d*(d<0 ? RNDTOWARDS : RNDAWAY)); |
2798 } | 2987 } |
2799 return f; | 2988 return f; |
2800 } | 2989 } |
2801 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */ | 2990 #endif /* !defined(SQLITE_RTREE_INT_ONLY) */ |
2802 | 2991 |
| 2992 /* |
| 2993 ** A constraint has failed while inserting a row into an rtree table. |
| 2994 ** Assuming no OOM error occurs, this function sets the error message |
| 2995 ** (at pRtree->base.zErrMsg) to an appropriate value and returns |
| 2996 ** SQLITE_CONSTRAINT. |
| 2997 ** |
| 2998 ** Parameter iCol is the index of the leftmost column involved in the |
| 2999 ** constraint failure. If it is 0, then the constraint that failed is |
| 3000 ** the unique constraint on the id column. Otherwise, it is the rtree |
| 3001 ** (c1<=c2) constraint on columns iCol and iCol+1 that has failed. |
| 3002 ** |
| 3003 ** If an OOM occurs, SQLITE_NOMEM is returned instead of SQLITE_CONSTRAINT. |
| 3004 */ |
| 3005 static int rtreeConstraintError(Rtree *pRtree, int iCol){ |
| 3006 sqlite3_stmt *pStmt = 0; |
| 3007 char *zSql; |
| 3008 int rc; |
| 3009 |
| 3010 assert( iCol==0 || iCol%2 ); |
| 3011 zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree->zDb, pRtree->zName); |
| 3012 if( zSql ){ |
| 3013 rc = sqlite3_prepare_v2(pRtree->db, zSql, -1, &pStmt, 0); |
| 3014 }else{ |
| 3015 rc = SQLITE_NOMEM; |
| 3016 } |
| 3017 sqlite3_free(zSql); |
| 3018 |
| 3019 if( rc==SQLITE_OK ){ |
| 3020 if( iCol==0 ){ |
| 3021 const char *zCol = sqlite3_column_name(pStmt, 0); |
| 3022 pRtree->base.zErrMsg = sqlite3_mprintf( |
| 3023 "UNIQUE constraint failed: %s.%s", pRtree->zName, zCol |
| 3024 ); |
| 3025 }else{ |
| 3026 const char *zCol1 = sqlite3_column_name(pStmt, iCol); |
| 3027 const char *zCol2 = sqlite3_column_name(pStmt, iCol+1); |
| 3028 pRtree->base.zErrMsg = sqlite3_mprintf( |
| 3029 "rtree constraint failed: %s.(%s<=%s)", pRtree->zName, zCol1, zCol2 |
| 3030 ); |
| 3031 } |
| 3032 } |
| 3033 |
| 3034 sqlite3_finalize(pStmt); |
| 3035 return (rc==SQLITE_OK ? SQLITE_CONSTRAINT : rc); |
| 3036 } |
| 3037 |
| 3038 |
2803 | 3039 |
2804 /* | 3040 /* |
2805 ** The xUpdate method for rtree module virtual tables. | 3041 ** The xUpdate method for rtree module virtual tables. |
2806 */ | 3042 */ |
2807 static int rtreeUpdate( | 3043 static int rtreeUpdate( |
2808 sqlite3_vtab *pVtab, | 3044 sqlite3_vtab *pVtab, |
2809 int nData, | 3045 int nData, |
2810 sqlite3_value **azData, | 3046 sqlite3_value **azData, |
2811 sqlite_int64 *pRowid | 3047 sqlite_int64 *pRowid |
2812 ){ | 3048 ){ |
(...skipping 22 matching lines...) Expand all Loading... |
2835 int ii; | 3071 int ii; |
2836 | 3072 |
2837 /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. | 3073 /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. |
2838 ** | 3074 ** |
2839 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared | 3075 ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared |
2840 ** with "column" that are interpreted as table constraints. | 3076 ** with "column" that are interpreted as table constraints. |
2841 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5)); | 3077 ** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5)); |
2842 ** This problem was discovered after years of use, so we silently ignore | 3078 ** This problem was discovered after years of use, so we silently ignore |
2843 ** these kinds of misdeclared tables to avoid breaking any legacy. | 3079 ** these kinds of misdeclared tables to avoid breaking any legacy. |
2844 */ | 3080 */ |
2845 assert( nData<=(pRtree->nDim*2 + 3) ); | 3081 assert( nData<=(pRtree->nDim2 + 3) ); |
2846 | 3082 |
2847 #ifndef SQLITE_RTREE_INT_ONLY | 3083 #ifndef SQLITE_RTREE_INT_ONLY |
2848 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ | 3084 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ |
2849 for(ii=0; ii<nData-4; ii+=2){ | 3085 for(ii=0; ii<nData-4; ii+=2){ |
2850 cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]); | 3086 cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]); |
2851 cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]); | 3087 cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]); |
2852 if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ | 3088 if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ |
2853 rc = SQLITE_CONSTRAINT; | 3089 rc = rtreeConstraintError(pRtree, ii+1); |
2854 goto constraint; | 3090 goto constraint; |
2855 } | 3091 } |
2856 } | 3092 } |
2857 }else | 3093 }else |
2858 #endif | 3094 #endif |
2859 { | 3095 { |
2860 for(ii=0; ii<nData-4; ii+=2){ | 3096 for(ii=0; ii<nData-4; ii+=2){ |
2861 cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]); | 3097 cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]); |
2862 cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]); | 3098 cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]); |
2863 if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ | 3099 if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ |
2864 rc = SQLITE_CONSTRAINT; | 3100 rc = rtreeConstraintError(pRtree, ii+1); |
2865 goto constraint; | 3101 goto constraint; |
2866 } | 3102 } |
2867 } | 3103 } |
2868 } | 3104 } |
2869 | 3105 |
2870 /* If a rowid value was supplied, check if it is already present in | 3106 /* If a rowid value was supplied, check if it is already present in |
2871 ** the table. If so, the constraint has failed. */ | 3107 ** the table. If so, the constraint has failed. */ |
2872 if( sqlite3_value_type(azData[2])!=SQLITE_NULL ){ | 3108 if( sqlite3_value_type(azData[2])!=SQLITE_NULL ){ |
2873 cell.iRowid = sqlite3_value_int64(azData[2]); | 3109 cell.iRowid = sqlite3_value_int64(azData[2]); |
2874 if( sqlite3_value_type(azData[0])==SQLITE_NULL | 3110 if( sqlite3_value_type(azData[0])==SQLITE_NULL |
2875 || sqlite3_value_int64(azData[0])!=cell.iRowid | 3111 || sqlite3_value_int64(azData[0])!=cell.iRowid |
2876 ){ | 3112 ){ |
2877 int steprc; | 3113 int steprc; |
2878 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); | 3114 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); |
2879 steprc = sqlite3_step(pRtree->pReadRowid); | 3115 steprc = sqlite3_step(pRtree->pReadRowid); |
2880 rc = sqlite3_reset(pRtree->pReadRowid); | 3116 rc = sqlite3_reset(pRtree->pReadRowid); |
2881 if( SQLITE_ROW==steprc ){ | 3117 if( SQLITE_ROW==steprc ){ |
2882 if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){ | 3118 if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){ |
2883 rc = rtreeDeleteRowid(pRtree, cell.iRowid); | 3119 rc = rtreeDeleteRowid(pRtree, cell.iRowid); |
2884 }else{ | 3120 }else{ |
2885 rc = SQLITE_CONSTRAINT; | 3121 rc = rtreeConstraintError(pRtree, 0); |
2886 goto constraint; | 3122 goto constraint; |
2887 } | 3123 } |
2888 } | 3124 } |
2889 } | 3125 } |
2890 bHaveRowid = 1; | 3126 bHaveRowid = 1; |
2891 } | 3127 } |
2892 } | 3128 } |
2893 | 3129 |
2894 /* If azData[0] is not an SQL NULL value, it is the rowid of a | 3130 /* If azData[0] is not an SQL NULL value, it is the rowid of a |
2895 ** record to delete from the r-tree table. The following block does | 3131 ** record to delete from the r-tree table. The following block does |
(...skipping 30 matching lines...) Expand all Loading... |
2926 } | 3162 } |
2927 } | 3163 } |
2928 } | 3164 } |
2929 | 3165 |
2930 constraint: | 3166 constraint: |
2931 rtreeRelease(pRtree); | 3167 rtreeRelease(pRtree); |
2932 return rc; | 3168 return rc; |
2933 } | 3169 } |
2934 | 3170 |
2935 /* | 3171 /* |
| 3172 ** Called when a transaction starts. |
| 3173 */ |
| 3174 static int rtreeBeginTransaction(sqlite3_vtab *pVtab){ |
| 3175 Rtree *pRtree = (Rtree *)pVtab; |
| 3176 assert( pRtree->inWrTrans==0 ); |
| 3177 pRtree->inWrTrans++; |
| 3178 return SQLITE_OK; |
| 3179 } |
| 3180 |
| 3181 /* |
| 3182 ** Called when a transaction completes (either by COMMIT or ROLLBACK). |
| 3183 ** The sqlite3_blob object should be released at this point. |
| 3184 */ |
| 3185 static int rtreeEndTransaction(sqlite3_vtab *pVtab){ |
| 3186 Rtree *pRtree = (Rtree *)pVtab; |
| 3187 pRtree->inWrTrans = 0; |
| 3188 nodeBlobReset(pRtree); |
| 3189 return SQLITE_OK; |
| 3190 } |
| 3191 |
| 3192 /* |
2936 ** The xRename method for rtree module virtual tables. | 3193 ** The xRename method for rtree module virtual tables. |
2937 */ | 3194 */ |
2938 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){ | 3195 static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){ |
2939 Rtree *pRtree = (Rtree *)pVtab; | 3196 Rtree *pRtree = (Rtree *)pVtab; |
2940 int rc = SQLITE_NOMEM; | 3197 int rc = SQLITE_NOMEM; |
2941 char *zSql = sqlite3_mprintf( | 3198 char *zSql = sqlite3_mprintf( |
2942 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";" | 3199 "ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";" |
2943 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";" | 3200 "ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";" |
2944 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";" | 3201 "ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";" |
2945 , pRtree->zDb, pRtree->zName, zNewName | 3202 , pRtree->zDb, pRtree->zName, zNewName |
2946 , pRtree->zDb, pRtree->zName, zNewName | 3203 , pRtree->zDb, pRtree->zName, zNewName |
2947 , pRtree->zDb, pRtree->zName, zNewName | 3204 , pRtree->zDb, pRtree->zName, zNewName |
2948 ); | 3205 ); |
2949 if( zSql ){ | 3206 if( zSql ){ |
2950 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); | 3207 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); |
2951 sqlite3_free(zSql); | 3208 sqlite3_free(zSql); |
2952 } | 3209 } |
2953 return rc; | 3210 return rc; |
2954 } | 3211 } |
2955 | 3212 |
| 3213 |
2956 /* | 3214 /* |
2957 ** This function populates the pRtree->nRowEst variable with an estimate | 3215 ** This function populates the pRtree->nRowEst variable with an estimate |
2958 ** of the number of rows in the virtual table. If possible, this is based | 3216 ** of the number of rows in the virtual table. If possible, this is based |
2959 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST. | 3217 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST. |
2960 */ | 3218 */ |
2961 static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){ | 3219 static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){ |
2962 const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'"; | 3220 const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'"; |
2963 char *zSql; | 3221 char *zSql; |
2964 sqlite3_stmt *p; | 3222 sqlite3_stmt *p; |
2965 int rc; | 3223 int rc; |
2966 i64 nRow = 0; | 3224 i64 nRow = 0; |
2967 | 3225 |
| 3226 rc = sqlite3_table_column_metadata( |
| 3227 db, pRtree->zDb, "sqlite_stat1",0,0,0,0,0,0 |
| 3228 ); |
| 3229 if( rc!=SQLITE_OK ){ |
| 3230 pRtree->nRowEst = RTREE_DEFAULT_ROWEST; |
| 3231 return rc==SQLITE_ERROR ? SQLITE_OK : rc; |
| 3232 } |
2968 zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName); | 3233 zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName); |
2969 if( zSql==0 ){ | 3234 if( zSql==0 ){ |
2970 rc = SQLITE_NOMEM; | 3235 rc = SQLITE_NOMEM; |
2971 }else{ | 3236 }else{ |
2972 rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0); | 3237 rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0); |
2973 if( rc==SQLITE_OK ){ | 3238 if( rc==SQLITE_OK ){ |
2974 if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0); | 3239 if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0); |
2975 rc = sqlite3_finalize(p); | 3240 rc = sqlite3_finalize(p); |
2976 }else if( rc!=SQLITE_NOMEM ){ | 3241 }else if( rc!=SQLITE_NOMEM ){ |
2977 rc = SQLITE_OK; | 3242 rc = SQLITE_OK; |
(...skipping 20 matching lines...) Expand all Loading... |
2998 rtreeDisconnect, /* xDisconnect - Disconnect from a table */ | 3263 rtreeDisconnect, /* xDisconnect - Disconnect from a table */ |
2999 rtreeDestroy, /* xDestroy - Drop a table */ | 3264 rtreeDestroy, /* xDestroy - Drop a table */ |
3000 rtreeOpen, /* xOpen - open a cursor */ | 3265 rtreeOpen, /* xOpen - open a cursor */ |
3001 rtreeClose, /* xClose - close a cursor */ | 3266 rtreeClose, /* xClose - close a cursor */ |
3002 rtreeFilter, /* xFilter - configure scan constraints */ | 3267 rtreeFilter, /* xFilter - configure scan constraints */ |
3003 rtreeNext, /* xNext - advance a cursor */ | 3268 rtreeNext, /* xNext - advance a cursor */ |
3004 rtreeEof, /* xEof */ | 3269 rtreeEof, /* xEof */ |
3005 rtreeColumn, /* xColumn - read data */ | 3270 rtreeColumn, /* xColumn - read data */ |
3006 rtreeRowid, /* xRowid - read data */ | 3271 rtreeRowid, /* xRowid - read data */ |
3007 rtreeUpdate, /* xUpdate - write data */ | 3272 rtreeUpdate, /* xUpdate - write data */ |
3008 0, /* xBegin - begin transaction */ | 3273 rtreeBeginTransaction, /* xBegin - begin transaction */ |
3009 0, /* xSync - sync transaction */ | 3274 rtreeEndTransaction, /* xSync - sync transaction */ |
3010 0, /* xCommit - commit transaction */ | 3275 rtreeEndTransaction, /* xCommit - commit transaction */ |
3011 0, /* xRollback - rollback transaction */ | 3276 rtreeEndTransaction, /* xRollback - rollback transaction */ |
3012 0, /* xFindFunction - function overloading */ | 3277 0, /* xFindFunction - function overloading */ |
3013 rtreeRename, /* xRename - rename the table */ | 3278 rtreeRename, /* xRename - rename the table */ |
3014 0, /* xSavepoint */ | 3279 0, /* xSavepoint */ |
3015 0, /* xRelease */ | 3280 0, /* xRelease */ |
3016 0 /* xRollbackTo */ | 3281 0, /* xRollbackTo */ |
3017 }; | 3282 }; |
3018 | 3283 |
3019 static int rtreeSqlInit( | 3284 static int rtreeSqlInit( |
3020 Rtree *pRtree, | 3285 Rtree *pRtree, |
3021 sqlite3 *db, | 3286 sqlite3 *db, |
3022 const char *zDb, | 3287 const char *zDb, |
3023 const char *zPrefix, | 3288 const char *zPrefix, |
3024 int isCreate | 3289 int isCreate |
3025 ){ | 3290 ){ |
3026 int rc = SQLITE_OK; | 3291 int rc = SQLITE_OK; |
3027 | 3292 |
3028 #define N_STATEMENT 9 | 3293 #define N_STATEMENT 8 |
3029 static const char *azSql[N_STATEMENT] = { | 3294 static const char *azSql[N_STATEMENT] = { |
3030 /* Read and write the xxx_node table */ | 3295 /* Write the xxx_node table */ |
3031 "SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1", | |
3032 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)", | 3296 "INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)", |
3033 "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1", | 3297 "DELETE FROM '%q'.'%q_node' WHERE nodeno = :1", |
3034 | 3298 |
3035 /* Read and write the xxx_rowid table */ | 3299 /* Read and write the xxx_rowid table */ |
3036 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1", | 3300 "SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1", |
3037 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)", | 3301 "INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)", |
3038 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1", | 3302 "DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1", |
3039 | 3303 |
3040 /* Read and write the xxx_parent table */ | 3304 /* Read and write the xxx_parent table */ |
3041 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1", | 3305 "SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1", |
(...skipping 17 matching lines...) Expand all Loading... |
3059 if( !zCreate ){ | 3323 if( !zCreate ){ |
3060 return SQLITE_NOMEM; | 3324 return SQLITE_NOMEM; |
3061 } | 3325 } |
3062 rc = sqlite3_exec(db, zCreate, 0, 0, 0); | 3326 rc = sqlite3_exec(db, zCreate, 0, 0, 0); |
3063 sqlite3_free(zCreate); | 3327 sqlite3_free(zCreate); |
3064 if( rc!=SQLITE_OK ){ | 3328 if( rc!=SQLITE_OK ){ |
3065 return rc; | 3329 return rc; |
3066 } | 3330 } |
3067 } | 3331 } |
3068 | 3332 |
3069 appStmt[0] = &pRtree->pReadNode; | 3333 appStmt[0] = &pRtree->pWriteNode; |
3070 appStmt[1] = &pRtree->pWriteNode; | 3334 appStmt[1] = &pRtree->pDeleteNode; |
3071 appStmt[2] = &pRtree->pDeleteNode; | 3335 appStmt[2] = &pRtree->pReadRowid; |
3072 appStmt[3] = &pRtree->pReadRowid; | 3336 appStmt[3] = &pRtree->pWriteRowid; |
3073 appStmt[4] = &pRtree->pWriteRowid; | 3337 appStmt[4] = &pRtree->pDeleteRowid; |
3074 appStmt[5] = &pRtree->pDeleteRowid; | 3338 appStmt[5] = &pRtree->pReadParent; |
3075 appStmt[6] = &pRtree->pReadParent; | 3339 appStmt[6] = &pRtree->pWriteParent; |
3076 appStmt[7] = &pRtree->pWriteParent; | 3340 appStmt[7] = &pRtree->pDeleteParent; |
3077 appStmt[8] = &pRtree->pDeleteParent; | |
3078 | 3341 |
3079 rc = rtreeQueryStat1(db, pRtree); | 3342 rc = rtreeQueryStat1(db, pRtree); |
3080 for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){ | 3343 for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){ |
3081 char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix); | 3344 char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix); |
3082 if( zSql ){ | 3345 if( zSql ){ |
3083 rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); | 3346 rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0); |
3084 }else{ | 3347 }else{ |
3085 rc = SQLITE_NOMEM; | 3348 rc = SQLITE_NOMEM; |
3086 } | 3349 } |
3087 sqlite3_free(zSql); | 3350 sqlite3_free(zSql); |
(...skipping 117 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3205 nName = (int)strlen(argv[2]); | 3468 nName = (int)strlen(argv[2]); |
3206 pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2); | 3469 pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2); |
3207 if( !pRtree ){ | 3470 if( !pRtree ){ |
3208 return SQLITE_NOMEM; | 3471 return SQLITE_NOMEM; |
3209 } | 3472 } |
3210 memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); | 3473 memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); |
3211 pRtree->nBusy = 1; | 3474 pRtree->nBusy = 1; |
3212 pRtree->base.pModule = &rtreeModule; | 3475 pRtree->base.pModule = &rtreeModule; |
3213 pRtree->zDb = (char *)&pRtree[1]; | 3476 pRtree->zDb = (char *)&pRtree[1]; |
3214 pRtree->zName = &pRtree->zDb[nDb+1]; | 3477 pRtree->zName = &pRtree->zDb[nDb+1]; |
3215 pRtree->nDim = (argc-4)/2; | 3478 pRtree->nDim = (u8)((argc-4)/2); |
3216 pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2; | 3479 pRtree->nDim2 = pRtree->nDim*2; |
3217 pRtree->eCoordType = eCoordType; | 3480 pRtree->nBytesPerCell = 8 + pRtree->nDim2*4; |
| 3481 pRtree->eCoordType = (u8)eCoordType; |
3218 memcpy(pRtree->zDb, argv[1], nDb); | 3482 memcpy(pRtree->zDb, argv[1], nDb); |
3219 memcpy(pRtree->zName, argv[2], nName); | 3483 memcpy(pRtree->zName, argv[2], nName); |
3220 | 3484 |
3221 /* Figure out the node size to use. */ | 3485 /* Figure out the node size to use. */ |
3222 rc = getNodeSize(db, pRtree, isCreate, pzErr); | 3486 rc = getNodeSize(db, pRtree, isCreate, pzErr); |
3223 | 3487 |
3224 /* Create/Connect to the underlying relational database schema. If | 3488 /* Create/Connect to the underlying relational database schema. If |
3225 ** that is successful, call sqlite3_declare_vtab() to configure | 3489 ** that is successful, call sqlite3_declare_vtab() to configure |
3226 ** the r-tree table schema. | 3490 ** the r-tree table schema. |
3227 */ | 3491 */ |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3280 */ | 3544 */ |
3281 static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ | 3545 static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ |
3282 char *zText = 0; | 3546 char *zText = 0; |
3283 RtreeNode node; | 3547 RtreeNode node; |
3284 Rtree tree; | 3548 Rtree tree; |
3285 int ii; | 3549 int ii; |
3286 | 3550 |
3287 UNUSED_PARAMETER(nArg); | 3551 UNUSED_PARAMETER(nArg); |
3288 memset(&node, 0, sizeof(RtreeNode)); | 3552 memset(&node, 0, sizeof(RtreeNode)); |
3289 memset(&tree, 0, sizeof(Rtree)); | 3553 memset(&tree, 0, sizeof(Rtree)); |
3290 tree.nDim = sqlite3_value_int(apArg[0]); | 3554 tree.nDim = (u8)sqlite3_value_int(apArg[0]); |
| 3555 tree.nDim2 = tree.nDim*2; |
3291 tree.nBytesPerCell = 8 + 8 * tree.nDim; | 3556 tree.nBytesPerCell = 8 + 8 * tree.nDim; |
3292 node.zData = (u8 *)sqlite3_value_blob(apArg[1]); | 3557 node.zData = (u8 *)sqlite3_value_blob(apArg[1]); |
3293 | 3558 |
3294 for(ii=0; ii<NCELL(&node); ii++){ | 3559 for(ii=0; ii<NCELL(&node); ii++){ |
3295 char zCell[512]; | 3560 char zCell[512]; |
3296 int nCell = 0; | 3561 int nCell = 0; |
3297 RtreeCell cell; | 3562 RtreeCell cell; |
3298 int jj; | 3563 int jj; |
3299 | 3564 |
3300 nodeGetCell(&tree, &node, ii, &cell); | 3565 nodeGetCell(&tree, &node, ii, &cell); |
3301 sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid); | 3566 sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid); |
3302 nCell = (int)strlen(zCell); | 3567 nCell = (int)strlen(zCell); |
3303 for(jj=0; jj<tree.nDim*2; jj++){ | 3568 for(jj=0; jj<tree.nDim2; jj++){ |
3304 #ifndef SQLITE_RTREE_INT_ONLY | 3569 #ifndef SQLITE_RTREE_INT_ONLY |
3305 sqlite3_snprintf(512-nCell,&zCell[nCell], " %g", | 3570 sqlite3_snprintf(512-nCell,&zCell[nCell], " %g", |
3306 (double)cell.aCoord[jj].f); | 3571 (double)cell.aCoord[jj].f); |
3307 #else | 3572 #else |
3308 sqlite3_snprintf(512-nCell,&zCell[nCell], " %d", | 3573 sqlite3_snprintf(512-nCell,&zCell[nCell], " %d", |
3309 cell.aCoord[jj].i); | 3574 cell.aCoord[jj].i); |
3310 #endif | 3575 #endif |
3311 nCell = (int)strlen(zCell); | 3576 nCell = (int)strlen(zCell); |
3312 } | 3577 } |
3313 | 3578 |
(...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3503 sqlite3 *db, | 3768 sqlite3 *db, |
3504 char **pzErrMsg, | 3769 char **pzErrMsg, |
3505 const sqlite3_api_routines *pApi | 3770 const sqlite3_api_routines *pApi |
3506 ){ | 3771 ){ |
3507 SQLITE_EXTENSION_INIT2(pApi) | 3772 SQLITE_EXTENSION_INIT2(pApi) |
3508 return sqlite3RtreeInit(db); | 3773 return sqlite3RtreeInit(db); |
3509 } | 3774 } |
3510 #endif | 3775 #endif |
3511 | 3776 |
3512 #endif | 3777 #endif |
OLD | NEW |