GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/smallhash.h
Date: 2026-09-20 02:39:58
Exec Total Coverage
Lines: 259 263 98.5%
Branches: 86 110 78.2%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 */
4
5 #ifndef CVMFS_SMALLHASH_H_
6 #define CVMFS_SMALLHASH_H_
7
8 #include "duplex_testing.h"
9 #include <inttypes.h>
10 #include <pthread.h>
11 #include <stdint.h>
12
13 #include <algorithm>
14 #include <cassert>
15 #include <cstdlib>
16 #include <new>
17
18 #include "util/atomic.h"
19 #include "util/murmur.hxx"
20 #include "util/prng.h"
21 #include "util/smalloc.h"
22
23 /**
24 * Hash table with linear probing as collision resolution. Works only for
25 * a fixed (maximum) number of elements, i.e. no resizing. Load factor fixed
26 * to 0.7.
27 */
28 template<class Key, class Value, class Derived>
29 class SmallHashBase {
30 FRIEND_TEST(T_Smallhash, InsertAndCopyMd5Slow);
31
32 public:
33 static const double kLoadFactor; // mainly useless for the dynamic version
34 static const double kThresholdGrow; // only used for resizable version
35 static const double kThresholdShrink; // only used for resizable version
36
37 256345 SmallHashBase() {
38 256345 keys_ = NULL;
39 256345 values_ = NULL;
40 256345 hasher_ = NULL;
41 256345 bytes_allocated_ = 0;
42 256345 num_collisions_ = 0;
43 256345 max_collisions_ = 0;
44
45 // Properly initialized by Init()
46 256345 capacity_ = 0;
47 256345 initial_capacity_ = 0;
48 256345 size_ = 0;
49 256345 }
50
51 256207 ~SmallHashBase() { DeallocMemory(keys_, values_, capacity_); }
52
53 256273 void Init(uint32_t expected_size, Key empty,
54 uint32_t (*hasher)(const Key &key)) {
55 256273 hasher_ = hasher;
56 256273 empty_key_ = empty;
57 256273 capacity_ = static_cast<uint32_t>(static_cast<double>(expected_size)
58 256273 / kLoadFactor);
59 256273 initial_capacity_ = capacity_;
60 256273 static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size
61 256273 AllocMemory();
62 256273 this->DoClear(false);
63 256273 }
64
65 128373810 bool Lookup(const Key &key, Value *value) const {
66 uint32_t bucket;
67 uint32_t collisions;
68
1/2
✓ Branch 1 taken 128276242 times.
✗ Branch 2 not taken.
 128373810 const bool found = DoLookup(key, &bucket, &collisions);
69
2/2
✓ Branch 0 taken 104489083 times.
✓ Branch 1 taken 23787159 times.
 128419212 if (found)
70
1/2
✓ Branch 1 taken 90354 times.
✗ Branch 2 not taken.
 104536095 *value = values_[bucket];
71 128419212 return found;
72 }
73
74 /**
75 * Returns both the key and the value. That is useful if Key's equality
76 * operator implements an equivalence relation on Key. In this case, LookupEx
77 * returns the key representing the equivalence class that has been used
78 * during Insert().
79 * Used to return a glue::InodeEx element when looking for an inode.
80 */
81 296 bool LookupEx(Key *key, Value *value) const {
82 296 uint32_t bucket = ScaleHash(*key);
83
2/2
✓ Branch 1 taken 98 times.
✓ Branch 2 taken 50 times.
 296 while (!(keys_[bucket] == empty_key_)) {
84
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 196 if (keys_[bucket] == *key) {
85 196 *key = keys_[bucket];
86 196 *value = values_[bucket];
87 196 return true;
88 }
89 ✗ bucket = (bucket + 1) % capacity_;
90 }
91 100 return false;
92 }
93
94 46049661 bool Contains(const Key &key) const {
95 uint32_t bucket;
96 uint32_t collisions;
97
1/2
✓ Branch 1 taken 46049121 times.
✗ Branch 2 not taken.
 46049661 const bool found = DoLookup(key, &bucket, &collisions);
98 46049661 return found;
99 }
100
101 2133070306 void Insert(const Key &key, const Value &value) {
102 2133070306 static_cast<Derived *>(this)->Grow(); // No-op if fixed-size
103 2124890146 const bool overwritten = DoInsert(key, value, true);
104 2122919233 size_ += !overwritten; // size + 1 if the key was not yet in the map
105 2122919233 }
106
107 123414574 bool Erase(const Key &key) {
108 uint32_t bucket;
109 uint32_t collisions;
110
1/2
✓ Branch 1 taken 121939454 times.
✗ Branch 2 not taken.
 123414574 const bool found = DoLookup(key, &bucket, &collisions);
111
1/2
✓ Branch 0 taken 121959406 times.
✗ Branch 1 not taken.
 121945212 if (found) {
112 121964836 keys_[bucket] = empty_key_;
113 121964836 size_--;
114 121964836 bucket = (bucket + 1) % capacity_;
115
3/3
✓ Branch 0 taken 215082178 times.
✓ Branch 1 taken 119787522 times.
✓ Branch 2 taken 374455 times.
 335249659 while (!(keys_[bucket] == empty_key_)) {
116 215262375 Key rehash = keys_[bucket];
117 215262375 keys_[bucket] = empty_key_;
118
1/2
✓ Branch 1 taken 213284749 times.
✗ Branch 2 not taken.
 215262375 DoInsert(rehash, values_[bucket], false);
119 213284823 bucket = (bucket + 1) % capacity_;
120 }
121
1/2
✓ Branch 1 taken 121184152 times.
✗ Branch 2 not taken.
 119987284 static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size
122 }
123 121215407 return found;
124 }
125
126 2399 void Clear() { DoClear(true); }
127
128 7942 uint64_t bytes_allocated() const { return bytes_allocated_; }
129 2094 static double GetEntrySize() {
130 4188 const double unit = sizeof(Key) + sizeof(Value);
131 4188 return unit / kLoadFactor;
132 }
133
134 void GetCollisionStats(uint64_t *num_collisions,
135 uint32_t *max_collisions) const {
136 *num_collisions = num_collisions_;
137 *max_collisions = max_collisions_;
138 }
139
140 // Careful with the direct access TODO: iterator
141 uint32_t capacity() const { return capacity_; }
142 252826 Key empty_key() const { return empty_key_; }
143 561806 Key *keys() const { return keys_; }
144 460 Value *values() const { return values_; }
145
146 // Only needed by compat
147 ✗ void SetHasher(uint32_t (*hasher)(const Key &key)) { hasher_ = hasher; }
148
149 protected:
150 3010589011 uint32_t ScaleHash(const Key &key) const {
151 3010589011 const double bucket = (static_cast<double>(hasher_(key))
152 2985900813 * static_cast<double>(capacity_)
153 / static_cast<double>(static_cast<uint32_t>(-1)));
154 2985900813 return static_cast<uint32_t>(bucket) % capacity_;
155 }
156
157 418188 void AllocMemory() {
158 418188 keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key)));
159 418332 values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value)));
160
2/2
✓ Branch 0 taken 2139477451 times.
✓ Branch 1 taken 211547 times.
 4267434476 for (uint32_t i = 0; i < capacity_; ++i) {
161 4267016144 /*keys_[i] =*/new (keys_ + i) Key();
162 }
163
2/2
✓ Branch 0 taken 2142695887 times.
✓ Branch 1 taken 135047 times.
 4273718348 for (uint32_t i = 0; i < capacity_; ++i) {
164 4273453016 /*values_[i] =*/new (values_ + i) Value();
165 }
166 265332 bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_;
167 265332 }
168
169 418122 void DeallocMemory(Key *k, Value *v, uint32_t c) {
170
2/2
✓ Branch 0 taken 2148036757 times.
✓ Branch 1 taken 211441 times.
 4284555608 for (uint32_t i = 0; i < c; ++i) {
171 4284137486 k[i].~Key();
172 }
173
2/2
✓ Branch 0 taken 2147496901 times.
✓ Branch 1 taken 211441 times.
 4283475896 for (uint32_t i = 0; i < c; ++i) {
174 4283057774 v[i].~Value();
175 }
176
1/2
✓ Branch 0 taken 211477 times.
✗ Branch 1 not taken.
 418122 if (k)
177 418194 smunmap(k);
178
1/2
✓ Branch 0 taken 211477 times.
✗ Branch 1 not taken.
 418122 if (v)
179 418194 smunmap(v);
180 418122 k = NULL;
181 418122 v = NULL;
182 418122 }
183
184 // Returns true iff the key is overwritten
185 2509679237 bool DoInsert(const Key &key, const Value &value,
186 const bool count_collisions) {
187 uint32_t bucket;
188 uint32_t collisions;
189
1/2
✓ Branch 1 taken 1298002590 times.
✗ Branch 2 not taken.
 2509679237 const bool overwritten = DoLookup(key, &bucket, &collisions);
190
2/2
✓ Branch 0 taken 1084828455 times.
✓ Branch 1 taken 213174135 times.
 2507577641 if (count_collisions) {
191 2123905454 num_collisions_ += collisions;
192 2123905454 max_collisions_ = std::max(collisions, max_collisions_);
193 }
194 2506572736 keys_[bucket] = key;
195
1/2
✓ Branch 1 taken 42710484 times.
✗ Branch 2 not taken.
 2506572736 values_[bucket] = value;
196 2506572736 return overwritten;
197 }
198
199 3022367026 bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const {
200 3022367026 *bucket = ScaleHash(key);
201 2983578427 *collisions = 0;
202
3/3
✓ Branch 0 taken 23533296978 times.
✓ Branch 1 taken 1274069917 times.
✓ Branch 2 taken 267453082 times.
 27872686871 while (!(keys_[*bucket] == empty_key_)) {
203
3/3
✓ Branch 0 taken 245798387 times.
✓ Branch 1 taken 23337041395 times.
✓ Branch 2 taken 211522239 times.
 25401778379 if (keys_[*bucket] == key)
204 512669935 return true;
205 24889108444 *bucket = (*bucket + 1) % capacity_;
206 24889108444 (*collisions)++;
207 }
208 2470908492 return false;
209 }
210
211 418416 void DoClear(const bool reset_capacity) {
212
2/2
✓ Branch 0 taken 2399 times.
✓ Branch 1 taken 209232 times.
 418416 if (reset_capacity)
213 3983 static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size
214
2/2
✓ Branch 0 taken 2141542231 times.
✓ Branch 1 taken 211631 times.
 4271449460 for (uint32_t i = 0; i < capacity_; ++i)
215 4271031044 keys_[i] = empty_key_;
216 418416 size_ = 0;
217 418416 }
218
219 // Methods for resizable version
220 void SetThresholds() { }
221 void Grow() { }
222 void Shrink() { }
223 void ResetCapacity() { }
224
225 // Separate key and value arrays for better locality
226 Key *keys_;
227 Value *values_;
228 uint32_t capacity_;
229 uint32_t initial_capacity_;
230 uint32_t size_;
231 uint32_t (*hasher_)(const Key &key);
232 uint64_t bytes_allocated_;
233 uint64_t num_collisions_;
234 uint32_t max_collisions_; /**< maximum collisions for a single insert */
235 Key empty_key_;
236 };
237
238
239 template<class Key, class Value>
240 class SmallHashFixed
241 : public SmallHashBase<Key, Value, SmallHashFixed<Key, Value> > {
242 friend class SmallHashBase<Key, Value, SmallHashFixed<Key, Value> >;
243
244 protected:
245 // No-ops
246 7858 void SetThresholds() { }
247 1195631 void Grow() { }
248 45449 void Shrink() { }
249 84 void ResetCapacity() { }
250 };
251
252
253 template<class Key, class Value>
254 class SmallHashDynamic
255 : public SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> > {
256 friend class SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> >;
257
258 public:
259 typedef SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> > Base;
260 static const double kThresholdGrow;
261 static const double kThresholdShrink;
262
263 248487 SmallHashDynamic() : Base() {
264 248487 num_migrates_ = 0;
265
266 // Properly set by Init
267 248487 threshold_grow_ = 0;
268 248487 threshold_shrink_ = 0;
269 248487 }
270
271 SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base() {
272 num_migrates_ = 0;
273 CopyFrom(other);
274 }
275
276 340 SmallHashDynamic<Key, Value> &operator=(
277 const SmallHashDynamic<Key, Value> &other) {
278
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 188 times.
 340 if (&other == this)
279 ✗ return *this;
280
281 340 CopyFrom(other);
282 340 return *this;
283 }
284
285 49893881 uint32_t capacity() const { return Base::capacity_; }
286 1206904110 uint32_t size() const { return Base::size_; }
287 uint32_t num_migrates() const { return num_migrates_; }
288
289 protected:
290 410330 void SetThresholds() {
291 410330 threshold_grow_ = static_cast<uint32_t>(static_cast<double>(capacity())
292 410330 * kThresholdGrow);
293 410330 threshold_shrink_ = static_cast<uint32_t>(static_cast<double>(capacity())
294 410330 * kThresholdShrink);
295 410330 }
296
297 2129546606 void Grow() {
298
2/2
✓ Branch 1 taken 54264 times.
✓ Branch 2 taken 1084870290 times.
 2129546606 if (size() > threshold_grow_)
299 108528 Migrate(capacity() * 2);
300 2125322435 }
301
302 121128575 void Shrink() {
303
2/2
✓ Branch 1 taken 24019626 times.
✓ Branch 2 taken 97077499 times.
 121128575 if (size() < threshold_shrink_) {
304 24025056 const uint32_t target_capacity = capacity() / 2;
305
2/2
✓ Branch 0 taken 24732 times.
✓ Branch 1 taken 23992712 times.
 24022874 if (target_capacity >= Base::initial_capacity_)
306 24732 Migrate(target_capacity);
307 }
308 121100409 }
309
310 3899 void ResetCapacity() {
311 3899 Base::DeallocMemory(Base::keys_, Base::values_, Base::capacity_);
312 3899 Base::capacity_ = Base::initial_capacity_;
313 3899 Base::AllocMemory();
314 3899 SetThresholds();
315 3899 }
316
317 private:
318 // Returns a random permutation of indices [0..N-1] that is allocated
319 // by smmap (Knuth's shuffle algorithm)
320 49912 uint32_t *ShuffleIndices(const uint32_t N) {
321 49912 uint32_t *shuffled = static_cast<uint32_t *>(smmap(N * sizeof(uint32_t)));
322 // Init with identity
323
2/2
✓ Branch 0 taken 405995496 times.
✓ Branch 1 taken 24956 times.
 812040904 for (unsigned i = 0; i < N; ++i)
324 811990992 shuffled[i] = i;
325 // Shuffle (no shuffling for the last element)
326
1/2
✓ Branch 0 taken 388069648 times.
✗ Branch 1 not taken.
 776029008 for (unsigned i = 0; i < N - 1; ++i) {
327 776139296 const uint32_t swap_idx = i + g_prng.Next(N - i);
328 775979096 const uint32_t tmp = shuffled[i];
329 775979096 shuffled[i] = shuffled[swap_idx];
330 775979096 shuffled[swap_idx] = tmp;
331 }
332 340 return shuffled;
333 }
334
335 157992 void Migrate(const uint32_t new_capacity) {
336 157992 Key *old_keys = Base::keys_;
337 157992 Value *old_values = Base::values_;
338 157992 const uint32_t old_capacity = capacity();
339 157992 const uint32_t old_size = size();
340
341 157992 Base::capacity_ = new_capacity;
342 157992 SetThresholds();
343 157992 Base::AllocMemory();
344 158136 Base::DoClear(false);
345
2/2
✓ Branch 0 taken 24768 times.
✓ Branch 1 taken 54300 times.
 158136 if (new_capacity < old_capacity) {
346 49536 uint32_t *shuffled_indices = ShuffleIndices(old_capacity);
347
1/2
✓ Branch 0 taken 346831524 times.
✗ Branch 1 not taken.
 693520920 for (uint32_t i = 0; i < old_capacity; ++i) {
348
2/3
✓ Branch 0 taken 87060420 times.
✓ Branch 1 taken 259771104 times.
✗ Branch 2 not taken.
 693663048 if (old_keys[shuffled_indices[i]] != Base::empty_key_) {
349 174120840 Base::Insert(old_keys[shuffled_indices[i]],
350 174120840 old_values[shuffled_indices[i]]);
351 }
352 }
353 ✗ smunmap(shuffled_indices);
354 } else {
355
2/2
✓ Branch 0 taken 651904602 times.
✓ Branch 1 taken 30036 times.
 1303869276 for (uint32_t i = 0; i < old_capacity; ++i) {
356
3/3
✓ Branch 0 taken 376808962 times.
✓ Branch 1 taken 237675737 times.
✓ Branch 2 taken 37419903 times.
 1303809204 if (old_keys[i] != Base::empty_key_)
357 978156764 Base::Insert(old_keys[i], old_values[i]);
358 }
359 }
360
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 78996 times.
 109608 assert(size() == old_size);
361
362 157992 Base::DeallocMemory(old_keys, old_values, old_capacity);
363 158136 num_migrates_++;
364 158136 }
365
366 340 void CopyFrom(const SmallHashDynamic<Key, Value> &other) {
367 340 uint32_t *shuffled_indices = ShuffleIndices(other.capacity_);
368
2/2
✓ Branch 0 taken 49548408 times.
✓ Branch 1 taken 188 times.
 49551940 for (uint32_t i = 0; i < other.capacity_; ++i) {
369
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 36001596 times.
✓ Branch 2 taken 13546812 times.
 49551600 if (other.keys_[shuffled_indices[i]] != other.empty_key_) {
370 36000000 this->Insert(other.keys_[shuffled_indices[i]],
371 36000000 other.values_[shuffled_indices[i]]);
372 }
373 }
374 340 smunmap(shuffled_indices);
375 340 }
376
377 uint32_t num_migrates_;
378 uint32_t threshold_grow_;
379 uint32_t threshold_shrink_;
380 static Prng g_prng;
381 };
382
383
384 /**
385 * Distributes the key-value pairs over $n$ dynamic hash maps with individual
386 * mutexes. Hence low mutex contention, and benefits from multiple processors.
387 */
388 template<class Key, class Value>
389 class MultiHash {
390 public:
391 360 MultiHash() {
392 360 num_hashmaps_ = 0;
393 360 hashmaps_ = NULL;
394 360 locks_ = NULL;
395 360 }
396
397 360 void Init(const uint8_t num_hashmaps, const Key &empty_key,
398 uint32_t (*hasher)(const Key &key)) {
399
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 360 times.
 360 assert(num_hashmaps > 0);
400 360 const uint8_t N = num_hashmaps;
401 360 num_hashmaps_ = N;
402
3/4
✓ Branch 2 taken 15120 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 15120 times.
✓ Branch 5 taken 360 times.
 15480 hashmaps_ = new SmallHashDynamic<Key, Value>[N]();
403 360 locks_ = static_cast<pthread_mutex_t *>(
404 360 smalloc(N * sizeof(pthread_mutex_t)));
405
2/2
✓ Branch 0 taken 15120 times.
✓ Branch 1 taken 360 times.
 15480 for (uint8_t i = 0; i < N; ++i) {
406 15120 int retval = pthread_mutex_init(&locks_[i], NULL);
407
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15120 times.
 15120 assert(retval == 0);
408 15120 hashmaps_[i].Init(128, empty_key, hasher);
409 }
410 360 }
411
412 360 ~MultiHash() {
413
2/2
✓ Branch 0 taken 15120 times.
✓ Branch 1 taken 360 times.
 15480 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
414 15120 pthread_mutex_destroy(&locks_[i]);
415 }
416 360 free(locks_);
417
3/4
✓ Branch 0 taken 360 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15120 times.
✓ Branch 3 taken 360 times.
 15480 delete[] hashmaps_;
418 360 }
419
420 36000000 bool Lookup(const Key &key, Value *value) {
421 36000000 uint8_t target = SelectHashmap(key);
422 36000000 Lock(target);
423 36000000 const bool result = hashmaps_[target].Lookup(key, value);
424 36000000 Unlock(target);
425 36000000 return result;
426 }
427
428 134314632 void Insert(const Key &key, const Value &value) {
429 134314632 uint8_t target = SelectHashmap(key);
430 130543128 Lock(target);
431 135886392 hashmaps_[target].Insert(key, value);
432 128306340 Unlock(target);
433 140049900 }
434
435 65572200 void Erase(const Key &key) {
436 65572200 uint8_t target = SelectHashmap(key);
437 62651880 Lock(target);
438 66757824 hashmaps_[target].Erase(key);
439 61209720 Unlock(target);
440 67873284 }
441
442 36 void Clear() {
443
2/2
✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 36 times.
 1548 for (uint8_t i = 0; i < num_hashmaps_; ++i)
444 1512 Lock(i);
445
2/2
✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 36 times.
 1548 for (uint8_t i = 0; i < num_hashmaps_; ++i)
446 1512 hashmaps_[i].Clear();
447
2/2
✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 36 times.
 1548 for (uint8_t i = 0; i < num_hashmaps_; ++i)
448 1512 Unlock(i);
449 36 }
450
451 360 uint8_t num_hashmaps() const { return num_hashmaps_; }
452
453 288 void GetSizes(uint32_t *sizes) {
454
2/2
✓ Branch 0 taken 12096 times.
✓ Branch 1 taken 288 times.
 12384 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
455 12096 Lock(i);
456 12096 sizes[i] = hashmaps_[i].size();
457 12096 Unlock(i);
458 }
459 288 }
460
461 void GetCollisionStats(uint64_t *num_collisions, uint32_t *max_collisions) {
462 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
463 Lock(i);
464 hashmaps_[i].GetCollisionStats(&num_collisions[i], &max_collisions[i]);
465 Unlock(i);
466 }
467 }
468
469 private:
470 234203328 inline uint8_t SelectHashmap(const Key &key) {
471 234203328 uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37);
472 230328936 double bucket = static_cast<double>(hash)
473 230328936 * static_cast<double>(num_hashmaps_)
474 / static_cast<double>(static_cast<uint32_t>(-1));
475 230328936 return static_cast<uint32_t>(bucket) % num_hashmaps_;
476 }
477
478 228406572 inline void Lock(const uint8_t target) {
479 228406572 int retval = pthread_mutex_lock(&locks_[target]);
480
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 246455640 times.
 246455640 assert(retval == 0);
481 246455640 }
482
483 225469908 inline void Unlock(const uint8_t target) {
484 225469908 int retval = pthread_mutex_unlock(&locks_[target]);
485
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 247989708 times.
 247989708 assert(retval == 0);
486 247989708 }
487
488 uint8_t num_hashmaps_;
489 SmallHashDynamic<Key, Value> *hashmaps_;
490 pthread_mutex_t *locks_;
491 };
492
493
494 // initialize the static fields
495 template<class Key, class Value>
496 Prng SmallHashDynamic<Key, Value>::g_prng;
497
498 template<class Key, class Value, class Derived>
499 const double SmallHashBase<Key, Value, Derived>::kLoadFactor = 0.75;
500
501 template<class Key, class Value>
502 const double SmallHashDynamic<Key, Value>::kThresholdGrow = 0.75;
503
504 template<class Key, class Value>
505 const double SmallHashDynamic<Key, Value>::kThresholdShrink = 0.25;
506
507 #endif // CVMFS_SMALLHASH_H_
508