ht.h

Windows CE .Net 下面 VOIP编程的经典实例。对于初学Windows 平台下VOIP编程技术的程序员颇具借鉴意义！

//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// Use of this source code is subject to the terms of the Microsoft end-user
// license agreement (EULA) under which you licensed this SOFTWARE PRODUCT.
// If you did not accept the terms of the EULA, you are not authorized to use
// this source code. For a copy of the EULA, please see the LICENSE.RTF on your
// install media.
//
/*************************************************************************


  Disclaimer:

    This code and information is provided "as is" without warranty of
    any kind, either expressed or implied, including but not limited to
    the implied warranties of merchantability and/or fitness for a
    particular purpose.

Module Name:

	ht.h

Abstract:

	Simple hash table using templates.  Unsorted Chained hash w/ HT_SIZE buckets.
	
	  IMPORTANT! delete will be called on any template object stored in the hash upon removal

Notes:

 	This hash table is a chained hash table using a doubly linked list to store collisions.	
 	Presently there are 17 buckets, a decent number for our purposes (Session, buddy, etc), with
 	a good prime for hashing.  The hash table is relatively thread safe (Add / Delete / some searches
 	are guarenteed, but the element pointed to could be killed without another thread knowing).  Since
 	Delete and Add shouldn't occur on the same element in different threads, this is good enough for our
 	purposes.  The hash table makes use of class templates, mainly so it's Clear() function will successfully
 	delete any elements it has (for this purpose it's highly recommended that the hash table is ONLY used with
 	new'ed pointers.  This can be modified for other purposes relatively easily.

**************************************************************************/  

#ifndef _HT_H_
#define _HT_H_

#include <windows.h>

#define HT_SIZE 17 // nice prime, low enough for these purposes
#define HT_LAST NULL
#define HT_INVALID -1

template <class T>
class CNode
{
public:
	CNode():next(NULL), prev(NULL), hKey(NULL) {}
	CNode(HANDLE HKey, T HVal): hKey(HKey), hVal(HVal), next(NULL), prev(NULL) {};
	~CNode();
	
	HANDLE	hKey;
	T		hVal;

	CNode<T>*	next;
	CNode<T>*	prev;
};

template <class T>
class CHashTable
{
public:
				CHashTable();
				~CHashTable();
	BOOL		Add( IN HANDLE hKey, IN T& hVal );
	T&			Access( IN HANDLE hKey);
	void		Clear();
	BOOL		Exist( IN HANDLE hKey );
	BOOL		Remove( IN HANDLE hKey);
	
	T*			First();
	T*			Next();
	T*			Last();

private:
	CNode<T>*			m_Lookup( IN HANDLE hKey );
	BOOL				m_Append( CNode<T>* pNewNode ); 
	int					m_h( IN HANDLE hKey ); // hash function	
	CNode<T>*			m_NodeAry[HT_SIZE];
	CRITICAL_SECTION	csHashTable;
	
	CNode<T>*			pIterNextNode;
};


/************************************************************************************************
 
   CNode destructor
 
 	Since the CSession can only be accessed from inside the CNode, when the CNode dies,
 	kill whatever it contains too.
 
 ************************************************************************************************/

template<class T>
CNode<T>::~CNode()
{
	if (hVal)
		delete hVal;
}


template<class T>
CHashTable<T>::CHashTable()
{		
	for (int i = 0; i < HT_SIZE; i++) {
		m_NodeAry[i] = NULL;
	}

	InitializeCriticalSection( &csHashTable );

	pIterNextNode = NULL;
}


/************************************************************************************************
 
   CHashTable::~CHashTable()
 
 	Cleanup the container, sending a shutdown message on any open sessions.
 
 ************************************************************************************************/

template<class T>
CHashTable<T>::~CHashTable()
{
	// shutdown msg
	Clear();

	// Crashes in RTC will cause the critical section not to be init'ed properly
	DeleteCriticalSection( &csHashTable );
}

/************************************************************************************************
 
   Add()
 
 	Create a new node, then append that node to the appropriate chain of the hash table.
 
 ************************************************************************************************/


