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