diff options
Diffstat (limited to 'src/hmap.cpp')
| -rw-r--r-- | src/hmap.cpp | 206 |
1 files changed, 206 insertions, 0 deletions
diff --git a/src/hmap.cpp b/src/hmap.cpp new file mode 100644 index 0000000..81db939 --- /dev/null +++ b/src/hmap.cpp @@ -0,0 +1,206 @@ +/*:* + *: File: ./src/hmap.cpp + *: + *: yChat; Homepage: www.yChat.org; Version 0.5.6-BASIC + *: + *: Copyright (C) 2003, 2004 Paul C. Buetow, Volker Richter + *: Copyright (C) 2005 EXA Digital Solutions GbR + *: + *: This program 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. + *: + *: This program 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 this program; if not, write to the Free Software + *: Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + *:*/ + +#ifndef hmap_cpp +#define hmap_cpp + + +#include "hmap.h" + +using namespace std; + +bool isPrime( int n ); +int nextPrime( int n ); + +// Construct the hash table. +template <class obj_type, class key_type> +hmap<obj_type, key_type>::hmap( double mop ) + : maxOccupiedPercentage(mop), array( nextPrime( 101 ) ) +{ + cout << "hmap Constructor" << endl; + lookups = 0; + make_empty( ); +} + +// Insert item x into the hash table. If the item is +// already present, do nothing +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::add_elem( const obj_type &x, const key_type &k ) +{ + // Insert x as active + int currentPos = findPos( k ); + if( isActive( currentPos ) ) + return; + + array[ currentPos ] = hash_entry( x, k, ACTIVE ); + // cout << "Inserted=" << x << "= at " << currentPos << endl; + if( ++occupied > array.size( ) * maxOccupiedPercentage ) + rehash( ); +} + +// Expand the hash table. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::rehash( ) +{ + vector<hash_entry> oldArray = array; + + // Create new double-sized, empty table + array.resize( nextPrime( 2 * oldArray.size( ) ) ); + for( int j = 0; j < array.size( ); j++ ) + array[ j ].info = EMPTY; + + // Copy table over + make_empty( ); + for( int i = 0; i < oldArray.size( ); i++ ) + if( oldArray[ i ].info == ACTIVE ) + add_elem( oldArray[ i ].element, oldArray[ i ].key ); +} + +// Hash function, can only handle strings. +// If you want to hash other objects you will have to +// create a hash table for them +template <class obj_type, class key_type> +unsigned int hmap<obj_type, key_type>::hash( const string & key ) const +{ + unsigned int hashVal = 0; + // cout << key << "%"; + + for( size_t i = 0; i < key.size(); i++ ) + hashVal = ( hashVal << 5 ) ^ key[ i ] ^ hashVal; + + return hashVal; +} + +// Method that performs quadratic probing resolution. +// Return the position where the search for x terminates. +template <class obj_type, class key_type> +int hmap<obj_type, key_type>::findPos( const key_type &k ) +{ + int collisionNum = 0; + int currentPos = hash( k ) % array.size( ); + lookups++; + + while( array[ currentPos ].info != EMPTY && + array[ currentPos ].key != k ) + { + // cout << array[ currentPos ].element << "!=" << x << endl; + lookups++; + currentPos += 2 * ++collisionNum - 1; // Compute ith probe + + if( currentPos >= array.size( ) ) + currentPos -= array.size( ); + } + + // cout << currentPos << " "; + return currentPos; +} + +// Remove item x from the hash table. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::del_elem( const key_type & k ) +{ + int currentPos = findPos( k ); + if( isActive( currentPos ) ) + array[ currentPos ].info = DELETED; +} + +// Find item x in the hash table. +// Return a pointer to the matching item or 0 if not found +template <class obj_type, class key_type> +obj_type hmap<obj_type, key_type>::get_elem( const key_type &k ) +{ + int currentPos = findPos( k ); + if( isActive( currentPos ) ) + return array[ currentPos ].element; + else + return 0; +} + +// Make the hash table logically empty. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::make_empty( ) +{ + occupied = 0; + for( int i = 0; i < array.size( ); i++ ) + array[ i ].info = EMPTY; +} + +// Return true if currentPos exists and is active. +template <class obj_type, class key_type> +bool hmap<obj_type, key_type>::isActive( int currentPos ) const +{ + return array[ currentPos ].info == ACTIVE; +} + + +// Internal method to test if a positive number is prime. +// Not an efficient algorithm. +template <class obj_type, class key_type> +bool hmap<obj_type, key_type>::isPrime( int n ) const +{ + if( n == 2 || n == 3 ) + return true; + + else if( n == 1 || n % 2 == 0 ) + return false; + + for( int i = 3; i * i <= n; i += 2 ) + if( n % i == 0 ) + return false; + + return true; +} + +// Internal method to return a prime number at least as large as n. +// Assumes n > 0. +template <class obj_type, class key_type> +int hmap<obj_type, key_type>::nextPrime( int n ) const +{ + if( n % 2 == 0 ) + n++; + + for( ; !isPrime( n ); n += 2 ) + ; + + return n; +} +template<class obj_type, class key_type> +void +hmap<obj_type, key_type>::run_func( void (*func)(obj_type) ) +{ + for( int i = 0; i < array.size( ); i++ ) + if ( array[i].info == ACTIVE ) + ( *func ) ( array[i].element ); +} + +template<class obj_type, class key_type> +void +hmap<obj_type, key_type>::run_func( void (*func)(obj_type, void*), void* v_arg ) +{ + for( int i = 0; i < array.size( ); i++ ) + if ( array[i].info == ACTIVE ) + ( *func ) ( array[i].element, v_arg ); +} + +#endif + |