/ Check-in [e8060f85]
Login

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

Overview
Comment:Better asserts(). But now some of the tests are busted again. (CVS 4320)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e8060f85e7871572e2a38dc96f03e6e1f34cc8fd
User & Date: drh 2007-08-29 04:00:58
Context
2007-08-29
12:31
Modifications to the malloc failure tests to test transient and persistent failures. (CVS 4321) check-in: e38ef81b user: danielk1977 tags: trunk
04:00
Better asserts(). But now some of the tests are busted again. (CVS 4320) check-in: e8060f85 user: drh tags: trunk
00:33
More locking fixes. Now makes it all the way through quick.test. There are errors but no assertion faults. Progress. (CVS 4319) check-in: 844d40b8 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/alter.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
230
231
232
233
234
235
236

237
238
239
240
241
242
243
...
284
285
286
287
288
289
290

291
292
293
294
295
296
297
...
442
443
444
445
446
447
448

449
450
451
452
453
454
455
...
552
553
554
555
556
557
558

559
560
561
562
563
564
565
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that used to generate VDBE code
** that implements the ALTER TABLE command.
**
** $Id: alter.c,v 1.30 2007/08/25 13:09:26 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The code in this file only exists if we are not omitting the
** ALTER TABLE logic from the build.
................................................................................
  int iDb;                   /* Index of database containing pTab */
#ifndef SQLITE_OMIT_TRIGGER
  Trigger *pTrig;
#endif

  v = sqlite3GetVdbe(pParse);
  if( !v ) return;

  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  assert( iDb>=0 );

#ifndef SQLITE_OMIT_TRIGGER
  /* Drop any table triggers from the internal schema. */
  for(pTrig=pTab->pTrigger; pTrig; pTrig=pTrig->pNext){
    int iTrigDb = sqlite3SchemaToIndex(pParse->db, pTrig->pSchema);
................................................................................
#ifndef SQLITE_OMIT_TRIGGER
  char *zWhere = 0;         /* Where clause to locate temp triggers */
#endif
  int isVirtualRename = 0;  /* True if this is a v-table with an xRename() */
  
  if( db->mallocFailed ) goto exit_rename_table;
  assert( pSrc->nSrc==1 );


  pTab = sqlite3LocateTable(pParse, pSrc->a[0].zName, pSrc->a[0].zDatabase);
  if( !pTab ) goto exit_rename_table;
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  zDb = db->aDb[iDb].zName;

  /* Get a NULL terminated version of the new table name. */
................................................................................
  sqlite3 *db;              /* The database connection; */

  if( pParse->nErr ) return;
  pNew = pParse->pNewTable;
  assert( pNew );

  db = pParse->db;

  iDb = sqlite3SchemaToIndex(db, pNew->pSchema);
  zDb = db->aDb[iDb].zName;
  zTab = pNew->zName;
  pCol = &pNew->aCol[pNew->nCol-1];
  pDflt = pCol->pDflt;
  pTab = sqlite3FindTable(db, zTab, zDb);
  assert( pTab );
................................................................................
  int iDb;
  int i;
  int nAlloc;
  sqlite3 *db = pParse->db;

  /* Look up the table being altered. */
  assert( pParse->pNewTable==0 );

  if( db->mallocFailed ) goto exit_begin_add_column;
  pTab = sqlite3LocateTable(pParse, pSrc->a[0].zName, pSrc->a[0].zDatabase);
  if( !pTab ) goto exit_begin_add_column;

#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( IsVirtual(pTab) ){
    sqlite3ErrorMsg(pParse, "virtual tables may not be altered");







|







 







>







 







>







 







>







 







>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
...
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
...
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
...
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that used to generate VDBE code
** that implements the ALTER TABLE command.
**
** $Id: alter.c,v 1.31 2007/08/29 04:00:58 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The code in this file only exists if we are not omitting the
** ALTER TABLE logic from the build.
................................................................................
  int iDb;                   /* Index of database containing pTab */
#ifndef SQLITE_OMIT_TRIGGER
  Trigger *pTrig;
#endif

  v = sqlite3GetVdbe(pParse);
  if( !v ) return;
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  assert( iDb>=0 );

#ifndef SQLITE_OMIT_TRIGGER
  /* Drop any table triggers from the internal schema. */
  for(pTrig=pTab->pTrigger; pTrig; pTrig=pTrig->pNext){
    int iTrigDb = sqlite3SchemaToIndex(pParse->db, pTrig->pSchema);
................................................................................
#ifndef SQLITE_OMIT_TRIGGER
  char *zWhere = 0;         /* Where clause to locate temp triggers */
#endif
  int isVirtualRename = 0;  /* True if this is a v-table with an xRename() */
  
  if( db->mallocFailed ) goto exit_rename_table;
  assert( pSrc->nSrc==1 );
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );

  pTab = sqlite3LocateTable(pParse, pSrc->a[0].zName, pSrc->a[0].zDatabase);
  if( !pTab ) goto exit_rename_table;
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  zDb = db->aDb[iDb].zName;

  /* Get a NULL terminated version of the new table name. */
................................................................................
  sqlite3 *db;              /* The database connection; */

  if( pParse->nErr ) return;
  pNew = pParse->pNewTable;
  assert( pNew );

  db = pParse->db;
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  iDb = sqlite3SchemaToIndex(db, pNew->pSchema);
  zDb = db->aDb[iDb].zName;
  zTab = pNew->zName;
  pCol = &pNew->aCol[pNew->nCol-1];
  pDflt = pCol->pDflt;
  pTab = sqlite3FindTable(db, zTab, zDb);
  assert( pTab );
................................................................................
  int iDb;
  int i;
  int nAlloc;
  sqlite3 *db = pParse->db;

  /* Look up the table being altered. */
  assert( pParse->pNewTable==0 );
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  if( db->mallocFailed ) goto exit_begin_add_column;
  pTab = sqlite3LocateTable(pParse, pSrc->a[0].zName, pSrc->a[0].zDatabase);
  if( !pTab ) goto exit_begin_add_column;

#ifndef SQLITE_OMIT_VIRTUALTABLE
  if( IsVirtual(pTab) ){
    sqlite3ErrorMsg(pParse, "virtual tables may not be altered");

Changes to src/analyze.c.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
33
34
35
36
37
38
39


40
41
42
43
44
45
46
..
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
...
254
255
256
257
258
259
260

261
262
263
264
265
266
267
...
284
285
286
287
288
289
290

291
292
293
294
295
296
297
...
377
378
379
380
381
382
383


384
385
386
387
388
389
390
**    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.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.
**
** @(#) $Id: analyze.c,v 1.21 2007/08/16 10:09:02 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table on cursor
** iStatCur.
................................................................................
  sqlite3 *db = pParse->db;
  Db *pDb;
  int iRootPage;
  Table *pStat;
  Vdbe *v = sqlite3GetVdbe(pParse);

  if( v==0 ) return;


  pDb = &db->aDb[iDb];
  if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
    /* The sqlite_stat1 tables does not exist.  Create it.  
    ** Note that a side-effect of the CREATE TABLE statement is to leave
    ** the rootpage of the new table on the top of the stack.  This is
    ** important because the OpenWrite opcode below will be needing it. */
    sqlite3NestedParse(pParse,
................................................................................
  int iDb;         /* Index of database containing pTab */

  v = sqlite3GetVdbe(pParse);
  if( v==0 || pTab==0 || pTab->pIndex==0 ){
    /* Do no analysis for tables that have no indices */
    return;
  }

  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  assert( iDb>=0 );
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
      pParse->db->aDb[iDb].zName ) ){
    return;
  }
................................................................................
** a database.
*/
static void analyzeTable(Parse *pParse, Table *pTab){
  int iDb;
  int iStatCur;

  assert( pTab!=0 );

  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  sqlite3BeginWriteOperation(pParse, 0, iDb);
  iStatCur = pParse->nTab++;
  openStatTable(pParse, iDb, iStatCur, pTab->zName);
  analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem);
  loadAnalysis(pParse, iDb);
}
................................................................................
  int i;
  char *z, *zDb;
  Table *pTab;
  Token *pTableName;

  /* Read the database schema. If an error occurs, leave an error message
  ** and code in pParse and return NULL. */

  if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
    return;
  }

  if( pName1==0 ){
    /* Form 1:  Analyze everything */
    for(i=0; i<db->nDb; i++){
................................................................................
** Load the content of the sqlite_stat1 table into the index hash tables.
*/
int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;
  int rc;



  /* Clear any prior statistics */
  for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    sqlite3DefaultRowEst(pIdx);
  }








|







 







>
>







 







|







 







>







 







>







 







>
>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
..
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
...
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
...
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
...
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
**    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.
**
*************************************************************************
** This file contains code associated with the ANALYZE command.
**
** @(#) $Id: analyze.c,v 1.22 2007/08/29 04:00:58 drh Exp $
*/
#ifndef SQLITE_OMIT_ANALYZE
#include "sqliteInt.h"

/*
** This routine generates code that opens the sqlite_stat1 table on cursor
** iStatCur.
................................................................................
  sqlite3 *db = pParse->db;
  Db *pDb;
  int iRootPage;
  Table *pStat;
  Vdbe *v = sqlite3GetVdbe(pParse);

  if( v==0 ) return;
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  assert( sqlite3VdbeDb(v)==db );
  pDb = &db->aDb[iDb];
  if( (pStat = sqlite3FindTable(db, "sqlite_stat1", pDb->zName))==0 ){
    /* The sqlite_stat1 tables does not exist.  Create it.  
    ** Note that a side-effect of the CREATE TABLE statement is to leave
    ** the rootpage of the new table on the top of the stack.  This is
    ** important because the OpenWrite opcode below will be needing it. */
    sqlite3NestedParse(pParse,
................................................................................
  int iDb;         /* Index of database containing pTab */

  v = sqlite3GetVdbe(pParse);
  if( v==0 || pTab==0 || pTab->pIndex==0 ){
    /* Do no analysis for tables that have no indices */
    return;
  }
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  assert( iDb>=0 );
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
      pParse->db->aDb[iDb].zName ) ){
    return;
  }
................................................................................
** a database.
*/
static void analyzeTable(Parse *pParse, Table *pTab){
  int iDb;
  int iStatCur;

  assert( pTab!=0 );
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  sqlite3BeginWriteOperation(pParse, 0, iDb);
  iStatCur = pParse->nTab++;
  openStatTable(pParse, iDb, iStatCur, pTab->zName);
  analyzeOneTable(pParse, pTab, iStatCur, pParse->nMem);
  loadAnalysis(pParse, iDb);
}
................................................................................
  int i;
  char *z, *zDb;
  Table *pTab;
  Token *pTableName;

  /* Read the database schema. If an error occurs, leave an error message
  ** and code in pParse and return NULL. */
  assert( sqlite3BtreeHoldsAllMutexes(pParse->db) );
  if( SQLITE_OK!=sqlite3ReadSchema(pParse) ){
    return;
  }

  if( pName1==0 ){
    /* Form 1:  Analyze everything */
    for(i=0; i<db->nDb; i++){
................................................................................
** Load the content of the sqlite_stat1 table into the index hash tables.
*/
int sqlite3AnalysisLoad(sqlite3 *db, int iDb){
  analysisInfo sInfo;
  HashElem *i;
  char *zSql;
  int rc;

  assert( sqlite3BtreeHoldsAllMutexes(db) );

  /* Clear any prior statistics */
  for(i=sqliteHashFirst(&db->aDb[iDb].pSchema->idxHash);i;i=sqliteHashNext(i)){
    Index *pIdx = sqliteHashData(i);
    sqlite3DefaultRowEst(pIdx);
  }

Changes to src/btmutex.c.

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
...
104
105
106
107
108
109
110














111
112
113
114
115
116
117
...
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
...
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
...
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
...
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
**
**    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: btmutex.c,v 1.4 2007/08/29 00:33:07 drh Exp $
**
** This file contains code used to implement mutexes on Btree objects.
** This code really belongs in btree.c.  But btree.c is getting too
** big and we want to break it down some.  This packaged seemed like
** a good breakout.
*/
#include "btreeInt.h"
................................................................................
  assert( p->sharable || (p->pNext==0 && p->pPrev==0) );

  /* Check for locking consistency */
  assert( !p->locked || p->wantToLock>0 );
  assert( p->sharable || p->wantToLock==0 );

  /* We should already hold a lock on the database connection */
  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );

  if( !p->sharable ) return;
  p->wantToLock++;
  if( p->locked ) return;

  /* In most cases, we should be able to acquire the lock we
  ** want without having to go throught the ascending lock
................................................................................
    if( p->wantToLock==0 ){
      assert( p->locked );
      sqlite3_mutex_leave(p->pBt->mutex);
      p->locked = 0;
    }
  }
}















/*
** Enter the mutex on every Btree associated with a database
** connection.  This is needed (for example) prior to parsing
** a statement since we will be comparing table and column names
** against all schemas and we do not want those schemas being
** reset out from under us.
................................................................................
** Enter the mutexes in accending order by BtShared pointer address
** to avoid the possibility of deadlock when two threads with
** two or more btrees in common both try to lock all their btrees
** at the same instant.
*/
void sqlite3BtreeEnterAll(sqlite3 *db){
  int i;
  Btree *p;
  assert( sqlite3_mutex_held(db->mutex) );
  for(i=0; i<db->nDb && ((p = db->aDb[i].pBt)==0 || p->sharable==0); i++){}
  if( i<db->nDb ){





    while( p->pNext ) p = p->pNext;
    while( 1 ){

      if( p->locked ){
        sqlite3_mutex_leave(p->pBt->mutex);
        p->locked = 0;
      }
      if( p->pPrev==0 ) break;
      p = p->pPrev;
    }
    while( p ){
      p->wantToLock++;
      sqlite3_mutex_enter(p->pBt->mutex);
      p->locked = 1;
      p = p->pNext;


    }
  }
}
void sqlite3BtreeLeaveAll(sqlite3 *db){
  int i;
  Btree *p;
  assert( sqlite3_mutex_held(db->mutex) );
  for(i=0; i<db->nDb && ((p = db->aDb[i].pBt)==0 || p->sharable==0); i++){}
  if( i<db->nDb ){
    while( p->pPrev ) p = p->pPrev;
    while( p ){
      p->wantToLock--;
      if( p->wantToLock==0 ){

        sqlite3_mutex_leave(p->pBt->mutex);
        p->locked = 0;
      }
      p = p->pNext;
    }
  }
}

























/*
** Potentially dd a new Btree pointer to a BtreeMutexArray.
** Really only add the Btree if it can possibly be shared with
** another database connection.
**
** The Btrees are kept in sorted order by pBtree->pBt.  That
................................................................................
**
** The number of shared btrees will always be small (usually 0 or 1)
** so an insertion sort is an adequate algorithm here.
*/
void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
  int i, j;
  BtShared *pBt;
  if( !pBtree->sharable ) return;
#ifndef NDEBUG
  {
    for(i=0; i<pArray->nMutex; i++){
      assert( pArray->aBtree[i]!=pBtree );
    }
  }
#endif
................................................................................
void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
  int i;
  for(i=0; i<pArray->nMutex; i++){
    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( !p->locked || p->wantToLock>0 );
    assert( p->sharable );

    /* We should already hold a lock on the database connection */
    assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );

    p->wantToLock++;
    if( !p->locked ){
      sqlite3_mutex_enter(p->pBt->mutex);
      p->locked = 1;
    }
  }
}

/*
................................................................................
*/
void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
  int i;
  for(i=0; i<pArray->nMutex; i++){
    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( p->locked );
    assert( p->sharable );
    assert( p->wantToLock>0 );

    /* We should already hold a lock on the database connection */
    assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );

    p->wantToLock--;
    if( p->wantToLock==0 ){
      sqlite3_mutex_leave(p->pBt->mutex);
      p->locked = 0;
    }
  }
}


#endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */







|







 







|







 







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







 







|

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







|
|
|
|


>



<



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







 







|







 







<


|


|







 







|
<



|


|








6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
..
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
...
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
...
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
...
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
...
255
256
257
258
259
260
261

262
263
264
265
266
267
268
269
270
271
272
273
274
...
276
277
278
279
280
281
282
283

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
**
**    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: btmutex.c,v 1.5 2007/08/29 04:00:58 drh Exp $
**
** This file contains code used to implement mutexes on Btree objects.
** This code really belongs in btree.c.  But btree.c is getting too
** big and we want to break it down some.  This packaged seemed like
** a good breakout.
*/
#include "btreeInt.h"
................................................................................
  assert( p->sharable || (p->pNext==0 && p->pPrev==0) );

  /* Check for locking consistency */
  assert( !p->locked || p->wantToLock>0 );
  assert( p->sharable || p->wantToLock==0 );

  /* We should already hold a lock on the database connection */
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );

  if( !p->sharable ) return;
  p->wantToLock++;
  if( p->locked ) return;

  /* In most cases, we should be able to acquire the lock we
  ** want without having to go throught the ascending lock
................................................................................
    if( p->wantToLock==0 ){
      assert( p->locked );
      sqlite3_mutex_leave(p->pBt->mutex);
      p->locked = 0;
    }
  }
}

#ifndef NDEBUG
/*
** Return true if a mutex is held on the btree.
**
** This routine is used only from within assert() statements.
*/
int sqlite3BtreeHoldsMutex(Btree *p){
  return sqlite3_mutex_held(p->pSqlite->mutex) && 
         (p->sharable==0 ||
             (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
}
#endif


/*
** Enter the mutex on every Btree associated with a database
** connection.  This is needed (for example) prior to parsing
** a statement since we will be comparing table and column names
** against all schemas and we do not want those schemas being
** reset out from under us.
................................................................................
** Enter the mutexes in accending order by BtShared pointer address
** to avoid the possibility of deadlock when two threads with
** two or more btrees in common both try to lock all their btrees
** at the same instant.
*/
void sqlite3BtreeEnterAll(sqlite3 *db){
  int i;
  Btree *p, *pLater;
  assert( sqlite3_mutex_held(db->mutex) );
  for(i=0; i<db->nDb; i++){
    p = db->aDb[i].pBt;
    if( p && p->sharable ){
      p->wantToLock++;
      if( !p->locked ){
        assert( p->wantToLock==1 );
        while( p->pPrev ) p = p->pPrev;
        while( p->locked && p->pNext ) p = p->pNext;

        for(pLater = p->pNext; pLater; pLater=pLater->pNext){
          if( pLater->locked ){
            sqlite3_mutex_leave(pLater->pBt->mutex);
            pLater->locked = 0;
          }


        }
        while( p ){

          sqlite3_mutex_enter(p->pBt->mutex);
          p->locked++;
          p = p->pNext;
        }
      }
    }
  }
}
void sqlite3BtreeLeaveAll(sqlite3 *db){
  int i;
  Btree *p;
  assert( sqlite3_mutex_held(db->mutex) );
  for(i=0; i<db->nDb; i++){
    p = db->aDb[i].pBt;
    if( p && p->sharable ){
      assert( p->wantToLock>0 );
      p->wantToLock--;
      if( p->wantToLock==0 ){
        assert( p->locked );
        sqlite3_mutex_leave(p->pBt->mutex);
        p->locked = 0;
      }

    }
  }
}

#ifndef NDEBUG
/*
** Return true if the current thread holds the database connection
** mutex and all required BtShared mutexes.
**
** This routine is used inside assert() statements only.
*/
int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
  int i;
  if( !sqlite3_mutex_held(db->mutex) ){
    return 0;
  }
  for(i=0; i<db->nDb; i++){
    Btree *p;
    p = db->aDb[i].pBt;
    if( p && p->sharable &&
         (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
      return 0;
    }
  }
  return 1;
}
#endif /* NDEBUG */

/*
** Potentially dd a new Btree pointer to a BtreeMutexArray.
** Really only add the Btree if it can possibly be shared with
** another database connection.
**
** The Btrees are kept in sorted order by pBtree->pBt.  That
................................................................................
**
** The number of shared btrees will always be small (usually 0 or 1)
** so an insertion sort is an adequate algorithm here.
*/
void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
  int i, j;
  BtShared *pBt;
  if( pBtree->sharable==0 ) return;
#ifndef NDEBUG
  {
    for(i=0; i<pArray->nMutex; i++){
      assert( pArray->aBtree[i]!=pBtree );
    }
  }
#endif
................................................................................
void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
  int i;
  for(i=0; i<pArray->nMutex; i++){
    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( !p->locked || p->wantToLock>0 );


    /* We should already hold a lock on the database connection */
    assert( sqlite3_mutex_held(p->pSqlite->mutex) );

    p->wantToLock++;
    if( !p->locked && p->sharable ){
      sqlite3_mutex_enter(p->pBt->mutex);
      p->locked = 1;
    }
  }
}

/*
................................................................................
*/
void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
  int i;
  for(i=0; i<pArray->nMutex; i++){
    Btree *p = pArray->aBtree[i];
    /* Some basic sanity checking */
    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
    assert( p->locked || !p->sharable );

    assert( p->wantToLock>0 );

    /* We should already hold a lock on the database connection */
    assert( sqlite3_mutex_held(p->pSqlite->mutex) );

    p->wantToLock--;
    if( p->wantToLock==0 && p->locked ){
      sqlite3_mutex_leave(p->pBt->mutex);
      p->locked = 0;
    }
  }
}


#endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
..
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
...
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
...
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
...
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
...
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
...
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
...
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
...
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
...
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
...
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
...
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
...
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
...
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
...
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
...
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
...
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
...
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
...
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
...
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
...
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
...
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
....
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
....
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
....
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
....
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
....
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
....
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
....
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
....
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
....
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
....
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
....
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
....
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
....
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
....
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
....
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
....
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
....
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
....
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
....
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
....
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
....
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
....
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
....
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
....
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
....
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
....
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
....
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
....
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
....
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
....
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
....
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
....
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
....
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
....
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
....
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
....
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
....
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
....
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
....
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
....
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
....
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
....
4335
4336
4337
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
....
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
....
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
....
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
....
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
....
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
....
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
....
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
....
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
....
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
....
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
....
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
....
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
....
5686
5687
5688
5689
5690
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
....
5707
5708
5709
5710
5711
5712
5713
5714
5715
5716
5717
5718
5719
5720
5721
5722
....
5856
5857
5858
5859
5860
5861
5862
5863
5864
5865
5866
5867
5868
5869
5870
....
5938
5939
5940
5941
5942
5943
5944
5945
5946
5947
5948
5949
5950
5951
5952
....
6139
6140
6141
6142
6143
6144
6145
6146
6147
6148
6149
6150
6151
6152
6153
....
6599
6600
6601
6602
6603
6604
6605
6606
6607
6608
6609
6610
6611
6612
6613
6614
6615
6616
6617
6618
6619
6620
6621
6622
6623
6624
6625
6626
6627
6628
6629
6630
6631
6632
6633
6634
6635
6636
6637
6638
6639
....
6705
6706
6707
6708
6709
6710
6711
6712
6713
6714
6715
6716
6717
6718
6719
6720
6721
6722
6723
6724
6725
6726
6727
6728
6729
6730
6731
6732
6733
6734
6735
6736
....
6759
6760
6761
6762
6763
6764
6765
6766
6767
6768
6769
6770
6771
6772
6773
....
6795
6796
6797
6798
6799
6800
6801
6802
6803
6804
6805
6806
6807
6808
6809
6810
....
6833
6834
6835
6836
6837
6838
6839
6840
6841
6842
6843
6844
6845
6846
** 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.415 2007/08/28 23:28:08 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"

