// **********************************************************************
//
// Copyright (c) 1999
// Object Oriented Concepts, Inc.
// Billerica, MA, USA
//
// All Rights Reserved
//
// **********************************************************************

#ifndef OB_HASHTABLE_I_H
#define OB_HASHTABLE_I_H

// ----------------------------------------------------------------------
// OBHashtable template
// ----------------------------------------------------------------------


// ----------------------------------------------------------------------
// OBHashtable constructor
// ----------------------------------------------------------------------

template<class K, class T, class LS>
OBHashtable<K, T, LS>::OBHashtable(CORBA_ULong len, CORBA_Float load)
    : length_(len), load_(load), count_(0)
{
    threshold_ = (CORBA_ULong)(length_ * load_);
    table_ = new node*[length_];
    for(CORBA_ULong i = 0 ; i < length_ ; i++)
        table_[i] = 0;
}

template<class K, class T, class LS>
OBHashtable<K, T, LS>::~OBHashtable()
{
    removeAll();
    delete []table_;
}

// ----------------------------------------------------------------------
// OBHashtable public member implementation
// ----------------------------------------------------------------------

template<class K, class T, class LS>
void
OBHashtable<K, T, LS>::clear()
{
    LS sync(*this);

    removeAll();

    for(CORBA_ULong i = 0 ; i < length_ ; i++)
        table_[i] = 0;
}

template<class K, class T, class LS>
bool
OBHashtable<K, T, LS>::contains(const K& key) const
{
    LS sync(*this);

    CORBA_ULong fullHash = OBHash(key);
    CORBA_ULong h = fullHash % length_;

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

    return false;
}

template<class K, class T, class LS>
void
OBHashtable<K, T, LS>::put(const K& key, T value)
{
    LS sync(*this);

    CORBA_ULong fullHash = OBHash(key);
    CORBA_ULong h = fullHash % length_;

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

        n = n -> next;
    }

    //
    // Insert at head of bucket
    //
    n = new node(key, value, table_[h]);
    table_[h] = n;

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

template<class K, class T, class LS>
void
OBHashtable<K, T, LS>::remove(const K& key)
{
    LS sync(*this);

    CORBA_ULong fullHash = OBHash(key);
    CORBA_ULong h = fullHash % length_;

    node* prev = 0;
    node* n = table_[h];

    while(n != 0)
    {
        if(n -> fullHash == fullHash && OBHashCompare(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_--;
        delete n;
    }
}

template<class K, class T, class LS>
bool
OBHashtable<K, T, LS>::get(const K& key, T& value) const
{
    LS sync(*this);

    CORBA_ULong fullHash = OBHash(key);
    CORBA_ULong h = fullHash % length_;

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

        n = n -> next;
    }

    return false;
}

#ifdef HAVE_NO_TYPENAME
template<class K, class T, class LS>
OBHashtable<K, T, LS>::Enumerator
OBHashtable<K, T, LS>::keys() const
#else
template<class K, class T, class LS>
typename OBHashtable<K, T, LS>::Enumerator
OBHashtable<K, T, LS>::keys() const
#endif
{
    LS sync(*this);

    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 LS>
void
OBHashtable<K, T, LS>::displayStats(ostream& os)
{
    LS sync(*this);

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

// ----------------------------------------------------------------------
// OBHashtable private member implementation
// ----------------------------------------------------------------------

template<class K, class T, class LS>
void
OBHashtable<K, T, LS>::removeAll()
{
    CORBA_ULong len = length_;
    CORBA_ULong num = count_;
    CORBA_ULong i, j;

    if(table_ != 0)
    {
        //
        // Copy nodes to a temporary array to avoid reentrant problems
        // when key or value destructors manipulate the table
        //
        node** temp = new node*[num];
        j = 0;
        for(i = 0 ; i < len ; i++)
        {
            for(node* n = table_[i] ; n != 0 ; n = n -> next)
                temp[j++] = n;
        }

        //
        // Clear table
        //
        for(i = 0 ; i < len ; i++)
            table_[i] = 0;

        count_ = 0;

        //
        // Delete old nodes
        //
        for(i = 0 ; i < num ; i++)
            delete temp[i];

        delete []temp;
    }
}

template<class K, class T, class LS>
void
OBHashtable<K, T, LS>::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_);
    delete []table_;
    table_ = table;
}

#endif
