SQLite

  geopolyFilter,              /* xFilter - configure scan constraints */
  rtreeNext,                  /* xNext - advance a cursor */
  rtreeEof,                   /* xEof */
  geopolyColumn,              /* xColumn - read data */
  rtreeRowid,                 /* xRowid - read data */
  geopolyUpdate,              /* xUpdate - write data */
  rtreeBeginTransaction,      /* xBegin - begin transaction */
  rtreeEndTransaction,        /* xSync - sync transaction */
  rtreeEndTransaction,        /* xCommit - commit transaction */
  rtreeEndTransaction,        /* xRollback - rollback transaction */
  rtreeCommit,                /* xSync - sync transaction */
  rtreeCommit,                /* xCommit - commit transaction */
  rtreeRollback,              /* xRollback - rollback transaction */
  geopolyFindFunction,        /* xFindFunction - function overloading */
  rtreeRename,                /* xRename - rename the table */
  rtreeSavepoint,             /* xSavepoint */
  0,                          /* xRelease */
  0,                          /* xRollbackTo */
  rtreeCacheWrite,            /* xRelease */
  rtreeCacheAbandon,          /* xRollbackTo */
  rtreeShadowName             /* xShadowName */
};

static int sqlite3_geopoly_init(sqlite3 *db){
  int rc = SQLITE_OK;
  static const struct {
    void (*xFunc)(sqlite3_context*,int,sqlite3_value**);

typedef struct RtreeNode RtreeNode;
typedef struct RtreeCell RtreeCell;
typedef struct RtreeConstraint RtreeConstraint;
typedef struct RtreeMatchArg RtreeMatchArg;
typedef struct RtreeGeomCallback RtreeGeomCallback;
typedef union RtreeCoord RtreeCoord;
typedef struct RtreeSearchPoint RtreeSearchPoint;
typedef struct RtreeGlobal RtreeGlobal;

/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
#define RTREE_MAX_DIMENSIONS 5

/* Maximum number of auxiliary columns */
#define RTREE_MAX_AUX_COLUMN 100

/* Size of hash table Rtree.aHash. This hash table is not expected to
/* Initial size of hash table Rtree.aHash.  */
** ever contain very many entries, so a fixed number of buckets is 
** used.
*/
#define HASHSIZE 97
#define INITIAL_HASHSIZE 97

/* The xBestIndex method of this virtual table requires an estimate of
** the number of rows in the virtual table to calculate the costs of
** various strategies. If possible, this estimate is loaded from the
** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum).
** Otherwise, if no sqlite_stat1 entry is available, use 
** RTREE_DEFAULT_ROWEST.
*/
#define RTREE_DEFAULT_ROWEST 1048576
#define RTREE_MIN_ROWEST         100

/*
** There is one instance of this structure for each database handle (sqlite3*)
** that the rtree extension is registered with. It is used to allow the
** rtreecheck() function to locate the Rtree structure it is operating on.
*/
struct RtreeGlobal {
  Rtree *pGlobalRtree;            /* List of all Rtree structures for this db */
  int nGlobalRef;                 /* Number of pointers to this structure */
};

/* 
** An rtree virtual-table object.
*/
struct Rtree {
  sqlite3_vtab base;          /* Base class.  Must be first */
  sqlite3 *db;                /* Host database connection */

  sqlite3_stmt *pReadParent;
  sqlite3_stmt *pWriteParent;
  sqlite3_stmt *pDeleteParent;

  /* Statement for writing to the "aux:" fields, if there are any */
  sqlite3_stmt *pWriteAux;

  int nHashSize;              /* Number of hash buckets */
  int nHashEntry;             /* Number of entries in hash table */
  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
  RtreeNode **aHash;          /* Hash table of in-memory nodes. */ 

  RtreeGlobal *pGlobal;       /* Database-wide object */
  Rtree *pGlobalNext;         /* Next in RtreeGlobal.pGlobalNext */
};

/* Possible values for Rtree.eCoordType: */
#define RTREE_COORD_REAL32 0
#define RTREE_COORD_INT32  1

/*

# define RTREE_ZERO 0.0
#endif

/*
** Set the Rtree.bCorrupt flag
*/
#ifdef SQLITE_DEBUG
static void rtreeIsCorrupt(Rtree *pRtree){
  pRtree->bCorrupt = 1;
}
# define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1)
# define RTREE_IS_CORRUPT(X) rtreeIsCorrupt(X)
#else
# define RTREE_IS_CORRUPT(X)
#endif

/*
** When doing a search of an r-tree, instances of the following structure
** record intermediate results from the tree walk.

** are used in the cursor for contraints such as x=NULL (RTREE_FALSE) or
** x<'xyz' (RTREE_TRUE) */
#define RTREE_TRUE  0x3f  /* ? */
#define RTREE_FALSE 0x40  /* @ */

/* 
** An rtree structure node.
**
** bDel:
**  This node is not in the hash table. It should be freed when its 
**  ref-count reaches 0.
*/
struct RtreeNode {
  RtreeNode *pParent;         /* Parent node */
  i64 iNode;                  /* The node number */
  int nRef;                   /* Number of references to this node */
  u8 bDel;
  int isDirty;                /* True if the node needs to be written to disk */
  u8 isDirty;                 /* True if the node needs to be written to disk */
  u8 *zData;                  /* Content of the node, as should be on disk */
  RtreeNode *pNext;           /* Next node in this hash collision chain */
};

/* Return the number of cells in a node  */
#define NCELL(pNode) readInt16(&(pNode)->zData[2])

  p->isDirty = 1;
}

/*
** Given a node number iNode, return the corresponding key to use
** in the Rtree.aHash table.
*/
static unsigned int nodeHash(i64 iNode){
  return ((unsigned)iNode) % HASHSIZE;
static unsigned int nodeHash(Rtree *pRtree, i64 iNode){
  return ((unsigned)iNode) % pRtree->nHashSize;
}

/*
** Search the node hash table for node iNode. If found, return a pointer
** to it. Otherwise, return 0.
*/
static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){
  RtreeNode *p;
  for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
  for(p=pRtree->aHash[nodeHash(pRtree, iNode)]; p&&p->iNode!=iNode; p=p->pNext);
  return p;
}

/*
** Add node pNode to the node hash table.
*/
static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
  int iHash;
  assert( pNode->pNext==0 );
  assert( pNode->pParent==0 || pNode->nRef>0 );
  assert( pNode->bDel==0 );

  if( pRtree->nHashEntry>pRtree->nHashSize ){
    int nNew = pRtree->nHashSize * 2;
    RtreeNode **aNew = (RtreeNode**)sqlite3_malloc64(sizeof(RtreeNode*)*nNew);
    if( aNew ){
      int ii;
      memset(aNew, 0, sizeof(RtreeNode*)*nNew);
      for(ii=0; ii<pRtree->nHashSize; ii++){
        RtreeNode *p, *pNext;
        for(p=pRtree->aHash[ii]; p; p=pNext){
          int iBucket = p->iNode % nNew;
          pNext = p->pNext;
          p->pNext = aNew[iBucket];
          aNew[iBucket] = p;
        }
      }

      sqlite3_free(pRtree->aHash);
      pRtree->aHash = aNew;
      pRtree->nHashSize = nNew;
    }
  }

  iHash = nodeHash(pNode->iNode);
  iHash = nodeHash(pRtree, pNode->iNode);
  pNode->pNext = pRtree->aHash[iHash];
  pRtree->aHash[iHash] = pNode;
  pRtree->nHashEntry++;
}

