Directory: | cvmfs/ |
---|---|
File: | cvmfs/smallhash.h |
Date: | 2025-07-06 02:35:01 |
Exec | Total | Coverage | |
---|---|---|---|
Lines: | 259 | 263 | 98.5% |
Branches: | 88 | 110 | 80.0% |
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 | 174814 | SmallHashBase() { | |
43 | 174814 | keys_ = NULL; | |
44 | 174814 | values_ = NULL; | |
45 | 174814 | hasher_ = NULL; | |
46 | 174814 | bytes_allocated_ = 0; | |
47 | 174814 | num_collisions_ = 0; | |
48 | 174814 | max_collisions_ = 0; | |
49 | |||
50 | // Properly initialized by Init() | ||
51 | 174814 | capacity_ = 0; | |
52 | 174814 | initial_capacity_ = 0; | |
53 | 174814 | size_ = 0; | |
54 | 174814 | } | |
55 | |||
56 | 174676 | ~SmallHashBase() { DeallocMemory(keys_, values_, capacity_); } | |
57 | |||
58 | 174754 | void Init(uint32_t expected_size, Key empty, | |
59 | uint32_t (*hasher)(const Key &key)) { | ||
60 | 174754 | hasher_ = hasher; | |
61 | 174754 | empty_key_ = empty; | |
62 | 174754 | capacity_ = static_cast<uint32_t>(static_cast<double>(expected_size) | |
63 | 174754 | / kLoadFactor); | |
64 | 174754 | initial_capacity_ = capacity_; | |
65 | 174754 | static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size | |
66 | 174754 | AllocMemory(); | |
67 | 174754 | this->DoClear(false); | |
68 | 174754 | } | |
69 | |||
70 | 95451942 | bool Lookup(const Key &key, Value *value) const { | |
71 | uint32_t bucket; | ||
72 | uint32_t collisions; | ||
73 |
1/2✓ Branch 1 taken 95429660 times.
✗ Branch 2 not taken.
|
95451942 | const bool found = DoLookup(key, &bucket, &collisions); |
74 |
2/2✓ Branch 0 taken 80297631 times.
✓ Branch 1 taken 15132029 times.
|
95556552 | if (found) |
75 |
1/2✓ Branch 1 taken 56265 times.
✗ Branch 2 not taken.
|
80339147 | *value = values_[bucket]; |
76 | 95556552 | 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 | 36 | bool LookupEx(Key *key, Value *value) const { | |
87 | 36 | uint32_t bucket = ScaleHash(*key); | |
88 |
2/2✓ Branch 1 taken 12 times.
✓ Branch 2 taken 6 times.
|
36 | while (!(keys_[bucket] == empty_key_)) { |
89 |
1/2✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
|
24 | if (keys_[bucket] == *key) { |
90 | 24 | *key = keys_[bucket]; | |
91 | 24 | *value = values_[bucket]; | |
92 | 24 | return true; | |
93 | } | ||
94 | ✗ | bucket = (bucket + 1) % capacity_; | |
95 | } | ||
96 | 12 | return false; | |
97 | } | ||
98 | |||
99 | 25061328 | bool Contains(const Key &key) const { | |
100 | uint32_t bucket; | ||
101 | uint32_t collisions; | ||
102 |
1/2✓ Branch 1 taken 25060980 times.
✗ Branch 2 not taken.
|
25061328 | const bool found = DoLookup(key, &bucket, &collisions); |
103 | 25061328 | return found; | |
104 | } | ||
105 | |||
106 | 1839154777 | void Insert(const Key &key, const Value &value) { | |
107 | 1839154777 | static_cast<Derived *>(this)->Grow(); // No-op if fixed-size | |
108 | 1832698147 | const bool overwritten = DoInsert(key, value, true); | |
109 | 1830721777 | size_ += !overwritten; // size + 1 if the key was not yet in the map | |
110 | 1830721777 | } | |
111 | |||
112 | 111794910 | bool Erase(const Key &key) { | |
113 | uint32_t bucket; | ||
114 | uint32_t collisions; | ||
115 |
1/2✓ Branch 1 taken 108629950 times.
✗ Branch 2 not taken.
|
111794910 | const bool found = DoLookup(key, &bucket, &collisions); |
116 |
1/2✓ Branch 0 taken 108642247 times.
✗ Branch 1 not taken.
|
108634290 | if (found) { |
117 | 108646356 | keys_[bucket] = empty_key_; | |
118 | 108646356 | size_--; | |
119 | 108646356 | bucket = (bucket + 1) % capacity_; | |
120 |
3/3✓ Branch 0 taken 165671134 times.
✓ Branch 1 taken 95229157 times.
✓ Branch 2 taken 14359413 times.
|
275263813 | while (!(keys_[bucket] == empty_key_)) { |
121 | 168052297 | Key rehash = keys_[bucket]; | |
122 | 168052297 | keys_[bucket] = empty_key_; | |
123 |
1/2✓ Branch 1 taken 166617457 times.
✗ Branch 2 not taken.
|
168052297 | DoInsert(rehash, values_[bucket], false); |
124 | 166617457 | bucket = (bucket + 1) % capacity_; | |
125 | } | ||
126 |
1/2✓ Branch 1 taken 108871623 times.
✗ Branch 2 not taken.
|
107211516 | static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size |
127 | } | ||
128 | 108892140 | return found; | |
129 | } | ||
130 | |||
131 | 1493 | void Clear() { DoClear(true); } | |
132 | |||
133 | 5078 | uint64_t bytes_allocated() const { return bytes_allocated_; } | |
134 | 1440 | static double GetEntrySize() { | |
135 | 2880 | const double unit = sizeof(Key) + sizeof(Value); | |
136 | 2880 | 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 | 227628 | Key empty_key() const { return empty_key_; } | |
148 | 481092 | Key *keys() const { return keys_; } | |
149 | 234 | 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 | 2535499353 | uint32_t ScaleHash(const Key &key) const { | |
156 | 2535499353 | const double bucket = (static_cast<double>(hasher_(key)) | |
157 | 2522447493 | * static_cast<double>(capacity_) | |
158 | / static_cast<double>(static_cast<uint32_t>(-1))); | ||
159 | 2522447493 | return static_cast<uint32_t>(bucket) % capacity_; | |
160 | } | ||
161 | |||
162 | 310292 | void AllocMemory() { | |
163 | 310292 | keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key))); | |
164 | 310472 | values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value))); | |
165 |
2/2✓ Branch 0 taken 1664912532 times.
✓ Branch 1 taken 156211 times.
|
3322792472 | for (uint32_t i = 0; i < capacity_; ++i) { |
166 | 3322482000 | /*keys_[i] =*/new (keys_ + i) Key(); | |
167 | } | ||
168 |
2/2✓ Branch 0 taken 1669041432 times.
✓ Branch 1 taken 140341 times.
|
3331018532 | for (uint32_t i = 0; i < capacity_; ++i) { |
169 | 3330739800 | /*values_[i] =*/new (values_ + i) Value(); | |
170 | } | ||
171 | 278732 | bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_; | |
172 | 278732 | } | |
173 | |||
174 | 310394 | void DeallocMemory(Key *k, Value *v, uint32_t c) { | |
175 |
2/2✓ Branch 0 taken 1670373144 times.
✓ Branch 1 taken 156171 times.
|
3333716348 | for (uint32_t i = 0; i < c; ++i) { |
176 | 3333405954 | k[i].~Key(); | |
177 | } | ||
178 |
2/2✓ Branch 0 taken 1669210224 times.
✓ Branch 1 taken 156171 times.
|
3331390508 | for (uint32_t i = 0; i < c; ++i) { |
179 | 3331080114 | v[i].~Value(); | |
180 | } | ||
181 |
2/2✓ Branch 0 taken 156141 times.
✓ Branch 1 taken 30 times.
|
310394 | if (k) |
182 | 310334 | smunmap(k); | |
183 |
2/2✓ Branch 0 taken 156141 times.
✓ Branch 1 taken 30 times.
|
310394 | if (v) |
184 | 310334 | smunmap(v); | |
185 | 310394 | k = NULL; | |
186 | 310394 | v = NULL; | |
187 | 310394 | } | |
188 | |||
189 | // Returns true iff the key is overwritten | ||
190 | 2141057462 | 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 1096887006 times.
✗ Branch 2 not taken.
|
2141057462 | const bool overwritten = DoLookup(key, &bucket, &collisions); |
195 |
2/2✓ Branch 0 taken 930654509 times.
✓ Branch 1 taken 166232497 times.
|
2138837972 | if (count_collisions) { |
196 | 1832431117 | num_collisions_ += collisions; | |
197 | 1832431117 | max_collisions_ = std::max(collisions, max_collisions_); | |
198 | } | ||
199 | 2137580852 | keys_[bucket] = key; | |
200 |
1/2✓ Branch 1 taken 26045898 times.
✗ Branch 2 not taken.
|
2137580852 | values_[bucket] = value; |
201 | 2137580852 | return overwritten; | |
202 | } | ||
203 | |||
204 | 2530576917 | bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const { | |
205 | 2530576917 | *bucket = ScaleHash(key); | |
206 | 2521078977 | *collisions = 0; | |
207 |
3/3✓ Branch 0 taken 14649543361 times.
✓ Branch 1 taken 1051714313 times.
✓ Branch 2 taken 259807544 times.
|
18332370709 | while (!(keys_[*bucket] == empty_key_)) { |
208 |
3/3✓ Branch 0 taken 186835896 times.
✓ Branch 1 taken 14503832652 times.
✓ Branch 2 taken 185347357 times.
|
16218259970 | if (keys_[*bucket] == key) |
209 | 406968238 | return true; | |
210 | 15811291732 | *bucket = (*bucket + 1) % capacity_; | |
211 | 15811291732 | (*collisions)++; | |
212 | } | ||
213 | 2114110739 | return false; | |
214 | } | ||
215 | |||
216 | 310526 | void DoClear(const bool reset_capacity) { | |
217 |
2/2✓ Branch 0 taken 1493 times.
✓ Branch 1 taken 154772 times.
|
310526 | if (reset_capacity) |
218 | 2813 | static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size | |
219 |
2/2✓ Branch 0 taken 1670090322 times.
✓ Branch 1 taken 156265 times.
|
3333074396 | for (uint32_t i = 0; i < capacity_; ++i) |
220 | 3332763870 | keys_[i] = empty_key_; | |
221 | 310526 | size_ = 0; | |
222 | 310526 | } | |
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 | 5024 | void SetThresholds() { } | |
252 | 664079 | void Grow() { } | |
253 | 28474 | void Shrink() { } | |
254 | 54 | 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 | 169790 | SmallHashDynamic() : Base() { | |
269 | 169790 | num_migrates_ = 0; | |
270 | |||
271 | // Properly set by Init | ||
272 | 169790 | threshold_grow_ = 0; | |
273 | 169790 | threshold_shrink_ = 0; | |
274 | 169790 | } | |
275 | |||
276 | SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base() { | ||
277 | num_migrates_ = 0; | ||
278 | CopyFrom(other); | ||
279 | } | ||
280 | |||
281 | 246 | SmallHashDynamic<Key, Value> &operator=( | |
282 | const SmallHashDynamic<Key, Value> &other) { | ||
283 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 138 times.
|
246 | if (&other == this) |
284 | ✗ | return *this; | |
285 | |||
286 | 246 | CopyFrom(other); | |
287 | 246 | return *this; | |
288 | } | ||
289 | |||
290 | 59676951 | uint32_t capacity() const { return Base::capacity_; } | |
291 | 1053942796 | uint32_t size() const { return Base::size_; } | |
292 | uint32_t num_migrates() const { return num_migrates_; } | ||
293 | |||
294 | protected: | ||
295 | 305268 | void SetThresholds() { | |
296 | 305268 | threshold_grow_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
297 | 305328 | * kThresholdGrow); | |
298 | 305328 | threshold_shrink_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
299 | 305328 | * kThresholdShrink); | |
300 | 305328 | } | |
301 | |||
302 | 1836319514 | void Grow() { | |
303 |
2/2✓ Branch 1 taken 45778 times.
✓ Branch 2 taken 930754472 times.
|
1836319514 | if (size() > threshold_grow_) |
304 | 91556 | Migrate(capacity() * 2); | |
305 | 1833412454 | } | |
306 | |||
307 | 108406862 | void Shrink() { | |
308 |
2/2✓ Branch 1 taken 29090304 times.
✓ Branch 2 taken 79529829 times.
|
108406862 | if (size() < threshold_shrink_) { |
309 | 29094413 | const uint32_t target_capacity = capacity() / 2; | |
310 |
2/2✓ Branch 0 taken 20610 times.
✓ Branch 1 taken 29066034 times.
|
29090753 | if (target_capacity >= Base::initial_capacity_) |
311 | 20610 | Migrate(target_capacity); | |
312 | } | ||
313 | 108620612 | } | |
314 | |||
315 | 2759 | void ResetCapacity() { | |
316 | 2759 | Base::DeallocMemory(Base::keys_, Base::values_, Base::capacity_); | |
317 | 2759 | Base::capacity_ = Base::initial_capacity_; | |
318 | 2759 | Base::AllocMemory(); | |
319 | 2759 | SetThresholds(); | |
320 | 2759 | } | |
321 | |||
322 | private: | ||
323 | // Returns a random permutation of indices [0..N-1] that is allocated | ||
324 | // by smmap (Knuth's shuffle algorithm) | ||
325 | 41556 | uint32_t *ShuffleIndices(const uint32_t N) { | |
326 | 41556 | uint32_t *shuffled = static_cast<uint32_t *>(smmap(N * sizeof(uint32_t))); | |
327 | // Init with identity | ||
328 |
2/2✓ Branch 0 taken 335418108 times.
✓ Branch 1 taken 20778 times.
|
670877772 | for (unsigned i = 0; i < N; ++i) |
329 | 670836216 | shuffled[i] = i; | |
330 | // Shuffle (no shuffling for the last element) | ||
331 |
1/2✓ Branch 0 taken 315831210 times.
✗ Branch 1 not taken.
|
631651896 | for (unsigned i = 0; i < N - 1; ++i) { |
332 | 631662420 | const uint32_t swap_idx = i + g_prng.Next(N - i); | |
333 | 631610340 | const uint32_t tmp = shuffled[i]; | |
334 | 631610340 | shuffled[i] = shuffled[swap_idx]; | |
335 | 631610340 | shuffled[swap_idx] = tmp; | |
336 | } | ||
337 | 246 | return shuffled; | |
338 | } | ||
339 | |||
340 | 132836 | void Migrate(const uint32_t new_capacity) { | |
341 | 132836 | Key *old_keys = Base::keys_; | |
342 | 132836 | Value *old_values = Base::values_; | |
343 | 132836 | const uint32_t old_capacity = capacity(); | |
344 | 132836 | const uint32_t old_size = size(); | |
345 | |||
346 | 132776 | Base::capacity_ = new_capacity; | |
347 | 132776 | SetThresholds(); | |
348 | 132776 | Base::AllocMemory(); | |
349 | 132956 | Base::DoClear(false); | |
350 |
2/2✓ Branch 0 taken 20640 times.
✓ Branch 1 taken 45838 times.
|
132956 | if (new_capacity < old_capacity) { |
351 | 41280 | uint32_t *shuffled_indices = ShuffleIndices(old_capacity); | |
352 |
1/2✓ Branch 0 taken 289268130 times.
✗ Branch 1 not taken.
|
578534880 | for (uint32_t i = 0; i < old_capacity; ++i) { |
353 |
2/3✓ Branch 0 taken 72577890 times.
✓ Branch 1 taken 216690240 times.
✗ Branch 2 not taken.
|
578536260 | if (old_keys[shuffled_indices[i]] != Base::empty_key_) { |
354 | 145155780 | Base::Insert(old_keys[shuffled_indices[i]], | |
355 | 145155780 | old_values[shuffled_indices[i]]); | |
356 | } | ||
357 | } | ||
358 | ✗ | smunmap(shuffled_indices); | |
359 | } else { | ||
360 |
2/2✓ Branch 0 taken 570447315 times.
✓ Branch 1 taken 29578 times.
|
1140953786 | for (uint32_t i = 0; i < old_capacity; ++i) { |
361 |
3/3✓ Branch 0 taken 314511272 times.
✓ Branch 1 taken 218110798 times.
✓ Branch 2 taken 37825245 times.
|
1140894630 | if (old_keys[i] != Base::empty_key_) |
362 | 855994066 | Base::Insert(old_keys[i], old_values[i]); | |
363 | } | ||
364 | } | ||
365 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 66478 times.
|
100436 | assert(size() == old_size); |
366 | |||
367 | 132956 | Base::DeallocMemory(old_keys, old_values, old_capacity); | |
368 | 132956 | num_migrates_++; | |
369 | 132956 | } | |
370 | |||
371 | 246 | void CopyFrom(const SmallHashDynamic<Key, Value> &other) { | |
372 | 246 | uint32_t *shuffled_indices = ShuffleIndices(other.capacity_); | |
373 |
2/2✓ Branch 0 taken 41289948 times.
✓ Branch 1 taken 138 times.
|
41292462 | for (uint32_t i = 0; i < other.capacity_; ++i) { |
374 |
2/3✗ Branch 0 not taken.
✓ Branch 1 taken 30001134 times.
✓ Branch 2 taken 11288814 times.
|
41292216 | if (other.keys_[shuffled_indices[i]] != other.empty_key_) { |
375 | 30000000 | this->Insert(other.keys_[shuffled_indices[i]], | |
376 | 30000000 | other.values_[shuffled_indices[i]]); | |
377 | } | ||
378 | } | ||
379 | 246 | smunmap(shuffled_indices); | |
380 | 246 | } | |
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 | 300 | MultiHash() { | |
397 | 300 | num_hashmaps_ = 0; | |
398 | 300 | hashmaps_ = NULL; | |
399 | 300 | locks_ = NULL; | |
400 | 300 | } | |
401 | |||
402 | 300 | 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 300 times.
|
300 | assert(num_hashmaps > 0); |
405 | 300 | const uint8_t N = num_hashmaps; | |
406 | 300 | num_hashmaps_ = N; | |
407 |
3/4✓ Branch 2 taken 12600 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 12600 times.
✓ Branch 5 taken 300 times.
|
12900 | hashmaps_ = new SmallHashDynamic<Key, Value>[N](); |
408 | 300 | locks_ = static_cast<pthread_mutex_t *>( | |
409 | 300 | smalloc(N * sizeof(pthread_mutex_t))); | |
410 |
2/2✓ Branch 0 taken 12600 times.
✓ Branch 1 taken 300 times.
|
12900 | for (uint8_t i = 0; i < N; ++i) { |
411 | 12600 | int retval = pthread_mutex_init(&locks_[i], NULL); | |
412 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 12600 times.
|
12600 | assert(retval == 0); |
413 | 12600 | hashmaps_[i].Init(128, empty_key, hasher); | |
414 | } | ||
415 | 300 | } | |
416 | |||
417 | 300 | ~MultiHash() { | |
418 |
2/2✓ Branch 0 taken 12600 times.
✓ Branch 1 taken 300 times.
|
12900 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
419 | 12600 | pthread_mutex_destroy(&locks_[i]); | |
420 | } | ||
421 | 300 | free(locks_); | |
422 |
3/4✓ Branch 0 taken 300 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12600 times.
✓ Branch 3 taken 300 times.
|
12900 | delete[] hashmaps_; |
423 | 300 | } | |
424 | |||
425 | 30000000 | bool Lookup(const Key &key, Value *value) { | |
426 | 30000000 | uint8_t target = SelectHashmap(key); | |
427 | 30000000 | Lock(target); | |
428 | 30000000 | const bool result = hashmaps_[target].Lookup(key, value); | |
429 | 30000000 | Unlock(target); | |
430 | 30000000 | return result; | |
431 | } | ||
432 | |||
433 | 111979590 | void Insert(const Key &key, const Value &value) { | |
434 | 111979590 | uint8_t target = SelectHashmap(key); | |
435 | 111964170 | Lock(target); | |
436 | 113487510 | hashmaps_[target].Insert(key, value); | |
437 | 106842900 | Unlock(target); | |
438 | 116718420 | } | |
439 | |||
440 | 53869350 | void Erase(const Key &key) { | |
441 | 53869350 | uint8_t target = SelectHashmap(key); | |
442 | 51519750 | Lock(target); | |
443 | 55314930 | hashmaps_[target].Erase(key); | |
444 | 49549140 | Unlock(target); | |
445 | 55884960 | } | |
446 | |||
447 | 30 | void Clear() { | |
448 |
2/2✓ Branch 0 taken 1260 times.
✓ Branch 1 taken 30 times.
|
1290 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
449 | 1260 | Lock(i); | |
450 |
2/2✓ Branch 0 taken 1260 times.
✓ Branch 1 taken 30 times.
|
1290 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
451 | 1260 | hashmaps_[i].Clear(); | |
452 |
2/2✓ Branch 0 taken 1260 times.
✓ Branch 1 taken 30 times.
|
1290 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
453 | 1260 | Unlock(i); | |
454 | 30 | } | |
455 | |||
456 | 300 | uint8_t num_hashmaps() const { return num_hashmaps_; } | |
457 | |||
458 | 240 | void GetSizes(uint32_t *sizes) { | |
459 |
2/2✓ Branch 0 taken 10080 times.
✓ Branch 1 taken 240 times.
|
10320 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
460 | 10080 | Lock(i); | |
461 | 10080 | sizes[i] = hashmaps_[i].size(); | |
462 | 10080 | Unlock(i); | |
463 | } | ||
464 | 240 | } | |
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 | 194455140 | inline uint8_t SelectHashmap(const Key &key) { | |
476 | 194455140 | uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37); | |
477 | 191301690 | double bucket = static_cast<double>(hash) | |
478 | 191301690 | * static_cast<double>(num_hashmaps_) | |
479 | / static_cast<double>(static_cast<uint32_t>(-1)); | ||
480 | 191301690 | return static_cast<uint32_t>(bucket) % num_hashmaps_; | |
481 | } | ||
482 | |||
483 | 193757070 | inline void Lock(const uint8_t target) { | |
484 | 193757070 | int retval = pthread_mutex_lock(&locks_[target]); | |
485 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 206072040 times.
|
206072040 | assert(retval == 0); |
486 | 206072040 | } | |
487 | |||
488 | 186754980 | inline void Unlock(const uint8_t target) { | |
489 | 186754980 | int retval = pthread_mutex_unlock(&locks_[target]); | |
490 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 206340870 times.
|
206340870 | assert(retval == 0); |
491 | 206340870 | } | |
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 |