/ Check-in [18500cdc]
Login
Overview
Comment:Continued work on btree (CVS 219)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:18500cdcc1a42118cdf650681ebb1cbeac106aa7
User & Date: drh 2001-05-24 21:06:35
Context
2001-05-26
13:15
:-) (CVS 220) check-in: 45a0e0fc user: drh tags: trunk
2001-05-24
21:06
Continued work on btree (CVS 219) check-in: 18500cdc user: drh tags: trunk
2001-05-21
13:45
:-) (CVS 218) check-in: 523d52df user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
...
134
135
136
137
138
139
140
141

142
143
144
145
146
147
148
149
150
151
...
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
...
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
...
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
...
251
252
253
254
255
256
257
258
259


260
261
262
263
264

265
266
267
268
269
270
271
...
275
276
277
278
279
280
281
282
283




284
285
286
287
288
289
290
...
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
...
366
367
368
369
370
371
372














373
374
375
376
377
378
379
380
381
382
383
384
385
386
...
389
390
391
392
393
394
395

396
397
398
399
400
401
402
...
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
...
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
...
529
530
531
532
533
534
535
536
537
538


539
540
541
542
543
544
545
...
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573

574


575
576
577

578









579
580
581


582
583
584
585
586
587
588
...
615
616
617
618
619
620
621







622





















623





















624


625












626
627
628
629
630
631
632
...
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
...
683
684
685
686
687
688
689






690


















































691



692

693
694



695
696












































697

































698
699
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.6 2001/05/21 13:45:10 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

/*
................................................................................
};
#define MAGIC_1  0x7264dc61
#define MAGIC_2  0x54e55d9e

/*
** Each database page has a header as follows:
**
**      page1_header          Extra numbers found on page 1 only.
**      rightmost_pgno        Page number of the right-most child page
**      first_cell            Index into MemPage.aPage of first cell
**      first_free            Index of first free block
**
** MemPage.pStart always points to the rightmost_pgno.  First_free is
** 0 if there is no free space on this page.  Otherwise, first_free is
** the index in MemPage.aPage[] of a FreeBlk structure that describes
................................................................................
  u32 nData;      /* Number of bytes of data */
  char aData[4];  /* Key and data */
};

/*
** Free space on a page is remembered using a linked list of the FreeBlk
** structures.  Space on a database page is allocated in increments of
** at least 4 bytes and is always aligned to a 4-byte boundry.

*/
struct FreeBlk {
  u16 iSize;      /* Number of u32-sized slots in the block of free space */
  u16 iNext;      /* Index in MemPage.aPage[] of the next free block */
};

/*
** When the key and data for a single entry in the BTree will not fit in
** the MX_LOACAL_PAYLOAD bytes of space available on the database page,
** then all extra data is written to a linked list of overflow pages.
................................................................................
** Unused pages in the database are also represented by instances of
** the OverflowPage structure.  The Page1Header.freeList field is the
** page number of the first page in a linked list of unused database
** pages.
*/
struct OverflowPage {
  Pgno next;
  char aData[SQLITE_PAGE_SIZE-sizeof(Pgno)];
};

/*
** For every page in the database file, an instance of the following structure
** is stored in memory.  The aPage[] array contains the data obtained from
** the disk.  The rest is auxiliary data that held in memory only.  The
** auxiliary data is only valid for regular database pages - the auxiliary
** data is meaningless for overflow pages and pages on the freelist.
**
** Of particular interest in the auxiliary data is the aCell[] entry.  Each
** aCell[] entry is a pointer to a Cell structure in aPage[].  The cells
** put in this array so that they can be accessed in constant time, rather
** than in linear time which would be needed if we walked the linked list.





*/
struct MemPage {
  char aPage[SQLITE_PAGE_SIZE];  /* Page data stored on disk */
  unsigned char isInit;          /* True if auxiliary data is initialized */
  unsigned char validUp;         /* True if MemPage.up is valid */
  unsigned char validLeft;       /* True if MemPage.left is valid */
  unsigned char validRight;      /* True if MemPage.right is valid */
  Pgno up;                       /* The parent page. 0 means this is the root */

