** 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.119 2004/05/09 11:51:39 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.
................................................................................
    return rc;
  }
  sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->pPage1 = 0;
  pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
  pBt->pageSize = SQLITE_PAGE_SIZE;  /* FIX ME - read from header */











  pBt->maxLocal = (pBt->pageSize-10)/4-12;

  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
    pCur->idx--;
    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.
................................................................................
    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;

    }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<n; i++){
          int d2 = get4byte(&aData[8+i*4]) - nearby;
          if( d2<0 ) d2 = -d2;
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      put4byte(&aData[4], n-1);
      *pPgno = get4byte(&aData[8+closest*4]);


      if( closest<k-1 ){
        memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
      }
      put4byte(&pTrunk->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;
    rc = getPage(pBt, *pPgno, ppPage);
    if( rc ) return rc;
    rc = sqlite3pager_write((*ppPage)->aData);

  }
  return rc;
}

/*
** Add a page of the database file to the freelist.
**
................................................................................

  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);

  }else{
    /* Other free pages already exist.  Retrive the first trunk page
    ** of the freelist and find out how many leaves it has. */
    MemPage *pTrunk;
    rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);
    if( rc ) return rc;
    k = get4byte(&pTrunk->aData[4]);
................................................................................
      /* The trunk is full.  Turn the page being freed into a new
      ** trunk page with no leaves. */
      rc = sqlite3pager_write(pPage->aData);
      if( rc ) return rc;
      put4byte(pPage->aData, pTrunk->pgno);
      put4byte(&pPage->aData[4], 0);
      put4byte(&pPage1->aData[32], pPage->pgno);


    }else{
      /* Add the newly freed page as a leaf on the current trunk */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ) return rc;
      put4byte(&pTrunk->aData[4], k+1);
      put4byte(&pTrunk->aData[8+k*4], pPage->pgno);
      sqlite3pager_dont_write(pBt->pPager, pPage->pgno);

    }
    releasePage(pTrunk);
  }
  return rc;
}

/*
................................................................................
static void dropCell(MemPage *pPage, int idx, int sz){
  int j, pc;
  u8 *data;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, pPage->aCell[idx]) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->aCell[idx]>=pPage->aData );
  assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] );
  data = pPage->aData;
  pc = Addr(pPage->aCell[idx]) - Addr(data);
  assert( pc>pPage->hdrOffset && pc+sz<=pPage->pBt->pageSize );
  freeSpace(pPage, pc, sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->aCell[j] = pPage->aCell[j+1];
  }
................................................................................
static void movePage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  int pageSize;
  int ofst;

  assert( pTo->hdrOffset==0 );

  ofst = pFrom->hdrOffset;
  pageSize = pFrom->pBt->pageSize;
  sqliteFree(pTo->aCell);
  memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst);
  memcpy(pTo, pFrom, offsetof(MemPage, aData));
  pFrom->isInit = 0;
  pFrom->aCell = 0;
................................................................................
    uptr x = Addr(pTo->aCell[i]);
    if( x>from && x<from+pageSize-ofst ){
      *((uptr*)&pTo->aCell[i]) = x + to - from;
    }
  }
}

/*
** For debugging...
*/
#if 1
# define TRACE(X)   if( pager3_refinfo_enable ) printf X
#else
# define TRACE(X)
#endif

/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
** of the page that participate in the balancing operation.  NB is the
** total number of pages that participate, including the target page and
** NN neighbors on either side.
**
................................................................................
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */

  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
  */
  pParent = pPage->pParent;
  TRACE(("BALANCE: begin page %d\n", pPage->pgno));
  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
      if( pPage->leaf ){
        /* The table is completely empty */
        relinkCellList(pPage);
        TRACE(("BALANCE: empty table\n"));
      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the BTree by one.
        **
        ** If the root page is page 1, it has less space available than
        ** its child (due to the 100 byte header that occurs at the beginning
        ** of the database fle), so it might not be able to hold all of the 
        ** information currently contained in the child.  If this is the 
        ** case, then do not do the transfer.  Leave page 1 empty except
        ** for the right-pointer to the child page.  The child page becomes
................................................................................
            TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
            TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
          }
        }else{
          memcpy(pPage, pChild, pBt->pageSize);
          pPage->isInit = 0;
          pPage->pParent = 0;
          rc = initPage(pPage, 0);
          assert( rc==SQLITE_OK );
          freePage(pChild);
          TRACE(("BALANCE: transfer child %d into root\n", pChild->pgno));

        }
        reparentChildPages(pPage);
        releasePage(pChild);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pPage);
      TRACE(("BALANCE:  Root page is underfull but that is ok\n"));
      return SQLITE_OK;
    }
    /*
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
................................................................................
    pChild->idxParent = 0;
    pChild->isOverfull = 1;
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;
    extraUnref = pChild;
    TRACE(("BALANCE: Copy root into %d and blance\n", pPage->pgno));




  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  */
  for(i=0; i<nNew; i++){
    reparentChildPages(apNew[i]);
  }
  reparentChildPages(pParent);

  /*
  ** balance the parent page.


  */
  assert( pPage->isInit );
  assert( pParent->isInit );

  pageIntegrity(pPage);
  rc = balance(pParent);
  

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
    if( apCopy[i] ){
................................................................................
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  releasePage(extraUnref);
  TRACE(("BALANCE: Finished with %d\n", pPage->pgno));

  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;



  assert( pPage->isInit );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
  if( rc ) return rc;
  assert( szNew==cellSize(pPage, newCell) );

  if( loc==0 ){
    int szOld;
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    oldCell = pPage->aCell[pCur->idx];
    if( !pPage->leaf ){
      memcpy(&newCell[2], &oldCell[2], 4);
    }
................................................................................
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;


    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    memcpy(tempbuf, &pNext[-2], 4);
    put4byte(&pNext[-2], pgnoChild);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);
    rc = balance(pPage);
    if( rc ) return rc;
    memcpy(&pNext[-2], tempbuf, 4);
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{


    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    rc = balance(pPage);
  }
  moveToRoot(pCur);
  return rc;
}

