00001 #ifndef _XN_HASH_T_H_
00002 #define _XN_HASH_T_H_
00003
00004
00005
00006
00007 #include <XnOS.h>
00008 #include <XnListT.h>
00009
00010
00011
00012
00013 typedef XnUInt8 XnHashCode;
00014
00015
00016
00017
00018 template<class _TKey, class _TValue>
00019 struct XnKeyValuePair
00020 {
00021 typedef _TKey TKey;
00022 typedef _TValue TValue;
00023
00024 XnKeyValuePair() : key(TKey()), value(TValue()) {}
00025 XnKeyValuePair(TKey key, TValue value) : key(key), value(value) {}
00026 XnKeyValuePair(const XnKeyValuePair& other) : key(other.key), value(other.value) {}
00027
00028 public:
00029 TKey const& Key() const { return key; }
00030 TValue const& Value() const { return value; }
00031 TValue& Value() { return value; }
00032
00033 private:
00034 TKey key;
00035 TValue value;
00036 };
00037
00038 template<class TKey>
00039 class XnDefaultKeyManagerT
00040 {
00041 public:
00042 static XnHashCode Hash(TKey const& key)
00043 {
00044 return (((XnSizeT)key) & 0xff);
00045 }
00046
00047 static XnInt32 Compare(TKey const& key1, TKey const& key2)
00048 {
00049 return XnInt32(XnSizeT(key1)-XnSizeT(key2));
00050 }
00051 };
00052
00053 template<class TKey,
00054 class TValue,
00055 class TKeyManager = XnDefaultKeyManagerT<TKey>,
00056 class TAlloc = XnLinkedNodeDefaultAllocatorT<XnKeyValuePair<TKey, TValue> > >
00057 class XnHashT
00058 {
00059 public:
00060 typedef XnKeyValuePair<TKey, TValue> TPair;
00061 typedef XnListT<TPair, TAlloc> TPairList;
00062
00063 enum
00064 {
00065 LAST_BIN = (1 << (sizeof(XnHashCode)*8)),
00066 NUM_BINS = LAST_BIN + 1,
00067 };
00068
00069 class ConstIterator
00070 {
00071 public:
00072 ConstIterator() : m_ppBins(NULL), m_nCurrBin(0)
00073 {}
00074
00075 ConstIterator(TPairList* const* apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
00076 : m_ppBins(apBins), m_nCurrBin(nCurrBin), m_currIt(currIt)
00077 {
00078 if (nCurrBin != LAST_BIN && m_currIt == m_ppBins[m_nCurrBin]->End())
00079 {
00080
00081 ++*this;
00082 }
00083 }
00084
00085 ConstIterator(const ConstIterator& other)
00086 : m_ppBins(other.m_ppBins), m_nCurrBin(other.m_nCurrBin), m_currIt(other.m_currIt)
00087 {}
00088
00092 ConstIterator& operator++()
00093 {
00094 XN_ASSERT(m_nCurrBin != LAST_BIN);
00095
00096
00097 if (m_currIt != m_ppBins[m_nCurrBin]->End())
00098 {
00099 ++m_currIt;
00100 }
00101
00102
00103 if (m_currIt == m_ppBins[m_nCurrBin]->End())
00104 {
00105
00106 do
00107 {
00108 ++m_nCurrBin;
00109 } while (m_nCurrBin < LAST_BIN &&
00110 (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty()));
00111
00112 m_currIt = m_ppBins[m_nCurrBin]->Begin();
00113 }
00114
00115 return *this;
00116 }
00117
00121 ConstIterator operator++(int)
00122 {
00123 ConstIterator retVal(*this);
00124 ++*this;
00125 return retVal;
00126 }
00127
00131 ConstIterator& operator--()
00132 {
00133 XN_ASSERT(m_nCurrBin != LAST_BIN);
00134
00135
00136 if (m_currIt != m_ppBins[m_nCurrBin]->ReverseEnd())
00137 {
00138 --m_currIt;
00139 }
00140
00141
00142 if (m_currIt == m_ppBins[m_nCurrBin]->ReverseEnd())
00143 {
00144
00145 do
00146 {
00147 if (m_nCurrBin == 0)
00148 {
00149 m_nCurrBin = LAST_BIN;
00150 break;
00151 }
00152 else
00153 {
00154 --m_nCurrBin;
00155 }
00156 } while (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty());
00157
00158 m_currIt = m_ppBins[m_nCurrBin]->Begin();
00159 }
00160
00161 return *this;
00162 }
00163
00167 ConstIterator operator--(int)
00168 {
00169 ConstIterator retVal(*this);
00170 --*this;
00171 return retVal;
00172 }
00173
00179 inline XnBool operator==(const ConstIterator& other) const
00180 {
00181 return m_currIt == other.m_currIt;
00182 }
00183
00189 inline XnBool operator!=(const ConstIterator& other) const
00190 {
00191 return m_currIt != other.m_currIt;
00192 }
00193
00197 inline TPair const& operator*() const
00198 {
00199 return *m_currIt;
00200 }
00201
00205 inline TPair const* operator->() const
00206 {
00207 return m_currIt.operator->();
00208 }
00209
00210 protected:
00211 friend class XnHashT;
00212
00213 TPairList* const* m_ppBins;
00214 XnUInt32 m_nCurrBin;
00215 typename TPairList::ConstIterator m_currIt;
00216 };
00217
00218 class Iterator : public ConstIterator
00219 {
00220 public:
00221 Iterator() : ConstIterator()
00222 {}
00223
00224 Iterator(TPairList** apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
00225 : ConstIterator(apBins, nCurrBin, currIt)
00226 {}
00227
00228 Iterator(const Iterator& other) : ConstIterator(other)
00229 {}
00230
00234 Iterator& operator++()
00235 {
00236 ++(*(ConstIterator*)this);
00237 return (*this);
00238 }
00239
00243 inline Iterator operator++(int)
00244 {
00245 Iterator retVal(*this);
00246 ++*this;
00247 return (retVal);
00248 }
00249
00253 inline Iterator& operator--()
00254 {
00255 --(*(ConstIterator*)this);
00256 return (*this);
00257 }
00258
00262 inline Iterator operator--(int)
00263 {
00264 Iterator retVal(*this);
00265 --*this;
00266 return (retVal);
00267 }
00268
00272 inline TPair& operator*() const
00273 {
00274 return const_cast<TPair&>(*this->m_currIt);
00275 }
00276
00280 inline TPair* operator->() const
00281 {
00282 return const_cast<TPair*>(this->m_currIt.operator->());
00283 }
00284 };
00285
00286 XnHashT()
00287 {
00288 Init();
00289 }
00290
00291 XnHashT(const XnHashT& other)
00292 {
00293 Init();
00294 *this = other;
00295 }
00296
00297 XnHashT& operator=(const XnHashT& other)
00298 {
00299 Clear();
00300
00301 XnStatus nRetVal = XN_STATUS_OK;
00302
00303 for (ConstIterator it = other.Begin(); it != other.End(); ++it)
00304 {
00305 nRetVal = Set(it->Key(), it->Value());
00306 XN_ASSERT(nRetVal == XN_STATUS_OK);
00307 }
00308
00309 return *this;
00310 }
00311
00312 ~XnHashT()
00313 {
00314
00315 for (XnUInt32 i = 0; i < LAST_BIN; ++i)
00316 {
00317 if (m_apBins[i] != NULL)
00318 {
00319 XN_DELETE(m_apBins[i]);
00320 }
00321 }
00322 }
00323
00327 Iterator Begin()
00328 {
00329 return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
00330 }
00331
00335 ConstIterator Begin() const
00336 {
00337 return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
00338 }
00339
00343 Iterator End()
00344 {
00345 return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
00346 }
00347
00351 ConstIterator End() const
00352 {
00353 return ConstIterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
00354 }
00355
00362 XnStatus Set(const TKey& key, const TValue& value)
00363 {
00364 XnHashCode nHash = TKeyManager::Hash(key);
00365
00366
00367 if (m_apBins[nHash] == NULL)
00368 {
00369
00370 XN_VALIDATE_NEW(m_apBins[nHash], TPairList);
00371
00372 if (nHash < m_nMinBin)
00373 {
00374 m_nMinBin = nHash;
00375 }
00376 }
00377
00378
00379 for (typename TPairList::Iterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
00380 {
00381 if (TKeyManager::Compare(it->Key(), key) == 0)
00382 {
00383
00384 it->Value() = value;
00385 return (XN_STATUS_OK);
00386 }
00387 }
00388
00389
00390 return m_apBins[nHash]->AddLast(TPair(key, value));
00391 }
00392
00400 ConstIterator Find(TKey const& key) const
00401 {
00402 XnUInt32 nBin = LAST_BIN;
00403 typename TPairList::ConstIterator it;
00404 if (TRUE == Find(key, nBin, it))
00405 {
00406 return ConstIterator(m_apBins, nBin, it);
00407 }
00408 else
00409 {
00410 return End();
00411 }
00412 }
00413
00421 Iterator Find(TKey const& key)
00422 {
00423 XnUInt32 nBin = LAST_BIN;
00424 typename TPairList::Iterator it;
00425 if (TRUE == Find(key, nBin, it))
00426 {
00427 return Iterator(m_apBins, nBin, it);
00428 }
00429 else
00430 {
00431 return End();
00432 }
00433 }
00434
00443 XnStatus Find(TKey const& key, ConstIterator& it) const
00444 {
00445 it = Find(key);
00446 return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
00447 }
00448
00457 XnStatus Find(TKey const& key, Iterator& it)
00458 {
00459 it = Find(key);
00460 return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
00461 }
00462
00471 XnStatus Get(TKey const& key, TValue& value) const
00472 {
00473 ConstIterator it = Find(key);
00474 if (it == End())
00475 {
00476 return XN_STATUS_NO_MATCH;
00477 }
00478 else
00479 {
00480 value = it->Value();
00481 return XN_STATUS_OK;
00482 }
00483 }
00484
00493 XnStatus Get(TKey const& key, TValue const*& pValue) const
00494 {
00495 ConstIterator it = Find(key);
00496 if (it == End())
00497 {
00498 return XN_STATUS_NO_MATCH;
00499 }
00500 else
00501 {
00502 pValue = &it->Value();
00503 return XN_STATUS_OK;
00504 }
00505 }
00506
00515 XnStatus Get(TKey const& key, TValue& value)
00516 {
00517 Iterator it = Find(key);
00518 if (it == End())
00519 {
00520 return XN_STATUS_NO_MATCH;
00521 }
00522 else
00523 {
00524 value = it->Value();
00525 return XN_STATUS_OK;
00526 }
00527 }
00528
00537 XnStatus Get(TKey const& key, TValue*& pValue)
00538 {
00539 Iterator it = Find(key);
00540 if (it == End())
00541 {
00542 return XN_STATUS_NO_MATCH;
00543 }
00544 else
00545 {
00546 pValue = &it->Value();
00547 return XN_STATUS_OK;
00548 }
00549 }
00550
00556 TValue& operator[](TKey const& key)
00557 {
00558 XnStatus nRetVal = XN_STATUS_OK;
00559 Iterator it = Find(key);
00560 if (it == End())
00561 {
00562 nRetVal = Set(key, TValue());
00563 XN_ASSERT(nRetVal == XN_STATUS_OK);
00564
00565 it = Find(key);
00566 XN_ASSERT(it != End());
00567 }
00568
00569 return it->Value();
00570 }
00571
00572 XnStatus Remove(ConstIterator it)
00573 {
00574
00575 if (it == End())
00576 {
00577 XN_ASSERT(FALSE);
00578 return XN_STATUS_ILLEGAL_POSITION;
00579 }
00580
00581 XN_ASSERT(m_apBins == it.m_ppBins);
00582 XN_ASSERT(m_apBins[it.m_nCurrBin] != NULL);
00583
00584 return m_apBins[it.m_nCurrBin]->Remove(it.m_currIt);
00585 }
00586
00587 XnStatus Remove(TKey const& key)
00588 {
00589 ConstIterator it = Find(key);
00590 if (it != End())
00591 {
00592 return Remove(it);
00593 }
00594 else
00595 {
00596 return XN_STATUS_NO_MATCH;
00597 }
00598 }
00599
00603 XnStatus Clear()
00604 {
00605 while (Begin() != End())
00606 Remove(Begin());
00607
00608 return XN_STATUS_OK;
00609 }
00610
00614 XnBool IsEmpty() const
00615 {
00616 return (Begin() == End());
00617 }
00618
00622 XnUInt32 Size() const
00623 {
00624 XnUInt32 nSize = 0;
00625 for (ConstIterator iter = Begin(); iter != End(); ++iter, ++nSize)
00626 ;
00627
00628 return nSize;
00629 }
00630
00631 private:
00632 XnBool Find(TKey const& key, XnUInt32& nBin, typename TPairList::ConstIterator& currIt) const
00633 {
00634 XnHashCode nHash = TKeyManager::Hash(key);
00635
00636 if (m_apBins[nHash] != NULL)
00637 {
00638
00639 for (typename TPairList::ConstIterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
00640 {
00641 if (TKeyManager::Compare(it->Key(), key) == 0)
00642 {
00643 nBin = nHash;
00644 currIt = it;
00645 return TRUE;
00646 }
00647 }
00648 }
00649
00650
00651 return FALSE;
00652 }
00653
00654 void Init()
00655 {
00656 xnOSMemSet(m_apBins, 0, sizeof(m_apBins));
00657 m_apBins[LAST_BIN] = &m_lastBin;
00658 m_nMinBin = LAST_BIN;
00659 }
00660
00661 TPairList* m_apBins[NUM_BINS];
00662 TPairList m_lastBin;
00663 XnUInt32 m_nMinBin;
00664 };
00665
00666
00667
00668 #endif // _XN_HASH_T_H_