OpenNI 1.5.4
XnHashT.h
Go to the documentation of this file.
1 #ifndef _XN_HASH_T_H_
2 #define _XN_HASH_T_H_
3 
4 //---------------------------------------------------------------------------
5 // Includes
6 //---------------------------------------------------------------------------
7 #include <XnOS.h>
8 #include <XnListT.h>
9 
10 //---------------------------------------------------------------------------
11 // Defines
12 //---------------------------------------------------------------------------
13 typedef XnUInt8 XnHashCode;
14 
15 //---------------------------------------------------------------------------
16 // Code
17 //---------------------------------------------------------------------------
18 template<class _TKey, class _TValue>
20 {
21  typedef _TKey TKey;
22  typedef _TValue TValue;
23 
24  XnKeyValuePair() : key(TKey()), value(TValue()) {}
25  XnKeyValuePair(TKey key, TValue value) : key(key), value(value) {}
26  XnKeyValuePair(const XnKeyValuePair& other) : key(other.key), value(other.value) {}
27 
28 public:
29  TKey const& Key() const { return key; }
30  TValue const& Value() const { return value; }
31  TValue& Value() { return value; }
32 
33 private:
34  TKey key;
35  TValue value;
36 };
37 
38 template<class TKey>
40 {
41 public:
42  static XnHashCode Hash(TKey const& key)
43  {
44  return (((XnSizeT)key) & 0xff);
45  }
46 
47  static XnInt32 Compare(TKey const& key1, TKey const& key2)
48  {
49  return XnInt32(XnSizeT(key1)-XnSizeT(key2));
50  }
51 };
52 
53 template<class TKey,
54  class TValue,
55  class TKeyManager = XnDefaultKeyManagerT<TKey>,
57 class XnHashT
58 {
59 public:
62 
63  enum
64  {
65  LAST_BIN = (1 << (sizeof(XnHashCode)*8)),
67  };
68 
70  {
71  public:
73  {}
74 
75  ConstIterator(TPairList* const* apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
76  : m_ppBins(apBins), m_nCurrBin(nCurrBin), m_currIt(currIt)
77  {
78  if (nCurrBin != LAST_BIN && m_currIt == m_ppBins[m_nCurrBin]->End())
79  {
80  // this does not point to an actual entry. run to next one.
81  ++*this;
82  }
83  }
84 
86  : m_ppBins(other.m_ppBins), m_nCurrBin(other.m_nCurrBin), m_currIt(other.m_currIt)
87  {}
88 
93  {
94  XN_ASSERT(m_nCurrBin != LAST_BIN);
95 
96  // increment internal bin iterator
97  if (m_currIt != m_ppBins[m_nCurrBin]->End())
98  {
99  ++m_currIt;
100  }
101 
102  // check if we need to move to next bin
103  if (m_currIt == m_ppBins[m_nCurrBin]->End())
104  {
105  // go forward through bins, until we either reach the end or a non-empty bin
106  do
107  {
108  ++m_nCurrBin;
109  } while (m_nCurrBin < LAST_BIN &&
110  (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty()));
111 
113  }
114 
115  return *this;
116  }
117 
122  {
123  ConstIterator retVal(*this);
124  ++*this;
125  return retVal;
126  }
127 
132  {
133  XN_ASSERT(m_nCurrBin != LAST_BIN);
134 
135  // decrement internal bin iterator
136  if (m_currIt != m_ppBins[m_nCurrBin]->ReverseEnd())
137  {
138  --m_currIt;
139  }
140 
141  // check if we need to move to previous bin
142  if (m_currIt == m_ppBins[m_nCurrBin]->ReverseEnd())
143  {
144  // go backwards through bins, until we either reach the end or a non-empty bin
145  do
146  {
147  if (m_nCurrBin == 0)
148  {
150  break;
151  }
152  else
153  {
154  --m_nCurrBin;
155  }
156  } while (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty());
157 
159  }
160 
161  return *this;
162  }
163 
168  {
169  ConstIterator retVal(*this);
170  --*this;
171  return retVal;
172  }
173 
179  inline XnBool operator==(const ConstIterator& other) const
180  {
181  return m_currIt == other.m_currIt;
182  }
183 
189  inline XnBool operator!=(const ConstIterator& other) const
190  {
191  return m_currIt != other.m_currIt;
192  }
193 
197  inline TPair const& operator*() const
198  {
199  return *m_currIt;
200  }
201 
205  inline TPair const* operator->() const
206  {
207  return m_currIt.operator->();
208  }
209 
210  protected:
211  friend class XnHashT;
212 
214  XnUInt32 m_nCurrBin;
215  typename TPairList::ConstIterator m_currIt;
216  };
217 
218  class Iterator : public ConstIterator
219  {
220  public:
222  {}
223 
224  Iterator(TPairList** apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
225  : ConstIterator(apBins, nCurrBin, currIt)
226  {}
227 
228  Iterator(const Iterator& other) : ConstIterator(other)
229  {}
230 
235  {
236  ++(*(ConstIterator*)this);
237  return (*this);
238  }
239 
243  inline Iterator operator++(int)
244  {
245  Iterator retVal(*this);
246  ++*this;
247  return (retVal);
248  }
249 
253  inline Iterator& operator--()
254  {
255  --(*(ConstIterator*)this);
256  return (*this);
257  }
258 
262  inline Iterator operator--(int)
263  {
264  Iterator retVal(*this);
265  --*this;
266  return (retVal);
267  }
268 
272  inline TPair& operator*() const
273  {
274  return const_cast<TPair&>(*this->m_currIt);
275  }
276 
280  inline TPair* operator->() const
281  {
282  return const_cast<TPair*>(this->m_currIt.operator->());
283  }
284  };
285 
287  {
288  Init();
289  }
290 
291  XnHashT(const XnHashT& other)
292  {
293  Init();
294  *this = other;
295  }
296 
297  XnHashT& operator=(const XnHashT& other)
298  {
299  Clear();
300 
301  XnStatus nRetVal = XN_STATUS_OK;
302 
303  for (ConstIterator it = other.Begin(); it != other.End(); ++it)
304  {
305  nRetVal = Set(it->Key(), it->Value());
306  XN_ASSERT(nRetVal == XN_STATUS_OK);
307  }
308 
309  return *this;
310  }
311 
313  {
314  // NOTE: we don't want to delete LAST_BIN (it points to the m_lastBin member)
315  for (XnUInt32 i = 0; i < LAST_BIN; ++i)
316  {
317  if (m_apBins[i] != NULL)
318  {
319  XN_DELETE(m_apBins[i]);
320  }
321  }
322  }
323 
327  Iterator Begin()
328  {
329  return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
330  }
331 
335  ConstIterator Begin() const
336  {
337  return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
338  }
339 
343  Iterator End()
344  {
345  return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
346  }
347 
351  ConstIterator End() const
352  {
353  return ConstIterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
354  }
355 
362  XnStatus Set(const TKey& key, const TValue& value)
363  {
364  XnHashCode nHash = TKeyManager::Hash(key);
365 
366  // check if bin exists
367  if (m_apBins[nHash] == NULL)
368  {
369  // create it
370  XN_VALIDATE_NEW(m_apBins[nHash], TPairList);
371 
372  if (nHash < m_nMinBin)
373  {
374  m_nMinBin = nHash;
375  }
376  }
377 
378  // now check if key is already in the bin
379  for (typename TPairList::Iterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
380  {
381  if (TKeyManager::Compare(it->Key(), key) == 0)
382  {
383  // replace it
384  it->Value() = value;
385  return (XN_STATUS_OK);
386  }
387  }
388 
389  // if we got here, key is not in bin. Add it.
390  return m_apBins[nHash]->AddLast(TPair(key, value));
391  }
392 
400  ConstIterator Find(TKey const& key) const
401  {
402  XnUInt32 nBin = LAST_BIN;
403  typename TPairList::ConstIterator it;
404  if (TRUE == Find(key, nBin, it))
405  {
406  return ConstIterator(m_apBins, nBin, it);
407  }
408  else
409  {
410  return End();
411  }
412  }
413 
421  Iterator Find(TKey const& key)
422  {
423  XnUInt32 nBin = LAST_BIN;
424  typename TPairList::Iterator it;
425  if (TRUE == Find(key, nBin, it))
426  {
427  return Iterator(m_apBins, nBin, it);
428  }
429  else
430  {
431  return End();
432  }
433  }
434 
443  XnStatus Find(TKey const& key, ConstIterator& it) const
444  {
445  it = Find(key);
446  return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
447  }
448 
457  XnStatus Find(TKey const& key, Iterator& it)
458  {
459  it = Find(key);
460  return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
461  }
462 
471  XnStatus Get(TKey const& key, TValue& value) const
472  {
473  ConstIterator it = Find(key);
474  if (it == End())
475  {
476  return XN_STATUS_NO_MATCH;
477  }
478  else
479  {
480  value = it->Value();
481  return XN_STATUS_OK;
482  }
483  }
484 
493  XnStatus Get(TKey const& key, TValue const*& pValue) const
494  {
495  ConstIterator it = Find(key);
496  if (it == End())
497  {
498  return XN_STATUS_NO_MATCH;
499  }
500  else
501  {
502  pValue = &it->Value();
503  return XN_STATUS_OK;
504  }
505  }
506 
515  XnStatus Get(TKey const& key, TValue& value)
516  {
517  Iterator it = Find(key);
518  if (it == End())
519  {
520  return XN_STATUS_NO_MATCH;
521  }
522  else
523  {
524  value = it->Value();
525  return XN_STATUS_OK;
526  }
527  }
528 
537  XnStatus Get(TKey const& key, TValue*& pValue)
538  {
539  Iterator it = Find(key);
540  if (it == End())
541  {
542  return XN_STATUS_NO_MATCH;
543  }
544  else
545  {
546  pValue = &it->Value();
547  return XN_STATUS_OK;
548  }
549  }
550 
556  TValue& operator[](TKey const& key)
557  {
558  XnStatus nRetVal = XN_STATUS_OK;
559  Iterator it = Find(key);
560  if (it == End())
561  {
562  nRetVal = Set(key, TValue());
563  XN_ASSERT(nRetVal == XN_STATUS_OK);
564 
565  it = Find(key);
566  XN_ASSERT(it != End());
567  }
568 
569  return it->Value();
570  }
571 
572  XnStatus Remove(ConstIterator it)
573  {
574  // Verify iterator is valid
575  if (it == End())
576  {
577  XN_ASSERT(FALSE);
578  return XN_STATUS_ILLEGAL_POSITION;
579  }
580 
581  XN_ASSERT(m_apBins == it.m_ppBins);
582  XN_ASSERT(m_apBins[it.m_nCurrBin] != NULL);
583 
584  return m_apBins[it.m_nCurrBin]->Remove(it.m_currIt);
585  }
586 
587  XnStatus Remove(TKey const& key)
588  {
589  ConstIterator it = Find(key);
590  if (it != End())
591  {
592  return Remove(it);
593  }
594  else
595  {
596  return XN_STATUS_NO_MATCH;
597  }
598  }
599 
604  {
605  while (Begin() != End())
606  Remove(Begin());
607 
608  return XN_STATUS_OK;
609  }
610 
614  XnBool IsEmpty() const
615  {
616  return (Begin() == End());
617  }
618 
622  XnUInt32 Size() const
623  {
624  XnUInt32 nSize = 0;
625  for (ConstIterator iter = Begin(); iter != End(); ++iter, ++nSize)
626  ;
627 
628  return nSize;
629  }
630 
631 private:
632  XnBool Find(TKey const& key, XnUInt32& nBin, typename TPairList::ConstIterator& currIt) const
633  {
634  XnHashCode nHash = TKeyManager::Hash(key);
635 
636  if (m_apBins[nHash] != NULL)
637  {
638  // look for value in bin
639  for (typename TPairList::ConstIterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
640  {
641  if (TKeyManager::Compare(it->Key(), key) == 0)
642  {
643  nBin = nHash;
644  currIt = it;
645  return TRUE;
646  }
647  }
648  }
649 
650  // if we got here, key wasn't found
651  return FALSE;
652  }
653 
654  void Init()
655  {
656  xnOSMemSet(m_apBins, 0, sizeof(m_apBins));
657  m_apBins[LAST_BIN] = &m_lastBin;
658  m_nMinBin = LAST_BIN;
659  }
660 
661  TPairList* m_apBins[NUM_BINS];
662  TPairList m_lastBin;
663  XnUInt32 m_nMinBin;
664 };
665 
666 
667 
668 #endif // _XN_HASH_T_H_
XnHashT
Definition: XnHashT.h:57
XnHashT::Clear
XnStatus Clear()
Definition: XnHashT.h:603
XnHashT::ConstIterator::operator*
TPair const & operator*() const
Definition: XnHashT.h:197
XnHashT::Find
XnStatus Find(TKey const &key, ConstIterator &it) const
Definition: XnHashT.h:443
XnHashT::Iterator::operator++
Iterator & operator++()
Definition: XnHashT.h:234
XnHashT::Iterator::operator--
Iterator & operator--()
Definition: XnHashT.h:253
XnDefaultKeyManagerT::Compare
static XnInt32 Compare(TKey const &key1, TKey const &key2)
Definition: XnHashT.h:47
XnHashT::Iterator::Iterator
Iterator(const Iterator &other)
Definition: XnHashT.h:228
XnOS.h
XnHashT::End
ConstIterator End() const
Definition: XnHashT.h:351
XnHashT::Iterator
Definition: XnHashT.h:218
XnHashT::Iterator::operator*
TPair & operator*() const
Definition: XnHashT.h:272
XnListT::End
Iterator End()
Definition: XnListT.h:281
XnListT< TPair, TAlloc >
XN_STATUS_OK
#define XN_STATUS_OK
Definition: XnStatus.h:36
XnHashT::ConstIterator::ConstIterator
ConstIterator()
Definition: XnHashT.h:72
XnHashT::Get
XnStatus Get(TKey const &key, TValue const *&pValue) const
Definition: XnHashT.h:493
XnListT::Remove
XnStatus Remove(ConstIterator where)
Definition: XnListT.h:426
XnHashT::Iterator::operator->
TPair * operator->() const
Definition: XnHashT.h:280
XnHashT::Find
ConstIterator Find(TKey const &key) const
Definition: XnHashT.h:400
FALSE
#define FALSE
Definition: XnPlatform.h:93
XnHashT::Remove
XnStatus Remove(TKey const &key)
Definition: XnHashT.h:587
XnKeyValuePair::Value
TValue & Value()
Definition: XnHashT.h:31
TRUE
#define TRUE
Definition: XnPlatform.h:89
XnHashT::ConstIterator::operator--
ConstIterator & operator--()
Definition: XnHashT.h:131
XN_VALIDATE_NEW
#define XN_VALIDATE_NEW(ptr, type,...)
Definition: XnOS.h:167
XnStatus
XnUInt32 XnStatus
Definition: XnStatus.h:33
XnHashT::ConstIterator::m_nCurrBin
XnUInt32 m_nCurrBin
Definition: XnHashT.h:214
XnHashT::Iterator::Iterator
Iterator()
Definition: XnHashT.h:221
XnKeyValuePair::Value
TValue const & Value() const
Definition: XnHashT.h:30
XnHashT::Find
Iterator Find(TKey const &key)
Definition: XnHashT.h:421
XnKeyValuePair
Definition: XnHashT.h:19
XnHashT::ConstIterator
Definition: XnHashT.h:69
XnHashT::XnHashT
XnHashT(const XnHashT &other)
Definition: XnHashT.h:291
XnHashT::ConstIterator::operator==
XnBool operator==(const ConstIterator &other) const
Definition: XnHashT.h:179
XnHashT::TPairList
XnListT< TPair, TAlloc > TPairList
Definition: XnHashT.h:61
XnKeyValuePair::TValue
_TValue TValue
Definition: XnHashT.h:22
XnHashT::ConstIterator::operator++
ConstIterator operator++(int)
Definition: XnHashT.h:121
XnDefaultKeyManagerT::Hash
static XnHashCode Hash(TKey const &key)
Definition: XnHashT.h:42
XnDefaultKeyManagerT
Definition: XnHashT.h:39
XnHashT::Set
XnStatus Set(const TKey &key, const TValue &value)
Definition: XnHashT.h:362
XnLinkedNodeDefaultAllocatorT
Definition: XnListT.h:40
XnHashT::ConstIterator::m_currIt
TPairList::ConstIterator m_currIt
Definition: XnHashT.h:215
XnHashT::Begin
ConstIterator Begin() const
Definition: XnHashT.h:335
XnKeyValuePair::TKey
_TKey TKey
Definition: XnHashT.h:21
XnHashT::ConstIterator::operator++
ConstIterator & operator++()
Definition: XnHashT.h:92
XnHashT::Iterator::operator--
Iterator operator--(int)
Definition: XnHashT.h:262
XnHashT::Get
XnStatus Get(TKey const &key, TValue &value) const
Definition: XnHashT.h:471
XnHashT::Size
XnUInt32 Size() const
Definition: XnHashT.h:622
XnHashT::XnHashT
XnHashT()
Definition: XnHashT.h:286
XnHashT::operator=
XnHashT & operator=(const XnHashT &other)
Definition: XnHashT.h:297
XnHashT::End
Iterator End()
Definition: XnHashT.h:343
XnHashT::Iterator::Iterator
Iterator(TPairList **apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
Definition: XnHashT.h:224
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair()
Definition: XnHashT.h:24
XnHashT::~XnHashT
~XnHashT()
Definition: XnHashT.h:312
XnHashT::Find
XnStatus Find(TKey const &key, Iterator &it)
Definition: XnHashT.h:457
XnHashT::Iterator::operator++
Iterator operator++(int)
Definition: XnHashT.h:243
XnHashT::ConstIterator::operator!=
XnBool operator!=(const ConstIterator &other) const
Definition: XnHashT.h:189
XnHashT::ConstIterator::ConstIterator
ConstIterator(const ConstIterator &other)
Definition: XnHashT.h:85
XnListT::AddLast
XnStatus AddLast(T const &value)
Definition: XnListT.h:383
XnHashT::ConstIterator::m_ppBins
TPairList *const * m_ppBins
Definition: XnHashT.h:213
XnHashT::TPair
XnKeyValuePair< TKey, TValue > TPair
Definition: XnHashT.h:60
XnHashT::NUM_BINS
Definition: XnHashT.h:66
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair(const XnKeyValuePair &other)
Definition: XnHashT.h:26
XnHashT::LAST_BIN
Definition: XnHashT.h:65
XnHashT::Remove
XnStatus Remove(ConstIterator it)
Definition: XnHashT.h:572
XnHashT::ConstIterator::operator--
ConstIterator operator--(int)
Definition: XnHashT.h:167
XnHashT::IsEmpty
XnBool IsEmpty() const
Definition: XnHashT.h:614
XnListT.h
XnHashCode
XnUInt8 XnHashCode
Definition: XnHashT.h:13
XnHashT::ConstIterator::ConstIterator
ConstIterator(TPairList *const *apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
Definition: XnHashT.h:75
XN_DELETE
#define XN_DELETE(p)
Definition: XnOS.h:335
XnKeyValuePair::XnKeyValuePair
XnKeyValuePair(TKey key, TValue value)
Definition: XnHashT.h:25
XnHashT::Get
XnStatus Get(TKey const &key, TValue &value)
Definition: XnHashT.h:515
XnHashT::Begin
Iterator Begin()
Definition: XnHashT.h:327
xnOSMemSet
XN_C_API void XN_C_DECL xnOSMemSet(void *pDest, XnUInt8 nValue, XnSizeT nCount)
XnHashT::operator[]
TValue & operator[](TKey const &key)
Definition: XnHashT.h:556
XnHashT::Get
XnStatus Get(TKey const &key, TValue *&pValue)
Definition: XnHashT.h:537
XnKeyValuePair::Key
TKey const & Key() const
Definition: XnHashT.h:29
XnHashT::ConstIterator::operator->
TPair const * operator->() const
Definition: XnHashT.h:205
XnListT::Begin
Iterator Begin()
Definition: XnListT.h:265