37 static int generateHash (uint32 key,
int upperLimit)
noexcept {
return (
int) (key % (uint32) upperLimit); }
41 static int generateHash (uint64 key,
int upperLimit)
noexcept {
return (
int) (key % (uint64) upperLimit); }
49 static int generateHash (
const void* key,
int upperLimit)
noexcept {
return generateHash ((uint64) (pointer_sized_uint) key, upperLimit); }
99template <
typename KeyType,
101 class HashFunctionType = DefaultHashFunctions,
102 class TypeOfCriticalSectionToUse = DummyCriticalSection>
106 using KeyTypeParameter =
typename TypeHelpers::ParameterType<KeyType>::type;
107 using ValueTypeParameter =
typename TypeHelpers::ParameterType<ValueType>::type;
121 explicit HashMap (
int numberOfSlots = defaultHashTableSize,
122 HashFunctionType hashFunction = HashFunctionType())
123 : hashFunctionToUse (hashFunction)
143 for (
auto i = hashSlots.
size(); --i >= 0;)
149 const std::unique_ptr<HashEntry> deleter (h);
153 hashSlots.
set (i,
nullptr);
161 inline int size() const noexcept
163 return totalNumItems;
170 inline ValueType
operator[] (KeyTypeParameter keyToLookFor)
const
174 if (
auto* entry = getEntry (getSlot (keyToLookFor), keyToLookFor))
188 auto hashIndex = generateHashFor (keyToLookFor,
getNumSlots());
192 if (
auto* entry = getEntry (firstEntry, keyToLookFor))
195 auto* entry =
new HashEntry (keyToLookFor, ValueType(), firstEntry);
196 hashSlots.
set (hashIndex, entry);
207 bool contains (KeyTypeParameter keyToLookFor)
const
211 return (getEntry (getSlot (keyToLookFor), keyToLookFor) !=
nullptr);
220 for (
auto* entry = hashSlots.
getUnchecked(i); entry !=
nullptr; entry = entry->nextEntry)
221 if (entry->value == valueToLookFor)
232 void set (KeyTypeParameter newKey, ValueTypeParameter newValue) {
getReference (newKey) = newValue; }
235 void remove (KeyTypeParameter keyToRemove)
238 auto hashIndex = generateHashFor (keyToRemove,
getNumSlots());
240 HashEntry* previous =
nullptr;
242 while (entry !=
nullptr)
244 if (entry->key == keyToRemove)
246 const std::unique_ptr<HashEntry> deleter (entry);
248 entry = entry->nextEntry;
250 if (previous !=
nullptr)
251 previous->nextEntry = entry;
253 hashSlots.
set (hashIndex, entry);
260 entry = entry->nextEntry;
273 HashEntry* previous =
nullptr;
275 while (entry !=
nullptr)
277 if (entry->value == valueToRemove)
279 const std::unique_ptr<HashEntry> deleter (entry);
281 entry = entry->nextEntry;
283 if (previous !=
nullptr)
284 previous->nextEntry = entry;
286 hashSlots.
set (i, entry);
293 entry = entry->nextEntry;
312 HashEntry* nextEntry =
nullptr;
314 for (
auto* entry = hashSlots.
getUnchecked(i); entry !=
nullptr; entry = nextEntry)
316 auto hashIndex = generateHashFor (entry->key, newNumberOfSlots);
318 nextEntry = entry->nextEntry;
321 newSlots.
set (hashIndex, entry);
334 return hashSlots.
size();
339 template <
class OtherHashMapType>
340 void swapWith (OtherHashMapType& otherHashMap)
noexcept
343 const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
345 hashSlots.
swapWith (otherHashMap.hashSlots);
346 std::swap (totalNumItems, otherHashMap.totalNumItems);
354 inline const TypeOfCriticalSectionToUse&
getLock() const noexcept {
return lock; }
364 HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry*
const next)
365 : key (k), value (val), nextEntry (next)
370 HashEntry* nextEntry;
372 JUCE_DECLARE_NON_COPYABLE (HashEntry)
402 : hashMap (hashMapToIterate), entry (
nullptr), index (0)
406 : hashMap (other.hashMap), entry (other.entry), index (other.index)
415 if (entry !=
nullptr)
416 entry = entry->nextEntry;
418 while (entry ==
nullptr)
434 return entry !=
nullptr ? entry->key : KeyType();
442 return entry !=
nullptr ? entry->value : ValueType();
452 Iterator& operator++() noexcept {
next();
return *
this; }
453 ValueType operator*()
const {
return getValue(); }
454 bool operator!= (
const Iterator& other)
const noexcept {
return entry != other.entry || index != other.index; }
455 void resetToEnd() noexcept { index = hashMap.
getNumSlots(); }
459 const HashMap& hashMap;
464 Iterator& operator= (
const Iterator&) =
delete;
466 JUCE_LEAK_DETECTOR (Iterator)
477 enum { defaultHashTableSize = 101 };
478 friend struct Iterator;
480 HashFunctionType hashFunctionToUse;
481 Array<HashEntry*> hashSlots;
482 int totalNumItems = 0;
483 TypeOfCriticalSectionToUse lock;
485 int generateHashFor (KeyTypeParameter key,
int numSlots)
const
487 const int hash = hashFunctionToUse.generateHash (key, numSlots);
488 jassert (isPositiveAndBelow (hash, numSlots));
492 static inline HashEntry* getEntry (HashEntry* firstEntry, KeyType keyToLookFor)
noexcept
494 for (
auto* entry = firstEntry; entry !=
nullptr; entry = entry->nextEntry)
495 if (entry->key == keyToLookFor)
501 inline HashEntry* getSlot (KeyType key)
const noexcept {
return hashSlots.getUnchecked (generateHashFor (key,
getNumSlots())); }
503 JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR (HashMap)
void swapWith(OtherArrayType &otherArray) noexcept
ElementType getUnchecked(int index) const
int size() const noexcept
void set(int indexToChange, ParameterType newValue)
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
int getNumSlots() const noexcept
bool containsValue(ValueTypeParameter valueToLookFor) const
const TypeOfCriticalSectionToUse & getLock() const noexcept
Iterator begin() const noexcept
ValueType operator[](KeyTypeParameter keyToLookFor) const
void swapWith(OtherHashMapType &otherHashMap) noexcept
void remove(KeyTypeParameter keyToRemove)
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
void remapTable(int newNumberOfSlots)
bool contains(KeyTypeParameter keyToLookFor) const
void removeValue(ValueTypeParameter valueToRemove)
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Iterator end() const noexcept
ValueType & getReference(KeyTypeParameter keyToLookFor)
int size() const noexcept
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
static int generateHash(const void *key, int upperLimit) noexcept
static int generateHash(int32 key, int upperLimit) noexcept
static int generateHash(const String &key, int upperLimit) noexcept
static int generateHash(int64 key, int upperLimit) noexcept
static int generateHash(uint64 key, int upperLimit) noexcept
static int generateHash(const Uuid &key, int upperLimit) noexcept
static int generateHash(const var &key, int upperLimit) noexcept
static int generateHash(uint32 key, int upperLimit) noexcept
ValueType getValue() const