/ Check-in [3dca2809]
Login

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

Overview
Comment:Add the sqlite3_rtree_query_callback() API to the RTree virtual table.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sessions
Files: files | file ages | folders
SHA1: 3dca2809352c6c6d56db74447a814f77011c6220
User & Date: drh 2014-04-28 17:51:12
Context
2014-04-28
18:02
Merge all recent trunk enhancements and fixes into the sessions branch. check-in: e158812c user: drh tags: sessions
17:56
Add the sqlite3_rtree_query_callback() API to the RTree virtual table. (Cherrypick from the sessions branch.) check-in: af2cbe64 user: drh tags: trunk
17:51
Add the sqlite3_rtree_query_callback() API to the RTree virtual table. check-in: 3dca2809 user: drh tags: sessions
2014-04-25
16:29
Enhance the sqlite3_rtree_query_info object to report on the number of elements in the priority queue at each level. Closed-Leaf check-in: f7dad408 user: drh tags: rtree-enhancements
2014-04-18
01:10
Merge recent trunk changes into sessions. check-in: 95e77efe user: drh tags: sessions
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

    50     50   **      of 4-byte coordinates. For leaf nodes the integer is the rowid
    51     51   **      of a record. For internal nodes it is the node number of a
    52     52   **      child page.
    53     53   */
    54     54   
    55     55   #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
    56     56   
    57         -/*
    58         -** This file contains an implementation of a couple of different variants
    59         -** of the r-tree algorithm. See the README file for further details. The 
    60         -** same data-structure is used for all, but the algorithms for insert and
    61         -** delete operations vary. The variants used are selected at compile time 
    62         -** by defining the following symbols:
    63         -*/
    64         -
    65         -/* Either, both or none of the following may be set to activate 
    66         -** r*tree variant algorithms.
    67         -*/
    68         -#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
    69         -#define VARIANT_RSTARTREE_REINSERT      1
    70         -
    71         -/* 
    72         -** Exactly one of the following must be set to 1.
    73         -*/
    74         -#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
    75         -#define VARIANT_GUTTMAN_LINEAR_SPLIT    0
    76         -#define VARIANT_RSTARTREE_SPLIT         1
    77         -
    78         -#define VARIANT_GUTTMAN_SPLIT \
    79         -        (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
    80         -
    81         -#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
    82         -  #define PickNext QuadraticPickNext
    83         -  #define PickSeeds QuadraticPickSeeds
    84         -  #define AssignCells splitNodeGuttman
    85         -#endif
    86         -#if VARIANT_GUTTMAN_LINEAR_SPLIT
    87         -  #define PickNext LinearPickNext
    88         -  #define PickSeeds LinearPickSeeds
    89         -  #define AssignCells splitNodeGuttman
    90         -#endif
    91         -#if VARIANT_RSTARTREE_SPLIT
    92         -  #define AssignCells splitNodeStartree
    93         -#endif
    94         -
    95         -#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) 
    96         -# define NDEBUG 1
    97         -#endif
    98         -
    99     57   #ifndef SQLITE_CORE
   100     58     #include "sqlite3ext.h"
   101     59     SQLITE_EXTENSION_INIT1
   102     60   #else
   103     61     #include "sqlite3.h"
   104     62   #endif
   105     63   
   106     64   #include <string.h>
   107     65   #include <assert.h>
           66  +#include <stdio.h>
   108     67   
   109     68   #ifndef SQLITE_AMALGAMATION
   110     69   #include "sqlite3rtree.h"
   111     70   typedef sqlite3_int64 i64;
   112     71   typedef unsigned char u8;
           72  +typedef unsigned short u16;
   113     73   typedef unsigned int u32;
   114     74   #endif
   115     75   
   116     76   /*  The following macro is used to suppress compiler warnings.
   117     77   */
   118     78   #ifndef UNUSED_PARAMETER
   119     79   # define UNUSED_PARAMETER(x) (void)(x)
................................................................................
   123     83   typedef struct RtreeCursor RtreeCursor;
   124     84   typedef struct RtreeNode RtreeNode;
   125     85   typedef struct RtreeCell RtreeCell;
   126     86   typedef struct RtreeConstraint RtreeConstraint;
   127     87   typedef struct RtreeMatchArg RtreeMatchArg;
   128     88   typedef struct RtreeGeomCallback RtreeGeomCallback;
   129     89   typedef union RtreeCoord RtreeCoord;
           90  +typedef struct RtreeSearchPoint RtreeSearchPoint;
   130     91   
   131     92   /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
   132     93   #define RTREE_MAX_DIMENSIONS 5
   133     94   
   134     95   /* Size of hash table Rtree.aHash. This hash table is not expected to
   135     96   ** ever contain very many entries, so a fixed number of buckets is 
   136     97   ** used.
   137     98   */
   138         -#define HASHSIZE 128
           99  +#define HASHSIZE 97
   139    100   
   140    101   /* The xBestIndex method of this virtual table requires an estimate of
   141    102   ** the number of rows in the virtual table to calculate the costs of
   142    103   ** various strategies. If possible, this estimate is loaded from the
   143    104   ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
   144    105   ** Otherwise, if no sqlite_stat1 entry is available, use 
   145    106   ** RTREE_DEFAULT_ROWEST.
................................................................................
   147    108   #define RTREE_DEFAULT_ROWEST 1048576
   148    109   #define RTREE_MIN_ROWEST         100
   149    110   
   150    111   /* 
   151    112   ** An rtree virtual-table object.
   152    113   */
   153    114   struct Rtree {
   154         -  sqlite3_vtab base;
          115  +  sqlite3_vtab base;          /* Base class.  Must be first */
   155    116     sqlite3 *db;                /* Host database connection */
   156    117     int iNodeSize;              /* Size in bytes of each node in the node table */
   157         -  int nDim;                   /* Number of dimensions */
   158         -  int nBytesPerCell;          /* Bytes consumed per cell */
          118  +  u8 nDim;                    /* Number of dimensions */
          119  +  u8 eCoordType;              /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
          120  +  u8 nBytesPerCell;           /* Bytes consumed per cell */
   159    121     int iDepth;                 /* Current depth of the r-tree structure */
   160    122     char *zDb;                  /* Name of database containing r-tree table */
   161    123     char *zName;                /* Name of r-tree table */ 
   162         -  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
   163    124     int nBusy;                  /* Current number of users of this structure */
   164    125     i64 nRowEst;                /* Estimated number of rows in this table */
   165    126   
   166    127     /* List of nodes removed during a CondenseTree operation. List is
   167    128     ** linked together via the pointer normally used for hash chains -
   168    129     ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 
   169    130     ** headed by the node (leaf nodes have RtreeNode.iNode==0).
................................................................................
   182    143     sqlite3_stmt *pDeleteRowid;
   183    144   
   184    145     /* Statements to read/write/delete a record from xxx_parent */
   185    146     sqlite3_stmt *pReadParent;
   186    147     sqlite3_stmt *pWriteParent;
   187    148     sqlite3_stmt *pDeleteParent;
   188    149   
   189         -  int eCoordType;
          150  +  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
   190    151   };
   191    152   
   192         -/* Possible values for eCoordType: */
          153  +/* Possible values for Rtree.eCoordType: */
   193    154   #define RTREE_COORD_REAL32 0
   194    155   #define RTREE_COORD_INT32  1
   195    156   
   196    157   /*
   197    158   ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will
   198    159   ** only deal with integer coordinates.  No floating point operations
   199    160   ** will be done.
   200    161   */
   201    162   #ifdef SQLITE_RTREE_INT_ONLY
   202    163     typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
   203    164     typedef int RtreeValue;                  /* Low accuracy coordinate */
          165  +# define RTREE_ZERO 0
   204    166   #else
   205    167     typedef double RtreeDValue;              /* High accuracy coordinate */
   206    168     typedef float RtreeValue;                /* Low accuracy coordinate */
          169  +# define RTREE_ZERO 0.0
   207    170   #endif
          171  +
          172  +/*
          173  +** When doing a search of an r-tree, instances of the following structure
          174  +** record intermediate results from the tree walk.
          175  +**
          176  +** The id is always a node-id.  For iLevel>=1 the id is the node-id of
          177  +** the node that the RtreeSearchPoint represents.  When iLevel==0, however,
          178  +** the id is of the parent node and the cell that RtreeSearchPoint
          179  +** represents is the iCell-th entry in the parent node.
          180  +*/
          181  +struct RtreeSearchPoint {
          182  +  RtreeDValue rScore;    /* The score for this node.  Smallest goes first. */
          183  +  sqlite3_int64 id;      /* Node ID */
          184  +  u8 iLevel;             /* 0=entries.  1=leaf node.  2+ for higher */
          185  +  u8 eWithin;            /* PARTLY_WITHIN or FULLY_WITHIN */
          186  +  u8 iCell;              /* Cell index within the node */
          187  +};
   208    188   
   209    189   /*
   210    190   ** The minimum number of cells allowed for a node is a third of the 
   211    191   ** maximum. In Gutman's notation:
   212    192   **
   213    193   **     m = M/3
   214    194   **
................................................................................
   224    204   ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
   225    205   ** Therefore all non-root nodes must contain at least 3 entries. Since 
   226    206   ** 2^40 is greater than 2^64, an r-tree structure always has a depth of
   227    207   ** 40 or less.
   228    208   */
   229    209   #define RTREE_MAX_DEPTH 40
   230    210   
          211  +
          212  +/*
          213  +** Number of entries in the cursor RtreeNode cache.  The first entry is
          214  +** used to cache the RtreeNode for RtreeCursor.sPoint.  The remaining
          215  +** entries cache the RtreeNode for the first elements of the priority queue.
          216  +*/
          217  +#define RTREE_CACHE_SZ  5
          218  +
   231    219   /* 
   232    220   ** An rtree cursor object.
   233    221   */
   234    222   struct RtreeCursor {
   235         -  sqlite3_vtab_cursor base;
   236         -  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
   237         -  int iCell;                        /* Index of current cell in pNode */
          223  +  sqlite3_vtab_cursor base;         /* Base class.  Must be first */
          224  +  u8 atEOF;                         /* True if at end of search */
          225  +  u8 bPoint;                        /* True if sPoint is valid */
   238    226     int iStrategy;                    /* Copy of idxNum search parameter */
   239    227     int nConstraint;                  /* Number of entries in aConstraint */
   240    228     RtreeConstraint *aConstraint;     /* Search constraints. */
          229  +  int nPointAlloc;                  /* Number of slots allocated for aPoint[] */
          230  +  int nPoint;                       /* Number of slots used in aPoint[] */
          231  +  int mxLevel;                      /* iLevel value for root of the tree */
          232  +  RtreeSearchPoint *aPoint;         /* Priority queue for search points */
          233  +  RtreeSearchPoint sPoint;          /* Cached next search point */
          234  +  RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
          235  +  u32 anQueue[RTREE_MAX_DEPTH+1];   /* Number of queued entries by iLevel */
   241    236   };
   242    237   
          238  +/* Return the Rtree of a RtreeCursor */
          239  +#define RTREE_OF_CURSOR(X)   ((Rtree*)((X)->base.pVtab))
          240  +
          241  +/*
          242  +** A coordinate can be either a floating point number or a integer.  All
          243  +** coordinates within a single R-Tree are always of the same time.
          244  +*/
   243    245   union RtreeCoord {
   244         -  RtreeValue f;
   245         -  int i;
          246  +  RtreeValue f;      /* Floating point value */
          247  +  int i;             /* Integer value */
          248  +  u32 u;             /* Unsigned for byte-order conversions */
   246    249   };
   247    250   
   248    251   /*
   249    252   ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
   250    253   ** formatted as a RtreeDValue (double or int64). This macro assumes that local
   251    254   ** variable pRtree points to the Rtree structure associated with the
   252    255   ** RtreeCoord.
................................................................................
   263    266   
   264    267   /*
   265    268   ** A search constraint.
   266    269   */
   267    270   struct RtreeConstraint {
   268    271     int iCoord;                     /* Index of constrained coordinate */
   269    272     int op;                         /* Constraining operation */
   270         -  RtreeDValue rValue;             /* Constraint value. */
   271         -  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
   272         -  sqlite3_rtree_geometry *pGeom;  /* Constraint callback argument for a MATCH */
          273  +  union {
          274  +    RtreeDValue rValue;             /* Constraint value. */
          275  +    int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
          276  +    int (*xQueryFunc)(sqlite3_rtree_query_info*);
          277  +  } u;
          278  +  sqlite3_rtree_query_info *pInfo;  /* xGeom and xQueryFunc argument */
   273    279   };
   274    280   
   275    281   /* Possible values for RtreeConstraint.op */
   276         -#define RTREE_EQ    0x41
   277         -#define RTREE_LE    0x42
   278         -#define RTREE_LT    0x43
   279         -#define RTREE_GE    0x44
   280         -#define RTREE_GT    0x45
   281         -#define RTREE_MATCH 0x46
          282  +#define RTREE_EQ    0x41  /* A */
          283  +#define RTREE_LE    0x42  /* B */
          284  +#define RTREE_LT    0x43  /* C */
          285  +#define RTREE_GE    0x44  /* D */
          286  +#define RTREE_GT    0x45  /* E */
          287  +#define RTREE_MATCH 0x46  /* F: Old-style sqlite3_rtree_geometry_callback() */
          288  +#define RTREE_QUERY 0x47  /* G: New-style sqlite3_rtree_query_callback() */
          289  +
   282    290   
   283    291   /* 
   284    292   ** An rtree structure node.
   285    293   */
   286    294   struct RtreeNode {
   287         -  RtreeNode *pParent;               /* Parent node */
   288         -  i64 iNode;
   289         -  int nRef;
   290         -  int isDirty;
   291         -  u8 *zData;
   292         -  RtreeNode *pNext;                 /* Next node in this hash chain */
          295  +  RtreeNode *pParent;         /* Parent node */
          296  +  i64 iNode;                  /* The node number */
          297  +  int nRef;                   /* Number of references to this node */
          298  +  int isDirty;                /* True if the node needs to be written to disk */
          299  +  u8 *zData;                  /* Content of the node, as should be on disk */
          300  +  RtreeNode *pNext;           /* Next node in this hash collision chain */
   293    301   };
          302  +
          303  +/* Return the number of cells in a node  */
   294    304   #define NCELL(pNode) readInt16(&(pNode)->zData[2])
   295    305   
   296    306   /* 
   297         -** Structure to store a deserialized rtree record.
          307  +** A single cell from a node, deserialized
   298    308   */
   299    309   struct RtreeCell {
   300         -  i64 iRowid;
   301         -  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
          310  +  i64 iRowid;                                 /* Node or entry ID */
          311  +  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];  /* Bounding box coordinates */
          312  +};
          313  +
          314  +
          315  +/*
          316  +** This object becomes the sqlite3_user_data() for the SQL functions
          317  +** that are created by sqlite3_rtree_geometry_callback() and
          318  +** sqlite3_rtree_query_callback() and which appear on the right of MATCH
          319  +** operators in order to constrain a search.
          320  +**
          321  +** xGeom and xQueryFunc are the callback functions.  Exactly one of 
          322  +** xGeom and xQueryFunc fields is non-NULL, depending on whether the
          323  +** SQL function was created using sqlite3_rtree_geometry_callback() or
          324  +** sqlite3_rtree_query_callback().
          325  +** 
          326  +** This object is deleted automatically by the destructor mechanism in
          327  +** sqlite3_create_function_v2().
          328  +*/
          329  +struct RtreeGeomCallback {
          330  +  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
          331  +  int (*xQueryFunc)(sqlite3_rtree_query_info*);
          332  +  void (*xDestructor)(void*);
          333  +  void *pContext;
   302    334   };
   303    335   
   304    336   
   305    337   /*
   306    338   ** Value for the first field of every RtreeMatchArg object. The MATCH
   307    339   ** operator tests that the first field of a blob operand matches this
   308    340   ** value to avoid operating on invalid blobs (which could cause a segfault).
   309    341   */
   310    342   #define RTREE_GEOMETRY_MAGIC 0x891245AB
   311    343   
   312    344   /*
   313         -** An instance of this structure must be supplied as a blob argument to
   314         -** the right-hand-side of an SQL MATCH operator used to constrain an
   315         -** r-tree query.
          345  +** An instance of this structure (in the form of a BLOB) is returned by
          346  +** the SQL functions that sqlite3_rtree_geometry_callback() and
          347  +** sqlite3_rtree_query_callback() create, and is read as the right-hand
          348  +** operand to the MATCH operator of an R-Tree.
   316    349   */
   317    350   struct RtreeMatchArg {
   318         -  u32 magic;                      /* Always RTREE_GEOMETRY_MAGIC */
   319         -  int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue*, int *);
   320         -  void *pContext;
   321         -  int nParam;
   322         -  RtreeDValue aParam[1];
   323         -};
   324         -
   325         -/*
   326         -** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
   327         -** a single instance of the following structure is allocated. It is used
   328         -** as the context for the user-function created by by s_r_g_c(). The object
   329         -** is eventually deleted by the destructor mechanism provided by
   330         -** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
   331         -** the geometry callback function).
   332         -*/
   333         -struct RtreeGeomCallback {
   334         -  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
   335         -  void *pContext;
          351  +  u32 magic;                  /* Always RTREE_GEOMETRY_MAGIC */
          352  +  RtreeGeomCallback cb;       /* Info about the callback functions */
          353  +  int nParam;                 /* Number of parameters to the SQL function */
          354  +  RtreeDValue aParam[1];      /* Values for parameters to the SQL function */
   336    355   };
   337    356   
   338    357   #ifndef MAX
   339    358   # define MAX(x,y) ((x) < (y) ? (y) : (x))
   340    359   #endif
   341    360   #ifndef MIN
   342    361   # define MIN(x,y) ((x) > (y) ? (y) : (x))
