/ Check-in [53688a25]
Login

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

Overview
Comment:Initial attempt at getting R-Tree queries to work using a priority queue. This check-in compiles, but R-Trees do not work well. And there are debugging printf()s left in the code. This is an incremental check-in.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-queue
Files: files | file ages | folders
SHA1: 53688a25c23c394278a357829793889970aa4157
User & Date: drh 2014-04-15 21:06:14
Context
2014-04-16
13:00
Bug fixes to the priority-queue implementation for R-Trees. Improved tracing capability. Some queries work now, but still many problems. check-in: a439ddd6 user: drh tags: rtree-queue
2014-04-15
21:06
Initial attempt at getting R-Tree queries to work using a priority queue. This check-in compiles, but R-Trees do not work well. And there are debugging printf()s left in the code. This is an incremental check-in. check-in: 53688a25 user: drh tags: rtree-queue
2014-04-14
14:43
Fix comments on the rtreenode() and rtreedepth() test function in the R-Tree module. check-in: ade5b986 user: drh tags: rtree-enhancements
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

    59     59     SQLITE_EXTENSION_INIT1
    60     60   #else
    61     61     #include "sqlite3.h"
    62     62   #endif
    63     63   
    64     64   #include <string.h>
    65     65   #include <assert.h>
           66  +#include <stdio.h>
    66     67   
    67     68   #ifndef SQLITE_AMALGAMATION
    68     69   #include "sqlite3rtree.h"
    69     70   typedef sqlite3_int64 i64;
    70     71   typedef unsigned char u8;
    71     72   typedef unsigned short u16;
    72     73   typedef unsigned int u32;