  Pgno left;                     /* Left sibling page.  0==none */
  Pgno right;                    /* Right sibling page.  0==none */
  int idxStart;                  /* Index in aPage[] of real data */
  PageHdr *pStart;               /* Points to aPage[idxStart] */
  int nFree;                     /* Number of free bytes in aPage[] */
  int nCell;                     /* Number of entries on this page */
  Cell *aCell[MX_CELL];          /* All data entires in sorted order */
................................................................................
typedef Btree Bt;

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct Cursor {
  Btree *pBt;            /* The pointer back to the BTree */
  Cursor *pPrev, *pNext; /* List of all cursors */
  MemPage *pPage;        /* Page that contains the entry */
  int idx;               /* Index of the entry in pPage->aCell[] */
  int skip_incr;         /* */
};

/*
** Defragment the page given.  All of the free space
** is collected into one big block at the end of the
** page.
*/
static void defragmentPage(MemPage *pPage){
  int pc;
  int i, n;
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

................................................................................
    n = ROUNDUP(n);
    n += sizeof(Cell) - sizeof(pCell->aData);
    pCell->iNext = i<pPage->nCell ? pc + n : 0;
    memcpy(&newPage[pc], pCell, n);
    pPage->aCell[i] = (Cell*)&pPage->aPage[pc];
    pc += n;
  }
  assert( pPage->nFree==pc );
  memcpy(pPage->aPage, newPage, pc);
  pFBlk = &pPage->aPage[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->pStart->firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}
................................................................................
** Allocate space on a page.  The space needs to be at least
** nByte bytes in size.  (Actually, all allocations are rounded
** up to the next even multiple of 4.)  Return the index into
** pPage->aPage[] of the first byte of the new allocation.
** Or return 0 if there is not enough free space on the page to
** satisfy the allocation request.
**
** This routine will call defragmentPage if necessary to consolidate
** free space.  


*/
static int allocSpace(MemPage *pPage, int nByte){
  FreeBlk *p;
  u16 *pIdx;
  int start;

  nByte = ROUNDUP(nByte);
  if( pPage->nFree<nByte ) return 0;
  pIdx = &pPage->pStart->firstFree;
  p = (FreeBlk*)&pPage->aPage[*pIdx];
  while( p->iSize<nByte ){
    if( p->iNext==0 ){
      defragmentPage(pPage);
................................................................................
    }
    p = (FreeBlk*)&pPage->aPage[*pIdx];
  }
  if( p->iSize==nByte ){
    start = *pIdx;
    *pIdx = p->iNext;
  }else{
    p->iSize -= nByte;
    start = *pIdx + p->iSize;




  }
  pPage->nFree -= nByte;
  return start;
}

/*
** Return a section of the MemPage.aPage[] to the freelist.
................................................................................
  }
  *pIdx = start;
  pPage->nFree += size;
}

/*
** Initialize the auxiliary information for a disk block.






*/
static int initPage(MemPage *pPage, Pgno pgnoThis, Pgno pgnoParent){
  int idx;
  Cell *pCell;
  FreeBlk *pFBlk;

  pPage->idxStart = (pgnoThis==1) ? sizeof(Page1Header) : 0;
  pPage->pStart = (PageHdr*)&pPage->aPage[pPage->idxStart];
  pPage->isInit = 1;
  pPage->validUp = 1;
  pPage->up = pgnoParent;

  pPage->nCell = 0;
  idx = pPage->pStart->firstCell;
  while( idx!=0 ){
    if( idx>SQLITE_PAGE_SIZE-sizeof(Cell) ) goto page_format_error;
    if( idx<pPage->idxStart + sizeof(PageHeader) ) goto page_format_error;
    pCell = (Cell*)&pPage->aPage[idx];
    pPage->aCell[pPage->nCell++] = pCell;
................................................................................
    idx = pFBlk->iNext;
  }
  return SQLITE_OK;

page_format_error:
  return SQLITE_CORRUPT;
}















/*
** Open a new database.
**
** Actually, this routine just sets up the internal data structures
** for accessing the database.  We do not actually open the database
** file until the first page is loaded.
*/
int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree){
  Btree *pBt;

  pBt = sqliteMalloc( sizeof(*pBt) );
  if( pBt==0 ){
    **ppBtree = 0;
................................................................................
  rc = sqlitepager_open(&pBt->pPager, zFilename, 100, EXTRA_SPACE);
  if( rc!=SQLITE_OK ){
    if( pBt->pPager ) sqlitepager_close(pBt->pPager);
    sqliteFree(pBt);
    *ppBtree = 0;
    return rc;
  }

  pBt->pCursor = 0;
  pBt->page1 = 0;
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
................................................................................
*/
static int lockBtree(Btree *pBt){
  int rc;
  if( pBt->page1 ) return SQLITE_OK;
  rc = sqlitepager_get(pBt->pPager, 1, &pBt->page1);
  if( rc!=SQLITE_OK ) return rc;
  rc = initPage(pBt->page1, 1, 0);
  if( rc!=SQLITE_OK ) goto lock_failed;

  /* Do some checking to help insure the file we opened really is
  ** a valid database file. 
  */
  if( sqlitepager_pagecount(pBt->pPager)>0 ){
    Page1Header *pP1 = (Page1Header*)pBt->page1;
    if( pP1->magic1!=MAGIC_1 || pP1->magic2!=MAGIC_2 ){
      rc = SQLITE_CORRUPT;
      goto lock_failed;
    }
  }
  return rc;

lock_failed:
  sqlitepager_unref(pBt->page1);
  pBt->page1 = 0;

}

/*
** Start a new transaction
*/
int sqliteBtreeBeginTrans(Btree *pBt){
  int rc;

  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ) return rc;
  }
  rc = sqlitepager_write(pBt->page1);
  if( rc==SQLITE_OK ){
    pBt->inTrans = 1;





  }
  return rc;
}

/*
** Remove the last reference to the database file.  This will
** remove the read lock.
................................................................................

/*
** Commit the transaction currently in progress.  All cursors
** must be closed before this routine is called.
*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  assert( pBt->pCursor==0 );
  rc = sqlitepager_commit(pBt->pPager);
  unlockBtree(pBt);
  return rc;
}

/*
** Rollback the transaction in progress.  All cursors must be
** closed before this routine is called.
*/
int sqliteBtreeRollback(Btree *pBt){
  int rc;
  assert( pBt->pCursor==0 );
  rc = sqlitepager_rollback(pBt->pPager);
  unlockBtree(pBt);
  return rc;
}

/*
** Create a new cursor.  The act of acquiring a cursor
................................................................................
  rc = sqlitepager_get(pBt->pPager, 1, &pCur->pPage);
  if( rc!=SQLITE_OK ){
    sqliteFree(pCur);
    *ppCur = 0;
    return rc;
  }
  if( !pCur->pPage->isInit ){
    initPage(pCur->pPage);
  }
  pCur->idx = 0;


  *ppCur = pCur;
  return SQLITE_OK;
}

/*
** Close a cursor. 
*/
................................................................................
  if( pBt->pCursor==0 && pBt->inTrans==0 ){
    unlockBtree(pBt);
  }
  sqliteFree(pCur);
}