................................................................................
   422    441   }
   423    442   
   424    443   /*
   425    444   ** Given a node number iNode, return the corresponding key to use
   426    445   ** in the Rtree.aHash table.
   427    446   */
   428    447   static int nodeHash(i64 iNode){
   429         -  return (
   430         -    (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 
   431         -    (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
   432         -  ) % HASHSIZE;
          448  +  return iNode % HASHSIZE;
   433    449   }
   434    450   
   435    451   /*
   436    452   ** Search the node hash table for node iNode. If found, return a pointer
   437    453   ** to it. Otherwise, return 0.
   438    454   */
   439    455   static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
................................................................................
   485    501     }
   486    502     return pNode;
   487    503   }
   488    504   
   489    505   /*
   490    506   ** Obtain a reference to an r-tree node.
   491    507   */
   492         -static int
   493         -nodeAcquire(
          508  +static int nodeAcquire(
   494    509     Rtree *pRtree,             /* R-tree structure */
   495    510     i64 iNode,                 /* Node number to load */
   496    511     RtreeNode *pParent,        /* Either the parent node or NULL */
   497    512     RtreeNode **ppNode         /* OUT: Acquired node */
   498    513   ){
   499    514     int rc;
   500    515     int rc2 = SQLITE_OK;
................................................................................
   575    590     return rc;
   576    591   }
   577    592   
   578    593   /*
   579    594   ** Overwrite cell iCell of node pNode with the contents of pCell.
   580    595   */
   581    596   static void nodeOverwriteCell(
   582         -  Rtree *pRtree, 
   583         -  RtreeNode *pNode,  
   584         -  RtreeCell *pCell, 
   585         -  int iCell
          597  +  Rtree *pRtree,             /* The overall R-Tree */
          598  +  RtreeNode *pNode,          /* The node into which the cell is to be written */
          599  +  RtreeCell *pCell,          /* The cell to write */
          600  +  int iCell                  /* Index into pNode into which pCell is written */
   586    601   ){
   587    602     int ii;
   588    603     u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
   589    604     p += writeInt64(p, pCell->iRowid);
   590    605     for(ii=0; ii<(pRtree->nDim*2); ii++){
   591    606       p += writeCoord(p, &pCell->aCoord[ii]);
   592    607     }
   593    608     pNode->isDirty = 1;
   594    609   }
   595    610   
   596    611   /*
   597         -** Remove cell the cell with index iCell from node pNode.
          612  +** Remove the cell with index iCell from node pNode.
   598    613   */
   599    614   static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
   600    615     u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
   601    616     u8 *pSrc = &pDst[pRtree->nBytesPerCell];
   602    617     int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
   603    618     memmove(pDst, pSrc, nByte);
   604    619     writeInt16(&pNode->zData[2], NCELL(pNode)-1);
................................................................................
   607    622   
   608    623   /*
   609    624   ** Insert the contents of cell pCell into node pNode. If the insert
   610    625   ** is successful, return SQLITE_OK.
   611    626   **
   612    627   ** If there is not enough free space in pNode, return SQLITE_FULL.
   613    628   */
   614         -static int
   615         -nodeInsertCell(
   616         -  Rtree *pRtree, 
   617         -  RtreeNode *pNode, 
   618         -  RtreeCell *pCell 
          629  +static int nodeInsertCell(
          630  +  Rtree *pRtree,                /* The overall R-Tree */
          631  +  RtreeNode *pNode,             /* Write new cell into this node */
          632  +  RtreeCell *pCell              /* The cell to be inserted */
   619    633   ){
   620    634     int nCell;                    /* Current number of cells in pNode */
   621    635     int nMaxCell;                 /* Maximum number of cells for pNode */
   622    636   
   623    637     nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
   624    638     nCell = NCELL(pNode);
   625    639   
................................................................................
   632    646   
   633    647     return (nCell==nMaxCell);
   634    648   }
   635    649   
   636    650   /*
   637    651   ** If the node is dirty, write it out to the database.
   638    652   */
   639         -static int
   640         -nodeWrite(Rtree *pRtree, RtreeNode *pNode){
          653  +static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){
   641    654     int rc = SQLITE_OK;
   642    655     if( pNode->isDirty ){
   643    656       sqlite3_stmt *p = pRtree->pWriteNode;
   644    657       if( pNode->iNode ){
   645    658         sqlite3_bind_int64(p, 1, pNode->iNode);
   646    659       }else{
   647    660         sqlite3_bind_null(p, 1);
................................................................................
   658    671     return rc;
   659    672   }
   660    673   
   661    674   /*
   662    675   ** Release a reference to a node. If the node is dirty and the reference
   663    676   ** count drops to zero, the node data is written to the database.
   664    677   */
   665         -static int
   666         -nodeRelease(Rtree *pRtree, RtreeNode *pNode){
          678  +static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
   667    679     int rc = SQLITE_OK;
   668    680     if( pNode ){
   669    681       assert( pNode->nRef>0 );
   670    682       pNode->nRef--;
   671    683       if( pNode->nRef==0 ){
   672    684         if( pNode->iNode==1 ){
   673    685           pRtree->iDepth = -1;
................................................................................
   687    699   
   688    700   /*
   689    701   ** Return the 64-bit integer value associated with cell iCell of
   690    702   ** node pNode. If pNode is a leaf node, this is a rowid. If it is
   691    703   ** an internal node, then the 64-bit integer is a child page number.
   692    704   */
   693    705   static i64 nodeGetRowid(
   694         -  Rtree *pRtree, 
   695         -  RtreeNode *pNode, 
   696         -  int iCell
          706  +  Rtree *pRtree,       /* The overall R-Tree */
          707  +  RtreeNode *pNode,    /* The node from which to extract the ID */
          708  +  int iCell            /* The cell index from which to extract the ID */
   697    709   ){
   698    710     assert( iCell<NCELL(pNode) );
   699    711     return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
   700    712   }
   701    713   
   702    714   /*
   703    715   ** Return coordinate iCoord from cell iCell in node pNode.
   704    716   */
   705    717   static void nodeGetCoord(
   706         -  Rtree *pRtree, 
   707         -  RtreeNode *pNode, 
   708         -  int iCell,
   709         -  int iCoord,
   710         -  RtreeCoord *pCoord           /* Space to write result to */
          718  +  Rtree *pRtree,               /* The overall R-Tree */
          719  +  RtreeNode *pNode,            /* The node from which to extract a coordinate */
          720  +  int iCell,                   /* The index of the cell within the node */
          721  +  int iCoord,                  /* Which coordinate to extract */
          722  +  RtreeCoord *pCoord           /* OUT: Space to write result to */
   711    723   ){
   712    724     readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
   713    725   }
   714    726   
   715    727   /*
   716    728   ** Deserialize cell iCell of node pNode. Populate the structure pointed
   717    729   ** to by pCell with the results.
   718    730   */
   719    731   static void nodeGetCell(
   720         -  Rtree *pRtree, 
   721         -  RtreeNode *pNode, 
   722         -  int iCell,
   723         -  RtreeCell *pCell
          732  +  Rtree *pRtree,               /* The overall R-Tree */
          733  +  RtreeNode *pNode,            /* The node containing the cell to be read */
          734  +  int iCell,                   /* Index of the cell within the node */
          735  +  RtreeCell *pCell             /* OUT: Write the cell contents here */
   724    736   ){
   725         -  int ii;
          737  +  u8 *pData;
          738  +  u8 *pEnd;
          739  +  RtreeCoord *pCoord;
   726    740     pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
   727         -  for(ii=0; ii<pRtree->nDim*2; ii++){
   728         -    nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
          741  +  pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
          742  +  pEnd = pData + pRtree->nDim*8;
          743  +  pCoord = pCell->aCoord;
          744  +  for(; pData<pEnd; pData+=4, pCoord++){
          745  +    readCoord(pData, pCoord);
   729    746     }
   730    747   }
   731    748   
   732    749   
   733    750   /* Forward declaration for the function that does the work of
   734    751   ** the virtual table module xCreate() and xConnect() methods.
   735    752   */
................................................................................
   847    864   /*
   848    865   ** Free the RtreeCursor.aConstraint[] array and its contents.
   849    866   */
   850    867   static void freeCursorConstraints(RtreeCursor *pCsr){
   851    868     if( pCsr->aConstraint ){
   852    869       int i;                        /* Used to iterate through constraint array */
   853    870       for(i=0; i<pCsr->nConstraint; i++){
   854         -      sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
   855         -      if( pGeom ){
   856         -        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
   857         -        sqlite3_free(pGeom);
          871  +      sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
          872  +      if( pInfo ){
          873  +        if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
          874  +        sqlite3_free(pInfo);
   858    875         }
   859    876       }
   860    877       sqlite3_free(pCsr->aConstraint);
   861    878       pCsr->aConstraint = 0;
   862    879     }
   863    880   }
   864    881   
   865    882   /* 
   866    883   ** Rtree virtual table module xClose method.
   867    884   */
   868    885   static int rtreeClose(sqlite3_vtab_cursor *cur){
   869    886     Rtree *pRtree = (Rtree *)(cur->pVtab);
   870         -  int rc;
          887  +  int ii;
   871    888     RtreeCursor *pCsr = (RtreeCursor *)cur;
   872    889     freeCursorConstraints(pCsr);
   873         -  rc = nodeRelease(pRtree, pCsr->pNode);
          890  +  sqlite3_free(pCsr->aPoint);
          891  +  for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
   874    892     sqlite3_free(pCsr);
   875         -  return rc;
          893  +  return SQLITE_OK;
   876    894   }
   877    895   
   878    896   /*
   879    897   ** Rtree virtual table module xEof method.
   880    898   **
   881    899   ** Return non-zero if the cursor does not currently point to a valid 
   882    900   ** record (i.e if the scan has finished), or zero otherwise.
   883    901   */
   884    902   static int rtreeEof(sqlite3_vtab_cursor *cur){
   885    903     RtreeCursor *pCsr = (RtreeCursor *)cur;
   886         -  return (pCsr->pNode==0);
   887         -}
   888         -
   889         -/*
   890         -** The r-tree constraint passed as the second argument to this function is
   891         -** guaranteed to be a MATCH constraint.
   892         -*/
   893         -static int testRtreeGeom(
   894         -  Rtree *pRtree,                  /* R-Tree object */
   895         -  RtreeConstraint *pConstraint,   /* MATCH constraint to test */
   896         -  RtreeCell *pCell,               /* Cell to test */
   897         -  int *pbRes                      /* OUT: Test result */
   898         -){
   899         -  int i;
   900         -  RtreeDValue aCoord[RTREE_MAX_DIMENSIONS*2];
   901         -  int nCoord = pRtree->nDim*2;
   902         -
   903         -  assert( pConstraint->op==RTREE_MATCH );
   904         -  assert( pConstraint->pGeom );
   905         -
   906         -  for(i=0; i<nCoord; i++){
   907         -    aCoord[i] = DCOORD(pCell->aCoord[i]);
   908         -  }
   909         -  return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
   910         -}
   911         -
   912         -/* 
   913         -** Cursor pCursor currently points to a cell in a non-leaf page.
   914         -** Set *pbEof to true if the sub-tree headed by the cell is filtered
   915         -** (excluded) by the constraints in the pCursor->aConstraint[] 
   916         -** array, or false otherwise.
   917         -**
   918         -** Return SQLITE_OK if successful or an SQLite error code if an error
   919         -** occurs within a geometry callback.
   920         -*/
   921         -static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   922         -  RtreeCell cell;
   923         -  int ii;
   924         -  int bRes = 0;
   925         -  int rc = SQLITE_OK;
   926         -
   927         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   928         -  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
   929         -    RtreeConstraint *p = &pCursor->aConstraint[ii];
   930         -    RtreeDValue cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
   931         -    RtreeDValue cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
   932         -
   933         -    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   934         -        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   935         -    );
   936         -
   937         -    switch( p->op ){
   938         -      case RTREE_LE: case RTREE_LT: 
   939         -        bRes = p->rValue<cell_min; 
   940         -        break;
   941         -
   942         -      case RTREE_GE: case RTREE_GT: 
   943         -        bRes = p->rValue>cell_max; 
   944         -        break;
   945         -
   946         -      case RTREE_EQ:
   947         -        bRes = (p->rValue>cell_max || p->rValue<cell_min);
   948         -        break;
   949         -
   950         -      default: {
   951         -        assert( p->op==RTREE_MATCH );
   952         -        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
   953         -        bRes = !bRes;
   954         -        break;
   955         -      }
   956         -    }
   957         -  }
   958         -
   959         -  *pbEof = bRes;
          904  +  return pCsr->atEOF;
          905  +}
          906  +
          907  +/*
          908  +** Convert raw bits from the on-disk RTree record into a coordinate value.
          909  +** The on-disk format is big-endian and needs to be converted for little-
          910  +** endian platforms.  The on-disk record stores integer coordinates if
          911  +** eInt is true and it stores 32-bit floating point records if eInt is
          912  +** false.  a[] is the four bytes of the on-disk record to be decoded.
          913  +** Store the results in "r".
          914  +**
          915  +** There are three versions of this macro, one each for little-endian and
          916  +** big-endian processors and a third generic implementation.  The endian-
          917  +** specific implementations are much faster and are preferred if the
          918  +** processor endianness is known at compile-time.  The SQLITE_BYTEORDER
          919  +** macro is part of sqliteInt.h and hence the endian-specific
          920  +** implementation will only be used if this module is compiled as part
          921  +** of the amalgamation.
          922  +*/
          923  +#if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234
          924  +#define RTREE_DECODE_COORD(eInt, a, r) {                        \
          925  +    RtreeCoord c;    /* Coordinate decoded */                   \
          926  +    memcpy(&c.u,a,4);                                           \
          927  +    c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)|                   \
          928  +          ((c.u&0xff)<<24)|((c.u&0xff00)<<8);                   \
          929  +    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
          930  +}
          931  +#elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321
          932  +#define RTREE_DECODE_COORD(eInt, a, r) {                        \
          933  +    RtreeCoord c;    /* Coordinate decoded */                   \
          934  +    memcpy(&c.u,a,4);                                           \
          935  +    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
          936  +}
          937  +#else
          938  +#define RTREE_DECODE_COORD(eInt, a, r) {                        \
          939  +    RtreeCoord c;    /* Coordinate decoded */                   \
          940  +    c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16)                     \
          941  +           +((u32)a[2]<<8) + a[3];                              \
          942  +    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
          943  +}
          944  +#endif
          945  +
          946  +/*
          947  +** Check the RTree node or entry given by pCellData and p against the MATCH
          948  +** constraint pConstraint.  
          949  +*/
          950  +static int rtreeCallbackConstraint(
          951  +  RtreeConstraint *pConstraint,  /* The constraint to test */
          952  +  int eInt,                      /* True if RTree holding integer coordinates */
          953  +  u8 *pCellData,                 /* Raw cell content */
          954  +  RtreeSearchPoint *pSearch,     /* Container of this cell */
          955  +  sqlite3_rtree_dbl *prScore,    /* OUT: score for the cell */
          956  +  int *peWithin                  /* OUT: visibility of the cell */
          957  +){
          958  +  int i;                                                /* Loop counter */
          959  +  sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */
          960  +  int nCoord = pInfo->nCoord;                           /* No. of coordinates */
          961  +  int rc;                                             /* Callback return code */
          962  +  sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2];   /* Decoded coordinates */
          963  +
          964  +  assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );
          965  +  assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );
          966  +
          967  +  if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){
          968  +    pInfo->iRowid = readInt64(pCellData);
          969  +  }
          970  +  pCellData += 8;
          971  +  for(i=0; i<nCoord; i++, pCellData += 4){
          972  +    RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]);
          973  +  }
          974  +  if( pConstraint->op==RTREE_MATCH ){
          975  +    rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo,
          976  +                              nCoord, aCoord, &i);
          977  +    if( i==0 ) *peWithin = NOT_WITHIN;
          978  +    *prScore = RTREE_ZERO;
          979  +  }else{
          980  +    pInfo->aCoord = aCoord;
          981  +    pInfo->iLevel = pSearch->iLevel - 1;
          982  +    pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
          983  +    pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
          984  +    rc = pConstraint->u.xQueryFunc(pInfo);
          985  +    if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
          986  +    if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
          987  +      *prScore = pInfo->rScore;
          988  +    }
          989  +  }
   960    990     return rc;
   961    991   }
   962    992   
   963    993   /* 
   964         -** Test if the cell that cursor pCursor currently points to
   965         -** would be filtered (excluded) by the constraints in the 
   966         -** pCursor->aConstraint[] array. If so, set *pbEof to true before
   967         -** returning. If the cell is not filtered (excluded) by the constraints,
   968         -** set pbEof to zero.
   969         -**
   970         -** Return SQLITE_OK if successful or an SQLite error code if an error
   971         -** occurs within a geometry callback.
   972         -**
   973         -** This function assumes that the cell is part of a leaf node.
   974         -*/
   975         -static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   976         -  RtreeCell cell;
   977         -  int ii;
   978         -  *pbEof = 0;
   979         -
   980         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   981         -  for(ii=0; ii<pCursor->nConstraint; ii++){
   982         -    RtreeConstraint *p = &pCursor->aConstraint[ii];
   983         -    RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
   984         -    int res;
   985         -    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   986         -        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   987         -    );
   988         -    switch( p->op ){
   989         -      case RTREE_LE: res = (coord<=p->rValue); break;
   990         -      case RTREE_LT: res = (coord<p->rValue);  break;
   991         -      case RTREE_GE: res = (coord>=p->rValue); break;
   992         -      case RTREE_GT: res = (coord>p->rValue);  break;
   993         -      case RTREE_EQ: res = (coord==p->rValue); break;
   994         -      default: {
   995         -        int rc;
   996         -        assert( p->op==RTREE_MATCH );
   997         -        rc = testRtreeGeom(pRtree, p, &cell, &res);
   998         -        if( rc!=SQLITE_OK ){
   999         -          return rc;
  1000         -        }
  1001         -        break;
  1002         -      }
  1003         -    }
  1004         -
  1005         -    if( !res ){
  1006         -      *pbEof = 1;
  1007         -      return SQLITE_OK;
  1008         -    }
  1009         -  }
  1010         -
  1011         -  return SQLITE_OK;
  1012         -}
  1013         -
  1014         -/*
  1015         -** Cursor pCursor currently points at a node that heads a sub-tree of
  1016         -** height iHeight (if iHeight==0, then the node is a leaf). Descend
  1017         -** to point to the left-most cell of the sub-tree that matches the 
  1018         -** configured constraints.
  1019         -*/
  1020         -static int descendToCell(
  1021         -  Rtree *pRtree, 
  1022         -  RtreeCursor *pCursor, 
  1023         -  int iHeight,
  1024         -  int *pEof                 /* OUT: Set to true if cannot descend */
  1025         -){
  1026         -  int isEof;
  1027         -  int rc;
  1028         -  int ii;
  1029         -  RtreeNode *pChild;
  1030         -  sqlite3_int64 iRowid;
  1031         -
  1032         -  RtreeNode *pSavedNode = pCursor->pNode;
  1033         -  int iSavedCell = pCursor->iCell;
  1034         -
  1035         -  assert( iHeight>=0 );
  1036         -
  1037         -  if( iHeight==0 ){
  1038         -    rc = testRtreeEntry(pRtree, pCursor, &isEof);
  1039         -  }else{
  1040         -    rc = testRtreeCell(pRtree, pCursor, &isEof);
  1041         -  }
  1042         -  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
  1043         -    goto descend_to_cell_out;
  1044         -  }
  1045         -
  1046         -  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
  1047         -  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
  1048         -  if( rc!=SQLITE_OK ){
  1049         -    goto descend_to_cell_out;
  1050         -  }
  1051         -
  1052         -  nodeRelease(pRtree, pCursor->pNode);
  1053         -  pCursor->pNode = pChild;
  1054         -  isEof = 1;
  1055         -  for(ii=0; isEof && ii<NCELL(pChild); ii++){
  1056         -    pCursor->iCell = ii;
  1057         -    rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
  1058         -    if( rc!=SQLITE_OK ){
  1059         -      goto descend_to_cell_out;
  1060         -    }
  1061         -  }
  1062         -
  1063         -  if( isEof ){
  1064         -    assert( pCursor->pNode==pChild );
  1065         -    nodeReference(pSavedNode);
  1066         -    nodeRelease(pRtree, pChild);
  1067         -    pCursor->pNode = pSavedNode;
  1068         -    pCursor->iCell = iSavedCell;
  1069         -  }
  1070         -
  1071         -descend_to_cell_out:
  1072         -  *pEof = isEof;
  1073         -  return rc;
          994  +** Check the internal RTree node given by pCellData against constraint p.
          995  +** If this constraint cannot be satisfied by any child within the node,
          996  +** set *peWithin to NOT_WITHIN.
          997  +*/
          998  +static void rtreeNonleafConstraint(
          999  +  RtreeConstraint *p,        /* The constraint to test */
         1000  +  int eInt,                  /* True if RTree holds integer coordinates */
         1001  +  u8 *pCellData,             /* Raw cell content as appears on disk */
         1002  +  int *peWithin              /* Adjust downward, as appropriate */
         1003  +){
         1004  +  sqlite3_rtree_dbl val;     /* Coordinate value convert to a double */
         1005  +
         1006  +  /* p->iCoord might point to either a lower or upper bound coordinate
         1007  +  ** in a coordinate pair.  But make pCellData point to the lower bound.
         1008  +  */
         1009  +  pCellData += 8 + 4*(p->iCoord&0xfe);
         1010  +
         1011  +  assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
         1012  +      || p->op==RTREE_GT || p->op==RTREE_EQ );
         1013  +  switch( p->op ){
         1014  +    case RTREE_LE:
         1015  +    case RTREE_LT:
         1016  +    case RTREE_EQ:
         1017  +      RTREE_DECODE_COORD(eInt, pCellData, val);
         1018  +      /* val now holds the lower bound of the coordinate pair */
         1019  +      if( p->u.rValue>=val ) return;
         1020  +      if( p->op!=RTREE_EQ ) break;  /* RTREE_LE and RTREE_LT end here */
         1021  +      /* Fall through for the RTREE_EQ case */
         1022  +
         1023  +    default: /* RTREE_GT or RTREE_GE,  or fallthrough of RTREE_EQ */
         1024  +      pCellData += 4;
         1025  +      RTREE_DECODE_COORD(eInt, pCellData, val);
         1026  +      /* val now holds the upper bound of the coordinate pair */
         1027  +      if( p->u.rValue<=val ) return;
         1028  +  }
         1029  +  *peWithin = NOT_WITHIN;
         1030  +}
         1031  +
         1032  +/*
         1033  +** Check the leaf RTree cell given by pCellData against constraint p.
         1034  +** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
         1035  +** If the constraint is satisfied, leave *peWithin unchanged.
         1036  +**
         1037  +** The constraint is of the form:  xN op $val
         1038  +**
         1039  +** The op is given by p->op.  The xN is p->iCoord-th coordinate in
         1040  +** pCellData.  $val is given by p->u.rValue.
         1041  +*/
         1042  +static void rtreeLeafConstraint(
         1043  +  RtreeConstraint *p,        /* The constraint to test */
         1044  +  int eInt,                  /* True if RTree holds integer coordinates */
         1045  +  u8 *pCellData,             /* Raw cell content as appears on disk */
         1046  +  int *peWithin              /* Adjust downward, as appropriate */
         1047  +){
         1048  +  RtreeDValue xN;      /* Coordinate value converted to a double */
         1049  +
         1050  +  assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
         1051  +      || p->op==RTREE_GT || p->op==RTREE_EQ );
         1052  +  pCellData += 8 + p->iCoord*4;
         1053  +  RTREE_DECODE_COORD(eInt, pCellData, xN);
         1054  +  switch( p->op ){
         1055  +    case RTREE_LE: if( xN <= p->u.rValue ) return;  break;
         1056  +    case RTREE_LT: if( xN <  p->u.rValue ) return;  break;
         1057  +    case RTREE_GE: if( xN >= p->u.rValue ) return;  break;
         1058  +    case RTREE_GT: if( xN >  p->u.rValue ) return;  break;
         1059  +    default:       if( xN == p->u.rValue ) return;  break;
         1060  +  }
         1061  +  *peWithin = NOT_WITHIN;
  1074   1062   }
  1075   1063   
  1076   1064   /*
  1077   1065   ** One of the cells in node pNode is guaranteed to have a 64-bit 
  1078   1066   ** integer value equal to iRowid. Return the index of this cell.
  1079   1067   */
  1080   1068   static int nodeRowidIndex(
................................................................................
  1081   1069     Rtree *pRtree, 
  1082   1070     RtreeNode *pNode, 
  1083   1071     i64 iRowid,
  1084   1072     int *piIndex
  1085   1073   ){
  1086   1074     int ii;
  1087   1075     int nCell = NCELL(pNode);
         1076  +  assert( nCell<200 );
  1088   1077     for(ii=0; ii<nCell; ii++){
  1089   1078       if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
  1090   1079         *piIndex = ii;
  1091   1080         return SQLITE_OK;
  1092   1081       }
  1093   1082     }
  1094   1083     return SQLITE_CORRUPT_VTAB;
