juce_HashMap.h

Go to the documentation of this file.

/*
  ==============================================================================
 
   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