/*
** Return the number of bytes in the key of the entry to which
** the cursor is currently point.  If the cursor has not been
** initialized or is pointed to a deleted entry, then return 0.
*/
int sqliteBtreeKeySize(BtCursor *pCur){
  Cell *pCell;
  MemPage *pPage;

  pPage = pCur->pPage;

  if( pCur->idx >= pPage->nCell ) return 0;


  pCell = pPage->aCell[pCur->idx];
  return pCell->nKey;
}











static int getPayload(BtCursor *pCur, int offset, int amt, char *zBuf){
  char *aData;
  Pgno nextPage;


  aData = pCur->pPage->aCell[pCur->idx].aData;
  if( offset<MX_LOCAL_PAYLOAD ){
    int a = amt;
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aData[offset], a);
................................................................................
      zBuf += a;
    }
    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}








int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);





















int sqliteBtreeDataSize(BtCursor*);





















int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
















/*
** Compare the key for the entry that pCur points to against the 
** given key (pKey,nKeyOrig).  Put the comparison result in *pResult.
** The result is negative if pCur<pKey, zero if they are equal and
** positive if pCur>pKey.
**
................................................................................
  nextPage = *(Pgno*)&pCell->aData[MX_LOCAL_PAYLOAD];
  while( nKey>0 ){
    OverflowPage *pOvfl;
    if( nextPage==0 ){
      return SQLITE_CORRUPT;
    }
    rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl);
    if( rc!=0 ){
      return rc;
    }
    nextPage = pOvfl->next;
    n = nKey;
    if( n>OVERFLOW_SIZE ){
      n = OVERFLOW_SIZE;
    }
................................................................................
    pKey += n;
  }
  c = pCell->nKey - nKeyOrig;
  *pResult = c;
  return SQLITE_OK;
}


























































/* Move the cursor so that it points to an entry near pKey.



** Return 0 if the cursor is left pointing exactly at pKey.

** Return -1 if the cursor points to the largest entry less than pKey.
** Return 1 if the cursor points to the smallest entry greater than pKey.



*/
int sqliteBtreeMoveto(BtCursor*, void *pKey, int nKey);












































int sqliteBtreeDelete(BtCursor*);

































int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData);
int sqliteBtreeNext(BtCursor*);







|







 







|







 







|
>


|







 







|










|


>
>
>
>
>




<


<
>







 







|
|
|
|
|
|



|
|
|







 







|







 







|
|
>
>





>







 







<
|
>
>
>
>







 







>
>
>
>
>
>

|







|
|
>







 







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





|
|







 







>







 







|








|




|


>



|



>








>
>
>
>
>







 







|











|







 







|


>
>







 







|
|
|

|




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



>
>







 







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

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







 







|







 







>
>
>
>
>
>

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

>
>
>
|
>
|
<
>
>
>

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

|
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
...
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
...
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
...
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
...
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
...
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
...
283
284
285
286
287
288
289

290
291
292
293
294
295
296
297
298
299
300
301
...
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
...
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
...
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
...
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
...
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
...
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
...
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
...
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
...
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
...
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873

874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.7 2001/05/24 21:06:35 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

/*
................................................................................
};
#define MAGIC_1  0x7264dc61
#define MAGIC_2  0x54e55d9e

/*
** Each database page has a header as follows:
**
**      page1_header          Optional instance of Page1Header structure
**      rightmost_pgno        Page number of the right-most child page
**      first_cell            Index into MemPage.aPage of first cell
**      first_free            Index of first free block
**
** MemPage.pStart always points to the rightmost_pgno.  First_free is
** 0 if there is no free space on this page.  Otherwise, first_free is
** the index in MemPage.aPage[] of a FreeBlk structure that describes
................................................................................
  u32 nData;      /* Number of bytes of data */
  char aData[4];  /* Key and data */
};

/*
** Free space on a page is remembered using a linked list of the FreeBlk
** structures.  Space on a database page is allocated in increments of
** at least 4 bytes and is always aligned to a 4-byte boundry.  The
** linked list of freeblocks is always kept in order by address.
*/
struct FreeBlk {
  u16 iSize;      /* Number of bytes in this block of free space */
  u16 iNext;      /* Index in MemPage.aPage[] of the next free block */
};

/*
** When the key and data for a single entry in the BTree will not fit in
** the MX_LOACAL_PAYLOAD bytes of space available on the database page,
** then all extra data is written to a linked list of overflow pages.
................................................................................
** Unused pages in the database are also represented by instances of
** the OverflowPage structure.  The Page1Header.freeList field is the
** page number of the first page in a linked list of unused database
** pages.
*/
struct OverflowPage {
  Pgno next;
  char aData[OVERFLOW_SIZE];
};

/*
** For every page in the database file, an instance of the following structure
** is stored in memory.  The aPage[] array contains the data obtained from
** the disk.  The rest is auxiliary data that held in memory only.  The
** auxiliary data is only valid for regular database pages - the auxiliary
** data is meaningless for overflow pages and pages on the freelist.
**
** Of particular interest in the auxiliary data is the aCell[] entry.  Each
** aCell[] entry is a pointer to a Cell structure in aPage[].  The cells are
** put in this array so that they can be accessed in constant time, rather
** than in linear time which would be needed if we walked the linked list.
**
** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that.
*/
struct MemPage {
  char aPage[SQLITE_PAGE_SIZE];  /* Page data stored on disk */
  unsigned char isInit;          /* True if auxiliary data is initialized */

