gim_hash_table.h

Go to the documentation of this file.

#ifndef GIM_HASH_TABLE_H_INCLUDED
#define GIM_HASH_TABLE_H_INCLUDED

/*
-----------------------------------------------------------------------------
This source file is part of GIMPACT Library.

For the latest info, see http://gimpact.sourceforge.net/

Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
email: projectileman@yahoo.com

 This library is free software; you can redistribute it and/or
 modify it under the terms of EITHER:
   (1) The GNU Lesser General Public License as published by the Free
       Software Foundation; either version 2.1 of the License, or (at
       your option) any later version. The text of the GNU Lesser
       General Public License is included with this library in the
       file GIMPACT-LICENSE-LGPL.TXT.
   (2) The BSD-style license that is included with this library in
       the file GIMPACT-LICENSE-BSD.TXT.
   (3) The zlib/libpng license that is included with this library in
       the file GIMPACT-LICENSE-ZLIB.TXT.

 This library 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 files
 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.

-----------------------------------------------------------------------------
*/

#include "gim_radixsort.h"


#define GIM_INVALID_HASH 0xffffffff //!< A very very high value
#define GIM_DEFAULT_HASH_TABLE_SIZE 380
#define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4
#define GIM_HASH_TABLE_GROW_FACTOR 2

#define GIM_MIN_RADIX_SORT_SIZE 860 //!< calibrated on a PIII

template<typename T>
struct GIM_HASH_TABLE_NODE
{
    GUINT m_key;
    T m_data;
    GIM_HASH_TABLE_NODE()
    {
    }

    GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE & value)
    {
        m_key = value.m_key;
        m_data = value.m_data;
    }

    GIM_HASH_TABLE_NODE(GUINT key, const T & data)
    {
        m_key = key;
        m_data = data;
    }

    bool operator <(const GIM_HASH_TABLE_NODE<T> & other) const
        {
                if(m_key <  other.m_key) return true;
                return false;
        }

        bool operator >(const GIM_HASH_TABLE_NODE<T> & other) const
        {
                if(m_key >  other.m_key) return true;
                return false;
        }

        bool operator ==(const GIM_HASH_TABLE_NODE<T> & other) const
        {
                if(m_key ==  other.m_key) return true;
                return false;
        }
};

class GIM_HASH_NODE_GET_KEY
{
public:
        template<class T>
        inline GUINT operator()( const T& a)
        {
                return a.m_key;
        }
};



class GIM_HASH_NODE_CMP_KEY_MACRO
{
public:
        template<class T>
        inline int operator() ( const T& a, GUINT key)
        {
                return ((int)(a.m_key - key));
        }
};

class GIM_HASH_NODE_CMP_MACRO
{
public:
        template<class T>
        inline int operator() ( const T& a, const T& b )
        {
                return ((int)(a.m_key - b.m_key));
        }
};






template<typename T>
void gim_sort_hash_node_array(T * array, GUINT array_count)
{
    if(array_count<GIM_MIN_RADIX_SORT_SIZE)
    {
        gim_heap_sort(array,array_count,GIM_HASH_NODE_CMP_MACRO());
    }
    else
    {
        memcopy_elements_func cmpfunc;
        gim_radix_sort(array,array_count,GIM_HASH_NODE_GET_KEY(),cmpfunc);
    }
}






// Note: assumes long is at least 32 bits.
#define GIM_NUM_PRIME 28

static const GUINT gim_prime_list[GIM_NUM_PRIME] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  1610612741ul, 3221225473ul, 4294967291ul
};

inline GUINT gim_next_prime(GUINT number)
{
    //Find nearest upper prime
    GUINT result_ind = 0;
    gim_binary_search(gim_prime_list,0,(GIM_NUM_PRIME-2),number,result_ind);

    // inv: result_ind < 28
    return gim_prime_list[result_ind];
}




template<class T>
class gim_hash_table
{
protected:
    typedef GIM_HASH_TABLE_NODE<T> _node_type;

    //array< _node_type, SuperAllocator<_node_type> > m_nodes;
    gim_array< _node_type > m_nodes;
    //SuperBufferedArray< _node_type > m_nodes;
    bool m_sorted;

    GUINT * m_hash_table;
    GUINT m_table_size;
    GUINT m_node_size;
    GUINT m_min_hash_table_size;



    inline GUINT _find_cell(GUINT hashkey)
    {
        _node_type * nodesptr = m_nodes.pointer();
        GUINT start_index = (hashkey%m_table_size)*m_node_size;
        GUINT end_index = start_index + m_node_size;

        while(start_index<end_index)
        {
            GUINT value = m_hash_table[start_index];
            if(value != GIM_INVALID_HASH)
            {
                if(nodesptr[value].m_key == hashkey) return start_index;
            }
            start_index++;
        }
        return GIM_INVALID_HASH;
    }

