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
00020 #include <stdlib.h>
00021
00022 #include "morton.h"
00023
00024
00025
00026 template < typename Data > class Hash
00027
00028 {
00029 public:
00030 typedef uint cntr ;
00031
00032
00033 static const cntr HASH_SIZE = ((cntr)1<<HASH_BITS) ;
00034 static const cntr HASH_MASK = HASH_SIZE-1 ;
00035 static const cntr SKIP_MINI = 11 ;
00036 static const cntr SKIP_BITS = 3 ;
00037 static const cntr SKIP_MASK = ((cntr)1<<SKIP_BITS)-1 ;
00038
00039 typedef struct { Key key ; Data data ; } KeyData ;
00040 static KeyData KD_INV ;
00041
00042 protected:
00043
00044 KeyData *_hash ;
00045
00046 public:
00047
00048 Hash () { _hash = new KeyData[HASH_SIZE] ; reset() ; }
00049 ~Hash () { delete [] _hash ; }
00050
00051 void reset() { memset( _hash, KEY_INV, HASH_SIZE*sizeof(KeyData) ) ; KD_INV.key = KEY_INV ; }
00052
00053 inline cntr hash( Key k ) const ;
00054
00055 cntr size() const
00056 {
00057 cntr s = 0 ;
00058 cntr n = HASH_SIZE ;
00059 KeyData *ptr = _hash ;
00060 for( ; n > 0 ; --n, ++ptr )
00061 s += ( ptr->key != KEY_INV ) ;
00062 return s ;
00063 }
00064
00065 bool insert( KeyData d )
00066 {
00067 cntr h = hash( d.key ) ;
00068 KeyData *p = _hash + h ;
00069 const cntr skip = ((d.key>>HASH_BITS) & SKIP_MASK) + SKIP_MINI ;
00070 cntr overflow = skip ;
00071 while( p->key != KEY_INV && p->key != d.key )
00072 {
00073 h += skip ;
00074 if( h < HASH_SIZE )
00075 p += skip ;
00076 else
00077 {
00078 h &= HASH_MASK ;
00079 p = _hash + h ;
00080 if( !(overflow--) )
00081 return false ;
00082 }
00083 }
00084 *p = d ;
00085 return true ;
00086 }
00087
00088 const KeyData operator[] ( Key k ) const
00089 {
00090 cntr h = hash( k ) ;
00091 const KeyData *p = _hash + h ;
00092 const cntr skip = ((k>>HASH_BITS) & SKIP_MASK) + SKIP_MINI ;
00093 cntr overflow = skip ;
00094 while( p->key != k && p->key != KEY_INV )
00095 {
00096 h += skip ;
00097 if( h < HASH_SIZE )
00098 p += skip ;
00099 else
00100 {
00101 h &= HASH_MASK ;
00102 p = _hash + h ;
00103 if( !(overflow--) )
00104 return KD_INV ;
00105 }
00106 }
00107 return *p ;
00108 }
00109
00110 KeyData &operator[] ( Key k )
00111 {
00112 cntr h = hash( k ) ;
00113 KeyData *p = _hash + h ;
00114 const cntr skip = ((k>>HASH_BITS) & SKIP_MASK) + SKIP_MINI ;
00115 cntr overflow = skip ;
00116 while( p->key != k && p->key != KEY_INV )
00117 {
00118 h += skip ;
00119 if( h < HASH_SIZE )
00120 p += skip ;
00121 else
00122 {
00123 h &= HASH_MASK ;
00124 p = _hash + h ;
00125 if( !(overflow--) )
00126 return KD_INV ;
00127 }
00128 }
00129 return *p ;
00130 }
00131
00132
00133 bool contains( Key k ) const { return (*this)[k].key == k ; }
00134
00135
00136
00137
00138
00139 public :
00141 class iterator
00142 {
00143 public :
00144
00146 iterator( Hash<Data> &hash_, cntr id_ = 0 ) : _ptr(hash_._hash+id_), _last(hash_._hash+HASH_SIZE) { while( _ptr != _last && _ptr->key == KEY_INV ) ++_ptr ; }
00147
00149 ~iterator() {}
00150
00152 iterator( const iterator &it ) : _ptr(it._ptr), _last(it._last) {}
00153
00155 iterator &operator = ( const iterator &it )
00156 { _ptr = it._ptr; _last = it._last; return *this; }
00157
00158
00159
00160 public :
00162 inline bool operator ==( const iterator &it ) const { return _ptr == it._ptr ; }
00164 inline bool operator !=( const iterator &it ) const { return _ptr != it._ptr ; }
00165
00167 inline bool operator ()() const { return _ptr != _last ; }
00168
00170 inline const Key &key() const { return _ptr->key ; }
00171
00173 inline const Data &operator * () const { return _ptr->data ; }
00174
00176 inline Data &operator * () { return _ptr->data ; }
00177
00179 inline iterator &operator ++() { while( (++_ptr != _last) && _ptr->key == KEY_INV ) ; return *this ; }
00180
00181
00182
00183 private :
00184 KeyData *_ptr ;
00185 const KeyData *_last ;
00186 };
00187
00188
00189
00190 public :
00192 class const_iterator
00193 {
00194 public :
00195
00197 const_iterator( const Hash<Data> &hash_, cntr id_ = 0 ) : _ptr(hash_._hash+id_), _last(hash_._hash+HASH_SIZE) { while( _ptr != _last && _ptr->key == KEY_INV ) ++_ptr ; }
00198
00200 ~const_iterator() {}
00201
00203 const_iterator( const const_iterator &it ) : _ptr(it._ptr), _last(it._last) {}
00204
00206 const_iterator &operator = ( const const_iterator &it )
00207 { _ptr = it._ptr; _last = it._last; return *this; }
00208
00209
00210
00211 public :
00213 inline bool operator ==( const const_iterator &it ) const { return _ptr == it._ptr ; }
00215 inline bool operator !=( const const_iterator &it ) const { return _ptr != it._ptr ; }
00216
00218 inline bool operator ()() const { return _ptr != _last ; }
00219
00221 inline const Key &key() const { return _ptr->key ; }
00222
00224 inline const Data &operator * () const { return _ptr->data ; }
00225
00227 inline const_iterator &operator ++() { while( (++_ptr != _last) && _ptr->key == KEY_INV ) ; return *this ; }
00228
00229
00230
00231 private :
00232 const KeyData * _ptr ;
00233 const KeyData * const _last ;
00234 };
00235
00236 public :
00238 iterator begin( cntr id = 0 ) { return iterator( *this, id ) ; }
00240 const_iterator cbegin( cntr id = 0 ) { return const_iterator( *this, id ) ; }
00241
00242 };
00243
00244
00245
00246
00248 template <> inline Hash<real >::cntr Hash<real >::hash( Key k ) const { return k & HASH_MASK ; }
00249
00251 template <> inline Hash<Level>::cntr Hash<Level>::hash( Key k ) const { return (k>>NON_HASH_BITS) & HASH_MASK ; }