aboutsummaryrefslogtreecommitdiff
path: root/src/hash.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2011-04-06 14:33:10 +0000
committerMike Buland <eichlan@xagasoft.com>2011-04-06 14:33:10 +0000
commitf7888fb3078a781ecc947ded0b064d1a901d5887 (patch)
tree8a25cd3e15ea2c301a98ce1711e5b4a8ba6576e0 /src/hash.h
parent9f440fb38b36f2d602710695dd53ad9c80e84c2c (diff)
downloadlibbu++-f7888fb3078a781ecc947ded0b064d1a901d5887.tar.gz
libbu++-f7888fb3078a781ecc947ded0b064d1a901d5887.tar.bz2
libbu++-f7888fb3078a781ecc947ded0b064d1a901d5887.tar.xz
libbu++-f7888fb3078a781ecc947ded0b064d1a901d5887.zip
Tweaked the hash table resizer, it now is more careful about increasing the
size of the table when it can reclaim empty space from deletes, and it allows the table to shrink if little enough space is being used.
Diffstat (limited to '')
-rw-r--r--src/hash.h16
1 files changed, 14 insertions, 2 deletions
diff --git a/src/hash.h b/src/hash.h
index 26b16c7..5c7bc78 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -42,10 +42,22 @@ namespace Bu
42 */ 42 */
43 struct __calcNextTSize_fast 43 struct __calcNextTSize_fast
44 { 44 {
45 uint32_t operator()( uint32_t nCapacity, uint32_t, uint32_t nDeleted ) const 45 uint32_t operator()( uint32_t nCapacity, uint32_t nFilled,
46 uint32_t nDeleted ) const
46 { 47 {
47 if( nDeleted >= nCapacity/2 ) 48 // This frist case will allow hashtables that are mostly deleted
49 // items to reset to small allocations
50 if( nFilled-nDeleted <= nCapacity/4 )
51 {
52 nCapacity = 11;
53 while( nCapacity < nFilled*5/4 )
54 nCapacity = nCapacity*2+1;
55 return nCapacity;
56 }
57 // This will hopefully prevent hash tables from growing needlessly
58 if( nFilled-nDeleted <= nCapacity/2 )
48 return nCapacity; 59 return nCapacity;
60 // Otherwise, just increase the capacity
49 return nCapacity*2+1; 61 return nCapacity*2+1;
50 } 62 }
51 }; 63 };