/*** Set *pSize to the number of bytes of data in the entry the** cursor currently points to.  Always return SQLITE_OK.** 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.*/static int fileBtreeDataSize(BtCursor *pCur, int *pSize){  Cell *pCell;  MemPage *pPage;  pPage = pCur->pPage;  assert( pPage!=0 );  if( pCur->idx >= pPage->nCell ){    *pSize = 0;  }else{    pCell = pPage->apCell[pCur->idx];    *pSize = NDATA(pCur->pBt, pCell->h);  }  return SQLITE_OK;}/*** Read part of the data associated with cursor pCur.  A maximum** of "amt" bytes will be transfered into zBuf[].  The transfer** begins at "offset".  The number of bytes actually read is** returned.  The amount returned will be smaller than the** amount requested if there are not enough bytes in the data** to satisfy the request.*/static int fileBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){  Cell *pCell;  MemPage *pPage;  assert( amt>=0 );  assert( offset>=0 );  assert( pCur->pPage!=0 );  pPage = pCur->pPage;  if( pCur->idx >= pPage->nCell ){    return 0;  }  pCell = pPage->apCell[pCur->idx];  assert( amt+offset <= NDATA(pCur->pBt, pCell->h) );  getPayload(pCur, offset + NKEY(pCur->pBt, pCell->h), amt, zBuf);  return amt;}/*** Compare an external key against the key on the entry that pCur points to.**** The external key is pKey and is nKey bytes long.  The last nIgnore bytes** of the key associated with pCur are ignored, as if they do not exist.** (The normal case is for nIgnore to be zero in which case the entire** internal key is used in the comparison.)**** The comparison result is written to *pRes as follows:****    *pRes<0    This means pCur<pKey****    *pRes==0   This means pCur==pKey for all nKey bytes****    *pRes>0    This means pCur>pKey**** When one key is an exact prefix of the other, the shorter key is** considered less than the longer one.  In order to be equal the** keys must be exactly the same length. (The length of the pCur key** is the actual key length minus nIgnore bytes.)*/static int fileBtreeKeyCompare(  BtCursor *pCur,       /* Pointer to entry to compare against */  const void *pKey,     /* Key to compare against entry that pCur points to */  int nKey,             /* Number of bytes in pKey */  int nIgnore,          /* Ignore this many bytes at the end of pCur */  int *pResult          /* Write the result here */){  Pgno nextPage;  int n, c, rc, nLocal;  Cell *pCell;  Btree *pBt = pCur->pBt;  const char *zKey  = (const char*)pKey;  assert( pCur->pPage );  assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );  pCell = pCur->pPage->apCell[pCur->idx];  nLocal = NKEY(pBt, pCell->h) - nIgnore;  if( nLocal<0 ) nLocal = 0;  n = nKey<nLocal ? nKey : nLocal;  if( n>MX_LOCAL_PAYLOAD ){    n = MX_LOCAL_PAYLOAD;  }  c = memcmp(pCell->aPayload, zKey, n);  if( c!=0 ){    *pResult = c;    return SQLITE_OK;  }  zKey += n;  nKey -= n;  nLocal -= n;  nextPage = SWAB32(pBt, pCell->ovfl);  while( nKey>0 && nLocal>0 ){    OverflowPage *pOvfl;    if( nextPage==0 ){      return SQLITE_CORRUPT;    }    rc = sqlitepager_get(pBt->pPager, nextPage, (void**)&pOvfl);    if( rc ){      return rc;    }    nextPage = SWAB32(pBt, pOvfl->iNext);    n = nKey<nLocal ? nKey : nLocal;    if( n>OVERFLOW_SIZE ){      n = OVERFLOW_SIZE;    }    c = memcmp(pOvfl->aPayload, zKey, n);    sqlitepager_unref(pOvfl);    if( c!=0 ){      *pResult = c;      return SQLITE_OK;    }    nKey -= n;    nLocal -= n;    zKey += n;  }  if( c==0 ){    c = nLocal - nKey;  }  *pResult = c;  return SQLITE_OK;}/*** Move the cursor down to a new child page.  The newPgno argument is the** page number of the child page in the byte order of the disk image.*/static int moveToChild(BtCursor *pCur, int newPgno){  int rc;  MemPage *pNewPage;  Btree *pBt = pCur->pBt;  newPgno = SWAB32(pBt, newPgno);  rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);  if( rc ) return rc;  rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);  if( rc ) return rc;  assert( pCur->idx>=pCur->pPage->nCell          || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) );  assert( pCur->idx<pCur->pPage->nCell          || pCur->pPage->u.hdr.rightChild==SWAB32(pBt,newPgno) );  pNewPage->idxParent = pCur->idx;  pCur->pPage->idxShift = 0;  sqlitepager_unref(pCur->pPage);  pCur->pPage = pNewPage;  pCur->idx = 0;  if( pNewPage->nCell<1 ){    return SQLITE_CORRUPT;  }  return SQLITE_OK;}/*** Move the cursor up to the parent page.**** pCur->idx is set to the cell index that contains the pointer** to the page we are coming from.  If we are coming from the** right-most child page then pCur->idx is set to one more than** the largest cell index.*/static void moveToParent(BtCursor *pCur){  Pgno oldPgno;  MemPage *pParent;  MemPage *pPage;  int idxParent;  pPage = pCur->pPage;  assert( pPage!=0 );  pParent = pPage->pParent;  assert( pParent!=0 );  idxParent = pPage->idxParent;  sqlitepager_ref(pParent);  sqlitepager_unref(pPage);  pCur->pPage = pParent;  assert( pParent->idxShift==0 );  if( pParent->idxShift==0 ){    pCur->idx = idxParent;#ifndef NDEBUG      /* Verify that pCur->idx is the correct index to point back to the child    ** page we just came from     */    oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));    if( pCur->idx<pParent->nCell ){      assert( pParent->apCell[idxParent]->h.leftChild==oldPgno );    }else{      assert( pParent->u.hdr.rightChild==oldPgno );    }#endif  }else{    /* The MemPage.idxShift flag indicates that cell indices might have     ** changed since idxParent was set and hence idxParent might be out    ** of date.  So recompute the parent cell index by scanning all cells    ** and locating the one that points to the child we just came from.    */    int i;    pCur->idx = pParent->nCell;    oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));    for(i=0; i<pParent->nCell; i++){      if( pParent->apCell[i]->h.leftChild==oldPgno ){        pCur->idx = i;        break;      }    }  }}/*** Move the cursor to the root page*/static int moveToRoot(BtCursor *pCur){  MemPage *pNew;  int rc;  Btree *pBt = pCur->pBt;  rc = sqlitepager_get(pBt->pPager, pCur->pgnoRoot, (void**)&pNew);  if( rc ) return rc;  rc = initPage(pBt, pNew, pCur->pgnoRoot, 0);  if( rc ) return rc;  sqlitepager_unref(pCur->pPage);  pCur->pPage = pNew;  pCur->idx = 0;  return SQLITE_OK;}/*** Move the cursor down to the left-most leaf entry beneath the** entry to which it is currently pointing.*/static int moveToLeftmost(BtCursor *pCur){  Pgno pgno;  int rc;  while( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){    rc = moveToChild(pCur, pgno);    if( rc ) return rc;  }  return SQLITE_OK;}/*** Move the cursor down to the right-most leaf entry beneath the** page to which it is currently pointing.  Notice the difference** between moveToLeftmost() and moveToRightmost().  moveToLeftmost()** finds the left-most entry beneath the *entry* whereas moveToRightmost()** finds the right-most entry beneath the *page*.*/static int moveToRightmost(BtCursor *pCur){  Pgno pgno;  int rc;  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){    pCur->idx = pCur->pPage->nCell;    rc = moveToChild(pCur, pgno);    if( rc ) return rc;  }  pCur->idx = pCur->pPage->nCell - 1;  return SQLITE_OK;}/* Move the cursor to the first entry in the table.  Return SQLITE_OK** on success.  Set *pRes to 0 if the cursor actually points to something** or set *pRes to 1 if the table is empty.*/static int fileBtreeFirst(BtCursor *pCur, int *pRes){  int rc;  if( pCur->pPage==0 ) return SQLITE_ABORT;  rc = moveToRoot(pCur);  if( rc ) return rc;  if( pCur->pPage->nCell==0 ){    *pRes = 1;    return SQLITE_OK;  }  *pRes = 0;  rc = moveToLeftmost(pCur);  pCur->eSkip = SKIP_NONE;  return rc;}/* Move the cursor to the last entry in the table.  Return SQLITE_OK** on success.  Set *pRes to 0 if the cursor actually points to something** or set *pRes to 1 if the table is empty.*/static int fileBtreeLast(BtCursor *pCur, int *pRes){  int rc;  if( pCur->pPage==0 ) return SQLITE_ABORT;  rc = moveToRoot(pCur);  if( rc ) return rc;  assert( pCur->pPage->isInit );  if( pCur->pPage->nCell==0 ){    *pRes = 1;    return SQLITE_OK;  }  *pRes = 0;  rc = moveToRightmost(pCur);  pCur->eSkip = SKIP_NONE;  return rc;}/* Move the cursor so that it points to an entry near pKey.** Return a success code.**** If an exact match is not found, then the cursor is always** left pointing at a leaf page which would hold the entry if it** were present.  The cursor might point to an entry that comes** before or after the key.**** The result of comparing the key with the entry to which the** cursor is left pointing is stored in pCur->iMatch.  The same** value is also written to *pRes if pRes!=NULL.  The meaning of** this value is as follows:****     *pRes<0      The cursor is left pointing at an entry that**                  is smaller than pKey or if the table is empty**                  and the cursor is therefore left point to nothing.****     *pRes==0     The cursor is left pointing at an entry that**                  exactly matches pKey.****     *pRes>0      The cursor is left pointing at an entry that**                  is larger than pKey.*/staticint fileBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes){  int rc;  if( pCur->pPage==0 ) return SQLITE_ABORT;  pCur->eSkip = SKIP_NONE;  rc = moveToRoot(pCur);  if( rc ) return rc;  for(;;){    int lwr, upr;    Pgno chldPg;    MemPage *pPage = pCur->pPage;    int c = -1;  /* pRes return if table is empty must be -1 */    lwr = 0;    upr = pPage->nCell-1;    while( lwr<=upr ){      pCur->idx = (lwr+upr)/2;      rc = fileBtreeKeyCompare(pCur, pKey, nKey, 0, &c);      if( rc ) return rc;      if( c==0 ){        pCur->iMatch = c;        if( pRes ) *pRes = 0;        return SQLITE_OK;      }      if( c<0 ){        lwr = pCur->idx+1;      }else{        upr = pCur->idx-1;      }    }    assert( lwr==upr+1 );    assert( pPage->isInit );    if( lwr>=pPage->nCell ){      chldPg = pPage->u.hdr.rightChild;    }else{      chldPg = pPage->apCell[lwr]->h.leftChild;    }    if( chldPg==0 ){      pCur->iMatch = c;      if( pRes ) *pRes = c;      return SQLITE_OK;    }    pCur->idx = lwr;    rc = moveToChild(pCur, chldPg);    if( rc ) return rc;  }  /* NOT REACHED */}/*** Advance the cursor to the next entry in the database.  If** successful then set *pRes=0.  If the cursor** was already pointing to the last entry in the database before** this routine was called, then set *pRes=1.*/static int fileBtreeNext(BtCursor *pCur, int *pRes){  int rc;  MemPage *pPage = pCur->pPage;  assert( pRes!=0 );  if( pPage==0 ){    *pRes = 1;    return SQLITE_ABORT;  }  assert( pPage->isInit );  assert( pCur->eSkip!=SKIP_INVALID );  if( pPage->nCell==0 ){    *pRes = 1;    return SQLITE_OK;  }  assert( pCur->idx<pPage->nCell );  if( pCur->eSkip==SKIP_NEXT ){    pCur->eSkip = SKIP_NONE;    *pRes = 0;    return SQLITE_OK;  }  pCur->eSkip = SKIP_NONE;  pCur->idx++;  if( pCur->idx>=pPage->nCell ){    if( pPage->u.hdr.rightChild ){      rc = moveToChild(pCur, pPage->u.hdr.rightChild);      if( rc ) return rc;      rc = moveToLeftmost(pCur);      *pRes = 0;      return rc;    }    do{      if( pPage->pParent==0 ){        *pRes = 1;        return SQLITE_OK;      }      moveToParent(pCur);