gdatabase.cpp

一个非常有用的开源代码

			valPar.nLeft = nReplacement;
		else
		{
			GAssert(valPar.nRight == nValPos, "parent-child mismatch");
			valPar.nRight = nReplacement;
		}
		nValPos = nParPos;
		nParPos = valPar.nParent;
		nReplacement = Balance(nValPos, &valPar);
	}
	WriteIntValue(nHeadPos, nReplacement);
}

int GDataBase::GetReplacementValue(struct GDBValue* pVal)
{
	// If this value doesn't have a left or right child, it's easy
	if(pVal->nRight <= 0)
		return pVal->nLeft;
	if(pVal->nLeft <= 0)
		return pVal->nRight;

	// Load the left child (because we're going to use the left-child's
	// right-most descendant to fill the vacant spot it leaves when it
	// gets unlinked.)
	GDBValue valLeft;
	if(!Read((char*)&valLeft, pVal->nLeft, sizeof(struct GDBValue)))
	{
		GAssert(false, "failed to read");
		return 0;
	}

	// See if the left child has a right child
	if(valLeft.nRight > 0)
	{
		// Find right-most child of my left child to be my replacement
		int nReplacement;
		pVal->nLeft = UnlinkRightMost(pVal->nLeft, &valLeft, &nReplacement);

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

		// Insert the replacement value
		valReplacement.nLeft = pVal->nLeft;
		valReplacement.nRight = pVal->nRight;
		FixHeight(&valReplacement);
		return Balance(nReplacement, &valReplacement);
	}
	else
	{
		// Replace me with its left child
		valLeft.nRight = pVal->nRight;
		FixHeight(&valLeft);
		return Balance(pVal->nLeft, &valLeft);
	}
}

