** 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.207 2004/11/05 03:56:01 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    releasePage(pPtrPage);
  }
  return rc;
}

/* 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. */
  int nPtrMap;      /* Number of pointer-map pages deallocated */
  Pgno origSize;  /* Pages in the database file */
  Pgno finSize;   /* Pages in the database file after truncation */
  int i;            /* Counter variable */
  int rc;           /* Return code */
  u8 eType;
  int pgsz = pBt->pageSize;  /* Page size for this database */
  Pgno iDbPage;              /* The database page to move */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
................................................................................
  if( nFreeList==0 ){
    return SQLITE_OK;
  }

  origSize = sqlite3pager_pagecount(pPager);
  nPtrMap = (nFreeList-origSize+PTRMAP_PAGENO(pgsz, origSize)+pgsz/5)/(pgsz/5);
  finSize = origSize - nFreeList - nPtrMap;

  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origSize, finSize));

#if 0
  /* 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 finSize. 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=finSize+1; i<=origSize; 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;
    }
  }
#endif

  /* Variable 'finSize' 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 finSize).
  */
  for( iDbPage=finSize+1; iDbPage<=origSize; iDbPage++ ){
    rc = ptrmapGet(pBt, iDbPage, &eType, &iPtrPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    assert( eType!=PTRMAP_ROOTPAGE );

    /* If iDbPage is a free or pointer map page, do not swap it.
    ** Instead, make sure the page is in the journal file.
    */
    if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;

................................................................................
    ** allocatePage() routine.
    */
    do{
      if( pFreeMemPage ){
        releasePage(pFreeMemPage);
        pFreeMemPage = 0;
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origSize );
    }while( iFreePage>finSize );
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;

    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
................................................................................
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlite3pager_unref() on *ppPage if an error is returned.
**
** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "nearby".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.




*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno nearby){






  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */

  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    MemPage *pTrunk;

























    rc = sqlite3pager_write(pPage1->aData);
    if( rc ) return rc;
    put4byte(&pPage1->aData[36], n-1);










    rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);




    if( rc ) return rc;



    rc = sqlite3pager_write(pTrunk->aData);
    if( rc ){
      releasePage(pTrunk);

      return rc;
    }

    k = get4byte(&pTrunk->aData[4]);
    if( k==0 ){

      /* The trunk has no leaves.  So extract the trunk page itself and
      ** use it as the newly allocated page */
      *pPgno = get4byte(&pPage1->aData[32]);


      memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
      *ppPage = pTrunk;

      TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
    }else if( k>pBt->usableSize/4 - 8 ){
      /* Value of k is out of range.  Database corruption */
      return SQLITE_CORRUPT; /* bkpt-CORRUPT */











    }else{




































      /* Extract a leaf from the trunk */
      int closest;

      unsigned char *aData = pTrunk->aData;
      if( nearby>0 ){
        int i, dist;
        closest = 0;
        dist = get4byte(&aData[8]) - nearby;
        if( dist<0 ) dist = -dist;
        for(i=1; i<k; i++){
          int d2 = get4byte(&aData[8+i*4]) - nearby;
          if( d2<0 ) d2 = -d2;
          if( d2<dist ) closest = i;


        }

      }else{
        closest = 0;
      }

      *pPgno = get4byte(&aData[8+closest*4]);


      if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
        /* Free page off the end of the file */
        return SQLITE_CORRUPT; /* bkpt-CORRUPT */
      }
      TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d: %d more free pages\n",

             *pPgno, closest+1, k, pTrunk->pgno, n-1));
      if( closest<k-1 ){
        memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
      }
      put4byte(&aData[4], k-1);
      rc = getPage(pBt, *pPgno, ppPage);
      releasePage(pTrunk);
      if( rc==SQLITE_OK ){
        sqlite3pager_dont_rollback((*ppPage)->aData);
        rc = sqlite3pager_write((*ppPage)->aData);
      }

    }




  }else{
    /* There are no pages on the freelist, so create a new page at the
    ** end of the file */
    *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;

#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum && PTRMAP_ISPAGE(pBt->pageSize, *pPgno) ){
................................................................................
  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. Also make sure the page is in
  ** the journal file.
  */
  if( pBt->autoVacuum ){
    rc = ptrmapPut(pBt, pPage->pgno, PTRMAP_FREEPAGE, 0);
    if( rc ) return rc;
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
................................................................................
  pPrior = &pCell[info.iOverflow];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
#ifndef SQLITE_OMIT_AUTOVACUUM
      Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
#endif
      rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
#ifndef SQLITE_OMIT_AUTOVACUUM
      /* If the database supports auto-vacuum, and the second or subsequent
      ** overflow page is being allocated, add an entry to the pointer-map
      ** for that page now. The entry for the first overflow page will be
      ** added later, by the insertCell() routine.
      */
      if( pBt->autoVacuum && pgnoPtrmap!=0 && rc==SQLITE_OK ){
................................................................................
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(pNew->aData);
    }else{
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
................................................................................
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
#ifdef SQLITE_OMIT_AUTOVACUUM
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
  if( rc ) return rc;
#else
  if( pBt->autoVacuum ){
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */

    /* Run the auto-vacuum code to ensure the free-list is empty. This is
    ** not really necessary, but it avoids complications in dealing with
    ** a free-list in the code below.
    ** TODO: This may need to be revisited.
    ** TODO2: Actually this is no-good. running the auto-vacuum routine
    **        involves truncating the database, which means the journal-file
    **        must be synced(). No-good.
    */
/*
    rc = autoVacuumCommit(pBt);
    if( rc!=SQLITE_OK ) return rc;
*/

    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;
................................................................................
    }
    assert( pgnoRoot>=3 );

    /* Allocate a page. The page that currently resides at pgnoRoot will
    ** be moved to the allocated page (unless the allocated page happens
    ** to reside at pgnoRoot).
    */
    rc = allocatePage(pBt, &pPageMove, &pgnoMove, 1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    if( pgnoMove!=pgnoRoot ){
      u8 eType;
      Pgno iPtrPage;
................................................................................
    }
    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
    if( rc ) return rc;
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;

** 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.208 2004/11/05 12:27:02 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.
................................................................................
    rc = ptrmapPut(pBt, iFreePage, eType, iPtrPage);
    releasePage(pPtrPage);
  }
  return rc;
}

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

/*
** 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. */
  int nPtrMap;      /* Number of pointer-map pages deallocated */
  Pgno origSize;  /* Pages in the database file */
  Pgno finSize;   /* Pages in the database file after truncation */

  int rc;           /* Return code */
  u8 eType;
  int pgsz = pBt->pageSize;  /* Page size for this database */
  Pgno iDbPage;              /* The database page to move */
  MemPage *pDbMemPage = 0;   /* "" */
  Pgno iPtrPage;             /* The page that contains a pointer to iDbPage */
  Pgno iFreePage;            /* The free-list page to move iDbPage to */
................................................................................
  if( nFreeList==0 ){
    return SQLITE_OK;
  }

  origSize = sqlite3pager_pagecount(pPager);
  nPtrMap = (nFreeList-origSize+PTRMAP_PAGENO(pgsz, origSize)+pgsz/5)/(pgsz/5);
  finSize = origSize - nFreeList - nPtrMap;

  TRACE(("AUTOVACUUM: Begin (db size %d->%d)\n", origSize, finSize));



















  /* Variable 'finSize' 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 finSize).
  */
  for( iDbPage=finSize+1; iDbPage<=origSize; iDbPage++ ){
    rc = ptrmapGet(pBt, iDbPage, &eType, &iPtrPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;
    assert( eType!=PTRMAP_ROOTPAGE );

    /* If iDbPage is a free or pointer map page, do not swap it.
    ** TODO: Instead, make sure the page is in the journal file.
    */
    if( eType==PTRMAP_FREEPAGE || PTRMAP_ISPAGE(pgsz, iDbPage) ){
      continue;
    }
    rc = getPage(pBt, iDbPage, &pDbMemPage);
    if( rc!=SQLITE_OK ) goto autovacuum_out;

................................................................................
    ** allocatePage() routine.
    */
    do{
      if( pFreeMemPage ){
        releasePage(pFreeMemPage);
        pFreeMemPage = 0;
      }
      rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0, 0);
      if( rc!=SQLITE_OK ) goto autovacuum_out;
      assert( iFreePage<=origSize );
    }while( iFreePage>finSize );
    releasePage(pFreeMemPage);
    pFreeMemPage = 0;

    rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage);
................................................................................
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlite3pager_unref() on *ppPage if an error is returned.
**
** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "nearby".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.
**
** If the "exact" parameter is not 0, and the page-number nearby exists 
** anywhere on the free-list, then it is guarenteed to be returned. This
** is only used by auto-vacuum databases when allocating a new table.
*/
static int allocatePage(
  Btree *pBt, 
  MemPage **ppPage, 
  Pgno *pPgno, 
  Pgno nearby,
  u8 exact
){
  MemPage *pPage1;
  int rc;
  int n;     /* Number of pages on the freelist */
  int k;     /* Number of leaves on the trunk of the freelist */

  pPage1 = pBt->pPage1;
  n = get4byte(&pPage1->aData[36]);
  if( n>0 ){
    /* There are pages on the freelist.  Reuse one of those pages. */
    MemPage *pTrunk = 0;
    Pgno iTrunk;
    MemPage *pPrevTrunk = 0;
    u8 searchList = 0; /* If the free-list must be searched for 'nearby' */
    
    /* If the 'exact' parameter was true and a query of the pointer-map
    ** shows that the page 'nearby' is somewhere on the free-list, then
    ** the entire-list will be searched for that page.
    */
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( exact ){
      u8 eType;
      assert( nearby>0 );
      assert( pBt->autoVacuum );
      rc = ptrmapGet(pBt, nearby, &eType, 0);
      if( rc ) return rc;
      if( eType==PTRMAP_FREEPAGE ){
        searchList = 1;
      }
      *pPgno = nearby;
    }
#endif

    /* Decrement the free-list count by 1. Set iTrunk to the index of the
    ** first free-list trunk page. iPrevTrunk is initially 1.
    */
    rc = sqlite3pager_write(pPage1->aData);
    if( rc ) return rc;
    put4byte(&pPage1->aData[36], n-1);

    /* The code within this loop is run only once if the 'searchList' variable
    ** is not true. Otherwise, it runs once for each trunk-page on the
    ** free-list until the page 'nearby' is located.
    */
    do {
      pPrevTrunk = pTrunk;
      if( pPrevTrunk ){
        iTrunk = get4byte(&pPrevTrunk->aData[0]);
      }else{
        iTrunk = get4byte(&pPage1->aData[32]);
      }
      rc = getPage(pBt, iTrunk, &pTrunk);
      if( rc ){
        releasePage(pPrevTrunk);
        return rc;
      }

      /* TODO: This should move to after the loop? */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ){
        releasePage(pTrunk);
        releasePage(pPrevTrunk);
        return rc;
      }

      k = get4byte(&pTrunk->aData[4]);
      if( k==0 && !searchList ){
        /* The trunk has no leaves and the list is not being searched. 
        ** So extract the trunk page itself and use it as the newly 
        ** allocated page */

        assert( pPrevTrunk==0 );
        *pPgno = iTrunk;
        memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
        *ppPage = pTrunk;
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
      }else if( k>pBt->usableSize/4 - 8 ){
        /* Value of k is out of range.  Database corruption */
        return SQLITE_CORRUPT; /* bkpt-CORRUPT */
#ifndef SQLITE_OMIT_AUTOVACUUM
      }else if( searchList && nearby==iTrunk ){
        /* The list is being searched and this trunk page is the page
        ** to allocate, regardless of whether it has leaves.
        */
        assert( *pPgno==iTrunk );
        *ppPage = pTrunk;
        searchList = 0;
        if( k==0 ){
          if( !pPrevTrunk ){
            memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
          }else{
            memcpy(&pPrevTrunk->aData[0], &pTrunk->aData[0], 4);
          }
        }else{
          /* The trunk page is required by the caller but it contains 
          ** pointers to free-list leaves. The first leaf becomes a trunk
          ** page in this case.
          */
          MemPage *pNewTrunk;
          Pgno iNewTrunk = get4byte(&pTrunk->aData[8]);
          rc = getPage(pBt, iNewTrunk, &pNewTrunk);
          if( rc!=SQLITE_OK ){
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          rc = sqlite3pager_write(pNewTrunk->aData);
          if( rc!=SQLITE_OK ){
            releasePage(pNewTrunk);
            releasePage(pTrunk);
            releasePage(pPrevTrunk);
            return rc;
          }
          memcpy(&pNewTrunk->aData[0], &pTrunk->aData[0], 4);
          put4byte(&pNewTrunk->aData[4], k-1);
          memcpy(&pNewTrunk->aData[8], &pTrunk->aData[12], (k-1)*4);
          if( !pPrevTrunk ){
            put4byte(&pPage1->aData[32], iNewTrunk);
          }else{
            put4byte(&pPrevTrunk->aData[0], iNewTrunk);
          }
          releasePage(pNewTrunk);
        }
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
#endif
      }else{
        /* Extract a leaf from the trunk */
        int closest;
        Pgno iPage;
        unsigned char *aData = pTrunk->aData;
        if( nearby>0 ){
          int i, dist;
          closest = 0;
          dist = get4byte(&aData[8]) - nearby;
          if( dist<0 ) dist = -dist;
          for(i=1; i<k; i++){
            int d2 = get4byte(&aData[8+i*4]) - nearby;
            if( d2<0 ) d2 = -d2;
            if( d2<dist ){
              closest = i;
              dist = d2;
            }
          }
        }else{
          closest = 0;
        }

        iPage = get4byte(&aData[8+closest*4]);
        if( !searchList || iPage==nearby ){
          *pPgno = iPage;
          if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
            /* Free page off the end of the file */
            return SQLITE_CORRUPT; /* bkpt-CORRUPT */
          }
          TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
                 ": %d more free pages\n",
                 *pPgno, closest+1, k, pTrunk->pgno, n-1));
          if( closest<k-1 ){
            memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
          }
          put4byte(&aData[4], k-1);
          rc = getPage(pBt, *pPgno, ppPage);

          if( rc==SQLITE_OK ){
            sqlite3pager_dont_rollback((*ppPage)->aData);
            rc = sqlite3pager_write((*ppPage)->aData);
          }
          searchList = 0;
        }
      }
      releasePage(pPrevTrunk);
    }while( searchList );
    releasePage(pTrunk);
  }else{
    /* There are no pages on the freelist, so create a new page at the
    ** end of the file */
    *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;

#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum && PTRMAP_ISPAGE(pBt->pageSize, *pPgno) ){
................................................................................
  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);
    if( rc ) return rc;


  }