................................................................................
  1102   1091     RtreeNode *pParent = pNode->pParent;
  1103   1092     if( pParent ){
  1104   1093       return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
  1105   1094     }
  1106   1095     *piIndex = -1;
  1107   1096     return SQLITE_OK;
  1108   1097   }
         1098  +
         1099  +/*
         1100  +** Compare two search points.  Return negative, zero, or positive if the first
         1101  +** is less than, equal to, or greater than the second.
         1102  +**
         1103  +** The rScore is the primary key.  Smaller rScore values come first.
         1104  +** If the rScore is a tie, then use iLevel as the tie breaker with smaller
         1105  +** iLevel values coming first.  In this way, if rScore is the same for all
         1106  +** SearchPoints, then iLevel becomes the deciding factor and the result
         1107  +** is a depth-first search, which is the desired default behavior.
         1108  +*/
         1109  +static int rtreeSearchPointCompare(
         1110  +  const RtreeSearchPoint *pA,
         1111  +  const RtreeSearchPoint *pB
         1112  +){
         1113  +  if( pA->rScore<pB->rScore ) return -1;
         1114  +  if( pA->rScore>pB->rScore ) return +1;
         1115  +  if( pA->iLevel<pB->iLevel ) return -1;
         1116  +  if( pA->iLevel>pB->iLevel ) return +1;
         1117  +  return 0;
         1118  +}
         1119  +
         1120  +/*
         1121  +** Interchange to search points in a cursor.
         1122  +*/
         1123  +static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
         1124  +  RtreeSearchPoint t = p->aPoint[i];
         1125  +  assert( i<j );
         1126  +  p->aPoint[i] = p->aPoint[j];
         1127  +  p->aPoint[j] = t;
         1128  +  i++; j++;
         1129  +  if( i<RTREE_CACHE_SZ ){
         1130  +    if( j>=RTREE_CACHE_SZ ){
         1131  +      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
         1132  +      p->aNode[i] = 0;
         1133  +    }else{
         1134  +      RtreeNode *pTemp = p->aNode[i];
         1135  +      p->aNode[i] = p->aNode[j];
         1136  +      p->aNode[j] = pTemp;
         1137  +    }
         1138  +  }
         1139  +}
         1140  +
         1141  +/*
         1142  +** Return the search point with the lowest current score.
         1143  +*/
         1144  +static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
         1145  +  return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
         1146  +}
         1147  +
         1148  +/*
         1149  +** Get the RtreeNode for the search point with the lowest score.
         1150  +*/
         1151  +static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
         1152  +  sqlite3_int64 id;
         1153  +  int ii = 1 - pCur->bPoint;
         1154  +  assert( ii==0 || ii==1 );
         1155  +  assert( pCur->bPoint || pCur->nPoint );
         1156  +  if( pCur->aNode[ii]==0 ){
         1157  +    assert( pRC!=0 );
         1158  +    id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
         1159  +    *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
         1160  +  }
         1161  +  return pCur->aNode[ii];
         1162  +}
         1163  +
         1164  +/*
         1165  +** Push a new element onto the priority queue
         1166  +*/
         1167  +static RtreeSearchPoint *rtreeEnqueue(
         1168  +  RtreeCursor *pCur,    /* The cursor */
         1169  +  RtreeDValue rScore,   /* Score for the new search point */
         1170  +  u8 iLevel             /* Level for the new search point */
         1171  +){
         1172  +  int i, j;
         1173  +  RtreeSearchPoint *pNew;
         1174  +  if( pCur->nPoint>=pCur->nPointAlloc ){
         1175  +    int nNew = pCur->nPointAlloc*2 + 8;
         1176  +    pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
         1177  +    if( pNew==0 ) return 0;
         1178  +    pCur->aPoint = pNew;
         1179  +    pCur->nPointAlloc = nNew;
         1180  +  }
         1181  +  i = pCur->nPoint++;
         1182  +  pNew = pCur->aPoint + i;
         1183  +  pNew->rScore = rScore;
         1184  +  pNew->iLevel = iLevel;
         1185  +  assert( iLevel>=0 && iLevel<=RTREE_MAX_DEPTH );
         1186  +  while( i>0 ){
         1187  +    RtreeSearchPoint *pParent;
         1188  +    j = (i-1)/2;
         1189  +    pParent = pCur->aPoint + j;
         1190  +    if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
         1191  +    rtreeSearchPointSwap(pCur, j, i);
         1192  +    i = j;
         1193  +    pNew = pParent;
         1194  +  }
         1195  +  return pNew;
         1196  +}
         1197  +
         1198  +/*
         1199  +** Allocate a new RtreeSearchPoint and return a pointer to it.  Return
         1200  +** NULL if malloc fails.
         1201  +*/
         1202  +static RtreeSearchPoint *rtreeSearchPointNew(
         1203  +  RtreeCursor *pCur,    /* The cursor */
         1204  +  RtreeDValue rScore,   /* Score for the new search point */
         1205  +  u8 iLevel             /* Level for the new search point */
         1206  +){
         1207  +  RtreeSearchPoint *pNew, *pFirst;
         1208  +  pFirst = rtreeSearchPointFirst(pCur);
         1209  +  pCur->anQueue[iLevel]++;
         1210  +  if( pFirst==0
         1211  +   || pFirst->rScore>rScore 
         1212  +   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
         1213  +  ){
         1214  +    if( pCur->bPoint ){
         1215  +      int ii;
         1216  +      pNew = rtreeEnqueue(pCur, rScore, iLevel);
         1217  +      if( pNew==0 ) return 0;
         1218  +      ii = (int)(pNew - pCur->aPoint) + 1;
         1219  +      if( ii<RTREE_CACHE_SZ ){
         1220  +        assert( pCur->aNode[ii]==0 );
         1221  +        pCur->aNode[ii] = pCur->aNode[0];
         1222  +       }else{
         1223  +        nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
         1224  +      }
         1225  +      pCur->aNode[0] = 0;
         1226  +      *pNew = pCur->sPoint;
         1227  +    }
         1228  +    pCur->sPoint.rScore = rScore;
         1229  +    pCur->sPoint.iLevel = iLevel;
         1230  +    pCur->bPoint = 1;
         1231  +    return &pCur->sPoint;
         1232  +  }else{
         1233  +    return rtreeEnqueue(pCur, rScore, iLevel);
         1234  +  }
         1235  +}
         1236  +
         1237  +#if 0
         1238  +/* Tracing routines for the RtreeSearchPoint queue */
         1239  +static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
         1240  +  if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
         1241  +  printf(" %d.%05lld.%02d %g %d",
         1242  +    p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
         1243  +  );
         1244  +  idx++;
         1245  +  if( idx<RTREE_CACHE_SZ ){
         1246  +    printf(" %p\n", pCur->aNode[idx]);
         1247  +  }else{
         1248  +    printf("\n");
         1249  +  }
         1250  +}
         1251  +static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
         1252  +  int ii;
         1253  +  printf("=== %9s ", zPrefix);
         1254  +  if( pCur->bPoint ){
         1255  +    tracePoint(&pCur->sPoint, -1, pCur);
         1256  +  }
         1257  +  for(ii=0; ii<pCur->nPoint; ii++){
         1258  +    if( ii>0 || pCur->bPoint ) printf("              ");
         1259  +    tracePoint(&pCur->aPoint[ii], ii, pCur);
         1260  +  }
         1261  +}
         1262  +# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
         1263  +#else
         1264  +# define RTREE_QUEUE_TRACE(A,B)   /* no-op */
         1265  +#endif
         1266  +
         1267  +/* Remove the search point with the lowest current score.
         1268  +*/
         1269  +static void rtreeSearchPointPop(RtreeCursor *p){
         1270  +  int i, j, k, n;
         1271  +  i = 1 - p->bPoint;
         1272  +  assert( i==0 || i==1 );
         1273  +  if( p->aNode[i] ){
         1274  +    nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
         1275  +    p->aNode[i] = 0;
         1276  +  }
         1277  +  if( p->bPoint ){
         1278  +    p->anQueue[p->sPoint.iLevel]--;
         1279  +    p->bPoint = 0;
         1280  +  }else if( p->nPoint ){
         1281  +    p->anQueue[p->aPoint[0].iLevel]--;
         1282  +    n = --p->nPoint;
         1283  +    p->aPoint[0] = p->aPoint[n];
         1284  +    if( n<RTREE_CACHE_SZ-1 ){
         1285  +      p->aNode[1] = p->aNode[n+1];
         1286  +      p->aNode[n+1] = 0;
         1287  +    }
         1288  +    i = 0;
         1289  +    while( (j = i*2+1)<n ){
         1290  +      k = j+1;
         1291  +      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
         1292  +        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
         1293  +          rtreeSearchPointSwap(p, i, k);
         1294  +          i = k;
         1295  +        }else{
         1296  +          break;
         1297  +        }
         1298  +      }else{
         1299  +        if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
         1300  +          rtreeSearchPointSwap(p, i, j);
         1301  +          i = j;
         1302  +        }else{
         1303  +          break;
         1304  +        }
         1305  +      }
         1306  +    }
         1307  +  }
         1308  +}
         1309  +
         1310  +
         1311  +/*
         1312  +** Continue the search on cursor pCur until the front of the queue
         1313  +** contains an entry suitable for returning as a result-set row,
         1314  +** or until the RtreeSearchPoint queue is empty, indicating that the
         1315  +** query has completed.
         1316  +*/
         1317  +static int rtreeStepToLeaf(RtreeCursor *pCur){
         1318  +  RtreeSearchPoint *p;
         1319  +  Rtree *pRtree = RTREE_OF_CURSOR(pCur);
         1320  +  RtreeNode *pNode;
         1321  +  int eWithin;
         1322  +  int rc = SQLITE_OK;
         1323  +  int nCell;
         1324  +  int nConstraint = pCur->nConstraint;
         1325  +  int ii;
         1326  +  int eInt;
         1327  +  RtreeSearchPoint x;
         1328  +
         1329  +  eInt = pRtree->eCoordType==RTREE_COORD_INT32;
         1330  +  while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
         1331  +    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
         1332  +    if( rc ) return rc;
         1333  +    nCell = NCELL(pNode);
         1334  +    assert( nCell<200 );
         1335  +    while( p->iCell<nCell ){
         1336  +      sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1;
         1337  +      u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
         1338  +      eWithin = FULLY_WITHIN;
         1339  +      for(ii=0; ii<nConstraint; ii++){
         1340  +        RtreeConstraint *pConstraint = pCur->aConstraint + ii;
         1341  +        if( pConstraint->op>=RTREE_MATCH ){
         1342  +          rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
         1343  +                                       &rScore, &eWithin);
         1344  +          if( rc ) return rc;
         1345  +        }else if( p->iLevel==1 ){
         1346  +          rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin);
         1347  +        }else{
         1348  +          rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin);
         1349  +        }
         1350  +        if( eWithin==NOT_WITHIN ) break;
         1351  +      }
         1352  +      p->iCell++;
         1353  +      if( eWithin==NOT_WITHIN ) continue;
         1354  +      x.iLevel = p->iLevel - 1;
         1355  +      if( x.iLevel ){
         1356  +        x.id = readInt64(pCellData);
         1357  +        x.iCell = 0;
         1358  +      }else{
         1359  +        x.id = p->id;
         1360  +        x.iCell = p->iCell - 1;
         1361  +      }
         1362  +      if( p->iCell>=nCell ){
         1363  +        RTREE_QUEUE_TRACE(pCur, "POP-S:");
         1364  +        rtreeSearchPointPop(pCur);
         1365  +      }
         1366  +      if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
         1367  +      p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
         1368  +      if( p==0 ) return SQLITE_NOMEM;
         1369  +      p->eWithin = eWithin;
         1370  +      p->id = x.id;
         1371  +      p->iCell = x.iCell;
         1372  +      RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
         1373  +      break;
         1374  +    }
         1375  +    if( p->iCell>=nCell ){
         1376  +      RTREE_QUEUE_TRACE(pCur, "POP-Se:");
         1377  +      rtreeSearchPointPop(pCur);
         1378  +    }
         1379  +  }
         1380  +  pCur->atEOF = p==0;
         1381  +  return SQLITE_OK;
         1382  +}
  1109   1383   
  1110   1384   /* 
  1111   1385   ** Rtree virtual table module xNext method.
  1112   1386   */
  1113   1387   static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  1114         -  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
  1115   1388     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1116   1389     int rc = SQLITE_OK;
  1117   1390   
  1118         -  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
  1119         -  ** already at EOF. It is against the rules to call the xNext() method of
  1120         -  ** a cursor that has already reached EOF.
  1121         -  */
  1122         -  assert( pCsr->pNode );
  1123         -
  1124         -  if( pCsr->iStrategy==1 ){
  1125         -    /* This "scan" is a direct lookup by rowid. There is no next entry. */
  1126         -    nodeRelease(pRtree, pCsr->pNode);
  1127         -    pCsr->pNode = 0;
  1128         -  }else{
  1129         -    /* Move to the next entry that matches the configured constraints. */
  1130         -    int iHeight = 0;
  1131         -    while( pCsr->pNode ){
  1132         -      RtreeNode *pNode = pCsr->pNode;
  1133         -      int nCell = NCELL(pNode);
  1134         -      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
  1135         -        int isEof;
  1136         -        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
  1137         -        if( rc!=SQLITE_OK || !isEof ){
  1138         -          return rc;
  1139         -        }
  1140         -      }
  1141         -      pCsr->pNode = pNode->pParent;
  1142         -      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
  1143         -      if( rc!=SQLITE_OK ){
  1144         -        return rc;
  1145         -      }
  1146         -      nodeReference(pCsr->pNode);
  1147         -      nodeRelease(pRtree, pNode);
  1148         -      iHeight++;
  1149         -    }
  1150         -  }
  1151         -
         1391  +  /* Move to the next entry that matches the configured constraints. */
         1392  +  RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
         1393  +  rtreeSearchPointPop(pCsr);
         1394  +  rc = rtreeStepToLeaf(pCsr);
  1152   1395     return rc;
  1153   1396   }
  1154   1397   
  1155   1398   /* 
  1156   1399   ** Rtree virtual table module xRowid method.
  1157   1400   */
  1158   1401   static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
  1159         -  Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1160   1402     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1161         -
  1162         -  assert(pCsr->pNode);
  1163         -  *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1164         -
  1165         -  return SQLITE_OK;
         1403  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1404  +  int rc = SQLITE_OK;
         1405  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
         1406  +  if( rc==SQLITE_OK && p ){
         1407  +    *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
         1408  +  }
         1409  +  return rc;
  1166   1410   }
  1167   1411   
  1168   1412   /* 
  1169   1413   ** Rtree virtual table module xColumn method.
  1170   1414   */
  1171   1415   static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  1172   1416     Rtree *pRtree = (Rtree *)cur->pVtab;
  1173   1417     RtreeCursor *pCsr = (RtreeCursor *)cur;
         1418  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1419  +  RtreeCoord c;
         1420  +  int rc = SQLITE_OK;
         1421  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
  1174   1422   
         1423  +  if( rc ) return rc;
         1424  +  if( p==0 ) return SQLITE_OK;
  1175   1425     if( i==0 ){
  1176         -    i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1177         -    sqlite3_result_int64(ctx, iRowid);
         1426  +    sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
  1178   1427     }else{
  1179         -    RtreeCoord c;
  1180         -    nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
         1428  +    if( rc ) return rc;
         1429  +    nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
  1181   1430   #ifndef SQLITE_RTREE_INT_ONLY
  1182   1431       if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
  1183   1432         sqlite3_result_double(ctx, c.f);
  1184   1433       }else
  1185   1434   #endif
  1186   1435       {
  1187   1436         assert( pRtree->eCoordType==RTREE_COORD_INT32 );
  1188   1437         sqlite3_result_int(ctx, c.i);
  1189   1438       }
  1190   1439     }
  1191         -
  1192   1440     return SQLITE_OK;
  1193   1441   }
  1194   1442   
  1195   1443   /* 
  1196   1444   ** Use nodeAcquire() to obtain the leaf node containing the record with 
  1197   1445   ** rowid iRowid. If successful, set *ppLeaf to point to the node and
  1198   1446   ** return SQLITE_OK. If there is no such record in the table, set
  1199   1447   ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
  1200   1448   ** to zero and return an SQLite error code.
  1201   1449   */
  1202         -static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
         1450  +static int findLeafNode(
         1451  +  Rtree *pRtree,              /* RTree to search */
         1452  +  i64 iRowid,                 /* The rowid searching for */
         1453  +  RtreeNode **ppLeaf,         /* Write the node here */
         1454  +  sqlite3_int64 *piNode       /* Write the node-id here */
         1455  +){
  1203   1456     int rc;
  1204   1457     *ppLeaf = 0;
  1205   1458     sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
  1206   1459     if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
  1207   1460       i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
         1461  +    if( piNode ) *piNode = iNode;
  1208   1462       rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
  1209   1463       sqlite3_reset(pRtree->pReadRowid);
  1210   1464     }else{
  1211   1465       rc = sqlite3_reset(pRtree->pReadRowid);
  1212   1466     }
  1213   1467     return rc;
  1214   1468   }
