gdatabase.cpp

一个非常有用的开源代码

	// Get the right page
	GDBPage* pPage = pChapter->m_pPages[nPage];
	if(!pPage)
	{
		// Load the new page
		pPage = new GDBPage(nPos & (~BYTES_IN_PAGE_MASK));
		pChapter->m_pPages[nPage] = pPage;
		fseek(m_pFile, nPos & (~BYTES_IN_PAGE_MASK), SEEK_SET); // todo: check for errors
		fread(pPage->m_data, GDB_PAGE_SIZE, 1, m_pFile); // todo: check for errors

		// Throw out an old page (if necessary)
		if(m_nPageCacheSize > PAGES_TO_CACHE)
		{
			GDBPage* pCondemnedPage = m_pLeastRecentlyUsedPage;
			m_pLeastRecentlyUsedPage = m_pLeastRecentlyUsedPage->m_pPrev;
			if(m_pLeastRecentlyUsedPage)
				m_pLeastRecentlyUsedPage->m_pNext = NULL;
			m_nPageCacheSize--;
			FlushPage(pCondemnedPage);

			// Remove page from the chapter
			int nPage2 = pCondemnedPage->m_nPos >> BITS_IN_PAGE_SIZE;
			int nChapter2 = nPage2 >> BITS_IN_CHAPTER_SIZE;
			nPage2 &= PAGE_IN_CHAPTER_MASK;
			GDBChapterLookup tmp(nChapter2);
			int nIndex;
			pChapter = (GDBChapter*)m_pChapters->GetNode(&tmp, &nIndex);
			GAssert(pChapter, "Chapter for condemned page not found");
			GAssert(pChapter->m_pPages[nPage2] == pCondemnedPage, "Condemned page not in chapter");
			pChapter->m_pPages[nPage2] = NULL;

			// Delete the page
			delete(pCondemnedPage);
		}
	}

	// Move this page to the front of the list
	GAssert(pPage, "Should have found the page by now");
	if(m_pMostRecentlyUsedPage != pPage)
	{
		if(pPage->m_pPrev)
			pPage->m_pPrev->m_pNext = pPage->m_pNext;
		if(m_pLeastRecentlyUsedPage == pPage)
		{
			m_pLeastRecentlyUsedPage = pPage->m_pPrev;
			GAssert(pPage->m_pNext == NULL, "not the last in the list");
		}
		else if(pPage->m_pNext)
			pPage->m_pNext->m_pPrev = pPage->m_pPrev;
		pPage->m_pNext = m_pMostRecentlyUsedPage;
		pPage->m_pPrev = NULL;
		if(m_pMostRecentlyUsedPage)
			m_pMostRecentlyUsedPage->m_pPrev = pPage;
		m_pMostRecentlyUsedPage = pPage;
		if(!m_pLeastRecentlyUsedPage)
			m_pLeastRecentlyUsedPage = pPage;
	}

	return pPage;
}

bool GDataBase::Read(char* pBuf, int nPos, int nSize)
{
	GAssert(nPos > 0 || (nPos == 0 && nSize == sizeof(int)), "out of range (727)");
	while(nSize > 0)
	{
		GDBPage* pPage = GetPage(nPos);
		int nBytesForThisPage;
		if((nPos & BYTES_IN_PAGE_MASK) + nSize > GDB_PAGE_SIZE)
			nBytesForThisPage = GDB_PAGE_SIZE - (nPos & BYTES_IN_PAGE_MASK);
		else
			nBytesForThisPage = nSize;
		memcpy(pBuf, &pPage->m_data[nPos & BYTES_IN_PAGE_MASK], nBytesForThisPage);
		pBuf += nBytesForThisPage;
		nPos += nBytesForThisPage;
		nSize -= nBytesForThisPage;
	}
	return true;
}

