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

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

Overview
Comment:Backport the RTree implementation from the trunk into the 3.6.23 branch. The code for the application-defined query boxes is still present but is disabled. The reason for this backport is to take advantage of recent enhancements to robustness to database corruption.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | branch-3.6.23
Files: files | file ages | folders
SHA1: 854b23c117c973fcf63f31bda189b7492595c3f9
User & Date: drh 2010-10-01 20:45:09
Context
2010-10-02
01:00
Fix the amalgamation builder so that it works with the rtree updates of the prior check-in. Leaf check-in: 265b0b29 user: drh tags: branch-3.6.23
2010-10-01
20:45
Backport the RTree implementation from the trunk into the 3.6.23 branch. The code for the application-defined query boxes is still present but is disabled. The reason for this backport is to take advantage of recent enhancements to robustness to database corruption. check-in: 854b23c1 user: drh tags: branch-3.6.23
2010-08-24
12:05
Pull the incremental_vacuum bug fix ([255f1eefa373153942c67b18b]) and the R-tree segfault bug fix ([7f2f71cc9e3c39093f09231f44]) into the 3.6.23 branch. Increase the version number to 3.6.23.3. check-in: bcbdecd8 user: drh tags: branch-3.6.23
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains code for implementations of the r-tree and r*-tree
    13     13   ** algorithms packaged as an SQLite virtual table module.
    14     14   */
           15  +
           16  +/*
           17  +** Database Format of R-Tree Tables
           18  +** --------------------------------
           19  +**
           20  +** The data structure for a single virtual r-tree table is stored in three 
           21  +** native SQLite tables declared as follows. In each case, the '%' character
           22  +** in the table name is replaced with the user-supplied name of the r-tree
           23  +** table.
           24  +**
           25  +**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
           26  +**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
           27  +**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
           28  +**
           29  +** The data for each node of the r-tree structure is stored in the %_node
           30  +** table. For each node that is not the root node of the r-tree, there is
           31  +** an entry in the %_parent table associating the node with its parent.
           32  +** And for each row of data in the table, there is an entry in the %_rowid
           33  +** table that maps from the entries rowid to the id of the node that it
           34  +** is stored on.
           35  +**
           36  +** The root node of an r-tree always exists, even if the r-tree table is
           37  +** empty. The nodeno of the root node is always 1. All other nodes in the
           38  +** table must be the same size as the root node. The content of each node
           39  +** is formatted as follows:
           40  +**
           41  +**   1. If the node is the root node (node 1), then the first 2 bytes
           42  +**      of the node contain the tree depth as a big-endian integer.
           43  +**      For non-root nodes, the first 2 bytes are left unused.
           44  +**
           45  +**   2. The next 2 bytes contain the number of entries currently 
           46  +**      stored in the node.
           47  +**
           48  +**   3. The remainder of the node contains the node entries. Each entry
           49  +**      consists of a single 8-byte integer followed by an even number
           50  +**      of 4-byte coordinates. For leaf nodes the integer is the rowid
           51  +**      of a record. For internal nodes it is the node number of a
           52  +**      child page.
           53  +*/
    15     54   
    16     55   #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
    17     56   
    18     57   /*
    19     58   ** This file contains an implementation of a couple of different variants
    20     59   ** of the r-tree algorithm. See the README file for further details. The 
    21     60   ** same data-structure is used for all, but the algorithms for insert and
................................................................................
    49     88     #define PickSeeds LinearPickSeeds
    50     89     #define AssignCells splitNodeGuttman
    51     90   #endif
    52     91   #if VARIANT_RSTARTREE_SPLIT
    53     92     #define AssignCells splitNodeStartree
    54     93   #endif
    55     94   
           95  +#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) 
           96  +# define NDEBUG 1
           97  +#endif
    56     98   
    57     99   #ifndef SQLITE_CORE
    58    100     #include "sqlite3ext.h"
    59    101     SQLITE_EXTENSION_INIT1
    60    102   #else
    61    103     #include "sqlite3.h"
    62    104   #endif
    63    105   
    64    106   #include <string.h>
    65    107   #include <assert.h>
    66    108   
    67    109   #ifndef SQLITE_AMALGAMATION
          110  +#include "sqlite3rtree.h"
    68    111   typedef sqlite3_int64 i64;
    69    112   typedef unsigned char u8;
    70    113   typedef unsigned int u32;
    71    114   #endif
    72    115   
    73    116   typedef struct Rtree Rtree;
    74    117   typedef struct RtreeCursor RtreeCursor;
    75    118   typedef struct RtreeNode RtreeNode;
    76    119   typedef struct RtreeCell RtreeCell;
    77    120   typedef struct RtreeConstraint RtreeConstraint;
          121  +typedef struct RtreeMatchArg RtreeMatchArg;
          122  +typedef struct RtreeGeomCallback RtreeGeomCallback;
    78    123   typedef union RtreeCoord RtreeCoord;
    79    124   
    80    125   /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
    81    126   #define RTREE_MAX_DIMENSIONS 5
    82    127   
    83    128   /* Size of hash table Rtree.aHash. This hash table is not expected to
    84    129   ** ever contain very many entries, so a fixed number of buckets is 
................................................................................
   140    185   ** If an R*-tree "Reinsert" operation is required, the same number of
   141    186   ** cells are removed from the overfull node and reinserted into the tree.
   142    187   */
   143    188   #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
   144    189   #define RTREE_REINSERT(p) RTREE_MINCELLS(p)
   145    190   #define RTREE_MAXCELLS 51
   146    191   
          192  +/*
          193  +** The smallest possible node-size is (512-64)==448 bytes. And the largest
          194  +** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
          195  +** Therefore all non-root nodes must contain at least 3 entries. Since 
          196  +** 2^40 is greater than 2^64, an r-tree structure always has a depth of
          197  +** 40 or less.
          198  +*/
          199  +#define RTREE_MAX_DEPTH 40
          200  +
   147    201   /* 
   148    202   ** An rtree cursor object.
   149    203   */
   150    204   struct RtreeCursor {
   151    205     sqlite3_vtab_cursor base;
   152    206     RtreeNode *pNode;                 /* Node cursor is currently pointing at */
   153    207     int iCell;                        /* Index of current cell in pNode */
................................................................................
   172    226       ((double)coord.i)                             \
   173    227   )
   174    228   
   175    229   /*
   176    230   ** A search constraint.
   177    231   */
   178    232   struct RtreeConstraint {
   179         -  int iCoord;                       /* Index of constrained coordinate */
   180         -  int op;                           /* Constraining operation */
   181         -  double rValue;                    /* Constraint value. */
          233  +  int iCoord;                     /* Index of constrained coordinate */
          234  +  int op;                         /* Constraining operation */
          235  +  double rValue;                  /* Constraint value. */
          236  +  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
          237  +  sqlite3_rtree_geometry *pGeom;  /* Constraint callback argument for a MATCH */
   182    238   };
   183    239   
   184    240   /* Possible values for RtreeConstraint.op */
   185         -#define RTREE_EQ 0x41
   186         -#define RTREE_LE 0x42
   187         -#define RTREE_LT 0x43
   188         -#define RTREE_GE 0x44
   189         -#define RTREE_GT 0x45
          241  +#define RTREE_EQ    0x41
          242  +#define RTREE_LE    0x42
          243  +#define RTREE_LT    0x43
          244  +#define RTREE_GE    0x44
          245  +#define RTREE_GT    0x45
          246  +#define RTREE_MATCH 0x46
   190    247   
   191    248   /* 
   192    249   ** An rtree structure node.
   193         -**
   194         -** Data format (RtreeNode.zData):
   195         -**
   196         -**   1. If the node is the root node (node 1), then the first 2 bytes
   197         -**      of the node contain the tree depth as a big-endian integer.
   198         -**      For non-root nodes, the first 2 bytes are left unused.
   199         -**
   200         -**   2. The next 2 bytes contain the number of entries currently 
   201         -**      stored in the node.
   202         -**
   203         -**   3. The remainder of the node contains the node entries. Each entry
   204         -**      consists of a single 8-byte integer followed by an even number
   205         -**      of 4-byte coordinates. For leaf nodes the integer is the rowid
   206         -**      of a record. For internal nodes it is the node number of a
   207         -**      child page.
   208    250   */
   209    251   struct RtreeNode {
   210    252     RtreeNode *pParent;               /* Parent node */
   211    253     i64 iNode;
   212    254     int nRef;
   213    255     int isDirty;
   214    256     u8 *zData;
................................................................................
   220    262   ** Structure to store a deserialized rtree record.
   221    263   */
   222    264   struct RtreeCell {
   223    265     i64 iRowid;
   224    266     RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
   225    267   };
   226    268   
          269  +
          270  +/*
          271  +** Value for the first field of every RtreeMatchArg object. The MATCH
          272  +** operator tests that the first field of a blob operand matches this
          273  +** value to avoid operating on invalid blobs (which could cause a segfault).
          274  +*/
          275  +#define RTREE_GEOMETRY_MAGIC 0x891245AB
          276  +
          277  +/*
          278  +** An instance of this structure must be supplied as a blob argument to
          279  +** the right-hand-side of an SQL MATCH operator used to constrain an
          280  +** r-tree query.
          281  +*/
          282  +struct RtreeMatchArg {
          283  +  u32 magic;                      /* Always RTREE_GEOMETRY_MAGIC */
          284  +  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
          285  +  void *pContext;
          286  +  int nParam;
          287  +  double aParam[1];
          288  +};
          289  +
          290  +/*
          291  +** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
          292  +** a single instance of the following structure is allocated. It is used
          293  +** as the context for the user-function created by by s_r_g_c(). The object
          294  +** is eventually deleted by the destructor mechanism provided by
          295  +** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
          296  +** the geometry callback function).
          297  +*/
          298  +struct RtreeGeomCallback {
          299  +  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
          300  +  void *pContext;
          301  +};
          302  +
   227    303   #ifndef MAX
   228    304   # define MAX(x,y) ((x) < (y) ? (y) : (x))
   229    305   #endif
   230    306   #ifndef MIN
   231    307   # define MIN(x,y) ((x) > (y) ? (y) : (x))
   232    308   #endif
   233    309   
................................................................................
   302    378     }
   303    379   }
   304    380   
   305    381   /*
   306    382   ** Clear the content of node p (set all bytes to 0x00).
   307    383   */
   308    384   static void nodeZero(Rtree *pRtree, RtreeNode *p){
   309         -  if( p ){
   310         -    memset(&p->zData[2], 0, pRtree->iNodeSize-2);
   311         -    p->isDirty = 1;
   312         -  }
          385  +  memset(&p->zData[2], 0, pRtree->iNodeSize-2);
          386  +  p->isDirty = 1;
   313    387   }
   314    388   
   315    389   /*
   316    390   ** Given a node number iNode, return the corresponding key to use
   317    391   ** in the Rtree.aHash table.
   318    392   */
   319    393   static int nodeHash(i64 iNode){
................................................................................
   325    399   
   326    400   /*
   327    401   ** Search the node hash table for node iNode. If found, return a pointer
   328    402   ** to it. Otherwise, return 0.
   329    403   */
   330    404   static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
   331    405     RtreeNode *p;
   332         -  assert( iNode!=0 );
   333    406     for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
   334    407     return p;
   335    408   }
   336    409   
   337    410   /*
   338    411   ** Add node pNode to the node hash table.
   339    412   */
   340    413   static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
   341         -  if( pNode ){
   342         -    int iHash;
   343         -    assert( pNode->pNext==0 );
   344         -    iHash = nodeHash(pNode->iNode);
   345         -    pNode->pNext = pRtree->aHash[iHash];
   346         -    pRtree->aHash[iHash] = pNode;
   347         -  }
          414  +  int iHash;
          415  +  assert( pNode->pNext==0 );
          416  +  iHash = nodeHash(pNode->iNode);
          417  +  pNode->pNext = pRtree->aHash[iHash];
          418  +  pRtree->aHash[iHash] = pNode;
   348    419   }
   349    420   
   350    421   /*
   351    422   ** Remove node pNode from the node hash table.
   352    423   */
   353    424   static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
   354    425     RtreeNode **pp;