................................................................................
    82     83   typedef struct RtreeCursor RtreeCursor;
    83     84   typedef struct RtreeNode RtreeNode;
    84     85   typedef struct RtreeCell RtreeCell;
    85     86   typedef struct RtreeConstraint RtreeConstraint;
    86     87   typedef struct RtreeMatchArg RtreeMatchArg;
    87     88   typedef struct RtreeGeomCallback RtreeGeomCallback;
    88     89   typedef union RtreeCoord RtreeCoord;
           90  +typedef struct RtreeSearchPoint RtreeSearchPoint;
    89     91   
    90     92   /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
    91     93   #define RTREE_MAX_DIMENSIONS 5
    92     94   
    93     95   /* Size of hash table Rtree.aHash. This hash table is not expected to
    94     96   ** ever contain very many entries, so a fixed number of buckets is 
    95     97   ** used.
................................................................................
   161    163     typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
   162    164     typedef int RtreeValue;                  /* Low accuracy coordinate */
   163    165   #else
   164    166     typedef double RtreeDValue;              /* High accuracy coordinate */
   165    167     typedef float RtreeValue;                /* Low accuracy coordinate */
   166    168   #endif
   167    169   
          170  +/*
          171  +** When doing a search of an r-tree, instances of the following structure
          172  +** record intermediate results from the tree walk.
          173  +**
          174  +** The id is always a node-id.  For iLevel>=1 the id is the node-id of
          175  +** the node that the RtreeSearchPoint represents.  When iLevel==0, however,
          176  +** the id is of the parent node and the cell that RtreeSearchPoint
          177  +** represents is the iCell-th entry in the parent node.
          178  +*/
          179  +struct RtreeSearchPoint {
          180  +  RtreeDValue rScore;    /* The score for this node.  Smallest goes first. */
          181  +  sqlite3_int64 id;      /* Node ID */
          182  +  u8 iLevel;             /* 0=entries.  1=leaf node.  2+ for higher */
          183  +  u8 eWithin;            /* PARTLY_WITHIN or FULLY_WITHIN */
          184  +  u8 iCell;              /* Cell index within the node */
          185  +};
          186  +
   168    187   /*
   169    188   ** The minimum number of cells allowed for a node is a third of the 
   170    189   ** maximum. In Gutman's notation:
   171    190   **
   172    191   **     m = M/3
   173    192   **
   174    193   ** If an R*-tree "Reinsert" operation is required, the same number of
................................................................................
   183    202   ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
   184    203   ** Therefore all non-root nodes must contain at least 3 entries. Since 
   185    204   ** 2^40 is greater than 2^64, an r-tree structure always has a depth of
   186    205   ** 40 or less.
   187    206   */
   188    207   #define RTREE_MAX_DEPTH 40
   189    208   
          209  +
          210  +/*
          211  +** Number of entries in the cursor RtreeNode cache.  The first entry is
          212  +** used to cache the RtreeNode for RtreeCursor.sPoint.  The remaining
          213  +** entries cache the RtreeNode for the first elements of the priority queue.
          214  +*/
          215  +#define RTREE_CACHE_SZ  5
          216  +
   190    217   /* 
   191    218   ** An rtree cursor object.
   192    219   */
   193    220   struct RtreeCursor {
   194    221     sqlite3_vtab_cursor base;         /* Base class.  Must be first */
   195         -  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
   196         -  int iCell;                        /* Index of current cell in pNode */
          222  +  u8 atEOF;                         /* True if at end of search */
          223  +  u8 bPoint;                        /* True if sPoint is valid */
   197    224     int iStrategy;                    /* Copy of idxNum search parameter */
   198    225     int nConstraint;                  /* Number of entries in aConstraint */
   199    226     RtreeConstraint *aConstraint;     /* Search constraints. */
          227  +  int nPointAlloc;                  /* Number of slots allocated for aPoint[] */
          228  +  int nPoint;                       /* Number of slots used in aPoint[] */
          229  +  RtreeSearchPoint *aPoint;         /* Priority queue for search points */
          230  +  RtreeSearchPoint sPoint;          /* Cached next search point */
          231  +  RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
   200    232   };
   201    233   
          234  +/* Return the Rtree of a RtreeCursor */
          235  +#define RTREE_OF_CURSOR(X)   ((Rtree*)((X)->base.pVtab))
          236  +
   202    237   /*
   203    238   ** A coordinate can be either a floating point number or a integer.  All
   204    239   ** coordinates within a single R-Tree are always of the same time.
   205    240   */
   206    241   union RtreeCoord {
   207    242     RtreeValue f;      /* Floating point value */
   208    243     int i;             /* Integer value */
................................................................................
   242    277   #define RTREE_EQ    0x41
   243    278   #define RTREE_LE    0x42
   244    279   #define RTREE_LT    0x43
   245    280   #define RTREE_GE    0x44
   246    281   #define RTREE_GT    0x45
   247    282   #define RTREE_MATCH 0x46  /* Old-style sqlite3_rtree_geometry_callback() */
   248    283   #define RTREE_QUERY 0x47  /* New-style sqlite3_rtree_query_callback() */
          284  +
   249    285   
   250    286   /* 
   251    287   ** An rtree structure node.
   252    288   */
   253    289   struct RtreeNode {
   254    290     RtreeNode *pParent;         /* Parent node */
   255    291     i64 iNode;                  /* The node number */
................................................................................
   834    870   }
   835    871   
   836    872   /* 
   837    873   ** Rtree virtual table module xClose method.
   838    874   */
   839    875   static int rtreeClose(sqlite3_vtab_cursor *cur){
   840    876     Rtree *pRtree = (Rtree *)(cur->pVtab);
   841         -  int rc;
          877  +  int ii;
   842    878     RtreeCursor *pCsr = (RtreeCursor *)cur;
   843    879     freeCursorConstraints(pCsr);
   844         -  rc = nodeRelease(pRtree, pCsr->pNode);
          880  +  sqlite3_free(pCsr->aPoint);
          881  +  for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
   845    882     sqlite3_free(pCsr);
   846         -  return rc;
          883  +  return SQLITE_OK;
   847    884   }
   848    885   
   849    886   /*
   850    887   ** Rtree virtual table module xEof method.
   851    888   **
   852    889   ** Return non-zero if the cursor does not currently point to a valid 
   853    890   ** record (i.e if the scan has finished), or zero otherwise.
   854    891   */
   855    892   static int rtreeEof(sqlite3_vtab_cursor *cur){
   856    893     RtreeCursor *pCsr = (RtreeCursor *)cur;
   857         -  return (pCsr->pNode==0);
          894  +  return pCsr->atEOF;
   858    895   }
   859    896   
   860    897   /*
   861    898   ** The r-tree constraint passed as the second argument to this function is
   862    899   ** guaranteed to be a MATCH constraint.
   863    900   */
   864         -static int testRtreeGeom(
          901  +static int rtreeTestGeom(
   865    902     Rtree *pRtree,                  /* R-Tree object */
   866    903     RtreeConstraint *pConstraint,   /* MATCH constraint to test */
   867    904     RtreeCell *pCell,               /* Cell to test */
   868    905     int *pbRes                      /* OUT: Test result */
   869    906   ){
   870    907     int i;
   871    908     RtreeDValue aCoord[RTREE_MAX_DIMENSIONS*2];
................................................................................
   879    916     }
   880    917     return pConstraint->u.xGeom((sqlite3_rtree_geometry*)pConstraint->pGeom,
   881    918                                 nCoord, aCoord, pbRes);
   882    919   }
   883    920   
   884    921   /* 
   885    922   ** Cursor pCursor currently points to a cell in a non-leaf page.
   886         -** Set *pbEof to true if the sub-tree headed by the cell is filtered
   887         -** (excluded) by the constraints in the pCursor->aConstraint[] 
   888         -** array, or false otherwise.
          923  +** Set *peWithin to NOT_WITHIN if the constraints in pCursor->aConstraint[]
          924  +** are guaranteed to never be satisfied by any subelement under the
          925  +** current cell.  If some subelement of the cell might satisfy all
          926  +** constraints, then set *peWithin to PARTLY_WITHIN.  If all subelements
          927  +** of the cell are guaranteed to fully satisfy all constraints, then
          928  +** set *peWithin to FULLY_WITHIN.
          929  +**
          930  +** In other words, set *peWithin to NOT_WITHIN, PARTLY_WITHIN, or
          931  +** FULLY_WITHIN if the cell is completely outside of the field-of-view,
          932  +** overlaps the field of view, or is completely contained within the
          933  +** field of view, respectively.
          934  +**
          935  +** It is not an error to set *peWithin to PARTLY_WITHIN when FULLY_WITHIN
          936  +** would be correct.  Doing so is suboptimal, but will still give the
          937  +** correct answer.  
   889    938   **
   890    939   ** Return SQLITE_OK if successful or an SQLite error code if an error
   891         -** occurs within a geometry callback.
          940  +** occurs.  Errors can only possible if there is a geometry callback.
   892    941   */
   893         -static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   894         -  RtreeCell cell;
          942  +static int rtreeTestCell(
          943  +  RtreeCursor *pCursor,      /* The cursor to check */
          944  +  RtreeCell *pCell,          /* The cell to check */
          945  +  int *peWithin              /* Set true if element is out-of-bounds */
          946  +){
   895    947     int ii;
   896         -  int bRes = 0;
          948  +  int bOutOfBounds = 0;
   897    949     int rc = SQLITE_OK;
          950  +  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);
   898    951   
   899         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   900         -  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
          952  +  for(ii=0; bOutOfBounds==0 && ii<pCursor->nConstraint; ii++){
   901    953       RtreeConstraint *p = &pCursor->aConstraint[ii];
   902         -    RtreeDValue cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
   903         -    RtreeDValue cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
          954  +    RtreeDValue cell_min = DCOORD(pCell->aCoord[(p->iCoord>>1)*2]);
          955  +    RtreeDValue cell_max = DCOORD(pCell->aCoord[(p->iCoord>>1)*2+1]);
   904    956   
   905    957       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   906    958           || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   907    959       );
   908    960   
   909    961       switch( p->op ){
   910    962         case RTREE_LE: case RTREE_LT: 
   911         -        bRes = p->u.rValue<cell_min; 
          963  +        bOutOfBounds = p->u.rValue<cell_min; 
   912    964           break;
   913    965   
   914    966         case RTREE_GE: case RTREE_GT: 
   915         -        bRes = p->u.rValue>cell_max; 
          967  +        bOutOfBounds = p->u.rValue>cell_max; 
   916    968           break;
   917    969   
   918    970         case RTREE_EQ:
   919         -        bRes = (p->u.rValue>cell_max || p->u.rValue<cell_min);
          971  +        bOutOfBounds = (p->u.rValue>cell_max || p->u.rValue<cell_min);
   920    972           break;
   921    973   
   922    974         default: {
   923    975           assert( p->op==RTREE_MATCH );
   924         -        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
   925         -        bRes = !bRes;
          976  +        rc = rtreeTestGeom(pRtree, p, pCell, &bOutOfBounds);
          977  +        bOutOfBounds = !bOutOfBounds;
   926    978           break;
   927    979         }
   928    980       }
   929    981     }
   930    982   
   931         -  *pbEof = bRes;
          983  +  *peWithin = bOutOfBounds ? NOT_WITHIN : PARTLY_WITHIN;
   932    984     return rc;
   933    985   }
   934    986   
   935    987   /* 
   936         -** Test if the cell that cursor pCursor currently points to
   937         -** would be filtered (excluded) by the constraints in the 
   938         -** pCursor->aConstraint[] array. If so, set *pbEof to true before
   939         -** returning. If the cell is not filtered (excluded) by the constraints,
   940         -** set pbEof to zero.
          988  +** pCursor points to a leaf r-tree entry which is a candidate for output.
          989  +** This routine sets *peWithin to one of NOT_WITHIN, PARTLY_WITHIN, or
          990  +** FULLY_WITHIN depending on whether or not the leaf entry is completely
          991  +** outside the region defined by pCursor->aConstraints[], or overlaps the
          992  +** region, or is completely within the region, respectively.
          993  +**
          994  +** This routine is more selective than rtreeTestCell().  rtreeTestCell()
          995  +** will return PARTLY_WITHIN or FULLY_WITHIN if the constraints are such
          996  +** that a subelement of the cell to be included in the result set.  This
          997  +** routine is is only called for leaf r-tree entries and does not need
          998  +** to concern itself with subelements.  Hence it only sets *peWithin to
          999  +** PARTLY_WITHIN or FULLY_WITHIN if the cell itself meets the requirements.
   941   1000   **
   942   1001   ** Return SQLITE_OK if successful or an SQLite error code if an error
   943   1002   ** occurs within a geometry callback.
   944   1003   **
   945   1004   ** This function assumes that the cell is part of a leaf node.
   946   1005   */
   947         -static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   948         -  RtreeCell cell;
         1006  +static int rtreeTestEntry(
         1007  +  RtreeCursor *pCursor,   /* Cursor pointing to the leaf element */
         1008  +  RtreeCell *pCell,       /* The cell to check */
         1009  +  int *peWithin           /* OUT: NOT_WITHIN, PARTLY_WITHIN, or FULLY_WITHIN */
         1010  +){
         1011  +  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);
   949   1012     int ii;
   950         -  *pbEof = 0;
         1013  +  int res = 1;     /* Innocent until proven guilty */
   951   1014   
   952         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   953         -  for(ii=0; ii<pCursor->nConstraint; ii++){
         1015  +  for(ii=0; res && ii<pCursor->nConstraint; ii++){
   954   1016       RtreeConstraint *p = &pCursor->aConstraint[ii];
   955         -    RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
   956         -    int res;
         1017  +    RtreeDValue coord = DCOORD(pCell->aCoord[p->iCoord]);
   957   1018       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   958   1019           || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   959   1020       );
   960   1021       switch( p->op ){
   961   1022         case RTREE_LE: res = (coord<=p->u.rValue); break;
   962   1023         case RTREE_LT: res = (coord<p->u.rValue);  break;
   963   1024         case RTREE_GE: res = (coord>=p->u.rValue); break;
   964   1025         case RTREE_GT: res = (coord>p->u.rValue);  break;
   965   1026         case RTREE_EQ: res = (coord==p->u.rValue); break;
   966   1027         default: {
   967   1028           int rc;
   968   1029           assert( p->op==RTREE_MATCH );
   969         -        rc = testRtreeGeom(pRtree, p, &cell, &res);
         1030  +        rc = rtreeTestGeom(pRtree, p, pCell, &res);
   970   1031           if( rc!=SQLITE_OK ){
   971   1032             return rc;
   972   1033           }
   973   1034           break;
   974   1035         }
   975   1036       }
   976         -
   977         -    if( !res ){
   978         -      *pbEof = 1;
   979         -      return SQLITE_OK;
   980         -    }
   981   1037     }
   982   1038   
         1039  +  *peWithin = res ? FULLY_WITHIN : NOT_WITHIN;
   983   1040     return SQLITE_OK;
   984   1041   }
   985   1042   
   986         -/*
   987         -** Cursor pCursor currently points at a node that heads a sub-tree of
   988         -** height iHeight (if iHeight==0, then the node is a leaf). Descend
   989         -** to point to the left-most cell of the sub-tree that matches the 
   990         -** configured constraints.
   991         -*/
   992         -static int descendToCell(
   993         -  Rtree *pRtree, 
   994         -  RtreeCursor *pCursor, 
   995         -  int iHeight,
   996         -  int *pEof                 /* OUT: Set to true if cannot descend */
   997         -){
   998         -  int isEof;
   999         -  int rc;
  1000         -  int ii;
  1001         -  RtreeNode *pChild;
  1002         -  sqlite3_int64 iRowid;
  1003         -
  1004         -  RtreeNode *pSavedNode = pCursor->pNode;
  1005         -  int iSavedCell = pCursor->iCell;
  1006         -
  1007         -  assert( iHeight>=0 );
  1008         -
  1009         -  if( iHeight==0 ){
  1010         -    rc = testRtreeEntry(pRtree, pCursor, &isEof);
  1011         -  }else{
  1012         -    rc = testRtreeCell(pRtree, pCursor, &isEof);
  1013         -  }
  1014         -  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
  1015         -    goto descend_to_cell_out;
  1016         -  }
  1017         -
  1018         -  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
  1019         -  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
  1020         -  if( rc!=SQLITE_OK ){
  1021         -    goto descend_to_cell_out;
  1022         -  }
  1023         -
  1024         -  nodeRelease(pRtree, pCursor->pNode);
  1025         -  pCursor->pNode = pChild;
  1026         -  isEof = 1;
  1027         -  for(ii=0; isEof && ii<NCELL(pChild); ii++){
  1028         -    pCursor->iCell = ii;
  1029         -    rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
  1030         -    if( rc!=SQLITE_OK ){
  1031         -      goto descend_to_cell_out;
  1032         -    }
  1033         -  }
  1034         -
  1035         -  if( isEof ){
  1036         -    assert( pCursor->pNode==pChild );
  1037         -    nodeReference(pSavedNode);
  1038         -    nodeRelease(pRtree, pChild);
  1039         -    pCursor->pNode = pSavedNode;
  1040         -    pCursor->iCell = iSavedCell;
  1041         -  }
  1042         -
  1043         -descend_to_cell_out:
  1044         -  *pEof = isEof;
  1045         -  return rc;
  1046         -}
  1047         -
  1048   1043   /*
  1049   1044   ** One of the cells in node pNode is guaranteed to have a 64-bit 
  1050   1045   ** integer value equal to iRowid. Return the index of this cell.
  1051   1046   */
  1052   1047   static int nodeRowidIndex(
  1053   1048     Rtree *pRtree, 
  1054   1049     RtreeNode *pNode, 
  1055   1050     i64 iRowid,
  1056   1051     int *piIndex
  1057   1052   ){
  1058   1053     int ii;
  1059   1054     int nCell = NCELL(pNode);
         1055  +  assert( nCell<200 );
  1060   1056     for(ii=0; ii<nCell; ii++){
  1061   1057       if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
  1062   1058         *piIndex = ii;
  1063   1059         return SQLITE_OK;
  1064   1060       }
  1065   1061     }
  1066   1062     return SQLITE_CORRUPT_VTAB;
