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
Side-by-Side 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
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;
  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
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);
  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
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);
    if( p==0 ) return SQLITE_NOMEM;
      p = rtreeSearchPointNew(pCsr, 0.0, 0);
      assert( p!=0 );  /* Always returns pCsr->sPoint */
    rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
    pCsr->aNode[0] = pLeaf;
    p->eWithin = PARTLY_WITHIN;
      pCsr->aNode[0] = pLeaf;
      p->id = iNode;
      p->eWithin = PARTLY_WITHIN;
    if( rc==SQLITE_OK ){
      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
    }
    p->iCell = iCell;
    RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
      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
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}}}
  } {{{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