Any possibility to see this with the containers?


#1

/*
  ==============================================================================

   This file is part of the JUCE library - "Jules' Utility Class Extensions"
   Copyright 2004-7 by Raw Material Software ltd.

  ------------------------------------------------------------------------------

   JUCE can be redistributed and/or modified under the terms of the
   GNU General Public License, as published by the Free Software Foundation;
   either version 2 of the License, or (at your option) any later version.

   JUCE is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with JUCE; if not, visit www.gnu.org/licenses or write to the
   Free Software Foundation, Inc., 59 Temple Place, Suite 330,
   Boston, MA 02111-1307 USA

  ------------------------------------------------------------------------------

   If you'd like to release a closed-source product which uses JUCE, commercial
   licenses are also available: visit www.rawmaterialsoftware.com/juce for
   more information.

  ==============================================================================
*/

#ifndef __JUCE_OWNEDHASH_JUCEHEADER__
#define __JUCE_OWNEDHASH_JUCEHEADER__

#include "juce.h"


//==============================================================================
/** The default max load (percentage) of the total size.

    When we reach numElements > (maxsize * juceDefaultHashSetMaxLoad) then we
    will grow the array a bit more.
*/
const float juceDefaultOwnedHashMaxLoad = 0.66f;

//==============================================================================
/** The default initial size of the owned hash internal table

    Could be a prime number, better if is a prime (but not mandatory)
*/
const int juceDefaultOwnedHashDefaultSize = 101;


//==============================================================================
/**
    Implements a owned hash typically useful with Object pointers

    It is faster when accessing elements with bigger tables than doing a linear
    search of an unordered table.

    @code
        class StringHashFunction {
        public:
            static int generateHash (const String& key, const int size) {
                return key.hashCode() % size;
            }
        };
        typedef OwnedHash<String, MyObject, StringHashFunction> StringOwnedHash;

        // int key and Myclass* element type with specied hash function 
        class IntHashFunction {
        public:
            static int generateHash (const int e, const int size) {
                if (e < 0) e *= -1;
                return e % size;
            }
        };
        typedef OwnedHash<int, void, IntHashFunction> IntOwnedHash;


        // usage example
        StringOwnedHash hash;
        hash.add (T("test1"), new MyObject (1));
        hash.add (T("test2"), new MyObject (2));

        if (set.contains (T("test1")))
            std::cout << set [T("test1")]->myFunc() << std::endl;

        set.remove (T("test2"));
        MyObject* removed = set [T("test2")];
        if (removed)
            std::cout << removed->myFunc() << std::endl;

    @endcode

    @see OwnedArray, ReferenceCountedArray, SparseSet
*/
template <class KeyType,
          class ObjectClass,
          class HashFunctionToUse,
          class TypeOfCriticalSectionToUse = DummyCriticalSection>
class OwnedHash
{
private:

    //==============================================================================
    /** Internal linked list structure holding key and value */
    struct OwnedHashEntry
    {
        OwnedHashEntry (const KeyType key_, ObjectClass* element_)
        {
            key = key_;
            element = element_;
            nextEntry = 0;
        }

        KeyType key;
        ObjectClass* element;
        OwnedHashEntry* nextEntry;
    };

public:

    //==============================================================================
    /** Iterates the owned hash regardless of the order

        @see OwnedHash
    */
    class Iterator
    {
    public:
        //==============================================================================
        Iterator (const OwnedHash& set_)
            : currentEntry (0),
              set (set_),
              currentRowEntry (0),
              currentElement (0)
        {
        }

        //==============================================================================
        /** Moves onto the next element in the owned hash

            If this returns false, there are no more elements. If it returns true,
            the currentElement variable will be set to the hold pointer of the current
            element, while currentKey will hold it's key
        */
        bool next()
        {
            // advance to the next entry
            if (currentEntry)
                currentEntry = currentEntry->pNext;

            // if the entry does not exist, scan for a non empy row
            while (! currentEntry && currentRowEntry < set.size() - 1)
                currentEntry = set.entries [++currentRowEntry];

            if (currentEntry)
            {
                currentKey = currentEntry->key;
                currentElement = currentEntry->element;
                return true;
            }
            else
            {
                currentKey = KeyType();
                currentElement = 0;
                return false;
            }
        }

