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