tcshl.cpp

来自「并行TIN生成算法, 基于DeWall算法理论实现」· C++ 代码 · 共 382 行

// TcsHL.cpp
// 邓雪清, 2008/12/15

#include "TcsHL.h"

/////////////////////////////////////////////////////////////////////////////
// CTcsHL

CTcsHL::CTcsHL(long nSize)
{
	m_nSize = -1;
	m_eSize = 0;
	m_eFunc = 0;
	m_hFunc = 0;
	m_pHead = 0;
	m_pFree = 0;
	m_mLock = 0;

	if (!nSize)	nSize = 128;
	for ( ; nSize; nSize >>= 1)
		++m_nSize;

	m_pHead = new NODE*[1 << m_nSize];
	memset(m_pHead, 0, (1 << m_nSize) * sizeof(NODE*));

	m_mLock = ::CreateMutex(0, 0, 0);
}

CTcsHL::CTcsHL(long nSize, EQLH_FUNC eFunc, HASH_FUNC hFunc)
{
	m_nSize = -1;
	m_eSize = 0;
	m_eFunc = 0;
	m_hFunc = 0;
	m_pHead = 0;
	m_pFree = 0;
	m_mLock = 0;
	if (!eFunc || !hFunc)
		return;

	m_eFunc = eFunc;
	m_hFunc = hFunc;
	if (!nSize)	nSize = 128;
	for ( ; nSize; nSize >>= 1)
		++m_nSize;

	m_pHead = new NODE*[1 << m_nSize];
	memset(m_pHead, 0, (1 << m_nSize) * sizeof(NODE*));

	m_mLock = ::CreateMutex(0, 0, 0);
}

CTcsHL::~CTcsHL(void)
{
	if (m_mLock)
		::WaitForSingleObject(m_mLock, INFINITE);

	NODE *p, *n, **pp;
	NODE **old = m_pHead;
	NODE **end = old + (1 << m_nSize);

	for (pp = old; pp < end; ++pp)
	{
		p = *pp;
		while (p)
		{	n = p->next;	delete p;	p = n;	}
	}
	if (m_pHead)
		delete []m_pHead;

	p = m_pFree;
	while (p)
	{	n = p->next;	delete p;	p = n;	}

	if (m_mLock)
		::CloseHandle(m_mLock);
}

uong CTcsHL::Hash(void *code)
{
	uong hash = EQHASH(code);

	hash >>= (28 - m_nSize);
	hash &= ((1 << m_nSize) - 1);

	return hash;
}

CTcsHL::NODE **CTcsHL::Lookup(void *code)
{
	NODE **pp, *p;

	uong hash = Hash(code);

	for (pp = &m_pHead[hash]; (p = *pp); pp = &p->next)
	{
		if (p->code == code)
			return pp;
	}

	return pp;
}

CTcsHL::NODE **CTcsHL::Lookup(void *code, uong hash)
{
	NODE **pp, *p;

	uong idx = hash;
	
	idx >>= (28 - m_nSize);
	idx &= ((1 << m_nSize) - 1);
	
	for (pp = &m_pHead[idx]; (p = *pp); pp = &p->next)
	{
		if (hash == p->hash && (*m_eFunc)(p->code, code))
			return pp;
	}

	return pp;
}

void *CTcsHL::GetData(void *code)
{
	if (m_eFunc)
	{
		uong hash = (*m_hFunc)(code);
		NODE *p, **pp = Lookup(code, hash);
		return (p = *pp) ? p->data : (void*)0;
	}
	else
	{
		NODE *p, **pp = Lookup(code);
		return (p = *pp) ? p->data : (void*)0;
	}
}

void CTcsHL::Grow(void)
{
	if (m_eFunc)
	{
		long nSize = 1 << m_nSize;
		if (!m_pFree && 2 * m_eSize > nSize)
		{
			NODE **old = m_pHead;
			NODE **end = old + nSize;
			NODE **opp, **pp, *p, *next;
			
			++m_nSize;
			m_pHead = new NODE*[2 * nSize];
			memset(m_pHead, 0, (2 * nSize) * sizeof(NODE*));
			for (opp = old; opp < end; ++opp)
			{
				p = *opp;
				while (p)
				{
					next = p->next;		pp = Lookup(p->code, p->hash);
					p->next = *pp;	*pp = p;	p = next;
				}
			}
			delete []old;
		}
	}
	else
	{
		long nSize = 1 << m_nSize;
		if (!m_pFree && 2 * m_eSize > nSize)
		{
			NODE **old = m_pHead;
			NODE **end = old + nSize;
			NODE **opp, **pp, *p, *next;
			
			++m_nSize;
			m_pHead = new NODE*[2 * nSize];
			memset(m_pHead, 0, (2 * nSize) * sizeof(NODE*));
			for (opp = old; opp < end; ++opp)
			{
				p = *opp;
				while (p)
				{
					next = p->next;		pp = Lookup(p->code);
					p->next = *pp;	*pp = p;	p = next;
				}
			}
			delete []old;
		}
	}
}

