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
48namespace folly {
49
50namespace f14 {
51namespace detail {
52template <typename K, typename M, typename H, typename E, typename A>
53class 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
97template <
98 typename Key,
99 typename Mapped,
100 typename Hasher,
101 typename KeyEqual,
102 typename Alloc>
103class 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
120template <
121 typename Key,
122 typename Mapped,
123 typename Hasher,
124 typename KeyEqual,
125 typename Alloc>
126class 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
143template <
144 typename Key,
145 typename Mapped,
146 typename Hasher,
147 typename KeyEqual,
148 typename Alloc>
149class 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
166template <
167 typename Key,
168 typename Mapped,
169 typename Hasher,
170 typename KeyEqual,
171 typename Alloc>
172class 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
194namespace folly {
195namespace f14 {
196namespace detail {
197
198template <typename Policy>
199class 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
948template <typename M>
949bool 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
977template <
978 typename Key,
979 typename Mapped,
980 typename Hasher,
981 typename KeyEqual,
982 typename Alloc>
983class 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
1025template <typename K, typename M, typename H, typename E, typename A>
1026bool 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
1032template <typename K, typename M, typename H, typename E, typename A>
1033bool 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
1039template <
1040 typename Key,
1041 typename Mapped,
1042 typename Hasher,
1043 typename KeyEqual,
1044 typename Alloc>
1045class 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
1092template <typename K, typename M, typename H, typename E, typename A>
1093bool 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
1099template <typename K, typename M, typename H, typename E, typename A>
1100bool 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
1106namespace f14 {
1107namespace detail {
1108template <
1109 typename Key,
1110 typename Mapped,
1111 typename Hasher,
1112 typename KeyEqual,
1113 typename Alloc,
1114 typename EligibleForPerturbedInsertionOrder>
1115class 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
1266template <
1267 typename Key,
1268 typename Mapped,
1269 typename Hasher,
1270 typename KeyEqual,
1271 typename Alloc>
1272class 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
1365template <typename K, typename M, typename H, typename E, typename A>
1366bool 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
1372template <typename K, typename M, typename H, typename E, typename A>
1373bool 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
1379template <
1380 typename Key,
1381 typename Mapped,
1382 typename Hasher,
1383 typename KeyEqual,
1384 typename Alloc>
1385class 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
1423template <typename K, typename M, typename H, typename E, typename A>
1424bool 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
1430template <typename K, typename M, typename H, typename E, typename A>
1431bool 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
1440namespace folly {
1441
1442template <typename K, typename M, typename H, typename E, typename A>
1443void 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
1449template <typename K, typename M, typename H, typename E, typename A>
1450void 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
1456template <typename K, typename M, typename H, typename E, typename A>
1457void 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
1463template <typename K, typename M, typename H, typename E, typename A>
1464void 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