................................................................................
   362    433   
   363    434   /*
   364    435   ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
   365    436   ** indicating that node has not yet been assigned a node number. It is
   366    437   ** assigned a node number when nodeWrite() is called to write the
   367    438   ** node contents out to the database.
   368    439   */
   369         -static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){
          440  +static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
   370    441     RtreeNode *pNode;
   371    442     pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
   372    443     if( pNode ){
   373         -    memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
          444  +    memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
   374    445       pNode->zData = (u8 *)&pNode[1];
   375    446       pNode->nRef = 1;
   376    447       pNode->pParent = pParent;
   377    448       pNode->isDirty = 1;
   378    449       nodeReference(pParent);
   379    450     }
   380    451     return pNode;
................................................................................
   387    458   nodeAcquire(
   388    459     Rtree *pRtree,             /* R-tree structure */
   389    460     i64 iNode,                 /* Node number to load */
   390    461     RtreeNode *pParent,        /* Either the parent node or NULL */
   391    462     RtreeNode **ppNode         /* OUT: Acquired node */
   392    463   ){
   393    464     int rc;
          465  +  int rc2 = SQLITE_OK;
   394    466     RtreeNode *pNode;
   395    467   
   396    468     /* Check if the requested node is already in the hash table. If so,
   397    469     ** increase its reference count and return it.
   398    470     */
   399    471     if( (pNode = nodeHashLookup(pRtree, iNode)) ){
   400    472       assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
................................................................................
   403    475         pNode->pParent = pParent;
   404    476       }
   405    477       pNode->nRef++;
   406    478       *ppNode = pNode;
   407    479       return SQLITE_OK;
   408    480     }
   409    481   
   410         -  pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
   411         -  if( !pNode ){
   412         -    *ppNode = 0;
   413         -    return SQLITE_NOMEM;
   414         -  }
   415         -  pNode->pParent = pParent;
   416         -  pNode->zData = (u8 *)&pNode[1];
   417         -  pNode->nRef = 1;
   418         -  pNode->iNode = iNode;
   419         -  pNode->isDirty = 0;
   420         -  pNode->pNext = 0;
   421         -
   422    482     sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
   423    483     rc = sqlite3_step(pRtree->pReadNode);
   424    484     if( rc==SQLITE_ROW ){
   425    485       const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
   426         -    assert( sqlite3_column_bytes(pRtree->pReadNode, 0)==pRtree->iNodeSize );
   427         -    memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
   428         -    nodeReference(pParent);
          486  +    if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){
          487  +      pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize);
          488  +      if( !pNode ){
          489  +        rc2 = SQLITE_NOMEM;
          490  +      }else{
          491  +        pNode->pParent = pParent;
          492  +        pNode->zData = (u8 *)&pNode[1];
          493  +        pNode->nRef = 1;
          494  +        pNode->iNode = iNode;
          495  +        pNode->isDirty = 0;
          496  +        pNode->pNext = 0;
          497  +        memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
          498  +        nodeReference(pParent);
          499  +      }
          500  +    }
          501  +  }
          502  +  rc = sqlite3_reset(pRtree->pReadNode);
          503  +  if( rc==SQLITE_OK ) rc = rc2;
          504  +
          505  +  /* If the root node was just loaded, set pRtree->iDepth to the height
          506  +  ** of the r-tree structure. A height of zero means all data is stored on
          507  +  ** the root node. A height of one means the children of the root node
          508  +  ** are the leaves, and so on. If the depth as specified on the root node
          509  +  ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
          510  +  */
          511  +  if( pNode && iNode==1 ){
          512  +    pRtree->iDepth = readInt16(pNode->zData);
          513  +    if( pRtree->iDepth>RTREE_MAX_DEPTH ){
          514  +      rc = SQLITE_CORRUPT;
          515  +    }
          516  +  }
          517  +
          518  +  /* If no error has occurred so far, check if the "number of entries"
          519  +  ** field on the node is too large. If so, set the return code to 
          520  +  ** SQLITE_CORRUPT.
          521  +  */
          522  +  if( pNode && rc==SQLITE_OK ){
          523  +    if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
          524  +      rc = SQLITE_CORRUPT;
          525  +    }
          526  +  }
          527  +
          528  +  if( rc==SQLITE_OK ){
          529  +    if( pNode!=0 ){
          530  +      nodeHashInsert(pRtree, pNode);
          531  +    }else{
          532  +      rc = SQLITE_CORRUPT;
          533  +    }
          534  +    *ppNode = pNode;
   429    535     }else{
   430    536       sqlite3_free(pNode);
   431         -    pNode = 0;
   432         -  }
   433         -
   434         -  *ppNode = pNode;
   435         -  rc = sqlite3_reset(pRtree->pReadNode);
   436         -
   437         -  if( rc==SQLITE_OK && iNode==1 ){
   438         -    pRtree->iDepth = readInt16(pNode->zData);
   439         -  }
   440         -
   441         -  if( pNode!=0 ){
   442         -    nodeHashInsert(pRtree, pNode);
   443         -  }else if( rc==SQLITE_OK ){
   444         -    rc = SQLITE_CORRUPT;
          537  +    *ppNode = 0;
   445    538     }
   446    539   
   447    540     return rc;
   448    541   }
   449    542   
   450    543   /*
   451    544   ** Overwrite cell iCell of node pNode with the contents of pCell.
................................................................................
   491    584   ){
   492    585     int nCell;                    /* Current number of cells in pNode */
   493    586     int nMaxCell;                 /* Maximum number of cells for pNode */
   494    587   
   495    588     nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
   496    589     nCell = NCELL(pNode);
   497    590   
   498         -  assert(nCell<=nMaxCell);
   499         -
          591  +  assert( nCell<=nMaxCell );
   500    592     if( nCell<nMaxCell ){
   501    593       nodeOverwriteCell(pRtree, pNode, pCell, nCell);
   502    594       writeInt16(&pNode->zData[2], nCell+1);
   503    595       pNode->isDirty = 1;
   504    596     }
   505    597   
   506    598     return (nCell==nMaxCell);
