gdatabase.cpp

一个非常有用的开源代码

	char* pTmp = pRec + sizeof(struct GDBRecordHeader);
	struct GDBValue* pValue;
	int nFieldCount = pHeader->nFieldCount;
	int n;
	for(n = 0; n < nFieldCount; n++)
	{
		pValue = (struct GDBValue*)pTmp;
		pValue->nLeft = 0;
		pValue->nRight = 0;
		pValue->nParent = 0;
		pValue->nHeight = 1;
		pValue->nRecord = nPos;
		pValue->nValueSize = pRecord->GetFieldSize(n);
		pTmp += sizeof(struct GDBValue);
		memcpy(pTmp, pRecord->GetField(n), pValue->nValueSize);
		pTmp += pValue->nValueSize;
	}
	GAssert(pTmp - pRec == nSize, "alignment error");

	// Write the record
	if(!Write(pRec, nPos, nSize))
		return false;

	// Insert the table
	if(pTableRecord)
	{
		// Insert each field
		pTmp = pRec + sizeof(struct GDBRecordHeader);
		for(n = 0; n < nFieldCount; n++)
		{
			pValue = (struct GDBValue*)pTmp;
			pTmp += sizeof(struct GDBValue);
			pTmp += pValue->nValueSize;
			InsertValue(pTableRecord->GetRootPos(n), nPos + ((char*)pValue - (char*)pRec));
		}
	}
	else
	{
		// Update root values
		pTmp = pRec + sizeof(struct GDBRecordHeader);
		for(n = 0; n < nFieldCount - 1; n++)
		{
			pValue = (struct GDBValue*)pTmp;
			pTmp += sizeof(struct GDBValue);
			pTmp += pValue->nValueSize;
			pRecord->SetRoot(n, nPos + ((char*)pValue - (char*)pRec) + MEMBEROFFSET(struct GDBValue, nLeft), pValue->nLeft);
		}

		// Only insert the last field
		InsertValue(MEMBEROFFSET(struct GDataBaseHeader, nRootTable), nPos + ((char*)pTmp - pRec));
	}

	return true;
}

bool GDataBase::AddTable(GDBRecord* pRecord)
{
	return AddRecord(pRecord, NULL);
}

bool GDataBase::AddTuple(GDBRecord* pRecord, GDBRecord* pTableRecord)
{
	GAssert(pTableRecord, "pTableRecord can't be NULL");
	return AddRecord(pRecord, pTableRecord);
}

int GDataBase::FindRecord(const char* szValue, int nValueSize, bool bRightMost, bool bClosest, int nRootValue, int* pnOutValPos)
{
	*pnOutValPos = Find(szValue, nValueSize, bRightMost, bClosest, nRootValue);
	if(*pnOutValPos < 1)
		return 0;
	struct GDBValue valThis;
	if(!Read((char*)&valThis, *pnOutValPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "error reading value");
		return 0;
	}
	GAssert(valThis.nRecord > 0, "bad record pos");
	return valThis.nRecord;
}

bool GDataBase::GetTable(GDBRecord* pOutTable, const void* pName, int nNameSize)
{
	int nTmp;
	int nTablePos = FindRecord((const char*)pName, nNameSize, false, false, ReadHeaderValue(nRootTable), &nTmp);
	if(nTablePos < 1)
		return false;
	bool bRet = ReadRecord(pOutTable, nTablePos, MAX_VALUE_CAP);
	if(bRet)
		pOutTable->SetValidTable(true);
	return bRet;
}

bool GDataBase::GetTuple(GDBRecord* pOutTuple, GDBRecord* pInTable, int nField, const void* pValue, int nValueSize, int nValueSizeCap/*=MAX_VALUE_CAP*/)
{
	int nTmp;
	int nTuplePos = FindRecord((const char*)pValue, nValueSize, false, false, pInTable->GetRootValue(nField), &nTmp);
	if(nTuplePos < 1)
		return false;
	return ReadRecord(pOutTuple, nTuplePos, nValueSizeCap);
}

