/ Check-in [1ccaaed6]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Test cases and bug fixes for the sqlite3_rtree_query_callback() mechanism.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-enhancements
Files: files | file ages | folders
SHA1: 1ccaaed6b516ec2ce953c1b31025a82ba76d00e7
User & Date: drh 2014-04-17 14:52:20
Context
2014-04-17
15:34
More test cases with very long priority queues. check-in: 71692aa9 user: drh tags: rtree-enhancements
14:52
Test cases and bug fixes for the sqlite3_rtree_query_callback() mechanism. check-in: 1ccaaed6 user: drh tags: rtree-enhancements
13:15
Refactor the constraint checking logic in RTree. The new-style constraint callbacks created by sqlite3_rtree_query_callback() are now hooked up from end to end, though still untested. check-in: 32a13870 user: drh tags: rtree-enhancements
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to ext/rtree/rtree.c.

   158    158   ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
   159    159   ** only deal with integer coordinates.  No floating point operations
   160    160   ** will be done.
   161    161   */
   162    162   #ifdef SQLITE_RTREE_INT_ONLY
   163    163     typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
   164    164     typedef int RtreeValue;                  /* Low accuracy coordinate */
          165  +# define RTREE_ZERO 0
   165    166   #else
   166    167     typedef double RtreeDValue;              /* High accuracy coordinate */
   167    168     typedef float RtreeValue;                /* Low accuracy coordinate */
          169  +# define RTREE_ZERO 0.0
   168    170   #endif
   169    171   
   170    172   /*
   171    173   ** When doing a search of an r-tree, instances of the following structure
   172    174   ** record intermediate results from the tree walk.
   173    175   **
   174    176   ** The id is always a node-id.  For iLevel>=1 the id is the node-id of
................................................................................
   266    268     int iCoord;                     /* Index of constrained coordinate */
   267    269     int op;                         /* Constraining operation */
   268    270     union {
   269    271       RtreeDValue rValue;             /* Constraint value. */
   270    272       int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
   271    273       int (*xQueryFunc)(sqlite3_rtree_query_info*);
   272    274     } u;
   273         -  sqlite3_rtree_query_info *pGeom;  /* xGeom and xQueryFunc argument */
          275  +  sqlite3_rtree_query_info *pInfo;  /* xGeom and xQueryFunc argument */
   274    276   };
   275    277   
   276    278   /* Possible values for RtreeConstraint.op */
   277    279   #define RTREE_EQ    0x41  /* A */
   278    280   #define RTREE_LE    0x42  /* B */
   279    281   #define RTREE_LT    0x43  /* C */
   280    282   #define RTREE_GE    0x44  /* D */
