SQLite

splitnode_out:
  nodeRelease(pRtree, pRight);
  nodeRelease(pRtree, pLeft);
  sqlite3_free(aCell);
  return rc;
}

/*
** If node pLeaf is not the root of the r-tree and its pParent
** pointer is still NULL, locate the parent node of pLeaf and populate 
** pLeaf->pParent.
*/
static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
  int rc = SQLITE_OK;
  if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
    int rc2;                      /* sqlite3_reset() return code */
    sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
    rc = sqlite3_step(pRtree->pReadParent);
    if( rc==SQLITE_ROW ){

    ** it, schedule the contents of the child for reinsertion and 
    ** reduce the tree height by one.
    **
    ** This is equivalent to copying the contents of the child into
    ** the root node (the operation that Gutman's paper says to perform 
    ** in this scenario).
    */
    if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){

      RtreeNode *pChild;
      i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
      rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
      if( rc==SQLITE_OK ){
        rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
      }
      if( rc==SQLITE_OK ){
        pRtree->iDepth--;
        writeInt16(pRoot->zData, pRtree->iDepth);
        pRoot->isDirty = 1;

      }
    }

    /* Re-insert the contents of any underfull nodes removed from the tree. */
    for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
      if( rc==SQLITE_OK ){
        rc = reinsertNodeContent(pRtree, pLeaf);

#
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);

  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-4a -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  db eval { SELECT count(*) FROM rt }
} -test {
  faultsim_test_result {0 1500}
}

do_faultsim_test rtree3-4b -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  db eval { DELETE FROM rt WHERE ii BETWEEN 1 AND 100 }
} -test {
  faultsim_test_result {0 {}}
}

do_test rtree3-5.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 < 100} {incr i} {
    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
  }
  execsql { COMMIT }
  faultsim_save_and_close
} {}
do_faultsim_test rtree3-5 -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  for {set i 100} {$i < 110} {incr i} {
    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
  }
} -test {
  faultsim_test_result {0 {}}
}

do_test rtree3-6.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 < 50} {incr i} {
    execsql { INSERT INTO rt VALUES($i, $i, $i+1, $i, $i+1) }
  }
  execsql { COMMIT }
  faultsim_save_and_close
} {}
do_faultsim_test rtree3-6 -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  execsql BEGIN
  for {set i 0} {$i < 50} {incr i} {
    execsql { DELETE FROM rt WHERE ii=$i }
  }
  execsql COMMIT
} -test {
  faultsim_test_result {0 {}}
}

do_test rtree3-7.prep {
  faultsim_delete_and_reopen
  execsql { CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2) }
  faultsim_save_and_close
} {}
do_faultsim_test rtree3-7 -faults oom-* -prep {
  faultsim_restore_and_reopen
} -body {
  execsql { ALTER TABLE rt RENAME TO rt2 }
} -test {
  faultsim_test_result {0 {}}
}

do_faultsim_test rtree3-8 -faults oom-* -prep {
  catch { db close }
} -body {
  sqlite3 db test.db
} 

finish_test

} {}


#-------------------------------------------------------------------------
# Test that trying to use the MATCH operator with the r-tree module does
# not confuse it.
#

populate_t1 10
do_catchsql_test rtree8-3.1 { 
  SELECT * FROM t1 WHERE x1 MATCH '1234'
} {1 {unable to use function MATCH in the requested context}}

#-------------------------------------------------------------------------
# Test a couple of invalid arguments to rtreedepth().
#
do_catchsql_test rtree8-4.1 {
  SELECT rtreedepth('hello world')
} {1 {Invalid argument to rtreedepth()}}
do_catchsql_test rtree8-4.2 {
  SELECT rtreedepth(X'00')
} {1 {Invalid argument to rtreedepth()}}


#-------------------------------------------------------------------------
# Delete half of a lopsided tree.
#
do_execsql_test rtree8-5.1 { 
  CREATE VIRTUAL TABLE t2 USING rtree_i32(id, x1, x2) 
} {}
do_test rtree8-5.2 {
  execsql BEGIN
  for {set i 0} {$i < 100} {incr i} {
    execsql { INSERT INTO t2 VALUES($i, 100, 101) }
  }
  for {set i 100} {$i < 200} {incr i} {
    execsql { INSERT INTO t2 VALUES($i, 1000, 1001) }
  }
  execsql COMMIT
} {}
do_test rtree8-5.3 {
  execsql BEGIN
  for {set i 0} {$i < 200} {incr i} {
    execsql { DELETE FROM t2 WHERE id = $i }
  }
  execsql COMMIT
} {}


finish_test

rename finish_test rtree_finish_test
proc finish_test {} {}

set RTREE_EXCLUDE { }
if {[info exists G(isquick)] && $G(isquick)} { 
  set RTREE_EXCLUDE rtree3.test
}
set G(isquick) 1

set rtreedir [file join $testdir .. ext rtree]

foreach testfile [lsort -dictionary [glob -nocomplain $rtreedir/*.test]] {
  set tail [file tail $testfile]
  if {[lsearch -exact $RTREE_EXCLUDE $tail]>=0} continue
  source $testfile