void GDataBase::Query(GDBQueryEnumerator* pOutEnumerator, GDBRecord* pTableRecord, int nField, QueryType eQueryType, const void* pValue1, int nValue1Size, const void* pValue2 /*=NULL*/, int nValue2Size /*=0*/, bool bLeftToRight /*=true*/, int nValueSizeCap /*=MAX_VALUE_CAP*/)
{
	pOutEnumerator->m_pDataBase = NULL;

	// Check parameters, swap values if necessary, and figure out which value to search on
	const char* pSearchValue = (const char*)pValue1;
	int nSearchValueSize = nValue1Size;
	bool bRightMost = !bLeftToRight;
	bool bEnd = false;
	bool bClosest = true;
	switch(eQueryType)
	{
		case less:
			bRightMost = bLeftToRight;
			// intentional fall through
		case lessOrEqual:
			GAssert(!pValue2, "Only a one-value operation");
			if(bLeftToRight)
				bEnd = true;
			break;

		case greater:
			bRightMost = bLeftToRight;
			// intentional fall through
		case greaterOrEqual:
			GAssert(!pValue2, "Only a one-value operation");
			if(!bLeftToRight)
				bEnd = true;
			break;

		case equal:
			GAssert(!pValue2, "Only a one-value operation");
			bClosest = false;
			break;

		case betweenExclusive:
			bRightMost = bLeftToRight;
			// intentional fall-through
		case betweenInclusive:
			GAssert(pValue2, "Expected a second value");
			if(CompareValues((const char*)pValue1, nValue1Size, (const char*)pValue2, nValue2Size) > 0)
			{
				const char* pTmp = (const char*)pValue2;
				int nTmpSize = nValue2Size;
				pValue2 = pValue1;
				nValue2Size = nValue1Size;
				pValue1 = pTmp;
				nValue1Size = nTmpSize;
				pSearchValue = (const char*)pValue1;
				nSearchValueSize = nValue1Size;
			}
			if(!bLeftToRight)
			{
				pSearchValue = (const char*)pValue2;
				nSearchValueSize = nValue2Size;
			}
			break;

		default:
			GAssert(false, "unexpected value");
			break;
	}

	int nValPos;
	if(bEnd)
		nValPos = GetLeftOrRightMost(pTableRecord->GetRootValue(nField), !bLeftToRight);
	else
	{
		// Search for the first record
		nValPos = Find(pSearchValue, nSearchValueSize, bRightMost, bClosest, pTableRecord->GetRootValue(nField));

		// See if we need to get the next record
		bool bNeedNext = false;
		if(nValPos <= 0)
		{
			switch(eQueryType)
			{
				case equal:
				case less:
				case greater:
				case betweenExclusive:
					return;

				case lessOrEqual:
				case greaterOrEqual:
				case betweenInclusive:
					bNeedNext = true;
					break;

				default:
					GAssert(false, "unexpected value");
					break;
			}
		}
		else
		{
			if(eQueryType != equal)
			{
				// Load the value
				struct GDBValue valFirst;
				if(!Read((char*)&valFirst, nValPos, sizeof(struct GDBValue)))
				{
					GAssert(false, "failed to read");
					return;
				}
				char sFirst[GDB_VALUE_SORTING_PART_SIZE];
				int nFirstSize = MIN(valFirst.nValueSize, GDB_VALUE_SORTING_PART_SIZE);
				if(!Read(sFirst, nValPos + sizeof(struct GDBValue), nFirstSize))
				{
					GAssert(false, "failed to read");
					return;
				}

				// See if it's in range
				int nCmp = CompareValues(sFirst, nFirstSize, pSearchValue, nSearchValueSize);
				switch(eQueryType)
				{
					case less:
						GAssert(nCmp <= 0, "Find returned bad results");
						if(nCmp >= 0)
							bNeedNext = true;
						break;

					case lessOrEqual:
						if(nCmp > 0)
							bNeedNext = true;
						break;

					case greater:
						GAssert(nCmp >= 0, "Find returned bad results");
						if(nCmp <= 0)
							bNeedNext = true;
						break;

					case greaterOrEqual:
						if(nCmp < 0)
							bNeedNext = true;
						break;

					case betweenExclusive:
						if(bLeftToRight)
						{
							// Same as greater
							GAssert(nCmp >= 0, "Find returned bad results");
							if(nCmp <= 0)
								bNeedNext = true;
						}
						else
						{
							// Same as less
							GAssert(nCmp <= 0, "Find returned bad results");
							if(nCmp >= 0)
								bNeedNext = true;
						}
						break;

					case betweenInclusive:
						if(bLeftToRight)
						{
							// Same as greaterOrEqual
							if(nCmp < 0)
								bNeedNext = true;
						}
						else
						{
							// Same as lessOrEqual
							if(nCmp > 0)
								bNeedNext = true;
						}
						break;

					default:
						GAssert(false, "unexpected value");
						break;
				}
			}
		}

		// Get the next value (if necessary)
		if(bNeedNext)
			nValPos = GetNextValue(nValPos, pTableRecord, nField, bLeftToRight);
	}

	// Convert the value to a record pos
	if(nValPos <= 0)
		return;
	struct GDBValue valThis;
	if(!Read((char*)&valThis, nValPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "error reading value");
		return;
	}
	GAssert(valThis.nRecord > 0, "bad record pos");

	// Set up the query enumerator
	pOutEnumerator->m_bLeftToRight = bLeftToRight;
	pOutEnumerator->m_nBufferedRecordPos = valThis.nRecord;
	pOutEnumerator->m_nCurrentValuePos = nValPos;
	pOutEnumerator->m_nField = nField;
	pOutEnumerator->m_nValueSizeCap = nValueSizeCap;
	pOutEnumerator->m_pTable = pTableRecord;
	pOutEnumerator->m_pDataBase = this;
	pOutEnumerator->m_eQueryType = eQueryType;

	// See if the enumerator needs to check the value
	pOutEnumerator->m_bNeedCompareValue = true;
	switch(eQueryType)
	{
		case less:
		case lessOrEqual:
			if(!bLeftToRight)
				pOutEnumerator->m_bNeedCompareValue = false;
			break;
		case greater:
		case greaterOrEqual:
			if(bLeftToRight)
				pOutEnumerator->m_bNeedCompareValue = false;
			break;
		default:
			break;
	}
	if(pOutEnumerator->m_bNeedCompareValue)
	{
		bool bFirstValue = true;
		if(eQueryType == betweenInclusive || eQueryType == betweenExclusive)
		{
			if(bLeftToRight)
				bFirstValue = false;
		}
		pOutEnumerator->m_nCompareValueSize = MIN(bFirstValue ? nValue1Size : nValue2Size, GDB_VALUE_SORTING_PART_SIZE);
		memcpy(pOutEnumerator->m_sCompareValue, bFirstValue ? pValue1 : pValue2, pOutEnumerator->m_nCompareValueSize);
	}
	else
		pOutEnumerator->m_nCompareValueSize = 0;
}

