[Silgraphite-cvs] silgraphite/src/Generic HashMap.cpp,NONE,1.1 HashMap_i.cpp,NONE,1.1 Set_i.cpp,NONE,1.1 Util.cpp,1.2,1.3

[<sil...@li...>]

Update of /cvsroot/silgraphite/silgraphite/src/Generic
In directory sc8-pr-cvs1:/tmp/cvs-serv17051/src/Generic

Modified Files:
	Util.cpp 
Added Files:
	HashMap.cpp HashMap_i.cpp Set_i.cpp 
Log Message:
Added/modified utility files for GrCompiler


--- NEW FILE: HashMap.cpp ---
/*--------------------------------------------------------------------*//*:Ignore this sentence.
Copyright (C) 2001 SIL International. All rights reserved.

Distributable under the terms of either the Common Public License or the
GNU Lesser General Public License, as specified in the LICENSING.txt file.

File: HashMap.cpp
Responsibility: Steve McConnel
Last reviewed: Not yet.

Description:
	This file contains the default implementations of the default hashing and equality
	functors for the various hash map collection classes.
----------------------------------------------------------------------------------------------*/

/***********************************************************************************************
	Include files
***********************************************************************************************/
#include "Main.h"

#pragma hdrstop
#undef THIS_FILE
DEFINE_THIS_FILE

/***********************************************************************************************
	Methods
***********************************************************************************************/
//:End Ignore

/*----------------------------------------------------------------------------------------------
	Compute a hash value from the bits of an arbitrary object, and return the computed value.

	@param pKey Pointer to a block of memory (presumably an object of some sort).
	@param cbKey Number of bytes in the block of memory.
----------------------------------------------------------------------------------------------*/
int HashObj::operator () (void * pKey, int cbKey)
{
	if ((NULL == pKey) || (cbKey <= 0))
		return 0;
	int nHash = 0;
	int i;
	if (0 == (cbKey % isizeof(int)))
	{
		int cn = cbKey / isizeof(int);
		int * pn = (int *)pKey;
		for (i = 0; i < cn; ++i)
			nHash += (nHash << 4) + *pn++;
	}
	else if (0 == (cbKey % isizeof(short)))
	{
		int csu = cbKey / isizeof(short);
		ushort * psu = (ushort *)pKey;
		for (i = 0; i < csu; ++i)
			nHash += (nHash << 4) + *psu++;
	}
	else
	{
		byte * pb = (byte *)pKey;
		for (i = 0; i < cbKey; ++i)
			nHash += (nHash << 4) + *pb++;
	}
	return nHash;
}

/*----------------------------------------------------------------------------------------------
	Compare the bits of two objects for being the same, returning true if the two objects have
	exactly the same bits, and otherwise returning false.

	@param pKey1 Pointer to a block of memory (presumably an object of some sort).
	@param pKey2 Pointer to another block of memory (presumably an object of some sort).
	@param cbKey Number of bytes in each block of memory.
----------------------------------------------------------------------------------------------*/
bool EqlObj::operator () (void * pKey1, void * pKey2, int cbKey)
{
	if (pKey1 == pKey2)
		return true;
	if ((NULL == pKey1) || (NULL == pKey2))
		return false;
	if (cbKey <= 0)
		return true;
	return (0 == memcmp(pKey1, pKey2, cbKey));
}


--- NEW FILE: HashMap_i.cpp ---
/*--------------------------------------------------------------------*//*:Ignore this sentence.
Copyright (C) 2001 SIL International. All rights reserved.

Distributable under the terms of either the Common Public License or the
GNU Lesser General Public License, as specified in the LICENSING.txt file.

File: HashMap_i.cpp
Responsibility: Steve McConnel
Last reviewed: Not yet.

Description:
	This file provides the implementations of methods for the HashMap template collection
	classes.  It is used as an #include file in any file which explicitly instantiates any
	particular type of HashMap<K,T>, HashMapStrUni<T>, or HashMapChars<T>.
----------------------------------------------------------------------------------------------*/
#pragma once
#ifndef HASHMAP_I_C_INCLUDED
#define HASHMAP_I_C_INCLUDED

#include "UtilHashMap.h"
#include <malloc.h>

/***********************************************************************************************
	Methods
***********************************************************************************************/
//:End Ignore