        //==============================================================================
        const KeyType& currentKey;
        ObjectClass* currentElement;

    private:
        const OwnedHash& set;
        int currentRowEntry;
        OwnedHashEntry* currentEntry;

        Iterator (const Iterator&);
        const Iterator& operator= (const Iterator&);
    };


    //==============================================================================
    /** Creates an empty owned hash with intial size of juceDefaultOwnedHashDefaultSize. */
    OwnedHash ()
        : maxSize (0),
          numEntries (0),
          entries (0)
    {
        setAllocatedSize (juceDefaultOwnedHashDefaultSize);
    }

    /** Creates an owned hash with the initial size of the specified value.

        @param initialSize  this is the size of increment by which the internal storage
        will be increased.
    */
    OwnedHash (const int initialSize)
        : maxSize (0),
          numEntries (0),
          entries (0)
    {
        setAllocatedSize (initialSize);
    }

    /** Destructor. */
    ~OwnedHash()
    {
        clear ();
        setAllocatedSize (0);
    }

    //==============================================================================
    /** Removes all elements from the owned hash.

        This will remove all the elements, and free any storage that the hash is
        using. You can eventually block deleting owned object by passing false as
        first argument (it works like clear of the OwnedArray).
    */
    void clear (const bool deleteObjects = true)
    {
        lock.enter();

        for (int i = 0; i < maxSize; i++)
        {
            OwnedHashEntry* entry = entries[i];
            while (entry)
            {
                OwnedHashEntry* oldEntry = entry;
                entry = entry->nextEntry;

                if (deleteObjects)
                    delete oldEntry->element;

                delete oldEntry;
            }
            entries[i] = 0;
        }
        numEntries = 0;

        lock.exit();
    }

    //==============================================================================
    /** Returns the current number of elements in the owned hash. */
    inline int size() const throw()
    {
        return numEntries;
    }

    /** If the key passed in is not present  elements, this will return zero.

        If you're certain that the key will always be a valid element, you
        can call getUnchecked() instead, which is faster.

        @param keyToLookFor    the key of the element being requested
        @see getUnchecked
    */
    inline ObjectClass* operator[] (const KeyType keyToLookFor) const throw()
    {
        lock.enter();

        const int searchIndex = HashFunctionToUse::generateHash (keyToLookFor, maxSize);
        OwnedHashEntry* entry = entries [searchIndex];

        while (entry && entry->key != keyToLookFor)
            entry = entry->nextEntry;

        ObjectClass* const result = (entry != 0) ? entry->element : 0;

        lock.exit();

        return result;
    }

    /** Returns a pointer to the object with this key in the map, without checking if
        it exists or not.

        This is a faster and less safe version of operator[] which doesn't check the
        resulting entry if it exists or not, so it can be used when you're sure the
        key will always represent a object in the map.
    */
    inline ObjectClass* getUnchecked (const KeyType keyToLookFor) const throw()
    {
        lock.enter();

        const int searchIndex = HashFunctionToUse::generateHash (keyToLookFor, maxSize);
        OwnedHashEntry* entry = entries [searchIndex];

        while (entry && entry->key != keyToLookFor)
            entry = entry->nextEntry;

        ObjectClass* const result = entry->element;

        lock.exit();

        return result;
    }

    //==============================================================================
    /** Returns the key of the given object.

        @param elementToLookFor     the value or object to look for
        @param resultKey            the key for the found object (unset otherwise)
        @returns                    true if we found the key for the object
    */
    bool keyOf (const ObjectClass* const elementToLookFor, KeyType& resultKey) const throw()
    {
        for (int i = maxSize; --i >= 0;)
        {
            OwnedHashEntry* entry = entries[i];
            while (entry)
            {
                if (entry->element == elementToLookFor)
                {
                    resultKey = entry->key;
                    return true;
                }

                entry = entry->nextEntry;
            }
        }
        return false;
    }

