/ Check-in [16041116]
Login

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

Overview
Comment:Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 16041116aaaa2d52a289aa02a24bef579ba60896
User & Date: drh 2007-05-05 11:48:52
Original Comment: Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925)
Original User & Date: drh 2007-05-05 11:48:53
Context
2007-05-05
11:48
Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3926) check-in: ad549a40 user: drh tags: trunk
11:48
Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925) check-in: 16041116 user: drh tags: trunk
2007-05-04
19:16
Add documentation on the incremental vacuum feature. (CVS 3924) check-in: b3e2cdae user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to Makefile.in.

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
...
148
149
150
151
152
153
154

155
156
157
158
159
160
161
...
200
201
202
203
204
205
206

207
208
209
210
211
212
213
...
234
235
236
237
238
239
240

241
242
243
244
245
246
247
...
362
363
364
365
366
367
368



369
370
371
372
373
374
375
TCC += -DSQLITE_OMIT_LOAD_EXTENSION=1

# Object files for the SQLite library.
#
LIBOBJ = alter.lo analyze.lo attach.lo auth.lo btree.lo build.lo \
         callback.lo complete.lo date.lo \
         delete.lo expr.lo func.lo hash.lo insert.lo loadext.lo \
         main.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
         pager.lo parse.lo pragma.lo prepare.lo printf.lo random.lo \
         select.lo table.lo tokenize.lo trigger.lo update.lo \
         util.lo vacuum.lo \
         vdbe.lo vdbeapi.lo vdbeaux.lo vdbefifo.lo vdbemem.lo \
         where.lo utf.lo legacy.lo vtab.lo

# All of the source code files.
................................................................................
  $(TOP)/src/func.c \
  $(TOP)/src/hash.c \
  $(TOP)/src/hash.h \
  $(TOP)/src/insert.c \
  $(TOP)/src/legacy.c \
  $(TOP)/src/loadext.c \
  $(TOP)/src/main.c \

  $(TOP)/src/os.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
................................................................................
# Source code to the test files.
#
TESTSRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/date.c \
  $(TOP)/src/func.c \
  $(TOP)/src/insert.c \

  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/printf.c \
................................................................................
  $(TOP)/src/where.c

# Header files used by all library source files.
#
HDR = \
   sqlite3.h  \
   $(TOP)/src/btree.h \

   $(TOP)/src/hash.h \
   opcodes.h \
   $(TOP)/src/os.h \
   $(TOP)/src/os_common.h \
   $(TOP)/src/sqlite3ext.h \
   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/vdbe.h \
................................................................................

loadext.lo:	$(TOP)/src/loadext.c $(HDR)
	$(LTCOMPILE) -c $(TOP)/src/loadext.c

main.lo:	$(TOP)/src/main.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/main.c




pager.lo:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
	$(LTCOMPILE) -c $(TOP)/src/pager.c

opcodes.lo:	opcodes.c
	$(LTCOMPILE) -c opcodes.c

opcodes.c:	opcodes.h $(TOP)/mkopcodec.awk







|







 







>







 







>







 







>







 







>
>
>







119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
...
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
...
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
...
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
...
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
TCC += -DSQLITE_OMIT_LOAD_EXTENSION=1

# Object files for the SQLite library.
#
LIBOBJ = alter.lo analyze.lo attach.lo auth.lo btree.lo build.lo \
         callback.lo complete.lo date.lo \
         delete.lo expr.lo func.lo hash.lo insert.lo loadext.lo \
         main.lo malloc.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
         pager.lo parse.lo pragma.lo prepare.lo printf.lo random.lo \
         select.lo table.lo tokenize.lo trigger.lo update.lo \
         util.lo vacuum.lo \
         vdbe.lo vdbeapi.lo vdbeaux.lo vdbefifo.lo vdbemem.lo \
         where.lo utf.lo legacy.lo vtab.lo

# All of the source code files.
................................................................................
  $(TOP)/src/func.c \
  $(TOP)/src/hash.c \
  $(TOP)/src/hash.h \
  $(TOP)/src/insert.c \
  $(TOP)/src/legacy.c \
  $(TOP)/src/loadext.c \
  $(TOP)/src/main.c \
  $(TOP)/src/mallo.c \
  $(TOP)/src/os.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
................................................................................
# Source code to the test files.
#
TESTSRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/date.c \
  $(TOP)/src/func.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/malloc.c \
  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/printf.c \
................................................................................
  $(TOP)/src/where.c

# Header files used by all library source files.
#
HDR = \
   sqlite3.h  \
   $(TOP)/src/btree.h \
   $(TOP)/src/btreeInt.h \
   $(TOP)/src/hash.h \
   opcodes.h \
   $(TOP)/src/os.h \
   $(TOP)/src/os_common.h \
   $(TOP)/src/sqlite3ext.h \
   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/vdbe.h \
................................................................................

loadext.lo:	$(TOP)/src/loadext.c $(HDR)
	$(LTCOMPILE) -c $(TOP)/src/loadext.c

main.lo:	$(TOP)/src/main.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/main.c

malloc.lo:	$(TOP)/src/malloc.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/malloc.c

pager.lo:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
	$(LTCOMPILE) -c $(TOP)/src/pager.c

opcodes.lo:	opcodes.c
	$(LTCOMPILE) -c opcodes.c

opcodes.c:	opcodes.h $(TOP)/mkopcodec.awk

Changes to main.mk.

54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
..
83
84
85
86
87
88
89

90
91
92
93
94
95
96
...
156
157
158
159
160
161
162

163
164
165
166
167
168
169
...
190
191
192
193
194
195
196

197
198
199
200
201
202
203
...
314
315
316
317
318
319
320



321
322
323
324
325
326
327
TCCX = $(TCC) $(OPTS) $(THREADSAFE) $(USLEEP) -I. -I$(TOP)/src

# Object files for the SQLite library.
#
LIBOBJ+= alter.o analyze.o attach.o auth.o btree.o build.o \
         callback.o complete.o date.o delete.o \
         expr.o func.o hash.o insert.o loadext.o \
         main.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pragma.o prepare.o printf.o random.o \
         select.o table.o tclsqlite.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbefifo.o vdbemem.o \
         where.o utf.o legacy.o vtab.o

# All of the source code files.
................................................................................
  $(TOP)/src/func.c \
  $(TOP)/src/hash.c \
  $(TOP)/src/hash.h \
  $(TOP)/src/insert.c \
  $(TOP)/src/legacy.c \
  $(TOP)/src/loadext.c \
  $(TOP)/src/main.c \

  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
................................................................................
#
TESTSRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/date.c \
  $(TOP)/src/func.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \

  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/printf.c \
................................................................................
  $(TOP)/src/where.c

# Header files used by all library source files.
#
HDR = \
   sqlite3.h  \
   $(TOP)/src/btree.h \

   $(TOP)/src/hash.h \
   opcodes.h \
   $(TOP)/src/os.h \
   $(TOP)/src/os_common.h \
   $(TOP)/src/sqlite3ext.h \
   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/vdbe.h \
................................................................................
	$(TCCX) -c $(TOP)/src/legacy.c

loadext.o:	$(TOP)/src/loadext.c $(HDR)
	$(TCCX) -c $(TOP)/src/loadext.c

main.o:	$(TOP)/src/main.c $(HDR)
	$(TCCX) -c $(TOP)/src/main.c




pager.o:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
	$(TCCX) -c $(TOP)/src/pager.c

opcodes.o:	opcodes.c
	$(TCCX) -c opcodes.c








|







 







>







 







>







 







>







 







>
>
>







54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
..
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
...
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
...
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
...
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
TCCX = $(TCC) $(OPTS) $(THREADSAFE) $(USLEEP) -I. -I$(TOP)/src

# Object files for the SQLite library.
#
LIBOBJ+= alter.o analyze.o attach.o auth.o btree.o build.o \
         callback.o complete.o date.o delete.o \
         expr.o func.o hash.o insert.o loadext.o \
         main.o malloc.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pragma.o prepare.o printf.o random.o \
         select.o table.o tclsqlite.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbefifo.o vdbemem.o \
         where.o utf.o legacy.o vtab.o

# All of the source code files.
................................................................................
  $(TOP)/src/func.c \
  $(TOP)/src/hash.c \
  $(TOP)/src/hash.h \
  $(TOP)/src/insert.c \
  $(TOP)/src/legacy.c \
  $(TOP)/src/loadext.c \
  $(TOP)/src/main.c \
  $(TOP)/src/malloc.c \
  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
................................................................................
#
TESTSRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/date.c \
  $(TOP)/src/func.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/malloc.c \
  $(TOP)/src/os.c \
  $(TOP)/src/os_os2.c \
  $(TOP)/src/os_unix.c \
  $(TOP)/src/os_win.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/printf.c \
................................................................................
  $(TOP)/src/where.c

# Header files used by all library source files.
#
HDR = \
   sqlite3.h  \
   $(TOP)/src/btree.h \
   $(TOP)/src/btreeInt.h \
   $(TOP)/src/hash.h \
   opcodes.h \
   $(TOP)/src/os.h \
   $(TOP)/src/os_common.h \
   $(TOP)/src/sqlite3ext.h \
   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/vdbe.h \
................................................................................
	$(TCCX) -c $(TOP)/src/legacy.c

loadext.o:	$(TOP)/src/loadext.c $(HDR)
	$(TCCX) -c $(TOP)/src/loadext.c

main.o:	$(TOP)/src/main.c $(HDR)
	$(TCCX) -c $(TOP)/src/main.c

malloc.o:	$(TOP)/src/malloc.c $(HDR)
	$(TCCX) -c $(TOP)/src/malloc.c

pager.o:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
	$(TCCX) -c $(TOP)/src/pager.c

opcodes.o:	opcodes.c
	$(TCCX) -c opcodes.c

Changes to src/btree.c.

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
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
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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
...
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
....
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
....
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
....
6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.375 2007/05/04 19:03:03 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
**
** The basic idea is that each page of the file contains N database
** entries and N+1 pointers to subpages.
**
**   ----------------------------------------------------------------
**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
**   ----------------------------------------------------------------
**
** All of the keys on the page that Ptr(0) points to have values less
** than Key(0).  All of the keys on page Ptr(1) and its subpages have
** values greater than Key(0) and less than Key(1).  All of the keys
** on Ptr(N) and its subpages have values greater than Key(N-1).  And
** so forth.
**
** Finding a particular key requires reading O(log(M)) pages from the 
** disk where M is the number of entries in the tree.
**
** In this implementation, a single file can hold one or more separate 
** BTrees.  Each BTree is identified by the index of its root page.  The
** key and data for any entry are combined to form the "payload".  A
** fixed amount of payload can be carried directly on the database
** page.  If the payload is larger than the preset amount then surplus
** bytes are stored on overflow pages.  The payload for an entry
** and the preceding pointer are combined to form a "Cell".  Each 
** page has a small header which contains the Ptr(N) pointer and other
** information such as the size of key and data.
**
** FORMAT DETAILS
**
** The file is divided into pages.  The first page is called page 1,
** the second is page 2, and so forth.  A page number of zero indicates
** "no such page".  The page size can be anything between 512 and 65536.
** Each page can be either a btree page, a freelist page or an overflow
** page.
**
** The first page is always a btree page.  The first 100 bytes of the first
** page contain a special header (the "file header") that describes the file.
** The format of the file header is as follows:
**
**   OFFSET   SIZE    DESCRIPTION
**      0      16     Header string: "SQLite format 3\000"
**     16       2     Page size in bytes.  
**     18       1     File format write version
**     19       1     File format read version
**     20       1     Bytes of unused space at the end of each page
**     21       1     Max embedded payload fraction
**     22       1     Min embedded payload fraction
**     23       1     Min leaf payload fraction
**     24       4     File change counter
**     28       4     Reserved for future use
**     32       4     First freelist page
**     36       4     Number of freelist pages in the file
**     40      60     15 4-byte meta values passed to higher layers
**
** All of the integer values are big-endian (most significant byte first).
**
** The file change counter is incremented when the database is changed more
** than once within the same second.  This counter, together with the
** modification time of the file, allows other processes to know
** when the file has changed and thus when they need to flush their
** cache.
**
** The max embedded payload fraction is the amount of the total usable
** space in a page that can be consumed by a single cell for standard
** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
** is to limit the maximum cell size so that at least 4 cells will fit
** on one page.  Thus the default max embedded payload fraction is 64.
**
** If the payload for a cell is larger than the max payload, then extra
** payload is spilled to overflow pages.  Once an overflow page is allocated,
** as many bytes as possible are moved into the overflow pages without letting
** the cell size drop below the min embedded payload fraction.
**
** The min leaf payload fraction is like the min embedded payload fraction
** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
** not specified in the header.
**
** Each btree pages is divided into three sections:  The header, the
** cell pointer array, and the cell area area.  Page 1 also has a 100-byte
** file header that occurs before the page header.
**
**      |----------------|
**      | file header    |   100 bytes.  Page 1 only.
**      |----------------|
**      | page header    |   8 bytes for leaves.  12 bytes for interior nodes
**      |----------------|
**      | cell pointer   |   |  2 bytes per cell.  Sorted order.
**      | array          |   |  Grows downward
**      |                |   v
**      |----------------|
**      | unallocated    |
**      | space          |
**      |----------------|   ^  Grows upwards
**      | cell content   |   |  Arbitrary order interspersed with freeblocks.
**      | area           |   |  and free space fragments.
**      |----------------|
**
** The page headers looks like this:
**
**   OFFSET   SIZE     DESCRIPTION
**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
**      1       2      byte offset to the first freeblock
**      3       2      number of cells on this page
**      5       2      first byte of the cell content area
**      7       1      number of fragmented free bytes
**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
**
** The flags define the format of this btree page.  The leaf flag means that
** this page has no children.  The zerodata flag means that this page carries
** only keys and no data.  The intkey flag means that the key is a integer
** which is stored in the key size entry of the cell header rather than in
** the payload area.
**
** The cell pointer array begins on the first byte after the page header.
** The cell pointer array contains zero or more 2-byte numbers which are
** offsets from the beginning of the page to the cell content in the cell
** content area.  The cell pointers occur in sorted order.  The system strives
** to keep free space after the last cell pointer so that new cells can
** be easily added without having to defragment the page.
**
** Cell content is stored at the very end of the page and grows toward the
** beginning of the page.
**
** Unused space within the cell content area is collected into a linked list of
** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset
** to the first freeblock is given in the header.  Freeblocks occur in
** increasing order.  Because a freeblock must be at least 4 bytes in size,
** any group of 3 or fewer unused bytes in the cell content area cannot
** exist on the freeblock chain.  A group of 3 or fewer free bytes is called
** a fragment.  The total number of bytes in all fragments is recorded.
** in the page header at offset 7.
**
**    SIZE    DESCRIPTION
**      2     Byte offset of the next freeblock
**      2     Bytes in this freeblock
**
** Cells are of variable length.  Cells are stored in the cell content area at
** the end of the page.  Pointers to the cells are in the cell pointer array
** that immediately follows the page header.  Cells is not necessarily
** contiguous or in order, but cell pointers are contiguous and in order.
**
** Cell content makes use of variable length integers.  A variable
** length integer is 1 to 9 bytes where the lower 7 bits of each 
** byte are used.  The integer consists of all bytes that have bit 8 set and
** the first byte with bit 8 clear.  The most significant byte of the integer
** appears first.  A variable-length integer may not be more than 9 bytes long.
** As a special case, all 8 bytes of the 9th byte are used as data.  This
** allows a 64-bit integer to be encoded in 9 bytes.
**
**    0x00                      becomes  0x00000000
**    0x7f                      becomes  0x0000007f
**    0x81 0x00                 becomes  0x00000080
**    0x82 0x00                 becomes  0x00000100
**    0x80 0x7f                 becomes  0x0000007f
**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
**
** Variable length integers are used for rowids and to hold the number of
** bytes of key and data in a btree cell.
**
** The content of a cell looks like this:
**
**    SIZE    DESCRIPTION
**      4     Page number of the left child. Omitted if leaf flag is set.
**     var    Number of bytes of data. Omitted if the zerodata flag is set.
**     var    Number of bytes of key. Or the key itself if intkey flag is set.
**      *     Payload
**      4     First page of the overflow chain.  Omitted if no overflow
**
** Overflow pages form a linked list.  Each page except the last is completely
** filled with data (pagesize - 4 bytes).  The last page can have as little
** as 1 byte of data.
**
**    SIZE    DESCRIPTION
**      4     Page number of next overflow page
**      *     Data
**
** Freelist pages come in two subtypes: trunk pages and leaf pages.  The
** file header points to first in a linked list of trunk page.  Each trunk
** page points to multiple leaf pages.  The content of a leaf page is
** unspecified.  A trunk page looks like this:
**
**    SIZE    DESCRIPTION
**      4     Page number of next trunk page
**      4     Number of leaf pointers on this page
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>

