/ Changes On Branch branch-3.6.23
Login

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

Changes In Branch branch-3.6.23 Excluding Merge-Ins

This is equivalent to a diff from 4ae453ea7b to 265b0b29b8

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: 265b0b29b8 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: 854b23c117 user: drh tags: branch-3.6.23
2010-03-26
17:37
After any rollback that modifies the database file, sync the database before deleting the rollback journal. This is a cherry-pick merge of check-ins [b21b911f23] and [f2326dad4e] check-in: ca0bc2a22e user: drh tags: branch-3.6.23
2010-03-10
14:06
Fix typo in a comment in the sqliteInt.h. No changes to code. check-in: 1716821ddb user: drh tags: trunk
2010-03-09
19:31
Version 3.6.23 check-in: 4ae453ea7b user: drh tags: trunk, release
15:10
Fix a test script issue affecting the TCL backup tests under Windows. check-in: 20c400e73a user: shaneh tags: trunk

Changes to VERSION.

1
3.6.23
|
1
3.6.23.3

Changes to configure.

1
2
3
4
5
6
7
8
9
10
...
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
....
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
....
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
....
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
.....
13968
13969
13970
13971
13972
13973
13974
13975
13976
13977
13978
13979
13980
13981
13982
.....
14021
14022
14023
14024
14025
14026
14027
14028
14029
14030
14031
14032
14033
14034
14035
#! /bin/sh
# Guess values for system-dependent variables and create Makefiles.
# Generated by GNU Autoconf 2.62 for sqlite 3.6.23.
#
# Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001,
# 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
# This configure script is free software; the Free Software Foundation
# gives unlimited permission to copy, distribute and modify it.
## --------------------- ##
## M4sh Initialization.  ##
................................................................................
MFLAGS=
MAKEFLAGS=
SHELL=${CONFIG_SHELL-/bin/sh}

# Identity of this package.
PACKAGE_NAME='sqlite'
PACKAGE_TARNAME='sqlite'
PACKAGE_VERSION='3.6.23'
PACKAGE_STRING='sqlite 3.6.23'
PACKAGE_BUGREPORT=''

# Factoring default headers for most tests.
ac_includes_default="\
#include <stdio.h>
#ifdef HAVE_SYS_TYPES_H
# include <sys/types.h>
................................................................................
#
# Report the --help message.
#
if test "$ac_init_help" = "long"; then
  # Omit some internal or obsolete options to make the list less imposing.
  # This message is too long to be a string in the A/UX 3.1 sh.
  cat <<_ACEOF