int GDataBase::GetNextRecord(int* pnValPos, GDBRecord* pTableRecord, int nField, bool bRight)
{
	*pnValPos = GetNextValue(*pnValPos, pTableRecord, nField, bRight);
	if(*pnValPos < 1)
	{
		GAssert(*pnValPos == 0, "bad value");
		return 0;
	}
	struct GDBValue valNext;
	if(!Read((char*)&valNext, *pnValPos, sizeof(struct GDBValue)))
	{
		GAssert(false, "error reading value");
		return 0;
	}
	GAssert(valNext.nRecord > 0, "bad record value");
	return valNext.nRecord;
}

int GDataBase::GetNextValue(int nPos, GDBRecord* pTableRecord, int nField, bool bRight)
{
	int nNextValPos;
	if(nPos == 0)
	{
		// Get first or last value in the database
		int nRootVal;
		if(pTableRecord)
			nRootVal = pTableRecord->GetRootValue(nField);
		else
			nRootVal = ReadHeaderValue(nRootTable);
		nNextValPos = GetLeftOrRightMost(nRootVal, !bRight);
	}
	else
	{
		// Find the next value
		GAssert(nPos > 0, "bad value pos");
		struct GDBValue valThis;
		if(!Read((char*)&valThis, nPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "error reading value");
			return 0;
		}
		if(bRight)
			nNextValPos = GetNextRight(nPos, &valThis);
		else
			nNextValPos = GetNextLeft(nPos, &valThis);
		GAssert(nPos == 0 || nNextValPos != nPos, "it's the same value again");
	}

	return nNextValPos;
}