................................................................................
   859    861   /*
   860    862   ** Free the RtreeCursor.aConstraint[] array and its contents.
   861    863   */
   862    864   static void freeCursorConstraints(RtreeCursor *pCsr){
   863    865     if( pCsr->aConstraint ){
   864    866       int i;                        /* Used to iterate through constraint array */
   865    867       for(i=0; i<pCsr->nConstraint; i++){
   866         -      sqlite3_rtree_query_info *pGeom = pCsr->aConstraint[i].pGeom;
   867         -      if( pGeom ){
   868         -        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
   869         -        sqlite3_free(pGeom);
          868  +      sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
          869  +      if( pInfo ){
          870  +        if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
          871  +        sqlite3_free(pInfo);
   870    872         }
   871    873       }
   872    874       sqlite3_free(pCsr->aConstraint);
   873    875       pCsr->aConstraint = 0;
   874    876     }
   875    877   }
   876    878   
................................................................................
   924    926     int eInt,                      /* True if RTree holding integer coordinates */
   925    927     u8 *pCellData,                 /* Raw cell content */
   926    928     RtreeSearchPoint *pSearch,     /* Container of this cell */
   927    929     sqlite3_rtree_dbl *prScore,    /* OUT: score for the cell */
   928    930     int *peWithin                  /* OUT: visibility of the cell */
   929    931   ){
   930    932     int i;                                                /* Loop counter */
   931         -  sqlite3_rtree_query_info *pGeom = pConstraint->pGeom; /* Callback info */
   932         -  int nCoord = pGeom->nCoord;                           /* No. of coordinates */
          933  +  sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
          934  +  int nCoord = pInfo->nCoord;                           /* No. of coordinates */
   933    935     int rc;                                             /* Callback return code */
   934    936     sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2];   /* Decoded coordinates */
   935    937   
   936    938     assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );
   937    939     assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );
   938    940   
   939    941     pCellData += 8;
   940    942     for(i=0; i<nCoord; i++, pCellData += 4){
   941    943       RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]);
   942    944     }
   943    945     if( pConstraint->op==RTREE_MATCH ){
   944         -    rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pGeom,
          946  +    rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
   945    947                                 nCoord, aCoord, &i);
   946    948       if( i==0 ) *peWithin = NOT_WITHIN;
          949  +    *prScore = RTREE_ZERO;
   947    950     }else{
   948         -    pGeom->aCoord = aCoord;
   949         -    pGeom->iLevel = pSearch->iLevel;
   950         -    pGeom->rScore = pGeom->rParentScore = pSearch->rScore;
   951         -    pGeom->eWithin = pGeom->eParentWithin = pSearch->eWithin;
   952         -    rc = pConstraint->u.xQueryFunc(pGeom);
   953         -    if( pGeom->eWithin<*peWithin ) *peWithin = pGeom->eWithin;
   954         -    if( pGeom->rScore<*prScore ) *prScore = pGeom->rScore;
          951  +    pInfo->aCoord = aCoord;
          952  +    pInfo->iLevel = pSearch->iLevel;
          953  +    pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
          954  +    pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
          955  +    rc = pConstraint->u.xQueryFunc(pInfo);
          956  +    if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
          957  +    if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
          958  +      *prScore = pInfo->rScore;
          959  +    }
   955    960     }
   956    961     return rc;
   957    962   }
   958    963   
   959    964   /* 
   960    965   ** Check the internal RTree node given by pCellData against constraint p.
   961    966   ** If this constraint cannot be satisfied by any child within the node,
................................................................................
  1061   1066     *piIndex = -1;
  1062   1067     return SQLITE_OK;
  1063   1068   }
  1064   1069   
  1065   1070   /*
  1066   1071   ** Compare two search points.  Return negative, zero, or positive if the first
  1067   1072   ** is less than, equal to, or greater than the second.
         1073  +**
         1074  +** The rScore is the primary key.  Smaller rScore values come first.
         1075  +** If the rScore is a tie, then use iLevel as the tie breaker with smaller
         1076  +** iLevel values coming first.  In this way, if rScore is the same for all
         1077  +** SearchPoints, then iLevel becomes the deciding factor and the result
         1078  +** is a depth-first search, which is the desired default behavior.
  1068   1079   */
  1069   1080   static int rtreeSearchPointCompare(
  1070   1081     const RtreeSearchPoint *pA,
  1071   1082     const RtreeSearchPoint *pB
  1072   1083   ){
  1073   1084     if( pA->rScore<pB->rScore ) return -1;
  1074   1085     if( pA->rScore>pB->rScore ) return +1;
................................................................................
  1285   1296     eInt = pRtree->eCoordType==RTREE_COORD_INT32;
  1286   1297     while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
  1287   1298       pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
  1288   1299       if( rc ) return rc;
  1289   1300       nCell = NCELL(pNode);
  1290   1301       assert( nCell<200 );
  1291   1302       while( p->iCell<nCell ){
  1292         -      sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)0;
         1303  +      sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
  1293   1304         u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
  1294   1305         eWithin = FULLY_WITHIN;
  1295   1306         for(ii=0; ii<nConstraint; ii++){
  1296   1307           RtreeConstraint *pConstraint = pCur->aConstraint + ii;
  1297   1308           if( pConstraint->op>=RTREE_MATCH ){
  1298   1309             rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
  1299   1310                                          &rScore, &eWithin);
................................................................................
  1315   1326           x.id = p->id;
  1316   1327           x.iCell = p->iCell - 1;
  1317   1328         }
  1318   1329         if( p->iCell>=nCell ){
  1319   1330           RTREE_QUEUE_TRACE(pCur, "POP-S:");
  1320   1331           rtreeSearchPointPop(pCur);
  1321   1332         }
         1333  +      if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
  1322   1334         p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
  1323   1335         if( p==0 ) return SQLITE_NOMEM;
  1324   1336         p->eWithin = eWithin;
  1325   1337         p->id = x.id;
  1326   1338         p->iCell = x.iCell;
  1327   1339         RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
  1328   1340         break;
................................................................................
  1425   1437   /*
  1426   1438   ** This function is called to configure the RtreeConstraint object passed
  1427   1439   ** as the second argument for a MATCH constraint. The value passed as the
  1428   1440   ** first argument to this function is the right-hand operand to the MATCH
  1429   1441   ** operator.
  1430   1442   */
  1431   1443   static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
  1432         -  RtreeMatchArg *p;
  1433         -  sqlite3_rtree_query_info *pGeom;
  1434         -  int nBlob;
         1444  +  RtreeMatchArg *pBlob;              /* BLOB returned by geometry function */
         1445  +  sqlite3_rtree_query_info *pInfo;   /* Callback information */
         1446  +  int nBlob;                         /* Size of the geometry function blob */
         1447  +  int nExpected;                     /* Expected size of the BLOB */
  1435   1448   
  1436   1449     /* Check that value is actually a blob. */
  1437   1450     if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
  1438   1451   
  1439   1452     /* Check that the blob is roughly the right size. */
  1440   1453     nBlob = sqlite3_value_bytes(pValue);
  1441   1454     if( nBlob<(int)sizeof(RtreeMatchArg) 
  1442   1455      || ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
  1443   1456     ){
  1444   1457       return SQLITE_ERROR;
  1445   1458     }
  1446   1459   
  1447         -  pGeom = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pGeom)+nBlob );
  1448         -  if( !pGeom ) return SQLITE_NOMEM;
  1449         -  memset(pGeom, 0, sizeof(*pGeom));
  1450         -  p = (RtreeMatchArg*)&pGeom[1];
         1460  +  pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob );
         1461  +  if( !pInfo ) return SQLITE_NOMEM;
         1462  +  memset(pInfo, 0, sizeof(*pInfo));
         1463  +  pBlob = (RtreeMatchArg*)&pInfo[1];
  1451   1464   
  1452         -  memcpy(p, sqlite3_value_blob(pValue), nBlob);
  1453         -  if( p->magic!=RTREE_GEOMETRY_MAGIC 
  1454         -   || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
  1455         -  ){
  1456         -    sqlite3_free(pGeom);
         1465  +  memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
         1466  +  nExpected = (int)(sizeof(RtreeMatchArg) +
         1467  +                    (pBlob->nParam-1)*sizeof(RtreeDValue));
         1468  +  if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){
         1469  +    sqlite3_free(pInfo);
  1457   1470       return SQLITE_ERROR;
  1458   1471     }
  1459         -  pGeom->pContext = p->cb.pContext;
  1460         -  pGeom->nParam = p->nParam;
  1461         -  pGeom->aParam = p->aParam;
         1472  +  pInfo->pContext = pBlob->cb.pContext;
         1473  +  pInfo->nParam = pBlob->nParam;
         1474  +  pInfo->aParam = pBlob->aParam;
  1462   1475   
  1463         -  pCons->u.xGeom = p->cb.xGeom;
  1464         -  pCons->pGeom = pGeom;
         1476  +  if( pBlob->cb.xGeom ){
         1477  +    pCons->u.xGeom = pBlob->cb.xGeom;
         1478  +  }else{
         1479  +    pCons->op = RTREE_QUERY;
         1480  +    pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
         1481  +  }
         1482  +  pCons->pInfo = pInfo;
  1465   1483     return SQLITE_OK;
  1466   1484   }
  1467   1485   
  1468   1486   /* 
  1469   1487   ** Rtree virtual table module xFilter method.
  1470   1488   */
  1471   1489   static int rtreeFilter(
................................................................................
  1489   1507       /* Special case - lookup by rowid. */
  1490   1508       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
  1491   1509       RtreeSearchPoint *p;     /* Search point for the the leaf */
  1492   1510       i64 iRowid = sqlite3_value_int64(argv[0]);
  1493   1511       i64 iNode = 0;
  1494   1512       rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
  1495   1513       if( rc==SQLITE_OK && pLeaf!=0 ){
  1496         -      p = rtreeSearchPointNew(pCsr, 0.0, 0);
         1514  +      p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
  1497   1515         assert( p!=0 );  /* Always returns pCsr->sPoint */
  1498   1516         pCsr->aNode[0] = pLeaf;
  1499   1517         p->id = iNode;
  1500   1518         p->eWithin = PARTLY_WITHIN;
  1501   1519         rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
  1502   1520         p->iCell = iCell;
  1503   1521         RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
................................................................................
  1517   1535           memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
  1518   1536           assert( (idxStr==0 && argc==0)
  1519   1537                   || (idxStr && (int)strlen(idxStr)==argc*2) );
  1520   1538           for(ii=0; ii<argc; ii++){
  1521   1539             RtreeConstraint *p = &pCsr->aConstraint[ii];
  1522   1540             p->op = idxStr[ii*2];
  1523   1541             p->iCoord = idxStr[ii*2+1]-'0';
  1524         -          if( p->op==RTREE_MATCH ){
         1542  +          if( p->op>=RTREE_MATCH ){
  1525   1543               /* A MATCH operator. The right-hand-side must be a blob that
  1526   1544               ** can be cast into an RtreeMatchArg object. One created using
  1527   1545               ** an sqlite3_rtree_geometry_callback() SQL user function.
  1528   1546               */
  1529   1547               rc = deserializeGeometry(argv[ii], p);
  1530   1548               if( rc!=SQLITE_OK ){
  1531   1549                 break;
  1532   1550               }
  1533         -            p->pGeom->nCoord = pRtree->nDim*2;
         1551  +            p->pInfo->nCoord = pRtree->nDim*2;
  1534   1552             }else{
  1535   1553   #ifdef SQLITE_RTREE_INT_ONLY
  1536   1554               p->u.rValue = sqlite3_value_int64(argv[ii]);
  1537   1555   #else
  1538   1556               p->u.rValue = sqlite3_value_double(argv[ii]);
  1539   1557   #endif
  1540   1558             }
................................................................................
  1542   1560         }
  1543   1561       }
  1544   1562     
  1545   1563       if( rc==SQLITE_OK ){
  1546   1564         rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  1547   1565       }
  1548   1566       if( rc==SQLITE_OK ){
  1549         -      RtreeSearchPoint *pNew = rtreeSearchPointNew(pCsr, 0.0, pRtree->iDepth+1);
         1567  +      RtreeSearchPoint *pNew;
         1568  +      pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1);
  1550   1569         if( pNew==0 ) return SQLITE_NOMEM;
  1551   1570         pNew->id = 1;
  1552   1571         pNew->iCell = 0;
  1553   1572         pNew->eWithin = PARTLY_WITHIN;
  1554   1573         assert( pCsr->bPoint==1 );
  1555   1574         pCsr->aNode[0] = pRoot;
  1556   1575         RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
................................................................................
  1755   1774   static RtreeDValue cellOverlap(
  1756   1775     Rtree *pRtree, 
  1757   1776     RtreeCell *p, 
  1758   1777     RtreeCell *aCell, 
  1759   1778     int nCell
  1760   1779   ){
  1761   1780     int ii;
  1762         -  RtreeDValue overlap = 0.0;
         1781  +  RtreeDValue overlap = RTREE_ZERO;
  1763   1782     for(ii=0; ii<nCell; ii++){
  1764   1783       int jj;
  1765   1784       RtreeDValue o = (RtreeDValue)1;
  1766   1785       for(jj=0; jj<(pRtree->nDim*2); jj+=2){
  1767   1786         RtreeDValue x1, x2;
  1768   1787         x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
  1769   1788         x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
................................................................................
  1795   1814     RtreeNode *pNode;
  1796   1815     rc = nodeAcquire(pRtree, 1, 0, &pNode);
  1797   1816   
  1798   1817     for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
  1799   1818       int iCell;
  1800   1819       sqlite3_int64 iBest = 0;
  1801   1820   
  1802         -    RtreeDValue fMinGrowth = 0.0;
  1803         -    RtreeDValue fMinArea = 0.0;
         1821  +    RtreeDValue fMinGrowth = RTREE_ZERO;
         1822  +    RtreeDValue fMinArea = RTREE_ZERO;
  1804   1823   
  1805   1824       int nCell = NCELL(pNode);
  1806   1825       RtreeCell cell;
  1807   1826       RtreeNode *pChild;
  1808   1827   
  1809   1828       RtreeCell *aCell = 0;
  1810   1829   
................................................................................
  2046   2065   ){
  2047   2066     int **aaSorted;
  2048   2067     int *aSpare;
  2049   2068     int ii;
  2050   2069   
  2051   2070     int iBestDim = 0;
  2052   2071     int iBestSplit = 0;
  2053         -  RtreeDValue fBestMargin = 0.0;
         2072  +  RtreeDValue fBestMargin = RTREE_ZERO;
  2054   2073   
  2055   2074     int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
  2056   2075   
  2057   2076     aaSorted = (int **)sqlite3_malloc(nByte);
  2058   2077     if( !aaSorted ){
  2059   2078       return SQLITE_NOMEM;
  2060   2079     }
................................................................................
  2067   2086       for(jj=0; jj<nCell; jj++){
  2068   2087         aaSorted[ii][jj] = jj;
  2069   2088       }
  2070   2089       SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
  2071   2090     }
  2072   2091   
  2073   2092     for(ii=0; ii<pRtree->nDim; ii++){
  2074         -    RtreeDValue margin = 0.0;
  2075         -    RtreeDValue fBestOverlap = 0.0;
  2076         -    RtreeDValue fBestArea = 0.0;
         2093  +    RtreeDValue margin = RTREE_ZERO;
         2094  +    RtreeDValue fBestOverlap = RTREE_ZERO;
         2095  +    RtreeDValue fBestArea = RTREE_ZERO;
  2077   2096       int iBestLeft = 0;
  2078   2097       int nLeft;
  2079   2098   
  2080   2099       for(
  2081   2100         nLeft=RTREE_MINCELLS(pRtree); 
  2082   2101         nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 
  2083   2102         nLeft++
................................................................................
  2488   2507       }
  2489   2508     }
  2490   2509     for(iDim=0; iDim<pRtree->nDim; iDim++){
  2491   2510       aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2));
  2492   2511     }
  2493   2512   
  2494   2513     for(ii=0; ii<nCell; ii++){
  2495         -    aDistance[ii] = 0.0;
         2514  +    aDistance[ii] = RTREE_ZERO;
  2496   2515       for(iDim=0; iDim<pRtree->nDim; iDim++){
  2497   2516         RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) - 
  2498   2517                                  DCOORD(aCell[ii].aCoord[iDim*2]));
  2499   2518         aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
  2500   2519       }
  2501   2520     }
  2502   2521   