  unsigned char validLeft;       /* True if MemPage.left is valid */
  unsigned char validRight;      /* True if MemPage.right is valid */

  MemPage *pParent;              /* The parent of this page.  NULL for root */
  Pgno left;                     /* Left sibling page.  0==none */
  Pgno right;                    /* Right sibling page.  0==none */
  int idxStart;                  /* Index in aPage[] of real data */
  PageHdr *pStart;               /* Points to aPage[idxStart] */
  int nFree;                     /* Number of free bytes in aPage[] */
  int nCell;                     /* Number of entries on this page */
  Cell *aCell[MX_CELL];          /* All data entires in sorted order */
................................................................................
typedef Btree Bt;

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBt;                     /* The pointer back to the BTree */
  BtCursor *pPrev, *pNext;        /* List of all cursors */
  MemPage *pPage;                 /* Page that contains the entry */
  int idx;                        /* Index of the entry in pPage->aCell[] */
  int skip_incr;                  /* */
};

/*
** Defragment the page given.  All Cells are moved to the
** beginning of the page and all free space is collected 
** into one big FreeBlk at the end of the page.
*/
static void defragmentPage(MemPage *pPage){
  int pc;
  int i, n;
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

................................................................................
    n = ROUNDUP(n);
    n += sizeof(Cell) - sizeof(pCell->aData);
    pCell->iNext = i<pPage->nCell ? pc + n : 0;
    memcpy(&newPage[pc], pCell, n);
    pPage->aCell[i] = (Cell*)&pPage->aPage[pc];
    pc += n;
  }
  assert( pPage->nFree==SQLITE_PAGE_SIZE-pc );
  memcpy(pPage->aPage, newPage, pc);
  pFBlk = &pPage->aPage[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->pStart->firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}
................................................................................
** Allocate space on a page.  The space needs to be at least
** nByte bytes in size.  (Actually, all allocations are rounded
** up to the next even multiple of 4.)  Return the index into
** pPage->aPage[] of the first byte of the new allocation.
** Or return 0 if there is not enough free space on the page to
** satisfy the allocation request.
**
** If the page contains nBytes of free space but does not contain
** nBytes of contiguous free space, then defragementPage() is
** called to consolidate all free space before allocating the
** new chunk.
*/
static int allocSpace(MemPage *pPage, int nByte){
  FreeBlk *p;
  u16 *pIdx;
  int start;

  nByte = ROUNDUP(nByte);
  if( pPage->nFree<nByte ) return 0;
  pIdx = &pPage->pStart->firstFree;
  p = (FreeBlk*)&pPage->aPage[*pIdx];
  while( p->iSize<nByte ){
    if( p->iNext==0 ){
      defragmentPage(pPage);
................................................................................
    }
    p = (FreeBlk*)&pPage->aPage[*pIdx];
  }
  if( p->iSize==nByte ){
    start = *pIdx;
    *pIdx = p->iNext;
  }else{

    start = *pIdx;
    FreeBlk *pNew = (FreeBlk*)&pPage->aPage[start + nByte];
    pNew->iNext = p->iNext;
    pNew->iSize = p->iSize - nByte;
    *pIdx = start + nByte;
  }
  pPage->nFree -= nByte;
  return start;
}

/*
** Return a section of the MemPage.aPage[] to the freelist.
................................................................................
  }
  *pIdx = start;
  pPage->nFree += size;
}

/*
** Initialize the auxiliary information for a disk block.
**
** Return SQLITE_OK on success.  If we see that the page does
** not contained a well-formed database page, then return 
** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
** guarantee that the page is well-formed.  It only shows that
** we failed to detect any corruption.
*/
static int initPage(MemPage *pPage, Pgno pgnoThis, MemPage *pParent){
  int idx;
  Cell *pCell;
  FreeBlk *pFBlk;

  pPage->idxStart = (pgnoThis==1) ? sizeof(Page1Header) : 0;
  pPage->pStart = (PageHdr*)&pPage->aPage[pPage->idxStart];
  pPage->isInit = 1;
  assert( pPage->pParent==0 );
  pPage->pParent = pParent;
  if( pParent ) sqlitepager_ref(pParent);
  pPage->nCell = 0;
  idx = pPage->pStart->firstCell;
  while( idx!=0 ){
    if( idx>SQLITE_PAGE_SIZE-sizeof(Cell) ) goto page_format_error;
    if( idx<pPage->idxStart + sizeof(PageHeader) ) goto page_format_error;
    pCell = (Cell*)&pPage->aPage[idx];
    pPage->aCell[pPage->nCell++] = pCell;
................................................................................
    idx = pFBlk->iNext;
  }
  return SQLITE_OK;

page_format_error:
  return SQLITE_CORRUPT;
}

