gdatabase.cpp

一个非常有用的开源代码

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GDataBase.h"
#include "GMacros.h"
#include "GAVLTree.h"
#include <stdlib.h>

// -------------------------------------------------------------------
// Constants
// -------------------------------------------------------------------

#define GDB_PAGE_SIZE 4096
#define BITS_IN_PAGE_SIZE 12
#define BYTES_IN_PAGE_MASK ((1 << BITS_IN_PAGE_SIZE) - 1)
#define GDB_PAGES_PER_CHAPTER 256
#define BITS_IN_CHAPTER_SIZE 8
#define PAGE_IN_CHAPTER_MASK ((1 << BITS_IN_CHAPTER_SIZE) - 1)
#define PAGES_TO_CACHE 2048

// -------------------------------------------------------------------
// File Structures
// -------------------------------------------------------------------

struct GDataBaseHeader
{
	int nDataBaseSize;
	int nRootTable;
};

enum GDBRecordType
{
	GDBRT_DELETED = 100,
	GDBRT_TABLE = 101,
	GDBRT_TUPLE = 102,
};

struct GDBRecordHeader
{
	int nState; // a GDBRecordType enum
	int nRecordSize; // size in bytes of the entire record
	int nFieldCount; // count of the values in this record
	// GDBValue pValues[];
};

struct GDBValue
{
	int nLeft; // For Table values, this refers to the head tuple
	int nRight;
	int nParent;
	int nHeight; // The max of the heights of both children plus 1
	int nRecord; // The record position of the record that contains this value
	int nValueSize;
	// char sValue[];
};


// -------------------------------------------------------------------
// Page
// -------------------------------------------------------------------

class GDBPage
{
public:
	char m_data[GDB_PAGE_SIZE];
	int m_nPos;
	bool m_bDirty;

	// Pages are linked in a list in order of most recently used
	// so that when we run out of RAM we can throw out the least
	// recently used page.
	GDBPage* m_pPrev;
	GDBPage* m_pNext;

	GDBPage(int nPos)
	{
		GAssert((nPos & BYTES_IN_PAGE_MASK) == 0, "Page not aligned properly");
		m_nPos = nPos;
		m_bDirty = false;
		m_pPrev = NULL;
		m_pNext = NULL;
	}

	virtual ~GDBPage()
	{
	}
};

// -------------------------------------------------------------------
// Chapter
// -------------------------------------------------------------------


class GDBChapterLookup : public GAVLNode
{
public:
	int m_nChapter;

	GDBChapterLookup(int nChapter)
	{
		m_nChapter = nChapter;
	}

	virtual ~GDBChapterLookup()
	{
	}

	virtual int Compare(GAVLNode* pThat)
	{
		if(m_nChapter < ((GDBChapterLookup*)pThat)->m_nChapter)
			return -1;
		if(m_nChapter > ((GDBChapterLookup*)pThat)->m_nChapter)
			return 1;
		return 0;
	}
};

class GDBChapter : public GDBChapterLookup
{
public:
	GDBPage* m_pPages[GDB_PAGES_PER_CHAPTER];
	
	GDBChapter(int nChapter) : GDBChapterLookup(nChapter)
	{
		memset(m_pPages, '\0', sizeof(GDBPage*) * GDB_PAGES_PER_CHAPTER);
	}

	virtual ~GDBChapter()
	{
		int n;
		for(n = 0; n < GDB_PAGES_PER_CHAPTER; n++)
			delete(m_pPages[n]);
	}
};

// -------------------------------------------------------------------
// GDBRecord
// -------------------------------------------------------------------

GDBRecord::GDBRecord()
{
	m_nFieldCount = 0;
	m_nRecordPos = 0;
	m_pFields = NULL;
	m_bValidTable = false;
}

GDBRecord::~GDBRecord()
{
	Clear();
}

void GDBRecord::Clear()
{
	int n;
	for(n = 0; n < m_nFieldCount; n++)
		delete(m_pFields[n].pValue);
	delete(m_pFields);
	m_nFieldCount = 0;
	m_pFields = NULL;
}

void GDBRecord::SetFieldCount(int nFieldCount)
{
	Clear();
	if(nFieldCount > 0)
	{
		m_pFields = new struct GDBRecordField[nFieldCount];
		memset(m_pFields, '\0', sizeof(struct GDBRecordField) * nFieldCount);
	}
	else
		m_pFields = NULL;
	m_nFieldCount = nFieldCount;
}

