btree.c

在VC6环境下开发

	int rc;
	Pgno pgno;
	MemPage *pPage;
	pPage = pCur->pPage;
	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;
	}
	if( pCur->eSkip==SKIP_PREV ){
		pCur->eSkip = SKIP_NONE;
		*pRes = 0;
		return eDb_OK;
	}
	pCur->eSkip = SKIP_NONE;
	assert( pCur->idx>=0 );
	if( (pgno = pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
		rc = moveToChild(pCur, pgno);
		if( rc ) return rc;
		rc = moveToRightmost(pCur);
	}else{
		while( pCur->idx==0 ){
			if( pPage->pParent==0 ){
				if( pRes ) *pRes = 1;
				return eDb_OK;
			}
			moveToParent(pCur);
			pPage = pCur->pPage;
		}
		pCur->idx--;
		rc = eDb_OK;
	} 
	*pRes = 0;
	return rc;
}

/*
** Allocate a new page from the database file.
**
** The new page is marked as dirty.  (In other words, eDbpager_write()
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** eDbpager_unref() on the new page when it is done.
**
** eDb_OK is returned on success.  Any other return value indicates
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke eDbpager_unref() on *ppPage if an error is returned.
**
** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "nearby".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.
*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno nearby){
	PageOne *pPage1 = pBt->page1;
	int rc;
	if( pPage1->freeList ){
		OverflowPage *pOvfl;
		FreelistInfo *pInfo;

		rc = eDbpager_write(pPage1);
		if( rc ) return rc;
		SWAB_ADD(pBt, pPage1->nFree, -1);
		rc = eDbpager_get(pBt->pPager, SWAB32(pBt, pPage1->freeList),
							(void**)&pOvfl);
		if( rc ) return rc;
		rc = eDbpager_write(pOvfl);
		if( rc ){
			eDbpager_unref(pOvfl);
			return rc;
		}
		pInfo = (FreelistInfo*)pOvfl->aPayload;
		if( pInfo->nFree==0 ){
		  *pPgno = SWAB32(pBt, pPage1->freeList);
		  pPage1->freeList = pOvfl->iNext;
		  *ppPage = (MemPage*)pOvfl;
		}else{
			int closest, n;
			n = SWAB32(pBt, pInfo->nFree);
			if( n>1 && nearby>0 ){
				int i, dist;
				closest = 0;
				dist = SWAB32(pBt, pInfo->aFree[0]) - nearby;
				if( dist<0 ) dist = -dist;
				for(i=1; i<n; i++){
					int d2 = SWAB32(pBt, pInfo->aFree[i]) - nearby;
					if( d2<0 ) d2 = -d2;
					if( d2<dist ) closest = i;
				}
			}else{
				closest = 0;
			}
			SWAB_ADD(pBt, pInfo->nFree, -1);
			*pPgno = SWAB32(pBt, pInfo->aFree[closest]);
			pInfo->aFree[closest] = pInfo->aFree[n-1];
			rc = eDbpager_get(pBt->pPager, *pPgno, (void**)ppPage);
			eDbpager_unref(pOvfl);
			if( rc==eDb_OK ){
				eDbpager_dont_rollback(*ppPage);
				rc = eDbpager_write(*ppPage);
			}
		}/*end if( pInfo->nFree==0 ) esle*/
	}else{ /*end if( pPage1->freeList ) else*/
		*pPgno = eDbpager_pagecount(pBt->pPager) + 1;
		rc = eDbpager_get(pBt->pPager, *pPgno, (void**)ppPage);
		if( rc ) return rc;
		rc = eDbpager_write(*ppPage);
	}
	return rc;
}