bool GDataBase::Write(const char* pBuf, int nPos, int nSize)
{
	GAssert(nPos > 0 || (nPos == 0 && nSize == sizeof(int)), "out of range (728)");
	while(nSize > 0)
	{
		GDBPage* pPage = GetPage(nPos);
		pPage->m_bDirty = true;
		int nBytesForThisPage;
		if((nPos & BYTES_IN_PAGE_MASK) + nSize > GDB_PAGE_SIZE)
			nBytesForThisPage = GDB_PAGE_SIZE - (nPos & BYTES_IN_PAGE_MASK);
		else
			nBytesForThisPage = nSize;
		memcpy(&pPage->m_data[nPos & BYTES_IN_PAGE_MASK], pBuf, nBytesForThisPage);
		pBuf += nBytesForThisPage;
		nPos += nBytesForThisPage;
		nSize -= nBytesForThisPage;
	}
	return true;
}

// -------------------------------------------------------------------
// AVL Tree methods
// -------------------------------------------------------------------

void GDataBase::GetChildrenHeights(struct GDBValue* pVal, int* pnLeft, int* pnRight)
{
	struct GDBValue valTmp;

	// Left
	*pnLeft = 0;
	if(pVal->nLeft)
	{
		if(!Read((char*)&valTmp, pVal->nLeft, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read while fixing height");
			valTmp.nHeight = 1; // guess (best hope for recovery)
		}
		*pnLeft = valTmp.nHeight;
	}

	// Right
	*pnRight = 0;
	if(pVal->nRight)
	{
		if(!Read((char*)&valTmp, pVal->nRight, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read while fixing height");
			valTmp.nHeight = 1; // guess (best hope for recovery)
		}
		*pnRight = valTmp.nHeight;
	}
}

void GDataBase::FixHeight(struct GDBValue* pVal)
{
	int nLeftHeight;
	int nRightHeight;
	GetChildrenHeights(pVal, &nLeftHeight, &nRightHeight);
	pVal->nHeight = MAX(nLeftHeight, nRightHeight) + 1;
}

// This method must be kept in sync with RotateRight
int GDataBase::RotateLeft(int nPos, GDBValue* pVal)
{
	// Read in right record
	int nRightPos = pVal->nRight;
	if(nRightPos <= 0)
	{
		GAssert(false, "Can't rotate left if there's no right child");
		return 0;
	}
	struct GDBValue valRight;
	if(!Read((char*)&valRight, nRightPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to read while rotating");
		return 0;
	}

	// Do the rotation
	int nTmp = valRight.nLeft;
	valRight.nLeft = nPos;
	int nOldPar = pVal->nParent;
	pVal->nParent = nRightPos;
	valRight.nParent = nOldPar;
	pVal->nRight = nTmp;
	if(nTmp > 0)
		WriteIntValue(nTmp + MEMBEROFFSET(struct GDBValue, nParent), nPos);
	FixHeight(pVal);
	if(!Write((char*)pVal, nPos, sizeof(struct GDBValue)))
		GAssert(false, "failed to write while rotating");
	FixHeight(&valRight);
	if(!Write((char*)&valRight, nRightPos, sizeof(struct GDBValue)))
		GAssert(false, "failed to write while rotating");

	return nRightPos;
}

// This method must be kept in sync with RotateLeft
int GDataBase::RotateRight(int nPos, GDBValue* pVal)
{
	// Read in left record
	int nLeftPos = pVal->nLeft;
	if(nLeftPos <= 0)
	{
		GAssert(false, "Can't rotate right if there's no left child");
		return 0;
	}
	struct GDBValue valLeft;
	if(!Read((char*)&valLeft, nLeftPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to read while rotating");
		return 0;
	}

	// Do the rotation
	int nTmp = valLeft.nRight;
	valLeft.nRight = nPos;
	int nOldPar = pVal->nParent;
	pVal->nParent = nLeftPos;
	valLeft.nParent = nOldPar;
	pVal->nLeft = nTmp;
	if(nTmp > 0)
		WriteIntValue(nTmp + MEMBEROFFSET(struct GDBValue, nParent), nPos);
	FixHeight(pVal);
	if(!Write((char*)pVal, nPos, sizeof(struct GDBValue)))
		GAssert(false, "failed to write while rotating");
	FixHeight(&valLeft);
	if(!Write((char*)&valLeft, nLeftPos, sizeof(struct GDBValue)))
		GAssert(false, "failed to write while rotating");

	return nLeftPos;
}

int GDataBase::Balance(int nPos, GDBValue* pVal)
{
	int nLeft = 0;
	int nRight = 0;
	GetChildrenHeights(pVal, &nLeft, &nRight);
	int nBal = nRight - nLeft;
	if(nBal > 1)
	{
		// Load the right child
		struct GDBValue valRight;
		if(!Read((char*)&valRight, pVal->nRight, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read while balancing");
			return 0;
		}

		// Rotate the right child right (if necessary)
		int nLeftHeight = 0;
		int nRightHeight = 0;
		GetChildrenHeights(&valRight, &nLeftHeight, &nRightHeight);
		if(nRightHeight - nLeftHeight < 0)
			pVal->nRight = RotateRight(pVal->nRight, &valRight);

		// Rotate left
		return RotateLeft(nPos, pVal);
	}
	if(nBal < -1)
	{
		// Load the right child
		struct GDBValue valLeft;
		if(!Read((char*)&valLeft, pVal->nLeft, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read while balancing");
			return 0;
		}

		// Rotate the right child right (if necessary)
		int nLeftHeight = 0;
		int nRightHeight = 0;
		GetChildrenHeights(&valLeft, &nLeftHeight, &nRightHeight);
		if(nRightHeight - nLeftHeight > 0)
			pVal->nLeft = RotateLeft(pVal->nLeft, &valLeft);

		// Rotate left
		return RotateRight(nPos, pVal);
	}

	// This method guarantees to write out the value, so do it now
	if(!Write((const char*)pVal, nPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to write while balancing");
		return 0;
	}

	return nPos;
}

bool GDataBase::InsertValue(int nHeadPos, int nValuePos)
{
	// Read in the position of the head value
	int nHeadValuePos;
	if(!Read((char*)&nHeadValuePos, nHeadPos, sizeof(int)))
		return false;

	// Read the value
	struct GDBValue valThat;
	if(!Read((char*)&valThat, nValuePos, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to read");
		return 0;
	}

	// Insert the value
	if(nHeadValuePos <= 0)
	{
		GAssert(nHeadValuePos == 0, "Bad value");
		nHeadValuePos = nValuePos;

		// Update this value
		valThat.nHeight = 1;
		valThat.nLeft = 0;
		valThat.nRight = 0;
		valThat.nParent = 0;

		// Write this value
		if(!Write((char*)&valThat, nValuePos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return 0;
		}
	}
	else
	{
		char sThat[GDB_VALUE_SORTING_PART_SIZE];
		int nThatSize = MIN(valThat.nValueSize, GDB_VALUE_SORTING_PART_SIZE);
		if(!Read(sThat, nValuePos + sizeof(struct GDBValue), nThatSize))
		{
			GAssert(false, "failed to read");
			return 0;
		}

		nHeadValuePos = Insert(nHeadValuePos, nValuePos, &valThat, nThatSize, sThat);
	}

	// Write the head position
	if(nHeadValuePos <= 0)
	{
		GAssert(false, "failed to insert value");
		return false;
	}
	if(!Write((char*)&nHeadValuePos, nHeadPos, sizeof(int)))
		return false;

	return true;
}

// "This" is the node already in the tree, and
// "That" is the node you want to insert into the tree
int GDataBase::Insert(int nThisPos, int nThatPos, GDBValue* pValThat, int nThatSize, char* sThat)
{
	// Check that value
	GAssert(pValThat->nHeight == 1 &&
			pValThat->nLeft == 0 &&
			pValThat->nRight == 0 &&
			pValThat->nParent == 0, "Value to insert not prepared properly");

	// Read this value
	struct GDBValue valThis;
	if(!Read((char*)&valThis, nThisPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to read");
		return 0;
	}
	char sThis[GDB_VALUE_SORTING_PART_SIZE];
	int nThisSize = MIN(valThis.nValueSize, GDB_VALUE_SORTING_PART_SIZE);
	if(!Read(sThis, nThisPos + sizeof(struct GDBValue), nThisSize))
	{
		GAssert(false, "failed to read");
		return 0;
	}

	// Compare the values
	int nCmp = CompareValues(sThis, nThisSize, sThat, nThatSize);

	// Insert the node
	int nRetVal = 0;
	if(nCmp > 0)
	{
		if(valThis.nLeft > 0)
		{
			valThis.nLeft = Insert(valThis.nLeft, nThatPos, pValThat, nThatSize, sThat);
			FixHeight(&valThis);
			nRetVal = Balance(nThisPos, &valThis);
		}
		else
		{
			valThis.nLeft = nThatPos;
			valThis.nHeight = 1;
			nRetVal = nThisPos;
			WriteIntValue(nThatPos + MEMBEROFFSET(struct GDBValue, nParent), nThisPos);
			if(!Write((char*)&valThis, nThisPos, sizeof(struct GDBValue)))
			{
				GAssert(false, "failed to write");
				return 0;
			}
		}
	}
	else
	{
		if(valThis.nRight > 0)
		{
			valThis.nRight = Insert(valThis.nRight, nThatPos, pValThat, nThatSize, sThat);
			FixHeight(&valThis);
			nRetVal = Balance(nThisPos, &valThis);
		}
		else
		{
			valThis.nRight = nThatPos;
			valThis.nHeight = 1;
			nRetVal = nThisPos;
			WriteIntValue(nThatPos + MEMBEROFFSET(struct GDBValue, nParent), nThisPos);
			if(!Write((char*)&valThis, nThisPos, sizeof(struct GDBValue)))
			{
				GAssert(false, "failed to write");
				return 0;
			}
		}
	}
	return nRetVal;
}

// This guarantees to find the left-most (or right-most if bRightMost is true) value
// that matches sVal.  If there is no matching value, it will return 0.  If bClosest
// is true, it will return the closest value (the value just less than if bRightMost
// is false, and just greater than if bRightMost is true), or 0 if there isn't one.
int GDataBase::Find(const char* sVal, int nValSize, bool bRightMost, bool bClosest, int nNodePos)
{
	if(nNodePos <= 0)
	{
		GAssert(nNodePos == 0, "Bad value");
		return 0;
	}
	struct GDBValue valThis;
	char sThis[GDB_VALUE_SORTING_PART_SIZE];
	while(true)
	{
		// Read this value
		if(!Read((char*)&valThis, nNodePos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return 0;
		}
		int nThisSize = MIN(valThis.nValueSize, GDB_VALUE_SORTING_PART_SIZE);
		if(!Read(sThis, nNodePos + sizeof(struct GDBValue), nThisSize))
		{
			GAssert(false, "failed to read");
			return 0;
		}

		// Compare
		int nCmp = CompareValues(sThis, nThisSize, sVal, nValSize);

		if(nCmp < 0)
		{
			if(valThis.nRight > 0)
				nNodePos = valThis.nRight;
			else
			{
				if(bClosest)
				{
					if(bRightMost)
						return GetNextRight(nNodePos, &valThis);
					else
						return nNodePos;
				}
				else
					return 0;
			}
		}
		else if(nCmp > 0)
		{
			if(valThis.nLeft > 0)
				nNodePos = valThis.nLeft;
			else
			{
				if(bClosest)
				{
					if(bRightMost)
						return nNodePos;
					else
						return GetNextLeft(nNodePos, &valThis);
				}
				else
					return 0;
			}
		}
		else
		{
			if(bRightMost)
			{
				if(valThis.nRight > 0)
				{
					int nTmp = Find(sVal, nValSize, bRightMost, false, valThis.nRight);
					if(nTmp > 0)
						return nTmp;
				}
			}
			else
			{
				if(valThis.nLeft > 0)
				{
					int nTmp = Find(sVal, nValSize, bRightMost, false, valThis.nLeft);
					if(nTmp > 0)
						return nTmp;
				}
			}
			return nNodePos;
		}
	}
}

void GDataBase::UnlinkValue(int nValPos, struct GDBValue* pVal, int nHeadPos)
{
	int nReplacement = GetReplacementValue(pVal);
	WriteIntValue(nReplacement + MEMBEROFFSET(struct GDBValue, nParent), pVal->nParent);
	GDBValue valPar;
	int nParPos = pVal->nParent;
	while(nParPos > 0)
	{
		if(!Read((char*)&valPar, nParPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return;
		}
		if(valPar.nLeft == nValPos)