summaryrefslogtreecommitdiff
path: root/src/stable/hash.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/stable/hash.h2610
1 files changed, 1305 insertions, 1305 deletions
diff --git a/src/stable/hash.h b/src/stable/hash.h
index 86f189e..1574a1c 100644
--- a/src/stable/hash.h
+++ b/src/stable/hash.h
@@ -17,1311 +17,1311 @@
17 17
18namespace Bu 18namespace Bu
19{ 19{
20 subExceptionDecl( HashException ) 20 subExceptionDecl( HashException )
21 21
22 enum eHashException 22 enum eHashException
23 { 23 {
24 excodeNotFilled 24 excodeNotFilled
25 }; 25 };
26 26
27 template<typename T> 27 template<typename T>
28 uint32_t __calcHashCode( const T &k ); 28 uint32_t __calcHashCode( const T &k );
29 29
30 template<typename T> 30 template<typename T>
31 bool __cmpHashKeys( const T &a, const T &b ); 31 bool __cmpHashKeys( const T &a, const T &b );
32 32
33 /** 33 /**
34 * Default functor used to compute the size of hash tables. This version 34 * Default functor used to compute the size of hash tables. This version
35 * effectively doubles the size of the table when space is low, ensuring 35 * effectively doubles the size of the table when space is low, ensuring
36 * that you always wind up with an odd number for the table size. A 36 * that you always wind up with an odd number for the table size. A
37 * better but slower option is to always find the next prime number that's 37 * better but slower option is to always find the next prime number that's
38 * above double your current table size, but that has the potential to be 38 * above double your current table size, but that has the potential to be
39 * slower. 39 * slower.
40 */ 40 */
41 struct __calcNextTSize_fast 41 struct __calcNextTSize_fast
42 { 42 {
43 uint32_t operator()( uint32_t nCapacity, uint32_t nFilled, 43 uint32_t operator()( uint32_t nCapacity, uint32_t nFilled,
44 uint32_t nDeleted ) const 44 uint32_t nDeleted ) const
45 { 45 {
46 // This frist case will allow hashtables that are mostly deleted 46 // This frist case will allow hashtables that are mostly deleted
47 // items to reset to small allocations 47 // items to reset to small allocations
48 if( nFilled-nDeleted <= nCapacity/4 ) 48 if( nFilled-nDeleted <= nCapacity/4 )
49 { 49 {
50 nCapacity = 11; 50 nCapacity = 11;
51 while( nCapacity < nFilled*5/4 ) 51 while( nCapacity < nFilled*5/4 )
52 nCapacity = nCapacity*2+1; 52 nCapacity = nCapacity*2+1;
53 return nCapacity; 53 return nCapacity;
54 } 54 }
55 // This will hopefully prevent hash tables from growing needlessly 55 // This will hopefully prevent hash tables from growing needlessly
56 if( nFilled-nDeleted <= nCapacity/2 ) 56 if( nFilled-nDeleted <= nCapacity/2 )
57 { 57 {
58 if( nDeleted == 0 ) 58 if( nDeleted == 0 )
59 return nCapacity/4*5+1; // Grow just a little 59 return nCapacity/4*5+1; // Grow just a little
60 else 60 else
61 return nCapacity; // We're going to delete things 61 return nCapacity; // We're going to delete things
62 } 62 }
63 // Otherwise, just increase the capacity 63 // Otherwise, just increase the capacity
64 return nCapacity*2+1; 64 return nCapacity*2+1;
65 } 65 }
66 }; 66 };
67 67
68 template<typename totype> 68 template<typename totype>
69 int bitsTo( int iCount ) 69 int bitsTo( int iCount )
70 { 70 {
71 return ( (iCount/(sizeof(totype)*8)) 71 return ( (iCount/(sizeof(totype)*8))
72 + (iCount%(sizeof(totype)*8)>0 ? 1 : 0)); 72 + (iCount%(sizeof(totype)*8)>0 ? 1 : 0));
73 } 73 }
74 74
75 template<typename key, typename value, typename sizecalc, typename keyalloc, 75 template<typename key, typename value, typename sizecalc, typename keyalloc,
76 typename valuealloc, typename challoc> 76 typename valuealloc, typename challoc>
77 class Hash; 77 class Hash;
78 78
79 /** @cond DEVEL */ 79 /** @cond DEVEL */
80 template<typename key, typename value, typename sizecalc, typename keyalloc, 80 template<typename key, typename value, typename sizecalc, typename keyalloc,
81 typename valuealloc, typename challoc > 81 typename valuealloc, typename challoc >
82 class HashCore 82 class HashCore
83 { 83 {
84 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 84 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
85 friend class SharedCore< 85 friend class SharedCore<
86 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>, 86 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
87 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> 87 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
88 >; 88 >;
89 private: 89 private:
90 HashCore() : 90 HashCore() :
91 nCapacity( 0 ), 91 nCapacity( 0 ),
92 nFilled( 0 ), 92 nFilled( 0 ),
93 nDeleted( 0 ), 93 nDeleted( 0 ),
94 bFilled( NULL ), 94 bFilled( NULL ),
95 bDeleted( NULL ), 95 bDeleted( NULL ),
96 aKeys( NULL ), 96 aKeys( NULL ),
97 aValues( NULL ), 97 aValues( NULL ),
98 aHashCodes( NULL ) 98 aHashCodes( NULL )
99 { 99 {
100 } 100 }
101 101
102 virtual ~HashCore() 102 virtual ~HashCore()
103 { 103 {
104 clear(); 104 clear();
105 } 105 }
106 106
107 void init() 107 void init()
108 { 108 {
109 if( nCapacity > 0 ) 109 if( nCapacity > 0 )
110 return; 110 return;
111 111
112 nCapacity = 11; 112 nCapacity = 11;
113 nKeysSize = bitsTo<uint32_t>( nCapacity ); 113 nKeysSize = bitsTo<uint32_t>( nCapacity );
114 bFilled = ca.allocate( nKeysSize ); 114 bFilled = ca.allocate( nKeysSize );
115 bDeleted = ca.allocate( nKeysSize ); 115 bDeleted = ca.allocate( nKeysSize );
116 clearBits(); 116 clearBits();
117 117
118 aHashCodes = ca.allocate( nCapacity ); 118 aHashCodes = ca.allocate( nCapacity );
119 aKeys = ka.allocate( nCapacity ); 119 aKeys = ka.allocate( nCapacity );
120 aValues = va.allocate( nCapacity ); 120 aValues = va.allocate( nCapacity );
121 } 121 }
122 122
123 void clearBits() 123 void clearBits()
124 { 124 {
125 if( nCapacity == 0 ) 125 if( nCapacity == 0 )
126 return; 126 return;
127 127
128 for( uint32_t j = 0; j < nKeysSize; j++ ) 128 for( uint32_t j = 0; j < nKeysSize; j++ )
129 { 129 {
130 bFilled[j] = bDeleted[j] = 0; 130 bFilled[j] = bDeleted[j] = 0;
131 } 131 }
132 } 132 }
133 133
134 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash ) 134 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
135 { 135 {
136 init(); 136 init();
137 137
138 bFilled[loc/32] |= (1<<(loc%32)); 138 bFilled[loc/32] |= (1<<(loc%32));
139 va.construct( &aValues[loc], v ); 139 va.construct( &aValues[loc], v );
140 ka.construct( &aKeys[loc], k ); 140 ka.construct( &aKeys[loc], k );
141 aHashCodes[loc] = hash; 141 aHashCodes[loc] = hash;
142 nFilled++; 142 nFilled++;
143 //printf("Filled: %d, Deleted: %d, Capacity: %d\n", 143 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
144 // nFilled, nDeleted, nCapacity ); 144 // nFilled, nDeleted, nCapacity );
145 } 145 }
146 146
147 void _erase( uint32_t loc ) 147 void _erase( uint32_t loc )
148 { 148 {
149 if( nCapacity == 0 ) 149 if( nCapacity == 0 )
150 return; 150 return;
151 151
152 bDeleted[loc/32] |= (1<<(loc%32)); 152 bDeleted[loc/32] |= (1<<(loc%32));
153 va.destroy( &aValues[loc] ); 153 va.destroy( &aValues[loc] );
154 ka.destroy( &aKeys[loc] ); 154 ka.destroy( &aKeys[loc] );
155 nDeleted++; 155 nDeleted++;
156 //printf("Filled: %d, Deleted: %d, Capacity: %d\n", 156 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
157 // nFilled, nDeleted, nCapacity ); 157 // nFilled, nDeleted, nCapacity );
158 } 158 }
159 159
160 key &getKeyAtPos( uint32_t nPos ) 160 key &getKeyAtPos( uint32_t nPos )
161 { 161 {
162 if( nPos >= nCapacity ) 162 if( nPos >= nCapacity )
163 throw HashException("Referenced position invalid."); 163 throw HashException("Referenced position invalid.");
164 return aKeys[nPos]; 164 return aKeys[nPos];
165 } 165 }
166 166
167 const key &getKeyAtPos( uint32_t nPos ) const 167 const key &getKeyAtPos( uint32_t nPos ) const
168 { 168 {
169 if( nPos >= nCapacity ) 169 if( nPos >= nCapacity )
170 throw HashException("Referenced position invalid."); 170 throw HashException("Referenced position invalid.");
171 return aKeys[nPos]; 171 return aKeys[nPos];
172 } 172 }
173 173
174 value &getValueAtPos( uint32_t nPos ) 174 value &getValueAtPos( uint32_t nPos )
175 { 175 {
176 if( nPos >= nCapacity ) 176 if( nPos >= nCapacity )
177 throw HashException("Referenced position invalid."); 177 throw HashException("Referenced position invalid.");
178 return aValues[nPos]; 178 return aValues[nPos];
179 } 179 }
180 180
181 const value &getValueAtPos( uint32_t nPos ) const 181 const value &getValueAtPos( uint32_t nPos ) const
182 { 182 {
183 if( nPos >= nCapacity ) 183 if( nPos >= nCapacity )
184 throw HashException("Referenced position invalid."); 184 throw HashException("Referenced position invalid.");
185 return aValues[nPos]; 185 return aValues[nPos];
186 } 186 }
187 187
188 uint32_t getFirstPos( bool &bFinished ) const 188 uint32_t getFirstPos( bool &bFinished ) const
189 { 189 {
190 for( uint32_t j = 0; j < nCapacity; j++ ) 190 for( uint32_t j = 0; j < nCapacity; j++ )
191 { 191 {
192 if( isFilled( j ) ) 192 if( isFilled( j ) )
193 if( !isDeleted( j ) ) 193 if( !isDeleted( j ) )
194 return j; 194 return j;
195 } 195 }
196 196
197 bFinished = true; 197 bFinished = true;
198 return 0; 198 return 0;
199 } 199 }
200 200
201 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const 201 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
202 { 202 {
203 for( uint32_t j = nPos+1; j < nCapacity; j++ ) 203 for( uint32_t j = nPos+1; j < nCapacity; j++ )
204 { 204 {
205 if( isFilled( j ) ) 205 if( isFilled( j ) )
206 if( !isDeleted( j ) ) 206 if( !isDeleted( j ) )
207 return j; 207 return j;
208 } 208 }
209 209
210 bFinished = true; 210 bFinished = true;
211 return 0; 211 return 0;
212 } 212 }
213 213
214 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true ) 214 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
215 { 215 {
216 init(); 216 init();
217 217
218 uint32_t nCur = hash%nCapacity; 218 uint32_t nCur = hash%nCapacity;
219 219
220 // First we scan to see if the key is already there, abort if we 220 // First we scan to see if the key is already there, abort if we
221 // run out of probing room, or we find a non-filled entry 221 // run out of probing room, or we find a non-filled entry
222 int8_t j; 222 int8_t j;
223 for( j = 0; 223 for( j = 0;
224 isFilled( nCur ) && j < 32; 224 isFilled( nCur ) && j < 32;
225 nCur = (nCur + (1<<j))%nCapacity, j++ 225 nCur = (nCur + (1<<j))%nCapacity, j++
226 ) 226 )
227 { 227 {
228 // Is this the same hash code we were looking for? 228 // Is this the same hash code we were looking for?
229 if( hash == aHashCodes[nCur] ) 229 if( hash == aHashCodes[nCur] )
230 { 230 {
231 // Skip over deleted entries. Deleted entries are also filled, 231 // Skip over deleted entries. Deleted entries are also filled,
232 // so we only have to do this check here. 232 // so we only have to do this check here.
233 if( isDeleted( nCur ) ) 233 if( isDeleted( nCur ) )
234 continue; 234 continue;
235 235
236 // Is it really the same key? (for safety) 236 // Is it really the same key? (for safety)
237 if( __cmpHashKeys( aKeys[nCur], k ) == true ) 237 if( __cmpHashKeys( aKeys[nCur], k ) == true )
238 { 238 {
239 bFill = true; 239 bFill = true;
240 return nCur; 240 return nCur;
241 } 241 }
242 } 242 }
243 } 243 }
244 244
245 // This is our insurance, if the table is full, then go ahead and 245 // This is our insurance, if the table is full, then go ahead and
246 // rehash, then try again. 246 // rehash, then try again.
247 if( (isFilled( nCur ) || j == 32) && rehash == true ) 247 if( (isFilled( nCur ) || j == 32) && rehash == true )
248 { 248 {
249 reHash( szCalc( nCapacity, nFilled, nDeleted ) ); 249 reHash( szCalc( nCapacity, nFilled, nDeleted ) );
250 250
251 // This is potentially dangerous, and could cause an infinite loop. 251 // This is potentially dangerous, and could cause an infinite loop.
252 // Be careful writing probe, eh? 252 // Be careful writing probe, eh?
253 return probe( hash, k, bFill ); 253 return probe( hash, k, bFill );
254 } 254 }
255 255
256 bFill = false; 256 bFill = false;
257 return nCur; 257 return nCur;
258 } 258 }
259 259
260 uint32_t probe( uint32_t hash, key k, bool &bFill ) const 260 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
261 { 261 {
262 if( nCapacity == 0 ) 262 if( nCapacity == 0 )
263 throw Bu::ExceptionBase("Probe in empty hash table."); 263 throw Bu::ExceptionBase("Probe in empty hash table.");
264 264
265 uint32_t nCur = hash%nCapacity; 265 uint32_t nCur = hash%nCapacity;
266 266
267 // First we scan to see if the key is already there, abort if we 267 // First we scan to see if the key is already there, abort if we
268 // run out of probing room, or we find a non-filled entry 268 // run out of probing room, or we find a non-filled entry
269 for( int8_t j = 0; 269 for( int8_t j = 0;
270 isFilled( nCur ) && j < 32; 270 isFilled( nCur ) && j < 32;
271 nCur = (nCur + (1<<j))%nCapacity, j++ 271 nCur = (nCur + (1<<j))%nCapacity, j++
272 ) 272 )
273 { 273 {
274 // Is this the same hash code we were looking for? 274 // Is this the same hash code we were looking for?
275 if( hash == aHashCodes[nCur] ) 275 if( hash == aHashCodes[nCur] )
276 { 276 {
277 // Skip over deleted entries. Deleted entries are also filled, 277 // Skip over deleted entries. Deleted entries are also filled,
278 // so we only have to do this check here. 278 // so we only have to do this check here.
279 if( isDeleted( nCur ) ) 279 if( isDeleted( nCur ) )
280 continue; 280 continue;
281 281
282 // Is it really the same key? (for safety) 282 // Is it really the same key? (for safety)
283 if( __cmpHashKeys( aKeys[nCur], k ) == true ) 283 if( __cmpHashKeys( aKeys[nCur], k ) == true )
284 { 284 {
285 bFill = true; 285 bFill = true;
286 return nCur; 286 return nCur;
287 } 287 }
288 } 288 }
289 } 289 }
290 290
291 bFill = false; 291 bFill = false;
292 return nCur; 292 return nCur;
293 } 293 }
294 294
295 void insert( const key &k, const value &v ) 295 void insert( const key &k, const value &v )
296 { 296 {
297 uint32_t hash = __calcHashCode( k ); 297 uint32_t hash = __calcHashCode( k );
298 bool bFill; 298 bool bFill;
299 uint32_t nPos = probe( hash, k, bFill ); 299 uint32_t nPos = probe( hash, k, bFill );
300 300
301 if( bFill ) 301 if( bFill )
302 { 302 {
303 va.destroy( &aValues[nPos] ); 303 va.destroy( &aValues[nPos] );
304 va.construct( &aValues[nPos], v ); 304 va.construct( &aValues[nPos], v );
305 } 305 }
306 else 306 else
307 { 307 {
308 fill( nPos, k, v, hash ); 308 fill( nPos, k, v, hash );
309 } 309 }
310 } 310 }
311 311
312 void reHash( uint32_t nNewSize ) 312 void reHash( uint32_t nNewSize )
313 { 313 {
314 //printf("--rehash: %d --> %d (%d, %d)\n", nCapacity, nNewSize, nFilled, nDeleted ); 314 //printf("--rehash: %d --> %d (%d, %d)\n", nCapacity, nNewSize, nFilled, nDeleted );
315 //printf("---REHASH---"); 315 //printf("---REHASH---");
316 //printf("Filled: %d, Deleted: %d, Capacity: %d\n", 316 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
317 // nFilled, nDeleted, nCapacity ); 317 // nFilled, nDeleted, nCapacity );
318 318
319 // Save all the old data 319 // Save all the old data
320 uint32_t nOldCapacity = nCapacity; 320 uint32_t nOldCapacity = nCapacity;
321 uint32_t *bOldFilled = bFilled; 321 uint32_t *bOldFilled = bFilled;
322 uint32_t *aOldHashCodes = aHashCodes; 322 uint32_t *aOldHashCodes = aHashCodes;
323 uint32_t nOldKeysSize = nKeysSize; 323 uint32_t nOldKeysSize = nKeysSize;
324 uint32_t *bOldDeleted = bDeleted; 324 uint32_t *bOldDeleted = bDeleted;
325 value *aOldValues = aValues; 325 value *aOldValues = aValues;
326 key *aOldKeys = aKeys; 326 key *aOldKeys = aKeys;
327 327
328 // Calculate new sizes 328 // Calculate new sizes
329 nCapacity = nNewSize; 329 nCapacity = nNewSize;
330 nKeysSize = bitsTo<uint32_t>( nCapacity ); 330 nKeysSize = bitsTo<uint32_t>( nCapacity );
331 331
332 // Allocate new memory + prep 332 // Allocate new memory + prep
333 bFilled = ca.allocate( nKeysSize ); 333 bFilled = ca.allocate( nKeysSize );
334 bDeleted = ca.allocate( nKeysSize ); 334 bDeleted = ca.allocate( nKeysSize );
335 clearBits(); 335 clearBits();
336 336
337 aHashCodes = ca.allocate( nCapacity ); 337 aHashCodes = ca.allocate( nCapacity );
338 aKeys = ka.allocate( nCapacity ); 338 aKeys = ka.allocate( nCapacity );
339 aValues = va.allocate( nCapacity ); 339 aValues = va.allocate( nCapacity );
340 340
341 nDeleted = nFilled = 0; 341 nDeleted = nFilled = 0;
342 342
343 // Re-insert all of the old data (except deleted items) 343 // Re-insert all of the old data (except deleted items)
344 for( uint32_t j = 0; j < nOldCapacity; j++ ) 344 for( uint32_t j = 0; j < nOldCapacity; j++ )
345 { 345 {
346 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 346 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
347 (bOldDeleted[j/32]&(1<<(j%32)))==0 ) 347 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
348 { 348 {
349 insert( aOldKeys[j], aOldValues[j] ); 349 insert( aOldKeys[j], aOldValues[j] );
350 } 350 }
351 } 351 }
352 352
353 // Delete all of the old data 353 // Delete all of the old data
354 for( uint32_t j = 0; j < nOldCapacity; j++ ) 354 for( uint32_t j = 0; j < nOldCapacity; j++ )
355 { 355 {
356 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 356 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
357 (bOldDeleted[j/32]&(1<<(j%32)))==0 ) 357 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
358 { 358 {
359 va.destroy( &aOldValues[j] ); 359 va.destroy( &aOldValues[j] );
360 ka.destroy( &aOldKeys[j] ); 360 ka.destroy( &aOldKeys[j] );
361 } 361 }
362 } 362 }
363 va.deallocate( aOldValues, nOldCapacity ); 363 va.deallocate( aOldValues, nOldCapacity );
364 ka.deallocate( aOldKeys, nOldCapacity ); 364 ka.deallocate( aOldKeys, nOldCapacity );
365 ca.deallocate( bOldFilled, nOldKeysSize ); 365 ca.deallocate( bOldFilled, nOldKeysSize );
366 ca.deallocate( bOldDeleted, nOldKeysSize ); 366 ca.deallocate( bOldDeleted, nOldKeysSize );
367 ca.deallocate( aOldHashCodes, nOldCapacity ); 367 ca.deallocate( aOldHashCodes, nOldCapacity );
368 } 368 }
369 369
370 bool isFilled( uint32_t loc ) const 370 bool isFilled( uint32_t loc ) const
371 { 371 {
372 if( loc >= nCapacity ) 372 if( loc >= nCapacity )
373 throw HashException("Referenced position invalid."); 373 throw HashException("Referenced position invalid.");
374 return (bFilled[loc/32]&(1<<(loc%32)))!=0; 374 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
375 } 375 }
376 376
377 bool isDeleted( uint32_t loc ) const 377 bool isDeleted( uint32_t loc ) const
378 { 378 {
379 if( loc >= nCapacity ) 379 if( loc >= nCapacity )
380 throw HashException("Referenced position invalid."); 380 throw HashException("Referenced position invalid.");
381 return (bDeleted[loc/32]&(1<<(loc%32)))!=0; 381 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
382 } 382 }
383 383
384 void clear() 384 void clear()
385 { 385 {
386 for( uint32_t j = 0; j < nCapacity; j++ ) 386 for( uint32_t j = 0; j < nCapacity; j++ )
387 { 387 {
388 if( isFilled( j ) ) 388 if( isFilled( j ) )
389 if( !isDeleted( j ) ) 389 if( !isDeleted( j ) )
390 { 390 {
391 va.destroy( &aValues[j] ); 391 va.destroy( &aValues[j] );
392 ka.destroy( &aKeys[j] ); 392 ka.destroy( &aKeys[j] );
393 } 393 }
394 } 394 }
395 va.deallocate( aValues, nCapacity ); 395 va.deallocate( aValues, nCapacity );
396 ka.deallocate( aKeys, nCapacity ); 396 ka.deallocate( aKeys, nCapacity );
397 ca.deallocate( bFilled, nKeysSize ); 397 ca.deallocate( bFilled, nKeysSize );
398 ca.deallocate( bDeleted, nKeysSize ); 398 ca.deallocate( bDeleted, nKeysSize );
399 ca.deallocate( aHashCodes, nCapacity ); 399 ca.deallocate( aHashCodes, nCapacity );
400 400
401 bFilled = NULL; 401 bFilled = NULL;
402 bDeleted = NULL; 402 bDeleted = NULL;
403 aKeys = NULL; 403 aKeys = NULL;
404 aValues = NULL; 404 aValues = NULL;
405 aHashCodes = NULL; 405 aHashCodes = NULL;
406 406
407 nCapacity = 0; 407 nCapacity = 0;
408 nFilled = 0; 408 nFilled = 0;
409 nDeleted = 0; 409 nDeleted = 0;
410 } 410 }
411 411
412 uint32_t nCapacity; 412 uint32_t nCapacity;
413 uint32_t nFilled; 413 uint32_t nFilled;
414 uint32_t nDeleted; 414 uint32_t nDeleted;
415 uint32_t *bFilled; 415 uint32_t *bFilled;
416 uint32_t *bDeleted; 416 uint32_t *bDeleted;
417 uint32_t nKeysSize; 417 uint32_t nKeysSize;
418 key *aKeys; 418 key *aKeys;
419 value *aValues; 419 value *aValues;
420 uint32_t *aHashCodes; 420 uint32_t *aHashCodes;
421 valuealloc va; 421 valuealloc va;
422 keyalloc ka; 422 keyalloc ka;
423 challoc ca; 423 challoc ca;
424 sizecalc szCalc; 424 sizecalc szCalc;
425 }; 425 };
426 /** @endcond */ 426 /** @endcond */
427 427
428 /** 428 /**
429 * Libbu++ Template Hash Table. This is your average hash table, that uses 429 * Libbu++ Template Hash Table. This is your average hash table, that uses
430 * template functions in order to do fast, efficient, generalized hashing. 430 * template functions in order to do fast, efficient, generalized hashing.
431 * It's pretty easy to use, and works well with all other libbu++ types so 431 * It's pretty easy to use, and works well with all other libbu++ types so
432 * far. 432 * far.
433 * 433 *
434 * In order to use it, I recommend the following for all basic usage: 434 * In order to use it, I recommend the following for all basic usage:
435 *@code 435 *@code
436 // Define a Hash typedef with strings as keys and ints as values. 436 // Define a Hash typedef with strings as keys and ints as values.
437 typedef Bu::Hash<Bu::String, int> StrIntHash; 437 typedef Bu::Hash<Bu::String, int> StrIntHash;
438 438
439 // Create one 439 // Create one
440 StrIntHash hInts; 440 StrIntHash hInts;
441 441
442 // Insert some integers 442 // Insert some integers
443 hInts["one"] = 1; 443 hInts["one"] = 1;
444 hInts["forty-two"] = 42; 444 hInts["forty-two"] = 42;
445 hInts.insert("forty two", 42 ); 445 hInts.insert("forty two", 42 );
446 446
447 // Get values out of the hash, the last two options are the most explicit, 447 // Get values out of the hash, the last two options are the most explicit,
448 // and must be used if the hash's value type does not match what you're 448 // and must be used if the hash's value type does not match what you're
449 // comparing to exactly. 449 // comparing to exactly.
450 if( hInts["one"] == 1 ) doSomething(); 450 if( hInts["one"] == 1 ) doSomething();
451 if( hInts["forty-two"].value() == 42 ) doSomething(); 451 if( hInts["forty-two"].value() == 42 ) doSomething();
452 if( hInts.get("forty two") == 42 ) doSomething(); 452 if( hInts.get("forty two") == 42 ) doSomething();
453 453
454 // Iterate through the Hash 454 // Iterate through the Hash
455 for( StrIntHash::iterator i = hInts.begin(); i != hInts.end(); i++ ) 455 for( StrIntHash::iterator i = hInts.begin(); i != hInts.end(); i++ )
456 { 456 {
457 // i.getValue() works too 457 // i.getValue() works too
458 print("'%s' = %d\n", i.getKey().getStr(), (*i) ); 458 print("'%s' = %d\n", i.getKey().getStr(), (*i) );
459 } 459 }
460 460
461 @endcode 461 @endcode
462 *@param key (typename) The datatype of the hashtable keys 462 *@param key (typename) The datatype of the hashtable keys
463 *@param value (typename) The datatype of the hashtable data 463 *@param value (typename) The datatype of the hashtable data
464 *@param sizecalc (typename) Functor to compute new table size on rehash 464 *@param sizecalc (typename) Functor to compute new table size on rehash
465 *@param keyalloc (typename) Memory allocator for hashtable keys 465 *@param keyalloc (typename) Memory allocator for hashtable keys
466 *@param valuealloc (typename) Memory allocator for hashtable values 466 *@param valuealloc (typename) Memory allocator for hashtable values
467 *@param challoc (typename) Byte allocator for bitflags 467 *@param challoc (typename) Byte allocator for bitflags
468 *@ingroup Containers 468 *@ingroup Containers
469 */ 469 */
470 template<typename key, typename value, 470 template<typename key, typename value,
471 typename sizecalc = __calcNextTSize_fast, 471 typename sizecalc = __calcNextTSize_fast,
472 typename keyalloc = std::allocator<key>, 472 typename keyalloc = std::allocator<key>,
473 typename valuealloc = std::allocator<value>, 473 typename valuealloc = std::allocator<value>,
474 typename challoc = std::allocator<uint32_t> 474 typename challoc = std::allocator<uint32_t>
475 > 475 >
476 class Hash : public SharedCore< 476 class Hash : public SharedCore<
477 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>, 477 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
478 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> 478 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
479 > 479 >
480 { 480 {
481 private: 481 private:
482 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core; 482 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core;
483 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType; 483 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType;
484 protected: 484 protected:
485 using SharedCore<MyType, Core>::core; 485 using SharedCore<MyType, Core>::core;
486 using SharedCore<MyType, Core>::_hardCopy; 486 using SharedCore<MyType, Core>::_hardCopy;
487 using SharedCore<MyType, Core>::_resetCore; 487 using SharedCore<MyType, Core>::_resetCore;
488 using SharedCore<MyType, Core>::_allocateCore; 488 using SharedCore<MyType, Core>::_allocateCore;
489 489
490 public: 490 public:
491 Hash() 491 Hash()
492 { 492 {
493 } 493 }
494 494
495 Hash( const MyType &src ) : 495 Hash( const MyType &src ) :
496 SharedCore<MyType, Core >( src ) 496 SharedCore<MyType, Core >( src )
497 { 497 {
498 } 498 }
499 499
500 virtual ~Hash() 500 virtual ~Hash()
501 { 501 {
502 } 502 }
503 503
504 /** 504 /**
505 * Get the current hash table capacity. (Changes at re-hash) 505 * Get the current hash table capacity. (Changes at re-hash)
506 *@returns (uint32_t) The current capacity. 506 *@returns (uint32_t) The current capacity.
507 */ 507 */
508 uint32_t getCapacity() const 508 uint32_t getCapacity() const
509 { 509 {
510 return core->nCapacity; 510 return core->nCapacity;
511 } 511 }
512 512
513 /** 513 /**
514 * Get the number of hash locations spoken for. (Including 514 * Get the number of hash locations spoken for. (Including
515 * not-yet-cleaned-up deleted items.) 515 * not-yet-cleaned-up deleted items.)
516 *@returns (uint32_t) The current fill state. 516 *@returns (uint32_t) The current fill state.
517 */ 517 */
518 uint32_t getFill() const 518 uint32_t getFill() const
519 { 519 {
520 return core->nFilled; 520 return core->nFilled;
521 } 521 }
522 522
523 /** 523 /**
524 * Get the number of items stored in the hash table. 524 * Get the number of items stored in the hash table.
525 *@returns (uint32_t) The number of items stored in the hash table. 525 *@returns (uint32_t) The number of items stored in the hash table.
526 */ 526 */
527 uint32_t getSize() const 527 uint32_t getSize() const
528 { 528 {
529 return core->nFilled-core->nDeleted; 529 return core->nFilled-core->nDeleted;
530 } 530 }
531 531
532 bool isEmpty() const 532 bool isEmpty() const
533 { 533 {
534 return (core->nFilled-core->nDeleted) == 0; 534 return (core->nFilled-core->nDeleted) == 0;
535 } 535 }
536 536
537 /** 537 /**
538 * Get the number of items which have been deleted, but not yet 538 * Get the number of items which have been deleted, but not yet
539 * cleaned up. 539 * cleaned up.
540 *@returns (uint32_t) The number of deleted items. 540 *@returns (uint32_t) The number of deleted items.
541 */ 541 */
542 uint32_t getDeleted() const 542 uint32_t getDeleted() const
543 { 543 {
544 return core->nDeleted; 544 return core->nDeleted;
545 } 545 }
546 546
547 struct HashProxy 547 struct HashProxy
548 { 548 {
549 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 549 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
550 private: 550 private:
551 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) : 551 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) :
552 hsh( h ), 552 hsh( h ),
553 pKey( k ), 553 pKey( k ),
554 nPos( nPos ), 554 nPos( nPos ),
555 hash( hash ), 555 hash( hash ),
556 bFilled( false ) 556 bFilled( false )
557 { 557 {
558 } 558 }
559 559
560 HashProxy( MyType &h, uint32_t nPos, value *pValue ) : 560 HashProxy( MyType &h, uint32_t nPos, value *pValue ) :
561 hsh( h ), 561 hsh( h ),
562 nPos( nPos ), 562 nPos( nPos ),
563 pValue( pValue ), 563 pValue( pValue ),
564 bFilled( true ) 564 bFilled( true )
565 { 565 {
566 } 566 }
567 567
568 MyType &hsh; 568 MyType &hsh;
569 const key *pKey; 569 const key *pKey;
570 uint32_t nPos; 570 uint32_t nPos;
571 value *pValue; 571 value *pValue;
572 uint32_t hash; 572 uint32_t hash;
573 bool bFilled; 573 bool bFilled;
574 574
575 public: 575 public:
576 /** 576 /**
577 * Cast operator for HashProxy. 577 * Cast operator for HashProxy.
578 *@returns (value_type &) The value the HashProxy is pointing to. 578 *@returns (value_type &) The value the HashProxy is pointing to.
579 */ 579 */
580 operator value &() 580 operator value &()
581 { 581 {
582 if( bFilled == false ) 582 if( bFilled == false )
583 throw HashException( 583 throw HashException(
584 excodeNotFilled, 584 excodeNotFilled,
585 "No data associated with that key." 585 "No data associated with that key."
586 ); 586 );
587 return *pValue; 587 return *pValue;
588 } 588 }
589 589
590 /** 590 /**
591 * Direct function for retrieving a value out of the HashProxy. 591 * Direct function for retrieving a value out of the HashProxy.
592 *@returns (value_type &) The value pointed to by this HashProxy. 592 *@returns (value_type &) The value pointed to by this HashProxy.
593 */ 593 */
594 value &getValue() 594 value &getValue()
595 { 595 {
596 if( bFilled == false ) 596 if( bFilled == false )
597 throw HashException( 597 throw HashException(
598 excodeNotFilled, 598 excodeNotFilled,
599 "No data associated with that key." 599 "No data associated with that key."
600 ); 600 );
601 return *pValue; 601 return *pValue;
602 } 602 }
603 603
604 /** 604 /**
605 * Whether this HashProxy points to something real or not. 605 * Whether this HashProxy points to something real or not.
606 */ 606 */
607 bool isFilled() 607 bool isFilled()
608 { 608 {
609 return bFilled; 609 return bFilled;
610 } 610 }
611 611
612 /** 612 /**
613 * Erase the data pointed to by this HashProxy. 613 * Erase the data pointed to by this HashProxy.
614 */ 614 */
615 void erase() 615 void erase()
616 { 616 {
617 if( bFilled ) 617 if( bFilled )
618 { 618 {
619 hsh.core->_erase( nPos ); 619 hsh.core->_erase( nPos );
620 } 620 }
621 } 621 }
622 622
623 /** 623 /**
624 * Assign data to this point in the hash table. 624 * Assign data to this point in the hash table.
625 *@param nval (value_type) the data to assign. 625 *@param nval (value_type) the data to assign.
626 */ 626 */
627 value operator=( value nval ) 627 value operator=( value nval )
628 { 628 {
629 if( bFilled ) 629 if( bFilled )
630 { 630 {
631 hsh.core->va.destroy( &hsh.core->aValues[nPos] ); 631 hsh.core->va.destroy( &hsh.core->aValues[nPos] );
632 hsh.core->va.construct( &hsh.core->aValues[nPos], nval ); 632 hsh.core->va.construct( &hsh.core->aValues[nPos], nval );
633 } 633 }
634 else 634 else
635 { 635 {
636 hsh.core->fill( nPos, *pKey, nval, hash ); 636 hsh.core->fill( nPos, *pKey, nval, hash );
637 } 637 }
638 638
639 return nval; 639 return nval;
640 } 640 }
641 641
642 /** 642 /**
643 * Pointer extraction operator. Access to members of data pointed to 643 * Pointer extraction operator. Access to members of data pointed to
644 * by HashProxy. 644 * by HashProxy.
645 *@returns (value_type *) 645 *@returns (value_type *)
646 */ 646 */
647 value *operator->() 647 value *operator->()
648 { 648 {
649 if( bFilled == false ) 649 if( bFilled == false )
650 throw HashException( 650 throw HashException(
651 excodeNotFilled, 651 excodeNotFilled,
652 "No data associated with that key." 652 "No data associated with that key."
653 ); 653 );
654 return pValue; 654 return pValue;
655 } 655 }
656 }; 656 };
657 657
658 /** 658 /**
659 * Hash table index operator 659 * Hash table index operator
660 *@param k (key_type) Key of data to be retrieved. 660 *@param k (key_type) Key of data to be retrieved.
661 *@returns (HashProxy) Proxy pointing to the data. 661 *@returns (HashProxy) Proxy pointing to the data.
662 */ 662 */
663 HashProxy operator[]( const key &k ) 663 HashProxy operator[]( const key &k )
664 { 664 {
665 _hardCopy(); 665 _hardCopy();
666 666
667 uint32_t hash = __calcHashCode( k ); 667 uint32_t hash = __calcHashCode( k );
668 bool bFill; 668 bool bFill;
669 uint32_t nPos = core->probe( hash, k, bFill ); 669 uint32_t nPos = core->probe( hash, k, bFill );
670 670
671 if( bFill ) 671 if( bFill )
672 { 672 {
673 return HashProxy( *this, nPos, &core->aValues[nPos] ); 673 return HashProxy( *this, nPos, &core->aValues[nPos] );
674 } 674 }
675 else 675 else
676 { 676 {
677 return HashProxy( *this, &k, nPos, hash ); 677 return HashProxy( *this, &k, nPos, hash );
678 } 678 }
679 } 679 }
680 680
681 /** 681 /**
682 * Insert a value (v) under key (k) into the hash table 682 * Insert a value (v) under key (k) into the hash table
683 *@param k (key_type) Key to list the value under. 683 *@param k (key_type) Key to list the value under.
684 *@param v (value_type) Value to store in the hash table. 684 *@param v (value_type) Value to store in the hash table.
685 */ 685 */
686 void insert( const key &k, const value &v ) 686 void insert( const key &k, const value &v )
687 { 687 {
688 _hardCopy(); 688 _hardCopy();
689 689
690 core->insert( k, v ); 690 core->insert( k, v );
691 } 691 }
692 692
693 /** 693 /**
694 * Remove a value from the hash table. 694 * Remove a value from the hash table.
695 *@param k (key_type) The data under this key will be erased. 695 *@param k (key_type) The data under this key will be erased.
696 */ 696 */
697 void erase( const key &k ) 697 void erase( const key &k )
698 { 698 {
699 _hardCopy(); 699 _hardCopy();
700 700
701 uint32_t hash = __calcHashCode( k ); 701 uint32_t hash = __calcHashCode( k );
702 bool bFill; 702 bool bFill;
703 uint32_t nPos = core->probe( hash, k, bFill ); 703 uint32_t nPos = core->probe( hash, k, bFill );
704 704
705 if( bFill ) 705 if( bFill )
706 { 706 {
707 core->_erase( nPos ); 707 core->_erase( nPos );
708 } 708 }
709 } 709 }
710 710
711 struct iterator; 711 struct iterator;
712 712
713 /** 713 /**
714 * Remove a value from the hash pointed to from an iterator. 714 * Remove a value from the hash pointed to from an iterator.
715 *@param i (iterator &) The data to be erased. 715 *@param i (iterator &) The data to be erased.
716 */ 716 */
717 void erase( struct iterator &i ) 717 void erase( struct iterator &i )
718 { 718 {
719 if( this != i.hsh ) 719 if( this != i.hsh )
720 throw HashException("This iterator didn't come from this Hash."); 720 throw HashException("This iterator didn't come from this Hash.");
721 721
722 _hardCopy(); 722 _hardCopy();
723 723
724 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) ) 724 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) )
725 { 725 {
726 core->_erase( i.nPos ); 726 core->_erase( i.nPos );
727 } 727 }
728 } 728 }
729 729
730 /** 730 /**
731 * Remove all data from the hash table. 731 * Remove all data from the hash table.
732 */ 732 */
733 virtual void clear() 733 virtual void clear()
734 { 734 {
735 _resetCore(); 735 _resetCore();
736 } 736 }
737 737
738 /** 738 /**
739 * Get an item of data from the hash table. 739 * Get an item of data from the hash table.
740 *@param k (key_type) Key pointing to the data to be retrieved. 740 *@param k (key_type) Key pointing to the data to be retrieved.
741 *@returns (value_type &) The data pointed to by (k). 741 *@returns (value_type &) The data pointed to by (k).
742 */ 742 */
743 value &get( const key &k ) 743 value &get( const key &k )
744 { 744 {
745 _hardCopy(); 745 _hardCopy();
746 746
747 uint32_t hash = __calcHashCode( k ); 747 uint32_t hash = __calcHashCode( k );
748 bool bFill; 748 bool bFill;
749 uint32_t nPos = core->probe( hash, k, bFill, false ); 749 uint32_t nPos = core->probe( hash, k, bFill, false );
750 750
751 if( bFill ) 751 if( bFill )
752 { 752 {
753 return core->aValues[nPos]; 753 return core->aValues[nPos];
754 } 754 }
755 else 755 else
756 { 756 {
757 throw HashException( 757 throw HashException(
758 excodeNotFilled, 758 excodeNotFilled,
759 "No data associated with that key." 759 "No data associated with that key."
760 ); 760 );
761 } 761 }
762 } 762 }
763 763
764 /** 764 /**
765 * Get a const item of data from the hash table. 765 * Get a const item of data from the hash table.
766 *@param k (key_type) Key pointing to the data to be retrieved. 766 *@param k (key_type) Key pointing to the data to be retrieved.
767 *@returns (const value_type &) A const version of the data pointed 767 *@returns (const value_type &) A const version of the data pointed
768 * to by (k). 768 * to by (k).
769 */ 769 */
770 const value &get( const key &k ) const 770 const value &get( const key &k ) const
771 { 771 {
772 uint32_t hash = __calcHashCode( k ); 772 uint32_t hash = __calcHashCode( k );
773 bool bFill; 773 bool bFill;
774 uint32_t nPos = core->probe( hash, k, bFill ); 774 uint32_t nPos = core->probe( hash, k, bFill );
775 775
776 if( bFill ) 776 if( bFill )
777 { 777 {
778 return core->aValues[nPos]; 778 return core->aValues[nPos];
779 } 779 }
780 else 780 else
781 { 781 {
782 throw HashException( 782 throw HashException(
783 excodeNotFilled, 783 excodeNotFilled,
784 "No data associated with that key." 784 "No data associated with that key."
785 ); 785 );
786 } 786 }
787 } 787 }
788 788
789 /** 789 /**
790 * Does the hash table contain an item under key (k). 790 * Does the hash table contain an item under key (k).
791 *@param k (key_type) The key to check. 791 *@param k (key_type) The key to check.
792 *@returns (bool) Whether there was an item in the hash under key (k). 792 *@returns (bool) Whether there was an item in the hash under key (k).
793 */ 793 */
794 bool has( const key &k ) const 794 bool has( const key &k ) const
795 { 795 {
796 bool bFill; 796 bool bFill;
797 core->probe( __calcHashCode( k ), k, bFill ); 797 core->probe( __calcHashCode( k ), k, bFill );
798 798
799 return bFill; 799 return bFill;
800 } 800 }
801 801
802 /** 802 /**
803 * Iteration structure for iterating through the hash. 803 * Iteration structure for iterating through the hash.
804 */ 804 */
805 typedef struct iterator 805 typedef struct iterator
806 { 806 {
807 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 807 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
808 private: 808 private:
809 iterator( MyType *hsh ) : 809 iterator( MyType *hsh ) :
810 hsh( hsh ), 810 hsh( hsh ),
811 nPos( 0 ), 811 nPos( 0 ),
812 bFinished( false ) 812 bFinished( false )
813 { 813 {
814 nPos = hsh->core->getFirstPos( bFinished ); 814 nPos = hsh->core->getFirstPos( bFinished );
815 } 815 }
816 816
817 iterator( MyType *hsh, bool bDone ) : 817 iterator( MyType *hsh, bool bDone ) :
818 hsh( hsh ), 818 hsh( hsh ),
819 nPos( 0 ), 819 nPos( 0 ),
820 bFinished( bDone ) 820 bFinished( bDone )
821 { 821 {
822 } 822 }
823 823
824 MyType *hsh; 824 MyType *hsh;
825 uint32_t nPos; 825 uint32_t nPos;
826 bool bFinished; 826 bool bFinished;
827 827
828 public: 828 public:
829 iterator( const iterator &i ) : 829 iterator( const iterator &i ) :
830 hsh( i.hsh ), 830 hsh( i.hsh ),
831 nPos( i.nPos ), 831 nPos( i.nPos ),
832 bFinished( i.bFinished ) 832 bFinished( i.bFinished )
833 { 833 {
834 } 834 }
835 835
836 iterator() : 836 iterator() :
837 hsh( NULL ), 837 hsh( NULL ),
838 nPos( NULL ), 838 nPos( NULL ),
839 bFinished( true ) 839 bFinished( true )
840 { 840 {
841 } 841 }
842 842
843 bool isValid() const 843 bool isValid() const
844 { 844 {
845 return !bFinished; 845 return !bFinished;
846 } 846 }
847 847
848 operator bool() const 848 operator bool() const
849 { 849 {
850 return !bFinished; 850 return !bFinished;
851 } 851 }
852 852
853 /** 853 /**
854 * Iterator incrementation operator. Move the iterator forward. 854 * Iterator incrementation operator. Move the iterator forward.
855 */ 855 */
856 iterator operator++( int ) 856 iterator operator++( int )
857 { 857 {
858 if( bFinished == false ) 858 if( bFinished == false )
859 nPos = hsh->core->getNextPos( nPos, bFinished ); 859 nPos = hsh->core->getNextPos( nPos, bFinished );
860 860
861 return *this; 861 return *this;
862 } 862 }
863 863
864 /** 864 /**
865 * Iterator incrementation operator. Move the iterator forward. 865 * Iterator incrementation operator. Move the iterator forward.
866 */ 866 */
867 iterator operator++() 867 iterator operator++()
868 { 868 {
869 if( bFinished == false ) 869 if( bFinished == false )
870 nPos = hsh->core->getNextPos( nPos, bFinished ); 870 nPos = hsh->core->getNextPos( nPos, bFinished );
871 871
872 return *this; 872 return *this;
873 } 873 }
874 874
875 /** 875 /**
876 * Iterator equality comparison operator. Iterators the same? 876 * Iterator equality comparison operator. Iterators the same?
877 */ 877 */
878 bool operator==( const iterator &oth ) const 878 bool operator==( const iterator &oth ) const
879 { 879 {
880 if( bFinished != oth.bFinished ) 880 if( bFinished != oth.bFinished )
881 return false; 881 return false;
882 if( bFinished == true ) 882 if( bFinished == true )
883 { 883 {
884 return true; 884 return true;
885 } 885 }
886 else 886 else
887 { 887 {
888 if( oth.nPos == nPos ) 888 if( oth.nPos == nPos )
889 return true; 889 return true;
890 return false; 890 return false;
891 } 891 }
892 } 892 }
893 893
894 /** 894 /**
895 * Iterator not equality comparison operator. Not the same? 895 * Iterator not equality comparison operator. Not the same?
896 */ 896 */
897 bool operator!=( const iterator &oth ) const 897 bool operator!=( const iterator &oth ) const
898 { 898 {
899 return !(*this == oth ); 899 return !(*this == oth );
900 } 900 }
901 901
902 /** 902 /**
903 * Iterator assignment operator. 903 * Iterator assignment operator.
904 */ 904 */
905 iterator operator=( const iterator &oth ) 905 iterator operator=( const iterator &oth )
906 { 906 {
907 hsh = oth.hsh; 907 hsh = oth.hsh;
908 nPos = oth.nPos; 908 nPos = oth.nPos;
909 bFinished = oth.bFinished; 909 bFinished = oth.bFinished;
910 return *this; 910 return *this;
911 } 911 }
912 912
913 /** 913 /**
914 * Iterator dereference operator... err.. get the value 914 * Iterator dereference operator... err.. get the value
915 *@returns (value_type &) The value behind this iterator. 915 *@returns (value_type &) The value behind this iterator.
916 */ 916 */
917 value &operator *() 917 value &operator *()
918 { 918 {
919 hsh->_hardCopy(); 919 hsh->_hardCopy();
920 return hsh->core->getValueAtPos( nPos ); 920 return hsh->core->getValueAtPos( nPos );
921 } 921 }
922 922
923 const value &operator *() const 923 const value &operator *() const
924 { 924 {
925 return hsh->core->getValueAtPos( nPos ); 925 return hsh->core->getValueAtPos( nPos );
926 } 926 }
927 927
928 /** 928 /**
929 * Get the key behind this iterator. 929 * Get the key behind this iterator.
930 *@returns (key_type &) The key behind this iterator. 930 *@returns (key_type &) The key behind this iterator.
931 */ 931 */
932 const key &getKey() const 932 const key &getKey() const
933 { 933 {
934 return hsh->core->getKeyAtPos( nPos ); 934 return hsh->core->getKeyAtPos( nPos );
935 } 935 }
936 936
937 /** 937 /**
938 * Get the value behind this iterator. 938 * Get the value behind this iterator.
939 *@returns (value_type &) The value behind this iterator. 939 *@returns (value_type &) The value behind this iterator.
940 */ 940 */
941 value &getValue() 941 value &getValue()
942 { 942 {
943 hsh->_hardCopy(); 943 hsh->_hardCopy();
944 return hsh->core->getValueAtPos( nPos ); 944 return hsh->core->getValueAtPos( nPos );
945 } 945 }
946 946
947 /** 947 /**
948 * Get the value behind this iterator. 948 * Get the value behind this iterator.
949 *@returns (value_type &) The value behind this iterator. 949 *@returns (value_type &) The value behind this iterator.
950 */ 950 */
951 const value &getValue() const 951 const value &getValue() const
952 { 952 {
953 return hsh->core->getValueAtPos( nPos ); 953 return hsh->core->getValueAtPos( nPos );
954 } 954 }
955 } iterator; 955 } iterator;
956 956
957 /** 957 /**
958 * Iteration structure for iterating through the hash (const). 958 * Iteration structure for iterating through the hash (const).
959 */ 959 */
960 typedef struct const_iterator 960 typedef struct const_iterator
961 { 961 {
962 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 962 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
963 private: 963 private:
964 const_iterator( const MyType *hsh ) : 964 const_iterator( const MyType *hsh ) :
965 hsh( hsh ), 965 hsh( hsh ),
966 nPos( 0 ), 966 nPos( 0 ),
967 bFinished( false ) 967 bFinished( false )
968 { 968 {
969 nPos = hsh->core->getFirstPos( bFinished ); 969 nPos = hsh->core->getFirstPos( bFinished );
970 } 970 }
971 971
972 const_iterator( const MyType *hsh, bool bDone ) : 972 const_iterator( const MyType *hsh, bool bDone ) :
973 hsh( hsh ), 973 hsh( hsh ),
974 nPos( 0 ), 974 nPos( 0 ),
975 bFinished( bDone ) 975 bFinished( bDone )
976 { 976 {
977 } 977 }
978 978
979 const MyType *hsh; 979 const MyType *hsh;
980 uint32_t nPos; 980 uint32_t nPos;
981 bool bFinished; 981 bool bFinished;
982 982
983 public: 983 public:
984 const_iterator() : 984 const_iterator() :
985 hsh( NULL ), 985 hsh( NULL ),
986 nPos( 0 ), 986 nPos( 0 ),
987 bFinished( true ) 987 bFinished( true )
988 { 988 {
989 } 989 }
990 990
991 const_iterator( const const_iterator &src ) : 991 const_iterator( const const_iterator &src ) :
992 hsh( src.hsh ), 992 hsh( src.hsh ),
993 nPos( src.nPos ), 993 nPos( src.nPos ),
994 bFinished( src.bFinished ) 994 bFinished( src.bFinished )
995 { 995 {
996 } 996 }
997 997
998 const_iterator( const iterator &src ) : 998 const_iterator( const iterator &src ) :
999 hsh( src.hsh ), 999 hsh( src.hsh ),
1000 nPos( src.nPos ), 1000 nPos( src.nPos ),
1001 bFinished( src.bFinished ) 1001 bFinished( src.bFinished )
1002 { 1002 {
1003 } 1003 }
1004 1004
1005 bool isValid() const 1005 bool isValid() const
1006 { 1006 {
1007 return !bFinished; 1007 return !bFinished;
1008 } 1008 }
1009 1009
1010 operator bool() const 1010 operator bool() const
1011 { 1011 {
1012 return !bFinished; 1012 return !bFinished;
1013 } 1013 }
1014 1014
1015 /** 1015 /**
1016 * Iterator incrementation operator. Move the iterator forward. 1016 * Iterator incrementation operator. Move the iterator forward.
1017 */ 1017 */
1018 const_iterator operator++( int ) 1018 const_iterator operator++( int )
1019 { 1019 {
1020 if( bFinished == false ) 1020 if( bFinished == false )
1021 nPos = hsh->core->getNextPos( nPos, bFinished ); 1021 nPos = hsh->core->getNextPos( nPos, bFinished );
1022 1022
1023 return *this; 1023 return *this;
1024 } 1024 }
1025 1025
1026 /** 1026 /**
1027 * Iterator incrementation operator. Move the iterator forward. 1027 * Iterator incrementation operator. Move the iterator forward.
1028 */ 1028 */
1029 const_iterator operator++() 1029 const_iterator operator++()
1030 { 1030 {
1031 if( bFinished == false ) 1031 if( bFinished == false )
1032 nPos = hsh->core->getNextPos( nPos, bFinished ); 1032 nPos = hsh->core->getNextPos( nPos, bFinished );
1033 1033
1034 return *this; 1034 return *this;
1035 } 1035 }
1036 1036
1037 /** 1037 /**
1038 * Iterator equality comparison operator. Iterators the same? 1038 * Iterator equality comparison operator. Iterators the same?
1039 */ 1039 */
1040 bool operator==( const const_iterator &oth ) const 1040 bool operator==( const const_iterator &oth ) const
1041 { 1041 {
1042 if( bFinished != oth.bFinished ) 1042 if( bFinished != oth.bFinished )
1043 return false; 1043 return false;
1044 if( bFinished == true ) 1044 if( bFinished == true )
1045 { 1045 {
1046 return true; 1046 return true;
1047 } 1047 }
1048 else 1048 else
1049 { 1049 {
1050 if( oth.nPos == nPos ) 1050 if( oth.nPos == nPos )
1051 return true; 1051 return true;
1052 return false; 1052 return false;
1053 } 1053 }
1054 } 1054 }
1055 1055
1056 /** 1056 /**
1057 * Iterator not equality comparison operator. Not the same? 1057 * Iterator not equality comparison operator. Not the same?
1058 */ 1058 */
1059 bool operator!=( const const_iterator &oth ) const 1059 bool operator!=( const const_iterator &oth ) const
1060 { 1060 {
1061 return !(*this == oth ); 1061 return !(*this == oth );
1062 } 1062 }
1063 1063
1064 /** 1064 /**
1065 * Iterator assignment operator. 1065 * Iterator assignment operator.
1066 */ 1066 */
1067 const_iterator operator=( const const_iterator &oth ) 1067 const_iterator operator=( const const_iterator &oth )
1068 { 1068 {
1069 hsh = oth.hsh; 1069 hsh = oth.hsh;
1070 nPos = oth.nPos; 1070 nPos = oth.nPos;
1071 bFinished = oth.bFinished; 1071 bFinished = oth.bFinished;
1072 return *this; 1072 return *this;
1073 } 1073 }
1074 1074
1075 /** 1075 /**
1076 * Iterator dereference operator... err.. get the value 1076 * Iterator dereference operator... err.. get the value
1077 *@returns (value_type &) The value behind this iterator. 1077 *@returns (value_type &) The value behind this iterator.
1078 */ 1078 */
1079 const value &operator *() const 1079 const value &operator *() const
1080 { 1080 {
1081 return hsh->core->getValueAtPos( nPos ); 1081 return hsh->core->getValueAtPos( nPos );
1082 } 1082 }
1083 1083
1084 /** 1084 /**
1085 * Get the key behind this iterator. 1085 * Get the key behind this iterator.
1086 *@returns (key_type &) The key behind this iterator. 1086 *@returns (key_type &) The key behind this iterator.
1087 */ 1087 */
1088 const key &getKey() const 1088 const key &getKey() const
1089 { 1089 {
1090 return hsh->core->getKeyAtPos( nPos ); 1090 return hsh->core->getKeyAtPos( nPos );
1091 } 1091 }
1092 1092
1093 /** 1093 /**
1094 * Get the value behind this iterator. 1094 * Get the value behind this iterator.
1095 *@returns (value_type &) The value behind this iterator. 1095 *@returns (value_type &) The value behind this iterator.
1096 */ 1096 */
1097 const value &getValue() const 1097 const value &getValue() const
1098 { 1098 {
1099 return hsh->core->getValueAtPos( nPos ); 1099 return hsh->core->getValueAtPos( nPos );
1100 } 1100 }
1101 } const_iterator; 1101 } const_iterator;
1102 1102
1103 /** 1103 /**
1104 * Get an iterator pointing to the first item in the hash table. 1104 * Get an iterator pointing to the first item in the hash table.
1105 *@returns (iterator) An iterator pointing to the first item in the 1105 *@returns (iterator) An iterator pointing to the first item in the
1106 * hash table. 1106 * hash table.
1107 */ 1107 */
1108 iterator begin() 1108 iterator begin()
1109 { 1109 {
1110 return iterator( this ); 1110 return iterator( this );
1111 } 1111 }
1112 1112
1113 const_iterator begin() const 1113 const_iterator begin() const
1114 { 1114 {
1115 return const_iterator( this ); 1115 return const_iterator( this );
1116 } 1116 }
1117 1117
1118 /** 1118 /**
1119 * Get an iterator pointing to a point just past the last item in the 1119 * Get an iterator pointing to a point just past the last item in the
1120 * hash table. 1120 * hash table.
1121 *@returns (iterator) An iterator pointing to a point just past the 1121 *@returns (iterator) An iterator pointing to a point just past the
1122 * last item in the hash table. 1122 * last item in the hash table.
1123 */ 1123 */
1124 iterator end() 1124 iterator end()
1125 { 1125 {
1126 return iterator( this, true ); 1126 return iterator( this, true );
1127 } 1127 }
1128 1128
1129 const_iterator end() const 1129 const_iterator end() const
1130 { 1130 {
1131 return const_iterator( this, true ); 1131 return const_iterator( this, true );
1132 } 1132 }
1133 1133
1134 /** 1134 /**
1135 * Get a list of all the keys in the hash table. 1135 * Get a list of all the keys in the hash table.
1136 *@returns (std::list<key_type>) The list of keys in the hash table. 1136 *@returns (std::list<key_type>) The list of keys in the hash table.
1137 */ 1137 */
1138 Bu::List<key> getKeys() const 1138 Bu::List<key> getKeys() const
1139 { 1139 {
1140 Bu::List<key> lKeys; 1140 Bu::List<key> lKeys;
1141 1141
1142 for( uint32_t j = 0; j < core->nCapacity; j++ ) 1142 for( uint32_t j = 0; j < core->nCapacity; j++ )
1143 { 1143 {
1144 if( core->isFilled( j ) ) 1144 if( core->isFilled( j ) )
1145 { 1145 {
1146 if( !core->isDeleted( j ) ) 1146 if( !core->isDeleted( j ) )
1147 { 1147 {
1148 lKeys.append( core->aKeys[j] ); 1148 lKeys.append( core->aKeys[j] );
1149 } 1149 }
1150 } 1150 }
1151 } 1151 }
1152 1152
1153 return lKeys; 1153 return lKeys;
1154 } 1154 }
1155 1155
1156 Bu::List<value> getValues() const 1156 Bu::List<value> getValues() const
1157 { 1157 {
1158 Bu::List<value> lValues; 1158 Bu::List<value> lValues;
1159 1159
1160 for( uint32_t j = 0; j < core->nCapacity; j++ ) 1160 for( uint32_t j = 0; j < core->nCapacity; j++ )
1161 { 1161 {
1162 if( core->isFilled( j ) ) 1162 if( core->isFilled( j ) )
1163 { 1163 {
1164 if( !core->isDeleted( j ) ) 1164 if( !core->isDeleted( j ) )
1165 { 1165 {
1166 lValues.append( core->aValues[j] ); 1166 lValues.append( core->aValues[j] );
1167 } 1167 }
1168 } 1168 }
1169 } 1169 }
1170 1170
1171 return lValues; 1171 return lValues;
1172 } 1172 }
1173 1173
1174 bool operator==( const MyType &rhs ) const 1174 bool operator==( const MyType &rhs ) const
1175 { 1175 {
1176 if( this == &rhs ) 1176 if( this == &rhs )
1177 return true; 1177 return true;
1178 if( core == rhs.core ) 1178 if( core == rhs.core )
1179 return true; 1179 return true;
1180 if( core == NULL || rhs.core == NULL ) 1180 if( core == NULL || rhs.core == NULL )
1181 return false; 1181 return false;
1182 if( getSize() != rhs.getSize() ) 1182 if( getSize() != rhs.getSize() )
1183 return false; 1183 return false;
1184 1184
1185 for( uint32_t j = 0; j < core->nCapacity; j++ ) 1185 for( uint32_t j = 0; j < core->nCapacity; j++ )
1186 { 1186 {
1187 if( core->isFilled( j ) ) 1187 if( core->isFilled( j ) )
1188 { 1188 {
1189 if( !core->isDeleted( j ) ) 1189 if( !core->isDeleted( j ) )
1190 { 1190 {
1191 // Check to see if this key is in the other hash 1191 // Check to see if this key is in the other hash
1192 if( rhs.has( core->aKeys[j] ) ) 1192 if( rhs.has( core->aKeys[j] ) )
1193 { 1193 {
1194 if( !(core->aValues[j] == rhs.get( core->aKeys[j]) ) ) 1194 if( !(core->aValues[j] == rhs.get( core->aKeys[j]) ) )
1195 { 1195 {
1196 return false; 1196 return false;
1197 } 1197 }
1198 } 1198 }
1199 else 1199 else
1200 { 1200 {
1201 return false; 1201 return false;
1202 } 1202 }
1203 } 1203 }
1204 } 1204 }
1205 } 1205 }
1206 1206
1207 return true; 1207 return true;
1208 } 1208 }
1209 1209
1210 bool operator!=( const MyType &rhs ) const 1210 bool operator!=( const MyType &rhs ) const
1211 { 1211 {
1212 return !(*this == rhs); 1212 return !(*this == rhs);
1213 } 1213 }
1214 1214
1215 MyType &operator+=( const MyType &rhs ) 1215 MyType &operator+=( const MyType &rhs )
1216 { 1216 {
1217 if( this == &rhs ) 1217 if( this == &rhs )
1218 return *this; 1218 return *this;
1219 if( core == rhs.core ) 1219 if( core == rhs.core )
1220 return *this; 1220 return *this;
1221 if( core == NULL || rhs.core == NULL ) 1221 if( core == NULL || rhs.core == NULL )
1222 return *this; 1222 return *this;
1223 1223
1224 for( const_iterator i = rhs.begin(); i; i++ ) 1224 for( const_iterator i = rhs.begin(); i; i++ )
1225 insert( i.getKey(), i.getValue() ); 1225 insert( i.getKey(), i.getValue() );
1226 1226
1227 return *this; 1227 return *this;
1228 } 1228 }
1229 1229
1230 protected: 1230 protected:
1231 virtual Core *_copyCore( Core *src ) 1231 virtual Core *_copyCore( Core *src )
1232 { 1232 {
1233 Core *pRet = _allocateCore(); 1233 Core *pRet = _allocateCore();
1234 1234
1235 pRet->nFilled = 0; 1235 pRet->nFilled = 0;
1236 pRet->nDeleted = 0; 1236 pRet->nDeleted = 0;
1237 pRet->nCapacity = src->nCapacity; 1237 pRet->nCapacity = src->nCapacity;
1238 pRet->nKeysSize = bitsTo<uint32_t>( pRet->nCapacity ); 1238 pRet->nKeysSize = bitsTo<uint32_t>( pRet->nCapacity );
1239 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize ); 1239 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize );
1240 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize ); 1240 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize );
1241 pRet->clearBits(); 1241 pRet->clearBits();
1242 1242
1243 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity ); 1243 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity );
1244 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity ); 1244 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity );
1245 pRet->aValues = pRet->va.allocate( pRet->nCapacity ); 1245 pRet->aValues = pRet->va.allocate( pRet->nCapacity );
1246 1246
1247 for( uint32_t j = 0; j < src->nCapacity; j++ ) 1247 for( uint32_t j = 0; j < src->nCapacity; j++ )
1248 { 1248 {
1249 if( src->isFilled( j ) && !src->isDeleted( j ) ) 1249 if( src->isFilled( j ) && !src->isDeleted( j ) )
1250 { 1250 {
1251 pRet->insert( src->aKeys[j], src->aValues[j] ); 1251 pRet->insert( src->aKeys[j], src->aValues[j] );
1252 } 1252 }
1253 } 1253 }
1254 1254
1255 return pRet; 1255 return pRet;
1256 } 1256 }
1257 }; 1257 };
1258 1258
1259 template<typename T> uint32_t __calcHashCode( const T &k ) 1259 template<typename T> uint32_t __calcHashCode( const T &k )
1260 { 1260 {
1261 return static_cast<uint32_t>( k ); 1261 return static_cast<uint32_t>( k );
1262 } 1262 }
1263 1263
1264 template<typename T> bool __cmpHashKeys( const T &a, const T &b ) 1264 template<typename T> bool __cmpHashKeys( const T &a, const T &b )
1265 { 1265 {
1266 return (a == b); 1266 return (a == b);
1267 } 1267 }
1268 1268
1269 template<> uint32_t __calcHashCode<const char *>( const char * const &k ); 1269 template<> uint32_t __calcHashCode<const char *>( const char * const &k );
1270 template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b ); 1270 template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
1271 1271
1272 template<> uint32_t __calcHashCode<char *>( char * const &k ); 1272 template<> uint32_t __calcHashCode<char *>( char * const &k );
1273 template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b ); 1273 template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
1274 1274
1275 class Formatter; 1275 class Formatter;
1276 Formatter &operator<<( Formatter &rOut, char *sStr ); 1276 Formatter &operator<<( Formatter &rOut, char *sStr );
1277 Formatter &operator<<( Formatter &rOut, signed char c ); 1277 Formatter &operator<<( Formatter &rOut, signed char c );
1278 template<typename key, typename value> 1278 template<typename key, typename value>
1279 Formatter &operator<<( Formatter &f, const Bu::Hash<key, value> &l ) 1279 Formatter &operator<<( Formatter &f, const Bu::Hash<key, value> &l )
1280 { 1280 {
1281 f << '{'; 1281 f << '{';
1282 for( typename Bu::Hash<key,value>::const_iterator i = l.begin(); i; i++ ) 1282 for( typename Bu::Hash<key,value>::const_iterator i = l.begin(); i; i++ )
1283 { 1283 {
1284 if( i != l.begin() ) 1284 if( i != l.begin() )
1285 f << ", "; 1285 f << ", ";
1286 f << i.getKey() << ": " << i.getValue(); 1286 f << i.getKey() << ": " << i.getValue();
1287 } 1287 }
1288 f << '}'; 1288 f << '}';
1289 1289
1290 return f; 1290 return f;
1291 } 1291 }
1292 1292
1293 template<typename key, typename value, typename a, typename b, 1293 template<typename key, typename value, typename a, typename b,
1294 typename c, typename d> 1294 typename c, typename d>
1295 ArchiveBase &operator<<( ArchiveBase &ar, const Hash<key,value,a,b,c,d> &h ) 1295 ArchiveBase &operator<<( ArchiveBase &ar, const Hash<key,value,a,b,c,d> &h )
1296 { 1296 {
1297 long iSize = h.getSize(); 1297 long iSize = h.getSize();
1298 ar << iSize; 1298 ar << iSize;
1299 for( typename Hash<key,value,a,b,c,d>::const_iterator i = h.begin(); i != h.end(); i++ ) 1299 for( typename Hash<key,value,a,b,c,d>::const_iterator i = h.begin(); i != h.end(); i++ )
1300 { 1300 {
1301 ar << (i.getKey()); 1301 ar << (i.getKey());
1302 ar << (i.getValue()); 1302 ar << (i.getValue());
1303 } 1303 }
1304 1304
1305 return ar; 1305 return ar;
1306 } 1306 }
1307 1307
1308 template<typename key, typename value, typename a, typename b, 1308 template<typename key, typename value, typename a, typename b,
1309 typename c, typename d> 1309 typename c, typename d>
1310 ArchiveBase &operator>>( ArchiveBase &ar, Hash<key,value,a,b,c,d> &h ) 1310 ArchiveBase &operator>>( ArchiveBase &ar, Hash<key,value,a,b,c,d> &h )
1311 { 1311 {
1312 h.clear(); 1312 h.clear();
1313 long nSize; 1313 long nSize;
1314 ar >> nSize; 1314 ar >> nSize;
1315 1315
1316 for( long j = 0; j < nSize; j++ ) 1316 for( long j = 0; j < nSize; j++ )
1317 { 1317 {
1318 key k; value v; 1318 key k; value v;
1319 ar >> k >> v; 1319 ar >> k >> v;
1320 h.insert( k, v ); 1320 h.insert( k, v );
1321 } 1321 }
1322 1322
1323 return ar; 1323 return ar;
1324 } 1324 }
1325} 1325}
1326 1326
1327#endif 1327#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-30 23:24:13 +0000