#endif

  if( n==0 ){
    /* This is the first free page */
    rc = sqlite3pager_write(pPage->aData);
    if( rc ) return rc;
................................................................................
  pPrior = &pCell[info.iOverflow];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
#ifndef SQLITE_OMIT_AUTOVACUUM
      Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
#endif
      rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl, 0);
#ifndef SQLITE_OMIT_AUTOVACUUM
      /* If the database supports auto-vacuum, and the second or subsequent
      ** overflow page is being allocated, add an entry to the pointer-map
      ** for that page now. The entry for the first overflow page will be
      ** added later, by the insertCell() routine.
      */
      if( pBt->autoVacuum && pgnoPtrmap!=0 && rc==SQLITE_OK ){
................................................................................
    MemPage *pNew;
    if( i<nOld ){
      pNew = apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlite3pager_write(pNew->aData);
    }else{
      rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1], 0);
      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }

................................................................................
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );
  usableSize = pBt->usableSize;
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  brk = get2byte(&data[hdr+5]);
  cdata = pChild->aData;
................................................................................
    /* Must start a transaction first */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
#ifdef SQLITE_OMIT_AUTOVACUUM
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
  if( rc ) return rc;
#else
  if( pBt->autoVacuum ){
    Pgno pgnoMove;      /* Move a page here to make room for the root-page */
    MemPage *pPageMove; /* The page to move to. */














    /* Read the value of meta[3] from the database to determine where the
    ** root page of the new table should go. meta[3] is the largest root-page
    ** created so far, so the new root-page is (meta[3]+1).
    */
    rc = sqlite3BtreeGetMeta(pBt, 4, &pgnoRoot);
    if( rc!=SQLITE_OK ) return rc;
    pgnoRoot++;
................................................................................
    }
    assert( pgnoRoot>=3 );

    /* Allocate a page. The page that currently resides at pgnoRoot will
    ** be moved to the allocated page (unless the allocated page happens
    ** to reside at pgnoRoot).
    */
    rc = allocatePage(pBt, &pPageMove, &pgnoMove, pgnoRoot, 1);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    if( pgnoMove!=pgnoRoot ){
      u8 eType;
      Pgno iPtrPage;
................................................................................
    }
    rc = sqlite3BtreeUpdateMeta(pBt, 4, pgnoRoot);
    if( rc ){
      releasePage(pRoot);
      return rc;
    }
  }else{
    rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1, 0);
    if( rc ) return rc;
  }
