avl_node_file.h

独立于AVL库的存储媒体 虽现在有不少可用的AVL树库

/////////////////////////////////////////////////////////////////////////////
// Name:        avl_node_file.h
// Version:		1.0.0
// Purpose:     A Node Handle Class using file as storage media
// Author:      Wu Yuh Song
// Modified by:
// Created:     07/31/1999
// Copyright:   (c) Wu Yuh Song
// Licence:   	Wu Yuh Song's Library Licence, Version 1
/////////////////////////////////////////////////////////////////////////////



#ifndef ___AVL_NODE_FILE___
#define ___AVL_NODE_FILE___

#include <stdio.h>
#include <stddef.h>
#include "../AVL_Libraries/avl.h"
#include "../AVL_Libraries/avl_node.h"

FILE*	fpDB = NULL; 


//open the database
void OpenDB()
{
	if ( !(fpDB = fopen("database", "r+b")) ) {	//New Database
		fpDB = fopen("database", "w+b");
		fseek(fpDB, 0, SEEK_SET);
		long tmp = 0;
		fwrite(&(tmp), sizeof(long),1, fpDB);	// write the file position of the info block.
												// tmp = 0 means no info block is available.
	}
}


long GetInfoBlockPos()
{

	long pos;

	fseek(fpDB, 0, SEEK_SET);
	fread(&pos, sizeof(long), 1, fpDB);

	return pos;

}

void SetInfoBlockPos(long pos)
{

	fseek(fpDB, 0, SEEK_SET);
	fwrite(&pos, sizeof(long), 1, fpDB);

}

void CloseDB()
{
	
	fclose(fpDB);
}

//use to free the space occupied by block started at file position 'pos'
//currently, do nothing, for simplicity.
void ReleaseBlock(long pos)
{
	(pos);
}


//For simplicity, a new block is allocated from the end of the file.
long NewBlock(int nSize)
{
	long pos;

	fseek(fpDB, 0, SEEK_END);
	pos = ftell(fpDB);

	if ( nSize) {	//enlarge the file
		fseek(fpDB, pos+nSize-1, SEEK_SET);	
		fputc(0,fpDB);
	}

	return pos;
}

/// the node handle class which uses a file (by default, it is a file pointed by fpDB) 
/// as storage media.
class avl_node_hnd_file
{

	long	posCurrent;	//file position of the start of the block occpuied the node
						//currently referenced by the avl_node_hnd_file object.

	//struct for storing temporary information in the memory of a node.
	struct tagDataCore
	{

		long	posParent;		//file position of the start of the block occpuied the parent of the node
		long	posLeftChild;	//file position of the start of the block occpuied the left child of the node
		long	posRightChild;	//file position of the start of the block occpuied the right child of the node
#ifdef ___AVL_LINKLIST_SUPPORT___
		long	posLeftSibling; //file position of the start of the block occpuied the left sibling of the node
		long	posRightSibling;//file position of the start of the block occpuied the right sibling of the node
#endif		
		long	posKey;   //file position of the start of the block which contains the 'key' of the node
		long	posValue; //file position of the start of the block which contains the 'value' of the node
		int		nBF;

		int		nRef;	//reference count used to determine the lifetime in the memory of the tagDataCore structure
		char*	szKey;	//pointer to the 'key'
		char*	szValue;//pointer to the 'value'
		bool	bKeyChanged, bValueChanged;
		bool	bWaitRelease;	//indicate that the space of this
								//node should be released while nRef
								//reaches 0.
		long	posCurrent;
		int		nNodeType;		//nNodeType = 1  ==>  Memory node

		
		static int size()
		{
			return offsetof(tagDataCore, nRef)-offsetof(tagDataCore, posParent);
		}

		static int offset()
		{
			return 0;
		}

		tagDataCore()
		{
			nRef = 1;
			szKey = NULL;
			szValue = NULL;
			bWaitRelease = false;
			nNodeType = 0;	//normal node
		}

		// increase reference count
		void AddRef()
		{
			nRef++;
		}

		// decrease reference count, and free the DataCore
		// when ref count reaches zero.
		void Release()
		{
			

			if ( --nRef <= 0) {
											
				if ( nNodeType != 1 ) {	//file node only

					//Remove reference address
					avl_node_hnd_mem<long,tagDataCore*> tmp, tmp2;

					tmp.NewNode();
					tmp2.SetToNode(tmp);
					tmp2.SetKey(posCurrent);
					
					verify ( lookup_tree.Delete(tmp2) );

					tmp2.DeleteNode();
					tmp.DeleteNode();


					if ( bWaitRelease ) {
						ReleaseBlock(posKey);
						ReleaseBlock(posValue);
						ReleaseBlock(posCurrent);
					}
					else {
						Write();											
					}

				}

				if ( szKey)
					delete szKey;
				if ( szValue)
					delete szValue;

				delete this;
			}				
		}