    /** Returns true if the owned hash contains one occurrence of the specied key.

        @param keyToLookFor         the key to look for
        @returns                    true if the item is found
    */
    bool contains (const KeyType keyToLookFor) const throw()
    {
        const int searchIndex = HashFunctionToUse::generateHash (keyToLookFor, maxSize);
        OwnedHashEntry* entry = entries [searchIndex];

        while (entry && entry->key != keyToLookFor)
            entry = entry->nextEntry;

        return entry != 0;
    }

    /** Returns true if the owned hash contains at least one occurrence of an object.

        @param elementToLookFor     the value or object to look for
        @returns                    true if the item is found
    */
    bool containsObject (const ObjectClass* const elementToLookFor) const throw()
    {
        for (int i = maxSize; --i >= 0;)
        {
            OwnedHashEntry* entry = entries[i];
            while (entry)
            {
                if (entry->element == elementToLookFor)
                    return true;

                entry = entry->nextEntry;
            }
        }
        return false;
    }

    //==============================================================================
    /** Appends a new element to the owned hash.

        @param newElement       the new object to add to the owned hash
        @see remove
    */
    void add (const KeyType newKey, ObjectClass* const newElement) throw()
    {
        lock.enter();

        const int writeIndex = HashFunctionToUse::generateHash (newKey, maxSize);
        OwnedHashEntry* entry = entries [writeIndex];

        if (! entry)
        {
            insertAt (newKey, newElement, writeIndex);
        }
        else
        {
            while (entry->nextEntry && entry->nextEntry->key != newKey)
                entry = entry->nextEntry;

            if (! entry->nextEntry)
                insertAt (newKey, newElement, writeIndex);
        }

        lock.exit();
    }

    /** Removes an element from the owned hash.

        This will remove the element, and eventually free the holded object.
        If the key passed is not currently in the owned hash, nothing will happen.

        @param keyToRemove      the key of the element to remove
        @param deleteObject     true if ou want to free the holded object memory
    */
    void remove (const KeyType keyToRemove,
                 const bool deleteObject = true) throw ()
    {
        lock.enter();

        const int removeIndexPos = HashFunctionToUse::generateHash (keyToRemove, maxSize);
        OwnedHashEntry* entry = entries [removeIndexPos];

        if (entry)
        {
            // it's the first one
            if (entry->key == keyToRemove)
            {
                entries [removeIndexPos] = entry->nextEntry;

                if (deleteObject)
                    delete entry->element;

                delete entry;
                --numEntries;
            }
            else
            {
                while (entry->nextEntry && entry->nextEntry->key != keyToRemove)
                    entry = entry->nextEntry;

                // we found it
                if (entry->nextEntry)
                {
                    OwnedHashEntry* tempEntry = entry->nextEntry;
                    entry->nextEntry = entry->nextEntry->nextEntry;

                    if (deleteObject)
                        delete tempEntry->element;

                    delete tempEntry;
                    --numEntries;
                }
            }
        }

        lock.exit();
    }

    /** Removes a specified object from the owned hash.

        If the item isn't found, no action is taken.

        @param objectToRemove   the object to try to remove
        @param deleteObject     whether to delete the object (if it's found)
        @see remove, removeRange
    */
    void removeObject (const ObjectClass* const objectToRemove,
                       const bool deleteObject = true)
    {
        lock.enter();

        bool continueSearch = true;

        for (int i = maxSize; --i >= 0 && continueSearch;)
        {
            OwnedHashEntry* entry = entries[i];
            OwnedHashEntry* previousEntry = 0;
            while (entry)
            {
                if (entry->element == objectToRemove)
                {
                    if (previousEntry == 0)
                        entries [i] = entry->nextEntry;
                    else
                        previousEntry->nextEntry = entry->nextEntry;

                    if (deleteObject)
                        delete entry->element;

                    delete entry;
                    --numEntries;

                    continueSearch = false;
                    break;
                }

                previousEntry = entry;
                entry = entry->nextEntry;
            }
        }

        lock.exit();
    }