#endif
  assert( sqlite3pager_iswriteable(pRoot->aData) );
  zeroPage(pRoot, flags | PTF_LEAF);
  sqlite3pager_unref(pRoot->aData);
  *piTable = (int)pgnoRoot;

#    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.6 2004/11/04 14:30:06 danielk1977 Exp $

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

# Return a string $len characters long. The returned string is $char repeated
# over and over. For example, [make_str abc 8] returns "abcabcab".
proc make_str {char len} {
................................................................................
  # Make sure the integrity check passes with the initial data.
  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}


  foreach delete $delete_order {
    # Delete one set of rows from the table.
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
................................................................................

  # All rows have been deleted. Ensure the file has shrunk to 4 pages.
  do_test autovacuum-1.$tn.3 {
    file_pages
  } {4}
}

# Tests autovacuum-2.* test that root pages are allocated correctly at
# the start of the file.











do_test autovacuum-2.1 {
  for {set i 0} {$i<5} {incr i} {
















    execsql "
      INSERT INTO av1 VALUES('[make_str abc 1000]')



    "



  }









  file_pages 
} {14}

for {set i 5} {$i < 15} {incr i} {
  set tablename "av$i"






  

  do_test autovacuum-2.$i.2 {






    execsql "
      CREATE TABLE $tablename (a);
      SELECT rootpage FROM sqlite_master WHERE name = '$tablename';










    "










  } $i






  do_test autovacuum-2.$i.3 {
    file_pages 
  } [expr $i+10]






  do_test autovacuum-2.$i.4 {
    execsql {
      pragma integrity_check

    }













  } {ok}



}