................................................................................
   712    804       rc = SQLITE_OK;
   713    805     }
   714    806     *ppCursor = (sqlite3_vtab_cursor *)pCsr;
   715    807   
   716    808     return rc;
   717    809   }
   718    810   
          811  +
          812  +/*
          813  +** Free the RtreeCursor.aConstraint[] array and its contents.
          814  +*/
          815  +static void freeCursorConstraints(RtreeCursor *pCsr){
          816  +  if( pCsr->aConstraint ){
          817  +    int i;                        /* Used to iterate through constraint array */
          818  +    for(i=0; i<pCsr->nConstraint; i++){
          819  +      sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
          820  +      if( pGeom ){
          821  +        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
          822  +        sqlite3_free(pGeom);
          823  +      }
          824  +    }
          825  +    sqlite3_free(pCsr->aConstraint);
          826  +    pCsr->aConstraint = 0;
          827  +  }
          828  +}
          829  +
   719    830   /* 
   720    831   ** Rtree virtual table module xClose method.
   721    832   */
   722    833   static int rtreeClose(sqlite3_vtab_cursor *cur){
   723    834     Rtree *pRtree = (Rtree *)(cur->pVtab);
   724    835     int rc;
   725    836     RtreeCursor *pCsr = (RtreeCursor *)cur;
   726         -  sqlite3_free(pCsr->aConstraint);
          837  +  freeCursorConstraints(pCsr);
   727    838     rc = nodeRelease(pRtree, pCsr->pNode);
   728    839     sqlite3_free(pCsr);
   729    840     return rc;
   730    841   }
   731    842   
   732    843   /*
   733    844   ** Rtree virtual table module xEof method.
................................................................................
   735    846   ** Return non-zero if the cursor does not currently point to a valid 
   736    847   ** record (i.e if the scan has finished), or zero otherwise.
   737    848   */
   738    849   static int rtreeEof(sqlite3_vtab_cursor *cur){
   739    850     RtreeCursor *pCsr = (RtreeCursor *)cur;
   740    851     return (pCsr->pNode==0);
   741    852   }
          853  +
          854  +/*
          855  +** The r-tree constraint passed as the second argument to this function is
          856  +** guaranteed to be a MATCH constraint.
          857  +*/
          858  +static int testRtreeGeom(
          859  +  Rtree *pRtree,                  /* R-Tree object */
          860  +  RtreeConstraint *pConstraint,   /* MATCH constraint to test */
          861  +  RtreeCell *pCell,               /* Cell to test */
          862  +  int *pbRes                      /* OUT: Test result */
          863  +){
          864  +  int i;
          865  +  double aCoord[RTREE_MAX_DIMENSIONS*2];
          866  +  int nCoord = pRtree->nDim*2;
          867  +
          868  +  assert( pConstraint->op==RTREE_MATCH );
          869  +  assert( pConstraint->pGeom );
          870  +
          871  +  for(i=0; i<nCoord; i++){
          872  +    aCoord[i] = DCOORD(pCell->aCoord[i]);
          873  +  }
          874  +  return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
          875  +}
   742    876   
   743    877   /* 
   744    878   ** Cursor pCursor currently points to a cell in a non-leaf page.
   745         -** Return true if the sub-tree headed by the cell is filtered
          879  +** Set *pbEof to true if the sub-tree headed by the cell is filtered
   746    880   ** (excluded) by the constraints in the pCursor->aConstraint[] 
   747    881   ** array, or false otherwise.
          882  +**
          883  +** Return SQLITE_OK if successful or an SQLite error code if an error
          884  +** occurs within a geometry callback.
   748    885   */
   749         -static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){
          886  +static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   750    887     RtreeCell cell;
   751    888     int ii;
   752    889     int bRes = 0;
   753    890   
   754    891     nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   755    892     for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
   756    893       RtreeConstraint *p = &pCursor->aConstraint[ii];
   757    894       double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
   758    895       double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
   759    896   
   760    897       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   761         -        || p->op==RTREE_GT || p->op==RTREE_EQ
          898  +        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   762    899       );
   763    900   
   764    901       switch( p->op ){
   765         -      case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break;
   766         -      case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break;
   767         -      case RTREE_EQ: 
          902  +      case RTREE_LE: case RTREE_LT: 
          903  +        bRes = p->rValue<cell_min; 
          904  +        break;
          905  +
          906  +      case RTREE_GE: case RTREE_GT: 
          907  +        bRes = p->rValue>cell_max; 
          908  +        break;
          909  +
          910  +      case RTREE_EQ:
   768    911           bRes = (p->rValue>cell_max || p->rValue<cell_min);
   769    912           break;
          913  +
          914  +      default: {
          915  +        int rc;
          916  +        assert( p->op==RTREE_MATCH );
          917  +        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
          918  +        if( rc!=SQLITE_OK ){
          919  +          return rc;
          920  +        }
          921  +        bRes = !bRes;
          922  +        break;
          923  +      }
   770    924       }
   771    925     }
   772    926   
   773         -  return bRes;
          927  +  *pbEof = bRes;
          928  +  return SQLITE_OK;
   774    929   }
   775    930   
   776    931   /* 
   777         -** Return true if the cell that cursor pCursor currently points to
          932  +** Test if the cell that cursor pCursor currently points to
   778    933   ** would be filtered (excluded) by the constraints in the 
   779         -** pCursor->aConstraint[] array, or false otherwise.
          934  +** pCursor->aConstraint[] array. If so, set *pbEof to true before
          935  +** returning. If the cell is not filtered (excluded) by the constraints,
          936  +** set pbEof to zero.
          937  +**
          938  +** Return SQLITE_OK if successful or an SQLite error code if an error
          939  +** occurs within a geometry callback.
   780    940   **
   781    941   ** This function assumes that the cell is part of a leaf node.
   782    942   */
   783         -static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){
          943  +static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   784    944     RtreeCell cell;
   785    945     int ii;
          946  +  *pbEof = 0;
   786    947   
   787    948     nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   788    949     for(ii=0; ii<pCursor->nConstraint; ii++){
   789    950       RtreeConstraint *p = &pCursor->aConstraint[ii];
   790    951       double coord = DCOORD(cell.aCoord[p->iCoord]);
   791    952       int res;
   792    953       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   793         -        || p->op==RTREE_GT || p->op==RTREE_EQ
          954  +        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   794    955       );
   795    956       switch( p->op ){
   796    957         case RTREE_LE: res = (coord<=p->rValue); break;
   797    958         case RTREE_LT: res = (coord<p->rValue);  break;
   798    959         case RTREE_GE: res = (coord>=p->rValue); break;
   799    960         case RTREE_GT: res = (coord>p->rValue);  break;
   800    961         case RTREE_EQ: res = (coord==p->rValue); break;
          962  +      default: {
          963  +        int rc;
          964  +        assert( p->op==RTREE_MATCH );
          965  +        rc = testRtreeGeom(pRtree, p, &cell, &res);
          966  +        if( rc!=SQLITE_OK ){
          967  +          return rc;
          968  +        }
          969  +        break;
          970  +      }
   801    971       }
   802    972   
   803         -    if( !res ) return 1;
          973  +    if( !res ){
          974  +      *pbEof = 1;
          975  +      return SQLITE_OK;
          976  +    }
   804    977     }
   805    978   
   806         -  return 0;
          979  +  return SQLITE_OK;
   807    980   }
   808    981   
   809    982   /*
   810    983   ** Cursor pCursor currently points at a node that heads a sub-tree of
   811    984   ** height iHeight (if iHeight==0, then the node is a leaf). Descend
   812    985   ** to point to the left-most cell of the sub-tree that matches the 
   813    986   ** configured constraints.
................................................................................
   826    999   
   827   1000     RtreeNode *pSavedNode = pCursor->pNode;
   828   1001     int iSavedCell = pCursor->iCell;
   829   1002   
   830   1003     assert( iHeight>=0 );
   831   1004   
   832   1005     if( iHeight==0 ){
   833         -    isEof = testRtreeEntry(pRtree, pCursor);
         1006  +    rc = testRtreeEntry(pRtree, pCursor, &isEof);
   834   1007     }else{
   835         -    isEof = testRtreeCell(pRtree, pCursor);
         1008  +    rc = testRtreeCell(pRtree, pCursor, &isEof);
   836   1009     }
   837         -  if( isEof || iHeight==0 ){
         1010  +  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
   838   1011       *pEof = isEof;
   839         -    return SQLITE_OK;
         1012  +    return rc;
   840   1013     }
   841   1014   
   842   1015     iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
   843   1016     rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
   844   1017     if( rc!=SQLITE_OK ){
   845   1018       return rc;
   846   1019     }
................................................................................
   868   1041     return SQLITE_OK;
   869   1042   }
   870   1043   
   871   1044   /*
   872   1045   ** One of the cells in node pNode is guaranteed to have a 64-bit 
   873   1046   ** integer value equal to iRowid. Return the index of this cell.
   874   1047   */
   875         -static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){
         1048  +static int nodeRowidIndex(
         1049  +  Rtree *pRtree, 
         1050  +  RtreeNode *pNode, 
         1051  +  i64 iRowid,
         1052  +  int *piIndex
         1053  +){
   876   1054     int ii;
   877         -  for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
   878         -    assert( ii<(NCELL(pNode)-1) );
         1055  +  int nCell = NCELL(pNode);
         1056  +  for(ii=0; ii<nCell; ii++){
         1057  +    if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
         1058  +      *piIndex = ii;
         1059  +      return SQLITE_OK;
         1060  +    }
   879   1061     }
   880         -  return ii;
         1062  +  return SQLITE_CORRUPT;
   881   1063   }
   882   1064   
   883   1065   /*
   884   1066   ** Return the index of the cell containing a pointer to node pNode
   885   1067   ** in its parent. If pNode is the root node, return -1.
   886   1068   */
   887         -static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){
         1069  +static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
   888   1070     RtreeNode *pParent = pNode->pParent;
   889   1071     if( pParent ){
   890         -    return nodeRowidIndex(pRtree, pParent, pNode->iNode);
         1072  +    return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
   891   1073     }
   892         -  return -1;
         1074  +  *piIndex = -1;
         1075  +  return SQLITE_OK;
   893   1076   }
   894   1077   
   895   1078   /* 
   896   1079   ** Rtree virtual table module xNext method.
   897   1080   */
   898   1081   static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
   899   1082     Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
   900   1083     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
   901   1084     int rc = SQLITE_OK;
         1085  +
         1086  +  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
         1087  +  ** already at EOF. It is against the rules to call the xNext() method of
         1088  +  ** a cursor that has already reached EOF.
         1089  +  */
         1090  +  assert( pCsr->pNode );
   902   1091   
   903   1092     if( pCsr->iStrategy==1 ){
   904   1093       /* This "scan" is a direct lookup by rowid. There is no next entry. */
   905   1094       nodeRelease(pRtree, pCsr->pNode);
   906   1095       pCsr->pNode = 0;
   907         -  }
   908         -
   909         -  else if( pCsr->pNode ){
         1096  +  }else{
   910   1097       /* Move to the next entry that matches the configured constraints. */
   911   1098       int iHeight = 0;
   912   1099       while( pCsr->pNode ){
   913   1100         RtreeNode *pNode = pCsr->pNode;
   914   1101         int nCell = NCELL(pNode);
   915   1102         for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
   916   1103           int isEof;
   917   1104           rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
   918   1105           if( rc!=SQLITE_OK || !isEof ){
   919   1106             return rc;
   920   1107           }
   921   1108         }
   922   1109         pCsr->pNode = pNode->pParent;
   923         -      pCsr->iCell = nodeParentIndex(pRtree, pNode);
         1110  +      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
         1111  +      if( rc!=SQLITE_OK ){
         1112  +        return rc;
         1113  +      }
   924   1114         nodeReference(pCsr->pNode);
   925   1115         nodeRelease(pRtree, pNode);
   926   1116         iHeight++;
   927   1117       }
   928   1118     }
   929   1119   
   930   1120     return rc;
