/ Check-in [f864bacc]
Login

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: f864baccd3fe0ee939ac1ec20069792f649cddc0
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

  1235   1235   # define RTREE_QUEUE_TRACE(A,B)   /* no-op */
  1236   1236   #endif
  1237   1237   
  1238   1238   /* Remove the search point with the lowest current score.
  1239   1239   */
  1240   1240   static void rtreeSearchPointPop(RtreeCursor *p){
  1241   1241     int i, j, k, n;
  1242         -  i = p->bPoint;
         1242  +  i = 1 - p->bPoint;
  1243   1243     assert( i==0 || i==1 );
  1244   1244     if( p->aNode[i] ){
  1245   1245       nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
  1246   1246       p->aNode[i] = 0;
  1247   1247     }
  1248   1248     if( p->bPoint ){
  1249   1249       p->bPoint = 0;
................................................................................
  1341   1341   static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  1342   1342     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1343   1343     int rc = SQLITE_OK;
  1344   1344   
  1345   1345     /* Move to the next entry that matches the configured constraints. */
  1346   1346     RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
  1347   1347     rtreeSearchPointPop(pCsr);
  1348         -  rtreeStepToLeaf(pCsr);
         1348  +  rc = rtreeStepToLeaf(pCsr);
  1349   1349     return rc;
  1350   1350   }
  1351   1351   
  1352   1352   /* 
  1353   1353   ** Rtree virtual table module xRowid method.
  1354   1354   */
  1355   1355   static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
................................................................................
  1486   1486     pCsr->iStrategy = idxNum;
  1487   1487   
  1488   1488     if( idxNum==1 ){
  1489   1489       /* Special case - lookup by rowid. */
  1490   1490       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
  1491   1491       RtreeSearchPoint *p;     /* Search point for the the leaf */
  1492   1492       i64 iRowid = sqlite3_value_int64(argv[0]);
  1493         -    p = rtreeSearchPointNew(pCsr, 0.0, 0);
  1494         -    if( p==0 ) return SQLITE_NOMEM;
  1495         -    rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
  1496         -    pCsr->aNode[0] = pLeaf;
  1497         -    p->eWithin = PARTLY_WITHIN;
  1498         -    if( rc==SQLITE_OK ){
         1493  +    i64 iNode = 0;
         1494  +    rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
         1495  +    if( rc==SQLITE_OK && pLeaf!=0 ){
         1496  +      p = rtreeSearchPointNew(pCsr, 0.0, 0);
         1497  +      assert( p!=0 );  /* Always returns pCsr->sPoint */
         1498  +      pCsr->aNode[0] = pLeaf;
         1499  +      p->id = iNode;
         1500  +      p->eWithin = PARTLY_WITHIN;
  1499   1501         rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
         1502  +      p->iCell = iCell;
         1503  +      RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
         1504  +    }else{
         1505  +      pCsr->atEOF = 1;
  1500   1506       }
  1501         -    p->iCell = iCell;
  1502         -    RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
  1503   1507     }else{
  1504   1508       /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
  1505   1509       ** with the configured constraints. 
  1506   1510       */
  1507   1511       if( argc>0 ){
  1508   1512         pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
  1509   1513         pCsr->nConstraint = argc;

Changes to ext/rtree/rtreeB.test.

    37     37         INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
    38     38         INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
    39     39         INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
    40     40         INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
    41     41         INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
    42     42         SELECT rtreenode(2, data) FROM t1_node;
    43     43       }
    44         -  } {{{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}}}
           44  +  } {{{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}}}
    45     45   }
    46     46   
    47     47   finish_test