    inline GUINT _find_avaliable_cell(GUINT hashkey)
    {
        _node_type * nodesptr = m_nodes.pointer();
        GUINT avaliable_index = GIM_INVALID_HASH;
        GUINT start_index = (hashkey%m_table_size)*m_node_size;
        GUINT end_index = start_index + m_node_size;

        while(start_index<end_index)
        {
            GUINT value = m_hash_table[start_index];
            if(value == GIM_INVALID_HASH)
            {
                if(avaliable_index==GIM_INVALID_HASH)
                {
                    avaliable_index = start_index;
                }
            }
            else if(nodesptr[value].m_key == hashkey)
            {
                return start_index;
            }
            start_index++;
        }
        return avaliable_index;
    }




    inline void _reserve_table_memory(GUINT newtablesize)
    {
        if(newtablesize==0) return;
        if(m_node_size==0) return;

        //Get a Prime size

        m_table_size = gim_next_prime(newtablesize);

        GUINT datasize = m_table_size*m_node_size;
        //Alloc the data buffer
        m_hash_table =  (GUINT *)gim_alloc(datasize*sizeof(GUINT));
    }

    inline void _invalidate_keys()
    {
        GUINT datasize = m_table_size*m_node_size;
        for(GUINT i=0;i<datasize;i++)
        {
            m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys
        }
    }

    inline void _clear_table_memory()
    {
        if(m_hash_table==NULL) return;
        gim_free(m_hash_table);
        m_hash_table = NULL;
        m_table_size = 0;
    }

    inline void _rehash()
    {
        _invalidate_keys();

        _node_type * nodesptr = m_nodes.pointer();
        for(GUINT i=0;i<(GUINT)m_nodes.size();i++)
        {
            GUINT nodekey = nodesptr[i].m_key;
            if(nodekey != GIM_INVALID_HASH)
            {
                //Search for the avaliable cell in buffer
                GUINT index = _find_avaliable_cell(nodekey);


                                if(m_hash_table[index]!=GIM_INVALID_HASH)
                                {//The new index is alreade used... discard this new incomming object, repeated key
                                    btAssert(m_hash_table[index]==nodekey);
                                        nodesptr[i].m_key = GIM_INVALID_HASH;
                                }
                                else
                                {
                                        //;
                                        //Assign the value for alloc
                                        m_hash_table[index] = i;
                                }
            }
        }
    }

    inline void _resize_table(GUINT newsize)
    {
        //Clear memory
        _clear_table_memory();
        //Alloc the data
        _reserve_table_memory(newsize);
        //Invalidate keys and rehash
        _rehash();
    }

    inline void _destroy()
    {
        if(m_hash_table==NULL) return;
        _clear_table_memory();
    }

    inline GUINT _assign_hash_table_cell(GUINT hashkey)
    {
        GUINT cell_index = _find_avaliable_cell(hashkey);

        if(cell_index==GIM_INVALID_HASH)
        {
            //rehashing
            _resize_table(m_table_size+1);
            GUINT cell_index = _find_avaliable_cell(hashkey);
            btAssert(cell_index!=GIM_INVALID_HASH);
        }
        return cell_index;
    }

    inline bool _erase_by_index_hash_table(GUINT index)
    {
        if(index >= m_nodes.size()) return false;
        if(m_nodes[index].m_key != GIM_INVALID_HASH)
        {
            //Search for the avaliable cell in buffer
            GUINT cell_index = _find_cell(m_nodes[index].m_key);

            btAssert(cell_index!=GIM_INVALID_HASH);
            btAssert(m_hash_table[cell_index]==index);

            m_hash_table[cell_index] = GIM_INVALID_HASH;
        }

        return this->_erase_unsorted(index);
    }

    inline bool _erase_hash_table(GUINT hashkey)
    {
        if(hashkey == GIM_INVALID_HASH) return false;

        //Search for the avaliable cell in buffer
        GUINT cell_index = _find_cell(hashkey);
        if(cell_index ==GIM_INVALID_HASH) return false;

        GUINT index = m_hash_table[cell_index];
        m_hash_table[cell_index] = GIM_INVALID_HASH;

        return this->_erase_unsorted(index);
    }




    inline GUINT _insert_hash_table(GUINT hashkey, const T & value)
    {
        if(hashkey==GIM_INVALID_HASH)
        {
            //Insert anyway
            _insert_unsorted(hashkey,value);
            return GIM_INVALID_HASH;
        }

        GUINT cell_index = _assign_hash_table_cell(hashkey);

        GUINT value_key = m_hash_table[cell_index];

        if(value_key!= GIM_INVALID_HASH) return value_key;// Not overrited

        m_hash_table[cell_index] = m_nodes.size();

        _insert_unsorted(hashkey,value);
        return GIM_INVALID_HASH;
    }