/*
** Remove node pNode from the node hash table.
*/
static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
  RtreeNode **pp;
  if( pNode->iNode!=0 ){
    pp = &pRtree->aHash[nodeHash(pNode->iNode)];
    pp = &pRtree->aHash[nodeHash(pRtree, pNode->iNode)];
    for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
    *pp = pNode->pNext;
    pNode->pNext = 0;
    pRtree->nHashEntry--;
  }
}

/*
** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
** indicating that node has not yet been assigned a node number. It is
** assigned a node number when nodeWrite() is called to write the
** node contents out to the database.
*/
static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
  RtreeNode *pNode;
  pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode) + pRtree->iNodeSize);
  if( pNode ){
    memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
    pNode->zData = (u8 *)&pNode[1];
    pNode->nRef = 1;
    pRtree->nNodeRef++;
    pNode->pParent = pParent;
    pNode->isDirty = 1;
    pNode->bDel = 1;
    nodeReference(pParent);
  }
  return pNode;
}

/*
** Clear the Rtree.pNodeBlob object

  int rc = SQLITE_OK;
  RtreeNode *pNode = 0;

  /* Check if the requested node is already in the hash table. If so,
  ** increase its reference count and return it.
  */
  if( (pNode = nodeHashLookup(pRtree, iNode))!=0 ){
    assert( pNode->pParent==0 || pNode->nRef>0 );
    if( pNode->nRef==0 ){
      pNode->pParent = pParent;
      nodeReference(pParent);
    }else{
    if( pParent && pParent!=pNode->pParent ){
      RTREE_IS_CORRUPT(pRtree);
      return SQLITE_CORRUPT_VTAB;
    }
      if( pParent && pParent!=pNode->pParent ){
        RTREE_IS_CORRUPT(pRtree);
        return SQLITE_CORRUPT_VTAB;
      }
    }
    if( pNode->nRef==0 ) pRtree->nNodeRef++;
    pNode->nRef++;
    *ppNode = pNode;
    if( iNode==1 ) pRtree->iDepth = readInt16(pNode->zData);
    return SQLITE_OK;
  }

  if( pRtree->pNodeBlob ){
    sqlite3_blob *pBlob = pRtree->pNodeBlob;
    pRtree->pNodeBlob = 0;
    rc = sqlite3_blob_reopen(pBlob, iNode);

      RTREE_IS_CORRUPT(pRtree);
    }
  }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){
    pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode)+pRtree->iNodeSize);
    if( !pNode ){
      rc = SQLITE_NOMEM;
    }else{
      pNode->pParent = pParent;
      pNode->zData = (u8 *)&pNode[1];
      pNode->nRef = 1;
      pRtree->nNodeRef++;
      pNode->iNode = iNode;
      pNode->isDirty = 0;
      pNode->pNext = 0;
      pNode->bDel = 0;
      rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData,
                             pRtree->iNodeSize, 0);
    }
  }

  /* If the root node was just loaded, set pRtree->iDepth to the height
  ** of the r-tree structure. A height of zero means all data is stored on

      rc = SQLITE_CORRUPT_VTAB;
      RTREE_IS_CORRUPT(pRtree);
    }
  }

  if( rc==SQLITE_OK ){
    if( pNode!=0 ){
      pNode->pParent = pParent;
      nodeReference(pParent);
      nodeHashInsert(pRtree, pNode);
    }else{
      rc = SQLITE_CORRUPT_VTAB;
      RTREE_IS_CORRUPT(pRtree);
    }
    *ppNode = pNode;

    }
    sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
    sqlite3_step(p);
    pNode->isDirty = 0;
    rc = sqlite3_reset(p);
    sqlite3_bind_null(p, 2);
    if( pNode->iNode==0 && rc==SQLITE_OK ){
      pNode->bDel = 0;
      pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
      nodeHashInsert(pRtree, pNode);
    }
  }
  return rc;
}

/*
** Write all dirty nodes out to disk.
*/
static int rtreeFlushCache(Rtree *pRtree){
  int i;
  int rc = SQLITE_OK;
  i64 iLIR = sqlite3_last_insert_rowid(pRtree->db);
  for(i=0; i<pRtree->nHashSize && rc==SQLITE_OK; i++){
    RtreeNode *pNode;
    for(pNode=pRtree->aHash[i]; pNode; pNode=pNode->pNext){
      if( pNode->isDirty ){
         rc = nodeWrite(pRtree, pNode);
         if( rc ) break;
      }
    }
  }
  sqlite3_set_last_insert_rowid(pRtree->db, iLIR);
  return rc;
}

