RP411/MUNGA/HASH.cpp

#include "munga.h"
#pragma hdrstop

#include "hash.h"

//~~~~~~~~~~~~~~~~~~~~~~~~~~~ Hash ~~~~~~~~~~~~~~~~~~~~~~~~~~~

#define Verify_Index(x) 		Verify(0 <= (x) && (x) < hashTableSize)

//
//###########################################################################
// Hash
//###########################################################################
//
Hash::Hash(
	CollectionSize size,
	Node *node,
	Logical has_unique_entries
):
	SortedSocket(node, has_unique_entries)
{
	hashTableSize = size;
	BuildHashTable();
}

void
	Hash::BuildHashTable()
{
	int i;

#if 0
	hashTable = (VChain**)malloc(hashTableSize * sizeof(VChain*));
#else
	hashTable = new VChain*[hashTableSize];
#endif
	Register_Pointer(hashTable);

	for (i = 0; i < hashTableSize; i++)
	{
		Check_Pointer(hashTable);
		Verify_Index(i);
		hashTable[i] = NULL;
	}
}

//
//###########################################################################
// ~Hash
//###########################################################################
//
Hash::~Hash()
{
	int i;

	for (i = 0; i < hashTableSize; i++)
	{
		Check_Pointer(hashTable);
		Verify_Index(i);
		if (hashTable[i] != NULL)
		{
			Unregister_Object(hashTable[i]);
			delete hashTable[i];
		}
	}

	Unregister_Pointer(hashTable);
#if 0
	free(hashTable);
#else
	delete[] hashTable;
#endif
	hashTable = NULL;
	hashTableSize = 0;
}

//
//###########################################################################
// TestInstance
//###########################################################################
//
Logical
	Hash::TestInstance() const
{
	SortedSocket::TestInstance();

	Check_Pointer(hashTable);
	Verify(hashTableSize > 0);

	return True;
}

//
//###########################################################################
// AddImplementation
//###########################################################################
//
void
	Hash::AddImplementation(Plug *plug)
{
	AddValueImplementation(plug, NULL);
}

//
//###########################################################################
// AddValueImplementation
//###########################################################################
//
void
	Hash::AddValueImplementation(
		Plug *plug,
		const void *value
	)
{
	Check(this);
	Check(plug);
	Check_Pointer(value);

	//
	//-------------------------------------------------------------
	// Verify that value has not been added
	//-------------------------------------------------------------
	//
	Verify(HasUniqueEntries() ? (FindImplementation(value) == NULL) : (Logical)True);

	//
	//-------------------------------------------------------------
	// Find hash entry
	//-------------------------------------------------------------
	//
	IteratorPosition index;

	index = GetHashIndex(value);

	//
	//-------------------------------------------------------------
	// Get vchain for this index
	//-------------------------------------------------------------
	//
	VChain *vchain;

	Check_Pointer(hashTable);
	Verify_Index(index);
	if ((vchain = hashTable[index]) == NULL)
	{
		vchain = MakeVChain();
		Register_Object(vchain);
		hashTable[index] = vchain;
	}

	//
	//-------------------------------------------------------------
	// Add to the vchain
	//-------------------------------------------------------------
	//
	Check(vchain);
	vchain->AddValuePlug(plug, value);
}

//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug*
	Hash::FindImplementation(
		const void *value
	)
{
	Check(this);
	Check_Pointer(value);

	//
	//-------------------------------------------------------------
	// Find hash entry
	//-------------------------------------------------------------
	//
	IteratorPosition index;

	index = GetHashIndex(value);

	//
	//-------------------------------------------------------------
	// Get vchain for this index
	//-------------------------------------------------------------
	//
	VChain *vchain;

	Check_Pointer(hashTable);
	Verify_Index(index);
	if ((vchain = hashTable[index]) == NULL)
	{
		return NULL;
	}

	//
	//-------------------------------------------------------------
	// Find in vchain
	//-------------------------------------------------------------
	//
	Check(vchain);
	return vchain->FindPlug(value);
}

//
//###########################################################################
// MakeVChain
//###########################################################################
//
VChain*
	Hash::MakeVChain()
{
	Fail("Hash::MakeVChain - Should never reach here");
   return NULL;
}

