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); }
99 template <
typename KeyType,
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)
125 hashSlots.insertMultiple (0,
nullptr, numberOfSlots);
143 for (
auto i = hashSlots.size(); --i >= 0;)
145 auto* h = hashSlots.getUnchecked(i);
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());
190 auto* firstEntry = hashSlots.getUnchecked (hashIndex);
192 if (
auto* entry = getEntry (firstEntry, keyToLookFor))
195 auto* entry =
new HashEntry (keyToLookFor, ValueType(), firstEntry);
196 hashSlots.set (hashIndex, entry);
199 if (totalNumItems > (getNumSlots() * 3) / 2)
200 remapTable (getNumSlots() * 2);
207 bool contains (KeyTypeParameter keyToLookFor)
const 211 return (getEntry (getSlot (keyToLookFor), keyToLookFor) !=
nullptr);
219 for (
auto i = getNumSlots(); --i >= 0;)
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());
239 auto* entry = hashSlots.getUnchecked (hashIndex);
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;
270 for (
auto i = getNumSlots(); --i >= 0;)
272 auto* entry = hashSlots.getUnchecked(i);
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;
310 for (
auto i = getNumSlots(); --i >= 0;)
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);
325 hashSlots.swapWith (newSlots);
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)
420 if (index >= hashMap.getNumSlots())
423 entry = hashMap.hashSlots.getUnchecked (index++);
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(); }
477 enum { defaultHashTableSize = 101 };
480 HashFunctionType hashFunctionToUse;
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)
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
bool containsValue(ValueTypeParameter valueToLookFor) const
Iterator begin() const noexcept
void remapTable(int newNumberOfSlots)
int size() const noexcept
int getNumSlots() const noexcept
static int generateHash(const Uuid &key, int upperLimit) noexcept
static int generateHash(int64 key, int upperLimit) noexcept
ElementType getUnchecked(int index) const
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
static int generateHash(uint32 key, int upperLimit) noexcept
void swapWith(OtherHashMapType &otherHashMap) noexcept
static int generateHash(const String &key, int upperLimit) noexcept
const TypeOfCriticalSectionToUse & getLock() const noexcept
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
static int generateHash(int32 key, int upperLimit) noexcept
Iterator end() const noexcept
void removeValue(ValueTypeParameter valueToRemove)
static int generateHash(const var &key, int upperLimit) noexcept
ValueType getValue() const
static int generateHash(uint64 key, int upperLimit) noexcept
void set(int indexToChange, ParameterType newValue)
bool contains(KeyTypeParameter keyToLookFor) const
ValueType & getReference(KeyTypeParameter keyToLookFor)
static int generateHash(const void *key, int upperLimit) noexcept