/*
** Scan the hash table.  Verify that every hash table entry has nRef==0
** and remove them.  Any dirty pages are written if writeDirty is true.
*/
static int rtreeResetHashTable(Rtree *pRtree, int writeDirty){
  int i;
  int rc = SQLITE_OK;
  for(i=0; i<pRtree->nHashSize; i++){
    RtreeNode *pNode = pRtree->aHash[i];
    RtreeNode *pNext;
    if( pNode==0 ) continue;
    while( 1 /*exit-by-break*/ ){
      pNext = pNode->pNext;
      if( pNode->isDirty && writeDirty ){
         rc = nodeWrite(pRtree, pNode);
         if( rc ) writeDirty = 0;
      }
      if( pNode->nRef==0 ){
        sqlite3_free(pNode);
      }else{
        pNode->isDirty = 0;
        pNode->bDel = 1;
      }
      if( pNext==0 ) break;
      pNode = pNext;
    }
    pRtree->aHash[i] = 0;
  }
  pRtree->nHashEntry = 0;
  return rc;
}

/*
** Release a reference to a node. If the node is dirty and the reference
** count drops to zero, the node data is written to the database.
*/
static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
  int rc = SQLITE_OK;
  if( pNode ){
    assert( pNode->nRef>0 );
    assert( pRtree->nNodeRef>0 );
    pNode->nRef--;
    if( pNode->nRef==0 ){
      pRtree->nNodeRef--;
      if( pNode->iNode==1 ){
        pRtree->iDepth = -1;
      }
      if( pNode->pParent ){
        rc = nodeRelease(pRtree, pNode->pParent);
        pNode->pParent = 0;
      }
      if( pNode->bDel ){
        sqlite3_free(pNode);
      }
#if 0
      if( rc==SQLITE_OK ){
        rc = nodeWrite(pRtree, pNode);
      }
      nodeHashDelete(pRtree, pNode);
      sqlite3_free(pNode);
#endif
    }
  }
  return rc;
}

