OpenNI 1.5.7
XnHashT.h
Go to the documentation of this file.
1 /*****************************************************************************
2 * *
3 * OpenNI 1.x Alpha *
4 * Copyright (C) 2012 PrimeSense Ltd. *
5 * *
6 * This file is part of OpenNI. *
7 * *
8 * Licensed under the Apache License, Version 2.0 (the "License"); *
9 * you may not use this file except in compliance with the License. *
10 * You may obtain a copy of the License at *
11 * *
12 * http://www.apache.org/licenses/LICENSE-2.0 *
13 * *
14 * Unless required by applicable law or agreed to in writing, software *
15 * distributed under the License is distributed on an "AS IS" BASIS, *
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
17 * See the License for the specific language governing permissions and *
18 * limitations under the License. *
19 * *
20 *****************************************************************************/
21 #ifndef _XN_HASH_T_H_
22 #define _XN_HASH_T_H_
23 
24 //---------------------------------------------------------------------------
25 // Includes
26 //---------------------------------------------------------------------------
27 #include <XnOS.h>
28 #include <XnListT.h>
29 
30 //---------------------------------------------------------------------------
31 // Defines
32 //---------------------------------------------------------------------------
33 typedef XnUInt8 XnHashCode;
34 
35 //---------------------------------------------------------------------------
36 // Code
37 //---------------------------------------------------------------------------
38 template<class _TKey, class _TValue>
40 {
41  typedef _TKey TKey;
42  typedef _TValue TValue;
43 
44  XnKeyValuePair() : key(TKey()), value(TValue()) {}
45  XnKeyValuePair(TKey key, TValue value) : key(key), value(value) {}
46  XnKeyValuePair(const XnKeyValuePair& other) : key(other.key), value(other.value) {}
47 
48 public:
49  TKey const& Key() const { return key; }
50  TValue const& Value() const { return value; }
51  TValue& Value() { return value; }
52 
53 private:
54  TKey key;
55  TValue value;
56 };
57 
58 template<class TKey>
60 {
61 public:
62  static XnHashCode Hash(TKey const& key)
63  {
64  return (((XnSizeT)key) & 0xff);
65  }
66 
67  static XnInt32 Compare(TKey const& key1, TKey const& key2)
68  {
69  return XnInt32(XnSizeT(key1)-XnSizeT(key2));
70  }
71 };
72 
73 template<class TKey,
74  class TValue,
75  class TKeyManager = XnDefaultKeyManagerT<TKey>,
77 class XnHashT
78 {
79 public:
82 
83  enum
84  {
85  LAST_BIN = (1 << (sizeof(XnHashCode)*8)),
87  };
88 
90  {
91  public:
93  {}
94 
95  ConstIterator(TPairList* const* apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
96  : m_ppBins(apBins), m_nCurrBin(nCurrBin), m_currIt(currIt)
97  {
98  if (nCurrBin != LAST_BIN && m_currIt == m_ppBins[m_nCurrBin]->End())
99  {
100  // this does not point to an actual entry. run to next one.
101  ++*this;
102  }
103  }
104 
106  : m_ppBins(other.m_ppBins), m_nCurrBin(other.m_nCurrBin), m_currIt(other.m_currIt)
107  {}
108 
113  {
114  XN_ASSERT(m_nCurrBin != LAST_BIN);
115 
116  // increment internal bin iterator
117  if (m_currIt != m_ppBins[m_nCurrBin]->End())
118  {
119  ++m_currIt;
120  }
121 
122  // check if we need to move to next bin
123  if (m_currIt == m_ppBins[m_nCurrBin]->End())
124  {
125  // go forward through bins, until we either reach the end or a non-empty bin
126  do
127  {
128  ++m_nCurrBin;
129  } while (m_nCurrBin < LAST_BIN &&
130  (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty()));
131 
133  }
134 
135  return *this;
136  }
137 
142  {
143  ConstIterator retVal(*this);
144  ++*this;
145  return retVal;
146  }
147 
152  {
153  XN_ASSERT(m_nCurrBin != LAST_BIN);
154 
155  // decrement internal bin iterator
156  if (m_currIt != m_ppBins[m_nCurrBin]->ReverseEnd())
157  {
158  --m_currIt;
159  }
160 
161  // check if we need to move to previous bin
162  if (m_currIt == m_ppBins[m_nCurrBin]->ReverseEnd())
163  {
164  // go backwards through bins, until we either reach the end or a non-empty bin
165  do
166  {
167  if (m_nCurrBin == 0)
168  {
170  break;
171  }
172  else
173  {
174  --m_nCurrBin;
175  }
176  } while (m_ppBins[m_nCurrBin] == NULL || m_ppBins[m_nCurrBin]->IsEmpty());
177 
179  }
180 
181  return *this;
182  }
183 
188  {
189  ConstIterator retVal(*this);
190  --*this;
191  return retVal;
192  }
193 
199  inline XnBool operator==(const ConstIterator& other) const
200  {
201  return m_currIt == other.m_currIt;
202  }
203 
209  inline XnBool operator!=(const ConstIterator& other) const
210  {
211  return m_currIt != other.m_currIt;
212  }
213 
217  inline TPair const& operator*() const
218  {
219  return *m_currIt;
220  }
221 
225  inline TPair const* operator->() const
226  {
227  return m_currIt.operator->();
228  }
229 
230  protected:
231  friend class XnHashT;
232 
234  XnUInt32 m_nCurrBin;
236  };
237 
238  class Iterator : public ConstIterator
239  {
240  public:
242  {}
243 
244  Iterator(TPairList** apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
245  : ConstIterator(apBins, nCurrBin, currIt)
246  {}
247 
248  Iterator(const Iterator& other) : ConstIterator(other)
249  {}
250 
255  {
256  ++(*(ConstIterator*)this);
257  return (*this);
258  }
259 
263  inline Iterator operator++(int)
264  {
265  Iterator retVal(*this);
266  ++*this;
267  return (retVal);
268  }
269 
273  inline Iterator& operator--()
274  {
275  --(*(ConstIterator*)this);
276  return (*this);
277  }
278 
282  inline Iterator operator--(int)
283  {
284  Iterator retVal(*this);
285  --*this;
286  return (retVal);
287  }
288 
292  inline TPair& operator*() const
293  {
294  return const_cast<TPair&>(*this->m_currIt);
295  }
296 
300  inline TPair* operator->() const
301  {
302  return const_cast<TPair*>(this->m_currIt.operator->());
303  }
304  };
305 
307  {
308  Init();
309  }
310 
311  XnHashT(const XnHashT& other)
312  {
313  Init();
314  *this = other;
315  }
316 
317  XnHashT& operator=(const XnHashT& other)
318  {
319  Clear();
320 
321  XnStatus nRetVal = XN_STATUS_OK;
322 
323  for (ConstIterator it = other.Begin(); it != other.End(); ++it)
324  {
325  nRetVal = Set(it->Key(), it->Value());
326  XN_ASSERT(nRetVal == XN_STATUS_OK);
327  }
328 
329  return *this;
330  }
331 
333  {
334  // NOTE: we don't want to delete LAST_BIN (it points to the m_lastBin member)
335  for (XnUInt32 i = 0; i < LAST_BIN; ++i)
336  {
337  if (m_apBins[i] != NULL)
338  {
339  XN_DELETE(m_apBins[i]);
340  }
341  }
342  }
343 
348  {
349  return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
350  }
351 
356  {
357  return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
358  }
359 
364  {
365  return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
366  }
367 
372  {
373  return ConstIterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
374  }
375 
382  XnStatus Set(const TKey& key, const TValue& value)
383  {
384  XnHashCode nHash = TKeyManager::Hash(key);
385 
386  // check if bin exists
387  if (m_apBins[nHash] == NULL)
388  {
389  // create it
390  XN_VALIDATE_NEW(m_apBins[nHash], TPairList);
391 
392  if (nHash < m_nMinBin)
393  {
394  m_nMinBin = nHash;
395  }
396  }
397 
398  // now check if key is already in the bin
399  for (typename TPairList::Iterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
400  {
401  if (TKeyManager::Compare(it->Key(), key) == 0)
402  {
403  // replace it
404  it->Value() = value;
405  return (XN_STATUS_OK);
406  }
407  }
408 
409  // if we got here, key is not in bin. Add it.
410  return m_apBins[nHash]->AddLast(TPair(key, value));
411  }
412 
420  ConstIterator Find(TKey const& key) const
421  {
422  XnUInt32 nBin = LAST_BIN;
423  typename TPairList::ConstIterator it;
424  if (TRUE == Find(key, nBin, it))
425  {
426  return ConstIterator(m_apBins, nBin, it);
427  }
428  else
429  {
430  return End();
431  }
432  }
433 
441  Iterator Find(TKey const& key)
442  {
443  XnUInt32 nBin = LAST_BIN;
444  typename TPairList::Iterator it;
445  if (TRUE == Find(key, nBin, it))
446  {
447  return Iterator(m_apBins, nBin, it);
448  }
449  else
450  {
451  return End();
452  }
453  }
454 
463  XnStatus Find(TKey const& key, ConstIterator& it) const
464  {
465  it = Find(key);
466  return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
467  }
468 
477  XnStatus Find(TKey const& key, Iterator& it)
478  {
479  it = Find(key);
480  return (it == End() ? XN_STATUS_NO_MATCH : XN_STATUS_OK);
481  }
482 
491  XnStatus Get(TKey const& key, TValue& value) const
492  {
493  ConstIterator it = Find(key);
494  if (it == End())
495  {
496  return XN_STATUS_NO_MATCH;
497  }
498  else
499  {
500  value = it->Value();
501  return XN_STATUS_OK;
502  }
503  }
504 
513  XnStatus Get(TKey const& key, TValue const*& pValue) const
514  {
515  ConstIterator it = Find(key);
516  if (it == End())
517  {
518  return XN_STATUS_NO_MATCH;
519  }
520  else
521  {
522  pValue = &it->Value();
523  return XN_STATUS_OK;
524  }
525  }
526 
535  XnStatus Get(TKey const& key, TValue& value)
536  {
537  Iterator it = Find(key);
538  if (it == End())
539  {
540  return XN_STATUS_NO_MATCH;
541  }
542  else
543  {
544  value = it->Value();
545  return XN_STATUS_OK;
546  }
547  }
548 
557  XnStatus Get(TKey const& key, TValue*& pValue)
558  {
559  Iterator it = Find(key);
560  if (it == End())
561  {
562  return XN_STATUS_NO_MATCH;
563  }
564  else
565  {
566  pValue = &it->Value();
567  return XN_STATUS_OK;
568  }
569  }
570 
576  TValue& operator[](TKey const& key)
577  {
578  XnStatus nRetVal = XN_STATUS_OK;
579  Iterator it = Find(key);
580  if (it == End())
581  {
582  nRetVal = Set(key, TValue());
583  XN_ASSERT(nRetVal == XN_STATUS_OK);
584 
585  it = Find(key);
586  XN_ASSERT(it != End());
587  }
588 
589  return it->Value();
590  }
591 
593  {
594  // Verify iterator is valid
595  if (it == End())
596  {
597  XN_ASSERT(FALSE);
598  return XN_STATUS_ILLEGAL_POSITION;
599  }
600 
601  XN_ASSERT(m_apBins == it.m_ppBins);
602  XN_ASSERT(m_apBins[it.m_nCurrBin] != NULL);
603 
604  return m_apBins[it.m_nCurrBin]->Remove(it.m_currIt);
605  }
606 
607  XnStatus Remove(TKey const& key)
608  {
609  ConstIterator it = Find(key);
610  if (it != End())
611  {
612  return Remove(it);
613  }
614  else
615  {
616  return XN_STATUS_NO_MATCH;
617  }
618  }
619 
624  {
625  while (Begin() != End())
626  Remove(Begin());
627 
628  return XN_STATUS_OK;
629  }
630 
634  XnBool IsEmpty() const
635  {
636  return (Begin() == End());
637  }
638 
642  XnUInt32 Size() const
643  {
644  XnUInt32 nSize = 0;
645  for (ConstIterator iter = Begin(); iter != End(); ++iter, ++nSize)
646  ;
647 
648  return nSize;
649  }
650 
651 private:
652  XnBool Find(TKey const& key, XnUInt32& nBin, typename TPairList::ConstIterator& currIt) const
653  {
654  XnHashCode nHash = TKeyManager::Hash(key);
655 
656  if (m_apBins[nHash] != NULL)
657  {
658  // look for value in bin
659  for (typename TPairList::ConstIterator it = m_apBins[nHash]->Begin(); it != m_apBins[nHash]->End(); ++it)
660  {
661  if (TKeyManager::Compare(it->Key(), key) == 0)
662  {
663  nBin = nHash;
664  currIt = it;
665  return TRUE;
666  }
667  }
668  }
669 
670  // if we got here, key wasn't found
671  return FALSE;
672  }
673 
674  void Init()
675  {
676  xnOSMemSet(m_apBins, 0, sizeof(m_apBins));
677  m_apBins[LAST_BIN] = &m_lastBin;
678  m_nMinBin = LAST_BIN;
679  }
680 
681  TPairList* m_apBins[NUM_BINS];
682  TPairList m_lastBin;
683  XnUInt32 m_nMinBin;
684 };
685 
686 
687 
688 #endif // _XN_HASH_T_H_
XnUInt8 XnHashCode
Definition: XnHashT.h:33
#define XN_DELETE(p)
Definition: XnOS.h:339
#define XN_VALIDATE_NEW(ptr, type,...)
Definition: XnOS.h:171
XN_C_API void XN_C_DECL xnOSMemSet(void *pDest, XnUInt8 nValue, XnSizeT nCount)
#define TRUE
Definition: XnPlatform.h:85
#define FALSE
Definition: XnPlatform.h:89
XnUInt32 XnStatus
Definition: XnStatus.h:33
#define XN_STATUS_OK
Definition: XnStatus.h:36
Definition: XnHashT.h:60
static XnHashCode Hash(TKey const &key)
Definition: XnHashT.h:62
static XnInt32 Compare(TKey const &key1, TKey const &key2)
Definition: XnHashT.h:67
Definition: XnHashT.h:90
TPair const & operator*() const
Definition: XnHashT.h:217
ConstIterator operator++(int)
Definition: XnHashT.h:141
ConstIterator(const ConstIterator &other)
Definition: XnHashT.h:105
XnUInt32 m_nCurrBin
Definition: XnHashT.h:234
TPairList::ConstIterator m_currIt
Definition: XnHashT.h:235
ConstIterator operator--(int)
Definition: XnHashT.h:187
ConstIterator(TPairList *const *apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
Definition: XnHashT.h:95
ConstIterator()
Definition: XnHashT.h:92
XnBool operator==(const ConstIterator &other) const
Definition: XnHashT.h:199
ConstIterator & operator--()
Definition: XnHashT.h:151
TPairList *const * m_ppBins
Definition: XnHashT.h:233
ConstIterator & operator++()
Definition: XnHashT.h:112
TPair const * operator->() const
Definition: XnHashT.h:225
XnBool operator!=(const ConstIterator &other) const
Definition: XnHashT.h:209
Definition: XnHashT.h:239
Iterator operator++(int)
Definition: XnHashT.h:263
TPair & operator*() const
Definition: XnHashT.h:292
Iterator()
Definition: XnHashT.h:241
TPair * operator->() const
Definition: XnHashT.h:300
Iterator(TPairList **apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
Definition: XnHashT.h:244
Iterator operator--(int)
Definition: XnHashT.h:282
Iterator & operator--()
Definition: XnHashT.h:273
Iterator & operator++()
Definition: XnHashT.h:254
Iterator(const Iterator &other)
Definition: XnHashT.h:248
Definition: XnHashT.h:78
XnListT< TPair, TAlloc > TPairList
Definition: XnHashT.h:81
@ LAST_BIN
Definition: XnHashT.h:85
@ NUM_BINS
Definition: XnHashT.h:86
~XnHashT()
Definition: XnHashT.h:332
XnStatus Remove(TKey const &key)
Definition: XnHashT.h:607
XnStatus Find(TKey const &key, ConstIterator &it) const
Definition: XnHashT.h:463
XnHashT & operator=(const XnHashT &other)
Definition: XnHashT.h:317
ConstIterator End() const
Definition: XnHashT.h:371
XnStatus Get(TKey const &key, TValue const *&pValue) const
Definition: XnHashT.h:513
XnStatus Get(TKey const &key, TValue &value) const
Definition: XnHashT.h:491
XnStatus Set(const TKey &key, const TValue &value)
Definition: XnHashT.h:382
XnHashT(const XnHashT &other)
Definition: XnHashT.h:311
ConstIterator Find(TKey const &key) const
Definition: XnHashT.h:420
XnStatus Get(TKey const &key, TValue &value)
Definition: XnHashT.h:535
XnHashT()
Definition: XnHashT.h:306
XnStatus Remove(ConstIterator it)
Definition: XnHashT.h:592
TValue & operator[](TKey const &key)
Definition: XnHashT.h:576
Iterator Find(TKey const &key)
Definition: XnHashT.h:441
Iterator End()
Definition: XnHashT.h:363
XnStatus Find(TKey const &key, Iterator &it)
Definition: XnHashT.h:477
XnKeyValuePair< TKey, TValue > TPair
Definition: XnHashT.h:80
XnUInt32 Size() const
Definition: XnHashT.h:642
XnStatus Clear()
Definition: XnHashT.h:623
XnStatus Get(TKey const &key, TValue *&pValue)
Definition: XnHashT.h:557
ConstIterator Begin() const
Definition: XnHashT.h:355
Iterator Begin()
Definition: XnHashT.h:347
XnBool IsEmpty() const
Definition: XnHashT.h:634
Definition: XnListT.h:61
Definition: XnListT.h:95
Definition: XnListT.h:188
Definition: XnListT.h:85
XnStatus AddLast(T const &value)
Definition: XnListT.h:403
Iterator End()
Definition: XnListT.h:301
Iterator Begin()
Definition: XnListT.h:285
XnStatus Remove(ConstIterator where)
Definition: XnListT.h:446
Definition: XnHashT.h:40
TKey const & Key() const
Definition: XnHashT.h:49
_TValue TValue
Definition: XnHashT.h:42
XnKeyValuePair()
Definition: XnHashT.h:44
XnKeyValuePair(TKey key, TValue value)
Definition: XnHashT.h:45
TValue & Value()
Definition: XnHashT.h:51
XnKeyValuePair(const XnKeyValuePair &other)
Definition: XnHashT.h:46
_TKey TKey
Definition: XnHashT.h:41
TValue const & Value() const
Definition: XnHashT.h:50