SQLite

/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.131 2004/05/13 01:12:57 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.

** of that header is as follows:
**
**   OFFSET   SIZE    DESCRIPTION
**      0      16     Header string: "SQLite format 3\000"
**     16       2     Page size in bytes.  
**     18       1     File format write version
**     19       1     File format read version
**     20       1     Bytes of unused space at the end of each page
**     21       1     Max embedded payload fraction
**     22       1     Min embedded payload fraction
**     23       1     Min leaf payload fraction
**     24       4     File change counter
**     28       4     Reserved for future use
**     32       4     First freelist page
**     36       4     Number of freelist pages in the file
**     40      60     15 4-byte meta values passed to higher layers
**
** All of the integer values are big-endian (most significant byte first).
**
** The file change counter is incremented every time the database is more
** than once within the same second.  This counter, together with the
** modification time of the file, allows other processes to know
** when the file has changed and thus when they need to flush their
** cache.
**
** The max embedded payload fraction is the amount of the total usable
** space in a page that can be consumed by a single cell for standard
** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
** is to limit the maximum cell size so that at least 4 cells will fit
** on one pages.  Thus the default max embedded payload fraction is 64.
**
** If the payload for a cell is larger than the max payload, then extra
** payload is spilled to overflow pages.  Once an overflow page is allocated,
** as many bytes as possible are moved into the overflow pages without letting
** the cell size drop below the min embedded payload fraction.
**
** The min leaf payload fraction is like the min embedded payload fraction
** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
** not specified in the header.
**
** Each btree page begins with a header described below.  Note that the
** header for page one begins at byte 100.  For all other btree pages, the
** header begins on byte zero.
**
**   OFFSET   SIZE     DESCRIPTION
**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
**      1       2      byte offset to the first freeblock
**      3       2      byte offset to the first cell
**      5       1      number of fragmented free bytes
**      6       4      Right child (the Ptr(N+1) value).  Omitted if leaf
**
** The flags define the format of this btree page.  The leaf flag means that
** this page has no children.  The zerodata flag means that this page carries
** only keys and no data.  The intkey flag means that the key is a single
** variable length integer at the beginning of the payload.
**
** A variable-length integer is 1 to 9 bytes where the lower 7 bits of each 
** byte are used.  The integer consists of all bytes that have bit 8 set and
** the first byte with bit 8 clear.  The most significant byte of the integer
** appears first.
**
**    0x00                      becomes  0x00000000
**    0x7f                      becomes  0x0000007f
**    0x81 0x00                 becomes  0x00000080
**    0x82 0x00                 becomes  0x00000100
**    0x80 0x7f                 becomes  0x0000007f
**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
**
** Variable length integers are used for rowids and to hold the number of
** bytes of key and data in a btree cell.
**
** Unused space within a btree page is collected into a linked list of
** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset

** or any machine where memory and especially stack memory is limited,
** one may wish to chose a smaller value for the maximum page size.
*/
#ifndef MX_PAGE_SIZE
# define MX_PAGE_SIZE 1024
#endif







/* The following value is the maximum cell size assuming a maximum page
** size give above.
*/
#define MX_CELL_SIZE  (MX_PAGE_SIZE-10)

/* The maximum number of cells on a single page of the database.  This
** assumes a minimum cell size of 3 bytes.  Such small cells will be
** exceedingly rare, but they are possible.
*/
#define MX_CELL ((MX_PAGE_SIZE-10)/3)

  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* A list of all open cursors */
  MemPage *pPage1;      /* First page of the database */
  u8 inTrans;           /* True if a transaction is in progress */
  u8 inStmt;            /* True if there is a checkpoint on the transaction */
  u8 readOnly;          /* True if the underlying file is readonly */
  int pageSize;         /* Number of usable bytes on each page */
  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
};
typedef Btree Bt;

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.

  int idx;                  /* Index of the entry in pPage->aCell[] */
  u8 wrFlag;                /* True if writable */
  u8 iMatch;                /* compare result from last sqlite3BtreeMoveto() */
  u8 isValid;               /* TRUE if points to a valid entry */
  u8 status;                /* Set to SQLITE_ABORT if cursors is invalidated */
};

/*
** An instance of the following structure is used to hold information
** about a cell.  The parseCell() function fills the structure in.
*/
typedef struct CellInfo CellInfo;
struct CellInfo {
  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
  u32 nData;     /* Number of bytes of data */
  int nHeader;   /* Size of the header in bytes */
  int nLocal;    /* Amount of payload held locally */
  int iOverflow; /* Offset to overflow page number.  Zero if none */
  int nSize;     /* Size of the cell */
};