/*
** Add a page of the database file to the freelist.  Either pgno or
** pPage but not both may be 0. 
**
** eDbpager_unref() is NOT called for pPage.
*/
static int freePage(Btree *pBt, void *pPage, Pgno pgno){
	PageOne *pPage1 = pBt->page1;
	OverflowPage *pOvfl = (OverflowPage*)pPage;
	int rc;
	int needUnref = 0;
	MemPage *pMemPage;

	if( pgno==0 ){
		assert( pOvfl!=0 );
		pgno = eDbpager_pagenumber(pOvfl);
	}
	assert( pgno>2 );
	assert( eDbpager_pagenumber(pOvfl)==pgno );
	pMemPage = (MemPage*)pPage;
	pMemPage->isInit = 0;
	if( pMemPage->pParent ){
		eDbpager_unref(pMemPage->pParent);
		pMemPage->pParent = 0;
	}
	rc = eDbpager_write(pPage1);
	if( rc ){
		return rc;
	}
	SWAB_ADD(pBt, pPage1->nFree, 1);
	if( pPage1->nFree!=0 && pPage1->freeList!=0 ){
		OverflowPage *pFreeIdx;
		rc = eDbpager_get(pBt->pPager, SWAB32(pBt, pPage1->freeList),
							(void**)&pFreeIdx);
		if( rc==eDb_OK ){
			FreelistInfo *pInfo = (FreelistInfo*)pFreeIdx->aPayload;
			int n = SWAB32(pBt, pInfo->nFree);
			if( n<(sizeof(pInfo->aFree)/sizeof(pInfo->aFree[0])) ){
				rc = eDbpager_write(pFreeIdx);
				if( rc==eDb_OK ){
					pInfo->aFree[n] = SWAB32(pBt, pgno);
					SWAB_ADD(pBt, pInfo->nFree, 1);
					eDbpager_unref(pFreeIdx);
					eDbpager_dont_write(pBt->pPager, pgno);
					return rc;
				}
			}
			eDbpager_unref(pFreeIdx);
		}
	}
	if( pOvfl==0 ){
		assert( pgno>0 );
		rc = eDbpager_get(pBt->pPager, pgno, (void**)&pOvfl);
		if( rc ) return rc;
		needUnref = 1;
	}
	rc = eDbpager_write(pOvfl);
	if( rc ){
		if( needUnref ) eDbpager_unref(pOvfl);
		return rc;
	}
	pOvfl->iNext = pPage1->freeList;
	pPage1->freeList = SWAB32(pBt, pgno);
	memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
	if( needUnref ) rc = eDbpager_unref(pOvfl);
	return rc;
}

/*
** Erase all the data out of a cell.  This involves returning overflow
** pages back the freelist.
*/
static int clearCell(Btree *pBt, Cell *pCell){
	Pager *pPager = pBt->pPager;
	OverflowPage *pOvfl;
	Pgno ovfl, nextOvfl;
	int rc;

	if( NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h) <= MX_LOCAL_PAYLOAD ){
		return eDb_OK;
	}
	ovfl = SWAB32(pBt, pCell->ovfl);
	pCell->ovfl = 0;
	while( ovfl ){
		rc = eDbpager_get(pPager, ovfl, (void**)&pOvfl);
		if( rc ) return rc;
		nextOvfl = SWAB32(pBt, pOvfl->iNext);
		rc = freePage(pBt, pOvfl, ovfl);
		if( rc ) return rc;
		eDbpager_unref(pOvfl);
		ovfl = nextOvfl;
	}
	return eDb_OK;
}