/*
** Return the 64-bit integer value associated with cell iCell of

*/
static void rtreeRelease(Rtree *pRtree){
  pRtree->nBusy--;
  if( pRtree->nBusy==0 ){
    pRtree->inWrTrans = 0;
    assert( pRtree->nCursor==0 );
    nodeBlobReset(pRtree);
    rtreeResetHashTable(pRtree, 0);
    assert( pRtree->nNodeRef==0 || pRtree->bCorrupt );
    sqlite3_finalize(pRtree->pWriteNode);
    sqlite3_finalize(pRtree->pDeleteNode);
    sqlite3_finalize(pRtree->pReadRowid);
    sqlite3_finalize(pRtree->pWriteRowid);
    sqlite3_finalize(pRtree->pDeleteRowid);
    sqlite3_finalize(pRtree->pReadParent);
    sqlite3_finalize(pRtree->pWriteParent);
    sqlite3_finalize(pRtree->pDeleteParent);
    sqlite3_finalize(pRtree->pWriteAux);
    sqlite3_free(pRtree->zReadAuxSql);
    sqlite3_free(pRtree->aHash);

    /* Remove this object from the global list. */
    if( pRtree->pGlobal ){
      Rtree **pp;
      for(pp=&pRtree->pGlobal->pGlobalRtree;*pp!=pRtree;pp=&(*pp)->pGlobalNext);
      *pp = pRtree->pGlobalNext;
    }

    sqlite3_free(pRtree);
  }
}

/* 
** Rtree virtual table module xDisconnect method.
*/

  RtreeCursor *pCsr = (RtreeCursor *)cur;
  assert( pRtree->nCursor>0 );
  resetCursor(pCsr);
  sqlite3_finalize(pCsr->pReadAux);
  sqlite3_free(pCsr);
  pRtree->nCursor--;
  nodeBlobReset(pRtree);
  if( pRtree->inWrTrans==0 && pRtree->nCursor==0 ){
    /* If this was the last open cursor, and there is no write-transaction,
    ** discard the contents of the node-cache.  */
    rtreeResetHashTable(pRtree, 0);
  }
  return SQLITE_OK;
}

/*
** Rtree virtual table module xEof method.
**
** Return non-zero if the cursor does not currently point to a valid 

  xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
  if( iHeight>0 ){
    RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
    RtreeNode *p;
    for(p=pNode; p; p=p->pParent){
      if( p==pChild ) return SQLITE_CORRUPT_VTAB;
    }
    if( pChild ){
    if( pChild && pChild->nRef>0 ){
      nodeRelease(pRtree, pChild->pParent);
      nodeReference(pNode);
      pChild->pParent = pNode;
    }
  }
  if( NEVER(pNode==0) ) return SQLITE_ERROR;
  return xSetMapping(pRtree, iRowid, pNode->iNode);

  RtreeNode *pNode,
  RtreeCell *pCell,
  int iHeight
){
  int rc = SQLITE_OK;
  if( iHeight>0 ){
    RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
    if( pChild ){
    if( pChild && pChild->nRef>0 ){
      nodeRelease(pRtree, pChild->pParent);
      nodeReference(pNode);
      pChild->pParent = pNode;
    }
  }
  if( nodeInsertCell(pRtree, pNode, pCell) ){
    if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){

  sqlite3_value **aData, 
  sqlite_int64 *pRowid
){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;
  RtreeCell cell;                 /* New cell to insert if nData>1 */
  int bHaveRowid = 0;             /* Set to 1 after new rowid is determined */
  i64 iLIR = sqlite3_last_insert_rowid(pRtree->db);