void *CTcsHL::PutData(void *code, void *data)
{
	if (!data)	return 0;

	NODE *p, **pp;
	uong hash = 0;

	if (m_hFunc)
		hash = (*m_hFunc)(code);

	Grow();

	if (m_hFunc)
		pp = Lookup(code, hash);
	else
		pp = Lookup(code);

	if ((p = *pp))
		p->data = data;	// Replace current value
	else
	{
		if ((p = m_pFree))
			m_pFree = p->next;
		else
			p = new NODE;
		
		p->next = 0;		p->code = code;
		p->data = data;		p->hash = hash;
		*pp = p;	++m_eSize;
	}

	return data;
}

void *CTcsHL::DetData(void *code)
{
	NODE *p, **pp;

	if (m_hFunc)
	{
		uong hash = (*m_hFunc)(code);
		pp = Lookup(code, hash);
	}
	else
		pp = Lookup(code);

	if ((p = *pp))
	{
		*pp = p->next;	p->next = m_pFree;
		m_pFree = p;	--m_eSize;
		return p->data;
	}
	else
		return 0;
}

void *CTcsHL::GetHead(void)
{
	void *data = 0;
	NODE **old = m_pHead;
	m_oSize = 1 << m_nSize;
	NODE **end = old + m_oSize;

	m_nHidx = 0;
	for (NODE *p, **pp = old; pp < end; ++pp, ++m_nHidx)
	{
		if ((p = *pp))
		{
			data = p->data;
			if (p->next)
				m_nEidx = 1;
			else
			{
				m_nEidx = 0;
				m_nHidx++;
			}

			return data;
		}
	}

	return data;
}

void *CTcsHL::GetNext(void)
{
	if (0 > m_nHidx)	return 0;

	long i;
	NODE *p, **pp;
	void *data = 0;

	while (m_nHidx < m_oSize)
	{
		pp = &m_pHead[m_nHidx];
		if ((p = *pp))
		{
			i = 0;
			while (i < m_nEidx && p)
			{
				p = p->next;
				i++;
			}
			if (p)
			{
				data = p->data;
				if (p->next)
					m_nEidx += 1;
				else
				{
					m_nEidx = 0;
					m_nHidx++;
				}

				return data;
			}
			else
			{	m_nHidx++;	m_nEidx = 0;	}
		}
		else
		{	m_nHidx++;	m_nEidx = 0;	}
	}

	return data;
}

void *CTcsHL::RemoveHead(void)
{
	void *data = 0;
	NODE **old = m_pHead;
	m_oSize = 1 << m_nSize;
	NODE **end = old + m_oSize;

	m_nHidx = 0;
	for (NODE *p, **pp = old; pp < end; ++pp, ++m_nHidx)
	{
		if ((p = *pp))
		{
			data = p->data;
			*pp = p->next;	p->next = m_pFree;
			m_pFree = p;	--m_eSize;

			return data;
		}
	}

	return data;
}

void *CTcsHL::RemoveNext(void)
{
	if (0 > m_nHidx)	return 0;

	NODE *p, **pp;
	void *data = 0;

	while (m_nHidx < m_oSize)
	{
		pp = &m_pHead[m_nHidx];
		if ((p = *pp))
		{
			data = p->data;
			*pp = p->next;	p->next = m_pFree;
			m_pFree = p;	--m_eSize;

			return data;
		}
		else
			m_nHidx++;
	}

	return data;
}

void CTcsHL::Free(void)
{
	NODE **old = m_pHead;
	NODE **end = old + (1 << m_nSize);

	for (NODE *p, *n, **pp = old; pp < end; ++pp)
	{
		p = *pp;
		while (p)
		{
			n = p->next;	p->next = m_pFree;
			m_pFree = p;	p = n;
		}
		*pp = 0;
	}
	memset(m_pHead, 0 , (1 << m_nSize) * sizeof(NODE*));

	m_eSize = 0;
}