SQLite

  #define PickSeeds LinearPickSeeds
  #define AssignCells splitNodeGuttman
#endif
#if VARIANT_RSTARTREE_SPLIT
  #define AssignCells splitNodeStartree
#endif

#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) 
# define NDEBUG 1
#endif

#ifndef SQLITE_CORE
  #include "sqlite3ext.h"
  SQLITE_EXTENSION_INIT1
#else
  #include "sqlite3.h"
#endif

  }
}

/*
** Clear the content of node p (set all bytes to 0x00).
*/
static void nodeZero(Rtree *pRtree, RtreeNode *p){

  memset(&p->zData[2], 0, pRtree->iNodeSize-2);
  p->isDirty = 1;

}

/*
** Given a node number iNode, return the corresponding key to use
** in the Rtree.aHash table.
*/
static int nodeHash(i64 iNode){

  return p;
}

/*
** Add node pNode to the node hash table.
*/
static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){

  int iHash;
  assert( pNode->pNext==0 );
  iHash = nodeHash(pNode->iNode);
  pNode->pNext = pRtree->aHash[iHash];
  pRtree->aHash[iHash] = pNode;

}

/*
** Remove node pNode from the node hash table.
*/
static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
  RtreeNode **pp;

/*
** 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_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
  if( pNode ){
    memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
    pNode->zData = (u8 *)&pNode[1];
    pNode->nRef = 1;
    pNode->pParent = pParent;
    pNode->isDirty = 1;
    nodeReference(pParent);
  }
  return pNode;

    sqlite3_free(pNode);
    pNode = 0;
  }

  *ppNode = pNode;
  rc = sqlite3_reset(pRtree->pReadNode);

  if( pNode && iNode==1 ){
    pRtree->iDepth = readInt16(pNode->zData);
  }

  if( pNode!=0 ){
    nodeHashInsert(pRtree, pNode);
  }else if( rc==SQLITE_OK ){
    rc = SQLITE_CORRUPT;

    double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);

    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ
    );

    switch( p->op ){
      case RTREE_LE: case RTREE_LT: 
        bRes = p->rValue<cell_min; 
        break;

      case RTREE_GE: case RTREE_GT: 
        bRes = p->rValue>cell_max; 
        break;

      default: assert( p->op==RTREE_EQ );
        bRes = (p->rValue>cell_max || p->rValue<cell_min);
        break;
    }
  }

  return bRes;
}

        || p->op==RTREE_GT || p->op==RTREE_EQ
    );
    switch( p->op ){
      case RTREE_LE: res = (coord<=p->rValue); break;
      case RTREE_LT: res = (coord<p->rValue);  break;
      case RTREE_GE: res = (coord>=p->rValue); break;
      case RTREE_GT: res = (coord>p->rValue);  break;
      default:       res = (coord==p->rValue); break;
    }

    if( !res ) return 1;
  }

  return 0;
}

/* 
** Rtree virtual table module xNext method.
*/
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  int rc = SQLITE_OK;

  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
  ** already at EOF. It is against the rules to call the xNext() method of
  ** a cursor that has already reached EOF.
  */
  assert( pCsr->pNode );

  if( pCsr->iStrategy==1 ){
    /* This "scan" is a direct lookup by rowid. There is no next entry. */
    nodeRelease(pRtree, pCsr->pNode);
    pCsr->pNode = 0;
  }else{


    /* Move to the next entry that matches the configured constraints. */
    int iHeight = 0;
    while( pCsr->pNode ){
      RtreeNode *pNode = pCsr->pNode;
      int nCell = NCELL(pNode);
      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
        int isEof;

  if( idxNum==1 ){
    /* Special case - lookup by rowid. */
    RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
    i64 iRowid = sqlite3_value_int64(argv[0]);
    rc = findLeafNode(pRtree, iRowid, &pLeaf);
    pCsr->pNode = pLeaf; 
    if( pLeaf ){
      assert( rc==SQLITE_OK );
      pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
    }
  }else{
    /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
    ** with the configured constraints. 
    */
    if( argc>0 ){

  RtreeCell *aCell, 
  int nCell, 
  int iExclude
){
  int ii;
  float overlap = 0.0;
  for(ii=0; ii<nCell; ii++){
#if VARIANT_RSTARTREE_CHOOSESUBTREE
    if( ii!=iExclude )
#else
    assert( iExclude==-1 );
#endif
    {
      int jj;
      float o = 1.0;
      for(jj=0; jj<(pRtree->nDim*2); jj+=2){
        double x1;
        double x2;

        x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));

#endif

    /* Select the child node which will be enlarged the least if pCell
    ** is inserted into it. Resolve ties by choosing the entry with
    ** the smallest area.
    */
    for(iCell=0; iCell<nCell; iCell++){
      int bBest = 0;
      float growth;
      float area;
      float overlap = 0.0;
      nodeGetCell(pRtree, pNode, iCell, &cell);
      growth = cellGrowth(pRtree, &cell, pCell);
      area = cellArea(pRtree, &cell);

#if VARIANT_RSTARTREE_CHOOSESUBTREE
      if( ii==(pRtree->iDepth-1) ){
        overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
      }

      if( (iCell==0) 
       || (overlap<fMinOverlap) 
       || (overlap==fMinOverlap && growth<fMinGrowth)
       || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
      ){
        bBest = 1;
      }
#else
      if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
        bBest = 1;
      }
#endif
      if( bBest ){
        fMinOverlap = overlap;
        fMinGrowth = growth;
        fMinArea = area;
        iBest = cell.iRowid;
      }
    }

    nodeGetCell(pRtree, pNode, i, &aCell[i]);
  }
  nodeZero(pRtree, pNode);
  memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
  nCell++;

  if( pNode->iNode==1 ){
    pRight = nodeNew(pRtree, pNode);
    pLeft = nodeNew(pRtree, pNode);
    pRtree->iDepth++;
    pNode->isDirty = 1;
    writeInt16(pNode->zData, pRtree->iDepth);
  }else{
    pLeft = pNode;
    pRight = nodeNew(pRtree, pLeft->pParent);
    nodeReference(pLeft);
  }

  if( !pLeft || !pRight ){
    rc = SQLITE_NOMEM;
    goto splitnode_out;
  }

){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;

  rtreeReference(pRtree);

  assert(nData>=1);
#if 0
  assert(hashIsEmpty(pRtree));
#endif

  /* If azData[0] is not an SQL NULL value, it is the rowid of a
  ** record to delete from the r-tree table. The following block does
  ** just that.
  */
  if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
    i64 iDelete;                /* The rowid to delete */

  return
}

set ::NROW   1000
set ::NDEL     10
set ::NSELECT 100

if {[info exists G(isquick)] && $G(isquick)} {
  set ::NROW 100
  set ::NSELECT 10
}

foreach module {rtree_i32 rtree} {
  for {set nDim 1} {$nDim <= 5} {incr nDim} {
  

# out-of-memory conditions.
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source $testdir/tester.tcl
source $testdir/malloc_common.tcl

ifcapable !rtree {
  finish_test
  return
}

# Only run these tests if memory debugging is turned on.
#
source $testdir/malloc_common.tcl
if {!$MEMDEBUG} {
   puts "Skipping malloc tests: not compiled with -DSQLITE_MEMDEBUG..."
   finish_test
   return
}

if 1 {

do_faultsim_test rtree3-1 -faults oom* -prep {
  faultsim_delete_and_reopen
} -body {
  execsql {
    BEGIN TRANSACTION;
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
    INSERT INTO rt VALUES(NULL, 13, 15, 17, 19);
    DELETE FROM rt WHERE ii = 1;
    SELECT * FROM rt;
    SELECT ii FROM rt WHERE ii = 2;
    COMMIT;
  }
}

do_test rtree3-2.prep {
  faultsim_delete_and_reopen
  execsql {
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
  }
  faultsim_save_and_close
} {}
do_faultsim_test rtree3-2 -faults oom* -prep {
  faultsim_restore_and_reopen
} -body {
  execsql { DROP TABLE rt } 
}


do_malloc_test rtree3-3.prep {
  faultsim_delete_and_reopen
  execsql {
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
  }
  faultsim_save_and_close
} {}

do_faultsim_test rtree3-3a -faults oom* -prep {
  faultsim_restore_and_reopen
} -body {
  db eval BEGIN
  for {set ii 0} {$ii < 100} {incr ii} {
    set f [expr rand()]
    db eval {INSERT INTO rt VALUES(NULL, $f*10.0, $f*10.0, $f*15.0, $f*15.0)}
  }
  db eval COMMIT
}
faultsim_save_and_close

do_faultsim_test rtree3-3b -faults oom* -prep {
  faultsim_restore_and_reopen
} -body {
  db eval BEGIN
  for {set ii 0} {$ii < 100} {incr ii} {
    set f [expr rand()]
    db eval { DELETE FROM rt WHERE x1<($f*10.0) AND x1>($f*10.5) }
  }
  db eval COMMIT
} 

}

do_test rtree3-4.prep {
  faultsim_delete_and_reopen
  execsql {
    BEGIN;
    PRAGMA page_size = 512;
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
  }
  for {set i 0} {$i < 1500} {incr i} {
    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
  }
  execsql { COMMIT }
  faultsim_save_and_close
} {}

do_faultsim_test rtree3-4 -faults oom-transient -prep {
  faultsim_restore_and_reopen
} -body {
  db eval { SELECT count(*) FROM rt }
} -test {
  faultsim_test_result {0 1500}
}

finish_test

ifcapable !rtree {
  finish_test
  return
}

set ::NROW 2500
if {[info exists G(isquick)] && $G(isquick)} {
  set ::NROW 250
}

# Return a floating point number between -X and X.
# 
proc rand {X} {
  return [expr {int((rand()-0.5)*1024.0*$X)/512.0}]

# 2010 February 16
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# 
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

#-------------------------------------------------------------------------
# The following block of tests - rtree8-1.* - feature reading and writing
# an r-tree table while there exist open cursors on it.
#
proc populate_t1 {n} {
  execsql { DELETE FROM t1 }
  for {set i 1} {$i <= $n} {incr i} {
    execsql { INSERT INTO t1 VALUES($i, $i, $i+2) }
  }
}

# A DELETE while a cursor is reading the table.
#
do_test rtree8-1.1.1 {
  execsql { PRAGMA page_size = 512 }
  execsql { CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2) }
  populate_t1 5
} {}
do_test rtree8-1.1.2 {
  set res [list]
  db eval { SELECT * FROM t1 } { 
    lappend res $x1 $x2
    if {$id==3} { db eval { DELETE FROM t1 WHERE id>3 } }
  }
  set res
} {1 3 2 4 3 5}
do_test rtree8-1.1.3 {
  execsql { SELECT * FROM t1 }
} {1 1 3 2 2 4 3 3 5}

# Many SELECTs on the same small table.
#
proc nested_select {n} {
  set ::max $n
  db eval { SELECT * FROM t1 } {
    if {$id == $n} { nested_select [expr $n+1] }
  }
  return $::max
}
do_test rtree8-1.2.1 { populate_t1 50  } {}
do_test rtree8-1.2.2 { nested_select 1 } {51}

# This test runs many SELECT queries simultaneously against a large 
# table, causing a collision in the hash-table used to store r-tree 
# nodes internally.
#
populate_t1 1500
do_execsql_test rtree8-1.3.1 { SELECT max(nodeno) FROM t1_node } {164}
do_test rtree8-1.3.2 {
  set rowids [execsql {SELECT min(rowid) FROM t1_rowid GROUP BY nodeno}]
  set stmt_list [list]
  foreach row $rowids {
    set stmt [sqlite3_prepare db "SELECT * FROM t1 WHERE id = $row" -1 tail]
    sqlite3_step $stmt
    lappend res_list [sqlite3_column_int $stmt 0]
    lappend stmt_list $stmt 
  }
} {}
do_test rtree8-1.3.3 { set res_list } $rowids
do_execsql_test rtree8-1.3.4 { SELECT count(*) FROM t1 } {1500}
do_test rtree8-1.3.5 { 
  foreach stmt $stmt_list { sqlite3_finalize $stmt }
} {}


#-------------------------------------------------------------------------
# The following block of tests - rtree8-2.* - test a couple of database
# corruption cases. In this case things are not corrupted at the b-tree
# level, but the contents of the various tables used internally by an
# r-tree table are inconsistent.
#
populate_t1 50
do_execsql_test rtree8-2.1.1 { SELECT max(nodeno) FROM t1_node } {5}
do_execsql_test rtree8-2.1.2 { DELETE FROM t1_node } {}
for {set i 1} {$i <= 50} {incr i} {
  do_catchsql_test rtree8-2.1.3.$i { 
    SELECT * FROM t1 WHERE id = $i 
  } {1 {database disk image is malformed}}
}
do_catchsql_test rtree8-2.1.4 { 
  SELECT * FROM t1
} {1 {database disk image is malformed}}
do_catchsql_test rtree8-2.1.5 { 
  DELETE FROM t1
} {1 {database disk image is malformed}}

do_execsql_test rtree8-2.1.6 { 
  DELETE FROM t1_node;
  DELETE FROM t1_parent;
  DELETE FROM t1_rowid;
  DROP TABLE t1;
  CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2);
} {}

#-------------------------------------------------------------------------
# Test that trying to use the MATCH operator with the r-tree module does
# not confuse it.
#
breakpoint
populate_t1 10
do_catchsql_test rtree8-3.1 { 
  SELECT * FROM t1 WHERE x1 MATCH '1234'
} {1 {}}


finish_test