................................................................................
  if( !pPage->leaf ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), pPage->pParent, 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else{
    zeroPage(pPage, pPage->aData[0]);
  }
  releasePage(pPage);
  return rc;
}

/*
** Delete all information from a single table in the database.
................................................................................
  IntegrityCk *pCheck,  /* Integrity checking context */
  int isFreeList,       /* True for a freelist.  False for overflow page list */
  int iPage,            /* Page number for first page in the list */
  int N,                /* Expected number of pages in the list */
  char *zContext        /* Context for error messages */
){
  int i;


  char zMsg[100];
  while( N-- > 0 ){
    unsigned char *pOvfl;
    if( iPage<1 ){
      sprintf(zMsg, "%d pages missing from overflow list", N+1);

      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      sprintf(zMsg, "failed to get page %d", iPage);
      checkAppendMsg(pCheck, zContext, zMsg);
................................................................................
  /* Check that the page exists
  */
  cur.pBt = pBt = pCheck->pBt;
  maxLocal = pBt->maxLocal;
  pageSize = pBt->pageSize;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;
  sprintf(zContext, "On tree page %d: ", iPage);
  if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
    sprintf(zMsg, "unable to get the page. error code=%d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    return 0;
  }
  if( (rc = initPage(pPage, pParent))!=0 ){
    sprintf(zMsg, "initPage() returns error code %d", rc);
................................................................................
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = pPage->aCell[i];
    u64 nKey, nData;
    int sz, nHeader;

    /* Check payload overflow pages
    */

    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    sz = nData;
    if( !pPage->intKey ) sz += nKey;
    if( sz>maxLocal ){
      int nPage = (sz - maxLocal + pageSize - 5)/(pageSize - 4);
      checkList(pCheck, 0, get4byte(&pCell[nHeader+maxLocal]),nPage,zContext);
    }

** 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.120 2004/05/09 20:40:11 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.
................................................................................
    return rc;
  }
  sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
  pBt->pCursor = 0;
  pBt->pPage1 = 0;
  pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
  pBt->pageSize = SQLITE_PAGE_SIZE;  /* FIX ME - read from header */

  /* maxLocal is the maximum amount of payload to store locally for
  ** a cell.  Make sure it is small enough so that at least MN_CELLS_PER_PAGE
  ** will fit on one page.  We assume a 10-byte page header.  Besides
  ** the payload, the cell must store:
  **     2-byte pointer to next cell
  **     4-byte child pointer
  **     9-byte nKey value
  **     4-byte nData value
  **     4-byte overflow page pointer
  */
  pBt->maxLocal = (pBt->pageSize-10)/MN_CELLS_PER_PAGE - 23;
  assert( pBt->maxLocal + 23 <= MX_CELL_SIZE );
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/
................................................................................
    pCur->idx--;
    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 ){ printf 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.
................................................................................
    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{
      /* 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]);
      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;
    rc = getPage(pBt, *pPgno, ppPage);
    if( rc ) return rc;
    rc = sqlite3pager_write((*ppPage)->aData);
    TRACE(("ALLOCATE: %d from end of file\n", *pPgno));
  }
  return rc;
}

/*
** Add a page of the database file to the freelist.
**
................................................................................

  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);
    TRACE(("FREE-PAGE: %d first\n", pPage->pgno));
  }else{
    /* Other free pages already exist.  Retrive the first trunk page
    ** of the freelist and find out how many leaves it has. */
    MemPage *pTrunk;
    rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);
    if( rc ) return rc;
    k = get4byte(&pTrunk->aData[4]);
................................................................................
      /* The trunk is full.  Turn the page being freed into a new
      ** trunk page with no leaves. */
      rc = sqlite3pager_write(pPage->aData);
      if( rc ) return rc;
      put4byte(pPage->aData, pTrunk->pgno);
      put4byte(&pPage->aData[4], 0);
      put4byte(&pPage1->aData[32], pPage->pgno);
      TRACE(("FREE-PAGE: %d new trunk page replacing %d\n",
              pPage->pgno, pTrunk->pgno));
    }else{
      /* Add the newly freed page as a leaf on the current trunk */
      rc = sqlite3pager_write(pTrunk->aData);
      if( rc ) return rc;
      put4byte(&pTrunk->aData[4], k+1);
      put4byte(&pTrunk->aData[8+k*4], pPage->pgno);
      sqlite3pager_dont_write(pBt->pPager, pPage->pgno);
      TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
    }
    releasePage(pTrunk);
  }
  return rc;
}

