/ Check-in [d12481f0]
Login

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

Overview
Comment:Code to auto-vacuum the database if all root pages happen to be in the right place. Not active by default and largely untested. (CVS 2037)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d12481f09cbe51c7ea499bc22afec5de3af14ad4
User & Date: danielk1977 2004-11-02 12:56:41
Context
2004-11-02
14:24
Require that the page size be a power of 2. (CVS 2038) check-in: c33b34db user: drh tags: trunk
12:56
Code to auto-vacuum the database if all root pages happen to be in the right place. Not active by default and largely untested. (CVS 2037) check-in: d12481f0 user: danielk1977 tags: trunk
2004-11-01
16:03
Updates to the support.html page. (CVS 2036) check-in: 5515acce user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
...
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
....
1177
1178
1179
1180
1181
1182
1183

1184

1185
1186
1187
1188
1189
1190
1191
....
1449
1450
1451
1452
1453
1454
1455










































































































































































































































































1456
1457
1458
1459
1460
1461
1462
....
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
....
2610
2611
2612
2613
2614
2615
2616









2617
2618
2619
2620
2621
2622
2623
....
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
....
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
....
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
....
3758
3759
3760
3761
3762
3763
3764

3765

3766
3767
3768
3769
3770
3771
3772
....
3874
3875
3876
3877
3878
3879
3880












3881
3882
3883
3884
3885
3886
3887
....
4338
4339
4340
4341
4342
4343
4344





4345
4346
4347
4348
4349
4350
4351






4352
4353
4354
4355
4356

4357
4358
4359
4360
4361
4362
4363

4364
4365
4366
4367
4368
4369
4370
....
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
....
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
....
4565
4566
4567
4568
4569
4570
4571






4572
4573
4574
4575
4576
4577
4578
....
4707
4708
4709
4710
4711
4712
4713






4714
4715
4716
4717
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.195 2004/10/31 16:25:43 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
** used to test if pgno is a pointer-map page.
*/
#define PTRMAP_PAGENO(pgsz, pgno) (((pgno-2)/(pgsz/5+1))*(pgsz/5+1)+2)
#define PTRMAP_PTROFFSET(pgsz, pgno) (((pgno-2)%(pgsz/5+1)-1)*5)

/*
** The first byte of each 5-byte pointer map entry identifies the type
** of page that the following 4-byte page number refers to (either a
** regular btree page or an overflow page).



**
** If the type is PTRMAP_OVERFLOW, then the page is an overflow page.
** In this case the pointer is always the first 4 bytes of the page.


**
** If the type is PTRMAP_BTREE, then the page is a btree page. In this
** case the pointer may be a 'left-pointer' (stored following a cell-header), 
** a pointer to an overflow page (stored after a cell's data payload), 
** or the 'right pointer' of a btree page.












*/
#define PTRMAP_BTREE 1

#define PTRMAP_OVERFLOW 2



/*
** Write an entry into the pointer map.




*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  iPtrmap = PTRMAP_PAGENO(pBt->pageSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=0 ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->pageSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=pgno ){
    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
................................................................................

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
** Read an entry from the pointer map.




*/
static int ptrmapGet(Btree *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->pageSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=0 ){
    return rc;
  }

  offset = PTRMAP_PTROFFSET(pBt->pageSize, key);
  *pEType = pPtrmap[offset];
  *pPgno = get4byte(&pPtrmap[offset+1]);

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

#endif /* SQLITE_OMIT_AUTOVACUUM */

................................................................................
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
  sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);
  *ppBtree = pBt;
#ifdef SQLITE_AUTOVACUUM
  /* Note: This is temporary code for use during development of auto-vacuum. */

  pBt->autoVacuum = 1;

#endif
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}











































































































































































































































































/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeCommit(Btree *pBt){
................................................................................
      rc = SQLITE_OK;
    }
  }
  *pRes = 0;
  return rc;
}

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

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlite3pager_write()
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** sqlite3pager_unref() on the new page when it is done.
................................................................................
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3pager_write(pPage1->aData);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);










  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
    memset(pPage->aData, 0, 8);
    put4byte(&pPage1->aData[32], pPage->pgno);
................................................................................
      /* If the database supports auto-vacuum, add an entry to the 
      ** pointer-map for the overflow page just allocated. If the page just 
      ** allocated was the first in the overflow list, then the balance() 
      ** routine may adjust the pointer-map entry later.
      */
      if( pBt->autoVacuum && rc==0 ){
        if( pgnoPtrmap!=0 ){
          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW, pgnoPtrmap);
        }else{
          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_BTREE, pPage->pgno);
        }
      }
