---

hash.h

/*
 *                         Sun Public License Notice
 *
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"); you may not use this file except
 * in compliance with the License. A copy of the License is available
 * at http://www.sun.com/
 *
 * The Original Code is the Java Profiler module.  The Initial Developers
 * of the Original Code are Jan Stola, Pavel Vacha, Michal Pise, Petr Luner,
 * Lukas Petru and Marek Przeczek.
 *
 * Portions created by Jan Stola are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Portions created by Pavel Vacha are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Portions created by Michal Pise are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Portions created by Petr Luner are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Portions created by Lukas Petru are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Portions created by Marek Przeczek are Copyright (C) 2000-2001.
 * All Rights Reserved.
 *
 * Contributors: Jan Stola, Pavel Vacha, Michal Pise, Petr Luner,
 *               Lukas Petru and Marek Przeczek.
 */

#ifndef _HASH_H_
#define _HASH_H_

#include "../main/includes.h"
#include "../list/list.h"

template<class T, class K, class L> class Hash {

        enum e {
                
                HASH_LIST_LIMIT = 3
        };

private:

        List<T,L>* _table;

        unsigned int _size;

        unsigned int _mask;

        unsigned int _numItems;

        unsigned int _index;

public:

        Hash() :

                _size( 1<<10),
                _numItems( 0),
                _index(0) {
        
                _table = new List<T,L>[_size];
                _mask = _size-1;
        }

        ~Hash() { delete[] _table;}

        void clear() {

                List<T,L>* p = _table;
                for( unsigned int i = 0; i < _size; i++, p++) p->clear();
        }

        T* first() {

                List<T,L>* p = _table;
                T* q;

                for( _index = 0; _index < _size; _index++, p++)
                        if( q = p->first()) return q;

                return NULL;
        }

        T* next( T* item) {

                T* q = static_cast<T*>( static_cast<L*>( item->L::next()));
                if( q) return q;

                List<T,L>* p = &_table[++_index];

                for( ; _index < _size; _index++)
                        if( q = p->first()) return q;

                return NULL;
        }

        T* addNoRehash( T* item) {
        
                if( !item) return NULL;

                K key;
                int h = T::hashKey( item->getKey( key));

                _table[makeIndex( h)].add( item);
                _numItems++;

                return item;
        }

        T* add( T* item) {

                if( !addNoRehash( item)) return NULL;
                if( _numItems > _size*HASH_LIST_LIMIT+5) rehash( _size<<1);

                return item;
        }

        T* removeNoRehash( T* item) {

                if( !item) return NULL;


                item->L::remove();
                _numItems--;

                return item;
        }

        T* remove( T* item) {

                if( !removeNoRehash( item)) return NULL;

                unsigned int sz = _size>>1;
                if( _numItems < sz*HASH_LIST_LIMIT) rehash( sz);

                return item;
        }

        T* get( const K& key) {

                int h = T::hashKey( key);
                List<T,L>* list = &_table[makeIndex( h)];
                T* p = list->first();

                while( p && !(*p == key)) p = list->next( p);

                if( p) list->add( list->remove( p));

                return p;
        }

        int forEach( int (*f)( T*, void**), void** inout) {
        
                List<T,L>* p = _table;
        
                for( unsigned int i = 0; i < _size; i++, p++) {
        
                        int rc = p->forEach( f, inout);
                        if( rc) return rc;
                }

                return 0;
        }

private:

        unsigned int makeIndex( int x) {

                unsigned int key = (unsigned)x;

                key += (key << 12);
                key ^= (key >> 22);
                key += (key << 4);
                key ^= (key >> 9);
                key += (key << 10);
                key ^= (key >> 2);
                key += (key << 7);
                key ^= (key >> 12);

                unsigned int index = key & _mask;
                if( index >= _size) index >>= 1;

                return index;
        }

        void rehash( unsigned int sz) {

                unsigned int size = _size;
                List<T,L>* table = _table;

                _size = sz;
                _table = new List<T,L>[_size];

                _mask = _size-1;
                _numItems = 0;

                _index = 0;

                List<T,L>* p = table;
        
                for( unsigned int i = 0; i < size; i++, p++)
                        while( addNoRehash( p->remove( p->first())));

                delete[] table;
        }

#ifdef _DEBUG
public:

        void printStatistics() const {

                cout << "table size: "  << _size     << endl;
                cout << "total items: " << _numItems << endl;

                if( !_size) return;

                unsigned int max = 0, len;
                unsigned int i, j;

                List<T,L>* p;
                int hist[10];

                for( i = 0, p = _table; i < _size; i++, p++)
                        if ((len = p->length()) > max) max = len;

                memset( hist, 0, 10*sizeof(int));

                for( i = 0, p = _table; i < _size; i++, p++) {

                        len = p->length();
                        for( j = 0; j < 10; j++)

                                if( len <= max*(j+1)/10) {

                                        hist[j]++;
                                        break;
                                }
                }

                cout << "distribution of list length:" << endl;
                for( j = 0; j < 10; j++)
                        cout << max*j/10 << " - " << max*(j+1)/10 << " items: " << (hist[j]*100)/_size << "%" << endl;
        }
#endif
};

#endif // _HASH_H_

---