................................................................................
  1216   1470   /*
  1217   1471   ** This function is called to configure the RtreeConstraint object passed
  1218   1472   ** as the second argument for a MATCH constraint. The value passed as the
  1219   1473   ** first argument to this function is the right-hand operand to the MATCH
  1220   1474   ** operator.
  1221   1475   */
  1222   1476   static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
  1223         -  RtreeMatchArg *p;
  1224         -  sqlite3_rtree_geometry *pGeom;
  1225         -  int nBlob;
         1477  +  RtreeMatchArg *pBlob;              /* BLOB returned by geometry function */
         1478  +  sqlite3_rtree_query_info *pInfo;   /* Callback information */
         1479  +  int nBlob;                         /* Size of the geometry function blob */
         1480  +  int nExpected;                     /* Expected size of the BLOB */
  1226   1481   
  1227   1482     /* Check that value is actually a blob. */
  1228   1483     if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
  1229   1484   
  1230   1485     /* Check that the blob is roughly the right size. */
  1231   1486     nBlob = sqlite3_value_bytes(pValue);
  1232   1487     if( nBlob<(int)sizeof(RtreeMatchArg) 
  1233   1488      || ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
  1234   1489     ){
  1235   1490       return SQLITE_ERROR;
  1236   1491     }
  1237   1492   
  1238         -  pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
  1239         -      sizeof(sqlite3_rtree_geometry) + nBlob
  1240         -  );
  1241         -  if( !pGeom ) return SQLITE_NOMEM;
  1242         -  memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
  1243         -  p = (RtreeMatchArg *)&pGeom[1];
         1493  +  pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob );
         1494  +  if( !pInfo ) return SQLITE_NOMEM;
         1495  +  memset(pInfo, 0, sizeof(*pInfo));
         1496  +  pBlob = (RtreeMatchArg*)&pInfo[1];
  1244   1497   
  1245         -  memcpy(p, sqlite3_value_blob(pValue), nBlob);
  1246         -  if( p->magic!=RTREE_GEOMETRY_MAGIC 
  1247         -   || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
  1248         -  ){
  1249         -    sqlite3_free(pGeom);
         1498  +  memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
         1499  +  nExpected = (int)(sizeof(RtreeMatchArg) +
         1500  +                    (pBlob->nParam-1)*sizeof(RtreeDValue));
         1501  +  if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){
         1502  +    sqlite3_free(pInfo);
  1250   1503       return SQLITE_ERROR;
  1251   1504     }
         1505  +  pInfo->pContext = pBlob->cb.pContext;
         1506  +  pInfo->nParam = pBlob->nParam;
         1507  +  pInfo->aParam = pBlob->aParam;
  1252   1508   
  1253         -  pGeom->pContext = p->pContext;
  1254         -  pGeom->nParam = p->nParam;
  1255         -  pGeom->aParam = p->aParam;
  1256         -
  1257         -  pCons->xGeom = p->xGeom;
  1258         -  pCons->pGeom = pGeom;
         1509  +  if( pBlob->cb.xGeom ){
         1510  +    pCons->u.xGeom = pBlob->cb.xGeom;
         1511  +  }else{
         1512  +    pCons->op = RTREE_QUERY;
         1513  +    pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
         1514  +  }
         1515  +  pCons->pInfo = pInfo;
  1259   1516     return SQLITE_OK;
  1260   1517   }
  1261   1518   
  1262   1519   /* 
  1263   1520   ** Rtree virtual table module xFilter method.
  1264   1521   */
  1265   1522   static int rtreeFilter(
  1266   1523     sqlite3_vtab_cursor *pVtabCursor, 
  1267   1524     int idxNum, const char *idxStr,
  1268   1525     int argc, sqlite3_value **argv
  1269   1526   ){
  1270   1527     Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1271   1528     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1272         -
  1273   1529     RtreeNode *pRoot = 0;
  1274   1530     int ii;
  1275   1531     int rc = SQLITE_OK;
         1532  +  int iCell = 0;
  1276   1533   
  1277   1534     rtreeReference(pRtree);
  1278   1535   
  1279   1536     freeCursorConstraints(pCsr);
  1280   1537     pCsr->iStrategy = idxNum;
  1281   1538   
  1282   1539     if( idxNum==1 ){
  1283   1540       /* Special case - lookup by rowid. */
  1284   1541       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
         1542  +    RtreeSearchPoint *p;     /* Search point for the the leaf */
  1285   1543       i64 iRowid = sqlite3_value_int64(argv[0]);
  1286         -    rc = findLeafNode(pRtree, iRowid, &pLeaf);
  1287         -    pCsr->pNode = pLeaf; 
  1288         -    if( pLeaf ){
  1289         -      assert( rc==SQLITE_OK );
  1290         -      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
         1544  +    i64 iNode = 0;
         1545  +    rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
         1546  +    if( rc==SQLITE_OK && pLeaf!=0 ){
         1547  +      p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
         1548  +      assert( p!=0 );  /* Always returns pCsr->sPoint */
         1549  +      pCsr->aNode[0] = pLeaf;
         1550  +      p->id = iNode;
         1551  +      p->eWithin = PARTLY_WITHIN;
         1552  +      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
         1553  +      p->iCell = iCell;
         1554  +      RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
         1555  +    }else{
         1556  +      pCsr->atEOF = 1;
  1291   1557       }
  1292   1558     }else{
  1293   1559       /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
  1294   1560       ** with the configured constraints. 
  1295   1561       */
  1296         -    if( argc>0 ){
         1562  +    rc = nodeAcquire(pRtree, 1, 0, &pRoot);
         1563  +    if( rc==SQLITE_OK && argc>0 ){
  1297   1564         pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
  1298   1565         pCsr->nConstraint = argc;
  1299   1566         if( !pCsr->aConstraint ){
  1300   1567           rc = SQLITE_NOMEM;
  1301   1568         }else{
  1302   1569           memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
         1570  +        memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
  1303   1571           assert( (idxStr==0 && argc==0)
  1304   1572                   || (idxStr && (int)strlen(idxStr)==argc*2) );
  1305   1573           for(ii=0; ii<argc; ii++){
  1306   1574             RtreeConstraint *p = &pCsr->aConstraint[ii];
  1307   1575             p->op = idxStr[ii*2];
  1308         -          p->iCoord = idxStr[ii*2+1]-'a';
  1309         -          if( p->op==RTREE_MATCH ){
         1576  +          p->iCoord = idxStr[ii*2+1]-'0';
         1577  +          if( p->op>=RTREE_MATCH ){
  1310   1578               /* A MATCH operator. The right-hand-side must be a blob that
  1311   1579               ** can be cast into an RtreeMatchArg object. One created using
  1312   1580               ** an sqlite3_rtree_geometry_callback() SQL user function.
  1313   1581               */
  1314   1582               rc = deserializeGeometry(argv[ii], p);
  1315   1583               if( rc!=SQLITE_OK ){
  1316   1584                 break;
  1317   1585               }
         1586  +            p->pInfo->nCoord = pRtree->nDim*2;
         1587  +            p->pInfo->anQueue = pCsr->anQueue;
         1588  +            p->pInfo->mxLevel = pRtree->iDepth + 1;
  1318   1589             }else{
  1319   1590   #ifdef SQLITE_RTREE_INT_ONLY
  1320         -            p->rValue = sqlite3_value_int64(argv[ii]);
         1591  +            p->u.rValue = sqlite3_value_int64(argv[ii]);
  1321   1592   #else
  1322         -            p->rValue = sqlite3_value_double(argv[ii]);
         1593  +            p->u.rValue = sqlite3_value_double(argv[ii]);
  1323   1594   #endif
  1324   1595             }
  1325   1596           }
  1326   1597         }
  1327   1598       }
  1328         -  
  1329         -    if( rc==SQLITE_OK ){
  1330         -      pCsr->pNode = 0;
  1331         -      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  1332         -    }
  1333         -    if( rc==SQLITE_OK ){
  1334         -      int isEof = 1;
  1335         -      int nCell = NCELL(pRoot);
  1336         -      pCsr->pNode = pRoot;
  1337         -      for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
  1338         -        assert( pCsr->pNode==pRoot );
  1339         -        rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
  1340         -        if( !isEof ){
  1341         -          break;
  1342         -        }
  1343         -      }
  1344         -      if( rc==SQLITE_OK && isEof ){
  1345         -        assert( pCsr->pNode==pRoot );
  1346         -        nodeRelease(pRtree, pRoot);
  1347         -        pCsr->pNode = 0;
  1348         -      }
  1349         -      assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
  1350         -    }
  1351         -  }
  1352         -
         1599  +    if( rc==SQLITE_OK ){
         1600  +      RtreeSearchPoint *pNew;
         1601  +      pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1);
         1602  +      if( pNew==0 ) return SQLITE_NOMEM;
         1603  +      pNew->id = 1;
         1604  +      pNew->iCell = 0;
         1605  +      pNew->eWithin = PARTLY_WITHIN;
         1606  +      assert( pCsr->bPoint==1 );
         1607  +      pCsr->aNode[0] = pRoot;
         1608  +      pRoot = 0;
         1609  +      RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
         1610  +      rc = rtreeStepToLeaf(pCsr);
         1611  +    }
         1612  +  }
         1613  +
         1614  +  nodeRelease(pRtree, pRoot);
  1353   1615     rtreeRelease(pRtree);
  1354   1616     return rc;
  1355   1617   }
  1356   1618   
  1357   1619   /*
  1358   1620   ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this
  1359   1621   ** extension is currently being used by a version of SQLite too old to
................................................................................
  1447   1709           case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
  1448   1710           default:
  1449   1711             assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
  1450   1712             op = RTREE_MATCH; 
  1451   1713             break;
  1452   1714         }
  1453   1715         zIdxStr[iIdx++] = op;
  1454         -      zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
         1716  +      zIdxStr[iIdx++] = p->iColumn - 1 + '0';
  1455   1717         pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
  1456   1718         pIdxInfo->aConstraintUsage[ii].omit = 1;
  1457   1719       }
  1458   1720     }
  1459   1721   
  1460   1722     pIdxInfo->idxNum = 2;
  1461   1723     pIdxInfo->needToFreeIdxStr = 1;
................................................................................
  1540   1802     RtreeCell cell;
  1541   1803     memcpy(&cell, p, sizeof(RtreeCell));
  1542   1804     area = cellArea(pRtree, &cell);
  1543   1805     cellUnion(pRtree, &cell, pCell);
  1544   1806     return (cellArea(pRtree, &cell)-area);
  1545   1807   }
  1546   1808   
  1547         -#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
  1548   1809   static RtreeDValue cellOverlap(
  1549   1810     Rtree *pRtree, 
  1550   1811     RtreeCell *p, 
  1551   1812     RtreeCell *aCell, 
  1552         -  int nCell, 
  1553         -  int iExclude
         1813  +  int nCell
  1554   1814   ){
  1555   1815     int ii;
  1556         -  RtreeDValue overlap = 0.0;
         1816  +  RtreeDValue overlap = RTREE_ZERO;
  1557   1817     for(ii=0; ii<nCell; ii++){
  1558         -#if VARIANT_RSTARTREE_CHOOSESUBTREE
  1559         -    if( ii!=iExclude )
  1560         -#else
  1561         -    assert( iExclude==-1 );
  1562         -    UNUSED_PARAMETER(iExclude);
  1563         -#endif
  1564         -    {
  1565         -      int jj;
  1566         -      RtreeDValue o = (RtreeDValue)1;
  1567         -      for(jj=0; jj<(pRtree->nDim*2); jj+=2){
  1568         -        RtreeDValue x1, x2;
  1569         -
  1570         -        x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
  1571         -        x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
  1572         -
  1573         -        if( x2<x1 ){
  1574         -          o = 0.0;
  1575         -          break;
  1576         -        }else{
  1577         -          o = o * (x2-x1);
  1578         -        }
         1818  +    int jj;
         1819  +    RtreeDValue o = (RtreeDValue)1;
         1820  +    for(jj=0; jj<(pRtree->nDim*2); jj+=2){
         1821  +      RtreeDValue x1, x2;
         1822  +      x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
         1823  +      x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
         1824  +      if( x2<x1 ){
         1825  +        o = (RtreeDValue)0;
         1826  +        break;
         1827  +      }else{
         1828  +        o = o * (x2-x1);
  1579   1829         }
  1580         -      overlap += o;
  1581   1830       }
         1831  +    overlap += o;
  1582   1832     }
  1583   1833     return overlap;
  1584   1834   }
  1585         -#endif
  1586         -
  1587         -#if VARIANT_RSTARTREE_CHOOSESUBTREE
  1588         -static RtreeDValue cellOverlapEnlargement(
  1589         -  Rtree *pRtree, 
  1590         -  RtreeCell *p, 
  1591         -  RtreeCell *pInsert, 
  1592         -  RtreeCell *aCell, 
  1593         -  int nCell, 
  1594         -  int iExclude
  1595         -){
  1596         -  RtreeDValue before, after;
  1597         -  before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
  1598         -  cellUnion(pRtree, p, pInsert);
  1599         -  after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
  1600         -  return (after-before);
  1601         -}
  1602         -#endif
  1603   1835   
  1604   1836   
  1605   1837   /*
  1606   1838   ** This function implements the ChooseLeaf algorithm from Gutman[84].
  1607   1839   ** ChooseSubTree in r*tree terminology.
  1608   1840   */
  1609   1841   static int ChooseLeaf(
................................................................................
  1617   1849     RtreeNode *pNode;
  1618   1850     rc = nodeAcquire(pRtree, 1, 0, &pNode);
  1619   1851   
  1620   1852     for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
  1621   1853       int iCell;
  1622   1854       sqlite3_int64 iBest = 0;
  1623   1855   
  1624         -    RtreeDValue fMinGrowth = 0.0;
  1625         -    RtreeDValue fMinArea = 0.0;
  1626         -#if VARIANT_RSTARTREE_CHOOSESUBTREE
  1627         -    RtreeDValue fMinOverlap = 0.0;
  1628         -    RtreeDValue overlap;
  1629         -#endif
         1856  +    RtreeDValue fMinGrowth = RTREE_ZERO;
         1857  +    RtreeDValue fMinArea = RTREE_ZERO;
  1630   1858   
  1631   1859       int nCell = NCELL(pNode);
  1632   1860       RtreeCell cell;
  1633   1861       RtreeNode *pChild;
  1634   1862   
  1635   1863       RtreeCell *aCell = 0;
  1636   1864   
  1637         -#if VARIANT_RSTARTREE_CHOOSESUBTREE
  1638         -    if( ii==(pRtree->iDepth-1) ){
  1639         -      int jj;
  1640         -      aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
  1641         -      if( !aCell ){
  1642         -        rc = SQLITE_NOMEM;
  1643         -        nodeRelease(pRtree, pNode);
  1644         -        pNode = 0;
  1645         -        continue;
  1646         -      }
  1647         -      for(jj=0; jj<nCell; jj++){
  1648         -        nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
  1649         -      }
  1650         -    }
  1651         -#endif
  1652         -
  1653   1865       /* Select the child node which will be enlarged the least if pCell
  1654   1866       ** is inserted into it. Resolve ties by choosing the entry with
  1655   1867       ** the smallest area.
  1656   1868       */
  1657   1869       for(iCell=0; iCell<nCell; iCell++){
  1658   1870         int bBest = 0;
  1659   1871         RtreeDValue growth;
  1660   1872         RtreeDValue area;
  1661   1873         nodeGetCell(pRtree, pNode, iCell, &cell);
  1662   1874         growth = cellGrowth(pRtree, &cell, pCell);
  1663   1875         area = cellArea(pRtree, &cell);
  1664         -
  1665         -#if VARIANT_RSTARTREE_CHOOSESUBTREE
  1666         -      if( ii==(pRtree->iDepth-1) ){
  1667         -        overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
  1668         -      }else{
  1669         -        overlap = 0.0;
  1670         -      }
  1671         -      if( (iCell==0) 
  1672         -       || (overlap<fMinOverlap) 
  1673         -       || (overlap==fMinOverlap && growth<fMinGrowth)
  1674         -       || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
  1675         -      ){
  1676         -        bBest = 1;
  1677         -        fMinOverlap = overlap;
  1678         -      }
  1679         -#else
  1680   1876         if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
  1681   1877           bBest = 1;
  1682   1878         }
  1683         -#endif
  1684   1879         if( bBest ){
  1685   1880           fMinGrowth = growth;
  1686   1881           fMinArea = area;
  1687   1882           iBest = cell.iRowid;
  1688   1883         }
  1689   1884       }
  1690   1885   
