SQLite

Check-in [803156cba8]
Login

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

Overview
Comment:Merge latest trunk changes into this branch.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | sqlar-shell-support
Files: files | file ages | folders
SHA3-256: 803156cba8b056a1cb8d1bb186a57454afe72341abe7de1dfe529234c3415cd2
User & Date: dan 2017-12-14 13:55:01.572
Context
2017-12-14
15:40
Improve error and usage messages output by the shell ".ar" command. (check-in: b9d2d5d972 user: dan tags: sqlar-shell-support)
13:55
Merge latest trunk changes into this branch. (check-in: 803156cba8 user: dan tags: sqlar-shell-support)
2017-12-13
23:47
In valueFromExpr() only generate a OOM fault if there have been no prior faults. (check-in: 3765aaf712 user: drh tags: trunk)
20:17
Add the shell tool ".ar --update" command. (check-in: 825e3c037b user: dan tags: sqlar-shell-support)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to Makefile.msc.
2157
2158
2159
2160
2161
2162
2163


















2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174




2175
2176
2177
2178
2179
2180
2181
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203







+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+











+
+
+
+







   fts5parse.c fts5parse.h \
   $(TOP)\ext\fts5\fts5_storage.c \
   $(TOP)\ext\fts5\fts5_tokenize.c \
   $(TOP)\ext\fts5\fts5_unicode2.c \
   $(TOP)\ext\fts5\fts5_varint.c \
   $(TOP)\ext\fts5\fts5_vocab.c

LSM1_SRC = \
   $(TOP)\ext\lsm1\lsm.h \
   $(TOP)\ext\lsm1\lsmInt.h \
   $(TOP)\ext\lsm1\lsm_ckpt.c \
   $(TOP)\ext\lsm1\lsm_file.c \
   $(TOP)\ext\lsm1\lsm_log.c \
   $(TOP)\ext\lsm1\lsm_main.c \
   $(TOP)\ext\lsm1\lsm_mem.c \
   $(TOP)\ext\lsm1\lsm_mutex.c \
   $(TOP)\ext\lsm1\lsm_shared.c \
   $(TOP)\ext\lsm1\lsm_sorted.c \
   $(TOP)\ext\lsm1\lsm_str.c \
   $(TOP)\ext\lsm1\lsm_tree.c \
   $(TOP)\ext\lsm1\lsm_unix.c \
   $(TOP)\ext\lsm1\lsm_varint.c \
   $(TOP)\ext\lsm1\lsm_vtab.c \
   $(TOP)\ext\lsm1\lsm_win32.c

fts5parse.c:	$(TOP)\ext\fts5\fts5parse.y lemon.exe
	copy $(TOP)\ext\fts5\fts5parse.y .
	del /Q fts5parse.h 2>NUL
	.\lemon.exe $(REQ_FEATURE_FLAGS) $(OPT_FEATURE_FLAGS) $(EXT_FEATURE_FLAGS) $(OPTS) fts5parse.y

fts5parse.h:	fts5parse.c

fts5.c:	$(FTS5_SRC)
	$(TCLSH_CMD) $(TOP)\ext\fts5\tool\mkfts5c.tcl
	copy $(TOP)\ext\fts5\fts5.h .

lsm1.c:	$(LSM1_SRC)
	$(TCLSH_CMD) $(TOP)\ext\lsm1\tool\mklsm1c.tcl
	copy $(TOP)\ext\lsm1\lsm.h .

fts5.lo:	fts5.c $(HDR) $(EXTHDR)
	$(LTCOMPILE) $(CORE_COMPILE_OPTS) $(NO_WARN) -DSQLITE_CORE -c fts5.c

fts5_ext.lo:	fts5.c $(HDR) $(EXTHDR)
	$(LTCOMPILE) $(NO_WARN) -c fts5.c

fts5.dll:	fts5_ext.lo
2397
2398
2399
2400
2401
2402
2403

2404
2419
2420
2421
2422
2423
2424
2425
2426
2427







+

	del /Q sqlite3.c sqlite3-*.c 2>NUL
	del /Q sqlite3rc.h 2>NUL
	del /Q shell.c sqlite3ext.h sqlite3session.h 2>NUL
	del /Q sqlite3_analyzer.exe sqlite3_analyzer.c 2>NUL
	del /Q sqlite-*-output.vsix 2>NUL
	del /Q fuzzershell.exe fuzzcheck.exe sqldiff.exe dbhash.exe 2>NUL
	del /Q fts5.* fts5parse.* 2>NUL
	del /Q lsm.h lsm1.c 2>NUL
# <</mark>>
Changes to README.md.
203
204
205
206
207
208
209
210
211


212
213
214
215
216
217
218
203
204
205
206
207
208
209


210
211
212
213
214
215
216
217
218







-
-
+
+







tool/mksqlite3c.tcl script is run to copy them all together in just the
right order while resolving internal "#include" references.

The amalgamation source file is more than 200K lines long.  Some symbolic
debuggers (most notably MSVC) are unable to deal with files longer than 64K
lines.  To work around this, a separate Tcl script, tool/split-sqlite3c.tcl,
can be run on the amalgamation to break it up into a single small C file
called **sqlite3-all.c** that does #include on about five other files
named **sqlite3-1.c**, **sqlite3-2.c**, ..., **sqlite3-5.c**.  In this way,
called **sqlite3-all.c** that does #include on about seven other files
named **sqlite3-1.c**, **sqlite3-2.c**, ..., **sqlite3-7.c**.  In this way,
all of the source code is contained within a single translation unit so
that the compiler can do extra cross-procedure optimization, but no
individual source file exceeds 32K lines in length.

## How It All Fits Together

SQLite is modular in design.
233
234
235
236
237
238
239
240


241
242
243
244
245
246
247
248
249
250
251

252

253
254
255
256
257
258



259
260
261


262
263
264
265
266
267

268
269


270
271
272
273










274
275
276
277
278
279
280
281
282
283
284
233
234
235
236
237
238
239

240
241
242
243
244
245
246
247
248
249
250
251
252
253

254
255
256
257
258
259

260
261
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







-
+
+











+
-
+





-
+
+
+


-
+
+





-
+

-
+
+




+
+
+
+
+
+
+
+
+
+











Key files:

  *  **sqlite.h.in** - This file defines the public interface to the SQLite
     library.  Readers will need to be familiar with this interface before
     trying to understand how the library works internally.

  *  **sqliteInt.h** - this header file defines many of the data objects
     used internally by SQLite.
     used internally by SQLite.  In addition to "sqliteInt.h", some
     subsystems have their own header files.

  *  **parse.y** - This file describes the LALR(1) grammar that SQLite uses
     to parse SQL statements, and the actions that are taken at each step
     in the parsing process.

  *  **vdbe.c** - This file implements the virtual machine that runs
     prepared statements.  There are various helper files whose names
     begin with "vdbe".  The VDBE has access to the vdbeInt.h header file
     which defines internal data objects.  The rest of SQLite interacts
     with the VDBE through an interface defined by vdbe.h.

  *  **where.c** - This file (together with its helper files named
  *  **where.c** - This file analyzes the WHERE clause and generates
     by "where*.c") analyzes the WHERE clause and generates
     virtual machine code to run queries efficiently.  This file is
     sometimes called the "query optimizer".  It has its own private
     header file, whereInt.h, that defines data objects used internally.

  *  **btree.c** - This file contains the implementation of the B-Tree
     storage engine used by SQLite.
     storage engine used by SQLite.  The interface to the rest of the system
     is defined by "btree.h".  The "btreeInt.h" header defines objects
     used internally by btree.c and not published to the rest of the system.

  *  **pager.c** - This file contains the "pager" implementation, the
     module that implements transactions.
     module that implements transactions.  The "pager.h" header file
     defines the interface between pager.c and the rest of the system.

  *  **os_unix.c** and **os_win.c** - These two files implement the interface
     between SQLite and the underlying operating system using the run-time
     pluggable VFS interface.

  *  **shell.c** - This file is not part of the core SQLite library.  This
  *  **shell.c.in** - This file is not part of the core SQLite library.  This
     is the file that, when linked against sqlite3.a, generates the
     "sqlite3.exe" command-line shell.
     "sqlite3.exe" command-line shell.  The "shell.c.in" file is transformed
     into "shell.c" as part of the build process.

  *  **tclsqlite.c** - This file implements the Tcl bindings for SQLite.  It
     is not part of the core SQLite library.  But as most of the tests in this
     repository are written in Tcl, the Tcl language bindings are important.

  *  **test*.c** - Files in the src/ folder that begin with "test" go into
     building the "testfixture.exe" program.  The testfixture.exe program is
     an enhanced TCL shell.  The testfixture.exe program runs scripts in the
     test/ folder to validate the core SQLite code.  The testfixture program
     (and some other test programs too) is build and run when you type
     "make test".

  *  **ext/misc/json1.c** - This file implements the various JSON functions
     that are build into SQLite.

There are many other source files.  Each has a succinct header comment that
describes its purpose and role within the larger system.


## Contacts

The main SQLite webpage is [http://www.sqlite.org/](http://www.sqlite.org/)
with geographically distributed backups at
[http://www2.sqlite.org/](http://www2.sqlite.org) and
[http://www3.sqlite.org/](http://www3.sqlite.org).
Changes to ext/fts5/fts5_index.c.
4905
4906
4907
4908
4909
4910
4911






4912

4913
4914
4915
4916
4917
4918
4919
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917

4918
4919
4920
4921
4922
4923
4924
4925







+
+
+
+
+
+
-
+







  if( p2->n ){
    i64 iLastRowid = 0;
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out = {0, 0, 0};
    Fts5Buffer tmp = {0, 0, 0};

    /* The maximum size of the output is equal to the sum of the two 
    ** input sizes + 1 varint (9 bytes). The extra varint is because if the
    ** first rowid in one input is a large negative number, and the first in
    ** the other a non-negative number, the delta for the non-negative
    ** number will be larger on disk than the literal integer value
    ** was.  */
    if( sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n) ) return;
    if( sqlite3Fts5BufferSize(&p->rc, &out, p1->n + p2->n + 9) ) return;
    fts5DoclistIterInit(p1, &i1);
    fts5DoclistIterInit(p2, &i2);

    while( 1 ){
      if( i1.iRowid<i2.iRowid ){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
4999
5000
5001
5002
5003
5004
5005

5006
5007
5008
5009
5010
5011
5012
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019







+







      fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
      fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.aEof - i1.aPoslist);
    }
    else if( i2.aPoslist ){
      fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
      fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.aEof - i2.aPoslist);
    }
    assert( out.n<=(p1->n+p2->n+9) );

    fts5BufferSet(&p->rc, p1, out.n, out.p);
    fts5BufferFree(&tmp);
    fts5BufferFree(&out);
  }
}

Changes to ext/fts5/test/fts5query.test.
60
61
62
63
64
65
66
67

68
69
70
71
72
73
74
75
76
77
78
79










80
81
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
85
86
87
88
89
90
91







-
+












+
+
+
+
+
+
+
+
+
+


    foreach x [list bbb ddd fff hhh jjj lll nnn ppp rrr ttt] {
      set doc [string repeat "$x " 30]
      execsql { INSERT INTO t1 VALUES($doc) }
    }
    execsql COMMIT
  } {}

  do_execsql_test 1.$tn.2 {
  do_execsql_test 2.$tn.2 {
    INSERT INTO t1(t1) VALUES('integrity-check');
  }

  set ret 1
  foreach x [list a c e g i k m o q s u] {
    do_execsql_test 2.$tn.3.$ret {
      SELECT rowid FROM t1 WHERE t1 MATCH $x || '*';
    } {}
    incr ret
  }
}

reset_db
do_execsql_test 3.0 {
  CREATE VIRTUAL TABLE x1 USING fts5(a);
  INSERT INTO x1(rowid, a) VALUES(-1000000000000, 'toyota');
  INSERT INTO x1(rowid, a) VALUES(1, 'tarago');
}
do_execsql_test 3.1 {
  SELECT rowid FROM x1('t*');
} {-1000000000000 1}


finish_test
Changes to ext/icu/icu.c.
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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76







-
+
+
+
















+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+







**
**   * Integration of ICU and SQLite collation sequences.
**
**   * An implementation of the LIKE operator that uses ICU to 
**     provide case-independent matching.
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_ICU)
#if !defined(SQLITE_CORE)                  \
 || defined(SQLITE_ENABLE_ICU)             \
 || defined(SQLITE_ENABLE_ICU_COLLATIONS)

/* Include ICU headers */
#include <unicode/utypes.h>
#include <unicode/uregex.h>
#include <unicode/ustring.h>
#include <unicode/ucol.h>

#include <assert.h>

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

/*
** This function is called when an ICU function called from within
** the implementation of an SQL scalar function returns an error.
**
** The scalar function context passed as the first argument is 
** loaded with an error message based on the following two args.
*/
static void icuFunctionError(
  sqlite3_context *pCtx,       /* SQLite scalar function context */
  const char *zName,           /* Name of ICU function that failed */
  UErrorCode e                 /* Error code returned by ICU function */
){
  char zBuf[128];
  sqlite3_snprintf(128, zBuf, "ICU error: %s(): %s", zName, u_errorName(e));
  zBuf[127] = '\0';
  sqlite3_result_error(pCtx, zBuf, -1);
}

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

/*
** Maximum length (in bytes) of the pattern in a LIKE or GLOB
** operator.
*/
#ifndef SQLITE_MAX_LIKE_PATTERN_LENGTH
# define SQLITE_MAX_LIKE_PATTERN_LENGTH 50000
#endif
220
221
222
223
224
225
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
242
243
244
245
246
247
248


















249
250
251
252
253
254
255







-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-







  }

  if( zA && zB ){
    sqlite3_result_int(context, icuLikeCompare(zA, zB, uEsc));
  }
}

/*
** This function is called when an ICU function called from within
** the implementation of an SQL scalar function returns an error.
**
** The scalar function context passed as the first argument is 
** loaded with an error message based on the following two args.
*/
static void icuFunctionError(
  sqlite3_context *pCtx,       /* SQLite scalar function context */
  const char *zName,           /* Name of ICU function that failed */
  UErrorCode e                 /* Error code returned by ICU function */
){
  char zBuf[128];
  sqlite3_snprintf(128, zBuf, "ICU error: %s(): %s", zName, u_errorName(e));
  zBuf[127] = '\0';
  sqlite3_result_error(pCtx, zBuf, -1);
}

/*
** Function to delete compiled regexp objects. Registered as
** a destructor function with sqlite3_set_auxdata().
*/
static void icuRegexpDelete(void *p){
  URegularExpression *pExpr = (URegularExpression *)p;
  uregex_close(pExpr);
403
404
405
406
407
408
409


410
411
412
413
414
415
416
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422







+
+







      icuFunctionError(p, bToUpper ? "u_strToUpper" : "u_strToLower", status);
    }
    return;
  }
  assert( 0 );     /* Unreachable */
}

#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_ICU) */

/*
** Collation sequence destructor function. The pCtx argument points to
** a UCollator structure previously allocated using ucol_open().
*/
static void icuCollationDel(void *pCtx){
  UCollator *p = (UCollator *)pCtx;
  ucol_close(p);
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
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







+











+



-







    const char *zName;                        /* Function name */
    unsigned char nArg;                       /* Number of arguments */
    unsigned short enc;                       /* Optimal text encoding */
    unsigned char iContext;                   /* sqlite3_user_data() context */
    void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
  } scalars[] = {
    {"icu_load_collation",  2, SQLITE_UTF8,                1, icuLoadCollation},
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_ICU)
    {"regexp", 2, SQLITE_ANY|SQLITE_DETERMINISTIC,         0, icuRegexpFunc},
    {"lower",  1, SQLITE_UTF16|SQLITE_DETERMINISTIC,       0, icuCaseFunc16},
    {"lower",  2, SQLITE_UTF16|SQLITE_DETERMINISTIC,       0, icuCaseFunc16},
    {"upper",  1, SQLITE_UTF16|SQLITE_DETERMINISTIC,       1, icuCaseFunc16},
    {"upper",  2, SQLITE_UTF16|SQLITE_DETERMINISTIC,       1, icuCaseFunc16},
    {"lower",  1, SQLITE_UTF8|SQLITE_DETERMINISTIC,        0, icuCaseFunc16},
    {"lower",  2, SQLITE_UTF8|SQLITE_DETERMINISTIC,        0, icuCaseFunc16},
    {"upper",  1, SQLITE_UTF8|SQLITE_DETERMINISTIC,        1, icuCaseFunc16},
    {"upper",  2, SQLITE_UTF8|SQLITE_DETERMINISTIC,        1, icuCaseFunc16},
    {"like",   2, SQLITE_UTF8|SQLITE_DETERMINISTIC,        0, icuLikeFunc},
    {"like",   3, SQLITE_UTF8|SQLITE_DETERMINISTIC,        0, icuLikeFunc},
#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_ICU) */
  };
  int rc = SQLITE_OK;
  int i;

  
  for(i=0; rc==SQLITE_OK && i<(int)(sizeof(scalars)/sizeof(scalars[0])); i++){
    const struct IcuScalar *p = &scalars[i];
    rc = sqlite3_create_function(
        db, p->zName, p->nArg, p->enc, 
        p->iContext ? (void*)db : (void*)0,
        p->xFunc, 0, 0
Changes to ext/lsm1/lsmInt.h.
106
107
108
109
110
111
112
113

114
115
116
117
118
119
120
106
107
108
109
110
111
112

113
114
115
116
117
118
119
120







-
+







typedef unsigned short int u16;
typedef unsigned int u32;
typedef lsm_i64 i64;
typedef unsigned long long int u64;
#endif

/* A page number is a 64-bit integer. */
typedef i64 Pgno;
typedef i64 LsmPgno;

#ifdef LSM_DEBUG
int lsmErrorBkpt(int);
#else
# define lsmErrorBkpt(x) (x)
#endif

398
399
400
401
402
403
404
405
406
407



408
409
410
411
412
413
414
398
399
400
401
402
403
404



405
406
407
408
409
410
411
412
413
414







-
-
-
+
+
+







  void **apShm;                   /* Shared memory chunks */
  ShmHeader *pShmhdr;             /* Live shared-memory header */
  TreeHeader treehdr;             /* Local copy of tree-header */
  u32 aSnapshot[LSM_META_PAGE_SIZE / sizeof(u32)];
};

struct Segment {
  Pgno iFirst;                     /* First page of this run */
  Pgno iLastPg;                    /* Last page of this run */
  Pgno iRoot;                      /* Root page number (if any) */
  LsmPgno iFirst;                  /* First page of this run */
  LsmPgno iLastPg;                 /* Last page of this run */
  LsmPgno iRoot;                   /* Root page number (if any) */
  int nSize;                       /* Size of this run in pages */

  Redirect *pRedirect;             /* Block redirects (or NULL) */
};

/*
** iSplitTopic/pSplitKey/nSplitKey:
452
453
454
455
456
457
458
459

460
461
462
463
464
465
466
467
468

469
470
471
472
473
474
475
452
453
454
455
456
457
458

459
460
461
462
463
464
465
466
467

468
469
470
471
472
473
474
475







-
+








-
+







** access to the associated Level struct.
**
** iOutputOff:
**   The byte offset to write to next within the last page of the 
**   output segment.
*/
struct MergeInput {
  Pgno iPg;                       /* Page on which next input is stored */
  LsmPgno iPg;                    /* Page on which next input is stored */
  int iCell;                      /* Cell containing next input to merge */
};
struct Merge {
  int nInput;                     /* Number of input runs being merged */
  MergeInput *aInput;             /* Array nInput entries in size */
  MergeInput splitkey;            /* Location in file of current splitkey */
  int nSkip;                      /* Number of separators entries to skip */
  int iOutputOff;                 /* Write offset on output page */
  Pgno iCurrentPtr;               /* Current pointer value */
  LsmPgno iCurrentPtr;            /* Current pointer value */
};

/* 
** The first argument to this macro is a pointer to a Segment structure.
** Returns true if the structure instance indicates that the separators
** array is valid.
*/
575
576
577
578
579
580
581
582
583
584
585




586
587
588
589
590
591
592
575
576
577
578
579
580
581




582
583
584
585
586
587
588
589
590
591
592







-
-
-
-
+
+
+
+







  u32 iCmpId;                     /* Id of compression scheme */
  Level *pLevel;                  /* Pointer to level 0 of snapshot (or NULL) */
  i64 iId;                        /* Snapshot id */
  i64 iLogOff;                    /* Log file offset */
  Redirect redirect;              /* Block redirection array */

  /* Used by worker snapshots only */
  int nBlock;                     /* Number of blocks in database file */
  Pgno aiAppend[LSM_APPLIST_SZ];  /* Append point list */
  Freelist freelist;              /* Free block list */
  u32 nWrite;                     /* Total number of pages written to disk */
  int nBlock;                        /* Number of blocks in database file */
  LsmPgno aiAppend[LSM_APPLIST_SZ];  /* Append point list */
  Freelist freelist;                 /* Free block list */
  u32 nWrite;                        /* Total number of pages written to disk */
};
#define LSM_INITIAL_SNAPSHOT_ID 11

