** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.14 2001/06/24 20:39:41 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.
................................................................................
** for additional information.)  Page 0 does not exist and a page
** number of 0 is used to mean "no such page".
*/
struct PageOne {
  char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */
  int iMagic;              /* Integer to verify correct byte order */
  Pgno freeList;           /* First free page in a list of all free pages */

  int aMeta[SQLITE_N_BTREE_META];  /* User defined integers */
};

/*
** Each database page has a header that is an instance of this
** structure.
**
** PageHdr.firstFree is 0 if there is no free space on this page.
................................................................................
** The maximum amount of payload (in bytes) that can be stored locally for
** a database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
**
** This number is chosen so that at least 4 cells will fit on every page.
*/
#define MX_LOCAL_PAYLOAD \
  ((SQLITE_PAGE_SIZE-sizeof(PageHdr))/4-(sizeof(CellHdr)+sizeof(Pgno)))

/*
** Data on a database page is stored as a linked list of Cell structures.
** Both the key and the data are stored in aPayload[].  The key always comes
** first.  The aPayload[] field grows as necessary to hold the key and data,
** up to a maximum of MX_LOCAL_PAYLOAD bytes.  If the size of the key and
** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the
................................................................................
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

  pc = sizeof(PageHdr);
  pPage->u.hdr.firstCell = pc;
  memcpy(newPage, pPage->u.aDisk, pc);
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = (Cell*)&pPage->apCell[i];

    /* This routine should never be called on an overfull page.  The
    ** following asserts verify that constraint. */
    assert( Addr(pCell) > Addr(pPage) );
    assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE );

    n = cellSize(pCell);
    pCell->h.iNext = i<pPage->nCell-1 ? pc + n : 0;
    memcpy(&newPage[pc], pCell, n);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
    pc += n;
  }
  assert( pPage->nFree==SQLITE_PAGE_SIZE-pc );
  memcpy(pPage->u.aDisk, newPage, pc);



  pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->u.hdr.firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}

................................................................................
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

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

/*
................................................................................
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset += a;
    zBuf += a;
    amt -= a;
  }
  if( amt>0 ){
    nextPage = pCur->pPage->apCell[pCur->idx]->ovfl;
  }
  while( amt>0 && nextPage ){
................................................................................
    nextPage = pOvfl->iNext;
    if( offset<OVERFLOW_SIZE ){
      int a = amt;
      if( a + offset > OVERFLOW_SIZE ){
        a = OVERFLOW_SIZE - offset;
      }
      memcpy(zBuf, &pOvfl->aPayload[offset], a);

      amt -= a;
      zBuf += a;
    }

    offset -= OVERFLOW_SIZE;

    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A total
................................................................................
    if( rc ) return rc;
    rc = sqlitepager_write(pOvfl);
    if( rc ){
      sqlitepager_unref(pOvfl);
      return rc;
    }
    pPage1->freeList = pOvfl->iNext;

    *ppPage = (MemPage*)pOvfl;
  }else{
    *pPgno = sqlitepager_pagecount(pBt->pPager);
    rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
    if( rc ) return rc;
    rc = sqlitepager_write(*ppPage);
  }
  return rc;
}

................................................................................
  int rc;
  int needOvflUnref = 0;

  if( pgno==0 ){
    assert( pOvfl!=0 );
    pgno = sqlitepager_pagenumber(pOvfl);
  }

  rc = sqlitepager_write(pPage1);
  if( rc ){
    return rc;
  }
  if( pOvfl==0 ){
    assert( pgno>0 );
    rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl);
................................................................................
  rc = sqlitepager_write(pOvfl);
  if( rc ){
    if( needOvflUnref ) sqlitepager_unref(pOvfl);
    return rc;
  }
  pOvfl->iNext = pPage1->freeList;
  pPage1->freeList = pgno;

  memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
  ((MemPage*)pPage)->isInit = 0;
  assert( ((MemPage*)pPage)->pParent==0 );
  rc = sqlitepager_unref(pOvfl);
  return rc;
}

................................................................................
  while( ovfl ){
    rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl);
    if( rc ) return rc;
    nextOvfl = pOvfl->iNext;
    rc = freePage(pBt, pOvfl, ovfl);
    if( rc ) return rc;
    ovfl = nextOvfl;
    sqlitepager_unref(pOvfl);
  }
  return SQLITE_OK;
}

/*
** Create a new cell from key and data.  Overflow pages are allocated as
** necessary and linked to this cell.  
................................................................................
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pCell) );

  for(j=pPage->nCell; j>i; j--){
    pPage->apCell[j] = pPage->apCell[j-1];
  }
  pPage->nCell++;
  idx = allocateSpace(pPage, sz);
  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->apCell[i] = pCell;
  }else{
    memcpy(&pPage->u.aDisk[idx], pCell, sz);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
  }
................................................................................
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(Btree *pBt, Pgno pgno){
  MemPage *pPage;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);
  if( rc ) return rc;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 ){
    pCell = (Cell*)&pPage->u.aDisk[idx];
    idx = pCell->h.iNext;
    if( pCell->h.leftChild ){
      rc = clearDatabasePage(pBt, pCell->h.leftChild);
      if( rc ) return rc;
    }
    rc = clearCell(pBt, pCell);
    if( rc ) return rc;
  }

  rc = clearDatabasePage(pBt, pPage->u.hdr.rightChild);
  if( rc ) return rc;


  return freePage(pBt, pPage, pgno);




}

/*
** Delete all information from a single table in the database.
*/
int sqliteBtreeClearTable(Btree *pBt, int iTable){
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = clearDatabasePage(pBt, (Pgno)iTable);
  if( rc ){
    sqliteBtreeRollback(pBt);
  }
  return rc;
}

