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//---------------------------------------------------------------------------
33typedef XnUInt8 XnHashCode;
34
35//---------------------------------------------------------------------------
36// Code
37//---------------------------------------------------------------------------
38template<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
48public:
49 TKey const& Key() const { return key; }
50 TValue const& Value() const { return value; }
51 TValue& Value() { return value; }
52
53private:
54 TKey key;
55 TValue value;
56};
57
58template<class TKey>
60{
61public:
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
73template<class TKey,
74 class TValue,
75 class TKeyManager = XnDefaultKeyManagerT<TKey>,
78{
79public:
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
132 m_currIt = m_ppBins[m_nCurrBin]->Begin();
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
178 m_currIt = m_ppBins[m_nCurrBin]->Begin();
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;
235 typename TPairList::ConstIterator m_currIt;
236 };
237
238 class Iterator : public ConstIterator
239 {
240 public:
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
274 {
275 --(*(ConstIterator*)this);
276 return (*this);
277 }
278
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
347 Iterator Begin()
348 {
349 return Iterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
350 }
351
355 ConstIterator Begin() const
356 {
357 return ConstIterator(m_apBins, m_nMinBin, m_apBins[m_nMinBin]->Begin());
358 }
359
363 Iterator End()
364 {
365 return Iterator(m_apBins, LAST_BIN, m_apBins[LAST_BIN]->Begin());
366 }
367
371 ConstIterator End() const
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
592 XnStatus Remove(ConstIterator it)
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
651private:
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
TPair const * operator->() const
Definition XnHashT.h:225
ConstIterator operator++(int)
Definition XnHashT.h:141
TPair const & operator*() const
Definition XnHashT.h:217
ConstIterator(const ConstIterator &other)
Definition XnHashT.h:105
XnUInt32 m_nCurrBin
Definition XnHashT.h:234
ConstIterator & operator++()
Definition XnHashT.h:112
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
friend class XnHashT
Definition XnHashT.h:231
ConstIterator & operator--()
Definition XnHashT.h:151
TPairList *const * m_ppBins
Definition XnHashT.h:233
XnBool operator!=(const ConstIterator &other) const
Definition XnHashT.h:209
Iterator operator++(int)
Definition XnHashT.h:263
TPair * operator->() const
Definition XnHashT.h:300
Iterator & operator++()
Definition XnHashT.h:254
Iterator()
Definition XnHashT.h:241
TPair & operator*() const
Definition XnHashT.h:292
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(const Iterator &other)
Definition XnHashT.h:248
XnListT< TPair, TAlloc > TPairList
Definition XnHashT.h:81
~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
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
XnHashT & operator=(const XnHashT &other)
Definition XnHashT.h:317
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
TValue & operator[](TKey const &key)
Definition XnHashT.h:576
XnStatus Get(TKey const &key, TValue &value)
Definition XnHashT.h:535
XnHashT()
Definition XnHashT.h:306
XnStatus Remove(ConstIterator it)
Definition XnHashT.h:592
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
Iterator End()
Definition XnListT.h:301
Definition XnHashT.h:40
_TValue TValue
Definition XnHashT.h:42
TValue & Value()
Definition XnHashT.h:51
XnKeyValuePair()
Definition XnHashT.h:44
TValue const & Value() const
Definition XnHashT.h:50
XnKeyValuePair(TKey key, TValue value)
Definition XnHashT.h:45
XnKeyValuePair(const XnKeyValuePair &other)
Definition XnHashT.h:46
TKey const & Key() const
Definition XnHashT.h:49
_TKey TKey
Definition XnHashT.h:41