aboutsummaryrefslogtreecommitdiff
path: root/src/stable/hash.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2020-02-04 09:01:45 -0800
committerMike Buland <eichlan@xagasoft.com>2020-02-04 09:01:45 -0800
commited5e7684b766a3914b30c5b449608542695fd3b8 (patch)
tree85ca29cecca05606ea2ce5dfadc0ab158310562d /src/stable/hash.h
parent969e708d25351ea631e3ce9afb64313851869ec5 (diff)
downloadlibbu++-ed5e7684b766a3914b30c5b449608542695fd3b8.tar.gz
libbu++-ed5e7684b766a3914b30c5b449608542695fd3b8.tar.bz2
libbu++-ed5e7684b766a3914b30c5b449608542695fd3b8.tar.xz
libbu++-ed5e7684b766a3914b30c5b449608542695fd3b8.zip
Minor Bu::Hash updates and additions.
Bu::Hash::KeyList has been added, I thought that was always there. Bu::Hash::rehash has been added. Rehashes can be triggered manually now.
Diffstat (limited to '')
-rw-r--r--src/stable/hash.h40
1 files changed, 34 insertions, 6 deletions
diff --git a/src/stable/hash.h b/src/stable/hash.h
index 7f4066e..0c5bd9e 100644
--- a/src/stable/hash.h
+++ b/src/stable/hash.h
@@ -211,7 +211,7 @@ namespace Bu
211 return 0; 211 return 0;
212 } 212 }
213 213
214 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true ) 214 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool bRehash=true )
215 { 215 {
216 init(); 216 init();
217 217
@@ -244,9 +244,9 @@ namespace Bu
244 244
245 // This is our insurance, if the table is full, then go ahead and 245 // This is our insurance, if the table is full, then go ahead and
246 // rehash, then try again. 246 // rehash, then try again.
247 if( (isFilled( nCur ) || j == 32) && rehash == true ) 247 if( (isFilled( nCur ) || j == 32) && bRehash == true )
248 { 248 {
249 reHash( szCalc( nCapacity, nFilled, nDeleted ) ); 249 rehash( szCalc( nCapacity, nFilled, nDeleted ) );
250 250
251 // This is potentially dangerous, and could cause an infinite loop. 251 // This is potentially dangerous, and could cause an infinite loop.
252 // Be careful writing probe, eh? 252 // Be careful writing probe, eh?
@@ -309,7 +309,7 @@ namespace Bu
309 } 309 }
310 } 310 }
311 311
312 void reHash( uint32_t nNewSize ) 312 void rehash( uint32_t nNewSize )
313 { 313 {
314 //printf("--rehash: %d --> %d (%d, %d)\n", nCapacity, nNewSize, nFilled, nDeleted ); 314 //printf("--rehash: %d --> %d (%d, %d)\n", nCapacity, nNewSize, nFilled, nDeleted );
315 //printf("---REHASH---"); 315 //printf("---REHASH---");
@@ -386,11 +386,13 @@ namespace Bu
386 for( uint32_t j = 0; j < nCapacity; j++ ) 386 for( uint32_t j = 0; j < nCapacity; j++ )
387 { 387 {
388 if( isFilled( j ) ) 388 if( isFilled( j ) )
389 {
389 if( !isDeleted( j ) ) 390 if( !isDeleted( j ) )
390 { 391 {
391 va.destroy( &aValues[j] ); 392 va.destroy( &aValues[j] );
392 ka.destroy( &aKeys[j] ); 393 ka.destroy( &aKeys[j] );
393 } 394 }
395 }
394 } 396 }
395 va.deallocate( aValues, nCapacity ); 397 va.deallocate( aValues, nCapacity );
396 ka.deallocate( aKeys, nCapacity ); 398 ka.deallocate( aKeys, nCapacity );
@@ -501,6 +503,8 @@ namespace Bu
501 { 503 {
502 } 504 }
503 505
506 typedef Bu::List<key> KeyList;
507
504 /** 508 /**
505 * Get the current hash table capacity. (Changes at re-hash) 509 * Get the current hash table capacity. (Changes at re-hash)
506 *@returns (uint32_t) The current capacity. 510 *@returns (uint32_t) The current capacity.
@@ -1135,9 +1139,9 @@ namespace Bu
1135 * Get a list of all the keys in the hash table. 1139 * Get a list of all the keys in the hash table.
1136 *@returns (std::list<key_type>) The list of keys in the hash table. 1140 *@returns (std::list<key_type>) The list of keys in the hash table.
1137 */ 1141 */
1138 Bu::List<key> getKeys() const 1142 KeyList getKeys() const
1139 { 1143 {
1140 Bu::List<key> lKeys; 1144 KeyList lKeys;
1141 1145
1142 for( uint32_t j = 0; j < core->nCapacity; j++ ) 1146 for( uint32_t j = 0; j < core->nCapacity; j++ )
1143 { 1147 {
@@ -1171,6 +1175,30 @@ namespace Bu
1171 return lValues; 1175 return lValues;
1172 } 1176 }
1173 1177
1178 /**
1179 * This can be a very expensive operation, but when there are a decent
1180 * number of deleted entries it can be good to be able to clean them
1181 * up on your own terms.
1182 *
1183 * This will always allocate a new table and move all non-deleted items
1184 * over to it. The size of the new table depends on which resizing
1185 * calculator is selected. The default resize calculator will shrink
1186 * the table if it's mostly deleted/empty space.
1187 *
1188 * This will be done by the system whenever it deems necesarry, but
1189 * only during probing operations. That means that an insert could
1190 * trigger a rehash, which could be very expensive. If you know, for
1191 * example, that you'll be deleting most of the entries once a night
1192 * during a low-usage time, that would probably be a good time to
1193 * manually trigger a rehash and save the extra time on the next insert
1194 * after the cleanup. This is partucularly true for systems like
1195 * caches that need to be periodically cleaned up.
1196 */
1197 void rehash()
1198 {
1199 core->rehash( core->szCalc( core->nCapacity, core->nFilled, core->nDeleted ) );
1200 }
1201
1174 bool operator==( const MyType &rhs ) const 1202 bool operator==( const MyType &rhs ) const
1175 { 1203 {
1176 if( this == &rhs ) 1204 if( this == &rhs )