/*
................................................................................
int sqliteBtreeDropTable(Btree *pBt, int iTable){
  int rc;
  MemPage *pPage;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeClearTable(pBt, iTable);
  }

  if( rc==SQLITE_OK && iTable!=2 ){
    rc = freePage(pBt, pPage, (Pgno)iTable);
  }

  sqlitepager_unref(pPage);

  return rc;  
}

/*
** Read the meta-information out of a database file.
*/
int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc;

  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;

  memcpy(aMeta, pP1->aMeta, sizeof(pP1->aMeta));
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
................................................................................
  PageOne *pP1;
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  pP1 = pBt->page1;
  rc = sqlitepager_write(pP1);
  if( rc ) return rc;
  memcpy(pP1->aMeta, aMeta, sizeof(pP1->aMeta));
  return SQLITE_OK;
}

#ifdef SQLITE_TEST
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
................................................................................
  }
  i = 0;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){
    Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
    int sz = cellSize(pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);

    if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
    memcpy(payload, pCell->aPayload, sz);
    for(j=0; j<sz; j++){
      if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
    }
    payload[sz] = 0;
    printf(
      "cell %2d: i=%-10s chld=%-4d nk=%-3d nd=%-3d payload=%s\n",
      i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData,
      pCell->aPayload
    );



    i++;
    idx = pCell->h.iNext;
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  printf("right_child: %d\n", pPage->u.hdr.rightChild);
................................................................................
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx];
    sprintf(range,"%d..%d", idx, idx+p->iSize-1);
    nFree += p->iSize;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, p->iSize, nFree);
    idx = p->iNext;

  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
/*
** Put the page number and index of a cursor into aResult[0] and aResult[1]
** This routine is used for debugging and testing only.









*/
int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){


  aResult[0] = sqlitepager_pagenumber(pCur->pPage);
  aResult[1] = pCur->idx;

















  return SQLITE_OK;
}
#endif

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.15 2001/06/25 02:11:07 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.
................................................................................
** for additional information.)  Page 0 does not exist and a page
** number of 0 is used to mean "no such page".
*/
struct PageOne {
  char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */
  int iMagic;              /* Integer to verify correct byte order */
  Pgno freeList;           /* First free page in a list of all free pages */
  int nFree;               /* Number of pages on the free list */
  int aMeta[SQLITE_N_BTREE_META-1];  /* User defined integers */
};