................................................................................
  1747   1942     sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
  1748   1943     sqlite3_step(pRtree->pWriteParent);
  1749   1944     return sqlite3_reset(pRtree->pWriteParent);
  1750   1945   }
  1751   1946   
  1752   1947   static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
  1753   1948   
  1754         -#if VARIANT_GUTTMAN_LINEAR_SPLIT
  1755         -/*
  1756         -** Implementation of the linear variant of the PickNext() function from
  1757         -** Guttman[84].
  1758         -*/
  1759         -static RtreeCell *LinearPickNext(
  1760         -  Rtree *pRtree,
  1761         -  RtreeCell *aCell, 
  1762         -  int nCell, 
  1763         -  RtreeCell *pLeftBox, 
  1764         -  RtreeCell *pRightBox,
  1765         -  int *aiUsed
  1766         -){
  1767         -  int ii;
  1768         -  for(ii=0; aiUsed[ii]; ii++);
  1769         -  aiUsed[ii] = 1;
  1770         -  return &aCell[ii];
  1771         -}
  1772         -
  1773         -/*
  1774         -** Implementation of the linear variant of the PickSeeds() function from
  1775         -** Guttman[84].
  1776         -*/
  1777         -static void LinearPickSeeds(
  1778         -  Rtree *pRtree,
  1779         -  RtreeCell *aCell, 
  1780         -  int nCell, 
  1781         -  int *piLeftSeed, 
  1782         -  int *piRightSeed
  1783         -){
  1784         -  int i;
  1785         -  int iLeftSeed = 0;
  1786         -  int iRightSeed = 1;
  1787         -  RtreeDValue maxNormalInnerWidth = (RtreeDValue)0;
  1788         -
  1789         -  /* Pick two "seed" cells from the array of cells. The algorithm used
  1790         -  ** here is the LinearPickSeeds algorithm from Gutman[1984]. The 
  1791         -  ** indices of the two seed cells in the array are stored in local
  1792         -  ** variables iLeftSeek and iRightSeed.
  1793         -  */
  1794         -  for(i=0; i<pRtree->nDim; i++){
  1795         -    RtreeDValue x1 = DCOORD(aCell[0].aCoord[i*2]);
  1796         -    RtreeDValue x2 = DCOORD(aCell[0].aCoord[i*2+1]);
  1797         -    RtreeDValue x3 = x1;
  1798         -    RtreeDValue x4 = x2;
  1799         -    int jj;
  1800         -
  1801         -    int iCellLeft = 0;
  1802         -    int iCellRight = 0;
  1803         -
  1804         -    for(jj=1; jj<nCell; jj++){
  1805         -      RtreeDValue left = DCOORD(aCell[jj].aCoord[i*2]);
  1806         -      RtreeDValue right = DCOORD(aCell[jj].aCoord[i*2+1]);
  1807         -
  1808         -      if( left<x1 ) x1 = left;
  1809         -      if( right>x4 ) x4 = right;
  1810         -      if( left>x3 ){
  1811         -        x3 = left;
  1812         -        iCellRight = jj;
  1813         -      }
  1814         -      if( right<x2 ){
  1815         -        x2 = right;
  1816         -        iCellLeft = jj;
  1817         -      }
  1818         -    }
  1819         -
  1820         -    if( x4!=x1 ){
  1821         -      RtreeDValue normalwidth = (x3 - x2) / (x4 - x1);
  1822         -      if( normalwidth>maxNormalInnerWidth ){
  1823         -        iLeftSeed = iCellLeft;
  1824         -        iRightSeed = iCellRight;
  1825         -      }
  1826         -    }
  1827         -  }
  1828         -
  1829         -  *piLeftSeed = iLeftSeed;
  1830         -  *piRightSeed = iRightSeed;
  1831         -}
  1832         -#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
  1833         -
  1834         -#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
  1835         -/*
  1836         -** Implementation of the quadratic variant of the PickNext() function from
  1837         -** Guttman[84].
  1838         -*/
  1839         -static RtreeCell *QuadraticPickNext(
  1840         -  Rtree *pRtree,
  1841         -  RtreeCell *aCell, 
  1842         -  int nCell, 
  1843         -  RtreeCell *pLeftBox, 
  1844         -  RtreeCell *pRightBox,
  1845         -  int *aiUsed
  1846         -){
  1847         -  #define FABS(a) ((a)<0.0?-1.0*(a):(a))
  1848         -
  1849         -  int iSelect = -1;
  1850         -  RtreeDValue fDiff;
  1851         -  int ii;
  1852         -  for(ii=0; ii<nCell; ii++){
  1853         -    if( aiUsed[ii]==0 ){
  1854         -      RtreeDValue left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
  1855         -      RtreeDValue right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
  1856         -      RtreeDValue diff = FABS(right-left);
  1857         -      if( iSelect<0 || diff>fDiff ){
  1858         -        fDiff = diff;
  1859         -        iSelect = ii;
  1860         -      }
  1861         -    }
  1862         -  }
  1863         -  aiUsed[iSelect] = 1;
  1864         -  return &aCell[iSelect];
  1865         -}
  1866         -
  1867         -/*
  1868         -** Implementation of the quadratic variant of the PickSeeds() function from
  1869         -** Guttman[84].
  1870         -*/
  1871         -static void QuadraticPickSeeds(
  1872         -  Rtree *pRtree,
  1873         -  RtreeCell *aCell, 
  1874         -  int nCell, 
  1875         -  int *piLeftSeed, 
  1876         -  int *piRightSeed
  1877         -){
  1878         -  int ii;
  1879         -  int jj;
  1880         -
  1881         -  int iLeftSeed = 0;
  1882         -  int iRightSeed = 1;
  1883         -  RtreeDValue fWaste = 0.0;
  1884         -
  1885         -  for(ii=0; ii<nCell; ii++){
  1886         -    for(jj=ii+1; jj<nCell; jj++){
  1887         -      RtreeDValue right = cellArea(pRtree, &aCell[jj]);
  1888         -      RtreeDValue growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
  1889         -      RtreeDValue waste = growth - right;
  1890         -
  1891         -      if( waste>fWaste ){
  1892         -        iLeftSeed = ii;
  1893         -        iRightSeed = jj;
  1894         -        fWaste = waste;
  1895         -      }
  1896         -    }
  1897         -  }
  1898         -
  1899         -  *piLeftSeed = iLeftSeed;
  1900         -  *piRightSeed = iRightSeed;
  1901         -}
  1902         -#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
  1903   1949   
  1904   1950   /*
  1905   1951   ** Arguments aIdx, aDistance and aSpare all point to arrays of size
  1906   1952   ** nIdx. The aIdx array contains the set of integers from 0 to 
  1907   1953   ** (nIdx-1) in no particular order. This function sorts the values
  1908   1954   ** in aIdx according to the indexed values in aDistance. For
  1909   1955   ** example, assuming the inputs:
................................................................................
  2036   2082           assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) );
  2037   2083         }
  2038   2084       }
  2039   2085   #endif
  2040   2086     }
  2041   2087   }
  2042   2088   
  2043         -#if VARIANT_RSTARTREE_SPLIT
  2044   2089   /*
  2045   2090   ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
  2046   2091   */
  2047   2092   static int splitNodeStartree(
  2048   2093     Rtree *pRtree,
  2049   2094     RtreeCell *aCell,
  2050   2095     int nCell,
................................................................................
  2055   2100   ){
  2056   2101     int **aaSorted;
  2057   2102     int *aSpare;
  2058   2103     int ii;
  2059   2104   
  2060   2105     int iBestDim = 0;
  2061   2106     int iBestSplit = 0;
  2062         -  RtreeDValue fBestMargin = 0.0;
         2107  +  RtreeDValue fBestMargin = RTREE_ZERO;
  2063   2108   
  2064   2109     int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
  2065   2110   
  2066   2111     aaSorted = (int **)sqlite3_malloc(nByte);
  2067   2112     if( !aaSorted ){
  2068   2113       return SQLITE_NOMEM;
  2069   2114     }
................................................................................
  2076   2121       for(jj=0; jj<nCell; jj++){
  2077   2122         aaSorted[ii][jj] = jj;
  2078   2123       }
  2079   2124       SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
  2080   2125     }
  2081   2126   
  2082   2127     for(ii=0; ii<pRtree->nDim; ii++){
  2083         -    RtreeDValue margin = 0.0;
  2084         -    RtreeDValue fBestOverlap = 0.0;
  2085         -    RtreeDValue fBestArea = 0.0;
         2128  +    RtreeDValue margin = RTREE_ZERO;
         2129  +    RtreeDValue fBestOverlap = RTREE_ZERO;
         2130  +    RtreeDValue fBestArea = RTREE_ZERO;
  2086   2131       int iBestLeft = 0;
  2087   2132       int nLeft;
  2088   2133   
  2089   2134       for(
  2090   2135         nLeft=RTREE_MINCELLS(pRtree); 
  2091   2136         nLeft<=(nCell-RTREE_MINCELLS(pRtree)); 
  2092   2137         nLeft++
................................................................................
  2104   2149             cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
  2105   2150           }else{
  2106   2151             cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
  2107   2152           }
  2108   2153         }
  2109   2154         margin += cellMargin(pRtree, &left);
  2110   2155         margin += cellMargin(pRtree, &right);
  2111         -      overlap = cellOverlap(pRtree, &left, &right, 1, -1);
         2156  +      overlap = cellOverlap(pRtree, &left, &right, 1);
  2112   2157         area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
  2113   2158         if( (nLeft==RTREE_MINCELLS(pRtree))
  2114   2159          || (overlap<fBestOverlap)
  2115   2160          || (overlap==fBestOverlap && area<fBestArea)
  2116   2161         ){
  2117   2162           iBestLeft = nLeft;
  2118   2163           fBestOverlap = overlap;
................................................................................
  2136   2181       nodeInsertCell(pRtree, pTarget, pCell);
  2137   2182       cellUnion(pRtree, pBbox, pCell);
  2138   2183     }
  2139   2184   
  2140   2185     sqlite3_free(aaSorted);
  2141   2186     return SQLITE_OK;
  2142   2187   }
  2143         -#endif
  2144   2188   
  2145         -#if VARIANT_GUTTMAN_SPLIT
  2146         -/*
  2147         -** Implementation of the regular R-tree SplitNode from Guttman[1984].
  2148         -*/
  2149         -static int splitNodeGuttman(
  2150         -  Rtree *pRtree,
  2151         -  RtreeCell *aCell,
  2152         -  int nCell,
  2153         -  RtreeNode *pLeft,
  2154         -  RtreeNode *pRight,
  2155         -  RtreeCell *pBboxLeft,
  2156         -  RtreeCell *pBboxRight
  2157         -){
  2158         -  int iLeftSeed = 0;
  2159         -  int iRightSeed = 1;
  2160         -  int *aiUsed;
  2161         -  int i;
  2162         -
  2163         -  aiUsed = sqlite3_malloc(sizeof(int)*nCell);
  2164         -  if( !aiUsed ){
  2165         -    return SQLITE_NOMEM;
  2166         -  }
  2167         -  memset(aiUsed, 0, sizeof(int)*nCell);
  2168         -
  2169         -  PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
  2170         -
  2171         -  memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
  2172         -  memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
  2173         -  nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
  2174         -  nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
  2175         -  aiUsed[iLeftSeed] = 1;
  2176         -  aiUsed[iRightSeed] = 1;
  2177         -
  2178         -  for(i=nCell-2; i>0; i--){
  2179         -    RtreeCell *pNext;
  2180         -    pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
  2181         -    RtreeDValue diff =  
  2182         -      cellGrowth(pRtree, pBboxLeft, pNext) - 
  2183         -      cellGrowth(pRtree, pBboxRight, pNext)
  2184         -    ;
  2185         -    if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
  2186         -     || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
  2187         -    ){
  2188         -      nodeInsertCell(pRtree, pRight, pNext);
  2189         -      cellUnion(pRtree, pBboxRight, pNext);
  2190         -    }else{
  2191         -      nodeInsertCell(pRtree, pLeft, pNext);
  2192         -      cellUnion(pRtree, pBboxLeft, pNext);
  2193         -    }
  2194         -  }
  2195         -
  2196         -  sqlite3_free(aiUsed);
  2197         -  return SQLITE_OK;
  2198         -}
  2199         -#endif
  2200   2189   
  2201   2190   static int updateMapping(
  2202   2191     Rtree *pRtree, 
  2203   2192     i64 iRowid, 
  2204   2193     RtreeNode *pNode, 
  2205   2194     int iHeight
  2206   2195   ){
................................................................................
  2270   2259       rc = SQLITE_NOMEM;
  2271   2260       goto splitnode_out;
  2272   2261     }
  2273   2262   
  2274   2263     memset(pLeft->zData, 0, pRtree->iNodeSize);
  2275   2264     memset(pRight->zData, 0, pRtree->iNodeSize);
  2276   2265   
  2277         -  rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
         2266  +  rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
         2267  +                         &leftbbox, &rightbbox);
  2278   2268     if( rc!=SQLITE_OK ){
  2279   2269       goto splitnode_out;
  2280   2270     }
  2281   2271   
  2282   2272     /* Ensure both child nodes have node numbers assigned to them by calling
  2283   2273     ** nodeWrite(). Node pRight always needs a node number, as it was created
  2284   2274     ** by nodeNew() above. But node pLeft sometimes already has a node number.
................................................................................
  2553   2543       }
  2554   2544     }
  2555   2545     for(iDim=0; iDim<pRtree->nDim; iDim++){
  2556   2546       aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2));
  2557   2547     }
  2558   2548   
  2559   2549     for(ii=0; ii<nCell; ii++){
  2560         -    aDistance[ii] = 0.0;
         2550  +    aDistance[ii] = RTREE_ZERO;
  2561   2551       for(iDim=0; iDim<pRtree->nDim; iDim++){
  2562   2552         RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) - 
  2563   2553                                  DCOORD(aCell[ii].aCoord[iDim*2]));
  2564   2554         aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
  2565   2555       }
  2566   2556     }
  2567   2557   
................................................................................
  2619   2609       if( pChild ){
  2620   2610         nodeRelease(pRtree, pChild->pParent);
  2621   2611         nodeReference(pNode);
  2622   2612         pChild->pParent = pNode;
  2623   2613       }
  2624   2614     }
  2625   2615     if( nodeInsertCell(pRtree, pNode, pCell) ){
  2626         -#if VARIANT_RSTARTREE_REINSERT
  2627   2616       if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
  2628   2617         rc = SplitNode(pRtree, pNode, pCell, iHeight);
  2629   2618       }else{
  2630   2619         pRtree->iReinsertHeight = iHeight;
  2631   2620         rc = Reinsert(pRtree, pNode, pCell, iHeight);
  2632   2621       }
  2633         -#else
  2634         -    rc = SplitNode(pRtree, pNode, pCell, iHeight);
  2635         -#endif
  2636   2622     }else{
  2637   2623       rc = AdjustTree(pRtree, pNode, pCell);
  2638   2624       if( rc==SQLITE_OK ){
  2639   2625         if( iHeight==0 ){
  2640   2626           rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
  2641   2627         }else{
  2642   2628           rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
................................................................................
  2698   2684     /* Obtain a reference to the root node to initialize Rtree.iDepth */
  2699   2685     rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  2700   2686   
  2701   2687     /* Obtain a reference to the leaf node that contains the entry 
  2702   2688     ** about to be deleted. 
  2703   2689     */
  2704   2690     if( rc==SQLITE_OK ){
  2705         -    rc = findLeafNode(pRtree, iDelete, &pLeaf);
         2691  +    rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
  2706   2692     }
  2707   2693   
  2708   2694     /* Delete the cell in question from the leaf node. */
  2709   2695     if( rc==SQLITE_OK ){
  2710   2696       int rc2;
  2711   2697       rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
  2712   2698       if( rc==SQLITE_OK ){
................................................................................
  3035   3021   
  3036   3022     pRtree->db = db;
  3037   3023   
  3038   3024     if( isCreate ){
  3039   3025       char *zCreate = sqlite3_mprintf(
  3040   3026   "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
  3041   3027   "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
  3042         -"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
         3028  +"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
         3029  +                                  " parentnode INTEGER);"
  3043   3030   "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
  3044   3031         zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
  3045   3032       );
  3046   3033       if( !zCreate ){
  3047   3034         return SQLITE_NOMEM;
  3048   3035       }
  3049   3036       rc = sqlite3_exec(db, zCreate, 0, 0, 0);
................................................................................
  3249   3236   }
  3250   3237   
  3251   3238   
  3252   3239   /*
  3253   3240   ** Implementation of a scalar function that decodes r-tree nodes to
  3254   3241   ** human readable strings. This can be used for debugging and analysis.
  3255   3242   **
  3256         -** The scalar function takes two arguments, a blob of data containing
  3257         -** an r-tree node, and the number of dimensions the r-tree indexes.
  3258         -** For a two-dimensional r-tree structure called "rt", to deserialize
  3259         -** all nodes, a statement like:
         3243  +** The scalar function takes two arguments: (1) the number of dimensions
         3244  +** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
         3245  +** an r-tree node.  For a two-dimensional r-tree structure called "rt", to
         3246  +** deserialize all nodes, a statement like:
  3260   3247   **
  3261   3248   **   SELECT rtreenode(2, data) FROM rt_node;
  3262   3249   **
  3263   3250   ** The human readable string takes the form of a Tcl list with one
  3264   3251   ** entry for each cell in the r-tree node. Each entry is itself a
  3265   3252   ** list, containing the 8-byte rowid/pageno followed by the 
  3266   3253   ** <num-dimension>*2 coordinates.
................................................................................
  3285   3272       int jj;
  3286   3273   
  3287   3274       nodeGetCell(&tree, &node, ii, &cell);
  3288   3275       sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
  3289   3276       nCell = (int)strlen(zCell);
  3290   3277       for(jj=0; jj<tree.nDim*2; jj++){
  3291   3278   #ifndef SQLITE_RTREE_INT_ONLY
  3292         -      sqlite3_snprintf(512-nCell,&zCell[nCell], " %f",
         3279  +      sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
  3293   3280                          (double)cell.aCoord[jj].f);
  3294   3281   #else
  3295   3282         sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
  3296   3283                          cell.aCoord[jj].i);
  3297   3284   #endif
  3298   3285         nCell = (int)strlen(zCell);
  3299   3286       }
................................................................................
  3306   3293         zText = sqlite3_mprintf("{%s}", zCell);
  3307   3294       }
  3308   3295     }
  3309   3296     
  3310   3297     sqlite3_result_text(ctx, zText, -1, sqlite3_free);
  3311   3298   }
  3312   3299   
         3300  +/* This routine implements an SQL function that returns the "depth" parameter
         3301  +** from the front of a blob that is an r-tree node.  For example:
         3302  +**
         3303  +**     SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
         3304  +**
         3305  +** The depth value is 0 for all nodes other than the root node, and the root
         3306  +** node always has nodeno=1, so the example above is the primary use for this
         3307  +** routine.  This routine is intended for testing and analysis only.
         3308  +*/
  3313   3309   static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
  3314   3310     UNUSED_PARAMETER(nArg);
  3315   3311     if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB 
  3316   3312      || sqlite3_value_bytes(apArg[0])<2
  3317   3313     ){
  3318   3314       sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); 
  3319   3315     }else{
................................................................................
  3348   3344       rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
  3349   3345     }
  3350   3346   
  3351   3347     return rc;
  3352   3348   }
  3353   3349   
  3354   3350   /*
  3355         -** A version of sqlite3_free() that can be used as a callback. This is used
  3356         -** in two places - as the destructor for the blob value returned by the
  3357         -** invocation of a geometry function, and as the destructor for the geometry
  3358         -** functions themselves.
         3351  +** This routine deletes the RtreeGeomCallback object that was attached
         3352  +** one of the SQL functions create by sqlite3_rtree_geometry_callback()
         3353  +** or sqlite3_rtree_query_callback().  In other words, this routine is the
         3354  +** destructor for an RtreeGeomCallback objecct.  This routine is called when
         3355  +** the corresponding SQL function is deleted.
  3359   3356   */
  3360         -static void doSqlite3Free(void *p){
         3357  +static void rtreeFreeCallback(void *p){
         3358  +  RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
         3359  +  if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
  3361   3360     sqlite3_free(p);
  3362   3361   }
  3363   3362   
  3364   3363   /*
  3365         -** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
  3366         -** scalar user function. This C function is the callback used for all such
  3367         -** registered SQL functions.
         3364  +** Each call to sqlite3_rtree_geometry_callback() or
         3365  +** sqlite3_rtree_query_callback() creates an ordinary SQLite
         3366  +** scalar function that is implemented by this routine.
         3367  +**
         3368  +** All this function does is construct an RtreeMatchArg object that
         3369  +** contains the geometry-checking callback routines and a list of
         3370  +** parameters to this function, then return that RtreeMatchArg object
         3371  +** as a BLOB.
  3368   3372   **
  3369         -** The scalar user functions return a blob that is interpreted by r-tree
  3370         -** table MATCH operators.
         3373  +** The R-Tree MATCH operator will read the returned BLOB, deserialize
         3374  +** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
         3375  +** out which elements of the R-Tree should be returned by the query.
  3371   3376   */
  3372   3377   static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
  3373   3378     RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
  3374   3379     RtreeMatchArg *pBlob;
  3375   3380     int nBlob;
  3376   3381   
  3377   3382     nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue);
  3378   3383     pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
  3379   3384     if( !pBlob ){
  3380   3385       sqlite3_result_error_nomem(ctx);
  3381   3386     }else{
  3382   3387       int i;
  3383   3388       pBlob->magic = RTREE_GEOMETRY_MAGIC;
  3384         -    pBlob->xGeom = pGeomCtx->xGeom;
  3385         -    pBlob->pContext = pGeomCtx->pContext;
         3389  +    pBlob->cb = pGeomCtx[0];
  3386   3390       pBlob->nParam = nArg;
  3387   3391       for(i=0; i<nArg; i++){
  3388   3392   #ifdef SQLITE_RTREE_INT_ONLY
  3389   3393         pBlob->aParam[i] = sqlite3_value_int64(aArg[i]);
  3390   3394   #else
  3391   3395         pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
  3392   3396   #endif
  3393   3397       }
  3394         -    sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
         3398  +    sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free);
  3395   3399     }
  3396   3400   }
  3397   3401   
  3398   3402   /*
  3399   3403   ** Register a new geometry function for use with the r-tree MATCH operator.
  3400   3404   */
  3401   3405   int sqlite3_rtree_geometry_callback(
  3402         -  sqlite3 *db,
  3403         -  const char *zGeom,
  3404         -  int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue *, int *),
  3405         -  void *pContext
         3406  +  sqlite3 *db,                  /* Register SQL function on this connection */
         3407  +  const char *zGeom,            /* Name of the new SQL function */
         3408  +  int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */
         3409  +  void *pContext                /* Extra data associated with the callback */
  3406   3410   ){
  3407   3411     RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
  3408   3412   
  3409   3413     /* Allocate and populate the context object. */
  3410   3414     pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
  3411   3415     if( !pGeomCtx ) return SQLITE_NOMEM;
  3412   3416     pGeomCtx->xGeom = xGeom;
         3417  +  pGeomCtx->xQueryFunc = 0;
         3418  +  pGeomCtx->xDestructor = 0;
  3413   3419     pGeomCtx->pContext = pContext;
  3414         -
  3415         -  /* Create the new user-function. Register a destructor function to delete
  3416         -  ** the context object when it is no longer required.  */
  3417   3420     return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
  3418         -      (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
         3421  +      (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
         3422  +  );
         3423  +}
         3424  +
         3425  +/*
         3426  +** Register a new 2nd-generation geometry function for use with the
         3427  +** r-tree MATCH operator.
         3428  +*/
         3429  +int sqlite3_rtree_query_callback(
         3430  +  sqlite3 *db,                 /* Register SQL function on this connection */
         3431  +  const char *zQueryFunc,      /* Name of new SQL function */
         3432  +  int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */
         3433  +  void *pContext,              /* Extra data passed into the callback */
         3434  +  void (*xDestructor)(void*)   /* Destructor for the extra data */
         3435  +){
         3436  +  RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
         3437  +
         3438  +  /* Allocate and populate the context object. */
         3439  +  pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
         3440  +  if( !pGeomCtx ) return SQLITE_NOMEM;
         3441  +  pGeomCtx->xGeom = 0;
         3442  +  pGeomCtx->xQueryFunc = xQueryFunc;
         3443  +  pGeomCtx->xDestructor = xDestructor;
         3444  +  pGeomCtx->pContext = pContext;
         3445  +  return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, 
         3446  +      (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
  3419   3447     );
  3420   3448   }
  3421   3449   
  3422   3450   #if !SQLITE_CORE
  3423   3451   #ifdef _WIN32
  3424   3452   __declspec(dllexport)
  3425   3453   #endif

Changes to ext/rtree/rtree1.test.

   116    116     }
   117    117     return $out
   118    118   }
   119    119   
   120    120   # Test that it is possible to open an existing database that contains
   121    121   # r-tree tables.
   122    122   #
   123         -do_test rtree-1.4.1 {
   124         -  execsql {
   125         -    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
   126         -    INSERT INTO t1 VALUES(1, 5.0, 10.0);
   127         -    INSERT INTO t1 VALUES(2, 15.0, 20.0);
   128         -  }
          123  +do_execsql_test rtree-1.4.1a {
          124  +  CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
          125  +  INSERT INTO t1 VALUES(1, 5.0, 10.0);
          126  +  SELECT substr(hex(data),1,40) FROM t1_node;
          127  +} {00000001000000000000000140A0000041200000}
          128  +do_execsql_test rtree-1.4.1b {
          129  +  INSERT INTO t1 VALUES(2, 15.0, 20.0);
   129    130   } {}
   130    131   do_test rtree-1.4.2 {
   131    132     db close
   132    133     sqlite3 db test.db
   133    134     execsql_intout { SELECT * FROM t1 ORDER BY ii }
   134    135   } {1 5 10 2 15 20}
   135    136   do_test rtree-1.4.3 {
................................................................................
   431    432     }
   432    433   } {2}
   433    434   
   434    435   #-------------------------------------------------------------------------
   435    436   # Test on-conflict clause handling.
   436    437   #
   437    438   db_delete_and_reopen
   438         -do_execsql_test 12.0 {
          439  +do_execsql_test 12.0.1 {
   439    440     CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
   440    441     INSERT INTO t1 VALUES(1,   1, 2, 3, 4);
          442  +  SELECT substr(hex(data),1,56) FROM t1_node;
          443  +} {00000001000000000000000100000001000000020000000300000004}
          444  +do_execsql_test 12.0.2 {
   441    445     INSERT INTO t1 VALUES(2,   2, 3, 4, 5);
   442    446     INSERT INTO t1 VALUES(3,   3, 4, 5, 6);
   443    447   
   444    448     CREATE TABLE source(idx, x1, x2, y1, y2);
   445    449     INSERT INTO source VALUES(5, 8, 8, 8, 8);
   446    450     INSERT INTO source VALUES(2, 7, 7, 7, 7);
   447         -  
   448    451   }
   449    452   db_save_and_close
   450    453   foreach {tn sql_template testdata} {
   451    454     1    "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" {
   452    455       ROLLBACK 0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
   453    456       ABORT    0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
   454    457       IGNORE   0 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}

Changes to ext/rtree/rtree6.test.

    53     53       CREATE TABLE t2(k INTEGER PRIMARY KEY, v);
    54     54       CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
    55     55     }
    56     56   } {}
    57     57   
    58     58   do_test rtree6-1.2 {
    59     59     rtree_strategy {SELECT * FROM t1 WHERE x1>10}
    60         -} {Ea}
           60  +} {E0}
    61     61   
    62     62   do_test rtree6-1.3 {
    63     63     rtree_strategy {SELECT * FROM t1 WHERE x1<10}
    64         -} {Ca}
           64  +} {C0}
    65     65   
    66     66   do_test rtree6-1.4 {
    67     67     rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
    68         -} {Ca}
           68  +} {C0}
    69     69   
    70     70   do_test rtree6-1.5 {
    71     71     rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
    72         -} {Ca}
           72  +} {C0}
    73     73   
    74     74   do_eqp_test rtree6.2.1 {
    75     75     SELECT * FROM t1,t2 WHERE k=+ii AND x1<10
    76     76   } {
    77         -  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:Ca} 
           77  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
    78     78     0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
    79     79   }
    80     80   
    81     81   do_eqp_test rtree6.2.2 {
    82     82     SELECT * FROM t1,t2 WHERE k=ii AND x1<10
    83     83   } {
    84         -  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:Ca} 
           84  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
    85     85     0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
    86     86   }
    87     87   
    88     88   do_eqp_test rtree6.2.3 {
    89     89     SELECT * FROM t1,t2 WHERE k=ii
    90     90   } {
    91     91     0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
    92     92     0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
    93     93   }
    94     94   
    95     95   do_eqp_test rtree6.2.4 {
    96     96     SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
    97     97   } {
    98         -  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:CaEb} 
           98  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
    99     99     0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
   100    100   }
   101    101   
   102    102   do_eqp_test rtree6.2.5 {
   103    103     SELECT * FROM t1,t2 WHERE k=ii AND x1<v
   104    104   } {
   105    105     0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
................................................................................
   122    122     rtree_strategy {
   123    123       SELECT * FROM t3 WHERE 
   124    124         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   125    125         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   126    126         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   127    127         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 
   128    128     }
   129         -} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}
          129  +} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
   130    130   do_test rtree6.3.3 {
   131    131     rtree_strategy {
   132    132       SELECT * FROM t3 WHERE 
   133    133         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   134    134         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   135    135         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   136    136         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   137    137         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
   138    138         x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5
   139    139     }
   140         -} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}
          140  +} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
   141    141   
   142    142   do_execsql_test rtree6-3.4 {
   143    143     SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1
   144    144   } {}
   145    145   do_execsql_test rtree6-3.5 {
   146    146     SELECT * FROM t3 WHERE 
   147    147       x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 

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

Changes to ext/rtree/rtreeC.test.

    25     25   }
    26     26   
    27     27   do_eqp_test 1.1 {
    28     28     SELECT * FROM r_tree, t 
    29     29     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
    30     30   } {
    31     31     0 0 1 {SCAN TABLE t}
    32         -  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
           32  +  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
    33     33   }
    34     34   
    35     35   do_eqp_test 1.2 {
    36     36     SELECT * FROM t, r_tree
    37     37     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
    38     38   } {
    39     39     0 0 0 {SCAN TABLE t}
    40         -  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
           40  +  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
    41     41   }
    42     42   
    43     43   do_eqp_test 1.3 {
    44     44     SELECT * FROM t, r_tree
    45     45     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
    46     46   } {
    47     47     0 0 0 {SCAN TABLE t}
    48         -  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
           48  +  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
    49     49   }
    50     50   
    51     51   do_eqp_test 1.5 {
    52     52     SELECT * FROM t, r_tree
    53     53   } {
    54     54     0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
    55     55     0 1 0 {SCAN TABLE t} 
................................................................................
    78     78   sqlite3 db test.db
    79     79   
    80     80   do_eqp_test 2.1 {
    81     81     SELECT * FROM r_tree, t 
    82     82     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
    83     83   } {
    84     84     0 0 1 {SCAN TABLE t}
    85         -  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
           85  +  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
    86     86   }
    87     87   
    88     88   do_eqp_test 2.2 {
    89     89     SELECT * FROM t, r_tree
    90     90     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
    91     91   } {
    92     92     0 0 0 {SCAN TABLE t}
    93         -  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
           93  +  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
    94     94   }
    95     95   
    96     96   do_eqp_test 2.3 {
    97     97     SELECT * FROM t, r_tree
    98     98     WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
    99     99   } {
   100    100     0 0 0 {SCAN TABLE t}
   101         -  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
          101  +  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
   102    102   }
   103    103   
   104    104   do_eqp_test 2.5 {
   105    105     SELECT * FROM t, r_tree
   106    106   } {
   107    107     0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
   108    108     0 1 0 {SCAN TABLE t} 
................................................................................
   267    267       execsql { SELECT * FROM rt }
   268    268     } {1 2.0 3.0}
   269    269     db close
   270    270   }
   271    271   
   272    272   
   273    273   finish_test
   274         -

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 rt1 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 rt1 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 rt1 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 rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
           49  +} {}
           50  +
           51  +# Queries against each of the three clusters */
           52  +do_execsql_test rtreeE-1.1 {
           53  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
           54  +} {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}
           55  +do_execsql_test rtreeE-1.2 {
           56  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id;
           57  +} {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}
           58  +do_execsql_test rtreeE-1.3 {
           59  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id;
           60  +} {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}
           61  +
           62  +# The Qcircle geometry function gives a lower score to larger leaf-nodes.
           63  +# This causes the 200s to sort before the 100s and the 0s to sort before
           64  +# last.
           65  +#
           66  +do_execsql_test rtreeE-1.4 {
           67  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,3) AND id%100==0
           68  +} {200 100 0}
           69  +
           70  +# Exclude odd rowids on a depth-first search
           71  +do_execsql_test rtreeE-1.5 {
           72  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,4) ORDER BY +id
           73  +} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
           74  +
           75  +# Exclude odd rowids on a breadth-first search.
           76  +do_execsql_test rtreeE-1.6 {
           77  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,5) ORDER BY +id
           78  +} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
           79  +
           80  +# Construct a large 2-D RTree with thousands of random entries.
           81  +#
           82  +do_test rtreeE-2.1 {
           83  +  db eval {
           84  +    CREATE TABLE t2(id,x0,x1,y0,y1);
           85  +    CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
           86  +    BEGIN;
           87  +  }
           88  +  expr srand(0)
           89  +  for {set i 1} {$i<=10000} {incr i} {
           90  +    set dx [expr {int(rand()*40)+1}]
           91  +    set dy [expr {int(rand()*40)+1}]
           92  +    set x0 [expr {int(rand()*(10000 - $dx))}]
           93  +    set x1 [expr {$x0+$dx}]
           94  +    set y0 [expr {int(rand()*(10000 - $dy))}]
           95  +    set y1 [expr {$y0+$dy}]
           96  +    set id [expr {$i+10000}]
           97  +    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
           98  +  }
           99  +  db eval {
          100  +    INSERT INTO rt2 SELECT * FROM t2;
          101  +    COMMIT;
          102  +  }
          103  +} {}
          104  +
          105  +for {set i 1} {$i<=200} {incr i} {
          106  +  set dx [expr {int(rand()*100)}]
          107  +  set dy [expr {int(rand()*100)}]
          108  +  set x0 [expr {int(rand()*(10000 - $dx))}]
          109  +  set x1 [expr {$x0+$dx}]
          110  +  set y0 [expr {int(rand()*(10000 - $dy))}]
          111  +  set y1 [expr {$y0+$dy}]
          112  +  set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}]
          113  +  do_execsql_test rtreeE-2.2.$i {
          114  +    SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id
          115  +  } $ans
          116  +}
          117  +
          118  +# Run query that have very deep priority queues
          119  +#
          120  +set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}]
          121  +do_execsql_test rtreeE-2.3 {
          122  +  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id
          123  +} $ans
          124  +set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}]
          125  +do_execsql_test rtreeE-2.4 {
          126  +  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id
          127  +} $ans
          128  +
          129  +finish_test

