Loading...
Searching...
No Matches
juce_HashMap.h
/*
==============================================================================
This file is part of the JUCE library.
Copyright (c) 2022 - Raw Material Software Limited
JUCE is an open source library subject to commercial or open-source
licensing.
The code included in this file is provided under the terms of the ISC license
http://www.isc.org/downloads/software-support-policy/isc-license. Permission
To use, copy, modify, and/or distribute this software for any purpose with or
without fee is hereby granted provided that the above copyright notice and
this permission notice appear in all copies.
JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
DISCLAIMED.
==============================================================================
*/
namespace juce
{
//==============================================================================
struct DefaultHashFunctions
{
static int generateHash (uint32 key, int upperLimit) noexcept { return (int) (key % (uint32) upperLimit); }
static int generateHash (int32 key, int upperLimit) noexcept { return generateHash ((uint32) key, upperLimit); }
static int generateHash (uint64 key, int upperLimit) noexcept { return (int) (key % (uint64) upperLimit); }
static int generateHash (int64 key, int upperLimit) noexcept { return generateHash ((uint64) key, upperLimit); }
static int generateHash (const String& key, int upperLimit) noexcept { return generateHash ((uint32) key.hashCode(), upperLimit); }
static int generateHash (const var& key, int upperLimit) noexcept { return generateHash (key.toString(), upperLimit); }
static int generateHash (const void* key, int upperLimit) noexcept { return generateHash ((uint64) (pointer_sized_uint) key, upperLimit); }
static int generateHash (const Uuid& key, int upperLimit) noexcept { return generateHash (key.hash(), upperLimit); }
};
//==============================================================================
template <typename KeyType,
typename ValueType,
class HashFunctionType = DefaultHashFunctions,
class TypeOfCriticalSectionToUse = DummyCriticalSection>
class HashMap
{
private:
using KeyTypeParameter = typename TypeHelpers::ParameterType<KeyType>::type;
using ValueTypeParameter = typename TypeHelpers::ParameterType<ValueType>::type;
public:
//==============================================================================
explicit HashMap (int numberOfSlots = defaultHashTableSize,
HashFunctionType hashFunction = HashFunctionType())
: hashFunctionToUse (hashFunction)
{
hashSlots.insertMultiple (0, nullptr, numberOfSlots);
}
~HashMap()
{
clear();
}
//==============================================================================
void clear()
{
const ScopedLockType sl (getLock());
for (auto i = hashSlots.size(); --i >= 0;)
{
auto* h = hashSlots.getUnchecked (i);
while (h != nullptr)
{
const std::unique_ptr<HashEntry> deleter (h);
h = h->nextEntry;
}
hashSlots.set (i, nullptr);
}
totalNumItems = 0;
}
//==============================================================================
inline int size() const noexcept
{
return totalNumItems;
}
inline ValueType operator[] (KeyTypeParameter keyToLookFor) const
{
const ScopedLockType sl (getLock());
if (auto* entry = getEntry (getSlot (keyToLookFor), keyToLookFor))
return entry->value;
return ValueType();
}
inline ValueType& getReference (KeyTypeParameter keyToLookFor)
{
const ScopedLockType sl (getLock());
auto hashIndex = generateHashFor (keyToLookFor, getNumSlots());
auto* firstEntry = hashSlots.getUnchecked (hashIndex);
if (auto* entry = getEntry (firstEntry, keyToLookFor))
return entry->value;
auto* entry = new HashEntry (keyToLookFor, ValueType(), firstEntry);
hashSlots.set (hashIndex, entry);
++totalNumItems;
if (totalNumItems > (getNumSlots() * 3) / 2)
remapTable (getNumSlots() * 2);
return entry->value;
}
//==============================================================================
bool contains (KeyTypeParameter keyToLookFor) const
{
const ScopedLockType sl (getLock());
return (getEntry (getSlot (keyToLookFor), keyToLookFor) != nullptr);
}
bool containsValue (ValueTypeParameter valueToLookFor) const
{
const ScopedLockType sl (getLock());
for (auto i = getNumSlots(); --i >= 0;)
for (auto* entry = hashSlots.getUnchecked (i); entry != nullptr; entry = entry->nextEntry)
if (entry->value == valueToLookFor)
return true;
return false;
}
//==============================================================================
void set (KeyTypeParameter newKey, ValueTypeParameter newValue) { getReference (newKey) = newValue; }
void remove (KeyTypeParameter keyToRemove)
{
const ScopedLockType sl (getLock());
auto hashIndex = generateHashFor (keyToRemove, getNumSlots());
auto* entry = hashSlots.getUnchecked (hashIndex);
HashEntry* previous = nullptr;
while (entry != nullptr)
{
if (entry->key == keyToRemove)
{
const std::unique_ptr<HashEntry> deleter (entry);
entry = entry->nextEntry;
if (previous != nullptr)
previous->nextEntry = entry;
else
hashSlots.set (hashIndex, entry);
--totalNumItems;
}
else
{
previous = entry;
entry = entry->nextEntry;
}
}
}
void removeValue (ValueTypeParameter valueToRemove)
{
const ScopedLockType sl (getLock());
for (auto i = getNumSlots(); --i >= 0;)
{
auto* entry = hashSlots.getUnchecked (i);
HashEntry* previous = nullptr;
while (entry != nullptr)
{
if (entry->value == valueToRemove)
{
const std::unique_ptr<HashEntry> deleter (entry);
entry = entry->nextEntry;
if (previous != nullptr)
previous->nextEntry = entry;
else
hashSlots.set (i, entry);
--totalNumItems;
}
else
{
previous = entry;
entry = entry->nextEntry;
}
}
}
}
void remapTable (int newNumberOfSlots)
{
const ScopedLockType sl (getLock());
Array<HashEntry*> newSlots;
newSlots.insertMultiple (0, nullptr, newNumberOfSlots);
for (auto i = getNumSlots(); --i >= 0;)
{
HashEntry* nextEntry = nullptr;
for (auto* entry = hashSlots.getUnchecked (i); entry != nullptr; entry = nextEntry)
{
auto hashIndex = generateHashFor (entry->key, newNumberOfSlots);
nextEntry = entry->nextEntry;
entry->nextEntry = newSlots.getUnchecked (hashIndex);
newSlots.set (hashIndex, entry);
}
}
hashSlots.swapWith (newSlots);
}
inline int getNumSlots() const noexcept
{
return hashSlots.size();
}
//==============================================================================
template <class OtherHashMapType>
void swapWith (OtherHashMapType& otherHashMap) noexcept
{
const ScopedLockType lock1 (getLock());
const typename OtherHashMapType::ScopedLockType lock2 (otherHashMap.getLock());
hashSlots.swapWith (otherHashMap.hashSlots);
std::swap (totalNumItems, otherHashMap.totalNumItems);
}
//==============================================================================
inline const TypeOfCriticalSectionToUse& getLock() const noexcept { return lock; }
using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
private:
//==============================================================================
class HashEntry
{
public:
HashEntry (KeyTypeParameter k, ValueTypeParameter val, HashEntry* const next)
: key (k), value (val), nextEntry (next)
{}
const KeyType key;
ValueType value;
HashEntry* nextEntry;
JUCE_DECLARE_NON_COPYABLE (HashEntry)
};
public:
//==============================================================================
struct Iterator
{
Iterator (const HashMap& hashMapToIterate) noexcept
: hashMap (hashMapToIterate), entry (nullptr), index (0)
{}
Iterator (const Iterator& other) noexcept
: hashMap (other.hashMap), entry (other.entry), index (other.index)
{}
bool next() noexcept
{
if (entry != nullptr)
entry = entry->nextEntry;
while (entry == nullptr)
{
if (index >= hashMap.getNumSlots())
return false;
entry = hashMap.hashSlots.getUnchecked (index++);
}
return true;
}
KeyType getKey() const
{
return entry != nullptr ? entry->key : KeyType();
}
ValueType getValue() const
{
return entry != nullptr ? entry->value : ValueType();
}
void reset() noexcept
{
entry = nullptr;
index = 0;
}
Iterator& operator++() noexcept { next(); return *this; }
ValueType operator*() const { return getValue(); }
bool operator!= (const Iterator& other) const noexcept { return entry != other.entry || index != other.index; }
void resetToEnd() noexcept { index = hashMap.getNumSlots(); }
private:
//==============================================================================
const HashMap& hashMap;
HashEntry* entry;
int index;
// using the copy constructor is ok, but you cannot assign iterators
Iterator& operator= (const Iterator&) = delete;
JUCE_LEAK_DETECTOR (Iterator)
};
Iterator begin() const noexcept { Iterator i (*this); i.next(); return i; }
Iterator end() const noexcept { Iterator i (*this); i.resetToEnd(); return i; }
private:
//==============================================================================
enum { defaultHashTableSize = 101 };
friend struct Iterator;
HashFunctionType hashFunctionToUse;
Array<HashEntry*> hashSlots;
int totalNumItems = 0;
TypeOfCriticalSectionToUse lock;
int generateHashFor (KeyTypeParameter key, int numSlots) const
{
const int hash = hashFunctionToUse.generateHash (key, numSlots);
jassert (isPositiveAndBelow (hash, numSlots)); // your hash function is generating out-of-range numbers!
return hash;
}
static HashEntry* getEntry (HashEntry* firstEntry, KeyType keyToLookFor) noexcept
{
for (auto* entry = firstEntry; entry != nullptr; entry = entry->nextEntry)
if (entry->key == keyToLookFor)
return entry;
return nullptr;
}
inline HashEntry* getSlot (KeyType key) const noexcept { return hashSlots.getUnchecked (generateHashFor (key, getNumSlots())); }
JUCE_DECLARE_NON_COPYABLE_WITH_LEAK_DETECTOR (HashMap)
};
} // namespace juce
juce::Array
Definition juce_Array.h:56
juce::Array::getUnchecked
ElementType getUnchecked(int index) const
Definition juce_Array.h:252
juce::Array::set
void set(int indexToChange, ParameterType newValue)
Definition juce_Array.h:542
juce::Array::insertMultiple
void insertMultiple(int indexToInsertAt, ParameterType newElement, int numberOfTimesToInsertIt)
Definition juce_Array.h:480
juce::HashMap::~HashMap
~HashMap()
Definition juce_HashMap.h:129
juce::HashMap::getNumSlots
int getNumSlots() const noexcept
Definition juce_HashMap.h:332
juce::HashMap::containsValue
bool containsValue(ValueTypeParameter valueToLookFor) const
Definition juce_HashMap.h:215
juce::HashMap::getLock
const TypeOfCriticalSectionToUse & getLock() const noexcept
Definition juce_HashMap.h:354
juce::HashMap::begin
Iterator begin() const noexcept
Definition juce_HashMap.h:470
juce::HashMap::operator[]
ValueType operator[](KeyTypeParameter keyToLookFor) const
Definition juce_HashMap.h:170
juce::HashMap::swapWith
void swapWith(OtherHashMapType &otherHashMap) noexcept
Definition juce_HashMap.h:340
juce::HashMap::remove
void remove(KeyTypeParameter keyToRemove)
Definition juce_HashMap.h:235
juce::HashMap::set
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Definition juce_HashMap.h:232
juce::HashMap::remapTable
void remapTable(int newNumberOfSlots)
Definition juce_HashMap.h:303
juce::HashMap::contains
bool contains(KeyTypeParameter keyToLookFor) const
Definition juce_HashMap.h:207
juce::HashMap::removeValue
void removeValue(ValueTypeParameter valueToRemove)
Definition juce_HashMap.h:266
juce::HashMap::clear
void clear()
Definition juce_HashMap.h:139
juce::HashMap::ScopedLockType
typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType
Definition juce_HashMap.h:357
juce::HashMap::end
Iterator end() const noexcept
Definition juce_HashMap.h:473
juce::HashMap::getReference
ValueType & getReference(KeyTypeParameter keyToLookFor)
Definition juce_HashMap.h:185
juce::HashMap::size
int size() const noexcept
Definition juce_HashMap.h:161
juce::HashMap::HashMap
HashMap(int numberOfSlots=defaultHashTableSize, HashFunctionType hashFunction=HashFunctionType())
Definition juce_HashMap.h:121
juce::String
Definition juce_String.h:53
juce::Uuid
Definition juce_Uuid.h:39
juce::var
Definition juce_Variant.h:42
juce::DefaultHashFunctions
Definition juce_HashMap.h:35
juce::DefaultHashFunctions::generateHash
static int generateHash(const void *key, int upperLimit) noexcept
Definition juce_HashMap.h:49
juce::DefaultHashFunctions::generateHash
static int generateHash(int32 key, int upperLimit) noexcept
Definition juce_HashMap.h:39
juce::DefaultHashFunctions::generateHash
static int generateHash(const String &key, int upperLimit) noexcept
Definition juce_HashMap.h:45
juce::DefaultHashFunctions::generateHash
static int generateHash(int64 key, int upperLimit) noexcept
Definition juce_HashMap.h:43
juce::DefaultHashFunctions::generateHash
static int generateHash(uint64 key, int upperLimit) noexcept
Definition juce_HashMap.h:41
juce::DefaultHashFunctions::generateHash
static int generateHash(const Uuid &key, int upperLimit) noexcept
Definition juce_HashMap.h:51
juce::DefaultHashFunctions::generateHash
static int generateHash(const var &key, int upperLimit) noexcept
Definition juce_HashMap.h:47
juce::DefaultHashFunctions::generateHash
static int generateHash(uint32 key, int upperLimit) noexcept
Definition juce_HashMap.h:37
juce::HashMap::Iterator
Definition juce_HashMap.h:400
juce::HashMap::Iterator::getValue
ValueType getValue() const
Definition juce_HashMap.h:440
juce::HashMap::Iterator::next
bool next() noexcept
Definition juce_HashMap.h:413
juce::HashMap::Iterator::getKey
KeyType getKey() const
Definition juce_HashMap.h:432
juce::HashMap::Iterator::reset
void reset() noexcept
Definition juce_HashMap.h:446