\`configure' configures sqlite 3.6.23 to adapt to many kinds of systems.

Usage: $0 [OPTION]... [VAR=VALUE]...

To assign environment variables (e.g., CC, CFLAGS...), specify them as
VAR=VALUE.  See below for descriptions of some of the useful variables.

Defaults for the options are specified in brackets.
................................................................................
  --build=BUILD     configure for building on BUILD [guessed]
  --host=HOST       cross-compile to build programs to run on HOST [BUILD]
_ACEOF
fi

if test -n "$ac_init_help"; then
  case $ac_init_help in
     short | recursive ) echo "Configuration of sqlite 3.6.23:";;
   esac
  cat <<\_ACEOF

Optional Features:
  --disable-option-checking  ignore unrecognized --enable/--with options
  --disable-FEATURE       do not include FEATURE (same as --enable-FEATURE=no)
  --enable-FEATURE[=ARG]  include FEATURE [ARG=yes]
................................................................................
    cd "$ac_pwd" || { ac_status=$?; break; }
  done
fi

test -n "$ac_init_help" && exit $ac_status
if $ac_init_version; then
  cat <<\_ACEOF
sqlite configure 3.6.23
generated by GNU Autoconf 2.62

Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001,
2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
This configure script is free software; the Free Software Foundation
gives unlimited permission to copy, distribute and modify it.
_ACEOF
  exit
fi
cat >config.log <<_ACEOF
This file contains any messages produced by compilers while
running configure, to aid debugging if configure makes a mistake.

It was created by sqlite $as_me 3.6.23, which was
generated by GNU Autoconf 2.62.  Invocation command line was

  $ $0 $@

_ACEOF
exec 5>>config.log
{
................................................................................

exec 6>&1

# Save the log message, to keep $[0] and so on meaningful, and to
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
This file was extended by sqlite $as_me 3.6.23, which was
generated by GNU Autoconf 2.62.  Invocation command line was

  CONFIG_FILES    = $CONFIG_FILES
  CONFIG_HEADERS  = $CONFIG_HEADERS
  CONFIG_LINKS    = $CONFIG_LINKS
  CONFIG_COMMANDS = $CONFIG_COMMANDS
  $ $0 $@
................................................................................
$config_commands

Report bugs to <bug-autoconf@gnu.org>."

_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
sqlite config.status 3.6.23
configured by $0, generated by GNU Autoconf 2.62,
  with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"

Copyright (C) 2008 Free Software Foundation, Inc.
This config.status script is free software; the Free Software Foundation
gives unlimited permission to copy, distribute and modify it."



|







 







|
|







 







|







 







|







 







|













|







 







|







 







|







1
2
3
4
5
6
7
8
9
10
...
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
....
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
....
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
....
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
.....
13968
13969
13970
13971
13972
13973
13974
13975
13976
13977
13978
13979
13980
13981
13982
.....
14021
14022
14023
14024
14025
14026
14027
14028
14029
14030
14031
14032
14033
14034
14035
#! /bin/sh
# Guess values for system-dependent variables and create Makefiles.
# Generated by GNU Autoconf 2.62 for sqlite 3.6.23.1.
#
# Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001,
# 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
# This configure script is free software; the Free Software Foundation
# gives unlimited permission to copy, distribute and modify it.
## --------------------- ##
## M4sh Initialization.  ##
................................................................................
MFLAGS=
MAKEFLAGS=
SHELL=${CONFIG_SHELL-/bin/sh}

# Identity of this package.
PACKAGE_NAME='sqlite'
PACKAGE_TARNAME='sqlite'
PACKAGE_VERSION='3.6.23.1'
PACKAGE_STRING='sqlite 3.6.23.1'
PACKAGE_BUGREPORT=''

# Factoring default headers for most tests.
ac_includes_default="\
#include <stdio.h>
#ifdef HAVE_SYS_TYPES_H
# include <sys/types.h>
................................................................................
#
# Report the --help message.
#
if test "$ac_init_help" = "long"; then
  # Omit some internal or obsolete options to make the list less imposing.
  # This message is too long to be a string in the A/UX 3.1 sh.
  cat <<_ACEOF
\`configure' configures sqlite 3.6.23.1 to adapt to many kinds of systems.

Usage: $0 [OPTION]... [VAR=VALUE]...

To assign environment variables (e.g., CC, CFLAGS...), specify them as
VAR=VALUE.  See below for descriptions of some of the useful variables.

Defaults for the options are specified in brackets.
................................................................................
  --build=BUILD     configure for building on BUILD [guessed]
  --host=HOST       cross-compile to build programs to run on HOST [BUILD]
_ACEOF
fi

if test -n "$ac_init_help"; then
  case $ac_init_help in
     short | recursive ) echo "Configuration of sqlite 3.6.23.1:";;
   esac
  cat <<\_ACEOF

Optional Features:
  --disable-option-checking  ignore unrecognized --enable/--with options
  --disable-FEATURE       do not include FEATURE (same as --enable-FEATURE=no)
  --enable-FEATURE[=ARG]  include FEATURE [ARG=yes]
................................................................................
    cd "$ac_pwd" || { ac_status=$?; break; }
  done
fi

test -n "$ac_init_help" && exit $ac_status
if $ac_init_version; then
  cat <<\_ACEOF
sqlite configure 3.6.23.1
generated by GNU Autoconf 2.62

Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001,
2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
This configure script is free software; the Free Software Foundation
gives unlimited permission to copy, distribute and modify it.
_ACEOF
  exit
fi
cat >config.log <<_ACEOF
This file contains any messages produced by compilers while
running configure, to aid debugging if configure makes a mistake.

It was created by sqlite $as_me 3.6.23.1, which was
generated by GNU Autoconf 2.62.  Invocation command line was

  $ $0 $@

_ACEOF
exec 5>>config.log
{
................................................................................

exec 6>&1

# Save the log message, to keep $[0] and so on meaningful, and to
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
This file was extended by sqlite $as_me 3.6.23.1, which was
generated by GNU Autoconf 2.62.  Invocation command line was

  CONFIG_FILES    = $CONFIG_FILES
  CONFIG_HEADERS  = $CONFIG_HEADERS
  CONFIG_LINKS    = $CONFIG_LINKS
  CONFIG_COMMANDS = $CONFIG_COMMANDS
  $ $0 $@
................................................................................
$config_commands

Report bugs to <bug-autoconf@gnu.org>."

_ACEOF
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_version="\\
sqlite config.status 3.6.23.1
configured by $0, generated by GNU Autoconf 2.62,
  with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\"

Copyright (C) 2008 Free Software Foundation, Inc.
This config.status script is free software; the Free Software Foundation
gives unlimited permission to copy, distribute and modify it."

Changes to ext/fts3/fts3.c.

595
596
597
598
599
600
601








602
603
604
605
606
607
608
609
610
611
612
613
614


615


616



617
618
619
620
621
622
623
624
625
....
2029
2030
2031
2032
2033
2034
2035
2036






2037
2038
2039
2040
2041
2042
2043
....
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
    fts3DbExec(&rc, db, 
        "CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
        p->zDb, p->zName
    );
  }
  return rc;
}









/*
** Determine if a table currently exists in the database.
*/
static void fts3TableExists(
  int *pRc,             /* Success code */
  sqlite3 *db,          /* The database connection to test */
  const char *zDb,      /* ATTACHed database within the connection */
  const char *zName,    /* Name of the FTS3 table */
  const char *zSuffix,  /* Shadow table extension */
  u8 *pResult           /* Write results here */
){
  int rc = SQLITE_OK;


  if( *pRc ) return;


  fts3DbExec(&rc, db, "SELECT 1 FROM %Q.'%q%s'", zDb, zName, zSuffix);



  *pResult = (rc==SQLITE_OK) ? 1 : 0;
  if( rc!=SQLITE_ERROR ) *pRc = rc;
}

/*
** This function is the implementation of both the xConnect and xCreate
** methods of the FTS3 virtual table.
**
** The argv[] array contains the following:
................................................................................
    if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
      return SQLITE_NOMEM;
    }

    rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn, 
        iCol, zQuery, -1, &pCsr->pExpr
    );
    if( rc!=SQLITE_OK ) return rc;







    rc = evalFts3Expr(p, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
    pCsr->pNextId = pCsr->aDoclist;
    pCsr->iPrevId = 0;
  }

  if( rc!=SQLITE_OK ) return rc;
................................................................................
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", -1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
  ){
    rc = sqlite3_create_module_v2(
        db, "fts3", &fts3Module, (void *)pHash, hashDestroy
    );
#if 0 /* FTS4 is disabled in 3.6.23 since it is not yet ready for publication */
    if( rc==SQLITE_OK ){
      rc = sqlite3_create_module_v2(
          db, "fts4", &fts3Module, (void *)pHash, 0
      );
    }
#endif /* disable FTS4 */
    return rc;
  }

  /* An error has occurred. Delete the hash table and return the error code. */
  assert( rc!=SQLITE_OK );
  if( pHash ){
    sqlite3Fts3HashClear(pHash);







>
>
>
>
>
>
>
>













>
>

>
>
|
>
>
>
|
|







 







|
>
>
>
>
>
>







 







<





<







595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
....
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
....
2570
2571
2572
2573
2574
2575
2576

2577
2578
2579
2580
2581

2582
2583
2584
2585
2586
2587
2588
    fts3DbExec(&rc, db, 
        "CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
        p->zDb, p->zName
    );
  }
  return rc;
}

/*
** An sqlite3_exec() callback for fts3TableExists.
*/
static int fts3TableExistsCallback(void *pArg, int n, char **pp1, char **pp2){
  *(int*)pArg = 1;
  return 1;
}

/*
** Determine if a table currently exists in the database.
*/
static void fts3TableExists(
  int *pRc,             /* Success code */
  sqlite3 *db,          /* The database connection to test */
  const char *zDb,      /* ATTACHed database within the connection */
  const char *zName,    /* Name of the FTS3 table */
  const char *zSuffix,  /* Shadow table extension */
  u8 *pResult           /* Write results here */
){
  int rc = SQLITE_OK;
  int res = 0;
  char *zSql;
  if( *pRc ) return;
  zSql = sqlite3_mprintf(
    "SELECT 1 FROM %Q.sqlite_master WHERE name='%q%s'",
    zDb, zName, zSuffix
  );    
  rc = sqlite3_exec(db, zSql, fts3TableExistsCallback, &res, 0);
  sqlite3_free(zSql);
  *pResult = res & 0xff;
  if( rc!=SQLITE_ABORT ) *pRc = rc;
}

/*
** This function is the implementation of both the xConnect and xCreate
** methods of the FTS3 virtual table.
**
** The argv[] array contains the following:
................................................................................
    if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
      return SQLITE_NOMEM;
    }

    rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn, 
        iCol, zQuery, -1, &pCsr->pExpr
    );
    if( rc!=SQLITE_OK ){
      if( rc==SQLITE_ERROR ){
        p->base.zErrMsg = sqlite3_mprintf("malformed MATCH expression: [%s]",
                                          zQuery);
      }
      return rc;
    }

    rc = evalFts3Expr(p, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
    pCsr->pNextId = pCsr->aDoclist;
    pCsr->iPrevId = 0;
  }

  if( rc!=SQLITE_OK ) return rc;
................................................................................
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "offsets", 1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "matchinfo", -1))
   && SQLITE_OK==(rc = sqlite3_overload_function(db, "optimize", 1))
  ){
    rc = sqlite3_create_module_v2(
        db, "fts3", &fts3Module, (void *)pHash, hashDestroy
    );

    if( rc==SQLITE_OK ){
      rc = sqlite3_create_module_v2(
          db, "fts4", &fts3Module, (void *)pHash, 0
      );
    }

    return rc;
  }

  /* An error has occurred. Delete the hash table and return the error code. */
  assert( rc!=SQLITE_OK );
  if( pHash ){
    sqlite3Fts3HashClear(pHash);

Changes to ext/fts3/fts3_snippet.c.

1152
1153
1154
1155
1156
1157
1158


1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
        }
        if( rc==SQLITE_OK ){
          char aBuffer[64];
          sqlite3_snprintf(sizeof(aBuffer), aBuffer, 
              "%d %d %d %d ", iCol, pTerm-sCtx.aTerm, iStart, iEnd-iStart
          );
          rc = fts3StringAppend(&res, aBuffer, -1);


        }
      }
    }
    if( rc==SQLITE_DONE ){
      rc = SQLITE_CORRUPT;
    }

    pMod->xClose(pC);
    if( rc!=SQLITE_OK ) goto offsets_out;
  }

 offsets_out:







>
>




|







1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
        }
        if( rc==SQLITE_OK ){
          char aBuffer[64];
          sqlite3_snprintf(sizeof(aBuffer), aBuffer, 
              "%d %d %d %d ", iCol, pTerm-sCtx.aTerm, iStart, iEnd-iStart
          );
          rc = fts3StringAppend(&res, aBuffer, -1);
        }else if( rc==SQLITE_DONE ){
          rc = SQLITE_CORRUPT;
        }
      }
    }
    if( rc==SQLITE_DONE ){
      rc = SQLITE_OK;
    }

    pMod->xClose(pC);
    if( rc!=SQLITE_OK ) goto offsets_out;
  }

 offsets_out:

Changes to ext/fts3/fts3_write.c.

182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/* 1  */  "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",
/* 2  */  "DELETE FROM %Q.'%q_content'",
/* 3  */  "DELETE FROM %Q.'%q_segments'",
/* 4  */  "DELETE FROM %Q.'%q_segdir'",
/* 5  */  "DELETE FROM %Q.'%q_docsize'",
/* 6  */  "DELETE FROM %Q.'%q_stat'",
/* 7  */  "SELECT * FROM %Q.'%q_content' WHERE rowid=?",
/* 8  */  "SELECT coalesce(max(idx)+1, 0) FROM %Q.'%q_segdir' WHERE level=?",
/* 9  */  "INSERT INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
/* 10 */  "SELECT coalesce(max(blockid)+1, 1) FROM %Q.'%q_segments'",
/* 11 */  "INSERT INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",

          /* Return segments in order from oldest to newest.*/ 
/* 12 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
            "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
/* 13 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
            "FROM %Q.'%q_segdir' ORDER BY level DESC, idx ASC",







|

|







182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/* 1  */  "SELECT NOT EXISTS(SELECT docid FROM %Q.'%q_content' WHERE rowid!=?)",
/* 2  */  "DELETE FROM %Q.'%q_content'",
/* 3  */  "DELETE FROM %Q.'%q_segments'",
/* 4  */  "DELETE FROM %Q.'%q_segdir'",
/* 5  */  "DELETE FROM %Q.'%q_docsize'",
/* 6  */  "DELETE FROM %Q.'%q_stat'",
/* 7  */  "SELECT * FROM %Q.'%q_content' WHERE rowid=?",
/* 8  */  "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",
/* 9  */  "INSERT INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
/* 10 */  "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",
/* 11 */  "INSERT INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",

          /* Return segments in order from oldest to newest.*/ 
/* 12 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
            "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
/* 13 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
            "FROM %Q.'%q_segdir' ORDER BY level DESC, idx ASC",

Changes to ext/rtree/rtree.c.

8
9
10
11
12
13
14







































15
16
17
18
19
20
21
..
49
50
51
52
53
54
55



56
57
58
59
60
61
62
63
64
65
66
67

68
69
70
71
72
73
74
75
76
77


78
79
80
81
82
83
84
...
140
141
142
143
144
145
146









147
148
149
150
151
152
153
...
172
173
174
175
176
177
178
179
180
181


182
183
184
185
186
187
188
189

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
...
220
221
222
223
224
225
226


































227
228
229
230
231
232
233
...
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
...
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
...
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
...
387
388
389
390
391
392
393

394
395
396
397
398
399
400
...
403
404
405
406
407
408
409





410
411
412
413
414

415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434

435

436






437
438


439
440
441













442


443






444
445
446
447
448
449
450
...
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
...
709
710
711
712
713
714
715



















716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
...
732
733
734
735
736
737
738
739
740























741
742
743
744



745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762



763



764
765
766











767
768
769

770
771
772
773
774
775
776





777
778
779
780
781
782

783
784
785
786
787
788
789
790
791
792
793
794
795
796
797






798

799


800


801
802

803
804
805
806
807
808
809
810
...
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
...
865
866
867
868
869
870
871
872





873


874
875


876

877
878
879
880
881
882
883
884
885
886
887
888

889
890
891
892
893
894
895
896
897
898






899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920



921
922
923
924
925
926
927
...
981
982
983
984
985
986
987













































988
989
990
991
992
993
994
...
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015

1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028

1029
1030
1031
1032
1033










1034

1035
1036
1037
1038
1039
1040
1041
....
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
....
1088
1089
1090
1091
1092
1093
1094

1095
1096
1097
1098
1099
1100
1101
....
1126
1127
1128
1129
1130
1131
1132
1133


1134
1135
1136
1137
1138
1139
1140




1141
1142


1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
....
1266
1267
1268
1269
1270
1271
1272

1273




1274
1275
1276
1277
1278
1279
1280
....
1359
1360
1361
1362
1363
1364
1365

1366
1367
1368
1369
1370
1371

1372
1373
1374
1375
1376
1377
1378
1379
1380
1381








1382
1383
1384
1385
1386
1387
1388
....
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412



1413


1414
1415
1416
1417
1418
1419
1420
1421
1422

1423
1424
1425
1426
1427
1428
1429
....
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
....
1968
1969
1970
1971
1972
1973
1974
1975




1976
1977
1978
1979
1980
1981
1982
1983
....
1985
1986
1987
1988
1989
1990
1991

1992

1993
1994




1995
1996
1997
1998
1999
2000
2001
....
2031
2032
2033
2034
2035
2036
2037











2038
2039
2040



2041
2042









2043


2044
2045
2046
2047

2048
2049
2050
2051


2052
2053
2054
2055
2056
2057
2058
2059

2060
2061
2062
2063
2064
2065
2066

2067
2068
2069

2070
2071




2072
2073
2074
2075
2076
2077
2078
....
2094
2095
2096
2097
2098
2099
2100
2101
2102

2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114

2115
2116
2117


2118
2119
2120
2121
2122
2123
2124

2125
2126
2127
2128
2129
2130
2131
....
2134
2135
2136
2137
2138
2139
2140
2141
2142

2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
....
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
....
2278
2279
2280
2281
2282
2283
2284
2285

2286
2287
2288
2289

2290
2291
2292
2293
2294
2295
2296
....
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
....
2378
2379
2380
2381
2382
2383
2384
2385

2386

2387
2388
2389
2390
2391
2392
2393
....
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415


2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
....
2479
2480
2481
2482
2483
2484
2485

2486
2487
2488
2489
2490
2491
2492
....
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
....
2848
2849
2850
2851
2852
2853
2854

2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
....
2869
2870
2871
2872
2873
2874
2875



































































2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
*/








































#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
** same data-structure is used for all, but the algorithms for insert and
................................................................................
  #define PickSeeds LinearPickSeeds
  #define AssignCells splitNodeGuttman
#endif
#if VARIANT_RSTARTREE_SPLIT
  #define AssignCells splitNodeStartree
#endif





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

#include <string.h>
#include <assert.h>

#ifndef SQLITE_AMALGAMATION

typedef sqlite3_int64 i64;
typedef unsigned char u8;
typedef unsigned int u32;
#endif

typedef struct Rtree Rtree;
typedef struct RtreeCursor RtreeCursor;
typedef struct RtreeNode RtreeNode;
typedef struct RtreeCell RtreeCell;
typedef struct RtreeConstraint RtreeConstraint;


typedef union RtreeCoord RtreeCoord;

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

/* Size of hash table Rtree.aHash. This hash table is not expected to
** ever contain very many entries, so a fixed number of buckets is 
................................................................................
** If an R*-tree "Reinsert" operation is required, the same number of
** cells are removed from the overfull node and reinserted into the tree.
*/
#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
#define RTREE_MAXCELLS 51










/* 
** An rtree cursor object.
*/
struct RtreeCursor {
  sqlite3_vtab_cursor base;
  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
  int iCell;                        /* Index of current cell in pNode */
................................................................................
    ((double)coord.i)                             \
)

/*
** A search constraint.
*/
struct RtreeConstraint {
  int iCoord;                       /* Index of constrained coordinate */
  int op;                           /* Constraining operation */
  double rValue;                    /* Constraint value. */


};

/* Possible values for RtreeConstraint.op */
#define RTREE_EQ 0x41
#define RTREE_LE 0x42
#define RTREE_LT 0x43
#define RTREE_GE 0x44
#define RTREE_GT 0x45


/* 
** An rtree structure node.
**
** Data format (RtreeNode.zData):
**
**   1. If the node is the root node (node 1), then the first 2 bytes
**      of the node contain the tree depth as a big-endian integer.
**      For non-root nodes, the first 2 bytes are left unused.
**
**   2. The next 2 bytes contain the number of entries currently 
**      stored in the node.
**
**   3. The remainder of the node contains the node entries. Each entry
**      consists of a single 8-byte integer followed by an even number
**      of 4-byte coordinates. For leaf nodes the integer is the rowid
**      of a record. For internal nodes it is the node number of a
**      child page.
*/
struct RtreeNode {
  RtreeNode *pParent;               /* Parent node */
  i64 iNode;
  int nRef;
  int isDirty;
  u8 *zData;
................................................................................
** Structure to store a deserialized rtree record.
*/
struct RtreeCell {
  i64 iRowid;
  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
};



































#ifndef MAX
# define MAX(x,y) ((x) < (y) ? (y) : (x))
#endif
#ifndef MIN
# define MIN(x,y) ((x) > (y) ? (y) : (x))
#endif

................................................................................
  }
}

/*
** Clear the content of node p (set all bytes to 0x00).
*/
static void nodeZero(Rtree *pRtree, RtreeNode *p){
  if( 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){
................................................................................

/*
** 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;
  assert( iNode!=0 );
  for(p=pRtree->aHash[nodeHash(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){
  if( 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, int zero){
  RtreeNode *pNode;
  pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
  if( pNode ){
    memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
    pNode->zData = (u8 *)&pNode[1];
    pNode->nRef = 1;
    pNode->pParent = pParent;
    pNode->isDirty = 1;
    nodeReference(pParent);
  }
  return pNode;
................................................................................
nodeAcquire(
  Rtree *pRtree,             /* R-tree structure */
  i64 iNode,                 /* Node number to load */
  RtreeNode *pParent,        /* Either the parent node or NULL */
  RtreeNode **ppNode         /* OUT: Acquired node */
){
  int rc;

  RtreeNode *pNode;

  /* 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)) ){
    assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
................................................................................
      pNode->pParent = pParent;
    }
    pNode->nRef++;
    *ppNode = pNode;
    return SQLITE_OK;
  }






  pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
  if( !pNode ){
    *ppNode = 0;
    return SQLITE_NOMEM;
  }

  pNode->pParent = pParent;
  pNode->zData = (u8 *)&pNode[1];
  pNode->nRef = 1;
  pNode->iNode = iNode;
  pNode->isDirty = 0;
  pNode->pNext = 0;

  sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
  rc = sqlite3_step(pRtree->pReadNode);
  if( rc==SQLITE_ROW ){
    const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
    assert( sqlite3_column_bytes(pRtree->pReadNode, 0)==pRtree->iNodeSize );
    memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
    nodeReference(pParent);
  }else{
    sqlite3_free(pNode);
    pNode = 0;
  }

  *ppNode = pNode;

  rc = sqlite3_reset(pRtree->pReadNode);








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


  }

  assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );













  nodeHashInsert(pRtree, pNode);









  return rc;
}

/*
** Overwrite cell iCell of node pNode with the contents of pCell.
*/
static void nodeOverwriteCell(
................................................................................
){
  int nCell;                    /* Current number of cells in pNode */
  int nMaxCell;                 /* Maximum number of cells for pNode */

  nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
  nCell = NCELL(pNode);

  assert(nCell<=nMaxCell);

  if( nCell<nMaxCell ){
    nodeOverwriteCell(pRtree, pNode, pCell, nCell);
    writeInt16(&pNode->zData[2], nCell+1);
    pNode->isDirty = 1;
  }

  return (nCell==nMaxCell);
................................................................................
    rc = SQLITE_OK;
  }
  *ppCursor = (sqlite3_vtab_cursor *)pCsr;

  return rc;
}




















/* 
** Rtree virtual table module xClose method.
*/
static int rtreeClose(sqlite3_vtab_cursor *cur){
  Rtree *pRtree = (Rtree *)(cur->pVtab);
  int rc;
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  sqlite3_free(pCsr->aConstraint);
  rc = nodeRelease(pRtree, pCsr->pNode);
  sqlite3_free(pCsr);
  return rc;
}

/*
** Rtree virtual table module xEof method.
................................................................................
** Return non-zero if the cursor does not currently point to a valid 
** record (i.e if the scan has finished), or zero otherwise.
*/
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return (pCsr->pNode==0);
}

/* 























** Cursor pCursor currently points to a cell in a non-leaf page.
** Return true if the sub-tree headed by the cell is filtered
** (excluded) by the constraints in the pCursor->aConstraint[] 
** array, or false otherwise.



*/
static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){
  RtreeCell cell;
  int ii;
  int bRes = 0;

  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
    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;



      case RTREE_EQ: 
        bRes = (p->rValue>cell_max || p->rValue<cell_min);
        break;











    }
  }


  return bRes;
}

/* 
** Return true if the cell that cursor pCursor currently points to
** would be filtered (excluded) by the constraints in the 
** pCursor->aConstraint[] array, or false otherwise.





**
** This function assumes that the cell is part of a leaf node.
*/
static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){
  RtreeCell cell;
  int ii;


  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
  for(ii=0; ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    double coord = DCOORD(cell.aCoord[p->iCoord]);
    int res;
    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: 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;
      case RTREE_EQ: res = (coord==p->rValue); break;






    }




    if( !res ) return 1;


  }


  return 0;
}

/*
** Cursor pCursor currently points at a node that heads a sub-tree of
** height iHeight (if iHeight==0, then the node is a leaf). Descend
** to point to the left-most cell of the sub-tree that matches the 
** configured constraints.
................................................................................

  RtreeNode *pSavedNode = pCursor->pNode;
  int iSavedCell = pCursor->iCell;

  assert( iHeight>=0 );

  if( iHeight==0 ){
    isEof = testRtreeEntry(pRtree, pCursor);
  }else{
    isEof = testRtreeCell(pRtree, pCursor);
  }
  if( isEof || iHeight==0 ){
    *pEof = isEof;
    return SQLITE_OK;
  }

  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
  if( rc!=SQLITE_OK ){
    return rc;
  }
................................................................................
  return SQLITE_OK;
}

/*
** One of the cells in node pNode is guaranteed to have a 64-bit 
** integer value equal to iRowid. Return the index of this cell.
*/
static int nodeRowidIndex(Rtree *pRtree, RtreeNode *pNode, i64 iRowid){





  int ii;


  for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
    assert( ii<(NCELL(pNode)-1) );


  }

  return ii;
}

/*
** Return the index of the cell containing a pointer to node pNode
** in its parent. If pNode is the root node, return -1.
*/
static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode){
  RtreeNode *pParent = pNode->pParent;
  if( pParent ){
    return nodeRowidIndex(pRtree, pParent, pNode->iNode);
  }

  return -1;
}

/* 
** 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;







  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 if( pCsr->pNode ){
    /* 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;
        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
        if( rc!=SQLITE_OK || !isEof ){
          return rc;
        }
      }
      pCsr->pNode = pNode->pParent;
      pCsr->iCell = nodeParentIndex(pRtree, pNode);



      nodeReference(pCsr->pNode);
      nodeRelease(pRtree, pNode);
      iHeight++;
    }
  }

  return rc;
................................................................................
    sqlite3_reset(pRtree->pReadRowid);
  }else{
    rc = sqlite3_reset(pRtree->pReadRowid);
  }
  return rc;
}















































/* 
** Rtree virtual table module xFilter method.
*/
static int rtreeFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
................................................................................

  RtreeNode *pRoot = 0;
  int ii;
  int rc = SQLITE_OK;

  rtreeReference(pRtree);

  sqlite3_free(pCsr->aConstraint);
  pCsr->aConstraint = 0;
  pCsr->iStrategy = idxNum;

  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 && 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 ){
      pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
      pCsr->nConstraint = argc;
      if( !pCsr->aConstraint ){
        rc = SQLITE_NOMEM;
      }else{

        assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
        for(ii=0; ii<argc; ii++){
          RtreeConstraint *p = &pCsr->aConstraint[ii];
          p->op = idxStr[ii*2];
          p->iCoord = idxStr[ii*2+1]-'a';










          p->rValue = sqlite3_value_double(argv[ii]);

        }
      }
    }
  
    if( rc==SQLITE_OK ){
      pCsr->pNode = 0;
      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
................................................................................
** Rtree virtual table module xBestIndex method. There are three
** table scan strategies to choose from (in order from most to 
** least desirable):
**
**   idxNum     idxStr        Strategy
**   ------------------------------------------------
**     1        Unused        Direct lookup by rowid.
**     2        See below     R-tree query.
**     3        Unused        Full table scan.
**   ------------------------------------------------
**
** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
** 2 is used, idxStr is formatted to contain 2 bytes for each 
** constraint used. The first two bytes of idxStr correspond to 
** the constraint in sqlite3_index_info.aConstraintUsage[] with
** (argvIndex==1) etc.
**
** The first of each pair of bytes in idxStr identifies the constraint
** operator as follows:
................................................................................
**   Operator    Byte Value
**   ----------------------
**      =        0x41 ('A')
**     <=        0x42 ('B')
**      <        0x43 ('C')
**     >=        0x44 ('D')
**      >        0x45 ('E')

**   ----------------------
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
................................................................................
      ** considered almost as quick as a direct rowid lookup (for which 
      ** sqlite uses an internal cost of 0.0).
      */ 
      pIdxInfo->estimatedCost = 10.0;
      return SQLITE_OK;
    }

    if( p->usable && p->iColumn>0 ){


      u8 op = 0;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;




      }
      if( op ){


        /* Make sure this particular constraint has not been used before.
        ** If it has been used before, ignore it.
        **
        ** A <= or < can be used if there is a prior >= or >.
        ** A >= or > can be used if there is a prior < or <=.
        ** A <= or < is disqualified if there is a prior <=, <, or ==.
        ** A >= or > is disqualified if there is a prior >=, >, or ==.
        ** A == is disqualifed if there is any prior constraint.
        */
        int j, opmsk;
        static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
        assert( compatible[RTREE_EQ & 7]==0 );
        assert( compatible[RTREE_LT & 7]==1 );
        assert( compatible[RTREE_LE & 7]==1 );
        assert( compatible[RTREE_GT & 7]==2 );
        assert( compatible[RTREE_GE & 7]==2 );
        cCol = p->iColumn - 1 + 'a';
        opmsk = compatible[op & 7];
        for(j=0; j<iIdx; j+=2){
          if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
            op = 0;
            break;
          }
        }
      }
      if( op ){
        assert( iIdx<sizeof(zIdxStr)-1 );
        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = cCol;
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
................................................................................
  RtreeCell *aCell, 
  int nCell, 
  int iExclude
){
  int ii;
  float overlap = 0.0;
  for(ii=0; ii<nCell; ii++){

    if( ii!=iExclude ){




      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++){

      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);
      }
#endif
      if( (iCell==0) 
       || (overlap<fMinOverlap) 
       || (overlap==fMinOverlap && growth<fMinGrowth)
       || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
      ){








        fMinOverlap = overlap;
        fMinGrowth = growth;
        fMinArea = area;
        iBest = cell.iRowid;
      }
    }

................................................................................
}

/*
** A cell with the same content as pCell has just been inserted into
** the node pNode. This function updates the bounding box cells in
** all ancestor elements.
*/
static void AdjustTree(
  Rtree *pRtree,                    /* Rtree table */
  RtreeNode *pNode,                 /* Adjust ancestry of this node. */
  RtreeCell *pCell                  /* This cell was just inserted */
){
  RtreeNode *p = pNode;
  while( p->pParent ){
    RtreeCell cell;
    RtreeNode *pParent = p->pParent;



    int iCell = nodeParentIndex(pRtree, p);



    nodeGetCell(pRtree, pParent, iCell, &cell);
    if( !cellContains(pRtree, &cell, pCell) ){
      cellUnion(pRtree, &cell, pCell);
      nodeOverwriteCell(pRtree, pParent, &cell, iCell);
    }
 
    p = pParent;
  }

}

/*
** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
*/
static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
  sqlite3_bind_int64(pRtree->pWriteRowid, 1, 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, 1);
    pLeft = nodeNew(pRtree, pNode, 1);
    pRtree->iDepth++;
    pNode->isDirty = 1;
    writeInt16(pNode->zData, pRtree->iDepth);
  }else{
    pLeft = pNode;
    pRight = nodeNew(pRtree, pLeft->pParent, 1);
    nodeReference(pLeft);
  }

  if( !pLeft || !pRight ){
    rc = SQLITE_NOMEM;
    goto splitnode_out;
  }
................................................................................
  memset(pRight->zData, 0, pRtree->iNodeSize);

  rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
  if( rc!=SQLITE_OK ){
    goto splitnode_out;
  }

  /* Ensure both child nodes have node numbers assigned to them. */




  if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
   || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
  ){
    goto splitnode_out;
  }

  rightbbox.iRowid = pRight->iNode;
  leftbbox.iRowid = pLeft->iNode;
................................................................................
  if( pNode->iNode==1 ){
    rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
    if( rc!=SQLITE_OK ){
      goto splitnode_out;
    }
  }else{
    RtreeNode *pParent = pLeft->pParent;

    int iCell = nodeParentIndex(pRtree, pLeft);

    nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
    AdjustTree(pRtree, pParent, &leftbbox);




  }
  if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
    goto splitnode_out;
  }

  for(i=0; i<NCELL(pRight); i++){
    i64 iRowid = nodeGetRowid(pRtree, pRight, i);
................................................................................
splitnode_out:
  nodeRelease(pRtree, pRight);
  nodeRelease(pRtree, pLeft);
  sqlite3_free(aCell);
  return rc;
}












static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
  int rc = SQLITE_OK;
  if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){



    sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
    if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){









      i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);


      rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
    }else{
      rc = SQLITE_ERROR;
    }

    sqlite3_reset(pRtree->pReadParent);
    if( rc==SQLITE_OK ){
      rc = fixLeafParent(pRtree, pLeaf->pParent);
    }


  }
  return rc;
}

static int deleteCell(Rtree *, RtreeNode *, int, int);

static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
  int rc;

  RtreeNode *pParent;
  int iCell;

  assert( pNode->nRef==1 );

  /* Remove the entry in the parent cell. */
  iCell = nodeParentIndex(pRtree, pNode);

  pParent = pNode->pParent;
  pNode->pParent = 0;
  if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1)) 

   || SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
  ){




    return rc;
  }

  /* Remove the xxx_node entry. */
  sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
  sqlite3_step(pRtree->pDeleteNode);
  if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
................................................................................
  pNode->pNext = pRtree->pDeleted;
  pNode->nRef++;
  pRtree->pDeleted = pNode;

  return SQLITE_OK;
}

static void fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
  RtreeNode *pParent = pNode->pParent;

  if( pParent ){
    int ii; 
    int nCell = NCELL(pNode);
    RtreeCell box;                            /* Bounding box for pNode */
    nodeGetCell(pRtree, pNode, 0, &box);
    for(ii=1; ii<nCell; ii++){
      RtreeCell cell;
      nodeGetCell(pRtree, pNode, ii, &cell);
      cellUnion(pRtree, &box, &cell);
    }
    box.iRowid = pNode->iNode;
    ii = nodeParentIndex(pRtree, pNode);

    nodeOverwriteCell(pRtree, pParent, &box, ii);
    fixBoundingBox(pRtree, pParent);
  }


}

/*
** Delete the cell at index iCell of node pNode. After removing the
** cell, adjust the r-tree data structure if required.
*/
static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){

  int rc;

  if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
    return rc;
  }

  /* Remove the cell from the node. This call just moves bytes around
................................................................................
  nodeDeleteCell(pRtree, pNode, iCell);

  /* If the node is not the tree root and now has less than the minimum
  ** number of cells, remove it from the tree. Otherwise, update the
  ** cell in the parent node so that it tightly contains the updated
  ** node.
  */
  if( pNode->iNode!=1 ){
    RtreeNode *pParent = pNode->pParent;

    if( (pParent->iNode!=1 || NCELL(pParent)!=1) 
     && (NCELL(pNode)<RTREE_MINCELLS(pRtree))
    ){
      rc = removeNode(pRtree, pNode, iHeight);
    }else{
      fixBoundingBox(pRtree, pNode);
    }
  }

  return rc;
}

static int Reinsert(
................................................................................
        rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
      }else{
        rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
      }
    }
  }
  if( rc==SQLITE_OK ){
    fixBoundingBox(pRtree, pNode);
  }
  for(; rc==SQLITE_OK && ii<nCell; ii++){
    /* Find a node to store this cell in. pNode->iNode currently contains
    ** the height of the sub-tree headed by the cell.
    */
    RtreeNode *pInsert;
    RtreeCell *p = &aCell[aOrder[ii]];
................................................................................
      pRtree->iReinsertHeight = iHeight;
      rc = Reinsert(pRtree, pNode, pCell, iHeight);
    }
#else
    rc = SplitNode(pRtree, pNode, pCell, iHeight);
#endif
  }else{
    AdjustTree(pRtree, pNode, pCell);

    if( iHeight==0 ){
      rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
    }else{
      rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);

    }
  }
  return rc;
}

static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
  int ii;
................................................................................
){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;

  rtreeReference(pRtree);

  assert(nData>=1);
  assert(hashIsEmpty(pRtree));

  /* 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 */
................................................................................
      iDelete = sqlite3_value_int64(azData[0]);
      rc = findLeafNode(pRtree, iDelete, &pLeaf);
    }

    /* Delete the cell in question from the leaf node. */
    if( rc==SQLITE_OK ){
      int rc2;
      iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);

      rc = deleteCell(pRtree, pLeaf, iCell, 0);

      rc2 = nodeRelease(pRtree, pLeaf);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }

    /* Delete the corresponding entry in the <rtree>_rowid table. */
................................................................................
    ** 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 ){
      if( rc==SQLITE_OK && 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);
................................................................................
      if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
        sqlite3_reset(pRtree->pReadRowid);
        rc = SQLITE_CONSTRAINT;
        goto constraint;
      }
      rc = sqlite3_reset(pRtree->pReadRowid);
    }


    if( rc==SQLITE_OK ){
      rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
    }
    if( rc==SQLITE_OK ){
      int rc2;
      pRtree->iReinsertHeight = -1;
................................................................................
  char **pzErr,                       /* OUT: Error message, if any */
  int isCreate                        /* True for xCreate, false for xConnect */
){
  int rc = SQLITE_OK;
  Rtree *pRtree;
  int nDb;              /* Length of string argv[1] */
  int nName;            /* Length of string argv[2] */
  int eCoordType = (int)pAux;

  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 */
  };
................................................................................

/*
** 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){

  int rc = SQLITE_OK;

  if( rc==SQLITE_OK ){
    int utf8 = SQLITE_UTF8;
    rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
  }
  if( rc==SQLITE_OK ){
    int utf8 = SQLITE_UTF8;
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }
  if( rc==SQLITE_OK ){
    void *c = (void *)RTREE_COORD_REAL32;
    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
................................................................................
  if( rc==SQLITE_OK ){
    void *c = (void *)RTREE_COORD_INT32;
    rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
  }

  return rc;
}




































































#if !SQLITE_CORE
int sqlite3_extension_init(
  sqlite3 *db,
  char **pzErrMsg,
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi)
  return sqlite3RtreeInit(db);
}
#endif

#endif







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>
>
>












>










>
>







 







>
>
>
>
>
>
>
>
>







 







|
|
|
>
>



|
|
|
|
|
>



<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







<
|
|
<







 







<








<
|
|
|
|
|
<







 







|



|







 







>







 







>
>
>
>
>
|
|
<
|
<
>
|
|
|
|
|
|
<
<
<
<
<
<
|
|
<
<
<
|
|
<
>

>

>
>
>
>
>
>
|

>
>
|
|
<
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
|
>
>
>
>
>
>







 







|
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







|







 








|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|


>
>
>

|











|



|
>
>
>
|
>
>
>
|


>
>
>
>
>
>
>
>
>
>
>



>
|



|

|
>
>
>
>
>



|


>







|







>
>
>
>
>
>
|
>
|
>
>
|
>
>
|
|
>
|







 







|

|

|

|







 







|
>
>
>
>
>

>
>
|
<
>
>
|
>
|






|


|

>
|









>
>
>
>
>
>





|
<
<













|
>
>
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
<








>
|
|











>





>
>
>
>
>
>
>
>
>
>
|
>







 







|
<


|







 







>







 







|
>
>







>
>
>
>

<
>
>
|
|
|
|
|
|
|
|
|
<
<
|
|
|
|
|
|
|
|
|
|
|
<







 







>
|
>
>
>
>







 







>






>




<





>
>
>
>
>
>
>
>







 







|






<

>
>
>
|
>
>









>







 







|
|





|







 







|
>
>
>
>
|







 







>
|
>
|
|
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>
>


<
>
>
>
|
|
>
>
>
>
>
>
>
>
>
|
>
>
|
<
<
|
>
|
|
<
<
>
>








>






|
>
|
|
|
>
|
<
>
>
>
>







 







|

>











|
>
|
|
|
>
>







>







 







<
|
>
|
|
<


|







 







|







 







|
>
|
|
|
|
>







 







<







 







|
>
|
>







 







|
|
|
|
|
|
|
|
>
>
|
|
|
|
<







 







>







 







|







 







>
|

<
<
|
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>













8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
..
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
...
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
...
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249















250
251
252
253
254
255
256
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
...
378
379
380
381
382
383
384

385
386

387
388
389
390
391
392
393
...
399
400
401
402
403
404
405

406
407
408
409
410
411
412
413

414
415
416
417
418

419
420
421
422
423
424
425
...
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
...
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
...
475
476
477
478
479
480
481
482
483
484
485
486
487
488

489

490
491
492
493
494
495
496






497
498



499
500

501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516

517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
...
584
585
586
587
588
589
590
591

592
593
594
595
596
597
598
...
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
...
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
...
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
....
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057

1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096


1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
....
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
....
1237
1238
1239
1240
1241
1242
1243
1244

1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
....
1318
1319
1320
1321
1322
1323
1324
1325

1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
....
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
....
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397

1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408


1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419

1420
1421
1422
1423
1424
1425
1426
....
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
....
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636

1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
....
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678

1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
....
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
....
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
....
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
....
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333

2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351


2352
2353
2354
2355


2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379

2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
....
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
....
2451
2452
2453
2454
2455
2456
2457

2458
2459
2460
2461

2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
....
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
....
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
....
2670
2671
2672
2673
2674
2675
2676

2677
2678
2679
2680
2681
2682
2683
....
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
....
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740

2741
2742
2743
2744
2745
2746
2747
....
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
....
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
....
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178


3179

3180
3181
3182
3183
3184
3185
3186
....
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
*/

/*
** Database Format of R-Tree Tables
** --------------------------------
**
** The data structure for a single virtual r-tree table is stored in three 
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the r-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** The data for each node of the r-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.
**
** The root node of an r-tree always exists, even if the r-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   1. If the node is the root node (node 1), then the first 2 bytes
**      of the node contain the tree depth as a big-endian integer.
**      For non-root nodes, the first 2 bytes are left unused.
**
**   2. The next 2 bytes contain the number of entries currently 
**      stored in the node.
**
**   3. The remainder of the node contains the node entries. Each entry
**      consists of a single 8-byte integer followed by an even number
**      of 4-byte coordinates. For leaf nodes the integer is the rowid
**      of a record. For internal nodes it is the node number of a
**      child page.
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
** same data-structure is used for all, but the algorithms for insert and
................................................................................
  #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

#include <string.h>
#include <assert.h>

#ifndef SQLITE_AMALGAMATION
#include "sqlite3rtree.h"
typedef sqlite3_int64 i64;
typedef unsigned char u8;
typedef unsigned int u32;
#endif

typedef struct Rtree Rtree;
typedef struct RtreeCursor RtreeCursor;
typedef struct RtreeNode RtreeNode;
typedef struct RtreeCell RtreeCell;
typedef struct RtreeConstraint RtreeConstraint;
typedef struct RtreeMatchArg RtreeMatchArg;
typedef struct RtreeGeomCallback RtreeGeomCallback;
typedef union RtreeCoord RtreeCoord;

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

/* Size of hash table Rtree.aHash. This hash table is not expected to
** ever contain very many entries, so a fixed number of buckets is 
................................................................................
** If an R*-tree "Reinsert" operation is required, the same number of
** cells are removed from the overfull node and reinserted into the tree.
*/
#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
#define RTREE_MAXCELLS 51

/*
** The smallest possible node-size is (512-64)==448 bytes. And the largest
** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
** Therefore all non-root nodes must contain at least 3 entries. Since 
** 2^40 is greater than 2^64, an r-tree structure always has a depth of
** 40 or less.
*/
#define RTREE_MAX_DEPTH 40

/* 
** An rtree cursor object.
*/
struct RtreeCursor {
  sqlite3_vtab_cursor base;
  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
  int iCell;                        /* Index of current cell in pNode */
................................................................................
    ((double)coord.i)                             \
)

/*
** A search constraint.
*/
struct RtreeConstraint {
  int iCoord;                     /* Index of constrained coordinate */
  int op;                         /* Constraining operation */
  double rValue;                  /* Constraint value. */
  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
  sqlite3_rtree_geometry *pGeom;  /* Constraint callback argument for a MATCH */
};

/* Possible values for RtreeConstraint.op */
#define RTREE_EQ    0x41
#define RTREE_LE    0x42
#define RTREE_LT    0x43
#define RTREE_GE    0x44
#define RTREE_GT    0x45
#define RTREE_MATCH 0x46

/* 
** An rtree structure node.















*/
struct RtreeNode {
  RtreeNode *pParent;               /* Parent node */
  i64 iNode;
  int nRef;
  int isDirty;
  u8 *zData;
................................................................................
** Structure to store a deserialized rtree record.
*/
struct RtreeCell {
  i64 iRowid;
  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
};


/*
** Value for the first field of every RtreeMatchArg object. The MATCH
** operator tests that the first field of a blob operand matches this
** value to avoid operating on invalid blobs (which could cause a segfault).
*/
#define RTREE_GEOMETRY_MAGIC 0x891245AB

/*
** An instance of this structure must be supplied as a blob argument to
** the right-hand-side of an SQL MATCH operator used to constrain an
** r-tree query.
*/
struct RtreeMatchArg {
  u32 magic;                      /* Always RTREE_GEOMETRY_MAGIC */
  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
  void *pContext;
  int nParam;
  double aParam[1];
};

/*
** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
** a single instance of the following structure is allocated. It is used
** as the context for the user-function created by by s_r_g_c(). The object
** is eventually deleted by the destructor mechanism provided by
** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
** the geometry callback function).
*/
struct RtreeGeomCallback {
  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *);
  void *pContext;
};

#ifndef MAX
# define MAX(x,y) ((x) < (y) ? (y) : (x))
#endif
#ifndef MIN
# define MIN(x,y) ((x) > (y) ? (y) : (x))
#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){
................................................................................

/*
** 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);
  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;
................................................................................
nodeAcquire(
  Rtree *pRtree,             /* R-tree structure */
  i64 iNode,                 /* Node number to load */
  RtreeNode *pParent,        /* Either the parent node or NULL */
  RtreeNode **ppNode         /* OUT: Acquired node */
){
  int rc;
  int rc2 = SQLITE_OK;
  RtreeNode *pNode;

  /* 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)) ){
    assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
................................................................................
      pNode->pParent = pParent;
    }
    pNode->nRef++;
    *ppNode = pNode;
    return SQLITE_OK;
  }

  sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
  rc = sqlite3_step(pRtree->pReadNode);
  if( rc==SQLITE_ROW ){
    const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
    if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){
      pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize);
      if( !pNode ){

        rc2 = SQLITE_NOMEM;

      }else{
        pNode->pParent = pParent;
        pNode->zData = (u8 *)&pNode[1];
        pNode->nRef = 1;
        pNode->iNode = iNode;
        pNode->isDirty = 0;
        pNode->pNext = 0;






        memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
        nodeReference(pParent);



      }
    }

  }
  rc = sqlite3_reset(pRtree->pReadNode);
  if( rc==SQLITE_OK ) rc = rc2;

  /* 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
  ** the root node. A height of one means the children of the root node
  ** are the leaves, and so on. If the depth as specified on the root node
  ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
  */
  if( pNode && iNode==1 ){
    pRtree->iDepth = readInt16(pNode->zData);
    if( pRtree->iDepth>RTREE_MAX_DEPTH ){
      rc = SQLITE_CORRUPT;
    }
  }


  /* If no error has occurred so far, check if the "number of entries"
  ** field on the node is too large. If so, set the return code to 
  ** SQLITE_CORRUPT.
  */
  if( pNode && rc==SQLITE_OK ){
    if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
      rc = SQLITE_CORRUPT;
    }
  }

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

  return rc;
}

/*
** Overwrite cell iCell of node pNode with the contents of pCell.
*/
static void nodeOverwriteCell(
................................................................................
){
  int nCell;                    /* Current number of cells in pNode */
  int nMaxCell;                 /* Maximum number of cells for pNode */

  nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
  nCell = NCELL(pNode);

  assert( nCell<=nMaxCell );

  if( nCell<nMaxCell ){
    nodeOverwriteCell(pRtree, pNode, pCell, nCell);
    writeInt16(&pNode->zData[2], nCell+1);
    pNode->isDirty = 1;
  }

  return (nCell==nMaxCell);
................................................................................
    rc = SQLITE_OK;
  }
  *ppCursor = (sqlite3_vtab_cursor *)pCsr;

  return rc;
}


/*
** Free the RtreeCursor.aConstraint[] array and its contents.
*/
static void freeCursorConstraints(RtreeCursor *pCsr){
  if( pCsr->aConstraint ){
    int i;                        /* Used to iterate through constraint array */
    for(i=0; i<pCsr->nConstraint; i++){
      sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
      if( pGeom ){
        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
        sqlite3_free(pGeom);
      }
    }
    sqlite3_free(pCsr->aConstraint);
    pCsr->aConstraint = 0;
  }
}

/* 
** Rtree virtual table module xClose method.
*/
static int rtreeClose(sqlite3_vtab_cursor *cur){
  Rtree *pRtree = (Rtree *)(cur->pVtab);
  int rc;
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  freeCursorConstraints(pCsr);
  rc = nodeRelease(pRtree, pCsr->pNode);
  sqlite3_free(pCsr);
  return rc;
}

/*
** Rtree virtual table module xEof method.
................................................................................
** Return non-zero if the cursor does not currently point to a valid 
** record (i.e if the scan has finished), or zero otherwise.
*/
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return (pCsr->pNode==0);
}

/*
** The r-tree constraint passed as the second argument to this function is
** guaranteed to be a MATCH constraint.
*/
static int testRtreeGeom(
  Rtree *pRtree,                  /* R-Tree object */
  RtreeConstraint *pConstraint,   /* MATCH constraint to test */
  RtreeCell *pCell,               /* Cell to test */
  int *pbRes                      /* OUT: Test result */
){
  int i;
  double aCoord[RTREE_MAX_DIMENSIONS*2];
  int nCoord = pRtree->nDim*2;

  assert( pConstraint->op==RTREE_MATCH );
  assert( pConstraint->pGeom );

  for(i=0; i<nCoord; i++){
    aCoord[i] = DCOORD(pCell->aCoord[i]);
  }
  return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
}

/* 
** Cursor pCursor currently points to a cell in a non-leaf page.
** Set *pbEof to true if the sub-tree headed by the cell is filtered
** (excluded) by the constraints in the pCursor->aConstraint[] 
** array, or false otherwise.
**
** Return SQLITE_OK if successful or an SQLite error code if an error
** occurs within a geometry callback.
*/
static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
  RtreeCell cell;
  int ii;
  int bRes = 0;

  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
    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 || p->op==RTREE_MATCH
    );

    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;

      case RTREE_EQ:
        bRes = (p->rValue>cell_max || p->rValue<cell_min);
        break;

      default: {
        int rc;
        assert( p->op==RTREE_MATCH );
        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        bRes = !bRes;
        break;
      }
    }
  }

  *pbEof = bRes;
  return SQLITE_OK;
}

/* 
** Test if the cell that cursor pCursor currently points to
** would be filtered (excluded) by the constraints in the 
** pCursor->aConstraint[] array. If so, set *pbEof to true before
** returning. If the cell is not filtered (excluded) by the constraints,
** set pbEof to zero.
**
** Return SQLITE_OK if successful or an SQLite error code if an error
** occurs within a geometry callback.
**
** This function assumes that the cell is part of a leaf node.
*/
static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
  RtreeCell cell;
  int ii;
  *pbEof = 0;

  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
  for(ii=0; ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    double coord = DCOORD(cell.aCoord[p->iCoord]);
    int res;
    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
    );
    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;
      case RTREE_EQ: res = (coord==p->rValue); break;
      default: {
        int rc;
        assert( p->op==RTREE_MATCH );
        rc = testRtreeGeom(pRtree, p, &cell, &res);
        if( rc!=SQLITE_OK ){
          return rc;
        }
        break;
      }
    }

    if( !res ){
      *pbEof = 1;
      return SQLITE_OK;
    }
  }

  return SQLITE_OK;
}

/*
** Cursor pCursor currently points at a node that heads a sub-tree of
** height iHeight (if iHeight==0, then the node is a leaf). Descend
** to point to the left-most cell of the sub-tree that matches the 
** configured constraints.
................................................................................

  RtreeNode *pSavedNode = pCursor->pNode;
  int iSavedCell = pCursor->iCell;

  assert( iHeight>=0 );

  if( iHeight==0 ){
    rc = testRtreeEntry(pRtree, pCursor, &isEof);
  }else{
    rc = testRtreeCell(pRtree, pCursor, &isEof);
  }
  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
    *pEof = isEof;
    return rc;
  }

  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
  if( rc!=SQLITE_OK ){
    return rc;
  }
................................................................................
  return SQLITE_OK;
}

/*
** One of the cells in node pNode is guaranteed to have a 64-bit 
** integer value equal to iRowid. Return the index of this cell.
*/
static int nodeRowidIndex(
  Rtree *pRtree, 
  RtreeNode *pNode, 
  i64 iRowid,
  int *piIndex
){
  int ii;
  int nCell = NCELL(pNode);
  for(ii=0; ii<nCell; ii++){
    if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){

      *piIndex = ii;
      return SQLITE_OK;
    }
  }
  return SQLITE_CORRUPT;
}

/*
** Return the index of the cell containing a pointer to node pNode
** in its parent. If pNode is the root node, return -1.
*/
static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
  RtreeNode *pParent = pNode->pParent;
  if( pParent ){
    return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
  }
  *piIndex = -1;
  return SQLITE_OK;
}

/* 
** 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;
        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
        if( rc!=SQLITE_OK || !isEof ){
          return rc;
        }
      }
      pCsr->pNode = pNode->pParent;
      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
      if( rc!=SQLITE_OK ){
        return rc;
      }
      nodeReference(pCsr->pNode);
      nodeRelease(pRtree, pNode);
      iHeight++;
    }
  }

  return rc;
................................................................................
    sqlite3_reset(pRtree->pReadRowid);
  }else{
    rc = sqlite3_reset(pRtree->pReadRowid);
  }
  return rc;
}

/*
** This function is called to configure the RtreeConstraint object passed
** as the second argument for a MATCH constraint. The value passed as the
** first argument to this function is the right-hand operand to the MATCH
** operator.
*/
static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
  RtreeMatchArg *p;
  sqlite3_rtree_geometry *pGeom;
  int nBlob;

  /* Check that value is actually a blob. */
  if( !sqlite3_value_type(pValue)==SQLITE_BLOB ) return SQLITE_ERROR;

  /* Check that the blob is roughly the right size. */
  nBlob = sqlite3_value_bytes(pValue);
  if( nBlob<sizeof(RtreeMatchArg) 
   || ((nBlob-sizeof(RtreeMatchArg))%sizeof(double))!=0
  ){
    return SQLITE_ERROR;
  }

  pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
      sizeof(sqlite3_rtree_geometry) + nBlob
  );
  if( !pGeom ) return SQLITE_NOMEM;
  memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
  p = (RtreeMatchArg *)&pGeom[1];

  memcpy(p, sqlite3_value_blob(pValue), nBlob);
  if( p->magic!=RTREE_GEOMETRY_MAGIC 
   || nBlob!=(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(double))
  ){
    sqlite3_free(pGeom);
    return SQLITE_ERROR;
  }

  pGeom->pContext = p->pContext;
  pGeom->nParam = p->nParam;
  pGeom->aParam = p->aParam;

  pCons->xGeom = p->xGeom;
  pCons->pGeom = pGeom;
  return SQLITE_OK;
}

/* 
** Rtree virtual table module xFilter method.
*/
static int rtreeFilter(
  sqlite3_vtab_cursor *pVtabCursor, 
  int idxNum, const char *idxStr,
................................................................................

  RtreeNode *pRoot = 0;
  int ii;
  int rc = SQLITE_OK;

  rtreeReference(pRtree);

  freeCursorConstraints(pCsr);

  pCsr->iStrategy = idxNum;

  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 );
      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
    }
  }else{
    /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
    ** with the configured constraints. 
    */
    if( argc>0 ){
      pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
      pCsr->nConstraint = argc;
      if( !pCsr->aConstraint ){
        rc = SQLITE_NOMEM;
      }else{
        memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
        assert( (idxStr==0 && argc==0) || strlen(idxStr)==argc*2 );
        for(ii=0; ii<argc; ii++){
          RtreeConstraint *p = &pCsr->aConstraint[ii];
          p->op = idxStr[ii*2];
          p->iCoord = idxStr[ii*2+1]-'a';
          if( p->op==RTREE_MATCH ){
            /* A MATCH operator. The right-hand-side must be a blob that
            ** can be cast into an RtreeMatchArg object. One created using
            ** an sqlite3_rtree_geometry_callback() SQL user function.
            */
            rc = deserializeGeometry(argv[ii], p);
            if( rc!=SQLITE_OK ){
              break;
            }
          }else{
            p->rValue = sqlite3_value_double(argv[ii]);
          }
        }
      }
    }
  
    if( rc==SQLITE_OK ){
      pCsr->pNode = 0;
      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
................................................................................
** Rtree virtual table module xBestIndex method. There are three
** table scan strategies to choose from (in order from most to 
** least desirable):
**
**   idxNum     idxStr        Strategy
**   ------------------------------------------------
**     1        Unused        Direct lookup by rowid.
**     2        See below     R-tree query or full-table scan.

**   ------------------------------------------------
**
** If strategy 1 is used, then idxStr is not meaningful. If strategy
** 2 is used, idxStr is formatted to contain 2 bytes for each 
** constraint used. The first two bytes of idxStr correspond to 
** the constraint in sqlite3_index_info.aConstraintUsage[] with
** (argvIndex==1) etc.
**
** The first of each pair of bytes in idxStr identifies the constraint
** operator as follows:
................................................................................
**   Operator    Byte Value
**   ----------------------
**      =        0x41 ('A')
**     <=        0x42 ('B')
**      <        0x43 ('C')
**     >=        0x44 ('D')
**      >        0x45 ('E')
**   MATCH       0x46 ('F')
**   ----------------------
**
** The second of each pair of bytes identifies the coordinate column
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
................................................................................
      ** considered almost as quick as a direct rowid lookup (for which 
      ** sqlite uses an internal cost of 0.0).
      */ 
      pIdxInfo->estimatedCost = 10.0;
      return SQLITE_OK;
    }

    if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){
      int j, opmsk;
      static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
      u8 op = 0;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
        default:
          assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
          op = RTREE_MATCH; 
          break;
      }

      assert( op!=0 );

      /* Make sure this particular constraint has not been used before.
      ** If it has been used before, ignore it.
      **
      ** A <= or < can be used if there is a prior >= or >.
      ** A >= or > can be used if there is a prior < or <=.
      ** A <= or < is disqualified if there is a prior <=, <, or ==.
      ** A >= or > is disqualified if there is a prior >=, >, or ==.
      ** A == is disqualifed if there is any prior constraint.
      */


      assert( compatible[RTREE_EQ & 7]==0 );
      assert( compatible[RTREE_LT & 7]==1 );
      assert( compatible[RTREE_LE & 7]==1 );
      assert( compatible[RTREE_GT & 7]==2 );
      assert( compatible[RTREE_GE & 7]==2 );
      cCol = p->iColumn - 1 + 'a';
      opmsk = compatible[op & 7];
      for(j=0; j<iIdx; j+=2){
        if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
          op = 0;
          break;

        }
      }
      if( op ){
        assert( iIdx<sizeof(zIdxStr)-1 );
        zIdxStr[iIdx++] = op;
        zIdxStr[iIdx++] = cCol;
        pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
................................................................................
  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;
      }
    }

................................................................................
}

/*
** A cell with the same content as pCell has just been inserted into
** the node pNode. This function updates the bounding box cells in
** all ancestor elements.
*/
static int AdjustTree(
  Rtree *pRtree,                    /* Rtree table */
  RtreeNode *pNode,                 /* Adjust ancestry of this node. */
  RtreeCell *pCell                  /* This cell was just inserted */
){
  RtreeNode *p = pNode;
  while( p->pParent ){

    RtreeNode *pParent = p->pParent;
    RtreeCell cell;
    int iCell;

    if( nodeParentIndex(pRtree, p, &iCell) ){
      return SQLITE_CORRUPT;
    }

    nodeGetCell(pRtree, pParent, iCell, &cell);
    if( !cellContains(pRtree, &cell, pCell) ){
      cellUnion(pRtree, &cell, pCell);
      nodeOverwriteCell(pRtree, pParent, &cell, iCell);
    }
 
    p = pParent;
  }
  return SQLITE_OK;
}

/*
** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
*/
static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
  sqlite3_bind_int64(pRtree->pWriteRowid, 1, 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;
  }
................................................................................
  memset(pRight->zData, 0, pRtree->iNodeSize);

  rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
  if( rc!=SQLITE_OK ){
    goto splitnode_out;
  }

  /* Ensure both child nodes have node numbers assigned to them by calling
  ** nodeWrite(). Node pRight always needs a node number, as it was created
  ** by nodeNew() above. But node pLeft sometimes already has a node number.
  ** In this case avoid the all to nodeWrite().
  */
  if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight))
   || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
  ){
    goto splitnode_out;
  }

  rightbbox.iRowid = pRight->iNode;
  leftbbox.iRowid = pLeft->iNode;
................................................................................
  if( pNode->iNode==1 ){
    rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
    if( rc!=SQLITE_OK ){
      goto splitnode_out;
    }
  }else{
    RtreeNode *pParent = pLeft->pParent;
    int iCell;
    rc = nodeParentIndex(pRtree, pLeft, &iCell);
    if( rc==SQLITE_OK ){
      nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
      rc = AdjustTree(pRtree, pParent, &leftbbox);
    }
    if( rc!=SQLITE_OK ){
      goto splitnode_out;
    }
  }
  if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
    goto splitnode_out;
  }

  for(i=0; i<NCELL(pRight); i++){
    i64 iRowid = nodeGetRowid(pRtree, pRight, i);
................................................................................
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, load all ancestor nodes of pLeaf into memory and populate
** the pLeaf->pParent chain all the way up to the root node.
**
** This operation is required when a row is deleted (or updated - an update
** is implemented as a delete followed by an insert). SQLite provides the
** rowid of the row to delete, which can be used to find the leaf on which
** the entry resides (argument pLeaf). Once the leaf is located, this 
** function is called to determine its ancestry.
*/
static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){
  int rc = SQLITE_OK;

  RtreeNode *pChild = pLeaf;
  while( rc==SQLITE_OK && pChild->iNode!=1 && pChild->pParent==0 ){
    int rc2 = SQLITE_OK;          /* sqlite3_reset() return code */
    sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode);
    rc = sqlite3_step(pRtree->pReadParent);
    if( rc==SQLITE_ROW ){
      RtreeNode *pTest;           /* Used to test for reference loops */
      i64 iNode;                  /* Node number of parent node */

      /* Before setting pChild->pParent, test that we are not creating a
      ** loop of references (as we would if, say, pChild==pParent). We don't
      ** want to do this as it leads to a memory leak when trying to delete
      ** the referenced counted node structures.
      */
      iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
      for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent);
      if( !pTest ){
        rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent);


      }
    }
    rc = sqlite3_reset(pRtree->pReadParent);
    if( rc==SQLITE_OK ) rc = rc2;


    if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT;
    pChild = pChild->pParent;
  }
  return rc;
}

static int deleteCell(Rtree *, RtreeNode *, int, int);

static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
  int rc;
  int rc2;
  RtreeNode *pParent;
  int iCell;

  assert( pNode->nRef==1 );

  /* Remove the entry in the parent cell. */
  rc = nodeParentIndex(pRtree, pNode, &iCell);
  if( rc==SQLITE_OK ){
    pParent = pNode->pParent;
    pNode->pParent = 0;
    rc = deleteCell(pRtree, pParent, iCell, iHeight+1);
  }
  rc2 = nodeRelease(pRtree, pParent);

  if( rc==SQLITE_OK ){
    rc = rc2;
  }
  if( rc!=SQLITE_OK ){
    return rc;
  }

  /* Remove the xxx_node entry. */
  sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
  sqlite3_step(pRtree->pDeleteNode);
  if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
................................................................................
  pNode->pNext = pRtree->pDeleted;
  pNode->nRef++;
  pRtree->pDeleted = pNode;

  return SQLITE_OK;
}

static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
  RtreeNode *pParent = pNode->pParent;
  int rc = SQLITE_OK; 
  if( pParent ){
    int ii; 
    int nCell = NCELL(pNode);
    RtreeCell box;                            /* Bounding box for pNode */
    nodeGetCell(pRtree, pNode, 0, &box);
    for(ii=1; ii<nCell; ii++){
      RtreeCell cell;
      nodeGetCell(pRtree, pNode, ii, &cell);
      cellUnion(pRtree, &box, &cell);
    }
    box.iRowid = pNode->iNode;
    rc = nodeParentIndex(pRtree, pNode, &ii);
    if( rc==SQLITE_OK ){
      nodeOverwriteCell(pRtree, pParent, &box, ii);
      rc = fixBoundingBox(pRtree, pParent);
    }
  }
  return rc;
}

/*
** Delete the cell at index iCell of node pNode. After removing the
** cell, adjust the r-tree data structure if required.
*/
static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
  RtreeNode *pParent;
  int rc;

  if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
    return rc;
  }

  /* Remove the cell from the node. This call just moves bytes around
................................................................................
  nodeDeleteCell(pRtree, pNode, iCell);

  /* If the node is not the tree root and now has less than the minimum
  ** number of cells, remove it from the tree. Otherwise, update the
  ** cell in the parent node so that it tightly contains the updated
  ** node.
  */

  pParent = pNode->pParent;
  assert( pParent || pNode->iNode==1 );
  if( pParent ){
    if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){

      rc = removeNode(pRtree, pNode, iHeight);
    }else{
      rc = fixBoundingBox(pRtree, pNode);
    }
  }

  return rc;
}

static int Reinsert(
................................................................................
        rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
      }else{
        rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
      }
    }
  }
  if( rc==SQLITE_OK ){
    rc = fixBoundingBox(pRtree, pNode);
  }
  for(; rc==SQLITE_OK && ii<nCell; ii++){
    /* Find a node to store this cell in. pNode->iNode currently contains
    ** the height of the sub-tree headed by the cell.
    */
    RtreeNode *pInsert;
    RtreeCell *p = &aCell[aOrder[ii]];
................................................................................
      pRtree->iReinsertHeight = iHeight;
      rc = Reinsert(pRtree, pNode, pCell, iHeight);
    }
#else
    rc = SplitNode(pRtree, pNode, pCell, iHeight);
#endif
  }else{
    rc = AdjustTree(pRtree, pNode, pCell);
    if( rc==SQLITE_OK ){
      if( iHeight==0 ){
        rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
      }else{
        rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
      }
    }
  }
  return rc;
}

static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
  int ii;
................................................................................
){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;

  rtreeReference(pRtree);

  assert(nData>=1);


  /* 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 */
................................................................................
      iDelete = sqlite3_value_int64(azData[0]);
      rc = findLeafNode(pRtree, iDelete, &pLeaf);
    }

    /* Delete the cell in question from the leaf node. */
    if( rc==SQLITE_OK ){
      int rc2;
      rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
      if( rc==SQLITE_OK ){
        rc = deleteCell(pRtree, pLeaf, iCell, 0);
      }
      rc2 = nodeRelease(pRtree, pLeaf);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }

    /* Delete the corresponding entry in the <rtree>_rowid table. */
................................................................................
    ** 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 ){
      int rc2;
      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);
      }
      rc2 = nodeRelease(pRtree, pChild);
      if( rc==SQLITE_OK ) rc = rc2;
      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);
................................................................................
      if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
        sqlite3_reset(pRtree->pReadRowid);
        rc = SQLITE_CONSTRAINT;
        goto constraint;
      }
      rc = sqlite3_reset(pRtree->pReadRowid);
    }
    *pRowid = cell.iRowid;

    if( rc==SQLITE_OK ){
      rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
    }
    if( rc==SQLITE_OK ){
      int rc2;
      pRtree->iReinsertHeight = -1;
................................................................................
  char **pzErr,                       /* OUT: Error message, if any */
  int isCreate                        /* True for xCreate, false for xConnect */
){
  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);

  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 */
  };
................................................................................

/*
** 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){
  const int utf8 = SQLITE_UTF8;
  int rc;



  rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);

  if( rc==SQLITE_OK ){
    int utf8 = SQLITE_UTF8;
    rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
  }
  if( rc==SQLITE_OK ){
    void *c = (void *)RTREE_COORD_REAL32;
    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
................................................................................
  if( rc==SQLITE_OK ){
    void *c = (void *)RTREE_COORD_INT32;
    rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
  }

  return rc;
}

/*
** A version of sqlite3_free() that can be used as a callback. This is used
** in two places - as the destructor for the blob value returned by the
** invocation of a geometry function, and as the destructor for the geometry
** functions themselves.
*/
static void doSqlite3Free(void *p){
  sqlite3_free(p);
}

/*
** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
** scalar user function. This C function is the callback used for all such
** registered SQL functions.
**
** The scalar user functions return a blob that is interpreted by r-tree
** table MATCH operators.
*/
static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
  RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
  RtreeMatchArg *pBlob;
  int nBlob;

  nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(double);
  pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob);
  if( !pBlob ){
    sqlite3_result_error_nomem(ctx);
  }else{
    int i;
    pBlob->magic = RTREE_GEOMETRY_MAGIC;
    pBlob->xGeom = pGeomCtx->xGeom;
    pBlob->pContext = pGeomCtx->pContext;
    pBlob->nParam = nArg;
    for(i=0; i<nArg; i++){
      pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
    }
    sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
  }
}

/*
** Register a new geometry function for use with the r-tree MATCH operator.
*/
int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int, double *, int *),
  void *pContext
){
#if 0
  RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */

  /* Allocate and populate the context object. */
  pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
  if( !pGeomCtx ) return SQLITE_NOMEM;
  pGeomCtx->xGeom = xGeom;
  pGeomCtx->pContext = pContext;

  /* Create the new user-function. Register a destructor function to delete
  ** the context object when it is no longer required.  */
  return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
      (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
  );
#endif
  return SQLITE_MISUSE;
}

#if !SQLITE_CORE
int sqlite3_extension_init(
  sqlite3 *db,
  char **pzErrMsg,
  const sqlite3_api_routines *pApi
){
  SQLITE_EXTENSION_INIT2(pApi)
  return sqlite3RtreeInit(db);
}
#endif

#endif

Added ext/rtree/sqlite3rtree.h.

















































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
** 2010 August 30
**
** 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.
**
*************************************************************************
*/

#ifndef _SQLITE3RTREE_H_
#define _SQLITE3RTREE_H_

#include <sqlite3.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;

/*
** Register a geometry callback named zGeom that can be used as part of an
** R-Tree geometry query as follows:
**
**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...)
*/
int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
  void *pContext
);


/*
** A pointer to a structure of the following type is passed as the first
** argument to callbacks registered using rtree_geometry_callback().
*/
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam[] */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
};


#ifdef __cplusplus
}  /* end of the 'extern "C"' block */
#endif

#endif  /* ifndef _SQLITE3RTREE_H_ */

Changes to publish.sh.

30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
..
83
84
85
86
87
88
89














90
91
92
93
94
95
96
gcc $CFLAGS -Itsrc sqlite3.c tsrc/shell.c -o sqlite3 -ldl
strip sqlite3
mv sqlite3 sqlite3-$VERS.bin
gzip sqlite3-$VERS.bin
chmod 644 sqlite3-$VERS.bin.gz
mv sqlite3-$VERS.bin.gz doc

# Build a source archive useful for windows.
#
make target_source
cd tsrc
echo '***** BUILDING preprocessed source archives'
rm fts[12]* icu*
rm -f ../doc/sqlite-source-$VERSW.zip
zip ../doc/sqlite-source-$VERSW.zip *
cd ..
cp tsrc/sqlite3.h tsrc/sqlite3ext.h .
pwd
zip doc/sqlite-amalgamation-$VERSW.zip sqlite3.c sqlite3.h sqlite3ext.h

# Build the sqlite.so and tclsqlite.so shared libraries
# under Linux
#
TCLDIR=/home/drh/tcltk/846/linux/846linux
TCLSTUBLIB=$TCLDIR/libtclstub8.4g.a
CFLAGS="-Os -DSQLITE_ENABLE_FTS3=3 -DSQLITE_ENABLE_RTREE=1"
CFLAGS="$CFLAGS -DHAVE_LOCALTIME_R=1 -DHAVE_GMTIME_R=1"
................................................................................
#
OPTS='-DSTATIC_BUILD=1 -DNDEBUG=1 -DSQLITE_THREADSAFE=0'
OPTS="$OPTS -DSQLITE_ENABLE_FTS3=1 -DSQLITE_ENABLE_RTREE=1"
i386-mingw32msvc-gcc -Os $OPTS -Itsrc -I$TCLDIR sqlite3.c tsrc/shell.c \
      -o sqlite3.exe
zip doc/sqlite-$VERSW.zip sqlite3.exe















# Construct a tarball of the source tree
#
echo '***** BUILDING source archive'
ORIGIN=`pwd`
cd $srcdir
chmod +x configure
cd ..







<
<
<
<
<
<
<
<
<
<
<
<
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>







30
31
32
33
34
35
36













37
38
39
40
41
42
43
..
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
gcc $CFLAGS -Itsrc sqlite3.c tsrc/shell.c -o sqlite3 -ldl
strip sqlite3
mv sqlite3 sqlite3-$VERS.bin
gzip sqlite3-$VERS.bin
chmod 644 sqlite3-$VERS.bin.gz
mv sqlite3-$VERS.bin.gz doc














# Build the sqlite.so and tclsqlite.so shared libraries
# under Linux
#
TCLDIR=/home/drh/tcltk/846/linux/846linux
TCLSTUBLIB=$TCLDIR/libtclstub8.4g.a
CFLAGS="-Os -DSQLITE_ENABLE_FTS3=3 -DSQLITE_ENABLE_RTREE=1"
CFLAGS="$CFLAGS -DHAVE_LOCALTIME_R=1 -DHAVE_GMTIME_R=1"
................................................................................
#
OPTS='-DSTATIC_BUILD=1 -DNDEBUG=1 -DSQLITE_THREADSAFE=0'
OPTS="$OPTS -DSQLITE_ENABLE_FTS3=1 -DSQLITE_ENABLE_RTREE=1"
i386-mingw32msvc-gcc -Os $OPTS -Itsrc -I$TCLDIR sqlite3.c tsrc/shell.c \
      -o sqlite3.exe
zip doc/sqlite-$VERSW.zip sqlite3.exe

# Build a source archive useful for windows.
#
make target_source
cd tsrc
echo '***** BUILDING preprocessed source archives'
rm fts[12]* icu*
rm -f ../doc/sqlite-source-$VERSW.zip
zip ../doc/sqlite-source-$VERSW.zip *
cd ..
cp tsrc/sqlite3.h tsrc/sqlite3ext.h .
cp tsrc/shell.c .
pwd
zip doc/sqlite-amalgamation-$VERSW.zip sqlite3.c sqlite3.h sqlite3ext.h shell.c sqlite3.def

# Construct a tarball of the source tree
#
echo '***** BUILDING source archive'
ORIGIN=`pwd`
cd $srcdir
chmod +x configure
cd ..

Changes to src/btree.c.

4726
4727
4728
4729
4730
4731
4732




4733
4734
4735
4736
4737
4738
4739
        if( rc ){
          goto end_allocate_page;
        }
        if( k==0 ){
          if( !pPrevTrunk ){
            memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
          }else{




            memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
          }
        }else{
          /* The trunk page is required by the caller but it contains 
          ** pointers to free-list leaves. The first leaf becomes a trunk
          ** page in this case.
          */







>
>
>
>







4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
        if( rc ){
          goto end_allocate_page;
        }
        if( k==0 ){
          if( !pPrevTrunk ){
            memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
          }else{
            rc = sqlite3PagerWrite(pPrevTrunk->pDbPage);
            if( rc!=SQLITE_OK ){
              goto end_allocate_page;
            }
            memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
          }
        }else{
          /* The trunk page is required by the caller but it contains 
          ** pointers to free-list leaves. The first leaf becomes a trunk
          ** page in this case.
          */

Changes to src/ctime.c.

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#endif
#ifdef SQLITE_ENABLE_FTS3
  "ENABLE_FTS3",
#endif
#ifdef SQLITE_ENABLE_FTS3_PARENTHESIS
  "ENABLE_FTS3_PARENTHESIS",
#endif
#if 0 /* Disabled because FTS4 is not ready for publication */
#ifdef SQLITE_ENABLE_FTS4
  "ENABLE_FTS4",
#endif
#endif
#ifdef SQLITE_ENABLE_ICU
  "ENABLE_ICU",
#endif
#ifdef SQLITE_ENABLE_IOTRACE
  "ENABLE_IOTRACE",
#endif







<


<







80
81
82
83
84
85
86

87
88

89
90
91
92
93
94
95
#endif
#ifdef SQLITE_ENABLE_FTS3
  "ENABLE_FTS3",
#endif
#ifdef SQLITE_ENABLE_FTS3_PARENTHESIS
  "ENABLE_FTS3_PARENTHESIS",
#endif

#ifdef SQLITE_ENABLE_FTS4
  "ENABLE_FTS4",

#endif
#ifdef SQLITE_ENABLE_ICU
  "ENABLE_ICU",
#endif
#ifdef SQLITE_ENABLE_IOTRACE
  "ENABLE_IOTRACE",
#endif

Changes to src/os_unix.c.

3344
3345
3346
3347
3348
3349
3350






3351
3352
3353
3354
3355
3356
3357
    case SQLITE_FCNTL_LOCKSTATE: {
      *(int*)pArg = ((unixFile*)id)->locktype;
      return SQLITE_OK;
    }
    case SQLITE_LAST_ERRNO: {
      *(int*)pArg = ((unixFile*)id)->lastErrno;
      return SQLITE_OK;






    }
#ifndef NDEBUG
    /* The pager calls this method to signal that it has done
    ** a rollback and that the database is therefore unchanged and
    ** it hence it is OK for the transaction change counter to be
    ** unchanged.
    */







>
>
>
>
>
>







3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
    case SQLITE_FCNTL_LOCKSTATE: {
      *(int*)pArg = ((unixFile*)id)->locktype;
      return SQLITE_OK;
    }
    case SQLITE_LAST_ERRNO: {
      *(int*)pArg = ((unixFile*)id)->lastErrno;
      return SQLITE_OK;
    }
    case SQLITE_FCNTL_SIZE_HINT: {
      sqlite3_int64 szFile = *(sqlite3_int64*)pArg;
      unixFile *pFile = (unixFile*)id;
      ftruncate(pFile->h, szFile);
      return SQLITE_OK;
    }
#ifndef NDEBUG
    /* The pager calls this method to signal that it has done
    ** a rollback and that the database is therefore unchanged and
    ** it hence it is OK for the transaction change counter to be
    ** unchanged.
    */

Changes to src/os_win.c.

1107
1108
1109
1110
1111
1112
1113





1114
1115
1116
1117
1118
1119
1120
    case SQLITE_FCNTL_LOCKSTATE: {
      *(int*)pArg = ((winFile*)id)->locktype;
      return SQLITE_OK;
    }
    case SQLITE_LAST_ERRNO: {
      *(int*)pArg = (int)((winFile*)id)->lastErrno;
      return SQLITE_OK;





    }
  }
  return SQLITE_ERROR;
}

/*
** Return the sector size in bytes of the underlying block device for







>
>
>
>
>







1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
    case SQLITE_FCNTL_LOCKSTATE: {
      *(int*)pArg = ((winFile*)id)->locktype;
      return SQLITE_OK;
    }
    case SQLITE_LAST_ERRNO: {
      *(int*)pArg = (int)((winFile*)id)->lastErrno;
      return SQLITE_OK;
    }
    case SQLITE_FCNTL_SIZE_HINT: {
      sqlite3_int64 sz = *(sqlite3_int64*)pArg;
      winTruncate(id, sz);
      return SQLITE_OK;
    }
  }
  return SQLITE_ERROR;
}

/*
** Return the sector size in bytes of the underlying block device for

Changes to src/pager.c.

2015
2016
2017
2018
2019
2020
2021



2022
2023
2024
2025
2026
2027
2028
....
2861
2862
2863
2864
2865
2866
2867











2868
2869
2870
2871
2872
2873
2874
....
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
  pPager->changeCountDone = pPager->tempFile;

  if( rc==SQLITE_OK ){
    zMaster = pPager->pTmpSpace;
    rc = readMasterJournal(pPager->jfd, zMaster, pPager->pVfs->mxPathname+1);
    testcase( rc!=SQLITE_OK );
  }



  if( rc==SQLITE_OK ){
    rc = pager_end_transaction(pPager, zMaster[0]!='\0');
    testcase( rc!=SQLITE_OK );
  }
  if( rc==SQLITE_OK && zMaster[0] && res ){
    /* If there was a master journal and this routine will return success,
    ** see if it is possible to delete the master journal.
................................................................................
  ** is not possible for rc to be other than SQLITE_OK if this branch
  ** is taken, as pager_wait_on_lock() is a no-op for temp-files.
  */
  if( !isOpen(pPager->fd) ){
    assert( pPager->tempFile && rc==SQLITE_OK );
    rc = pagerOpentemp(pPager, pPager->fd, pPager->vfsFlags);
  }












  while( rc==SQLITE_OK && pList ){
    Pgno pgno = pList->pgno;

    /* If there are dirty pages in the page cache with page numbers greater
    ** than Pager.dbSize, this means sqlite3PagerTruncateImage() was called to
    ** make the file smaller (presumably by auto-vacuum code). Do not write
................................................................................
          PgHdr *pPage;             /* Page to journal */
          rc = sqlite3PagerGet(pPager, i, &pPage);
          if( rc!=SQLITE_OK ) goto commit_phase_one_exit;
          rc = sqlite3PagerWrite(pPage);
          sqlite3PagerUnref(pPage);
          if( rc!=SQLITE_OK ) goto commit_phase_one_exit;
        }
      } 
      pPager->dbSize = dbSize;
    }
#endif

    /* Write the master journal name into the journal file. If a master 
    ** journal file name has already been written to the journal file, 
    ** or if zMaster is NULL (no master journal), then this call is a no-op.







>
>
>







 







>
>
>
>
>
>
>
>
>
>
>







 







|







2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
....
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
....
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
  pPager->changeCountDone = pPager->tempFile;

  if( rc==SQLITE_OK ){
    zMaster = pPager->pTmpSpace;
    rc = readMasterJournal(pPager->jfd, zMaster, pPager->pVfs->mxPathname+1);
    testcase( rc!=SQLITE_OK );
  }
  if( rc==SQLITE_OK && pPager->noSync==0 && pPager->state>=PAGER_EXCLUSIVE ){
    rc = sqlite3OsSync(pPager->fd, pPager->sync_flags);
  }
  if( rc==SQLITE_OK ){
    rc = pager_end_transaction(pPager, zMaster[0]!='\0');
    testcase( rc!=SQLITE_OK );
  }
  if( rc==SQLITE_OK && zMaster[0] && res ){
    /* If there was a master journal and this routine will return success,
    ** see if it is possible to delete the master journal.
................................................................................
  ** is not possible for rc to be other than SQLITE_OK if this branch
  ** is taken, as pager_wait_on_lock() is a no-op for temp-files.
  */
  if( !isOpen(pPager->fd) ){
    assert( pPager->tempFile && rc==SQLITE_OK );
    rc = pagerOpentemp(pPager, pPager->fd, pPager->vfsFlags);
  }

  /* Before the first write, give the VFS a hint of what the final
  ** file size will be.
  */
  if( rc==SQLITE_OK
   && pPager->dbSize>(pPager->dbFileSize+1)
   && isOpen(pPager->fd)
  ){
    sqlite3_int64 szFile = pPager->pageSize * (sqlite3_int64)pPager->dbSize;
    sqlite3OsFileControl(pPager->fd, SQLITE_FCNTL_SIZE_HINT, &szFile);
  }

  while( rc==SQLITE_OK && pList ){
    Pgno pgno = pList->pgno;

    /* If there are dirty pages in the page cache with page numbers greater
    ** than Pager.dbSize, this means sqlite3PagerTruncateImage() was called to
    ** make the file smaller (presumably by auto-vacuum code). Do not write
................................................................................
          PgHdr *pPage;             /* Page to journal */
          rc = sqlite3PagerGet(pPager, i, &pPage);
          if( rc!=SQLITE_OK ) goto commit_phase_one_exit;
          rc = sqlite3PagerWrite(pPage);
          sqlite3PagerUnref(pPage);
          if( rc!=SQLITE_OK ) goto commit_phase_one_exit;
        }
      }
      pPager->dbSize = dbSize;
    }
#endif

    /* Write the master journal name into the journal file. If a master 
    ** journal file name has already been written to the journal file, 
    ** or if zMaster is NULL (no master journal), then this call is a no-op.

Changes to src/sqlite.h.in.

666
667
668
669
670
671
672







673
674
675
676
677

678
679
680
681
682
683
684
** The [SQLITE_FCNTL_LOCKSTATE] opcode is used for debugging.  This
** opcode causes the xFileControl method to write the current state of
** the lock (one of [SQLITE_LOCK_NONE], [SQLITE_LOCK_SHARED],
** [SQLITE_LOCK_RESERVED], [SQLITE_LOCK_PENDING], or [SQLITE_LOCK_EXCLUSIVE])
** into an integer that the pArg argument points to. This capability
** is used during testing and only needs to be supported when SQLITE_TEST
** is defined.







*/
#define SQLITE_FCNTL_LOCKSTATE        1
#define SQLITE_GET_LOCKPROXYFILE      2
#define SQLITE_SET_LOCKPROXYFILE      3
#define SQLITE_LAST_ERRNO             4


/*
** CAPI3REF: Mutex Handle
**
** The mutex module within SQLite defines [sqlite3_mutex] to be an
** abstract type for a mutex object.  The SQLite core never looks
** at the internal representation of an [sqlite3_mutex].  It only







>
>
>
>
>
>
>





>







666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
** The [SQLITE_FCNTL_LOCKSTATE] opcode is used for debugging.  This
** opcode causes the xFileControl method to write the current state of
** the lock (one of [SQLITE_LOCK_NONE], [SQLITE_LOCK_SHARED],
** [SQLITE_LOCK_RESERVED], [SQLITE_LOCK_PENDING], or [SQLITE_LOCK_EXCLUSIVE])
** into an integer that the pArg argument points to. This capability
** is used during testing and only needs to be supported when SQLITE_TEST
** is defined.
**
** The [SQLITE_FCNTL_SIZE_HINT] opcode is used by SQLite to give the VFS
** layer a hint of how large the database file will grow to be during the
** current transaction.  This hint is not guaranteed to be accurate but it
** is often close.  The underlying VFS might choose to preallocate database
** file space based on this hint in order to help writes to the database
** file run faster.
*/
#define SQLITE_FCNTL_LOCKSTATE        1
#define SQLITE_GET_LOCKPROXYFILE      2
#define SQLITE_SET_LOCKPROXYFILE      3
#define SQLITE_LAST_ERRNO             4
#define SQLITE_FCNTL_SIZE_HINT        5

/*
** CAPI3REF: Mutex Handle
**
** The mutex module within SQLite defines [sqlite3_mutex] to be an
** abstract type for a mutex object.  The SQLite core never looks
** at the internal representation of an [sqlite3_mutex].  It only

Changes to test/corruptE.test.

16
17
18
19
20
21
22







23
24
25
26
27
28
29
#
# $Id: corruptE.test,v 1.14 2009/07/11 06:55:34 danielk1977 Exp $

catch {file delete -force test.db test.db-journal test.bu}

set testdir [file dirname $argv0]
source $testdir/tester.tcl








# Construct a compact, dense database for testing.
#
do_test corruptE-1.1 {
  execsql {
    PRAGMA auto_vacuum = 0;
    PRAGMA legacy_file_format=1;







>
>
>
>
>
>
>







16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#
# $Id: corruptE.test,v 1.14 2009/07/11 06:55:34 danielk1977 Exp $

catch {file delete -force test.db test.db-journal test.bu}

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Do not run the tests in this file if ENABLE_OVERSIZE_CELL_CHECK is on.
#
ifcapable oversize_cell_check {
  finish_test
  return
}

# Construct a compact, dense database for testing.
#
do_test corruptE-1.1 {
  execsql {
    PRAGMA auto_vacuum = 0;
    PRAGMA legacy_file_format=1;

Changes to test/crash8.test.

335
336
337
338
339
340
341
342


























































343
  } {def}

  do_test crash8-4.10 {
    file delete $zMasterJournal
    execsql { SELECT b FROM main.ab WHERE a = 0 }
  } {jkl}
}



























































finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
  } {def}

  do_test crash8-4.10 {
    file delete $zMasterJournal
    execsql { SELECT b FROM main.ab WHERE a = 0 }
  } {jkl}
}

for {set i 1} {$i < 10} {incr i} {
  catch { db close }
  file delete -force test.db test.db-journal
  sqlite3 db test.db
  do_test crash8-5.$i.1 {
    execsql {
      CREATE TABLE t1(x PRIMARY KEY);
      INSERT INTO t1 VALUES(randomblob(900));
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;          /* 64 rows */
    }
    crashsql -file test.db -delay [expr ($::i%2) + 1] {
      PRAGMA cache_size = 10;
      BEGIN;
        UPDATE t1 SET x = randomblob(900);
      ROLLBACK;
      INSERT INTO t1 VALUES(randomblob(900));
    }
    execsql { PRAGMA integrity_check }
  } {ok}
  
  catch { db close }
  file delete -force test.db test.db-journal
  sqlite3 db test.db
  do_test crash8-5.$i.2 {
    execsql {
      PRAGMA cache_size = 10;
      CREATE TABLE t1(x PRIMARY KEY);
      INSERT INTO t1 VALUES(randomblob(900));
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;
      INSERT INTO t1 SELECT randomblob(900) FROM t1;          /* 64 rows */
      BEGIN;
        UPDATE t1 SET x = randomblob(900);
    }
    file delete -force testX.db testX.db-journal
    copy_file test.db testX.db
    copy_file test.db-journal testX.db-journal
    db close

    crashsql -file test.db -delay [expr ($::i%2) + 1] {
      SELECT * FROM sqlite_master;
      INSERT INTO t1 VALUES(randomblob(900));
    }

    sqlite3 db2 testX.db
    execsql { PRAGMA integrity_check } db2
  } {ok}
}
catch {db2 close}

finish_test

Changes to test/fts3ac.test.

1193
1194
1195
1196
1197
1198
1199
1200


















1201
  execsql {
    SELECT snippet(email) FROM email
     WHERE email MATCH 'enron OR com questar'
  }
} {{matt.smith@<b>enron</b>.<b>com</b><b>...</b>31 Keystone Receipts
15 <b>Questar</b> Pipeline
40 Rockies<b>...</b>}}



















finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
  execsql {
    SELECT snippet(email) FROM email
     WHERE email MATCH 'enron OR com questar'
  }
} {{matt.smith@<b>enron</b>.<b>com</b><b>...</b>31 Keystone Receipts
15 <b>Questar</b> Pipeline
40 Rockies<b>...</b>}}

#-------------------------------------------------------------------------
# Test a problem reported on the mailing list.
#
do_test fts3ac-6.1 {
  execsql {
    CREATE VIRTUAL TABLE ft USING fts3(one, two);
    INSERT INTO ft VALUES('', 'foo');
    INSERT INTO ft VALUES('foo', 'foo');
    SELECT offsets(ft) FROM ft WHERE ft MATCH 'foo';
  }
} {{1 0 0 3} {0 0 0 3 1 0 0 3}}
do_test fts3ac-6.2 {
  execsql {
    DELETE FROM ft WHERE one = 'foo';
    SELECT offsets(ft) FROM ft WHERE ft MATCH 'foo';
  }
} {{1 0 0 3}}

finish_test

Changes to test/fts3ag.test.

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
do_test fts3ag-1.9 {
  execsql {SELECT rowid FROM t1 WHERE t1 MATCH 'this something'}
} {}

# No support for all-except queries.
do_test fts3ag-1.10 {
  catchsql {SELECT rowid FROM t1 WHERE t1 MATCH '-this -something'}
} {1 {SQL logic error or missing database}}

# Test that docListOrMerge() correctly handles reaching the end of one
# doclist before it reaches the end of the other.
do_test fts3ag-1.11 {
breakpoint
  execsql {SELECT rowid FROM t1 WHERE t1 MATCH 'this OR also'}
} {1 2}







|







69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
do_test fts3ag-1.9 {
  execsql {SELECT rowid FROM t1 WHERE t1 MATCH 'this something'}
} {}

# No support for all-except queries.
do_test fts3ag-1.10 {
  catchsql {SELECT rowid FROM t1 WHERE t1 MATCH '-this -something'}
} {1 {malformed MATCH expression: [-this -something]}}

# Test that docListOrMerge() correctly handles reaching the end of one
# doclist before it reaches the end of the other.
do_test fts3ag-1.11 {
breakpoint
  execsql {SELECT rowid FROM t1 WHERE t1 MATCH 'this OR also'}
} {1 2}

Changes to test/fts3expr.test.

332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
do_test fts3expr-4.1 {
  execsql { CREATE VIRTUAL TABLE t1 USING fts3(a, b, c) }
} {}

# Mismatched parenthesis:
do_test fts3expr-4.2.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example AND (hello OR world))' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.2.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example AND (hello OR world' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.2.3 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(hello' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.2.4 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.2.5 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH ')' }
} {1 {SQL logic error or missing database}}

do_test fts3expr-4.2.6 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example (hello world' }
} {1 {SQL logic error or missing database}}

# Unterminated quotation marks:
do_test fts3expr-4.3.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example OR "hello world' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.3.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example OR hello world"' }
} {1 {SQL logic error or missing database}}

# Binary operators without the required operands.
do_test fts3expr-4.4.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'OR hello world' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.4.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'hello world OR' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.4.3 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one (hello world OR) two' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.4.4 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one (OR hello world) two' }
} {1 {SQL logic error or missing database}}

# NEAR operators with something other than phrases as arguments.
do_test fts3expr-4.5.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(hello OR world) NEAR one' }
} {1 {SQL logic error or missing database}}
do_test fts3expr-4.5.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one NEAR (hello OR world)' }
} {1 {SQL logic error or missing database}}

#------------------------------------------------------------------------
# The following OOM tests are designed to cover cases in fts3_expr.c.
# 
source $testdir/malloc_common.tcl
do_malloc_test fts3expr-malloc-1 -sqlbody {
  SELECT fts3_exprtest('simple', 'a b c "d e f"', 'a', 'b', 'c')







|


|


|


|


|



|




|


|




|


|


|


|




|


|







332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
do_test fts3expr-4.1 {
  execsql { CREATE VIRTUAL TABLE t1 USING fts3(a, b, c) }
} {}

# Mismatched parenthesis:
do_test fts3expr-4.2.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example AND (hello OR world))' }
} {1 {malformed MATCH expression: [example AND (hello OR world))]}}
do_test fts3expr-4.2.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example AND (hello OR world' }
} {1 {malformed MATCH expression: [example AND (hello OR world]}}
do_test fts3expr-4.2.3 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(hello' }
} {1 {malformed MATCH expression: [(hello]}}
do_test fts3expr-4.2.4 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(' }
} {1 {malformed MATCH expression: [(]}}
do_test fts3expr-4.2.5 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH ')' }
} {1 {malformed MATCH expression: [)]}}

do_test fts3expr-4.2.6 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example (hello world' }
} {1 {malformed MATCH expression: [example (hello world]}}

# Unterminated quotation marks:
do_test fts3expr-4.3.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example OR "hello world' }
} {1 {malformed MATCH expression: [example OR "hello world]}}
do_test fts3expr-4.3.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'example OR hello world"' }
} {1 {malformed MATCH expression: [example OR hello world"]}}

# Binary operators without the required operands.
do_test fts3expr-4.4.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'OR hello world' }
} {1 {malformed MATCH expression: [OR hello world]}}
do_test fts3expr-4.4.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'hello world OR' }
} {1 {malformed MATCH expression: [hello world OR]}}
do_test fts3expr-4.4.3 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one (hello world OR) two' }
} {1 {malformed MATCH expression: [one (hello world OR) two]}}
do_test fts3expr-4.4.4 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one (OR hello world) two' }
} {1 {malformed MATCH expression: [one (OR hello world) two]}}

# NEAR operators with something other than phrases as arguments.
do_test fts3expr-4.5.1 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH '(hello OR world) NEAR one' }
} {1 {malformed MATCH expression: [(hello OR world) NEAR one]}}
do_test fts3expr-4.5.2 {
  catchsql { SELECT * FROM t1 WHERE t1 MATCH 'one NEAR (hello OR world)' }
} {1 {malformed MATCH expression: [one NEAR (hello OR world)]}}

#------------------------------------------------------------------------
# The following OOM tests are designed to cover cases in fts3_expr.c.
# 
source $testdir/malloc_common.tcl
do_malloc_test fts3expr-malloc-1 -sqlbody {
  SELECT fts3_exprtest('simple', 'a b c "d e f"', 'a', 'b', 'c')

Added test/tkt-5e10420e8d.test.





















































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 2010 August 23
#
# 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.
#
#***********************************************************************
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

do_test tkt-5e10420e8d.1 {
  db eval {
    PRAGMA page_size = 1024;
    PRAGMA auto_vacuum = incremental;
  
    CREATE TABLE t1(x);
    CREATE TABLE t2(x);
    CREATE TABLE t3(x);
  }
} {}

do_test tkt-5e10420e8d.2 {
  db eval {
    INSERT INTO t3 VALUES(randomblob(500 + 1024*248));
    INSERT INTO t1 VALUES(randomblob(1500));
    INSERT INTO t2 VALUES(randomblob(500 + 1024*248));
  
    DELETE FROM t3;
    DELETE FROM t2;
    DELETE FROM t1;
  }
} {}

do_test tkt-5e10420e8d.3 {
  db eval {
    PRAGMA incremental_vacuum(248)
  }
} {}

do_test tkt-5e10420e8d.4 {
  db eval {
    PRAGMA incremental_vacuum(1)
  }
} {}

db close
sqlite3 db test.db

do_test tkt-5e10420e8d.5 {
  db eval {PRAGMA integrity_check;}
} {ok}

finish_test

Changes to tool/mksqlite3c.tcl.

207
208
209
210
211
212
213

214
215
216
217
218
219
220
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
# used subroutines first in order to help the compiler find
# inlining opportunities.
#
foreach file {
   sqliteInt.h

   global.c

   status.c
   date.c
   os.c

   fault.c
   mem0.c
   mem1.c
................................................................................
   expr.c
   alter.c
   analyze.c
   attach.c
   auth.c
   build.c
   callback.c
   ctime.c
   delete.c
   func.c
   fkey.c
   insert.c
   legacy.c
   loadext.c
   pragma.c







>







 







<







207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
...
263
264
265
266
267
268
269

270
271
272
273
274
275
276
# used subroutines first in order to help the compiler find
# inlining opportunities.
#
foreach file {
   sqliteInt.h

   global.c
   ctime.c
   status.c
   date.c
   os.c

   fault.c
   mem0.c
   mem1.c
................................................................................
   expr.c
   alter.c
   analyze.c
   attach.c
   auth.c
   build.c
   callback.c

   delete.c
   func.c
   fkey.c
   insert.c
   legacy.c
   loadext.c
   pragma.c

Changes to tool/mksqlite3h.tcl.

61
62
63
64
65
66
67
68
69

70
71
72
73
74





75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

close $in

# Set up patterns for recognizing API declarations.
#
set varpattern {^[a-zA-Z][a-zA-Z_0-9 *]+sqlite3_[_a-zA-Z0-9]+(\[|;| =)}
set declpattern {^ *[a-zA-Z][a-zA-Z_0-9 ]+ \**sqlite3_[_a-zA-Z0-9]+\(}

# Process the  src/sqlite.h.in  file.
#

set in [open $TOP/src/sqlite.h.in]
while {![eof $in]} {

  set line [gets $in]






  regsub -- --VERS--           $line $zVersion line
  regsub -- --VERSION-NUMBER-- $line $nVersion line
  regsub -- --SOURCE-ID--      $line "$zDate $zUuid" line

  if {[regexp {define SQLITE_EXTERN extern} $line]} {
    puts $line
    puts [gets $in]
    puts ""
    puts "#ifndef SQLITE_API"
    puts "# define SQLITE_API"
    puts "#endif"
    set line ""
  }

  if {([regexp $varpattern $line] && ![regexp {^ *typedef} $line])
   || ([regexp $declpattern $line])
  } {
    set line "SQLITE_API $line"
  }
  puts $line
}
close $in








|

>
|
|
|
|

>
>
>
>
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
close $in

# Set up patterns for recognizing API declarations.
#
set varpattern {^[a-zA-Z][a-zA-Z_0-9 *]+sqlite3_[_a-zA-Z0-9]+(\[|;| =)}
set declpattern {^ *[a-zA-Z][a-zA-Z_0-9 ]+ \**sqlite3_[_a-zA-Z0-9]+\(}

# Process the src/sqlite.h.in ext/rtree/sqlite3rtree.h files.
#
foreach file [list $TOP/src/sqlite.h.in $TOP/ext/rtree/sqlite3rtree.h] {
  set in [open $file]
  while {![eof $in]} {
  
    set line [gets $in]

    # File sqlite3rtree.h contains a line "#include <sqlite3.h>". Omit this
    # line when copying sqlite3rtree.h into sqlite3.h.
    #
    if {[string match {*#include*<sqlite3.h>*} $line]} continue
  
    regsub -- --VERS--           $line $zVersion line
    regsub -- --VERSION-NUMBER-- $line $nVersion line
    regsub -- --SOURCE-ID--      $line "$zDate $zUuid" line
  
    if {[regexp {define SQLITE_EXTERN extern} $line]} {
      puts $line
      puts [gets $in]
      puts ""
      puts "#ifndef SQLITE_API"
      puts "# define SQLITE_API"
      puts "#endif"
      set line ""
    }
  
    if {([regexp $varpattern $line] && ![regexp {^ *typedef} $line])
     || ([regexp $declpattern $line])
    } {
      set line "SQLITE_API $line"
    }
    puts $line
  }
  close $in
}