Changes to ext/rtree/sqlite3rtree.h.

    17     17   #include <sqlite3.h>
    18     18   
    19     19   #ifdef __cplusplus
    20     20   extern "C" {
    21     21   #endif
    22     22   
    23     23   typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
           24  +typedef struct sqlite3_rtree_query_info sqlite3_rtree_query_info;
           25  +
           26  +/* The double-precision datatype used by RTree depends on the
           27  +** SQLITE_RTREE_INT_ONLY compile-time option.
           28  +*/
           29  +#ifdef SQLITE_RTREE_INT_ONLY
           30  +  typedef sqlite3_int64 sqlite3_rtree_dbl;
           31  +#else
           32  +  typedef double sqlite3_rtree_dbl;
           33  +#endif
    24     34   
    25     35   /*
    26     36   ** Register a geometry callback named zGeom that can be used as part of an
    27     37   ** R-Tree geometry query as follows:
    28     38   **
    29     39   **   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...)
    30     40   */
    31     41   int sqlite3_rtree_geometry_callback(
    32     42     sqlite3 *db,
    33     43     const char *zGeom,
    34         -#ifdef SQLITE_RTREE_INT_ONLY
    35         -  int (*xGeom)(sqlite3_rtree_geometry*, int n, sqlite3_int64 *a, int *pRes),
    36         -#else
    37         -  int (*xGeom)(sqlite3_rtree_geometry*, int n, double *a, int *pRes),
    38         -#endif
           44  +  int (*xGeom)(sqlite3_rtree_geometry*, int, sqlite3_rtree_dbl*,int*),
    39     45     void *pContext
    40     46   );
    41     47   
    42     48   
    43     49   /*
    44     50   ** A pointer to a structure of the following type is passed as the first
    45     51   ** argument to callbacks registered using rtree_geometry_callback().
    46     52   */
    47     53   struct sqlite3_rtree_geometry {
    48     54     void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
    49     55     int nParam;                     /* Size of array aParam[] */
    50         -  double *aParam;                 /* Parameters passed to SQL geom function */
           56  +  sqlite3_rtree_dbl *aParam;      /* Parameters passed to SQL geom function */
    51     57     void *pUser;                    /* Callback implementation user data */
    52     58     void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
    53     59   };
    54     60   
           61  +/*
           62  +** Register a 2nd-generation geometry callback named zScore that can be 
           63  +** used as part of an R-Tree geometry query as follows:
           64  +**
           65  +**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zQueryFunc(... params ...)
           66  +*/
           67  +int sqlite3_rtree_query_callback(
           68  +  sqlite3 *db,
           69  +  const char *zQueryFunc,
           70  +  int (*xQueryFunc)(sqlite3_rtree_query_info*),
           71  +  void *pContext,
           72  +  void (*xDestructor)(void*)
           73  +);
           74  +
           75  +
           76  +/*
           77  +** A pointer to a structure of the following type is passed as the 
           78  +** argument to scored geometry callback registered using
           79  +** sqlite3_rtree_query_callback().
           80  +**
           81  +** Note that the first 5 fields of this structure are identical to
           82  +** sqlite3_rtree_geometry.  This structure is a subclass of
           83  +** sqlite3_rtree_geometry.
           84  +*/
           85  +struct sqlite3_rtree_query_info {
           86  +  void *pContext;                   /* pContext from when function registered */
           87  +  int nParam;                       /* Number of function parameters */
           88  +  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
           89  +  void *pUser;                      /* callback can use this, if desired */
           90  +  void (*xDelUser)(void*);          /* function to free pUser */
           91  +  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
           92  +  unsigned int *anQueue;            /* Number of pending entries in the queue */
           93  +  int nCoord;                       /* Number of coordinates */
           94  +  int iLevel;                       /* Level of current node or entry */
           95  +  int mxLevel;                      /* The largest iLevel value in the tree */
           96  +  sqlite3_int64 iRowid;             /* Rowid for current entry */
           97  +  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
           98  +  int eParentWithin;                /* Visibility of parent node */
           99  +  int eWithin;                      /* OUT: Visiblity */
          100  +  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
          101  +};
          102  +
          103  +/*
          104  +** Allowed values for sqlite3_rtree_query.eWithin and .eParentWithin.
          105  +*/
          106  +#define NOT_WITHIN       0   /* Object completely outside of query region */
          107  +#define PARTLY_WITHIN    1   /* Object partially overlaps query region */
          108  +#define FULLY_WITHIN     2   /* Object fully contained within query region */
          109  +
    55    110   
    56    111   #ifdef __cplusplus
    57    112   }  /* end of the 'extern "C"' block */
    58    113   #endif
    59    114   
    60    115   #endif  /* ifndef _SQLITE3RTREE_H_ */