// note that this will take ownership of pValue
void GDBRecord::SetField(int nField, int nValuePos, int nValueSize, int nValueSizeLoaded, void* pValue)
{
	GAssert(nField >= 0 && nField < m_nFieldCount, "Out of range (725)");
	m_pFields[nField].nRootPos = 0;
	m_pFields[nField].nRootValue = 0;
	m_pFields[nField].nValuePos = nValuePos;
	m_pFields[nField].nValueSize = nValueSize;
	m_pFields[nField].nValueSizeLoaded = nValueSizeLoaded;
	delete(m_pFields[nField].pValue);
	m_pFields[nField].pValue = (char*)pValue;
}

void GDBRecord::SetField(int nField, const void* pValue, int nValueSize)
{
	char* pNewValue = new char[nValueSize + 2];
	memcpy(pNewValue, pValue, nValueSize);
	pNewValue[nValueSize] = '\0';
	pNewValue[nValueSize + 1] = '\0';
	SetField(nField, 0, nValueSize, nValueSize, pNewValue);
}

int GDBRecord::GetRecordSize()
{
	int nSize = sizeof(struct GDBRecordHeader);
	nSize += m_nFieldCount * sizeof(struct GDBValue);
	int n;
	for(n = 0; n < m_nFieldCount; n++)
		nSize += m_pFields[n].nValueSize;
	return nSize;
}

void GDBRecord::SetRoot(int nField, int nRootPos, int nRootValue)
{
	m_pFields[nField].nRootPos = nRootPos;
	m_pFields[nField].nRootValue = nRootValue;
}

int GDBRecord::GetRootPos(int nField)
{
	GAssert(m_pFields[nField].nRootPos, "The root pos should never be zero--this happens if it's not a table or the table wasn't added to the database");
	return m_pFields[nField].nRootPos;
}

int GDBRecord::GetRootValue(int nField)
{
	return m_pFields[nField].nRootValue;
}

// -------------------------------------------------------------------
// GDBQueryEnumerator
// -------------------------------------------------------------------

inline int CompareValues(const char* sThis, int nThisSize, const char* sThat, int nThatSize)
{
	// Compare the values
	int nCmp = 0;
	int nSize = nThisSize;
	if(nThisSize > nThatSize)
	{
		nSize = nThatSize;
		nCmp = 1;
	}
	else if(nThisSize < nThatSize)
		nCmp = -1;
	int n;
	for(n = 0; n < nSize; n++)
	{
		if(sThis[n] > sThat[n])
		{
			nCmp = 1;
			break;
		}
		if(sThis[n] < sThat[n])
		{
			nCmp = -1;
			break;
		}
	}
	return nCmp;
}

