/* * Copyright (c) Facebook, Inc. and its affiliates. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #pragma once #include #include #include #include #include #include #include /** * This file is intended to be included only by F14Map.h. It contains fallback * implementations of F14Map types for platforms that do not support the * required SIMD instructions, based on std::unordered_map. */ #if !FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE namespace folly { namespace f14 { namespace detail { template class F14BasicMap : public std::unordered_map { using Super = std::unordered_map; template using EnableHeterogeneousFind = std::enable_if_t< ::folly::detail::EligibleForHeterogeneousFind::value, T>; template using EnableHeterogeneousInsert = std::enable_if_t< ::folly::detail::EligibleForHeterogeneousInsert::value, T>; template using IsIter = Disjunction< std::is_same>, std::is_same>>; template using EnableHeterogeneousErase = std::enable_if_t< ::folly::detail::EligibleForHeterogeneousFind< K, H, E, std::conditional_t::value, K, K2>>::value && !IsIter::value, T>; public: using typename Super::const_iterator; using typename Super::hasher; using typename Super::iterator; using typename Super::key_equal; using typename Super::key_type; using typename Super::mapped_type; using typename Super::pointer; using typename Super::size_type; using typename Super::value_type; F14BasicMap() = default; using Super::Super; //// PUBLIC - Modifiers std::pair insert(value_type const& value) { return emplace(value); } template std::enable_if_t< std::is_constructible::value, std::pair> insert(P&& value) { return emplace(std::forward

(value)); } // TODO(T31574848): Work around libstdc++ versions (e.g., GCC < 6) with no // implementation of N4387 ("perfect initialization" for pairs and tuples). template std::enable_if_t< std::is_constructible::value && std::is_constructible::value, std::pair> insert(std::pair const& value) { return emplace(value); } // TODO(T31574848) template std::enable_if_t< std::is_constructible::value && std::is_constructible::value, std::pair> insert(std::pair&& value) { return emplace(std::move(value)); } std::pair insert(value_type&& value) { return emplace(std::move(value)); } iterator insert(const_iterator /*hint*/, value_type const& value) { return insert(value).first; } template std::enable_if_t::value, iterator> insert(const_iterator /*hint*/, P&& value) { return insert(std::forward