/*
................................................................................
static void dropCell(MemPage *pPage, int idx, int sz){
  int j, pc;
  u8 *data;
  assert( idx>=0 && idx<pPage->nCell );
  assert( sz==cellSize(pPage, pPage->aCell[idx]) );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  assert( pPage->aCell[idx]>=pPage->aData );
  assert( pPage->aCell[idx]<=&pPage->aData[pPage->pBt->pageSize-sz] );
  data = pPage->aData;
  pc = Addr(pPage->aCell[idx]) - Addr(data);
  assert( pc>pPage->hdrOffset && pc+sz<=pPage->pBt->pageSize );
  freeSpace(pPage, pc, sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->aCell[j] = pPage->aCell[j+1];
  }
................................................................................
static void movePage(MemPage *pTo, MemPage *pFrom){
  uptr from, to;
  int i;
  int pageSize;
  int ofst;

  assert( pTo->hdrOffset==0 );
  assert( pFrom->isInit );
  ofst = pFrom->hdrOffset;
  pageSize = pFrom->pBt->pageSize;
  sqliteFree(pTo->aCell);
  memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst);
  memcpy(pTo, pFrom, offsetof(MemPage, aData));
  pFrom->isInit = 0;
  pFrom->aCell = 0;
................................................................................
    uptr x = Addr(pTo->aCell[i]);
    if( x>from && x<from+pageSize-ofst ){
      *((uptr*)&pTo->aCell[i]) = x + to - from;
    }
  }
}










/*
** The following parameters determine how many adjacent pages get involved
** in a balancing operation.  NN is the number of neighbors on either side
** of the page that participate in the balancing operation.  NB is the
** total number of pages that participate, including the target page and
** NN neighbors on either side.
**
................................................................................
  int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
  u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)];  /* Space for apCopy[] */

  /* 
  ** Return without doing any work if pPage is neither overfull nor
  ** underfull.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;
  if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){
    relinkCellList(pPage);
    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be balanced.  If there is no parent,
  ** it means this page is the root page and special rules apply.
  */
  pParent = pPage->pParent;

  if( pParent==0 ){
    Pgno pgnoChild;
    MemPage *pChild;
    assert( pPage->isInit );
    if( pPage->nCell==0 ){
      if( pPage->leaf ){
        /* The table is completely empty */
        relinkCellList(pPage);
        TRACE(("BALANCE: empty table %d\n", pPage->pgno));
      }else{
        /* The root page is empty but has one child.  Transfer the
        ** information from that one child into the root page if it 
        ** will fit.  This reduces the depth of the tree by one.
        **
        ** If the root page is page 1, it has less space available than
        ** its child (due to the 100 byte header that occurs at the beginning
        ** of the database fle), so it might not be able to hold all of the 
        ** information currently contained in the child.  If this is the 
        ** case, then do not do the transfer.  Leave page 1 empty except
        ** for the right-pointer to the child page.  The child page becomes
................................................................................
            TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
          }else{
            /* The child has more information that will fit on the root.
            ** The tree is already balanced.  Do nothing. */
            TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
          }
        }else{
          memcpy(pPage->aData, pChild->aData, pBt->pageSize);
          pPage->isInit = 0;
          pPage->pParent = 0;
          rc = initPage(pPage, 0);
          assert( rc==SQLITE_OK );
          freePage(pChild);
          TRACE(("BALANCE: transfer child %d into root %d\n",
                  pChild->pgno, pPage->pgno));
        }
        reparentChildPages(pPage);
        releasePage(pChild);
      }
      return SQLITE_OK;
    }
    if( !pPage->isOverfull ){
      /* It is OK for the root page to be less than half full.
      */
      relinkCellList(pPage);
      TRACE(("BALANCE: root page %d is low - no changes\n", pPage->pgno));
      return SQLITE_OK;
    }
    /*
    ** If we get to here, it means the root page is overfull.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
................................................................................
    pChild->idxParent = 0;
    pChild->isOverfull = 1;
    zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
    put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno);
    pParent = pPage;
    pPage = pChild;
    extraUnref = pChild;
    TRACE(("BALANCE: copy root %d into %d and balance %d\n",
            pParent->pgno, pPage->pgno, pPage->pgno));
  }else{
    TRACE(("BALANCE: begin page %d child of %d\n",
            pPage->pgno, pParent->pgno));
  }
  rc = sqlite3pager_write(pParent->aData);
  if( rc ) return rc;
  assert( pParent->isInit );
  
  /*
  ** Find the cell in the parent page whose left child points back
................................................................................
  */
  for(i=0; i<nNew; i++){
    reparentChildPages(apNew[i]);
  }
  reparentChildPages(pParent);

  /*
  ** Balance the parent page.  Note that the current page (pPage) might
  ** have been added to the freelist is it might no longer be initialized.
  ** But the parent page will always be initialized.
  */

  assert( pParent->isInit );
  /* assert( pPage->isInit ); // No! pPage might have been added to freelist */
  /* pageIntegrity(pPage);    // No! pPage might have been added to freelist */ 
  rc = balance(pParent);
  

  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  for(i=0; i<nOld; i++){
    releasePage(apOld[i]);
    if( apCopy[i] ){
................................................................................
    }
  }
  for(i=0; i<nNew; i++){
    releasePage(apNew[i]);
  }
  releasePage(pParent);
  releasePage(extraUnref);
  TRACE(("BALANCE: finished with %d: old=%d new=%d cells=%d\n",
          pPage->pgno, nOld, nNew, nCell));
  return rc;
}