#ifdef SQLITE_DEBUG
  int nNodeRefSave = pRtree->nNodeRef;
#endif

  if( pRtree->nNodeRef ){
    /* Unable to write to the btree while another cursor is reading from it,
    ** since the write might do a rebalance which would disrupt the read
    ** cursor. */
    return SQLITE_LOCKED_VTAB;
  }

      }
      sqlite3_step(pUp);
      rc = sqlite3_reset(pUp);
    }
  }

constraint:
  sqlite3_set_last_insert_rowid(pRtree->db, iLIR);
  assert( pRtree->nNodeRef==nNodeRefSave );
  rtreeRelease(pRtree);
  return rc;
}

/*
** Called when a transaction starts.
*/
static int rtreeBeginTransaction(sqlite3_vtab *pVtab){
  Rtree *pRtree = (Rtree *)pVtab;
  assert( pRtree->inWrTrans==0 );
  pRtree->inWrTrans++;
  return SQLITE_OK;
}

/*
** Called when a transaction completes (either by COMMIT or ROLLBACK).
** The sqlite3_blob object should be released at this point.
*/
static int rtreeEndTransaction(sqlite3_vtab *pVtab){
static int rtreeCommit(sqlite3_vtab *pVtab){
  int rc = SQLITE_OK;
  Rtree *pRtree = (Rtree *)pVtab;
  i64 iLIR = sqlite3_last_insert_rowid(pRtree->db);
  pRtree->inWrTrans = 0;
  nodeBlobReset(pRtree);
  rc = rtreeResetHashTable(pRtree, 1);
  sqlite3_set_last_insert_rowid(pRtree->db, iLIR);
  return rc;
}
static int rtreeRollback(sqlite3_vtab *pVtab){
  Rtree *pRtree = (Rtree *)pVtab;
  pRtree->inWrTrans = 0;
  nodeBlobReset(pRtree);
  rtreeResetHashTable(pRtree, 0);
  return SQLITE_OK;
}

/*
** Called at the end of a statement to ensure that the cache
** has been cleared and that all changes have been written.
*/
static int rtreeCacheWrite(sqlite3_vtab *pVtab, int n){
  UNUSED_PARAMETER(n);
  return rtreeFlushCache((Rtree*)pVtab);
}
static int rtreeCacheAbandon(sqlite3_vtab *pVtab, int n){
  UNUSED_PARAMETER(n);
  rtreeResetHashTable((Rtree*)pVtab, 0);
  return SQLITE_OK;
}

/*
** The xRename method for rtree module virtual tables.
*/
static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){

**     INSERT INTO rtree...
**     DROP TABLE <tablename>;    -- Would fail with SQLITE_LOCKED
**   COMMIT;
*/
static int rtreeSavepoint(sqlite3_vtab *pVtab, int iSavepoint){
  Rtree *pRtree = (Rtree *)pVtab;
  u8 iwt = pRtree->inWrTrans;
  int rc = SQLITE_OK;
  UNUSED_PARAMETER(iSavepoint);
  rc = rtreeFlushCache(pRtree);
  pRtree->inWrTrans = 0;
  nodeBlobReset(pRtree);
  pRtree->inWrTrans = iwt;
  return SQLITE_OK;
  return rc;
}

/*
** This function populates the pRtree->nRowEst variable with an estimate
** of the number of rows in the virtual table. If possible, this is based
** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
*/

  rtreeFilter,                /* xFilter - configure scan constraints */
  rtreeNext,                  /* xNext - advance a cursor */
  rtreeEof,                   /* xEof */
  rtreeColumn,                /* xColumn - read data */
  rtreeRowid,                 /* xRowid - read data */
  rtreeUpdate,                /* xUpdate - write data */
  rtreeBeginTransaction,      /* xBegin - begin transaction */
  rtreeEndTransaction,        /* xSync - sync transaction */
  rtreeEndTransaction,        /* xCommit - commit transaction */
  rtreeEndTransaction,        /* xRollback - rollback transaction */
  rtreeCommit,                /* xSync - sync transaction */
  rtreeCommit,                /* xCommit - commit transaction */
  rtreeRollback,              /* xRollback - rollback transaction */
  0,                          /* xFindFunction - function overloading */
  rtreeRename,                /* xRename - rename the table */
  rtreeSavepoint,             /* xSavepoint */
  0,                          /* xRelease */
  0,                          /* xRollbackTo */
  rtreeCacheWrite,            /* xRelease */
  rtreeCacheAbandon,          /* xRollbackTo */
  rtreeShadowName             /* xShadowName */
};

