folly/folly/container/HeterogeneousAccess.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 <functional>
#include <string>
#include <string_view>

#include <folly/Range.h>
#include <folly/Traits.h>
#include <folly/container/HeterogeneousAccess-fwd.h>
#include <folly/hash/Hash.h>

namespace folly {

// folly::HeterogeneousAccessEqualTo<T>, and
// folly::HeterogeneousAccessHash<T> are functors suitable as defaults
// for containers that support heterogeneous access.  When possible, they
// will be marked as transparent.  When no transparent implementation
// is available then they fall back to std::equal_to and std::hash
// respectively.  Since the fallbacks are not marked as transparent,
// heterogeneous lookup won't be available in that case.  A corresponding
// HeterogeneousAccessLess<T> could be easily added if desired.
//
// If T can be implicitly converted to a StringPiece or
// to a Range<T::value_type const*> that is hashable, then
// HeterogeneousAccess{EqualTo,Hash}<T> will be transparent without any
// additional work.  In practice this is true for T that can be convered to
// StringPiece or Range<IntegralType const*>.  This includes std::string,
// std::string_view (when available), std::array, folly::Range,
// std::vector, and folly::small_vector.
//
// Additional specializations of HeterogeneousAccess*<T> should go in
// the header that declares T.  Don't forget to typedef is_transparent to
// void and folly_is_avalanching to std::true_type in the specializations.

template <typename T, typename Enable>
struct HeterogeneousAccessEqualTo : std::equal_to<T> { … };

template <typename T, typename Enable>
struct HeterogeneousAccessHash : std::hash<T> { … };

//////// strings

namespace detail {

template <typename T, typename Enable = void>
struct ValueTypeForTransparentConversionToRange { … };

// We assume that folly::hasher<folly::Range<T const*>> won't be enabled
// when it would be lower quality than std::hash<U> for a U that is
// convertible to folly::Range<T const*>.
ValueTypeForTransparentConversionToRange<T, void_t<decltype(std::declval<hasher<Range<const typename T::value_type *>>>()(std::declval<Range<const typename T::value_type *>>()))>>;

TransparentlyConvertibleToRange;

template <typename T>
struct TransparentRangeEqualTo { … };

template <typename T>
struct TransparentRangeHash { … };

template <>
struct TransparentRangeHash<char> { … };

template <
    typename TableKey,
    typename Hasher,
    typename KeyEqual,
    typename ArgKey>
struct EligibleForHeterogeneousFind
    : Conjunction<
          is_transparent<Hasher>,
          is_transparent<KeyEqual>,
          is_invocable<Hasher, ArgKey const&>,
          is_invocable<KeyEqual, ArgKey const&, TableKey const&>> { … };

EligibleForHeterogeneousInsert;

} // namespace detail

HeterogeneousAccessEqualTo<T, std::enable_if_t<detail::TransparentlyConvertibleToRange<T>::value>>;

HeterogeneousAccessHash<T, std::enable_if_t<detail::TransparentlyConvertibleToRange<T>::value>>;

} // namespace folly