//
//###########################################################################
// MakeVChain
//###########################################################################
//
IteratorPosition
	Hash::GetHashIndex(const void*)
{
	Fail("Hash::GetHashIndex - Should never reach here");
   return 0;
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~ HashIterator ~~~~~~~~~~~~~~~~~~~~~~~~~~~

const IteratorPosition HashIteratorNullPosition = -1;

//
//###########################################################################
// HashIterator
//###########################################################################
//
HashIterator::HashIterator(Hash *hash):
	SortedIterator(hash)
{
	hashTable = hash->hashTable;
	hashTableSize = hash->hashTableSize;
	currentPosition = HashIteratorNullPosition;
	vchainIterator = NULL;
	First();
}

HashIterator::~HashIterator()
{
	hashTable = NULL;
	hashTableSize = 0;
	currentPosition = HashIteratorNullPosition;
	DeleteVChainIterator();
}

//
//###########################################################################
// TestInstance
//###########################################################################
//
Logical
	HashIterator::TestInstance() const
{
	SortedIterator::TestInstance();

	Check_Pointer(hashTable);
	Verify(hashTableSize > 0);

	if (vchainIterator != NULL)
	{
		Check(vchainIterator);
	}

	return True;
}

//
//###########################################################################
// First
//###########################################################################
//
void
	HashIterator::First()
{
	NextVChainIterator(0);
}

//
//###########################################################################
// Last
//###########################################################################
//
void
	HashIterator::Last()
{
	//
	// Should never reach here
	//
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
}

//
//###########################################################################
// Next
//###########################################################################
//
void
	HashIterator::Next()
{
	if (vchainIterator != NULL)
	{
		Check(vchainIterator);

		if (vchainIterator->GetCurrentPlug() != NULL)
		{
			//
			// Try to step to the next item in this list
			//
			vchainIterator->Next();
		}
		if (vchainIterator->GetCurrentPlug() == NULL)
		{
			//
			// At end of list, step to the next list
			//
			NextVChainIterator(currentPosition+1);
		}
	}
}

//
//###########################################################################
// Previous
//###########################################################################
//
void
	HashIterator::Previous()
{
	//
	// Should never reach here
	//
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
}

//
//###########################################################################
// GetCurrentImplementation
//###########################################################################
//
void
	*HashIterator::GetCurrentImplementation()
{
	if (vchainIterator != NULL)
	{
		Check(vchainIterator);

		if (vchainIterator->GetCurrentPlug() != NULL)
		{
			return vchainIterator->GetCurrentPlug();
		}

		//
		// List was emptied, step to next list
		//
		NextVChainIterator(currentPosition+1);

		if (vchainIterator != NULL)
		{
			Check(vchainIterator);
			Verify(vchainIterator->GetCurrentPlug() != NULL);
			return vchainIterator->GetCurrentPlug();
		}
	}
	return NULL;
}

//
//###########################################################################
// GetSize
//###########################################################################
//
CollectionSize
	HashIterator::GetSize()
{
	HashIterator	iterator(Cast_Object(Hash*, socket));
	CollectionSize i = 0;

	while (iterator.ReadAndNextImplementation() != NULL)
	{
		i++;
	}
	return(i);
}

//
//###########################################################################
// Remove
//###########################################################################
//
void
	HashIterator::Remove()
{
	if (vchainIterator != NULL)
	{
		Check(vchainIterator);

		if (vchainIterator->GetCurrentPlug() != NULL)
		{
			vchainIterator->Remove();
			return;
		}

		//
		// List was emptied, step to next list
		//
		NextVChainIterator(currentPosition+1);

		if (vchainIterator != NULL)
		{
			Check(vchainIterator);
			vchainIterator->Remove();
			return;
		}
	}
}

//
//###########################################################################
// FindImplementation
//###########################################################################
//
Plug
	*HashIterator::FindImplementation(
		const void*
	)
{
	//
	// Should never reach here
	//
	#ifdef __BCPLUSPLUS__
		#pragma warn -ccc
			Verify(False);
		#pragma warn +ccc
	#endif
	return NULL;
}

//
//###########################################################################
// ReceiveMemo
//###########################################################################
//
void
	HashIterator::ReceiveMemo(
		IteratorMemo,
		void*
	)
{
}

//
//###########################################################################
//###########################################################################
//
void
	HashIterator::DeleteVChainIterator()
{
	if (vchainIterator != NULL)
	{
		Unregister_Object(vchainIterator);
		delete vchainIterator;
      vchainIterator = NULL;
	}
}

//
//###########################################################################
//###########################################################################
//
void
	HashIterator::NextVChainIterator(IteratorPosition index)
{
	int i;

	DeleteVChainIterator();
	currentPosition = HashIteratorNullPosition;

	for (i = index; i < hashTableSize; i++)
	{
		Check_Pointer(hashTable);
		Verify_Index(i);

		if (hashTable[i] != NULL)
		{
			//
			// This index contains a vchain
			//
			Check(hashTable[i]);

			//
			// Create a vchain iterator
			//
			vchainIterator = new VChainIterator(hashTable[i]);
			Register_Object(vchainIterator);
			if (vchainIterator->GetCurrentPlug() != NULL)
			{
				//
				// The vchain contains items
				//
				currentPosition = i;
				return;
			}

			//
			// Destroy the vchain iterator
			//
			DeleteVChainIterator();
		}
	}
}

#if defined(TEST_CLASS)
#	include "hash.tcp"
#endif