aboutsummaryrefslogtreecommitdiff
path: root/src/hash.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2010-10-14 23:26:25 +0000
committerMike Buland <eichlan@xagasoft.com>2010-10-14 23:26:25 +0000
commit867dae89929a11a421ec21af71d494ad0ecc1963 (patch)
tree85d4330d5cdc0567194f1bfb2f9b1bda4e95b444 /src/hash.h
parent13fa07280dd9ed2c62ad2be0848f88b0d85fe322 (diff)
downloadlibbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.gz
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.bz2
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.xz
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.zip
SharedCore has more features now, which is cool, including a test to see if
another object of the parent type has the same core, and another to clone the parent object. That one is pretty cool, it means you can now get a real copy when you want to, great for multi-threaded stuff. Also, two more classes are now SharedCore: Hash and Heap!
Diffstat (limited to '')
-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 )