Version
menu_open
link
Wwise SDK 2023.1.4
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  Copyright (c) 2024 Audiokinetic Inc.
25 *******************************************************************************/
26 
27 #ifndef _AKHASHLIST_H
28 #define _AKHASHLIST_H
29 
30 #include <AK/Tools/Common/AkKeyDef.h>// for MapStruct
33 
34 // NOTE: when using this template, a hashing function of the following form must be available:
35 //
36 // AkHashType AkHash( T_KEY );
37 
39 
40 template < class T_KEY >
41 AkForceInline AkHashType AkHash(T_KEY in_key) { return (AkHashType)in_key; }
42 
43 #define AK_HASH_SIZE_VERY_SMALL 11
44 extern const AK_SELECTANY 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 };
45 constexpr size_t kNumHashSizes = sizeof(kHashSizes) / sizeof(kHashSizes[0]);
47 
48 template < class T_KEY, class T_ITEM, typename T_ALLOC = ArrayPoolDefault >
49 class AkHashList: public T_ALLOC
50 {
51 public:
52 
53  struct Item
54  {
55  Item * pNextItem; // our next one
56  MapStruct<T_KEY, T_ITEM> Assoc; // key-item association
57  };
58 
60 
61  struct Iterator
62  {
66 
67  inline Iterator& operator++()
68  {
69  AKASSERT( pItem );
71 
72  while ( ( pItem == NULL ) && ( ++uiTable < pTable->Length() ) )
73  pItem = (*pTable)[ uiTable ];
74 
75  return *this;
76  }
77 
79  {
80  AKASSERT( pItem );
81  return pItem->Assoc;
82  }
83 
85  {
86  AKASSERT(pItem);
87  return &pItem->Assoc;
88  }
89 
90  bool operator ==(const Iterator& in_rOp) const
91  {
92  return pItem == in_rOp.pItem;
93  }
94 
95  bool operator !=( const Iterator& in_rOp ) const
96  {
97  return !operator==(in_rOp);
98  }
99  };
100 
102  {
106 
108  {
109  AKASSERT(pItem);
110  pItem = pItem->pNextItem;
111 
112  while ((pItem == NULL) && (++uiTable < pTable->Length()))
113  pItem = (*pTable)[uiTable];
114 
115  return *this;
116  }
117 
119  {
120  AKASSERT(pItem);
121  return pItem->Assoc;
122  }
123 
125  {
126  AKASSERT(pItem);
127  return &pItem->Assoc;
128  }
129 
130  bool operator ==(const ConstIterator& in_rOp) const
131  {
132  return pItem == in_rOp.pItem;
133  }
134 
135  bool operator !=(const ConstIterator& in_rOp) const
136  {
137  return !operator==(in_rOp);
138  }
139  };
140 
141  // The IteratorEx iterator is intended for usage when a possible erase may occurs
142  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
143  struct IteratorEx : public Iterator
144  {
146 
148  {
149  AKASSERT( this->pItem );
150 
151  pPrevItem = this->pItem;
152  this->pItem = this->pItem->pNextItem;
153 
154  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
155  {
156  pPrevItem = NULL;
157  this->pItem = (*this->pTable)[ this->uiTable ];
158  }
159 
160  return *this;
161  }
162  };
163 
165  {
167 
169  {
170  AKASSERT(this->pItem);
171 
172  pPrevItem = this->pItem;
173  this->pItem = this->pItem->pNextItem;
174 
175  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
176  {
177  pPrevItem = NULL;
178  this->pItem = (*this->pTable)[this->uiTable];
179  }
180 
181  return *this;
182  }
183  };
184 
185  Iterator Begin()
186  {
187  Iterator returnedIt;
188 
189  if (HashSize() > 0)
190  {
191  returnedIt.pTable = &m_table;
192  returnedIt.uiTable = 0;
193  returnedIt.pItem = m_table[0];
194 
195  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
196  returnedIt.pItem = m_table[returnedIt.uiTable];
197  }
198  else
199  {
200  returnedIt.pTable = NULL;
201  returnedIt.uiTable = 0;
202  returnedIt.pItem = NULL;
203  }
204 
205  return returnedIt;
206  }
207 
208  ConstIterator Begin() const
209  {
210  ConstIterator returnedIt;
211 
212  if (HashSize() > 0)
213  {
214  returnedIt.pTable = &m_table;
215  returnedIt.uiTable = 0;
216  returnedIt.pItem = m_table[0];
217 
218  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
219  returnedIt.pItem = m_table[returnedIt.uiTable];
220  }
221  else
222  {
223  returnedIt.pTable = NULL;
224  returnedIt.uiTable = 0;
225  returnedIt.pItem = NULL;
226  }
227 
228  return returnedIt;
229  }
230 
231  IteratorEx BeginEx()
232  {
233  IteratorEx returnedIt;
234 
235  if (HashSize() > 0)
236  {
237  returnedIt.pTable = &m_table;
238  returnedIt.uiTable = 0;
239  returnedIt.pItem = *(m_table.Begin());
240  returnedIt.pPrevItem = NULL;
241 
242  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
243  returnedIt.pItem = m_table[returnedIt.uiTable];
244  }
245  else
246  {
247  returnedIt.pTable = NULL;
248  returnedIt.uiTable = 0;
249  returnedIt.pItem = NULL;
250  }
251 
252  return returnedIt;
253  }
254 
255  ConstIteratorEx BeginEx() const
256  {
257  ConstIteratorEx returnedIt;
258 
259  if (HashSize() > 0)
260  {
261  returnedIt.pTable = &m_table;
262  returnedIt.uiTable = 0;
263  returnedIt.pItem = *(m_table.Begin());
264  returnedIt.pPrevItem = NULL;
265 
266  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
267  returnedIt.pItem = m_table[returnedIt.uiTable];
268  }
269  else
270  {
271  returnedIt.pTable = NULL;
272  returnedIt.uiTable = 0;
273  returnedIt.pItem = NULL;
274  }
275 
276  return returnedIt;
277  }
278 
279  inline Iterator End()
280  {
281  Iterator returnedIt;
282  returnedIt.pItem = NULL;
283  return returnedIt;
284  }
285 
286  inline ConstIterator End() const
287  {
288  ConstIterator returnedIt;
289  returnedIt.pItem = NULL;
290  return returnedIt;
291  }
292 
293  inline IteratorEx EndEx()
294  {
295  IteratorEx returnedIt;
296  returnedIt.pItem = NULL;
297  return returnedIt;
298  }
299 
300  inline ConstIterator EndEx() const
301  {
302  ConstIteratorEx returnedIt;
303  returnedIt.pItem = NULL;
304  return returnedIt;
305  }
306 
307  IteratorEx FindEx( T_KEY in_Key )
308  {
309  IteratorEx returnedIt;
310 
311  if (HashSize() > 0)
312  {
313  returnedIt.pTable = &m_table;
314  returnedIt.uiTable = AkHash(in_Key) % HashSize();
315  returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
316  returnedIt.pPrevItem = NULL;
317 
318  while (returnedIt.pItem != NULL)
319  {
320  if (returnedIt.pItem->Assoc.key == in_Key)
321  break;
322 
323  returnedIt.pPrevItem = returnedIt.pItem;
324  returnedIt.pItem = returnedIt.pItem->pNextItem;
325  }
326  }
327  else
328  {
329  returnedIt.pTable = NULL;
330  returnedIt.uiTable = 0;
331  returnedIt.pItem = NULL;
332  returnedIt.pPrevItem = NULL;
333  }
334 
335  return returnedIt;
336  }
337 
338  ConstIteratorEx FindEx(T_KEY in_Key) const
339  {
340  ConstIteratorEx returnedIt;
341 
342  if (HashSize() > 0)
343  {
344  returnedIt.pTable = &m_table;
345  returnedIt.uiTable = AkHash(in_Key) % HashSize();
346  returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
347  returnedIt.pPrevItem = NULL;
348 
349  while (returnedIt.pItem != NULL)
350  {
351  if (returnedIt.pItem->Assoc.key == in_Key)
352  break;
353 
354  returnedIt.pPrevItem = returnedIt.pItem;
355  returnedIt.pItem = returnedIt.pItem->pNextItem;
356  }
357  }
358  else
359  {
360  returnedIt.pTable = NULL;
361  returnedIt.uiTable = 0;
362  returnedIt.pItem = NULL;
363  returnedIt.pPrevItem = NULL;
364  }
365 
366  return returnedIt;
367  }
368 
370  {
371  }
372 
374  {
375  AKASSERT(m_uiSize == 0);
376  m_table.Term();
377  }
378 
379  void Term()
380  {
381  RemoveAll();
382  m_table.Term();
383  }
384 
385  void RemoveAll()
386  {
387  for (AkHashType i = 0; i < HashSize(); ++i)
388  {
389  Item * pItem = m_table[ i ];
390  while ( pItem != NULL )
391  {
392  Item * pNextItem = pItem->pNextItem;
393  pItem->Assoc.item.~T_ITEM();
394  T_ALLOC::Free( pItem );
395  pItem = pNextItem;
396  }
397 
398  m_table[ i ] = NULL;
399  }
400 
401  m_uiSize = 0;
402  }
403 
404  T_ITEM * Exists( T_KEY in_Key )
405  {
406  if (HashSize() > 0)
407  {
408  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
409  return ExistsInList(in_Key, uiTable);
410  }
411  return NULL;
412  }
413 
414  // Set using an externally preallocated Item -- Hash list takes ownership of the Item.
415  T_ITEM * Set( Item * in_pItem )
416  {
417  if (CheckSize())
418  {
419  AkHashType uiTable = AkHash(in_pItem->Assoc.key) % HashSize();
420 
421  AKASSERT(!ExistsInList(in_pItem->Assoc.key, uiTable)); // Item must not exist in list !
422 
423  // Add new entry
424 
425  in_pItem->pNextItem = m_table[uiTable];
426  m_table[uiTable] = in_pItem;
427 
428  ++m_uiSize;
429 
430  return &(in_pItem->Assoc.item);
431  }
432 
433  return NULL;
434  }
435 
436  T_ITEM * Set( T_KEY in_Key )
437  {
438  if ( CheckSize() )
439  {
440  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
441  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
442  if (pItem)
443  return pItem;
444 
445  return CreateEntry(in_Key, uiTable);
446  }
447 
448  return NULL;
449  }
450 
451  T_ITEM * Set( T_KEY in_Key, bool& out_bWasAlreadyThere )
452  {
453  if (CheckSize())
454  {
455  AkHashType uiTable = AkHash(in_Key) % HashSize();
456  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
457  if (pItem)
458  {
459  out_bWasAlreadyThere = true;
460  return pItem;
461  }
462  else
463  {
464  out_bWasAlreadyThere = false;
465  }
466 
467  return CreateEntry(in_Key, uiTable);
468  }
469 
470  return NULL;
471  }
472 
473  void Unset( T_KEY in_Key )
474  {
475  if (HashSize() > 0)
476  {
477  AkHashType uiTable = AkHash(in_Key) % HashSize();
478  Item * pItem = m_table[uiTable];
479  Item * pPrevItem = NULL;
480  while (pItem != NULL)
481  {
482  if (pItem->Assoc.key == in_Key)
483  break;
484 
485  pPrevItem = pItem;
486  pItem = pItem->pNextItem;
487  }
488 
489  if (pItem)
490  RemoveItem(uiTable, pItem, pPrevItem);
491  }
492  }
493 
494  IteratorEx Erase( const IteratorEx& in_rIter )
495  {
496  IteratorEx returnedIt;
497  returnedIt.pTable = in_rIter.pTable;
498  returnedIt.uiTable = in_rIter.uiTable;
499  returnedIt.pItem = in_rIter.pItem->pNextItem;
500  returnedIt.pPrevItem = in_rIter.pPrevItem;
501 
502  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
503  {
504  returnedIt.pPrevItem = NULL;
505  returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
506  }
507 
508  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
509 
510  return returnedIt;
511  }
512 
513  void RemoveItem( AkHashType in_uiTable, Item* in_pItem, Item* in_pPrevItem )
514  {
515  if( in_pPrevItem )
516  in_pPrevItem->pNextItem = in_pItem->pNextItem;
517  else
518  m_table[ in_uiTable ] = in_pItem->pNextItem;
519 
520  in_pItem->Assoc.item.~T_ITEM();
521  T_ALLOC::Free(in_pItem);
522 
523  --m_uiSize;
524  }
525 
526  AkUInt32 Length() const
527  {
528  return m_uiSize;
529  }
530 
531  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
532  {
533  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
534  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
535 
536  return AK_Success;
537  }
538 
539  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
540  {
541  AKRESULT res = AK_Fail;
542 
543  AkUInt32 uNewSize = 0;
544  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
545  {
546  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
547  {
548  uNewSize = kHashSizes[i];
549  break;
550  }
551  }
552 
553  if (uNewSize > 0)
554  {
555  HashTableArray oldArray;
556  oldArray.Transfer(m_table);
557 
558  if ( m_table.GrowArray(uNewSize) )
559  {
560  for (AkUInt32 i = 0; i < uNewSize; i++)
562 
563  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
564  {
565  Item * pItem = oldArray[i];
566  while (pItem != NULL)
567  {
568  Item * pNextItem = pItem->pNextItem;
569  {
570  AkHashType uiTable = AkHash(pItem->Assoc.key) % HashSize();
571  pItem->pNextItem = m_table[uiTable];
572  m_table[uiTable] = pItem;
573  }
574  pItem = pNextItem;
575  }
576  }
577 
578  oldArray.Term();
579 
580  res = AK_Success;
581  }
582  else
583  {
584  //Backpedal..
585  m_table.Transfer(oldArray);
586  }
587  }
588 
589  return res;
590  }
591 
592  inline AkUInt32 HashSize() const
593  {
594  return m_table.Length();
595  }
596 
597  inline bool CheckSize()
598  {
600  Resize(HashSize());
601 
602  return (HashSize() > 0);
603  }
604 
606  {
607  Term();
608 
609  m_table.Transfer(in_source.m_table);
610  m_uiSize = in_source.m_uiSize;
611 
612  in_source.m_uiSize = 0;
613  }
614 
615 protected:
616  T_ITEM * ExistsInList( T_KEY in_Key, AkUIntPtr in_uiTable )
617  {
618  AKASSERT(HashSize() > 0);
619 
620  Item * pItem = m_table[(AkUInt32)in_uiTable];
621  while (pItem != NULL)
622  {
623  if (pItem->Assoc.key == in_Key)
624  return &(pItem->Assoc.item); // found
625 
626  pItem = pItem->pNextItem;
627  }
628 
629  return NULL; // not found
630  }
631 
632  T_ITEM * CreateEntry( T_KEY in_Key, AkUIntPtr in_uiTable )
633  {
634  Item * pNewItem = (Item *)T_ALLOC::Alloc(sizeof(Item));
635  if ( pNewItem == NULL )
636  return NULL;
637 
638  pNewItem->pNextItem = m_table[ (AkUInt32)in_uiTable ];
639  pNewItem->Assoc.key = in_Key;
640 
641  AkPlacementNew( &(pNewItem->Assoc.item) ) T_ITEM;
642 
643  m_table[(AkUInt32)in_uiTable] = pNewItem;
644 
645  ++m_uiSize;
646 
647  return &(pNewItem->Assoc.item);
648  }
649 
652 };
653 
654 // this one lets you define the structure
655 // only requirement is that T_MAPSTRUCT must have members pNextItem and key.
656 // client is responsible for allocation/deallocation of T_MAPSTRUCTS.
657 template <class T_KEY, class T_MAPSTRUCT>
659 {
660  static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) {return in_pItem->key;}
661  static T_MAPSTRUCT*& Next(T_MAPSTRUCT* in_pItem) { return (*in_pItem).pNextItem; }
662 };
663 
664 template <class T_KEY, class T_MAPSTRUCT>
666 {
667  static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) { return in_pItem->Key(); }
668  static T_MAPSTRUCT*& Next(T_MAPSTRUCT* in_pItem) { return (*in_pItem).pNextItem; }
669 };
670 
671 template <class T_KEY, class T_MAPSTRUCT>
673 
674 template <class T_KEY, class T_MAPSTRUCT, typename T_ALLOC = ArrayPoolDefault, class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>, class LIST_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>>
676 {
678 public:
679  struct Iterator
680  {
683  T_MAPSTRUCT* pItem;
684 
686  {
687  AKASSERT( pItem );
688  pItem = LIST_POLICY::Next(pItem);
689 
690  while ((pItem == NULL) && (++uiTable < pTable->Length()))
691  pItem = (*pTable)[ uiTable ];
692 
693  return *this;
694  }
695 
696  inline T_MAPSTRUCT * operator*()
697  {
698  AKASSERT( pItem );
699  return pItem;
700  }
701 
702  inline T_MAPSTRUCT* operator->()
703  {
704  AKASSERT(pItem);
705  return pItem;
706  }
707 
708  bool operator !=( const Iterator& in_rOp ) const
709  {
710  return ( pItem != in_rOp.pItem );
711  }
712 
713  bool operator ==(const Iterator& in_rOp) const
714  {
715  return (pItem == in_rOp.pItem);
716  }
717  };
718 
720  {
723  T_MAPSTRUCT* pItem;
724 
726  {
727  AKASSERT(pItem);
728  pItem = pItem->pNextItem;
729 
730  while ((pItem == NULL) && (++uiTable < pTable->Length()))
731  pItem = (*pTable)[uiTable];
732 
733  return *this;
734  }
735 
736  inline const T_MAPSTRUCT* operator*()
737  {
738  AKASSERT(pItem);
739  return pItem;
740  }
741 
742  inline const T_MAPSTRUCT* operator->() const
743  {
744  AKASSERT(pItem);
745  return pItem;
746  }
747 
748  bool operator !=(const ConstIterator& in_rOp) const
749  {
750  return (pItem != in_rOp.pItem);
751  }
752 
753  bool operator ==(const ConstIterator& in_rOp) const
754  {
755  return (pItem == in_rOp.pItem);
756  }
757  };
758 
759  // The IteratorEx iterator is intended for usage when a possible erase may occurs
760  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
761  struct IteratorEx : public Iterator
762  {
763  T_MAPSTRUCT* pPrevItem;
764 
766  {
767  AKASSERT(this->pItem);
768 
769  pPrevItem = this->pItem;
770  this->pItem = this->pItem->pNextItem;
771 
772  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
773  {
774  pPrevItem = NULL;
775  this->pItem = (*this->pTable)[this->uiTable];
776  }
777 
778  return *this;
779  }
780  };
781 
783  {
784  T_MAPSTRUCT* pPrevItem;
785 
787  {
788  AKASSERT( this->pItem );
789 
790  pPrevItem = this->pItem;
791  this->pItem = LIST_POLICY::Next(this->pItem);
792 
793  while ( ( this->pItem == NULL ) && ( ++this->uiTable < this->pTable->Length() ) )
794  {
795  pPrevItem = NULL;
796  this->pItem = (*this->pTable)[ this->uiTable ];
797  }
798 
799  return *this;
800  }
801  };
802 
803  Iterator Begin()
804  {
805  Iterator returnedIt;
806 
807  if (HashSize() > 0)
808  {
809  returnedIt.pTable = &m_table;
810  returnedIt.uiTable = 0;
811  returnedIt.pItem = m_table[0];
812 
813  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
814  returnedIt.pItem = m_table[returnedIt.uiTable];
815  }
816  else
817  {
818  returnedIt.pTable = NULL;
819  returnedIt.uiTable = 0;
820  returnedIt.pItem = NULL;
821  }
822 
823  return returnedIt;
824  }
825 
826  ConstIterator Begin() const
827  {
828  ConstIterator returnedIt;
829 
830  if (HashSize() > 0)
831  {
832  returnedIt.pTable = &m_table;
833  returnedIt.uiTable = 0;
834  returnedIt.pItem = m_table[0];
835 
836  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
837  returnedIt.pItem = m_table[returnedIt.uiTable];
838  }
839  else
840  {
841  returnedIt.pTable = NULL;
842  returnedIt.uiTable = 0;
843  returnedIt.pItem = NULL;
844  }
845 
846  return returnedIt;
847  }
848 
849  IteratorEx BeginEx()
850  {
851  IteratorEx returnedIt;
852 
853  if (HashSize() > 0)
854  {
855  returnedIt.pTable = &m_table;
856  returnedIt.uiTable = 0;
857  returnedIt.pItem = m_table[0];
858  returnedIt.pPrevItem = NULL;
859 
860  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
861  returnedIt.pItem = m_table[ returnedIt.uiTable ];
862  }
863  else
864  {
865  returnedIt.pTable = NULL;
866  returnedIt.uiTable = 0;
867  returnedIt.pItem = NULL;
868  returnedIt.pPrevItem = NULL;
869  }
870 
871  return returnedIt;
872  }
873 
874  ConstIteratorEx BeginEx() const
875  {
876  ConstIteratorEx returnedIt;
877 
878  if (HashSize() > 0)
879  {
880  returnedIt.pTable = &m_table;
881  returnedIt.uiTable = 0;
882  returnedIt.pItem = m_table[0];
883  returnedIt.pPrevItem = NULL;
884 
885  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
886  returnedIt.pItem = m_table[returnedIt.uiTable];
887  }
888  else
889  {
890  returnedIt.pTable = NULL;
891  returnedIt.uiTable = 0;
892  returnedIt.pItem = NULL;
893  returnedIt.pPrevItem = NULL;
894  }
895 
896  return returnedIt;
897  }
898 
899  inline Iterator End()
900  {
901  Iterator returnedIt;
902  returnedIt.pItem = NULL;
903  return returnedIt;
904  }
905 
906  inline ConstIterator End() const
907  {
908  ConstIterator returnedIt;
909  returnedIt.pItem = NULL;
910  return returnedIt;
911  }
912 
913  IteratorEx FindEx( T_KEY in_Key )
914  {
915  IteratorEx returnedIt;
916 
917  if (HashSize() > 0)
918  {
919  returnedIt.pTable = &m_table;
920  returnedIt.uiTable = AkHash(in_Key) % HashSize();
921  returnedIt.pItem = m_table[returnedIt.uiTable];
922  returnedIt.pPrevItem = NULL;
923 
924  while (returnedIt.pItem != NULL)
925  {
926  if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
927  break;
928 
929  returnedIt.pPrevItem = returnedIt.pItem;
930  returnedIt.pItem = LIST_POLICY::Next(returnedIt.pItem);
931  }
932  }
933  else
934  {
935  returnedIt.pTable = NULL;
936  returnedIt.uiTable = 0;
937  returnedIt.pItem = NULL;
938  returnedIt.pPrevItem = NULL;
939  }
940 
941  return returnedIt;
942  }
943 
944  ConstIteratorEx FindEx(T_KEY in_Key) const
945  {
946  ConstIteratorEx returnedIt;
947 
948  if (HashSize() > 0)
949  {
950  returnedIt.pTable = &m_table;
951  returnedIt.uiTable = AkHash(in_Key) % HashSize();
952  returnedIt.pItem = m_table[returnedIt.uiTable];
953  returnedIt.pPrevItem = NULL;
954 
955  while (returnedIt.pItem != NULL)
956  {
957  if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
958  break;
959 
960  returnedIt.pPrevItem = returnedIt.pItem;
961  returnedIt.pItem = returnedIt.pItem->pNextItem;
962  }
963  }
964  else
965  {
966  returnedIt.pTable = NULL;
967  returnedIt.uiTable = 0;
968  returnedIt.pItem = NULL;
969  returnedIt.pPrevItem = NULL;
970  }
971 
972  return returnedIt;
973  }
974 
976  : m_uiSize( 0 )
977  {
978  }
979 
981  {
982  }
983 
984  //If you set 0 as the starting size, you *must* check all returns of Set() calls.
985  //If you initialize with anything else, you can ignore return codes of Set(), they will always succeed.
986  bool Init(AkUInt32 in_iStartingSize)
987  {
988  m_uiSize = 0;
989 
990  if(!m_table.Resize(in_iStartingSize))
991  return false;
992 
993  for ( AkHashType i = 0; i < HashSize(); ++i )
994  m_table[ i ] = NULL;
995 
996  return true;
997  }
998 
999  void Term()
1000  {
1001  AKASSERT( m_uiSize == 0 );
1002  m_table.Term();
1003  }
1004 /*
1005  void RemoveAll()
1006  {
1007  for ( AkHashType i = 0; i < HashSize(); ++i )
1008  {
1009  T_MAPSTRUCT * pItem = m_table[ i ];
1010  while ( pItem != NULL )
1011  {
1012  T_MAPSTRUCT * pNextItem = LIST_POLICY::Next(pItem);
1013  pItem->~T_MAPSTRUCT();
1014  T_ALLOD::Free( pItem );
1015  pItem = pNextItem;
1016  }
1017 
1018  m_table[ i ] = NULL;
1019  }
1020 
1021  m_uiSize = 0;
1022  }
1023 */
1024  T_MAPSTRUCT * Exists( T_KEY in_Key ) const
1025  {
1026  if (HashSize() > 0)
1027  {
1028  AkHashType uiTable = AkHash(in_Key) % HashSize();
1029  return ExistsInList(in_Key, uiTable);
1030  }
1031  return NULL;
1032  }
1033 
1034  // Set using an externally preallocated T_MAPSTRUCT -- Hash list takes ownership of the T_MAPSTRUCT.
1035  bool Set( T_MAPSTRUCT * in_pItem, bool& out_exists )
1036  {
1037  out_exists = false;
1038  if (CheckSize())
1039  {
1040  AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
1041  if (ExistsInList(KEY_POLICY::Key(in_pItem), uiTable))
1042  {
1043  out_exists = true;
1044  return false;
1045  }
1046 
1047  _Set(in_pItem, uiTable);
1048  return true;
1049  }
1050  //This can only happen if the initial size of the map was 0.
1051  return false;
1052  }
1053 
1054  bool Set( T_MAPSTRUCT * in_pItem )
1055  {
1056  if (CheckSize())
1057  {
1058  AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
1059  AKASSERT(!ExistsInList(KEY_POLICY::Key(in_pItem), uiTable)); // T_MAPSTRUCT must not exist in list !
1060  _Set(in_pItem, uiTable);
1061  return true;
1062  }
1063  //This can only happen if the initial size of the map was 0.
1064  return false;
1065  }
1066 
1067 private:
1068  void _Set( T_MAPSTRUCT * in_pItem, AkHashType in_uiTable )
1069  {
1070  LIST_POLICY::Next(in_pItem) = m_table[in_uiTable];
1071  m_table[in_uiTable] = in_pItem;
1072  ++m_uiSize;
1073  }
1074 
1075 public:
1076  T_MAPSTRUCT * Unset( const T_KEY &in_Key )
1077  {
1078  T_MAPSTRUCT * pItem = NULL;
1079 
1080  if (HashSize() > 0)
1081  {
1082  AkHashType uiTable = AkHash(in_Key) % HashSize();
1083  pItem = m_table[uiTable];
1084  T_MAPSTRUCT * pPrevItem = NULL;
1085  while (pItem != NULL)
1086  {
1087  if (KEY_POLICY::Key(pItem) == in_Key)
1088  break;
1089 
1090  pPrevItem = pItem;
1091  pItem = LIST_POLICY::Next(pItem);
1092  }
1093 
1094  if (pItem)
1095  RemoveItem(uiTable, pItem, pPrevItem);
1096  }
1097 
1098  return pItem;
1099  }
1100 
1101  IteratorEx Erase( const IteratorEx& in_rIter )
1102  {
1103  IteratorEx returnedIt;
1104  returnedIt.pTable = in_rIter.pTable;
1105  returnedIt.uiTable = in_rIter.uiTable;
1106  returnedIt.pItem = LIST_POLICY::Next(in_rIter.pItem);
1107  returnedIt.pPrevItem = in_rIter.pPrevItem;
1108 
1109  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
1110  {
1111  returnedIt.pPrevItem = NULL;
1112  returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
1113  }
1114 
1115  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
1116 
1117  return returnedIt;
1118  }
1119 
1121  {
1122  return m_uiSize;
1123  }
1124 
1125  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
1126  {
1127  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
1128  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
1129 
1130  return AK_Success;
1131  }
1132 
1133  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
1134  {
1135  AKRESULT res = AK_Fail;
1136 
1137  AkHashType uNewSize = 0;
1138  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
1139  {
1140  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
1141  {
1142  uNewSize = kHashSizes[i];
1143  break;
1144  }
1145  }
1146 
1147  if (uNewSize > 0)
1148  {
1149  HashTableArray oldArray;
1150  oldArray.Transfer(m_table);
1151 
1152  if (m_table.GrowArray(uNewSize))
1153  {
1154  for (AkUInt32 i = 0; i < uNewSize; i++)
1155  m_table.AddLast(NULL);
1156 
1157  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
1158  {
1159  T_MAPSTRUCT* pItem = oldArray[i];
1160  while (pItem != NULL)
1161  {
1162  T_MAPSTRUCT* pNextItem = LIST_POLICY::Next(pItem);
1163  {
1164  AkHashType uiTable = AkHash(KEY_POLICY::Key(pItem)) % uNewSize;
1165  LIST_POLICY::Next(pItem) = m_table[uiTable];
1166  m_table[uiTable] = pItem;
1167  }
1168  pItem = pNextItem;
1169  }
1170  }
1171 
1172  oldArray.Term();
1173 
1174  res = AK_Success;
1175  }
1176  else
1177  {
1178  //Backpedal..
1179  m_table.Transfer(oldArray);
1180  }
1181  }
1182 
1183  return res;
1184  }
1185 
1186  inline AkHashType HashSize() const
1187  {
1188  return m_table.Length();
1189  }
1190 
1191 
1192  inline bool CheckSize()
1193  {
1195  Resize(HashSize());
1196 
1197  return (HashSize() > 0);
1198  }
1199 
1200 protected:
1201  void RemoveItem( AkHashType in_uiTable, T_MAPSTRUCT* in_pItem, T_MAPSTRUCT* in_pPrevItem )
1202  {
1203  if( in_pPrevItem )
1204  LIST_POLICY::Next(in_pPrevItem) = LIST_POLICY::Next(in_pItem);
1205  else
1206  m_table[ in_uiTable ] = LIST_POLICY::Next(in_pItem);
1207 
1208  --m_uiSize;
1209  }
1210 
1211  T_MAPSTRUCT * ExistsInList( T_KEY in_Key, AkHashType in_uiTable ) const
1212  {
1213  T_MAPSTRUCT * pItem = m_table[in_uiTable];
1214  while (pItem != NULL)
1215  {
1216  if (KEY_POLICY::Key(pItem) == in_Key)
1217  return pItem; // found
1218 
1219  pItem = LIST_POLICY::Next(pItem);
1220  }
1221 
1222  return NULL; // not found
1223  }
1224 
1226 
1228 };
1229 
1230 
1231 #endif // _AKHASHLIST_H
AkHashListBare< T_KEY, T_MAPSTRUCT, T_ALLOC, KEY_POLICY, LIST_POLICY >::HashTableArray * pTable
Definition: AkHashList.h:681
IteratorEx EndEx()
Definition: AkHashList.h:293
bool operator!=(const ConstIterator &in_rOp) const
Definition: AkHashList.h:748
ConstIterator & operator++()
Definition: AkHashList.h:107
AkArray< Item *, Item *, T_ALLOC, AkGrowByPolicy_NoGrow > HashTableArray
Definition: AkHashList.h:59
@ AK_Fail
The operation failed.
Definition: AkTypes.h:134
static const T_KEY & Key(const T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:660
T_ITEM * ExistsInList(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:616
Iterator End()
Definition: AkHashList.h:279
Iterator & operator++()
Definition: AkHashList.h:685
ConstIteratorEx BeginEx() const
Definition: AkHashList.h:874
AkUInt32 m_uiSize
Definition: AkHashList.h:651
IteratorEx BeginEx()
Definition: AkHashList.h:849
HashTableArray m_table
Definition: AkHashList.h:1225
AKSOUNDENGINE_API void Free(AkMemPoolId in_poolId, void *in_pMemAddress)
static T_MAPSTRUCT *& Next(T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:668
AKRESULT
Standard function call result.
Definition: AkTypes.h:131
ConstIteratorEx BeginEx() const
Definition: AkHashList.h:255
T_MAPSTRUCT * ExistsInList(T_KEY in_Key, AkHashType in_uiTable) const
Definition: AkHashList.h:1211
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:95
ConstIterator End() const
Definition: AkHashList.h:906
void RemoveAll()
Definition: AkHashList.h:385
AkHashType uiTable
Definition: AkHashList.h:64
T_ITEM * Exists(T_KEY in_Key)
Definition: AkHashList.h:404
bool Set(T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:1054
Specific implementation of array.
Definition: AkArray.h:258
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:494
#define NULL
Definition: AkTypes.h:46
float AkReal32
32-bit floating point
@ AK_Success
The operation was successful.
Definition: AkTypes.h:133
ConstIterator & operator++()
Definition: AkHashList.h:725
const AkHashListBare< T_KEY, T_MAPSTRUCT, T_ALLOC, KEY_POLICY >::HashTableArray * pTable
Definition: AkHashList.h:721
constexpr size_t kNumHashSizes
Definition: AkHashList.h:45
void RemoveItem(AkHashType in_uiTable, Item *in_pItem, Item *in_pPrevItem)
Definition: AkHashList.h:513
AkUInt32 Length() const
Definition: AkHashList.h:1120
MapStruct< T_KEY, T_ITEM > Assoc
Definition: AkHashList.h:56
uintptr_t AkUIntPtr
Integer (unsigned) type for pointers.
Iterator End()
Definition: AkHashList.h:899
AkUInt32 AkHashType
Definition: AkHashList.h:38
void Term()
Definition: AkHashList.h:379
AkUInt32 Length() const
Definition: AkHashList.h:526
bool operator==(const Iterator &in_rOp) const
Definition: AkHashList.h:713
#define AkPlacementNew(_memory)
Definition: AkObject.h:49
bool operator!=(const ConstIterator &in_rOp) const
Definition: AkHashList.h:135
Iterator Begin()
Definition: AkHashList.h:803
T_ITEM * CreateEntry(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:632
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:822
Iterator Begin()
Definition: AkHashList.h:185
const AK_SELECTANY AkHashType kHashSizes[]
ConstIteratorEx & operator++()
Definition: AkHashList.h:786
ConstIterator End() const
Definition: AkHashList.h:286
void RemoveItem(AkHashType in_uiTable, T_MAPSTRUCT *in_pItem, T_MAPSTRUCT *in_pPrevItem)
Definition: AkHashList.h:1201
MapStruct< T_KEY, T_ITEM > * operator->() const
Definition: AkHashList.h:124
AkUInt32 HashSize() const
Definition: AkHashList.h:592
ConstIteratorEx & operator++()
Definition: AkHashList.h:168
T_MAPSTRUCT * Unset(const T_KEY &in_Key)
Definition: AkHashList.h:1076
#define AKASSERT(Condition)
Definition: AkAssert.h:67
ConstIteratorEx FindEx(T_KEY in_Key) const
Definition: AkHashList.h:944
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:913
T_ITEM * Set(Item *in_pItem)
Definition: AkHashList.h:415
IteratorEx & operator++()
Definition: AkHashList.h:765
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:1101
Iterator & operator++()
Definition: AkHashList.h:67
MapStruct< T_KEY, T_ITEM > & operator*()
Definition: AkHashList.h:78
bool operator==(const ConstIterator &in_rOp) const
Definition: AkHashList.h:753
ConstIterator Begin() const
Definition: AkHashList.h:826
T_MAPSTRUCT * operator->()
Definition: AkHashList.h:702
const MapStruct< T_KEY, T_ITEM > & operator*()
Definition: AkHashList.h:118
AkForceInline AkHashType AkHash(T_KEY in_key)
Definition: AkHashList.h:41
bool Set(T_MAPSTRUCT *in_pItem, bool &out_exists)
Definition: AkHashList.h:1035
void Transfer(AkArray< T, ARG_T, TAlloc, TGrowBy, TMovePolicy > &in_rSource)
Definition: AkArray.h:852
ConstIterator EndEx() const
Definition: AkHashList.h:300
T_MAPSTRUCT * operator*()
Definition: AkHashList.h:696
bool operator==(const ConstIterator &in_rOp) const
Definition: AkHashList.h:130
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:539
constexpr AkReal32 kHashTableGrowthFactor
Definition: AkHashList.h:46
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:531
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:344
void Transfer(AkHashList< T_KEY, T_ITEM, T_ALLOC > &in_source)
Definition: AkHashList.h:605
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:566
MapStruct< T_KEY, T_ITEM > * operator->()
Definition: AkHashList.h:84
bool Init(AkUInt32 in_iStartingSize)
Definition: AkHashList.h:986
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:1125
HashTableArray m_table
Definition: AkHashList.h:650
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:307
IteratorEx BeginEx()
Definition: AkHashList.h:231
AkUInt32 m_uiSize
Definition: AkHashList.h:1227
AkHashList< T_KEY, T_ITEM, T_ALLOC >::HashTableArray * pTable
Definition: AkHashList.h:63
bool GrowArray()
Definition: AkArray.h:772
bool operator==(const Iterator &in_rOp) const
Definition: AkHashList.h:90
AkForceInline T * AddLast()
Definition: AkArray.h:592
uint32_t AkUInt32
Unsigned 32-bit integer.
#define AK_SELECTANY
Definition: AkPlatforms.h:128
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:554
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:1133
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:708
T_MAPSTRUCT * Exists(T_KEY in_Key) const
Definition: AkHashList.h:1024
T_ITEM * Set(T_KEY in_Key)
Definition: AkHashList.h:436
const T_MAPSTRUCT * operator->() const
Definition: AkHashList.h:742
const T_MAPSTRUCT * operator*()
Definition: AkHashList.h:736
#define AkForceInline
Definition: AkTypes.h:63
T_ITEM * Set(T_KEY in_Key, bool &out_bWasAlreadyThere)
Definition: AkHashList.h:451
Item * pNextItem
Definition: AkHashList.h:55
static T_MAPSTRUCT *& Next(T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:661
ConstIterator Begin() const
Definition: AkHashList.h:208
ConstIteratorEx FindEx(T_KEY in_Key) const
Definition: AkHashList.h:338
bool CheckSize()
Definition: AkHashList.h:1192
static const T_KEY & Key(const T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:667
IteratorEx & operator++()
Definition: AkHashList.h:147
AkHashType HashSize() const
Definition: AkHashList.h:1186
bool CheckSize()
Definition: AkHashList.h:597
void Unset(T_KEY in_Key)
Definition: AkHashList.h:473
const AkHashList< T_KEY, T_ITEM, T_ALLOC >::HashTableArray * pTable
Definition: AkHashList.h:103

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