 |
OpenNI 1.5.4
|
XnHashT.h
Go to the documentation of this file.
00001 #ifndef _XN_HASH_T_H_ 00002 #define _XN_HASH_T_H_ 00003 00004 //--------------------------------------------------------------------------- 00005 // Includes 00006 //--------------------------------------------------------------------------- 00007 #include <XnOS.h> 00008 #include <XnListT.h> 00009 00010 //--------------------------------------------------------------------------- 00011 // Defines 00012 //--------------------------------------------------------------------------- 00013 typedef XnUInt8 XnHashCode; 00014 00015 //--------------------------------------------------------------------------- 00016 // Code 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 // this does not point to an actual entry. run to next one. 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 // increment internal bin iterator 00097 if (m_currIt != m_ppBins[m_nCurrBin]->End()) 00098 { 00099 ++m_currIt; 00100 } 00101 00102 // check if we need to move to next bin 00103 if (m_currIt == m_ppBins[m_nCurrBin]->End()) 00104 { 00105 // go forward through bins, until we either reach the end or a non-empty bin 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 // decrement internal bin iterator 00136 if (m_currIt != m_ppBins[m_nCurrBin]->ReverseEnd()) 00137 { 00138 --m_currIt; 00139 } 00140 00141 // check if we need to move to previous bin 00142 if (m_currIt == m_ppBins[m_nCurrBin]->ReverseEnd()) 00143 { 00144 // go backwards through bins, until we either reach the end or a non-empty bin 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 // NOTE: we don't want to delete LAST_BIN (it points to the m_lastBin member) 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 // check if bin exists 00367 if (m_apBins[nHash] == NULL) 00368 { 00369 // create it 00370 XN_VALIDATE_NEW(m_apBins[nHash], TPairList); 00371 00372 if (nHash < m_nMinBin) 00373 { 00374 m_nMinBin = nHash; 00375 } 00376 } 00377 00378 // now check if key is already in the bin 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 // replace it 00384 it->Value() = value; 00385 return (XN_STATUS_OK); 00386 } 00387 } 00388 00389 // if we got here, key is not in bin. Add it. 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 // Verify iterator is valid 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 // look for value in bin 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 // if we got here, key wasn't found 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_
Generated on Wed May 16 2012 10:16:05 for OpenNI 1.5.4 by
1.7.5.1