................................................................................
   984   1174       sqlite3_reset(pRtree->pReadRowid);
   985   1175     }else{
   986   1176       rc = sqlite3_reset(pRtree->pReadRowid);
   987   1177     }
   988   1178     return rc;
   989   1179   }
   990   1180   
         1181  +/*
         1182  +** This function is called to configure the RtreeConstraint object passed
         1183  +** as the second argument for a MATCH constraint. The value passed as the
         1184  +** first argument to this function is the right-hand operand to the MATCH
         1185  +** operator.
         1186  +*/
         1187  +static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
         1188  +  RtreeMatchArg *p;
         1189  +  sqlite3_rtree_geometry *pGeom;
         1190  +  int nBlob;
         1191  +
         1192  +  /* Check that value is actually a blob. */
         1193  +  if( !sqlite3_value_type(pValue)==SQLITE_BLOB ) return SQLITE_ERROR;
         1194  +
         1195  +  /* Check that the blob is roughly the right size. */
         1196  +  nBlob = sqlite3_value_bytes(pValue);
         1197  +  if( nBlob<sizeof(RtreeMatchArg) 
         1198  +   || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0
         1199  +  ){
         1200  +    return SQLITE_ERROR;
         1201  +  }
         1202  +
         1203  +  pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
         1204  +      sizeof(sqlite3_rtree_geometry) + nBlob
         1205  +  );
         1206  +  if( !pGeom ) return SQLITE_NOMEM;
         1207  +  memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
         1208  +  p = (RtreeMatchArg *)&pGeom[1];
         1209  +
         1210  +  memcpy(p, sqlite3_value_blob(pValue), nBlob);
         1211  +  if( p->magic!=RTREE_GEOMETRY_MAGIC 
         1212  +   || nBlob!=(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double))
         1213  +  ){
         1214  +    sqlite3_free(pGeom);
         1215  +    return SQLITE_ERROR;
         1216  +  }
         1217  +
         1218  +  pGeom->pContext = p->pContext;
         1219  +  pGeom->nParam = p->nParam;
         1220  +  pGeom->aParam = p->aParam;
         1221  +
         1222  +  pCons->xGeom = p->xGeom;
         1223  +  pCons->pGeom = pGeom;
         1224  +  return SQLITE_OK;
         1225  +}
   991   1226   
   992   1227   /* 
   993   1228   ** Rtree virtual table module xFilter method.
   994   1229   */
   995   1230   static int rtreeFilter(
   996   1231     sqlite3_vtab_cursor *pVtabCursor, 
   997   1232     int idxNum, const char *idxStr,
................................................................................
  1002   1237   
  1003   1238     RtreeNode *pRoot = 0;
  1004   1239     int ii;
  1005   1240     int rc = SQLITE_OK;
  1006   1241   
  1007   1242     rtreeReference(pRtree);
  1008   1243   
  1009         -  sqlite3_free(pCsr->aConstraint);
  1010         -  pCsr->aConstraint = 0;
         1244  +  freeCursorConstraints(pCsr);
  1011   1245     pCsr->iStrategy = idxNum;
  1012   1246   
  1013   1247     if( idxNum==1 ){
  1014   1248       /* Special case - lookup by rowid. */
  1015   1249       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
  1016   1250       i64 iRowid = sqlite3_value_int64(argv[0]);
  1017   1251       rc = findLeafNode(pRtree, iRowid, &pLeaf);
  1018   1252       pCsr->pNode = pLeaf; 
  1019         -    if( pLeaf && rc==SQLITE_OK ){
  1020         -      pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
         1253  +    if( pLeaf ){
         1254  +      assert( rc==SQLITE_OK );
         1255  +      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
  1021   1256       }
  1022   1257     }else{
  1023   1258       /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
  1024   1259       ** with the configured constraints. 
  1025   1260       */
  1026   1261       if( argc>0 ){
  1027   1262         pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
  1028   1263         pCsr->nConstraint = argc;
  1029   1264         if( !pCsr->aConstraint ){
  1030   1265           rc = SQLITE_NOMEM;
  1031   1266         }else{
         1267  +        memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
  1032   1268           assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
  1033   1269           for(ii=0; ii<argc; ii++){
  1034   1270             RtreeConstraint *p = &pCsr->aConstraint[ii];
  1035   1271             p->op = idxStr[ii*2];
  1036   1272             p->iCoord = idxStr[ii*2+1]-'a';
  1037         -          p->rValue = sqlite3_value_double(argv[ii]);
         1273  +          if( p->op==RTREE_MATCH ){
         1274  +            /* A MATCH operator. The right-hand-side must be a blob that
         1275  +            ** can be cast into an RtreeMatchArg object. One created using
         1276  +            ** an sqlite3_rtree_geometry_callback() SQL user function.
         1277  +            */
         1278  +            rc = deserializeGeometry(argv[ii], p);
         1279  +            if( rc!=SQLITE_OK ){
         1280  +              break;
         1281  +            }
         1282  +          }else{
         1283  +            p->rValue = sqlite3_value_double(argv[ii]);
         1284  +          }
  1038   1285           }
  1039   1286         }
  1040   1287       }
  1041   1288     
  1042   1289       if( rc==SQLITE_OK ){
  1043   1290         pCsr->pNode = 0;
  1044   1291         rc = nodeAcquire(pRtree, 1, 0, &pRoot);
................................................................................
  1071   1318   ** Rtree virtual table module xBestIndex method. There are three
  1072   1319   ** table scan strategies to choose from (in order from most to 
  1073   1320   ** least desirable):
  1074   1321   **
  1075   1322   **   idxNum     idxStr        Strategy
  1076   1323   **   ------------------------------------------------
  1077   1324   **     1        Unused        Direct lookup by rowid.
  1078         -**     2        See below     R-tree query.
  1079         -**     3        Unused        Full table scan.
         1325  +**     2        See below     R-tree query or full-table scan.
  1080   1326   **   ------------------------------------------------
  1081   1327   **
  1082         -** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
         1328  +** If strategy 1 is used, then idxStr is not meaningful. If strategy
  1083   1329   ** 2 is used, idxStr is formatted to contain 2 bytes for each 
  1084   1330   ** constraint used. The first two bytes of idxStr correspond to 
  1085   1331   ** the constraint in sqlite3_index_info.aConstraintUsage[] with
  1086   1332   ** (argvIndex==1) etc.
  1087   1333   **
  1088   1334   ** The first of each pair of bytes in idxStr identifies the constraint
  1089   1335   ** operator as follows:
................................................................................
  1091   1337   **   Operator    Byte Value
  1092   1338   **   ----------------------
  1093   1339   **      =        0x41 ('A')
  1094   1340   **     <=        0x42 ('B')
  1095   1341   **      <        0x43 ('C')
  1096   1342   **     >=        0x44 ('D')
  1097   1343   **      >        0x45 ('E')
         1344  +**   MATCH       0x46 ('F')
  1098   1345   **   ----------------------
  1099   1346   **
  1100   1347   ** The second of each pair of bytes identifies the coordinate column
  1101   1348   ** to which the constraint applies. The leftmost coordinate column
  1102   1349   ** is 'a', the second from the left 'b' etc.
  1103   1350   */
  1104   1351   static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
................................................................................
  1129   1376         ** considered almost as quick as a direct rowid lookup (for which 
  1130   1377         ** sqlite uses an internal cost of 0.0).
  1131   1378         */ 
  1132   1379         pIdxInfo->estimatedCost = 10.0;
  1133   1380         return SQLITE_OK;
  1134   1381       }
  1135   1382   
  1136         -    if( p->usable && p->iColumn>0 ){
         1383  +    if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){
         1384  +      int j, opmsk;
         1385  +      static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
  1137   1386         u8 op = 0;
  1138   1387         switch( p->op ){
  1139   1388           case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
  1140   1389           case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
  1141   1390           case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
  1142   1391           case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
  1143   1392           case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
  1144         -      }
  1145         -      if( op ){
  1146         -        /* Make sure this particular constraint has not been used before.
  1147         -        ** If it has been used before, ignore it.
  1148         -        **
  1149         -        ** A <= or < can be used if there is a prior >= or >.
  1150         -        ** A >= or > can be used if there is a prior < or <=.
  1151         -        ** A <= or < is disqualified if there is a prior <=, <, or ==.
  1152         -        ** A >= or > is disqualified if there is a prior >=, >, or ==.
  1153         -        ** A == is disqualifed if there is any prior constraint.
  1154         -        */
  1155         -        int j, opmsk;
  1156         -        static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
  1157         -        assert( compatible[RTREE_EQ & 7]==0 );
  1158         -        assert( compatible[RTREE_LT & 7]==1 );
  1159         -        assert( compatible[RTREE_LE & 7]==1 );
  1160         -        assert( compatible[RTREE_GT & 7]==2 );
  1161         -        assert( compatible[RTREE_GE & 7]==2 );
  1162         -        cCol = p->iColumn - 1 + 'a';
  1163         -        opmsk = compatible[op & 7];
  1164         -        for(j=0; j<iIdx; j+=2){
  1165         -          if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
  1166         -            op = 0;
  1167         -            break;
  1168         -          }
         1393  +        default:
         1394  +          assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
         1395  +          op = RTREE_MATCH; 
         1396  +          break;
         1397  +      }
         1398  +      assert( op!=0 );
         1399  +
         1400  +      /* Make sure this particular constraint has not been used before.
         1401  +      ** If it has been used before, ignore it.
         1402  +      **
         1403  +      ** A <= or < can be used if there is a prior >= or >.
         1404  +      ** A >= or > can be used if there is a prior < or <=.
         1405  +      ** A <= or < is disqualified if there is a prior <=, <, or ==.
         1406  +      ** A >= or > is disqualified if there is a prior >=, >, or ==.
         1407  +      ** A == is disqualifed if there is any prior constraint.
         1408  +      */
         1409  +      assert( compatible[RTREE_EQ & 7]==0 );
         1410  +      assert( compatible[RTREE_LT & 7]==1 );
         1411  +      assert( compatible[RTREE_LE & 7]==1 );
         1412  +      assert( compatible[RTREE_GT & 7]==2 );
         1413  +      assert( compatible[RTREE_GE & 7]==2 );
         1414  +      cCol = p->iColumn - 1 + 'a';
         1415  +      opmsk = compatible[op & 7];
         1416  +      for(j=0; j<iIdx; j+=2){
         1417  +        if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
         1418  +          op = 0;
         1419  +          break;
  1169   1420           }
  1170   1421         }
  1171   1422         if( op ){
  1172   1423           assert( iIdx<sizeof(zIdxStr)-1 );
  1173   1424           zIdxStr[iIdx++] = op;
  1174   1425           zIdxStr[iIdx++] = cCol;
  1175   1426           pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
................................................................................
  1269   1520     RtreeCell *aCell, 
  1270   1521     int nCell, 
  1271   1522     int iExclude
  1272   1523   ){
  1273   1524     int ii;
  1274   1525     float overlap = 0.0;
  1275   1526     for(ii=0; ii<nCell; ii++){
  1276         -    if( ii!=iExclude ){
         1527  +#if VARIANT_RSTARTREE_CHOOSESUBTREE
         1528  +    if( ii!=iExclude )
         1529  +#else
         1530  +    assert( iExclude==-1 );
         1531  +#endif
         1532  +    {
  1277   1533         int jj;
  1278   1534         float o = 1.0;
  1279   1535         for(jj=0; jj<(pRtree->nDim*2); jj+=2){
  1280   1536           double x1;
  1281   1537           double x2;
  1282   1538   
  1283   1539           x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
................................................................................
  1362   1618   #endif
  1363   1619   
  1364   1620       /* Select the child node which will be enlarged the least if pCell
  1365   1621       ** is inserted into it. Resolve ties by choosing the entry with
  1366   1622       ** the smallest area.
  1367   1623       */
  1368   1624       for(iCell=0; iCell<nCell; iCell++){
         1625  +      int bBest = 0;
  1369   1626         float growth;
  1370   1627         float area;
  1371   1628         float overlap = 0.0;
  1372   1629         nodeGetCell(pRtree, pNode, iCell, &cell);
  1373   1630         growth = cellGrowth(pRtree, &cell, pCell);
  1374   1631         area = cellArea(pRtree, &cell);
         1632  +
  1375   1633   #if VARIANT_RSTARTREE_CHOOSESUBTREE
  1376   1634         if( ii==(pRtree->iDepth-1) ){
  1377   1635           overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
  1378   1636         }
  1379         -#endif
  1380   1637         if( (iCell==0) 
  1381   1638          || (overlap<fMinOverlap) 
  1382   1639          || (overlap==fMinOverlap && growth<fMinGrowth)
  1383   1640          || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
  1384   1641         ){
         1642  +        bBest = 1;
         1643  +      }
         1644  +#else
         1645  +      if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
         1646  +        bBest = 1;
         1647  +      }
         1648  +#endif
         1649  +      if( bBest ){
  1385   1650           fMinOverlap = overlap;
  1386   1651           fMinGrowth = growth;
  1387   1652           fMinArea = area;
  1388   1653           iBest = cell.iRowid;
  1389   1654         }
  1390   1655       }
  1391   1656   
................................................................................
  1400   1665   }
  1401   1666   
  1402   1667   /*
  1403   1668   ** A cell with the same content as pCell has just been inserted into
  1404   1669   ** the node pNode. This function updates the bounding box cells in
  1405   1670   ** all ancestor elements.
  1406   1671   */
  1407         -static void AdjustTree(
         1672  +static int AdjustTree(
  1408   1673     Rtree *pRtree,                    /* Rtree table */
  1409   1674     RtreeNode *pNode,                 /* Adjust ancestry of this node. */
  1410   1675     RtreeCell *pCell                  /* This cell was just inserted */
  1411   1676   ){
  1412   1677     RtreeNode *p = pNode;
  1413   1678     while( p->pParent ){
  1414         -    RtreeCell cell;
  1415   1679       RtreeNode *pParent = p->pParent;
  1416         -    int iCell = nodeParentIndex(pRtree, p);
         1680  +    RtreeCell cell;
         1681  +    int iCell;
         1682  +
         1683  +    if( nodeParentIndex(pRtree, p, &iCell) ){
         1684  +      return SQLITE_CORRUPT;
         1685  +    }
  1417   1686   
  1418   1687       nodeGetCell(pRtree, pParent, iCell, &cell);
  1419   1688       if( !cellContains(pRtree, &cell, pCell) ){
  1420   1689         cellUnion(pRtree, &cell, pCell);
  1421   1690         nodeOverwriteCell(pRtree, pParent, &cell, iCell);
  1422   1691       }
  1423   1692    
  1424   1693       p = pParent;
  1425   1694     }
         1695  +  return SQLITE_OK;
  1426   1696   }
  1427   1697   
  1428   1698   /*
  1429   1699   ** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
  1430   1700   */
  1431   1701   static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
  1432   1702     sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
................................................................................
  1947   2217       nodeGetCell(pRtree, pNode, i, &aCell[i]);
  1948   2218     }
  1949   2219     nodeZero(pRtree, pNode);
  1950   2220     memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
  1951   2221     nCell++;
  1952   2222   
  1953   2223     if( pNode->iNode==1 ){
  1954         -    pRight = nodeNew(pRtree, pNode, 1);
  1955         -    pLeft = nodeNew(pRtree, pNode, 1);
         2224  +    pRight = nodeNew(pRtree, pNode);
         2225  +    pLeft = nodeNew(pRtree, pNode);
  1956   2226       pRtree->iDepth++;
  1957   2227       pNode->isDirty = 1;
  1958   2228       writeInt16(pNode->zData, pRtree->iDepth);
  1959   2229     }else{
  1960   2230       pLeft = pNode;
  1961         -    pRight = nodeNew(pRtree, pLeft->pParent, 1);
         2231  +    pRight = nodeNew(pRtree, pLeft->pParent);
  1962   2232       nodeReference(pLeft);
  1963   2233     }
  1964   2234   
  1965   2235     if( !pLeft || !pRight ){
  1966   2236       rc = SQLITE_NOMEM;
  1967   2237       goto splitnode_out;
  1968   2238     }
................................................................................
  1971   2241     memset(pRight->zData, 0, pRtree->iNodeSize);
  1972   2242   
  1973   2243     rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
  1974   2244     if( rc!=SQLITE_OK ){
  1975   2245       goto splitnode_out;
  1976   2246     }
  1977   2247   
  1978         -  /* Ensure both child nodes have node numbers assigned to them. */
  1979         -  if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
         2248  +  /* Ensure both child nodes have node numbers assigned to them by calling
         2249  +  ** nodeWrite(). Node pRight always needs a node number, as it was created
         2250  +  ** by nodeNew() above. But node pLeft sometimes already has a node number.
         2251  +  ** In this case avoid the all to nodeWrite().
         2252  +  */
         2253  +  if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
  1980   2254      || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
  1981   2255     ){
  1982   2256       goto splitnode_out;
  1983   2257     }
  1984   2258   
  1985   2259     rightbbox.iRowid = pRight->iNode;
  1986   2260     leftbbox.iRowid = pLeft->iNode;
................................................................................
  1988   2262     if( pNode->iNode==1 ){
  1989   2263       rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
  1990   2264       if( rc!=SQLITE_OK ){
  1991   2265         goto splitnode_out;
  1992   2266       }
  1993   2267     }else{
  1994   2268       RtreeNode *pParent = pLeft->pParent;
  1995         -    int iCell = nodeParentIndex(pRtree, pLeft);
  1996         -    nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
  1997         -    AdjustTree(pRtree, pParent, &leftbbox);
         2269  +    int iCell;
         2270  +    rc = nodeParentIndex(pRtree, pLeft, &iCell);
         2271  +    if( rc==SQLITE_OK ){
         2272  +      nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
         2273  +      rc = AdjustTree(pRtree, pParent, &leftbbox);
         2274  +    }
         2275  +    if( rc!=SQLITE_OK ){
         2276  +      goto splitnode_out;
         2277  +    }
  1998   2278     }
  1999   2279     if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
  2000   2280       goto splitnode_out;
  2001   2281     }
  2002   2282   
  2003   2283     for(i=0; i<NCELL(pRight); i++){
  2004   2284       i64 iRowid = nodeGetRowid(pRtree, pRight, i);
................................................................................
  2034   2314   splitnode_out:
  2035   2315     nodeRelease(pRtree, pRight);
  2036   2316     nodeRelease(pRtree, pLeft);
  2037   2317     sqlite3_free(aCell);
  2038   2318     return rc;
  2039   2319   }
  2040   2320   
         2321  +/*
         2322  +** If node pLeaf is not the root of the r-tree and its pParent pointer is 
         2323  +** still NULL, load all ancestor nodes of pLeaf into memory and populate
         2324  +** the pLeaf->pParent chain all the way up to the root node.
         2325  +**
         2326  +** This operation is required when a row is deleted (or updated - an update
         2327  +** is implemented as a delete followed by an insert). SQLite provides the
         2328  +** rowid of the row to delete, which can be used to find the leaf on which
         2329  +** the entry resides (argument pLeaf). Once the leaf is located, this 
         2330  +** function is called to determine its ancestry.
         2331  +*/
  2041   2332   static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
  2042   2333     int rc = SQLITE_OK;
  2043         -  if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
  2044         -    sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
  2045         -    if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){
  2046         -      i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
  2047         -      rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
  2048         -    }else{
  2049         -      rc = SQLITE_ERROR;
         2334  +  RtreeNode *pChild = pLeaf;
         2335  +  while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
         2336  +    int rc2 = SQLITE_OK;          /* sqlite3_reset() return code */
         2337  +    sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
         2338  +    rc = sqlite3_step(pRtree->pReadParent);
         2339  +    if( rc==SQLITE_ROW ){
         2340  +      RtreeNode *pTest;           /* Used to test for reference loops */
         2341  +      i64 iNode;                  /* Node number of parent node */
         2342  +
         2343  +      /* Before setting pChild->pParent, test that we are not creating a
         2344  +      ** loop of references (as we would if, say, pChild==pParent). We don't
         2345  +      ** want to do this as it leads to a memory leak when trying to delete
         2346  +      ** the referenced counted node structures.
         2347  +      */
         2348  +      iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
         2349  +      for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
         2350  +      if( !pTest ){
         2351  +        rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);
         2352  +      }
  2050   2353       }
  2051         -    sqlite3_reset(pRtree->pReadParent);
  2052         -    if( rc==SQLITE_OK ){
  2053         -      rc = fixLeafParent(pRtree, pLeaf->pParent);
  2054         -    }
         2354  +    rc = sqlite3_reset(pRtree->pReadParent);
         2355  +    if( rc==SQLITE_OK ) rc = rc2;
         2356  +    if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT;
         2357  +    pChild = pChild->pParent;
  2055   2358     }
  2056   2359     return rc;
  2057   2360   }
  2058   2361   
  2059   2362   static int deleteCell(Rtree *, RtreeNode *, int, int);
  2060   2363   
  2061   2364   static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
  2062   2365     int rc;
         2366  +  int rc2;
  2063   2367     RtreeNode *pParent;
  2064   2368     int iCell;
  2065   2369   
  2066   2370     assert( pNode->nRef==1 );
  2067   2371   
  2068   2372     /* Remove the entry in the parent cell. */
  2069         -  iCell = nodeParentIndex(pRtree, pNode);
  2070         -  pParent = pNode->pParent;
  2071         -  pNode->pParent = 0;
  2072         -  if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1)) 
  2073         -   || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
  2074         -  ){
         2373  +  rc = nodeParentIndex(pRtree, pNode, &iCell);
         2374  +  if( rc==SQLITE_OK ){
         2375  +    pParent = pNode->pParent;
         2376  +    pNode->pParent = 0;
         2377  +    rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
         2378  +  }
         2379  +  rc2 = nodeRelease(pRtree, pParent);
         2380  +  if( rc==SQLITE_OK ){
         2381  +    rc = rc2;
         2382  +  }
         2383  +  if( rc!=SQLITE_OK ){
  2075   2384       return rc;
  2076   2385     }
  2077   2386   
  2078   2387     /* Remove the xxx_node entry. */
  2079   2388     sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
  2080   2389     sqlite3_step(pRtree->pDeleteNode);
  2081   2390     if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
................................................................................
  2097   2406     pNode->pNext = pRtree->pDeleted;
  2098   2407     pNode->nRef++;
  2099   2408     pRtree->pDeleted = pNode;
  2100   2409   
  2101   2410     return SQLITE_OK;
  2102   2411   }
  2103   2412   
  2104         -static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
         2413  +static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
  2105   2414     RtreeNode *pParent = pNode->pParent;
         2415  +  int rc = SQLITE_OK; 
  2106   2416     if( pParent ){
  2107   2417       int ii; 
  2108   2418       int nCell = NCELL(pNode);
  2109   2419       RtreeCell box;                            /* Bounding box for pNode */
  2110   2420       nodeGetCell(pRtree, pNode, 0, &box);
  2111   2421       for(ii=1; ii<nCell; ii++){
  2112   2422         RtreeCell cell;
  2113   2423         nodeGetCell(pRtree, pNode, ii, &cell);
  2114   2424         cellUnion(pRtree, &box, &cell);
  2115   2425       }
  2116   2426       box.iRowid = pNode->iNode;
  2117         -    ii = nodeParentIndex(pRtree, pNode);
  2118         -    nodeOverwriteCell(pRtree, pParent, &box, ii);
  2119         -    fixBoundingBox(pRtree, pParent);
         2427  +    rc = nodeParentIndex(pRtree, pNode, &ii);
         2428  +    if( rc==SQLITE_OK ){
         2429  +      nodeOverwriteCell(pRtree, pParent, &box, ii);
         2430  +      rc = fixBoundingBox(pRtree, pParent);
         2431  +    }
  2120   2432     }
         2433  +  return rc;
  2121   2434   }
  2122   2435   
  2123   2436   /*
  2124   2437   ** Delete the cell at index iCell of node pNode. After removing the
  2125   2438   ** cell, adjust the r-tree data structure if required.
  2126   2439   */
  2127   2440   static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
         2441  +  RtreeNode *pParent;
  2128   2442     int rc;
  2129   2443   
  2130   2444     if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
  2131   2445       return rc;
  2132   2446     }
  2133   2447   
  2134   2448     /* Remove the cell from the node. This call just moves bytes around
................................................................................
  2137   2451     nodeDeleteCell(pRtree, pNode, iCell);
  2138   2452   
  2139   2453     /* If the node is not the tree root and now has less than the minimum
  2140   2454     ** number of cells, remove it from the tree. Otherwise, update the
  2141   2455     ** cell in the parent node so that it tightly contains the updated
  2142   2456     ** node.
  2143   2457     */
  2144         -  if( pNode->iNode!=1 ){
  2145         -    RtreeNode *pParent = pNode->pParent;
  2146         -    if( (pParent->iNode!=1 || NCELL(pParent)!=1) 
  2147         -     && (NCELL(pNode)<RTREE_MINCELLS(pRtree))
  2148         -    ){
         2458  +  pParent = pNode->pParent;
         2459  +  assert( pParent || pNode->iNode==1 );
         2460  +  if( pParent ){
         2461  +    if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
  2149   2462         rc = removeNode(pRtree, pNode, iHeight);
  2150   2463       }else{
  2151         -      fixBoundingBox(pRtree, pNode);
         2464  +      rc = fixBoundingBox(pRtree, pNode);
  2152   2465       }
  2153   2466     }
  2154   2467   
  2155   2468     return rc;
  2156   2469   }
  2157   2470   
  2158   2471   static int Reinsert(
................................................................................
  2227   2540           rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
  2228   2541         }else{
  2229   2542           rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
  2230   2543         }
  2231   2544       }
  2232   2545     }
  2233   2546     if( rc==SQLITE_OK ){
  2234         -    fixBoundingBox(pRtree, pNode);
         2547  +    rc = fixBoundingBox(pRtree, pNode);
  2235   2548     }
  2236   2549     for(; rc==SQLITE_OK && ii<nCell; ii++){
  2237   2550       /* Find a node to store this cell in. pNode->iNode currently contains
  2238   2551       ** the height of the sub-tree headed by the cell.
  2239   2552       */
  2240   2553       RtreeNode *pInsert;
  2241   2554       RtreeCell *p = &aCell[aOrder[ii]];
................................................................................
  2281   2594         pRtree->iReinsertHeight = iHeight;
  2282   2595         rc = Reinsert(pRtree, pNode, pCell, iHeight);
  2283   2596       }
  2284   2597   #else
  2285   2598       rc = SplitNode(pRtree, pNode, pCell, iHeight);
  2286   2599   #endif
  2287   2600     }else{
  2288         -    AdjustTree(pRtree, pNode, pCell);
  2289         -    if( iHeight==0 ){
  2290         -      rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
  2291         -    }else{
  2292         -      rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
         2601  +    rc = AdjustTree(pRtree, pNode, pCell);
         2602  +    if( rc==SQLITE_OK ){
         2603  +      if( iHeight==0 ){
         2604  +        rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
         2605  +      }else{
         2606  +        rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
         2607  +      }
  2293   2608       }
  2294   2609     }
  2295   2610     return rc;
  2296   2611   }
  2297   2612   
  2298   2613   static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
  2299   2614     int ii;