template<class T>
BOOL 
CHashTable<T>::Add( 
				IN HANDLE hKey,
				IN T& hVal
				)
{	
	// add to the hash table
	CNode<T>* pNewNode = new CNode<T>( hKey, hVal );

	// check new retval
	if (pNewNode == NULL) {
		return FALSE;
	}

	if (m_Append(pNewNode) == FALSE) {
		// don't want to delete the pointer we we're called with, set 
		// new node's val as NULL to ensure no delete.
		pNewNode->hVal = NULL;
		delete pNewNode;
		return FALSE;
	}

	return TRUE;
}

/************************************************************************************************
 
   CHashTable::Access()
 
 	Get at the pointer for the value, allows for easier debugging.
 
 ************************************************************************************************/

template <class T>
T&
CHashTable<T>::Access( 
				   IN HANDLE hKey
				   ) 
{
	CNode<T>* pNode = m_Lookup(hKey);

    return pNode->hVal;
}


/************************************************************************************************

   CHashTable::Exist()
 
 	Check for the existence of hKey in the hash table
 
 ************************************************************************************************/

template<class T>
BOOL
CHashTable<T>::Exist( 
				  IN HANDLE hKey
				  ) 
{
	CNode<T>* pNode = m_Lookup(hKey);
	
	return pNode != NULL;	
}

/************************************************************************************************
 
   CHashTable::Remove()
 	
 	Remove the Session from the container and call it's destructor, removes
 	both the node and the session itself.
 
 	Thread Safe
 
************************************************************************************************/

template<class T>
BOOL
CHashTable<T>::Remove(
				   IN HANDLE hKey						  
				   )
{	
	CNode<T>* pNode = NULL;
	HANDLE hVal = NULL;
	
	EnterCriticalSection( &csHashTable );
	
	// first check if it exists
	pNode = m_Lookup(hKey);

	// not found, do nothing
	if (pNode == NULL) {
		LeaveCriticalSection( &csHashTable );
		return FALSE;
	}
	
	// we've found it, patch up the list and delete it
	if (pNode->next != NULL) {
		// point the next node to the deleted one's previous
		pNode->next->prev = pNode->prev;
	}

	if (pNode->prev != NULL) {
		// point the previous node to the deleted one's next
		pNode->prev->next = pNode->next;
	} else {
		// prev = head node
		m_NodeAry[m_h(hKey)] = pNode->next;
	}

	LeaveCriticalSection( &csHashTable );
	
	hVal = pNode->hVal;

	// delete the node
	delete pNode;	

	// return the value for external delete (if desired)
	return TRUE;
}

/************************************************************************************************
 
   CHashTable::Clear()
 
 	Remove all sessions from the container, explicitly call their destructors.
 
 	Thread Safe

 ************************************************************************************************/

template<class T>
void
CHashTable<T>::Clear() 
{
	int i;
	HANDLE* pVal = NULL;
	CNode<T>*	pCurrent = NULL;
	CNode<T>*	pPrev = NULL;

	EnterCriticalSection( &csHashTable );

	for (i = 0; i < HT_SIZE; i++) {
		if (m_NodeAry[i] == NULL) {
			continue;
		} else {
			// traverse the list, deleting each object			
			pCurrent = m_NodeAry[i];
	
			while (pCurrent->next != NULL) {
				pPrev = pCurrent;
				pCurrent = pCurrent->next;					

				// delete the previous node
				delete pPrev;
			}

			// now delete the current node
			delete pCurrent;
		}				
	}	

	LeaveCriticalSection( &csHashTable );
}

/************************************************************************************************

  CHashTable::m_Lookup()
 
 	Hash the key, and find the node pointed to, if exist
 
 ************************************************************************************************/


template<class T>
CNode<T>*
CHashTable<T>::m_Lookup( 
					 IN HANDLE hKey 
					 )
{
	CNode<T>* pNode;

	int i = m_h(hKey);

	EnterCriticalSection( &csHashTable );
	pNode = m_NodeAry[i];

	while (pNode != NULL) {
		if (pNode->hKey == hKey) {
			LeaveCriticalSection( &csHashTable );
			return pNode;
		} else {
			pNode = pNode->next;
		}
	}
	
	LeaveCriticalSection( &csHashTable );
	// not found
	return pNode;
}