#endif
      if( rc ){
        releasePage(pToRelease);
        clearCell(pPage, pCell);
        return rc;
................................................................................
    ** TODO: This looks like quite an expensive thing to do. Investigate.
    */
    if( pBt->autoVacuum ){
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      if( info.iOverflow ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_BTREE, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }
  if( !pPage->leaf ){
    rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
................................................................................
*/
static int balance(MemPage *pPage){
  int rc = SQLITE_OK;
  if( pPage->pParent==0 ){
    if( pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( pPage->nCell==0 ){
      rc = balance_shallower(pPage);
    }
  }else{
    if( pPage->nOverflow>0 || pPage->nFree>pPage->pBt->usableSize*2/3 ){
      rc = balance_nonroot(pPage);
    }
  }
................................................................................
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */

  moveToRoot(pCur);

end_insert:
  sqliteFree(newCell);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
  if( rc ) return rc;












  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}

................................................................................
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
      break;
    }
    if( isFreeList ){
      int n = get4byte(&pOvfl[4]);





      if( n>pCheck->pBt->usableSize/4-8 ){
        checkAppendMsg(pCheck, zContext,
           "freelist leaf count too big on page %d", iPage);
        N--;
      }else{
        for(i=0; i<n; i++){
          checkRef(pCheck, get4byte(&pOvfl[8+i*4]), zContext);






        }
        N -= n;
      }
    }
#ifndef SQLITE_OMIT_AUTOVACUUM

    /* If this database supports auto-vacuum and iPage is not the last
    ** page in this overflow list, check that the pointer-map entry for
    ** the following page matches iPage.
    */
    if( pCheck->pBt->autoVacuum && !isFreeList && N>0 ){
      i = get4byte(pOvfl);
      checkPtrmap(pCheck, i, PTRMAP_OVERFLOW, iPage, zContext);

    }
#endif
    iPage = get4byte(pOvfl);
    sqlite3pager_unref(pOvfl);
  }
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */
................................................................................
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;
    if( sz>info.nLocal ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_BTREE, iPage, zContext);
      }
#endif
      checkList(pCheck, 0, pgnoOvfl, nPage, zContext);
    }

    /* Check sanity of left child page.
    */
................................................................................
    }
  }
  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    sprintf(zContext, "On page %d at right child: ", iPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, zContext);
    }
#endif
    checkTreePage(pCheck, pgno, pPage, zContext,0,0,0,0);
  }
 
  /* Check for complete coverage of the page
  */
................................................................................
  checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
            get4byte(&pBt->pPage1->aData[36]), "Main freelist: ");

  /* Check all the tables.
  */
  for(i=0; i<nRoot; i++){
    if( aRoot[i]==0 ) continue;






    checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
  }

  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage; i++){
#ifdef SQLITE_OMIT_AUTOVACUUM
................................................................................
** created, populated with this journal pointer and synced to disk.
**
** Once this is routine has returned, the only thing required to commit
** the write-transaction for this database file is to delete the journal.
*/
int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
  if( pBt->inTrans==TRANS_WRITE ){






    return sqlite3pager_sync(pBt->pPager, zMaster);
  }
  return SQLITE_OK;
}







|







 







|
|
|
>
>
>

<
<
>
>

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

|
>
|
>
>



>
>
>
>









|







 







>
>
>
>







 







|
|







 







>
|
>







 







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







 







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







 







>
>
>
>
>
>
>
>
>







 







|

|







 







|







 







|







 







>
|
>







 







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







 







>
>
>
>
>






|
>
>
>
>
>
>





>
|
|
|
|
|
|
|
>







 







|







 







|







 







>
>
>
>
>
>







 







>
>
>
>
>
>




5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
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
...
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
....
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
....
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
....
2759
2760
2761
2762
2763
2764
2765













2766
2767
2768
2769
2770
2771
2772
....
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
....
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
....
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
....
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
....
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
....
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
....
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
....
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
....
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
....
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
....
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.196 2004/11/02 12:56:41 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
** used to test if pgno is a pointer-map page.
*/
#define PTRMAP_PAGENO(pgsz, pgno) (((pgno-2)/(pgsz/5+1))*(pgsz/5+1)+2)
#define PTRMAP_PTROFFSET(pgsz, pgno) (((pgno-2)%(pgsz/5+1)-1)*5)