/*
** Each database page has a header that is an instance of this
** structure.
**
** PageHdr.firstFree is 0 if there is no free space on this page.
................................................................................
** The maximum amount of payload (in bytes) that can be stored locally for
** a database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
**
** This number is chosen so that at least 4 cells will fit on every page.
*/
#define MX_LOCAL_PAYLOAD \
  (((SQLITE_PAGE_SIZE-sizeof(PageHdr))/4-(sizeof(CellHdr)+sizeof(Pgno)))&~3)

/*
** Data on a database page is stored as a linked list of Cell structures.
** Both the key and the data are stored in aPayload[].  The key always comes
** first.  The aPayload[] field grows as necessary to hold the key and data,
** up to a maximum of MX_LOCAL_PAYLOAD bytes.  If the size of the key and
** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the
................................................................................
  FreeBlk *pFBlk;
  char newPage[SQLITE_PAGE_SIZE];

  pc = sizeof(PageHdr);
  pPage->u.hdr.firstCell = pc;
  memcpy(newPage, pPage->u.aDisk, pc);
  for(i=0; i<pPage->nCell; i++){
    Cell *pCell = pPage->apCell[i];

    /* This routine should never be called on an overfull page.  The
    ** following asserts verify that constraint. */
    assert( Addr(pCell) > Addr(pPage) );
    assert( Addr(pCell) < Addr(pPage) + SQLITE_PAGE_SIZE );

    n = cellSize(pCell);
    pCell->h.iNext = pc + n;
    memcpy(&newPage[pc], pCell, n);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
    pc += n;
  }
  assert( pPage->nFree==SQLITE_PAGE_SIZE-pc );
  memcpy(pPage->u.aDisk, newPage, pc);
  if( pPage->nCell>0 ){
    pPage->apCell[pPage->nCell-1]->h.iNext = 0;
  }
  pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];
  pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
  pFBlk->iNext = 0;
  pPage->u.hdr.firstFree = pc;
  memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk));
}

................................................................................
    sqlitepager_unref(pBt->page1);
    pBt->page1 = 0;
    pBt->inTrans = 0;
  }
}

/*
** Commit the transaction currently in progress.

*/
int sqliteBtreeCommit(Btree *pBt){
  int rc;
  if( pBt->inTrans==0 ) return SQLITE_ERROR;
  rc = sqlitepager_commit(pBt->pPager);
  pBt->inTrans = 0;
  unlockBtree(pBt);
  return rc;
}