/* Round up a number to the next larger multiple of 8.  This is used
** to force 8-byte alignment on 64-bit architectures.
*/
#define ROUND8(x)   ((x+7)&~7)


/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

/* The maximum number of cells on a single page of the database.  This
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL(pBt) ((pBt->pageSize-8)/3)

/* Forward declarations */
typedef struct MemPage MemPage;
typedef struct BtLock BtLock;

/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**
** You can change this value at compile-time by specifying a
** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
** header must be exactly 16 bytes including the zero-terminator so
** the string itself should be 15 characters long.  If you change
** the header, then your custom library will not be able to read 
** databases generated by the standard tools and the standard tools
** will not be able to read databases created by your custom library.
*/
#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
#  define SQLITE_FILE_HEADER "SQLite format 3"
#endif
static const char zMagicHeader[] = SQLITE_FILE_HEADER;

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02
#define PTF_LEAFDATA  0x04
#define PTF_LEAF      0x08

/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.

**
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  u8 isInit;           /* True if previously initialized. MUST BE FIRST! */
  u8 idxShift;         /* True if Cell indices have changed */
  u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
  u8 intKey;           /* True if intkey flag is set */
  u8 leaf;             /* True if leaf flag is set */
  u8 zeroData;         /* True if table stores keys only */
  u8 leafData;         /* True if tables stores data on leaves only */
  u8 hasData;          /* True if this page stores data */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;          /* Pointers to the body of the overflow cell */
    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  BtShared *pBt;       /* Pointer back to BTree structure */
  u8 *aData;           /* Pointer back to the start of the page */
  DbPage *pDbPage;     /* Pager page handle */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/
#define EXTRA_SIZE sizeof(MemPage)

/* Btree handle */
struct Btree {
  sqlite3 *pSqlite;
  BtShared *pBt;
  u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
};

/*
** Btree.inTrans may take one of the following values.
**
** If the shared-data extension is enabled, there may be multiple users
** of the Btree structure. At most one of these may open a write transaction,
** but any number may have active read transactions. Variable Btree.pDb 
** points to the handle that owns any current write-transaction.
*/
#define TRANS_NONE  0
#define TRANS_READ  1
#define TRANS_WRITE 2

/*
** Everything we need to know about an open database
*/
struct BtShared {
  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* A list of all open cursors */
  MemPage *pPage1;      /* First page of the database */
  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 autoVacuum;        /* True if auto-vacuum is enabled */
  u8 incrVacuum;        /* True if incr-vacuum is enabled */
  Pgno nTrunc;          /* Non-zero if the db will be truncated (incr vacuum) */
#endif
  u16 pageSize;         /* Total number of bytes on a page */
  u16 usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
  u8 inTransaction;     /* Transaction state */
  int nRef;             /* Number of references to this structure */
  int nTransaction;     /* Number of open transactions (read + write) */
  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
#ifndef SQLITE_OMIT_SHARED_CACHE
  BtLock *pLock;        /* List of locks held on this shared-btree struct */
  BtShared *pNext;      /* Next in ThreadData.pBtree linked list */
#endif
};

/*
** An instance of the following structure is used to hold information
** about a cell.  The parseCellPtr() function fills in this structure
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
struct CellInfo {
  u8 *pCell;     /* Pointer to the start of cell content */
  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
  u32 nData;     /* Number of bytes of data */
  u32 nPayload;  /* Total amount of payload */
  u16 nHeader;   /* Size of the cell content header in bytes */
  u16 nLocal;    /* Amount of payload held locally */
  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBtree;            /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
#ifndef SQLITE_OMIT_INCRBLOB
  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
  Pgno *aOverflow;          /* Cache of overflow page locations */
#endif
};

/*
** Potential values for BtCursor.eState.
**
** CURSOR_VALID:
**   Cursor points to a valid entry. getPayload() etc. may be called.
**
** CURSOR_INVALID:
**   Cursor does not point to a valid entry. This can happen (for example) 
**   because the table is empty or because BtreeCursorFirst() has not been
**   called.
**
** CURSOR_REQUIRESEEK:
**   The table that this cursor was opened on still exists, but has been 
**   modified since the cursor was last used. The cursor position is saved
**   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in 
**   this state, restoreOrClearCursorPosition() can be called to attempt to
**   seek the cursor to the saved position.
*/
#define CURSOR_INVALID           0
#define CURSOR_VALID             1
#define CURSOR_REQUIRESEEK       2

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace )\
/*                        { sqlite3DebugPrintf X; fflush(stdout); } */ \
{ printf X; fflush(stdout); }
int sqlite3_btree_trace=0;  /* True to enable tracing */
#else
# define TRACE(X)
#endif

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);

/*
** Read or write a two- and four-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
static u32 get4byte(unsigned char *p){
  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
}
static void put2byte(unsigned char *p, u32 v){
  p[0] = v>>8;
  p[1] = v;
}
static void put4byte(unsigned char *p, u32 v){
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}

/*
** Routines to read and write variable-length integers.  These used to
** be defined locally, but now we use the varint routines in the util.c
** file.
*/
#define getVarint    sqlite3GetVarint
/* #define getVarint32  sqlite3GetVarint32 */
#define getVarint32(A,B)  ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))
#define putVarint    sqlite3PutVarint

/* The database page the PENDING_BYTE occupies. This page is never used.
** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
** should possibly be consolidated (presumably in pager.h).
**
** If disk I/O is omitted (meaning that the database is stored purely
** in memory) then there is no pending byte.
*/
#ifdef SQLITE_OMIT_DISKIO
# define PENDING_BYTE_PAGE(pBt)  0x7fffffff
#else
# define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)
#endif

/*
** A linked list of the following structures is stored at BtShared.pLock.
** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
** is opened on the table with root page BtShared.iTable. Locks are removed
** from this list when a transaction is committed or rolled back, or when
** a btree handle is closed.
*/
struct BtLock {
  Btree *pBtree;        /* Btree handle holding this lock */
  Pgno iTable;          /* Root page of table */
  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
  BtLock *pNext;        /* Next in BtShared.pLock list */
};

/* Candidate values for BtLock.eLock */
#define READ_LOCK     1
#define WRITE_LOCK    2

#ifdef SQLITE_OMIT_SHARED_CACHE
  /*
  ** The functions queryTableLock(), lockTable() and unlockAllTables()
  ** manipulate entries in the BtShared.pLock linked list used to store
  ** shared-cache table level locks. If the library is compiled with the
  ** shared-cache feature disabled, then there is only ever one user
................................................................................
}

#define restoreOrClearCursorPosition(p) \
  (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p):SQLITE_OK)

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** These macros define the location of the pointer-map entry for a 
** database page. The first argument to each is the number of usable
** bytes on each page of the database (often 1024). The second is the
** page number to look up in the pointer map.
**
** PTRMAP_PAGENO returns the database page number of the pointer-map
** page that stores the required pointer. PTRMAP_PTROFFSET returns
** the offset of the requested map entry.
**
** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
** this test.
*/
#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
#define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))
#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))

static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){
  int nPagesPerMapPage = (pBt->usableSize/5)+1;
  int iPtrMap = (pgno-2)/nPagesPerMapPage;
  int ret = (iPtrMap*nPagesPerMapPage) + 2; 
  if( ret==PENDING_BYTE_PAGE(pBt) ){
    ret++;
  }
  return ret;
}

/*
** The pointer map is a lookup table that identifies the parent page for
** each child page in the database file.  The parent page is the page that
** contains a pointer to the child.  Every page in the database contains
** 0 or 1 parent pages.  (In this context 'database page' refers
** to any page that is not part of the pointer map itself.)  Each pointer map
** entry consists of a single byte 'type' and a 4 byte parent page number.
** The PTRMAP_XXX identifiers below are the valid types.
**
** The purpose of the pointer map is to facility moving pages from one
** position in the file to another as part of autovacuum.  When a page
** is moved, the pointer in its parent must be updated to point to the
** new location.  The pointer map is used to locate the parent page quickly.
**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
** PTRMAP_OVERFLOW1: The database page is the first page in a list of 
**                   overflow pages. The page number identifies the page that
**                   contains the cell with a pointer to this overflow page.
**
** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
**                   overflow pages. The page-number identifies the previous
**                   page in the overflow page list.
**
** PTRMAP_BTREE: The database page is a non-root btree page. The page number
**               identifies the parent page in the btree.
*/
#define PTRMAP_ROOTPAGE 1
#define PTRMAP_FREEPAGE 2
#define PTRMAP_OVERFLOW1 3
#define PTRMAP_OVERFLOW2 4
#define PTRMAP_BTREE 5

/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
................................................................................
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif


/* A bunch of assert() statements to check the transaction state variables
** of handle p (type Btree*) are internally consistent.
*/
#define btreeIntegrity(p) \
  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
  assert( p->pBt->inTransaction>=p->inTrans ); 

/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
................................................................................
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}
#endif /* SQLITE_OMIT_QUICKBALANCE */

/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
*/
#ifndef SQLITE_OMIT_AUTOVACUUM
#define ISAUTOVACUUM (pBt->autoVacuum)
#else
#define ISAUTOVACUUM 0
#endif

/*
** This routine redistributes Cells on pPage and up to NN*2 siblings
** of pPage so that all pages have about the same amount of free space.
** Usually NN siblings on either side of pPage is used in the balancing,
** though more siblings might come from one side if pPage is the first
** or last child of its parent.  If pPage has fewer than 2*NN siblings
** (something which can only happen if pPage is the root page or a 
................................................................................
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
*/
Pager *sqlite3BtreePager(Btree *p){
  return p->pBt->pPager;
}

/*
** This structure is passed around through all the sanity checking routines
** in order to keep track of some global state information.
*/
typedef struct IntegrityCk IntegrityCk;
struct IntegrityCk {
  BtShared *pBt;    /* The tree being checked out */
  Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
  int nPage;        /* Number of pages in the database */
  int *anRef;       /* Number of times each page is referenced */
  int mxErr;        /* Stop accumulating errors when this reaches zero */
  char *zErrMsg;    /* An error message.  NULL if no errors seen. */
  int nErr;         /* Number of messages written to zErrMsg so far */
};

#ifndef SQLITE_OMIT_INTEGRITY_CHECK
/*
** Append a message to the error message string.
*/
static void checkAppendMsg(
  IntegrityCk *pCheck,
  char *zMsg1,







|


|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

<
<
|
<
<

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

|
|
<
<
<
<
<
<
<
<

<
<
<


<
<
<
<
<
<
<
<


<
<
<
>
|
<
<
<
<

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

<
<
<

<
<







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







 







|
|
|
<
<
<
<
<
<
<
<
<
<

<
<
<
<










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







 







<
<
<
<
<
<
<
<
<







 







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







 







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







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
...
317
318
319
320
321
322
323
324
325
326










327




328
329
330
331
332
333
334
335
336
337





































338
339
340
341
342
343
344
...
571
572
573
574
575
576
577









578
579
580
581
582
583
584
....
4239
4240
4241
4242
4243
4244
4245













4246
4247
4248
4249
4250
4251
4252
....
5838
5839
5840
5841
5842
5843
5844















5845
5846
5847
5848
5849
5850
5851
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.376 2007/05/05 11:48:54 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.






























































































































































































*/


#include "btreeInt.h"
























/*
** The header string that appears at the beginning of every
** SQLite database.








*/



static const char zMagicHeader[] = SQLITE_FILE_HEADER;










/*



** Set this global variable to 1 to enable tracing using the TRACE
** macro.




*/































































































































































#if SQLITE_TEST



int sqlite3_btree_trace=0;  /* True to enable tracing */


#endif

/*
** Forward declaration
*/
static int checkReadLocks(Btree*,Pgno,BtCursor*);






























































#ifdef SQLITE_OMIT_SHARED_CACHE
  /*
  ** The functions queryTableLock(), lockTable() and unlockAllTables()
  ** manipulate entries in the BtShared.pLock linked list used to store
  ** shared-cache table level locks. If the library is compiled with the
  ** shared-cache feature disabled, then there is only ever one user
................................................................................
}

#define restoreOrClearCursorPosition(p) \
  (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p):SQLITE_OK)

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** Given a page number of a regular database page, return the page
** number for the pointer-map page that contains the entry for the
** input page number.










*/




static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){
  int nPagesPerMapPage = (pBt->usableSize/5)+1;
  int iPtrMap = (pgno-2)/nPagesPerMapPage;
  int ret = (iPtrMap*nPagesPerMapPage) + 2; 
  if( ret==PENDING_BYTE_PAGE(pBt) ){
    ret++;
  }
  return ret;
}






































/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
................................................................................
  u8 *pCell;
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif











/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static int defragmentPage(MemPage *pPage){
................................................................................
  ** in case the divider cell inserted caused it to become overfull.
  */
  releasePage(pNew);
  return balance(pParent, 0);
}
#endif /* SQLITE_OMIT_QUICKBALANCE */














/*
** This routine redistributes Cells on pPage and up to NN*2 siblings
** of pPage so that all pages have about the same amount of free space.
** Usually NN siblings on either side of pPage is used in the balancing,
** though more siblings might come from one side if pPage is the first
** or last child of its parent.  If pPage has fewer than 2*NN siblings
** (something which can only happen if pPage is the root page or a 
................................................................................
** Return the pager associated with a BTree.  This routine is used for
** testing and debugging only.
*/
Pager *sqlite3BtreePager(Btree *p){
  return p->pBt->pPager;
}
















#ifndef SQLITE_OMIT_INTEGRITY_CHECK
/*
** Append a message to the error message string.
*/
static void checkAppendMsg(
  IntegrityCk *pCheck,
  char *zMsg1,

Added src/btreeInt.h.

































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
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
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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
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
/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btreeInt.h,v 1.1 2007/05/05 11:48:54 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
**
** The basic idea is that each page of the file contains N database
** entries and N+1 pointers to subpages.
**
**   ----------------------------------------------------------------
**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
**   ----------------------------------------------------------------
**
** All of the keys on the page that Ptr(0) points to have values less
** than Key(0).  All of the keys on page Ptr(1) and its subpages have
** values greater than Key(0) and less than Key(1).  All of the keys
** on Ptr(N) and its subpages have values greater than Key(N-1).  And
** so forth.
**
** Finding a particular key requires reading O(log(M)) pages from the 
** disk where M is the number of entries in the tree.
**
** In this implementation, a single file can hold one or more separate 
** BTrees.  Each BTree is identified by the index of its root page.  The
** key and data for any entry are combined to form the "payload".  A
** fixed amount of payload can be carried directly on the database
** page.  If the payload is larger than the preset amount then surplus
** bytes are stored on overflow pages.  The payload for an entry
** and the preceding pointer are combined to form a "Cell".  Each 
** page has a small header which contains the Ptr(N) pointer and other
** information such as the size of key and data.
**
** FORMAT DETAILS
**
** The file is divided into pages.  The first page is called page 1,
** the second is page 2, and so forth.  A page number of zero indicates
** "no such page".  The page size can be anything between 512 and 65536.
** Each page can be either a btree page, a freelist page or an overflow
** page.
**
** The first page is always a btree page.  The first 100 bytes of the first
** page contain a special header (the "file header") that describes the file.
** The format of the file header is as follows:
**
**   OFFSET   SIZE    DESCRIPTION
**      0      16     Header string: "SQLite format 3\000"
**     16       2     Page size in bytes.  
**     18       1     File format write version
**     19       1     File format read version
**     20       1     Bytes of unused space at the end of each page
**     21       1     Max embedded payload fraction
**     22       1     Min embedded payload fraction
**     23       1     Min leaf payload fraction
**     24       4     File change counter
**     28       4     Reserved for future use
**     32       4     First freelist page
**     36       4     Number of freelist pages in the file
**     40      60     15 4-byte meta values passed to higher layers
**
** All of the integer values are big-endian (most significant byte first).
**
** The file change counter is incremented when the database is changed more
** than once within the same second.  This counter, together with the
** modification time of the file, allows other processes to know
** when the file has changed and thus when they need to flush their
** cache.
**
** The max embedded payload fraction is the amount of the total usable
** space in a page that can be consumed by a single cell for standard
** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
** is to limit the maximum cell size so that at least 4 cells will fit
** on one page.  Thus the default max embedded payload fraction is 64.
**
** If the payload for a cell is larger than the max payload, then extra
** payload is spilled to overflow pages.  Once an overflow page is allocated,
** as many bytes as possible are moved into the overflow pages without letting
** the cell size drop below the min embedded payload fraction.
**
** The min leaf payload fraction is like the min embedded payload fraction
** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
** not specified in the header.
**
** Each btree pages is divided into three sections:  The header, the
** cell pointer array, and the cell area area.  Page 1 also has a 100-byte
** file header that occurs before the page header.
**
**      |----------------|
**      | file header    |   100 bytes.  Page 1 only.
**      |----------------|
**      | page header    |   8 bytes for leaves.  12 bytes for interior nodes
**      |----------------|
**      | cell pointer   |   |  2 bytes per cell.  Sorted order.
**      | array          |   |  Grows downward
**      |                |   v
**      |----------------|
**      | unallocated    |
**      | space          |
**      |----------------|   ^  Grows upwards
**      | cell content   |   |  Arbitrary order interspersed with freeblocks.
**      | area           |   |  and free space fragments.
**      |----------------|
**
** The page headers looks like this:
**
**   OFFSET   SIZE     DESCRIPTION
**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
**      1       2      byte offset to the first freeblock
**      3       2      number of cells on this page
**      5       2      first byte of the cell content area
**      7       1      number of fragmented free bytes
**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
**
** The flags define the format of this btree page.  The leaf flag means that
** this page has no children.  The zerodata flag means that this page carries
** only keys and no data.  The intkey flag means that the key is a integer
** which is stored in the key size entry of the cell header rather than in
** the payload area.
**
** The cell pointer array begins on the first byte after the page header.
** The cell pointer array contains zero or more 2-byte numbers which are
** offsets from the beginning of the page to the cell content in the cell
** content area.  The cell pointers occur in sorted order.  The system strives
** to keep free space after the last cell pointer so that new cells can
** be easily added without having to defragment the page.
**
** Cell content is stored at the very end of the page and grows toward the
** beginning of the page.
**
** Unused space within the cell content area is collected into a linked list of
** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset
** to the first freeblock is given in the header.  Freeblocks occur in
** increasing order.  Because a freeblock must be at least 4 bytes in size,
** any group of 3 or fewer unused bytes in the cell content area cannot
** exist on the freeblock chain.  A group of 3 or fewer free bytes is called
** a fragment.  The total number of bytes in all fragments is recorded.
** in the page header at offset 7.
**
**    SIZE    DESCRIPTION
**      2     Byte offset of the next freeblock
**      2     Bytes in this freeblock
**
** Cells are of variable length.  Cells are stored in the cell content area at
** the end of the page.  Pointers to the cells are in the cell pointer array
** that immediately follows the page header.  Cells is not necessarily
** contiguous or in order, but cell pointers are contiguous and in order.
**
** Cell content makes use of variable length integers.  A variable
** length integer is 1 to 9 bytes where the lower 7 bits of each 
** byte are used.  The integer consists of all bytes that have bit 8 set and
** the first byte with bit 8 clear.  The most significant byte of the integer
** appears first.  A variable-length integer may not be more than 9 bytes long.
** As a special case, all 8 bytes of the 9th byte are used as data.  This
** allows a 64-bit integer to be encoded in 9 bytes.
**
**    0x00                      becomes  0x00000000
**    0x7f                      becomes  0x0000007f
**    0x81 0x00                 becomes  0x00000080
**    0x82 0x00                 becomes  0x00000100
**    0x80 0x7f                 becomes  0x0000007f
**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
**
** Variable length integers are used for rowids and to hold the number of
** bytes of key and data in a btree cell.
**
** The content of a cell looks like this:
**
**    SIZE    DESCRIPTION
**      4     Page number of the left child. Omitted if leaf flag is set.
**     var    Number of bytes of data. Omitted if the zerodata flag is set.
**     var    Number of bytes of key. Or the key itself if intkey flag is set.
**      *     Payload
**      4     First page of the overflow chain.  Omitted if no overflow
**
** Overflow pages form a linked list.  Each page except the last is completely
** filled with data (pagesize - 4 bytes).  The last page can have as little
** as 1 byte of data.
**
**    SIZE    DESCRIPTION
**      4     Page number of next overflow page
**      *     Data
**
** Freelist pages come in two subtypes: trunk pages and leaf pages.  The
** file header points to first in a linked list of trunk page.  Each trunk
** page points to multiple leaf pages.  The content of a leaf page is
** unspecified.  A trunk page looks like this:
**
**    SIZE    DESCRIPTION
**      4     Page number of next trunk page
**      4     Number of leaf pointers on this page
**      *     zero or more pages numbers of leaves
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "os.h"
#include <assert.h>

/* Round up a number to the next larger multiple of 8.  This is used
** to force 8-byte alignment on 64-bit architectures.
*/
#define ROUND8(x)   ((x+7)&~7)


/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

/* The maximum number of cells on a single page of the database.  This
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL(pBt) ((pBt->pageSize-8)/3)

/* Forward declarations */
typedef struct MemPage MemPage;
typedef struct BtLock BtLock;

/*
** This is a magic string that appears at the beginning of every
** SQLite database in order to identify the file as a real database.
**
** You can change this value at compile-time by specifying a
** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
** header must be exactly 16 bytes including the zero-terminator so
** the string itself should be 15 characters long.  If you change
** the header, then your custom library will not be able to read 
** databases generated by the standard tools and the standard tools
** will not be able to read databases created by your custom library.
*/
#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
#  define SQLITE_FILE_HEADER "SQLite format 3"
#endif

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02
#define PTF_LEAFDATA  0x04
#define PTF_LEAF      0x08

/*
** As each page of the file is loaded into memory, an instance of the following
** structure is appended and initialized to zero.  This structure stores
** information about the page that is decoded from the raw file page.
**
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  u8 isInit;           /* True if previously initialized. MUST BE FIRST! */
  u8 idxShift;         /* True if Cell indices have changed */
  u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
  u8 intKey;           /* True if intkey flag is set */
  u8 leaf;             /* True if leaf flag is set */
  u8 zeroData;         /* True if table stores keys only */
  u8 leafData;         /* True if tables stores data on leaves only */
  u8 hasData;          /* True if this page stores data */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer */
  u16 idxParent;       /* Index in parent of this node */
  u16 nFree;           /* Number of free bytes on the page */
  u16 nCell;           /* Number of cells on this page, local and ovfl */
  struct _OvflCell {   /* Cells that will not fit on aData[] */
    u8 *pCell;          /* Pointers to the body of the overflow cell */
    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
  } aOvfl[5];
  BtShared *pBt;       /* Pointer back to BTree structure */
  u8 *aData;           /* Pointer back to the start of the page */
  DbPage *pDbPage;     /* Pager page handle */
  Pgno pgno;           /* Page number for this page */
  MemPage *pParent;    /* The parent of this page.  NULL for root */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/
#define EXTRA_SIZE sizeof(MemPage)

/* Btree handle */
struct Btree {
  sqlite3 *pSqlite;
  BtShared *pBt;
  u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
};

/*
** Btree.inTrans may take one of the following values.
**
** If the shared-data extension is enabled, there may be multiple users
** of the Btree structure. At most one of these may open a write transaction,
** but any number may have active read transactions. Variable Btree.pDb 
** points to the handle that owns any current write-transaction.
*/
#define TRANS_NONE  0
#define TRANS_READ  1
#define TRANS_WRITE 2

/*
** Everything we need to know about an open database
*/
struct BtShared {
  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* A list of all open cursors */
  MemPage *pPage1;      /* First page of the database */
  u8 inStmt;            /* True if we are in a statement subtransaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 autoVacuum;        /* True if auto-vacuum is enabled */
  u8 incrVacuum;        /* True if incr-vacuum is enabled */
  Pgno nTrunc;          /* Non-zero if the db will be truncated (incr vacuum) */
#endif
  u16 pageSize;         /* Total number of bytes on a page */
  u16 usableSize;       /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
  u8 inTransaction;     /* Transaction state */
  int nRef;             /* Number of references to this structure */
  int nTransaction;     /* Number of open transactions (read + write) */
  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
#ifndef SQLITE_OMIT_SHARED_CACHE
  BtLock *pLock;        /* List of locks held on this shared-btree struct */
  BtShared *pNext;      /* Next in ThreadData.pBtree linked list */
#endif
};

/*
** An instance of the following structure is used to hold information
** about a cell.  The parseCellPtr() function fills in this structure
** based on information extract from the raw disk page.
*/
typedef struct CellInfo CellInfo;
struct CellInfo {
  u8 *pCell;     /* Pointer to the start of cell content */
  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
  u32 nData;     /* Number of bytes of data */
  u32 nPayload;  /* Total amount of payload */
  u16 nHeader;   /* Size of the cell content header in bytes */
  u16 nLocal;    /* Amount of payload held locally */
  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
  u16 nSize;     /* Size of the cell content on the main b-tree page */
};

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBtree;            /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */
  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
  void *pKey;      /* Saved key that was cursor's last known position */
  i64 nKey;        /* Size of pKey, or last integer key */
  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
#ifndef SQLITE_OMIT_INCRBLOB
  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
  Pgno *aOverflow;          /* Cache of overflow page locations */
#endif
};

/*
** Potential values for BtCursor.eState.
**
** CURSOR_VALID:
**   Cursor points to a valid entry. getPayload() etc. may be called.
**
** CURSOR_INVALID:
**   Cursor does not point to a valid entry. This can happen (for example) 
**   because the table is empty or because BtreeCursorFirst() has not been
**   called.
**
** CURSOR_REQUIRESEEK:
**   The table that this cursor was opened on still exists, but has been 
**   modified since the cursor was last used. The cursor position is saved
**   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in 
**   this state, restoreOrClearCursorPosition() can be called to attempt to
**   seek the cursor to the saved position.
*/
#define CURSOR_INVALID           0
#define CURSOR_VALID             1
#define CURSOR_REQUIRESEEK       2

/*
** The TRACE macro will print high-level status information about the
** btree operation when the global variable sqlite3_btree_trace is
** enabled.
*/
#if SQLITE_TEST
# define TRACE(X)   if( sqlite3_btree_trace ){ printf X; fflush(stdout); }
#else
# define TRACE(X)
#endif

/*
** Routines to read and write variable-length integers.  These used to
** be defined locally, but now we use the varint routines in the util.c
** file.
*/
#define getVarint    sqlite3GetVarint
#define getVarint32(A,B)  ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))
#define putVarint    sqlite3PutVarint

/* The database page the PENDING_BYTE occupies. This page is never used.
** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
** should possibly be consolidated (presumably in pager.h).
**
** If disk I/O is omitted (meaning that the database is stored purely
** in memory) then there is no pending byte.
*/
#ifdef SQLITE_OMIT_DISKIO
# define PENDING_BYTE_PAGE(pBt)  0x7fffffff
#else
# define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)
#endif

/*
** A linked list of the following structures is stored at BtShared.pLock.
** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
** is opened on the table with root page BtShared.iTable. Locks are removed
** from this list when a transaction is committed or rolled back, or when
** a btree handle is closed.
*/
struct BtLock {
  Btree *pBtree;        /* Btree handle holding this lock */
  Pgno iTable;          /* Root page of table */
  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
  BtLock *pNext;        /* Next in BtShared.pLock list */
};