/************************************************************************************************

  CHashTable::m_h()
 
 	Hash the HANDLE into an integer for one of the hash buckets.
 
 ************************************************************************************************/


template<class T>
int
CHashTable<T>::m_h( 
				IN HANDLE hKey 
				)
{
	// need a more random hash method
	return (unsigned int) hKey %  HT_SIZE;
}

/************************************************************************************************

  CHashTable::m_Append()
 
 	Append a new'ed node to the hash table.
 
 	Thread safe.

 ************************************************************************************************/

template<class T>
BOOL 
CHashTable<T>::m_Append(
					 IN CNode<T>* pNewNode 
					 )
{
	EnterCriticalSection( &csHashTable );	
	int i = m_h( pNewNode->hKey );

	CNode<T>* pCurrent;
	
	if ( m_NodeAry[i] == NULL ) {
		// empty, simply add
		m_NodeAry[i] = 	pNewNode;	
		
	} else {
		// find a spot to place it
		pCurrent = m_NodeAry[i];		
		
		while (pCurrent->next != NULL)
			pCurrent = pCurrent->next;

		pCurrent->next = pNewNode;	

		// retval ok, point new node back to the last in the list
		pCurrent->next->prev = pCurrent;		
	}	

	LeaveCriticalSection( &csHashTable );	

	// success
	return TRUE;
}

/************************************************************************************************

 
   First()
 
 	Return the first item in the hash table (for straight iteration.
 	Point to the next item, as the first could be invalidated after return.
 
 	Thread safe (to an extent)

 ************************************************************************************************/
	
template <class T>
T*
CHashTable<T>::First()
{
	CNode<T>* pFirst = NULL;
	pIterNextNode = NULL;
	
	EnterCriticalSection( &csHashTable );
	// find the first element of the hash table return it as a handle
	for (int i = 0; i < HT_SIZE; i++) {
		if (m_NodeAry[i] == NULL) {
			continue;
		} else {
			if (!pFirst) {
				// this is the first item
				pFirst = m_NodeAry[i];

				// check if the next node is further down this list
				if (pFirst->next) {
					// set next item
					pIterNextNode = pFirst->next;
					LeaveCriticalSection( &csHashTable );
					return &pFirst->hVal;
				}
			} else {
				// this is the next item;
				pIterNextNode = m_NodeAry[i];
				LeaveCriticalSection( &csHashTable );
				return &pFirst->hVal;
			}
		}				
	}	
	
	LeaveCriticalSection( &csHashTable );
	
	if (pFirst) {
		// we found only 1 item, return it
		return &pFirst->hVal;
	}
	// not found
	return HT_LAST;
}

/************************************************************************************************
 
   Next()
 
 	Return the value of the next item on the hash table.  Since the 
 	keys themselves could become invalidated, we must store the next node* as an internal
 	pointer, and prepare it for the next search.
 
 	Thread safe (to an extent)

 ************************************************************************************************/

template <class T>
T*		
CHashTable<T>::Next()
{
	CNode<T>* pCurrent = pIterNextNode;
	pIterNextNode = NULL;
	BOOL bFound = FALSE;

	if (!pCurrent) {
		// uninitialized iterator, no more items on the list
		return HT_LAST;
	}

	// starting with pIterNextNode, find the next element in the hash table
	EnterCriticalSection( &csHashTable );

	if (pCurrent->next) {
		// found it right after the current node
		pIterNextNode = pCurrent->next;
		LeaveCriticalSection( &csHashTable );
		return &pCurrent->hVal;
	}
	else {
		// need to check the others
		for (int i = m_h(pCurrent->hKey) + 1; i < HT_SIZE; i++) {
			if (m_NodeAry[i] == NULL) {
				continue;
			} else {
				pIterNextNode = m_NodeAry[i];
				LeaveCriticalSection( &csHashTable );
				return &pCurrent->hVal;
			}				
		}	
	}

	LeaveCriticalSection( &csHashTable );

	// we have a node, but it's the last (pIterNextNode is still NULL)
	return &pCurrent->hVal;
}
	
/************************************************************************************************

  Last()
	
	  Return the flag for the last item in the hash table
 
 ************************************************************************************************/

template <class T>
T*		
CHashTable<T>::Last()
{
	return HT_LAST;
}


#endif _HT_H_