/*
** Read or write a two-, four-, and eight-byte big-endian integer values.
*/
static u32 get2byte(unsigned char *p){
  return (p[0]<<8) | p[1];
}
static u32 get4byte(unsigned char *p){
  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
}




static void put2byte(unsigned char *p, u32 v){
  p[0] = v>>8;
  p[1] = v;
}
static void put4byte(unsigned char *p, u32 v){
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}

#if 0 /* NOT_USED */
static u64 get8byte(unsigned char *p){
  u64 v = get4byte(p);
  return (v<<32) | get4byte(&p[4]);
}
static void put8byte(unsigned char *p, u64 v){
  put4byte(&p[4], v>>32);
  put4byte(p, v);
}
#endif

/*
** Read a variable-length integer.  Store the result in *pResult.
** Return the number of bytes in the integer.
*/
static unsigned int getVarint(unsigned char *p, u64 *pResult){
  u64 x = 0;
  int n = 0;
  unsigned char c;
  do{
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }while( (c & 0x80)!=0 );
  *pResult = x;
  return n;
}
static unsigned int getVarint32(unsigned char *p, u32 *pResult){
  u32 x = 0;
  int n = 0;
  unsigned char c;
  do{
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }while( (c & 0x80)!=0 );
  *pResult = x;
  return n;
}

/*
** Write a variable length integer with value v into p[].  Return
** the number of bytes written.
*/
static unsigned int putVarint(unsigned char *p, u64 v){
  int i, j, n;
  u8 buf[10];
  n = 0;
  do{
    buf[n++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  buf[0] &= 0x7f;
  for(i=0, j=n-1; j>=0; j--, i++){
    p[i] = buf[j];
  }
  return n;
}

/*
** Parse a cell header and fill in the CellInfo structure.
*/
static void parseCell(
  MemPage *pPage,         /* Page containing the cell */
  unsigned char *pCell,   /* The cell */
  CellInfo *pInfo         /* Fill in this structure */


){
  int n;
  int nPayload;
  Btree *pBt;
  int minLocal, maxLocal;
  if( pPage->leaf ){
    n = 2;
  }else{
    n = 6;
  }
  if( pPage->hasData ){
    n += getVarint32(&pCell[n], &pInfo->nData);
  }else{
    pInfo->nData = 0;
  }
  n += getVarint(&pCell[n], &pInfo->nKey);
  pInfo->nHeader = n;
  nPayload = pInfo->nData;
  if( !pPage->intKey ){
    nPayload += pInfo->nKey;
  }
  pBt = pPage->pBt;
  if( pPage->leafData ){
    minLocal = pBt->minLeaf;
    maxLocal = pBt->pageSize - 23;
  }else{
    minLocal = pBt->minLocal;
    maxLocal = pBt->maxLocal;
  }
  if( nPayload<=maxLocal ){
    pInfo->nLocal = nPayload;
    pInfo->iOverflow = 0;
    pInfo->nSize = nPayload + n;
  }else{
    int surplus = minLocal + (nPayload - minLocal)%(pBt->pageSize - 4);
    if( surplus <= maxLocal ){
      pInfo->nLocal = surplus;
    }else{
      pInfo->nLocal = minLocal;
    }
    pInfo->iOverflow = pInfo->nLocal + n;
    pInfo->nSize = pInfo->iOverflow + 4;
  }
}

/*
** Compute the total number of bytes that a Cell needs on the main
** database page.  The number returned includes the Cell header,
** local payload storage, and the pointer to overflow pages (if
** applicable).  Additional space allocated on overflow pages
** is NOT included in the value returned from this routine.
*/
static int cellSize(MemPage *pPage, unsigned char *pCell){
  CellInfo info;




  parseCell(pPage, pCell, &info);








  return info.nSize;
}

/*
** Do sanity checking on a page.  Throw an exception if anything is
** not right.
**
** This routine is used for internal error checking only.  It is omitted

    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->maxEmbedFrac = 64;            /* FIX ME - read from header */
  pBt->minEmbedFrac = 32;            /* FIX ME - read from header */
  pBt->minLeafFrac = 32;             /* 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 minFanout
  ** cells can 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
  ** So a cell consists of a header which is as much as 19 bytes long,
  ** 0 to N bytes of payload, and an optional 4 byte overflow page pointer.
  */
  assert(pBt->maxEmbedFrac>0 && 255/pBt->maxEmbedFrac>=3 );
  pBt->maxLocal = (pBt->pageSize-10)*pBt->maxEmbedFrac/255 - 23;
  pBt->minLocal = (pBt->pageSize-10)*pBt->minEmbedFrac/255 - 23;
  pBt->maxLeaf = pBt->pageSize - 33;
  pBt->minLeaf = (pBt->pageSize-10)*pBt->minLeafFrac/255 - 23;

  assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE );
  *ppBtree = pBt;
  return SQLITE_OK;
}