/* Candidate values for BtLock.eLock */
#define READ_LOCK     1
#define WRITE_LOCK    2

/*
** These macros define the location of the pointer-map entry for a 
** database page. The first argument to each is the number of usable
** bytes on each page of the database (often 1024). The second is the
** page number to look up in the pointer map.
**
** PTRMAP_PAGENO returns the database page number of the pointer-map
** page that stores the required pointer. PTRMAP_PTROFFSET returns
** the offset of the requested map entry.
**
** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
** this test.
*/
#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
#define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))
#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))

/*
** The pointer map is a lookup table that identifies the parent page for
** each child page in the database file.  The parent page is the page that
** contains a pointer to the child.  Every page in the database contains
** 0 or 1 parent pages.  (In this context 'database page' refers
** to any page that is not part of the pointer map itself.)  Each pointer map
** entry consists of a single byte 'type' and a 4 byte parent page number.
** The PTRMAP_XXX identifiers below are the valid types.
**
** The purpose of the pointer map is to facility moving pages from one
** position in the file to another as part of autovacuum.  When a page
** is moved, the pointer in its parent must be updated to point to the
** new location.  The pointer map is used to locate the parent page quickly.
**
** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**
** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
** PTRMAP_OVERFLOW1: The database page is the first page in a list of 
**                   overflow pages. The page number identifies the page that
**                   contains the cell with a pointer to this overflow page.
**
** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
**                   overflow pages. The page-number identifies the previous
**                   page in the overflow page list.
**
** PTRMAP_BTREE: The database page is a non-root btree page. The page number
**               identifies the parent page in the btree.
*/
#define PTRMAP_ROOTPAGE 1
#define PTRMAP_FREEPAGE 2
#define PTRMAP_OVERFLOW1 3
#define PTRMAP_OVERFLOW2 4
#define PTRMAP_BTREE 5

/* A bunch of assert() statements to check the transaction state variables
** of handle p (type Btree*) are internally consistent.
*/
#define btreeIntegrity(p) \
  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
  assert( p->pBt->inTransaction>=p->inTrans ); 


/*
** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
** if the database supports auto-vacuum or not. Because it is used
** within an expression that is an argument to another macro 
** (sqliteMallocRaw), it is not possible to use conditional compilation.
** So, this macro is defined instead.
*/
#ifndef SQLITE_OMIT_AUTOVACUUM
#define ISAUTOVACUUM (pBt->autoVacuum)
#else
#define ISAUTOVACUUM 0
#endif


/*
** This structure is passed around through all the sanity checking routines
** in order to keep track of some global state information.
*/
typedef struct IntegrityCk IntegrityCk;
struct IntegrityCk {
  BtShared *pBt;    /* The tree being checked out */
  Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
  int nPage;        /* Number of pages in the database */
  int *anRef;       /* Number of times each page is referenced */
  int mxErr;        /* Stop accumulating errors when this reaches zero */
  char *zErrMsg;    /* An error message.  NULL if no errors seen. */
  int nErr;         /* Number of messages written to zErrMsg so far */
};

/*
** Read or write a two- and four-byte big-endian integer values.
*/
#define get2byte sqlite3Get2byte
#define get4byte sqlite3Get4byte
#define put2byte sqlite3Put2byte
#define put4byte sqlite3Put4byte

Added src/malloc.c.















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
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
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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
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
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
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
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
700
701
702
703
704
705
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
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Memory allocation functions used throughout sqlite.
**
**
** $Id: malloc.c,v 1.1 2007/05/05 11:48:54 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <stdarg.h>
#include <ctype.h>

/*
** MALLOC WRAPPER ARCHITECTURE
**
** The sqlite code accesses dynamic memory allocation/deallocation by invoking
** the following six APIs (which may be implemented as macros).
**
**     sqlite3Malloc()
**     sqlite3MallocRaw()
**     sqlite3Realloc()
**     sqlite3ReallocOrFree()
**     sqlite3Free()
**     sqlite3AllocSize()
**
** The function sqlite3FreeX performs the same task as sqlite3Free and is
** guaranteed to be a real function. The same holds for sqlite3MallocX
**
** The above APIs are implemented in terms of the functions provided in the
** operating-system interface. The OS interface is never accessed directly
** by code outside of this file.
**
**     sqlite3OsMalloc()
**     sqlite3OsRealloc()
**     sqlite3OsFree()
**     sqlite3OsAllocationSize()
**
** Functions sqlite3MallocRaw() and sqlite3Realloc() may invoke 
** sqlite3_release_memory() if a call to sqlite3OsMalloc() or
** sqlite3OsRealloc() fails (or if the soft-heap-limit for the thread is
** exceeded). Function sqlite3Malloc() usually invokes
** sqlite3MallocRaw().
**
** MALLOC TEST WRAPPER ARCHITECTURE
**
** The test wrapper provides extra test facilities to ensure the library 
** does not leak memory and handles the failure of the underlying OS level
** allocation system correctly. It is only present if the library is 
** compiled with the SQLITE_MEMDEBUG macro set.
**
**     * Guardposts to detect overwrites.
**     * Ability to cause a specific Malloc() or Realloc() to fail.
**     * Audit outstanding memory allocations (i.e check for leaks).
*/

#define MAX(x,y) ((x)>(y)?(x):(y))

#if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) && !defined(SQLITE_OMIT_DISKIO)
/*
** Set the soft heap-size limit for the current thread. Passing a negative
** value indicates no limit.
*/
void sqlite3_soft_heap_limit(int n){
  ThreadData *pTd = sqlite3ThreadData();
  if( pTd ){
    pTd->nSoftHeapLimit = n;
  }
  sqlite3ReleaseThreadData();
}

/*
** Release memory held by SQLite instances created by the current thread.
*/
int sqlite3_release_memory(int n){
  return sqlite3PagerReleaseMemory(n);
}
#else
/* If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, then define a version
** of sqlite3_release_memory() to be used by other code in this file.
** This is done for no better reason than to reduce the number of 
** pre-processor #ifndef statements.
*/
#define sqlite3_release_memory(x) 0    /* 0 == no memory freed */
#endif

#ifdef SQLITE_MEMDEBUG
/*--------------------------------------------------------------------------
** Begin code for memory allocation system test layer.
**
** Memory debugging is turned on by defining the SQLITE_MEMDEBUG macro.
**
** SQLITE_MEMDEBUG==1    -> Fence-posting only (thread safe) 
** SQLITE_MEMDEBUG==2    -> Fence-posting + linked list of allocations (not ts)
** SQLITE_MEMDEBUG==3    -> Above + backtraces (not thread safe, req. glibc)
*/

/* Figure out whether or not to store backtrace() information for each malloc.
** The backtrace() function is only used if SQLITE_MEMDEBUG is set to 2 or 
** greater and glibc is in use. If we don't want to use backtrace(), then just
** define it as an empty macro and set the amount of space reserved to 0.
*/
#if defined(__GLIBC__) && SQLITE_MEMDEBUG>2
  extern int backtrace(void **, int);
  #define TESTALLOC_STACKSIZE 128
  #define TESTALLOC_STACKFRAMES ((TESTALLOC_STACKSIZE-8)/sizeof(void*))
#else
  #define backtrace(x, y)
  #define TESTALLOC_STACKSIZE 0
  #define TESTALLOC_STACKFRAMES 0
#endif

/*
** Number of 32-bit guard words.  This should probably be a multiple of
** 2 since on 64-bit machines we want the value returned by sqliteMalloc()
** to be 8-byte aligned.
*/
#ifndef TESTALLOC_NGUARD
# define TESTALLOC_NGUARD 2
#endif

/*
** Size reserved for storing file-name along with each malloc()ed blob.
*/
#define TESTALLOC_FILESIZE 64

/*
** Size reserved for storing the user string. Each time a Malloc() or Realloc()
** call succeeds, up to TESTALLOC_USERSIZE bytes of the string pointed to by
** sqlite3_malloc_id are stored along with the other test system metadata.
*/
#define TESTALLOC_USERSIZE 64
const char *sqlite3_malloc_id = 0;

/*
** Blocks used by the test layer have the following format:
**
**        <sizeof(void *) pNext pointer>
**        <sizeof(void *) pPrev pointer>
**        <TESTALLOC_NGUARD 32-bit guard words>
**            <The application level allocation>
**        <TESTALLOC_NGUARD 32-bit guard words>
**        <32-bit line number>
**        <TESTALLOC_FILESIZE bytes containing null-terminated file name>
**        <TESTALLOC_STACKSIZE bytes of backtrace() output>
*/ 

#define TESTALLOC_OFFSET_GUARD1(p)    (sizeof(void *) * 2)
#define TESTALLOC_OFFSET_DATA(p) ( \
  TESTALLOC_OFFSET_GUARD1(p) + sizeof(u32) * TESTALLOC_NGUARD \
)
#define TESTALLOC_OFFSET_GUARD2(p) ( \
  TESTALLOC_OFFSET_DATA(p) + sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD \
)
#define TESTALLOC_OFFSET_LINENUMBER(p) ( \
  TESTALLOC_OFFSET_GUARD2(p) + sizeof(u32) * TESTALLOC_NGUARD \
)
#define TESTALLOC_OFFSET_FILENAME(p) ( \
  TESTALLOC_OFFSET_LINENUMBER(p) + sizeof(u32) \
)
#define TESTALLOC_OFFSET_USER(p) ( \
  TESTALLOC_OFFSET_FILENAME(p) + TESTALLOC_FILESIZE \
)
#define TESTALLOC_OFFSET_STACK(p) ( \
  TESTALLOC_OFFSET_USER(p) + TESTALLOC_USERSIZE + 8 - \
  (TESTALLOC_OFFSET_USER(p) % 8) \
)

#define TESTALLOC_OVERHEAD ( \
  sizeof(void *)*2 +                   /* pPrev and pNext pointers */   \
  TESTALLOC_NGUARD*sizeof(u32)*2 +              /* Guard words */       \
  sizeof(u32) + TESTALLOC_FILESIZE +   /* File and line number */       \
  TESTALLOC_USERSIZE +                 /* User string */                \
  TESTALLOC_STACKSIZE                  /* backtrace() stack */          \
)


/*
** For keeping track of the number of mallocs and frees.   This
** is used to check for memory leaks.  The iMallocFail and iMallocReset
** values are used to simulate malloc() failures during testing in 
** order to verify that the library correctly handles an out-of-memory
** condition.
*/
int sqlite3_nMalloc;         /* Number of sqliteMalloc() calls */
int sqlite3_nFree;           /* Number of sqliteFree() calls */
int sqlite3_memUsed;         /* TODO Total memory obtained from malloc */
int sqlite3_memMax;          /* TODO Mem usage high-water mark */
int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */

void *sqlite3_pFirst = 0;         /* Pointer to linked list of allocations */
int sqlite3_nMaxAlloc = 0;        /* High water mark of ThreadData.nAlloc */
int sqlite3_mallocDisallowed = 0; /* assert() in sqlite3Malloc() if set */
int sqlite3_isFail = 0;           /* True if all malloc calls should fail */
const char *sqlite3_zFile = 0;    /* Filename to associate debug info with */
int sqlite3_iLine = 0;            /* Line number for debug info */

/*
** Check for a simulated memory allocation failure.  Return true if
** the failure should be simulated.  Return false to proceed as normal.
*/
int sqlite3TestMallocFail(){
  if( sqlite3_isFail ){
    return 1;
  }
  if( sqlite3_iMallocFail>=0 ){
    sqlite3_iMallocFail--;
    if( sqlite3_iMallocFail==0 ){
      sqlite3_iMallocFail = sqlite3_iMallocReset;
      sqlite3_isFail = 1;
      return 1;
    }
  }
  return 0;
}

/*
** The argument is a pointer returned by sqlite3OsMalloc() or xRealloc().
** assert() that the first and last (TESTALLOC_NGUARD*4) bytes are set to the
** values set by the applyGuards() function.
*/
static void checkGuards(u32 *p)
{
  int i;
  char *zAlloc = (char *)p;
  char *z;

  /* First set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    assert(((u32 *)z)[i]==0xdead1122);
  }

  /* Second set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    u32 guard = 0;
    memcpy(&guard, &z[i*sizeof(u32)], sizeof(u32));
    assert(guard==0xdead3344);
  }
}

/*
** The argument is a pointer returned by sqlite3OsMalloc() or Realloc(). The
** first and last (TESTALLOC_NGUARD*4) bytes are set to known values for use as 
** guard-posts.
*/
static void applyGuards(u32 *p)
{
  int i;
  char *z;
  char *zAlloc = (char *)p;

  /* First set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    ((u32 *)z)[i] = 0xdead1122;
  }

  /* Second set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    static const int guard = 0xdead3344;
    memcpy(&z[i*sizeof(u32)], &guard, sizeof(u32));
  }

  /* Line number */
  z = &((char *)z)[TESTALLOC_NGUARD*sizeof(u32)];             /* Guard words */
  z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
  memcpy(z, &sqlite3_iLine, sizeof(u32));

  /* File name */
  z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
  strncpy(z, sqlite3_zFile, TESTALLOC_FILESIZE);
  z[TESTALLOC_FILESIZE - 1] = '\0';

  /* User string */
  z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
  z[0] = 0;
  if( sqlite3_malloc_id ){
    strncpy(z, sqlite3_malloc_id, TESTALLOC_USERSIZE);
    z[TESTALLOC_USERSIZE-1] = 0;
  }

  /* backtrace() stack */
  z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
  backtrace((void **)z, TESTALLOC_STACKFRAMES);

  /* Sanity check to make sure checkGuards() is working */
  checkGuards(p);
}

/*
** The argument is a malloc()ed pointer as returned by the test-wrapper.
** Return a pointer to the Os level allocation.
*/
static void *getOsPointer(void *p)
{
  char *z = (char *)p;
  return (void *)(&z[-1 * TESTALLOC_OFFSET_DATA(p)]);
}


#if SQLITE_MEMDEBUG>1
/*
** The argument points to an Os level allocation. Link it into the threads list
** of allocations.
*/
static void linkAlloc(void *p){
  void **pp = (void **)p;
  pp[0] = 0;
  pp[1] = sqlite3_pFirst;
  if( sqlite3_pFirst ){
    ((void **)sqlite3_pFirst)[0] = p;
  }
  sqlite3_pFirst = p;
}

/*
** The argument points to an Os level allocation. Unlinke it from the threads
** list of allocations.
*/
static void unlinkAlloc(void *p)
{
  void **pp = (void **)p;
  if( p==sqlite3_pFirst ){
    assert(!pp[0]);
    assert(!pp[1] || ((void **)(pp[1]))[0]==p);
    sqlite3_pFirst = pp[1];
    if( sqlite3_pFirst ){
      ((void **)sqlite3_pFirst)[0] = 0;
    }
  }else{
    void **pprev = pp[0];
    void **pnext = pp[1];
    assert(pprev);
    assert(pprev[1]==p);
    pprev[1] = (void *)pnext;
    if( pnext ){
      assert(pnext[0]==p);
      pnext[0] = (void *)pprev;
    }
  }
}

/*
** Pointer p is a pointer to an OS level allocation that has just been
** realloc()ed. Set the list pointers that point to this entry to it's new
** location.
*/
static void relinkAlloc(void *p)
{
  void **pp = (void **)p;
  if( pp[0] ){
    ((void **)(pp[0]))[1] = p;
  }else{
    sqlite3_pFirst = p;
  }
  if( pp[1] ){
    ((void **)(pp[1]))[0] = p;
  }
}
#else
#define linkAlloc(x)
#define relinkAlloc(x)
#define unlinkAlloc(x)
#endif

/*
** This function sets the result of the Tcl interpreter passed as an argument
** to a list containing an entry for each currently outstanding call made to 
** sqliteMalloc and friends by the current thread. Each list entry is itself a
** list, consisting of the following (in order):
**
**     * The number of bytes allocated
**     * The __FILE__ macro at the time of the sqliteMalloc() call.
**     * The __LINE__ macro ...
**     * The value of the sqlite3_malloc_id variable ...
**     * The output of backtrace() (if available) ...
**
** Todo: We could have a version of this function that outputs to stdout, 
** to debug memory leaks when Tcl is not available.
*/
#if defined(TCLSH) && defined(SQLITE_DEBUG) && SQLITE_MEMDEBUG>1
#include <tcl.h>
int sqlite3OutstandingMallocs(Tcl_Interp *interp){
  void *p;
  Tcl_Obj *pRes = Tcl_NewObj();
  Tcl_IncrRefCount(pRes);


  for(p=sqlite3_pFirst; p; p=((void **)p)[1]){
    Tcl_Obj *pEntry = Tcl_NewObj();
    Tcl_Obj *pStack = Tcl_NewObj();
    char *z;
    u32 iLine;
    int nBytes = sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD;
    char *zAlloc = (char *)p;
    int i;

    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(nBytes));

    z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));

    z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
    memcpy(&iLine, z, sizeof(u32));
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(iLine));

    z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));

    z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
    for(i=0; i<TESTALLOC_STACKFRAMES; i++){
      char zHex[128];
      sqlite3_snprintf(sizeof(zHex), zHex, "%p", ((void **)z)[i]);
      Tcl_ListObjAppendElement(0, pStack, Tcl_NewStringObj(zHex, -1));
    }

    Tcl_ListObjAppendElement(0, pEntry, pStack);
    Tcl_ListObjAppendElement(0, pRes, pEntry);
  }

  Tcl_ResetResult(interp);
  Tcl_SetObjResult(interp, pRes);
  Tcl_DecrRefCount(pRes);
  return TCL_OK;
}
#endif

