Version
menu_open
Wwise SDK 2023.1.4
AkHashTableFuncs.h
Go to the documentation of this file.
1 /***********************************************************************
2  The content of this file includes source code for the sound engine
3  portion of the AUDIOKINETIC Wwise Technology and constitutes "Level
4  Two Source Code" as defined in the Source Code Addendum attached
5  with this file. Any use of the Level Two Source Code shall be
6  subject to the terms and conditions outlined in the Source Code
7  Addendum and the End User License Agreement for Wwise(R).
8 
9  Copyright (c) 2024 Audiokinetic Inc.
10  ***********************************************************************/
11 
12 #pragma once
13 
16 
17 // Inline-able functions for AK::HashTable
18 // Exposing enough functionality to be use by plug-in services and other things in non-header files
19 // For plug-ins, further functionality is provided by IAkPluginServiceHashTable
20 // For core soundengine execution, further functionality is provided in AkHashTable.h
21 namespace AK
22 {
23 
24 namespace HashTable
25 {
26 namespace Internal
27 {
28  template<typename KeyType>
29  inline AkInt32 IdealPos(KeyType uKey, AkInt32 iEntriesMask)
30  {
31  return AkInt32(uKey) & iEntriesMask;
32  }
33 
34  // returns how far away the current slot is from the key's ideal position
35  template<typename KeyType>
36  AkInt32 DistanceFromIdealPos(AkInt32 iSlot, KeyType uKey, AkInt32 iEntriesMask)
37  {
38  // subtraction against an unmasked key and then masking afterwards,
39  // will give same result as if we masked the slot and key individually, first
40  // (also wraparound of the slot relative to the ukey also washes away with the masking)
41  return (iSlot - AkInt32(uKey)) & iEntriesMask;
42  }
43 
44  // Internal helper function for AkHashTableBase; don't call this directly, use AK::HashTable::Get* functions instead
45  template<typename KeyType>
46  inline AkInt32 LinearProbe(const KeyType* pKeys, const bool* pbSlotOccupied, KeyType uKey, AkInt32 iSlot, AkUInt32 uNumEntries)
47  {
48  AkInt32 iDistFromBestSlot = 0;
49  AkInt32 iEntriesMask = (AkInt32)uNumEntries - 1;
50  for (; ; )
51  {
52  if (!pbSlotOccupied[iSlot])
53  return -1;
54  KeyType keyInSlot = pKeys[iSlot];
55  if (keyInSlot == uKey)
56  break;
57  if (iDistFromBestSlot > DistanceFromIdealPos(iSlot, keyInSlot, iEntriesMask))
58  return -1;
59  iSlot = (iSlot + 1) & iEntriesMask;
60  ++iDistFromBestSlot;
61  }
62  return iSlot;
63  }
64 
65  // Internal helper function for AkHashTableBase; don't call this directly, use AkHashTableGet* functions instead
66  inline AkInt32 OccupiedProbe(const bool* pbSlotOccupied, AkInt32 iSlot, AkInt32 iNumEntries)
67  {
68  while (iSlot < iNumEntries)
69  {
70  // 64-bit load to scan 8 pbSlotOccupieds at once
71  // (safe to load a bit past the end of slotOccupied region because we cap against iNumEntries anyway)
72  if (AkUInt64 slotOccCompressed = *((AkUInt64*)(pbSlotOccupied + iSlot)))
73  {
74  iSlot = iSlot + AKPLATFORM::AkBitScanForward64(slotOccCompressed) / 8;
75  iSlot = (iSlot >= iNumEntries) ? -1 : iSlot;
76  return iSlot;
77  }
78  else
79  {
80  iSlot += 8;
81  }
82  }
83  return -1;
84  }
85 } // namespace Internal
86 
87  // returns either:
88  // the slot of the first valid entry that uKey maps to
89  // -1 if there are no valid entries at the table that uKey maps to
90  template<typename KeyType>
91  inline AkInt32 GetFirstSlotForKey(const AkHashTableBase<KeyType>* pHashTable, KeyType uKey)
92  {
93  if (pHashTable->uNumReservedEntries == 0)
94  return -1;
95  AkUInt32 uNumEntries = pHashTable->uNumReservedEntries;
96  AkInt32 iBestSlot = uKey & (uNumEntries - 1);
97  return Internal::LinearProbe(pHashTable->pKeys, pHashTable->pbSlotOccupied, uKey, iBestSlot, uNumEntries);
98  }
99 
100  // returns either:
101  // the next slot after iPreviousIndex which contains a valid entry
102  // -1 if the next table after iPreviousIndex doesn't contain a valid entry
103  template<typename KeyType>
104  inline AkInt32 GetNextSlotForKey(const AkHashTableBase<KeyType>* pHashTable, KeyType uKey, AkInt32 iPreviousSlot)
105  {
106  if (pHashTable->uNumReservedEntries == 0)
107  return -1;
108  AkUInt32 uNumEntries = pHashTable->uNumReservedEntries;
109  AkInt32 iNextSlot = (iPreviousSlot + 1) & (uNumEntries - 1);
110  return Internal::LinearProbe(pHashTable->pKeys, pHashTable->pbSlotOccupied, uKey, iNextSlot, uNumEntries);
111  }
112 
113  // returns either:
114  // the slot of the first occupied entry in the hash table
115  // -1 if there are no occupied entries in the table
116  template<typename KeyType>
118  {
119  return Internal::OccupiedProbe(pHashTable->pbSlotOccupied, 0, (AkInt32)pHashTable->uNumReservedEntries);
120  }
121 
122  // returns either:
123  // the slot of the next occupied entry in the hash table (relative to iPreviousSlot)
124  // -1 if there are no occupied entries in the table after iPreviousSlot
125  template<typename KeyType>
126  inline AkInt32 GetNextActiveSlot(const AkHashTableBase<KeyType>* pHashTable, AkInt32 iPreviousSlot)
127  {
128  return Internal::OccupiedProbe(pHashTable->pbSlotOccupied, iPreviousSlot + 1, (AkInt32)pHashTable->uNumReservedEntries);
129  }
130 
131  // runs the provided function over every active slot in the hashtable
132  // functype(AkUInt32 in_slot)
133  template<typename KeyType, typename FuncType>
134  inline void ForEachSlot(const AkHashTableBase<KeyType>* in_pHashTable, FuncType in_func)
135  {
136  AkUInt32 uNumReservedEntries = in_pHashTable->uNumReservedEntries;
137  bool* pbSlotOccupied = in_pHashTable->pbSlotOccupied;
138  for (AkUInt32 uBaseSlot = 0; uBaseSlot < uNumReservedEntries; uBaseSlot += 8)
139  {
140  AkUInt64 slotOccMask = *(AkUInt64*)(pbSlotOccupied + uBaseSlot);
141  while (slotOccMask)
142  {
143  AkUInt32 slotSubIdx = AKPLATFORM::AkBitScanReverse64(slotOccMask);
144  in_func(uBaseSlot + 7 - (slotSubIdx / 8));
145  slotOccMask ^= (0x8000000000000000ULL >> slotSubIdx);
146  }
147  }
148  }
149 
150 } // namespace HashTable
151 } // namespace AK
void ForEachSlot(const AkHashTableBase< KeyType > *in_pHashTable, FuncType in_func)
Audiokinetic namespace.
AkForceInline AkUInt32 AkBitScanReverse64(AkUInt64 in_bits)
Definition: AkBitFuncs.h:133
AkInt32 GetNextSlotForKey(const AkHashTableBase< KeyType > *pHashTable, KeyType uKey, AkInt32 iPreviousSlot)
AkInt32 IdealPos(KeyType uKey, AkInt32 iEntriesMask)
AkForceInline AkUInt32 AkBitScanForward64(AkUInt64 in_bits)
Definition: AkBitFuncs.h:76
int32_t AkInt32
Signed 32-bit integer.
AkInt32 GetFirstActiveSlot(const AkHashTableBase< KeyType > *pHashTable)
AkInt32 LinearProbe(const KeyType *pKeys, const bool *pbSlotOccupied, KeyType uKey, AkInt32 iSlot, AkUInt32 uNumEntries)
AkInt32 GetFirstSlotForKey(const AkHashTableBase< KeyType > *pHashTable, KeyType uKey)
uint64_t AkUInt64
Unsigned 64-bit integer.
AkInt32 DistanceFromIdealPos(AkInt32 iSlot, KeyType uKey, AkInt32 iEntriesMask)
AkInt32 OccupiedProbe(const bool *pbSlotOccupied, AkInt32 iSlot, AkInt32 iNumEntries)
uint32_t AkUInt32
Unsigned 32-bit integer.
AkInt32 GetNextActiveSlot(const AkHashTableBase< KeyType > *pHashTable, AkInt32 iPreviousSlot)

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