/*
................................................................................
    if( a+offset>MX_LOCAL_PAYLOAD ){
      a = MX_LOCAL_PAYLOAD - offset;
    }
    memcpy(zBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset = 0;
    zBuf += a;
    amt -= a;
  }
  if( amt>0 ){
    nextPage = pCur->pPage->apCell[pCur->idx]->ovfl;
  }
  while( amt>0 && nextPage ){
................................................................................
    nextPage = pOvfl->iNext;
    if( offset<OVERFLOW_SIZE ){
      int a = amt;
      if( a + offset > OVERFLOW_SIZE ){
        a = OVERFLOW_SIZE - offset;
      }
      memcpy(zBuf, &pOvfl->aPayload[offset], a);
      offset = 0;
      amt -= a;
      zBuf += a;

    }else{
      offset -= OVERFLOW_SIZE;
    }
    sqlitepager_unref(pOvfl);
  }
  return amt==0 ? SQLITE_OK : SQLITE_CORRUPT;
}

/*
** Read part of the key associated with cursor pCur.  A total
................................................................................
    if( rc ) return rc;
    rc = sqlitepager_write(pOvfl);
    if( rc ){
      sqlitepager_unref(pOvfl);
      return rc;
    }
    pPage1->freeList = pOvfl->iNext;
    pPage1->nFree--;
    *ppPage = (MemPage*)pOvfl;
  }else{
    *pPgno = sqlitepager_pagecount(pBt->pPager) + 1;
    rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
    if( rc ) return rc;
    rc = sqlitepager_write(*ppPage);
  }
  return rc;
}

................................................................................
  int rc;
  int needOvflUnref = 0;

  if( pgno==0 ){
    assert( pOvfl!=0 );
    pgno = sqlitepager_pagenumber(pOvfl);
  }
  assert( pgno>2 );
  rc = sqlitepager_write(pPage1);
  if( rc ){
    return rc;
  }
  if( pOvfl==0 ){
    assert( pgno>0 );
    rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl);
................................................................................
  rc = sqlitepager_write(pOvfl);
  if( rc ){
    if( needOvflUnref ) sqlitepager_unref(pOvfl);
    return rc;
  }
  pOvfl->iNext = pPage1->freeList;
  pPage1->freeList = pgno;
  pPage1->nFree++;
  memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
  ((MemPage*)pPage)->isInit = 0;
  assert( ((MemPage*)pPage)->pParent==0 );
  rc = sqlitepager_unref(pOvfl);
  return rc;
}

................................................................................
  while( ovfl ){
    rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl);
    if( rc ) return rc;
    nextOvfl = pOvfl->iNext;
    rc = freePage(pBt, pOvfl, ovfl);
    if( rc ) return rc;
    ovfl = nextOvfl;

  }
  return SQLITE_OK;
}

/*
** Create a new cell from key and data.  Overflow pages are allocated as
** necessary and linked to this cell.  
................................................................................
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(MemPage *pPage, int i, Cell *pCell, int sz){
  int idx, j;
  assert( i>=0 && i<=pPage->nCell );
  assert( sz==cellSize(pCell) );
  idx = allocateSpace(pPage, sz);
  for(j=pPage->nCell; j>i; j--){
    pPage->apCell[j] = pPage->apCell[j-1];
  }
  pPage->nCell++;

  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->apCell[i] = pCell;
  }else{
    memcpy(&pPage->u.aDisk[idx], pCell, sz);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
  }
................................................................................
  return SQLITE_OK;
}

/*
** Erase the given database page and all its children.  Return
** the page to the freelist.
*/
static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){
  MemPage *pPage;
  int rc;
  Cell *pCell;
  int idx;

  rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);
  if( rc ) return rc;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 ){
    pCell = (Cell*)&pPage->u.aDisk[idx];
    idx = pCell->h.iNext;
    if( pCell->h.leftChild ){
      rc = clearDatabasePage(pBt, pCell->h.leftChild, 1);
      if( rc ) return rc;
    }
    rc = clearCell(pBt, pCell);
    if( rc ) return rc;
  }
  if( pPage->u.hdr.rightChild ){
    rc = clearDatabasePage(pBt, pPage->u.hdr.rightChild, 1);
    if( rc ) return rc;
  }
  if( freePageFlag ){
    rc = freePage(pBt, pPage, pgno);
  }else{
    zeroPage(pPage);
  }
  return rc;
}

/*
** Delete all information from a single table in the database.
*/
int sqliteBtreeClearTable(Btree *pBt, int iTable){
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = clearDatabasePage(pBt, (Pgno)iTable, 0);
  if( rc ){
    sqliteBtreeRollback(pBt);
  }
  return rc;
}

/*
................................................................................
int sqliteBtreeDropTable(Btree *pBt, int iTable){
  int rc;
  MemPage *pPage;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
  if( rc ) return rc;
  rc = sqliteBtreeClearTable(pBt, iTable);

  if( rc ) return rc;
  if( iTable>2 ){
    rc = freePage(pBt, pPage, iTable);
  }else{
    zeroPage(pPage);
    sqlitepager_unref(pPage);
  }
  return rc;  
}

/*
** Read the meta-information out of a database file.
*/
int sqliteBtreeGetMeta(Btree *pBt, int *aMeta){
  PageOne *pP1;
  int rc;

  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
  if( rc ) return rc;
  aMeta[0] = pP1->nFree;
  memcpy(&aMeta[1], pP1->aMeta, sizeof(pP1->aMeta));
  sqlitepager_unref(pP1);
  return SQLITE_OK;
}