/*
** The pointer map is a lookup table that contains an entry for each database
** page in the file except for page 1. In this context 'database page' refers
** to any page that is not part of the pointer map itself.  Each pointer map
** entry consists of a single byte 'type' and a 4 byte page number. The
** PTRMAP_XXX identifiers below are the valid types. The interpretation
** of the page-number depends on the type, as follows:
**


** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
**                  used in this case.
**



** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
**                  is not used in this case.
**
** PTRMAP_OVERFLOW1: The database page is the first page in a list of 
**                   overflow pages. The page number identifies the page that
**                   contains the cell with a pointer to this overflow page.
**
** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
**                   overflow pages. The page-number identifies the previous
**                   page in the overflow page list.
**
** PTRMAP_BTREE: The database page is a non-root btree page. The page number
**               identifies the parent page in the btree.
*/
#define PTRMAP_ROOTPAGE 1
#define PTRMAP_FREEPAGE 2
#define PTRMAP_OVERFLOW1 3
#define PTRMAP_OVERFLOW2 4
#define PTRMAP_BTREE 5

/*
** Write an entry into the pointer map.
**
** This routine updates the pointer map entry for page number 'key'
** so that it maps to type 'eType' and parent page number 'pgno'.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){
  u8 *pPtrmap;    /* The pointer map page */
  Pgno iPtrmap;   /* The pointer map page number */
  int offset;     /* Offset in pointer map page */
  int rc;

  iPtrmap = PTRMAP_PAGENO(pBt->pageSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  offset = PTRMAP_PTROFFSET(pBt->pageSize, key);

  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=pgno ){
    rc = sqlite3pager_write(pPtrmap);
    if( rc!=0 ){
................................................................................

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

/*
** Read an entry from the pointer map.
**
** This routine retrieves the pointer map entry for page 'key', writing
** the type and parent page number to *pEType and *pPgno respectively.
** An error code is returned if something goes wrong, otherwise SQLITE_OK.
*/
static int ptrmapGet(Btree *pBt, Pgno key, u8 *pEType, Pgno *pPgno){
  int iPtrmap;       /* Pointer map page index */
  u8 *pPtrmap;       /* Pointer map page data */
  int offset;        /* Offset of entry in pointer map */
  int rc;

................................................................................
  iPtrmap = PTRMAP_PAGENO(pBt->pageSize, key);
  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);
  if( rc!=0 ){
    return rc;
  }

  offset = PTRMAP_PTROFFSET(pBt->pageSize, key);
  if( pEType ) *pEType = pPtrmap[offset];
  if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);

  sqlite3pager_unref(pPtrmap);
  return SQLITE_OK;
}

#endif /* SQLITE_OMIT_AUTOVACUUM */

................................................................................
  }
  pBt->usableSize = pBt->pageSize - nReserve;
  pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
  sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);
  *ppBtree = pBt;
#ifdef SQLITE_AUTOVACUUM
  /* Note: This is temporary code for use during development of auto-vacuum. */
  if( zFilename && 0!=strcmp(zFilename, ":memory:") ){
    pBt->autoVacuum = 1;
  }
#endif
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
    if( wrflag ) pBt->inStmt = 0;
  }else{
    unlockBtreeIfUnused(pBt);
  }
  return rc;
}

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

#ifndef SQLITE_OMIT_AUTOVACUUM

/*
** Set the pointer-map entries for all children of page pPage. Also, if
** pPage contains cells that point to overflow pages, set the pointer
** map entries for the overflow pages as well.
*/
static int setChildPtrmaps(MemPage *pPage){
  int i;                             /* Counter variable */
  int nCell;                         /* Number of cells in page pPage */
  int rc = SQLITE_OK;                /* Return code */
  Btree *pBt = pPage->pBt;
  int isInitOrig = pPage->isInit;
  Pgno pgno = pPage->pgno;

  initPage(pPage, 0);
  nCell = pPage->nCell;

  for(i=0; i<nCell; i++){
    CellInfo info;
    u8 *pCell = findCell(pPage, i);

    parseCellPtr(pPage, pCell, &info);
    if( info.iOverflow ){
      Pgno ovflPgno = get4byte(&pCell[info.iOverflow]);
      rc = ptrmapPut(pBt, ovflPgno, PTRMAP_OVERFLOW1, pgno);
      if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
    }
    if( !pPage->leaf ){
      Pgno childPgno = get4byte(pCell);
      rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
      if( rc!=SQLITE_OK ) goto set_child_ptrmaps_out;
    }
  }

  if( !pPage->leaf ){
    Pgno childPgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    rc = ptrmapPut(pBt, childPgno, PTRMAP_BTREE, pgno);
  }

set_child_ptrmaps_out:
  pPage->isInit = isInitOrig;
  return rc;
}