/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
................................................................................
  }
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
          pCur->pgnoRoot, nKey, nData, pPage->pgno,
          loc==0 ? "overwrite" : "new entry"));
  assert( pPage->isInit );
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
  if( rc ) return rc;
  assert( szNew==cellSize(pPage, newCell) );
  assert( szNew<=sizeof(newCell) );
  if( loc==0 ){
    int szOld;
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    oldCell = pPage->aCell[pCur->idx];
    if( !pPage->leaf ){
      memcpy(&newCell[2], &oldCell[2], 4);
    }
................................................................................
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc!=SQLITE_OK ){
      if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
      return rc;
    }
    rc = sqlite3pager_write(leafCur.pPage->aData);
    if( rc ) return rc;
    TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    pNext = leafCur.pPage->aCell[leafCur.idx];
    szNext = cellSize(leafCur.pPage, pNext);
    memcpy(tempbuf, &pNext[-2], 4);
    put4byte(&pNext[-2], pgnoChild);
    insertCell(pPage, pCur->idx, &pNext[-4], szNext+4);
    rc = balance(pPage);
    if( rc ) return rc;
    memcpy(&pNext[-2], tempbuf, 4);
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSize(pPage, pCell));
    rc = balance(pPage);
  }
  moveToRoot(pCur);
  return rc;
}

................................................................................
  if( !pPage->leaf ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), pPage->pParent, 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else{
    zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
  }
  releasePage(pPage);
  return rc;
}