Changes to main.mk.

   479    479   parse.c:	$(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk
   480    480   	cp $(TOP)/src/parse.y .
   481    481   	rm -f parse.h
   482    482   	./lemon $(OPTS) parse.y
   483    483   	mv parse.h parse.h.temp
   484    484   	$(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h
   485    485   
   486         -sqlite3.h:	$(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION
          486  +sqlite3.h:	$(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h
   487    487   	tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h
   488    488   
   489    489   keywordhash.h:	$(TOP)/tool/mkkeywordhash.c
   490    490   	$(BCC) -o mkkeywordhash $(OPTS) $(TOP)/tool/mkkeywordhash.c
   491    491   	./mkkeywordhash >keywordhash.h
   492    492   
   493    493   

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;
           39  +  int eScoreType;
    38     40   };
    39     41   
    40     42   /*
    41     43   ** Destructor function for Circle objects allocated by circle_geom().
    42     44   */
    43     45   static void circle_del(void *p){
    44     46     sqlite3_free(p);
................................................................................
    46     48   
    47     49   /*
    48     50   ** Implementation of "circle" r-tree geometry callback.
    49     51   */
    50     52   static int circle_geom(
    51     53     sqlite3_rtree_geometry *p,
    52     54     int nCoord, 
    53         -#ifdef SQLITE_RTREE_INT_ONLY
    54         -  sqlite3_int64 *aCoord,
    55         -#else
    56         -  double *aCoord, 
    57         -#endif
           55  +  sqlite3_rtree_dbl *aCoord,
    58     56     int *pRes
    59     57   ){
    60     58     int i;                          /* Iterator variable */
    61     59     Circle *pCircle;                /* Structure defining circular region */
    62     60     double xmin, xmax;              /* X dimensions of box being tested */
    63     61     double ymin, ymax;              /* X dimensions of box being tested */
    64     62   
    65         -  if( p->pUser==0 ){
           63  +  xmin = aCoord[0];
           64  +  xmax = aCoord[1];
           65  +  ymin = aCoord[2];
           66  +  ymax = aCoord[3];
           67  +  pCircle = (Circle *)p->pUser;
           68  +  if( pCircle==0 ){
    66     69       /* If pUser is still 0, then the parameter values have not been tested
    67     70       ** for correctness or stored into a Circle structure yet. Do this now. */
    68     71   
    69     72       /* This geometry callback is for use with a 2-dimensional r-tree table.
    70     73       ** Return an error if the table does not have exactly 2 dimensions. */
    71     74       if( nCoord!=4 ) return SQLITE_ERROR;
    72     75   
................................................................................
   104    107       pCircle->aBox[0].xmax = pCircle->centerx;
   105    108       pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
   106    109       pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
   107    110       pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
   108    111       pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
   109    112       pCircle->aBox[1].ymin = pCircle->centery;
   110    113       pCircle->aBox[1].ymax = pCircle->centery;
          114  +    pCircle->mxArea = (xmax - xmin)*(ymax - ymin) + 1.0;
   111    115     }
   112    116   
   113         -  pCircle = (Circle *)p->pUser;
   114         -  xmin = aCoord[0];
   115         -  xmax = aCoord[1];
   116         -  ymin = aCoord[2];
   117         -  ymax = aCoord[3];
   118         -
   119    117     /* Check if any of the 4 corners of the bounding-box being tested lie 
   120    118     ** inside the circular region. If they do, then the bounding-box does
   121    119     ** intersect the region of interest. Set the output variable to true and
   122    120     ** return SQLITE_OK in this case. */
   123    121     for(i=0; i<4; i++){
   124    122       double x = (i&0x01) ? xmax : xmin;
   125    123       double y = (i&0x02) ? ymax : ymin;
................................................................................
   149    147     }
   150    148   
   151    149     /* The specified bounding box does not intersect the circular region. Set
   152    150     ** the output variable to zero and return SQLITE_OK. */
   153    151     *pRes = 0;
   154    152     return SQLITE_OK;
   155    153   }
          154  +
          155  +/*
          156  +** Implementation of "circle" r-tree geometry callback using the 
          157  +** 2nd-generation interface that allows scoring.
          158  +*/
          159  +static int circle_query_func(sqlite3_rtree_query_info *p){
          160  +  int i;                          /* Iterator variable */
          161  +  Circle *pCircle;                /* Structure defining circular region */
          162  +  double xmin, xmax;              /* X dimensions of box being tested */
          163  +  double ymin, ymax;              /* X dimensions of box being tested */
          164  +  int nWithin = 0;                /* Number of corners inside the circle */
          165  +
          166  +  xmin = p->aCoord[0];
          167  +  xmax = p->aCoord[1];
          168  +  ymin = p->aCoord[2];
          169  +  ymax = p->aCoord[3];
          170  +  pCircle = (Circle *)p->pUser;
          171  +  if( pCircle==0 ){
          172  +    /* If pUser is still 0, then the parameter values have not been tested
          173  +    ** for correctness or stored into a Circle structure yet. Do this now. */
          174  +
          175  +    /* This geometry callback is for use with a 2-dimensional r-tree table.
          176  +    ** Return an error if the table does not have exactly 2 dimensions. */
          177  +    if( p->nCoord!=4 ) return SQLITE_ERROR;
          178  +
          179  +    /* Test that the correct number of parameters (4) have been supplied,
          180  +    ** and that the parameters are in range (that the radius of the circle 
          181  +    ** radius is greater than zero). */
          182  +    if( p->nParam!=4 || p->aParam[2]<0.0 ) return SQLITE_ERROR;
          183  +
          184  +    /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
          185  +    ** if the allocation fails. */
          186  +    pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
          187  +    if( !pCircle ) return SQLITE_NOMEM;
          188  +    p->xDelUser = circle_del;
          189  +
          190  +    /* Record the center and radius of the circular region. One way that
          191  +    ** tested bounding boxes that intersect the circular region are detected
          192  +    ** is by testing if each corner of the bounding box lies within radius
          193  +    ** units of the center of the circle. */
          194  +    pCircle->centerx = p->aParam[0];
          195  +    pCircle->centery = p->aParam[1];
          196  +    pCircle->radius = p->aParam[2];
          197  +    pCircle->eScoreType = (int)p->aParam[3];
          198  +
          199  +    /* Define two bounding box regions. The first, aBox[0], extends to
          200  +    ** infinity in the X dimension. It covers the same range of the Y dimension
          201  +    ** as the circular region. The second, aBox[1], extends to infinity in
          202  +    ** the Y dimension and is constrained to the range of the circle in the
          203  +    ** X dimension.
          204  +    **
          205  +    ** Then imagine each box is split in half along its short axis by a line
          206  +    ** that intersects the center of the circular region. A bounding box
          207  +    ** being tested can be said to intersect the circular region if it contains
          208  +    ** points from each half of either of the two infinite bounding boxes.
          209  +    */
          210  +    pCircle->aBox[0].xmin = pCircle->centerx;
          211  +    pCircle->aBox[0].xmax = pCircle->centerx;
          212  +    pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
          213  +    pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
          214  +    pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
          215  +    pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
          216  +    pCircle->aBox[1].ymin = pCircle->centery;
          217  +    pCircle->aBox[1].ymax = pCircle->centery;
          218  +    pCircle->mxArea = 200.0*200.0;
          219  +  }
          220  +
          221  +  /* Check if any of the 4 corners of the bounding-box being tested lie 
          222  +  ** inside the circular region. If they do, then the bounding-box does
          223  +  ** intersect the region of interest. Set the output variable to true and
          224  +  ** return SQLITE_OK in this case. */
          225  +  for(i=0; i<4; i++){
          226  +    double x = (i&0x01) ? xmax : xmin;
          227  +    double y = (i&0x02) ? ymax : ymin;
          228  +    double d2;
          229  +    
          230  +    d2  = (x-pCircle->centerx)*(x-pCircle->centerx);
          231  +    d2 += (y-pCircle->centery)*(y-pCircle->centery);
          232  +    if( d2<(pCircle->radius*pCircle->radius) ) nWithin++;
          233  +  }
          234  +
          235  +  /* Check if the bounding box covers any other part of the circular region.
          236  +  ** See comments above for a description of how this test works. If it does
          237  +  ** cover part of the circular region, set the output variable to true
          238  +  ** and return SQLITE_OK. */
          239  +  if( nWithin==0 ){
          240  +    for(i=0; i<2; i++){
          241  +      if( xmin<=pCircle->aBox[i].xmin 
          242  +       && xmax>=pCircle->aBox[i].xmax 
          243  +       && ymin<=pCircle->aBox[i].ymin 
          244  +       && ymax>=pCircle->aBox[i].ymax 
          245  +      ){
          246  +        nWithin = 1;
          247  +        break;
          248  +      }
          249  +    }
          250  +  }
          251  +
          252  +  if( pCircle->eScoreType==1 ){
          253  +    /* Depth first search */
          254  +    p->rScore = p->iLevel;
          255  +  }else if( pCircle->eScoreType==2 ){
          256  +    /* Breadth first search */
          257  +    p->rScore = 100 - p->iLevel;
          258  +  }else if( pCircle->eScoreType==3 ){
          259  +    /* Depth-first search, except sort the leaf nodes by area with
          260  +    ** the largest area first */
          261  +    if( p->iLevel==1 ){
          262  +      p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
          263  +      if( p->rScore<0.01 ) p->rScore = 0.01;
          264  +    }else{
          265  +      p->rScore = 0.0;
          266  +    }
          267  +  }else if( pCircle->eScoreType==4 ){
          268  +    /* Depth-first search, except exclude odd rowids */
          269  +    p->rScore = p->iLevel;
          270  +    if( p->iRowid&1 ) nWithin = 0;
          271  +  }else{
          272  +    /* Breadth-first search, except exclude odd rowids */
          273  +    p->rScore = 100 - p->iLevel;
          274  +    if( p->iRowid&1 ) nWithin = 0;
          275  +  }
          276  +  if( nWithin==0 ){
          277  +    p->eWithin = NOT_WITHIN;
          278  +  }else if( nWithin>=4 ){
          279  +    p->eWithin = FULLY_WITHIN;
          280  +  }else{
          281  +    p->eWithin = PARTLY_WITHIN;
          282  +  }
          283  +  return SQLITE_OK;
          284  +}
          285  +/*
          286  +** Implementation of "breadthfirstsearch" r-tree geometry callback using the 
          287  +** 2nd-generation interface that allows scoring.
          288  +**
          289  +**     ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
          290  +**
          291  +** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
          292  +*/
          293  +static int bfs_query_func(sqlite3_rtree_query_info *p){
          294  +  double x0,x1,y0,y1;        /* Dimensions of box being tested */
          295  +  double bx0,bx1,by0,by1;    /* Boundary of the query function */
          296  +
          297  +  if( p->nParam!=4 ) return SQLITE_ERROR;
          298  +  x0 = p->aCoord[0];
          299  +  x1 = p->aCoord[1];
          300  +  y0 = p->aCoord[2];
          301  +  y1 = p->aCoord[3];
          302  +  bx0 = p->aParam[0];
          303  +  bx1 = p->aParam[1];
          304  +  by0 = p->aParam[2];
          305  +  by1 = p->aParam[3];
          306  +  p->rScore = 100 - p->iLevel;
          307  +  if( p->eParentWithin==FULLY_WITHIN ){
          308  +    p->eWithin = FULLY_WITHIN;
          309  +  }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){
          310  +    p->eWithin = FULLY_WITHIN;
          311  +  }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){
          312  +    p->eWithin = PARTLY_WITHIN;
          313  +  }else{
          314  +    p->eWithin = NOT_WITHIN;
          315  +  }
          316  +  return SQLITE_OK;
          317  +}
   156    318   
   157    319   /* END of implementation of "circle" geometry callback.
   158    320   **************************************************************************
   159    321   *************************************************************************/
   160    322   
   161    323   #include <assert.h>
   162    324   #include "tcl.h"
................................................................................
   190    352   **   cube(x, y, z, width, height, depth)
   191    353   **
   192    354   ** The width, height and depth parameters must all be greater than zero.
   193    355   */
   194    356   static int cube_geom(
   195    357     sqlite3_rtree_geometry *p,
   196    358     int nCoord,
   197         -#ifdef SQLITE_RTREE_INT_ONLY
   198         -  sqlite3_int64 *aCoord, 
   199         -#else
   200         -  double *aCoord, 
   201         -#endif
          359  +  sqlite3_rtree_dbl *aCoord,
   202    360     int *piRes
   203    361   ){
   204    362     Cube *pCube = (Cube *)p->pUser;
   205    363   
   206    364     assert( p->pContext==(void *)&gHere );
   207    365   
   208    366     if( pCube==0 ){
................................................................................
   289    447   
   290    448     if( objc!=2 ){
   291    449       Tcl_WrongNumArgs(interp, 1, objv, "DB");
   292    450       return TCL_ERROR;
   293    451     }
   294    452     if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
   295    453     rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);
          454  +  if( rc==SQLITE_OK ){
          455  +    rc = sqlite3_rtree_query_callback(db, "Qcircle",
          456  +                                      circle_query_func, 0, 0);
          457  +  }
          458  +  if( rc==SQLITE_OK ){
          459  +    rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
          460  +                                      bfs_query_func, 0, 0);
          461  +  }
   296    462     Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
   297    463   #endif
   298    464     return TCL_OK;
   299    465   }
   300    466   
   301    467   int Sqlitetestrtree_Init(Tcl_Interp *interp){
   302    468     Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);
   303    469     Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);
   304    470     return TCL_OK;
   305    471   }