/*----------------------------------------------------------------------------------------------
	Constructor.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	HashMap<K,T,H,Eq>::HashMap()
{
	m_prgihsndBuckets = NULL;
	m_cBuckets = 0;
	m_prghsnd = NULL;
	m_ihsndLim = 0;
	m_ihsndMax = 0;
	m_ihsndFirstFree = FreeListIdx(-1);
}

/*----------------------------------------------------------------------------------------------
	Copy constructor.  It throws an error if it runs out of memory.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	HashMap<K,T,H,Eq>::HashMap(HashMap<K,T,H,Eq> & hm)
{
	m_prgihsndBuckets = NULL;
	m_cBuckets= 0;
	m_prghsnd = NULL;
	m_ihsndLim = 0;
	m_ihsndMax = 0;
	m_ihsndFirstFree = FreeListIdx(-1);
	hm.CopyTo(this);
}

/*----------------------------------------------------------------------------------------------
	Destructor.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	HashMap<K,T,H,Eq>::~HashMap()
{
	Clear();
}

/*----------------------------------------------------------------------------------------------
	Return an iterator that references the first key and value stored in the HashMap.
	If the hash map is empty, Begin returns the same value as End.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	HashMap<K,T,H,Eq>::iterator HashMap<K,T,H,Eq>::Begin()
{
	AssertObj(this);
	int ihsnd;
	for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
	{
		if (m_prghsnd[ihsnd].InUse())
		{
			iterator ithm(this, ihsnd);
			return ithm;
		}
	}
	return End();
}

/*----------------------------------------------------------------------------------------------
	Return an iterator that marks the end of the set of keys and values stored in the HashMap.
	If the HashMap is empty, End returns the same value as Begin.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	HashMap<K,T,H,Eq>::iterator HashMap<K,T,H,Eq>::End()
{
	AssertObj(this);
	iterator ithm(this, m_ihsndLim);
	return ithm;
}

/*----------------------------------------------------------------------------------------------
	Add one key and value to the HashMap.  Insert potentially invalidates existing iterators
	for this HashMap.  An exception is thrown if there are any errors.

	@param key Reference to the key object.  An internal copy is made of this object.
	@param value Reference to the object associated with the key.  An internal copy is
					 made of this object.
	@param fOverwrite Optional flag (defaults to false) to allow a value already associated
					with this key to be replaced by this value.
	@param pihsndOut Optional pointer to an integer for returning the internal index where the
					key-value pair is stored.

	@exception E_INVALIDARG if fOverwrite is not true and the key already is stored with a value
					in this HashMap.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	void HashMap<K,T,H,Eq>::Insert(K & key, T & value, bool fOverwrite, int * pihsndOut)
{
	AssertObj(this);
	// Check for initial allocation of memory.
	if (!m_cBuckets)
	{
		int cBuckets = GetPrimeNear(10);
		m_prgihsndBuckets = (int *)malloc(cBuckets * isizeof(int));
		if (!m_prgihsndBuckets)
			ThrowHr(WarnHr(E_OUTOFMEMORY));
		memset(m_prgihsndBuckets, -1, cBuckets * isizeof(int));
		m_cBuckets = cBuckets;
	}
	if (!m_ihsndMax)
	{
		int iMax = 32;
		m_prghsnd = (HashNode *)malloc(iMax * isizeof(HashNode));
		if (!m_prghsnd)
			ThrowHr(WarnHr(E_OUTOFMEMORY));
		memset(m_prghsnd, 0, iMax * isizeof(HashNode));
		m_ihsndLim = 0;
		m_ihsndMax = iMax;
		m_ihsndFirstFree = FreeListIdx(-1);
	}
	// Check whether this key is already used.
	// If it is, store the value if overwriting is allowed, otherwise return an error value.
	H hasher;
	Eq equal;
	int ihsnd;
	int nHash = hasher(&key, isizeof(K));
	int ie = (unsigned)nHash % m_cBuckets;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K)))
		{
			if (fOverwrite)
			{
				m_prghsnd[ihsnd].PutValue(value);
				if (pihsndOut)
					*pihsndOut = ihsnd;
				AssertObj(this);
				return;
			}
			else
			{
				ThrowHr(WarnHr(E_INVALIDARG));
			}
		}
	}
	// Check whether to increase the number of buckets to redistribute the wealth.
	// Calculate the average depth of hash collection chains.
	// If greater than or equal to two, increase the number of buckets.
	int chsndFree = 0;
	int i;
	for (i = m_ihsndFirstFree; i != FreeListIdx(-1); i = m_prghsnd[FreeListIdx(i)].GetNext())
		++chsndFree;
	int chsndAvgDepth = (m_ihsndLim - chsndFree) / m_cBuckets;
	if (chsndAvgDepth > 2)
	{
		int cNewBuckets = GetPrimeNear(4 * m_cBuckets);
		if (cNewBuckets && cNewBuckets > m_cBuckets)
		{
			int * pNewBuckets = (int *)realloc(m_prgihsndBuckets, cNewBuckets * isizeof(int));
			if (pNewBuckets)
			{
				memset(pNewBuckets, -1, cNewBuckets * isizeof(int));
				m_cBuckets = cNewBuckets;
				m_prgihsndBuckets = pNewBuckets;
				for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
				{
					if (m_prghsnd[ihsnd].InUse())
					{
						ie = (unsigned)m_prghsnd[ihsnd].GetHash() % m_cBuckets;
						m_prghsnd[ihsnd].PutNext(m_prgihsndBuckets[ie]);
						m_prgihsndBuckets[ie] = ihsnd;
					}
				}
				// Recompute the new entry's slot so that it can be stored properly.
				ie = (unsigned)nHash % m_cBuckets;
			}
		}
	}
	if (m_ihsndLim < m_ihsndMax)
	{
		ihsnd = m_ihsndLim;
		++m_ihsndLim;
	}
	else if (m_ihsndFirstFree != FreeListIdx(-1))
	{
		ihsnd = FreeListIdx(m_ihsndFirstFree);
		m_ihsndFirstFree = m_prghsnd[ihsnd].GetNext();
	}
	else
	{
		int iNewMax = (!m_ihsndMax) ? 32 : 2 * m_ihsndMax;
		HashNode * pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode));
		if (!pNewNodes && iNewMax > 32)
		{
			iNewMax = m_ihsndMax + (m_ihsndMax / 2);
			pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode));
			if (!pNewNodes)
				ThrowHr(WarnHr(E_OUTOFMEMORY));
		}
		m_prghsnd = pNewNodes;
		m_ihsndMax = iNewMax;
		Assert(m_ihsndLim < m_ihsndMax);
		ihsnd = m_ihsndLim;
		++m_ihsndLim;
	}
	// Call constructor on previously allocated memory.
	new((void *)&m_prghsnd[ihsnd]) HashNode(key, value, nHash, m_prgihsndBuckets[ie]);
	m_prgihsndBuckets[ie] = ihsnd;
	if (pihsndOut)
		*pihsndOut = ihsnd;
	AssertObj(this);
}

/*----------------------------------------------------------------------------------------------
	Search the HashMap for the given key, and return true if the key is found or false if the
	key is not found.  If the key is found and the given pointer is not NULL, copy the
	associated value to that memory location.

	@param key Reference to a key object.
	@param pvalueRet Pointer to an empty object for storing a copy of the value associated with
					the key, if one exists.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	bool HashMap<K,T,H,Eq>::Retrieve(K & key, T * pvalueRet)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&key, isizeof(K));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K)))
		{
			if (pvalueRet)
				*pvalueRet = m_prghsnd[ihsnd].GetValue();
			return true;
		}
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	Remove the element with the given key from the stored HashMap.  This potentially
	invalidates existing iterators for this HashMap.  If the key is not found in the
	HashMap, then nothing is deleted.

	@param key Reference to a key object.

	@return True if the key is found, and something is actually deleted; otherwise, false.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	bool HashMap<K,T,H,Eq>::Delete(K & key)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&key, isizeof(K));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	int ihsndPrev = -1;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K)))
		{
			if (ihsndPrev == -1)
				m_prgihsndBuckets[ie] = m_prghsnd[ihsnd].GetNext();
			else
				m_prghsnd[ihsndPrev].PutNext(m_prghsnd[ihsnd].GetNext());
			m_prghsnd[ihsnd].~HashNode();		// Ensure member destructors are called.
			memset(&m_prghsnd[ihsnd], 0, isizeof(HashNode));
			m_prghsnd[ihsnd].PutNext(m_ihsndFirstFree);
			m_ihsndFirstFree = FreeListIdx(ihsnd);
			AssertObj(this);
			return true;
		}
		ihsndPrev = ihsnd;
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	Free all the memory used by the HashMap.  When done, only the minimum amount of
	bookkeeping memory is still taking up space, and any internal pointers all been set
	to NULL.  The appropriate destructor is called for all key and value objects stored
	in the HashMap before the memory space is freed.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	void HashMap<K,T,H,Eq>::Clear()
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return;
	int ihsnd;
	for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
	{
		if (m_prghsnd[ihsnd].InUse())
			m_prghsnd[ihsnd].~HashNode();	// Ensure member destructors are called.
	}
	free(m_prgihsndBuckets);
	free(m_prghsnd);
	m_prgihsndBuckets = NULL;
	m_cBuckets = 0;
	m_prghsnd = NULL;
	m_ihsndLim = 0;
	m_ihsndMax = 0;
	m_ihsndFirstFree = FreeListIdx(-1);
	AssertObj(this);
}

/*----------------------------------------------------------------------------------------------
	Copy the content of one HashMap to another.  An exception is thrown if there are any errors.

	@param hmKT Reference to the other HashMap.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	void HashMap<K,T,H,Eq>::CopyTo(HashMap<K,T,H,Eq> & hmKT)
{
	AssertObj(this);
	AssertObj(&hmKT);
	hmKT.Clear();
	iterator itmm;
	for (itmm = Begin(); itmm != End(); ++itmm)
		hmKT.Insert(itmm->GetKey(), itmm->GetValue());
}

/*----------------------------------------------------------------------------------------------
	Copy the content of one HashMap to another.  An exception is thrown if there are any errors.

	@param phmKT Pointer to the other HashMap.

	@exception E_POINTER if phmKT is NULL.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	void HashMap<K,T,H,Eq>::CopyTo(HashMap<K,T,H,Eq> * phmKT)
{
	if (!phmKT)
		ThrowHr(WarnHr(E_POINTER));
	CopyTo(*phmKT);
}

/*----------------------------------------------------------------------------------------------
	If the given key is found in the HashMap, return true, and if the provided index pointer
	is not NULL, also store the internal index value in the indicated memory location.
	If the given key is NOT found in the HashMap, return false and ignore the provided index
	pointer.

	@param key Reference to a key object.
	@param pihsndRet Pointer to an integer for returning the internal index where the
					key-value pair is stored.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	bool HashMap<K,T,H,Eq>::GetIndex(K & key, int * pihsndRet)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&key, isizeof(K));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K)))
		{
			if (pihsndRet)
				*pihsndRet = ihsnd;
			return true;
		}
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	If the given internal HashMap index is valid, return true, and if the provided pointer to a
	key object is not NULL, also copy the indexed key to the indicated memory location.
	If the given internal index is NOT valid, return false, and ignore the provided key
	object pointer.

	@param ihsnd Internal index value returned earlier by GetIndex or Insert.
	@param pkeyRet Pointer to an empty key object for storing a copy of the key found at the
				indexed location.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	bool HashMap<K,T,H,Eq>::IndexKey(int ihsnd, K * pkeyRet)
{
	AssertObj(this);
	if ((ihsnd < 0) || (ihsnd >= m_ihsndLim))
		return false;
	if (m_prghsnd[ihsnd].InUse())
	{
		if (pkeyRet)
			*pkeyRet = m_prghsnd[ihsnd].GetKey();
		return true;
	}
	else
	{
		return false;
	}
}

/*----------------------------------------------------------------------------------------------
	If the given internal HashMap index is valid, return true, and if the provided pointer to an
	object is not NULL, also copy the indexed value to the indicated memory location.
	If the given internal index is NOT valid, return false, and ignore the provided
	object pointer.

	@param ihsnd Internal index value returned earlier by GetIndex or Insert.
	@param pvalueRet Pointer to an empty object for storing a copy of the value found at the
				indexed location.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	bool HashMap<K,T,H,Eq>::IndexValue(int ihsnd, T * pvalueRet)
{
	AssertObj(this);
	if (ihsnd < 0 || ihsnd >= m_ihsndLim)
		return false;
	if (m_prghsnd[ihsnd].InUse())
	{
		if (pvalueRet)
			*pvalueRet = m_prghsnd[ihsnd].GetValue();
		return true;
	}
	else
	{
		return false;
	}
}

/*----------------------------------------------------------------------------------------------
	Return the number of items (key-value pairs) stored in the HashMap.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	int HashMap<K,T,H,Eq>::Size()
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return 0;
	int chsndFree = 0;
	int ihsnd;
	for (ihsnd = m_ihsndFirstFree;
		 ihsnd != FreeListIdx(-1);
		 ihsnd = m_prghsnd[FreeListIdx(ihsnd)].GetNext())
	{
		++chsndFree;
	}
	return m_ihsndLim - chsndFree;
}

//:Ignore
#ifdef DEBUG
/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) currently allocated for the hash map.  This is
	useful only for debugging the hash map mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	int HashMap<K,T,H,Eq>::_BucketCount()
{
	AssertObj(this);
	return m_cBuckets;
}

/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) that do not point to a list of HashNode objects.
	This is useful only for debugging the hash map mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	int HashMap<K,T,H,Eq>::_EmptyBuckets()
{
	AssertObj(this);
	int ceUnused = 0;
	int ie;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		if (m_prgihsndBuckets[ie] == -1)
			++ceUnused;
	}
	return ceUnused;
}

/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) that currently point to a list of HashNode
	objects in the hash map.  This is useful only for debugging the hash map mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	int HashMap<K,T,H,Eq>::_BucketsUsed()
{
	AssertObj(this);
	int ceUsed = 0;
	int ie;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		if (m_prgihsndBuckets[ie] != -1)
			++ceUsed;
	}
	return ceUsed;
}

/*----------------------------------------------------------------------------------------------
	Return the length of the longest list of HashNode objects stored in any bucket (hash slot)
	of the hash map.  This is useful only for debugging the hash map mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class K, class T, class H, class Eq>
	int HashMap<K,T,H,Eq>::_FullestBucket()
{
	AssertObj(this);
	int chsndMax = 0;
	int chsnd;
	int ie;
	int ihsnd;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		chsnd = 0;
		for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
			++chsnd;
		if (chsndMax < chsnd)
			chsndMax = chsnd;
	}
	return chsndMax;
}
#endif
//:End Ignore


// Local Variables:
// mode:C++
// c-file-style:"cellar"
// tab-width:4
// End:

#endif /*HASHMAP_I_C_INCLUDED*/

