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

Overview
Comment:Further progress on b-treee backend.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: c9549586972550291b00b4cb2dfc7cd7bb27ed07
User & Date: dan 2013-09-24 20:39:25.192
Context
2013-09-25
18:46
Further btree updates. check-in: 6548088566 user: dan tags: trunk
2013-09-24
20:39
Further progress on b-treee backend. check-in: c954958697 user: dan tags: trunk
2013-09-19
19:19
Further btree updates. check-in: 0b68007d89 user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to main.mk.
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
         random.o resolve.o rowset.o rtree.o select.o status.o \
         tokenize.o trigger.o \
         update.o util.o varint.o \
         vdbeapi.o vdbeaux.o vdbecodec.o vdbecursor.o \
         vdbemem.o vdbetrace.o \
         walker.o where.o utf.o

LIBOBJ += bt_unix.o bt_pager.o bt_main.o 

# All of the source code files.
#
SRC = \
  $(TOP)/src/alter.c \
  $(TOP)/src/analyze.c \
  $(TOP)/src/attach.c \







|







83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
         random.o resolve.o rowset.o rtree.o select.o status.o \
         tokenize.o trigger.o \
         update.o util.o varint.o \
         vdbeapi.o vdbeaux.o vdbecodec.o vdbecursor.o \
         vdbemem.o vdbetrace.o \
         walker.o where.o utf.o

LIBOBJ += bt_unix.o bt_pager.o bt_main.o bt_varint.o kvbt.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/alter.c \
  $(TOP)/src/analyze.c \
  $(TOP)/src/attach.c \
Changes to src/bt.h.
100
101
102
103
104
105
106



107
108
109
110
111
112
113
**   SQLITE4_OK:
**   SQLITE4_NOTFOUND:
**   SQLITE4_INEXACT:
**   other:
*/
int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek);




int sqlite4BtCsrFirst(bt_cursor *pCsr);
int sqlite4BtCsrLast(bt_cursor *pCsr);

int sqlite4BtCsrNext(bt_cursor *pCsr);
int sqlite4BtCsrPrev(bt_cursor *pCsr);

int sqlite4BtCsrValid(bt_cursor *pCsr);







>
>
>







100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
**   SQLITE4_OK:
**   SQLITE4_NOTFOUND:
**   SQLITE4_INEXACT:
**   other:
*/
int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek);

/*
** TODO: Are these actually even required for SQLite4 KV stores?
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr);
int sqlite4BtCsrLast(bt_cursor *pCsr);

int sqlite4BtCsrNext(bt_cursor *pCsr);
int sqlite4BtCsrPrev(bt_cursor *pCsr);

int sqlite4BtCsrValid(bt_cursor *pCsr);
Changes to src/btInt.h.
11
12
13
14
15
16
17

18

19
20
21
22
23
24
25
*************************************************************************
**
*/

#include "bt.h"

typedef sqlite4_int64 i64;

typedef unsigned int u32;

typedef unsigned char u8;

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;
typedef struct BtPager BtPager;







>

>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
*************************************************************************
**
*/

#include "bt.h"

typedef sqlite4_int64 i64;
typedef sqlite4_uint64 u64;
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;
typedef struct BtPager BtPager;
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int sqlite4BtPagerRevert(BtPager*, int iLevel);
int sqlite4BtPagerRollback(BtPager*, int iLevel);
int sqlite4BtPagerTransactionLevel(BtPager*);

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager*, int *pnByte);

/* 
** Query for the root page number. Requires an open read transaction.
*/
int sqlite4BtPagerRootpgno(BtPager*, u32 *piRoot);

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
int sqlite4BtPageWrite(BtPage*);
int sqlite4BtPageTrim(BtPage*);







|




|







47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
int sqlite4BtPagerRevert(BtPager*, int iLevel);
int sqlite4BtPagerRollback(BtPager*, int iLevel);
int sqlite4BtPagerTransactionLevel(BtPager*);

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager*);

/* 
** Query for the root page number. Requires an open read transaction.
*/
u32 sqlite4BtPagerRootpgno(BtPager*);

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
int sqlite4BtPageWrite(BtPage*);
int sqlite4BtPageTrim(BtPage*);
126
127
128
129
130
131
132














133





134
/* Find the default VFS */
bt_env *sqlite4BtEnvDefault(void);

/*
** End of file system interface.
*************************************************************************/





























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

>
>
>
>
>

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
/* Find the default VFS */
bt_env *sqlite4BtEnvDefault(void);

/*
** End of file system interface.
*************************************************************************/

/*************************************************************************
** Interface to bt_varint.c functionality.
**
** All this is just copied from SQLite4 proper. It is a bit ridiculous.
*/
int sqlite4BtVarintPut32(u8 *, int);
int sqlite4BtVarintGet32(u8 *, int *);
int sqlite4BtVarintPut64(u8 *aData, i64 iVal);
int sqlite4BtVarintGet64(const u8 *aData, i64 *piVal);
int sqlite4BtVarintLen32(int);
int sqlite4BtVarintSize(u8 c);
/*
** End of bt_varint.c interface.
*************************************************************************/

#ifdef NDEBUG
# define btErrorBkpt(x) x
#else
int btErrorBkpt(int rc);
#endif

Changes to src/bt_main.c.
9
10
11
12
13
14
15










