Version
menu_open
Wwise SDK 2024.1.4
IAkPluginHashTable.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) 2025 Audiokinetic Inc.
25 *******************************************************************************/
26 
27 /// \file
28 /// Plug-in interface for HashTable
29 
30 #pragma once
31 
32 #include <type_traits>
33 #include <AK/SoundEngine/Common/AkAudioObject.h>
34 #include <AK/SoundEngine/Common/AkHashTableTypes.h>
35 #include <AK/SoundEngine/Common/AkHashTableFuncs.h>
36 #include <AK/SoundEngine/Common/IAkPlugin.h>
37 #include <AK/Tools/Common/AkMurMurHash.h>
38 #include <AK/Tools/Common/AkPlacementNew.h>
39 
40 namespace AK
41 {
42 
43 /// Interface for an open-addressed hash table (or key-value array).
44 /// Relatively low-cost (O(1)) lookup, add, and removal by key. Typical use is to add values by key,
45 /// and then using GetFirstSlotByKey (and GetNextSlotByKey, if keys are not guaranteed to be unique)
46 /// to get a Slot into the AkHashTableBase, and then indexing AkHashTableBase::pValues by the provided Slot.
47 ///
48 /// Note that the AkHashTableBase referred to is not inherently thread-safe, so appropriate protections
49 /// will be required if the same hashTable is shared across multiple plug-in instances.
50 ///
51 /// Some hash functions are provided in AkMurMurHash.h which can be used for key generation.
52 /// In particular, this can be very useful for storing data on audio objects, or audio object channels,
53 /// over time. Note that if indexing by object-channel is desired, GetObjectChannelHash is recommended
54 /// to mitigate key-collisions from multiple channels of data. However, Audio Object IDs themselves are
55 /// chaotic enough that they can be used directly.
56 
57 class IAkPluginServiceHashTable : public IAkPluginService
58 {
59 protected:
60  virtual ~IAkPluginServiceHashTable() {}
61 public:
62 
63  // initializes and preallocates storage for specified number of entries
64  //
65  // returns either:
66  // AK_InsufficientMemory if a required allocation could not be made
67  // AK_Success if the hash table was initialized successfully
68  virtual AKRESULT InitBase(AK::AkHashTableBase<AkUInt64>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator,
69  AkUInt32 in_uInitialReserveCount, AkUInt32 in_uValueElementSize, AkUInt32 in_uValueElementAlign) = 0;
70 
71  // frees memory allocated for entries
72  virtual void Term(AkHashTableBase<AkUInt64>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator) = 0;
73 
74  // resets the table, clearing all keys and values to zero, but leaving the memory allocated
75  virtual void Reset(AkHashTableBase<AkUInt64>* io_pHashTable) = 0;
76 
77  // adds the provided key to the hash table
78  // and returns a pointer to the value made available, or nullptr if a grow occurred but memory could not be provided
79  // - keys can be added to the table multiple times
80  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
81  virtual void* AddKey(AkHashTableBase<AkUInt64>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator, AkUInt64 in_uKey) = 0;
82 
83  // removes the entry at the slot provided
84  // Returns true when a move of data around the end of the list occurred, e.g. in case iteration over the table needs to be modified
85  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
86  virtual bool RemoveSlot(AkHashTableBase<AkUInt64>* io_pHashTable, AkInt32 in_iSlot) = 0;
87 
88  // finds a slot with the provided key and deletes it from the table
89  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
90  virtual void RemoveKey(AkHashTableBase<AkUInt64>* io_pHashTable, AkUInt64 in_uKey) = 0;
91 
92  ///////////////////////////////////////////////////////////////////////////
93  // All virtual/interface specific functions should only be above this point.
94  // Inline/static helpers that call the interface functions, or other hashtable funcs are as follows:
95 
96  // returns either:
97  // the slot of the first valid entry that in_uKey maps to
98  // -1 if there are no valid entries at the table that uKey maps to
99  static AkInt32 GetFirstSlotByKey(AkHashTableBase<AkUInt64>* in_pHashTable, AkUInt64 in_uKey) {
100  return AK::HashTable::GetFirstSlotForKey(in_pHashTable, in_uKey);
101  }
102 
103  // returns either:
104  // the next slot after iPreviousSlot which contains a valid entry
105  // -1 if the next slot after iPreviousSlot doesn't contain a valid entry
106  static AkInt32 GetNextSlotByKey(AkHashTableBase<AkUInt64>* in_pHashTable, AkUInt64 in_uKey, AkInt32 in_iPreviousSlot) {
107  return AK::HashTable::GetNextSlotForKey(in_pHashTable, in_uKey, in_iPreviousSlot);
108  }
109 
110  // helper function for initialization of the hashtable against a specific value type
111  template<typename ValueType>
112  AkForceInline AKRESULT Init(AkHashTable<AkUInt64, ValueType>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator,
113  AkUInt32 in_uInitialReserveCount)
114  {
115  return InitBase(io_pHashTable, in_pAllocator, in_uInitialReserveCount, sizeof(ValueType), alignof(ValueType));
116  }
117 
118  // frees memory allocated for entries, and invokes the destructor for all value types along the way
119  template<typename KeyType, typename ValueType>
120  AkForceInline void TermValues(AkHashTable<KeyType, ValueType>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator)
121  {
122  if (!std::is_trivially_destructible<ValueType>::value)
123  {
124  AK::HashTable::ForEachSlot(io_pHashTable, [&](AkUInt32 uSlot)
125  {
126  (io_pHashTable->ValueAt(uSlot)).~ValueType();
127  });
128  }
129  Term((AkHashTableBase<KeyType>*)io_pHashTable, in_pAllocator);
130  }
131 
132  // adds the provided key to the hash table, performs default initialization of the table's valueType,
133  // and returns a pointer to the value made available, or nullptr if a grow occurred but memory could not be provided
134  // - keys can be added to the table multiple times
135  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
136  template<typename KeyType, typename ValueType>
137  AkForceInline void* AddKeyDefaultValue(AkHashTable<KeyType, ValueType>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator,
138  KeyType in_uKey)
139  {
140  if (ValueType* pInsertedValue = (ValueType*)AddKey(io_pHashTable, in_pAllocator, in_uKey))
141  {
142  AKASSERT(sizeof(ValueType) == io_pHashTable->uValueElementSize);
143  AkPlacementNew(pInsertedValue) (ValueType);
144  return pInsertedValue;
145  }
146  return nullptr;
147  }
148 
149  // adds the provided key to the hash table, copies the provided value into the newly allocated value,
150  // and returns a pointer to the value made available, or nullptr if a grow occurred but memory could not be provided
151  // - keys can be added to the table multiple times
152  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
153  template<typename ValueType>
154  AkForceInline ValueType* AddKeyValue(AkHashTable<AkUInt64, ValueType>* io_pHashTable, AK::IAkPluginMemAlloc* in_pAllocator,
155  AkUInt64 in_uKey, ValueType* in_pNewValue)
156  {
157  if (ValueType* pInsertedValue = (ValueType*)AddKey(io_pHashTable, in_pAllocator, in_uKey))
158  {
159  AKASSERT(sizeof(ValueType) == io_pHashTable->uValueElementSize);
160  AKPLATFORM::AkMemCpy(pInsertedValue, in_pNewValue, sizeof(ValueType));
161  return pInsertedValue;
162  }
163  return nullptr;
164  }
165 
166  // removes the entry at the slot provided, and performed destruction of the table's valuetype
167  // Returns true when a move of data around the end of the list occurred, e.g. in case iteration over the table needs to be modified
168  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
169  template<typename KeyType, typename ValueType>
170  AkForceInline bool RemoveSlotValue(AkHashTable<KeyType, ValueType>* io_pHashTable, AkInt32 in_iSlotToRemove)
171  {
172  io_pHashTable->ValueAt(in_iSlotToRemove).~ValueType();
173  return RemoveSlot(io_pHashTable, in_iSlotToRemove);
174  }
175 
176  // runs the provided function over every active slot in the hashtable, which is used to determine if the element should be removed
177  // For each element where this function returns true, it removes the entry at the slot provided
178  //
179  // in_func should be of type "bool functype(AkUInt32 in_slot)"
180  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
181  template<typename KeyType, typename FuncType>
182  AkForceInline void RemoveIf(AkHashTableBase<KeyType>* in_pHashTable, FuncType in_func)
183  {
184  AkUInt32 uSlotsToEvaluate = in_pHashTable->uNumUsedEntries;
185  bool* pbSlotOccupied = in_pHashTable->pbSlotOccupied;
186  AkUInt32 uSlot = 0;
187  while (uSlotsToEvaluate > 0)
188  {
189  AKASSERT(uSlot < in_pHashTable->uNumReservedEntries);
190  if (pbSlotOccupied[uSlot])
191  {
192  // run the provided func to determine if this slot should be removed
193  uSlotsToEvaluate--;
194  if (in_func(uSlot))
195  {
196  RemoveSlot(in_pHashTable, (AkInt32)uSlot);
197  continue; // don't advance uSlot; RemoveSlot moves data down
198  }
199  }
200  uSlot++;
201  }
202  }
203 
204  // runs the provided function over every active slot in the hashtable, which is used to determine if the element should be removed
205  // For each element where this function returns true, it removes the entry at the slot provided, and performs destruction of the table's valuetype
206  //
207  // in_func should be of type "bool functype(AkUInt32 in_slot)"
208  // - this function can move entries in the table around, so previous pointers to elements, etc, should be considered invalidated
209  template<typename KeyType, typename ValueType, typename FuncType>
210  AkForceInline void RemoveIfValue(AkHashTable<KeyType, ValueType>* in_pHashTable, FuncType in_func)
211  {
212  AkUInt32 uSlotsToEvaluate = in_pHashTable->uNumUsedEntries;
213  bool* pbSlotOccupied = in_pHashTable->pbSlotOccupied;
214  AkUInt32 uSlot = 0;
215  while (uSlotsToEvaluate > 0)
216  {
217  AKASSERT(uSlot < in_pHashTable->uNumReservedEntries);
218  if (pbSlotOccupied[uSlot])
219  {
220  // run the provided func to determine if this slot should be removed
221  uSlotsToEvaluate--;
222  if (in_func(uSlot))
223  {
224  RemoveSlotValue(in_pHashTable, (AkInt32)uSlot);
225  continue; // don't advance uSlot; RemoveSlot moves data down
226  }
227  }
228  uSlot++;
229  }
230  }
231 };
232 
233 #define AK_GET_PLUGIN_SERVICE_HASHTABLE(plugin_ctx) static_cast<AK::IAkPluginServiceHashTable*>(plugin_ctx->GetPluginService(AK::PluginServiceType_HashTable))
234 
235 /// A common hashtable for mapping audioobjectIds to a combination of audio buffers and objects
236 struct AkAudioObjectBuffer
237 {
238  AkAudioObjectBuffer() : pMetadata(nullptr) {}
239 
240  AkAudioBuffer pBuffer;
241  AkAudioObject* pMetadata;
242 };
243 typedef AK::AkHashTable<AkAudioObjectID, AkAudioObjectBuffer> AkAudioObjectBufferMap;
244 
245 /// Common hash function for getting a unique hash for a channel on an audio object
246 AkForceInline AkUInt64 GetObjectChannelHash(AkUInt64 in_uAudioObjectId, AkUInt32 in_uChannelIdx)
247 {
248  return AkHashMurMurMix64(((AkUInt64)in_uChannelIdx << AkAudioObject::kObjectKeyNumBits) | (in_uAudioObjectId & AkAudioObject::kObjectKeyMask));
249 }
250 
251 } // namespace AK
AK::GetObjectChannelHash
AkForceInline AkUInt64 GetObjectChannelHash(AkUInt64 in_uAudioObjectId, AkUInt32 in_uChannelIdx)
Common hash function for getting a unique hash for a channel on an audio object.
Definition: IAkPluginHashTable.h:246
AK::HashTable::ForEachSlot
void ForEachSlot(const AkHashTableBase< KeyType > *in_pHashTable, FuncType in_func)
Definition: AkHashTableFuncs.h:134
AK
Definition of data structures for AkAudioObject.
Definition: AkWwiseSDKVersion.cs:31
AK::IAkPluginServiceHashTable::GetNextSlotByKey
static AkInt32 GetNextSlotByKey(AkHashTableBase< AkUInt64 > *in_pHashTable, AkUInt64 in_uKey, AkInt32 in_iPreviousSlot)
Definition: IAkPluginHashTable.h:106
AkAudioObject::kObjectKeyNumBits
static const AkUInt64 kObjectKeyNumBits
Definition: AkAudioObject.h:62
AkPlacementNew
#define AkPlacementNew(_memory)
Definition: AkPlacementNew.h:48
AkAudioObject::kObjectKeyMask
static const AkUInt64 kObjectKeyMask
Definition: AkAudioObject.h:63
AK::IAkPluginServiceHashTable::RemoveSlot
virtual bool RemoveSlot(AkHashTableBase< AkUInt64 > *io_pHashTable, AkInt32 in_iSlot)=0
AKRESULT
AKRESULT
Standard function call result.
Definition: AkTypes.h:134
AK::HashTable::GetNextSlotForKey
AkInt32 GetNextSlotForKey(const AkHashTableBase< KeyType > *pHashTable, KeyType uKey, AkInt32 iPreviousSlot)
Definition: AkHashTableFuncs.h:104
AK::IAkPluginService
Common interface for plug-in services accessed through the global plug-in context.
Definition: IAkPlugin.h:1357
AK::IAkPluginServiceHashTable::RemoveIfValue
AkForceInline void RemoveIfValue(AkHashTable< KeyType, ValueType > *in_pHashTable, FuncType in_func)
Definition: IAkPluginHashTable.h:210
AK::IAkPluginServiceHashTable::InitBase
virtual AKRESULT InitBase(AK::AkHashTableBase< AkUInt64 > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator, AkUInt32 in_uInitialReserveCount, AkUInt32 in_uValueElementSize, AkUInt32 in_uValueElementAlign)=0
AkInt32
int32_t AkInt32
Signed 32-bit integer.
Definition: AkNumeralTypes.h:43
AK::IAkPluginServiceHashTable::AddKey
virtual void * AddKey(AkHashTableBase< AkUInt64 > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator, AkUInt64 in_uKey)=0
AK::AkAudioObjectBuffer
A common hashtable for mapping audioobjectIds to a combination of audio buffers and objects.
Definition: IAkPluginHashTable.h:237
AK::IAkPluginServiceHashTable::Term
virtual void Term(AkHashTableBase< AkUInt64 > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator)=0
AKASSERT
#define AKASSERT(Condition)
Definition: AkAssert.h:67
AKPLATFORM::AkMemCpy
AkForceInline void AkMemCpy(void *pDest, const void *pSrc, AkUInt32 uSize)
Platform Independent Helper for memcpy/memmove/memset.
Definition: AkPlatformFuncs.h:127
AK::AkAudioObjectBufferMap
AK::AkHashTable< AkAudioObjectID, AkAudioObjectBuffer > AkAudioObjectBufferMap
Definition: IAkPluginHashTable.h:243
AK::IAkPluginServiceHashTable::AddKeyDefaultValue
AkForceInline void * AddKeyDefaultValue(AkHashTable< KeyType, ValueType > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator, KeyType in_uKey)
Definition: IAkPluginHashTable.h:137
AK::IAkPluginServiceHashTable::TermValues
AkForceInline void TermValues(AkHashTable< KeyType, ValueType > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator)
Definition: IAkPluginHashTable.h:120
AK::IAkPluginServiceHashTable::RemoveIf
AkForceInline void RemoveIf(AkHashTableBase< KeyType > *in_pHashTable, FuncType in_func)
Definition: IAkPluginHashTable.h:182
AK::HashTable::GetFirstSlotForKey
AkInt32 GetFirstSlotForKey(const AkHashTableBase< KeyType > *pHashTable, KeyType uKey)
Definition: AkHashTableFuncs.h:91
AK::IAkPluginServiceHashTable::Reset
virtual void Reset(AkHashTableBase< AkUInt64 > *io_pHashTable)=0
AkUInt64
uint64_t AkUInt64
Unsigned 64-bit integer.
Definition: AkNumeralTypes.h:39
AK::IAkPluginServiceHashTable::RemoveSlotValue
AkForceInline bool RemoveSlotValue(AkHashTable< KeyType, ValueType > *io_pHashTable, AkInt32 in_iSlotToRemove)
Definition: IAkPluginHashTable.h:170
AK::IAkPluginServiceHashTable::Init
AkForceInline AKRESULT Init(AkHashTable< AkUInt64, ValueType > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator, AkUInt32 in_uInitialReserveCount)
Definition: IAkPluginHashTable.h:112
AkUInt32
uint32_t AkUInt32
Unsigned 32-bit integer.
Definition: AkNumeralTypes.h:38
AK::IAkPluginServiceHashTable::GetFirstSlotByKey
static AkInt32 GetFirstSlotByKey(AkHashTableBase< AkUInt64 > *in_pHashTable, AkUInt64 in_uKey)
Definition: IAkPluginHashTable.h:99
AK::AkHashTable::ValueAt
ValueType & ValueAt(AkUInt32 uSlot)
Definition: AkHashTableTypes.h:63
AK::IAkPluginServiceHashTable::RemoveKey
virtual void RemoveKey(AkHashTableBase< AkUInt64 > *io_pHashTable, AkUInt64 in_uKey)=0
AkForceInline
#define AkForceInline
Definition: AkTypes.h:63
AK::IAkPluginServiceHashTable::AddKeyValue
AkForceInline ValueType * AddKeyValue(AkHashTable< AkUInt64, ValueType > *io_pHashTable, AK::IAkPluginMemAlloc *in_pAllocator, AkUInt64 in_uKey, ValueType *in_pNewValue)
Definition: IAkPluginHashTable.h:154
AkHashMurMurMix64
AkForceInline AkUInt64 AkHashMurMurMix64(AkUInt64 uValue)
Definition: AkMurMurHash.h:50

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