/*
** This is the test layer's wrapper around sqlite3OsMalloc().
*/
static void * OSMALLOC(int n){
  sqlite3OsEnterMutex();
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  sqlite3_nMaxAlloc = 
      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
#endif
  assert( !sqlite3_mallocDisallowed );
  if( !sqlite3TestMallocFail() ){
    u32 *p;
    p = (u32 *)sqlite3OsMalloc(n + TESTALLOC_OVERHEAD);
    assert(p);
    sqlite3_nMalloc++;
    applyGuards(p);
    linkAlloc(p);
    sqlite3OsLeaveMutex();
    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
  }
  sqlite3OsLeaveMutex();
  return 0;
}

static int OSSIZEOF(void *p){
  if( p ){
    u32 *pOs = (u32 *)getOsPointer(p);
    return sqlite3OsAllocationSize(pOs) - TESTALLOC_OVERHEAD;
  }
  return 0;
}

/*
** This is the test layer's wrapper around sqlite3OsFree(). The argument is a
** pointer to the space allocated for the application to use.
*/
static void OSFREE(void *pFree){
  u32 *p;         /* Pointer to the OS-layer allocation */
  sqlite3OsEnterMutex();
  p = (u32 *)getOsPointer(pFree);
  checkGuards(p);
  unlinkAlloc(p);
  memset(pFree, 0x55, OSSIZEOF(pFree));
  sqlite3OsFree(p);
  sqlite3_nFree++;
  sqlite3OsLeaveMutex();
}

/*
** This is the test layer's wrapper around sqlite3OsRealloc().
*/
static void * OSREALLOC(void *pRealloc, int n){
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  sqlite3_nMaxAlloc = 
      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
#endif
  assert( !sqlite3_mallocDisallowed );
  if( !sqlite3TestMallocFail() ){
    u32 *p = (u32 *)getOsPointer(pRealloc);
    checkGuards(p);
    p = sqlite3OsRealloc(p, n + TESTALLOC_OVERHEAD);
    applyGuards(p);
    relinkAlloc(p);
    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
  }
  return 0;
}

static void OSMALLOC_FAILED(){
  sqlite3_isFail = 0;
}

#else
/* Define macros to call the sqlite3OsXXX interface directly if 
** the SQLITE_MEMDEBUG macro is not defined.
*/
#define OSMALLOC(x)        sqlite3OsMalloc(x)
#define OSREALLOC(x,y)     sqlite3OsRealloc(x,y)
#define OSFREE(x)          sqlite3OsFree(x)
#define OSSIZEOF(x)        sqlite3OsAllocationSize(x)
#define OSMALLOC_FAILED()

#endif  /* SQLITE_MEMDEBUG */
/*
** End code for memory allocation system test layer.
**--------------------------------------------------------------------------*/

/*
** This routine is called when we are about to allocate n additional bytes
** of memory.  If the new allocation will put is over the soft allocation
** limit, then invoke sqlite3_release_memory() to try to release some
** memory before continuing with the allocation.
**
** This routine also makes sure that the thread-specific-data (TSD) has
** be allocated.  If it has not and can not be allocated, then return
** false.  The updateMemoryUsedCount() routine below will deallocate
** the TSD if it ought to be.
**
** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
** a no-op
*/ 
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
static int enforceSoftLimit(int n){
  ThreadData *pTsd = sqlite3ThreadData();
  if( pTsd==0 ){
    return 0;
  }
  assert( pTsd->nAlloc>=0 );
  if( n>0 && pTsd->nSoftHeapLimit>0 ){
    while( pTsd->nAlloc+n>pTsd->nSoftHeapLimit && sqlite3_release_memory(n) ){}
  }
  return 1;
}
#else
# define enforceSoftLimit(X)  1
#endif

/*
** Update the count of total outstanding memory that is held in
** thread-specific-data (TSD).  If after this update the TSD is
** no longer being used, then deallocate it.
**
** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
** a no-op
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
static void updateMemoryUsedCount(int n){
  ThreadData *pTsd = sqlite3ThreadData();
  if( pTsd ){
    pTsd->nAlloc += n;
    assert( pTsd->nAlloc>=0 );
    if( pTsd->nAlloc==0 && pTsd->nSoftHeapLimit==0 ){
      sqlite3ReleaseThreadData();
    }
  }
}
#else
#define updateMemoryUsedCount(x)  /* no-op */
#endif

/*
** Allocate and return N bytes of uninitialised memory by calling
** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
** by calling sqlite3_release_memory().
*/
void *sqlite3MallocRaw(int n, int doMemManage){
  void *p = 0;
  if( n>0 && !sqlite3MallocFailed() && (!doMemManage || enforceSoftLimit(n)) ){
    while( (p = OSMALLOC(n))==0 && sqlite3_release_memory(n) ){}
    if( !p ){
      sqlite3FailedMalloc();
      OSMALLOC_FAILED();
    }else if( doMemManage ){
      updateMemoryUsedCount(OSSIZEOF(p));
    }
  }
  return p;
}

/*
** Resize the allocation at p to n bytes by calling sqlite3OsRealloc(). The
** pointer to the new allocation is returned.  If the Realloc() call fails,
** attempt to free memory by calling sqlite3_release_memory().
*/
void *sqlite3Realloc(void *p, int n){
  if( sqlite3MallocFailed() ){
    return 0;
  }

  if( !p ){
    return sqlite3Malloc(n, 1);
  }else{
    void *np = 0;
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
    int origSize = OSSIZEOF(p);
#endif
    if( enforceSoftLimit(n - origSize) ){
      while( (np = OSREALLOC(p, n))==0 && sqlite3_release_memory(n) ){}
      if( !np ){
        sqlite3FailedMalloc();
        OSMALLOC_FAILED();
      }else{
        updateMemoryUsedCount(OSSIZEOF(np) - origSize);
      }
    }
    return np;
  }
}

/*
** Free the memory pointed to by p. p must be either a NULL pointer or a 
** value returned by a previous call to sqlite3Malloc() or sqlite3Realloc().
*/
void sqlite3FreeX(void *p){
  if( p ){
    updateMemoryUsedCount(0 - OSSIZEOF(p));
    OSFREE(p);
  }
}

/*
** A version of sqliteMalloc() that is always a function, not a macro.
** Currently, this is used only to alloc to allocate the parser engine.
*/
void *sqlite3MallocX(int n){
  return sqliteMalloc(n);
}

/*
** sqlite3Malloc
** sqlite3ReallocOrFree
**
** These two are implemented as wrappers around sqlite3MallocRaw(), 
** sqlite3Realloc() and sqlite3Free().
*/ 
void *sqlite3Malloc(int n, int doMemManage){
  void *p = sqlite3MallocRaw(n, doMemManage);
  if( p ){
    memset(p, 0, n);
  }
  return p;
}
void *sqlite3ReallocOrFree(void *p, int n){
  void *pNew;
  pNew = sqlite3Realloc(p, n);
  if( !pNew ){
    sqlite3FreeX(p);
  }
  return pNew;
}

/*
** sqlite3ThreadSafeMalloc() and sqlite3ThreadSafeFree() are used in those
** rare scenarios where sqlite may allocate memory in one thread and free
** it in another. They are exactly the same as sqlite3Malloc() and 
** sqlite3Free() except that:
**
**   * The allocated memory is not included in any calculations with 
**     respect to the soft-heap-limit, and
**
**   * sqlite3ThreadSafeMalloc() must be matched with ThreadSafeFree(),
**     not sqlite3Free(). Calling sqlite3Free() on memory obtained from
**     ThreadSafeMalloc() will cause an error somewhere down the line.
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
void *sqlite3ThreadSafeMalloc(int n){
  (void)ENTER_MALLOC;
  return sqlite3Malloc(n, 0);
}
void sqlite3ThreadSafeFree(void *p){
  (void)ENTER_MALLOC;
  if( p ){
    OSFREE(p);
  }
}
#endif


/*
** Return the number of bytes allocated at location p. p must be either 
** a NULL pointer (in which case 0 is returned) or a pointer returned by 
** sqlite3Malloc(), sqlite3Realloc() or sqlite3ReallocOrFree().
**
** The number of bytes allocated does not include any overhead inserted by 
** any malloc() wrapper functions that may be called. So the value returned
** is the number of bytes that were available to SQLite using pointer p, 
** regardless of how much memory was actually allocated.
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
int sqlite3AllocSize(void *p){
  return OSSIZEOF(p);
}
#endif

/*
** Make a copy of a string in memory obtained from sqliteMalloc(). These 
** functions call sqlite3MallocRaw() directly instead of sqliteMalloc(). This
** is because when memory debugging is turned on, these two functions are 
** called via macros that record the current file and line number in the
** ThreadData structure.
*/
char *sqlite3StrDup(const char *z){
  char *zNew;
  int n;
  if( z==0 ) return 0;
  n = strlen(z)+1;
  zNew = sqlite3MallocRaw(n, 1);
  if( zNew ) memcpy(zNew, z, n);
  return zNew;
}
char *sqlite3StrNDup(const char *z, int n){
  char *zNew;
  if( z==0 ) return 0;
  zNew = sqlite3MallocRaw(n+1, 1);
  if( zNew ){
    memcpy(zNew, z, n);
    zNew[n] = 0;
  }
  return zNew;
}

/*
** Create a string from the 2nd and subsequent arguments (up to the
** first NULL argument), store the string in memory obtained from
** sqliteMalloc() and make the pointer indicated by the 1st argument
** point to that string.  The 1st argument must either be NULL or 
** point to memory obtained from sqliteMalloc().
*/
void sqlite3SetString(char **pz, ...){
  va_list ap;
  int nByte;
  const char *z;
  char *zResult;

  assert( pz!=0 );
  nByte = 1;
  va_start(ap, pz);
  while( (z = va_arg(ap, const char*))!=0 ){
    nByte += strlen(z);
  }
  va_end(ap);
  sqliteFree(*pz);
  *pz = zResult = sqliteMallocRaw( nByte );
  if( zResult==0 ){
    return;
  }
  *zResult = 0;
  va_start(ap, pz);
  while( (z = va_arg(ap, const char*))!=0 ){
    int n = strlen(z);
    memcpy(zResult, z, n);
    zResult += n;
  }
  zResult[0] = 0;
  va_end(ap);
}


/*
** This function must be called before exiting any API function (i.e. 
** returning control to the user) that has called sqlite3Malloc or
** sqlite3Realloc.
**
** The returned value is normally a copy of the second argument to this
** function. However, if a malloc() failure has occured since the previous
** invocation SQLITE_NOMEM is returned instead. 
**
** If the first argument, db, is not NULL and a malloc() error has occured,
** then the connection error-code (the value returned by sqlite3_errcode())
** is set to SQLITE_NOMEM.
*/
static int mallocHasFailed = 0;
int sqlite3ApiExit(sqlite3* db, int rc){
  if( sqlite3MallocFailed() ){
    mallocHasFailed = 0;
    sqlite3OsLeaveMutex();
    sqlite3Error(db, SQLITE_NOMEM, 0);
    rc = SQLITE_NOMEM;
  }
  return rc & (db ? db->errMask : 0xff);
}

/* 
** Return true is a malloc has failed in this thread since the last call
** to sqlite3ApiExit(), or false otherwise.
*/
int sqlite3MallocFailed(){
  return (mallocHasFailed && sqlite3OsInMutex(1));
}

/* 
** Set the "malloc has failed" condition to true for this thread.
*/
void sqlite3FailedMalloc(){
  if( !sqlite3MallocFailed() ){
    sqlite3OsEnterMutex();
    assert( mallocHasFailed==0 );
    mallocHasFailed = 1;
  }
}

#ifdef SQLITE_MEMDEBUG
/*
** This function sets a flag in the thread-specific-data structure that will
** cause an assert to fail if sqliteMalloc() or sqliteRealloc() is called.
*/
void sqlite3MallocDisallow(){
  assert( sqlite3_mallocDisallowed>=0 );
  sqlite3_mallocDisallowed++;
}

