umap.h

/*
===========================================================================
Copyright (C) 2024 the OpenMoHAA team
 
This file is part of OpenMoHAA source code.
 
OpenMoHAA source code is free software; you can redistribute it
and/or modify it 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.
 
OpenMoHAA source code 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 OpenMoHAA source code; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/
 
// umap.h: Hash table based map class template.  Maps text based keys to previously
// stored data.
//
 
#pragma once
 
#include "str.h"
#include <stdlib.h>
 
template<class Type>
class UMap : public Class
{
private:
    struct hashnode_s {
        str         key;
        Type        value;
        hashnode_s *next;
 
        hashnode_s(const char *k, Type v, hashnode_s *n)
            : key(k)
            , value(v)
            , next(n) {};
        hashnode_s(const str& k, Type v, hashnode_s *n)
            : key(k.c_str())
            , value(v)
            , next(n) {};
    };
 
    hashnode_s **m_heads;
    Type         m_defaultvalue;
 
    unsigned m_tablesize;
    unsigned m_numentries;
    unsigned m_tablesizemask;
 
    unsigned getHash(const char *key);
 
public:
    void     Clear(void);
    unsigned getNumEntries(void) const;
    void     DeleteDefaultValues(void);
 
    Type& operator[](const char *key);
    Type& operator[](const str& key);
 
    const char *getKeyByIndex(int index) const;
    Type&       getValueByIndex(unsigned index);
 
    ~UMap<Type>();
 
    UMap(Type defaultvalue, unsigned tablesize = 64)
        : m_defaultvalue(defaultvalue)
        , m_tablesize(tablesize)
    {
        int i;
        int bits;
 
        assert(m_tablesize > 0);
 
        m_heads = new hashnode_s *[m_tablesize];
        memset(m_heads, 0, sizeof(*m_heads) * m_tablesize);
 
        m_numentries    = 0;
        m_tablesizemask = 0;
 
        bits = 0;
        for (i = 0; i < 32; i++) {
            if (m_tablesize & (1 << i)) {
                bits++;
            }
        }
 
        if (bits == 1) {
            m_tablesizemask = m_tablesize - 1;
        }
    };
 
    UMap(UMap<Type>& map)
        : m_defaultvalue(map.m_defaultvalue)
        , m_tablesize(map.m_tablesize)
    {
        unsigned     i;
        hashnode_s  *node;
        hashnode_s **prev;
 
        assert(m_tablesize > 0);
 
        m_heads         = new hashnode_s *[m_tablesize];
        m_numentries    = map.m_numentries;
        m_tablesizemask = map.m_tablesizemask;
 
        for (i = 0; i < m_tablesize; i++) {
            if (!map.m_heads[i]) {
                m_heads[i] = NULL;
                continue;
            }
 
            prev = &m_heads[i];
            for (node = map.m_heads[i]; node != NULL; node = node->next) {
                *prev = new hashnode_s(node->key, node->value, NULL);
                prev  = &(*prev)->next;
            }
        }
    };
};
 
template<class Type>
UMap<Type>::~UMap<Type>()
{
    Clear();
    delete m_heads;
}
 
template<class Type>
unsigned UMap<Type>::getHash(const char *key)
{
    unsigned    h;
    const char *v;
 
    if (m_tablesizemask) {
        h = 0;
        for (v = key; *v != '\0'; v++) {
            h = (64 * h + unsigned(*v)) & m_tablesizemask;
        }
    } else {
        h = 0;
        for (v = key; *v != '\0'; v++) {
            h = (64 * h + unsigned(*v)) % m_tablesize;
        }
    }
 
    return h;
}
 
template<class Type>
Type& UMap<Type>::operator[](const char *key)
{
    hashnode_s **head;
    hashnode_s  *node;
    unsigned     hash;
 
    // FIXME
    // if list was always sorted, could just insert new node as soon as we get
    // node whose key is greater than the search key
    hash = getHash(key);
    head = &m_heads[hash];
    if (*head) {
        for (node = *head; node != NULL; node = node->next) {
            if (node->key == key) {
                return node->value;
            }
        }
    }
 
    m_numentries++;
 
    *head = new hashnode_s(key, m_defaultvalue, *head);
 
    return (*head)->value;
}
 
template<class Type>
const char *UMap<Type>::getKeyByIndex(int index) const
{
    unsigned head;
 
    for (head = 0; head < m_tablesize; head++) {
        hashnode_s *node;
 
        for (node = m_heads[head]; node; node = node->next) {
            if (!index) {
                return node->key.c_str();
            }
 
            index--;
        }
    }
 
    return NULL;
}
 
template<class Type>
Type& UMap<Type>::getValueByIndex(unsigned index)
{
    unsigned head;
 
    ASSERT(index < getNumEntries());
 
    for (head = 0; head < m_tablesize; head++) {
        hashnode_s *node;
 
        for (node = m_heads[head]; node; node = node->next) {
            if (!index) {
                return node->value;
            }
 
            index--;
        }
    }
 
    // Should never, EVER get here.
    ASSERT(0);
    return m_defaultvalue;
}
 
template<class Type>
inline void UMap<Type>::DeleteDefaultValues(void)
{
    unsigned head;
 
    for (head = 0; head < m_tablesize; head++) {
        hashnode_s *node;
 
        while (m_heads[head] && m_heads[head]->value == m_defaultvalue) {
            node          = m_heads[head];
            m_heads[head] = node->next;
            delete node;
            m_numentries--;
        }
 
        if (!m_heads[head]) {
            continue;
        }
 
        for (node = m_heads[head]; node->next;) {
            hashnode_s *next = node->next;
 
            if (next->value == m_defaultvalue) {
                node->next = next->next;
                delete next;
                m_numentries--;
            } else {
                node = node->next;
            }
        }
    }
}
 
template<class Type>
inline Type& UMap<Type>::operator[](const str& key)
{
    return this->[key.c_str()];
}
 
template<class Type>
void UMap<Type>::Clear(void)
{
    unsigned    i;
    hashnode_s *node;
    hashnode_s *next;
 
    for (i = 0; i < m_tablesize; i++) {
        next = m_heads[i];
        while (next != NULL) {
            node = next;
            next = next->next;
            delete node;
        }
 
        m_heads[i] = NULL;
    }
 
    m_numentries = 0;
}
 
template<class Type>
inline unsigned UMap<Type>::getNumEntries(void) const
{
    return m_numentries;
}