handletable.cpp

基于SD卡的软实现CSP程序

//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// Use of this sample source code is subject to the terms of the Microsoft
// license agreement under which you licensed this sample source code. If
// you did not accept the terms of the license agreement, you are not
// authorized to use this sample source code. For the terms of the license,
// please see the license agreement between you and Microsoft or, if applicable,
// see the LICENSE.RTF on your install media or the root of your tools installation.
// THE SAMPLE SOURCE CODE IS PROVIDED "AS IS", WITH NO WARRANTIES.
//
//
//

/*
HandleTable.cpp
This source file maintains a table of handles (void*s) in
hashtable format.  This is used by CContext and other classes
to ensure handles passed in are actually valid.

History:
jamesku - Created 2/19/2001
*/

#include "HandleTable.h"
#include <windows.h>
#include "assert.h"
#define HANDLE_TABLE_GROWTH_FACTOR (2)
#define HANDLE_TABLE_INITIAL_SIZE (3) //must be at least 2 or expansion will fail  (HANDLE_TABLE_GROWTH_FACTOR) * anything less than 2 casted to an int comes back with the same size)
#define ENTRY_EMPTY (0x0)
#define ENTRY_DELETED (0xFFFFFFFF)


/*
CHandleTable::CHandleTable
Purpose: 
	Constructs a new handle table (effectively a hashtable with
	a linear probe)

Params:
	None

Returns:
	void
*/
CHandleTable::CHandleTable()
{
	//Allocate the initial start table.
	m_pHandleTable = new void*[HANDLE_TABLE_INITIAL_SIZE];
	InitializeCriticalSection(&m_csHandleTable);
	if(!m_pHandleTable)
	{
		m_iHandleTableUsed = 0;
		m_iHandleTableSize = 0;
		return;
	}
	memset(m_pHandleTable,ENTRY_EMPTY,HANDLE_TABLE_INITIAL_SIZE*sizeof(void*));
	m_iHandleTableSize = HANDLE_TABLE_INITIAL_SIZE;
	m_iHandleTableUsed = 0;
}


/*
CHandleTable::~CHandleTable
Purpose: 
	Destructor

Params:
	None.

Returns:
	void
*/
CHandleTable::~CHandleTable()
{
	DeleteCriticalSection(&m_csHandleTable);
	if(m_pHandleTable)
		delete[] m_pHandleTable;
}


/*
CHandleTable::ComputeIndex
Purpose: 
	Computes the index of the handle item in the hashtable.
	Note it ignores the bottom two bits since most ptrs are 4 byte
	multiples this makes them hash "better" if the size of the table 
	is a multiple of 4.

Params:
	void * const IN pHandle: The handle to find the index of.

Returns:
	int : the initial index of the item in the hashtable.
*/
__inline int CHandleTable::ComputeIndex(const void * const IN pHandle)
{
	return ((int)pHandle >> 2) % m_iHandleTableSize;
}


/*
CHandleTable::VerifyExistance
Purpose: 
	Determines if the parameter is a valid handle or not

Params:
	const void * const IN pHandle: The handle to be checked for validity

Returns:
	bool : true if the handle is in the table, false otherwise.
*/
bool CHandleTable::VerifyExistance(const void * const IN pHandle)
{
	if(0 == m_iHandleTableUsed)
		return false;

	EnterCriticalSection(&m_csHandleTable);

	//We should never have a ENTRY_EMPTY or ENTRY_DELETED handle
	assert(pHandle != (void*)ENTRY_DELETED && pHandle != (void*)ENTRY_EMPTY);
	if(pHandle == (void*)ENTRY_DELETED
		|| pHandle == (void*)ENTRY_EMPTY)
	{
		LeaveCriticalSection(&m_csHandleTable);
		return false;
	}

	//Compute the index into the hashtable.
	int iindex = ComputeIndex(pHandle);
	int iStartLoc = iindex;
	assert(iindex < m_iHandleTableSize);
	bool bSuccess = false;

	//Linear probe to find the item
	do
	{
		if(m_pHandleTable[iindex] == pHandle)
			bSuccess = true;
		iindex = (iindex + 1)%m_iHandleTableSize;
	}while(iindex != iStartLoc && m_pHandleTable[iindex] != (void*)ENTRY_EMPTY);

	LeaveCriticalSection(&m_csHandleTable);
	return bSuccess;
}