................................................................................
  1074   1070     RtreeNode *pParent = pNode->pParent;
  1075   1071     if( pParent ){
  1076   1072       return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
  1077   1073     }
  1078   1074     *piIndex = -1;
  1079   1075     return SQLITE_OK;
  1080   1076   }
         1077  +
         1078  +/*
         1079  +** Compare two search points.  Return negative, zero, or positive if the first
         1080  +** is less than, equal to, or greater than the second.
         1081  +*/
         1082  +static int rtreeSearchPointCompare(
         1083  +  const RtreeSearchPoint *pA,
         1084  +  const RtreeSearchPoint *pB
         1085  +){
         1086  +  if( pA->rScore<pB->rScore ) return -1;
         1087  +  if( pA->rScore>pB->rScore ) return +1;
         1088  +  if( pA->iLevel<pB->iLevel ) return -1;
         1089  +  if( pA->iLevel>pB->iLevel ) return +1;
         1090  +  return 0;
         1091  +}
         1092  +
         1093  +/*
         1094  +** Interchange to search points in a cursor.
         1095  +*/
         1096  +static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
         1097  +  RtreeSearchPoint t = p->aPoint[i];
         1098  +  assert( i<j );
         1099  +  p->aPoint[i] = p->aPoint[j];
         1100  +  p->aPoint[j] = t;
         1101  +  if( i<RTREE_CACHE_SZ-1 ){
         1102  +    if( j>=RTREE_CACHE_SZ-1 ){
         1103  +      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i+1]);
         1104  +      p->aNode[i+1] = 0;
         1105  +    }else{
         1106  +      RtreeNode *pTemp = p->aNode[i+i];
         1107  +      p->aNode[i+1] = p->aNode[j+1];
         1108  +      p->aNode[j+1] = pTemp;
         1109  +    }
         1110  +  }
         1111  +}
         1112  +
         1113  +/*
         1114  +** Return the search point with the lowest current score.
         1115  +*/
         1116  +static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
         1117  +  return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
         1118  +}
         1119  +
         1120  +/*
         1121  +** Get the RtreeNode for the search point with the lowest score.
         1122  +*/
         1123  +static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
         1124  +  sqlite3_int64 id;
         1125  +  int ii = 1 - pCur->bPoint;
         1126  +  assert( ii==0 || ii==1 );
         1127  +  assert( pCur->bPoint || pCur->nPoint );
         1128  +  if( pCur->aNode[ii]==0 ){
         1129  +    assert( pRC!=0 );
         1130  +    id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
         1131  +    *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
         1132  +  }
         1133  +  return pCur->aNode[ii];
         1134  +}
         1135  +
         1136  +/*
         1137  +** Push a new element onto the priority queue
         1138  +*/
         1139  +static RtreeSearchPoint *rtreeEnqueue(
         1140  +  RtreeCursor *pCur,    /* The cursor */
         1141  +  RtreeDValue rScore,   /* Score for the new search point */
         1142  +  u8 iLevel             /* Level for the new search point */
         1143  +){
         1144  +  int i, j;
         1145  +  RtreeSearchPoint *pNew;
         1146  +  if( pCur->nPoint>=pCur->nPointAlloc ){
         1147  +    int nNew = pCur->nPointAlloc*2 + 8;
         1148  +    pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
         1149  +    if( pNew==0 ) return 0;
         1150  +    pCur->aPoint = pNew;
         1151  +    pCur->nPointAlloc = nNew;
         1152  +  }
         1153  +  i = pCur->nPoint++;
         1154  +  pNew = pCur->aPoint + i;
         1155  +  pNew->rScore = rScore;
         1156  +  pNew->iLevel = iLevel;  
         1157  +  while( i>0 ){
         1158  +    RtreeSearchPoint *pParent;
         1159  +    j = (i-1)/2;
         1160  +    pParent = pCur->aPoint + j;
         1161  +    if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
         1162  +    rtreeSearchPointSwap(pCur, j, i);
         1163  +    i = j;
         1164  +    pNew = pParent;
         1165  +  }
         1166  +  return pNew;
         1167  +}
         1168  +
         1169  +/*
         1170  +** Allocate a new RtreeSearchPoint and return a pointer to it.  Return
         1171  +** NULL if malloc fails.
         1172  +*/
         1173  +static RtreeSearchPoint *rtreeSearchPointNew(
         1174  +  RtreeCursor *pCur,    /* The cursor */
         1175  +  RtreeDValue rScore,   /* Score for the new search point */
         1176  +  u8 iLevel             /* Level for the new search point */
         1177  +){
         1178  +  RtreeSearchPoint *pNew, *pFirst;
         1179  +  pFirst = rtreeSearchPointFirst(pCur);
         1180  +  if( pFirst==0
         1181  +   || pFirst->rScore>rScore 
         1182  +   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
         1183  +  ){
         1184  +    if( pCur->bPoint ){
         1185  +      pNew = rtreeEnqueue(pCur, rScore, iLevel);
         1186  +      if( pNew==0 ) return 0;
         1187  +      assert( pCur->aNode[1]==0 );
         1188  +      pCur->aNode[1] = pCur->aNode[0];
         1189  +      pCur->aNode[0] = 0;
         1190  +      *pNew = pCur->sPoint;
         1191  +    }
         1192  +    pCur->sPoint.rScore = rScore;
         1193  +    pCur->sPoint.iLevel = iLevel;
         1194  +    pCur->bPoint = 1;
         1195  +    return &pCur->sPoint;
         1196  +  }else{
         1197  +    return rtreeEnqueue(pCur, rScore, iLevel);
         1198  +  }
         1199  +}
         1200  +
         1201  +static void traceTop(RtreeCursor *pCur, const char *zPrefix){
         1202  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCur);
         1203  +  if( p ){
         1204  +    printf("=== %6s id=%lld lvl=%d iCell=%d rScore=%g eWithin=%d\n",
         1205  +       zPrefix, p->id, p->iLevel, p->iCell, p->rScore, p->eWithin);
         1206  +  }
         1207  +}
         1208  +
         1209  +/* Remove the search point with the lowest current score.
         1210  +*/
         1211  +static void rtreeSearchPointPop(RtreeCursor *p){
         1212  +  int i, j, k, n;
         1213  +  i = p->bPoint;
         1214  +  assert( i==0 || i==1 );
         1215  +  if( p->aNode[i] ){
         1216  +    nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
         1217  +    p->aNode[i] = 0;
         1218  +  }
         1219  +  if( p->bPoint ){
         1220  +    p->bPoint = 0;
         1221  +  }else if( p->nPoint ){
         1222  +    n = --p->nPoint;
         1223  +    p->aPoint[0] = p->aPoint[n];
         1224  +    i = 0;
         1225  +    while( (j = i*2+1)<n ){
         1226  +      k = j+1;
         1227  +      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
         1228  +        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
         1229  +          rtreeSearchPointSwap(p, i, k);
         1230  +          i = k;
         1231  +        }else{
         1232  +          break;
         1233  +        }
         1234  +      }else{
         1235  +        if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
         1236  +          rtreeSearchPointSwap(p, i, j);
         1237  +          i = j;
         1238  +        }else{
         1239  +          break;
         1240  +        }
         1241  +      }
         1242  +    }
         1243  +  }
         1244  +}
         1245  +
         1246  +
         1247  +/*
         1248  +** Continue the search on cursor pCur until the front of the queue
         1249  +** contains an entry suitable for returning as a result-set row,
         1250  +** or until the RtreeSearchPoint queue is empty, indicating that the
         1251  +** query has completed.
         1252  +*/
         1253  +static int rtreeStepToLeaf(RtreeCursor *pCur){
         1254  +  RtreeSearchPoint *p;
         1255  +  RtreeSearchPoint *pNew;
         1256  +  Rtree *pRtree = RTREE_OF_CURSOR(pCur);
         1257  +  RtreeNode *pNode;
         1258  +  int eWithin;
         1259  +  int rc = SQLITE_OK;
         1260  +  int nCell;
         1261  +  RtreeCell cell;
         1262  +  RtreeSearchPoint x;
         1263  +
         1264  +  while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
         1265  +    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
         1266  +    if( rc ) return rc;
         1267  +    nCell = NCELL(pNode);
         1268  +    assert( nCell<200 );
         1269  +    while( p->iCell<nCell ){
         1270  +      nodeGetCell(pRtree, pNode, p->iCell, &cell);
         1271  +      if( p->iLevel==1 ){
         1272  +        rc = rtreeTestEntry(pCur, &cell, &eWithin);
         1273  +      }else{
         1274  +        rc = rtreeTestCell(pCur, &cell, &eWithin);
         1275  +      }
         1276  +      if( rc ) return rc;
         1277  +      x = *p;
         1278  +      p->iCell++;
         1279  +      if( p->iCell>=nCell ){
         1280  +traceTop(pCur, "POP:");
         1281  +        rtreeSearchPointPop(pCur);
         1282  +      }
         1283  +      if( eWithin==NOT_WITHIN ) continue;
         1284  +      pNew = rtreeSearchPointNew(pCur, /*rScore*/0.0, x.iLevel-1);
         1285  +      if( pNew==0 ) return SQLITE_NOMEM;
         1286  +      pNew->eWithin = eWithin;
         1287  +      if( pNew->iLevel ){
         1288  +        pNew->id = cell.iRowid;
         1289  +        pNew->iCell = 0;
         1290  +      }else{
         1291  +        pNew->id = x.id;
         1292  +        pNew->iCell = x.iCell;
         1293  +      }
         1294  +traceTop(pCur, "PUSH:");
         1295  +      break;
         1296  +    }
         1297  +  }
         1298  +  pCur->atEOF = p==0;
         1299  +  return SQLITE_OK;
         1300  +}
  1081   1301   
  1082   1302   /* 
  1083   1303   ** Rtree virtual table module xNext method.
  1084   1304   */
  1085   1305   static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  1086         -  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
  1087   1306     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1088   1307     int rc = SQLITE_OK;
  1089   1308   
  1090         -  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
  1091         -  ** already at EOF. It is against the rules to call the xNext() method of
  1092         -  ** a cursor that has already reached EOF.
  1093         -  */
  1094         -  assert( pCsr->pNode );
  1095         -
  1096         -  if( pCsr->iStrategy==1 ){
  1097         -    /* This "scan" is a direct lookup by rowid. There is no next entry. */
  1098         -    nodeRelease(pRtree, pCsr->pNode);
  1099         -    pCsr->pNode = 0;
  1100         -  }else{
  1101         -    /* Move to the next entry that matches the configured constraints. */
  1102         -    int iHeight = 0;
  1103         -    while( pCsr->pNode ){
  1104         -      RtreeNode *pNode = pCsr->pNode;
  1105         -      int nCell = NCELL(pNode);
  1106         -      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
  1107         -        int isEof;
  1108         -        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
  1109         -        if( rc!=SQLITE_OK || !isEof ){
  1110         -          return rc;
  1111         -        }
  1112         -      }
  1113         -      pCsr->pNode = pNode->pParent;
  1114         -      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
  1115         -      if( rc!=SQLITE_OK ){
  1116         -        return rc;
  1117         -      }
  1118         -      nodeReference(pCsr->pNode);
  1119         -      nodeRelease(pRtree, pNode);
  1120         -      iHeight++;
  1121         -    }
  1122         -  }
  1123         -
         1309  +  /* Move to the next entry that matches the configured constraints. */
         1310  +traceTop(pCsr, "POP:");
         1311  +  rtreeSearchPointPop(pCsr);
         1312  +  rtreeStepToLeaf(pCsr);
  1124   1313     return rc;
  1125   1314   }
  1126   1315   
  1127   1316   /* 
  1128   1317   ** Rtree virtual table module xRowid method.
  1129   1318   */
  1130   1319   static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
  1131         -  Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1132   1320     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1133         -
  1134         -  assert(pCsr->pNode);
  1135         -  *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1136         -
  1137         -  return SQLITE_OK;
         1321  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1322  +  int rc = SQLITE_OK;
         1323  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
         1324  +  if( rc==SQLITE_OK && p ){
         1325  +    *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
         1326  +  }
         1327  +  return rc;
  1138   1328   }
  1139   1329   
  1140   1330   /* 
  1141   1331   ** Rtree virtual table module xColumn method.
  1142   1332   */
  1143   1333   static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  1144   1334     Rtree *pRtree = (Rtree *)cur->pVtab;
  1145   1335     RtreeCursor *pCsr = (RtreeCursor *)cur;
         1336  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1337  +  RtreeCoord c;
         1338  +  int rc = SQLITE_OK;
         1339  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
  1146   1340   
         1341  +  if( rc ) return rc;
         1342  +  if( p==0 ) return SQLITE_OK;
  1147   1343     if( i==0 ){
  1148         -    i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1149         -    sqlite3_result_int64(ctx, iRowid);
         1344  +    sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
  1150   1345     }else{
  1151         -    RtreeCoord c;
  1152         -    nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
         1346  +    if( rc ) return rc;
         1347  +    nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
  1153   1348   #ifndef SQLITE_RTREE_INT_ONLY
  1154   1349       if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
  1155   1350         sqlite3_result_double(ctx, c.f);
  1156   1351       }else
  1157   1352   #endif
  1158   1353       {
  1159   1354         assert( pRtree->eCoordType==RTREE_COORD_INT32 );
  1160   1355         sqlite3_result_int(ctx, c.i);
  1161   1356       }
  1162   1357     }
  1163         -
  1164   1358     return SQLITE_OK;
  1165   1359   }
  1166   1360   
  1167   1361   /* 
  1168   1362   ** Use nodeAcquire() to obtain the leaf node containing the record with 
  1169   1363   ** rowid iRowid. If successful, set *ppLeaf to point to the node and
  1170   1364   ** return SQLITE_OK. If there is no such record in the table, set
  1171   1365   ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
  1172   1366   ** to zero and return an SQLite error code.
  1173   1367   */
  1174         -static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
         1368  +static int findLeafNode(
         1369  +  Rtree *pRtree,              /* RTree to search */
         1370  +  i64 iRowid,                 /* The rowid searching for */
         1371  +  RtreeNode **ppLeaf,         /* Write the node here */
         1372  +  sqlite3_int64 *piNode       /* Write the node-id here */
         1373  +){
  1175   1374     int rc;
  1176   1375     *ppLeaf = 0;
  1177   1376     sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
  1178   1377     if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
  1179   1378       i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
         1379  +    if( piNode ) *piNode = iNode;
  1180   1380       rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
  1181   1381       sqlite3_reset(pRtree->pReadRowid);
  1182   1382     }else{
  1183   1383       rc = sqlite3_reset(pRtree->pReadRowid);
  1184   1384     }
  1185   1385     return rc;
  1186   1386   }