/*
** Close an open database and invalidate all cursors.
*/

** Failure is not possible.  If the cursor is not currently
** pointing to an entry (which can happen, for example, if
** the database is empty) then *pSize is set to 0.
*/
int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
  MemPage *pPage;
  unsigned char *cell;


  if( !pCur->isValid ){
    return pCur->status ? pCur->status : SQLITE_INTERNAL;
  }
  pPage = pCur->pPage;
  assert( pPage!=0 );
  assert( pPage->isInit );
  pageIntegrity(pPage);
  if( !pPage->hasData ){
    *pSize = 0;
  }else{
    assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
    cell = pPage->aCell[pCur->idx];
    cell += 2;   /* Skip the offset to the next cell */
    if( !pPage->leaf ){
      cell += 4;  /* Skip the child pointer */
    }
    getVarint32(cell, pSize);


  }
  return SQLITE_OK;
}

/*
** Read payload information from the entry that the pCur cursor is
** pointing to.  Begin reading the payload at "offset" and read

  int skipKey          /* offset begins at data if this is true */
){
  unsigned char *aPayload;
  Pgno nextPage;
  int rc;
  MemPage *pPage;
  Btree *pBt;


  int ovflSize;
  CellInfo info;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];


  parseCell(pPage, aPayload, &info);


  aPayload += info.nHeader;




  if( pPage->intKey ){
    info.nKey = 0;
  }
  assert( offset>=0 );
  if( skipKey ){
    offset += info.nKey;
  }
  if( offset+amt > info.nKey+info.nData ){
    return SQLITE_ERROR;
  }

  if( offset<info.nLocal ){
    int a = amt;
    if( a+offset>info.nLocal ){
      a = info.nLocal - offset;
    }
    memcpy(pBuf, &aPayload[offset], a);
    if( a==amt ){
      return SQLITE_OK;
    }
    offset = 0;
    pBuf += a;
    amt -= a;
  }else{
    offset -= info.nLocal;
  }
  if( amt>0 ){
    nextPage = get4byte(&aPayload[info.nLocal]);
  }
  ovflSize = pBt->pageSize - 4;
  while( amt>0 && nextPage ){
    rc = sqlite3pager_get(pBt->pPager, nextPage, (void**)&aPayload);
    if( rc!=0 ){
      return rc;
    }

  BtCursor *pCur,      /* Cursor pointing to entry to read from */
  int amt,             /* Amount requested */
  int skipKey          /* read beginning at data if this is true */
){
  unsigned char *aPayload;
  MemPage *pPage;
  Btree *pBt;


  CellInfo info;

  assert( pCur!=0 && pCur->pPage!=0 );
  assert( pCur->isValid );
  pBt = pCur->pBt;
  pPage = pCur->pPage;
  pageIntegrity(pPage);
  assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
  aPayload = pPage->aCell[pCur->idx];


  parseCell(pPage, aPayload, &info);


  aPayload += info.nHeader;




  if( pPage->intKey ){
    info.nKey = 0;
  }

  if( skipKey ){
    aPayload += info.nKey;
    info.nLocal -= info.nKey;
    if( amt<0 ) amt = info.nData;
    assert( amt<=info.nData );
  }else{
    if( amt<0 ) amt = info.nKey;
    assert( amt<=info.nKey );
  }
  if( amt>info.nLocal ){
    return 0;  /* If any of the data is not local, return nothing */
  }
  return aPayload;
}