    inline GUINT _insert_hash_table_replace(GUINT hashkey, const T & value)
    {
        if(hashkey==GIM_INVALID_HASH)
        {
            //Insert anyway
            _insert_unsorted(hashkey,value);
            return GIM_INVALID_HASH;
        }

        GUINT cell_index = _assign_hash_table_cell(hashkey);

        GUINT value_key = m_hash_table[cell_index];

        if(value_key!= GIM_INVALID_HASH)
        {//replaces the existing
            m_nodes[value_key] = _node_type(hashkey,value);
            return value_key;// index of the replaced element
        }

        m_hash_table[cell_index] = m_nodes.size();

        _insert_unsorted(hashkey,value);
        return GIM_INVALID_HASH;

    }

    
    inline bool _erase_sorted(GUINT index)
    {
        if(index>=(GUINT)m_nodes.size()) return false;
        m_nodes.erase_sorted(index);
                if(m_nodes.size()<2) m_sorted = false;
        return true;
    }

    inline bool _erase_unsorted(GUINT index)
    {
        if(index>=m_nodes.size()) return false;

        GUINT lastindex = m_nodes.size()-1;
        if(index<lastindex && m_hash_table!=0)
        {
                        GUINT hashkey =  m_nodes[lastindex].m_key;
                        if(hashkey!=GIM_INVALID_HASH)
                        {
                                //update the new position of the last element
                                GUINT cell_index = _find_cell(hashkey);
                                btAssert(cell_index!=GIM_INVALID_HASH);
                                //new position of the last element which will be swaped
                                m_hash_table[cell_index] = index;
                        }
        }
        m_nodes.erase(index);
        m_sorted = false;
        return true;
    }


    inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos)
    {
        m_nodes.insert(_node_type(hashkey,value),pos);
        this->check_for_switching_to_hashtable();
    }

    inline GUINT _insert_sorted(GUINT hashkey, const T & value)
    {
        if(hashkey==GIM_INVALID_HASH || size()==0)
        {
            m_nodes.push_back(_node_type(hashkey,value));
            return GIM_INVALID_HASH;
        }
        //Insert at last position
        //Sort element


        GUINT result_ind=0;
        GUINT last_index = m_nodes.size()-1;
        _node_type * ptr = m_nodes.pointer();

        bool found = gim_binary_search_ex(
                ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());


        //Insert before found index
        if(found)
        {
            return result_ind;
        }
        else
        {
            _insert_in_pos(hashkey, value, result_ind);
        }
        return GIM_INVALID_HASH;
    }

    inline GUINT _insert_sorted_replace(GUINT hashkey, const T & value)
    {
        if(hashkey==GIM_INVALID_HASH || size()==0)
        {
            m_nodes.push_back(_node_type(hashkey,value));
            return GIM_INVALID_HASH;
        }
        //Insert at last position
        //Sort element
        GUINT result_ind;
        GUINT last_index = m_nodes.size()-1;
        _node_type * ptr = m_nodes.pointer();

        bool found = gim_binary_search_ex(
                ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());

        //Insert before found index
        if(found)
        {
            m_nodes[result_ind] = _node_type(hashkey,value);
        }
        else
        {
            _insert_in_pos(hashkey, value, result_ind);
        }
        return result_ind;
    }

    inline GUINT  _insert_unsorted(GUINT hashkey, const T & value)
    {
        m_nodes.push_back(_node_type(hashkey,value));
        m_sorted = false;
        return GIM_INVALID_HASH;
    }

    

