btree.c

sqlite数据库管理系统开放源码

}

/*
** 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.
*/
static
int 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;
      }