SQLite

Check-in [f864baccd3]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:TCL tests now all pass.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | rtree-queue
Files: files | file ages | folders
SHA1: f864baccd3fe0ee939ac1ec20069792f649cddc0
User & Date: drh 2014-04-16 17:15:14.114
Context
2014-04-16
17:23
Convert the RTree module query mechanism over to using a priority queue for walking the RTree. (check-in: f26936f71a user: drh tags: rtree-enhancements)
17:15
TCL tests now all pass. (Closed-Leaf check-in: f864baccd3 user: drh tags: rtree-queue)
14:45
Fix a bug in rowid=? query handling. More problems remain. (check-in: 5b0e6ba4a5 user: drh tags: rtree-queue)
Changes
Unified Diff Ignore Whitespace Patch
Changes to ext/rtree/rtree.c.
︙︙
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249

# 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;








|








1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249

# 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;
︙︙
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355

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){








|








1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355

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){
︙︙
1486
1487
1488
1489
1490
1491
1492



1493
1494
1495
1496

1497
1498
1499
1500
1501
1502



1503
1504
1505
1506
1507
1508
1509

  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;








>
>
>
|
|
<
|
>
|
<

<
|
|
>
>
>








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

  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