/*
** Delete all information from a single table in the database.
................................................................................
  IntegrityCk *pCheck,  /* Integrity checking context */
  int isFreeList,       /* True for a freelist.  False for overflow page list */
  int iPage,            /* Page number for first page in the list */
  int N,                /* Expected number of pages in the list */
  char *zContext        /* Context for error messages */
){
  int i;
  int expected = N;
  int iFirst = iPage;
  char zMsg[100];
  while( N-- > 0 ){
    unsigned char *pOvfl;
    if( iPage<1 ){
      sprintf(zMsg, "%d of %d pages missing from overflow list starting at %d",
          N+1, expected, iFirst);
      checkAppendMsg(pCheck, zContext, zMsg);
      break;
    }
    if( checkRef(pCheck, iPage, zContext) ) break;
    if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
      sprintf(zMsg, "failed to get page %d", iPage);
      checkAppendMsg(pCheck, zContext, zMsg);
................................................................................
  /* Check that the page exists
  */
  cur.pBt = pBt = pCheck->pBt;
  maxLocal = pBt->maxLocal;
  pageSize = pBt->pageSize;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage, zParentContext) ) return 0;

  if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
    sprintf(zMsg, "unable to get the page. error code=%d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    return 0;
  }
  if( (rc = initPage(pPage, pParent))!=0 ){
    sprintf(zMsg, "initPage() returns error code %d", rc);
................................................................................
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = pPage->aCell[i];
    u64 nKey, nData;
    int sz, nHeader;

    /* Check payload overflow pages
    */
    sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
    parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader);
    sz = nData;
    if( !pPage->intKey ) sz += nKey;
    if( sz>maxLocal ){
      int nPage = (sz - maxLocal + pageSize - 5)/(pageSize - 4);
      checkList(pCheck, 0, get4byte(&pCell[nHeader+maxLocal]),nPage,zContext);
    }

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.32 2004/05/09 00:40:52 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){

  static struct {
     char *zName;
     Tcl_CmdProc *xProc;
  } aCmd[] = {
     { "btree_open",               (Tcl_CmdProc*)btree_open               },
     { "btree_close",              (Tcl_CmdProc*)btree_close              },
     { "btree_begin_transaction",  (Tcl_CmdProc*)btree_begin_transaction  },
................................................................................
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,


     TCL_LINK_INT);
  return TCL_OK;
}

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.33 2004/05/09 20:40:11 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){
  extern int sqlite3_btree_trace;
  static struct {
     char *zName;
     Tcl_CmdProc *xProc;
  } aCmd[] = {
     { "btree_open",               (Tcl_CmdProc*)btree_open               },
     { "btree_close",              (Tcl_CmdProc*)btree_close              },
     { "btree_begin_transaction",  (Tcl_CmdProc*)btree_begin_transaction  },
................................................................................
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  Tcl_LinkVar(interp, "btree_trace", (char*)&sqlite3_btree_trace,
     TCL_LINK_INT);
  return TCL_OK;
}

#    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 script is btree database backend
#
# $Id: btree2.test,v 1.11 2004/05/09 00:40:52 drh Exp $


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

if {[info commands btree_open]!=""} {

................................................................................
#
# An explanation for what all these tables are used for is provided below.
#
do_test btree2-1.1 {
  expr srand(1)
  file delete -force test2.bt
  file delete -force test2.bt-journal
  set ::b [btree_open test2.bt]
  btree_begin_transaction $::b
  btree_create_table $::b



} {3}
do_test btree2-1.2 {
  btree_create_table $::b
} {4}
do_test btree2-1.3 {
  btree_create_table $::b
} {5}
do_test btree2-1.4 {
  btree_create_table $::b
} {6}
do_test btree2-1.5 {
  set ::c2 [btree_cursor $::b 2 1]
  btree_insert $::c2 {one} {1}

  btree_delete $::c2
  btree_close_cursor $::c2
  btree_commit $::b
  btree_integrity_check $::b 2 3 4 5 6
} {}

# This test module works by making lots of pseudo-random changes to a
# database while simultaneously maintaining an invariant on that database.
# Periodically, the script does a sanity check on the database and verifies
# that the invariant is satisfied.
#
................................................................................
  return [string range $r 0 [expr {$len-1}]]
}

# Verify the invariants on the database.  Return an empty string on 
# success or an error message if something is amiss.
#
proc check_invariants {} {
  set ck [btree_integrity_check $::b 2 3 4 5 6]
  if {$ck!=""} {
    puts "\n*** SANITY:\n$ck"
    exit
    return $ck
  }
  btree_move_to $::c3 {}
  btree_move_to $::c4 {}
................................................................................
# from the descriptor table.  Each changes begins with a random key.
# the entry with that key is put in the foreground table with probability
# $I and it is put in background with probability (1.0-$I).  It gets
# a long key with probability $K and long data with probability $D.  
# 
set chngcnt 0
proc random_changes {n I K D} {

  btree_move_to $::c2 N
  set N [btree_data $::c2]
  btree_move_to $::c2 L
  set L [btree_data $::c2]
  set LM1 [expr {$L-1}]
  set total [expr {int($N*$n)}]
  set format %0${L}d
  for {set i 0} {$i<$total} {incr i} {
    set k [expr {int(rand()*$N)+1}]
    set insert [expr {rand()<=$I}]
    set longkey [expr {rand()<=$K}]
    set longdata [expr {rand()<=$D}]
    # incr ::chngcnt
    # if {$::chngcnt==251} {btree_tree_dump $::b 3} 
    # puts "CHANGE $::chngcnt: $k $insert $longkey $longdata"
    if {$longkey} {
      set x [expr {rand()}]
      set keylen [expr {int($x*$x*$x*$x*3000)+10}]
    } else {
      set keylen $L
    }
    set key [make_payload $k $L $keylen]
................................................................................
      if {[string match $basekey* [btree_key $::c4]]} {
        btree_delete $::c4
      }
    }
    if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
    if {$kx==$k} {
      btree_delete $::c4











    }
    if {$insert} {
      btree_insert $::c3 $key $data
    } else {
      btree_insert $::c4 $key $data
    }
    if {$longkey} {
................................................................................
      btree_delete $::c5
    }
    if {$longdata} {
      btree_insert $::c6 $basekey $datalen
    } elseif {[btree_move_to $::c6 $basekey]==0} {
      btree_delete $::c6
    }
    # set ck [btree_integrity_check $::b 2 3 4 5 6]
    # if {$ck!=""} {
    #   puts "\nSANITY CHECK FAILED!\n$ck"
    #   exit
    # }
    # puts "PAGE 3:"; btree_page_dump $::b 3
    # puts "PAGE 4:"; btree_page_dump $::b 4




  }
}

# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
................................................................................
    btree_close_cursor $::c5
    btree_close_cursor $::c6
    lindex [btree_pager_stats $::b] 1
  } {0}
  do_test btree2-$testno.7 {
    btree_close $::b
  } {}