................................................................................
  1235   1435   static int rtreeFilter(
  1236   1436     sqlite3_vtab_cursor *pVtabCursor, 
  1237   1437     int idxNum, const char *idxStr,
  1238   1438     int argc, sqlite3_value **argv
  1239   1439   ){
  1240   1440     Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1241   1441     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1242         -
  1243   1442     RtreeNode *pRoot = 0;
  1244   1443     int ii;
  1245   1444     int rc = SQLITE_OK;
         1445  +  int iCell = 0;
  1246   1446   
  1247   1447     rtreeReference(pRtree);
  1248   1448   
  1249   1449     freeCursorConstraints(pCsr);
  1250   1450     pCsr->iStrategy = idxNum;
  1251   1451   
  1252   1452     if( idxNum==1 ){
  1253   1453       /* Special case - lookup by rowid. */
  1254   1454       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
         1455  +    RtreeSearchPoint *p;     /* Search point for the the leaf */
  1255   1456       i64 iRowid = sqlite3_value_int64(argv[0]);
  1256         -    rc = findLeafNode(pRtree, iRowid, &pLeaf);
  1257         -    pCsr->pNode = pLeaf; 
  1258         -    if( pLeaf ){
  1259         -      assert( rc==SQLITE_OK );
  1260         -      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
  1261         -    }
         1457  +    p = rtreeSearchPointNew(pCsr, 0.0, 0);
         1458  +    if( p==0 ) return SQLITE_NOMEM;
         1459  +    rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
         1460  +    pCsr->aNode[0] = pLeaf;
         1461  +    p->eWithin = PARTLY_WITHIN;
         1462  +    if( rc ) rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
         1463  +    p->iCell = iCell;
         1464  +traceTop(pCsr, "PUSH:");
  1262   1465     }else{
  1263   1466       /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
  1264   1467       ** with the configured constraints. 
  1265   1468       */
  1266   1469       if( argc>0 ){
  1267   1470         pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
  1268   1471         pCsr->nConstraint = argc;
................................................................................
  1293   1496   #endif
  1294   1497             }
  1295   1498           }
  1296   1499         }
  1297   1500       }
  1298   1501     
  1299   1502       if( rc==SQLITE_OK ){
  1300         -      pCsr->pNode = 0;
  1301   1503         rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  1302   1504       }
  1303   1505       if( rc==SQLITE_OK ){
  1304         -      int isEof = 1;
  1305         -      int nCell = NCELL(pRoot);
  1306         -      pCsr->pNode = pRoot;
  1307         -      for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
  1308         -        assert( pCsr->pNode==pRoot );
  1309         -        rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
  1310         -        if( !isEof ){
  1311         -          break;
  1312         -        }
  1313         -      }
  1314         -      if( rc==SQLITE_OK && isEof ){
  1315         -        assert( pCsr->pNode==pRoot );
  1316         -        nodeRelease(pRtree, pRoot);
  1317         -        pCsr->pNode = 0;
  1318         -      }
  1319         -      assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
         1506  +      RtreeSearchPoint *pNew = rtreeSearchPointNew(pCsr, 0.0, pRtree->iDepth+1);
         1507  +      if( pNew==0 ) return SQLITE_NOMEM;
         1508  +      pNew->id = 1;
         1509  +      pNew->iCell = 0;
         1510  +      pNew->eWithin = PARTLY_WITHIN;
         1511  +      assert( pCsr->bPoint==1 );
         1512  +      pCsr->aNode[0] = pRoot;
         1513  +traceTop(pCsr, "PUSH:");
         1514  +      rc = rtreeStepToLeaf(pCsr);
  1320   1515       }
  1321   1516     }
  1322   1517   
  1323   1518     rtreeRelease(pRtree);
  1324   1519     return rc;
  1325   1520   }
  1326   1521   
................................................................................
  2391   2586     /* Obtain a reference to the root node to initialize Rtree.iDepth */
  2392   2587     rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  2393   2588   
  2394   2589     /* Obtain a reference to the leaf node that contains the entry 
  2395   2590     ** about to be deleted. 
  2396   2591     */
  2397   2592     if( rc==SQLITE_OK ){
  2398         -    rc = findLeafNode(pRtree, iDelete, &pLeaf);
         2593  +    rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
  2399   2594     }
  2400   2595   
  2401   2596     /* Delete the cell in question from the leaf node. */
  2402   2597     if( rc==SQLITE_OK ){
  2403   2598       int rc2;
  2404   2599       rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
  2405   2600       if( rc==SQLITE_OK ){