btree.c

在VC6环境下开发

	}
	return eDb_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 eDb_OK;
	}
	zKey += n;
	nKey -= n;
	nLocal -= n;
	nextPage = SWAB32(pBt, pCell->ovfl);
	while( nKey>0 && nLocal>0 ){
		OverflowPage *pOvfl;
		if( nextPage==0 ){
			return eDb_CORRUPT;
		}
		rc = eDbpager_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);
		eDbpager_unref(pOvfl);
		if( c!=0 ){
			*pResult = c;
			return eDb_OK;
		}
		nKey -= n;
		nLocal -= n;
		zKey += n;
	}
	if( c==0 ){
		c = nLocal - nKey;
	}
	*pResult = c;
	return eDb_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 = eDbpager_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;
	eDbpager_unref(pCur->pPage);
	pCur->pPage = pNewPage;
	pCur->idx = 0;
	if( pNewPage->nCell<1 ){
		return eDb_CORRUPT;
	}
	return eDb_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;
	eDbpager_ref(pParent);
	eDbpager_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, eDbpager_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, eDbpager_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 = eDbpager_get(pBt->pPager, pCur->pgnoRoot, (void**)&pNew);
	if( rc ) return rc;
	rc = initPage(pBt, pNew, pCur->pgnoRoot, 0);
	if( rc ) return rc;
	eDbpager_unref(pCur->pPage);
	pCur->pPage = pNew;
	pCur->idx = 0;
	return eDb_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 eDb_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 eDb_OK;
}

/* Move the cursor to the first entry in the table.  Return eDb_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 eDb_ABORT;
	rc = moveToRoot(pCur);
	if( rc ) return rc;
	if( pCur->pPage->nCell==0 ){
		*pRes = 1;
		return eDb_OK;
	}
	*pRes = 0;
	rc = moveToLeftmost(pCur);
	pCur->eSkip = SKIP_NONE;
	return rc;
}

/* Move the cursor to the last entry in the table.  Return eDb_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 eDb_ABORT;
	rc = moveToRoot(pCur);
	if( rc ) return rc;
	assert( pCur->pPage->isInit );
	if( pCur->pPage->nCell==0 ){
		*pRes = 1;
		return eDb_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 eDb_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 eDb_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 eDb_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 eDb_ABORT;
	}
	assert( pPage->isInit );
	//assert( pCur->eSkip!=SKIP_INVALID );
	if( pPage->nCell==0 ){
		*pRes = 1;
		return eDb_OK;
	}
	//assert( pCur->idx<pPage->nCell );
	if( pCur->eSkip==SKIP_NEXT ){
		pCur->eSkip = SKIP_NONE;
		*pRes = 0;
		return eDb_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 eDb_OK;
			}
			moveToParent(pCur);
			pPage = pCur->pPage;
		}while( pCur->idx>=pPage->nCell );
		*pRes = 0;
		return eDb_OK;
	}/*end if(pCur->idx>=pPage->nCell)*/
	*pRes = 0;
	if( pPage->u.hdr.rightChild==0 ){
		return eDb_OK;
	}
	rc = moveToLeftmost(pCur);
	return rc;
}

/*
** Step the cursor to the back to the previous entry in the database.  If
** successful then set *pRes=0.  If the cursor
** was already pointing to the first entry in the database before
** this routine was called, then set *pRes=1.
*/
static int fileBtreePrevious(BtCursor *pCur, int *pRes){