// **********************************************************************
//
// Copyright (c) 2002
// IONA Technologies, Inc.
// Waltham, MA, USA
//
// All Rights Reserved
//
// **********************************************************************

#ifndef OB_HASHTABLE_I_H
#define OB_HASHTABLE_I_H

#include <OB/Hashtable.h>

namespace OB
{

// ----------------------------------------------------------------------
// Hashtable constructor and destructor
// ----------------------------------------------------------------------

template<class K, class T, class H>
Hashtable<K, T, H>::Hashtable(CORBA::ULong len, CORBA::Float load)
    : length_(len), load_(load), count_(0)
{
    threshold_ = (CORBA::ULong)(length_ * load_);

    if(len <= 15)
    {    
	table_ = stable_;
	memset(table_, 0, sizeof(node*) * length_);
    }
    else
    {
	table_ = new node*[length_];
	for(CORBA::ULong i = 0 ; i < length_ ; i++)
	    table_[i] = 0;
    }
}

template<class K, class T, class H>
Hashtable<K, T, H>::~Hashtable()
{
    //
    // Optimization: Don't call removeAll(), this is more efficient
    // (we don't need to de-allocate the allocator memory since the
    // allocator will do it when it is destroyed).
    //
    if(count_ > 0)
    {
	for(CORBA::ULong i = 0 ; i < length_ ; i++)
	{
	    node* n = table_[i];

	    //
	    // Set table_[i] to null now to avoid reentrant problems when
	    // key or value destructors manipulate the table.
	    //
	    table_[i] = 0;

	    while(n)
	    {
		node *n1 = n;
		n = n -> next;
		allocator_.destroy(n1);
	    }
	}
    }

    if(table_ != stable_)
	delete []table_;
}

// ----------------------------------------------------------------------
// Hashtable public member implementation
// ----------------------------------------------------------------------

template<class K, class T, class H>
void
Hashtable<K, T, H>::clear()
{
    removeAll();
}

template<class K, class T, class H>
bool
Hashtable<K, T, H>::containsKey(const K& key) const
{
    CORBA::ULong fullHash = H::hash(key);
    CORBA::ULong h = fullHash % length_;
	
    node* n = table_[h];
    while(n != 0)
    {
	if(n -> fullHash == fullHash && H::comp(n -> key, key))
	    return true;
	n = n -> next;
    }

    return false;
}

template<class K, class T, class H>
void
Hashtable<K, T, H>::put(const K& key, const T& value)
{
    CORBA::ULong fullHash = H::hash(key);
    CORBA::ULong h = fullHash % length_;

    node* n = table_[h];
    while(n != 0)
    {
        if(n -> fullHash == fullHash && H::comp(n -> key, key))
        {
            n -> value = value;
            return;
        }

        n = n -> next;
    }

    //
    // Insert at head of bucket
    //
    n = allocator_.allocate(1);
    allocator_.construct(n, node(key, value, table_[h]));

    table_[h] = n;

    count_++;
    if(count_ > threshold_)
        resize();
}

template<class K, class T, class H>
void
Hashtable<K, T, H>::remove(const K& key)
{
    CORBA::ULong fullHash = H::hash(key);
    CORBA::ULong h = fullHash % length_;
	
    node* prev = 0;
    node* n = table_[h];
    
    while(n != 0)
    {
	if(n -> fullHash == fullHash && H::comp(n -> key, key))
	    break;

	prev = n;
	n = n -> next;
    }

    if(n != 0)
    {
	if(prev != 0)
	    prev -> next = n -> next;
	else
	    table_[h] = n -> next;

	count_--;

	allocator_.destroy(n);
	allocator_.deallocate(n, 1);
    }
}

template<class K, class T, class H>
bool
Hashtable<K, T, H>::get(const K& key, T& value) const
{
    CORBA::ULong fullHash = H::hash(key);
    CORBA::ULong h = fullHash % length_;

    node* n = table_[h];
    while(n != 0)
    {
	if(n -> fullHash == fullHash && H::comp(n -> key, key))
	{
	    value = n -> value;
	    return true;
	}

	n = n -> next;
    }

    return false;
}

#ifdef HAVE_NO_TYPENAME
template<class K, class T, class H>
Hashtable<K, T, H>::Enumerator
Hashtable<K, T, H>::keys() const
#else
template<class K, class T, class H>
typename Hashtable<K, T, H>::Enumerator
Hashtable<K, T, H>::keys() const
#endif
{
    CORBA::ULong index = 0;
    K* keys = new K[count_];

    for(CORBA::ULong i = 0 ; i < length_ ; i++)
    {
	for(node* n = table_[i] ; n != 0 ; n = n -> next)
	    keys[index++] = n -> key;
    }

    Enumerator e(keys, count_);

    return e;
}

template<class K, class T, class H>
CORBA::ULong
Hashtable<K, T, H>::size() const
{
    return count_;
}

template<class K, class T, class H>
void
Hashtable<K, T, H>::displayStats(OB_STD(ostream)& os)
{
    CORBA::ULong most = 0;
    CORBA::ULong occupied = 0;
    for(CORBA::ULong i = 0 ; i < length_ ; i++)
    {
        CORBA::ULong bucketLen = 0;
        for(node* n = table_[i] ; n != 0 ; n = n -> next, bucketLen++)
            ;
        if(bucketLen > most)
            most = bucketLen;
        if(bucketLen > 0)
            occupied++;
    }
    os << "Hash table: " << length_ << " buckets.\n";
    os << "Keys      : " << count_ << "\n";
    os << "Average   : " << (double)count_/(double)occupied << "\n";
    os << "Largest   : " << most << "\n";
    os << OB_FLUSH;
}

// ----------------------------------------------------------------------
// Hashtable private member implementation
// ----------------------------------------------------------------------

template<class K, class T, class H>
void
Hashtable<K, T, H>::removeAll()
{
    if(count_ > 0)
    {
	for(CORBA::ULong i = 0 ; i < length_ ; i++)
	{
	    node* n = table_[i];

	    //
	    // Set table_[i] to null now to avoid reentrant problems when
	    // key or value destructors manipulate the table.
	    //
	    table_[i] = 0;
	
	    while(n)
	    {
		node *n1 = n;
		n = n -> next;

		allocator_.destroy(n1);
		allocator_.deallocate(n1, 1);
	    }
	}
    
	count_ = 0;
    }
}

template<class K, class T, class H>
void
Hashtable<K, T, H>::resize()
{
    CORBA::ULong i;
    CORBA::ULong size = length_ * 2 + 1;

    //
    // Create new table
    //
    node** table = new node*[size];
    for(i = 0 ; i < size ; i++)
        table[i] = 0;

    //
    // Migrate nodes from existing table to new one
    //
    for(i = 0 ; i < length_ ; i++)
    {
        node* n = table_[i];
        while(n != 0)
        {
            node* next = n -> next;
            CORBA::ULong h = n -> fullHash % size;
            n -> next = table[h];
            table[h] = n;
            n = next;
        }
    }

    //
    // Update state
    //
    length_ = size;
    threshold_ = (CORBA::ULong)(length_ * load_);
    if(table_ != stable_)
	delete []table_;
    table_ = table;
}

} // End of namespace OB

#endif