/*
** Somewhere on pPage, which is guarenteed to be a btree page, not an overflow
** page, is a pointer to page iFrom. Modify this pointer so that it points to
** iTo. Parameter eType describes the type of pointer to be modified, as 
** follows:
**
** PTRMAP_BTREE:     pPage is a btree-page. The pointer points at a child 
**                   page of pPage.
**
** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
**                   page pointed to by one of the cells on pPage.
**
** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
**                   overflow page in the list.
*/
static void modifyPagePointer(MemPage *pPage, Pgno iFrom, Pgno iTo, u8 eType){

  if( eType==PTRMAP_OVERFLOW2 ){
    assert( get4byte(pPage->aData)==iFrom );
    put4byte(pPage->aData, iFrom);
  }else{
    int isInitOrig = pPage->isInit;
    int i;
    int nCell;

    initPage(pPage, 0);
    nCell = pPage->nCell;

   /*  assert( !pPage->leaf && eType==PTRMAP_BTREE ); */

    for(i=0; i<nCell; i++){
      u8 *pCell = findCell(pPage, i);
      if( eType==PTRMAP_OVERFLOW1 ){
        CellInfo info;
        parseCellPtr(pPage, pCell, &info);
        if( info.iOverflow ){
          if( iFrom==get4byte(&pCell[info.iOverflow]) ){
            put4byte(&pCell[info.iOverflow], iTo);
            break;
          }
        }
      }else{
        if( get4byte(pCell)==iFrom ){
          put4byte(pCell, iTo);
          break;
        }
      }
    }
  
    if( i==nCell ){
      assert( eType==PTRMAP_BTREE );
      assert( get4byte(&pPage->aData[pPage->hdrOffset+8])==iFrom );
      put4byte(&pPage->aData[pPage->hdrOffset+8], iTo);
    }

    pPage->isInit = isInitOrig;
  }
}

/* Forward declaration required by autoVacuumCommit(). */
static int allocatePage(Btree *, MemPage **, Pgno *, Pgno);

/*
** This routine is called prior to sqlite3pager_commit when a transaction
** is commited for an auto-vacuum database.
*/
static int autoVacuumCommit(Btree *pBt){
  Pager *pPager = pBt->pPager;
  Pgno nFreeList;   /* Number of pages remaining on the free-list. */
  Pgno origDbSize;  /* Pages in the database file */
  Pgno finDbSize;   /* Pages in the database file after truncation */
  int i;            /* Counter variable */
  int rc;           /* Return code */
  u8 eType;

  Pgno iDbPage;              /* The database page to move */
  u8 *pDbPage = 0;           /* "" */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  MemPage *pPtrMemPage = 0;  /* "" */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
  MemPage *pFreeMemPage = 0; /* "" */

#ifndef NDEBUG
  int nRef = *sqlite3pager_stats(pPager);
#endif

  assert( pBt->autoVacuum );

  /* Figure out how many free-pages are in the database. If there are no
  ** free pages, then auto-vacuum is a no-op.
  */
  nFreeList = get4byte(&pBt->pPage1->aData[36]);
  if( nFreeList==0 ) return SQLITE_OK;

  origDbSize = sqlite3pager_pagecount(pPager);
  finDbSize = origDbSize - nFreeList;
  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origDbSize, finDbSize));

  /* Note: This is temporary code for use during development of auto-vacuum. 
  **
  ** Inspect the pointer map to make sure there are no root pages with a
  ** page number greater than finDbSize. If so, the auto-vacuum cannot
  ** proceed. This limitation will be fixed when root pages are automatically
  ** allocated at the start of the database file.
  */
  for( i=finDbSize+1; i<=origDbSize; i++ ){
    rc = ptrmapGet(pBt, i, &eType, 0);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    if( eType==PTRMAP_ROOTPAGE ){
      TRACE(("AUTOVACUUM: Cannot proceed due to root-page on page %d\n", i));
      return SQLITE_OK;
    }
  }

  /* Variable 'finDbSize' will be the size of the file in pages after
  ** the auto-vacuum has completed (the current file size minus the number
  ** of pages on the free list). Loop through the pages that lie beyond
  ** this mark, and if they are not already on the free list, move them
  ** to a free page earlier in the file (somewhere before finDbSize).
  */
  for( iDbPage=finDbSize+1; iDbPage<=origDbSize; iDbPage++ ){
    rc = ptrmapGet(pBt, iDbPage, &eType, &iPtrPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    assert( eType!=PTRMAP_ROOTPAGE );

    /* If iDbPage is already on the free-list, do not swap it. */
    if( eType==PTRMAP_FREEPAGE ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbPage = pDbMemPage->aData;

    /* Find the next page in the free-list that is not already at the end 
    ** of the file. A page can be pulled off the free list using the 
    ** allocatePage() routine.
    */
    do{
      if( pFreeMemPage ){
        releasePage(pFreeMemPage);
        pFreeMemPage = 0;
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origDbSize );
    }while( iFreePage>finDbSize );

    /* Move page iDbPage from it's current location to page number iFreePage */
    TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d)\n", 
        iDbPage, iFreePage, iPtrPage));
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;
    rc = sqlite3pager_movepage(pPager, pDbPage, iFreePage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    pDbMemPage->pgno = iFreePage;

    /* If pDbPage was a btree-page, then it may have child pages and/or cells
    ** that point to overflow pages. The pointer map entries for all these
    ** pages need to be changed.
    */
    if( eType==PTRMAP_BTREE ){
      rc = setChildPtrmaps(pDbMemPage);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
    }
    releasePage(pDbMemPage);
    pDbMemPage = 0;

    /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
    ** that it points at iFreePage. Also fix the pointer map entry for
    ** iPtrPage.
    */
    rc = getPage(pBt, iPtrPage, &pPtrMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    rc = sqlite3pager_write(pPtrMemPage->aData);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    modifyPagePointer(pPtrMemPage, iDbPage, iFreePage, eType);
    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    releasePage(pPtrMemPage);
  }

  /* The entire free-list has been swapped to the end of the file. So
  ** truncate the database file to finDbSize pages and consider the
  ** free-list empty.
  */
  rc = sqlite3pager_write(pBt->pPage1->aData);
  if( rc!=SQLITE_OK ) goto autovacuum_out;
  put4byte(&pBt->pPage1->aData[32], 0);
  put4byte(&pBt->pPage1->aData[36], 0);
  rc = sqlite3pager_truncate(pBt->pPager, finDbSize);
  if( rc!=SQLITE_OK ) goto autovacuum_out;

autovacuum_out:
  /* TODO: A goto autovacuum_out; will fail to call releasePage() on 
  ** outstanding references. Fix.
  */
  if( nRef!=*sqlite3pager_stats(pPager) ){
    sqlite3pager_refdump(pPager);
  }
  assert( nRef==*sqlite3pager_stats(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3pager_rollback(pPager);
  }
  return rc;
}
#endif

/*
** Commit the transaction currently in progress.
**
** This will release the write lock on the database file.  If there
** are no active cursors, it also releases the read lock.
*/
int sqlite3BtreeCommit(Btree *pBt){
................................................................................
      rc = SQLITE_OK;
    }
  }
  *pRes = 0;
  return rc;
}