/*
** Functions from file "lsm_ckpt.c".
*/
int lsmCheckpointWrite(lsm_db *, u32 *);
706
707
708
709
710
711
712
713

714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730

731
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
706
707
708
709
710
711
712

713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729

730
731
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







-
+
















-
+






-
+













-
+



















-
-
+
+















-
+










-
+








int lsmFsPageSize(FileSystem *);
void lsmFsSetPageSize(FileSystem *, int);

int lsmFsFileid(lsm_db *pDb, void **ppId, int *pnId);

/* Creating, populating, gobbling and deleting sorted runs. */
void lsmFsGobble(lsm_db *, Segment *, Pgno *, int);
void lsmFsGobble(lsm_db *, Segment *, LsmPgno *, int);
int lsmFsSortedDelete(FileSystem *, Snapshot *, int, Segment *);
int lsmFsSortedFinish(FileSystem *, Segment *);
int lsmFsSortedAppend(FileSystem *, Snapshot *, Level *, int, Page **);
int lsmFsSortedPadding(FileSystem *, Snapshot *, Segment *);

/* Functions to retrieve the lsm_env pointer from a FileSystem or Page object */
lsm_env *lsmFsEnv(FileSystem *);
lsm_env *lsmPageEnv(Page *);
FileSystem *lsmPageFS(Page *);

int lsmFsSectorSize(FileSystem *);

void lsmSortedSplitkey(lsm_db *, Level *, int *);

/* Reading sorted run content. */
int lsmFsDbPageLast(FileSystem *pFS, Segment *pSeg, Page **ppPg);
int lsmFsDbPageGet(FileSystem *, Segment *, Pgno, Page **);
int lsmFsDbPageGet(FileSystem *, Segment *, LsmPgno, Page **);
int lsmFsDbPageNext(Segment *, Page *, int eDir, Page **);

u8 *lsmFsPageData(Page *, int *);
int lsmFsPageRelease(Page *);
int lsmFsPagePersist(Page *);
void lsmFsPageRef(Page *);
Pgno lsmFsPageNumber(Page *);
LsmPgno lsmFsPageNumber(Page *);

int lsmFsNRead(FileSystem *);
int lsmFsNWrite(FileSystem *);

int lsmFsMetaPageGet(FileSystem *, int, int, MetaPage **);
int lsmFsMetaPageRelease(MetaPage *);
u8 *lsmFsMetaPageData(MetaPage *, int *);

#ifdef LSM_DEBUG
int lsmFsDbPageIsLast(Segment *pSeg, Page *pPg);
int lsmFsIntegrityCheck(lsm_db *);
#endif

Pgno lsmFsRedirectPage(FileSystem *, Redirect *, Pgno);
LsmPgno lsmFsRedirectPage(FileSystem *, Redirect *, LsmPgno);

int lsmFsPageWritable(Page *);

/* Functions to read, write and sync the log file. */
int lsmFsWriteLog(FileSystem *pFS, i64 iOff, LsmString *pStr);
int lsmFsSyncLog(FileSystem *pFS);
int lsmFsReadLog(FileSystem *pFS, i64 iOff, int nRead, LsmString *pStr);
int lsmFsTruncateLog(FileSystem *pFS, i64 nByte);
int lsmFsTruncateDb(FileSystem *pFS, i64 nByte);
int lsmFsCloseAndDeleteLog(FileSystem *pFS);

LsmFile *lsmFsDeferClose(FileSystem *pFS);

/* And to sync the db file */
int lsmFsSyncDb(FileSystem *, int);

void lsmFsFlushWaiting(FileSystem *, int *);

/* Used by lsm_info(ARRAY_STRUCTURE) and lsm_config(MMAP) */
int lsmInfoArrayStructure(lsm_db *pDb, int bBlock, Pgno iFirst, char **pzOut);
int lsmInfoArrayPages(lsm_db *pDb, Pgno iFirst, char **pzOut);
int lsmInfoArrayStructure(lsm_db *pDb, int bBlock, LsmPgno iFirst, char **pz);
int lsmInfoArrayPages(lsm_db *pDb, LsmPgno iFirst, char **pzOut);
int lsmConfigMmap(lsm_db *pDb, int *piParam);

int lsmEnvOpen(lsm_env *, const char *, int, lsm_file **);
int lsmEnvClose(lsm_env *pEnv, lsm_file *pFile);
int lsmEnvLock(lsm_env *pEnv, lsm_file *pFile, int iLock, int eLock);
int lsmEnvTestLock(lsm_env *pEnv, lsm_file *pFile, int iLock, int nLock, int);

int lsmEnvShmMap(lsm_env *, lsm_file *, int, int, void **); 
void lsmEnvShmBarrier(lsm_env *);
void lsmEnvShmUnmap(lsm_env *, lsm_file *, int);

void lsmEnvSleep(lsm_env *, int);

int lsmFsReadSyncedId(lsm_db *db, int, i64 *piVal);

int lsmFsSegmentContainsPg(FileSystem *pFS, Segment *, Pgno, int *);
int lsmFsSegmentContainsPg(FileSystem *pFS, Segment *, LsmPgno, int *);

void lsmFsPurgeCache(FileSystem *);

/*
** End of functions from "lsm_file.c".
**************************************************************************/

/* 
** Functions from file "lsm_sorted.c".
*/
int lsmInfoPageDump(lsm_db *, Pgno, int, char **);
int lsmInfoPageDump(lsm_db *, LsmPgno, int, char **);
void lsmSortedCleanup(lsm_db *);
int lsmSortedAutoWork(lsm_db *, int nUnit);

int lsmSortedWalkFreelist(lsm_db *, int, int (*)(void *, int, i64), void *);

int lsmSaveWorker(lsm_db *, int);

Changes to ext/lsm1/lsm_ckpt.c.
385
386
387
388
389
390
391
392

393
394
395
396
397
398
399
385
386
387
388
389
390
391

392
393
394
395
396
397
398
399







-
+







static void ckptExportAppendlist(
  lsm_db *db,                     /* Database connection */
  CkptBuffer *p,                  /* Checkpoint buffer to write to */
  int *piOut,                     /* IN/OUT: Offset within checkpoint buffer */
  int *pRc                        /* IN/OUT: Error code */
){
  int i;
  Pgno *aiAppend = db->pWorker->aiAppend;
  LsmPgno *aiAppend = db->pWorker->aiAppend;

  for(i=0; i<LSM_APPLIST_SZ; i++){
    ckptAppend64(p, piOut, aiAppend[i], pRc);
  }
};