after 100
  # For each database size, run various changes tests.
  #
  set num2 1
  foreach {n I K D} {
    0.5 0.5 0.1 0.1
    1.0 0.2 0.1 0.1
    1.0 0.8 0.1 0.1
................................................................................
    2.0 1.0 0.1 0.1
    2.0 0.0 0.0 0.0
    2.0 1.0 0.0 0.0
  } {
    set testid btree2-$testno.8.$num2
    set hash [md5file test2.bt]
    do_test $testid.0 {
      set ::b [btree_open test2.bt]
      set ::c2 [btree_cursor $::b 2 1]
      set ::c3 [btree_cursor $::b 3 1]
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
................................................................................
    for {set i 2} {$i<=6} {incr i} {
      if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt}
    }
    do_test $testid.1 {
      btree_begin_transaction $::b
      lindex [btree_pager_stats $::b] 1
    } $cnt
    # exec cp test2.bt test2.bt.bu1
    do_test $testid.2 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.3 {
      check_invariants
    } {}
    do_test $testid.4 {
................................................................................
      btree_close_cursor $::c3
      btree_close_cursor $::c4
      btree_close_cursor $::c5
      btree_close_cursor $::c6
      btree_rollback $::b
      md5file test2.bt
    } $hash
    # exec cp test2.bt test2.bt.bu2
    btree_begin_transaction $::b
    set ::c2 [btree_cursor $::b 2 1]
    set ::c3 [btree_cursor $::b 3 1]
    set ::c4 [btree_cursor $::b 4 1]
    set ::c5 [btree_cursor $::b 5 1]
    set ::c6 [btree_cursor $::b 6 1]

    do_test $testid.5 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.6 {
      check_invariants
    } {}
    do_test $testid.7 {
................................................................................
      btree_close_cursor $::c4
      btree_close_cursor $::c5
      btree_close_cursor $::c6
      lindex [btree_pager_stats $::b] 1
    } {0}
    do_test $testid.9 {
      btree_close $::b
      set ::b [btree_open test2.bt]
      set ::c2 [btree_cursor $::b 2 1]
      set ::c3 [btree_cursor $::b 3 1]
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
................................................................................
    } {0}
    do_test $testid.11 {
      btree_close $::b
    } {}
    incr num2
  }
  incr testno
  set ::b [btree_open test2.bt]
}  

# Testing is complete.  Shut everything down.
#
do_test btree-999.1 {
  lindex [btree_pager_stats $::b] 1
} {0}

#    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 script is btree database backend
#
# $Id: btree2.test,v 1.12 2004/05/09 20:40:11 drh Exp $


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

if {[info commands btree_open]!=""} {

................................................................................
#
# An explanation for what all these tables are used for is provided below.
#
do_test btree2-1.1 {
  expr srand(1)
  file delete -force test2.bt
  file delete -force test2.bt-journal
  set ::b [btree_open test2.bt 2000 0]
  btree_begin_transaction $::b
  btree_create_table $::b 0
} {2}
do_test btree2-1.2 {
  btree_create_table $::b 0
} {3}
do_test btree2-1.3 {
  btree_create_table $::b 0
} {4}
do_test btree2-1.4 {
  btree_create_table $::b 0
} {5}
do_test btree2-1.5 {
  btree_create_table $::b 0
} {6}
do_test btree2-1.6 {
  set ::c2 [btree_cursor $::b 2 1]
  btree_insert $::c2 {one} {1}
  btree_move_to $::c2 {one}
  btree_delete $::c2
  btree_close_cursor $::c2
  btree_commit $::b
  btree_integrity_check $::b 1 2 3 4 5 6
} {}

# This test module works by making lots of pseudo-random changes to a
# database while simultaneously maintaining an invariant on that database.
# Periodically, the script does a sanity check on the database and verifies
# that the invariant is satisfied.
#
................................................................................
  return [string range $r 0 [expr {$len-1}]]
}

# Verify the invariants on the database.  Return an empty string on 
# success or an error message if something is amiss.
#
proc check_invariants {} {
  set ck [btree_integrity_check $::b 1 2 3 4 5 6]
  if {$ck!=""} {
    puts "\n*** SANITY:\n$ck"
    exit
    return $ck
  }
  btree_move_to $::c3 {}
  btree_move_to $::c4 {}
................................................................................
# from the descriptor table.  Each changes begins with a random key.
# the entry with that key is put in the foreground table with probability
# $I and it is put in background with probability (1.0-$I).  It gets
# a long key with probability $K and long data with probability $D.  
# 
set chngcnt 0
proc random_changes {n I K D} {
  global chngcnt
  btree_move_to $::c2 N
  set N [btree_data $::c2]
  btree_move_to $::c2 L
  set L [btree_data $::c2]
  set LM1 [expr {$L-1}]
  set total [expr {int($N*$n)}]
  set format %0${L}d
  for {set i 0} {$i<$total} {incr i} {
    set k [expr {int(rand()*$N)+1}]
    set insert [expr {rand()<=$I}]
    set longkey [expr {rand()<=$K}]
    set longdata [expr {rand()<=$D}]



    if {$longkey} {
      set x [expr {rand()}]
      set keylen [expr {int($x*$x*$x*$x*3000)+10}]
    } else {
      set keylen $L
    }
    set key [make_payload $k $L $keylen]
................................................................................
      if {[string match $basekey* [btree_key $::c4]]} {
        btree_delete $::c4
      }
    }
    if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
    if {$kx==$k} {
      btree_delete $::c4
    }
    # For debugging - change the "0" to "1" to integrity check after
    # every change.
    if 0 {
      incr chngcnt
      puts check----$chngcnt
      set ck [btree_integrity_check $::b 1 2 3 4 5 6]
      if {$ck!=""} {
         puts "\nSANITY CHECK FAILED!\n$ck"
         exit
       }
    }
    if {$insert} {
      btree_insert $::c3 $key $data
    } else {
      btree_insert $::c4 $key $data
    }
    if {$longkey} {
................................................................................
      btree_delete $::c5
    }
    if {$longdata} {
      btree_insert $::c6 $basekey $datalen
    } elseif {[btree_move_to $::c6 $basekey]==0} {
      btree_delete $::c6
    }
    # For debugging - change the "0" to "1" to integrity check after
    # every change.
    if 0 {
      incr chngcnt
      puts check----$chngcnt
      set ck [btree_integrity_check $::b 1 2 3 4 5 6]
      if {$ck!=""} {
         puts "\nSANITY CHECK FAILED!\n$ck"
         exit
       }
    }
  }
}

# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
................................................................................
    btree_close_cursor $::c5
    btree_close_cursor $::c6
    lindex [btree_pager_stats $::b] 1
  } {0}
  do_test btree2-$testno.7 {
    btree_close $::b
  } {}

  # For each database size, run various changes tests.
  #
  set num2 1
  foreach {n I K D} {
    0.5 0.5 0.1 0.1
    1.0 0.2 0.1 0.1
    1.0 0.8 0.1 0.1
................................................................................
    2.0 1.0 0.1 0.1
    2.0 0.0 0.0 0.0
    2.0 1.0 0.0 0.0
  } {
    set testid btree2-$testno.8.$num2
    set hash [md5file test2.bt]
    do_test $testid.0 {
      set ::b [btree_open test2.bt 2000 0]
      set ::c2 [btree_cursor $::b 2 1]
      set ::c3 [btree_cursor $::b 3 1]
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
................................................................................
    for {set i 2} {$i<=6} {incr i} {
      if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt}
    }
    do_test $testid.1 {
      btree_begin_transaction $::b
      lindex [btree_pager_stats $::b] 1
    } $cnt

    do_test $testid.2 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.3 {
      check_invariants
    } {}
    do_test $testid.4 {
................................................................................
      btree_close_cursor $::c3
      btree_close_cursor $::c4
      btree_close_cursor $::c5
      btree_close_cursor $::c6
      btree_rollback $::b
      md5file test2.bt
    } $hash

    btree_begin_transaction $::b
    set ::c2 [btree_cursor $::b 2 1]
    set ::c3 [btree_cursor $::b 3 1]
    set ::c4 [btree_cursor $::b 4 1]
    set ::c5 [btree_cursor $::b 5 1]
    set ::c6 [btree_cursor $::b 6 1]
#if {$testid=="btree2-3.8.4"} {set btree_trace 1}
    do_test $testid.5 [subst {
      random_changes $n $I $K $D
    }] {}
    do_test $testid.6 {
      check_invariants
    } {}
    do_test $testid.7 {
................................................................................
      btree_close_cursor $::c4
      btree_close_cursor $::c5
      btree_close_cursor $::c6
      lindex [btree_pager_stats $::b] 1
    } {0}
    do_test $testid.9 {
      btree_close $::b
      set ::b [btree_open test2.bt 2000 0]
      set ::c2 [btree_cursor $::b 2 1]
      set ::c3 [btree_cursor $::b 3 1]
      set ::c4 [btree_cursor $::b 4 1]
      set ::c5 [btree_cursor $::b 5 1]
      set ::c6 [btree_cursor $::b 6 1]
      check_invariants
    } {}
................................................................................
    } {0}
    do_test $testid.11 {
      btree_close $::b
    } {}
    incr num2
  }
  incr testno
  set ::b [btree_open test2.bt 2000 0]
}  

# Testing is complete.  Shut everything down.
#
do_test btree-999.1 {
  lindex [btree_pager_stats $::b] 1
} {0}

# 2001 November 22
#
# 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 script is btree database backend
#
# In particular, this file tests a small part of the Delete logic
# for the BTree backend.  When a row is deleted from a table, the
# cursor is suppose to be left pointing at either the previous or
# next entry in that table.  If the cursor is left pointing at the
# next entry, then the next Next operation is ignored.  So the 
# sequence of operations (Delete, Next) should always leave the
# cursor pointing at the first entry past the one that was deleted.
# This test is designed to verify that behavior.
#
# $Id: btree3.test,v 1.2 2002/12/04 13:40:27 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt]
btree_begin_transaction $::b1

# Insert a few one records
#
set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data
for {set k 2} {$k<=10} {incr k} {
  for {set j 1} {$j<=$k} {incr j} {
    set jkey [format %02d $j]
    btree_clear_table $::b1 2
    set ::c1 [btree_cursor $::b1 2 1]
    for {set i 1} {$i<=$k} {incr i} {
      set key [format %02d $i]
      do_test btree3-$k.$j.1.$i {
        btree_insert $::c1 $::key $::data
      } {}
      # btree_tree_dump $::b1 2
    }
    do_test btree3-$k.$j.2 {
      btree_move_to $::c1 $::jkey
      btree_key $::c1
    } $::jkey
    do_test btree3-$k.$j.3 {
      btree_delete $::c1
    } {}
    if {$j<$k} {
      do_test btree3-$k.$j.4 {
        btree_next $::c1
        btree_key $::c1
      } [format %02d [expr $j+1]]
    }
    if {$j>1} {
      do_test btree3-$k.$j.5 {
        btree_prev $::c1
        btree_key $::c1
      } [format %02d [expr $j-1]]
    }
    btree_close_cursor $::c1
  }
}

btree_rollback $::b1    
btree_pager_ref_dump $::b1
btree_close $::b1

} ;# end if( not mem: and has pager_open command );