/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, sqlite3pager_write()
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** sqlite3pager_unref() on the new page when it is done.
................................................................................
  pPage->pParent = 0;

  /* Increment the free page count on pPage1 */
  rc = sqlite3pager_write(pPage1->aData);
  if( rc ) return rc;
  n = get4byte(&pPage1->aData[36]);
  put4byte(&pPage1->aData[36], n+1);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If the database supports auto-vacuum, write an entry in the pointer-map
  ** to indicate that the page is free.
  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
    memset(pPage->aData, 0, 8);
    put4byte(&pPage1->aData[32], pPage->pgno);
................................................................................
      /* If the database supports auto-vacuum, add an entry to the 
      ** pointer-map for the overflow page just allocated. If the page just 
      ** allocated was the first in the overflow list, then the balance() 
      ** routine may adjust the pointer-map entry later.
      */
      if( pBt->autoVacuum && rc==0 ){
        if( pgnoPtrmap!=0 ){
          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW2, pgnoPtrmap);
        }else{
          rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        }
      }
#endif
      if( rc ){
        releasePage(pToRelease);
        clearCell(pPage, pCell);
        return rc;
................................................................................
    ** TODO: This looks like quite an expensive thing to do. Investigate.
    */
    if( pBt->autoVacuum ){
      CellInfo info;
      parseCellPtr(pPage, pCell, &info);
      if( info.iOverflow ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }
  if( !pPage->leaf ){
    rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
................................................................................
*/
static int balance(MemPage *pPage){
  int rc = SQLITE_OK;
  if( pPage->pParent==0 ){
    if( pPage->nOverflow>0 ){
      rc = balance_deeper(pPage);
    }
    if( rc==SQLITE_OK && pPage->nCell==0 ){
      rc = balance_shallower(pPage);
    }
  }else{
    if( pPage->nOverflow>0 || pPage->nFree>pPage->pBt->usableSize*2/3 ){
      rc = balance_nonroot(pPage);
    }
  }
................................................................................
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
  sqliteFree(newCell);
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.  The cursor
................................................................................
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
  if( rc ) return rc;
#ifndef SQLITE_OMIT_AUTOVACUUM
  /* Note: This is temporary code for use during development of auto-vacuum. 
  ** There should be no need for a pointer map entry for root-pages.
  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pgnoRoot, PTRMAP_ROOTPAGE, 0);
    if( rc ){
      sqlite3pager_unref(pRoot->aData);
      return rc;
    }
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}

................................................................................
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
      break;
    }
    if( isFreeList ){
      int n = get4byte(&pOvfl[4]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pCheck->pBt->autoVacuum ){
        checkPtrmap(pCheck, iPage, PTRMAP_FREEPAGE, 0, zContext);
      }
#endif
      if( n>pCheck->pBt->usableSize/4-8 ){
        checkAppendMsg(pCheck, zContext,
           "freelist leaf count too big on page %d", iPage);
        N--;
      }else{
        for(i=0; i<n; i++){
          Pgno iFreePage = get4byte(&pOvfl[8+i*4]);
#ifndef SQLITE_OMIT_AUTOVACUUM
          if( pCheck->pBt->autoVacuum ){
            checkPtrmap(pCheck, iFreePage, PTRMAP_FREEPAGE, 0, zContext);
          }
#endif
          checkRef(pCheck, iFreePage, zContext);
        }
        N -= n;
      }
    }
#ifndef SQLITE_OMIT_AUTOVACUUM
    else{
      /* If this database supports auto-vacuum and iPage is not the last
      ** page in this overflow list, check that the pointer-map entry for
      ** the following page matches iPage.
      */
      if( pCheck->pBt->autoVacuum && N>0 ){
        i = get4byte(pOvfl);
        checkPtrmap(pCheck, i, PTRMAP_OVERFLOW2, iPage, zContext);
      }
    }
#endif
    iPage = get4byte(pOvfl);
    sqlite3pager_unref(pOvfl);
  }
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */
................................................................................
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;
    if( sz>info.nLocal ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext);
      }
#endif
      checkList(pCheck, 0, pgnoOvfl, nPage, zContext);
    }

    /* Check sanity of left child page.
    */
