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//---------------------------------------------------------------------------
13typedef XnUInt8 XnHashCode;
14
15//---------------------------------------------------------------------------
16// Code
17//---------------------------------------------------------------------------
18template<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
28public:
29 TKey const& Key() const { return key; }
30 TValue const& Value() const { return value; }
31 TValue& Value() { return value; }
32
33private:
34 TKey key;
35 TValue value;
36};
37
38template<class TKey>
40{
41public:
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
53template<class TKey,
54 class TValue,
55 class TKeyManager = XnDefaultKeyManagerT<TKey>,
58{
59public:
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
87 {}
88
93 {
94 XN_ASSERT(m_nCurrBin != LAST_BIN);
95
96 // increment internal bin iterator
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;
216 };
217
218 class Iterator : public ConstIterator
219 {
220 public:
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
254 {
255 --(*(ConstIterator*)this);
256 return (*this);
257 }
258
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
328 {
329 return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
330 }
331
336 {
337 return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
338 }
339
344 {
345 return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
346 }
347
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
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
631private:
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_
XnUInt8 XnHashCode
Definition XnHashT.h:13
#define XN_DELETE(p)
Definition XnOS.h:336
#define XN_VALIDATE_NEW(ptr, type,...)
Definition XnOS.h:168
XN_C_API void XN_C_DECL xnOSMemSet(void *pDest, XnUInt8 nValue, XnSizeT nCount)
#define TRUE
Definition XnPlatform.h:96
#define FALSE
Definition XnPlatform.h:100
XnUInt32 XnStatus
Definition XnStatus.h:34
#define XN_STATUS_OK
Definition XnStatus.h:37
Definition XnHashT.h:40
static XnHashCode Hash(TKey const &key)
Definition XnHashT.h:42
static XnInt32 Compare(TKey const &key1, TKey const &key2)
Definition XnHashT.h:47
Definition XnHashT.h:70
TPair const * operator->() const
Definition XnHashT.h:205
ConstIterator operator++(int)
Definition XnHashT.h:121
TPair const & operator*() const
Definition XnHashT.h:197
ConstIterator(const ConstIterator &other)
Definition XnHashT.h:85
XnUInt32 m_nCurrBin
Definition XnHashT.h:214
ConstIterator & operator++()
Definition XnHashT.h:92
TPairList::ConstIterator m_currIt
Definition XnHashT.h:215
ConstIterator operator--(int)
Definition XnHashT.h:167
ConstIterator(TPairList *const *apBins, XnUInt32 nCurrBin, typename TPairList::ConstIterator currIt)
Definition XnHashT.h:75
ConstIterator()
Definition XnHashT.h:72
XnBool operator==(const ConstIterator &other) const
Definition XnHashT.h:179
ConstIterator & operator--()
Definition XnHashT.h:131
TPairList *const * m_ppBins
Definition XnHashT.h:213
XnBool operator!=(const ConstIterator &other) const
Definition XnHashT.h:189
Definition XnHashT.h:219
Iterator operator++(int)
Definition XnHashT.h:243
TPair * operator->() const
Definition XnHashT.h:280
Iterator & operator++()
Definition XnHashT.h:234
Iterator()
Definition XnHashT.h:221
TPair & operator*() const
Definition XnHashT.h:272
Iterator(TPairList **apBins, XnUInt32 nCurrBin, typename TPairList::Iterator currIt)
Definition XnHashT.h:224
Iterator operator--(int)
Definition XnHashT.h:262
Iterator & operator--()
Definition XnHashT.h:253
Iterator(const Iterator &other)
Definition XnHashT.h:228
Definition XnHashT.h:58
XnListT< TPair, TAlloc > TPairList
Definition XnHashT.h:61
@ LAST_BIN
Definition XnHashT.h:65
@ NUM_BINS
Definition XnHashT.h:66
~XnHashT()
Definition XnHashT.h:312
XnStatus Remove(TKey const &key)
Definition XnHashT.h:587
XnStatus Find(TKey const &key, ConstIterator &it) const
Definition XnHashT.h:443
ConstIterator End() const
Definition XnHashT.h:351
XnStatus Get(TKey const &key, TValue const *&pValue) const
Definition XnHashT.h:493
XnStatus Get(TKey const &key, TValue &value) const
Definition XnHashT.h:471
XnHashT & operator=(const XnHashT &other)
Definition XnHashT.h:297
XnStatus Set(const TKey &key, const TValue &value)
Definition XnHashT.h:362
XnHashT(const XnHashT &other)
Definition XnHashT.h:291
ConstIterator Find(TKey const &key) const
Definition XnHashT.h:400
TValue & operator[](TKey const &key)
Definition XnHashT.h:556
XnStatus Get(TKey const &key, TValue &value)
Definition XnHashT.h:515
XnHashT()
Definition XnHashT.h:286
XnStatus Remove(ConstIterator it)
Definition XnHashT.h:572
Iterator Find(TKey const &key)
Definition XnHashT.h:421
Iterator End()
Definition XnHashT.h:343
XnStatus Find(TKey const &key, Iterator &it)
Definition XnHashT.h:457
XnKeyValuePair< TKey, TValue > TPair
Definition XnHashT.h:60
XnUInt32 Size() const
Definition XnHashT.h:622
XnStatus Clear()
Definition XnHashT.h:603
XnStatus Get(TKey const &key, TValue *&pValue)
Definition XnHashT.h:537
ConstIterator Begin() const
Definition XnHashT.h:335
Iterator Begin()
Definition XnHashT.h:327
XnBool IsEmpty() const
Definition XnHashT.h:614
Definition XnListT.h:41
Definition XnListT.h:75
Definition XnListT.h:168
Definition XnListT.h:65
XnStatus AddLast(T const &value)
Definition XnListT.h:383
Iterator End()
Definition XnListT.h:281
Iterator Begin()
Definition XnListT.h:265
XnStatus Remove(ConstIterator where)
Definition XnListT.h:426
Definition XnHashT.h:20
_TValue TValue
Definition XnHashT.h:22
TValue & Value()
Definition XnHashT.h:31
XnKeyValuePair()
Definition XnHashT.h:24
TValue const & Value() const
Definition XnHashT.h:30
XnKeyValuePair(TKey key, TValue value)
Definition XnHashT.h:25
XnKeyValuePair(const XnKeyValuePair &other)
Definition XnHashT.h:26
TKey const & Key() const
Definition XnHashT.h:29
_TKey TKey
Definition XnHashT.h:21