int GDataBase::UnlinkRightMost(int nVal, struct GDBValue* pVal, int* pnOutThat)
{
	if(pVal->nRight > 0)
	{
		// Load the right child
		struct GDBValue valRight;
		if(!Read((char*)&valRight, pVal->nRight, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read while unlinking");
			return 0;
		}

		// Recurse
		pVal->nRight = UnlinkRightMost(pVal->nRight, &valRight, pnOutThat);
		FixHeight(pVal);
		return Balance(nVal, pVal);
	}
	else
	{
		*pnOutThat = nVal;
		return pVal->nLeft;
	}
}

int GDataBase::GetNextRight(int nPos, struct GDBValue* pVal)
{
	if(pVal->nRight > 0)
		return GetLeftOrRightMost(pVal->nRight, false);
	while(pVal->nParent > 0)
	{
		int nParPos = pVal->nParent;
		if(!Read((char*)pVal, nParPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return 0;
		}
		if(pVal->nLeft == nPos)
			return nParPos;
		GAssert(pVal->nRight == nPos, "parent-child mismatch");
		nPos = nParPos;
	}
	return 0;
}

int GDataBase::GetNextLeft(int nPos, struct GDBValue* pVal)
{
	if(pVal->nLeft > 0)
		return GetLeftOrRightMost(pVal->nLeft, true);
	while(pVal->nParent > 0)
	{
		int nParPos = pVal->nParent;
		if(!Read((char*)pVal, nParPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return 0;
		}
		if(pVal->nRight == nPos)
			return nParPos;
		GAssert(pVal->nLeft == nPos, "parent-child mismatch");
		nPos = nParPos;
	}
	return 0;
}

int GDataBase::GetLeftOrRightMost(int nValPos, bool bRight)
{
	if(nValPos <= 0)
	{
		GAssert(nValPos == 0, "bad value");
		return 0;
	}
	struct GDBValue valThis;
	int nNextVal;
	while(true)
	{
		if(!Read((char*)&valThis, nValPos, sizeof(struct GDBValue)))
		{
			GAssert(false, "failed to read");
			return 0;
		}
		nNextVal = bRight ? valThis.nRight : valThis.nLeft;
		if(nNextVal > 0)
			nValPos = nNextVal;
		else
			return nValPos;
	}
}

int GDataBase::ValToInt(const char* pBuf)
{
	char szTmp[32];
	int nSize = (int)*pBuf;
	memcpy(szTmp, pBuf + 1, nSize);
	szTmp[nSize] = '\0';
	return atoi(szTmp);
}

int GDataBase::IntToVal(int nVal, char* pBuf)
{
	itoa(nVal, pBuf + 1, 10);
	int nSize = strlen(pBuf + 1);
	pBuf[0] = (char)nSize;
	return nSize + 1;
}

#ifndef NO_TEST_CODE
void MakeRecord(GDBRecord* pRec, int nVal)
{
	char szTmp[32];
	int nSize = GDataBase::IntToVal(nVal, szTmp);
	pRec->SetFieldCount(2);
	pRec->SetField(0, szTmp, nSize);
	pRec->SetField(1, szTmp, nSize);
}

/*static*/ void GDataBase::Test()
{
	if(!GDataBase::Create("TestDB.gdb"))
		throw "failed";
	GDataBase* pDataBase = GDataBase::Open("TestDB.gdb");
	if(!pDataBase)
		throw "failed";
	Holder<GDataBase*> hDataBase(pDataBase);

	// Make a table
	GDBRecord tbl;
	tbl.SetFieldCount(3);
	tbl.SetField(0, "Val", 3);
	tbl.SetField(1, "Val2", 4);
	tbl.SetField(2, "MyTable", 7);
	if(!pDataBase->AddTable(&tbl))
		throw "failed";

	// Add some values to the table
	int nRecordCount = 256;
	int nQueryRuns = 20;
	int n;
	GAssert(((nRecordCount & 1) == 0) && nRecordCount > nQueryRuns && ((nQueryRuns & 1) == 0), "nRecordCount must be even and more than nQueryRuns and nQueryRuns must be even");
	for(n = 0; n < nRecordCount / 2; n += 2)
	{
		// Find the table
		if(!pDataBase->GetTable(&tbl, "MyTable", 7))
			throw "failed";

		// Add a record
		GDBRecord rec;
		MakeRecord(&rec, n);
		if(!pDataBase->AddTuple(&rec, &tbl))
			throw "failed";
	}
	if(n < nRecordCount / 2)
		throw "failed";
	for(n = nRecordCount - 2; n >= nRecordCount / 2; n -= 2)
	{
		// Find the table
		if(!pDataBase->GetTable(&tbl, "MyTable", 7))
			throw "failed";

		// Add a record
		GDBRecord rec;
		MakeRecord(&rec, n);
		if(!pDataBase->AddTuple(&rec, &tbl))
			throw "failed";
	}
	if(n >= nRecordCount / 2)
		throw "failed";

	// Get the table
	const char* pBologna = "Bologna";
	memset(&tbl, '\0', sizeof(GDBRecord));
	if(pDataBase->GetTable(&tbl, pBologna, strlen(pBologna)))
		throw "failed";
	if(!pDataBase->GetTable(&tbl, "MyTable", strlen("MyTable")))
		throw "failed";
	if(tbl.GetFieldCount() != 3)
		throw "failed";

	// Query equal (positive)
	GDBQueryEnumerator qe;
	GDBRecord rec;
	char pVal[256];
	int nValSize = GDataBase::IntToVal(nQueryRuns, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::equal, pVal, nValSize);
	if(!qe.GetNext(&rec))
		throw "failed";
	if(rec.GetFieldCount() != 2)
		throw "failed";
	if(GDataBase::ValToInt(rec.GetField(0)) != nQueryRuns)
		throw "failed";
	if(GDataBase::ValToInt(rec.GetField(1)) != nQueryRuns)
		throw "failed";

	// Delete this record
	if(!pDataBase->DeleteRecord(&rec, &tbl))
		throw "failed";

	// Query equal (negative never added)
	nValSize = GDataBase::IntToVal(nQueryRuns + 1, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::equal, pVal, nValSize);
	if(qe.GetNext(&rec))
		throw "failed";

	// Query equal (negative deleted)
	nValSize = GDataBase::IntToVal(nQueryRuns, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::equal, pVal, nValSize);
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greater (left to right)
	int nStart = nRecordCount - nQueryRuns;
	nValSize = GDataBase::IntToVal(nStart, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greater, pVal, nValSize);
	for(n = nStart + 2; n < nRecordCount; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nRecordCount)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greater (right to left)
	pDataBase->Query(&qe, &tbl, 1, GDataBase::greater, pVal, nValSize, NULL, 0, false);
	for(n = nRecordCount - 2; n > nStart; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nStart)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greater (negative)
	nValSize = GDataBase::IntToVal(nRecordCount - 2, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greater, pVal, nValSize);
	if(qe.GetNext(&rec))
		throw "failed";
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greater, pVal, nValSize, NULL, 0, false);
	if(qe.GetNext(&rec))
		throw "failed";

	// Query less (right to left)
	int nEnd = nQueryRuns;
	nValSize = GDataBase::IntToVal(nEnd, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::less, pVal, nValSize, NULL, 0, false);
	for(n = nEnd - 2; n >= 0; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != -2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query less (left to right)
	pDataBase->Query(&qe, &tbl, 1, GDataBase::less, pVal, nValSize);
	for(n = 0; n < nEnd; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nEnd)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query less (negative)
	nValSize = GDataBase::IntToVal(0, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::less, pVal, nValSize, NULL, 0, false);
	if(qe.GetNext(&rec))
		throw "failed";
	pDataBase->Query(&qe, &tbl, 0, GDataBase::less, pVal, nValSize);
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greaterOrEqual (left to right)
	nStart = nRecordCount - nQueryRuns;
	nValSize = GDataBase::IntToVal(nStart, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greaterOrEqual, pVal, nValSize);
	for(n = nStart; n < nRecordCount; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nRecordCount)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greaterOrEqual (right to left)
	pDataBase->Query(&qe, &tbl, 1, GDataBase::greaterOrEqual, pVal, nValSize, NULL, 0, false);
	for(n = nRecordCount - 2; n >= nStart; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nStart - 2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query greaterOrEqual (negative)
	nValSize = GDataBase::IntToVal(nRecordCount + 2, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greaterOrEqual, pVal, nValSize);
	if(qe.GetNext(&rec))
		throw "failed";
	pDataBase->Query(&qe, &tbl, 0, GDataBase::greaterOrEqual, pVal, nValSize, NULL, 0, false);
	if(qe.GetNext(&rec))
		throw "failed";

	// Query lessOrEqual (right to left)
	nEnd = nQueryRuns;
	nValSize = GDataBase::IntToVal(nEnd, pVal);
	pDataBase->Query(&qe, &tbl, 0, GDataBase::lessOrEqual, pVal, nValSize, NULL, 0, false);
	for(n = nEnd; n >= 0; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != -2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query lessOrEqual (left to right)
	pDataBase->Query(&qe, &tbl, 1, GDataBase::lessOrEqual, pVal, nValSize);
	for(n = 0; n <= nEnd; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nEnd + 2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query betweenInclusive (left to right)
	nStart = (nRecordCount - nQueryRuns) / 2;
	if(nStart & 1)
		nStart++;
	nEnd = (nRecordCount + nQueryRuns) / 2;
	if(nEnd & 1)
		nEnd--;
	nValSize = GDataBase::IntToVal(nStart, pVal);
	char pVal2[256];
	int nValSize2 = GDataBase::IntToVal(nEnd, pVal2);		
	pDataBase->Query(&qe, &tbl, 0, GDataBase::betweenInclusive, pVal, nValSize, pVal2, nValSize2);
	for(n = nStart; n <= nEnd; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nEnd + 2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query betweenInclusive (right to left), (swapped left/right)
	pDataBase->Query(&qe, &tbl, 0, GDataBase::betweenInclusive, pVal2, nValSize2, pVal, nValSize, false);
	for(n = nEnd; n >= nStart; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nStart - 2)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query betweenExclusive (left to right), (swapped left/right)
	pDataBase->Query(&qe, &tbl, 0, GDataBase::betweenExclusive, pVal2, nValSize2, pVal, nValSize);
	for(n = nStart + 2; n < nEnd; n += 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nEnd)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

	// Query betweenExclusive (right to left)
	pDataBase->Query(&qe, &tbl, 0, GDataBase::betweenExclusive, pVal, nValSize, pVal2, nValSize2, false);
	for(n = nEnd - 2; n > nStart; n -= 2)
	{
		if(n == nQueryRuns)
			continue;
		if(!qe.GetNext(&rec))
			throw "failed";
		if(GDataBase::ValToInt(rec.GetField(0)) != n)
			throw "failed";
	}
	if(n != nStart)
		throw "failed";
	if(qe.GetNext(&rec))
		throw "failed";

}
#endif // !NO_TEST_CODE