finish_test

#    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.7 2004/11/05 12:27:03 danielk1977 Exp $

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

# Return a string $len characters long. The returned string is $char repeated
# over and over. For example, [make_str abc 8] returns "abcabcab".
proc make_str {char len} {
................................................................................
  # Make sure the integrity check passes with the initial data.
  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

# set btree_trace 1
  foreach delete $delete_order {
    # Delete one set of rows from the table.
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
................................................................................

  # All rows have been deleted. Ensure the file has shrunk to 4 pages.
  do_test autovacuum-1.$tn.3 {
    file_pages
  } {4}
}

# Tests cases autovacuum-2.* test that root pages are allocated 
# and deallocated correctly at the start of the file. Operation is roughly as
# follows:
#
# autovacuum-2.1.*: Drop the tables that currently exist in the database.
# autovacuum-2.2.*: Create some tables. Ensure that data pages can be
#                   moved correctly to make space for new root-pages.
# autovacuum-2.3.*: Drop one of the tables just created (not the last one),
#                   and check that one of the other tables is moved to
#                   the free root-page location.
# autovacuum-2.4.*: Check that a table can be created correctly when the
#                   root-page it requires is on the free-list.
#
do_test autovacuum-2.1.1 {

  execsql {
    DROP TABLE av1;
  }
} {}
do_test autovacuum-2.1.2 {
  file_pages
} {1}

# Create a table and put some data in it.
do_test autovacuum-2.2.1 {
  execsql {
    CREATE TABLE av1(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3}
do_test autovacuum-2.2.2 {
  execsql "
    INSERT INTO av1 VALUES('[make_str abc 3000]');
    INSERT INTO av1 VALUES('[make_str def 3000]');
    INSERT INTO av1 VALUES('[make_str ghi 3000]');
    INSERT INTO av1 VALUES('[make_str jkl 3000]');
  "
  set ::av1_data [db eval {select * from av1}]
  file_pages
} {15}

# Create another table. Check it is located immediately after the first.
# This test case moves the second page in an over-flow chain.
do_test autovacuum-2.2.3 {
  execsql {
    CREATE TABLE av2(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4}
do_test autovacuum-2.2.4 {
  file_pages
} {16}



# Create another table. Check it is located immediately after the second.
# This test case moves the first page in an over-flow chain.
do_test autovacuum-2.2.5 {
  execsql {
    CREATE TABLE av3(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5}
do_test autovacuum-2.2.6 {
  file_pages
} {17}

# Create another table. Check it is located immediately after the second.
# This test case moves a btree leaf page.
do_test autovacuum-2.2.7 {
  execsql {
    CREATE TABLE av4(x);
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5 6}
do_test autovacuum-2.2.8 {
  file_pages
} {18}
do_test autovacuum-2.2.9 {
  execsql {
    select * from av1
  }
} $av1_data

do_test autovacuum-2.3.1 {
  execsql {
    INSERT INTO av2 SELECT 'av1' || x FROM av1;
    INSERT INTO av3 SELECT 'av2' || x FROM av1;
    INSERT INTO av4 SELECT 'av3' || x FROM av1;
  }
  set ::av2_data [execsql {select x from av2}]
  set ::av3_data [execsql {select x from av3}]
  set ::av4_data [execsql {select x from av4}]
  file_pages
} {54}
do_test autovacuum-2.3.2 {
  execsql {
    DROP TABLE av2;
    SELECT rootpage FROM sqlite_master ORDER BY rootpage;
  }
} {3 4 5}
do_test autovacuum-2.3.3 {
  file_pages

} {41}
do_test autovacuum-2.3.4 {
  execsql {
    SELECT x FROM av3;
  }
} $::av3_data
do_test autovacuum-2.3.5 {
  execsql {

    SELECT x FROM av4;
  }
} $::av4_data

# Drop all the tables in the file. This puts all pages except the first 2
# (the sqlite_master root-page and the first pointer map page) on the 
# free-list.
do_test autovacuum-2.4.1 {
  execsql {
    DROP TABLE av1;
    DROP TABLE av3;
    BEGIN;
    DROP TABLE av4;
  }
  file_pages
} {15}
do_test autovacuum-2.4.2 {
  for {set i 3} {$i<=10} {incr i} {
    execsql "CREATE TABLE av$i (x)"
  }
  file_pages
} {15}
do_test autovacuum-2.4.3 {
  execsql {
    SELECT rootpage FROM sqlite_master ORDER by rootpage
  }
} {3 4 5 6 7 8 9 10}

finish_test