GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/smallhash.h
Date: 2025-02-02 02:34:22
Exec Total Coverage
Lines: 264 268 98.5%
Branches: 89 110 80.9%
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 #ifndef __STDC_FORMAT_MACROS
9 // NOLINTNEXTLINE
10 #define __STDC_FORMAT_MACROS
11 #endif
12
13 #include <gtest/gtest_prod.h>
14 #include <inttypes.h>
15 #include <pthread.h>
16 #include <stdint.h>
17
18 #include <algorithm>
19 #include <cassert>
20 #include <cstdlib>
21 #include <new>
22
23 #include "util/atomic.h"
24 #include "util/murmur.hxx"
25 #include "util/prng.h"
26 #include "util/smalloc.h"
27
28 /**
29 * Hash table with linear probing as collision resolution. Works only for
30 * a fixed (maximum) number of elements, i.e. no resizing. Load factor fixed
31 * to 0.7.
32 */
33 template<class Key, class Value, class Derived>
34 class SmallHashBase {
35 FRIEND_TEST(T_Smallhash, InsertAndCopyMd5Slow);
36
37 public:
38 static const double kLoadFactor; // mainly useless for the dynamic version
39 static const double kThresholdGrow; // only used for resizable version
40 static const double kThresholdShrink; // only used for resizable version
41
42 6078 SmallHashBase() {
43 6078 keys_ = NULL;
44 6078 values_ = NULL;
45 6078 hasher_ = NULL;
46 6078 bytes_allocated_ = 0;
47 6078 num_collisions_ = 0;
48 6078 max_collisions_ = 0;
49
50 // Properly initialized by Init()
51 6078 capacity_ = 0;
52 6078 initial_capacity_ = 0;
53 6078 size_ = 0;
54 6078 }
55
56 6070 ~SmallHashBase() {
57 6070 DeallocMemory(keys_, values_, capacity_);
58 6070 }
59
60 6076 void Init(uint32_t expected_size, Key empty,
61 uint32_t (*hasher)(const Key &key))
62 {
63 6076 hasher_ = hasher;
64 6076 empty_key_ = empty;
65 6076 capacity_ =
66 6076 static_cast<uint32_t>(static_cast<double>(expected_size)/kLoadFactor);
67 6076 initial_capacity_ = capacity_;
68 6076 static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size
69 6076 AllocMemory();
70 6076 this->DoClear(false);
71 6076 }
72
73 3197510 bool Lookup(const Key &key, Value *value) const {
74 uint32_t bucket;
75 uint32_t collisions;
76
1/2
✓ Branch 1 taken 3197338 times.
✗ Branch 2 not taken.
 3197510 const bool found = DoLookup(key, &bucket, &collisions);
77
2/2
✓ Branch 0 taken 2692740 times.
✓ Branch 1 taken 504598 times.
 3200867 if (found)
78
1/2
✓ Branch 1 taken 2154 times.
✗ Branch 2 not taken.
 2693908 *value = values_[bucket];
79 3200867 return found;
80 }
81
82 /**
83 * Returns both the key and the value. That is useful if Key's equality
84 * operator implements an equivalence relation on Key. In this case, LookupEx
85 * returns the key representing the equivalence class that has been used
86 * during Insert().
87 * Used to return a glue::InodeEx element when looking for an inode.
88 */
89 12 bool LookupEx(Key *key, Value *value) const {
90 12 uint32_t bucket = ScaleHash(*key);
91
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
 12 while (!(keys_[bucket] == empty_key_)) {
92
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 if (keys_[bucket] == *key) {
93 8 *key = keys_[bucket];
94 8 *value = values_[bucket];
95 8 return true;
96 }
97 ✗ bucket = (bucket + 1) % capacity_;
98 }
99 4 return false;
100 }
101
102 1001996 bool Contains(const Key &key) const {
103 uint32_t bucket;
104 uint32_t collisions;
105
1/2
✓ Branch 1 taken 1001979 times.
✗ Branch 2 not taken.
 1001996 const bool found = DoLookup(key, &bucket, &collisions);
106 1001996 return found;
107 }
108
109 60771570 void Insert(const Key &key, const Value &value) {
110 60771570 static_cast<Derived *>(this)->Grow(); // No-op if fixed-size
111 60588648 const bool overwritten = DoInsert(key, value, true);
112 60614842 size_ += !overwritten; // size + 1 if the key was not yet in the map
113 60614842 }
114
115 3625124 bool Erase(const Key &key) {
116 uint32_t bucket;
117 uint32_t collisions;
118
1/2
✓ Branch 1 taken 3518031 times.
✗ Branch 2 not taken.
 3625124 const bool found = DoLookup(key, &bucket, &collisions);
119
1/2
✓ Branch 0 taken 3518401 times.
✗ Branch 1 not taken.
 3518176 if (found) {
120 3518538 keys_[bucket] = empty_key_;
121 3518538 size_--;
122 3518538 bucket = (bucket+1) % capacity_;
123
3/3
✓ Branch 0 taken 5709732 times.
✓ Branch 1 taken 3172582 times.
✓ Branch 2 taken 368513 times.
 9250964 while (!(keys_[bucket] == empty_key_)) {
124 5772399 Key rehash = keys_[bucket];
125 5772399 keys_[bucket] = empty_key_;
126
1/2
✓ Branch 1 taken 5732426 times.
✗ Branch 2 not taken.
 5772399 DoInsert(rehash, values_[bucket], false);
127 5732426 bucket = (bucket+1) % capacity_;
128 }
129
1/2
✓ Branch 1 taken 3533906 times.
✗ Branch 2 not taken.
 3478565 static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size
130 }
131 3534819 return found;
132 }
133
134 63 void Clear() {
135 63 DoClear(true);
136 63 }
137
138 186 uint64_t bytes_allocated() const { return bytes_allocated_; }
139 48 static double GetEntrySize() {
140 96 const double unit = sizeof(Key) + sizeof(Value);
141 96 return unit/kLoadFactor;
142 }
143
144 void GetCollisionStats(uint64_t *num_collisions,
145 uint32_t *max_collisions) const
146 {
147 *num_collisions = num_collisions_;
148 *max_collisions = max_collisions_;
149 }
150
151 // Careful with the direct access TODO: iterator
152 uint32_t capacity() const { return capacity_; }
153 6176 Key empty_key() const { return empty_key_; }
154 13618 Key *keys() const { return keys_; }
155 15 Value *values() const { return values_; }
156
157 // Only needed by compat
158 ✗ void SetHasher(uint32_t (*hasher)(const Key &key)) {
159 ✗ hasher_ = hasher;
160 }
161
162 protected:
163 84087555 uint32_t ScaleHash(const Key &key) const {
164 83872227 double bucket =
165 84087555 (static_cast<double>(hasher_(key)) * static_cast<double>(capacity_) /
166 static_cast<double>(static_cast<uint32_t>(-1)));
167 83872227 return static_cast<uint32_t>(bucket) % capacity_;
168 }
169
170 10598 void AllocMemory() {
171 10598 keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key)));
172 10602 values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value)));
173
2/2
✓ Branch 0 taken 57032776 times.
✓ Branch 1 taken 5356 times.
 113816416 for (uint32_t i = 0; i < capacity_; ++i) {
174 113805814 /*keys_[i] =*/ new (keys_ + i) Key();
175 }
176
2/2
✓ Branch 0 taken 57139220 times.
✓ Branch 1 taken 8897 times.
 114036386 for (uint32_t i = 0; i < capacity_; ++i) {
177 114018702 /*values_[i] =*/ new (values_ + i) Value();
178 }
179 17684 bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_;
180 17684 }
181
182 10596 void DeallocMemory(Key *k, Value *v, uint32_t c) {
183
2/2
✓ Branch 0 taken 57292597 times.
✓ Branch 1 taken 5353 times.
 114336052 for (uint32_t i = 0; i < c; ++i) {
184 114325456 k[i].~Key();
185 }
186
2/2
✓ Branch 0 taken 57298623 times.
✓ Branch 1 taken 5353 times.
 114348104 for (uint32_t i = 0; i < c; ++i) {
187 114337508 v[i].~Value();
188 }
189
2/2
✓ Branch 0 taken 5352 times.
✓ Branch 1 taken 1 times.
 10596 if (k)
190 10594 smunmap(k);
191
2/2
✓ Branch 0 taken 5352 times.
✓ Branch 1 taken 1 times.
 10596 if (v)
192 10594 smunmap(v);
193 10596 k = NULL;
194 10596 v = NULL;
195 10596 }
196
197 // Returns true iff the key is overwritten
198 71020209 bool DoInsert(const Key &key, const Value &value,
199 const bool count_collisions)
200 {
201 uint32_t bucket;
202 uint32_t collisions;
203
1/2
✓ Branch 1 taken 36514863 times.
✗ Branch 2 not taken.
 71020209 const bool overwritten = DoLookup(key, &bucket, &collisions);
204
2/2
✓ Branch 0 taken 30800911 times.
✓ Branch 1 taken 5713952 times.
 71012636 if (count_collisions) {
205 60626974 num_collisions_ += collisions;
206 60626974 max_collisions_ = std::max(collisions, max_collisions_);
207 }
208 71011512 keys_[bucket] = key;
209
1/2
✓ Branch 1 taken 1041570 times.
✗ Branch 2 not taken.
 71011512 values_[bucket] = value;
210 71011512 return overwritten;
211 }
212
213 84149447 bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const {
214 84149447 *bucket = ScaleHash(key);
215 83849450 *collisions = 0;
216
3/3
✓ Branch 0 taken 577897025 times.
✓ Branch 1 taken 35384751 times.
✓ Branch 2 taken 8432851 times.
 700588245 while (!(keys_[*bucket] == empty_key_)) {
217
3/3
✓ Branch 0 taken 6242502 times.
✓ Branch 1 taken 573092874 times.
✓ Branch 2 taken 6285083 times.
 630440802 if (keys_[*bucket] == key)
218 13702007 return true;
219 616738795 *bucket = (*bucket+1) % capacity_;
220 616738795 (*collisions)++;
221 }
222 70147443 return false;
223 }
224
225 10604 void DoClear(const bool reset_capacity) {
226
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 5295 times.
 10604 if (reset_capacity)
227 107 static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size
228
2/2
✓ Branch 0 taken 57064055 times.
✓ Branch 1 taken 5358 times.
 113876246 for (uint32_t i = 0; i < capacity_; ++i)
229 113865642 keys_[i] = empty_key_;
230 10604 size_ = 0;
231 10604 }
232
233 // Methods for resizable version
234 void SetThresholds() { }
235 void Grow() { }
236 void Shrink() { }
237 void ResetCapacity() { }
238
239 // Separate key and value arrays for better locality
240 Key *keys_;
241 Value *values_;
242 uint32_t capacity_;
243 uint32_t initial_capacity_;
244 uint32_t size_;
245 uint32_t (*hasher_)(const Key &key);
246 uint64_t bytes_allocated_;
247 uint64_t num_collisions_;
248 uint32_t max_collisions_; /**< maximum collisions for a single insert */
249 Key empty_key_;
250 };
251
252
253 template<class Key, class Value>
254 class SmallHashFixed :
255 public SmallHashBase< Key, Value, SmallHashFixed<Key, Value> >
256 {
257 friend class SmallHashBase< Key, Value, SmallHashFixed<Key, Value> >;
258 protected:
259 // No-ops
260 184 void SetThresholds() { }
261 26400 void Grow() { }
262 1138 void Shrink() { }
263 2 void ResetCapacity() { }
264 };
265
266
267 template<class Key, class Value>
268 class SmallHashDynamic :
269 public SmallHashBase< Key, Value, SmallHashDynamic<Key, Value> >
270 {
271 friend class SmallHashBase< Key, Value, SmallHashDynamic<Key, Value> >;
272 public:
273 typedef SmallHashBase< Key, Value, SmallHashDynamic<Key, Value> > Base;
274 static const double kThresholdGrow;
275 static const double kThresholdShrink;
276
277 5894 SmallHashDynamic() : Base() {
278 5894 num_migrates_ = 0;
279
280 // Properly set by Init
281 5894 threshold_grow_ = 0;
282 5894 threshold_shrink_ = 0;
283 5894 }
284
285 SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base()
286 {
287 num_migrates_ = 0;
288 CopyFrom(other);
289 }
290
291 9 SmallHashDynamic<Key, Value> &operator= (
292 const SmallHashDynamic<Key, Value> &other)
293 {
294
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 9 if (&other == this)
295 ✗ return *this;
296
297 9 CopyFrom(other);
298 9 return *this;
299 }
300
301 1774437 uint32_t capacity() const { return Base::capacity_; }
302 34679741 uint32_t size() const { return Base::size_; }
303 uint32_t num_migrates() const { return num_migrates_; }
304
305 protected:
306 10416 void SetThresholds() {
307 10414 threshold_grow_ =
308 10416 static_cast<uint32_t>(static_cast<double>(capacity()) * kThresholdGrow);
309 10414 threshold_shrink_ =
310 10414 static_cast<uint32_t>(static_cast<double>(capacity()) * kThresholdShrink);
311 10414 }
312
313 60677622 void Grow() {
314
2/2
✓ Branch 1 taken 1522 times.
✓ Branch 2 taken 30772947 times.
 60677622 if (size() > threshold_grow_)
315 3044 Migrate(capacity() * 2);
316 60601218 }
317
318 3527235 void Shrink() {
319
2/2
✓ Branch 1 taken 863727 times.
✓ Branch 2 taken 2672073 times.
 3527235 if (size() < threshold_shrink_) {
320 863864 uint32_t target_capacity = capacity() / 2;
321
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 863010 times.
 863835 if (target_capacity >= Base::initial_capacity_)
322 688 Migrate(target_capacity);
323 }
324 3535908 }
325
326 105 void ResetCapacity() {
327 105 Base::DeallocMemory(Base::keys_, Base::values_, Base::capacity_);
328 105 Base::capacity_ = Base::initial_capacity_;
329 105 Base::AllocMemory();
330 105 SetThresholds();
331 105 }
332
333 private:
334 // Returns a random permutation of indices [0..N-1] that is allocated
335 // by smmap (Knuth's shuffle algorithm)
336 1386 uint32_t *ShuffleIndices(const uint32_t N) {
337 uint32_t *shuffled =
338 1386 static_cast<uint32_t *>(smmap(N * sizeof(uint32_t)));
339 // Init with identity
340
2/2
✓ Branch 0 taken 11150585 times.
✓ Branch 1 taken 693 times.
 22302556 for (unsigned i = 0; i < N; ++i)
341 22301170 shuffled[i] = i;
342 // Shuffle (no shuffling for the last element)
343
1/2
✓ Branch 0 taken 10643433 times.
✗ Branch 1 not taken.
 21279580 for (unsigned i = 0; i < N-1; ++i) {
344 21286866 const uint32_t swap_idx = i + g_prng.Next(N - i);
345 21278194 uint32_t tmp = shuffled[i];
346 21278194 shuffled[i] = shuffled[swap_idx];
347 21278194 shuffled[swap_idx] = tmp;
348 }
349 9 return shuffled;
350 }
351
352 4418 void Migrate(const uint32_t new_capacity) {
353 4418 Key *old_keys = Base::keys_;
354 4418 Value *old_values = Base::values_;
355 4418 uint32_t old_capacity = capacity();
356 4418 uint32_t old_size = size();
357
358 4418 Base::capacity_ = new_capacity;
359 4418 SetThresholds();
360 4416 Base::AllocMemory();
361 4420 Base::DoClear(false);
362
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 1522 times.
 4420 if (new_capacity < old_capacity) {
363 1376 uint32_t *shuffled_indices = ShuffleIndices(old_capacity);
364
2/2
✓ Branch 0 taken 9634251 times.
✓ Branch 1 taken 54 times.
 19268610 for (uint32_t i = 0; i < old_capacity; ++i) {
365
2/3
✓ Branch 0 taken 2416580 times.
✓ Branch 1 taken 7217671 times.
✗ Branch 2 not taken.
 19268502 if (old_keys[shuffled_indices[i]] != Base::empty_key_) {
366 4833160 Base::Insert(old_keys[shuffled_indices[i]],
367 4833160 old_values[shuffled_indices[i]]);
368 }
369 }
370 108 smunmap(shuffled_indices);
371 } else {
372
2/2
✓ Branch 0 taken 18784816 times.
✓ Branch 1 taken 1160 times.
 37571952 for (uint32_t i = 0; i < old_capacity; ++i) {
373
3/3
✓ Branch 0 taken 10468175 times.
✓ Branch 1 taken 7108176 times.
✓ Branch 2 taken 1208465 times.
 37569632 if (old_keys[i] != Base::empty_key_)
374 28187778 Base::Insert(old_keys[i], old_values[i]);
375 }
376 }
377
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2210 times.
 3696 assert(size() == old_size);
378
379 4420 Base::DeallocMemory(old_keys, old_values, old_capacity);
380 4420 num_migrates_++;
381 4420 }
382
383 9 void CopyFrom(const SmallHashDynamic<Key, Value> &other) {
384 9 uint32_t *shuffled_indices = ShuffleIndices(other.capacity_);
385
2/2
✓ Branch 0 taken 1376340 times.
✓ Branch 1 taken 5 times.
 1376433 for (uint32_t i = 0; i < other.capacity_; ++i) {
386
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 1000042 times.
✓ Branch 2 taken 376298 times.
 1376424 if (other.keys_[shuffled_indices[i]] != other.empty_key_) {
387 1000000 this->Insert(other.keys_[shuffled_indices[i]],
388 1000000 other.values_[shuffled_indices[i]]);
389 }
390 }
391 9 smunmap(shuffled_indices);
392 9 }
393
394 uint32_t num_migrates_;
395 uint32_t threshold_grow_;
396 uint32_t threshold_shrink_;
397 static Prng g_prng;
398 };
399
400
401 /**
402 * Distributes the key-value pairs over $n$ dynamic hash maps with individual
403 * mutexes. Hence low mutex contention, and benefits from multiple processors.
404 */
405 template<class Key, class Value>
406 class MultiHash {
407 public:
408 10 MultiHash() {
409 10 num_hashmaps_ = 0;
410 10 hashmaps_ = NULL;
411 10 locks_ = NULL;
412 10 }
413
414 10 void Init(const uint8_t num_hashmaps, const Key &empty_key,
415 uint32_t (*hasher)(const Key &key))
416 {
417
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 assert(num_hashmaps > 0);
418 10 const uint8_t N = num_hashmaps;
419 10 num_hashmaps_ = N;
420
3/4
✓ Branch 2 taken 420 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 420 times.
✓ Branch 5 taken 10 times.
 430 hashmaps_ = new SmallHashDynamic<Key, Value>[N]();
421 10 locks_ =
422 10 static_cast<pthread_mutex_t *>(smalloc(N * sizeof(pthread_mutex_t)));
423
2/2
✓ Branch 0 taken 420 times.
✓ Branch 1 taken 10 times.
 430 for (uint8_t i = 0; i < N; ++i) {
424 420 int retval = pthread_mutex_init(&locks_[i], NULL);
425
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 420 times.
 420 assert(retval == 0);
426 420 hashmaps_[i].Init(128, empty_key, hasher);
427 }
428 10 }
429
430 10 ~MultiHash() {
431
2/2
✓ Branch 0 taken 420 times.
✓ Branch 1 taken 10 times.
 430 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
432 420 pthread_mutex_destroy(&locks_[i]);
433 }
434 10 free(locks_);
435
3/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 420 times.
✓ Branch 3 taken 10 times.
 430 delete[] hashmaps_;
436 10 }
437
438 1000000 bool Lookup(const Key &key, Value *value) {
439 1000000 uint8_t target = SelectHashmap(key);
440 1000000 Lock(target);
441 1000000 const bool result = hashmaps_[target].Lookup(key, value);
442 1000000 Unlock(target);
443 1000000 return result;
444 }
445
446 3714033 void Insert(const Key &key, const Value &value) {
447 3714033 uint8_t target = SelectHashmap(key);
448 3608038 Lock(target);
449 3748641 hashmaps_[target].Insert(key, value);
450 3567240 Unlock(target);
451 3891242 }
452
453 1788270 void Erase(const Key &key) {
454 1788270 uint8_t target = SelectHashmap(key);
455 1706101 Lock(target);
456 1830493 hashmaps_[target].Erase(key);
457 1668011 Unlock(target);
458 1856946 }
459
460 1 void Clear() {
461
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
 43 for (uint8_t i = 0; i < num_hashmaps_; ++i)
462 42 Lock(i);
463
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
 43 for (uint8_t i = 0; i < num_hashmaps_; ++i)
464 42 hashmaps_[i].Clear();
465
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
 43 for (uint8_t i = 0; i < num_hashmaps_; ++i)
466 42 Unlock(i);
467 1 }
468
469 10 uint8_t num_hashmaps() const { return num_hashmaps_; }
470
471 8 void GetSizes(uint32_t *sizes) {
472
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 8 times.
 344 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
473 336 Lock(i);
474 336 sizes[i] = hashmaps_[i].size();
475 336 Unlock(i);
476 }
477 8 }
478
479 void GetCollisionStats(uint64_t *num_collisions, uint32_t *max_collisions) {
480 for (uint8_t i = 0; i < num_hashmaps_; ++i) {
481 Lock(i);
482 hashmaps_[i].GetCollisionStats(&num_collisions[i], &max_collisions[i]);
483 Unlock(i);
484 }
485 }
486
487 private:
488 6488850 inline uint8_t SelectHashmap(const Key &key) {
489 6488850 uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37);
490 6361097 double bucket =
491 6361097 static_cast<double>(hash) * static_cast<double>(num_hashmaps_) /
492 static_cast<double>(static_cast<uint32_t>(-1));
493 6361097 return static_cast<uint32_t>(bucket) % num_hashmaps_;
494 }
495
496 6296462 inline void Lock(const uint8_t target) {
497 6296462 int retval = pthread_mutex_lock(&locks_[target]);
498
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6833766 times.
 6833766 assert(retval == 0);
499 6833766 }
500
501 6236523 inline void Unlock(const uint8_t target) {
502 6236523 int retval = pthread_mutex_unlock(&locks_[target]);
503
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6897706 times.
 6897706 assert(retval == 0);
504 6897706 }
505
506 uint8_t num_hashmaps_;
507 SmallHashDynamic<Key, Value> *hashmaps_;
508 pthread_mutex_t *locks_;
509 };
510
511
512 // initialize the static fields
513 template<class Key, class Value>
514 Prng SmallHashDynamic<Key, Value>::g_prng;
515
516 template<class Key, class Value, class Derived>
517 const double SmallHashBase<Key, Value, Derived>::kLoadFactor = 0.75;
518
519 template<class Key, class Value>
520 const double SmallHashDynamic<Key, Value>::kThresholdGrow = 0.75;
521
522 template<class Key, class Value>
523 const double SmallHashDynamic<Key, Value>::kThresholdShrink = 0.25;
524
525 #endif // CVMFS_SMALLHASH_H_
526