41 static int generateHash (uint32 key,
int upperLimit) noexcept {
return (
int) (key % (uint32) upperLimit); }
45 static int generateHash (uint64 key,
int upperLimit) noexcept {
return (
int) (key % (uint64) upperLimit); }
53 static int generateHash (
const void* key,
int upperLimit) noexcept {
return generateHash ((uint64) (pointer_sized_uint) key, upperLimit); }
103 template <
typename KeyType,
105 class HashFunctionType = DefaultHashFunctions,
106 class TypeOfCriticalSectionToUse = DummyCriticalSection>
110 using KeyTypeParameter =
typename TypeHelpers::ParameterType<KeyType>::type;
111 using ValueTypeParameter =
typename TypeHelpers::ParameterType<ValueType>::type;
125 explicit HashMap (
int numberOfSlots = defaultHashTableSize,
126 HashFunctionType hashFunction = HashFunctionType())
127 : hashFunctionToUse (hashFunction)
147 for (
auto i = hashSlots.
size(); --i >= 0;)
153 const std::unique_ptr<HashEntry> deleter (h);
157 hashSlots.
set (i,
nullptr);
165 inline int size() const noexcept
167 return totalNumItems;
174 inline ValueType
operator[] (KeyTypeParameter keyToLookFor)
const
178 if (
auto* entry = getEntry (getSlot (keyToLookFor), keyToLookFor))
192 auto hashIndex = generateHashFor (keyToLookFor,
getNumSlots());
196 if (
auto* entry = getEntry (firstEntry, keyToLookFor))
199 auto* entry =
new HashEntry (keyToLookFor, ValueType(), firstEntry);
200 hashSlots.
set (hashIndex, entry);
211 bool contains (KeyTypeParameter keyToLookFor)
const
215 return (getEntry (getSlot (keyToLookFor), keyToLookFor) !=
nullptr);
224 for (
auto* entry = hashSlots.
getUnchecked(i); entry !=
nullptr; entry = entry->nextEntry)
225 if (entry->value == valueToLookFor)
236 void set (KeyTypeParameter newKey, ValueTypeParameter newValue) {
getReference (newKey) = newValue; }
239 void remove (KeyTypeParameter keyToRemove)
242 auto hashIndex = generateHashFor (keyToRemove,
getNumSlots());
244 HashEntry* previous =
nullptr;
246 while (entry !=
nullptr)
248 if (entry->key == keyToRemove)
250 const std::unique_ptr<HashEntry> deleter (entry);
252 entry = entry->nextEntry;
254 if (previous !=
nullptr)
255 previous->nextEntry = entry;
257 hashSlots.
set (hashIndex, entry);
264 entry = entry->nextEntry;
277 HashEntry* previous =
nullptr;
279 while (entry !=
nullptr)
281 if (entry->value == valueToRemove)
283 const std::unique_ptr<HashEntry> deleter (entry);
285 entry = entry->nextEntry;
287 if (previous !=
nullptr)
288 previous->nextEntry = entry;
290 hashSlots.
set (i, entry);
297 entry = entry->nextEntry;
316 HashEntry* nextEntry =
nullptr;
318 for (
auto* entry = hashSlots.
getUnchecked(i); entry !=
nullptr; entry = nextEntry)
320 auto hashIndex = generateHashFor (entry->key, newNumberOfSlots);
322 nextEntry = entry->nextEntry;
325 newSlots.
set (hashIndex, entry);
338 return hashSlots.
size();
343 template <
class OtherHashMapType>
344 void swapWith (OtherHashMapType& otherHashMap) noexcept
347 const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
349 hashSlots.
swapWith (otherHashMap.hashSlots);
350 std::swap (totalNumItems, otherHashMap.totalNumItems);
358 inline const TypeOfCriticalSectionToUse&
getLock() const noexcept {
return lock; }
368 HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry*
const next)
369 : key (k), value (val), nextEntry (next)
374 HashEntry* nextEntry;
376 JUCE_DECLARE_NON_COPYABLE (HashEntry)
406 : hashMap (hashMapToIterate), entry (
nullptr), index (0)
410 : hashMap (other.hashMap), entry (other.entry), index (other.index)
419 if (entry !=
nullptr)
420 entry = entry->nextEntry;
422 while (entry ==
nullptr)
438 return entry !=
nullptr ? entry->key : KeyType();
446 return entry !=
nullptr ? entry->value : ValueType();
456 Iterator& operator++() noexcept {
next();
return *
this; }
457 ValueType operator*()
const {
return getValue(); }
458 bool operator!= (
const Iterator& other)
const noexcept {
return entry != other.entry || index != other.index; }
459 void resetToEnd() noexcept { index = hashMap.
getNumSlots(); }
468 Iterator& operator= (
const Iterator&) =
delete;
470 JUCE_LEAK_DETECTOR (Iterator)
474 Iterator
begin() const noexcept { Iterator i (*
this); i.next();
return i; }
477 Iterator
end() const noexcept { Iterator i (*
this); i.resetToEnd();
return i; }
481 enum { defaultHashTableSize = 101 };
482 friend struct Iterator;
484 HashFunctionType hashFunctionToUse;
485 Array<HashEntry*> hashSlots;
486 int totalNumItems = 0;
487 TypeOfCriticalSectionToUse lock;
489 int generateHashFor (KeyTypeParameter key,
int numSlots)
const
491 const int hash = hashFunctionToUse.generateHash (key, numSlots);
492 jassert (isPositiveAndBelow (hash, numSlots));
496 static inline HashEntry* getEntry (HashEntry* firstEntry, KeyType keyToLookFor) noexcept
498 for (
auto* entry = firstEntry; entry !=
nullptr; entry = entry->nextEntry)
499 if (entry->key == keyToLookFor)
505 inline HashEntry* getSlot (KeyType key)
const noexcept {
return hashSlots.getUnchecked (generateHashFor (key,
getNumSlots())); }
507 JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR (
HashMap)