folly/folly/container/detail/Util.h

/*
 * Copyright (c) Meta Platforms, Inc. and 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 <memory>
#include <tuple>
#include <type_traits>
#include <utility>

#include <folly/Traits.h>
#include <folly/container/Iterator.h>
#include <folly/functional/ApplyTuple.h>

// Utility functions for container implementors

namespace folly {
namespace detail {

template <typename KeyType, typename Alloc>
struct TemporaryEmplaceKey { … };

// A map's emplace(args...) function takes arguments that can be used to
// construct a pair<key_type const, mapped_type>, but that construction
// only needs to take place if the key is not present in the container.
// callWithExtractedKey helps to handle this efficiently by looking for a
// reference to the key within the args list.  If the search is successful
// then the search can be performed without constructing any temporaries.
// If the search is not successful then callWithExtractedKey constructs
// a temporary key_type and a new argument list suitable for constructing
// the entire value_type if necessary.
//
// callWithExtractedKey(a, f, args...) will call f(k, args'...), where
// k is the key and args'... is an argument list that can be used to
// construct a pair of key and mapped value.  Note that this means f gets
// the key twice.
//
// In some cases a temporary key must be constructed.  This is accomplished
// with std::allocator_traits<>::construct, and the temporary will be
// destroyed with std::allocator_traits<>::destroy.  Using the allocator's
// construct method reduces unnecessary copies for pmr allocators.
//
// callWithExtractedKey supports heterogeneous lookup with the UsableAsKey
// template parameter.  If a single key argument of type K is found in
// args... then it will be passed directly to f if it is either KeyType or
// if UsableAsKey<remove_cvref_t<K>>::value is true.  If you don't care
// about heterogeneous lookup you can just pass a single-arg template
// that extends std::false_type.

// TODO(T31574848): We can remove the std::enable_if_t once we no longer
// target platforms without N4387 ("perfect initialization" for pairs
// and tuples).  libstdc++ at gcc-6.1.0 is the first release that contains
// the improved set of pair constructors.
template <
    typename KeyType,
    typename MappedType,
    typename Func,
    typename UsableKeyType,
    typename Arg1,
    typename Arg2,
    std::enable_if_t<
        std::is_constructible<
            std::pair<KeyType const, MappedType>,
            Arg1&&,
            Arg2&&>::value,
        int> = 0>
auto callWithKeyAndPairArgs(
    Func&& f,
    UsableKeyType const& key,
    std::tuple<Arg1>&& first_args,
    std::tuple<Arg2>&& second_args) { … }

template <
    typename KeyType,
    typename MappedType,
    typename Func,
    typename UsableKeyType,
    typename... Args1,
    typename... Args2>
auto callWithKeyAndPairArgs(
    Func&& f,
    UsableKeyType const& key,
    std::tuple<Args1...>&& first_args,
    std::tuple<Args2...>&& second_args) { … }

ExactKeyMatchOnly;

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename Arg1,
    typename... Args2,
    std::enable_if_t<
        std::is_same<remove_cvref_t<Arg1>, KeyType>::value ||
            UsableAsKey<remove_cvref_t<Arg1>>::value,
        int> = 0>
auto callWithExtractedKey(
    Alloc&,
    Func&& f,
    std::piecewise_construct_t,
    std::tuple<Arg1>&& first_args,
    std::tuple<Args2...>&& second_args) { … }

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename... Args1,
    typename... Args2>
auto callWithExtractedKey(
    Alloc& a,
    Func&& f,
    std::piecewise_construct_t,
    std::tuple<Args1...>&& first_args,
    std::tuple<Args2...>&& second_args) { … }

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func>
auto callWithExtractedKey(Alloc& a, Func&& f) { … }

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename U1,
    typename U2>
auto callWithExtractedKey(Alloc& a, Func&& f, U1&& x, U2&& y) { … }

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename U1,
    typename U2>
auto callWithExtractedKey(Alloc& a, Func&& f, std::pair<U1, U2> const& p) { … }

template <
    typename KeyType,
    typename MappedType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename U1,
    typename U2>
auto callWithExtractedKey(Alloc& a, Func&& f, std::pair<U1, U2>&& p) { … }

// callWithConstructedKey is the set container analogue of
// callWithExtractedKey

template <
    typename KeyType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename Arg,
    std::enable_if_t<
        std::is_same<remove_cvref_t<Arg>, KeyType>::value ||
            UsableAsKey<remove_cvref_t<Arg>>::value,
        int> = 0>
auto callWithConstructedKey(Alloc&, Func&& f, Arg&& arg) { … }

template <
    typename KeyType,
    template <typename> class UsableAsKey = ExactKeyMatchOnly,
    typename Alloc,
    typename Func,
    typename... Args>
auto callWithConstructedKey(Alloc& a, Func&& f, Args&&... args) { … }

// Traits to simplify deduction guides implementation for containers.

// SFINAE constraint to test whether a type is an allocator according to
// is_allocator trait.
RequireAllocator;

RequireNotAllocator;

RequireInputIterator;

} // namespace detail
} // namespace folly