/*
** 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(void *pData){
  MemPage *pPage = (MemPage*)pData;
  if( pPage->pParent ){
    MemPage *pParent = pPage->pParent;
    pPage->pParent = 0;
    sqlitepager_unref(pParent);
  }
}

/*
** Open a new database.
**
** Actually, this routine just sets up the internal data structures
** for accessing the database.  We do not open the database file 
** until the first page is loaded.
*/
int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree){
  Btree *pBt;

  pBt = sqliteMalloc( sizeof(*pBt) );
  if( pBt==0 ){
    **ppBtree = 0;
................................................................................
  rc = sqlitepager_open(&pBt->pPager, zFilename, 100, EXTRA_SPACE);
  if( rc!=SQLITE_OK ){
    if( pBt->pPager ) sqlitepager_close(pBt->pPager);
    sqliteFree(pBt);
    *ppBtree = 0;
    return rc;
  }
  sqlitepager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->page1 = 0;
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
................................................................................
*/
static int lockBtree(Btree *pBt){
  int rc;
  if( pBt->page1 ) return SQLITE_OK;
  rc = sqlitepager_get(pBt->pPager, 1, &pBt->page1);
  if( rc!=SQLITE_OK ) return rc;
  rc = initPage(pBt->page1, 1, 0);
  if( rc!=SQLITE_OK ) goto page1_init_failed;

  /* Do some checking to help insure the file we opened really is
  ** a valid database file. 
  */
  if( sqlitepager_pagecount(pBt->pPager)>0 ){
    Page1Header *pP1 = (Page1Header*)pBt->page1;
    if( pP1->magic1!=MAGIC_1 || pP1->magic2!=MAGIC_2 ){
      rc = SQLITE_CORRUPT;
      goto page1_init_failed;
    }
  }
  return rc;

page1_init_failed:
  sqlitepager_unref(pBt->page1);
  pBt->page1 = 0;
  return rc;
}

/*
** Attempt to start a new transaction.
*/
int sqliteBtreeBeginTrans(Btree *pBt){
  int rc;
  Page1Header *pP1;
  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ) return rc;
  }
  rc = sqlitepager_write(pBt->page1);
  if( rc==SQLITE_OK ){
    pBt->inTrans = 1;
  }
  pP1 = (Page1Header*)pBt->page1;
  if( pP1->magic1==0 ){
    pP1->magic1 = MAGIC_1;
    pP1->magic2 = MAGIC_2;
  }
  return rc;
}

/*
** Remove the last reference to the database file.  This will
** remove the read lock.
................................................................................

/*
** Commit the transaction currently in progress.  All cursors
** must be closed before this routine is called.
*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  unlockBtree(pBt);
  return rc;
}

/*
** Rollback the transaction in progress.  All cursors must be
** closed before this routine is called.
*/
int sqliteBtreeRollback(Btree *pBt){
  int rc;
  if( pBt->pCursor!=0 ) return SQLITE_ERROR;
  rc = sqlitepager_rollback(pBt->pPager);
  unlockBtree(pBt);
  return rc;
}

/*
** Create a new cursor.  The act of acquiring a cursor
................................................................................
  rc = sqlitepager_get(pBt->pPager, 1, &pCur->pPage);
  if( rc!=SQLITE_OK ){
    sqliteFree(pCur);
    *ppCur = 0;
    return rc;
  }
  if( !pCur->pPage->isInit ){
    initPage(pCur->pPage, 1, 0);
  }
  pCur->idx = 0;
  pCur->depth = 0;
  pCur->aPage[0] = pCur->pPage;
  *ppCur = pCur;
  return SQLITE_OK;
}

/*
** Close a cursor. 
*/
................................................................................
  if( pBt->pCursor==0 && pBt->inTrans==0 ){
    unlockBtree(pBt);
  }
  sqliteFree(pCur);
}

/*
** Write the number of bytes of key for the entry the cursor is
** pointing to into *pSize.  Return SQLITE_OK.  Failure is not
** possible.
*/
int sqliteBtreeKeySize(BtCursor *pCur, int *pSize){
  Cell *pCell;
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    *pSize = 0;
  }else{
    pCell = pPage->aCell[pCur->idx];
    *psize = pCell->nKey;
  }
  return SQLITE_OK;
}

/*
** Read payload information from the entry that the pCur cursor is
** pointing to.  Begin reading the payload at "offset" and read
** a total of "amt" bytes.  Put the result in zBuf.
**
** This routine does not make a distinction between key and data.
** It just reads bytes from the payload area.
*/
static int getPayload(BtCursor *pCur, int offset, int amt, char *zBuf){
  char *aData;
  Pgno nextPage;
  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->idx>=0 && pCur->idx<pCur->nCell );
  aData = pCur->pPage->aCell[pCur->idx].aData;
  if( offset<MX_LOCAL_PAYLOAD ){
    int a = amt;
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aData[offset], a);
................................................................................
      zBuf += a;
    }
    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A total
** of "amt" bytes will be transfered into zBuf[].  The transfer
** begins at "offset".  If the key does not contain enough data
** to satisfy the request, no data is fetched and this routine
** returns SQLITE_ERROR.
*/
int sqliteBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){
  Cell *pCell;
  MemPage *pPage;

  if( amt<0 ) return SQLITE_ERROR;
  if( offset<0 ) return SQLITE_ERROR;
  if( amt==0 ) return SQLITE_OK;
  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;
  }
  pCell = pPage->aCell[pCur->idx];
  if( amt+offset > pCell->nKey ){
  return getPayload(pCur, offset, amt, zBuf);
}

/*
** Write the number of bytes of data on the entry that the cursor
** is pointing to into *pSize.  Return SQLITE_OK.  Failure is
** not possible.
*/
int sqliteBtreeDataSize(BtCursor *pCur, int *pSize){
  Cell *pCell;
  MemPage *pPage;

  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    *pSize = 0;
  }else{
    pCell = pPage->aCell[pCur->idx];
    *pSize = pCell->nData;
  }
  return SQLITE_OK;
}