finish_test

# 2001 November 22
#
# 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 script is btree database backend
#
# In particular, this file tests a small part of the Delete logic
# for the BTree backend.  When a row is deleted from a table, the
# cursor is suppose to be left pointing at either the previous or
# next entry in that table.  If the cursor is left pointing at the
# next entry, then the next Next operation is ignored.  So the 
# sequence of operations (Delete, Next) should always leave the
# cursor pointing at the first entry past the one that was deleted.
# This test is designed to verify that behavior.
#
# $Id: btree3rb.test,v 1.1 2003/04/20 23:45:23 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
set b1 [btree_open :memory:]
btree_begin_transaction $::b1

# Insert a few one records
#
set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data
for {set k 2} {$k<=20} {incr k} {
  for {set j 1} {$j<=$k} {incr j} {
    set jkey [format %02d $j]
    btree_clear_table $::b1 2
    set ::c1 [btree_cursor $::b1 2 1]
    for {set i 1} {$i<=$k} {incr i} {
      set key [format %02d $i]
      do_test btree3rb-$k.$j.1.$i {
        btree_insert $::c1 $::key $::data
      } {}
      # btree_tree_dump $::b1 2
    }
    do_test btree3rb-$k.$j.2 {
      btree_move_to $::c1 $::jkey
      btree_key $::c1
    } $::jkey
    do_test btree3rb-$k.$j.3 {
      btree_delete $::c1
    } {}
    if {$j<$k} {
      do_test btree3rb-$k.$j.4 {
        btree_next $::c1
        btree_key $::c1
      } [format %02d [expr $j+1]]
    }
    if {$j>1} {
      do_test btree3rb-$k.$j.5 {
        btree_prev $::c1
        btree_key $::c1
      } [format %02d [expr $j-1]]
    }
    btree_close_cursor $::c1
  }
}

btree_rollback $::b1    
#btree_pager_ref_dump $::b1
btree_close $::b1

} ;# end if( not mem: and has pager_open command );

finish_test

# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# This file focuses on testing the sqliteBtreeNext() and 
# sqliteBtreePrevious() procedures and making sure they are able
# to step through an entire table from either direction.
#
# $Id: btree4.test,v 1.1 2002/12/04 13:40:27 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt]
btree_begin_transaction $::b1




set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data

# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# This file focuses on testing the sqliteBtreeNext() and 
# sqliteBtreePrevious() procedures and making sure they are able
# to step through an entire table from either direction.
#
# $Id: btree4.test,v 1.2 2004/05/09 20:40:12 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
file delete -force test1.bt
file delete -force test1.bt-journal
set b1 [btree_open test1.bt 2000 0]
btree_begin_transaction $b1
do_test btree4-0.1 {
  btree_create_table $b1 0
} 2

set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data

# 2002 December 03
#
# 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 script is btree database backend
#
# This file focuses on testing the sqliteBtreeNext() and 
# sqliteBtreePrevious() procedures and making sure they are able
# to step through an entire table from either direction.
#
# $Id: btree4rb.test,v 1.1 2003/04/20 23:45:23 drh Exp $


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

if {[info commands btree_open]!=""} {

# Open a test database.
#
set b1 [btree_open :memory:]
btree_begin_transaction $::b1

set data {abcdefghijklmnopqrstuvwxyz0123456789}
append data $data
append data $data
append data $data
append data $data

foreach N {10 100 1000} {
  btree_clear_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  do_test btree4rb-$N.1 {
    for {set i 1} {$i<=$N} {incr i} {
      btree_insert $::c1 [format k-%05d $i] $::data-$i
    }
    btree_first $::c1
    btree_key $::c1
  } {k-00001}
  do_test btree4rb-$N.2 {
    btree_data $::c1
  } $::data-1
  for {set i 2} {$i<=$N} {incr i} {
    do_test btree-$N.3.$i.1 {
      btree_next $::c1
    } 0
    do_test btree-$N.3.$i.2 {
      btree_key $::c1
    } [format k-%05d $i]
    do_test btree-$N.3.$i.3 {
      btree_data $::c1
    } $::data-$i
  }
  do_test btree4rb-$N.4 {
    btree_next $::c1
  } 1
  do_test btree4rb-$N.5 {
    btree_last $::c1
  } 0
  do_test btree4rb-$N.6 {
    btree_key $::c1
  } [format k-%05d $N]
  do_test btree4rb-$N.7 {
    btree_data $::c1
  } $::data-$N
  for {set i [expr {$N-1}]} {$i>=1} {incr i -1} {
    do_test btree4rb-$N.8.$i.1 {
      btree_prev $::c1
    } 0
    do_test btree4rb-$N.8.$i.2 {
      btree_key $::c1
    } [format k-%05d $i]
    do_test btree4rb-$N.8.$i.3 {
      btree_data $::c1
    } $::data-$i
  }
  do_test btree4rb-$N.9 {
    btree_prev $::c1
  } 1
  btree_close_cursor $::c1
}

btree_rollback $::b1    
btree_close $::b1

} ;# end if( not mem: and has pager_open command );

finish_test