................................................................................
** SQLITE_OK if the lock may be obtained (by calling lockTable()), or
** SQLITE_LOCKED if not.
*/
static int queryTableLock(Btree *p, Pgno iTab, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pIter;

  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  
  /* This is a no-op if the shared-cache is not enabled */
  if( !p->sharable ){
    return SQLITE_OK;
  }

  /* This (along with lockTable()) is where the ReadUncommitted flag is
................................................................................
** SQLITE_NOMEM may also be returned.
*/
static int lockTable(Btree *p, Pgno iTable, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pLock = 0;
  BtLock *pIter;

  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );

  /* This is a no-op if the shared-cache is not enabled */
  if( !p->sharable ){
    return SQLITE_OK;
  }

  assert( SQLITE_OK==queryTableLock(p, iTable, eLock) );
................................................................................
/*
** Release all the table locks (locks obtained via calls to the lockTable()
** procedure) held by Btree handle p.
*/
static void unlockAllTables(Btree *p){
  BtLock **ppIter = &p->pBt->pLock;

  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
  assert( p->sharable || 0==*ppIter );

  while( *ppIter ){
    BtLock *pLock = *ppIter;
    if( pLock->pBtree==p ){
      *ppIter = pLock->pNext;
      sqlite3_free(pLock);
................................................................................
      ppIter = &pLock->pNext;
    }
  }
}
#endif /* SQLITE_OMIT_SHARED_CACHE */

static void releasePage(MemPage *pPage);  /* Forward reference */











#ifndef SQLITE_OMIT_INCRBLOB
/*
** Invalidate the overflow page-list cache for cursor pCur, if any.
*/
static void invalidateOverflowCache(BtCursor *pCur){
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  sqlite3_free(pCur->aOverflow);
  pCur->aOverflow = 0;
}

/*
** Invalidate the overflow page-list cache for all cursors opened
** on the shared btree structure pBt.
*/
static void invalidateAllOverflowCache(BtShared *pBt){
  BtCursor *p;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  for(p=pBt->pCursor; p; p=p->pNext){
    invalidateOverflowCache(p);
  }
}
#else
  #define invalidateOverflowCache(x)
  #define invalidateAllOverflowCache(x)
................................................................................
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
*/
static int saveCursorPosition(BtCursor *pCur){
  int rc;

  assert( CURSOR_VALID==pCur->eState );
  assert( 0==pCur->pKey );
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );

  rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
................................................................................
/*
** Save the positions of all cursors except pExcept open on the table 
** with root-page iRoot. Usually, this is called just before cursor
** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).
*/
static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){
  BtCursor *p;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( pExcept==0 || pExcept->pBt==pBt );
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 
        p->eState==CURSOR_VALID ){
      int rc = saveCursorPosition(p);
      if( SQLITE_OK!=rc ){
        return rc;
................................................................................
  return SQLITE_OK;
}

/*
** Clear the current cursor position.
*/
static void clearCursorPosition(BtCursor *pCur){
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  sqlite3_free(pCur->pKey);
  pCur->pKey = 0;
  pCur->eState = CURSOR_INVALID;
}

/*
** Restore the cursor to the position it was in (or as close to as possible)
................................................................................
**
** If the second argument argument - doSeek - is false, then instead of 
** returning the cursor to it's saved position, any saved position is deleted
** and the cursor state set to CURSOR_INVALID.
*/
int sqlite3BtreeRestoreOrClearCursorPosition(BtCursor *pCur){
  int rc;
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( pCur->eState==CURSOR_REQUIRESEEK );
#ifndef SQLITE_OMIT_INCRBLOB
  if( pCur->isIncrblobHandle ){
    return SQLITE_ABORT;
  }
#endif
  pCur->eState = CURSOR_INVALID;
................................................................................
/*
** 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, iPtrMap, ret;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  nPagesPerMapPage = (pBt->usableSize/5)+1;
  iPtrMap = (pgno-2)/nPagesPerMapPage;
  ret = (iPtrMap*nPagesPerMapPage) + 2; 
  if( ret==PENDING_BYTE_PAGE(pBt) ){
    ret++;
  }
  return ret;
................................................................................
static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){
  DbPage *pDbPage;  /* The pointer map page */
  u8 *pPtrmap;      /* The pointer map data */
  Pgno iPtrmap;     /* The pointer map page number */
  int offset;       /* Offset in pointer map page */
  int rc;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  /* The master-journal page number must never be used as a pointer map page */
  assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );

  assert( pBt->autoVacuum );
  if( key==0 ){
    return SQLITE_CORRUPT_BKPT;
  }
................................................................................
static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  DbPage *pDbPage;   /* The pointer map page */
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );

  iPtrmap = PTRMAP_PAGENO(pBt, key);
  rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
  if( rc!=0 ){
    return rc;
  }
  pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
................................................................................

