XnHashT.h
Go to the documentation of this file.
#ifndef _XN_HASH_T_H_
#define _XN_HASH_T_H_
//---------------------------------------------------------------------------
// Includes
//---------------------------------------------------------------------------
#include <XnOS.h>
#include <XnListT.h>
//---------------------------------------------------------------------------
// Defines
//---------------------------------------------------------------------------
typedef XnUInt8 XnHashCode;
//---------------------------------------------------------------------------
// Code
//---------------------------------------------------------------------------
template<class _TKey, class _TValue>
struct XnKeyValuePair
{
typedef _TKey TKey;
typedef _TValue TValue;
XnKeyValuePair() : key(TKey()), value(TValue()) {}
XnKeyValuePair(TKey key, TValue value) : key(key), value(value) {}
XnKeyValuePair(const XnKeyValuePair& other) : key(other.key), value(other.value) {}
public:
TKey const& Key() const { return key; }
TValue const& Value() const { return value; }
TValue& Value() { return value; }
private:
TKey key;
TValue value;
};
template<class TKey>
class XnDefaultKeyManagerT
{
public:
static XnHashCode Hash(TKey const& key)
{
return (((XnSizeT)key) & 0xff);
}
static XnInt32 Compare(TKey const& key1, TKey const& key2)
{
return XnInt32(XnSizeT(key1)-XnSizeT(key2));
}
};
template<class TKey,
class TValue,
class TKeyManager = XnDefaultKeyManagerT<TKey>,
class TAlloc = XnLinkedNodeDefaultAllocatorT<XnKeyValuePair<TKey, TValue> > >
class XnHashT
{
public:
typedef XnKeyValuePair<TKey, TValue> TPair;
typedef XnListT<TPair, TAlloc> TPairList;
enum
{
LAST_BIN = (1 << (sizeof(XnHashCode)*8)),
NUM_BINS = LAST_BIN + 1,
};
class ConstIterator
{
public:
ConstIterator() : m_ppBins(NULL), m_nCurrBin(0)
{}
ConstIterator(TPairList* const* apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
: m_ppBins(apBins), m_nCurrBin(nCurrBin), m_currIt(currIt)
{
if (nCurrBin != LAST_BIN && m_currIt == m_ppBins[m_nCurrBin]->End())
{
// this does not point to an actual entry. run to next one.
++*this;
}
}
ConstIterator(const ConstIterator& other)
: m_ppBins(other.m_ppBins), m_nCurrBin(other.m_nCurrBin), m_currIt(other.m_currIt)
{}
ConstIterator& operator++()
{
XN_ASSERT(m_nCurrBin != LAST_BIN);
// increment internal bin iterator
if (m_currIt != m_ppBins[m_nCurrBin]->End())
{
++m_currIt;
}
// check if we need to move to next bin
if (m_currIt == m_ppBins[m_nCurrBin]->End())
{
// go forward through bins, until we either reach the end or a non-empty bin
do
{
++m_nCurrBin;
} while (m_nCurrBin < LAST_BIN &&
(m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty()));
m_currIt = m_ppBins[m_nCurrBin]->Begin();
}
return *this;
}
ConstIterator operator++(int)
{
ConstIterator retVal(*this);
++*this;
return retVal;
}
ConstIterator& operator--()
{
XN_ASSERT(m_nCurrBin != LAST_BIN);
// decrement internal bin iterator
if (m_currIt != m_ppBins[m_nCurrBin]->ReverseEnd())
{
--m_currIt;
}
// check if we need to move to previous bin
if (m_currIt == m_ppBins[m_nCurrBin]->ReverseEnd())
{
// go backwards through bins, until we either reach the end or a non-empty bin
do
{
if (m_nCurrBin == 0)
{
m_nCurrBin = LAST_BIN;
break;
}
else
{
--m_nCurrBin;
}
} while (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty());
m_currIt = m_ppBins[m_nCurrBin]->Begin();
}
return *this;
}
ConstIterator operator--(int)
{
ConstIterator retVal(*this);
--*this;
return retVal;
}
inline XnBool operator==(const ConstIterator& other) const
{
return m_currIt == other.m_currIt;
}
inline XnBool operator!=(const ConstIterator& other) const
{
return m_currIt != other.m_currIt;
}
inline TPair const& operator*() const
{
return *m_currIt;
}
inline TPair const* operator->() const
{
return m_currIt.operator->();
}
protected:
friend class XnHashT;
TPairList* const* m_ppBins;
XnUInt32 m_nCurrBin;
typename TPairList::ConstIterator m_currIt;
};
class Iterator : public ConstIterator
{
public:
Iterator() : ConstIterator()
{}
Iterator(TPairList** apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
: ConstIterator(apBins, nCurrBin, currIt)
{}
Iterator(const Iterator& other) : ConstIterator(other)
{}
Iterator& operator++()
{
++(*(ConstIterator*)this);
return (*this);
}
inline Iterator operator++(int)
{
Iterator retVal(*this);
++*this;
return (retVal);
}
inline Iterator& operator--()
{
--(*(ConstIterator*)this);
return (*this);
}
inline Iterator operator--(int)
{
Iterator retVal(*this);
--*this;
return (retVal);
}
inline TPair& operator*() const
{
return const_cast<TPair&>(*this->m_currIt);
}
inline TPair* operator->() const
{
return const_cast<TPair*>(this->m_currIt.operator->());
}
};
XnHashT()
{
Init();
}
XnHashT(const XnHashT& other)
{
Init();
*this = other;
}
XnHashT& operator=(const XnHashT& other)
{
Clear();
XnStatus nRetVal = XN_STATUS_OK;
for (ConstIterator it = other.Begin(); it != other.End(); ++it)
{
nRetVal = Set(it->Key(), it->Value());
XN_ASSERT(nRetVal == XN_STATUS_OK);
}
return *this;
}
~XnHashT()
{
// NOTE: we don't want to delete LAST_BIN (it points to the m_lastBin member)
for (XnUInt32 i = 0; i < LAST_BIN; ++i)
{
if (m_apBins[i] != NULL)
{
XN_DELETE(m_apBins[i]);
}
}
}
Iterator Begin()
{
return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
}
ConstIterator Begin() const
{
return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
}
Iterator End()
{
return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
}
ConstIterator End() const
{
return ConstIterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
}
XnStatus Set(const TKey& key, const TValue& value)
{
XnHashCode nHash = TKeyManager::Hash(key);
// check if bin exists
if (m_apBins[nHash] == NULL)
{
// create it
XN_VALIDATE_NEW(m_apBins[nHash], TPairList);
if (nHash < m_nMinBin)
{
m_nMinBin = nHash;
}
}
// now check if key is already in the bin
for (typename TPairList::Iterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
{
if (TKeyManager::Compare(it->Key(), key) == 0)
{
// replace it
it->Value() = value;
return (XN_STATUS_OK);
}
}
// if we got here, key is not in bin. Add it.
return m_apBins[nHash]->AddLast(TPair(key, value));
}
ConstIterator Find(TKey const& key) const
{
XnUInt32 nBin = LAST_BIN;
typename TPairList::ConstIterator it;
if (TRUE == Find(key, nBin, it))
{
return ConstIterator(m_apBins, nBin, it);
}
else
{
return End();
}
}
Iterator Find(TKey const& key)
{
XnUInt32 nBin = LAST_BIN;
typename TPairList::Iterator it;
if (TRUE == Find(key, nBin, it))
{
return Iterator(m_apBins, nBin, it);
}
else
{
return End();
}
}
XnStatus Find(TKey const& key, ConstIterator& it) const
{
it = Find(key);
return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
}
XnStatus Find(TKey const& key, Iterator& it)
{
it = Find(key);
return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
}
XnStatus Get(TKey const& key, TValue& value) const
{
ConstIterator it = Find(key);
if (it == End())
{
return XN_STATUS_NO_MATCH;
}
else
{
value = it->Value();
return XN_STATUS_OK;
}
}
XnStatus Get(TKey const& key, TValue const*& pValue) const
{
ConstIterator it = Find(key);
if (it == End())
{
return XN_STATUS_NO_MATCH;
}
else
{
pValue = &it->Value();
return XN_STATUS_OK;
}
}
XnStatus Get(TKey const& key, TValue& value)
{
Iterator it = Find(key);
if (it == End())
{
return XN_STATUS_NO_MATCH;
}
else
{
value = it->Value();
return XN_STATUS_OK;
}
}
XnStatus Get(TKey const& key, TValue*& pValue)
{
Iterator it = Find(key);
if (it == End())
{
return XN_STATUS_NO_MATCH;
}
else
{
pValue = &it->Value();
return XN_STATUS_OK;
}
}
TValue& operator[](TKey const& key)
{
XnStatus nRetVal = XN_STATUS_OK;
Iterator it = Find(key);
if (it == End())
{
nRetVal = Set(key, TValue());
XN_ASSERT(nRetVal == XN_STATUS_OK);
it = Find(key);
XN_ASSERT(it != End());
}
return it->Value();
}
XnStatus Remove(ConstIterator it)
{
// Verify iterator is valid
if (it == End())
{
XN_ASSERT(FALSE);
return XN_STATUS_ILLEGAL_POSITION;
}
XN_ASSERT(m_apBins == it.m_ppBins);
XN_ASSERT(m_apBins[it.m_nCurrBin] != NULL);
return m_apBins[it.m_nCurrBin]->Remove(it.m_currIt);
}
XnStatus Remove(TKey const& key)
{
ConstIterator it = Find(key);
if (it != End())
{
return Remove(it);
}
else
{
return XN_STATUS_NO_MATCH;
}
}
XnStatus Clear()
{
while (Begin() != End())
Remove(Begin());
return XN_STATUS_OK;
}
XnBool IsEmpty() const
{
return (Begin() == End());
}
XnUInt32 Size() const
{
XnUInt32 nSize = 0;
for (ConstIterator iter = Begin(); iter != End(); ++iter, ++nSize)
;
return nSize;
}
private:
XnBool Find(TKey const& key, XnUInt32& nBin, typename TPairList::ConstIterator& currIt) const
{
XnHashCode nHash = TKeyManager::Hash(key);
if (m_apBins[nHash] != NULL)
{
// look for value in bin
for (typename TPairList::ConstIterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
{
if (TKeyManager::Compare(it->Key(), key) == 0)
{
nBin = nHash;
currIt = it;
return TRUE;
}
}
}
// if we got here, key wasn't found
return FALSE;
}
void Init()
{
xnOSMemSet(m_apBins, 0, sizeof(m_apBins));
m_apBins[LAST_BIN] = &m_lastBin;
m_nMinBin = LAST_BIN;
}
TPairList* m_apBins[NUM_BINS];
TPairList m_lastBin;
XnUInt32 m_nMinBin;
};
#endif // _XN_HASH_T_H_
XnHashCode
XnUInt8 XnHashCode
Definition XnHashT.h:13
XnListT.h
XnOS.h
XN_DELETE
#define XN_DELETE(p)
Definition XnOS.h:336
XN_VALIDATE_NEW
#define XN_VALIDATE_NEW(ptr, type,...)
Definition XnOS.h:168
xnOSMemSet
XN_C_API void XN_C_DECL xnOSMemSet(void *pDest, XnUInt8 nValue, XnSizeT nCount)
TRUE
#define TRUE
Definition XnPlatform.h:96
FALSE
#define FALSE
Definition XnPlatform.h:100
XnStatus
XnUInt32 XnStatus
Definition XnStatus.h:34
XN_STATUS_OK
#define XN_STATUS_OK
Definition XnStatus.h:37
XnDefaultKeyManagerT
Definition XnHashT.h:40
XnDefaultKeyManagerT::Hash
static XnHashCode Hash(TKey const &key)
Definition XnHashT.h:42
XnDefaultKeyManagerT::Compare
static XnInt32 Compare(TKey const &key1, TKey const &key2)
Definition XnHashT.h:47
XnHashT::ConstIterator::operator->
TPair const * operator->() const
Definition XnHashT.h:205
XnHashT::ConstIterator::operator++
ConstIterator operator++(int)
Definition XnHashT.h:121
XnHashT::ConstIterator::operator*
TPair const & operator*() const
Definition XnHashT.h:197
XnHashT::ConstIterator::ConstIterator
ConstIterator(const ConstIterator &other)
Definition XnHashT.h:85
XnHashT::ConstIterator::m_nCurrBin
XnUInt32 m_nCurrBin
Definition XnHashT.h:214
XnHashT::ConstIterator::operator++
ConstIterator & operator++()
Definition XnHashT.h:92
XnHashT::ConstIterator::m_currIt
TPairList::ConstIterator m_currIt
Definition XnHashT.h:215
XnHashT::ConstIterator::operator--
ConstIterator operator--(int)
Definition XnHashT.h:167
XnHashT::ConstIterator::ConstIterator
ConstIterator(TPairList *const *apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
Definition XnHashT.h:75
XnHashT::ConstIterator::ConstIterator
ConstIterator()
Definition XnHashT.h:72
XnHashT::ConstIterator::operator==
XnBool operator==(const ConstIterator &other) const
Definition XnHashT.h:179
XnHashT::ConstIterator::XnHashT
friend class XnHashT
Definition XnHashT.h:211
XnHashT::ConstIterator::operator--
ConstIterator & operator--()
Definition XnHashT.h:131
XnHashT::ConstIterator::m_ppBins
TPairList *const * m_ppBins
Definition XnHashT.h:213
XnHashT::ConstIterator::operator!=
XnBool operator!=(const ConstIterator &other) const
Definition XnHashT.h:189
XnHashT::Iterator::operator++
Iterator operator++(int)
Definition XnHashT.h:243
XnHashT::Iterator::operator->
TPair * operator->() const
Definition XnHashT.h:280
XnHashT::Iterator::operator++
Iterator & operator++()
Definition XnHashT.h:234
XnHashT::Iterator::Iterator
Iterator()
Definition XnHashT.h:221
XnHashT::Iterator::operator*
TPair & operator*() const
Definition XnHashT.h:272
XnHashT::Iterator::Iterator
Iterator(TPairList **apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
Definition XnHashT.h:224
XnHashT::Iterator::operator--
Iterator operator--(int)
Definition XnHashT.h:262
XnHashT::Iterator::operator--
Iterator & operator--()
Definition XnHashT.h:253
XnHashT::Iterator::Iterator
Iterator(const Iterator &other)
Definition XnHashT.h:228
XnHashT::TPairList
XnListT< TPair, TAlloc > TPairList
Definition XnHashT.h:61
XnHashT::~XnHashT
~XnHashT()
Definition XnHashT.h:312
XnHashT::Remove
XnStatus Remove(TKey const &key)
Definition XnHashT.h:587
XnHashT::Find
XnStatus Find(TKey const &key, ConstIterator &it) const
Definition XnHashT.h:443
XnHashT::End
ConstIterator End() const
Definition XnHashT.h:351
XnHashT::Get
XnStatus Get(TKey const &key, TValue const *&pValue) const
Definition XnHashT.h:493
XnHashT::Get
XnStatus Get(TKey const &key, TValue &value) const
Definition XnHashT.h:471
XnHashT::operator=
XnHashT & operator=(const XnHashT &other)
Definition XnHashT.h:297
XnHashT::Set
XnStatus Set(const TKey &key, const TValue &value)
Definition XnHashT.h:362
XnHashT::XnHashT
XnHashT(const XnHashT &other)
Definition XnHashT.h:291
XnHashT::Find
ConstIterator Find(TKey const &key) const
Definition XnHashT.h:400
XnHashT::operator[]
TValue & operator[](TKey const &key)
Definition XnHashT.h:556
XnHashT::Get
XnStatus Get(TKey const &key, TValue &value)
Definition XnHashT.h:515
XnHashT::XnHashT
XnHashT()
Definition XnHashT.h:286
XnHashT::Remove
XnStatus Remove(ConstIterator it)
Definition XnHashT.h:572
XnHashT< const XnChar *, TValue, XnStringsHashKeyManager, XnStringsNodeAllocator< TValue > >::LAST_BIN
@ LAST_BIN
Definition XnHashT.h:65
XnHashT< const XnChar *, TValue, XnStringsHashKeyManager, XnStringsNodeAllocator< TValue > >::NUM_BINS
@ NUM_BINS
Definition XnHashT.h:66
XnHashT::Find
Iterator Find(TKey const &key)
Definition XnHashT.h:421
XnHashT::End
Iterator End()
Definition XnHashT.h:343
XnHashT::Find
XnStatus Find(TKey const &key, Iterator &it)
Definition XnHashT.h:457
XnHashT::TPair
XnKeyValuePair< TKey, TValue > TPair
Definition XnHashT.h:60
XnHashT::Size
XnUInt32 Size() const
Definition XnHashT.h:622
XnHashT::Clear
XnStatus Clear()
Definition XnHashT.h:603
XnHashT::Get
XnStatus Get(TKey const &key, TValue *&pValue)
Definition XnHashT.h:537
XnHashT::Begin
ConstIterator Begin() const
Definition XnHashT.h:335
XnHashT::Begin
Iterator Begin()
Definition XnHashT.h:327
XnHashT::IsEmpty
XnBool IsEmpty() const
Definition XnHashT.h:614
XnLinkedNodeDefaultAllocatorT
Definition XnListT.h:41
XnListT::ConstIterator
Definition XnListT.h:75
XnListT::Iterator
Definition XnListT.h:168
XnListT
Definition XnListT.h:65
XnListT::End
Iterator End()
Definition XnListT.h:281
XnKeyValuePair
Definition XnHashT.h:20
XnKeyValuePair::TValue
_TValue TValue
Definition XnHashT.h:22
XnKeyValuePair::Value
TValue & Value()
Definition XnHashT.h:31
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair()
Definition XnHashT.h:24
XnKeyValuePair::Value
TValue const & Value() const
Definition XnHashT.h:30
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair(TKey key, TValue value)
Definition XnHashT.h:25
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair(const XnKeyValuePair &other)
Definition XnHashT.h:26
XnKeyValuePair::Key
TKey const & Key() const
Definition XnHashT.h:29
XnKeyValuePair::TKey
_TKey TKey
Definition XnHashT.h:21