/*
CHandleTable::AddToTable
Purpose: 
	Adds a new handle to the table.

Params:
	const void * const IN pHandle: The handle to add

Returns:
	bool : true if it was successful, false otherwise.
*/
bool CHandleTable::AddToTable(void * const IN pHandle)
{
	EnterCriticalSection(&m_csHandleTable);
	assert(pHandle != (void*)ENTRY_DELETED && pHandle != (void*)ENTRY_EMPTY);

	if((void*)ENTRY_DELETED == pHandle || (void*)ENTRY_EMPTY == pHandle)
		return false;

	//Grow the table if we need more room to accomodate 
	//the new handle...
	//We assert here if we've used more than there is space
	//in which case we've run past the end of the array.
	assert(m_iHandleTableUsed <= m_iHandleTableSize);
	if(m_iHandleTableUsed >= m_iHandleTableSize)
		if(!GrowTable())
		{
			LeaveCriticalSection(&m_csHandleTable);
			return false;
		}

	//Verify it isn't already in the table.
	if(VerifyExistance(pHandle))
	{
		LeaveCriticalSection(&m_csHandleTable);
		return true;
	}

	//Compute the index into the hashtable.
	int iindex = ComputeIndex(pHandle);
	assert(iindex < m_iHandleTableSize);

	//Find the next index where there is room.
	for(; m_pHandleTable[iindex] != (void*)ENTRY_EMPTY
		&& m_pHandleTable[iindex] != (void*)ENTRY_DELETED;
		iindex = (iindex + 1) % m_iHandleTableSize);

	//Set the item at that index to the handle
	m_pHandleTable[iindex] = pHandle;

	//Increment the amount of space used in the table.
	++m_iHandleTableUsed;
	LeaveCriticalSection(&m_csHandleTable);
	return true;
}


/*
CHandleTable::RemoveFromTable
Purpose: 
	Removes a handle from the table.

Params:
	const void * const IN pHandle: The handle to be removed

Returns:
	void
*/
void CHandleTable::RemoveFromTable(const void * const IN pHandle)
{
	EnterCriticalSection(&m_csHandleTable);

	//This is a very bad pointer if it's either of these two values...
	assert(pHandle != (void*)ENTRY_DELETED && pHandle != (void*)ENTRY_EMPTY);

	//Find where it should be...
	int iindex = ComputeIndex(pHandle);
	int iStartLoc = iindex;
	assert(iindex < m_iHandleTableSize);

	//Find the handle in the table
	do
	{
		if(m_pHandleTable[iindex] == pHandle)
		{
			m_pHandleTable[iindex] = (void*)ENTRY_DELETED;
	        --m_iHandleTableUsed;
			break;
		}
		iindex = (iindex + 1)%m_iHandleTableSize;
	}while(iindex != iStartLoc && m_pHandleTable[iindex] != (void*)ENTRY_EMPTY);

	LeaveCriticalSection(&m_csHandleTable);
}


/*
CHandleTable::GrowTable
Purpose: 
	Grows the size of the table by a factor of HANDLE_TABLE_GROWTH_FACTOR
	and rehashes all of its elements to new positions in the expanded table.
	Note we do not EnterCriticalSection here because this is a private
	member function and as such we must have already entered it as we passed
	through one of the public entrypoints into this class.
	There is no reason to waste time calling it again.

Params:
	None.

Returns:
	bool : Returns true if the table could be grown.
*/
bool CHandleTable::GrowTable()
{
	//We should own the thread
	assert(m_csHandleTable.OwnerThread == (HANDLE)GetCurrentThreadId());
	// handle table should be full
	assert(m_iHandleTableUsed == m_iHandleTableSize);

	//Save the old size of the handle table
	int iOldHandleTableSize = m_iHandleTableSize;

	//Calculate the expanded size
	m_iHandleTableSize = (int)(m_iHandleTableSize*HANDLE_TABLE_GROWTH_FACTOR);

	//Allocate the expanded size
	void** pTmpHandleTable = new void*[m_iHandleTableSize];

	//If the handle table was allocated successfully
	if(!pTmpHandleTable)
	{
		m_iHandleTableSize = iOldHandleTableSize;
		return false;
	}

	m_iHandleTableUsed = 0;
	//Set all its entries to empty:
	memset(pTmpHandleTable, ENTRY_EMPTY, m_iHandleTableSize*sizeof(void*));

	//Save off a ptr to our old handle table
	void** pOldHandleTable = m_pHandleTable;
	//Set the current handle table to the newly alloced array
	m_pHandleTable = pTmpHandleTable;

	//Add all the entries from the old array to the new one
	for(int iindex = 0; iindex < iOldHandleTableSize; ++iindex)
		AddToTable(pOldHandleTable[iindex]);

	//Free the old handle table.
	delete [] pOldHandleTable;

	return true;
}



/*
CHandleTable::GetNext
Purpose: 
	Gets the next item out of the handle table

Params:
	int& iCookie: Where to start looking for the next item.
					MUST be "START" at first call.

Returns:
	void* : A ptr to the item, if there is one, NULL otherwise
*/
void* CHandleTable::GetNext(int& iCookie)
{
	EnterCriticalSection(&m_csHandleTable);

	//If the cookie is not in the table, return false.
	if(iCookie < 0)
		return NULL;

	while(iCookie < m_iHandleTableSize)
	{
		void* pEntry = m_pHandleTable[iCookie++];
		if(pEntry != (void*)ENTRY_DELETED
			&& pEntry != (void*)ENTRY_EMPTY)
		{
			LeaveCriticalSection(&m_csHandleTable);
			return pEntry;
		}
	}

	LeaveCriticalSection(&m_csHandleTable);
	return NULL;
}