(value)).first; } iterator insert(const_iterator /*hint*/, value_type&& value) { return insert(std::move(value)).first; } template iterator emplace_hint(const_iterator /*hint*/, Args&&... args) { return emplace(std::forward(args)...).first; } template void insert(InputIt first, InputIt last) { while (first != last) { insert(*first); ++first; } } void insert(std::initializer_list ilist) { insert(ilist.begin(), ilist.end()); } template std::pair insert_or_assign(key_type const& key, M2&& obj) { auto rv = try_emplace(key, std::forward(obj)); if (!rv.second) { rv.first->second = std::forward(obj); } return rv; } template std::pair insert_or_assign(key_type&& key, M2&& obj) { auto rv = try_emplace(std::move(key), std::forward(obj)); if (!rv.second) { rv.first->second = std::forward(obj); } return rv; } template iterator insert_or_assign( const_iterator /*hint*/, key_type const& key, M2&& obj) { return insert_or_assign(key, std::forward(obj)).first; } template iterator insert_or_assign(const_iterator /*hint*/, key_type&& key, M2&& obj) { return insert_or_assign(std::move(key), std::forward(obj)).first; } template EnableHeterogeneousInsert> insert_or_assign( K2&& key, M2&& obj) { auto rv = try_emplace(std::forward(key), std::forward(obj)); if (!rv.second) { rv.first->second = std::forward(obj); } return rv; } private: template using UsableAsKey = ::folly::detail:: EligibleForHeterogeneousFind; public: template std::pair emplace(Args&&... args) { auto alloc = this->get_allocator(); return folly::detail::callWithExtractedKey< key_type, mapped_type, UsableAsKey>( alloc, [&](auto& key, auto&&... inner) { if (!std::is_same>::value) { // this is a heterogeneous lookup auto it = find(key); if (it != this->end()) { return std::make_pair(it, false); } auto rv = Super::emplace(std::forward(inner)...); FOLLY_SAFE_DCHECK( rv.second, "post-find emplace should always insert"); return rv; } else { // callWithExtractedKey will use 2 inner args if possible, which // maximizes the changes for the STL emplace to search for an // existing key before constructing a value_type return Super::emplace(std::forward(inner)...); } }, std::forward(args)...); } template std::pair try_emplace(key_type const& key, Args&&... args) { return emplace( std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(std::forward(args)...)); } template std::pair try_emplace(key_type&& key, Args&&... args) { return emplace( std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::forward_as_tuple(std::forward(args)...)); } template iterator try_emplace( const_iterator /*hint*/, key_type const& key, Args&&... args) { return emplace( std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(std::forward(args)...)) .first; } template iterator try_emplace( const_iterator /*hint*/, key_type&& key, Args&&... args) { return emplace( std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::forward_as_tuple(std::forward(args)...)) .first; } template EnableHeterogeneousInsert> try_emplace( K2&& key, Args&&... args) { return emplace( std::piecewise_construct, std::forward_as_tuple(std::forward(key)), std::forward_as_tuple(std::forward(args)...)); } using Super::erase; template EnableHeterogeneousErase erase(K2 const& key) { auto it = find(key); if (it != this->end()) { erase(it); return 1; } else { return 0; } } //// PUBLIC - Lookup private: template struct BottomKeyEqual { [[noreturn]] bool operator()(K2 const&, K2 const&) const { assume_unreachable(); } }; template static auto findLocal(Self& self, K2 const& key) -> folly::Optional { if (self.empty()) { return none; } using A2 = typename std::allocator_traits::template rebind_alloc< std::pair>; using E2 = BottomKeyEqual; // this is exceedingly wicked! auto slot = reinterpret_cast const&>(self) .bucket(key); auto b = self.begin(slot); auto e = self.end(slot); while (b != e) { if (self.key_eq()(key, b->first)) { return b; } ++b; } FOLLY_SAFE_DCHECK( self.size() > 3 || std::none_of( self.begin(), self.end(), [&](auto const& kv) { return self.key_eq()(key, kv.first); }), ""); return none; } template static auto& atImpl(Self& self, K2 const& key) { auto it = findLocal(self, key); if (!it) { throw_exception("at() did not find key"); } return (*it)->second; } public: mapped_type& at(key_type const& key) { return Super::at(key); } mapped_type const& at(key_type const& key) const { return Super::at(key); } template EnableHeterogeneousFind at(K2 const& key) { return atImpl(*this, key); } template EnableHeterogeneousFind at(K2 const& key) const { return atImpl(*this, key); } using Super::operator[]; template EnableHeterogeneousInsert operator[](K2&& key) { return try_emplace(std::forward(key)).first->second; } size_type count(key_type const& key) const { return Super::count(key); } template EnableHeterogeneousFind count(K2 const& key) const { return !findLocal(*this, key) ? 0 : 1; } bool contains(key_type const& key) const { return count(key) != 0; } template EnableHeterogeneousFind contains(K2 const& key) const { return count(key) != 0; } private: template static std:: enable_if_t::value, Iter> fromLocal(LocalIter const& src, int = 0) { return Iter(src); } template static std:: enable_if_t::value, Iter> fromLocal(LocalIter const& src) { Iter dst; static_assert(sizeof(dst) <= sizeof(src), ""); std::memcpy(std::addressof(dst), std::addressof(src), sizeof(dst)); FOLLY_SAFE_CHECK( std::addressof(*src) == std::addressof(*dst), "ABI-assuming local_iterator to iterator conversion failed"); return dst; } template static Iter findImpl(Self& self, K2 const& key) { auto optLocalIt = findLocal(self, key); if (!optLocalIt) { return self.end(); } else { return fromLocal(*optLocalIt); } } public: iterator find(key_type const& key) { return Super::find(key); } const_iterator find(key_type const& key) const { return Super::find(key); } template EnableHeterogeneousFind find(K2 const& key) { return findImpl(*this, key); } template EnableHeterogeneousFind find(K2 const& key) const { return findImpl(*this, key); } private: template static auto equalRangeImpl(Self& self, K2 const& key) { auto first = self.find(key); auto last = first; if (last != self.end()) { ++last; } return std::make_pair(first, last); } public: using Super::equal_range; template EnableHeterogeneousFind> equal_range( K2 const& key) { return equalRangeImpl(*this, key); } template EnableHeterogeneousFind> equal_range(K2 const& key) const { return equalRangeImpl(*this, key); } //// PUBLIC - F14 Extensions #if FOLLY_F14_ERASE_INTO_AVAILABLE // emulation of eraseInto requires unordered_map::extract template iterator eraseInto(const_iterator pos, BeforeDestroy&& beforeDestroy) { iterator it = erase(pos, pos); FOLLY_SAFE_CHECK(std::addressof(*it) == std::addressof(*pos), ""); return eraseInto(it, beforeDestroy); } template iterator eraseInto(iterator pos, BeforeDestroy&& beforeDestroy) { const_iterator prev{pos}; ++pos; auto nh = this->extract(prev); FOLLY_SAFE_CHECK(!nh.empty(), ""); beforeDestroy(std::move(nh.key()), std::move(nh.mapped())); return pos; } template iterator eraseInto( const_iterator first, const_iterator last, BeforeDestroy&& beforeDestroy) { iterator pos = erase(first, first); FOLLY_SAFE_CHECK(std::addressof(*pos) == std::addressof(*first), ""); while (pos != last) { pos = eraseInto(pos, beforeDestroy); } return pos; } private: template size_type eraseIntoImpl(K2 const& key, BeforeDestroy& beforeDestroy) { auto it = find(key); if (it != this->end()) { eraseInto(it, beforeDestroy); return 1; } else { return 0; } } public: template size_type eraseInto(key_type const& key, BeforeDestroy&& beforeDestroy) { return eraseIntoImpl(key, beforeDestroy); } template EnableHeterogeneousErase eraseInto( K2 const& key, BeforeDestroy&& beforeDestroy) { return eraseIntoImpl(key, beforeDestroy); } #endif bool containsEqualValue(value_type const& value) const { // bucket isn't valid if bucket_count is zero if (this->empty()) { return false; } auto slot = this->bucket(value.first); auto e = this->end(slot); for (auto b = this->begin(slot); b != e; ++b) { if (b->first == value.first) { return b->second == value.second; } } return false; } // exact for libstdc++, approximate for others std::size_t getAllocatedMemorySize() const { std::size_t rv = 0; visitAllocationClasses( [&](std::size_t bytes, std::size_t n) { rv += bytes * n; }); return rv; } // exact for libstdc++, approximate for others template void visitAllocationClasses(V&& visitor) const { auto bc = this->bucket_count(); if (bc > 1) { visitor(bc * sizeof(pointer), 1); } if (this->size() > 0) { visitor(sizeof(StdNodeReplica), this->size()); } } template void visitContiguousRanges(V&& visitor) const { for (value_type const& entry : *this) { value_type const* b = std::addressof(entry); visitor(b, b + 1); } } }; } // namespace detail } // namespace f14 template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14ValueMap : public f14::detail::F14BasicMap { using Super = f14::detail::F14BasicMap; public: using typename Super::value_type; F14ValueMap() = default; using Super::Super; F14ValueMap& operator=(std::initializer_list ilist) { Super::operator=(ilist); return *this; } }; template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14NodeMap : public f14::detail::F14BasicMap { using Super = f14::detail::F14BasicMap; public: using typename Super::value_type; F14NodeMap() = default; using Super::Super; F14NodeMap& operator=(std::initializer_list ilist) { Super::operator=(ilist); return *this; } }; template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14VectorMap : public f14::detail::F14BasicMap { using Super = f14::detail::F14BasicMap; public: using typename Super::const_iterator; using typename Super::iterator; using typename Super::value_type; F14VectorMap() = default; using Super::Super; F14VectorMap& operator=(std::initializer_list ilist) { Super::operator=(ilist); return *this; } }; template < typename Key, typename Mapped, typename Hasher, typename KeyEqual, typename Alloc> class F14FastMap : public f14::detail::F14BasicMap { using Super = f14::detail::F14BasicMap; public: using typename Super::value_type; F14FastMap() = default; using Super::Super; F14FastMap& operator=(std::initializer_list ilist) { Super::operator=(ilist); return *this; } }; } // namespace folly #endif // !if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE