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;
    }