1 | /* |
2 | * Copyright 2017-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | /** |
20 | * F14NodeMap, F14ValueMap, and F14VectorMap |
21 | * |
22 | * F14FastMap conditionally inherits from F14ValueMap or F14VectorMap |
23 | * |
24 | * See F14.md |
25 | * |
26 | * @author Nathan Bronson <ngbronson@fb.com> |
27 | * @author Xiao Shi <xshi@fb.com> |
28 | */ |
29 | |
30 | #include <stdexcept> |
31 | |
32 | #include <folly/Traits.h> |
33 | #include <folly/functional/ApplyTuple.h> |
34 | #include <folly/lang/Exception.h> |
35 | #include <folly/lang/SafeAssert.h> |
36 | |
37 | #include <folly/container/F14Map-fwd.h> |
38 | #include <folly/container/detail/F14Policy.h> |
39 | #include <folly/container/detail/F14Table.h> |
40 | |
41 | #if !FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
42 | |
43 | //////// Compatibility for unsupported platforms (not x86_64 and not aarch64) |
44 | |
45 | #include <string> |
46 | #include <unordered_map> |
47 | |
48 | namespace folly { |
49 | |
50 | namespace f14 { |
51 | namespace detail { |
52 | template <typename K, typename M, typename H, typename E, typename A> |
53 | class F14BasicMap : public std::unordered_map<K, M, H, E, A> { |
54 | using Super = std::unordered_map<K, M, H, E, A>; |
55 | |
56 | public: |
57 | using typename Super::pointer; |
58 | using typename Super::value_type; |
59 | |
60 | F14BasicMap() = default; |
61 | |
62 | using Super::Super; |
63 | |
64 | //// PUBLIC - F14 Extensions |
65 | |
66 | // exact for libstdc++, approximate for others |
67 | std::size_t getAllocatedMemorySize() const { |
68 | std::size_t rv = 0; |
69 | visitAllocationClasses( |
70 | [&](std::size_t bytes, std::size_t n) { rv += bytes * n; }); |
71 | return rv; |
72 | } |
73 | |
74 | // exact for libstdc++, approximate for others |
75 | template <typename V> |
76 | void visitAllocationClasses(V&& visitor) const { |
77 | auto bc = this->bucket_count(); |
78 | if (bc > 1) { |
79 | visitor(bc * sizeof(pointer), 1); |
80 | } |
81 | if (this->size() > 0) { |
82 | visitor(sizeof(StdNodeReplica<K, value_type, H>), this->size()); |
83 | } |
84 | } |
85 | |
86 | template <typename V> |
87 | void visitContiguousRanges(V&& visitor) const { |
88 | for (value_type const& entry : *this) { |
89 | value_type const* b = std::addressof(entry); |
90 | visitor(b, b + 1); |
91 | } |
92 | } |
93 | }; |
94 | } // namespace detail |
95 | } // namespace f14 |
96 | |
97 | template < |
98 | typename Key, |
99 | typename Mapped, |
100 | typename Hasher, |
101 | typename KeyEqual, |
102 | typename Alloc> |
103 | class F14ValueMap |
104 | : public f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc> { |
105 | using Super = f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc>; |
106 | |
107 | public: |
108 | using typename Super::value_type; |
109 | |
110 | F14ValueMap() = default; |
111 | |
112 | using Super::Super; |
113 | |
114 | F14ValueMap& operator=(std::initializer_list<value_type> ilist) { |
115 | Super::operator=(ilist); |
116 | return *this; |
117 | } |
118 | }; |
119 | |
120 | template < |
121 | typename Key, |
122 | typename Mapped, |
123 | typename Hasher, |
124 | typename KeyEqual, |
125 | typename Alloc> |
126 | class F14NodeMap |
127 | : public f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc> { |
128 | using Super = f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc>; |
129 | |
130 | public: |
131 | using typename Super::value_type; |
132 | |
133 | F14NodeMap() = default; |
134 | |
135 | using Super::Super; |
136 | |
137 | F14NodeMap& operator=(std::initializer_list<value_type> ilist) { |
138 | Super::operator=(ilist); |
139 | return *this; |
140 | } |
141 | }; |
142 | |
143 | template < |
144 | typename Key, |
145 | typename Mapped, |
146 | typename Hasher, |
147 | typename KeyEqual, |
148 | typename Alloc> |
149 | class F14VectorMap |
150 | : public f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc> { |
151 | using Super = f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc>; |
152 | |
153 | public: |
154 | using typename Super::value_type; |
155 | |
156 | F14VectorMap() = default; |
157 | |
158 | using Super::Super; |
159 | |
160 | F14VectorMap& operator=(std::initializer_list<value_type> ilist) { |
161 | Super::operator=(ilist); |
162 | return *this; |
163 | } |
164 | }; |
165 | |
166 | template < |
167 | typename Key, |
168 | typename Mapped, |
169 | typename Hasher, |
170 | typename KeyEqual, |
171 | typename Alloc> |
172 | class F14FastMap |
173 | : public f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc> { |
174 | using Super = f14::detail::F14BasicMap<Key, Mapped, Hasher, KeyEqual, Alloc>; |
175 | |
176 | public: |
177 | using typename Super::value_type; |
178 | |
179 | F14FastMap() = default; |
180 | |
181 | using Super::Super; |
182 | |
183 | F14FastMap& operator=(std::initializer_list<value_type> ilist) { |
184 | Super::operator=(ilist); |
185 | return *this; |
186 | } |
187 | }; |
188 | } // namespace folly |
189 | |
190 | #else // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
191 | |
192 | //////// Common case for supported platforms |
193 | |
194 | namespace folly { |
195 | namespace f14 { |
196 | namespace detail { |
197 | |
198 | template <typename Policy> |
199 | class F14BasicMap { |
200 | template <typename K, typename T> |
201 | using EnableHeterogeneousFind = std::enable_if_t< |
202 | EligibleForHeterogeneousFind< |
203 | typename Policy::Key, |
204 | typename Policy::Hasher, |
205 | typename Policy::KeyEqual, |
206 | K>::value, |
207 | T>; |
208 | |
209 | template <typename K, typename T> |
210 | using EnableHeterogeneousInsert = std::enable_if_t< |
211 | EligibleForHeterogeneousInsert< |
212 | typename Policy::Key, |
213 | typename Policy::Hasher, |
214 | typename Policy::KeyEqual, |
215 | K>::value, |
216 | T>; |
217 | |
218 | template <typename K, typename T> |
219 | using EnableHeterogeneousErase = std::enable_if_t< |
220 | EligibleForHeterogeneousFind< |
221 | typename Policy::Value, |
222 | typename Policy::Hasher, |
223 | typename Policy::KeyEqual, |
224 | K>::value && |
225 | !std::is_same<typename Policy::Iter, remove_cvref_t<K>>::value && |
226 | !std::is_same<typename Policy::ConstIter, remove_cvref_t<K>>::value, |
227 | T>; |
228 | |
229 | public: |
230 | //// PUBLIC - Member types |
231 | |
232 | using key_type = typename Policy::Key; |
233 | using mapped_type = typename Policy::Mapped; |
234 | using value_type = typename Policy::Value; |
235 | using size_type = std::size_t; |
236 | using difference_type = std::ptrdiff_t; |
237 | using hasher = typename Policy::Hasher; |
238 | using key_equal = typename Policy::KeyEqual; |
239 | using allocator_type = typename Policy::Alloc; |
240 | using reference = value_type&; |
241 | using const_reference = value_type const&; |
242 | using pointer = typename Policy::AllocTraits::pointer; |
243 | using const_pointer = typename Policy::AllocTraits::const_pointer; |
244 | using iterator = typename Policy::Iter; |
245 | using const_iterator = typename Policy::ConstIter; |
246 | |
247 | private: |
248 | using ItemIter = typename Policy::ItemIter; |
249 | |
250 | public: |
251 | //// PUBLIC - Member functions |
252 | |
253 | F14BasicMap() noexcept(Policy::kDefaultConstructIsNoexcept) |
254 | : F14BasicMap(0) {} |
255 | |
256 | explicit F14BasicMap( |
257 | std::size_t initialCapacity, |
258 | hasher const& hash = hasher{}, |
259 | key_equal const& eq = key_equal{}, |
260 | allocator_type const& alloc = allocator_type{}) |
261 | : table_{initialCapacity, hash, eq, alloc} {} |
262 | |
263 | explicit F14BasicMap(std::size_t initialCapacity, allocator_type const& alloc) |
264 | : F14BasicMap(initialCapacity, hasher{}, key_equal{}, alloc) {} |
265 | |
266 | explicit F14BasicMap( |
267 | std::size_t initialCapacity, |
268 | hasher const& hash, |
269 | allocator_type const& alloc) |
270 | : F14BasicMap(initialCapacity, hash, key_equal{}, alloc) {} |
271 | |
272 | explicit F14BasicMap(allocator_type const& alloc) |
273 | : F14BasicMap(0, hasher{}, key_equal{}, alloc) {} |
274 | |
275 | template <typename InputIt> |
276 | F14BasicMap( |
277 | InputIt first, |
278 | InputIt last, |
279 | std::size_t initialCapacity = 0, |
280 | hasher const& hash = hasher{}, |
281 | key_equal const& eq = key_equal{}, |
282 | allocator_type const& alloc = allocator_type{}) |
283 | : table_{initialCapacity, hash, eq, alloc} { |
284 | initialInsert(first, last, initialCapacity); |
285 | } |
286 | |
287 | template <typename InputIt> |
288 | F14BasicMap( |
289 | InputIt first, |
290 | InputIt last, |
291 | std::size_t initialCapacity, |
292 | allocator_type const& alloc) |
293 | : table_{initialCapacity, hasher{}, key_equal{}, alloc} { |
294 | initialInsert(first, last, initialCapacity); |
295 | } |
296 | |
297 | template <typename InputIt> |
298 | F14BasicMap( |
299 | InputIt first, |
300 | InputIt last, |
301 | std::size_t initialCapacity, |
302 | hasher const& hash, |
303 | allocator_type const& alloc) |
304 | : table_{initialCapacity, hash, key_equal{}, alloc} { |
305 | initialInsert(first, last, initialCapacity); |
306 | } |
307 | |
308 | F14BasicMap(F14BasicMap const& rhs) = default; |
309 | |
310 | F14BasicMap(F14BasicMap const& rhs, allocator_type const& alloc) |
311 | : table_{rhs.table_, alloc} {} |
312 | |
313 | F14BasicMap(F14BasicMap&& rhs) = default; |
314 | |
315 | F14BasicMap(F14BasicMap&& rhs, allocator_type const& alloc) noexcept( |
316 | Policy::kAllocIsAlwaysEqual) |
317 | : table_{std::move(rhs.table_), alloc} {} |
318 | |
319 | F14BasicMap( |
320 | std::initializer_list<value_type> init, |
321 | std::size_t initialCapacity = 0, |
322 | hasher const& hash = hasher{}, |
323 | key_equal const& eq = key_equal{}, |
324 | allocator_type const& alloc = allocator_type{}) |
325 | : table_{initialCapacity, hash, eq, alloc} { |
326 | initialInsert(init.begin(), init.end(), initialCapacity); |
327 | } |
328 | |
329 | F14BasicMap( |
330 | std::initializer_list<value_type> init, |
331 | std::size_t initialCapacity, |
332 | allocator_type const& alloc) |
333 | : table_{initialCapacity, hasher{}, key_equal{}, alloc} { |
334 | initialInsert(init.begin(), init.end(), initialCapacity); |
335 | } |
336 | |
337 | F14BasicMap( |
338 | std::initializer_list<value_type> init, |
339 | std::size_t initialCapacity, |
340 | hasher const& hash, |
341 | allocator_type const& alloc) |
342 | : table_{initialCapacity, hash, key_equal{}, alloc} { |
343 | initialInsert(init.begin(), init.end(), initialCapacity); |
344 | } |
345 | |
346 | F14BasicMap& operator=(F14BasicMap const&) = default; |
347 | |
348 | F14BasicMap& operator=(F14BasicMap&&) = default; |
349 | |
350 | F14BasicMap& operator=(std::initializer_list<value_type> ilist) { |
351 | clear(); |
352 | bulkInsert(ilist.begin(), ilist.end(), false); |
353 | return *this; |
354 | } |
355 | |
356 | allocator_type get_allocator() const noexcept { |
357 | return table_.alloc(); |
358 | } |
359 | |
360 | //// PUBLIC - Iterators |
361 | |
362 | iterator begin() noexcept { |
363 | return table_.makeIter(table_.begin()); |
364 | } |
365 | const_iterator begin() const noexcept { |
366 | return cbegin(); |
367 | } |
368 | const_iterator cbegin() const noexcept { |
369 | return table_.makeConstIter(table_.begin()); |
370 | } |
371 | |
372 | iterator end() noexcept { |
373 | return table_.makeIter(table_.end()); |
374 | } |
375 | const_iterator end() const noexcept { |
376 | return cend(); |
377 | } |
378 | const_iterator cend() const noexcept { |
379 | return table_.makeConstIter(table_.end()); |
380 | } |
381 | |
382 | //// PUBLIC - Capacity |
383 | |
384 | bool empty() const noexcept { |
385 | return table_.empty(); |
386 | } |
387 | |
388 | std::size_t size() const noexcept { |
389 | return table_.size(); |
390 | } |
391 | |
392 | std::size_t max_size() const noexcept { |
393 | return table_.max_size(); |
394 | } |
395 | |
396 | //// PUBLIC - Modifiers |
397 | |
398 | void clear() noexcept { |
399 | table_.clear(); |
400 | } |
401 | |
402 | std::pair<iterator, bool> insert(value_type const& value) { |
403 | return emplace(value); |
404 | } |
405 | |
406 | template <typename P> |
407 | std::enable_if_t< |
408 | std::is_constructible<value_type, P&&>::value, |
409 | std::pair<iterator, bool>> |
410 | insert(P&& value) { |
411 | return emplace(std::forward<P>(value)); |
412 | } |
413 | |
414 | // TODO(T31574848): Work around libstdc++ versions (e.g., GCC < 6) with no |
415 | // implementation of N4387 ("perfect initialization" for pairs and tuples). |
416 | template <typename U1, typename U2> |
417 | std::enable_if_t< |
418 | std::is_constructible<key_type, U1 const&>::value && |
419 | std::is_constructible<mapped_type, U2 const&>::value, |
420 | std::pair<iterator, bool>> |
421 | insert(std::pair<U1, U2> const& value) { |
422 | return emplace(value); |
423 | } |
424 | |
425 | // TODO(T31574848) |
426 | template <typename U1, typename U2> |
427 | std::enable_if_t< |
428 | std::is_constructible<key_type, U1&&>::value && |
429 | std::is_constructible<mapped_type, U2&&>::value, |
430 | std::pair<iterator, bool>> |
431 | insert(std::pair<U1, U2>&& value) { |
432 | return emplace(std::move(value)); |
433 | } |
434 | |
435 | std::pair<iterator, bool> insert(value_type&& value) { |
436 | return emplace(std::move(value)); |
437 | } |
438 | |
439 | // std::unordered_map's hinted insertion API is misleading. No |
440 | // implementation I've seen actually uses the hint. Code restructuring |
441 | // by the caller to use the hinted API is at best unnecessary, and at |
442 | // worst a pessimization. It is used, however, so we provide it. |
443 | |
444 | iterator insert(const_iterator /*hint*/, value_type const& value) { |
445 | return insert(value).first; |
446 | } |
447 | |
448 | template <typename P> |
449 | std::enable_if_t<std::is_constructible<value_type, P&&>::value, iterator> |
450 | insert(const_iterator /*hint*/, P&& value) { |
451 | return insert(std::forward<P>(value)).first; |
452 | } |
453 | |
454 | iterator insert(const_iterator /*hint*/, value_type&& value) { |
455 | return insert(std::move(value)).first; |
456 | } |
457 | |
458 | template <class... Args> |
459 | iterator emplace_hint(const_iterator /*hint*/, Args&&... args) { |
460 | return emplace(std::forward<Args>(args)...).first; |
461 | } |
462 | |
463 | private: |
464 | template <class InputIt> |
465 | FOLLY_ALWAYS_INLINE void |
466 | bulkInsert(InputIt first, InputIt last, bool autoReserve) { |
467 | if (autoReserve) { |
468 | auto n = std::distance(first, last); |
469 | if (n == 0) { |
470 | return; |
471 | } |
472 | table_.reserveForInsert(n); |
473 | } |
474 | while (first != last) { |
475 | insert(*first); |
476 | ++first; |
477 | } |
478 | } |
479 | |
480 | template <class InputIt> |
481 | void initialInsert(InputIt first, InputIt last, std::size_t initialCapacity) { |
482 | FOLLY_SAFE_DCHECK(empty() && bucket_count() >= initialCapacity, "" ); |
483 | |
484 | // It's possible that there are a lot of duplicates in first..last and |
485 | // so we will oversize ourself. The common case, however, is that |
486 | // we can avoid a lot of rehashing if we pre-expand. The behavior |
487 | // is easy to disable at a particular call site by asking for an |
488 | // initialCapacity of 1. |
489 | bool autoReserve = |
490 | std::is_same< |
491 | typename std::iterator_traits<InputIt>::iterator_category, |
492 | std::random_access_iterator_tag>::value && |
493 | initialCapacity == 0; |
494 | bulkInsert(first, last, autoReserve); |
495 | } |
496 | |
497 | public: |
498 | template <class InputIt> |
499 | void insert(InputIt first, InputIt last) { |
500 | // Bulk reserve is a heuristic choice, so it can backfire. We restrict |
501 | // ourself to situations that mimic bulk construction without an |
502 | // explicit initialCapacity. |
503 | bool autoReserve = |
504 | std::is_same< |
505 | typename std::iterator_traits<InputIt>::iterator_category, |
506 | std::random_access_iterator_tag>::value && |
507 | bucket_count() == 0; |
508 | bulkInsert(first, last, autoReserve); |
509 | } |
510 | |
511 | void insert(std::initializer_list<value_type> ilist) { |
512 | insert(ilist.begin(), ilist.end()); |
513 | } |
514 | |
515 | template <typename M> |
516 | std::pair<iterator, bool> insert_or_assign(key_type const& key, M&& obj) { |
517 | auto rv = try_emplace(key, std::forward<M>(obj)); |
518 | if (!rv.second) { |
519 | rv.first->second = std::forward<M>(obj); |
520 | } |
521 | return rv; |
522 | } |
523 | |
524 | template <typename M> |
525 | std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj) { |
526 | auto rv = try_emplace(std::move(key), std::forward<M>(obj)); |
527 | if (!rv.second) { |
528 | rv.first->second = std::forward<M>(obj); |
529 | } |
530 | return rv; |
531 | } |
532 | |
533 | template <typename M> |
534 | iterator |
535 | insert_or_assign(const_iterator /*hint*/, key_type const& key, M&& obj) { |
536 | return insert_or_assign(key, std::move(obj)).first; |
537 | } |
538 | |
539 | template <typename M> |
540 | iterator insert_or_assign(const_iterator /*hint*/, key_type&& key, M&& obj) { |
541 | return insert_or_assign(std::move(key), std::move(obj)).first; |
542 | } |
543 | |
544 | template <typename K, typename M> |
545 | EnableHeterogeneousInsert<K, std::pair<iterator, bool>> insert_or_assign( |
546 | K&& key, |
547 | M&& obj) { |
548 | auto rv = try_emplace(std::forward<K>(key), std::forward<M>(obj)); |
549 | if (!rv.second) { |
550 | rv.first->second = std::forward<M>(obj); |
551 | } |
552 | return rv; |
553 | } |
554 | |
555 | private: |
556 | std::pair<ItemIter, bool> emplaceItem() { |
557 | // rare but valid |
558 | return table_.tryEmplaceValue(key_type{}); |
559 | } |
560 | |
561 | template <typename U1, typename U2> |
562 | std::pair<ItemIter, bool> emplaceItem(U1&& x, U2&& y) { |
563 | using K = KeyTypeForEmplace<key_type, hasher, key_equal, U1>; |
564 | K key(std::forward<U1>(x)); |
565 | |
566 | // TODO(T31574848): piecewise_construct is to work around libstdc++ versions |
567 | // (e.g., GCC < 6) with no implementation of N4387 ("perfect initialization" |
568 | // for pairs and tuples). Otherwise we could just pass key, forwarded key, |
569 | // and forwarded y to tryEmplaceValue. |
570 | return table_.tryEmplaceValue( |
571 | key, |
572 | std::piecewise_construct, |
573 | std::forward_as_tuple(std::forward<K>(key)), |
574 | std::forward_as_tuple(std::forward<U2>(y))); |
575 | } |
576 | |
577 | template <typename U1, typename U2> |
578 | std::pair<ItemIter, bool> emplaceItem(std::pair<U1, U2> const& p) { |
579 | return emplaceItem(p.first, p.second); |
580 | } |
581 | |
582 | template <typename U1, typename U2> |
583 | std::pair<ItemIter, bool> emplaceItem(std::pair<U1, U2>&& p) { |
584 | return emplaceItem(std::move(p.first), std::move(p.second)); |
585 | } |
586 | |
587 | template <typename Arg1, typename... Args2> |
588 | std::pair<ItemIter, bool> emplaceItem( |
589 | std::piecewise_construct_t, |
590 | std::tuple<Arg1>&& first_args, |
591 | std::tuple<Args2...>&& second_args) { |
592 | using K = KeyTypeForEmplace<key_type, hasher, key_equal, Arg1>; |
593 | K key(std::get<0>(std::move(first_args))); |
594 | |
595 | // Args2&&... holds only references even if the caller gave us a |
596 | // tuple that directly contains values. |
597 | return table_.tryEmplaceValue( |
598 | key, |
599 | std::piecewise_construct, |
600 | std::forward_as_tuple(std::forward<K>(key)), |
601 | std::tuple<Args2&&...>(std::move(second_args))); |
602 | } |
603 | |
604 | template <typename... Args1, typename... Args2> |
605 | std::enable_if_t<sizeof...(Args1) != 1, std::pair<ItemIter, bool>> |
606 | emplaceItem( |
607 | std::piecewise_construct_t, |
608 | std::tuple<Args1...>&& first_args, |
609 | std::tuple<Args2...>&& second_args) { |
610 | auto key = make_from_tuple<key_type>( |
611 | std::tuple<Args1&&...>(std::move(first_args))); |
612 | return table_.tryEmplaceValue( |
613 | key, |
614 | std::piecewise_construct, |
615 | std::forward_as_tuple(std::move(key)), |
616 | std::tuple<Args2&&...>(std::move(second_args))); |
617 | } |
618 | |
619 | public: |
620 | template <typename... Args> |
621 | std::pair<iterator, bool> emplace(Args&&... args) { |
622 | auto rv = emplaceItem(std::forward<Args>(args)...); |
623 | return std::make_pair(table_.makeIter(rv.first), rv.second); |
624 | } |
625 | |
626 | template <typename... Args> |
627 | std::pair<iterator, bool> try_emplace(key_type const& key, Args&&... args) { |
628 | auto rv = table_.tryEmplaceValue( |
629 | key, |
630 | std::piecewise_construct, |
631 | std::forward_as_tuple(key), |
632 | std::forward_as_tuple(std::forward<Args>(args)...)); |
633 | return std::make_pair(table_.makeIter(rv.first), rv.second); |
634 | } |
635 | |
636 | template <typename... Args> |
637 | std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args) { |
638 | auto rv = table_.tryEmplaceValue( |
639 | key, |
640 | std::piecewise_construct, |
641 | std::forward_as_tuple(std::move(key)), |
642 | std::forward_as_tuple(std::forward<Args>(args)...)); |
643 | return std::make_pair(table_.makeIter(rv.first), rv.second); |
644 | } |
645 | |
646 | template <typename... Args> |
647 | iterator |
648 | try_emplace(const_iterator /*hint*/, key_type const& key, Args&&... args) { |
649 | auto rv = table_.tryEmplaceValue( |
650 | key, |
651 | std::piecewise_construct, |
652 | std::forward_as_tuple(key), |
653 | std::forward_as_tuple(std::forward<Args>(args)...)); |
654 | return table_.makeIter(rv.first); |
655 | } |
656 | |
657 | template <typename... Args> |
658 | iterator |
659 | try_emplace(const_iterator /*hint*/, key_type&& key, Args&&... args) { |
660 | auto rv = table_.tryEmplaceValue( |
661 | key, |
662 | std::piecewise_construct, |
663 | std::forward_as_tuple(std::move(key)), |
664 | std::forward_as_tuple(std::forward<Args>(args)...)); |
665 | return table_.makeIter(rv.first); |
666 | } |
667 | |
668 | template <typename K, typename... Args> |
669 | EnableHeterogeneousInsert<K, std::pair<iterator, bool>> try_emplace( |
670 | K&& key, |
671 | Args&&... args) { |
672 | auto rv = table_.tryEmplaceValue( |
673 | key, |
674 | std::piecewise_construct, |
675 | std::forward_as_tuple(std::forward<K>(key)), |
676 | std::forward_as_tuple(std::forward<Args>(args)...)); |
677 | return std::make_pair(table_.makeIter(rv.first), rv.second); |
678 | } |
679 | |
680 | FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) { |
681 | // If we are inlined then gcc and clang can optimize away all of the |
682 | // work of itemPos.advance() if our return value is discarded. |
683 | auto itemPos = table_.unwrapIter(pos); |
684 | table_.eraseIter(itemPos); |
685 | itemPos.advanceLikelyDead(); |
686 | return table_.makeIter(itemPos); |
687 | } |
688 | |
689 | // This form avoids ambiguity when key_type has a templated constructor |
690 | // that accepts const_iterator |
691 | iterator erase(iterator pos) { |
692 | auto itemPos = table_.unwrapIter(pos); |
693 | table_.eraseIter(itemPos); |
694 | itemPos.advanceLikelyDead(); |
695 | return table_.makeIter(itemPos); |
696 | } |
697 | |
698 | iterator erase(const_iterator first, const_iterator last) { |
699 | auto itemFirst = table_.unwrapIter(first); |
700 | auto itemLast = table_.unwrapIter(last); |
701 | while (itemFirst != itemLast) { |
702 | table_.eraseIter(itemFirst); |
703 | itemFirst.advance(); |
704 | } |
705 | return table_.makeIter(itemFirst); |
706 | } |
707 | |
708 | size_type erase(key_type const& key) { |
709 | return table_.eraseKey(key); |
710 | } |
711 | |
712 | template <typename K> |
713 | EnableHeterogeneousErase<K, size_type> erase(K const& key) { |
714 | return table_.eraseKey(key); |
715 | } |
716 | |
717 | //// PUBLIC - Lookup |
718 | |
719 | FOLLY_ALWAYS_INLINE mapped_type& at(key_type const& key) { |
720 | return at(*this, key); |
721 | } |
722 | |
723 | FOLLY_ALWAYS_INLINE mapped_type const& at(key_type const& key) const { |
724 | return at(*this, key); |
725 | } |
726 | |
727 | template <typename K> |
728 | EnableHeterogeneousFind<K, mapped_type&> at(K const& key) { |
729 | return at(*this, key); |
730 | } |
731 | |
732 | template <typename K> |
733 | EnableHeterogeneousFind<K, mapped_type const&> at(K const& key) const { |
734 | return at(*this, key); |
735 | } |
736 | |
737 | mapped_type& operator[](key_type const& key) { |
738 | return try_emplace(key).first->second; |
739 | } |
740 | |
741 | mapped_type& operator[](key_type&& key) { |
742 | return try_emplace(std::move(key)).first->second; |
743 | } |
744 | |
745 | template <typename K> |
746 | EnableHeterogeneousInsert<K, mapped_type&> operator[](K&& key) { |
747 | return try_emplace(std::forward<K>(key)).first->second; |
748 | } |
749 | |
750 | FOLLY_ALWAYS_INLINE std::size_t count(key_type const& key) const { |
751 | return table_.find(key).atEnd() ? 0 : 1; |
752 | } |
753 | |
754 | template <typename K> |
755 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, std::size_t> count( |
756 | K const& key) const { |
757 | return table_.find(key).atEnd() ? 0 : 1; |
758 | } |
759 | |
760 | // prehash(key) does the work of evaluating hash_function()(key) |
761 | // (including additional bit-mixing for non-avalanching hash functions), |
762 | // wraps the result of that work in a token for later reuse, and |
763 | // begins prefetching the first steps of looking for key into the |
764 | // local CPU cache. |
765 | // |
766 | // The returned token may be used at any time, may be used more than |
767 | // once, and may be used in other F14 sets and maps. Tokens are |
768 | // transferrable between any F14 containers (maps and sets) with the |
769 | // same key_type and equal hash_function()s. |
770 | // |
771 | // Hash tokens are not hints -- it is a bug to call any method on this |
772 | // class with a token t and key k where t isn't the result of a call |
773 | // to prehash(k2) with k2 == k. |
774 | F14HashToken prehash(key_type const& key) const { |
775 | return table_.prehash(key); |
776 | } |
777 | |
778 | template <typename K> |
779 | EnableHeterogeneousFind<K, F14HashToken> prehash(K const& key) const { |
780 | return table_.prehash(key); |
781 | } |
782 | |
783 | FOLLY_ALWAYS_INLINE iterator find(key_type const& key) { |
784 | return table_.makeIter(table_.find(key)); |
785 | } |
786 | |
787 | FOLLY_ALWAYS_INLINE const_iterator find(key_type const& key) const { |
788 | return table_.makeConstIter(table_.find(key)); |
789 | } |
790 | |
791 | FOLLY_ALWAYS_INLINE iterator |
792 | find(F14HashToken const& token, key_type const& key) { |
793 | return table_.makeIter(table_.find(token, key)); |
794 | } |
795 | |
796 | FOLLY_ALWAYS_INLINE const_iterator |
797 | find(F14HashToken const& token, key_type const& key) const { |
798 | return table_.makeConstIter(table_.find(token, key)); |
799 | } |
800 | |
801 | template <typename K> |
802 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find(K const& key) { |
803 | return table_.makeIter(table_.find(key)); |
804 | } |
805 | |
806 | template <typename K> |
807 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find( |
808 | K const& key) const { |
809 | return table_.makeConstIter(table_.find(key)); |
810 | } |
811 | |
812 | template <typename K> |
813 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, iterator> find( |
814 | F14HashToken const& token, |
815 | K const& key) { |
816 | return table_.makeIter(table_.find(token, key)); |
817 | } |
818 | |
819 | template <typename K> |
820 | FOLLY_ALWAYS_INLINE EnableHeterogeneousFind<K, const_iterator> find( |
821 | F14HashToken const& token, |
822 | K const& key) const { |
823 | return table_.makeConstIter(table_.find(token, key)); |
824 | } |
825 | |
826 | std::pair<iterator, iterator> equal_range(key_type const& key) { |
827 | return equal_range(*this, key); |
828 | } |
829 | |
830 | std::pair<const_iterator, const_iterator> equal_range( |
831 | key_type const& key) const { |
832 | return equal_range(*this, key); |
833 | } |
834 | |
835 | template <typename K> |
836 | EnableHeterogeneousFind<K, std::pair<iterator, iterator>> equal_range( |
837 | K const& key) { |
838 | return equal_range(*this, key); |
839 | } |
840 | |
841 | template <typename K> |
842 | EnableHeterogeneousFind<K, std::pair<const_iterator, const_iterator>> |
843 | equal_range(K const& key) const { |
844 | return equal_range(*this, key); |
845 | } |
846 | |
847 | //// PUBLIC - Bucket interface |
848 | |
849 | std::size_t bucket_count() const noexcept { |
850 | return table_.bucket_count(); |
851 | } |
852 | |
853 | std::size_t max_bucket_count() const noexcept { |
854 | return table_.max_bucket_count(); |
855 | } |
856 | |
857 | //// PUBLIC - Hash policy |
858 | |
859 | float load_factor() const noexcept { |
860 | return table_.load_factor(); |
861 | } |
862 | |
863 | float max_load_factor() const noexcept { |
864 | return table_.max_load_factor(); |
865 | } |
866 | |
867 | void max_load_factor(float v) { |
868 | table_.max_load_factor(v); |
869 | } |
870 | |
871 | void rehash(std::size_t bucketCapacity) { |
872 | // The standard's rehash() requires understanding the max load factor, |
873 | // which is easy to get wrong. Since we don't actually allow adjustment |
874 | // of max_load_factor there is no difference. |
875 | reserve(bucketCapacity); |
876 | } |
877 | |
878 | void reserve(std::size_t capacity) { |
879 | table_.reserve(capacity); |
880 | } |
881 | |
882 | //// PUBLIC - Observers |
883 | |
884 | hasher hash_function() const { |
885 | return table_.hasher(); |
886 | } |
887 | |
888 | key_equal key_eq() const { |
889 | return table_.keyEqual(); |
890 | } |
891 | |
892 | //// PUBLIC - F14 Extensions |
893 | |
894 | // Get memory footprint, not including sizeof(*this). |
895 | std::size_t getAllocatedMemorySize() const { |
896 | return table_.getAllocatedMemorySize(); |
897 | } |
898 | |
899 | // Enumerates classes of allocated memory blocks currently owned |
900 | // by this table, calling visitor(allocationSize, allocationCount). |
901 | // This can be used to get a more accurate indication of memory footprint |
902 | // than getAllocatedMemorySize() if you have some way of computing the |
903 | // internal fragmentation of the allocator, such as JEMalloc's nallocx. |
904 | // The visitor might be called twice with the same allocationSize. The |
905 | // visitor's computation should produce the same result for visitor(8, |
906 | // 2) as for two calls to visitor(8, 1), for example. The visitor may |
907 | // be called with a zero allocationCount. |
908 | template <typename V> |
909 | void visitAllocationClasses(V&& visitor) const { |
910 | return table_.visitAllocationClasses(visitor); |
911 | } |
912 | |
913 | // Calls visitor with two value_type const*, b and e, such that every |
914 | // entry in the table is included in exactly one of the ranges [b,e). |
915 | // This can be used to efficiently iterate elements in bulk when crossing |
916 | // an API boundary that supports contiguous blocks of items. |
917 | template <typename V> |
918 | void visitContiguousRanges(V&& visitor) const; |
919 | |
920 | F14TableStats computeStats() const noexcept { |
921 | return table_.computeStats(); |
922 | } |
923 | |
924 | private: |
925 | template <typename Self, typename K> |
926 | FOLLY_ALWAYS_INLINE static auto& at(Self& self, K const& key) { |
927 | auto iter = self.find(key); |
928 | if (iter == self.end()) { |
929 | throw_exception<std::out_of_range>("at() did not find key" ); |
930 | } |
931 | return iter->second; |
932 | } |
933 | |
934 | template <typename Self, typename K> |
935 | static auto equal_range(Self& self, K const& key) { |
936 | auto first = self.find(key); |
937 | auto last = first; |
938 | if (last != self.end()) { |
939 | ++last; |
940 | } |
941 | return std::make_pair(first, last); |
942 | } |
943 | |
944 | protected: |
945 | F14Table<Policy> table_; |
946 | }; |
947 | |
948 | template <typename M> |
949 | bool mapsEqual(M const& lhs, M const& rhs) { |
950 | if (lhs.size() != rhs.size()) { |
951 | return false; |
952 | } |
953 | for (auto& kv : lhs) { |
954 | auto iter = rhs.find(kv.first); |
955 | if (iter == rhs.end()) { |
956 | return false; |
957 | } |
958 | if (std::is_same< |
959 | typename M::key_equal, |
960 | std::equal_to<typename M::key_type>>::value) { |
961 | // find already checked key, just check value |
962 | if (!(kv.second == iter->second)) { |
963 | return false; |
964 | } |
965 | } else { |
966 | // spec says we compare key with == as well as with key_eq() |
967 | if (!(kv == *iter)) { |
968 | return false; |
969 | } |
970 | } |
971 | } |
972 | return true; |
973 | } |
974 | } // namespace detail |
975 | } // namespace f14 |
976 | |
977 | template < |
978 | typename Key, |
979 | typename Mapped, |
980 | typename Hasher, |
981 | typename KeyEqual, |
982 | typename Alloc> |
983 | class F14ValueMap |
984 | : public f14::detail::F14BasicMap<f14::detail::MapPolicyWithDefaults< |
985 | f14::detail::ValueContainerPolicy, |
986 | Key, |
987 | Mapped, |
988 | Hasher, |
989 | KeyEqual, |
990 | Alloc>> { |
991 | protected: |
992 | using Policy = f14::detail::MapPolicyWithDefaults< |
993 | f14::detail::ValueContainerPolicy, |
994 | Key, |
995 | Mapped, |
996 | Hasher, |
997 | KeyEqual, |
998 | Alloc>; |
999 | |
1000 | private: |
1001 | using Super = f14::detail::F14BasicMap<Policy>; |
1002 | |
1003 | public: |
1004 | using typename Super::value_type; |
1005 | |
1006 | F14ValueMap() = default; |
1007 | |
1008 | using Super::Super; |
1009 | |
1010 | F14ValueMap& operator=(std::initializer_list<value_type> ilist) { |
1011 | Super::operator=(ilist); |
1012 | return *this; |
1013 | } |
1014 | |
1015 | void swap(F14ValueMap& rhs) noexcept(Policy::kSwapIsNoexcept) { |
1016 | this->table_.swap(rhs.table_); |
1017 | } |
1018 | |
1019 | template <typename V> |
1020 | void visitContiguousRanges(V&& visitor) const { |
1021 | this->table_.visitContiguousItemRanges(visitor); |
1022 | } |
1023 | }; |
1024 | |
1025 | template <typename K, typename M, typename H, typename E, typename A> |
1026 | bool operator==( |
1027 | F14ValueMap<K, M, H, E, A> const& lhs, |
1028 | F14ValueMap<K, M, H, E, A> const& rhs) { |
1029 | return mapsEqual(lhs, rhs); |
1030 | } |
1031 | |
1032 | template <typename K, typename M, typename H, typename E, typename A> |
1033 | bool operator!=( |
1034 | F14ValueMap<K, M, H, E, A> const& lhs, |
1035 | F14ValueMap<K, M, H, E, A> const& rhs) { |
1036 | return !(lhs == rhs); |
1037 | } |
1038 | |
1039 | template < |
1040 | typename Key, |
1041 | typename Mapped, |
1042 | typename Hasher, |
1043 | typename KeyEqual, |
1044 | typename Alloc> |
1045 | class F14NodeMap |
1046 | : public f14::detail::F14BasicMap<f14::detail::MapPolicyWithDefaults< |
1047 | f14::detail::NodeContainerPolicy, |
1048 | Key, |
1049 | Mapped, |
1050 | Hasher, |
1051 | KeyEqual, |
1052 | Alloc>> { |
1053 | protected: |
1054 | using Policy = f14::detail::MapPolicyWithDefaults< |
1055 | f14::detail::NodeContainerPolicy, |
1056 | Key, |
1057 | Mapped, |
1058 | Hasher, |
1059 | KeyEqual, |
1060 | Alloc>; |
1061 | |
1062 | private: |
1063 | using Super = f14::detail::F14BasicMap<Policy>; |
1064 | |
1065 | public: |
1066 | using typename Super::value_type; |
1067 | |
1068 | F14NodeMap() = default; |
1069 | |
1070 | using Super::Super; |
1071 | |
1072 | F14NodeMap& operator=(std::initializer_list<value_type> ilist) { |
1073 | Super::operator=(ilist); |
1074 | return *this; |
1075 | } |
1076 | |
1077 | void swap(F14NodeMap& rhs) noexcept(Policy::kSwapIsNoexcept) { |
1078 | this->table_.swap(rhs.table_); |
1079 | } |
1080 | |
1081 | template <typename V> |
1082 | void visitContiguousRanges(V&& visitor) const { |
1083 | this->table_.visitItems([&](typename Policy::Item ptr) { |
1084 | value_type const* b = std::addressof(*ptr); |
1085 | visitor(b, b + 1); |
1086 | }); |
1087 | } |
1088 | |
1089 | // TODO extract and node_handle insert |
1090 | }; |
1091 | |
1092 | template <typename K, typename M, typename H, typename E, typename A> |
1093 | bool operator==( |
1094 | F14NodeMap<K, M, H, E, A> const& lhs, |
1095 | F14NodeMap<K, M, H, E, A> const& rhs) { |
1096 | return mapsEqual(lhs, rhs); |
1097 | } |
1098 | |
1099 | template <typename K, typename M, typename H, typename E, typename A> |
1100 | bool operator!=( |
1101 | F14NodeMap<K, M, H, E, A> const& lhs, |
1102 | F14NodeMap<K, M, H, E, A> const& rhs) { |
1103 | return !(lhs == rhs); |
1104 | } |
1105 | |
1106 | namespace f14 { |
1107 | namespace detail { |
1108 | template < |
1109 | typename Key, |
1110 | typename Mapped, |
1111 | typename Hasher, |
1112 | typename KeyEqual, |
1113 | typename Alloc, |
1114 | typename EligibleForPerturbedInsertionOrder> |
1115 | class F14VectorMapImpl : public F14BasicMap<MapPolicyWithDefaults< |
1116 | VectorContainerPolicy, |
1117 | Key, |
1118 | Mapped, |
1119 | Hasher, |
1120 | KeyEqual, |
1121 | Alloc, |
1122 | EligibleForPerturbedInsertionOrder>> { |
1123 | protected: |
1124 | using Policy = MapPolicyWithDefaults< |
1125 | VectorContainerPolicy, |
1126 | Key, |
1127 | Mapped, |
1128 | Hasher, |
1129 | KeyEqual, |
1130 | Alloc, |
1131 | EligibleForPerturbedInsertionOrder>; |
1132 | |
1133 | private: |
1134 | using Super = F14BasicMap<Policy>; |
1135 | |
1136 | template <typename K, typename T> |
1137 | using EnableHeterogeneousVectorErase = std::enable_if_t< |
1138 | EligibleForHeterogeneousFind< |
1139 | typename Policy::Value, |
1140 | typename Policy::Hasher, |
1141 | typename Policy::KeyEqual, |
1142 | K>::value && |
1143 | !std::is_same<typename Policy::Iter, remove_cvref_t<K>>::value && |
1144 | !std::is_same<typename Policy::ConstIter, remove_cvref_t<K>>::value && |
1145 | !std::is_same<typename Policy::ReverseIter, remove_cvref_t<K>>:: |
1146 | value && |
1147 | !std::is_same<typename Policy::ConstReverseIter, remove_cvref_t<K>>:: |
1148 | value, |
1149 | T>; |
1150 | |
1151 | public: |
1152 | using typename Super::const_iterator; |
1153 | using typename Super::iterator; |
1154 | using typename Super::key_type; |
1155 | using typename Super::value_type; |
1156 | |
1157 | F14VectorMapImpl() = default; |
1158 | |
1159 | // inherit constructors |
1160 | using Super::Super; |
1161 | |
1162 | F14VectorMapImpl& operator=(std::initializer_list<value_type> ilist) { |
1163 | Super::operator=(ilist); |
1164 | return *this; |
1165 | } |
1166 | |
1167 | iterator begin() { |
1168 | return this->table_.linearBegin(this->size()); |
1169 | } |
1170 | const_iterator begin() const { |
1171 | return cbegin(); |
1172 | } |
1173 | const_iterator cbegin() const { |
1174 | return this->table_.linearBegin(this->size()); |
1175 | } |
1176 | |
1177 | iterator end() { |
1178 | return this->table_.linearEnd(); |
1179 | } |
1180 | const_iterator end() const { |
1181 | return cend(); |
1182 | } |
1183 | const_iterator cend() const { |
1184 | return this->table_.linearEnd(); |
1185 | } |
1186 | |
1187 | private: |
1188 | void eraseUnderlying(typename Policy::ItemIter underlying) { |
1189 | Alloc& a = this->table_.alloc(); |
1190 | auto values = this->table_.values_; |
1191 | |
1192 | // Remove the ptr from the base table and destroy the value. |
1193 | auto index = underlying.item(); |
1194 | // The item still needs to be hashable during this call, so we must destroy |
1195 | // the value _afterwards_. |
1196 | this->table_.eraseIter(underlying); |
1197 | Policy::AllocTraits::destroy(a, std::addressof(values[index])); |
1198 | |
1199 | // move the last element in values_ down and fix up the inbound index |
1200 | auto tailIndex = this->size(); |
1201 | if (tailIndex != index) { |
1202 | auto tail = this->table_.find( |
1203 | VectorContainerIndexSearch{static_cast<uint32_t>(tailIndex)}); |
1204 | tail.item() = index; |
1205 | auto p = std::addressof(values[index]); |
1206 | assume(p != nullptr); |
1207 | this->table_.transfer(a, std::addressof(values[tailIndex]), p, 1); |
1208 | } |
1209 | } |
1210 | |
1211 | template <typename K> |
1212 | std::size_t eraseUnderlyingKey(K const& key) { |
1213 | auto underlying = this->table_.find(key); |
1214 | if (underlying.atEnd()) { |
1215 | return 0; |
1216 | } else { |
1217 | eraseUnderlying(underlying); |
1218 | return 1; |
1219 | } |
1220 | } |
1221 | |
1222 | public: |
1223 | FOLLY_ALWAYS_INLINE iterator erase(const_iterator pos) { |
1224 | auto index = this->table_.iterToIndex(pos); |
1225 | auto underlying = this->table_.find(VectorContainerIndexSearch{index}); |
1226 | eraseUnderlying(underlying); |
1227 | return index == 0 ? end() : this->table_.indexToIter(index - 1); |
1228 | } |
1229 | |
1230 | // This form avoids ambiguity when key_type has a templated constructor |
1231 | // that accepts const_iterator |
1232 | FOLLY_ALWAYS_INLINE iterator erase(iterator pos) { |
1233 | const_iterator cpos{pos}; |
1234 | return erase(cpos); |
1235 | } |
1236 | |
1237 | iterator erase(const_iterator first, const_iterator last) { |
1238 | while (first != last) { |
1239 | first = erase(first); |
1240 | } |
1241 | auto index = this->table_.iterToIndex(first); |
1242 | return index == 0 ? end() : this->table_.indexToIter(index - 1); |
1243 | } |
1244 | |
1245 | std::size_t erase(key_type const& key) { |
1246 | return eraseUnderlyingKey(key); |
1247 | } |
1248 | |
1249 | template <typename K> |
1250 | EnableHeterogeneousVectorErase<K, std::size_t> erase(K const& key) { |
1251 | return eraseUnderlyingKey(key); |
1252 | } |
1253 | |
1254 | template <typename V> |
1255 | void visitContiguousRanges(V&& visitor) const { |
1256 | auto n = this->table_.size(); |
1257 | if (n > 0) { |
1258 | value_type const* b = std::addressof(this->table_.values_[0]); |
1259 | visitor(b, b + n); |
1260 | } |
1261 | } |
1262 | }; |
1263 | } // namespace detail |
1264 | } // namespace f14 |
1265 | |
1266 | template < |
1267 | typename Key, |
1268 | typename Mapped, |
1269 | typename Hasher, |
1270 | typename KeyEqual, |
1271 | typename Alloc> |
1272 | class F14VectorMap : public f14::detail::F14VectorMapImpl< |
1273 | Key, |
1274 | Mapped, |
1275 | Hasher, |
1276 | KeyEqual, |
1277 | Alloc, |
1278 | std::false_type> { |
1279 | using Super = f14::detail:: |
1280 | F14VectorMapImpl<Key, Mapped, Hasher, KeyEqual, Alloc, std::false_type>; |
1281 | |
1282 | public: |
1283 | using typename Super::const_iterator; |
1284 | using typename Super::iterator; |
1285 | using typename Super::value_type; |
1286 | using reverse_iterator = typename Super::Policy::ReverseIter; |
1287 | using const_reverse_iterator = typename Super::Policy::ConstReverseIter; |
1288 | |
1289 | F14VectorMap() = default; |
1290 | |
1291 | // inherit constructors |
1292 | using Super::Super; |
1293 | |
1294 | F14VectorMap& operator=(std::initializer_list<value_type> ilist) { |
1295 | Super::operator=(ilist); |
1296 | return *this; |
1297 | } |
1298 | |
1299 | void swap(F14VectorMap& rhs) noexcept(Super::Policy::kSwapIsNoexcept) { |
1300 | this->table_.swap(rhs.table_); |
1301 | } |
1302 | |
1303 | // ITERATION ORDER |
1304 | // |
1305 | // Deterministic iteration order for insert-only workloads is part of |
1306 | // F14VectorMap's supported API: iterator is LIFO and reverse_iterator |
1307 | // is FIFO. |
1308 | // |
1309 | // If there have been no calls to erase() then iterator and |
1310 | // const_iterator enumerate entries in the opposite of insertion order. |
1311 | // begin()->first is the key most recently inserted. reverse_iterator |
1312 | // and reverse_const_iterator, therefore, enumerate in LIFO (insertion) |
1313 | // order for insert-only workloads. Deterministic iteration order is |
1314 | // only guaranteed if no keys were removed since the last time the |
1315 | // map was empty. Iteration order is preserved across rehashes and |
1316 | // F14VectorMap copies and moves. |
1317 | // |
1318 | // iterator uses LIFO order so that erasing while iterating with begin() |
1319 | // and end() is safe using the erase(it++) idiom, which is supported |
1320 | // by std::map and std::unordered_map. erase(iter) invalidates iter |
1321 | // and all iterators before iter in the non-reverse iteration order. |
1322 | // Every successful erase invalidates all reverse iterators. |
1323 | // |
1324 | // No erase is provided for reverse_iterator or const_reverse_iterator |
1325 | // to make it harder to shoot yourself in the foot by erasing while |
1326 | // reverse-iterating. You can write that as map.erase(map.iter(riter)) |
1327 | // if you really need it. |
1328 | |
1329 | reverse_iterator rbegin() { |
1330 | return this->table_.values_; |
1331 | } |
1332 | const_reverse_iterator rbegin() const { |
1333 | return crbegin(); |
1334 | } |
1335 | const_reverse_iterator crbegin() const { |
1336 | return this->table_.values_; |
1337 | } |
1338 | |
1339 | reverse_iterator rend() { |
1340 | return this->table_.values_ + this->table_.size(); |
1341 | } |
1342 | const_reverse_iterator rend() const { |
1343 | return crend(); |
1344 | } |
1345 | const_reverse_iterator crend() const { |
1346 | return this->table_.values_ + this->table_.size(); |
1347 | } |
1348 | |
1349 | // explicit conversions between iterator and reverse_iterator |
1350 | iterator iter(reverse_iterator riter) { |
1351 | return this->table_.iter(riter); |
1352 | } |
1353 | const_iterator iter(const_reverse_iterator riter) const { |
1354 | return this->table_.iter(riter); |
1355 | } |
1356 | |
1357 | reverse_iterator riter(iterator it) { |
1358 | return this->table_.riter(it); |
1359 | } |
1360 | const_reverse_iterator riter(const_iterator it) const { |
1361 | return this->table_.riter(it); |
1362 | } |
1363 | }; |
1364 | |
1365 | template <typename K, typename M, typename H, typename E, typename A> |
1366 | bool operator==( |
1367 | F14VectorMap<K, M, H, E, A> const& lhs, |
1368 | F14VectorMap<K, M, H, E, A> const& rhs) { |
1369 | return mapsEqual(lhs, rhs); |
1370 | } |
1371 | |
1372 | template <typename K, typename M, typename H, typename E, typename A> |
1373 | bool operator!=( |
1374 | F14VectorMap<K, M, H, E, A> const& lhs, |
1375 | F14VectorMap<K, M, H, E, A> const& rhs) { |
1376 | return !(lhs == rhs); |
1377 | } |
1378 | |
1379 | template < |
1380 | typename Key, |
1381 | typename Mapped, |
1382 | typename Hasher, |
1383 | typename KeyEqual, |
1384 | typename Alloc> |
1385 | class F14FastMap : public std::conditional_t< |
1386 | sizeof(std::pair<Key const, Mapped>) < 24, |
1387 | F14ValueMap<Key, Mapped, Hasher, KeyEqual, Alloc>, |
1388 | f14::detail::F14VectorMapImpl< |
1389 | Key, |
1390 | Mapped, |
1391 | Hasher, |
1392 | KeyEqual, |
1393 | Alloc, |
1394 | std::true_type>> { |
1395 | using Super = std::conditional_t< |
1396 | sizeof(std::pair<Key const, Mapped>) < 24, |
1397 | F14ValueMap<Key, Mapped, Hasher, KeyEqual, Alloc>, |
1398 | f14::detail::F14VectorMapImpl< |
1399 | Key, |
1400 | Mapped, |
1401 | Hasher, |
1402 | KeyEqual, |
1403 | Alloc, |
1404 | std::true_type>>; |
1405 | |
1406 | public: |
1407 | using typename Super::value_type; |
1408 | |
1409 | F14FastMap() = default; |
1410 | |
1411 | using Super::Super; |
1412 | |
1413 | F14FastMap& operator=(std::initializer_list<value_type> ilist) { |
1414 | Super::operator=(ilist); |
1415 | return *this; |
1416 | } |
1417 | |
1418 | void swap(F14FastMap& rhs) noexcept(Super::Policy::kSwapIsNoexcept) { |
1419 | this->table_.swap(rhs.table_); |
1420 | } |
1421 | }; |
1422 | |
1423 | template <typename K, typename M, typename H, typename E, typename A> |
1424 | bool operator==( |
1425 | F14FastMap<K, M, H, E, A> const& lhs, |
1426 | F14FastMap<K, M, H, E, A> const& rhs) { |
1427 | return mapsEqual(lhs, rhs); |
1428 | } |
1429 | |
1430 | template <typename K, typename M, typename H, typename E, typename A> |
1431 | bool operator!=( |
1432 | F14FastMap<K, M, H, E, A> const& lhs, |
1433 | F14FastMap<K, M, H, E, A> const& rhs) { |
1434 | return !(lhs == rhs); |
1435 | } |
1436 | } // namespace folly |
1437 | |
1438 | #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE |
1439 | |
1440 | namespace folly { |
1441 | |
1442 | template <typename K, typename M, typename H, typename E, typename A> |
1443 | void swap( |
1444 | F14ValueMap<K, M, H, E, A>& lhs, |
1445 | F14ValueMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { |
1446 | lhs.swap(rhs); |
1447 | } |
1448 | |
1449 | template <typename K, typename M, typename H, typename E, typename A> |
1450 | void swap( |
1451 | F14NodeMap<K, M, H, E, A>& lhs, |
1452 | F14NodeMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { |
1453 | lhs.swap(rhs); |
1454 | } |
1455 | |
1456 | template <typename K, typename M, typename H, typename E, typename A> |
1457 | void swap( |
1458 | F14VectorMap<K, M, H, E, A>& lhs, |
1459 | F14VectorMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { |
1460 | lhs.swap(rhs); |
1461 | } |
1462 | |
1463 | template <typename K, typename M, typename H, typename E, typename A> |
1464 | void swap( |
1465 | F14FastMap<K, M, H, E, A>& lhs, |
1466 | F14FastMap<K, M, H, E, A>& rhs) noexcept(noexcept(lhs.swap(rhs))) { |
1467 | lhs.swap(rhs); |
1468 | } |
1469 | |
1470 | } // namespace folly |
1471 | |