/*
** Read part of the data associated with cursor pCur.  A total
** of "amt" bytes will be transfered into zBuf[].  The transfer
** begins at "offset".  If the size of the data in the record
** is insufficent to satisfy this request then no data is read
** and this routine returns SQLITE_ERROR.
*/
int sqliteBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){
  Cell *pCell;
  MemPage *pPage;

  if( amt<0 ) return SQLITE_ERROR;
  if( offset<0 ) return SQLITE_ERROR;
  if( amt==0 ) return SQLITE_OK;
  pPage = pCur->pPage;
  assert( pPage!=0 );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;
  }
  pCell = pPage->aCell[pCur->idx];
  if( amt+offset > pCell->nKey ){
  return getPayload(pCur, offset + pCell->nKey, amt, zBuf);
}

/*
** Compare the key for the entry that pCur points to against the 
** given key (pKey,nKeyOrig).  Put the comparison result in *pResult.
** The result is negative if pCur<pKey, zero if they are equal and
** positive if pCur>pKey.
**
................................................................................
  nextPage = *(Pgno*)&pCell->aData[MX_LOCAL_PAYLOAD];
  while( nKey>0 ){
    OverflowPage *pOvfl;
    if( nextPage==0 ){
      return SQLITE_CORRUPT;
    }
    rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl);
    if( rc ){
      return rc;
    }
    nextPage = pOvfl->next;
    n = nKey;
    if( n>OVERFLOW_SIZE ){
      n = OVERFLOW_SIZE;
    }
................................................................................
    pKey += n;
  }
  c = pCell->nKey - nKeyOrig;
  *pResult = c;
  return SQLITE_OK;
}

/*
** Move the cursor down to a new child page.
*/
static int childPage(BtCursor *pCur, int newPgno){
  int rc;
  MemPage *pNewPage;

  rc = sqlitepager_get(pCur->pBt->pPager, newPgno, &pNewPage);
  if( rc ){
    return rc;
  }
  if( !pNewPage->isInit ){
    initPage(pNewPage, newPgno, pCur->pPage);
  }
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  return SQLITE_OK;
}

/*
** Move the cursor up to the parent page
*/
static int parentPage(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;

  pParent = pCur->pPage->pParent;
  oldPgno = sqlitepager_pagenumber(pCur->pPage);
  if( pParent==0 ){
    return SQLITE_INTERNAL;
  }
  sqlitepager_ref(pParent);
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pParent;
  pCur->idx = pPage->nCell;
  for(i=0; i<pPage->nCell; i++){
    if( pPage->aCell[i].pgno==oldPgno ){
      pCur->idx = i;
      break;
    }
  }
}

/*
** Move the cursor to the root page
*/
static int rootPage(BtCursor *pCur){
  MemPage *pNew;
  pNew = pCur->pBt->page1;
  sqlitepager_ref(pNew);
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pNew;
  pCur->idx = 0;
  return SQLITE_OK;
}

/* Move the cursor so that it points to an entry near pKey.
** Return a success code.
**
** If pRes!=NULL, then *pRes is written with an integer code to
** describe the results.  *pRes is set to 0 if the cursor is left 
** pointing at an entry that exactly matches pKey.  *pRes is made
** negative if the cursor is on the largest entry less than pKey.

** *pRes is set positive if the cursor is on the smallest entry
** greater than pKey.  *pRes is not changed if the return value
** is something other than SQLITE_OK;
*/
int sqliteBtreeMoveto(BtCursor *pCur, void *pKey, int nKey, int *pRes){
  int rc;
  rc = rootPage(pCur);
  if( rc ) return rc;
  for(;;){
    int lwr, upr;
    Pgno chldPg;
    MemPage *pPage = pCur->pPage;
    lwr = 0;
    upr = pPage->nCell-1;
    while( lwr<=upr ){
      int c;
      pCur->idx = (lwr+upr)/2;
      rc = compareKey(pCur, pKey, nKey, &c);
      if( rc ) return rc;
      if( c==0 ){
        if( pRes ) *pRes = 0;
        return SQLITE_OK;
      }
      if( c<0 ){
        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
    assert( lwr==upr+1 );
    if( lwr>=pPage->nCell ){
      chldPg = pPage->pStart->pgno;
    }else{
      chldPg = pPage->aCell[lwr].pgno;
    }
    if( chldPg==0 ){
      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }
    rc = childPage(pCur, chldPg);
    if( rc ) return rc;
  }
}

/*
** Advance the cursor to the next entry in the database.  If pRes!=NULL
** then set *pRes=0 on success and set *pRes=1 if the cursor was
** pointing to the last entry in the database.
*/
int sqliteBtreeNext(BtCursor *pCur, int *pRes){
  MemPage *pPage;
  int rc;
  int moved = 0;
  if( pCur->skip_next ){
    pCur->skip_next = 0;
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  pPage = pCur->pPage;
  pCur->idx++;
  while( pCur->idx>=pPage->nCell ){
    if( pCur->depth==0 ){
      if( pRes ) *pRes = 1;
      return SQLITE_OK;
    }
    rc = parentPage(pCur);
    if( rc ) return rc;
    moved = 1;
    pPage = pCur->pPage;
  }
  if( moved ){
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  while( pCur->idx<pPage->nCell && pPage->aCell[pCur->idx].pgno>0 ){
    rc = childPage(pCur, pPage->aCell[pCur->idx].pgno);
    if( rc ) return rc;
    pPage = pCur->pPage;
  }
  if( pRes ) *pRes = 0;
  return SQLITE_OK;
}

int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData);
int sqliteBtreeDelete(BtCursor*);

Changes to src/btree.h.

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
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.1 2001/04/17 20:09:11 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................

int sqliteBtreeBeginTrans(Btree*);
int sqliteBtreeCommit(Btree*);
int sqliteBtreeRollback(Btree*);


int sqliteBtreeCursor(Btree*, BtCursor **ppCur);

/* Move the cursor so that it points to an entry near pKey.
** Return 0 if the cursor is left pointing exactly at pKey.
** Return -1 if the cursor points to the largest entry less than pKey.
** Return 1 if the cursor points to the smallest entry greater than pKey.
*/
int sqliteBtreeMoveto(BtCursor*, void *pKey, int nKey);
int sqliteBtreeDelete(BtCursor*);
int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData);
int sqliteBtreeNext(BtCursor*);
int sqliteBtreeKeySize(BtCursor*);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);







|







 







<
<
<
<
<
<
|


|
|

|


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
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.2 2001/05/24 21:06:36 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................

int sqliteBtreeBeginTrans(Btree*);
int sqliteBtreeCommit(Btree*);
int sqliteBtreeRollback(Btree*);


int sqliteBtreeCursor(Btree*, BtCursor **ppCur);






int sqliteBtreeMoveto(BtCursor*, void *pKey, int nKey, *pRes);
int sqliteBtreeDelete(BtCursor*);
int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData);
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

