Directory: | cvmfs/ |
---|---|
File: | cvmfs/smallhash.h |
Date: | 2025-07-27 02:42:09 |
Exec | Total | Coverage | |
---|---|---|---|
Lines: | 259 | 263 | 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 | 93444 | SmallHashBase() { | |
43 | 93444 | keys_ = NULL; | |
44 | 93444 | values_ = NULL; | |
45 | 93444 | hasher_ = NULL; | |
46 | 93444 | bytes_allocated_ = 0; | |
47 | 93444 | num_collisions_ = 0; | |
48 | 93444 | max_collisions_ = 0; | |
49 | |||
50 | // Properly initialized by Init() | ||
51 | 93444 | capacity_ = 0; | |
52 | 93444 | initial_capacity_ = 0; | |
53 | 93444 | size_ = 0; | |
54 | 93444 | } | |
55 | |||
56 | 93306 | ~SmallHashBase() { DeallocMemory(keys_, values_, capacity_); } | |
57 | |||
58 | 93442 | void Init(uint32_t expected_size, Key empty, | |
59 | uint32_t (*hasher)(const Key &key)) { | ||
60 | 93442 | hasher_ = hasher; | |
61 | 93442 | empty_key_ = empty; | |
62 | 93442 | capacity_ = static_cast<uint32_t>(static_cast<double>(expected_size) | |
63 | 93442 | / kLoadFactor); | |
64 | 93442 | initial_capacity_ = capacity_; | |
65 | 93442 | static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size | |
66 | 93442 | AllocMemory(); | |
67 | 93442 | this->DoClear(false); | |
68 | 93442 | } | |
69 | |||
70 | 20282860 | bool Lookup(const Key &key, Value *value) const { | |
71 | uint32_t bucket; | ||
72 | uint32_t collisions; | ||
73 |
1/2✓ Branch 1 taken 20322858 times.
✗ Branch 2 not taken.
|
20282860 | const bool found = DoLookup(key, &bucket, &collisions); |
74 |
2/2✓ Branch 0 taken 12260829 times.
✓ Branch 1 taken 8062029 times.
|
20336316 | if (found) |
75 |
1/2✓ Branch 1 taken 36558 times.
✗ Branch 2 not taken.
|
12265287 | *value = values_[bucket]; |
76 | 20336316 | return found; | |
77 | } | ||
78 | |||
79 | /** | ||
80 | * Returns both the key and the value. That is useful if Key's equality | ||
81 | * operator implements an equivalence relation on Key. In this case, LookupEx | ||
82 | * returns the key representing the equivalence class that has been used | ||
83 | * during Insert(). | ||
84 | * Used to return a glue::InodeEx element when looking for an inode. | ||
85 | */ | ||
86 | 504 | bool LookupEx(Key *key, Value *value) const { | |
87 | 504 | uint32_t bucket = ScaleHash(*key); | |
88 |
2/2✓ Branch 1 taken 168 times.
✓ Branch 2 taken 84 times.
|
504 | while (!(keys_[bucket] == empty_key_)) { |
89 |
1/2✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
|
336 | if (keys_[bucket] == *key) { |
90 | 336 | *key = keys_[bucket]; | |
91 | 336 | *value = values_[bucket]; | |
92 | 336 | return true; | |
93 | } | ||
94 | ✗ | bucket = (bucket + 1) % capacity_; | |
95 | } | ||
96 | 168 | return false; | |
97 | } | ||
98 | |||
99 | 49040235 | bool Contains(const Key &key) const { | |
100 | uint32_t bucket; | ||
101 | uint32_t collisions; | ||
102 |
1/2✓ Branch 1 taken 49039950 times.
✗ Branch 2 not taken.
|
49040235 | const bool found = DoLookup(key, &bucket, &collisions); |
103 | 49040235 | return found; | |
104 | } | ||
105 | |||
106 | 274515098 | void Insert(const Key &key, const Value &value) { | |
107 | 274515098 | static_cast<Derived *>(this)->Grow(); // No-op if fixed-size | |
108 | 274303514 | const bool overwritten = DoInsert(key, value, true); | |
109 | 274305312 | size_ += !overwritten; // size + 1 if the key was not yet in the map | |
110 | 274305312 | } | |
111 | |||
112 | 26232917 | bool Erase(const Key &key) { | |
113 | uint32_t bucket; | ||
114 | uint32_t collisions; | ||
115 |
1/2✓ Branch 1 taken 26157238 times.
✗ Branch 2 not taken.
|
26232917 | const bool found = DoLookup(key, &bucket, &collisions); |
116 |
2/2✓ Branch 0 taken 26157105 times.
✓ Branch 1 taken 133 times.
|
26160931 | if (found) { |
117 | 26160424 | keys_[bucket] = empty_key_; | |
118 | 26160424 | size_--; | |
119 | 26160424 | bucket = (bucket + 1) % capacity_; | |
120 |
3/3✓ Branch 0 taken 22365455 times.
✓ Branch 1 taken 13041112 times.
✓ Branch 2 taken 15472287 times.
|
50882173 | while (!(keys_[bucket] == empty_key_)) { |
121 | 24777954 | Key rehash = keys_[bucket]; | |
122 | 24777954 | keys_[bucket] = empty_key_; | |
123 |
1/2✓ Branch 1 taken 24721749 times.
✗ Branch 2 not taken.
|
24777954 | DoInsert(rehash, values_[bucket], false); |
124 | 24721749 | bucket = (bucket + 1) % capacity_; | |
125 | } | ||
126 |
1/2✓ Branch 1 taken 26131309 times.
✗ Branch 2 not taken.
|
26104219 | static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size |
127 | } | ||
128 | 26154609 | return found; | |
129 | } | ||
130 | |||
131 | 352 | void Clear() { DoClear(true); } | |
132 | |||
133 | 1624 | uint64_t bytes_allocated() const { return bytes_allocated_; } | |
134 | 144 | static double GetEntrySize() { | |
135 | 288 | const double unit = sizeof(Key) + sizeof(Value); | |
136 | 288 | return unit / kLoadFactor; | |
137 | } | ||
138 | |||
139 | void GetCollisionStats(uint64_t *num_collisions, | ||
140 | uint32_t *max_collisions) const { | ||
141 | *num_collisions = num_collisions_; | ||
142 | *max_collisions = max_collisions_; | ||
143 | } | ||
144 | |||
145 | // Careful with the direct access TODO: iterator | ||
146 | uint32_t capacity() const { return capacity_; } | ||
147 | 7242 | Key empty_key() const { return empty_key_; } | |
148 | 35664 | Key *keys() const { return keys_; } | |
149 | 357 | Value *values() const { return values_; } | |
150 | |||
151 | // Only needed by compat | ||
152 | ✗ | void SetHasher(uint32_t (*hasher)(const Key &key)) { hasher_ = hasher; } | |
153 | |||
154 | protected: | ||
155 | 470472069 | uint32_t ScaleHash(const Key &key) const { | |
156 | 470472069 | const double bucket = (static_cast<double>(hasher_(key)) | |
157 | 469842953 | * static_cast<double>(capacity_) | |
158 | / static_cast<double>(static_cast<uint32_t>(-1))); | ||
159 | 469842953 | return static_cast<uint32_t>(bucket) % capacity_; | |
160 | } | ||
161 | |||
162 | 100068 | void AllocMemory() { | |
163 | 100068 | keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key))); | |
164 | 100072 | values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value))); | |
165 |
2/2✓ Branch 0 taken 732157555 times.
✓ Branch 1 taken 50907 times.
|
1463174522 | for (uint32_t i = 0; i < capacity_; ++i) { |
166 | 1463074450 | /*keys_[i] =*/new (keys_ + i) Key(); | |
167 | } | ||
168 |
2/2✓ Branch 0 taken 732295944 times.
✓ Branch 1 taken 54863 times.
|
1463459212 | for (uint32_t i = 0; i < capacity_; ++i) { |
169 | 1463351228 | /*values_[i] =*/new (values_ + i) Value(); | |
170 | } | ||
171 | 107984 | bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_; | |
172 | 107984 | } | |
173 | |||
174 | 99936 | void DeallocMemory(Key *k, Value *v, uint32_t c) { | |
175 |
2/2✓ Branch 0 taken 732482552 times.
✓ Branch 1 taken 50838 times.
|
1463827110 | for (uint32_t i = 0; i < c; ++i) { |
176 | 1463727174 | k[i].~Key(); | |
177 | } | ||
178 |
2/2✓ Branch 0 taken 732392384 times.
✓ Branch 1 taken 50838 times.
|
1463646774 | for (uint32_t i = 0; i < c; ++i) { |
179 | 1463546838 | v[i].~Value(); | |
180 | } | ||
181 |
2/2✓ Branch 0 taken 50837 times.
✓ Branch 1 taken 1 times.
|
99936 | if (k) |
182 | 99934 | smunmap(k); | |
183 |
2/2✓ Branch 0 taken 50837 times.
✓ Branch 1 taken 1 times.
|
99936 | if (v) |
184 | 99934 | smunmap(v); | |
185 | 99936 | k = NULL; | |
186 | 99936 | v = NULL; | |
187 | 99936 | } | |
188 | |||
189 | // Returns true iff the key is overwritten | ||
190 | 306081193 | bool DoInsert(const Key &key, const Value &value, | |
191 | const bool count_collisions) { | ||
192 | uint32_t bucket; | ||
193 | uint32_t collisions; | ||
194 |
1/2✓ Branch 1 taken 169462468 times.
✗ Branch 2 not taken.
|
306081193 | const bool overwritten = DoLookup(key, &bucket, &collisions); |
195 |
2/2✓ Branch 0 taken 144739455 times.
✓ Branch 1 taken 24723013 times.
|
306068691 | if (count_collisions) { |
196 | 274352626 | num_collisions_ += collisions; | |
197 | 274352626 | max_collisions_ = std::max(collisions, max_collisions_); | |
198 | } | ||
199 | 306027557 | keys_[bucket] = key; | |
200 |
1/2✓ Branch 1 taken 17710717 times.
✗ Branch 2 not taken.
|
306027557 | values_[bucket] = value; |
201 | 306027557 | return overwritten; | |
202 | } | ||
203 | |||
204 | 470729667 | bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const { | |
205 | 470729667 | *bucket = ScaleHash(key); | |
206 | 469801973 | *collisions = 0; | |
207 |
3/3✓ Branch 0 taken 9228282817 times.
✓ Branch 1 taken 299397741 times.
✓ Branch 2 taken 110521299 times.
|
10048554265 | while (!(keys_[*bucket] == empty_key_)) { |
208 |
3/3✓ Branch 0 taken 29867130 times.
✓ Branch 1 taken 9263002894 times.
✓ Branch 2 taken 175405302 times.
|
9742392058 | if (keys_[*bucket] == key) |
209 | 163639766 | return true; | |
210 | 9578752292 | *bucket = (*bucket + 1) % capacity_; | |
211 | 9578752292 | (*collisions)++; | |
212 | } | ||
213 | 306162207 | return false; | |
214 | } | ||
215 | |||
216 | 100106 | void DoClear(const bool reset_capacity) { | |
217 |
2/2✓ Branch 0 taken 352 times.
✓ Branch 1 taken 50589 times.
|
100106 | if (reset_capacity) |
218 | 398 | static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size | |
219 |
2/2✓ Branch 0 taken 732555159 times.
✓ Branch 1 taken 50941 times.
|
1463923354 | for (uint32_t i = 0; i < capacity_; ++i) |
220 | 1463823248 | keys_[i] = empty_key_; | |
221 | 100106 | size_ = 0; | |
222 | 100106 | } | |
223 | |||
224 | // Methods for resizable version | ||
225 | void SetThresholds() { } | ||
226 | void Grow() { } | ||
227 | void Shrink() { } | ||
228 | void ResetCapacity() { } | ||
229 | |||
230 | // Separate key and value arrays for better locality | ||
231 | Key *keys_; | ||
232 | Value *values_; | ||
233 | uint32_t capacity_; | ||
234 | uint32_t initial_capacity_; | ||
235 | uint32_t size_; | ||
236 | uint32_t (*hasher_)(const Key &key); | ||
237 | uint64_t bytes_allocated_; | ||
238 | uint64_t num_collisions_; | ||
239 | uint32_t max_collisions_; /**< maximum collisions for a single insert */ | ||
240 | Key empty_key_; | ||
241 | }; | ||
242 | |||
243 | |||
244 | template<class Key, class Value> | ||
245 | class SmallHashFixed | ||
246 | : public SmallHashBase<Key, Value, SmallHashFixed<Key, Value> > { | ||
247 | friend class SmallHashBase<Key, Value, SmallHashFixed<Key, Value> >; | ||
248 | |||
249 | protected: | ||
250 | // No-ops | ||
251 | 1590 | void SetThresholds() { } | |
252 | 98210 | void Grow() { } | |
253 | 19474 | void Shrink() { } | |
254 | 34 | void ResetCapacity() { } | |
255 | }; | ||
256 | |||
257 | |||
258 | template<class Key, class Value> | ||
259 | class SmallHashDynamic | ||
260 | : public SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> > { | ||
261 | friend class SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> >; | ||
262 | |||
263 | public: | ||
264 | typedef SmallHashBase<Key, Value, SmallHashDynamic<Key, Value> > Base; | ||
265 | static const double kThresholdGrow; | ||
266 | static const double kThresholdShrink; | ||
267 | |||
268 | 91854 | SmallHashDynamic() : Base() { | |
269 | 91854 | num_migrates_ = 0; | |
270 | |||
271 | // Properly set by Init | ||
272 | 91854 | threshold_grow_ = 0; | |
273 | 91854 | threshold_shrink_ = 0; | |
274 | 91854 | } | |
275 | |||
276 | SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base() { | ||
277 | num_migrates_ = 0; | ||
278 | CopyFrom(other); | ||
279 | } | ||
280 | |||
281 | 369 | SmallHashDynamic<Key, Value> &operator=( | |
282 | const SmallHashDynamic<Key, Value> &other) { | ||
283 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 185 times.
|
369 | if (&other == this) |
284 | ✗ | return *this; | |
285 | |||
286 | 369 | CopyFrom(other); | |
287 | 369 | return *this; | |
288 | } | ||
289 | |||
290 | 46472872 | uint32_t capacity() const { return Base::capacity_; } | |
291 | 186219841 | uint32_t size() const { return Base::size_; } | |
292 | uint32_t num_migrates() const { return num_migrates_; } | ||
293 | |||
294 | protected: | ||
295 | 98474 | void SetThresholds() { | |
296 | 98474 | threshold_grow_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
297 | 98474 | * kThresholdGrow); | |
298 | 98474 | threshold_shrink_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
299 | 98476 | * kThresholdShrink); | |
300 | 98476 | } | |
301 | |||
302 | 274351834 | void Grow() { | |
303 |
2/2✓ Branch 1 taken 2422 times.
✓ Branch 2 taken 144630068 times.
|
274351834 | if (size() > threshold_grow_) |
304 | 4844 | Migrate(capacity() * 2); | |
305 | 274250298 | } | |
306 | |||
307 | 26136473 | void Shrink() { | |
308 |
2/2✓ Branch 1 taken 23112328 times.
✓ Branch 2 taken 3017822 times.
|
26136473 | if (size() < threshold_shrink_) { |
309 | 23115647 | const uint32_t target_capacity = capacity() / 2; | |
310 |
2/2✓ Branch 0 taken 687 times.
✓ Branch 1 taken 23109260 times.
|
23113266 | if (target_capacity >= Base::initial_capacity_) |
311 | 687 | Migrate(target_capacity); | |
312 | } | ||
313 | 26131089 | } | |
314 | |||
315 | 364 | void ResetCapacity() { | |
316 | 364 | Base::DeallocMemory(Base::keys_, Base::values_, Base::capacity_); | |
317 | 364 | Base::capacity_ = Base::initial_capacity_; | |
318 | 364 | Base::AllocMemory(); | |
319 | 364 | SetThresholds(); | |
320 | 364 | } | |
321 | |||
322 | private: | ||
323 | // Returns a random permutation of indices [0..N-1] that is allocated | ||
324 | // by smmap (Knuth's shuffle algorithm) | ||
325 | 1746 | uint32_t *ShuffleIndices(const uint32_t N) { | |
326 | 1746 | uint32_t *shuffled = static_cast<uint32_t *>(smmap(N * sizeof(uint32_t))); | |
327 | // Init with identity | ||
328 |
2/2✓ Branch 0 taken 11287737 times.
✓ Branch 1 taken 873 times.
|
22577220 | for (unsigned i = 0; i < N; ++i) |
329 | 22575474 | shuffled[i] = i; | |
330 | // Shuffle (no shuffling for the last element) | ||
331 |
1/2✓ Branch 0 taken 10692253 times.
✗ Branch 1 not taken.
|
21381362 | for (unsigned i = 0; i < N - 1; ++i) { |
332 | 21384506 | const uint32_t swap_idx = i + g_prng.Next(N - i); | |
333 | 21379616 | const uint32_t tmp = shuffled[i]; | |
334 | 21379616 | shuffled[i] = shuffled[swap_idx]; | |
335 | 21379616 | shuffled[swap_idx] = tmp; | |
336 | } | ||
337 | 369 | return shuffled; | |
338 | } | ||
339 | |||
340 | 6216 | void Migrate(const uint32_t new_capacity) { | |
341 | 6216 | Key *old_keys = Base::keys_; | |
342 | 6216 | Value *old_values = Base::values_; | |
343 | 6216 | const uint32_t old_capacity = capacity(); | |
344 | 6216 | const uint32_t old_size = size(); | |
345 | |||
346 | 6216 | Base::capacity_ = new_capacity; | |
347 | 6216 | SetThresholds(); | |
348 | 6218 | Base::AllocMemory(); | |
349 | 6224 | Base::DoClear(false); | |
350 |
2/2✓ Branch 0 taken 688 times.
✓ Branch 1 taken 2424 times.
|
6224 | if (new_capacity < old_capacity) { |
351 | 1376 | uint32_t *shuffled_indices = ShuffleIndices(old_capacity); | |
352 |
1/2✓ Branch 0 taken 9663115 times.
✗ Branch 1 not taken.
|
19326130 | for (uint32_t i = 0; i < old_capacity; ++i) { |
353 |
2/3✓ Branch 0 taken 2427649 times.
✓ Branch 1 taken 7235466 times.
✗ Branch 2 not taken.
|
19326230 | if (old_keys[shuffled_indices[i]] != Base::empty_key_) { |
354 | 4855298 | Base::Insert(old_keys[shuffled_indices[i]], | |
355 | 4855298 | old_values[shuffled_indices[i]]); | |
356 | } | ||
357 | } | ||
358 | ✗ | smunmap(shuffled_indices); | |
359 | } else { | ||
360 |
2/2✓ Branch 0 taken 47438625 times.
✓ Branch 1 taken 2082 times.
|
94881414 | for (uint32_t i = 0; i < old_capacity; ++i) { |
361 |
3/3✓ Branch 0 taken 10511959 times.
✓ Branch 1 taken 28569851 times.
✓ Branch 2 taken 8356815 times.
|
94877250 | if (old_keys[i] != Base::empty_key_) |
362 | 71171432 | Base::Insert(old_keys[i], old_values[i]); | |
363 | } | ||
364 | } | ||
365 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3112 times.
|
5540 | assert(size() == old_size); |
366 | |||
367 | 6224 | Base::DeallocMemory(old_keys, old_values, old_capacity); | |
368 | 6224 | num_migrates_++; | |
369 | 6224 | } | |
370 | |||
371 | 369 | void CopyFrom(const SmallHashDynamic<Key, Value> &other) { | |
372 | 369 | uint32_t *shuffled_indices = ShuffleIndices(other.capacity_); | |
373 |
2/2✓ Branch 0 taken 1380120 times.
✓ Branch 1 taken 185 times.
|
1384353 | for (uint32_t i = 0; i < other.capacity_; ++i) { |
374 |
2/3✗ Branch 0 not taken.
✓ Branch 1 taken 1001932 times.
✓ Branch 2 taken 378188 times.
|
1383984 | if (other.keys_[shuffled_indices[i]] != other.empty_key_) { |
375 | 1000000 | this->Insert(other.keys_[shuffled_indices[i]], | |
376 | 1000000 | other.values_[shuffled_indices[i]]); | |
377 | } | ||
378 | } | ||
379 | 369 | smunmap(shuffled_indices); | |
380 | 369 | } | |
381 | |||
382 | uint32_t num_migrates_; | ||
383 | uint32_t threshold_grow_; | ||
384 | uint32_t threshold_shrink_; | ||
385 | static Prng g_prng; | ||
386 | }; | ||
387 | |||
388 | |||
389 | /** | ||
390 | * Distributes the key-value pairs over $n$ dynamic hash maps with individual | ||
391 | * mutexes. Hence low mutex contention, and benefits from multiple processors. | ||
392 | */ | ||
393 | template<class Key, class Value> | ||
394 | class MultiHash { | ||
395 | public: | ||
396 | 10 | MultiHash() { | |
397 | 10 | num_hashmaps_ = 0; | |
398 | 10 | hashmaps_ = NULL; | |
399 | 10 | locks_ = NULL; | |
400 | 10 | } | |
401 | |||
402 | 10 | void Init(const uint8_t num_hashmaps, const Key &empty_key, | |
403 | uint32_t (*hasher)(const Key &key)) { | ||
404 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
|
10 | assert(num_hashmaps > 0); |
405 | 10 | const uint8_t N = num_hashmaps; | |
406 | 10 | num_hashmaps_ = N; | |
407 |
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](); |
408 | 10 | locks_ = static_cast<pthread_mutex_t *>( | |
409 | 10 | smalloc(N * sizeof(pthread_mutex_t))); | |
410 |
2/2✓ Branch 0 taken 420 times.
✓ Branch 1 taken 10 times.
|
430 | for (uint8_t i = 0; i < N; ++i) { |
411 | 420 | int retval = pthread_mutex_init(&locks_[i], NULL); | |
412 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 420 times.
|
420 | assert(retval == 0); |
413 | 420 | hashmaps_[i].Init(128, empty_key, hasher); | |
414 | } | ||
415 | 10 | } | |
416 | |||
417 | 10 | ~MultiHash() { | |
418 |
2/2✓ Branch 0 taken 420 times.
✓ Branch 1 taken 10 times.
|
430 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
419 | 420 | pthread_mutex_destroy(&locks_[i]); | |
420 | } | ||
421 | 10 | free(locks_); | |
422 |
3/4✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 420 times.
✓ Branch 3 taken 10 times.
|
430 | delete[] hashmaps_; |
423 | 10 | } | |
424 | |||
425 | 1000000 | bool Lookup(const Key &key, Value *value) { | |
426 | 1000000 | uint8_t target = SelectHashmap(key); | |
427 | 1000000 | Lock(target); | |
428 | 1000000 | const bool result = hashmaps_[target].Lookup(key, value); | |
429 | 1000000 | Unlock(target); | |
430 | 1000000 | return result; | |
431 | } | ||
432 | |||
433 | 3739289 | void Insert(const Key &key, const Value &value) { | |
434 | 3739289 | uint8_t target = SelectHashmap(key); | |
435 | 3635480 | Lock(target); | |
436 | 3783069 | hashmaps_[target].Insert(key, value); | |
437 | 3603161 | Unlock(target); | |
438 | 3892150 | } | |
439 | |||
440 | 1808374 | void Erase(const Key &key) { | |
441 | 1808374 | uint8_t target = SelectHashmap(key); | |
442 | 1728613 | Lock(target); | |
443 | 1851886 | hashmaps_[target].Erase(key); | |
444 | 1675572 | Unlock(target); | |
445 | 1874711 | } | |
446 | |||
447 | 1 | void Clear() { | |
448 |
2/2✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
|
43 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
449 | 42 | Lock(i); | |
450 |
2/2✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
|
43 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
451 | 42 | hashmaps_[i].Clear(); | |
452 |
2/2✓ Branch 0 taken 42 times.
✓ Branch 1 taken 1 times.
|
43 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
453 | 42 | Unlock(i); | |
454 | 1 | } | |
455 | |||
456 | 10 | uint8_t num_hashmaps() const { return num_hashmaps_; } | |
457 | |||
458 | 8 | void GetSizes(uint32_t *sizes) { | |
459 |
2/2✓ Branch 0 taken 336 times.
✓ Branch 1 taken 8 times.
|
344 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
460 | 336 | Lock(i); | |
461 | 336 | sizes[i] = hashmaps_[i].size(); | |
462 | 336 | Unlock(i); | |
463 | } | ||
464 | 8 | } | |
465 | |||
466 | void GetCollisionStats(uint64_t *num_collisions, uint32_t *max_collisions) { | ||
467 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { | ||
468 | Lock(i); | ||
469 | hashmaps_[i].GetCollisionStats(&num_collisions[i], &max_collisions[i]); | ||
470 | Unlock(i); | ||
471 | } | ||
472 | } | ||
473 | |||
474 | private: | ||
475 | 6502426 | inline uint8_t SelectHashmap(const Key &key) { | |
476 | 6502426 | uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37); | |
477 | 6395470 | double bucket = static_cast<double>(hash) | |
478 | 6395470 | * static_cast<double>(num_hashmaps_) | |
479 | / static_cast<double>(static_cast<uint32_t>(-1)); | ||
480 | 6395470 | return static_cast<uint32_t>(bucket) % num_hashmaps_; | |
481 | } | ||
482 | |||
483 | 6439731 | inline void Lock(const uint8_t target) { | |
484 | 6439731 | int retval = pthread_mutex_lock(&locks_[target]); | |
485 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6871273 times.
|
6871273 | assert(retval == 0); |
486 | 6871273 | } | |
487 | |||
488 | 6279316 | inline void Unlock(const uint8_t target) { | |
489 | 6279316 | int retval = pthread_mutex_unlock(&locks_[target]); | |
490 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6888395 times.
|
6888395 | assert(retval == 0); |
491 | 6888395 | } | |
492 | |||
493 | uint8_t num_hashmaps_; | ||
494 | SmallHashDynamic<Key, Value> *hashmaps_; | ||
495 | pthread_mutex_t *locks_; | ||
496 | }; | ||
497 | |||
498 | |||
499 | // initialize the static fields | ||
500 | template<class Key, class Value> | ||
501 | Prng SmallHashDynamic<Key, Value>::g_prng; | ||
502 | |||
503 | template<class Key, class Value, class Derived> | ||
504 | const double SmallHashBase<Key, Value, Derived>::kLoadFactor = 0.75; | ||
505 | |||
506 | template<class Key, class Value> | ||
507 | const double SmallHashDynamic<Key, Value>::kThresholdGrow = 0.75; | ||
508 | |||
509 | template<class Key, class Value> | ||
510 | const double SmallHashDynamic<Key, Value>::kThresholdShrink = 0.25; | ||
511 | |||
512 | #endif // CVMFS_SMALLHASH_H_ | ||
513 |