Directory: | cvmfs/ |
---|---|
File: | cvmfs/smallhash.h |
Date: | 2024-04-21 02:33:16 |
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 | 6064 | SmallHashBase() { | |
43 | 6064 | keys_ = NULL; | |
44 | 6064 | values_ = NULL; | |
45 | 6064 | hasher_ = NULL; | |
46 | 6064 | bytes_allocated_ = 0; | |
47 | 6064 | num_collisions_ = 0; | |
48 | 6064 | max_collisions_ = 0; | |
49 | |||
50 | // Properly initialized by Init() | ||
51 | 6064 | capacity_ = 0; | |
52 | 6064 | initial_capacity_ = 0; | |
53 | 6064 | size_ = 0; | |
54 | 6064 | } | |
55 | |||
56 | 6056 | ~SmallHashBase() { | |
57 | 6056 | DeallocMemory(keys_, values_, capacity_); | |
58 | 6056 | } | |
59 | |||
60 | 6062 | void Init(uint32_t expected_size, Key empty, | |
61 | uint32_t (*hasher)(const Key &key)) | ||
62 | { | ||
63 | 6062 | hasher_ = hasher; | |
64 | 6062 | empty_key_ = empty; | |
65 | 6062 | capacity_ = | |
66 | 6062 | static_cast<uint32_t>(static_cast<double>(expected_size)/kLoadFactor); | |
67 | 6062 | initial_capacity_ = capacity_; | |
68 | 6062 | static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size | |
69 | 6062 | AllocMemory(); | |
70 | 6062 | this->DoClear(false); | |
71 | 6062 | } | |
72 | |||
73 | 3199611 | bool Lookup(const Key &key, Value *value) const { | |
74 | uint32_t bucket; | ||
75 | uint32_t collisions; | ||
76 |
1/2✓ Branch 1 taken 3198434 times.
✗ Branch 2 not taken.
|
3199611 | const bool found = DoLookup(key, &bucket, &collisions); |
77 |
2/2✓ Branch 0 taken 2693352 times.
✓ Branch 1 taken 505082 times.
|
3201613 | if (found) |
78 |
1/2✓ Branch 1 taken 2154 times.
✗ Branch 2 not taken.
|
2694427 | *value = values_[bucket]; |
79 | 3201613 | 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 | 60890070 | void Insert(const Key &key, const Value &value) { | |
110 | 60890070 | static_cast<Derived *>(this)->Grow(); // No-op if fixed-size | |
111 | 60704985 | const bool overwritten = DoInsert(key, value, true); | |
112 | 60712408 | size_ += !overwritten; // size + 1 if the key was not yet in the map | |
113 | 60712408 | } | |
114 | |||
115 | 3639649 | bool Erase(const Key &key) { | |
116 | uint32_t bucket; | ||
117 | uint32_t collisions; | ||
118 |
1/2✓ Branch 1 taken 3548931 times.
✗ Branch 2 not taken.
|
3639649 | const bool found = DoLookup(key, &bucket, &collisions); |
119 |
1/2✓ Branch 0 taken 3549891 times.
✗ Branch 1 not taken.
|
3548934 | if (found) { |
120 | 3549894 | keys_[bucket] = empty_key_; | |
121 | 3549894 | size_--; | |
122 | 3549894 | bucket = (bucket+1) % capacity_; | |
123 |
3/3✓ Branch 0 taken 5732257 times.
✓ Branch 1 taken 3222543 times.
✓ Branch 2 taken 368450 times.
|
9323253 | while (!(keys_[bucket] == empty_key_)) { |
124 | 5800481 | Key rehash = keys_[bucket]; | |
125 | 5800481 | keys_[bucket] = empty_key_; | |
126 |
1/2✓ Branch 1 taken 5773359 times.
✗ Branch 2 not taken.
|
5800481 | DoInsert(rehash, values_[bucket], false); |
127 | 5773359 | bucket = (bucket+1) % capacity_; | |
128 | } | ||
129 |
1/2✓ Branch 1 taken 3552556 times.
✗ Branch 2 not taken.
|
3522772 | static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size |
130 | } | ||
131 | 3552737 | 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 | 84309172 | uint32_t ScaleHash(const Key &key) const { | |
164 | 84231608 | double bucket = | |
165 | 84309172 | (static_cast<double>(hasher_(key)) * static_cast<double>(capacity_) / | |
166 | static_cast<double>(static_cast<uint32_t>(-1))); | ||
167 | 84231608 | return static_cast<uint32_t>(bucket) % capacity_; | |
168 | } | ||
169 | |||
170 | 10586 | void AllocMemory() { | |
171 | 10586 | keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key))); | |
172 | 10588 | values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value))); | |
173 |
2/2✓ Branch 0 taken 57148615 times.
✓ Branch 1 taken 5348 times.
|
114048122 | for (uint32_t i = 0; i < capacity_; ++i) { |
174 | 114037534 | /*keys_[i] =*/ new (keys_ + i) Key(); | |
175 | } | ||
176 |
2/2✓ Branch 0 taken 57264823 times.
✓ Branch 1 taken 5834 times.
|
114281510 | for (uint32_t i = 0; i < capacity_; ++i) { |
177 | 114269950 | /*values_[i] =*/ new (values_ + i) Value(); | |
178 | } | ||
179 | 11560 | bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_; | |
180 | 11560 | } | |
181 | |||
182 | 10582 | void DeallocMemory(Key *k, Value *v, uint32_t c) { | |
183 |
2/2✓ Branch 0 taken 57323491 times.
✓ Branch 1 taken 5345 times.
|
114397868 | for (uint32_t i = 0; i < c; ++i) { |
184 | 114387286 | k[i].~Key(); | |
185 | } | ||
186 |
2/2✓ Branch 0 taken 57337969 times.
✓ Branch 1 taken 5345 times.
|
114426824 | for (uint32_t i = 0; i < c; ++i) { |
187 | 114416242 | v[i].~Value(); | |
188 | } | ||
189 |
2/2✓ Branch 0 taken 5344 times.
✓ Branch 1 taken 1 times.
|
10582 | if (k) |
190 | 10580 | smunmap(k); | |
191 |
2/2✓ Branch 0 taken 5344 times.
✓ Branch 1 taken 1 times.
|
10582 | if (v) |
192 | 10580 | smunmap(v); | |
193 | 10582 | k = NULL; | |
194 | 10582 | v = NULL; | |
195 | 10582 | } | |
196 | |||
197 | // Returns true iff the key is overwritten | ||
198 | 71200479 | 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 36638814 times.
✗ Branch 2 not taken.
|
71200479 | const bool overwritten = DoLookup(key, &bucket, &collisions); |
204 |
2/2✓ Branch 0 taken 30882457 times.
✓ Branch 1 taken 5756357 times.
|
71259980 | if (count_collisions) { |
205 | 60789518 | num_collisions_ += collisions; | |
206 | 60789518 | max_collisions_ = std::max(collisions, max_collisions_); | |
207 | } | ||
208 | 71191159 | keys_[bucket] = key; | |
209 |
1/2✓ Branch 1 taken 1041570 times.
✗ Branch 2 not taken.
|
71191159 | values_[bucket] = value; |
210 | 71191159 | return overwritten; | |
211 | } | ||
212 | |||
213 | 84374026 | bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const { | |
214 | 84374026 | *bucket = ScaleHash(key); | |
215 | 84195279 | *collisions = 0; | |
216 |
3/3✓ Branch 0 taken 577971900 times.
✓ Branch 1 taken 35532153 times.
✓ Branch 2 taken 8438142 times.
|
701038572 | while (!(keys_[*bucket] == empty_key_)) { |
217 |
3/3✓ Branch 0 taken 6278538 times.
✓ Branch 1 taken 573131642 times.
✓ Branch 2 taken 6298604 times.
|
630615218 | if (keys_[*bucket] == key) |
218 | 13771925 | return true; | |
219 | 616843293 | *bucket = (*bucket+1) % capacity_; | |
220 | 616843293 | (*collisions)++; | |
221 | } | ||
222 | 70423354 | return false; | |
223 | } | ||
224 | |||
225 | 10590 | void DoClear(const bool reset_capacity) { | |
226 |
2/2✓ Branch 0 taken 63 times.
✓ Branch 1 taken 5287 times.
|
10590 | if (reset_capacity) |
227 | 107 | static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size | |
228 |
2/2✓ Branch 0 taken 57330186 times.
✓ Branch 1 taken 5350 times.
|
114408536 | for (uint32_t i = 0; i < capacity_; ++i) |
229 | 114397946 | keys_[i] = empty_key_; | |
230 | 10590 | size_ = 0; | |
231 | 10590 | } | |
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 | 5880 | SmallHashDynamic() : Base() { | |
278 | 5880 | num_migrates_ = 0; | |
279 | |||
280 | // Properly set by Init | ||
281 | 5880 | threshold_grow_ = 0; | |
282 | 5880 | threshold_shrink_ = 0; | |
283 | 5880 | } | |
284 | |||
285 | SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base() | ||
286 | { | ||
287 | num_migrates_ = 0; | ||
288 | CopyFrom(other); | ||
289 | } | ||
290 | |||
291 | 1 | SmallHashDynamic<Key, Value> &operator= ( | |
292 | const SmallHashDynamic<Key, Value> &other) | ||
293 | { | ||
294 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | if (&other == this) |
295 | ✗ | return *this; | |
296 | |||
297 | 1 | CopyFrom(other); | |
298 | 1 | return *this; | |
299 | } | ||
300 | |||
301 | 1756069 | uint32_t capacity() const { return Base::capacity_; } | |
302 | 34759874 | uint32_t size() const { return Base::size_; } | |
303 | uint32_t num_migrates() const { return num_migrates_; } | ||
304 | |||
305 | protected: | ||
306 | 10402 | void SetThresholds() { | |
307 | 10402 | threshold_grow_ = | |
308 | 10402 | static_cast<uint32_t>(static_cast<double>(capacity()) * kThresholdGrow); | |
309 | 10402 | threshold_shrink_ = | |
310 | 10402 | static_cast<uint32_t>(static_cast<double>(capacity()) * kThresholdShrink); | |
311 | 10402 | } | |
312 | |||
313 | 60793628 | void Grow() { | |
314 |
2/2✓ Branch 1 taken 1520 times.
✓ Branch 2 taken 30829703 times.
|
60793628 | if (size() > threshold_grow_) |
315 | 3040 | Migrate(capacity() * 2); | |
316 | 60714332 | } | |
317 | |||
318 | 3549230 | void Shrink() { | |
319 |
2/2✓ Branch 1 taken 854699 times.
✓ Branch 2 taken 2697583 times.
|
3549230 | if (size() < threshold_shrink_) { |
320 | 854702 | uint32_t target_capacity = capacity() / 2; | |
321 |
2/2✓ Branch 0 taken 688 times.
✓ Branch 1 taken 853809 times.
|
854500 | if (target_capacity >= Base::initial_capacity_) |
322 | 688 | Migrate(target_capacity); | |
323 | } | ||
324 | 3552083 | } | |
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 | 1378 | uint32_t *ShuffleIndices(const uint32_t N) { | |
337 | uint32_t *shuffled = | ||
338 | 1378 | static_cast<uint32_t *>(smmap(N * sizeof(uint32_t))); | |
339 | // Init with identity | ||
340 |
2/2✓ Branch 0 taken 11334819 times.
✓ Branch 1 taken 689 times.
|
22671016 | for (unsigned i = 0; i < N; ++i) |
341 | 22669638 | shuffled[i] = i; | |
342 | // Shuffle (no shuffling for the last element) | ||
343 |
1/2✓ Branch 0 taken 10904108 times.
✗ Branch 1 not taken.
|
21800626 | for (unsigned i = 0; i < N-1; ++i) { |
344 | 21808216 | const uint32_t swap_idx = i + g_prng.Next(N - i); | |
345 | 21799248 | uint32_t tmp = shuffled[i]; | |
346 | 21799248 | shuffled[i] = shuffled[swap_idx]; | |
347 | 21799248 | shuffled[swap_idx] = tmp; | |
348 | } | ||
349 | 1 | return shuffled; | |
350 | } | ||
351 | |||
352 | 4416 | void Migrate(const uint32_t new_capacity) { | |
353 | 4416 | Key *old_keys = Base::keys_; | |
354 | 4416 | Value *old_values = Base::values_; | |
355 | 4416 | uint32_t old_capacity = capacity(); | |
356 | 4416 | uint32_t old_size = size(); | |
357 | |||
358 | 4418 | Base::capacity_ = new_capacity; | |
359 | 4418 | SetThresholds(); | |
360 | 4418 | 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 9774309 times.
✓ Branch 1 taken 285 times.
|
19549188 | for (uint32_t i = 0; i < old_capacity; ++i) { |
365 |
2/3✓ Branch 0 taken 2450599 times.
✓ Branch 1 taken 7323710 times.
✗ Branch 2 not taken.
|
19548618 | if (old_keys[shuffled_indices[i]] != Base::empty_key_) { |
366 | 4901198 | Base::Insert(old_keys[shuffled_indices[i]], | |
367 | 4901198 | old_values[shuffled_indices[i]]); | |
368 | } | ||
369 | } | ||
370 | 570 | smunmap(shuffled_indices); | |
371 | } else { | ||
372 |
2/2✓ Branch 0 taken 18829119 times.
✓ Branch 1 taken 1260 times.
|
37660758 | for (uint32_t i = 0; i < old_capacity; ++i) { |
373 |
3/3✓ Branch 0 taken 10500967 times.
✓ Branch 1 taken 7119687 times.
✓ Branch 2 taken 1208465 times.
|
37658238 | if (old_keys[i] != Base::empty_key_) |
374 | 28253362 | Base::Insert(old_keys[i], old_values[i]); | |
375 | } | ||
376 | } | ||
377 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2210 times.
|
3896 | assert(size() == old_size); |
378 | |||
379 | 4420 | Base::DeallocMemory(old_keys, old_values, old_capacity); | |
380 | 4420 | num_migrates_++; | |
381 | 4420 | } | |
382 | |||
383 | 1 | void CopyFrom(const SmallHashDynamic<Key, Value> &other) { | |
384 | 1 | uint32_t *shuffled_indices = ShuffleIndices(other.capacity_); | |
385 |
2/2✓ Branch 0 taken 1376256 times.
✓ Branch 1 taken 1 times.
|
1376257 | for (uint32_t i = 0; i < other.capacity_; ++i) { |
386 |
2/3✗ Branch 0 not taken.
✓ Branch 1 taken 1000000 times.
✓ Branch 2 taken 376256 times.
|
1376256 | 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 | 1 | smunmap(shuffled_indices); | |
392 | 1 | } | |
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 | 3705292 | void Insert(const Key &key, const Value &value) { | |
447 | 3705292 | uint8_t target = SelectHashmap(key); | |
448 | 3598714 | Lock(target); | |
449 | 3736270 | hashmaps_[target].Insert(key, value); | |
450 | 3555759 | Unlock(target); | |
451 | 3885190 | } | |
452 | |||
453 | 1801579 | void Erase(const Key &key) { | |
454 | 1801579 | uint8_t target = SelectHashmap(key); | |
455 | 1729022 | Lock(target); | |
456 | 1843448 | hashmaps_[target].Erase(key); | |
457 | 1683659 | Unlock(target); | |
458 | 1874463 | } | |
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 | 6495110 | inline uint8_t SelectHashmap(const Key &key) { | |
489 | 6495110 | uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37); | |
490 | 6369327 | double bucket = | |
491 | 6369327 | static_cast<double>(hash) * static_cast<double>(num_hashmaps_) / | |
492 | static_cast<double>(static_cast<uint32_t>(-1)); | ||
493 | 6369327 | return static_cast<uint32_t>(bucket) % num_hashmaps_; | |
494 | } | ||
495 | |||
496 | 6307473 | inline void Lock(const uint8_t target) { | |
497 | 6307473 | int retval = pthread_mutex_lock(&locks_[target]); | |
498 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6824074 times.
|
6824074 | assert(retval == 0); |
499 | 6824074 | } | |
500 | |||
501 | 6242662 | inline void Unlock(const uint8_t target) { | |
502 | 6242662 | int retval = pthread_mutex_unlock(&locks_[target]); | |
503 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6894719 times.
|
6894719 | assert(retval == 0); |
504 | 6894719 | } | |
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 |