		//Read key from file to szKey
		void ReadKey()
		{
			if ( !szKey) {
				char buf[1024];
				
				fseek(fpDB, posKey, SEEK_SET );
				fread(buf, sizeof(buf),1,fpDB);
				szKey = new char[ strlen(buf)+1 ];
				strcpy( szKey, buf);
				bKeyChanged = false;
			}
		}

		//Read value from file to szValue
		void ReadValue()
		{
			if ( !szValue) {
				char buf[1024];
				
				fseek(fpDB, posValue,  SEEK_SET);
				fread(buf, sizeof(buf),1,fpDB);
				szValue = new char[ strlen(buf)+1 ];
				strcpy( szValue, buf);
				bValueChanged = false;
			}
		}


		//write the block to file
		void Write()
		{
			int k;
			
			//only a normal node can be write to file
			assert(nNodeType != 1);

			if ( bKeyChanged && szKey) {
				ReleaseBlock(posKey);
				k = strlen(szKey)+1;
				posKey = NewBlock(k);
				fseek(fpDB, posKey, SEEK_SET);
				fwrite(szKey, k, 1, fpDB);
				bKeyChanged = false;
			}

			if ( bValueChanged && szValue) {
				ReleaseBlock(posValue);
				k = strlen(szValue)+1;
				posValue = NewBlock(k);
				fseek(fpDB, posValue, SEEK_SET);
				fwrite(szValue, k, 1, fpDB);
				bValueChanged = false;
			}

			fseek(fpDB, posCurrent + offset(), SEEK_SET);
			fwrite(this, size(), 1, fpDB);
		}
	}*pDataCore;

	friend struct tagDataCore;
	static AVL< avl_node_hnd_mem<long,tagDataCore*> > lookup_tree;

	
public:
	
	avl_node_hnd_file()
	{
		pDataCore = NULL;

	}

	~avl_node_hnd_file()
	{
		if ( pDataCore)
			pDataCore->Release();
	}

	//
	//	nType = 0  ==> a normal node, which occupies space of the file
	//	nType = 1  ==> a memory node, whcih occupies no space of the file 
	//
	void NewNode(int nType)
	{
		if ( pDataCore)
			pDataCore->Release();
		
		pDataCore = new tagDataCore();
		
		pDataCore->nNodeType = nType;

		if ( nType != 1) {
			posCurrent = NewBlock(tagDataCore::offset() + tagDataCore::size());
			pDataCore->posCurrent = posCurrent;

			//write reference address
			avl_node_hnd_mem<long,tagDataCore*> tmp;
			tmp.NewNode();
			tmp.SetKey(posCurrent);
			tmp.SetValue(pDataCore);
			verify ( lookup_tree.Insert(tmp) );

		}
		else {
			pDataCore->posCurrent = 0;
			pDataCore->nNodeType = 1;	//indicate this is a memory node
		}

		pDataCore->posKey = 0;
		pDataCore->posValue = 0;
		
		
	}

	// Delete space of the file occupied by the node.
	//
	// NOTE : It's not necessary to call this function for freeing 
	//        space occupied by a memory node.
	void DeleteNode()
	{

		if ( pDataCore) {
			pDataCore->bWaitRelease = true;
			pDataCore->Release();
		}
	
		pDataCore = NULL;
	}

	void SetKey(char* szKey)
	{
		if ( pDataCore->szKey) 
			delete pDataCore->szKey;
		
		pDataCore->szKey = new char[strlen(szKey)+1];
		pDataCore->bKeyChanged = true;
		strcpy( pDataCore->szKey, szKey);
	}

	void SetValue(char* szValue)
	{
		if ( pDataCore->szValue) 
			delete pDataCore->szValue;
		
		pDataCore->szValue = new char[strlen(szValue)+1];
		pDataCore->bValueChanged = true;
		strcpy( pDataCore->szValue, szValue);

	}

	char* GetKey()	
	{

		if ( !pDataCore->szKey) 
			pDataCore->ReadKey();

		return pDataCore->szKey;
	}