16
17
18
19
20
21
22
23
24
25
26
27
28
























29
30
31
32
33
34
35
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

#include "btInt.h"











struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
};

struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int iCell;                      /* Current cell in apPage[nPg] */
  BtPage *apPage[32];             /* All pages from root to current leaf */
};

























/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  bt_db *db = 0;                  /* New database object */
  BtPager *pPager = 0;            /* Pager object for this database */







>
>
>
>
>
>
>
>
>
>










|
|

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







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
*/

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

#define BT_MAX_DEPTH 32           /* Maximum possible depth of tree */

/*
** Values that make up the single byte flags field at the start of
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
};

struct bt_cursor {
  bt_db *pDb;                     /* Database that owns this cursor */

  int nPg;                        /* Number of valid entries in apPage[] */
  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
};

#ifndef btErrorBkpt
int btErrorBkpt(int rc){
  static int error_cnt = 0;
  error_cnt++;
  return rc;
}
#endif

/*
** Interpret the first 4 bytes of the buffer indicated by the first parameter
** as a 32-bit unsigned big-endian integer.
*/
static u32 btGetU32(const u8 *a){
  return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]);
}
static u16 btGetU16(const u8 *a){
  return ((u32)a[0] << 8) + (u32)a[1];
}

static void btPutU16(u8 *a, u16 i){
  a[0] = (u8)((i>>8) & 0xFF);
  a[1] = (u8)((i>>0) & 0xFF);
}

/*
** Allocate a new database handle.
*/
int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
  bt_db *db = 0;                  /* New database object */
  BtPager *pPager = 0;            /* Pager object for this database */
96
97
98
99
100
101
102





103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138














139























































































































































































140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160



161

162
163
164
165

166
167
168
169

170
171
172
173





174
175
176
177
178
179
180
181
182
183

184
185
186
































































187





















188
189
190
191

192
193
194
195
196
197
198
199
200
201
202








  rc = sqlite4BtPagerRollback(db->pPager, iLevel);
  return rc;
}

int sqlite4BtTransactionLevel(bt_db *db){
  return sqlite4BtPagerTransactionLevel(db->pPager);
}






int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc;                         /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */
  bt_cursor *pCsr;                /* New cursor object */

  nByte = sizeof(bt_cursor) + nExtra;
  pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = SQLITE4_NOMEM;
  }else{
    memset(pCsr, 0, nByte);
    pCsr->pDb = db;
  }

  return rc;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}

int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek){
  return SQLITE4_OK;
}

static void btCsrReset(bt_cursor *pCsr){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
  }
  pCsr->nPg = 0;














  pCsr->iCell = 0;























































































































































































}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){
  /* Reset the cursor */
  btCsrReset(pCsr);

  /* Load the root page into pCsr->apPage[0] */

  return SQLITE4_OK;
}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  return SQLITE4_OK;
}




int sqlite4BtCsrNext(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtCsrPrev(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtCsrValid(bt_cursor *pCsr){

  return 0;
}

int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){





  return SQLITE4_OK;
}

int sqlite4BtCsrData(
  bt_cursor *pCsr,                /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){

  return SQLITE4_OK;
}

































































int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){





















  return SQLITE4_OK;
}

int sqlite4BtDelete(bt_cursor *pCsr){

  return SQLITE4_OK;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}
















>
>
>
>
>







|

|

<
|













<
<
<
<






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






<
<
|
<
<
<






|


>
>
>

>




>




>




>
>
>
>
>










>



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

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



>











>
>
>
>
>
>
>
>
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

153
154
155
156
157
158
159
160
161
162
163
164
165
166




167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376


377



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
  rc = sqlite4BtPagerRollback(db->pPager, iLevel);
  return rc;
}

int sqlite4BtTransactionLevel(bt_db *db){
  return sqlite4BtPagerTransactionLevel(db->pPager);
}

static void btCsrSetup(bt_db *db, bt_cursor *pCsr){
  memset(pCsr, 0, sizeof(bt_cursor));
  pCsr->pDb = db;
}

int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
  int rc;                         /* Return Code */
  int nByte;                      /* Total bytes of space to allocate */
  bt_cursor *pCsr;                /* New cursor object */

  nByte = sizeof(bt_cursor) + nExtra;
  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
  if( pCsr==0 ){
    rc = btErrorBkpt(SQLITE4_NOMEM);
  }else{

    btCsrSetup(db, pCsr);
  }

  return rc;
}

int sqlite4BtCsrClose(bt_cursor *pCsr){
  return SQLITE4_OK;
}

void *sqlite4BtCsrExtra(bt_cursor *pCsr){
  return (void*)&pCsr[1];
}





static void btCsrReset(bt_cursor *pCsr){
  int i;
  for(i=0; i<pCsr->nPg; i++){
    sqlite4BtPageRelease(pCsr->apPage[i]);
  }
  pCsr->nPg = 0;
}

/*
** Set pCsr->apPage[pCsr->nPg] to a reference to database page pgno.
*/
static int btCsrDescend(bt_cursor *pCsr, u32 pgno){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
    if( pCsr->nPg==0 && rc==SQLITE4_OK ){
    }
    if( rc==SQLITE4_OK ){
      pCsr->nPg++;
    }
  }
  return rc;
}

static int btCellCount(const u8 *aData, int nData){
  return (int)btGetU16(&aData[nData-2]);
}

static int btFreeOffset(const u8 *aData, int nData){
  return (int)btGetU16(&aData[nData-4]);
}

static u8 btFlags(const u8 *aData, int nData){
  return aData[0];
}

static u8 *btCellFind(u8 *aData, int nData, int iCell){
  int iOff = btGetU16(&aData[nData - 4 - iCell*2 - 2]);
  return &aData[iOff];
}

/*
** Return a pointer to the big-endian u16 field that contains the 
** pointer to cell iCell.
*/
static u8* btCellPtrFind(u8 *aData, int nData, int iCell){
  return &aData[nData - 4 - iCell*2 - 2];
}


/*
** This function seeks the cursor as required for either sqlite4BtCsrFirst()
** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
*/
static int btCsrEnd(bt_cursor *pCsr, int bLast){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  int rc;                         /* Return Code */
  u32 pgno;                       /* Page number for next page to load */

  /* Reset the cursor */
  btCsrReset(pCsr);

  /* Figure out the root page number */
  assert( pCsr->nPg==0 );
  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);

  while( rc==SQLITE4_OK ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nByte;
      u8 *pCell;
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      /* If the cursor has descended to a leaf break out of the loop. */
      pCsr->aiCell[pCsr->nPg-1] = (bLast ? btCellCount(aData, pgsz) : 0);
      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
      
      /* Otherwise, set pgno to the left or rightmost child of the page
      ** just loaded, depending on whether the cursor is seeking to the
      ** start or end of the tree.  */
      if( bLast==0 ){
        pCell = btCellFind(aData, pgsz, 0);
        pCell += sqlite4BtVarintGet32(pCell, &nByte);
        pCell += nByte;
        sqlite4BtVarintGet32(pCell, (int *)&pgno);
      }else{
        pgno = btGetU32(&aData[1]);
      }
    }
  }
  return rc;
}

/*
** This function compares the key passed via parameters pK and nK to the
** key stored as part of cell iCell on the database page stored in buffer
** aData (size nData bytes).
**
** If the cell key is C, and the user key K, then this function sets:
**
**     *piRes = (C - K).
**
** In other workds, *piRes is +ve, zero or -ve if C is respectively larger, 
** equal to or smaller than K.
*/
static int btCellKeyCompare(
  bt_cursor *pCsr,                /* Cursor handle */
  const u8 *aData, int nData,     /* Page data (nData is the page size) */
  int iCell,                      /* Cell to compare key from */
  const u8 *pK, int nK,           /* Key to compare to cell key */
  int *piRes                      /* OUT: Result of comparison */
){
  int rc = SQLITE4_OK;
  u8 *pCell = btCellFind((u8*)aData, nData, iCell);
  int nCellKey;                   /* Number of bytes in cell key */
  int res;

  pCell += sqlite4BtVarintGet32(pCell, &nCellKey);
  if( nCellKey==0 ){
    /* Type (c) cell */
    assert( 0 );
  }else{
    int nCmp = ((nCellKey <= nK) ? nCellKey : nK);
    res = memcmp(pCell, pK, nCmp);
    if( res==0 ){
      res = nCellKey - nK;
    }
  }

  *piRes = res;
  return rc;
}

int sqlite4BtCsrSeek(
  bt_cursor *pCsr, 
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc = SQLITE4_OK;            /* Return Code */

  /* Reset the cursor */
  btCsrReset(pCsr);

  /* Figure out the root page number */
  assert( pCsr->nPg==0 );
  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);

  while( rc==SQLITE4_OK && pgno ){
    /* Load page number pgno into the b-tree */
    rc = btCsrDescend(pCsr, pgno);
    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int iHi;                    /* pK/nK is <= than cell iHi */
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */
      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);

      while( iHi>iLo ){
        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
        rc = btCellKeyCompare(pCsr, aData, pgsz, iTst, pK, nK, &res);
        if( rc!=SQLITE4_OK || res==0 ){
          /* Cell iTst is EQUAL to pK/nK */
          iHi = iLo = iTst;
        }else if( res<0 ){
          /* Cell iTst is SMALLER than pK/nK */
          iLo = iTst+1;
        }else{
          /* Cell iTst is LARGER than pK/nK */
          iHi = iTst;
        }
      }
      assert( rc!=SQLITE4_OK || iHi==iLo );
      pCsr->aiCell[pCsr->nPg-1] = iHi;

      if( aData[0] & BT_PGFLAGS_INTERNAL ){
        if( iHi==nCell ){
          pgno = btGetU32(&aData[1]);
        }else{
          u8 *pCell;
          int nByte;
          pCell = btCellFind(aData, pgsz, 0);
          pCell += sqlite4BtVarintGet32(pCell, &nByte);
          pCell += nByte;
          sqlite4BtVarintGet32(pCell, (int*)&pgno);
        }
      }else{
        pgno = 0;
        if( res!=0 ){
          rc = SQLITE4_INEXACT;
        }
      }
    }
  }

  return rc;
}

/*
** Position cursor pCsr to point to the smallest key in the database.
*/
int sqlite4BtCsrFirst(bt_cursor *pCsr){


  return btCsrEnd(pCsr, 0);



}