static int ckptExportSnapshot( 
Changes to ext/lsm1/lsm_file.c.
265
266
267
268
269
270
271
272

273
274
275
276
277
278
279
265
266
267
268
269
270
271

272
273
274
275
276
277
278
279







-
+







**   The lsmFsSortedAppend() function sets the pSeg pointer to point to the
**   segment that the new page will be a part of. It is unset by
**   lsmFsPagePersist() after the page is written to disk.
*/
struct Page {
  u8 *aData;                      /* Buffer containing page data */
  int nData;                      /* Bytes of usable data at aData[] */
  Pgno iPg;                       /* Page number */
  LsmPgno iPg;                    /* Page number */
  int nRef;                       /* Number of outstanding references */
  int flags;                      /* Combination of PAGE_XXX flags */
  Page *pHashNext;                /* Next page in hash table slot */
  Page *pLruNext;                 /* Next page in LRU list */
  Page *pLruPrev;                 /* Previous page in LRU list */
  FileSystem *pFS;                /* File system that owns this page */

328
329
330
331
332
333
334
335

336
337
338
339
340
341
342
328
329
330
331
332
333
334

335
336
337
338
339
340
341
342







-
+







#else
# define IOERR_WRAPPER(rc) (rc)
#endif

#ifdef NDEBUG
# define assert_lists_are_ok(x)
#else
static Page *fsPageFindInHash(FileSystem *pFS, Pgno iPg, int *piHash);
static Page *fsPageFindInHash(FileSystem *pFS, LsmPgno iPg, int *piHash);

static void assert_lists_are_ok(FileSystem *pFS){
#if 0
  Page *p;

  assert( pFS->nMapLimit>=0 );

528
529
530
531
532
533
534
535

536
537
538
539
540
541
542
543

544
545
546
547
548
549
550
528
529
530
531
532
533
534

535
536
537
538
539
540
541
542

543
544
545
546
547
548
549
550







-
+







-
+







  return LSM_OK;
}

/*
** Return true if page iReal of the database should be accessed using mmap.
** False otherwise.
*/
static int fsMmapPage(FileSystem *pFS, Pgno iReal){
static int fsMmapPage(FileSystem *pFS, LsmPgno iReal){
  return ((i64)iReal*pFS->nPagesize <= pFS->nMapLimit);
}

/*
** Given that there are currently nHash slots in the hash table, return 
** the hash key for file iFile, page iPg.
*/
static int fsHashKey(int nHash, Pgno iPg){
static int fsHashKey(int nHash, LsmPgno iPg){
  return (iPg % nHash);
}

/*
** This is a helper function for lsmFsOpen(). It opens a single file on
** disk (either the database or log file).
*/
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
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







-
-
+
+




-
+




















-
+

-
+










-
+












-
+










-
+







** Return the page number of the first page on block iBlock. Blocks are
** numbered starting from 1.
**
** For a compressed database, page numbers are byte offsets. The first
** page on each block is the byte offset immediately following the 4-byte
** "previous block" pointer at the start of each block.
*/
static Pgno fsFirstPageOnBlock(FileSystem *pFS, int iBlock){
  Pgno iPg;
static LsmPgno fsFirstPageOnBlock(FileSystem *pFS, int iBlock){
  LsmPgno iPg;
  if( pFS->pCompress ){
    if( iBlock==1 ){
      iPg = pFS->nMetasize * 2 + 4;
    }else{
      iPg = pFS->nBlocksize * (Pgno)(iBlock-1) + 4;
      iPg = pFS->nBlocksize * (LsmPgno)(iBlock-1) + 4;
    }
  }else{
    const int nPagePerBlock = (pFS->nBlocksize / pFS->nPagesize);
    if( iBlock==1 ){
      iPg = 1 + ((pFS->nMetasize*2 + pFS->nPagesize - 1) / pFS->nPagesize);
    }else{
      iPg = 1 + (iBlock-1) * nPagePerBlock;
    }
  }
  return iPg;
}

/*
** Return the page number of the last page on block iBlock. Blocks are
** numbered starting from 1.
**
** For a compressed database, page numbers are byte offsets. The first
** page on each block is the byte offset of the byte immediately before 
** the 4-byte "next block" pointer at the end of each block.
*/
static Pgno fsLastPageOnBlock(FileSystem *pFS, int iBlock){
static LsmPgno fsLastPageOnBlock(FileSystem *pFS, int iBlock){
  if( pFS->pCompress ){
    return pFS->nBlocksize * (Pgno)iBlock - 1 - 4;
    return pFS->nBlocksize * (LsmPgno)iBlock - 1 - 4;
  }else{
    const int nPagePerBlock = (pFS->nBlocksize / pFS->nPagesize);
    return iBlock * nPagePerBlock;
  }
}

/*
** Return the block number of the block that page iPg is located on. 
** Blocks are numbered starting from 1.
*/
static int fsPageToBlock(FileSystem *pFS, Pgno iPg){
static int fsPageToBlock(FileSystem *pFS, LsmPgno iPg){
  if( pFS->pCompress ){
    return (int)((iPg / pFS->nBlocksize) + 1);
  }else{
    return (int)(1 + ((iPg-1) / (pFS->nBlocksize / pFS->nPagesize)));
  }
}

/*
** Return true if page iPg is the last page on its block.
**
** This function is only called in non-compressed database mode.
*/
static int fsIsLast(FileSystem *pFS, Pgno iPg){
static int fsIsLast(FileSystem *pFS, LsmPgno iPg){
  const int nPagePerBlock = (pFS->nBlocksize / pFS->nPagesize);
  assert( !pFS->pCompress );
  return ( iPg && (iPg % nPagePerBlock)==0 );
}

/*
** Return true if page iPg is the first page on its block.
**
** This function is only called in non-compressed database mode.
*/
static int fsIsFirst(FileSystem *pFS, Pgno iPg){
static int fsIsFirst(FileSystem *pFS, LsmPgno iPg){
  const int nPagePerBlock = (pFS->nBlocksize / pFS->nPagesize);
  assert( !pFS->pCompress );
  return ( (iPg % nPagePerBlock)==1
        || (iPg<nPagePerBlock && iPg==fsFirstPageOnBlock(pFS, 1))
  );
}

963
964
965
966
967
968
969
970

971
972
973
974
975
976
977
963
964
965
966
967
968
969

970
971
972
973
974
975
976
977







-
+







  }
  return pPage->aData;
}

/*
** Return the page number of a page.
*/
Pgno lsmFsPageNumber(Page *pPage){
LsmPgno lsmFsPageNumber(Page *pPage){
  /* assert( (pPage->flags & PAGE_DIRTY)==0 ); */
  return pPage ? pPage->iPg : 0;
}

/*
** Page pPg is currently part of the LRU list belonging to pFS. Remove
** it from the list. pPg->pLruNext and pPg->pLruPrev are cleared by this
1054
1055
1056
1057
1058
1059
1060
1061

1062
1063
1064
1065
1066
1067
1068
1054
1055
1056
1057
1058
1059
1060

1061
1062
1063
1064
1065
1066
1067
1068







-
+







/*
** Search the hash-table for page iPg. If an entry is round, return a pointer
** to it. Otherwise, return NULL.
**
** Either way, if argument piHash is not NULL set *piHash to the hash slot
** number that page iPg would be stored in before returning.
*/
static Page *fsPageFindInHash(FileSystem *pFS, Pgno iPg, int *piHash){
static Page *fsPageFindInHash(FileSystem *pFS, LsmPgno iPg, int *piHash){
  Page *p;                        /* Return value */
  int iHash = fsHashKey(pFS->nHash, iPg);

  if( piHash ) *piHash = iHash;
  for(p=pFS->apHash[iHash]; p; p=p->pHashNext){
    if( p->iPg==iPg) break;
  }
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
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







-
-
+
+












-
+













-
+







}

/*
** If page iPg has been redirected according to the redirections in the
** object passed as the second argument, return the destination page to
** which it is redirected. Otherwise, return a copy of iPg.
*/
Pgno lsmFsRedirectPage(FileSystem *pFS, Redirect *pRedir, Pgno iPg){
  Pgno iReal = iPg;
LsmPgno lsmFsRedirectPage(FileSystem *pFS, Redirect *pRedir, LsmPgno iPg){
  LsmPgno iReal = iPg;

  if( pRedir ){
    const int nPagePerBlock = (
        pFS->pCompress ? pFS->nBlocksize : (pFS->nBlocksize / pFS->nPagesize)
    );
    int iBlk = fsPageToBlock(pFS, iPg);
    int i;
    for(i=0; i<pRedir->n; i++){
      int iFrom = pRedir->a[i].iFrom;
      if( iFrom>iBlk ) break;
      if( iFrom==iBlk ){
        int iTo = pRedir->a[i].iTo;
        iReal = iPg - (Pgno)(iFrom - iTo) * nPagePerBlock;
        iReal = iPg - (LsmPgno)(iFrom - iTo) * nPagePerBlock;
        if( iTo==1 ){
          iReal += (fsFirstPageOnBlock(pFS, 1)-1);
        }
        break;
      }
    }
  }

  assert( iReal!=0 );
  return iReal;
}

/* Required by the circular fsBlockNext<->fsPageGet dependency. */
static int fsPageGet(FileSystem *, Segment *, Pgno, int, Page **, int *);
static int fsPageGet(FileSystem *, Segment *, LsmPgno, int, Page **, int *);

/*
** Parameter iBlock is a database file block. This function reads the value 
** stored in the blocks "next block" pointer and stores it in *piNext.
** LSM_OK is returned if everything is successful, or an LSM error code
** otherwise.
*/
1265
1266
1267
1268
1269
1270
1271
1272

1273
1274
1275
1276
1277
1278
1279
1265
1266
1267
1268
1269
1270
1271

1272
1273
1274
1275
1276
1277
1278
1279







-
+







  }
  return rc;
}

/*
** Return the page number of the last page on the same block as page iPg.
*/
Pgno fsLastPageOnPagesBlock(FileSystem *pFS, Pgno iPg){
LsmPgno fsLastPageOnPagesBlock(FileSystem *pFS, LsmPgno iPg){
  return fsLastPageOnBlock(pFS, fsPageToBlock(pFS, iPg));
}

/*
** Read nData bytes of data from offset iOff of the database file into
** buffer aData. If this means reading past the end of a block, follow
** the block pointer to the next block and continue reading.
1533
1534
1535
1536
1537
1538
1539
1540

1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552

1553
1554
1555
1556
1557
1558
1559
1533
1534
1535
1536
1537
1538
1539

1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551

1552
1553
1554
1555
1556
1557
1558
1559







-
+











-
+







** to the total number of free bytes before returning.
**
** If no error occurs, LSM_OK is returned. Otherwise, an lsm error code.
*/
static int fsPageGet(
  FileSystem *pFS,                /* File-system handle */
  Segment *pSeg,                  /* Block redirection to use (or NULL) */
  Pgno iPg,                       /* Page id */
  LsmPgno iPg,                    /* Page id */
  int noContent,                  /* True to not load content from disk */
  Page **ppPg,                    /* OUT: New page handle */
  int *pnSpace                    /* OUT: Bytes of free space */
){
  Page *p;
  int iHash;
  int rc = LSM_OK;

  /* In most cases iReal is the same as iPg. Except, if pSeg->pRedirect is 
  ** not NULL, and the block containing iPg has been redirected, then iReal
  ** is the page number after redirection.  */
  Pgno iReal = lsmFsRedirectPage(pFS, (pSeg ? pSeg->pRedirect : 0), iPg);
  LsmPgno iReal = lsmFsRedirectPage(pFS, (pSeg ? pSeg->pRedirect : 0), iPg);

  assert_lists_are_ok(pFS);
  assert( iPg>=fsFirstPageOnBlock(pFS, 1) );
  assert( iReal>=fsFirstPageOnBlock(pFS, 1) );
  *ppPg = 0;

  /* Search the hash-table for the page */
1685
1686
1687
1688
1689
1690
1691
1692
1693


1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709


1710
1711
1712
1713
1714
1715
1716
1685
1686
1687
1688
1689
1690
1691


1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707


1708
1709
1710
1711
1712
1713
1714
1715
1716







-
-
+
+














-
-
+
+







/*
** Return true if the first or last page of segment pRun falls between iFirst
** and iLast, inclusive, and pRun is not equal to pIgnore.
*/
static int fsRunEndsBetween(
  Segment *pRun, 
  Segment *pIgnore, 
  Pgno iFirst, 
  Pgno iLast
  LsmPgno iFirst, 
  LsmPgno iLast
){
  return (pRun!=pIgnore && (
        (pRun->iFirst>=iFirst && pRun->iFirst<=iLast)
     || (pRun->iLastPg>=iFirst && pRun->iLastPg<=iLast)
  ));
}

/*
** Return true if level pLevel contains a segment other than pIgnore for
** which the first or last page is between iFirst and iLast, inclusive.
*/
static int fsLevelEndsBetween(
  Level *pLevel, 
  Segment *pIgnore, 
  Pgno iFirst, 
  Pgno iLast
  LsmPgno iFirst, 
  LsmPgno iLast
){
  int i;

  if( fsRunEndsBetween(&pLevel->lhs, pIgnore, iFirst, iLast) ){
    return 1;
  }
  for(i=0; i<pLevel->nRight; i++){
1729
1730
1731
1732
1733
1734
1735
1736
1737


1738
1739
1740
1741
1742

1743
1744
1745
1746
1747
1748
1749
1729
1730
1731
1732
1733
1734
1735


1736
1737
1738
1739
1740
1741

1742
1743
1744
1745
1746
1747
1748
1749







-
-
+
+




-
+







static int fsFreeBlock(
  FileSystem *pFS,                /* File system object */
  Snapshot *pSnapshot,            /* Worker snapshot */
  Segment *pIgnore,               /* Ignore this run when searching */
  int iBlk                        /* Block number of block to free */
){
  int rc = LSM_OK;                /* Return code */
  Pgno iFirst;                    /* First page on block iBlk */
  Pgno iLast;                     /* Last page on block iBlk */
  LsmPgno iFirst;                 /* First page on block iBlk */
  LsmPgno iLast;                  /* Last page on block iBlk */
  Level *pLevel;                  /* Used to iterate through levels */

  int iIn;                        /* Used to iterate through append points */
  int iOut = 0;                   /* Used to output append points */
  Pgno *aApp = pSnapshot->aiAppend;
  LsmPgno *aApp = pSnapshot->aiAppend;

  iFirst = fsFirstPageOnBlock(pFS, iBlk);
  iLast = fsLastPageOnBlock(pFS, iBlk);

  /* Check if any other run in the snapshot has a start or end page 
  ** within this block. If there is such a run, return early. */
  for(pLevel=lsmDbSnapshotLevel(pSnapshot); pLevel; pLevel=pLevel->pNext){
1807
1808
1809
1810
1811
1812
1813

1814
1815






1816
1817
1818

1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831

1832
1833
1834
1835
1836
1837
1838
1807
1808
1809
1810
1811
1812
1813
1814


1815
1816
1817
1818
1819
1820
1821
1822

1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835

1836
1837
1838
1839
1840
1841
1842
1843







+
-
-
+
+
+
+
+
+


-
+












-
+







}

/*
** aPgno is an array containing nPgno page numbers. Return the smallest page
** number from the array that falls on block iBlk. Or, if none of the pages
** in aPgno[] fall on block iBlk, return 0.
*/
static LsmPgno firstOnBlock(
static Pgno firstOnBlock(FileSystem *pFS, int iBlk, Pgno *aPgno, int nPgno){
  Pgno iRet = 0;
  FileSystem *pFS, 
  int iBlk, 
  LsmPgno *aPgno, 
  int nPgno
){
  LsmPgno iRet = 0;
  int i;
  for(i=0; i<nPgno; i++){
    Pgno iPg = aPgno[i];
    LsmPgno iPg = aPgno[i];
    if( fsPageToBlock(pFS, iPg)==iBlk && (iRet==0 || iPg<iRet) ){
      iRet = iPg;
    }
  }
  return iRet;
}

#ifndef NDEBUG
/*
** Return true if page iPg, which is a part of segment p, lies on
** a redirected block. 
*/
static int fsPageRedirects(FileSystem *pFS, Segment *p, Pgno iPg){
static int fsPageRedirects(FileSystem *pFS, Segment *p, LsmPgno iPg){
  return (iPg!=0 && iPg!=lsmFsRedirectPage(pFS, p->pRedirect, iPg));
}

/*
** Return true if the second argument is not NULL and any of the first
** last or root pages lie on a redirected block. 
*/
1850
1851
1852
1853
1854
1855
1856
1857

1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874

1875
1876
1877
1878
1879
1880
1881
1855
1856
1857
1858
1859
1860
1861

1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878

1879
1880
1881
1882
1883
1884
1885
1886







-
+
















-
+







** the segment pRun. This function gobbles from the start of the run to the
** first page that appears in aPgno[] (i.e. so that the aPgno[] entry is
** the new first page of the run).
*/
void lsmFsGobble(
  lsm_db *pDb,
  Segment *pRun, 
  Pgno *aPgno,
  LsmPgno *aPgno,
  int nPgno
){
  int rc = LSM_OK;
  FileSystem *pFS = pDb->pFS;
  Snapshot *pSnapshot = pDb->pWorker;
  int iBlk;

  assert( pRun->nSize>0 );
  assert( 0==fsSegmentRedirects(pFS, pRun) );
  assert( nPgno>0 && 0==fsPageRedirects(pFS, pRun, aPgno[0]) );

  iBlk = fsPageToBlock(pFS, pRun->iFirst);
  pRun->nSize += (int)(pRun->iFirst - fsFirstPageOnBlock(pFS, iBlk));

  while( rc==LSM_OK ){
    int iNext = 0;
    Pgno iFirst = firstOnBlock(pFS, iBlk, aPgno, nPgno);
    LsmPgno iFirst = firstOnBlock(pFS, iBlk, aPgno, nPgno);
    if( iFirst ){
      pRun->iFirst = iFirst;
      break;
    }
    rc = fsBlockNext(pFS, pRun, iBlk, &iNext);
    if( rc==LSM_OK ) rc = fsFreeBlock(pFS, pSnapshot, pRun, iBlk);
    pRun->nSize -= (int)(
1901
1902
1903
1904
1905
1906
1907
1908

1909
1910

1911
1912

1913
1914
1915
1916
1917
1918
1919
1906
1907
1908
1909
1910
1911
1912

1913
1914

1915
1916

1917
1918
1919
1920
1921
1922
1923
1924







-
+

-
+

-
+







**   *piNext = iPg + nByte;
**
** But take block overflow and redirection into account.
*/
static int fsNextPageOffset(
  FileSystem *pFS,                /* File system object */
  Segment *pSeg,                  /* Segment to move within */
  Pgno iPg,                       /* Offset of current page */
  LsmPgno iPg,                    /* Offset of current page */
  int nByte,                      /* Size of current page including headers */
  Pgno *piNext                    /* OUT: Offset of next page. Or zero (EOF) */
  LsmPgno *piNext                 /* OUT: Offset of next page. Or zero (EOF) */
){
  Pgno iNext;
  LsmPgno iNext;
  int rc;

  assert( pFS->pCompress );

  rc = fsAddOffset(pFS, pSeg, iPg, nByte-1, &iNext);
  if( pSeg && iNext==pSeg->iLastPg ){
    iNext = 0;
1935
1936
1937
1938
1939
1940
1941
1942
1943


1944
1945
1946
1947
1948
1949
1950
1940
1941
1942
1943
1944
1945
1946


1947
1948
1949
1950
1951
1952
1953
1954
1955







-
-
+
+







** LSM_OK is returned if no error occurs. Otherwise, an lsm error code.
** If any value other than LSM_OK is returned, then the final value of
** *piPrev is undefined.
*/
static int fsGetPageBefore(
  FileSystem *pFS, 
  Segment *pSeg, 
  Pgno iPg, 
  Pgno *piPrev
  LsmPgno iPg, 
  LsmPgno *piPrev
){
  u8 aSz[3];
  int rc;
  i64 iRead;

  assert( pFS->pCompress );

1986
1987
1988
1989
1990
1991
1992
1993

1994
1995
1996
1997
1998
1999
2000
1991
1992
1993
1994
1995
1996
1997

1998
1999
2000
2001
2002
2003
2004
2005







-
+







**
** Page references returned by this function should be released by the 
** caller using lsmFsPageRelease().
*/
int lsmFsDbPageNext(Segment *pRun, Page *pPg, int eDir, Page **ppNext){
  int rc = LSM_OK;
  FileSystem *pFS = pPg->pFS;
  Pgno iPg = pPg->iPg;
  LsmPgno iPg = pPg->iPg;

  assert( 0==fsSegmentRedirects(pFS, pRun) );
  if( pFS->pCompress ){
    int nSpace = pPg->nCompress + 2*3;

    do {
      if( eDir>0 ){
2058
2059
2060
2061
2062
2063
2064
2065

2066
2067
2068


2069
2070
2071
2072
2073
2074
2075
2063
2064
2065
2066
2067
2068
2069

2070
2071


2072
2073
2074
2075
2076
2077
2078
2079
2080







-
+

-
-
+
+







** already allocated block. If it is possible, the page number of the first
** page to use for the new segment is returned. Otherwise zero.
**
** If argument pLvl is not NULL, then this function will not attempt to
** start the new segment immediately following any segment that is part
** of the right-hand-side of pLvl.
*/
static Pgno findAppendPoint(FileSystem *pFS, Level *pLvl){
static LsmPgno findAppendPoint(FileSystem *pFS, Level *pLvl){
  int i;
  Pgno *aiAppend = pFS->pDb->pWorker->aiAppend;
  Pgno iRet = 0;
  LsmPgno *aiAppend = pFS->pDb->pWorker->aiAppend;
  LsmPgno iRet = 0;

  for(i=LSM_APPLIST_SZ-1; iRet==0 && i>=0; i--){
    if( (iRet = aiAppend[i]) ){
      if( pLvl ){
        int iBlk = fsPageToBlock(pFS, iRet);
        int j;
        for(j=0; iRet && j<pLvl->nRight; j++){
2094
2095
2096
2097
2098
2099
2100
2101
2102


2103
2104

2105
2106
2107
2108
2109
2110
2111
2099
2100
2101
2102
2103
2104
2105


2106
2107
2108

2109
2110
2111
2112
2113
2114
2115
2116







-
-
+
+

-
+







  Snapshot *pSnapshot,
  Level *pLvl,
  int bDefer,
  Page **ppOut
){
  int rc = LSM_OK;
  Page *pPg = 0;
  Pgno iApp = 0;
  Pgno iNext = 0;
  LsmPgno iApp = 0;
  LsmPgno iNext = 0;
  Segment *p = &pLvl->lhs;
  Pgno iPrev = p->iLastPg;
  LsmPgno iPrev = p->iLastPg;

  *ppOut = 0;
  assert( p->pRedirect==0 );

  if( pFS->pCompress || bDefer ){
    /* In compressed database mode the page is not assigned a page number
    ** or location in the database file at this point. This will be done
2191
2192
2193
2194
2195
2196
2197
2198

2199
2200
2201
2202
2203
2204
2205
2196
2197
2198
2199
2200
2201
2202

2203
2204
2205
2206
2207
2208
2209
2210







-
+







    ** Shift this extra block back to the free-block list. 
    **
    ** Otherwise, add the first free page in the last block used by the run
    ** to the lAppend list.
    */
    if( fsLastPageOnPagesBlock(pFS, p->iLastPg)!=p->iLastPg ){
      int i;
      Pgno *aiAppend = pFS->pDb->pWorker->aiAppend;
      LsmPgno *aiAppend = pFS->pDb->pWorker->aiAppend;
      for(i=0; i<LSM_APPLIST_SZ; i++){
        if( aiAppend[i]==0 ){
          aiAppend[i] = p->iLastPg+1;
          break;
        }
      }
    }else if( pFS->pCompress==0 ){
2222
2223
2224
2225
2226
2227
2228
2229

2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241

2242
2243
2244
2245
2246
2247
2248
2227
2228
2229
2230
2231
2232
2233

2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245

2246
2247
2248
2249
2250
2251
2252
2253







-
+











-
+







}

/*
** Obtain a reference to page number iPg.
**
** Return LSM_OK if successful, or an lsm error code if an error occurs.
*/
int lsmFsDbPageGet(FileSystem *pFS, Segment *pSeg, Pgno iPg, Page **ppPg){
int lsmFsDbPageGet(FileSystem *pFS, Segment *pSeg, LsmPgno iPg, Page **ppPg){
  return fsPageGet(pFS, pSeg, iPg, 0, ppPg, 0);
}

/*
** Obtain a reference to the last page in the segment passed as the 
** second argument.
**
** Return LSM_OK if successful, or an lsm error code if an error occurs.
*/
int lsmFsDbPageLast(FileSystem *pFS, Segment *pSeg, Page **ppPg){
  int rc;
  Pgno iPg = pSeg->iLastPg;
  LsmPgno iPg = pSeg->iLastPg;
  if( pFS->pCompress ){
    int nSpace;
    iPg++;
    do {
      nSpace = 0;
      rc = fsGetPageBefore(pFS, pSeg, iPg, &iPg);
      if( rc==LSM_OK ){
2362
2363
2364
2365
2366
2367
2368
2369

2370
2371

2372
2373
2374
2375
2376

2377
2378
2379
2380
2381
2382
2383
2367
2368
2369
2370
2371
2372
2373

2374
2375

2376
2377
2378
2379
2380

2381
2382
2383
2384
2385
2386
2387
2388







-
+

-
+




-
+







** number (*piPg) lies on block iFrom, then calculate the equivalent
** page on block iTo and set *piPg to this value before returning.
*/
static void fsMovePage(
  FileSystem *pFS,                /* File system object */
  int iTo,                        /* Destination block */
  int iFrom,                      /* Source block */
  Pgno *piPg                      /* IN/OUT: Page number */
  LsmPgno *piPg                   /* IN/OUT: Page number */
){
  Pgno iPg = *piPg;
  LsmPgno iPg = *piPg;
  if( iFrom==fsPageToBlock(pFS, iPg) ){
    const int nPagePerBlock = (
        pFS->pCompress ? pFS ->nBlocksize : (pFS->nBlocksize / pFS->nPagesize)
    );
    *piPg = iPg - (Pgno)(iFrom - iTo) * nPagePerBlock;
    *piPg = iPg - (LsmPgno)(iFrom - iTo) * nPagePerBlock;
  }
}

/*
** Copy the contents of block iFrom to block iTo. 
**
** It is safe to assume that there are no outstanding references to pages 
2453
2454
2455
2456
2457
2458
2459
2460

2461
2462
2463
2464
2465
2466
2467

2468
2469
2470
2471
2472
2473
2474


2475
2476
2477
2478
2479
2480
2481
2458
2459
2460
2461
2462
2463
2464

2465
2466
2467
2468
2469
2470
2471

2472
2473
2474
2475
2476
2477


2478
2479
2480
2481
2482
2483
2484
2485
2486







-
+






-
+





-
-
+
+







/*
** Append raw data to a segment. Return the database file offset that the
** data is written to (this may be used as the page number if the data
** being appended is a new page record).
**
** This function is only used in compressed database mode.
*/
static Pgno fsAppendData(
static LsmPgno fsAppendData(
  FileSystem *pFS,                /* File-system handle */
  Segment *pSeg,                  /* Segment to append to */
  const u8 *aData,                /* Buffer containing data to write */
  int nData,                      /* Size of buffer aData[] in bytes */
  int *pRc                        /* IN/OUT: Error code */
){
  Pgno iRet = 0;
  LsmPgno iRet = 0;
  int rc = *pRc;
  assert( pFS->pCompress );
  if( rc==LSM_OK ){
    int nRem = 0;
    int nWrite = 0;
    Pgno iLastOnBlock;
    Pgno iApp = pSeg->iLastPg+1;
    LsmPgno iLastOnBlock;
    LsmPgno iApp = pSeg->iLastPg+1;

    /* If this is the first data written into the segment, find an append-point
    ** or allocate a new block.  */
    if( iApp==1 ){
      pSeg->iFirst = iApp = findAppendPoint(pFS, 0);
      if( iApp==0 ){
        int iBlk;
2515
2516
2517
2518
2519
2520
2521
2522

2523
2524
2525
2526
2527
2528
2529
2520
2521
2522
2523
2524
2525
2526

2527
2528
2529
2530
2531
2532
2533
2534







-
+







          assert( iApp==(fsPageToBlock(pFS, iApp)*pFS->nBlocksize)-4 );
          lsmPutU32(aPtr, iBlk);
          rc = lsmEnvWrite(pFS->pEnv, pFS->fdDb, iApp, aPtr, sizeof(aPtr));
        }

        /* Set the "prev" pointer on the new block */
        if( rc==LSM_OK ){
          Pgno iWrite;
          LsmPgno iWrite;
          lsmPutU32(aPtr, fsPageToBlock(pFS, iApp));
          iWrite = fsFirstPageOnBlock(pFS, iBlk);
          rc = lsmEnvWrite(pFS->pEnv, pFS->fdDb, iWrite-4, aPtr, sizeof(aPtr));
          if( nRem>0 ) iApp = iWrite;
        }
      }else{
        /* The next block is already allocated. */
2584
2585
2586
2587
2588
2589
2590
2591

2592
2593
2594
2595

2596
2597
2598
2599
2600
2601
2602
2589
2590
2591
2592
2593
2594
2595

2596
2597
2598
2599

2600
2601
2602
2603
2604
2605
2606
2607







-
+



-
+







** LSM_OK is returned if successful, or an lsm error code otherwise. If
** any value other than LSM_OK is returned, then the final value of all
** output variables is undefined.
*/
static int fsAppendPage(
  FileSystem *pFS, 
  Segment *pSeg,
  Pgno *piNew,
  LsmPgno *piNew,
  int *piPrev,
  int *piNext
){
  Pgno iPrev = pSeg->iLastPg;
  LsmPgno iPrev = pSeg->iLastPg;
  int rc;
  assert( iPrev!=0 );

  *piPrev = 0;
  *piNext = 0;

  if( fsIsLast(pFS, iPrev) ){
2646
2647
2648
2649
2650
2651
2652
2653

2654
2655
2656
2657
2658
2659
2660
2651
2652
2653
2654
2655
2656
2657

2658
2659
2660
2661
2662
2663
2664
2665







-
+







  }
  *pRc = rc;
}

/*
** If there exists a hash-table entry associated with page iPg, remove it.
*/
static void fsRemoveHashEntry(FileSystem *pFS, Pgno iPg){
static void fsRemoveHashEntry(FileSystem *pFS, LsmPgno iPg){
  Page *p;
  int iHash = fsHashKey(pFS->nHash, iPg);

  for(p=pFS->apHash[iHash]; p && p->iPg!=iPg; p=p->pHashNext);

  if( p ){
    assert( p->nRef==0 || (p->flags & PAGE_FREE)==0 );
2800
2801
2802
2803
2804
2805
2806
2807
2808


2809
2810
2811
2812
2813
2814
2815
2805
2806
2807
2808
2809
2810
2811


2812
2813
2814
2815
2816
2817
2818
2819
2820







-
-
+
+







int lsmFsSortedPadding(
  FileSystem *pFS, 
  Snapshot *pSnapshot,
  Segment *pSeg
){
  int rc = LSM_OK;
  if( pFS->pCompress && pSeg->iFirst ){
    Pgno iLast2;
    Pgno iLast = pSeg->iLastPg;     /* Current last page of segment */
    LsmPgno iLast2;
    LsmPgno iLast = pSeg->iLastPg;  /* Current last page of segment */
    int nPad;                       /* Bytes of padding required */
    u8 aSz[3];

    iLast2 = (1 + iLast/pFS->szSector) * pFS->szSector - 1;
    assert( fsPageToBlock(pFS, iLast)==fsPageToBlock(pFS, iLast2) );
    nPad = (int)(iLast2 - iLast);

2931
2932
2933
2934
2935
2936
2937
2938

2939
2940
2941
2942
2943
2944
2945
2946

2947
2948
2949
2950
2951
2952
2953
2936
2937
2938
2939
2940
2941
2942

2943
2944
2945
2946
2947
2948
2949
2950

2951
2952
2953
2954
2955
2956
2957
2958







-
+







-
+







int lsmFsSectorSize(FileSystem *pFS){
  return pFS->szSector;
}

/*
** Helper function for lsmInfoArrayStructure().
*/
static Segment *startsWith(Segment *pRun, Pgno iFirst){
static Segment *startsWith(Segment *pRun, LsmPgno iFirst){
  return (iFirst==pRun->iFirst) ? pRun : 0;
}

/*
** Return the segment that starts with page iFirst, if any. If no such segment
** can be found, return NULL.
*/
static Segment *findSegment(Snapshot *pWorker, Pgno iFirst){
static Segment *findSegment(Snapshot *pWorker, LsmPgno iFirst){
  Level *pLvl;                    /* Used to iterate through db levels */
  Segment *pSeg = 0;              /* Pointer to segment to return */

  for(pLvl=lsmDbSnapshotLevel(pWorker); pLvl && pSeg==0; pLvl=pLvl->pNext){
    if( 0==(pSeg = startsWith(&pLvl->lhs, iFirst)) ){
      int i;
      for(i=0; i<pLvl->nRight; i++){
2966
2967
2968
2969
2970
2971
2972
2973

2974
2975
2976
2977
2978
2979
2980
2971
2972
2973
2974
2975
2976
2977

2978
2979
2980
2981
2982
2983
2984
2985







-
+







** eventually free the string using lsmFree().
**
** If an error occurs, *pzOut is set to NULL and an LSM error code returned.
*/
int lsmInfoArrayStructure(
  lsm_db *pDb, 
  int bBlock,                     /* True for block numbers only */
  Pgno iFirst,
  LsmPgno iFirst,
  char **pzOut
){
  int rc = LSM_OK;
  Snapshot *pWorker;              /* Worker snapshot */
  Segment *pArray = 0;            /* Array to report on */
  int bUnlock = 0;

3031
3032
3033
3034
3035
3036
3037
3038

3039
3040
3041
3042
3043
3044
3045
3036
3037
3038
3039
3040
3041
3042

3043
3044
3045
3046
3047
3048
3049
3050







-
+







  }
  return rc;
}

int lsmFsSegmentContainsPg(
  FileSystem *pFS, 
  Segment *pSeg, 
  Pgno iPg, 
  LsmPgno iPg, 
  int *pbRes
){
  Redirect *pRedir = pSeg->pRedirect;
  int rc = LSM_OK;
  int iBlk;
  int iLastBlk;
  int iPgBlock;                   /* Block containing page iPg */
3060
3061
3062
3063
3064
3065
3066
3067

3068
3069
3070
3071
3072
3073
3074
3065
3066
3067
3068
3069
3070
3071

3072
3073
3074
3075
3076
3077
3078
3079







-
+







** This function implements the lsm_info(LSM_INFO_ARRAY_PAGES) request.
** If successful, *pzOut is set to point to a nul-terminated string 
** containing the array structure and LSM_OK is returned. The caller should
** eventually free the string using lsmFree().
**
** If an error occurs, *pzOut is set to NULL and an LSM error code returned.
*/
int lsmInfoArrayPages(lsm_db *pDb, Pgno iFirst, char **pzOut){
int lsmInfoArrayPages(lsm_db *pDb, LsmPgno iFirst, char **pzOut){
  int rc = LSM_OK;
  Snapshot *pWorker;              /* Worker snapshot */
  Segment *pSeg = 0;              /* Array to report on */
  int bUnlock = 0;

  *pzOut = 0;
  if( iFirst==0 ) return LSM_ERROR;
3293
3294
3295
3296
3297
3298
3299
3300

3301
3302
3303
3304
3305
3306
3307
3298
3299
3300
3301
3302
3303
3304

3305
3306
3307
3308
3309
3310
3311
3312







-
+







#ifndef NDEBUG
/*
** Return true if pPg happens to be the last page in segment pSeg. Or false
** otherwise. This function is only invoked as part of assert() conditions.
*/
int lsmFsDbPageIsLast(Segment *pSeg, Page *pPg){
  if( pPg->pFS->pCompress ){
    Pgno iNext = 0;
    LsmPgno iNext = 0;
    int rc;
    rc = fsNextPageOffset(pPg->pFS, pSeg, pPg->iPg, pPg->nCompress+6, &iNext);
    return (rc!=LSM_OK || iNext==0);
  }
  return (pPg->iPg==pSeg->iLastPg);
}
#endif
Changes to ext/lsm1/lsm_main.c.
579
580
581
582
583
584
585
586

587
588
589
590
591
592
593

594
595
596
597
598
599
600
601

602
603
604
605
606
607
608
579
580
581
582
583
584
585

586
587
588
589
590
591
592

593
594
595
596
597
598
599
600

601
602
603
604
605
606
607
608







-
+






-
+







-
+







    case LSM_INFO_DB_STRUCTURE: {
      char **pzVal = va_arg(ap, char **);
      rc = lsmStructList(pDb, pzVal);
      break;
    }

    case LSM_INFO_ARRAY_STRUCTURE: {
      Pgno pgno = va_arg(ap, Pgno);
      LsmPgno pgno = va_arg(ap, LsmPgno);
      char **pzVal = va_arg(ap, char **);
      rc = lsmInfoArrayStructure(pDb, 0, pgno, pzVal);
      break;
    }

    case LSM_INFO_ARRAY_PAGES: {
      Pgno pgno = va_arg(ap, Pgno);
      LsmPgno pgno = va_arg(ap, LsmPgno);
      char **pzVal = va_arg(ap, char **);
      rc = lsmInfoArrayPages(pDb, pgno, pzVal);
      break;
    }

    case LSM_INFO_PAGE_HEX_DUMP:
    case LSM_INFO_PAGE_ASCII_DUMP: {
      Pgno pgno = va_arg(ap, Pgno);
      LsmPgno pgno = va_arg(ap, LsmPgno);
      char **pzVal = va_arg(ap, char **);
      int bUnlock = 0;
      rc = infoGetWorker(pDb, 0, &bUnlock);
      if( rc==LSM_OK ){
        int bHex = (eParam==LSM_INFO_PAGE_HEX_DUMP);
        rc = lsmInfoPageDump(pDb, pgno, bHex, pzVal);
      }
Changes to ext/lsm1/lsm_sorted.c.
100
101
102
103
104
105
106
107

108
109

110
111
112
113
114
115
116
100
101
102
103
104
105
106

107
108

109
110
111
112
113
114
115
116







-
+

-
+









#ifndef LSM_SEGMENTPTR_FREE_THRESHOLD
# define LSM_SEGMENTPTR_FREE_THRESHOLD 1024
#endif

typedef struct SegmentPtr SegmentPtr;
typedef struct Blob Blob;
typedef struct LsmBlob LsmBlob;

struct Blob {
struct LsmBlob {
  lsm_env *pEnv;
  void *pData;
  int nData;
  int nAlloc;
};

/*
125
126
127
128
129
130
131
132

133
134
135
136
137

138
139
140
141
142
143


144
145
146
147
148
149
150
125
126
127
128
129
130
131

132
133
134
135
136

137
138
139
140
141


142
143
144
145
146
147
148
149
150







-
+




-
+




-
-
+
+







  Level *pLevel;                /* Level object segment is part of */
  Segment *pSeg;                /* Segment to access */

  /* Current page. See segmentPtrLoadPage(). */
  Page *pPg;                    /* Current page */
  u16 flags;                    /* Copy of page flags field */
  int nCell;                    /* Number of cells on pPg */
  Pgno iPtr;                    /* Base cascade pointer */
  LsmPgno iPtr;                 /* Base cascade pointer */

  /* Current cell. See segmentPtrLoadCell() */
  int iCell;                    /* Current record within page pPg */
  int eType;                    /* Type of current record */
  Pgno iPgPtr;                  /* Cascade pointer offset */
  LsmPgno iPgPtr;               /* Cascade pointer offset */
  void *pKey; int nKey;         /* Key associated with current record */
  void *pVal; int nVal;         /* Current record value (eType==WRITE only) */

  /* Blobs used to allocate buffers for pKey and pVal as required */
  Blob blob1;
  Blob blob2;
  LsmBlob blob1;
  LsmBlob blob2;
};

/*
** Used to iterate through the keys stored in a b-tree hierarchy from start
** to finish. Only First() and Next() operations are required.
**
**   btreeCursorNew()
167
168
169
170
171
172
173
174

175
176
177

178
179
180
181
182
183
184
167
168
169
170
171
172
173

174
175
176

177
178
179
180
181
182
183
184







-
+


-
+







  int iPg;                        /* Current entry in aPg[]. -1 -> EOF. */
  BtreePg *aPg;                   /* Pages from root to current location */

  /* Cache of current entry. pKey==0 for EOF. */
  void *pKey;
  int nKey;
  int eType;
  Pgno iPtr;
  LsmPgno iPtr;

  /* Storage for key, if not local */
  Blob blob;
  LsmBlob blob;
};


/*
** A cursor used for merged searches or iterations through up to one
** Tree structure and any number of sorted files.
**
199
200
201
202
203
204
205
206
207


208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

225
226
227
228
229
230
231
199
200
201
202
203
204
205


206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

224
225
226
227
228
229
230
231







-
-
+
+
















-
+







*/
struct MultiCursor {
  lsm_db *pDb;                    /* Connection that owns this cursor */
  MultiCursor *pNext;             /* Next cursor owned by connection pDb */
  int flags;                      /* Mask of CURSOR_XXX flags */

  int eType;                      /* Cache of current key type */
  Blob key;                       /* Cache of current key (or NULL) */
  Blob val;                       /* Cache of current value */
  LsmBlob key;                    /* Cache of current key (or NULL) */
  LsmBlob val;                    /* Cache of current value */

  /* All the component cursors: */
  TreeCursor *apTreeCsr[2];       /* Up to two tree cursors */
  int iFree;                      /* Next element of free-list (-ve for eof) */
  SegmentPtr *aPtr;               /* Array of segment pointers */
  int nPtr;                       /* Size of array aPtr[] */
  BtreeCursor *pBtCsr;            /* b-tree cursor (db writes only) */

  /* Comparison results */
  int nTree;                      /* Size of aTree[] array */
  int *aTree;                     /* Array of comparison results */

  /* Used by cursors flushing the in-memory tree only */
  void *pSystemVal;               /* Pointer to buffer to free */

  /* Used by worker cursors only */
  Pgno *pPrevMergePtr;
  LsmPgno *pPrevMergePtr;
};

/*
** The following constants are used to assign integers to each component
** cursor of a multi-cursor.
*/
#define CURSOR_DATA_TREE0     0   /* Current tree cursor (apTreeCsr[0]) */
291
292
293
294
295
296
297
298

299
300

301
302

303
304
305
306
307
308
309
291
292
293
294
295
296
297

298
299

300
301

302
303
304
305
306
307
308
309







-
+

-
+

-
+







  lsm_db *pDb;                    /* Database handle */
  Level *pLevel;                  /* Worker snapshot Level being merged */
  MultiCursor *pCsr;              /* Cursor to read new segment contents from */
  int bFlush;                     /* True if this is an in-memory tree flush */
  Hierarchy hier;                 /* B-tree hierarchy under construction */
  Page *pPage;                    /* Current output page */
  int nWork;                      /* Number of calls to mergeWorkerNextPage() */
  Pgno *aGobble;                  /* Gobble point for each input segment */
  LsmPgno *aGobble;               /* Gobble point for each input segment */

  Pgno iIndirect;
  LsmPgno iIndirect;
  struct SavedPgno {
    Pgno iPgno;
    LsmPgno iPgno;
    int bStore;
  } aSave[2];
};

#ifdef LSM_DEBUG_EXPENSIVE
static int assertPointersOk(lsm_db *, Segment *, Segment *, int);
static int assertBtreeOk(lsm_db *, Segment *);
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

402
403
404
405
406
407
408
409
410

411
412
413
414
415
416
417
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
402
403
404
405
406
407
408
409

410
411
412
413
414
415
416
417







-
+










-
+







-
+




-
+


-
+








-
+







  aOut[3] = (u8)((nVal>>32) & 0xFF);
  aOut[4] = (u8)((nVal>>24) & 0xFF);
  aOut[5] = (u8)((nVal>>16) & 0xFF);
  aOut[6] = (u8)((nVal>> 8) & 0xFF);
  aOut[7] = (u8)((nVal    ) & 0xFF);
}

static int sortedBlobGrow(lsm_env *pEnv, Blob *pBlob, int nData){
static int sortedBlobGrow(lsm_env *pEnv, LsmBlob *pBlob, int nData){
  assert( pBlob->pEnv==pEnv || (pBlob->pEnv==0 && pBlob->pData==0) );
  if( pBlob->nAlloc<nData ){
    pBlob->pData = lsmReallocOrFree(pEnv, pBlob->pData, nData);
    if( !pBlob->pData ) return LSM_NOMEM_BKPT;
    pBlob->nAlloc = nData;
    pBlob->pEnv = pEnv;
  }
  return LSM_OK;
}

static int sortedBlobSet(lsm_env *pEnv, Blob *pBlob, void *pData, int nData){
static int sortedBlobSet(lsm_env *pEnv, LsmBlob *pBlob, void *pData, int nData){
  if( sortedBlobGrow(pEnv, pBlob, nData) ) return LSM_NOMEM;
  memcpy(pBlob->pData, pData, nData);
  pBlob->nData = nData;
  return LSM_OK;
}

#if 0
static int sortedBlobCopy(Blob *pDest, Blob *pSrc){
static int sortedBlobCopy(LsmBlob *pDest, LsmBlob *pSrc){
  return sortedBlobSet(pDest, pSrc->pData, pSrc->nData);
}
#endif

static void sortedBlobFree(Blob *pBlob){
static void sortedBlobFree(LsmBlob *pBlob){
  assert( pBlob->pEnv || pBlob->pData==0 );
  if( pBlob->pData ) lsmFree(pBlob->pEnv, pBlob->pData);
  memset(pBlob, 0, sizeof(Blob));
  memset(pBlob, 0, sizeof(LsmBlob));
}

static int sortedReadData(
  Segment *pSeg,
  Page *pPg,
  int iOff,
  int nByte,
  void **ppData,
  Blob *pBlob
  LsmBlob *pBlob
){
  int rc = LSM_OK;
  int iEnd;
  int nData;
  int nCell;
  u8 *aData;

477
478
479
480
481
482
483
484
485


486
487
488
489
490
491
492
477
478
479
480
481
482
483


484
485
486
487
488
489
490
491
492







-
-
+
+







  return rc;
}

static int pageGetNRec(u8 *aData, int nData){
  return (int)lsmGetU16(&aData[SEGMENT_NRECORD_OFFSET(nData)]);
}

static Pgno pageGetPtr(u8 *aData, int nData){
  return (Pgno)lsmGetU64(&aData[SEGMENT_POINTER_OFFSET(nData)]);
static LsmPgno pageGetPtr(u8 *aData, int nData){
  return (LsmPgno)lsmGetU64(&aData[SEGMENT_POINTER_OFFSET(nData)]);
}

static int pageGetFlags(u8 *aData, int nData){
  return (int)lsmGetU16(&aData[SEGMENT_FLAGS_OFFSET(nData)]);
}

static u8 *pageGetCell(u8 *aData, int nData, int iCell){
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
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







-
-
+
+














-
+







  return pageGetNRec(aData, nData);
}

/*
** Return the decoded (possibly relative) pointer value stored in cell 
** iCell from page aData/nData.
*/
static Pgno pageGetRecordPtr(u8 *aData, int nData, int iCell){
  Pgno iRet;                      /* Return value */
static LsmPgno pageGetRecordPtr(u8 *aData, int nData, int iCell){
  LsmPgno iRet;                   /* Return value */
  u8 *aCell;                      /* Pointer to cell iCell */

  assert( iCell<pageGetNRec(aData, nData) && iCell>=0 );
  aCell = pageGetCell(aData, nData, iCell);
  lsmVarintGet64(&aCell[1], &iRet);
  return iRet;
}

static u8 *pageGetKey(
  Segment *pSeg,                  /* Segment pPg belongs to */
  Page *pPg,                      /* Page to read from */
  int iCell,                      /* Index of cell on page to read */
  int *piTopic,                   /* OUT: Topic associated with this key */
  int *pnKey,                     /* OUT: Size of key in bytes */
  Blob *pBlob                     /* If required, use this for dynamic memory */
  LsmBlob *pBlob                  /* If required, use this for dynamic memory */
){
  u8 *pKey;
  int nDummy;
  int eType;
  u8 *aData;
  int nData;

550
551
552
553
554
555
556
557

558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573


574
575
576
577
578
579
580
550
551
552
553
554
555
556

557
558
559
560
561
562
563
564
565
566
567
568
569
570
571


572
573
574
575
576
577
578
579
580







-
+














-
-
+
+








static int pageGetKeyCopy(
  lsm_env *pEnv,                  /* Environment handle */
  Segment *pSeg,                  /* Segment pPg belongs to */
  Page *pPg,                      /* Page to read from */
  int iCell,                      /* Index of cell on page to read */
  int *piTopic,                   /* OUT: Topic associated with this key */
  Blob *pBlob                     /* If required, use this for dynamic memory */
  LsmBlob *pBlob                  /* If required, use this for dynamic memory */
){
  int rc = LSM_OK;
  int nKey;
  u8 *aKey;

  aKey = pageGetKey(pSeg, pPg, iCell, piTopic, &nKey, pBlob);
  assert( (void *)aKey!=pBlob->pData || nKey==pBlob->nData );
  if( (void *)aKey!=pBlob->pData ){
    rc = sortedBlobSet(pEnv, pBlob, aKey, nKey);
  }

  return rc;
}

static Pgno pageGetBtreeRef(Page *pPg, int iKey){
  Pgno iRef;
static LsmPgno pageGetBtreeRef(Page *pPg, int iKey){
  LsmPgno iRef;
  u8 *aData;
  int nData;
  u8 *aCell;

  aData = fsPageData(pPg, &nData);
  aCell = pageGetCell(aData, nData, iKey);
  assert( aCell[0]==0 );
588
589
590
591
592
593
594
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
588
589
590
591
592
593
594

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







-
+



-
+
















-
+







#define GETVARINT64(a, i) (((i)=((u8*)(a))[0])<=240?1:lsmVarintGet64((a), &(i)))
#define GETVARINT32(a, i) (((i)=((u8*)(a))[0])<=240?1:lsmVarintGet32((a), &(i)))

static int pageGetBtreeKey(
  Segment *pSeg,                  /* Segment page pPg belongs to */
  Page *pPg,
  int iKey, 
  Pgno *piPtr, 
  LsmPgno *piPtr, 
  int *piTopic, 
  void **ppKey,
  int *pnKey,
  Blob *pBlob
  LsmBlob *pBlob
){
  u8 *aData;
  int nData;
  u8 *aCell;
  int eType;

  aData = fsPageData(pPg, &nData);
  assert( SEGMENT_BTREE_FLAG & pageGetFlags(aData, nData) );
  assert( iKey>=0 && iKey<pageGetNRec(aData, nData) );

  aCell = pageGetCell(aData, nData, iKey);
  eType = *aCell++;
  aCell += GETVARINT64(aCell, *piPtr);

  if( eType==0 ){
    int rc;
    Pgno iRef;                  /* Page number of referenced page */
    LsmPgno iRef;               /* Page number of referenced page */
    Page *pRef;
    aCell += GETVARINT64(aCell, iRef);
    rc = lsmFsDbPageGet(lsmPageFS(pPg), pSeg, iRef, &pRef);
    if( rc!=LSM_OK ) return rc;
    pageGetKeyCopy(lsmPageEnv(pPg), pSeg, pRef, 0, &eType, pBlob);
    lsmFsPageRelease(pRef);
    *ppKey = pBlob->pData;
634
635
636
637
638
639
640
641

642
643
644
645
646
647
648
634
635
636
637
638
639
640

641
642
643
644
645
646
647
648







-
+







static int btreeCursorLoadKey(BtreeCursor *pCsr){
  int rc = LSM_OK;
  if( pCsr->iPg<0 ){
    pCsr->pKey = 0;
    pCsr->nKey = 0;
    pCsr->eType = 0;
  }else{
    Pgno dummy;
    LsmPgno dummy;
    int iPg = pCsr->iPg;
    int iCell = pCsr->aPg[iPg].iCell;
    while( iCell<0 && (--iPg)>=0 ){
      iCell = pCsr->aPg[iPg].iCell-1;
    }
    if( iPg<0 || iCell<0 ) return LSM_CORRUPT_BKPT;

679
680
681
682
683
684
685
686

687
688
689
690
691
692
693
679
680
681
682
683
684
685

686
687
688
689
690
691
692
693







-
+







  assert( pCsr->iPg==pCsr->nDepth-1 );

  aData = fsPageData(pPg->pPage, &nData);
  nCell = pageGetNRec(aData, nData);
  assert( pPg->iCell<=nCell );
  pPg->iCell++;
  if( pPg->iCell==nCell ){
    Pgno iLoad;
    LsmPgno iLoad;

    /* Up to parent. */
    lsmFsPageRelease(pPg->pPage);
    pPg->pPage = 0;
    pCsr->iPg--;
    while( pCsr->iPg>=0 ){
      pPg = &pCsr->aPg[pCsr->iPg];
838
839
840
841
842
843
844
845

846
847
848
849
850
851
852
838
839
840
841
842
843
844

845
846
847
848
849
850
851
852







-
+







  MergeInput *p
){
  int rc = LSM_OK;

  if( p->iPg ){
    lsm_env *pEnv = lsmFsEnv(pCsr->pFS);
    int iCell;                    /* Current cell number on leaf page */
    Pgno iLeaf;                   /* Page number of current leaf page */
    LsmPgno iLeaf;                /* Page number of current leaf page */
    int nDepth;                   /* Depth of b-tree structure */
    Segment *pSeg = pCsr->pSeg;

    /* Decode the MergeInput structure */
    iLeaf = p->iPg;
    nDepth = (p->iCell & 0x00FF);
    iCell = (p->iCell >> 8) - 1;
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
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







-
+
















-
+







      pCsr->nDepth = nDepth;
      pCsr->aPg[pCsr->iPg].iCell = iCell;
      rc = lsmFsDbPageGet(pCsr->pFS, pSeg, iLeaf, pp);
    }

    /* Populate any other aPg[] array entries */
    if( rc==LSM_OK && nDepth>1 ){
      Blob blob = {0,0,0};
      LsmBlob blob = {0,0,0};
      void *pSeek;
      int nSeek;
      int iTopicSeek;
      int iPg = 0;
      int iLoad = (int)pSeg->iRoot;
      Page *pPg = pCsr->aPg[nDepth-1].pPage;
 
      if( pageObjGetNRec(pPg)==0 ){
        /* This can happen when pPg is the right-most leaf in the b-tree.
        ** In this case, set the iTopicSeek/pSeek/nSeek key to a value
        ** greater than any real key.  */
        assert( iCell==-1 );
        iTopicSeek = 1000;
        pSeek = 0;
        nSeek = 0;
      }else{
        Pgno dummy;
        LsmPgno dummy;
        rc = pageGetBtreeKey(pSeg, pPg,
            0, &dummy, &iTopicSeek, &pSeek, &nSeek, &pCsr->blob
        );
      }

      do {
        Page *pPg2;
908
909
910
911
912
913
914
915

916
917
918
919
920
921
922
908
909
910
911
912
913
914

915
916
917
918
919
920
921
922







-
+







          iMax = iCell2-1;
          iMin = 0;

          while( iMax>=iMin ){
            int iTry = (iMin+iMax)/2;
            void *pKey; int nKey;         /* Key for cell iTry */
            int iTopic;                   /* Topic for key pKeyT/nKeyT */
            Pgno iPtr;                    /* Pointer for cell iTry */
            LsmPgno iPtr;                 /* Pointer for cell iTry */
            int res;                      /* (pSeek - pKeyT) */

            rc = pageGetBtreeKey(
                pSeg, pPg2, iTry, &iPtr, &iTopic, &pKey, &nKey, &blob
            );
            if( rc!=LSM_OK ) break;

951
952
953
954
955
956
957
958

959
960
961
962
963
964
965
951
952
953
954
955
956
957

958
959
960
961
962
963
964
965







-
+







      u8 *aData;
      int nData;

      pBtreePg = &pCsr->aPg[pCsr->iPg];
      aData = fsPageData(pBtreePg->pPage, &nData);
      pCsr->iPtr = btreeCursorPtr(aData, nData, pBtreePg->iCell+1);
      if( pBtreePg->iCell<0 ){
        Pgno dummy;
        LsmPgno dummy;
        int i;
        for(i=pCsr->iPg-1; i>=0; i--){
          if( pCsr->aPg[i].iCell>0 ) break;
        }
        assert( i>=0 );
        rc = pageGetBtreeKey(pSeg,
            pCsr->aPg[i].pPage, pCsr->aPg[i].iCell-1,
1026
1027
1028
1029
1030
1031
1032
1033

1034
1035
1036
1037
1038
1039
1040
1026
1027
1028
1029
1030
1031
1032

1033
1034
1035
1036
1037
1038
1039
1040







-
+







}

static int segmentPtrReadData(
  SegmentPtr *pPtr,
  int iOff,
  int nByte,
  void **ppData,
  Blob *pBlob
  LsmBlob *pBlob
){
  return sortedReadData(pPtr->pSeg, pPtr->pPg, iOff, nByte, ppData, pBlob);
}

static int segmentPtrNextPage(
  SegmentPtr *pPtr,              /* Load page into this SegmentPtr object */
  int eDir                       /* +1 for next(), -1 for prev() */
1119
1120
1121
1122
1123
1124
1125
1126

1127
1128
1129
1130
1131
1132
1133
1134

1135
1136
1137
1138
1139
1140
1141
1119
1120
1121
1122
1123
1124
1125

1126
1127
1128
1129
1130
1131
1132
1133

1134
1135
1136
1137
1138
1139
1140
1141







-
+







-
+








  pSeg = sortedSplitkeySegment(pLevel);
  if( rc==LSM_OK ){
    rc = lsmFsDbPageGet(pDb->pFS, pSeg, pMerge->splitkey.iPg, &pPg);
  }
  if( rc==LSM_OK ){
    int iTopic;
    Blob blob = {0, 0, 0, 0};
    LsmBlob blob = {0, 0, 0, 0};
    u8 *aData;
    int nData;
  
    aData = lsmFsPageData(pPg, &nData);
    if( pageGetFlags(aData, nData) & SEGMENT_BTREE_FLAG ){
      void *pKey;
      int nKey;
      Pgno dummy;
      LsmPgno dummy;
      rc = pageGetBtreeKey(pSeg,
          pPg, pMerge->splitkey.iCell, &dummy, &iTopic, &pKey, &nKey, &blob
      );
      if( rc==LSM_OK && blob.pData!=pKey ){
        rc = sortedBlobSet(pEnv, &blob, pKey, nKey);
      }
    }else{
1338
1339
1340
1341
1342
1343
1344
1345

1346
1347
1348
1349
1350
1351
1352
1338
1339
1340
1341
1342
1343
1344

1345
1346
1347
1348
1349
1350
1351
1352







-
+







*/
static int assertKeyLocation(
  MultiCursor *pCsr, 
  SegmentPtr *pPtr, 
  void *pKey, int nKey
){
  lsm_env *pEnv = lsmFsEnv(pCsr->pDb->pFS);
  Blob blob = {0, 0, 0};
  LsmBlob blob = {0, 0, 0};
  int eDir;
  int iTopic = 0;                 /* TODO: Fix me */

  for(eDir=-1; eDir<=1; eDir+=2){
    Page *pTest = pPtr->pPg;

    lsmFsPageRef(pTest);
1484
1485
1486
1487
1488
1489
1490
1491

1492
1493
1494
1495
1496
1497
1498
1484
1485
1486
1487
1488
1489
1490

1491
1492
1493
1494
1495
1496
1497
1498







-
+







  return rc;
}

static int ptrFwdPointer(
  Page *pPage,
  int iCell,
  Segment *pSeg,
  Pgno *piPtr,
  LsmPgno *piPtr,
  int *pbFound
){
  Page *pPg = pPage;
  int iFirst = iCell;
  int rc = LSM_OK;

  do {
1569
1570
1571
1572
1573
1574
1575
1576

1577
1578
1579
1580
1581
1582
1583

1584
1585
1586
1587
1588
1589
1590
1569
1570
1571
1572
1573
1574
1575

1576
1577
1578
1579
1580
1581
1582

1583
1584
1585
1586
1587
1588
1589
1590







-
+






-
+







**   much better if the multi-cursor could do this lazily - only seek to the
**   level (N+1) page after the user has moved the cursor on level N passed
**   the big range-delete.
*/
static int segmentPtrFwdPointer(
  MultiCursor *pCsr,              /* Multi-cursor pPtr belongs to */
  SegmentPtr *pPtr,               /* Segment-pointer to extract FC ptr from */
  Pgno *piPtr                     /* OUT: FC pointer value */
  LsmPgno *piPtr                  /* OUT: FC pointer value */
){
  Level *pLvl = pPtr->pLevel;
  Level *pNext = pLvl->pNext;
  Page *pPg = pPtr->pPg;
  int rc;
  int bFound;
  Pgno iOut = 0;
  LsmPgno iOut = 0;

  if( pPtr->pSeg==&pLvl->lhs || pPtr->pSeg==&pLvl->aRhs[pLvl->nRight-1] ){
    if( pNext==0 
        || (pNext->nRight==0 && pNext->lhs.iRoot)
        || (pNext->nRight!=0 && pNext->aRhs[0].iRoot)
      ){
      /* Do nothing. The pointer will not be used anyway. */
1637
1638
1639
1640
1641
1642
1643
1644

1645
1646
1647
1648
1649
1650
1651
1637
1638
1639
1640
1641
1642
1643

1644
1645
1646
1647
1648
1649
1650
1651







-
+







  int *pbStop
){
  int (*xCmp)(void *, int, void *, int) = pCsr->pDb->xCmp;
  int res = 0;                        /* Result of comparison operation */
  int rc = LSM_OK;
  int iMin;
  int iMax;
  Pgno iPtrOut = 0;
  LsmPgno iPtrOut = 0;

  /* If the current page contains an oversized entry, then there are no
  ** pointers to one or more of the subsequent pages in the sorted run.
  ** The following call ensures that the segment-ptr points to the correct 
  ** page in this case.  */
  rc = segmentPtrSearchOversized(pCsr, pPtr, iTopic, pKey, nKey);
  iPtrOut = pPtr->iPtr;
1764
1765
1766
1767
1768
1769
1770
1771

1772
1773
1774
1775
1776
1777
1778

1779
1780
1781
1782

1783
1784
1785
1786
1787
1788
1789
1764
1765
1766
1767
1768
1769
1770

1771
1772
1773
1774
1775
1776
1777

1778
1779
1780
1781

1782
1783
1784
1785
1786
1787
1788
1789







-
+






-
+



-
+







}

static int seekInBtree(
  MultiCursor *pCsr,              /* Multi-cursor object */
  Segment *pSeg,                  /* Seek within this segment */
  int iTopic,
  void *pKey, int nKey,           /* Key to seek to */
  Pgno *aPg,                      /* OUT: Page numbers */
  LsmPgno *aPg,                   /* OUT: Page numbers */
  Page **ppPg                     /* OUT: Leaf (sorted-run) page reference */
){
  int i = 0;
  int rc;
  int iPg;
  Page *pPg = 0;
  Blob blob = {0, 0, 0};
  LsmBlob blob = {0, 0, 0};

  iPg = (int)pSeg->iRoot;
  do {
    Pgno *piFirst = 0;
    LsmPgno *piFirst = 0;
    if( aPg ){
      aPg[i++] = iPg;
      piFirst = &aPg[i];
    }

    rc = lsmFsDbPageGet(pCsr->pDb->pFS, pSeg, iPg, &pPg);
    assert( rc==LSM_OK || pPg==0 );
1804
1805
1806
1807
1808
1809
1810
1811

1812
1813
1814
1815
1816
1817
1818
1804
1805
1806
1807
1808
1809
1810

1811
1812
1813
1814
1815
1816
1817
1818







-
+








      iMin = 0;
      iMax = nRec-1;
      while( iMax>=iMin ){
        int iTry = (iMin+iMax)/2;
        void *pKeyT; int nKeyT;       /* Key for cell iTry */
        int iTopicT;                  /* Topic for key pKeyT/nKeyT */
        Pgno iPtr;                    /* Pointer associated with cell iTry */
        LsmPgno iPtr;                 /* Pointer associated with cell iTry */
        int res;                      /* (pKey - pKeyT) */

        rc = pageGetBtreeKey(
            pSeg, pPg, iTry, &iPtr, &iTopicT, &pKeyT, &nKeyT, &blob
        );
        if( rc!=LSM_OK ) break;
        if( piFirst && pKeyT==blob.pData ){
1895
1896
1897
1898
1899
1900
1901
1902

1903
1904
1905
1906
1907
1908
1909
1895
1896
1897
1898
1899
1900
1901

1902
1903
1904
1905
1906
1907
1908
1909







-
+







*/
static int seekInLevel(
  MultiCursor *pCsr,              /* Sorted cursor object to seek */
  SegmentPtr *aPtr,               /* Pointer to array of (nRhs+1) SPs */
  int eSeek,                      /* Search bias - see above */
  int iTopic,                     /* Key topic to search for */
  void *pKey, int nKey,           /* Key to search for */
  Pgno *piPgno,                   /* IN/OUT: fraction cascade pointer (or 0) */
  LsmPgno *piPgno,                /* IN/OUT: fraction cascade pointer (or 0) */
  int *pbStop                     /* OUT: See above */
){
  Level *pLvl = aPtr[0].pLevel;   /* Level to seek within */
  int rc = LSM_OK;                /* Return code */
  int iOut = 0;                   /* Pointer to return to caller */
  int res = -1;                   /* Result of xCmp(pKey, split) */
  int nRhs = pLvl->nRight;        /* Number of right-hand-side segments */
3051
3052
3053
3054
3055
3056
3057
3058

3059
3060
3061
3062
3063
3064
3065
3051
3052
3053
3054
3055
3056
3057

3058
3059
3060
3061
3062
3063
3064
3065







-
+







  void *pKey, int nKey, 
  int eSeek
){
  int eESeek = eSeek;             /* Effective eSeek parameter */
  int bStop = 0;                  /* Set to true to halt search operation */
  int rc = LSM_OK;                /* Return code */
  int iPtr = 0;                   /* Used to iterate through pCsr->aPtr[] */
  Pgno iPgno = 0;                 /* FC pointer value */
  LsmPgno iPgno = 0;              /* FC pointer value */

  assert( pCsr->apTreeCsr[0]==0 || iTopic==0 );
  assert( pCsr->apTreeCsr[1]==0 || iTopic==0 );

  if( eESeek==LSM_SEEK_LEFAST ) eESeek = LSM_SEEK_LE;

  assert( eESeek==LSM_SEEK_EQ || eESeek==LSM_SEEK_LE || eESeek==LSM_SEEK_GE );
3533
3534
3535
3536
3537
3538
3539
3540

3541
3542
3543
3544
3545
3546
3547
3533
3534
3535
3536
3537
3538
3539

3540
3541
3542
3543
3544
3545
3546
3547







-
+







** differences are:
**
**   1. The record format is (usually, see below) as follows:
**
**         + Type byte (always SORTED_SEPARATOR or SORTED_SYSTEM_SEPARATOR),
**         + Absolute pointer value (varint),
**         + Number of bytes in key (varint),
**         + Blob containing key data.
**         + LsmBlob containing key data.
**
**   2. All pointer values are stored as absolute values (not offsets 
**      relative to the footer pointer value).
**
**   3. Each pointer that is part of a record points to a page that 
**      contains keys smaller than the records key (note: not "equal to or
**      smaller than - smaller than").
3567
3568
3569
3570
3571
3572
3573
3574
3575


3576
3577
3578
3579
3580
3581
3582
3567
3568
3569
3570
3571
3572
3573


3574
3575
3576
3577
3578
3579
3580
3581
3582







-
-
+
+







**
** See function seekInBtree() for the code that traverses b-tree pages.
*/

static int mergeWorkerBtreeWrite(
  MergeWorker *pMW,
  u8 eType,
  Pgno iPtr,
  Pgno iKeyPg,
  LsmPgno iPtr,
  LsmPgno iKeyPg,
  void *pKey,
  int nKey
){
  Hierarchy *p = &pMW->hier;
  lsm_db *pDb = pMW->pDb;         /* Database handle */
  int rc = LSM_OK;                /* Return Code */
  int iLevel;                     /* Level of b-tree hierachy to write to */
3678
3679
3680
3681
3682
3683
3684
3685

3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706

3707
3708
3709
3710
3711
3712
3713
3678
3679
3680
3681
3682
3683
3684

3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705

3706
3707
3708
3709
3710
3711
3712
3713







-
+




















-
+








  return rc;
}

static int mergeWorkerBtreeIndirect(MergeWorker *pMW){
  int rc = LSM_OK;
  if( pMW->iIndirect ){
    Pgno iKeyPg = pMW->aSave[1].iPgno;
    LsmPgno iKeyPg = pMW->aSave[1].iPgno;
    rc = mergeWorkerBtreeWrite(pMW, 0, pMW->iIndirect, iKeyPg, 0, 0);
    pMW->iIndirect = 0;
  }
  return rc;
}

/*
** Append the database key (iTopic/pKey/nKey) to the b-tree under 
** construction. This key has not yet been written to a segment page.
** The pointer that will accompany the new key in the b-tree - that
** points to the completed segment page that contains keys smaller than
** (pKey/nKey) is currently stored in pMW->aSave[0].iPgno.
*/
static int mergeWorkerPushHierarchy(
  MergeWorker *pMW,               /* Merge worker object */
  int iTopic,                     /* Topic value for this key */
  void *pKey,                     /* Pointer to key buffer */
  int nKey                        /* Size of pKey buffer in bytes */
){
  int rc = LSM_OK;                /* Return Code */
  Pgno iPtr;                      /* Pointer value to accompany pKey/nKey */
  LsmPgno iPtr;                   /* Pointer value to accompany pKey/nKey */

  assert( pMW->aSave[0].bStore==0 );
  assert( pMW->aSave[1].bStore==0 );
  rc = mergeWorkerBtreeIndirect(pMW);

  /* Obtain the absolute pointer value to store along with the key in the
  ** page body. This pointer points to a page that contains keys that are
3730
3731
3732
3733
3734
3735
3736
3737

3738
3739
3740
3741
3742
3743
3744
3730
3731
3732
3733
3734
3735
3736

3737
3738
3739
3740
3741
3742
3743
3744







-
+







}

static int mergeWorkerFinishHierarchy(
  MergeWorker *pMW                /* Merge worker object */
){
  int i;                          /* Used to loop through apHier[] */
  int rc = LSM_OK;                /* Return code */
  Pgno iPtr;                      /* New right-hand-child pointer value */
  LsmPgno iPtr;                   /* New right-hand-child pointer value */

  iPtr = pMW->aSave[0].iPgno;
  for(i=0; i<pMW->hier.nHier && rc==LSM_OK; i++){
    Page *pPg = pMW->hier.apHier[i];
    int nData;                    /* Size of aData[] in bytes */
    u8 *aData;                    /* Page data for pPg */

3826
3827
3828
3829
3830
3831
3832
3833

3834
3835
3836
3837
3838
3839
3840
3826
3827
3828
3829
3830
3831
3832

3833
3834
3835
3836
3837
3838
3839
3840







-
+







** zero records. The flags field is cleared. The page footer pointer field
** is set to iFPtr.
**
** If successful, LSM_OK is returned. Otherwise, an error code.
*/
static int mergeWorkerNextPage(
  MergeWorker *pMW,               /* Merge worker object to append page to */
  Pgno iFPtr                      /* Pointer value for footer of new page */
  LsmPgno iFPtr                   /* Pointer value for footer of new page */
){
  int rc = LSM_OK;                /* Return code */
  Page *pNext = 0;                /* New page appended to run */
  lsm_db *pDb = pMW->pDb;         /* Database handle */

  rc = lsmFsSortedAppend(pDb->pFS, pDb->pWorker, pMW->pLevel, 0, &pNext);
  assert( rc || pMW->pLevel->lhs.iFirst>0 || pMW->pDb->compress.xCompress );
4214
4215
4216
4217
4218
4219
4220
4221

4222
4223
4224
4225
4226
4227
4228
4214
4215
4216
4217
4218
4219
4220

4221
4222
4223
4224
4225
4226
4227
4228







-
+








static int mergeWorkerStep(MergeWorker *pMW){
  lsm_db *pDb = pMW->pDb;       /* Database handle */
  MultiCursor *pCsr;            /* Cursor to read input data from */
  int rc = LSM_OK;              /* Return code */
  int eType;                    /* SORTED_SEPARATOR, WRITE or DELETE */
  void *pKey; int nKey;         /* Key */
  Pgno iPtr;
  LsmPgno iPtr;
  int iVal;

  pCsr = pMW->pCsr;

  /* Pull the next record out of the source cursor. */
  lsmMCursorKey(pCsr, &pKey, &nKey);
  eType = pCsr->eType;
4367
4368
4369
4370
4371
4372
4373
4374

4375
4376
4377
4378
4379
4380
4381
4367
4368
4369
4370
4371
4372
4373

4374
4375
4376
4377
4378
4379
4380
4381







-
+







      multiCursorIgnoreDelete(pCsr);
    }
  }

  if( rc!=LSM_OK ){
    lsmMCursorClose(pCsr, 0);
  }else{
    Pgno iLeftPtr = 0;
    LsmPgno iLeftPtr = 0;
    Merge merge;                  /* Merge object used to create new level */
    MergeWorker mergeworker;      /* MergeWorker object for the same purpose */

    memset(&merge, 0, sizeof(Merge));
    memset(&mergeworker, 0, sizeof(MergeWorker));

    pNew->pMerge = &merge;
4544
4545
4546
4547
4548
4549
4550
4551

4552
4553
4554
4555
4556
4557
4558
4544
4545
4546
4547
4548
4549
4550

4551
4552
4553
4554
4555
4556
4557
4558







-
+







  assert( pDb->pWorker );
  assert( pLevel->pMerge );
  assert( pLevel->nRight>0 );

  memset(pMW, 0, sizeof(MergeWorker));
  pMW->pDb = pDb;
  pMW->pLevel = pLevel;
  pMW->aGobble = lsmMallocZeroRc(pDb->pEnv, sizeof(Pgno) * pLevel->nRight, &rc);
  pMW->aGobble = lsmMallocZeroRc(pDb->pEnv, sizeof(LsmPgno)*pLevel->nRight,&rc);

  /* Create a multi-cursor to read the data to write to the new
  ** segment. The new segment contains:
  **
  **   1. Records from LHS of each of the nMerge levels being merged.
  **   2. Separators from either the last level being merged, or the
  **      separators attached to the LHS of the following level, or neither.
4626
4627
4628
4629
4630
4631
4632
4633

4634
4635
4636
4637
4638
4639
4640
4641
4642

4643
4644
4645
4646
4647
4648
4649
4626
4627
4628
4629
4630
4631
4632

4633
4634
4635
4636
4637
4638
4639
4640
4641

4642
4643
4644
4645
4646
4647
4648
4649







-
+








-
+







  lsm_db *pDb,                    /* Worker connection */
  MultiCursor *pCsr,              /* Multi-cursor being used for a merge */
  int iGobble                     /* pCsr->aPtr[] entry to operate on */
){
  int rc = LSM_OK;
  if( rtTopic(pCsr->eType)==0 ){
    Segment *pSeg = pCsr->aPtr[iGobble].pSeg;
    Pgno *aPg;
    LsmPgno *aPg;
    int nPg;

    /* Seek from the root of the b-tree to the segment leaf that may contain
    ** a key equal to the one multi-cursor currently points to. Record the
    ** page number of each b-tree page and the leaf. The segment may be
    ** gobbled up to (but not including) the first of these page numbers.
    */
    assert( pSeg->iRoot>0 );
    aPg = lsmMallocZeroRc(pDb->pEnv, sizeof(Pgno)*32, &rc);
    aPg = lsmMallocZeroRc(pDb->pEnv, sizeof(LsmPgno)*32, &rc);
    if( rc==LSM_OK ){
      rc = seekInBtree(pCsr, pSeg, 
          rtTopic(pCsr->eType), pCsr->key.pData, pCsr->key.nData, aPg, 0
      ); 
    }

    if( rc==LSM_OK ){
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471



5472
5473
5474
5475
5476
5477
5478
5462
5463
5464
5465
5466
5467
5468



5469
5470
5471
5472
5473
5474
5475
5476
5477
5478







-
-
-
+
+
+







/*
** Return a string representation of the segment passed as the only argument.
** Space for the returned string is allocated using lsmMalloc(), and should
** be freed by the caller using lsmFree().
*/
static char *segToString(lsm_env *pEnv, Segment *pSeg, int nMin){
  int nSize = pSeg->nSize;
  Pgno iRoot = pSeg->iRoot;
  Pgno iFirst = pSeg->iFirst;
  Pgno iLast = pSeg->iLastPg;
  LsmPgno iRoot = pSeg->iRoot;
  LsmPgno iFirst = pSeg->iFirst;
  LsmPgno iLast = pSeg->iLastPg;
  char *z;

  char *z1;
  char *z2;
  int nPad;

  z1 = lsmMallocPrintf(pEnv, "%d.%d", iFirst, iLast);
5523
5524
5525
5526
5527
5528
5529
5530

5531
5532
5533
5534
5535
5536
5537
5523
5524
5525
5526
5527
5528
5529

5530
5531
5532
5533
5534
5535
5536
5537







-
+







    aBuf[0] = '\0';
  }

  return i;
}

void sortedDumpPage(lsm_db *pDb, Segment *pRun, Page *pPg, int bVals){
  Blob blob = {0, 0, 0};         /* Blob used for keys */
  LsmBlob blob = {0, 0, 0};       /* LsmBlob used for keys */
  LsmString s;
  int i;

  int nRec;
  int iPtr;
  int flags;
  u8 *aData;
5559
5560
5561
5562
5563
5564
5565
5566

5567
5568
5569
5570
5571
5572
5573
5559
5560
5561
5562
5563
5564
5565

5566
5567
5568
5569
5570
5571
5572
5573







-
+








    aCell = pageGetCell(aData, nData, i);
    eType = *aCell++;
    assert( (flags & SEGMENT_BTREE_FLAG) || eType!=0 );
    aCell += lsmVarintGet32(aCell, &iPgPtr);

    if( eType==0 ){
      Pgno iRef;                  /* Page number of referenced page */
      LsmPgno iRef;               /* Page number of referenced page */
      aCell += lsmVarintGet64(aCell, &iRef);
      lsmFsDbPageGet(pDb->pFS, pRun, iRef, &pRef);
      aKey = pageGetKey(pRun, pRef, 0, &iTopic, &nKey, &blob);
    }else{
      aCell += lsmVarintGet32(aCell, &nKey);
      if( rtIsWrite(eType) ) aCell += lsmVarintGet32(aCell, &nVal);
      sortedReadData(0, pPg, (aCell-aData), nKey+nVal, (void **)&aKey, &blob);
5603
5604
5605
5606
5607
5608
5609
5610

5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628

5629
5630
5631
5632
5633
5634
5635
5603
5604
5605
5606
5607
5608
5609

5610
5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627

5628
5629
5630
5631
5632
5633
5634
5635







-
+

















-
+







  int bIndirect,                  /* True to follow indirect refs */
  Page *pPg,
  int iCell,
  int *peType,
  int *piPgPtr,
  u8 **paKey, int *pnKey,
  u8 **paVal, int *pnVal,
  Blob *pBlob
  LsmBlob *pBlob
){
  u8 *aData; int nData;           /* Page data */
  u8 *aKey; int nKey = 0;         /* Key */
  u8 *aVal = 0; int nVal = 0;     /* Value */
  int eType;
  int iPgPtr;
  Page *pRef = 0;                 /* Pointer to page iRef */
  u8 *aCell;

  aData = fsPageData(pPg, &nData);

  aCell = pageGetCell(aData, nData, iCell);
  eType = *aCell++;
  aCell += lsmVarintGet32(aCell, &iPgPtr);

  if( eType==0 ){
    int dummy;
    Pgno iRef;                  /* Page number of referenced page */
    LsmPgno iRef;                 /* Page number of referenced page */
    aCell += lsmVarintGet64(aCell, &iRef);
    if( bIndirect ){
      lsmFsDbPageGet(pDb->pFS, pSeg, iRef, &pRef);
      pageGetKeyCopy(pDb->pEnv, pSeg, pRef, 0, &dummy, pBlob);
      aKey = (u8 *)pBlob->pData;
      nKey = pBlob->nData;
      lsmFsPageRelease(pRef);
5667
5668
5669
5670
5671
5672
5673
5674

5675
5676
5677
5678
5679
5680
5681
5667
5668
5669
5670
5671
5672
5673

5674
5675
5676
5677
5678
5679
5680
5681







-
+







#define INFO_PAGE_DUMP_DATA     0x01
#define INFO_PAGE_DUMP_VALUES   0x02
#define INFO_PAGE_DUMP_HEX      0x04
#define INFO_PAGE_DUMP_INDIRECT 0x08

static int infoPageDump(
  lsm_db *pDb,                    /* Database handle */
  Pgno iPg,                       /* Page number of page to dump */
  LsmPgno iPg,                    /* Page number of page to dump */
  int flags,
  char **pzOut                    /* OUT: lsmMalloc'd string */
){
  int rc = LSM_OK;                /* Return code */
  Page *pPg = 0;                  /* Handle for page iPg */
  int i, j;                       /* Loop counters */
  const int perLine = 16;         /* Bytes per line in the raw hex dump */
5708
5709
5710
5711
5712
5713
5714
5715

5716
5717
5718
5719
5720
5721
5722
5708
5709
5710
5711
5712
5713
5714

5715
5716
5717
5718
5719
5720
5721
5722







-
+







  ** to pass a NULL in place of the segment pointer as the second argument
  ** to lsmFsDbPageGet() here.  */
  if( rc==LSM_OK ){
    rc = lsmFsDbPageGet(pDb->pFS, 0, iPg, &pPg);
  }

  if( rc==LSM_OK ){
    Blob blob = {0, 0, 0, 0};
    LsmBlob blob = {0, 0, 0, 0};
    int nKeyWidth = 0;
    LsmString str;
    int nRec;
    int iPtr;
    int flags2;
    int iCell;
    u8 *aData; int nData;         /* Page data and size thereof */
5743
5744
5745
5746
5747
5748
5749
5750

5751
5752
5753
5754
5755
5756
5757
5743
5744
5745
5746
5747
5748
5749

5750
5751
5752
5753
5754
5755
5756
5757







-
+







    if( bHex ) nKeyWidth = nKeyWidth * 2;

    for(iCell=0; iCell<nRec; iCell++){
      u8 *aKey; int nKey = 0;       /* Key */
      u8 *aVal; int nVal = 0;       /* Value */
      int iPgPtr;
      int eType;
      Pgno iAbsPtr;
      LsmPgno iAbsPtr;
      char zFlags[8];

      infoCellDump(pDb, pSeg, bIndirect, pPg, iCell, &eType, &iPgPtr,
          &aKey, &nKey, &aVal, &nVal, &blob
      );
      iAbsPtr = iPgPtr + ((flags2 & SEGMENT_BTREE_FLAG) ? 0 : iPtr);

5809
5810
5811
5812
5813
5814
5815
5816

5817
5818
5819
5820
5821
5822
5823
5809
5810
5811
5812
5813
5814
5815

5816
5817
5818
5819
5820
5821
5822
5823







-
+







  }

  return rc;
}

int lsmInfoPageDump(
  lsm_db *pDb,                    /* Database handle */
  Pgno iPg,                       /* Page number of page to dump */
  LsmPgno iPg,                    /* Page number of page to dump */
  int bHex,                       /* True to output key/value in hex form */
  char **pzOut                    /* OUT: lsmMalloc'd string */
){
  int flags = INFO_PAGE_DUMP_DATA | INFO_PAGE_DUMP_VALUES;
  if( bHex ) flags |= INFO_PAGE_DUMP_HEX;
  return infoPageDump(pDb, iPg, flags, pzOut);
}
5985
5986
5987
5988
5989
5990
5991
5992
5993


5994
5995
5996
5997
5998
5999
6000
5985
5986
5987
5988
5989
5990
5991


5992
5993
5994
5995
5996
5997
5998
5999
6000







-
-
+
+







  iHdr = SEGMENT_EOF(nOrig, nEntry);
  memmove(&aData[iHdr + (nData-nOrig)], &aData[iHdr], nOrig-iHdr);
}

#ifdef LSM_DEBUG_EXPENSIVE
static void assertRunInOrder(lsm_db *pDb, Segment *pSeg){
  Page *pPg = 0;
  Blob blob1 = {0, 0, 0, 0};
  Blob blob2 = {0, 0, 0, 0};
  LsmBlob blob1 = {0, 0, 0, 0};
  LsmBlob blob2 = {0, 0, 0, 0};

  lsmFsDbPageGet(pDb->pFS, pSeg, pSeg->iFirst, &pPg);
  while( pPg ){
    u8 *aData; int nData;
    Page *pNext;

    aData = lsmFsPageData(pPg, &nData);
6048
6049
6050
6051
6052
6053
6054
6055

6056
6057
6058
6059
6060
6061
6062
6048
6049
6050
6051
6052
6053
6054

6055
6056
6057
6058
6059
6060
6061
6062







-
+







  Segment *pOne,                  /* Segment containing pointers */
  Segment *pTwo,                  /* Segment containing pointer targets */
  int bRhs                        /* True if pTwo may have been Gobble()d */
){
  int rc = LSM_OK;                /* Error code */
  SegmentPtr ptr1;                /* Iterates through pOne */
  SegmentPtr ptr2;                /* Iterates through pTwo */
  Pgno iPrev;
  LsmPgno iPrev;

  assert( pOne && pTwo );

  memset(&ptr1, 0, sizeof(ptr1));
  memset(&ptr2, 0, sizeof(ptr1));
  ptr1.pSeg = pOne;
  ptr2.pSeg = pTwo;
6071
6072
6073
6074
6075
6076
6077
6078

6079
6080
6081
6082
6083
6084
6085
6071
6072
6073
6074
6075
6076
6077

6078
6079
6080
6081
6082
6083
6084
6085







-
+







  }

  if( rc==LSM_OK && ptr1.nCell>0 ){
    rc = segmentPtrLoadCell(&ptr1, 0);
  }
      
  while( rc==LSM_OK && ptr2.pPg ){
    Pgno iThis;
    LsmPgno iThis;

    /* Advance to the next page of segment pTwo that contains at least
    ** one cell. Break out of the loop if the iterator reaches EOF.  */
    do{
      rc = segmentPtrNextPage(&ptr2, 1);
      assert( rc==LSM_OK );
    }while( rc==LSM_OK && ptr2.pPg && ptr2.nCell==0 );
6133
6134
6135
6136
6137
6138
6139
6140

6141
6142
6143
6144
6145
6146
6147
6133
6134
6135
6136
6137
6138
6139

6140
6141
6142
6143
6144
6145
6146
6147







-
+







*/
static int assertBtreeOk(
  lsm_db *pDb,
  Segment *pSeg
){
  int rc = LSM_OK;                /* Return code */
  if( pSeg->iRoot ){
    Blob blob = {0, 0, 0};        /* Buffer used to cache overflow keys */
    LsmBlob blob = {0, 0, 0};     /* Buffer used to cache overflow keys */
    FileSystem *pFS = pDb->pFS;   /* File system to read from */
    Page *pPg = 0;                /* Main run page */
    BtreeCursor *pCsr = 0;        /* Btree cursor */

    rc = btreeCursorNew(pDb, pSeg, &pCsr);
    if( rc==LSM_OK ){
      rc = btreeCursorFirst(pCsr);
Added ext/lsm1/tool/mklsm1c.tcl.
























































































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
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
85
86
87
88
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
#!/bin/sh
# restart with tclsh \
exec tclsh "$0" "$@"

set srcdir [file dirname [file dirname [info script]]]
set G(src) [string map [list %dir% $srcdir] {
  %dir%/lsm.h
  %dir%/lsmInt.h
  %dir%/lsm_vtab.c
  %dir%/lsm_ckpt.c
  %dir%/lsm_file.c
  %dir%/lsm_log.c
  %dir%/lsm_main.c
  %dir%/lsm_mem.c
  %dir%/lsm_mutex.c
  %dir%/lsm_shared.c
  %dir%/lsm_sorted.c
  %dir%/lsm_str.c
  %dir%/lsm_tree.c
  %dir%/lsm_unix.c
  %dir%/lsm_varint.c
  %dir%/lsm_win32.c
}]

set G(hdr) {

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

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

}

set G(footer) {
    
#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_LSM1) */
}

#-------------------------------------------------------------------------
# Read and return the entire contents of text file $zFile from disk.
#
proc readfile {zFile} {
  set fd [open $zFile]
  set data [read $fd]
  close $fd
  return $data
}

proc lsm1c_init {zOut} {
  global G
  set G(fd) stdout
  set G(fd) [open $zOut w]

  puts -nonewline $G(fd) $G(hdr)
}

proc lsm1c_printfile {zIn} {
  global G
  set data [readfile $zIn]
  set zTail [file tail $zIn]
  puts $G(fd) "#line 1 \"$zTail\""

  foreach line [split $data "\n"] {
    if {[regexp {^# *include.*lsm} $line]} {
      set line "/* $line */"
    } elseif { [regexp {^(const )?[a-zA-Z][a-zA-Z0-9]* [*]?lsm[^_]} $line] } {
      set line "static $line"
    }
    puts $G(fd) $line
  }
}

proc lsm1c_close {} {
  global G
  puts -nonewline $G(fd) $G(footer)
  if {$G(fd)!="stdout"} {
    close $G(fd)
  }
}


lsm1c_init lsm1.c
foreach f $G(src) { lsm1c_printfile $f }
lsm1c_close
Changes to ext/misc/rot13.c.
43
44
45
46
47
48
49
50

51
52

53
54
55
56
57
58
59
60

61
62
63
64
65
66
67
43
44
45
46
47
48
49

50
51

52
53
54
55
56
57
58
59

60
61
62
63
64
65
66
67







-
+

-
+







-
+







  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  const unsigned char *zIn;
  int nIn;
  unsigned char *zOut;
  char *zToFree = 0;
  unsigned char *zToFree = 0;
  int i;
  char zTemp[100];
  unsigned char zTemp[100];
  assert( argc==1 );
  if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
  zIn = (const unsigned char*)sqlite3_value_text(argv[0]);
  nIn = sqlite3_value_bytes(argv[0]);
  if( nIn<sizeof(zTemp)-1 ){
    zOut = zTemp;
  }else{
    zOut = zToFree = sqlite3_malloc( nIn+1 );
    zOut = zToFree = (unsigned char*)sqlite3_malloc64( nIn+1 );
    if( zOut==0 ){
      sqlite3_result_error_nomem(context);
      return;
    }
  }
  for(i=0; i<nIn; i++) zOut[i] = rot13(zIn[i]);
  zOut[i] = 0;
Changes to main.mk.
259
260
261
262
263
264
265


















266
267
268
269
270
271
272
259
260
261
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







+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+







   fts5parse.c \
   $(TOP)/ext/fts5/fts5_storage.c \
   $(TOP)/ext/fts5/fts5_tokenize.c \
   $(TOP)/ext/fts5/fts5_unicode2.c \
   $(TOP)/ext/fts5/fts5_varint.c \
   $(TOP)/ext/fts5/fts5_vocab.c  \

LSM1_SRC = \
   $(TOP)/ext/lsm1/lsm.h \
   $(TOP)/ext/lsm1/lsmInt.h \
   $(TOP)/ext/lsm1/lsm_ckpt.c \
   $(TOP)/ext/lsm1/lsm_file.c \
   $(TOP)/ext/lsm1/lsm_log.c \
   $(TOP)/ext/lsm1/lsm_main.c \
   $(TOP)/ext/lsm1/lsm_mem.c \
   $(TOP)/ext/lsm1/lsm_mutex.c \
   $(TOP)/ext/lsm1/lsm_shared.c \
   $(TOP)/ext/lsm1/lsm_sorted.c \
   $(TOP)/ext/lsm1/lsm_str.c \
   $(TOP)/ext/lsm1/lsm_tree.c \
   $(TOP)/ext/lsm1/lsm_unix.c \
   $(TOP)/ext/lsm1/lsm_varint.c \
   $(TOP)/ext/lsm1/lsm_vtab.c \
   $(TOP)/ext/lsm1/lsm_win32.c


# Generated source code files
#
SRC += \
  keywordhash.h \
  opcodes.c \
  opcodes.h \
762
763
764
765
766
767
768




769
770
771
772
773
774
775
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797







+
+
+
+








fts5parse.h: fts5parse.c

fts5.c: $(FTS5_SRC) $(FTS5_HDR)
	tclsh $(TOP)/ext/fts5/tool/mkfts5c.tcl
	cp $(TOP)/ext/fts5/fts5.h .

lsm1.c: $(LSM1_SRC)
	tclsh $(TOP)/ext/lsm1/tool/mklsm1c.tcl
	cp $(TOP)/ext/lsm1/lsm.h .

userauth.o:	$(TOP)/ext/userauth/userauth.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/userauth/userauth.c

sqlite3session.o:	$(TOP)/ext/session/sqlite3session.c $(HDR) $(EXTHDR)
	$(TCCX) -DSQLITE_CORE -c $(TOP)/ext/session/sqlite3session.c

sqlite3rbu.o:	$(TOP)/ext/rbu/sqlite3rbu.c $(HDR) $(EXTHDR)
1015
1016
1017
1018
1019
1020
1021

1037
1038
1039
1040
1041
1042
1043
1044







+
	rm -f sqlite3_analyzer sqlite3_analyzer.exe sqlite3_analyzer.c
	rm -f sqlite-*-output.vsix
	rm -f mptester mptester.exe
	rm -f fuzzershell fuzzershell.exe
	rm -f fuzzcheck fuzzcheck.exe
	rm -f sqldiff sqldiff.exe
	rm -f fts5.* fts5parse.*
	rm -f lsm.h lsm1.c
Changes to src/build.c.
4360
4361
4362
4363
4364
4365
4366












4367
4368
4369
4370
4371
4372
4373
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385







+
+
+
+
+
+
+
+
+
+
+
+







    for(i=0; i<nCol; i++){
      const char *zColl = pIdx->azColl[i];
      pKey->aColl[i] = zColl==sqlite3StrBINARY ? 0 :
                        sqlite3LocateCollSeq(pParse, zColl);
      pKey->aSortOrder[i] = pIdx->aSortOrder[i];
    }
    if( pParse->nErr ){
      assert( pParse->rc==SQLITE_ERROR_MISSING_COLLSEQ );
      if( pIdx->bNoQuery==0 ){
        /* Deactivate the index because it contains an unknown collating
        ** sequence.  The only way to reactive the index is to reload the
        ** schema.  Adding the missing collating sequence later does not
        ** reactive the index.  The application had the chance to register
        ** the missing index using the collation-needed callback.  For
        ** simplicity, SQLite will not give the application a second chance.
        */
        pIdx->bNoQuery = 1;
        pParse->rc = SQLITE_ERROR_RETRY;
      }
      sqlite3KeyInfoUnref(pKey);
      pKey = 0;
    }
  }
  return pKey;
}

Changes to src/callback.c.
101
102
103
104
105
106
107

108
109
110
111
112
113
114
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115







+







  }
  if( p && !p->xCmp && synthCollSeq(db, p) ){
    p = 0;
  }
  assert( !p || p->xCmp );
  if( p==0 ){
    sqlite3ErrorMsg(pParse, "no such collation sequence: %s", zName);
    pParse->rc = SQLITE_ERROR_MISSING_COLLSEQ;
  }
  return p;
}

/*
** This routine is called on a collation sequence before it is used to
** check that it is defined. An undefined collation sequence exists when
Changes to src/date.c.
35
36
37
38
39
40
41
42

43
44
45
46
47
48
49
35
36
37
38
39
40
41

42
43
44
45
46
47
48
49







-
+







** dates afterwards, depending on locale.  Beware of this difference.
**
** The conversion algorithms are implemented based on descriptions
** in the following text:
**
**      Jean Meeus
**      Astronomical Algorithms, 2nd Edition, 1998
**      ISBM 0-943396-61-1
**      ISBN 0-943396-61-1
**      Willmann-Bell, Inc
**      Richmond, Virginia (USA)
*/
#include "sqliteInt.h"
#include <stdlib.h>
#include <assert.h>
#include <time.h>
Changes to src/delete.c.
279
280
281
282
283
284
285
286
287
288
289
290

291
292
293
294
295
296
297
279
280
281
282
283
284
285

286
287
288
289
290
291
292
293
294
295
296
297







-




+








  /* Figure out if we have any triggers and if the table being
  ** deleted from is a view
  */
#ifndef SQLITE_OMIT_TRIGGER
  pTrigger = sqlite3TriggersExist(pParse, pTab, TK_DELETE, 0, 0);
  isView = pTab->pSelect!=0;
  bComplex = pTrigger || sqlite3FkRequired(pParse, pTab, 0, 0);
#else
# define pTrigger 0
# define isView 0
#endif
  bComplex = pTrigger || sqlite3FkRequired(pParse, pTab, 0, 0);
#ifdef SQLITE_OMIT_VIEW
# undef isView
# define isView 0
#endif

#ifdef SQLITE_ENABLE_UPDATE_DELETE_LIMIT
  if( !isView ){
Changes to src/main.c.
18
19
20
21
22
23
24
25

26
27
28
29
30
31
32
18
19
20
21
22
23
24

25
26
27
28
29
30
31
32







-
+








#ifdef SQLITE_ENABLE_FTS3
# include "fts3.h"
#endif
#ifdef SQLITE_ENABLE_RTREE
# include "rtree.h"
#endif
#ifdef SQLITE_ENABLE_ICU
#if defined(SQLITE_ENABLE_ICU) || defined(SQLITE_ENABLE_ICU_COLLATIONS)
# include "sqliteicu.h"
#endif
#ifdef SQLITE_ENABLE_JSON1
int sqlite3Json1Init(sqlite3*);
#endif
#ifdef SQLITE_ENABLE_STMTVTAB
int sqlite3StmtVtabInit(sqlite3*);
3046
3047
3048
3049
3050
3051
3052
3053

3054
3055
3056
3057
3058
3059
3060
3046
3047
3048
3049
3050
3051
3052

3053
3054
3055
3056
3057
3058
3059
3060







-
+








#ifdef SQLITE_ENABLE_FTS3 /* automatically defined by SQLITE_ENABLE_FTS4 */
  if( !db->mallocFailed && rc==SQLITE_OK ){
    rc = sqlite3Fts3Init(db);
  }
#endif

#ifdef SQLITE_ENABLE_ICU
#if defined(SQLITE_ENABLE_ICU) || defined(SQLITE_ENABLE_ICU_COLLATIONS)
  if( !db->mallocFailed && rc==SQLITE_OK ){
    rc = sqlite3IcuInit(db);
  }
#endif

#ifdef SQLITE_ENABLE_RTREE
  if( !db->mallocFailed && rc==SQLITE_OK){
Changes to src/os_unix.c.
479
480
481
482
483
484
485
486

487
488
489
490
491
492
493
479
480
481
482
483
484
485

486
487
488
489
490
491
492
493







-
+







#define osMmap ((void*(*)(void*,size_t,int,int,int,off_t))aSyscall[22].pCurrent)

#if !defined(SQLITE_OMIT_WAL) || SQLITE_MAX_MMAP_SIZE>0
  { "munmap",       (sqlite3_syscall_ptr)munmap,          0 },
#else
  { "munmap",       (sqlite3_syscall_ptr)0,               0 },
#endif
#define osMunmap ((void*(*)(void*,size_t))aSyscall[23].pCurrent)
#define osMunmap ((int(*)(void*,size_t))aSyscall[23].pCurrent)

#if HAVE_MREMAP && (!defined(SQLITE_OMIT_WAL) || SQLITE_MAX_MMAP_SIZE>0)
  { "mremap",       (sqlite3_syscall_ptr)mremap,          0 },
#else
  { "mremap",       (sqlite3_syscall_ptr)0,               0 },
#endif
#define osMremap ((void*(*)(void*,size_t,size_t,int,...))aSyscall[24].pCurrent)
4161
4162
4163
4164
4165
4166
4167
4168

4169
4170
4171
4172
4173
4174
4175
4161
4162
4163
4164
4165
4166
4167

4168
4169
4170
4171
4172
4173
4174
4175







-
+







){
  unixShmNode *pShmNode; /* Apply locks to this open shared-memory segment */
  struct flock f;        /* The posix advisory locking structure */
  int rc = SQLITE_OK;    /* Result code form fcntl() */

  /* Access to the unixShmNode object is serialized by the caller */
  pShmNode = pFile->pInode->pShmNode;
  assert( sqlite3_mutex_held(pShmNode->mutex) || pShmNode->nRef==0 );
  assert( pShmNode->nRef==0 || sqlite3_mutex_held(pShmNode->mutex) );

  /* Shared locks never span more than one byte */
  assert( n==1 || lockType!=F_RDLCK );

  /* Locks are within range */
  assert( n>=1 && n<=SQLITE_SHM_NLOCK );

5795
5796
5797
5798
5799
5800
5801
5802

5803
5804
5805
5806
5807
5808
5809
5795
5796
5797
5798
5799
5800
5801

5802
5803
5804
5805
5806
5807
5808
5809







-
+







  struct statfs fsInfo;
#endif

  /* If creating a master or main-file journal, this function will open
  ** a file-descriptor on the directory too. The first time unixSync()
  ** is called the directory file descriptor will be fsync()ed and close()d.
  */
  int syncDir = (isCreate && (
  int isNewJrnl = (isCreate && (
        eType==SQLITE_OPEN_MASTER_JOURNAL 
     || eType==SQLITE_OPEN_MAIN_JOURNAL 
     || eType==SQLITE_OPEN_WAL
  ));

  /* If argument zPath is a NULL pointer, this function is required to open
  ** a temporary file. Use this buffer to store the file name in.
5865
5866
5867
5868
5869
5870
5871
5872

5873
5874
5875
5876
5877
5878
5879
5865
5866
5867
5868
5869
5870
5871

5872
5873
5874
5875
5876
5877
5878
5879







-
+







    /* Database filenames are double-zero terminated if they are not
    ** URIs with parameters.  Hence, they can always be passed into
    ** sqlite3_uri_parameter(). */
    assert( (flags & SQLITE_OPEN_URI) || zName[strlen(zName)+1]==0 );

  }else if( !zName ){
    /* If zName is NULL, the upper layer is requesting a temp file. */
    assert(isDelete && !syncDir);
    assert(isDelete && !isNewJrnl);
    rc = unixGetTempname(pVfs->mxPathname, zTmpname);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    zName = zTmpname;

    /* Generated temporary filenames are always double-zero terminated
5911
5912
5913
5914
5915
5916
5917



5918
5919
5920
5921
5922
5923
5924
5911
5912
5913
5914
5915
5916
5917
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927







+
+
+







      flags |= SQLITE_OPEN_READONLY;
      openFlags |= O_RDONLY;
      isReadonly = 1;
      fd = robust_open(zName, openFlags, openMode);
    }
    if( fd<0 ){
      rc = unixLogError(SQLITE_CANTOPEN_BKPT, "open", zName);
      /* If unable to create a journal, change the error code to
      ** indicate that the directory permissions are wrong. */
      if( isNewJrnl && osAccess(zName, F_OK) ) rc = SQLITE_READONLY_DIRECTORY;
      goto open_finished;
    }

    /* If this process is running as root and if creating a new rollback
    ** journal or WAL file, set the ownership of the journal or WAL to be
    ** the same as the original database.
    */
5970
5971
5972
5973
5974
5975
5976
5977

5978
5979
5980
5981
5982
5983
5984
5973
5974
5975
5976
5977
5978
5979

5980
5981
5982
5983
5984
5985
5986
5987







-
+







#endif

  /* Set up appropriate ctrlFlags */
  if( isDelete )                ctrlFlags |= UNIXFILE_DELETE;
  if( isReadonly )              ctrlFlags |= UNIXFILE_RDONLY;
  noLock = eType!=SQLITE_OPEN_MAIN_DB;
  if( noLock )                  ctrlFlags |= UNIXFILE_NOLOCK;
  if( syncDir )                 ctrlFlags |= UNIXFILE_DIRSYNC;
  if( isNewJrnl )               ctrlFlags |= UNIXFILE_DIRSYNC;
  if( flags & SQLITE_OPEN_URI ) ctrlFlags |= UNIXFILE_URI;

#if SQLITE_ENABLE_LOCKING_STYLE
#if SQLITE_PREFER_PROXY_LOCKING
  isAutoProxy = 1;
#endif
  if( isAutoProxy && (zPath!=NULL) && (!noLock) && pVfs->xOpen ){
Changes to src/os_win.c.
3738
3739
3740
3741
3742
3743
3744
3745

3746
3747
3748
3749
3750
3751
3752
3738
3739
3740
3741
3742
3743
3744

3745
3746
3747
3748
3749
3750
3751
3752







-
+







  int lockType,         /* WINSHM_UNLCK, WINSHM_RDLCK, or WINSHM_WRLCK */
  int ofst,             /* Offset to first byte to be locked/unlocked */
  int nByte             /* Number of bytes to lock or unlock */
){
  int rc = 0;           /* Result code form Lock/UnlockFileEx() */

  /* Access to the winShmNode object is serialized by the caller */
  assert( sqlite3_mutex_held(pFile->mutex) || pFile->nRef==0 );
  assert( pFile->nRef==0 || sqlite3_mutex_held(pFile->mutex) );

  OSTRACE(("SHM-LOCK file=%p, lock=%d, offset=%d, size=%d\n",
           pFile->hFile.h, lockType, ofst, nByte));

  /* Release/Acquire the system-level lock */
  if( lockType==WINSHM_UNLCK ){
    rc = winUnlockFile(&pFile->hFile.h, ofst, 0, nByte, 0);
Changes to src/prepare.c.
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
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
693
694
695
696
697
651
652
653
654
655
656
657


658
659
660
661
662
663
664
665
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

693
694
695
696
697
698
699







-
-












+










+
+
+
+
-
-
-
+
+
+
+
-
-
-

+
+

-







    sParse.pTriggerPrg = pT->pNext;
    sqlite3DbFree(db, pT);
  }

end_prepare:

  sqlite3ParserReset(&sParse);
  rc = sqlite3ApiExit(db, rc);
  assert( (rc&db->errMask)==rc );
  return rc;
}
static int sqlite3LockAndPrepare(
  sqlite3 *db,              /* Database handle. */
  const char *zSql,         /* UTF-8 encoded SQL statement. */
  int nBytes,               /* Length of zSql in bytes. */
  u32 prepFlags,            /* Zero or more SQLITE_PREPARE_* flags */
  Vdbe *pOld,               /* VM being reprepared */
  sqlite3_stmt **ppStmt,    /* OUT: A pointer to the prepared statement */
  const char **pzTail       /* OUT: End of parsed string */
){
  int rc;
  int cnt = 0;

#ifdef SQLITE_ENABLE_API_ARMOR
  if( ppStmt==0 ) return SQLITE_MISUSE_BKPT;
#endif
  *ppStmt = 0;
  if( !sqlite3SafetyCheckOk(db)||zSql==0 ){
    return SQLITE_MISUSE_BKPT;
  }
  sqlite3_mutex_enter(db->mutex);
  sqlite3BtreeEnterAll(db);
  do{
    /* Make multiple attempts to compile the SQL, until it either succeeds
    ** or encounters a permanent error.  A schema problem after one schema
    ** reset is considered a permanent error. */
  rc = sqlite3Prepare(db, zSql, nBytes, prepFlags, pOld, ppStmt, pzTail);
  if( rc==SQLITE_SCHEMA ){
    sqlite3ResetOneSchema(db, -1);
    rc = sqlite3Prepare(db, zSql, nBytes, prepFlags, pOld, ppStmt, pzTail);
    assert( rc==SQLITE_OK || *ppStmt==0 );
  }while( rc==SQLITE_ERROR_RETRY
       || (rc==SQLITE_SCHEMA && (sqlite3ResetOneSchema(db,-1), cnt++)==0) );
    sqlite3_finalize(*ppStmt);
    rc = sqlite3Prepare(db, zSql, nBytes, prepFlags, pOld, ppStmt, pzTail);
  }
  sqlite3BtreeLeaveAll(db);
  rc = sqlite3ApiExit(db, rc);
  assert( (rc&db->errMask)==rc );
  sqlite3_mutex_leave(db->mutex);
  assert( rc==SQLITE_OK || *ppStmt==0 );
  return rc;
}

/*
** Rerun the compilation of a statement after a schema change.
**
** If the statement is successfully recompiled, return SQLITE_OK. Otherwise,
Changes to src/sqlite.h.in.
466
467
468
469
470
471
472


473
474
475
476
477
478
479
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481







+
+







** support for additional result codes that provide more detailed information
** about errors. These [extended result codes] are enabled or disabled
** on a per database connection basis using the
** [sqlite3_extended_result_codes()] API.  Or, the extended code for
** the most recent error can be obtained using
** [sqlite3_extended_errcode()].
*/
#define SQLITE_ERROR_MISSING_COLLSEQ   (SQLITE_ERROR | (1<<8))
#define SQLITE_ERROR_RETRY             (SQLITE_ERROR | (2<<8))
#define SQLITE_IOERR_READ              (SQLITE_IOERR | (1<<8))
#define SQLITE_IOERR_SHORT_READ        (SQLITE_IOERR | (2<<8))
#define SQLITE_IOERR_WRITE             (SQLITE_IOERR | (3<<8))
#define SQLITE_IOERR_FSYNC             (SQLITE_IOERR | (4<<8))
#define SQLITE_IOERR_DIR_FSYNC         (SQLITE_IOERR | (5<<8))
#define SQLITE_IOERR_TRUNCATE          (SQLITE_IOERR | (6<<8))
#define SQLITE_IOERR_FSTAT             (SQLITE_IOERR | (7<<8))
511
512
513
514
515
516
517

518
519
520
521
522
523
524
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527







+







#define SQLITE_CANTOPEN_DIRTYWAL       (SQLITE_CANTOPEN | (5<<8))
#define SQLITE_CORRUPT_VTAB            (SQLITE_CORRUPT | (1<<8))
#define SQLITE_READONLY_RECOVERY       (SQLITE_READONLY | (1<<8))
#define SQLITE_READONLY_CANTLOCK       (SQLITE_READONLY | (2<<8))
#define SQLITE_READONLY_ROLLBACK       (SQLITE_READONLY | (3<<8))
#define SQLITE_READONLY_DBMOVED        (SQLITE_READONLY | (4<<8))
#define SQLITE_READONLY_CANTINIT       (SQLITE_READONLY | (5<<8))
#define SQLITE_READONLY_DIRECTORY      (SQLITE_READONLY | (6<<8))
#define SQLITE_ABORT_ROLLBACK          (SQLITE_ABORT | (2<<8))
#define SQLITE_CONSTRAINT_CHECK        (SQLITE_CONSTRAINT | (1<<8))
#define SQLITE_CONSTRAINT_COMMITHOOK   (SQLITE_CONSTRAINT | (2<<8))
#define SQLITE_CONSTRAINT_FOREIGNKEY   (SQLITE_CONSTRAINT | (3<<8))
#define SQLITE_CONSTRAINT_FUNCTION     (SQLITE_CONSTRAINT | (4<<8))
#define SQLITE_CONSTRAINT_NOTNULL      (SQLITE_CONSTRAINT | (5<<8))
#define SQLITE_CONSTRAINT_PRIMARYKEY   (SQLITE_CONSTRAINT | (6<<8))
Changes to src/sqliteInt.h.
2168
2169
2170
2171
2172
2173
2174

2175
2176
2177
2178
2179
2180
2181
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182







+







  unsigned idxType:2;      /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
  unsigned isResized:1;    /* True if resizeIndexObject() has been called */
  unsigned isCovering:1;   /* True if this is a covering index */
  unsigned noSkipScan:1;   /* Do not try to use skip-scan if true */
  unsigned hasStat1:1;     /* aiRowLogEst values come from sqlite_stat1 */
  unsigned bNoQuery:1;     /* Do not use this index to optimize queries */
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  int nSample;             /* Number of elements in aSample[] */
  int nSampleCol;          /* Size of IndexSample.anEq[] and so on */
  tRowcnt *aAvgEq;         /* Average nEq values for keys not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
  tRowcnt *aiRowEst;       /* Non-logarithmic stat1 data for this index */
  tRowcnt nRowEst0;        /* Non-logarithmic number of rows in the index */
2980
2981
2982
2983
2984
2985
2986
2987

2988
2989
2990
2991
2992
2993
2994
2981
2982
2983
2984
2985
2986
2987

2988
2989
2990
2991
2992
2993
2994
2995







-
+







  int nRangeReg;       /* Size of the temporary register block */
  int iRangeReg;       /* First register in temporary register block */
  int nErr;            /* Number of errors seen */
  int nTab;            /* Number of previously allocated VDBE cursors */
  int nMem;            /* Number of memory cells used so far */
  int nOpAlloc;        /* Number of slots allocated for Vdbe.aOp[] */
  int szOpAlloc;       /* Bytes of memory space allocated for Vdbe.aOp[] */
  int iSelfTab;        /* Table for associated with an index on expr, or negative
  int iSelfTab;        /* Table associated with an index on expr, or negative
                       ** of the base register during check-constraint eval */
  int iCacheLevel;     /* ColCache valid when aColCache[].iLevel<=iCacheLevel */
  int iCacheCnt;       /* Counter used to generate aColCache[].lru values */
  int nLabel;          /* Number of labels used */
  int *aLabel;         /* Space to hold the labels */
  ExprList *pConstExpr;/* Constant expressions */
  Token constraintName;/* Name of the constraint currently being parsed */
Changes to src/test_config.c.
424
425
426
427
428
429
430






431
432
433
434
435
436
437
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443







+
+
+
+
+
+







#endif

#ifdef SQLITE_ENABLE_ICU
  Tcl_SetVar2(interp, "sqlite_options", "icu", "1", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "icu", "0", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_ENABLE_ICU_COLLATIONS
  Tcl_SetVar2(interp, "sqlite_options", "icu_collations", "1", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "icu_collations", "0", TCL_GLOBAL_ONLY);
#endif

#ifdef SQLITE_OMIT_INCRBLOB
  Tcl_SetVar2(interp, "sqlite_options", "incrblob", "0", TCL_GLOBAL_ONLY);
#else
  Tcl_SetVar2(interp, "sqlite_options", "incrblob", "1", TCL_GLOBAL_ONLY);
#endif /* SQLITE_OMIT_AUTOVACUUM */

Changes to src/vdbemem.c.
1317
1318
1319
1320
1321
1322
1323

1324



1325
1326
1327
1328
1329
1330
1331
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335







+

+
+
+







  sqlite3_value *pVal = 0;
  int negInt = 1;
  const char *zNeg = "";
  int rc = SQLITE_OK;

  assert( pExpr!=0 );
  while( (op = pExpr->op)==TK_UPLUS || op==TK_SPAN ) pExpr = pExpr->pLeft;
#if defined(SQLITE_ENABLE_STAT3_OR_STAT4)
  if( op==TK_REGISTER ) op = pExpr->op2;
#else
  if( NEVER(op==TK_REGISTER) ) op = pExpr->op2;
#endif

  /* Compressed expressions only appear when parsing the DEFAULT clause
  ** on a table column definition, and hence only when pCtx==0.  This
  ** check ensures that an EP_TokenOnly expression is never passed down
  ** into valueFromFunction(). */
  assert( (pExpr->flags & EP_TokenOnly)==0 || pCtx==0 );

1412
1413
1414
1415
1416
1417
1418



1419

1420
1421
1422
1423
1424
1425
1426
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425

1426
1427
1428
1429
1430
1431
1432
1433







+
+
+
-
+







  }
#endif

  *ppVal = pVal;
  return rc;

no_mem:
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( pCtx==0 || pCtx->pParse->nErr==0 )
#endif
  sqlite3OomFault(db);
    sqlite3OomFault(db);
  sqlite3DbFree(db, zVal);
  assert( *ppVal==0 );
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  if( pCtx==0 ) sqlite3ValueFree(pVal);
#else
  assert( pCtx==0 ); sqlite3ValueFree(pVal);
#endif
Changes to src/where.c.
2875
2876
2877
2878
2879
2880
2881

2882
2883
2884
2885
2886
2887
2888
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889







+







      pProbe=(pSrc->pIBIndex ? 0 : pProbe->pNext), iSortIdx++
  ){
    if( pProbe->pPartIdxWhere!=0
     && !whereUsablePartialIndex(pSrc->iCursor, pWC, pProbe->pPartIdxWhere) ){
      testcase( pNew->iTab!=pSrc->iCursor );  /* See ticket [98d973b8f5] */
      continue;  /* Partial index inappropriate for this query */
    }
    if( pProbe->bNoQuery ) continue;
    rSize = pProbe->aiRowLogEst[0];
    pNew->u.btree.nEq = 0;
    pNew->u.btree.nBtm = 0;
    pNew->u.btree.nTop = 0;
    pNew->nSkip = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
Changes to src/wherecode.c.
1686
1687
1688
1689
1690
1691
1692

1693
1694
1695
1696
1697
1698
1699
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700







+







      if( sqlite3ExprIsVector(pRight)==0 ){
        disableTerm(pLevel, pRangeEnd);
      }else{
        endEq = 1;
      }
    }else if( bStopAtNull ){
      sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
      sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
      endEq = 0;
      nConstraint++;
    }
    sqlite3DbFree(db, zStartAff);
    sqlite3DbFree(db, zEndAff);

    /* Top of the loop body */
Changes to test/icu.test.
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
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
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












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







-
+



















+
+
-
-
-
-
-
-
-
+
+
+
+
+
+
+

-
-
-
-
+
+
+
+

-
-
+
+

-
-
-
-
+
+
+
+

-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+

-
-
+
+

-
-
-
+
+
+

-
-
-
-
-
-
-
+
+
+
+
+
+
+
+







#
# $Id: icu.test,v 1.2 2008/07/12 14:52:20 drh Exp $
#

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

ifcapable !icu {
ifcapable !icu&&!icu_collations {
  finish_test
  return
}

# Create a table to work with.
#
execsql {CREATE TABLE test1(i1 int, i2 int, r1 real, r2 real, t1 text, t2 text)}
execsql {INSERT INTO test1 VALUES(1,2,1.1,2.2,'hello','world')}
proc test_expr {name settings expr result} {
  do_test $name [format {
    lindex [db eval {
      BEGIN; 
      UPDATE test1 SET %s; 
      SELECT %s FROM test1; 
      ROLLBACK;
    }] 0
  } $settings $expr] $result
}

ifcapable icu {

# Tests of the REGEXP operator.
#
test_expr icu-1.1 {i1='hello'} {i1 REGEXP 'hello'}  1
test_expr icu-1.2 {i1='hello'} {i1 REGEXP '.ello'}  1
test_expr icu-1.3 {i1='hello'} {i1 REGEXP '.ell'}   0
test_expr icu-1.4 {i1='hello'} {i1 REGEXP '.ell.*'} 1
test_expr icu-1.5 {i1=NULL}    {i1 REGEXP '.ell.*'} {}
  # Tests of the REGEXP operator.
  #
  test_expr icu-1.1 {i1='hello'} {i1 REGEXP 'hello'}  1
  test_expr icu-1.2 {i1='hello'} {i1 REGEXP '.ello'}  1
  test_expr icu-1.3 {i1='hello'} {i1 REGEXP '.ell'}   0
  test_expr icu-1.4 {i1='hello'} {i1 REGEXP '.ell.*'} 1
  test_expr icu-1.5 {i1=NULL}    {i1 REGEXP '.ell.*'} {}

# Some non-ascii characters with defined case mappings
#
set ::EGRAVE "\xC8"
set ::egrave "\xE8"
  # Some non-ascii characters with defined case mappings
  #
  set ::EGRAVE "\xC8"
  set ::egrave "\xE8"

set ::OGRAVE "\xD2"
set ::ograve "\xF2"
  set ::OGRAVE "\xD2"
  set ::ograve "\xF2"

# That German letter that looks a bit like a B. The
# upper-case version of which is "SS" (two characters).
#
set ::szlig "\xDF" 
  # That German letter that looks a bit like a B. The
  # upper-case version of which is "SS" (two characters).
  #
  set ::szlig "\xDF" 

# Tests of the upper()/lower() functions.
#
test_expr icu-2.1 {i1='HellO WorlD'} {upper(i1)} {HELLO WORLD}
test_expr icu-2.2 {i1='HellO WorlD'} {lower(i1)} {hello world}
test_expr icu-2.3 {i1=$::egrave} {lower(i1)}     $::egrave
test_expr icu-2.4 {i1=$::egrave} {upper(i1)}     $::EGRAVE
test_expr icu-2.5 {i1=$::ograve} {lower(i1)}     $::ograve
test_expr icu-2.6 {i1=$::ograve} {upper(i1)}     $::OGRAVE
test_expr icu-2.3 {i1=$::EGRAVE} {lower(i1)}     $::egrave
test_expr icu-2.4 {i1=$::EGRAVE} {upper(i1)}     $::EGRAVE
test_expr icu-2.5 {i1=$::OGRAVE} {lower(i1)}     $::ograve
test_expr icu-2.6 {i1=$::OGRAVE} {upper(i1)}     $::OGRAVE
  # Tests of the upper()/lower() functions.
  #
  test_expr icu-2.1 {i1='HellO WorlD'} {upper(i1)} {HELLO WORLD}
  test_expr icu-2.2 {i1='HellO WorlD'} {lower(i1)} {hello world}
  test_expr icu-2.3 {i1=$::egrave} {lower(i1)}     $::egrave
  test_expr icu-2.4 {i1=$::egrave} {upper(i1)}     $::EGRAVE
  test_expr icu-2.5 {i1=$::ograve} {lower(i1)}     $::ograve
  test_expr icu-2.6 {i1=$::ograve} {upper(i1)}     $::OGRAVE
  test_expr icu-2.3 {i1=$::EGRAVE} {lower(i1)}     $::egrave
  test_expr icu-2.4 {i1=$::EGRAVE} {upper(i1)}     $::EGRAVE
  test_expr icu-2.5 {i1=$::OGRAVE} {lower(i1)}     $::ograve
  test_expr icu-2.6 {i1=$::OGRAVE} {upper(i1)}     $::OGRAVE

test_expr icu-2.7 {i1=$::szlig} {upper(i1)}      "SS"
test_expr icu-2.8 {i1='SS'} {lower(i1)}          "ss"
  test_expr icu-2.7 {i1=$::szlig} {upper(i1)}      "SS"
  test_expr icu-2.8 {i1='SS'} {lower(i1)}          "ss"

do_execsql_test icu-2.9 {
  SELECT upper(char(0xfb04,0xfb04,0xfb04,0xfb04));
} {FFLFFLFFLFFL}
  do_execsql_test icu-2.9 {
    SELECT upper(char(0xfb04,0xfb04,0xfb04,0xfb04));
  } {FFLFFLFFLFFL}

# In turkish (locale="tr_TR"), the lower case version of I
# is "small dotless i" (code point 0x131 (decimal 305)).
#
set ::small_dotless_i "\u0131"
test_expr icu-3.1 {i1='I'} {lower(i1)}           "i"
test_expr icu-3.2 {i1='I'} {lower(i1, 'tr_tr')}  $::small_dotless_i
test_expr icu-3.3 {i1='I'} {lower(i1, 'en_AU')}  "i"
  # In turkish (locale="tr_TR"), the lower case version of I
  # is "small dotless i" (code point 0x131 (decimal 305)).
  #
  set ::small_dotless_i "\u0131"
  test_expr icu-3.1 {i1='I'} {lower(i1)}           "i"
  test_expr icu-3.2 {i1='I'} {lower(i1, 'tr_tr')}  $::small_dotless_i
  test_expr icu-3.3 {i1='I'} {lower(i1, 'en_AU')}  "i"
}

#--------------------------------------------------------------------
# Test the collation sequence function.
#
do_test icu-4.1 {
  execsql {
    CREATE TABLE fruit(name);
120
121
122
123
124
125
126

127
128
129
130
131
132
133
134
135
136
137
138
139













140
141
142
143
144





145
123
124
125
126
127
128
129
130













131
132
133
134
135
136
137
138
139
140
141
142
143





144
145
146
147
148
149







+
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
+
+
+
+
+


#-------------------------------------------------------------------------
# Test that it is not possible to call the ICU regex() function with 
# anything other than exactly two arguments. See also:
#
#   http://src.chromium.org/viewvc/chrome/trunk/src/third_party/sqlite/icu-regexp.patch?revision=34807&view=markup
#
ifcapable icu {
do_catchsql_test icu-5.1 { SELECT regexp('a[abc]c.*', 'abc') } {0 1}
do_catchsql_test icu-5.2 { 
  SELECT regexp('a[abc]c.*') 
} {1 {wrong number of arguments to function regexp()}}
do_catchsql_test icu-5.3 { 
  SELECT regexp('a[abc]c.*', 'abc', 'c') 
} {1 {wrong number of arguments to function regexp()}}
do_catchsql_test icu-5.4 { 
  SELECT 'abc' REGEXP 'a[abc]c.*'
} {0 1}
do_catchsql_test icu-5.4 { SELECT 'abc' REGEXP }    {1 {near " ": syntax error}}
do_catchsql_test icu-5.5 { SELECT 'abc' REGEXP, 1 } {1 {near ",": syntax error}}

  do_catchsql_test icu-5.1 { SELECT regexp('a[abc]c.*', 'abc') } {0 1}
  do_catchsql_test icu-5.2 { 
    SELECT regexp('a[abc]c.*') 
  } {1 {wrong number of arguments to function regexp()}}
  do_catchsql_test icu-5.3 { 
    SELECT regexp('a[abc]c.*', 'abc', 'c') 
  } {1 {wrong number of arguments to function regexp()}}
  do_catchsql_test icu-5.4 { 
    SELECT 'abc' REGEXP 'a[abc]c.*'
  } {0 1}
  do_catchsql_test icu-5.4 {SELECT 'abc' REGEXP }   {1 {near " ": syntax error}}
  do_catchsql_test icu-5.5 {SELECT 'abc' REGEXP, 1} {1 {near ",": syntax error}}
 

do_malloc_test icu-6.10 -sqlbody {
  SELECT upper(char(0xfb04,0xdf,0xfb04,0xe8,0xfb04));
}

  do_malloc_test icu-6.10 -sqlbody {
    SELECT upper(char(0xfb04,0xdf,0xfb04,0xe8,0xfb04));
  }
}

finish_test
Changes to test/limit2.test.
145
146
147
148
149
150
151

















152
153
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170







+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+


  INSERT INTO t502 VALUES(1, 5);
  INSERT INTO t502 VALUES(2, 4);
  INSERT INTO t502 VALUES(3, 3);
  INSERT INTO t502 VALUES(4, 6);
  INSERT INTO t502 VALUES(5, 1);
  SELECT j FROM t502 WHERE i IN (1,2,3,4,5) ORDER BY j LIMIT 3;
} {1 3 4}

# Ticket https://www.sqlite.org/src/info/123c9ba32130a6c9 2017-12-13
# Incorrect result when an idnex is used for an ordered join.
#
# This test case is in the limit2.test module because the problem was first
# exposed by check-in https://www.sqlite.org/src/info/559733b09e which 
# implemented the ORDER BY LIMIT optimization that limit2.test strives to
# test.
#
do_execsql_test 600 {
  DROP TABLE IF EXISTS t1;
  CREATE TABLE t1(a, b);  INSERT INTO t1 VALUES(1,2);
  DROP TABLE IF EXISTS t2;
  CREATE TABLE t2(x, y);  INSERT INTO t2 VALUES(1,3);
  CREATE INDEX t1ab ON t1(a,b);
  SELECT y FROM t1, t2 WHERE a=x AND b<=y ORDER BY b DESC;
} {3}

finish_test