Changes to src/test_vfstrace.c.

   674    674     const char *zPath, 
   675    675     int flags, 
   676    676     int *pResOut
   677    677   ){
   678    678     vfstrace_info *pInfo = (vfstrace_info*)pVfs->pAppData;
   679    679     sqlite3_vfs *pRoot = pInfo->pRootVfs;
   680    680     int rc;
   681         -  vfstrace_printf(pInfo, "%s.xDelete(\"%s\",%d)",
          681  +  vfstrace_printf(pInfo, "%s.xAccess(\"%s\",%d)",
   682    682                     pInfo->zVfsName, zPath, flags);
   683    683     rc = pRoot->xAccess(pRoot, zPath, flags, pResOut);
   684    684     vfstrace_print_errcode(pInfo, " -> %s", rc);
   685    685     vfstrace_printf(pInfo, ", out=%d\n", *pResOut);
   686    686     return rc;
   687    687   }
   688    688   

Added test/show_speedtest1_rtree.tcl.

            1  +#!/usr/bin/tclsh
            2  +#
            3  +# This script displays the field of rectangles used by --testset rtree
            4  +# of speedtest1.  Run this script as follows:
            5  +#
            6  +#      rm test.db
            7  +#      ./speedtest1 --testset rtree --size 25 test.db
            8  +#      sqlite3 --separator ' ' test.db 'SELECT * FROM rt1' >data.txt
            9  +#      wish show_speedtest1_rtree.tcl
           10  +#
           11  +# The filename "data.txt" is hard coded into this script and so that name
           12  +# must be used on lines 3 and 4 above.  Elsewhere, different filenames can
           13  +# be used.  The --size N parameter can be adjusted as desired.
           14  +#
           15  +package require Tk
           16  +set f [open data.txt rb]
           17  +set data [read $f]
           18  +close $f
           19  +canvas .c
           20  +frame .b
           21  +button .b.b1 -text X-Y -command refill-xy
           22  +button .b.b2 -text X-Z -command refill-xz
           23  +button .b.b3 -text Y-Z -command refill-yz
           24  +pack .b.b1 .b.b2 .b.b3 -side left
           25  +pack .c -side top -fill both -expand 1
           26  +pack .b -side top
           27  +proc resize_canvas_to_fit {} {
           28  +  foreach {x0 y0 x1 y1} [.c bbox all] break
           29  +  set w [expr {$x1-$x0}]
           30  +  set h [expr {$y1-$y0}]
           31  +  .c config -width $w -height $h
           32  +}
           33  +proc refill-xy {} {
           34  +  .c delete all
           35  +  foreach {id x0 x1 y0 y1 z0 z1} $::data {
           36  +    .c create rectangle $x0 $y0 $x1 $y1
           37  +  }
           38  +  .c scale all 0 0 0.05 0.05
           39  +  resize_canvas_to_fit
           40  +}
           41  +proc refill-xz {} {
           42  +  .c delete all
           43  +  foreach {id x0 x1 y0 y1 z0 z1} $::data {
           44  +    .c create rectangle $x0 $z0 $x1 $z1
           45  +  }
           46  +  .c scale all 0 0 0.05 0.05
           47  +  resize_canvas_to_fit
           48  +}
           49  +proc refill-yz {} {
           50  +  .c delete all
           51  +  foreach {id x0 x1 y0 y1 z0 z1} $::data {
           52  +    .c create rectangle $y0 $z0 $y1 $z1
           53  +  }
           54  +  .c scale all 0 0 0.05 0.05
           55  +  resize_canvas_to_fit
           56  +}
           57  +refill-xy

Changes to test/speedtest1.c.

    25     25     "  --sqlonly           No-op.  Only show the SQL that would have been run.\n"
    26     26     "  --size N            Relative test size.  Default=100\n"
    27     27     "  --stats             Show statistics at the end\n"
    28     28     "  --testset T         Run test-set T\n"
    29     29     "  --trace             Turn on SQL tracing\n"
    30     30     "  --utf16be           Set text encoding to UTF-16BE\n"
    31     31     "  --utf16le           Set text encoding to UTF-16LE\n"
           32  +  "  --verify            Run additional verification steps.\n"
    32     33     "  --without-rowid     Use WITHOUT ROWID where appropriate\n"
    33     34   ;
    34     35   
    35     36   
    36     37   #include "sqlite3.h"
    37     38   #include <assert.h>
    38     39   #include <stdio.h>
................................................................................
    47     48     sqlite3_stmt *pStmt;       /* Current SQL statement */
    48     49     sqlite3_int64 iStart;      /* Start-time for the current test */
    49     50     sqlite3_int64 iTotal;      /* Total time */
    50     51     int bWithoutRowid;         /* True for --without-rowid */
    51     52     int bReprepare;            /* True to reprepare the SQL on each rerun */
    52     53     int bSqlOnly;              /* True to print the SQL once only */
    53     54     int bExplain;              /* Print SQL with EXPLAIN prefix */
           55  +  int bVerify;               /* Try to verify that results are correct */
    54     56     int szTest;                /* Scale factor for test iterations */
    55     57     const char *zWR;           /* Might be WITHOUT ROWID */
    56     58     const char *zNN;           /* Might be NOT NULL */
    57     59     const char *zPK;           /* Might be UNIQUE or PRIMARY KEY */
    58     60     unsigned int x, y;         /* Pseudo-random number generator state */
    59     61     int nResult;               /* Size of the current result */
    60     62     char zResult[3000];        /* Text of the current result */
................................................................................
   926    928       ");",
   927    929       nElem, nElem
   928    930     );
   929    931     speedtest1_run();
   930    932     speedtest1_end_test();
   931    933   
   932    934   }
          935  +
          936  +/* Generate two numbers between 1 and mx.  The first number is less than
          937  +** the second.  Usually the numbers are near each other but can sometimes
          938  +** be far apart.
          939  +*/
          940  +static void twoCoords(
          941  +  int p1, int p2,                   /* Parameters adjusting sizes */
          942  +  unsigned mx,                      /* Range of 1..mx */
          943  +  unsigned *pX0, unsigned *pX1      /* OUT: write results here */
          944  +){
          945  +  unsigned d, x0, x1, span;
          946  +
          947  +  span = mx/100 + 1;
          948  +  if( speedtest1_random()%3==0 ) span *= p1;
          949  +  if( speedtest1_random()%p2==0 ) span = mx/2;
          950  +  d = speedtest1_random()%span + 1;
          951  +  x0 = speedtest1_random()%(mx-d) + 1;
          952  +  x1 = x0 + d;
          953  +  *pX0 = x0;
          954  +  *pX1 = x1;
          955  +}
          956  +
          957  +/* The following routine is an R-Tree geometry callback.  It returns
          958  +** true if the object overlaps a slice on the Y coordinate between the
          959  +** two values given as arguments.  In other words
          960  +**
          961  +**     SELECT count(*) FROM rt1 WHERE id MATCH xslice(10,20);
          962  +**
          963  +** Is the same as saying:
          964  +**
          965  +**     SELECT count(*) FROM rt1 WHERE y1>=10 AND y0<=20;
          966  +*/
          967  +static int xsliceGeometryCallback(
          968  +  sqlite3_rtree_geometry *p,
          969  +  int nCoord,
          970  +  double *aCoord,
          971  +  int *pRes
          972  +){
          973  +  *pRes = aCoord[3]>=p->aParam[0] && aCoord[2]<=p->aParam[1];
          974  +  return SQLITE_OK;
          975  +}
          976  +
          977  +/*
          978  +** A testset for the R-Tree virtual table
          979  +*/
          980  +void testset_rtree(int p1, int p2){
          981  +  unsigned i, n;
          982  +  unsigned mxCoord;
          983  +  unsigned x0, x1, y0, y1, z0, z1;
          984  +  unsigned iStep;
          985  +  int *aCheck = sqlite3_malloc( sizeof(int)*g.szTest*100 );
          986  +
          987  +  mxCoord = 15000;
          988  +  n = g.szTest*100;
          989  +  speedtest1_begin_test(100, "%d INSERTs into an r-tree", n);
          990  +  speedtest1_exec("BEGIN");
          991  +  speedtest1_exec("CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1,z0,z1)");
          992  +  speedtest1_prepare("INSERT INTO rt1(id,x0,x1,y0,y1,z0,z1)"
          993  +                     "VALUES(?1,?2,?3,?4,?5,?6,?7)");
          994  +  for(i=1; i<=n; i++){
          995  +    twoCoords(p1, p2, mxCoord, &x0, &x1);
          996  +    twoCoords(p1, p2, mxCoord, &y0, &y1);
          997  +    twoCoords(p1, p2, mxCoord, &z0, &z1);
          998  +    sqlite3_bind_int(g.pStmt, 1, i);
          999  +    sqlite3_bind_int(g.pStmt, 2, x0);
         1000  +    sqlite3_bind_int(g.pStmt, 3, x1);
         1001  +    sqlite3_bind_int(g.pStmt, 4, y0);
         1002  +    sqlite3_bind_int(g.pStmt, 5, y1);
         1003  +    sqlite3_bind_int(g.pStmt, 6, z0);
         1004  +    sqlite3_bind_int(g.pStmt, 7, z1);
         1005  +    speedtest1_run();
         1006  +  }
         1007  +  speedtest1_exec("COMMIT");
         1008  +  speedtest1_end_test();
         1009  +
         1010  +  speedtest1_begin_test(101, "Copy from rtree to a regular table");
         1011  +  speedtest1_exec("CREATE TABLE t1(id INTEGER PRIMARY KEY,x0,x1,y0,y1,z0,z1)");
         1012  +  speedtest1_exec("INSERT INTO t1 SELECT * FROM rt1");
         1013  +  speedtest1_end_test();
         1014  +
         1015  +  n = g.szTest*20;
         1016  +  speedtest1_begin_test(110, "%d one-dimensional intersect slice queries", n);
         1017  +  speedtest1_prepare("SELECT count(*) FROM rt1 WHERE x0>=?1 AND x1<=?2");
         1018  +  iStep = mxCoord/n;
         1019  +  for(i=0; i<n; i++){
         1020  +    sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1021  +    sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1022  +    speedtest1_run();
         1023  +    aCheck[i] = atoi(g.zResult);
         1024  +  }
         1025  +  speedtest1_end_test();
         1026  +
         1027  +  if( g.bVerify ){
         1028  +    n = g.szTest*20;
         1029  +    speedtest1_begin_test(111, "Verify result from 1-D intersect slice queries");
         1030  +    speedtest1_prepare("SELECT count(*) FROM t1 WHERE x0>=?1 AND x1<=?2");
         1031  +    iStep = mxCoord/n;
         1032  +    for(i=0; i<n; i++){
         1033  +      sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1034  +      sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1035  +      speedtest1_run();
         1036  +      if( aCheck[i]!=atoi(g.zResult) ){
         1037  +        fatal_error("Count disagree step %d: %d..%d.  %d vs %d",
         1038  +                    i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult));
         1039  +      }
         1040  +    }
         1041  +    speedtest1_end_test();
         1042  +  }
         1043  +  
         1044  +  n = g.szTest*20;
         1045  +  speedtest1_begin_test(120, "%d one-dimensional overlap slice queries", n);
         1046  +  speedtest1_prepare("SELECT count(*) FROM rt1 WHERE y1>=?1 AND y0<=?2");
         1047  +  iStep = mxCoord/n;
         1048  +  for(i=0; i<n; i++){
         1049  +    sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1050  +    sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1051  +    speedtest1_run();
         1052  +    aCheck[i] = atoi(g.zResult);
         1053  +  }
         1054  +  speedtest1_end_test();
         1055  +
         1056  +  if( g.bVerify ){
         1057  +    n = g.szTest*20;
         1058  +    speedtest1_begin_test(121, "Verify result from 1-D overlap slice queries");
         1059  +    speedtest1_prepare("SELECT count(*) FROM t1 WHERE y1>=?1 AND y0<=?2");
         1060  +    iStep = mxCoord/n;
         1061  +    for(i=0; i<n; i++){
         1062  +      sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1063  +      sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1064  +      speedtest1_run();
         1065  +      if( aCheck[i]!=atoi(g.zResult) ){
         1066  +        fatal_error("Count disagree step %d: %d..%d.  %d vs %d",
         1067  +                    i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult));
         1068  +      }
         1069  +    }
         1070  +    speedtest1_end_test();
         1071  +  }
         1072  +  
         1073  +
         1074  +  n = g.szTest*20;
         1075  +  speedtest1_begin_test(125, "%d custom geometry callback queries", n);
         1076  +  sqlite3_rtree_geometry_callback(g.db, "xslice", xsliceGeometryCallback, 0);
         1077  +  speedtest1_prepare("SELECT count(*) FROM rt1 WHERE id MATCH xslice(?1,?2)");
         1078  +  iStep = mxCoord/n;
         1079  +  for(i=0; i<n; i++){
         1080  +    sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1081  +    sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1082  +    speedtest1_run();
         1083  +    if( aCheck[i]!=atoi(g.zResult) ){
         1084  +      fatal_error("Count disagree step %d: %d..%d.  %d vs %d",
         1085  +                  i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult));
         1086  +    }
         1087  +  }
         1088  +  speedtest1_end_test();
         1089  +
         1090  +  n = g.szTest*80;
         1091  +  speedtest1_begin_test(130, "%d three-dimensional intersect box queries", n);
         1092  +  speedtest1_prepare("SELECT count(*) FROM rt1 WHERE x1>=?1 AND x0<=?2"
         1093  +                     " AND y1>=?1 AND y0<=?2 AND z1>=?1 AND z0<=?2");
         1094  +  iStep = mxCoord/n;
         1095  +  for(i=0; i<n; i++){
         1096  +    sqlite3_bind_int(g.pStmt, 1, i*iStep);
         1097  +    sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep);
         1098  +    speedtest1_run();
         1099  +    aCheck[i] = atoi(g.zResult);
         1100  +  }
         1101  +  speedtest1_end_test();
         1102  +
         1103  +  n = g.szTest*100;
         1104  +  speedtest1_begin_test(140, "%d rowid queries", n);
         1105  +  speedtest1_prepare("SELECT * FROM rt1 WHERE id=?1");
         1106  +  for(i=1; i<=n; i++){
         1107  +    sqlite3_bind_int(g.pStmt, 1, i);
         1108  +    speedtest1_run();
         1109  +  }
         1110  +  speedtest1_end_test();
         1111  +}
   933   1112   
   934   1113   /*
   935   1114   ** A testset used for debugging speedtest1 itself.
   936   1115   */
   937   1116   void testset_debug1(void){
   938   1117     unsigned i, n;
   939   1118     unsigned x1, x2;
................................................................................
  1046   1225           zTSet = argv[++i];
  1047   1226         }else if( strcmp(z,"trace")==0 ){
  1048   1227           doTrace = 1;
  1049   1228         }else if( strcmp(z,"utf16le")==0 ){
  1050   1229           zEncoding = "utf16le";
  1051   1230         }else if( strcmp(z,"utf16be")==0 ){
  1052   1231           zEncoding = "utf16be";
         1232  +      }else if( strcmp(z,"verify")==0 ){
         1233  +        g.bVerify = 1;
  1053   1234         }else if( strcmp(z,"without-rowid")==0 ){
  1054   1235           g.zWR = "WITHOUT ROWID";
  1055   1236           g.zPK = "PRIMARY KEY";
  1056   1237         }else if( strcmp(z, "help")==0 || strcmp(z,"?")==0 ){
  1057   1238           printf(zHelp, argv[0]);
  1058   1239           exit(0);
  1059   1240         }else{
................................................................................
  1137   1318     if( g.bExplain ) printf(".explain\n.echo on\n");
  1138   1319     if( strcmp(zTSet,"main")==0 ){
  1139   1320       testset_main();
  1140   1321     }else if( strcmp(zTSet,"debug1")==0 ){
  1141   1322       testset_debug1();
  1142   1323     }else if( strcmp(zTSet,"cte")==0 ){
  1143   1324       testset_cte();
         1325  +  }else if( strcmp(zTSet,"rtree")==0 ){
         1326  +    testset_rtree(6, 147);
  1144   1327     }else{
  1145         -    fatal_error("unknown testset: \"%s\"\n", zTSet);
         1328  +    fatal_error("unknown testset: \"%s\"\nChoices: main debug1 cte rtree\n",
         1329  +                 zTSet);
  1146   1330     }
  1147   1331     speedtest1_final();
  1148   1332   
  1149   1333     /* Database connection statistics printed after both prepared statements
  1150   1334     ** have been finalized */
  1151   1335   #if SQLITE_VERSION_NUMBER>=3007009
  1152   1336     if( showStats ){