................................................................................
  3295   3314   ** This routine deletes the RtreeGeomCallback object that was attached
  3296   3315   ** one of the SQL functions create by sqlite3_rtree_geometry_callback()
  3297   3316   ** or sqlite3_rtree_query_callback().  In other words, this routine is the
  3298   3317   ** destructor for an RtreeGeomCallback objecct.  This routine is called when
  3299   3318   ** the corresponding SQL function is deleted.
  3300   3319   */
  3301   3320   static void rtreeFreeCallback(void *p){
  3302         -  RtreeGeomCallback *pGeom = (RtreeGeomCallback*)p;
  3303         -  if( pGeom->xDestructor ) pGeom->xDestructor(pGeom->pContext);
         3321  +  RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
         3322  +  if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
  3304   3323     sqlite3_free(p);
  3305   3324   }
  3306   3325   
  3307   3326   /*
  3308   3327   ** Each call to sqlite3_rtree_geometry_callback() or
  3309   3328   ** sqlite3_rtree_query_callback() creates an ordinary SQLite
  3310   3329   ** scalar function that is implemented by this routine.

Added ext/rtree/rtreeE.test.

            1  +# 2010 August 28
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file contains tests for the r-tree module. Specifically, it tests
           12  +# that new-style custom r-tree queries (geometry callbacks) work.
           13  +# 
           14  +
           15  +if {![info exists testdir]} {
           16  +  set testdir [file join [file dirname [info script]] .. .. test]
           17  +} 
           18  +source $testdir/tester.tcl
           19  +ifcapable !rtree { finish_test ; return }
           20  +ifcapable rtree_int_only { finish_test; return }
           21  +
           22  +
           23  +#-------------------------------------------------------------------------
           24  +# Test the example 2d "circle" geometry callback.
           25  +#
           26  +register_circle_geom db
           27  +
           28  +do_execsql_test rtreeE-1.1 {
           29  +  PRAGMA page_size=512;
           30  +  CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
           31  +  
           32  +  /* A tight pattern of small boxes near 0,0 */
           33  +  WITH RECURSIVE
           34  +    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
           35  +    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
           36  +  INSERT INTO rt2 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;
           37  +
           38  +  /* A looser pattern of small boxes near 100, 0 */
           39  +  WITH RECURSIVE
           40  +    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
           41  +    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
           42  +  INSERT INTO rt2 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;
           43  +
           44  +  /* A looser pattern of larger boxes near 0, 200 */
           45  +  WITH RECURSIVE
           46  +    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
           47  +    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
           48  +  INSERT INTO rt2 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
           49  +} {}
           50  +
           51  +if 0 {
           52  +# Queries against each of the three clusters */
           53  +do_execsql_test rtreeE-1.1 {
           54  +  SELECT id FROM rt2 WHERE id MATCH Qcircle(0.0, 0.0, 50.0) ORDER BY id;
           55  +} {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
           56  +do_execsql_test rtreeE-1.2 {
           57  +  SELECT id FROM rt2 WHERE id MATCH Qcircle(100.0, 0.0, 50.0) ORDER BY id;
           58  +} {100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124}
           59  +do_execsql_test rtreeE-1.3 {
           60  +  SELECT id FROM rt2 WHERE id MATCH Qcircle(0.0, 200.0, 50.0) ORDER BY id;
           61  +} {200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224}
           62  +}
           63  +
           64  +# The Qcircle geometry function gives a lower score to larger leaf-nodes.
           65  +# This causes the 200s to sort before the 100s and the 0s to sort before
           66  +# last.
           67  +#
           68  +do_execsql_test rtreeE-1.4 {
           69  +  SELECT id FROM rt2 WHERE id MATCH Qcircle(0,0,1000) AND id%100==0
           70  +} {200 100 0}
           71  +
           72  +finish_test

Changes to src/test_rtree.c.

    31     31       double xmax;
    32     32       double ymin;
    33     33       double ymax;
    34     34     } aBox[2];
    35     35     double centerx;
    36     36     double centery;
    37     37     double radius;
           38  +  double mxArea;
    38     39   };
    39     40   
    40     41   /*
    41     42   ** Destructor function for Circle objects allocated by circle_geom().
    42     43   */
    43     44   static void circle_del(void *p){
    44     45     sqlite3_free(p);
................................................................................
    54     55     int *pRes
    55     56   ){
    56     57     int i;                          /* Iterator variable */
    57     58     Circle *pCircle;                /* Structure defining circular region */
    58     59     double xmin, xmax;              /* X dimensions of box being tested */
    59     60     double ymin, ymax;              /* X dimensions of box being tested */
    60     61   
    61         -  if( p->pUser==0 ){
           62  +  xmin = aCoord[0];
           63  +  xmax = aCoord[1];
           64  +  ymin = aCoord[2];
           65  +  ymax = aCoord[3];
           66  +  pCircle = (Circle *)p->pUser;
           67  +  if( pCircle==0 ){
    62     68       /* If pUser is still 0, then the parameter values have not been tested
    63     69       ** for correctness or stored into a Circle structure yet. Do this now. */
    64     70   
    65     71       /* This geometry callback is for use with a 2-dimensional r-tree table.
    66     72       ** Return an error if the table does not have exactly 2 dimensions. */
    67     73       if( nCoord!=4 ) return SQLITE_ERROR;
    68     74   
................................................................................
   100    106       pCircle->aBox[0].xmax = pCircle->centerx;
   101    107       pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
   102    108       pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
   103    109       pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
   104    110       pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
   105    111       pCircle->aBox[1].ymin = pCircle->centery;
   106    112       pCircle->aBox[1].ymax = pCircle->centery;
          113  +    pCircle->mxArea = (xmax - xmin)*(ymax - ymin) + 1.0;
   107    114     }
   108    115   
   109         -  pCircle = (Circle *)p->pUser;
   110         -  xmin = aCoord[0];
   111         -  xmax = aCoord[1];
   112         -  ymin = aCoord[2];
   113         -  ymax = aCoord[3];
   114         -
   115    116     /* Check if any of the 4 corners of the bounding-box being tested lie 
   116    117     ** inside the circular region. If they do, then the bounding-box does
   117    118     ** intersect the region of interest. Set the output variable to true and
   118    119     ** return SQLITE_OK in this case. */
   119    120     for(i=0; i<4; i++){
   120    121       double x = (i&0x01) ? xmax : xmin;
   121    122       double y = (i&0x02) ? ymax : ymin;
................................................................................
   157    158   static int circle_query_func(sqlite3_rtree_query_info *p){
   158    159     int i;                          /* Iterator variable */
   159    160     Circle *pCircle;                /* Structure defining circular region */
   160    161     double xmin, xmax;              /* X dimensions of box being tested */
   161    162     double ymin, ymax;              /* X dimensions of box being tested */
   162    163     int nWithin = 0;                /* Number of corners inside the circle */
   163    164   
   164         -  if( p->pUser==0 ){
          165  +  xmin = p->aCoord[0];
          166  +  xmax = p->aCoord[1];
          167  +  ymin = p->aCoord[2];
          168  +  ymax = p->aCoord[3];
          169  +  pCircle = (Circle *)p->pUser;
          170  +  if( pCircle==0 ){
   165    171       /* If pUser is still 0, then the parameter values have not been tested
   166    172       ** for correctness or stored into a Circle structure yet. Do this now. */
   167    173   
   168    174       /* This geometry callback is for use with a 2-dimensional r-tree table.
   169    175       ** Return an error if the table does not have exactly 2 dimensions. */
   170    176       if( p->nCoord!=4 ) return SQLITE_ERROR;
   171    177   
................................................................................
   203    209       pCircle->aBox[0].xmax = pCircle->centerx;
   204    210       pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
   205    211       pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
   206    212       pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
   207    213       pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
   208    214       pCircle->aBox[1].ymin = pCircle->centery;
   209    215       pCircle->aBox[1].ymax = pCircle->centery;
          216  +    pCircle->mxArea = 200.0*200.0;
   210    217     }
   211    218   
   212         -  pCircle = (Circle *)p->pUser;
   213         -  xmin = p->aCoord[0];
   214         -  xmax = p->aCoord[1];
   215         -  ymin = p->aCoord[2];
   216         -  ymax = p->aCoord[3];
   217         -
   218    219     /* Check if any of the 4 corners of the bounding-box being tested lie 
   219    220     ** inside the circular region. If they do, then the bounding-box does
   220    221     ** intersect the region of interest. Set the output variable to true and
   221    222     ** return SQLITE_OK in this case. */
   222    223     for(i=0; i<4; i++){
   223    224       double x = (i&0x01) ? xmax : xmin;
   224    225       double y = (i&0x02) ? ymax : ymin;
................................................................................
   242    243         ){
   243    244           nWithin = 1;
   244    245           break;
   245    246         }
   246    247       }
   247    248     }
   248    249   
   249         -  p->rScore = p->iLevel;
          250  +  if( p->iLevel==2 ){
          251  +    p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
          252  +    if( p->rScore<0.01 ) p->rScore = 0.01;
          253  +  }else{
          254  +    p->rScore = 0.0;
          255  +  }
   250    256     if( nWithin==0 ){
   251    257       p->eWithin = NOT_WITHIN;
   252    258     }else if( nWithin>=4 ){
   253    259       p->eWithin = FULLY_WITHIN;
   254    260     }else{
   255    261       p->eWithin = PARTLY_WITHIN;
   256    262     }