/*
** Position cursor pCsr to point to the largest key in the database.
*/
int sqlite4BtCsrLast(bt_cursor *pCsr){
  return btCsrEnd(pCsr, 1);
}

/*
** Advance to the next entry in the tree.
*/
int sqlite4BtCsrNext(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtCsrPrev(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtCsrValid(bt_cursor *pCsr){
  assert( 0 );
  return 0;
}

int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);

  return SQLITE4_OK;
}

int sqlite4BtCsrData(
  bt_cursor *pCsr,                /* Cursor handle */
  int iOffset,                    /* Offset of requested data */
  int nByte,                      /* Bytes requested (or -ve for all avail.) */
  const void **ppV,               /* OUT: Pointer to data buffer */
  int *pnV                        /* OUT: Size of data buffer in bytes */
){
  assert( 0 );
  return SQLITE4_OK;
}

static int btInsertIntoLeaf(
  bt_cursor *pCsr, 
  const void *pK, int nK, 
  const void *pV, int nV
){
  int rc = SQLITE4_OK;
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;                      /* Page buffer */
  int nCell;                      /* Number of cells on this page already */
  int nFree;                      /* Free space on this page in bytes */
  int nReq;                       /* Space required for type (a) cell */
  int iCell;                      /* Position to insert new key */
  int iWrite;                     /* Byte offset at which to write new cell */
  BtPage *pLeaf;

  nReq = sqlite4BtVarintLen32(nK) + nK + sqlite4BtVarintLen32(nV) + nV + 2;

  iCell = pCsr->aiCell[pCsr->nPg-1];
  assert( pCsr->nPg>0 );
  pLeaf = pCsr->apPage[pCsr->nPg-1];
  aData = (u8*)sqlite4BtPageData(pLeaf);

  nCell = btCellCount(aData, pgsz);
  assert( iCell<=btCellCount(aData, pgsz) );

  if( nCell==0 ){
    iWrite = 1;                   /* Right after "flags" byte */
    nFree = pgsz - 1 - 4;         /* Page is free aside from header & footer */
  }else{
    iWrite = btFreeOffset(aData, pgsz);
    nFree = pgsz - btFreeOffset(aData, pgsz) - (2+nCell) * 2;
  }
  if( nFree>=nReq ){
    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Increase cell count */
      btPutU16(&aData[pgsz-2], nCell+1);

      /* Update the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = &aData[pgsz-4-iCell*2];
        memmove(aFrom, &aFrom[-2], (nCell-iCell) * 2);
      }
      btPutU16(btCellPtrFind(aData, pgsz, iCell), iWrite);
      
      /* Write the cell itself */
      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nK);
      iWrite += nK;
      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nV);
      iWrite += nV;
      btPutU16(&aData[pgsz-4], iWrite);
    }
  }else{
    assert( 0 );
  }

  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.
*/
int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
  int rc = SQLITE4_OK;
  bt_cursor csr;

  btCsrSetup(db, &csr);
  rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
  if( rc==SQLITE4_OK ){
    /* The cursor currently points to an entry with key pK/nK. This call
    ** should therefore replace that entry. So delete it and then re-seek
    ** the cursor.  */
    rc = sqlite4BtDelete(&csr);
    if( rc==SQLITE4_OK ){
      rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
    }
  }
  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);

  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
    /* Insert the new KV pair into the current leaf. */
    rc = btInsertIntoLeaf(&csr, pK, nK, pV, nV);
  }

  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  assert( 0 );
  return SQLITE4_OK;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
  return sqlite4BtPagerSetCookie(db->pPager, iVal);
}

int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
  return sqlite4BtPagerGetCookie(db->pPager, piVal);
}

#ifndef NDEBUG
static void printPage(u8 *aData, int nData){
  printf("nCell=%d\n", (int)btCellCount(aData, nData));
  printf("iFree=%d\n", (int)btFreeOffset(aData, nData));
  printf("flags=%d\n", (int)btFlags(aData, nData));
}
#endif

Changes to src/bt_pager.c.
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
  if( p->hash.nEntry>=p->hash.nHash/2 ){
    int i;
    int nNew = (p->hash.nHash ? p->hash.nHash*2 : 256);
    BtPage **aNew;
    BtPage **aOld = p->hash.aHash;

    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return SQLITE4_NOMEM;
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pPg->pgno);
        pShift->pNextHash = aNew[h];







|







100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
  if( p->hash.nEntry>=p->hash.nHash/2 ){
    int i;
    int nNew = (p->hash.nHash ? p->hash.nHash*2 : 256);
    BtPage **aNew;
    BtPage **aOld = p->hash.aHash;

    aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
    if( aNew==0 ) return btErrorBkpt(SQLITE4_NOMEM);
    memset(aNew, 0, nNew*sizeof(BtPage*));
    for(i=0; i<p->hash.nHash; i++){
      while( aOld[i] ){
        BtPage *pShift = aOld[i];
        aOld[i] = pShift->pNextHash;
        h = hashkey(nNew, pPg->pgno);
        pShift->pNextHash = aNew[h];
142
143
144
145
146
147
148


149
150
151

152
153
154
155
156
157
158
}

/*
** Search the hash table for a page with page number pgno. If found, return
** a pointer to the BtPage object. Otherwise, return NULL.
*/
static BtPage *btHashSearch(BtPager *p, u32 pgno){


  int h = hashkey(p->hash.nHash, pgno);
  BtPage *pRet;
  for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);

  return pRet;
}

/*
** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/







>
>
|
<
|
>







142
143
144
145
146
147
148
149
150
151

152
153
154
155
156
157
158
159
160
}

/*
** Search the hash table for a page with page number pgno. If found, return
** a pointer to the BtPage object. Otherwise, return NULL.
*/
static BtPage *btHashSearch(BtPager *p, u32 pgno){
  BtPage *pRet = 0;
  if( p->hash.nHash ){
    int h = hashkey(p->hash.nHash, pgno);

    for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);
  }
  return pRet;
}