/*

}

/*
** Free any overflow pages associated with the given Cell.
*/
static int clearCell(MemPage *pPage, unsigned char *pCell){
  Btree *pBt = pPage->pBt;
  CellInfo info;


  Pgno ovflPgno;
  int rc;

  parseCell(pPage, pCell, &info);


  if( info.iOverflow==0 ){



    return SQLITE_OK;  /* No overflow pages. Return without doing anything */
  }
  ovflPgno = get4byte(&pCell[info.iOverflow]);
  while( ovflPgno!=0 ){
    MemPage *pOvfl;
    rc = getPage(pBt, ovflPgno, &pOvfl);
    if( rc ) return rc;
    ovflPgno = get4byte(pOvfl->aData);
    rc = freePage(pOvfl);
    if( rc ) return rc;

  MemPage *pOvfl = 0;
  MemPage *pToRelease = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;
  CellInfo info;

  /* Fill in the header. */
  nHeader = 2;
  if( !pPage->leaf ){
    nHeader += 4;
  }
  if( pPage->hasData ){
    nHeader += putVarint(&pCell[nHeader], nData);
  }else{
    nData = 0;
  }
  nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
  parseCell(pPage, pCell, &info);
  assert( info.nHeader==nHeader );
  assert( info.nKey==nKey );
  assert( info.nData==nData );
  
  /* Fill in the payload */



  nPayload = nData;
  if( pPage->intKey ){
    pSrc = pData;
    nSrc = nData;
    nData = 0;
  }else{
    nPayload += nKey;
    pSrc = pKey;
    nSrc = nKey;
  }



  *pnSize = info.nSize;

  spaceLeft = info.nLocal;
  pPayload = &pCell[nHeader];
  pPrior = &pCell[info.iOverflow];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc =  allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
      if( rc ){
        releasePage(pToRelease);
        clearCell(pPage, pCell);

      int sz;
      pCell = apCell[j];
      sz = szCell[j] + leafCorrection;
      if( !pNew->leaf ){
        memcpy(&pNew->aData[6], pCell+2, 4);
        pTemp = 0;
      }else if( leafData ){


        CellInfo info;
        j--;
        parseCell(pNew, apCell[j], &info);
        pCell = aInsBuf[i];
        fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = aInsBuf[i];
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);
      put4byte(&pParent->aCell[nxDiv][2], pNew->pgno);

  printf("PAGE %d:  flags=0x%02x  frag=%d   parent=%d\n", pgno,
    data[hdr], data[hdr+5], 
    (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
  i = 0;
  assert( hdr == (pgno==1 ? 100 : 0) );
  idx = get2byte(&data[hdr+3]);
  while( idx>0 && idx<=pBt->pageSize ){


    CellInfo info;
    Pgno child;
    unsigned char *pCell = &data[idx];
    int sz;

    pCell = &data[idx];
    parseCell(pPage, pCell, &info);
    sz = info.nSize;
    sprintf(range,"%d..%d", idx, idx+sz-1);

    if( pPage->leaf ){
      child = 0;
    }else{
      child = get4byte(&pCell[2]);
    }
    sz = info.nData;
    if( !pPage->intKey ) sz += info.nKey;
    if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
    memcpy(payload, &pCell[info.nHeader], 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=%-4lld nd=%-4d payload=%s\n",
      i, range, child, info.nKey, info.nData, payload
    );
    if( pPage->isInit && pPage->aCell[i]!=pCell ){
      printf("**** aCell[%d] does not match on prior entry ****\n", i);
    }
    i++;
    idx = get2byte(pCell);
  }

      N -= n;
    }
    iPage = get4byte(pOvfl);
    sqlite3pager_unref(pOvfl);
  }
}


















/*
** Do various sanity checks on a single page of a tree.  Return
** the tree depth.  Root pages return 0.  Parents of root pages
** return 1, and so forth.
** 
** These checks are done:
**

  char *zUpperBound,    /* All keys should be less than this, if not NULL */
  int nUpper            /* Number of characters in zUpperBound */
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr;
  u8 *data;


  BtCursor cur;
  Btree *pBt;
  int maxLocal, pageSize;
  char zMsg[100];
  char zContext[100];
  char hit[MX_PAGE_SIZE];

  /* Check that the page exists
  */
  cur.pBt = pBt = pCheck->pBt;

  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;
  }
  maxLocal = pPage->leafData ? pBt->maxLeaf : pBt->maxLocal;
  if( (rc = initPage(pPage, pParent))!=0 ){
    sprintf(zMsg, "initPage() returns error code %d", rc);
    checkAppendMsg(pCheck, zContext, zMsg);
    releasePage(pPage);
    return 0;
  }

  /* Check out all the cells.
  */
  depth = 0;
  cur.pPage = pPage;
  for(i=0; i<pPage->nCell; i++){
    u8 *pCell;


    int sz;
    CellInfo info;

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

    /* Check sanity of left child page.
    */
    if( !pPage->leaf ){
      pgno = get4byte(&pCell[2]);
      d2 = checkTreePage(pCheck,pgno,pPage,zContext,0,0,0,0);