CascadeHashTable.h

Go to the documentation of this file.

//
// CascadeHashTable.h - header file for class CascadeHashTable
//
// Copyright (c) 2002, Roku, LLC.  All rights reserved.
//

#ifndef _ROKU_INCLUDE_CASCADE_UTIL_CASCADEHASHTABLE_H
#define _ROKU_INCLUDE_CASCADE_UTIL_CASCADEHASHTABLE_H

#include <cascade/util/CascadeNewArray.h>
#include <cascade/util/CascadeString.h>

#undef CASSERT  /* temporary */
#define CASSERT(x) do {} while (false) /* temporary */

template <class KEY, class DATA>
class CascadeHashTable : public CascadeObject
{
public:
    CascadeHashTable(u32 nInitialTableSize = kMinTableSize);
    virtual ~CascadeHashTable();

public: // public functions dealing with entries
    bool SetAt(const KEY & key, const DATA & data);
        // SetAt() sets the entry identified by key to data
        // adding an entry for key if one doesn't already exist,
        // replacing the entry for key if it does
        // a copy is made of data

    bool GetAt(const KEY & key, DATA & dataToSet) const;
        // GetAt() sets dataToSet with the data for the key identified by key
        // returning true if successful, false if there is no entry at key
        // dataToSet is set with a copy of data

    u32 GetSize() const;
        // GetSize() gets the number of entries in the hash table

    bool RemoveAt(const KEY & key);
        // RemoveAt() removes the entry at key if it exists

    void RemoveAllEntries();
        // RemoveAllEntries() removes all entries from the hash table.

public: // public functions dealing with enumeration
    typedef bool (EntryEnumProc)(const KEY & key, const DATA & data, void * pClientData);
    bool EnumerateEntries(EntryEnumProc * pEnumProc, void * pClientData) const;
        // EnumerateEntries() calls back pEnumProc once for each entry in the
        // hash table.  It is safe to call RemoveAt on the entry (and only
        // on the entry) passed into the pEnumProc.  EnumerateEntries() returns
        // true if the enumeration ran to completion, false if it was aborted.

protected:
    enum { kMinTableSize = 8, kExpansionFactor = 3 };

protected:
    class KeyDataPair
    {
    public:
        KeyDataPair(const KEY & key, const DATA & data, KeyDataPair * pNext) : m_key(key), m_data(data), m_pNext(pNext) { }
        ~KeyDataPair() { }
    public: 
        KEY m_key;
        DATA m_data;
        KeyDataPair * m_pNext;
    };

protected:
    void ExpandTable();

protected:
    u32 m_nSize;
    CascadeNewArray<KeyDataPair *> m_table;
};

// CascadeHashTable default template KeyHash and KeyCompare functions
template <class KEY> inline u32 CascadeHashTable_KeyHash(const KEY & key)
{
    // default hash: simple identity hash - give yourself a u32 casting operator to use it
    // e.g.  inline operator u32 () const { return (u32)this; }
    u32 nKey = (u32)key;
    return nKey >> 4;
}

template <class KEY> inline bool CascadeHashTable_KeyCompare(const KEY & key1, const KEY & key2)
{
    // default hash key compare function: better have an operator ==
    return (key1 == key2);
}

// CascadeHashTable overloaded template KeyHash and KeyCompare functions for common key types
#ifndef WIN32
template <class KEY>
#endif
inline u32 CascadeHashTable_KeyHash(const CascadeString & string)
{
    const char * pString = (const char *)string;
    u32 nHash = 0;
    while (*pString) { nHash *= 65599; nHash += *pString++; }
    return nHash;
}

#ifndef WIN32
template <class KEY>
#endif
inline u32 CascadeHashTable_KeyHash(const char * pString)
{
        u32 nHash = 0;
    while (*pString) { nHash *= 65599; nHash += *pString++; }
        return nHash;
}

#ifndef WIN32
template <class KEY>
#endif
inline bool CascadeHashTable_KeyCompare(const char * pStringKey1, const char * pStringKey2)
{
    int c = 0;
    while (! (c = *(u8 *)pStringKey1 - *(u8 *)pStringKey2) && *pStringKey2) ++pStringKey1, ++pStringKey2;
    return (c == 0);
}

// template class CascadeHashTable<KEY, DATA> implementation
template <class KEY, class DATA>
CascadeHashTable<KEY, DATA>::CascadeHashTable(u32 nInitialTableSize) :
    m_nSize(0),
    m_table(nInitialTableSize < kMinTableSize ? kMinTableSize : nInitialTableSize)
{
    // constructor for m_table specifies initial mem size for array, must also
    // set the size (number of elements we want active) the array
    m_table.SetSize(nInitialTableSize < kMinTableSize ? kMinTableSize : nInitialTableSize);
    for (u32 i = 0; i < m_table.GetSize(); i++) m_table[i] = NULL;
}

template <class KEY, class DATA>
CascadeHashTable<KEY, DATA>::~CascadeHashTable()
{
  RemoveAllEntries();
}

