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,
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)
129 hashSlots.insertMultiple (0,
nullptr, numberOfSlots);
147 for (
auto i = hashSlots.size(); --i >= 0;)
149 auto* h = hashSlots.getUnchecked(i);
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());
194 auto* firstEntry = hashSlots.getUnchecked (hashIndex);
196 if (
auto* entry = getEntry (firstEntry, keyToLookFor))
199 auto* entry =
new HashEntry (keyToLookFor, ValueType(), firstEntry);
200 hashSlots.set (hashIndex, entry);
203 if (totalNumItems > (getNumSlots() * 3) / 2)
204 remapTable (getNumSlots() * 2);
211 bool contains (KeyTypeParameter keyToLookFor)
const 215 return (getEntry (getSlot (keyToLookFor), keyToLookFor) !=
nullptr);
223 for (
auto i = getNumSlots(); --i >= 0;)
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());
243 auto* entry = hashSlots.getUnchecked (hashIndex);
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;
274 for (
auto i = getNumSlots(); --i >= 0;)
276 auto* entry = hashSlots.getUnchecked(i);
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;
314 for (
auto i = getNumSlots(); --i >= 0;)
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);
329 hashSlots.swapWith (newSlots);
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)
424 if (index >= hashMap.getNumSlots())
427 entry = hashMap.hashSlots.getUnchecked (index++);
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(); }
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;
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)
Holds a set of mappings between some key/value pairs.
typename DummyCriticalSection ::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.
bool containsValue(ValueTypeParameter valueToLookFor) const
Returns true if the hash contains at least one occurrence of a given value.
Iterator begin() const noexcept
Returns a start iterator for the values in this tree.
void remapTable(int newNumberOfSlots)
Remaps the hash-map to use a different number of slots for its hash function.
A variant class, that can be used to hold a range of primitive values.
int size() const noexcept
Returns the current number of items in the map.
bool next() noexcept
Moves to the next item, if one is available.
int getNumSlots() const noexcept
Returns the number of slots which are available for hashing.
KeyType getKey() const
Returns the current item's key.
void clear()
Removes all values from the map.
static int generateHash(const Uuid &key, int upperLimit) noexcept
Generates a simple hash from a UUID.
static int generateHash(int64 key, int upperLimit) noexcept
Generates a simple hash from an int64.
ElementType getUnchecked(int index) const
Returns one of the elements in the array, without checking the index passed in.
A universally unique 128-bit identifier.
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
Inserts multiple copies of an element into the array at a given position.
static int generateHash(uint32 key, int upperLimit) noexcept
Generates a simple hash from an unsigned int.
A class that can be used in place of a real CriticalSection object, but which doesn't perform any loc...
Iterates over the items in a HashMap.
void swapWith(OtherHashMapType &otherHashMap) noexcept
Efficiently swaps the contents of two hash-maps.
static int generateHash(const String &key, int upperLimit) noexcept
Generates a simple hash from a string.
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this structure.
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Creates an empty hash-map.
Holds a resizable array of primitive or copy-by-value objects.
static int generateHash(int32 key, int upperLimit) noexcept
Generates a simple hash from an integer.
Iterator end() const noexcept
Returns an end iterator for the values in this tree.
void removeValue(ValueTypeParameter valueToRemove)
Removes all items with the given value.
static int generateHash(const var &key, int upperLimit) noexcept
Generates a simple hash from a variant.
ValueType getValue() const
Returns the current item's value.
static int generateHash(uint64 key, int upperLimit) noexcept
Generates a simple hash from a uint64.
A simple class to generate hash functions for some primitive types, intended for use with the HashMap...
void reset() noexcept
Resets the iterator to its starting position.
void set(int indexToChange, ParameterType newValue)
Replaces an element with a new value.
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specied key.
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
static int generateHash(const void *key, int upperLimit) noexcept
Generates a simple hash from a void ptr.