--- NEW FILE: Set_i.cpp ---
/*--------------------------------------------------------------------*//*:Ignore this sentence.
Copyright (C) 2001 SIL International. All rights reserved.

Distributable under the terms of either the Common Public License or the
GNU Lesser General Public License, as specified in the LICENSING.txt file.

File: Set_i.cpp
Responsibility: Steve McConnel
Last reviewed: Not yet.

Description:
	This file provides the implementations of the methods for the Set template collection class.
	It is used as an #include file in any file which explicitly instantiates any particular type
	of Set<T>.
----------------------------------------------------------------------------------------------*/
#pragma once
#ifndef SET_I_C_INCLUDED
#define SET_I_C_INCLUDED

#include "UtilSet.h"
#include <malloc.h>

/***********************************************************************************************
	Methods.
***********************************************************************************************/
//:End Ignore

/*----------------------------------------------------------------------------------------------
	Constructor.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	Set<T,H,Eq>::Set()
{
	m_prgihsndBuckets = NULL;
	m_cBuckets = 0;
	m_prghsnd = NULL;
	m_ihsndLim = 0;
	m_ihsndMax = 0;
	m_ihsndFirstFree = FreeListIdx(-1);
}

/*----------------------------------------------------------------------------------------------
	Destructor.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	Set<T,H,Eq>::~Set()
{
	Clear();
}

/*----------------------------------------------------------------------------------------------
	Return an iterator that references the first value stored in the set.
	If the set is empty, Begin returns the same value as End.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	Set<T,H,Eq>::iterator Set<T,H,Eq>::Begin()
{
	int ihsnd;
	for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
	{
		if (m_prghsnd[ihsnd].InUse())
		{
			iterator itset(this, ihsnd);
			return itset;
		}
	}
	return End();
}

/*----------------------------------------------------------------------------------------------
	Return an iterator that marks the end of the set of values stored in the set.
	If the set is empty, End returns the same value as Begin.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	Set<T,H,Eq>::iterator Set<T,H,Eq>::End()
{
	iterator itset(this, m_ihsndLim);
	return itset;
}

/*----------------------------------------------------------------------------------------------
	Add one value to the set.  Insert potentially invalidates existing iterators for this
	set.  An exception is thrown if there are any errors.

	@param value Reference to a copy of the object to store in the set.  An internal copy is
				made of this object.
	@param pihsndOut Optional pointer to an integer for returning the internal index where the
				object is stored.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	void Set<T,H,Eq>::Insert(T & value, int * pihsndOut)
{
	AssertObj(this);
	// Check for initial allocation of memory.
	if (!m_cBuckets)
	{
		int cBuckets = GetPrimeNear(10);
		m_prgihsndBuckets = (int *)malloc(cBuckets * isizeof(int));
		if (!m_prgihsndBuckets)
			ThrowHr(WarnHr(E_OUTOFMEMORY));
		memset(m_prgihsndBuckets, -1, cBuckets * isizeof(int));
		m_cBuckets = cBuckets;
	}
	if (!m_ihsndMax)
	{
		int iMax = 32;
		m_prghsnd = (HashNode *)malloc(iMax * isizeof(HashNode));
		if (!m_prghsnd)
			ThrowHr(WarnHr(E_OUTOFMEMORY));
		memset(m_prghsnd, 0, iMax * isizeof(HashNode));
		m_ihsndLim = 0;
		m_ihsndMax = iMax;
		m_ihsndFirstFree = FreeListIdx(-1);
	}
	// Check whether this value is already present. If so, do nothing.
	H hasher;
	Eq equal;
	int ihsnd;
	int nHash = hasher(&value, isizeof(T));
	int ie = (unsigned)nHash % m_cBuckets;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&value, &m_prghsnd[ihsnd].GetValue(), isizeof(T)))
		{
			return;
		}
	}
	// Check whether to increase the number of buckets to redistribute the wealth.
	// Calculate the average depth of hash collection chains.
	// If greater than or equal to two, increase the number of buckets.
	int chsndFree = 0;
	int i;
	for (i = m_ihsndFirstFree; i != FreeListIdx(-1); i = m_prghsnd[FreeListIdx(i)].GetNext())
		++chsndFree;
	int chsndAvgDepth = (m_ihsndLim - chsndFree) / m_cBuckets;
	if (chsndAvgDepth > 2)
	{
		int cNewBuckets = GetPrimeNear(4 * m_cBuckets);
		if (cNewBuckets && cNewBuckets > m_cBuckets)
		{
			int * pNewBuckets = NULL;
			if (cNewBuckets)
				pNewBuckets = (int *)realloc(m_prgihsndBuckets, cNewBuckets * isizeof(int));
			if (pNewBuckets)
			{
				memset(pNewBuckets, -1, cNewBuckets * isizeof(int));
				m_cBuckets = cNewBuckets;
				m_prgihsndBuckets = pNewBuckets;
				for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
				{
					if (m_prghsnd[ihsnd].InUse())
					{
						ie = (unsigned)m_prghsnd[ihsnd].GetHash() % m_cBuckets;
						m_prghsnd[ihsnd].PutNext(m_prgihsndBuckets[ie]);
						m_prgihsndBuckets[ie] = ihsnd;
					}
				}
				// Recompute the new entry's slot so that it can be stored properly.
				ie = (unsigned)nHash % m_cBuckets;
			}
		}
	}
	if (m_ihsndLim < m_ihsndMax)
	{
		ihsnd = m_ihsndLim;
		++m_ihsndLim;
	}
	else if (m_ihsndFirstFree != FreeListIdx(-1))
	{
		ihsnd = FreeListIdx(m_ihsndFirstFree);
		m_ihsndFirstFree = m_prghsnd[ihsnd].GetNext();
	}
	else
	{
		int iNewMax = (!m_ihsndMax) ? 32 : 2 * m_ihsndMax;
		HashNode * pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode));
		if (!pNewNodes && iNewMax > 32)
		{
			iNewMax = m_ihsndMax + (m_ihsndMax / 2);
			pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode));
			if (!pNewNodes)
				ThrowHr(WarnHr(E_OUTOFMEMORY));
		}
		m_prghsnd = pNewNodes;
		m_ihsndMax = iNewMax;
		Assert(m_ihsndLim < m_ihsndMax);
		ihsnd = m_ihsndLim;
		++m_ihsndLim;
	}
	// Call constructor on previously allocated memory.
	new((void *)&m_prghsnd[ihsnd]) HashNode(value, nHash, m_prgihsndBuckets[ie]);
	m_prgihsndBuckets[ie] = ihsnd;
	if (pihsndOut)
		*pihsndOut = ihsnd;
	AssertObj(this);
}

/*----------------------------------------------------------------------------------------------
	Return true if the given value is found in the set, or false if it is not found.

	@param value Reference to a copy of the object to search for in the set.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	bool Set<T,H,Eq>::IsMember(T & value)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&value, isizeof(T));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&value, &m_prghsnd[ihsnd].GetValue(), isizeof(T)))
		{
			return true;
		}
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	Remove the element with the given value from the stored set.  This potentially
	invalidates existing iterators for this set.  If the value is not found in the set,
	then nothing is deleted.

	@param value Reference to a copy of the object to delete from the set.

	@return True if the value is found, and something is actually deleted; otherwise, false.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	bool Set<T,H,Eq>::Delete(T & value)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&value, isizeof(T));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	int ihsndPrev = -1;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&value, &m_prghsnd[ihsnd].GetValue(), isizeof(T)))
		{
			if (ihsndPrev == -1)
				m_prgihsndBuckets[ie] = m_prghsnd[ihsnd].GetNext();
			else
				m_prghsnd[ihsndPrev].PutNext(m_prghsnd[ihsnd].GetNext());

			m_prghsnd[ihsnd].~HashNode();		// Ensure member destructors are called.
			memset(&m_prghsnd[ihsnd], 0, isizeof(HashNode));
			m_prghsnd[ihsnd].PutNext(m_ihsndFirstFree);
			m_ihsndFirstFree = FreeListIdx(ihsnd);
			AssertObj(this);
			return true;
		}
		ihsndPrev = ihsnd;
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	Free all the memory used by the set.  When done, only the minimum amount of
	bookkeeping memory is still taking up space, and any internal pointers all been set
	to NULL.  The appropriate destructor is called for all key and value objects stored
	in the set before the memory space is freed.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	void Set<T,H,Eq>::Clear()
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return;
	int ihsnd;
	for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd)
	{
		if (m_prghsnd[ihsnd].InUse())
			m_prghsnd[ihsnd].~HashNode();	// Ensure member destructors are called.
	}
	free(m_prgihsndBuckets);
	free(m_prghsnd);
	m_prgihsndBuckets = NULL;
	m_cBuckets = 0;
	m_prghsnd = NULL;
	m_ihsndLim = 0;
	m_ihsndMax = 0;
	m_ihsndFirstFree = FreeListIdx(-1);
	AssertObj(this);
}

/*----------------------------------------------------------------------------------------------
	If the given value is found in the set, return true, and if the provided index pointer
	is not NULL, also store the value's internal index in the indicated memory location.
	If the given value is NOT found in the set, return false and ignore the provided index
	pointer.

	@param value Reference to a copy of the object to search for in the set.
	@param pihsndRet Optional pointer to an integer for storing the internal index value.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	bool Set<T,H,Eq>::GetIndex(T & value, int * pihsndRet)
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return false;
	H hasher;
	Eq equal;
	int nHash = hasher(&value, isizeof(T));
	int ie = (unsigned)nHash % m_cBuckets;
	int ihsnd;
	for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
	{
		if ((nHash == m_prghsnd[ihsnd].GetHash()) &&
			equal(&value, &m_prghsnd[ihsnd].GetValue(), isizeof(T)))
		{
			if (pihsndRet)
				*pihsndRet = ihsnd;
			return true;
		}
	}
	return false;
}

/*----------------------------------------------------------------------------------------------
	If the given index is valid, return true, and if the provided pointer to a
	T object is not NULL, also copy the indexed value to the indicated memory location.
	If the given index is NOT valid, return false, and ignore the provided value
	object pointer.

	@param ihsnd Index into the set's internal data structure.
	@param pvalueRet Optional pointer to a place for storing a copy of the stored value.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	bool Set<T,H,Eq>::IndexValue(int ihsnd, T * pvalueRet)
{
	AssertObj(this);
	if (ihsnd < 0 || ihsnd >= m_ihsndLim)
		return false;
	if (m_prghsnd[ihsnd].InUse())
	{
		if (pvalueRet)
			*pvalueRet = m_prghsnd[ihsnd].GetValue();
		return true;
	}
	else
	{
		return false;
	}
}

/*----------------------------------------------------------------------------------------------
	Return the number of items stored in the set.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	int Set<T,H,Eq>::Size()
{
	AssertObj(this);
	if (!m_prgihsndBuckets)
		return 0;
	int chsndFree = 0;
	int ihsnd;
	for (ihsnd = m_ihsndFirstFree;
		 ihsnd != FreeListIdx(-1);
		 ihsnd = m_prghsnd[FreeListIdx(ihsnd)].GetNext())
	{
		++chsndFree;
	}
	return m_ihsndLim - chsndFree;
}

/*----------------------------------------------------------------------------------------------
	Return true if the sets are equal, in the sense that they are the same size, and every
	member of *this is a member of the argument set.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	bool Set<T,H,Eq>::Equals(Set<T, H, Eq> & itset)
{
	AssertObj(this);
	if (Size() != itset.Size())
		return false;
	iterator it = Begin();
	iterator itEnd = End();
	for ( ; it != itEnd; ++it)
	{
		if (!itset.IsMember(*it))
			return false;
	}
	return true;
}


#ifdef DEBUG
/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) currently allocated for the set.  This is
	useful only for debugging the set mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	int Set<T,H,Eq>::_BucketCount()
{
	AssertObj(this);
	return m_cBuckets;
}

/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) that do not point to a list of HashNode objects.
	This is useful only for debugging the set mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	int Set<T,H,Eq>::_EmptyBuckets()
{
	AssertObj(this);
	int ceUnused = 0;
	int ie;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		if (m_prgihsndBuckets[ie] == -1)
			++ceUnused;
	}
	return ceUnused;
}

/*----------------------------------------------------------------------------------------------
	Return the number of buckets (hash slots) that currently point to a list of HashNode
	objects in the set.  This is useful only for debugging the set mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	int Set<T,H,Eq>::_BucketsUsed()
{
	AssertObj(this);
	int ceUsed = 0;
	int ie;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		if (m_prgihsndBuckets[ie] != -1)
			++ceUsed;
	}
	return ceUsed;
}

/*----------------------------------------------------------------------------------------------
	Return the length of the longest list of HashNode objects stored in any bucket (hash slot)
	of the set.  This is useful only for debugging the set mechanism itself.
----------------------------------------------------------------------------------------------*/
template<class T, class H, class Eq>
	int Set<T,H,Eq>::_FullestBucket()
{
	AssertObj(this);
	int chsndMax = 0;
	int chsnd;
	int ie;
	int ihsnd;
	for (ie = 0; ie < m_cBuckets; ++ie)
	{
		chsnd = 0;
		for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext())
			++chsnd;
		if (chsndMax < chsnd)
			chsndMax = chsnd;
	}
	return chsndMax;
}
#endif /*DEBUG*/