................................................................................
  2355   2670   ){
  2356   2671     Rtree *pRtree = (Rtree *)pVtab;
  2357   2672     int rc = SQLITE_OK;
  2358   2673   
  2359   2674     rtreeReference(pRtree);
  2360   2675   
  2361   2676     assert(nData>=1);
  2362         -  assert(hashIsEmpty(pRtree));
  2363   2677   
  2364   2678     /* If azData[0] is not an SQL NULL value, it is the rowid of a
  2365   2679     ** record to delete from the r-tree table. The following block does
  2366   2680     ** just that.
  2367   2681     */
  2368   2682     if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
  2369   2683       i64 iDelete;                /* The rowid to delete */
................................................................................
  2381   2695         iDelete = sqlite3_value_int64(azData[0]);
  2382   2696         rc = findLeafNode(pRtree, iDelete, &pLeaf);
  2383   2697       }
  2384   2698   
  2385   2699       /* Delete the cell in question from the leaf node. */
  2386   2700       if( rc==SQLITE_OK ){
  2387   2701         int rc2;
  2388         -      iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
  2389         -      rc = deleteCell(pRtree, pLeaf, iCell, 0);
         2702  +      rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
         2703  +      if( rc==SQLITE_OK ){
         2704  +        rc = deleteCell(pRtree, pLeaf, iCell, 0);
         2705  +      }
  2390   2706         rc2 = nodeRelease(pRtree, pLeaf);
  2391   2707         if( rc==SQLITE_OK ){
  2392   2708           rc = rc2;
  2393   2709         }
  2394   2710       }
  2395   2711   
  2396   2712       /* Delete the corresponding entry in the <rtree>_rowid table. */
