Version
menu_open
link
Wwise SDK 2021.1.14
AkHashList.h
Go to the documentation of this file.
1 /*******************************************************************************
2 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
3 released in source code form as part of the SDK installer package.
4 
5 Commercial License Usage
6 
7 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
8 may use this file in accordance with the end user license agreement provided
9 with the software or, alternatively, in accordance with the terms contained in a
10 written agreement between you and Audiokinetic Inc.
11 
12 Apache License Usage
13 
14 Alternatively, this file may be used under the Apache License, Version 2.0 (the
15 "Apache License"); you may not use this file except in compliance with the
16 Apache License. You may obtain a copy of the Apache License at
17 http://www.apache.org/licenses/LICENSE-2.0.
18 
19 Unless required by applicable law or agreed to in writing, software distributed
20 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
21 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
22 the specific language governing permissions and limitations under the License.
23 
24  Version: v2021.1.14 Build: 6590
25  Copyright (c) 2006-2023 Audiokinetic Inc.
26 *******************************************************************************/
27 
28 #ifndef _AKHASHLIST_H
29 #define _AKHASHLIST_H
30 
31 #include <AK/Tools/Common/AkKeyDef.h>// for MapStruct
32 #include <AK/Tools/Common/AkObject.h>
33 #include <AK/Tools/Common/AkArray.h>
34 
35 // NOTE: when using this template, a hashing function of the following form must be available:
36 //
37 // AkHashType AkHash( T_KEY );
38 
39 typedef AkUInt32 AkHashType;
40 
41 template < class T_KEY >
42 AkForceInline AkHashType AkHash(T_KEY in_key) { return (AkHashType)in_key; }
43 
44 #define AK_HASH_SIZE_VERY_SMALL 11
45 static const AkHashType kHashSizes[] = { 29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };
46 static const size_t kNumHashSizes = sizeof(kHashSizes) / sizeof(kHashSizes[0]);
47 static const AkReal32 kHashTableGrowthFactor = 0.9f;
48 
49 template < class T_KEY, class T_ITEM, typename T_ALLOC = ArrayPoolDefault >
50 class AkHashList: public T_ALLOC
51 {
52 public:
53 
54  struct Item
55  {
56  Item * pNextItem; // our next one
57  MapStruct<T_KEY, T_ITEM> Assoc; // key-item association
58  };
59 
60  typedef AkArray<Item*, Item*, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray;
61 
62  struct Iterator
63  {
64  typename AkHashList<T_KEY,T_ITEM,T_ALLOC>::HashTableArray* pTable;
65  AkHashType uiTable;
66  Item* pItem;
67 
68  inline Iterator& operator++()
69  {
70  AKASSERT( pItem );
71  pItem = pItem->pNextItem;
72 
73  while ( ( pItem == NULL ) && ( ++uiTable < pTable->Length() ) )
74  pItem = (*pTable)[ uiTable ];
75 
76  return *this;
77  }
78 
79  inline MapStruct<T_KEY, T_ITEM>& operator*()
80  {
81  AKASSERT( pItem );
82  return pItem->Assoc;
83  }
84 
85  inline MapStruct<T_KEY, T_ITEM>* operator->()
86  {
87  AKASSERT(pItem);
88  return &pItem->Assoc;
89  }
90 
91  bool operator ==(const Iterator& in_rOp) const
92  {
93  return pItem == in_rOp.pItem;
94  }
95 
96  bool operator !=( const Iterator& in_rOp ) const
97  {
98  return !operator==(in_rOp);
99  }
100  };
101 
102  struct ConstIterator
103  {
104  const typename AkHashList<T_KEY, T_ITEM, T_ALLOC>::HashTableArray* pTable;
105  AkHashType uiTable;
106  Item* pItem;
107 
108  inline ConstIterator& operator++()
109  {
110  AKASSERT(pItem);
111  pItem = pItem->pNextItem;
112 
113  while ((pItem == NULL) && (++uiTable < pTable->Length()))
114  pItem = (*pTable)[uiTable];
115 
116  return *this;
117  }
118 
119  inline const MapStruct<T_KEY, T_ITEM>& operator*()
120  {
121  AKASSERT(pItem);
122  return pItem->Assoc;
123  }
124 
125  inline MapStruct<T_KEY, T_ITEM>* operator->() const
126  {
127  AKASSERT(pItem);
128  return &pItem->Assoc;
129  }
130 
131  bool operator ==(const ConstIterator& in_rOp) const
132  {
133  return pItem == in_rOp.pItem;
134  }
135 
136  bool operator !=(const ConstIterator& in_rOp) const
137  {
138  return !operator==(in_rOp);
139  }
140  };
141 
142  // The IteratorEx iterator is intended for usage when a possible erase may occurs
143  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
144  struct IteratorEx : public Iterator
145  {
146  Item* pPrevItem;
147 
148  IteratorEx& operator++()
149  {
150  AKASSERT( this->pItem );
151 
152  pPrevItem = this->pItem;
153  this->pItem = this->pItem->pNextItem;
154 
155  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
156  {
157  pPrevItem = NULL;
158  this->pItem = (*this->pTable)[ this->uiTable ];
159  }
160 
161  return *this;
162  }
163  };
164 
165  struct ConstIteratorEx : public ConstIterator
166  {
167  Item* pPrevItem;
168 
169  ConstIteratorEx& operator++()
170  {
171  AKASSERT(this->pItem);
172 
173  pPrevItem = this->pItem;
174  this->pItem = this->pItem->pNextItem;
175 
176  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
177  {
178  pPrevItem = NULL;
179  this->pItem = (*this->pTable)[this->uiTable];
180  }
181 
182  return *this;
183  }
184  };
185 
186  Iterator Begin()
187  {
188  Iterator returnedIt;
189 
190  if (HashSize() > 0)
191  {
192  returnedIt.pTable = &m_table;
193  returnedIt.uiTable = 0;
194  returnedIt.pItem = m_table[0];
195 
196  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
197  returnedIt.pItem = m_table[returnedIt.uiTable];
198  }
199  else
200  {
201  returnedIt.pTable = NULL;
202  returnedIt.uiTable = 0;
203  returnedIt.pItem = NULL;
204  }
205 
206  return returnedIt;
207  }
208 
209  ConstIterator Begin() const
210  {
211  ConstIterator returnedIt;
212 
213  if (HashSize() > 0)
214  {
215  returnedIt.pTable = &m_table;
216  returnedIt.uiTable = 0;
217  returnedIt.pItem = m_table[0];
218 
219  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
220  returnedIt.pItem = m_table[returnedIt.uiTable];
221  }
222  else
223  {
224  returnedIt.pTable = NULL;
225  returnedIt.uiTable = 0;
226  returnedIt.pItem = NULL;
227  }
228 
229  return returnedIt;
230  }
231 
232  IteratorEx BeginEx()
233  {
234  IteratorEx returnedIt;
235 
236  if (HashSize() > 0)
237  {
238  returnedIt.pTable = &m_table;
239  returnedIt.uiTable = 0;
240  returnedIt.pItem = *(m_table.Begin());
241  returnedIt.pPrevItem = NULL;
242 
243  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
244  returnedIt.pItem = m_table[returnedIt.uiTable];
245  }
246  else
247  {
248  returnedIt.pTable = NULL;
249  returnedIt.uiTable = 0;
250  returnedIt.pItem = NULL;
251  }
252 
253  return returnedIt;
254  }
255 
256  ConstIteratorEx BeginEx() const
257  {
258  ConstIteratorEx returnedIt;
259 
260  if (HashSize() > 0)
261  {
262  returnedIt.pTable = &m_table;
263  returnedIt.uiTable = 0;
264  returnedIt.pItem = *(m_table.Begin());
265  returnedIt.pPrevItem = NULL;
266 
267  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
268  returnedIt.pItem = m_table[returnedIt.uiTable];
269  }
270  else
271  {
272  returnedIt.pTable = NULL;
273  returnedIt.uiTable = 0;
274  returnedIt.pItem = NULL;
275  }
276 
277  return returnedIt;
278  }
279 
280  inline Iterator End()
281  {
282  Iterator returnedIt;
283  returnedIt.pItem = NULL;
284  return returnedIt;
285  }
286 
287  inline ConstIterator End() const
288  {
289  ConstIterator returnedIt;
290  returnedIt.pItem = NULL;
291  return returnedIt;
292  }
293 
294  inline IteratorEx EndEx()
295  {
296  IteratorEx returnedIt;
297  returnedIt.pItem = NULL;
298  return returnedIt;
299  }
300 
301  inline ConstIterator EndEx() const
302  {
303  ConstIteratorEx returnedIt;
304  returnedIt.pItem = NULL;
305  return returnedIt;
306  }
307 
308  IteratorEx FindEx( T_KEY in_Key )
309  {
310  IteratorEx returnedIt;
311 
312  if (HashSize() > 0)
313  {
314  returnedIt.pTable = &m_table;
315  returnedIt.uiTable = AkHash(in_Key) % HashSize();
316  returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
317  returnedIt.pPrevItem = NULL;
318 
319  while (returnedIt.pItem != NULL)
320  {
321  if (returnedIt.pItem->Assoc.key == in_Key)
322  break;
323 
324  returnedIt.pPrevItem = returnedIt.pItem;
325  returnedIt.pItem = returnedIt.pItem->pNextItem;
326  }
327  }
328  else
329  {
330  returnedIt.pTable = NULL;
331  returnedIt.uiTable = 0;
332  returnedIt.pItem = NULL;
333  returnedIt.pPrevItem = NULL;
334  }
335 
336  return returnedIt;
337  }
338 
339  ConstIteratorEx FindEx(T_KEY in_Key) const
340  {
341  ConstIteratorEx returnedIt;
342 
343  if (HashSize() > 0)
344  {
345  returnedIt.pTable = &m_table;
346  returnedIt.uiTable = AkHash(in_Key) % HashSize();
347  returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
348  returnedIt.pPrevItem = NULL;
349 
350  while (returnedIt.pItem != NULL)
351  {
352  if (returnedIt.pItem->Assoc.key == in_Key)
353  break;
354 
355  returnedIt.pPrevItem = returnedIt.pItem;
356  returnedIt.pItem = returnedIt.pItem->pNextItem;
357  }
358  }
359  else
360  {
361  returnedIt.pTable = NULL;
362  returnedIt.uiTable = 0;
363  returnedIt.pItem = NULL;
364  returnedIt.pPrevItem = NULL;
365  }
366 
367  return returnedIt;
368  }
369 
370  AkHashList(): m_uiSize( 0 )
371  {
372  }
373 
374  ~AkHashList()
375  {
376  AKASSERT(m_uiSize == 0);
377  m_table.Term();
378  }
379 
380  void Term()
381  {
382  RemoveAll();
383  m_table.Term();
384  }
385 
386  void RemoveAll()
387  {
388  for (AkHashType i = 0; i < HashSize(); ++i)
389  {
390  Item * pItem = m_table[ i ];
391  while ( pItem != NULL )
392  {
393  Item * pNextItem = pItem->pNextItem;
394  pItem->Assoc.item.~T_ITEM();
395  T_ALLOC::Free( pItem );
396  pItem = pNextItem;
397  }
398 
399  m_table[ i ] = NULL;
400  }
401 
402  m_uiSize = 0;
403  }
404 
405  T_ITEM * Exists( T_KEY in_Key )
406  {
407  if (HashSize() > 0)
408  {
409  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
410  return ExistsInList(in_Key, uiTable);
411  }
412  return NULL;
413  }
414 
415  // Set using an externally preallocated Item -- Hash list takes ownership of the Item.
416  T_ITEM * Set( Item * in_pItem )
417  {
418  if (CheckSize())
419  {
420  AkHashType uiTable = AkHash(in_pItem->Assoc.key) % HashSize();
421 
422  AKASSERT(!ExistsInList(in_pItem->Assoc.key, uiTable)); // Item must not exist in list !
423 
424  // Add new entry
425 
426  in_pItem->pNextItem = m_table[uiTable];
427  m_table[uiTable] = in_pItem;
428 
429  ++m_uiSize;
430 
431  return &(in_pItem->Assoc.item);
432  }
433 
434  return NULL;
435  }
436 
437  T_ITEM * Set( T_KEY in_Key )
438  {
439  if ( CheckSize() )
440  {
441  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
442  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
443  if (pItem)
444  return pItem;
445 
446  return CreateEntry(in_Key, uiTable);
447  }
448 
449  return NULL;
450  }
451 
452  T_ITEM * Set( T_KEY in_Key, bool& out_bWasAlreadyThere )
453  {
454  if (CheckSize())
455  {
456  AkHashType uiTable = AkHash(in_Key) % HashSize();
457  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
458  if (pItem)
459  {
460  out_bWasAlreadyThere = true;
461  return pItem;
462  }
463  else
464  {
465  out_bWasAlreadyThere = false;
466  }
467 
468  return CreateEntry(in_Key, uiTable);
469  }
470 
471  return NULL;
472  }
473 
474  void Unset( T_KEY in_Key )
475  {
476  if (HashSize() > 0)
477  {
478  AkHashType uiTable = AkHash(in_Key) % HashSize();
479  Item * pItem = m_table[uiTable];
480  Item * pPrevItem = NULL;
481  while (pItem != NULL)
482  {
483  if (pItem->Assoc.key == in_Key)
484  break;
485 
486  pPrevItem = pItem;
487  pItem = pItem->pNextItem;
488  }
489 
490  if (pItem)
491  RemoveItem(uiTable, pItem, pPrevItem);
492  }
493  }
494 
495  IteratorEx Erase( const IteratorEx& in_rIter )
496  {
497  IteratorEx returnedIt;
498  returnedIt.pTable = in_rIter.pTable;
499  returnedIt.uiTable = in_rIter.uiTable;
500  returnedIt.pItem = in_rIter.pItem->pNextItem;
501  returnedIt.pPrevItem = in_rIter.pPrevItem;
502 
503  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
504  {
505  returnedIt.pPrevItem = NULL;
506  returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
507  }
508 
509  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
510 
511  return returnedIt;
512  }
513 
514  void RemoveItem( AkHashType in_uiTable, Item* in_pItem, Item* in_pPrevItem )
515  {
516  if( in_pPrevItem )
517  in_pPrevItem->pNextItem = in_pItem->pNextItem;
518  else
519  m_table[ in_uiTable ] = in_pItem->pNextItem;
520 
521  in_pItem->Assoc.item.~T_ITEM();
522  T_ALLOC::Free(in_pItem);
523 
524  --m_uiSize;
525  }
526 
527  AkUInt32 Length() const
528  {
529  return m_uiSize;
530  }
531 
532  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
533  {
534  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
535  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
536 
537  return AK_Success;
538  }
539 
540  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
541  {
542  AKRESULT res = AK_Fail;
543 
544  AkUInt32 uNewSize = 0;
545  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
546  {
547  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
548  {
549  uNewSize = kHashSizes[i];
550  break;
551  }
552  }
553 
554  if (uNewSize > 0)
555  {
556  HashTableArray oldArray;
557  oldArray.Transfer(m_table);
558 
559  if ( m_table.GrowArray(uNewSize) )
560  {
561  for (AkUInt32 i = 0; i < uNewSize; i++)
562  m_table.AddLast(NULL);
563 
564  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
565  {
566  Item * pItem = oldArray[i];
567  while (pItem != NULL)
568  {
569  Item * pNextItem = pItem->pNextItem;
570  {
571  AkHashType uiTable = AkHash(pItem->Assoc.key) % HashSize();
572  pItem->pNextItem = m_table[uiTable];
573  m_table[uiTable] = pItem;
574  }
575  pItem = pNextItem;
576  }
577  }
578 
579  oldArray.Term();
580 
581  res = AK_Success;
582  }
583  else
584  {
585  //Backpedal..
586  m_table.Transfer(oldArray);
587  }
588  }
589 
590  return res;
591  }
592 
593  inline AkUInt32 HashSize() const
594  {
595  return m_table.Length();
596  }
597 
598  inline bool CheckSize()
599  {
600  if ( HashSize() == 0 || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
601  Resize(HashSize());
602 
603  return (HashSize() > 0);
604  }
605 
606 protected:
607  T_ITEM * ExistsInList( T_KEY in_Key, AkUIntPtr in_uiTable )
608  {
609  AKASSERT(HashSize() > 0);
610 
611  Item * pItem = m_table[(AkUInt32)in_uiTable];
612  while (pItem != NULL)
613  {
614  if (pItem->Assoc.key == in_Key)
615  return &(pItem->Assoc.item); // found
616 
617  pItem = pItem->pNextItem;
618  }
619 
620  return NULL; // not found
621  }
622 
623  T_ITEM * CreateEntry( T_KEY in_Key, AkUIntPtr in_uiTable )
624  {
625  Item * pNewItem = (Item *)T_ALLOC::Alloc(sizeof(Item));
626  if ( pNewItem == NULL )
627  return NULL;
628 
629  pNewItem->pNextItem = m_table[ (AkUInt32)in_uiTable ];
630  pNewItem->Assoc.key = in_Key;
631 
632  AkPlacementNew( &(pNewItem->Assoc.item) ) T_ITEM;
633 
634  m_table[(AkUInt32)in_uiTable] = pNewItem;
635 
636  ++m_uiSize;
637 
638  return &(pNewItem->Assoc.item);
639  }
640 
641  HashTableArray m_table;
642  AkUInt32 m_uiSize;
643 };
644 
645 // this one lets you define the structure
646 // only requirement is that T_MAPSTRUCT must have members pNextItem and key.
647 // client is responsible for allocation/deallocation of T_MAPSTRUCTS.
648 template <class T_KEY, class T_MAPSTRUCT>
649 struct AkDefaultHashListBarePolicy
650 {
651  static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) {return in_pItem->key;}
652 };
653 
654 template < class T_KEY, class T_MAPSTRUCT, typename T_ALLOC = ArrayPoolDefault, class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT> >
655 class AkHashListBare
656 {
657  typedef AkArray<T_MAPSTRUCT*, T_MAPSTRUCT*, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray;
658 public:
659  struct Iterator
660  {
661  typename AkHashListBare<T_KEY,T_MAPSTRUCT,T_ALLOC,KEY_POLICY>::HashTableArray* pTable;
662  AkHashType uiTable;
663  T_MAPSTRUCT* pItem;
664 
665  inline Iterator& operator++()
666  {
667  AKASSERT( pItem );
668  pItem = pItem->pNextItem;
669 
670  while ((pItem == NULL) && (++uiTable < pTable->Length()))
671  pItem = (*pTable)[ uiTable ];
672 
673  return *this;
674  }
675 
676  inline T_MAPSTRUCT * operator*()
677  {
678  AKASSERT( pItem );
679  return pItem;
680  }
681 
682  bool operator !=( const Iterator& in_rOp ) const
683  {
684  return ( pItem != in_rOp.pItem );
685  }
686  };
687 
688  // The IteratorEx iterator is intended for usage when a possible erase may occurs
689  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
690  struct IteratorEx : public Iterator
691  {
692  T_MAPSTRUCT* pPrevItem;
693 
694  IteratorEx& operator++()
695  {
696  AKASSERT( this->pItem );
697 
698  pPrevItem = this->pItem;
699  this->pItem = this->pItem->pNextItem;
700 
701  while ( ( this->pItem == NULL ) && ( ++this->uiTable < this->pTable->Length() ) )
702  {
703  pPrevItem = NULL;
704  this->pItem = (*this->pTable)[ this->uiTable ];
705  }
706 
707  return *this;
708  }
709  };
710 
711  Iterator Begin()
712  {
713  Iterator returnedIt;
714 
715  if (HashSize() > 0)
716  {
717  returnedIt.pTable = &m_table;
718  returnedIt.uiTable = 0;
719  returnedIt.pItem = m_table[0];
720 
721  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
722  returnedIt.pItem = m_table[returnedIt.uiTable];
723  }
724  else
725  {
726  returnedIt.pTable = NULL;
727  returnedIt.uiTable = 0;
728  returnedIt.pItem = NULL;
729  }
730 
731  return returnedIt;
732  }
733 
734  IteratorEx BeginEx()
735  {
736  IteratorEx returnedIt;
737 
738  if (HashSize() > 0)
739  {
740  returnedIt.pTable = &m_table;
741  returnedIt.uiTable = 0;
742  returnedIt.pItem = m_table[0];
743  returnedIt.pPrevItem = NULL;
744 
745  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
746  returnedIt.pItem = m_table[ returnedIt.uiTable ];
747  }
748  else
749  {
750  returnedIt.pTable = NULL;
751  returnedIt.uiTable = 0;
752  returnedIt.pItem = NULL;
753  }
754 
755  return returnedIt;
756  }
757 
758  inline Iterator End()
759  {
760  Iterator returnedIt;
761  returnedIt.pItem = NULL;
762  return returnedIt;
763  }
764 
765  IteratorEx FindEx( T_KEY in_Key )
766  {
767  IteratorEx returnedIt;
768 
769  if (HashSize() > 0)
770  {
771  returnedIt.pTable = &m_table;
772  returnedIt.uiTable = AkHash(in_Key) % HashSize();
773  returnedIt.pItem = m_table[returnedIt.uiTable];
774  returnedIt.pPrevItem = NULL;
775 
776  while (returnedIt.pItem != NULL)
777  {
778  if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
779  break;
780 
781  returnedIt.pPrevItem = returnedIt.pItem;
782  returnedIt.pItem = returnedIt.pItem->pNextItem;
783  }
784  }
785  else
786  {
787  returnedIt.pTable = NULL;
788  returnedIt.uiTable = 0;
789  returnedIt.pItem = NULL;
790  returnedIt.pPrevItem = NULL;
791  }
792 
793  return returnedIt;
794  }
795 
796  AkHashListBare()
797  : m_uiSize( 0 )
798  {
799  }
800 
801  ~AkHashListBare()
802  {
803  }
804 
805  //If you set 0 as the starting size, you *must* check all returns of Set() calls.
806  //If you initialize with anything else, you can ignore return codes of Set(), they will always succeed.
807  bool Init(AkUInt32 in_iStartingSize)
808  {
809  m_uiSize = 0;
810 
811  if(!m_table.Resize(in_iStartingSize))
812  return false;
813 
814  for ( AkHashType i = 0; i < HashSize(); ++i )
815  m_table[ i ] = NULL;
816 
817  return true;
818  }
819 
820  void Term()
821  {
822  AKASSERT( m_uiSize == 0 );
823  m_table.Term();
824  }
825 /*
826  void RemoveAll()
827  {
828  for ( AkHashType i = 0; i < HashSize(); ++i )
829  {
830  T_MAPSTRUCT * pItem = m_table[ i ];
831  while ( pItem != NULL )
832  {
833  T_MAPSTRUCT * pNextItem = pItem->pNextItem;
834  pItem->~T_MAPSTRUCT();
835  T_ALLOD::Free( pItem );
836  pItem = pNextItem;
837  }
838 
839  m_table[ i ] = NULL;
840  }
841 
842  m_uiSize = 0;
843  }
844 */
845  T_MAPSTRUCT * Exists( T_KEY in_Key ) const
846  {
847  if (HashSize() > 0)
848  {
849  AkHashType uiTable = AkHash(in_Key) % HashSize();
850  return ExistsInList(in_Key, uiTable);
851  }
852  return NULL;
853  }
854 
855  // Set using an externally preallocated T_MAPSTRUCT -- Hash list takes ownership of the T_MAPSTRUCT.
856  bool Set( T_MAPSTRUCT * in_pItem )
857  {
858  if (CheckSize())
859  {
860  AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
861  AKASSERT(!ExistsInList(KEY_POLICY::Key(in_pItem), uiTable)); // T_MAPSTRUCT must not exist in list !
862 
863  // Add new entry
864 
865  in_pItem->pNextItem = m_table[uiTable];
866  m_table[uiTable] = in_pItem;
867 
868  ++m_uiSize;
869  return true;
870  }
871  //This can only happen if the initial size of the map was 0.
872  return false;
873  }
874 
875  T_MAPSTRUCT * Unset( const T_KEY &in_Key )
876  {
877  T_MAPSTRUCT * pItem = NULL;
878 
879  if (HashSize() > 0)
880  {
881  AkHashType uiTable = AkHash(in_Key) % HashSize();
882  pItem = m_table[uiTable];
883  T_MAPSTRUCT * pPrevItem = NULL;
884  while (pItem != NULL)
885  {
886  if (KEY_POLICY::Key(pItem) == in_Key)
887  break;
888 
889  pPrevItem = pItem;
890  pItem = pItem->pNextItem;
891  }
892 
893  if (pItem)
894  RemoveItem(uiTable, pItem, pPrevItem);
895  }
896 
897  return pItem;
898  }
899 
900  IteratorEx Erase( const IteratorEx& in_rIter )
901  {
902  IteratorEx returnedIt;
903  returnedIt.pTable = in_rIter.pTable;
904  returnedIt.uiTable = in_rIter.uiTable;
905  returnedIt.pItem = in_rIter.pItem->pNextItem;
906  returnedIt.pPrevItem = in_rIter.pPrevItem;
907 
908  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
909  {
910  returnedIt.pPrevItem = NULL;
911  returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
912  }
913 
914  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
915 
916  return returnedIt;
917  }
918 
919  AkUInt32 Length() const
920  {
921  return m_uiSize;
922  }
923 
924  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
925  {
926  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
927  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
928 
929  return AK_Success;
930  }
931 
932  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
933  {
934  AKRESULT res = AK_Fail;
935 
936  AkHashType uNewSize = 0;
937  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
938  {
939  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
940  {
941  uNewSize = kHashSizes[i];
942  break;
943  }
944  }
945 
946  if (uNewSize > 0)
947  {
948  HashTableArray oldArray;
949  oldArray.Transfer(m_table);
950 
951  if (m_table.GrowArray(uNewSize))
952  {
953  for (AkUInt32 i = 0; i < uNewSize; i++)
954  m_table.AddLast(NULL);
955 
956  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
957  {
958  T_MAPSTRUCT* pItem = oldArray[i];
959  while (pItem != NULL)
960  {
961  T_MAPSTRUCT* pNextItem = pItem->pNextItem;
962  {
963  AkHashType uiTable = AkHash(KEY_POLICY::Key(pItem)) % uNewSize;
964  pItem->pNextItem = m_table[uiTable];
965  m_table[uiTable] = pItem;
966  }
967  pItem = pNextItem;
968  }
969  }
970 
971  oldArray.Term();
972 
973  res = AK_Success;
974  }
975  else
976  {
977  //Backpedal..
978  m_table.Transfer(oldArray);
979  }
980  }
981 
982  return res;
983  }
984 
985  inline AkHashType HashSize() const
986  {
987  return m_table.Length();
988  }
989 
990 
991  inline bool CheckSize()
992  {
993  if ( (HashSize() == 0) || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
994  Resize(HashSize());
995 
996  return (HashSize() > 0);
997  }
998 
999 protected:
1000  void RemoveItem( AkHashType in_uiTable, T_MAPSTRUCT* in_pItem, T_MAPSTRUCT* in_pPrevItem )
1001  {
1002  if( in_pPrevItem )
1003  in_pPrevItem->pNextItem = in_pItem->pNextItem;
1004  else
1005  m_table[ in_uiTable ] = in_pItem->pNextItem;
1006 
1007  --m_uiSize;
1008  }
1009 
1010  T_MAPSTRUCT * ExistsInList( T_KEY in_Key, AkHashType in_uiTable ) const
1011  {
1012  T_MAPSTRUCT * pItem = m_table[in_uiTable];
1013  while (pItem != NULL)
1014  {
1015  if (KEY_POLICY::Key(pItem) == in_Key)
1016  return pItem; // found
1017 
1018  pItem = pItem->pNextItem;
1019  }
1020 
1021  return NULL; // not found
1022  }
1023 
1024  HashTableArray m_table;
1025 
1026  AkUInt32 m_uiSize;
1027 };
1028 
1029 
1030 #endif // _AKHASHLIST_H
AkHashListBare::Reserve
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:924
AkReal32
float AkReal32
32-bit floating point
Definition: AkTypes.h:70
AkHashList::EndEx
IteratorEx EndEx()
Definition: AkHashList.h:294
AkHashList::ConstIterator::operator++
ConstIterator & operator++()
Definition: AkHashList.h:108
AkHashList::HashTableArray
AkArray< Item *, Item *, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray
Definition: AkHashList.h:60
AK_Fail
@ AK_Fail
The operation failed.
Definition: AkTypes.h:135
AkHashListBare::Resize
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:932
AkHashList::ExistsInList
T_ITEM * ExistsInList(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:607
AkHashList::End
Iterator End()
Definition: AkHashList.h:280
AkHashList::m_uiSize
AkUInt32 m_uiSize
Definition: AkHashList.h:642
AkHashListBare::m_uiSize
AkUInt32 m_uiSize
Definition: AkHashList.h:1026
AkHashListBare::m_table
HashTableArray m_table
Definition: AkHashList.h:1024
AkHashListBare::Iterator::pTable
AkHashListBare< T_KEY, T_MAPSTRUCT, T_ALLOC, KEY_POLICY >::HashTableArray * pTable
Definition: AkHashList.h:661
AkHashListBare::BeginEx
IteratorEx BeginEx()
Definition: AkHashList.h:734
AK::MemoryMgr::Free
AKSOUNDENGINE_API void Free(AkMemPoolId in_poolId, void *in_pMemAddress)
AkHashListBare::Begin
Iterator Begin()
Definition: AkHashList.h:711
AKRESULT
AKRESULT
Standard function call result.
Definition: AkTypes.h:132
AkHashList::BeginEx
ConstIteratorEx BeginEx() const
Definition: AkHashList.h:256
AkHashListBare::IteratorEx::pPrevItem
T_MAPSTRUCT * pPrevItem
Definition: AkHashList.h:692
AkHashList::Iterator::operator!=
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:96
AkDefaultHashListBarePolicy::Key
static const T_KEY & Key(const T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:651
AkUIntPtr
uintptr_t AkUIntPtr
Definition: AkTypes.h:61
AkHashList::RemoveAll
void RemoveAll()
Definition: AkHashList.h:386
AkHashList::Iterator::uiTable
AkHashType uiTable
Definition: AkHashList.h:65
AkHashListBare::Iterator::operator!=
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:682
AkHashListBare::FindEx
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:765
AkHashListBare::Iterator::operator++
Iterator & operator++()
Definition: AkHashList.h:665
AkHashList::Exists
T_ITEM * Exists(T_KEY in_Key)
Definition: AkHashList.h:405
AkArray
Specific implementation of array.
Definition: AkArray.h:200
AkHashList::Erase
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:495
NULL
#define NULL
Definition: AkTypes.h:47
AkHashListBare::CheckSize
bool CheckSize()
Definition: AkHashList.h:991
AkHashListBare::Set
bool Set(T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:856
AK_Success
@ AK_Success
The operation was successful.
Definition: AkTypes.h:134
AkHashList::RemoveItem
void RemoveItem(AkHashType in_uiTable, Item *in_pItem, Item *in_pPrevItem)
Definition: AkHashList.h:514
AkHashListBare::IteratorEx::operator++
IteratorEx & operator++()
Definition: AkHashList.h:694
AkHashList::Item::Assoc
MapStruct< T_KEY, T_ITEM > Assoc
Definition: AkHashList.h:57
AkHashType
AkUInt32 AkHashType
Definition: AkHashList.h:39
AkHashList::Term
void Term()
Definition: AkHashList.h:380
AkHashList::Length
AkUInt32 Length() const
Definition: AkHashList.h:527
AkPlacementNew
#define AkPlacementNew(_memory)
Definition: AkObject.h:50
AkHashList::ConstIterator::operator!=
bool operator!=(const ConstIterator &in_rOp) const
Definition: AkHashList.h:136
MapStruct
Definition: AkKeyDef.h:35
AkHashListBare::HashSize
AkHashType HashSize() const
Definition: AkHashList.h:985
AkHashList::CreateEntry
T_ITEM * CreateEntry(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:623
AkHashList::ConstIterator::uiTable
AkHashType uiTable
Definition: AkHashList.h:105
AkArray::Resize
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:665
AkHashList::Begin
Iterator Begin()
Definition: AkHashList.h:186
AkHashList::End
ConstIterator End() const
Definition: AkHashList.h:287
kHashTableGrowthFactor
static const AkReal32 kHashTableGrowthFactor
Definition: AkHashList.h:47
AkHashList::ConstIterator::operator->
MapStruct< T_KEY, T_ITEM > * operator->() const
Definition: AkHashList.h:125
AkHashList::AkHashList
AkHashList()
Definition: AkHashList.h:370
AkHashListBare::Length
AkUInt32 Length() const
Definition: AkHashList.h:919
AkHashList::HashSize
AkUInt32 HashSize() const
Definition: AkHashList.h:593
AkHashList::ConstIteratorEx::operator++
ConstIteratorEx & operator++()
Definition: AkHashList.h:169
AkHashListBare::Exists
T_MAPSTRUCT * Exists(T_KEY in_Key) const
Definition: AkHashList.h:845
AKASSERT
#define AKASSERT(Condition)
Definition: AkAssert.h:76
AkHashListBare::AkHashListBare
AkHashListBare()
Definition: AkHashList.h:796
AkHashList::Set
T_ITEM * Set(Item *in_pItem)
Definition: AkHashList.h:416
AkHashList::Iterator::operator++
Iterator & operator++()
Definition: AkHashList.h:68
AkHashList::~AkHashList
~AkHashList()
Definition: AkHashList.h:374
AkHashList::Iterator::operator*
MapStruct< T_KEY, T_ITEM > & operator*()
Definition: AkHashList.h:79
AkHashListBare::Init
bool Init(AkUInt32 in_iStartingSize)
Definition: AkHashList.h:807
AkHashList::ConstIterator::operator*
const MapStruct< T_KEY, T_ITEM > & operator*()
Definition: AkHashList.h:119
AkHash
AkForceInline AkHashType AkHash(T_KEY in_key)
Definition: AkHashList.h:42
AkHashList::Iterator::pItem
Item * pItem
Definition: AkHashList.h:66
AkArray::Transfer
void Transfer(AkArray< T, ARG_T, TAlloc, TGrowBy, TMovePolicy > &in_rSource)
Definition: AkArray.h:695
AkHashList::EndEx
ConstIterator EndEx() const
Definition: AkHashList.h:301
AkHashList::ConstIterator::operator==
bool operator==(const ConstIterator &in_rOp) const
Definition: AkHashList.h:131
AkHashList::Resize
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:540
AkHashList::Reserve
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:532
AkArray::Begin
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:286
kHashSizes
static const AkHashType kHashSizes[]
Definition: AkHashList.h:45
AkArray::Length
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:452
AkHashList::Iterator::operator->
MapStruct< T_KEY, T_ITEM > * operator->()
Definition: AkHashList.h:85
kNumHashSizes
static const size_t kNumHashSizes
Definition: AkHashList.h:46
AkHashList::m_table
HashTableArray m_table
Definition: AkHashList.h:641
AkHashList::FindEx
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:308
AkHashList::BeginEx
IteratorEx BeginEx()
Definition: AkHashList.h:232
AkHashList::Iterator::pTable
AkHashList< T_KEY, T_ITEM, T_ALLOC >::HashTableArray * pTable
Definition: AkHashList.h:64
AkHashListBare::End
Iterator End()
Definition: AkHashList.h:758
AkArray::GrowArray
bool GrowArray()
Definition: AkArray.h:617
AkHashList::Iterator::operator==
bool operator==(const Iterator &in_rOp) const
Definition: AkHashList.h:91
AkArray::AddLast
AkForceInline T * AddLast()
Definition: AkArray.h:478
AkHashListBare::Unset
T_MAPSTRUCT * Unset(const T_KEY &in_Key)
Definition: AkHashList.h:875
AkUInt32
uint32_t AkUInt32
Unsigned 32-bit integer.
Definition: AkTypes.h:59
AkHashListBare::RemoveItem
void RemoveItem(AkHashType in_uiTable, T_MAPSTRUCT *in_pItem, T_MAPSTRUCT *in_pPrevItem)
Definition: AkHashList.h:1000
AkHashListBare::Iterator::pItem
T_MAPSTRUCT * pItem
Definition: AkHashList.h:663
AkArray::Term
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:440
AkHashListBare::Term
void Term()
Definition: AkHashList.h:820
AkHashList::Set
T_ITEM * Set(T_KEY in_Key)
Definition: AkHashList.h:437
AkHashListBare::Erase
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:900
AkHashListBare::ExistsInList
T_MAPSTRUCT * ExistsInList(T_KEY in_Key, AkHashType in_uiTable) const
Definition: AkHashList.h:1010
AkForceInline
#define AkForceInline
Definition: AkTypes.h:60
AkHashListBare::Iterator::uiTable
AkHashType uiTable
Definition: AkHashList.h:662
AkHashList::Set
T_ITEM * Set(T_KEY in_Key, bool &out_bWasAlreadyThere)
Definition: AkHashList.h:452
AkHashListBare::Iterator::operator*
T_MAPSTRUCT * operator*()
Definition: AkHashList.h:676
AkHashList::Item::pNextItem
Item * pNextItem
Definition: AkHashList.h:56
AkHashList::Begin
ConstIterator Begin() const
Definition: AkHashList.h:209
AkHashListBare::~AkHashListBare
~AkHashListBare()
Definition: AkHashList.h:801
AkHashList::FindEx
ConstIteratorEx FindEx(T_KEY in_Key) const
Definition: AkHashList.h:339
AkHashList::IteratorEx::operator++
IteratorEx & operator++()
Definition: AkHashList.h:148
AkHashList::CheckSize
bool CheckSize()
Definition: AkHashList.h:598
AkHashList::Unset
void Unset(T_KEY in_Key)
Definition: AkHashList.h:474
AkHashList::ConstIterator::pTable
const AkHashList< T_KEY, T_ITEM, T_ALLOC >::HashTableArray * pTable
Definition: AkHashList.h:104

Was this page helpful?

Need Support?

Questions? Problems? Need more info? Contact us, and we can help!

Visit our Support page

Tell us about your project. We're here to help.

Register your project and we'll help you get started with no strings attached!

Get started with Wwise