	char* GetValue()
	{

		if ( !pDataCore->szValue) 
			pDataCore->ReadValue();


		return pDataCore->szValue;			
	}

	bool SetToNode( long pos)
	{	
		posCurrent = pos;
		AttachToNode();
		return true;
	}

	long peek_pos()
	{
		return posCurrent;
	}

protected:

	void AttachToNode()
	{
		tagDataCore* pOld = pDataCore;

		pDataCore = NULL;


		avl_node_hnd_mem<long,tagDataCore*> tmp;
		AVL< avl_node_hnd_mem<long,tagDataCore*> >::SearchResult sr;
		
		tmp.NewNode();
		sr.nhndSearch.SetToNode(tmp);
		sr.nhndSearch.SetKey(posCurrent);
		
		if ( !lookup_tree.Search(sr) ) {	//first time to reference
			
			pDataCore = new tagDataCore();
	
			//write reference address
			tmp.SetValue(pDataCore);
			lookup_tree.Insert(tmp, &sr);

			fseek(fpDB, posCurrent + tagDataCore::offset() , SEEK_SET);
			fread( pDataCore, tagDataCore::size(), 1, fpDB);
			pDataCore->posCurrent = posCurrent;
		}
		else {
			sr.nhndSearch.GetValue(pDataCore);
			pDataCore->AddRef();
			tmp.DeleteNode();
		}


		if ( pOld) {
			pOld->Release();
		}
		
	}





public:

	bool SetToNode(avl_node_hnd_file& node)
	{
		posCurrent = node.posCurrent;

		if ( node.pDataCore && node.pDataCore->nNodeType == 1 ) {
			if ( pDataCore)
				pDataCore->Release();
			pDataCore = node.pDataCore;
			pDataCore->AddRef();
		}
		else {
			AttachToNode();
		}

		return true;
	}

	void SetParent(avl_node_hnd_file& node)
	{
		pDataCore->posParent = node.posCurrent;
	}

	void SetLeftChild(avl_node_hnd_file& node)
	{
		pDataCore->posLeftChild = node.posCurrent;
	}

	void SetRightChild(avl_node_hnd_file& node)
	{
		pDataCore->posRightChild = node.posCurrent;
	}

#ifdef ___AVL_LINKLIST_SUPPORT___

	void SetLeftSibling(avl_node_hnd_file& node)
	{
		pDataCore->posLeftSibling = node.posCurrent;
	}

	void SetRightSibling(avl_node_hnd_file& node)
	{
		pDataCore->posRightSibling = node.posCurrent;
	}

#endif
	
	void SetParentNull()
	{
		pDataCore->posParent = 0;
	}

	void SetLeftChildNull()
	{
		pDataCore->posLeftChild = 0;
	}

	void SetRightChildNull()
	{
		pDataCore->posRightChild = 0;
	}
	
#ifdef ___AVL_LINKLIST_SUPPORT___
	void SetLeftSiblingNull()
	{
		pDataCore->posLeftSibling = 0;
	}

	void SetRightSiblingNull()
	{
		pDataCore->posRightSibling = 0;
	}

#endif

	int Compare(avl_node_hnd_file& node)
	{
		return strcmp( GetKey(), node.GetKey() );
	}
	
	void SetBalanceFactor(int nbf)
	{
		pDataCore->nBF = nbf;
	}

	int  GetBalanceFactor()
	{
		return pDataCore->nBF;
	}
	

	bool StepUp()
	{
		if ( pDataCore->posParent) {

			posCurrent = pDataCore->posParent;			
			AttachToNode();
			return true;
		}
		else
			return false;
	}

	bool StepRight()
	{
		if ( pDataCore->posRightChild) {
			posCurrent = pDataCore->posRightChild;
			AttachToNode();
			return true;
		}
		else
			return false;
	}

	bool StepLeft()
	{
		if ( pDataCore->posLeftChild) {
			posCurrent = pDataCore->posLeftChild;
			AttachToNode();
			return true;
		}
		else
			return false;
	}

#ifdef ___AVL_LINKLIST_SUPPORT___
	bool StepToLeftSibling()
	{
		if ( pDataCore->posLeftSibling) {
			posCurrent = pDataCore->posLeftSibling;
			AttachToNode();
			return true;
		}
		else
			return false;		
	}

	bool StepToRightSibling()
	{
		if ( pDataCore->posRightSibling) {
			posCurrent = pDataCore->posRightSibling;
			AttachToNode();
			return true;
		}
		else
			return false;
		
	}
#endif

};


#endif