public:

    gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE,
                     GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE,
                     GUINT min_hash_table_size = GIM_INVALID_HASH)
    {
        m_hash_table = NULL;
        m_table_size = 0;
        m_sorted = false;
        m_node_size = node_size;
        m_min_hash_table_size = min_hash_table_size;

        if(m_node_size!=0)
        {
            if(reserve_size!=0)
            {
                m_nodes.reserve(reserve_size);
                _reserve_table_memory(reserve_size);
                _invalidate_keys();
            }
            else
            {
                m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE);
                _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE);
                _invalidate_keys();
            }
        }
        else if(reserve_size!=0)
        {
            m_nodes.reserve(reserve_size);
        }

    }

    ~gim_hash_table()
    {
        _destroy();
    }

    inline bool is_hash_table()
    {
        if(m_hash_table) return true;
        return false;
    }

    inline bool is_sorted()
    {
        if(size()<2) return true;
        return m_sorted;
    }

    bool sort()
    {
        if(is_sorted()) return true;
        if(m_nodes.size()<2) return false;


        _node_type * ptr = m_nodes.pointer();
        GUINT siz = m_nodes.size();
        gim_sort_hash_node_array(ptr,siz);
        m_sorted=true;



        if(m_hash_table)
        {
            _rehash();
        }
        return true;
    }

    bool switch_to_hashtable()
    {
        if(m_hash_table) return false;
        if(m_node_size==0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
        if(m_nodes.size()<GIM_DEFAULT_HASH_TABLE_SIZE)
        {
            _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE);
        }
        else
        {
            _resize_table(m_nodes.size()+1);
        }

        return true;
    }

    bool switch_to_sorted_array()
    {
        if(m_hash_table==NULL) return true;
        _clear_table_memory();
        return sort();
    }

    bool check_for_switching_to_hashtable()
    {
        if(this->m_hash_table) return true;

        if(!(m_nodes.size()< m_min_hash_table_size))
        {
            if(m_node_size == 0)
            {
                m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
            }

            _resize_table(m_nodes.size()+1);
            return true;
        }
        return false;
    }

    inline void set_sorted(bool value)
    {
        m_sorted = value;
    }

    inline GUINT size() const
    {
        return m_nodes.size();
    }

    inline GUINT get_key(GUINT index) const
    {
        return m_nodes[index].m_key;
    }


    inline T * get_value_by_index(GUINT index)
    {
        return &m_nodes[index].m_data;
    }

    inline const T& operator[](GUINT index) const
    {
        return m_nodes[index].m_data;
    }

    inline T& operator[](GUINT index)
    {
        return m_nodes[index].m_data;
    }


    inline GUINT find(GUINT hashkey)
    {
        if(m_hash_table)
        {
            GUINT cell_index = _find_cell(hashkey);
            if(cell_index==GIM_INVALID_HASH) return GIM_INVALID_HASH;
            return m_hash_table[cell_index];
        }
                GUINT last_index = m_nodes.size();
        if(last_index<2)
        {
                        if(last_index==0) return GIM_INVALID_HASH;
            if(m_nodes[0].m_key == hashkey) return 0;
            return GIM_INVALID_HASH;
        }
        else if(m_sorted)
        {
            //Binary search
            GUINT result_ind = 0;
                        last_index--;
            _node_type *  ptr =  m_nodes.pointer();

            bool found = gim_binary_search_ex(ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());


            if(found) return result_ind;
        }
        return GIM_INVALID_HASH;
    }


    inline T * get_value(GUINT hashkey)
    {
        GUINT index = find(hashkey);
        if(index == GIM_INVALID_HASH) return NULL;
        return &m_nodes[index].m_data;
    }


    inline bool erase_by_index(GUINT index)
    {
        if(index > m_nodes.size()) return false;

        if(m_hash_table == NULL)
        {
            if(is_sorted())
            {
                return this->_erase_sorted(index);
            }
            else
            {
                return this->_erase_unsorted(index);
            }
        }
        else
        {
            return this->_erase_by_index_hash_table(index);
        }
        return false;
    }



    inline bool erase_by_index_unsorted(GUINT index)
    {
        if(index > m_nodes.size()) return false;

        if(m_hash_table == NULL)
        {
            return this->_erase_unsorted(index);
        }
        else
        {
            return this->_erase_by_index_hash_table(index);
        }
        return false;
    }



    inline bool erase_by_key(GUINT hashkey)
    {
        if(size()==0) return false;

        if(m_hash_table)
        {
            return this->_erase_hash_table(hashkey);
        }
        //Binary search

        if(is_sorted()==false) return false;

        GUINT result_ind = find(hashkey);
        if(result_ind!= GIM_INVALID_HASH)
        {
            return this->_erase_sorted(result_ind);
        }
        return false;
    }

    void clear()
    {
        m_nodes.clear();

        if(m_hash_table==NULL) return;
        GUINT datasize = m_table_size*m_node_size;
        //Initialize the hashkeys.
        GUINT i;
        for(i=0;i<datasize;i++)
        {
            m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys
        }
                m_sorted = false;
    }


    inline GUINT insert(GUINT hashkey, const T & element)
    {
        if(m_hash_table)
        {
            return this->_insert_hash_table(hashkey,element);
        }
        if(this->is_sorted())
        {
            return this->_insert_sorted(hashkey,element);
        }
        return this->_insert_unsorted(hashkey,element);
    }


    inline GUINT insert_override(GUINT hashkey, const T & element)
    {
        if(m_hash_table)
        {
            return this->_insert_hash_table_replace(hashkey,element);
        }
        if(this->is_sorted())
        {
            return this->_insert_sorted_replace(hashkey,element);
        }
        this->_insert_unsorted(hashkey,element);
        return m_nodes.size();
    }




    inline GUINT insert_unsorted(GUINT hashkey,const T & element)
    {
        if(m_hash_table)
        {
            return this->_insert_hash_table(hashkey,element);
        }
        return this->_insert_unsorted(hashkey,element);
    }


};



#endif // GIM_CONTAINERS_H_INCLUDED