// void CascadeHashTable::SetEntry(const KEY & key, const DATA & data);
template <class KEY, class DATA>
bool
CascadeHashTable<KEY, DATA>::SetAt(const KEY & key, const DATA & data)
{
    u32 nHash = CascadeHashTable_KeyHash<KEY>(key) % m_table.GetSize();
    KeyDataPair * pCurr = m_table[nHash];
    while (pCurr)
    {
        if (CascadeHashTable_KeyCompare<KEY>(key, pCurr->m_key))
        {
            pCurr->m_data = data;
            return true;
        }
        pCurr = pCurr->m_pNext;
    }
    m_table[nHash] = new KeyDataPair(key, data, m_table[nHash]);
    m_nSize++;
    if (m_nSize > (kExpansionFactor * m_table.GetSize())) ExpandTable();
    return true;
}

// bool CascadeHashTable::GetEntry(const KEY & key, DATA & dataToSet);
template <class KEY, class DATA>
bool
CascadeHashTable<KEY, DATA>::GetAt(const KEY & key, DATA & dataToSet) const
{
    KeyDataPair * pBucket = m_table[CascadeHashTable_KeyHash<KEY>(key) % m_table.GetSize()];
    while (pBucket)
    {
        if (CascadeHashTable_KeyCompare<KEY>(key, pBucket->m_key))
        {
            dataToSet = pBucket->m_data;
            return true;
        }
        pBucket = pBucket->m_pNext;
    }
    return false;
}

// u32 CascadeHashTable::GetSize();
template <class KEY, class DATA>
inline u32
CascadeHashTable<KEY, DATA>::GetSize() const
{
    return m_nSize;
}

// void CascadeHashTable::RemoveAt(const KEY & key);
template <class KEY, class DATA>
bool
CascadeHashTable<KEY, DATA>::RemoveAt(const KEY & key)
{
    u32 nHash = CascadeHashTable_KeyHash<KEY>(key) % m_table.GetSize();
    KeyDataPair * pCurr = m_table[nHash];
    KeyDataPair * pPrev = NULL;
    while (pCurr)
    {
        if (CascadeHashTable_KeyCompare<KEY>(key, pCurr->m_key))
        {
            if (pPrev) pPrev->m_pNext = pCurr->m_pNext;
            else m_table[nHash] = pCurr->m_pNext;
            delete pCurr;
            m_nSize--;
            return true;
        }
        pPrev = pCurr; pCurr = pCurr->m_pNext;
    }
    return false;
}

// void CascadeHashTable::RemoveAllEntries();
template <class KEY, class DATA>
void
CascadeHashTable<KEY, DATA>::RemoveAllEntries()
{
    u32 nSize = m_table.GetSize();
    for (u32 i = 0; i < nSize; i++)
    {
        KeyDataPair * pCurr = m_table[i];
        KeyDataPair * pDel;
        while (pCurr)
        {
            pDel = pCurr;
            pCurr = pCurr->m_pNext;
            delete pDel;
        }
        m_table[i] = NULL;
    }
    m_nSize = 0;
}

// bool CascadeHashTable::EnumerateEntries(EntryEnumProc * pEnumProc, void * pClientData);
template <class KEY, class DATA>
bool
CascadeHashTable<KEY, DATA>::EnumerateEntries(EntryEnumProc * pEnumProc, void * pClientData) const
{
    u32 nSize = m_table.GetSize();
    for (u32 i = 0; i < nSize; i++)
    {
        KeyDataPair * pCurr = m_table[i];
        KeyDataPair * pNext;
        while (pCurr)
        {
            pNext = pCurr->m_pNext;
            if (! (*pEnumProc)(pCurr->m_key, pCurr->m_data, pClientData)) return false;
            pCurr = pNext;
        }
    }
    return true;
}

// void CascadeHashTable::ExpandTable();
template <class KEY, class DATA>
void
CascadeHashTable<KEY, DATA>::ExpandTable()
{
    u32 nSizeOld = m_table.GetSize();
    u32 nSizeNew = 2 * nSizeOld;
    u32 nHashNew;
    m_table.SetSize(nSizeNew);
    for (u32 i = nSizeOld; i < nSizeNew; i++) m_table[i] = NULL;

    // rehash buckets from 0 to (nSizeOld-1)
    for (u32 nHashOld = 0; nHashOld < nSizeOld; nHashOld++)
    {
        KeyDataPair * pCurr = m_table[nHashOld];
        KeyDataPair * pPrev = NULL;
        while (pCurr)
        {
            nHashNew = CascadeHashTable_KeyHash<KEY>(pCurr->m_key) % nSizeNew;
            if (nHashNew == nHashOld)
            {
                // hash staying the same
                pPrev = pCurr;
                pCurr = pCurr->m_pNext;
            }
            else
            {
                // hash is in new slot, move it
                CASSERT(nHashNew == (nHashOld * 2)); // must be nHashOld*2 since we doubled the table size and modded against the new size
                if (pPrev)
                {
                    pPrev->m_pNext = pCurr->m_pNext;
                    pCurr->m_pNext = m_table[nHashNew];
                    m_table[nHashNew] = pCurr;
                    pCurr = pPrev->m_pNext;
                }
                else
                {
                    m_table[nHashOld] = pCurr->m_pNext;
                    pCurr->m_pNext = m_table[nHashNew];
                    m_table[nHashNew] = pCurr;
                    pCurr = m_table[nHashOld];
                }
            }
        }
    }
}

#endif // #ifndef _ROKU_INCLUDE_CASCADE_UTIL_CASCADEHASHTABLE_H

//  LOG
//  07-Feb-04   dwoodward       created
//  15-Mar-04   dwoodward   made overloaded KeyHash and KeyCompare functions
//                          WIN32 friendly

---