/*
** This function clears the flag set in the thread-specific-data structure set
** by sqlite3MallocDisallow().
*/
void sqlite3MallocAllow(){
  assert( sqlite3_mallocDisallowed>0 );
  sqlite3_mallocDisallowed--;
}
#endif

Changes to src/pager.c.

14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
...
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
...
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.335 2007/05/04 13:15:56 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
**
** All values are stored on disk as big-endian.
*/
static int read32bits(OsFile *fd, u32 *pRes){
  unsigned char ac[4];
  int rc = sqlite3OsRead(fd, ac, sizeof(ac));
  if( rc==SQLITE_OK ){
    *pRes = (ac[0]<<24) | (ac[1]<<16) | (ac[2]<<8) | ac[3];
  }
  return rc;
}

/*
** Write a 32-bit integer into a string buffer in big-endian byte order.
*/
static void put32bits(char *ac, u32 val){
  ac[0] = (val>>24) & 0xff;
  ac[1] = (val>>16) & 0xff;
  ac[2] = (val>>8) & 0xff;
  ac[3] = val & 0xff;
}

/*
** Write a 32-bit integer into the given file descriptor.  Return SQLITE_OK
** on success or an error code is something goes wrong.
*/
static int write32bits(OsFile *fd, u32 val){
  char ac[4];
................................................................................
/*
** Read a 32-bit integer at offset 'offset' from the page identified by
** page header 'p'.
*/
static u32 retrieve32bits(PgHdr *p, int offset){
  unsigned char *ac;
  ac = &((unsigned char*)PGHDR_TO_DATA(p))[offset];
  return (ac[0]<<24) | (ac[1]<<16) | (ac[2]<<8) | ac[3];
}


/*
** This function should be called when an error occurs within the pager
** code. The first argument is a pointer to the pager structure, the
** second the error-code about to be returned by a pager API function. 







|







 







|







|
<
<
<
<
<







 







|







14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
...
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469





470
471
472
473
474
475
476
...
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.336 2007/05/05 11:48:54 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>
................................................................................
**
** All values are stored on disk as big-endian.
*/
static int read32bits(OsFile *fd, u32 *pRes){
  unsigned char ac[4];
  int rc = sqlite3OsRead(fd, ac, sizeof(ac));
  if( rc==SQLITE_OK ){
    *pRes = sqlite3Get4byte(ac);
  }
  return rc;
}

/*
** Write a 32-bit integer into a string buffer in big-endian byte order.
*/
#define put32bits(A,B)  sqlite3Put4byte((u8*)A,B)






/*
** Write a 32-bit integer into the given file descriptor.  Return SQLITE_OK
** on success or an error code is something goes wrong.
*/
static int write32bits(OsFile *fd, u32 val){
  char ac[4];
................................................................................
/*
** Read a 32-bit integer at offset 'offset' from the page identified by
** page header 'p'.
*/
static u32 retrieve32bits(PgHdr *p, int offset){
  unsigned char *ac;
  ac = &((unsigned char*)PGHDR_TO_DATA(p))[offset];
  return sqlite3Get4byte(ac);
}


/*
** This function should be called when an error occurs within the pager
** code. The first argument is a pointer to the pager structure, the
** second the error-code about to be returned by a pager API function. 

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1910
1911
1912
1913
1914
1915
1916





1917
1918
1919
1920
1921
1922
1923
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.556 2007/05/04 18:30:41 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

#if defined(SQLITE_TCL) || defined(TCLSH)
# include <tcl.h>
#endif
................................................................................
int sqlite3VtabCallCreate(sqlite3*, int, const char *, char **);
int sqlite3VtabCallConnect(Parse*, Table*);
int sqlite3VtabCallDestroy(sqlite3*, int, const char *);
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);






#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

/*
** If the SQLITE_ENABLE IOTRACE exists then the global variable







|







 







>
>
>
>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.557 2007/05/05 11:48:54 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

#if defined(SQLITE_TCL) || defined(TCLSH)
# include <tcl.h>
#endif
................................................................................
int sqlite3VtabCallCreate(sqlite3*, int, const char *, char **);
int sqlite3VtabCallConnect(Parse*, Table*);
int sqlite3VtabCallDestroy(sqlite3*, int, const char *);
int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
FuncDef *sqlite3VtabOverloadFunction(FuncDef*, int nArg, Expr*);
void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
int sqlite3Reprepare(Vdbe*);

u32 sqlite3Get2byte(const u8*);
u32 sqlite3Get4byte(const u8*);
void sqlite3Put2byte(u8*, u32);
void sqlite3Put4byte(u8*, u32);

#ifdef SQLITE_SSE
#include "sseInt.h"
#endif

/*
** If the SQLITE_ENABLE IOTRACE exists then the global variable

Changes to src/test1.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
26
27
28
29
30
31
32





































33
34
35
36
37
38
39
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.244 2007/05/04 19:03:03 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
** tclsqlite.c.  We need it here so that the get_sqlite_pointer routine
** can extract the sqlite3* pointer from an existing Tcl SQLite
** connection.
*/
struct SqliteDb {
  sqlite3 *db;
};






































/*
** A TCL command that returns the address of the sqlite* pointer
** for an sqlite connection instance.  Bad things happen if the
** input is not an sqlite connection.
*/
static int get_sqlite_pointer(







|







 







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







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
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
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing all sorts of SQLite interfaces.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test1.c,v 1.245 2007/05/05 11:48:54 drh Exp $
*/
#include "sqliteInt.h"
#include "tcl.h"
#include "os.h"
#include <stdlib.h>
#include <string.h>

................................................................................
** tclsqlite.c.  We need it here so that the get_sqlite_pointer routine
** can extract the sqlite3* pointer from an existing Tcl SQLite
** connection.
*/
struct SqliteDb {
  sqlite3 *db;
};

/*
** Convert text generated by the "%p" conversion format back into
** a pointer.
*/
static int testHexToInt(int h){
  if( h>='0' && h<='9' ){
    return h - '0';
  }else if( h>='a' && h<='f' ){
    return h - 'a' + 10;
  }else{
    assert( h>='A' && h<='F' );
    return h - 'A' + 10;
  }
}
void *sqlite3TextToPtr(const char *z){
  void *p;
  u64 v;
  u32 v2;
  if( z[0]=='0' && z[1]=='x' ){
    z += 2;
  }
  v = 0;
  while( *z ){
    v = (v<<4) + testHexToInt(*z);
    z++;
  }
  if( sizeof(p)==sizeof(v) ){
    memcpy(&p, &v, sizeof(p));
  }else{
    assert( sizeof(p)==sizeof(v2) );
    v2 = (u32)v;
    memcpy(&p, &v2, sizeof(p));
  }
  return p;
}


/*
** A TCL command that returns the address of the sqlite* pointer
** for an sqlite connection instance.  Bad things happen if the
** input is not an sqlite connection.
*/
static int get_sqlite_pointer(

Changes to src/util.c.

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
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
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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
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
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
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
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
700
701
702
703
704
705
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
....
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
....
1333
1334
1335
1336
1337
1338
1339























1340
1341
1342
1343
1344
1345
1346
....
1374
1375
1376
1377
1378
1379
1380
1381

1382
1383
1384





















1385
1386
1387
1388
1389
1390
1391







1392
1393
1394
1395
1396

1397
1398
1399










1400
1401
1402
1403



1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
....
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.200 2007/05/04 13:15:56 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <stdarg.h>
#include <ctype.h>

/*
** MALLOC WRAPPER ARCHITECTURE
**
** The sqlite code accesses dynamic memory allocation/deallocation by invoking
** the following six APIs (which may be implemented as macros).
**
**     sqlite3Malloc()
**     sqlite3MallocRaw()
**     sqlite3Realloc()
**     sqlite3ReallocOrFree()
**     sqlite3Free()
**     sqlite3AllocSize()
**
** The function sqlite3FreeX performs the same task as sqlite3Free and is
** guaranteed to be a real function. The same holds for sqlite3MallocX
**
** The above APIs are implemented in terms of the functions provided in the
** operating-system interface. The OS interface is never accessed directly
** by code outside of this file.
**
**     sqlite3OsMalloc()
**     sqlite3OsRealloc()
**     sqlite3OsFree()
**     sqlite3OsAllocationSize()
**
** Functions sqlite3MallocRaw() and sqlite3Realloc() may invoke 
** sqlite3_release_memory() if a call to sqlite3OsMalloc() or
** sqlite3OsRealloc() fails (or if the soft-heap-limit for the thread is
** exceeded). Function sqlite3Malloc() usually invokes
** sqlite3MallocRaw().
**
** MALLOC TEST WRAPPER ARCHITECTURE
**
** The test wrapper provides extra test facilities to ensure the library 
** does not leak memory and handles the failure of the underlying OS level
** allocation system correctly. It is only present if the library is 
** compiled with the SQLITE_MEMDEBUG macro set.
**
**     * Guardposts to detect overwrites.
**     * Ability to cause a specific Malloc() or Realloc() to fail.
**     * Audit outstanding memory allocations (i.e check for leaks).
*/

#define MAX(x,y) ((x)>(y)?(x):(y))

#if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) && !defined(SQLITE_OMIT_DISKIO)
/*
** Set the soft heap-size limit for the current thread. Passing a negative
** value indicates no limit.
*/
void sqlite3_soft_heap_limit(int n){
  ThreadData *pTd = sqlite3ThreadData();
  if( pTd ){
    pTd->nSoftHeapLimit = n;
  }
  sqlite3ReleaseThreadData();
}

/*
** Release memory held by SQLite instances created by the current thread.
*/
int sqlite3_release_memory(int n){
  return sqlite3PagerReleaseMemory(n);
}
#else
/* If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, then define a version
** of sqlite3_release_memory() to be used by other code in this file.
** This is done for no better reason than to reduce the number of 
** pre-processor #ifndef statements.
*/
#define sqlite3_release_memory(x) 0    /* 0 == no memory freed */
#endif

#ifdef SQLITE_MEMDEBUG
/*--------------------------------------------------------------------------
** Begin code for memory allocation system test layer.
**
** Memory debugging is turned on by defining the SQLITE_MEMDEBUG macro.
**
** SQLITE_MEMDEBUG==1    -> Fence-posting only (thread safe) 
** SQLITE_MEMDEBUG==2    -> Fence-posting + linked list of allocations (not ts)
** SQLITE_MEMDEBUG==3    -> Above + backtraces (not thread safe, req. glibc)
*/

/* Figure out whether or not to store backtrace() information for each malloc.
** The backtrace() function is only used if SQLITE_MEMDEBUG is set to 2 or 
** greater and glibc is in use. If we don't want to use backtrace(), then just
** define it as an empty macro and set the amount of space reserved to 0.
*/
#if defined(__GLIBC__) && SQLITE_MEMDEBUG>2
  extern int backtrace(void **, int);
  #define TESTALLOC_STACKSIZE 128
  #define TESTALLOC_STACKFRAMES ((TESTALLOC_STACKSIZE-8)/sizeof(void*))
#else
  #define backtrace(x, y)
  #define TESTALLOC_STACKSIZE 0
  #define TESTALLOC_STACKFRAMES 0
#endif

/*
** Number of 32-bit guard words.  This should probably be a multiple of
** 2 since on 64-bit machines we want the value returned by sqliteMalloc()
** to be 8-byte aligned.
*/
#ifndef TESTALLOC_NGUARD
# define TESTALLOC_NGUARD 2
#endif

/*
** Size reserved for storing file-name along with each malloc()ed blob.
*/
#define TESTALLOC_FILESIZE 64

/*
** Size reserved for storing the user string. Each time a Malloc() or Realloc()
** call succeeds, up to TESTALLOC_USERSIZE bytes of the string pointed to by
** sqlite3_malloc_id are stored along with the other test system metadata.
*/
#define TESTALLOC_USERSIZE 64
const char *sqlite3_malloc_id = 0;

/*
** Blocks used by the test layer have the following format:
**
**        <sizeof(void *) pNext pointer>
**        <sizeof(void *) pPrev pointer>
**        <TESTALLOC_NGUARD 32-bit guard words>
**            <The application level allocation>
**        <TESTALLOC_NGUARD 32-bit guard words>
**        <32-bit line number>
**        <TESTALLOC_FILESIZE bytes containing null-terminated file name>
**        <TESTALLOC_STACKSIZE bytes of backtrace() output>
*/ 

#define TESTALLOC_OFFSET_GUARD1(p)    (sizeof(void *) * 2)
#define TESTALLOC_OFFSET_DATA(p) ( \
  TESTALLOC_OFFSET_GUARD1(p) + sizeof(u32) * TESTALLOC_NGUARD \
)
#define TESTALLOC_OFFSET_GUARD2(p) ( \
  TESTALLOC_OFFSET_DATA(p) + sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD \
)
#define TESTALLOC_OFFSET_LINENUMBER(p) ( \
  TESTALLOC_OFFSET_GUARD2(p) + sizeof(u32) * TESTALLOC_NGUARD \
)
#define TESTALLOC_OFFSET_FILENAME(p) ( \
  TESTALLOC_OFFSET_LINENUMBER(p) + sizeof(u32) \
)
#define TESTALLOC_OFFSET_USER(p) ( \
  TESTALLOC_OFFSET_FILENAME(p) + TESTALLOC_FILESIZE \
)
#define TESTALLOC_OFFSET_STACK(p) ( \
  TESTALLOC_OFFSET_USER(p) + TESTALLOC_USERSIZE + 8 - \
  (TESTALLOC_OFFSET_USER(p) % 8) \
)

#define TESTALLOC_OVERHEAD ( \
  sizeof(void *)*2 +                   /* pPrev and pNext pointers */   \
  TESTALLOC_NGUARD*sizeof(u32)*2 +              /* Guard words */       \
  sizeof(u32) + TESTALLOC_FILESIZE +   /* File and line number */       \
  TESTALLOC_USERSIZE +                 /* User string */                \
  TESTALLOC_STACKSIZE                  /* backtrace() stack */          \
)


/*
** For keeping track of the number of mallocs and frees.   This
** is used to check for memory leaks.  The iMallocFail and iMallocReset
** values are used to simulate malloc() failures during testing in 
** order to verify that the library correctly handles an out-of-memory
** condition.
*/
int sqlite3_nMalloc;         /* Number of sqliteMalloc() calls */
int sqlite3_nFree;           /* Number of sqliteFree() calls */
int sqlite3_memUsed;         /* TODO Total memory obtained from malloc */
int sqlite3_memMax;          /* TODO Mem usage high-water mark */
int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */

void *sqlite3_pFirst = 0;         /* Pointer to linked list of allocations */
int sqlite3_nMaxAlloc = 0;        /* High water mark of ThreadData.nAlloc */
int sqlite3_mallocDisallowed = 0; /* assert() in sqlite3Malloc() if set */
int sqlite3_isFail = 0;           /* True if all malloc calls should fail */
const char *sqlite3_zFile = 0;    /* Filename to associate debug info with */
int sqlite3_iLine = 0;            /* Line number for debug info */

/*
** Check for a simulated memory allocation failure.  Return true if
** the failure should be simulated.  Return false to proceed as normal.
*/
int sqlite3TestMallocFail(){
  if( sqlite3_isFail ){
    return 1;
  }
  if( sqlite3_iMallocFail>=0 ){
    sqlite3_iMallocFail--;
    if( sqlite3_iMallocFail==0 ){
      sqlite3_iMallocFail = sqlite3_iMallocReset;
      sqlite3_isFail = 1;
      return 1;
    }
  }
  return 0;
}

/*
** The argument is a pointer returned by sqlite3OsMalloc() or xRealloc().
** assert() that the first and last (TESTALLOC_NGUARD*4) bytes are set to the
** values set by the applyGuards() function.
*/
static void checkGuards(u32 *p)
{
  int i;
  char *zAlloc = (char *)p;
  char *z;

  /* First set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    assert(((u32 *)z)[i]==0xdead1122);
  }

  /* Second set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    u32 guard = 0;
    memcpy(&guard, &z[i*sizeof(u32)], sizeof(u32));
    assert(guard==0xdead3344);
  }
}

/*
** The argument is a pointer returned by sqlite3OsMalloc() or Realloc(). The
** first and last (TESTALLOC_NGUARD*4) bytes are set to known values for use as 
** guard-posts.
*/
static void applyGuards(u32 *p)
{
  int i;
  char *z;
  char *zAlloc = (char *)p;

  /* First set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    ((u32 *)z)[i] = 0xdead1122;
  }

  /* Second set of guard words */
  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
  for(i=0; i<TESTALLOC_NGUARD; i++){
    static const int guard = 0xdead3344;
    memcpy(&z[i*sizeof(u32)], &guard, sizeof(u32));
  }

  /* Line number */
  z = &((char *)z)[TESTALLOC_NGUARD*sizeof(u32)];             /* Guard words */
  z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
  memcpy(z, &sqlite3_iLine, sizeof(u32));

  /* File name */
  z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
  strncpy(z, sqlite3_zFile, TESTALLOC_FILESIZE);
  z[TESTALLOC_FILESIZE - 1] = '\0';

  /* User string */
  z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
  z[0] = 0;
  if( sqlite3_malloc_id ){
    strncpy(z, sqlite3_malloc_id, TESTALLOC_USERSIZE);
    z[TESTALLOC_USERSIZE-1] = 0;
  }

  /* backtrace() stack */
  z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
  backtrace((void **)z, TESTALLOC_STACKFRAMES);

  /* Sanity check to make sure checkGuards() is working */
  checkGuards(p);
}

/*
** The argument is a malloc()ed pointer as returned by the test-wrapper.
** Return a pointer to the Os level allocation.
*/
static void *getOsPointer(void *p)
{
  char *z = (char *)p;
  return (void *)(&z[-1 * TESTALLOC_OFFSET_DATA(p)]);
}


#if SQLITE_MEMDEBUG>1
/*
** The argument points to an Os level allocation. Link it into the threads list
** of allocations.
*/
static void linkAlloc(void *p){
  void **pp = (void **)p;
  pp[0] = 0;
  pp[1] = sqlite3_pFirst;
  if( sqlite3_pFirst ){
    ((void **)sqlite3_pFirst)[0] = p;
  }
  sqlite3_pFirst = p;
}

/*
** The argument points to an Os level allocation. Unlinke it from the threads
** list of allocations.
*/
static void unlinkAlloc(void *p)
{
  void **pp = (void **)p;
  if( p==sqlite3_pFirst ){
    assert(!pp[0]);
    assert(!pp[1] || ((void **)(pp[1]))[0]==p);
    sqlite3_pFirst = pp[1];
    if( sqlite3_pFirst ){
      ((void **)sqlite3_pFirst)[0] = 0;
    }
  }else{
    void **pprev = pp[0];
    void **pnext = pp[1];
    assert(pprev);
    assert(pprev[1]==p);
    pprev[1] = (void *)pnext;
    if( pnext ){
      assert(pnext[0]==p);
      pnext[0] = (void *)pprev;
    }
  }
}

/*
** Pointer p is a pointer to an OS level allocation that has just been
** realloc()ed. Set the list pointers that point to this entry to it's new
** location.
*/
static void relinkAlloc(void *p)
{
  void **pp = (void **)p;
  if( pp[0] ){
    ((void **)(pp[0]))[1] = p;
  }else{
    sqlite3_pFirst = p;
  }
  if( pp[1] ){
    ((void **)(pp[1]))[0] = p;
  }
}
#else
#define linkAlloc(x)
#define relinkAlloc(x)
#define unlinkAlloc(x)
#endif

/*
** This function sets the result of the Tcl interpreter passed as an argument
** to a list containing an entry for each currently outstanding call made to 
** sqliteMalloc and friends by the current thread. Each list entry is itself a
** list, consisting of the following (in order):
**
**     * The number of bytes allocated
**     * The __FILE__ macro at the time of the sqliteMalloc() call.
**     * The __LINE__ macro ...
**     * The value of the sqlite3_malloc_id variable ...
**     * The output of backtrace() (if available) ...
**
** Todo: We could have a version of this function that outputs to stdout, 
** to debug memory leaks when Tcl is not available.
*/
#if defined(TCLSH) && defined(SQLITE_DEBUG) && SQLITE_MEMDEBUG>1
#include <tcl.h>
int sqlite3OutstandingMallocs(Tcl_Interp *interp){
  void *p;
  Tcl_Obj *pRes = Tcl_NewObj();
  Tcl_IncrRefCount(pRes);


  for(p=sqlite3_pFirst; p; p=((void **)p)[1]){
    Tcl_Obj *pEntry = Tcl_NewObj();
    Tcl_Obj *pStack = Tcl_NewObj();
    char *z;
    u32 iLine;
    int nBytes = sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD;
    char *zAlloc = (char *)p;
    int i;

    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(nBytes));

    z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));

    z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
    memcpy(&iLine, z, sizeof(u32));
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(iLine));

    z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));

    z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
    for(i=0; i<TESTALLOC_STACKFRAMES; i++){
      char zHex[128];
      sqlite3_snprintf(sizeof(zHex), zHex, "%p", ((void **)z)[i]);
      Tcl_ListObjAppendElement(0, pStack, Tcl_NewStringObj(zHex, -1));
    }

    Tcl_ListObjAppendElement(0, pEntry, pStack);
    Tcl_ListObjAppendElement(0, pRes, pEntry);
  }

  Tcl_ResetResult(interp);
  Tcl_SetObjResult(interp, pRes);
  Tcl_DecrRefCount(pRes);
  return TCL_OK;
}
#endif

/*
** This is the test layer's wrapper around sqlite3OsMalloc().
*/
static void * OSMALLOC(int n){
  sqlite3OsEnterMutex();
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  sqlite3_nMaxAlloc = 
      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
#endif
  assert( !sqlite3_mallocDisallowed );
  if( !sqlite3TestMallocFail() ){
    u32 *p;
    p = (u32 *)sqlite3OsMalloc(n + TESTALLOC_OVERHEAD);
    assert(p);
    sqlite3_nMalloc++;
    applyGuards(p);
    linkAlloc(p);
    sqlite3OsLeaveMutex();
    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
  }
  sqlite3OsLeaveMutex();
  return 0;
}

static int OSSIZEOF(void *p){
  if( p ){
    u32 *pOs = (u32 *)getOsPointer(p);
    return sqlite3OsAllocationSize(pOs) - TESTALLOC_OVERHEAD;
  }
  return 0;
}

/*
** This is the test layer's wrapper around sqlite3OsFree(). The argument is a
** pointer to the space allocated for the application to use.
*/
static void OSFREE(void *pFree){
  u32 *p;         /* Pointer to the OS-layer allocation */
  sqlite3OsEnterMutex();
  p = (u32 *)getOsPointer(pFree);
  checkGuards(p);
  unlinkAlloc(p);
  memset(pFree, 0x55, OSSIZEOF(pFree));
  sqlite3OsFree(p);
  sqlite3_nFree++;
  sqlite3OsLeaveMutex();
}

/*
** This is the test layer's wrapper around sqlite3OsRealloc().
*/
static void * OSREALLOC(void *pRealloc, int n){
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  sqlite3_nMaxAlloc = 
      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
#endif
  assert( !sqlite3_mallocDisallowed );
  if( !sqlite3TestMallocFail() ){
    u32 *p = (u32 *)getOsPointer(pRealloc);
    checkGuards(p);
    p = sqlite3OsRealloc(p, n + TESTALLOC_OVERHEAD);
    applyGuards(p);
    relinkAlloc(p);
    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
  }
  return 0;
}

static void OSMALLOC_FAILED(){
  sqlite3_isFail = 0;
}

#else
/* Define macros to call the sqlite3OsXXX interface directly if 
** the SQLITE_MEMDEBUG macro is not defined.
*/
#define OSMALLOC(x)        sqlite3OsMalloc(x)
#define OSREALLOC(x,y)     sqlite3OsRealloc(x,y)
#define OSFREE(x)          sqlite3OsFree(x)
#define OSSIZEOF(x)        sqlite3OsAllocationSize(x)
#define OSMALLOC_FAILED()

#endif  /* SQLITE_MEMDEBUG */
/*
** End code for memory allocation system test layer.
**--------------------------------------------------------------------------*/

/*
** This routine is called when we are about to allocate n additional bytes
** of memory.  If the new allocation will put is over the soft allocation
** limit, then invoke sqlite3_release_memory() to try to release some
** memory before continuing with the allocation.
**
** This routine also makes sure that the thread-specific-data (TSD) has
** be allocated.  If it has not and can not be allocated, then return
** false.  The updateMemoryUsedCount() routine below will deallocate
** the TSD if it ought to be.
**
** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
** a no-op
*/ 
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
static int enforceSoftLimit(int n){
  ThreadData *pTsd = sqlite3ThreadData();
  if( pTsd==0 ){
    return 0;
  }
  assert( pTsd->nAlloc>=0 );
  if( n>0 && pTsd->nSoftHeapLimit>0 ){
    while( pTsd->nAlloc+n>pTsd->nSoftHeapLimit && sqlite3_release_memory(n) ){}
  }
  return 1;
}
#else
# define enforceSoftLimit(X)  1
#endif

/*
** Update the count of total outstanding memory that is held in
** thread-specific-data (TSD).  If after this update the TSD is
** no longer being used, then deallocate it.
**
** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
** a no-op
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
static void updateMemoryUsedCount(int n){
  ThreadData *pTsd = sqlite3ThreadData();
  if( pTsd ){
    pTsd->nAlloc += n;
    assert( pTsd->nAlloc>=0 );
    if( pTsd->nAlloc==0 && pTsd->nSoftHeapLimit==0 ){
      sqlite3ReleaseThreadData();
    }
  }
}
#else
#define updateMemoryUsedCount(x)  /* no-op */
#endif

/*
** Allocate and return N bytes of uninitialised memory by calling
** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
** by calling sqlite3_release_memory().
*/
void *sqlite3MallocRaw(int n, int doMemManage){
  void *p = 0;
  if( n>0 && !sqlite3MallocFailed() && (!doMemManage || enforceSoftLimit(n)) ){
    while( (p = OSMALLOC(n))==0 && sqlite3_release_memory(n) ){}
    if( !p ){
      sqlite3FailedMalloc();
      OSMALLOC_FAILED();
    }else if( doMemManage ){
      updateMemoryUsedCount(OSSIZEOF(p));
    }
  }
  return p;
}

/*
** Resize the allocation at p to n bytes by calling sqlite3OsRealloc(). The
** pointer to the new allocation is returned.  If the Realloc() call fails,
** attempt to free memory by calling sqlite3_release_memory().
*/
void *sqlite3Realloc(void *p, int n){
  if( sqlite3MallocFailed() ){
    return 0;
  }

  if( !p ){
    return sqlite3Malloc(n, 1);
  }else{
    void *np = 0;
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
    int origSize = OSSIZEOF(p);
#endif
    if( enforceSoftLimit(n - origSize) ){
      while( (np = OSREALLOC(p, n))==0 && sqlite3_release_memory(n) ){}
      if( !np ){
        sqlite3FailedMalloc();
        OSMALLOC_FAILED();
      }else{
        updateMemoryUsedCount(OSSIZEOF(np) - origSize);
      }
    }
    return np;
  }
}

/*
** Free the memory pointed to by p. p must be either a NULL pointer or a 
** value returned by a previous call to sqlite3Malloc() or sqlite3Realloc().
*/
void sqlite3FreeX(void *p){
  if( p ){
    updateMemoryUsedCount(0 - OSSIZEOF(p));
    OSFREE(p);
  }
}

/*
** A version of sqliteMalloc() that is always a function, not a macro.
** Currently, this is used only to alloc to allocate the parser engine.
*/
void *sqlite3MallocX(int n){
  return sqliteMalloc(n);
}

/*
** sqlite3Malloc
** sqlite3ReallocOrFree
**
** These two are implemented as wrappers around sqlite3MallocRaw(), 
** sqlite3Realloc() and sqlite3Free().
*/ 
void *sqlite3Malloc(int n, int doMemManage){
  void *p = sqlite3MallocRaw(n, doMemManage);
  if( p ){
    memset(p, 0, n);
  }
  return p;
}
void *sqlite3ReallocOrFree(void *p, int n){
  void *pNew;
  pNew = sqlite3Realloc(p, n);
  if( !pNew ){
    sqlite3FreeX(p);
  }
  return pNew;
}