................................................................................
    }
  }
  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    sprintf(zContext, "On page %d at right child: ", iPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, 0);
    }
#endif
    checkTreePage(pCheck, pgno, pPage, zContext,0,0,0,0);
  }
 
  /* Check for complete coverage of the page
  */
................................................................................
  checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
            get4byte(&pBt->pPage1->aData[36]), "Main freelist: ");

  /* Check all the tables.
  */
  for(i=0; i<nRoot; i++){
    if( aRoot[i]==0 ) continue;
#ifndef SQLITE_OMIT_AUTOVACUUM
/* Note: This is temporary code for use during development of auto-vacuum. */
    if( pBt->autoVacuum && aRoot[i]>1 ){
      checkPtrmap(&sCheck, aRoot[i], PTRMAP_ROOTPAGE, 0, 0);
    }
#endif
    checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
  }

  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage; i++){
#ifdef SQLITE_OMIT_AUTOVACUUM
................................................................................
** created, populated with this journal pointer and synced to disk.
**
** Once this is routine has returned, the only thing required to commit
** the write-transaction for this database file is to delete the journal.
*/
int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
  if( pBt->inTrans==TRANS_WRITE ){
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      int rc = autoVacuumCommit(pBt); 
      if( rc!=SQLITE_OK ) return rc;
    }
#endif
    return sqlite3pager_sync(pBt->pPager, zMaster);
  }
  return SQLITE_OK;
}

Changes to src/pager.c.

14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
....
2013
2014
2015
2016
2017
2018
2019






2020
2021
2022
2023






2024
2025
2026
2027
2028
2029
2030
....
3197
3198
3199
3200
3201
3202
3203











































































3204
3205
3206
3207
3208
3209
3210
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.169 2004/10/31 02:22:49 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

................................................................................
  if( rc!=SQLITE_OK ){
    return rc;
  }

  while( pList ){
    assert( pList->dirty );
    sqlite3OsSeek(&pPager->fd, (pList->pgno-1)*(i64)pPager->pageSize);






    CODEC(pPager, PGHDR_TO_DATA(pList), pList->pgno, 6);
    TRACE3("STORE %d page %d\n", pPager->fd.h, pList->pgno);
    rc = sqlite3OsWrite(&pPager->fd, PGHDR_TO_DATA(pList), pPager->pageSize);
    CODEC(pPager, PGHDR_TO_DATA(pList), pList->pgno, 0);






    if( rc ) return rc;
    pList->dirty = 0;
    pList = pList->pDirty;
  }
  return SQLITE_OK;
}

................................................................................

    pPager->state = PAGER_SYNCED;
  }

sync_exit:
  return rc;
}












































































#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
/*
** Return the current state of the file lock for the given pager.
** The return value is one of NO_LOCK, SHARED_LOCK, RESERVED_LOCK,
** PENDING_LOCK, or EXCLUSIVE_LOCK.
*/







|







 







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







 







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







14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
....
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
....
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.170 2004/11/02 12:56:41 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