    //==============================================================================
    /** Swaps a pair of objects in the owned hash.

        If either of the keys passed in are not found, nothing will happen,
        otherwise the two objects with these keys will be exchanged.
    */
    void swap (const KeyType keyIndex1,
               const KeyType keyIndex2) throw()
    {
        lock.enter();

        const int indexSearch1 = HashFunctionToUse::generateHash (keyIndex1, maxSize);
        const int indexSearch2 = HashFunctionToUse::generateHash (keyIndex2, maxSize);
        OwnedHashEntry* entry1 = entries [indexSearch1];
        OwnedHashEntry* entry2 = entries [indexSearch2];

        while (entry1)
        {
            if (entry1->key == keyIndex1)
                break;
            entry1 = entry1->nextEntry;
        }

        while (entry2)
        {
            if (entry2->key == keyIndex2)
                break;
            entry2 = entry2->nextEntry;
        }

        if (entry1 && entry2)
            swapVariables (entry1->element, entry2->element);

        lock.exit();
    }

    //==============================================================================
    /** Locks the owned hash's CriticalSection.

        Of course if the type of section used is a DummyCriticalSection, this won't
        have any effect.

        @see unlockHash
    */
    void lockHash() const throw()
    {
        lock.enter();
    }

    /** Unlocks the owned hash's CriticalSection.

        Of course if the type of section used is a DummyCriticalSection, this won't
        have any effect.

        @see lockHash
    */
    void unlockHash() const throw()
    {
        lock.exit();
    }

    //==============================================================================
    juce_UseDebuggingNewOperator

private:

    //==============================================================================
    /** Changes the amount of storage allocated.

        This will retain any data currently held in the owned hash

        @param newSize    the size of the table to create
    */
    void setAllocatedSize (const int newSize) throw()
    {
        if (maxSize != newSize)
        {
            maxSize = newSize;

            if (newSize > 0)
            {
                entries = (OwnedHashEntry**) juce_malloc (sizeof (OwnedHashEntry*) * newSize);
                zeromem (entries, sizeof (OwnedHashEntry*) * newSize);
            }
            else
            {
                if (entries != 0)
                {
                    juce_free (entries);
                    entries = 0;
                }
            }
        }
    }

    //==============================================================================
    void insertAt (const KeyType newKey, ObjectClass* const newElement, const int pushPosition)
    {
        OwnedHashEntry* newEntry = new OwnedHashEntry (newKey, newElement);
        OwnedHashEntry* oldEntry = entries [pushPosition];
        entries [pushPosition] = newEntry;
        newEntry->nextEntry = oldEntry;
        numEntries++;

        if ((numEntries / (float) maxSize) > juceDefaultOwnedHashMaxLoad)
            growInternalArray();
    }

    //==============================================================================
    void growInternalArray()
    {
        const int oldNumEntries = numEntries;
        const int oldSize = maxSize;
        OwnedHashEntry** oldEntries = entries;

        // create new storage twice as big as the old
        setAllocatedSize (2 * maxSize);

        // rehash all of the entries
        // this can be more efficient-- right now it recreates all of the hash_entries.
        for (int i = 0; i < oldSize; i++)
        {
            OwnedHashEntry* entry = oldEntries[i];
            while (entry)
            {
                add (entry->key, entry->element);
                OwnedHashEntry* temp = entry;
                entry = entry->nextEntry;
                delete temp;
            }
        }

        jassert (oldNumEntries == numEntries);

        juce_free (oldEntries);
    }

    //==============================================================================
    friend class Iterator;

    int maxSize, numEntries;
    OwnedHashEntry** entries;
    TypeOfCriticalSectionToUse lock;

    OwnedHash (const OwnedHash&);
    const OwnedHash& operator= (const OwnedHash&);
};



class StringHashFunction
{
public:

    static int generateHash (const String& key, const int size)
    {
        return key.hashCode() % size;
    }
};

typedef OwnedHash<String, String, StringHashFunction> StringOwnedHash;


class IntHashFunction
{
public:
    static int generateHash (int e, int size)
    {
        if (e < 0)
            e *= -1;
        return e % size;
    }
};

typedef OwnedHash<int, String, IntHashFunction> IntOwnedHash;


#endif

what i’m lacking in juce is a powerful modular hash map for owned objects in the juce containers style

ps. don’t mention any boost libraries or i’ll flame you :smiley:

[/b][/code]


#2

Looks pretty cool! I’ve always meant to add some hashing containers, but never needed one enough that I actually got round to writing them… Bit busy right now but will take a look at that asap. Thanks!


#3