/*
** sqlite3ThreadSafeMalloc() and sqlite3ThreadSafeFree() are used in those
** rare scenarios where sqlite may allocate memory in one thread and free
** it in another. They are exactly the same as sqlite3Malloc() and 
** sqlite3Free() except that:
**
**   * The allocated memory is not included in any calculations with 
**     respect to the soft-heap-limit, and
**
**   * sqlite3ThreadSafeMalloc() must be matched with ThreadSafeFree(),
**     not sqlite3Free(). Calling sqlite3Free() on memory obtained from
**     ThreadSafeMalloc() will cause an error somewhere down the line.
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
void *sqlite3ThreadSafeMalloc(int n){
  (void)ENTER_MALLOC;
  return sqlite3Malloc(n, 0);
}
void sqlite3ThreadSafeFree(void *p){
  (void)ENTER_MALLOC;
  if( p ){
    OSFREE(p);
  }
}
#endif


/*
** Return the number of bytes allocated at location p. p must be either 
** a NULL pointer (in which case 0 is returned) or a pointer returned by 
** sqlite3Malloc(), sqlite3Realloc() or sqlite3ReallocOrFree().
**
** The number of bytes allocated does not include any overhead inserted by 
** any malloc() wrapper functions that may be called. So the value returned
** is the number of bytes that were available to SQLite using pointer p, 
** regardless of how much memory was actually allocated.
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
int sqlite3AllocSize(void *p){
  return OSSIZEOF(p);
}
#endif

/*
** Make a copy of a string in memory obtained from sqliteMalloc(). These 
** functions call sqlite3MallocRaw() directly instead of sqliteMalloc(). This
** is because when memory debugging is turned on, these two functions are 
** called via macros that record the current file and line number in the
** ThreadData structure.
*/
char *sqlite3StrDup(const char *z){
  char *zNew;
  int n;
  if( z==0 ) return 0;
  n = strlen(z)+1;
  zNew = sqlite3MallocRaw(n, 1);
  if( zNew ) memcpy(zNew, z, n);
  return zNew;
}
char *sqlite3StrNDup(const char *z, int n){
  char *zNew;
  if( z==0 ) return 0;
  zNew = sqlite3MallocRaw(n+1, 1);
  if( zNew ){
    memcpy(zNew, z, n);
    zNew[n] = 0;
  }
  return zNew;
}

/*
** Create a string from the 2nd and subsequent arguments (up to the
** first NULL argument), store the string in memory obtained from
** sqliteMalloc() and make the pointer indicated by the 1st argument
** point to that string.  The 1st argument must either be NULL or 
** point to memory obtained from sqliteMalloc().
*/
void sqlite3SetString(char **pz, ...){
  va_list ap;
  int nByte;
  const char *z;
  char *zResult;

  assert( pz!=0 );
  nByte = 1;
  va_start(ap, pz);
  while( (z = va_arg(ap, const char*))!=0 ){
    nByte += strlen(z);
  }
  va_end(ap);
  sqliteFree(*pz);
  *pz = zResult = sqliteMallocRaw( nByte );
  if( zResult==0 ){
    return;
  }
  *zResult = 0;
  va_start(ap, pz);
  while( (z = va_arg(ap, const char*))!=0 ){
    int n = strlen(z);
    memcpy(zResult, z, n);
    zResult += n;
  }
  zResult[0] = 0;
  va_end(ap);
}

/*
** Set the most recent error code and error string for the sqlite
** handle "db". The error code is set to "err_code".
**
** If it is not NULL, string zFormat specifies the format of the
** error string in the style of the printf functions: The following
................................................................................
  int i, c;
  if( *zNum=='-' || *zNum=='+' ) zNum++;
  for(i=0; (c=zNum[i])>='0' && c<='9'; i++){}
  return i<19 || (i==19 && memcmp(zNum,"9223372036854775807",19)<=0);
}


/*
** Change the sqlite.magic from SQLITE_MAGIC_OPEN to SQLITE_MAGIC_BUSY.
** Return an error (non-zero) if the magic was not SQLITE_MAGIC_OPEN
** when this routine is called.
**
** This routine is called when entering an SQLite API.  The SQLITE_MAGIC_OPEN
** value indicates that the database connection passed into the API is
** open and is not being used by another thread.  By changing the value
** to SQLITE_MAGIC_BUSY we indicate that the connection is in use.
** sqlite3SafetyOff() below will change the value back to SQLITE_MAGIC_OPEN
** when the API exits. 
**
** This routine is a attempt to detect if two threads use the
** same sqlite* pointer at the same time.  There is a race 
** condition so it is possible that the error is not detected.
** But usually the problem will be seen.  The result will be an
** error which can be used to debug the application that is
** using SQLite incorrectly.
**
** Ticket #202:  If db->magic is not a valid open value, take care not
** to modify the db structure at all.  It could be that db is a stale
** pointer.  In other words, it could be that there has been a prior
** call to sqlite3_close(db) and db has been deallocated.  And we do
** not want to write into deallocated memory.
*/
int sqlite3SafetyOn(sqlite3 *db){
  if( db->magic==SQLITE_MAGIC_OPEN ){
    db->magic = SQLITE_MAGIC_BUSY;
    return 0;
  }else if( db->magic==SQLITE_MAGIC_BUSY ){
    db->magic = SQLITE_MAGIC_ERROR;
    db->u1.isInterrupted = 1;
  }
  return 1;
}

/*
** Change the magic from SQLITE_MAGIC_BUSY to SQLITE_MAGIC_OPEN.
** Return an error (non-zero) if the magic was not SQLITE_MAGIC_BUSY
** when this routine is called.
*/
int sqlite3SafetyOff(sqlite3 *db){
  if( db->magic==SQLITE_MAGIC_BUSY ){
    db->magic = SQLITE_MAGIC_OPEN;
    return 0;
  }else {
    db->magic = SQLITE_MAGIC_ERROR;
    db->u1.isInterrupted = 1;
    return 1;
  }
}

/*
** Check to make sure we have a valid db pointer.  This test is not
** foolproof but it does provide some measure of protection against
** misuse of the interface such as passing in db pointers that are
** NULL or which have been previously closed.  If this routine returns
** TRUE it means that the db pointer is invalid and should not be
** dereferenced for any reason.  The calling function should invoke
................................................................................
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 && i<9 );
  return i;
}
























#if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC) \
    || defined(SQLITE_TEST)
/*
** Translate a single byte of Hex into an integer.
*/
static int hexToInt(int h){
................................................................................
      zBlob[i/2] = (hexToInt(z[i])<<4) | hexToInt(z[i+1]);
    }
  }
  return zBlob;
}
#endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */

#if defined(SQLITE_TEST)

/*
** Convert text generated by the "%p" conversion format back into
** a pointer.





















*/
void *sqlite3TextToPtr(const char *z){
  void *p;
  u64 v;
  u32 v2;
  if( z[0]=='0' && z[1]=='x' ){
    z += 2;







  }
  v = 0;
  while( *z ){
    v = (v<<4) + hexToInt(*z);
    z++;

  }
  if( sizeof(p)==sizeof(v) ){
    memcpy(&p, &v, sizeof(p));










  }else{
    assert( sizeof(p)==sizeof(v2) );
    v2 = (u32)v;
    memcpy(&p, &v2, sizeof(p));



  }
  return p;
}
#endif

/*
** Return a pointer to the ThreadData associated with the calling thread.
*/
ThreadData *sqlite3ThreadData(){
  ThreadData *p = (ThreadData*)sqlite3OsThreadSpecificData(1);
  if( !p ){
................................................................................
/*
** Check to see if the ThreadData for this thread is all zero.  If it
** is, then deallocate it. 
*/
void sqlite3ReleaseThreadData(){
  sqlite3OsThreadSpecificData(-1);
}

/*
** This function must be called before exiting any API function (i.e. 
** returning control to the user) that has called sqlite3Malloc or
** sqlite3Realloc.
**
** The returned value is normally a copy of the second argument to this
** function. However, if a malloc() failure has occured since the previous
** invocation SQLITE_NOMEM is returned instead. 
**
** If the first argument, db, is not NULL and a malloc() error has occured,
** then the connection error-code (the value returned by sqlite3_errcode())
** is set to SQLITE_NOMEM.
*/
static int mallocHasFailed = 0;
int sqlite3ApiExit(sqlite3* db, int rc){
  if( sqlite3MallocFailed() ){
    mallocHasFailed = 0;
    sqlite3OsLeaveMutex();
    sqlite3Error(db, SQLITE_NOMEM, 0);
    rc = SQLITE_NOMEM;
  }
  return rc & (db ? db->errMask : 0xff);
}

/* 
** Return true is a malloc has failed in this thread since the last call
** to sqlite3ApiExit(), or false otherwise.
*/
int sqlite3MallocFailed(){
  return (mallocHasFailed && sqlite3OsInMutex(1));
}

/* 
** Set the "malloc has failed" condition to true for this thread.
*/
void sqlite3FailedMalloc(){
  if( !sqlite3MallocFailed() ){
    sqlite3OsEnterMutex();
    assert( mallocHasFailed==0 );
    mallocHasFailed = 1;
  }
}

#ifdef SQLITE_MEMDEBUG
/*
** This function sets a flag in the thread-specific-data structure that will
** cause an assert to fail if sqliteMalloc() or sqliteRealloc() is called.
*/
void sqlite3MallocDisallow(){
  assert( sqlite3_mallocDisallowed>=0 );
  sqlite3_mallocDisallowed++;
}

/*
** This function clears the flag set in the thread-specific-data structure set
** by sqlite3MallocDisallow().
*/
void sqlite3MallocAllow(){
  assert( sqlite3_mallocDisallowed>0 );
  sqlite3_mallocDisallowed--;
}
#endif







|






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







 







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







 







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







 







<
>

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

<
<
<
<
<
<
>
>
>
>
>
>
>

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

<

<







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
10
11
12
13
14
15
16
17
18
19
20
21
22
23


















































































































































































































































































































































































































































































































































































































































































































































































24
25
26
27
28
29
30
...
374
375
376
377
378
379
380




















































381
382
383
384
385
386
387
...
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
...
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






624
625
626
627
628
629
630
631




632
633


634
635
636
637
638
639
640
641
642
643
644



645
646
647
648

649

650
651
652
653
654
655
656
...
674
675
676
677
678
679
680































































**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.201 2007/05/05 11:48:54 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <stdarg.h>
#include <ctype.h>




















































































































































































































































































































































































































































































































































































































































































































































































/*
** Set the most recent error code and error string for the sqlite
** handle "db". The error code is set to "err_code".
**
** If it is not NULL, string zFormat specifies the format of the
** error string in the style of the printf functions: The following
................................................................................
  int i, c;
  if( *zNum=='-' || *zNum=='+' ) zNum++;
  for(i=0; (c=zNum[i])>='0' && c<='9'; i++){}
  return i<19 || (i==19 && memcmp(zNum,"9223372036854775807",19)<=0);
}






















































/*
** Check to make sure we have a valid db pointer.  This test is not
** foolproof but it does provide some measure of protection against
** misuse of the interface such as passing in db pointers that are
** NULL or which have been previously closed.  If this routine returns
** TRUE it means that the db pointer is invalid and should not be
** dereferenced for any reason.  The calling function should invoke
................................................................................
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 && i<9 );
  return i;
}


/*
** Read or write a two- and four-byte big-endian integer values.
*/
u32 sqlite3Get2byte(const u8 *p){
  return (p[0]<<8) | p[1];
}
u32 sqlite3Get4byte(const u8 *p){
  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
}
void sqlite3Put2byte(unsigned char *p, u32 v){
  p[0] = v>>8;
  p[1] = v;
}
void sqlite3Put4byte(unsigned char *p, u32 v){
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}



#if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC) \
    || defined(SQLITE_TEST)
/*
** Translate a single byte of Hex into an integer.
*/
static int hexToInt(int h){
................................................................................
      zBlob[i/2] = (hexToInt(z[i])<<4) | hexToInt(z[i+1]);
    }
  }
  return zBlob;
}
#endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */



/*
** Change the sqlite.magic from SQLITE_MAGIC_OPEN to SQLITE_MAGIC_BUSY.
** Return an error (non-zero) if the magic was not SQLITE_MAGIC_OPEN
** when this routine is called.
**
** This routine is called when entering an SQLite API.  The SQLITE_MAGIC_OPEN
** value indicates that the database connection passed into the API is
** open and is not being used by another thread.  By changing the value
** to SQLITE_MAGIC_BUSY we indicate that the connection is in use.
** sqlite3SafetyOff() below will change the value back to SQLITE_MAGIC_OPEN
** when the API exits. 
**
** This routine is a attempt to detect if two threads use the
** same sqlite* pointer at the same time.  There is a race 
** condition so it is possible that the error is not detected.
** But usually the problem will be seen.  The result will be an
** error which can be used to debug the application that is
** using SQLite incorrectly.
**
** Ticket #202:  If db->magic is not a valid open value, take care not
** to modify the db structure at all.  It could be that db is a stale
** pointer.  In other words, it could be that there has been a prior
** call to sqlite3_close(db) and db has been deallocated.  And we do
** not want to write into deallocated memory.
*/






int sqlite3SafetyOn(sqlite3 *db){
  if( db->magic==SQLITE_MAGIC_OPEN ){
    db->magic = SQLITE_MAGIC_BUSY;
    return 0;
  }else if( db->magic==SQLITE_MAGIC_BUSY ){
    db->magic = SQLITE_MAGIC_ERROR;
    db->u1.isInterrupted = 1;
  }




  return 1;
}



/*
** Change the magic from SQLITE_MAGIC_BUSY to SQLITE_MAGIC_OPEN.
** Return an error (non-zero) if the magic was not SQLITE_MAGIC_BUSY
** when this routine is called.
*/
int sqlite3SafetyOff(sqlite3 *db){
  if( db->magic==SQLITE_MAGIC_BUSY ){
    db->magic = SQLITE_MAGIC_OPEN;
    return 0;
  }else {



    db->magic = SQLITE_MAGIC_ERROR;
    db->u1.isInterrupted = 1;
    return 1;
  }

}


/*
** Return a pointer to the ThreadData associated with the calling thread.
*/
ThreadData *sqlite3ThreadData(){
  ThreadData *p = (ThreadData*)sqlite3OsThreadSpecificData(1);
  if( !p ){
................................................................................
/*
** Check to see if the ThreadData for this thread is all zero.  If it
** is, then deallocate it. 
*/
void sqlite3ReleaseThreadData(){
  sqlite3OsThreadSpecificData(-1);
}































































Changes to tool/mksqlite3c.tcl.

68
69
70
71
72
73
74

75
76
77
78
79
80
81
...
148
149
150
151
152
153
154

155
156
157
158
159
160
161

# These are the header files used by SQLite.  The first time any of these 
# files are seen in a #include statement in the C code, include the complete
# text of the file in-line.  The file only needs to be included once.
#
foreach hdr {
   btree.h

   hash.h
   keywordhash.h
   opcodes.h
   os_common.h
   os.h
   os_os2.h
   pager.h
................................................................................
#
foreach file {
   sqlite3.h

   date.c
   os.c


   printf.c
   random.c
   utf.c
   util.c
   hash.c
   opcodes.c








>







 







>







68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
...
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

# These are the header files used by SQLite.  The first time any of these 
# files are seen in a #include statement in the C code, include the complete
# text of the file in-line.  The file only needs to be included once.
#
foreach hdr {
   btree.h
   btreeInt.h
   hash.h
   keywordhash.h
   opcodes.h
   os_common.h
   os.h
   os_os2.h
   pager.h
................................................................................
#
foreach file {
   sqlite3.h

   date.c
   os.c

   malloc.c
   printf.c
   random.c
   utf.c
   util.c
   hash.c
   opcodes.c