SQLite

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.11 2001/06/08 00:21:52 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.

#include "pager.h"
#include "btree.h"
#include <assert.h>


/*
** Primitive data types.  u32 must be 4 bytes and u16 must be 2 bytes.

** Change these typedefs when porting to new architectures.
*/

typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

/*
** Forward declarations of structures used only in this file.
*/

};

/*
** 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.
** Otherwise, PageHdr.firstFree is the index in MemPage.aDisk[] of a 
** FreeBlk structure that describes the first block of free space.  
** All free space is defined by a linked list of FreeBlk structures.
**
** Data is stored in a linked list of Cell structures.  PageHdr.firstCell
** is the index into MemPage.aDisk[] of the first cell on the page.  The
** Cells are kept in sorted order.
**
** A Cell contains all information about a database entry and a pointer
** to a child page that contains other entries less than itself.  In
** other words, the i-th Cell contains both Ptr(i) and Key(i).  The
** right-most pointer of the page is contained in PageHdr.rightChild.
*/
struct PageHdr {
  Pgno rightChild;  /* Child page that comes after all cells on this page */
  u16 firstCell;    /* Index in MemPage.aDisk[] of the first cell */
  u16 firstFree;    /* Index in MemPage.aDisk[] of the first free block */
};

/*
** Entries on a page of the database are called "Cells".  Each Cell
** has a header and data.  This structure defines the header.  The
** key and data (collectively the "payload") follow this header on
** the database page.
**
** A definition of the complete Cell structure is given below.  The
** header for the cell must be defined separately in order to do some
** of the sizing #defines that follow.
*/
struct CellHdr {
  Pgno leftChild; /* Child page that comes before this cell */
  u16 nKey;       /* Number of bytes in the key */
  u16 iNext;      /* Index in MemPage.aDisk[] of next cell in sorted order */
  u32 nData;      /* Number of bytes of data */
}

/*
** The minimum size of a complete Cell.  The Cell must contain a header
** and at least 4 bytes of payload.
*/

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

/*
** Number of bytes on a single overflow page.
*/
#define OVERFLOW_SIZE (SQLITE_PAGE_SIZE-sizeof(Pgno))

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

/*
** For every page in the database file, an instance of the following structure
** is stored in memory.  The aDisk[] array contains the raw bits read from
** the disk.  The rest is auxiliary information that held in memory only. The
** auxiliary info is only valid for regular database pages - it is not
** used for overflow pages and pages on the freelist.
**
** Of particular interest in the auxiliary info is the apCell[] entry.  Each
** apCell[] entry is a pointer to a Cell structure in aDisk[].  The cells are
** put in this array so that they can be accessed in constant time, rather
** than in linear time which would be needed if we had to walk the linked 
** list on every access.
**









** The pParent field points back to the parent page.  This allows us to
** walk up the BTree from any leaf to the root.  Care must be taken to
** unref() the parent page pointer when this page is no longer referenced.
** The pageDestructor() routine handles that chore.
*/
struct MemPage {

  char aDisk[SQLITE_PAGE_SIZE];  /* Page data stored on disk */


  int isInit;                    /* True if auxiliary data is initialized */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
  int nFree;                     /* Number of free bytes in aDisk[] */
  int nCell;                     /* Number of entries on this page */

  Cell *apCell[MX_CELL+1];       /* All data entires in sorted order */
}

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
*/

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.apCell[] of the entry.
*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pPrev, *pNext;  /* List of all cursors */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  u16 idx;                  /* Index of the entry in pPage->apCell[] */
  u8 bSkipNext;             /* sqliteBtreeNext() is no-op if true */
  u8 iMatch;                /* compare result from last sqliteBtreeMoveto() */
};

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

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