/*
** This a more complex version of sqlite3BtreeFindCell() that works for
** pages that do contain overflow cells.  See insert
*/
static u8 *findOverflowCell(MemPage *pPage, int iCell){
  int i;
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  for(i=pPage->nOverflow-1; i>=0; i--){
    int k;
    struct _OvflCell *pOvfl;
    pOvfl = &pPage->aOvfl[i];
    k = pOvfl->idx;
    if( k<=iCell ){
      if( k==iCell ){
................................................................................
  MemPage *pPage,         /* Page containing the cell */
  u8 *pCell,              /* Pointer to the cell text. */
  CellInfo *pInfo         /* Fill in this structure */
){
  int n;                  /* Number bytes in cell content header */
  u32 nPayload;           /* Number of bytes of cell payload */

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );

  pInfo->pCell = pCell;
  assert( pPage->leaf==0 || pPage->leaf==1 );
  n = pPage->childPtrSize;
  assert( n==4-4*pPage->leaf );
  if( pPage->hasData ){
    n += getVarint32(&pCell[n], &nPayload);
................................................................................
/*
** If the cell with index iCell on page pPage contains a pointer
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/
static int ptrmapPutOvfl(MemPage *pPage, int iCell){
  u8 *pCell;
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif


/*
................................................................................
  unsigned char *data;       /* The page data */
  unsigned char *temp;       /* Temp area for cell content */

  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt!=0 );
  assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
  assert( pPage->nOverflow==0 );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  temp = sqlite3_malloc( pPage->pBt->pageSize );
  if( temp==0 ) return SQLITE_NOMEM;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  cellOffset = pPage->cellOffset;
  nCell = pPage->nCell;
  assert( nCell==get2byte(&data[hdr+3]) );
................................................................................
  int nCell;
  int cellOffset;
  unsigned char *data;
  
  data = pPage->aData;
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->nOverflow>0 ) return 0;
  pPage->nFree -= nByte;
  hdr = pPage->hdrOffset;

  nFrag = data[hdr+7];
  if( nFrag<60 ){
................................................................................
  int addr, pbegin, hdr;
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  assert( (start + size)<=pPage->pBt->usableSize );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( size<4 ) size = 4;

#ifdef SQLITE_SECURE_DELETE
  /* Overwrite deleted information with zeros when the SECURE_DELETE 
  ** option is enabled at compile-time */
  memset(&data[start], 0, size);
#endif
................................................................................
** Decode the flags byte (the first byte of the header) for a page
** and initialize fields of the MemPage structure accordingly.
*/
static void decodeFlags(MemPage *pPage, int flagByte){
  BtShared *pBt;     /* A copy of pPage->pBt */

  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  pPage->leaf = (flagByte & PTF_LEAF)!=0;
  pPage->childPtrSize = 4*(pPage->leaf==0);
  pBt = pPage->pBt;
  if( flagByte & PTF_LEAFDATA ){
    pPage->leafData = 1;
................................................................................
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit ) return SQLITE_OK;
................................................................................
  BtShared *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3PagerPagenumber(pPage->pDbPage)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  memset(&data[hdr], 0, pBt->usableSize - hdr);
  data[hdr] = flags;
  first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
  memset(&data[hdr+1], 0, 4);
  data[hdr+7] = 0;
  put2byte(&data[hdr+5], pBt->usableSize);
  pPage->nFree = pBt->usableSize - first;
................................................................................
  MemPage **ppPage,    /* Return the page in this parameter */
  int noContent        /* Do not load page content if true */
){
  int rc;
  MemPage *pPage;
  DbPage *pDbPage;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  rc = sqlite3PagerAcquire(pBt->pPager, pgno, (DbPage**)&pDbPage, noContent);
  if( rc ) return rc;
  pPage = (MemPage *)sqlite3PagerGetExtra(pDbPage);
  pPage->aData = sqlite3PagerGetData(pDbPage);
  pPage->pDbPage = pDbPage;
  pPage->pBt = pBt;
  pPage->pgno = pgno;
................................................................................
static int getAndInitPage(
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }
  rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);
  if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
    rc = sqlite3BtreeInitPage(*ppPage, pParent);
  }
................................................................................
** call to sqlite3BtreeGetPage.
*/
static void releasePage(MemPage *pPage){
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
    sqlite3PagerUnref(pPage->pDbPage);
  }
}

/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(DbPage *pData, int pageSize){
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  assert( pPage->isInit==0 || sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    assert( pPage->isInit==1 );
    assert( pParent->pBt==pPage->pBt );
    pPage->pParent = 0;
    releasePage(pParent);
  }
................................................................................
** page to agree with the restored data.
*/
static void pageReinit(DbPage *pData, int pageSize){
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  if( pPage->isInit ){
    assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
    pPage->isInit = 0;
    sqlite3BtreeInitPage(pPage, pPage->pParent);
  }
}

/*
** Open a database file.
................................................................................
  if( p->pNext ) p->pNext->pPrev = p->pPrev;
#endif

  sqlite3_free(p);
  return SQLITE_OK;
}

#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
/*
** Short-cuts for entering and leaving mutexes on a cursor.
*/
# define cursorEnter(X) assert( sqlite3_mutex_held(X->pBt->mutex) )
# define cursorLeave(X)
#else
# define cursorEnter(X)
# define cursorLeave(X)
#endif /* !SQLITE_OMIT_SHARED_CACHE */

/*
** Change the busy handler callback function.
*/
int sqlite3BtreeSetBusyHandler(Btree *p, BusyHandler *pHandler){
  BtShared *pBt = p->pBt;
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  sqlite3BtreeEnter(p);
................................................................................
** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
** is returned if we run out of memory. 
*/
static int lockBtree(BtShared *pBt){
  int rc, pageSize;
  MemPage *pPage1;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( pBt->pPage1 ) return SQLITE_OK;
  rc = sqlite3BtreeGetPage(pBt, 1, &pPage1, 0);
  if( rc!=SQLITE_OK ) return rc;
  

  /* Do some checking to help insure the file we opened really is
  ** a valid database file. 
................................................................................
/*
** This routine works like lockBtree() except that it also invokes the
** busy callback if there is lock contention.
*/
static int lockBtreeWithRetry(Btree *pRef){
  int rc = SQLITE_OK;

  assert( sqlite3BtreeMutexHeld(pRef->pSqlite->mutex) );
  assert( sqlite3BtreeMutexHeld(pRef->pBt->mutex) );
  if( pRef->inTrans==TRANS_NONE ){
    u8 inTransaction = pRef->pBt->inTransaction;
    btreeIntegrity(pRef);
    rc = sqlite3BtreeBeginTrans(pRef, 0);
    pRef->pBt->inTransaction = inTransaction;
    pRef->inTrans = TRANS_NONE;
    if( rc==SQLITE_OK ){
................................................................................
** has the effect of releasing the read lock.
**
** If there are any outstanding cursors, this routine is a no-op.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(BtShared *pBt){
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( pBt->inTransaction==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
    if( sqlite3PagerRefcount(pBt->pPager)>=1 ){
      if( pBt->pPage1->aData==0 ){
        MemPage *pPage = pBt->pPage1;
        pPage->aData = &((u8*)pPage)[-pBt->pageSize];
        pPage->pBt = pBt;
        pPage->pgno = 1;
................................................................................
** file.
*/
static int newDatabase(BtShared *pBt){
  MemPage *pP1;
  unsigned char *data;
  int rc;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( sqlite3PagerPagecount(pBt->pPager)>0 ) return SQLITE_OK;
  pP1 = pBt->pPage1;
  assert( pP1!=0 );
  data = pP1->aData;
  rc = sqlite3PagerWrite(pP1->pDbPage);
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
................................................................................
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc;                            /* Return code */
  BtShared *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  rc = sqlite3BtreeInitPage(pPage, pPage->pParent);
  if( rc!=SQLITE_OK ){
    goto set_child_ptrmaps_out;
  }
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
................................................................................
** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
**                   page pointed to by one of the cells on pPage.
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static int modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( eType==PTRMAP_OVERFLOW2 ){
    /* The pointer is always the first 4 bytes of the page in this case.  */
    if( get4byte(pPage->aData)!=iFrom ){
      return SQLITE_CORRUPT_BKPT;
    }
    put4byte(pPage->aData, iTo);
  }else{
................................................................................
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
  Pager *pPager = pBt->pPager;
  int rc;

  assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
      eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE );
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( pDbPage->pBt==pBt );

  /* Move page iDbPage from it's current location to page number iFreePage */
  TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
      iDbPage, iFreePage, iPtrPage, eType));
  rc = sqlite3PagerMovepage(pPager, pDbPage->pDbPage, iFreePage);
  if( rc!=SQLITE_OK ){
................................................................................
** number of pages the database file will contain after this 
** process is complete.
*/
static int incrVacuumStep(BtShared *pBt, Pgno nFin){
  Pgno iLastPg;             /* Last page in the database */
  Pgno nFreeList;           /* Number of pages still on the free-list */

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  iLastPg = pBt->nTrunc;
  if( iLastPg==0 ){
    iLastPg = sqlite3PagerPagecount(pBt->pPager);
  }

  if( !PTRMAP_ISPAGE(pBt, iLastPg) && iLastPg!=PENDING_BYTE_PAGE(pBt) ){
    int rc;
................................................................................
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  int rc = SQLITE_OK;
  Pager *pPager = pBt->pPager;
#ifndef NDEBUG
  int nRef = sqlite3PagerRefcount(pPager);
#endif

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  invalidateAllOverflowCache(pBt);
  assert(pBt->autoVacuum);
  if( !pBt->incrVacuum ){
    Pgno nFin = 0;

    if( pBt->nTrunc==0 ){
      Pgno nFree;
................................................................................
  void *pArg,                                 /* First arg to xCompare() */
  BtCursor **ppCur                            /* Write new cursor here */
){
  int rc;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(p, iTable, 0) ){
      return SQLITE_LOCKED;
................................................................................
/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqlite3BtreeCloseCursor(BtCursor *pCur){
  BtShared *pBt = pCur->pBt;

  assert( sqlite3_mutex_held(pCur->pBt->mutex) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  clearCursorPosition(pCur);
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
................................................................................
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.
*/
void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur){
  cursorEnter(pCur);
  memcpy(pTempCur, pCur, sizeof(*pCur));
  pTempCur->pNext = 0;
  pTempCur->pPrev = 0;
  if( pTempCur->pPage ){
    sqlite3PagerRef(pTempCur->pPage->pDbPage);
  }
  cursorLeave(pCur);
}

/*
** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
** function above.
*/
void sqlite3BtreeReleaseTempCursor(BtCursor *pCur){
  cursorEnter(pCur);
  if( pCur->pPage ){
    sqlite3PagerUnref(pCur->pPage->pDbPage);
  }
  cursorLeave(pCur);
}

/*
** Make sure the BtCursor* given in the argument has a valid
** BtCursor.info structure.  If it is not already valid, call
** sqlite3BtreeParseCell() to fill it in.
**
................................................................................
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  int rc;

  assert( sqlite3_mutex_held(pCur->pBt->mutex) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
    if( pCur->eState==CURSOR_INVALID ){
      *pSize = 0;
    }else{
      getCellInfo(pCur);
................................................................................
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  int rc;

  assert( sqlite3_mutex_held(pCur->pBt->mutex) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
    if( pCur->eState==CURSOR_INVALID ){
      /* Not pointing at a valid entry - set *pSize to 0. */
      *pSize = 0;
    }else{
................................................................................
  Pgno ovfl,                   /* Overflow page */
  MemPage **ppPage,            /* OUT: MemPage handle */
  Pgno *pPgnoNext              /* OUT: Next overflow page number */
){
  Pgno next = 0;
  int rc;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  /* One of these must not be NULL. Otherwise, why call this function? */
  assert(ppPage || pPgnoNext);

  /* If pPgnoNext is NULL, then this function is being called to obtain
  ** a MemPage* reference only. No page-data is required in this case.
  */
  if( !pPgnoNext ){
................................................................................
  MemPage *pPage = pCur->pPage;     /* Btree page of current cursor entry */
  BtShared *pBt = pCur->pBt;        /* Btree this cursor belongs to */

  assert( pPage );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( offset>=0 );
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );

  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  nKey = (pPage->intKey ? 0 : pCur->info.nKey);

  if( skipKey ){
    offset += nKey;
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  int rc;

  cursorEnter(pCur);
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    if( pCur->pPage->intKey ){
      cursorLeave(pCur);
      return SQLITE_CORRUPT_BKPT;
    }
    assert( pCur->pPage->intKey==0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0, 0);
  }
  cursorLeave(pCur);
  return rc;
}

/*
** Read part of the data associated with cursor pCur.  Exactly
** "amt" bytes will be transfered into pBuf[].  The transfer
** begins at "offset".
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  int rc;

  cursorEnter(pCur);
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, pBuf, 1, 0);
  }
  cursorLeave(pCur);
  return rc;
}

/*
** Return a pointer to payload information from the entry that the 
** pCur cursor is pointing to.  The pointer is to the beginning of
** the key if skipKey==0 and it points to the beginning of data if
................................................................................
  unsigned char *aPayload;
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  pPage = pCur->pPage;
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
................................................................................
** Hence, a mutex on the BtShared should be held prior to calling
** this routine.
**
** These routines is used to get quick access to key and data
** in the common case where no overflow pages are used.
*/
const void *sqlite3BtreeKeyFetch(BtCursor *pCur, int *pAmt){
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  if( pCur->eState==CURSOR_VALID ){
    return (const void*)fetchPayload(pCur, pAmt, 0);
  }
  return 0;
}
const void *sqlite3BtreeDataFetch(BtCursor *pCur, int *pAmt){
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  if( pCur->eState==CURSOR_VALID ){
    return (const void*)fetchPayload(pCur, pAmt, 1);
  }
  return 0;
}


................................................................................
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBt;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( pCur->eState==CURSOR_VALID );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
................................................................................
** is empty except for the right-pointer.  In such cases the
** virtual root page is the page that the right-pointer of page
** 1 is pointing to.
*/
int sqlite3BtreeIsRootPage(MemPage *pPage){
  MemPage *pParent;

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  pParent = pPage->pParent;
  if( pParent==0 ) return 1;
  if( pParent->pgno>1 ) return 0;
  if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
  return 0;
}

................................................................................
** the largest cell index.
*/
void sqlite3BtreeMoveToParent(BtCursor *pCur){
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  cursorEnter(pCur);
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !sqlite3BtreeIsRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlite3PagerRef(pParent->pDbPage);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;
  cursorLeave(pCur);
}

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc = SQLITE_OK;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( pCur->eState==CURSOR_REQUIRESEEK ){
    clearCursorPosition(pCur);
  }
  pRoot = pCur->pPage;
  if( pRoot && pRoot->pgno==pCur->pgnoRoot ){
    assert( pRoot->isInit );
  }else{
................................................................................
** in ascending order.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->idx));
    rc = moveToChild(pCur, pgno);
  }
  return rc;
................................................................................
** key in ascending order.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
  }
  if( rc==SQLITE_OK ){
................................................................................
/* Move the cursor to the first entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;

  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
      rc = SQLITE_OK;
    }else{
................................................................................
/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  int rc;
 
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->eState==CURSOR_VALID );
................................................................................
  const void *pKey,      /* The key content for indices.  Not used by tables */
  i64 nKey,              /* Size of pKey.  Or the key for tables */
  int biasRight,         /* If true, bias the search to the high end */
  int *pRes              /* Search result flag */
){
  int rc;

  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pPage );
  assert( pCur->pPage->isInit );
  if( pCur->eState==CURSOR_INVALID ){
................................................................................
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
static int btreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage;

  assert( sqlite3_mutex_held(pCur->pBt->mutex) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  assert( pRes!=0 );
  pPage = pCur->pPage;
  if( CURSOR_INVALID==pCur->eState ){
................................................................................
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
}
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  cursorEnter(pCur);
  rc = btreeNext(pCur, pRes);
  cursorLeave(pCur);
  return rc;
}


/*
** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
................................................................................
** this routine was called, then set *pRes=1.
*/
static int btreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;

  assert( sqlite3_mutex_held(pCur->pBt->mutex) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
................................................................................
    }
  }
  *pRes = 0;
  return rc;
}
int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  cursorEnter(pCur);
  rc = btreePrevious(pCur, pRes);
  cursorLeave(pCur);
  return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlite3PagerWrite()
................................................................................
  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */
  MemPage *pTrunk = 0;
  MemPage *pPrevTrunk = 0;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    Pgno iTrunk;
    u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
    
................................................................................
*/
static int freePage(MemPage *pPage){
  BtShared *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3PagerWrite(pPage1->pDbPage);
................................................................................
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;
  int nOvfl;
  int ovflPageSize;

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  ovflPageSize = pBt->usableSize - 4;
  nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
................................................................................
  unsigned char *pPrior;
  unsigned char *pPayload;
  BtShared *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );

  /* Fill in the header. */
  nHeader = 0;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
................................................................................
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  DbPage *pDbPage;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( pNewParent!=0 );
  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  pDbPage = sqlite3PagerLookup(pBt->pPager, pgno);
  if( pDbPage ){
    pThis = (MemPage *)sqlite3PagerGetExtra(pDbPage);
    if( pThis->isInit ){
................................................................................
** another.
*/
static int reparentChildPages(MemPage *pPage){
  int i;
  BtShared *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( pPage->leaf ) return SQLITE_OK;

  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = reparentPage(pBt, get4byte(pCell), pPage, i);
      if( rc!=SQLITE_OK ) return rc;
................................................................................
  int pc;         /* Offset to cell content of cell being deleted */
  u8 *data;       /* pPage->aData */
  u8 *ptr;        /* Used to move bytes around within data[] */

  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, idx) );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  data = pPage->aData;
  ptr = &data[pPage->cellOffset + 2*idx];
  pc = get2byte(ptr);
  assert( pc>10 && pc+sz<=pPage->pBt->usableSize );
  freeSpace(pPage, pc, sz);
  for(i=idx+1; i<pPage->nCell; i++, ptr+=2){
    ptr[0] = ptr[2];
................................................................................
  int hdr;          /* Offset into data[] of the page header */
  int cellOffset;   /* Address of first cell pointer in data[] */
  u8 *data;         /* The content of the whole page */
  u8 *ptr;          /* Used for moving information around in data[] */

  assert( i>=0 && i<=pPage->nCell+pPage->nOverflow );
  assert( sz==cellSizePtr(pPage, pCell) );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( pPage->nOverflow || sz+2>pPage->nFree ){
    if( pTemp ){
      memcpy(pTemp+nSkip, pCell+nSkip, sz-nSkip);
      pCell = pTemp;
    }
    j = pPage->nOverflow++;
    assert( j<sizeof(pPage->aOvfl)/sizeof(pPage->aOvfl[0]) );
................................................................................
  int totalSize;    /* Total size of all cells */
  int hdr;          /* Index of page header */
  int cellptr;      /* Address of next cell pointer */
  int cellbody;     /* Address of next cell body */
  u8 *data;         /* Data for the page */

  assert( pPage->nOverflow==0 );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  totalSize = 0;
  for(i=0; i<nCell; i++){
    totalSize += aSize[i];
  }
  assert( totalSize+2*nCell<=pPage->nFree );
  assert( pPage->nCell==0 );
  cellptr = pPage->cellOffset;
................................................................................
  int szCell;
  CellInfo info;
  BtShared *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );

  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
  rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  if( rc!=SQLITE_OK ){
    return rc;
................................................................................
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 *aFrom = 0;
#endif

  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
................................................................................
  BtShared *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqlite3_malloc( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
  if( apCell==0 ) return SQLITE_NOMEM;
  szCell = (int*)&apCell[mxCellPerPage];
  if( pPage->leaf ){
    /* The table is completely empty */
................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3PagerIswriteable(pChild->pDbPage) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
................................................................................

/*
** Decide if the page pPage needs to be balanced.  If balancing is
** required, call the appropriate balancing routine.
*/
static int balance(MemPage *pPage, int insert){
  int rc = SQLITE_OK;
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  if( pPage->pParent==0 ){
    rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc==SQLITE_OK && pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( rc==SQLITE_OK && pPage->nCell==0 ){
      rc = balance_shallower(pPage);
................................................................................
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBtree, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  BtShared *pBt = pBtree->pBt;
  sqlite3 *db = pBtree->pSqlite;
  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(db->mutex) );
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p==pExclude ) continue;
    if( p->eState!=CURSOR_VALID ) continue;
    if( p->pgnoRoot!=pgnoRoot ) continue;
    if( p->wrFlag==0 ){
      sqlite3 *dbOther = p->pBtree->pSqlite;
      if( dbOther==0 ||
................................................................................
  int szNew;
  MemPage *pPage;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;

  cursorEnter(pCur);
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
    cursorLeave(pCur);
    return rc;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
    cursorLeave(pCur);
    return SQLITE_PERM;   /* Cursor not open for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
    cursorLeave(pCur);
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Save the positions of any other cursors open on this table */
  clearCursorPosition(pCur);
  if( 
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  ){
    cursorLeave(pCur);
    return rc;
  }

  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->leafData );
  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
................................................................................
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
  sqlite3_free(newCell);
  cursorLeave(pCur);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
................................................................................
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;

  cursorEnter(pCur);
  assert( pPage->isInit );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
    cursorLeave(pCur);
    return rc;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    cursorLeave(pCur);
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){
    cursorLeave(pCur);
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){
    cursorLeave(pCur);
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3PagerWrite() on the page
  ** that the entry will be deleted from.
  */
  if( 
    (rc = restoreOrClearCursorPosition(pCur))!=0 ||
    (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur))!=0 ||
    (rc = sqlite3PagerWrite(pPage->pDbPage))!=0
  ){
    cursorLeave(pCur);
    return rc;
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  rc = clearCell(pPage, pCell);
  if( rc ){
    cursorLeave(pCur);
    return rc;
  }

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
................................................................................
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    rc = balance(pPage, 0);
  }
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
  cursorLeave(pCur);
  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**
................................................................................
*/
static int btreeCreateTable(Btree *p, int *piTable, int flags){
  BtShared *pBt = p->pBt;
  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;

  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction first */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
    return rc;
  }
  assert( !pBt->readOnly );

................................................................................
  int freePageFlag      /* Deallocate page if true */
){
  MemPage *pPage = 0;
  int rc;
  unsigned char *pCell;
  int i;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( pgno>sqlite3PagerPagecount(pBt->pPager) ){
    return SQLITE_CORRUPT_BKPT;
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
................................................................................
** meta[3] is updated by this procedure.
*/
static int btreeDropTable(Btree *p, int iTable, int *piMoved){
  int rc;
  MemPage *pPage = 0;
  BtShared *pBt = p->pBt;

  assert( sqlite3BtreeMutexHeld(pBt->mutex) );
  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* It is illegal to drop a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move another root-page to fill a gap left by the deleted
................................................................................
** is currently pointing to.
*/
int sqlite3BtreeFlags(BtCursor *pCur){
  /* TODO: What about CURSOR_REQUIRESEEK state? Probably need to call
  ** restoreOrClearCursorPosition() here.
  */
  MemPage *pPage = pCur->pPage;
  assert( sqlite3BtreeMutexHeld(pPage->pBt->mutex) );
  assert( pPage->pBt==pCur->pBt );
  return pPage ? pPage->aData[pPage->hdrOffset] : 0;
}


/*
** Return the pager associated with a BTree.  This routine is used for
................................................................................
** Return the full pathname of the underlying database file.
**
** The pager filename is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetFilename(Btree *p){
  assert( p->pBt->pPager!=0 );
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  return sqlite3PagerFilename(p->pBt->pPager);
}

/*
** Return the pathname of the directory that contains the database file.
**
** The pager directory name is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetDirname(Btree *p){
  assert( p->pBt->pPager!=0 );
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  return sqlite3PagerDirname(p->pBt->pPager);
}

/*
** Return the pathname of the journal file for this database. The return
** value of this routine is the same regardless of whether the journal file
** has been created or not.
**
** The pager journal filename is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetJournalname(Btree *p){
  assert( p->pBt->pPager!=0 );
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  return sqlite3PagerJournalname(p->pBt->pPager);
}

#ifndef SQLITE_OMIT_VACUUM
/*
** Copy the complete content of pBtFrom into pBtTo.  A transaction
** must be active for both files.
................................................................................

#endif /* SQLITE_OMIT_VACUUM */

/*
** Return non-zero if a transaction is active.
*/
int sqlite3BtreeIsInTrans(Btree *p){
  assert( p==0 || sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  return (p && (p->inTrans==TRANS_WRITE));
}

/*
** Return non-zero if a statement transaction is active.
*/
int sqlite3BtreeIsInStmt(Btree *p){
  assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  return (p->pBt && p->pBt->inStmt);
}

/*
** Return non-zero if a read (or write) transaction is active.
*/
int sqlite3BtreeIsInReadTrans(Btree *p){
  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  return (p && (p->inTrans!=TRANS_NONE));
}

/*
** This function returns a pointer to a blob of memory associated with
** a single shared-btree. The memory is used by client code for it's own
** purposes (for example, to store a high-level schema associated with 
................................................................................

/*
** Return true if another user of the same shared btree as the argument
** handle holds an exclusive lock on the sqlite_master table.
*/
int sqlite3BtreeSchemaLocked(Btree *p){
  int rc;
  assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
  sqlite3BtreeEnter(p);
  rc = (queryTableLock(p, MASTER_ROOT, READ_LOCK)!=SQLITE_OK);
  sqlite3BtreeLeave(p);
  return rc;
}


................................................................................
** Argument pCsr must be a cursor opened for writing on an 
** INTKEY table currently pointing at a valid table entry. 
** This function modifies the data stored as part of that entry.
** Only the data content may only be modified, it is not possible
** to change the length of the data stored.
*/
int sqlite3BtreePutData(BtCursor *pCsr, u32 offset, u32 amt, void *z){
  assert( sqlite3BtreeMutexHeld(pCsr->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(pCsr->pBtree->pSqlite->mutex) );
  assert(pCsr->isIncrblobHandle);
  if( pCsr->eState==CURSOR_REQUIRESEEK ){
    return SQLITE_ABORT;
  }

  /* Check some preconditions: 
  **   (a) the cursor is open for writing,
................................................................................
**
** This function sets a flag only. The actual page location cache
** (stored in BtCursor.aOverflow[]) is allocated and used by function
** accessPayload() (the worker function for sqlite3BtreeData() and
** sqlite3BtreePutData()).
*/
void sqlite3BtreeCacheOverflow(BtCursor *pCur){
  assert( sqlite3BtreeMutexHeld(pCur->pBt->mutex) );
  assert( sqlite3BtreeMutexHeld(pCur->pBtree->pSqlite->mutex) );
  assert(!pCur->isIncrblobHandle);
  assert(!pCur->aOverflow);
  pCur->isIncrblobHandle = 1;
}
#endif







|







 







<
|







 







<
|







 







<
|







 







>
>
>
>
>
>
>
>
>
>






|










|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|













|







 







|







 







<
<
<
<
<
<
<
<
<
<
<







 







|







 







<
|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|
<







 







|







 







|






<







|



<







 







|







 







|







 







|







 







|







 







|





<






<







 







|







<







 







|







 







|






|







 







|







 







|







 







|













<











|







 







|







 







|







 







|
|







 







|
|







 







|
|







 







|







 







|

<







 







|







 







|

<







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|
<







 







|



<




<



<









<







 







<







 







|




<




<



<



<













<













<







 







<







 







<
|







 







|







 







|







 







|







 







|











|













|







 







|







|
<







|







 







|







 







|
|







 







|
|





5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
..
92
93
94
95
96
97
98

99
100
101
102
103
104
105
106
...
144
145
146
147
148
149
150

151
152
153
154
155
156
157
158
...
210
211
212
213
214
215
216

217
218
219
220
221
222
223
224
...
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
...
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
...
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
...
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
...
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
...
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
...
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
...
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
...
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
...
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
...
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
...
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
...
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
...
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
...
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
...
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
....
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
....
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
....
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
....
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
....
1396
1397
1398
1399
1400
1401
1402











1403
1404
1405
1406
1407
1408
1409
....
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
....
1668
1669
1670
1671
1672
1673
1674

1675
1676
1677
1678
1679
1680
1681
1682
....
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
....
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
....
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
....
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
....
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
....
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
....
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
....
2596
2597
2598
2599
2600
2601
2602
2603

2604
2605
2606
2607
2608
2609
2610
....
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
....
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717

2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728

2729
2730
2731
2732
2733
2734
2735
....
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
....
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
....
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
....
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
....
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122

3123
3124
3125
3126
3127
3128

3129
3130
3131
3132
3133
3134
3135
....
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151

3152
3153
3154
3155
3156
3157
3158
....
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
....
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
....
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
....
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
....
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314

3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
....
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
....
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
....
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
....
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
....
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
....
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
....
3684
3685
3686
3687
3688
3689
3690
3691
3692

3693
3694
3695
3696
3697
3698
3699
....
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
....
3750
3751
3752
3753
3754
3755
3756
3757
3758

3759
3760
3761
3762
3763
3764
3765
....
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
....
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
....
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
....
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
....
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
....
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
....
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
....
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
....
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
....
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
....
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
....
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
....
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
....
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
....
5435
5436
5437
5438
5439
5440
5441
5442

5443
5444
5445
5446
5447
5448
5449
....
5478
5479
5480
5481
5482
5483
5484
5485
5486
5487
5488

5489
5490
5491
5492

5493
5494
5495

5496
5497
5498
5499
5500
5501
5502
5503
5504

5505
5506
5507
5508
5509
5510
5511
....
5546
5547
5548
5549
5550
5551
5552

5553
5554
5555
5556
5557
5558
5559
....
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572

5573
5574
5575
5576

5577
5578
5579

5580
5581
5582

5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595

5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608

5609
5610
5611
5612
5613
5614
5615
....
5660
5661
5662
5663
5664
5665
5666

5667
5668
5669
5670
5671
5672
5673
....
5680
5681
5682
5683
5684
5685
5686

5687
5688
5689
5690
5691
5692
5693
5694
....
5828
5829
5830
5831
5832
5833
5834
5835
5836
5837
5838
5839
5840
5841
5842
....
5910
5911
5912
5913
5914
5915
5916
5917
5918
5919
5920
5921
5922
5923
5924
....
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
....
6571
6572
6573
6574
6575
6576
6577
6578
6579
6580
6581
6582
6583
6584
6585
6586
6587
6588
6589
6590
6591
6592
6593
6594
6595
6596
6597
6598
6599
6600
6601
6602
6603
6604
6605
6606
6607
6608
6609
6610
6611
....
6677
6678
6679
6680
6681
6682
6683
6684
6685
6686
6687
6688
6689
6690
6691
6692

6693
6694
6695
6696
6697
6698
6699
6700
6701
6702
6703
6704
6705
6706
6707
....
6730
6731
6732
6733
6734
6735
6736
6737
6738
6739
6740
6741
6742
6743
6744
....
6766
6767
6768
6769
6770
6771
6772
6773
6774
6775
6776
6777
6778
6779
6780
6781
....
6804
6805
6806
6807
6808
6809
6810
6811
6812
6813
6814
6815
6816
6817
** 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.416 2007/08/29 04:00:58 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"

................................................................................
** SQLITE_OK if the lock may be obtained (by calling lockTable()), or
** SQLITE_LOCKED if not.
*/
static int queryTableLock(Btree *p, Pgno iTab, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pIter;


  assert( sqlite3BtreeHoldsMutex(p) );
  
  /* This is a no-op if the shared-cache is not enabled */
  if( !p->sharable ){
    return SQLITE_OK;
  }

  /* This (along with lockTable()) is where the ReadUncommitted flag is
................................................................................
** SQLITE_NOMEM may also be returned.
*/
static int lockTable(Btree *p, Pgno iTable, u8 eLock){
  BtShared *pBt = p->pBt;
  BtLock *pLock = 0;
  BtLock *pIter;


  assert( sqlite3BtreeHoldsMutex(p) );

  /* This is a no-op if the shared-cache is not enabled */
  if( !p->sharable ){
    return SQLITE_OK;
  }

  assert( SQLITE_OK==queryTableLock(p, iTable, eLock) );
................................................................................
/*
** Release all the table locks (locks obtained via calls to the lockTable()
** procedure) held by Btree handle p.
*/
static void unlockAllTables(Btree *p){
  BtLock **ppIter = &p->pBt->pLock;


  assert( sqlite3BtreeHoldsMutex(p) );
  assert( p->sharable || 0==*ppIter );

  while( *ppIter ){
    BtLock *pLock = *ppIter;
    if( pLock->pBtree==p ){
      *ppIter = pLock->pNext;
      sqlite3_free(pLock);
................................................................................
      ppIter = &pLock->pNext;
    }
  }
}
#endif /* SQLITE_OMIT_SHARED_CACHE */

static void releasePage(MemPage *pPage);  /* Forward reference */

/*
** Verify that the cursor holds a mutex on the BtShared
*/
#ifndef NDEBUG
static int cursorHoldsMutex(BtCursor *p){
  return sqlite3BtreeHoldsMutex(p->pBtree);
}
#endif


#ifndef SQLITE_OMIT_INCRBLOB
/*
** Invalidate the overflow page-list cache for cursor pCur, if any.
*/
static void invalidateOverflowCache(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  sqlite3_free(pCur->aOverflow);
  pCur->aOverflow = 0;
}

/*
** Invalidate the overflow page-list cache for all cursors opened
** on the shared btree structure pBt.
*/
static void invalidateAllOverflowCache(BtShared *pBt){
  BtCursor *p;
  assert( sqlite3_mutex_held(pBt->mutex) );
  for(p=pBt->pCursor; p; p=p->pNext){
    invalidateOverflowCache(p);
  }
}
#else
  #define invalidateOverflowCache(x)
  #define invalidateAllOverflowCache(x)
................................................................................
** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.
*/
static int saveCursorPosition(BtCursor *pCur){
  int rc;

  assert( CURSOR_VALID==pCur->eState );
  assert( 0==pCur->pKey );
  assert( cursorHoldsMutex(pCur) );

  rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

  /* If this is an intKey table, then the above call to BtreeKeySize()
  ** stores the integer key in pCur->nKey. In this case this value is
  ** all that is required. Otherwise, if pCur is not open on an intKey
  ** table, then malloc space for and store the pCur->nKey bytes of key 
................................................................................
/*
** Save the positions of all cursors except pExcept open on the table 
** with root-page iRoot. Usually, this is called just before cursor
** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).
*/
static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){
  BtCursor *p;
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pExcept==0 || pExcept->pBt==pBt );
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 
        p->eState==CURSOR_VALID ){
      int rc = saveCursorPosition(p);
      if( SQLITE_OK!=rc ){
        return rc;
................................................................................
  return SQLITE_OK;
}

/*
** Clear the current cursor position.
*/
static void clearCursorPosition(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  sqlite3_free(pCur->pKey);
  pCur->pKey = 0;
  pCur->eState = CURSOR_INVALID;
}

/*
** Restore the cursor to the position it was in (or as close to as possible)
................................................................................
**
** If the second argument argument - doSeek - is false, then instead of 
** returning the cursor to it's saved position, any saved position is deleted
** and the cursor state set to CURSOR_INVALID.
*/
int sqlite3BtreeRestoreOrClearCursorPosition(BtCursor *pCur){
  int rc;
  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_REQUIRESEEK );
#ifndef SQLITE_OMIT_INCRBLOB
  if( pCur->isIncrblobHandle ){
    return SQLITE_ABORT;
  }
#endif
  pCur->eState = CURSOR_INVALID;
................................................................................
/*
** 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, iPtrMap, ret;
  assert( sqlite3_mutex_held(pBt->mutex) );
  nPagesPerMapPage = (pBt->usableSize/5)+1;
  iPtrMap = (pgno-2)/nPagesPerMapPage;
  ret = (iPtrMap*nPagesPerMapPage) + 2; 
  if( ret==PENDING_BYTE_PAGE(pBt) ){
    ret++;
  }
  return ret;
................................................................................
static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){
  DbPage *pDbPage;  /* The pointer map page */
  u8 *pPtrmap;      /* The pointer map data */
  Pgno iPtrmap;     /* The pointer map page number */
  int offset;       /* Offset in pointer map page */
  int rc;

  assert( sqlite3_mutex_held(pBt->mutex) );
  /* The master-journal page number must never be used as a pointer map page */
  assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );

  assert( pBt->autoVacuum );
  if( key==0 ){
    return SQLITE_CORRUPT_BKPT;
  }
................................................................................
static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  DbPage *pDbPage;   /* The pointer map page */
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

  assert( sqlite3_mutex_held(pBt->mutex) );

  iPtrmap = PTRMAP_PAGENO(pBt, key);
  rc = sqlite3PagerGet(pBt->pPager, iPtrmap, &pDbPage);
  if( rc!=0 ){
    return rc;
  }
  pPtrmap = (u8 *)sqlite3PagerGetData(pDbPage);
................................................................................

/*
** This a more complex version of sqlite3BtreeFindCell() that works for
** pages that do contain overflow cells.  See insert
*/
static u8 *findOverflowCell(MemPage *pPage, int iCell){
  int i;
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  for(i=pPage->nOverflow-1; i>=0; i--){
    int k;
    struct _OvflCell *pOvfl;
    pOvfl = &pPage->aOvfl[i];
    k = pOvfl->idx;
    if( k<=iCell ){
      if( k==iCell ){
................................................................................
  MemPage *pPage,         /* Page containing the cell */
  u8 *pCell,              /* Pointer to the cell text. */
  CellInfo *pInfo         /* Fill in this structure */
){
  int n;                  /* Number bytes in cell content header */
  u32 nPayload;           /* Number of bytes of cell payload */

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  pInfo->pCell = pCell;
  assert( pPage->leaf==0 || pPage->leaf==1 );
  n = pPage->childPtrSize;
  assert( n==4-4*pPage->leaf );
  if( pPage->hasData ){
    n += getVarint32(&pCell[n], &nPayload);
................................................................................
/*
** If the cell with index iCell on page pPage contains a pointer
** to an overflow page, insert an entry into the pointer-map
** for the overflow page.
*/
static int ptrmapPutOvfl(MemPage *pPage, int iCell){
  u8 *pCell;
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pCell = findOverflowCell(pPage, iCell);
  return ptrmapPutOvflPtr(pPage, pCell);
}
#endif


/*
................................................................................
  unsigned char *data;       /* The page data */
  unsigned char *temp;       /* Temp area for cell content */

  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt!=0 );
  assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
  assert( pPage->nOverflow==0 );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  temp = sqlite3_malloc( pPage->pBt->pageSize );
  if( temp==0 ) return SQLITE_NOMEM;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  cellOffset = pPage->cellOffset;
  nCell = pPage->nCell;
  assert( nCell==get2byte(&data[hdr+3]) );
................................................................................
  int nCell;
  int cellOffset;
  unsigned char *data;
  
  data = pPage->aData;
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( nByte<4 ) nByte = 4;
  if( pPage->nFree<nByte || pPage->nOverflow>0 ) return 0;
  pPage->nFree -= nByte;
  hdr = pPage->hdrOffset;

  nFrag = data[hdr+7];
  if( nFrag<60 ){
................................................................................
  int addr, pbegin, hdr;
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
  assert( (start + size)<=pPage->pBt->usableSize );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( size<4 ) size = 4;

#ifdef SQLITE_SECURE_DELETE
  /* Overwrite deleted information with zeros when the SECURE_DELETE 
  ** option is enabled at compile-time */
  memset(&data[start], 0, size);
#endif
................................................................................
** Decode the flags byte (the first byte of the header) for a page
** and initialize fields of the MemPage structure accordingly.
*/
static void decodeFlags(MemPage *pPage, int flagByte){
  BtShared *pBt;     /* A copy of pPage->pBt */

  assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
  pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
  pPage->leaf = (flagByte & PTF_LEAF)!=0;
  pPage->childPtrSize = 4*(pPage->leaf==0);
  pBt = pPage->pBt;
  if( flagByte & PTF_LEAFDATA ){
    pPage->leafData = 1;
................................................................................
  int cellOffset;    /* Offset from start of page to first cell pointer */
  int nFree;         /* Number of unused bytes on the page */
  int top;           /* First byte of the cell content area */

  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit ) return SQLITE_OK;
................................................................................
  BtShared *pBt = pPage->pBt;
  int hdr = pPage->hdrOffset;
  int first;

  assert( sqlite3PagerPagenumber(pPage->pDbPage)==pPage->pgno );
  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( sqlite3_mutex_held(pBt->mutex) );
  memset(&data[hdr], 0, pBt->usableSize - hdr);
  data[hdr] = flags;
  first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
  memset(&data[hdr+1], 0, 4);
  data[hdr+7] = 0;
  put2byte(&data[hdr+5], pBt->usableSize);
  pPage->nFree = pBt->usableSize - first;
................................................................................
  MemPage **ppPage,    /* Return the page in this parameter */
  int noContent        /* Do not load page content if true */
){
  int rc;
  MemPage *pPage;
  DbPage *pDbPage;

  assert( sqlite3_mutex_held(pBt->mutex) );
  rc = sqlite3PagerAcquire(pBt->pPager, pgno, (DbPage**)&pDbPage, noContent);
  if( rc ) return rc;
  pPage = (MemPage *)sqlite3PagerGetExtra(pDbPage);
  pPage->aData = sqlite3PagerGetData(pDbPage);
  pPage->pDbPage = pDbPage;
  pPage->pBt = pBt;
  pPage->pgno = pgno;
................................................................................
static int getAndInitPage(
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }
  rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);
  if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
    rc = sqlite3BtreeInitPage(*ppPage, pParent);
  }
................................................................................
** call to sqlite3BtreeGetPage.
*/
static void releasePage(MemPage *pPage){
  if( pPage ){
    assert( pPage->aData );
    assert( pPage->pBt );
    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
    assert( sqlite3_mutex_held(pPage->pBt->mutex) );
    sqlite3PagerUnref(pPage->pDbPage);
  }
}

/*
** This routine is called when the reference count for a page
** reaches zero.  We need to unref the pParent pointer when that
** happens.
*/
static void pageDestructor(DbPage *pData, int pageSize){
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  assert( pPage->isInit==0 || sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    assert( pPage->isInit==1 );
    assert( pParent->pBt==pPage->pBt );
    pPage->pParent = 0;
    releasePage(pParent);
  }
................................................................................
** page to agree with the restored data.
*/
static void pageReinit(DbPage *pData, int pageSize){
  MemPage *pPage;
  assert( (pageSize & 7)==0 );
  pPage = (MemPage *)sqlite3PagerGetExtra(pData);
  if( pPage->isInit ){
    assert( sqlite3_mutex_held(pPage->pBt->mutex) );
    pPage->isInit = 0;
    sqlite3BtreeInitPage(pPage, pPage->pParent);
  }
}

/*
** Open a database file.
................................................................................
  if( p->pNext ) p->pNext->pPrev = p->pPrev;
#endif

  sqlite3_free(p);
  return SQLITE_OK;
}












/*
** Change the busy handler callback function.
*/
int sqlite3BtreeSetBusyHandler(Btree *p, BusyHandler *pHandler){
  BtShared *pBt = p->pBt;
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  sqlite3BtreeEnter(p);
................................................................................
** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
** is returned if we run out of memory. 
*/
static int lockBtree(BtShared *pBt){
  int rc, pageSize;
  MemPage *pPage1;

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pBt->pPage1 ) return SQLITE_OK;
  rc = sqlite3BtreeGetPage(pBt, 1, &pPage1, 0);
  if( rc!=SQLITE_OK ) return rc;
  

  /* Do some checking to help insure the file we opened really is
  ** a valid database file. 
................................................................................
/*
** This routine works like lockBtree() except that it also invokes the
** busy callback if there is lock contention.
*/
static int lockBtreeWithRetry(Btree *pRef){
  int rc = SQLITE_OK;


  assert( sqlite3BtreeHoldsMutex(pRef) );
  if( pRef->inTrans==TRANS_NONE ){
    u8 inTransaction = pRef->pBt->inTransaction;
    btreeIntegrity(pRef);
    rc = sqlite3BtreeBeginTrans(pRef, 0);
    pRef->pBt->inTransaction = inTransaction;
    pRef->inTrans = TRANS_NONE;
    if( rc==SQLITE_OK ){
................................................................................
** has the effect of releasing the read lock.
**
** If there are any outstanding cursors, this routine is a no-op.
**
** If there is a transaction in progress, this routine is a no-op.
*/
static void unlockBtreeIfUnused(BtShared *pBt){
  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pBt->inTransaction==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
    if( sqlite3PagerRefcount(pBt->pPager)>=1 ){
      if( pBt->pPage1->aData==0 ){
        MemPage *pPage = pBt->pPage1;
        pPage->aData = &((u8*)pPage)[-pBt->pageSize];
        pPage->pBt = pBt;
        pPage->pgno = 1;
................................................................................
** file.
*/
static int newDatabase(BtShared *pBt){
  MemPage *pP1;
  unsigned char *data;
  int rc;

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( sqlite3PagerPagecount(pBt->pPager)>0 ) return SQLITE_OK;
  pP1 = pBt->pPage1;
  assert( pP1!=0 );
  data = pP1->aData;
  rc = sqlite3PagerWrite(pP1->pDbPage);
  if( rc ) return rc;
  memcpy(data, zMagicHeader, sizeof(zMagicHeader));
................................................................................
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc;                            /* Return code */
  BtShared *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  rc = sqlite3BtreeInitPage(pPage, pPage->pParent);
  if( rc!=SQLITE_OK ){
    goto set_child_ptrmaps_out;
  }
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
................................................................................
** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
**                   page pointed to by one of the cells on pPage.
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static int modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( eType==PTRMAP_OVERFLOW2 ){
    /* The pointer is always the first 4 bytes of the page in this case.  */
    if( get4byte(pPage->aData)!=iFrom ){
      return SQLITE_CORRUPT_BKPT;
    }
    put4byte(pPage->aData, iTo);
  }else{
................................................................................
  MemPage *pPtrPage;   /* The page that contains a pointer to pDbPage */
  Pgno iDbPage = pDbPage->pgno;
  Pager *pPager = pBt->pPager;
  int rc;

  assert( eType==PTRMAP_OVERFLOW2 || eType==PTRMAP_OVERFLOW1 || 
      eType==PTRMAP_BTREE || eType==PTRMAP_ROOTPAGE );
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pDbPage->pBt==pBt );

  /* Move page iDbPage from it's current location to page number iFreePage */
  TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n", 
      iDbPage, iFreePage, iPtrPage, eType));
  rc = sqlite3PagerMovepage(pPager, pDbPage->pDbPage, iFreePage);
  if( rc!=SQLITE_OK ){
................................................................................
** number of pages the database file will contain after this 
** process is complete.
*/
static int incrVacuumStep(BtShared *pBt, Pgno nFin){
  Pgno iLastPg;             /* Last page in the database */
  Pgno nFreeList;           /* Number of pages still on the free-list */

  assert( sqlite3_mutex_held(pBt->mutex) );
  iLastPg = pBt->nTrunc;
  if( iLastPg==0 ){
    iLastPg = sqlite3PagerPagecount(pBt->pPager);
  }

  if( !PTRMAP_ISPAGE(pBt, iLastPg) && iLastPg!=PENDING_BYTE_PAGE(pBt) ){
    int rc;
................................................................................
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  int rc = SQLITE_OK;
  Pager *pPager = pBt->pPager;
#ifndef NDEBUG
  int nRef = sqlite3PagerRefcount(pPager);
#endif

  assert( sqlite3_mutex_held(pBt->mutex) );
  invalidateAllOverflowCache(pBt);
  assert(pBt->autoVacuum);
  if( !pBt->incrVacuum ){
    Pgno nFin = 0;

    if( pBt->nTrunc==0 ){
      Pgno nFree;
................................................................................
  void *pArg,                                 /* First arg to xCompare() */
  BtCursor **ppCur                            /* Write new cursor here */
){
  int rc;
  BtCursor *pCur;
  BtShared *pBt = p->pBt;

  assert( sqlite3BtreeHoldsMutex(p) );

  *ppCur = 0;
  if( wrFlag ){
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(p, iTable, 0) ){
      return SQLITE_LOCKED;
................................................................................
/*
** Close a cursor.  The read lock on the database file is released
** when the last cursor is closed.
*/
int sqlite3BtreeCloseCursor(BtCursor *pCur){
  BtShared *pBt = pCur->pBt;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  clearCursorPosition(pCur);
  if( pCur->pPrev ){
    pCur->pPrev->pNext = pCur->pNext;
  }else{
    pBt->pCursor = pCur->pNext;
  }
................................................................................
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.
*/
void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur){
  assert( cursorHoldsMutex(pCur) );
  memcpy(pTempCur, pCur, sizeof(*pCur));
  pTempCur->pNext = 0;
  pTempCur->pPrev = 0;
  if( pTempCur->pPage ){
    sqlite3PagerRef(pTempCur->pPage->pDbPage);
  }

}

/*
** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
** function above.
*/
void sqlite3BtreeReleaseTempCursor(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  if( pCur->pPage ){
    sqlite3PagerUnref(pCur->pPage->pDbPage);
  }

}

/*
** Make sure the BtCursor* given in the argument has a valid
** BtCursor.info structure.  If it is not already valid, call
** sqlite3BtreeParseCell() to fill it in.
**
................................................................................
**
** For a table with the INTKEY flag set, this routine returns the key
** itself, not the number of bytes in the key.
*/
int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
    if( pCur->eState==CURSOR_INVALID ){
      *pSize = 0;
    }else{
      getCellInfo(pCur);
................................................................................
** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_INVALID || pCur->eState==CURSOR_VALID );
    if( pCur->eState==CURSOR_INVALID ){
      /* Not pointing at a valid entry - set *pSize to 0. */
      *pSize = 0;
    }else{
................................................................................
  Pgno ovfl,                   /* Overflow page */
  MemPage **ppPage,            /* OUT: MemPage handle */
  Pgno *pPgnoNext              /* OUT: Next overflow page number */
){
  Pgno next = 0;
  int rc;

  assert( sqlite3_mutex_held(pBt->mutex) );
  /* One of these must not be NULL. Otherwise, why call this function? */
  assert(ppPage || pPgnoNext);

  /* If pPgnoNext is NULL, then this function is being called to obtain
  ** a MemPage* reference only. No page-data is required in this case.
  */
  if( !pPgnoNext ){
................................................................................
  MemPage *pPage = pCur->pPage;     /* Btree page of current cursor entry */
  BtShared *pBt = pCur->pBt;        /* Btree this cursor belongs to */

  assert( pPage );
  assert( pCur->eState==CURSOR_VALID );
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  assert( offset>=0 );
  assert( cursorHoldsMutex(pCur) );

  getCellInfo(pCur);
  aPayload = pCur->info.pCell + pCur->info.nHeader;
  nKey = (pPage->intKey ? 0 : pCur->info.nKey);

  if( skipKey ){
    offset += nKey;
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    if( pCur->pPage->intKey ){

      return SQLITE_CORRUPT_BKPT;
    }
    assert( pCur->pPage->intKey==0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, (unsigned char*)pBuf, 0, 0);
  }

  return rc;
}

/*
** Read part of the data associated with cursor pCur.  Exactly
** "amt" bytes will be transfered into pBuf[].  The transfer
** begins at "offset".
................................................................................
** Return SQLITE_OK on success or an error code if anything goes
** wrong.  An error is returned if "offset+amt" is larger than
** the available payload.
*/
int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc==SQLITE_OK ){
    assert( pCur->eState==CURSOR_VALID );
    assert( pCur->pPage!=0 );
    assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
    rc = accessPayload(pCur, offset, amt, pBuf, 1, 0);
  }

  return rc;
}

/*
** Return a pointer to payload information from the entry that the 
** pCur cursor is pointing to.  The pointer is to the beginning of
** the key if skipKey==0 and it points to the beginning of data if
................................................................................
  unsigned char *aPayload;
  MemPage *pPage;
  u32 nKey;
  int nLocal;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->eState==CURSOR_VALID );
  assert( cursorHoldsMutex(pCur) );
  pPage = pCur->pPage;
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  getCellInfo(pCur);
  aPayload = pCur->info.pCell;
  aPayload += pCur->info.nHeader;
  if( pPage->intKey ){
    nKey = 0;
................................................................................
** Hence, a mutex on the BtShared should be held prior to calling
** this routine.
**
** These routines is used to get quick access to key and data
** in the common case where no overflow pages are used.
*/
const void *sqlite3BtreeKeyFetch(BtCursor *pCur, int *pAmt){
  assert( cursorHoldsMutex(pCur) );
  if( pCur->eState==CURSOR_VALID ){
    return (const void*)fetchPayload(pCur, pAmt, 0);
  }
  return 0;
}
const void *sqlite3BtreeDataFetch(BtCursor *pCur, int *pAmt){
  assert( cursorHoldsMutex(pCur) );
  if( pCur->eState==CURSOR_VALID ){
    return (const void*)fetchPayload(pCur, pAmt, 1);
  }
  return 0;
}


................................................................................
*/
static int moveToChild(BtCursor *pCur, u32 newPgno){
  int rc;
  MemPage *pNewPage;
  MemPage *pOldPage;
  BtShared *pBt = pCur->pBt;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
  if( rc ) return rc;
  pNewPage->idxParent = pCur->idx;
  pOldPage = pCur->pPage;
  pOldPage->idxShift = 0;
  releasePage(pOldPage);
................................................................................
** is empty except for the right-pointer.  In such cases the
** virtual root page is the page that the right-pointer of page
** 1 is pointing to.
*/
int sqlite3BtreeIsRootPage(MemPage *pPage){
  MemPage *pParent;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pParent = pPage->pParent;
  if( pParent==0 ) return 1;
  if( pParent->pgno>1 ) return 0;
  if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
  return 0;
}

................................................................................
** the largest cell index.
*/
void sqlite3BtreeMoveToParent(BtCursor *pCur){
  MemPage *pParent;
  MemPage *pPage;
  int idxParent;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( !sqlite3BtreeIsRootPage(pPage) );
  pParent = pPage->pParent;
  assert( pParent!=0 );
  idxParent = pPage->idxParent;
  sqlite3PagerRef(pParent->pDbPage);
  releasePage(pPage);
  pCur->pPage = pParent;
  pCur->info.nSize = 0;
  assert( pParent->idxShift==0 );
  pCur->idx = idxParent;

}

/*
** Move the cursor to the root page
*/
static int moveToRoot(BtCursor *pCur){
  MemPage *pRoot;
  int rc = SQLITE_OK;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;

  assert( cursorHoldsMutex(pCur) );
  if( pCur->eState==CURSOR_REQUIRESEEK ){
    clearCursorPosition(pCur);
  }
  pRoot = pCur->pPage;
  if( pRoot && pRoot->pgno==pCur->pgnoRoot ){
    assert( pRoot->isInit );
  }else{
................................................................................
** in ascending order.
*/
static int moveToLeftmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    pgno = get4byte(findCell(pPage, pCur->idx));
    rc = moveToChild(pCur, pgno);
  }
  return rc;
................................................................................
** key in ascending order.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc = SQLITE_OK;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  assert( pCur->eState==CURSOR_VALID );
  while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCur->idx = pPage->nCell;
    rc = moveToChild(pCur, pgno);
  }
  if( rc==SQLITE_OK ){
................................................................................
/* Move the cursor to the first entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( pCur->eState==CURSOR_INVALID ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
      rc = SQLITE_OK;
    }else{
................................................................................
/* Move the cursor to the last entry in the table.  Return SQLITE_OK
** on success.  Set *pRes to 0 if the cursor actually points to something
** or set *pRes to 1 if the table is empty.
*/
int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
  int rc;
 
  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc==SQLITE_OK ){
    if( CURSOR_INVALID==pCur->eState ){
      assert( pCur->pPage->nCell==0 );
      *pRes = 1;
    }else{
      assert( pCur->eState==CURSOR_VALID );
................................................................................
  const void *pKey,      /* The key content for indices.  Not used by tables */
  i64 nKey,              /* Size of pKey.  Or the key for tables */
  int biasRight,         /* If true, bias the search to the high end */
  int *pRes              /* Search result flag */
){
  int rc;

  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  rc = moveToRoot(pCur);
  if( rc ){
    return rc;
  }
  assert( pCur->pPage );
  assert( pCur->pPage->isInit );
  if( pCur->eState==CURSOR_INVALID ){
................................................................................
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
static int btreeNext(BtCursor *pCur, int *pRes){
  int rc;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  assert( pRes!=0 );
  pPage = pCur->pPage;
  if( CURSOR_INVALID==pCur->eState ){
................................................................................
    return SQLITE_OK;
  }
  rc = moveToLeftmost(pCur);
  return rc;
}
int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
  int rc;
  assert( cursorHoldsMutex(pCur) );
  rc = btreeNext(pCur, pRes);

  return rc;
}


/*
** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
................................................................................
** this routine was called, then set *pRes=1.
*/
static int btreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  Pgno pgno;
  MemPage *pPage;

  assert( cursorHoldsMutex(pCur) );
  rc = restoreOrClearCursorPosition(pCur);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( CURSOR_INVALID==pCur->eState ){
    *pRes = 1;
    return SQLITE_OK;
................................................................................
    }
  }
  *pRes = 0;
  return rc;
}
int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
  int rc;
  assert( cursorHoldsMutex(pCur) );
  rc = btreePrevious(pCur, pRes);

  return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlite3PagerWrite()
................................................................................
  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */
  MemPage *pTrunk = 0;
  MemPage *pPrevTrunk = 0;

  assert( sqlite3_mutex_held(pBt->mutex) );
  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    Pgno iTrunk;
    u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
    
................................................................................
*/
static int freePage(MemPage *pPage){
  BtShared *pBt = pPage->pBt;
  MemPage *pPage1 = pBt->pPage1;
  int rc, n, k;

  /* Prepare the page for freeing */
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( pPage->pgno>1 );
  pPage->isInit = 0;
  releasePage(pPage->pParent);
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3PagerWrite(pPage1->pDbPage);
................................................................................
  BtShared *pBt = pPage->pBt;
  CellInfo info;
  Pgno ovflPgno;
  int rc;
  int nOvfl;
  int ovflPageSize;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  if( info.iOverflow==0 ){
    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  ovflPageSize = pBt->usableSize - 4;
  nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize;
................................................................................
  unsigned char *pPrior;
  unsigned char *pPayload;
  BtShared *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* Fill in the header. */
  nHeader = 0;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
................................................................................
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){
  MemPage *pThis;
  DbPage *pDbPage;

  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pNewParent!=0 );
  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
  pDbPage = sqlite3PagerLookup(pBt->pPager, pgno);
  if( pDbPage ){
    pThis = (MemPage *)sqlite3PagerGetExtra(pDbPage);
    if( pThis->isInit ){
................................................................................
** another.
*/
static int reparentChildPages(MemPage *pPage){
  int i;
  BtShared *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->leaf ) return SQLITE_OK;

  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = reparentPage(pBt, get4byte(pCell), pPage, i);
      if( rc!=SQLITE_OK ) return rc;
................................................................................
  int pc;         /* Offset to cell content of cell being deleted */
  u8 *data;       /* pPage->aData */
  u8 *ptr;        /* Used to move bytes around within data[] */

  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, idx) );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  data = pPage->aData;
  ptr = &data[pPage->cellOffset + 2*idx];
  pc = get2byte(ptr);
  assert( pc>10 && pc+sz<=pPage->pBt->usableSize );
  freeSpace(pPage, pc, sz);
  for(i=idx+1; i<pPage->nCell; i++, ptr+=2){
    ptr[0] = ptr[2];
................................................................................
  int hdr;          /* Offset into data[] of the page header */
  int cellOffset;   /* Address of first cell pointer in data[] */
  u8 *data;         /* The content of the whole page */
  u8 *ptr;          /* Used for moving information around in data[] */

  assert( i>=0 && i<=pPage->nCell+pPage->nOverflow );
  assert( sz==cellSizePtr(pPage, pCell) );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->nOverflow || sz+2>pPage->nFree ){
    if( pTemp ){
      memcpy(pTemp+nSkip, pCell+nSkip, sz-nSkip);
      pCell = pTemp;
    }
    j = pPage->nOverflow++;
    assert( j<sizeof(pPage->aOvfl)/sizeof(pPage->aOvfl[0]) );
................................................................................
  int totalSize;    /* Total size of all cells */
  int hdr;          /* Index of page header */
  int cellptr;      /* Address of next cell pointer */
  int cellbody;     /* Address of next cell body */
  u8 *data;         /* Data for the page */

  assert( pPage->nOverflow==0 );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  totalSize = 0;
  for(i=0; i<nCell; i++){
    totalSize += aSize[i];
  }
  assert( totalSize+2*nCell<=pPage->nFree );
  assert( pPage->nCell==0 );
  cellptr = pPage->cellOffset;
................................................................................
  int szCell;
  CellInfo info;
  BtShared *pBt = pPage->pBt;
  int parentIdx = pParent->nCell;   /* pParent new divider cell index */
  int parentSize;                   /* Size of new divider cell */
  u8 parentCell[64];                /* Space for the new divider cell */

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* Allocate a new page. Insert the overflow cell from pPage
  ** into it. Then remove the overflow cell from pPage.
  */
  rc = allocateBtreePage(pBt, &pNew, &pgnoNew, 0, 0);
  if( rc!=SQLITE_OK ){
    return rc;
................................................................................
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
#ifndef SQLITE_OMIT_AUTOVACUUM
  u8 *aFrom = 0;
#endif

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
................................................................................
  BtShared *pBt;                  /* The main BTree structure */
  int mxCellPerPage;           /* Maximum number of cells per page */
  u8 **apCell;                 /* All cells from pages being balanced */
  int *szCell;                 /* Local size of all cells */

  assert( pPage->pParent==0 );
  assert( pPage->nCell==0 );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  pBt = pPage->pBt;
  mxCellPerPage = MX_CELL(pBt);
  apCell = sqlite3_malloc( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
  if( apCell==0 ) return SQLITE_NOMEM;
  szCell = (int*)&apCell[mxCellPerPage];
  if( pPage->leaf ){
    /* The table is completely empty */
................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  assert( sqlite3_mutex_held(pBt->mutex) );
  rc = allocateBtreePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3PagerIswriteable(pChild->pDbPage) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
................................................................................

/*
** Decide if the page pPage needs to be balanced.  If balancing is
** required, call the appropriate balancing routine.
*/
static int balance(MemPage *pPage, int insert){
  int rc = SQLITE_OK;
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->pParent==0 ){
    rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc==SQLITE_OK && pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( rc==SQLITE_OK && pPage->nCell==0 ){
      rc = balance_shallower(pPage);
................................................................................
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBtree, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  BtShared *pBt = pBtree->pBt;
  sqlite3 *db = pBtree->pSqlite;
  assert( sqlite3BtreeHoldsMutex(pBtree) );

  for(p=pBt->pCursor; p; p=p->pNext){
    if( p==pExclude ) continue;
    if( p->eState!=CURSOR_VALID ) continue;
    if( p->pgnoRoot!=pgnoRoot ) continue;
    if( p->wrFlag==0 ){
      sqlite3 *dbOther = p->pBtree->pSqlite;
      if( dbOther==0 ||
................................................................................
  int szNew;
  MemPage *pPage;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;

  assert( cursorHoldsMutex(pCur) );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;

    return rc;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){

    return SQLITE_PERM;   /* Cursor not open for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){

    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Save the positions of any other cursors open on this table */
  clearCursorPosition(pCur);
  if( 
    SQLITE_OK!=(rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur)) ||
    SQLITE_OK!=(rc = sqlite3BtreeMoveto(pCur, pKey, nKey, appendBias, &loc))
  ){

    return rc;
  }

  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->leafData );
  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
................................................................................
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
  sqlite3_free(newCell);

  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
** is left pointing at a random location.
*/
................................................................................
  MemPage *pPage = pCur->pPage;
  unsigned char *pCell;
  int rc;
  Pgno pgnoChild = 0;
  Btree *p = pCur->pBtree;
  BtShared *pBt = p->pBt;

  assert( cursorHoldsMutex(pCur) );
  assert( pPage->isInit );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction before doing a delete */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;

    return rc;
  }
  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){

    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){

    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pCur->pBtree, pCur->pgnoRoot, pCur) ){

    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Restore the current cursor position (a no-op if the cursor is not in 
  ** CURSOR_REQUIRESEEK state) and save the positions of any other cursors 
  ** open on the same table. Then call sqlite3PagerWrite() on the page
  ** that the entry will be deleted from.
  */
  if( 
    (rc = restoreOrClearCursorPosition(pCur))!=0 ||
    (rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur))!=0 ||
    (rc = sqlite3PagerWrite(pPage->pDbPage))!=0
  ){

    return rc;
  }

  /* Locate the cell within it's page and leave pCell pointing to the
  ** data. The clearCell() call frees any overflow pages associated with the
  ** cell. The cell itself is still intact.
  */
  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);
  }
  rc = clearCell(pPage, pCell);
  if( rc ){

    return rc;
  }

  if( !pPage->leaf ){
    /*
    ** The entry we are about to delete is not a leaf so if we do not
    ** do something we will leave a hole on an internal page.
................................................................................
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    rc = balance(pPage, 0);
  }
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }

  return rc;
}

/*
** Create a new BTree table.  Write into *piTable the page
** number for the root page of the new table.
**
................................................................................
*/
static int btreeCreateTable(Btree *p, int *piTable, int flags){
  BtShared *pBt = p->pBt;
  MemPage *pRoot;
  Pgno pgnoRoot;
  int rc;


  assert( sqlite3BtreeHoldsMutex(p) );
  if( pBt->inTransaction!=TRANS_WRITE ){
    /* Must start a transaction first */
    rc = pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
    return rc;
  }
  assert( !pBt->readOnly );

................................................................................
  int freePageFlag      /* Deallocate page if true */
){
  MemPage *pPage = 0;
  int rc;
  unsigned char *pCell;
  int i;

  assert( sqlite3_mutex_held(pBt->mutex) );
  if( pgno>sqlite3PagerPagecount(pBt->pPager) ){
    return SQLITE_CORRUPT_BKPT;
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
................................................................................
** meta[3] is updated by this procedure.
*/
static int btreeDropTable(Btree *p, int iTable, int *piMoved){
  int rc;
  MemPage *pPage = 0;
  BtShared *pBt = p->pBt;

  assert( sqlite3BtreeHoldsMutex(p) );
  if( p->inTrans!=TRANS_WRITE ){
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }

  /* It is illegal to drop a table if any cursors are open on the
  ** database. This is because in auto-vacuum mode the backend may
  ** need to move another root-page to fill a gap left by the deleted
................................................................................
** is currently pointing to.
*/
int sqlite3BtreeFlags(BtCursor *pCur){
  /* TODO: What about CURSOR_REQUIRESEEK state? Probably need to call
  ** restoreOrClearCursorPosition() here.
  */
  MemPage *pPage = pCur->pPage;
  assert( cursorHoldsMutex(pCur) );
  assert( pPage->pBt==pCur->pBt );
  return pPage ? pPage->aData[pPage->hdrOffset] : 0;
}


/*
** Return the pager associated with a BTree.  This routine is used for
................................................................................
** Return the full pathname of the underlying database file.
**
** The pager filename is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetFilename(Btree *p){
  assert( p->pBt->pPager!=0 );
  /* assert( sqlite3BtreeHoldsMutex(p) ); */
  return sqlite3PagerFilename(p->pBt->pPager);
}

/*
** Return the pathname of the directory that contains the database file.
**
** The pager directory name is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetDirname(Btree *p){
  assert( p->pBt->pPager!=0 );
  assert( sqlite3BtreeHoldsMutex(p) );
  return sqlite3PagerDirname(p->pBt->pPager);
}

/*
** Return the pathname of the journal file for this database. The return
** value of this routine is the same regardless of whether the journal file
** has been created or not.
**
** The pager journal filename is invariant as long as the pager is
** open so it is safe to access without the BtShared mutex.
*/
const char *sqlite3BtreeGetJournalname(Btree *p){
  assert( p->pBt->pPager!=0 );
  assert( sqlite3BtreeHoldsMutex(p) );
  return sqlite3PagerJournalname(p->pBt->pPager);
}

#ifndef SQLITE_OMIT_VACUUM
/*
** Copy the complete content of pBtFrom into pBtTo.  A transaction
** must be active for both files.
................................................................................

#endif /* SQLITE_OMIT_VACUUM */

/*
** Return non-zero if a transaction is active.
*/
int sqlite3BtreeIsInTrans(Btree *p){
  assert( p==0 || sqlite3_mutex_held(p->pSqlite->mutex) );
  return (p && (p->inTrans==TRANS_WRITE));
}

/*
** Return non-zero if a statement transaction is active.
*/
int sqlite3BtreeIsInStmt(Btree *p){
  assert( sqlite3BtreeHoldsMutex(p) );

  return (p->pBt && p->pBt->inStmt);
}

/*
** Return non-zero if a read (or write) transaction is active.
*/
int sqlite3BtreeIsInReadTrans(Btree *p){
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  return (p && (p->inTrans!=TRANS_NONE));
}

/*
** This function returns a pointer to a blob of memory associated with
** a single shared-btree. The memory is used by client code for it's own
** purposes (for example, to store a high-level schema associated with 
................................................................................

/*
** Return true if another user of the same shared btree as the argument
** handle holds an exclusive lock on the sqlite_master table.
*/
int sqlite3BtreeSchemaLocked(Btree *p){
  int rc;
  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
  sqlite3BtreeEnter(p);
  rc = (queryTableLock(p, MASTER_ROOT, READ_LOCK)!=SQLITE_OK);
  sqlite3BtreeLeave(p);
  return rc;
}


................................................................................
** Argument pCsr must be a cursor opened for writing on an 
** INTKEY table currently pointing at a valid table entry. 
** This function modifies the data stored as part of that entry.
** Only the data content may only be modified, it is not possible
** to change the length of the data stored.
*/
int sqlite3BtreePutData(BtCursor *pCsr, u32 offset, u32 amt, void *z){
  assert( cursorHoldsMutex(pCsr) );
  assert( sqlite3_mutex_held(pCsr->pBtree->pSqlite->mutex) );
  assert(pCsr->isIncrblobHandle);
  if( pCsr->eState==CURSOR_REQUIRESEEK ){
    return SQLITE_ABORT;
  }

  /* Check some preconditions: 
  **   (a) the cursor is open for writing,
................................................................................
**
** This function sets a flag only. The actual page location cache
** (stored in BtCursor.aOverflow[]) is allocated and used by function
** accessPayload() (the worker function for sqlite3BtreeData() and
** sqlite3BtreePutData()).
*/
void sqlite3BtreeCacheOverflow(BtCursor *pCur){
  assert( cursorHoldsMutex(pCur) );
  assert( sqlite3_mutex_held(pCur->pBtree->pSqlite->mutex) );
  assert(!pCur->isIncrblobHandle);
  assert(!pCur->aOverflow);
  pCur->isIncrblobHandle = 1;
}
#endif

Changes to src/btree.h.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
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
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.89 2007/08/29 00:33:07 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
** If we are not using shared cache, then there is no need to
** use mutexes to access the BtShared structures.  So make the
** Enter and Leave procedures no-ops.
*/
#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
  void sqlite3BtreeEnter(Btree*);
  void sqlite3BtreeLeave(Btree*);
# define sqlite3BtreeMutexHeld(X) sqlite3_mutex_held(X)
  void sqlite3BtreeEnterAll(sqlite3*);
  void sqlite3BtreeLeaveAll(sqlite3*);

  void sqlite3BtreeMutexArrayEnter(BtreeMutexArray*);
  void sqlite3BtreeMutexArrayLeave(BtreeMutexArray*);
  void sqlite3BtreeMutexArrayInsert(BtreeMutexArray*, Btree*);
#else
# define sqlite3BtreeEnter(X)
# define sqlite3BtreeLeave(X)
# define sqlite3BtreeMutexHeld(X) 1
# define sqlite3BtreeEnterAll(X)
# define sqlite3BtreeLeaveAll(X)

# define sqlite3BtreeMutexArrayEnter(X)
# define sqlite3BtreeMutexArrayLeave(X)
# define sqlite3BtreeMutexArrayInsert(X,Y)
#endif



#endif /* _BTREE_H_ */







|







 







|


>






|


>




<



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
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
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.  See comments in the source code for a detailed description
** of what each interface routine does.
**
** @(#) $Id: btree.h,v 1.90 2007/08/29 04:00:58 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

/* TODO: This definition is just included so other modules compile. It
** needs to be revisited.
*/
................................................................................
** If we are not using shared cache, then there is no need to
** use mutexes to access the BtShared structures.  So make the
** Enter and Leave procedures no-ops.
*/
#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
  void sqlite3BtreeEnter(Btree*);
  void sqlite3BtreeLeave(Btree*);
  int sqlite3BtreeHoldsMutex(Btree*);
  void sqlite3BtreeEnterAll(sqlite3*);
  void sqlite3BtreeLeaveAll(sqlite3*);
  int sqlite3BtreeHoldsAllMutexes(sqlite3*);
  void sqlite3BtreeMutexArrayEnter(BtreeMutexArray*);
  void sqlite3BtreeMutexArrayLeave(BtreeMutexArray*);
  void sqlite3BtreeMutexArrayInsert(BtreeMutexArray*, Btree*);
#else
# define sqlite3BtreeEnter(X)
# define sqlite3BtreeLeave(X)
# define sqlite3BtreeHoldsMutex(X) 1
# define sqlite3BtreeEnterAll(X)
# define sqlite3BtreeLeaveAll(X)
# define sqlite3BtreeHoldsAllMutexes(X) 1
# define sqlite3BtreeMutexArrayEnter(X)
# define sqlite3BtreeMutexArrayLeave(X)
# define sqlite3BtreeMutexArrayInsert(X,Y)
#endif



#endif /* _BTREE_H_ */