// Local Variables:
// mode:C++
// c-file-style:"cellar"
// tab-width:4
// End:

#endif /*SET_I_C_INCLUDED*/

Index: Util.cpp
===================================================================
RCS file: /cvsroot/silgraphite/silgraphite/src/Generic/Util.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- Util.cpp	1 Apr 2003 09:00:02 -0000	1.2
+++ Util.cpp	17 Apr 2003 22:04:03 -0000	1.3
@@ -121,3 +121,134 @@
 
 #endif //!NO_ASM
 }
+
+/***********************************************************************************************
+	Integer utilities.
+***********************************************************************************************/
+
+/*
+ * table of powers of 2, and largest prime smaller than each power of 2
+ *   n    2**n       prime      diff
+ *  --- ----------  ----------  ----
+ *   2:          4           3  ( -1)
+ *   3:          8           7  ( -1)
+ *   4:         16          13  ( -3)
+ *   5:         32          31  ( -1)
+ *   6:         64          61  ( -3)
+ *   7:        128         127  ( -1)
+ *   8:        256         251  ( -5)
+ *   9:        512         509  ( -3)
+ *  10:       1024        1021  ( -3)
+ *  11:       2048        2039  ( -9)
+ *  12:       4096        4093  ( -3)
+ *  13:       8192        8191  ( -1)
+ *  14:      16384       16381  ( -3)
+ *  15:      32768       32749  (-19)
+ *  16:      65536       65521  (-15)
+ *  17:     131072      131071  ( -1)
+ *  18:     262144      262139  ( -5)
+ *  19:     524288      524287  ( -1)
+ *  20:    1048576     1048573  ( -3)
+ *  21:    2097152     2097143  ( -9)
+ *  22:    4194304     4194301  ( -3)
+ *  23:    8388608     8388593  (-15)
+ *  24:   16777216    16777213  ( -3)
+ *  25:   33554432    33554393  (-39)
+ *  26:   67108864    67108859  ( -5)
+ *  27:  134217728   134217689  (-39)
+ *  28:  268435456   268435399  (-57)
+ *  29:  536870912   536870909  ( -3)
+ *  30: 1073741824  1073741789  (-35)
+ *  31: 2147483648  2147483647  ( -1)
+ *  32: 4294967296  4294967291	( -5)
+ */
+const static uint g_rguPrimes[] = {
+	3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093,	8191, 16381, 32749, 65521, 131071,
+	262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
+	134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291
+};
+
+
+/*----------------------------------------------------------------------------------------------
+	Returns the prime in g_rguPrimes that is closest to u.
+----------------------------------------------------------------------------------------------*/
+uint GetPrimeNear(uint u)
+{
+	int cu = isizeof(g_rguPrimes) / isizeof(uint);
+	int iuMin;
+	int iuLim;
+	int iu;
+
+	for (iuMin = 0, iuLim = cu; iuMin < iuLim; )
+	{
+		iu = (iuMin + iuLim) / 2;
+		if (u > g_rguPrimes[iu])
+			iuMin = iu + 1;
+		else
+			iuLim = iu;
+	}
+	Assert(iuMin == cu || iuMin < cu && u <= g_rguPrimes[iuMin]);
+	Assert(iuMin == 0 || iuMin > 0 && u > g_rguPrimes[iuMin - 1]);
+
+	if (!iuMin)
+		return g_rguPrimes[0];
+	if (iuMin == cu)
+		return g_rguPrimes[cu - 1];
+	if (g_rguPrimes[iuMin] - u < u - g_rguPrimes[iuMin - 1])
+		return g_rguPrimes[iuMin];
+	return g_rguPrimes[iuMin - 1];
+}
+
+
+/*----------------------------------------------------------------------------------------------
+	Returns the prime in g_rguPrimes that is larger than u or is the largest in the list.
+----------------------------------------------------------------------------------------------*/
+uint GetLargerPrime(uint u)
+{
+	int cu = isizeof(g_rguPrimes) / isizeof(uint);
+	int iuMin;
+	int iuLim;
+	int iu;
+
+	for (iuMin = 0, iuLim = cu; iuMin < iuLim; )
+	{
+		iu = (iuMin + iuLim) / 2;
+		if (u >= g_rguPrimes[iu])
+			iuMin = iu + 1;
+		else
+			iuLim = iu;
+	}
+	Assert(iuMin == cu || iuMin < cu && u < g_rguPrimes[iuMin]);
+	Assert(iuMin == 0 || iuMin > 0 && u >= g_rguPrimes[iuMin - 1]);
+
+	if (iuMin == cu)
+		return g_rguPrimes[cu - 1];
+	return g_rguPrimes[iuMin];
+}
+
+
+/*----------------------------------------------------------------------------------------------
+	Returns the prime in g_rguPrimes that is smaller than u or is the smallest in the list.
+----------------------------------------------------------------------------------------------*/
+uint GetSmallerPrime(uint u)
+{
+	int cu = isizeof(g_rguPrimes) / isizeof(uint);
+	int iuMin;
+	int iuLim;
+	int iu;
+
+	for (iuMin = 0, iuLim = cu; iuMin < iuLim; )
+	{
+		iu = (iuMin + iuLim) / 2;
+		if (u > g_rguPrimes[iu])
+			iuMin = iu + 1;
+		else
+			iuLim = iu;
+	}
+	Assert(iuMin == cu || iuMin < cu && u <= g_rguPrimes[iuMin]);
+	Assert(iuMin == 0 || iuMin > 0 && u > g_rguPrimes[iuMin - 1]);
+
+	if (!iuMin)
+		return g_rguPrimes[0];
+	return g_rguPrimes[iuMin - 1];
+}