Version
menu_open
link
Wwise SDK 2019.1.11
AkHashList.h
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: <VERSION> Build: <BUILDNUMBER>
25  Copyright (c) <COPYRIGHTYEAR> 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 
61 
62  struct Iterator
63  {
65  AkHashType uiTable;
67 
68  inline Iterator& operator++()
69  {
70  AKASSERT( pItem );
72 
73  while ( ( pItem == NULL ) && ( ++uiTable < pTable->Length() ) )
74  pItem = (*pTable)[ uiTable ];
75 
76  return *this;
77  }
78 
80  {
81  AKASSERT( pItem );
82  return pItem->Assoc;
83  }
84 
85  bool operator !=( const Iterator& in_rOp ) const
86  {
87  return ( pItem != in_rOp.pItem );
88  }
89  };
90 
91  // The IteratorEx iterator is intended for usage when a possible erase may occurs
92  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
93  struct IteratorEx : public Iterator
94  {
96 
98  {
99  AKASSERT( this->pItem );
100 
101  pPrevItem = this->pItem;
102  this->pItem = this->pItem->pNextItem;
103 
104  while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
105  {
106  pPrevItem = NULL;
107  this->pItem = (*this->pTable)[ this->uiTable ];
108  }
109 
110  return *this;
111  }
112  };
113 
114  Iterator Begin()
115  {
116  Iterator returnedIt;
117 
118  if (HashSize() > 0)
119  {
120  returnedIt.pTable = &m_table;
121  returnedIt.uiTable = 0;
122  returnedIt.pItem = m_table[0];
123 
124  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
125  returnedIt.pItem = m_table[returnedIt.uiTable];
126  }
127  else
128  {
129  returnedIt.pTable = NULL;
130  returnedIt.uiTable = 0;
131  returnedIt.pItem = NULL;
132  }
133 
134  return returnedIt;
135  }
136 
137  IteratorEx BeginEx()
138  {
139  IteratorEx returnedIt;
140 
141  if (HashSize() > 0)
142  {
143  returnedIt.pTable = &m_table;
144  returnedIt.uiTable = 0;
145  returnedIt.pItem = *(m_table.Begin());
146  returnedIt.pPrevItem = NULL;
147 
148  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
149  returnedIt.pItem = m_table[returnedIt.uiTable];
150  }
151  else
152  {
153  returnedIt.pTable = NULL;
154  returnedIt.uiTable = 0;
155  returnedIt.pItem = NULL;
156  }
157 
158  return returnedIt;
159  }
160 
161  inline Iterator End()
162  {
163  Iterator returnedIt;
164  returnedIt.pItem = NULL;
165  return returnedIt;
166  }
167 
168  IteratorEx FindEx( T_KEY in_Key )
169  {
170  IteratorEx returnedIt;
171 
172  if (HashSize() > 0)
173  {
174  returnedIt.pTable = &m_table;
175  returnedIt.uiTable = AkHash(in_Key) % HashSize();
176  returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
177  returnedIt.pPrevItem = NULL;
178 
179  while (returnedIt.pItem != NULL)
180  {
181  if (returnedIt.pItem->Assoc.key == in_Key)
182  break;
183 
184  returnedIt.pPrevItem = returnedIt.pItem;
185  returnedIt.pItem = returnedIt.pItem->pNextItem;
186  }
187  }
188  else
189  {
190  returnedIt.pTable = NULL;
191  returnedIt.uiTable = 0;
192  returnedIt.pItem = NULL;
193  returnedIt.pPrevItem = NULL;
194  }
195 
196  return returnedIt;
197  }
198 
200  {
201  }
202 
204  {
205  AKASSERT(m_uiSize == 0);
206  m_table.Term();
207  }
208 
209  void Term()
210  {
211  RemoveAll();
212  m_table.Term();
213  }
214 
215  void RemoveAll()
216  {
217  for (AkHashType i = 0; i < HashSize(); ++i)
218  {
219  Item * pItem = m_table[ i ];
220  while ( pItem != NULL )
221  {
222  Item * pNextItem = pItem->pNextItem;
223  pItem->Assoc.item.~T_ITEM();
224  T_ALLOC::Free( pItem );
225  pItem = pNextItem;
226  }
227 
228  m_table[ i ] = NULL;
229  }
230 
231  m_uiSize = 0;
232  }
233 
234  T_ITEM * Exists( T_KEY in_Key )
235  {
236  if (HashSize() > 0)
237  {
238  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
239  return ExistsInList(in_Key, uiTable);
240  }
241  return NULL;
242  }
243 
244  // Set using an externally preallocated Item -- Hash list takes ownership of the Item.
245  T_ITEM * Set( Item * in_pItem )
246  {
247  if (CheckSize())
248  {
249  AkHashType uiTable = AkHash(in_pItem->Assoc.key) % HashSize();
250 
251  AKASSERT(!ExistsInList(in_pItem->Assoc.key, uiTable)); // Item must not exist in list !
252 
253  // Add new entry
254 
255  in_pItem->pNextItem = m_table[uiTable];
256  m_table[uiTable] = in_pItem;
257 
258  ++m_uiSize;
259 
260  return &(in_pItem->Assoc.item);
261  }
262 
263  return NULL;
264  }
265 
266  T_ITEM * Set( T_KEY in_Key )
267  {
268  if ( CheckSize() )
269  {
270  AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
271  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
272  if (pItem)
273  return pItem;
274 
275  return CreateEntry(in_Key, uiTable);
276  }
277 
278  return NULL;
279  }
280 
281  T_ITEM * Set( T_KEY in_Key, bool& out_bWasAlreadyThere )
282  {
283  if (CheckSize())
284  {
285  AkHashType uiTable = AkHash(in_Key) % HashSize();
286  T_ITEM * pItem = ExistsInList(in_Key, uiTable);
287  if (pItem)
288  {
289  out_bWasAlreadyThere = true;
290  return pItem;
291  }
292  else
293  {
294  out_bWasAlreadyThere = false;
295  }
296 
297  return CreateEntry(in_Key, uiTable);
298  }
299 
300  return NULL;
301  }
302 
303  void Unset( T_KEY in_Key )
304  {
305  if (HashSize() > 0)
306  {
307  AkHashType uiTable = AkHash(in_Key) % HashSize();
308  Item * pItem = m_table[uiTable];
309  Item * pPrevItem = NULL;
310  while (pItem != NULL)
311  {
312  if (pItem->Assoc.key == in_Key)
313  break;
314 
315  pPrevItem = pItem;
316  pItem = pItem->pNextItem;
317  }
318 
319  if (pItem)
320  RemoveItem(uiTable, pItem, pPrevItem);
321  }
322  }
323 
324  IteratorEx Erase( const IteratorEx& in_rIter )
325  {
326  IteratorEx returnedIt;
327  returnedIt.pTable = in_rIter.pTable;
328  returnedIt.uiTable = in_rIter.uiTable;
329  returnedIt.pItem = in_rIter.pItem->pNextItem;
330  returnedIt.pPrevItem = in_rIter.pPrevItem;
331 
332  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
333  {
334  returnedIt.pPrevItem = NULL;
335  returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
336  }
337 
338  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
339 
340  return returnedIt;
341  }
342 
343  void RemoveItem( AkHashType in_uiTable, Item* in_pItem, Item* in_pPrevItem )
344  {
345  if( in_pPrevItem )
346  in_pPrevItem->pNextItem = in_pItem->pNextItem;
347  else
348  m_table[ in_uiTable ] = in_pItem->pNextItem;
349 
350  in_pItem->Assoc.item.~T_ITEM();
351  T_ALLOC::Free(in_pItem);
352 
353  --m_uiSize;
354  }
355 
356  AkUInt32 Length() const
357  {
358  return m_uiSize;
359  }
360 
361  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
362  {
363  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
364  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
365 
366  return AK_Success;
367  }
368 
369  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
370  {
371  AKRESULT res = AK_Fail;
372 
373  AkUInt32 uNewSize = 0;
374  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
375  {
376  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
377  {
378  uNewSize = kHashSizes[i];
379  break;
380  }
381  }
382 
383  if (uNewSize > 0)
384  {
385  HashTableArray oldArray;
386  oldArray.Transfer(m_table);
387 
388  if ( m_table.GrowArray(uNewSize) )
389  {
390  for (AkUInt32 i = 0; i < uNewSize; i++)
391  m_table.AddLast(NULL);
392 
393  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
394  {
395  Item * pItem = oldArray[i];
396  while (pItem != NULL)
397  {
398  Item * pNextItem = pItem->pNextItem;
399  {
400  AkHashType uiTable = AkHash(pItem->Assoc.key) % HashSize();
401  pItem->pNextItem = m_table[uiTable];
402  m_table[uiTable] = pItem;
403  }
404  pItem = pNextItem;
405  }
406  }
407 
408  oldArray.Term();
409 
410  res = AK_Success;
411  }
412  else
413  {
414  //Backpedal..
415  m_table.Transfer(oldArray);
416  }
417  }
418 
419  return res;
420  }
421 
422  inline AkUInt32 HashSize() const
423  {
424  return m_table.Length();
425  }
426 
427  inline bool CheckSize()
428  {
429  if ( HashSize() == 0 || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
430  Resize(HashSize());
431 
432  return (HashSize() > 0);
433  }
434 
435 protected:
436  T_ITEM * ExistsInList( T_KEY in_Key, AkUIntPtr in_uiTable )
437  {
438  AKASSERT(HashSize() > 0);
439 
440  Item * pItem = m_table[(AkUInt32)in_uiTable];
441  while (pItem != NULL)
442  {
443  if (pItem->Assoc.key == in_Key)
444  return &(pItem->Assoc.item); // found
445 
446  pItem = pItem->pNextItem;
447  }
448 
449  return NULL; // not found
450  }
451 
452  T_ITEM * CreateEntry( T_KEY in_Key, AkUIntPtr in_uiTable )
453  {
454  Item * pNewItem = (Item *)T_ALLOC::Alloc(sizeof(Item));
455  if ( pNewItem == NULL )
456  return NULL;
457 
458  pNewItem->pNextItem = m_table[ (AkUInt32)in_uiTable ];
459  pNewItem->Assoc.key = in_Key;
460 
461  AkPlacementNew( &(pNewItem->Assoc.item) ) T_ITEM;
462 
463  m_table[(AkUInt32)in_uiTable] = pNewItem;
464 
465  ++m_uiSize;
466 
467  return &(pNewItem->Assoc.item);
468  }
469 
471  AkUInt32 m_uiSize;
472 };
473 
474 // this one lets you define the structure
475 // only requirement is that T_MAPSTRUCT must have members pNextItem and key.
476 // client is responsible for allocation/deallocation of T_MAPSTRUCTS.
477 template <class T_KEY, class T_MAPSTRUCT>
479 {
480  static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) {return in_pItem->key;}
481 };
482 
483 template < class T_KEY, class T_MAPSTRUCT, typename T_ALLOC = ArrayPoolDefault, class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT> >
485 {
487 public:
488  struct Iterator
489  {
491  AkHashType uiTable;
492  T_MAPSTRUCT* pItem;
493 
495  {
496  AKASSERT( pItem );
497  pItem = pItem->pNextItem;
498 
499  while ((pItem == NULL) && (++uiTable < pTable->Length()))
500  pItem = (*pTable)[ uiTable ];
501 
502  return *this;
503  }
504 
505  inline T_MAPSTRUCT * operator*()
506  {
507  AKASSERT( pItem );
508  return pItem;
509  }
510 
511  bool operator !=( const Iterator& in_rOp ) const
512  {
513  return ( pItem != in_rOp.pItem );
514  }
515  };
516 
517  // The IteratorEx iterator is intended for usage when a possible erase may occurs
518  // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
519  struct IteratorEx : public Iterator
520  {
521  T_MAPSTRUCT* pPrevItem;
522 
524  {
525  AKASSERT( this->pItem );
526 
527  pPrevItem = this->pItem;
528  this->pItem = this->pItem->pNextItem;
529 
530  while ( ( this->pItem == NULL ) && ( ++this->uiTable < this->pTable->Length() ) )
531  {
532  pPrevItem = NULL;
533  this->pItem = (*this->pTable)[ this->uiTable ];
534  }
535 
536  return *this;
537  }
538  };
539 
541  {
542  Iterator returnedIt;
543 
544  if (HashSize() > 0)
545  {
546  returnedIt.pTable = &m_table;
547  returnedIt.uiTable = 0;
548  returnedIt.pItem = m_table[0];
549 
550  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
551  returnedIt.pItem = m_table[returnedIt.uiTable];
552  }
553  else
554  {
555  returnedIt.pTable = NULL;
556  returnedIt.uiTable = 0;
557  returnedIt.pItem = NULL;
558  }
559 
560  return returnedIt;
561  }
562 
564  {
565  IteratorEx returnedIt;
566 
567  if (HashSize() > 0)
568  {
569  returnedIt.pTable = &m_table;
570  returnedIt.uiTable = 0;
571  returnedIt.pItem = m_table[0];
572  returnedIt.pPrevItem = NULL;
573 
574  while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
575  returnedIt.pItem = m_table[ returnedIt.uiTable ];
576  }
577  else
578  {
579  returnedIt.pTable = NULL;
580  returnedIt.uiTable = 0;
581  returnedIt.pItem = NULL;
582  }
583 
584  return returnedIt;
585  }
586 
587  inline Iterator End()
588  {
589  Iterator returnedIt;
590  returnedIt.pItem = NULL;
591  return returnedIt;
592  }
593 
594  IteratorEx FindEx( T_KEY in_Key )
595  {
596  IteratorEx returnedIt;
597 
598  if (HashSize() > 0)
599  {
600  returnedIt.pTable = &m_table;
601  returnedIt.uiTable = AkHash(in_Key) % HashSize();
602  returnedIt.pItem = m_table[returnedIt.uiTable];
603  returnedIt.pPrevItem = NULL;
604 
605  while (returnedIt.pItem != NULL)
606  {
607  if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
608  break;
609 
610  returnedIt.pPrevItem = returnedIt.pItem;
611  returnedIt.pItem = returnedIt.pItem->pNextItem;
612  }
613  }
614  else
615  {
616  returnedIt.pTable = NULL;
617  returnedIt.uiTable = 0;
618  returnedIt.pItem = NULL;
619  returnedIt.pPrevItem = NULL;
620  }
621 
622  return returnedIt;
623  }
624 
626  : m_uiSize( 0 )
627  {
628  }
629 
631  {
632  }
633 
634  //If you set 0 as the starting size, you *must* check all returns of Set() calls.
635  //If you initialize with anything else, you can ignore return codes of Set(), they will always succeed.
636  bool Init(AkUInt32 in_iStartingSize)
637  {
638  m_uiSize = 0;
639 
640  if(!m_table.Resize(in_iStartingSize))
641  return false;
642 
643  for ( AkHashType i = 0; i < HashSize(); ++i )
644  m_table[ i ] = NULL;
645 
646  return true;
647  }
648 
649  void Term()
650  {
651  AKASSERT( m_uiSize == 0 );
652  m_table.Term();
653  }
654 /*
655  void RemoveAll()
656  {
657  for ( AkHashType i = 0; i < HashSize(); ++i )
658  {
659  T_MAPSTRUCT * pItem = m_table[ i ];
660  while ( pItem != NULL )
661  {
662  T_MAPSTRUCT * pNextItem = pItem->pNextItem;
663  pItem->~T_MAPSTRUCT();
664  T_ALLOD::Free( pItem );
665  pItem = pNextItem;
666  }
667 
668  m_table[ i ] = NULL;
669  }
670 
671  m_uiSize = 0;
672  }
673 */
674  T_MAPSTRUCT * Exists( T_KEY in_Key ) const
675  {
676  if (HashSize() > 0)
677  {
678  AkHashType uiTable = AkHash(in_Key) % HashSize();
679  return ExistsInList(in_Key, uiTable);
680  }
681  return NULL;
682  }
683 
684  // Set using an externally preallocated T_MAPSTRUCT -- Hash list takes ownership of the T_MAPSTRUCT.
685  bool Set( T_MAPSTRUCT * in_pItem )
686  {
687  if (CheckSize())
688  {
689  AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
690  AKASSERT(!ExistsInList(KEY_POLICY::Key(in_pItem), uiTable)); // T_MAPSTRUCT must not exist in list !
691 
692  // Add new entry
693 
694  in_pItem->pNextItem = m_table[uiTable];
695  m_table[uiTable] = in_pItem;
696 
697  ++m_uiSize;
698  return true;
699  }
700  //This can only happen if the initial size of the map was 0.
701  return false;
702  }
703 
704  T_MAPSTRUCT * Unset( const T_KEY &in_Key )
705  {
706  T_MAPSTRUCT * pItem = NULL;
707 
708  if (HashSize() > 0)
709  {
710  AkHashType uiTable = AkHash(in_Key) % HashSize();
711  pItem = m_table[uiTable];
712  T_MAPSTRUCT * pPrevItem = NULL;
713  while (pItem != NULL)
714  {
715  if (KEY_POLICY::Key(pItem) == in_Key)
716  break;
717 
718  pPrevItem = pItem;
719  pItem = pItem->pNextItem;
720  }
721 
722  if (pItem)
723  RemoveItem(uiTable, pItem, pPrevItem);
724  }
725 
726  return pItem;
727  }
728 
729  IteratorEx Erase( const IteratorEx& in_rIter )
730  {
731  IteratorEx returnedIt;
732  returnedIt.pTable = in_rIter.pTable;
733  returnedIt.uiTable = in_rIter.uiTable;
734  returnedIt.pItem = in_rIter.pItem->pNextItem;
735  returnedIt.pPrevItem = in_rIter.pPrevItem;
736 
737  while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
738  {
739  returnedIt.pPrevItem = NULL;
740  returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
741  }
742 
743  RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
744 
745  return returnedIt;
746  }
747 
748  AkUInt32 Length() const
749  {
750  return m_uiSize;
751  }
752 
753  AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
754  {
755  if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
756  return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
757 
758  return AK_Success;
759  }
760 
761  AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
762  {
763  AKRESULT res = AK_Fail;
764 
765  AkHashType uNewSize = 0;
766  for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
767  {
768  if (kHashSizes[i] > in_uExpectedNumberOfEntires)
769  {
770  uNewSize = kHashSizes[i];
771  break;
772  }
773  }
774 
775  if (uNewSize > 0)
776  {
777  HashTableArray oldArray;
778  oldArray.Transfer(m_table);
779 
780  if (m_table.GrowArray(uNewSize))
781  {
782  for (AkUInt32 i = 0; i < uNewSize; i++)
783  m_table.AddLast(NULL);
784 
785  for (AkUInt32 i = 0; i < oldArray.Length(); i++)
786  {
787  T_MAPSTRUCT* pItem = oldArray[i];
788  while (pItem != NULL)
789  {
790  T_MAPSTRUCT* pNextItem = pItem->pNextItem;
791  {
792  AkHashType uiTable = AkHash(KEY_POLICY::Key(pItem)) % uNewSize;
793  pItem->pNextItem = m_table[uiTable];
794  m_table[uiTable] = pItem;
795  }
796  pItem = pNextItem;
797  }
798  }
799 
800  oldArray.Term();
801 
802  res = AK_Success;
803  }
804  else
805  {
806  //Backpedal..
807  m_table.Transfer(oldArray);
808  }
809  }
810 
811  return res;
812  }
813 
814  inline AkHashType HashSize() const
815  {
816  return m_table.Length();
817  }
818 
819 
820  inline bool CheckSize()
821  {
822  if ( (HashSize() == 0) || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
823  Resize(HashSize());
824 
825  return (HashSize() > 0);
826  }
827 
828 protected:
829  void RemoveItem( AkHashType in_uiTable, T_MAPSTRUCT* in_pItem, T_MAPSTRUCT* in_pPrevItem )
830  {
831  if( in_pPrevItem )
832  in_pPrevItem->pNextItem = in_pItem->pNextItem;
833  else
834  m_table[ in_uiTable ] = in_pItem->pNextItem;
835 
836  --m_uiSize;
837  }
838 
839  T_MAPSTRUCT * ExistsInList( T_KEY in_Key, AkHashType in_uiTable ) const
840  {
841  T_MAPSTRUCT * pItem = m_table[in_uiTable];
842  while (pItem != NULL)
843  {
844  if (KEY_POLICY::Key(pItem) == in_Key)
845  return pItem; // found
846 
847  pItem = pItem->pNextItem;
848  }
849 
850  return NULL; // not found
851  }
852 
854 
855  AkUInt32 m_uiSize;
856 };
857 
858 
859 #endif // _AKHASHLIST_H
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:753
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:761
T_ITEM * ExistsInList(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:436
Iterator End()
Definition: AkHashList.h:161
AkUInt32 m_uiSize
Definition: AkHashList.h:471
AkUInt32 m_uiSize
Definition: AkHashList.h:855
HashTableArray m_table
Definition: AkHashList.h:853
AkHashListBare< T_KEY, T_MAPSTRUCT, T_ALLOC, KEY_POLICY >::HashTableArray * pTable
Definition: AkHashList.h:490
IteratorEx BeginEx()
Definition: AkHashList.h:563
Iterator Begin()
Definition: AkHashList.h:540
T_MAPSTRUCT * pPrevItem
Definition: AkHashList.h:521
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:85
static const T_KEY & Key(const T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:480
void RemoveAll()
Definition: AkHashList.h:215
AkHashType uiTable
Definition: AkHashList.h:65
bool operator!=(const Iterator &in_rOp) const
Definition: AkHashList.h:511
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:594
Iterator & operator++()
Definition: AkHashList.h:494
T_ITEM * Exists(T_KEY in_Key)
Definition: AkHashList.h:234
Specific implementation of array.
Definition: AkArray.h:190
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:324
bool CheckSize()
Definition: AkHashList.h:820
bool Set(T_MAPSTRUCT *in_pItem)
Definition: AkHashList.h:685
void RemoveItem(AkHashType in_uiTable, Item *in_pItem, Item *in_pPrevItem)
Definition: AkHashList.h:343
IteratorEx & operator++()
Definition: AkHashList.h:523
MapStruct< T_KEY, T_ITEM > Assoc
Definition: AkHashList.h:57
void Term()
Definition: AkHashList.h:209
AkUInt32 Length() const
Definition: AkHashList.h:356
Definition: AkKeyDef.h:35
AkHashType HashSize() const
Definition: AkHashList.h:814
T_ITEM * CreateEntry(T_KEY in_Key, AkUIntPtr in_uiTable)
Definition: AkHashList.h:452
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:629
Iterator Begin()
Definition: AkHashList.h:114
AkHashList()
Definition: AkHashList.h:199
AkUInt32 Length() const
Definition: AkHashList.h:748
AkUInt32 HashSize() const
Definition: AkHashList.h:422
T_MAPSTRUCT * Exists(T_KEY in_Key) const
Definition: AkHashList.h:674
AkHashListBare()
Definition: AkHashList.h:625
T_ITEM * Set(Item *in_pItem)
Definition: AkHashList.h:245
Iterator & operator++()
Definition: AkHashList.h:68
~AkHashList()
Definition: AkHashList.h:203
MapStruct< T_KEY, T_ITEM > & operator*()
Definition: AkHashList.h:79
bool Init(AkUInt32 in_iStartingSize)
Definition: AkHashList.h:636
bool GrowArray(AkUInt32 in_uGrowBy=TGrowBy)
Resize the array.
Definition: AkArray.h:588
AkArray< Item *, Item *, T_ALLOC, 0 > HashTableArray
Definition: AkHashList.h:60
Item * pItem
Definition: AkHashList.h:66
void Transfer(AkArray< T, ARG_T, TAlloc, TGrowBy, TMovePolicy > &in_rSource)
Definition: AkArray.h:659
AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
Definition: AkHashList.h:369
AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
Definition: AkHashList.h:361
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:270
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:422
HashTableArray m_table
Definition: AkHashList.h:470
IteratorEx FindEx(T_KEY in_Key)
Definition: AkHashList.h:168
IteratorEx BeginEx()
Definition: AkHashList.h:137
AkHashList< T_KEY, T_ITEM, T_ALLOC >::HashTableArray * pTable
Definition: AkHashList.h:64
Iterator End()
Definition: AkHashList.h:587
AkForceInline T * AddLast()
Definition: AkArray.h:448
T_MAPSTRUCT * Unset(const T_KEY &in_Key)
Definition: AkHashList.h:704
void RemoveItem(AkHashType in_uiTable, T_MAPSTRUCT *in_pItem, T_MAPSTRUCT *in_pPrevItem)
Definition: AkHashList.h:829
T_MAPSTRUCT * pItem
Definition: AkHashList.h:492
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:410
void Term()
Definition: AkHashList.h:649
T_ITEM * Set(T_KEY in_Key)
Definition: AkHashList.h:266
IteratorEx Erase(const IteratorEx &in_rIter)
Definition: AkHashList.h:729
T_MAPSTRUCT * ExistsInList(T_KEY in_Key, AkHashType in_uiTable) const
Definition: AkHashList.h:839
AkHashType uiTable
Definition: AkHashList.h:491
T_ITEM * Set(T_KEY in_Key, bool &out_bWasAlreadyThere)
Definition: AkHashList.h:281
T_MAPSTRUCT * operator*()
Definition: AkHashList.h:505
Item * pNextItem
Definition: AkHashList.h:56
~AkHashListBare()
Definition: AkHashList.h:630
IteratorEx & operator++()
Definition: AkHashList.h:97
Item * pPrevItem
Definition: AkHashList.h:95
bool CheckSize()
Definition: AkHashList.h:427
void Unset(T_KEY in_Key)
Definition: AkHashList.h:303

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