/*
** Write meta-information back into the database.
*/
................................................................................
  PageOne *pP1;
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  pP1 = pBt->page1;
  rc = sqlitepager_write(pP1);
  if( rc ) return rc;	
  memcpy(pP1->aMeta, &aMeta[1], sizeof(pP1->aMeta));
  return SQLITE_OK;
}

#ifdef SQLITE_TEST
/*
** Print a disassembly of the given page on standard output.  This routine
** is used for debugging and testing only.
................................................................................
  }
  i = 0;
  idx = pPage->u.hdr.firstCell;
  while( idx>0 && idx<=SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){
    Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
    int sz = cellSize(pCell);
    sprintf(range,"%d..%d", idx, idx+sz-1);
    sz = pCell->h.nKey + pCell->h.nData;
    if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
    memcpy(payload, pCell->aPayload, sz);
    for(j=0; j<sz; j++){
      if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
    }
    payload[sz] = 0;
    printf(
      "cell %2d: i=%-10s chld=%-4d nk=%-3d nd=%-3d payload=%s\n",
      i, range, (int)pCell->h.leftChild, pCell->h.nKey, pCell->h.nData,
      payload
    );
    if( pPage->apCell[i]!=pCell ){
      printf("**** apCell[%d] does not match on prior entry ****\n", i);
    }
    i++;
    idx = pCell->h.iNext;
  }
  if( idx!=0 ){
    printf("ERROR: next cell index out of range: %d\n", idx);
  }
  printf("right_child: %d\n", pPage->u.hdr.rightChild);
................................................................................
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx];
    sprintf(range,"%d..%d", idx, idx+p->iSize-1);
    nFree += p->iSize;
    printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
       i, range, p->iSize, nFree);
    idx = p->iNext;
    i++;
  }
  if( idx!=0 ){
    printf("ERROR: next freeblock index out of range: %d\n", idx);
  }
  sqlitepager_unref(pPage);
  return SQLITE_OK;
}
#endif

#ifdef SQLITE_TEST
/*
** Fill aResult[] with information about the entry and page that the
** cursor is pointing to.
** 
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
int sqliteBtreeCursorDump(BtCursor *pCur, int *aResult){
  int cnt, idx;
  MemPage *pPage = pCur->pPage;
  aResult[0] = sqlitepager_pagenumber(pPage);
  aResult[1] = pCur->idx;
  aResult[2] = pPage->nCell;
  if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
    aResult[3] = cellSize(pPage->apCell[pCur->idx]);
    aResult[6] = pPage->apCell[pCur->idx]->h.leftChild;
  }else{
    aResult[3] = 0;
    aResult[6] = 0;
  }
  aResult[4] = pPage->nFree;
  cnt = 0;
  idx = pPage->u.hdr.firstFree;
  while( idx>0 && idx<SQLITE_PAGE_SIZE ){
    cnt++;
    idx = ((FreeBlk*)&pPage->u.aDisk[idx])->iNext;
  }
  aResult[5] = cnt;
  aResult[7] = pPage->u.hdr.rightChild;
  return SQLITE_OK;
}
#endif

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.5 2001/06/22 19:15:00 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 3
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
#endif

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.6 2001/06/25 02:11:07 drh Exp $
*/

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree);
int sqliteBtreeClose(Btree*);
................................................................................
int sqliteBtreeNext(BtCursor*, int *pRes);
int sqliteBtreeKeySize(BtCursor*, int *pSize);
int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeDataSize(BtCursor*, int *pSize);
int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf);
int sqliteBtreeCloseCursor(BtCursor*);

#define SQLITE_N_BTREE_META 4
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
#endif

**   http://www.hwaci.com/drh/
**
*************************************************************************
** 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.2 2001/06/22 19:15:01 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  free(zBuf);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_dump ID
**
** Return two integers which are the page number and cell index for
** the given cursor.









