Go to the documentation of this file.00001
00010
00011
00012
00013 #ifndef _HASH_H_
00014 # error This header should not be included directly! include hash.h instead
00015 #endif // _HASH_H_
00016
00017 #pragma once
00018
00019 #define HASH_HAS_ERASE 1
00020
00021 #include <stdlib.h>
00022 #include "mlist.h"
00023
00024 #include "morton.h"
00025
00026
00027
00028 template < typename Data > class Hash
00029
00030 {
00031 public:
00032 typedef uint cntr ;
00033
00034
00035 static const cntr HASH_SIZE = ((cntr)1<<HASH_BITS) ;
00036 static const cntr HASH_MASK = HASH_SIZE-1 ;
00037
00038
00039 typedef struct KeyData
00040 {
00041 Key key ;
00042 Data data ;
00043
00045 bool operator==( const struct KeyData& rhs) const { return key == rhs.key ; }
00046
00048 bool operator!=( const struct KeyData& rhs) const { return key != rhs.key ; }
00049
00050 } KeyData ;
00051 static KeyData KD_INV ;
00052
00053 class iterator ;
00054
00055 public:
00056 typedef List<KeyData> KeyBucket ;
00057 typedef typename KeyBucket::iterator keybucket_iterator ;
00058 typedef typename KeyBucket::const_iterator keybucket_const_iterator ;
00059
00060 protected:
00061
00062 KeyBucket *_hash ;
00063
00064 public:
00065
00066 Hash () { _hash = new KeyBucket[HASH_SIZE] ; }
00067 ~Hash () { delete [] _hash ; }
00068
00069 void reset()
00070 {
00071 cntr n = HASH_SIZE ;
00072 KeyBucket *ptr = _hash ;
00073 for( ; n > 0 ; --n, ++ptr )
00074 {
00075 (*ptr).clear() ;
00076 }
00077 KD_INV.key = KEY_INV ;
00078 }
00079
00080 cntr size() const
00081 {
00082 cntr s = 0 ;
00083 cntr n = HASH_SIZE ;
00084 KeyBucket *ptr = _hash ;
00085 for( ; n > 0 ; --n, ++ptr )
00086 s += ptr->size() ;
00087 return s ;
00088 }
00089
00090 void stats() const
00091 {
00092 static const cntr MAX_COLLISION = 32 ;
00093 cntr colls[MAX_COLLISION] ;
00094 memset( colls, 0, MAX_COLLISION*sizeof(cntr) ) ;
00095 KeyBucket *ptr = _hash ;
00096 for( cntr n = HASH_SIZE ; n > 0 ; --n, ++ptr )
00097 {
00098 cntr s = ptr->size() ;
00099 if( s >= MAX_COLLISION ) s = MAX_COLLISION-1 ;
00100 ++colls[s] ;
00101 }
00102
00103 printf( "Hashtable collisions: [\t") ;
00104 for( cntr n = 0 ; n < MAX_COLLISION ; ++n )
00105 printf( "%d\t", colls[n] ) ;
00106 printf( "\t]\n") ;
00107 }
00108
00109 inline cntr hash( Key k ) const ;
00110
00111 bool insert( KeyData d )
00112 {
00113 cntr h = hash( d.key ) ;
00114 KeyBucket &l = _hash[h] ;
00115 return l.insert_unique( d ) ;
00116 }
00117
00118 const KeyData operator[] ( Key k ) const
00119 {
00120 cntr h = hash( k ) ;
00121 KeyData kd ; kd.key = k ;
00122 keybucket_const_iterator it = _hash[h].cfind( kd ) ;
00123 if( !it() ) return KD_INV ;
00124 return *it ;
00125 }
00126
00127 KeyData &operator[] ( Key k )
00128 {
00129 cntr h = hash( k ) ;
00130 KeyData kd ; kd.key = k ;
00131 keybucket_iterator it = _hash[h].find( kd ) ;
00132 if( !it() ) return KD_INV ;
00133 return *it ;
00134 }
00135
00136 KeyData erase( Key k )
00137 {
00138 cntr h = hash( k ) ;
00139 KeyData kd ; kd.key = k ;
00140 if( _hash[h].remove( kd ) )
00141 return kd ;
00142 return KD_INV ;
00143 }
00144
00145 bool contains( Key k ) const { return (*this)[k].key == k ; }
00146
00147
00148
00149
00150 public :
00152 class iterator
00153 {
00154 public :
00155
00157 iterator( Hash<Data> &hash_, Key id_ = 0 ) : _ptr(hash_._hash+id_), _last(hash_._hash+HASH_SIZE)
00158 {
00159 while( _ptr != _last && _ptr->empty() )
00160 ++_ptr ;
00161 if( _ptr != _last )
00162 _l_it = _ptr->begin() ;
00163 }
00164
00166 ~iterator() {}
00167
00169 iterator( const iterator &it ) : _ptr(it._ptr), _last(it._last), _l_it(it._l_it) {}
00170
00172 iterator &operator = ( const iterator &it )
00173 { _ptr = it._ptr; _last = it._last; _l_it = it._l_it ; return *this; }
00174
00175
00176
00177 public :
00179 inline bool operator ==( const iterator &it ) const { return _ptr == it._ptr && _l_it == it._l_it ; }
00181 inline bool operator !=( const iterator &it ) const { return _ptr != it._ptr || _l_it != it._l_it ; }
00182
00184 inline bool operator ()() const { return _ptr != _last ; }
00185
00187 inline const Key &key() const { return (*_l_it).key ; }
00188
00190 inline const Data &operator * () const { return (*_l_it).data ; }
00191
00193 inline Data &operator * () { return (*_l_it).data ; }
00194
00196 inline iterator &operator ++() {
00197 if( !(++_l_it)() )
00198 {
00199 while( _ptr != _last && (*(++_ptr)).empty() ) ;
00200 if( _ptr != _last )
00201 _l_it = _ptr->begin() ;
00202 }
00203 return *this ;
00204 }
00205
00206
00207
00208 private :
00209 KeyBucket *_ptr ;
00210 const KeyBucket *_last ;
00211 keybucket_iterator _l_it ;
00212 };
00213
00214
00215
00216 public :
00218 class const_iterator
00219 {
00220 public :
00221
00223 const_iterator( Hash<Data> &hash_, Key id_ = 0 ) : _ptr(hash_._hash+id_), _last(hash_._hash+HASH_SIZE)
00224 {
00225 while( _ptr != _last && _ptr->empty() )
00226 ++_ptr ;
00227 if( _ptr != _last )
00228 _l_it = _ptr->cbegin() ;
00229 }
00230
00232 ~const_iterator() {}
00233
00235 const_iterator( const const_iterator &it ) : _ptr(it._ptr), _last(it._last), _l_it(it._l_it) {}
00236
00238 const_iterator &operator = ( const const_iterator &it )
00239 { _ptr = it._ptr; _last = it._last; _l_it = it._l_it ; return *this; }
00240
00241
00242
00243 public :
00245 inline bool operator ==( const const_iterator &it ) const { return _ptr == it._ptr && _l_it == it._l_it ; ; }
00247 inline bool operator !=( const const_iterator &it ) const { return _ptr != it._ptr || _l_it != it._l_it ; ; }
00248
00250 inline bool operator ()() const { return _ptr != _last ; }
00251
00253 inline const Key &key() const { return (*_l_it).key ; }
00254
00256 inline const Data &operator * () const { return (*_l_it).data ; }
00257
00259 inline const_iterator &operator ++() {
00260 if( !(++_l_it)() )
00261 {
00262 while( _ptr != _last && (*(++_ptr)).empty() ) ;
00263 if( _ptr != _last )
00264 _l_it = _ptr->cbegin() ;
00265 }
00266 return *this ;
00267 }
00268
00269
00270
00271 private :
00272 const KeyBucket * _ptr ;
00273 const KeyBucket * const _last ;
00274 keybucket_const_iterator _l_it ;
00275 };
00276
00277 public :
00279 iterator begin( cntr id = 0 ) { return iterator( *this, id ) ; }
00281 const_iterator cbegin( cntr id = 0 ) { return const_iterator( *this, id ) ; }
00282 };
00283
00284
00285
00287 template <> inline Hash<real >::cntr Hash<real >::hash( Key k ) const { return k & HASH_MASK ; }
00288
00290 template <> inline Hash<Level>::cntr Hash<Level>::hash( Key k ) const { return (k>>NON_HASH_BITS) & HASH_MASK ; }