................................................................................
  if( rc!=SQLITE_OK ){
    return rc;
  }

  while( pList ){
    assert( pList->dirty );
    sqlite3OsSeek(&pPager->fd, (pList->pgno-1)*(i64)pPager->pageSize);
    /* If there are dirty pages in the page cache with page numbers greater
    ** than Pager.dbSize, this means sqlite3pager_truncate() was called to
    ** make the file smaller (presumably by auto-vacuum code). Do not write
    ** any such pages to the file.
    */
    if( pList->pgno<=pPager->dbSize ){
      CODEC(pPager, PGHDR_TO_DATA(pList), pList->pgno, 6);
      TRACE3("STORE %d page %d\n", pPager->fd.h, pList->pgno);
      rc = sqlite3OsWrite(&pPager->fd, PGHDR_TO_DATA(pList), pPager->pageSize);
      CODEC(pPager, PGHDR_TO_DATA(pList), pList->pgno, 0);
    }
#ifndef NDEBUG
    else{
      TRACE3("NOSTORE %d page %d\n", pPager->fd.h, pList->pgno);
    }
#endif
    if( rc ) return rc;
    pList->dirty = 0;
    pList = pList->pDirty;
  }
  return SQLITE_OK;
}

................................................................................

    pPager->state = PAGER_SYNCED;
  }

sync_exit:
  return rc;
}

#ifndef SQLITE_OMIT_AUTOVACUUM
/*
** Move the page identified by pData to location pgno in the file. 
**
** There must be no references to the current page pgno. If current page
** pgno is not already in the rollback journal, it is not written there by
** by this routine. The same applies to the page pData refers to on entry to
** this routine.
**
** References to the page refered to by pData remain valid. Updating any
** meta-data associated with page pData (i.e. data stored in the nExtra bytes
** allocated along with the page) is the responsibility of the caller.
**
** A transaction must be active when this routine is called, however it is 
** illegal to call this routine if a statment transaction is active.
*/
int sqlite3pager_movepage(Pager *pPager, void *pData, Pgno pgno){
  PgHdr *pPg = DATA_TO_PGHDR(pData);
  PgHdr *pPgOld; 

  assert( !pPager->stmtInUse );
  /* assert( pPg->pNextFree==0 && pPg->pPrevFree==0 && pPg->nRef>0 ); */
  assert( pPg->nRef>0 );

  /* Unlink pPg from it's hash-chain */
  if( pPg->pNextHash ){
    pPg->pNextHash->pPrevHash = pPg->pPrevHash;
  }
  if( pPg->pPrevHash ){
    pPg->pPrevHash->pNextHash = pPg->pNextHash;
  }else{
    int h = pager_hash(pPg->pgno);
    assert( pPager->aHash[h]==pPg );
    pPager->aHash[h] = pPg->pNextHash;
  }

  /* Change the page number for pPg */
  pPg->pgno = pgno;

  pPgOld = pager_lookup(pPager, pgno);
  if( pPgOld ){
    /* Remove pPgOld from the page number hash-chain and insert pPg. */
    assert(pPgOld->nRef==0 && !pPgOld->pNextStmt && !pPgOld->pPrevStmt );
    if( pPgOld->pNextHash ){
      pPgOld->pNextHash->pPrevHash = pPg;
    }
    if( pPgOld->pPrevHash ){
      pPgOld->pPrevHash->pNextHash = pPg;
    }else{
      int h = pager_hash(pgno);
      assert( pPager->aHash[h]==pPgOld );
      pPager->aHash[h] = pPg;
    }
    pPgOld->pNextHash = pPgOld->pPrevHash = 0;
  }else{
    /* Insert pPg into it's new hash-chain. */
    int h = pager_hash(pgno);
    if( pPager->aHash[h] ){
      pPager->aHash[h]->pNextHash = pPg;
    }
    pPg->pNextHash = pPager->aHash[h];
    pPg->pPrevHash = 0;
  }

  /* Don't write the old page when sqlite3pager_sync() is called. Do write
  ** the new one. 
  */
  pPgOld->dirty = 0;
  pPg->dirty = 1;
  pPager->dirtyCache = 1;

  return SQLITE_OK;
}
#endif

#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
/*
** Return the current state of the file lock for the given pager.
** The return value is one of NO_LOCK, SHARED_LOCK, RESERVED_LOCK,
** PENDING_LOCK, or EXCLUSIVE_LOCK.
*/

Changes to src/pager.h.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
87
88
89
90
91
92
93

94
95
96
97
98
99
100
101
102
**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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.38 2004/10/05 02:41:43 drh Exp $
*/