/*
** Remove all entries from the hash-table. And free any allocations made
** by earlier calls to btHashAdd().
*/
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
*/
int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
  BtPager *p;
  int nByte;

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return SQLITE4_NOMEM; 
  memset(p, 0, nByte);

  p->pEnv = pEnv;
  p->pVfs = sqlite4BtEnvDefault();
  *pp = p;
  return SQLITE4_OK;
}







|







171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
*/
int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
  BtPager *p;
  int nByte;

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return btErrorBkpt(SQLITE4_NOMEM); 
  memset(p, 0, nByte);

  p->pEnv = pEnv;
  p->pVfs = sqlite4BtEnvDefault();
  *pp = p;
  return SQLITE4_OK;
}
243
244
245
246
247
248
249





250
251
252
253
254
255
256
  if( rc==SQLITE4_OK && nByte>0 ){
    rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
  }else{
    memset(&p->dbhdr, 0, sizeof(p->dbhdr));
    p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
  }






  return rc;
}

/*
** Commit the current write transaction to disk.
*/
static int btCommitTransaction(BtPager *p){







>
>
>
>
>







245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
  if( rc==SQLITE4_OK && nByte>0 ){
    rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
  }else{
    memset(&p->dbhdr, 0, sizeof(p->dbhdr));
    p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
  }

  if( rc==SQLITE4_OK ){
    /* If the read transaction was successfully opened, the transaction 
    ** level is now 1.  */
    p->iTransactionLevel = 1;
  }
  return rc;
}

/*
** Commit the current write transaction to disk.
*/
static int btCommitTransaction(BtPager *p){
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
    memset(pRet, 0, sizeof(BtPage));
    pRet->aData = aData;
    pRet->pPager = p;
    rc = SQLITE4_OK;
  }else{
    sqlite4_free(p->pEnv, pRet);
    sqlite4_free(p->pEnv, aData);
    rc = SQLITE4_NOMEM;
    pRet = 0;
  }

  *ppPg = pRet;
  return rc;
}








|







302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
    memset(pRet, 0, sizeof(BtPage));
    pRet->aData = aData;
    pRet->pPager = p;
    rc = SQLITE4_OK;
  }else{
    sqlite4_free(p->pEnv, pRet);
    sqlite4_free(p->pEnv, aData);
    rc = btErrorBkpt(SQLITE4_NOMEM);
    pRet = 0;
  }

  *ppPg = pRet;
  return rc;
}

379
380
381
382
383
384
385
386
387
388
389
390

391

392
393
394
395
396
397
398
    }
    p->iTransactionLevel = iLevel;
  }
  return rc;
}

int sqlite4BtPagerRollback(BtPager *p, int iLevel){
  int rc;

  assert( p->pFd );
  if( p->iTransactionLevel>=iLevel ){
    assert( iLevel<=1 );          /* TODO: Fix this! */

    rc = btRollbackTransaction(p);

    p->iTransactionLevel = iLevel;
  }

  return rc;
}

int sqlite4BtPagerRevert(BtPager *p, int iLevel){







|




>
|
>







386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
    }
    p->iTransactionLevel = iLevel;
  }
  return rc;
}

int sqlite4BtPagerRollback(BtPager *p, int iLevel){
  int rc = SQLITE4_OK;

  assert( p->pFd );
  if( p->iTransactionLevel>=iLevel ){
    assert( iLevel<=1 );          /* TODO: Fix this! */
    if( p->iTransactionLevel>=2 ){
      rc = btRollbackTransaction(p);
    }
    p->iTransactionLevel = iLevel;
  }

  return rc;
}

int sqlite4BtPagerRevert(BtPager *p, int iLevel){
413
414
415
416
417
418
419
420
421
422
423
424

425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
int sqlite4BtPagerTransactionLevel(BtPager *p){
  return p->iTransactionLevel;
}

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager *p, int *pnByte){
  assert( p->iTransactionLevel>=1 && p->pFd );
  *pnByte = (int)p->dbhdr.pgsz;
  return SQLITE4_OK;
}


/* 
** Query for the root page number. Requires an open read transaction.
*/
int sqlite4BtPagerRootpgno(BtPager *p, u32 *piRoot){
  assert( p->iTransactionLevel>=1 && p->pFd );
  *piRoot = 2;
  return SQLITE4_OK;
}

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */







|

|
<

>




|

<
|







422
423
424
425
426
427
428
429
430
431

432
433
434
435
436
437
438
439

440
441
442
443
444
445
446
447
int sqlite4BtPagerTransactionLevel(BtPager *p){
  return p->iTransactionLevel;
}

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );
  return (int)p->dbhdr.pgsz;

}