bool GDataBase::ReadRecord(GDBRecord* pOutRecord, int nPos, int nValueSizeCap)
{
	struct GDBRecordHeader header;
	if(!Read((char*)&header, nPos, sizeof(struct GDBRecordHeader)))
	{
		GAssert(false, "error reading record");
		return false;
	}
	pOutRecord->SetRecordPos(nPos);
	nPos += sizeof(struct GDBRecordHeader);
	pOutRecord->SetFieldCount(header.nFieldCount);
	struct GDBValue value;
	int n;
	for(n = 0; n < header.nFieldCount; n++)
	{
		int nValuePos = nPos;
		if(!Read((char*)&value, nPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "error reading record");
			return false;
		}
		nPos += sizeof(struct GDBValue);
		int nReadSize = MIN(nValueSizeCap, value.nValueSize);
		char* pBuf = new char[nReadSize + 2];
		if(!Read(pBuf, nPos, nReadSize))
		{
			GAssert(false, "error reading record");
			return false;
		}
		pBuf[nReadSize] = '\0';
		pBuf[nReadSize + 1] = '\0';
		pOutRecord->SetField(n, nPos, value.nValueSize, nReadSize, pBuf);
		pOutRecord->SetRoot(n, nValuePos + MEMBEROFFSET(struct GDBValue, nLeft), value.nLeft);
		nPos += value.nValueSize;
	}
	return true;
}

bool GDataBase::DeleteRecord(GDBRecord* pTuple, GDBRecord* pTable)
{
	int nPos = pTuple->GetRecordPos();
	if(nPos <= 0)
		return false;

	// Read in the header (to get the record size)
	struct GDBRecordHeader header;
	if(!Read((char*)&header, nPos, sizeof(struct GDBRecordHeader)))
		return false;
	if(header.nState == GDBRT_DELETED)
		return false;

	// Unlink all the fields
	nPos += sizeof(struct GDBRecordHeader);
	struct GDBValue value;
	int n;
	GAssert(pTable->GetFieldCount() == header.nFieldCount + 1, "Table doesn't go with record");
	for(n = 0; n < header.nFieldCount; n++)
	{
		if(!Read((char*)&value, nPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "error reading record");
			return false;
		}
		UnlinkValue(nPos, &value, pTable->GetRootPos(n));
		nPos += sizeof(struct GDBValue);
		nPos += value.nValueSize;
	}

	// Put in table of free area to reuse

	return true;
}

int GDataBase::FindDeletedRecordToReuse(int nSize)
{
	// todo: write this
	return 0;
}

void GDataBase::Flush()
{
	GDBPage* pPage;
	for(pPage = m_pMostRecentlyUsedPage; pPage; pPage = pPage->m_pNext)
		FlushPage(pPage);
	m_pMostRecentlyUsedPage = NULL;
}

void GDataBase::FlushPage(GDBPage* pPage)
{
	// Write the changes to disk
	if(!pPage->m_bDirty)
		return;
	fseek(m_pFile, pPage->m_nPos, SEEK_SET); // todo: check for errors
	fwrite(pPage->m_data, GDB_PAGE_SIZE, 1, m_pFile); // todo: check for errors
	pPage->m_bDirty = false;
}

GDBPage* GDataBase::GetPage(int nPos)
{
	// Calculate chapter and page
	GAssert(nPos >= 0, "out of range (726)");
	int nPage = nPos >> BITS_IN_PAGE_SIZE;
	int nChapter = nPage >> BITS_IN_CHAPTER_SIZE;
	nPage &= PAGE_IN_CHAPTER_MASK;

	// Find the right chapter
	GDBChapter* pChapter;
	if(m_pCurrentChapter && m_pCurrentChapter->m_nChapter == nChapter)
		pChapter = m_pCurrentChapter;
	else
	{
		GDBChapterLookup tmp(nChapter);
		int nIndex;
		pChapter = (GDBChapter*)m_pChapters->GetNode(&tmp, &nIndex);
		if(!pChapter)
		{
			pChapter = new GDBChapter(nChapter);
			m_pChapters->Insert(pChapter);
		}
	}