Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | TCL tests now all pass. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | rtree-queue |
| Files: | files | file ages | folders |
| SHA1: |
f864baccd3fe0ee939ac1ec20069792f |
| User & Date: | drh 2014-04-16 17:15:14 |
Context
|
2014-04-16
| ||
| 17:23 | Convert the RTree module query mechanism over to using a priority queue for walking the RTree. check-in: f26936f7 user: drh tags: rtree-enhancements | |
| 17:15 | TCL tests now all pass. Closed-Leaf check-in: f864bacc user: drh tags: rtree-queue | |
| 14:45 | Fix a bug in rowid=? query handling. More problems remain. check-in: 5b0e6ba4 user: drh tags: rtree-queue | |
Changes
Changes to ext/rtree/rtree.c.
1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 .... 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 .... 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 |
# define RTREE_QUEUE_TRACE(A,B) /* no-op */
#endif
/* Remove the search point with the lowest current score.
*/
static void rtreeSearchPointPop(RtreeCursor *p){
int i, j, k, n;
i = p->bPoint;
assert( i==0 || i==1 );
if( p->aNode[i] ){
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
p->aNode[i] = 0;
}
if( p->bPoint ){
p->bPoint = 0;
................................................................................
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
int rc = SQLITE_OK;
/* Move to the next entry that matches the configured constraints. */
RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
rtreeSearchPointPop(pCsr);
rtreeStepToLeaf(pCsr);
return rc;
}
/*
** Rtree virtual table module xRowid method.
*/
static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
................................................................................
pCsr->iStrategy = idxNum;
if( idxNum==1 ){
/* Special case - lookup by rowid. */
RtreeNode *pLeaf; /* Leaf on which the required cell resides */
RtreeSearchPoint *p; /* Search point for the the leaf */
i64 iRowid = sqlite3_value_int64(argv[0]);
p = rtreeSearchPointNew(pCsr, 0.0, 0);
if( p==0 ) return SQLITE_NOMEM;
rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
pCsr->aNode[0] = pLeaf;
p->eWithin = PARTLY_WITHIN;
if( rc==SQLITE_OK ){
rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
}
p->iCell = iCell;
RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
}else{
/* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
** with the configured constraints.
*/
if( argc>0 ){
pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
pCsr->nConstraint = argc;
|
| | > > > | < < > | > | < < | | > > > |
1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 .... 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 .... 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 |
# define RTREE_QUEUE_TRACE(A,B) /* no-op */
#endif
/* Remove the search point with the lowest current score.
*/
static void rtreeSearchPointPop(RtreeCursor *p){
int i, j, k, n;
i = 1 - p->bPoint;
assert( i==0 || i==1 );
if( p->aNode[i] ){
nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
p->aNode[i] = 0;
}
if( p->bPoint ){
p->bPoint = 0;
................................................................................
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
int rc = SQLITE_OK;
/* Move to the next entry that matches the configured constraints. */
RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
rtreeSearchPointPop(pCsr);
rc = rtreeStepToLeaf(pCsr);
return rc;
}
/*
** Rtree virtual table module xRowid method.
*/
static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
................................................................................
pCsr->iStrategy = idxNum;
if( idxNum==1 ){
/* Special case - lookup by rowid. */
RtreeNode *pLeaf; /* Leaf on which the required cell resides */
RtreeSearchPoint *p; /* Search point for the the leaf */
i64 iRowid = sqlite3_value_int64(argv[0]);
i64 iNode = 0;
rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
if( rc==SQLITE_OK && pLeaf!=0 ){
p = rtreeSearchPointNew(pCsr, 0.0, 0);
assert( p!=0 ); /* Always returns pCsr->sPoint */
pCsr->aNode[0] = pLeaf;
p->id = iNode;
p->eWithin = PARTLY_WITHIN;
rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
p->iCell = iCell;
RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
}else{
pCsr->atEOF = 1;
}
}else{
/* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
** with the configured constraints.
*/
if( argc>0 ){
pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
pCsr->nConstraint = argc;
|
Changes to ext/rtree/rtreeB.test.
37 38 39 40 41 42 43 44 45 46 47 |
INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
SELECT rtreenode(2, data) FROM t1_node;
}
} {{{1073741824 0.000000 0.000000 100.000000 100.000000} {2147483646 0.000000 0.000000 200.000000 200.000000} {4294967296 0.000000 0.000000 300.000000 300.000000} {8589934592 20.000000 20.000000 150.000000 150.000000} {9223372036854775807 150.000000 150.000000 400.000000 400.000000}}}
}
finish_test
|
| |
37 38 39 40 41 42 43 44 45 46 47 |
INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
SELECT rtreenode(2, data) FROM t1_node;
}
} {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
}
finish_test
|