/*
** Allocate nByte bytes of space on a page.  nByte must be a 
** multiple of 4.
**
** Return the index into pPage->aDisk[] of the first byte of
** the new allocation. Or return 0 if there is not enough free
** space on the page to satisfy the allocation request.
**
** If the page contains nBytes of free space but does not contain
** nBytes of contiguous free space, then this routine automatically
** calls defragementPage() to consolidate all free space before 
** allocating the new chunk.
*/
static int allocateSpace(MemPage *pPage, int nByte){
  FreeBlk *p;
  u16 *pIdx;
  int start;

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

/*
** Return a section of the MemPage.aDisk[] to the freelist.
** The first byte of the new free block is pPage->aDisk[start]
** and the size of the block is "size" bytes.

**
** Most of the effort here is involved in coalesing adjacent
** free blocks into a single big free block.
*/
static void freeSpace(MemPage *pPage, int start, int size){
  int end = start + size;
  u16 *pIdx, idx;
  FreeBlk *pFBlk;
  FreeBlk *pNew;
  FreeBlk *pNext;

  assert( size == ROUNDUP(size) );
  assert( start == ROUNDUP(start) );
  pIdx = &((PageHdr*)pPage)->firstFree;
  idx = *pIdx;
  while( idx!=0 && idx<start ){
    pFBlk = (FreeBlk*)&pPage->aDisk[idx];
    if( idx + pFBlk->iSize == start ){
      pFBlk->iSize += size;
      if( idx + pFBlk->iSize == pFBlk->iNext ){
        pNext = (FreeBlk*)&pPage->aDisk[pFblk->iNext];
        pFBlk->iSize += pNext->iSize;
        pFBlk->iNext = pNext->iNext;
      }
      pPage->nFree += size;
      return;
    }
    pIdx = &pFBlk->iNext;
    idx = *pIdx;
  }
  pNew = (FreeBlk*)&pPage->aDisk[start];
  if( idx != end ){
    pNew->iSize = size;
    pNew->iNext = idx;
  }else{
    pNext = (FreeBlk*)&pPage->aDisk[idx];
    pNew->iSize = size + pNext->iSize;
    pNew->iNext = pNext->iNext;
  }
  *pIdx = start;
  pPage->nFree += size;
}

** Return SQLITE_OK on success.  If we see that the page does
** not contained a well-formed database page, then return 
** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
** guarantee that the page is well-formed.  It only shows that
** we failed to detect any corruption.
*/
static int initPage(MemPage *pPage, Pgno pgnoThis, MemPage *pParent){
  int idx;           /* An index into pPage->aDisk[] */
  Cell *pCell;       /* A pointer to a Cell in pPage->aDisk[] */
  FreeBlk *pFBlk;    /* A pointer to a free block in pPage->aDisk[] */
  int sz;            /* The size of a Cell in bytes */
  int freeSpace;     /* Amount of free space on the page */

  if( pPage->pParent ){
    assert( pPage->pParent==pParent );
    return SQLITE_OK;
  }
  if( pParent ){
    pPage->pParent = pParent;
    sqlitepager_ref(pParent);
  }
  if( pPage->isInit ) return SQLITE_OK;
  pPage->isInit = 1;
  pPage->nCell = 0;
  freeSpace = SQLITE_PAGE_SIZE - sizeof(PageHdr);
  idx = ((PageHdr*)pPage)->firstCell;
  while( idx!=0 ){
    if( idx>SQLITE_PAGE_SIZE-MN_CELL_SIZE ) goto page_format_error;
    if( idx<sizeof(PageHdr) ) goto page_format_error;
    pCell = (Cell*)&pPage->aDisk[idx];
    sz = cellSize(pCell);
    if( idx+sz > SQLITE_PAGE_SIZE ) goto page_format_error;
    freeSpace -= sz;
    pPage->apCell[pPage->nCell++] = pCell;
    idx = pCell->h.iNext;
  }
  pPage->nFree = 0;
  idx = ((PageHdr*)pPage)->firstFree;
  while( idx!=0 ){
    if( idx>SQLITE_PAGE_SIZE-sizeof(FreeBlk) ) goto page_format_error;
    if( idx<sizeof(PageHdr) ) goto page_format_error;
    pFBlk = (FreeBlk*)&pPage->aDisk[idx];
    pPage->nFree += pFBlk->iSize;
    if( pFBlk->iNext <= idx ) goto page_format_error;
    idx = pFBlk->iNext;
  }
  if( pPage->nCell==0 && pPage->nFree==0 ){
    /* As a special case, an uninitialized root page appears to be
    ** an empty database */
    return SQLITE_OK;
  }
  if( pPage->nFree!=freeSpace ) goto page_format_error;
  return SQLITE_OK;

page_format_error:
  return SQLITE_CORRUPT;
}

/*
** Recompute the MemPage.apCell[], MemPage.nCell, and MemPage.nFree parameters
** for a cell after the MemPage.aDisk[] content has be changed significantly.
**
** The computation here is similar to initPage() except that in this case
** the MemPage.aDisk[] field has been set up internally (instead of 
** having been read from disk) so we do not need to do as much error
** checking.
*/
static void reinitPage(MemPage *pPage){
  Cell *pCell;

  pPage->nCell = 0;
  idx = ((PageHdr*)pPage)->firstCell;
  while( idx!=0 ){
    pCell = (Cell*)&pPage->aDisk[idx];
    sz = cellSize(pCell);
    pPage->apCell[pPage->nCell++] = pCell;
    idx = pCell->h.iNext;
  }
  pPage->nFree = 0;
  idx = ((PageHdr*)pPage)->firstFree;
  while( idx!=0 ){
    pFBlk = (FreeBlk*)&pPage->aDisk[idx];
    pPage->nFree += pFBlk->iSize;
    idx = pFBlk->iNext;
  }
  return SQLITE_OK;
}

/*
** Set up a raw page so that it looks like a database page holding
** no entries.
*/
static void zeroPage(MemPage *pPage){
  PageHdr *pHdr;
  FreeBlk *pFBlk;
  memset(pPage, 0, SQLITE_PAGE_SIZE);
  pHdr = (PageHdr*)pPage;
  pHdr->firstCell = 0;
  pHdr->firstFree = sizeof(*pHdr);
  pFBlk = (FreeBlk*)&pHdr[1];
  pFBlk->iNext = 0;
  pFBlk->iSize = SQLITE_PAGE_SIZE - sizeof(*pHdr);
}

  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  rc = initPage(pCur->pPage, pCur->pgnoRoot, 0);
  if( rc!=SQLITE_OK ){
    goto create_cursor_exception;
  }
  pCur->pPrev = 0;

  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }

  pBt->pCursor = pCur;
  pCur->pBt = pBt;
  pCur->idx = 0;
  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:
  *ppCur = 0;
  if( pCur ){
    if( pCur->pPage ) sqlitepager_unref(pCur->pPage);

  sqliteFree(pCur);
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.
** The temporary cursor is not on the cursor list for the Btree.
*/
static void CreateTemporaryCursor(BtCursor *pCur, BtCursor *pTempCur){
  memcpy(pTempCur, pCur, sizeof(*pCur));
  pTempCur->pNext = 0;
  pTempCur->pPrev = 0;
  sqlitepager_ref(pTempCur->pPage);
}

/*
** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
** function above.
*/
static void DestroyTemporaryCursor(BeCursor *pCur){
  sqlitepager_unref(pCur->pPage);
}

/*
** Set *pSize to the number of bytes of key in the entry the
** cursor currently points to.  Always return SQLITE_OK.
** Failure is not possible.  If the cursor is not currently

  }
  while( amt>0 && nextPage ){
    OverflowPage *pOvfl;
    rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl);
    if( rc!=0 ){
      return rc;
    }
    nextPage = pOvfl->next;
    if( offset<OVERFLOW_SIZE ){
      int a = amt;
      if( a + offset > OVERFLOW_SIZE ){
        a = OVERFLOW_SIZE - offset;
      }
      memcpy(zBuf, &pOvfl->aPayload[offset], a);
      amt -= a;

    if( nextPage==0 ){
      return SQLITE_CORRUPT;
    }
    rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl);
    if( rc ){
      return rc;
    }
    nextPage = pOvfl->next;
    n = nKey;
    if( n>OVERFLOW_SIZE ){
      n = OVERFLOW_SIZE;
    }
    c = memcmp(pOvfl->aPayload, pKey, n);
    sqlitepager_unref(pOvfl);
    if( c!=0 ){

        lwr = pCur->idx+1;
      }else{
        upr = pCur->idx-1;
      }
    }
    assert( lwr==upr+1 );
    if( lwr>=pPage->nCell ){
      chldPg = ((PageHdr*)pPage)->rightChild;
    }else{
      chldPg = pPage->apCell[lwr]->h.leftChild;
    }
    if( chldPg==0 ){
      pCur->iMatch = c;
      if( pRes ) *pRes = c;
      return SQLITE_OK;

  if( pCur->bSkipNext ){
    pCur->bSkipNext = 0;
    if( pRes ) *pRes = 0;
    return SQLITE_OK;
  }
  pCur->idx++;
  if( pCur->idx>=pCur->pPage->nCell ){
    if( ((PageHdr*)pPage)->rightChild ){
      rc = moveToChild(pCur, ((PageHdr*)pPage)->rightChild);
      if( rc ) return rc;
      rc = moveToLeftmost(pCur);
      if( rc ) return rc;
      if( pRes ) *pRes = 0;
      return SQLITE_OK;
    }
    do{

    rc = sqlitepager_get(pBt->pPager, pPage1->freeList, &pOvfl);
    if( rc ) return rc;
    rc = sqlitepager_write(pOvfl);
    if( rc ){
      sqlitepager_unref(pOvfl);
      return rc;
    }
    pPage1->freeList = pOvfl->next;
    *ppPage = (MemPage*)pOvfl;
  }else{
    *pPgno = sqlitepager_pagecount(pBt->pPager);
    rc = sqlitepager_get(pBt->pPager, *pPgno, ppPage);
    if( rc ) return rc;
    rc = sqlitepager_write(*ppPage);
  }

    needOvflUnref = 1;
  }
  rc = sqlitepager_write(pOvfl);
  if( rc ){
    if( needOvflUnref ) sqlitepager_unref(pOvfl);
    return rc;
  }
  pOvfl->next = pPage1->freeList;
  pPage1->freeList = pgno;
  memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
  pPage->isInit = 0;
  assert( pPage->pParent==0 );
  rc = sqlitepager_unref(pOvfl);
  return rc;
}

    return SQLITE_OK;
  }
  ovfl = pCell->ovfl;
  pCell->ovfl = 0;
  while( ovfl ){
    rc = sqlitepager_get(pPager, ovfl, &pOvfl);
    if( rc ) return rc;
    nextOvfl = pOvfl->next;
    rc = freePage(pBt, pOvfl, ovfl);
    if( rc ) return rc;
    ovfl = nextOvfl;
    sqlitepager_unref(pOvfl);
  }
  return SQLITE_OK;
}

      if( rc ){
        *pNext = 0;
        clearCell(pBt, pCell);
        return rc;
      }
      spaceLeft = OVERFLOW_SIZE;
      pSpace = pOvfl->aPayload;
      pNextPg = &pOvfl->next;
    }
    n = nPayload;
    if( n>spaceLeft ) n = spaceLeft;
    memcpy(pSpace, pPayload, n);
    nPayload -= n;
    if( nPayload==0 && pData ){
      pPayload = pData;

** another.
*/
static void reparentChildPages(Pager *pPager, Page *pPage){
  int i;
  for(i=0; i<pPage->nCell; i++){
    reparentPage(pPager, pPage->apCell[i]->leftChild, pPage);
  }
  reparentPage(pPager, ((PageHdr*)pPage)->rightChild, pPage);
}

/*


































































































** This routine redistributes Cells on pPage and up to two siblings
** of pPage so that all pages have about the same amount of free space.
** Usually one siblings on either side of pPage are used in the repack,
** though both siblings might come from one side if pPage is the first
** or last child of its parent.  If pPage has fewer than two siblings
** (something which can only happen if pPage is the root page or a 
** child of root) then all siblings participate in the repack.
**
** The number of siblings of pPage might be increased or decreased by
** one in order to keep all pages between 2/3 and completely full.  If
** pPage is the root page, then the depth of the tree might be increased
** or decreased by one, as necessary, to keep the root page from being
** overfull or empty.
**









** Note that when this routine is called, some of the Cells on pPage
** might not actually be stored in pPage->aDisk[].  This can happen
** if the page is overfull.  Part of the job of this routine is to
** make sure all Cells for pPage once again fit in pPage->aDisk[].



*/
static int repack(Btree *pBt, MemPage *pPage){
  MemPage *pParent;            /* The parent of pPage */
  MemPage *apOld[3];           /* pPage and up to two siblings before repack */
  Pgno pgnoOld[3];             /* Page numbers for each page in apOld[] */
  MemPage *apNew[4];           /* pPage and up to 3 siblings after repack */

  int idxDiv[3];               /* Indices of divider cells in pParent */
  Cell *apDiv[3];              /* Divider cells in pParent */
  int nCell;                   /* Number of cells in apCell[] */
  int nOld;                    /* Number of pages in apOld[] */
  int nNew;                    /* Number of pages in apNew[] */
  int perPage;                 /* Approximate number of bytes per page */
  int nDiv;                    /* Number of cells in apDiv[] */







  Cell *apCell[MX_CELL*3+5];   /* All cells from pages being repacked */

  int unrefPage = 0;           /* If true, then unref pPage when done */


  /*

  ** Early out if no repacking is needed.
  */
  if( pPage->nFree>=0 && pPage->nFree<SQLITE_PAGE_SIZE/2 ){

    return SQLITE_OK;
  }

  /*
  ** Find the parent of the page to be repacked.
  */
  pParent = pPage->pParent;

  /*
  ** If there is no parent, it means the page is the root page.
  ** special rules apply.
  */

  if( pParent==0 ){
    Pgno pgnoChild;
    Page *pChild;
    if( pPage->nCell==0 ){
      if( ((PageHdr*)pPage)->rightChild ){

        /* The root page is under full.  Copy the one child page
        ** into the root page and return.  This reduces the depth
        ** of the BTree by one.
        */


        pgnoChild = ((PageHdr*)pPage->rightChild;
        rc = sqlitepager_get(pBt, pgnoChild, &pChild);
        if( rc ) return rc;
        memcpy(pPage, pChild, SQLITE_PAGE_SIZE);
        pPage->isInit = 0;
        initPage(pPage, sqlitepager_pagenumber(pPage), 0);
        reparentChildPages(pBt->pPager, pPage);
        freePage(pBt, pChild, pgnoChild);
        sqlitepager_unref(pChild);
      }
      return SQLITE_OK;
    }
    if( pPage->nFree>=0 ){
      /* It is OK for the root page to be less than half full.
      */

      return SQLITE_OK;
    }

    /* If we get to here, it means the root page is over full.
    ** When this happens, Create a new child page and copy the
    ** contents of the root into the child.  Then make the root
    ** page and empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */


    rc = allocatePage(pBt, &pChild, &pgnoChild);
    if( rc ) return rc;
    memcpy(pChild, pPage, SQLITE_PAGE_SIZE);
    for(i=0; i<pPage->nCell; i++){

      if( pPage->apCell[i]>(Cell*)pPage && pPage->apCell[i]<(Cell*)&pPage[1] ){
        int offset = (int)pPage->apCell[i] - (int)pPage;
        pChild->apCell[i] = (Cell*)((int)pChild + offset);
      }else{

        pChild->apCell[i] = pPage->apCell[i];
      }
    }
    pChild->isInit = 1;
    pChild->nCell = pPage->nCell;
    pChild->nFree = pPage->nFree;
    /* reparentChildPages(pBt->pPager, pChild); */
    zeroPage(pPage);
    ((PageHdr*)pPage)->rightChild = pgnoChild;
    pParent = pPage;
    pPage = pChild;

    unrefPage = 1;

  }

  /*
  ** Find the Cell in the parent page that refers to the page
  ** to be repacked.

  */
  idx = -1;
  pgno = sqlitepager_pagenumber(pPage);
  for(i=0; i<pParent->nCell; i++){
    if( pParent->apCell[i]->h.leftChild==pgno ){
      idx = i;
      break;
    }
  }
  if( idx<0 && ((PageHdr*)pPage)->rightChild==pgno ){
    idx = pPage->nCell;
  }
  if( idx<0 ){
    rc = SQLITE_CORRUPT;
    goto end_of_repack;
  }

  /*





  ** Get sibling pages and their dividers






  */
  if( idx==pPage->nCell ){
    idx -= 2;
  }else{
    idx--;
  }
  if( idx<0 ) idx = 0;
  nDiv = 0;
  nOld = 0;
  for(i=0; i<3; i++){
    if( i+idx<pParent->nCell ){
      idxDiv[i] = i+idx;
      apDiv[i] = pParent->apCell[i+idx];
      nDiv++;
      pgnoOld[i] = apDiv[i]->h.leftChild;
      rc = sqlitepager_get(pBt, pgnoOld[i], &apOld[i]);
      if( rc ) goto end_of_repack;
      nOld++;
    }
    if( i+idx==pParent->nCell ){
      pgnoOld[i] = pParent->rightChild;



      rc = sqlitepager_get(pBt, pgnoOld[i], &apOld[i]);
      if( rc ) goto end_of_repack;
      nOld++;
    }


























  }

  /*
  ** Get all cells


  */
  nCell = 0;
  for(i=0; i<nOld; i++){
    MemPage *pOld = apOld[i];
    for(j=0; j<pOld->nCell; j++){
      apCell[nCell++] = pOld->apCell[j];


    }
    if( i<nOld-1 ){


      apCell[nCell++] = apDiv[i];




    }
  }

  /*
  ** Estimate the number of pages needed


  */
  totalSize = 0;
  for(i=0; i<nCell; i++){
    totalSize += cellSize(apCell[i]);
  }
  nNew = (totalSize + (SQLITE_PAGE_SIZE - sizeof(PageHdr) - 1)) /
            (SQLITE_PAGE_SIZE - sizeof(PageHdr));
  perPage = totalSize/nNew;

  

  /*
  ** Allocate new pages
  */
  for(i=0; i<nNew; i++){
    rc = allocatePage(pBt, &apNew[i], &pgnoNew[i]);
    if( rc ) goto end_of_repack;

    zeroPage(apNew[i]);
  }

  /*
  ** Copy data into the new pages
  */
  for(i=0; i<nNew; i++){
  }

  /*
  ** Reparent children of all cells
  */

  /*
  ** Release the old pages
  */
  for(i=0; i<nOld; i++){
    releasePage(pBt, apOld[i], 0);
  }

  /*
  ** Repack the parent page, if necessary
  */
  if( needToRepackParent ){
    return repack(pParent);
  }
  rc = SQLITE_OK;

end_of_repack:
  if( unrefPage ){
    sqlitepager_unref(pPage);
  }
  return rc;
}

/*
** Attempt to move N or more bytes out of the page that the cursor
** points to into the left sibling page.  (The left sibling page
** contains cells that are less than the cells on this page.)  The
** entry that the cursor is pointing to cannot be moved.  Return
** TRUE if successful and FALSE if not.
**
** Reasons for not being successful include: 
**
**    (1) there is no left sibling,
**    (2) we could only move N-1 bytes or less,
**    (3) some kind of file I/O error occurred
**
** Note that a partial rotation may have occurred even if this routine
** returns FALSE.  Failure means we could not rotation a full N bytes.
** If it is possible to rotation some smaller number M, then the 
** rotation occurs but we still return false.
**
** Example:  Consider a segment of the Btree that looks like the
** figure below prior to rotation.  The cursor is pointing to the
** entry *.  The sort order of the entries is A B C D E * F Y.
**
**
**            -------------------------
**                ... | C | Y | ...
**            -------------------------
**                     /     \
**            ---------       -----------------
**            | A | B |       | D | E | * | F |
**            ---------       -----------------
**
** After rotation of two cells (D and E), the same Btree segment 
** looks like this:
**
**            -------------------------
**                ... | E | Y | ...
**            -------------------------
**                     /     \
**    -----------------       ---------
**    | A | B | C | D |       | * | F |
**    -----------------       ---------
**
** The size of this rotation is the size by which the page containing
** the cursor was reduced.  In this case, the size of D and E.
**
*/
static int rotateLeft(BtCursor *pCur, int N){
  return 0;

}

/*
** This routine is the same as rotateLeft() except that it move data
** to the right instead of to the left.  See comments on the rotateLeft()
** routine for additional information.
*/
static int rotateRight(BtCursor *pCur, int N){
  return 0;
}

/*



** Append a cell onto the end of a page.
**
** The child page of the cell is reparented if pPager!=NULL.
*/
static void appendCell(
  Pager *pPager,      /* The page cache.  Needed for reparenting */
  Cell *pSrc,         /* The Cell to be copied onto a new page */
  MemPage *pPage      /* The page into which the cell is copied */
){

  int pc;
  int sz;
  Cell *pDest;

  sz = cellSize(pSrc);
  pc = allocateSpace(pPage, sz);
  assert( pc>0 ){
  pDest = pPage->apCell[pPage->nCell] = &pPage->aDisk[pc];
  memcpy(pDest, pSrc, sz);
  pDest->h.iNext = 0;


  if( pPage->nCell>0 ){
    pPage->apCell[pPage->nCell-1]->h.iNext = pc;

  }else{
    ((PageHdr*)pPage)->firstCell = pc;

  }
  if( pPager && pDest->h.leftChild ){

    reparentPage(pPager, pDest->h.leftChild, pPage);
  }
}

/*
** Split a single database page into two roughly equal-sized pages.
**
** The input is an existing page and a new Cell.  The Cell might contain
** a valid Cell.h.leftChild field pointing to a child page.
**
** The output is the Cell that divides the two new pages.  The content
** of this divider Cell is written into *pCenter.  pCenter->h.leftChild
** holds the page number of the new page that was created to hold the 
** smaller of the cells from the divided page.  The larger cells from
** the divided page are written to a newly allocated page and *ppOut 
** is made to point to that page.  Or if ppOut==NULL then the larger cells
** remain on pIn.
**
** Upon return, pCur should be pointing to the same cell, even if that
** cell has moved to a new page.  The cell that pCur points to cannot
** be the pCenter cell.
*/
static int split(
  BtCursor *pCur,     /* A cursor pointing at a cell on the page to be split */
  Cell *pNewCell,     /* A new cell to add to pIn before dividing it up */
  Cell *pCenter,      /* Write the cell that divides the two pages here */
  MemPage **ppOut     /* If not NULL, put larger cells in new page at *ppOut */
){
  MemPage *pLeft, *pRight;
  Pgno pgnoLeft, pgnoRight;
  PageHdr *pHdr;
  int rc;
  Pager *pPager = pCur->pBt->pPager;
  MemPage tempPage;

  /* Allocate pages to hold cells after the split and make pRight and 
  ** pLeft point to the newly allocated pages.
  */
  rc = allocatePage(pCur->pBt, &pLeft, &pgnoLeft);
  if( rc ) return rc;
  if( ppOut ){
    rc = allocatePage(pCur->pBt, &pRight, &pgnoRight);
    if( rc ){
      freePage(pCur->pBt, pLeft, pgnoLeft);
      return rc;
    }
    *ppOut = pRight;
  }else{
    *ppOut = tempPage;
  }

  /* Copy the smaller cells from the original page into the left page
  ** of the split.
  */
  zeroPage(pLeft);
  if( pCur->idx==0 && pCur->match>0 ){
    appendCell(pPager, pNewCell, pLeft);
  }
  do{
    assert( i<pPage->nCell );
    appendCell(pPager, pPage->apCell[i++], pLeft);
    if( pCur->idx==i && pCur->iMatch>0 ){
      appendCell(pPager, pNewCell, Left);
    }
  }while( pc < SQLITE_PAGE_SIZE/2 );

  /* Copy the middle entry into *pCenter
  */
  assert( i<pPage->nCell );
  memcpy(pCenter, pPage->aCell[i], cellSize(pPage->aCell[i]));
  i++;
  pHdr = (PageHdr*)pLeft;
  pHdr->rightChild = pCenter->h.leftChild;
  if( pHdr->rightChild ){
    reparentPage(pPager, pHdr->rightChild, pLeft);
  }
  pCenter->h.leftChild = pgnoLeft;
 
  /* Copy the larger cells from the original page into the right
  ** page of the split
  */
  zeroPage(pRight);
  while( i<pPage->nCell ){
    appendCell(0, pPage->apCell[i++], pRight);
  }

  /* If ppOut==NULL then copy the temporary right page over top of
  ** the original input page.
  */
  if( ppOut==0 ){
    pRight->pParent = pPage->pParent;
    pRight->isInit = 1;
    memcpy(pPage, pRight, sizeof(*pPage));
  }
  reparentChildPages(pPager, pPage);
}

/*
** Unlink a cell from a database page.  Add the space used by the cell
** back to the freelist for the database page on which the cell used to
** reside.
**
** This operation overwrites the cell header and content.
*/
static void unlinkCell(BtCursor *pCur){
  MemPage *pPage;    /* Page containing cell to be unlinked */
  int idx;           /* The index of the cell to be unlinked */
  Cell *pCell;       /* Pointer to the cell to be unlinked */
  u16 *piCell;       /* iNext pointer from prior cell */
  int iCell;         /* Index in pPage->aDisk[] of cell to be unlinked */
  int i;             /* Loop counter */

  pPage = pCur->pPage;

  sqlitepager_write(pPage);
  idx = pCur->idx;
  pCell = pPage->apCell[idx];
  if( idx==0 ){
    piCell = &pPage->pHdr->firstCell;
  }else{
    piCell = &pPage->apCell[idx-1]->h.iNext;
  }
  iCell = *piCell;
  *piCell = pCell->h.iNext;
  freeSpace(pPage, iCell, cellSize(pCell));
  pPage->nCell--;
  for(i=idx; i<pPage->nCell; i++){
    pPage->apCell[i] = pPage->apCell[i+1];
  }
}

/*
** Add a Cell to a database page at the spot indicated by the cursor.
**
** With this routine, we know that the Cell pNewCell will fit into the
** database page that pCur points to.  The calling routine has made
** sure it will fit.  All this routine needs to do is add the Cell
** to the page.  The addToPage() routine should be used for cases
** were it is not known if the new cell will fit.
**
** The new cell is added to the page either before or after the cell
** to which the cursor is pointing.  The new cell is added before
** the cursor cell if pCur->iMatch>0 and the new cell is added after
** the cursor cell if pCur->iMatch<0.  pCur->iMatch should have been set
** by a prior call to sqliteBtreeMoveto() where the key was the key
** of the cell being inserted.  If sqliteBtreeMoveto() ended up on a
** cell that is larger than the key, then pCur->iMatch was set to a
** positive number, hence we insert the new record before the pointer
** if pCur->iMatch is positive.  If sqliteBtreeMaveto() ended up on a
** cell that is smaller than the key then pCur->iMatch was set to a
** negative number, hence we insert the new record after then pointer
** if pCur->iMatch is negative.
*/
static int insertCell(BtCursor *pCur, Cell *pNewCell){
  int sz;
  int idx;
  int i;
  Cell *pCell, *pIdx;
  MemPage *pPage;


  pPage = pCur->pPage;
  sz = cellSize(pNewCell);
  idx = allocateSpace(pPage, sz);
  assert( idx>0 && idx<=SQLITE_PAGE_SIZE - sz );
  pCell = (Cell*)&pPage->aDisk[idx];
  memcpy(pCell, pNewCell, sz);
  pIdx = pPage->aDisk[pCur->idx];
  if( pCur->iMatch<0 ){
    /* Insert the new cell after the cell pCur points to */
    pCell->h.iNext = pIdx->h.iNext;
    pIdx->h.iNext = idx;
    for(i=pPage->nCell-1; i>pCur->idx; i--){
      pPage->apCell[i+1] = pPage->apCell[i];
    }
    pPage->apCell[pCur->idx+1] = pCell;
  }else{
    /* Insert the new cell before the cell pCur points to */
    pCell->h.iNext = pPage->pHdr->firstCell;
    pPage->pHdr->firstCell = idx;
    for(i=pPage->nCell; i>0; i++){
      pPage->apCell[i] = pPage->apCell[i-1];
    }
    pPage->apCell[0] = pCell;
  }
  pPage->nCell++;
  if( pCell->h.leftChild ){
    MemPage *pChild = sqlitepager_lookup(pCur->pBt, pCell->h.leftChild);
    if( pChild && pChild->pParent ){
      sqlitepager_unref(pChild->pParent);
      pChild->pParent = pPage;
      sqlitepager_ref(pChild->pParent);
    }
  }
  return SQLITE_OK;
}

/*
** Insert pNewCell into the database page that pCur is pointing to at
** the place where pCur is pointing.  
**
** This routine works just like insertCell() except that the cell
** to be inserted need not fit on the page.  If the new cell does 
** not fit, then the page sheds data to its siblings to try to get 
** down to a size where the new cell will fit.  If that effort fails,
** then the page is split.
*/
static int addToPage(BtCursor *pCur, Cell *pNewCell){
  Cell tempCell;
  Cell centerCell;

  for(;;){
    MemPage *pPage = pCur->pPage;
    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    int sz = cellSize(pNewCell);
    if( sz<=pPage->nFree ){
      insertCell(pCur, pNewCell);
      return SQLITE_OK;
    }
    if( pPage->pParent==0 ){
      MemPage *pRight;
      PageHdr *pHdr;
      FreeBlk *pFBlk;
      int pc;
      rc = split(pCur, pNewCell, &centerCell, &pRight);
      if( rc ) return rc;
      pHdr = pPage->pHdr;
      pHdr->right = sqlitepager_pagenumber(pRight);
      sqlitepager_unref(pRight);
      pHdr->firstCell = pc = sizeof(*pHdr);
      sz = cellSize(&centerCell);
      memcpy(&pPage->aDisk[pc], &centerCell, sz);
      pc += sz;
      pHdr->firstFree = pc;
      pFBlk = (FreeBlk*)&pPage->aDisk[pc];
      pFBlk->iSize = SQLITE_PAGE_SIZE - pc;
      pFBlk->iNext = 0;
      memset(&pFBlk[1], 0, pFBlk->iSize-sizeof(*pFBlk));
      return SQLITE_OK;
    }
    if( rotateLeft(pCur, sz - pPage->nFree) 
           || rotateRight(pCur, sz - pPage->nFree) ){
      insertCell(pCur, pNewCell);
      return SQLITE_OK;
    }
    rc = split(pCur, pNewCell, &centerCell, 0);
    if( rc ) return rc;
    moveToParent(pCur);
    tempCell = centerCell;
    pNewPage = &tempCell;
  }
  /* NOT REACHED */
}

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what database the record should be inserted into.  The cursor
** is NOT left pointing at the new record.
*/
int sqliteBtreeInsert(
  BtCursor *pCur,            /* Insert data into the table of this cursor */
  void *pKey,  int nKey,     /* The key of the new record */
  void *pData, int nData     /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;

  MemPage *pPage;
  Btree *pBt = pCur->pBt;

  if( !pCur->pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  rc = sqliteBtreeMoveTo(pCur, pKey, nKey, &loc);
  if( rc ) return rc;

  rc = sqlitepager_write(pCur->pPage);
  if( rc ) return rc;
  rc = fillInCell(pBt, &newCell, pKey, nKey, pData, nData);
  if( rc ) return rc;

  if( loc==0 ){
    newCell.h.leftChild = pCur->pPage->apCell[pCur->idx]->h.leftChild;
    rc = clearCell(pBt, pCur->pPage->apCell[pCur->idx]);
    if( rc ) return rc;
    unlinkCell(pCur);
  }
  return addToPage(pCur, &newCell);
}

/*
** Check the page at which the cursor points to see if it is less than
** half full.  If it is less than half full, then try to increase
** its fill factor by grabbing cells from siblings or by merging
** the page with siblings.
*/
static int refillPage(BtCursor *pCur){
  MemPage *pPage;
  BtCursor tempCur;
  int rc;
  Pager *pPager;

  pPage = pCur->pPage;
  if( pPage->nFree < SQLITE_PAGE_SIZE/2 ){
    return SQLITE_OK;
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pPager = pCur->pBt->pPager;

  if( pPage->nCell==0 ){
    /* The page being refilled is the root of the BTree and it has
    ** no entries of its own.  If there is a child page, then make the
    ** child become the new root.
    */
    MemPage *pChild;
    Pgno pgnoChild;
    assert( pPage->pParent==0 );
    assert( sqlitepager_pagenumber(pPage)==pCur->pgnoRoot );
    pgnoChild = ((PageHdr*)pPage)->rightChild;
    if( pgnoChild==0 ){
      return SQLITE_OK;
    }
    rc = sqlitepager_get(pPager, pgno, &pChild);
    if( rc ) return rc;
    memcpy(pPage, pChild, SQLITE_PAGE_SIZE);
    memset(&pPage->aDisk[SQLITE_PAGE_SIZE], 0, EXTRA_SIZE);
    freePage(pCur->pBt, pChild, pgnoChild);
    sqlitepager_unref(pChild);
    rc = initPage(pPage, pCur->pgnoRoot, 0);
    reparentChildPages(pPager, pPage);
    return SQLITE_OK;
  }

  /** merge with siblings **/

  /** borrow from siblings **/
}

/*
** Replace the content of the cell that pCur is pointing to with the content
** in pNewContent.  The pCur cell is not unlinked or moved in the Btree,
** its content is just replaced.
**
** If the size of pNewContent is greater than the current size of the
** cursor cell then the page that cursor points to might have to split.
*/
static int ReplaceContentOfCell(BtCursor *pCur, Cell *pNewContent){
  Cell *pCell;       /* The cell whose content will be changed */
  Pgno pgno;         /* Temporary storage for a page number */

  pCell = pCur->pPage->apCell[pCur->idx];
  rc = clearCell(pCur->pBt, pCell);
  if( rc ) return rc;
  pgno = pNewCell->h.leftChild;
  pNewCell->h.leftChild = pCell->h.leftChild;
  unlinkCell(pCur);
  rc = addToPage(pCur, pNewCell);
  pNewCell->h.leftChild = pgno;
  return rc;
}

/*
** Delete the entry that the cursor is pointing to.
**
** The cursor is left pointing at either the next or the previous

  }
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  rc = sqlitepager_write(pPage);
  if( rc ) return rc;
  pCell = pPage->apCell[pCur->idx];



  if( pPage->pHdr->rightChild ){

    /* The entry to be deleted is not on a leaf page.  Non-leaf entries 

    ** cannot be deleted directly because they have to be present to
    ** hold pointers to subpages.  So what we do is look at the next 
    ** entry in sequence.  The next entry is guaranteed to exist and 
    ** be a leaf.  We copy the payload from the next entry into this
    ** entry, then delete the next entry.
    */
    BtCursor origCur;


    CreateTemporaryCursor(pCur, &origCur);
    rc = sqliteBtreeNext(pCur, 0);
    if( rc==SQLITE_OK ){
      pPage = pCur->pPage;
      pCell = pPage->apCell[pCur->idx];
      rc = ReplaceContentOfCell(&origCur, pCell);
    }
    DestroyTemporaryCursor(&origCur);
    if( rc ) return rc;
  }


  rc = clearCell(pCell);

  if( rc ) return rc;
  unlinkCell(pCur->pBt, pCell);
  if( pCur->idx == 0 ){
    pCur->bSkipNext = 1;



  }else{

    pCur->idx--;
  }
  rc = refillPage(pCur);
  return rc;
}

/*
** Create a new BTree in the same file.  Write into *piTable the index
** of the root page of the new table.
*/

  int rc;
  int i;
  Cell *pCell;
  int idx;

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