Changes to src/pager.c.

23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
109
110
111
112
113
114
115

116
117
118
119
120
121
122
...
473
474
475
476
477
478
479











480
481
482
483
484
485
486
...
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820



821
822
823
824
825
826
827
*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or one writer.
**
** @(#) $Id: pager.c,v 1.6 2001/05/21 13:45:10 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>
................................................................................
struct Pager {
  char *zFilename;            /* Name of the database file */
  char *zJournal;             /* Name of the journal file */
  int fd, jfd;                /* File descriptors for database and journal */
  int dbSize;                 /* Number of pages in the file */
  int origDbSize;             /* dbSize before the current change */
  int nExtra;                 /* Add this many bytes to each in-memory page */

  int nPage;                  /* Total number of in-memory pages */
  int nRef;                   /* Number of in-memory pages with PgHdr.nRef>0 */
  int mxPage;                 /* Maximum number of pages to hold in cache */
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  unsigned char state;        /* SQLITE_UNLOCK, _READLOCK or _WRITELOCK */
  unsigned char errMask;      /* One of several kinds of errors */
  PgHdr *pFirst, *pLast;      /* List of free pages */
................................................................................
  pPager->errMask = 0;
  pPager->pFirst = 0;
  pPager->pLast = 0;
  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  *ppPager = pPager;
  return SQLITE_OK;
}












/*
** Return the total number of pages in the file opened by pPager.
*/
int sqlitepager_pagecount(Pager *pPager){
  int n;
  struct stat statbuf;
................................................................................
  /* Decrement the reference count for this page
  */
  pPg = DATA_TO_PGHDR(pData);
  assert( pPg->nRef>0 );
  pPager = pPg->pPager;
  pPg->nRef--;

  /* When the number of references to a page reach 0, add the
  ** page to the freelist.
  */
  if( pPg->nRef==0 ){
    pPg->pNextFree = 0;
    pPg->pPrevFree = pPager->pLast;
    pPager->pLast = pPg;
    if( pPg->pPrevFree ){
      pPg->pPrevFree->pNextFree = pPg;
    }else{
      pPager->pFirst = pPg;
    }



  
    /* When all pages reach the freelist, drop the read lock from
    ** the database file.
    */
    pPager->nRef--;
    assert( pPager->nRef>=0 );
    if( pPager->nRef==0 ){







|







 







>







 







>
>
>
>
>
>
>
>
>
>
>







 







|
|










>
>
>







23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
...
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
...
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or one writer.
**
** @(#) $Id: pager.c,v 1.7 2001/05/24 21:06:36 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>
................................................................................
struct Pager {
  char *zFilename;            /* Name of the database file */
  char *zJournal;             /* Name of the journal file */
  int fd, jfd;                /* File descriptors for database and journal */
  int dbSize;                 /* Number of pages in the file */
  int origDbSize;             /* dbSize before the current change */
  int nExtra;                 /* Add this many bytes to each in-memory page */
  void (*xDestructor)(void*); /* Call this routine when freeing pages */
  int nPage;                  /* Total number of in-memory pages */
  int nRef;                   /* Number of in-memory pages with PgHdr.nRef>0 */
  int mxPage;                 /* Maximum number of pages to hold in cache */
  int nHit, nMiss, nOvfl;     /* Cache hits, missing, and LRU overflows */
  unsigned char state;        /* SQLITE_UNLOCK, _READLOCK or _WRITELOCK */
  unsigned char errMask;      /* One of several kinds of errors */
  PgHdr *pFirst, *pLast;      /* List of free pages */
................................................................................
  pPager->errMask = 0;
  pPager->pFirst = 0;
  pPager->pLast = 0;
  memset(pPager->aHash, 0, sizeof(pPager->aHash));
  *ppPager = pPager;
  return SQLITE_OK;
}

/*
** Set the destructor for this pager.  If not NULL, the destructor is called
** when the reference count on the page reaches zero.  
**
** The destructor is not called as a result sqlitepager_close().  
** Destructors are only called by sqlitepager_unref().
*/
void sqlitepager_set_destructor(Pager *pPager, void (*xDesc)(void*)){
  pPager->xDestructor = xDesc;
}

/*
** Return the total number of pages in the file opened by pPager.
*/
int sqlitepager_pagecount(Pager *pPager){
  int n;
  struct stat statbuf;
................................................................................
  /* Decrement the reference count for this page
  */
  pPg = DATA_TO_PGHDR(pData);
  assert( pPg->nRef>0 );
  pPager = pPg->pPager;
  pPg->nRef--;

  /* When the number of references to a page reach 0, call the
  ** destructor and add the page to the freelist.
  */
  if( pPg->nRef==0 ){
    pPg->pNextFree = 0;
    pPg->pPrevFree = pPager->pLast;
    pPager->pLast = pPg;
    if( pPg->pPrevFree ){
      pPg->pPrevFree->pNextFree = pPg;
    }else{
      pPager->pFirst = pPg;
    }
    if( pPager->xDestructor ){
      pPager->xDestructor(pData);
    }
  
    /* When all pages reach the freelist, drop the read lock from
    ** the database file.
    */
    pPager->nRef--;
    assert( pPager->nRef>=0 );
    if( pPager->nRef==0 ){

Changes to src/pager.h.

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
..
40
41
42
43
44
45
46
47

48
49
50
51
52
53
54
55
56
57
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem.  The page cache subsystem reads and writes a file a page
** at a time and provides a journal for rollback.
**
** @(#) $Id: pager.h,v 1.3 2001/04/28 16:52:42 drh Exp $
*/

/*
** The size of one page
*/
#define SQLITE_PAGE_SIZE 1024

................................................................................
typedef unsigned int Pgno;

/*
** Each open file is managed by a separate instance of the "Pager" structure.
*/
typedef struct Pager Pager;

int sqlitepager_open(Pager **ppPager, const char *zFilename,int nPage,int nEx);

int sqlitepager_close(Pager *pPager);
int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);
void *sqlitepager_lookup(Pager *pPager, Pgno pgno);
int sqlitepager_unref(void*);
Pgno sqlitepager_pagenumber(void*);
int sqlitepager_write(void*);
int sqlitepager_pagecount(Pager*);
int sqlitepager_commit(Pager*);
int sqlitepager_rollback(Pager*);
int *sqlitepager_stats(Pager*);







|







 







|
>










21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
..
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem.  The page cache subsystem reads and writes a file a page
** at a time and provides a journal for rollback.
**
** @(#) $Id: pager.h,v 1.4 2001/05/24 21:06:36 drh Exp $
*/

/*
** The size of one page
*/
#define SQLITE_PAGE_SIZE 1024

................................................................................
typedef unsigned int Pgno;

/*
** Each open file is managed by a separate instance of the "Pager" structure.
*/
typedef struct Pager Pager;

int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx);
void sqiltepager_set_destructor(Pager*, void(*)(void*));
int sqlitepager_close(Pager *pPager);
int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);
void *sqlitepager_lookup(Pager *pPager, Pgno pgno);
int sqlitepager_unref(void*);
Pgno sqlitepager_pagenumber(void*);
int sqlitepager_write(void*);
int sqlitepager_pagecount(Pager*);
int sqlitepager_commit(Pager*);
int sqlitepager_rollback(Pager*);
int *sqlitepager_stats(Pager*);

Changes to test/pager.test.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
62
63
64
65
66
67
68
69






70
71
72
73
74
75

















76
77
78
79
80
81
82
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is page cache subsystem.
#
# $Id: pager.test,v 1.4 2001/05/21 13:45:10 drh Exp $


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

if {$dbprefix!="mem:" && [info commands pager_open]!=""} {

................................................................................
} {0}
do_test pager-2.2 {
  set v [catch {
    set ::g1 [page_get $::p1 0]
  } msg]
  lappend v $msg
} {1 SQLITE_ERROR}
do_test pager-2.3 {






  set v [catch {
    set ::g1 [page_get $::p1 1]
  } msg]
  if {$v} {lappend v $msg}
  set v
} {0}

















do_test pager-2.4 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0}
do_test pager-2.5 {
  pager_pagecount $::p1
} {0}
do_test pager-2.6 {







|







 







|
>
>
>
>
>
>






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







19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
..
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is page cache subsystem.
#
# $Id: pager.test,v 1.5 2001/05/24 21:06:36 drh Exp $


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

if {$dbprefix!="mem:" && [info commands pager_open]!=""} {

................................................................................
} {0}
do_test pager-2.2 {
  set v [catch {
    set ::g1 [page_get $::p1 0]
  } msg]
  lappend v $msg
} {1 SQLITE_ERROR}
do_test pager-2.3.1 {
  set ::gx [page_lookup $::p1 1]
} {}
do_test pager-2.3.2 {
  pager_stats $::p1
} {ref 0 page 0 max 10 size -1 state 0 err 0 hit 0 miss 0 ovfl 0}
do_test pager-2.3.3 {
  set v [catch {
    set ::g1 [page_get $::p1 1]
  } msg]
  if {$v} {lappend v $msg}
  set v
} {0}
do_test pager-2.3.3 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0}
do_test pager-2.3.4 {
  set ::gx [page_lookup $::p1 1]
  expr {$::gx!=""}
} {1}
do_test pager-2.3.5 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0}
do_test pager-2.3.6 {
  expr $::g1==$::gx
} {1}
do_test pager-2.3.7 {
  page_unref $::gx
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0}
do_test pager-2.4 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0}
do_test pager-2.5 {
  pager_pagecount $::p1
} {0}
do_test pager-2.6 {