static int rtreeSqlInit(
  Rtree *pRtree, 
  sqlite3 *db, 
  const char *zDb, 

  sqlite3 *db,                        /* Database connection */
  void *pAux,                         /* One of the RTREE_COORD_* constants */
  int argc, const char *const*argv,   /* Parameters to CREATE TABLE statement */
  sqlite3_vtab **ppVtab,              /* OUT: New virtual table */
  char **pzErr,                       /* OUT: Error message, if any */
  int isCreate                        /* True for xCreate, false for xConnect */
){
  RtreeGlobal *pGlobal = (RtreeGlobal*)pAux;
  int rc = SQLITE_OK;
  Rtree *pRtree;
  int nDb;              /* Length of string argv[1] */
  int nName;            /* Length of string argv[2] */
  int eCoordType = (pAux ? RTREE_COORD_INT32 : RTREE_COORD_REAL32);
  int eCoordType = 0; 
  sqlite3_str *pSql;
  char *zSql;
  int ii = 4;
  int iErr;

  const char *aErrMsg[] = {
    0,                                                    /* 0 */
    "Wrong number of columns for an rtree table",         /* 1 */
    "Too few columns for an rtree table",                 /* 2 */
    "Too many columns for an rtree table",                /* 3 */
    "Auxiliary rtree columns must be last"                /* 4 */
  };

  eCoordType = RTREE_COORD_INT32;
#ifndef SQLITE_RTREE_INT_ONLY
  if( sqlite3_stricmp("rtree", argv[0])==0 ){
    eCoordType = RTREE_COORD_REAL32;
  }
#endif

  assert( RTREE_MAX_AUX_COLUMN<256 ); /* Aux columns counted by a u8 */
  if( argc<6 || argc>RTREE_MAX_AUX_COLUMN+3 ){
    *pzErr = sqlite3_mprintf("%s", aErrMsg[2 + (argc>=6)]);
    return SQLITE_ERROR;
  }

  pRtree->base.pModule = &rtreeModule;
  pRtree->zDb = (char *)&pRtree[1];
  pRtree->zName = &pRtree->zDb[nDb+1];
  pRtree->eCoordType = (u8)eCoordType;
  memcpy(pRtree->zDb, argv[1], nDb);
  memcpy(pRtree->zName, argv[2], nName);

  pRtree->aHash = (RtreeNode**)sqlite3_malloc64(
      sizeof(RtreeNode*) * INITIAL_HASHSIZE
  );
  if( pRtree->aHash==0 ){
    rc = SQLITE_NOMEM;
    goto rtreeInit_fail;
  }
  memset(pRtree->aHash, 0, sizeof(RtreeNode*)*INITIAL_HASHSIZE);
  pRtree->nHashSize = INITIAL_HASHSIZE;

  /* Create/Connect to the underlying relational database schema. If
  ** that is successful, call sqlite3_declare_vtab() to configure
  ** the r-tree table schema.
  */
  pSql = sqlite3_str_new(db);
  sqlite3_str_appendf(pSql, "CREATE TABLE x(%.*s INT", 

  rc = getNodeSize(db, pRtree, isCreate, pzErr);
  if( rc ) goto rtreeInit_fail;
  rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate);
  if( rc ){
    *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
    goto rtreeInit_fail;
  }

  /* Link this rtree into the global list */
  pRtree->pGlobal = pGlobal;
  pRtree->pGlobalNext = pGlobal->pGlobalRtree;
  pGlobal->pGlobalRtree = pRtree;

  *ppVtab = (sqlite3_vtab *)pRtree;
  return SQLITE_OK;

rtreeInit_fail:
  if( rc==SQLITE_OK ) rc = SQLITE_ERROR;
  assert( *ppVtab==0 );

** implementation of integrity-check function rtreecheck().
*/
typedef struct RtreeCheck RtreeCheck;
struct RtreeCheck {
  sqlite3 *db;                    /* Database handle */
  const char *zDb;                /* Database containing rtree table */
  const char *zTab;               /* Name of rtree table */
  Rtree *pRtree;                  /* Rtree object (may be NULL) */
  int bInt;                       /* True for rtree_i32 table */
  int nDim;                       /* Number of dimensions for this rtree tbl */
  sqlite3_stmt *pGetNode;         /* Statement used to retrieve nodes */
  sqlite3_stmt *aCheckMapping[2]; /* Statements to query %_parent/%_rowid */
  int nLeaf;                      /* Number of leaf cells in table */
  int nNonLeaf;                   /* Number of non-leaf cells in table */
  int rc;                         /* Return code */

**
** Or, if an error does occur, NULL is returned and an error code left
** in the RtreeCheck object. The final value of *pnNode is undefined in
** this case.
*/
static u8 *rtreeCheckGetNode(RtreeCheck *pCheck, i64 iNode, int *pnNode){
  u8 *pRet = 0;                   /* Return value */
  
  if( pCheck->pRtree ){
    RtreeNode *pNode = nodeHashLookup(pCheck->pRtree, iNode);
    if( pNode ){
      int nNode = pCheck->pRtree->iNodeSize;
      pRet = (u8*)sqlite3_malloc64(nNode);
      if( pRet==0 ){
        pCheck->rc = SQLITE_NOMEM;
      }else{
        memcpy(pRet, pNode->zData, nNode);
        *pnNode = nNode;
      }
      return pRet;
    }
  }

  if( pCheck->rc==SQLITE_OK && pCheck->pGetNode==0 ){
    pCheck->pGetNode = rtreeCheckPrepare(pCheck,
        "SELECT data FROM %Q.'%q_node' WHERE nodeno=?", 
        pCheck->zDb, pCheck->zTab
    );
  }

/*
** This function does the bulk of the work for the rtree integrity-check.
** It is called by rtreecheck(), which is the SQL function implementation.
*/
static int rtreeCheckTable(
  sqlite3 *db,                    /* Database handle to access db through */
  RtreeGlobal *pGlobal,
  const char *zDb,                /* Name of db ("main", "temp" etc.) */
  const char *zTab,               /* Name of rtree table to check */
  char **pzReport                 /* OUT: sqlite3_malloc'd report text */
){
  RtreeCheck check;               /* Common context for various routines */
  sqlite3_stmt *pStmt = 0;        /* Used to find column count of rtree table */
  int bEnd = 0;                   /* True if transaction should be closed */
  int nAux = 0;                   /* Number of extra columns. */
  Rtree *pRtree = 0;

  /* Initialize the context object */
  memset(&check, 0, sizeof(check));
  check.db = db;
  check.zDb = zDb;
  check.zTab = zTab;
  for(pRtree=pGlobal->pGlobalRtree; pRtree; pRtree=pRtree->pGlobalNext){
    if( sqlite3_stricmp(zDb, pRtree->zDb) ) continue;
    if( sqlite3_stricmp(zTab, pRtree->zName) ) continue;
    break;
  }
  check.pRtree = pRtree;

  /* If there is not already an open transaction, open one now. This is
  ** to ensure that the queries run as part of this integrity-check operate
  ** on a consistent snapshot.  */
  if( sqlite3_get_autocommit(db) ){
    check.rc = sqlite3_exec(db, "BEGIN", 0, 0, 0);
    bEnd = 1;

  sqlite3_value **apArg
){
  if( nArg!=1 && nArg!=2 ){
    sqlite3_result_error(ctx, 
        "wrong number of arguments to function rtreecheck()", -1
    );
  }else{
    sqlite3 *db = sqlite3_context_db_handle(ctx);
    RtreeGlobal *pGlobal = (RtreeGlobal*)sqlite3_user_data(ctx);
    int rc;
    char *zReport = 0;
    const char *zDb = (const char*)sqlite3_value_text(apArg[0]);
    const char *zTab;
    if( nArg==1 ){
      zTab = zDb;
      zDb = "main";
    }else{
      zTab = (const char*)sqlite3_value_text(apArg[1]);
    }
    rc = rtreeCheckTable(sqlite3_context_db_handle(ctx), zDb, zTab, &zReport);
    rc = rtreeCheckTable(db, pGlobal, zDb, zTab, &zReport);
    if( rc==SQLITE_OK ){
      sqlite3_result_text(ctx, zReport ? zReport : "ok", -1, SQLITE_TRANSIENT);
    }else{
      sqlite3_result_error_code(ctx, rc);
    }
    sqlite3_free(zReport);
  }
}

/* Conditionally include the geopoly code */
#ifdef SQLITE_ENABLE_GEOPOLY
# include "geopoly.c"
#endif

/*
** The argument passed to this function is an RtreeGlobal structure. 
** Decrement its reference count. Free the structure if it reaches 0.
*/
static void rtreeDestroyGlobal(void *p){
  RtreeGlobal *pGlobal = (RtreeGlobal*)p;
  assert( pGlobal->nGlobalRef>0 );
  if( 0==(--pGlobal->nGlobalRef) ){
    sqlite3_free(pGlobal);
  }
}

/*
** Register the r-tree module with database handle db. This creates the
** virtual table module "rtree" and the debugging/analysis scalar 
** function "rtreenode".
*/
int sqlite3RtreeInit(sqlite3 *db){
  RtreeGlobal *pGlobal = 0;
  const int utf8 = SQLITE_UTF8;
  int rc;

  rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  if( rc==SQLITE_OK ){
  pGlobal = (RtreeGlobal*)sqlite3_malloc(sizeof(*pGlobal));
  if( pGlobal==0 ) return SQLITE_NOMEM;
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }
  memset(pGlobal, 0, sizeof(*pGlobal));

  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreecheck", -1, utf8, 0,rtreecheck, 0,0);
  pGlobal->nGlobalRef++;
  rc = sqlite3_create_function_v2(db, "rtreecheck", 
  }
      -1, utf8, pGlobal, rtreecheck, 0, 0, rtreeDestroyGlobal
  );
  if( rc==SQLITE_OK ){
#ifdef SQLITE_RTREE_INT_ONLY
    void *c = (void *)RTREE_COORD_INT32;
#else
    pGlobal->nGlobalRef++;
    void *c = (void *)RTREE_COORD_REAL32;
#endif
    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
    rc = sqlite3_create_module_v2(db, "rtree", 
        &rtreeModule, pGlobal, rtreeDestroyGlobal
    );
  }
  if( rc==SQLITE_OK ){
    void *c = (void *)RTREE_COORD_INT32;
    rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
    pGlobal->nGlobalRef++;
    rc = sqlite3_create_module_v2(db, "rtree_i32", 
        &rtreeModule, pGlobal, rtreeDestroyGlobal
    );
  }
#ifdef SQLITE_ENABLE_GEOPOLY
  if( rc==SQLITE_OK ){
    rc = sqlite3_geopoly_init(db);
  }
#endif

  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  }
  if( rc==SQLITE_OK ){
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }

  return rc;
}

/*
** This routine deletes the RtreeGeomCallback object that was attached
** one of the SQL functions create by sqlite3_rtree_geometry_callback()

db null -
do_execsql_test 20.3 {
  SELECT * FROM t1 JOIN t0 ON true RIGHT JOIN rt0 ON x0>a WHERE +x0 = 0;
} {- - 0 0.0 0.0}
do_execsql_test 20.4 {
  SELECT * FROM t1 JOIN t0 ON true RIGHT JOIN rt0 ON x0>a WHERE x0 = 0;
} {- - 0 0.0 0.0}

reset_db
do_execsql_test 21.0 {
  CREATE VIRTUAL TABLE rt0 USING rtree(id, x0, x1);
  INSERT INTO rt0 VALUES(5, 10, 10);
  SELECT last_insert_rowid();
} {5}

finish_test