bool GDBQueryEnumerator::GetNext(GDBRecord* pOutRecord)
{
	// Check if we already finished
	if(!m_pDataBase)
		return false;

#ifdef _DEBUG
	// Make sure we have a good database object
	if(!m_pDataBase->Check())
	{
		GAssert(false, "DataBase object corrupt or deleted!");
		return false;
	}
#endif // _DEBUG

	// Make sure we know the next record pos
	if(m_nBufferedRecordPos == 0)
	{
		// Find the next record
		m_nBufferedRecordPos = m_pDataBase->GetNextRecord(&m_nCurrentValuePos, m_pTable, m_nField, m_bLeftToRight);
		if(m_nBufferedRecordPos < 1)
		{
			GAssert(m_nBufferedRecordPos == 0, "bad record pos");
			m_pDataBase = NULL; // indicates we are done
			return false;
		}
	}

	// Read the record
	GAssert(m_nBufferedRecordPos > 0, "bad record pos");
	if(!m_pDataBase->ReadRecord(pOutRecord, m_nBufferedRecordPos, m_nValueSizeCap))
	{
		GAssert(false, "failed to read record");
		m_pDataBase = NULL; // indicates we are done
		return false;
	}
	m_nBufferedRecordPos = 0;

	// Check the value
	if(!m_bNeedCompareValue)
		return true;
	int nCmp = CompareValues(pOutRecord->GetField(m_nField), pOutRecord->GetFieldSize(m_nField), m_sCompareValue, m_nCompareValueSize);
	switch(m_eQueryType)
	{
		case GDataBase::equal:
			if(nCmp != 0)
			{
				GAssert(nCmp = m_bLeftToRight ? 1 : -1, "sorting problem");
				m_pDataBase = NULL;
				return false;
			}
			break;

		case GDataBase::less:
			if(nCmp >= 0)
			{
				m_pDataBase = NULL;
				return false;
			}
			break;

		case GDataBase::greater:
			if(nCmp <= 0)
			{
				m_pDataBase = NULL;
				return false;
			}
			break;

		case GDataBase::lessOrEqual:
			if(nCmp > 0)
			{
				m_pDataBase = NULL;
				return false;
			}
			break;

		case GDataBase::greaterOrEqual:
			if(nCmp < 0)
			{
				m_pDataBase = NULL;
				return false;
			}
			break;

		case GDataBase::betweenInclusive:
			if(m_bLeftToRight)
			{
				// same as lessOrEqual
				if(nCmp > 0)
				{
					m_pDataBase = NULL;
					return false;
				}
			}
			else
			{
				// same as greaterOrEqual
				if(nCmp < 0)
				{
					m_pDataBase = NULL;
					return false;
				}
			}
			break;

		case GDataBase::betweenExclusive:
			if(m_bLeftToRight)
			{
				// same as less
				if(nCmp >= 0)
				{
					m_pDataBase = NULL;
					return false;
				}
			}
			else
			{
				// same as greater
				if(nCmp <= 0)
				{
					m_pDataBase = NULL;
					return false;
				}
			}
			break;

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

	return true;
}

// -------------------------------------------------------------------
// GDataBase
// -------------------------------------------------------------------

#define ReadHeaderValue(field) ReadIntValue(MEMBEROFFSET(struct GDataBaseHeader, field))
#define WriteHeaderValue(field, value) WriteIntValue(MEMBEROFFSET(struct GDataBaseHeader, field), value)

GDataBase::GDataBase(FILE* pFile)
{
	GAssert((1 << BITS_IN_PAGE_SIZE) == GDB_PAGE_SIZE, "Page size problem");
	GAssert((1 << BITS_IN_CHAPTER_SIZE) == GDB_PAGES_PER_CHAPTER, "Chapter size problem");
	m_pFile = pFile;
	m_pChapters = new GAVLTree();
	m_nChaptersCreated = 0;
	m_pCurrentChapter = NULL;
	m_pMostRecentlyUsedPage = NULL;
	m_pLeastRecentlyUsedPage = NULL;
	m_nPageCacheSize = 0;
#ifdef _DEBUG
	m_nMagic = 0x31636a54; // This value is so we can check that the database hasn't been deleted
#endif // _DEBUG
}

GDataBase::~GDataBase()
{
#ifdef _DEBUG
	m_nMagic = 0;
#endif // _DEBUG
	Flush();
	fclose(m_pFile);
	delete(m_pChapters);
}

/*static*/ bool GDataBase::Create(const char* szFilename)
{
	// Create a file
	FILE* pFile = fopen(szFilename, "wb");
	if(!pFile)
	{
		GAssert(false, "failed to create file");
		return false;
	}

	// Create a header
	struct GDataBaseHeader header;
	header.nRootTable = 0;
	header.nDataBaseSize = sizeof(struct GDataBaseHeader);

	// Write it to the file
	fwrite(&header, sizeof(struct GDataBaseHeader), 1, pFile); // todo: check for errors
	fclose(pFile);
	return true;
}

/*static*/ GDataBase* GDataBase::Open(const char* szFilename)
{
	FILE* pFile = fopen(szFilename, "rb+");
	if(!pFile)
	{
		GAssert(false, "failed to open file");
		return NULL;
	}
	GDataBase* pDataBase = new GDataBase(pFile);
	return pDataBase;
}

int GDataBase::ReadIntValue(int nPos)
{
	int nValue;
	if(!Read((char*)&nValue, nPos, sizeof(int)))
	{
		GAssert(false, "error reading int");
		return 0;
	}
	return nValue;
}

void GDataBase::WriteIntValue(int nPos, int nValue)
{
	if(!Write((char*)&nValue, nPos, sizeof(int)))
		GAssert(false, "error writing int");
}

bool GDataBase::AddRecord(GDBRecord* pRecord, GDBRecord* pTableRecord)
{
	GAssert(!pTableRecord || pTableRecord->IsValidTable(), "This table is no longer valid.  (You must get the table again after you add a record to it.)");
	GAssert(!pTableRecord || pTableRecord->GetFieldCount() - 1 == pRecord->GetFieldCount(), "Field count mismatch");
	if(pTableRecord)
		pTableRecord->SetValidTable(false);
	
	// Allocate space for a record
	int nSize = pRecord->GetRecordSize();
	GTEMPBUF(char, pRec, nSize); // this macro allocates a temporary buffer in pRec

	// Fill in the struct values
	struct GDBRecordHeader* pHeader = (struct GDBRecordHeader*)pRec;
	pHeader->nFieldCount = pRecord->GetFieldCount();
	pHeader->nRecordSize = nSize;
	pHeader->nState = pTableRecord ? GDBRT_TUPLE : GDBRT_TABLE;

	// Find a spot for it
	int nPos = FindDeletedRecordToReuse(pHeader->nRecordSize);
	if(nPos == 0)
	{
		nPos = ReadHeaderValue(nDataBaseSize);
		WriteHeaderValue(nDataBaseSize, nPos + pHeader->nRecordSize);
	}

	// Set all the field names