/* 
** Query for the root page number. Requires an open read transaction.
*/
u32 sqlite4BtPagerRootpgno(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->pFd );

  return 2;
}

/*
** Read, write and trim existing database pages.
*/
int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
  int rc = SQLITE4_OK;            /* Return code */
Changes to src/bt_unix.c.
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "btInt.h"

/* There is no fdatasync() call on Android */
#ifdef __ANDROID__
# define fdatasync(x) fsync(x)
#endif

/*
** The malloc/free functions used for allocations made within this file.
** There are relatively few such allocations.
*/
static void *btMalloc(size_t n){ 
  return malloc(n); 
}
static void btFree(void *p){ 
  free(p); 
}
static void *btRealloc(void *p, size_t n){ 
  return realloc(p, n); 
}
static void *btReallocOrFree(void *p, size_t n){
  void *pNew = realloc(p, n); 
  if( pNew==0 ) free(p);
  return pNew;
}

#ifdef NDEBUG
# define btErrorBkpt(x) x
#else
static int btErrorBkpt(int rc){
  return rc;
}
#endif

/*
** An open file is an instance of the following object
*/
typedef struct PosixFile PosixFile;
struct PosixFile {
  sqlite4_env *pSqlEnv;
  bt_env *pEnv;                   /* The run-time environment */
  const char *zName;              /* Full path to file */
  int fd;                         /* The open file descriptor */
  int shmfd;                      /* Shared memory file-descriptor */
  int nShm;                       /* Number of entries in array apShm[] */
  void **apShm;                   /* Array of 32K shared memory segments */
};

static char *posixShmFile(PosixFile *p){
  char *zShm;
  int nName = strlen(p->zName);
  zShm = (char*)btMalloc(nName+4+1);
  if( zShm ){
    memcpy(zShm, p->zName, nName);
    memcpy(&zShm[nName], "-shm", 5);
  }
  return zShm;
}








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

















|







39
40
41
42
43
44
45



























46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include "btInt.h"

/* There is no fdatasync() call on Android */
#ifdef __ANDROID__
# define fdatasync(x) fsync(x)
#endif




























/*
** An open file is an instance of the following object
*/
typedef struct PosixFile PosixFile;
struct PosixFile {
  sqlite4_env *pSqlEnv;
  bt_env *pEnv;                   /* The run-time environment */
  const char *zName;              /* Full path to file */
  int fd;                         /* The open file descriptor */
  int shmfd;                      /* Shared memory file-descriptor */
  int nShm;                       /* Number of entries in array apShm[] */
  void **apShm;                   /* Array of 32K shared memory segments */
};

static char *posixShmFile(PosixFile *p){
  char *zShm;
  int nName = strlen(p->zName);
  zShm = (char*)sqlite4_malloc(p->pSqlEnv, nName+4+1);
  if( zShm ){
    memcpy(zShm, p->zName, nName);
    memcpy(&zShm[nName], "-shm", 5);
  }
  return zShm;
}

356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
    struct stat sStat;

    /* If the shared-memory file has not been opened, open it now. */
    if( p->shmfd<=0 ){
      char *zShm = posixShmFile(p);
      if( !zShm ) return btErrorBkpt(SQLITE4_NOMEM);
      p->shmfd = open(zShm, O_RDWR|O_CREAT, 0644);
      btFree(zShm);
      if( p->shmfd<0 ){ 
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    /* If the shared-memory file is not large enough to contain the 
    ** requested chunk, cause it to grow.  */
    if( fstat(p->shmfd, &sStat) ){
      return btErrorBkpt(SQLITE4_IOERR);
    }
    if( sStat.st_size<nReq ){
      if( ftruncate(p->shmfd, nReq) ){
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    apNew = (void**)btRealloc(p->apShm, sizeof(void *) * nNew);
    if( !apNew ) return btErrorBkpt(SQLITE4_NOMEM);
    for(i=p->nShm; i<nNew; i++){
      apNew[i] = 0;
    }
    p->apShm = apNew;
    p->nShm = nNew;
  }







|
















|







329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
    struct stat sStat;

    /* If the shared-memory file has not been opened, open it now. */
    if( p->shmfd<=0 ){
      char *zShm = posixShmFile(p);
      if( !zShm ) return btErrorBkpt(SQLITE4_NOMEM);
      p->shmfd = open(zShm, O_RDWR|O_CREAT, 0644);
      sqlite4_free(p->pSqlEnv, zShm);
      if( p->shmfd<0 ){ 
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    /* If the shared-memory file is not large enough to contain the 
    ** requested chunk, cause it to grow.  */
    if( fstat(p->shmfd, &sStat) ){
      return btErrorBkpt(SQLITE4_IOERR);
    }
    if( sStat.st_size<nReq ){
      if( ftruncate(p->shmfd, nReq) ){
        return btErrorBkpt(SQLITE4_IOERR);
      }
    }

    apNew = (void**)sqlite4_realloc(p->pSqlEnv, p->apShm, sizeof(void*) * nNew);
    if( !apNew ) return btErrorBkpt(SQLITE4_NOMEM);
    for(i=p->nShm; i<nNew; i++){
      apNew[i] = 0;
    }
    p->apShm = apNew;
    p->nShm = nNew;
  }
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
      }
    }
    close(p->shmfd);
    p->shmfd = 0;
    if( bDelete ){
      char *zShm = posixShmFile(p);
      if( zShm ) unlink(zShm);
      btFree(zShm);
    }
  }
  return SQLITE4_OK;
}