/*
** Create a new cell from key and data.  Overflow pages are allocated as
** necessary and linked to this cell.  
*/
static int fillInCell(
	Btree *pBt,              /* The whole Btree.  Needed to allocate pages */
	Cell *pCell,             /* Populate this Cell structure */
	const void *pKey, int nKey,    /* The key */
	const void *pData,int nData    /* The data */
){
	OverflowPage *pOvfl, *pPrior;
	Pgno *pNext;
	int spaceLeft;
	int n, rc;
	int nPayload;
	const char *pPayload;
	char *pSpace;
	Pgno nearby = 0;

	pCell->h.leftChild = 0;
	pCell->h.nKey = SWAB16(pBt, (u16)(nKey & 0xffff));
	pCell->h.nKeyHi = nKey >> 16;
	pCell->h.nData = SWAB16(pBt, (u16)(nData & 0xffff));
	pCell->h.nDataHi = nData >> 16;
	pCell->h.iNext = 0;

	pNext = &pCell->ovfl;
	pSpace = pCell->aPayload;
	spaceLeft = MX_LOCAL_PAYLOAD;
	pPayload = pKey;
	pKey = 0;
	nPayload = nKey;
	pPrior = 0;
	while( nPayload>0 ){
		if( spaceLeft==0 ){
			rc = allocatePage(pBt, (MemPage**)&pOvfl, pNext, nearby);
			if( rc ){
				*pNext = 0;
			}else{
				nearby = *pNext;
			}
			if( pPrior ) eDbpager_unref(pPrior);
			if( rc ){
				clearCell(pBt, pCell);
				return rc;
			}
			if( pBt->needSwab ) *pNext = swab32(*pNext);
			pPrior = pOvfl;
			spaceLeft = OVERFLOW_SIZE;
			pSpace = pOvfl->aPayload;
			pNext = &pOvfl->iNext;
		}
		n = nPayload;
		if( n>spaceLeft ) n = spaceLeft;
		memcpy(pSpace, pPayload, n);
		nPayload -= n;
		if( nPayload==0 && pData ){
			pPayload = pData;
			nPayload = nData;
			pData = 0;
		}else{
			pPayload += n;
		}
		spaceLeft -= n;
		pSpace += n;
	} /*end while( nPayload>0 )*/
	*pNext = 0;
	if( pPrior ){
		eDbpager_unref(pPrior);
	}
	return eDb_OK;
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static void reparentPage(Pager *pPager, Pgno pgno, MemPage *pNewParent,int idx){
	MemPage *pThis;

	if( pgno==0 ) return;
	assert( pPager!=0 );
	pThis = eDbpager_lookup(pPager, pgno);
	if( pThis && pThis->isInit ){
		if( pThis->pParent!=pNewParent ){
			if( pThis->pParent ) eDbpager_unref(pThis->pParent);
			pThis->pParent = pNewParent;
			if( pNewParent ) eDbpager_ref(pNewParent);
		}
		pThis->idxParent = idx;
		eDbpager_unref(pThis);
	}
}

/*
** Reparent all children of the given page to be the given page.
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(Btree *pBt, MemPage *pPage){
	int i;
	Pager *pPager = pBt->pPager;
	for(i=0; i<pPage->nCell; i++){
		reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage, i);
	}
	reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), pPage, i);
	pPage->idxShift = 0;
}

/*
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
** removes the reference to the cell from pPage.
**
** "sz" must be the number of bytes in the cell.
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void dropCell(Btree *pBt, MemPage *pPage, int idx, int sz){
	int j;
	assert( idx>=0 && idx<pPage->nCell );
	assert( sz==cellSize(pBt, pPage->apCell[idx]) );
	assert( eDbpager_iswriteable(pPage) );
	freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);
	for(j=idx; j<pPage->nCell-1; j++){
		pPage->apCell[j] = pPage->apCell[j+1];
	}
	pPage->nCell--;
	pPage->idxShift = 1;
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it
** will not fit, then just make pPage->apCell[i] point to the content
** and set pPage->isOverfull.  
**
** Do not bother maintaining the integrity of the linked list of Cells.
** Only the pPage->apCell[] array is important.  The relinkCellList() 
** routine will be called soon after this routine in order to rebuild 
** the linked list.
*/
static void insertCell(Btree *pBt, MemPage *pPage, int i, Cell *pCell, int sz){
	int idx, j;
	assert( i>=0 && i<=pPage->nCell );
	assert( sz==cellSize(pBt, pCell) );
	assert( eDbpager_iswriteable(pPage) );
	idx = allocateSpace(pBt, pPage, sz);
	for(j=pPage->nCell; j>i; j--){
		pPage->apCell[j] = pPage->apCell[j-1];
	}
	pPage->nCell++;
	if( idx<=0 ){
		pPage->isOverfull = 1;
		pPage->apCell[i] = pCell;
	}else{
		memcpy(&pPage->u.aDisk[idx], pCell, sz);
		pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
	}
	pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->apCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
*/
static void relinkCellList(Btree *pBt, MemPage *pPage){
	int i;
	u16 *pIdx;
	assert( eDbpager_iswriteable(pPage) );
	pIdx = &pPage->u.hdr.firstCell;
	for(i=0; i<pPage->nCell; i++){
		int idx = Addr(pPage->apCell[i]) - Addr(pPage);
		assert( idx>0 && idx<eDb_USABLE_SIZE );
		*pIdx = SWAB16(pBt, idx);
		pIdx = &pPage->apCell[i]->h.iNext;
	}
	*pIdx = 0;
}

/*
** Make a copy of the contents of pFrom into pTo.  The pFrom->apCell[]
** pointers that point into pFrom->u.aDisk[] must be adjusted to point
** into pTo->u.aDisk[] instead.  But some pFrom->apCell[] entries might
** not point to pFrom->u.aDisk[].  Those are unchanged.
*/
static void copyPage(MemPage *pTo, MemPage *pFrom){
	uptr from, to;
	int i;
	memcpy(pTo->u.aDisk, pFrom->u.aDisk, eDb_USABLE_SIZE);
	pTo->pParent = 0;
	pTo->isInit = 1;
	pTo->nCell = pFrom->nCell;
	pTo->nFree = pFrom->nFree;
	pTo->isOverfull = pF