................................................................................
  2404   2720       ** it, schedule the contents of the child for reinsertion and 
  2405   2721       ** reduce the tree height by one.
  2406   2722       **
  2407   2723       ** This is equivalent to copying the contents of the child into
  2408   2724       ** the root node (the operation that Gutman's paper says to perform 
  2409   2725       ** in this scenario).
  2410   2726       */
  2411         -    if( rc==SQLITE_OK && pRtree->iDepth>0 ){
  2412         -      if( rc==SQLITE_OK && NCELL(pRoot)==1 ){
  2413         -        RtreeNode *pChild;
  2414         -        i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
  2415         -        rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
  2416         -        if( rc==SQLITE_OK ){
  2417         -          rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
  2418         -        }
  2419         -        if( rc==SQLITE_OK ){
  2420         -          pRtree->iDepth--;
  2421         -          writeInt16(pRoot->zData, pRtree->iDepth);
  2422         -          pRoot->isDirty = 1;
  2423         -        }
         2727  +    if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){
         2728  +      int rc2;
         2729  +      RtreeNode *pChild;
         2730  +      i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
         2731  +      rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
         2732  +      if( rc==SQLITE_OK ){
         2733  +        rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
         2734  +      }
         2735  +      rc2 = nodeRelease(pRtree, pChild);
         2736  +      if( rc==SQLITE_OK ) rc = rc2;
         2737  +      if( rc==SQLITE_OK ){
         2738  +        pRtree->iDepth--;
         2739  +        writeInt16(pRoot->zData, pRtree->iDepth);
         2740  +        pRoot->isDirty = 1;
  2424   2741         }
  2425   2742       }
  2426   2743   
  2427   2744       /* Re-insert the contents of any underfull nodes removed from the tree. */
  2428   2745       for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
  2429   2746         if( rc==SQLITE_OK ){
  2430   2747           rc = reinsertNodeContent(pRtree, pLeaf);
................................................................................
  2482   2799         if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
  2483   2800           sqlite3_reset(pRtree->pReadRowid);
  2484   2801           rc = SQLITE_CONSTRAINT;
  2485   2802           goto constraint;
  2486   2803         }
  2487   2804         rc = sqlite3_reset(pRtree->pReadRowid);
  2488   2805       }
         2806  +    *pRowid = cell.iRowid;
  2489   2807   
  2490   2808       if( rc==SQLITE_OK ){
  2491   2809         rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
  2492   2810       }
  2493   2811       if( rc==SQLITE_OK ){
  2494   2812         int rc2;
  2495   2813         pRtree->iReinsertHeight = -1;
................................................................................
  2705   3023     char **pzErr,                       /* OUT: Error message, if any */
  2706   3024     int isCreate                        /* True for xCreate, false for xConnect */
  2707   3025   ){
  2708   3026     int rc = SQLITE_OK;
  2709   3027     Rtree *pRtree;
  2710   3028     int nDb;              /* Length of string argv[1] */
  2711   3029     int nName;            /* Length of string argv[2] */
  2712         -  int eCoordType = (int)pAux;
         3030  +  int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
  2713   3031   
  2714   3032     const char *aErrMsg[] = {
  2715   3033       0,                                                    /* 0 */
  2716   3034       "Wrong number of columns for an rtree table",         /* 1 */
  2717   3035       "Too few columns for an rtree table",                 /* 2 */
  2718   3036       "Too many columns for an rtree table"                 /* 3 */
  2719   3037     };
................................................................................
  2851   3169   
  2852   3170   /*
  2853   3171   ** Register the r-tree module with database handle db. This creates the
  2854   3172   ** virtual table module "rtree" and the debugging/analysis scalar 
  2855   3173   ** function "rtreenode".
  2856   3174   */
  2857   3175   int sqlite3RtreeInit(sqlite3 *db){
  2858         -  int rc = SQLITE_OK;
         3176  +  const int utf8 = SQLITE_UTF8;
         3177  +  int rc;
  2859   3178   
  2860         -  if( rc==SQLITE_OK ){
  2861         -    int utf8 = SQLITE_UTF8;
  2862         -    rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  2863         -  }
         3179  +  rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  2864   3180     if( rc==SQLITE_OK ){
  2865   3181       int utf8 = SQLITE_UTF8;
  2866   3182       rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  2867   3183     }
  2868   3184     if( rc==SQLITE_OK ){
  2869   3185       void *c = (void *)RTREE_COORD_REAL32;
  2870   3186       rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
................................................................................
  2872   3188     if( rc==SQLITE_OK ){
  2873   3189       void *c = (void *)RTREE_COORD_INT32;
  2874   3190       rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
  2875   3191     }
  2876   3192   
  2877   3193     return rc;
  2878   3194   }
         3195  +
         3196  +/*
         3197  +** A version of sqlite3_free() that can be used as a callback. This is used
         3198  +** in two places - as the destructor for the blob value returned by the
         3199  +** invocation of a geometry function, and as the destructor for the geometry
         3200  +** functions themselves.
         3201  +*/
         3202  +static void doSqlite3Free(void *p){
         3203  +  sqlite3_free(p);
         3204  +}
         3205  +
         3206  +/*
         3207  +** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
         3208  +** scalar user function. This C function is the callback used for all such
         3209  +** registered SQL functions.
         3210  +**
         3211  +** The scalar user functions return a blob that is interpreted by r-tree
         3212  +** table MATCH operators.
         3213  +*/
         3214  +static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
         3215  +  RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
         3216  +  RtreeMatchArg *pBlob;
         3217  +  int nBlob;
         3218  +
         3219  +  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
         3220  +  pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
         3221  +  if( !pBlob ){
         3222  +    sqlite3_result_error_nomem(ctx);
         3223  +  }else{
         3224  +    int i;
         3225  +    pBlob->magic = RTREE_GEOMETRY_MAGIC;
         3226  +    pBlob->xGeom = pGeomCtx->xGeom;
         3227  +    pBlob->pContext = pGeomCtx->pContext;
         3228  +    pBlob->nParam = nArg;
         3229  +    for(i=0; i<nArg; i++){
         3230  +      pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
         3231  +    }
         3232  +    sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
         3233  +  }
         3234  +}
         3235  +
         3236  +/*
         3237  +** Register a new geometry function for use with the r-tree MATCH operator.
         3238  +*/
         3239  +int sqlite3_rtree_geometry_callback(
         3240  +  sqlite3 *db,
         3241  +  const char *zGeom,
         3242  +  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
         3243  +  void *pContext
         3244  +){
         3245  +#if 0
         3246  +  RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
         3247  +
         3248  +  /* Allocate and populate the context object. */
         3249  +  pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
         3250  +  if( !pGeomCtx ) return SQLITE_NOMEM;
         3251  +  pGeomCtx->xGeom = xGeom;
         3252  +  pGeomCtx->pContext = pContext;
         3253  +
         3254  +  /* Create the new user-function. Register a destructor function to delete
         3255  +  ** the context object when it is no longer required.  */
         3256  +  return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
         3257  +      (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
         3258  +  );
         3259  +#endif
         3260  +  return SQLITE_MISUSE;
         3261  +}
  2879   3262   
  2880   3263   #if !SQLITE_CORE
  2881   3264   int sqlite3_extension_init(
  2882   3265     sqlite3 *db,
  2883   3266     char **pzErrMsg,
  2884   3267     const sqlite3_api_routines *pApi
  2885   3268   ){
  2886   3269     SQLITE_EXTENSION_INIT2(pApi)
  2887   3270     return sqlite3RtreeInit(db);
  2888   3271   }
  2889   3272   #endif
  2890   3273   
  2891   3274   #endif

Added ext/rtree/sqlite3rtree.h.

            1  +/*
            2  +** 2010 August 30
            3  +**
            4  +** The author disclaims copyright to this source code.  In place of
            5  +** a legal notice, here is a blessing:
            6  +**
            7  +**    May you do good and not evil.
            8  +**    May you find forgiveness for yourself and forgive others.
            9  +**    May you share freely, never taking more than you give.
           10  +**
           11  +*************************************************************************
           12  +*/
           13  +
           14  +#ifndef _SQLITE3RTREE_H_
           15  +#define _SQLITE3RTREE_H_
           16  +
           17  +#include <sqlite3.h>
           18  +
           19  +#ifdef __cplusplus
           20  +extern "C" {
           21  +#endif
           22  +
           23  +typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
           24  +
           25  +/*
           26  +** Register a geometry callback named zGeom that can be used as part of an
           27  +** R-Tree geometry query as follows:
           28  +**
           29  +**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...)
           30  +*/
           31  +int sqlite3_rtree_geometry_callback(
           32  +  sqlite3 *db,
           33  +  const char *zGeom,
           34  +  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
           35  +  void *pContext
           36  +);
           37  +
           38  +
           39  +/*
           40  +** A pointer to a structure of the following type is passed as the first
           41  +** argument to callbacks registered using rtree_geometry_callback().
           42  +*/
           43  +struct sqlite3_rtree_geometry {
           44  +  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
           45  +  int nParam;                     /* Size of array aParam[] */
           46  +  double *aParam;                 /* Parameters passed to SQL geom function */
           47  +  void *pUser;                    /* Callback implementation user data */
           48  +  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
           49  +};
           50  +
           51  +
           52  +#ifdef __cplusplus
           53  +}  /* end of the 'extern "C"' block */
           54  +#endif
           55  +
           56  +#endif  /* ifndef _SQLITE3RTREE_H_ */