aboutsummaryrefslogtreecommitdiff
path: root/src/hash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/hash.h')
-rw-r--r--src/hash.h1036
1 files changed, 528 insertions, 508 deletions
diff --git a/src/hash.h b/src/hash.h
index 1cb539b..714a7f7 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -12,7 +12,8 @@
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/list.h" 13#include "bu/list.h"
14#include "bu/util.h" 14#include "bu/util.h"
15#include "archivebase.h" 15#include "bu/archivebase.h"
16#include "bu/sharedcore.h"
16 17
17#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) 18#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
18 19
@@ -49,137 +50,354 @@ namespace Bu
49 } 50 }
50 }; 51 };
51 52
52 template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> > 53 template<typename key, typename value, typename sizecalc, typename keyalloc,
54 typename valuealloc, typename challoc>
53 class Hash; 55 class Hash;
54 56
55 template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> > 57 template<typename key, typename value, typename sizecalc, typename keyalloc,
56 struct HashProxy 58 typename valuealloc, typename challoc >
59 class HashCore
57 { 60 {
58 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>; 61 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
62 friend class SharedCore<
63 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
64 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
65 >;
59 private: 66 private:
60 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, const key *k, uint32_t nPos, uint32_t hash ) : 67 HashCore() :
61 hsh( h ), 68 nCapacity( 0 ),
62 pKey( k ), 69 nFilled( 0 ),
63 nPos( nPos ), 70 nDeleted( 0 ),
64 hash( hash ), 71 bFilled( NULL ),
65 bFilled( false ) 72 bDeleted( NULL ),
73 aKeys( NULL ),
74 aValues( NULL ),
75 aHashCodes( NULL )
66 { 76 {
67 } 77 }
68 78
69 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) : 79 virtual ~HashCore()
70 hsh( h ),
71 nPos( nPos ),
72 pValue( pValue ),
73 bFilled( true )
74 { 80 {
81 clear();
75 } 82 }
76 83
77 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 84 void init()
78 const key *pKey; 85 {
79 uint32_t nPos; 86 if( nCapacity > 0 )
80 _value *pValue; 87 return;
81 uint32_t hash;
82 bool bFilled;
83 88
84 public: 89 nCapacity = 11;
85 /** 90 nKeysSize = bitsToBytes( nCapacity );
86 * Cast operator for HashProxy. 91 bFilled = ca.allocate( nKeysSize );
87 *@returns (value_type &) The value the HashProxy is pointing to. 92 bDeleted = ca.allocate( nKeysSize );
88 */ 93 clearBits();
89 operator _value &() 94
95 aHashCodes = ca.allocate( nCapacity );
96 aKeys = ka.allocate( nCapacity );
97 aValues = va.allocate( nCapacity );
98 }
99
100 void clearBits()
90 { 101 {
91 if( bFilled == false ) 102 if( nCapacity == 0 )
92 throw HashException( 103 return;
93 excodeNotFilled, 104
94 "No data assosiated with that key." 105 for( uint32_t j = 0; j < nKeysSize; j++ )
95 ); 106 {
96 return *pValue; 107 bFilled[j] = bDeleted[j] = 0;
108 }
97 } 109 }
98 110
99 /** 111 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
100 * Direct function for retrieving a value out of the HashProxy.
101 *@returns (value_type &) The value pointed to by this HashProxy.
102 */
103 DEPRECATED
104 _value &value()
105 { 112 {
106 if( bFilled == false ) 113 init();
107 throw HashException( 114
108 excodeNotFilled, 115 bFilled[loc/32] |= (1<<(loc%32));
109 "No data assosiated with that key." 116 va.construct( &aValues[loc], v );
110 ); 117 ka.construct( &aKeys[loc], k );
111 return *pValue; 118 aHashCodes[loc] = hash;
119 nFilled++;
120 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
121 // nFilled, nDeleted, nCapacity );
122 }
123
124 void _erase( uint32_t loc )
125 {
126 if( nCapacity == 0 )
127 return;
128
129 bDeleted[loc/32] |= (1<<(loc%32));
130 va.destroy( &aValues[loc] );
131 ka.destroy( &aKeys[loc] );
132 nDeleted++;
133 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
134 // nFilled, nDeleted, nCapacity );
135 }
136
137 key &getKeyAtPos( uint32_t nPos )
138 {
139 if( nPos >= nCapacity )
140 throw HashException("Referenced position invalid.");
141 return aKeys[nPos];
112 } 142 }
113 143
114 /** 144 const key &getKeyAtPos( uint32_t nPos ) const
115 * Direct function for retrieving a value out of the HashProxy.
116 *@returns (value_type &) The value pointed to by this HashProxy.
117 */
118 _value &getValue()
119 { 145 {
120 if( bFilled == false ) 146 if( nPos >= nCapacity )
121 throw HashException( 147 throw HashException("Referenced position invalid.");
122 excodeNotFilled, 148 return aKeys[nPos];
123 "No data assosiated with that key." 149 }
124 ); 150
125 return *pValue; 151 value &getValueAtPos( uint32_t nPos )
152 {
153 if( nPos >= nCapacity )
154 throw HashException("Referenced position invalid.");
155 return aValues[nPos];
156 }
157
158 const value &getValueAtPos( uint32_t nPos ) const
159 {
160 if( nPos >= nCapacity )
161 throw HashException("Referenced position invalid.");
162 return aValues[nPos];
126 } 163 }
127 164
128 /** 165 uint32_t getFirstPos( bool &bFinished ) const
129 * Whether this HashProxy points to something real or not.
130 */
131 bool isFilled()
132 { 166 {
133 return bFilled; 167 for( uint32_t j = 0; j < nCapacity; j++ )
168 {
169 if( isFilled( j ) )
170 if( !isDeleted( j ) )
171 return j;
172 }
173
174 bFinished = true;
175 return 0;
134 } 176 }
135 177
136 /** 178 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
137 * Erase the data pointed to by this HashProxy.
138 */
139 void erase()
140 { 179 {
141 if( bFilled ) 180 for( uint32_t j = nPos+1; j < nCapacity; j++ )
142 { 181 {
143 hsh._erase( nPos ); 182 if( isFilled( j ) )
144 hsh.onDelete(); 183 if( !isDeleted( j ) )
184 return j;
145 } 185 }
186
187 bFinished = true;
188 return 0;
146 } 189 }
147 190
148 /** 191 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
149 * Assign data to this point in the hash table.
150 *@param nval (value_type) the data to assign.
151 */
152 _value operator=( _value nval )
153 { 192 {
154 if( bFilled ) 193 init();
194
195 uint32_t nCur = hash%nCapacity;
196
197 // First we scan to see if the key is already there, abort if we
198 // run out of probing room, or we find a non-filled entry
199 int8_t j;
200 for( j = 0;
201 isFilled( nCur ) && j < 32;
202 nCur = (nCur + (1<<j))%nCapacity, j++
203 )
155 { 204 {
156 hsh.va.destroy( &hsh.aValues[nPos] ); 205 // Is this the same hash code we were looking for?
157 hsh.va.construct( &hsh.aValues[nPos], nval ); 206 if( hash == aHashCodes[nCur] )
158 hsh.onUpdate(); 207 {
208 // Skip over deleted entries. Deleted entries are also filled,
209 // so we only have to do this check here.
210 if( isDeleted( nCur ) )
211 continue;
212
213 // Is it really the same key? (for safety)
214 if( __cmpHashKeys( aKeys[nCur], k ) == true )
215 {
216 bFill = true;
217 return nCur;
218 }
219 }
220 }
221
222 // This is our insurance, if the table is full, then go ahead and
223 // rehash, then try again.
224 if( (isFilled( nCur ) || j == 32) && rehash == true )
225 {
226 reHash( szCalc( nCapacity, nFilled, nDeleted ) );
227
228 // This is potentially dangerous, and could cause an infinite loop.
229 // Be careful writing probe, eh?
230 return probe( hash, k, bFill );
231 }
232
233 bFill = false;
234 return nCur;
235 }
236
237 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
238 {
239 if( nCapacity == 0 )
240 throw Bu::ExceptionBase("Probe in empty hash table.");
241
242 uint32_t nCur = hash%nCapacity;
243
244 // First we scan to see if the key is already there, abort if we
245 // run out of probing room, or we find a non-filled entry
246 for( int8_t j = 0;
247 isFilled( nCur ) && j < 32;
248 nCur = (nCur + (1<<j))%nCapacity, j++
249 )
250 {
251 // Is this the same hash code we were looking for?
252 if( hash == aHashCodes[nCur] )
253 {
254 // Skip over deleted entries. Deleted entries are also filled,
255 // so we only have to do this check here.
256 if( isDeleted( nCur ) )
257 continue;
258
259 // Is it really the same key? (for safety)
260 if( __cmpHashKeys( aKeys[nCur], k ) == true )
261 {
262 bFill = true;
263 return nCur;
264 }
265 }
266 }
267
268 bFill = false;
269 return nCur;
270 }
271
272 void insert( const key &k, const value &v )
273 {
274 uint32_t hash = __calcHashCode( k );
275 bool bFill;
276 uint32_t nPos = probe( hash, k, bFill );
277
278 if( bFill )
279 {
280 va.destroy( &aValues[nPos] );
281 va.construct( &aValues[nPos], v );
159 } 282 }
160 else 283 else
161 { 284 {
162 hsh.fill( nPos, *pKey, nval, hash ); 285 fill( nPos, k, v, hash );
163 hsh.onInsert();
164 } 286 }
287 }
165 288
166 return nval; 289 void reHash( uint32_t nNewSize )
290 {
291 //printf("---REHASH---");
292 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
293 // nFilled, nDeleted, nCapacity );
294
295 // Save all the old data
296 uint32_t nOldCapacity = nCapacity;
297 uint32_t *bOldFilled = bFilled;
298 uint32_t *aOldHashCodes = aHashCodes;
299 uint32_t nOldKeysSize = nKeysSize;
300 uint32_t *bOldDeleted = bDeleted;
301 value *aOldValues = aValues;
302 key *aOldKeys = aKeys;
303
304 // Calculate new sizes
305 nCapacity = nNewSize;
306 nKeysSize = bitsToBytes( nCapacity );
307
308 // Allocate new memory + prep
309 bFilled = ca.allocate( nKeysSize );
310 bDeleted = ca.allocate( nKeysSize );
311 clearBits();
312
313 aHashCodes = ca.allocate( nCapacity );
314 aKeys = ka.allocate( nCapacity );
315 aValues = va.allocate( nCapacity );
316
317 nDeleted = nFilled = 0;
318
319 // Re-insert all of the old data (except deleted items)
320 for( uint32_t j = 0; j < nOldCapacity; j++ )
321 {
322 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
323 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
324 {
325 insert( aOldKeys[j], aOldValues[j] );
326 }
327 }
328
329 // Delete all of the old data
330 for( uint32_t j = 0; j < nOldCapacity; j++ )
331 {
332 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
333 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
334 {
335 va.destroy( &aOldValues[j] );
336 ka.destroy( &aOldKeys[j] );
337 }
338 }
339 va.deallocate( aOldValues, nOldCapacity );
340 ka.deallocate( aOldKeys, nOldCapacity );
341 ca.deallocate( bOldFilled, nOldKeysSize );
342 ca.deallocate( bOldDeleted, nOldKeysSize );
343 ca.deallocate( aOldHashCodes, nOldCapacity );
167 } 344 }
168 345
169 /** 346 bool isFilled( uint32_t loc ) const
170 * Pointer extraction operator. Access to members of data pointed to
171 * by HashProxy.
172 *@returns (value_type *)
173 */
174 _value *operator->()
175 { 347 {
176 if( bFilled == false ) 348 if( loc >= nCapacity )
177 throw HashException( 349 throw HashException("Referenced position invalid.");
178 excodeNotFilled, 350 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
179 "No data assosiated with that key." 351 }
180 ); 352
181 return pValue; 353 bool isDeleted( uint32_t loc ) const
354 {
355 if( loc >= nCapacity )
356 throw HashException("Referenced position invalid.");
357 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
358 }
359
360 void clear()
361 {
362 for( uint32_t j = 0; j < nCapacity; j++ )
363 {
364 if( isFilled( j ) )
365 if( !isDeleted( j ) )
366 {
367 va.destroy( &aValues[j] );
368 ka.destroy( &aKeys[j] );
369 }
370 }
371 va.deallocate( aValues, nCapacity );
372 ka.deallocate( aKeys, nCapacity );
373 ca.deallocate( bFilled, nKeysSize );
374 ca.deallocate( bDeleted, nKeysSize );
375 ca.deallocate( aHashCodes, nCapacity );
376
377 bFilled = NULL;
378 bDeleted = NULL;
379 aKeys = NULL;
380 aValues = NULL;
381 aHashCodes = NULL;
382
383 nCapacity = 0;
384 nFilled = 0;
385 nDeleted = 0;
182 } 386 }
387
388 uint32_t nCapacity;
389 uint32_t nFilled;
390 uint32_t nDeleted;
391 uint32_t *bFilled;
392 uint32_t *bDeleted;
393 uint32_t nKeysSize;
394 key *aKeys;
395 value *aValues;
396 uint32_t *aHashCodes;
397 valuealloc va;
398 keyalloc ka;
399 challoc ca;
400 sizecalc szCalc;
183 }; 401 };
184 402
185 /** 403 /**
@@ -224,119 +442,38 @@ namespace Bu
224 *@param challoc (typename) Byte allocator for bitflags 442 *@param challoc (typename) Byte allocator for bitflags
225 *@ingroup Containers 443 *@ingroup Containers
226 */ 444 */
227 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 445 template<typename key, typename value,
228 class Hash 446 typename sizecalc = __calcNextTSize_fast,
447 typename keyalloc = std::allocator<key>,
448 typename valuealloc = std::allocator<value>,
449 typename challoc = std::allocator<uint32_t>
450 >
451 class Hash : public SharedCore<
452 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
453 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
454 >
229 { 455 {
230 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>; 456 private:
457 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core;
231 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType; 458 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType;
459 protected:
460 using SharedCore<MyType, Core>::core;
461 using SharedCore<MyType, Core>::_hardCopy;
462 using SharedCore<MyType, Core>::_resetCore;
463 using SharedCore<MyType, Core>::_allocateCore;
464
232 public: 465 public:
233 Hash() : 466 Hash()
234 nCapacity( 11 ),
235 nFilled( 0 ),
236 nDeleted( 0 ),
237 bFilled( NULL ),
238 bDeleted( NULL ),
239 aKeys( NULL ),
240 aValues( NULL ),
241 aHashCodes( NULL )
242 { 467 {
243 nKeysSize = bitsToBytes( nCapacity );
244 bFilled = ca.allocate( nKeysSize );
245 bDeleted = ca.allocate( nKeysSize );
246 clearBits();
247
248 aHashCodes = ca.allocate( nCapacity );
249 aKeys = ka.allocate( nCapacity );
250 aValues = va.allocate( nCapacity );
251 } 468 }
252 469
253 Hash( const Hash &src ) : 470 Hash( const MyType &src ) :
254 nCapacity( src.nCapacity ), 471 SharedCore<MyType, Core >( src )
255 nFilled( 0 ),
256 nDeleted( 0 ),
257 bFilled( NULL ),
258 bDeleted( NULL ),
259 aKeys( NULL ),
260 aValues( NULL ),
261 aHashCodes( NULL )
262 { 472 {
263 nKeysSize = bitsToBytes( nCapacity );
264 bFilled = ca.allocate( nKeysSize );
265 bDeleted = ca.allocate( nKeysSize );
266 clearBits();
267
268 aHashCodes = ca.allocate( nCapacity );
269 aKeys = ka.allocate( nCapacity );
270 aValues = va.allocate( nCapacity );
271
272 for( uint32_t j = 0; j < src.nCapacity; j++ )
273 {
274 if( src.isFilled( j ) && !src.isDeleted( j ) )
275 {
276 insert( src.aKeys[j], src.aValues[j] );
277 }
278 }
279 }
280
281 /**
282 * Hashtable assignment operator. Clears this hashtable and
283 * copies RH into it.
284 */
285 Hash &operator=( const Hash &src )
286 {
287 for( uint32_t j = 0; j < nCapacity; j++ )
288 {
289 if( isFilled( j ) && !isDeleted( j ) )
290 {
291 va.destroy( &aValues[j] );
292 ka.destroy( &aKeys[j] );
293 }
294 }
295 va.deallocate( aValues, nCapacity );
296 ka.deallocate( aKeys, nCapacity );
297 ca.deallocate( bFilled, nKeysSize );
298 ca.deallocate( bDeleted, nKeysSize );
299 ca.deallocate( aHashCodes, nCapacity );
300
301 nFilled = 0;
302 nDeleted = 0;
303 nCapacity = src.nCapacity;
304 nKeysSize = bitsToBytes( nCapacity );
305 bFilled = ca.allocate( nKeysSize );
306 bDeleted = ca.allocate( nKeysSize );
307 clearBits();
308
309 aHashCodes = ca.allocate( nCapacity );
310 aKeys = ka.allocate( nCapacity );
311 aValues = va.allocate( nCapacity );
312
313 for( uint32_t j = 0; j < src.nCapacity; j++ )
314 {
315 if( src.isFilled( j ) && !src.isDeleted( j ) )
316 {
317 insert( src.aKeys[j], src.aValues[j] );
318 }
319 }
320
321 return *this;
322 } 473 }
323 474
324 virtual ~Hash() 475 virtual ~Hash()
325 { 476 {
326 for( uint32_t j = 0; j < nCapacity; j++ )
327 {
328 if( isFilled( j ) )
329 if( !isDeleted( j ) )
330 {
331 va.destroy( &aValues[j] );
332 ka.destroy( &aKeys[j] );
333 }
334 }
335 va.deallocate( aValues, nCapacity );
336 ka.deallocate( aKeys, nCapacity );
337 ca.deallocate( bFilled, nKeysSize );
338 ca.deallocate( bDeleted, nKeysSize );
339 ca.deallocate( aHashCodes, nCapacity );
340 } 477 }
341 478
342 /** 479 /**
@@ -345,7 +482,7 @@ namespace Bu
345 */ 482 */
346 uint32_t getCapacity() const 483 uint32_t getCapacity() const
347 { 484 {
348 return nCapacity; 485 return core->nCapacity;
349 } 486 }
350 487
351 /** 488 /**
@@ -355,7 +492,7 @@ namespace Bu
355 */ 492 */
356 uint32_t getFill() const 493 uint32_t getFill() const
357 { 494 {
358 return nFilled; 495 return core->nFilled;
359 } 496 }
360 497
361 /** 498 /**
@@ -364,12 +501,12 @@ namespace Bu
364 */ 501 */
365 uint32_t getSize() const 502 uint32_t getSize() const
366 { 503 {
367 return nFilled-nDeleted; 504 return core->nFilled-core->nDeleted;
368 } 505 }
369 506
370 bool isEmpty() const 507 bool isEmpty() const
371 { 508 {
372 return (nFilled-nDeleted) == 0; 509 return (core->nFilled-core->nDeleted) == 0;
373 } 510 }
374 511
375 /** 512 /**
@@ -379,27 +516,140 @@ namespace Bu
379 */ 516 */
380 uint32_t getDeleted() const 517 uint32_t getDeleted() const
381 { 518 {
382 return nDeleted; 519 return core->nDeleted;
383 } 520 }
384 521
522 struct HashProxy
523 {
524 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
525 private:
526 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) :
527 hsh( h ),
528 pKey( k ),
529 nPos( nPos ),
530 hash( hash ),
531 bFilled( false )
532 {
533 }
534
535 HashProxy( MyType &h, uint32_t nPos, value *pValue ) :
536 hsh( h ),
537 nPos( nPos ),
538 pValue( pValue ),
539 bFilled( true )
540 {
541 }
542
543 MyType &hsh;
544 const key *pKey;
545 uint32_t nPos;
546 value *pValue;
547 uint32_t hash;
548 bool bFilled;
549
550 public:
551 /**
552 * Cast operator for HashProxy.
553 *@returns (value_type &) The value the HashProxy is pointing to.
554 */
555 operator value &()
556 {
557 if( bFilled == false )
558 throw HashException(
559 excodeNotFilled,
560 "No data assosiated with that key."
561 );
562 return *pValue;
563 }
564
565 /**
566 * Direct function for retrieving a value out of the HashProxy.
567 *@returns (value_type &) The value pointed to by this HashProxy.
568 */
569 value &getValue()
570 {
571 if( bFilled == false )
572 throw HashException(
573 excodeNotFilled,
574 "No data assosiated with that key."
575 );
576 return *pValue;
577 }
578
579 /**
580 * Whether this HashProxy points to something real or not.
581 */
582 bool isFilled()
583 {
584 return bFilled;
585 }
586
587 /**
588 * Erase the data pointed to by this HashProxy.
589 */
590 void erase()
591 {
592 if( bFilled )
593 {
594 hsh.core->_erase( nPos );
595 }
596 }
597
598 /**
599 * Assign data to this point in the hash table.
600 *@param nval (value_type) the data to assign.
601 */
602 value operator=( value nval )
603 {
604 if( bFilled )
605 {
606 hsh.core->va.destroy( &hsh.core->aValues[nPos] );
607 hsh.core->va.construct( &hsh.core->aValues[nPos], nval );
608 }
609 else
610 {
611 hsh.core->fill( nPos, *pKey, nval, hash );
612 }
613
614 return nval;
615 }
616
617 /**
618 * Pointer extraction operator. Access to members of data pointed to
619 * by HashProxy.
620 *@returns (value_type *)
621 */
622 value *operator->()
623 {
624 if( bFilled == false )
625 throw HashException(
626 excodeNotFilled,
627 "No data assosiated with that key."
628 );
629 return pValue;
630 }
631 };
632
385 /** 633 /**
386 * Hash table index operator 634 * Hash table index operator
387 *@param k (key_type) Key of data to be retrieved. 635 *@param k (key_type) Key of data to be retrieved.
388 *@returns (HashProxy) Proxy pointing to the data. 636 *@returns (HashProxy) Proxy pointing to the data.
389 */ 637 */
390 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( const key &k ) 638 HashProxy operator[]( const key &k )
391 { 639 {
640 _hardCopy();
641
392 uint32_t hash = __calcHashCode( k ); 642 uint32_t hash = __calcHashCode( k );
393 bool bFill; 643 bool bFill;
394 uint32_t nPos = probe( hash, k, bFill ); 644 uint32_t nPos = core->probe( hash, k, bFill );
395 645
396 if( bFill ) 646 if( bFill )
397 { 647 {
398 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] ); 648 return HashProxy( *this, nPos, &core->aValues[nPos] );
399 } 649 }
400 else 650 else
401 { 651 {
402 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash ); 652 return HashProxy( *this, &k, nPos, hash );
403 } 653 }
404 } 654 }
405 655
@@ -408,39 +658,28 @@ namespace Bu
408 *@param k (key_type) Key to list the value under. 658 *@param k (key_type) Key to list the value under.
409 *@param v (value_type) Value to store in the hash table. 659 *@param v (value_type) Value to store in the hash table.
410 */ 660 */
411 virtual void insert( const key &k, const value &v ) 661 void insert( const key &k, const value &v )
412 { 662 {
413 uint32_t hash = __calcHashCode( k ); 663 _hardCopy();
414 bool bFill;
415 uint32_t nPos = probe( hash, k, bFill );
416 664
417 if( bFill ) 665 core->insert( k, v );
418 {
419 va.destroy( &aValues[nPos] );
420 va.construct( &aValues[nPos], v );
421 onUpdate();
422 }
423 else
424 {
425 fill( nPos, k, v, hash );
426 onInsert();
427 }
428 } 666 }
429 667
430 /** 668 /**
431 * Remove a value from the hash table. 669 * Remove a value from the hash table.
432 *@param k (key_type) The data under this key will be erased. 670 *@param k (key_type) The data under this key will be erased.
433 */ 671 */
434 virtual void erase( const key &k ) 672 void erase( const key &k )
435 { 673 {
674 _hardCopy();
675
436 uint32_t hash = __calcHashCode( k ); 676 uint32_t hash = __calcHashCode( k );
437 bool bFill; 677 bool bFill;
438 uint32_t nPos = probe( hash, k, bFill ); 678 uint32_t nPos = core->probe( hash, k, bFill );
439 679
440 if( bFill ) 680 if( bFill )
441 { 681 {
442 _erase( nPos ); 682 core->_erase( nPos );
443 onDelete();
444 } 683 }
445 } 684 }
446 685
@@ -450,14 +689,16 @@ namespace Bu
450 * Remove a value from the hash pointed to from an iterator. 689 * Remove a value from the hash pointed to from an iterator.
451 *@param i (iterator &) The data to be erased. 690 *@param i (iterator &) The data to be erased.
452 */ 691 */
453 virtual void erase( struct iterator &i ) 692 void erase( struct iterator &i )
454 { 693 {
455 if( this != i.hsh ) 694 if( this != i.hsh )
456 throw HashException("This iterator didn't come from this Hash."); 695 throw HashException("This iterator didn't come from this Hash.");
457 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) 696
697 _hardCopy();
698
699 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) )
458 { 700 {
459 _erase( i.nPos ); 701 core->_erase( i.nPos );
460 onDelete();
461 } 702 }
462 } 703 }
463 704
@@ -466,17 +707,7 @@ namespace Bu
466 */ 707 */
467 virtual void clear() 708 virtual void clear()
468 { 709 {
469 for( uint32_t j = 0; j < nCapacity; j++ ) 710 _resetCore();
470 {
471 if( isFilled( j ) )
472 if( !isDeleted( j ) )
473 {
474 _erase( j );
475 onDelete();
476 }
477 }
478
479 clearBits();
480 } 711 }
481 712
482 /** 713 /**
@@ -484,15 +715,17 @@ namespace Bu
484 *@param k (key_type) Key pointing to the data to be retrieved. 715 *@param k (key_type) Key pointing to the data to be retrieved.
485 *@returns (value_type &) The data pointed to by (k). 716 *@returns (value_type &) The data pointed to by (k).
486 */ 717 */
487 virtual value &get( const key &k ) 718 value &get( const key &k )
488 { 719 {
720 _hardCopy();
721
489 uint32_t hash = __calcHashCode( k ); 722 uint32_t hash = __calcHashCode( k );
490 bool bFill; 723 bool bFill;
491 uint32_t nPos = probe( hash, k, bFill, false ); 724 uint32_t nPos = core->probe( hash, k, bFill, false );
492 725
493 if( bFill ) 726 if( bFill )
494 { 727 {
495 return aValues[nPos]; 728 return core->aValues[nPos];
496 } 729 }
497 else 730 else
498 { 731 {
@@ -509,15 +742,15 @@ namespace Bu
509 *@returns (const value_type &) A const version of the data pointed 742 *@returns (const value_type &) A const version of the data pointed
510 * to by (k). 743 * to by (k).
511 */ 744 */
512 virtual const value &get( const key &k ) const 745 const value &get( const key &k ) const
513 { 746 {
514 uint32_t hash = __calcHashCode( k ); 747 uint32_t hash = __calcHashCode( k );
515 bool bFill; 748 bool bFill;
516 uint32_t nPos = probe( hash, k, bFill ); 749 uint32_t nPos = core->probe( hash, k, bFill );
517 750
518 if( bFill ) 751 if( bFill )
519 { 752 {
520 return aValues[nPos]; 753 return core->aValues[nPos];
521 } 754 }
522 else 755 else
523 { 756 {
@@ -533,18 +766,10 @@ namespace Bu
533 *@param k (key_type) The key to check. 766 *@param k (key_type) The key to check.
534 *@returns (bool) Whether there was an item in the hash under key (k). 767 *@returns (bool) Whether there was an item in the hash under key (k).
535 */ 768 */
536 virtual bool has( const key &k ) 769 bool has( const key &k ) const
537 { 770 {
538 bool bFill; 771 bool bFill;
539 probe( __calcHashCode( k ), k, bFill, false ); 772 core->probe( __calcHashCode( k ), k, bFill );
540
541 return bFill;
542 }
543
544 virtual bool has( const key &k ) const
545 {
546 bool bFill;
547 probe( __calcHashCode( k ), k, bFill );
548 773
549 return bFill; 774 return bFill;
550 } 775 }
@@ -561,7 +786,7 @@ namespace Bu
561 nPos( 0 ), 786 nPos( 0 ),
562 bFinished( false ) 787 bFinished( false )
563 { 788 {
564 nPos = hsh->getFirstPos( bFinished ); 789 nPos = hsh->core->getFirstPos( bFinished );
565 } 790 }
566 791
567 iterator( MyType *hsh, bool bDone ) : 792 iterator( MyType *hsh, bool bDone ) :
@@ -590,11 +815,6 @@ namespace Bu
590 { 815 {
591 } 816 }
592 817
593 DEPRECATED bool isActive() const
594 {
595 return !bFinished;
596 }
597
598 bool isValid() const 818 bool isValid() const
599 { 819 {
600 return !bFinished; 820 return !bFinished;
@@ -611,7 +831,7 @@ namespace Bu
611 iterator operator++( int ) 831 iterator operator++( int )
612 { 832 {
613 if( bFinished == false ) 833 if( bFinished == false )
614 nPos = hsh->getNextPos( nPos, bFinished ); 834 nPos = hsh->core->getNextPos( nPos, bFinished );
615 835
616 return *this; 836 return *this;
617 } 837 }
@@ -622,7 +842,7 @@ namespace Bu
622 iterator operator++() 842 iterator operator++()
623 { 843 {
624 if( bFinished == false ) 844 if( bFinished == false )
625 nPos = hsh->getNextPos( nPos, bFinished ); 845 nPos = hsh->core->getNextPos( nPos, bFinished );
626 846
627 return *this; 847 return *this;
628 } 848 }
@@ -671,21 +891,22 @@ namespace Bu
671 */ 891 */
672 value &operator *() 892 value &operator *()
673 { 893 {
674 return hsh->getValueAtPos( nPos ); 894 hsh->_hardCopy();
895 return hsh->core->getValueAtPos( nPos );
675 } 896 }
676 897
677 const value &operator *() const 898 const value &operator *() const
678 { 899 {
679 return hsh->getValueAtPos( nPos ); 900 return hsh->core->getValueAtPos( nPos );
680 } 901 }
681 902
682 /** 903 /**
683 * Get the key behind this iterator. 904 * Get the key behind this iterator.
684 *@returns (key_type &) The key behind this iterator. 905 *@returns (key_type &) The key behind this iterator.
685 */ 906 */
686 key &getKey() 907 const key &getKey() const
687 { 908 {
688 return hsh->getKeyAtPos( nPos ); 909 return hsh->core->getKeyAtPos( nPos );
689 } 910 }
690 911
691 /** 912 /**
@@ -694,7 +915,17 @@ namespace Bu
694 */ 915 */
695 value &getValue() 916 value &getValue()
696 { 917 {
697 return hsh->getValueAtPos( nPos ); 918 hsh->_hardCopy();
919 return hsh->core->getValueAtPos( nPos );
920 }
921
922 /**
923 * Get the value behind this iterator.
924 *@returns (value_type &) The value behind this iterator.
925 */
926 const value &getValue() const
927 {
928 return hsh->core->getValueAtPos( nPos );
698 } 929 }
699 } iterator; 930 } iterator;
700 931
@@ -710,7 +941,7 @@ namespace Bu
710 nPos( 0 ), 941 nPos( 0 ),
711 bFinished( false ) 942 bFinished( false )
712 { 943 {
713 nPos = hsh->getFirstPos( bFinished ); 944 nPos = hsh->core->getFirstPos( bFinished );
714 } 945 }
715 946
716 const_iterator( const MyType *hsh, bool bDone ) : 947 const_iterator( const MyType *hsh, bool bDone ) :
@@ -762,7 +993,7 @@ namespace Bu
762 const_iterator operator++( int ) 993 const_iterator operator++( int )
763 { 994 {
764 if( bFinished == false ) 995 if( bFinished == false )
765 nPos = hsh->getNextPos( nPos, bFinished ); 996 nPos = hsh->core->getNextPos( nPos, bFinished );
766 997
767 return *this; 998 return *this;
768 } 999 }
@@ -773,7 +1004,7 @@ namespace Bu
773 const_iterator operator++() 1004 const_iterator operator++()
774 { 1005 {
775 if( bFinished == false ) 1006 if( bFinished == false )
776 nPos = hsh->getNextPos( nPos, bFinished ); 1007 nPos = hsh->core->getNextPos( nPos, bFinished );
777 1008
778 return *this; 1009 return *this;
779 } 1010 }
@@ -822,7 +1053,7 @@ namespace Bu
822 */ 1053 */
823 const value &operator *() const 1054 const value &operator *() const
824 { 1055 {
825 return hsh->getValueAtPos( nPos ); 1056 return hsh->core->getValueAtPos( nPos );
826 } 1057 }
827 1058
828 /** 1059 /**
@@ -831,7 +1062,7 @@ namespace Bu
831 */ 1062 */
832 const key &getKey() const 1063 const key &getKey() const
833 { 1064 {
834 return hsh->getKeyAtPos( nPos ); 1065 return hsh->core->getKeyAtPos( nPos );
835 } 1066 }
836 1067
837 /** 1068 /**
@@ -840,7 +1071,7 @@ namespace Bu
840 */ 1071 */
841 const value &getValue() const 1072 const value &getValue() const
842 { 1073 {
843 return hsh->getValueAtPos( nPos ); 1074 return hsh->core->getValueAtPos( nPos );
844 } 1075 }
845 } const_iterator; 1076 } const_iterator;
846 1077
@@ -883,13 +1114,13 @@ namespace Bu
883 { 1114 {
884 Bu::List<key> lKeys; 1115 Bu::List<key> lKeys;
885 1116
886 for( uint32_t j = 0; j < nCapacity; j++ ) 1117 for( uint32_t j = 0; j < core->nCapacity; j++ )
887 { 1118 {
888 if( isFilled( j ) ) 1119 if( core->isFilled( j ) )
889 { 1120 {
890 if( !isDeleted( j ) ) 1121 if( !core->isDeleted( j ) )
891 { 1122 {
892 lKeys.append( aKeys[j] ); 1123 lKeys.append( core->aKeys[j] );
893 } 1124 }
894 } 1125 }
895 } 1126 }
@@ -901,13 +1132,13 @@ namespace Bu
901 { 1132 {
902 Bu::List<value> lValues; 1133 Bu::List<value> lValues;
903 1134
904 for( uint32_t j = 0; j < nCapacity; j++ ) 1135 for( uint32_t j = 0; j < core->nCapacity; j++ )
905 { 1136 {
906 if( isFilled( j ) ) 1137 if( core->isFilled( j ) )
907 { 1138 {
908 if( !isDeleted( j ) ) 1139 if( !core->isDeleted( j ) )
909 { 1140 {
910 lValues.append( aValues[j] ); 1141 lValues.append( core->aValues[j] );
911 } 1142 }
912 } 1143 }
913 } 1144 }
@@ -916,243 +1147,32 @@ namespace Bu
916 } 1147 }
917 1148
918 protected: 1149 protected:
919 virtual void onInsert() {} 1150 virtual Core *_copyCore( Core *src )
920 virtual void onUpdate() {}
921 virtual void onDelete() {}
922 virtual void onReHash() {}
923
924 virtual void clearBits()
925 {
926 for( uint32_t j = 0; j < nKeysSize; j++ )
927 {
928 bFilled[j] = bDeleted[j] = 0;
929 }
930 }
931
932 virtual void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
933 {
934 bFilled[loc/32] |= (1<<(loc%32));
935 va.construct( &aValues[loc], v );
936 ka.construct( &aKeys[loc], k );
937 aHashCodes[loc] = hash;
938 nFilled++;
939 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
940 // nFilled, nDeleted, nCapacity );
941 }
942
943 virtual void _erase( uint32_t loc )
944 {
945 bDeleted[loc/32] |= (1<<(loc%32));
946 va.destroy( &aValues[loc] );
947 ka.destroy( &aKeys[loc] );
948 nDeleted++;
949 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
950 // nFilled, nDeleted, nCapacity );
951 }
952
953 virtual key &getKeyAtPos( uint32_t nPos )
954 {
955 return aKeys[nPos];
956 }
957
958 virtual const key &getKeyAtPos( uint32_t nPos ) const
959 {
960 return aKeys[nPos];
961 }
962
963 virtual value &getValueAtPos( uint32_t nPos )
964 {
965 return aValues[nPos];
966 }
967
968 virtual const value &getValueAtPos( uint32_t nPos ) const
969 {
970 return aValues[nPos];
971 }
972
973 virtual uint32_t getFirstPos( bool &bFinished ) const
974 {
975 for( uint32_t j = 0; j < nCapacity; j++ )
976 {
977 if( isFilled( j ) )
978 if( !isDeleted( j ) )
979 return j;
980 }
981
982 bFinished = true;
983 return 0;
984 }
985
986 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
987 {
988 for( uint32_t j = nPos+1; j < nCapacity; j++ )
989 {
990 if( isFilled( j ) )
991 if( !isDeleted( j ) )
992 return j;
993 }
994
995 bFinished = true;
996 return 0;
997 }
998
999 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
1000 {
1001 uint32_t nCur = hash%nCapacity;
1002
1003 // First we scan to see if the key is already there, abort if we
1004 // run out of probing room, or we find a non-filled entry
1005 int8_t j;
1006 for( j = 0;
1007 isFilled( nCur ) && j < 32;
1008 nCur = (nCur + (1<<j))%nCapacity, j++
1009 )
1010 {
1011 // Is this the same hash code we were looking for?
1012 if( hash == aHashCodes[nCur] )
1013 {
1014 // Skip over deleted entries. Deleted entries are also filled,
1015 // so we only have to do this check here.
1016 if( isDeleted( nCur ) )
1017 continue;
1018
1019 // Is it really the same key? (for safety)
1020 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1021 {
1022 bFill = true;
1023 return nCur;
1024 }
1025 }
1026 }
1027
1028 // This is our insurance, if the table is full, then go ahead and
1029 // rehash, then try again.
1030 if( (isFilled( nCur ) || j == 32) && rehash == true )
1031 {
1032 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
1033
1034 // This is potentially dangerous, and could cause an infinite loop.
1035 // Be careful writing probe, eh?
1036 return probe( hash, k, bFill );
1037 }
1038
1039 bFill = false;
1040 return nCur;
1041 }
1042
1043 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
1044 {
1045 uint32_t nCur = hash%nCapacity;
1046
1047 // First we scan to see if the key is already there, abort if we
1048 // run out of probing room, or we find a non-filled entry
1049 for( int8_t j = 0;
1050 isFilled( nCur ) && j < 32;
1051 nCur = (nCur + (1<<j))%nCapacity, j++
1052 )
1053 {
1054 // Is this the same hash code we were looking for?
1055 if( hash == aHashCodes[nCur] )
1056 {
1057 // Skip over deleted entries. Deleted entries are also filled,
1058 // so we only have to do this check here.
1059 if( isDeleted( nCur ) )
1060 continue;
1061
1062 // Is it really the same key? (for safety)
1063 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1064 {
1065 bFill = true;
1066 return nCur;
1067 }
1068 }
1069 }
1070
1071 bFill = false;
1072 return nCur;
1073 }
1074
1075 void reHash( uint32_t nNewSize )
1076 { 1151 {
1077 //printf("---REHASH---"); 1152 Core *pRet = _allocateCore();
1078 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
1079 // nFilled, nDeleted, nCapacity );
1080
1081 // Save all the old data
1082 uint32_t nOldCapacity = nCapacity;
1083 uint32_t *bOldFilled = bFilled;
1084 uint32_t *aOldHashCodes = aHashCodes;
1085 uint32_t nOldKeysSize = nKeysSize;
1086 uint32_t *bOldDeleted = bDeleted;
1087 value *aOldValues = aValues;
1088 key *aOldKeys = aKeys;
1089
1090 // Calculate new sizes
1091 nCapacity = nNewSize;
1092 nKeysSize = bitsToBytes( nCapacity );
1093
1094 // Allocate new memory + prep
1095 bFilled = ca.allocate( nKeysSize );
1096 bDeleted = ca.allocate( nKeysSize );
1097 clearBits();
1098 1153
1099 aHashCodes = ca.allocate( nCapacity ); 1154 pRet->nFilled = 0;
1100 aKeys = ka.allocate( nCapacity ); 1155 pRet->nDeleted = 0;
1101 aValues = va.allocate( nCapacity ); 1156 pRet->nCapacity = src->nCapacity;
1157 pRet->nKeysSize = bitsToBytes( pRet->nCapacity );
1158 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize );
1159 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize );
1160 pRet->clearBits();
1102 1161
1103 nDeleted = nFilled = 0; 1162 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity );
1163 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity );
1164 pRet->aValues = pRet->va.allocate( pRet->nCapacity );
1104 1165
1105 // Re-insert all of the old data (except deleted items) 1166 for( uint32_t j = 0; j < src->nCapacity; j++ )
1106 for( uint32_t j = 0; j < nOldCapacity; j++ )
1107 { 1167 {
1108 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 1168 if( src->isFilled( j ) && !src->isDeleted( j ) )
1109 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1110 { 1169 {
1111 insert( aOldKeys[j], aOldValues[j] ); 1170 pRet->insert( src->aKeys[j], src->aValues[j] );
1112 } 1171 }
1113 } 1172 }
1114 1173
1115 // Delete all of the old data 1174 return pRet;
1116 for( uint32_t j = 0; j < nOldCapacity; j++ )
1117 {
1118 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
1119 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1120 {
1121 va.destroy( &aOldValues[j] );
1122 ka.destroy( &aOldKeys[j] );
1123 }
1124 }
1125 va.deallocate( aOldValues, nOldCapacity );
1126 ka.deallocate( aOldKeys, nOldCapacity );
1127 ca.deallocate( bOldFilled, nOldKeysSize );
1128 ca.deallocate( bOldDeleted, nOldKeysSize );
1129 ca.deallocate( aOldHashCodes, nOldCapacity );
1130 }
1131
1132 virtual bool isFilled( uint32_t loc ) const
1133 {
1134 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
1135 }
1136
1137 virtual bool isDeleted( uint32_t loc ) const
1138 {
1139 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
1140 } 1175 }
1141
1142 protected:
1143 uint32_t nCapacity;
1144 uint32_t nFilled;
1145 uint32_t nDeleted;
1146 uint32_t *bFilled;
1147 uint32_t *bDeleted;
1148 uint32_t nKeysSize;
1149 key *aKeys;
1150 value *aValues;
1151 uint32_t *aHashCodes;
1152 valuealloc va;
1153 keyalloc ka;
1154 challoc ca;
1155 sizecalc szCalc;
1156 }; 1176 };
1157 1177
1158 template<typename T> uint32_t __calcHashCode( const T &k ) 1178 template<typename T> uint32_t __calcHashCode( const T &k )
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 03:20:13 +0000