29 #ifndef JUCE_HASHMAP_H_INCLUDED 30 #define JUCE_HASHMAP_H_INCLUDED 42 int generateHash (
const int key,
const int upperLimit)
const noexcept {
return std::abs (key) % upperLimit; }
94 template <
typename KeyType,
116 explicit HashMap (
int numberOfSlots = defaultHashTableSize,
117 HashFunctionType hashFunction = HashFunctionType())
118 : hashFunctionToUse (hashFunction), totalNumItems (0)
120 hashSlots.insertMultiple (0,
nullptr, numberOfSlots);
138 for (
int i = hashSlots.size(); --i >= 0;)
140 HashEntry* h = hashSlots.getUnchecked(i);
148 hashSlots.set (i,
nullptr);
158 return totalNumItems;
165 inline ValueType operator[] (KeyTypeParameter keyToLookFor)
const 169 for (
const HashEntry* entry = hashSlots.getUnchecked (generateHashFor (keyToLookFor)); entry !=
nullptr; entry = entry->nextEntry)
170 if (entry->key == keyToLookFor)
178 bool contains (KeyTypeParameter keyToLookFor)
const 182 for (
const HashEntry* entry = hashSlots.getUnchecked (generateHashFor (keyToLookFor)); entry !=
nullptr; entry = entry->nextEntry)
183 if (entry->key == keyToLookFor)
194 for (
int i = getNumSlots(); --i >= 0;)
195 for (
const HashEntry* entry = hashSlots.getUnchecked(i); entry !=
nullptr; entry = entry->nextEntry)
196 if (entry->value == valueToLookFor)
207 void set (KeyTypeParameter newKey, ValueTypeParameter newValue)
210 const int hashIndex = generateHashFor (newKey);
212 HashEntry*
const firstEntry = hashSlots.getUnchecked (hashIndex);
214 for (HashEntry* entry = firstEntry; entry !=
nullptr; entry = entry->nextEntry)
216 if (entry->key == newKey)
218 entry->value = newValue;
223 hashSlots.set (hashIndex,
new HashEntry (newKey, newValue, firstEntry));
226 if (totalNumItems > (getNumSlots() * 3) / 2)
227 remapTable (getNumSlots() * 2);
231 void remove (KeyTypeParameter keyToRemove)
234 const int hashIndex = generateHashFor (keyToRemove);
235 HashEntry* entry = hashSlots.getUnchecked (hashIndex);
236 HashEntry* previous =
nullptr;
238 while (entry !=
nullptr)
240 if (entry->key == keyToRemove)
244 entry = entry->nextEntry;
246 if (previous !=
nullptr)
247 previous->nextEntry = entry;
249 hashSlots.set (hashIndex, entry);
256 entry = entry->nextEntry;
266 for (
int i = getNumSlots(); --i >= 0;)
268 HashEntry* entry = hashSlots.getUnchecked(i);
269 HashEntry* previous =
nullptr;
271 while (entry !=
nullptr)
273 if (entry->value == valueToRemove)
277 entry = entry->nextEntry;
279 if (previous !=
nullptr)
280 previous->nextEntry = entry;
282 hashSlots.set (i, entry);
289 entry = entry->nextEntry;
301 HashMap newTable (newNumberOfSlots);
303 for (
int i = getNumSlots(); --i >= 0;)
304 for (
const HashEntry* entry = hashSlots.getUnchecked(i); entry !=
nullptr; entry = entry->nextEntry)
305 newTable.
set (entry->key, entry->value);
316 return hashSlots.size();
321 template <
class OtherHashMapType>
325 const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
327 hashSlots.swapWith (otherHashMap.hashSlots);
328 std::swap (totalNumItems, otherHashMap.totalNumItems);
346 HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry*
const next)
347 : key (k), value (val), nextEntry (next)
352 HashEntry* nextEntry;
386 : hashMap (hashMapToIterate), entry (
nullptr), index (0)
395 if (entry !=
nullptr)
396 entry = entry->nextEntry;
398 while (entry ==
nullptr)
400 if (index >= hashMap.getNumSlots())
403 entry = hashMap.hashSlots.getUnchecked (index++);
414 return entry !=
nullptr ? entry->key : KeyType();
422 return entry !=
nullptr ? entry->value : ValueType();
436 enum { defaultHashTableSize = 101 };
439 HashFunctionType hashFunctionToUse;
442 TypeOfCriticalSectionToUse lock;
444 int generateHashFor (KeyTypeParameter key)
const 446 const int hash = hashFunctionToUse.
generateHash (key, getNumSlots());
455 #endif // JUCE_HASHMAP_H_INCLUDED int generateHash(const int64 key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:44
ValueType getValue() const
Definition: juce_HashMap.h:420
Definition: juce_Variant.h:46
Definition: juce_HashMap.h:98
#define noexcept
Definition: juce_CompilerSupport.h:141
int size() const noexcept
Definition: juce_HashMap.h:156
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition: juce_HashMap.h:336
bool isPositiveAndBelow(Type valueToTest, Type upperLimit) noexcept
Definition: juce_core.h:238
bool next()
Definition: juce_HashMap.h:393
bool contains(KeyTypeParameter keyToLookFor) const
Definition: juce_HashMap.h:178
void remapTable(int newNumberOfSlots)
Definition: juce_HashMap.h:299
Definition: juce_String.h:43
Definition: juce_HashMap.h:39
Iterator(const HashMap &hashMapToIterate)
Definition: juce_HashMap.h:385
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Definition: juce_HashMap.h:207
unsigned int uint32
Definition: juce_MathsFunctions.h:51
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Definition: juce_HashMap.h:116
Definition: juce_ScopedPointer.h:70
long long int64
Definition: juce_MathsFunctions.h:60
int getNumSlots() const noexcept
Definition: juce_HashMap.h:314
Definition: juce_Array.h:60
int generateHash(const int key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:42
void removeValue(ValueTypeParameter valueToRemove)
Definition: juce_HashMap.h:262
void swapWith(OtherHashMapType &otherHashMap) noexcept
Definition: juce_HashMap.h:322
#define nullptr
Definition: juce_CompilerSupport.h:151
TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Definition: juce_HashMap.h:339
void clear()
Definition: juce_HashMap.h:134
Definition: juce_CriticalSection.h:136
Definition: juce_HashMap.h:381
bool containsValue(ValueTypeParameter valueToLookFor) const
Definition: juce_HashMap.h:190
#define PARAMETER_TYPE(a)
int generateHash(const var &key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:48
~HashMap()
Definition: juce_HashMap.h:124
KeyType getKey() const
Definition: juce_HashMap.h:412
int generateHash(const String &key, const int upperLimit) const noexcept
Definition: juce_HashMap.h:46