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)
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)
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
ElementType getUnchecked(int index) const
Returns one of the elements in the array, without checking the index passed in.
int size() const noexcept
Returns the current number of elements in the array.
void set(int indexToChange, ParameterType newValue)
Replaces an element with a new value.
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
Inserts multiple copies of an element into the array at a given position.
Holds a set of mappings between some key/value pairs.
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
int getNumSlots() const noexcept
Returns the number of slots which are available for hashing.
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.
ValueType operator[](KeyTypeParameter keyToLookFor) const
Returns the value corresponding to a given key.
void swapWith(OtherHashMapType &otherHashMap) noexcept
Efficiently swaps the contents of two hash-maps.
void remove(KeyTypeParameter keyToRemove)
Removes an item with the given key.
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Adds or replaces an element in the hash-map.
void remapTable(int newNumberOfSlots)
Remaps the hash-map to use a different number of slots for its hash function.
const TypeOfCriticalSectionToUse & getLock() const noexcept
Returns the CriticalSection that locks this structure.
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specified key.
void removeValue(ValueTypeParameter valueToRemove)
Removes all items with the given value.
void clear()
Removes all values from the map.
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Returns the type of scoped lock to use for locking this array.
Iterator end() const noexcept
Returns an end iterator for the values in this tree.
int size() const noexcept
Returns the current number of items in the map.
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Creates an empty hash-map.
A universally unique 128-bit identifier.
A variant class, that can be used to hold a range of primitive values.
A simple class to generate hash functions for some primitive types, intended for use with the HashMap...
static int generateHash(const void *key, int upperLimit) noexcept
Generates a simple hash from a void ptr.
static int generateHash(int32 key, int upperLimit) noexcept
Generates a simple hash from an integer.
static int generateHash(const String &key, int upperLimit) noexcept
Generates a simple hash from a string.
static int generateHash(int64 key, int upperLimit) noexcept
Generates a simple hash from an int64.
static int generateHash(uint64 key, int upperLimit) noexcept
Generates a simple hash from a uint64.
static int generateHash(const Uuid &key, int upperLimit) noexcept
Generates a simple hash from a UUID.
static int generateHash(const var &key, int upperLimit) noexcept
Generates a simple hash from a variant.
static int generateHash(uint32 key, int upperLimit) noexcept
Generates a simple hash from an unsigned int.
Iterates over the items in a HashMap.
ValueType getValue() const
Returns the current item's value.
bool next() noexcept
Moves to the next item, if one is available.
KeyType getKey() const
Returns the current item's key.
void reset() noexcept
Resets the iterator to its starting position.