/*
** The default size of a database page.
*/
#ifndef SQLITE_DEFAULT_PAGE_SIZE
# define SQLITE_DEFAULT_PAGE_SIZE 1024
................................................................................
int *sqlite3pager_stats(Pager*);
void sqlite3pager_set_safety_level(Pager*,int);
const char *sqlite3pager_filename(Pager*);
const char *sqlite3pager_dirname(Pager*);
const char *sqlite3pager_journalname(Pager*);
int sqlite3pager_rename(Pager*, const char *zNewName);
void sqlite3pager_set_codec(Pager*,void(*)(void*,void*,Pgno,int),void*);


#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
int sqlite3pager_lockstate(Pager*);
#endif

#ifdef SQLITE_TEST
void sqlite3pager_refdump(Pager*);
int pager3_refinfo_enable;
#endif







|







 







>









9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
**    May you share freely, never taking more than you give.
**
*************************************************************************
** 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.39 2004/11/02 12:56:41 danielk1977 Exp $
*/

/*
** The default size of a database page.
*/
#ifndef SQLITE_DEFAULT_PAGE_SIZE
# define SQLITE_DEFAULT_PAGE_SIZE 1024
................................................................................
int *sqlite3pager_stats(Pager*);
void sqlite3pager_set_safety_level(Pager*,int);
const char *sqlite3pager_filename(Pager*);
const char *sqlite3pager_dirname(Pager*);
const char *sqlite3pager_journalname(Pager*);
int sqlite3pager_rename(Pager*, const char *zNewName);
void sqlite3pager_set_codec(Pager*,void(*)(void*,void*,Pgno,int),void*);
int sqlite3pager_movepage(Pager*,void*,Pgno);

#if defined(SQLITE_DEBUG) || defined(SQLITE_TEST)
int sqlite3pager_lockstate(Pager*);
#endif

#ifdef SQLITE_TEST
void sqlite3pager_refdump(Pager*);
int pager3_refinfo_enable;
#endif

Added test/autovacuum.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the SELECT statement.
#
# $Id: autovacuum.test,v 1.1 2004/11/02 12:56:41 danielk1977 Exp $

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

proc make_str {char len} {
  set str [string repeat $char. $len]
  return [string range $str 0 [expr $len-1]]
}

proc file_pages {} {
  return [expr [file size test.db] / 1024]
}

do_test autovacuum-1.1 {
  execsql {
    CREATE TABLE av1(a);
  }
} {}

set ENTRY_LEN 1100

set delete_orders [list]
lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20}
lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} 
lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1}
lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2}

lappend delete_orders {{1 2 3 4 5 6 7 8 9 10} {11 12 13 14 15 16 17 18 19 20}}
lappend delete_orders \
        {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12 4 10}}


set tn 0
foreach delete_order $delete_orders {
  incr tn

  # Set up the table.
  set ::tbl_data [list]
  foreach i [lsort -integer [eval concat $delete_order]] {
    execsql "INSERT INTO av1 (oid, a) VALUES($i, '[make_str $i $ENTRY_LEN]')"
    lappend ::tbl_data [make_str $i $ENTRY_LEN]
  }

# puts "File has [file_pages] pages"

  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

  foreach delete $delete_order {
# if {$delete==6} { set btree_trace 1 ; breakpoint }
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
set btree_trace 0

    do_test autovacuum-1.$tn.($delete).2 {
      execsql {
        pragma integrity_check
      }
    } {ok}

    foreach d $delete {
      set idx [lsearch $::tbl_data [make_str $d $ENTRY_LEN]]
      set ::tbl_data [lreplace $::tbl_data $idx $idx]
    }
    do_test autovacuum-1.$tn.($delete).3 {
      execsql {
        select a from av1
      }
    } $::tbl_data
# if {$::nErr>0} finish_test
  }

  do_test autovacuum-1.$tn.3 {
    file_pages
  } {3}
}

finish_test

Changes to test/quick.test.

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
..
28
29
30
31
32
33
34


35
36
37
38
39
40
41
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file runs all tests.
#
# $Id: quick.test,v 1.30 2004/09/02 14:57:09 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

................................................................................
  corrupt.test
  crash.test
  malloc.test
  memleak.test
  misuse.test
  quick.test
  utf16.test


}

if {[sqlite3 -has-codec]} {
  # lappend EXCLUDE \
  #  conflict.test
}








|







 







>
>







6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
..
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file runs all tests.
#
# $Id: quick.test,v 1.31 2004/11/02 12:56:41 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

................................................................................
  corrupt.test
  crash.test
  malloc.test
  memleak.test
  misuse.test
  quick.test
  utf16.test

  autovacuum.test
}

if {[sqlite3 -has-codec]} {
  # lappend EXCLUDE \
  #  conflict.test
}