*/
static int btree_cursor_dump(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  char **argv            /* Text of each argument */
){
  BtCursor *pCur;
  int rc;

  int aResult[2];
  char zBuf[50];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeCursorDump(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  sprintf(zBuf,"%d %d",aResult[0], aResult[1]);




  Tcl_AppendResult(interp, zBuf, 0);
  return SQLITE_OK;
}

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

**   http://www.hwaci.com/drh/
**
*************************************************************************
** 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.3 2001/06/25 02:11:07 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  free(zBuf);
  return SQLITE_OK;
}

/*
** Usage:   btree_cursor_dump ID
**
** Return eight integers containing information about the entry the
** cursor is pointing to:
**
**   aResult[0] =  The page number
**   aResult[1] =  The entry number
**   aResult[2] =  Total number of entries on this page
**   aResult[3] =  Size of this entry
**   aResult[4] =  Number of free bytes on this page
**   aResult[5] =  Number of free blocks on the page
**   aResult[6] =  Page number of the left child of this entry
**   aResult[7] =  Page number of the right child for the whole page
*/
static int btree_cursor_dump(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  char **argv            /* Text of each argument */
){
  BtCursor *pCur;
  int rc;
  int i, j;
  int aResult[8];
  char zBuf[400];

  if( argc!=2 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  rc = sqliteBtreeCursorDump(pCur, aResult);
  if( rc ){
    Tcl_AppendResult(interp, errorName(rc), 0);
    return TCL_ERROR;
  }
  j = 0;
  for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){
    sprintf(&zBuf[j]," %d", aResult[i]);
    j += strlen(&zBuf[j]);
  }
  Tcl_AppendResult(interp, &zBuf[1], 0);
  return SQLITE_OK;
}

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

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.1 2001/06/24 20:39:41 drh Exp $


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

if {$dbprefix!="memory:" && [info commands btree_open]!=""} {

................................................................................
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Commit and make sure the delete is still there.
#
do_test btree-4.5 {

















  btree_close_cursor $::c1
  btree_commit $::b1

  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}













































do_test btree-99.1 {






























































































































































































  btree_close $::b1








} {}









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

finish_test

#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.2 2001/06/25 02:11:07 drh Exp $


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

if {$dbprefix!="memory:" && [info commands btree_open]!=""} {

................................................................................
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Commit and make sure the delete is still there.
#
do_test btree-4.5 {
  btree_commit $::b1
  btree_move_to $::c1 {}
  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Completely close the database and reopen it.  Then check
# the data again.
#
do_test btree-4.6 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2]

  set r {}
  while 1 {
    set key [btree_key $::c1]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $::c1]
    btree_next $::c1
  }
  set r   
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}

