AtomicGameEngine/Source/ThirdParty/TurboBadger/tb_hashtable.cpp

// ================================================================================
// ==      This file is a part of Turbo Badger. (C) 2011-2014, Emil Segerås      ==
// ==                     See tb_core.h for more information.                    ==
// ================================================================================

#include "tb_hashtable.h"
#include "tb_system.h"
#include "tb_tempbuffer.h"

namespace tb {

//FIX: reduce memory (block allocation of ITEM)
//FIX: should shrink when deleting single items (but not when adding items!)
//FIX: should grow when about 70% full instead of 100%

// == TBHashTable =======================================================================

TBHashTable::TBHashTable()
    : m_buckets(nullptr)
    , m_num_buckets(0)
    , m_num_items(0)
{
}

TBHashTable::~TBHashTable()
{
    RemoveAll();
}

void TBHashTable::RemoveAll(bool delete_content)
{
#ifdef TB_RUNTIME_DEBUG_INFO
    //Debug();
#endif
    for (uint32 i = 0; i < m_num_buckets; i++)
    {
        ITEM *item = m_buckets[i];
        while (item)
        {
            ITEM *item_next = item->next;
            if (delete_content)
                DeleteContent(item->content);
            delete item;
            item = item_next;
        }
    }
    delete [] m_buckets;
    m_buckets = nullptr;
    m_num_buckets = m_num_items = 0;
}

bool TBHashTable::Rehash(uint32 new_num_buckets)
{
    if (new_num_buckets == m_num_buckets)
        return true;
    if (ITEM **new_buckets = new ITEM*[new_num_buckets])
    {
        memset(new_buckets, 0, sizeof(ITEM*) * new_num_buckets);
        // Rehash all items into the new buckets
        for (uint32 i = 0; i < m_num_buckets; i++)
        {
            ITEM *item = m_buckets[i];
            while (item)
            {
                ITEM *item_next = item->next;
                // Add it to new_buckets
                uint32 bucket = item->key & (new_num_buckets - 1);
                item->next = new_buckets[bucket];
                new_buckets[bucket] = item;
                item = item_next;
            }
        }
        // Delete old buckets and update
        delete [] m_buckets;
        m_buckets = new_buckets;
        m_num_buckets = new_num_buckets;
        return true;
    }
    return false;
}

bool TBHashTable::NeedRehash() const
{
    // Grow if more items than buckets
    return !m_num_buckets || m_num_items >= m_num_buckets;
}

uint32 TBHashTable::GetSuitableBucketsCount() const
{
    // As long as we use FNV for TBID (in TBGetHash), power of two hash sizes are the best.
    if (!m_num_items)
        return 16;
    return m_num_items * 2;
}

void *TBHashTable::Get(uint32 key) const
{
    if (!m_num_buckets)
        return nullptr;
    uint32 bucket = key & (m_num_buckets - 1);
    ITEM *item = m_buckets[bucket];
    while (item)
    {
        if (item->key == key)
            return item->content;
        item = item->next;
    }
    return nullptr;
}

bool TBHashTable::Add(uint32 key, void *content)
{
    if (NeedRehash() && !Rehash(GetSuitableBucketsCount()))
        return false;
    assert(!Get(key));
    if (ITEM *item = new ITEM)
    {
        uint32 bucket = key & (m_num_buckets - 1);
        item->key = key;
        item->content = content;
        item->next = m_buckets[bucket];
        m_buckets[bucket] = item;
        m_num_items++;
        return true;
    }
    return false;
}

void *TBHashTable::Remove(uint32 key)
{
    if (!m_num_buckets)
        return nullptr;
    uint32 bucket = key & (m_num_buckets - 1);
    ITEM *item = m_buckets[bucket];
    ITEM *prev_item = nullptr;
    while (item)
    {
        if (item->key == key)
        {
            if (prev_item)
                prev_item->next = item->next;
            else
                m_buckets[bucket] = item->next;
            m_num_items--;
            void *content = item->content;
            delete item;
            return content;
        }
        prev_item = item;
        item = item->next;
    }
    assert(!"This hash table didn't contain the given key!");
    return nullptr;
}

void TBHashTable::Delete(uint32 key)
{
    DeleteContent(Remove(key));
}

#ifdef TB_RUNTIME_DEBUG_INFO

void TBHashTable::Debug()
{
    TBTempBuffer line;
    line.AppendString("Hash table: ");
    int total_count = 0;
    for (uint32 i = 0; i < m_num_buckets; i++)
    {
        int count = 0;
        ITEM *item = m_buckets[i];
        while (item)
        {
            count++;
            item = item->next;
        }
        TBStr tmp; tmp.SetFormatted("%d ", count);
        line.AppendString(tmp);
        total_count += count;
    }
    TBStr tmp; tmp.SetFormatted(" (total: %d of %d buckets)\n", total_count, m_num_buckets);
    line.AppendString(tmp);
    TBDebugOut(line.GetData());
}

#endif // TB_RUNTIME_DEBUG_INFO

// == TBHashTableIterator ===============================================================

TBHashTableIterator::TBHashTableIterator(TBHashTable *hash_table)
    : m_hash_table(hash_table)
    , m_current_bucket(0)
    , m_current_item(nullptr)
{
}

void *TBHashTableIterator::GetNextContent()
{
    if (m_current_bucket == m_hash_table->m_num_buckets)
        return nullptr;
    if (m_current_item && m_current_item->next)
        m_current_item = m_current_item->next;
    else
    {
        if (m_current_item)
            m_current_bucket++;
        if (m_current_bucket == m_hash_table->m_num_buckets)
            return nullptr;
        while (m_current_bucket < m_hash_table->m_num_buckets)
        {
            m_current_item = m_hash_table->m_buckets[m_current_bucket];
            if (m_current_item)
                break;
            m_current_bucket++;
        }
    }
    return m_current_item ? m_current_item->content : nullptr;
}

} // namespace tb