Directory: | cvmfs/ |
---|---|
File: | cvmfs/smallhash.h |
Date: | 2025-10-19 02:35:28 |
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 "duplex_testing.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 | 168670 | SmallHashBase() { | |
43 | 168670 | keys_ = NULL; | |
44 | 168670 | values_ = NULL; | |
45 | 168670 | hasher_ = NULL; | |
46 | 168670 | bytes_allocated_ = 0; | |
47 | 168670 | num_collisions_ = 0; | |
48 | 168670 | max_collisions_ = 0; | |
49 | |||
50 | // Properly initialized by Init() | ||
51 | 168670 | capacity_ = 0; | |
52 | 168670 | initial_capacity_ = 0; | |
53 | 168670 | size_ = 0; | |
54 | 168670 | } | |
55 | |||
56 | 168532 | ~SmallHashBase() { DeallocMemory(keys_, values_, capacity_); } | |
57 | |||
58 | 168608 | void Init(uint32_t expected_size, Key empty, | |
59 | uint32_t (*hasher)(const Key &key)) { | ||
60 | 168608 | hasher_ = hasher; | |
61 | 168608 | empty_key_ = empty; | |
62 | 168608 | capacity_ = static_cast<uint32_t>(static_cast<double>(expected_size) | |
63 | 168608 | / kLoadFactor); | |
64 | 168608 | initial_capacity_ = capacity_; | |
65 | 168608 | static_cast<Derived *>(this)->SetThresholds(); // No-op for fixed size | |
66 | 168608 | AllocMemory(); | |
67 | 168608 | this->DoClear(false); | |
68 | 168608 | } | |
69 | |||
70 | 68338307 | bool Lookup(const Key &key, Value *value) const { | |
71 | uint32_t bucket; | ||
72 | uint32_t collisions; | ||
73 |
1/2✓ Branch 1 taken 68210426 times.
✗ Branch 2 not taken.
|
68338307 | const bool found = DoLookup(key, &bucket, &collisions); |
74 |
2/2✓ Branch 0 taken 65939965 times.
✓ Branch 1 taken 2270461 times.
|
68348595 | if (found) |
75 |
1/2✓ Branch 1 taken 81733 times.
✗ Branch 2 not taken.
|
65985148 | *value = values_[bucket]; |
76 | 68348595 | 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 | 12 | bool LookupEx(Key *key, Value *value) const { | |
87 | 12 | uint32_t bucket = ScaleHash(*key); | |
88 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
|
12 | while (!(keys_[bucket] == empty_key_)) { |
89 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
8 | if (keys_[bucket] == *key) { |
90 | 8 | *key = keys_[bucket]; | |
91 | 8 | *value = values_[bucket]; | |
92 | 8 | return true; | |
93 | } | ||
94 | ✗ | bucket = (bucket + 1) % capacity_; | |
95 | } | ||
96 | 4 | return false; | |
97 | } | ||
98 | |||
99 | 40066401 | bool Contains(const Key &key) const { | |
100 | uint32_t bucket; | ||
101 | uint32_t collisions; | ||
102 |
1/2✓ Branch 1 taken 40066032 times.
✗ Branch 2 not taken.
|
40066401 | const bool found = DoLookup(key, &bucket, &collisions); |
103 | 40066401 | return found; | |
104 | } | ||
105 | |||
106 | 1902394366 | void Insert(const Key &key, const Value &value) { | |
107 | 1902394366 | static_cast<Derived *>(this)->Grow(); // No-op if fixed-size | |
108 | 1896697696 | const bool overwritten = DoInsert(key, value, true); | |
109 | 1893987358 | size_ += !overwritten; // size + 1 if the key was not yet in the map | |
110 | 1893987358 | } | |
111 | |||
112 | 102206151 | bool Erase(const Key &key) { | |
113 | uint32_t bucket; | ||
114 | uint32_t collisions; | ||
115 |
1/2✓ Branch 1 taken 98556535 times.
✗ Branch 2 not taken.
|
102206151 | const bool found = DoLookup(key, &bucket, &collisions); |
116 |
1/2✓ Branch 0 taken 98566527 times.
✗ Branch 1 not taken.
|
98561914 | if (found) { |
117 | 98571580 | keys_[bucket] = empty_key_; | |
118 | 98571580 | size_--; | |
119 | 98571580 | bucket = (bucket + 1) % capacity_; | |
120 |
3/3✓ Branch 0 taken 183918452 times.
✓ Branch 1 taken 85198444 times.
✓ Branch 2 taken 14728781 times.
|
283850730 | while (!(keys_[bucket] == empty_key_)) { |
121 | 186462978 | Key rehash = keys_[bucket]; | |
122 | 186462978 | keys_[bucket] = empty_key_; | |
123 |
1/2✓ Branch 1 taken 185279150 times.
✗ Branch 2 not taken.
|
186462978 | DoInsert(rehash, values_[bucket], false); |
124 | 185279150 | bucket = (bucket + 1) % capacity_; | |
125 | } | ||
126 |
1/2✓ Branch 1 taken 99906135 times.
✗ Branch 2 not taken.
|
97387752 | static_cast<Derived *>(this)->Shrink(); // No-op if fixed-size |
127 | } | ||
128 | 99944475 | return found; | |
129 | } | ||
130 | |||
131 | 1799 | void Clear() { DoClear(true); } | |
132 | |||
133 | 7000 | uint64_t bytes_allocated() const { return bytes_allocated_; } | |
134 | 2073 | static double GetEntrySize() { | |
135 | 4146 | const double unit = sizeof(Key) + sizeof(Value); | |
136 | 4146 | 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 | 246026 | Key empty_key() const { return empty_key_; } | |
148 | 534400 | Key *keys() const { return keys_; } | |
149 | 239 | 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 | 2612878730 | uint32_t ScaleHash(const Key &key) const { | |
156 | 2612878730 | const double bucket = (static_cast<double>(hasher_(key)) | |
157 | 2603682854 | * static_cast<double>(capacity_) | |
158 | / static_cast<double>(static_cast<uint32_t>(-1))); | ||
159 | 2603682854 | return static_cast<uint32_t>(bucket) % capacity_; | |
160 | } | ||
161 | |||
162 | 309026 | void AllocMemory() { | |
163 | 309026 | keys_ = static_cast<Key *>(smmap(capacity_ * sizeof(Key))); | |
164 | 309150 | values_ = static_cast<Value *>(smmap(capacity_ * sizeof(Value))); | |
165 |
2/2✓ Branch 0 taken 1914225974 times.
✓ Branch 1 taken 156165 times.
|
3818590798 | for (uint32_t i = 0; i < capacity_; ++i) { |
166 | 3818281648 | /*keys_[i] =*/new (keys_ + i) Key(); | |
167 | } | ||
168 |
2/2✓ Branch 0 taken 1914208366 times.
✓ Branch 1 taken 104798 times.
|
3818452848 | for (uint32_t i = 0; i < capacity_; ++i) { |
169 | 3818246432 | /*values_[i] =*/new (values_ + i) Value(); | |
170 | } | ||
171 | 206416 | bytes_allocated_ = (sizeof(Key) + sizeof(Value)) * capacity_; | |
172 | 206416 | } | |
173 | |||
174 | 309074 | void DeallocMemory(Key *k, Value *v, uint32_t c) { | |
175 |
2/2✓ Branch 0 taken 1918766633 times.
✓ Branch 1 taken 156126 times.
|
3827674770 | for (uint32_t i = 0; i < c; ++i) { |
176 | 3827365696 | k[i].~Key(); | |
177 | } | ||
178 |
2/2✓ Branch 0 taken 1919341900 times.
✓ Branch 1 taken 156126 times.
|
3828825304 | for (uint32_t i = 0; i < c; ++i) { |
179 | 3828516230 | v[i].~Value(); | |
180 | } | ||
181 |
2/2✓ Branch 0 taken 156095 times.
✓ Branch 1 taken 31 times.
|
309074 | if (k) |
182 | 309012 | smunmap(k); | |
183 |
2/2✓ Branch 0 taken 156095 times.
✓ Branch 1 taken 31 times.
|
309074 | if (v) |
184 | 309012 | smunmap(v); | |
185 | 309074 | k = NULL; | |
186 | 309074 | v = NULL; | |
187 | 309074 | } | |
188 | |||
189 | // Returns true iff the key is overwritten | ||
190 | 2227301564 | 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 1133812834 times.
✗ Branch 2 not taken.
|
2227301564 | const bool overwritten = DoLookup(key, &bucket, &collisions); |
195 |
2/2✓ Branch 0 taken 949222289 times.
✓ Branch 1 taken 184590545 times.
|
2223331520 | if (count_collisions) { |
196 | 1893746008 | num_collisions_ += collisions; | |
197 | 1893746008 | max_collisions_ = std::max(collisions, max_collisions_); | |
198 | } | ||
199 | 2223393792 | keys_[bucket] = key; | |
200 |
1/2✓ Branch 1 taken 39579506 times.
✗ Branch 2 not taken.
|
2223393792 | values_[bucket] = value; |
201 | 2223393792 | return overwritten; | |
202 | } | ||
203 | |||
204 | 2614955056 | bool DoLookup(const Key &key, uint32_t *bucket, uint32_t *collisions) const { | |
205 | 2614955056 | *bucket = ScaleHash(key); | |
206 | 2602292130 | *collisions = 0; | |
207 |
3/3✓ Branch 0 taken 21644649011 times.
✓ Branch 1 taken 1122836084 times.
✓ Branch 2 taken 282361742 times.
|
25560353496 | while (!(keys_[*bucket] == empty_key_)) { |
208 |
3/3✓ Branch 0 taken 150930354 times.
✓ Branch 1 taken 21549967776 times.
✓ Branch 2 taken 228802092 times.
|
23363957627 | if (keys_[*bucket] == key) |
209 | 405896261 | return true; | |
210 | 22958061366 | *bucket = (*bucket + 1) % capacity_; | |
211 | 22958061366 | (*collisions)++; | |
212 | } | ||
213 | 2196395869 | return false; | |
214 | } | ||
215 | |||
216 | 309226 | void DoClear(const bool reset_capacity) { | |
217 |
2/2✓ Branch 0 taken 1799 times.
✓ Branch 1 taken 154442 times.
|
309226 | if (reset_capacity) |
218 | 3165 | static_cast<Derived *>(this)->ResetCapacity(); // No-op if fixed-size | |
219 |
2/2✓ Branch 0 taken 1915660606 times.
✓ Branch 1 taken 156241 times.
|
3821356398 | for (uint32_t i = 0; i < capacity_; ++i) |
220 | 3821047172 | keys_[i] = empty_key_; | |
221 | 309226 | size_ = 0; | |
222 | 309226 | } | |
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 | 6924 | void SetThresholds() { } | |
252 | 627154 | void Grow() { } | |
253 | 42953 | void Shrink() { } | |
254 | 76 | 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 | 161746 | SmallHashDynamic() : Base() { | |
269 | 161746 | num_migrates_ = 0; | |
270 | |||
271 | // Properly set by Init | ||
272 | 161746 | threshold_grow_ = 0; | |
273 | 161746 | threshold_shrink_ = 0; | |
274 | 161746 | } | |
275 | |||
276 | SmallHashDynamic(const SmallHashDynamic<Key, Value> &other) : Base() { | ||
277 | num_migrates_ = 0; | ||
278 | CopyFrom(other); | ||
279 | } | ||
280 | |||
281 | 351 | SmallHashDynamic<Key, Value> &operator=( | |
282 | const SmallHashDynamic<Key, Value> &other) { | ||
283 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 191 times.
|
351 | if (&other == this) |
284 | ✗ | return *this; | |
285 | |||
286 | 351 | CopyFrom(other); | |
287 | 351 | return *this; | |
288 | } | ||
289 | |||
290 | 34995367 | uint32_t capacity() const { return Base::capacity_; } | |
291 | 1064691529 | uint32_t size() const { return Base::size_; } | |
292 | uint32_t num_migrates() const { return num_migrates_; } | ||
293 | |||
294 | protected: | ||
295 | 302102 | void SetThresholds() { | |
296 | 302102 | threshold_grow_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
297 | 302102 | * kThresholdGrow); | |
298 | 302102 | threshold_shrink_ = static_cast<uint32_t>(static_cast<double>(capacity()) | |
299 | 302102 | * kThresholdShrink); | |
300 | 302102 | } | |
301 | |||
302 | 1898791833 | void Grow() { | |
303 |
2/2✓ Branch 1 taken 47305 times.
✓ Branch 2 taken 950246414 times.
|
1898791833 | if (size() > threshold_grow_) |
304 | 94610 | Migrate(capacity() * 2); | |
305 | 1896519989 | } | |
306 | |||
307 | 98843121 | void Shrink() { | |
308 |
2/2✓ Branch 1 taken 16709678 times.
✓ Branch 2 taken 82354216 times.
|
98843121 | if (size() < threshold_shrink_) { |
309 | 16714731 | const uint32_t target_capacity = capacity() / 2; | |
310 |
2/2✓ Branch 0 taken 21297 times.
✓ Branch 1 taken 16688778 times.
|
16715128 | if (target_capacity >= Base::initial_capacity_) |
311 | 21297 | Migrate(target_capacity); | |
312 | } | ||
313 | 99069375 | } | |
314 | |||
315 | 3089 | void ResetCapacity() { | |
316 | 3089 | Base::DeallocMemory(Base::keys_, Base::values_, Base::capacity_); | |
317 | 3089 | Base::capacity_ = Base::initial_capacity_; | |
318 | 3089 | Base::AllocMemory(); | |
319 | 3089 | SetThresholds(); | |
320 | 3089 | } | |
321 | |||
322 | private: | ||
323 | // Returns a random permutation of indices [0..N-1] that is allocated | ||
324 | // by smmap (Knuth's shuffle algorithm) | ||
325 | 43038 | uint32_t *ShuffleIndices(const uint32_t N) { | |
326 | 43038 | uint32_t *shuffled = static_cast<uint32_t *>(smmap(N * sizeof(uint32_t))); | |
327 | // Init with identity | ||
328 |
2/2✓ Branch 0 taken 350508363 times.
✓ Branch 1 taken 21519 times.
|
701059764 | for (unsigned i = 0; i < N; ++i) |
329 | 701016726 | shuffled[i] = i; | |
330 | // Shuffle (no shuffling for the last element) | ||
331 |
1/2✓ Branch 0 taken 336517965 times.
✗ Branch 1 not taken.
|
672439872 | for (unsigned i = 0; i < N - 1; ++i) { |
332 | 673035930 | const uint32_t swap_idx = i + g_prng.Next(N - i); | |
333 | 672396834 | const uint32_t tmp = shuffled[i]; | |
334 | 672396834 | shuffled[i] = shuffled[swap_idx]; | |
335 | 672396834 | shuffled[swap_idx] = tmp; | |
336 | } | ||
337 | 351 | return shuffled; | |
338 | } | ||
339 | |||
340 | 137266 | void Migrate(const uint32_t new_capacity) { | |
341 | 137266 | Key *old_keys = Base::keys_; | |
342 | 137266 | Value *old_values = Base::values_; | |
343 | 137266 | const uint32_t old_capacity = capacity(); | |
344 | 137266 | const uint32_t old_size = size(); | |
345 | |||
346 | 137328 | Base::capacity_ = new_capacity; | |
347 | 137328 | SetThresholds(); | |
348 | 137328 | Base::AllocMemory(); | |
349 | 137452 | Base::DoClear(false); | |
350 |
2/2✓ Branch 0 taken 21328 times.
✓ Branch 1 taken 47398 times.
|
137452 | if (new_capacity < old_capacity) { |
351 | 42656 | uint32_t *shuffled_indices = ShuffleIndices(old_capacity); | |
352 |
1/2✓ Branch 0 taken 299583628 times.
✗ Branch 1 not taken.
|
599059562 | for (uint32_t i = 0; i < old_capacity; ++i) { |
353 |
2/3✓ Branch 0 taken 75179154 times.
✓ Branch 1 taken 224404474 times.
✗ Branch 2 not taken.
|
599167256 | if (old_keys[shuffled_indices[i]] != Base::empty_key_) { |
354 | 150358308 | Base::Insert(old_keys[shuffled_indices[i]], | |
355 | 150358308 | old_values[shuffled_indices[i]]); | |
356 | } | ||
357 | } | ||
358 | ✗ | smunmap(shuffled_indices); | |
359 | } else { | ||
360 |
2/2✓ Branch 0 taken 589563825 times.
✓ Branch 1 taken 31836 times.
|
1179191322 | for (uint32_t i = 0; i < old_capacity; ++i) { |
361 |
3/3✓ Branch 0 taken 325169366 times.
✓ Branch 1 taken 225357761 times.
✓ Branch 2 taken 39036698 times.
|
1179127650 | if (old_keys[i] != Base::empty_key_) |
362 | 884579772 | Base::Insert(old_keys[i], old_values[i]); | |
363 | } | ||
364 | } | ||
365 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 68726 times.
|
106328 | assert(size() == old_size); |
366 | |||
367 | 137452 | Base::DeallocMemory(old_keys, old_values, old_capacity); | |
368 | 137452 | num_migrates_++; | |
369 | 137452 | } | |
370 | |||
371 | 351 | void CopyFrom(const SmallHashDynamic<Key, Value> &other) { | |
372 | 351 | uint32_t *shuffled_indices = ShuffleIndices(other.capacity_); | |
373 |
2/2✓ Branch 0 taken 42667296 times.
✓ Branch 1 taken 191 times.
|
42671007 | for (uint32_t i = 0; i < other.capacity_; ++i) { |
374 |
2/3✗ Branch 0 not taken.
✓ Branch 1 taken 31001680 times.
✓ Branch 2 taken 11665616 times.
|
42670656 | if (other.keys_[shuffled_indices[i]] != other.empty_key_) { |
375 | 31000000 | this->Insert(other.keys_[shuffled_indices[i]], | |
376 | 31000000 | other.values_[shuffled_indices[i]]); | |
377 | } | ||
378 | } | ||
379 | 351 | smunmap(shuffled_indices); | |
380 | 351 | } | |
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 | 310 | MultiHash() { | |
397 | 310 | num_hashmaps_ = 0; | |
398 | 310 | hashmaps_ = NULL; | |
399 | 310 | locks_ = NULL; | |
400 | 310 | } | |
401 | |||
402 | 310 | 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 310 times.
|
310 | assert(num_hashmaps > 0); |
405 | 310 | const uint8_t N = num_hashmaps; | |
406 | 310 | num_hashmaps_ = N; | |
407 |
3/4✓ Branch 2 taken 13020 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 13020 times.
✓ Branch 5 taken 310 times.
|
13330 | hashmaps_ = new SmallHashDynamic<Key, Value>[N](); |
408 | 310 | locks_ = static_cast<pthread_mutex_t *>( | |
409 | 310 | smalloc(N * sizeof(pthread_mutex_t))); | |
410 |
2/2✓ Branch 0 taken 13020 times.
✓ Branch 1 taken 310 times.
|
13330 | for (uint8_t i = 0; i < N; ++i) { |
411 | 13020 | int retval = pthread_mutex_init(&locks_[i], NULL); | |
412 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 13020 times.
|
13020 | assert(retval == 0); |
413 | 13020 | hashmaps_[i].Init(128, empty_key, hasher); | |
414 | } | ||
415 | 310 | } | |
416 | |||
417 | 310 | ~MultiHash() { | |
418 |
2/2✓ Branch 0 taken 13020 times.
✓ Branch 1 taken 310 times.
|
13330 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
419 | 13020 | pthread_mutex_destroy(&locks_[i]); | |
420 | } | ||
421 | 310 | free(locks_); | |
422 |
3/4✓ Branch 0 taken 310 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 13020 times.
✓ Branch 3 taken 310 times.
|
13330 | delete[] hashmaps_; |
423 | 310 | } | |
424 | |||
425 | 31000000 | bool Lookup(const Key &key, Value *value) { | |
426 | 31000000 | uint8_t target = SelectHashmap(key); | |
427 | 31000000 | Lock(target); | |
428 | 31000000 | const bool result = hashmaps_[target].Lookup(key, value); | |
429 | 31000000 | Unlock(target); | |
430 | 31000000 | return result; | |
431 | } | ||
432 | |||
433 | 116119397 | void Insert(const Key &key, const Value &value) { | |
434 | 116119397 | uint8_t target = SelectHashmap(key); | |
435 | 112311202 | Lock(target); | |
436 | 116572524 | hashmaps_[target].Insert(key, value); | |
437 | 110163801 | Unlock(target); | |
438 | 118275540 | } | |
439 | |||
440 | 56037522 | void Erase(const Key &key) { | |
441 | 56037522 | uint8_t target = SelectHashmap(key); | |
442 | 53332772 | Lock(target); | |
443 | 57040620 | hashmaps_[target].Erase(key); | |
444 | 52258188 | Unlock(target); | |
445 | 57737283 | } | |
446 | |||
447 | 31 | void Clear() { | |
448 |
2/2✓ Branch 0 taken 1302 times.
✓ Branch 1 taken 31 times.
|
1333 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
449 | 1302 | Lock(i); | |
450 |
2/2✓ Branch 0 taken 1302 times.
✓ Branch 1 taken 31 times.
|
1333 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
451 | 1302 | hashmaps_[i].Clear(); | |
452 |
2/2✓ Branch 0 taken 1302 times.
✓ Branch 1 taken 31 times.
|
1333 | for (uint8_t i = 0; i < num_hashmaps_; ++i) |
453 | 1302 | Unlock(i); | |
454 | 31 | } | |
455 | |||
456 | 310 | uint8_t num_hashmaps() const { return num_hashmaps_; } | |
457 | |||
458 | 248 | void GetSizes(uint32_t *sizes) { | |
459 |
2/2✓ Branch 0 taken 10416 times.
✓ Branch 1 taken 248 times.
|
10664 | for (uint8_t i = 0; i < num_hashmaps_; ++i) { |
460 | 10416 | Lock(i); | |
461 | 10416 | sizes[i] = hashmaps_[i].size(); | |
462 | 10416 | Unlock(i); | |
463 | } | ||
464 | 248 | } | |
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 | 202102361 | inline uint8_t SelectHashmap(const Key &key) { | |
476 | 202102361 | uint32_t hash = MurmurHash2(&key, sizeof(key), 0x37); | |
477 | 198089876 | double bucket = static_cast<double>(hash) | |
478 | 198089876 | * static_cast<double>(num_hashmaps_) | |
479 | / static_cast<double>(static_cast<uint32_t>(-1)); | ||
480 | 198089876 | return static_cast<uint32_t>(bucket) % num_hashmaps_; | |
481 | } | ||
482 | |||
483 | 198504160 | inline void Lock(const uint8_t target) { | |
484 | 198504160 | int retval = pthread_mutex_lock(&locks_[target]); | |
485 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 212730122 times.
|
212730122 | assert(retval == 0); |
486 | 212730122 | } | |
487 | |||
488 | 193577206 | inline void Unlock(const uint8_t target) { | |
489 | 193577206 | int retval = pthread_mutex_unlock(&locks_[target]); | |
490 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 213800149 times.
|
213800149 | assert(retval == 0); |
491 | 213800149 | } | |
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 |