# Try to read and write meta data
#
do_test btree-5.1 {
  btree_get_meta $::b1
} {0 0 0 0}
do_test btree-5.2 {
  set rc [catch {btree_update_meta $::b1 1 2 3 4} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-5.3 {
  btree_begin_transaction $::b1
  set rc [catch {btree_update_meta $::b1 1 2 3 4} msg]
  lappend rc $msg
} {0 {}}
do_test btree-5.4 {
  btree_get_meta $::b1
} {0 2 3 4}
do_test btree-5.5 {
  btree_close_cursor $::c1
  btree_rollback $::b1
  btree_get_meta $::b1
} {0 0 0 0}
do_test btree-5.6 {
  btree_begin_transaction $::b1
  btree_update_meta $::b1 999 10 20 30
  btree_commit $::b1
  btree_get_meta $::b1
} {0 10 20 30}

proc select_all {cursor} {
  set r {}
  btree_move_to $cursor {}
  while 1 {
    set key [btree_key $cursor]
    if {$key==""} break
    lappend r $key
    lappend r [btree_data $cursor]
    btree_next $cursor
  }
  return $r
}

# Try to create a new table in the database file
#
do_test btree-6.1 {
  set rc [catch {btree_create_table $::b1} msg]
  lappend rc $msg
} {1 SQLITE_ERROR}
do_test btree-6.2 {
  btree_begin_transaction $::b1
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.2.1 {
  set ::c2 [btree_cursor $::b1 $::t2]
  btree_insert $::c2 ten 10
  btree_key $::c2
} {ten}
do_test btree-6.3 {
  btree_commit $::b1
  set ::c1 [btree_cursor $::b1 2]
  select_all $::c1
} {five 5.00 four 4.00 six 6.00 three 3.00 two 2.00}
#btree_page_dump $::b1 3
do_test btree-6.4 {
  select_all $::c2
} {ten 10}

# Drop the new table, then create it again anew.
#
do_test btree-6.5 {
  btree_begin_transaction $::b1
} {}
do_test btree-6.6 {
  btree_close_cursor $::c2
} {}
do_test btree-6.7 {
  btree_drop_table $::b1 $::t2
} {}
do_test btree-6.7.1 {
  lindex [btree_get_meta $::b1] 0
} {1}
do_test btree-6.8 {
  set ::t2 [btree_create_table $::b1]
} {3}
do_test btree-6.8.1 {
  lindex [btree_get_meta $::b1] 0
} {0}
do_test btree-6.9 {
  set ::c2 [btree_cursor $::b1 $::t2]
  btree_move_to $::c2 {}
  btree_key $::c2
} {}

# If we drop table 2 it just clears the table.  Table 2 always exists.
#
do_test btree-6.10 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 {}
  btree_key $::c1
} {}
do_test btree-6.11 {
  btree_commit $::b1
  select_all $::c1
} {}
do_test btree-6.12 {
  select_all $::c2
} {}

# Check to see that pages defragment properly.  To do this test we will
# 
#   1.  Fill the first page table 2 with data.
#   2.  Delete every other entry of table 2. 
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
do_test btree-7.2 {
  for {set i 0} {$i<36} {incr i} {
    set key [format %03d $i]
    set data "*** $key ***"
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {8 1}
do_test btree-7.3 {
  btree_move_to $::c1 000
  while {[btree_key $::c1]!=""} {
    btree_delete $::c1
    btree_next $::c1
    btree_next $::c1
  }
  lrange [btree_cursor_dump $::c1] 4 5
} {512 19}
#btree_page_dump $::b1 2
do_test btree-7.4 {
  btree_insert $::c1 018 {*** 018 ***+++}
  btree_key $::c1
} {018}
do_test btree-7.5 {
  lrange [btree_cursor_dump $::c1] 4 5
} {480 1}
#btree_page_dump $::b1 2

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
do_test btree-7.6 {
  btree_move_to $::c1 007
  btree_delete $::c1
  btree_move_to $::c1 011
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lindex [btree_cursor_dump $::c1] 5
} {3}
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 007 {*** 007 ***}
  lindex [btree_cursor_dump $::c1] 5
} {2}
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 013
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {536 2}
do_test btree-7.10 {
  btree_move_to $::c1 009
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {564 2}
do_test btree-7.11 {
  btree_move_to $::c1 018
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {596 2}
do_test btree-7.13 {
  btree_move_to $::c1 033
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {624 3}
do_test btree-7.14 {
  btree_move_to $::c1 035
  btree_delete $::c1
  lrange [btree_cursor_dump $::c1] 4 5
} {652 2}
#btree_page_dump $::b1 2

# Check to see that both key and data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<256} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
#btree_page_dump $::b1 2
do_test btree-8.2 {
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.3 {
  btree_data $::c1
} $::data
do_test btree-8.4 {
  btree_delete $::c1
} {}
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key"
  while {[string length $data]<2000} {append data $data}
  set ::data $data
  btree_insert $::c1 020 $data
} {}
do_test btree-8.6 {
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
  btree_data $::c1
} $::data
do_test btree-8.9 {
  btree_close_cursor $::c1
  btree_close $::b1
  set ::b1 [btree_open test1.bt]
  set ::c1 [btree_cursor $::b1 2]
  btree_move_to $::c1 020
  btree_data $::c1
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
puts [btree_get_meta $::b1]

do_test btree-99.1 {
  btree_close $::b1
} {}

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

finish_test