static int btPosixOsClose(bt_file *pFile){
   PosixFile *p = (PosixFile *)pFile;
   btPosixOsShmUnmap(pFile, 0);
   close(p->fd);
   btFree(p->apShm);
   btFree(p);
   return SQLITE4_OK;
}

bt_env *sqlite4BtEnvDefault(void){
  static bt_env posix_env = {
    0,                            /* pVfsCtx */
    btPosixOsFullpath,            /* xFullpath */







|










|
|







384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
      }
    }
    close(p->shmfd);
    p->shmfd = 0;
    if( bDelete ){
      char *zShm = posixShmFile(p);
      if( zShm ) unlink(zShm);
      sqlite4_free(p->pSqlEnv, zShm);
    }
  }
  return SQLITE4_OK;
}


static int btPosixOsClose(bt_file *pFile){
   PosixFile *p = (PosixFile *)pFile;
   btPosixOsShmUnmap(pFile, 0);
   close(p->fd);
   sqlite4_free(p->pSqlEnv, p->apShm);
   sqlite4_free(p->pSqlEnv, p);
   return SQLITE4_OK;
}

bt_env *sqlite4BtEnvDefault(void){
  static bt_env posix_env = {
    0,                            /* pVfsCtx */
    btPosixOsFullpath,            /* xFullpath */
Changes to src/env.c.
20
21
22
23
24
25
26






27
28
29
30
31
32
33
34
35
*/
static KVFactory memFactory = {
   0,
   "temp",
   sqlite4KVStoreOpenMem,
   1
};






KVFactory sqlite4BuiltinFactory = {
   &memFactory,
   "main",
   sqlite4KVStoreOpenLsm,
   1
};

/*
** The following singleton contains the global configuration for







>
>
>
>
>
>

|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
*/
static KVFactory memFactory = {
   0,
   "temp",
   sqlite4KVStoreOpenMem,
   1
};
static KVFactory btFactory = {
   &memFactory,
   "bt",
   sqlite4OpenBtree,
   1
};
KVFactory sqlite4BuiltinFactory = {
   &btFactory,
   "main",
   sqlite4KVStoreOpenLsm,
   1
};

/*
** The following singleton contains the global configuration for
Changes to src/kv.c.
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
  const char *zStorageName;
  KVFactory *pMkr;
  sqlite4_kvfactory xFactory;

  if( (flags & SQLITE4_KVOPEN_TEMPORARY)!=0 || zUri==0 || zUri[0]==0 ){
    zStorageName = "temp";
  }else{
    zStorageName = sqlite4_uri_parameter(zName, "kv");
    if( zStorageName==0 ){
      if( memcmp(":memory:", zUri, 8)==0 ){
        zStorageName = "temp";
      }else{
        zStorageName = "main";
      }
    }







|







91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
  const char *zStorageName;
  KVFactory *pMkr;
  sqlite4_kvfactory xFactory;

  if( (flags & SQLITE4_KVOPEN_TEMPORARY)!=0 || zUri==0 || zUri[0]==0 ){
    zStorageName = "temp";
  }else{
    zStorageName = sqlite4_uri_parameter(zUri, "kv");
    if( zStorageName==0 ){
      if( memcmp(":memory:", zUri, 8)==0 ){
        zStorageName = "temp";
      }else{
        zStorageName = "main";
      }
    }
Changes to src/kv.h.
154
155
156
157
158
159
160

161
162
163
164
165
166
167
/* Typedefs of datatypes */
typedef struct sqlite4_kvstore KVStore;
typedef struct sqlite4_kv_methods KVStoreMethods;
typedef struct sqlite4_kvcursor KVCursor;
typedef unsigned char KVByteArray;
typedef sqlite4_kvsize KVSize;


int sqlite4KVStoreOpenMem(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenLsm(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpen(
  sqlite4*,
  const char *zLabel, 
  const char *zUri,
  KVStore**,







>







154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/* Typedefs of datatypes */
typedef struct sqlite4_kvstore KVStore;
typedef struct sqlite4_kv_methods KVStoreMethods;
typedef struct sqlite4_kvcursor KVCursor;
typedef unsigned char KVByteArray;
typedef sqlite4_kvsize KVSize;

int sqlite4OpenBtree(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenMem(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpenLsm(sqlite4_env*, KVStore**, const char *, unsigned);
int sqlite4KVStoreOpen(
  sqlite4*,
  const char *zLabel, 
  const char *zUri,
  KVStore**,
Changes to src/kvbt.c.
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
*/
static int btSeek(
  KVCursor *pKVCursor, 
  const KVByteArray *aKey,
  KVSize nKey,
  int dir
){
  int rc;
  KVBtCsr *pCsr = (KVBtCsr *)pKVCursor;

  assert( dir==0 || dir==1 || dir==-1 || dir==-2 );
  assert( BT_SEEK_EQ==0 && BT_SEEK_GE==1 && BT_SEEK_LE==-1 );
  assert( BT_SEEK_LEFAST==-2 );

  return sqlite4BtCsrSeek(pCsr->pCsr, (void *)aKey, nKey, dir);
}

/*
** Delete the entry that the cursor is pointing to.
**
** Though the entry is "deleted", it still continues to exist as a
** phantom.  Subsequent xNext or xPrev calls will work, as will
** calls to xKey and xData, thought the result from xKey and xData
** are undefined.
*/
static int btDelete(KVCursor *pKVCursor){
  KVBtCsr *pBtcsr = (KVBtCsr *)pKVCursor;
  return sqlite4BtDelete(pBtcsr);
}

/*
** Return the key of the node the cursor is pointing to.
*/
static int btKey(
  KVCursor *pKVCursor,         /* The cursor whose key is desired */







<



















|







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
*/
static int btSeek(
  KVCursor *pKVCursor, 
  const KVByteArray *aKey,
  KVSize nKey,
  int dir
){

  KVBtCsr *pCsr = (KVBtCsr *)pKVCursor;

  assert( dir==0 || dir==1 || dir==-1 || dir==-2 );
  assert( BT_SEEK_EQ==0 && BT_SEEK_GE==1 && BT_SEEK_LE==-1 );
  assert( BT_SEEK_LEFAST==-2 );

  return sqlite4BtCsrSeek(pCsr->pCsr, (void *)aKey, nKey, dir);
}

/*
** Delete the entry that the cursor is pointing to.
**
** Though the entry is "deleted", it still continues to exist as a
** phantom.  Subsequent xNext or xPrev calls will work, as will
** calls to xKey and xData, thought the result from xKey and xData
** are undefined.
*/
static int btDelete(KVCursor *pKVCursor){
  KVBtCsr *pBtcsr = (KVBtCsr *)pKVCursor;
  return sqlite4BtDelete(pBtcsr->pCsr);
}

/*
** Return the key of the node the cursor is pointing to.
*/
static int btKey(
  KVCursor *pKVCursor,         /* The cursor whose key is desired */
272
273
274
275
276
277
278

279
280
281
282
283
284
285
286
287
    btGetMeta,                    /* xGetMeta */
    btPutMeta,                    /* xPutMeta */
    btGetMethod                   /* xGetMethod */
  };

  KVBt *pNew = 0;
  bt_db *pDb = 0;


  rc = sqlite4BtNew(ENV, sizeof(KVBt), &pDb);
  if( rc==SQLITE4_OK ){
    pNew = (KVBt*)sqlite4BtExtra(pDb);
    pNew->base.pStoreVfunc = &bt_methods;
    pNew->base.pEnv = pEnv;
    pNew->pDb = pDb;
    rc = sqlite4BtOpen(pDb, zFilename);
  }







>

|







271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
    btGetMeta,                    /* xGetMeta */
    btPutMeta,                    /* xPutMeta */
    btGetMethod                   /* xGetMethod */
  };

  KVBt *pNew = 0;
  bt_db *pDb = 0;
  int rc;

  rc = sqlite4BtNew(pEnv, sizeof(KVBt), &pDb);
  if( rc==SQLITE4_OK ){
    pNew = (KVBt*)sqlite4BtExtra(pDb);
    pNew->base.pStoreVfunc = &bt_methods;
    pNew->base.pEnv = pEnv;
    pNew->pDb = pDb;
    rc = sqlite4BtOpen(pDb, zFilename);
  }
Added test/simple3.test.


























































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 2013 September 24
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# The tests in this file were used while developing the SQLite 4 code. 
#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix simple3

db close
forcedelete test.db

do_test 1.0 {
  sqlite4 db file:test.db?kv=bt
  db close
} {}

do_test 1.1 { sqlite4 db file:test.db?kv=bt } {}
execsql { PRAGMA trace = 1 }
do_execsql_test 1.2 { CREATE TABLE t1(a, b) } 

finish_test
Changes to www/bt.wiki.
493
494
495
496
497
498
499
500
501
502
503
504
505
506







507
508
509
510
511
512
513

<p><b>Page Header</b>

<p>Page headers are similar to those in SQLite3: 

<ul>
  <li> 1 byte - flags.
  <li> 2 bytes - Number of cells on this page.
  <li> 2 bytes - Offset of first byte after last cell.
  <li> Internal nodes only: 4 bytes - Page number of rightmost child node.
</ul>

<p><b>Page Footer</b>









<h4 id=cell_formats>2.2.3.8. Cell Formats</h4>

<p><b>B-Tree Nodes</b>

<p>Cell format:








<
<





>
>
>
>
>
>
>







493
494
495
496
497
498
499


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

<p><b>Page Header</b>

<p>Page headers are similar to those in SQLite3: 

<ul>
  <li> 1 byte - flags.


  <li> Internal nodes only: 4 bytes - Page number of rightmost child node.
</ul>

<p><b>Page Footer</b>

<p> Starting from the end of the page, the fields in the page footer are:

<ul>
  <li> 2 bytes - Number of cells on this page.
  <li> 2 bytes - Offset of first byte after last cell.
  <li> 2 bytes for each cell - the offset to the start of the cell.
</ul>

<h4 id=cell_formats>2.2.3.8. Cell Formats</h4>

<p><b>B-Tree Nodes</b>

<p>Cell format: